Modul: B-BS Betriebssysteme WS 2012 Prof. Dr. Rüdiger Brause Adaptive Systemarchitektur Institut für Informatik Fachbereich Informatik und Mathematik

Modul: B-BSBetriebssystemeWS 2012

Prof. Dr. Rüdiger BrauseAdaptive SystemarchitekturInstitut für InformatikFachbereich Informatik und Mathematik (12)

Datei-verwaltung

Folie 2Betriebssysteme: © R.Brause, J.W.G-Universität Frankfurt a.M.Dateiverwaltung

Dateisysteme

Liste von Dateien auf Massenspeicher

= relationale Datenbank!Objektorientierte Datenbank: mit Methoden+AttributenMulti-Media-Datenbank: mit Bild+Tonobjekten+Synchron.

Organisation von DatenbankenPersistent Storage Manager PSM (kleineObjekte)Object-Oriented Database Management System OODBMS

Nummer Name Position Länge Datum ...

0 Datei1.dat 264 1024 11.12.87

1 MyProgram 234504 550624 23.4.96

2 Datei1.dat 530 2048 25.1.97

... ... ... ... ... ...


Dateinamen und Attribute

Dateistrukturen

Dateiimplementierung

Dateiarten


Dateinamen

Hierarchische Dateiorganisation in BaumformKnoten = „Ordner“ = directorygleiche Dateinamen möglich

Zusätzliche Vernetzung

Firma Abteilung 5

Formulare Rudi Hans

BriefVorlage.dot Brief1.doc .. BriefN.doc Brief1.doc BriefM.doc

“Wald” (azykl.Graph)

Alle Dateien

Gruppe 1 ... Gruppe m Datei f

Datei 1 Datei 2 ... Datei n Datei 1 ... Datei s


Dateinamen

Namensbildung Name.ext (üblich)Extension = Dateityp, Dateizweck

Beispiele:.dat Daten; Format hängt vom Erzeugerprogramm ab.doc Textdokument in dem speziellen Format des

Texteditors.pas PASCAL-Programm Quellcode.c C-Programm Quellcode.h Deklarations (header)-Dateien für C-Programme.ps Postscript Dateien zum Ausdrucken.Z, .zip, .gz Komprimierte Dateien nicht genormte Endung!.tar ein gesamtes Dateisystem, in einer Datei abgespeichert.html ASCII-Textdatei für das world wide web-

Hypertextsystem.jpg, .gif, png, Bilddateien (komprimiert/unkomprimiert).tif, .bmp

MS-DOS: 3 Extensionsbuchstaben! Sonst: 215 Char ohne \ / : * ? " < >


Geschachtelte Typen

Beispiel: Skript.ps.gz= Textdatei Postscript-FormatKomprimiert

Dateinamen: Externe Typangabe

Typaktionen Typ verknüpft mit Aktion

Benutzeroberfläche (Desktopmanager HP -VUE, MS-Explorer) behandelt Dateinamen

Liste von Aktionen pro Typ definiert (Kontextmenü)

Doppelklick = erste Aktion ausführen


Dateinamen: UNIX Interne Typangabe

class File Header {a_magic: LONG CARDINAL (* Magische Zahl *)a_txt: CARDINAL (* Code-Segmentgröße *)a_data: CARDINAL (* Segmentgröße der init.

Daten*)a_bss: CARDINAL (* Segmentgröße der nicht

init.Daten*)a_syms : CARDINAL (* Größe der Symboltabelle*)a_entry: CARDINAL (* Start des Programms*)

... }a_magic =407B (* altes Format: Code („text“) und Daten werden nicht schreibgeschützt

und sollen deshalb nicht von anderen Prozessen genutzt werden *)

410B (* Text-Segment wird schreibgeschützt, und das Datensegment wird an die nächsten Seitengrenzen (4 KB) im Speicher gelegt *)

413B (* Text-Segment fängt an der nächsten Seitengrenze der Datei an; text und Datensegmente sind Multiple der Seitenlänge *)


Dateinamen: Eindeutigkeit

Problem: eineindeutige Abbildung langer Namen auf kurzez.B. NTFS MS-DOS (8 Zeichen.3Zeichen)

Lösung Windows NT:Alle illegalen MS-DOS Buchstaben (Nicht-ASCII + Sonderzeichen)

löschen, sowie alle Punkte innerhalb des Namens bis auf den letzten, falls er nicht abschließt. Kleinbuchstaben Großbuchstaben.

Nur die ersten 6 Buchstaben beibehalten, Zeichen „1“ vor dem Punkt einfügen.

3 Zeichen hinter dem Punkt beibehalten, alle anderen löschen.

Ex. Datei gleichen Namens, so wird „1“ zu „2“ bzw. zu „3“, falls schon existiert.

Beispiel: „Längerer Dateiname.text.ps“ LNGERE~1.ps


Dateinamen

absoluter PfadnameDateiname = Kette aus Knotennamen von der Wurzel zum Blatt

Beispiel: /Abteilung5/Rudi/Brief1.doc Unix \Abteilung5\Rudi\Brief1.doc NT

Vorgänger: ..Dieses Verzeichnis .

relativer Pfadname z.B. Rudi/Brief1.doc bei Hans: ../Rudi/Brief1.doc

Abteilung 5

Rudi Hans

BriefN.doc Brief1.doc BriefM.docBrief1.doc


Dateinamen

Vorteil relativer Pfadnamen: PortabilitätBeispiel Programmsystem

/

toolsX toolsY

Daten Programme

Dat1.a liba libb Prog

Absolute Pfadnamen müssen nach Verschiebung des Programmsystems geändert werden, relative nicht !

Folie 11Betriebssysteme: © R.Brause, J.W.G-Universität Frankfurt a.M.

Zugriff mit /users/Rudi/Brief1.doc

user file system

Rudi Hans Ute Festplatte 2

Brief1.doc

/

Dateiverwaltung

Dateinamen: UNIX Pfaderweiterung

Einhängen eines Dateisystems (mounten)

root file system

etc bin usr

users

/Festplatte 1

Frage: Was passiert mit den Dateien, die vorher in „users“ waren?


Dateinamen: UNIX Namensraum

Querverbindungen durch hard links (gleiches Laufwerk) oder symbolic links (anderes Laufwerk)

Beispiel : hard link löschen zu Datei2: Datei bleibt erhalten (Zähler).Problem: rück-referiertes Verzeichnis stand-alone Verzeichnis?

Abteilung5

Gruppe 1 Gruppe2

Rudi Hans

Datei1 Datei2 Datei3

symbolic linkhard link

Baumorientiertes Dateisystem


Dateinamen: Windows NT Namensraum

Namensraum für alle Objekte wie pipes, shared memory, Prozesse, Semaphoren, events, ...

Logische Querverbindungen (symbolic links) ab NT 6.0

Löschen von Dateien: 2 Referenzzähler (user und kernel handles)

„Durchsuchen“-Methode bei jedem Objekt:

Einbindung neuer, unbekannter Dateisysteme möglich!

(Vorteil ADT)


Dateinamen: Windows NT Namensraum

Symbolic link parsing-Methode:

DosDevices

B: C:

Texte Email Partition0

bs_mem.doc bs_files.docObjekt Manager Namensraum

Dateimanager Namensraum

\Device

Floppy0

Beispiel A:\Texte\bs_files.doc

Objekt manager: A:\Texte\bs_files.doc \Device\Floppy0\Texte\bs_files.doc

Dateimanager: Methode Find ( Texte\bs_files.doc )

mit austauschbaren Methoden für FAT, HPFS, CD-ROM, EFS,...

A:HardDisk0


Dateiattribute und Sicherheit

Dateiattribute Dateilänge Datum für Erzeugung, letzte Änderung,.. Log. Attribute hidden, system, Archiv, Erzeuger, Besitzer, Benutzer und ihre Rechte

Rechte & Sicherheit in POSIX-6:

Geringst-möglichste Rechte für eine Aufgabe (least privilege)

Diskrete Angaben für Zugangskontrolle: Wer darf, wer nicht (ACL)

Zugangskontrolle nur von Prozessen größerer Rechte (mandatory control)

Aufzeichnung des Zugangs (audit trail)


Frage

Kann man mit geeigneten Zugriffsrechten (ACL)

Virenaktionen verhindern?

AntwortNein, da auch Systemprogramme mit großen Zugriffsrechten Fehler haben können

Dateiverwaltung


drwx r-x r-x brause 512 Apr23 15:55 .

off 512 May17 17:53 ..

-rw- r-- r-- brause 44181 Apr23 15:56 data1.txt

drwx r-x r-x

Zugriffsrechte: Lesen R, Schreiben W, Ausführen X

Verzeichnisse: r=Liste lesen, w=neue Datei aufnehmen, x=Liste durchsuchen nach Datei („ betreten“ des Verzeichnisses)

Getrennt für Besitzer, Gruppe, Alle

Dateiverwaltung

Dateiattribute und Sicherheit: UNIX

Rechte bei Programmausführung = user RechteAber: set userId, set group Id system calls

ACL ex. in neuerem Unix (Wer, was, wie)


Dateiattribute und Sicherheit: Windows NT

Standardrechte: Read, Write, ExecuteOnly, Vollzugriff, ...ACL ex., neue Gruppen möglich

Auditing möglich

Speziell für Dateien: Attribute

• Dateiname, Gerätetyp, Position in Datei, share-Status(r,w,del)• Mode: sync/async, mit/ohne Cache, seq/random Access, ...• File disposition: temp oder persistent

Methoden• CreateFile(), OpenFile(), ReadFile(), WriteFile(), CloseFile()• Lesen/setzen von Dateiinfo, Attributen, Geräteinfo, Verzeichnissen• Sichern/freigeben der Dateilänge

Attribute implementiert durch Datenströme, neu erzeugbar„MeineDatei.dat : MeinKommentar“ (aber: unsichtbare Viren!)


Verbind.-orientierte Kommunikation

Typische Dateifunktionen

Create File Name, Zugriffsart: Tabelleneintrag

Open File Apprüfen der Zugriffsrechte, Puffereinrichtung,

Close FilePuffer + Tabellen deallozieren,

Read/Write File Puffer schreiben/lesen: DMA!

Seek FileIndex setzen der aktuellen Position random access


Dateifunktionen: UNIX

fd = creat(Name, mode) file descriptor = Index in Tabellefd = open (Name, mode)read (fd, bufadr, nbytes) write(fd, bufadr, nbytes)close(fd)

fd=1 fd=0 fd=1 fd=0Programm1 Programm2 Programm N

fd=2 fd=2 fd=2

Fehlerausgabe Fehlerausgabe Fehlerausgabe

Beispiel Dateideskriptoren in pipesfd=0: Standard Input, fd=1 Standard Output, fd=2 standard error

Programm1 | Programm2 | .. | ProgrammN


Dateifunktionen: Windows NT

Übliche Dateizugriffsfunktionen wie Unix

Bei Veränderung der Dateistruktur: Atomare Transaktionendurch log file service LFS (write-ahead logging)

Ergänzung der Operationen nach Absturz:= Fehlertolerantes Dateisystem

Wirksam bei fail save-System, nicht aber bei aktivem Fehler



Dateistrukturen


Dateiarten


Strukturierte Zugriffsfunktionen

Sequentielle Dateien sequential filesMagnetbänder, Lochstreifen z.B. put, get in PascalProblem: unbekannte Zugriffsreihenfolge

Wahlfreie Dateien random access filesFestplatten, CD-ROM: Positionsangabe (offset) möglichProblem: ineffizient zum Suchen bei bekannter

DatenorganisationIndexsequentielle Dateien index-sequential filesIndex Sequential Access Method (ISAM) von IBM, 1960/70

Übersicht (Index) am Dateianfang,Ordnung nach einem Kriterium (Schlüssel),

z.B. Name, Geburtsdatum, ...Grundlage für MYISAM→MySQL, MS Active Directory, Access

Fehlen der DB-Unterstützung: Problem bei UNIX!


Indexsequentielle Dateien

Beispiel: Einwohnerdatei, Schlüssel = Alter

Auffüllen von Containern der Größe m mit Schlüsseln

Baumstruktur für indizierten Zugriff

Index-sequentielle Speicherung (ohne Kopfbewegung: Zylinder, Spur, Sektor)

Beispiel 12 Record-Schlüssel: 5, 15, 26, 42, 48, 56, 80, 82, 97, 37, 50

48 97 Index 1. StufeZylinder

x£48 48<x£97

26 48 80 97 Index 2. StufeSpur

x£26 26<x£48 x£80 80<x£97

5 15 26 37 42 48 50 56 80 82 97 Index 3. StufeSektor

Datensätze

Problem: Eingliedern/Ausgliedern von Datensätzen in die Container (Datenblöcke) fester Größe, z.B. „41“

Folie 25Betriebssysteme: © R.Brause, J.W.G-Universität Frankfurt a.M.Ein- und Ausgabeverwaltung

Festplattenmodell

Schreib/Lese-MagnetkopfSchreib/Lesespur mit SektorenZylindergruppe: Spuren bei mehreren Platten

Zylindergruppe

Schreib-/Lesekopf

Positionier-mechanik

Drehachse

Spur mitSektoren

Alu-Platte mit Eisenoxid



NeuordnungSchnellerer Zugriff: Jeder Schlüssel wird nur einmal notiert und enthält bereits das Info für den Dateizugriff

Pro Intervall ein Ast (oder Blatt), max. m Intervalle pro Knoten, m-1 Schlüssel

Ist ein Schlüssel nicht vorhanden, wird er im Intervall auf unterster Stufe eingefügt und ein neues Blatt (Platzhalter) wird daneben erzeugt Alle Blätter sind auf der selben Ebene

Ist ein Behälter zu voll, so wird er in zwei Behälter aufgeteilt und der Schlüssel in der Mitte eine Ebene höher verschoben

Beispiel: m=5 (max. 4 Schlüssel pro Knoten bzw. Schlüsselbehälter) Die 12 Record-Schlüssel 5, 15, 26, 42, 48, 56, 80, 82, 97, 37, 50 werden abgespeichert



Beispiel: m = 5 Schlüssel 5, 15, 26, 42, 48, 56, 80, 82, 97, 37, 50

Eingliedern

Index 1. Stufe

Index 2. Stufe485 15 26 42




Schlüsselbehälter aufspalten

Index 1. Stufe

Index 2. Stufe

26

5 15 42 4826




Schlüsselbehälter auffüllen

Index 1. Stufe

Index 2. Stufe

26

5 15 42 48 56 80 82




Schlüsselbehälter teilen

Index 1. Stufe

Index 2. Stufe56

26

5 15 42 48 80 82

56




Schlüsselbehälter auffüllen

Index 1. Stufe

Index 2. Stufe97

26

5 15 42 48 80 82

56

5037


B-Baum

Allgemein: Einfacheres Einfügen neuer Schlüssel

Intervall (Ast oder Blatt) suchen für neuen SchlüsselEinfügen auf unterster Stufe in einen BehälterBehälter bereits voll (ex. m-1 Schlüssel) : Aufteilen in zwei Behälterhälften und Einzelschlüssel

[S1...St-1], St, [St+1...Sm] mit t = m/2

Mittleren Schlüssel St nach oben verschieben in höhere Stufe

Bei Überlauf im Behälter der höheren Stufe wie oben verfahren

Eigenschaften Gleiche Anzahl von Verzweigungen pro Behälter pro Ebene Schlüsselbehälter sind mind. zur Hälfe ( m/2 ) voll

„B-Baum“


B-Baum

Definition B-Baum (Bayer, McCreight 1972)

Ein B-Baum der Ordnung m ist ein Baum, bei dem

(1) die Wurzel (wenn sie nicht Blatt ist) mind. 2 und max m Äste hat

(2) jeder Knoten mit k Verzweigungen k–1 Schlüssel (Indizes) enthält,

(3) jeder Ast bzw. Knoten (bis auf die Wurzel und Blätter) in minimal k = m/2 und maximal k = m Äste verzweigt,(minimal zur Hälfte gefüllte Behälter)

(4) alle Blätter auf derselben Ebene sind. Die Blätter selbst tragen keine Information; sie stellen nur mögliche

Einfügepunkte für Indizes dar.

Satz: Bei N Schlüsseln gibt es N+1 Blätter


B-Baum

Anzahl der nötigen Stufen (Baumtiefe) (ungerades m)

1.Stufe: mind. 2 Verzweigungen der Wurzel nötig2.Stufe: mind. 2 mal m/2 Verzweigungen auf der Stufe3.Stufe: mind. 2 mal m/2 mal m/2 Verzweigungenn-te Stufe: mind. 2m/2m/2.. = 2m/2n–1 Verzweigungen

= N+1 Blattverzweigungen

Wir erreichen spätestens in der n-ten Stufe 2m/2n–1 = N+1 Verzweigungen.Also: 2m/2n–1 = N+1

n–1 = logm/2 (N+1)/2 Log. Suchzeit! BeispielBei m=200, N=2 Mill.: max. n-1 = log100(1106)=log100(1003) = 3 Stufen, also nur max. n=4 Stufen!

B-Bäume sind flach !


B-Baum

Problem: Häufiges Teilen der Behälter

Verbesserungen:

Ausgleich zwischen vollen und leeren BehälternVerschiebe vom Schlüsselbehälter mit m–1 Schlüsseln

zu einem Nachbarbehälter mit k < m-1 Schlüsseln so, dassjeweils die halbe Gesamtschlüsselzahl verbleibt und der mittlere Schlüssel mit Index i= (k+m)/2+1 nach oben wandert.

Aufteilen von zwei vollen Behältern in drei BehälterTeile vollen (m-1) und übervollen (m) Behälter + dazugehörenden Schlüssel der nächsthöheren Stufe (=2m) in drei Behälter auf zu je (2m-2)/3 Schlüssel, sowie 2 für die nächste Stufe.

Also jeweils (2m–2)/3, (2m–1)/3 und (2m)/3 Schlüssel, wobei die beiden Schlüssel SA und SB mit den Indizes A= (2m-2)/3 +1, B = A + (2m–1)/3 +1 nach oben in die höhere Indexstufe wandern.

Jede Partition ist nicht mind. ½, sondern 2/3 voll


B*-Baum

Definition B*-Baum Ein B*-Baum der Ordnung m ist ein Baum, bei dem

(1) die Wurzel mindestens 2 und maximal 2 (2m–2)/3 +1 Verzweigungen hat. Damit kann die Wurzel beim Überfließen in 2 Behälter zu je (2m–2)/3 Schlüssel (plus ein Schlüssel als neue Wurzel) geteilt werden.

(2) jeder Ast bzw. Knoten (bis auf die Wurzel und Blätter) in minimal k = (2m–1)/3 und maximal m Äste verzweigt.

(3) jeder Knoten k–1 Schlüssel (Indizes) enthält.

(4) alle Blätter auf derselben Ebene sind.


Beispiel B*-Baum


B*-Baum: Eingliedern in Wurzel mit max 2 (2m–2)/3 = 4 Schlüsseln

Index 1. Stufe

Index 2. Stufe485 15 26 42


Beispiel B*-Baum


B*-Baum: Wurzel-Schlüsselbehälter aufspalten

Index 1. Stufe

Index 2. Stufe

26

5 15 42 4826

Resultiert in 2 Behälter je (2m–2)/3 = 2 Schlüssel wie beim B-Baum


26

155 42 48

Beispiel B*-Baum


B*-Baum: Überfließen

Index 1. Stufe

Index 2. Stufe829756 805

42

2615 48 56 80 825 15

48

4226 56 80 82 97


26 56

B*-Baum: Beispiel


B*-Baum: Behälter dreiteilen

Index 1. Stufe

Index 2. Stufe 42 80265 15 56 82 97 37

37 42 48

48

m=5 (2m-2)/3=2 (2m-1)/3 =3 (2m)/3 =3


B-Baum vs. B*-Baum

Vergleich B-Baum vs. B*-Baum

Beispiel: Aufbau + Einfügen von „41“

m=5

(a) (b)

26 42 56 37 56 Index 1.Stufe

5 15 37 41 48 50 80 82 97 5 15 26 41 42 48 50 80 82 97 Index 2.Stufe

Fazit: B*-Baum hat besseren Füllgrad weniger Behälter nötig



Dateistrukturen


Dateiarten


Mehrfachlisten und Invertierte Dateien

Die Indexfolge jeder Schlüsselart ist als Liste implementiertBeispiel: Mehrfachliste (z.B. für Alter, Größe, ..)

Indexfolge 1, 3, 2, 6, 5, 8

Problem: Sequentielle Schlüsselsuche

Lösung: Alle Zeiger im Dateianfang: invertierte Datei

(SchlüsselRecord, statt umgekehrt)

Schlüssel 1

Schlüssel 2

...

Schlüssel m

Satz 1 Satz 2 Satz 3 Satz 4 Satz 5 Satz 6 Satz 7 Satz 8


Bibliotheksdateien= BS-typische, von allen Prozessen nutzbare Funktionen,

die nicht im Kern sindVorteile weniger Hauptspeicher nötig, da Modul nur einmal vorhanden Wartung ist erleichtert, da zentralAber:

Speicher wird billiger & wenige Module sind oft benutztAnfangsadresse Null nicht immer möglich relozierte Kopien nötigWartung ist bei zentraler Verteilung lokaler Kopien einfacherDLL-Hölle: Mehrere Module gleicher Version bilden eine Gruppe & Verschiedene Programme benötigen unterschiedliche Funktionalität

von Modulversionen gleichen Namens & kein Schnittstellencheck CRASH unklarer Herkunft !

Also:• Bibliotheksmodule bei Applikation lassen• registrierte Systembibliotheken automatisch reparieren

(WIN 2000: 2800 signierte System-DLLs)


Idee: wahlfreier Zugriff auf Massenspeicher = RAMPlattenspeicherblöcke Hauptspeicherseiten

memory mapped files

paging

Datei auf Platte virt. Adreßraum im Hauptspeicher

Daten

header

Daten

code

stack

Vorteile: Einlesen des Bereichs nur wenn nötig (ohne Kopie) Pufferung automatisch durch Paging (kein extra Cache nötig)

Problem: Änderung der Länge der Datei auf Platte


memory mapped files

Beispiel Unixmmap() stellt eine Abbildung von virtuellem Adreßraum in den

Bereich einer Datei her.munmap() beendet die Abbildung. Wurde der Speicherinhalt

verändert, so werden die veränderten Seiten auf die Datei zurückgeschrieben.

msync() aktualisiert die Datei aus dem Speicher.

Außerdem: Semaphor-Operationen zur Synchronisation

Beispiel Windows NT VM-Manager & I/O-Manager

CreateFileMapping() erzeugt ein ObjektOpenFileMapping() öffnet es anderen Prozesse unter dem Namen

MapViewOfFile() Teilbereiche daraus in den virt. Adreßraum abb.FlushViewOfFile() aktualisiert den Dateibereich UnmapViewOfFile() wieder schließen


special files

Abbildung von Dateimechanismen auf Gerätesteuerung Öffnen/Schließen von Dateien = Initialisierung der Geräte Lesen/Schreiben von Daten = I/O der Daten Statusänderung der Datei = Statusänderung des Geräts

Beispiel Unix„/dev/tty“ Terminal ein/ausgabe (character-oriented)„/dev/mt“ Magnetband (block-oriented)Open(),close(),read(),write() Ein Gerät, mehrere Namen

und damit Modi (sequentiell, random access) möglich.

Ioctl() Statusänderung, z.B. Übertragungsmodus&GeschwindigkeitMount() Wurzelknoten des Dateisystems auf Gerät ersetzt Datei

Beispiel Windows NT virtual filesZugriff auf Geräte, Netzwerkverbindungen etc. wie auf normale Dateien



Dateistrukturen


Dateiarten



Kontinuierliche SpeicherzuweisungDatei „in einem Stück“: Schnell, aber nicht änderbar.

Listenartige SpeicherzuweisungVerzeigerte Liste von Speicherblöcken (Strategien!)

Vorteil Rekonstruktion möglich bei Anker-Löschung Nachteil ineffizienter wahlfreier Zugriff, da nur sequentiell möglich

Datei A

Datei B Nil

BBlock 0

ABlock 1

BBlock 1

BBlock 2

ABlock 0

ABlock 2

BBlock 3

0 1 2 3 4 5 6



Zentrale indexbezogene Speicherzuweisungzentraler Block von Zeigern (Indizes) in einer Liste

Anfang Datei B

Anfang Datei A

Ende Datei B

Phys.BlockNr = ListenIndex

nächsterDaten-block

0 21 52 33 64 15 76 NIL


Beispiel: Zentraler Index

Beispiel File Allocation Table FAT von MS-DOS

Blockgröße: 512 Byte (= 1 Sektor), Block 0: Bootstrap,

Blöcke 1-5: FAT mit je Eintrag 12 Bit = 3 Hexzahlen = 1.5 Byte pro EintragBlöcke 11-17 Wurzelverzeichnis

Pro cluster 1024 Byte = 2 Blöcke

Cluster 0

Cluster 1

Cluster 2

Index 3

12 Bit

1024 Byte

Index 2

Index 4

Index 5

Index 6

Block 18/19

Block 20/21

Block 22/23

Maximale Diskettengrößemax. FATgröße: 5 Blöcke512 = 2560Byte

Max. Zahl der Einträge = 2560/1.5 = 1706 Einträge (cluster), also max 1706 Einträge 1024 Byte-Cluster

= 1,7 MB pro Diskette


Beispiel: FAT

Beispiel File Allocation Table FAT von MS-DOS (Block 11-17)

DateiName.ext A reserved tim dat st len

32 Byte-Verzeichniseintrag (16 Stück pro 512 Byte-Sektor)

A = 8 bit-Bitmap,1 = wahr0 = falsch

Unterverzeichnis = Datei mit Verzeichniseinträgen

Datei nur lesenverborgenSystemdateiGerätename, nicht DateinameUnterverzeichnisArchiveReserviertReserviert


Beispiel: Zentraler Index

FAT-Probleme bei PlattenIndexgröße Floppy 12 Bit Platten 16 Bit 212 Einträge 216 Einträge = 216 Cluster

Problem1: zu wenige ClusterBei 2 GB Platte und 216 Cluster istClustergröße = 2 GB/Clusterzahl

= 231/216 = 215 = 32kB groß: großer Verschnitt von 16kB!

Problem2: zu kleine Cluster

Bei 2 GB Platte und 1kB Clustergröße 231/210 = 221 = 2 Mill. Einträge. Da jeder Eintrag 2 Mill andereEinträge referieren kann, muss er mind. 21 Bit (3 Bytes) breit sein. Dies bedeutet 2 Mill. 3 Bytes = 6 MB Platz für die FAT-Tabelleim Hauptspeicher, ohne dass alle Einträge benutzt werden.

Bei kleinen Clustern gibt es lange Listen im RAM sowie lange Suchdauer.


Implementierung

Zentrale indexbezogene Speicherzuweisungzentraler Block von Zeigern (Indizes) in einer Liste

Anfang Datei B

Anfang Datei A

Ende Datei B

Phys.BlockNr = ListenIndex

nächsterDaten-block

0 21 52 33 64 15 76 NIL

Problem: Lange Listen, unbenutzter Indexplatz


Implementierung

Verteilte indexbezogene Speicherzuweisung

Statt zentraler Index aller Dateien pro Datei eigene Indexliste:

Datei A4157...

Datei B0236

NIL

Problem: Bei einigen Dateien ex. sehr viele Blöcke, lineare Blocksuche wird langsam.


Implementierung

Verteilte indexbezogene SpeicherzuweisungBaumstruktur zur schnellen BlocksucheTabellengröße vs. Suchzeit: 1-,2-,3-stufige Tabellen

phys.

Blöcke

(a) einstufige (b) zweistufige (c) dreistufige Übersetzung (einfach-indirekt) (zweifach-indirekt)

... ... ...


Implementierung: UNIX

Zentrale Tabelle pro Datei: i-node (Indexknoten) z.B. EXT2Verwaltungsdaten (Referenzen, Zeiger für free-Liste + mount()-Tabelle), erste Adressen von Datenblöcken + Zeiger für weitere

Verzeichnis = Datei = Tabelle aus Dateinamen + i-node-Nummer

Zentrale Tabelle aller i-nodes = super node

modelink countowner uidowner gidfile size

3 time ref.

Adressender e rsten10 Blö cke

1-indirekt2-indirekt3-indirekt

Max 256 Einträge (Zeiger)

67 MB

Max 256 Einträge (Blockindizes)

266 kB

16,8 GB


Implementierung: UNIX

LINUX Dateisystemkonzept

Prozess 1 Prozess 2

Virt.Datei-system

VFS

user mode

kernel mode

v-node cache

directory cachedcache

Dateisystemca. 20 Stck

Gerätetreiber

Datencache

Minix Ext2 Reiser Proc . . .

tape disk1 disk2 D/A print . . .

syscalls: create, open, close, lseek, read, write, stat


Dateiimplementierung: UNIX

LINUX- Beispiel EXT2 Dateisystem (1993)

Blockgruppen (kopierte) Dateiinformationen

Gruppe 0

Gruppe 1

…

Gruppe N

Super Block-Kopie

Gruppenbeschreibung

1 Block Belegungs-Bitmap

Inode Bitmap

Inode-Tabelle

Datenblöcke



LINUX- Beispiel EXT2 Dateisystem Gruppenbeschreibung

(kopierte) Gruppeninformationen

Deskriptor 0

Deskriptor 1

…

Deskriptor M

ADR (Block-Bitmap)

ADR (inode Bitmap)

ADR (Inode-Tabelle)

Anzahl freier Blöcke

Anzahl freier inodes

Anzahl von Verzeichniseinträgen



LINUX- Beispiel EXT2 Dateisystem Verzeichniseinträge

Inode-Index: 3

Nächster Eintrag

Länge des Namens:

8

MeinName

.

..

inode-Tabelle

0

1

2

3

4

5

Inode-Index: 4

Nächster Eintrag

Länge des Namens:

11

AndererName


Dateiimplementierung: Windows NT

KonzeptVolumes (log. Massenspeicher) als DatenspeichereinheitAlle Untereinheiten eines volumes sind nur Dateien (files), gekennzeichnet durch eine 48 Bit-Zahl &16Bit-Sequenznummer

Vorteile Dateien vs. dedizierte Blöcke (Plattenbereiche)

einfacher, konsistenter Dateizugriffsmechanismus, sogar auf die boot-Information.

Die Sicherheitsinformationen sind getrennt pro Objekt (Verwaltungsinformation) besser anpaßbar an die inhaltlichen Notwendigkeiten des Objekts bzw. der Funktion.

Werden Plattenteile unbrauchbar, so können die Verwaltungs-informationen unsichtbar für den Benutzer auch auf andere Plattenteile verlagert werden.


Chkdsk-Programm

Dateiimplementierung : MFT

~ ~

Datei 0 Eigeneintrag Master File Table

Datei 1 Sicherheitskopie der MFT ( Plattenmitte)

Datei 2 log file: Alle Operationen, die die NTFS-Struktur ändern, werden hier verzeichnet und garantieren so atomare Dateitransaktionen.

Datei 3 volume file: Statusinformationen Name, NTFS Version, ...corrupted Bit=1:

Datei 4

attribute definition table:Attributstypen + ihr Status

Datei 5

Root directory : Name des Wurzelverzeichnisses, z. B. \

Datei 6

bitmap file: Belegungstabelle der volume-Speichereinheiten (Cluster)

Datei 7 boot file: bootstrap Code von Windows NT und die physikalische Geräteadresse der MFT -Datei.

Datei 8 bad cluster file: Verzeichnis der unbrauchbaren volume

-Cluster

. . .

Datei 16 Normale Benutzerdateien und Verzeichnisse

Eintrag


Nichtresidente Attributsteile

MFT-Eintrag

standard information file name

security descriptor data stream

start VCN 0

start LCN 1261

length 4

start VCN 5

start LCN 1265

length 4

.. .. ..

HPFS extended attr. ...

0 1 2 3 1261 1262 1263 1264

VCN LCN

5 6 7 8 1265 1266 1267 1268

Dateiimplementierung : Windows NT

Struktur eines Master File Table-Eintrags

(eigentliche Datenblöcke)

Lücke: Datenkompression!



Struktur des Wurzelverzeichnisses root directory

root file Indexpuffer

Standardinformat ion

file name „ \ “

B*-Baum index root

file 4

file 10file 15

index alloc ation VCN ®LCN

bitmap XXX0XX0XXXXX

...

VCN0 file 0, …1 file 1, …2 file 3, …3

VCN4 file 6, …5 file 8, …67 file 9, …

VCN8 file 11, …9 file 12, …10 file 13, …11 file 14, …

Max. 15 Dateien (Schlüssel)

pro container (4 Cluster)

Wurzelcontainerdes B*-Baums



Interne Datenstrukturen für eine NTFS-Datei

Object manager data NTFS memory data NTFS disk database

processmaster file

table

...

fileco ntrol

block

streamco ntrolblocksdata

str eam

user-definedattribute

file handletable

...

fileobject

fileobject

Hauptspeicher Massenspeicher

Documents

Modul: B-BS Betriebssysteme WS 2012 Prof. Dr. Rüdiger Brause Adaptive Systemarchitektur Institut für Informatik Fachbereich Informatik und Mathematik