Non-blocking linked list

A non-blocking linked list is an example of non-blocking data structures designed to implement a linked list in shared memory using synchronization primitives:

• Compare-and-swap
• Fetch-and-add
• Load-link/store-conditional

Operations on lock-free linked lists

Insertion

Basic idea

• search for the right spot in the list
• insert using [Compare-and-swap]

Deletion

Basic idea

• search for the right spot in the list
• insert using [Compare-and-swap]

Problem

• a process deleting node B requires an atomic action on the node's predecessor
• concurrently another process tries to insert a node C after node B (B.next=C)
• node B is deleted from the list but C is gone along with it

Solutions

Harris, T. (2001), "A Pragmatic Implementation of Non-Blocking Linked Lists", DISC '01 Proceedings of the 15th International Conference on Distributed Computing, Springer-Verlag London, UK, pp. 300–314 http://dl.acm.org/citation.cfm?id=676105 {{citation}}: Missing or empty |title= (help)CS1 maint: location missing publisher (link)

• place a 'mark' in the next pointer of the soon-to-be deleted node
• fail when we try to CAS the 'mark'
• when detected go back to start of the list and restart

Further reading

• A Pragmatic Implementation of Non-blocking Linked-Lists, Timothy L Harris