Betriebssysteme 2, Sommersemester 2007

Aktuelles

Termine

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. 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 (Datei arch/i386/kernel/syscall_table.S).
• Für das Kopieren von Datenbereichen, die im Systemaufruf über Funktionszeiger identifiziert werden: copy_to_user() kopiert aus dem Kernelspace in den Userspace. copy_from_user() kopiert aus dem Userspace in den Kernelspace.
• Beispiel: Systemaufruf gettimeofday(2) - Kernel-Implementierung mittels sys_gettimeofday() (Datei kernel/time.c). Hierzu weitere interessante Dateien:
  • kernel/timer.c: Funktionen void do_gettimeofday() und __get_realtime_clock_ts() und __get_nsec_offset().
  • include/linux/clocksource.h: Funktion static inline cycle_t clocksource_read() verweist über Funktionspointer auf die HW-abhängige Methode zum Lesen der Mikrosekunden-Zeiteinheiten.
  • arch/i386/kernel/tsc.c: Realisierung der Zeitabfrage über das Time Stamp Counter Register (TSC), siehe static struct clocksource clocksource_tsc und static cycle_t read_tsc() und static int __init init_tsc_clocksource().
  • include/asm-i386/msr.h: Definition des Assemblermakros rdtsc(), welches das TSC-Register ausliest.
• 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

• Linux Kernel 2.6.20.1 herunterladen
• Kernelquellen auspacken: als normaler User im eigenen Home-Verzeichnis
• Ins Verzeichnis linux-2.6.20.1 wechseln.
• Versionsnummer modifizieren, z.B. echo -bs2 > localversion-bs2.
• Kernel konfigurieren: make xconfig - 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
  • include/asm-i386/unistd.h
  • arch/i386/kernel/syscall_table.S
  • kernel/bs2.c
  • kernel/Makefile
In diesem Beispiel wird der neue Systemaufruf über den Standard-Trap aktiviert und in einer neuen Datei implementiert, die zum Kernel hinzugelinkt wird.
• Wenn neue Dateien (z.B. unter kernel/)angelegt werden, müssen die zugehörigen Objektdateien im Makefile des Verzeichnisses eingetragen werden.
• Kernel übersetzen: make
• als root: Modules installieren: make modules_install
• als root: Kernel installieren: make install
  Wenn man kein zu exotisches System hat, passiert an dieser Stelle automatisch das Richtige, nämlich das Kopieren von arch/i386/boot/bzImage nach /boot, ggf. das Anlegen einer initrd und das Erstellen eines neuen Eintrags in /boot/grub/menu.lst. Auf jeden Fall sollte dies noch einmal von Hand kontrolliert werden.
• Reboot unter Auswahl des neuen Kernels - hier hilft auch manchmal ein kleines Gebet ...
• Kernel-Patch zum Registrieren der BS2-Systemaufrufe mit eigenem Trap: bs2d.patch. Den Patch in das linux-2.6.20.1-Verzeichnis kopieren. Dann dort einspielen mit patch -p1 < bs2d.patch .
• Hilfreicher Link: Cross-Referencing Linux

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 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 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 Vorlesungstoff vertiefen.

Aufgabenblätter