Betriebssysteme
Geschwurbel von Daniel Schwamm (10.05.1994 bis 23.05.1994)
Inhalt
Es gibt grob unterschieden zwei Arten von Software (SW): Systemsoftware und
Anwendungssoftware. Die wichtigste Systemsoftware ist das Betriebssystem (BS) an
sich. Es umfasst den Kern, die Compiler, die Editoren und die Interpreter,
die von der aufsitzenden Anwendungssoftware (z.B. Datenbanksystem (DBS) oder
Spiele) benötigt werden.
Das BS hat zwei wesentliche Funktionen:
-
Virtuelle Maschine: Das BS sitzt auf der Hardware (HW) auf,
die aus dem physikalischen Gerät, der Mikroprogrammierung und der
Maschinensprache besteht. Das BS schirmt den Anwender dadurch von
der Komplexität der HW ab und erleichtert deren Programmierung.
-
Verwaltung: Das BS verwaltet alle Betriebsmittel. Dadurch wird
z.B. dafür gesorgt, dass nicht zwei Programme einen Drucker gleichzeitig
verwenden.
Die Rechner-Architektur eines Rechners betrifft eher die Hardware als
die Software (bzw. das Betriebssystem). Sie umfasst den Instruktionssatz, die
Speicherorganisation, die Input-/Output-Verarbeitung und die Busstruktur. Redet
man von Rechnerfamilien, bedeutet dies, dass hier die Architektur weitgehend
aufwärts kompatibel gehalten wurde. Woraus dann auch resultiert, dass i.d.R.
das gleiche BS Verwendung finden kann.
| 1850 |
Charles Babbage baute den ersten echten Digitalrechner ohne BS. |
| 1945 |
1.Generation (Röhrenrechner). Noch ohne Assembler oder gar BS. |
| 1955 |
2.Generation (Transistor-Rechner). Stapelverarbeitung, Jobs,
FORTRAN, Assembler, MULTIC (Multiplexed Information and Computing Service) und
Bandlaufwerke finden Verwendung. |
| 1965 |
3.Generation (IC-Rechner). Offline Mehrprogramm-BS (z.B. IBM
System/360), später auch online Time Sharing-BS. Das Spooling
automatisiert die Job-Abarbeitung und Ken Thompson programmiert MULTIC zu UNIX
(Uniplexed Information and Computing System) um. Erste Minirechner (z.B. DEC PDP)
tauchen auf. |
| 1980 |
4.Generation (LSI-Rechner). PCs, Workstations drängen auf den
Markt. Es gibt zahlreiche BS, v.a. MS-DOS, WINDOWS und UNIX, z.T. auch schon
verteilte Betriebssysteme (VBS). Generell ist die Benutzerfreundlichkeit der BS
enorm gestiegen. |
Konzeptionelle Bestandteile eines jeden BS sind: Systemaufrufe
(BS-Instruktionen zur Bearbeitung von Systemressourcen nach dem Schema "TRAP
... BS hat Kontrolle ... RETURN FROM TRAP"), Prozesse, Dateien und eine oder
mehrere Shells (die eigentlich kein Teil des BS sind, sondern nur spezielle
Prozesse). Diesen Bestandteilen werden wir uns später noch zuwenden.
Strukturlose BS nennt man monolithische Systeme. Bei diesem Modell sieht der
Benutzer das BS als Blackbox und kennt nur die Systemcalls zu seiner
Benutzung.
Geschichtete Systeme haben BS, die sich aus mehreren SW-Modulen aufbauen,
die untereinander über Dienstaufrufe kommunizieren. Beim THE-System z.B.
gibt es sechs Schichten, wobei die erste Schicht für das Multiprogramming
zuständig ist und die letzte Schicht für die direkte Bearbeitung der
Benutzerprozesse.
Virtuelle Maschinen bieten dem Benutzer nicht nur ein BS,
sondern mehrere Betriebssysteme an, die aber alle auf einem gemeinsamen BS fussen,
z.B. im Falle der S/370 auf dem Virtual Machine-Betriebssystem (VM).
Die Client-Server-Modelle (C/S-Modelle) haben das BS auf den unbedingt nötigen
Kern reduziert und alle Komplexität in Serverprozesse verlagert, die von
Client-Prozessen aktiviert werden können. Der Kern arbeitet nur
mechanistisch - er betreibt Interprozesskommunikation (IPC) und sonst
nichts -, während die Server strategisch vorgehen. C/S-Modelle eignen sich
im besonderen Masse für VBS, wie wir noch sehen werden.
Die Einprozessmaschinen sind out. Heute können BS mehrere Prozesse
gleichzeitig verarbeiten (Multiprocessing). Wie lange jeder Prozess die
CPU nutzen darf, entscheidet der sogenannte Scheduler. Üblich ist, dass
I/O-lastige Prozesse höhere Priorität besitzen als andere Prozesse.
Es gibt die Prozesszustände und die Prozessübergänge:
<------------------------ 3 -----------------------
rechnend ---- 1 ----> blockiert ---- 4 ----> bereit
------------------------- 2 ---------------------->
Zur Verwaltung der einzelnen Prozesse benötigt das BS eine Tabelle,
die pro Prozess Informationen enthält über: Register,
Statuswort, Programmzähler, Erzeugerzeit, PID, Datensegmentzeiger,
Vaterprozess, Wurzelverzeichnis, Stack-Zeiger, Datei-Deskriptoren usw.
Werden mehrere Prozesse pseudo-parallel bearbeitet, dann muss es
Strategien geben, die dafür sorgen, dass es bei konkurrierendem
Zugriff auf die Ressourcen nicht zu Dateninkonsistenzen kommen kann.
Nehmen wir als Beispiel für einen zeitkritischen Ablauf das
Erzeuger-Verbraucher-Problem: Ein Erzeuger füllt einen Puffer, der vom
Verbraucher geleert wird. Die Gefahr besteht nun darin, dass der
Verbraucher den Puffer gerade leert, vom Erzeuger unterbrochen wird, der neue
Daten in den Puffer füllt. Wenn nun der Verbraucher wieder das Kommando erhält,
interpretiert er eventuell die neuen Daten als die ursprünglichen Daten.
Mittels geschickter IPC kann dafür gesorgt werden, dass immer nur ein Prozess im
kritischen Bereich tätig ist, d.h. Zugriff auf die Ressource besitzt.
Ein BS wie UNIX bietet sogar mehrere Möglichkeiten zur Lösung des
Erzeuger-Verbraucher-Problems an:
-
Sperren aller Interrupts. Nachteil: verschwenderisch.
-
Shared Variable als Ja-/Nein-Flag benutzen. Hierbei besteht jedoch die
Gefahr, dass gerade während der Prüfung und der Änderung des Flags ein
Prozesswechsel stattfindet.
-
Striktes Alternieren: Ein Prozess prüft aktiv ein Shared Flag,
bis es eine spezielle Nummer angenommen hat, die nur für diesen
Prozess gilt.
-
Peterson-Algorithmus (nach Larry Peterson):
void enter_krit_region(int process) {
interested[process]=TRUE;
turn=process;
while(turn==process && interested[1-process]==TRUE);
};
void leave_krit_region(int process){interested[process]=FALSE;};
Auch wenn Prozess-2 die Variable "turn" direkt nach Prozess-1 überschreibt,
so wird doch zuerst Prozess-1 ausgeführt. Prozess-2 hängt dann so lange in
einer Schleife, bis Prozess-1 "leave_krit_region()" aufruft.
-
TSL-Instruktion: Einige BS bieten Test-and-Set-Lock-Befehle an, z.B.
"tsl register, flag". Sowie die "flag"-Sperre gelöst wird, wird es wieder
gesperrt und sein Wert an "register" übergeben, wo es in aller Ruhe
überprüft werden kann. Nachteile: Busy Waiting,
Prioritätsinversionsproblem (Scheduler wählt laufend hohe
Prioritätsprozesse, obwohl nur ein niedriger Prioritätsprozess
Sperre auflösen kann).
-
Semaphoren: Semaphoren sind Shared Flags, die einen Prozess schlafen legen,
so wie sie null sind, ansonsten aber nach jedem atomaren Betriebssystem-Aufruf
inkrementiert oder dekrementiert werden. Nachteil: Die Semaphoren-Reihenfolge
ist nicht unwichtig.
void producer() {
down(empty); // Puffer leer? Wenn nein, schlafe
down(mutex); // kritischer Bereich möglich? Wenn nein, schlafe
fill_puffer();
up(mutex); // wecke eventuell consumer
up(full); // Puffer voll
};
void consumer() {
down(full); down(mutex);
clr_puffer();
up(mutex); up(empty);
};
-
Ereigniszähler: Jeder Eintrag inkrementiert "e", jede Austragung
inkrementiert "a". Es muss stets gelten:
0 <= e - a <= Puffergrösse.
Es gibt dazu einen BS-Befehl, der einen Prozess so lange schlafen legt,
bis der Ereigniszähler einen bestimmten Wert angenommen hat.
-
Monitore: Einige BS erlauben es, Prozeduren einzurichten, die mehrere
Prozesse beinhalten, von denen aber immer nur einer aktiv sein kann. Ein
Compiler übernimmt dabei automatisch die korrekte Semaphore-Setzung. Nachteil:
Der Blockademechanismus muss explizit programmiert werden.
-
Pipes: Bei dieser Technik können, müssen Prozesse aber nicht
gleichzeitig laufen, da Pipes wie Mailboxen funktionieren. Der Erzeuger sendet
dem Verbraucher den zu füllenden Puffer (genauer: Die Adresse der Pipe)
zu, und der Verbraucher sendet den geleerten Puffer anschliessend wieder
zurück.
Ein klassisches Kommunikationsproblem haben wir im vorherigen Abschnitt
bereits kennengelernt: das Erzeuger-Verbraucher-Problem. Weitere seien nun
vorgestellt:
-
Das Philosophen-Problem: Um einen runden Tisch sitzen fünf
Philosophen, jeder hat eine Gabel zu seiner Linken und vor sich einen Teller
Spaghetti. Zum Essen benötigt er zwei Gabeln, d.h., ein Philosoph kann nur
dann Essen, wenn keiner seiner Nachbarn isst. Dieses Problem lässt
sich folgendermassen lösen:
Erst gelangt ein hungriger Philosoph über den Semaphore-Mechanismus
alleine in den kritischen Bereich. Dort prüft er, ob seine beiden Nachbarn
essen. Falls ja, dann blockiert er so lange, ansonsten beginnt er zu essen,
wobei er den kritischen Bereich verlässt. Ist er fertig mit Essen, dann muss
er in den kritischen Bereich zurück, seinen Status auf "Thinking" setzen, die
Gabeln freigeben und den kritischen Bereich erneut verlassen.
-
Lesen-Schreiben-Problem: Dieses Problem ist bei DBS zu beachten, damit
ein Leser nicht ein Datum liest, dass im selben Moment überschrieben
wird, und ein Schreiber nicht etwas schreibt, das im selben Moment wieder
überschrieben wird. Eine Lösung des Problems ist:
Falls ein Leser auf die Datenbank zugreift, beansprucht er den kritischen Bereich
für sich alleine. Andere Leser können jederzeit hinzukommen, ein
Zähler hält allerdings ihre Anzahl fest. Der kritische Bereich wird
freigegeben, sowie dieser Zähler auf null steht. Erst dann kann ein
Schreiber den kritischen Bereich für sich alleine beanspruchen.
-
Schlafender-Friseur-Problem: Ein Kunde kommt zum Friseur. Falls kein
anderer Kunde da ist, weckt er den Friseur und lässt sich die Haare
schneiden. Ansonsten nimmt er im Warteraum Platz. Ist dort kein Stuhl mehr
frei, dann verlässt er den Salon wieder. Folgendermassen lassen
sich hier zeitkritische Abläufe verhindern:
Jeder neue Kunde wartet, bis er im kritischen Bereich alleine ist. Falls
"waiting" grösser-gleich der Stuhlanzahl ist, verlässt er
den Salon, ansonsten inkrementiert "waiting", der kritische Bereich wird
verlassen und über einen Semaphore auf die Bereitschaft des Friseurs
gewartet. Der Friseur schläft, bis der erste Kunde den Salon betritt. Nach
dem Kunden erhält der Friseur sofort exklusiven Zugriff auf "waiting",
welches er dekrementiert. Danach verlässt er den kritischen Bereich
wieder und schneidet dem Kunden die Haare.
Ein Scheduler entscheidet nach einer bestimmten Strategie (mehr als nur
ein blosser Mechanismus), welcher Prozess zu welchem Zeitpunkt die CPU
beanspruchen darf. Kriterien für einen guten Scheduler sind: Fairness,
Effizienz, kurze Antwortzeiten, kurze Verweilzeiten und hoher Durchsatz.
Zumindest kurze Antwortzeiten und kurze Verweilzeiten sind als konträre
Zielsetzungen anzusehen.
Beim präemptiven Scheduling entscheidet der Scheduler in periodischen
Abständen darüber, ob ein Prozess die CPU behalten darf oder sie
abzugeben hat. Dadurch ist er nicht abhängig davon, dass sich ein Prozess
bei I/O-Operationen freiwillig schlafen legt. Ältere BS betreiben ein
End-to-Completion-Scheduling, d.h., der Scheduler übergibt hier jedem
Prozess bis zu seiner Terminierung die CPU. Ein solcher Scheduler eignet
sich bestenfalls für einen reinen Stapelbetrieb.
Oben wurde bereits erwähnt, dass Scheduler ihre Entscheidungen auf bestimmte
Strategien zurückführen. Beispiele für solche Strategien sind:
-
Round-Robin-Scheduling: Das bedeutet Queue-Abarbeitung, wobei jeder
Prozess ein festes Zeitquantum zugewiesen bekommt. Dies stellt die üblichste
Form des Scheduling dar.
-
Prioritätsscheduling: Der Prozess mit der höchsten Priorität wird für
eine bestimmte Zeit ausgeführt und danach seine Priorität dekrementiert. I.d.R.
werden dazu verschiedene Prozessklassen gebildet, wobei jede Klasse intern per
Round-Robin-Scheduling CPU-Zeit zugewiesen bekommt.
-
Multi-Queue-Scheduling: Bei dieser Strategie bekommen lange Prozesse bei
jeder erneuten Aktivierung ein doppelt so langes Zeitquantum zugewiesen und
werden danach über eine anderen Queue verwaltet.
-
Shortest-Job-First-Scheduling: Anhand alter Jobs kann abgeschätzt
werden, wie lange ein neuer Job zur Abarbeitung benötigt. Diejenigen, die
voraussichtlich am wenigsten CPU-Zeit beanspruchen, werden zuerst und nach
Möglichkeit komplett abgearbeitet.
-
Garantiertes Scheduling: Jeder Prozess hat ein Anrecht darauf,
innerhalb seiner Session-Zeit genau so viel CPU-Zeit zu erhalten, wie alle
anderen aktiven Prozesse. Der Scheduler achtet darauf, dass dieses Gleichgewicht
eingehalten wird (Zeit = Sessionzeit / Benutzeranzahl).
-
Benutzerprozessgesteuertes Scheduling: Der Vaterprozess weiss, wie viel
Zeit seine jeweiligen Kindprozesse benötigen und weist ihnen aktiv selbst die
CPU zu. Die Strategie obliegt damit dem Vater, der Mechanismus bleibt beim Scheduler.
-
Zweistufiges Scheduling: Prozesse, die im Hauptspeicher liegen, werden
bei der CPU-Vergabe bevorzugt gegenüber Prozessen, die im Hintergrund ablaufen.
Im Einprogrammbetrieb fällt die Speicherverwaltung einfach aus, da der
gesamte RAM-Bereich (Read Access Memory; Arbeitsspeicher) einem einzigen
Prozess zur Verfügung steht. Allerdings ist darauf zu achten, dass i.d.R.
immer auch einige BS-Teile ebenfalls RAM für sich beanspruchen.
Beim Mehrprogrammbetrieb gilt die Regel, dass die CPU umso besser
ausgelastet wird, je mehr Prozesse gleichzeitig ablaufen, weil dann die
Wahrscheinlichkeit klein ist, dass alle Prozesse durch I/O-Operationen
blockiert sind. Aus diesem Grund wächst die CPU-Auslastung auch mit der
Erweiterung des Speichers, weil mehr Speicher bedeutet, dass mehr Prozesse
gleichzeitig ablaufen können.
Um beim Mehrprogrammbetrieb den einzelnen Prozessen Speicher zur Verfügung
zu stellen, wird der Gesamtspeicher partitioniert - üblicherweise in
mehrerer Partitionen fixer Grössen. Diese Partitionen sind pro Grössenklasse
durch eine eigene Queue verwaltbar oder für alle Grössenklassen nur durch
eine einzige Queue. Letztere Option scheint die sinnvollere Methode zu sein,
weil weniger komplex.
Bei der Unterteilung des Speichers in Partitionen für Prozesse ist das
Relokationsproblem (Verschiebeproblem) und das Schutzproblem zu
beachten. D.h., es muss sichergestellt werden, dass die Prozessadressen relativ
zur Position des zugewiesenen Speicherbereichs angelegt werden, und dass ein
Prozess nur innerhalb seines eigenen Speicherbereichs wahlfreien Zugriff
besitzen darf. Üblicherweise geschieht dies durch die Einrichtung eines
Basisregisters (mittels Hardware), welches bei jedem Prozesswechsel die
Startadresse des Speicherbereichs des aktuellen Prozesses erhält.
Wenn der Speicherbedarf aller aktiven Prozesse grösser ist als der aller
Partitionen des Speichers (was z.B. bei Time Sharing-BS nahezu ständig
gegeben ist), dann müssen Teile des Speichers auf der Platte abgelegt
und dort auch verwaltet werden. Üblich sind hierbei variable Partitionen,
die über Referenztabellen angesprochen werden können. Solche
Referenztabellen können sein:
-
Bitmaps: Der Speicher wird in Allokationseinheiten unterteilt, wobei
jede Allokationseinheit durch ein Bit repräsentiert wird. Wird freier Speicher
gesucht, müssen also entsprechend viele zusammenhängende Bits gefunden werden,
was allerdings zeitaufwendig ist.
-
Verknüpfte Listen: Das sind doppelt verkettete Listen, deren Elemente nach
Adresse sortiert sind, wodurch sich Speicher-Verschmelzungen und -Aufspaltungen
vereinfachen, und die ein Längenfeld enthalten. Als Belegungsstrategien kommen
infrage: First Fit, Next Fit, Best Fit (Nachteil: hohe Fragmentation), Worst
Fit und Quick Fit (pro Grössenklasse eine eigene verknüpfte Liste).
-
Buddy-System: Der leere Speicherbereich wird jeweils in zwei
gleichgrosse "Buddies" unterteilt, bis der angeforderte Speicherplatz in
minimaler Grösse einer Zweierpotenz vorliegt. Jeder Buddy wird durch
eine eigene Queue verwaltet, d.h., bei einem Speicher von 1 MByte gibt es 21
Queues, wobei die erste Queue (2^0)-Byte- und die letzte (2^20)-Byte-Buddies
verwaltet. Vorteil: Die Allokation von Speicher geht leicht vonstatten,
denn wenn 2^k-Byte Speicher benötigt, muss nur die (2^k)-Byte-Buddy-Queue
durchsucht werden, nicht aber auch alle anderen Queues.
Falls ein Programm so gross ist, dass es nicht komplett in den
Arbeitsspeicher passt, dann müssen Teile davon auf der Platte ausgelagert und
bei Bedarf wieder eingelesen werden. Das BS sorgt dafür, dass dies nach
bestimmten Strategien geschieht. Dem Benutzer gaukelt es dadurch einen
virtuellen Speicher vor, der um ein Vielfaches grösser sein kann als
der physikalische Speicher. Aus diesem Grund können virtuelle Adressen aber
auch nicht direkt auf den Speicherbus gelegt werden, sondern müssen
zunächst von der Memory Management Unit (MMU) in physikalische Adressen
umgerechnet werden.
Um nicht jede Adresse dieser Prozedur zu unterziehen, wird der virtuelle
Speicher in Seiten von der Grösse 8 kB unterteilt, die mit den physischen
Seitenrahmen korrespondieren. Die MMU greift auf Tabellen zurück, die diese
Seiten verwalten. In diesen steht, in welchen Seitenrahmen eine Seite bei
Bedarf hineinzukopieren ist. Bei einem virtuellen Adressraum von 32 bit
(4 GB) und einer Seitengrösse von 4 kB macht das 1 Millionen mögliche
Seiten, also 1 Millionen Einträge der Form:
Caching? | Referenziert? | Modifiziert? | Schutz? | Present/Absent?| Seitenrahmennummer
Es gibt verschiedene Methoden, über die die physikalischen Seitenrahmen aus den
virtuellen Seiten zu berechnen sind:
-
Seitentabelle komplett in Registern: zu teuer.
-
Seitentabelle komplett im Speicher: Ein CPU-Register zeigt dabei auf die
jeweils aktuelle Seite.
-
Mehrstufige Seitentabellen: Eine Tabelle zeigt mit ihren 1024
Einträgen jeweils auf eine andere Tabelle, die dann die eigentlichen
Seitenrahmen referenzieren (zweistufige Seitentabellen, z.B. bei VAXEN
üblich). SPARCstations benutzen dreistufige, 68030er Prozessoren von
Motorola sogar vierstufige Seitentabellen. Vorteil: Es müssen nie alle
Tabellen gleichzeitig im Arbeitsspeicher gehalten werden.
-
Assoziativspeicher und Seitentabellen: Ein Assoziativspeicher ist ein
Baustein der MMU, der sich ca. 32 Seitentabellen-Einträge merken kann und
einen sehr schnellen Zugriff erlaubt. Nur wenn eine gewünschte Seite hier
nicht vorhanden sein sollte, muss auf die Seitentabelle zurückgegriffen werden.
-
Reine Assoziativspeicher: Die MIPS R2000 verzichtet auf jede
Seitentabelle und benutzt einen Assoziativspeicher mit 64 Einträgen. Falls
hier die gewünschte Seite nicht enthalten ist, rechnet das BS anhand
bestimmter Register den zugehörigen Seitenrahmen eigenständig aus.
-
Invertierte Seitentabellen mit Assoziativspeicher: Bei einem virtuellen
Adressraum von 64 bit nehmen Seitentabellen so grosse Ausmasse an, dass sie von
vorneherein nur noch auf Platte gelagert werden können. Im Hauptspeicher wird
nur eine Seitenrahmentabelle (invertierte Seitentabelle) verwaltet. In der MMU
selbst liegt ein Assoziativspeicher vor. Das System/370-BS von IBM greift z.B.
auf diese Paging-Methode zurück.
Da die virtuelle Seitenanzahl die physikalische Seitenrahmenanzahl übertreffen
kann, kommt es vor, dass bei Bedarf einer bestimmten Seite zuvor eine alte Seite
aus dem Speicher entfernt werden muss. Welche die zu entfernende Seite ist,
entscheidet das BS nach einer der folgenden Strategien, die i.d.R. auf das
Referenced-Bit (R-Bit, welches normalerweise alle paar Sekunden automatisch
gelöscht wird) und das Modified-Bit (M-Bit) der Seitentabelle zurückgreifen:
-
Not-Recently-Used-Seitenersetzung: Das BS untersucht die R- und M-Bits
der Seiten und bildet daraus vier Klassen: 0=NOT-R UND NOT-M, 1=NOT-R UND M,
2=R UND NOT-M, 3=R UND M. Gelöscht wird stets eine Seite mit möglichst niedrigster
Klasse. Falls mehrere gleichwertige Seiten vorliegen, wird eine davon per
Zufall ausgewählt.
-
FIFO-Seitenersetzung (First in, first out): Bei dieser Methode wird die
jeweils älteste Seite ersetzt.
-
Second Chance-Seitenersetzung: Es wird wie bei der FIFO-Seitenersetzung
verfahren. Aber: Ist das R-Bit gesetzt, wird es gelöscht, die Seite an das Ende
der Queue angehängt, und erneut die älteste Seite gesucht.
-
Uhr-Seitenersetzung: Es wird wie bei der Second Chance-Seitenersetzung
verfahren. Aber: Statt einer Queue wird eine zyklische Liste verwendet, sodass
nur der Startpointer wie der Zeiger einer Uhr auf den nächsten Eintrag verrückt
wird.
-
Least-Recently-Used-Seitenersetzung: Bei jeder Referenzierung einer
Seite wird ein Zeiger inkrementiert, woran das BS später erkennen kann,
welche Seiten nur selten benötigt werden. Wenig benutzte Seiten werden
anschiessend im Bedarfsfall bevorzugt ersetzt.
Früher ging man davon aus, dass je mehr Seitenrahmen im Speicher
haltbar sind, desto weniger Seitenfehler auftreten würden. Doch die
sogenannte Belady-Anomalie widerlegte diese Generalisierung für die
FIFO-Seitenersetzung. Die Seitenfolge "0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4" z.B.
produziert bei 4 Seitenrahmen 10 Seitenfehler und bei 3 Seitenrahmen nur 9
Seitenfehler, sofern FIFO eingesetzt wird.
Zu Beginn eines Prozesses werden ständig Seitenfehler produziert, weil
die Seiten noch nicht im Speicher vorhanden sind. Weiss man jedoch den
Anfangsarbeitsbereich eines Programms, so können schon vor dessen
Ausführung die nötigen Seitenrahmen allokiert werden. Dies wird durch
ein Arbeitsbereich-Modell erreicht (im Gegensatz zum Anforderungspaging).
Bisher haben wir noch nicht unterschieden, ob die Seitenersetzungsalgorithmen
lokal für einen Prozess oder global für alle Prozesse durchgeführt
werden sollte. Die globale Seitenersetzung scheint die sinnvollere Variante zu sein;
wenig aktive Prozesse können so nach der Page-Fault-Frequency-Strategie ganz
aus dem Speicher ausgelagert werden, wodurch sich die Seitenfehlerrate einzelner
aktiver Prozesse verringert.
Die Wahl der Seitengrösse ist entscheidend für die Effizienz des Pagings.
Ist sie zu gross, wird Speicherplatz verschwendet, ist sie zu klein, dann
werden die Verwaltungstabellen übermässig gross. Kennt man die durchschnittliche
Prozessgrösse "S", dann lässt sich die optimale Seitengrösse "P" folgendermassen
bestimmen:
Sei "E" die Anzahl Bytes pro Tabelleneintrag eines Prozesses, dann werden
pro Prozess "S/P" Bytes benötigt. Daraus ergibt sich eine
Tabellengrösse von "(S/P)*E" Bytes pro Prozess. Die interne
Fragmentierung verschwendet im Schnitt die Hälfte der letzten Seite,
dadurch ergibt sich ein Gesamt-Overhead pro Prozess von:
Overhead = (S/P)*E + P/2.
Da wir den Overhead zu minimieren wünschen, bilden wir die erste Ableitung
über "P" und erhalten die Gleichung:
0 = -((S/P)*E)/P + 1/2 ==> P = Wurzel(2*S*E)
Trifft ein Prozess auf die Instruktion "MOVE.L #6(A1), A0", die eine
nicht im Speicher liegende virtuelle Adresse enthält, so wird ein
Seitenfehler produziert, die Seite in den Speicher kopiert und die Instruktion
wieder aufgenommen. Aber an welcher Stelle? Obige Instruktion ist 6 Bytes lang,
der Programmzähler zeigt irgendwo dazwischen, sodass der Prozessor
die Instruktion nicht mehr nachvollziehen kann. Noch schlimmer wird es, wenn es
sich um eine inkrementierende Instruktion handelt. Aus diesem Grund müssen
bei Seitenfehlern die Startposition und die Inkrementationszahl der
Abbruchsinstruktion in zwei Register gespeichert werden.
Einige Seiten müssen vorm Löschen geschützt werden, obwohl
sie schon lange nicht mehr referenziert wurden, denn es kann sein, dass
in ihnen bestimmte I/O-Puffer liegen. Wir die Seite weggenommen, schreibt das
I/O-Gerät seinen Output fälschlicherweise in die neue Seite, da es ja
von dem Seitenwechsel nichts wissen kann. Um solche Seiten zu schützen,
existieren in den Seitentabellen spezielle Schutz-Flags.
Bei einigen Seiten ist es sinnvoll, sie mehreren Prozessen
zur Verfügung zu stellen, nämlich dann, wenn beide Prozesse das gleiche
Programm ausführen, z.B. einen bestimmten Editor. Dies gilt natürlich nur
für Programmseiten, nicht Datenseiten.
Besonders nützlich sind Paging-Dämone, die im Hintergrund laufen und ständig
dafür sorgen, dass länger unbenutzte Seiten als überschreibbar markiert sind,
sodass immer ein paar freie Seitenrahmen bei Bedarf zur Verfügung stehen.
Tabellen, die ihre Grösse dynamisch ändern, machen ihre
Haltung im Speicher nicht einfach. Daher erlauben viele BS die Segmentierung
des Speichers, d.h. dass beliebig grosse Speicherbereiche angefordert
werden können, die unabhängig voneinander sind. Auch ihre
Grösse kann noch während der Laufzeit geändert werden.
Anders als beim Paging muss die Segmentierung jedoch vom Benutzer extra
angefordert werden. Dadurch sind auch seine Zugriffsrechte von Hand bestimmbar
- Shared Segmente sind dadurch keine Probleme mehr, d.h., jeder Prozess
kann ein bestimmtes Segment in den eigenen Adressraum einblenden, hat
darauf aber nur die Rechte, die der Segmenterzeuger vergeben hat.
Übrigens: Die Segmente können auch virtuell sein!
Dateien sind persistent (absturzsicher), von vielen Prozessen gleichzeitig
benutzbar, und ideale Speicher für beliebig grosse Datenmengen.
Strukturiert sind sie entweder als Byte-Sequenzen, als Records oder als
Bäume (bei Grossrechnern). Als Dateitypen gibt es gewöhnliche
Dateien (ASCII für Texte oder binär für ausführende und
archivierende Dateien), Verzeichnisse und zeichenorientierte bzw. blockorientierte
Spezialdateien. Auf Dateien kann entweder sequenziell oder direkt zugegriffen
werden. Mögliche Attribute sind z.B. Schutzbits, Erzeugername,
Eigentümername, Archivierungsflags, Grösse, maximale Grösse und Satzgrösse.
Übliche Operationen auf Dateien sind: Create, Delete, Open, Close, Write,
Read, Append, Seek, GET/SET Attributes und Rename.
Statt auf die Dateioperatoren zurückzugreifen, bieten einige BS die
Möglichkeit, Dateien in den Speicher "hineinzumappen", z.B. in den
Adressraum eines laufenden Prozesses. Dieser Prozess kann dann auf
die Datei zugreifen, als sei sie ein Stück RAM (Read und Write werden
nicht benötigt). Bei Prozessterminierung wird die Datei automatisch
auf die Platte zurückgeschrieben. I.d.R. finden hier Segmente Verwendung,
damit die Dateien auch wachsen können. Nachteilig an diesen
speicherabgebildeten Dateien ist jedoch, dass es zu Problemen bei
konkurrierendem Zugriff kommen kann.
Bei den meisten BS sind Verzeichnisse nichts anderes als besondere Dateien.
Üblicherweise sind Verzeichnisse hierarchisch strukturiert (ausser
bei CP/M und beim C64), sodass Namenskonflikte minimiert werden, und
das BS nur die Wurzeladresse auf der Platte kennen muss, um einen vom
Benutzer angegebenen (absoluten oder relativen) Pfadnamen parsen zu können.
Das jeweils aktuelle Verzeichnis wird Arbeitsverzeichnis genannt. An
Operationen auf Verzeichnisse stehen üblicherweise zur Verfügung:
Create, Delete, Opendir, Closedir, Readdir, Writedir, Link (ein Dateiname
steht in mehreren Verzeichnissen) und Unlink.
Die Blöcke auf der Platte werden vom Dateisystem (DS) nach verschiedenen
Methoden verwaltet:
- Kontinuierliche Allokation: Nachteil: Fragmentierung
- Allokation mittels verknüpfter Listen: Nachteil: Zeiger braucht Platz
- Allokation mittels Indizes (MSDOS): Nachteil: Index ist komplett im Speicher zu halten.
- I-Nodes (UNIX): Mehrfachverkettung.
Bei MSDOS stehen die Dateinamen und seine Attribute in den jeweiligen
Verzeichnisdateien. Bei UNIX stehen in den Verzeichnisdateien nur die
Dateinamen und die I-Nodes, In den I-Nodes befinden sich dann alle weiteren
Informationen zu den Dateien.
Ähnlich wie beim Paging die Seitengrösse, spielt beim DS die Blockgrösse
eine wesentliche Rolle bezüglich der Systemperformance. I.d.R. wählt man
als Blockgrösse "B" ein Vielfaches der physikalischen Sektorengrösse. Die
durchschnittliche Zugriffszeit "Z" auf eine Datei lässt sich folgendermassen
ermitteln:
Z = Positionierungszeit + (B/Spurgrösse) * Rotationszeit
Die freien Blöcke einer Platte werden entweder über Freilisten
oder Bitmaps verwaltet. Bei leeren Platten sind Freilisten besser, bei vollen
Platten dagegen Bitmaps. Die Implementierung beider Methoden ist üblich.
Damit ein Benutzer in einem Multiuser-BS nicht die ganze Platte für sich
alleine beanspruchen kann, vergibt der Systemadministrator i.d.R.
Plattenquanten mit harten und weichen Grenzwerten an die Benutzer.
Wird eine weiche Grenze Überschritten, so wird der Benutzer beim nächsten
Einloggen gewarnt. Ignoriert er die Warnung mehr als dreimal, dann kann er
sich nicht mehr einloggen. Harte Grenzen können dagegen niemals überschritten
werden.
Das DS sorgt auch für die Sicherheit der abgespeicherten Daten. Die
Zuverlässigkeit wird gewährleistet durch Fehlerblockverwaltungen, durch
Backups und durch Techniken, die die Systemkonsistenz überwachen.
Um die langwierigen Zugriffe auf die Platte zu minimieren, speichern BS
häufig Blöcke statt direkt auf die Platte erst einmal im Cache ab,
einem reservierten Pufferbereich im Hauptspeicher. Um den Cache effektiv
auszunutzen, kommen wieder die Seitenersetzungsalgorithmen zum Zuge.
Allerdings muss bezüglich des LRU-Algorithmus (least recently used)
einschränkend bemerkt werden, dass I-Node-Blöcke ständig benutzt werden und
daher nicht auf Platte gesichert werden, was bei einem Systemausfall
gravierende Folgen für die durch sie lokalisierten Dateien haben kann. Aus
diesem Grund sorgt bei UNIX der Hintergrundprozess SYNCH alle 30 Sekunden
dafür, dass der Cache auf Platte gesichert wird. MSDOS dagegen
benutzt einen Write-Through-Cache, der bei jeder Modifikation den Cache sofort
auf die Platte durchschreibt. Dass dies real nicht bei jedem eingetippten
Buchstaben passiert, ist den programminternen I/O-Puffern zu verdanken,
um die sich die Programmierer nicht selbst kümmern müssen.
Neben dem Caching lässt sich die DS-Performance auch noch durch regelmässige
Defragmentierungsprozeduren verbessern.
Einige (bekannte) Sicherheitsmängel seien aufgeführt:
-
Im frühen UNIX konnte man über "lpr" die Passwortdatei
unleserlich ausdrucken, mit der Option, sie anschliessend automatisch zu
löschen. Da "lpr" die effektive UID (User Identification) des Superusers
trug, gelang dies auch. Die Folge waren allgemeine Systemzusammenbrüche.
-
In MULTICS war die Sicherheit des Time-Sharing-BS hui, die des
Stapelbetriebs aber pfui. Über Jobs liessen sich ohne grossen
Aufwand Trojanische Pferde in das "bin"-Verzeichnis von anderen Teilnehmern
einschleusen.
-
Robert Morris Internet-Wurm legte 1988 weltweit Tausende von Computer lahm.
-
Viele Vieren haben traurige Berühmtheit erlangt, z.B. der PLO-Virus.
Generelle Schwachpunkte bezüglich der Sicherheit von BS sind:
- Monitore u.ä. können geschützte Bereiche im Speicher/auf Platte einsehen.
- Monitore können als gelöscht markierte Plattenteile einsehen.
- Viele Programme lassen sich über falsche Parameter verwirren.
- Nach dem Einloggen Break-Taste drücken, um Batch-Sperren zu überwinden.
- Modifikation von BS-Strukturen im Benutzeradressraum, z.B. Handler.
- Verführung der schlecht bezahlten Sekretärin.
- Benutzer-Authentifizierung austricksen.
- Login-Bildschirm simulieren, um Passwörter abzufangen.
Schutz-Domänen durch Zugriffsmatrizen einrichten: Beschränkt Zugriff von
Objekten für bestimmte Prozesse. Eine Domäne ist dabei ein Objekt-Rechte-Paar.
Verschiedene Domänen können sich überschneiden, so kann z.B. ein Drucker "lpt1"
von den Domänen "1" und "2", nicht aber "3" benutzt werden. Möchte man die Domäne
wechseln, so kann dies in UNIX über "setuid/setgid" geschehen, sofern man die
entsprechenden Passwörter weiss. Die Zugriffsmatrizen werden entweder als
Zugriffskontrolllisten oder als Capabilities-Liste implementiert, die weniger
Speicherplatz beanspruchen.
-
Zugriffskontrolllisten: Jedem File ist eine Domäne zugeordnet, die
Auskunft darüber gibt, wer welche Rechte auf das Fiel besitzt. Diese Liste
wird in UNIX in einem separaten I-Node gespeichert, auf den ein Eintrag der
Datei-I-Nodes hinweist. Ein Zeileneintrag könnte z.B. folgendermassen
aufgebaut sein: "File 1: (Schwamm, Gruppe1, RWX)".
-
Capabilities-Liste: Jedem Prozess wird vom BS eine C-Liste
zugeordnet, in der steht, welche Rechte er auf welche Objekte besitzt. Ebenso
führen Capabilities auch immer gewisse generische Rechte mit sich, so
z.B. COPY CAPABILITY, COPY OBJECT, KILL OBJEKT, KILL CAPABILITY usw. Nachteilig
daran ist, dass das BS einem Prozess nicht einfach seine
Zugriffsrechte nehmen kann, und dass die C-Liste natürlich vor den
Prozessen zu schützen ist. Dies kann geschehen durch:
- C-Liste vollständig im BS-Adressraum halten (z.B. in Hydra realisiert).
- Capabilities verschlüsseln, v.a. in VBS wie Amoeba angewandt.
-
Tagged Architektur: Ein Tag-Bit muss verändert werden, um einen C-Eintrag zu
modifizieren. Nur das BS ist aber in der Lage, das Tag-Bit zu ändern.
Absolute Sicherheit durch ein Schutzmodell ist in einem Rechnersystem
nicht zu erreichen, denn wie B.W. Lampson zeigte, gibt es immer die Möglichkeit,
über versteckte Kanäle Informationen unbemerkt auszutauschen. Als
Beispiel nennt er das Confinement-Problem: Ein Server empfängt sensitive
Client-Daten, an die ein dritter Prozess heran will. Wenn der Server aktiv
ist, dann empfängt er eine "1", wenn er schläft, dann eine "0" -
dadurch kann der dritte Prozess erkennen, welche Daten der Server vom
Client erhält. Den gleichen Effekt erhält man beim Dateienöffnen bzw.
-sperren oder bei Seitenfehlern.
Über das BS werden I/O-Geräte gesteuert. Wir unterscheiden zwei Klassen von
Geräten: zeichenorientierte, wie z.B. Zeilendrucker, oder blockorientierte,
wie z.B. Festplatten. Die I/O-HW ist geräteunabhängig; über geräteabhängige
Treiber werden die Schnittstellen angepasst. Das BS ist über den Systembus
mit den Steuerwerken der I/O-Geräte verbunden. Das Steuerwerk verfügt über
Register, die i.d.R. im Adressraum des Rechners liegen. So besitzt die
386er-Uhr die I/O-Adressen von $040 bis $043. Nach Beschreibung dieser
Register wird das Gerät aktiv, während das BS weiterarbeiten kann, bis ihm
eine Unterbrechung signalisiert, dass das I/O-Ergebnis vorliegt. Wir sehen,
dass Steuerwerke ähnlich sind wie kleine Computer mit eigenem Speicher,
Registern, Fehlern und Kommandos.
Einige I/O-Geräte, v.a. die blockorientierten, unterstützen Direct Memory
Access (DMA). In diesem Fall muss der Prozessor die Daten nicht aus dem
Puffer des Gerätes in den Speicher kopieren, sondern kann dies das Steuerwerk
selbst übernehmen lassen. Dazu muss das Steuerwerk zwei Register besitzen:
eines für die Speicheradresse und eines für die Anzahl der übertragenen Daten.
Bei Festplatten ist im Zusammenhang mit DMA der Interleaving-Faktor zu
berücksichtigen: In der Zeit, in der die Daten aus dem Steuerwerk über den
Systembus in den Speicher gelangen, können keine neuen Daten von der Platte
empfangen werden, die sich aber ständig weiter dreht. Nur jeder x-te Block
ist daher von der Platte direkt lesbar, was durch eine entsprechende
Blocknummerierung zu beachten ist, wobei x dem Interleave-Faktor entspricht.
Die I/O-SW hat die Ziele:
- Geräteunabhängigkeit: Z.B. Disketten wie Festplatten behandeln.
- Fehlerbehandlung so nahe an HW wie möglich.
- Zugriff regeln: Exclusive und Shared Access.
Die I/O-SW lässt sich in vier Schichten unterteilen:
-
Unterbrechungsbehandlungsschicht: Die Geräteprozesse müssen sich durch
Semaphore mittels DOWN, über ein Receive-Kommando oder ein WAIT-Kommando
selbst blockieren. Nach Eintritt eines Ereignisse erfolgt die Entblockierung
des Prozesses durch das BS mittels einer Semaphoren-Freigabe, einer Nachricht
oder eines Signals.
-
Gerätetreiber-Schicht: Die SW dieser Schicht muss sich mit den
Details der diversen Geräte herumschlagen, z.B. dem Interleave-Faktor, um
korrekt arbeiten zu können. Die Treiber beschreiben die Register des
Steuerwerks, sie regeln die Queue-Abarbeitung von Kommandos der Form "Lies
Block n" und schlafen bei Nichtbenutzung.
-
Geräteunabhängige Software-Schicht: Ausführung von I/O-Funktionen,
die für alle Geräte gemeinsam gelten, wie z.B. die Pufferung, (das Fehlerhandling),
der Geräteschutz, die Gerätebenennung, ...
-
Benutzer-Input/Output-Software: Das ist die SW, die nicht zum BS gehört,
die aber der I/O dient, z.B. Bibliotheken wie "stdio.h" von C. Auch Spooling-Dämone
gehören hier dazu.
Die Hardware der Festplatten umfasst den Plattenarm mit dem Schreib-/Lesekopf
bzw. -köpfen. Die Platte besteht aus Zylindern, die von Spuren durchzogen
sind, wobei die Anzahl der Spuren mit der Anzahl der Schreib-/Lese-Köpfe
übereinstimmt. Die Spuren sind unterteilt in 8 bis 32 Sektoren. Auch wenn
die äusseren Sektoren länger sind, so haben jedoch alle Sektoren
die gleiche Kapazität.
Die Performance des Plattentreibers hängt wesentlich davon ab, welchen
Plattenarm-Scheduling-Algorithmus er verwendet. Alternativen sind:
- First Come, First Serve: Wenig optimierbar, weil nur ein Prozess bedient wird.
- Shortest Seek First: -: Pendelt in der Mitte umher, vergisst Ränder.
- Aufzug-Algorithmus: Behält eingeschlagene Richtung bei.
-
RAID: 38 Platten parallel für 38-bit-Wörter für fehlerkorrigierenden Hamming-Code.
Selbst bei Ausfall einer Platte ist das Bit rekonstruierbar.
Das Fehlerhandling des Plattentreibers betrifft folgende
Ereignisse:
- Programmierfehler, z.B. nicht-existenter Sektor wurde angefordert.
- Flüchtige Prüfsummenfehler aufgrund von z.B. Staub
- Permanente Prüfsummenfehler aufgrund von defekten Blöcken.
- Steuerwerksfehler, nimmt z.B. keine Kommandos mehr entgegen.
- Suchfehler aufgrund eines defekten Plattenarms.
Der Fall des Suchfehlers kann vom Plattentreiber oder dem BS z.B. dadurch korrigiert
werden, dass ein RECALIBRATE-Kommando ausgeführt wird, wodurch der Plattenarm in
Reset-Stellung geht, von wo aus er erneut auf die Suche gehen kann.
Einige Festplatten-Treiber beherrschen Spuren-Caching, d.h., sie lesen jedes Mal
ganze Spuren, statt nur einen Block, denn dadurch kann Suchzeit eingespart werden.
Allerdings sollte sich der Cache-Puffer im Steuerwerk befinden, um mittels DMA in
den Hauptspeicher kopiert zu werden, andernfalls muss die CPU bemüht werden.
Obwohl Uhren weder block-, noch zeichenorientiert sind, sind sie aufgebaut
wie Gerätetreiber. Entweder werden sie durch den Wechselstrom oder durch
einen internen Quarz geschaltet. Programmierbare Uhren besitzen
Zählregister, die batteriegepuffert sind. Problem: Die Zähler
können überlaufen (was bei UNIX z.B. im Jahre 2038 der Fall sein
wird). Ein Uhrtreiber hat die Aufgaben:
- Uhrverwaltung, z.B. Zähler-Inkrementierung bei jedem Uhrentick.
- Scheduler steuern.
- Erzeugerzeit von Prozessen dokumentieren.
- Profiling: Wie viel Zeit hat welcher Teil des Programms gebraucht?
- ALARM-Funktion realisieren.
Es gibt zwei Arten von Terminals:
-
Nicht-speicherbasierte Terminals: Tastatur und Bildschirm sind
unabhängig vom Computer. Sie stehen mit ihm über den seriellen Port
in Verbindung, wo jedes Byte mit Anfangs- und Endbit mit einer Datenrate von
1200 bis 9600 Baud übertragen wird, d.h. jedes Zeichen ist ca. eine
Millisekunde unterwegs. Die Schnittstellenkarte besitzt UARTs (Universal
Asynchronous Receiver and Transmitter) zur Zeichen-Bit-Transformation.
Verstehen diese Terminals auch Escape-Sequenzen
(z.B. zur Cursor-Positionierung), dann besitzen sie einen eignen Prozessor,
EPROM-Programme und Speicherplatz bis zu einem MByte. Beispiel: B-232-Terminals
von UNIX.
-
Speicherbasierte Terminals: Tastatur und Bildschirm sind Teile des
Computers. Über die parallele Schnittstelle können sie Zeichen auf
den Bus geben. Das Video-RAM liegt im Hauptspeicher. Beispiel:
MS-DOS-Terminals.
Über den Terminalmodus können Terminals verwaltet werden. Er enthält die Felder:
- Tabulatorengrösse
- Zeichen- oder Zeilenmodus: Letzterer lässt Zeilenkorrigierungen zu.
- Zeilenvorschub benötigt Wagenrücklauf oder nicht.
- Echo-Funktion an/aus: Spezielle Zeichenumwandlung erwünscht oder nicht.
- CTRL-Break-Modus an/aus
Die Output-SW hat darauf zu achten, dass diverse Zeichen besonders zu
interpretieren sind, so z.B. Escape-Sequenzen oder das ASCII-Klingel-Zeichen.
Ausserdem kann über die Echo-Funktion erreicht werden, dass manche
getippte Zeichen nicht auf dem Monitor erscheinen, was z.B. bei
Passworteingaben üblicherweise benötigt wird.
Betriebssysteme müssen Möglichkeiten zur Verfügung stellen, mit denen ein
Prozess (temporär) exklusiven Zugriff auf ein Betriebsmittel erhält. Doch wenn
mehrere Prozesse auf eine bestimmte Ressourcen zugreifen wollen, besteht durch
die Sperrung derselben Deadlock-Gefahr. Ein Deadlock ist eine gegenseitige
Sperrung, die nur von aussen aufgelöst werden kann.
Beispiel: Prozess A hat exklusiven Zugriff auf den Drucker, und
Prozess B hat exklusiven Zugriff auf die Datei, die beide Prozesse
ausdrucken wollen. Keiner der beiden Prozesse kann dann seine Arbeit
fortführen.
Vier Möglichkeiten zur Behandlung von Deadlocks sind:
-
Ignorieren (Vogel-Strauss-Politik): Dieser Weg wird zwar ungern von
Mathematikern eingeschlagen, doch die Praktiker von z.B. UNIX können ganz
gut damit Leben, dass eventuell Deadlocks auftreten können, von denen sie
bisher noch nichts wissen.
-
Erkennen und Beheben: Das Erkennen lässt sich über einen
Graphen erreichen, der auf Zyklen hin untersucht wird. Finden sich welche,
z.B. über Tiefensuche, dann liegt eine Deadlock-Situation vor. Ressourcen und
Prozesse sind hierbei die Knoten im Baum, wobei allokierte Ressourcen auf
den zugehörigen Prozess weisen und der Prozess selbst wiederum auf die
erwünschten Ressourcen weist.
Die Behebung kann erreicht werden über:
- die Unterbrechung eines Prozesses.
- Prozess an bestimmten Checkpoint zurückspringen lassen.
- die temporäre Aufhebung einer exklusiven Sperre eines Prozesses.
-
Verhinderung durch vorsichtige Betriebsmittelzuweisung: Weiss man
im Voraus, welche Prozesse welche Ressourcen wann allokieren, dann lassen sich
daraus sogenannte Betriebsmittel-Flugbahnen erstellen, die bei zwei Prozessen
ein anschauliches zweidimensionales Feld bilden, in dem es Deadlock-kritische
Zonen gibt, die es über eine geeignete Scheduler-Steuerung zu vermeiden gilt.
-
Vermeidung von Dreadlocks durch:
-
Spooling: Nur ein spezieller Dämon darf eine Ressource allokieren.
Diese Methode eignet sich allerdings nicht für alle Ressourcen.
-
Alles-oder-Nichts-Allokation: Ein Prozess kann erst aktiv werden,
wenn er alle Ressourcen allokiert hat. Gelingt ihm dies nicht auf Anhieb,
muss er sie wieder freigeben. Ähnlich wie beim Zwei-Phasen-Sperren
werden hier aber unnötig lange Ressourcen gesperrt.
-
Einfach-Allokation: Ein Prozess darf jeweils nur eine Ressource allokieren.
-
Betriebsmittel-Nummerierung: Bei diesem Verfahren hat die jeweils höchste
Nummer Vorrang.
Neben Betriebsmittel-Deadlocks gibt es auch noch andere Deadlocks. Z.B.
können sich Semaphore auf ewig gegenseitig Sperren, wenn sie in falscher
Reihenfolge aufgerufen werden. Verwandt mit Deadlocks ist auch das
Verhungern von Prozessen, was jedoch durch ein einfaches
FCFS-Scheduling (First Come, First Serve) verhindert werden kann.
Eines der ersten Time-Sharing-Betriebssysteme war CTSS (Compatible Time-Sharing
System), welches vom MIT, den Bell Labs und General Electric in MULTICS
umprogrammiert wurde. Da MULTICS in vieler Hinsicht zu komplex aufgebaut war
und noch dazu in der Sprache PL/1 programmiert war, wurde es jedoch bald wieder
aufgegeben. In den Bell Labs entwickelte dann Ken Thompson eine abgespeckte
Assembler-Version von MULTICS, die zunächst UNICS, dann EUNICS
und schliesslich UNIX hiess.
Dennis Ritchie gefiel UNIX, nur missfiel ihm dabei die Assemblerprogrammierung.
Also entwickelte Thompson aus BCPL (Basic Combined Programming Language; eine
vereinfachte Variante von CPL) zunächst die Sprache B, die von Ritchie
wiederum zur Sprache C umprogrammiert wurde. 1974 bauten dann Thompson
und Ritchie zusammen UNIX in C gänzlich neu auf. Da die Bell Labs zu AT & T
gehörten und dieses Unternehmen monopolistisch orientiert war, durfte die
beiden ihr Produkt allerdings nicht vermarkten, weshalb UNIX zunächst
kostenlos zur Verfügung stand. Nach einer Umstrukturierung von AT & T änderte
sich dies jedoch - nun wurde UNIX als System III bzw. System V verkauft
(System IV blieb aus; keiner weiss, warum). Bis zu diesem Zeitpunkt hatten
sich aber bereits die Berkeley-Universität und die DARPA dem Betriebssystem
UNIX angenommen und es auch substanziell geändert. Das BSD-UNIX (Berkeley
Software Distribution) kannte z.B. im Gegensatz zum AT & T-UNIX
bereits Paging, TCP/IP und etliche Standard-Hilfsprogramme.
Um ein Auseinanderdriften der beiden UNIX-Versionen zu
verhindern, wurde der POSIX-Standard verabschiedet, der für beide Systeme
gelten sollte. Aber IBM, DEC und HP glaubten, AT & T käme dabei zu gut weg,
und so gründeten sie kurzerhand einen eigenen Standard: OSF (Open System
Foundation). AT & T antwortete nun seinerseits mit einem eigenen Standard:
UI (UNIX International). Dadurch verfielen die Firmen letztlich darauf,
jede für sich eine eigene UNIX-Version zu entwickeln, sodass heute von
einem einheitlichen Standard keine Rede mehr sein kann.
Andrew Tanenbaum kritisierte darüber hinaus auch die zunehmende Komplexität
von UNIX und entwarf eine weitere eigene UNIX-Version namens MINIX,
welche heute gerne als Muster-UNIX für die Betriebssystem-Lehre verwendet wird.
1975 kam der erste PC auf den Markt, der Altair 8800 von MITS. Er basierte auf
dem 8080-Prozessor von Intel. Sein BS war CP/M von DR (Digital Research), und da
BASIC für dieses BS noch nicht vorlag, entwarf Bill Gates eine Version dazu.
Einen für IBM eher ungewöhnlichen Wege beschritt kurz darauf Philip Estridge,
als Big Blue in den PC-Markt einsteigen wollte: Er suchte IBM-externe Entwickler
wie Intel und Microsoft auf. Gates empfahl IBM zwar selbst noch CP/M als BS für
ihren PC, doch DR war mit der Entwicklung zu langsam. Also schnappte sich Gates
1981 den Programmierer Tim Paterson, und liess sich von diesem dessen 86-DOS auf
den 8088-Prozessor umprogrammieren. Dort wurde es als MS-DOS schliesslich mit
über 50 Millionen Installationen zum erfolgreichsten BS aller Zeiten.
1983 kam der PC/XT heraus und MS programmierte MS-DOS immer weiter in Richtung UNIX,
dessen Hauptvertreiber damals ebenfalls MS war. 1987 baute IBM die neue Linie PS/2
und dazu das neue BS OS/2, welches zwar wesentlich potenter als MS-DOS war, dennoch
aber nie richtigen Anklang bei der Kundschaft fand. 1991 gab Microsoft OS/2 schliesslich
auf, was zum Bruch zwischen IBM und MS führte. Danach wurde Apple zum Vertriebspartner
von IBM für OS/2, was am Nischendasein von OS/2 jedoch nichts zu ändern vermochte.
Zwei Entwicklungen der letzten Jahre führten zu verteilten Betriebssystemen (VBS):
Die Entwicklung von billigen Mikrocomputern und die Entwicklung von LANs. Die
Hardware (HW) für VBS steht demnach im Prinzip bereits zur Verfügung. Nur mit
der Software (SW) hapert es noch.
Doch was ist eigentlich die Intention hinter den VBS? Sehen wir uns dazu mögliche
Vorteile bzw. Nachteile an:
-
Im Vergleich zu Mainframes sind VBS wirtschaftlicher, skalierbarer,
schneller, zuverlässiger und an bestimmte Strukturen angepasster. Bei
PCs gilt von Groschs Gesetz nicht mehr, dass die Rechenleitung proportional
zum Quadrat des Preises zunimmt. Hier lohnt es sich, stets die schnellste
Kiste aufzutreiben, die man sich leisten kann.
-
Im Vergleich zu (mehreren) Stand-Alone-PCs sind VBS kommunikativer, flexibler,
die Leistung ist verteilter und die Redundanz weniger ausgeprägt.
-
VBS haben drei Probleme: Die SW, die Sicherheit der Daten und unzuverlässige Netzwerke.
Bei VBS spielen insbesondere Netzwerksysteme eine grosse Rolle. Schritte in
Richtung VBS sind Netzwerksysteme, die bereits heute Remote Operations erlauben,
mit Datei-Servern zusammenarbeiten und u.U. auch mit verschiedenen BS arbeiten
können, wie z.B. NFS (Network File System) von SUN. Doch auch wenn NFS das
Einbinden von entfernten Verzeichnissen gestattet, welche dann wie lokale
Verzeichnisse benutzt werden können, ist es kein vollwertiges VBS, denn zum
Einbinden der Verzeichnisse müssen Zielpfade eingegeben werden, d.h. die
Transparenz der Verteilung ist nicht zur Gänze gegeben. Auch können mit NFS
keine beliebigen entfernten Unterprogramme ausgeführt werden. Der zustandslose
NFS-Server gestattet zudem keinen exklusiven Zugriff auf bestimmte
Dateien - im Gegensatz zum RFS (Remote File System) von UNIX System V oder
diversen internen UNIX-Operationen.
Immerhin gibt es jedoch bereits Methoden im NFS, die die Sicherheit erhöhen,
z.B. öffentliche Schlüssel, die vom NIS (Network Information Service;
früher Yellow Pages) verwaltet werden. Die NIS-Server sind dabei im
Netzwerk repliziert. Es existiert zwar ein Hauptserver für alle Modifikationen,
dennoch sind kurzfristige Inkonsistenzen unvermeidbar. Caches in Clients bzw.
Servern verbessern die Performance erheblich, bringen jedoch u.U.
Kohärenzprobleme mit sich. Üblich sind daher alle drei Sekunden (bei
Verzeichnissen alle 30 Sekunden) Prüfungen auf Modifikationen.
Echte VBS verhalten sich wie virtuelle Einprozessor-Maschinen. Dazu sind
globale Dateisysteme nötig, ein globaler BS-Kern und eine Interprocess
Communication (IPC), die alleine über Nachrichten abläuft, da bei
Multicomputersystemen im Gegensatz zu Multiprozessorsystemen kein
Shared Memory existiert.
Wichtige Entwurfsziele der VBS-SW sind:
-
Transparenz: Die Transparenz des Ortes, der Migration, der Reputation
und der Parallelität sollte für VBS angestrebt werden. Gerade Letzteres
ist fast nicht möglich, da bei gezielter Verwendung mehrere Prozessoren
zur Lösung eines Problems diese bisher vom Programmierer auch direkt
angesprochen werden müssen.
-
Flexibilität: Mikrokern-BS sind monolithischen BS vorzuziehen;
dadurch sind z.B. MS-DOS- und UNIX-Server gleichzeitig als Dateisystem
denkbar.
-
Zuverlässigkeit: VBS erhöhen im Idealfall die Zuverlässigkeit. Fällt
hier nämlich ein einzelner Prozessor mit 5-prozentiger Wahrscheinlichkeit aus,
dann fallen fünf Prozessoren nur noch mit einer Wahrscheinlichkeit von 0.0006%
(0.05^5) aus. Weitere Zuverlässigkeitskriterien sind: Verfügbarkeit, Sicherheit
und Fehlertoleranz.
-
Leistung: Mögliche Leistungsmasse von VBS sind: Durchsatz, Antwortzeiten,
Benchmarks und v.a. Körnungsgrössen von Berechnungen (Granularität), wobei
grobe Körnungen vorzuziehen sind.
-
Skalierbarkeit: Alle zentralen Elemente sind zu eliminieren.
Der wesentliche Unterschied zwischen Einprozessormaschinen und verteilten
Systemen (VS) ist, dass VS keinen gemeinsamen Speicher besitzen, d.h.,
IPC-Mechanismen wie Semaphore oder Monitore sind hier nicht realisierbar.
Jede Kommunikation läuft daher auf einen Austausch von Nachrichten hinaus.
Um die Komplexität der Kommunikationssoftware zu reduzieren, wird sie
geschichtet angefertigt: Jede Schicht übernimmt dabei nur einen speziellen
Teilbereich zur Kommunikation. Das bekannteste Schichtenmodell ist das
ISO/OSI-Referenzmodell. Im Bezug auf VBS haben diese Schichtmodelle allerdings
den Nachteil, dass sie zu viel Leistung für z.T. unnötige Operationen benötigen.
So sind z.B. die Pakete unnötig gross durch die diversen Schichtheader. Oder
interne Felder wie Assembly/Reassembly machen bei LANs keinen Sinn, müssen aber
dennoch stets mittransportiert werden.
C/S-Kommunikation (Client/Server) läuft meistens verbindungsunabhängig ab,
was vergleichsweise einfache Anfrage-Antwort-Protokolle ermöglicht. In das
BS müssen im Prinzip nur die Aufrufe ...
send(destination, &messageptr);
und
receive(addr, &messageptr);
... implementiert werden. Zur Adressierung können dann jeweils der
Zielrechner und der dortige Zielprozess angegeben werden. Über einen
Name-Server wird für die nötige Transparenz gesorgt.
Folgende Alternativen gelten für die Primitive der C/S-Protokolle:
-
Blockierende (synchrone) bzw. nichtblockierende (asynchrone) Primitive:
Durch Timeout-Schranken lassen sich Ewigblockaden bei blockierenden Primitiven
verhindern. Dagegen sind Puffer nur bei nichtblockierenden Primitiven auf
Empfängerseite nötig.
-
Gepufferte (mailboxorientierte) bzw. ungepufferte Primitive: Bei ungepufferten
Primitiven muss "receive" vor "send" erfolgen.
-
Zuverlässige bzw. unzuverlässige Primitive: Quittung nötig oder nicht?
Typische Paketarten bei C/S-Modellen sind:
- REQ
- REP
- ACK
- AYA ("Lebst du noch?")
- IIA ("Ich lebe noch")
- TA ("Wiederhole")
- AU ("Ziel unbekannt")
Verlangen verteilte Betriebssysteme die Kommunikation auf Basis von
"receive" und "send", geht damit Transparenz verloren, da diese Kommunikation
eine angepasste Programmierung verlangt. Besser sind entfernte
Unterprogrammmechanismen (Remote Procedure Call; RPC), wie sie
Birell und Nelson (1984) vorgeschlagen haben. Der Nachrichtenmaustausch läuft
dabei völlig transparent ab. Das VBS erzeugt für Server- und Client-Prozesse
sogenannte Stubs, die für den korrekten Ablauf der Kommunikation (auch
kritischer Pfad genannt) sorgen:
Der Client ruft seinen Client-Stub auf. Der Client-Stub verpackt den Aufruf
und führt einen System-Call aus. Der Client-BS-Kern bestimmt die Zieladresse
(über Name-Server), setzt einen Timer und versendet die Nachricht zum
Server-BS-Kern. Der Server-BS-Kern entscheidet, welcher Server-Stub die
Nachricht erhält. Der Server-Stub entpackt den Aufruf und gibt in an den
Server-Prozess weiter. Der Server-Prozess führt den Aufruf aus (und liefert
dann das Ergebnis auf dem umgekehrten Weg wieder zurück).
Das Binden kann über die Stubs statisch geschehen, d.h., im Stub liegt
die Server-Adresse bereits fixiert vor. Besser ist jedoch ein dynamisches
Binden, sodass der Aufruf nicht immer an den gleichen Server gehen muss.
Dazu ist es aber wichtig, dass sich die Server zuvor bei einem Binder
(Name-Server?) registrieren lassen. Bei einem RPC kann sich dann der
Client beim Binder die Hardware-Adresse des passenden Servers besorgen.
So kann z.B. ein "read"-Aufruf einen "file_server"-Server verlangen,
der in der richtigen Versionsnummer vorliegen muss. Dadurch lässt sich
schon erhebliche Transparenz aufrecht erhalten, auch wenn z.B.
Call-by-Reference-Aufrufe üblicherweise durch Call-by-Copy-Aufrufe
ersetzt werden müssen. Treten allerdings Fehler auf, dann ist es aus mit
der Transparenz.
Mögliche Fehler können sein:
-
Client kann Server nicht lokalisieren: Dies kann passieren, wenn der
Client einen veralteten Stub hat, dessen Versionsnummer kein Server mehr
führt. Der Client muss dann neu kompiliert werden. Was soll in diesem
Fall das BS dem Client melden? "-1" könnte ein Ergebnis sein, also muss
ein Exception-Handler programmiert werden - und die Transparenz ist
für den Programmierer wieder einmal futsch.
-
Anfragen gehen verloren: Timeout-Schranken lösen das Problem. Erfolgt
nach Ablauf einer gewissen Zeit keine Antwort, wird die Anfrage wiederholt.
-
Quittungen gehen verloren: Timeouts und Sequenznummern gegen
Duplikat-Annahmen (weil nicht alle Unterprogramme idempotent sind) lösen
das Problem.
-
Server-Ausfall: Wünschenswert wäre hier eine
Genau-einmal-Semantik-Garantie, möglich ist i.d.R. aber nur eine
Höchstens-einmal- oder Mindestens-einmal-Semantik-Garantie.
-
Client-Ausfall: Dieser Fehler verlangt ein Orphan-Handling, denn
Waisen kosten CPU-Zeit und können neu gestartete Clients verwirren.
Möglichkeiten sind hier:
-
Ausrottung der Waisen über Protokollierungsdateien auf absturzsicheren Rechnern.
-
Reinkarnation: Neustart des Clients sorgt für eine neue Epoche, die alle
vorherigen RPCs verwirft.
-
Sanfte Reinkarnation: Hier werden nur die RPCs gekillt, die ihren Client
nach Prüfung nicht mehr finden können.
-
Verfallszeiten: Der Server muss vom Client regelmässig Zeitmarken erhalten,
sonst bricht er die RPC-Bearbeitung ab.
Die RPC-Protokolle sind i.d.R. nicht verbindungsorientiert, obwohl dadurch
ein Quittungsbetrieb auf Programmebene nötig wird. Aber LANs sind
relativ sicher und verbindungsunabhängige Protokolle wesentlich schneller.
Eher selten werden bereits vorhandene Protokolle für RPCs genutzt. Eine
Ausnahme stellt das Internet Protocol (IP) der UNIX-Netze dar, trotz
seiner vielen Nachteile für VBS, wie z.B., dass die Ethernet-Paketgrösse nur
maximal 1536 Bytes betragen darf, dass IP kein Endbenutzer-Protokoll ist, und
dass das IP für die LAN-Kommunikation unnötige Felder führt. Baut man Protokolle
selbst, muss man sich überlegen, ob einfache Stop-and-Wait-Protokolle
genügen, oder ob man besser die volle Bandbreite durch Blast-Protokolle
ausnutzt. Wenn man sich für Blast-Protokolle entscheidet, benötigt
man auch eine Flusskontrolle. Ausserdem müssen Fehlerfälle
durch Go-n-Back- oder Selective-Repeat-Algorithmen behandelt werden, wobei hier
der Aufwand den an und für sich sicheren LANs nicht ganz gerecht wird.
Problematisch an RPCs, v.a. im Bezug auf die Programmiersprache C, sind noch viele
weitere Dinge (C schlicht zu verbieten ist keine Lösung, sondern ein Bruch gegen das
heilige Transparenzziel):
-
"errno" ist eine globale C-Variable, die nach dem POSIX-Standard vorliegen muss.
Doch wie soll sich eine solche Variable in VBS ohne Shared Memory realisieren lassen?
-
In C können Felder beliebiger Länge übergeben werden. Wie soll der Stub solche Felder
verpacken können, ohne ihre Länge zu kennen?
-
Der C-Befehl "printf" erlaubt eine beliebige Anzahl von Parametern. Eine solche
Freiheit ist bezüglich RPCs de facto unmöglich.
In VBS genügen nicht Client-Server-Kommunikationen, sondern es sind
auch Server-Server-Kooperationen u.ä. nötig. Eine Kommunikation
zwischen Gruppen ist immer eine Einer-zu-Allen-Kommunikation, die sich durch
Broadcast-, Multicast-, n-facher Unicast- und - ganz neu! -
Prädikatenadressierung (Multicast + Bedingung) realisieren
lässt. Es ist darauf zu achten, dass Gruppen dynamisch sind,
daher gibt es i.d.R. einen Gruppen-Server, der Austritte und Aufnahmen
verwaltet.
Die HW/SW verlangt neue Wege bei Gruppenkommunikation. Um z.B. nicht von
einer Gruppe n Antworten zu erhalten, haben VBS üblicherweise spezielle
Gruppenaufrufe der Form "group_receive" und "group_send". Ein wichtiges
Entwurfsziel ist auch die Atomarität aller Gruppenanfragen. Ebenso wichtig
sind die Reihenfolgegarantie, die Skalierbarkeit und das Ermöglichen von
überlappenden Gruppen.
Als Beispiel einer existierenden Gruppenkommunikation sei
das ISIS-System für VBS genannt. Bei dieser Programmsammlung wird v.a. Wert auf
die Synchronität gelegt, d.h., dass alle in die Gruppe eingehenden Nachrichten
im selben Moment alle Gruppenmitglieder erreichen sollen. Da dies einen
unrealistischen Idealfall darstellt, operiert ISIS allerdings nur mit einer
abgeschwächten Form der Synchronität.
Wie kooperieren Prozesse in VBS, wenn sie Betriebsmittel allokieren wollen?
Da Shared Memory fehlt, gibt es keine Semaphoren- oder Monitorregelung, sondern
nur Nachrichten. Dazu muss aber sichergestellt sein, dass so etwas wie
eine Art absolute Zeit im Netz existiert, damit u.a. die zeitliche Reihenfolge
von Allokationsanfragen eingehalten werden kann.
In Einprozessorsystemen ist eine eindeutige Zeitgebung keine grosse
Sache. Doch VBS benötigen besondere Methoden, um Ereignisse in zeitlicher
Reihenfolge ihrer Anfrage zu garantierten. Zwei Methoden seien hier
vorgestellt:
-
Logische Uhren: Logische Uhren müssen nicht mit der physikalischen
Zeit übereinstimmen, es muss aber sichergestellt sein, dass die
an einer Kommunikation beteiligten Prozesse von einer synchronen Basis
ausgehen. Z.B. darf nicht Folgendes passieren:
Prozess 2 sendet zur lokalen Zeit 60 -> Prozess 1 empfängt zur lokalen Zeit 56
Prozess 1 sendet zur lokalen Zeit 64 -> Prozess 0 empfängt zur lokalen Zeit 54
Lamport zeigte einen Algorithmus, der dieses Problem mit logischen Uhren löst:
Prozess 2 sendet zur lokalen Zeit 60 -> Prozess 1 empfängt mit log. Zeit 60+1
Prozess 1 sendet zur log. Zeit 69 -> Prozess 0 empfängt zur log. Zeit 96+1
-
Physikalische Uhren: In Real-Time-Anwendungen ist es z.T. nötig,
dass von einer absoluten Zeit ausgegangen werden kann. Eine solche
lässt sich über Zeit-Server realisieren, die eventuell über eine
Satellitenleitung die exakte Atomuhrzeit übermittelt bekommen. Dabei kann
der Zeit-Server passiv oder in Form eines Dämons auch aktiv sein.
Wie kann der wechselseitige Ausschuss in VBS erreicht werden? Wie der
exklusive Eintritt in kritische Bereiche? Möglichkeiten sind:
- Ein zentraler "Semaphore"-Server.
- Server reagieren auf Anforderungen mit niedrigstem Zeitstempel.
- Token Passing-Algorithmus
Die Atomarität, d.h. die Alles-oder-Nichts-Eigenschaft von Transaktionen,
können die Programmierung von VBS wesentlich erleichtern. Ihre Serialität stellt
sicher, dass sich ihre Ergebnisse nicht ändern, egal, ob mehrere Transaktionen
sequenziell oder parallel
ausgeführt werden. Die Permanenz schliesslich sichert das Ergebnis
auf einer sicheren, am besten gespiegelten Platte. Die Idee der Transaktionen
kommt noch aus der Zeit der Speicherbänder, als beliebige DB-Zustände
jederzeit durch Rückspulen der Speicherbänder reproduzierbar sein
mussten. Mögliche Primitive sind: BEGIN-TRANSACTION, END-TRANSACTION,
ABORT, READ und WRITE.
Implementierungsmöglichkeiten gibt es mehrere:
-
Bildung von Schattenblöcken: Jeder Prozess erhält einen
privaten Arbeitsbereich, in den hinein die Daten kopiert werden.
Änderungen werden nur an dieser Kopie vorgenommen.
-
Rollback-Offerte: Kann eine Transaktion nicht vollständig
abgearbeitet werden, lässt sich über eine Protokolldatei (Logbuch-Datei)
der vorherige Zustand der Datenbank "zurückspulen" bzw. ab einem
gespeicherten Checkpoint bis zum Transaktionsbeginn "vorspulen".
-
Zwei-Phasen-Commit-Protokoll: Erst nachdem alle Teiltransaktionen an den
Schattenblöcken erfolgreich abgeschlossen und die Ergebnisse im sicheren
Speicher sind (erste Phase), wird die physikalische Änderung der Daten in
der DB vorgenommen (zweite Phase). Bei Commit-NAKs wird über Rollback der
alte DB-Zustand herbeigeführt.
Damit sich mehrere Prozesse nicht gegenseitig in die Quere kommen, muss
die Nebenläufigkeit kontrolliert werden. Dies geschieht über:
-
Zwei-Phasen-Sperren: In der ersten Phase werden alle Locks gesetzt und in
der zweiten Phase alle Locks wieder gelöst - in umgekehrter Reihenfolge,
um Deadlocks zu verhindern.
-
Optimistische Nebenläufigkeit: Führt ohne Rücksicht auf
andere die Transaktion aus. Prüft im Anschluss, ob das Ergebnis
korrekt übernommen wurde oder von anderen manipuliert wurde. Bei
Manipulation Abbruch. Dazu sind Schattenblöcke nötig. Funktioniert
frei von Deadlocks, kann aber bei starker Auslastung den Transaktionen
das Leben schwer machen.
-
Zeitstempel: Die jeweils jüngste Modifikation wird in einer
Transaktion vermerkt. Trifft sie auf ältere Modifikation, bricht sie ab.
Auch hier werden Deadlocks verhindert.
Deadlocks sind wie im Einprozessormodell über vier Strategien behandelbar.
In verteilten Betriebssystemen lohnen sich v.a. die Deadlock-Erkennung und
die Deadlock-Vermeidung. Wichtig ist, dass das Transaktionssystem einen
gefahrlosen Abbruch von Prozessen gewährleistet.
-
Zentrale Erkennung: Ein Koordinator bekommt Informationen zugesendet und
verwaltet damit einen Betriebsmittel-Graphen. Schein-Deadlocks durch zeitliche
Differenzen lassen sich über die Lamport-Ordnung verhindern.
-
Verteilte Erkennung: Jeder Prozess, der auf eine Ressource zugreifen
will, sendet eine Untersuchungsnachricht aus.
-
Verteilte Vermeidung: Ältere Prozesse haben Vorfahrt bei den
Ressourcen. Die jüngeren Transaktionen werden abgebrochen, können
dann aber mit altem Zeitstempel fortfahren.
Threads verhalten sich zu Prozessen, wie Prozesse zum Prozessor. Die Threads
eines Prozesses besitzen den gleichen Adressraum, wodurch sich globale
Variablen wie Semaphore realisieren lassen. Daneben verfügt jeder Thread
aber auch über einen eigenen Stack, Programmzähler, Registersatz und
Zeiger auf Kinder-Threads. Vorteil: Ein Prozess muss selten
völlig blockieren, sondern nur seine Threads, wodurch sich der Durchsatz
erhöhen kann. Trotz sequenzieller Thread-Programmierung werden so parallele
Verarbeitungen möglich! Sinn voll ist dies z.B. für Datei-Server, die
einen Verteiler-Thread einrichten können, der auf Anfragen wartet,
während andere Threads die eigentliche Arbeit erledigen.
Thread-Pakete sind Primitive, die dem Benutzer zur
Verfügung stehen, um Threads zu verwalten. Über sie kann z.B. auch das
prozessinterne Shared Memory durch binäre Mutex-Semaphore den Threads
zugeteilt werden. Implementiert werden können Threads im:
-
Benutzeradressraum: Vorteil: Threads werden vom BS nicht wahrgenommen.
-
BS-Adressraum: Vorteil: Blockierende Systemcalls legen nicht den
ganzen Prozess lahm.
Auch im Zusammenhang mit RPCs sind Thread-Pakete eine gelungene Erweiterung,
erlauben sie doch die Unterbrechung einzelner Threads ohne Verlust wichtiger
Programmvariablen (im Gegensatz zu schwergewichtigen Prozessen). Ein
Pop-Up-Thread z.B. erzeugt nach einem RPC einen Kind-Thread, dessen Stack
einfach auf die Nachricht setzbar ist, d.h., die Daten müssen nicht erst in
den Adressraum des Prozesses kopiert werden.
Die OSF (Open System Foundation) bietet z.B. DCE-Threads (Distributed
Computing Environment) für VBS, die gestatten, dass pro Prozess
ein beliebig wählbarer Algorithmus das interne Thread-Scheduling
übernimmt.
Man unterscheidet zwei System-Model-Präsentationen:
-
Lokale Präsentation von Ressourcen und Prozessoren: Über ein LAN
werden Workstations verbunden, die über eigene Betriebsmittel
verfügen. Primitive helfen, nicht ausgelastete Prozessoren zu finden und dort
remote Operationen auszuführen. Im Idealfall melden sich nicht ausgelastete
Prozessoren selbst, sodass diese nicht explizit angesprochen werden müssen.
-
Globale Präsentation von Ressourcen und Prozessoren: Zentral oder
verteilt implementierte Ressourcen-Pools gestatten über vorgeschaltete
Warteschlangen eine dynamische Zuordnung entsprechend der Anfragen der
Terminals.
Unterschieden werden müssen bei der Prozessorzuteilung migrierende und
nicht-migrierende Modelle. Nur die erste Variante gestattet einen
Prozessorwechsel eines Prozesses zur Laufzeit.
Entwurfskriterien bei Zuteilungsalgorithmen sind:
- Deterministisch bzw. heuristisch (Last nicht vorhersagbar)?
- Zentral bzw. verteilt?
- Optimal bzw. suboptimal?
- Lokale Entscheidung bzw. globale Entscheidung möglich?
- Sender initiiert (sucht) bzw. Empfänger initiiert (sagt, dass er frei ist)?
Als Beispiel sei der Aktionsalgorithmus genannt: Jeder Prozess
muss hier Leistung von einem Prozessor kaufen, wobei er sich nach einem
günstigen Angebot umsieht. Je mehr Rechenkapazität ein Prozessor frei
hat, umso teurer ist er. Ein ungelöstes Problem hierbei ist aber noch,
mit was eigentlich ein Prozess den Prozessor bezahlen soll.
Das Scheduling wird i.d.R. von jedem Prozessor nur für sich
ausgeführt, was aber bei starker Kommunikation nicht unbedingt der beste
Weg ist. Das Coscheduling von J. K. Ousterhout (1982) sucht daher über eine
Zeitscheiben-Matrix über alle Prozesse ein globales Scheduling zu
erreichen, indem es sicherstellt, dass kommunizierende Prozesse stets
gleichzeitig aktiv sind.
In verteilten Dateisystemen (VDS) bieten verschiedene Dateiserver in
transparenter Weise Dateidienste an. Im Idealfall verhält sich ein VDS
wie ein Einprozessor-Dateisystem, allerdings können VDS u.U. mehrere
Dateisysteme gleichzeitig anbieten, z.B. die von MS-DOS und UNIX.
Zwei Schichten gibt es bei VDS: Die Datei-Schicht und die Verzeichnis-Schicht.
Dateidienste der Dateischicht können nur auf ganze Dateien zugreifen
(Auflademodell bzw. Ablademodell; es wird mit Kopien gearbeitet) oder
aber sie können SEEK-Operationen durchführen (RACCESS-Modell).
Bei der Verzeichnis-Schicht muss man sich überlegen, ob die
Verzeichnisse für alle gleich aussehen sollen oder ob ein individuelles
Mounten zu bevorzugen ist. Um Ortstransparenz zu erreichen, können
Dateiserver benutzt werden (im Pfad steht zwar "/Server1/...", dies sagt aber
nichts über den Ort aus, da der Server beliebig wechseln kann) -
Ortsunabhängigkeit ist dadurch aber nicht gegeben (ein beliebiges
Verschieben der Dateien ist nicht möglich). Durch symbolische
Namen wie "prog.c", die vom VBS in Dateiserver-Adressen umgerechnet werden,
lässt sich auch Ortsunabhängigkeit erreichen.
Mit Shared Dateien muss gesondert umgegangen werden:
- UNIX-Semantik: Jedes Write ist für jedes Read sofort lesbar.
- Sitzungssemantik: Schreibaktionen sind erst nach Close lesbar.
- Unveränderliche Dateien: Modifikationen gehen mit neuen Dateien einher.
- Transaktionssemantik: Protokolle regeln den konkurrierenden Zugriff.
Vor der Implementierung von VDS sollte man wissen, für was und in welchem Masse
das VDS benutzt wird. Wichtig ist z.B.:
- Die meisten Dateien sind kleiner als 10 kB gross.
- Es wird mehr gelesen, als geschrieben.
- Es wird mehr sequenziell, als wahlfrei zugegriffen.
- Pro Prozess werden im Schnitt zwei Dateien benötigt.
Daraus lässt sich erlesen, dass Dateien besser stets komplett als
nur in Blöcken übertragen werden sollten, dass ein Caching sinnvoll ist,
dass der Client temporäre Kopie-Dateien anlegen sollte, usw.
Man muss wählen zwischen zustandslosen Servern mit hoher
Fehlertoleranz oder zustandsbehafteten Servern, die ein exklusives Sperren
erlauben. Statt das Caching auf der Serverplatte durchzuführen, kann es
auch im Hauptspeicher abgewickelt werden, wodurch v.a. die Plattensuchzeit
entfällt. Bei Verwendung von Client-Caching kann die Inkonsistenzgefahr
durch ein Write-Through-Caching vermindert werden.
Replikative Daten können folgendermassen aktuell gehalten werden:
- Replikation erster Kopie: Nur die Hauptserver-Daten sind änderbar.
- Voting: Erst nach Erlaubniseinholung sind Daten änderbar. Vorteil: robuster.
Die Hardware wird immer billiger. Dies wird zu einer Revolution in der
Organisation der Dateiserver führen, da früher oder später die
Platten wegfallen und sich alles im Hauptspeicher abspielt. Dies geht auch mit
einer Vereinfachung der Strukturen einher, so fällt z.B. das
Datei-Splitting flach. Die Sicherheit könnte durch kontinuierliche
Bandaufzeichnungen oder optischen Platten gewährleistet werden.
Damit verteilte Dateisysteme für grosse Anwendermengen nutzbar sind, ist ein Verzicht
auf alle zentralen Algorithmen unvermeidlich. Ein Cluster-Konzept ist hier der
richtige Weg, um die Skalierbarkeit zu gewährleisten.
Neben optischen beschreibbaren Platten sind auch WANs im Kommen. Verteilte Dateisysteme
müssen hier mit kleinen Bandbreiten (bei Telefonkabeln z.B. nur 64 kB)
und viel Heterogenität zurechtkommen. Im Gegensatz zu Lichtwellenleiter-LANs
wird hier auch ein Caching wieder nötig werden.
Das derzeit schnellst wachsende Marktsegment sind mobile Computersysteme.
Ein Caching ist hier kaum zu vermeiden, doch Online-Betrieb findet dort sehr
selten statt, was die Inkonsistenzgefahr erhöht.
Die heutigen Rechner sind eindeutig noch nicht fehlertolerant genug,
um für VDS bzw. VBS geeignet zu sein. Nur über Replikationsstrategien
können bis auf Weiteres Ausfälle vom VBS sinnvoll verarbeitet werden.
Der erste Prototyp von Amoeba wurde 1983 von Andrew Tanenbaum und Doktoranden
entwickelt. Amoeba basiert auf keinem existierenden System, erlaubt aber die
Emulation von UNIX. "Homecomputer" gibt es nicht, nur Terminals, die Prozessoren
aus zentralen Pools allokieren können. Welche Prozessor-Architektur gewählt wird,
hängt vom Auftrag ab. Die Wahl geschieht dabei völlig transparent für den Benutzer.
Neben normalen Servern verfügt Amoeba auch noch über:
- Bullet Server: Dateien bleiben konstant (bis auf Löschung).
- Verzeichnis-Server: Capabilities-Verteiler.
- Replikationsserver
- Bootserver für Fehlertoleranzsteigerung.
- TCP/IP-Server
- Server-Server: Trifft Entscheidung über Prozessorarchitektur.
Objekte können nur nach Vergabe von Capabilities erzeugt/benutzt
werden. Sie enthalten die Rechte, die auf ein Objekt zur Verfügung stehen.
Prozesse werden über spezielle Prozessdeskriptoren verwaltet, die
neben Stackzeigern, Segmentzeigern (Text, Daten, Stack, Heap und Shared Memory)
und Threadzeigern auch ein Feld für die verwendete Prozessorarchitektur
enthalten. RPCs und Gruppenkommunikation werden über FLIP (Fast Local
Internet Protocol) erreicht.
Mach von OSF und DARPA war zunächst ein monolithisches System,
dass später jedoch zu einem Mikrokern-System wurde. Wie Amoeba
besitzt es Threads, Capabilities und UNIX ist sogar als normaler
Anwenderprozess laufbar. Im Gegensatz zu Amoeba besitzt Mach im Kern viel
Funktionalität, es hat keine Prozessorpools, kommuniziert
hauptsächlich über lokalen Speicher statt über Netzwerke.
Verwendet Mach doch einmal das Netzwerk, so dient ihm das Internet Protocol
zur Kommunikation.