Recovering Spin Locks from Process Failure
In building main-memory databases where many processes access shared data
structures, it is necessary to ensure that no process's untimely termination
causes system resources to become ``permanantly'' unavailable. Synchronization
primitives must be recoverable. A simple way to achieve recoverability
is to use system semaphores. However, they tend to be very slow---roughly
two-order-of-magnitude slower than spin locks based on an atomic instruction
like test-and-set. However, if a process dies holding a semaphore,
the semaphore (and its guarded resource) may be unavailable. Hence,
simple spin locks are not recoverable.
Our original work in this area modified simple spin locks to produce a
semaphore that combined high performance with recoverability.
It is described in our
our SPDP'95 paper. This algorithm is used in
Dali.
While this algorithm works well in low-contention cases, it shares the
poor scalability characteristics of simple spin locks under high
contention. Simple spin locks cause a great deal of bus contention
on lock control variables and produce a large number of invalidates under
high contention. To improve this, we modified a high-performance, scalable
spin lock, the MCS lock to make it recoverable. This algorithm is
described in our SPDP'96 paper.
Both pieces of work modify the original protocols to write additional information to shared memory and use a cleanup process which returns locks to a
usable state in case of process deaths.
Neither of our algorithms require kernel or hardware support other than
the swap instruction (our initial work only requires
test-and-set actually).