Betriebssysteme 2, Sommersemester 2010

• Binärer Baum mit Knotenmarkierung rot/schwarz
• Nutzt Parent-, Left-, Right-Pointer, die auf NIL zeigen, falls kein "echter" Parent-, Left-, Right-Knoten mehr existiert.
• Garantiert einen Grad von Balancierung, der allerdings schwächer ist als derjenige von AVL-Bäumen: Bei Rot-Schwarz-Bäumen ist kein Pfad von der Wurzel zum Blatt mehr als doppelt so lang wie ein anderer.
• Dieser Grad von Balancierung wird durch Einhaltung der Rot-Schwarz-Eigenschaften beim Einfügen und Löschen erreicht:
  • Jeder Knoten ist rot oder schwarz
  • Jedes NIL-Blatt ist schwarz
  • Wenn ein Knoten rot ist, dann sind alle seine Kinder schwarz
  • Für jeden Knoten n gilt: Jeder von n ausgehende Pfad, der erst bei einem NIL-Blatt endet, besitzt dieselbe Anzahl schwarzer Knoten.
• Rot-Schwarz-Bäume mit k Knoten haben eine maximale Höhe von 2lg(k+1).
• Zum Einfügen und Löschen werden die üblichen Algorithmen für binäre Bäume verwendet. Danach muss aber ggf. der Baum neu balanciert werden, um die Rot-Schwarz-Eigenschaften wieder herzustellen. Dies erfolgt mit Hilfe von Links- und Rechts-Rotationen, sowie durch Umfärbung von Knoten.
• Siehe Pseudocode für Rot-Schwarz Einfügen und [18; pp. 263].

Beispiel aus dem Tutorium für eine einfache Scheduling-Klasse.

Session 5: Das virtuelle Dateisystem (Virtual File System VFS)

• Das folgende Klassendiagramm zum VFS stellt die Zusammenhänge zwischen den Datenstrukturen her, die beim Ausführen eines auf Dateien oder Verzeichnissen operierenden Systemaufrufs ausgewertet bzw. erzeugt werden - vom Prozesstabelleneintrag des aufrufenden Prozesses bis zur die Datei/das Verzeichnis repräsentierenden Inode-Instanz im Kernel.
• Die vier Unix-Abstraktionen in Bezug auf Dateisysteme: Dateien, Verzeichnisse, Inodes, Mount Points
• Die primären Objekttypen des VFS:
  • Superblock Objekt (struct super_block) - repräsentiert ein Dateisystem nach dem Mount.

    Die zugehörigen Operationen werden aus dem Superblock-Objekt via Referenz auf eine Instanz von struct super_operations entnommen. Diese Operationen unterstützen alle Aktivitäten, welche das gesamte Dateisystem betreffen, z.B.: Zurückschreiben des Superblocks auf die Platte (write_super()), Initialisieren eines neuen Inodes bei Erzeugung einer neuen Datei/eines neuen Verzeichnisses in diesem Dateisystem (alloc_inode()), Zurückschreiben aller im Kernel vorhandenen geänderten Daten (Superblock, Dateien oder Verzeichnisse mit Inodes und Nutzdaten) des Dateisystems auf die Platte (sync_fs()). Die Operationen lassen sich in solche einteilen, die nur auf die Dateisystemrepräsentation im Kernel einwirken (z.B. alloc_inode(),put_inode() [Inode wird im Kernel freigegeben]) und solche, die auf das Dateisystem auf der Platte einwirken (z.B. sync_fs(), delete_inode()[Inode wird im Dateisystem auf der Platte gelöscht]). Das Superblock Objekt und die Superblock-Operationen sind in include/linux/fs.h deklariert.

  • Inode Objekt (struct inode) - repräsentiert eine Datei. Verzeichnisse sind unter Unix spezielle Dateien, daher wird auch ein Directory über einen Inode repräsentiert.

    Die auf dem Inode wirkenden Operationen werden über eine Referenz auf eine Dateisystemtyp-spezifische Instanz von struct inode_operations gefunden. Inode-Operationen betreffen immer die ganze Datei (nie den Dateiinhalt), z.B. Öffnen/neu Anlegen der Datei in einem vorgegebenen Verzeichnis, Erzeugen und Löschen von harten und symbolischen Links, Umbenennen. Das Inode Objekt und die Inode-Operationen sind in include/linux/fs.h deklariert.

  • Dentry Objekt - repräsentiert einen Verzeichniseintrag, genauer, einen Pfadabschnitt, der ein Verzeichnis oder eine Datei in einem Verzeichnis repräsentiert.

    Auch Mount-Points werden durch Dentry-Objekte repräsentiert. Im Pfad /mnt/d1/d2/file1.txt werden /, mnt, d1, d2, file1.txt im Kernel durch jeweils ein Dentry-Objekt repräsentiert. Die auf einem Dentry-Objekt wirkenden Operationen werden über eine Referenz auf eine Instanz von struct dentry_operations gefunden. Die Operationen ermöglichen beispielsweise das Vergleichen von Verzeichnis- oder Dateinamen (wichtig z.B. für Dateisysteme, bei denen Groß- und Kleinschreibung nicht unterschieden wird), sowie das Löschen eines Verzeichniseintrags (was gleichzeitig das zugehörige Dentry-Objekt invalidiert. Dentry-Objekte haben keine direkte Entsprechung im Dateisystem auf der Platte: Dort ist die Beziehung zwischen Verzeichnissen und Unterverzeichnissen oder Dateien in den Nutzdaten der Verzeichnisse repräsentierenden Dateien codiert. Dentry-Objekte werden in einem Kernel-Cache gehalten, um schnelle Pfadauflösungen zu ermöglichen. Das Dentry Objekt und die Dentry-Operationen sind in include/linux/dcache.h deklariert.

  • File Objekt - repräsentiert eine mit einem Prozess assoziierte geöffnete Datei.

    Die zum File-Objekt gehörigen Operationen sind in struct file_operations zusammegefasst. Sie unterstützen alle Aktivitäten, die den Dateiinhalt betreffen, auf welchen ein Prozess zugreift. Beispiele sind llseek() (Positionieren des Lese-/Schreibzeigers), read(), write(). Das File Objekt und die IFile-Operationen sind in include/linux/fs.h deklariert.

• Dateisysteme sind typischerweise in Kernel-Modulen implementiert. Die __init()-Funktion eines solchen Moduls ruft den Kernel-Dienst int register_filesystem(struct file_system_type * fs) (filesystems.c) auf und übergibt dabei die Adresse einer ausgefüllten file_system_type-Struktur (fs.h). Unter den Komponenten dieser Struktur befindet sich der Funktionszeiger auf die get-superblock Funktion
  int (*get_sb) (struct file_system_type *, int, const char *, void *, struct vfsmount *);
  welche jedes Dateisystem mit dieser Signatur anbieten muss, damit Mounts auf Instanzen dieses Dateisystems durchgeführt werden können.
• Die konkrete Instanz eines Dateisystems nach dem Mount-Vorgang wird im Kernel durch die Struktur struct vfsmount (mount.h) repräsentiert.
• Als ergänzende Literatur sind die unten angegebenen Bücher [3] (gibt einen sehr guten Überblick der zu Grunde liegenden Konzepte des VFS; die Darstellung ist von Linux unabhängig und bezieht sich auf Unix im Allgemeinen) und[0,1,2] (Linux-spezifische Details) zu empfehlen.

Session 6: Second and Third Extended File Systems - ext2/ext3

• Die Struktur von Ext2 Plattenpartitionen: Sonderrolle des Bootblocks - Blockgruppen - Blockgruppenaufteilung in Superblock, Blockgruppendeskriptor, Datenblock-Bitmap, Inode-Bitmap, Inode-Tabelle, Datenböcke - Inode Struktur - Codierung von Directory-Inhalten in den Datenblöcken der Directory-Files.
• Journalling im Ext3 Filesystem Die 3 journalling modes
  • Writeback: Nur die Metadaten kommen ins Log. Damit können Nutzdaten abgeschlossener write()-Operationen nach einem Crash verloren sein, aber die Konsistenz des Dateisystems nach der Recovery (=Einspielen offener Transaktionen aus dem Journal in die Partition) ist gesichert.
  • Ordered: Das Commit für die Metadaten im Journal wird erst gegeben, nachdem die Nutzdaten auf die Disk geschrieben wurden. Dadurch sind vor einem Crash vergrösserte Dateilängen nur dann nach der Recovery sichtbar, wenn auch der korrekte Dateninhalt am Dateiende eingetragen ist. Write()-Operationen, die innerhalb einer Datei stattfinden, ohne ihre Länge zu verändern, können genau wie beim Writeback-Mode bei einem Crash verloren gehen bzw. zu einem inkonsistenten Zustand der Nutzdaten führen, wenn vor dem Crash nur ein Teil der Aktualisierung tatsächlich auf den Nutzdaten in der Partition realisiert wurde.
  • Journal: Metadaten und Nutzdaten werden ins Log geschrieben, so dass sowohl das Dateisystem konsistent bleibt, als auch alle abgeschlossenen write()-Operationen nach einem Crash rekonstruierbar sind.
• Vergleich des Ext3-Journalling mit Logging und Transaktionsmanagement bei Datenbanksystemen

• Als Literatur empfehlen wir [2; pp. 495] und [4]

Session 7: Interrupts und Interrupt Handling

• Nebenbemerkungen:
  • direkter Zugriff auf Hardware-Devices, ihre Register (I/O Ports) und ggf. ihren zusätzliche Speicher (I/O Memory) mittels
    outb(), inb(), outw(), inw(), outl(), inl()
  • Polling versus Interrupts
  • Betrieb von Interface Devices ohne Interrupt Handling durch (1) zyklisches Auslesen der Statusregister und ggf. nachfolgenden Lese-/Schreibaufträgen an das Device, (2) DMA Devices ohne Interrupterzeugung, (3) Dual-ported RAM Devices
• Synchrone Interrupts (Traps und Exceptions)
• Asynchrone Interrupts - von externen Devices erzeugt
• Vom HW-Interrupt bis zum Interrupt Handler: Interrupt am Device - Interrupt Controller - Interrupt lines zur CPU - do_IRQ()-Schnittstelle - Interrupt Vector - Interrupt Handler (= Interrupt Service Routine ISR, Top-Half) - Monitoring über /proc/interrupts
• Registrierung von Interrupt Handlern durch Device Driver
• ISR Interface
• ISR Context im neuen Linux vom Prozesscontext verschieden - insbesondre mit eigenem Stack
• Shared IRQs von Devices, welche die selbe Interrupt Line benutzen, Identifikation der zuständigen ISR
• Sperren/Freigeben von Interrupts
• Reentrant ISR sind unter Linux nicht erforderlich
• Kernel Entropy Pool und der Beitrag von Interrupts zur Erzeugung "echter" Zufallszahlen
• Bottom-halves zur Entlastung des Interrupt Handlers durch Verlagerung nicht zeitkritischer Aktivitäten in
  • Softirqs,
  • Taskletts,
  • Work Queues
• Als Literatur empfehlen wir [0; pp. 75-118]

Session 8: Treiberentwicklung unter Linux

• Als Literatur empfehlen wir [17]
• Framework für Linux Kernel Modules, die Treiber realisieren, siehe [17; Chapter 2].
• Klassifikation der Treiber in Character/Block/Network Device Drivers
• Major/Minor Numbers zur Identifikation von Treibern und den zugeordneten Hardwareschnittstellen (anwendbar für Character und Block Devices) - dynamische Vergabe der Major/Minor Numbers - Zuordnung über /proc/devices. Siehe [17; Chapter 3]
• Die Realisierung von Treiberoperationen als Ausprägungen des virtuellen Dateisystems - Herstellung der Verbindung zwischen API-Aufruf (z.B. read(), write()) und Treiberfunktionen über File Structure, File Operations, Inode Structure - Kombination der (Treiber,Device)-spezifischen Zustandsdaten mit den Standardinformationen über Treiber, welche im Inode abgelegt werden (Devicenummer dev_t i_rdev; und Kernel-Datenstrukturen für (Character-) Devices struct cdev cdev;) - Standard-Entwurfsmuster für open(), read(), write(). Siehe [17; Chapter 3]
• Das Beispiel eines Character Device Drivers ohne echten Hardware-Zugriff (Beispiel 'Scull' aus [17]) ist unter scull.tgz zu finden. Diese Beispiel erläutert das zugrunde liegende Framework für Linux Character Device Driver auf hervorragende Weise.

Literatur

Für die Lehrveranstaltung sind die folgenden Literaturangaben relevant, wobei speziell [0], [1], [2], [3] und [4] den Vorlesungstoff vertiefen.

Aufgabenblätter

• Übungsblatt 1, Abgabe am 11.05.2010
  hierzu sysdep.h zur Generierung der Systemcall-Wrapper im Userspace
• Übungsblatt 2, Abgabe am 18.05.2010
• Übungsblatt 3, Abgabe am 08.06.2010
• Übungsblatt 4, Abgabe am 29.06.2010 [Makefile] [Hinweise]