Wiederholung : Erläutern Sie Beispiele für die drei Welten Betriebs-, Programmier- und Dienstleistungssysteme!

Metasteuerung

Metasteuerung ist Teil des Betriebssystems

Was ist ein kritischer Abschnitt ?

Ein Kritischer Abschnitt ist ein zeitlicher Bereich, in welchem mindestens zwei Prozesse auf das gleiche Betriebsmittel zugreifen und mindestens eines davon schreibt. (Zeitkritischer Ablauf)

Ein kritischer Abschnitt ist eine Teilprozessfolge, in deren Verlauf Werte eines von einem Teilprozess genutzten Betriebsmittels durch einen anderen Prozess geändert werden könnten.

Was ist nötig, damit keine Inkonsistenz auftritt?

1. zu jedem Zeitpunkt darf nur ein Prozess im k. A. sein

2. kein Prozess im k. A. darf Prozesse außerhalb beeinflussen

3. alle Prozesse müssen in endlicher Zeit den k. A. betreten können, wenn sie es wollen

4. die Lösung muss unabhängig von externen Faktoren sein (Ausführungsgeschwindigkeit, Prozessoranzahl, ...)

Erklären sie am Bsp. Druckerspooler den kritischen Abschnitt!

  1. in Spooler ist der Platz 4 frei
  2. Prozess A will drucken und liest die Platznummer
  3. PUM aktiviert Prozess B, welcher ebenfalls diese Platznummer liest
  4. Prozess B schreibt den Auftrag nach Platz 4
  5. PUM schaltet zu A zurück und A überschreibt nun den Druckauftrag von B!
Deshalb notwendig: Wechselseitiger Ausschluss!

Was ist wechselseitiger Ausschluss?

Es muss gewährleistet werden, dass niemals sich mehr als ein Prozess in einem kritischen Abschnitt befinden darf. Die Anwendung einer einfachen Sperrvariable ist hier nicht möglich, da der Zugriff und das Setzen dieser, selbst einen kritischen Abschnitt darstellt. Es müssen Algorithmen gefunden werden, welche die Funktionalität gefahrlos implementieren

Welche Anforderungen muss eine Steuerung für kritische Abschnitte erfüllen?

  1. exklusive Nutzung durch verschiedene Teilprozesse über mutual exclusion
  2. Ein Prozess darf einen anderen nur behindern, wenn beide im kritischen Abschnitt
  3. Der Eintritt in einen kritischen Abschnitt darf nicht lang dauern
  4. Alle Prozesse müssen in endlicher Zeit ihre Betriebsmittel zugewiesen bekommen
  5. globale Unabhängigkeit von allgemeinen Fortschreiten der Prozesse

Erläuterung von Begriffen

Die Verwaltung des kritischen Abschnitts kann zentral (durch eine zentrale Instanz wie das BS oder einen Server) oder dezentral (durch Kooperation der Prozesse selbst) erfolgen.

Atomare Funktionen sind Funktionen, die in ihrer Ausführung nicht durch Scheduling unterbrochen werden können. Ebenso können Speicherzugriffe, die sie eventuell ausführen, nicht gestört werden.

Für den k.A. sind immer zwei atomare Funktionen notwendig.

P() ... down() ... wait()

(passerr)

Wird beim Betreten des kritischen Abschnitts aufgerufen.

Teilt der Verwaltung (zentral oder dezentral) den Wunsch mit, den kritischen Abschnitt zu betreten.

P() wartet, bis der kritische Abschnitt frei ist, also keine andere Aktivität sich darin aufhält.

Kehrt P() zurück, betritt die Aktivität den k.A. – er ist somit für alle anderen Aktivitäten gesperrt.

V() ... up() ... signal()

(verlaat)

Wird beim Verlassen des kritischen Abschnitts aufgerufen.

Teilt der Verwaltung (zentral oder dezentral) mit, dass der kritische Abschnitt abgearbeitet wurde.

V() erlaubt, dass andere Aktivitäten den kritischen Abschnitt betreten.

Nachdem V() zurückgekehrt ist, hat die Aktivität den k.A. verlassen.

dezentrale Steuerung

P() und V() müssen bei der dezentralen Steuerung …

1. ... von den Prozessen selbst implementiert sein und aufgerufen werden und

2. ... über einen (hier nicht näher diskutierten) Kommunikationsmechanismus (evtuell IPC) verfügen (z.B. über eine gemeinsam genutzte Variable, die durch einen Prozess initialisiert wird).

Wie arbeitet Striktes Alternieren? (Ping Pong)

 

P1

P2

 

Initialisierung int var = 1;

P(): while (var == 2); while (var == 1);
  /* kritischer Abschnitt */
V(): var = 2; var = 1;

var gibt an, welcher Prozess den kritischen Abschnitt betreten darf

P2 kann erst beginnen, wenn P1 V() verlassen hat.

P1 muss immer zuerst ausgeführt werden.

Wenn P1 ausgeführt wurde, dann muss erst P2 abgearbeitet werden, bevor P1 den k.A. wieder betreten

kann und umgekehrt. „Ping-Pong“

Das heißt, mehrmaliges Betreten des k.A. hintereinander durch einen Prozess ist nicht möglich.

Variante 2

 

P1

P2

 

Initialisierung int var = 0;

P(): while (var == 1); while (var == 1);
  /* kritischer Abschnitt */
V(): var = 0; var = 0;

Beliebige Folge des Eintritts in den kritischen Abschnitt möglich.

Wird einem Prozess nach der While-Schleife der Prozessor entzogen, dann können beide Prozesse gleichzeitig in den k.A. gelangen.

Gibt es mehr als einen Prozessor, dann wird das Ganze noch kritischer.

Verstoß gegen Punkt 1, da 2 Prozesse zur selben Zeit den k. A. betreten können

Variante 3  Zwei Variablen

 

P1

P2

 

Initialisierung int var1 = Var2 = 0;

P(): while (var1 == 1); /*Warten*/ while (var2 == 1);  /*Warten*/
  var1 = 1; Var2 = 1;
  /* kritischer Abschnitt */
V(): var1 = 0; var2 = 0;

varx==0           Prozess x ist nicht im kritischen Abschnitt.

varx==1           Prozess x ist im kritischen Abschnitt.

komplexer als Variante 2, aber gleiches Fehlerpotenzial

Variante 4  Lifelock

 

P1

P2

 

Initialisierung int var1 = Var2 = 0;

P(): var1 = 1; Var2 = 1;
  while (var1 == 1); /*Warten*/ while (var2 == 1);  /*Warten*/
  /* kritischer Abschnitt */
V(): var1 = 0; var2 = 0;

Verstoß gegen Punkt 3, da im schlimmsten Fall keiner der beiden Prozesse den kritischen Abschnitt betreten kann („Verhungern“)

Variante 5  "Bitte nach Ihnen"

 

P1

P2

 

Initialisierung int var1 = Var2 = 0;

  m1:  var1 = 1; m2: var2 = 1;
  if (var2 == 1) while (var1 == 1); 
  { {
P(): var1 = 0; var2 = 0;
  goto m1 goto m2
  } }
  /* kritischer Abschnitt */
V(): var1 = 0; var2 = 0;

„Verhungern“ bei absolut gleichzeitigem Fortschreiten

Stellt ein Prozess fest, dass er nicht in den kritischen Abschnitt kann, so zieht er seine Anforderung kurzzeitig zurück, bevor er es wieder versucht.

Variante 6  Dekker-Algorithmus

 

P1

P2

 

Initialisierung int var1 = var2 = 0;

 

int turn =1;

  var1 = 1; var2 = 1;
  if (var2 == 1) while (var1 == 1); 
  {  
P(): var1 = 0; var2 = 0;
  while ( turn == 2 ) while ( turn == 1 )
  var1 = 1; var2 = 1;
  } }
  /* kritischer Abschnitt */
V(): var1 = 0; turn = 2; var2 = 0; turn = 1;

„Dekker-Algorithmus“

Ist eine vollständige und korrekte Lösung.

Einführung einer 3. Variablen turn.

turn gibt an, welcher Prozess bei exakter Gleichzeitigkeit den Vorrang erhält.

Es ist immer der, der am längsten wartet.

Bei unterschiedlicher Abarbeitungszustand entspricht diese Variante ihrer Vorgängervariante.

Variante 6  Petersen-Algorithmus

 

P1

P2

 

Initialisierung int var1 = var2 = 0;

 

int turn =1;

  var1 = 1; var2 = 1;
  if (var2 == 1) while (var1 == 1); 
  {  
P(): var1 = 0; var2 = 0;
  while ( turn == 2 ) while ( turn == 1 )
  var1 = 1; var2 = 1;
  } }
  /* kritischer Abschnitt */
V(): var1 = 0; turn = 2; var2 = 0; turn = 1;

 MERKE: Alle dezentralen Lösungen haben den Nachteil, dass Prozessorzeit durch das “aktive” Warten “verschwendet” wird!

Stürzt ein Prozess im kritischen Abschnitt ab, so hat er ihn ja nicht verlassen, der k.A. bleibt belegt und die anderen sind automatisch deadgelockt.

Was sind Semaphore - zentrale Steuerung?

Ein Semaphor ist ein allgemeiner Mechanismus zur Synchronisation, ohne aktiv warten zu müssen. Das Verfahren wurde von Dijkstra (1965) entwickelt und hat sich durchgesetzt. Ein Semaphor arbeitet auf einer priviligierten Schicht des Betriebssystems und ist somit nicht Teil der Prozesse.
Ein Binärer Semaphor kann einen Kritischen Abschnitt für zwei Prozesse verwalten. Falls mehrere Prozesse gleichzeitig auf ein Betriebsmittel zugreifen dürfen, reicht der binäre Semaphor nicht aus. Der Semaphor wird dann als Zähler implementiert. Falls er 0 ist, ist das Betriebsmittel voll ausgelastet. Ist er größer als 0, so sind noch Ressourcen vorhanden, d.h. andere Prozesse dürfen in den Kritischen Abschnitt eintreten, solange der Semaphor nicht Null ist. Dabei dekrementieren sie diesen und blockieren ihn für andere Prozesse, falls der Semaphor nun Null ist. Verlässt ein Prozess den Kritischen Abschnitt, inkrementiert der Prozess den Semaphor wieder und signalisiert damit, dass er seine Arbeit getan hat und nun ein anderer eintreten darf. Daher werden die beiden Operationen vor und nach dem Kritischen Abschnitt oft als Down(sem) und Up(sem) definiert.

Wie funktioniert das Grundprinzip von Semaphoren?

Es wird nicht mehr eine Art Sperrvariable verwendet, sondern ein Zähler. Für dieses Zähler gibt es die Operationen up(s) bzw. V und down(s) bzw. P zum Erhöhen bzw. Dekrementieren des Zählers. Ist nach einem down(s) der Zähler null, wird gewartet. Ist er irgendwann wieder größer als Null werden die Anweisungen ausgeführt. Der Semaphor ist nun nichts weiter als dieser Zähler, welcher nur durch up und down ansprechbar ist! Die beiden Operationen P und V stellen natürlich auch kleine kritische Abschnitte dar, welche über aktives Warten synchronisiert werden.

Ein Semaphor ist eine nichtnegative Ganzzahl, mit der Verwaltungsinformationen von Prozessen (Threads) verbunden sind.

Quasistandard: Semaphor == 0 BM ist belegt

Semaphor > 0 BM ist frei

Beim kritischen Abschnitt gibt es maximal einen Benutzer, daher nimmt man hier binäre Semaphoren {0, 1}

Semaphoren haben Zeiger/Anker für die Prozesse in der Warteschlange (Liste), die durch die Semaphore als „wartend” gekennzeichnet werden und damit temporär aus dem Scheduling entfernt werden.

P() Semaphore prüfen, ob größer als 0 (BM frei); wenn ja, Wert der Semaphore dekrementieren, wenn nein, Prozess in Wartepool der Semaphore einreihen.

V() Befinden sich Prozesse im Wartepool der Semaphore? Wenn ja, einen beliebigen auswählen und wieder als „bereit“ markieren (also wieder ins Scheduling einbinden); wenn nein, Wert der Semaphore inkrementieren.

P(sem) //Probiere in kritischen Abschnitt einzutreten
{
        if (sem == 0)
        sleep(sem); //Prozess auf wartend setzen
        sem--;
}

V(sem) //Verlasse kritischen Abschnitt
{
        sem++; //Zugang wieder freigeben
        wakeup(sem);
}
sleep und wakup sind Systembefehle, welche einen Prozess Schlafenlegen oder Aufwecken.

Prozess A Prozess B
int sem = 1; //zwei Prozesse
While (1)
{
        P(sem);
        // kritischer Abschnitt
        V(sem);
}
While (1)
{
        P(sem);
        // kritischer Abschnitt
        V(sem);
}

Beispiele:

    Erzeuger-Verbraucher-Problem

    Leser-Schreiber-Problem

    Problem der wartenden Friseure

    Problem der dinierenden Philosophen

Ein Prozess mit niedriger Priorität ist ein einem (durch P() und V() gesicherten) kritischen Abschnitt. Was passiert, wenn jetzt ein Prozess mit höherer Priorität ebenfalls diese k.A. betreten will? Welche Rolle spielt dabei die Anzahl vorhandener Prozessoren? 

Ein Prozess befindet sich in einem kritischen Abschnitt, der Operationen auf den Speicher schützt. Er hat beim Betreten des Abschnittes P() aufgerufen, und wird beim Verlassen V() rufen. Was passiert, wenn ein weiterer Prozess diesen k.A. betreten will, ohne jedoch vorher P() zu rufen?

 

Was ist das Erzeuger-Verbraucher-Problem?

Zwei Prozesse nutzen einen Puffer mit N Plätzen zum Datenaustausch. Während Prozess A Daten sequentiell in den Puffer schreibt, entnimmt Prozess B ein Datum aus dem Puffer.

Nun stellen sich die Fragen
  1. Wie soll man das gleichzeitige Einfügen und Entnehmen synchronisieren?
  2. Ein Datum darf nur eingefügt werden wenn der Puffer nicht voll ist.
  3. Ein Datum darf nur eingefügt werden, wenn noch Platz im Buffer ist.
Gelöst werden, kann das Problem mit mehreren Semaphoren.
  • Ein Semaphor für die Kontrolle des kritischen Abschnittes
  • Ein Semaphor, welcher die freien Plätze zählt
  • Ein Semaphor, welcher die vergebenen Plätze zählt
const N 100	 //buffer size

int mutex = 1 //Für Kritischen Abschnitt
int empty = N //Anfangs leerer Buffer
int full  = 0 //noch keine Daten im Buffer

void ErzeugerProzess()
{
        int item;

        while(1)
        {
                iNode = CreateItem();

                P(empty);
                P(mutex);
                Insert(item) //Critical Section
                V(mutex);	 //Mutex wieder erhöhen
                V(full);	 //full=full+1
        }
}

void VerbraucherProzess()
{

        int item;

        while(1)
        {

                P(full);
                P(mutex);
                Item = RemoveItem(); //Critical Section
                V(mutex);
                V(empty);
                MakeSomething(Item);
        }
}
Der Semaphor mutex verhindert, daß gleichzeitig Verbraucher und Erzeuger im kritischen Abschnitt sind. Denn falls der Erzeuger gerade eingetreten ist, ist der Semaphore mutex null. Versucht nun der Verbraucher in den kritischen Abschnitt einzutreten, muss er bei P(mutex) warten, da der mutex noch null ist. Um nun zu Verhindern das aus einer leeren Liste gelesen oder in eine volle geschrieben wird, werden hier elegant zwei weitere Semaphoren verwendet, welche das Vorhandensein von freien Plätzen (empty) und belegten Plätzen (full) zählen.

Was ist das Philosophenproblem?

Beim Philosophenproblem geht es nicht um Kommunikation sondern um Synchronisation. Abstrakt gesehen, gibt es N Prozesse und N Betriebsmittel. Ein Prozess benötigt mindestens zwei der Betriebsmittel um fortschreiten zu können. Ohne Synchronisation, würden im schlimmsten Fall alle 5 Prozesse je ein Betriebsmittel bekommen und dann unendlich darauf warten, daß ein anderer Prozess eins freigibt.

Es sitzen fünf Personen an einem runden Tisch. Sie können entweder Denken oder Essen. Es gibt zwar für jeden einen Teller, aber nur fünf Stäbchen. Um Essen zu können braucht man aber bekanntermaßen zwei.

Wie kann das Philosophenproblem gelöst werden?

Natürlich denkt man zuerst an Semaphoren. Nur funktioniert die triviale Lösung mit einem Semaphor pro Stäbchen nicht. Es können immer noch alle Philosophen je ein Stäbchen gleichzeitig aufnehmen und die Prozesse wären allesamt verklemmt. Es muss also irgendwie möglich sein, mehr als ein Stäbchen gleichzeitig aufzunehmen. Bei den verschiedenen Implementationen ist vor allem darauf zu achten, dass dieses Aufnehmen der beiden Stäbe eine Atomare Funktion ist.