Semaphores
The main disadvantage of the semaphore discussed in the previous section is that they all
require busy waiting. While a process is in its critical section, any other process that tries
to enter its critical section must loop continuously in the entry code. This continual
looping is clearly a problem in a real multiprogramming system, where a single CPU is
shared among many processes. Busy waiting wastes CPU cycles that some other process
may be able to use productively. This type of semaphore is also called a spinlock
(because the process spins while waiting for the lock)
. Spinlocks are useful in
multiprocessor systems. The advantage of a spinlock is that no context switch is required
when a process must wait on a lock, and a context switch may take considerable time.
This, when locks are expected to be held for short times, spinlocks are useful.
To overcome the need for busy waiting, we can modify the definition of semaphore
and the wait and signal operations on it. When a process executes the wait operation and
finds that the semaphore value is not positive, it must wait. However, rather than busy
waiting, the process can block itself. The block operation places a process into a waiting
queue associated with the semaphore, and the state of the process is switched to the
waiting state. Then, control is transferred to the CPU scheduler, which selects another
process to execute.
A process that is blocked, waiting on a semaphore S, should be restarted when some
other process executes a signal operation. The process is restarted by a wakeup operation,
which changes the process from the waiting state to the ready state. The process is then
placed in the ready queue. (The CPU may or may not be switched from the running
process to the newly ready process, depending on the CPU scheduling algorithm.)
Such an implementation of a semaphore is as follows:
Code:
typedef struct {
int value;
struct process *L;
} semaphore;
111
Each semaphore has an integer value and a list of processes. When a process must
wait on a semaphore; it is added to the list of processes. A signal operation removes one
process from the list of the waiting processes and awakens that process. The wait
operation can be defined as:
Code:
void wait(semaphore S) {
S.value--;
if(S.value < 0) {
add this process to S.L;
block();
}
}
The signal semaphore operation can be defined as
Code:
void signal wait(semaphore S) {
S.value++;
if(S.value <= 0) {
remove a process P from S.L;
wakeup(P);
}
}
The block operation suspends the process that invokes it. The wakeup(P) operation
resumes the execution of a blocked process P. These two operations are provided by the
operating system as basic system calls. The negative value of S.value indicates the
number of processes waiting for the semaphore. A pointer in the PCB needed to maintain
a queue of processes waiting for a semaphore. As mentioned before, the busy-waiting
version is better when critical sections are small and queue-waiting version is better for
long critical sections (when waiting is for longer periods of time).

Sponsored Links