康 超 凡

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



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

康 超 凡

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

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

并发 无锁 自组织 链表

0 引 言

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

针对于自组织链表的链表更新问题，最常用的确定型联机算法主要有三种:MTF(Move-To-Front)、TP(Transpose)，以及FC(Frequency-Count)[2]。MTF规则是每次对链表进行访问时，将被访问的结点移动到链表头部；TP规则是每次访问链表结点时，将被访问的结点与其直接前驱进行交换；FC规则是一种基于访问计数的自组织规则，需要额外的空间记录链表中每个结点的被访问次数，当结点被访问时，次数加1，同时维护链表，使链表中的结点按照被访问次数非递增的顺序排列。

在当前的多核处理器时代，并发程序与传统的串行程序相比，更能充分发挥多核处理器的优势。近些年来，并发程序设计问题成为人们重点研究和讨论的问题。

数据结构是程序设计的基础与核心，链表是一种常见的数据结构，为了发挥多处理器的优势，并发链表的设计与实现，具有重要的意义。根据不同的同步机制，并发链表可以分为阻塞链表和非阻塞链表。

阻塞链表的实现一般采用加锁的方法，如粗粒度同步链表、细粒度同步链表、乐观同步链表，以及惰性同步链表等。这种加锁的算法实现较为简单，但是可能会带来死锁和优先级反转等问题。

与阻塞链表相比，非阻塞链表不使用锁来实现同步，而是使用更强的原子指令。在非阻塞链表中，线程间的执行是互不影响的，某一个线程的延迟并不会对其他线程的执行带来影响。而根据不同的演进性条件，非阻塞又分为无妨碍、无锁，以及无等待。三个演进性条件依次增强。其中无妨碍特性保证了如果在线程调用过程中其他所有线程调用被暂停，那么该线程调用将在有限步骤内完成；无锁保证了至少存在一个线程调用能够在有限步骤内完成；无等待是最强的演进性条件，在无等待条件下，所有线程调用都能够在有限步骤内完成[3]。

Valois提出了第一个基于CAS(compare-and-swap)的无阻塞并发链表[4]。在Valois的链表中，在普通结点之间添加了辅助结点，用来解决并发操作中可能出现的插入丢失和删除丢失问题，同时使用backlink技术实现快速重做。之后Harris提出了另一种简单有效的无锁链表的实现方法[5]。Harris的算法主要思想是在链表中的结点被物理删除之前先对结点进行标记。Harris的算法与Valois的算法相比，实现更加简单，并且性能更好。之后，Michael提出一个静态的无锁哈希表的算法[6]，其中哈希表中桶的实现使用了一种基于Harris算法的无锁链表算法。这种链表算法与Harris链表算法大同小异，二者合称为Harris-Michael算法。Fomitchev和Ruppert将Valois和Harris算法的思想相结合，提出了一种新的无锁链表的实现方法，并且使用分摊分析证明了算法有较好的平均复杂度[7]。Braginsky等则提出了一种基于局部感知的无锁链表的实现方法[8]。Timnat等提出了第一个基于单CAS指令的无等待链表算法[9]，算法在Harris的无锁并发链表的基础上，通过使用帮助机制实现了具有无等待演进特性的并发链表。Zhang等设计并实现了新的无锁和无等待的无序链表的算法，具有良好的性能[10]。

自组织链表是一种非常具有实用价值的数据结构，将自组织链表应用于并发环境下，可以充分发挥多核处理器的优势，获得更好的执行性能。阻塞方式的实现简单，但是加锁的方法使算法难以实现高并行性；非阻塞方式与阻塞方式相比具有更好的可靠性和健壮性。Herlihy[11-13]等证明了使用CAS操作原语能够实现任何非阻塞数据结构，但是这种通用构造的方法实现较为复杂，并且效率不高。因此，对于实现非阻塞自组织链表算法，需要更加精细的设计。

将自组织链表应用于并发环境下，自组织规则的应用会给算法的设计带来新的问题，难以保证算法的正确性。以基于MTF规则的自组织链表为例，在应用MTF规则时，需要将被访问的结点移动到链表的头部，具体操作为：先将结点从原位置删除，再插入到链表的头部。在单个线程对链表进行顺序访问时，上一次的访问中对访问结点位置的调整不会影响到当前对链表的访问。然而在多线程的并发环境下，多个线程可以同时对共享链表进行操作，一个线程所执行的MTF自组织操作，将访问结点移动到链表头部的过程中，可能会影响到另外的线程对该结点的访问，从而造成相应的访问错误。这也是在设计非阻塞自组织链表的过程中所需要解决的难点问题。

谭龙飞提出了一种基于副本的无锁自组织链表[14]。这个算法在链表数据结点的基础上又引入了数据结点的副本结点。算法中对MTF自组织规则的执行只在副本结点中进行，而不会修改数据结点，从而巧妙地解决了由于MTF导致的由于其他线程将结点移动到链表头部而导致可能出现的结点在链表中而搜索不到的问题。链表的实现较为简单，但是增加了维护副本结点的空间开销。

1 算法设计

本文实现了一个基于MTF规则的无锁自组织链表算法。链表的结构如表1所示。

表1 无锁MTF自组织链表结构及初始化

链表中的结点分为五个域：key域和next域分别表示结点的键值和指向下一个结点的指针；state域表示该结点目前所处的状态：其中，DAT表示该结点可能属于集合元素，REM表示该结点最终将要被逻辑删除，INV表示该结点已经被逻辑删除；result域表示操作的结果：FND表示找到目标结点，NFD表示没有找到目标结点，UNK表示目前还没有找到目标结点；friend指针域，指向当前结点的下一个朋友结点，所谓朋友结点，指的是链表中当前结点之后，与当前结点具有相同键值并且state=DAT的结点。在链表中，通过每个结点的firend指针形成相应的朋友链，同时用dummy来表示朋友结点的结束。

算法实现了链表的查找、删除和插入方法。这三个方法的主要思想是在链表的头部插入相应的操作结点，然后调用search方法向后进行链表的遍历。同时在遍历的过程中对朋友结点进行监听。search方法是查找、删除和插入操作的基础和核心部分。

算法中对于在链表头部插入的操作结点定义如下：

数据结点: state=DAT&result=FND

查找结点: state=DAT &result=UNK

删除结点: state=REM&result=UNK

插入结点:数据结点+删除结点

算法的伪代码如表2-表6。

表2 search方法

表3 contains方法

表4 insert方法

表5 remove方法

表6 enlist方法

1.1 搜索操作

search方法是整个算法中的基础算法，链表的插入、删除，以及查找操作都会调用这个方法。search方法以home结点作为当前结点开始向后进行链表的遍历，搜索与home结点键值相等的结点，处理并返回搜索结果的布尔值。

search方法在遍历链表过程中，会遇到以下情况：

(1) 对home结点或新加入的朋友结点进行监听，如果监听到朋友结点得到NFD或者FND的搜索结果，则结束遍历。

(2) 搜索到状态为INV的结点，此结点表示已经被逻辑删除，对其进行物理删除，并继续向后遍历。

(3) 搜索到与home结点键值不相等的结点，继续向后遍历。

(4) 搜索到与home结点键值相等的状态为DAT的数据结点或者搜索结点，此结点为朋友结点，将其加入到朋友链中，同时改为监听此结点，并继续向后遍历。

(5) 搜索到与home结点键值相等状态为REM的删除结点，设置线程搜索结果result值为NFD，结束遍历。

(6) 遍历到链表尾部，结束遍历。

search方法在结束遍历之后，无论是自己得到操作结果还是从朋友结点监听得到操作结果，都一定会得到FND或者NFD的结果。接下来线程将此结果通知到所有朋友结点，并对这些朋友结点进行逻辑删除。

完成上述两步操作之后，可以保证home结点之后将不存在与home结点键值相等的查找结点或者数据结点。

1.2 查找操作

contains方法是查找操作，方法以需要查找的键值作为参数，查找链表中具有相同键值的结点，并返回查找结果的布尔值。contains方法首先创建一个查找结点home={key=x，state=DAT，result=UNK}，并且调用enlist方法将该结点插入到链表的头部，然后从该结点开始调用search方法进行遍历，最后contains方法返回search方法的搜索结果。如果search方法返回true，则表示链表中home结点之后存在目标结点，并且在search方法返回之前将目标结点逻辑删除，contains方法最初插入的查找结点作为数据结点，相当于执行了MTF操作，contains方法直接返回true，表示查找成功；如果search方法返回false，则表示链表中home结点之后不存在目标结点，contains方法将home结点逻辑删除之后返回false表示查找失败。

1.3 删除操作

remove方法是删除操作，方法将需要删除的键值作为参数，删除链表中具有相同键值的结点，并返回删除是否成功的布尔值。

remove方法首先创建一个删除结点home={key=x，state=REM，result=UNK}，并调用enlist方法将此结点插入到链表头部，从该结点开始调用search方法对链表进行遍历。如果search方法返回true，说明链表中home结点之后存在目标结点，并且在search方法返回之前将目标结点逻辑删除，remove方法将home结点逻辑删除后，返回true，表示删除成功；如果search方法返回false，表示链表之中在home结点之后不存在目标结点，remove方法将home结点逻辑删除后，返回false表示删除失败。

1.4 插入操作

insert方法为链表的插入操作，该方法以需要插入的键值为参数，向链表中插入该键值的结点，并且返回插入操作是否成功的布尔值。

insert方法首先创建一个数据结点和一个删除结点。node={key=x，state=DAT，result=FND}是数据结点，home={key=x，state=REM，result=UNK}是删除结点，并且node结点的next域指向home结点。接下来，以home结点为起始结点调用search方法进行链表的遍历，如果search方法返回true，表示链表中home结点以后存在目标结点，并且在search方法返回之前已经将目标结点删除，insert方法在search方法返回true之后，将home结点逻辑删除。最初在链表头部插入的数据结点相当于对原数据结点执行了MTF操作，最后insert方法返回false表示插入失败；如果search方法返回false，表示链表之中home结点之后不存在目标结点，insert方法在search方法返回false之后，将home结点逻辑删除。最初在链表头部插入的数据结点相当于新插入的数据结点，并且执行了MTF操作，最后insert方法返回true表示插入成功。

1.5 结点加入操作

enlist方法是向链表头部插入操作结点的方法。该方法输入参数包括first结点和last结点，enlist方法首先将last结点指向head指向的结点，然后使用CAS操作扭转head指针指向first结点。方法反复执行这一过程直至CAS操作成功。调用enlist方法将操作结点插入到链表头部这一过程是无锁的，当有多个线程同时执行这一操作时，至少有一个线程的CAS操作能够成功执行并返回。

2 正确性证明

并发对象的行为可以用安全性和活性来描述，也称为正确性和演进性[3]，安全性是指算法实现了一个抽象数据结构，活性指的是算法的演进性保证，包括阻塞特性和非阻塞特性。

常见的正确性条件有静态一致性、顺序一致性和可线性化特性。其中可线性化特性是一种较强的条件约束，适用于可线性化组件构成的高层系统[3]。本文使用可线性化特性作为算法的正确性条件。

本文中提出的算法没有加锁，同时保证了总有一个线程调用能够在有限步骤内完成，具有无锁的演进特性。

本文将在2.1节和2.2节分别对算法的可线性化性和无锁特性进行说明。

2.1 算法的可线性化性

要证明算法实现的数据结构对应一个顺序对象的可线性化实现，只需要找到一个可线性化点。

本节对算法的可线性化证明的主要框架是把算法的实现映射到一个抽象的整型集合，证明该算法实现了一个整形集合，并且算法中的每个成功的或者失败的insert、remove，以及contains方法都在可线性化点上发生。

无锁自组织链表实现了一个抽象的整数集合，由以h为起点的链表中元素到抽象集合的映射关系如下：

定义基于MTF无锁自组织链表的可线性化点为：

insert(x)操作、remove(x)操作，以及contains(x)操作的可线性化点都在enlist中成功的CAS操作。

对于线程p执行insert(x)操作：若在执行CAS操作之前x∉AbsSet(head)，如果p成功执行CAS操作，将键值为x的数据结点和删除结点插入到链表中，那么insert(x)返回true，x∈AbsSet(head)；若在执行CAS操作之前x∈AbsSet(head)，如果p成功执行CAS操作，将键值为x的数据结点first和删除结点last插入到链表中，相当于对键值为x的结点执行了MTF操作，并且search方法的执行保证了first结点之后不存在有效的键值为x的数据结点或查找结点。insert(x)返回false。

对于线程p执行remove(x)操作：若在执行CAS操作之前x∉AbsSet(head)，如果p成功执行CAS操作，将键值为x的删除结点插入到链表中，search方法的执行保证了删除结点得到NFD的遍历结果，remove(x)方法返回false；若在执行CAS操作之前x∈AbsSet(head)，如果p成功执行CAS操作，将键值为x的删除结点插入到链表中，search方法的执行保证了删除结点之后不存在键值为x的结点，成功执行了删除操作，remove(x)方法返回true，且x∉AbsSet(head)。

对于线程p执行contains(x)操作：若在执行CAS操作之前x∉AbsSet(head)，如果p成功执行CAS操作，将键值为x的查找结点插入到链表中，search方法的执行保证了查找结点得到NFD的遍历结果，contains(x)方法返回false；若在执行CAS操作之前x∈AbsSet(head)，如果p成功执行CAS操作，将键值为x的查找结点插入到链表中，相当于对键值为x的结点执行了MTF操作，同时保证了查找结点之后不存在键值为k的数据结点或查找结点，contains(x)返回true。

综上所述，本文提出的基于MTF自组织规则的无锁自组织链表是可线性化的。

2.2 算法的无锁特性

该算法提供的关于链表的插入、删除和查找操作都是先创建相应的操作结点，并调用enlist方法将操作结点加入到链表的头部，接下来再进行search操作。

线程调用enlist方法将操作结点加入到链表头部的过程需要循环调用CAS操作，直到操作成功。当有多个线程同时执行操作结点的加入，CAS操作可以保证至少有一个线程可以插入成功，因此这一个过程是无锁的。

search方法对链表中的结点进行遍历，并物理删除已经被逻辑删除的结点，search对结点的遍历最长会遍历到链表的尾部，而且链表是无环的，因此遍历操作必然会在有限步骤内完成。

综上所述，该算法的实现是无锁的。

3 组织链表的性能分析

3.1 实验环境与实验内容

实验是在4核8线程64位计算机上运行，计算机内存为8 GB，操作系统为Microsoft Windows 10，Java版本为1.8，算法在MyEclipse下用Java实现。

本实验中共实现了三个算法：

Harris：Harris-Michael实现的无锁有序的链表算法，链表中结点按升序排列；

MTFList：本文实现的基于MTF规则的无锁自组织链表算法；

TanList：文献[14]实现的基于副本的无锁自组织链表方法。

本文中实验所使用的实验数据取自并发自组织搜索树[15],使用的实验数据来源是具有局部性的数据集[16]。数据集中包含了33 135 073条IP记录，实验中根据需要，将这些IP记录通过哈希映射转换为整形。实验中每个线程从一个共享数组中相互独立地获取实验数据。

在实验中，通过在不同的操作比例和键值范围下运行算法，以吞吐率作为算法的性能指标，查看随着线程数目的变化，吞吐率的变化情况。其中操作比例指的是查找、插入和删除操作的调用比例，分三种情况：34%/33%/33%、50%/45%/5%，以及90%/9%/1%；键值范围指的是结点中键值的取值范围，分为三种情况：0～512、0～2 048，以及0～8 192。实验在初始化时，会预先向链表中插入数目为键值范围一半的结点。在实验过程中，线程根据选定的操作比例，随机选择操作类型。

3.2 实验结果与实验分析

根据操作比例和键值范围的不同取值，实验共分为9组，每组实验运10次，每次运行5秒钟，最终结果取平均值。实验结果如图1-图9所示。

图1 不同线程数下的吞吐率(键值范围0～512，操作比例34%/33%/33%)

图2 不同线程数下的吞吐率(键值范围0～2 048，操作比例34%/33%/33%)

图3 不同线程数下的吞吐率(键值范围0～8 192，操作比例34%/33%/33%)

图4 不同线程数下的吞吐率(键值范围0～512，操作比例50%/45%/5%)

图5 不同线程数下的吞吐率(键值范围0～2 048，操作比例50%/45%/5%)

图6 不同线程数下的吞吐率(键值范围0～8 192，操作比例50%/45%/5%)

图7 不同线程数下的吞吐率(键值范围0～512，操作比例90%/9%/1%)

图8 不同线程数下的吞吐率(键值范围0～2 048，操作比例90%/9%/1%)

图9 不同线程数下的吞吐率(键值范围0～8 192，操作比例90%/9%/1%)

在每组实验结果图中，横轴表示线程数目，纵轴表示吞吐率。通过实验结果可以看出，在每组实验中，随着线程数目的增加，吞吐率也在增长。并且，与Harris和TanList两个算法相比，本文提出的MTFList算法的实验性能都是最好的。原因是该算法能充分利用数据的局部性，从而提高链表的访问速率。

通过图1、图2和图3，图4、图5和图6，图7、图8和图9可以看出，在操作比例不变的情况下，随着键值范围的增加，每个算法的吞吐率都有所下降，但随着线程数目增加，每个算法吞吐率增加的基本趋势是不变的。

通过图1、图4和图7，图2、图5和图8，图3、图6和图9可以看出，在键值范围不变的情况下，随着查找和插入操作比例的增加，进行自组织操作的概率增加，本文提出的基于MTF无锁自组织链表的算法性能优于其他两个算法。

上述9组实验，通过控制变量的方法，观察了键值范围、操作比例,以及线程数目对算法性能的影响，可以得出如下结论：

(1) 在固定的操作比例和键值范围下，随着线程数目的增加，每个算法的性能都有所提高。

(2) 随着键值范围的增大，链表初始化时，链表的长度增加，执行操作时平均访问结点数目有所增加，因此，各个算法的性能都有所下降。

4 结 语

并发自组织链表能够充分发挥多核处理器的优势，在并发环境下可以通过动态调整访问结点在链表中的位置来提高链表访问效率，从而获取更好的性能。链表的无锁实现方式保证了总有一个线程能够完成操作，与基于锁的实现方式相比，避免了死锁和优先级反转等问题，具有更好的可靠性和健壮性；同时自组织链表在数据局部性较强的情况下，能够表现出更好的执行性能。

本文对目前已有的并发链表进行了总结和归纳，并提出了一个基于MTF规则的无锁自组织链表。并对新算法的可线性化性无锁特性进行了讨论。

本文设计的算法的实现是无锁的，即保证了总有一个操作能够完成操作。算法中，只有enlist的过程是无锁的，其他的过程都可以在有限步骤内完成，具有无等待的特性。因此，对enlist算法进行修改，确保enlist操作能够在有限步骤内完成，则可以实现一个无等待的MTF自组织链表。

针对并发环境下非阻塞自组织链表的研究还有很大的空间。除了MTF自组织规则，还有TP以及FC规则，都可以考虑将基于这些规则的链表应用于并发环境下。

[1] McCabe J. On serial files with relocatable records[J]. O-perations Research, 1965, 13(4): 609-618.

[2] Albers S, Westbrook J. Self-organizing data structures[M]//Online Algorithms. Springer Berlin Heidelberg, 1998: 13-51.

[3] Herlihy M, Shavit N. The Art of Multiprocessor Progra-mming, revised first edition[M]. Morgan Kaufmann, 2012.

[4] Valois J D. Lock-free linked lists using compare-and-swap[C]//Proceedings of the fourteenth annual ACM sympos-ium on Principles of distributed computing. ACM, 1995:214-222.

[5] Harris T L. A pragmatic implementation of non-blocking linked-lists[C]//International Symposium on Distributed C- omputing. Springer Berlin Heidelberg, 2001: 300-314.

[6] Michael M M. High performance dynamic lock-free hashtables and list-based sets[C]//Proceedings of the fourteent-h annual ACM symposium on Parallel algorithms and ar-chitectures. ACM, 2002: 73-82.

[7] Fomitchev M, Ruppert E. Lock-free linked lists and skip lists[C]//Proceedings of the twenty-third annual ACM sy-mposium on Principles of distributed computing. ACM, 2 004: 50-59.

[8] Braginsky A, Petrank E. Locality-conscious lock-free lin-ked lists[C]//International Conference on Distributed Computing and Networking. Springer Berlin Heidelberg, 2011:107-118.

[9] Timnat S, Braginsky A, Kogan A, et al. Wait-free linked-lists[C]//International Conference on Principles Of Distri-buted Systems. Springer Berlin Heidelberg, 2012: 330-344.

[10] Zhang K, Zhao Y, Yang Y, et al. Practical non-blockingunordered lists[C]//International Symposium on Distributed Computing. Springer Berlin Heidelberg, 2013: 239-253.

[11] Herlihy M P. Impossibility and universality results for wait-free synchronization[C]//Proceedings of the seventh annual ACM Symposium on Principles of distributed computing. ACM, 1988: 276-290.

[12] Herlihy M. Wait-free synchronization[J]. ACM Transacti-ons on Programming Languages and Systems (TOPLAS),1991, 13(1): 124-149.

[13] Barnes G. A method for implementing lock-free shared-data structures[C]//Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures. ACM,1993: 261-270.

[14] 谭龙飞. 基于副本的非阻塞自组织链表[D]. 天津： 天津大学, 2012.

[15] Korenfeld B. CBTree: A Practical Concurrent Self-Adjusting Search Tree[D]. Tel Aviv, Israel: Tel Aviv Universit-y, 2012.

[16] Kc Clay, Dan Andersen, Paul Hick. The caida anonymized 2011 internet traces[OL]. [2016-07-17]. http://www.caida.org/data/passive/passive_2011_dataset.xml.

NON-BLOCKING SELF-ORGANIZED LINKED LIST BASED ON MTF RULE

Kang Chaofan

(SchoolofComputerScienceandTechnology,TianjinUniversity,Tianjin300000,China)

Self-organized linked list is a special linked list. Comparing with the static linked list, we need to consider that self-organized operation would change the status of the linked list. Therefore, the study of concurrent self-organized list, especially the non-blocking self-organized linked list, is more complex. In recent years, the results of concurrent linked list have been significant, but studies on the linked list algorithms are few and far between. In this context, this paper proposes a lock-free self-organized linked list algorithm based on the move-to-front self-organized rule. The algorithm implements the insertion, deletion and searching operation on the set, and the implementation of the algorithm is lock-free. The experimental results show that the performance of the algorithm is superior to the Harris algorithm in most cases, and has a certain value.

Concurrency Lock-free Self-organized Linked List

2016-10-16。康超凡，硕士生，主研领域：并发数据结构。

TP311.11

A

10.3969/j.issn.1000-386x.2017.07.053