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 FunktionenSchreibSeriell 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önnten.
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 entgegen genommen 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.
Die V-Operation muss auch mit Lock/Unlock geschützt werden, sofern sie nicht aus einer Unterbrechunsbehandlung aufgerufen wird (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. cTAB 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 ersten acht 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.
Bild 1: 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.
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.
Bild 2: FreispeicherListe nach Aufruf von
SpeicherHolen(56 KByte)
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.
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.
Ihr solltet 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. 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önnen.
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 Kommando-Interpreter)
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 den vollständigen
Pfad angeben.
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: 05.03.2008
| Letzte Änderung: 05.03.2008 Daniel Lüdtke |
 Impressum |