康 超 凡

(天津大学计算机科学与技术学院 天津 300000)



基于MTF规则的非阻塞自组织链表

康 超 凡

(天津大学计算机科学与技术学院 天津 300000)

自组织链表是一种特殊的链表。与静态链表相比，将自组织链表应用于并发环境下，需要考虑自组织操作对链表状态的改变。因此，对于并发自组织链表，尤其是具有非阻塞特性的自组织链表的研究更加复杂。近些年来，并发链表的研究成果显著，而关于并发自组织链表算法的研究屈指可数。在这种背景下，提出了一种基于MTF(Move-To-Front)自组织规则的无锁自组织链表，证明了该链表算法实现了在集合上的插入、删除，以及查找操作，并且算法的实现是无锁的。实验结果表明，该算法的性能在大多数情况下都优于Harris算法，具有一定的使用价值。

并发 无锁 自组织 链表

0 引 言

链表是一种常见的数据结构，可以使用非连续的存储空间来存储结点元素。在程序设计中，链表实现简单，性能优越，具有非常广泛的应用。自组织链表是一种特殊的链表，最初源于搜索问题，是McCabe在1965年提出的[1]。自组织链表可以在链表的访问过程中对链表结点进行动态调整，在访问数据具有较强的局部性的时候，自组织链表与静态链表相比具有更高的搜索速率和更短的平均访问时间，从而表现出更好的性能。

针对于自组织链表的链表更新问题，最常用的确定型联机算法主要有三种:MTF(Move-To-Front)、TP(Transpose)，以及FC(Frequency-Count)[2]。MTF规则是每次对链表进行访问时，将被访问的结点移动到链表头部；……