 |
Gemeinsame Nutzung von Betriebsmitteln
Manche Betriebsmittel dürfen nicht gleichzeitig von mehreren Prozessen genutzt
werden. Klassisches Beispiel ist hier der Drucker. Die Ausgaben mehrerer Prozesse würden vermischt. Abhilfe bietet hier die Nutzung des Druckers durch einen einzigen Prozeß, den Druckerspooler. Alle Prozesse übergeben ihre Ausgaben an diesen Prozeß, der die Druckaufträge in einer Warteschlange speichert und nacheinander abarbeitet.Beim Wettbewerb mehrerer Prozesse um Betriebsmittel (Ressourcen), zu denen ja primär Speicher, Dateien und die (als Dateien eingebundenen)Geräte gehören, kann es zu sogenannten Verklemmungen (dead locks) kommen.
Eine Verklemmung tritt bei Anforderungen von Ressourcen durch mehrere Prozesse
dann auf, wenn ohne drastische Aktionen des BS all diese Anforderungen niemals
erfüllt werden können. Folge: Die Prozesse blockieren sich gegenseitig.
Beispiel aus dem täglichen Leben:
Das Problem wurde schon vor vielen Jahren behoben. Die Abbiegevorschriften wurden
so geändert, daß die Autos voreinander abbiegen dürfen.
Die speisenden Philosophen
Dieses Beispiel stammt von Dijkstra und ist also Demonstrationsmodell für
das Entstehens von Deadlocks gedacht. Es wird seither auch immer als Testproblem
für neue Prozeß-Synchronisations-Algorithmen verwendet.
Bei Tanenbaum essen die Philosophen Spaghetti und zwar immer mit zwei Gabeln.
Programm für einen Philosophen mit zwei Gabeln:
#include "prototypes.h"
#define N 5
void philosoph (int i)
{
while (1) # Endlosschleife
{
denke();
NimmGabel(links);
NimmGabel(rechts);
esse();
LegeGabel(links);
LegeGabel(rechts);
}
}
Unterstellt man, daß die Philosophen pseudoparallel, also in Zeitscheiben
arbeiten, ist das Modell gleichzeitig auch als Modell für die Beschreibung
kritischer Abschnitte (zeitkritischer Situationen) geeignet.
Die Funktion NimmGabel(Seite), müßte logischerweise zuerst
prüfen, ob die Gabel frei ist, und erst dann die Gabel aufnehmen.
Der zeitkritische Charakter der Funktion NimmGabel(Seite) besteht darin,
daß zwischen der Prüfung "Gabel frei" und der Ausführung
NimmGabel(Seite)ein zeitkritischer Abschnitt besteht.
Beispiel: System mit Drucker und Magnetband, 2 Prozesse
- Prozeß A fordert den Drucker an, Prozeß B die Bandstation. Beiden
Anforderungen wird entsprochen.
- Nun fordert A die Bandstation an, ohne den Drucker freizugeben. Prozeß B
verlangt dagegen den Drucker an ohne die Bandstation freizugeben.
- Folge: gegenseitige Blockierung
Setzt man für "Drucker" und "Bandstation" zwei Datensätze
einer Datenbankdatei, so führt auch diese Situation zur Verklemmung.
Nahezu jede Situation, in der Prozesse Ressourcen exklusiv anfordern, kann
zur Verklemmung führen. Jedes exklusive Betriebsmittel kann immer nur von
einem Prozeß angefordert werden.
Solange das Betriebsmittel nicht frei ist, verbleibt der Prozeß im Zustand
"blockiert". Nicht jede Anforderung von exklusiven Ressourcen führt
zur Verklemmung. Für das Auftreten einer Verklemmung müssen folgende Bedingungen
erfüllt sein:
- Exklusive Nutzung: Das BM wird entweder von genau einem Prozeß verwendet
oder es ist frei (z. B. Druckerspooler).
- Wartebedingung: Prozesse belegen verfügbare BM, während sie auf zusätzliche
BM warten.
- Nichtentziehbarkeit: Einem Prozeß können zugeordnete BM nicht zwangsweise
entzogen werden; er muß sie explizit freigeben.
- Geschlossene Kette: Es existiert eine geschlossene Kette von 2 bis n Prozessen.
Jeder von ihnen wartet auf ein BM, das durch den nächsten Prozeß in der
Kette gehalten wird.
Im allgemeinen werden vier Strategien zur Behandlung von Verklemmungen verwendet:
- Ignorieren des Problems
Die Frage ist, wie oft eine Verklemmung auftritt. Bei durchschnittlich einer Verklemmung
pro Monat kann das Problem durchaus ignoriert werden. Interaktiv arbeitende Benutzer
werden sowieso bald die Geduld verlieren und den Prozeß abbrechen. Bei Batch-Systemen
wird die Verklemmung bei der täglichen oder wöchentlichen Systemwartung
entdeckt.
- Entdecken und Beheben von Verklemmungen
Das BS hält Anforderungen und Freigaben von BM fest und stellt sie in Form
eines BM-Grafen dar. Bei jeder Anforderung/Freigabe wird der Graf auf Zyklen untersucht.
Billigere Methode: Zyklisch prüfen, ob ein Prozeß längere Zeit (einige
Stunden) blockiert ist und diesen dann entfernen. Nachteil: möglicherweise
inkonsistente Daten.
- Verhindern von Verklemmungen durch Negation einer der 4 Bedingungen
- Beispiel Drucker: Es wird ein Prozeß eingeführt, der als einziger
Prozeß den Drucker exklusiv "besitzt".
- Durchbrechen der Wartebedingung, indem ein Prozeß die vorher angeforderten
BM freigibt. Nur wenn die Anforderung erfolgreich war, erhält er sie
zurück.
- Es gibt noch eine Reihe weiterer Methoden.
- Vermeiden der Verklemmungen durch sorgfältige BM-Vergabe
Durch geeignete BM-Zuweisung kann eine Verklemmung vermieden werden, wenn einige
Informationen im voraus verfügbar sind.
Banker-Algorithmus: Eine Methode zur Vermeidung von Verklemmungen
Wie eine Bank niemals soviel Geld bereithält, daß alle Kreditrahmen der
Kunden voll ausgeschöpft werden können, kann auch das BS die Ressourcen
so verwalten, daß immer mindestens ein Prozeß voll befriedigt werden
kann. Dazu muß bei jedem Prozeß ein Maximalwert für die anzufordernden
BM existieren.
Beispiel: Der Rechner hat 10 Magnetbandstationen
Zustand 1 Zustand 2 Zustand 3
Prozess bel. Max. Prozess bel. Max. Prozess bel. Max.
----------------- ----------------- -----------------
A 0 6 A 1 6 A 1 6
B 0 5 B 1 5 B 2 5
C 0 4 C 2 4 C 2 4
D 0 7 D 4 7 D 4 7
----------------- ----------------- ----------------
sicher sicher unsicher
10 frei 2 frei 1 frei
Ein Zustand ist dann sicher, wenn das BS mindestens bei einem Prozeß
seine Maximalforderung erfüllen kann (die anderen müssen u. U. warten).
Zustand 1 ist sicher, da jeder Prozeß befriedigt werden kann.
Zustand 2 ist sicher, da Prozeß C befriedigt werden kann.
Zustand 3 ist unsicher, da keiner der der Prozesse voll befriedigt werden
kann.
Das Schema kann auf beliebig viele BM erweitert werden.
|
|
|
DIENSTE
