vorige Seite
 
Originalskript
 

 

Kapitel 2

Pseudoparallele Programmierung 

Der Ursprung der Entwicklung von Konzepten, Techniken und Sprachen zur Programmierung nebenläufiger Systeme liegt in der pseudoparallelen Programmierung. Aus historischer Sicht wuchs mit der technischen Leistungsfähigkeit der sequentiell arbeitenden Computer der Wunsch, dieses Potential eines Rechners mehreren Benutzern gleichzeitig zur Verfügung zu stellen. So begann die Konstruktion von Softwaresystemen, die einen Mehrprogrammbetrieb auf einer Ein-Prozessor-Rechnerarchitektur zulassen, lange Zeit vor der Konstruktion der ersten Parallelrechner im heutigen Sinne. Dieser Zweig der Betriebssystementwicklung behandelt grundlegende Methoden, die zur Organisation des Ablaufs mehrerer Prozesse auf einem Rechner notwendig sind. Die Entwicklung beginnt bei dem Entwurf und der Untersuchung unterschiedlicher Schedulingmethoden, die dazu dienen, einen pseudoparallelen Ablauf mehrerer Prozesse1 zu organisieren, indem die CPU in kurzen zeitlichen Abständen zwischen den jeweiligen Prozeßkontexten umgeschaltet wird. Da die einzelnen Prozesse nicht alle unabhängig voneinander sind, müssen zusätzlich zum Scheduling Methoden zur Synchronisation und Koordination der Prozesse behandelt werden. 

In diesem Kapitel erläutern wir an einem einleitenden Beispiel die hier vorliegende Form der Parallelität, nämlich die sequentielle Ausführung einer Folge von atomaren Operationen, die durch eine in gewissem Sinne zufällige Verschachtelung der Befehle der pseudoparallelen Prozesse entsteht. Wir behandeln das Problem des wechselseitigen Ausschlusses, dessen Lösung zur Synchronisation pseudoparalleler Prozesse dient.  

2.1 Pseudoparallele Ausführung mehrerer Prozesse

Auf einer Ein-Prozessor-Rechnerarchitektur ist eine gleichzeitige Ausführung mehrerer Prozesse grundsätzlich nicht möglich. Bei einer Multiprozessorarchitektur besteht zwar technisch die Möglichkeit, daß mehrere Operationen gleichzeitig stattfinden, dennoch unterliegt diese Parallelität einigen Einschränkungen. Die parallelen Operationen können sich eventuell gegenseitig behindern; so ist etwa aus hardwaretechnischen Gründen der gleichzeitige Zugriff mehrerer Prozessoren auf eine gemeinsame Speicherzelle unmöglich. 

Wir gehen im folgenden davon aus, daß das Betriebssystem des Rechners einen pseudoparallelen Betrieb ermöglicht. Eine übersichtliche Darstellung der dazu geeigneten Methoden findet der Leser etwa in [SPG91]. Unabhängig von der konkreten Hardware und der jeweiligen Realisierung des pseudoparallelen Betriebs nehmen wir hier einen abstrakten Standpunkt ein und betrachten das pseudoparallele Ablaufen zweier Prozesse gemäß den folgenden Erläuterungen. 

Ein Prozeß P besteht aus einer Folge von jeweils untrennbaren Operationen p1, p2, p3, ..., sogenannten atomaren Operationen. Diese Operationen sind beispielsweise Lese-, Test- oder Schreiboperationen auf dem globalen Speicher des Rechners. Mit einem zweiten Prozeß Q, bestehend aus den atomaren Operationen q1, q2, q3, ..., bedeutet eine pseudoparallele Ausführung der Prozesse P und Q, daß die Operationen beider Folgen in einer beliebig geschachtelten Reihenfolge ausgeführt werden, bei der jedoch die Ordnung beider einzelnen Folgen erhalten bleibt. Bei dem pseudoparallelen Start beider Prozesse sind die aktuellen Operationen also p1 und q1. Seien nun pi und qj die aktuellen Befehle, dann wird in der pseudoparallelen Ausführung nichtdeterministisch entweder pi oder qj ausgeführt. Bei der Auswahl der Ausführung von pi sind danach pi+1 und qj die aktuellen Operationen, bei der Ausführung von qj sind es pi und qj+1. Falls pi+1 oder qj+1 nicht vorhanden sind, die entsprechende Operationsfolge also endlich ist, gibt es für diesen Prozeß keine aktuelle Operation mehr, und es werden die Operationen des anderen Prozesses ausgeführt. Wenn mindestens eine der Operationsfolgen unendlich ist, verlangen wir für die pseudoparallele Ausführung, daß eine Abwechslung beider Prozesse garantiert ist, indem wir formal etwa fordern, daß für alle pi und qj ein endlicher Wert ci bzw. dj existiert, der angibt, wie viele Operationen des jeweils anderen Prozesses zwischen pi und pi+1 bzw. qj und qj+1 maximal ausgeführt werden (Fairness). 

In diesem Kapitel geben wir die Prozesse in einer an Pascal orientierten Syntax an. Eigentlich würde durch eine Darstellung in Assemblercode eher die Atomarität einzelner Befehle deutlich, worunter jedoch die Verständlichkeit zu leiden hätte. Zum anderen werden wir im Verlauf dieses Kapitels höhere atomare Operationen einführen, die in einer an Pascal orientierten Syntax einfacher erklärt werden können. Trotzdem werden wir an einigen Stellen auf die konkrete Implementierung eingehen. Im übrigen stehen in diesem Kapitel die Konzepte im Vordergrund; diese sind unabhängig von der zur Erläuterung benutzen Programmiersprache. 

Wir beschreiben im folgenden einzelne Prozesse als Pascal-Prozeduren: Die pseudoparallele Ausführung zweier Prozesse P und Q stellen wir für die Pascal-Prozeduren P und Q durch das folgende im Hauptprogramm auftretende Konstrukt dar: 

parbegin P, Q parend 
In dem folgenden Programm sind zwei Prozeduren P und Q, die jeweils zehnmal die globale Variable n lesen, ihren Wert lokal zwischenspeichern und schließlich den um eins inkrementierten Wert wieder in der globalen Variable ablegen. Beide Prozeduren laufen pseudoparallel, d.h. eine Ausführung des Programms bedeutet, daß die mit den Klammersymbolen gekennzeichneten atomaren Operationen in einer zufälligen Verschachtelung ausgeführt werden. Bei dieser Verschachtelung wird die prozedurinterne Reihenfolge der Operationen eingehalten. 
program increment;
const m = 10;
var n: integer;

procedure P;
var i: integer;
    a: integer;
begin
  for i := 1 to m do begin
    a := n;     (* Operation "(" *)
    n := a + 1; (* Operation ")" *)
  end;
end;

procedure Q;
var i: integer;
    a: integer;
begin
  for i := 1 to m do begin
    a := n;     (* Operation "[" *)
    n := a + 1; (* Operation "]" *)
  end;
end;

begin           (* Hauptprogramm *)
  n := 0;
  parbegin P, Q parend;
  writeln ('Summe: ', n);
end.
Wenn man die Zugriffe auf die globale Variable durch Klammersymbole repräsentiert, kann man die Menge aller pseudoparallelen Programmausführungen als Menge aller möglichen Verschachtelungen von jeweils m Klammerpaaren ,,()`` und ,,[]`` auffassen. Man überlegt sich leicht, daß dem Klammerausdruck 
()()()()()()()()()()10 [][][][][][][][][][]10

das Resultat n=20 entspricht. Dem Klammerausdruck 

([])([])([])([])([])([])([])([])([])([])

entspricht das Ergebnis n=10. Insgesamt ist es möglich, daß Werte zwischen 2 und 2 m für m 2 berechnet werden. Diese Werte werden etwa bei einer Verschachtelung der Operationen erzielt, die dem folgenden Klammerausdruck entspricht, der das Resultat n=2+i+j zur Folge hat. 

[()...()m-1-i()...()i []...[]j ([]...[]m-1-j) mit i,j {0,...,m-1} 

Es sind sicher andere Anweisungsreihenfolgen denkbar, jedoch keine, deren Resultat n nicht im Bereich {2,...,2m} liegt. Ein Ergebnis n=0 ist nicht möglich, da weder bei der Operation ,,)`` noch bei ,,]`` der Wert 0 abgelegt wird. Das Resultat n=1 könnte nur dann entstehen, wenn in der letzten Operation, etwa ,,)``, 1 abgelegt würde. Das würde aber bedeuten, daß in der zugehörigen ,,(`` Operation 0 gelesen wurde. Da wegen m 2 zuvor aber mindestens eine ,,)`` Operation ausgeführt wird, kann diese Situation nicht eintreten. Schließlich sind Ergebnisse n > 2 m nicht möglich, da mit jedem Klammerpaar der Wert der Variablen n um maximal 1 erhöht wird, insgesamt aber nur 2m Klammerpaare vorhanden sind. 

Das obige Beispiel zeigt, daß eine pseudoparallele Ausführung zweier Prozesse eine nichtdeterministische Programmausführung zur Folge haben kann, aus der dann verschiedene Ergebnisse hervorgehen können. Wie im folgenden Beispiel deutlich wird, kann dieser Nichtdeterminismus problematisch sein. 
 

1Wir benutzen hier den Begriff Prozeß im allgemeineren Sinn und unterscheiden damit nicht zwischen den Anwenderprogrammen und den Systemprogrammen.

 

 
vorige Seite