Parallelprogrammierung - Komplex 1

1

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

2

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)

3

  • 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

4

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

5

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

6

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

7

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)

8

  • 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

9

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

10

  • 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

11

  • 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

12

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

13

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)
 
wiki/study/scripts/pp/k1.txt · Last modified: 2005/07/18 18:28 (external edit)
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki