Multitasking

BS21 – Multitasking 03.12.98 PROZESSORZUTEILUNG Prozeßzustandsübergänge und damit eine neue Prozessorzuteilung können durch verschiedene Ereignisse ausgelöst werden. Wenn ein laufender Prozeß verdrängt wird und ihm sozusagend der Prozessor entzogen wird, kann je nach Verfahren z.B. seine Zeitscheibe abgelaufen sein, oder ein höherpriorisierter Prozeß geht in den Zustand "ready" über (siehe späteres Beispiel). Der Entzug des Prozessors kann weitere Ursachen haben:

n Ein-/Ausgabe: Interrupt „end of IO“ => Ausgangslage: Ein laufender Prozeß stößt eine E/A-Operation an und geht vom Zustand "running" in den Zustand "blocked" über. Ein anderer Prozeß wird dem Prozessor zugeteilt. Sobald die E/A-Operation beendet wird, wird der blockierte Prozeß wieder "ready". Je nach Verfahren kann dieser den laufenden Prozeß zu seinen Gunsten vom Prozessor verdrängen, z.B. wenn er höherpriorisiert ist. (siehe Tafelbild) n Programmfehler:

-- Divide by Zero -- Adreßfehler (Segmentation Violation) n Supervisor Call (SVC) => Aufruf einer BS-Kernroutine -- z.B. I/O-Aufruf, Speicheranforderung, Uhrzeit n externe Unterbrechung (Operateur, Zeitgeber o.ä.) n Maschinenfehler (Speicherfehler o.ä.)

STEUERUNG DER PROZESSE DURCH SCHEDULER UND DISPATCHER

Scheduler ¹ und Dispatcher ² , beides wichtige Prozeduren des Systemkerns, spielen bei der Steuerung der Prozesse eine entscheidende Rolle. Der Scheduler entscheidet, welcher der bereiten Prozessen als erster ausgeführt wird. Der Dispatcher hat grob gesprochen die Aufgabe, den nächsten Prozeß fortzuführen.

Wie kann nun der Zustandsübergang praktisch gesteuert werden? Wie kann ein unterbrochener Prozeß bei erneuter Prozessorzuteilung genau dort fortgesetzt werden, wo er unterbrochen wurde?

Hier ist die Aufgabe Prozeßverwaltung des Betriebssystems angesprochen. Der Systemkern ³ muß über jeden einzelnen Prozeß „buchführen“, d.h. alle relevanten Daten über jeden Prozeß sammeln, wie z.B. seinen aktuellen Zustand. Diese Angaben werden in einem Datenblock, dem Prozeßdeskriptor oder Prozeßkontrollblock (einer je Prozeß) gespeichert. Eine Prozeßtabelle wiederum ist ein Array von Prozeßdeskriptoren.

¹ To schedule = (engl.) planen, (Zeitplan) ansetzen

^{2 to dispatch = (engl.) abschicken, -senden, aufgeben; abfertigen 3} Systemkern ^{besteht aus} (1) Code-Teil ^{(ausführbare Befehle, z.B. die des Dispatchers) und} (2) Datenbereich ^{(für die Prozeßverwaltung), auf den sich der Code-Teil bezieht} hier: Datenbereich von Dispatcher und Scheduler

BS21 – Multitasking 03.12.98

Nach jedem Zeit-Interrupt sichert eine kleine Prozedur alle Registerinhalte des unterbrochenen Prozesses:

• Die Inhalte der Arbeitsregister werden auf einem eigenen Stackbereich ablegt, über den der Prozeß exklusiv verfügt.

• Auch der Befehlszähler (PC), der die Stelle angibt, wo aktueller Prozeß unterbrochen wurde, wird auf dem prozeßeigenen Stack abgelegt.

• Der Wert des so positionierten Stack Pointers wird im Prozeßdeskriptor festgehalten.

Wird dem so abgewickelten Prozeß der Prozessor wieder neu zugeteilt, wird der so gesicherte Stackpointer Aufhängepunkt für diese Aktion. Mit ihm können die restlichen Register auf ihren ursprünglichen Stand gebracht werden.

Nach diesem Abschnitt zur Registersicherung werden erst Scheduler, dann Dispatcher durchlaufen.

BS21 – Multitasking 03.12.98

Scheduler

• Der Scheduler durchläuft die Prozeß-Deskriptorliste von Anfang bis Ende ohne auf Prioritäten zu achten.

• Er verwaltet die Zeitsteuerung, (Zeitangaben in Grundtakten, aber auch Uhrzeit, Datum) d.h. er verwaltet pro Aufruf nacheinander die aktuellen Zähler der Tasks, d.h. er führt für jeden Prozeß getrennt eine Uhr/ einen Zähler Falls ein Zähler > 0 ist, dekrementiert ihn der Scheduler um eins, wenn es sich um einen Abwärtszähler handelt. Die Dekrementierung von 1 auf 0 entspricht der Zuweisung des Zustandes "ready".

Dispatcher:

Nach dem Durchlauf des Schedulers, hat der Dispatcher die Aufgabe, den nächsten Prozeß fortzuführen. Welcher dies ist, hängt von dem implemenierten Verfahren ab.

Z.B. das Round-Robin-Verfahren

• FIFO-Zuteilung

• Betriebsmittelzuteilung zeitlich beschränkt => Zeitscheibe

• in der Regel konstante Zeitscheibe; jedoch nicht zwingend

• ^{Sonderfall: verbrauchtes Zeitquantum beeinflußt Priorität => Bevorzugung von kurzer Nutzerzeit} z.B. das Vordergrund-Hintergrund-Verfahren

• zwei Prioritätsklassen:

1 -- hohe Priorität: E/A-intensive Prozesse (interaktiv, Vordergrund) 2 -- niedrige Priorität: Rechenintensive Prozesse (batch, Hintergrund)

• ^{innerhalb der Klassen: FIFO} z.B. E/A-orientiertes Verfahren drei Prioritätsklassen:

1. hohe Priorität: langsames E/A-Gerät

2. mittlere Priorität: schnelles E/A- Gerät

3. niedrige Priorität: rechenintensiv innerhalb der Klassen: FIFO Gewichtsverfahren

z.B. die priorisierte Verwaltung oder unterbrechende Steuerung, welche ich nun exemplarisch näher vorstellen möchte:

Einzelne Deskriptorblöcke sind zu einer verketteten Liste zusammengebaut. (siehe Abbildung 2) Der zum Dispatcher gehörende sog. Anker zeigt auf den ersten Deskriptorblock, von jedem Deskriptorblock zeigt wiederum ein Zeiger auf den jeweils folgenden Block. Vom Block am Ende der Kette geht kein Zeiger aus, sondern er enthält die Bezeichnung NIL. Der Prozeß am Anfang der Kette hat die höchste Priorität, der am

BS21 – Multitasking 03.12.98

A Der Dispatcher würde den Prozeß 2 fortführen. Bei weiteren Zeit-lnterrupts würde der Dispatcher nun immer den Prozeß 2 fortführen.

à Wichtig ist, daß sich ein Prozeß, der seine Aufgabe erledigt hat, selber beendet; d. h. er begibt sich in den Zustand "terminated". Das selbständige Beenden eines Prozesses kann durch eine Systemprozedur erfolgen (Kap. 2.3).

B Der Scheduler vergibt den Prozessor solange an Prozeß 3, bis dieser sich beendet oder bis ein höherpriorisierter Prozeß "ready" wird.

C Z.B. soll Prozeß 1 zyklisch laufen, und nach Ablaufen seiner Zeit wird er "ready". Der Dispatcher, der vorher den Prozessor an Prozeß 3 vergeben hat, unterbricht diesen und läßt Prozeß 1da dieser eine höhere Priorität hat - anlaufen. Prozeß 3 kommt erst wieder in den Genuß des Prozessors, wenn Prozeß 1 "terminated" ist.

Nachteile der unterbrechenden Steuerung:

L Wenn einzelne Prozesse lange laufen L Viele Prozesse wie Endlosschleifen vorhanden sind L Viele User am System arbeiten: Mehrbenutzersysteme (höher priorisierter User könnte so durch Programmierfehler alle Prozesse unter sich lahmlegen à Ungeeignet für Mehrbenutzersysteme à Round-Robin-Verfahren: Keine Prioritäten-Vergabe

BS21 – Multitasking 03.12.98

Zusammenfassend läßt sich der Ablaufplan bei einer Unterbrechung anhand von Abbildung 4 darstellen:

BS21 – Multitasking 03.12.98 SYSTEMPROZEDUREN DES KERNS

Wie bereits erwähnt, ist es wichtig, daß sich Prozesse selber beenden können. Es handelt sich hierbei um nur eine Routine, die von einzelnen Prozessen her aufgerufen werden können. Mit ihnen ist es möglich, auf den Prozeßablauf Einfluß zu nehmen.

Beenden eines Prozesses

Im Kern muß sich eine Stelle befinden, wo sich ein laufender Prozeß selber beenden kann. Man kann dies erreichen, indem man diese Stelle direkt anspringt, oder sich durch einen Return-Mechanismus dorthin begibt. Die augenfälligste Aktion wird dort sein, daß im entsprechenden Prozeßdeskriptor der Zustand "terminated" eingetragen wird. Zusätzlich muß der Stack Pointer sowie im prozeßeigenen Stack die Startadresse restauriert werden. Zusammenfassend kann man sagen, daß hier eine Initialisierung des Prozeßdeskriptors für den nächsten Neustart erfolgt.

Verzögerung eines Prozesses

Mit einer DELAY-Prozedur kann sich ein Prozeß für eine gewisse Zeit verzögern. Sie wird dann gebraucht, wenn ein Prozeß für eine konkrete Zeit warten muß. Als Beispiel wäre das Abwarten einer Tastenprellzeit zu nennen. Forderung ist, daß während des Wartens der Prozessor anderen Prozessen zur Verfügung steht. Demnach darf nicht verzögert werden, indem man Prozessorzeit durch Zählschleifen vergeudet. Das Warten eines Prozesses realisiert werden, indem ein neuer Zustand mit der Bezeichnung "delayed" eingeführt wird. Der Übergang von "running" nach "delayed" erfolgt durch die Prozedur DELAY. Die anderen Übergänge, bis auf die Beendigung eines Prozesses, werden durch den Dispatcher ausgeführt. Die DELAY-Routine benötigt im Prozeßdeskriptor einen zusätzlichen Zeitzähler. Er wird mit einem vom Prozeß übergebenen Wert belegt. Die Verwaltung dieses Zählers fällt in das Aufgabengebiet des Schedulers, der die Zeitvorgabe dekrementiert und den Prozeß, der sich im Zustand "delayed" befindet, nach Ablauf seiner Zeit wieder "ready" setzt. Hierdurch wird er fortgesetzt.

Aktivieren eines Prozesses

Oft ist es nötig, von einem Prozeß aus einen anderen zu aktivieren; besonders dann, wenn die Prozesse voneinander zeitlich abhängen. Die Prozedur ACTIVE ermöglicht eine solche Verständigung unter einzelnen Tasks. ACTIVE sucht zunächst den Deskriptor aus, auf den sich der Aktivierungsbefehl bezieht. Dort wird der Zustand "ready" eingetragen und so der Prozeß aufgeweckt. Die Übergabe des Namens bzw. der Identifikations-Nummer des betreffenden Prozesses erfolgt durch einen Parameter beim Aufruf.

Prozeßgenerierung

Beim Hochfahren des gesamten Systems muß dem Kern einmal mitgeteilt werden, welche Prozesse zur Verarbeitung anstehen. Es ist möglich, daß man abgetrennt vom Kern die Liste der Prozeßdeskriptoren, einschließlich ihrer Verkettung, aufbaut, und dem Kern nur eine Ankeradresse, die auf den ersten Deskriptor weist, übergibt. Dies führt zu einem besonders kleinen und einfachen Kern.

Viele Betriebssysteme verwenden hingegen eine CREATE-Prozedur, die es ermöglicht, von außen her Prozesse dem Kern bekannt zu machen. Sie produziert Deskriptorblöcke und hängt diese an die

BS21 – Multitasking 03.12.98 entsprechende Stelle der Liste ein. In einem Parameterblock werden die Prozeßkenndaten (Startadresse, Prozeßnamen, Zykluszeiten etc.) übergeben. Der große Vorteil dabei ist, daß man Prozesse bei Bedarf dynamisch generieren, und durch eine entsprechende Prozedur wieder löschen kann. Ferner ist die Schnittstelle zum Einketten von Prozessen transparenter, was bei der Systempflege eine große Rolle spielt.

Die erste Vorgehensweise wird durch die Verwendung von Daten mit strukturiertem Typ (z. B. records) und deren Verbindung durch Pointer vereinfacht; auf Assemblerebene können solche Ketten leicht mit Macros produziert werden. Andererseits ist es gefährlich, solche bedeutungsvolle Datenbereiche wie die Deskriptoren in die Verantwortung von außenstehenden Modulen zu geben.

Bei allen Kernprozeduren, die von Prozessen aus aufgerufen werden, ist es wichtig, den lnterrupt während ihrer Ausführung zu sperren. Dadurch wird vermieden, daß der Zeitinterrupt in einer Kernprozedur zuschlägt, was fatale Folgen haben könnte.

Die obigen Prozeduren gehören zum Standardrepertoire eines Multitasksystems und sollten generell implementiert werden. Darüber hinaus können Routinen, wie z. B. zur Verzögerung eines Prozesses bis zum Eintreffen eines lnterrupts oder zur Suspendierung einzelner Prozesse usw., hier in ähnlicher Weise eingegliedert werden.

BS21 – Multitasking 03.12.98

PROZESSE IN UNIX

n Jeder UNIX-Prozeß besteht aus einem Kern- und einem Benutzerteil (kernel part, user part). n Der Kernteil wird nur aktiv, wenn im Benutzerteil ein Systemaufruf erfolgt. Er hat einen eigenen Instruktionszeiger und Stack.

n Der Betriebssystemkern verwaltet zwei wichtige Datenstrukturen: -- die Prozeßtabelle (process table) und -- die Benutzerstruktur (user structure).

n Die Prozeßtabelle ist immer im Hauptspeicher (resident) und enthält Informationen über alle Prozesse:

-- Scheduling Parameter: welcher Prozeß kommt als nächstes zur Ausführung? (Priorität, verbrauchte CPU Zeit etc.) -- Speicherabbild (Memory Image): wo befinden sich die Speicherbereiche der Prozesse? (Code-, Stack-, Datensegmente, ggfs. Seitentabelle) -- Signale: welche Signale werden ignoriert, gesendet etc.? -- Verschiedenes: Prozeßstatus, -nummer, etc.

n Die Benutzerstruktur enthält Informationen, die nur notwendig sind, wenn der Prozeß aktiv ist. Sie wird ggfs. mit dem Prozeß ausgelagert:

n Maschinenregister n Status des Systemaufrufs n „File Descriptor“-Tabelle n Verwaltungsinformationen n Kernel Stack

Wenn ein FORK-Aufruf erfolgt ⁴ ,

• ermittelt der Kernteil des ausführenden Prozesses einen freien Platz in der Prozeßtabelle und

• kopiert alle eigenen Einträge in den freien Platz für den zu erzeugenden Kindprozeß.

• Anschließend wird Speicherplatz für den Kindprozeß allokiert und alle Speicherbereiche (insbesondere auch die Benutzerstruktur) des Elternprozesses werden dorthin kopiert.

⁴ UNIX-Prozeßerzeugung

Der Systemaufruf fork() erzeugt eine exakte Kopie (Kindprozeß) des ausführenden Prozesses (Elternprozeß). Eltern- und Kindprozeß haben eigene private Speicherbereiche. Lokale Änderungen sind für den anderen Prozeß unsichtbar. Geöffnete Dateien werden von Eltern- und Kindprozessen gemeinsam benutzt. Änderungen sind global sichtbar. Die Unterscheidung von Eltern- und Kindprozeß erfolgt durch den vom Systemaufruf fork() zurückgelieferten Wert:

-- Der Kindprozeß erhält den Wert 0.

-- Der Elternprozeß erhält eine positive Zahl, die Prozeßnummer (pid, process identifier) des Kindprozesses.

-- Ein Prozeß kann seine eigene Nummer mittels des Systemaufrufs getpid() erfragen.

BS21 – Multitasking 03.12.98 Scheduling in UNIX

n prioritätenbasiert n Zuteilungsverfahren:

-- „round robin“ innerhalb der Prioritätenklassen -- Prozeßwechsel erfolgt bei Zeitscheibenablauf oder Blockierung eines Prozesses durch Ein-/Ausgabe Prozeßstruktur

Ein laufendes Unix-System besteht (wie das Dateisystem) aus einer baumartigen, hierarchischen Struktur von Prozessen. Jedem Prozeß ist eine eindeutige Nummer, die PID (Process IDentificatiton Number) zugeordnet.

DER LOGIN-PROZEß

Die Wurzel der Prozeßstruktur, das ist der Prozeß mit der PID 0, wird beim Start des Systems erzeugt. Dieser Prozeß startet mehrere Systemprozesse, darunter den Prozeß init mit der PID 1. Der Prozeß init wiederum ist der Urvater aller Benutzer- und der meisten Dämonprozesse (das sind vom System abgesetzte Hintergrundprozesse, die in zyklischen Zeitabständen ausgeführt werden und diverse Dienste zur Verfügung stellen bzw. bestimmte administrative Aufgaben erledigen).

Nach erfolgreicher Anmeldung über den login-Prozeß wird für jeden Benutzer ein neuer eigener Prozeß, nämlich die systemseitig definierte login-Shell, gestartet. Mit dem login wird der Benutzer Eigentümer genau dieses Prozesses und damit auch aller von diesem Prozeß erzeugten Kindprozesse. Verläßt der Benutzer die login-Shell (exit), so ist seine Sitzung beendet, was gleichbedeutend mit einem Ausloggen ist. Die Prozeßkenndaten

Einen Überblick über die laufenden Prozesse kann man mit dem Kommando ps (process status) erhalten. Beispiel:

Kommando ps entsprechende Prozeß mit der PID 197.

BS21 – Multitasking 03.12.98 Will man sich alle im System laufenden Prozesse ansehen, sind die Optitonen -a, -e und -f von Bedeutung; das folgende Beispiel zeigt die Anwendung. Beispiel:

UID Username des Prozeßeigentümers, PID Prozeß-Nummer, PPID Eltern-Prozeß-Nummer (Parent PID), C systeminterner Scheduling-Parameter, TTY Name der Dialogstation, von der dieser Prozeß gestartet wurde (? = keiner Dialogstation zugeordnet), TIME bisher vom Prozeß verbrauchte CP-Zeit, COMMAND Name des Kommandos, welches diesen Prozeß gestartet hat.

BS21 – Multitasking 03.12.98 Jedem Prozeß ist eine Reihe von Prozeßkenndaten zugeordnet. Einen weiteren Teil dieser Daten kann man sich mit dem Kommando -ps -ael anzeigen lassen:

Dabei bedeutet die Ausgabe des Kommandos folgendes (hier sind erläutert, die unter –ps eaf nicht oder in anderer Form vokamen):

Systemintern benutzte Flags; z.B. bedeutet 10, daß dieser Prozeß im Arbeitsspeicher liegt F bezeichnet den Zustand des Prozesses: S Prozeß ist aktiv, 0 Prozeß wurde gerade kreiert, I Prozeß wurde angehalten, T Prozeß wurde suspendiert, S Prozeß ist im lauffähigen Zustand in der Warteschlange, R Prozeß ist fehlerhaft terminiert (Zombie), Z Prozeß wächst und wartet auf mehr Speicher, X UID-Nummer des Prozeßeigentümers, UID aktuelle Priorität des Prozesses (je kleiner PRI, desto größer die Priorität), PRI Nice-größe für die Prioritätsberechnung, NI Hauptspeicher- oder Plattenadresse des Prozesses, ADDR Größe des Prozesses im Hauptspeicher in kByte, SZ WCHAN Adresse eines Events, auf die der Prozeß wartet