9. Plattenspeicher und Dateien - … · 9.1.3 Adressierung: • Im Prinzip über über Zylinder, Kopf, Sektor. • Verschiedene Adressierungbeschränkungen: - PC-Bios adressiert nicht

9. Plattenspeicher und Dateien

9.1 Aufbau einer Festplatte

9.1.1 Physikalischer Aufbau

• Staubdicht versiegelt.

• Eine oder mehrere rotierende Platten: - 5.400 - 15.000 U/min,.magnetisierbare FeO-Schicht, meist auf Aluminium, - unterteilt in z.B. 1000 konzentrische Spuren (Tracks) à z.B. 1 MByte. - Zylinder = Gruppe übereinander liegender Spuren, - Spuren sind wiederum in Sektoren unterteilt.

• Beweglicher Kamm: - mit Schreib-/Leseköpfen, - dicht über Magnetschicht, - langsam beweglich (10 ms).

• Sektoren à 512 Bytes netto.

1

9.1.2 Sektoren Betriebssysteme 2004, © P. Schulthess, VS Informatik, Ulm

• Typischerweise 512 Bytes pro Sektor derzeit üblich.

• Entstehen durch physikalische bzw. Low-Level-Formatierung.

• Lücke zwischen Index-Record & Datenrecord: - Index-Record wird nur beim Low-Level formatieren geschrieben. - Datenrecord wird immer und wiederholt als Ganzes neu geschrieben.

• Aufbau: - IAM: Index Adress Mark markiert Adressfeld. - DAM: Data Adress Mark markiert Datenfeld. - SYNC: abhängig vom Aufzeichnungsverfahren. SYNC Datenfeld

IAM #Spur #Kopf #Sektor CRC

DAM 512 Byte Daten CRC

SYNC Adressfeld

2 Betriebssysteme 2004, © P. Schulthess, VS Informatik, Ulm

9.1.3 Adressierung:

• Im Prinzip über über Zylinder, Kopf, Sektor.

• Verschiedene Adressierungbeschränkungen: - PC-Bios adressiert nicht mehr als 8 GB, - "Direct LBA" adressiert 128 GB unter Umgehung des PC-BIOS, - "Direct LBA(48)" adressiert 134'217'728 GB.

• alte Disks (MFM, RLL): - Sektoren haben auf äußeren Spuren grössere Ausdehnung, - Entspricht konstanter Winkelgeschwindigkeit.

• Moderne Disks (IDE): - bis zu 40% mehr Sektoren auf äußeren Spuren.


9.1.4 Fehlerbehandlung:

• Sector Forwarding: - Controller hat Liste „schlechter“ Blöcke und leitet Zugriffsversuch auf

fehlerhaften Block (unsichtbar für Treiber) auf einen Reserveblock um. - Reserveblöcke pro Zylinder oder in Reservezylinder - Auswirkungen auf Disk-Scheduling !

• Prüfsumme und FEC für jeden Sektor.

• Disks sind fehleranfällig - teilweise fehlerhafte Blöcke bei Auslieferung. - Köpfe schweben knapp über der Oberfläche. - Staubkorn kann zum Headcrash führen.


9.2 Festplatten-Scheduling

• Zugriff auf die Festplatte ist viel langsamer als auf den Hauptspeicher: - Suchzeit: Kopf auf Zylinder positionieren. - Rotationsverzögerung bis Sektor unter Kopf.

• Armpositionierung ist besonders teuer: - alte Festplatten (zu Zeiten des XT ~ 1985) haben jeden Spurwechel geprüft

jeweils Arm abbremsen & beschleunigen, - aktuelle Disks überfahren Spuren mit hoher Geschwindigkeit - wo genau Sektoren liegen ist unbekannt.

• Aktuelle Schreib- & Lesegeschwindigkeiten: - Zugriff in einer Richtung schneller, - Zugriffe auf fortlaufende Sektoren schneller, - sequentiell: ~ 50 MB/s; verstreut: ~ 1 MB/s, - Höhere Leistung durch parallele Disks, - Verluste im Betriebssystem.

• Disk-Scheduler (in Treiber) legt Reihenfolge der Festplattenzugriffe fest.


9.2.1 Strategien zur Kopfpositionierung:

• Zufallsstrategie Aufträge werden zufälliger Reihenfolge ausgewählt.

• FCFS (First Come First Serve): Abarbeitung in Ankunftsreihenfolge.

• Prioritätsstrategie: Reihenfolge abhängig von Priorität der Aufträge.

• SSTF (Shortest Seek Time First): kürzeste Armpositionierung zuerst.

• SCAN (Fahrstuhlstrategie): Arm bewegt sich in eine Richtung, immer bis an das Ende und arbeitet dabei alle Aufträge ab. Erst danach ist eine Bewegung zurück oder in eine andere Richtung erlaubt.

• Eine Optimierung der Dateiverteilung ist immer empfohlen.

• Beispiel: - Start bei Zylinder 53; - Sequenz: 98, 183, 37, 122, 14, 124, 65, 67.


9.2.2 FCFS (First Come First Serve):

• FCFS erfordert im Mittel ein Überfahren von 1/3 der Spuren (Gleichver-teilung und volle Festplatte).

• Kopfbewegung über insgesamt 640 Zylinder.


9.2.3 SSTF (Shortest Seek Time First):

• SSTF ist empfohlen, kann jedoch zum „Verhungern“ von Aufträgen führen.

• Kopfbewegung über 236 Zylinder:


9.2.4 SCAN (Fahrstuhlstrategie/Elevator Seek)):

• SCAN, und SSTF bringen vor allem bei starker Last Vorteile. Im Hochlastfall ist evenbtuell nur eine Spur weit zu springen.

• SCAN & SSTF benachteiligen „Randspuren“.

• Kopfbewegung über 208 Zylinder:


9.3 Festplattenorganisation bei PCs

9.3.1 Plattenstruktur

• Festplatten werden in eine oder mehrere Partitionen (Bereiche) unterteilt: - verschiedene Dateisysteme auf einer Festplatte, - mehrere Betriebssysteme auf einer Disk,

Partitionen - Trennung von System & Benutzerdaten, MBR - Besonderheit in Linux: Swap-Partition.

• Master Boot Record (MBR):

Bootlader (446 Bytes)000

Partitionstabelle 446

Signatur (0xAA55) 510

- Position ist (Zylinder 0, Kopf 0, Sektor 1). - Wird durch BIOS beim Systemstart an Adr.

0x7C00 geladen und angesprungen. - Bootlader lädt BS oder Boot-Manager. - MBR nur einmal auf Disk.


9.3.2 Partitionen

• Eine Partitionstabelle beschreibt max. vier Partitionen, die die Disk in unabhäng voneinander nutzbare Bereiche unterteilen.

• primäre Partionen: - immer in Partitionstabelle des Master Boot Records, - in der Regel vier Stück pro Disk bei PCs, - beginnen mit Bootsektor (BSC).

• Erweiterte Partitionen: - Container für logische Unterpartitionen, - beginnen mit Partitionssektor (PSC), - Aufbau wie ein MBR, aber nur als Partitionstabelle genutzt (kein Bootcode).

• Logische Partitionen: MBR

BSC

primäre Part.

erweiterte Part.

logische Part.

BSC

PSC - einer erweiterten Partition zugeordnet, - beginnen mit Bootsektor (BSC), - beinhalten keine Partitionstab.

• Beispiel: 1 primäre & 1 logische Part.


9.3.3 Aufbau eines Partitionseintrages (16 Bytes):

Offset Größe Inhalt

0 1 Boot – Flag (80h aktiv; 00h inaktiv)

1 3 Beginn der Partition (CHS)

4 1 System Kennung: z.B. 0: Eintrag frei, 1: DOS 12-Bit FAT; 4: DOS 16-Bit FAT … 5: erweiterte Partition

F: erweiterte Partition

5 3 Ende der Partition (CHS)

8 4 Entfernung des ersten Sektors der Partition: - vom MBR bei primären Part. - vom PBR bei erweiterten Part.

12 4 Größe der Partition in Sektoren CHS-Einträge nur für alte kleinere Disks. LBA-Adressierung für moderne Disks.


• Erweiterte Partitionen nutzen immer nur zwei Einträge in der Partitionstabelle: - max. ein Eintrag beschreibt ein log. Laufwerk. - max. ein Eintrag verweist auf erweiterte Part. - somit entsteht evt. Kette erweiterter Part., - wobei die erste so gross ist, dass hierin alle geschachtelten Part. beinhaltet sind.

• Beispiel: 1 primäre und zwei logische Partitionen

MBR

BSC

PSC

primäre Part. log. Part. log. Part.

erweiterte Part.

• Besonderheit: „Offest des ersten Sektors“ in der Partitionstabelle: - in primären Partitionen immer bezogen auf phys. Anfang der Disk.

13 B

9.3.4 Namensgebung von Partitionen:

- alle erweiterten Part. beziehen sich auf die phys. Adresse des Ankers der erweiteren Partitions-Kette

etriebssysteme 2004, © P. Schulthess, VS Informatik, Ulm

• Windows: Laufwerksbuchstaben „c:“, „d:“, ... - zuerst primäre Part. von allen Disks, - dann logische Part. aller Disks, - ab NT frei umbennenbar.

• Unix: interner Name: z.B. „/dev/hda2“: - Disk-Volume: a,b,c,d - Partition: primäre = 1 - 4; log.: >= 5

• Bemerkung zu Partitionierungswerkzeugen: - zeigen Schachtelung von erweiterter Partition nicht an. - arbeiten unterschiedlich Vorsicht!


9.3.5 Mounting:

/

home usr etc tmp

Root File System

/

local bin

/dev/hdb5

/

home usr etc tmp

local bin

• „Montieren“ einer Partition in einem Verzeichnis des Dateisystems.

• Auch unterschiedl. (verteilte) Dateisysteme können in einem Dateibaum vereint werden.

mount /dev/hdb5 /usr• UNIX: mount und umount

Befehle.

• Ab Windows NT per Disk-Manager möglich:


9.4 Plattenspeichervergabe

• Sequentielle Natur einer Platte erfordert andere Verfahren als im Heap: - Armbewegungen sind kritisch, - kleines Abbild im Hauptspeicher vorhalten, - optimale Suchverfahren für die Verzeichnisse …

• Vergabequantum: - Praktisch immer festgelegt für eine bestimmte Partition, - Nicht zu gross wählen, da sonst Verschnitt bei kleinen Dateien, - Nicht zu klein wählen, sonst zuviele "Extents", - Typische Werte: 0,5 – 32 KB (je nach Disk).

• Die physische Blockgrösse ist meist kleiner als das Vergabequantum.

512 512 512 512

4 KByte

512 512 512 512

4 KByte

512 512 512 512

4 KByte


9.4.1 Vergabe mit Bit-Vektor

• Partition in Blöcke fester Größe unterteilen.

• Jeweils ein Bit zeigt an, ob ein Block frei ist oder nicht (0=

• 10 GB Disk, 1 KB pro Block 1,25 MB für Bitmap.

• Bewertung: - fortlaufende Blöcke einfach identifizierbar. - u.U. große Bitmap bei kleinen Blöcken. - Bitmap im virtuellen Speicher halten.

4 KB

512 512

4 KByte

512 512 512

4 KByte

512 512 512 51

4 KByte

512 512 512 512

4 KByte

512 512 512 512

4 KByte

01101110100101

512 512 512 512 512 512 512 512

4 KByte

17

belegt,1=frei).

yte

512 512 512 2

Betriebssysteme 2004, © P. Schulthess, VS Informatik, Ulm

9.4.2 Verkettete Freispeicherliste


• Finden von N zusammenhängenden Blöcken schwieriger.

• Ermitteln N aufeinanderfolgendener Blöcke erfordert das Durchlaufen von mindestens N Blöcken.

• Gegebenenfalls effizienter als Bitmap, da nur freie Blöcke gespeichert werden.

18 B

9.4.3 Freispeicherverwaltung mit Zählen

• Verkettete Liste.


1 1

3

1 2

2

1 2

1

2

• Speichern von Zeiger und Anzahl unmittelbar nachfolgender freier Blöcke in einem freien Block.

• Vereinfacht die Suche nach N aufeinander-folgenden Blöcken.

19 B

9.4.4 Freispeicherverwaltung mit Gruppieren

• Speichern der ersten N freien Blöcke im ersten Block.


• N-1 dieser Blöcke sind frei.

• Im N-ten Block sind weitere N freie Blöcke gespeichert - usw.

• Beispiel: N=4 Speichern von Zeiger und An-zahl unmittelbar.

20 B

9.5 Extents von Dateien

• Schrittweise Zuordnung Blöcken für Dateien.

• Mehrere offene Dateien auf einer Festplatte.

• Ziele: - effektive Ausnutzung der Festplatte (Disk), - sehr grosse Dateien müssen möglich sein, - schneller Dateizugriff.

• Z.B. Zusammenhängende Allozierung: - Nur ein Extent pro Datei. - Externe Fragmentierung der Festplatte. - Problem bei der Expansion von Dateien.

Datei Start LängeTest.java 0 2.profile 6 2

Plan 16 3News 19 6Mail 28 4


9.5.1 Verkettete Allokation

• Datei als verkettete Liste von Blöcken. - Beliebige Anordnung der Blöcke einer Datei. - Expansion von Dateien einfach. - Keine Platzverschwendung.

• Speichern von Zeigern in Blöcken. - Bei einem beschädigtem Block geht die ganze Datei verloren.

- Zugriffsgeschwindigkeit abhängig von Zersplitterung. - Z.B. FAT (Zeiger separat untergebracht).

Datei Start Länge

Test.java 9 25… … …


9.5.2 Multilevel-Index Allokation

• Limitierte Dateigröße bei einem Indexblock: - 1 Block = 512 Byte - Z.B. 1 Zeiger = 4 Bytes

max. 128 Zeiger Datei max. 64 kB

• Verketten von Indexblöcken.

Verwaltungs- Information

Direkte Blöcke

Blöcke mit 1er Indirektion

Blöcke mit 2 Indirektionen

• Multilevel Index: - Beispiel: 2 Level - 128*128 Zeiger 16384 Zeiger - max. Dateigröße = 8 MB

• mehrere Levels z.B. in Unix I-Nodes (Typen: Dateien, Verzeichnisse, Links, ...).


9.5.3 Erweiterungsquanten im Mac OS

• Vergabeeinheiten: - Log. Blöcke à 512 Bytes werden normalerweise auf einen phys. Sektor abgebildet. - Die Belegungseinheit (Allocation Block) ist jeweils mindestens 2 logische Blöcke.

Dies reduziert die Größe der Vergabetabellen.

• Die Zuteilung erfolgt aber in Erweiterungsquanten (Clumps) von mehr als einer Belegungseinheit:

phys. EOF Logischer Block (512 Bytes)

Belegungsblock

Erweiterungsquantum

- typisch 4 bis 8 Belegungs-einheiten pro Clump,

- teilweise Rückgabe nach Close,

• Fördert zusammenhängende Dateiplazierung.


9.6 Datei- & Verzeichnissysteme

• Anforderungen: Persistenz, Zugang per Name, Schutz durch Zugriffsrechte,

• Logische Formatierung = Partition mit einem Dateisystem initialisieren.

• Datei (File): = Behälter zur dauerhaften Speicherung von beliebigen Informationen, - Programme und Daten, - Dateistruktur abhängig vom Dateityp. - Attribute: Name, Typ, Grösse, letzte Änderung, Zugriffsschutz, ... - Dateien können mehrere Streams haben:

o Stream: unterteilt Datein in Unterbereich. o DOS: nur ein Stream o NT: beliebige Streams datei:stream

(default stream ohne Suffix). - Namenskonventionen:

o DOS: 8.3 Zeichen name.ext o Unix, NT 256 Zeichen a.b.c.d o Unix: Groß- & Kleinschreibung beachten!


• Verzeichnis (Directory): - vom Dateisystem verwaltete Datei zur Strukturierung externer Speichermedien. - Home Directory: Wurzelverzeichnis eines Benutzers. - Working Directory: aktuelles Arbeitsverzeichnis. - typischerweise hierarchisch organisiert.

• Pfade: - Folge von Bezeichnern getrennt durch Trennzeichen (Unix ‚/’, Windows: ‚\’). - absoluter Pfad: ausgehend von Wurzel (Unix ‚/’, Windows: Laufwerksbuchstaben,

z.B. ‚c:\’). - relativer Pfad: beginnt mit Bezeichner und bezieht sich auf Working Directory.

• Verweis (Link, Shortcut, Alias): - Direkter Zugriff, ohne navigieren zu müssen. - Löschen & Verschieben ungültige Links. - Unix hard link: Verweis auf I-Node (ln datei link).

(Datei wird erst gelöscht, wenn letzter hard link gekappt wurde). - Unix symbolic link: Verweis auf Dateinamen. (ln –s datei link).


9.6.1 Dateikontrollblock

• Verwaltungsdaten im Dateikontrollblock (file control block, FCB): - Positionszeiger + aktuelle Blockadresse auf Disk, - Verweise auf Puffer (im HS) + Pufferfüllgrad, - Sperrinformation, Datum, ...

• FCB ist Teil der Verzeichnisstrukturen auf der Platte.

• Also unter Umständen mehrere FCBs pro Datei.

• Beim Öffnen einer Datei: - Kopie des File Kontroll Blockes im Hauptspeicher anlegen, - Im Hauptspeicher einen Puffer für die Daten allozieren, - Datei als offen markieren (read, write ?). - Zugriffsrechte prüfen.


9.6.2 Dateizugriff

• sequentiell: - lesen & schreiben immer nur in Vorwärtsrichtung, - Magnetbänder als Modellvorstellung.

• direkt (random access): - einzelne Bytes oder Blöcke direkt adressierbar - z.B. Festplatten, CDROM, ...

• index-sequentiell: - i.d.R. von BS nicht unterstützt Datenbanken setzen direkt auf Disk auf, - Zugriff auf einzelne Blöcke über evtl. mehrstufige Indextabelle, - Überlaufbe- Gelegentlic

00102030

28

reiche erleichtern das Einfügen, he Reorganisation erforderlich.

1-100 1-200 1-300 1-400

Betriebssysteme 2004, © P. Schulthess, VS Informatik, Ulm

9.6.3 Beispiel: sequentielle Datei in Windows NT

#include <string.h> #include <windows.h> int main() { HANDLE hFile; DWORD dwWritten; char *data=“hello world“; hFile = CreateFile("c:\\test.txt", GENERIC_WRITE, // name, write access

0, NULL, CREATE_ALWAYS, // share mode & securit, creation mode FILE_ATTRIBUTE_NORMAL| FILE_FLAG_NO_BUFFERING, NULL // template file ); WriteFile(hFile, data, strlen(data), & dwWritten, NULL ); // file handle, data, len, #bytes written, overlapped I/O CloseHandle(hFile); }


9.6.4 Beispiel: File Allocation Table - FAT

• Nietet keine Schutzmechanismen.

• Zugriffsrechte: read-only oder read & write.

• Größenbeschränkung und 8+3 Dateinamen.

• Aber Daten unter vielen BS zugänglich.

• Optionale Kompression.

• Belegungseinheiten heißen Cluster. - Unterschiedlich, aber fest für eine Partition. - üblich sind 512, 1024, 4096 Bytes.

• FAT12 für Disketten:, 12-Bit 4096 Cluster, 16 MB bei 32KB Cluster.

• FAT16: 16-Bit 65.536 Cluster, 2 GB pro Partition bei 32KB Cluster.

• FAT32: 28-Bit > 2 GB, weniger Verschnitt durch kleinere Cluster.

• VFAT16/32: virtual FAT - lange Dateinamen (max 255 Zeichen). - mehrere Verzeichniseinträge verwenden.


• Separate Verkettung der Blöcke in Dateizuordnungstabelle (FAT): - auf den ersten Spuren einer Festplatte, - für jeden Block einen Eintrag,

0 fff7 fff74 7 0 ffff ffff8 a b

#1 #2 #3 #4 #5 #6 #7 #8 #9 #a #bCluster-Nr. (Index in Tab.) Dateianfang

Verkettung FAT-

Einträge- sicherheitshalber repliziert, - Kopie im Hauptspeicher, - wird ständig aktualisiert.

• Alle Cluster einer Datei sind über die FAT verkettet: - 0 = leerer Block, - $FFF7 = schadhafter Block., - $FFFF = letzter Block einer Datei.

• Partitionsstruktur:

FAT

...

Dateicluster

Wurzel-Verz.

BSC



Aufbau eines FAT16 Verzeichnisses:

• Verzeichnisse sind ebenfalls Dateien: - Verzeichnis zeigt auf ersten Block einer Datei, bzw. ersten Eintrag in der Tabelle. - Länge des Verzeichnisses im übergordneten Verzeichnis. - Länge des Wurzelverzeichnis im PSC od. MBR.

• Aufbau eines Datei-Eintrages:

Offset Größe Inhalt0 8 Dateiname 8 3 Dateinamen-Erweiterung11 1 Attribute: Archiv-Bit, read-only, Verzeichnis/Datei, versteckt 12 10 Reserviert 22 2 Uhrzeit der Erstellung 24 2 Datum der Erstellung 26 2 Startcluster der Datei 28 4 Dateilänge in Bytes

• Sonderfälle für das 1. Zeichen im Namensfeld: 00h: letzter Eintrag im Verz. (ungültig), 2E: aktuelles Verz. (‚.’), E5h: Eintrag wurde gelöscht

• Sonderfall für die ersten 2. Zeichen: 2E2E = übergeordnetes Verz. („..“)

Documents

9. Plattenspeicher und Dateien - … · 9.1.3 Adressierung: • Im Prinzip über über Zylinder, Kopf, Sektor. • Verschiedene Adressierungbeschränkungen: - PC-Bios adressiert nicht