Non-blocking linked list

(Singly) linked lists are fundamental data structures that are widely used as is, or to build other data structures. They consist of "nodes", or "links", that are put in some order indicated by a "next" pointer on each node. The last node in the list (the "tail") has a {{mono|nil}} next pointer. The first node (the "head") is a sentinel: it stores no interesting information and is only used for its {{mono|next}} pointer.

The operations that must be supported on lists are as follows.

• Given a node {{mono|n}} that is not yet part of the list, and a pointer {{mono|p}} to a node in the list (perhaps the head), insert {{mono|n}} after {{mono|p}}.
• Given a pointer {{mono|p}}, delete {{mono|p.next}} from the list.

Both operations must support concurrent use: two or more threads of execution must be able to perform insertions and deletions without interfering with each other's work (see diagram).

File:Lock-free linked list error.svg

In a 2001 paper, Harris gives a solution to concurrent maintenance of ordered linked list that is non-blocking, using a compare-and-swap ({{mono|cas}}) primitive.{{r|harris}} Insertion of {{mono|n}} after {{mono|p}} is simple:

1. {{mono|next ← p.next}}
2. {{mono|n.next ← next}}
3. {{mono|cas(address-of(p.next), next, n)}}
4. If the {{mono|cas}} was not successful, go back to 1.

Deletion of {{mono|p.next}} is more involved. The naive solution of resetting this pointer with a single CAS runs the risk of losing data when another thread is simultaneously inserting (see diagram). This is specific case of the ABA problem. Instead, two invocations of {{mono|cas}} are needed for a correct algorithm. The first marks the pointer {{mono|p.next}} as deleted, changing its value but in such a way that the original pointer can still be reconstructed. The second actually deletes the node by resetting {{mono|p.next}}.

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

• search for the right spot in the list
• delete using Compare-and-swap

• 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

• 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

• Harris {{Citation

| last1 = Harris| first1 = T.

| title = A Pragmatic Implementation of Non-Blocking Linked Lists

| series = DISC '01 Proceedings of the 15th International Conference on Distributed Computing

| place = Springer-Verlag London, UK

| pages = 300–314

| year = 2001

| isbn = 9783540426059

| url = http://dl.acm.org/citation.cfm?id=676105 }}

• 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 al.{{Citation

| last1 = Zhang| first1 = K.

| last2 = Zhao| first2 = Y.

| last3 = Yang| first3 = Y.

| last4 = Liu| first4 = Y.

| last5 = Spear| first5 = M.

| title = Practical Non-Blocking Unordered Lists

| series = DISC '13 Proceedings of the 27th International Conference on Distributed Computing

| place = Jerusalem, Israel

| year = 2013

| url = http://dblp.uni-trier.de/db/conf/wdag/disc2013.html#ZhangZYLS13 }}

• 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

• 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

Valois {{Citation

| last1 = Valois| first1 = J.

| title = Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing - PODC '95

| chapter = Lock-Free Linked Lists Using Compare-and-Swap

| series = PODC '95 Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing

| place = New York, NY, USA

| pages = 214–222

| year = 1995

| doi = 10.1145/224964.224988

| isbn = 0897917103

| s2cid = 2047186

| chapter-url = http://dl.acm.org/citation.cfm?id=224988}}

• 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 clean up 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

• High Performance Dynamic Lock-Free Hash Tables and List-Based Sets, Maged M. Michael
• {{Cite conference | last1 = Fomitchev | first1 = Mikhail| last2 = Ruppert | first2 = Eric| doi = 10.1145/1011767.1011776 | title = Lock-free linked lists and skip lists | conference = Proc. Annual ACM Symp. on Principles of Distributed Computing (PODC)| pages = 50–59| year = 2004 | isbn = 1581138024 | url = http://www.cse.yorku.ca/~ruppert/papers/lfll.pdf}}
• 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

{{Reflist}}

Category:Linked lists