Nebenläufige Programme

Die klassische Programmierung, wie sie in Grundkursen der Informatik und Datenverarbeitung vermittelt wird, geht von drei Annahmen aus:

Jeder Algorithmus ist aus einzelnen Schritten aufgebaut. Erst die richtige Kombination dieser Schritte ergibt das gewünschte Ergebnis. Wie man diese Kombination in einem Programm, durch das der Algorithmus beschrieben wird, ausdrücken soll, war jahrelang Gegenstand heftigster Diskussion, wobei Schlagworte wie „strukturierte Programmierung“, „schrittweise Verfeinerung“ oder „Modularisierung“ eine wichtige Rolle spielten. Ziel dieser Diskussion war es, Hilfsmittel für die Strukturierung von Programmen zu finden, die dem zu lösenden Problem angemessen sind und zugleich die Richtigkeit, Nachvollziehbarkeit und Wartbarkeit der Programme fördern. Aus heutiger Sicht wurde dabei ein Strukturierungsmittel oft nicht seiner Bedeutung entsprechend behandelt, da es auf den ersten Blick mehr Probleme zu schaffen schien, als zu lösen. Es handelt sich um das Strukturierungsmittel des Prozesses, das in diesem Kapitel näher erläutert wird.

An die Einführung des Nebenläufigkeitsbegriffs könnte sich im Prinzip nun die programmiersprachliche Behandlung von nebenläufigen Prozessen unmittelbar anschließen. Da Prozesse in Abschnitt 1.2 als besonders wichtige Hilfsmittel bei der Strukturierung nebenläufiger Programmsysteme eingeführt wurden, ist es sinnvoll, zunächst auf die allgemeinen Möglichkeiten zur Strukturierung von Programmsystemen einzugehen. Dies ermöglicht im Anschluß einen einfacheren Zugang zu Konzepten für die Beschreibung nebenläufiger Prozesse.

Für die Beschreibung nebenläufiger Prozesse in Programmsystemen gibt es verschiedene Sprachmittel. Historisch gesehen haben sich diese Sprachmittel aus der Idee der Aufspaltung des Kontrollflusses in einem (sequentiellen) Programm entwickelt. Sie äußern sich demzufolge größtenteils in Anweisungen, die zur Erzeugung von Prozessen führen. Dem gegenüber steht der jüngere Ansatz, Prozesse als eigenständige Programmelemente zu deklarieren. In diesem Kapitel werden beide Arten von Sprachmitteln behandelt.

Das vorangegangene Kapitel zeigte, mit welchen programmiersprachlichen Mitteln Prozesse beschrieben werden können. Dieses Kapitel soll nun klären, wie die so beschriebenen Prozesse ausgeführt und verwaltet werden.

Im letzten Kapitel wurde gezeigt, daß Koroutinen allein für eine zufriedenstellende Prozeßverwaltung noch nicht ausreichen. Prozesse müssen ihren Zustand in dem Moment ändern, in dem ein von ihnen erwartetes Betriebsmittel vorliegt oder in dem ihre Zeitscheibe abgelaufen ist. Dies geht nur, wenn dem laufenden Prozeß in diesen Fällen der Prozessor zugunsten der Prozeßverwaltung entzogen wird. Dies kann mit den in diesem Kapitel beschriebenen Unterbrechungen erreicht werden.

Zeitabhängigkeiten treten in jeder Rechenanlage auf allen Betrachtungsebenen auf: Die Anforderung des internen Rechnerbusses muß beispielsweise innerhalb einer festgelegten Zeitspanne beantwortet sein. Von der Prozeßverwaltung wird z.B. nach einer bestimmten Zeitscheibe ein ProzeßWechsel herbeigeführt, wodurch der Eindruck entsteht, jeder Prozeß besäße einen eigenen Prozessor. Derartige Zeitabhängigkeiten treten innerhalb der Rechenanlage auf und sollen im weiteren nicht interessieren. Im Mittelpunkt dieses Kapitels stehen Zeitbedingungen, die der Rechenanlage von außen vorgegeben werden und bei der Abwicklung von Prozessen zu berücksichtigen sind.

Wie bereits in den ersten Kapiteln gezeigt wurde, müssen sich nebenläufige Prozesse hin und wieder synchronisieren, damit sie ihre jeweiligen Arbeitsziele erreichen, sei es aus Gründen der Kooperation oder aus Gründen der Konkurrenz. Durch die Synchronisation wird die Unabhängigkeit der Abfolge von Aktivitäten verschiedener Prozesse eingeschränkt. Bestimmte Aktivitäten eines Prozesses werden mit bestimmten Aktivitäten anderer Prozesse zeitlich geordnet, indem der Beginn ihrer Durchführung verzögert wird.

Nebenläufige Systeme und ihre Synchronisation, wie sie im vorangegangenen Kapitel behandelt wurde, lassen sich anschaulich mit Petri-Netzen (Petri nets) modellieren. Seit ihrer ersten Veröffentlichung [Petri 1962] wurden zahlreiche Varianten dieser Netze entwickelt [Peterson 1977, Reisig 1986, Brauer et al. 1987a, 1987b], so daß hier nur ein kleiner Ausschnitt dargestellt werden kann. Wir wollen diesen Exkurs unternehmen, bevor wir später auf Synchronisationsverfahren zu sprechen kommen, um anhand des formalen Modells ein tieferes Verständnis für Synchronisationsprobleme zu schaffen.

Durch Synchronisationsmaßnahmen werden Prozesse verzögert. Irgendwann soll der Grund für die Verzögerung wegfallen, und die Prozesse sollen weiterarbeiten können. Leider können Prozesse selbst verhindern, daß sie fortgesetzt werden. Das folgende Beispiel verdeutlicht dies:

Zwei Studenten benötigen zur Vorbereitung auf die Prüfung ein zweibäandiges Lehrbuch. Der erste Student leiht zunä Band 1 aus will Band 2 erst später holen. Als der zweite Student kommt, entdeckt er zwat, daß Band 1 bereits nicht mehr vorhanden ist, leiht aber „vorsorglich“ schon Band 2 aus.

Der erste Student ist nun mit dem Bearbeiten von Band 1 fertig und will Band 2 ausleihen. Er kann Band 1 noch nicht zurückgeben, da er weiß, daß er beim Durcharbeiten des ersten Kapitels von Band 2 den ersten Band noch häufig zum Nachschlagen benögen wird. Beide Studenten warten nun auf die Rückgabe des jeweils anderen Bandes, ohne den eigenen zurückzugeben.

Synchronisationsmaßnahmen wurden in Kapitel 7 abstrakt mit Hilfe von await- und crjt-Anweisungen ausgedrückt. In diesem Kapitel wollen wir untersuchen, wie man diese Anweisungen auf möglichst einfache Weise implementieren kann. Wir können uns dann denken, daß ein Übersetzer die Synchronisationsanweisungen automatisch durch solche Implementierungen ersetzt.

Die im letzten Kapitel implementierten Synchronisationsprozeduren sind aufgrund des Nachteil des aktiven Wartens zumindest in Einprozessorsystemen nicht sinnvoll verwendbar: So, wie wir vor einer geschlossenen Schranke eines Bahnübergangs den Motor unseres Autos abstellen, weil sein Laufen mehr schadet als nützt, sollten wir auch Prozesse dann von der Nutzung des Prozessors ausschließen, wenn sie auf das Eintreten einer Bedingung warten müssen. Dieses Kapitel stellt ein Verfahren vor, das auf dieser Überlegung basiert.

Die Programmbeispiele des vorangegangenen Kapitels haben bereits deutlich gemacht, daß die Verwendung von Semaphoren schnell zu unübersichtlichen Programmen führt und demzufolge die Gefahr von Programmierfehlern bietet. Programmierer können leicht die zu einer P-Operation gehörige V-Operation vergessen und umgekehrt. Dies ist besonders leicht möglich, wenn wie bei der einseitigen Synchronisation solche Operationen in verschiedenen Prozessen auftreten. Andererseits erfüllen Semaphore durch die Blockierung von Prozessen beim Warten auf ein Ereignis genau das Ziel einer möglichst effizienten Synchronisation.

Als einen Nachteil der bedingten kritischen Abschnitte des letzten Kapitels kann man empfinden, daß kritische Abschnitte mit ihren Synchronisationsanweisungen über das gesamte Programm verstreut sind.zeigt dies in Teil (a). Hier kann leicht einmal das Schützen gemeinsamer Variablen vergessen werden.

Monitore, wie sie im vorangegangenen Kapitel behandelt wurden, zeichnen sich gegenüber den zuvor betrachteten bedingten kritischen Abschnitten dadurch aus, daß sie jede Regelung der Synchronisation vor ihren Benutzern verstecken. Synchronisiert wird ausschließlich innerhalb des Monitors: Die mehrseitige Synchronisation wird durch den gegenseitigen Ausschluß der Monitorprozeduren gewährleistet und die einseitige an verschiedenen Stellen durch Ereignisvariablen vorgenommen. Die konsequente Fortführung des Monitoransatzes besteht darin, auch die einseitige Synchronisation aus den Zugriffsoperationen herauszuziehen. Dies hat den Vorteil, daß sämtliche Maßnahmen zur Synchronisation übersichtlich an einer Stelle zusammengefaßt sind. Diesen letzten Schritt der Abstraktion von Semaphoren wollen wir in diesem Kapitel machen.

Die bisher vorgestellten Synchronisationsverfahren basieren darauf, daß Prozesse gemeinsame Variablen besitzen. Über diese Variablen können sie miteinander kommunizieren. Wenn nun keine gemeinsamen Datenbereiche von Prozessen vorhanden sind, scheidet diese Möglichkeit der Kommunikation und damit auch der Synchronisation aus. Hier können Prozesse Informationen nur austauschen, wenn sie in der Lage sind, Daten von einem Datenbereich in einen anderen zu transferieren. Wie dies geschehen kann, ist Gegenstand dieses Kapitels.

Jeder Nachrichtenaustausch zwischen Prozessen ist an das Vorhandensein eines Kommunikationskanals gebunden, auf den die im vorangegangenen Kapitel diskutierten Sende- und Empfangsfunktionen angewendet werden können. In diesem Kapitel werden verschiedene Möglichkeiten vorgestellt, Kommunikations-kanäle zwischen Prozessen einzurichten.

So wie Semaphoroperationen zwar die gewünschte Funktionalität bereitstellen, aber für eine strukturierte Programmierung schlecht zu verwenden sind, lassen auch Funktionen zum Nachrichtenaustausch unter Strukturierungsgesichtspunkten Wünsche offen. Genau wie man bei einem Monitor einzelne Synchronisationsoperationen verbirgt, kann man auch von einzelnen Operationen zum Nachrichtenaustausch abstrahieren. Diese Abstraktion steht im Mittelpunkt dieses Kapitels.

Bei den Prozedurfernaufrufen des vorangegangenen Kapitels stand eine ferne Prozedur jederzeit zur Ausführung bereit. Ein Prozeß, der die Prozedur zum Aufruf anbot, hatte keinen Einfluß darauf, wann die Prozedur ausgeführt wurde. Aus den Programmbeispielen mit datenorientierter Kommunikation sieht man, daß es sinnvoll sein kann, wenn ein Prozeß in verschiedenen Zuständen unterschiedliche Nachrichten entgegennimmt. In diesem Kapitel wird vorgestellt, wie sich dies auf die aktionsorientierte Kommunikation übertragen läßt.

Wenn Prozesse über Nachrichten miteinander kommunizieren, benötigen sie keine gemeinsamen Datenbereiche, um Informationen auszutauschen. Sie können deshalb bei dieser Art der Kommunikation auch auf verschiedenen Rechnern ablaufen, die keinen gemeinsamen Speicher besitzen und lediglich über Leitungen zum Datenaustausch miteinander verbunden sind. Die Prozesse arbeiten dann verteilt (distributed). Verteilte Programmsysteme stehen im Mittelpunkt des Rests dieses Buches. Im vorliegenden Kapitel wollen wir einen Überblick über die Strukturen und Möglichkeiten solcher Systeme geben, bevor wir uns danach wieder konkreten Fragen ihrer Programmierung zuwenden.

Im letzten Kapitel haben wir bei der Architektur verteilter Systeme nur deren horizontale Aufteilung in Schichten betrachtet. Ebenso kann man auch eine vertikale Aufteilung vornehmen, indem man Prozesse nach den Rechnern ordnet, auf denen sie ablaufen. Angenommen, ein verteiltes Programmsystem wird auf einem Rechner entwickelt und soll nun auf einem Rechnernetz zur Ausführung kommen. In diesem Fall müssen die Programmierer die Zuordnung der Prozesse zu Rechnern spezifizieren. Dieses Kapitel beschreibt, welche Festlegungen dabei zu treffen sind.

Die Verständigung zwischen Prozessen, die miteinander kommunizieren, unterliegt Regeln, die wir in Kapitel 19 als Protokolle bezeichnet haben. In verteilten Systemen kommt Protokollen besondere Bedeutung zu, da hier eine Verständigung trotz einer Vielzahl von Fehlern möglich sein muß. Leitungen, über die Nachrichten übertragen werden, können gestört werden. Rechner, auf denen die Kommunikationspartner angesiedelt sind, können während der Kommunikation ausfallen oder schlicht ausgeschaltet werden. In diesem Kapitel wollen wir einen Eindruck von den Aufgaben vermitteln, die Protokolle in einem verteilten System zu erbringen haben, wohl wissend, daß eine ausführliche Behandlung dieses Themenkomplexes ein eigenes Buch erfordert.

Da die bislang angegebenen Beispiele immer zur Demonstration bestimmter Aspekte oder Algorithmen dienten, konnten sie noch keinen Eindruck von der Komplexität nebenläufiger, verteilter und echtzeitabhängiger Systeme in der Praxis vermitteln. Um dies nachzuholen, soll zum Schluß ein größeres Beispiel vorgestellt werden, das bereits recht realitätsnah ist, läßt man einmal außer acht, daß es keine Mechanismen enthält, um auch beim Ausfall von Rechnern zuverlässig zu arbeiten. Um zur realen Problemstellung auch eine reale Lösung anzugeben, implementieren wir dieses Schlußbeispiel in der Sprache Ada, deren Elemente im Laufe der vorangegangenen Kapitel ausführlich beschrieben wurden.

Wir haben in diesem Buch viele grundlegende Techniken der Programmierung nebenläufiger, verteilter und echtzeitabhängiger Systeme vorgestellt. Unser Weg hat uns von einer maschinennahen Betrachtungsebene zu mehr benutzernahen Mechanismen geführt. Es sind diese Mechanismen, mit denen man solche Systeme programmieren sollte. Dies setzt voraus, daß man sie sich, sollten sie auf den zu verwendenden Rechnern noch nicht verfügbar sein, selbst verschafft.