Nebenläufige Programme

ISBN-13: 9783540577836 / Niemiecki / Twarda / 1994 / 488 str.

Ralf G. Herrtwich; G]nter Hommel; R. Krischker

Opis

Die Programmierung nebenl ufiger, verteilter und echtzeitabh ngiger Systeme ist durch den zunehmenden Einsatz von neuartigen Rechnerarchitekturen und Rechnernetzen, z.B. in der Telekommunikation, der Produktionstechnik und der B roautomation, gegen ber der klassischen sequentiellen Programmierung in den Vordergrund ger ckt. Dieses Buch stellt die daf r grundlegenden Konzepte, Methoden und Techniken im Zusammenhang dar. Das Buch wendet sich an Informatiker, Ingenieure und Naturwissenschaftler. Es soll sowohl Studierenden als auch den in der Praxis T tigen ein umfassendes Grundwissen vermitteln, das ihnen das Verstehen und Anwenden der erforderlichen Mechanismen erm glicht und sie auch in die Lage versetzt, solche Mechanismen selbst zu implementieren.

Spis treści

Prolog.- 0 Motivation.- A: Strukturen nebenläufiger Programmsysteme.- 1 Nebenläufigkeit.- 1.1 Zusätzliche Eigenschaften von Algorithmen.- 1.1.1 Verzicht auf Sequentialität.- 1.1.2 Verzicht auf Determinismus.- 1.1.3 Nebenläufigkeit, Nichtdeterminismus, Nichtdeterminiertheit.- 1.2 Prozesse.- 1.2.1 Kooperierende und konkurrierende Prozesse.- 1.2.2 Synchronisation und Kommunikation.- 2 Modularität.- 2.1 Module.- 2.2 Modularten.- 2.2.1 Abstrakte Datenstrukturen.- 2.2.2 Abstrakte Datentypen.- 2.2.3 Generische abstrakte Datentypen.- 2.3 Modularität in Modula-2.- 2.4 Modularität in Ada.- 3 Prozeßbeschreibung.- 3.1 Ablauforientierte Prozeßbeschreibung.- 3.1.1 Prozeßablösung.- 3.1.2 Koroutinen.- 3.1.3 Nebenläufige Blöcke.- 3.1.4 Prozeßabzweigung.- 3.2 Prozeßdeklaration.- 3.2.1 Prozesse in PEARL.- 3.2.2 Prozesse in Ada.- B: Abwicklung von Prozessen.- 4 Prozeßverwaltung.- 4.1 Betriebsmittel für Prozesse.- 4.2 Zuteilung eines Prozessors.- 4.2.1 Zustandsübergänge von Prozessen.- 4.2.1.1 Verwaltungsarbeiten bei Zustandsübergängen.- 4.2.2 Zustandsübergänge in PEARL.- 4.3 Planung.- 4.3.1 Planungskriterien.- 4.3.2 Planung im prozessorbeschränkten System.- 4.3.2.1 Einplanung nach Wartezeit.- 4.3.2.2 Einplanung nach Laufzeit.- 4.3.2.3 Zyklische Einplanung.- 4.3.2.4 Mehrstufige Warteschlangen.- 4.3.3 Berücksichtigung zusätzlicher Betriebsmittel.- 5 Unterbrechungen.- 5.1 Unterbrechungsarten.- 5.2 Asynchrone Unterbrechungen.- 5.2.1 Beispiel der Unterbrechungsbehandlung beim MC 68000.- 5.2.2 Unterbrechungsbehandlung in PEARL.- 5.2.3 Unterbrechungsbehandlung in Ada.- 5.3 Ausnahmebedingungen.- 5.3.1 Ausnahmebehandlung mit konventionellen Sprachmitteln.- 5.3.2 Ausnahmebehandlung mit speziellen Sprachmitteln.- 5.3.3 Ausnahmebehandlung in PEARL.- 5.3.4 Ausnahmebehandlung in Ada.- 6 Echtzeitabhängigkeit.- 6.1 Echtzeitbetrieb.- 6.2 Zeitbedingungen.- 6.2.1 Technische Prozesse.- 6.2.2 Verarbeitung von Prozeßdaten.- 6.2.3 Maximale Antwortzeiten.- 6.2.3.1 Beispiel einer Meßwerterfassung.- 6.2.3.2 Beispiel einer Paketverteilanlage.- 6.3 Zeitgerechte Einplanung.- 6.3.1 Planung für Einprozessorsysteme.- 6.3.2 Planung für Mehrprozessorsysteme.- 6.4 Zeitangaben in Programmen.- 6.4.1 Zeitangaben in PEARL.- 6.4.2 Zeitangaben in Ada.- 6.5 Zeitüberwachung.- C: Abhängigkeiten zwischen Prozessen.- 7 Synchronisation.- 7.1 Synchronisationsbedarf.- 7.1.1 Vermeiden von Nichtdeterminiertheit.- 7.1.2 Vermeiden von Inkonsistenz.- 7.1.3 Gewährleisten einer logischen Abfolge.- 7.2 Synchronisationsarten.- 7.2.1 Einseitige Synchronisation.- 7.2.2 Mehrseitige Synchronisation.- 7.3 Typische Synchronisationsprobleme.- 7.3.1 Betriebsmittelnutzung.- 7.3.2 Leser und Schreiber.- 7.3.3 Speisende Philosophen.- 8 Petri-Netze.- 8.1 Petri-Netze ohne Marken.- 8.1.1 Kanal-Instanz-Netze.- 8.1.2 Netzmorphismen.- 8.2 Petri-Netze mit Marken.- 8.2.1 Stellen-Transitions-Netze.- 8.2.2 Beispiele für die Synchronisation in Petri-Netzen.- 8.2.2.1 Produzenten und Konsumenten.- 8.2.2.2 Leser und Schreiber.- 8.2.2.3 Speisende Philosophen.- 8.2.3 Petri-Netze mit unterscheidbaren Marken.- 9 Verklemmungen.- 9.1 Ursachen für Verklemmungen.- 9.2 Verklemmungsvermeidung durch Regeln.- 9.3 Verklemmungsvermeidung durch Bedarfsanalyse.- 9.4 Verklemmungserkennung.- D: Kommunikation über gemeinsame Variablen.- 10 Schloßvariablen.- 10.1 Gegenseitiger Ausschluß mit Schloßvariablen.- 10.2 Schloßalgorithmen mit unteilbaren Operationen.- 10.3 Schloßalgorithmen ohne spezielle Operationen.- 10.3.1 Schloßalgorithmen für zwei Prozesse.- 10.3.1.1 Lösungsansatz 1.- 10.3.1.2 Lösungsansatz 2.- 10.3.1.3 Lösungsansatz 3.- 10.3.1.4 Lösungsansatz 4.- 10.3.1.5 Lösungsansatz 5.- 10.3.1.6 Lösungsansatz 6.- 10.3.1.7 Lösungsansatz 7.- 10.3.2 Schloßalgorithmen für eine beliebige feste Prozeßzahl.- 10.3.2.1 Lösungsansatz 1.- 10.3.2.2 Lösungsansatz 2.- 10.3.2.3 Lösungsansatz 3.- 10.4 Aktives Warten und andere Probleme.- 11 Semaphore.- 11.1 Synchronisation mit Semaphoren.- 11.1.1 Gegenseitiger Ausschluß mit Semaphoren.- 11.1.2 Einseitige Synchronisation mit Semaphoren.- 11.2 Implementierung von Semaphoren.- 11.3 Beispiele für die Synchronisation mit Semaphoren.- 11.3.1 Produzenten und Konsumenten.- 11.3.2 Produzenten und Konsumenten mit binären Semaphoren.- 11.3.3 Leser und Schreiber.- 11.3.4 Speisende Philosophen.- 11.3.5 Zigarettenraucher.- 11.4 Erweiterungen von Semaphoren.- 11.4.1 Additive Semaphore.- 11.4.2 Mehrfach-Semaphoroperationen.- 11.5 Semaphore in PEARL.- 11.5.1 Gewöhnliche Semaphore.- 11.5.2 Eingeschränkte additive Semaphore.- E: Abstraktion von Semaphoren.- 12 Bedingte kritische Abschnitte.- 12.1 Bindung von Bedingungen an kritische Abschnitte.- 12.2 Implementierung bedingter kritischer Abschnitte.- 12.3 Synchronisation mit bedingten kritischen Abschnitten.- 12.4 Bedingte kritische Abschnitte in Edison.- 13 Monitore.- 13.1 Synchronisation mit Monitoren.- 13.1.1 Gegenseitiger Ausschluß im Monitor.- 13.1.2 Ereignisvariablen.- 13.2 Implementierung von Monitoren.- 13.3 Beispiele für die Synchronisation mit Monitoren.- 13.3.1 Produzenten und Konsumenten.- 13.3.2 Leser und Schreiber.- 13.4 Monitorvarianten.- 13.4.1 Einelementige Warteschlangen in Concurrent Pascal.- 13.4.2 Priorisiertes Warten in Concurrent Euclid.- 13.4.3 Bedingungsgebundene Ereignisvariablen.- 13.4.4 Signale als Hinweise in Mesa.- 13.4.5 Geschachtelte Aufrufe von Monitorprozeduren.- 14 Pfadausdrücke.- 14.1 Synchronisation mit Pfadausdrücken.- 14.1.1 Pfadoperatoren.- 14.1.2 Geschlossene Pfadausdrücke.- 14.1.3 Offene Pfadausdrücke.- 14.2 Beispiele für die Synchronisation mit Pfadausdrücken.- 14.2.1 Ringpuffer.- 14.2.2 Speisende Philosophen.- 14.3 Probleme mit Pfadausdrücken.- F: Kommunikation über Nachrichten.- 15 Nachrichten.- 15.1 Nachrichtenaustausch.- 15.1.1 Senden von Nachrichten.- 15.1.2 Empfangen von Nachrichten.- 15.1.3 Kopieren beim Nachrichtenaustausch.- 15.1.3.1 Synchroner Nachrichtenaustausch.- 15.1.3.2 Asynchroner Nachrichtenaustausch.- 15.1.3.3 Dualität beim Nachrichtenaustausch.- 15.2 Selektiver Nachrichtenaustausch.- 15.2.1 Selektives Empfangen.- 15.2.2 Selektives Senden.- 15.2.3 Erweiterungen des selektiven Nachrichtenaustauschs.- 15.3 Nachrichtenaustausch in CSP.- 15.3.1 Sprachelemente von CSP.- 15.3.1.1 Kommunikationsanweisungen.- 15.3.1.2 Nichtdeterministische Auswahl.- 15.3.1.3 Prozesse.- 15.3.2 Beispiele für die Synchronisation mit CSP.- 15.3.2.1 Rückkehr in den Zoo.- 15.3.2.2 Speisende Philosophen.- 15.3.2.3 Sieb des Eratosthenes.- 15.3.3 Korrektheitsbeweise für CSP-Programme.- 15.4 Nachrichtenaustausch in Occam.- 15.4.1 Kommunikationsanweisungen.- 15.4.2 Replikatoren.- 15.4.3 Beispiel einer einfachen Steuerung.- 16 Kommunikationskanäle.- 16.1 Adressierung.- 16.1.1 Direkte Benennung.- 16.1.2 Briefkästen.- 16.1.3 Ports.- 16.1.3.1 Rückmeldungen.- 16.1.3.2 Synchronisation von Prozeßklassen mit Ports.- 16.1.3.3 Synchronisationsverhalten beim Zugriff auf Ports.- 16.1.4 Verbindungen.- 16.1.4.1 Einrichten von Verbindungen.- 16.1.4.2 Verbindungen in Mehrrechner-PEARL.- 16.2 Dynamische Kommunikationskanäle.- G: Abstraktion von Nachrichten.- 17 Prozedurfernaufrufe.- 17.1 Aktionsorientierte Kommunikation.- 17.1.1 Prozeduren als Kommunikationsmittel.- 17.1.2 Nebenläufigkeit bei Prozedurfernaufrufen.- 17.2 Implementierung von Prozedurfemaufrufen.- 17.3 Lokale und ferne Prozeduren.- 17.3.1 Ausführen femer Prozeduren.- 17.3.2 Parameter ferner Prozeduren.- 17.4 Prozedurfernaufrufe in DP.- 17.4.1 Prozesse und Prozeduren.- 17.4.2 Bewachte Anweisungen.- 17.4.3 Beispiele für die Synchronisation mit DP.- 18 Rendezvous.- 18.1 Eingehen eines Rendezvous.- 18.1.1 Selektives Eingehen von Rendezvous.- 18.1.2 Nebenläufigkeit beim Rendezvous.- 18.2 Beispiele für die Synchronisation mit Rendezvous.- 18.2.1 Ringpuffer.- 18.2.2 Leser und Schreiber.- 18.3 Rendezvous in Ada.- 18.3.1 Anbieten von Rendezvous.- 18.3.2 Beantragen von Rendezvous.- 18.3.3 Zeitüberwachung von Rendezvousausführungen.- H: Strukturen verteilter Programmsysteme.- 19 Verteiltheit.- 19.1 Verteilte Systeme.- 19.1.1 Physikalische Verteiltheit der Hardware.- 19.1.2 Physikalische Verteiltheit der Software.- 19.1.2.1 Dezentralisierung.- 19.1.2.2 Gemeinsame Nutzung von Betriebsmitteln.- 19.1.2.3 Erhöhen der Zuverlässigkeit.- 19.1.3 Von der physikalischen zur logischen Verteiltheit.- 19.2 Unschärfen in verteilten Systemen.- 19.3 Architektur verteilter Systeme.- 19.3.1 Dienste und Protokolle.- 19.3.2 Typische Schichtenstruktur verteilter Systeme.- 19.3.2.1 Anwendungssystem.- 19.3.2.2 Programmiersystem.- 19.3.2.3 Betriebssystem.- 19.3.2.4 Kommunikationssystem.- 20 Konfiguration.- 20.1 Topographie verteilter Systeme.- 20.1.1 Physikalische Topographie.- 20.1.2 Logische Topographie.- 20.1.3 Abbilden der Topographien.- 20.2 Konfiguration in Occam.- 20.3 Konfiguration in Mehrrechner-PEARL.- 20.3.1 Beschreibung der physikalischen Topographie.- 20.3.1.1 Stationsteil.- 20.3.1.2 Netzteil.- 20.3.1.3 Systemteü.- 20.3.2 Logische Topographie und Konfiguration.- 20.4 Benennung in verteilten Systemen.- 20.4.1 Namensbildung.- 20.4.2 Namensverwaltung.- 20.4.2.1 Namensvergabe.- 20.4.2.2 Namensverteilung.- 21 Protokolle.- 21.1 Aufgaben von Protokollen.- 21.1.1 Fehlererkennung.- 21.1.2 Reihenfolgeerhaltung.- 21.1.3 Flußkontrolle.- 21.1.4 Nachrichtenbestätigung.- 21.2 Abwicklung von Protokollen.- 21.2.1 Protokolle als Spielregeln.- 21.2.2 Protokollmaschinen.- 21.2.2.1 Protokollspezifikation.- 21.2.2.2 Protokollanwendung.- 21.3 Protokollspezifikation mit RSPL-Z.- 21.3.1 Sprachelemente von RSPL-Z.- 21.3.1.1 Sequenzausdrücke.- 21.3.1.2 Werdegang.- 21.3.2 Spezifikation eines einfachen Protokolls.- 21.4 Ein Protokoll zur datenorientierten Kommunikation.- 21.4.1 Protokoll auf Empfängerseite.- 21.4.2 Protokoll auf Senderseite.- 21.5 Ein Protokoll zur aktionsorientierten Kommunikation.- 21.5.1 Semantik von Prozedurfernaufrufen.- 21.5.1.1 Aufruf ferner Prozeduren.- 21.5.1.2 Ausführen ferner Prozeduren.- 21.5.2 Beispiel einer Fernaufrufimplementierung.- 21.5.2.1 Starten eines Fernaufrufs.- 21.5.2.2 Verwaltung von eigenen und fremden Femaufrufen.- 21.5.2.3 Weiterleitung von Fernaufrufen an fremde Rechner.- 21.5.2.4 Empfang von fremden Fernaufrufen im eigenen Rechner.- Epilog.- 22 Schlußbeispiel.- 22.1 Aufgabenstellung.- 22.2 Programmstruktur.- 22.3 Programminitialisierung.- 22.4 Steuerung der Kabinen.- 22.4.1 Fahrt einer Kabine über die Strecke.- 22.4.2 Fahrt einer Kabine in den Bahnhof.- 22.5 Sicherung der Streckenabschnitte.- 22.6 Verteilen von Fahraufträgen.- 22.7 Fahrgäste.- Nachwort.- Literatur.