6 Folien/Seite

Überblick
Vorlesung Betriebssysteme II
I
Implementierung von Dateisystemen
I
Thema 6: Dateisysteme/Massenspeicher
I
I
I
Robert Baumgartl
I
Kontinuierliche Allokation
Verkettete Liste
Indizierte Speicherung
Journaling
I/O-Scheduling
I
I
8. Juni 2015
I
I
FCFS, SSTF
SCAN (Elevator) und Varianten
Shortest Access Time First (SATF)
Verfahren im Linux-Kernel
1 / 43
2 / 43
Kontinuierliche Allokation
I
I
I
I
I
I
Verkettete Liste
fortlaufende Ablage der Daten einer Datei auf
Massenspeicher
Dateiparameter: Anfangsblock, Länge
schneller sequentieller und wahlfreier Zugriff
bei konstanter Dateilänge (ROM) vorteilhaft
nachträgliche Einfüge- und Löschoperationen nur mit sehr
großem Aufwand möglich
Beispiel: ISO9660
Nr.
12
13
14
15
16
17
18
...
A
A
A
A
B
B
C
I
Listenelement: Nutzdatenfeld + Zeiger auf Nachfolger
I
verwirklicht variable Dateigröße
I
Dateiparameter: Anfangsblock
Nr.
13
...
A
14
15
16
17
A
A
A
B
0016
0015
FFFF
0014
...
0042
...
Endekennzeichen
Abbildung: Datei als einfach verkettete Liste
Logische Speicherblöcke
Abbildung: Kontinuierliche Allokation von Blöcken
3 / 43
4 / 43
Verkettete Liste
Liste mit Zuordnungstabelle
Nachteile
wahlfreier Zugriff sehr langsam (vom Start durch Liste
suchen)
I
Unterbrechung der Liste führt zum Verlust aller dahinter
liegenden Daten
I
Nutzdatenteil keine Zweierpotenz (ungünstig für Transfer
Hauptspeicher ↔ Massenspeicher!)
→ mehrfache Verkettung ? (
Ablage der Folgezeiger in separater Tabelle
I
Sicherungskopien der Tabelle generierbar
I
Totalverlust des Dateisystems, wenn Tabelle korrumpiert
I
wahlfreier Zugriff effizienter, da kompakte Abspeicherung
der Verwaltungsinformationen
I
Beispiele: FAT12, FAT16, FAT32
...
I
I
behebt Nachteile nicht)
0016
14
0015
15
FFFF
16
0014
17
0042
Nr.
...
13
14
15
16
17
A
A
A
A
B
...
...
→ Trennung Nutzdaten und Verkettungsinformationen
13
Dateizuordnungstabelle
Abbildung: Prinzip der Zuordnungstabelle
5 / 43
6 / 43
1
Indizierte Speicherung
Speicherung mit variablen Indexblocks
...
I
alle zu einer Datei gehörigen Blocknummern in separaten
Indexblocks abgelegt
I
Dateiparameter: Startadresse des Indexblocks, Länge
I
sequentieller und wahlfreier Zugriff effizient
I
Verlängern und Verkürzen von Dateien problematisch (→
Umordnung der Indexeinträge nötig)
I
feste Größe der Indexblocks ebenfalls ungünstig
0007
Start A
0013
Ende A
Start B
Ende B
Start C
0016
0014
0015
0042
0047
0071
Indexblock für A
Indexblock für B
...
8 / 43
7 / 43
Indirekt-indizierte Speicherung
Indirekt-indizierte Speicherung
...
I
I
I
I
0015
Indexblock
frei
Anzahl Indexblöcke erhöhen
Anzahl Indirektionsstufen erhöhen
Kombination direkter mit indirekter Indexierung
frei
0042
langsamerer Zugriff als direkte Indexierung (zusätzliches
Lesen der Indexblocks nötig)
...
I
0014
...
I
Start A
Start B
Start C
Idee: Speicherung der Indexinformationen in separaten
Blöcken (gleiche Größe wie Nutzdatenblöcke)
wenn ein Indexblock nicht ausreicht:
0013
0016
0047
frei
...
frei
9 / 43
10 / 43
Beispiel: ISO 9660 (1988)
Beispiel: ISO 9660 (1988)
I
keine Freispeicherverwaltung nötig
I
Entwurfsziel: unter jedem Betriebssystem lesbar
(→ kleinster Nenner – MS-DOS)
I
unterstützt Sets von CDs (maximal 216 − 1), mehrere
Partitionen pro CD
I
alle Binärfelder sowohl big- als auch little endian-kodiert
I
erlaubte Zeichen im Namen: Großbuchstaben, Ziffern, ’_’
Bytes
1 1
8
Startsektor
8
Dateigröße
Länge des Verzeichniseintrags
7
Datum, Zeit
1
2
4 1
CD#
I
maximale Verschachtelungstiefe: 8
I
3 verschiedene Levels der Dateibenennung
Erweiterungen:
4−15
Dateiname
I
Rock Ridge – ermöglicht UNIX-Attribute und -Dateinamen
I
Joliet – längere Dateinamen, Unicode-Zeichen, größere
Tiefe
Länge des Namens
Flags
Name
.
Ext ; Ver
Abbildung: Verzeichniseintrag im Dateisystem ISO9660
11 / 43
12 / 43
2
Beispiel: UNIX-Dateisystem
Beispiel: UNIX-Dateisystem
Dateiadressierung mittels Inodes
Inode
I
Verwaltungsstruktur jeder Datei: Indexknoten (index node,
inode)
enthält Attribute (Flags, Zeitstempel,
Eigentümerinformationen) sowie Blockinformationen:
I
I
I
I
einfach indi−
rekter Block
...
I
direkte Adressen
Attri−
bute
doppelt indi−
rekter Block
12 direkte Blockadressen
Adresse eines einfach indirekten Blockes
Adresse eines doppelt indirekten Blockes
Adresse eines dreifach indirekten Blockes
dreifach indi−
rekter Block
Datenblock
13 / 43
14 / 43
Beispiel: UNIX-Dateisystem
Journaling
Nachteil traditioneller Dateisysteme
Operationen über den Dateisystem-Metadaten müssen atomar
ausgeführt werden, sonst drohen Inkonsistenzen.
I
Zugriff auf kurze Dateien effizient
I
Zugriff auf sehr lange Dateien dauert länger, da
Indirektionsstufen abzuschreiten
I
trotzdem sehr große Dateien realisierbar
I
vgl. struct ext2_inode in
include/linux/ext2_fs.h
Beispiel: Löschen einer Datei besteht aus 2 Suboperationen.
a) Löschen des Verzeichniseintrags
b) Freigabe der Datenblöcke der zu löschenden Datei
Was passiert bei Unterbrechung (infolge Stromausfall, Reset,
Systemabsturz usw.)?
nur a) → „verlorene“ Datenblöcke
nur b) → „Datei ohne Inhalt“
Es resultiert ein inkonsistentes Dateisystem, das repariert
werden muss (z. B. mit fsck). Konsequenzen:
I Zeitaufwand
I Gefahr des Datenverlusts bei Nichtbeachtung
15 / 43
16 / 43
Journaling
Journaling
Betriebsmodi
Idee des Journals:
I Schreiboperationen in einem reservierten Bereich des
Massenspeichers, dem Journal, ‘loggen’
I zu bestimmten Zeitpunkten das Journal auf den
Massenspeicher ‘durchschreiben’ (Commit)
Writeback Mode
Schreib−
operationen
nur Metadaten im Journal
I
Datenblocks werden direkt geschrieben
Ordered Mode
Commit
Journal
(on−disk)
I
zuerst werden Datenblocks direkt geschrieben
I
danach Metadaten ins Journal
Data Mode
Dateisystem
(on−disk)
Dateisystem−
Reparatur
I
I
I
sowohl Daten als auch Metadaten im Journal
I
am sichersten (kein Datenverlust möglich), aber am
langsamsten (Daten zweimal geschrieben)
Bei Unterbrechung wird das Journal erneut
durchgeschrieben.
17 / 43
18 / 43
3
Journaling-Dateisysteme
Erweiterte Attribute
Zusammenfassung
Wann erfolgt Journal Commit?
I
bei Erreichen eines bestimmten „Füllstandes“
I
zyklisch
Vorteile gegenüber konventionellen Dateisystemen
I
kleinere Reparaturzeit nach Crash
I
geringere Inkonsistenzgefahr
I
Standardattribute: Zugriffsrechte, Zeitstempel, Eigentümer,
. . . (alles, was im struct stat steht)
I
moderne Dateisysteme bieten dem Nutzer (oder dem
System) die Möglichkeit, eigene Attribute zu definieren und
mit Werten zu belegen
I
meist als Paare „Attributname – Attributwert“, die dem
Inode assoziiert sind, realisiert
Anwendungsbeispiele
I
I
Beispiele: JFS, JFS2 (IBM), XFS (SGI), SFS (Smart File
System), ext3fs, ext4fs, ReiserFS
I
Access Control Lists (ACL) zur feingranularen
Zugriffssteuerung
Alternate Data Streams in NTFS
19 / 43
20 / 43
Erweiterte Attribute in Linux-Dateisystemen
Erweiterte Attribute in Linux-Dateisystemen
Benötigte Systemrufe
I
I
unterstützt im ext2, ext3, ext4, XFS (u. a.)
I
z. B. in ext2 muss beim Montieren die Option user_xattr
angegeben werden
I
Kommandos getfattr und setfattr zum Auslesen
bzw. Setzen der (erweiterten) Attribute
#include <attr/xattr.h>
Ruf
getxattr()
setxattr()
listxattr()
removexattr()
I
I
Semantik
Abfragen eines Attributwertes
Setzen eines Attributwertes
Abfragen der Liste aller Attributnamen
Löschen eines Attributnamens
Unterscheide Löschen des Wertes vs. Löschen des
Attributes!
jeweils 3 Varianten, die differieren in
I
I
Behandlung von symbolischen Links,
Adressierung des Inodes über Pfadangabe oder Deskriptor.
21 / 43
22 / 43
Optimierung von Massenspeicherzugriffen
First Come First Serve (FCFS)
Grundsätzliche Strategien:
I
I
Beeinflussung des Datenlayouts auf Festplatte → angewandt in
(strombasierten) Multimedia-Dateisystemen, z. B. CMFS1
Scheduling (Umordnen) der wartenden
Massenspeicher-Operationen
a) Reduzierung der Positionierungszeit
b) Reduzierung der Positionierungszeit und
Rotationsverzögerung
I
Aufträge in Reihenfolge des Eintreffens ausgeführt,
I
fair,
I
leicht zu implementieren,
I
ineffizient → ungünstig bei großer Last.
Beispiel (40 Sektoren):
Reihenfolge des Eintreffens: 11, 1, 36, 16, 9, 12, 34
Reihenfolge der Bearbeitung: 11, 1, 36, 16, 9, 12, 34
mittlere Weglänge = 10+35+20+7+3+22
= 97
6
6 = 16.2
Zielstellung:
1. Maximierung des Durchsatzes,
0
2. Minimierung der Latenz,
5
10
15
20
25
30
35
3. Fairness.
4. (Garantie der Antwortzeit ↑ Echtzeitsysteme)
1
David P. Anderson, Yoshitomo Osawa und Ramesh Govindan. “A File
System for Continuous Media”. In: ACM Transactions on Computer Systems
(Nov. 1992), S. 311–337.
t
23 / 43
24 / 43
4
Shortest Seek/Service Time First (SSTF)
Elevator-Algorithmus (SCAN)
Auftrag mit der kürzesten Distanz zum aktuellen Auftrag
wird ausgeführt
I minimiert mittlere Antwortzeit
I hoher Durchsatz
I unfair, „entfernt“ liegende Aufträge werden benachteiligt,
I Verhungern möglich: durch kontinuierliches Eintreffen
neuer „naher“ Forderungen werden entfernte Forderungen
blockiert
Beispiel (identische Voraussetzungen):
Reihenfolge des Eintreffens: 11, 1, 36, 16, 9, 12, 34
Reihenfolge der Bearbeitung: 11, 12, 9, 16, 1, 34, 36
= 61
mittlere Weglänge = 1+3+7+15+33+2
6
6 = 10.2
I
0
5
10
15
20
25
30
I
I
unidirektionale Bewegung des Kopfes, Abarbeitung aller
Aufträge, die passiert werden
Bewegung des Kopfes
a) bis zum Ende der Platte oder
b) bis keine Aufträge in dieser Richtung mehr anstehen
(LOOK),
35
I
danach Umkehrung der Richtung und wiederum
unidirektionale Bewegung usw.
I
etwas schlechtere mittlere Antwortzeit als SSTF, da
schlechtere Ausnutzung der Lokalität
I
kein Verhungern mehr möglich
I
Benachteiligung der äußeren Sektoren
I
Aufträge, die in der aktuellen Bewegungsrichtung des
Kopfes liegen, werden bevorteilt
25 / 43
t
26 / 43
Elevator-Algorithmus (SCAN)
Circular Scan (C-SCAN)
Beispiel:
Reihenfolge des Eintreffens: 11, 1, 36, 16, 9, 12, 34
Reihenfolge der Bearbeitung: 11, 12, 16, 34, 36 (U), 9, 1
(initiale Richtung: aufwärts)
mittlere Weglänge = 1+4+18+2+27+8
= 60
6
6 = 10.0
0
5
10
15
20
25
30
35
I
unidirektionale Bewegung des Kopfes bis keine Aufträge in
dieser Richtung mehr anstehen, dann Zurückfahren des
Kopfes an Anfang und erneuter Durchlauf in gleicher
Richtung
I
geringer Zeitverlust durch Rücklauf des Kopfes (nur
sinnvoll, wenn Rücklaufzeit vernachlässigt werden kann)
I
Benachteiligung der äußeren Sektoren eliminiert
I
geringere Varianz der Antwortzeit als bei SCAN
Beispiel (identische Voraussetzungen):
Reihenfolge des Eintreffens: 11, 1, 36, 16, 9, 12, 34
Reihenfolge der Bearbeitung: 11, 12, 16, 34, 36 (R), 1, 9
(Richtung: aufwärts)
= 68
mittlere Weglänge = 1+4+18+2+35+8
6
6 = 11.3
t
27 / 43
28 / 43
SCAN und Varianten
0
5
10
Shortest Access Time First (SATF)
15
20
25
30
35
t
I
I
SCAN und C-SCAN bei hoher Last besser als SSTF
geeignet (fairer)
bei SCAN und C-SCAN kein Verhungern möglich
Variante: FSCAN
I 2 Warteschlangen
I während Abarbeitung einer Schlange (SCAN), treffen neue
Anforderungen in andere Schlange ein
I kein „Vordrängeln“ später eintreffender Requests mehr
möglich
29 / 43
I
Einbeziehung der Rotationslatenz (!)
I
Es wird stets der Auftrag ausgewählt, dessen Zugriffszeit
ta , bezogen auf die aktuelle Kopfposition, minimal ist.
I
greedy
I
Verfahren mit der besten Performance aber höchsten
Gefahr des Verhungerns „abseits gelegener“ Jobs
30 / 43
5
Shortest Access Time First (SATF)
Shortest Access Time First (SATF)
Überlappung von Rotation und Seek
Berechnung der Access Time ta
Zur Ermittlung von ta sind notwendig
Drehrichtung
I
Rotationslatenz trot
I
Zeit für Seek zwischen Kopfposition und Zielsektor tseek
I
Zeit für eine komplette Umdrehung trev
Fallunterscheidung:
Zielsektor
tseek
I
Seek beendet, bevor Zielsektor erreicht (trot ≥ tseek ):
ta = trot
I
Seek „zu lang“, d. h. trot < tseek → ganze Umdrehung
warten: ta = trot + trev
I
Anzahl zu wartender vollständiger Umdrehungen kann bei
langen Seeks größer 1 sein
tseek − trot
ta = trot + trev
trev
trot
Kopfposition
31 / 43
32 / 43
Techniken zum Verhindern des Verhungerns
Techniken zum Verhindern des Verhungerns
Batch-Algorithmen
Erzwungenes Ausführen des ältesten Auftrags
I
Batched Shortest Access Time First (BSATF): Während
ein Puffer (komplett) bedient wird, landen alle neu
eintreffenden in einem anderen Puffer.
I
Je kleiner die Anzahl verbliebener Aufträge im Puffer,
desto schlechter arbeitet das Verfahren
I
Variation: „Two-Mode“ Batching: Im Falle des Verhungerns
BSATF, SATF ansonsten (limitiert negativen
Performanceeinfluß des Batching)
I
Leaky BSATF: Wenn bei Bedienung eines Puffers noch
Aufträge hinzukommen, die keinen zusätzlichen Aufwand
verursachen, werden sie sogleich mit aufgenommen.
I
Shortest Access Time First with Urgent Forcing (SATFUF):
Sobald ein Auftrag eine bestimmte Wartezeit überschritten
hat, wird er ausgeführt. Alle Aufträge, die auf dem Wege
zu ihm keine zusätzliche Verzögerung verursachen,
werden ebenfalls ausgeführt.
I
Alle wartenden Aufträge müssen betrachtet werden.
I
Bei hoher Last (und nur dann tritt Verhungern auf)
schlechte Performance: nähert sich FCFS; keine Chance
der „Erholung“ der Wartezeit.
I
Modifikation: SATFUF(N) führt N älteste Aufträge aus,
sobald Wartezeit ein Limit überschreitet (→ Erholung
möglich)
33 / 43
34 / 43
I/O-Scheduling im Linux-Kern
„Writes-starving-Reads“
Grundlagen
I
I
I
I
Beobachtung:
I Leseoperation i. a. synchron
Annahme: Abbildung LBN → PBN ist sequentiell
gewöhnlich write() asynchron, read() synchron
I
I
Latenz beim Lesen kritisch, beim Schreiben nicht
I
Leseoperationen hängen häufig voneinander ab,
Schreiboperationen gewöhnlich nicht
I
Phänomen: “Writes-Starving-Reads” (viele write() vs.
wenige, voneinander abhängige read())
I
struct request in linux/blkdev.h
Schreiboperationen i. a. asynchron
I
I
I
Daten landen im Buffercache des BS
Herausschreiben aus Cache erfolgt später
Schreiboperationen erfolgen häufig im Strom
I
35 / 43
Applikation wartet auf Komplettierung
Operationen hängen voneinander ab
es resultieren viele aufeinanderfolgende Schreibvorgänge
benachbarter Blöcke
36 / 43
6
„Writes-starving-Reads“
Linus Elevator (Kernel 2.4)
Beispiel
Situation:
I
Kopf auf Block 15
I
Schreibaufträge für Block 42 und 44
I
Leseauftrag für Block 2415
I
neu hinzukommende Schreibaufträge für Blöcke 47–49
LBN
0
15
...
42
44
W
W
Kopfposition
47 48 49
...
W W W
R
1 globale Auftragswarteschlange, geordnet nach LBN
I
abgearbeitet nach SCAN
I
empfindlich für “Writes-Starving-Reads” (Vordrängeln
lokaler Schreiboperationen)
I
vgl. drivers/block/elevator.c
Bei Eintreffen eines neuen Auftrags:
2415
...
I
...
1. Vereinigung mit benachbartem Auftrag, falls existent (1
Durchlauf durch WS)
neu
hinzugekommen
2. Anhängen an Ende der WS, falls wenigstens 1 Eintrag
verhungert
D. h. , (lokale) Schreiboperationen drängeln sich vor, lesende
Applikation muss (unverhältnismäßig) lange warten.
Schreiboperationen könnten aber verschoben werden.
3. Einordnen in Warteschlange
37 / 43
38 / 43
Deadline I/O Scheduler
I
globale Auftrags-WS wie im Linus Elevator
I
zwei zusätzliche Queues für Lese- und Schreiboperationen
(FIFO)
I
jeder Auftrag wird in globale und in Read- oder Write
Queue eingeordnet
Bedienung von Aufträgen aus
I
I
I
I
Anticipatory I/O Scheduler
I
Erweiterung des Deadline-I/O-Schedulers um Heuristik
Idee: Nach einer Leseoperation wird kurz (≈6 ms) gewartet, ob
in dieser Region weitere Leseoperationen erfolgen (Wkt. wegen
Lokalität des Zugriffs ziemlich hoch), bevor ein Seek zu einer
anderen Position ausgeführt wird.
Bsp: ein oder mehrere (langsame, da abhängige) Leseströme,
gleichzeitig sehr viele Schreiboperationen
FIFO Read Queue, wenn Auftrag am Queue-Anfang länger
als 500 ms wartet,
FIFO Write Queue, wenn Auftrag am Queue-Ende länger
als 5 s wartet,
ansonsten aus geordneter WS (via SCAN)
I
Scheduler führt Statistik für jeden Prozess über
I
I
I
I
entschärft “Writes-Starving-Reads”
I
im Worst Case bessere Latenz für Leseaufträge
I
I
vgl. drivers/block/deadline-iosched.c
I
I
“average think time”
“average seek distance”
Verbesserung der Reaktionsgeschwindigkeit für
Leseaufträge
insgesamt hoher Durchsatz
Default-Scheduler im Kern 2.6
vgl. drivers/block/as-iosched.c
39 / 43
40 / 43
CFQ und Noop
Praxis
Completely Fair Queueing (CFQ)
I
pro Prozess eine eigene Warteschlange
I
Entnahme einer identischen Anzahl Aufträge aus jeder WS
für das Scheduling
I
Kernel 2.6 enthält: noop, anticipatory (as), deadline, cfq
I
default cfq (seit 2.6.18), bis dahin as
I
entwickelt für Multimedia Storage Server
I
I
Ziel: Fairneß pro Prozeß
I
vgl. drivers/block/cfq-iosched.c
Wechsel des Schedulers (Beispiel):
root@idir:˜$ echo cfq >
/sys/block/hda/queue/scheduler
I
Auswahl eines geeigneten Schedulers a priori schwierig,
aber für Desktop-Systeme unkritisch
I
Werkzeug iotop zur Beobachtung der I/O-Bandbreite
Noop I/O Scheduler
I
FIFO
I
faßt benachbarte Aufträge zusammen
I
sonst keine weitere Optimierung
I
für Geräte, die nicht auf Platten basieren (z.B. MTD)
41 / 43
42 / 43
7
Was haben wir gelernt?
I
Implementationstechniken typischer Dateisysteme
I
Was ist Journaling?
I
Was sind erweiterte Attribute?
I
Verfahren für I/O-Scheduling
I
I/O-Scheduling im Linux-Kernel
43 / 43
8

Download Report