View
110
Download
5
Category
Preview:
Citation preview
Modul: B-BSBetriebssystemeSS 2014
Prof. Dr. Rüdiger BrauseAdaptive SystemarchitekturInstitut für InformatikFachbereich Informatik und Mathematik (12)
Prozess-synchronisation
Folie 2R.Brause - Betriebssysteme: ProzeßSynchronisation(C) Goethe-Universität, Frankfurt
Prozesskommunikation
Race Conditions, Semaphore
Anwendungen
Verklemmungen
Folie 3R.Brause - Betriebssysteme: ProzeßSynchronisation
Race conditions
Beispiel: Kontoführung Paralleler Zugriff auf globale Variable C
Parallele Prozesse von vielen Benutzern arbeiten gleichzeitig auf den Daten. Falls gleichzeitig zwei Benutzer auf das gleiche Konto einzahlen möchten, so kann es sein, dass der Kontostand hinterher nicht stimmt.
Ein solcher Fehler wird von keinem Kunden toleriert!
Zeit
15:00 Uhr Konto C= 300 €
15:01 A := read(C)
A := A + 500
A write(C)
15:04
15:03
15:02
B := read(C)
B := B -100
B write(C)
Konto C = 200 €
500 € einzahlen 100 € abheben
Eine Fehlbuchung tritt nur auf, wenn Prozess den Prozess überholt („race condition“)
(C) Goethe-Universität, Frankfurt
Folie 4R.Brause - Betriebssysteme: ProzeßSynchronisation
Race conditions
Situation: Warteschlangeneintrag eines PCB
Einhängen A Aushängen B(1) Lesen des Ankers: PointToB (1) Lesen des Ankers: PointToB(2) Setzen des NextZeigers:=PointToB (2) Lesen des NextZeigers:PointToC(3) Setzen des Ankers:=PointToA (3) Setzen des Ankers:=PointToC
Problem: („Race conditions“: kontextbedingt, nicht-wiederholbare Effekte durch „überholende“ Prozesse)
a) Unterbrechung beim Aushängen von B durch Einhängen von A Prozeß A ist weg!
b) Unterbrechung beim Einhängen von A durch Aushängen von B Prozeß B bleibt erhalten!
Anker B C PointToB PointToC
A PointToA
PCB(B) PCB(C)
(C) Goethe-Universität, Frankfurt
Folie 5R.Brause - Betriebssysteme: ProzeßSynchronisation
Synchronisation: Forderungen
1. Zwei Prozesse dürfen nicht gleichzeitig in ihren kritischen Abschnitten sein (mutual exclusion).
2. Jeder Prozeß, der am Eingang eines kritischen Abschnitts wartet, muß irgendwann den Abschnitt auch betreten dürfen: kein ewiges Warten darf möglich sein (fairness condition).
3. Ein Prozeß darf außerhalb eines kritischen Abschnitts einen anderen Prozeß nicht blockieren.
4. Es dürfen keine Annahmen über die Abarbeitungsge-schwindigkeit oder Anzahl der Prozesse bzw. Prozessoren gemacht werden.
(Dijkstra 1965)
(C) Goethe-Universität, Frankfurt
Folie 6R.Brause - Betriebssysteme: ProzeßSynchronisation
Synchronisierung: erster Versuch
Naiver Ansatz: mutual exclusion mit globaler VariablenWartesperre errichten, bis kritischer Abschnitt frei Initial dran=1
Prozeß 1 Prozeß 2. . . . . .
WHILE dran1 DO NoOp END; WHILE dran2 DO NoOp END;
Kritischer Abschnitt Kritischer Abschnitt
dran := 2; dran := 1;
. . . . . .
Problem: nur wechselseitige Benutzung des kritischen Abschnitts möglich, Prozeß blockiert sich nach Ausführung selbst. (nicht-notw. Blockade sowie fairness sind verletzt bei ewigem Warten)
(C) Goethe-Universität, Frankfurt
Folie 7R.Brause - Betriebssysteme: ProzeßSynchronisation
Synchronisierung: zweiter Versuch
Verbesserung: Zugang nur blockiert beim Aufenthalt in krit. Abschnitt
Prozeß 1 Prozeß 2. . . . . .
WHILE drin2=TRUE DO NoOp END;
drin1 := TRUE;
WHILE drin1=TRUE DO NoOp END;
drin2 := TRUE;
Kritischer Abschnitt Kritischer Abschnitt
drin1 := FALSE; drin2 := FALSE;
. . . . . .
Problem: Initialisierung drin1=drin2=False keine mutual exclusion!drin1=True, drin2=False P2 ist blockiert ohne Sinn
(C) Goethe-Universität, Frankfurt
Folie 8R.Brause - Betriebssysteme: ProzeßSynchronisation
Synchronisierung: Lösung
Peterson 1981Verbesserung: eine globale Variable, 2 Prozeß-Zustandsvariable.
Initial Interesse1 = Interesse2 = FALSE
Prozeß 1 Prozeß 2. . . . . .
Interesse1 := TRUE; Interesse2 := TRUE; dran := 1;WHILE dran=1 AND Interesse2=TRUEDO NoOp END;
dran := 2;WHILE dran=2 AND Interesse1=TRUEDO NoOp END;
Kritischer Abschnitt Kritischer Abschnitt
Interesse1 := FALSE; Interesse2 := FALSE;
. . . . . .
(C) Goethe-Universität, Frankfurt
Folie 9R.Brause - Betriebssysteme: ProzeßSynchronisation
Lösung: Signale und Semaphoren
Peterson: Synchronisierung durch Signale (Interesse)
Allgemein: Das Semaphor (Signalbarken, Dijkstra 1965)
Passieren P(s) waitFor (signal)Aufruf vor krit. Abschnitt, Warten falls besetzt
Verlassen V(s) send (signal)Aufruf nach krit. Abschnitt, Aktivieren eines wart. Prozesses
Beispiel: paralleles Hochzählen z = 1, 2, 3, ... z global
Prozeß 1 Prozeß 2. . . . . .
P(s) P(s)
V(s) V(s)
. . . . . .
z :=z+1; WriteInteger(z)z :=z+1; WriteInteger(z)
warten
freigeben
(C) Goethe-Universität, Frankfurt
Folie 10R.Brause - Betriebssysteme: ProzeßSynchronisation
Implementierung Semaphoren: busy wait
Software Pseudo-Code Semaphore=Zähler, initial s=1
PROCEDURE P(VAR s:INTEGER)BEGIN WHILE s<=0 DO NoOp END; Ununterbrechbar! s:=s-1;END P; PROCEDURE V(VAR s:INTEGER)BEGIN s:=s+1; Ununterbrechbar!END V;
Problem: spin locks können fairness verletzten, wenn die Zeitscheibe eines niedrig-prio Prozeß im krit. Abschnitt zu Ende geht
(C) Goethe-Universität, Frankfurt
Folie 11R.Brause - Betriebssysteme: ProzeßSynchronisation
Implementierung Semaphoren: Schlafen
TYPE Semaphor = RECORD value: INTEGER; list : ProcessList; END;
Initial: s.value:=1
Software Pseudo-Code Datenstruktur
PROCEDURE P(VAR s:Semaphor)BEGIN s.value:=s.value-1; IF s.value < 0 THEN einhängen(MyID,s.list); sleep; END;END P; PROCEDURE V(VAR s:Semaphor)VAR PID: ProcessId;BEGIN IF s.value < 0 THEN PID:=aushängen(s.list); wakeup(PID); END; s.value:=s.value +1;END V;
(C) Goethe-Universität, Frankfurt
Folie 12R.Brause - Betriebssysteme: ProzeßSynchronisation
Atomare Aktionen
Beispiel: GeldtransaktionSie überweisen 2000 €.
Abbuchung 2000 € Empfänger-Gutbuchung 2000 €
Wo ist das Geld? Keine oder neue Überweisung = Verlust!
Forderung: „Atomare Aktion“Entweder vollständige Transaktion oder gar keine !(„roll back“ bei Abbruch)
Computerabsturz !
(C) Goethe-Universität, Frankfurt
Folie 13R.Brause - Betriebssysteme: ProzeßSynchronisation
Interrupts ausschalten (Probleme: timer, power failure, I/O)
Atomare Instruktionsfolgen
Test And Set (test and set lock)
PROCEDURE TestAndSet(VAR target:BOOLEAN): BOOLEANVAR tmp:BOOLEAN; tmp:=target; target:= TRUE; RETURN tmp;END TestAndSet;
Swap PROCEDURE swap(VAR source,target: BOOLEAN)VAR tmp:BOOLEAN;
tmp:=target; target:=source; source:=tmp;END swap;
Fetch And Add PROCEDURE fetchAndAdd(VAR a, value:INTEGER):INTEGERVAR tmp:INTEGER;
tmp:=a; a:=tmp+value; RETURN tmp;END fetchAndAdd;
HW-Implementierung: Atomare Aktionen
(C) Goethe-Universität, Frankfurt
Folie 14R.Brause - Betriebssysteme: ProzeßSynchronisation
Software Pseudo-Code Semaphore=Zähler, initial s=1
PROCEDURE P(VAR s:INTEGER)BEGIN WHILE FetchAndAdd(s,-1)<= 0 Ununterbrechbar!
DO FetchAndAdd(s,+1) END END P PROCEDURE V(VAR s:INTEGER)BEGIN FetchAndAdd(s,+1) Ununterbrechbar!END V
Probleme?
Implementierung Semaphoren: busy wait
(C) Goethe-Universität, Frankfurt
Folie 15R.Brause - Betriebssysteme: ProzeßSynchronisation
Implementierung der Semaphor-Operationen,Anwendung Multiprozessorsynchronisation
VAR s: INTEGER; (* Semaphore, initial = 1*) PROCEDURE P(s); PROCEDURE V(s);BEGIN BEGIN LOOP FetchAndAdd(s,1)
END V; IF (FetchAndAdd(s,-1) >= 1)
THEN RETURN END; FetchAndAdd(s,1); ENDLOOP;END P;
s = 1,
Anwendung Multiprozessoren
WHILE s<1 DO NoOp END;
P2 P1 P3 P2 P2 P3P3 ....P10, -1, 0, -1, 0, -1, 0, -1, 0,
P2 P2-1,
(C) Goethe-Universität, Frankfurt
Folie 16R.Brause - Betriebssysteme: ProzeßSynchronisation
Frage
Angenommen, Sie haben 3 Prozesse und 2 kritische Abschnitte pro Prozess.
Wieviele Semaphore benötigen Sie?
? 2? 3? 6? 12
Code A
Code A
Code A
Krit. Abschn.
Krit. Abschn.
Code B
Code B
Code B
Krit. Abschn.
Krit. Abschn.
Code C
Code C
Code C
Krit. Abschn.
Krit. Abschn.
(C) Goethe-Universität, Frankfurt
Folie 17R.Brause - Betriebssysteme: ProzeßSynchronisation
memory
Prozesse
Semaphoren: Unix
lockf Sperren Dateizugriff P(s) lock file
msem_init Semaphorinit. zumSpeicherzugriffmsem_lock Sperren eines Semaphors P(s)msem_unlock Entsperren eines Semaphors V(s)msem_remove Entfernen eines Semaphors
semctl Semaphorkontrolloperationensemget hole Semaphorwertsemop Semaphoroperation
(C) Goethe-Universität, Frankfurt
Folie 18R.Brause - Betriebssysteme: ProzeßSynchronisation
Semaphore: Windows NT
ProzesseCreateSemaphore() ErzeugenOpenSemaphore() InitialisierenWaitForSingleObject(Sema,TimeOutVal) P(s)ReleaseSemaphore() V(s)
Kernprozesse Spin locks: keine Referenzen zu Disk-Speicher, keine traps & syscalls
Threads
Semaphore = Type CRITICAL_SECTION InitializeCriticalSection(S)EnterCriticalSection(S) P(s)LeaveCriticalSection(S) V(s)
(C) Goethe-Universität, Frankfurt
Folie 19R.Brause - Betriebssysteme: ProzeßSynchronisation(C) Goethe-Universität, Frankfurt
Synchronisierung: Threads und Objekte
Object(Instanz 1)
Object(Instanz 1)
Thread 2
Object(Instanz 2)
Object(Instanz 2)
Thread 1
Zwei Threads innerhalb eines Prozesses erzeugen das gleiche Objekt.
Die Methoden beider Objekt-Instanzen greifen auf die gleichen globalen Daten (Attribute) zu.
Chaos, wenn beide Threads auf die globalen Daten zugreifen.
Glo
bal
e D
aten
(st
atic
)G
lob
ale
Dat
en (
stat
ic)
Problem:
Folie 20R.Brause - Betriebssysteme: ProzeßSynchronisation
Lösung: Prozeßgruppen
Apartment CApartment BApartment A
Prozess YProzess X
Objekt 1 Objekt 1 Objekt 1
Objekt 2 Objekt 2 Objekt 2
t3
t2
t1
t4
t5t6t7
Mögliche Lösung: Sperrung der Objekte, Serialisierung des Zugriffs (marshalling)
Nachteil: keine Parallelaktivitäten möglich!
Windows NT: explizite Zuordnung der Threads zu Objektmengen (Apartments)
(C) Goethe-Universität, Frankfurt
Folie 21R.Brause - Betriebssysteme: ProzeßSynchronisation
Lösung: Threadgruppen in NT
Für jedes Objekt Speicherung des Threading-Modells (STA, MTA,both) in der Registrierung. MTA nur bei lokalen Daten !
Thread 1Thread 1
Thread 2Thread 2
main STA
Single-Threaded Apartment STA
Thread 3Thread 3
Multi-Threaded Apartment MTA
Thread 4Thread 4
Pro
zess
Marshalling
Marshalling
Objekt 1
Objekt 2
Objekt 3
Objekt 4
(C) Goethe-Universität, Frankfurt
Folie 22R.Brause - Betriebssysteme: ProzeßSynchronisation(C) Goethe-Universität, Frankfurt
Prozesskommunikation
Race Conditions, Semaphore
Anwendungen
Verklemmungen
Folie 23R.Brause - Betriebssysteme: ProzeßSynchronisation
Anwendung: Synchr. von Prozessen
Präzedenzgraph
Implementierung mit Semaphoren
PROCESS A: TaskBodyA; V(b); V(c); END A;PROCESS B: P(b); TaskBodyB; V(d1);V(e); END B;PROCESS C: P(c); TaskBodyC; V(d2); END C;PROCESS D: P(d1); P(d2); TaskBodyD; END D;PROCESS E: P(e); TaskBodyE; END E;
Globale Variable b,c,d1,d2,e mit 0 initialisieren.
B E
A
C D
(C) Goethe-Universität, Frankfurt
Folie 24R.Brause - Betriebssysteme: ProzeßSynchronisation
Synch. Erzeuger-Verbraucher
Problem: race condition innerhalb der Flusskontrollebei Umschaltung nach „used=0“Pufferfüllung, dann ewiges Schlafen beider
Prozesse.
Erzeuger
LOOPproduce(item) IF used=N THEN sleep(); putInBuffer(item); used := used+1; IF used=1 THEN wakeup(Verbraucher);
END LOOP
Verbraucher
LOOP
IF used=0 THEN sleep(); getFromBuffer(item); used := used-1 IF used = N-1 THEN wakeup(Erzeuger); consume(item);
END LOOP
Naiver Ansatz Initial: used = 0
Umschaltung
(C) Goethe-Universität, Frankfurt
Folie 25R.Brause - Betriebssysteme: ProzeßSynchronisation
Synch. Erzeuger-Verbraucher
LösungSignal speichern. Aber: unbekannte Prozesszahl...?Semaphor einführen: belegtePlätze := 0, freiePlätze := N, mutex := 1
Erzeuger Verbraucher
LOOPproduce(item)P(freiePlätze);P(mutex);putInBuffer(item);V(mutex);V(belegtePlätze);
END LOOP
LOOPP(belegtePlätze);P(mutex);getFromBuffer(item);V(mutex);V(freiePlätze);consume(item);
END LOOP
krit. Abschnittskontrolle + Flusskontrolle durch Semaphor(C) Goethe-Universität, Frankfurt
Folie 26R.Brause - Betriebssysteme: ProzeßSynchronisation
readers/writers - Problem
Aufgabe: Koordination Lesen-Schreiben von Dateien
Erstes readers/writers-Problem (Vorrang für Leser)
Ein Leser soll nur warten, falls ein Schreiber bereits Zugriffsrecht zum Schreiben bekommen hat. Dies bedeutet, daß kein Leser auf einen anderen Leser warten muß, nur weil ein Schreiber wartet.
Problem: Schreiber wartet ewig (verhungert!)
Zweites readers/writers-Problem (Vorrang für Schreiber)
Wenn ein Schreiber bereit ist, führt er das Schreiben so schnell wie möglich durch. Wenn also ein Schreiber bereit ist, die Zugriffsrechte zu bekommen, dürfen keine neuen Leser mit Lesen beginnen. Problem: Leser wartet ewig (verhungert!)
(C) Goethe-Universität, Frankfurt
Folie 27R.Brause - Betriebssysteme: ProzeßSynchronisation
P(ReadSem); readcount:=readcount+1; IF readcount=1 THEN P(WSem) END;V(ReadSem); . . .Reading_Data(); . . .P(ReadSem); readcount:=readcount-1; IF readcount=0
THEN V(WSem) END;V(ReadSem);
Synchronisation readers/writers
Semaphor ReadSem : Semaphor für Lese-Strategie
WSem : Mutex f. Schreibvorgang
Lesen Schreiben
P(WSem); . . .Writing_Data(); . . .V(WSem);
(C) Goethe-Universität, Frankfurt
Folie 28R.Brause - Betriebssysteme: ProzeßSynchronisation
Multiprozessor-Synchronisation
Warteschlangenmanagement beim NYU-Ultracomputer (1983)FIFO-Ringpuffer im shared memory
Schutz der InSlot/OutSlot-Zeiger mittels FetchAndAdd
Puffermanagement full/empty
RingBuf[0]RingBuf[N-1]
RingBuf[1]
OutSlotInSlot
Fix
InUse
Init: 0Init: 0
(C) Goethe-Universität, Frankfurt
Folie 29R.Brause - Betriebssysteme: ProzeßSynchronisation
Multiprozessor-Synchronisation
Ein/Aushängen bei der ready-queue
Einhängen Aushängen
IF InUse >= N THEN Full:=TRUE; RETURNEND;
IF FetchAndAdd(InUse,1)>=NTHEN FetchAndAdd(InUse,-1); Full:=TRUE; RETURNEND;
MyInSlot:=FetchAndAdd (InSlot,1)MOD N;
P(InSem[MyInSlot]);RingBuf[MyInSlot]:= data;V(OutSem[MyInSlot]);
FetchAndAdd(Fix,1);
IF Fix <= 0 THEN Empty:=TRUE; RETURNEND;
IF FetchAndAdd(Fix,-1)<=0THEN FetchAndAdd(Fix,1); Empty:=TRUE; RETURNEND;
MyOutSlot:=FetchAndAdd (OutSlot,1)MOD N ;
P(OutSem[MyOutSlot]);data:= RingBuf[MyOutSlot];V(InSem[MyOutSlot]);
FetchAndAdd(InUse,-1);
(C) Goethe-Universität, Frankfurt
Folie 30R.Brause - Betriebssysteme: ProzeßSynchronisation
Frage
Warum benötigt man bei jedem einzelnen Slot einen P/V-Mechanismus? Warum reicht der FetchAndAdd-Mechanismus nicht aus?
Antwort
FetchAndAdd ist für die Flußsteuerung nötig, aber reicht nicht für den Slot-Schutz etwa bei halb gefülltem Puffer.
(C) Goethe-Universität, Frankfurt
Folie 31R.Brause - Betriebssysteme: ProzeßSynchronisation
Fehler bei Semaphoranwendung
Mögliche Fehler bei P/V-Anwendung
Vertauschung : alle sind nur gleichzeitig im krit. Abschnitt
V(mutex); ... krit. Abschnitt ...; P(mutex);
Replikation oder Weglassen: ewiges WartenP(mutex); ... krit. Abschnitt ...; P(mutex);
Falsche Reihenfolge Erzeuger-Verbraucher-Problem
Erzeuger
P(freiePlätze);P(mutex); putInBuffer(item);V(mutex);V(belegtePlätze);
ErzeugerP(mutex);P(freiePlätze); putInBuffer(item);V(mutex);V(belegtePlätze);
(C) Goethe-Universität, Frankfurt
Folie 32R.Brause - Betriebssysteme: ProzeßSynchronisation
Monitore
Lösung: Syntaktische Kapselung des kritischen Bereichs
critical region Shared s (Semaphor)region s do <statement> mutual exclusion
P(s); <statement>; V(s) conditional critical region region s when B do <statement>
Abstrakter Datentyp Monitor interner, automatischer Schutz von Daten und Methoden durch Compiler
MONITOR <name> (* lokale Daten und Prozeduren *)PUBLIC
(* Methoden der Schnittstelle nach außen *)BEGIN (*Initialisierung *)...ENDMONITOR
(C) Goethe-Universität, Frankfurt
Folie 33R.Brause - Betriebssysteme: ProzeßSynchronisation
Monitore: Erzeuger/Verbraucher
MONITOR Buffer; SchnittstelleTYPE Item = ARRAY[1..M] of BYTE;VAR RingBuf: ARRAY[1..N] of Item;
InSlot, (* 1. freier Platz *)OutSlot, (* 1. belegter Platz *)used: INTEGER;
PUBLIC PROCEDURE putInBuffer(item:Item);BEGIN ... END;PROCEDURE getFromBuffer(VAR item:Item);BEGIN ... END;
BEGIN used:=0; InSlot:=1; OutSlot:=1;END MONITOR;
Erzeuger Verbraucher
LOOPproduce(item)Buffer.putInBuffer(item)
END
LOOPBuffer.getFromBuffer(item)consume(item);
END
(C) Goethe-Universität, Frankfurt
Folie 34R.Brause - Betriebssysteme: ProzeßSynchronisation
Monitore: Flußkontrolle
Erzeuger/Verbraucher: Zusätzliche Flußkontrolle nötigCONDITION s
Signal(s)sendet Signal s an alle, die im Monitor warten
Wait(s)wartet auf ein Signal
PROCEDURE putInBuffer(item:Item) IF used=N THEN wait(frei)END; RingBuf[InSlot]:=item; used := used+1; InSlot := (InSlot+1) MOD N; signal(belegt); END putInBuffer;
PROCEDURE getFromBuffer(VAR item:Item);
IF used=0 THEN wait(belegt)END item := RingBuf[OutSlot]; used := used-1; OutSlot := (OutSlot+1) MOD N; signal(frei);END getFromBuffer;
CONDITION frei, belegt
Beispiel
(C) Goethe-Universität, Frankfurt
Folie 35R.Brause - Betriebssysteme: ProzeßSynchronisation
Monitore: Java
Konstrukt
synchronized (<expression>) <statement>
Thread wartet, bis <expression> frei ist (automat. Semaphor).
Innerhalb eines synchronized-Bereichs kann man zusätzlich mit den
Methoden wait() auf ein Signal warten, das mit notify() gesendet
wird, etwa zur Flusskontrolle.
(C) Goethe-Universität, Frankfurt
Folie 36R.Brause - Betriebssysteme: ProzeßSynchronisation(C) Goethe-Universität, Frankfurt
Prozesskommunikation
Race Conditions, Semaphore
Anwendungen
Verklemmungen
Folie 37R.Brause - Betriebssysteme: ProzeßSynchronisation
Verklemmungen
Beispiel
(C) Goethe-Universität, Frankfurt
Folie 38R.Brause - Betriebssysteme: ProzeßSynchronisation
Verklemmungen (deadlocks)
Beispiel: Datei bearbeiten und ausdrucken durch zwei Prozesse
P1 P2
Drucker
P1
hat die Datei,
will den Drucker
P2
hat den Drucker,
will die Datei
(C) Goethe-Universität, Frankfurt
Folie 39R.Brause - Betriebssysteme: ProzeßSynchronisation
Verklemmungen
Notwendige und hinreichende Bedingungen (Coffman 1971)
1. Beschränkte Belegung (mutual exclusion) semaphorgeregelter Zugang
2. Zusätzliche Belegung (hold-and-wait) hat Drucker, will Datei
3. Keine vorzeitige Rückgabe (no preemption) behält Datei bzw. Drucker
4. Gegenseitiges Warten (circular wait) P1 wartet auf P2, P2 wartet auf P1
(C) Goethe-Universität, Frankfurt
Folie 40R.Brause - Betriebssysteme: ProzeßSynchronisation
Verklemmungen
Strategien:
das Problem ignorieren,
die Verklemmungen erkennen und beseitigen,
die Verklemmungen vermeiden,
die Verklemmungen unmöglich machen.eine der Bedingungen (1)–(4) verhindern
(C) Goethe-Universität, Frankfurt
Folie 41R.Brause - Betriebssysteme: ProzeßSynchronisation
Verklemmungen
Erkennen und beseitigen Anzeichen: viele Prozesse warten, aber CPU ist idle
Prozesse müssen zu lange warten
Betriebsmittelgraph (resource allocation graph)
P1 P3 B 3
B1 B2 P4 P5
P2 B 4
Verklemmungsbedingungen erfüllt bei Zyklen im Graphen
(C) Goethe-Universität, Frankfurt
Folie 42R.Brause - Betriebssysteme: ProzeßSynchronisation
Verklemmungen
ES = Zahl der Betriebsmittel BM vom Typ SBKS = Zahl der von Prozeß K belegten BM vom Typ SCKS = Zahl der von Prozeß K geforderten BM vom Typ S
verfügbare Zahl der BM vom Typ S
Erkennungsalgorithmus für Verklemmung
(0) Alle Prozesse sind unmarkiert.(1) Suche einen unmarkierten Prozeß K, bei dem für alle
Betriebsmittel S gilt ASCKS .
(2) Falls ein solcher Prozeß existiert, markiere ihn und bilde AS:=AS+BKS .
(3) Gibt es einen solchen Prozeß ? DANN erneut (1) und (2).
(4) SONST STOP.
Wenn ein unmarkierter Prozeß ex. : Verklemmung ex !
A E BS KSSK
• Beispielrechnung(C) Goethe-Universität, Frankfurt
Folie 43R.Brause - Betriebssysteme: ProzeßSynchronisation
Verklemmungen
Beseitigen Prozesse abbrechen
z.B. verklemmten Prozess oder Prozess mit notw. BM
Prozesse zurücksetzen auf check point und verklemmenden Prozess warten lassen
Betriebsmittel entziehen von verklemmtem Prozess und warten, bis BM frei werden.
(C) Goethe-Universität, Frankfurt
Folie 44R.Brause - Betriebssysteme: ProzeßSynchronisation
Verklemmungen
Verklemmungsbedrohte Zustände vermeiden
Test: Banker-Algorithmus (Dijkstra 1965)
konservative Kreditausleihe eines Bankers:„Gib nur Kredit, wenn auch die Wünsche von anderen, vorgemerkten Kunden berücksichtigt werden können bei sichergestellter Rückzahlung“.„Verklemmung-JA“ = Verklemmungsbedrohung; sie muß nicht eintreten, wenn rechtzeitig BM zurückgegeben werden.
Vermeidung: lehne eine neue BM-Anforderung ab, wenn der Test
sagt, daß dies zu einer Verklemmung führen kann.
Aber: Realität unbekannte BM-Forderungen der Zukunft Prozesszahl + BM-Zahl wechselt Laufzeit- + Speicherintensiver Algorithmus
(C) Goethe-Universität, Frankfurt
Folie 45R.Brause - Betriebssysteme: ProzeßSynchronisation
Verklemmungen
Unmöglich machen Verhindere eine der vier Bedingungen
1. Beschränkte Belegung (mutual exclusion) BM fest nur einem Service-Prozess zuordnen
2. Zusätzliche Belegung (hold-and-wait) Nur ein BM pro Prozess (aber: lesen und drucken nicht gleichzeitig) Alle nötigen BM auf einmal anfordern (nicht bekannt und Vergeudung!) Alle BM zurückgeben vor Neuanforderung (Verwaltungsaufwand!)
3. Keine vorzeitige Rückgabe (no preemption) Vorzeitiger Prozess-Abbruch kann Inkonsistenzen verursachen
4. Gegenseitiges Warten (circular wait) Ordnungsrelation für BM einführen (Linearisierung)
(C) Goethe-Universität, Frankfurt
Folie 46R.Brause - Betriebssysteme: ProzeßSynchronisation
Verklemmungen
Beispiele OrdnungsrelationDurchnummerieren der BM derart, dass nur höhere Nummern angefordert werden (nicht immer möglich).Anordnung in einer Hierarchie
Disks
Disk 1 ... Disk n
Datei 1 ... Datei m
record 1 ... record p record 1 ... record s
Supervision der record-Belegung
Prozeß A Prozeß E Prozeß A Prozeß C
(C) Goethe-Universität, Frankfurt
Folie 47R.Brause - Betriebssysteme: ProzeßSynchronisation
Frage
Angenommen, man kann bei der BM-Belegung einen Timer (Zeituhr) aufsetzen. Welche der vier notwendigen Bedingungen für Verklemmungen sind damit nicht erfüllt?
Anwort:Bedingung 3: no premption, kein vorzeitiger Abbruch
(C) Goethe-Universität, Frankfurt
Folie 48R.Brause - Betriebssysteme: ProzeßSynchronisation(C) Goethe-Universität, Frankfurt
Prozesskommunikation
Race Conditions, Semaphore
Anwendungen
Verklemmungen
Folie 49R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation
Verbindungsanzahl
unicast multicast broadcast
···
(C) Goethe-Universität, Frankfurt
Folie 50R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: Adressierung
Eindeutige Adressierung: Qualifizierter ID mit IPAdresse = Prozeß-ID.RechnerName.Firma.Land
z.B. 5024.hera.rbi.uni-frankfurt.de
Problem: Prozeß wechselt ID bei Neustart, Aufgabe bleibt
Lösung: logische ID, nicht physische. Beispiel: „Drucker“
Prädikatsadresse: Spezifikationen als Adresse(IF 386-CPU AND Java_installiert AND Drucker)= True: fühle dich angesprochen, sonst nicht.
Arbeitsverteilung!
(C) Goethe-Universität, Frankfurt
Folie 51R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation
Verbindungsorientierte Kommunikation
openConnection(Adresse)
Feststellen, ob der Empfängerexistiert und bereit ist:Aufbau der Verbindung
send (Message)/receive(Message)
Nachrichtenaustausch;
closeConnection Leeren der Nachrichtenpuffer,Beenden der Verbindung
Verbindungslose Kommunikationsend (Adresse, Message)/ receive(Adresse, Message)
(C) Goethe-Universität, Frankfurt
Folie 52R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: Mailboxen
Mailbox = Nachrichtenpufferz.B. TYPE Mailbox = RECORD
SenderQueue : tList;EmpfängerQueue : tList;MsgQueue : tList;MsgZahl : INTEGER;
einhängen(tMsg): PROCEDURE;aushängen(tMsg): PROCEDURE;
END
Message = Kopf + Daten TYPE tMsg = RECORD
EmpfängerAdresse: STRING;AbsenderAdresse: STRING;NachrichtenTyp: tMsgTyp;SequenzNummer : INTEGER;Länge: CARDINAL;Data: POINTER TO tBlock; // oder inline
data END;
Zugriff mit Semaphoren schützen!
für Flußkontrolle
Kopf
(C) Goethe-Universität, Frankfurt
Folie 53R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: Pipes
Unix pipe() unidirektionale Kommunikation„ Programm1 | Programm2 | .. | Programm N “
Windows NT CreatePipe() Bidirektionale pipes
Globale Kommunikation: named pipes
write()Programm 1
read() Programm 2
(C) Goethe-Universität, Frankfurt
Folie 54R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: Signale
Problem: Synchrones Warten blockiert Prozesse
Abhilfe: Benachrichtigung durch asynchrone Signale(Software-Interrupts)
• Aufsetzen der Reaktion auf ein Signal, z.B. in UNIX mit sigaction(ISR)
• Abarbeiten des Hauptprogramms
• Bei Signaleintritt: Abarbeiten der angegebenen ISR
• Weiterarbeiten im Hauptprogramm
(C) Goethe-Universität, Frankfurt
Folie 55R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: Signale
Implementierung von Semaphoroperationen mit Signalen
TYPE Semaphor = RECORD besetzt : BOOLEAN; frei : SIGNAL;END;
PROCEDURE P(VAR S:Semaphor);BEGIN
IF S.besetzt THEN waitFor(S.frei) END;S.besetzt:= TRUE;
END P; PROCEDURE V(VAR S:Semaphor);BEGIN
S.besetzt:= FALSE;send(S.frei)
END V;
Unterbrechung verhindern durch Sperren des Signal-Interrupt !?
(C) Goethe-Universität, Frankfurt
Folie 56R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: atomic broadcast
Problem: Synchronisierung von Globaldaten (Systemtabelle, ...)
Lösung: Atomarer Rundspruch (atomic broadcast) Endliche Übertragungszeit Nachricht an alle oder keinen Gleiche Nachrichten-Reihenfolge
Implementierung: konsistente Message-Reihenfolge
Konsistenz durch Nachrichten an alle, auch sich selbst!
Empfänger-prozesse
Sender · · ·
Globaldaten
143
143
143
mailbox
(C) Goethe-Universität, Frankfurt
Folie 57R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation
ProgrammsynchronisationRendez-vous-Konzept (Ada)
Warten ohne Pufferung aufeinander
Senderprogramm Empfängerprogramm
...
send(Empfänger,Msg);
...
...
receive(Sender,Msg)
...
(C) Goethe-Universität, Frankfurt
Folie 58R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: Synchronisation
Guarded Commands (Dijkstra 1975)
Konstrukte:
DO unendl. loopC1 command1C2 command2
....OD
IF Auswahl IFC1 command1 (a > b) print „größer / gleich“C2 command2 (a < b) print „kleiner“
....FI FI
(C) Goethe-Universität, Frankfurt
Folie 59R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: Synchronisation
Kommunizierende Sequentielle Prozesse CSP (Hoare 1978)
Konstrukte: s A Auf ein Ereignis s folgt der Zustand A P = (s A) Wenn s kommt, so wird Zustand A erreicht, und P
nimmt A an.
Für den parallelen Fall ist P = (s1 A | s2 B | ... | sn D)
Wenn s1 kommt, nimmt P den Wert A an. Wenn s2 kommt, dann
B, usw.
(C) Goethe-Universität, Frankfurt
Folie 60R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: Synchronisation
CSP in OCCAM (INMOS 1988)
Konstrukte:Kanal!data1 send(Kanal,data1)Kanal?data2 receive(Kanal,data2)
Bei Rendez-vous: data2 := data1
PAR cmd1 parallele Ausführungcmd2
SEQcmd1 sequentielle Ausführungcmd2
ALTcmd1 einer davon wird ausgeführtcmd2
(C) Goethe-Universität, Frankfurt
Folie 61R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: Synchronisation
Beispiel: Erzeuger – Verbraucher, Code für Puffer
producer!buffer
producer?buffer
consumer
consumer?more
Erzeuger Puffer Verbraucher
producerconsumer!buffer consumer?buffer
consumer!more
CHAN OF items producer, consumer : INT in, out : SEQ in :=0 out:=0 WHILE TRUE ALT IF (in<out+10)AND(producer?buffer(in REM 10)) in:=in+1 IF (out<in) AND (consumer?more) consumer!buffer(out REM 10) out:=out+1
(C) Goethe-Universität, Frankfurt
Folie 62R.Brause - Betriebssysteme: ProzeßSynchronisation
Prozeßkommunikation: Synchronisation
Synchronisation durch Kommunikation
putInBuffer(item) send(consumer,item)Item internen Puffer, geregelt mit P() und V()
getFromBuffer(item) receive(producer,item) interner Puffer Item, geregelt mit P() und V()
Erzeuger
LOOP produce(item); send(consumer,item);
END
Verbraucher
LOOP receive(producer,item); consume(item);
END
(C) Goethe-Universität, Frankfurt
Recommended