Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #972

Lock free linked lists with Harris's delete bit

Show all headers | View raw

Hi,

I am fairly new to lock free programming and am attempting to implement (or reuse) a solution for lock free linked lists in C (logical delete only -  multiple writers and multiple readers). I am aware of existing libraries that solve the problem (concurrency kit, liblfds) but am having trouble understanding the algorithm described in Harris's paper. 

The basic idea is to atomically mark a node X that is to be deleted and then delete the node, in order to ensure, X's right node is also not concurrently modified. This seems to solve concurrency issues that can arise in both of the below situations:
1. Inserting after node X, while concurrently deleting node X:  As the next pointer on node X will be "marked" prior to a delete, either the node X will be successfully marked for delete or the new node will be successfully inserted after X, both cannot succeed due to the CAS operation involved in modifying X's next pointer
2. Deleting node X, while also deleting node Y = X->next: Similar to the above case, we can either succeed in marking node X for deletion,  or changing X->next, to delete node Y, and not both due to the CAS operation on X's next pointer.

Why do we then require the linked list to be sorted as is presented in algorithms that use Harris's delete bit? Am I missing any other concurrent operations that can cause a race condition?

Thank you for your time.
Vidya  

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar

Thread

Lock free linked lists with Harris's delete bit Vid <vidblr27@gmail.com> - 2012-07-23 19:23 -0700
  Re: Lock free linked lists with Harris's delete bit Dmitriy Vyukov <dvyukov@gmail.com> - 2012-07-24 22:39 -0700
    Re: Lock free linked lists with Harris's delete bit vidblr27@gmail.com - 2012-07-25 15:58 -0700
  Re: Lock free linked lists with Harris's delete bit Toby Douglass <a@b.com> - 2012-09-10 09:48 +0200

csiph-web