Information Technology Reference
In-Depth Information
at the start of the sequence and Lock::release() at the end. To enable this
abstraction, each lock has a state (FREEorBUSY) and a queue of zero or
more threads waiting for the lock to becomeFREE.
The discussion of Too Much Milk showed that it is both complex and costly
to implement locks with just memory reads and writes, so modern implementa-
tions use more powerful hardware primitives that allow us to atomically read,
modify, and write pieces of the lock's state. We will look at locks based on
two primitives: disabling interrupts, which can make a sequence of instructions
atomic with respect to a single processor, and atomic read-modify-write instruc-
tions, which allow a single instruction to atomically read and update a word of
memory with respect to every processor on a multiprocessor.
Implementing uniprocessor locks by disabling interrupts
On a uniprocessor machine, any sequence of instructions by one thread will
appear atomic to other threads if there is no context switch in the middle of
the sequence. So, on a uniprocessor machine a thread can make a sequence
of actions atomic by disabling interrupts (and refraining from calling thread
library functions that can trigger a context switch) during the sequence.
This observation suggests a trivial|but seriously limited|approach to im-
plementing locks on a uniprocessor machine:
Lock::acquire(){disableInterrupts();}
Lock::release(){enableInterrupts();}
This implementation does provide the mutual exclusion property we need
from locks, and some uniprocessor kernels use this simple approach. However,
it does not suce as a general implementation for locks. If the code sequence
the lock protects runs for a long time, interrupts will be disabled for a long time;
this will prevent other threads from running for a long time, and it will make
the system unresponsive to handling user inputs or other real-time tasks. Fur-
thermore, although this approach can work within the kernel where all code is
(presumably) carefully crafted and trusted to release the lock quickly, we cannot
let untrusted user-level code run with interrupts turned off, since a malcious or
bugger program could then monopolize a processor.
Implementing uniprocessor queuing locks
A more general solution is to briey disable interrupts to protect the lock's
data structures, but to reenable them once a thread has acquired the lock or
determined that the lock is busy. In the latter case, there is no point in running
the thread until the lock is free, so we suspend the thread by moving its thread
control block (TCB) from the ready list to a queue of threads waiting for the
lock.
 
Search WWH ::




Custom Search