Universität Bremen  
  Universität Bremen FB3 TZI BISS  
  AG BS > Lehre > SoSe 2006 > Deutsch
English
 

Betriebssysteme 2, Sommersemester 2006

 

Aktuelles

  • Eine Newsgroup ist eingerichtet: fb3/lv/bs2

Vorlesung: 
Mo. 15-17 Uhr, GW2 B1400 Prof. Dr. Jan Peleska, ab 24.4.2006
Übung: 
Mi. 8-10 Uhr, MZH 5210 Prof. Dr. Jan Peleska, ab 26.4.2006


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.


Informationen:

Linux-Kernelquellen: Wir werden in diesem Semester als Grundlage für alle Aufgaben den Linux Vanilla-Kernel 2.6.10 verwenden. Die offizielle Quelle für Linux-Kernel Dateien ist
http://www.kernel.org. Alternativ könnt Ihr die Quellen direkt von unserem Server laden (sollte etwas schneller gehen): linux-2.6.10.tar.bz2.

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

Betriebssysteme 2 umfasst folgende Themen:

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
  • 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


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.

[0] Robert Love: Linux Kernel Development, Second Edition, Novell Press, Indianapolis, USA, 2005.
[1] M. Beck, H. Böme, M. Dziadzka, U. Kunitz, R. Magnus, C. Schröter, D. Verworrner: Linux Kernel-Programmierung -- Algorithmen und Strukturen der Version 2.2, 5. Auflage. Addison-Wesley, 1999
[2] D.P. Bovet, M. Cesati: Understanding the Linux kernel, 1st edition. O'Reilly & Associates, 2001
[3] U. Vahalia: Unix Internals - The New Frontiers, Prentice Hall 1996.
Dieses Buch geht zu den einzelnen Themenbereichen mehr in die Tiefe als Tanenbaum oder Stallings: Wenn diese beiden Bücher nicht mehr genug Details verraten, lohnt es sich, einen Blick in den Vahalia zu werfen.
[4] Wolfgang Maurer: Linux Kernelarchitektur. Konzepte, Strukturen und Algorithmen von Kernel 2.6, Hanser (2005).
siehe folgende WWW Referenz
[5] A. Tanenbaum: Modern Operating Systems, 2nd edition. Prentice Hall, 2001
[6] A. Tanenbaum: Moderne Betriebssysteme, Hanser 1995
[7] A. Tanenbaum, A. S. Woodhull: Operating Systems: Design and Implementation, 2nd edition. Prentice Hall, 1997.
Dies ist eine erweitere Fassung des 1. Teils von [5] bzw. [6].
[8] A. Tanenbaum: Distributed Operating Systems, Prentice Hall 1995.
Dies ist eine erweiterte und aktualisierte Fassung des 2. Teils von [5] bzw. [6].
[9] V. Toth: Programming Windows 98/NT Unleashed, Sams Publishing, 1998.
Eine umfangreicher Überblick über die Systemprogrammierung unter Windows 98 und Windows NT inkl. CD-ROM mit Beispielen.
[10] W. Stallings: Operating Systems - Internals and Design Principles, Prentice Hall 1998.
Diese Buch ist eine Alternative zu den Büchern von Tanenbaum. Es werden ebenfalls alle wichtigen Standardthemen, auch in bezug auf verteilte Systeme, behandelt.
[11] W.R. Stevens: Unix Network Programming, Prentice Hall 1990.
Eine sehr detaillierte Einführung in die Systemprogrammierung unter UNIX anhand ausführlicher Beispiele. Insbesondere wird auf die Standard Internet Protokolle eingegangen sowie auf Interprozesskommunikationsmechanismen aber auch Remote Login sowie RPCs werden behandelt. Inzwischen gibt es eine überarbeitete zweibändige Ausgabe von 1998.
[12] C.A.R. Hoare: Communicating Sequential Processes, Prentice Hall 1985.
Das Standardwerk zu CSP.
[13] A.W. Roscoe: The Practice and Theory of Concurrency, Prentice Hall 1998.
Eine modernisierte Einführung in CSP und FDR.
[14] J. Peleska: Formal Methods and the Development of Dependable Systems, Christian-Albrechts-Universität zu Kiel 1996.
In dieser Habilitationsschrift befindet sich u. a. die Spezifikation d er HP-UX Access Control Lists (S. 149ff). Eine Postscript-Version liegt zum Download lokal auf den Seiten der Universität Bremen.
[15] S. Maxwell: Linux Core Kernel Commentary, The Coriolis Group, 1999
Kernel-Kommentierungen
[16] K. R. Apt and E.-R. Olderog: Verification of Sequential and Concurrent Programs., Springer-Verlag, Berlin Heidelberg New York (1991)
Definition des Fairness-Begriffs und Beweis der Eigenschaften des universell stark fairen Schedulers.
[17] J. Corbert, A. Rubini and G. Kroah-Hartman: Linux Device Drivers, 3rd Edition., O'Reilly (2005)
Alles was man über die Entwicklung von Linux Treibern unter Kernel 2.6 wissen muss. Das Buch ist unter http://www.oreilly.com/catalog/linuxdrive3/book/index.csp online verfügbar.


Aufgabenblätter



Aufgabenzettel Abgabe
blatt1.pdf 10.05.2006 in der Übung
blatt2.pdf 24.05.2006 in der Übung
blatt3.pdf 07.06.2006 in der Übung
blatt4.pdf 12.07.2006 in der Übung
 
   
Autor: jp
 
  AG Betriebssysteme, Verteilte Systeme 
Zuletzt geändert am: 2. November 2022   Impressum