Betriebssysteme: Stichwörter, Fakten und Statistiken

Geschwurbel von Daniel Schwamm (20.06.1994)

Inhalt

1. Einführung

Das Betriebssystem ist eine logische (HW-unabhängige) Schnittstelle, einer virtuelle Maschine, die zwischen HW (z.B. CPU) und SW (z.B. ein DBS) vermittelt.

Es gibt kein optimales BS für alle Anwendungen, da unter den Anwendungen konfliktionäre Ziele bestehen können, z.B. Sicherheit vs. Geschwindigkeit.

Die vierte Generation der BS geht aber dazu über, adaptiv zu sein und normierte Schnittstellen anzubieten.

Betriebsklassen:

  • Stapelbetrieb.
  • Dialogbetrieb.
  • Echtzeitbetrieb.

Hauptziel von BS: Betriebsmittel-Verwaltung (BM) -> Realisation über Strategien.

Die 6 UNIX-Schichten:

  • HW
  • Kern
  • Inneres BS
  • Äusseres BS
  • Systemprogramme
  • Applikationen

Benutzerschnittstelle zum BS: Kommandoschnittstelle (Shell).

Parameterlisten-Arten: Stichworte (Y VON = X NACH = Z), Position (Y X Z)

Betriebssystem-Funktionsaufrufe:

  • Direkter Aufruf (Einprogrammbetrieb)
  • Supervisor Call für spezielle BS-Routinen
  • normaler Prozedur-Aufruf

2. Prozesssystem

Prozess: BS-Verwaltungseinheit (im Gegensatz zum Programm dynamisch)

Prozesse können disjunkt oder parallel ablaufen.

Bei einem Speicher von n Bits sind 2^n Zustände möglich (=Zustandsraum).

Im Prozessleitblock finden sich Informationen über Prozess-Betriebsmittel, Prioritäten, Registerinhalte ... Der Prozessleitblock wird als Liste, Feld oder Mischform (Überlaufbereiche) implementiert.

Unterbrechungsstau: Wird verursacht von Interrupt-Routinen, die sich während ihrer Ausführung selbst unterbrechen (Rekursion).

Fehlerhandling: 50%-80% des BS-Codes dafür zuständig.

Mögliche Prozesszustände:

  • nicht definiert
  • inaktiv
  • bereit
  • rechnend
  • wartend
  • ausgelagert

-> Zustandsdiagramm erstellbar

Nullprozess: Dient der Verhinderung eines Prozessorleerlaufs; üblicherweise ein "jmp" auf der Stelle oder ein "hlt", welches auf einen Interrupt wartet.

Betriebsmittel-Operationen: Belegen eigen, Belegen fremd, Freigeben, zuweisen, entziehen. Realisierbar als Busy-Waiting-Prozeduren oder selbstständige Prozeduren.

Auftragsabwicklung: Eingabe -> Auftragsschlange -> Scheduler wählt einen von n Aufträgen aus -> Dispatcher teilt Prozessor zu -> n x Ende.

Zuteilungsstrategien:

  • Statische Priorität (Batch < Dialog < Systemprozeduren < Echtzeit < kritische Systemprozeduren)
  • Dynamische Priorität (Abgabe der Priorität bei E/A)
  • First In, First Out
  • Shortest Job First
  • Preemptive Shortest Job First -> Unterbrechung laufender Jobs möglich)
  • Round Robin

Die mittlere Verweildauer von Auftrag ist minimal bei Shortest Job First.

Ordungsrelation: Präzedenzrelationen (von parallelen Prozessen): A1 < B2 => Teilprozess A1 wird vor Teilprozess B2 ausgeführt. Verschärft: Direkte Präzedenz: A1 << B2 => es ex. kein d mit A1 < d < B2.

Paralleler Ablauf-Darstellung:

  • Graph (Kanten=direkte Präzedenzen, Knoten=Teilaufträge, Kantenbeschriftung=Zeitbedarf)
  • Gantt-Diagramme (Aufträge tabellarisch untereinander im Zeitablauf und CPU-Beanspruchung darstellen).

Wichtig! Bei Shortest Job First sind 4 Prozessoren nicht immer besser als 3 Prozeduren.

3. Kommunikationssynchronisation

Anweisungen sind atomar.

Kritischer Abschnitt: Programmteil, der Shared Resources nutzt.

Synchronisationsmethode des gegenseitigen Ausschusses: Eingangs- und Ausgangsprotokoll nötig, damit jeweils nur einer im kritischen Bereich sein kann. Realisation über P(S)- und V(S)-Semaphore. Bei P(S) wird S dekrementiert, man gelangt in kritischen Bereich bzw. legt sich Schlafen (S=0). Bei V(S) wird S inkrementiert und der nächste Prozess in der Queue wird geweckt.

Beispiel: 5-speisende-Philosophen-Problem und Erzeuger-Verbraucher-Problem. Lösung von n-Leser-m-Schreiber-Problemen.

Monitore: Werden mehrere Betriebsmittel geteilt, können ungünstige Semaphore-Schachtelungen zu Deadlocks führen. Monitore erledigen die Klammerung automatisch.

IPC: UNIX benutzt v.a. Pipes (Mailboxen).

Kanal: Ein adressierbares Kommunikationsobjekt, i.d.R. FIFO. Ist ein Kanal voll, wird der Sender blockiert, bis eine Quittung bzw. ein Timeout kommt.

In ADA haben Kanäle nur eine Kapazität von Null, also keinen Puffer. Daher müssen dort alle Prozesse über das Rendezvous-Konzept in Kontakt treten.

Port: Kanal, der an einen Prozess gebunden ist (1:1-Relation).

Treiber: Kombination von normalen Kanälen und Ports (m:1-Relation).

Die vier notwendigen Bedingungen für einen Deadlock:

  1. gegenseitiger Ausschluss (exklusiver Zugriff)
  2. Wartebedingung (Warten auf Betriebsmittel wie etwa Speicher)
  3. Nichtentziehbarkeit
  4. geschlossene Kette

Deadlock-Behandlung: Erkennen und beseitigen (svw.) oder vermeiden (avoidance; z.B. Betriebsmittel-Anforderungen in fester Reihenfolge).

Deadlock-Erkennungslogarithmus: Komplexität O(Prozessmenge^2 * Betriebsmittel); 

REPEAT
      wähle Prozess k aus Prozesshilfsindexmenge H;
      IF k bzgl. Betriebsmittel fortsetzbar THEN BEGIN
            Prozessindexmenge P=P\{k};
            Erhöhe Liste freier Betriebsmittel;
            H=P;
            IF P=0 THEN Deadlock:=FALSE;
      END
      ELSE BEGIN
            H=H\{k};
            IF H=0 THEN Deadlock:=TRUE;
      END;
UNTIL (P=0) ODER (H=0);

Petrinetze eigenen sich zur Darstellung asynchroner Ereignisse: Deadlocks lassen sich hiermit leicht feststellen, nämlich dann, wenn keine weiteren Zugangsänderungen möglich sind.

4. EA-/Geräte-Verwaltung

Das BS verbirgt die Geräte, die Programme kennen nur BS-Input-/Output-Funktionen. Nur der Gerätetreiber kennt die speziellen Eigenschaften eines Geräts. Die Steuerung des Treibers erfolgt über die CPU oder über Treiber-interne E/A-Prozessoren.

Bus: Verbindung zwischen Prozessor, Speicher, EA-Treibern. Sie arbeiten immer mit konstanter Geschwindigkeit, wodurch sie bei grossen Systemen zum Engpass werden. Daten, Adressen und Steuerangaben verlangen verschiedene Formate.

Kanal-Konzept: Treiber sind über Kanäle ansprechbar, wobei die Kanäle gemultiplext sein können (Multiplexing versus Selective-Kanalzuweisung).

Jedes Gerät ist ein exklusives Betriebsmittel (gehört nur einem Prozess). Welcher Prozess welches Gerät beanspruchen darf, steht im PCB (Process Control Block), der i.d.R. beim Systemastart initialisiert wird. Änderungen sind jederzeit möglich.

Treiber sind privilegierte (Supervisor) Prozesse der BS-Schale. Er setzt allgemeine EA-Aufträge in gerätespezifische Anweisungen um. Es gilt: Ein Treiber kann mehrere Geräte steuern, ein Gerät kann von mehreren Treibern gesteuert werden.

Bei den EA-Aufträgen kann man die folgenden Schritte unterscheiden: Auftragsverarbeitung <-> Geräteanstoss <-> Geräteanalyse <-> Auftragshandling.

Das Fehlerhandling ist auftragsspezifisch und gerätespezifisch!

5. Hauptspeicherverwaltung

Programme benutzten nur logische Adressen, die in physikalische umzurechnen sind. Dies wird realisiert durch: Gleichsetzung, durch relative Adressierung, einstufig streuende Adressierung, zweistufige streuende Adressierung.

Bei der relativen Adressierung beginnt die logische Adresse immer bei 0. Der Lader rechnet die physikalischen Adressen beim Einladen aus. Besser ist jedoch, ein spezielles Basisregister zu verwenden => Programme verschiebbar zu Laufzeiten!

Streuende Adressierung bedeutet, dass der logische Speicher in Seiten und der physikalische Speicher in Kacheln (Blöcke) unterteilt wird.

Seitentabellen helfen bei der einstufigen streuenden Speicherung, den Seiten Kacheln zuzuweisen und umgekehrt. Dies geschieht über das BS. Üblicherweise werden auch Assoziativspeicher als Cache für Seiten verwendet.

Seitentabellen verursachen Verschnitt. D.h., der letzte Block wird im Schnitt zur Hälfte nicht benutzt. Die Wahl der Seitenlänge ist daher zu optimieren.

Die optimale Seitenlänge ist die Wurzel von 2 Eintragslänge * Speicherlänge geteilt durch Mehrprogrammfaktor (Programmanzahl).

Bei der zweistufigen streuenden Adressierung wird der Speicher in Segmente und werden Segmente in Kacheln unterteilt. Dadurch wird der Verschnitt gemildert, aber es sind Grenzregister für die höchsten Adressen pro User nötig.

Die Segmenttabelle und die Seitentabelle verfügt über SLA-Bits (Save, Load, Activated). Durch sie wird ein effektiver Speicher-Zugriffsschutz gewährleistet.

Virtueller Speicher eignet sich für Swapping (Prozesse auf Sekundärspeicher laufen lassen), zur Overlay-Technik (bei Bedarf Programmteile nachladen), Paging (Seitentabelleneinsatz, wobei in einer Seite Operator und in jeweils anderer Seite der Operand steht => jedes Programm benötigt mindestens zwei Kacheln des Speichers).

Page Faults werden erzeugt, wenn eine Seite angefordert wird, die nicht im Speicher steht. Eine Interruptroutine (Paging-Treiber) besorgt die nötige Seite, sei es über Belegung einer freien Kachel oder einem Austauschprozess.

Austauschmethoden statischer Natur sind:

  • FIFO (Anomalien möglich, d.h. weniger Kacheln sind u.U. besser als viele)
  • optimale Methode (Zukunftsweisend nötig)
  • LRU (zu aufwendig)
  • FINUFO (First In, Not Used First Out, d.h. Referenzbit nötig)
  • RNU (Recently Not Used, d.h. Referenzbit plus Zeitzähler nötig).

Dynamische Verfahren erlauben es Programmen, während ihrer Laufzeit die Kachel-Anzahl (Working Set) zu ändern. Üblicherweise wird aber vor der Programmausführung die Kachelanzahl experimentell anhand der Page Faults ermittelt; danach wird mit RNU und FINUFO gearbeitet.

Im Multiuser-Betrieb können sich User Programmteile teilen, d.h. bestimmte Seiten sind shared Memory.

Die Speicherveraltung geschieht über eine der folgenden Methoden:

  • Blockverwaltung (First-Fit, Best-Fit, Next-Fit)
  • Halbierungsverfahren (2*c^k: c=1 => mehrere Blöcke der Grösse 1, 2, 4, 8, ... Bytes. Wenn 6 Bytes angefordert sind, wird ein 8 Byte-Block allokiert)
  • Vektorverfahren (Frei/Belegt-Array)
  • Kellerverfahren.

Die Speicherbereinigung (Garbage Collection) sorgt für eine Zweiteilung des Speichers in einen freien und einen belegten Block. Evtl. wird auf dem externen Speicher zwischengespeichert.

6. Dateiverwaltung

Datei: Kollektion von logisch zusammengehörenden Sätzen gleicher Struktur.

Dateiarten:

  • Ungeordnete Mengen
  • Random-Access-Kacheln
  • Sequenzen.

Datei-(System-)Anforderungen:

  • Portabilität (Datei mit logischer HW-unabhängiger Struktur)
  • Zugriffsschutz
  • Sicherungsschutz
  • flexibles Benennungssystem
  • Eingabe/Ausgabe-Reduzierung (Fahrstuhl-Plattenarm, Pufferung, Paging)

Dateiunterscheidungskriterien: Satzlänge (konstant/variable?), Satzstruktur (Bit-/Byte-/Komponentenfolge?), Zugriffsart (Hash?)

Der Dateikontrollblock enthält Infos über geöffnete Dateien, z.B. wo sich die EA-Puffer befinden.

Datenträger:

  • Band (Streamer)
  • Platte/Diskette (Blockzugriff; Volume Table Of Contents an fixer Adresse)

B-Bäume sind index-sequenzielle Organisationen: Wahlfrei im Baum, sequenziell in den Blättern. Suchen hat die Komplexität O(Höhe*Log Schlüsselordnung), wobei die Schlüsselordnung k bedeutet, dass minimal k+1 Schlüssel und maximal 2*k+1 in den Knoten sein müssen. Gleiche Schlüssel sind möglich. Grössere Inhalte werden in Extrablöcke geschrieben.

Einbettung der Dateiorganisation ins BS: Benutzer <-> Dateitreiber <-> Gerätetreiber <-> Datenträger.

Meist wird nur ein Dateitreiber für alle Benutzer verwendet. Bisweilen jedoch existieren auch für jede Organisationsform ein eigener Dateitreiber.

Systeminitialisierung: BS steht in Datei (Platte/Disk/Netz) -> im ROM BIOS-Treiber für Block 0, d.h., Block 0 enthält restlichen Treiber zum Laden des BS, und das wiederum heisst, eine bestimmte SW/HW-Konfiguration wird gestartet.

Die Konfiguration ist anpassbar über folgende Verfahren:

  • Statische (wie CONFIG.SYS)
  • Dynamische (Konfiguration im laufenden Betrieb änderbar)
  • Automatische (SW passt sich an HW an)

7. Datensicherung und Datenschutz

SW-Redundanz bringt nichts, es sei denn, es handelt sich um verschiedene Versionen eines Programms. Um sichere Ergebnisse zu erzielen kann nach der 2:3-Strategie vorgegangen werden: Die Mehrheit der Programmergebnisse hat recht.

Stützpunkte: Aufträge in Intervalle zerlegen (Transaktionsprinzip).

Zugriffsschutz: Physikalisch (benutzerspezifische Bereiche schaffen), logisch (IPC muss sich an Zugriffsmatrix halten).

Die Zugriffsmatrix Z=(zij) bedeutet, dass ein User i auf das Betriebsmittel j das Zugriffsrecht zij besitzt. Die Zeilen stellen Capability-Lists eines Users dar, die Spalten Access-Lists auf ein Betriebsmittel.

Zugriffsmatrizen benötigen viel Speicher. Weniger benötigen Zugangslisten (Prozess, Rechner) und Berechtigungslisten (Betriebsmittel, Recht).

Passwörter: Zur DÜ gibt es DES als Sicherungsverfahren. Dabei verschlüsselt ein 56 Bit-Schlüssel 64-Bit-Blöcke, wobei gilt: f(f(x))=x.

8. Verteilte Systeme

Ziele: Daten-, Funktionen-, Last-, Verfügbarkeitsverbund.

Netzklassen: Homogen, heterogen, offen.

Einbettung des OSI-Modells ins BS: Für jedes Protokoll i der Schicht i existiert ein Treiber i.

Struktur eines hierarchischen BS: Benutzerschnittstelle <-> BS-Teile (möglichst viel; z.B. Paging) <-> HW-Schnittstelle (Treiber, Kern, Interrupts) <-> HW.