陈春光，张坤龙，谭龙飞，韩 昭

(天津大学 a.软件学院；b.计算机科学与技术学院，天津 300072)

1 概述

在共享数据结构中，实现并发程序最常用的方法是使用互斥锁。然而，这种方法每次只允许一个线程处于临界区，当处于临界区的线程停止时，会阻止其他的线程进入临界区，整个系统都会停止前进，从而降低了系统的健壮性和可靠性。此外，互斥锁还会产生护航和优先级反转的问题。而利用非阻塞算法实现共享数据结构能够很好地解决这些问题，非阻塞算法能够确保在有限数目的操作步骤内总有某些操作能够完成，保证系统能够前进。同时，非阻塞算法还能提高并发度，因为它允许多个线程同时修改共享数据结构。

在自组织链表中有一套用来进行自组织的规则，每次操作后根据规则对链表进行重新组织，使得经常访问的结点位于链表前部。因此，在处理局部性较强的请求序列时，自组织链表有明显的优势。常用的3种自组织规则为MTF(Move-to-Front)规则、TP(Transpose)规则和 FC(Frequency-Count)规则[1]。本文使用并发 MTF规则，即每个线程在操作后把访问的结点移到链表的头部。

在并发自组织链表中，有多个线程在同一个自组织链表上进行操作，每个线程在每次操作后都需要对链表进行重新组织。操作后对链表进行重新组织是并发自组织链表的一个难点，因为一个线程对链表的自组织操作可能会影响其他线程的操作，其解决方法是对链表中的结点(称为数据结点)维护一个副本结点，对副本结点进行自组织操作，数据结点保持不动。……