Home
 
 

Wechselseitiger Ausschluß und gemeinsame Variablen

Wechselseitiger Ausschluß und gemeinsame Variablen

Die in diesem Kapitel benutzten Programmiertechniken und -lösungen taugen nichts; von ihrem Gebrauch wird dringend abgeraten!

Warum werden sie hier benutzt?

  1. Historisch-didaktische Gründe: Problemlage kennenlernen
  2. Hier noch nicht adäquate Ada- (oder sonstwas) Konzepte einführen, aber trotzdem Beispiele programmieren wollen.

Wechselseitiger Ausschluß (,,mutual exclusion``)

Problem
Zwei (oder mehr) konkurrente Prozesse benutzen dasselbe Betriebsmittel; dieses Betriebsmittel kann aber nicht von mehreren gleichzeitig benutzt werden.

Beispiel

Auf gerätetechnischer Ebene
massenhaft, z.B. Floppies kopieren bei nur 1 Laufwerk
auf Programmebene
z.B. Programmvariable oder komplizierte Datenstruktur (Container-Typ), I/O ...

$\Rightarrow$ Problem
Konkurrentes Verhalten adäquat einschränken (also so konkurrent wie möglich, aber nicht mehr), d.h. sicherstellen, daß kein zweiter zugreift (also notfalls nix tut = wartet), wenn der erste grad zugreift.
$\Rightarrow$ Prozesse synchronisieren (koordinieren)

In Ermangelung von etwas Besserem benutzen wir in diesem Kapitel lediglich

Gemeinsame Variablen (,,shared variables``)

beiden

Terminologie/Problemstruktur

  • Kritischer Abschnitt (,,critical section``) = Teil der Handlungsfolge eines Prozesses, der unter Ausschluß aller anderen Prozesse von der Ausführung ihrer entsprechenden Handlungsfolge ausgeführt werden muß; d.h. die kritischen Abschnitte verschiedener Prozesse sind sequentiell zueinander.
  • Zur Sicherstellung des Ausschlusses ist ein Protokoll (entsprechende Anweisungen vor und nach kritischem Abschnitt) nötig, also exemplarische Struktur eines Prozesses: 

    loop

    Non_Critical_Part1;

    Pre_Protocol;

    Critical_Section;

    Post_Protocol;

    Non_Critical_Part2;

    end loop;
  • Wobei critical_section und Protokollausführung kurz sein sollten im Verhältnis zur übrigen Rechnung. Nie etwas in kritische Abschnitte setzen, was da nicht unbedingt sein muß.
  • Wobei critical_section und Protokollteile besonders sicher sein sollten. (z.B. Prozeß darf nicht im Besitz des gemeinsamen Betriebsmittels sterben)

Beispiel: Gemeinsame Variablen (Shared_Demo1)

  • Das folgende Programm enthält Prozesse, die nur aus kritischen Abschnitten bestehen, nämlich eine gemeinsame Variable modifizieren.
  • Effekt war ohne das Zwischenspeichern in lokaler Variable nicht zu sehen, und auch erst für lange Läufe.
  • Technik des ,,busy waiting`` in Hauptprogramm ist ungut, mehr dazu später.


with Stringpack; use Stringpack;

procedure Shared_Demo1 is






N: Integer :=0; -shared variable

Anz: Positive := 1_000_000;






task Up;

task body Up is

My_N: Integer;

begin

for I in 1..Anz loop

My_N := N;        - -+

My_N := My_N+1;   -  | Kritischer Abschnitt: Zugriff auf n

N := My_N;        - -+

end loop;

end Up;






task Down;

task body Down is

My_N: Integer;

begin

for I in 1..Anz loop

My_N := N;        - -+

My_N := My_N-1;   -  | Kritischer Abschnitt

N := My_N;        - -+

end loop;

end Down;






begin

while not(Up'Terminated and Down'Terminated) loop

null;

end loop; - sehr schlechter Stil !!!!!!!!!!!!!!!






Print(n= " & N);

end Shared_Demo1;






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

39 pohlmann@pavian:shared_demo1

n= 517520

40 pohlmann@pavian:shared_demo1

n= 6204

41 pohlmann@pavian:shared_demo1

n= -97962

42 pohlmann@pavian:shared_demo1

n= 433532

Programm sollte als ,,Netto``-Effekt die Variable n wieder auf 0 setzen (= 1 Mio. inkrementieren/dekrementieren) aber offenbar unsicher;
Grund: Ungeschützter Gebrauch der gemeinsamen Variablen; also Abläufe möglich wie

 task uptask down
\fbox{n=0}  
 My_N := N; 
 My_N := My_N+1; 
  My_N := N;
  My_N := My_N-1;
  N := My_N;
\fbox{n=-1}  
 N := My_N; 
\fbox{n=1}  

Hausaufgabe

  1. Zwei Prozesse machen Einträge in eine gemeinsam benutzte Liste (Warteschlange, Keller)
  2. Zwei Prozesse benutzen Stringpack oder direkt task_io für Ein-/Ausgaben.

Anmerkung zum Hauptprogramm

Zweck
Endergebnis ausdrucken, nachdem die beiden tasks beendet sind.
Technik
,,busy waiting`` (geschäftiges Warten) d.h. Hauptprogramm fragt ständig nach, ob tasks schon fertig.
$\Rightarrow$ furchtbar viel Rechenaufwand für Nichts-tun!
$\Rightarrow$ andere Synchronisationstechniken müssen her! ($\Rightarrow$ später)

Wie Problem lösen?

  • Wir betrachten im folgenden einige Ideen (von denen erst die letzte wichtig ist).
  • Die alle keine besondere Unterstützung durch z.B.
    • spezielle Programmiersprachen-Konstrukte
    • spezielle Maschinenbefehle
    • Betriebssystemdienste
    verwenden;
  • Was bleibt sind dann:
    • Gewöhnliche Programmvariable + übliche Konstruktoren und Anweisungen!
    • Wobei man voraussetzen muß:
      1. Schreiben und Lesen von Variablen primitiver Datentypen (Boolean, Integer) erfolgt atomar (ungeteilt, ununterbrochen) und unter Ausschluß eines gleichzeitigen anderen Zugriffs.
      2. Die Prozesse benutzen die Variablen selbst und nicht lokale Kopien davon, die sie anfangs erstellen und später zurückschreiben.
1
Kann man als durch die Hardware garantiert ansehen - keine 2 gleichzeitigen Speicherzugriffe!
2
Geht durch Optimierungen des Compilers oft verloren!
Programm$\Rightarrow$Maschineninstruktionen
x := x+1; load x into register;
  add 1 to register;
if x = 10 compare register with 10;
then x := 0; if equal then set register to 0;
end if; store register into x;

Ende

Um solche Optimierungen zu verhindern und 2 sicherzustellen, kann man in Ada ein ,,pragma`` (= Compilerdirektive) verwenden:


pragma Volatile (x);
12 

pragma Atomic (x);

Idee 1

task 1 


loop

   ...

Flag1 := True;

while Flag2 loop

null;

end loop;

Critical_Section;

Flag1 := False;

   ...

end loop;

task 2 


loop

   ...

Flag2 := True;

while Flag1 loop

null;

end loop;

Critical_Section;

Flag2 := False;

   ...

end loop;

Wobei global vereinbart ist:


Flag1, Flag2: Boolean := False;

Es gilt:

  1. Das Verfahren ist sicher (,,safe``)
  2. Das Programm kann in eine Verklemmungssituation (,,deadlock``) geraten
safety
Es kann nichts Böses getan werden, d.h. Form von partieller Korrektheit.
deadlock
Zwei (oder mehrere) Prozesse sind verklemmt, wenn jeder auf ein Ergebnis wartet, das erst durch den Fortschritt des anderen eintreten kann, z.B. p1 wartet auf p2 während p2 auf p1 wartet.

Safety des Verfahrens

beide
$\Rightarrow$$\exists t_1, t_1', t_2, t_2', t_1<t_1'<t, t_2<t_2'<t$
  • flag1 im Intervall ($t_1$, t] und
  • flag2 im Intervall ($t_2$, t] und
  • $\neg$flag2 in $t_1'$ und
  • $\neg$flag1 in $t_2'$.


$ t_1 < t_2 \Rightarrow t_2' \in (t_1, t] $

$ t_1\ge t_2 \Rightarrow t_1' \in (t_2, t] $

Bildlich: 2 Gummibänder, fixiert am rechten Ende (= t) repräsentieren Gültigkeitsbereich von flag1 und flag2. 2 Marken auf den Bändern (= $t_1'$, $t_2'$) repräsentieren daß $\neg$flag1 und $\neg$flag2 gefunden werden. Unmöglich, die Bänder so zu dehnen daß beide Marken vor Beginn des jeweils anderen Bandes!

\includegraphics{gummiband.eps}

Korrektheitsbeweise für konkurrente Programme sind

  • sehr wünschenswert, weil man die möglichen Abläufe noch schlechter übersieht als im sequentiellen Fall,
  • besonders schwierig, weil man immer an mehreren Programmstellen zugleich ist.

Methoden

  • Gewöhnliche Prädikatenlogik, wobei man außer Zustandsgrößen auch noch über Zeitpunkte (oder Programmstellen, -zähler) reden muß, (s.o.)
  • Temporäre Logik, die spezielle Konstrukte wie ,,letztendlich``, ,,als nächstes`` u.ä. verwendet und dadurch die explizite Verwendung von Zeit erspart
  • (In einfachen Fällen) Zustandsdiagramme, endliche Automaten
  • Spezielle Formalismen zur Algorithmenbeschreibung wie Petri-Netze oder CSP und zugehörige Beweistechniken.

Verklemmung des Verfahrens

task 1task 2
flag1 := True; 
 flag2 := True;
 while flag1 loop
 null;
 end loop;
while flag2 loop 
null; 
end loop; 
Ab jetzt beide Tasks in Warteschleife.

Verklemmung schwierig durch Tests zu entdecken weil

  1. eintreten von Zufällen abhängig (timing, Verzahnung),
  2. oft durch andere Aktivitäten im System verdeckt.

Idee 2


task 1 


loop

   ...

Flag1 := True;

while Flag2 loop

Flag1 := False;

delay 1.0;

Flag1 := True;

end loop;

Critical_Section;

Flag1 := False;

   ...

end loop;

task 2 verläuft analog.

Es gilt

  1. Safety, aus ähnlichen Gründen wie bei Idee 1
  2. Deadlockfrei, jedenfalls in dem Sinn, daß das erwartete Ergebnis ($\neg$flag1 bzw. $\neg$flag2) immer wieder angeboten wird.
  3. Lockout möglich!
Lockout/Starvation (Verhungern)
Prozeß wird unbestimmt (ewig) lange von seinem Ziel abgehalten, wenn ein bestimmtes timing gerade eingehalten wird.
 flag1flag2
initFalseFalse
p1 setsTrueFalse
p2 setsTrueTrue
   
p1 testsTrueTrue
p2 testsTrueTrue
p1 setsFalseTrue
p2 setsFalseFalse
p1 setsTrueFalse
p2 setsTrueTrue

Dieser Fall ist weniger schwerwiegend als deadlock, da die Blockierung jetzt nicht zwangsläufig, sondern nur durch sehr unwahrscheinliche Aufrechterhaltung der Reihenfolge der Aktionen resultiert, aber praktisch insofern störend, als beliebig große Verzögerungen resultieren können; deadlock und starvation sind Verstöße gegen liveness (= Lebendigkeit) des Verfahrens.

Safety
Es passiert nix Böses, z.B. beide Prozesse in kritischem Abschnitt.
liveness
Letztendlich passiert was Gutes (= Zweck der Veranstaltung), z.B. jeder Prozeß kriegt einmal das gewünschte Betriebsmittel.

Hausaufgabe

Idee 3

Abwechseln

task 1 


loop

   ...

while Turn = 2 loop

null;

end loop;

Critical_Section;

Turn := 2;

   ...

end loop;

task 2 


loop

   ...

while Turn = 1 loop

null;

end loop;

Critical_Section;

Turn := 1;

   ...

end loop;

Verfahren ist sicher und frei von deadlock/starvation, bedeutet aber enge Kopplung beider Prozesse.

  • Wenn einer aussteigt kann der andere nicht mehr weiter.
  • Beide arbeiten mit derselben Rate.

Keine adäquate Lösung des Problems!

Idee 4


Gemeinsame Variablen


Flag1, Flag2: Boolean := False;

Turn: Positive range 1..2;

task 1 


loop

   ...

Flag1 := True;

Turn := 1;

while Flag2 and Turn = 1 loop

null;

end loop;

Critical_Section;

Flag1 := False;

   ...

end loop;

task 2 


loop

   ...

Flag2 := True;

Turn := 2;

while Flag1 and Turn = 2 loop

null;

end loop;

Critical_Section;

Flag2 := False;

   ...

end loop;

Es gilt

Kombination vermeidet deadlock-Gefahr von Idee 1

$\Rightarrow$
Keine Änderung der Variablenwerte
$\Rightarrow$
dauerhaft (flag2 and turn = 1) und (flag1 and turn = 2)

Kombination vermeidet strikte Abwechslung wie in Idee 3

unkritischen
$\Rightarrow$
längere Zeit oder ewig: $\neg$flag2
$\Rightarrow$
längere Zeit oder ewig: Bedingung der Warteschleife von Prozeß 1 ist False!

Korrektheitsbeweis für das Verfahren ist kompliziert und aufwendig, deshalb hier unterlassen. Für Interessierte: Das Buch von T. Axford (p. 203-205) präsentiert einen auf Zustandsdiagramme gestützten Beweis.

Beispiel (Shared_Demo2)


with Stringpack; use Stringpack;

procedure Shared_Demo2 is






N: Integer := 0; -shared variable

Anz: Positive := 1_000_000;






TURN: POSITIVE range 1..2;

FLAG1, FLAG2: BOOLEAN := FALSE;

pragma ATOMIC(TURN); -sicher ist sicher

pragma ATOMIC(FLAG1);

pragma ATOMIC(FLAG2);






task Up;

task body Up is

My_N: Integer;

begin

for I in 1..Anz loop

FLAG1 := TRUE;

TURN := 1;

while FLAG2 and TURN = 1 loop null; end loop;

My_N := N;

My_N := My_N+1;

N := My_N;

FLAG1 := FALSE;

end loop;

end Up;






task Down;

task body Down is

My_N: Integer;

begin

for I in 1..Anz loop

FLAG2 := TRUE;

TURN := 2;

while FLAG1 and TURN = 2 loop null; end loop;

My_N := N;

My_N := My_N-1;

N := My_N;

FLAG2 := FALSE;

end loop;

end Down;






begin

while not(Up'Terminated and Down'Terminated) loop

null;

end loop; - sehr schlechter Stil !!!!!!!!!!!!!!!






Print(n= " & N);

end Shared_Demo2;






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

70 pohlmann@pavian:shared_demo2

n= 0

Kritik an Lösung und verwendeten Mitteln

  1. Schwer zu verstehen, fehleranfällig im Gebrauch, schwer zu variieren (z.B.
    • Verallgemeinerung auf n Prozesse,
    • Verallgemeinerung auf verteilte Systeme).
  2. (Sehr) ineffizient, da Warten als geschäftiges Warten (,,busy waiting``) realisiert wird, d.h. wartender Prozeß beansprucht Prozessor und verzögert damit, daß anderer Prozeß vorankommt und insbesondere Wartebedingung auflöst. (Illustration siehe unten, mit Zählern in Warteschleifen.) Diese Kritik immer dann berechtigt, wenn wartender Prozeß nicht Prozessor für sich alleine hat!

with Stringpack; use Stringpack;

procedure Shared_Demo2a is






N: Integer := 0; -shared variable

Anz: Positive := 1_000_000;






TURN: POSITIVE range 1..2;

FLAG1, FLAG2: BOOLEAN := FALSE;

pragma ATOMIC(TURN); -sicher ist sicher

pragma ATOMIC(FLAG1);

pragma ATOMIC(FLAG2);






BUSY1, BUSY2: Natural := 0;






task Up;

task body Up is

My_N: Integer;

begin

for I in 1..Anz loop

FLAG1 := TRUE;

TURN := 1;

while FLAG2 and TURN = 1 loop BUSY1 := BUSY1+1; end loop;

My_N := N;

My_N := My_N+1;

N := My_N;

FLAG1 := FALSE;

end loop;

end Up;






task Down;

task body Down is

My_N: Integer;

begin

for I in 1..Anz loop

FLAG2 := TRUE;

TURN := 2;

while FLAG1 and TURN = 2 loop BUSY2 := BUSY2+1; end loop;

My_N := N;

My_N := My_N-1;

N := My_N;

FLAG2 := FALSE;

end loop;

end Down;






begin

delay 120.0;

Print("BUSY1= " &BUSY1 & " BUSY2= " & BUSY2);

end Shared_Demo2a;






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

pohlmann@pavian:shared_demo2a

BUSY1= 79802288 BUSY2= 78124617

^C






...

begin

while not(Up'Terminated and Down'Terminated) loop

null;

end loop; - sehr schlechter Stil !!!!!!!!!!!!!!!






Print("BUSY1= " &BUSY1 & " BUSY2= " & BUSY2);

end Shared_Demo2a;






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

rbla@bravo:shared_demo2a

BUSY1= 2147483647 BUSY2= 2147483647

Konsequenz daraus

  • Erfinde programmiersprachliche Konstrukte, die Details der nötigen Protokolle verbergen.
  • Implementiere solche Konstrukte so, daß kein busy waiting, vielmehr: benutze Prozeßverwaltung des Betriebssystems mit Diensten wie ,,Prozeß schlafen legen``/``Prozeß aufwecken``.

Hausaufgabe

nextnextupuppreviouspreviouscontentscontents
Nächste Seite:Semaphore und MonitoreAufwärts:Vorlesungsskriptum zu Spezielle AnwendersprachenVorherige Seite:Ada Tasks IInhaltsverzeichnis
Ronald Blaschke 2001-06-02