Synchronizing Access to Shared Objects - Operating Systems: Principles and Practice - page 217

the (short) sequences of instructions that manipulate the lock's state but that
suspends threads that try to acquire the lock when it is busy.
The basic idea is simple. A SpinLock called spinlock protects the lock's
data structures. Once the spinlock is acquired a thread can inspect and update
the lock's state. If a thread nds that the lock isBusy, it removes itself from the
ready list, adds itself to the lock's waiting list, and then suspends its execution to
allow another thread to run. Later, when the lock is released, if any threads are
waiting, then one of them is moved o the lock's waiting list to the scheduler's
ready list.
Belt and suspenders. Why do we both acquire a spinlock and disable inter-
rupts in the case where we suspend or resume a thread?
The basic issue is that we want to prevent a context switch during a context
switch. Note that we must access two shared data structures|the lock and the
scheduler's ready list. If the current thread is suspended after removing itself
from the ready list but before adding itself to the lock's waiting list, then it will
never be resumed. Turning off interrupts before beginning this sequence ensures
that both operations occur before the thread is suspended.
Notice that turning off interrupts in this case does not ensure mutual exclu-
sion. Instead, the lock and the ready list each have their own (spin-) locks to
protect their own data structures.
Case study: Linux 2.6 kernel mutex lock
The pseudo-code above may seem a bit abstract, but real implementations
closely follow this approach. For example, in Linux 2.6 the file include/linux/mutex.h
denes a mutex's data structure as follows 5 :
structmutex{
/*1:unlocked,0:locked,negative:locked,possiblewaiters*/
atomic_t count;
spinlock_t wait_lock;
structlist_head wait_list;
};
This structure is similar to what we sketched in Figure 5.12. waitlock and
waitlist correspond to the waiting queue and spinlock's state; the count
field is similar to the value eld.
However, Linux provides an optimized path to acquire a free lock or release
a lock with no waiting threads.
In particular, a lock can be in one of three main states as defined by count .
If count is 1 the lock is unlocked. If count is 0, the lock is locked, but the
5 For simplicity, throughout this example we include excerpts of the code and omit code
for debugging code and for coordinating with signal handing, and we omit compiler/linker
directives.