 |
Prozeß-Synchronisation
In einigen Multitasking-Betriebssystemen teilen sich verschiedene Prozesse
gemeinsame Betriebsmittel. Bei gleichzeitigem Zugriff zweier Prozesse auf diese Betriebsmittel kann es zu Inkonsistenzen der Daten kommen, die u. U. selten auftreten und sehr schwer aufzuspühren sind.
Kooperierende nebenläufige Prozesse müssen daher wegen der zwischen ihnen vorhandenen Abhängigkeiten miteinander synchronisiert (koordiniert) werden.Prinzipiell lassen sich zwei Klassen von Abhängigkeiten unterscheiden:- Die Prozesse konkurieren um die Nutzung gemeinsamer, exklusiv nutzbarer BetriebsmittelBeispiel: Zwei Prozesse greifen verändernd auf gemeinsame Daten zu. Der Zugriff zu den gemeinsamen Daten muß koordiniert werden, um eine Inkonsistenz der Daten zu
vermeiden --> Sperrsynchronisation (gegenseitiger Ausschluß, mutual exclusion)
- Die Prozesse sind voneinander datenabhängig.
Beispiel: Ein Prozeß erzeugt Daten, die von einem anderen Prozeß weiter
bearbeitet werden sollen. Es muß eine bestimmte Abarbeitungsreihenfolge
entsprechender Verarbeitungsschritte eingehalten werden --> Zustands- oder
Ereignissynchronisation (z. B. Produzenten-Konsumenten-Synchronisation)
Ohne eine solche Sperrung entstehen Datenverluste, z. B. in folgenden Fall:
- Prozeß A und Prozeß B lesen ein Datenelement im Zustand X(0).
- A schreibt es mit dem Wert X(1) zurück,
- danach schreibt B seinen Wert X(2) zurück.
Damit bleibt die Änderung X(0) nach X(1) aus dem Prozeß A
unberücksichtigt.
Oder auch bei folgendem Beispiel:
- Prozeß A informiert sich in der Spooler-Warteschlange über den
nächsten freien Eintrag und notiert dessen Adresse, z. B. 7 in der Variablen
next_free_slot. Danach wird ihm der Prozessor entzogen.
- Prozeß B findet die gleiche Adresse (7) und trägt sie in
next_free_slot ein. Danach schreibt er an die Position 7 der Warteschlange
den Namen der auszugebenden Datei und erhöht die Variable next_free_slot
auf 8.
- Prozeß A erhält nun den Prozessor wieder zugeteilt und macht dort weiter,
wo er unterbrochen wurde. Er findet in next_free_slot den Wert 7 und
trägt den Namen der von ihm auszugebenden Datei in Position 7 der
Spooler-Warteschlange ein und erhöht die Variable next_free_slot
ohne zu bemerken, daß der Wert 8 dort schon eingetragen war.
Folge: Prozeß A überschreibt den Dateinamen, den Prozeß B
in der Spooler-Warteschlange auf Position 8 eingetragen hatte.
Diese Datei wird vom Spooler "vergessen".
Solche Situationen heißen zeitkritsche Abläufe.
Programmabschnitte, die auf gemeinsam benutzte Daten zugreifen, heißen
kritische Abschnitte.
Fehler in zeitkritischen Abläufen sind sehr schwer erkennbar, da sie nur sehr
selten auftreten. Sie können nur durch wechselseitigen Ausschluß vermieden
werden. Kritische Abschnitte treten überall auf, wo zwei oder mehr Prozesse auf
einem Computer oder in einem Netz um mindestens eine Ressource konkurrieren,
die sie schreibend benutzen wollen. Kritische Abschnitte können aber auch
überall da auftreten, wo mehrere Prozesse um eine Ressource konkurrieren, die
sie schreibend benutzen. Das trifft besonders auf Datenbankserver zu
(z. B. Reservierungssysteme, zentrale Karteien, usw.).
Vier Bedingungen für eine gute Lösung (nach Tanenbaum):
- Höchstens ein Prozeß darf sich in einem kritischen Abschnitt
aufhalten. (Korrektheit)
- Es dürfen keine Annahmen über Ausführungsgeschwindigkeit und
Anzahl der Prozessoren gemacht werden.
- Kein Prozeß, der sich in einem kritischen Abschnitt befindet, darf
andere blockieren.
- Kein Prozeß soll unendlich lange warten müssen,
bis er in einen kritischen Bereich eintreten darf.
Die letzten beiden Punkte dienen der Stabilität, sie sollen Prozeßverklemmungen
verhindern.
Beispiele für zeitkritische Abläufe
1. Das Erzeuger-Verbraucher-Problem:
Der Erzeuger E stellt ein Produkt her und stellt es in einen begrenzten Pufferspeicher.
Verbraucher V entnimmt dem Puffer ein Stück des Produktes, um es zu verbrauchen.
Beides geschieht zu zufälligen Zeitpunkten. Der Puffer wird von beiden gemeinsam
verwaltet. Solche Erzeuger-Verbraucher-Probleme treten beispielsweise bei Pipes auf
(Ein Prozeß erzeugt Daten, der andere verarbeitet sie weiter.)
- Der Erzeuger muß zuerst prüfen, ob noch Platz im Puffer ist, bevor
er ein Produkt ablegen kann.
Er muß dann auch den Produktzähler count erhöhen.
Ist der Puffer voll, muß er schlafen gehen.
- Der Verbraucher muß prüfen, ob der Puffer nicht leer ist, bevor er
etwas entnimmt. Er muß dann count dekrementieren. Ist nichts im Puffer,
muß er schlafen gehen.
Wenn der Erzeuger ein Produkt in den Puffer stellt, muß er den Verbraucher wecken.
Analog muß der Verbraucher den Produzenten wecken, wenn er ein Produkt aus dem
Puffer entnimmt. Tanenbaum verwendet dafür die Funktionen SLEEP und
WAKEUP. Er zeigt eine Lösung für das Erzeuger-Verbraucher-Modell,
die einen fatalen Fehler zuläßt:
#define N 100 /* Puffergröße */
int count = 0; /* Tatsächlicher Pufferinhalt */
void producer (void)
}
tinhalt item;
while (1) /* Endlosschleife */
}
produce_item (&item); /* Erzeuge 1 Stück */
if (count == N) SLEEP(); /* Falls Puffer voll, schlafen */
enter_item (item); /* lege erzeugtes Stück in Puffer */
count++;
/* wenn Puffer vor dem Weiterzählen leer war, Verbraucher wecken */
if (count == 1) WAKEUP(consumer);
}
}
void consumer (void)
}
tinhalt item;
while (1) /* Endlosschleife */
}
if (count == 0) SLEEP(); /* Falls Puffer leer, schlafen */
remove_item (item); /* entnehme dem Puffer ein Stück */
count--; /* Pufferinhalt korrigieren */
/* wenn Puffer vor Korrigieren voll war, Erzeuger wecken */
if (count == N-1) WAKEUP(producer);
consume_item (&item); /* verbrauche 1 Stück */
}
}
Die Funktionen sollen selbstständig laufende Programme repräsentieren,
die beide zu beliebigen Zeitpunkt durch einen Scheduler-Eingriff unterbrochen
oder wieder aktiviert werden können.
Wenn der Consumer schläft, weil der Puffer leer ist, muß man nicht
davon ausgehen, daß der Puffer immer leer bleibt. Der Producer kann ja
zwischendurch den Prozessor zugeteilt bekommen, etwas in den Puffer legen und
den Consumer wieder wecken.
Umgekehrt schläft der Producer, wenn der Puffer voll ist. Während er
schläft, kann der Consumer den Prozessor zugeteilt bekommen, etwas verbrauchen
(so daß im Puffer wieder Platz wird) und den Producer wieder wecken.
Der Fehler tritt bei folgendem Szenario auf:
Der Puffer ist leer und der Verbraucher stellt das fest (count = 0).
Genau jetzt unterbricht der Scheduler den Verbraucher und startet den Produzenten.
Dieser legt ein Produkt in den Puffer, setzt count auf 1 und startet WAKEUP.
Wenn der Verbraucher vom Scheduler wieder die CPU zugeteilt bekommt, ist er noch
wach. Der Weckruf verhallt ungehört, weil ja der Verbraucher nicht schläft.
Der Verbraucher wertet die vorher festgestellte Tatsache "count = 0" aus und geht
schlafen. Es gibt für den Produzenten keinen Anlaß, nochmals zu wecken.
Der Verbraucher wird nie mehr geweckt.
Ursache für diese Blockierung ist eine Prozeßunterbrechung im kritischen
Abschnitt zwischen Erkennung der Bedingung, die zum Aufruf von SLEEP führt
und dem SLEEP-Kommando selbst. Die gleiche Situation würde auftreten, wenn der
Produzent zwischen der Erkenntnis, daß der Puffer voll ist (free = 0) und dem
Schlafengehen unterbrochen wird.
2. Das Problem des schlafenden Friseurs:
Dieses Modell geht davon aus, daß beide nach dem Zeitscheibenprinzip nur
abwechselnd handeln können.
Ein Friseur bedient, sobald er Zeit dafür hat, ankommende oder wartende Kunden.
Der Warteraum ist beschränkt auf N Stühle.
- Der Friseur (= Prozessor) startet zu Arbeitsbeginn die Funktion barbier().
Wenn kein Kunde da ist, legt er sich schlafen.
- Kommt ein Kunde, prüft er die Bedingung count >= N. Sind
alle Stühle belegt, geht er wieder. Sonst bleibt er und erhöht count
um eins. War count vorher 0, weckt er den schlafenden Friseur.
- Wenn der Friseur einen Kunden bedient hat, dekrementiert er count.
Ist count dann 0 geworden, legt er sich wieder schlafen.
Die kritische Situation besteht darin, daß der Kunde zwischen der Dekrementierung
von count und der Frage "Ist count gleich 0" ankommt und den Friseur
wecken kann, obwohl der sich noch gar nicht schlafen gelegt hat.
Lösungsversuche für das Problem der kritischen Abschnitte
- Einfachste Lösung: Vor Eintritt in den kritischen Bereich alle
Interrupts sperren und sie nach Verlassen des kritischen Bereichs wieder
freigeben. Damit kann der Scheduler nicht während des kritischen Abschnitts
den Prozeß unterbrechen.
Nachteil: Kein verdrängendes Multitasking mehr. Der Anwenderprozeß kann
den Scheduler blockieren (gewollt oder ungewollt durch einen Programmfehler).
- Verfahren mit gegenseitigem Ausschluß
Der Programmabschnitt, in dem ein Zugriff zu dem nur exklusiv nutzbaren Betriebsmittel
(z. B. die gemeinsamen Daten) erfolgt, wird kritischer Abschnitt genannt. Es muß
verhindert werden, daß sich zwei Prozesse gleichzeitig in ihren kritischen
Abschnitten befinden.
- Sperrvariable:
Es wird eine logische Variable geführt, die mit 0 den Eintritt in den
kritischen Bereich erlaubt und mit 1 sperrt. Der in den kritischen Bereich
eintretende Prozeß muß dann vor seinem Eintritt prüfen, ob
der Bereich frei ist, die Sperrvariable auf 1 setzen und nach Ende wieder
freigeben.
Der Abschnitt von der Prüfung der Sperrvariablen bis zu ihrem Setzen
ist selbst ein kritischer Abschnitt! Er ist zwar kürzer und damit die
Konfliktwahrscheinlichkeit geringer, aber die Gefahr des Konfliktes ist nicht
beseitigt! Es gibt bei vielen CPUs jedoch Befehle von der Form "teste und setze",
bei denen der kritische Abschnitt innerhalb eines Maschinenbefehls "abgehandelt"
wird. Damit sind folgende Lösungen möglich:
- "Aktives Warten":
bool v;
/* Warteschleife, bis Riegelvariable RV[i]= 0 ist */
do
v = test_and_set(&RV[i]);
while (v == 0);
...
/* kritischer Abschnitt zur Datenmenge i */
...
RV[i] : = 1;
Die Ver- bzw. Entriegelung wird häufig mit den Funktionen LOCK und
UNLOCK formuliert:
L0CK(RV[i]);
...
/* kritischer Abschnitt zur Datenmenge i */
...
UNLOCK(RV[i]);
Viele Computer, die für Mehrprozessorbetrieb konzipiert wurden, kennen den
Maschinenbefehl "Test and Set Lock". Dabei wird ein Speicherwort aus einem
Register gelesen und ein Wert ungleich Null hineingeschrieben.
Für die TSL-Operation wird eine gemeinsame Variable namens "Flag" verwendet.
Diese koordiniert den Zugriff. Beispiel:
enter_region: tsl register,flag kopiere flag ins Register und setzte flag auf 1
cmp register,#0 war flag Null?
jnz enter_region wenn nicht, Verriegelung gesetzt, Schleife
... kritischer Bereich ...
leave_region: mov flag,#0 flag auf 0 setzten
ret Rückkehr zum Aufrufer
Aktives Warten verbraucht CPU-Zeit durch Warteschleifen.
- "Striktes Alternieren":
Nur zwei Prozesse erlauben sich wechselweise den Eintritt in den kritischen
Abschnitt mit einer logischen Sperrvariablen. Zum Beispiel dient die gemeinsame
Sperrvariable turn zur Synchronisiation zweier Prozesse. Es gilt:
turn = i (i = 0,1) --> Prozeß Pi darf in den
kritischen Bereich eintreten:
PO:
while (1)
{
while (turn != 0) no_operaion; /* warten */
kritischer Bereich;
turn = 1;
unkritischer Bereich;
}
P1:
while (1)
{
while (turn != 1) no_operaion; /* warten */
kritischer Bereich;
turn = 0;
unkritischer Bereich;
}
Auch hier wird CPU-Zeit durch Warteschleifen verbraucht. Außerdem
ist striktes Alternieren auch keine gute Lösung, wenn ein Prozeß
wesentlich langsamer ist als der andere.
- Semaphore
Bisher haben die Prozesse ihren Eintritt in den kritischen Abschnitt selbst gesteuert.
Die folgenden Techniken erlauben es dem Betriebssystem, Prozessen den Zutritt zum
kritischen Abschnitt zu verwehren. Im Zusammenhang mit Algol 68 entwickelte Dijkstra
das Prinzip der Arbeit mit Semaphoren. Für jede zu schützende Datenmenge
wird eine Variable (Semaphor) eingeführt (binäre Variable oder nicht-negativer
Zähler).
Ein Semaphor (Sperrvariable, Steuervariable) signalisiert einen Zustand (Belegungszustand,
Eintritt eines Ereignisses) und gibt in Abhängigkeit von diesem Zustand den weiteren
Prozeßablauf frei oder versetzt den betreffenden Prozeß in den Wartezustand.
Beim Bemühen um unteilbare Ressourcen (z. B. den Prozessor) wird eine binäre
Variable verwendet, bei N Teil-Ressourcen (z. B. Arbeitsspeicher-Segmente oder
Plätze in einem Puffer) kommen Werte von 1 bis N vor.
Die binären Semaphore werden auch "Mutexe" (von "Mutual exclusion") genannt,
jene vom Typ Integer auch "Zähl-Semaphore".
Semaphore für den gegenseitigen Ausschluß sind dem jeweiligen exklusiv
nutzbaren Betriebsmittel zugeordnet und verwalten eine Warteliste für dieses
Betriebsmittel. Sie sind allen Prozessen zugänglich. Semaphore für die
Ereignissynchronisation zweier voneinander datenabhängiger Prozesse sind diesen
Prozessen direkt zugeordnet. Sie dienen zur Übergabe einer Meldung über das
Ereignis zwischen den Prozessen.
Zur Manipulation und Abfrage von Semaphoren existieren zwei unteilbare, d. h. nicht
unterbrechbare Operationen (Semaphor S):
- P-Operation: Anfrage-Operation
if (s > 0)
s = s - l; /* Prozeß kann weiterlaufen,
Zugriff für andere Prozesse wird gesperrt */
else
/* der die P-Operation ausführende Prozeß wird "wartend";
Eintrag des Prozesses in die vom Semaphor
verwaltete Warteliste; */
- V-Operation: Freigabe-Operation
if (Warteliste leer)
s = s + l; /* Zugriff für andere, noch nicht wartende
Prozesse wird freigegeben */
else
/* nächster Prozeß in Warteliste wird "bereit";
Zugriff für wartenden Prozeß wird freigegeben */
Lösungsmöglichkeit für Erzeuger-Verbraucher-Synchronisation
(Vorbesetzung der Semaphore: start = 0; finish = 0):
| Produzent: | | Konsument: |
|---|
while (1)
{
while (!buffer-full)
write_into_buffer();
signal(start); /* V-Operation */
wait(finish); /* P-Operation */
}
|
|
while (1)
{
wait(start); /* P-Operation */
while(!buffer-empty)
read_from_buffer();
signal(finish); /* V-Operation */
}
|
- Ereigniszähler
Für einen Ereigniszähler E sind drei Operationen definiert:
- read(E): Stelle Wert von E fest!
- advance(E): Inkrementiere E (atomare Operation)
- await(E,v): Warte bis E = v ist
Damit kann E nur wachsen, nicht kleiner werden! E sollte mit 0 initialisiert werden.
Die hier gezeigte Produzent-Konsument Lösung verwendet die Operation read()
nicht, andere Sychronisationsprobleme machen diese Operation dennoch notwendig.
Hier arbeitet der Puffer als Ringpuffer.
Anmerkung: Mit % wird der Modulo-Operator gekennzeichnet (= Rest der ganzzahligen
Division).
#define N 100 /* Puffergröße */
eventcounter inputcounter = 0, outputcounter = 0; /* Ereigniszaehler */
int inputsequence = 0, outputsequence = 0;
producer()
{
tinhalt item;
while (1)
{
produce(&item);
inputsequence = inputsequence + 1;
await(outputcounter,inputsequence-slots);
buffer[(inputsequence - 1) % N] = item;
advance(inputcounter);
}
}
consumer()
{
tinhalt item;
while (1)
{
outputsequence = outputsequence + 1;
await(inputcounter,outputsequence);
item = buffer[(outputsequence - 1] % N);
advance(outputcounter);
consume(&item);
}
}
Die Ereignis-Zähler werden nur erhöht, nie erniedrigt. Sie
beginnen immer bei 0. In unserem Beispiel werden zwei
Ereignis-Zähler verwendet. inputcounter zählt die
Anzahl der produzierten Elemente seit dem Start. outputcounter
zählt die Anzahl der konsumierten Elemente seit dem Start. Aus diesem
Grunde muß immer gelten: outputcounter <= inputcounter.
Sobald der Produzent ein neues Element erzeugt hat, prüft er mit Hilfe
des er den await-Systemaufrufs, ob noch Platz im Puffer vorhanden
ist. Zu Beginn ist outputcounter = 0 und (inputsequence - N)
negativ - somit wird der Produzent nicht blockiert. Falls es dem Produzenten
gelingt N+1 Elemente zu erzeugen, bevor der Konsument startet, muß er
warten, bis outputcounter = 1 ist. Dies tritt ein, wenn der Verbraucher
ein Element konsumiert. Die Logik des Konsumenten ist noch einfacher. Bevor das m-te
Element konsumiert werden kann, muß mit await(inputcounter,n)
auf das Erzeugen des m-ten Elementes gewartet werden.
|
| |
DIENSTE
