Betriebssystempraktikum (BSP)
Praktikum Systemprogrammierung (PSP)

Übungsaufgaben


Anmerkungen

  1. Zur Erlangung eines Teilnahmenachweises ist es notwendig, alle Aufgaben vollständig bearbeitet und gelöst zu haben. Es ist nicht möglich, eine Aufgabe auszulassen, da alle Aufgaben aufeinander aufbauen.
  2. Die ersten Aufgaben sind recht schnell zu erledigen, quasi zum Aufwärmen. Wer sich zu sehr daran gewöhnt, wird vom Aufwand bei der Programmierung und - nicht zu vergessen! - der Fehlersuche bei den letzten beiden Aufgaben überrascht sein. Das Motto sollte also sein, am Anfang des Praktikums Zeitreserven zu erarbeiten.
  3. Die Lösungen sind der Tutorin oder dem Tutor jeweils in der betreuten Rechnerzeit der angegebenen Woche vorzuführen. Dabei muss - außer in begründeten Ausnahmefällen - die Arbeitsgruppe komplett anwesend sein.
  4. Welche Aufgaben jeweils als gelöst betrachtet werden können, entscheidet allein die Tutorin oder der Tutor. Die Tutorin oder der Tutor kann sich nach eigenem Ermessen einige oder alle Dateien der Lösung per Email zuschicken lassen.
  5. Die ausgeteilten Programmlistings umfassen auch diejenigen vorgegebenen Dateien, die erst im Laufe der Aufgaben benötigt werden. Zusätzlich zur Lektüre einer Aufgabe sollte also immer auch ein Blick in die jeweilige(n) Vorgabe-Datei(en) geworfen werden.
  6. Wer Lösungen der Praktikumsaufgaben für andere Gruppen kopiert oder von anderen Gruppen kopieren lässt, begeht einen Betrugsversuch für einen Leistungsnachweis. Dies führt normalerweise zumindest zum Ausschluss vom Praktikum.

Aufgabe 1

a. Programmierung der seriellen Schnittstelle

Das Modul mxSeriell stellt die Operationen zur Verfügung, die über die serielle Schnittstelle des mx mit einer VT100-Terminal-Emulation kommunizieren sollen. Für die beiden zentralen Funktionen SchreibSeriell und LiesSeriell sind nur die Funktionsköpfe vorgegeben. Implementiert diese beiden Funktionen.

SchreibSeriell soll aktiv auf die Sendebereitschaft der Schnittstelle warten. Dabei darf die CPU keinesfalls abgegeben werden, weil sich sonst die mittels printk durchgeführten Ausgaben ins Syslog mit Bildschirmausgaben mischen können.

LiesSeriell soll nicht blockieren, sondern den Wert 0 zurückliefern, sofern kein Zeichen empfangen wurde. Darüber hinaus ist zu beachten, dass MinMax bei Eingabe von Control-C terminieren soll. Hierfür wird das globale Flag VT_Abbruch benutzt, das auf TRUE gesetzt werden muss, sofern cAbbruchZeichen eingegeben wurde (siehe Kapitel 9.2 der Dokumentation sowie die Listings zu MinMax.c und mxVT.h). Die nichtblockierende Semantik von LiesSeriell wird ab der 2. Aufgabe benötigt, daher erfolgt das Warten auf ein Zeichen in der Funktion LiesZeichen.

b. Ansteuerung der LED-Anzeige

Das Modul mxLED ist dafür zuständig, die Hardware der LED-Anzeige anzusteuern und Dezimalzahlen lesbar darauf darzustellen. Die beiden Funktionen Setze7SegmentBits und Setze7SegmentZiffer sind nur als Funktionsköpfe vorgegeben.

Die Funktion

void Setze7SegmentBits( tLEDStelle Stelle, int Wert )

soll das Byte Wert direkt auf dem Parallelport der angegebenen LED-Stelle (eEiner, eZehner) ausgeben. Die Funktion

void Setze7SegmentZiffer( tLEDStelle Stelle, int Ziffer, int Punkt )

stellt die Ziffer auf der angegebenen Stelle in der üblichen 7-Segment-Darstellung dar. Punkt (0 oder 1) gibt an, ob der Punkt auch leuchten soll (ungleich 0 für ja). Der Zugriff auf die Hardware erfolgt ausschließlich über Setze7SegmentBits.

Implementiert diese beiden Funktionen. Zur Ansteuerung der Anzeige und zur Zuordnung zwischen den Portbits und den Anzeigesegmenten siehe Kapitel 9.5 der Dokumentation und mxLED.c.

Anschließend könnt Ihr MinMax zum ersten Mal übersetzen und ausführen lassen.


Aufgabe 2

Bisher muss bei jedem einzelnen Aufruf von sys_LiesZeichen erst auf das zu lesende Zeichen gewartet werden. In späteren Ausbaustufen von MinMax, wenn viele Prozesse gleichzeitig laufen, könnten sogar Zeichen verloren gehen, weil man zwischen zwei CPU-Zuteilungen an den Zeichen lesenden Prozess durchaus mehr als eine Taste drücken kann. Ein Betriebssystem sollte einen physikalischen Eingabevorgang stets von der Datenanforderung durch die Prozesse trennen. Daher sollen ankommende Zeichen in MinMax nun von einer Unterbrechungsbehandlungsroutine entgegengenommen und in einem zyklischen Eingabepuffer abgelegt werden. Aus diesem Puffer holt sys_LiesZeichen die eingegebenen Benutzerkommandos und gibt sie an den Interpreter weiter.

a. Implementierung eines Eingabepuffers

Im neu zu implementierenden Modul mxEingabePuffer soll der Eingabepuffer als abstrakter Datentyp tEingabePuffer zur Verfügung gestellt werden. Die Realisierung als Datentyp ist wichtig, weil ab der nächsten Aufgabe mehrere Instanzen des Puffers benötigt werden.

Das Modul verwendet Puffer mit konstanter Länge und stellt als Operationen auf ihnen die Funktionen LiesInPuffer, LiesAusPuffer und ErzeugePuffer zur Verfügung. Die erste trägt ein Zeichen in den angegebenen Eingabepuffer ein, die zweite holt das jeweils nächste Zeichen aus dem angegebenen Puffer. Bedenkt bei der Implementierung, dass es zu einem Überlauf des Puffers kommen kann. Beachtet, dass das Warten auf ein Zeichen jetzt nicht mehr in LiesZeichen erfolgt, sondern in LiesAusPuffer, welches jetzt von LiesZeichen aus aufgerufen wird. ErzeugePuffer initialisiert eine Datenstruktur vom Typ tEingabePuffer mit einem leeren Puffer.

Implementiert zunächst das Modul mxEingabePuffer entsprechend der vorgegebenen Header-Datei und passt anschließend die Funktion LiesZeichen entsprechend an.

b. Einlesen eingegebener Zeichen per Unterbrechung

Der neu implementierte Eingabepuffer muss noch mit den eingegebenen Zeichen gefüllt werden. Dies geschieht in wirklichen Betriebssystemen immer mit Hilfe einer Unterbrechungsroutine (Interrupt), die nach der Eingabe eines Zeichens von der Hardware angestoßen wird. Dies soll auch in MinMax so geschehen.

Schreibt eine neue Unterbrechungsbehandlungsroutine erster Stufe in Assembler, die Prozedur EingabeUnterbrechung im Modul mxUnterbrechung. Sorgt dafür, dass diese Routine über den Unterbrechungsvektor cEingabeInterruptVektor angesprungen wird, sobald ein Zeichen gelesen wurde. Dazu muss auch die zugehörige Unterbrechung vom MFP (cEingabeBit) freigeschaltet sein. Bei der Termination von MinMax müssen der alte Wert des Unterbrechungsvektors wiederhergestellt und die Unterbrechung gesperrt werden, wie das auch beim Uhr-Interrupt geschieht.

EingabeUnterbrechung soll eine weitere von Euch zu implementierende Funktion aus mxEingabePuffer, nämlich EingabeUnterbrechungStufe2, als Unterbrechungsbehandlungsroutine zweiter Stufe aufrufen. Dort wird mit LiesSeriell das eingetroffene Zeichen gelesen und mit LiesInPuffer im Eingabepuffer abgelegt. Fangt auch die Situation ab, dass zwar eine Unterbrechung ausgelöst wurde, aber LiesSeriell gar kein Zeichen vorfindet. Bei Unterbrechungsbehandlungsroutinen ist Vorsicht ratsam!

c. Einfügen eines neuen Systemaufrufes zum "Schlafen"

Implementiert eine Funktion

void Schlafe( int ms )

im Modul mxCPUVerwaltung, die den aufrufenden Prozess mindestens für die angegebene Zahl von Millisekunden warten lässt. Da es keine geeigneten Hardware-Zeitgeber gibt, soll der schlafende Prozess selbst bei jeder CPU-Zuteilung prüfen, ob die Wartezeit schon abgelaufen ist. Wenn nicht, soll die Restlaufzeit des Prozesses anderen Prozessen zur Verfügung gestellt werden. Implementiert Schlafe so, dass auch bei Angabe von 0 Millisekunden die CPU einmal abgegeben wird.

Schlafe soll den MinMax-Benutzern als neuer Systemaufruf sys_Schlafe mit gleicher Parametrisierung zur Verfügung gestellt werden. Mit diesem Aufruf können Benutzerprozesse ohne aktives Warten präzise Zeitverzögerungen implementieren oder auch eine einzelne CPU-Abgabe hervorrufen. Ihr solltet beim Einfügen des neuen Systemaufrufs die Konventionen aus Anhang A beachten, damit Euer finales MinMax später die vorbereiteten Testprogramme ausführen kann!

Testet sys_Schlafe und den Eingabepuffer, indem Ihr per sys_Schlafe-Aufruf eine Verzögerung als neues Benutzerkommando in den Interpreter einfügt, während der Ihr einige Zeichen im Voraus eingeben könnt.


Aufgabe 3

a. Implementierung von Semaphoren

Implementiert Semaphore als Hilfsmittel für die Prozesssynchronisation in MinMax.

Erweitert dazu als erstes das Modul mxProzess um die Funktionen

void ProzessBlockieren( tListe *Warteschlange )

und

void ProzessFortsetzen( tListe *Warteschlange ).

ProzessBlockieren soll den laufenden Prozess in die übergebene Warteschlange einhängen und anschließend einen Prozesswechsel erzwingen, ProzessFortsetzen soll den ersten Prozess, der in der übergebenen Warteschlange hängt, herausholen und wieder lauffähig machen.

Erweitert außerdem die Datenstruktur tProzessStatus um die Komponente eBlockiert.

Als zweites implementiert Ihr das Modul mxSemaphor gemäß den in der Header-Datei vorgegebenen Schnittstellen. Berücksichtigt, dass die V-Operation auch aus einer Unterbrechungsbehandlung heraus aufgerufen wird. Ihr müsst aus diesem Grund unbedingt

durch Lock/Unlock schützen. Anderenfalls könnten durch eine Eingabe-Unterbrechung Konflikte bei der Manipulation des Semaphorzählers entstehen und die Konsistenz der BereitListe zerstört werden. Für die V-Operation genügt der Schutz mit ProzesswechselUnterbinden bzw. ProzesswechselZulassen (warum?).

Hinweis: Vergesst nicht, im Interpreter den neuen Prozessstatus zu berücksichtigen!

b. Erste Anwendungen von Semaphoren

Als erste Anwendung der Semaphore soll das Ein- und Auslesen von Zeichen in und aus dem Eingabepuffer mit Hilfe eines Semaphors logisch synchronisiert werden: Wenn ein Prozess aus einem leeren Puffer zu lesen versucht, soll er blockiert werden, bis mindestens ein Zeichen eingegeben wurde. Damit entfällt die Warteschleife in LiesAusPuffer.

c. Einfügen neuer Systemaufrufe durch Implementierung einer Fensterverwaltung

Zur übersichtlicheren Ein- und Ausgabe soll der Bildschirm in mehrere Abschnitte (Fenster) unterteilt werden, die von den einzelnen Prozessen genutzt werden können. Diese Fenster sollen vom Kern verwaltet und durch Systemaufrufe von den Benutzerprozessen angefordert, freigegeben und benutzt werden. Die Ein- und Ausgabe soll nur noch in Fenstern möglich sein. Implementiert zunächst das Modul mxFenster gemäß der vorgegebenen Header-Datei. Führt dazu im Modul mxStrukturen den Datentyp tFensterNummer ein:

typedef int tFensterNummer;
#define cKeinFenster -1

Dabei soll die Zählung der Fenster bei 0 beginnen. Stellt als nächstes die Funktionen sys_FensterOeffnen, sys_FensterSchliessen, sys_FensterWechseln, sys_LiesString sowie sys_FensterXY als Systemaufrufe den Benutzerprozessen zur Verfügung. Die Parameter dieser Systemaufrufe sollen den zugeordneten Dienstfunktionen entsprechen (also z. B. FensterLesen(char *s, int Wieviel) => sys_LiesString(char *s, int Wieviel)). Stellt die Bildschirmausgabe mit printf und die Eingabe mit sys_LiesZeichen im Modul mxSystemDienst so um, dass alle Aus- und Eingaben in und aus Fenstern erfolgen. Um Euch die Arbeit zu erleichtern, ist eine Datei mxFenster.c bereits vorgegeben, die Hilfsfunktionen zur Ausgabe in ein Fenster samt Cursor-Steuerung, zum Einlesen einer Zeichenkette und zum Zeichnen der Fenstergrenzen enthält. Schließlich müsst Ihr noch dafür sorgen, dass alle von einem terminierenden Prozess belegten Fenster wieder freigegeben werden.

Ihr solltet beim Einfügen der neuen Systemaufrufe die Konventionen aus Anhang A beachten, damit Euer finales MinMax später die vorbereiteten Testprogramme ausführen kann!

Die Ausgabe in ein Fenster muss als kritischer Abschnitt implementiert werden, damit kein anderer Prozess zwischendurch die Ausgabeposition im Terminal-Fenster ändern kann. Verwendet dazu ein Semaphor und erlaubt die Terminal-Ausgabe nur einem Prozess gleichzeitig. Beachtet dabei, dass die Hilfsfunktion FensterEingabe ebenfalls Ausgaben macht, durch den Aufruf von LiesAusPuffer den Prozess aber langfristig blockieren kann. Die Ausgaben mit kprintf sowie printk im Modul mxAusgabe sollen weiterhin unsynchronisiert und direkt auf die Schnittstelle erfolgen.

Hinweis: Das von mxBoot geöffnete MinMax-Fenster hat 120 Spalten mal 60 Zeilen.

d. Implementierung eines Eingabe-Fokus

Es gibt nun mehrere Fenster, aber immer noch nur eine Tastatur. Daher soll das Fenster, das jeweils die Eingaben erhält, mit der TAB-Taste umgeschaltet werden. Zu diesem Zweck enthält die vorgegebene Struktur tFenster für jedes Fenster einen eigenen Eingabepuffer. Erweitert EingabeUnterbrechungStufe2 so, dass eingegebene Zeichen im von der Variable EingabeFokus in mxFenster angezeigten Fenster landen und dieser Fokus mit jedem gelesenen Zeichen cTAB weiter geschaltet wird. TAB gelangt nicht in den Puffer!

Es ist sehr nützlich (aber nicht gefordert!), den Eingabefokus auch anzuzeigen - zum Beispiel in der Titelzeile des jeweiligen Fensters. Ihr dürft aber keinesfalls Bildschirmausgaben aus der Unterbrechungsbehandlung heraus machen, weil die Unterbrechung dann sehr lange dauert und weil eine möglicherweise laufende Ausgabe des unterbrochenen Prozesses an einer falschen Ausgabeposition fortgesetzt wird. Überlegt Euch also vorher gut, wie und wo sich eine Fokusanzeige implementieren lässt.

e. Anpassen der Benutzerprozesse an die Fensterverwaltung

Als erstes soll der Interpreter so umgestellt werden, dass er Fenster 0 öffnet, um Ein- und Ausgaben vornehmen zu können. Anschließend sollen die Benutzereingaben durch sys_LiesString eingelesen werden. Die Kommandos "A" bis "C" sollen durch die Kommandos "S" und "B" ersetzt werden, wobei "S" als zusätzliches Argument einen Prozessnamen als String für sys_StarteProzess erwartet. Außerdem sollen weitere Kommandozeilenparameter hinter dem Prozessnamen als Argument-String bei sys_StarteProzess übergeben werden. "B" erwartet als zusätzliches Argument eine Prozessnummer, die angibt, welcher Prozess beendet werden soll. Dadurch soll ermöglicht werden, zweimal hintereinander den gleichen Prozess zu starten.

Die Benutzerprozesse sollen beliebig Fenster öffnen, schließen und wechseln und Ausgaben in ihnen vornehmen, um die Fensterverwaltung zu testen. Im Verzeichnis minmax99/src findet Ihr außerdem in der Datei PDVIXtest.c einen Benutzerprozess, der alle implementierten Systemaufrufe testet. Tragt dazu PDVIXtest.o als neues Modul ins Makefile ein und ergänzt ein

#include "PDVIXtest.h"

im Interpreter. Beispielsweise auf das Kommando "S P" hin sollte der Interpreter die Funktion PDVIXtest mit Hilfe von sys_StarteProzess als neuen Prozess starten. Setzt die Variable AUFGABE im Makefile korrekt, damit die Testroutinen für später einzubauende Funktionen automatisch weggelassen werden.


Aufgabe 4

In dieser Aufgabe sollt Ihr MinMax um eine Freispeicherverwaltung erweitern.

a. Implementierung einer Freispeicherverwaltung

Den verschiedenen Schichten von MinMax soll es ermöglicht werden, den für ihre Aufgaben notwendigen Speicher dynamisch anzufordern und ihn, wenn er nicht mehr benötigt wird, wieder freizugeben. Dazu wird der 256 KByte große Speicherbereich zwischen den Adressen 0x040000 und 0x080000 als nutzbarer freier Speicher verwendet.

Das neu zu implementierende Modul mxSpeicher verwaltet diesen Bereich. Es verwendet dazu eine Freispeicher-Liste. In dieser Liste hängen alle momentan freien Speicherblöcke. Um diese Liste zu realisieren, werden die acht ersten Bytes eines freien Speicherblocks verwendet. Die ersten vier Bytes enthalten eine long-Variable, die angibt, wie groß der freie Speicherblock ist. Die folgenden vier Bytes sind ein Zeiger, d. h. die Adresse des nächsten freien Speicherblocks. Die Liste ist nach aufsteigenden Speicheradressen sortiert, d. h. der Speicherblock mit der niedrigsten Anfangsadresse steht am Anfang der Liste und jeder Zeiger zeigt auf den physikalisch folgenden freien Speicherblock. Bild 1 zeigt eine mögliche Freispeicher-Liste.

Die Operation SpeicherHolen soll nun diese Freispeicher-Liste nach der First-Fit-Strategie durchsuchen, d. h. nach dem ersten Block, der die angeforderte Größe hat oder übertrifft. Die Anfangsadresse dieses Blocks wird zurückgegeben. Das übrigbleibende Speicherstück des gefundenen Blocks wird, falls vorhanden, wieder in die Freispeicher-Liste eingefügt. Da hierzu wieder am Anfang des Blocks acht Bytes benötigt werden, ist es notwendig, dass diese Blöcke immer mindestens acht Bytes groß sind. Dies kann erreicht werden, wenn die Größe der allozierten Blöcke immer durch acht teilbar ist. Aus diesem Grund wird die angeforderte Größe immer auf ein Vielfaches von acht aufgerundet.

Bild einer möglichen Freispeicherliste
Bild 1: mögliche Freispeicher-Liste

Falls SpeicherHolen keinen Speicherblock finden kann, der groß genug ist, oder falls die angeforderte Blockgröße null ist, wird NULL zurückgegeben.

Bild 2 zeigt die Freispeicher-Liste, nachdem durch einen Aufruf von SpeicherHolen ein 56 KByte großer Speicherblock belegt wurde.

Die Funktion SpeicherFreigeben ist das Gegenstück zu SpeicherHolen. Sie sorgt dafür, dass der Speicherblock, dessen Anfangsadresse und Größe übergeben werden, wieder in die Freispeicher-Liste kommt. Darüber hinaus überprüft sie, ob er direkt an seinen Vorgänger oder an seinen Nachfolger oder an beide grenzt. In diesen Fällen werden die aneinandergrenzenden Blöcke zu einem Block zusammengefasst und nur noch dieser gesamte Block in der Freispeicher-Liste verwaltet.

Die Funktion rundet ebenfalls die übergebene Blockgröße auf ein Vielfaches von acht auf.

Falls die übergebene Anfangsadresse des Speicherblocks NULL oder seine Größe gleich null ist, soll SpeicherFreigeben nichts machen.

FreispeicherListe nach Aufruf von <code>SpeicherHolen(56 KByte)
Bild 2: FreispeicherListe nach Aufruf von SpeicherHolen(56 KByte)

Fehlerhafte Funktionsaufrufe (z. B. ein Speicherblock wird mehrmals freigegeben oder freigegebene Speicherblöcke überlappen) können vernachlässigt werden, da die Funktionen nur vom Betriebssystem verwendet und nicht den Benutzerprozessen zur Verfügung gestellt werden.

Testet Eure Freispeicherverwaltung mit dem Programm SpeicherTest. Dazu fügt Ihr vorübergehend ein

#include "SpeicherTest.c"

in MinMax.c ein und ruft nach der Initialisierung, aber vor dem Start des Interpreters, die Funktion SpeicherTest auf. Eine Änderung des Makefiles ist dabei nicht erforderlich.

b. Dynamisches Allozieren und Freigeben von Benutzer- und Systemkeller für Benutzerprozesse

Der Speicher für die Keller der Benutzerprozesse soll nicht mehr statisch vorhanden sein, sondern in mxLader beim Start eines neuen Prozesses alloziert und bei dessen Termination wieder freigegeben werden. Führt die dazu notwendigen Änderungen an den Funktionen LadeProzess und Freigeben durch. Die Variable Speichertabelle ist nun überflüssig. Bedenkt dabei, dass das Allozieren des Speichers auch fehlschlagen kann, und reagiert geeignet darauf. Überlegt beim Terminieren eines Prozesses genau, in welcher Reihenfolge freigegeben werden muss. Nach der korrekten Einführung dieser Änderung soll die maximale Anzahl von Prozessen auf 20 hochgesetzt werden.

c. Synchrone Kommunikation über Nachrichten

In dieser Ausbaustufe soll es den Benutzerprozessen ermöglicht werden, miteinander zu kommunizieren. Insgesamt werden dazu vier neue Systemaufrufe in MinMax eingebaut. Sie lassen sich in die beiden Bereiche Namensdienst und Kommunikation aufteilen. Grundlage für die Kommunikation ist der Namensdienst. Er ermöglicht es, dass sich Programme gegenseitig ansprechen können. Bevor ein Prozess mit einem anderen kommunizieren kann, muss er durch den Systemaufruf

int sys_NameAnmelden( tName Name )

dem Betriebssystem den Namen bekannt geben, unter dem er von anderen Prozessen angesprochen werden kann. Dieser Name muss eindeutig sein, d. h. der Systemaufruf muss scheitern, wenn ein anderer Prozess diesen Namen schon angemeldet hat. Mit dem parameterlosen Systemaufruf

void sys_NameAbmelden( void )

kann ein Prozess seinen Namen wieder löschen. Gleichzeitig wird dadurch allen Prozessen, die noch auf eine Nachricht von ihm warten oder gerade eine Nachricht an ihn senden, mitgeteilt, dass es diesen Kommunikationspartner nicht mehr gibt.

Die eigentliche Kommunikation erfolgt über die Systemaufrufe

tKommunikationsStatus sys_Senden( tName Empfaenger, char *Nachricht )

und

tKommunikationsStatus sys_Empfangen( tName *Sender, char *Nachricht )

wobei die beiden Typen tName und tKommunikationsStatus in mxStrukturen folgendermaßen definiert werden sollen:

typedef char tName;
#define cKeinName (char)0
typedef enum {
  eOk, eNichtAngemeldet, eUnbekannt
} tKommunikationsStatus;

Die verschiedenen Statusmeldungen haben folgende Bedeutung:

eNichtAngemeldet der aufrufende Prozess hat sich nicht angemeldet
eUnbekannt es existiert kein Prozess mit dem übergebenen Namen
eOk der Kommunikationsdienst konnte korrekt erbracht werden

Die Kommunikation erfolgt synchron, d. h. beide teilnehmenden Prozesse werden blockiert, bis die Nachricht tatsächlich vom Sender zum Empfänger kopiert worden ist. Die Nachrichten sollen nullterminierte Strings von höchstens cStringLaenge Zeichen (ohne Nullzeichen) sein, entsprechen also tString. Die Implementierung der Systemdienste soll gemäß der vorgegebenen Header-Datei mxKommunikation.h erfolgen. Ihr solltet beim Einfügen der neuen Systemaufrufe die Konventionen aus Anhang A beachten, damit Euer finales MinMax später die vorbereiteten Testprogramme ausführen kann! Die Kommunikation könnt Ihr jetzt schon mit PDVIXtest.c testen.

Hinweise zur Implementierung:

Bei der Implementierung könnt Ihr auf die vorgeschlagene Datenstruktur tNachrichtenZustand aus mxKommunikation.h zurückgreifen, die Bestandteil des Prozessverwaltungsblocks werden soll: Im Nachrichtenzustand wird vermerkt, ob der Prozess gerade sendet (Senden == 1) oder empfängt (Empfangen == 1). In Partner steht zunächst der gewünschte Kommunikationspartner und nach dem Empfangen der tatsächliche Kommunikationspartner, von dem die empfangene Nachricht stammt. In Puffer vermerkt der Prozess, wo die Daten der Nachricht stehen bzw. wo die Nachricht hinkopiert werden soll (dies kann direkt von Systemaufrufpaket zu Systemaufrufpaket erfolgen!). In Resultat trägt der kopierende Prozess nach dem Kopiervorgang eOk ein. Die Funktionen Senden und Empfangen sind dann sehr ähnlich zu implementieren. Das Kopieren der Nachricht erfolgt manchmal aus Senden und manchmal aus Empfangen und sollte daher in eine Hilfsfunktion ausgelagert werden.

Beim Einbinden der Kommunikation ist auf eine korrekte Behandlung bei der Prozesstermination zu achten. Es soll u. a. gewährleistet werden, dass

Beim Namensdienst sollen folgende Regeln berücksichtigt werden:

Die Kommunikation soll folgende Bedingungen erfüllen:

Sowohl logische als auch betriebsmittelorientierte Synchronisation werden bei der Kommunikation benötigt:

Mit Hilfe der logischen Synchronisation werden Prozesse blockiert bzw. deblockiert, die auf Nachrichtenversand oder -empfang warten. Dazu enthält die Struktur tNachrichtenZustand ein Semaphor, auf das beim Senden bzw. Empfangen blockiert wird, bis die gewünschte Nachricht kopiert wurde. Wenn ein Prozess seinen Namen abmeldet, müssen ebenfalls alle auf ihn wartenden Sender und Empfänger deblockiert werden.

Die betriebsmittelorientierte Synchronisation bei dieser Aufgabe erfordert mindestens ein Semaphor, das die Manipulation und Abfrage der Nachrichtenzustände der Prozesse schützt. Hier muss unbedingt verhindert werden, dass zwei Prozesse "gleichzeitig" eine Nachricht an denselben Empfänger schicken, obwohl der nur eine Nachricht haben wollte. Kritisch ist dann nur noch die Stelle, an der sich ein Sender oder Empfänger selbst blockieren muss, weil er auf die Kommunikation warten will.

Bei nennenswerter Langeweile könnt Ihr noch dafür sorgen, dass ein wegen Kommunikation blockierter Prozess von einem anderen Prozess aus terminiert werden kann. Das ist nämlich recht hilfreich, funktioniert aber leider nicht automatisch. Tipp: Es genügt typischerweise, in BeendenVorbereiten eine V-Operation zum Aufwecken des zu terminierenden Prozesses einzufügen. Beachtet dabei aber, dass der Zustand des Warte-Semaphors gültig bleibt bzw. wiederhergestellt wird!


Aufgabe 5

Mit dieser Ausbaustufe sollen die Benutzerprozesse endlich aus dem MinMax-Programm entfernt und statt dessen aus einem minimalen Dateisystem geladen werden. Dieses Dateisystem wird beim Start von MinMax in eine "RAM-Disk" geladen. Den Zugriff auf das Dateisystem übernimmt das zur Verfügung gestellte Modul mxDatei. Es ist in der Dokumentation zur Entwicklungsumgebung beschrieben und bei den ausgedruckten Dateien dabei. Damit MinMax die Benutzerprogramme, die in diesem Dateisystem gespeichert sind, starten kann, sind mehrere Änderungen notwendig:

a. Laden der Benutzerprogramme

Da die Benutzerprogramme nicht mehr als Funktionen in MinMax enthalten sind, muss die Funktion LadeProzess umgestellt werden. Statt in ProzessAufruf[] nach dem Prozessnamen zu suchen, steht das zu startende Programm jetzt im Dateisystem. LadeProzess versucht, das Programm mit dem erhaltenen Namen aus dem Dateisystem zu laden und zu starten. Dazu muss natürlich Speicher für den neuen Prozess zur Verfügung gestellt werden.

Das Dateisystem enthält für jedes Programm Informationen über den für das Programm benötigten Speicher. Dabei wird unterschieden zwischen Speicher für Code, Daten, Konstanten, Benutzer- und Systemkeller. Für jeden dieser Bereiche muss vom Lader ein entsprechend großer Speicherblock alloziert werden. Anschließend werden Code und Konstanten aus dem Dateisystem in die für sie reservierten Speicherbereiche geladen. Das Segment für die Daten muss mit Nullen initialisiert werden, da die C-Konventionen das verlangen und die Benutzerprogramme von einem so vorbereiteten Daten-Segment ausgehen könnten.

b. Vornehmen der Adressumsetzung

Da beim Binden der Benutzerprogramme noch nicht feststeht, an welcher Adresse im Speicher sie ausgeführt werden, kann der Code noch keine absoluten Adressen enthalten. Statt dessen steht im Code der Offset, den das hier angesprochene Objekt in seinem Segment hat.

Beispiel:

Ein Programm besteht aus einem 1 KByte großem Code-Segment und einem 500 Byte großen Daten-Segment. Die Funktion A beginnt an Byte 200 des Code-Segments und die Variable B an Byte 50 des Daten-Segments. Wenn nun im Code die Adresse der Funktion A benötigt wird, enthält der Code hier als Adresse den Wert 200. Wenn auf die Variable B zugegriffen werden soll, wird die Adresse 50 im Code verwendet.

Dieser Code kann natürlich nicht ausgeführt werden, da die in ihm angegebenen Adressen nicht die gewünschten Speicherzellen referenzieren. Deshalb muss vor dem Starten des Programms eine Adressumsetzung vorgenommen werden, durch die in den Code die richtigen Adressen eingesetzt werden. Wenn ein Programm statisch initialisierte Zeiger als Variablen enthält, können sogar im Konstanten-Segment solche Adressumsetzungen notwendig werden. Dafür enthält jedes Programm im Dateisystem eine Liste von Fixups. Fixups sind Referenzen auf die Positionen im Programmcode oder Konstanten-Segment, an denen eine absolute Adresse referenziert wird. Zusätzlich enthält ein Fixup noch die Information, welches Segment (Code, Daten oder Konstanten) über diese Adresse angesprochen werden soll.

Beispiel:

In dem oben beschriebenen Programm soll in Byte 100 des Code-Segments auf die Variable B zugegriffen werden, d. h. dieses Byte enthält den Wert 50. Dazu gibt es dann ein Fixup, das als Referenz in das Code-Segment den Wert 100 enthält und außerdem angibt, dass hier vom Code-Segment auf das Daten-Segment zugegriffen werden soll.

Durch das Allozieren der Speicherblöcke für die verschiedenen Segmente sind die Anfangsadressen der Segmente bekannt. Damit können alle absoluten Adressen bestimmt werden, indem man auf den im Code angegebenen Offset die Anfangsadresse desjenigen Segments addiert, das hier angesprochen werden soll.

Beispiel:

Der Speicherblock, der für das Code-Segment des oben beschriebenen Programms alloziert wurde, beginnt an Adresse 10000, der für das Datensegment an Adresse 20000. Mit Hilfe des aus dem Dateisystem erhaltenen Fixups kann festgestellt werden, dass im hundertsten Byte des Code-Segments ein Zugriff auf eine Speicherzelle des Daten-Segments vorgenommen werden muss. Damit muss nach dem Laden des Codes in das Code-Segment an Adresse 10100 eine Adressumsetzung vorgenommen werden. Auf den dort gespeicherten Offset muss die Anfangsadresse des Daten-Segments addiert werden, d. h. dort muss nach der Adressumsetzung die Adresse 20050 eingetragen sein.

Nachdem die Adressumsetzung mit allen Fixups des Programms durchgeführt wurde, kann das Programm gestartet werden.

Implementiert die oben beschriebene Adressumsetzung im Modul mxLader.

c. Trennung von System- und Benutzer-Adressraum

Durch das Entfernen der Benutzerprozesse aus dem Betriebssystem entsteht jetzt eine klare Trennung zwischen dem Benutzer- und dem Systemadressraum. Der neue MinMax-Kern "kennt" nicht von vornherein die Adressen, an denen bestimmte Funktionen der Benutzerprogramme liegen werden, und die Benutzerprogramme kennen keine Adressen des MinMax-Systems. Die einzige Schnittstelle dazwischen ist die Systemaufruf-Schnittstelle, denn sowohl MinMax als auch die Benutzerprozesse "verstehen" den Aufbau der Systemaufruf-Pakete.

Dies bedeutet, dass Ihr nun die Module mxSystemAufruf, mxBenutzer und mxInterpreter aus MinMax entfernt. Die Module mxTrap und mxLib gibt es fortan sowohl in MinMax als auch in den Benutzerprogrammen, aber natürlich als separate Kopien für MinMax und für jedes einzelne Benutzerprogramm.

Mit der Entfernung von mxSystemAufruf aus dem Betriebssystem kann MinMax nun nicht mehr die Adresse der Systemaufruf-Funktion sys_Terminiere im Benutzerkeller eintragen, um ein automatisches Terminieren eines Benutzerprozesses nach seiner letzten Anweisung zu gewährleisten. Statt dessen erhält jedes Benutzerprogramm ein winziges Zusatzmodul mxUserInit, in dem nur die Funktion _start steht. Sie wird als erste Funktion des Benutzerprogramms aufgerufen, weil sie durch den Binderaufruf im Makefile als erste Funktion im Programmcode steht. _start ruft nacheinander main im Benutzerprogramm und anschließend sys_Terminiere auf. Damit wird das Eintragen einer Rücksprungadresse im Benutzerkeller überflüssig. Trotzdem muss der Platz der Rücksprungadresse im Benutzerkeller weiterhin belegt werden, da sonst die Parameterübergabe an _start und main nicht funktioniert!

d. Neuer Systemaufruf für Inhalt des Dateisystems

Damit die Benutzerprozesse (und hier vor allem der Kommandointerpreter) erfahren können, welche Programme im Dateisystem gespeichert werden, muss noch die Funktion LiesVerzeichnis des Moduls mxDatei als Systemdienst zur Verfügung gestellt, d. h. ein weiterer Systemaufruf sys_LiesVerzeichnis in MinMax eingeführt werden. Die für diesen Systemaufruf relevanten neuen Datenstrukturen für MinMax und die Benutzerprogramme stehen bereits in der Vorgabe mxDatei.h. Die dortigen Deklarationen legen unter anderem fest, dass die Namen der Benutzerprogramme maximal 23 Zeichen lang sein können, wobei der Rest des Feldes (mindestens ein Byte) mit dem Füllzeichen (char)0 aufgefüllt ist.

Es müssen die üblichen Änderungen für die Einführung neuer Systemaufrufe durchgeführt werden. Wiederum solltet Ihr Anhang A beachten.

e. Anpassen der Benutzerprogramme

Als letzte Änderung müssen noch die Benutzerprogramme an die neue Situation angepasst werden. Dazu werden aus den bisher verwendeten Funktionen Hauptmodule gemacht, d. h. statt des Moduls mxBenutzer mit den Funktionen ProzessAB und ProzessC und dem Modul mxInterpreter mit der Funktion Interpreter gibt es nun die Module ProzessAB (ProzessAB.c), ProzessC (ProzessC.c) und Interpreter (Interpreter.c). Innerhalb jedes Moduls gibt es jetzt eine Funktion main.

Die im Makefile unter EXES eingetragenen Benutzermodule werden im Prinzip normal übersetzt. Damit sie jedoch in das Dateisystem aufgenommen werden können, werden sie anschließend von dem speziell für MinMax entwickelten Programm "mxLink" bearbeitet. Die so erzeugten Dateien im MinMax-Programmformat (Endung ".mxe" können als zusätzliche Argumente an "mxBoot" übergeben werden, das diese (ohne ".mxe") in die RAM-Disk einträgt, die beim Booten des mx nun zusammen mit MinMax übertragen wird.

Während sich die Änderungen bei ProzessAB und ProzessC auf das Erstellen von eigenen Modulen beschränken, muss der Interpreter an die neue Situation angepasst und um das Kommando "D", mit dem das Dateiverzeichnis ausgegeben wird, erweitert werden.

Testet Euer "fertiges" MinMax mit den im Verzeichnis minmax99/apps abgelegten, fertig übersetzten mxe-Dateien. Diese könnt Ihr in Eure "RAM-Disk" integrieren, indem Ihr sie unter DISK im Makefile eintragt. Nur wenn sich diese Applikationen fehlerfrei ausführen lassen, habt Ihr alles korrekt implementiert. Wenn Ihr beim Aufbau der Systemaufrufpakete von den Konventionen in Anhang A abgewichen seid, müsst Ihr die Beispielprogramme wahrscheinlich neu übersetzen - die Quellen stehen in minmax99/apps/src. Besonders wichtig ist das Programm PDVIXtest.mxe, das sämtliche Systemaufrufe ausführlich testet - und voraussichtlich bei der Vorführung dieser letzten Aufgabe am Rechner eine wichtige Rolle spielen wird. (Wenn Ihr PDVIXtest.mxe unter DISK ins Makefile aufnehmen wollt, ohne dass es neu übersetzt wird, müsst Ihr entweder den vollständigen Pfad angeben oder als Namen den symbolischen Link pt11.mxe verwenden, der in minmax99/apps vorhanden ist.)

Tipp zur Bearbeitungsreihenfolge:

Führt zunächst alle Änderungen durch, die für MinMax selbst relevant sind. Anschließend sollten alle Neuerungen bei den Systemaufrufen gleichzeitig eingeführt werden. Als letztes können dann die Benutzerprozesse angepasst werden. Vergesst nicht die Änderungen am MinMax-Makefile!


Anhang A

PDVIX-konforme Systemaufrufpakete im finalen MinMax

Die Auflistung in diesem Anhang zeigt die am Ende der 5. Aufgabe mindestens implementierten Systemaufrufe mit dem byteweisen Aufbau der zugehörigen Systemaufrufpakete und den numerischen Werten der Typkennung. Ihr solltet die hier gezeigten Konventionen befolgen, damit Euer finales MinMax binärkompatibel zu vorbereiteten Benutzerprogrammen ist. Dann könnt Ihr fertig übersetzte Benutzerprogramme auch mit anderen Gruppen tauschen. Wenn Ihr zusätzliche Systemaufrufe implementiert habt, sollten diese andere Typkennungen haben. Nur bei sys_SystemStatus ist Platz für eigene Erweiterungen fest vorgesehen.

Wir nennen die Binärkompatibilität von MinMax PDVIX-Konformität. Die folgende Auflistung zeigt den aktuellen Standard PDVIX 1.1:

sys_StarteProzess:
Typ = 0 (4 Byte)
Name (24 Byte) bzw. Prozessnummer (4 Byte)
Argument-String (max. 81 Byte)
sys_TerminiereProzess:
Typ = 1 (4 Byte)
Prozessnummer (4 Byte)
sys_Terminiere:
Typ = 2 (4 Byte)
sys_ProzessInformationen:
Typ = 3 (4 Byte)
Prozess 0: Status (4 Byte)
Prozess 0: Name (41 Byte)
Prozess 0: AmTerminieren (1 Byte)
Prozess 0: Abgeschossen (1 Byte)
Prozess 0: ImKern (1 Byte)
...
Prozess 19: Status (4 Byte)
Prozess 19: Name (41 Byte)
Prozess 19: AmTerminieren (1 Byte)
Prozess 19: Abgeschossen (1 Byte)
Prozess 19: ImKern (1 Byte)

cMaximaleProzessAnzahl sollte also auf 20 gesetzt sein!

sys_LiesZeichen:
Typ = 4 (4 Byte)
Zeichen (1 Byte)
printf:
Typ = 5 (4 Byte)
Ausgabe-String (max. 81 Byte)
sys_SystemStatus:
Typ = 6 (4 Byte)
uptime (4 Byte)
evtl. eigene Erweiterungen (60 Byte)
sys_Setze7Segment:
Typ = 7 (4 Byte)
Zahl (4 Byte)
Stellen (4 Byte)
sys_Schlafe:
Typ = 8 (4 Byte)
Millisekunden (4 Byte)
sys_FensterOeffnen:
Typ = 9 (4 Byte)
Fensternummer (4 Byte)
sys_FensterSchliessen:
Typ = 10 (4 Byte)
Fensternummer (4 Byte)
sys_FensterWechseln:
Typ = 11 (4 Byte)
Fensternummer (4 Byte)
sys_LiesString:
Typ = 12 (4 Byte)
Wieviel (4 Byte) bzw. String (max. 81 Byte)
sys_FensterXY:
Typ = 13 (4 Byte)
Spalte X (4 Byte)
Zeile Y (4 Byte)
sys_NameAnmelden:
Typ = 14 (4 Byte)
Rückgabewert (4 Byte)
Name (1 Byte)
sys_NameAbmelden:
Typ = 15 (4 Byte)
sys_Senden:
Typ = 16 (4 Byte)
KommunikationsStatus (4 Byte)
Empfänger (1 Byte)
Nachricht (max. 81 Byte)
sys_Empfangen:
Typ = 17 (4 Byte)
KommunikationsStatus (4 Byte)
Sender (1 Byte)
Nachricht (max. 81 Byte)
sys_LiesVerzeichnis:
Typ = 18 (4 Byte)
tatsächliche Anzahl (4 Byte)
1. Dateiname (24 Byte)
...
20. Dateiname (24 Byte)

Stand: 15.06.2006