Transcript
Page 1: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 81

Kapitel 9 Dateisysteme

Page 2: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 82

Überblick Betriebssysteme

6 Einführung

7 Prozesse, Fäden (threads), Scheduling

8. Speicherverwaltung

9 Dateisysteme

9.1 Benutzersicht

9.2 Implementierung

10 Ein- und Ausgabe

11 Nebenläufigkeit und wechselseitiger Ausschluss

12 Deadlocks

Page 3: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 83

9 Dateisysteme

• Eine der Grundaufgaben eines Betriebssystems:Dauerhaftes Speichern von Informationen

• Speichern von Daten auf externen Medien (Disketten, Festplatten).

• Datei – Abstraktion des persistenten (dauerhaften) Speichers, insbesondere unabhängig vom Speichermedium.

• Organisationseinheiten auf externem Medium: Dateien (Files).

• Kleinste Einheit persistenten Speichers – Datei; nichts kann man dauerhaft speichern außerhalb einer Datei.

• Dateisystem = Betriebssystemteil, der sich mit Dateien befasst

Page 4: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 84

Überblick

• 9.1 Von Dateisystem angebotene Funktionalität (Benutzer-Sicht)

• 9.2 Implementierung von Dateisystemen (interne Sicht)

Page 5: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 85

9.1 Externe Sicht auf Dateisysteme

• Aufgabe von Dateisystemen:– Dauerhafte Speicherung von Daten auf Medien wie Festplatten, CDs usw. in

Form benannter Objekte

• Konzept– Bereiche auf dem Medium werden mit einem so genannten Dateisystem

versehen– Dateisystem stellt die Verwaltungsstruktur für Objekte bereit

• Eigenschaften der Verwaltungsstruktur– Hierarchische Strukturierung - Verzeichnisse mit enthaltenen Objekten– Objekte:

• „reguläre“ Dateien (Files)• Verzeichnisse• „Gerätedateien“• Links (Hardlinks, Softlinks)• Pipes, …

Page 6: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 86

Benennung von Dateien

• Benennung durch Dateinamen• Zugriff über Namen• Regeln für Benennung variieren von System zu System

Bsp.:– MS-DOS: Dateinamen bestehen aus

• Eigentlichem Dateinamen (bis zu 8 Zeichen, beginnend mit Buchstaben)• Dateierweiterung: bis zu 3 Zeichen• Keine Unterscheidung zwischen Groß- und Kleinschreibung• Z.B.: PROG.C, HALLO.TXT etc.

– UNIX / LINUX: Dateien bestehen aus• Bis zu 255 beliebigen Zeichen (meistens)• Dateierweiterung: nur Konvention, kein Bestandteil der Namensregeln• Unterscheidung zwischen Groß- und Kleinschreibung• Z.B.: prog.c, Prog.c, prog.c.Z etc.

• Pfadnamen – Absolute: /usr/rw/sysarch/bs/dateisystem.pdf– Relative: bs/dateisystem.pdf im Arbeitsverzeichnis (working directory) /usr/rw/bs

Page 7: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 87

Dateinamen

• Datenamen bleiben beim Kopieren, Verschicken etc. erhalten.• Sie werden kreiert in Kontext eines Pfades, z.B.

/users/RW/articles/echtzeit/predictability• Typischerweise heißt die LaTeX-Hauptquelldatei main.tex• Die daraus erstellte Datei heißt dann typischerweise main.pdf• Ein Programmkommitee-Vorsitzender bekommt 150 Dateien

eingereicht, die mit LaTeX erstellt wurden. • Wie heißen die wohl?• Andere Beispiele:

– SpringerLink stellt Artikel zur Verfügung als Datei mit dem Namen fulltext.pdf

– IEEE ManuscriptCentral benennt etwa folgendermaßen 12376129813987478023487.pdf

Page 8: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 88

Dateistruktur und Dateitypen

• Dateistruktur:– ... in den meisten Systemen unstrukturierte Sequenz von Bytes– Bedeutung der Bytes ergibt sich aus Benutzerprogramm

(siehe Kodierung ! Kap. 2)

• Dateitypen:– Reguläre Dateien

(Sequenzen von Bytes, Benutzerinformationen)– Verzeichnisse: Systemdateien zur Strukturierung des Dateisystems– Modellierung von E/A-Geräten:

• Spezielle Zeichendateien zur Modellierung serieller Geräte, z.B. Terminals, Drucker, Netzwerke

• Spezielle Blockdateien zur Modellierung blockbasierter Geräte, z.B. Disketten, Festplatten, CDs

Page 9: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 89

Dateiattribute (1)

• Dateiattribute - Zusatzinformationen über Dateien, die das Betriebssystem speichert

• Beispiele:– Entstehungszeitpunkt (Datum, Uhrzeit)– Dateigröße– Zugriffsrechte: Wer darf in welcher Weise auf die Datei zugreifen?

• Zugriffsarten:– Lesender Zugriff– Schreibender Zugriff– Ausführung

• Zugreifender– Dateieigentümer– Benutzergruppe des Dateieigentümers– Alle Benutzer

Page 10: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 810

Dateiattribute (2)

• Sicht des Benutzers (Bsp. UNIX / LINUX):$ ls –l• drwxr-x--- 2 wilhelm RW-Flur 4096 2009-01-22 09:26 Betriebssysteme• -rwxr----- 1 wilhelm RW-Flur 460684 2009-06-16 12:19 kap07.pdf• -rwxr----- 1 wilhelm RW-Flur 380855 2009-06-24 10:06 kap08.pdf• -rwxr----- 1 wilhelm RW-Flur 640512 2009-06-24 10:14 kap08.ppt• -rwxr----- 1 wilhelm RW-Flur 2770944 2009-06-23 17:11 kap09.ppt

• Bedeutung der Felder:– Typ des Eintrags: Datei, Verzeichnis– Rechte für Besitzer, Gruppenbesitzer, alle anderen– Anzahl Einträge (Verzeichnis), Anzahl Referenzen (Datei)– Besitzer, Gruppenbesitzer– Speicherplatzverbrauch– Datum der letzten Modifikation– Name

Page 11: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 811

Mögliche Dateiattribute

Page 12: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 812

Rechteverwaltung UNIX (1)

Standardrechte für Verzeichnisse und Dateien:

• Dateien– „r“: Datei darf gelesen (read) werden– „w“: Datei darf geändert (write) werden– „x“: Datei darf als Programm ausgeführt (execute) werden

• Verzeichnisse– „r“: Der Inhalt des Verzeichnisses darf gelesen werden– „w“: Der Inhalt des Verzeichnisses darf geändert werden: Dateien

anlegen, umbenennen, löschen– „x“: Man darf in das Verzeichnis wechseln und seine Objekte

benutzen

Page 13: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 813

Rechteverwaltung UNIX (2)

Sonderrechte:Notation der Ausgabe von ls:

-rwsr-s--- und drwxrwxrwt• Dateien:

– SUID-Prozess (set user id) läuft unter der uid des Programmbesitzers– SGID-Prozess (set group id) läuft mit der gid des

Programmgruppenbesitzers

• Verzeichnisse:– SUID: Ohne Verwendung– SGID: Neu angelegte Dateien gehören der Gruppe, der auch das

Verzeichnis gehört– SVTX: Jeder darf nur löschen, was ihm gehört.

Page 14: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 814

Rechteverwaltung UNIX (3)

• Beispiel SUID:-r-s--x--x … root root … /usr/bin/passwd– Beim Aufruf von 'passwd' läuft das Programm mit der uid des

Besitzers (in dem Fall root).– SUID-root-Programme sind sicherheitskritisch!

• Beispiel SVTX:drwxrwxrwt … root root … /tmp– SVTX verhindert, dass jeder alles löschen darf.

Page 15: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 815

Verzeichnisse, Verzeichnisbaum

• Baumartige hierarchische Strukturierung• Wurzelverzeichnis /• Restliche Verzeichnisse baumartig angehängt:

• „Absolute Pfade“ beginnen mit /, z.B. /home/meier• „Relative Pfade“ beginnen nicht mit /, z.B. schulze• Relative Pfade beziehen sich auf ein aktuelles Arbeitsverzeichnis (working

directory).• Wechsel des aktuellen Arbeitsverzeichnisses durch cd

/

tmp etc var usr lib home

bin man lib meier mueller schulze

Page 16: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 816

Verzeichnisse, Verzeichnisbaum

• Graphische Repräsentation unter Windows:

Page 17: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 817

Zusammenbau von Verzeichnisbäumen

• Anhängen von Dateisystemen

mount /dev/fd0 /home/rw/diskette– Hängt Dateisystem in /dev/fd0 an das Verzeichnis /home/rw/diskette im bestehenden Verzeichnisbaum an

– Evtl. vorhandene Einträge in /home/rw/diskette werden temporär verdeckt; nach Abhängen wieder zugreifbar

• Abhängen mit umount• Geht nur, wenn keine Datei im angehängten Dateisystem geöffnet

ist.

Page 18: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 818

Links

• Zweck von Links:– Ansprechen desselben Objekts mit mehreren Namen

• Beispiel 1:– User meier befindet sich in Arbeitsverzeichnis /home/meier und will

bequem auf ausführbare Datei /home/mueller/mytools/Text/Format/m_format zugreifen.

– Anlegen eines Links im Verzeichnis /home/meier:$ ln –s /home/mueller/mytools/Text/Format/m_format m_format

$ ls –l m_format$ lrwxrwxrwx 1 meier users … m_format ->

/home/mueller/mytools/Text/Format/m_format

– Aufruf durch m_format in Verzeichnis /home/meier.

• Beispiel 2:– Z.B. Aliase für Geräte: '/dev/mouse' statt '/dev/psaux'

Page 19: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 819

Symbolische Links und Hardlinks (1)

• Symbolischer Link auf ein Referenzobjekt (kommt relativ häufig vor): $ ln -s datei1 datei2– Link ist Verzeichniseintrag mit anderem Namen für Referenzobjekt.– Lösche Referenzobjekt: Link zeigt ins Leere– Lösche Link: Referenzobjekt unverändert– Rechte am Link: wie beim Referenzobjekt– Zulässiges Referenzobjekt: beliebiges Objekt im Dateibaum

(absoluter / relativer Pfad) und beliebiger Name– Symbolische Links machen aus dem Dateibaum einen gerichteten,

azyklischen Graphen– Technische Realisierung: siehe später

Page 20: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 820

Symbolische Links und Hardlinks (2)

• Hardlink (relativ selten benutzt): $ ln datei1 datei2– Link erstellt Eintrag mit weiterem Namen für Dateiobjekt– Es gibt einen Linkzähler:

• Dateiobjekt mit n Hardlinks hat Linkzähler n+1.

• Löschen eines Links: Dekrementieren des Linkzählers

• Löschen des Dateiobjekts: Dekrementieren des Linkzählers

• Dateiobjekt wird erst dann wirklich gelöscht, wenn Linkzähler auf 0.

– Zulässiges Referenzobjekt: Dateiobjekt im selben Dateisystem.– Technische Realisierung: später.

Page 21: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 821

Kopieren von Links

Beispiel:

$ ls -l-rw-r----- 2 meier users … datei1lrwxrwxrwx 1 meier users … datei2 -> datei1-rw-r----- 2 meier users … datei3$ cp datei? /tmp ; ls -l /tmp-rw-r----- 1 meier users … datei1-rw-r----- 1 meier users … datei2-rw-r----- 1 meier users … datei3

• Bei allen Kommandos prüfen, wie sie Links behandeln!

Page 22: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 822

Dateizugriff

• Sequentieller Zugriff:– Alle Bytes einer Datei können nur nacheinander vom Anfang

beginnend gelesen werden.– Kein Überspringen– Zurückspulen möglich

• Random-Access-Dateien (Dateien mit wahlfreiem Zugriff):– Lesen erfolgt von der gerade aktuellen Position– Beliebiges Festlegen der aktuellen Position durch Seek-Operation

möglich

Page 23: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 823

Mögliche Operationen auf Dateien

• Operationen entsprechen Systemaufrufen des Betriebssystems:– Create: Erzeugen– Delete: Löschen– Open: Öffnen– Close: Schließen– Read: Lesen von aktueller Position– Write: Schreiben an aktuelle Position– Append: Anhängen an Dateiende– Seek: Bei Random-Access-Dateien aktuelle Position bestimmen– Get attributes: Lesen der Dateiattribute– Set attributes: Verändern der Dateiattribute– Rename: Umbenennen

Page 24: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 824

Mögliche Operationen auf Verzeichnissen

• Operationen entsprechen Systemaufrufen des Betriebssystems:– Create: Erzeugen– Delete: Löschen– Opendir: Öffnen– Closedir: Schließen– Readdir: Nächsten Verzeichniseintrag lesen– Get attributes: Lesen der Verzeichnisattribute– Set attributes: Verändern der Verzeichnisattribute– Rename: Umbenennen

– Kein Write. Verzeichniseinträge werden nur geschrieben bei Create etc. auf Dateien.

Page 25: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 825

9.2 Implementierung von Dateisystemen

• Dateisystem z.B. auf Festplatte:– Festplatte besteht aus mehreren Platten:

– Platten eingeteilt in Sektoren, alle Sektoren der Festplatte durchnummeriert, z.B.:

0 1234

5

etc., etc.

Page 26: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 826

Layout eines Dateisystems (1)

• Sektor 0 der Platte enthält MBR (Master Boot Record).– Verwendet beim Booten– Partitionstabelle mit Anfangs- und Endadresse jeder Partition– Eine aktive Partition

• Bootvorgang:– BIOS liest MBR ein.– Lokalisierung der aktiven Partition– Einlesen und Ausführen des Bootblocks der aktiven Partition– Bootblock enthält Betriebssystem, d.h. Starten des Betriebssystems!

MBR

Partitionstabelle Plattenpartition

Bootblock Superblock Freispeicherverw. I-Nodes Datenblöcke

Ganze Platte

Page 27: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 827

Layout eines Dateisystems (2)

• Bootblock lädt Dateisystem der Partition.• Superblock des Dateisystems enthält Schlüsselparameter des Dateisystems (z.B.

Schreibschutzmarkierung, Name des Dateisystemtyps etc.).• Freispeicherverwaltung: Informationen über freie Blöcke im Dateisystem• I-Nodes:

– Liste von Datenstrukturen– Eine Datenstruktur pro Datei mit wesentlichen Informationen über Datei

• Datenblöcke: Eigentliche Inhalte der Dateien.

MBR

Partitionstabelle Plattenpartition

Bootblock Superblock Freispeicherverw. I-Nodes Datenblöcke

Ganze Platte

Page 28: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 828

Realisierung von Dateien

• 3 verschiedene Alternativen zur Realisierung von Dateien:– Zusammenhängende Belegung– Belegung durch verkettete Listen– I-Nodes

Page 29: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 829

Realisierung von Dateien - Zusammenhängende Belegung (1)

• Abspeicherung von Dateien als zusammenhängende Menge von Plattenblöcken:

Page 30: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 830

Realisierung von Dateien - Zusammenhängende Belegung (2)

• Abspeicherung von Dateien als zusammenhängende Menge von Plattenblöcken:

• Vorteil bzgl. Lesegeschwindigkeit!

Datei A Datei C Datei E Datei G

Datei B Datei D Datei F

Page 31: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 831

Realisierung von Dateien - Zusammenhängende Belegung (2)

• Situation nach Löschen von D und F:

Fragmentierung der Platte!• Verschiebung der Blöcke?• Verwaltung der entstehenden Löcher in Freilisten?• Was passiert, wenn man eine Datei erzeugt, deren Größe aber

noch unbekannt ist?

Zusammenhängende Belegung im allgemeinen keine gute Idee!• Aber: Benutzt bei Spezialfällen wie Dateisystemen für CD-ROMs

Datei A Datei C Datei E Datei G

Datei B

Page 32: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 832

Realisierung von Dateien – Belegung durch verkettete Listen (1)

• Idee: Speichere Dateien als verkettete Listen von Plattenblöcken

• Variante 1:– Datei A:

– Datei B:

Datei-block 0

Datei-block 1

Datei-block 2

Datei-block 3

Datei-block 4

Plattenblock 4 7 2 10 12

Datei-block 0

Datei-block 1

Datei-block 2

Datei-block 3

Plattenblock 6 3 11 14

Page 33: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 833

Realisierung von Dateien – Belegung durch verkettete Listen (2)

Datei A:

Datei B:

• Vorteile: – Keine Fragmentierung– Sequentielles Lesen: Ok.!

• Nachteil: Problem bei wahlfreiem Zugriff auf Block n:n-1 Lesezugriffe auf die Platte, um Block n zu lokalisieren

Datei-block 0

Datei-block 1

Datei-block 2

Datei-block 3

Datei-block 4

Plattenblock 4 7 2 10 12

Datei-block 0

Datei-block 1

Datei-block 2

Datei-block 3

Plattenblock 6 3 11 14

Page 34: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 834

Realisierung von Dateien – Belegung durch verkettete Listen (3)

• Idee für Variante 2:Halte Information über Verkettung der Blöcke im Hauptspeicher ) Ersetze bei wahlfreiem Zugriff Plattenzugriffe durch (schnellere) Hauptspeicherzugriffe

Datei-Allokationstabelle bzw. FAT im Hauptspeicher

• Methode benutzt in – MS-DOS (FAT-12, FAT-16, FAT-32)– Windows 95, Windows 98 (FAT-32)– Windows 2000 (FAT-32, daneben aber auch NTFS = NT File System)

Page 35: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 835

Realisierung von Dateien – Belegung durch verkettete Listen (4)

• FAT:Datei-block 0

Datei-block 1

Datei-block 2

Datei-block 3

Datei-block 4

Plattenblock 4 7 2 10 12

Datei-block 0

Datei-block 1

Datei-block 2

Datei-block 3

Plattenblock 6 3 11 14

Datei A:

Datei B:

Plattenblock 0Plattenblock 1

Plattenblock 2

Plattenblock 3

Plattenblock 4

Plattenblock 5

Plattenblock 6

Plattenblock 7

Plattenblock 8

Plattenblock 9

Plattenblock 10

Plattenblock 11

Plattenblock 12

Plattenblock 13

Plattenblock 14

Plattenblock 15

10

11

7

3

2

12

14

-1

-1

Beginn Datei A

Beginn Datei B

Page 36: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 836

Realisierung von Dateien – Belegung durch verkettete Listen (5)

• Vorteil: Da FAT im Hauptspeicher abgelegt, muss bei wahlfreiem Zugriff auf Block n nur eine Kette von Verweisen im Hauptspeicher verfolgt werden

• Nachteil:– Größe der FAT im Speicher!– Anzahl der Einträge = Gesamtzahl der Plattenblöcke– Auch wenn Platte fast komplett unbelegt!

• Beobachtung:– Man braucht Verkettung der Plattenblöcke nur für aktuell bearbeitete

Dateien!) I-Node-Konzept (UNIX, LINUX)

Page 37: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 837

Realisierung von Dateien – I-Nodes (1)

• Zu jeder Datei gehört eine Datenstruktur, der sog. I-Node (Index-Node)

• I-Node ermöglicht Zugriff auf alle Blöcke der Datei.

• I-Node muss nur dann im Speicher sein, wenn Datei offen ist.– Wenn k Dateien offen sind und ein I-Node n Bytes benötigt, dann nur k ¢ n Bytes insgesamt.

• Einfaches Beispiel:

Page 38: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 838

Realisierung von Dateien – I-Nodes (2)

Bsp.: UNIX System V

I-Node einer Datei enthält– Alle Attribute der Datei– m Adressen von Plattenblöcken

(UNIX System V: m = 10)

Adresse von Plattenblock 0

Adresse von Plattenblock 1

Adresse von Plattenblock 2

Adresse von Plattenblock 3

Adresse von Plattenblock 4

Adresse von Plattenblock 5

Adresse von Plattenblock 6

Adresse von Plattenblock 7

Adresse von Plattenblock 8

Adresse von Plattenblock 9

Dateiattribute

Zeiger auf Block mit weiteren Adressen (einfach indirekt)

Zeiger auf Block mit weiteren Adressen (zweifach indirekt)

Zeiger auf Block mit weiteren Adressen (dreifach indirekt)

Page 39: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 839

Realisierung von Dateien – I-Nodes (3)

• Kleine Dateien bis 10 x 1 KByte (bei Blockgröße 1 KByte):

Zeiger 0

Zeiger 1

Zeiger 2

Zeiger 3

Zeiger 4

Zeiger 5

Zeiger 6

Zeiger 7

Zeiger 8

Zeiger 9

Datenblock 0

Datenblock 1

Datenblock 2

Datenblock 3

Datenblock 4

Datenblock 5

Datenblock 6

Datenblock 7

Datenblock 8

Datenblock 9

Page 40: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 840

Realisierung von Dateien – I-Nodes (4)

• Für größere Dateien werden Datenblöcke zur Speicherung von weiteren Plattenadressen genutzt

• Bsp.: – Blockgröße 1 KByte– Größe eines Zeigers auf Plattenblock: 4 Byte

) 256 Zeiger passen in einen Plattenblock– Nach 10 (direkten) Plattenadressen gibt es im I-Node Zeiger auf

Block mit 256 weiteren Plattenadressen

) Insgesamt Dateien bis zu (10 + 256) x 1 KByte = 266 KByte möglich.

Page 41: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 841

Realisierung von Dateien – I-Nodes (4)

Adresse von Plattenblock 0

Adresse von Plattenblock 1

Adresse von Plattenblock 2

Adresse von Plattenblock 3

Adresse von Plattenblock 4

Adresse von Plattenblock 5

Adresse von Plattenblock 6

Adresse von Plattenblock 7

Adresse von Plattenblock 8

Adresse von Plattenblock 9

Dateiattribute

Zeiger auf Block mit weiteren Adressen (einfach indirekt)

Insgesamt 256 weitere Adressen in indirekt

verbundenem Datenblock

…Adresse von Plattenblock 10

Adresse von Plattenblock 266

Page 42: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 842

Realisierung von Dateien – I-Nodes (5)

• Noch größere Dateien:

Adresse von Plattenblock 0

Adresse von Plattenblock 1

Adresse von Plattenblock 2

Adresse von Plattenblock 3

Adresse von Plattenblock 4

Adresse von Plattenblock 5

Adresse von Plattenblock 6

Adresse von Plattenblock 7

Adresse von Plattenblock 8

Adresse von Plattenblock 9

Dateiattribute

Zeiger auf Block mit weiteren Adressen (einfach indirekt)

Zeiger auf Block mit weiteren Adressen (zweifach indirekt)

Zeiger auf Block mit weiteren Adressen (dreifach indirekt)

Einfach indirekter Block

Doppelt indirekter Block

Dreifach indirekter Block

Adressen von Plattenblöcken

Page 43: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 843

Realisierung von Dateien – I-Nodes (6)

• Bei Blockgröße 1 KB und Zeigergröße 4 Byte erhält man über doppelt indirekten Block 256 x 256 = 65536 Zeiger auf Datenblöcke.

• Zusätzlich noch dreifach indirekter Block …

• Frage: Wie groß ist mit diesen Parametern die maximale Dateigröße?

Page 44: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 844

Realisierung von Dateien – I-Nodes (7)

• Attributinformationen in I-Nodes:– Bsp. UNIX System V

Page 45: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 845

Realisierung von Verzeichnissen (1)

• Verzeichnisse sind ebenfalls Dateien!

• Sie liefern eine Abbildung von – Datei- bzw. Verzeichnisnamen auf I-Node-Nummern.

) Jeder Verzeichniseintrag ist ein Paar aus Name und I-Node-Nummer.

• Über I-Nodes kommt man dann zu Dateiinhalten.

Page 46: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 846

Realisierung von Verzeichnissen (2)

games

mail

news

work

.

..

/

tmp etc var usr lib home

bin man lib meier mueller schulze

games mail news work

45

76

9

14

7

3

I-Node Nr. 45

I-Node Nr. 76

I-Node Nr. 9

I-Node Nr.14

I-Node von mueller

I-Node von home

Page 47: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 847

Verwaltung freier Plattenblöcke (1)

• Datenblöcke im Dateisystem an beliebigen Stellen genutzt.

• Nicht notwendigerweise aufeinander folgend.

• Verwaltung freier Blöcke:– Über Freibereichsliste als verkettete Liste:

• Speichere Nummern von freien Plattenblöcken

• Benutze zum Speichern der Nummern freie Plattenblöcke, die miteinander verkettet werden

– Bitmap• Bitmap mit 1 Bit für jeden Plattenblock

• Plattenblock frei , entsprechendes Bit = 1

Page 48: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 848

Verwaltung freier Plattenblöcke (2)

Page 49: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 849

Verwaltung freier Plattenblöcke (3)

• Wann ist welche Freispeicherverwaltung günstiger?

• Weitere Möglichkeit: Blockung zusammenhängender Bereiche – wann günstig? Eventuelles Problem?

Page 50: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 850

Belegung des Dateisystems

• Belegung gegeben durch Anzahl genutzter I-nodes und Datenblöcke.

• Dateisystem voll, wenn– Keine I-Nodes mehr frei oder– Keine Datenblöcke mehr frei.

• Überprüfung mittels df:

$ df -iFilesystem Inodes IUsed IFree IUse% Mounted on/dev/hda2 64512 6437 58075 10% //dev/hda1 6024 33 5991 1% /boot/dev/hda5 500960 76638 424322 16% /usr

Page 51: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 851

Implementierung von Hardlinks

$ ls –l-rw-r----- 1 meier users … datei1$ ln datei1 datei2$ ls –l-rw-r----- 2 meier users … datei1-rw-r----- 2 meier users … datei2

datei1

datei2

71

71

I-Node Nr. 71

linkcount = 2

Page 52: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 852

Implementierung symbolischer Links

$ ls –l-rw-r----- 1 meier users … datei1$ ln –s datei1 datei2$ ls –l-rw-r----- 1 meier users ... datei1lrwxrwxrwx 1 meier users ... datei2 -> datei1

datei1

datei2

71

39

I-Node Nr. 71

I-Node Nr. 39datei1

Datenblock einer neuen Datei vom Typ LINK, enthält Pfadnamen „datei1“

Page 53: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 853

Steigerung der Leistungsfähigkeit

• Festplatten-Cache zur Beschleunigung von Leseoperationen, – Jeder lesende Zugriff führt zum Laden in den Cache,– Prüfung auf Anwesenheit über Hash-Tabelle,– Ersetzungsstrategien modifiziertes LRU, um Zugriffshäufigkeit

auszunutzen und Konsistenzgefahren zu verkleinern.• Für Konsistenz wichtige Blöcke sofort zurück schreiben,

• Blöcke, die nicht bald wieder zugegriffen werden, z.B. I-nodes, als alt kennzeichnen.

Page 54: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 854

Steigerung der Leistungsfähigkeit (2)

• Reduzieren der Plattenarm-Bewegung• Woraus besteht ein Zugriff auf einen Plattenblock?

– Suchzeit (seek time) – Bewegung des Arms bis zum verlangten Zylinder,

– Rotationsverzögerung (rotation delay) – Zeit zum Erreichen des verlangten Sektors,

– Datentransferzeit – Zeit für die Übertragung der verlangten Daten.

• Meist dominiert die Suchzeit.• Mögliche Effizienzsteigerung:

– Tabelle, indiziert mit Zylindernummer, enthalten Köpfe von verketteten Listen anstehender Zugriffe auf den jeweiligen Zylinder.

– Nächster Zugriff wird mit Strategie Shortest Seek First ausgewählt.– Problem: Fairness– Abhilfe: Aufzugsalgorithmus – ein Bit für Up/Down

Page 55: RW-SystemarchitekturKap. 8 1 Kapitel 9 Dateisysteme

RW-Systemarchitektur Kap. 855

Zusammenfassung

• Objekte zur Datenspeicherung werden meist in Verzeichnisbäumen in Form von Dateieinträgen verwaltet.

• Dateien und Verzeichnisse vom Dateisystem bereitgestellt

• Der Verzeichnisbaum wird aus mehreren Dateisystemen zusammengebaut

• Links erzeugen neue Verweise auf (vorhandene) Objekte

• Verschiedene Implementierungsvarianten für Dateisysteme

• Unterschiede liegen in Effizienz (Speicher und Laufzeit)

• Geeignete Wahl des Dateisystems bestimmt durch Eigenschaften des physikalischen Speichermediums.


Recommended