Inhaltsverzeichnis

Vorwort   3

Kapitel  1: Einleitung in Kernel und Scheduler  4

Kapitel  2: Kernel-Architekturen  5

Kapitel  3: Scheduling-Modelle  7

3.1:  FIFO-Scheduling  7

3.2:  RR-Scheduling  7

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

3.2.2:  Timeslices  8

3.2.3:  Prozessdeskriptoren  8

3.2.4:  Prozesszustände und die Waitqueue  9

3.2.5:  Ereignis-basierte Waitqueues  10

3.3:  Prioritäten-basiertes Scheduling  11

Kapitel  4: Interrupts  12

4.1:  Definition eines Interrupts  12

4.2:  Präemptive und nicht-präemptive Kernel-Architekturen  12

Kapitel  5: Scheduling in Linux  14

5.1:  Einführung in das Schedulingverfahren des Linux-Kernels  14

5.2:  Epochen-Modell  14

5.3:  Echtzeitprozesse  15

5.3.1:  Schedulingverfahren von Echtzeitprozessen  15

5.4:  Normale Prozesse  16

5.4.1:  Nice-Level  16

5.4.2:  IO-Bonus  17

5.4.3:  Berechnung der Prioritätsklasse  18

5.4.4:  Berechnung der Timeslices  18

5.5:  Goodness  19

Fazit   20

Bildverzeichnis   21

Literaturverzeichnis   22

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 Linux-Kernels 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.

3

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.

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.

5

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.