Operating System Design/Processes/Semaphores

From Wikibooks, the open-content textbooks collection

[edit] Semaphores

Semaphores are the classic method for restricting access to shared resources (e.g. storage) in a multi-processing environment. They were invented by Dijkstra.

Many people prefer to use monitors instead of semaphores, because semaphores make it too easy to accidentally write code that deadlocks.

A semaphore is a protected variable(or ADT) which can only be accessed using the following operations:

        acquire(Semaphore s){
            while (s==0);    /* wait until s>0 */
            s=s-1;
        }
 
        release(Semaphore s){
            s=s+1;
        }
 
        Init(Semaphore s; Int v){
            s=v;
        }

Historically, "acquire" was originally called P (for Dutch “Proberen” to test) and is often called "wait"; the standard Java library uses "acquire". The function "release" was originally called V (for Dutch “Verhogen” to increment) and is often called "signal"; the standard Java library uses "release".

The value of a semaphore is the number of units of the resources which are free. If there is only one resource a “binary semaphore” with values 0 or 1 is used.

The "acquire" operation busy-waits or sleeps until a resource is available whereupon it immediately claims one. "release" is the inverse. It simply makes a resource available again after the process has finished using it. Init is only used once, to initialize the semaphore before any requests are made.

No other process can access the semaphore when P or V are executing.

To avoid busy waiting, a semaphore may have an associated queue of processes(FIFO) . If a process attempts an acquire on a semaphore which is zero, the process is added to the semaphore’s queue. When another process increments the semaphore by doing a release and there are tasks on the queue, one is taken off and resumed.

We can implement mutual-exclusion using semaphores:

 do
{
 
 acquire (s);
 critical section;
 release (s);
 
}while(1);

Let us take semaphore value to 1;

If process P1 wants to enter its critical section it has to acquire the semaphore. The value of s is decremented to 0. It releases the semaphore after executing its critical section. The value of s is incremented to 1.

Other process P2 wants to enter its critical section while P1 is in its critical section, it uses the shared semaphore value 0 and performs the acquire operation first. P2 continues to loop in the while until P1 executes release(s);

So, only one process will be executing at a time.

[edit] Disadvantage

The main disadvantage here is that processes require busy-waiting (looping in while). This continual looping is clearly a problem in a real multiprogramming system (where a single CPU is shared among multiple processes). Busy waiting wastes CPU cycles that some other may use them. This type of semaphore is called spinlock.

[edit] Implementation

To overcome the need for busy waiting, we can modify the definition of wait and signal semaphore operations.When a process executes the wait operation and finds that the semaphore value is not >0 , it is entered into waiting queue associated with the semaphore and the state of the process is switched to the waiting state. Then the control is transferred to the CPU scheduler, which selects another process to execute.

When another process executes a signal operation, any process from the waiting queue has to be restarted by a wakeup operation. The wakeup operation changes the process from the waiting state to the ready state. The process is then placed in the ready queue.

The operation system provides block() and wakeup(P) system calls. The block() operation suspends the process that invokes it. The wakeup(P <Process>) operation resumes the execution of blocked process P.

Seamaphores in wikipedia^[1]

[edit] References