Massenspeicherzugriff und Dateizugriff für FAT32 und ext2 Dateisysteme |
| 05.10.2015, 15:49 | Auf diesen Beitrag antworten » | ||||
| RoMa | Massenspeicherzugriff und Dateizugriff für FAT32 und ext2 Dateisysteme Guten Tag zusammen, das ist der erste Post, denn ich in dieses Forum schreibe. Ich schreibe demnächste Technische Informatik II und komme bei einer alten Klausuraufgabe mit der Musterlösung nicht klar. Hier die Aufgabenstellung: "Betrachtete werde der Zugriff auf die letzten 10 Byte einer 1GiB großen Datei im Wurzelverzeichnis auf einem ansonsten leeren, 500 GiB großen Dateisystem. Es werde eine Blockgröße von 4 KiB verwendet. Es soll der Einsatz einer Festplatte und einer SSD betrachtet werden. Beide Datenträger werden anhand von 512 Byte-Sektoren adressiert. Jede Leseanforderung besteht aus einer Sektoradresse und der Anzahl der ab diesem zu lesenden Sektoren. Jede Leseanforderung führt zu der jeweils unten angegebenen Zugriffslatenz, danach liefern beide Massenspeicher beim linearen Lesen diue angeforderte Zahl Sektoren mit dder angegebenen Leserate. Es kommt an keiner Stelle des Systems zu Cache-Mechanismen zum Einsatz. Die Dauern der Verarbeitung der Daten sowie der Befehlsübertragung sollen vernachlässigt werden. Festplatte: Latenz 10 ms, Leserate 100 MB/s SSD: Latenz 1 ms, Leserate 1000 MB/s Frage 1: Es soll das Dateisystem FAT32 zum Einsatz kommen. a) Wie viel Byte belegen die File Allocation Tables mindestens? b) Wie lange dauert es für Festplatte und SSD mindestens, bis die gesuchten 10 Byte voliegen? Wie lange dauert es jeweils im schlechtesten Fall? Frage 2: Es soll das Dateisystem ext2 zum Einsatz kommen. Zur Verwaltung von Datein verwendet ext2 zum einen I-Nodes, die zwar alle Dateiattribute enthalten, aber nur wenig direkte Zeiger auf Datenblöcke speichern, als auch Indexblöcke, die nur Zeiger auf Datenblöcke speichern. a) Wie viele Byte belegen die I-Node und Indexblöcke des Dateisystes insgesamt mindestens? (Ignorieren Sie den Platz, der durch die Blockgruppenstruktur belegt wird). b) Wie lange dauert es für Festplatte und SSD mindestens, bis die gesuchten 10 Byte voliegen? Wie lange dauert es jeweils im schlechtesten Fall? ***** Musterlösung ***** Frage 1: a) 500 GiB / 4 KiB = 131 072 000 Einträge, pro Eintrag 4 Byte, 2 FATs (geht aus der Strucktur des Datenträgers hervor/ Redundante Auslegung der FAT nach dem Bootsektor), also 1 048 576 000 Byte = 1000 MiB. F1:a) ist für mich nachempfindbar. b) Muss 1GiB/4 KiB = 2^(18) = 262 144 FAT-Einträge lesen. Das ist auch noch verständlich, da die FAT diese Anzahl an FAT-Einträge braucht um die 1 GiB zu verwalten. Worst-Case: je Eintrag 1 Zugriff + Lesen von 512 Byte. Schon hier habe ich leichte verständnisprobleme. Gehe ich hier recht in der Annahme, dass das Dateisystem keine zusammenhängene Sektoren (Blöcke/Cluster) finden/bereitstellen kann und deshalb die 1 GiB große Datei auf Sektoren aufteilt, die keine räumliche Lokalität haben? Dann würde nämlich auch die nachfolgende Rechnung der Musterlösung Sinn machen. HDD_Max: 262 144 *(10 ms + 512/100 MB/s) = 43 min. SSD_Max = HDD_Max/10 = 4,3 min. Best-Case: Von den 128 Verweisen eines Sektors verweisen 127 auf einträge im gleichen Sektor. Welcher Sektor als nächstes geladen werden muss, kann das Betriebssystem erst wissen, wenn es den jeweils 128. Pointer ausgewertet hat! Kein Read-Ahead-Cache -> neuer zugriff => (1 Zugriff, 512 Byte = 128 Pointer lesen) * 2^(18-7) HDD_Min = 2048*10ms + 2^(20)Byte/ 100 MB/s = 20,48 s SSD_Min = HDD_Min/10 = 2 s. Ich hab es hier so abgeschrieben, wie es auch in der Musterlösung drinn steht. Ich verstehe nicht wirklich was da gemacht wurde. Wieso sollen 127 Verweise auf den gleichen Sektor zeigen? Wie soll das gehen? Ich dachte immer jeder FAT-Eintrag hat immer nur einen Verweis auf einen Block/Cluster? Und wie sich daraus nun der Rechenweg ergibt ist mir auch unklar. Vielleicht findet sich hier Jemand, der mir das erklären kann? Frage 2: a) Min. 1 Block mit dem inode der Datei + 1 indirekter Block +(1 doppeltindirekter Block + ceil(( 1 GiB - 48 Kib - 4 MiB)/4MiB) = 258 Blocks = 1 056 768 Byte. Min. 1 Block mit dem inode der Datei + 1 indirekter Block ergibt sich ja aus der Strucktur des Datenträgers für ext2, doch wie kommt man auf die restlichen Terme? b) liegt im doppelt indirekten erreichbaren Bereich -> inode + 2 Sektoren der indirekten Index-Blöcke (im Vorraus berechnbar welche) + Datensektor zu lesen. Also ohne Caches immer 4 *(Zugriff + 512 Byte lesen) HDD_Min = HDD_Max = 4*10,00512 ms = 40 ms. SSD_Min = SSD_Max = HDD_Max/10 Wie läßt sich hier berechnen, auf welche I-Nodes zugegriffen wird bei einer 1 GiB großen Datei? Ich wende mich nun ans Forum, weil mein Dozent unglücklicherweise krank ist und der Tag der Prüfung immer näher rückt. Ich bin euch für jeden Denkanstoß, den ihr mir geben könnt, echt dankbar. |
||||
|
|
|||||
| 05.10.2015, 19:01 | Auf diesen Beitrag antworten » | ||||
| eulerscheZahl | Hardwarefragen sind nicht mein Spezialgebiet, aber bevor gar keine Antwort kommt: 1b) Ja, es kann sein, dass die Datei fragmentiert vorliegt. Ein Sektor hat mehrere Blöcke, im Idealfall kann man mehrere Blöcke lesen, ohne den Sektor wechseln zu müssen. 2a) ? 2b) (nur Vermutung): Die ersten 12 Blöcke werden direkt referenziert (wikipedia). Über den einfach indirekten Verweis kommst du dann auf die Blöcke 13-24. Der doppelt indirekte Block liefert 25-168. Dann käme noch ein dreifach indirekter Block, aber bei der gegebenen Dateigröße tut es auch ein weiterer doppelt indirekter. |
||||
| 05.10.2015, 19:59 | Auf diesen Beitrag antworten » | ||||
| RoMa |
Ich finde es verwirrend wenn du sagst ein Sektor hat mehrere Blöcke, weil ich es in der Vorlesung genau umgekehrt gelernt habe.
Erst einmal danke, dass du bislang als Einziger geantwortet hast. Ich hab das alles selber einmal durchgerechnet und habe mich dabei an diesem Bild von Wikipedia gehalten. (ich darf keine URLs posten, aber ich meine das Bild welches man beim Artikel I-Node findet und den Aufbau eines I-Nodes darstellt. Das Dateisystem (DS) muss 1 GiB adressieren. Dazu kann es, nach dem ext2 System, erst einmnal 12 Datenblöcke (áka 4 KiB) über 12 direkte Verweise adressieren. Es bleiben dann 1 073 692 672 Byte übrig. Nun kann das DS einen einfach indirekten Verweis auf einen indirekten Block adressieren. Dieser Block ist 4 KiB groß, wodurch 1024 Einträge möglich. Bei einer Größe von 4 KiB pro Datenblock, lassen sich mit dem indirekten Block 4 194 304 Byte adressieren und von den 1 073 692 672 Byte müssen nur noch 1 069 498 368 Byte adressiert werden. Nun nutzt das DS einen Verweis auf einen doppelt indirekten Block. Ein doppelt indirekter Block hat ebenfalls 1024 Einträge, wobei jeder Eintrag wieder auf einen Block mit 1024 Einträgen verweist. Nun weiß ich, dass mit einem solchen Block genau 4 194 304 Byte adressieren werden können, somit brauche ich 1 069 498 368 Byte/4 194 304 Byte = 255 Blöcke um die restlichen Bytes zu adressieren. In der Summe habe ich also 255 Blöcke gebraucht, die von einem doppelt indirekten Block referenziert werden + einem einfach indirekten Block + einem Block, das die I-Node der Datei enthält. Also insgesamt 258 Blöcke. Ich hoffe immernoch, dass mir Jemand bei meinen anderen Fragen helfen kann. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |