Kapitel 2 Prozess- und Prozessorverwaltung PDF

Kapitel 2 Prozess- und Prozessorverwaltung 2.1 Einleitung 2.1.1 Wiederholung In Kapitel 1 wurden bereits einige grundlegende Konzepte zu Prozessen erläutert. Zur Erinnerung: 1. Ein Programm ist eine Folge von Maschinenbefehlen in Form eines binären Maschinencodes. 2. Ein Prozess is...

Kapitel 2 Prozess- und Prozessorverwaltung 2.1 Einleitung 2.1.1 Wiederholung In Kapitel 1 wurden bereits einige grundlegende Konzepte zu Prozessen erläutert. Zur Erinnerung: 1. Ein Programm ist eine Folge von Maschinenbefehlen in Form eines binären Maschinencodes. 2. Ein Prozess ist ein in Ausführung befindliches Programm. Es kann mehrere Instanzen des gleichen Programmes geben. 3. Ein System besteht aus einer Menge von Prozessen. 4. Damit Prozesse sich nicht gegenseitig beeinflussen, müssen sie voneinander isoliert werden. 5. Für die Isolation muss das Betriebssystem die Ressourcen, die ein Prozess beansprucht verwalten. Das betrifft insbesondere: Prozessor-Rechenzeit. Das grundlegende Prinzip ist, dass Prozesse den Prozessor abwechselnd benutzen dürfen. Speicherbedarf Zugriff auf Ein-/Ausgabegeräte und Dateien. 29 2.1.2 Prozess- vs. Prozessorverwaltung Multiprogramming Wie bereits erläutert laufen auf einem Rechner mehrere Prozesse gleichzeitig, z.B. wird Musik abgespielt, während der Benutzer den Webbrowser verwendet. Es gibt jedoch in der Regel mehr Prozesse als Rechenkerne. Auch wenn ein Pro- zessor nur einen einzigen Rechenkern hat, sollen die Prozesse gleichzeitig laufen können, damit z.B. nicht die Musik anhält, sobald der Benutzer den Webbrowser verwendet. Da ein einzelner Rechenkern herkömmlicherweise nicht dafür gebaut ist, wird die Parallelität vorgegaukelt, indem die Prozesse sehr schnell abgewech- selt werden, sodass sie zumindest so wirken als würden sie parallel laufen. Diese quasi-parallele Verarbeitung ist die Grundlage für das Multiprogramming. Nur dann, wenn die CPU mehrere Rechenkerne hat, können Prozesse echt paral- lel laufen. Das Problem ist damit allerdings nicht gelöst: Heute sind vier und mehr Rechenkerne in einem Prozessor weit verbreitet, jedoch laufen auf einem Rechner oft mehr als hundert Prozesse zeitgleich. Das Ziel des Multiprogramming ist es, die Rechenzeit zu optimieren. Oftmals müssen Prozesse auf z.B. auf Eingaben, eine Ressourcenfreigabe oder einen an- deren Prozess warten. Diese Zeit sollen andere Prozesse nutzen können, sodass wertvolle Rechenzeit nicht verschwendet wird. Multithreading: Sequentielle und parallele Prozesse Bekanntlich folgt ein Programm einem Kontrollfluss. Dieser wird oft auch Thread (Deutsch: Faden) genannt. Ein sequentieller Prozess hat genau einen Thread, zu dem ein Befehlszähler und weitere Register sowie ein Stack gehört. Es gibt jedoch auch Programme, in denen es erwünscht ist, dass mehrere Ab- läufe parallel geschehen. In diesem Fall ist es möglich, dass ein einzelner Pro- zess mehrere Threads hat, und somit mehr als einem Kontrollfluss im Programm- code folgen kann. Bei einem parallelen Prozess hat dann jeder einzelne dieser Threads wieder einen eigenen Befehlszähler, eigene Registerwerte, und einen ei- genen Stack. 30 Für die Implementierung von Threads gibt es unterschiedliche Herangehenswei- sen, die wiederum die Implementierung von Prozessen beeinflussen. Daher soll zunächst im Abschnitt 2.2 Implementierung von Prozessen von rein sequentiellen Prozessen, d.h. Prozesse mit nur einem Kontrollfluss ausgegangen werden. Im Abschnitt 2.3 Implementierung von Threads wird dann der Übergang zu paralle- len Prozessen gemacht und je nach Herangehensweise betrachtet, wie die Prozes- simplementierung ergänzt oder verändert werden muss. Begriffsdifferenzierung Das Durchwechseln der Prozesse (ggf. auch Threads) implementiert das Betriebs- system. Dafür muss es einige Informationen über die Prozesse speichern. Die Gruppierung der Prozessinformationen wird Prozesskontext genannt. Die Prozessverwaltung des Betriebssystems verwaltet die Prozesse und ihren Zu- stand in verschiedenen Datenstrukturen. Das Betriebssystem bietet außerdem ei- ne Schnittstelle für die Erzeugung und Terminierung von Prozessen und ggf. Threads. Die Prozessorverwaltung des Betriebssystems hingegen verwaltet die Zuteilung von Prozessen auf einen Prozessor. Der Mechanismus des Wechsels von einem Prozess auf den nächsten wird Dispatching bzw. Kontextwechsel (engl.: context switch) genannt. Dieser wird vom Dispatcher durchgeführt. Die Auswahl des Pro- zesses, welcher als nächstes rechnen darf, wird Scheduling genannt und wird vom Scheduler getroffen. Diese zwei Hauptbestandteile der Prozessorverwal- tung werden im Abschnitt 2.4 Prozessorverwaltung genauer betrachtet. Für das Scheduling gibt es mehrere Strategien, die in Abschnitt 2.5 Schedulings- trategien behandelt werden. 31 2.2 Implementierung von Prozessen 2.2.1 Allgemeines zu Prozessen Wiederholung: Prozess im Speicher Aus der Sicht eines Prozesses teilt sich sein Prozessadressraum in drei große Seg- mente: Code (auch: Text), Data und Stack. Im Data-Segment ist auch der Heap enthalten. (stark vereinfacht) Register der CPU 0xFFFF...FFFF Stack Segment Stack Lokale Variablen Base Pointer Funktionsaufrufe Stack Pointer Heap malloc() Data Segment(s) Data Globale Variablen Instruction Pointer = Programmzähler Code (Text) Code Segment 0x0000...0000 Abbildung 2.1: Struktur eines Prozessadressraumes 1. Das Code-Segment beinhaltet sämtlichen ausführbaren Maschinencode und beginnt bei der Adresse null. Der Programmzähler (engl.: instruction pointer) zeigt auf die nächste auszuführende Codezeile im Code-Segment und wird im Register eip (Extended Instruction Pointer) gespeichert. 2. Das Data-Segment folgt direkt auf das Code-Segment. Dieses enthält globa- le Variablen und Konstanten. 3. Danach folgt der Heap des Programmes. Hier liegen alle Speicherbereiche, die dynamisch belegt wurden. In C sind das alle mit malloc() angeforderten Bytes, dies entspricht in Java (konzeptionell) dem new-Operator. Der Heap wächst je nach Bedarf nach oben. 32  4. Am Ende des Prozessadressraumes befindet sich der Stack. Dieser dient da- zu, Funktionsaufrufe und lokale Variablen zwischen zu speichern. Er wächst vom Ende des Adressraumes nach unten, d.h. zu niedrigeren Adressen. Der Stack Pointer zeigt auf das letzte Element im Stack und liegt im Register esp. Der Base Pointer zeigt auf den Beginn des Rahmens der aktuellen Funk- tion und liegt im Register ebp. Prozesszustände Für die Prozessorverwaltung speichert das Betriebssystem zu jedem Prozess einen bestimmten Zustand, der beschreibt ob er gerade ausgeführt werden kann. Je nach Implementierung kann es zusätzliche oder auch weniger Zustände geben. Die wichtigsten davon sind: assign ready resign running add retire ready block blocked created terminated Abbildung 2.2: Prozesszustände 1. Zustände: created: Der Prozess wurde erzeugt. ready: Der Prozess ist rechenwillig. running: Der Prozess wird gerade ausgeführt. blocked: Der Prozess warten, z.B. auf eine Eingabe oder Ressource. terminated: Der Prozess ist beendet, aber noch nicht gelöscht. 2. Zustandsübergänge: add: Ein neu erzeugter Prozess wird zur Menge der rechenwilligen Pro- zessen hinzugefügt. 33  assign: Infolge eines Kontextwechsels wird dem Prozess die CPU zu- geordnet. resign: Dem rechnenden Prozess wird die CPU entzogen. block: Aufgrund eines blockierenden Aufrufs, wie z.B. Ein- oder Aus- gaben oder eine Ressourcenanforderung, wird der Prozess auf wartend gesetzt. ready: Nach Beendigung der angestoßenen, blockierenden Operation wechselt der Prozess in den rechenwilligen Zustand. retire Der aktuell rechnende Prozess terminiert. Diese Zustände können variieren. Beispielsweise kann auf manchen Systemen der Zustand «created» weggelassen werden, da ein neuer Prozess als sofort rechen- willig betrachtet wird. Auf Echtzeit-Systemen wiederum kann er notwendig sein, um z.B. zu gewährleisten, dass Deadlines anderer Prozesse eingehalten werden können. Andererseits kann es je nach System zusätzliche Zustände geben. So z.B. «swapped out»: Hier kann ein Prozess zusätzlich aus dem Arbeitsspeicher auf eine Festplatte ausgelagert werden.1 2.2.2 Datenstrukturen zur Prozessverwaltung Process Control Blocks (PCBs) Damit das Betriebssystem die laufenden Prozesse verwalten kann, muss es über jeden Prozess Informationen speichern. Daher erzeugt das Betriebssystem für je- den Prozess eine Datenstruktur, die alle notwendigen Daten enthält. Diese Da- tenstruktur heißt Process Control Block (PCB) und speichert den Prozesskontext. Der Process Control Block enthält im Wesentlichen folgende Daten: 1. Daten für die Prozess(-or)verwaltung: Hierbei handelt es sich um alle Da- ten, die den aktuellen Zustand des Prozesses beschreiben. 2. Daten für die Speicherverwaltung: Diese Daten dienen dazu, die vom Pro- zess belegten Speicherbereiche im Hauptspeicher zu lokalisieren. 1 (Link einsetzen) Siehe auch Kapitel Speicherverwaltung, Swapping 34  3. Daten für die Dateiverwaltung: Es werden Informationen zu allen vom Pro- zess geöffneten Dateideskriptoren, sowie zu den Zugriffsrechten des Prozes- ses gespeichert. Tabelle 2.1: Die wichtigsten Einträge im PCB (Linux) Prozess(-or)verwaltung Speicherverwaltung Dateiverwaltung Registerinhalte Pointer auf... Dateideskriptoren Program Counter Stack-Segment User ID (UID) Stack Pointer Code-Segment Group ID (GID) Statusregister Data-Segment Prozesszustand (ready, etc.) Größe der Segmente Prioriät Process ID (PID) Parent PID (PPID) Process Group ID (PGID) Wenn der Dispatcher zu einem anderen Prozess wechselt, so muss später der ex- akte Zustand des Prozesses zum Zeitpunkt der Unterbrechung wiederhergestellt werden. Alle dafür notwendigen Informationen sind im Process Control Block enthalten. Die im PCB zwischengespeicherten Register (z.B. Programm Counter oder die Universalregister) sowie die Zeiger auf die Stack-, Code- und Datenseg- mente bieten das notwendige Gerüst dafür. Prozesstabellen Das Betriebssystem speichert alle Process Control Blocks der Prozesse mittels Ta- bellen. In den sogenannten Prozesstabellen ist jeder Eintrag ein PCB. Eine solche Tabelle wird als einfach verkettete Liste realisiert, daher enthält jeder PCB zusätz- lich einen Verweis auf den nachfolgenden PCB. Die PCBs aller aktiven Prozesse (rechenwillig oder rechnend) werden in der Run Queue gespeichert, die PCBs der wartenden Prozesse in der Wait Queue. 35 Rechnend Prozessidentifikation Registerzustand Scheduling Information (z.B. Priorität) Rechenwillig Adressrauminformation Sonstiges Wartend folgender PCB Prozesskontrollblock Abbildung 2.3: Prozesstabellen als verkettete Listen 2.2.3 Erzeugung von Prozessen Auslöser, die Prozesse erzeugen Systeminitialisierung. Beim Hochfahren des Betriebssystems werden eini- ge Prozesse automatisch gestartet, dabei gibt es: – Vordergrundprozesse: Diese Prozesse interagieren direkt mit dem Be- nutzer. – Hintergrundprozesse: Das sind Prozesse für Systemfunktionen. Zu Hin- tergrundprozessen gehören Dämonen – Prozesse, die vom Booten bis zum Herunterfahren des Systems aktiv sind und wichtige Aufgaben erfüllen. Beispiele für Dämonen: * sshd erlaubt, sich per SSH entfernt auf einem Rechner einzuloggen, * Mit crond können Tasks geplant werden, * httpd beantwortet Webanfragen, * lpd (line printer daemon) verwaltet Druckeraufträge. 36  Prozess startet einen weiteren Prozess. So etwa Serveranfragen: Für jede eingehende Anfrage erzeugt der Server einen Kindprozess, der sich um die- se Anfrage kümmert und anschließend eine Antwort an den Client schickt. Durch Benutzerinteraktion. Beim Eingeben von ls oder beim Doppelklick auf ein Icon wird ein neuer Prozess gestartet. Betriebssystem. Batch-Jobs werden auf diese Art geplant. Dabei handelt es sich um Hintergrundaufgaben, die keine Benutzerinteraktion brauchen und regelmäßig (z.B. täglich, wöchentlich) ausgeführt werden. Dafür wird der zuvor genannte Dämon crond benötigt. Ablauf der Prozesserzeugung Jeder Prozess wird von einem Elternprozess erzeugt. Ein Kindprozess ist zunächst eine exakte Kopie seines Elternprozesses. Insbesondere bedeutet das, dass der Kindprozess nicht nur eine Instanz desselben Programmes ist, sondern auch ge- nau an der gleichen Stelle weiter rechnet, da auch der Programmzähler kopiert wird. Der neue Prozess erbt somit auch sämtliche Dateideskriptoren zu offenen Dateien. Somit sind auch die Standardein- und ausgaben stdin, stdout und stderr des Kindprozesses gleich, da diese auch mittels Dateideskriptoren realisiert wer- den. Die im PCB referenzierten Code- und Data-Segmente werden aus Effizienz- gründen erst bei Bedarf dupliziert (Siehe unten, copy-on-write). Der neue Prozess besitzt jedoch einen anderen Adressraum. Somit sind sie unabhängig voneinan- der. Die Erzeugung des Kindprozesses läuft über den Systemaufruf fork(). Dieser nimmt keine Argumente entgegen und lässt, wie der Name bereits andeutet, einen Kindprozess an dieser Stelle abzweigen. Nun kehrt dieser Systemaufruf in zwei Prozessen zurück: Sowohl im Eltern- als auch im Kindprozess, da der beim fork() erzeugte, neue Prozess an der glei- chen Stelle die Programmausführung fortsetzt. Sein Rückgabewert ist im Falle des Elternprozesses die PID des Kindprozesses, und im Falle des neu erzeugten Prozesses gibt fork() «0» zurück. Somit kann nach dem Aufruf von fork() ermit- telt werden, ob man sich im Eltern- oder Kindprozess befindet, und gegebenen- falls den Programmfluss unterschiedlich fortsetzen. Die eigene PID kann mittels 37 getpid() und die Parent PID mittels getppid() erfragt werden. Jedoch ist der Kindprozess zu diesem Zeitpunkt noch eine Instanz des gleichen Programmes wie sein Elternprozess. Oftmals soll der Kindprozess jedoch eine Instanz eines anderen Programmes sein. Um dies zu ändern muss der exec()- Systemaufruf ausgeführt werden. Dieser lädt aus einer Datei ein neues Program- mabbild. Dabei wird der gesamte Adressraum des Kindprozesses überschrieben, und der Kindprozess rechnet beim Einstiegspunkt des neuen Programmes weiter. Copy-on-write...... P1 P1 PCB fork() P2 P2 PCB...... Speicher Prozesstabelle Festplatte Abbildung 2.4: Prozesserzeugung Die Erzeugung eines Prozesses ist in der Abbildung 2.4 visualisiert. Während der Erzeugung des neuen Prozesses wird der PCB des Elternprozes- ses dupliziert. Dabei entsteht ein neuer Eintrag in der Prozesstabelle. Damit der neue Prozess unabhängig wird, braucht dieser jedoch einen eigenen Speicherbe- reich. Ein einfacher Ansatz wäre, den gesamte Speicherinhalt des Elternprozesses zu kopieren, sodass beide Prozesse nachher unterschiedliche Stellen im Speicher verwenden und sich nicht gegenseitig beeinflussen können. Dies ist jedoch sehr zeitaufwendig, da bei großen Speicherabschnitten entsprechend viel kopiert wer- den muss. So können Latenzen in Programmabläufen entstehen. Das vollständige Kopieren des Speichers ist jedoch nicht immer notwendig. Wenn der Kindprozess unmittelbar nach seiner Erzeugung zum Beispiel exec() auf- ruft, wird sein Speicherbereich vom neuen Programmabbild überschrieben und das gesamte Kopieren war überflüssig. Daher existiert eine optimierte Variante 38 - «copy-on-write». Die Prozesserzeugung läuft wie zuvor, bloß referenziert der Kindprozess nach seiner Erzeugung immer noch den gleichen Speicherbereich. Solange der Kindprozess nur lesend auf den Speicher zugreift, wird keine Kopie erstellt. Der Speicher wird erst dann kopiert, wenn einer der Prozesse versucht in den Speicher zu schreiben. Beispiel: Sei ls ein Kindprozess von Shell. Bei der einfachen Kopie würde zu- nächst die gesamte Shell vollständig dupliziert werden, nur um anschließend beim Laden des Programmes ls überschrieben zu werden. Wenn copy-on-write verwendet wird, dann ist das nicht notwendig, und der in die Shell eingegebene Befehl kann früher ausgeführt werden. 2.2.4 Terminierung von Prozessen Jeder terminierende Prozess gibt (ähnlich wie eine Funktion), als Rückgabewert einen ganzzahligen Wert zurück. Dabei bedeutet eine «0», fehlerfrei terminiert. Prozesse terminieren gewöhnlicherweise unter einer der folgenden Bedingungen: 1. Normale Beendigung: Dies geschieht mittels dem Systemaufruf exit(0). Alternativ kann return 0; in der main()-Funktion aufgerufen werden. Im Prinzip passiert bei beidem das Gleiche, da der Rückgabewert der main()- Funktion immer an exit() weitergegeben wird. 2. Vorzeitige Beendigung im Fehlerfall: Nach Erkennung eines Fehlers kann das Programm abbrechen, ebenso mit einem exit() bwz. return aus der main()-Funktion. Durch die Rückgabe eines Wertes ungleich 0 wird signali- siert, dass es sich um eine vorzeitige Beendigung handelt. 3. Terminierung durch das Betriebssystem wegen einem fatalen Fehler. Bei- spielsweise tritt dieser Fall ein, wenn das Programm auf einen nicht existie- renden Speicherbereich zugreift (Segmentation Fault). Die Beendigung wird mittels Signalen2 realisiert. 4. Terminierung durch einen anderen Prozess: Die gleichen Signale können auch von einem anderen Prozess geschickt werden. Dafür wird der System- aufruf kill(pid, signal) verwendet. 2 Siehe Kapitel 5 Prozesskommunikation 39 Wenn ein Prozess terminiert, dann wird sein Rückgabewert im PCB gespeichert und er wechselt in den Zustand «terminated». Das Betriebssystem gibt eventuell belegte Ressourcen frei. Sobald die Informationen über den Prozess von nieman- den mehr benötigt werden, wird der PCB endgültig gelöscht. 2.2.5 Prozesshierarchie Neben der Speicherung in der Prozesstabelle in Form von Listen sind die PCBs unter Unix3 zusätzlich mittels einer Baumstruktur untereinander verlinkt. Jeder Prozess hat genau einen Elternprozess und kann mehrere Kindprozesse haben. Die Wurzel dieser sogenannten Prozesshierarchie ist ein spezieller Prozess na- mens init4 : Dies ist der erste User-Space-Prozess, der nach der Initialisierung des Kernels beim Hochfahren erzeugt wird. Seine PID ist immer 1 und seine PPID ist immer 0 (Siehe Abbildung 2.5). init startet mehrere virtuelle Terminals5 getty, die mittels dem Programm login das Einloggen mit einem Benutzer ermöglichen. Nach dem Login wird eine Shell erzeugt, die das Ausführen weiterer Prozesse er- möglicht. Einen Teilbaum der Prozesshierarchie nennt man Prozessgruppe, diese werden mittels einer Process Group ID (PGID) identifiziert. Der Wert der PGID entspricht der Wurzel des Teilbaums. Die Wurzel des Teilbaums heißt Process Group Lea- der. Die Prozesshierarchie spielt eine Rolle, wenn beispielsweise ein Signal an einen Prozess gesendet wird, dieses wird an alle Kind-Prozesse weitergeleitet und von diesen individuell behandelt. Zombie-Prozesse Als Zombie-Prozess werden Kind-Prozesse bezeichnet, die vor ihren Elternpro- zessen terminieren. Die Bezeichnung Zombie kommt daher, dass Kindprozesse nach ihrer Beendigung in der Prozesstabelle erhalten bleiben, obwohl sie nichts 3 InWindows gibt es keine Prozesshierarchien. 4 Im Fall von Linux ist init durch systemd ersetzt worden, der die gleichen Aufgaben über- nimmt. 5 Diese sind mittels Strg+Alt+ zugänglich. Gibt es einen grafischen Desktop, dann liegt auch dieser auf einer der Funktionstasten. Siehe auch Kapitel 8 Ein- und Ausgabe. 40  init PID=1 PPID=0 sshd bash httpd PID=2 PID=3 PID=4 PPID=1 PPID=1 PPID=1 ls firefox ps PID=5 PID=6 PID=7 PPID=3 PPID=3 PPID=3 firefox child PID=8 PPID=6 PGID=6 Abbildung 2.5: Prozesshierarchie mehr rechnen («terminated»). Sie bleiben so lange erhalten, bis der Elternpro- zess mittels den Systemaufrufen wait() oder waitpid() ihren Zustand erfragt hat, oder bis der Elternprozess beendet wird. Direkt nach der Terminierung des Kindprozesses wird sein verwendeter Speicher freigegeben und der in exit() übergebene Status in den PCB geschrieben. Jedoch wird der Prozesstabelleneintrag zunächst noch nicht gelöscht. Dies geschieht, da- mit das Verhalten der wait()-Funktionen gewährleistet bleibt: Sie blockieren den Aufrufer (den Elternprozess), bis ein beliebiges (wait()) oder ein bestimmtes (waitpid()) Kind beendet ist, und liefern den exit()-Status des Kindes zurück. Damit dieses Verhalten auch nach der Terminierung des Kindes gegeben ist, muss der Eintrag in der Prozesstabelle länger gehalten werden. Nachdem der Elternprozess den Sta- 41  tus des Kindes erfahren hat, wird der Prozesstabelleneintrag endgültig gelöscht. Waisen-Prozesse Waisen-Prozesse entstehen, falls der Elternprozess vor dem Kind-Prozess termi- niert. In diesem Fall wird der Kindesprozess vom init-Prozess adoptiert, also wird die PPID des Waisen auf den Wert 1 gesetzt. Dieses Verhalten kann in der Praxis dazu genutzt werden, um Dämonen-Prozesse zu erzeugen, die im Hinter- grund laufen und unabhängig von ihrem ursprünglichen Erzeuger sind. Durch Lösen der Group-ID und User-ID gehören sie auch zu keinem Benutzer mehr, und durch Umleiten bzw. Schließen aller offenen Dateideskriptoren kann der Dämon vom Elternprozess nicht mehr beeinflusst werden. 2.2.6 Anwendungsbeispiel Im folgenden soll ein Anwendungsbeispiel von fork() betrachtet werden. 1 # include < stdlib.h > 2 # include < stdio.h > 3 # include < unistd.h > 4 5 int mydata = 11; 6 7 int main ( int argc , char * argv []) { 8 pid_t cpid = fork () ; 9 10 switch ( cpid ) { 11 case -1: 12 perror ( " Kindprozess konnte nicht erzeugt werden " ) ; 13 return EXIT_FAILURE ; 14 case 0: 15 mydata = mydata * 3; 16 printf ( " Kindprozess ( PID =% d ) , " 17 " mydata =% d \ n " , getpid () , mydata ) ; 18 break ; 19 default : 20 printf ( " Elternprozess ( PID =% d ) , " 21 " PID des Kindes : %d , " 22 " mydata =% d \ n " , getpid () , cpid , mydata ) ; 23 } 24 return EXIT_SUCCESS ; 42 25 } Listing 2.1: fork-Beispiel Der in der Datei «fork.c» gespeicherte C-Code, kann mit folgenden Kommando- zeilenbefehlen übersetzt und ausgeführt werden: $ gcc -o fork fork. c $./ fork Elternprozess ( PID =15256) , PID des Kindes : 15257 , mydata =11 Kindprozess ( PID =15257) , mydata =33 Obwohl sie in der gleichen switch-Anweisung sind, wurden Beobachtet wird, dass sowohl case 0 als auch default ausgeführt wurden, ob- wohl sie in dem selben Switch-Case stehen. Da nach dem fork() Aufruf zwei Prozesse, mit unterschiedlichen Rückgabewerten in cpid, existieren. Der Eltern- prozess kennt mittels cpid die PID des Kindprozesses, während cpid für das Kind den Wert 0 hat. In der globalen Variable mydata haben beide Prozesse unterschiedliche Werte ste- hen, da ihre Adressräume nach dem fork() getrennt sind und nur der Kindpro- zess mit 3 multipliziert. Auch der Systemaufruf getpid() liefert je nach Prozess unterschiedliche Rückgabewerte. 2.3 Implementierung von Threads 2.3.1 Allgemeines zu Threads Am Anfang des Kapitels wurde bereits die Grundidee von Threads eingeführt. Zur Erinnerung: Ein Programm folgt einem Kontrollfluss, dem sogenannten Thread. Für manche Anwendungen ist es nützlich, mehr als einen Kontrollfluss zu haben, sodass nebenläufig an beide abgearbeitet werden können. Prozesse vs. Threads Diese Nebenläufigkeit wird durch die Trennung von Prozess und Thread reali- siert. Alle Threads eines Prozesses teilen sich den gleichen Prozessadressraum, jedoch besitzt jeder Thread einen eigenen Stack. 43  1. Ein Thread steht für einen eigenständigen Kontrollfluss im Code des Pro- grammes. Dafür braucht insbesondere jeder Thread einen eigenen Programm- zähler sowie einen eigenen Stack für die Funktionsaufrufe. 2. Der Prozess gruppiert die einzelnen Threads, sowie jene Ressourcen, die ge- meinsam von allen Threads verwendet werden oder nicht einem bestimm- ten Thread zuweisbar sind. Dazu gehören z.B. Code- und Daten-Segment oder offene Dateideskriptoren. Thread Nr. 3) Prozess (Adressraum) Stack von Thread 3) Kernel Abbildung 2.6: Threads vs. Prozess Da mehrere Threads auf den gleichen Adressraum zugreifen können, ist bei der Programmierung darauf zu achten, dass der Speicherzugriff ggf. synchronisiert werden muss. Threadzustände Threads können, genauso wie Prozesse, in verschiedenen Zuständen (created, rea- dy, running, blocked und terminated) sein. Die Zustandsübergänge erfolgen für Threads gleich wie bei Prozessen. Prozesskontext vs. Threadkontext Durch das Einführen von Threads passen Informationen wie z.B. der Programm- zähler nicht mehr allgemein zu einem Prozess. Daher werden alle Thread-spezifischen Informationen nun in einem Threadkontext zusammengefasst: 44  assign ready resign running add retire ready block created blocked terminated Abbildung 2.7: Threadzustände Prozesskontext (Ressourcengruppe) Threadkontext (Kontrollfluss) Ort des Code- und Data-Sements Stack Globale Variablen Programmzähler Dateideskriptoren Registerwerte Informationen über Adressraum Threadzustand Alarme und Interrupts (uvm.) Ob und wie diese Trennung den Prozesskontext beeinflusst, hängt von der Imple- mentierung ab. Gründe für Multithreading Die Verwendung von Threads bringt einige Vorteile mit sich. Wie stark sich diese auswirken hängt jedoch von der genauen Implementierung der Threads durch das Betriebssystem ab. Der gemeinsame Adressraum bedeutet einfachere Kommunikation durch direkten Datenaustausch. Da Threads leichtgewichtiger als Prozesse sind, ist der Aufwand für die Threaderzeugung und den Threadkontextwechsel geringer. Durch die Nebenläufigkeit können IO und CPU besser ausgelastet werden und echte Parallelität ist möglich, wenn mehrere Rechenkerne vorhanden sind. 45 Herausforderung: Die Synchronisation und Implementierung von parallelen Ab- läufen bringt mehr Programmieraufwand sowie höhere Fehleranfälligkeit mit sich. Beispiel 1: Word-Processor. Die Formatierung des Textes, das Reagieren auf Nut- zerinteraktion wie Tastatureingaben und das automatische Abspeichern des Do- kumentes auf die Festplatte geschieht nebenläufig. Beispiel 2: Web-Server. Ein Prozess wartet auf Anfragen. Kommt eine Anfrage herein, dann wird ein Thread für dessen Bearbeitung erstellt. Somit können meh- rere Anfragen bearbeitet werden, und gleichzeitig kann der Server stets auf neue Anfragen reagieren. Implementierung Der Übergang von sequentiellen auf parallele Prozesse wirft einige Fragen auf: Wie funktioniet das Scheduling und Dispatching eines Threads (bzw. Pro- zesses)? Wie genau sehen Threadkontext und Prozesskontext aus? Wer verwaltet die- se? Ob und wenn ja welche Datenstrukturen (z.B. PCBs, Prozesstabellen) ändern sich im Betriebssystem? Was ist mit mehreren Stacks im gleichen Prozessadressraum? Hat ein Prozess noch einen eigenen Zustand (running, ready, etc.), wenn er selbst keinen Kontrollfluss mehr hat? Die Antworten auf diese Fragen hängen davon ab, wer das Multithreading imple- mentiert. Dabei gibt es drei Möglichkeiten: 1. User-Level Threads: Das Betriebssystem kennt keine Threads, es verwal- tet weiterhin sequentielle Prozesse. Das Multithreading wird von einer Pro- grammbibliothek im User Space implementiert. 2. Kernel-Level Threads: Das Betriebssystem kennt alle Threads und verwal- tet diese im Kernel Space. 3. Hybride Implementierung: Es gibt sowohl Kernel-Threads als auch User- Threads. 46 2.3.2 User-Level Threads Funktionsprinzip Das Betriebssystem hat keine Kenntnisse über User-Threads und verwaltet ledig- lich sequentielle Prozesse. Die Prozessorzuteilung im Kernel erfolgt an Prozesse. Das Multithreading ist nicht im Kernel, sondern in einer separaten Programmbi- bliothek im User Space implementiert. Für den Programmierer stellt die Biblio- thek Funktionen zum Erzeugen, Beenden, usw. von Threads zur Verfügung. Sie verwaltet die Threadkontexte in eigenen Threadtabellen, hat einen eigenen Sche- duler, und macht auch den Kontextwechsel der Threads selbst. Dies resultiert in einem Scheduling-Verfahren mit zwei Ebenen: Ein Scheduler im Kernel des Betriebssystems entscheidet, welcher Prozess rechnen darf, und ein zweiter Scheduler im User Space entscheidet, welcher Thread rechnen darf. Aller- dings weiß dabei die Programmbibliothek ausschließlich über die Threads eines einzigen Prozesses Bescheid. Für jeden Prozess, der diese Bibliothek verwendet, gibt es also eine eigene Instanz des User-Level Schedulers/Dispatchers. Allerdings kann eine Programmbibliothek einen laufenden Thread nicht unter- brechen. Daher muss bei der Programmierung ein Thread nach einiger Zeit frei- willig die CPU abgeben. Vor- und Nachteile + Die Programmbibliothek kann betriebssystemunabhängig sein. + Da ein Wechsel des Arbeitsmodus aufwändig wäre, ist ein schnellerer Kontext- wechsel möglich. + Es kann ein anwendungsspezifisches Scheduling implementiert werden. − Blockiert ein Thread, dann blockiert der ganze Prozess − Ein Thread kann von einer Programmbibliothek nicht unterbrochen werden. Daher kann ein Thread die CPU monopolisieren, d.h. dauerhaft belegen. − Echte Parallelität bei mehreren vorhandenen Rechenkernen wird unmöglich, da das Betriebssystem von sequentiellen Prozessen ausgeht. =⇒ Die Nachteile widersprechen den eigentlichen Beweggründen von Threads. 47  Prozess Thread Benutzer Adressraum Benutzermodus) System BS-Kern Adressraum (Systemmodus) Laufzeit- Thread- Prozess- system tabelle tabelle Abbildung 2.8: User-Level Threads 2.3.3 Kernel-Level Threads Funktionsprinzip Das Betriebssystem verwaltet alle Threads selber im Kernel Space: Der Kernel un- terscheidet nun selber zwischen Prozess- und Threadkontext. Die Threads tragen den Zustand (running, ready, usw.). Die Prozessorzuteilung durch das Betriebs- system erfolgt nun nicht mehr an Prozesse, sondern an einzelne Threads. Für die Erzeugung, Beendigung, usw. von Threads stellt das Betriebssystem Systemauf- rufe zur Verfügung, die vom User in den Kernel Mode wechseln. Das Scheduling hat hier nur eine Ebene, es erfolgt im Betriebssystem. Der Auf- wand um zwischen Threads unterschiedlicher Prozesse zu wechseln ist gleich groß wie der Wechsel bei sequentiellen Prozessen. Da die Threads eines Prozesses den Adressraum teilen, kostet der Wechsel zwischen Threads des gleichen Pro- zesses weniger Zeit. Vor- und Nachteile + Blockierende Threads halten nicht mehr den ganzen Prozess an. + Echte Parallelität bei mehreren vorhandenen Rechenkernen möglich. − Der Wechsel zwischen Threads wird etwas teurer, da dafür vom User in den 48  Prozess Thread Benutzer Adressraum Benutzermodus) System BS-Kern Adressraum (Systemmodus) Thread- Prozess- tabelle tabelle Abbildung 2.9: Kernel-Level Threads Kernel Mode gewechselt werden muss. Weiß das Betriebssystem über die Zugehörigkeit von Threads zu Prozessen Be- scheid, dann kann es das berücksichtigen, um den Aufwand für einen Kontext- wechsel zu verringern. 2.3.4 Hybride Implementierung Dies ist eine Mischung von User- und Kernel-Level Threads: Die Kernel-Threads werden vom Betriebssystem wie bei einer reinen Kernel-Level Implementierung verwaltet. Es kann jedoch innerhalb eines Kernel-Threads im User Space mehre- re User-Threads geben. Diese sind wiederum wie bei User-Level Threads mittels einer Programmbibliothek implementiert. Dadurch ergibt sich wieder ein Sche- duling mit zwei Ebenen. Es werden n User-Threads auf m Kernel-Threads abgebildet, also gibt es eine n : m-Abbildung: 49  Mehrere Userthreads ausgehend von einem Kernel Thread Benutzer Adressraum Benutzermodus) System Kernel Adressraum (Systemmodus) Kernel- thread Abbildung 2.10: Hybride Threads 2.3.5 Anwendungsbeispiel Unix-basierte Systeme unterstützen Kernel-Level Threads. Daher kann ein Pro- zess Kernel-Threads benutzen, es ist aber auch möglich eine hybride Implemen- tierung darauf aufzubauen. Zur Erzeugung von Threads unter Linux gibt es z.B. den Systemaufruf clone(). Zwar haben die Threads unterschiedliche PIDs und PPIDs, sie teilen sich trotz- dem den Adressraum und Ressourcen wie Dateideskriptoren, Signale, usw. In der Praxis wird für die Programmierung mit Threads die POSIX Thread-Bibliothek («pthread») verwendet, die die Systemaufrufe abstrahiert. Sie implementiert eine 1:1-Abbildung von User-Level auf Kernel-Level Threads. Auch z.B. die Java Virtual Machine, die Laufzeitumgebung für Java-Programme, implementiert eine 1:1-Abbildung auf Kernel-Level Threads. Multithreading mit pthread Der Main-Thread erstellt einen zweiten Thread mittels pthread_create(). Der neue Thread führt die übergebene Funktion thread_func() aus. Dabei wird der 50  String "Hello!" als Argument übergeben. Mit dem Aufruf von pthread_join() blockiert der Main-Thread, bis der zweite Thread beendet ist. Der zweite Thread führt thread_func() aus und beendet sich mit pthread_exit(). Danach kann der Main-Thread fortgesetzt werden. 1 # include < stdio.h > 2 # include < string.h > 3 # include < pthread.h > 4 5 int mydata = 11; 6 7 void * thread_func ( void * arg ) { 8 printf ( " Thread : ID =% ld arg =% s mydata =% d \ n " , pthread_self () , 9 ( char *) arg , mydata ) ; 10 mydata = mydata * 3; 11 pthread_exit (( void *) strlen ( arg ) ) ; 12 } 13 14 int main ( int argc , char * argv []) { 15 void * res ; 16 pthread_t thread ; 17 18 pthread_create (& thread , NULL , thread_func , " Hello ! " ) ; 19 pthread_join ( thread , & res ) ; 20 21 printf ( " Main Thread : pthread returned % ld , mydata =% d \ n " , 22 ( long ) res , mydata ) ; 23 return 0; 24 } Listing 2.2: Pthreads (POSIX Threads) Befindet sich der C-Code in einer Datei «threads.c», kann er wie folgt übersetzt und ausgeführt werden: $ gcc - pthread -o threads threads. c $./ threads Thread : ID =140568241702656 arg = Hello ! mydata =11 Main Thread : pthread returned 6 , mydata =33 Mittels pthread_create() und pthread_join() können Argumente über- und zu- rückgegeben werden: "Hello!" und strlen() davon, was zu 6 evaluiert. Der neu 51 erzeugte Thread multipliziert die globale Variable mydata mit 3. Da sich beide Threads den gleichen Adressraum teilen, ist dieses Rechenergebnis auch im Main- Thread nachher sichtbar. 2.4 Prozessorverwaltung Nun soll genauer betrachtet werden, wie das Betriebssystem die Prozessorzutei- lung an Prozesse (bzw. Kernel-Threads) implementiert. 2.4.1 Dispatching Der Dispatcher implementiert den Kontextwechsel von einen Prozess (P0 ) auf den nächsten (P1 ). Er ist meistens Bestandteil des Schedulers. Beim Kontextwechsel muss er den Prozesskontext von P0 abspeichern und ersetzt ihn durch den von P1. Die Zustände der Prozesse werden entsprechend angepasst. Ablauf In der folgenden Grafik rechnet zunächst P0 , danach wird zu P1 gewechselt und nach einiger Zeit wird wieder zu P0 zurück gewechselt (blaue Pfeile). Der Wechsel von P0 auf P1 läuft wie folgt ab: 1. P0 wird gerade ausgeführt. 2. Durch einen Interrupt (bzw. Systemaufruf) wird in den Kernel Mode ge- wechselt. 3. Der Scheduler bestimmt, dass P1 fortgesetzt werden soll. 4. Der Dispatcher ändert je nach Situation den Zustand von P0 zu «ready», «blocked» oder «terminated». 5. Der Dispatcher sichert den Kontext von P0 (Registerwerte, Programmzähler, usw.) im zugehörigen Process Control Block. 6. Der Dispatcher lädt den Kontext von P1 (Registerwerte, Programmzähler, usw.) in die entsprechenden CPU-Register. 7. Der Dispatcher setzt den Zustand von P1 auf «running». 8. Es wird in den User Mode gewechselt und die Kontrolle an P1 abgegeben. 9. P1 wird fortgesetzt. 52  process P0 operating system process P1 interrupt or system call executing save state into PCB0 idle load state from PCB1 idle interrupt or system call executing save state into PCB1 idle load state from PCB0 executing Abbildung 2.11: Kontextwechsel Kontextwechsel zwischen Kernel-Threads Es ist anzumerken, dass umso umfangreicher ein Prozesskontext ist, desto auf- wendiger wird auch der Kontextwechsel. Im Allgemeinen sind Threadkontexte weniger umfangreich als Prozesskontexte. Da Threads eines gemeinsamen Pro- zesses sich untereinander Ressourcen teilen (insbesondere den Adressraum), er- folgt ein Wechsel zwischen Threads desselben Prozesses sehr schnell. Jedoch ist ein Wechsel zwischen Threads unterschiedlicher Prozesse gleich aufwändig wie ein Wechsel zwischen sequentiellen Prozessen. 2.4.2 Scheduling Der Scheduler trifft die Entscheidung, welcher Prozess (bzw. Kernel-Thread) wann und wie lange rechnen darf. Bei mehreren Rechenkernen muss zusätzlich ent- schieden werden, an welchen davon der Prozess gebunden wird. Für diese Ent- scheidungsfindung gibt es unterschiedliche Schedulingstrategien. Das Ziel dabei ist es, die Rechenzeit so effizient wie möglich aufzuteilen und dabei Systemricht- 53 linien zu erfüllen. Dazu nutzt er typische Eigenschaften von Prozessen aus, wie z.B. dass diese ab- wechselnd (a) auf Eingaben warten, dh. keine Rechenzeit brauchen und (b) da- nach diese verarbeiten und dafür dann umso mehr Rechenzeit benötigen. Prozes- se, die hauptsächlich rechnen, werden auch als CPU-lastig, und jene, die großteils Ein- und Ausgaben durchführen als I/O-lastig bezeichnet. Unterbrechend vs. nicht unterbrechend Prinzipiell kann die Arbeitsweise des Schedulings in zwei unterschiedliche Funk- tionsweisen aufgeteilt werden: Einerseits gibt es sogenannte nicht-unterbrechende (non-preemptive) Schedu- lingstrategien, bei denen Prozesse so lange ausgeführt werden, bis sie entweder terminieren, blockieren oder die CPU freiwillig wieder abgeben. Die Prozesse werden dadurch nicht unnötig oft unterbrochen, dh. es sind weniger Kontext- wechsel nötig. Allerdings kann ein Prozess die CPU monopolisieren (dauerhaft belegen), wenn er nicht von selber die CPU freigibt. Im Gegensatz dazu stehen unterbrechende (preemptive) Scheduling Strategien, die einen Prozess beim Auftreten von definierten Ereignissen (z.B. Timer-Interrupts oder Prozesserzeugung) unterbrechen können. Da ein noch nicht fertig gerechne- ter Prozess erneut geladen werden muss, fallen mehr Kontextwechsel an. Prozes- se können auch bei unterbrechenden Schedulingstrategien von sich aus die CPU wieder freigeben, z.B. über einen Systemaufruf. Schedulingstrategien Wie in Kapitel 1 im Abschnitt über Betriebsarten eingeführt, kann man grob zwi- schen Batch-Systemen, interaktiven Systemen und Echtzeit-Systemen unterschei- den. Je nach Betriebsart und dessen Einsatzgebiet ergeben sich unterschiedliche Ziele und Algorithmen für das Scheduling. Folgende Algorithmen werden be- sprochen: 1. Batch-Systeme: Es ist keine Nutzerinteraktion vorgesehen und alle Program- me sind beim Start bekannt. Aus der Menge der Prozesse wird jeweils einer abgearbeitet. 54  First-Come-First-Served (FCFS): nicht unterbrechend. Shortest Job First (SJF): nicht unterbrechend. Shortest Remaining Time Next (SRTN): unterbrechend. 2. Interaktive Systeme: Benutzer können mit dem Rechner interagieren: Da- bei werden i.d.R. geringe Antwortzeiten vom Benutzer erwartet. Dafür, und weil es sich hier meist um General-Purpose-Systeme handelt, ist es essenti- ell, dass das Scheduling unterbrechend ist. Round Robin (RR): unterbrechend. Priority Scheduling: unterbrechend. 3. Echtzeit-Systeme: Es gibt harte und weiche Deadlines. Harte Deadlines müs- sen eingehalten werden, während das Verpassen einer weichen unerwünscht, aber tolerierbar ist. Diese Rechensysteme sind oft Special-Purpose-Systeme und daher trotz der Deadlines auch nicht unterbrechend implementierbar. Earliest Deadline First (EDF): kann unterbrechend oder nicht sein. Rate-Monotonic Scheduling (RMS): unterbrechend. Optimierungsziele Aus den unterschiedlichen Einsatzgebieten der Betriebsarten heraus ergeben sich auch verschiedene Ziele beim Scheduling. Zwei Ziele haben jedoch alle gemein- sam: Alle Systemstrategien haben als Ziel die Fairness, wobei jeder Prozess einen fairen Anteil an Rechenzeit erhält. Damit ist nicht zwingend gemeint, dass jeder Prozess automatisch gleich viel Rechenzeit wie alle anderen Prozesse erhält, sondern dass er seiner Aufgabe angemessen viel Rechenzeit zugewie- sen bekommt. Dafür können die Prozesse mittels unterschiedlichen Priori- täten klassifiziert werden. Es soll allerdings auch nicht passieren, dass ein unwichtiger Prozess überhaupt nicht rechnen kann, sodass er nie terminiert. Man will das sogenannte «Verhungern von Prozessen» vermeiden. Das zweite, gemeinsame Ziel ist die Balance der Systemauslastung. Das be- deutet, dass CPU- bzw. I/O-lastige Prozesse gemischt werden, sodass alle Teile des System bestmöglich ausgelastet sind. Desiree : zukünftige IO- Aktionen 55 schätzen? (Latex Kom- mentar) Weiters gibt es folgende Ziele beim Scheduling, die abhängig von der Betriebsart des Rechensystems sind: 1. Ziele bei Batch-Systemen: Zusätzliches Ziel bei Batch-Systemen ist es, den Durchsatz zu maximie- ren. Dabei handelt es sich um die Anzahl der Aufträge, die innerhalb einer bestimmten Zeit ausgeführt werden. Ein weiteres Ziel ist die CPU-Belegung. Auch wenn die CPU durch- gehend ausgelastet ist, muss der Durchsatz nicht zwingend hoch sein. Beispielsweise könnte die gesamte Rechenleistung in einen einzigen, langlebigen Prozess gesteckt werden, während in der selben Zeit auch viele, kurze Prozesse abgearbeitet werden können. Desiree : Tannen- Die Ausführungszeit eines Prozesses ergibt sich aus der Summe von baum sagt Warte- und Rechenzeit. Diese soll minimiert werden. Auch wenn der dazu, dass dieses Durchsatz hoch ist, muss das nicht bedeuten, dass die Ausführungs- Kriterium zeit niedrig ist. Dies kann z.B. passieren, wenn viele, kurze Aufträge eigentlich ziemlich bearbeitet werden, dabei jedoch ein langer Prozess verhungert. useless ist... eben weil 2. Ziele bei Interaktiven Systemen: die CPU- Belegung weder den Antwortzeit: Wenn der Benutzer eine Anfrage stellt, soll der Rechner Durchsatz so schnell wie möglich darauf reagieren. noch die Ausfüh- Proportionalität: Die Erwartungshaltung des Benutzer sollte berück- rungszeit messen sichtigt werden. Zum Beispiel erwartet der Benutzer bei einem Mausklick kann eine nicht merkbare Reaktionszeit, während beim Download einer großen Datei niemand erwartet, dass das schnell passiert. 3. Ziele bei Echtzeit-Systemen: Zusätzlich zu den gemeinsamen Zielen haben Echtzeit-Systeme das Ziel ihre Deadlines einzuhalten. Bei Nichteinhalten von Soft-Deadlines kann es zu Datenverlusten kommen, bei harten Deadlines hingegen können schwerwiegende Fehler auftreten bzw. Gefahr im Verzug sein. Um alle Deadlines einhalten zu können, ist die Vorhersagbarkeit der Rechendauer ein weiteres Ziel. Umso besser die Dauer aller Prozes- se vorhergesagt werden kann, umso weniger unvorhergesehene Zwi- schenfälle verzögern den Prozessablauf. 56  Kein Verhungern: Auch auf einem Echtzeit-System kann es Prozesse ohne Deadlines geben. Unkritische Prozesse sollen nicht verhungern, während zeitkritische ihre Deadlines einhalten müssen. 2.5 Schedulingstrategien 2.5.1 Batch-Systeme First Come First Served | FCFS Die Prozesse bekommen in der Reihenfolge, in der sie Rechenzeit angefordert ha- ben, die CPU zugewiesen. Dafür verwaltet der Scheduler eine FIFO-Run-Queue, in der alle rechenwilligen Prozesse eingefügt werden. Dabei werden also keine Eigenschaften wie Priorität oder verbleibende Rechenzeit berücksichtigt. Die FCFS-Strategie ist non-preemptive: Ein rechnender Prozess wird so lange nicht ausgewechselt, bis er blockiert oder die CPU freiwillig abgibt. Sollte der rechnende Prozess die CPU abgeben, so wählt der Scheduler immer den ersten Prozess aus der Run-Queue aus. Diese Strategie ist sehr simpel und daher einfach zu implementieren. Allerdings können ein paar wenige Prozesse die CPU sehr lange beanspruchen, sodass ggf. viele kurze Prozesse nicht rechnen können, was auch den Durchsatz verringert. Shortest Job First | SJF Für diese Schedulingstrategie müssen die voraussichtlichen Rechenzeiten der Pro- zesse vorliegen. Bei der SJF-Strategie wird der Prozess mit der kürzesten ver- bleibenden Rechenzeit der CPU zugewiesen. Shortest Job First ist dabei non- preemtive, Prozesse werden also vom Scheduler nicht unterbrochen. Sind zusätzlich alle Prozesse am Anfang bekannt, d.h. sie werden nicht erst im Laufe der Zeit hinzugefügt, kann man zeigen, dass SJF die durchschnittliche Aus- führungszeit (= Wartezeit + Rechenzeit) optimiert. Dies soll anhand einem Bei- spiel veranschaulicht werden: Hierzu sollen die Prozesse P1−4 , deren Rechenzei- ten (8ms bzw. 4ms) im Voraus bekannt sind, sowohl mit FCFS als auch SJF durch- gelaufen werden: 57  Prozessreihenfolge: P1 P2 P3 P4 P2 P3 P4 P1 Wartezeit in ms: 0 8 12 16 0 4 8 12 Rechenzeit in ms: 8 4 4 4 4 4 4 8 ∅ Ausführungszeit: (FCFS) 14 ms (SJF) 11 ms Die linke Tabelle zeigt die FCFS-Strategie, bei der die Prozesse der Reihe nach von P1 bis P4 abgearbeitet werden. Der Prozess mit 8 Millisekunden Rechenzeit verzögert die Ausführung aller anderen Prozesse, was sich in der Wartezeit nie- derschlägt. Die rechte Tabelle enthält die gleichen Prozesse, die jedoch mittels der SJF-Strategie geplant wurden. Der längere Prozess verzögert nun nicht mehr alle anderen Pro- zesse, wodurch die durchschnittliche Ausführungszeit niedriger ist. Die durchschnittlich bessere Ausführungszeit spricht zwar für die SJF-Strategie, jedoch werden Prozesse mit sehr langen Rechenzeiten immer weiter aufgescho- ben, sodass sie schließlich verhungern können. Außerdem sind die genauen Re- chenzeiten der Prozesse in der Praxis nicht bekannt. Um dieses Problem zu umgehen, kann eine Abschätzung der Rechenzeiten be- rechnet werden. Voraussetzung dafür ist, dass die Prozesse gelegentlich blockie- ren oder freiwillig die CPU abgeben, sodass sie phasenweise rechnen. Ein einfa- cher Ansatz für die Abschätzung ist es, den Mittelwert der gemessenen Rechen- zeiten in jeder Rechenphase zu berechnen. Folgende Werte werden dabei benö- tigt: Ti : tatsächliche Rechenzeit in der i-ten Rechenphase (wird gemessen) Si : Schätzung für die i-te Rechenphase (wird berechnet) S1 : Schätzung für die erste Rechenphase (ist konstant) Für den Start des Prozesses ist die Schätzung S1 konstant, für Sn+1 kann der Durchschnitt der vorherigen Messergebnisse Ti berechnet werden: 1 n n i∑ S n +1 = ∗ Ti =1 Um nicht für alle Prozesse unnötig viele Werte speichern zu müssen, bzw. die Summe nicht ständig erneut zu berechnen, kann der Mittelwert rekursiv effizien- ter berechnet werden. 58  1 n−1 S n +1 = ∗ Tn + ∗ Sn n n Jedes Mal wenn der Scheduler aktiv wird, vergleicht er die Schätzungen der ein- zelnen Prozesse und verwendet diese für die Auswahl des nächsten Prozesses. In dieser Berechnung werden alle Rechenphasen gleich gewichtet, da es sich um ein arithmetisches Mittel handelt. In anderen Schätzungen können z.B. kürzlich gemessene Rechenzeiten stärker ins Gewicht fallen. Shortest Remaining Time Next | SRTN Die Shortest Remaining Time Next-Strategie wählt genauso wie SJF den Prozess mit der kürzesten verbleibenden Rechenzeit aus, mit dem Unterschied, dass es preemtive ist: Diese Strategie unterbricht den rechnenden Prozess sobald ein neu- er Prozess erzeugt wurde. Ist das der Fall, werden die voraussichtlichen Rechen- zeiten des rechnenden und des neuen Prozesses verglichen, und der mit der kür- zeren Zeit wird zuerst fortgesetzt. Prozess Ankunftszeit Rechenzeit Ausführungszeit Wartezeit P1 0 7 0-2, 9-14 2-9 P2 5 3 6-9 5-6 P3 2 4 2-4 – Es sind hier allerdings mehr Kontextwechsel nötig, da der längere Prozess zwi- schendurch unterbrochen wird. Die für den Prozesswechsel selbst benötigte Zeit wurde hier nicht mit einbezogen. Für kürzere Prozesse ist die SRTN-Strategie ef- fektiver, jedoch können lange Prozesse hier noch länger aufgeschoben werden, sodass sie ebenso wie bei der SJF-Strategie verhungern können. 2.5.2 Interaktive Systeme Round Robin (Zeitscheibenstrategie) Im Gegensatz zu den zuvor erläuterten Strategien ist es bei dieser nicht notwen- dig, die benötigte Rechenzeit der Prozesse zu kennen. Die rechenwilligen Prozesse werden in einer FIFO-Run-Queue verwaltet. Die Prozesse der Run-Queue dürfen reihum die CPU für ein bestimmtes Zeitquantum q lang verwenden. Da die Pro- zesse reihum rechnen, wird diese Strategie auch Zeitscheibenstrategie genannt. 59 Round Robin ist preemptive: Nach dem Ablauf des Zeitquantums q wird ein Timer-Interrupt ausgelöst, der den rechnenden Prozess unterbricht. Anschließend wird der nächste Prozess aus der Run-Queue ausgewählt. Dies geschieht auch wenn ein Prozess blockiert oder terminiert. Neue Prozesse werden am Ende der Queue hinzugefügt. Wenn das Zeitquantum q zu kurz gewählt wird, sind viele Kontextwechsel zwi- schen den Prozessen nötig, was wertvolle Rechenzeit kostet. Wird q andererseits zu lang gewählt, wird das System weniger reaktionsfähig, es dauert länger, bis ein Prozess erneut rechnen darf. Dafür sind weniger Kontextwechsel nötig. Dies sollte bei der Wahl von q bedacht werden. Desiree : es ist halt eig. eine queue, die Zeitscheibe alleine bringt glaube ich nicht so viel für das Ver- ständnis... Abbildung 2.12: Zeitscheibe mit drei Prozessen Desiree P1 P1 : Fände Beispiel aus Folien mit bestimmten P2 P2 P2 Zahlen und unter- schiedlichen P3 P3 q sinnvoller... Zeit Abbildung 2.13: Round-Robin Strategie ausgeführt Die Abbildung 2.13 zeigt die drei Prozesse P1 , P2 und P3 , die reihum Rechenzeit erhalten, bis sie terminieren. 60 Priority Scheduling Bei dieser Schedulingstrategie wird jedem Prozess eine Priorität zugeordnet. Da- bei gibt es pro Prioritätsklasse eine Queue, in der alle Prozesse mit der selben Priorität verwaltet werden. Die CPU bekommt stets einen Prozess mit der höch- sten Priorität zugewiesen. Innerhalb einer Prioritätsklasse werden andere Scheduling- Strategien angewandt, z.B. Round Robin. hoch Prio 1 P1 P7 Prio 2 P3 Prio 3 P4 P5 P6 niedrig Prio 4 P2 P8 Abbildung 2.14: Prozesslisten beim Priority Scheduling Priority Schedulig ist preemtive, da bei der Erzeugung eines neuen Prozesses die Priorität des neuen Prozesses mit der des aktuell rechnenden Prozesses verglichen wird. Sollte die Priorität des neuen Prozesses höher als die des rechnenden sein, dann wird die CPU dem neuen Prozess zugeordnet. Je nach Schedulingstrategie innerhalb einer Prioritätsklasse kann es zusätzliche Ereignisse geben, bei denen der rechnende Prozess unterbrochen wird, z.B. nach Ablauf eines Zeitquantums. Die Prioritäten können entweder statisch zugewiesen werden, oder dynamisch zur Laufzeit angepasst werden. Die statische Zuweisung ist einfacher, sorgt aber für ähnliche Probleme wie bei der FIFO-Strategie: Niedrig priorisierte Prozesse können verhungern. Die dynamische Zuweisung hingegen ermöglicht es, die Priorität z.B. nach Ablauf eines Zeitquantums neu zu berechnen: Die Prioritätserhöhung niedrig priorisierter Prozesse bewirkt, dass diese nicht verhungern. Die Prioritätsverringerung verhindert, dass höher priorisierte Prozesse die CPU durchgehend belegen. 61  Ein I/O-Boost ermöglicht I/O-lastige Prozesse kurzzeitig zu bevorzugen, so- dass in deren Wartezeit CPU-lastige Prozesse abgearbeitet werden können. 2.5.3 Echtzeit-Systeme Earliest Deadline First | EDF Bei dieser Strategie wird die CPU dem Prozess mit der kürzesten Deadline zuge- ordnet. Earliest Deadline First ähnelt somit dem Priority Scheduling, wobei die Deadline als Priorität gesehen wird. Diese Strategie ist sowohl preemptive, als auch non-preemptive realisierbar. Bei der preemptive-Variante wird der rechnende Prozess unterbrochen, sobald ein neuer Prozess mit kürzerer Deadline erzeugt wird. Bei der non-preemptive- Variante wird der aktuell laufende Prozess so lange nicht unterbrochen, bis er blockiert oder die CPU freiwillig abgibt. Diese Strategie ist zwar einfach zu implementieren, jedoch ist nicht sichergestellt, dass alle Deadlines eingehalten werden können. Daher ist EDF nur für Echtzeit- anwendungen mit weichen Deadlines geeignet. Rate-Monotonic Scheduling | RMS Die Prozesse werden periodisch ausgeführt, zum Beispiel alle 50 Millisekunden. Innerhalb dieser Periode muss der Prozess terminieren, das heißt die Rechenzeit muss kleiner als die Periode sein. Das Rate-Monotonic Scheduling ähnelt dem EDF-Scheduling und dem Priority Scheduling, wobei eine kürzere Periodendauer einer kürzeren Deadline, bzw. ei- ner höheren Priorität entspricht. Allerdings ist die Periodendauer bei RMS statisch einem Prozess zugeordnet. Da die Periodendauer statisch und die Rechenzeit bekannt ist, kann berechnet werden, ob die Deadlines vom System eingehalten werden können. Durch die bessere Planbarkeit wird RMS häufig in Steuerungen von Industrieanlagen einge- setzt, wo es häufiger harte Deadlines gibt. 62 Um zu berechnen, ob alle Rechenperioden realisierbar sind, wird über alle Pro- zesse aufsummiert, welchen Anteil der Periode als Rechenzeit benötigt wird: n Ri ∑ P (Ri... Rechenzeit, Pi... Periodendauer) i =1 i Das Ergebnis beschreibt zu welchem Anteil die CPU ausgelastet ist. Ist das Ergeb- nis größer als 1, dann ist sie zu «mehr als 100%» ausgelastet und die Periodendau- er kann nicht eingehalten werden. 2.5.4 Weiteres zu Schedulingstrategien Multilevel-Scheduling Wie in Abschnitt über Prozesszustände bereits erwähnt, gibt es die Möglichkeit z.B. wartende Prozesse aus dem Arbeitsspeicher auf die Festplatte auszulagern. Dies wird «Swapping» genannt, und dient dazu, falls zu wenig Arbeitsspeicher für alle Prozesse vorhanden ist, Platz für die rechnenden zu schaffen. Das Ein- und Auslagern der Prozesse ist allerdings zeitaufwändig. Weiters soll es im System eine gute Mischung von CPU-lastigen und IO-lastigen Prozessen geben, sodass alle Teile des Systems gleichmäßig ausgelastet sind. Dies wird in den bisher beschriebenen Strategien nicht beachtet. Um diese Aspekte anzugehen, wird ein mehrschichtiges Scheduling eingeführt, der die unterschiedlichen Aufgaben in drei separaten Teilen angeht. Die Mehr- schichtigkeit ergibt sich aus der Langfristigkeit der Schedulingentscheidungen. Es ist nicht zu vergleichen mit dem mehrschichtigen Scheduling von User-Level Threads, das von den unterschiedlichen Arbeitsmodi kommt. 1. Short-Term-Scheduler (STS): Dies ist der Scheduler, wie er bereits beschrie- ben wurde. Seine Aufgabe ist die Auswahl eines Prozesses aus den rechen- willigen Prozessen. Er wird sehr häufig aufgerufen. Der Dispatcher ist i.d.R. Bestandteil des Short-Term-Schedulers. 2. Medium-Term-Scheduler (MTS): Seine Aufgabe ist es, zu entscheiden wel- che Prozesse aus- bzw. eingelagert werden. Durch die Auslagerung kann er den Multiprogramming-Grad, d.h. die Anzahl der Prozesse im Arbeitsspei- cher, reduzieren. Er wird nur gelegentlich aufgerufen. 63  3. Long-Term-Scheduler (LTS): Dieser verwaltet den Übergang von erzeug- ten Prozessen zu rechenwilligen Prozessen. Damit steuert er die Mischung von CPU-lastigen und IO-lastigen Prozessen beeinflussen und kann den Multiprogramming-Grad steigern. Er wird selten aufgerufen. Scheduling unter Linux Zur Erinnerung: Linux verwendet Kernel-Level Threads, dh. der Scheduler weist einzelne Threads der CPU zu. Linux unterscheidet zwischen drei Klassen von Threads: 1. FIFO-Echtzeit-Threads: Wie der Name bereits andeutet, werden diese Threads mit einem FIFO-Scheduler geplant. Diese Threads sind nicht unterbrechbar. 2. RR-Echtzeit-Threads: Diese werden von einem Round Robin-Scheduler ver- waltet und haben daher ein zusätzliches Attribut für ein Zeitquantum. 3. Timesharing-Threads: Diese Threads sind für die meisten Prozesse gedacht. Bis Version 2.6 des Kernels wurden sie mittels einem Priority-Scheduling geplant. Ab der Version 2.6 werden die Threads mittels einem «Completely Fair Scheduler» verwaltet, der die Threads in einem Red-Black-Tree nach der verbrauchten CPU-Zeit sortiert, und stets den mit der geringsten Zeit als nächstes auswählt. Linux unterscheidet zwischen 140 Prioritäten, dabei ist 0 die höchste Priorität. Die Prioritäten 0-99 sind reserviert für Echtzeit-Threads und die Prioritäten 100-139 für Timesharing-Threads. Es ist zu beachten, dass Linux-Echtzeit-Threads nicht für Echtzeitanwendungen geeignet sind, da keine Deadlines spezifiziert werden können. 64