Tuesday, 14 May 2013

Semaphores


In 1965, Dijkstra proposed a new and very significant technique for mutual exclusion among an arbitrary number of processes by using the value of simple shared integer variable. A semaphore is a shared variable with non negative values which can only be subjected to the following operations:
Initialization, specified as part of its declaration, and
Indivisible atomic operations wait and signal.

The wait and signal operations were originally termed P (for wait; from the Dutch ‘proberen’, to test) and V (for signal, from ‘verhogen’, to increment). Indivisibility of the wait and signal operations implies that only one wait or signal operation can be in progress on a semaphore at any time and once started, the execution of the wait or signal operation must be completed without interruption. Operations wait and signal can be defines as follow:

The wait operation on semaphore ‘S’, written wait(S), operates as follows:
            If S>0 then
                        S=S-1;
            Else
                        Block the process executing wait operation, that is wait on S.
            Endif

The signal operation on semaphore ‘S’, written as signal(S), operates as follows:
            If there exist process(es) blocked on S then
                        Wake one blocked process;
            Else
                        S=S+1;
            Endif;

Binary semaphores are used to implement mutual exclusion. Binary semaphore can assume only the value 0 or 1, which can be used to indicate the availability or non-availability of the protected resource. The wait and signal operations are used to ‘bracket’ (ie. enclose) the critical region of processes, as follow:
            Wait(S)
                        Critical Section
            Signal(S)

The entry to the critical sections of active processes is controlled by the wait operations and the exit from the critical sections is signaled by the signal operations. Trying to execute the wait operation may allow a process access to the resource (if S>0) or may cause the process to be blocked (if S=0). The signal operation signals the fact that some process has released a resource, which can now be used by a process waiting for it.

Question:
1.     At a particular moment the value of a counting semaphore is 10. It will become 7 after,
a.     3 V operation
b.     3 P operation
c.      5 V operation and 2 P operation
d.     13 P operation and 10 P operation
Answer: b, d

Note: if a P operation is happen then the value of semaphore decrement by 1. If a V operation is occur then the value of the semaphore increment by 1. Semaphores are used to mutual exclusion as well as synchronization.

      NEXT: Deadlock 
      Index : Operating System




No comments:

Post a Comment