3.2.2 Semaphores

A general problem with the access to shared resources consists in the prevention of deadlocks.

Deadlock :
Several processes are waiting for an event which can be released only by one of these waiting processes (blocking).

Ex.: Dinner for five [Dijkstra, 1971]

Figure 3.5: Dinner for five

''The life of the philosophers consists of alternating activities thinking and eating. Each philosopher has its seat at the table.
Their only problem - apart from those philosophical nature - consists of the fact that the served meal is a very difficult type of spaghetti, for which consumption one needs two forks. Next to each plate 2 forks are situated, so that basically no difficulties should occur. It has however as a consequence that 2 neighbors cannot eat at the same time.`` [Rec94] (re-translation from German)

The 5 forks are representate the lack of resources in a large system.

Solution (Instruction) 1:

1. If you are hungry then occupy a vacant seat.
2. Wait until the left fork is available and take it.
3. Wait until the right fork is available and take it.
4. Eat your spaghetti.
5. Release both forks after the meal !

$\Longrightarrow$ Deadlock :
All philosophers will die by hunger with a fork in their left hand.

Solution 2:

1. If you are hungry then occupy a vacant seat.
2. Wait until the left and right fork are available and take it.
3. Eat your spaghetti.
4. Release both forks after the meal !

$\Longrightarrow$ ''Deadlock for all'' is impossible, but a single philosopher is threatened by hunger death, e.g., this happens for philosopher no.1, if no.0 and no.2 eat alternatively but with a small overlapp in time.


Dijkstra's suggestion : Definition of semaphores (a semaphore is a signal of the Dutch railway company).

Semaphore :
A signal, which is operated by individual processes and not by a central instance (Fig. 3.6).

The process [train] waits if the signal is on ''WAIT'' [red]. Otherwise, the access [entry] on the critical range [railroad line] is released and that process [train] places the signal on ''WAIT'' [red] for all other processes [trains].

Figure 3.6: Release of a semaphore

• Shared Memory $\longrightarrow$ semaphores
• Distributed Memory $\longrightarrow$ message passing model $\longrightarrow$ communication