Information Technology Reference
In-Depth Information
classLock{
private:
intvalue=FREE;
Queuewaiting;
public:
voidLock::Acquire(){
disableInterrupts();
if(value==BUSY){
waiting.add(currentthread'sTCB);//Thisthreadnolongeronreadylist
suspend(); //Likeyield(),butcurrentthread'sTCB
//isonwaitinglistratherthanreadylist
}
else{
value=BUSY;
}
enableInterrupts();
}
voidLock::Release(){
disableInterrupts();
if(waiting.notEmpty()){
moveoneTCBfromwaitingtoready;
}
else{
value=FREE;
}
enableInterrupts();
}
}
Figure5.11: Pseudocode for uniprocessor lock implementation via disabling
interrupts.
This approach is illustrated in the Lock implementation shown in Figure 5.11.
In this pseudo-code, if a lock isBusywhen a thread tries to acquire it, the thread
moves its thread control block (TCB) o of the ready list and onto the lock's
waiting list; the thread then suspends itself using a call similar to
yield()
;
since the thread's TCB is o the ready list, this
suspend()
call will not return
until some calls
Lock::Release()
and moves the suspended thread's TCB to
the ready list.
An optimization. Notice that if a thread is waiting for the lock, a call to
Lock::Release()
does not set
value
toFree. Instead, it leaves
value
as
Busy. Then, the thread whose TCB is moved to the ready list is guaranteed
to be the one that acquires the lock and returns next. This arrangement allows
an implementation to ensure freedom from starvation: assuming that TCBs
are removed from the
waiting
list in FIFO order, then a thread waiting for a
lock is guaranteed to succeed in acquiring the lock within a bounded number of
Release()
calls on that lock.
This feature is an optimization of this specific implementation of the lock
primitive. Users of locks should not assume anything about the order that
waiting threads will acquire a lock.
