Betriebssysteme 2, Sommersemester 2006

Aktuelles

• Eine Newsgroup ist eingerichtet: fb3/lv/bs2

Auf dieser Seite werden während des Semesters weiterführende Informationen sowie die jeweiligen Aufgabenzettel bereitgestellt. Wir bemühen uns, die Seite so aktuell wie möglich zu halten.

Dokumentation der Linux-Kernelquellen: Unter http://lxr.linux.no/source - Kernel-Source-Code Browser findet man einen sehr guten HTML-Browser für die Linux-Kernel Quellen. Nachdem die Startseite auf dem Bildschirm erschienen ist, muss oben rechts die gewünschte Version 2.6.10 selektiert werden.

gcc Compiler: Um die Kernelquellen korrekt übersetzen zu können, benötigt Ihr eine gcc-version 2.95.3 oder neuer - wir arbeiten hier mit gcc (GCC) 3.3.5.

Weitere Informationen zur Vorlesung:

• Überblick
• Veranstaltungsinhalte
• Literatur
• Aufgabenblätter

Überblick

Betriebssysteme 2 umfasst folgende Themen:

• Session 1: Der Weg durchs Betriebssystem
• Session 2: Linux-Kernel - Modifikation, Übersetzung, Installation
• Session 3: Der O(1) Scheduler im Linux Kernel 2.6
• Session 4: Faire Scheduler
• Session 5: Das virtuelle Dateisystem (Virtual File System VFS)
• Session 6: Second and Third Extended File Systems - ext2/ext3
• Session 7: Interrupts und Interrupt Handling
• Session 8: Treiberentwicklung unter Linux

Die Übungen vertiefen den Vorlesungsstoff durch praktische Anwendung der beschriebenen Konzepte.

Veranstaltungsinhalte

Session 1: Der Weg durchs Betriebssystem

• Definition von System-Calls (Datei include/asm-i386/unistd.h): Nummerierung der System-Calls - #define _syscallx()-Notation für die Konstruktion von System-Call Code (Funktionsdeklaration plus Funktionskörper) mit x=0,1,2,4,5,6 Parametern - Parameter(adress)übergabe in Registern - Auslösen des Traps (=Softwareinterrupt) 0x080 - Definition des Rückgabewertes.
• Zieladresse des Traps (Datei arch/i386/kernel/entry.S): Einsprungadresse ENTRY(system_call) - das Retten der Register auf dem Stack - Aufruf von sys_SystemCallName() über die Tabelle sys_call_table.
• Beispiel: Systemaufruf gettimeofday(2) - Kernel-Implementierung mittels sys_gettimeofday() und do_gettimeofday()
• Eigene System Calls mit neuem Trap registrieren - hierdurch vermeidet man den Konflikt zwischen des Systemaufrufnummern von Linux-Standardsystemaufrufen und den Nummern der eigenen Systemaufrufe.

Session 2: Linux-Kernel - Modifikation, Übersetzung, Installation

• Kernelquellen auspacken: Soft-Link des ausgepackten linux-2.6.10 Verzeichnisses nach /usr/src/linux legen.
• Ins Verzeichnis /usr/src/linux wechseln.
• Versionsnummer im Makefile registrieren, z.B. 2.6.10-bs2b.
• Kernel konfigurieren: make menuconfig - Hinweis: Je mehr Module konfiguriert sind, desto länger dauert der Generierungsvorgang. Es ist sinnvoll, die Konfiguration für die Lösung der BS2-Aufgaben so klein wie möglich zu halten.
• Kernel-Sources nach Bedarf modifizieren, siehe Beispiel des sehr einfachen neuen System Calls bs2_0: Das Anwendungsprogramm mit neuem System Call ist ex1.c. Die modifizierten Kernelquellen sind
  • unistd.h
  • entry.S
  • printk.c
In diesem Beispiel wird der neue Systemaufruf über den Standard-Trap aktiviert und in einer schon vorhandene Kernel-Datei implementiert.
• Wenn neue Dateien (z.B. unter kernel/)angelegt werden, müssen die zugehörigen Objektdateien im Makefile des Verzeichnisses eingetragen werden.
• Kernel-Patch zum Registrieren der BS2-Systemaufrufe mit eigenem Trap: bs2d.patch. Den Patch in das /usr/src/linux kopieren. Dann dort einspielen mit patch -p1 < bs2d.patch .
• Kernel übersetzen: make bzImage
• Modules übersetzen: make modules; make modules_install
• Kernel und System-Map in das /boot-Verzeichnis kopieren:
  • cp arch/i386/boot/bzImage /boot/vmlinuz-2.6.10-bs2b
  • cp System.map /boot/System.map-2.6.10-bs2b
• Neuen Kernel bei Grub registrieren - Eintrag in /boot/grub/menu.lst:
  ###Kommentar ....
title Vanilla 2.6.10-bs2b
kernel (hd0,5)/boot/vmlinuz-2.6.10-bs2b root=/dev/hda6 vga=791 splash=silent showopts

• Reboot unter Auswahl des neuen Kernels - hier hilft auch manchmal ein kleines Gebet ...

Session 3: Der O(1) Scheduler im Linux Kernel 2.6

• Als ergänzende Literatur zu den Kernel-Quellen sched.c, sched.h wird der Artikel Understanding the Linux 2.6.8.1 CPU Scheduler von Josh Aas empfohlen.

Session 4: Faire Scheduler

• Scheduler Runs, bestehend aus Paaren (E,i) mit E Menge der rechenbereiten Prozesse und i dem im aktuellen Scheduling Schritt selektierten Prozess.
• Stark und schwach faire Runs.
• Starke und schwache Fairness, sowie Universalität von Schedulern.
• CSP Spezifikation des universellen stark fairen Schedulers SCHED.
• Beweis der Universalität von SCHED.
• Beweis der starken Fairness von SCHED.
• Literaturhinweis: Als ergänzende Literatur zu den Definitionen, Beweisen und Beispielen der Vorlesung ist die Lektüre des Abschnitts 4.9, pp. 134 in [16] sehr empfohlen.

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.

  Achtung: Leider kann das Diagramm nur als Postscript-Datei zur Verfügung gestellt werden. Ihr seht es Euch am besten mit gv oder ggv im A3-Format an - dann lassen sich die Inhalte recht gut betrachten.

• 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.
  • 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
  Hinweis: Der Teill über bottom Halves ist kein Prüfungsstoff, weil wir aus bekannten Gründen in der letzten Vorlesung nicht mehr bis zu dieser Stelle vordringen konnten. Gehört aber eigentlich zum Wissen über Unterbrechungsbehandlung dazu.
• Als Literatur empfehlen wir [0; pp. 75-118]

Session 8: Treiberentwicklung unter Linux

• Als Literatur empfehlen wir [17]
• Framework für Linux Kernel Mdules, 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 Vorlesungsstoff vertiefen.

Aufgabenblätter