Parallelprogrammierung - Komplex 1

• Programm- (Task, Job), Prozedur-, Ausdrucks-, Bitebene, Prozedur und Programmebene
• Verschachtelte Verarbeitung
• Synchronisation beim Lesen/Schreiben nötig

Synchron:

• zentrale Programmsteuerung
  • übergeordnetter Rechner, Gleichtakt, Betriebssystem
  • Synchronisation erfolgt außerhalb der parallelen Prozesse

Asynchron:

• keine zentrale Steuerung
  • Prozesskommunikation nötig
  • Aufwand, d.h. nur für grobkörnige Systeme
  • Synchronisation erfolgt in den parallelen Prozessen (Programmierer)

• bestehen intern aus einer sequentiellen Abarbeitungsfolge
• sind zueinander potentiell parallel ausführbar d.h. kausal-logisch beliebige Abarbeitungsreihenfolge, sie können auch real parallel laufen
• parallele Prozesse: aktiv ausgeführte Nebenläufigkeit

Kooperation:

• Teilprozesse lösen eine gemeinsame Aufgabe, d.h. sie sind abhängige

Typen:

• datenorientierte Kooperation (Erzeuger- Verbraucher-Systeme)
• auftragsorientierte Kooperation (Client-Server-Systeme)

Konkurrenz:

• Teilaktivitäten behindern einander beim Zugriff auf gemeinsame Betriebsmittel
• Prozesse können funktionell abhängig oder unabhängig sein

Synchronisation:

• ist die Koordinantion von Kooperation und Konkurrenz

Kommunikation:

• Datenaustausch zur gegenseitigen Synchronisation

Eltern-Kind-Prozesse

• Vermischung von Deklarationen und Synchronisation, unstrukturiert, fehleranfälig

Co-Routinen:

• nur Qusiparallelbetrieb, PRozessorweitergabe, Hierachiebeziehung fehlt im Unterschied zu Routinen, mehrere Eintrittspunkte
• Vorteil: spart Verwaltungsaufwand (für kleine Systeme geeignet)

Nebenläufige Blöcke:

• Parallelbetrieb, zentrale Kontrollflussspaltung → keine Autonomie

Remote Procedure Call:

• Parallelbetrieb, Client-Server-Auftragsvergabe, Protokolle kompliziert

In allen drei Sprachen werden parallele Prozesse strukturiert deklariert. Sie unterscheiden sich in dem Start von paralleleln Prozessen.

PEARL:

• expliziter Prozessstart
  • durch Anweisung in Prozessen
  • durch das Betriebssystem beim Erreichen von Ereignissen

Synchronisation: Semaphorkonzept ADA:

• impliziter Prozessstart bei Deklaration, explizit bei Ereignissen

Synchronisation: Rendevouskonzept Cuncurrent PASCALL (==RPC):Remote Procedure Call:

• implizierter Prozesstart bei der Initialisierung deklarierter Prozesse

Synchronisation: Monitorkonzept

PCB ist Datenstruktur zur Verwaltung von parallelen Prozessen; alle PCB's bilden die Prozesstablle

Beschreibungsteil:

• Name, Priorität, Betribesmittel, Aktivierungsangaben (durch Programmierer)

Laufzeitinformationen:

• Zustand, Prozesszeit (enstehen zur Laufzeit) Verwaltungsinformationen:
• zu Auf- und Entnahme in Listen (entstehen zur Laufzeit)

• Nebenläufigkeit, Nichtdeterminismus → Unendlichkeit
• kausale Abhängigkeit → einseitiger Ausschluss
• Ressourcenteilung → gegenseitiger Ausschluss
• Datenaustausch, beschränkter Puffer → Erzeuger-Verbraucher-Problem
• nichtexklusive und exklusive Zugriffe → Leser-Schreiber-Problem

+-----+                         REST: beliebige Aktivitäten, auf die der Prozess
|     v				kurz in einen kritischen Abschnitt eintreten muss
|   Rest
|   Vorprotokoll
|   crit                    Vorprotokoll: ist Eintritt in crit erlaubt? Wenn ja
|   Nachprotokoll	Zutritt sperren
|   Rest
|     |
+-----+                        Nachprotokoll: Zutritt freigeben

Protokolle:

• realisieren Interprozesskimmmunikation
• stellen Aufwands- und Fehlerquelle dar

Wenn: Protokolle + kritische Abschnitte sehr kurz sind, nicht unterbrechbar, nicht abstürzen (d.h. sie terminieren) Dann: darf der Rest der Prozesse parallel, d.h. verschachtelt ablaufen

• Sicherheit (Korrektheitsanforderungen)
• Sicherheitsaspekte erweitern die Spezifikation
  • spezifiziert werden Nebenläufigkeit, Reichenfolge- und Ausschlussbedingungen
  • sicheres Programmsystem, wenn die Sicherheitsspekzifikation eingehalten wird
• Lebendigkeit (Korrektheitsanforderung)
  • lebendiges Programmsystem, wenn alle enthaltenen parallelen Prozesse schliesslich zu einem Ende kommen.
  • Verletzung der Lebendigkeit durch Verklemmung, Aussperrung

• Prozess oder eine Gruppe von Prozessen wartet eine Bedingung, die nur durch den Prozess oder durch Prozesse der Gruppe selbst erfüllt werden kann.

Vermeidung:

• innerhalb einer P-V-.Struktur wird jeweils nur 1 Betriebsmittel belegt
• statische oder simulative Vorabanalyse des Betriebsmttelbedarfs

Beseitigung:

• periodische Verhaltensüberprüfung durch das Betriebssystem
• entziehbare bzw. nichtexklusive Betriebsmittel

             Erzeuger                 Verbraucher
	  +->( S1 )>-+          +->+  +->( S4 )>-+
         /            \	       /    \/            \
	---           --- ( S5 )    ---           ---
	 \            /\     /       \            /
	  +-<( S2 )<-+	+-->+         +-<( S3 )<-+	

Init:

• M(S0)=n, S== alle Prozesse im System, passive Prozesse
• M(S1)=M(S2)=M(S3)=M(S4)=0; M(S5)=k

Lauf:

• S1 wollen schreiben, S2 schreibende, S3 wollen lesen, S4 lesende
• M(S5)=k → k-LEser, 1 Schreiber (Synchronisationstabelle)