3.2.2.1 Concept of semaphores

A semaphore is a structured data type consisting of

variables:
$\bullet$ $\mathbb{S}$- value (integer)
$\bullet$ Queue

and operations ($\bullet$ init):
$\bullet$ $\mathbb{P}$roberen $\equiv$ WAIT
$\bullet$ $\mathbb{V}$erhogen $\equiv$ SIGNAL

Operations $\mathbb{P}$ and $\mathbb{V}$ are atomic.

The operations are linked with the variables as follows :

$\mathbb{P}$(s):		$\mathbb{S}$-value $=$ 0		$\longrightarrow$		process in queue [train on the line]
		$\mathbb{S}$-value $>$ 0		$\longrightarrow$		( $\mathbb{S}$-value)$:= 0$ and resources are available
						[empty line, enter it and set signal on ''red'']
$\mathbb{V}$(s)		queue is empty		$\longrightarrow$		( $\mathbb{S}$-value)$:= 1$ [set signal on ''green'']
		queue not empty		$\longrightarrow$		activate a (waiting) process
						[let one stopped train enter the line, signal remains on ''red'']

The status query $\mathbb{P}$(s) will be done only once per process, therefore the queue is necessary.

Examples for the use of semaphores

• exclusive access (i.e. $N = N+1$, $N = N-1$)
  
  $\mathbb{S}$ semaphore $\longleftarrow$ INIT( $\mathbb{S}$) is required, otherwise deadlock appears.
  $\mathbb{R}$ Resources
  

  Figure 3.7: Exclusive access with help of semaphores

  
  The result is unique ( $N := (N+1) - 1$) !!
  
  Attention : The semaphore mechanism offers only the opportunity to achive a uniqe result. If processes A and B perform non-commutative operations on $N$ then the number of possible responses is only reduced from 4 to 2. This happens for A:  $N:=2\cdot N$ and B: $N:=3^N$.
• Synchronization of characteristics (e.g., producer - consumer)
  
  2 semaphores

  A $\longrightarrow$ represents a full buffer; INIT(A) with 0
  B $\longrightarrow$ represents an empty buffer; INIT(A) with 1

  
  

  Figure 3.8: Synchronization of characteristics using semaphores

  
  This synchronization can be found in the $\omega$-Gauß-Seidel iteration (forward) if a 5-point-stencil was used for the discretization of the Laplace problem. $$\widehat{c} \makebox[0pt]{}_{i,j} \;:=\; c_{i,j} + \left(... ...-1} + 4 c_{i,j} - c_{i+1,j} - c_{i,j+1} \right] }\right) / 4$$
  Here, $\widehat{c} \makebox[0pt]{}_{i,j}$ is the consumer and all remaining variables are producers (even  $\widehat{c} \makebox[0pt]{}_{i-1,j}$ and  $\widehat{c} \makebox[0pt]{}_{i,j-1}$ !!). See also Sec. 3.1.

Dijkstra`s solution of ''Dinner for Five''

In the universe we assume declared

1. the semaphore mutex initially $1$
2. the INTEGER ARRAY C[0:4] initially all elements 0
3. the semaphore INTEGER ARRAY prisem[0:4] initially all elements 0
4. there exists a procedure

    procedure test (integer value k);
      if C[(k-1) mod 5] <> 2   and   C[k] == 1   
                               and   C[(k+1) mod 5] <> 2
         begin  C[k] := 2,  V(prisem[k])  end
    end
   

   Remark :
   $C[k] \;=\; \begin{cases}0 & \qquad\text{vacant seat} \\ 1 & \qquad\text{occup... ...sopher} \\ 2 & \qquad\text{occupied seat, 2 forks in hands} \\ \end{cases}$
   
   $prisem[k] == 1 \;\;\;$ philosopher $k$ may start eating.
   
   For philosopher $k$ the above procedure consists in the queries
   • Is it true that the left neighbor has not two forks in his hands , i.e, that there is no fork at all in his hands ? ($=$ he does not eat)
   • Do I sit on the table and do I have hunger ?
   • Is it true that the right neighbor has not two forks in his hands ?
   If the answer to all queries is ''yes'', then philosopher $k$ takes the 2 forks and starts to eat.
5. In this the live of philosophers can be coded (philosopher $w$):

    1:     cycle begin  think
    2:                  P(mutex)
    3:                    C[w] := 1;  test(w)
    4:                  V(mutex)
    5:                  P(prisem[w]);  eat
    6:                  P(mutex)
    7:                    C[w] := 0;  test[(w+1) mod 5];  
                                      test[(w-1) mod 5]
    8:                  V(mutex)
    9:           end
   

   Explanation:

   3:

   Sit down and take 2 forks if possibly.

   5:

   Do I have permission to eat ? If answer is ''yes'', then start eating. Otherwise, wait until the permission will be given (i.e., semaphore prisem[w] is deleted)

   7:

   After the meal is finished, leave the seat and your neighbors will check whether both forks are vacant.

Further explanations can be found in the journal c't 12/90 at page 246.