Interprozesskommunikation

Begriff und Zweck

Interprozesskommunikation (englisch interprocess communication, kurz IPC) bezeichnet Verfahren des Informationsaustausches zwischen Prozessen eines Systems. Ein Prozess ist die Ablaufumgebung beziehungsweise Instanz eines laufenden Programms mit seiner Zustandsinformation. In Multitasking-Systemen laufen viele Prozesse nebenläufig: Sie werden abwechselnd oder auf mehreren CPUs gleichzeitig ausgeführt und wissen meist wenig voneinander.

IPC ist nötig, wenn mehrere Prozesse Daten gemeinsam verwenden, voneinander abhängen, Daten weiterreichen oder die Nutzung von Systemressourcen koordinieren müssen. Weil Speicherschutz normalerweise verhindert, dass ein Prozess direkt auf den Speicher eines anderen zugreift, braucht es geregelte Kommunikationswege. Diese Regeln werden wie in der Datenkommunikation als Protokoll verstanden.

Zwei Prozesse heißen konkurrent, wenn es mindestens ein Zeitintervall gibt, in dem beide begonnen, aber nicht abgeschlossen sind. In Einprozessorsystemen werden konkurrente Prozesse nur abschnittweise nacheinander bearbeitet; in Mehrprozessorsystemen können datenunabhängige Abschnitte gleichzeitig laufen. Gerade diese Nebenläufigkeit macht strukturierte Kommunikation wichtig: Programme sollen trotz nicht vollständig vorhersehbarer Ereignisse wie Betriebsmittelanforderungen, Laufzeitfehlern oder asynchronen Unterbrechungen zuverlässige Ergebnisse liefern.

Wichtige Kommunikationsverfahren

Bei speicherbasierter Kommunikation nutzen Prozesse gemeinsame Datenbereiche. Shared Memory stellt einen gemeinsamen Datenspeicher bereit, der in den Adressraum der beteiligten Prozesse eingefügt wird. Die Prozesse müssen wissen, ob sie lesend oder schreibend zugreifen dürfen. Shared Memory ist die schnellste Form der Interprozesskommunikation, weil kein Kopieren zwischen Server und Clients nötig ist. Es braucht aber Synchronisation, zum Beispiel durch Monitore oder Semaphore. Bei Paging kann Shared Memory durch gemeinsame Seiten umgesetzt werden, indem Seitentabelleneinträge verschiedener Prozesse auf dieselben Seitenrahmen im physischen Arbeitsspeicher verweisen.

Eine einfache Form ist Kommunikation über Dateien: Ein Prozess schreibt Daten in Dateien, die ein anderer Prozess lesen oder beschreiben kann. Auch hier ist Synchronisation nötig, etwa durch Datei-Locks des Betriebssystems oder durch Semaphore.

Nachrichtenbasierte Kommunikation arbeitet mit übergebenen Nachrichten. Eine Message Queue, also Nachrichtenschlange, wird meist als verkettete Liste verwaltet und hat eine eindeutige Kennung. Normalerweise gilt das First-In-First-Out-Prinzip (FIFO): Was zuerst eingefügt wurde, wird zuerst entnommen. Nachrichten können aber auch Prioritäten erhalten; dann kann ein Prozess etwa die erste Nachricht mit Priorität N abholen, auch wenn sie später eingefügt wurde. Warteschlangen werden häufig in verteilten Systemen genutzt, wenn Daten zwischen asynchronen Prozessen gepuffert werden müssen.

Pipes sind Datenströme zwischen zwei Prozessen durch einen Puffer nach dem FIFO-Prinzip. Eine Pipe leitet zum Beispiel die Ausgabe eines Programms als Eingabe an ein anderes weiter. Sie wurde 1973 von Douglas McIlroy für Unix erfunden. Namenlose Pipes transportieren Daten nur in eine Richtung; für Vollduplex-Kommunikation braucht man zwei Pipes. Sie können nur von Prozessen mit gemeinsamen Vorfahren eingerichtet werden, typischerweise von einem Elternprozess, der per fork() ein Kind erzeugt. In Unix verbindet das Symbol „|“ Programme, etwa who | sort.

Benannte Pipes oder FIFO-Pipes können auch Prozesse verbinden, die nicht miteinander verwandt sind. Sie haben wie Dateien Namen; jeder Prozess, der den Namen kennt und passende Zugriffsrechte besitzt, kann darüber kommunizieren. Sockets sind Schnittstellen für Kommunikation zwischen Prozessen auf demselben oder auf verschiedenen Computersystemen. Ein Socket verbindet zwei Punkte, die durch IP-Adresse und Port gekennzeichnet sind. Die Socket-API wurde 1984 für BSD-Unix eingeführt; local domain ermöglicht Kommunikation auf einem Rechner, internet domain über die TCP/IP-Protokollfamilie zwischen Rechnern.

Race Conditions und kritische Abschnitte

Eine Race Condition ist ein Fehler, bei dem das Ergebnis eines Systems oder Prozesses unerwartet von der Reihenfolge oder Dauer anderer Ereignisse abhängt. Das tritt besonders bei überlappenden Prozessen auf, also konkurrenten Prozessen, die gemeinsame veränderliche Daten benutzen. Race Conditions sind schwer zu finden, weil sie oft nur selten und unter bestimmten Bedingungen auftreten; ein anderes Laufzeitverhalten kann sie wieder unsichtbar machen.

Ein einfaches Beispiel ist eine gemeinsame Variable a mit Startwert 10. Wenn Prozess 1 zuerst a := a*a ausführt und druckt, danach Prozess 2 a := a/2 ausführt und druckt, entstehen die Ausgaben 100 und 50. Wenn aber Prozess 2 zuerst halbiert und Prozess 1 danach quadriert, können beide Prozesse 25 ausgeben. Das Ergebnis hängt also von der Ausführungsreihenfolge ab.

Die Programmteile, in denen auf gemeinsam genutzten Speicher, Dateien oder andere kritische Ressourcen zugegriffen wird, heißen kritische Abschnitte oder kritische Regionen. Sie müssen klar von unkritischen Abschnitten getrennt sein. Andrew S. Tanenbaum nennt vier Bedingungen zur Vermeidung von Race Conditions: Keine zwei Prozesse dürfen gleichzeitig in ihren kritischen Abschnitten sein; es braucht wechselseitigen Ausschluss. Es dürfen keine Annahmen über Geschwindigkeit und Anzahl der CPUs gemacht werden. Kein Prozess außerhalb seines kritischen Abschnitts darf andere Prozesse blockieren. Kein Prozess sollte ewig warten müssen, um in seinen kritischen Abschnitt einzutreten.

Synchronisation durch Warten und Ausschluss

Synchronisation koordiniert den Zugriff mehrerer Prozesse auf gemeinsame Ressourcen. Beim aktiven Warten (busy waiting) prüft ein Prozess fortlaufend eine Variable, bis ein bestimmter Wert erscheint. Ein Spinlock schützt so eine Ressource, verschwendet aber CPU-Zeit, weil wartende Prozesse weiter aktiv prüfen.

Eine Sperrvariable kann anzeigen, ob ein kritischer Abschnitt frei ist: 0 bedeutet frei, 1 bedeutet gesperrt. Das ist jedoch unsicher, wenn Testen und Setzen durch CPU-Scheduling unterbrochen werden. Dann können zwei Prozesse beide glauben, die Sperre sei frei, und gleichzeitig eintreten. Strikter Wechsel mit einer Variablen turn lässt Prozesse abwechselnd eintreten, ist aber unpraktisch, wenn ein Prozess deutlich langsamer ist.

Hardware-Unterstützung kann Lesen und Setzen unteilbar machen. Der TSL-Befehl (Test and Set Lock) liest ein Speicherwort LOCK in ein Register RX und schreibt zugleich einen Wert ungleich null nach LOCK; währenddessen kann kein anderer Prozess auf das Speicherwort zugreifen. Eine Alternative ist XCHG, das Inhalte zweier Speicherstellen automatisch austauscht. Der Algorithmus von Peterson wurde 1981 von Gary L. Peterson formuliert und löst das wechselseitige Ausschlussproblem für zwei Prozesse mit den Variablen turn und interested[N]. Jeder Prozess zeigt sein Interesse am Eintritt und wartet nur, solange der andere interessiert ist und an der Reihe wäre.

Beim passiven Warten wird ein Prozess schlafen gelegt, solange er nicht eintreten darf, zum Beispiel in einer Warteschlange. Ein Semaphor, 1965 von Edsger W. Dijkstra entwickelt, besitzt einen ganzzahligen Zähler und eine Warteschlange. down(s) wird beim Eintritt aufgerufen: Ist der Zähler größer als 0, wird er um 1 verringert; bei 0 muss der Prozess warten. up(s) wird beim Verlassen aufgerufen und erhöht den Zähler um 1. Für gegenseitigen Ausschluss wird der Zähler mit 1 initialisiert. Ein Mutex ist nach Peter Mandl ein binäres Semaphor mit Maximalwert N=1 und den Zuständen locked und unlocked; andere Autoren unterscheiden Mutex und binäres Semaphor, weil ein Mutex seinem aufrufenden Prozess oder Thread gehört, ein Semaphor aber keinen Besitzer hat.

Ein Monitor ist ein höheres Synchronisationsmittel, entwickelt 1974 von C.A.R. Hoare und 1975 von Per Brinch Hansen. Er bündelt gemeinsam genutzte Daten und ihre Zugriffsprozeduren in einem Modul, einem abstrakten Datentyp oder einer Klasse. Nur ein Prozess kann zur selben Zeit den Monitor benutzen; andere werden suspendiert. Der Compiler realisiert den wechselseitigen Ausschluss, zum Beispiel mit einem Mutex oder binären Semaphor.

Deadlocks

Eine Menge von Prozessen befindet sich in einem Deadlock-Zustand, wenn jeder Prozess auf ein Ereignis wartet, das nur ein anderer Prozess aus derselben Menge auslösen kann. Dadurch wacht kein Prozess mehr auf, weil alle gegenseitig voneinander abhängig sind.

Tanenbaums Beispiel beschreibt zwei Prozesse, die ein Dokument einscannen und anschließend auf CD brennen wollen. Prozess P1 belegt zuerst den Scanner, Prozess P2 zuerst den CD-Brenner. P1 wartet nun auf den CD-Brenner, gibt aber den Scanner nicht frei. P2 wartet auf den Scanner, gibt aber den CD-Brenner nicht frei. Beide blockieren sich gegenseitig. Ein Alltagsbeispiel ist eine Kreuzung, an der aus allen vier Richtungen gleichzeitig Autos ankommen und bei „rechts vor links“ jedes Auto auf das jeweils rechte wartet.

Klassische Probleme

Das Erzeuger-Verbraucher-Problem, auch Problem des begrenzten Puffers, behandelt die Zugriffsregelung auf eine Datenstruktur mit schreibenden Erzeugern und lesenden Verbrauchern. Ein Erzeuger legt Informationen in einen Puffer fester Größe, ein Verbraucher nimmt sie heraus. Der Verbraucher darf nicht lesen, wenn der Puffer leer ist, und der Erzeuger darf nicht schreiben, wenn der Puffer voll ist. Eine Variable count kann die Anzahl der Nachrichten verfolgen, bei maximal N Nachrichten. Eine naive Lösung kann aber Race Conditions erzeugen, etwa durch einen verlorenen Weckruf; Semaphoren können dieses Problem lösen.

Das Philosophenproblem wurde 1965 von Edsger W. Dijkstra veröffentlicht und gelöst. Fünf Philosophen sitzen um einen Tisch; zwischen zwei Tellern liegt je eine Gabel. Zum Essen braucht ein Philosoph zwei Gabeln, sonst denkt er. Es können maximal zwei Philosophen gleichzeitig essen. Werden die Gabeln einfach als Semaphore mit 1 umgesetzt, droht ein Deadlock: Wenn alle fast gleichzeitig ihre linke Gabel nehmen, wartet jeder ewig auf die rechte. Eine mögliche Lösung nutzt eine Statusvariable stat mit Denken (0), Hungrig (1) und Essen (2). Ein Philosoph darf nur essen, wenn keiner seiner Nachbarn isst; ein Feld von Semaphoren kann wartende Philosophen blockieren.

Beim Leser-Schreiber-Problem gibt es Leser und Schreiber, die einen gemeinsamen kritischen Bereich betreten wollen. Es gelten drei Regeln: Leser und Schreiber dürfen sich nie gleichzeitig im kritischen Abschnitt befinden; beliebig viele Leser dürfen gleichzeitig lesen; mehrere Schreiber dürfen nie gleichzeitig schreiben. Tanenbaum nennt als Beispiel ein Reservierungssystem einer Fluggesellschaft: Viele Prozesse dürfen gleichzeitig lesen, aber beim Aktualisieren der Datenbank darf kein anderer Prozess zugreifen. Eine Semaphor-Lösung kann Schreiber blockieren, solange Leser aktiv sind. Kommen jedoch ständig neue Leser hinzu, kann ein Schreiber verhungern. Eine mögliche Lösung ist, ankommende Leser hinter bereits wartende Schreiber zu stellen.