Beispiele

Beispiele
Readers-Writers-Problem
Dining Philosophers
Asynchrone Iteration

Beispiele

Readers-Writers-Problem

Gegeben

reader: Können konkurrent (gleichzeitig, überlappend) zugreifen.
writer: Benötigen exklusiven Besitz der Ressource.

Gesucht

Offensichtliche Lösung in Ada95:
Ressource = protected object mit
procedure write(...) $\Rightarrow$ exklusiv, darf Zustand ändern
function read(...) $\Rightarrow$ nicht exklusiv. Aber schließt gleichzeitiges write aus.

Illustration: Ressource = gemeinsame Variable


-----------------------------------

- Readers-Writers Demo, mit simpler integer-Variablen

-

- Version 1: protected object, => no preference for writer,

-                                 no potentially blocking ops

-----------------------------------






with Stringpack; use Stringpack;

procedure Readers_Writers1 is






protected Variable is

procedure Write (X : Integer);

function Read return Integer;

private
V : Integer := 0; - na ja

end Variable;






protected body Variable is

procedure Write (X : Integer) is

begin V := X; end Write;

function Read return Integer is

begin return V; end Read;

end Variable;






task type Reader;

task body Reader is

Local_X : Integer;

begin

for I in 1..100000 loop

Local_X := Variable.Read;

end loop;

Print(» " & Local_X);

end Reader;






task type Writer;

task body Writer is

Local_X : Integer := 1;

begin

for I in 1..100000 loop

Variable.Write(Local_X);

Local_X := Local_X + 1;

end loop;

end Writer;






Anz_R, Anz_W : Natural;






begin






Print("give #readers, #writers");
Anz_R := Getint; Anz_W := Getint;

declare

R : array(1..Anz_R) of Reader;

W : array(1..Anz_W) of Writer;

begin null; end;






end Readers_Writers1;






-----------------------------------

26 pohlmann@mandrill:readers_writers1

give #readers, #writers

3 1

> 97951

> 100000

> 100000

27 pohlmann@mandrill:






43 pohlmann@mandrill:readers_writers1

give #readers, #writers

3 1

> 90700

> 90700

> 90700

44 pohlmann@mandrill:

Nichtdeterminismus des Ablaufs und daher Nichtdeterminiertheit des Ergebnisses. Ergebnis = Letzter gelesener Wert bei 100000 Zugriffen.

Mängel der Lösung

Ada erlaubt keine ,,blockierenden Operationen in protected operations, also z.B. I/O.
Starvation (= Aushungern) der Schreiber möglich:
$\includegraphics{writerStarvation.eps}$

Ergebnis unseres Laufs brauchbar, da 1-Prozessor Implementierung vorliegt und reader wahrscheinlich nicht während seiner read-operation unterbrochen, bei Prozeßwechsel aber jeder Prozeßtyp gleichermaßen möglich.

Das umgekehrte Problem - Leser verhungern wegen Unfairness - ist auch denkbar:

$\includegraphics{readerStarvation.eps}$

Erfordert aber ,,bösartiges`` Verhalten der Prozeßverwaltung und genügend dichte (häufige) Aufrufe von write; praktisch weniger wichtiges Problem und von uns nicht behandelt!

Aber jetzt Verbesserung:

Wenn writer Ressource benutzen will, werden keine neuen Lesewünsche mehr zugelassen.
Protokoll realisiert duch Kontroll-Task, die über Ressourcenbenutzung Buch führt und ähnlich wie Semaphor-Kombination wirkt.


-----------------------------------

- Readers-Writers Demo, mit simpler integer-Variablen

-

- Version 2: control task in package =>  preference for writer,

-                                        potentially blocking ops allowed

-----------------------------------






with Stringpack; use Stringpack;

procedure Readers_Writers2 is






package Variable is

procedure Write (X : Integer);

function Read return Integer;

end Variable;






package body Variable is






V : Integer := 0; - na ja






task Control is

entry Start_Read;

entry Finish_Read;

entry Start_Write;

entry Finish_Write;

end Control;






task body Control is

Readers, Writers : Natural := 0;

begin

loop

select

when Writers = 0  and Start_Write'Count = 0 => - no writer inside or waiting

accept Start_Read;

Readers := Readers + 1;

or

accept Finish_Read;

Readers := Readers - 1;

or

when Readers = 0 and Writers = 0  =>  - nobody inside

accept Start_Write;

Writers := 1;

or

accept Finish_Write;

Writers := 0;

or

terminate;

end select;

end loop;

end Control;






procedure Write (X : Integer) is

begin

Control.Start_Write;
V := X;

Control.Finish_Write;
end Write;






function Read return Integer is

X : Integer;

begin

Control.Start_Read;

X := V;

Control.Finish_Read;

return V;
end Read;






end Variable;






task type Reader;

task body Reader is

Local_X : Integer;

begin

for I in 1..100000 loop

Local_X := Variable.Read;

end loop;

Print(» " & Local_X);

end Reader;






task type Writer;

task body Writer is

Local_X : Integer := 1;

begin

for I in 1..100000 loop

Variable.Write(Local_X);

Local_X := Local_X + 1;

end loop;

end Writer;






Anz_R, Anz_W : Natural;






begin






Print("give #readers, #writers");
Anz_R := Getint; Anz_W := Getint;

declare

R : array(1..Anz_R) of Reader;

W : array(1..Anz_W) of Writer;

begin null; end;






end Readers_Writers2;






--------------------------

35 pohlmann@mandrill:readers_writers2

give #readers, #writers

3 1

> 100000

> 100000

> 100000

36 pohlmann@mandrill:

Beachte:

Zugangskontrolle durch task, aber eigentliche Nutzung der Ressource außerhalb.
Alles verpackt in package mit read/write-ops als Schnittstelle, aber Protokollimplementierung vor Klient geschützt.
Guard vor accept-read berücksichtigt Anzahl der bereits wartenden Schreiber vermöge des Attributs ,,start_write'count`` = Zahl der aktuell wartenden Aufrufer dieses entry.

Zum Vergleich: Die folgende Programmversion unterläßt die Bedingung ,,when start_write'count = 0`` und läßt im Beispiel-Lauf die Leser öfter zum Zuge kommen:


-----------------------------------

- Readers-Writers Demo, mit simpler integer-Variablen

-

- Version 2: control task in package => *no* preference for writer,

-                                       potentially blocking ops allowed

-----------------------------------






with Stringpack; use Stringpack;

procedure Readers_Writers2a is






package Variable is

procedure Write (X : Integer);

function Read return Integer;

end Variable;






package body Variable is






V : Integer := 0; - na ja






task Control is

entry Start_Read;

entry Finish_Read;

entry Start_Write;

entry Finish_Write;

end Control;






task body Control is

Readers, Writers : Natural := 0;

begin

loop

select

when Writers = 0   => - no writer inside, no preference for writers

accept Start_Read;

Readers := Readers + 1;

or

accept Finish_Read;

Readers := Readers - 1;

or

when Readers = 0 and Writers = 0  =>  - nobody inside

accept Start_Write;

Writers := 1;

or

accept Finish_Write;

Writers := 0;

or

terminate;

end select;

end loop;

end Control;






procedure Write (X : Integer) is

begin

Control.Start_Write;
V := X;

Control.Finish_Write;
end Write;






function Read return Integer is

X : Integer;

begin

Control.Start_Read;

X := V;

Control.Finish_Read;

return V;
end Read;






end Variable;






task type Reader;

task body Reader is

Local_X : Integer;

begin

for I in 1..100000 loop

Local_X := Variable.Read;

end loop;

Print(» " & Local_X);

end Reader;






task type Writer;

task body Writer is

Local_X : Integer := 1;

begin

for I in 1..100000 loop

Variable.Write(Local_X);

Local_X := Local_X + 1;

end loop;

end Writer;






Anz_R, Anz_W : Natural;






begin






Print("give #readers, #writers");
Anz_R := Getint; Anz_W := Getint;

declare

R : array(1..Anz_R) of Reader;

W : array(1..Anz_W) of Writer;

begin null; end;






end Readers_Writers2a;






--------------------------

37 pohlmann@mandrill:readers_writers2a

give #readers, #writers

3 1

> 3751    -+

> 3751     | Also Leser viel schneller fertig als Schreiber!

> 4274    -+

38 pohlmann@mandrill:

Zur Korrektheit der Lösung (= ,,readers_writers2``):

Safety: (= ,,writer hat exklusiven Gebrauch``) Ist klar, wegen guards und Zählern.
No deadlock: Klar, wenn Gebrauch der Ressource nur endlich dauert.
No starvation: Auch klar, wenn Ada-Implementierung offene selective-accept-Alternativen fair bedient.

Angegebene Lösung hat erheblichen Zeitbedarf, weil pro Zugriff (read/write) 2 Rendezvous nötig.

Kleine Verbesserungsmöglichkeit: Eigentliche write-Tätigkeit in die task integrieren und den Zähler für writers sowie finish_write einsparen:


select

   ...

or

when Readers = 0 =>

accept Start_Write(X: Integer)

do V := X; end Start_Write;

or

terminate;

end select;

Alternative

protected-object


-----------------------------------

- Readers-Writers Demo, mit simpler integer-Variablen

-

- Version 3: protected object in package =>  preference for writer,

-                                            potentially blocking ops allowed

-----------------------------------






with Stringpack; use Stringpack;

procedure Readers_Writers3 is






package Variable is

procedure Write (X : Integer);

function Read return Integer;

end Variable;






package body Variable is






V : Integer := 0; - na ja






protected Control is

entry Start_Read;

procedure Finish_Read;

entry Start_Write;

procedure Finish_Write;

private

Readers, Writers : Natural := 0;

end Control;






protected body Control is






- no writer waiting or working

entry Start_Read when Writers = 0 and Start_Write'Count = 0 is  
begin Readers := Readers + 1; end Start_Read;






procedure Finish_Read is

begin Readers := Readers - 1; end Finish_Read;






entry Start_Write when Readers = 0 and Writers = 0   is   - nobody inside

begin Writers := 1; end Start_Write;






procedure Finish_Write is

begin Writers := 0; end Finish_Write;






end Control;






procedure Write (X : Integer) is

begin

Control.Start_Write;
V := X;

Control.Finish_Write;
end Write;






function Read return Integer is

X : Integer;

begin

Control.Start_Read;

X := V;

Control.Finish_Read;

return V;
end Read;






end Variable;






task type Reader;

task body Reader is

Local_X : Integer;

begin

for I in 1..100000 loop

Local_X := Variable.Read;

end loop;

Print(» " & Local_X);

end Reader;






task type Writer;

task body Writer is

Local_X : Integer := 1;

begin

for I in 1..100000 loop

Variable.Write(Local_X);

Local_X := Local_X + 1;

end loop;

end Writer;






Anz_R, Anz_W : Natural;






begin






Print("give #readers, #writers");
Anz_R := Getint; Anz_W := Getint;

declare

R : array(1..Anz_R) of Reader;

W : array(1..Anz_W) of Writer;

begin null; end;






end Readers_Writers3;






--------------------------

36 pohlmann@mandrill:readers_writers3

give #readers, #writers

3 1

> 71215

> 89096

> 100000

44 pohlmann@mandrill:readers_writers3

give #readers, #writers

3 1

> 44358

> 45480

> 52115

Unterschiede

ist schneller: Einige Sekunden statt Minuten.
streut stärker im Resultat, mit Tendenz zur Bevorzugung von Lesern!

Korrektheit (Schreiber verhungert nicht) bleibt natürlich erhalten, trotzdem möglich, daß ,,endliche`` Bevorzugung von Lesern:

Wegen anderer task-Verwaltung, also Frage von Implementierung, Scheduling, ..., insbesondere Prozeßwechsel bei Rendezvous.
Beachte auch Ada-Semantik: Bei Ende von protected procedure/entry werden guards neu ausgewertet und dann ausführbare entries sofort (also nicht in Konkurrenz zu neuen Ankünften) ausgeführt.

$\Rightarrow$

Dining Philosophers

Praktischer Hintergrund: Prozesse benötigen mehrere exklusive Betriebsmittel gleichzeitig - dann kann ungeschickte Zuteilung zu Verklemmung führen, z.B. 2 Köche in 1 Küche, 1 Topf, 1 Löffel, jeder braucht beides. Koch 1 ergreift Löffel, Koch 2 ergreift Topf $\Rightarrow$ Deadlock.

Gebräuchliche Vermeidungsstrategie: Lege fest, daß Prozesse die Betriebsmittel in derselben Reihenfolge belegen. Z.B. 1. Löffel, 2. Topf $\Rightarrow$ Wenn Koch 1 Löffel hat, muß Koch 2 warten, bis Koch 1 fertig.

,,Dining philosophers`` Problem ist so konstruiert, daß diese Lösung nicht möglich.

Gegeben

Gemeinschaft von (z.B.) 5 Philosophen, die ihr Leben mit Denken und Essen zubringen.
Speisesaal mit Tisch mit 5 Tellern, 5 Gabeln und Spaghettihaufen (unerschöpflich).
$\includegraphics{diningPhil.eps}$
Regel: Jeder Philisoph hat seinen Platz (Teller), benötigt aber beide danebenliegenden Gabeln (wobei er eine Gabel nicht mehr freigibt, bis er fertig gegessen hat)!

Gesucht

(Fragen der Hygiene, des Anstands usw. spielen keine Rolle; es ist aber zugesichert, daß kein Philosoph endlos ißt oder über seinem Teller stirbt! Anmerkung des Tippers: Auch der Diebstahl einer Gabel sei ausgeschlossen!)

Offensichtlich nötig


entry Pick_Up when Frei is

begin Free := False; end Pick_Up;






protected Put_Down is

begin Free := True; end Put_Down;

Klar: Safety (= keine 2 Philosophen haben dieselbe Gabel).
Aber: Verklemmung möglich: Jeder Philosoph ergreift linke Gabel und findet dann rechte Gabel benutzt.
Lösung: Erlaube höchstens 4 Philosophen im Speisesaal!

$\Rightarrow$ liveness, denn

Schubfachprinzip (=pigeonhole principle)

Jede

$\includegraphics{pigeon.eps}$

Identifiziere: Objekt = Gabel, Fach = Philosoph und beschränke Verteilungsmöglichkeit auf die für unser Problem legalen Fälle (linke, rechte Gabel pro Philosoph).

Das folgende Programm führt zur Beschränkung der im Speisesaal anwesenden Philosophen ein weiteres protected-object ein (task wäre auch möglich); zur Dokumentation wird bei jedem Ereignis (= Gabel ergreifen oder niederlegen) der aktuelle Stand protokolliert und ausgegeben:


-----------------------------------

- Dining Philosophers
-

- synchronisation by protected objects room and fork (1..#phils):

-                room (always less than #phils inside) => deadlock prevention,
-                                                 fork => mutual exclusion;
- for demo, phils call trace task whenever having seized/released a fork

-----------------------------------






with Stringpack; use Stringpack;

procedure Philosophers is






How_Many : constant Natural := 5;
subtype Phil_Range is Integer range 0..How_Many-1;

How_Often : constant Natural := 5;          - Zahl der Speisungen/Philosoph






task Trace is ----------------------------

entry Up(Where : Phil_Range);

entry Down(Where : Phil_Range);

end Trace;






task body Trace is

Busy : array(Phil_Range) of Boolean := (others => False);

begin

loop

Outbuffer := Varnull;

select

accept Up(Where : Phil_Range)

do Busy(Where) := True; end Up;

for J in Phil_Range loop

if Busy(J) then Outbuffer := Outbuffer & " X";

else Outbuffer := Outbuffer & " +"; end if;

end loop;

Print;

or

accept Down(Where : Phil_Range)

do Busy(Where) := False; end Down;

for J in Phil_Range loop

if Busy(J) then Outbuffer := Outbuffer & " X";

else Outbuffer := Outbuffer & "; end if;

end loop;

Print;

or

terminate;

end select;

end loop;

end Trace;  -----------------------------






protected Room is  --------------------------

entry Enter;

procedure Leave;

private

Present : Natural := 0;

end Room;






protected body Room is

entry Enter when Present < How_Many -1 is

begin Present := Present +1; end Enter;

procedure Leave is

begin Present := Present -1; end Leave;

end Room;  ------------------------------






protected type Forks is  -----------------------

entry Pick_Up;

procedure Put_Down;

private

Free : Boolean := True;

end Forks;






protected body Forks is

entry Pick_Up when Free is

begin Free := False; end Pick_Up;

procedure Put_Down is

begin Free := True; end Put_Down;

end Forks;






Fork : array(Phil_Range) of Forks; ------------------






task type Philosophers (Me : Phil_Range);   -------------






task body Philosophers is

begin

for I in 1..How_Often loop

delay 0.0001; - think

Room.Enter;

Fork(Me).Pick_Up;  -left fork

Trace.Up(Me);

Fork((Me + 1) mod How_Many).Pick_Up; -right fork

Trace.Up((Me + 1) mod How_Many);

delay 0.0001; - eat

Fork(Me).Put_Down;  -left fork

Trace.Down(Me);

Fork((Me + 1) mod How_Many).Put_Down; -right fork

Trace.Down((Me + 1) mod How_Many);

Room.Leave;

end loop;

end Philosophers;






type A_Philosophers is access Philosophers;

Philosopher : array(Phil_Range) of A_Philosophers;  ---------






begin  ------------------------------main






for I in Phil_Range loop Philosopher(I) := new Philosophers(I); end loop;






end Philosophers;  --------------------------






-----------------------------------

Legende: Spalte = fork-nr, 'X' = belegt, '+' und '-' = frei,
wobei ' -' =Freigabeereignis, '+' = Belegungsereignis.






33 pohlmann@pavian:philosophers

Spalte 1       Spalte 2       Spalte 3       Spalte 4

X + + + +      - - X X -      - X - - -      X - - X -

X X + + +      + X X X +      - - - - -      - - - X -

 - X - - -      - X - X -      + X + + +      + + + X X

 - - - - -      - X - - -      + X X + +      - - - - X

 + X + + +      + X X + +      - - X - -      - - - - -

 + X X + +      X X X + +      - - - - -      + + + + X

X X X + +      X - X - -      + + X + +      X + + + X

X - X - -      X - - - -      + + X X +      X + + X X

X - - - -      X + X + +      - - - X -      X - - X -

X + X + +      X + X X +      - - - - -      - - - X -

X + X X +      X X X X +      + + + X +      + + + X X

X X X X +      X X - X -      + + + X X      - - - - X

 - X X X -      X X - - -      - - - - X      - - - - -

 - - X X -      - X - - -      - - - - -      + + + + X

 - - - X -      - - - - -      + + + + X      X + + + X

 - - - - -      + X + + +      X + + + X      X + + X X

 + X + + +      + X X + +      X + + X X      X - - X -

 + X X + +      X X X + +      X - - X -      - - - X -

X X X + +      X - X - -      - - - X -      + + + X X

X - X - -      X - - - -      + + + X X      - - - - X

X - - - -      X + X + +      - - - - X      - - - - -

X X + + +      X + X X +      - - - - -      + + + + X

X X X + +      X X X X +      + + + + X      X + + + X

X X X X +      X X - X -      X + + + X      X - - - -

 - X X X -      X X - - -      X + + X X      - - - - -

weiter in       weiter in      weiter in

Spalte 2        Spalte 3       Spalte 4

34 pohlmann@pavian:

Asynchrone Iteration

Fixpunktproblems
$\begin{array}{rcl} x_1 & = & f_1(x_1, \dots, x_n) \ & \vdots & \ x_n & = & f_n(x_1, \dots, x_n) \ \end{array}$

$\begin{array}{rclr} x_1^{s+1} & = & f_1(x_1^s, \dots, x_n^s) & (Jakobi) \ & \vdots & & \ x_n^{s+1} & = & f_n(x_1^s, \dots, x_n^s) & \ \end{array}$

$\begin{array}{rclr} x_1^{s+1} & = & f_1(x_1^s, \dots, x_n^s) & (Gauss-Seidl) ... ... x_n^{s+1} & = & f_n(x_1^{s+1}, \dots, x_{n-1}^{s+1}, x_n^s) & \ \end{array}$

Solche Iterationen legen fest, welche Vor-Versionen von Werten zur Berechnung der nächsten Version $x_i^{s+1}$ zu benutzen sind und heißen deshalb synchron.

Zur Parallelisierung - z.B. für jede Komponente $x_i$ eigenen Prozeß - kann man sich andere sinnvolle Reihenfolgen ausdenken, oder die Reihenfolge überhaupt freigeben = asynchrone oder chaotische Iteration.

Standard Iteration

$\includegraphics{stdIteration.eps}$

Chaotische Iteration

$\includegraphics{chaosIteration.eps}$

Bezüge so, wie sie sich faktisch ergeben, also durch relative Geschwindigkeit der beteiligten Prozesse bzw. Verfügbarkeit von Werten!! (,,asynchron`` = ohne festen zeitlichen Bezug, insbesondere Reihenfolge).

Wir betrachten ein

Beispiel

Literatur

Programmentwicklungs-Philosophie: Clandy/Misra: ,,Parallel Program Design``, 19..
Technik für numerische Probleme: Bertsekas/Tsitsiktis: ,,Parallel & Distributed Computations: Numerical Methods``, 1984

Hausaufgabe

Im Sekretariat wir ein Terminvorschlag ausgehängt.
Jeder Professor kommt sooft wie möglich im Sekretariat vorbei, vergleicht seinen Terminkalender mit dem aktuellen Vorschlag und verschiebt, wenn nötig, letzteren auf den frühesten individuell möglichen späteren Termin.
Alle sind bereit, die Sitzung am letzten Tag des Semesters abzuhalten (weil sonst die Fakultät geschlossen wird), so daß das Problem eine Lösung hat.

Überlegen Sie sich, daß das beschriebene Verfahren die früheste für alle Profs mögliche Lösung findet.
Realisieren Sie das Verfahren mit Ada-tasks und statten Sie das Programm mit einem geeignetem Terminierungsprotokoll aus. (z.B. Terminvorschlag gilt, wenn von allen n Profs gesehen und nicht geändert).

Nächste Seite:Ada ,,requeue`` KonstruktAufwärts:Vorlesungsskriptum zu Spezielle AnwendersprachenVorherige Seite:Rendezvous mit AlternativenInhaltsverzeichnis

Ronald Blaschke 2001-06-02