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:
Description
Linked lists are fundamental data structures widely that are widely used as is or to build other data structures. Concurrent linked are challenging to design because of time and space complexity.
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]
- search the list to see if the value to be deleted exists, if exists mark the node logically deleted
- a subsequent traversal of the list will do garbage collection of logically deleted nodes
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)