如何实现无锁跳跃列表

本文介绍了如何实现无锁跳跃列表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要实现一个无锁跳跃列表。我试图寻找论文。不幸的是我所发现的是无锁单链表（许多种）。但是如何实现无锁跳跃列表？

I need to implement a lock-free skip list. I tried to look for papers. Unfortunatly all I found was lock-free single linked lists (in many flavors). However how to implement lock-free skip list?

推荐答案

无锁的跳跃列表在书中的艺术的多处理器编程和技术报告实用锁定自由，它是基于一个博士论文的主题。跳跃列表开始讨论第53页示例实现，基于这些资源上，包括在这个谷歌code ++项目。

Lock-free skip lists are described in the book The Art of Multiprocessor Programming, and the technical report Practical lock-freedom, which is based on a PhD thesis on the subject. The skip list discussion begins on page 53. An example implementation, based on these sources, is included in this google code project.

有相关的讨论，在做题链接到文学和实现（不一定是无锁）的跳转列表与二叉树和跳转列表 - 使用过他们？ / A>。

There are related discussions, links to literature and implementations (not necessarily lock-free) in the SO questions Skip List vs. Binary Tree, and Skip Lists - ever used them?.