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 Prozess erzeugt Daten, der andere verarbeitet sie weiter).

• Der Erzeuger muss zuerst prüfen, ob noch Platz im Puffer ist, bevor er ein Produkt ablegen kann.
  Er muss dann auch den Produktzähler count erhöhen. Ist der Puffer voll, muss er warten (d.h. sich in den Zustand blocked begeben).
• Der Verbraucher muss prüfen, ob der Puffer nicht leer ist, bevor er etwas entnimmt. Er muss dann count dekrementieren. Ist nichts im Puffer, muss er warten.

Wenn der Erzeuger ein Produkt in den Puffer stellt, muss er den Verbraucher wecken. Analog muss 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ässt:

#define N 100                  /* Puffergroesse   */

int count = 0;                 /* Tatsaechlicher Pufferinhalt */



void producer (void)

{

  tinhalt item;

  while (1)                    /*  Endlosschleife */

  {

    produce_item (&item);      /*  Erzeuge 1 Stueck */
    if (count == N) SLEEP();   /*  Falls Puffer voll, schlafen */
    enter_item (item);         /*  lege erzeugtes Stueck in Puffer  */
    count++;
    /*  wenn Puffer vor dem Weiterzaehlen 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 Stueck */
     count--;                  /*  Pufferinhalt korrigieren */
     /*  wenn Puffer vor Korrigieren voll war, Erzeuger wecken */
     if (count == N-1) WAKEUP(producer);
     consume_item (&item);    /* verbrauche 1 Stueck */
   }
}

Die Funktionen sollen selbstständig laufende Programme repräsentieren, die beide zu beliebigen Zeitpunkt durch einen Eingriff des Schedulers unterbrochen oder wieder aktiviert werden können.

Wenn der Consumer schläft, weil der Puffer leer ist, muss man nicht davon ausgehen, dass 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 dass im Puffer wieder Platz wird) und den Producer wieder wecken.

Der Fehler tritt bei folgendem Szenario auf:

Ursache für diese Blockierung ist eine Prozessunterbrechung 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, dass der Puffer voll ist (free = 0) und dem Schlafengehen unterbrochen wird.

2. Das Problem des schlafenden Friseurs:

Dieses Modell geht davon aus, dass 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.

• Der Friseur (= Prozessor) startet zu Arbeitsbeginn die Funktion friseur(). Wenn kein Kunde da ist, legt er sich schlafen.
• Kommt ein Kunde, prüft er die Bedingung count >= N. Sind alle Stühle belegt, geht er wieder. Sonst bleibt er und erhöht count um eins. War count vorher 0, weckt er den schlafenden Friseur.
• Wenn der Friseur einen Kunden bedient hat, dekrementiert er count. Ist count dann 0 geworden, legt er sich wieder schlafen.

Die kritische Situation besteht darin, dass der Kunde zwischen der Dekrementierung von count und der Frage "count gleich 0" ankommen 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 Prozess unterbrechen.

   Nachteil: Kein verdrängendes (pre-emptive) Multitasking mehr. Der Anwenderprozess kann den Scheduler blockieren (gewollt oder ungewollt durch einen Programmfehler).

   Dieses Verfahren entspricht dem Cooperative Scheduling: dabei ist gewährleistet, dass ein Prozess nur dann von einem anderen abgelöst wird, wenn er das freiwillig tut.

2. Verfahren mit gegenseitigem Ausschluss:

   Der Programmabschnitt, in dem ein Zugriff zu dem nur exklusiv nutzbaren Betriebsmittel (z. B. die gemeinsamen Daten) erfolgt, wird kritischer Abschnitt genannt. Es muss verhindert werden, dass sich zwei Prozesse gleichzeitig in ihren kritischen Abschnitten befinden. Dafür gibt es eine Reihe von Verfahren:

   a) Sperrvariable: Es wird eine logische Variable geführt, die mit 0 den Eintritt in den kritischen Bereich erlaubt und mit 1 sperrt. Der in den kritischen Bereich eintretende Prozess muss dann vor seinem Eintritt prüfen, ob der Bereich frei ist, die Sperrvariable auf 1 setzen und nach Ende wieder freigeben.

   Der Abschnitt von der Prüfung der Sperrvariablen bis zu ihrem Setzen ist selbst ein kritischer Abschnitt! Er ist zwar kürzer und damit die Konfliktwahrscheinlichkeit geringer, aber die Gefahr des Konfliktes ist nicht beseitigt! Es gibt bei vielen CPUs jedoch Befehle von der Form "teste und setze", bei denen der kritische Abschnitt innerhalb eines Maschinenbefehls "abgehandelt" wird. Ein einzelner Maschinenbefehl kann nicht unterbrochen werden. Damit ist auch die folgende Lösung möglich:

   b) "Aktives Warten":

  bool v;

  /* Warteschleife, bis Sperrvariable RV[i]= 0 ist */

  do

    v = test_and_set(&RV[i]);
  while (v == 0);

  ...

  /* kritischer Abschnitt, fuer den RV[i] zustaendig ist */

  ...

  RV[i] = 1;

  

Die Ver- bzw. Entriegelung wird häufig mit den Funktionen LOCK und UNLOCK formuliert:

  L0CK(RV[i]);

  ...

  /* kritischer Abschnitt fuer RV[i] */

  ...

  UNLOCK(RV[i]);

  

Viele Computer, die für Mehrprozessorbetrieb konzipiert wurden, kennen den Maschinenbefehl "Test and Set Lock". Dabei wird ein Speicherwort aus einem Register gelesen und ein Wert ungleich Null hineingeschrieben. Für die Test-and-set-lock-Operation tsl wird eine gemeinsame Variable namens "flag" verwendet. Diese koordiniert den Zugriff wie im folgenden Beispiel:

  enter_region: tsl register,flag kopiere flag ins Register und setzte flag auf 1

                cmp register,#0   war flag Null?

                jnz enter_region  wenn nicht, Verriegelung gesetzt, Schleife



                ... kritischer Bereich ...



  leave_region: mov flag,#0       flag auf 0 setzten

                ret               Rückkehr zum Aufrufer

  

Aktives Warten verbraucht CPU-Zeit durch Warteschleifen.

c) "Striktes Alternieren": Nur zwei Prozesse erlauben sich wechselweise den Eintritt in den kritischen Abschnitt mit einer logischen Sperrvariablen. Zum Beispiel dient die gemeinsame Sperrvariable turn zur Synchronisation zweier Prozesse. Es gilt: turn = i (i = 0,1) --> Prozess P_i darf in den kritischen Bereich eintreten:

  PO:

    while (1)

    {

      while (turn != 0) no_operation; /* warten */

      kritischer Bereich;

      turn = 1;

      unkritischer Bereich;

    }



  P1:

    while (1)

    {

      while (turn != 1) no_operation; /* warten */

      kritischer Bereich;

      turn = 0;

      unkritischer Bereich;

    }

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 der Programmiersprache 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).

• P-Operation: Anfrage-Operation

  if (s > 0)
    s = s - l; /* Prozess kann weiterlaufen,
                  Zugriff fuer andere Prozesse wird gesperrt */
  else
    /* der die P-Operation ausfuehrende Prozess wird "wartend";
       Eintrag des Prozesses in die vom Semaphor
       verwaltete Warteliste; */
  

• V-Operation: Freigabe-Operation

  if (Warteliste leer)
    s = s + l; /* Zugriff fuer andere, noch nicht wartende
                  Prozesse wird freigegeben */
  else
    /* naechster Prozess in Warteliste wird "bereit";
       Zugriff fuer wartenden Prozess wird freigegeben */

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:

• read(E): Stelle Wert von E fest.
• advance(E): Inkrementiere E (atomare = nicht unterbrechbare Operation).
• await(E,v): Warte bis E = v ist.

#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);
    }
}