Home

Impressum

kreissl.info[rmation science]

best practices

Dateisysteme

Kapitel 9 - Dateisysteme

Freispeicherverwaltung
Verschiedene Dateisysteme wie NTFS
Dateideskriptoren
Was sind I-Nodes?

Hier geht es im Besonderem um Verwaltung, Zugriffsoptimierung und die Umsetzung einer für den Menschen vereinfacht nutzbaren Abstraktion. Der Zugriff auf Daten erfolgt nicht wie beim Hauptspeicher Byte-orientiert, sondern aus Effizienzgründen blockweise, da Platten um ein vielfaches langsamer als Arbeitspeicher sind. Des Weiteren sind bis auf einige Ausnahmen, wie CD ISO9660, die meisten Dateisysteme Betriebssystemspezifisch.

Was ist eine Datei?

Eine Datei ist ein logisches Betriebsmittel, welches eine endliche Menge zusammengehöriger Daten beinhaltet. Verzeichnisse sind spezielle Dateien, welche zur Strukturierung von Dateisystemen eingeführt wurden.

Welche Möglichkeiten der Freispeicherverwaltung von File Systemem gibt es?

Kontinuierliche Allokation - schlecht wenn Datum angehangen werden soll
Verkettete Listen - schlecht, da Wahlfreier Zugriff extrem langsam
Listen mit Zuordnungstabellen - Zuordnungstabellen erlauben schnellen wahlfreien Zugriff (FAT)
Indizierte Speicherung
Indirekt indizierte Speicherung

Ein leeres Dateisystem wird als lineares Medium betrachtet und nach und nach linear aufgefüllt. Vorteil dieser Variante ist schneller Zugriff. Nachteil ist die extreme externe Fragmentierung bei Änderungen von Dateigrößen.

Wie funktioniert das Prinzip der Verketteten Listen?

Listen sind langsamer als kontinuierliche Allokation, bieten nur wahlfreien Zugriff und besitzen nur geringe Fehlertoleranz. Dafür werden aber nur sehr wenig Verwaltungsdaten benötigt. (Hier nur Pointer auf den nächsten belegten Block) Eine Verbesserung der Effizienz wird durch das Nutzen doppelt verketteter Listen erzielt, wobei sich aber auch der Zahl der Verwaltungsdaten verdoppelt.

Wie funktioniert das Prinzip der Listen mit Zuordnungstabellen

Hier werden die Nutzdaten von den Zeigern in eine extra Tabelle ausgelagert. Die Dateizuordnungstabelle am Bsp. FAT enthält für jeden Block einen Eintrag mit einem Verweis auf den Folgeblock oder einen bestimmten Eintrag für EOF. Die Effizient wird hier bei großen Tabellen eingeschränkt.

Wie funktioniert indizierte Speicherung

Für jede Datei wird hier die Startadresse und die Indexlänge gemerkt. So ist zwar schneller wahlfreier Zugriff möglich, aber es herrscht das gleiche Problem der externen Fragmentierung wie bei kontinuierlicher Allokation. Die Geschwindigkeitssteigerung gegenüber Zuordnungstabellen kommt daher, dass Zusammenhängende Blöcke in Zuordnungstabellen nicht hintereinander liegen, sondern verstreut in der Tabelle. Die indizierte Speicherung führt sogenannte Indexblöcke ein, in welche hintereinander die zur Datei gehörigen Blocknummern eingetragen werden. So muss bei einem Zugriff im Worst Case nicht die ganze Zuordnungstabelle nach den Blocknummern durchsucht werden.

Wie groß sollte nun aber so ein Indexblock gewählt werden? Variable längen sind schlecht realisierbar. Wählt man sie zu groß, geht Speicher durch interne Fragmentierung verloren. Wählt man sie zu klein, beschränkt man die Dateigröße... Deshalb wurde die indirekt indizierte Speicherung eingeführt.

Wie funktioniert indirekt indizierte Speicherung

Ein Eintrag im Verwaltungsblock (Indexblock) zeigt wieder auf einen oder mehrere Blöcke, die nun die Verweise auf die wirklichen Datenblöcke enthalten, oder wiederrum auf weitere Indexblöcke. (Dreifach Indirekt) So ist auch auf große Dateien der Zugriff gewährleistet.

Was ist das Besondere an Unix FS Ext 2?

Es werden Inodes für den Zugriff auf Datenblöcke verwendet. Die Dateinamen werden in einer extra Tabelle verwaltet, welche die Attribute (Eigentümer, Zeiten, Größe) und 12 direkte Zeiger auf Blockadressen (einfach, doppelt, dreifach indirekt) enthält.

Welche Festplatten Scheduling-Algorithmen kennen Sie?

First Come First Serve
Shortest Seek Time First (Sektor mit kürzesten Suchzeit suchen)
Scan (Diskarm bewegt sich von einem Ende zum Anderen und bearbeitet Requests)
C-Scan (Diskarm wird bei Erreichen des Endes wieder auf Anfang zurückgesetzt - kreisförmig)
Look (Wie C-Scan, nur wird nur so weit wie notwendig zurückgesetzt)
Look (Wie C-Look, nur kreisförmig)

Welche Bewertungskriterien für Festplattenalgorithmen gibt es?

Caching
Demand Paging wichtiger als E/A der Anwendungen
Robustheit nach Systemabstürzen
Berücksichtigung der hohen Rotationsgeschwindigkeiten moderner Platten
Verzeichnisse und Indexblöcke sollten in mittleren statt äußeren oder inneren Zylindern sein, da dort die mittlere Zugriffszeit am kleinsten ist (im Durchschnitt befindet sich der Lesekopf in der Mitte)

Wie arbeitet FAT - File Allocation Table?

Die FAT Dateizuordnungstabelle liegt auf den ersten Spuren einer Platte. Sie wird aus Sicherheitsgründen oft gesichert. Alle Blöcke einer Platte sind über die FAT miteinander verkettet (abgesetzte verkettete Allokation). Die Größe einer Zuordnungseinheit ist für eine Partition statisch, kann sich aber zwischen den Partitionen unterscheiden (üblich sind 512, 1024 oder 4096 Bytes). FAT bietet weder Schutzmechanismen, noch unterstützt es lange Dateinamen (erst ab VFAT).

Welche Verzeichniseinträge hat FAT?

Dateiname (8+3 Zeichen)
Attribut-Byte
Zeit und Datum der letzten Bearbeitung
Erste Zuordnungseinheit der Datei
Dateilänge

Das Dateisystem assoziiert eine Baumstruktur. Für jede Datei enthält die Dateizuordnungstabelle eine lineare, gezeigerte Liste, mit der die Blöcke der Datei bzw. des Unterverzeichnisses bestimmt werden können. Der Index der Tabelleneinträge stellt die Blocknummer der Festplatte dar.

Wie arbeitet NTFS?

NTFS heißt New Technology File System. NTFS ist mit einem Zugriffsschutz ausgestattet und hat auch keine Größenbegrenzung mehr. Ein Logfile wird verwendet, um nach einem Systemausfall Daten rekonstruieren zu können. NTFS besitzt nur Dateien. Analog zu den I-Nodes beim Unix gibt es beim NTFS eine Master File Table, in welcher jede Datei einen Eintrag besitzt. Zusammenhängende Bereiche (extents) werden als B-Baum organisiert.

Was ist die MFT von NTFS?

Bei kleinen Dateien bzw. Verzeichnissen werden alle Attribute (incl. der Daten) innerhalb des MFT-Eintrages abgelegt (bis zu 1 bis 4 KB). Ein Eintrag in der MFT benötigt einen oder mehrere Sätze der MFT (Satzlänge ist konfigurierbar). Bei großen Dateien enthält der MFT-Eintrag den Wurzelknoten eines B-Baums, dessen "Blätter" die Verweise auf die zusammenhängenden Dateibereiche (Extent oder Lauf) enthalten.

Ähnlich wie die Inode-Tabelle beim UNIX-System stellt die MFT ein flaches Dateisystem dar. Über die Verzeichnisse wird darauf die bekannte Baumstruktur definiert.

Wie werden unter NTFS Dateien eindeutig identifiziert?

Jede Datei ist eindeutig über eine ID identifizierbar. Diese ID ist die Satznummer ihres Eintrages in der MasterFileTable (48 Bit). Zusätzlich wird eine Folgenummer (16 Bit) angehängt, die bei jedem Bezug auf den MFT-Eintrag (z.B. beim Öffnen der Datei) um 1 erhöht wird (für Konsistenzüberprüfungen)

Wie werden unter NTFS Verzeichnisse umgesetzt?

Ein Verzeichniseintrag besteht aus dem Dateinamen, der ID-Nummer der Datei bzw. des Unterverzeichnisses, einer Kopie der Update-Zeit und der Dateilänge aus dem MFT-Eintrag. Verzeichnisse werden nicht wie bei FAT in einer linearen Liste verwaltet, sondern als B-Baum.

Welche Spezialdateien hat NTFS?

MasterFileTable (MFT)
MFT2: enthält die ersten 16 Einträge der MFT als Backup
Eine Logdatei (Daten über Transaktionen zum Wiederherstellen der Daten- bzw. der Dateisystemkonsistenz)
Datenträgerdatei enthält den Namen des Datenträgers, Versionsnummer des Dateisystems und eventuellen Verdacht auf Inkonsistenz
Wurzelverzeichnis
Cluster-Bitmap-Datei für belegte und freie Cluster des Datenträgers
Bootdatei mit dem Startcode für NT
BadClusterDatei, welche Verweise auf defekte Cluster enthält

Wie arbeiten I-Nodes - Das Unix Dateisystem

Die ersten Adressen von Plattenblöcken sind in dem I-Node gespeichert. Diese Adressen reichen aber nur für kleine Dateien aus. Für größere Dateien, welche nicht durch ein I-Node adressierbar sind, gibt es Adressen in dem I-Node, die die Adresse eines Plattenblockes enthalten, welcher weitere Plattenadressen enthält. Dieser Block wird "einfach indirekter Block" genannt. "Einfach indirekte" Blöcke verweisen auf Blöcke, die ihrerseits eine Reihe von direkten Blocknummern enthalten. Beim Zugriff auf Daten über einen indirekten Block muß der Kern zuerst diesen indirekten Block lesen, den passenden direkten Blockeintrag ermitteln und dann diesen Block lesen. Es gibt auch Adressen, die auf Blöcke zeigen, die die Adressen von einfach indirekten Blöcken enthalten. Solche "doppelt indirekten" Blöcke enthalten eine Liste indirekter Blocknummern. Blöcke mit dem Kennzeichen "dreifach indirekt" enthalten eine Liste von doppelt indirekten Blocknummern u.s.w.

I-Nodes

Was sind Dateideskriptoren?

Jedem Prozess ist eine eigene Benutzer-Filedecriptor-Tabelle zugeordnet. Ruft ein Prozess open oder create holt der Systemkern einen freien Inode aus der Inode-Tabelle und übergibt diesen an die globale Dateitabelle und erzeugt einen Eintrag in der Benutzer-Filedecriptor-Tabelle.

Was enthält die globale Dateitabelle des Systems?

Den Offset in Byte zum Dateianfang für den nächsten read- bzw. write-Befehl des Benutzers und die Zugriffsberechtigungen für den Prozeß, der die Datei eröffnet hat. Die Benutzer-Filedecriptor-Tabellen enthalten dagegen nur die geöffneten Dateien eines Prozesses.

Dateideskriptoren

Was beinhaltet ein I-Node?

Dateityp
Eigentümer
Gruppe des Eigentümers
Zugriffsschutzbits
Datumseinträge
Anzahl der Links für diesen I-Node
Zeiger auf den Dateiinhalt

Geräte als I/O Dateien

Es gibt zwei Klassen solcher Dateien. Blockorientierte Spezialdateien und Zeichenorientierte Spezialdateien.

Was sind Blockorientierte Spezialdateien?

Blockorientierte Spezialdateien werden benutzt, um Geräte zu modellieren, die aus frei adressierbaren Blöcken bestehen. ( random access devices wie Festplatten). Wird eine blockorientierte Spezialdatei geöffnet, so kann ein Block gelesen werden, ohne daß man sich um die Struktur des Dateisystems, das dies ermöglicht, kümmern zu müssen.

Was sind Zeichenorientierte Spezialdateien?

werden benutzt, um Geräte zu modellieren, die aus Zeichenströmen bestehen. Beispiele hierfür sind Terminals, Drucker, Netzschnittstellen. Ein Programm schreibt auf das entsprechende I/O-Gerät, indem es in die korrespondierende zeichenorientierte Spezialdatei schreibt. Analoges gilt für das Lesen.

Wie ist das Unix Dateisystems aufgebaut?

Der Bootblock ist meistens im ersten Sektor einer Partition. Er enthält den Bootstrap-Code, der beim Hochfahren eines UNIX-Rechners in den Speicher gelesen wird. Er lädt bzw. initialisiert das Betriebssystem.

Der Superblock beschreibt den Aufbau des Dateisystems. Eine Kopie des Superblocks befindet sich permanent im Speicher. Der Kern schreibt periodisch den Superblock auf die Platte zurück, so daß er immer mit den aktuellen Daten im Dateisystem übereinstimmt. Der Superblock enthält folgende Felder:

Größe des Dateisystems
Anzahl der freien Blöcke
Liste der freien Blöcke
Index auf den nächsten freien Block

Größe der I-Nodeliste
Anzahl der freien Inodes im Dateisystem
Liste der freien Inodes
Index auf den nächsten freien Inode in dieser Liste

Sperrkennzeichen für die Listen freier Blöcke und Inodes
Flag für durchgeführte Änderungen im Superblock

Wie kann ein Prozeß auf Daten auf der Festplatte zugreifen?

Das virtuelle Gerät hinter dem die Festplatte verborgen wird, heißt Datei.
Der Prozeß öffnet die Datei und erhält eine Datei-ID die auf eine Datei-Deskriptor-Tabelle verweist.
Es folgt die Adressierung der Sektoren.
Über die Sektoradresstabelle (FAT oder I-Node Tabelle) werden die Adressen der Blöcke ermittelt
Es folgt die Übertragung der Blöcke zum Hauptspeicher
Zugriff erfolgt nach speziellem Prinzip, wie z.B. SSN
zur Minimierung der Suchzeit muss Wahl einer effizienten Positionierungsstrategie
Durch einen Interrupt oder ein spezielles Register teilt der Controller dem BS das Ende der Übertragung mit.

Wie wird eine Datei unter Unix gesucht?

Linux identifiziert Dateien indirekt über den absoluten Pfadnamen, indem es durch diesen den dazugehörigen I-Node sucht. Jede Datei wird durch einen oder mehrere I-Nodes beschrieben. Die I-Nodes enthalten die Blockadressen der Datei. Ein Katalog (Verzeichnis) enthält alle im Verzeichnis enthaltenen Datei- bzw. Verzeichnisnamen und die dazugehörigen I-Nodes.

Beispielzugriff:

Es soll die Datei /var/log/messages betrachtet werden
Der I-Node des Wurzelverzeichnisses "/" steht an einer definierten Stelle auf der Platte
Es wird das Verzeichnis "var" im Wurzelkatalog (auch eine Datei) gesucht
In diesem Katalog steht der dazugehörige I-Node der auf das Verzeichnis bzw. den Katalog "var" verweist
nun wird in der Katalogdatei "var" nach "log" gesucht und der dazugehörige I-Node gelesen
Nun kann über den I-Node nach dem Eintrag "messages" in "log" gesucht werden
Der I-Node der Datei "messages" wird nun in die globale Dateideskriptortabelle und die lokale Deskriptortabelle des Prozesses geladen
Dieser Dateideskriptor ist das Handle, mit dem der Prozess auf die Datei zugreifen kann
Nach eine Close() wird der I-Node aus der Dateideskriptorliste wieder entfernt.

Inhalt

Anfang

zurück

EOT

Kapitel 1	Einleitung
Ebenen- oder Schichtenmodell, Aufgaben...
Kapitel 2	Modelle
Schichtenmodell, Betriebsmittel, Instanzen...
Kapitel 3	Aktivitäten
Token, Multitasking, Prozesse,Timesharing...
Kapitel 4	Kritischer Abschnitt
Gegenseitiger Ausschluss,Peterson,Semaphore...
Kapitel 5	Scheduling
Prozessorzuteilung, Prioritätsscheduling, RR...
Kapitel 6	Speichermanagment
Freispeicherverwaltung, Segmentierung, Paging...
Kapitel 7	Seitenersetzung
NRU, FiFo, Second Chance, LRU, NFU, Aging...
Kapitel 8	Deadlocks
Bedingungen, Erkennung und Auflösung...
Kapitel 9	Dateisysteme
Freispeicherverwaltung, Festplattenscheduling...

UNIX Codes

Unix Prozesse
Kommunikation

Quellen:

Andrew S. Tanenbaum
Computerarchitektur

Andrew S. Tanenbaum
Moderne Betriebssysteme

Petterson
Computer Architectur & Design

Christian Märtin
Rechnerarchitekturen

Kalfa
Skript und Vorlesung

Word Wide Web
Verschiedenste Seiten

Links:

Prozesse
FH-Bielefeld