In: Computer Science
It should be possible to implement general semaphores using binary semaphores. We can use the operations semWaitB and semSignalB and two binary semaphores, delay and mutex. Consider the following:
void semWait(semaphore s)
{
semWaitB(mutex);
s--;
if (s < 0) {
semSignalB(mutex);
semWaitB(delay);
}
else SemsignalB(mutex);
}
void semSignal(semaphore s);
{
semWaitB(mutex);
s++;
if (s <= 0)
semSignalB(delay);
semSignalB(mutex);
}
Initially, s is set to the desired semaphore value. Each semWait operation decrements s, and each semSignal operation increments s. The binary semaphore mutex, which is initialized to 1, assures that there is mutual exclusion for the updating of s. The binary semaphore delay, which is initialized to 0, is used to block processes.
There is a flaw in the preceding program. Demonstrate the flaw and propose a change that will fix it.
Suppose two processes each call semWait(s) when s is initially 0, and after the first has just done semSignalB(mutex) but not done semWaitB(delay), the second call to semWait(s) proceeds to the same point. Because s = -2 and mutex is unlocked, if two other processes then successively execute their calls to semSignal(s) at that moment, they will each do semSignalB(delay), but the effect of the second semSignalB is not defined.
The solution is to move the else line, which appears just before the end line in semWait to just before the end line in semSignal. Thus, the last semSignalB(mutex) in semWait becomes unconditional and the semSignalB(mutex) in semSignal becomes conditional.
Thus, the last semSignalB(mutex) in semWait becomes unconditional and the semSignalB(mutex) in semSignal becomes conditional.