Ein Modell für ein Timesharing-System

Dieser Abschnitt beschreibt ein Modell eines Timesharing-Systems, das ich für besonders geeignet halte, Interprozesskommunikation durchzuführen. Die Grundstruktur dieses Modell-Timesharing-Systems ist nicht originell [5][9].

Das Modell-Timesharing-System besteht aus zwei Teilen: dem Monitor und den Prozessen. Der Monitor erfüllt mehrere Funktionen, darunter die Steuerung nach Bedarf von einem Prozess zum nächsten weiterzugeben (etwa wenn ein Prozess „genügend“ Zeit verbraucht hat oder wenn ein Interrupt auftritt), den Kernspeicher und das Auslagerungsmedium zu verwalten, die Weitergabe der Steuerung von einem Prozess an einen anderen zu kontrollieren (d. h. Schutzmechanismen), Prozesse zu erzeugen, sich um schlafende Prozesse zu kümmern usw.

Die Prozesse erfüllen den größten Teil der Funktionen, die in einem Timesharing-System üblicherweise als Supervisorfunktionen gelten (Systemprozesse), sowie die normalen Benutzerfunktionen (Benutzerprozesse). Ein typischer Systemprozess ist der Plattenhandler oder das Dateisystem. Aus Effizienzgründen kann es nützlich sein, sich Systemprozesse als im Kernspeicher festgehalten vorzustellen.

Ein Prozess kann den Monitor um mehrere Funktionen bitten: einen weiteren, gleichrangigen, autonomen Prozess zu starten (d. h. ein Programm zu laden oder irgendwo eine Kopie eines Programms zu finden, die geteilt werden kann, es zu starten und ihm einige Anfangsparameter zu übergeben); den laufenden Prozess anzuhalten; den aktuellen Prozess bis zum Eintreten eines bestimmten Ereignisses schlafen zu legen; einem bestimmten Prozess eine Nachricht zu senden; sich zum Empfang einer Nachricht von einem bestimmten Prozess bereit zu machen; sich zum Empfang einer Nachricht von irgendeinem Prozess bereit zu machen; einem Prozess, der von irgendeinem Prozess empfangen kann, eine Nachricht zu senden; und eine eindeutige Nummer anzufordern. Zweifellos sollte es auch andere Monitorfunktionen geben. Es bleibt dem Leser als Übung überlassen, sich davon zu überzeugen, dass der Monitor, mit dem er sich herumschlagen muss, diese Funktionen bereitstellen kann - die meisten können es.

Mit Schutzbetrachtungen will ich mich hier nicht befassen, sondern stattdessen annehmen, dass alle Prozesse „gute“ Prozesse sind, die niemals Fehler machen. Wenn der Leser eine Schutzstruktur im Kopf behalten möchte, während er diese Notiz liest, sollte das in [5][6][7][8] beschriebene capability-System befriedigend sein.

Wir sehen uns nun die oben aufgeführten acht Operationen, um die ein Prozess den Monitor bitten kann, etwas genauer an.

START. Diese Operation startet einen weiteren Prozess. Sie hat zwei Parameter - irgendeine Art von Kennung für das zu ladende Programm und eine Parameterliste für dieses Programm. Sobald das Programm geladen ist, wird es an seinem gegebenen Einstiegspunkt gestartet und seine Parameterliste wird ihm auf irgendeine wohlbekannte Weise übergeben. Der Prozess wird so lange bestehen, bis er sich selbst anhält.

HALT. Diese Operation legt den gerade laufenden Prozess schlafen, bis ein bestimmtes Ereignis abgeschlossen ist. Die Operation hat einen Parameter, nämlich das Ereignis, auf das gewartet werden soll. Beispiele für Ereignisse sind das Eintreffen eines Hardware-Interrupts, das Eintreffen einer Nachricht von einem anderen Prozess usw. Der Prozess wird beim Befehl nach dem SLEEP-Befehl wieder aufgenommen. Der Monitor legt einen Prozess niemals einseitig schlafen, außer wenn der Prozess sein Zeitquantum überschreitet.

RECEIVE. Diese Operation erlaubt einem anderen Prozess, diesem Prozess eine Nachricht zu senden. Die Operation hat vier Parameter: den Port (unten definiert), der auf die Nachricht wartet, den Port, von dem eine Nachricht angenommen wird, eine Angabe des für den Empfang der Nachricht verfügbaren Puffers und eine Übergangsadresse, wenn die Übertragung abgeschlossen ist. [Mit anderen Worten eine Interrupt-Adresse. Jeder Nachrichtenport kann verwendet werden, um Interrupts, Ereigniskanäle usw. zu ermöglichen. Der Benutzer programmiert, was er will.]

SEND. Diese Operation sendet einem anderen Prozess eine Nachricht. [Ich nehme an, ein Prozess könnte auch sich selbst eine Nachricht senden.] Sie hat vier Parameter: einen Port, an den die Nachricht gesendet wird, den Port, von dem die Nachricht gesendet wird, die Nachricht und eine Übergangsadresse, wenn die Übertragung abgeschlossen ist.

RECEIVE ANY. Diese Operation erlaubt jedem Prozess, diesem Prozess eine Nachricht zu senden. Die Operation hat vier Parameter: den Port, der auf die Nachricht wartet, den für den Empfang der Nachricht verfügbaren Puffer, eine Übergangsadresse, wenn die Nachricht empfangen ist, und eine Adresse, an der der Port vermerkt werden kann, der die Nachricht gesendet hat.

SEND FROM ANY. Diese Operation erlaubt einem Prozess, einem Prozess, der von irgendeinem Prozess empfangen kann, eine Nachricht zu senden. Sie hat dieselben vier Parameter wie SEND. Die Notwendigkeit dieser Operation wird unten erörtert.

UNIQUE. Diese Operation holt eine eindeutige Nummer vom Monitor.

Ein Port ist ein bestimmter Datenpfad zu einem Prozess hin oder von einem Prozess weg. Alle Ports haben eine zugeordnete eindeutige Nummer, mit der der Port gekennzeichnet wird. Ports werden beim Übertragen von Nachrichten von einem Prozess zu einem anderen wie folgt verwendet. Man betrachte zwei Prozesse A und B, die kommunizieren möchten. Prozess A führt am Port N von Port M aus ein RECEIVE aus.

Prozess B führt von Port M an Port N ein SEND aus. Der Monitor ordnet die Portnummern einander zu und überträgt die Nachricht von Prozess B zu Prozess A. Sobald der Puffer vollständig aus Prozess B heraus übertragen worden ist, wird Prozess B an der im SEND-Vorgang angegebenen Stelle wieder aufgenommen. Sobald die Nachricht bei Prozess A vollständig empfangen ist, wird Prozess A an der im RECEIVE-Vorgang angegebenen Stelle wieder aufgenommen. Wie die Prozesse zu den richtigen Portnummern gelangen, mit denen sie mit anderen Prozessen kommunizieren, ist nicht Sache des Monitors - dieses Problem bleibt den Prozessen überlassen.

Ein Beispiel. Angenommen, unser Modell-Timesharing-System wird so initialisiert, dass mehrere Prozesse immer laufen. Außerdem haben diese ständigen Prozesse einige allgemein bekannte und dauerhaft zugewiesene Ports. [Oder vielleicht gibt es nur einen einzigen dauerhaft bekannten Port, der einem Verzeichnisprozess gehört, welcher eine Tabelle der Zuordnungen von Dauerprozessen zu wohlbekannten Ports führt.] Angenommen, zwei der dauerhaft laufenden Prozesse sind der Anmeldeprozess und der Fernschreiber-Abtastprozess. Wenn der Fernschreiber-Abtastprozess zu laufen beginnt, legt er sich schlafen und wartet auf einen Interrupt vom Hardware-Fernschreiberabtaster. Der Anmeldeprozess legt sich zunächst schlafen und wartet auf eine Nachricht vom Fernschreiber-Abtastprozess über wohlbekannte, dauerhafte SEND- und RECEIVE-Ports. Der Fernschreiber-Abtastprozess führt eine nach Fernschreibernummer indexierte Tabelle, in der jeder Eintrag einen Port enthält, an den Zeichen von diesem Fernschreiber zu senden sind, und einen Port, an dem Zeichen für diesen Fernschreiber zu empfangen sind. Trifft ein Zeichen ein (wodurch der Fernschreiber-Abtastprozess aufgeweckt wird) und hat der Prozess für diesen Fernschreiber noch keinen Eintrag, so holt er sich ein Paar eindeutiger Nummern vom Monitor (über UNIQUE) und sendet eine Nachricht mit diesem Nummernpaar an den Anmeldeprozess, und zwar über die Ports, von denen er weiß, dass der Anmeldeprozess dort ein RECEIVE offen hat. [Tatsächlich könnte der Abtastprozess für einen bestimmten Fernschreiber immer dasselbe Portnummernpaar verwenden, solange sie nur an jeweils eine Kopie des Executives weitergegeben werden.] Der Abtastprozess trägt das Nummernpaar außerdem in die Fernschreibertabelle ein und sendet die Zeichen und alle künftigen Zeichen dieses Fernschreibers von dem Port mit der zweiten Nummer an den Port mit der ersten Nummer. Der Abtastprozess übergibt dem Anmeldeprozess wahrscheinlich auch ein zweites Paar eindeutiger Nummern, damit dieser es für die Fernschreiberausgabe verwendet, und führt mit diesen Nummern ein RECEIVE aus. Wenn der Anmeldeprozess die Nachricht vom Abtastprozess empfängt, startet er eine Kopie dessen, was die Benutzer des SDS 940 TSS [12] das Executive nennen (jenes Programm, das Dateiverzeichnisse druckt, mitteilt, wer an anderen Fernschreibern ist, Subsysteme laufen lässt usw.), und übergibt dieser Kopie des Executives die Portnummern, damit dieser Executive-Prozess seine Ein- und Ausgaben zum Fernschreiber ebenfalls über diese Ports abwickeln kann. Wenn der Anmeldeprozess vom Benutzer eine Auftragsnummer und ein Passwort erhalten möchte, kann er vorübergehend diese Portnummern verwenden, um mit dem Benutzer zu kommunizieren, bevor er sie an das Executive weitergibt.

Portnummern werden häufig zwischen Prozessen weitergegeben. Seltener wird ein Port an einen anderen Prozess übertragen. Es ist entscheidend, dass ein Prozess, sobald er einen Port an einen anderen Prozess übertragen hat, diesen Port nicht mehr verwendet. Wir könnten einen Mechanismus hinzufügen, der dies erzwingt. Das System geschützter Objekte aus [8] ist ein solcher Mechanismus. [Wenn uns das System geschützter Objekte natürlich zur Verfügung steht, besteht wirklich keine Notwendigkeit mehr, zwei Portnummern anzugeben, bevor eine Übertragung stattfinden kann. Die Tatsache, dass ein Prozess eine bestehende RECEIVE-Portnummer kennt, ist ein Anscheinsbeweis für das Recht dieses Prozesses, an diesen Port zu senden. Der Unterschied zwischen RECEIVE- und RECEIVE ANY-Ports hängt dann allein von der Anzahl der Kopien einer bestimmten Portnummer ab, die ausgegeben worden sind. Ein auf diesem Ansatz beruhendes System wäre dem hier beschriebenen eindeutig vorzuziehen, wenn man annehmen könnte, dass alle autonomen Timesharing-Systeme in einem Netz diesen Schutzmechanismus übernehmen würden. Lässt sich diese Annahme nicht treffen, so erscheint es praktischer, beide Portnummern zu verlangen.]

Man beachte, dass es irgendwo im Monitor eine Tabelle von Portnummern geben muss, die Prozessen und Wiederaufnahmestellen zugeordnet sind. Die Einträge der Tabelle werden nach jeder SEND/RECEIVE-Zuordnung gelöscht. Man beachte ferner, dass, wenn ein Prozess läuft (vielleicht schläft) und ein RECEIVE ANY offen hat, jeder Prozess, der die Empfangsportnummer kennt, mit ihm sprechen kann, ohne über Anmeldeprozesse oder dergleichen zu gehen. Dies ist innerhalb eines lokalen Timesharing-Systems offensichtlich wesentlich und erscheint in einem allgemeineren Netz sehr nützlich, wenn das Ideal der Ressourcenteilung erreicht werden soll.

Wenn ein SEND ausgeführt wird, geschieht nichts, bis ein passendes RECEIVE ausgeführt wird. Wird nicht rechtzeitig ein geeignetes RECEIVE ausgeführt, so läuft das SEND nach einer Weile ab und der sendende Prozess wird benachrichtigt. Wird ein RECEIVE ausgeführt, aber das passende SEND tritt lange nicht auf, so läuft das RECEIVE ab und der empfangende Prozess wird benachrichtigt.

Ein RECEIVE ANY läuft nie ab, kann aber zurückgezogen werden. Eine SEND FROM ANY-Nachricht wird immer sofort gesendet und verworfen, wenn kein geeigneter Empfänger existiert. Eine Fehlermeldung wird nicht zurückgesendet, und eine Bestätigung, wenn es eine gibt, liegt bei den Prozessen. Läuft die Tabelle, in der SEND und RECEIVE einander zugeordnet werden, jemals über, so wird ein Prozess, der ein weiteres SEND oder RECEIVE auslöst, benachrichtigt, genau als wäre das SEND oder RECEIVE abgelaufen.

Im Allgemeinen werden wohlbekannte, dauerhaft zugewiesene Ports über RECEIVE ANY und SEND FROM ANY verwendet. Die dauerhaften Ports werden am häufigsten zum Starten von Prozessen verwendet, und folglich werden über sie nur wenige Daten gesendet.

Noch ein Beispiel, diesmal eine Vorführung der Verwendung des FORTRAN-Compilers. Wir haben bereits erklärt, wie ein Benutzer sich an seinen Fernschreiber setzt und mit einem Executive verbunden wird. Von dort fahren wir fort. Der Benutzer gibt beim Executive ein und empfängt von ihm, das SEND und RECEIVE ausführt. Schließlich tippt der Benutzer RUN FORTRAN, und das Executive bittet den Monitor, eine Kopie des FORTRAN-Compilers zu starten, und übergibt an FORTRAN als Startparameter die beiden Ports, die das Executive für die Kommunikation mit dem Fernschreiber verwendete. FORTRAN erwartet diese Parameter natürlich und führt SEND und RECEIVE an diese Ports aus, um herauszufinden, welche Ein- und Ausgabedateien der Benutzer verwenden möchte. FORTRAN tippt INPUT FILE? an den Benutzer, der mit F001 antwortet. FORTRAN sendet dann eine Nachricht an den Dateisystemprozess, der schläft und auf eine Aufgabe wartet. Die Nachricht wird über wohlbekannte Ports gesendet und bittet das Dateisystem, F001 zur Eingabe zu öffnen. Die Nachricht enthält außerdem ein Paar von Ports, die der Dateisystemprozess zum Senden seiner Antwort verwenden kann. Das Dateisystem sucht F001, öffnet es zur Eingabe, trägt einige Einträge in seine Tabellen offener Dateien ein und sendet eine Nachricht zurück an FORTRAN, die die Ports enthält, die FORTRAN zum Lesen der Datei verwenden kann. Für die Ausgabedatei wird dasselbe Verfahren befolgt. Wenn die Übersetzung abgeschlossen ist, gibt FORTRAN die Fernschreiber-Portnummern an das Executive zurück, das schlafend auf eine Nachricht von FORTRAN gewartet hat, und FORTRAN hält sich dann selbst an. Der Dateisystemprozess legt sich wieder schlafen, wenn er nichts anderes zu tun hat.

[Dem Leser dürfte inzwischen aufgefallen sein, dass ich es nicht mag, mir vorzustellen, dass jedes Mal ein neuer Prozess (bestehend aus einer neuen begrifflichen Kopie eines Programms) gestartet wird, wenn ein weiterer Benutzer dieses Programm nutzen möchte. Ich stelle mir das Programm lieber als einen einzigen Prozess vor, der weiß, dass er gleichzeitig von vielen anderen Prozessen genutzt wird, und der bewusst zwischen den Benutzern multiplexiert oder den Dienst an Benutzer aufschiebt, bis er sich um sie kümmern kann.]

Ebenso kann der Dateisystemprozess eine kleine Sammlung von Portnummern behalten, die er immer wieder verwendet, wenn es ihm gelingt, die Nutzer des Dateisystems dazu zu bringen, die Portnummern zurückzugeben, wenn sie fertig sind. Wenn diese Sammlung von Portnummern sich natürlich schließlich zerstreut hat, kann das Dateisystem beim Monitor einige neue eindeutige Nummern holen.

Man beachte, dass zwei Prozesse, die kommunizieren möchten, die Verbindung selbst einrichten und dabei in einer für beide Seiten bequemen Weise vorgehen können. Zum Beispiel können sie Portnummern austauschen, oder ein Prozess kann alle Portnummern auswählen und dem anderen mitteilen, welche er verwenden soll. Natürlich können die Erbauer des Systems bei einer bestimmten Implementierung eines Timesharing-Systems beschließen, die Ausführung von SENDs und RECEIVEs durch die Prozesse einzuschränken und das beliebige Weitergeben von Portnummern zu verbieten, und stattdessen zu verlangen, dass der Monitor (oder ein anderes spezielles Programm) aufgerufen wird, um diese Funktionen auszuführen.

Die Flusskontrolle wird in diesem System durch die einfache Methode bereitgestellt, dass ein SEND von einem Prozess nie begonnen wird, bevor nicht ein RECEIVE vom Empfänger ausgeführt wurde. Natürlich können Interprozessnachrichten hin- und hergeschickt werden, die nahelegen, dass ein Prozess das Senden einstellen soll, oder die um Zuweisung von Platz bitten usw.