Modul: B-BS Betriebssysteme SS 2014 Prof. Dr. Rüdiger Brause Adaptive Systemarchitektur Institut für Informatik Fachbereich Informatik und Mathematik

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


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)



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)



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)



Synchronisierung: zweiter Versuch

Verbesserung: Zugang nur blockiert beim Aufenthalt in krit. Abschnitt


WHILE drin2=TRUE DO NoOp END;

drin1 := TRUE;

WHILE drin1=TRUE DO NoOp END;

drin2 := TRUE;


drin1 := FALSE; drin2 := FALSE;

. . . . . .

Problem: Initialisierung drin1=drin2=False keine mutual exclusion!drin1=True, drin2=False P2 ist blockiert ohne Sinn



Synchronisierung: Lösung

Peterson 1981Verbesserung: eine globale Variable, 2 Prozeß-Zustandsvariable.

Initial Interesse1 = Interesse2 = FALSE


Interesse1 := TRUE; Interesse2 := TRUE; dran := 1;WHILE dran=1 AND Interesse2=TRUEDO NoOp END;

dran := 2;WHILE dran=2 AND Interesse1=TRUEDO NoOp END;


Interesse1 := FALSE; Interesse2 := FALSE;

. . . . . .



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


P(s) P(s)

V(s) V(s)

. . . . . .

z :=z+1; WriteInteger(z)z :=z+1; WriteInteger(z)

warten

freigeben



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



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;



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 !



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



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



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,



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.



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



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)



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:


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)



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





Anwendungen

Verklemmungen


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



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



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


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!)



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);



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



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);



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.



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);



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



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



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



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.





Anwendungen

Verklemmungen


Verklemmungen

Beispiel



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



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



Verklemmungen

Strategien:

das Problem ignorieren,

die Verklemmungen erkennen und beseitigen,

die Verklemmungen vermeiden,

die Verklemmungen unmöglich machen.eine der Bedingungen (1)–(4) verhindern



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



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


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.



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



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)



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



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





Anwendungen

Verklemmungen


Prozeßkommunikation

Verbindungsanzahl

unicast multicast broadcast

···



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!




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)



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



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



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



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 !?



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




ProgrammsynchronisationRendez-vous-Konzept (Ada)

Warten ohne Pufferung aufeinander

Senderprogramm Empfängerprogramm

...

send(Empfänger,Msg);

...

...

receive(Sender,Msg)

...



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




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.




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




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




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


Documents

Modul: B-BS Betriebssysteme SS 2014 Prof. Dr. Rüdiger Brause Adaptive Systemarchitektur Institut für Informatik Fachbereich Informatik und Mathematik