Semaphoren Patterns

Producer-Consumer Problem

Producer generieren daten die sie über einen Puffer an Consumer übergeben.

Mutual exclusion

Zu jedem Zeitpunkt darf nur ein Prozess auf den Puffer zugreifen.

Condition synchronization

Ein Consumer darf nur dann lesen wenn mindestens 1 Element im Buffer steht

Endloser Buffer-Speicher

append(v):
b[in] := v;
in := in + 1;take():
w := b[out];
out := out + 1;
return w;

init(S,1); init(N,0);

while(true){
produce(v);
wait(S);
append(v);
signal(S);
signal(N);
}

while(true){
wait(N);
wait(S);
w := take();
signal(S);
consume(w);
}

Über die Reihenfolge
Die Reihenfolge beim Consumer für die Zeilen 2, 3 ist relevant, wenn man sie vertauscht entsteht ein Deadlock weil der Consumer S.value auf 0 reduziert und der Producer nicht mehr durch kann.

Begrenzter Buffer-Speicher (Ring-Buffer)

Buffer hat K Elemente platz, (dafür nützen wir Semaphor E )

Schreiben: mindestens 1 Element gelesen

Lesen: mindestens 1 element geschrieben

append(v):
b[in] := v;
in := (in + 1) mod K;take():
w := b[out];
out := (out + 1) mod K;
return w;

init(S,1); init(N,0); init(E,K); <--

while(true){
produce(v);
wait(E); <--
wait(S);
append(v);
signal(S);
signal(N);
}

while(true){
wait(N);
wait(S);
w := take();
signal(S);
signal(E); <--
consume(w);
}

Priorität von Prozessen

Wir wollen P1-Prozesse gegenüber P2-Prozessen priorisieren.

Lösung 1

Synchronisierung von 2 Prozessen die mit mutual exclusion of ein ShM zugreifen, wobei P1 gegenüber P2 priorisiert wird.

init(A,1); init(B,1);

while(true){
wait(A);
ShMAccess;
signal(A);
}

while(true){
wait(B);
wait(A);
ShMAccess;
signal(A);
signal(B);
}

In der A queue kann maximal nur ein P2 Prozess stehen. - Dadurch kommen P1 Prozesse fast immer früher dran.

Lösung 2

Wartet bis alle P1 auf shared memory zugegriffen haben, und führt erst dann P2 aus.

init(A,1); init(B,1);
counter := 0;

while(true){
wait(B);
counter++;
if counter == 1 then wait(A);
signal(B);wait(B);
ShMAccess;
signal(B);wait(B);
counter--;
if counter == 0 then signal(A);
signal(B);
}

while(true){
wait(A);
ShMAccess;
signal(A);
}

B dient dazu in jedem der drei Segmente im Programm1 alle instructions atomar zu exekutieren.

Reader-Writer Problem

Analogie: Tafel in einer Schule

Während die Tafel jeweils von einem einzigen Schreiber beschrieben wird darf niemand zusehen aber danach dürfen beliebig viele Leser parellel die Tafel lesen.

Writer muss priorisiert werden und darf jederzeit die Leser unterbrechen.

Versuch 1

Der 1.reader muss sich mit dem writer synchronisieren, der Rest der reader nicht.

init(x,1); init(wsem,1);
rc := 0; //reader counter

while(true){
wait(x);
rc++;
if rc == 1 then wait(wsem);
signal(x);read;wait(x);
rc--;
if rc == 0 then signal(wsem);
signal(x);
}

Keine mutual exclusion um read, da mehrere reader gleichzeitig lesen dürfen.

while(true){
wait(wsem);
write;
signal(wsem);
}

Mutual exclusion um write, da jeweils nur 1 writer schreiben darf.

Dadurch ist mutual exclusion um write() und parallelität um read() hergestellt.

Problem:

So lange es noch weitere reader gibt, kommt der writer nicht mehr dran.

Reader sind priorisiert und können

Dadurch lesen die reader immer veralterte Daten - keine aktuellen.

Versuch 2

Wir spiegeln alles mit y , rsem :

Reader können jetzt ausgehungert werden - Es warten alle neuen reader bei der rsem queue sobald es einen writer bei Zeile $4$ gibt.

Dann wird gewartet bis die alten reader signal(wsem) und signal(rsem) ausgeführt haben und geschrieben werden kann.

init(x,1); init(y,1); init(wsem,1); init(rsem,1);
rc := 0; wc := 0;

while(true){
wait(rsem);
wait(x);
rc++;
if rc == 1 then wait(wsem);
signal(x);
signal(rsem);read;wait(x);
rc--;
if rc == 0 then signal(wsem);
signal(x);
}

while(true){
wait(y);
wc++;
if wc == 1 then wait(rsem);
signal(y);wait(wsem);
write;
signal(wsem);wait(y);
wc--;
if wc == 0 then signal(rsem);
signal(y);
}

Problem: Writer können reader nicht unterbrechen.

Sollte die blockierte rsem queue zu lange sein, muss der writer bei der $4$ . Zeile so lange warten, bis alle reader aus der FIFO queue fertig sind.

Wir wollen, dass die queue sich wo anders anhäuft damit wir sofort mit einem writer die reader unterbrechen können.

Lösung: Writer haben Priorität

Es kann jeweils nur ein einziger reader in die rsem queue wenn dieser nachkommt während geschrieben wird - die restlichen sind in der z queue.

init(x,1); init(y,1); init(z,1); init(wsem,1); init(rsem,1);
rc := 0; wc := 0;

while(true){
wait(z);
wait(rsem);
wait(x);
rc++;
if rc == 1 then wait(wsem);
signal(x);
signal(rsem);
signal(z);read;wait(x);
rc--;
if rc == 0 then signal(wsem);
signal(x);
}

while(true){
wait(y);
wc++;
if wc == 1 then wait(rsem);
signal(y);wait(wsem);
write;
signal(wsem);wait(y);
wc--;
if wc == 0 then signal(rsem);
signal(y);
}

Alternative Lösung: writer-Priorität ohne reader-starvation

Schreiber kommen früher dran - keine so starke Priorität wie davor.

Nicht die "klassische Lösung".

init(x,1); init(y,1); init(z,1); init(wsem,1); init(rsem,1);
rc := 0; wc := 0;

while(true){
wait(z);
wait(rsem);
wait(x);
rc++;
if rc == 1 then wait(wsem);
signal(x);
signal(rsem);
wait(z);read;wait(x);
rc--;
if rc == 0 then signal(wsem);
signal(x);
}

while(true){
wait(rsem);wait(wsem);
write;
signal(wsem);signal(rsem);
}

Dining Philosophers Problem

5 Philosophen die gemeinsam essen, jeder braucht 2 Gabeln.

Versuch

Ein Prozess pro Philosoph. Ein Semaphor pro Gabel.

Jeder Philosoph ist greedy und nimmt beide gabeln nacheinander. → Deadlock, kein Prozess kann die 3. Zeile ausführen wenn alle gleichzeitig die 2. Zeile ausführen.

for(i=0; i<=4; i++){
init(fork[i],1);
}

while(true){
think;
wait(fork[i]);
wait(fork[i+1 mod 5]);
eat;
signal(fork[i+1 mod 5]);
signal(fork[i]);
}

Mögliche Lösungen

Zusätzlicher Semaphor der nur zulässt dass an jedem Zeitpunkt nur 4 Gabeln genommen werden, dadurch bleibt immer eine Gabel frei.

Mindestens ein Prozess muss die Gabeln in umgekehrter Reihenfolge nehmen.

Gabeln immer gleichzeitig nehmen - alles oder nichts: Atomare Operation für mehrere Semaphore mit
mWait(S1...SN) blockiert wenn irgendeines ≤0 ist, verringert sonst alle gleichzeitig
mSignal(S1...SN) erhöht alle gleichzeitig um 1
(Bei mSignal ist es eigentlich egal ob sie alle gleichzeitig erhöht werden, es geht nur um die Lesbarkeit.)
Einsatz:
```
while(true){
think;
mWait(fork[i], fork[i+1 mod 5]);
eat;
mSignal(fork[i], fork[i+1 mod 5]);
}
```