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:
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 [1]
- 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
- Zhang et all [2]
See also
![[icon]](/wiki/File:Wiki_letter_w_cropped.svg?lang=en){kind=small} | This section is empty. You can help by adding to it. (November 2014) |
Further reading
- A Pragmatic Implementation of Non-blocking Linked-Lists, Timothy L Harris
References
- ^ 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
{{citation}}: CS1 maint: location missing publisher (link) - ^ Zhang, K.; Zhao, Y.; Yang, Y.; Liu, Y.; Spear, M. (2013), Practical Non-Blocking Unordered Lists, DISC '13 Proceedings of the 27th International Conference on Distributed Computing, Jerusalem, Israel
{{citation}}: CS1 maint: location missing publisher (link)