3. Implementierung in GORDO

3.1 Einführung in GORDO

GORDO ist ein Timesharing-System, das auf der SDS Sigma 7 implementiert ist. Nachfolgend skizzieren wir einige der für unsere Arbeit relevanten Merkmale.

3.1.1 GORDO-Dateisystem

Das Dateisystem ist seitenorientiert. Es besteht aus Dateien und Verzeichnissen. Eine Datei besteht aus einer Überschrift und einer Anzahl von Seiten, die den Rumpf der Datei bilden. Ein Verzeichnis besteht aus einer Anzahl von Einträgen, die entweder auf Dateien oder auf andere Verzeichnisse verweisen.

3.1.2 GORDO-Prozess

• Ein Prozess ist ein Programm (Prozeduren und Daten) plus seine logische Umgebung. Mit anderen Worten, ein Prozess ist ein Programm, das dem GORDO-Scheduler bekannt ist und von ihm gesteuert wird.
• Ein Benutzer (ein Job) kann mehrere Prozesse haben, die so unterschiedlich sind wie Compiler, Loader, Editor, Anwendungsprogramm usw. Ein Prozess wird durch einen Systemaufruf (FORK) erzeugt.
• Der Raum, auf den ein Prozess verweisen kann, ist der virtuelle Adressraum mit einer Länge von 128k Wörtern. Ein Teil davon (8k) ist für das Betriebssystem reserviert, auf den anderen Teil (120k) greift der Benutzer direkt zu. Letzterer kann seinen Teil des virtuellen Adressraums beim 'Koppeln' füllen oder ändern. (Siehe unten: Dienstaufrufe) Seiten, die aus verschiedenen Dateien entnommen sind. Abbildung 3 veranschaulicht diese Kopplung.
• Ein Prozess kann Dienste mithilfe von Systemaufrufen anfordern. Die für unsere Arbeit relevanten Systemaufrufe sind:

WAKE zum Aufwecken (Aktivsetzen) eines schlafenden Prozesses SLEEP zum Schlafenlegen eines anderen Prozesses (oder sich selbst) COUPLE zum Koppeln einer Seite aus dem Dateiraum an den virtuellen Adressraum.

• Ein Prozess läuft normalerweise im Slave-Modus. Wenn er jedoch als E/A-Prozess eingerichtet ist, kann er auf privilegierte Befehle zugreifen.
• Prozesse können Daten über Dateien austauschen, die an "Briefkasten"-Verzeichnisse angehängt sind.

Anmerkung: In dieser Mitteilung werden die Wörter Prozess und Programm austauschbar verwendet.

[Abbildung 3 - Virtueller Adressraum und Kopplung - siehe PDF-Datei]

3.2 Überblick über die Softwareorganisation

Abbildung 4 veranschaulicht die Gesamtorganisation.

Das System basiert auf zwei Hauptprogrammen: dem "Network" und dem "Handler".

Der Handler ist eine E/A-Unterbrechungsroutine, die eng mit der Hardware-Schnittstelle IMP-HOST verbunden ist. Er dient dem Netzwerkprozess beim Senden und Empfangen von Netzwerknachrichten.

Der Netzwerkprozess führt den größten Teil der Arbeit aus.

Seine Hauptfunktion ist es, die Anforderungen der Benutzer zum Öffnen/Schließen von Verbindungen und zum Senden/Empfangen von Netzwerknachrichten zu erfüllen. Zu diesem Zweck

• baut er die Links unter Verwendung der Zuordnungstabellen auf, identifiziert und bricht sie (HOST, CONNECT, INPUT LINK; siehe 3.3.1.1)
• erkennt er das Vorhandensein neuer Benutzer beim Durchsuchen des Briefkastenverzeichnisses des Netzwerks;
• kommuniziert er mit aktiven Benutzern mithilfe von gemeinsam genutzten Seiten, über die Nachrichten und Anforderungen ausgetauscht werden (gemeinsam genutzte Verbindungsseiten);
• formatiert er eingehende/ausgehende Nachrichten in einer Arbeitsseite. Diese Arbeitsseite hat eine Erweiterung (Notfallring);
• kommuniziert er mit dem Handler mithilfe einer gemeinsam genutzten Seite (E/A-Kommunikationsseite), die die E/A-Kommunikationspuffer enthält.

[Abbildung 4 - Überblick über die Softwareorganisation - siehe PDF-Datei]

3.3 Softwarebeschreibung

3.3.1 Datenstrukturen

3.3.1.1 Zuordnungstabellen: HOST, CONNECT, INPUT LINK

Das Netzwerkprogramm baut Links und Verbindungen unter Verwendung von 3 Tabellen auf, identifiziert und bricht sie:

Eine nach entferntem HOST # sortierte Tabelle.

Eine nach Verbindung # sortierte Tabelle.

Eine nach Eingangs-Link # sortierte Tabelle.

(a) HOST-Tabelle (siehe Abbildung 5)

Es ist eine Bittabelle, die die freien ausgehenden Links angibt. Sie hat die folgenden Merkmale:

• Position: Auf Platte resident
• Kopplung: An den virtuellen Adressraum des Netzwerkprozesses gekoppelt.
• Größe: So viele Slots wie entfernte HOST[s].
• Slot-Struktur: So viele Bits wie mögliche ausgehende Links zu einem entfernten HOST, d. h. 256.
• Zugriff: Indexierung. Auf jeden Slot wird über einen entfernten HOST # zugegriffen.
• Besonderheit: In der gesamten Tabelle dürfen nicht mehr als 64 Bits gesetzt sein. Diese Zahl entspricht der Höchstzahl ausgehender Links, die gleichzeitig aktiviert werden können (unabhängig davon, wie groß die Anzahl der entfernten HOST[s] ist).

(b) CONNECT-Tabelle

Diese Tabelle verfolgt die Umgebung aller Verbindungen.

Sie hat die folgenden Merkmale:

• Position: Auf Platte resident
• Kopplung: Wird an den virtuellen Adressraum des Netzwerkprozesses gekoppelt
• Größe: So viele Slots wie verwendete Verbindungen.
• Slot-Struktur: Siehe Abbildung 6. Jeder Slot ist 2 Wörter lang
• Zugriff: Indexierung. Auf jeden Slot wird über eine Verbindung # zugegriffen. Siehe 3.4 zur Art der Handhabung.
• Besonderheit 1: Die Slot-Struktur einer Primärverbindung ist nicht identisch mit der einer Hilfsverbindung (siehe Abbildung 7). Dies deshalb, weil Benutzeridentifikationen und -anforderungen über primäre gemeinsam genutzte Seiten erfolgen.
• Besonderheit 2: Diese Tabelle wird parallel zu den Verbindungsseiten gehandhabt (siehe 3.3.2 (b))
• Besonderheit 3: Diese Tabelle wird hauptsächlich zum Senden von Nachrichten verwendet. (Für jede Verbindung enthält sie den ausgehenden Link # und den entfernten HOST #, d. h. alle zum Senden einer Nachricht erforderlichen Informationen.)

(c) INPUT LINK-Tabelle

Diese Tabelle verfolgt alle eingehenden (Eingangs-)Links und steht daher in engem Zusammenhang mit der CONNECT-Tabelle.

[Abbildung 5 - HOST-Tabelle - siehe PDF-Datei]

[Abbildung 6 - CONNECT-Tabelle: Slot-Struktur - siehe PDF-Datei]

[Abbildung 7 - INSERT LINK-Tabelle: Slot-Struktur - siehe PDF-Datei]

Sie hat die folgenden Merkmale:

• Position: Auf Platte resident.
• Kopplung: An den virtuellen Adressraum des Netzwerkprozesses gekoppelt.
• Größe: So viele Slots wie eingehende Links, d. h. wie Verbindungen
• Slot-Struktur: Siehe Abbildung 7. Jeder Slot ist 1 Wort lang
• Zugriff: Hashing. Der gehashte Schlüsselwert basiert hauptsächlich auf dem eingehenden Link # und dem entfernten HOST #.
• Besonderheit 1: Diese Tabelle wird auch verwendet, um vorübergehend die Verbindungsnummer zu speichern, während die nächste Verbindung aufgebaut wird. Siehe 3.4 zur Art der Handhabung.
• Besonderheit 2: Diese Tabelle wird hauptsächlich beim Empfang von Nachrichten verwendet. (Für jeden eingehenden Link enthält sie die entsprechende Verbindung #, d. h. indirekt die Benutzeridentifikation, an die die Nachricht weitergeleitet werden soll)

3.3.1.2 Pufferseiten

Alle nun zu beschreibenden Seiten enthalten zwei Puffer (Eingabe und Ausgabe). Diese Puffer werden entweder zum Weiterleiten oder zur Verarbeitung von Nachrichten verwendet.

Die Größe jedes dieser Puffer sollte mindestens der einer Nachricht entsprechen, d. h. 8095 Bit. Wir haben eine Puffergröße von 253 Wörtern (8096 Bit) gewählt, sodass beide Puffer innerhalb einer Seite (512 Wörter) enthalten sind. Die 6 verbleibenden Wörter der Seite werden im Allgemeinen zur Steuerung verwendet.

Eine typische Pufferseitenstruktur ist in Abbildung 8 dargestellt.

(a) E/A-Kommunikationsseite

Siehe Abbildung 9.

Diese E/A-Kommunikationsseite wird als Schnittstelle zwischen dem Handler und dem Netzwerkprogramm verwendet.

In den Puffern dieser Seite werden die Nachrichten vom Handler Wort für Wort zusammengesetzt (Eingabe) oder zerlegt (Ausgabe), z. B. wird eine startbereite Nachricht, die vom Netzwerkprogramm in den Ausgabepuffer einsortiert wurde, vom Handler Wort für Wort ausgeliefert.

Hauptmerkmale:

• Position: Im Kern resident: gesperrte Seite
• Kopplung: An den virtuellen Adressraum des Netzwerkprozesses gekoppelt
• Inhalt: * Eingabepuffer (253 Wörter) für eingehende Nachrichten Ausgabepuffer (253 Wörter) für ausgehende Nachrichten
  • Eingabe-Steuerzone (6 Halbwörter)
  • Ausgabe-Steuerzone (6 Halbwörter)
• Struktur: Siehe Abbildung 9.
• Besonderheit: * Der Eingabepuffer wird vom Handler gefüllt (aus der Hardware gelesen) und vom Netzwerkprogramm geleert
  • Umgekehrt für den Ausgabepuffer

(b) Gemeinsam genutzte Verbindungsseiten (gemeinsame Zone Benutzer-Netzwerk)

Allgemeine Merkmale:

• Es gibt so viele gemeinsam genutzte Seiten wie Verbindungen.
• Diese zwischen dem Netzwerk und den Benutzerprozessen gemeinsam genutzten Seiten bilden eine Kommunikationszone zum (1) Hin- und Herübermitteln der Nachrichten und (2) Austauschen von Steuerinformationen, z. B. einer Anforderung zum Aufbau neuer Verbindungen.

Hauptmerkmale:

• Position: Auf Platte resident
• Kopplung: Sowohl an den virtuellen Adressraum eines Benutzerprozesses als auch an den virtuellen Adressraum des Netzwerkprozesses gekoppelt.
• Inhalt: - Eingabepuffer (253 Wörter) für eingehende Nachrichten
  • Ausgabepuffer (253 Wörter) für ausgehende Nachrichten
  • Eingabe-Steuerzone (6 Halbwörter)
  • Ausgabe-Steuerzone (6 Halbwörter)
• Struktur: Siehe Abbildung 10.
• Besonderheit 1: - Der Eingabepuffer wird vom Netzwerk gefüllt und vom Benutzer geleert.
  • Umgekehrt für den Ausgabepuffer.
• Besonderheit 2: Die Steuerzone, die einer gemeinsam genutzten Seite einer Primärverbindung entspricht, unterscheidet sich von der einer Hilfsverbindung. Dies deshalb, weil über eine "Steuerzone der Primärverbindung" die Anforderungen zum Aufbau von Hilfsverbindungen an den Netzwerkprozess übertragen werden.

(c) Arbeitsseite

Allgemeines Merkmal:

• Diese Seite ermöglicht es dem Netzwerk- und dem Handler-Programm, unabhängig an verschiedenen Nachrichten zu arbeiten, und trägt so zu einer Überlappung bei. Wenn der Handler beispielsweise damit beschäftigt ist, eine Nachricht an die Hardware zu senden, kann das Netzwerkprogramm die nächste auszuliefernde Nachricht formatieren (Kopf, Markierung usw.), sodass es den Handler wieder starten kann, sobald dieser frei ist.

Hauptmerkmale:

• Position: Auf Platte resident
• Kopplung: An den virtuellen Adressraum des Netzwerkprozesses gekoppelt
• Inhalt: - Eingabepuffer (253 Wörter) für eingehende Nachrichten
  • Ausgabepuffer (253 Wörter) für ausgehende Nachrichten

Anmerkung:

Beim Empfang kann es vorkommen, dass ein Benutzerprogramm nicht bereit ist, eine neue Nachricht anzunehmen. In diesem Fall speichert das Netzwerk, um eine Verstopfung des Systems zu vermeiden, die eingehende Nachricht vorübergehend in einem der Puffer des Notfallrings. (Wenn dieser Ring voll ist, wird eine Hilfsroutine aufgerufen.)

Beim Senden sind alle Vorgänge mit den RFNM[s] synchronisiert, daher müssen solche Prozeduren nicht bereitgestellt werden. (Das Netzwerkprogramm erlaubt einem Benutzer, erst dann erneut zu senden, wenn er das RFNM der zuvor gesendeten Nachricht empfangen hat.)

[Abbildung 8 - Typische Pufferseite - siehe PDF-Datei]

[Abbildung 9 - Struktur der E/A-Kommunikationsseite - siehe PDF-Datei]

[Abbildung 10 - Struktur der gemeinsam genutzten Verbindungsseite - siehe PDF-Datei]

3.3.2 Programme

3.3.2.1 Handler-Programm

Allgemeine Merkmale:

Es ist eine E/A-Unterbrechungsroutine, die die Hardware-Schnittstelle IMP/HOST ansteuert, um Nachrichten zu senden oder zu empfangen. Senden und Empfangen erfolgen im Vollduplex-Modus.

Hauptmerkmale:

• Position: Im Kern resident. Der Handler befindet sich in derselben Speicherzone wie das Betriebssystem und kann als Teil davon betrachtet werden.
• Auslösung: Durch die Hardware-Unterbrechung IMP-HOST. Diese Unterbrechung wird entweder ausgelöst:
• während des Sendens, wenn ein Nachrichtenwort vollständig an den IMP gesendet wurde
• während des Empfangens, wenn ein Nachrichtenwort vollständig vom IMP empfangen wurde
• während der Leerlaufzeit, wenn die Hardware entweder einen Befehl 'start input' oder 'start output' von der CPU der Sigma 7 empfangen hat. Diese Befehle werden vom Netzwerkprogramm ausgegeben, um Rückunterbrechungen hervorzurufen (und folglich den Handler indirekt zu starten).
• Hauptfunktionen: * Leert den Ausgabepuffer beim Senden seines Inhalts (ausgehende Nachricht) an den IMP. Dieser Vorgang wird Wort für Wort (32 Bit) ausgeführt und nutzt "Write"-Befehle zum Ansteuern der Hardware HOST-IMP.
• Füllt den Eingabepuffer mit Daten, die von der Hardware HOST-IMP empfangen wurden (eingehende Nachricht). Dieser Vorgang wird ebenfalls Wort für Wort ausgeführt und nutzt "Read"-Befehle zum Ansteuern der Hardware HOST-IMP.
• Weckt das Netzwerkprogramm auf, wenn einer der vorhergehenden Vorgänge abgeschlossen ist.

3.3.2.2 Netzwerkprogramm

Allgemeine Merkmale:

Dieses Programm dient dem Benutzer zum Öffnen/Schließen von Verbindungen und zum Senden/Empfangen von Nachrichten. Es verwendet den Handler als Hilfe für die Schnittstellenbildung mit der Hardware.

Aus Sicht von GORDO ist es ein regulärer Prozess und wird als solcher behandelt.

Hauptmerkmale:

• Position: Auf Platte resident. Genauer gesagt befindet es sich auf der Platte, wenn es schläft, und wird in den Kern gerufen, wenn es von einem Programm aufgeweckt wird.
• Auslösung: Es wird durch 'WAKE'-Dienstaufrufe ausgelöst, die entweder von einem Benutzerprozess oder vom Handler ausgegeben werden.
• Hauptfunktionen: * Baut ausgehende Verbindungen auf Anforderung der Benutzer auf/löscht sie. Zu diesem Zweck sendet es Steuernachrichten (siehe 2.4.2) an entfernte HOST[s], um Links aufzubauen/freizugeben; anschließend benachrichtigt es die Benutzer zurück.
  • Stellt die Verarbeitung eingehender Steuernachrichten sicher (über Steuerlinks übertragen), z. B. um zu Aufbauten/Löschungen von Verbindungen beizutragen (solchen, die von entfernten HOSTS angefordert wurden).
• Bereitet das Senden ausgehender Nachrichten vor. Es entnimmt Textnachrichten den gemeinsam genutzten Seiten (die Nachrichten werden dort von Benutzern gespeichert), formatiert sie (fügt Kopf, Markierung, Prüfsumme hinzu..) und leitet sie zum Senden an den Handler weiter.
• Stellt die Zustellung eingehender Nachrichten sicher. Es ist das Gegenteil des obigen Vorgangs. Die Benutzer, an die die Nachrichten zugestellt werden sollen, werden anhand der Köpfe identifiziert.
• Konfiguration des virtuellen Adressraums: Siehe Abbildung 11.
• Besonderheit: Es ist als E/A-Prozess integriert, sodass es auf privilegierte Befehle zugreifen kann (RD/WD zum indirekten Starten des Handlers).

[Abbildung 11 - Virtueller Adressraum des Netzwerkprozesses - siehe PDF-Datei]

3.4 Softwareprozeduren

Die detaillierten Softwareprozeduren sind in den Flussdiagrammen angegeben, die Anhang A beigefügt sind.

Um jedoch ein schnelles Verständnis der Implementierung zu erhalten, listen wir nachfolgend einige typische Softwareprozeduren auf.

3.4.1 Beschreibung einiger typischer Sequenzen

Betrachten Sie einige der dem Benutzer zur Verfügung stehenden Transaktionen (siehe 2.4) und zeigen Sie die grundlegenden Softwareprozeduren auf, die sie implizieren. Für jeden Fall werden wir (i) umreißen, was das Benutzerprogramm tut, und (ii) was das Netzwerkprogramm tut.

(a) Einen primären Link öffnen (siehe auch 2.4.2)

(i) Was das Benutzerprogramm tut[1]:

• es speichert im Briefkastenverzeichnis des Netzwerks den Namen einer Datei, z. B. DATA;
• es koppelt die erste Seite dieser Datei an seinen virtuellen Adressraum;
• es speichert Informationen in dieser Seite (seine Job-/Prozessnummer, den entfernten HOST #, z. B. (i));
• es weckt den Netzwerkprozess auf;
• es geht schlafen.

(ii) Was das Netzwerkprogramm tut:

• es durchsucht das Briefkastenverzeichnis des Netzwerks und greift auf die Datei DATA zu;
• es koppelt die erste Seite dieser Datei an seinen virtuellen Adressraum (gemeinsame Zone, siehe 3.3.1.2). Angenommen, diese Seite sei die k-te in der gemeinsamen Zone; k ist die interne Verbindung #;
• es durchsucht den i-ten Slot der neuen HOST-Tabelle (siehe 3.3.1.1 (a)) und wählt das erste Bit = 0, z. B. das (alpha)-te Bit; alpha entspricht dem ausgehenden Link #;
• es speichert Informationen (Job-/Prozessnummer, entfernter HOST # (i), ausgehender Link # (alpha)) im k-ten Slot der CONNECT-Tabelle (siehe 3.3.1.2).
• es speichert vorübergehend die Verbindung # (k) in der INPUT LINK-Tabelle. Dies erfolgt beim Anlegen eines Eintrags in dieser Tabelle (Hashing des Schlüsselwerts: "ausgehender Link # (alpha) + entfernter HOST # (i) + Ausgangs-Flag".);
• es bereitet den Nachrichtentext ENQ PRIM 0 0 a vor und formatiert eine vollständige Nachricht, indem es Kopf, Markierung, Prüfsumme usw. hinzufügt;
• es prüft den Zustand des Handlers (Bit in der gesperrten E/A-Seite). Wenn der Handler frei ist, speichert es die startbereite Steuernachricht im Ausgabepuffer der gesperrten E/A-Seite, startet den Handler und geht schlafen. Andernfalls geht es schlafen.

Nach einer Weile weckt der Handler den Netzwerkprozess auf, weil er eine vollständige Nachricht empfangen hat. Wir nehmen an, diese Nachricht sei die vom entfernten HOST gesendete Steuernachricht zur Bestätigung des Verbindungsaufbaus. Der Nachrichtentext sollte lauten:

ACK ENQ PRIM 0 0 alpha 0 0 beta

wobei beta der eingehende Link # ist. (Siehe 2.4.2)

Sehen wir nun, was das Netzwerkprogramm beim Empfang der obigen Steuernachricht tut:

• es ruft die zuvor in der INPUT LINK-Tabelle gespeicherte Verbindung # ab, indem es denselben Schlüsselwert erneut hasht (siehe oben). Außerdem löscht es diesen Eintrag;
• es legt einen Eintrag in der INPUT LINK-Tabelle für den eingehenden Link an. Zu diesem Zweck hasht es den Schlüsselwert: "eingehender Link # (beta]) + entfernter HOST # (i) + "Eingangs-Flag". In diesem Eintrag speichert es den HOST # (i), den eingehenden Link # (beta) und die Verbindung # (k);
• es aktualisiert den k-ten Slot der CONNECT-Tabelle, indem es den eingehenden Link # (beta) speichert;
• es setzt das Bit 'net-user' in der k-ten gemeinsam genutzten Seite (Seite, die der soeben geöffneten Primärverbindung entspricht) und weckt den Benutzerprozess auf;
• es geht schlafen.

(b) Eine Nachricht über den primären Link senden

(i) Was das Benutzerprogramm tut[1].

• es speichert den Nachrichtentext im Ausgabepuffer der gemeinsam genutzten Seite der Primärverbindung (siehe 3.3.1.2);
• es setzt das Bit 'user-net' dieser Seite und weckt den Netzwerkprozess auf;
• es geht schlafen.

(ii) Was das Netzwerkprogramm tut:

• es sucht nach einer Benutzeranforderung, d. h., es durchsucht der Reihe nach die gemeinsam genutzten Verbindungsseiten und wählt diejenige aus, bei der das Bit 'user-net' gesetzt ist. Angenommen, k sei die ausgewählte Seitenzahl in der Liste der gemeinsam genutzten Seiten, K ist die Verbindung #;
• es bestimmt den Anforderungstyp, indem es die 'Anforderungsbits' der gemeinsam genutzten Seite k prüft. Es stellt fest, dass es sich um eine Anforderung zum Senden einer Nachricht handelt.
• es entnimmt den Nachrichtentext dem Ausgabepuffer der gemeinsam genutzten Seite k, formatiert ihn zu einer vollständigen Nachricht und übergibt ihn in sehr ähnlicher Weise wie oben an den Handler (siehe Einen primären Link öffnen).
• es geht schlafen.

[1] Anmerkung: In einer ersten Phase wird der Benutzer die Netzwerkfunktionen direkt in sein Programm schreiben. Später werden dem Benutzer Unterprogramme zur Verfügung gestellt. Diese Unterprogramme werden den in 2.4 beschriebenen sehr nahe kommen.