Skip to main content
main-content

Über dieses Buch

Dieses Buch führt nach einem kurzen Kapitel über grundlegende Aspekte der Softwaretechnik und deren Realisierung in Go in die Nichtsequentielle und Verteilte Programmierung mit Go ein. Es stellt grundlegende Konzepte zur Synchronisation und Kommunikation nebenläufiger Prozesse systematisch dar. Dazu zählen unter anderem Schlösser, Semaphore, Fairness und Verklemmungen, Monitore, lokaler und netzweiter Botschaftenaustausch, Netzwerke als Graphen, Erkundung von Netzwerken, verteilte Tiefen- und Breitensuche und die Auswahl eines Leiters in Netzwerken. Um Lesern die Konzepte nahezubringen, greift der Autor klassische Beispiele auf. Das erleichtert das Lernen, denn die vorgestellten Konzepte lassen sich auf diese Weise besser mit den Sprachmitteln vergleichen.

Die Algorithmen sind in der Programmiersprache Go formuliert, mit der sich zahlreiche Synchronisationskonzepte ausdrücken lassen. Go bietet aufgrund der einfachen Syntax außerdem den Vorteil, dass auch Leserinnen und Leser ohne Vorkenntnisse den grundlegenden Konzepten folgen können. In den Kapiteln zu Schlössern, Semaphoren, Monitoren und zum netzweiten Botschaftenaustausch werden darüber hinaus auch einige grundlegende Ansätze zur Programmierung in C und Java vorgestellt. Sämtliche Quelltexte sind online verfügbar.

In der 4. Auflage des Lehrbuchs, das sich an Studierende der Informatik richtet, wurden einige Fehler korrigiert, kleinere Erweiterungen aufgenommen sowie Anpassungen aufgrund einer Änderung an Go vorgenommen.

Inhaltsverzeichnis

Frontmatter

1. Einführung

Zusammenfassung
In diesem Kapitel werden zentrale Begriffe der Nichtsequentiellen Programmierung definiert und konzeptionelle Unterschiede zur Sequentiellen Programmierung herausgearbeitet. Dabei wird gezeigt, dass die Größenordnungen der Anzahlen möglicher Abläufe nichtsequentieller Programme jegliches menschliche Vorstellungsvermögen übersteigen. Danach werden Schreibweisen für nebenläufige Anweisungen vorgestellt und der Prozessbegriff informell eingeführt.
An einigen Beispielen wird die extreme Anfälligkeit für Fehler demonstriert, die sich aus Konflikten beim Zugriff mehrerer Prozesse auf gemeinsame Ressourcen ergeben können. Sie verdeutlichen, dass Programme ohne Synchronisation dieser Zugriffe völlig unbrauchbar oder sogar beliebig schädlich sind.
Nach der Erklärung, was unter atomaren (unteilbaren) Anweisungen verstanden wird, werden das Wechselspiel zwischen dem Begriff der Unteilbarkeit und dem der kritischen Abschnitte erläutert und darauf basierend die Sperrsynchronisation als ein erstes Konzept zur Vermeidung von Zugriffskonflikten definiert. Den Schluss des Kapitels bildet die Entwicklung des Prozessbegriffs und die Darstellung der Übergänge zwischen Prozesszuständen. Sie dienen dem Verständnis der abstrakten Begriffe und ermöglichen den Einblick in innere Abläufe im Rechner.
Christian Maurer

2. Pakete, Interfaces und abstrakte Datentypen

Zusammenfassung
In diesem Kapitel gehen wir auf die im Vorwort angedeuteten wichtigen – von der NSP unabhängigen – Programmierprinzipien ein. Es dient lediglich dazu, einige Aspekte der in diesem Buch verwendeten programmiertechnischen Verfahrensweisen darzustellen. Im Wesentlichen geht es dabei darum, wie sich fundamentale softwaretechnische Grundprinzipien in Go realisieren lassen.
Es werden einige grundlegende Pakete aus den Quelltexten aus diesem Buch, dem nUniversum, vorgestellt und anhand einiger Beispiele – dem Interface Object und den abstrakten Datentypen ,,Warteschlange“ und ,,beschränkter Puffer“ – wird die Umsetzung softwaretechnischer Grundsätze detailliert erläutert.
Christian Maurer

3. Schlösser

Zusammenfassung
Dies ist das erste Kapitel, das sich mit der Konstruktion bestimmter Algorithmen zur Synchronisation nebenläufiger Prozesse befasst – den Ein- und Austrittsprotokollen zum Schutz kritischer Abschnitte. Den Effekt eines Eintrittsprotokolls kann man sich intuitiv etwa so vorstellen: Ein Prozess verschließt bei seinem Durchlaufen den Zugang zu einem kritischen Abschnitt hinter sich, um ihn nach dem Verlassen des kritischen Abschnitts im Austrittsprotokoll wieder aufzuschließen. Deshalb nennt man die Implementierungen dieser Protokolle Schlossalgorithmen und die zugehörigen Datentypen Schlösser .
Nach der Spezifikation von Schlössern werden sie unter Verwendung von – an gängigen Prozessoren ausgerichteten – Maschineninstruktionen implementiert und diese Verfahrensweisen bewertet. Danach werden Möglichkeiten vorgestellt, Ein- und Austrittsprotokolle zum Betreten kritischer Abschnitte mit elementaren Methoden der sequentiellen Programmierung durch den Zugriff auf gemeinsam benutzte Variablen zu implementieren. Viele dieser Lösungen sind ,,klassische Algorithmen“, die die Forschung über Jahre geprägt haben. Allerdings stellen sich dabei auch eine Reihe von – konzeptionellen wie praktischen – Nachteilen und Einschränkungen heraus.
Christian Maurer

4. Semaphore

Zusammenfassung
Wenn sich auch einfache Synchronisationsprobleme durch die Verwendung von Schlossalgorithmen lösen lassen, bergen ihre Implementierungen jedoch eine ganze Reihe von Nachteilen. Die älteste Idee zur Beseitigung einiger dieser Nachteile ist das Synchronisations-Konstrukt der Semaphore von Dijkstra. In diesem Kapitel werden seine Ideen vorgestellt und an vielen Anwendungen wird demonstriert, wie sich Semaphore einsetzen lassen.
In diesem Kapitel werden binäre und – im Kontext beschränkter Puffer – allgemeine Semaphore spezifiziert und die wechselseitigen Beziehungen zwischen ihnen erörtert; und nachdem Dijkstras schlafender Barbier geweckt ist, wird auf die Tücken der Konstruktion allgemeiner Semaphore aus binären hingewiesen. Das Leser-Schreiber-Problem und einige seiner Lösungen mit Semaphoren führen zum Muster des Staffelstab-Algorithmus. Ferner werden einige spezielle Fragen behandelt: Additive Semaphore, Barrierensynchronisation, das Links-Rechts-Problem, Dijkstras speisende Philosophen, das Problem der Zigarettenraucher, Hinweise zur Implementierung von Semaphoren und das Konvoi-Phänomen.
Christian Maurer

5. Der Staffelstab-Algorithmus

Zusammenfassung
In diesem Kapitel stellen wir eine geschickte Konstruktion zur Lösung vieler Probleme vor, die Bedingungssynchronisation erfordern. Mit ihr wird für mehrere disjunkte Prozessklassen erreicht, dass jeweils nur Prozesse aus der gleichen Klasse nebenläufig arbeiten dürfen, Prozesse aus verschiedenen Klassen dagegen nur unter gegenseitigem Ausschluss.
Christian Maurer

6. Universelle kritische Abschnitte

Zusammenfassung
Die Grundidee des Staffelstab-Algorithmus aus dem vorigen Kapitel gibt Anlass, darü- ber nachzudenken, ob das, was er gewissermaßen als ,,Muster zum Programmieren“ enthält, nicht auch ,,automatisch“ generiert werden könnte. In diesem Kapitel wird gezeigt, dass das in der Tat der Fall ist: Die Überlegungen dazu liefern die Entwicklung eines universellen Synchronisationskonzepts, zur einfachen Lösung von Problemen, die Bedingungssynchronisation erfordern.
Damit wird eine Abstraktionsstufe erreicht, mit der bestimmte Typen von Synchronisationsproblemen auf ihren gedanklichen Kern reduziert werden können. Dabei verschwinden die eigentlichen Maßnahmen zur Synchronisation hinter der Schnittstelle eines abstrakten Datentyps, was zu einer erheblichen Vereinfachung der Implementierungen führt.
Christian Maurer

7. Fairness

Zusammenfassung
Fairness bedeutet im Prinzip die Garantie, dass von einer endlichen Anzahl nebenläufiger Prozesse in einem unendlichen Betriebsablauf jeder einzelne unendlich oft aktiv ist, wobei die jeweilige Dauer der Aktivitität der Prozesse keinen Einschränkungen unterliegt. Es handelt sich also um ein Lebendigkeitskriterium.
Christian Maurer

8. Verklemmungen

Zusammenfassung
Prozesse, die im Betriebsablauf definitiv blockiert sind, ohne dass planmäßige Maßnahmen zur Synchronisation mit anderen Prozessen dafür ursächlich sind, heißen verklemmt. Mit ,,definitiv“ ist dabei gemeint, dass kein weiterer Ablauf der (den beteiligten Prozessen zugrundeliegenden) Algorithmen möglich ist, bei dem die verklemmten Prozesse deblockiert werden können. Als Verklemmung wird ein Zustand bezeichnet, in dem Prozesse verklemmt sind.
In diesem Kapitel werden solche Zustände charakterisiert und an einfachen Beispielen illustriert. Es werden Maßnahmen zu ihrem Ausschluss und zu ihrer Erkennung und Auflösung erörtert; zu ihrer Vermeidung wird der Bankiers-Algorithmus von Dijkstra vorgestellt. Abschließend werden Verklemmungswahrscheinlichkeiten berechnet und alle Gegenmaßnahmen bewertet.
Christian Maurer

9. Monitore

Zusammenfassung
Alle bisher gezeigten Beispiele verdeutlichen einige Nachteile der Implementierung von Schlössern, die auch bei der Verwendung von Semaphoren nicht ausgeräumt werden können. Die geeignete Antwort auf dieses Problem ist Hoare zu verdanken, der das Paket-ähnliche Konzept der Monitore eingeführt hat.
In diesem Kapitel werden Hoares Idee vorgestellt, die notwendigen Begriffe präzisiert, Bedingungsvariable als Sprachmittel zur Synchronisation eingeführt und es wird gezeigt, wie sie zur Synchronisation diverser klassischer Probleme wie z. B. des beschränkten Puffers und des Leser-Schreiber-Problems angewendet werden. Den Konkurrenzproblemen aus unterschiedlichen Ansätzen zur Realisierung von Monitoren ist die eingehende Erörterung der Signal-Semantiken gewidmet. Es folgen das Rundrufkonzept und etliche Monitor-Lösungen: zur Barrierensynchronisation, zum schlafenden Barbier, zum Wecker von Hoare und zur Priorisierung kürzester Anforderungen. Den Abschluss bildet eine kurze Darstellung der Problematik der Schachtelung von Monitoraufrufen.
Christian Maurer

10. Universelle Monitore

Zusammenfassung
Der Nachweis der Äquivalenz von Semaphor- und Monitorkonzept sowie die Details zur Implementierung des Monitorkonzepts im vorigen Kapitel lassen sich – wie der Staffelstab-Algorithmus – als Vorlage zur Konstruktion einer universellen Synchronisationsklasse verwenden, den in diesem Kapitel entwickelten universellen Monitoren. Es geht aber nicht um die Protokolle zum Schutz kritischer Abschnitte, sondern um die Gewährleistung des gegenseitigen Ausschlusses von nebenläufigen Prozessen bei ihren Operationen auf gemeinsam genutzten Daten. Dabei soll es möglich sein, dass die Funktionen nur dann ausgeführt werden können, wenn bestimmte Bedingungen erfüllt sind, die – wie die Anweisungen – eventuell von den Daten abhängen.
Damit sind auch in C, Java und Go, die – streng genommen – das Monitorkonzept nicht unterstützen, Monitor-Lösungen auf sehr einfache Weise möglich, wofür hier viele bereits bekannte Beispiele gegeben werden: Semaphore, das Konto, beschränkte Puffer und der schlafende Barbier, Barrierensynchronisation, das Leser-Schreiber- und das Links-Rechts-Problem, die speisenden Philosophen und die Zigarettenraucher.
Christian Maurer

11. Botschaftenaustausch

Zusammenfassung
Alle bisher vorgestellten programmiersprachlichen Konstruktionen synchronisieren Prozesse bei ihrem Zugriff auf gemeinsame Variable, setzen also gemeinsamen Speicher voraus. Für verteilte Anwendungen wird aber ein Paradigma benötigt, bei dem Prozesse darauf nicht angewiesen sind: die Kommunikation durch den Austausch von Botschaften.
Das Kapitel beginnt mit der Einführung von Kanälen und der Definition des synchronen und asynchronen Botschaftenaustauschs, einfachen Beispielen dazu und eleganten Anwendungen dieser Konzepte: der Konstruktion von Semaphoren, beschränkten Puffern und Netzwerken von Filtern. Danach wird ,,selektives Warten“ vorgestellt, das dem Botschaftenaustausch die Ausdruckskraft aller anderen Synchronisationskonstrukte verleiht und die Einführung des Kunden-Anbieter-Paradigmas ermöglicht. In Go lässt sich auch ,,bewachtes selektives Warten“ realisieren, was sehr zur Übersichtlichkeit von Algorithmen beiträgt. Zu beiden Konzepten folgen wieder viele aus den vorigen Kapiteln bekannte Beispiele. Den Schluss des Kapitels bildet der Beweis der Äquivalenz der Ausdrucksstärke von Semaphorkonzept und Botschaftenaustausch sowie eine konzise Gegenüberstellung der Sprachmittel des Monitorkonzepts und des Kunden-Anbieter-Paradigmas.
Christian Maurer

12. Vergleich der bisherigen Sprachkonstrukte

Zusammenfassung
Die ausführliche Behandlung der grundlegenden Synchronisationstechniken mit dem Einsatz von Schlössern, Semaphoren, Monitoren und Botschaftenaustausch ermöglicht eine gute Einschätzung der jeweiligen Stärken und Schwächen dieser Sprachkonzepte.
Die wesentlichen Gesichtspunkte der bisherigen Kapitel werden hier noch einmal kurz dargestellt.
Christian Maurer

13. Netzweiter Botschaftenaustausch

Zusammenfassung
So leistungsfähig auch der bisher vorgestellte Botschaftenaustausch für viele Aufgaben ist, widerspricht dessen Konzept im Grunde dem Begriff der verteilten Programmierung, bei der kein gemeinsamer Speicher vorausgesetzt wird: Die Kommunikation zwischen verschiedenen Goroutinen, die – im Unterschied zu Betriebssystem-Prozessen – Leichtgewichtsprozesse mit gemeinsamem Adressraum sind, läuft in Go über Kanäle, die ja selber bereits gemeinsame Variable sind. Verteilter Botschaftenaustausch im strengen Sinn ist die Kommunikation zwischen verschiedenen Rechnern oder verschiedenen Betriebssystem-Prozessen auf einem oder mehreren Rechnern.
In diesem Kapitel wird ein Kanalkonzept vorgestellt, indem nach einer kurzen Skizze von Aspekten der Netzkommunikation auf der Grundlage von TCP/IP ein Paket entwickelt wird, das den Austausch von Botschaften in Netzwerken und auf dieser Grundlage die Realisierung verteilter Programme ermöglicht.
Als Beispiel für ein verteiltes Programm wird der Algorithmus von Ricart und Agrawala zum dezentralisierten gegenseitigen Ausschluss erläutert.
Christian Maurer

14. Universelle ferne Monitore

Zusammenfassung
In diesem Kapitel wird zuerst unsere Konstruktion der Netzkanäle so erweitert, dass sie auch für 1:n-Verbindungen verwendbar sind. Damit ist die Umsetzung des Kunden-Anbieter-Paradigmas netzweit möglich. Darüber hinaus erlaubt es die Entwicklung einer weiteren universellen Synchronisationsklasse: die der fernen Monitore. Deren Bedeutung liegt in ihrer Ähnlichkeit zu den konditionierten universellen Monitoren. Sie weisen eine Reihe von Vorteilen gegenüber den Prozedurfernaufrufen (,,remote procedure calls“): die recht einfache Erledigung von Aufgaben, die sonst nur mit ihnen möglich sind.
In etlichen Anwendungen erweist sich die Stärke dieses Konzepts: der Konstruktion verteilter Semaphore, Warteschlangen und beschränkter Puffer und der Implementierung des verteilten Leser-Schreiber- und Links-Rechts-Problems.
In den letzten drei Kapiteln über Netzwerktopologie, verteilte Tiefen- und Breitensuche und die Auswahl eines Leiters im lokalen Netzwerk wird von dieser Konstruktion intensiv Gebrauch gemacht.
Christian Maurer

15. Netzwerke als Graphen

Zusammenfassung
In diesem Kapitel wird das Konzept von Graphen aufgegriffen und formalisiert. Dazu wird ein abstrakter Datentyp als Interface vorgestellt, das Graphen beschreibt, und zu einem Interface für verteilte Graphen weiterentwickelt.
Der Grund dafür liegt auf der Hand: Ein Netzwerk stellt konzeptionell einen ungerichteten Graphen dar. Die Prozesse auf den beteiligten Rechnern, die durch ihren Namen oder ihre IP eindeutig definiert sind, bilden seine Ecken und die Kommunikationswege zwischen ihnen – realisiert durch Netzwerkleitungen, z. B. Ethernet-Kabel, und die Programme, die den Netzwerkverkehr – den Transport von Botschaften über das Netz – ermöglichen, z. B. TCP/IP, bilden seine Kanten.
In den folgenden Kapiteln wird sich zeigen, dass viele verteilte Algorithmen genau in diesen Rahmen passen.
Christian Maurer

16. Pulsschlag-Algorithmen

Zusammenfassung
In diesem Kapitel wird gezeigt, dass es für jeden Prozess in einem Netzwerk, der anfangs nur seine Nachbarn kennt, unter Einsatz netzweiten Botschaftenaustauschs möglich ist, den Graphen des Netzwerks vollständig kennen zu lernen. Dazu wird das Konzept der Pulsschlag-Algorithmen entwickelt.
Eine einfache Lösung dieses Problems arbeitet mit einer Repräsentation von Graphen in Form von Adjazenzmatrizen. Das setzt voraus, dass jeder Prozess globale Informationen über das Netzwerks hat: die Anzahl der Prozesse in ihm (zur Festlegung der Größe dieser Matrix) und den Durchmesser des Netzwerkgraphen. Diese Einschränkung führt zur Entwicklung eines graphenbasierten Algorithmus, der ohne dieses globale Wissen auskommt.
Christian Maurer

17. Traversierungsalgorithmen

Zusammenfassung
Tiefen- und Breitensuche – die Standardverfahren zum Durchlaufen von Graphen – sind Grundlage für viele Graphenalgorithmen wie z. B. die Konstruktion von Spannbäumen und Ringen (Kreisen) und die Suche nach kürzesten Wegen.
Wegen ihrer Bedeutung werden in diesem Kapitel Techniken zur Konstruktion von Algorithmen zur Tiefen- und zur Breitensuche in verteilten Graphen entwickelt. Sie liefern die entsprechenden Spannbäume und Tiefensuche ermöglicht es auch, Kreise zu finden.
In vielen Lehrbüchern über Verteilte Programmierung werden nur die Prinzipien der Algorithmen dargestellt, ohne auf konkrete Realisierungen einzugehen. Der nennenswerte Aufwand dafür in diesem Kapitel zeigt, dass das keineswegs vernachlässigbar ist.
Christian Maurer

18. Auswahlalgorithmen

Zusammenfassung
Für viele Aufgaben in Netzwerken werden Anbieterprozesse benötigt, um Dienstleistungen zu erbringen, z. B. zur Bereitstellung von Daten oder zur Koordinierung verteilter Daten. Um den gravierenden Auswirkungen des Ausfalls eines solchen Prozesses zu entgehen, müssen seine Dienste von einem anderen Prozess übernommen werden. Dazu ist es notwendig, dass sich die beteiligten Prozesse darüber einigen, wer von ihnen diese Rolle spielen soll.
Damit sind wir bei dem Problem der Auswahl eines Leiters, zu dem in diesem Kapitel einige Algorithmen vorgestellt werden, die das Problem für ringförmige Graphen lösen. In Verbindung mit unserer Ringkonstruktion aus dem vorigen Kapitel ist das Problem im Prinzip für jeden Graphen lösbar.
Christian Maurer

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise