SEMAPHORES

SEMAPHORES

The first major advance in dealing with the problems of concurrent processes came in 1965 with Dijkstra's treatise. The fundamental principle is this: two or more processes can cooperate by means of simple signal, such that a process can be forced to stop at a specified place until it has received a specified signal. Any complex coordination requirement can be satisfied by the appropriate structure of signals. for signalling ,special variables called semaphores are used. To transmit a signal via semaphore s, a process executes the primitive signal (s). To receive a signal via semaphore s, a process executes the primitive wait (s); if the corresponding signal has not yet been transmitted, the process is suspended until the transmission takes place.

To achieve the desired effect, we can view the semaphore as a variable that has an integer value upon which three operations are defined:

A semaphore may be initialized to a non-negative value
The wait operation decrements the semaphore value. If the value becomes negative, then the process executing the wait is blocked
The signal operation increments the semaphore value. If the value is not positive, then a process blocked by wait operation is unblocked.

Other than these three operations, there is no way to inspect or manipulate semaphores (stalling pg 208).

Semaphores are operated on by a signal operation, which increments the semaphore value and the wait operation, which decreases it. the initial value of semaphore indicates the number of wait operations that can be performed on the semaphore. Thus:

V= I - W + S

where I is the initial value of the semaphore

W is the number of completed wait operations performed on the semaphore

S is the number of signal operations performed on it

V is the current value of the semaphore (which must be greater than or equal to zero).

As V is > 0 then I- W+ S > 0, which gives

I + S > W

W < I + S

Thus, the number of wait operations must be less than or equal to the initial value of the semaphore, plus the number of signal operations. A binary semaphore will have an initial value of 1 (I = 1), thus:

W< S+ 1

In mutual exclusion, waits always occur before signals, as waits happen at the start of a critical piece of code, with a signal at the end of it. The above equation states that no more than one wait may run to completion before a signal has been performed. Thus no more than one process may enter the critical section at a time as required (Buchanan pg 92-93).

THE PRODUCER-CONSUMER PROBLEM

Stallings looked at this problem as one or more producers generating some type of data and placing this in a buffer and there is a single consumer that is taking items out of the buffer one at a time. The system is to be constrained to prevent the overlap of buffer operations. that is only one agent (producer or consumer) may access the buffer at any one time.

It involves two concurrent processes, the producer and the consumer, the producer places data in a buffer- event E1 and the consumer reads data from the buffer- E2. Obviously, event E2 would have to wait for event E1 to occur. if E1 and E2 are simultaneous, the rules of mutual exclusion are violated.

Let s be a semaphore and s initially be zero;

Producer

Event E1

V(s)

Consumer

Event E2

P(s);

the consumer can only read from the buffer only when the producer has written to it.

References:

Ian Hyslop, Chris Imafidon (2002/2003), Systems Integration Handbook

Gary Nutt ,Operating System, A Modern Perspective, Second Edition

William Buchanan (2000), Distributed Systems and Networks