Multitasking. Prozesssteuerung durch Scheduler und Dispatcher

INHALT:

STEUERUNG DER PROZESSE DURCH SCHEDULER UND DISPATCHER
BESTANDTEILE DES PROZEßDESKRIPTORS
SCHEDULER
DISPATCHER

SYSTEMPROZEDUREN DES KERNS
BEENDEN EINES PROZESSES
VERZÖGERUNG EINES PROZESSES
AKTIVIEREN EINES PROZESSES
PROZEßGENERIERUNG

PROZESSE IN UNIX
SCHEDULING IN UNIX
PROZEßSTRUKTUR
DER LOGIN-PROZEß
DIE PROZEßKENNDATEN

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:

- 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)
- Supervisor Call (SVC) => Aufruf einer BS-Kernroutine
- z.B. I/O-Aufruf, Speicheranforderung, Uhrzeit
- 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.

Bestandteile des Prozeßdeskriptors:(siehe Abbildung 1)

- Prozeßidentifikation (ID-Nr., Name, ...) n Berechtigungen (Prioritäten, Zugriffsrechte auf Geräte, ...)
- Startadresse des Prozesses (dorthin verzweigt der Dispatcher, wenn er den Prozeß erstmalig/erneut anlaufen lassen will)
- Prozeßzustand (aktiv, blockiert, bereit) n Sicherungsbereich bei Unterbrechung (Stack, Register, ...)
- Verwaltungsdaten (Betriebsmittelbedarf, CPU-Zeit, ...)
- evt. weitere Prozeßkennzeichen (aktueller Zähler, Intervallzeitvorgabe, ...)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Exemplarischer Prozeßdeskriptorblock

- ach 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.

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

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".

Beispiel:

Vorgaben: Grundtakt = 10ms, Prozeß P soll jede Sekunde einmal laufen · aktueller Zähler und Intervallvorgabe :=100

- Scheduler setzt Prozeß erstmalig nach einer Sekunde auf "ready"
- D.h. nachdem er den Zähler 100 mal herabgesetzt hat, also nach 100 * 10ms = 1000ms = 1sek · der Prozeß wird im späteren Verlauf ausgeführt
- Durch Laden des aktuellen Zählers mit der Intervallzeitvorgabe wird der nächste Start (1 Sek später) vorbereitet.

Dispatcher:

- ach 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

Ende der Kette die niedrigste. Die Prioritäten der Prozesse können dynamisch verändert werden, indem die Zeiger Wie gesagt hat nach dem Durchlauf des Schedulers, der Dispatcher die Aufgabe, den nächsten Prozeß fortzuführen, im Falle der unterbrechenden Steuerung ist dies des Prozeß mit höchster Priorität = der erste in der Kette der Deskriptoren, der den Zustand "ready" trägt.

So kann ein Prozeß zugunsten eines anderen unterbrochen werden, daher die Bezeichnung unterbrechende Steuerung.

Beispiel: (Abbildung 3) 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).

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ß 1 -da dieser eine höhere Priorität hat - anlaufen. Prozeß 3 kommt erst wieder in den Genuß des Prozessors, wenn Prozeß 1 "terminated" ist.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Verkettete Deskriptoren

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Priorisierendes Verfahren

Nachteile der unterbrechenden Steuerung:

- Wenn einzelne Prozesse lange laufen

- Viele Prozesse wie Endlosschleifen vorhanden sind

- 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

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

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Ablaufplan bei Unterbrechung

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

PROZESSE IN UNIX

- Jeder UNIX-Prozeß besteht aus einem Kern- und einem Benutzerteil (kernel part, user part).
- Der Kernteil wird nur aktiv, wenn im Benutzerteil ein Systemaufruf erfolgt. Er hat einen eigenen Instruktionszeiger und Stack.
- Der Betriebssystemkern verwaltet zwei wichtige Datenstrukturen:
- die Prozeßtabelle (process table) und
- die Benutzerstruktur (user structure).
- 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.
- Die Benutzerstruktur enthält Informationen, die nur notwendig sind, wenn der Prozeß aktiv ist. Sie wird ggfs. mit dem Prozeß ausgelagert:
- Maschinenregister
- 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.

Scheduling in UNIX

- prioritätenbasiert
- 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).

- ach erfolgreicher Anmeldung über den login-Prozeß wird für jeden Benutzer ein neuer eigener Prozeß,

- ä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:

Abbildung in dieser Leseprobe nicht enthalten

Zwei Prozesse des Benutzers werden angezeigt, nämlich die Korn-Shell mit der PID 184 und der dem Kommando ps entsprechende Prozeß mit der PID 197.

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:

Abbildung in dieser Leseprobe nicht enthalten

[...]

---

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

² to dispatch = (engl.) abschicken, -senden, aufgeben; abfertigen

³ 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

⁴ 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.