Betriebssysteme 2, Sommersemester 2009

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: Scheduler Hierarchie und Completely Fair Scheduler im Kernel 2.6.29
• 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

• System-Call Wrapper für den Einsprung in den Kernel: Makros _syscallx() mit x=0,1,2,4,5,6 in der unistd.h für die Konstruktion von System-Call Wrappern (Funktionsdeklaration plus Funktionskörper). Parameter(adress)übergabe in Registern. Spezifizierung des Systemcalls über das EAX-Register. Auslösen des Traps (=Softwareinterrupt) 0x80. Setzen von errno. Definition des Rückgabewertes. Prozessorinstruktionen SYSENTER/SYSEXIT als Alternative zum Interrupt.
  Hinweis: In neueren Kernelversionen gibt es die unistd.h nicht mehr. Stattdessen befinden sich entsprechende Makros in den C-Libraries (siehe sysdep.h aus der GNU C-Library 2.9)
• Einstiegspunkt im Kernel (Datei arch/x86/kernel/entry_32.S): Einsprungadressen ENTRY(system_call) für Interrupt 0x80 und ENTRY(ia32_sysenter_target) für die SYSENTER-Instruktion. Retten der Register auf dem Stack. Aufruf von sys_SystemCallName() über die Tabelle sys_call_table (Datei arch/x86/kernel/syscall_table_32.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 getnstimeofday().
  • 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 rdtscll(), welches das TSC-Register ausliest.
• Das aktuelle System Call Interface (SCI) von glibc und Linux unter Nutzung der Intel Instruktionen sysenter, sysexit (verfügbar etwa ab Kernel 2.6.20)

Hintergrundlektüre: Kernel command using Linux system calls von M. Tim Jones

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

• Linux Kernel 2.6.29.1 herunterladen.
• Kernelquellen auspacken: als normaler User im eigenen Home-Verzeichnis
• Ins Verzeichnis linux-2.6.29.1 wechseln.
• Versionsnummer modifizieren, z.B. echo -bs2 > localversion-bs2.
• Konfiguration, Übersetzung, Installation und weitere Aktionen mit make. Ein Überblick verschafft make help.
  Hinweis: Eventuell muss muss die Zielarchitektur mit ARCH=... angegeben werden (zum Beispiel: make ARCH=i386 menuconfig)
• Übernahme einer bestehenden .config-Kernelkonfigurationsdatei mit make oldconfig
• Kernel konfigurieren: make menuconfig
  Hinweis: Je mehr Features 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. Sollen Teile des Kernels als Modul kompiliert werden, die jedoch zum Booten benötigt werden ist eine Init-Ramdisk nötig.
• Kernel-Sources nach Bedarf modifizieren.
• 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: Kernel-Module installieren: make modules_install . Die Module landen dann in der Regel unter /lib/modules/.
• als root: Kernel installieren: make install
  Hierdurch wird unter anderem das komprimierte Kernel-Image von arch/i386/boot/bzImage nach /boot kopiert. Ggf. ist auch noch per Hand das Anlegen einer Init-Ramdisk und das Erstellen eines neuen Eintrags in /boot/grub/menu.lst nötig. Auf jeden Fall sollte alles noch einmal kontrolliert werden.
• Reboot unter Auswahl des neuen Kernels - hier hilft auch manchmal ein kleines Gebet ...
• Um häufige Reboots zu vermeiden, ist der Emulator qemu nützlich.
  • Zur Konfiguration des Kernels für qemu kann die Datei .config übernommen werden.
  • Zum Starten eines selbstgebauten Kernels kann dieses Makefile genutzt werden.
    Das Makefile lädt automatisch ein vorinstalliertes Debian-Linux aus dem Netz und startet euren Kernel mit diesem System. Hierzu muss sich der übersetzte Kernel im Verzeichnis kernel/ befinden.
    Nützliche Makefile-Targets sind:
    • make run-kernel: Starten des Systems mit dem von euch gebauten Kernel.
    • make debug-kernel: Starten des Systems mit dem von euch gebauten Kernel, so dass er mit dem gdb debuggt werden kann.
    • make linux: Starten des Systems mit dem vorinstallierten Debian Linux-Kernel.

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

• Datenstrukturen: Runqueue mit active und expired Arrays
• Einsprungpunkte für das Scheduling:
  • scheduler_tick(): Aufgerufen vom Timer Interrupt und von do_fork()
  • schedule(): Wird aufgerufen, wann immer Kernel-Code entscheidet, dass der zugehörige Prozess schlafen muss, sowie immer wenn Task Preemption stattfinden soll.
  • sched_fork(): Wird f&uumöl;r einen neu erzeugten Kindprozess aufgerufen.
• 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, ausserdem [0], Kapitel 4.

Session 4: Scheduler Hierarchie und Completely Fair Scheduler im Kernel 2.6.29

• Scheduler Klassen und die struct sched_class Struktur mit ihren vorgegebenen Funktionen, die von jeder Klasse zu implementieren sind.
• Das Konzept der virtuellen Laufzeit (virtual runtime) die zwischen den rechenbereiten Prozessen fair ausgeglichen wird.
• O(1)-Eigenschaft des RT-Schedulers (sched_rt.c) für die Klassen SCHED_FIFO und SCHED_RR.
• Scheduling Gruppen, um Fairness zwischen Gruppen von Prozessen zu realisieren

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 Kleinschribung 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&öuml;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.

• 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

• Übungsblatt 1, Abgabe am 05.05.2009
  hierzu sysdep.h zur Generierung der Systemcall-Wrapper im Userspace
• Übungsblatt 2, Abgabe am 26.05.2009
• Übungsblatt 3, Abgabe am 30.06.2009 [Makefile] [Hinweise]