What are some examples of lock-free and wait-free data structures and algorithms in multithreading?

1 Lock-free vs wait-free

Lock-free and wait-free are two properties that describe how data structures and algorithms handle concurrent access by multiple threads. A data structure or algorithm is lock-free if it guarantees that at least one thread can make progress in a finite number of steps, regardless of the actions of other threads. A data structure or algorithm is wait-free if it guarantees that every thread can make progress in a finite number of steps, regardless of the actions of other threads. Lock-free is a weaker property than wait-free, as it allows some threads to starve or retry indefinitely, while wait-free ensures bounded latency and fairness for all threads.

2 Atomic operations

One of the key tools for implementing lock-free and wait-free data structures and algorithms is atomic operations. Atomic operations are operations that can be performed on shared memory without being interrupted or interfered by other threads. They can be used to read, write, or modify a single word or a small set of words in an indivisible and consistent way. Atomic operations are usually supported by hardware instructions or software emulation, and they can provide various levels of guarantees, such as compare-and-swap (CAS), fetch-and-add (FAA), or load-linked/store-conditional (LL/SC).

3 Lock-free stack

A stack is a data structure that stores elements in a last-in, first-out (LIFO) order. A simple way to implement a lock-free stack is to use a singly-linked list with a head pointer that points to the top element. To push an element to the stack, a thread can use a CAS operation to atomically update the head pointer to point to the new element, while linking the new element to the previous head. To pop an element from the stack, a thread can use a CAS operation to atomically update the head pointer to point to the next element, while returning the previous head. If the CAS operation fails, it means that another thread has modified the head pointer, so the thread can retry with the updated value.

4 Wait-free queue

A queue is a data structure that stores elements in a first-in, first-out (FIFO) order. A common way to implement a wait-free queue is to use a doubly-linked list with a head pointer and a tail pointer that point to the first and last elements respectively. To enqueue an element to the queue, a thread can use a FAA operation to atomically increment a counter that represents the index of the new element, and then use a LL/SC operation to atomically store the new element at the corresponding position in the list. To dequeue an element from the queue, a thread can use a FAA operation to atomically decrement a counter that represents the index of the first element, and then use a LL/SC operation to atomically load and remove the element at the corresponding position in the list.

5 Lock-free hash table

A hash table is a data structure that maps keys to values using a hash function and an array of buckets. A simple way to implement a lock-free hash table is to use an array of pointers to lock-free lists, where each list stores the key-value pairs that have the same hash code. To insert a key-value pair to the hash table, a thread can use a hash function to compute the index of the bucket, and then use a CAS operation to atomically insert the pair to the head of the list. To lookup a key-value pair from the hash table, a thread can use a hash function to compute the index of the bucket, and then traverse the list to find the matching pair.

6 Wait-free snapshot

A snapshot is a data structure that allows multiple threads to concurrently read and write a set of shared variables, and to obtain a consistent view of their values at any point in time. A common way to implement a wait-free snapshot is to use an array of records, where each record stores the value and version of a variable, and a global version counter. To write a variable to the snapshot, a thread can use a FAA operation to atomically increment the global version counter, and then use a CAS operation to atomically update the record of the variable with the new value and version. To read a variable from the snapshot, a thread can use a LL/SC operation to atomically load the record of the variable. To obtain a snapshot of all variables, a thread can use a loop to read all records, and then check if any record has been updated by another thread. If so, the thread can retry with the updated records.

7 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?