Einführung in Betriebssysteme


von Prof. Jürgen Plate

4 Peripherieverwaltung

Die Peripheriegeräte gehören zusammen mit dem Prozessor und dem Hauptspeicher zu den elementaren Hardwarekornponenten einer Rechenanlage. Entsprechend ihrer Funktion können sie in drei Gruppen unterteilt werden:

4.1 Dateien

Zur Erinnerung: Dateien speichern eine Menge von gleichartigen Objekten (z. B. Bytes) unter einem Namen. Das BS stellt Operationen zum Bearbeiten von Dateien zur Verfügung: Alle Betriebssysteme zielen auf Geräteunabhängigkeit ab, d. h. ein Programm muß sich nicht (oder zumindest nur wenig) darum kümmern, ob eine Datei sich auf Platte, Magnetband oder einem anderen Massenspeicher befindet. Weiterhin sollen Ein- und Ausgabe auf einem Peripheriegerät prinzipiell genauso erfolgen, wie die Lese- und Schreiboperationen auf einer Datei. Auch Ressourcen auf einem Server sollen zugreifbar sein wie lokale Ressourcen. Bei vielen BS ist es möglich, auf einen beliebigen Datensatz innerhalb einer Datei zuzugreifen (wahlfreier Zugriff). Bei anderen Systemen ist nur sequentielles Lesen möglich.

Bei einigen BS wird zwischen verschiedenen Speichergeräten unterschieden (z. B. MS-DOS), der Benutzer muß genau spezifizieren, auf welchem Gerät (Laufwerk) sich die gewünschte Datei befindet. Bei anderen BS (z. B. UNIX) kann jedes Gerät in das Dateisystem eingebunden werden, das sich um die, auf diesem Gerät befindlichen, Dateien erweitert.

Ein Sektor ist auch die kleinste Informationsmenge, die von der Platte gelesen oder darauf geschrieben werden kann. In der Regel nimmt eine Datei mehrere Sektoren (typische Größen: 512 Byte - 8 KByte) in Anspruch. Das BS sorgt dabei:

Für die "Buchführung" über freie und belegte Sektoren gibt es verschiedene Methoden. Am gebräuchlichsten sind:

Zusätzlich werden Informationen über die Datei selbst benötigt, z. B.:

4.2 Verzeichnisse (Kataloge, Ordner, Directories, Folder)

Bei frühen BS bestand das Dateisystem lediglich aus einem Verzeichnis, das alle oben aufgeführten Informationen zu jeder der Dateien in einer Liste zusammengefasst hat. Über dieses Verzeichnis kann dann gezielt auf eine bestimmte Datei zugegriffen werden.

Ein erster Schritt der Verbesserung war die Unterteilung in Benutzerbereiche auf der Platte (z. B. bei CP/M) oder ein Verzeichnis für jeden Benutzer. Für Benutzer mit vielen Dateien war diese Lösung jedoch immer noch unbefriedigend, da eine logische Strukturierung der Dateien unmöglich war. Erst eine allgemeine Hierarchie von Katalogen (z. B. als Baum) bot die gewünschte Strukturierungsmöglichkeit (UNIX, MS-DOS).

Ist ein Dateisystem als Baum organisiert, benötigt man eine Methode, den Dateinamen zu spezifizieren:

Zum Beispiel:

absoluter Pfadname:/meier/projekt/daten/dat1
working directory:/meier/projet
relativer Pfadname:daten/dat1

System mit nur einem Verzeichnis: z. B. CP/M

Das Verzeichnis besteht aus einer Tabelle mit Einträgen fester Länge:

Die Datei ist in Blöcken auf der Platte gespeichert, wobei der letzte Block nicht vollständig gefüllt sein muß. Das Feld "Extend" wird benötigt, wenn die Länge der Datei 16 Blöcke überschreitet. In diesem Fall wird ein zweiter Eintrag angelegt, und "Extend" hochgezählt. Das Verzeichnis hat eine feste Größe.

Hierarchisches System: z. B. MS-DOS

Hier enthält das Verzeichnis nur die erste Blocknummer der Datei, die als Index für die FAT (File Allocation Table) dient und so die Bestimmung der weiteren Blocknummern gestattet. Das Root-Verzeichnis hat eine feste Größe; die Unterverzeichnisse sind Dateien, die beliebige viele Einträge aufnehmen können.

Bevor man die Festplatte benutzen kann, muß man die Festplatte partitionieren und ein Dateisystem einrichten, damit das Betriebssystem darauf Daten ablegen kann. Das FAT-Dateisystem besteht im wesentlichen aus zwei Teilen:

Die FAT führt Buch über die freien und belegten Plattenblöcke.

Mit der Entwicklung von Windows 95 sah sich auch Microsoft genötigt, das betagte FAT-Dateisystem durch einen leistungsfähigeren Nachfolger zu ersetzen. Das Ergebnis heißt VFAT oder FAT32 (Virtual-FAT).VFAT unterstützt bis zu 255 Zeichen lange Dateinamen. Sogar unter DOS behalten diese ihre Gültigkeit in Form einer Ersatzdarstellung mit 8+3 Zeichen. Ferner besitzt die VFAT eine Pseudo-Unterscheidung zwischen Gross- und Kleinschreibung, konvertiert aber alle im 8+3-Format vorliegenden Dateinamen in große Buchstaben um.

Hierarchisches System: z. B. UNIX

Bei UNIX ist die Verzeichnisstruktur sehr einfach. Jeder Eintrag besteht nur aus dem Dateinamen und einer Nummer. Der Dateiname war anfangs auf 14 Zeichen begrenzt, kann aber heute bei den meisten Systemen sehr viel länger sein. Die Nummer verweist auf den sogenannten i-node, der alle weiteren Informationen zur Datei enthält. Die Verzeichnisse sind Dateien. Alle i-nodes haben einen festen Platz auf der Platte.

Zusätzlich zu den Dateiverweisen muß bei den hierarchischen Dateisystemen in Unterverzeichnissen (außer Root) noch mindestens ein Verweis auf das übergeordnete Verzeichnis enthalten sein, da sonst ein "Navigieren" in den Verzeichnissen nicht möglich ist (in der Regel ".."). In der Regel existiert noch ein weiterer Verweis auf das Verzeichnis selbst (in der Regel".").

Im Gegensatz zu CP/M oder MS-DOS, bei dem die einzelnen Plattenlaufwerke durch einen Buchstaben, gefolgt von einem Doppelpunkt, gekennzeichnet werden, sind bei UNIX die Platten in das Dateisystem eingebunden und können an ein beliebiges Unterverzeichnis gekoppelt werden.

Hierarchisches System: z. B. NTFS

"NTFS" ist eine Abkürzung für "New Technology File System". Es handelt sich um ein Dateisystem mit neuerer Technologie, das mit WINDOWS NT eingeführt wurde. Dieses Dateisystem unterstützt lange Dateinamen, erweiterte Dateiattribute und sehr große Speicherkapazitäten (bis zu 2 hoch 64 Bit, also ca. 17 Milliarden GByte). Dateinamen werden im Unicode, einem 16 Bit-Zeichensatz, gespeichert das heisst gute Austauschbarkeit zwischen Systemen. NTFS löst Probleme, die mit dem FAT-Dateisystem (DOS/Windows) bestanden Dateinamen können wie bei VFAT bis zu 255 Zeichen lang sein und es gibt raktisch keine Beschränkung im Hinblick auf die Größe einer Datei, eines Verzeichnisses oder einer Festplatte. Außerdem ist die Clustergröße auf großen Platten frei wählbar und es entfällt der FAT-typische Verschnitt bei großen Festplatten. Alle Dateien und Verzeichnisse sind in den Zugriffskontrollmechanismus von Windows NT eingebunden. Die Zugriffsoperationen (Lesen, Schreiben, Löschen ) können separat für beliebige Benutzer oder Gruppen erlaubt bzw. verboten werden. Damit haben nur bestimmte Personen Zugriff auf vorher vom Systemadministrator festgelegte Dateien. Bei der Entwicklung von Windows NT und NTFS wurde besonders auf die Sicherheit gegen Datenverlust geachtet. NTFS arbeitet bei Metadaten (z. B. Verzeichnisse) transaktionsorientiert. So werden unvollständige Änderungen nach einem Systemausfall entweder vervollständigt oder rückgängig gemacht.

Die wichtigste Komponente von NTFS ist die MFT (Master File Tabelle). Jede Datei wird durch einen Eintrag in der MFT repräsentiert, denn auch die MFT ist eine Datei. Die ersten 16 Einträge dieser Tabelle sind reserviert.

Ab dem 17. Eintrag beziehen sich alle Einträge auf die einzelnen Dateien und Verzeichnisse des Datenträgers. Jedem Dateieintrag wird eine bestimmte Menge an Speicherplatz zur Verfügung gestellt, in den die Attribute der Datei geschrieben werden. Kleine Dateien bzw. Verzeichniseinträge können vollständig vom MFT-Eintrag aufgenommen werden.

Größere Verzeichniseinträge werden in Form von B-Trees organisiert, deren Einträge Zeiger auf externe Cluster enthalten, welche die Verzeichniseinträge aufnehmen. Jeder Datei bzw. jedem Verzeichnis ist ein Satz von Attributen (Dateiname, Daten, Sicherheits-ID) zugeordnet.

Einige Typen von NTFS Dateiattributen

StandardinformationZeitpunkt der letzten Speicherung usw.
AttributlisteListe aller weiteren Attribute (nur für grosse Datei)
Dateinamelanger Dateiname bis zu 255 Unicode-Zeichen, kurzer Dateiname 8+3 Zeichen (MS-DOS),
zusätzliche Namen als weitere Dateinamensattribute möglich (Hard Links von POSIX gefordert)
SicherheitsdeskriptorInformationen über Eigentümer der Datei, über Benutzer die auf diese Datei Zugriff haben usw.
Dateneigentlichen Daten der Datei
Index-Wurzelbei der Implementierung von Verzeichnissen notwendig
Index-Zuordnungbei der Implementierung von Verzeichnissen notwendig
Datenträgerinfowird nur bei der Systemdatei des Datenträgers verwendet und enthält u.a. die Version und den Namen des Datenträgers
Bitmustereine Karte der in der MFT oder im Verzeichnis belegten Einträge

Aufbau eines MFT Eintrages

 FATNTFS
Dateiname8+3 ASCII-Zeichen, durch einen Punkt getrennt255 Unicode-Zeichen;mehrere Punkte sind alsTrennzeichen zulässig
Dateigrösse232 Bytes264 Bytes
Partition232 Bytes264 Bytes
max. Länge des Suchweges64Unbegrenzt
Attributeeinige BitflagsAlles, inklusive der Daten, wird als Dateiattribut behandelt
VerzeichnisseunsortiertB-Tree
KonzepteinfachSchnell, mit Datenwiederherstellung / Sicherheit
eingebaute SicherheitNeinJa

NTFS unterstützt Hot-Fixing: Bei fehlerhaften Sektoren werden die Daten in einen anderen Sektor verschoben und der defekte Sektor wird in die Karte der fehlerhaften Sektoren eingetragen die allen Anwendungen mit Schreib- und Leserechten zugänglich ist.

Jede E/A-Operation, die eine Datei auf einem NTFS-Datenträger verändert, wird als Transaktion betrachtet und kann als geschlossene Einheit verwaltet werden. In der Protokolldatei werden alle Infos zum Wiederholen bzw. Rückgängigmachen der Transaktion gespeichert --> hoher Aufwand für die Protokollierung.

4.3 Gemeinsam genutzte Dateien

Wenn mehrere Benutzer die gleiche Datei verwenden wollen, kann es nützlich sein, wenn jeder Benutzer die Datei aus einem seiner Kataloge ansprechen (ohne den absoluten Pfad zu verwenden) und u. U. auch einen eigenen Namen für die Datei vergeben kann (bei Namenskonflikt mit eigenen Dateien).

Es wird dann ein Verweis auf die Datei installiert, ein Link. Durch die Einführung von Links dürfen die durch die Datei belegten Plattenblöcke nicht im Katalog gespeichert werden, da sonst alle Katalogeinträge, die auf die Datei verweisen, bei jeder Änderung an der Datei aktualisiert werden müßten. Die Lösung kann auf zwei Arten erfolgen:

Probleme: Die erste Lösung kann in Mehrbenutzersystemen zu Inkonsistenzen führen. Angenommen Benutzer A ist Eigentümer einer Datei und gestattet Benutzer B, ein Link auf diese Datei zu setzen. Zu einem späteren Zeitpunkt wird der Benutzer A aus dem System gelöscht (und damit auch seine Dateien). Nun gibt es über das Link von B eine Datei, zu der es keinen Eigentümer mehr gibt.

Die zweite Lösung vermeidet solche Inkonsistenzen, erfordert beim Dateizugriff jedoch einen höheren Verwaltungsaufwand (aus der Link-Datei den Pfad lesen und erst damit die Datei eröffnen). ISt die Datei nicht mehr vorhanden, erfolgt eine Fehlermeldung.

4.4 Ein- und Ausgabegeräte

E/A-Geräte werden in der Regel in das Dateisystem eingebunden und aus Benutzersicht wie Dateien behandelt (die u. U. von "normalen" Dateien abweichende Eigenschaften haben). E/A-Geräte können grob in zwei Kategorien eingeteilt werden:

Einige Geräte lassen sich nicht definiert einordnen (z. B. Zeitgeber = Timer). Zur Ansteuerung der Geräte ist systemnahe und z. T. hardwareabhängige Software des BS notwendig. In der Regel erhält jedes Gerät einen fest vorgegebenen Namen, unter dem es dann wie eine Datei angesprochen werden kann. Je nach Typ können Geräte gemeinsam von allen Prozessen verwendet werden (z. B. Platte) oder sie sind exclusiv für einen Prozeß reserviert (z. B. Plotter). Die Software zur Ansteuerung von Geräten läßt sich in zwei Ebenen strukturieren:

Gerätesteuerung

Die Peripheriegerätesteuerung erfolgt auf der Hardware-Ebene über den Austausch von Statussignalen und Daten zwischen den angeschlossenen Geräten und dem Prozessor. Die Programme zur Steuerung von Peripheriegeräten werden Treiber (driver, handler) genannt. Die Komplexität der Steuerungsaufgaben ist weitgehend vom Geräteverhalten abhängig.
Alle drei Methoden des Signal- und Datenaustausches können zum Einsatz kommen (programmgesteuert, interruptgesteuert, DMA).

4.5 Gemeinsame Nutzung von Betriebsmitteln

Manche Betriebsmittel dürfen nicht gleichzeitig von mehreren Prozessen genutzt werden. Klassisches Beispiel ist hier der Drucker. Die Ausgaben mehrerer Prozesse würden vermischt. Abhilfe bietet hier die Nutzung des Druckers durch einen einzigen Prozeß, den Druckerspooler. Alle Prozesse übergeben ihre Ausgaben an diesen Prozeß, der die Druckaufträge in einer Warteschlange speichert und nacheinander abarbeitet.

Beim Wettbewerb mehrerer Prozesse um Betriebsmittel (Ressourcen), zu denen ja primär Speicher, Dateien und die (als Dateien eingebundenen)Geräte gehören, kann es zu sogenannten Verklemmungen (dead locks) kommen.
Eine Verklemmung tritt bei Anforderungen von Ressourcen durch mehrere Prozesse dann auf, wenn ohne drastische Aktionen des BS all diese Anforderungen niemals erfüllt werden können. Folge: Die Prozesse blockieren sich gegenseitig.

Beispiel aus dem täglichen Leben:

Das Problem wurde schon vor vielen Jahren behoben. Die Abbiegevorschriften wurden so geändert, daß die Autos voreinander abbiegen dürfen.

Die speisenden Philosophen

Dieses Beispiel stammt von Dijkstra und ist also Demonstrationsmodell für das Entstehens von Deadlocks gedacht. Es wird seither auch immer als Testproblem für neue Prozeß-Synchronisations-Algorithmen verwendet. Bei Tanenbaum essen die Philosophen Spaghetti und zwar immer mit zwei Gabeln.

Programm für einen Philosophen mit zwei Gabeln: 

#include "prototypes.h"
#define   N 5

void philosoph (int i)
  {  
  while (1)              # Endlosschleife
    { 
    denke();
    NimmGabel(links);
    NimmGabel(rechts);
    esse();
    LegeGabel(links);
    LegeGabel(rechts);
    }
  }
Unterstellt man, daß die Philosophen pseudoparallel, also in Zeitscheiben arbeiten, ist das Modell gleichzeitig auch als Modell für die Beschreibung kritischer Abschnitte (zeitkritischer Situationen) geeignet. Die Funktion NimmGabel(Seite), müßte logischerweise zuerst prüfen, ob die Gabel frei ist, und erst dann die Gabel aufnehmen. Der zeitkritische Charakter der Funktion NimmGabel(Seite) besteht darin, daß zwischen der Prüfung "Gabel frei" und der Ausführung NimmGabel(Seite)ein zeitkritischer Abschnitt besteht.

Beispiel: System mit Drucker und Magnetband, 2 Prozesse

Setzt man für "Drucker" und "Bandstation" zwei Datensätze einer Datenbankdatei, so führt auch diese Situation zur Verklemmung. Nahezu jede Situation, in der Prozesse Ressourcen exklusiv anfordern, kann zur Verklemmung führen. Jedes exklusive Betriebsmittel kann immer nur von einem Prozeß angefordert werden. Solange das Betriebsmittel nicht frei ist, verbleibt der Prozeß im Zustand "blockiert". Nicht jede Anforderung von exklusiven Ressourcen führt zur Verklemmung. Für das Auftreten einer Verklemmung müssen folgende Bedingungen erfüllt sein:

Im allgemeinen werden vier Strategien zur Behandlung von Verklemmungen verwendet:

Banker-Algorithmus: Eine Methode zur Vermeidung von Verklemmungen

Wie eine Bank niemals soviel Geld bereithält, daß alle Kreditrahmen der Kunden voll ausgeschöpft werden können, kann auch das BS die Ressourcen so verwalten, daß immer mindestens ein Prozeß voll befriedigt werden kann. Dazu muß bei jedem Prozeß ein Maximalwert für die anzufordernden BM existieren.

Beispiel: Der Rechner hat 10 Magnetbandstationen 

     Zustand 1            Zustand 2            Zustand 3 
 Prozess bel. Max.     Prozess bel. Max.     Prozess bel. Max. 
 -----------------     -----------------     ----------------- 
     A    0    6          A    1    6          A    1    6    
     B    0    5          B    1    5          B    2    5 
     C    0    4          C    2    4          C    2    4 
     D    0    7          D    4    7          D    4    7 
 -----------------     -----------------     ---------------- 
       sicher                sicher              unsicher 
       10 frei               2 frei              1 frei
Ein Zustand ist dann sicher, wenn das BS mindestens bei einem Prozeß seine Maximalforderung erfüllen kann (die anderen müssen u. U. warten).

Zustand 1 ist sicher, da jeder Prozeß befriedigt werden kann.

Zustand 2 ist sicher, da Prozeß C befriedigt werden kann.

Zustand 3 ist unsicher, da keiner der der Prozesse voll befriedigt werden kann.

Das Schema kann auf beliebig viele BM erweitert werden.

4.6 Dienstprogramme des Dateisystems

Auf der obersten BS-Ebene treten die Benutzer über eine Menge von Kommandos (= Programme) mit dem Rechner in Dialog. Die Benutzerschnittstelle muß dazu eigentlich nur eine Eingabe des Benutzers entgegennehmen (z. B. den Namen eines Programms) und diese Eingabe interpretieren --> Kommandointerpreter oder Shell. Auch bei BS mit geringem Befehlsumfang existieren üblicherweise Kommandos:

Diese Kommandos können entweder Teil des Kommandointerpreters sein (schnelle Ausführung) oder durch getrennte Programme ausgeführt werden, die auf der Platte gespeichert sind. Dabei stützt sich der Kommandointerpreter wieder auf elementare Operationen des BS.

Zum vorhergehenden Abschnitt Zum Inhaltsverzeichnis Zum nächsten Abschnitt

Copyright © FH München, FB 04, Prof. Jürgen Plate