Add Thesis

Implementation eines FAT-Treibers für das Lehrbetriebssystem ULIX

Written by Simon Brugger

Paper category

Bachelor Thesis

Subject

Computer Science

Year

2016

Abstract

Bachelorarbeit: FAT-Dateisystem Das FAT-Dateisystem entstand in den späten 1970er und frühen 1980er Jahren. Es wurde von Microsoft für das Betriebssystem MS-DOS entwickelt (siehe Microsoft, 2000, S. 1). Im Laufe der Jahre ist das gesamte FAT-System in der Dateisystemfamilie aufgetaucht, mit verschiedenen Ableitungen und Erweiterungen. Das NTFS-Dateisystem wurde von Microsoft mit Windows NT 3.1 eingeführt und gilt als Nachfolger des FAT-Dateisystems. Obwohl FAT kein Standard mehr ist, wird FAT von einer Vielzahl von Betriebssystemen unterstützt und ist in eingebetteten Systemen wie MP3-Playern, Digitalkameras und USB-Sticks weit verbreitet (vgl. Tanenbaum, 2009, S. 383). Die Gründe sind die Robustheit, relative Einfachheit und einfache Implementierung des FAT-Dateisystems (siehe Microsoft, 2010b). Das Grundkonzept des FAT-Dateisystems basiert auf der Tatsache, dass Dateien und Verzeichnisse durch Datenstrukturen repräsentiert werden, die als Verzeichniseinträge bezeichnet werden. Verzeichniseinträge enthalten Informationen wie den Namen, die Dateigröße, den ersten Startcluster der Datei und andere Metainformationen. Der Inhalt der Datei wird in derselben Einheit, dem sogenannten Cluster, gespeichert. Ein Verzeichnis oder eine Datei kann einen oder mehrere Cluster belegen. Die Beziehung zwischen Verzeichniseinträgen und Inhalt wird durch die dritte Datenstruktur FAT definiert. Alle zu einer Datei gehörenden Cluster können durch FAT identifiziert werden (vgl. Carrier, 2005, S. 156-157). Auch wenn das FAT-Dateisystem robust und einfach ist, hat dieses Konzept seine Nachteile. Das Schreiben und Löschen von Dateien führt zur Besetzung neuer Cluster, die nicht kontinuierlich geschrieben werden. Dies kann zu einer Fragmentierung des Dateisystems führen. Fragmentierung hat einen großen Einfluss auf die Leistung. Beim sequentiellen Lesen von Dateien wird die Clusterkette von Anfang bis Ende durchlaufen. Wird ein einzelner Cluster auf dem Datenträger verteilt, sind mehrere Plattenkopfbewegungen erforderlich (vgl. Friedman & Pentakalos, 2002, S. 423) Ein weiteres Problem ist die interne Fragmentierung. Die kleinste adressierbare Einheit des FAT-Dateisystems ist der Cluster. Wenn die Datei nicht den gesamten Cluster belegt, führt dies zu verschwendetem Speicherverbrauch. Zum Beispiel belegt eine 65 KB große Datei, die sich auf einer 3 GB FAT16-Partition mit einer Clustergröße von 64 KB befindet, zwei Cluster, sodass 63 KB ungenutzt bleiben (siehe Friedman & Pentakalos, 2002, Seite 424). 2.2 FAT-Varianten Das FAT-Dateisystem unterteilt sich grundsätzlich in drei verschiedene Varianten: FAT12, FAT16 und FAT32. Allen Versionen gemeinsam ist, dass sie FAT verwenden, um Daten zu organisieren und zu verwalten. FAT ist der Kern des Dateisystems und kann auch mehrfach auf dem Dateisystem gespeichert werden. Das Arbeitsprinzip des FAT-Dateisystems ist die Kettenzuordnung. 3.1 Anforderungen an den FAT-Dateisystemtreiber Zunächst werden die grundlegenden Anforderungen an den FAT-Dateisystemtreiber grob definiert. UC ist gut geeignet, diese Anforderungen zu definieren. UC fasst das Verhalten des Systems unter definierten Szenarien als Reaktion auf Teilnehmeranfragen zusammen. UC beschreibt, was während der Interaktion zwischen Teilnehmern und dem System passiert, um Ziele zu erreichen. Unabhängig von der konkreten technischen Umsetzung (vgl. Cockburn, 2001, S. 1) 3.1.1. UC: Dateien öffnen und schließen Beschreibung Um das Dateisystem nutzen zu können, muss der Treiber Dateien öffnen und schließen können. ActorUser.PreconditionsNone.Experience1. Der Benutzer ruft im Benutzermodus die Funktion open() auf. 2. Prüfen Sie, ob die Datei schreibgeschützt ist. 3. 4. Erstellen Sie einen Dateideskriptor und einen Inode. 5. Dateideskriptor zurückgeben Der Benutzer ruft im Benutzermodus die Funktion close() auf 6. Löschen Sie den Dateideskriptor und den Inode. Bedingung 1. Verwenden Sie für bereits geöffnete Dateien den neuen Deskriptor, um den vorhandenen Inode zu verknüpfen. 2. Wenn Sie mehrere Dateien geöffnet haben, löschen Sie bitte den Inode nicht, bevor die letzte Datei geschlossen wurde. Alternatives Verfahren: Keine. Das Öffnen einer Datei ist keine triviale Angelegenheit. Das Flussdiagramm in Abbildung 3.1 veranschaulicht diesen Prozess detaillierter. Wie in Kapitel 3.4 erwähnt, kennt FAT das Konzept der Inodes nicht. Aus diesem Grund werden Inodes zur Laufzeit generiert. Außerdem müssen die Dateiattribute des Verzeichniseintrags berücksichtigt werden. Sie dürfen eine schreibgeschützte Datei nicht zum Schreiben öffnen. Beim Anlegen eines neuen Deskriptors müssen Sie prüfen, ob die Datei bereits geöffnet ist. Ist dies der Fall, muss der Inode der geöffneten Datei dem neuen Deskriptor zugeordnet werden. Diese Implementierung basiert auf den Einschränkungen von Minix. Das bedeutet, dass bis zu 256 Deskriptoren und Inodes gleichzeitig verwendet werden können. Es können keine Deskriptoren und Inodes mehr erstellt werden. 3.1.2 UC: Synchroner Dateizugriff Beschreibung Eine Datei kann mehrfach geöffnet werden. Der Treiber muss gleichzeitig Lese-/Schreibzugriffe verarbeiten können. ActorUser.PreconditionsFile wurde zweimal geöffnet. Sequenz1. Der Benutzer ruft die allgemeine Funktion lseek() auf und definiert die Lese-/Schreibposition des ersten Dateideskriptors A.2. Der Benutzer ruft die allgemeine Funktion lseek() auf und definiert die Lese-/Schreibposition B.3 für den zweiten Dateideskriptor. Der Benutzer verwendet dann zwei Dateideskriptoren, um in die Datei zu schreiben. 4. Die Daten des ersten Dateideskriptors werden an Position A platziert und die Daten des zweiten Dateideskriptors werden an Position B platziert.BedingungKeine.Alternative ProzesseKeine. Read Less