21

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?

Gabe
  • 84,912
  • 12
  • 139
  • 238
Maciej Piechotka
  • 7,028
  • 6
  • 39
  • 61

2 Answers2

19

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.

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?.

Community
  • 1
  • 1
ire_and_curses
  • 68,372
  • 23
  • 116
  • 141
5

This paper presents a lock-free and wait-free skip list. It's straightforward to implement - I implemented this a few weeks ago as part of the Intel Threading Challenge 2010 (see the SkipList tab halfway down the page.)

Java includes an implementation of a concurrent skip list, java.util.concurrent.ConcurrentSkipListMap.

mdma
  • 56,943
  • 12
  • 94
  • 128
  • 1
    Is your code available anywhere (it's not obvious to me on the Intel site as to where to get it.) – Eloff Jun 23 '12 at 00:22
  • 4
    The algorithm in the paper referred to is neither lock-free nor wait-free. – Jonatan Lindén Jan 14 '13 at 10:01
  • 1
    Jonatan, I just took a quick glimpse at the paper again and you may be right. I read so many papers at the time I must have got my wires crossed. That was over two years ago, so I no longer recall which paper I had in mind when thinking of the lock and wait free list. – mdma Jan 16 '13 at 07:46
  • @mdma: In your implementation, for the insert operation, there doesn't seem to be a linearization point, compared to the paper by Shavit et al. Can this cause any problems for a concurrent read operation? – user1715122 Oct 04 '13 at 11:33