13 Betriebsysteme

13.4 Betriebsablaufsteuerung

Prozessverwaltung

Parallele Prozesse sind immer in einer gewissen Abhängigkeit zueinander. Diese entsteht z.B. durch gegenseitige Aufrufbeziehungen, das Bemühen um gleiche Ressourcen oder durch Bezugnahme auf gleiche Daten im Speicher.

Kooperation

Parallel aktive Programme sind im allgemeinen auf die Zusammenarbeit angewiesen. In diesem Fall sind Sie sowohl konkurrierende als auch kooperierende Prozesse.

(z.B.: Pipes und andere Prozesspaare, bei denen Prozess B auf die Ergebnisse von Prozess A warten muss, um sie verarbeiten zu können)

Kooperierende Prozesse können durch eine entsprechende Aufrufbeziehung hervorgerufen werden:

• Blockverbindung - Aufrufbeziehung durch sequentielle Abarbeitung innerhalb eines programmierten Ablaufes
• Subroutinen - beim Aufruf einer Subroutinen müsste der rufende Prozess blockiert sein
• Co-Routinen - wenn ein Programm zwei Co-Routinen A und B ruft, die sich gegenseitig aktivieren und blockieren

Konkurrenz (Prozessverklemmung)

Ein Prozess ist verklemmt, wenn er auf ein Ereignis wartet, das nicht eintreten kann. Die Ursachen für Verklemmungen können Programmfehler oder Betriebsmittelzuteilungskonflikte sein.

Im folgenden Beispiel tritt eine Verklemmung auf, weil die Prozesse A und B beide die exklusiven Betriebsmittel x und y benötigen und diese aber gegenseitig blockieren.

Prozess A	Prozess B	Bemerkung
... Anforderung von x ... Anforderung von y W W W W	... ... Anforderung von y ... ... Anforderung von x W W	Prozess A erhält Betriebsmittel x Prozess B erhält Betriebsmittel y Prozess A geht in Wartezustand, weil y nicht zugeteilt werden kann Prozess B geht in Wartezustand, weil x nicht zugeteilt werden kann
Verklemmung		Anweisungen werden nicht mehr ausgeführt

Das Auftreten von Verklemmungen ist keine Folge von Programmierfehlern! Im Beispiel arbeiten die beiden Prozesse für sich gesehen korrekt. Es wäre zu keiner Verklemmung gekommen, wenn der Prozess A etwas früher gestartet worden wäre.

Verklemmungen treten nur mit einer gewissen Wahrscheinlichkeit auf. Deshalb ist es schwierig, ein Produkt auf Verklemmungsfreiheit zu testen. Eine Auflösung von Verklemmungen ist durch den Zwangsabbruch einzelner Prozesse möglich. Im obigen Beispiel genügt es, einen Prozess abzubrechen, der andere läuft dann korrekt weiter.

Man kann Verklemmungen verhindern, wenn beim Erzeugen eines Prozesses alle Anforderungen nach exklusiven Betriebsmitteln vorliegen und diese auf einmal zugeteilt werden. Dies führt aber zu einer schlechten Auslastung, da nicht alle Betriebsmittel für die gesamte Existenzdauer des Prozesses benötigt werden, aber die ganze Zeit belegt sind.

Da es sehr häufig vorkommt das Prozesse beim Zugriff auf Betriebsmittel untereinander konkurrieren, wurden verschiedene Synchronisationsmechanismen entwickelt:

• Semaphor: Die Anzahl der Prozesse, welche nur begrenzt vorhandene Betriebsmittel (z.B. Drucker) benutzen dürfen, wird mittels Zähler begrenzt. Sobald einem Prozess ein solches Betriebsmittel zugeteilt wurde, wird die noch verfügbare Anzahl an Betriebsmitteln dekrementiert. Gibt ein Prozess das betreffende Betriebsmittel wieder frei, erfolgt die Inkrementation des Zählers. Steht kein weiteres Betriebsmittel mehr zur Verfügung, muss ein weiterer Prozess den Zustand "wartend" einnehmen.
• Mutex: Wechselseitiger Ausschluss vom Datenzugriff. Wird eine Datenstruktur von mehreren Prozessen gemeinsam benutzt, so müssen zur Vermeidung inkonsistenter Daten gleichzeitige Schreiboperationen ausgeschlossen werden. Prozess A kann mit Hilfe eines Mutex den Zugriff anderer Prozesse auf die betreffende Datenstruktur so lange verhindern, bis er seine Schreiboperation vollständig ausgeführt hat. Im Gegensatz zu einem Semaphor wird ein Prozess immer Eigentümer eines Mutex, sobald er erfolgreich auf ihn gewartet hat!
• Kritischer Abschnitt: Teil eines Programms, bei dem ein Prozess ausschließlichen Zugriff auf das Betriebsmittels CPU benötigt und die konkurrierende Zuteilung von Rechenzeit an andere Prozesse durch den Scheduler verhindert.
• Shared Memory: Teil des Betriebsmittels Speicher, der von mehreren Prozessen zum Datenaustausch und zur gegenseitigen Synchronisation verwendet wird.

Scheduling

Die Tatsache, dass Prozesse gleichzeitig existieren, fordert einen Mechanismus, der den "Prozessor" verteilt und jeweils einen der konkurrierenden Prozesse aktiviert. Hauptaufgabe bei der Steuerung kooperierender Prozesse ist die Synchronisation. Voraussetzung ist ein Informationsaustausch. Diese Aufgaben übernimmt der Scheduler.

Allgemein wird für den Scheduler nur die Aufgabe gesehen, den Prozessor zu verteilen, d.h. den Übergang vom Zustand "bereit" in den Zustand "rechnend" für einen ausgewählten Prozess zu steuern. Tatsächlich müssen aber Prozesse gestartet und beendet werden. Weiterhin ist es möglich Prozesse aus- und wieder einzulagern.

Mögliche Kriterien für die Prozessaktivierung sind:

• First-Come First-Served: Die Prozesse werden in der Reihenfolge ihres Eingangs bearbeitet. Diese Strategie erzielt eine gute Auslastung bezüglich der CPU, allerdings nicht bezüglich Ressourcen, die längere Zeit für eine Anforderung benötigen können, wie z.B. Ein-/Ausgabe oder Massenspeicher.
• Shortest Job First wird eingesetzt, wenn die benötigte Rechenzeit für einzelne Aufgaben aus Erfahrungswerten gut vorhergesagt werden kann. Ein Nachteil ist, dass große Prozesse u.U. niemals die CPU zugeteilt bekommen.
• Round Robin wird auch als Zeitscheibenverfahren bezeichnet. Dabei wird einem Prozess die CPU für eine bestimmte (kurze) Zeitspanne zugeteilt. Danach wird der Prozess wieder hinten in die Warteschlange eingereiht.

Es gibt weitere Kriterien die z.B. auf Fairnis, Effizienz, Antwortzeit oder Durchsatz der Prozesse beruhen können.

Soll die mittlere Ausführungszeit mehrerer Prozesse auf einen Monoprozessorsystem errechnet errechnet werden, dividiert man die Summe der Prozessausführungszeiten (total) durch die Anzahl der Prozesse.

Beispiel (für Strategie Anfangswartezeit - First Come First Serve):

Prozess	Prozessausführungszeit	Prozessausführungszeit (total)
A	5	5 (0+5)
B	3	8 (5+3)
C	7	15 (8+7)
D	7	22 (15+7)

mittlere Ausführungszeit: (5 + 8 + 15 + 22) / 4 = 10

Die mittlere Ausführungszeit der Prozesse bei dieser Strategie beträgt 10 Zeiteinheiten.

Wenn sie das Gefühl haben, das weiß ich alles schon, dann sollte der nachfolgende kleine Test keine Herausforderung sein.

Test   (Prozessverwaltung)