基于Transpose规则的无锁自组织链表算法

自组织链表可以依据访问序列动态调整链表结构,提高链表性能。在分析并研究现有自组织链表算法的基础上,结合Transpose规则,提出无锁自组织链表算法。线程可标记被访问的结点并尝试与标记结点前驱相交换,也可直接物理删除已被标记的结点,同时其他线程发现该标记结点时会辅助该线程完成相应操作,从而保证链表的非阻塞特性。实验结果表明,该算法性能与Harris-Michael链表算法相当,并且其无锁实现方式比粗粒度锁算法更具优势。

Lock-free Self-organizing Linked-list Algorithm Based on Transpose Rule