Bild 1: mögliche Freispeicher-Liste
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.
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.
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.
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.
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!
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.
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!
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.
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.
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.
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.
In dieser Aufgabe sollt Ihr MinMax um eine Freispeicherverwaltung erweitern.
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 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.
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.
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.
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.
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
der Name eines Prozesses automatisch bei dessen Termination freigegeben wird,
alle Prozesse, die blockiert sind, weil sie auf eine Nachricht eines
gerade terminierten Prozesses warten oder eine Nachricht an ihn senden
wollen, mit Status eUnbekannt aus
Senden bzw.
Empfangen zurückkehren.
Beim Namensdienst sollen folgende Regeln berücksichtigt werden:
Jeder Prozess kann maximal einen Namen besitzen.
Jeder Name kann maximal einem Prozess gleichzeitig zugeordnet sein (d. h. die Namen müssen eindeutig sein).
Wechselt ein Prozess seinen Namen (in dem er sich unter einem neuen Namen oder unter demselben Namen erneut anmeldet), so wird sein bisheriger Name automatisch gelöscht.
Beim Abmelden eines Namens werden alle Prozesse, die noch auf Kommunikation mit dem abmeldenden Prozess warten, deblockiert.
Die Kommunikation soll folgende Bedingungen erfüllen:
Ein Senden ist nur möglich, wenn der Empfänger bereits existiert und der Sender einen Namen angemeldet hat.
Empfangen ist möglich, sobald der Empfänger seinen Namen
angemeldet hat. Er kann an ihn gerichtete Nachrichten entweder von
beliebigen Sendern empfangen, indem er cKeinName angibt,
oder gezielt Nachrichten eines bestimmten Senders auswählen, indem
er dessen Kommunikationsnamen angibt.
Nur wenn beim Empfangen ausdrücklich ein Sender ausgewählt
wurde, aber kein Prozess mit diesem Namen (mehr) existiert, wird beim
Empfangen der Status eUnbekannt zurückgegeben.
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!
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:
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.
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.
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.
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.
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.
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!
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.
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.)
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!
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:
| Typ = 0 (4 Byte) |
| Name (24 Byte) bzw. Prozessnummer (4 Byte) |
| Argument-String (max. 81 Byte) |
| Typ = 1 (4 Byte) |
| Prozessnummer (4 Byte) |
| Typ = 2 (4 Byte) |
| 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!
| Typ = 4 (4 Byte) |
| Zeichen (1 Byte) |
| Typ = 5 (4 Byte) |
| Ausgabe-String (max. 81 Byte) |
| Typ = 6 (4 Byte) |
| uptime (4 Byte) |
| evtl. eigene Erweiterungen (60 Byte) |
| Typ = 7 (4 Byte) |
| Zahl (4 Byte) |
| Stellen (4 Byte) |
| Typ = 8 (4 Byte) |
| Millisekunden (4 Byte) |
| Typ = 9 (4 Byte) |
| Fensternummer (4 Byte) |
| Typ = 10 (4 Byte) |
| Fensternummer (4 Byte) |
| Typ = 11 (4 Byte) |
| Fensternummer (4 Byte) |
| Typ = 12 (4 Byte) |
| Wieviel (4 Byte) bzw. String (max. 81 Byte) |
| Typ = 13 (4 Byte) |
| Spalte X (4 Byte) |
| Zeile Y (4 Byte) |
| Typ = 14 (4 Byte) |
| Rückgabewert (4 Byte) |
| Name (1 Byte) |
| Typ = 15 (4 Byte) |
| Typ = 16 (4 Byte) |
| KommunikationsStatus (4 Byte) |
| Empfänger (1 Byte) |
| Nachricht (max. 81 Byte) |
| Typ = 17 (4 Byte) |
| KommunikationsStatus (4 Byte) |
| Sender (1 Byte) |
| Nachricht (max. 81 Byte) |
| Typ = 18 (4 Byte) |
| tatsächliche Anzahl (4 Byte) |
| 1. Dateiname (24 Byte) |
| ... |
| 20. Dateiname (24 Byte) |
Stand: 15.06.2006
| Letzte Änderung: 15.06.2006 Daniel Lüdtke |
 Impressum |