Process Synchronization--Part 6 (Semaphores-1)

In this post, we will look at a software solution to the n-process synchronization problem, semaphores.

A semaphore is an integer variable which can be accessed only through 2 atomic operations:-

1. wait()
2. signal()

So, if S is a semaphore variable, the only operations and the only 2 ways to access S is:-

1. wait(S)
2. signal(S)

The wait and signal operations on a semaphore variable S can be defined as follows:-

We should note that these operations will be called by processes. Also, S is a shared variable. So, all the n processes may execute statements like wait(S) and signal(S). 

Let us assume that S has been initialized with 1. Now, if a process invokes wait(S), S will become 0. Now, if another process invokes wait(S), it will start waiting in the infinite loop. When some process invokes signal(S), S will become 1 again, only then can an interested process which was waiting in the loop, proceed with its code segment after wait(S). 

**wait(S) and signal(S) need not be executed by the same process. For example, if Process P0 executes wait(S) when S is initially 1, S becomes 0. Now, if process P1 executes wait(S), it starts waiting in the infinite loop. If P0 now executes signal(S), S becomes 1 and P1 can now make S=0 and proceed with its code. But this signal(S) could have been done by some process other than P0 as well. This is a very important point which we must remember. So, from the above definition, we find that S can have a minimum value of 0 and its maximum value depends on how many processes perform signal(S).

Let us say we want to solve the n-process critical section problem using semaphores. So, as we have read earlier, any solution to the critical section problem must ensure that only 1 process is allowed to execute its critical section at any point of time.

To solve the critical section problem with n processes, code structure of any process Pi looks like this:-

We should note that for a software solution to work properly, the code must be correct, this should be kept in mind. The above code works as follows:-

• Initially S should be 1. This, in fact, is known as a Binary Semaphore as it can hold only 2 values, 0 and 1.
• Each process invokes wait(S) before accessing the critical section.
• Each process invokes signal(S) after accessing the critical section.
• A process gets the chance to enter its critical section only if S = 1, which means no other process is inside its critical section, as otherwise S would have been 0.
• When a process exits its critical section, it invokes signal(S) to make S = 1 so that some other process can enter its critical section (which process gets a chance is a matter of Scheduling and we will come back to it after some time).
• Mutual Exclusion holds as a process can enter only if S = 1. Once it enters, S becomes 0 and now no other process can enter as S is not equal to 1.
• An inherent assumption made in the above claim is that S = S + 1 and S = S - 1 are atomic statements. Also, there is no interruption when while(S<=0); statement is false and S = S - 1 is executed.
• Progress holds in above code. It is obvious.
• Bounded waiting may not hold. When a process P0 is inside its critical section, it has performed wait(S) and set S to 0. Until P0 sets S to 1 by signal(S) [acc, to above code] all the processes invoking wait(S) in the meantime will be blocked on this semaphore the details of which will have to be stored somehow. Bounded Waiting will depend on the Scheduling policy which we will get back to after some time.

So far, we have seen the concept of Semaphores, the concept of wait() and signal() operations defined on semaphore variables and a solution to the n-process critical section problem using semaphores. Now, we will see the actual implementation of Semaphores.

Implementation of Semaphores

We have stated that semaphores are integer variables with 2 operations defined on them. We have also seen that information about the processes blocked on a semaphore has to be stored along with the integer value so that they can resume operation once a process invokes signal(S).

So, we can define a semaphore has a structure (in C) or class (in Java) which has an integer data component and a pointer variable to construct a Linked List which will hold the processes which are blocked (after having invoked wait(S) on this particular semaphore. A possible implementation has been shown below and I have taken this diagram from the Operating System Course Notes of Dr. John T.Bell, Dept. of Computer Science, University of Illinois, Chicago.

Each semaphore has an integer value and also a pointer to construct a linked list which will hold processes which have invoked wait(S) when some process is already inside its critical section by having invoked wait(S) and setting it to 0.

In this implementation, the minimum value of S is not bounded. As and when new processes block, S value gets more and more negative. The last blocked process gets over when S increases from -1 to 0. At this point, only 1 process is inside its critical section using this semaphore and no process is blocked on this semaphore. Next time, when the current working process invokes signal(S), S comes back to 1 and everything is fine!

Phew! It was a bit of a roller-coaster ride I am sure :P 

But there is a problem. The line *remove a process P from S->list does not state in which order the processes are to be removed from the blocked list of a semaphore. If LIFO policy is followed, definitely starvation will occur. In this case, Bounded Waiting may not hold as well.

Deadlock Problem with Semaphores

R and S are semaphores. If process A executes wait(S), pre-empts, then process B executes wait(R), now both processes are in deadlock as neither A nor B can proceed as both R and S semaphores are already 'occupied'. This is an important problem which can occur with semaphore code.

We have seen binary semaphores and their applications. In the next post, we will see 2 other applications of semaphores.