Einführung in Betriebssysteme


von Prof. Jürgen Plate

2 Prozesse

2.1 Programme, Prozeduren, Prozesse und Instanzen

Programm:

Die Lösung einer Programmieraufgabe (=Algorithmus) wird in Form eines Programms realisiert. Teillösungen werden dabei als Prozeduren (Unterprogramme) formuliert, welche nach Beendigung ihrer Arbeit zum aufrufenden übergeordneten Programm zurückkehren. Damit die Leistungen des Betriebssystemkerns problemlos in Anwenderlösungen eingebunden werden können, sind sie ebenfalls als Prozeduren realisiert. Ein Programm (Prozedur, Unterprogramm) besteht aus: Beide Komponenten sind problemorientiert.

Prozeß:

Wird ein Programm (Prozedur) unter der Kontrolle eines Betriebssystems (genauer gesagt unter der Kontrolle eines Betriebssystemkerns) ausgeführt, so wird dieser Ablauf als Prozeß (engl. Task) bezeichnet. Diese Betrachtungsweise macht es möglich, daß mehrere Programme gleichzeitig als Prozesse parallel auf einem sequentiell arbeitenden Rechnersystem (unabhängig von der realen Anzahl Prozessoren) ablaufen können. Als Sonderfall gilt die Ausführung mehrerer Prozesse auf einem Prozessor. Bei der Ausführung von Prozessen entstehen Daten, die durch den Betriebssystemkern verwaltet werden. Diese werden Statusinformationen genannt und sind systemabhängig, z. B. Registerinhalte.

Die Funktionalität des Betriebssystemkerns bezüglich der Verwaltung von Prozessen ist bei der Ausführung von n Prozessen auf einem Prozessor äquivalent der Verwaltung auf m > 1 Prozessoren. Dabei kann das Verhältnis m : n sowohl statisch als auch dynamisch änderbar sein.

Als weitere Komponente wird beim Ablauf eines Programms ein Kellerspeicher (Stack) aufgebaut. Somit läßt sich ein Prozeß modellhaft folgendermaßen darstellen.

Alle vier Komponenten, die bei der Ausführung eines Programms (einer Prozedur) beteiligt sind, werden als Instanz zusammengefaßt.

Instanz:

Eine Instanz umfaßt das Tupel (C, D, S, I):

C:Codesegment-->problemorientiert
D:Datensegment-->problemorientiert
S:Stacksegment-->system-/problemorientiert
I:Statusinformation-->systemorientiert

Die physische Anordnung dieser Komponenten im Arbeitsspeichers eines Rechners kann in unterschiedlichen Betriebssystemen verschieden sein.
Wir halten also fest:

Prozeßmodell

2.2 Prozeßzustände

Während seiner Abarbeitung kann ein Prozeß verschiedene Zustände einnehmen:

Die Situation in der Hardware stellt sich etwa folgendermaßen dar. Im Speicher liegen die einzelnen Instanzen der Prozesse. Jeweils ein Prozeß wird der CPU zugeteilt.

Zustandswechsel eines Prozesses:

Zu jedem Prozeß legt das BS einen Prozeßsteuerblock (process control block = PCB) in der Prozeßtabelle ab, der alle notwendigen Informationen über einen Prozeß enthält, z. B.:

Zusätzlich zum PCB werden noch weitere, zum Prozeß gehörige Daten geführt, auf die er aber nur im Zustand "running" Zugriff hat. Dazu gehören:

2.3 Prozeßhierarchie und Prozeßrechte

Ein Prozeß kann einen neuen Prozeß starten (fork, spawn); ein solcher Prozeß heißt "Kindprozeß" oder "Sohnprozeß" (child process) und der Erzeuger-Prozeß wird "Elternprozeß" oder "Vaterprozeß" (parent process) genannt.

Die Prozeßrechte sollen anhand des Betriebssystems UNIX erläutert werden. Jeder Prozeß hat im Verlauf seiner Existenz zwei Benutzeridentifikationen:
Die "reale" Benutzer-ID bezeichnet den Benutzer, der für den Ablauf des Prozesses verantwortlich ist. Sie bleibt in der Regel konstant. Die "effektive" Benutzer-ID kann sich jedoch beliebig oft ändern und bestimmt jeweils die momentanen Rechte des Prozesses in Bezug auf Dateizugriffe und andere Mechanismen, die benutzerabhängigen Einschränkungen unterliegen.

Die Änderung der effektiven Benutzer-ID kann auf zweierlei Art erfolgen: Wenn der Prozeß ein Programm eines anderen Benutzers ausführen möchte, dann prüft das Betriebssystem zuerst seine Berechtigung dazu (über die entsprechenden Dateizugriffsrechte). Falls die Zugriffsrechte der Programmdatei außerdem das sogenannte "setuid-Bit" enthalten, dann wird die effektive Benutzer-ID des Prozesses mit der Eigentümerkennung des aufgerufenen Programms überschrieben, und der Prozeß hat demzufolge jetzt die Rechte des Eigentümers des Programms.
Die zweite Möglichkeit zur Veränderung der effektiven Benutzer-ID ist der explizite Aufruf der Systemfunktion setuid(). So ist es möglich, die effektive Benutzer-ID so zu verändern, daß sie den Wert der realen Benutzer-ID erhält oder den Wert der effektiven Benutzer-ID, die der Prozeß bei seiner Aktivierung von seinem Vater "geerbt" hat.

2.4 Prozeß-Operationen des BS

Aus dem bisher gesagten kann man bestimmte Operationen ableiten, die das Betriebssystem zur Steuerung und Kontrolle von Prozessen ausführt. Die wichtigsten Prozeß-Operationen sind in der folgenden Tabelle zusammengefaßt.

CreateErzeugen eines Prozesses (z.B. Laden eines Programms)
  • Vergabe einer PID, Anlegen eines PCB in der Prozeßtabelle
  • Allokieren des benötigten Speichers
  • Reservieren der benötigten Ressourcen
  • Vergabe einer Priorität
KillLöschen eines Prozesses
  • Löschen aller Einträge aus den Systemtabellen
  • Freigabe von Speicher und Ressourcen (z.B. Dateien schließen)
  • Löschen aller Abkömmlinge (Kindp., Enkelp., usw.)
SuspendSuspendieren eines Prozesses
  • Suspendierung normalerweise nur bei Systemüberlastung durch Prozesse höherer Priorität, Wiederaufnahme erfolgt sobald möglich.
ResumeWiederaufnehmen eines suspendierten Prozesses
  • Suspendierung normalerweise nur bei Systemüberlastung durch Prozesse höherer Priorität, Wiederaufnahme erfolgt sobald möglich.
BlockBlockieren eines Prozesses
WakeupAufwecken eines blockierten Prozesses
DispatchCPU an einen Prozeß zuteilen
ChangePriorität eines Prozesses ändern

In der Tabelle wird erstmals die Möglichkeit der "Suspendierung" eines Prozesses aufgeführt. Wird das System durch Prozesse höherer Priorität überlastet (kein Speicher mehr frei, keine Dateihandles mehr frei, Prozesstabelle voll, etc.), müssen Prozesse aus dem Speicher entfernt und z. B. auf die Platte ausgelagert werden. Im einfachsten Fall reicht auch manchmal die Auslagerung eines Eintrags in der Prozeßtabelle in eine andere Tabelle. Sobald sich die Situation entspannt hat, wird der Prozeß wieder in den alten Stand zurückversetzt. Bei der Suspendierung wird man natürlich solche Prozesse zuerst auslagern, die sowieso auf ein Ereignis warten. Durch die Suspendierungsmöglichkeit erweitert sich das Diagramm der Prozeßzustände:

2.5 Prozeß-Synchronisation

In einigen Multitasking-Betriebssystemen teilen sich verschiedene Prozesse gemeinsame Betriebsmittel. Bei gleichzeitigem Zugriff zweier Prozesse auf diese Betriebsmittel kann es zu Inkonsistenzen der Daten kommen, die u. U. selten auftreten und sehr schwer aufzuspühren sind.
Kooperierende nebenläufige Prozesse müssen daher wegen der zwischen ihnen vorhandenen Abhängigkeiten miteinander synchronisiert (koordiniert) werden. Prinzipiell lassen sich zwei Klassen von Abhängigkeiten unterscheiden: Ohne eine solche Sperrung entstehen Datenverluste, z. B. in folgenden Fall: Damit bleibt die Änderung X(0) nach X(1) aus dem Prozeß A unberücksichtigt.

Oder auch bei folgendem Beispiel:

Solche Situationen heißen zeitkritsche Abläufe. Programmabschnitte, die auf gemeinsam benutzte Daten zugreifen, heißen kritische Abschnitte.

Fehler in zeitkritischen Abläufen sind sehr schwer erkennbar, da sie nur sehr selten auftreten. Sie können nur durch wechselseitigen Ausschluß vermieden werden. Kritische Abschnitte treten überall auf, wo zwei oder mehr Prozesse auf einem Computer oder in einem Netz um mindestens eine Ressource konkurrieren, die sie schreibend benutzen wollen. Kritische Abschnitte können aber auch überall da auftreten, wo mehrere Prozesse um eine Ressource konkurrieren, die sie schreibend benutzen. Das trifft besonders auf Datenbankserver zu (z. B. Reservierungssysteme, zentrale Karteien, usw.).

Vier Bedingungen für eine gute Lösung (nach Tanenbaum):

  1. Höchstens ein Prozeß darf sich in einem kritischen Abschnitt aufhalten. (Korrektheit)
  2. Es dürfen keine Annahmen über Ausführungsgeschwindigkeit und Anzahl der Prozessoren gemacht werden.
  3. Kein Prozeß, der sich in einem kritischen Abschnitt befindet, darf andere blockieren.
  4. Kein Prozeß soll unendlich lange warten müssen, bis er in einen kritischen Bereich eintreten darf.
Die letzten beiden Punkte dienen der Stabilität, sie sollen Prozeßverklemmungen verhindern.

Beispiele für zeitkritische Abläufe

1. Das Erzeuger-Verbraucher-Problem:
Der Erzeuger E stellt ein Produkt her und stellt es in einen begrenzten Pufferspeicher. Verbraucher V entnimmt dem Puffer ein Stück des Produktes, um es zu verbrauchen. Beides geschieht zu zufälligen Zeitpunkten. Der Puffer wird von beiden gemeinsam verwaltet. Solche Erzeuger-Verbraucher-Probleme treten beispielsweise bei Pipes auf (Ein Prozeß erzeugt Daten, der andere verarbeitet sie weiter.) Wenn der Erzeuger ein Produkt in den Puffer stellt, muß er den Verbraucher wecken. Analog muß der Verbraucher den Produzenten wecken, wenn er ein Produkt aus dem Puffer entnimmt. Tanenbaum verwendet dafür die Funktionen SLEEP und WAKEUP. Er zeigt eine Lösung für das Erzeuger-Verbraucher-Modell, die einen fatalen Fehler zuläßt: 
#define N 100                  /* Puffergröße   */
int count = 0;                 /* Tatsächlicher Pufferinhalt */

void producer (void)
  }
  tinhalt item;
  while (1)                    /*  Endlosschleife */
    }
    produce_item (&item);  /*  Erzeuge 1 Stück */
    if (count == N) SLEEP();   /*  Falls Puffer voll, schlafen */
    enter_item (item);         /*  lege erzeugtes Stück in Puffer  */
    count++;
    /*  wenn Puffer vor dem Weiterzählen leer war, Verbraucher wecken */
    if (count == 1) WAKEUP(consumer);
    }
  }

void consumer (void)
  }
  tinhalt item;
   while (1)                   /*  Endlosschleife */
     }
     if (count == 0) SLEEP();  /*  Falls Puffer leer, schlafen */
     remove_item (item);       /*  entnehme dem Puffer ein Stück */
     count--;                  /*  Pufferinhalt korrigieren */
     /*  wenn Puffer vor Korrigieren voll war, Erzeuger wecken */
     if (count == N-1) WAKEUP(producer);  
     consume_item (&item);    /* verbrauche 1 Stück */
     }
  }
Die Funktionen sollen selbstständig laufende Programme repräsentieren, die beide zu beliebigen Zeitpunkt durch einen Scheduler-Eingriff unterbrochen oder wieder aktiviert werden können.
Wenn der Consumer schläft, weil der Puffer leer ist, muß man nicht davon ausgehen, daß der Puffer immer leer bleibt. Der Producer kann ja zwischendurch den Prozessor zugeteilt bekommen, etwas in den Puffer legen und den Consumer wieder wecken.
Umgekehrt schläft der Producer, wenn der Puffer voll ist. Während er schläft, kann der Consumer den Prozessor zugeteilt bekommen, etwas verbrauchen (so daß im Puffer wieder Platz wird) und den Producer wieder wecken.
Der Fehler tritt bei folgendem Szenario auf:

Der Puffer ist leer und der Verbraucher stellt das fest (count = 0). Genau jetzt unterbricht der Scheduler den Verbraucher und startet den Produzenten. Dieser legt ein Produkt in den Puffer, setzt count auf 1 und startet WAKEUP. Wenn der Verbraucher vom Scheduler wieder die CPU zugeteilt bekommt, ist er noch wach. Der Weckruf verhallt ungehört, weil ja der Verbraucher nicht schläft. Der Verbraucher wertet die vorher festgestellte Tatsache "count = 0" aus und geht schlafen. Es gibt für den Produzenten keinen Anlaß, nochmals zu wecken. Der Verbraucher wird nie mehr geweckt.

Ursache für diese Blockierung ist eine Prozeßunterbrechung im kritischen Abschnitt zwischen Erkennung der Bedingung, die zum Aufruf von SLEEP führt und dem SLEEP-Kommando selbst. Die gleiche Situation würde auftreten, wenn der Produzent zwischen der Erkenntnis, daß der Puffer voll ist (free = 0) und dem Schlafengehen unterbrochen wird.

2. Das Problem des schlafenden Friseurs: Dieses Modell geht davon aus, daß beide nach dem Zeitscheibenprinzip nur abwechselnd handeln können.
Ein Friseur bedient, sobald er Zeit dafür hat, ankommende oder wartende Kunden. Der Warteraum ist beschränkt auf N Stühle.

Die kritische Situation besteht darin, daß der Kunde zwischen der Dekrementierung von count und der Frage "Ist count gleich 0" ankommt und den Friseur wecken kann, obwohl der sich noch gar nicht schlafen gelegt hat.

Lösungsversuche für das Problem der kritischen Abschnitte

  1. Einfachste Lösung: Vor Eintritt in den kritischen Bereich alle Interrupts sperren und sie nach Verlassen des kritischen Bereichs wieder freigeben. Damit kann der Scheduler nicht während des kritischen Abschnitts den Prozeß unterbrechen.
    Nachteil: Kein verdrängendes Multitasking mehr. Der Anwenderprozeß kann den Scheduler blockieren (gewollt oder ungewollt durch einen Programmfehler).
  2. Verfahren mit gegenseitigem Ausschluß
    Der Programmabschnitt, in dem ein Zugriff zu dem nur exklusiv nutzbaren Betriebsmittel (z. B. die gemeinsamen Daten) erfolgt, wird kritischer Abschnitt genannt. Es muß verhindert werden, daß sich zwei Prozesse gleichzeitig in ihren kritischen Abschnitten befinden.
  3. Semaphore
    Bisher haben die Prozesse ihren Eintritt in den kritischen Abschnitt selbst gesteuert. Die folgenden Techniken erlauben es dem Betriebssystem, Prozessen den Zutritt zum kritischen Abschnitt zu verwehren. Im Zusammenhang mit Algol 68 entwickelte Dijkstra das Prinzip der Arbeit mit Semaphoren. Für jede zu schützende Datenmenge wird eine Variable (Semaphor) eingeführt (binäre Variable oder nicht-negativer Zähler).
    Ein Semaphor (Sperrvariable, Steuervariable) signalisiert einen Zustand (Belegungszustand, Eintritt eines Ereignisses) und gibt in Abhängigkeit von diesem Zustand den weiteren Prozeßablauf frei oder versetzt den betreffenden Prozeß in den Wartezustand.

    Beim Bemühen um unteilbare Ressourcen (z. B. den Prozessor) wird eine binäre Variable verwendet, bei N Teil-Ressourcen (z. B. Arbeitsspeicher-Segmente oder Plätze in einem Puffer) kommen Werte von 1 bis N vor. Die binären Semaphore werden auch "Mutexe" (von "Mutual exclusion") genannt, jene vom Typ Integer auch "Zähl-Semaphore".

    Semaphore für den gegenseitigen Ausschluß sind dem jeweiligen exklusiv nutzbaren Betriebsmittel zugeordnet und verwalten eine Warteliste für dieses Betriebsmittel. Sie sind allen Prozessen zugänglich. Semaphore für die Ereignissynchronisation zweier voneinander datenabhängiger Prozesse sind diesen Prozessen direkt zugeordnet. Sie dienen zur Übergabe einer Meldung über das Ereignis zwischen den Prozessen.

    Zur Manipulation und Abfrage von Semaphoren existieren zwei unteilbare, d. h. nicht unterbrechbare Operationen (Semaphor S):

    Lösungsmöglichkeit für Erzeuger-Verbraucher-Synchronisation (Vorbesetzung der Semaphore: start = 0; finish = 0):

    Produzent: Konsument:
      while (1)
    {
    while (!buffer-full)
      write_into_buffer();
    signal(start);   /* V-Operation */
    wait(finish);    /* P-Operation */
    }
    		  
      while (1)
    {
    wait(start);           /* P-Operation */ 
    while(!buffer-empty)
      read_from_buffer();
    signal(finish);        /* V-Operation */
    }

  4. Ereigniszähler
    Für einen Ereigniszähler E sind drei Operationen definiert: Damit kann E nur wachsen, nicht kleiner werden! E sollte mit 0 initialisiert werden. Die hier gezeigte Produzent-Konsument Lösung verwendet die Operation read() nicht, andere Sychronisationsprobleme machen diese Operation dennoch notwendig. Hier arbeitet der Puffer als Ringpuffer.
    Anmerkung: Mit % wird der Modulo-Operator gekennzeichnet (= Rest der ganzzahligen Division). 
    #define N 100                                     /* Puffergröße */

eventcounter inputcounter = 0, outputcounter = 0; /* Ereigniszaehler */
int inputsequence = 0, outputsequence = 0;

producer()
    {
    tinhalt item;   
    while (1)
      {
      produce(&item);
      inputsequence = inputsequence + 1;
      await(outputcounter,inputsequence-slots);
      buffer[(inputsequence - 1) % N] = item;
      advance(inputcounter);
      }
    }

consumer()
    {
    tinhalt item;

    while (1)
      {
      outputsequence = outputsequence + 1;
      await(inputcounter,outputsequence);
      item = buffer[(outputsequence - 1] % N);
      advance(outputcounter);
      consume(&item);
      }
    }
    Die Ereignis-Zähler werden nur erhöht, nie erniedrigt. Sie beginnen immer bei 0. In unserem Beispiel werden zwei Ereignis-Zähler verwendet. inputcounter zählt die Anzahl der produzierten Elemente seit dem Start. outputcounter zählt die Anzahl der konsumierten Elemente seit dem Start. Aus diesem Grunde muß immer gelten: outputcounter <= inputcounter. Sobald der Produzent ein neues Element erzeugt hat, prüft er mit Hilfe des er den await-Systemaufrufs, ob noch Platz im Puffer vorhanden ist. Zu Beginn ist outputcounter = 0 und (inputsequence - N) negativ - somit wird der Produzent nicht blockiert. Falls es dem Produzenten gelingt N+1 Elemente zu erzeugen, bevor der Konsument startet, muß er warten, bis outputcounter = 1 ist. Dies tritt ein, wenn der Verbraucher ein Element konsumiert. Die Logik des Konsumenten ist noch einfacher. Bevor das m-te Element konsumiert werden kann, muß mit await(inputcounter,n) auf das Erzeugen des m-ten Elementes gewartet werden. Auf die Probleme, die bei der Konkurrenz von Prozessen um exklusiv nutzbare Betriebsmittel auftreten, wird in Kapitel 4.5 eingegangen.

    2.6 Prozeß-Kommunikation

    Bei Multitasking-Betriebssystemen spielt die Kommunikation bzw. Synchronisation zwischen den quasiparallel ablaufenden Prozessen eine herausragende Rolle. Die Gründe dafür sind vielfältig. Zum einen werden größere Softwaresysteme häufig als Systeme mit mehreren kooperierenden Prozessen gestaltet. Diese müssen normalerweise in ihren Abläufen synchronisiert werden. Ferner müssen häufig Daten von einem Prozeß zum anderen transferiert werden. Ein anderer Grund liegt im Problem der kritischen Abschnitte von Prozessen beim Zugriff auf nicht gemeinsam benutzbare Betriebsmittel. Auch hier sind Synchronisationsmethoden erforderlich, die den gegenseitigen Ausschluß gewährleisten (siehe oben: Semaphore). Einige Möglichkeiten der Prozeß-Kommunikation (Interprocess Communication (IPC) sind:

    Selbst bei sehr einfachen Betriebssystemen ist eine IPC notwendig, da zumindest eine Kommunikation zwischen einem Prozeß und dem Scheduler möglich sein muß.

    2.7 Prozeß-Scheduling

    In Multitasking-Betriebssystemen ist ein spezieller Prozeß notwendig, der aus den bereiten Prozessen den nächsten aktiven Prozeß auswählt. Sobald mehr als ein Prozeß den Zustand "bereit" besitzt, muß der Scheduler des Betriebssystems entscheiden, welcher Prozeß die CPU erhält (wir gehen zur Vereinfachung von einem System mit nur einem Prozessor aus). Kriterien für einen guten Scheduler sind:

    Bei Multitasking-Betriebssystemen werden zwei Grundsysteme für das Scheduling unterschieden:

    Scheduling-Strategien

    Bei kooperativem Multitasking oder ereignisgesteuerten Schedulern wird die Zuteilungsstrategie über Prioritäten gesteuert, wobei man beim kooperativen System von relativem Vorrang spricht (der erst nach Freigabe der CPU durch den aktiven Prozeß wirksam wird) und beim ereignisgesteuerten System vom absoluten Vorrang (der sofort zum Prozeßwechsel führt).
    Die Zeitscheibensteuerung kann als Sonderfall der Ereignissteuerung betrachtet werden, das Ereignis ist in diesem Fall der Ablauf der zugeteilten Zeitscheibe.

    Einige Strategien, die in der Praxis verwendet werden, sind:

    In Dialogsystemen wird normalerweise Round Robin verwendet, um den Benutzern akzeptable Antwortzeiten zu bieten. Bei Batchbetrieb und gemischten Systemen kommen oft Kombinationen der o. g. Strategien vor - z. B. getrenntes Scheduling für Dialog- und Batchbetrieb.

    2.8 Beispiele

    Realzeitbetriebssysteme arbeiten in der Regel mit Zeitscheibenverfahren, wobei zusätzliche Bedingungen hinzukommen. Ereignisse (in der Regel Hardware- oder Software-Interrupts) müssen innerhalb einer bestimmten Sollzeit bearbeitet werden (Echtzeitbedingung). Daher findet sich hier häufig eine Aufteilung der Programme in einzelne Threads (bei Realzeitbetriebssystemen auch oft "Task" genannt).

    Zum vorhergehenden Abschnitt Zum Inhaltsverzeichnis Zum nächsten Abschnitt

    Copyright © FH München, FB 04, Prof. Jürgen Plate