Scheduling: Theorie und Praxis am Linux Kernel 2.6

Inhaltsverzeichnis

Vorwort

Kapitel 1: Einleitung in Kernel und Scheduler

Kapitel 2: Kernel-Architekturen

Kapitel 3: Scheduling-Modelle
3.1: FIFO-Scheduling
3.2: RR-Scheduling
3.2.1: Präemptives und nicht-präemptives Scheduling
3.2.2: Timeslices
3.2.3: Prozessdeskriptoren
3.2.4: Prozesszustände und die Waitqueue
3.2.5: Ereignis-basierte Waitqueues
3.3: Prioritäten-basiertes Scheduling

Kapitel 4: Interrupts
4.1: Definition eines Interrupts
4.2: Präemptive und nicht-präemptive Kernel-Architekturen

Kapitel 5: Scheduling in Linux
5.1: Einführung in das Schedulingverfahren des Linux-Kernels
5.2: Epochen-Modell
5.3: Echtzeitprozesse
5.3.1: Schedulingverfahren von Echtzeitprozessen
5.4: Normale Prozesse
5.4.1: Nice-Level
5.4.2: IO-Bonus
5.4.3: Berechnung der Prioritätsklasse
5.4.4: Berechnung der Timeslices
5.5: Goodness

Fazit

Bildverzeichnis

Literaturverzeichnis

Vorwort

In der heutigen Zeit ist es für Computer unabdingbar, mehrere Aufgaben gleichzeitig zu bearbeiten. Die CPU (Central Processing Unit) verarbeitet nacheinander Instruktionen und bearbeitet somit diese Aufgaben. Hierbei ist insbesondere das „nacheinander“ zu betonen, da eine einzelne CPU nicht mehrere Instruktionen gleichzeitig ausführen kann und lediglich durch einen schnellen Wechsel zwischen den Aufgaben (Prozessen) Parallelität vorgaukelt. Diese Wechsel werden durch ein Verwaltungssystem organisiert, welche die Laufzeit aufteilt, sodass sich verschiedene Aufgaben bei der Nutzung der CPU abwechseln. Dieses System ist, wie sämtliche die Hardware betreffende Verwaltungsaufgaben, ein Teil des Kernels und wird Scheduler genannt.

Diese Facharbeit wird verschiedene Scheduling-Algorithmen und die Implementation des LinuxKernels 2.6 erläutern. Zur Vereinfachung beziehen sich sämtliche Modelle auf Einprozessorsysteme, sofern nicht explizit auf die Verwendung des Modells bei Mehrprozessorsystemen hingewiesen wird.

Kapitel 1: Einleitung in Kernel und Scheduler

Zuerst ist es wichtig zu klären, was genau eigentlich der Kernel ist, wie dieser mit dem Scheduler zusammenhängt und welche Funktionalität geboten ist.

In erster Linie ist der Kernel als Teil des Betriebssystems und Abstraktionslevel der Hardware zu sehen. Somit stellt der Kernel die Schnittstelle zwischen einem Nutzer, der mit dem Betriebssystem agiert (und dabei bereitgestellte Funktionen des Kernels aufruft) und der Hardware, welche die Instruktionen ausführt bzw. die Aufgaben bearbeitet, dar.

Dazu gehört die Verwaltung von Festplattenspeicher, Arbeitsspeicher, Grafikspeicher, die Kommunikation mit Eingabegeräten (z.B. Tastaturen) und eben auch der CPU. Der Scheduler ist für die Verwaltung der zur Verfügung stehenden CPU-Zeit zuständig, genauer gesagt bestimmt er, wann welcher Prozess die CPU nutzen darf, und organisiert die bestehenden Prozesse in doppelt verketteten Listen (siehe Abb. 1.1).

Desweiteren wird durch den Kernel zwischen zwei Privileg-Stufen unterschieden:

- User-Mode
- Kernel-Mode

Anweisungen, die im User-Mode ausgeführt werden, sind nicht befugt, direkt auf die Hardware zuzugreifen oder Teile des Betriebssystems aufzurufen, sondern müssen diese Aufrufe von gesicherten Funktionen des Kernels aus erfolgen, weil es sehr schnell Konflikte mit der Hardware geben kann, wenn die Prozesse direkt darauf zugreifen, z.B. wenn 2 Prozesse gleichzeitig versuchen, Daten auf die Festplatte zu schreiben:

- Prozess 1 bewegt den Festplatten-Kopf auf seine zu beschreibende Adresse
- Prozess 2 bewegt den Festplatten-Kopf auf seine Adresse
- Prozess 1 schreibt seine Daten auf die Festplatte
- Prozess 2 überschreibt die Daten von Prozess 1

Somit ist es unabdingbar, dass solche Zugriffe für wechselseitigen Ausschluss gesichert sind und über den Betriebssystemkern erfolgen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1: Prozessliste

Kapitel 2: Kernel-Architekturen

Grundlegend gibt es 3 verschiedene Kernel-Architekturen, welche im Folgenden näher erläutert werden:

- Monolithische Kernel
- Mikrokernel
- Modulare monolithische Kernel

1. Monolithische Kernel:

Im Fall eines monolithischen Kernels sind sämtliche Module des Kernels kompakt zusammengefasst und laufen im Kernel-Mode (siehe Abb. 2.1). Die Unterprogramme des Kernels können sich gegenseitig direkt aufrufen. Zusätzlich gibt es definierte Schnittstellen (Traps), mit denen der Nutzer mit dem Betriebssystem interagieren kann.

Der größte Vorteil dieser Struktur ist die enge Verflechtung einzelner Teile des Kernels, sodass diese leicht untereinander kommunizieren können. Dies wird jedoch aufgewogen durch folgende Nachteile:

- der gesamte Kernel muss im Speicher liegen
- der Entwurf wird durch die enge Verflechtung oft unübersichtlich
- bei der Änderung eines kleinen Aspekts muss der komplette Kernel neu kompiliert werden

Insbesondere die Effizienz der Speichernutzung leidet stark unter einer solchen Betriebssystemarchitektur, weil der Kernel in diesem Fall sämtliche Treiber für alle möglichen Geräte impliziert, sodass ein großer Teil des Kernels niemals benutzt wird.

2. Mikrokernel:

Der Mikrokernel ist das Gegenstück zum monolithischen Kernel und birgt nur sehr wenige grundlegende Funktionen in sich. Die Speicher- und Geräteverwaltung wird in Systemprozessen realisiert, welche jedoch im User-Mode laufen (siehe Abb. 2.1). Dies bringt den Vorteil mit sich, dass es nicht notwendig ist, bei Änderungen eines Aspekts den kompletten Kernel neu zu kompilieren, jedoch sind an einer Aufgabe immer der Kernel selbst und mindestens einer der Systemprozesse beteiligt, welche kommunizieren müssen. Dies ist bei mehreren Prozessen wesentlich umständlicher und langsamer als bei einem direkten Aufruf eines Unterprogramms, wie es bei einem monolithischen Kernel der Fall ist.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: geschichteter (monolithischer) Kernel (links) und Mikrokernel (rechts)

3. Modulare monolithische Kernel:

Der Modulare monolithische Kernel wurde entwickelt, um die Vorteile beider Kernel-Varianten zu verbinden.

Das Kernstück des Kernels ist ein Mikrokernel, jedoch sind die anderen Teile des Betriebssystems in Kernel-Modulen organisiert, welche dynamisch zu dem Kernel hinzu geladen werden. Somit befinden sich nur die benötigten Teile des Kernels im Hauptspeicher, gleichzeitig laufen jedoch alle Module im Kernel-Mode und die Kommunikation gestaltet sich wie bei einem monolithischen Kernel durch direkte Aufrufe von Unterprogrammen.

Diese Modularität ist insbesondere in Anbetracht der Vielzahl an vorhandenen Gerätetreibern nützlich. Ein monolithischer Kernel müsste sämtliche Treiber, die es für Geräte gibt, in sich gebunden und immer zur Verfügung haben, während ein modularer monolithischer Kernel nur die Treiber hinzulädt, die gerade benötigt werden. Dieses Prinzip gilt für sämtliche Aspekte des Kernels, welche austauschbar sind, beispielsweise Dateisysteme.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Modularer monolithischer Kernel

Kapitel 3: Scheduling-Modelle

3.1:FIFO-Scheduling

Das FIFO-Scheduling (First-in-First-out) stellt das einfachste Modell eines Schedulingverfahrens dar. Wie der Name sagt, wird der Prozess, welcher als erstes gestartet wird, ohne Verzögerung auf die CPU genommen und bleibt dort, bis er seine Aufgabe erfüllt hat. Weitere Prozesse ketten sich in eine Runqueue (Liste der lauffähigen Prozesse) ein und werden nacheinander abgearbeitet. Blockiert ein Prozess während seiner Laufzeit, beispielsweise weil angeforderte Daten noch nicht zur Verfügung stehen, wird er wieder an das Ende der Runqueue angekettet und der nächste Prozess bekommt die CPU.

Der Vorteil dieser Methode ist, dass unnötige Scheduler-Aufrufe vermieden werden und somit die CPU am effizientesten genutzt wird. Dies ist allerdings nur für Systeme mit ausschließlich CPU- lastigen Prozessen sinnvoll, weil eine Interaktion mit dem Nutzer in einem solchen System kaum möglich ist.

3.2: RR-Scheduling

Das Round-Robin Scheduling erweitert das FIFO-Scheduling um die Funktionalität von Zeiteinheiten auf der CPU, sodass die Prozesse vereinfacht gesagt innerhalb einer rotierenden Bewegung abwechselnd auf der CPU arbeiten. Dieses Verfahren erfordert somit die Möglichkeit einer aktiven Verdrängung von Prozessen und ein System zur Verwaltung von blockierten Prozessen, welche im Folgenden erläutert werden.

3.2.1: Präemptives und nicht-präemptives ]Scheduling

Der Begriff Präemptiv kommt vom Englischen „pre-empt“, „jemandem zuvorkommen, um ihn von etwas abzuhalten“.

Nicht-präemptives Scheduling haben wir bereits beim FIFO-Scheduling kennen gelernt, weil dort der Prozess nur von der CPU verdrängt wird, wenn er freiwillig die CPU aufgibt oder blockiert. Präemptives Scheduling bedeutet, dass der Prozess auch aus anderen Gründen von der CPU verdrängt werden kann. Dies kann sein, weil er eine Zeitgrenze überschritten hat (siehe 3.2.2) oder von einem wichtigeren Prozess verdrängt wird (siehe 3.3).

Präemptives Scheduling wird von allen modernen Betriebssystemen mit Nutzer-Interaktion verwendet, weil man sich nicht darauf verlassen kann, dass ein Programm so konzipiert ist, dass es während der Laufzeit freiwillig die CPU aufgibt. Dies ist allerdings unabdingbar für Systeme, die mit einem Nutzer interagieren bzw. weiche Echtzeitanforderungen haben, da ein Prozess, welcher vom Benutzer eine Eingabe bekommt auch innerhalb eines geringen Zeitraumes auf diese Eingabe antworten sollte. Zudem sollte die Reaktionszeit möglichst konstant sein, weil andernfalls der Eindruck von Instabilität entsteht..

3.2.2: Timeslices

Wie bereits erwähnt ist es wichtig, dass ein Prozess nach einer gewissen Zeit von der CPU verdrängt wird, da bei besonders „gierigen“ Prozessen, welche lange Rechenzeiten ohne Blockieren oder freiwilliges Aufgeben der CPU verbringen, andere Prozesse „verhungern“ würden. Aus diesem Grund wurden Zeitscheiben (Timeslices) eingeführt, welche angeben, wie lange ein Prozess noch auf der CPU arbeiten darf. Jedem Prozess wird eine bestimmte Zeit zugewiesen, nach welcher er, sofern er nicht vorher von der CPU verdrängt wird, wieder am Ende der Runqueue eingekettet wird.

Zur Überprüfung dieser Zeit gibt es neben der CPU einen Zeitgeberbaustein welcher in regelmäßigen Abständen ein Signal (Tick) zur CPU sendet. Sobald eine bestimmte Anzahl Ticks ohne Prozesswechsel empfangen wurde, wird der Scheduler aufgerufen und der laufende Prozess verdrängt. Die Zeitscheibe wird je nach Art der Verwendung in Millisekunden oder Ticks angegeben.

3.2.3: Prozessdeskriptoren

Bei der parallelen Verarbeitung von mehreren Prozessen wird es notwendig, eine Datenstruktur einzuführen, welche alle notwendigen Informationen über einen Prozess beinhaltet, damit dieser, wenn er auf die CPU kommt den Zustand herstellen kann, der vor seiner Verdrängung herrschte. Diese Datenstruktur, welcher Prozessdeskriptor genannt wird, enthält folgende Elemente:

1. PID (Prozess-ID):

Jeder Prozess bekommt bei der Erzeugung eine im System einmalig vorhandene Nummer zugewiesen, über welche er identifiziert werden kann.

[...]