sysprog7.pdf

7. Dateisysteme Überblick 7.1 Einführung 7.2 Zuordnung Dateien ® Datenblöcke 7.3 Log-basierte Dateisysteme 7.4 Backup Systemprogrammierung 1  7.1 Einführung Das Dateisystem ist...

7. Dateisysteme Überblick 7.1 Einführung 7.2 Zuordnung Dateien ® Datenblöcke 7.3 Log-basierte Dateisysteme 7.4 Backup Systemprogrammierung 1  7.1 Einführung Das Dateisystem ist die am häufigsten genutzte Abstraktion des BS Mechanismus zum bequemen Speichern und Wiederfinden von Daten, Programmen, … für alle Benutzer Begriffsdefinitionen Ø Datei (file): Sammlung von Daten auf stabilem Speicher unter einem gewählten Namen Ø Verzeichnis, Ordner (directory, folder): Enthält eine Sammlung von Dateien und anderen Verzeichnissen Þ Baumstruktur Ø Dateisystem (file system): enthält einen Verzeichnisbaum; DS-Typ definiert allgemeine Charakteristika (max. Dateinamenlänge, max. Dateigröße, Abstraktions-Algorithmus) Ø Partition: Bereich (zusammenhängende Menge von Blöcken) einer Festplatte, der ein Dateisystem enthalten kann Ø Festplatte: persistentes Speichermedium, heutzutage meist flash-basiert (SSD) oder magnetspeicher-basiert (HDD), üblicherweise in Partitionen unterteilt Systemprogrammierung 2  Dateiattribute (Auswahl) Name: Symbolischer Bezeichner, aussagekräftig für Benutzer und üblicherweise zweigeteilt 1. Benutzervergebener Name der Datei 2. Dateierweiterung: Hinweis zu Typ und Format des Inhalts Bezeichner: Eindeutige – üblicherweise numerische – Kennung der Datei im Dateisystem Typ: UNIX unterscheidet z.B. reguläre Dateien, Verweise (Links), spezielle Gerätedateien, Pipes, Sockets… Position: Speicherort(e) der Datei (Blockadresse(n) in der Partition) Größe Benutzer- und Zugriffsinformationen: Wer darf lesen / schreiben / ausführen, … Zeitpunkte: Erstellung, letzter Zugriff, letzte Modifikation, … Systemprogrammierung 3  Beispiel-Dateityp: ausführbare Programme exec-Systemaufruf: BS soll aktuellen Prozess mit gegebenem Programm ersetzen Dazu muss das BS die Programmdatei öffnen und analysieren Möglichkeit 1: Stapelverarbeitungsdatei Ø Erste Zeile enthält das sog. Shebang (#!), gefolgt vom Dateinamen des Programms, das die Anweisungen in der Datei verstehen und abarbeiten kann Ø Beispiel: ein Shell-Script #!/bin/sh # bei Fehlern während der Abarbeitung des Skriptes sofort stoppen set –e # aktuellen Mensaplan nach /tmp herunterladen, anzeigen # (mit PDF-Viewer „evince“) und schließlich wieder löschen cd /tmp wget https://www.stw.berlin/assets/speiseplaene/321/aktuelle_woche_de.pdf evince aktuelle_woche_de.pdf rm aktuelle_woche_de.pdf exit 0 Systemprogrammierung 4  Beispiel-Dateityp: ausführbare Programme Möglichkeit 2: kompiliertes Programm (Linux: ELF Binary) Ø Erste vier Bytes enthalten eine spezielle Bytefolge („magic“) Ø Der Rest des Headers ist das „Inhaltsverzeichnis“: § Beginn und Größe des Programmcodes („Text“), der Daten, usw. § Einstiegspunkt: nachdem das Programm vollständig geladen wurde, an welcher virtuellen Adresse ist die erste Instruktion? Ø Es folgen die eigentlichen Programminhalte: § Code („Text“) § Daten § Symboltabelle (sehr nützlich zum Debuggen) § Liste von Funktionen, die aus anderen (zusätzlich zu ladenden) Bibliotheken benutzt werden solle Systemprogrammierung 5  Verzeichnisbaum Hierarchische Organisation von Verzeichnissen Ø Sicherheit durch Zugriffsrechte und Benutzeridentifikation Ø Komfort: jeder Benutzer hat alle Namen zur Verfügung Pfade Ø Vollständige Dateispezifikation über Pfadangabe und Dateiname Ø Absoluter Pfad: Weg vom Wurzel-Verzeichnis aus Ø Relativer Pfad: Weg vom aktuellen (Arbeits-)Verzeichnis aus Ø Spezielle Navigations-Symbole: /. aktuelles Verzeichnis.. übergeordnetes Verzeichnis bin home lib ~ Heimat-Verzeichnis des Nutzers Ø Beispiele: libc.so ls alice bob /home/alice/foo.txt../bob/foo.txt ~/foo.txt foo.txt foo.txt Systemprogrammierung 6  Mounting (Linux) Alle Partitionen werden in eine einzige Verzeichnisstruktur eingebunden Ø Systempartition bildet die globale Wurzel Ø Zusätzliche Partitionen können an ein leeres Träger-Verzeichnis („Mount point“) einer anderen Partition angedockt werden (gemountet) mount P2 /home P1 (system) P2 P1 (P2 unter /home) / / / bin home lib bin home lib alice bob ls alice bob libc.so ls libc.so foo.txt foo.txt foo.txt foo.txt Systemprogrammierung 7  UNIX Verweise (Links) Link = Verweis auf eine Datei in einem anderen Verzeichnis Þ Dateien können in mehreren Verzeichnissen sichtbar sein Ø Hard Link: beide Einträge verweisen auf denselben eindeutigen Bezeichner im Dateisystem Þ kein Unterschied zwischen „Quelle“ und „Ziel“ des Links § Beim Löschen einer der beiden ist die Datei am anderen Ort noch da § Hard Links nur innerhalb eines Dateisystems möglich Ø Soft Link (Symbolic Link): Link enthält den symbolischen Bezeichner (also den Dateinamen) des Ziels § Link definiert also nicht die Datei direkt, sondern ist eine „Weiterleitung“ § Wenn Originaldatei gelöscht wird, ist der Link „dangling“ und kaputt (und die Datei nicht mehr zugreifbar) § Soft Links über den gesamten Verzeichnisbaum möglich, also auch über Dateisysteme / Mount points hinweg Systemprogrammierung 8  Partitionierung einer Festplatte (MBR-Schema, 1983) Sektor 0 der Festplatte: MBR (Master Boot Record) Ø 446 Bytes Boot-Code Ø 4*16 Bytes: Partitionstabelle (Start/Ende-Adresse der Partitionen) Ø 2 Bytes: „magic“ Jede Partition enthält ein Dateisystem Ø Bootblock: Code zum Laden des in dieser Partition installierten BS Ø Superblock: Schlüsselparameter des Dateisystems („magic“ zur Typ-Identifikation, Anzahl Blöcke, administrative Informationen) Ø Liste der freien Blöcke Ø Verwaltungsstrukturen für die existierenden Dateien und Verzeichnisse Ø Eigentliche Daten Partitionstabelle MBR Partition 1 Partition 2 Partition n Bootblock Superblock Freispeicher I-Nodes root Dateien und Verzeichnisse Systemprogrammierung 9  7.2 Zusammenhängende Zuordnung Dateien ® Datenblöcke Einfachste Abbildung: Zusammenhängende Belegung Ø Dateiblöcke gleicher Größe werden direkt hintereinander abgelegt Vorteile Ø Dateizugriff mit maximaler Effizienz Þ Lesen einer Datei mit einer kontinuierlichen Operation Ø Direkter Zugriff auf einzelne Blöcke möglich Ø Einfache Verwaltung, da lediglich die Länge und die Indexnummer des ersten Datenblocks bekannt sein müssen Systemprogrammierung 10  Zusammenhängende Zuordnung Dateien ® Datenblöcke (2) Nachteile Ø Fragmentierung des Datenträgers durch Löschen/Anlegen von Dateien unterschiedlicher Länge Ø Probleme, wenn mehrere Dateien zum Schreiben offen gehalten werden müssen Ø Nur in speziellen Fällen brauchbar Wiederentdeckung durch Beschreiben von CD-ROMs / DVDs / Blu-Rays Systemprogrammierung 11  Belegung durch verkettete Listen (allgemeine Idee) Dateien können unter Nutzung geeigneter Datenstrukturen beliebig auf die Datenblöcke verteilt werden Ø Interne Verkettung Ø Externe Verkettung Ø Indexblöcke Interne Verkettung ohne Verwaltungsdatenblöcke Ø Startblock ist direkt im Dateiverzeichnis abgelegt Ø Jeder Block verweist auf seinen Nachfolger Ø Ausschließlich sequentielles Lesen möglich Datei A B A B B A A B Block 0 Block 1 Block 1 Block 2 Block 0 Block 2 Block 3 0 1 2 3 4 5 6 Datei B Systemprogrammierung 12  Belegung durch verkettete Listen: Interne Verkettung Vorteile Ø Keine externe Fragmentierung, Größenvorgabe nicht nötig Ø Einfaches Anlegen von Dateien (Ein Verzeichniseintrag) Nachteile Ø Teil des Blocks reserviert für Zeiger Þ interne Fragmentierung Ø Ineffizienter Zugriff: Auswertung vorhergehender Blöcke beim Zugriff notwendig Ø Zuverlässigkeit: Dateiverlust durch Zerstörung eines Blocks. Doppeltverkettung vergrößert die interne Fragmentierung Abhilfe: Gruppierung mehrerer Blöcke in Cluster Systemprogrammierung 13  Belegung durch verkettete Listen: Externe Verkettung (Hilfstabelle) Einsatz bei MS-DOS: FAT = File Allocation Table Phys. BlockNr. Nächster Datenblock Eigenschaften der Allokationstabelle 0 2 Ø Je eine Zeile pro Block des Dateisystems mit Anfang 1 5 Verweis auf Adresse des nächsten Blocks Datei B 2 3 Anfang 3 6 Ø FAT wird an fest reservierter Stelle einer Partition Datei A 4 1 gehalten und laufend aktualisiert 5 7 Ø Startblock einer Datei wird im Verzeichniseintrag abgelegt 6 NULL Ø Dateiende durch NULL-Zeiger angezeigt („kein Folgeblock“) 7 NULL Ende Ende Nachteile Datei A Datei B Ø Ineffizienter Zugriff, da bei jedem Zugriff ein Lesevorgang in der FAT notwendig ist Þ Sprung an Partitionsanfang Ø Bei Fehler im FAT droht massiver Datenverlust; daher redundant vorhanden Systemprogrammierung 14  Belegung durch verkettete Listen: Indexblöcke Zentrale Tabelle wie FAT ist Single Point of Failure und skaliert nicht mit Größe der Festplatte Idee: Tabelle dezentralisieren Þ einzelne Tabelle („Index“) für jede Datei Verzeichniseintrag verweist nicht auf ersten Datenblock, sondern auf einen sogenannten Indexblock Ø Indexblock: enthält Blockliste für diese Datei (als Array, nicht verkettet – daher auch schneller Zugriff an beliebige Positionen der Datei) Ø Zerstörung des Indexblocks Þ Verlust nur dieser einen Datei Systemprogrammierung 15  Indexblöcke: Verschachtelung Problem: Indexblock hat nur Platz für begrenzte Zahl Einträge Wie organisiert man das Abspeichern größerer Dateien? Þ Seitentabellen-Idee aufgreifen: Indexblöcke verschachteln! Idee: (dafür insgesamt weniger) Indizes im Haupt-Indexblock verweisen auf weitere Indexblöcke anstatt auf Datenblöcke Implementierungs-Probleme: Wann wählt man die Tiefe? Wo wird die festgehalten? Usw. Indexblock (variabel verschachtelt) Indexblock Indexblock (verschachtelt) Datenblöcke Systemprogrammierung 16  Indexblöcke: Diagramm Zugriffsschema bei Indexblöcken Ø Lese den Indexblock Ø Lese die i -te Zeile für den Zugriff auf den i -ten Block aus Ø Folge dem Zeiger zur Position des Blocks Belegung eines ganzen Blocks für Indexblock: ungünstig Ø Übliche Blockgröße: 4kB Ø Platz für 1024 (32-bit)-Indizes Ø Für kleine Dateien: massive Platzverschwendung! Ø Maximale Dateigröße: nur 1024*4kB = 4MB! Ø Wie speichern wir kleine Dateien effizienter? Und wie speichern wir größere Dateien überhaupt? Systemprogrammierung 17  Inodes: Beispiel (ext2/ext3-Dateisystem) Indexblöcke heißen bei UNIX inodes (aus „index nodes“) ext2/ext3: Kombiniertes Schema Ø Direct Blocks: Datenblock-Indizes Ø Single Indirect: Verweis auf Block, der weitere Daten-block-Indizes enthält Ø Double Indirect: Zwei Zwischenstufen Ø Triple Indirect: … Systemprogrammierung 18  Inodes: ext4 Extents Inode-Struktur: Platz für 4 Extents (anstelle von 15 Block Indizes) Jede Extents-Struktur enthält eine Start-Dateiblocknummer, ab der sie zuständig ist Ø Entweder: Länge + Zugeordnete Start-Dateisystemblocknummer (DS) Ø Oder: Verweis auf einen separaten Block mit weiteren Extents-Einträgen, die den verwalteten Bereich weiter unterteilen Beispiele (mit 4 Extents und mit mehr als 4 Extents): Ø Dateiblöcke 0-55 Þ ab Dateisystemblock 1200 Dateiblöcke 56-1400 Þ ab Dateisystemblock 9950 Dateiblöcke 1401-1410 Þ ab Dateisystemblock 10 Dateiblock 1411 Þ Dateisystemblock 9 0-39: è DS ab: 1200 0-55: è DS ab: 1200 ab 0: è Extents-Block 40-52: è DS ab: 9700 56-1400: è DS ab: 9950 56-1400: è DS ab: 9950 53-55: è DS ab: 1253 1401-1410: è DS ab: 10 1401-1410: è DS ab: 10 1411-1411: è DS ab: 9 1411-1411: è DS ab: 9 Systemprogrammierung 19  Realisierung von Verzeichnissen Verzeichnisse müssen mindestens Namen und Referenz auf jedes enthaltene Objekt (Datei, Unterverzeichnis, Link, …) enthalten Ø Einfache Organisation: Alle Meta-Informationen (Name, Typ, Größe, Zugriffsrechte, …) werden direkt im Verzeichniseintrag gespeichert Þ Verzeichnis ist Liste von Einträgen (z.B. MS-DOS) Ø Inode-basierte Verzeichnisse haben kürzere Einträge, die nur den Dateinamen und die Nummer der jeweiligen Inode aufnehmen (UNIX) Merke: Inodes selbst sind namenlos! Der Name steht im Verzeichnis, das die Datei (den Link, …) enthält! 1 Spiele Attribute 2 Spiele Mails Attribute Mails Inode- Strukturen News Attribute News Source Attribute Source Systemprogrammierung 20  Verwaltung des Plattenspeichers Ausgangssituation: Fast alle Dateisysteme teilen Dateien in Blöcke fester Größe auf Wie groß soll ein solcher Block sein? Ø Spuren, Sektoren, Zylinder Þ geräteabhängig, ungeeignet Ø Kompromiss zwischen Zugriffsgeschwindigkeit und Fragmentierung Ø Beispiel Datenrate/Platzbelegung als Funktion von der Blockgröße bei einer mittleren Dateigröße von 1680 Bytes Belegung des Plattenplatzes Datenrate (KByte/s) Plattenbelegung (Prozent) Datenrate Blockgröße (Byte) Systemprogrammierung 21  7.3 Log-basierte Dateisysteme Aktuelle Situation Ø CPU-Geschwindigkeit steigt sehr schnell an Ø Vergrößerung der Kapazitäten von Speicher und Caches Ø Festplatten werden immer größer, Geschwindigkeitszuwachs kann jedoch mit dem CPU-Zuwachs nicht mithalten Ø Bedeutung von Caches und Konsistenzproblemen wird immer größer Beispiel: Löschen einer Datei 1. Dateieintrag aus dem Verzeichnis entfernen 2. Inode der Datei freigeben (Inode als „frei“ markieren) 3. Von der Inode belegte Datenblöcke freigeben (DS-Freiliste updaten) Systemcrash zwischen Schritt 1 und 2? Þ „Orphaned Inode“ Systemcrash zwischen Schritt 2 und 3? Þ vermisste Blocks Systemprogrammierung 22  Zuverlässigkeit von Dateisystemen: Konsistenz Konsistenzüberprüfung Ø Vergleich der Daten in den Verzeichnissen mit den Datenblöcken auf der Festplatte und ggf. Behebung der Inkonsistenzen Ø Kritisch bei Inodes, Verzeichnisblöcken, Listen freier Segmente Ø Realisierung mit Hilfsprogrammen wie scandisk, fsck, … Ø Überprüfung von Dateien und Blöcken Vorgehensweise bei Blöcken Ø Zwei Tabellen mit Zählern, wie häufig ein Block vorkommt in § Einer Datei § Der Liste mit freien Segmenten Ø Auslesen aller Inodes und Überprüfung aller Blöcke Ø Bei Konsistenz ist jeder Block in genau einer Tabelle Vermisster Block Blocknummer Konsistenter Zustand Systemprogrammierung 23  Konsistenzüberprüfung (2) Was kann passieren? Ø Vermisster Block: Speicherplatzverschwendung Þ Freiliste aktualisieren Ø Datenblock doppelt als frei ausgewiesen Þ Freiliste aktualisieren Ø Block kommt in zwei Dateien vor Þ kritischer Fall § Wird eine Datei gelöscht, so wird der Block als frei gekennzeichnet § Block wird kopiert Þ beide Dateien haben eigenen Block § Meldung an Benutzer, da eine Datei evtl. durcheinander gebracht wurde Block zweimal frei Block in zwei Dateien Blocknummer Systemprogrammierung 24  Log-basierte Dateisysteme (2) Entwicklung von log-basierten Dateisystemen (auch Journaling Dateisysteme) Ø Verwendung des Transaktionskonzepts und der Recoverymechanismen Grundidee: Ø Dateisystem enthält einen abgeteilten Bereich: das „Logbuch“ Ø Logbuch = Ringpuffer mit den nächsten geplanten Operationen Ø Wenn eine Operation ausgeführt werden soll: § Beschreibung der Operation ins Logbuch schreiben § Eine Prüfsumme der Beschreibung ans Logbuch anhängen § Cache der Festplatte leeren § Operation durchführen § Operation im Logbuch als vollständig abgeschlossen markieren Ø Beim Hochfahren des Systems (womöglich nach Crash): Replay („Wiedereinspielen“) aller nicht abgeschlossenen Operationen im Logbuch Þ „Ganz-oder-gar-nicht“-Prinzip! Systemprogrammierung 25  Log-basierte Dateisysteme: Stufen von Journaling Vollständig: Daten und Metadaten werden über das Journal verarbeitet Ø Vorteil: volle Konsistenz-Garantie Ø Nachteil: alle Daten werden 2x ins Dateisystem geschrieben! Þ große Leistungseinbußen bei Schreibvorgängen Metadata-Only: Inhalt von Datenblöcken wird nicht ins Journal geschrieben Ø Vorteil: deutlich erhöhte Performance (Daten werden nur 1x geschrieben) Ø Nachteil: möglicher Datenverlust, selbst wenn die Metadaten dank Journal konsistent bleiben Ø Beispiel: Anhängen von Text an eine Datei Ø Bei Absturz: neue Größe der Datei korrekt vom Journal replayed, aber neu angehängte Inhalte nicht im Journal Þ verloren Journal muss nicht zwangsläufig Teil des DS sein Ø Journal auf anderer Festplatte (z.B. SSD) Ø Journal in batterie-gestütztem („battery-backed“) RAM Systemprogrammierung 26  Disk quotas (Plattenkontingente) Maximal erlaubte Anzahl von Dateien und Blöcken, die eine Nutzerin belegen darf Unterscheidung zwischen Soft- und Hardblocklimits bzw. Dateilimits Soft limits: Überschreitung x Mal möglich, x a-priori definiert und enthält die entsprechende Anzahl von Warnungen Ø Benutzer dürfen ihre Kontingente kurzfristig überschreiten. Beim erneuten Anmelden überprüft, ob ein Softlimit überschritten ist Ø Falls ja Þ Warnmeldung und x = x – 1. Ist x = 0 Þ Keine weitere Anmeldung möglich Hard limits: keine Überschreitung, Speicherung endet mit Fehlermeldung Realisierung der Quotas mit zwei Tabellen Ø Tabelle 1: Details der geöffneten Datei, Benutzer, Zeiger auf Quotatabelle Ø Tabelle 2: Belegung gesamt, Angaben Soft/Hard limits, Anzahl verbleibender Warnungen Systemprogrammierung 27  Leistungsaspekte: Interaktion Cache – Dateisystem – Treiber Beschleunigung durch Caching der zu schreibenden Blöcke: Plattentreiber sortiert die Schreibaufträge zur Optimierung der Schreibvorgänge Strategien bei Schreiben gecachter Daten auf Festplatte Ø Write through (Synchronous Write): Abschaltung des Cache Þ Daten und Metainformationen werden sofort geschrieben Ø Careful write: Verzögertes Schreiben § Alle Schreiboperationen erfolgen spätestens nach vorgegebener Maximalverzögerung § Inkonsistenzen beim Systemausfall möglich Ø Lazy write: Änderungen werden zunächst nur im Cache durchgeführt § Zyklische Analyse des Speichermediums, z.B. alle 30 Sekunden Þ nach Systemausfall gravierende Inkonsistenzen möglich Systemprogrammierung 28  7.4 Backup Backup: Datensicherung auf redundante Speichermedien Restore: Wiederherstellung verlorener/veränderter Daten anhand der Kopien nach Ø Festplattencrash und anderen Katastrophen Ø Datenverlust nach Fehlbedienung Backuparten: Vollständige und inkrementelle Sicherung Ø Vollständig: Alle Daten werden auf Backupmedium kopiert Ø Inkrementell: Sicherung aller Daten, die sich seit der letzten Sicherung geändert haben Ø Üblich: Wöchentliche vollständige Sicherung (etwa Wochenende) und tägliches inkrementelles Backup Ø Sicherung eines Zyklus (etwa 3-4 Wochen) auf unterschiedlichen Medien Ø Von Zeit zu Zeit Þ Vollständige Sicherung, die nicht überschrieben wird, d.h. ein bestimmter System- und Datenzustand wird konserviert Backupmedien sollen vor Gefahren wie Feuer, Wasserschäden, Erdbeben, Raub, usw. geschützt werden Systemprogrammierung 29  Backup (2) Physische Datensicherung Ø Beginnend mit Block 0 werden alle Blöcke der Festplatte auf ein Band geschrieben Ø Überspringen freier Blöcke Þ Speicherung der Blocknummer notwendig Ø Zugriff auf Bitmap erforderlich, um defekte und daher ausgeblendete Blöcke zu erkennen Ø Vorteil: einfach und schnell Ø Nachteil: keine Inkrementelle Sicherung möglich Logische Datensicherung Ø Beginnend bei einem oder mehreren vorgegebenen Verzeichnissen werden alle Unterverzeichnisse rekursiv durchlaufen und die darin enthaltenen Dateien gesichert Ø Auf dem Band werden sorgfältig identifizierte Dateien abgelegt Þ Restauration gesicherter Dateien einfach Ø Standardvorgehensweise bei den meisten Betriebssystemen Systemprogrammierung 30  Backup (3): Sicherung eines Beispieldateisystems Alle Verzeichnisse, die auf einem Pfad zu einer modifizierten Datei liegen, werden gesichert, obwohl sie selbst nicht verändert wurden Ø Wiederherstellung modifizierter Dateien auf einem frischen System durch vollständigen Pfad möglich Ø Restaurationsort, Besitzer, Zugriffsmodi, Zeiten werden korrekt hergestellt, obwohl das Homeverzeichnis der Datei gelöscht wurde Systemprogrammierung 31  Backup (4): Sicherungsalgorithmus in vier Phasen Rekursives Durchlaufen aller Verzeichnisse. Aufbau einer Bitmap, die mit den Nummern der I-Nodes indiziert wird. Für jede modifizierte Datei wird der entsprechende Eintrag markiert. Alle Verzeichnisse werden – verändert oder nicht – markiert Erneuter rekursiver Durchlauf und Aufhebung der Markierung aller Verzeichnisse, die keine modifizierten Dateien enthalten Nun ist es bekannt, welche Verzeichnisse und Dateien gesichert werden müssen Þ Erweiterung der Verzeichnisse um Attribute und Sicherung Analog für Dateien: Erweiterung um Attribute und Sicherung Systemprogrammierung 32