24
VO Betriebssysteme 1 Kapitel IV Prozesssynchronisation VO Betriebssysteme 2 Motivation Zentrale Bedeutung der Verwaltung von Prozessen und Threads Mehrprogrammbetrieb: mehrere Prozesse in einem sequentiellen Einprozessorsystem Mehrprozessorbetrieb: mehrere Prozesse in einem Mehrprozessorsystem verteilte Verarbeitung: Verwaltung mehrerer Prozesse, die auf mehreren verteilten Computersystemen ausgeführt wird. Grundlegend für die Entwicklung von Betriebssystemen: Nebenläufigkeit

Kapitel IV - dps.uibk.ac.attf/lehre/ss04old/bs/vorlesungen/ProzessSyncIV-2...VO Betriebssysteme 3 Nebenläufigkeit zgleichzeitige Ausführung von Prozessen oder Threads zNebenläufigkeit

  • Upload
    lequynh

  • View
    214

  • Download
    0

Embed Size (px)

Citation preview

VO Betriebssysteme

1

Kapitel IV

Prozesssynchronisation

VO

Bet

riebs

syst

eme

2

MotivationZentrale Bedeutung der Verwaltung von Prozessen undThreads

Mehrprogrammbetrieb: mehrere Prozesse in einem sequentiellen Einprozessorsystem

Mehrprozessorbetrieb: mehrere Prozesse in einem Mehrprozessorsystem

verteilte Verarbeitung: Verwaltung mehrerer Prozesse, die auf mehreren verteilten Computersystemen ausgeführt wird.

Grundlegend für die Entwicklung von Betriebssystemen:

Nebenläufigkeit

VO

Bet

riebs

syst

eme

3

Nebenläufigkeitgleichzeitige Ausführung von Prozessen oder Threads

Nebenläufigkeit ist in 3 Bereichen von BedeutungMehrprogrammbetrieb• Verarbeitungszeit wird auf mehrere Prozesse verteilt.

strukturierte Anwendungen• Anwendungen, die sich als Gruppe von nebenläufigen

Prozessen strukturieren und programmieren lassen.Betriebssystemstruktur• Betriebssysteme werden häufig als Gruppe von

nebenläufigen Prozessen oder Threads implementiert.

VO

Bet

riebs

syst

eme

4

Nebenläufigkeit: zentrale Konzepte

Kommunikation zwischen Prozessengemeinsame Nutzung von RessourcenWettbewerb um Ressourcen

Synchronisierung der Aktivitäten mehrerer ProzesseZuteilung von Prozessorzeit zu Prozessen.

VO

Bet

riebs

syst

eme

5

Gemeinsame Ressourcen• Nebenläufige (parallele) Prozesse können sich gegenseitig beeinflussen

• gemeinsamer Adressbereich • gemeinsame Ressourcen (Files, Devices, etc.)

• Dateninkonsistenzen können entstehen.• Ergebnisse können von der Ausführungsreihenfolge der Befehle

abhängen.

• Zugriffe auf gemeinsame Ressourcen und Daten müssen daher kontrolliert und konsistent erfolgen.

• Optimale Ressourcenzuteilung ist sehr schwierig.

• Programmierfehler schwierig zu lokalisieren und zu reproduzieren.

VO

Bet

riebs

syst

eme

6

Erzeuger/Verbraucher-Problem: gemeinsamer Puffer

Programm für Erzeuger:

Repeat

produziere Datum in nextp

while counter == n;

buffer[in]=nextp;

in = (in+1) % n;

counter++;

Until false;

Funktioniert diese Anwendung?

Programm für Verbraucher:

Repeat

while counter == 0;

nextc = buffer[out];

out = (out+1) % n;

counter--;

verarbeite Datum in nextc;

Until false;

VO

Bet

riebs

syst

eme

7

Probleme mit Erzeuger/Verbraucher-Problem

Betrachte 3-Adresscode für Variable counter

Counter Inkrement Counter Dekrement

reg1 = counter reg2 = counterreg1 = reg1 + 1 reg2 = reg2 – 1counter = reg1 counter = reg2

Betrachte eine bestimmte zeitliche Sequenz dieser Operationen:

T0 Erzeuger reg1 = counter {reg1 = 5}T1 Erzeuger reg1 = reg1 + 1 {reg1 = 6}T2 Verbraucher reg2 = counter {reg2 = 5}T3 Verbraucher reg2 = reg2 - 1 {reg2 = 4}T4 Erzeuger counter = reg1 {counter = 6}T5 Verbraucher counter = reg2 {counter = 4} Fehler !!!

Race-Condition

VO

Bet

riebs

syst

eme

8

Analyse des Erzeuger/Verbraucher-Algorithmus

Separat betrachtet, sind die Routinen Erzeuger und Verbraucher korrekt.

Wenn beide Routinen parallel ausgeführt werden, kann der Gesamtalgorithmus fehlerhaft sein.• Vermischung der Assembly-Instruktionen• Grad der Vermischung hängt vom Scheduling ab.

Wenn counter++ und counter– nicht atomar ausgeführt werden, ist das Resultat unvorhersehbar

Race Condition

VO

Bet

riebs

syst

eme

9

Terminologie (1)Race Condition• Die Ausführungsreihenfolge von Befehlen beeinflusst

das Resultat.• Resultat hängt davon ab, welcher Prozess zum Schluss

ausgeführt wird.• Wichtige Fälle: gemeinsame Daten

ZählerWarteschlangen

Um Race Conditions zu vermeiden, müssen nebenläufige Prozesse synchronisiert werden.

VO

Bet

riebs

syst

eme

10

Terminologie (2)

Wechselseitiger Ausschluss (Mutual Exclusion)• Nur jeweils 1 Prozess kann gemeinsame Ressourcen zu

jedem bestimmten Zeitpunkt verwenden. Ausnahme: mehrere Leser und ein Schreiber.

Kritische Region• Programmregion, die gemeinsame Daten ändert oder

verwendet.Benötige wechselseitigen Ausschluss für eine kritische Region.Keine Änderung von Daten während einer Leseoperation.

VO

Bet

riebs

syst

eme

11

Kritische Region

n Prozesse streben Zugriff auf gemeinsame Daten an.

Jeder Prozess hat eine Code-Region (kritische Region) in der auf die gemeinsamen Daten zugegriffen wird.

Problem: Zu jedem Zeitpunkt darf immer nur 1 Prozess in seiner kritischen Region sein.Prozess kann in seiner kritischen Region unterbrochen werden (Interrupt, Context Switching, ...)• Kein anderer Prozess darf in die kritische Region• Warte bis ursprünglicher Prozess Exekution fortsetzt

und kritische Region verlässt.

VO

Bet

riebs

syst

eme

14

Realisierung von kritischen Regionen (1) Annahmen: • Prozesse exekutieren mit einer Geschwindigkeit, die größer als Null

ist.• Keine Annahme zur relativen Geschwindigkeit unter den Prozessen.

Realisierung einer kritischen Region muss folgende Eigenschaftenerfüllen.• Wechselseitiger Ausschluss

Nur ein Prozess kann sich zu jedem Zeitpunkt in seiner kritischen Region befinden.

• Fortschreiten des ProgrammsKein Prozess außerhalb der kritische Region darf einen anderen Prozess beim Eintreten in seine kritische Region behindern.

• Begrenzte WartezeitenProzesse können sich nicht unbegrenzt lange in ihrer kritischen Region befinden, während andere Prozesse darauf warten, in die kritische Region zu gelangen.

VO

Bet

riebs

syst

eme

15

Realisierung von kritischen Regionen (2)

Software• keine Annahmen für korrektes Funktionieren.• Lösung muss für alle Szenarien funktionieren.

Hardware• spezielle atomare Maschineninstruktionen

Betriebssystem• Das Betriebssystem stellt spezielle Funktionen und

Datenstrukturen zur Verfügung.• Semaphore, Monitore, etc.

VO

Bet

riebs

syst

eme

16

SoftwarelösungenFür nebenläufige Prozesse auf • Einprozessorsystem • Multiprozessorsystem mit gemeinsamem Speicher

Lösung vorerst für 2 Prozesse• wird dann auf n Prozesse verallgemeinert.

Synchronisierung durch gemeinsame Variablen

Busy Waiting: • Warten auf das Eintreten einer Bedingung durch permanentes Testen

benötigt CPU-Zeit• Problem, wenn mehrere Prozesse die CPU verwenden wollen, da CPU

bei busy waiting blockiert ist.

VO

Bet

riebs

syst

eme

17

Kritische RegionDekker Algorithmus 1

Dekker Algorithmus 1 für 2 ProzesseVerwende gemeinsame Variable turn (Wert ist 1 oder 0)Prozess i kann kritische Region betreten, wenn turn = i wechselnde Nutzung des kritischen Abschnitts (dominiert durch langsameren Prozess)wenn 1 Prozess ausfällt, ist der andere Prozess dauerhaft blockiert

Prozess 0: Prozess 1:

repeat repeat

while turn != 0; while turn != 1;

// kritische Region // kritische Region

turn = 1; turn = 0;

// nicht-kritische Region // nicht-kritische Region

until false until false

Wechselseitiger Ausschluss ist gegeben. Dennoch funktioniert dieser Algorithmus nicht, da Fortschreiten des Programms nicht gewährleistet ist. Prozess 0 stoppt Prozess 1, wenn turn == 0 und Prozess 0 befindet sich in nicht-kritischer Region.

VO

Bet

riebs

syst

eme

18

Dekker Algorithmus 1: ProblemeName des Prozesses, der in kritischen Abschnitt eintreten

kann, wird gespeichert.

Besser: Jeder Prozess sollte Schlüssel für kritischen Abschnitt haben.Bei Ausfall eines Prozesses kann der andere Prozess in den kritischen Abschnitt eintreten.

führe booleschen Vektor ein: flag[2]Jeder Prozess kann das Flag des anderen überprüfen aber nicht ändern.

Dekker Algorithmus 2

VO

Bet

riebs

syst

eme

19

Verwende Prozess-Array, um festzulegen, welcher Prozess kritische Region betreten möchte.flag[i] = true bedeutet, dass Pi bereit ist, in kritische Region zu gelangen.

bool flag[i]=false;repeat

flag[i] = true;while (flag[j]);// kritische Regionflag[i] = false;// nicht kritische Region

until false;Wechselseitiger Ausschluss gegeben aber nicht Fortschreiten des Programms.Beide Prozesse könnten Flag zugleich auf true setzen.Wenn Prozess innerhalb der krit. Region ausfällt, dann ist auch der andere Prozess blockiert.

Kritische Region:Dekker Algorithmus 2 (1)

Beide Prozessekönnten gleichzeitig

hier sein.

VO

Bet

riebs

syst

eme

20Was passiert, wenn 2 Anweisungen vertauscht werden ?flag[i] = true heißt, dass Pi bereit ist, in kritische Region zu gelangen.

bool flag[i]=false;

repeat

while (flag[j]);flag[i] = true;// Kritische Region

flag[i] = false;

// nicht kritische Region

until false;

Wechselseitiger Ausschluss ist nicht mehr garantiert.

Kritische Region:Dekker Algorithmus 2 (2)

Diese beiden Anweisungen wurden vertauscht.

VO

Bet

riebs

syst

eme

21

Dekker Algorithmus 2: ProblemeProzesse setzen Ihren Status fest, ohne den Status des

anderen Prozesses zu berücksichtigen.

Jeder Prozess besteht darauf, in die krit. Region einzutreten Verklemmung möglich

Lösung: Jeder Prozess setzt Flag um anzuzeigen, dass er in die krit. Region eintreten möchte.Reihenfolg für das Eintreten in die krit. Region wird festgelegt.

VO

Bet

riebs

syst

eme

22

Kritische Region:Dekker Algorithmus 3

Kombination aus Algorithmus 1 mit Algorithmus 2Initialisierung: flag[0] = flag[1] = false; turn = 1 (oder 0);

Diesmal funktioniert es.• Wechselseitiger Ausschluss, Fortschreiten des Programms und

begrenzte Wartezeiten (implizit) sind gegeben.

// process ibool flag [2];int turn;repeat

flag[i] = true;turn = j;while (flag[j] && turn == j);// kritische Regionflag[i] = false;// nicht kritische Region

until false;

VO

Bet

riebs

syst

eme

23

Kritische Region für mehr als 2 ProzesseBakery Algorithmus (1)

N Prozesse möchten in ihre kritische Region eintreten.

• Jeder Prozess Pi bekommt eine Nummer number[i] – aktuelle Nummer ist stets größer oder gleich der vorher vergebenen Nummer.

• Prozess mit kleinster Nummer kommt zuerst in seine kritische Region.

• Algorithmus kann nicht ausschließen, dass mehrere Prozesse die gleiche Nummer bekommen. • Beispiel für Nummerierung: 1,2,3,3,3,4,4,5,6,6,6,7

• Wenn Prozesse Pi und Pj die gleiche Nummer bekommen und i < j, dann kommt Pi vor Pj in seine kritische Region.

• Prozesse betreten ihre kritische Region basierend auf First-Come-First-Served Prinzip.

VO

Bet

riebs

syst

eme

24

Kritische Region für mehr als 2 ProzesseBakery Algorithmus (2)

Verwende folgende Notation (lexikographische Reihenfolge) für Prozess i mit Tupel (number[i],i):

gemeinsame Variablenboolean choosing[n] mit false initialisiertint number[n] mit 0 initialisiert

(a,b) < (c,d) <==> (a < c) OR (a == c AND b < d)

VO

Bet

riebs

syst

eme

25

Bakery Algorithmusrepeat // aus der Sicht von Prozess i

choosing[i]= true; // choosing mit false und number mit 0 initialisiertnumber[i]= max(number[0],…,number[n-1])+1;choosing[i] = false;for j = 0 to n-1

do beginwhile choosing[j] do no-op;while number[j] != 0 and (number[j],j) < (number[i],i) do no-op;

do endfor end

number[i]= 0;

until false;

kritische Region

VO

Bet

riebs

syst

eme

26

HardwarelösungenInterrupt Disabling

Wird für Einprozessorsysteme verwendet.

Mehrere Prozesse verwenden die CPU im Time-Sharing-Modus.

Prozess behält die CPU solange bis ein Systemaufruf getätigt wird oder einInterrupt erfolgt.

Durch Verhindern von Interrupts können kritische Regionen realisiert werden.

BS bietet die Möglichkeit Interrupts ein- bzw. auszuschalten.

Nachteile:• Verlust von Performance durch Ausschalten von Time-Sharing-Modus• Funktioniert nicht für Multiprozessorsysteme, da sich pro Prozessor ein

Prozess in der kritischen Regionen befinden könnte.

repeatdisable interruptscritical sectionenable interruptsremainder

forever

VO

Bet

riebs

syst

eme

27

Hardwarelösungen Test and Set (1)

Mehrprozessorfähige HW-Lösung für eine kritische Region

Hardwarebefehl, der zwei Aktionen atomar (ohne Unterbrechung bzw.Interrupt) ausführt.

Funktion testset wird atomar ausgeführt.

function testset (var i: integer): boolean;begin

if i = 0 thenbegin

i := 1;testset := true;

end;else testset := false;

end.

VO

Bet

riebs

syst

eme

28

Hardwarelösungen Test and Set (2)

Realisierung einer kritischen Region mithilfe von Test und Set.

Es wird eine gemeinsame Variable (befindet sich im gemeinsamen Speicher) von allen Prozessen verwendet.

Maximal 1 Prozess kann sich in kritischer Region befinden

Alle anderen Prozesse, die in die kritische Region wollen, befinden sich imBusy-Waiting-Modus.

Nachteil: Starvation von Prozessen ist möglich. Auswahl eines bestimmten Prozesses bei Eingang der kritischen Region ist beliebig.

var shared: integer;shared := 0; // globale Initialisierung

while not testset (shared) do nothing;// kritische Region

shared := 0;// remainder

VO

Bet

riebs

syst

eme

29

HardwarelösungenTest und Set (3)

Verwendung von speziellen Maschinenbefehlen für die Realisierung von kritischen Regionen hat Vor- und Nachteile

Vorteile• Kann für beliebige Anzahl von Prozessen für Ein- und

Mehrprozessorsysteme (mit gemeinsamem Speicher) verwendet werden.

• einfache Lösung• Mehrere kritische Regionen (durch eindeutige Variablen

definiert) können unterstützt werden.

VO

Bet

riebs

syst

eme

30

HardwarelösungenTest und Set (4)

Nachteile• Busy waiting ist eine Verschwendung der CPU.• Starvation ist möglich.• Deadlock ist möglich.

1. P1 kommt in kritische Region über testset Operation2. P1 wird durch Interrupt unterbrochen.3. P2 mit höherer Priorität als P1 bekommt die CPU und

möchte in kritische Region.4. P2 kann aber erst in die kritische Region, wenn P1

diese verlassen hat.5. P2 geht daher in Busy-Waiting Modus.6. P1 bekommt die CPU nicht wegen geringerer Priorität

als P27. P1 und P2 befinden sich in einem Deadlock.

VO

Bet

riebs

syst

eme

31

BetriebssystemlösungenSemaphore

Wegen der Probleme mit Software- und Hardwarelösungen für die Realisierung von kritischen Regionen hat man sich nach anderen Mechanismen umgesehen, die vom Betriebssystem unterstützt werden.

Alternative die vom BS unterstützt wird: SEMAPHORE• Integer Variable s (Wert von s ist immer >= 0.)• Zugriff auf Semaphore-Variable durch 2 atomare Operationen

Diese Semaphore-Operationen bewirken Busy Waiting.• Verschwendung von CPU-Cycles

wait:while s <= 0;s=s-1;

signal:s=s+1;

VO

Bet

riebs

syst

eme

32

SemaphoreVerwendung von Semaphoren für die Realisierung von kritischen

Regionen:

wait(S);

critical section

signal(S);

non-critical section

VO

Bet

riebs

syst

eme

33

Semaphor ohne Busy WaitingSemaphor ohne Busy Waiting wird über eine Datenstruktur

realisiert.

Ein Prozess, der auf ein Semaphor S wartet, wird in die Liste der Prozesse (blocked queue) von S abgelegt.

Die signal Operation entfernt einen Prozess aus dieser Liste und stellt ihn in die Ready -Warteschlange.

type semaphore = recordvalue: integer;L: list of processes;end;

VO

Bet

riebs

syst

eme

34

Semaphore-Operationen (1)Semaphore müssen mit einem positiven Wert (>= 0) initialisiert

werden.wait und signal sind atomare Operationen (realisiert durch Test und

Set)

init (S, val): S.value := val; S.queue := leere Liste;

wait (S): S.value := S.value - 1;if S.value < 0then add this process to S.queue

and block it;

signal (S): S.value := S.value + 1;if S.value <= 0then remove a process P from S.queue

and place it on the ready queue;

VO

Bet

riebs

syst

eme

35

Semaphore-Operationen (2)S.value >= 0 bestimmt die Anzahl der Prozesse, die hintereinander ein

wait ausführen können, ohne warten zu müssen.

Der Absolutbetrag eines negativen S.value gibt die Anzahl der Prozesse an, die in der Warteschlange von S blockierend warten.

Mit der neuen Definition von Semaphore-Operationen blockieren wartende Prozesse in blocked Queues anstatt sich im Busy-Waiting-Modus zu befinden.

• Status des Prozesses wird auf Waiting gesetzt.• Kontrolle geht an den CPU-Scheduler, der einem anderen

Prozess die CPU zuteilen kann.

VO

Bet

riebs

syst

eme

36

Verwendung von SemaphorenBeispiel 1: Kritische Region

Beispiel 2: Prozess 2 soll mit Ausführung von S2 erst dann beginnen, nachdem Prozess 1 die Anweisung S1 ausgeführt hat.• Initialisierung: synch=0 Prozess 1

S1

signal(synch)

Prozess 2

wait(synch)

S2

Repeat

wait(mutex);

// kritische Region

signal(mutex)

// nicht kritische Region

until false

VO

Bet

riebs

syst

eme

37

Leser/Schreiber ProblemEin klassisches Synchronisationsproblem

Parallel exekutierende Prozesse teilen sich gemeinsame Daten (Shared Data).

Einige Prozesse lesen Daten, andere lesen oder schreiben Daten.• Beliebige Zahl von Leser kann Daten simultan lesen.• Nur ein Schreiber kann Daten zu einem bestimmten

Zeitpunkt schreiben.• Kein Leser kann Daten lesen, wenn Schreiber Daten

schreibt.

Leser und Schreiber können verschiedene Prioritäten haben.

VO

Bet

riebs

syst

eme

38

Leser hat Priorität

writer()

{

repeat

wait(wsem);

WRITEUNIT;

signal(wsem);

forever;

};

reader()

{ readcount=0; x =1; wsem = 1;

repeat

wait(x);

readcount=readcount+1;

if readcount == 1 then wait(wsem);

signal(x);

READUNIT;

wait(x);

readcount=readcount-1;

if readcount == 0 then signal(wsem);

signal(x);

forever; }

VO

Bet

riebs

syst

eme

39

Leser hat Priorität: Kommentare

readcount: Wie viele Leser gerade Daten lesen.

Verwende Semaphore x für exklusiven Zugriff aufreadcount.

Verwende Semaphor wsem für exklusiven Schreibzugriff.

Leser hat Priorität.

Schreiber hat nur dann Zugang zu Daten, wenn es keine Leser gibt.• Z.B. readcount = 0, signal(wsem) wird ausgeführt.

Schreiber können eventuell nie auf Daten zugreifen.

VO

Bet

riebs

syst

eme

40

MonitorProgrammiersprachenkonstrukt zur Koordinierung von Prozessen

bestehend aus• lokalen Variablen, die den Zustand des Monitors spezifizieren.• Prozeduren, die lokale Variablen abfragen oder verändern können.

• Prozesse kommen nur über diese Prozeduren in den Monitor.• Maximal 1 Prozess im Monitor zu jedem beliebigem Zeitpunkt

• Initialisierungs-Code

Syntax eines Monitors:Monitore bieten äquival.Funktionalität wie Semaphore jedoch mitbesserem Überblick.

type monitor-name = monitorvariable declarationsprocedure entry P1(…);

begin … end;…

procedure entry Pn(…);begin … end;

begininitialization code

end.

VO

Bet

riebs

syst

eme

41

Monitor mit Condition Variables Monitor ermöglicht wechselseitigen Ausschluss (Mutual Exclusion).

Bisheriges Monitorkonzept kann nicht alle Synchronisationsarten umsetzen.

Benötige neuen Synchronisationsmechanismus: Condition Variables• Syntax von Condition Variables

• Condition Variablen können nur im Zusammenhang mit 2 Operationen verwendet werden: signal und wait

• x.signal setzt einen Prozess fort, der nach Ausführung von x.waitblockiert ist.

• Falls kein Prozess durch x.wait wartet, dann induziert x.signal keinerlei Veränderung (keine speichernde Wirkung im Gegensatz zu Semaphoren).

• Der Prozess, der x.signal ausführt, wartet bis der freigesetzte Prozess den Monitor wieder verlässt.

var x,y: condition;

x.wait; // Prozess ist blockiert, bis ein anderer Prozess

x.signal; // x.signal aufruft. Condition Variable x wird true.

VO

Bet

riebs

syst

eme

43

Monitor: Erzeuger/Verbraucher-Problem

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

append (v):if (cnt = K) notfull.wait;b[In] := v;In := (In + 1) mod K;cnt := cnt + 1;notempty.signal;

take (v):if (cnt = 0) notempty.wait;v := b[Out];Out := (Out + 1) mod K;cnt := cnt - 1;notfull.signal;

type ErzeugerVerbraucher = monitor

VO

Bet

riebs

syst

eme

44

Dining Philosophers Problemklassisches Problem der Synchronisation

5 Philosophen denken und essen.

Jeder braucht zum Essen zwei Essstäbe (ES)

Jeder Philosoph kann nur 1 ES zu einem bestimmten Zeitpunkt aufheben.

gesucht: Lösung ohne Deadlock (Verklemmung)und Starvation (Verhungern)

VO

Bet

riebs

syst

eme

45

Dining Philosophers Problem: Lösungsversuch 1

Jeder Philosoph kann als Prozess realisiert werden.

Jeder ES wird durch ein Semaphor kontrolliert.

chopstick: array[0..4] ofsemaphore;

forall i in [0..4]init (chopstick[i], 1);

Prozess Pi:repeat

wait(chopstick[i]);wait(chopstick[i+1 mod 5]);eat;signal(chopstick[i]);signal(chopstick[i+1 mod 5]);think

until false

Diese Implementierung kann zu einer Verklemmung führen, wenn alle Philosophen gleichzeitig einen ES aufnehmen.

VO

Bet

riebs

syst

eme

46

Dining Philosophers Problem: Lösung 1Verklemmungen können vermieden werden:

Verwende zusätzliches Semaphor, um maximal 4 Philosophen gleichzeitig das Aufnehmen eines ES zu erlauben.

Ein Philosoph darf nur dann einen ES (in einer kritischen Region) aufnehmen, wenn beide verfügbar sind.

asymmetrische Lösung: Philosoph mit gerader ID nimmt zuerst linkes und dann rechtes Essstäbchen auf. Philosoph mit ungerader ID geht in umgekehrter Reihenfolge vor.

VO

Bet

riebs

syst

eme

47

Dining Philosophers Problem: Lösung 2

type dining-philosophers = monitorvar state : array [0..4] of (thinking, hungry, eating);var self : array [0..4] of condition;

procedure entry pickup (i:0..4); begin

state[i] := hungry;test(i);if state[i] != eating then self[i].wait;

end;

procedure entry putdown (i:0..4);begin

state[i]:=thinking;test(i+4 mod 5);test(i+1 mod 5);

end;

procedure test (k:0..4); begin

if state[k+4 mod 5] != eatingand state[k] = hungryand state[k+1 mod 5] != eatingthen begin

state[k] := eating;self[k].signal;end;

end;

beginfor i:= 0 to 4

do state[i] := thinking;end.

VO

Bet

riebs

syst

eme

48

Dining Philosophers ProblemLösung 2: Anmerkungen

Erlaube Philosophen nur dann einen ES aufzunehmen, wenn sein linker und rechter ES gerade nicht benutzt werden.

Condition Variable self wird verwendet, um das Essen für einen Philosophen zu verzögern, wenn ihm nicht 2 ESe zur Verfügung stehen.

Philosoph i muss die Operationen pickup und putdown in der folgenden Reihenfolge durchführen:

Deadlocks werden jetzt verhindert.

Allerdings kann ein Philosoph nach wie vor verhungern.

dp.pickup(i);eat

dp.putdown(i);

VO

Bet

riebs

syst

eme

49

Zusammenfassung (1)Anforderungen an nebenläufige Prozesse

konsistenter Zugriff auf gemeinsame Datenvorgegebene Reihenfolge von Aktionen

Konsistenz durch wechselseitigen Ausschluss

Reihenfolge durch Synchronisierung mit Bedingungen

Kritischer AbschnittAktionen, die gemeinsame Daten manipulierenmit Konstrukten zur Synchronisierung gesichert

VO

Bet

riebs

syst

eme

50

Zusammenfassung (2)Sicherung des kritischen Abschnitts

Softwarelösungen (z.B. Dekker)Test and SetUnterstützung durch Betriebssystem

Semaphoreinit, wait und signal

MonitorZusammenfassung von gemeinsamen Objekten, Zugriffsfunktionen und Bedingungsvariablen