Motivation

Früher Computer ausschließlich zum Rechnen, haben keine Dokumente gespeichert.

Heute auch File-System auch Dokumentenspeicher.

Sekundärspeicher früher zB als Band-Speicher oder Platten-Speicher.

Externer Speicher wird von File-System genutzt da Arbeitsspeicher

File

Menge an Datenblöcke im Speicher.

Mehrere Prozesse können gleichzeitig darauf zugreifen

Lebensdauer nicht durch Termination von Prozessen abhängig

____________

Sichten

User Sicht: File Management

Aus der sicht des Users / Programm Commands sieht man die logische Struktur. (Nicht die dahinterliegende Implementierung)

Ziele

Elemente der Datei Organisation / Datei Zugriff

Der graue Block steht für ein File - eine logische Datei.

OS Sicht: File System

Ermöglicht File Management.

Implementierung von OS-Designer.

Ziele

Effizient Datenblöcke der User $\curvearrowright$ Datenträger.

Elemente des Datei Systems

____________

User Sicht

Record Arten in structured files

Struktured Files

Datensätze einer Datenbank mit gleichem Aussehen (gleicher Struktur)

Man braucht meist eigene Datenbanksoftware um mit ihnen zu arbeiten, aber manche OS unterstützen diese bestimmte Datenformate.

Unstructured sequence of bytes

Default in den meisten OS. Unstructured Files als character-Strings behandelt.

Pile

Records mit unterschiedlicher Länge und Feld-Anzahl

Haben chronologische Reihenfolge

zB jeder Record als Datensatz einer Log-Datei

Schwer zu durchsuchen, Software muss wissen wie Daten zu lesen sind.

Sequential File

Records (Felder) mit fixer Länge und Feldanzahl.

Key-entry bestimmt Position und Reihenfolge der Felder in der Datei (für Suche via Key) .

Indexed sequential file

Noch effizientere Suche: keys in tree mit pointern zu Datensätzen in Datei.

Hinzufügen von Datensätzen schwer

Kurzfristige Lösung: Overflow-file für neu hinzugefügte Dateien

Nach bestimmter Zeit alles mit neuen Indizes neu generiert.

Indexed file

Alle Felder haben eigenen Index, zeigen auf Datensatz

zB Index für Nachnamenfeld in bestimmten Datensatz

Direct (hashed) file

Kein Sortieren mehr von sequential files notwendig, es wird Hashfunktion für keys benutzt.

Keine sequentielle Reihenfolge der Dateien

Overflow file für Kollisionen beim Einfügen.

Files

File Types

Regular files

In vielen OS wird nicht zwischen record Arten unterschieden sondern es gibt nur regular files.

Dabei unterscheidet man:

Directories

Files die dem User erlauben Dateien zu ordnen.

Special Files

Um IO Geräte zu repräsentieren

File Attributes

Nicht jedes OS muss alle diese Attribute unterstützen - Entscheidung des OS designers.

Metadaten / Verwaltungsdaten:

File Names

Kann mit Attributen-Namen oder seperat gespeichert werden.

Anzahl der Zeichen (8 bis 255)

Relevanz von Groß-/Kleinschreibung, erlaubte Zeichen

File Name Extensions zB.docs

File Operationen

Typische Operationen:

Datei Verzeichnis (File Directory / Folder)

Directories sind spezielle Dateien die zur Verwaltung dienen.

Einträge: Name, Attribute, phys. Adresse der Daten

1. Einfache Liste (erste OS)

2. Hierarchische Baumstruktur mit beliebig vielen child nodes

   Verzeichnisse in Hash-Struktur gespeichert für schnellere Zugriffszeiten (vs. separate Dateien).

Verzeichnis mit Baumstruktur

Von Root-Verzeichnis kann man sich überall durchnavigieren.

Absoluter Pfadname (absolute path name)

Relativer Pfadname (relative path name)

Directory Operationen

Typische Operationen:

____________

OS-Designer Sicht

File System Implementierung

Disk und File-System Layout

Partitionen

Jedes User Datei-System $\mapsto$ unabhängige Partition der Festplatte mit gespeichertem File-System

Master Boot Record (MBR)

Damit das OS weiß wie mit den Partitionen zu arbeiten ist.

MBR = initial program loader (IPL), volume boot code, masterboot

Steht in Sektor 0 der Disk, enthält:

Datei Implementierung

Datei im Sekundären Speicher = Sammlung von allokiierten Blöcken

Contiguous Allocation

Datei = eine einzige, aufeinanderfolgende Sequenz an Blöcken.

Wird bei unveränderlichen Datenträgern verwendet wie bei CD-ROMs, DVD-ROMs

$+$ gute Performance beim sequentiellen Lesen

$-$ Platzprobleme beim Vergrößern einer Datei

Einfügen von Blöcken schwer weil eine Datei nach der anderen kommt (Blöcke müssen verschoben werden)

$-$ Löschen und wieder einfügen → externe Fragmentierung

Chained Allocation

Datenblöcke sind miteinander mit einander verlinked - Bearbeiten der Daten leichter.

$+$ keine externe Fragmentierung, Platz gut ausgenützt - Blöcke können überall verstreut sein

$-$ Verstreutheit = keine Lokalität der Blöcke, viele Bewegungen des Lese-Schreib-Kopfes

$-$ langsamer Zugriff bei Random Access (man kann nur sequentiell iterieren)

$-$ Zeiger / Pointer in Datenblock-Liste braucht selbst auch Speicher

Indexed Allocation

Wie Chained Allocation aber

Pointer werden in einer eigenen Tabelle gespeichert ( File Allocation Table FAT ).

$+$ Schneller als sequentielle Iteration

$+$ Blöcke ganz für Nutzdaten verfügbar, kein Speicher für pointer belegt

$-$ Platzbedarf für FAT im Arbeitsspeicher

iNodes (Index Node)

In Unix Systemen verwendet um die Blöcke zu Dateien zu finden.

Eigenschaften:

$+$ iNode wird nur im Memory gebraucht, wenn ein File verwendet wird

iNodes sind in der iNode-Tablle im Dateisystem gespeichert (ein iNode für jedes File).

(notwendig für OS: Array muss maximale Anzahl offener Dateien halten können)

$-$ Anzahl der Blockreferenzen pro iNode ist begrenzt

Verwendung indirekter, doppelt und dreifach indirekter Blöcke. Sie können nicht öfter benutzt werden.

Structured file Implementierung

Allokiierung von Datenblöcken für strukturierte Datensätze.

Methoden zur Abbildung von Records auf Datenblöcke.

Fixed blocking

Records fixer Länge - werden der Reihe nach auf die Datenblöcke übertragen. → Verschnitt.

Beschränkte Anzahl von Records pro Datenblock.

$-$ Effizient aber extreme Fragmentierung.

Variable-length spanned blocking

Records variabler Länge - können auch auf mehreren Blöcken verteilt sein. → Kein Verschnitt.

$+$ Speicher wird besser genutzt.

$-$ Lesen eines Records kann 2 Block-Zugriffe beanspruchen.

Variable-length unspanned blocking

Records variabler Länge - können als ganzes in einem Block gepeichert werden aber nicht nicht über Blockgrenzen hinweg gehen. → Verschnitt.

$+$ Jeder Record kann mit einem Blockzugriff gelesen werden

$-$ Speicher nicht gut ausgenutzt

Directory Implementierung

Auffinden von Dateien

Position des Root Directories

Ermittlung der fixen Position vom Partitionsanfang durch OS:

Directories und File-Attribute

Wo findet OS die File-Attribute?

In Directory-Einträgen

zB Directory-Einträge fixer Größe der Form:

Filename (fixe Größe), Struktur mit File Attributen, eine oder mehrere Block-Adressen

In i-nodes

Directory Einträge: Filename, i-node Nummer

File Block Size

Wie groß sollen die Blöcke von Dateien sein?

Nutzung des Speicherplatzes vs. Zugriffszeit

In Unix Dateisystemen sind über 95% der Dateisysteme < 2KB groß

Verwaltung freier Blöcke

Disk Allocation Table zur Markierung freier Blöcke.

Chained Free Portions

Verlinkte liste von freien Speicherbereichen mit (Zeiger, Länge)-Eintrag.

$-$ Mühsame Suche durch die Liste

$-$ mit der Zeit Fragmentierung

$-$ Overhead für Zeigerupdate (=R/W) bei Fileoperationen.

Bit Tables

Bit-vektor mit je einem Bit pro Plattenblock. (0 oder 1 je nachdem ob Block frei ist) .

$+$ Geringer Platzbedarf, guter Überblick über Folgen von freien Blöcken.

Indexing

Freie Blöcke als eigenes File betrachtet. (4 Methoden um Daten zu verwalten siehe oben)

$+$ Effizient für alle Datei-Belegungsverfahren.

Performance

Plattenzugriffe beschleunigen durch:

Disk Caching (siehe vorherige Eineheit)

Block Read Ahead

Kopfbewegungen der Disk