Motivation

Competition Prozesse stehen im Wettkampf um gemeinsame Ressourcen

Shared Resources Daten in shared memory, Kontrolle, Peripherals

Ohne geregelte Ressourcenvergabe entstehen:

Deadlock

Lifelock

Starvation

Race Condition

Bsp Race Condition

Datenkonsistenz wäre möglich indem Prozesse atomar abgearbeitet werden müssen

Reihenfolge könnte festgelegt werden indem sich A und B immer abwechseln müssen und atomar abgearbeitet werden müssen.

____________

Mutual Exclusion

Definition: Kritischer Abschnitt

Programm-Abschnitt in der Prozesse auf gemeinsame Ressourcen zugreifen können.

An jedem Zeitpunkt darf sich höchstens 1 Prozess darin befinden.

Regelung durch Prolog / Epilog bei kritischem Abschnitt.

Wir wollen Daten-Konsistenz bei shared Memory $\rarr$ kein "gleichzeitiger" Zugriff auf kritischen Abschnitt.

Anforderungen:

1. Wechselseitiger Ausschluss vom kritischen Abschnitt

   Bewirkt Daten-Konsistenz bei shared Memory

   Ermöglicht durch atomaren Instruktionssequenzen

2. Progress / kein Lifelock

   Wenn kritischer Abschnitt leer, muss in endlicher Zeit entschieden werden welcher Prozess zuerst eintritt - kein "After You"

3. Bounded waiting / keine Starvation

   Nachdem ein Prozess request für Eintritt in ein Abschnitt abgegeben hat können andere nur beschränkt oft ankommen.

Software-Lösungen

Busy Waiting Beim Warten werden Test-instructions ausgeführt wie while x != true do nothing

Dekker-Algorithmus

$i$ oder $j$ im Code können entweder für die Zahl $0$ oder $1$ stehen.

• Attempt 1

  Global

  	var turn: 0..1; //can be initialized to either 0 or 1

  Process $P_i$

  while turn != i do nothing;
  ... critical section
  turn = j;
  ... remainder section

  Resultat

  Mutual exclusion aber auch erzwungene execution order ( $i$ und $j$ abwechselnd).

  Wir wollen nicht immer eine condition synchronization haben.

• Attempt 2

  Global

  flag[i] := false;
  flag[j] := false;

  Process $P_i$

  while flag[j] do nothing;
  //possible process switch here! -> No mutual exclusion
  flag[i] := true;
  ... critical section
  flag[i] := false;
  ... remainder section

  Resultat

  Keine erzwungene execution order, aber mutual exclusion nicht gegeben denn:

  1. $i$ führt Zeile $1$ aus und es kommt zu einem process-switch.

  2. Danach kann $j$ auch Zeile $1$ ausführen und sie betreten gemeinsam den kritischen Abschnitt

• Attempt 3

  Global

  flag[i] := false;
  flag[j] := false;

  Process $P_i$

  flag[i] := true;
  //possible process switch here! -> Deadlock
  while flag[j] do nothing;
  ... critical section
  flag[i] := false;
  ... remainder section

  Resultat

  Keine erzwungene execution order, mutual exclusion gegeben, aber deadlock möglich:

  1. $i$ führt Zeile $1$ aus und es kommt zu einem process-switch.

  2. Danach kann $j$ auch Zeile $1$ ausführen und es kann niemand mehr den kritischen Abschnitt betreten

• Attempt 4

  Global

  flag[i] := false;
  flag[j] := false;

  Process $P_i$

  flag[i] := true;
  while flag[j] do {
  flag[i] := false;
  ... wait for a short time
  flag[i] := true;
  }
  ...critical section
  flag[i] := false;
  ...remainder section

  Resultat:

  Keine erzwungene execution order, mutual exclusion gegeben.

  "after you" lifelock möglich wenn sich prozesse nach jeder Zeile abwechseln: Prozess setzt eigenen Flag auf false, falls beide gleichzeitig true sind und wartet bis anderer Prozess zuerst geht.

Initialisierung

flag[i] := false;
flag[j] := false;
turn := 0..1 //can be set to either 0 or 1

Process $P_i$

flag[i] := true;
while (flag[j]) { 					//both flags set to true
if (turn == j) { 					//it's the other process' turn
flag[i] := false;
while turn == j do nothing;
flag[i] := true;
}
}
... critical section
turn := j;
flag[i] := false;
... remainder section

While loop can only be left if !flag[j] && !(turn == j) but this case will never occur if we only stay within this process.

The other process will flip its own flag to false flag[j] == false if turn == i and wait.

Peterson-Algorithmus

Gleiche Logik wie Dekker-Algorithmus aber vereinfacht.

Initialisierung

flag[i] := false;
flag[j] := false;
turn := 0..1 //can be set to either 0 or 1

Process $P_i$

while(true) {
flag[i] := true;
turn := j;
while flag[j] and turn = j do nothing;
...critical section
flag[i] := false;
...remainder section
}

Mutual exclusion: Ab der Zeile $4$ ist mit Sicherheit !flag[j] && !(turn == j) , ansonsten wartet $P_i$ einfach.

Kein Lifelock: Es kann sein dass beide flag true sind, aber turn kann immer nur für ein Prozess true sein wodurch nur ein Prozess in while schleife warten kann.

Bakery Algorithm (für$n$Prozesse)

Globale Variablen:

choosing: boolean array [0..n-1] //mit false initialisiert
number: int array [0..n-1] //mit 0 initialisiert

Alle Prozesse erhalten eine Nummer.

Prozess $P_i$

while (true) {
choosing[i] := true;
number[i] := 1 + max(number[0], ..., number[n-1]);
choosing[i] := false;
for (j := 0 to n-1) do {
while choosing[j] do nothing;
while number[j] != 0 &&
(number[j] != number[i] ? number[j] < number[i] : j < i) do nothing;
}
...critical section
number [i] := 0;
...remainder section
}

Nummer $0$ bedeutet Prozess hat keine Anforderungen.

Prozess mit niedrigsten Nummer betritt kritischen Abschnitt zuerst.

neue Nummern ≥ alte Nummern - gleiche Nummernvergabe möglich wenn mehrere Prozesse hintereinander Zeile $3$ ausführen.

Hardwareunterstützte Lösungen

Interrupt Disabling

Interrupt Disabling während kritischen Abschnitt:

Test and Set

Eine einzige hardware instruction die 2 Aktionen atomar ausführt:

function testset(i: int): boolean {
if (i == 0){
i := 1;
return true;
} else {
return false;
}
}

Globale Variable

var b: integer;
b := 0;

Prozess $P_i$

while !testset(b) do nothing; //if b == 0, flip b and continue, else do nothing
...critical section
b := 0;
...remainder section

Exchange / Swap

Vertauscht Werte von 2 Variablen als atomare Instruktionssequenz.

Globale Variablen

int b := 0;

Lokale Variable - Vorinitialisiert

int key := 0;

Prozess $P_i$

key := 1;
do exchange(key,b) while (key == 1);
...critical section
exchange(key,b);
...remainder section

Damit ein Prozess die while Schleife erreicht, muss key := 1 sein.

Danach wenn die while Schleife erreicht wird, bestimmt b ob fortgesetzt wird:

• key := 1, b == 0 - swap → key := 0, b := 1 → continue

  Nach kritischem Abschnitt wird wieder geswapped wodurch anderer Prozess drankommt.

• key := 1, b == 1 - swap → key := 1, b := 1 - swap → $\dots$

Eigenschaften:

$+$ Einfach und für beliebig viele Prozesse einsetzbar

$-$ Starvation möglich → kein bounded waiting

$-$ Busy waiting (ineffizient)

Semaphore

Semaphore müssen für Mutual Exclusion auf 1 initialisiert werden.

Maximal 1 Prozess im kritischen Abschnitt

Reihenfolge und bounded waiting / fairness durch FIFO queue gegeben

init(S,1);

wait(S);
...critical section
signal(S);
...remainder section

____________

Condition Synchronization

Die Abarbeitungsreihenfolge (execution order) bestimmt Ereignisfolge.

Nicht eindeutig festgelegt $\rarr$ Race Condition.

Durch Bedingungssynchronisation geben wir die execution order vor.

Semaphore

Beispiel 1: Vorgegebene Reihenfolge

Ausführung von Code-Abschnitten in 2 Programmen.

init(S,0);

while(true){
...First this
signal(S);
}

while(true){
wait(S);
...Then that
}

Beispiel 2: Abwechselnder Zugriff

Daten werden nicht doppelt gelesen oder geschrieben.

P1 muss immer vollständig abgearbeitet werden bevor P2 starten kann - aber:

Das besondere an diesem Beispiel:

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

while(true){
generate data;
wait(A);
write ShM;
signal(B);
}

while(true){
wait(B)
read ShM;
signal(A);
use data;
}

Semaphore B ist gleich wie aus vorherigem Beispiel und A ist umgedreht, damit sie sich abwechseln.

Beispiel 3: Abwechselnder Zugriff

Gleich wie davor aber mit 3 Prozessen wobei die lesenden Prozesse parallel abgearbeitet werden sollen können.

Versuch 1

Keine Parallelität von P2, P3 gegeben - sondern P3 muss immer nach P2 kommen.

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

while(true){
generate data;
wait(A);
write ShM;
signal(B);
}

while(true){
wait(B)
read ShM;
signal(C);
use data;
}

while(true){
wait(C)
read ShM;
signal(A);
use data;
}

Versuch 2

Hier lösen wir das Beispiel genau nach dem Schema des vorherigen Beispiels.

Starvation von P2 oder P3 möglich, da eines von ihnen mehrfach ausgeführt werden kann ohne sich abzuwechseln.

init(A,2); init(B,0);

while(true){
generate data;
wait(A);
wait(A);
write ShM;
signal(B);
signal(B);
}

while(true){
wait(B)
read ShM;
signal(A);
use data;
}

while(true){
wait(B)
read ShM;
signal(A);
use data;
}

Lösung

Kleine Abänderung um Starvation zu vermeiden

init(A,2); init(B1,0); init(B2,0);

while(true){
generate data;
wait(A);
wait(A);
write ShM;
signal(B1);
signal(B2);
}

while(true){
wait(B1)
read ShM;
signal(A);
use data;
}

while(true){
wait(B2)
read ShM;
signal(A);
use data;
}

____________

Höhere Synchronisations-Konstrukte

Semaphore

Von OS zur Verfügung gestellt.

Wir vermeiden busy waiting - Prozesse warten in blocked queues bis ein Event auftritt.

Implementierung

• Detailiert

  type semaphore = record
  value: integer; //auch count genannt
  queue: list of processes;
  end;

  init(S, val):
  S.value := val;
  S.queue := empty list;

  wait(S):
  S.value := S.value - 1;
  if (S.value < 0) {
  ...add this process to S.queue and block it;
  }
  

  signal(S):
  S.value := S.value + 1;
  if (S.value <= 0) {
  ...remove a process P from S.queue and place on ready queue;
  }

Die Funktionen wait(S)/P(S) , signal(S)/V(S) sind atomare Instruktionssequenzen ausgeführt werden.

Variationen in der Implementierung

S.value = #Prozesse die hintereinander wait(S) ausführen können, ohne zu blockieren.

Wenn S.value < 0 ist |S.value| die Anzahl der Prozesse die in der blockierten Queue sind.

Probleme

kompliziert, unübersichtlich, schwer lesbar

Debuggen schwer da über Programm-Code verstreut

Operationen müssen entweder alle korrekt verwendet werden oder alle voneinander abhängigen Prozesse zeigen fehlferhalten.

Monitore

Software-Modul, dass alles was zu Synchronisation und Mutual Exclusion gehört bündelt - beinhaltet:

Prozeduren

Lokale Daten

Initialisierungscode

Zugriffsfunktionen

cwait(c) blockiert ausführenden / aufrufenden Prozess, bis c == true

csignal(c) setzt einen wartenden Prozess fort

Unterschiede zu Semaphoren

Compartmentalization

Automatische mutual exclusion

csignal macht nichts wenn es keinen wartenden Prozess gibt - keine Speichernde Wirkung.

Beispiel: Producer-Consumer Problem

Monitor Datei: ProducerConsumer

b: array[0..K-1] of items;
In := 0, Out := 0, count := 0 : integer;
notfull, notempty: condition;

append(v):
if (count = K) cwait(notfull);
b[In] := v;
In := (In + 1) mod K;
count++;
csignal(notempty);

take(v):
if (count = 0) cwait(notempty);
v := b[Out];
Out := (Out + 1) mod K;
count--;
csignal(notfull);

Message Passing / Nachrichten

Methode zur Interprozesskommunikation IPC für einzelne Computer und verteilte Systeme.

Nachrichten versichern Datenkonsistenz und sind atomare Datenstrukturen:

Es gibt eine Queue für empfangene Daten

Sendensend(destination, message)

Es können mehrere oder ein einziger Empfänder adressiert werden.

Es ist auch möglich direkt (Mailbox) oder indirekt (Portadresse) Nachrichten zu versenden.

Empfangenreceive(source, message)

Empfangene Daten können in einer Queue gespeichert werden (Ereignissemantik) oder alte empfangene Daten überschreiben (Zustandssemantik).

Beispiel

Gemeinsame mailbox mutex wird von mehreren Prozessen benutzt um eine blockierende Nachricht zu schicken und zu erhalten.

init: send(mutex, msg);

while(true){
receive(mutex, msg); //blocking receive
...critical section
send(mutex, msg); //non-blocking send
...remainder section
}

Lock

enter(lock) blockiert nachfolgende enter-Aufrufe

release(lock) gibt lock frei

Sequencer und Eventcounts

Eventcount E

advance(E)E++ (wobei Anfangswert immer 0)

await(E, val) blockiert bis E >= val

Sequencer S

ticket(S) retourniert S und executed S++

Beispiel: Mutual exclusion

myticket = ticket(S);
await(E, myticket);
...critical section
advance(E);

Dadurch dass, der vorgänger-Prozess von $i$ immer ein myticket erhält mit dem Wert $i-1$ funktioniert dieser Code.