Lock-free programming is a technique that allows concurrent updates of shared data structures without using explicit locks. This method ensures that no threads block for arbitrarily long times, and it thereby boosts performance.
Lock-free programming has the following advantages:
- Can be used in places where locks must be avoided, such as interrupt handlers
- Efficiency benefits compared to lock-based algorithms for some workloads, including potential scalability benefits on multiprocessor machines
- Avoidance of priority inversion in real-time systems
Lock-free programming requires the use of special atomic processor instructions, such as CAS (compare and swap), LL/SC (load linked/store conditional), or the C Standard
atomic_compare_exchange generic functions.
Applications for lock-free programming include
- Read-copy-update (RCU) in Linux 2.5 kernel
- Lock-free programming on AMD multicore systems
The ABA problem occurs during synchronization: a memory location is read twice and has the same value for both reads. However, another thread has modified the value, performed other work, then modified the value back between the two reads, thereby tricking the first thread into thinking that the value never changed.
Noncompliant Code Example
This noncompliant code example attempts to zero the maximum element of an array. The example is assumed to run in a multithreaded environment, where all variables are accessed by other threads.
The compare-and-swap operation sets
array[index] to 0 if and only if it is currently set to
value. However, this code does not necessarily zero out the maximum value of the array because
indexmay have changed.
valuemay have changed (that is, the value of the
valuemay no longer be the maximum value in the array.
Compliant Solution (Mutex)
This compliant solution uses a mutex to prevent the data from being modified during the operation. Although this code is thread-safe, it is no longer lock-free.
Noncompliant Code Example (GNU Glib)
This code implements a queue data structure using lock-free programming. It is implemented using glib. The function
CAS() internally uses
Assume there are two threads (
T2) operating simultaneously on the queue. The queue looks like this:
head -> A -> B -> C -> tail
The following sequence of operations occurs:
Removes node A
Removes node B
Enqueues node A back into the queue
Removes node C
Enqueues a new node D
Thread 1 starts execution
According to the sequence of events in this table,
head will now point to memory that was freed. Also, if reclaimed memory is returned to the operating system (for example, using
munmap()), access to such memory locations can result in fatal access violation errors. The ABA problem occurred because of the internal reuse of nodes that have been popped off the list or the reclamation of memory occupied by removed nodes.
Compliant Solution (GNU Glib, Hazard Pointers)
According to [Michael 2004], the core idea is to associate a number (typically one or two) of single-writer, multi-reader shared pointers, called hazard pointers, with each thread that intends to access lock-free dynamic objects. A hazard pointer either has a null value or points to a node that may be accessed later by that thread without further validation that the reference to the node is still valid. Each hazard pointer may be written only by its owner thread but may be read by other threads.
In this solution, communication with the associated algorithms is accomplished only through hazard pointers and a procedure
RetireNode() that is called by threads to pass the addresses of retired nodes.
The scan consists of two stages. The first stage involves scanning the hazard pointer list for non-null values. Whenever a non-null value is encountered, it is inserted in a local list,
plist, which can be implemented as a hash table. The second stage involves checking each node in
rlist against the pointers in
plist. If the lookup yields no match, the node is identified to be ready for arbitrary reuse. Otherwise, it is retained in
rlist until the next scan by the current thread. Insertion and lookup in
plist take constant expected time. The task of the memory reclamation method is to determine when a retired node is safely eligible for reuse while allowing memory reclamation.
In the implementation, the pointer being removed is stored in the hazard pointer, preventing other threads from reusing it and thereby avoiding the ABA problem.
Compliant Solution (GNU Glib, Mutex)
In this compliant solution,
mtx_lock() is used to lock the queue. When thread 1 locks on the queue to perform any operation, thread 2 cannot perform any operation on the queue, which prevents the ABA problem.
The likelihood of having a race condition is low. Once the race condition occurs, the reading memory that has already been freed can lead to abnormal program termination or unintended information disclosure.
|Polyspace Bug Finder|
Multiple tasks perform unprotected non-atomic operations on shared variables
|[Apiki 2006]||"Lock-Free Programming on AMD Multi-Core System"|
|[Asgher 2000]||"Practical Lock-Free Buffers"|
|[Michael 2004]||"Hazard Pointers"|