Operating System Design/Processes/Semaphores

Semaphores

A semaphore, in its most basic form, is a protected integer variable that can facilitate and restrict access to shared resources in a multi-processing environment. The two most common kinds of semaphores are counting semaphores and binary semaphores. Counting semaphores represent multiple resources, while binary semaphores, as the name implies, represents two possible states (generally 0 or 1; locked or unlocked). Semaphores were invented by the late Edsger Dijkstra.

Semaphores can be looked at as a representation of a limited number of resources, like seating capacity at a restaurant. If a restaurant has a capacity of 50 people and nobody is there, the semaphore would be initialized to 50. As each person arrives at the restaurant, they cause the seating capacity to decrease, so the semaphore in turn is decremented. When the maximum capacity is reached, the semaphore will be at zero, and nobody else will be able to enter the restaurant. Instead the hopeful restaurant goers must wait until someone is done with the resource, or in this analogy, done eating. When a patron leaves, the semaphore is incremented and the resource becomes available again.

A semaphore can only be accessed using the following operations: wait() and signal(). wait() is called when a process wants access to a resource. This would be equivalent to the arriving customer trying to get an open table. If there is an open table, or the semaphore is greater than zero, then he can take that resource and sit at the table. If there is no open table and the semaphore is zero, that process must wait until it becomes available. signal() is called when a process is done using a resource, or when the patron is finished with his meal. The following is an implementation of this counting semaphore (where the value can be greater than 1):

wait(Semaphore s){
    while (s==0);    /* wait until s>0 */
    s=s-1;
}

signal(Semaphore s){
    s=s+1;
}

Init(Semaphore s , Int v){
    s=v;
}

Historically, wait() was called P (for Dutch “Proberen” meaning to try) and signal() was called V (for Dutch “Verhogen” meaning to increment). The standard Java library instead uses the name "acquire" for P and "release" for V.

No other process can access the semaphore when P or V are executing. This is implemented with atomic hardware and code. An atomic operation is indivisible, that is, it can be considered to execute as a unit.

If there is only one count of a resource, a binary semaphore is used which can only have the values of 0 or 1. They are often used as mutex locks. Here is an implementation of mutual-exclusion using binary semaphores:

do
{
    wait(s);
    // critical section
    signal(s);
    // remainder section
} while(1);

In this implementation, a process wanting to enter its critical section it has to acquire the binary semaphore which will then give it mutual exclusion until it signals that it is done.

For example, we have semaphore s, and two processes, P1 and P2 that want to enter their critical sections at the same time. P1 first calls wait(s). The value of s is decremented to 0 and P1 enters its critical section. While P1 is in its critical section, P2 calls wait(s), but because the value of s is zero, it must wait until P1 finishes its critical section and executes signal(s). When P1 calls signal, the value of s is incremented to 1, and P2 can then proceed to execute in its critical section (after decrementing the semaphore again). Mutual exclusion is achieved because only one process can be in its critical section at any time.

Disadvantage

As shown in the examples above, processes waiting on a semaphore must constantly check to see if the semaphore is not zero. This continual looping is clearly a problem in a real multiprogramming system (where often a single CPU is shared among multiple processes). This is called busy waiting and it wastes CPU cycles. When a semaphore does this, it is called a spinlock.

To avoid busy waiting, a semaphore may use an associated queue of processes that are waiting on the semaphore, allowing the semaphore to block the process and then wake it when the semaphore is incremented. The operating system may provide the block() system call, which suspends the process that calls it, and the wakeup(P <Process>) system call which resumes the execution of blocked process P. If a process calls wait() on a semaphore with a value of zero, the process is added to the semaphore’s queue and then blocked. The state of the process is switched to the waiting state, and control is transferred to the CPU scheduler, which selects another process to execute. When another process increments the semaphore by calling signal() and there are tasks on the queue, one is taken off of it and resumed.

In a slightly modified implementation, it would be possible for a semaphore's value to be less than zero. When a process executes wait(), the semaphore count is automatically decremented. The magnitude of the negative value would determine how many processes were waiting on the semaphore:

wait(Semaphore s){
    s=s-1;
    if (s<0) {
        // add process to queue
        block();
    }
}

signal(Semaphore s){
    s=s+1;
    if (s<=0) {
        // remove process p from queue
        wakeup(p);
    }
}

Init(Semaphore s , Int v){
    s=v;
}