Unterthema: Prozeduren und Variablen von MPS
Unterthema: Modul: MPS.def
Unterthema: MODULE Sieve
Unterthema: MPS.mod
Auf dem Gebiet des Supercomputing, das heißt der Entwicklung und Anwendung von Rechnern der obersten Leistungsklasse, ist in den letzten Jahren ein Trend hin zum `Parallel Processing´ zu beobachten. Hinter diesem Begriff verbirgt sich die zunächst simple Idee, zur EDV-mäßigen Erledigung einer bestimmten Aufgabe mehr als nur einen Prozessor einzusetzen, um schneller damit fertig zu sein - etwa nach dem Motto `Wenn ein Arbeiter zum Bau eines Hauses ein Jahr benötigt, schaffen zwölf Arbeiter es in einem Monat´.
Aber nicht nur diese etwas naive Vorstellung führt zur Parallelverarbeitung: letztlich stößt man mit immer weiter hochgezüchteten Zentraleinheiten herkömmlicher, sequentiell arbeitender Rechner an Grenzen. Auch der Übergang zu neuen Technologien (z. B. Verwendung von Gallium-Arsenid statt Silizium bei der Chipherstellung) bewirkt nur eine größere Annäherung an die physikalischen Schranken. Schließlich können sich Signale innerhalb eines Rechners höchstens mit Lichtgeschwindigkeit ausbreiten.
Die Parallelverarbeitung jedoch bietet im Idealfall die Möglichkeit, einfach die Anzahl der Prozessoren zu erhöhen, um die Leistung eines Computersystems zu steigern - jedenfalls dann, wenn das zu lösende Problem parallelisierbar ist. Um aber eine gemeinsame Aufgabe bearbeiten zu können, müssen die einzelnen CPUs eines Multiprozessorsystems in irgendeiner Weise verbunden werden.
Zunächst muß jedoch auf jeden zu verwendenden Prozessor ein Prozeß - ein Programm(teil) - geladen und gestartet werden. In aller Regel gibt es in einem Parallelprogramm einen sogenannten Master-Prozeß und eine Reihe von Slave-Prozessen. Der Master übernimmt die Organisation des Programmablaufs, indem er die anderen Prozesse generiert und ihnen ihre lokalen Daten zuschickt, die diese verarbeiten. Gegen Ende des Programms sammelt er die Teilergebnisse der Slaves ein und setzt daraus das Gesamtergebnis zusammen.
Ein Beispiel: Es soll die Summe von 10 000 000 Zahlen mit zehn Prozessoren berechnet werden. Dazu ist auf einem Message-Passing-Rechner ein Master-Programm zu schreiben, das diese zehn Millionen Zahlen einliest sowie neun Slave-Prozesse erzeugt. An diese überträgt der Master jeweils eine Million Zahlen. Anschließend würde jeder der insgesamt zehn Prozesse die Summe seiner eigenen Million berechnen. Jeder der neun Slaves würde dann sein Ergebnis an den Master schicken, welcher die zehn Teilsummen aufaddiert und das Gesamtergebnis ausgibt.
An diesem Beispiel wird schon klar, daß man mit einem 10-Prozessor-System den idealen Beschleunigungsfaktor von 10 gegenüber einem Einprozessorrechner nicht erreichen wird, denn die Organisation des parallelen Ablaufs und das Übertragen der Daten kosten Zeit.
Ein Message-Passing-System muß also Befehle zum Kreieren von Prozessen, zum Verschicken von Daten und - als Gegenstück dazu - zum Empfangen von Daten ausführen können.
Man muß sich jedoch klarmachen, daß das Schreiben von Parallelprogrammen sehr viel fehleranfälliger ist als das von `normalen´ Programmen. Die Verwendung von Message-Passing-Befehlen birgt Quellen zusätzlicher und neuartiger Fehler, von denen die beiden wichtigsten hier erwähnt seien: Verklemmungen und nicht übereinstimmende Datenlisten.
Eine Verklemmung des Prozeßsystems (Deadlock) tritt auf, wenn durch einen Fehler in der Programmierung des Botschaftsaustauschs alle Prozesse Daten empfangen wollen, diese aber nicht abgeschickt wurden. Ein Fehler in einem einzigen Prozeß kann genügen, um alle Prozesse zum unbeabsichtigten Stillstand zu bringen.
Bei nicht übereinstimmenden Datenlisten können die Prozesse ebenfalls nicht mehr ordnungsgemäß weiterarbeiten. Das ist dann der Fall, wenn ein Prozeß mehr oder weniger Daten abgeschickt hat, als der empfangende einlesen will, oder wenn der empfangende Prozeß mehr oder weniger Daten einlesen will, als der sendende abgeschickt hat.
Optional können Trace-Meldungen über das Verschicken und Empfangen der Daten erzeugt werden, die es erlauben, den simulierten Ablauf des MPS-Programms zu verfolgen. Außerdem ist eine einfache grafische Aufbereitung dieser Informationen möglich.
Der Zweck von MPS besteht in der funktionellen Simulation eines Parallelrechners mit verteiltem Speicher, die es ermöglicht, die prinzipiellen, auf der Ebene einer höheren Programmiersprache möglichen Techniken des Message Passing und Parallel Computing nachzubilden und nachzuvollziehen. Künftige Supercomputer verlangen diese qualitativ neue Art der Programmierung, denn eine automatische Parallelisierung von sequentiellen Programmen ist bisher auf triviale Fälle beschränkt.
MPS wurde mit Hilfe des M2Amiga-Systems von A+L entwickelt (Version 3.20d). Es wurde jedoch auf die Benutzung neuer Prozeduren verzichtet, so daß diese Simulationssoftware auch mit älteren Versionen lauffähig ist.
Der Speicherbedarf wird lediglich bei größeren Projekten relevant, die eine große Anzahl von Slave-Prozessen generieren; ansonsten ist eine Speicherkonfiguration, die für das sehr speicherintensive M2A genügt, völlig ausreichend.
MPS ist nur für den Gebrauch vom CLI aus geeignet, da eventuelle Ausgaben des Programms mittels InOut-Prozeduren oder Trace-Ausgaben im CLI-Fenster erscheinen. Speziell für die Option MAP sollte die 80-Zeichen-Darstellung benutzt werden.
Ein MPS-Programm ist ein im syntaktischen Sinne `normales´ Modula-2-Programm. Das Hauptprogramm enthält dabei den Code des Master-Prozesses. Die Slave-Programme werden in Form von Prozeduren realisiert; deren Code muß natürlich nur einmal erstellt werden, auch wenn mehrere Slave-Prozesse generiert werden, die denselben Algorithmus abarbeiten.
Master und Slaves können die im Kasten beschriebenen MPS-Prozeduren aufrufen, nachdem diese aus MPS.mod importiert wurden. Außerdem benötigt ein Prozeß in manchen Fällen seine eigene Nummer oder die Anzahl aller existierenden Prozesse. Hierzu können die Variablen CurrentProcess und NumberOfProcesses importiert werden.
Prinzipiell arbeitet das Programm `Sieve´ nach dem wohlbekannten Sieb des Eratosthenes. Die Parallelität tritt dadurch zutage, daß für jede neu gefundene Primzahl ein Prozeß generiert wird, der diese Primzahl repräsentiert. Jeder dieser Prozesse sondert sodann in der zu untersuchenden Folge von Zahlen diejenigen aus, die durch eben jene Primzahl teilbar sind (siehe Abbildung).
Der Master (Hauptprogramm) liest zunächst die größte zu untersuchende Zahl maxNr ein und erzeugt den ersten Prozeß, der den Code Pipeline abarbeitet. Diesem schickt er nacheinander die Zahlen 2 bis maxNr und eine 0 als Endekennzeichen. Anschließend empfängt der Master dieselben Zahlen, allerdings gegebenenfalls mit einem Minuszeichen versehen. Ein positiver empfangener Wert signalisiert, daß es sich um eine Primzahl handelt.
Jeder Slave (Prozedur Pipeline) bestimmt zunächst seinen Vorgänger und Nachfolger. Die erste Zahl, die er geschickt bekommt, ist (laut Eratosthenes) eine Primzahl, die er als solche dem Master meldet. In der folgenden Schleife empfängt der Prozeß jeweils eine Zahl: ist sie ungleich 0, so handelt es sich nicht um das Ende der Zahlenfolge, sondern um eine zu untersuchende Zahl.
Wenn diese durch die eigene Primzahl teilbar ist, wird sie durch ein Minuszeichen als Nicht-Primzahl gekennzeichnet und an den Master geschickt. Andernfalls wird die Zahl zur weiteren Untersuchung an den Nachfolger geleitet, der gegebenenfalls noch - vor dem ersten `Durchreichen´ - erzeugt werden muß. Ist die empfangene Zahl gleich 0, also das Endekennzeichen, so ist sie an den Nachfolger weiterzugeben. Handelt es sich jedoch bei der Null um die erste (nach der eigenen Primzahl) empfangene Zahl, so bedeutet dies, daß der aktuelle Prozeß der letzte ist und die Null an den Master geschickt werden muß.
Insgesamt wird also eine Kette von Prozessen erzeugt, deren Länge bei Programmstart noch nicht feststeht. In der Regel werden Botschaften nur an den nachfolgenden Prozeß (successor) geschickt beziehungsweise vom vorhergehenden (predecessor) empfangen (Ausnahme: eine Zahl wird definitiv als prim oder nicht-prim erkannt und an den Master gesendet). Auch bei der praktischen Anwendung von parallelen Systemen werden oft logische Prozeßstrukturen wie Ring, zwei- oder dreidimensionales Gitter, Baum oder Hypercube erzeugt.
Das Modul Sieve verwendet zwei Zähler zur Unterscheidung der Messages (sCounter und rCounter) sowie ein Flag (first), um die Notwendigkeit der nächsten Prozeßgenerierung zu erkennen. Die Variable QUIT muß eingeführt werden, da MPS die Versendung von Konstanten nicht gestattet.
Das zu simulierende Parallelprogramm muß unter einem Namen mit der Endung `.mod´ abgespeichert werden, hier zum Beispiel `Sieve.mod´. Anschließend kann es mit dem M2A-System normal, das heißt ohne Optionen, übersetzt und gelinkt werden.
Der Aufruf zur Programmausführung kann in drei Formen erfolgen: Mit `Sieve´ allein werden nur die benutzereigenen Ausgaben erzeugt, in diesem Fall `2 is a prime´ und so fort. Beim Aufruf
Sieve TRACEwerden zusätzlich Trace-Informationen ausgegeben, die die Prozeßsteuerung des Simulators und den Botschaftsaustausch protokollieren. Hierbei sind folgende Meldungen möglich:
CRT pn:
Prozeß mit Nummer pn wird generiert
SND mn: cp -> pn
Nachricht mit Nummer mn wird vom aktuellen Prozeß cp an Prozeß pn verschickt
RCV mn: pn -> cp
aktueller Prozeß cp empfängt Nachricht mit Nummer mn von Prozeß pn
STP cp -> pn
Prozeß cp wird beendet und die Kontrolle an Prozeß pn abgegeben
Pass cp -> pn
die Kontrolle wird (aufgrund eines momentan nicht ausführbaren RCV) an Prozeß pn abgegeben
Die Informationen werden jeweils dann ausgegeben, wenn die entsprechende MPS-Prozedur beendet wurde. Bei einem RCV jedoch erfolgt die Meldung erst, wenn das zugehörige SND bereits ausgeführt wurde und somit auch das RCV ausgeführt werden konnte, und nicht unbedingt schon dann, wenn der aktuelle Prozeß auf das RCV läuft. Die Reihenfolge, in der die Trace-Meldungen erscheinen, hängt also von der Strategie ab, nach der das Simulationssystem die Prozesse bedient. Diese Abfolge entspricht in aller Regel nicht der zeitlichen Reihenfolge der Abarbeitung auf einem realen Parallelrechner.
Der Programmaufruf mit
Sieve MAPerzeugt eine inhaltlich ähnliche Ausgabe, bei der jedoch den einzelnen Prozessen (bis zu 8) Spalten zugeordnet sind, zwischen denen ein Botschaftsaustausch (SND und ausführbares RCV) sowie Prozeßwechsel oder -generierung (CRT, STP und nicht ausführbares RCV) mit Pfeilen dargestellt werden (siehe Bild).
Bei der Entwicklung von MPS mußten die beiden folgenden Aspekte berücksichtigt werden, um eine Parallelrechner-Simulation zu realisieren:
Jeder Prozeß hat einen eigenen Datenbereich, auf den ein Zugriff zugelassen sein muß, wenn der Prozeß aktiv ist. Wenn also zu einem bestimmten Zeitpunkt der Code eines bestimmten Prozesses abgearbeitet wird, muß dieser auf seinen eigenen Datenbereich zugreifen können, während die Daten anderer Prozesse für ihn nicht zugänglich sein dürfen.
Die Einrichtung solcher lokalen Datenbereiche sieht bereits die Coroutines-Prozedur NEWPROCESS vor. Dieser Prozedur wird neben dem Namen der Prozedur, die von dem neuen Prozeß bearbeitet werden soll, auch ein Speicherbereich übergeben, in dem die prozeßeigenen Daten abgelegt werden. Diese NEWPROCESS-Prozedur bildet den Kern der MPS-Prozedur CRT.
Irgendwann läuft nun der Master auf ein RCV (sonst ist das Parallelprogramm sinnlos). Da bisher kein anderer Prozeß (vom Simulator) aktiviert wurde, kann auch keine Nachricht an den Master abgeschickt worden sein (der recht sinnlose Fall, daß ein Prozeß etwas an sich selbst schickt, sei hier vernachlässigt). Das bedeutet aber, daß das RCV des Master nicht ausgeführt werden kann. Sobald MPS dies erkennt, initiiert es einen Prozeßwechsel, das heißt, der Datenbereich des nächsten Prozesses wird quasi in den Vordergrund geblendet und die Abarbeitung des Codes dieses Prozesses begonnen.
Ein derartiger Prozeßwechsel tritt nun aber auch auf, wenn das Programm erneut auf ein nicht ausführbares RCV oder auf ein STP läuft. In diesem Fall muß der Prozeß, auf den umgeschaltet wurde, genau an dem Punkt fortgesetzt werden, an dem er bei seiner letzten Desaktivierung angelangt war. Dies übernimmt im wesentlichen die Coroutines-Prozedur TRANSFER, die dann automatisch aufgerufen wird.
Alle zu jedem Zeitpunkt existierenden Prozesse sind in einer verketteten Ringliste festgehalten. Durch ein CRT wird ein neues Glied darin eingefügt und durch ein STP ein Glied entfernt. Die Bedienung der Prozesse geschieht in der Reihenfolge, in der sie in dieser Liste angeordnet, das heißt kreiert worden sind. Die Prozeßnummern sind in dieser Beziehung nicht von Bedeutung.
Wenn ein Prozeß auf ein SND läuft, wird der übergebene Datenbereich - egal ob Record, Array oder einfaches Objekt - in einem anderen Speicherbereich festgehalten und dies in der verketteten Liste einschließlich Informationen über Nachrichtennummer, sendenden und empfangenden Prozeß registriert.
Läuft nun ein anderer (oder derselbe) Prozeß auf ein entsprechendes RCV - oder anders gesag: stimmen also die dem RCV übergebenen Parameter über Nachrichtennummer und sendenden Prozeß sowie die aktuelle Prozeßnummer mit den Informationen eines Elementes in der verketteten Liste überein, so wird der entsprechende Datenbereich in den des Empfangsprozesses kopiert. Gleichzeitig wird er im Zwischenspeicher wie auch in der verketteten Liste gelöscht. Wird ein solches Element nicht gefunden, muß ein Prozeßwechsel erfolgen.
Eine mögliche Erweiterung von MPS wäre die zeitliche Simulation des parallelen Ablaufs. Hierbei könnte das System so erweitert werden, daß es Angaben über das Ineinandergreifen der Prozesse liefert (wann führt ein Prozeß eine bestimmte Aktion aus, wie lange muß ein Prozeß auf das Eintreffen einer Nachricht warten usw.). Dies würde quantitative Aussagen über die Güte eines parallelen Algorithmus beziehungsweise seiner Implementierung auf einem realen Parallelrechner erlauben.
Doch auch so bietet MPS viele Möglichkeiten des Experimentierens mit parallelen Programmen. (bb)
[2] C. A. R. Hoare, Communicating Sequential Processes, Prentice-Hall, London 1985
[3] Achim Scharf, Neue Ufer, c't 11/89, S. 74
[4] Ulrich Trottenberg, Der Suprenum-Rechner, c't 8/88, S. 150
CRT
Die Create-Prozedur dient zur Generierung eines Slave-Prozesses. Mit den Parametern definiert der Benutzer den Code, den dieser Prozeß abarbeiten soll, und die Nummer, unter der der generierte Prozeß angesprochen werden kann.
Alle Prozesse müssen numeriert werden, um sie beim Botschaftsaustausch adressieren zu können. Der Master-Prozeß hat die Nummer 0; die Slave-Numerierung besteht aus natürlichen Zahlen (sie sollte aus Gründen der Übersichtlichkeit - muß aber nicht - fortlaufend von 1 bis NumberOfProcesses sein). In einem Parallelprogramm können zwei Prozesse nicht mit derselben Nummer kreiert werden.
SND
Die Send-Prozedur dient zum Verschicken von Daten an einen Prozeß. Diese Daten müssen in einem Datenobjekt beliebigen Typs stehen; es sind also auch Arrays und Records zugelassen.
Jede Botschaft erhält eine Nummer, damit der empfangende Prozeß auch zwei vom selben Prozeß abgeschickte Botschaften unterscheiden kann. Ein Prozeß darf nicht eine zweite Botschaft mit derselben Nummer an denselben Prozeß abschicken, solange die erste nicht von dem empfangenden Prozeß eingelesen wurde.
Ist der zweite Parameter negativ, so erfolgt die Verschickung an alle existierenden Prozesse außer an den Master und den sendenden Prozeß selbst; diese Kommunikationsform nennt man Broadcast.
RCV
Die Receive-Prozedur dient zum Empfangen von Daten, die von einem anderen (oder auch demselben) Prozeß abgeschickt wurden. Diese Daten werden in ein Datenobjekt beliebigen Typs eingelesen.
Auch hier ist für den zweiten Parameter ein eigentlich unsinniger Wert kleiner als 0 erlaubt. Dieser bewirkt, daß die Prozeßnummer des Senders nicht relevant ist, das heißt, es wird die erste vorliegende oder als nächstes eintreffende Botschaft mit der passenden Nummer eingelesen. Diese Technik läßt sich sinnvoll etwa beim Einsammeln von mehreren Nachrichten anwenden, bei denen es auf die Reihenfolge des Einlesens nicht ankommt.
Zu jedem Send gehört ein Receive und umgekehrt; in einem Parallelprogramm müssen alle abgeschickten und zu empfangenden Botschaften zueinander passen. Bei der Abarbeitung des Programms müssen folglich immer Paare von SND- und RCV-Prozeduraufrufen auftreten, die bezüglich ihrer Parameter korrespondieren. Ansonsten liegt ein Fehler in der Kommunikationsstruktur vor. Derartige Fehler werden weitestgehend von MPS erkannt und in Form von Requestern angezeigt, die - falls es möglich ist - fortgesetzt oder abgebrochen werden können.
STP
Die Stop-Prozedur dient zum Beenden eines Slave-Prozesses.
Die Slaves sind nicht nur insofern eigenständig, als sie eigene Daten besitzen; sie können mit einer Ausnahme auch nicht von einem anderen Prozeß gestoppt werden. Daher ist die STP-Prozedur notwendig, die das Ende des Slave-Prozesses markiert; es handelt sich somit um das Gegenstück zur CRT-Prozedur. (Die erwähnte Ausnahme ist das Beenden des gesamten Parallelprogramms, indem der Master-Prozeß auf sein Ende läuft.)
Diese Variable enthält die Nummer des aktuellen Prozesses, also im Falle des Masters 0, sonst einen ganzzahligen Wert größer als 0.
NumberOfProcesses
Diese Variable enthält die Anzahl der gerade existierenden Prozesse (einschließlich des Masters). Der Wert ist zeitabhängig und daher mit Vorsicht zu verwenden.
1 (************************************************************************ 2 Modul : MPS.def 3 Funktion : Definition der MPS-Prozeduren und -Variablen 4 Rechner : Amiga 5 Compiler : M2Amiga V3.2d 6 Autor : Frank Strauß 7 ************************************************************************) 8 9 DEFINITION MODULE MPS; 10 11 FROM SYSTEM IMPORT ADDRESS; 12 13 VAR CurrentProcess: INTEGER; (* Nummer des laufenden Prozesses *) 14 NumberOfProcesses: INTEGER; (* Anzahl der bestehenden Prozesse *) 15 16 (************************************************************************ 17 CRT (create) : richtet die Prozedur "procedure" als Prozeß mit der 18 Nummer "ip" ein *) 19 20 PROCEDURE CRT (procedure: PROC; ip: INTEGER); 21 22 (************************************************************************ 23 SND (send) : verschickt den Datenbereich beginnend bei der Adresse 24 "data" mit der Länge "len" als Nachricht mit 25 der Nummer "mn" an den Prozeß mit der Nummer "ip" *) 26 27 PROCEDURE SND (mn, ip: INTEGER; data: ADDRESS; len: LONGINT); 28 29 (************************************************************************ 30 RCV (receive) : empfängt die Nachricht mit der Nummer "mn", die vom 31 Prozeß mit der Nummer "ip" abgeschickt wurde und 32 speichert diese im Datenbereich beginnend bei 33 der Adresse "data" mit der Länge "len" *) 34 35 PROCEDURE RCV (mn, ip: INTEGER; data: ADDRESS; len: LONGINT); 36 37 (************************************************************************ 38 STP (stop) : schließt den laufenden Prozeß ab *) 39 40 PROCEDURE STP; 41 42 END MPS.Kasten 3
1 MODULE Sieve;
3 FROM InOut IMPORT WriteString, WriteInt, WriteLn, ReadInt;
4
5 FROM MPS IMPORT CRT, SND, RCV, STP, CurrentProcess;
6
7 FROM SYSTEM IMPORT ADR;
8
9 VAR maxNr, i, QUIT: INTEGER;
10 p, sCounter: INTEGER;
11
12 PROCEDURE Pipeline;
13 VAR processNr, predecessor, successor, myPrime, Nr: INTEGER;
14 rCounter, sCounter: INTEGER;
15 first: BOOLEAN;
16 BEGIN
17 predecessor := CurrentProcess-1;
18 successor := CurrentProcess+1;
19 rCounter := 1;
20 sCounter := 1;
21 RCV (rCounter, predecessor, ADR(myPrime), SIZE(myPrime));
22 INC (rCounter);
23 SND (myPrime, 0, ADR(myPrime), SIZE(myPrime));
24 first := TRUE;
25 LOOP
26 RCV (rCounter, predecessor, ADR(Nr), SIZE(Nr));
27 INC (rCounter);
28 IF Nr#0 THEN
29 IF (Nr MOD myPrime)=0 THEN
30 Nr := -Nr;
31 SND (-Nr, 0, ADR(Nr), SIZE(Nr));
32 ELSE
33 IF first THEN
34 CRT (Pipeline, successor);
35 first := FALSE;
36 END;
37 SND (sCounter, successor, ADR(Nr), SIZE(Nr));
38 INC (sCounter);
39 END;
40 ELSE
41 IF NOT first THEN
42 SND (sCounter, successor, ADR(QUIT), SIZE(QUIT));
43 INC (sCounter);
44 ELSE
45 SND (0, 0, ADR(QUIT), SIZE(QUIT));
46 END;
47 EXIT;
48 END;
49 END;
50 STP;
51 END Pipeline;
52
53 BEGIN
54 QUIT := 0;
55 WriteString ("maxNr: ");
56 ReadInt (maxNr);
57 WriteLn;
58 CRT (Pipeline, 1);
59 sCounter := 1;
60 FOR i := 2 TO maxNr DO
61 SND (sCounter, 1, ADR(i), SIZE(i));
62 INC (sCounter);
63 END;
64 SND (sCounter, 1, ADR(QUIT), SIZE(QUIT));
65 INC (sCounter);
66 FOR i := 2 TO maxNr DO
67 RCV (i, -1, ADR(p), SIZE(p));
68 IF p>0 THEN
69 WriteInt(p, 6); WriteString(" is a prime"); WriteLn();
70 END;
71 END;
72 RCV (0, -1, ADR(QUIT), SIZE(QUIT));
73 END Sieve.
Kasten 4
1 (************************************************************************
2 Modul : MPS.mod
3 Funktion : Implementation der MPS-Prozeduren
4 Rechner : Amiga
5 Compiler : M2Amiga V3.2d
6 Autor : Frank Strauß
7 ************************************************************************)
8
9 IMPLEMENTATION MODULE MPS;
10
11
12 FROM SYSTEM IMPORT ADDRESS, ADR;
13
14 FROM Heap IMPORT Allocate, Deallocate;
15
16 FROM Exec IMPORT CopyMem;
17
18 FROM Coroutines IMPORT NEWPROCESS, TRANSFER, PROCESS;
19
20 FROM InOut IMPORT WriteString, WriteInt, WriteLn;
21
22 FROM Arts IMPORT Assert, Terminate;
23
24 FROM Intuition IMPORT IntuiText, AutoRequest, IDCMPFlagSet, IDCMPFlags;
25
26 FROM Graphics IMPORT jam1, jam2;
27
28 FROM Arguments IMPORT NumArgs, GetArg;
29
30 FROM Strings IMPORT Compare;
31
32 FROM Conversions IMPORT StrToVal;
33
34 CONST Workspace = 10000; (* Arbeitsspeichergroeße jedes Prozesses *)
35
36 TYPE ProcessPtr = POINTER TO ProcessType;
37
38 ProcessType = RECORD
39 pn: INTEGER; (* Nummer des Prozesses *)
40 process: PROCESS; (* prozeßcharakterisierende Adr *)
41 next: ProcessPtr; (* Pointer auf nächsten Prozeß *)
42 END;
43
44 MsgPtr = POINTER TO MsgType;
45
46 MsgType = RECORD
47 mn: INTEGER; (* Nummer der Nachricht *)
48 s: INTEGER; (* Absender der Nachricht *)
49 r: INTEGER; (* Empfänger der Nachricht *)
50 data: ADDRESS; (* Anfangsadresse des Datenbereichs *)
51 next: MsgPtr; (* Pointer auf nächste Nachricht *)
52 END;
53
54 VAR Trace, Map: BOOLEAN; (* Flags für Trace- und Map-Ausgaben *)
55 Deadlock: INTEGER; (* Zähler zur Erkennung eines Deadlock *)
56 FirstProcess: ProcessPtr; (* Pointer auf ersten Prozeß in Liste *)
57 LastProcess: ProcessPtr; (* Pointer auf letzten Prozeß in Liste *)
58 FirstMsg: MsgPtr; (* Pointer auf erste Nachricht in Liste *)
59
60 len, i: INTEGER;
61 help: LONGINT;
62 str: ARRAY [0..5] OF CHAR;
63 err, sign: BOOLEAN;
64
65 (************************************************************************
66 MPS-Warning Requester *)
67
68 PROCEDURE Warning (adr: ADDRESS);
69
70 VAR erg: BOOLEAN;
71 text, text2, postext, negtext: IntuiText;
72
73 BEGIN
74 WITH text DO
75 frontPen := 0;
76 backPen := 1;
77 drawMode := jam1;
78 leftEdge := 17;
79 topEdge := 6;
80 iTextFont := NIL;
81 iText := ADR("MPS Warning");
82 nextText := ADR(text2);
83 END;
84 WITH text2 DO
85 frontPen := 0;
86 backPen := 1;
87 drawMode := jam1;
88 leftEdge := 17;
89 topEdge := 18;
90 iTextFont := NIL;
91 iText := adr;
92 nextText := NIL;
93 END;
94 WITH postext DO
95 frontPen := 0;
96 backPen := 1;
97 drawMode := jam2;
98 leftEdge := 7;
99 topEdge := 4;
100 iTextFont := NIL;
101 iText := ADR(" fortsetzen ");
102 nextText := NIL;
103 END;
104 WITH negtext DO
105 frontPen := 0;
106 backPen := 1;
107 drawMode := jam2;
108 leftEdge := 7;
109 topEdge := 4;
110 iTextFont := NIL;
111 iText := ADR(" abbrechen ");
112 nextText := NIL;
113 END;
114 erg := AutoRequest (NIL, ADR(text), ADR(postext), ADR(negtext),
115 IDCMPFlagSet{}, IDCMPFlagSet{}, 320, 70);
116 IF NOT erg THEN
117 Terminate (0);
118 END;
119 END Warning;
120
121 (************************************************************************
122 Kann ein Prozeß nicht weiterarbeiten, so gibt diese Prozedur die
123 Kontrolle an den in der Prozeßliste folgenden Prozeß ab *)
124
125 PROCEDURE Pass;
126
127 VAR helpprocessptr: ProcessPtr;
128
129 BEGIN
130 (* wurden alle Prozesse einmal durchlaufen, ohne daß einer von
131 ihnen weiterarbeiten konnte, so wird mit einer Deadlock-Meldung
132 abgebrochen *)
133 Assert (NOT (NumberOfProcesses<Deadlock), ADR("Deadlock!"));
134 helpprocessptr := FirstProcess;
135
136 (* Aufsuchen des nächsten Prozesses anhand der Prozeßliste *)
137 WHILE (helpprocessptr^.pn#CurrentProcess) DO
138 helpprocessptr := helpprocessptr^.next;
139 END;
140 CurrentProcess := helpprocessptr^.next^.pn;
141
142 (* optionale Trace-Ausgabe *)
143 IF Trace THEN
144 WriteString ("Pass "); WriteInt (helpprocessptr^.pn, 2);
145 WriteString (" -> "); WriteInt (CurrentProcess, 2); WriteLn;
146 END;
147
148 (* optionale Map-Ausgabe *)
149 IF Map THEN
150 IF helpprocessptr^.pn<CurrentProcess THEN
151 FOR i := 1 TO 4+8*helpprocessptr^.pn DO WriteString (" "); END;
152 FOR i := 1 TO 8*(CurrentProcess-helpprocessptr^.pn-1) DO
153 WriteString ("-");
154 END;
155 WriteString ("-------->");
156 ELSE
157 WriteString (" <");
158 FOR i := 1 TO 8*helpprocessptr^.pn DO WriteString ("-"); END;
159 END;
160 WriteLn;
161 END;
162 (* Umschaltung auf den in der Prozeßliste folgenden Prozeß *)
163 TRANSFER (helpprocessptr^.process, helpprocessptr^.next^.process);
164
165 END Pass;
166
167 (************************************************************************
168 CRT richtet die Prozedur "procedure" als Prozeß
169 mit der Nummer "ip" ein *)
170
171 PROCEDURE CRT (procedure: PROC; ip: INTEGER);
172
173 VAR workspaceptr: ADDRESS;
174 helpprocessptr: ProcessPtr;
175 error: BOOLEAN;
176
177 BEGIN
178 (* Überprüfung, ob die zu generierende Prozeßnummer bereits
179 existiert *)
180 helpprocessptr := FirstProcess;
181 error := FALSE;
182 REPEAT
183 IF ip=helpprocessptr^.pn THEN error := TRUE; END;
184 helpprocessptr := helpprocessptr^.next;
185 UNTIL error OR (helpprocessptr=FirstProcess);
186 Assert (NOT error, ADR("Prozessnr. exisistiert bereits!"));
187
188 (* Bereitstellen des Arbeitsspeichers des neuen Prozesses *)
189 Allocate (workspaceptr, Workspace);
190 Assert (workspaceptr#NIL, ADR("Nicht genug Speicher beim CRT!"));
191
192 (* Eintragen des neuen Prozesses in die Prozeßliste *)
193 Allocate (LastProcess^.next, SIZE(ProcessType));
194 Assert (LastProcess^.next#NIL, ADR("Nicht genug Speicher beim CRT!"));
195 LastProcess^.next^.pn := ip;
196 LastProcess^.next^.next := FirstProcess;
197 NEWPROCESS (procedure, workspaceptr, Workspace,
198 LastProcess^.next^.process);
199 LastProcess := LastProcess^.next;
200 INC (NumberOfProcesses);
201
202 (* optionale Trace-Ausgabe *)
203 IF Trace THEN
204 WriteString ("CRT "); WriteInt (ip, 2); WriteLn;
205 END;
206 (* optionale Map-Ausgabe *)
207 IF Map THEN
208 IF CurrentProcess<ip THEN
209 FOR i := 1 TO 3+CurrentProcess*8 DO WriteString (" "); END;
210 WriteString ("CRT");
211 FOR i := 3 TO (ip-CurrentProcess)*8 DO WriteString ("-"); END;
212 WriteString (">");
213 ELSE
214 FOR i := 1 TO 4+ip*8 DO WriteString (" "); END;
215 WriteString ("<");
216 FOR i := 3 TO (CurrentProcess-ip)*8 DO WriteString ("-"); END;
217 WriteString ("CRT");
218 END;
219 WriteLn;
220 END;
221
222 END CRT;
223
224 (************************************************************************
225 SND verschickt den Datenbereich beginnend bei der Adresse "data" mit
226 der Länge "len" als Nachricht mit der Nummer "mn" an den Prozeß
227 mit der Nummer "ip" *)
228
229 PROCEDURE SND (mn, ip: INTEGER; data: ADDRESS; len: LONGINT);
230
231 VAR helpmsgptr, help2msgptr, newmsgptr: MsgPtr;
232 msgdata: ADDRESS;
233 iphelp: CARDINAL;
234 helpprocessptr: ProcessPtr;
235 error: BOOLEAN;
236
237 BEGIN
238 (* MPS Warning, falls der Prozeß an sich selbst sendet *)
239 IF ip=CurrentProcess THEN
240 Warning (ADR("Sender = Empfänger!"));
241 END;
242 (* Überprüfung, ob der Empfänger existiert *)
243 helpprocessptr := FirstProcess;
244 error := TRUE;
245 REPEAT
246 IF ip=helpprocessptr^.pn THEN error := FALSE; END;
247 helpprocessptr := helpprocessptr^.next;
248 UNTIL (NOT error) OR (helpprocessptr=FirstProcess);
249 IF error THEN
250 Warning (ADR("Zielprozessnr. exisistiert nicht!"));
251 END;
252
253 helpmsgptr := FirstMsg;
254 WHILE (helpmsgptr#NIL) AND (helpmsgptr^.next#NIL) DO
255 helpmsgptr := helpmsgptr^.next;
256 END;
257 iphelp := ip;
258 helpprocessptr := FirstProcess;
259 LOOP
260 (* bei negativer Empfängerprozeßnummer wird an alle existierenden
261 Prozesse außer den Master und den Absender die Nachricht
262 verschickt *)
263 IF iphelp<0 THEN
264 WHILE ((helpprocessptr^.pn=0) OR
265 (helpprocessptr^.pn=CurrentProcess)) AND
266 ((ip<0) OR (helpprocessptr#FirstProcess)) DO
267 helpprocessptr := helpprocessptr^.next;
268 ip := helpprocessptr^.pn;
269 END;
270 END;
271
272 IF ((ip>=1) AND (ip#CurrentProcess)) OR (iphelp>=0) THEN
273 (* MPS Warning, falls bereits eine Nachricht mit gleicher Nummer,
274 gleichem Absender und gleichem Empfänger vorliegt *)
275 help2msgptr := FirstMsg;
276 WHILE (help2msgptr#NIL) AND NOT ((help2msgptr^.mn=mn) AND
277 (help2msgptr^.s=CurrentProcess) AND (help2msgptr^.r=ip)) DO
278 help2msgptr := help2msgptr^.next;
279 END;
280 IF help2msgptr#NIL THEN
281 Warning (ADR("SND existiert bereits!"));
282 END;
283 (* Bereitstellen des Datenbereiches der Nachricht *)
284 Allocate (newmsgptr, SIZE(MsgType));
285 Assert (newmsgptr#NIL, ADR("Nicht genug Speicher beim SND!"));
286
287 (* Eintragen der Nachricht in die Nachrichtenliste *)
288 IF helpmsgptr#NIL THEN
289 helpmsgptr^.next := newmsgptr;
290 ELSE
291 FirstMsg := newmsgptr;
292 END;
293 helpmsgptr := newmsgptr;
294 newmsgptr^.mn := mn;
295 newmsgptr^.s := CurrentProcess;
296 newmsgptr^.r := ip;
297 Allocate (msgdata, len);
298 Assert (msgdata#NIL, ADR("Nicht genug Speicher beim SND!"));
299 CopyMem (data, msgdata, len);
300 newmsgptr^.data := msgdata;
301 newmsgptr^.next := NIL;
302
303 (* optionale Trace-Ausgaben *)
304 IF Trace THEN
305 WriteString ("SND "); WriteInt (mn, 2); WriteString (": ");
306 WriteInt (CurrentProcess, 2); WriteString (" -> ");
307 WriteInt (ip, 2); WriteLn;
308 END;
309 (* optionale Map-Ausgaben *)
310 IF Map THEN
311 IF CurrentProcess<ip THEN
312 FOR i := 1 TO 3+CurrentProcess*8 DO WriteString (" "); END;
313 WriteString ("S"); WriteInt (mn, 2);
314 FOR i := 3 TO (ip-CurrentProcess)*8 DO WriteString ("="); END;
315 WriteString (">");
316 ELSE
317 FOR i := 1 TO 4+ip*8 DO WriteString (" "); END;
318 WriteString ("<");
319 FOR i := 3 TO (CurrentProcess-ip)*8 DO WriteString ("="); END;
320 WriteString ("S"); WriteInt (mn, 2);
321 END;
322 WriteLn;
323 END;
324 END;
325 IF iphelp>=0 THEN EXIT END;
326 helpprocessptr := helpprocessptr^.next;
327 IF helpprocessptr=FirstProcess THEN EXIT END;
328 END;
329
330 END SND;
331
332 (************************************************************************
333 RCV empfängt die Nachricht mit der Nummer "mn", die vom Prozeß mit der
334 Nummer "ip" abgeschickt wurde und speichert diese im Datenbereich
335 beginnend bei der Adresse "data" mit der Länge "len" *)
336
337 PROCEDURE RCV (mn, ip: INTEGER; data: ADDRESS; len: LONGINT);
338
339 VAR helpprocessptr: ProcessPtr;
340 helpmsgptr, lastmsgptr: MsgPtr;
341 RCVok, error: BOOLEAN;
342
343 BEGIN
344 (* RCV solange durchlaufen, bis Nachricht empfangen werden konnte *)
345 RCVok := FALSE;
346 REPEAT
347 (* Suchen der Nachricht in der Nachrichtenliste *)
348 helpmsgptr := FirstMsg;
349 WHILE (helpmsgptr#NIL) AND ((helpmsgptr^.mn#mn) OR
350 ((helpmsgptr^.s#ip) AND (ip>=0)) OR
351 (helpmsgptr^.r#CurrentProcess)) DO
352 lastmsgptr := helpmsgptr;
353 helpmsgptr := helpmsgptr^.next;
354 END;
355 (* Nachricht empfangen, falls gefunden *)
356 IF helpmsgptr#NIL THEN
357 ip := helpmsgptr^.s;
358 CopyMem (helpmsgptr^.data, data, len);
359 IF helpmsgptr#FirstMsg THEN
360 lastmsgptr^.next := helpmsgptr^.next;
361 Deallocate (helpmsgptr);
362 ELSE
363 FirstMsg := helpmsgptr^.next;
364 Deallocate (helpmsgptr);
365 END;
366 RCVok := TRUE;
367
368 (* optionale Trace-Ausgaben *)
369 IF Trace THEN
370 WriteString ("RCV "); WriteInt (mn, 2); WriteString (": ");
371 WriteInt (ip, 2); WriteString (" -> ");
372 WriteInt (CurrentProcess, 2); WriteLn;
373 END;
374 (* optionale Map-Ausgaben *)
375 IF Map THEN
376 IF CurrentProcess<ip THEN
377 FOR i := 1 TO 3+CurrentProcess*8 DO WriteString (" "); END;
378 WriteString ("R"); WriteInt (mn, 2); WriteString ("<");
379 FOR i := 3 TO (ip-CurrentProcess)*8 DO WriteString ("="); END;
380 ELSE
381 FOR i := 1 TO 4+ip*8 DO WriteString (" "); END;
382 FOR i := 3 TO (CurrentProcess-ip)*8 DO WriteString ("="); END;
383 WriteString (">R"); WriteInt (mn, 2);
384 END;
385 WriteLn;
386 END;
387 ELSE
388 (* da die Nachricht nicht empfangen werden konnte, ... *)
389 IF ip>=0 THEN
390 (* ... wird eine MPS Warning ausgegeben, falls der Absender gar
391 nicht existiert *)
392 helpprocessptr := FirstProcess;
393 error := TRUE;
394 REPEAT
395 IF ip=helpprocessptr^.pn THEN error := FALSE; END;
396 helpprocessptr := helpprocessptr^.next;
397 UNTIL (NOT error) OR (helpprocessptr=FirstProcess);
398 IF error THEN
399 Warning (ADR("Sendeprozeßnr. exisistiert nicht!"));
400 END;
401 END;
402 (* ... oder die Kontrolle an den nächsten Prozeß abgegeben *)
403 INC (Deadlock);
404 Pass;
405 END;
406 UNTIL RCVok;
407 Deadlock := 0;
408
409 END RCV;
410
411 (************************************************************************
412 STP schließt den laufenden Prozeß ab *)
413
414 PROCEDURE STP;
415
416 VAR helpprocessptr, lastprocessptr: ProcessPtr;
417 helpprocess: ProcessType;
418 helppn: INTEGER;
419
420 BEGIN
421 (* der Master kann nicht mit STP beendet werden *)
422 Assert (CurrentProcess#0, ADR("STP für Master nicht moeglich!"));
423
424 (* Prozeß aus der Prozeßliste loeschen *)
425 helppn := CurrentProcess;
426 helpprocessptr := FirstProcess;
427 WHILE (helpprocessptr^.pn#CurrentProcess) DO
428 lastprocessptr := helpprocessptr;
429 helpprocessptr := helpprocessptr^.next;
430 END;
431 helpprocessptr := helpprocessptr^.next;
432 Deallocate (lastprocessptr^.next);
433 lastprocessptr^.next := helpprocessptr;
434 CurrentProcess := helpprocessptr^.pn;
435
436 (* optionale Trace-Ausgaben *)
437 IF Trace THEN
438 WriteString ("STP "); WriteInt (helppn, 2);
439 WriteString (" -> "); WriteInt (CurrentProcess, 2); WriteLn;
440 END;
441 (* optionale Map-Ausgaben *)
442 IF Map THEN
443 IF helppn<CurrentProcess THEN
444 FOR i := 1 TO 3+8*helppn DO WriteString (" "); END;
445 WriteString ("STP");
446 FOR i := 1 TO 8*(CurrentProcess-helppn-1) DO
447 WriteString ("-"); END;
448 WriteString ("------>");
449 ELSE
450 WriteString (" <");
451 FOR i := 1 TO 8*helppn-2 DO WriteString ("-"); END;
452 WriteString ("STP");
453 END;
454 WriteLn;
455 END;
456 DEC (NumberOfProcesses);
457
458 (* Kontrolle an den nächsten Prozeß abgeben *)
459 TRANSFER (helpprocess.process, helpprocessptr^.process);
460
461 END STP;
462
463 BEGIN
464
465 (**************** Behandlung der Argumente für Trace-Ausgaben **********)
466 Trace := FALSE; Map := FALSE;
467 IF NumArgs()>0 THEN
468 GetArg (1, str, len);
469 IF (Compare(str, 0, 5, "TRACE", FALSE)=0) AND (len=5) THEN
470 Trace := TRUE;
471 ELSIF (Compare(str, 0, 3, "MAP", FALSE)=0) AND (len=3) THEN
472 Map := TRUE;
473 FOR i := 0 TO 8 DO
474 WriteInt (i, 5); WriteString (" ");
475 END;
476 WriteLn;
477 END;
478 END;
479
480 (********************** Einrichten des Master-Prozesses ****************)
481 Allocate (FirstProcess, SIZE(ProcessType)); (* der Master-Prozeß ist *)
482 FirstProcess^.next := FirstProcess; (* der erste, in der Pro-*)
483 FirstProcess^.pn := 0; (* zeßliste eingetragene,
484 Prozeß
485 *************************** Initialisierung ***************************)
486 LastProcess := FirstProcess; (* letzter = erster Prozeß *)
487 CurrentProcess := 0; (* momentaner Prozeß = Master *)
488 FirstMsg := NIL; (* noch keine Nachrichten *)
489 Deadlock := 0; (* Deadlock-Zähler auf Null *)
490 NumberOfProcesses := 1; (* Master = einziger Prozeß *)
491
492 END MPS.