Information Technology Reference
In-Depth Information
6.3.2
Lock-free and wait-free data structures
RCU allows reads to proceed without acquiring a lock or updating shared syn-
chronization state, but it still requires updates to acquire locks. If the thread
that holds the lock is interrupted, has a bug that causes it to stop making
progress, or becomes deadlocked, other threads can be delayed for a long|
perhaps unlimited|period of time.
It is possible to build data structures that completely avoid locking on both
reads and writes.
Lock free data structures ensure eventual progress:
if all
Denition: Lock free
threads are allowed to run for some finite number of steps, then at least one
of the threads will complete its operation.
Wait free data structures ensure
Denition: Wait free
both eventual progress and fairness: if any thread is allowed to run for some
finite number of steps, that thread will complete its operation regardless of the
execution speed of the other threads.
Historically the design of ecient lock-free or wait-free data structures has
been complex and application-specific. Nonetheless, lock free or wait free al-
gorithms of varying levels of eciency exist for wide range of data structures
including FIFO queues, double-ended queues, LIFO stacks, sets, and hash ta-
bles.
Designing ecient wait-free data structures continue to be the domain of
experts, and a discussion of the techniques they use is outside the scope of
this topic. However, some reasonably-ecient and general approaches to im-
plementing lock-free data structures are known and in suently wide use to
warrent further comment here.
Lock-free data structures. Lock free data structures can be implemented
by having each operation detect concurrent, conflicting operations. When such
updates are detected, the operation waits a finite amount of time for them to
finish. If the conflicting operations do not finish, the operation either aborts
the conicting ones (rolling the object's state back to what it was before that
conflicting operations began) or it assists them (finishing the updates needed to
complete that operation).
Example: Transactions and software transactional memory (STM)
A transactional database with optimistic concurrency control, is an example of
a very flexible, lock-free data structure capable of running programs supplied by
different users accessing arbitrary data in arbitrary ways without risking dead-
lock. Recall that optimistic concurrency control allows transactions to proceed
without locking the data they access and aborts the transaction if at commit-
time any of the accessed data have changed.
To see that such databases are lock free, consider two conflicting transactions
executing at the same time. The first one to commit will succeed, and the second
one must abort and retry.
