nach oben

2018 | Buch

Kapitel lesen Erstes Kapitel lesen

Nichtsequentielle und Verteilte Programmierung mit Go

Synchronisation nebenläufiger Prozesse: Kommunikation – Kooperation – Konkurrenz

verfasst von: Dr. Christian Maurer

Verlag: Springer Fachmedien Wiesbaden

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Dieses Buch führt in die Nichtsequentielle und Verteilte Programmierung mit Go ein und stellt grundlegende Konzepte zur Synchronisation und Kommunikation nebenläufiger Prozesse systematisch dar. Dazu zählen unter anderem Schlösser, Semaphore, Fairness und Verklemmungen, Monitore sowie der lokale und netzweite Botschaftenaustausch. Um Lesern die Konzepte nahezubringen, greift der Autor immer wieder die gleichen klassischen Beispiele auf. Das erleichtert das Lernen, denn die vorgestellten Konzepte lassen sich auf diese Weise besser mit den Sprachmitteln vergleichen.

Das Buch folgt in seiner Grundstruktur den beiden Vorauflagen, enthält aber in der aktuellen, dritten Auflage einen neuen Teil zur Verteilten Programmierung mit drei Klassen von Algorithmen. Neben Netzwerken als Graphen werden dort unter anderem Algorithmen behandelt, die die Auswahl eines Leiters im Netzwerk ermöglichen oder das Kennenlernen des vollständigen Netzwerks, wenn jeder Beteiligte anfangs nur seine Nachbarn kennt.

Die Algorithmen sind in der Programmiersprache Go formuliert. Mit dieser Sprache lassen sich zahlreiche Synchronisationskonzepte ausdrücken. Go bietet aufgrund der einfachen Syntax außerdem den Vorteil, dass auch Leser ohne Vorkenntnisse den grundlegenden Konzepten folgen können. In den Abschnitten zu Schlössern, Semaphoren und Monitoren werden darüber hinaus auch einige grundlegende Ansätze zur Programmierung in C und Java vorgestellt.

Das Buch richtet sich an Studierende der Informatik und wurde für die Neuauflage klarer gegliedert. Zahlreiche Abschnitte wurden zudem teils erheblich erweitert. So wurden zusätzliche Algorithmen in das Kapitel über Schlösser aufgenommen und ein kurzes Kapitel übergrundlegende Aspekte der Softwaretechnik und deren Realisierung in Go eingefügt. Die Abschnitte über Semaphore und Monitore wurden um das Problem der Zigarettenraucher erweitert und den universellen Synchronisationsklassen sind nun eigene Kapitel gewidmet. Sämtliche Quelltexte sind online verfügbar.

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. Schlösser

Zusammenfassung

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 Zustandsvariablen 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

3. Pakete, Interfaces und abstrakte Datentypen

Zusammenfassung

Dieses Kapitel dient lediglich dazu, einige Aspekte der in diesem Buch verwendeten programmiertechnischen Verfahrensweisen darzustellen – im Wesentlichen, wie sich fundamentale softwaretechnische Grundprinzipien in Go realisieren lassen.

Anhand einiger Beispiele – dem Interface Object und den abstrakten Datentypen Warteschlange und beschränkter Puffer – wird das detailliert erläutert. Diese Beispiele werden in einigen der folgenden Kapitel gebraucht.

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

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.

Wie im vorigen Kapitel beschränken wir uns dabei auf den Einsatz von Go und kümmern uns – abgesehen von den technischen Aspekten – weder um C noch um die sehr komplexen entsprechenden Konstruktionen in Java.

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, der Implementierung des verteilten Leser-Schreiber- und Links-Rechts-Problems und einer verteilten Lösung des Problems der speisenden Philosophen.

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

Titel: Nichtsequentielle und Verteilte Programmierung mit Go
verfasst von: Dr. Christian Maurer
Verlag: Springer Fachmedien Wiesbaden
Electronic ISBN: 978-3-658-21153-0
Print ISBN: 978-3-658-21152-3
DOI: https://doi.org/10.1007/978-3-658-21153-0