Jump to content

Non-blocking linked list

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Athomeinkobe (talk | contribs) at 14:01, 28 December 2014 (→Concurrent insert and delete: fixed link to disambiguation page). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

Insert

Basic idea

Delete

Basic idea

Contains

Basic idea

  • search for a specific value in the list and return whether it is present or not
  • this is a read only operation, does not pose any concurrency issues

Problems

Concurrent insert and delete

  • 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

Concurrent deletions

  • two processes concurrently delete an adjacent node: node B and node C respectively
  • the delete of node C is undone by the delete of node B

Solutions

Valois [3]

  • make use of auxiliary nodes which contain only a next field
  • each regular node must have an auxiliary node as its predecessor and successor
  • deletion will result in an extra auxiliary node being left behind, which means the delete will have to keep trying to cleanup the extra auxiliary nodes
  • use an extra 'back_link' field so the delete operation can traverse back to a node that has not been deleted from the list

Further reading

  • A Pragmatic Implementation of Non-blocking Linked-Lists, Timothy L Harris
  • High Performance Dynamic Lock-Free Hash Tables and List-Based Sets, Maged M. Michael
  • Lock-Free Linked Lists and Skip Lists, Mikhail Fomitchev, Eric Ruppert
  • Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS, Michael Greewald
  • Highly-Concurrent Multi-word Synchronization, Hagit Attiya, Eshcar Hillel
  • Lock-free deques and doubly linked lists, Håkan Sundell, Philippas Tsigas

References

  1. ^ 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)
  2. ^ 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)
  3. ^ Valois, J. (1995), Lock-Free Linked Lists Using Compare-and-Swap, PODC '95 Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, New York, NY, USA, pp. 214–222{{citation}}: CS1 maint: location missing publisher (link)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Non-blocking_linked_list&oldid=639944759"