Betriebssysteme

Geschwurbel von Daniel Schwamm (10.05.1994 bis 23.05.1994)

Inhalt

1. Traditionelle Betriebssysteme

1.1. Einführung

1.1.1. Was ist ein Betriebssystem?

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:

  1. 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.
  2. 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.

1.1.2. Geschichte

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.

1.1.3. Betriebssystem-Konzepte und -Strukturen

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.

1.2. Prozesse

1.2.1. Einführung

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.

1.2.2. Interprozesskommunikation

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:

  1. Sperren aller Interrupts. Nachteil: verschwenderisch.
  2. 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.
  3. Striktes Alternieren: Ein Prozess prüft aktiv ein Shared Flag, bis es eine spezielle Nummer angenommen hat, die nur für diesen Prozess gilt.
  4. 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.

  5. 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).
  6. 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);
    };
    
  7. 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.

  8. 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.
  9. 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.

1.2.3. Weitere klassische Kommunikationsprobleme

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.

1.2.4. Prozess-Scheduling

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:

  1. Round-Robin-Scheduling: Das bedeutet Queue-Abarbeitung, wobei jeder Prozess ein festes Zeitquantum zugewiesen bekommt. Dies stellt die üblichste Form des Scheduling dar.
  2. 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.
  3. 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.
  4. 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.
  5. 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).
  6. 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.
  7. Zweistufiges Scheduling: Prozesse, die im Hauptspeicher liegen, werden bei der CPU-Vergabe bevorzugt gegenüber Prozessen, die im Hintergrund ablaufen.

1.3. Speicherverwaltung

1.3.1. Speicherverwaltung ohne Swapping und Paging

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.

1.3.2. Speicherverwaltung mit Swapping

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:

  1. 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.
  2. 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).
  3. 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.

1.3.3. Speicherverwaltung mit Paging

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:

  1. Seitentabelle komplett in Registern: zu teuer.
  2. Seitentabelle komplett im Speicher: Ein CPU-Register zeigt dabei auf die jeweils aktuelle Seite.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
1.3.3.1. Seitenersetzungsalgorithmen

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:

  1. 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.
  2. FIFO-Seitenersetzung (First in, first out): Bei dieser Methode wird die jeweils älteste Seite ersetzt.
  3. 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.
  4. 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.
  5. 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.
1.3.3.2. Bemerkungen über die Seitenersetzungsalgorithmen

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.

1.3.3.3. Seitengrösse

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)
1.3.3.4. Implementierungsprobleme

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.

1.3.4. Segmentierung

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!

1.4. Dateisysteme

1.4.1. Dateien

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.

1.4.2. Verzeichnisse

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.

1.4.3. Dateisystem-Implementierung

Die Blöcke auf der Platte werden vom Dateisystem (DS) nach verschiedenen Methoden verwaltet:

  1. Kontinuierliche Allokation: Nachteil: Fragmentierung
  2. Allokation mittels verknüpfter Listen: Nachteil: Zeiger braucht Platz
  3. Allokation mittels Indizes (MSDOS): Nachteil: Index ist komplett im Speicher zu halten.
  4. 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.

1.4.3.1. Caching

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.

1.4.4. Sicherheit

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.
1.4.4.1. Schutzmechanismen

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:
    1. C-Liste vollständig im BS-Adressraum halten (z.B. in Hydra realisiert).
    2. Capabilities verschlüsseln, v.a. in VBS wie Amoeba angewandt.
    3. 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.

1.5. Input-/Output-System

1.5.1. Eigenschaften der I/O-HW

Ü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.

1.5.2. Eigenschaften der Input-/Output-Software

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:

  1. 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.
  2. 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.
  3. 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, ...
  4. 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.

1.5.3. Festplatten

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.

1.5.4. Uhren

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.

1.5.5. Terminals

Es gibt zwei Arten von Terminals:

  1. 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.
  2. 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.

1.6. Deadlocks

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.

1.7. Ein Beispiel - UNIX

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.

1.8. Ein Beispiel - MS-DOS

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.

2. VERTEILTE BETRIEBSSYSTEME

2.1. Einführung

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.

2.1.1. Software-Konzepte

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.

2.2. Kommunikation in verteilten Systemen

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.

2.2.1. Schichtprotokolle

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.

2.2.2. Client-/Server-Modell

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")

2.2.3. Entfernter Unterprogrammmechanismus

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:

  1. 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.
  2. Anfragen gehen verloren: Timeout-Schranken lösen das Problem. Erfolgt nach Ablauf einer gewissen Zeit keine Antwort, wird die Anfrage wiederholt.
  3. Quittungen gehen verloren: Timeouts und Sequenznummern gegen Duplikat-Annahmen (weil nicht alle Unterprogramme idempotent sind) lösen das Problem.
  4. 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.
  5. 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.

2.2.4. Gruppenkommunikation

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.

2.3. Synchronisation in verteilten Systemen

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.

2.3.1. Uhren-Synchronisation

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:

  1. 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
    
  2. 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.

2.3.2. Wechselseitiger Ausschuss

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

2.3.3. Transaktionen

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.

2.3.4. Deadlocks in verteilten Systemen

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.

2.4. Prozesse und Prozessoren in verteilten Systemen

2.4.1. Threads

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.

2.4.2. System-Modelle

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.

2.4.3. Prozessorzuteilung und Scheduling

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.

2.5. Verteilte Dateisysteme

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.

2.5.1. Entwurf von verteilten Dateisystemen

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.

2.5.2. Implementierung von verteilten Dateisystemen

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.

2.5.3. Trends im Bereich von verteilten Dateisystemen

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.

2.6. Ein Beispiel - Amoeba

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.

2.7. Ein Beispiel - Mach

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.