Modul 6: Dateisysteme – Die Vogonen-Bürokratie der Festplatte

Willkommen in der intergalaktischen Aktenverwaltung. Wenn der Arbeitsspeicher (RAM) das Kurzzeitgedächtnis unseres Computers ist, dann sind Festplatten das Langzeitgedächtnis. Aber Festplatten kennen keine Dateien, keine Ordner und keine Zugriffsrechte. Viele Speichergeräte arbeiten schlichtweg blockweise[cite: 1]. Die Hardware bietet dem System lediglich eine riesige Menge von Blöcken an, die eindeutig adressierbar sind[cite: 1].

Eine Datei ist letztlich nur ein logisches Betriebsmittel, welches eine endliche Menge zusammengehöriger Daten beinhaltet[cite: 1]. Das Dateisystem (File System) ist der Teil des Betriebssystems, der die gigantische Übersetzungsarbeit leistet: Es mappt die für Menschen verständlichen, hierarchischen Dateinamen auf nackte Hardware-Blöcke[cite: 1]. Es erspart dem Benutzer das Hantieren mit lästigen Details, wie dem exakten Ausrichten eines Schreib-/Lesekopfes[cite: 1].

In der Unix/Linux-Welt gilt zudem das Paradigma: Everything is a file. Egal ob es sich um ein Textdokument, ein Verzeichnis (das wiederum nur eine spezielle Datei ist[cite: 1]), eine Netzwerk-Socket-Verbindung oder ein Block-Device wie /dev/sda handelt – das OS abstrahiert alles über Dateideskriptoren.

Bevor wir Daten strukturieren, müssen wir verstehen, wie wir sie physisch lesen. Da Platten um ein Vielfaches langsamer als der Arbeitsspeicher sind, erfolgt der Zugriff aus Effizienzgründen blockweise[cite: 1]. Bei mechanischen Festplatten (HDDs) besteht die Zugriffszeit aus der Seek Time (Kopfbewegung zur richtigen Spur) und der Rotational Latency (Warten, bis der richtige Sektor unter dem Kopf vorbeidreht).

Das Betriebssystem muss die anstehenden Lese- und Schreibanfragen (Requests) intelligent sortieren. Das Skript definiert hierzu mehrere klassische Scheduling-Algorithmen[cite: 1]:

• FCFS (First Come First Serve): Die Anfragen werden exakt in der Reihenfolge abgearbeitet, in der sie eintreffen[cite: 1]. Völlig ineffizient bei vielen verstreuten Zugriffen, da der Lesekopf wild hin und her springt.
• SSTF (Shortest Seek Time First): Der Sektor mit der kürzesten Suchzeit ausgehend von der aktuellen Kopfposition wird als Nächstes bedient[cite: 1]. Gefahr: „Aushungern“ (Starvation) von Anfragen am Rand der Platte.
• SCAN (Elevator-Algorithmus): Der Diskarm bewegt sich wie ein Fahrstuhl von einem Ende zum anderen und bearbeitet auf dem Weg alle Requests[cite: 1].
• C-SCAN (Circular SCAN): Der Diskarm fährt zum Ende, wird dann aber ohne Daten zu lesen sofort wieder auf den Anfang zurückgesetzt und arbeitet kreisförmig nur in eine Richtung[cite: 1].
• LOOK / C-LOOK: Eine Optimierung von SCAN/C-SCAN. Der Arm fährt nicht stur bis zum allerletzten physischen Zylinder, sondern nur so weit, wie der letzte reale Request es verlangt, und dreht dann um[cite: 1].

Bewertungskriterien in der Praxis: Die hohen Rotationsgeschwindigkeiten moderner Platten müssen zwingend berücksichtigt werden[cite: 1]. Ein guter Algorithmus legt Verzeichnisse und Indexblöcke in mittlere Zylinder, da dort die mittlere Zugriffszeit am kleinsten ist, weil sich der Lesekopf im Durchschnitt in der Mitte befindet[cite: 1]. Zudem muss das OS abwägen: Paging-Anfragen (Demand Paging für den RAM) sind oft kritischer als reguläre E/A-Anfragen von Anwendungen[cite: 1].

Ein leeres Dateisystem wird zunächst als lineares Medium betrachtet[cite: 1]. Wie speichert man nun eine Datei ab?

Die einfachste Form: Eine Datei belegt eine zusammenhängende (kontinuierliche) Anzahl von Blöcken[cite: 1]. * Vorteil: Extrem schneller sequenzieller Zugriff, da der Lesekopf nicht springen muss[cite: 1]. * Nachteil: Verheerende externe Fragmentierung bei Dateiänderungen[cite: 1]. Wenn eine Datei wächst, der nachfolgende Block aber belegt ist, muss die gesamte Datei kopiert werden. Extrem ineffizient[cite: 1].

Um externe Fragmentierung zu vermeiden, zerlegen wir Dateien in Blöcke und verketten sie. Die einfachste Form braucht sehr wenig Verwaltungsdaten, da jeder Block nur einen Pointer (Zeiger) auf den nächsten belegten Block enthält[cite: 1]. * Nachteil: Der wahlfreie Zugriff (Random Access) ist extrem langsam, da man immer am Anfang beginnen und sich durchhangeln muss[cite: 1].

Die Lösung ist eine File Allocation Table (FAT). Die Nutzdaten werden von den Zeigern getrennt und in eine zentrale Zuordnungstabelle ausgelagert[cite: 1]. Bei FAT liegt diese Tabelle auf den ersten Spuren der Platte[cite: 1]. Sie enthält für jeden Block einen Verweis auf den Folgeblock oder eine EOF-Markierung (End of File, in MS-DOS oft FFFF)[cite: 1]. Freie Blöcke erhalten eine 0, schadhafte Blöcke (Bad Sectors) z. B. FFF7[cite: 1]. * Vorteil: Schneller wahlfreier Zugriff, da die komplette Tabelle im RAM gehalten werden kann[cite: 1]. Alle Blöcke einer Platte sind über die FAT miteinander verkettet (abgesetzte verkettete Allokation)[cite: 1]. * Nachteil: FAT bietet historisch weder Schutzmechanismen noch lange Dateinamen[cite: 1].

Die indizierte Speicherung führt Indexblöcke ein, in die hintereinander die zur Datei gehörigen Blocknummern eingetragen werden[cite: 1]. Für jede Datei wird die Startadresse und die Indexlänge gemerkt[cite: 1]. So muss nicht die ganze Zuordnungstabelle durchsucht werden[cite: 1]. Wählt man den Indexblock aber zu groß, entsteht interne Fragmentierung; wählt man ihn zu klein, beschränkt das die maximale Dateigröße[cite: 1]. Dies führt uns zum Meisterstück der Unix-Architektur.

Wenn ihr ein Linux-Dateisystem (wie ext2, ext3 oder ext4) aufsetzt, erstellt das System neben den Datenblöcken eine feste Anzahl von INodes (Index Nodes)[cite: 1]. Jede Datei wird durch mindestens einen INode beschrieben[cite: 1].

Ein INode ist eine kleine Datenstruktur (oft 128 oder 256 Bytes), die keinen Dateinamen enthält, sondern ausschließlich Metadaten und Zeiger[cite: 1]. Laut Skript beinhaltet er[cite: 1]: * Dateityp (Regulär, Directory, Symlink)[cite: 1] * Eigentümer (UID) und Gruppe (GID)[cite: 1] * Zugriffsschutzbits (rwx)[cite: 1] * Datumseinträge (Erstellung, Modifikation, letzter Zugriff)[cite: 1] * Anzahl der Links (Hardlinks)[cite: 1] * Zeiger auf den eigentlichen Dateiinhalt[cite: 1]

Um riesige Dateien effizient zu adressieren, nutzt Unix die indirekt indizierte Speicherung[cite: 1]. Ein klassischer Inode (z. B. in ext2) hat exakt 13 Einträge (Zeiger) zur Adressierung von Datenblöcken[cite: 1].

* Zeiger 1 bis 10 (Direkte Blöcke): Zeigen direkt auf die ersten 10 Datenblöcke der Datei[cite: 1]. Dateien bis ca. 10 KByte (bei 1KB Blockgröße) können direkt referenziert werden, was das System extrem effizient für kleine Dateien macht[cite: 1]. * Zeiger 11 (Einfach indirekt): Zeigt auf einen Block, der keine Nutzerdaten, sondern weitere Plattenadressen (Zeiger auf Datenblöcke) enthält[cite: 1]. * Zeiger 12 (Doppelt indirekt): Zeigt auf einen Block, der Adressen von einfach indirekten Blöcken enthält, welche wiederum auf direkte Blöcke zeigen[cite: 1]. * Zeiger 13 (Dreifach indirekt): Zeigt auf einen Block mit Adressen von doppelt indirekten Blöcken[cite: 1].

Mathematischer Exkurs für Informatiker: Wie groß kann eine Datei maximal werden? Rechnen wir es aus! Gegeben sei eine Blockgröße $B = 4096 \text{ Bytes}$ (4 KB) und ein Zeiger benötigt $P = 4 \text{ Bytes}$. Ein indirekter Block kann also $N = \frac{4096}{4} = 1024$ Zeiger aufnehmen.

Die maximale Dateigröße $S_{max}$ berechnet sich wie folgt: $$ S_{max} = B \times ( 10 + N + N^2 + N^3 ) $$ $$ S_{max} = 4096 \times ( 10 + 1024 + 1024^2 + 1024^3 ) $$ $$ S_{max} \approx 4096 \times ( 1.074.791.434 ) \approx 4,004 \text{ Terabyte} $$ Dieses System wächst logarithmisch mit der Dateigröße und verhindert riesige Allokationstabellen im RAM.

Ein Verzeichnis (Katalog) ist unter Unix nichts anderes als eine Datei, die Dateinamen den dazugehörigen INode-Nummern zuordnet[cite: 1].

Beispielzugriff auf `/var/log/messages`:[cite: 1] 1. Der I-Node des Wurzelverzeichnisses („/“) steht an einer fest definierten Stelle der Festplatte[cite: 1]. 2. Der Kernel liest den Datenblock von „/“ und sucht darin den Namen „var“[cite: 1]. 3. Er findet den dazugehörigen I-Node für „var“ und liest dessen Datenblock[cite: 1]. 4. In der Verzeichnisdatei „var“ sucht er nach dem Eintrag „log“ und liest dessen I-Node[cite: 1]. 5. Über den I-Node von „log“ wird der Datenblock geladen und nach „messages“ gesucht[cite: 1]. 6. Der I-Node der Datei „messages“ wird gefunden und in die lokale Deskriptortabelle des Prozesses sowie die globale Dateideskriptortabelle geladen[cite: 1]. Dieser Deskriptor dient dem Prozess als Handle für Lese-/Schreibzugriffe[cite: 1]. Nach einem close() wird der I-Node wieder aus der Liste entfernt[cite: 1].

Die Festplatten-Partition selbst ist strukturiert. Das Skript zeigt den typischen Unix-Aufbau[cite: 1]: * Bootblock: Liegt im ersten Sektor und enthält den Bootstrap-Code, der beim Hochfahren das Betriebssystem initialisiert[cite: 1]. * Superblock: Beschreibt den Aufbau des Dateisystems[cite: 1]. Eine Kopie befindet sich permanent im RAM und wird periodisch zurückgeschrieben[cite: 1]. Er enthält kritische Metadaten[cite: 1]:

• Größe des Dateisystems[cite: 1].
• Anzahl und Liste der freien Blöcke und Inodes[cite: 1].
• Sperrkennzeichen und Flags für Änderungen[cite: 1].

* I-Node-Liste: Eine Tabelle aller Inodes[cite: 1]. * Datenblöcke: Die tatsächlichen Payload-Daten.

Microsoft geht mit dem New Technology File System (NTFS) einen anderen Weg. NTFS kennt keine festen Inode-Tabellen. Die zentrale Struktur ist die Master File Table (MFT) – sie stellt ein flaches Dateisystem dar, auf das über Verzeichnisse die bekannte Baumstruktur definiert wird[cite: 1]. Jede Datei und jedes Verzeichnis besitzt einen Datensatz in der MFT[cite: 1].

* Bei sehr kleinen Dateien (1 bis 4 KB) werden die Nutzdaten direkt innerhalb des MFT-Eintrags selbst gespeichert (resident attributes)[cite: 1]. * Bei großen Dateien enthält der MFT-Eintrag den Wurzelknoten eines B-Baums, dessen Blätter auf die Dateibereiche (Extents oder Lauffolgen) auf der Festplatte verweisen[cite: 1].

Dateien werden eindeutig über eine ID identifiziert, die sich aus der 48-Bit langen Satznummer in der MFT und einer 16-Bit Folgenummer (für Konsistenzüberprüfungen) zusammensetzt[cite: 1].

Zudem verwaltet NTFS spezielle Systemdateien (erkennbar an einem führenden '$')[cite: 1]: * MFT2: Ein Backup der ersten 16 Einträge der MFT[cite: 1]. * Logdatei: Enthält Transaktionsdaten, um das Dateisystem nach einem Ausfall rekonstruieren zu können (Journaling)[cite: 1]. * BadClusterDatei: Verweist auf defekte Sektoren[cite: 1]. * Cluster-Bitmap-Datei: Verfolgt belegte und freie Cluster[cite: 1].

Um von verschiedenen Verzeichnissen auf dieselbe Datei zuzugreifen, ohne sie zu kopieren, nutzen wir Links[cite: 1]. * Hardlinks: Das Verzeichnis verweist direkt auf die Inode-Datenstruktur der Datei[cite: 1]. Löscht Benutzer A (der Eigentümer) die Datei, existiert der Hardlink von Benutzer B weiterhin, was zu Inkonsistenzen (Dateien ohne Eigentümer) führen kann[cite: 1]. * Symbolic Linking (Symlinks): Eine spezielle Datei wird angelegt, die lediglich den absoluten Pfadnamen zur Zieldatei enthält[cite: 1]. Ist die Zieldatei gelöscht, läuft der Symlink ins Leere (Dangling Link)[cite: 1]. Der Verwaltungsaufwand ist beim Zugriff höher, da der Pfad erst gelesen und aufgelöst werden muss, aber Inkonsistenzen werden vermieden[cite: 1].

Quellen & Materialien
Dieses Modul basiert auf dem Lehrskript „Betriebssysteme“ der German-Baltic Management School.[cite: 1]