Table of Contents

Parallelprogrammierung - Komplex 3

1

Ziel:

  • Beseitigung/ Reduzierung von Fehlern, die durch Auswertung des unstrukturierten Semaphorenkonzepts entstehen können

Fehler:

  • Reihenfolge bei P- und V-Operatoren
  • fehlende P- und V- Operatoren
  • Aussperrung

Abstraktionen:

  • erweiterte Semaphorenoperatoren
    • additive Semaphoroperatoren
    • Mehrfachsemaphoroperationen
  • strukturierte Konzepte
    • kritische Regionen, Pfade, Monitor

2

Anwendung:

  • Einführung von unterschiedlichen Prozessklassen, die sichgegenseitig ausschliessen
    • Unterscheidung von exklusiven und nicht exklusiven
    • Zugriffen wird möglich

Erweiterte additive Semaphoroperatoren:

Leser: P(S(-1)) Schreiber: P(S(-n))
... ...
V(S(+1)) V(S(+n))

Implementierung:

  • jede Prozessklasse erhällt einen Semaphor mit eigener Warteschlange für die Klassenprozesse (Klassensemaphor)
  • Einführung eines Zählers: zählt wie viele Prozesse von der Klassensemaphorwarteschlange sind
  • Zählerzugriff wird durch Zählersemaphor geschützt
  • globaler Semaphor für gegenseitigen Ausschluss

3

Anwendung:

  • übergreifen der Prüfung mehrerer Eintrittsbedingungen für einen kritischen Abschnitt
    • Erfassung mehrerer Bedingungen

Erweiterte Mehrfachsemaphoroperationen:

P{(S1),(S2),...,(Sn)}
V{(S1),(S2),...,(Sn)}
  • Operationen arbeiten auf einer Menge von Semaphoren für unterschiedliche Bedingungen
  • wenn eine Bedingung nicht erfüllt ist, wird der ausführbare Prozess blockiert und der Zugriff auf alle weiteren Semaphoren der Menge wird freigegeben

4

Anwendung:

  • Spezifikation von Synchronisation

Vorteile:

  • Abstrakte formale Notation der Synchronisation
  • automatische Codegenerierung der Semaphorlösung

Prinzip:

  • Pfadoperatoren bestimmen die Synchronisation von Operation (paralleler Prozessen) und deren Zugriff auf Objekte (Kritische Abschnitte)
    • Objekt (abstrakter Datentyp) wird definiert
    • Objekt wird als Pfadausdruck Spezifiziert

Aufbau von Pfadobjekten und Pfadausdrücken: Objekte bestehen aus:

  1. Initialisierungsteil:
    • wird einmal ausgeführt → Objekt wird existent
  2. Operation:
    • alle zugelassenen Operationen am Objekt werden algorithmisch festgelegt
    • Pfadausdrücke bestehen aus Operation und Operatoren
  3. Operatoren:
    • Reihenfolge von Operationen
    • (beschränkte, bedingte) Parallelausführung von Operationen

Beispiel:

PATN N:(1:(a);1:(b)) END;
  • a und b schließen sich aus (a vor b), zu jeder a- Operation gibt es eine b- Operation, dabei darf die Zahl der angefangenen a-Operation die b-Operationen maximal um N überschreiben.

5

Grundidee:

  • Monitor als abstrakter Datentyp
  • Zentralisierung kritischer Abschnitte als Monitorprozeduren
    • Fehlersenkung
  • Monitorprozeduraufruf schließt Prozesse aus

Aufbau:

  • Deklaration der Monitordaten nd Monitorprozeduren als abstrakter Datentyp
  • Monitor- Body (Initialisierung)

Monitorsystem:

  • ein oder mehrere Monitore
  • Menge von parallelen Prozessen

6

Prozesse an der Warteschlange einer Bedingung werden vor weiteren externen parallelen Prozessen priorisiert. Das Monitorzustandmodell muss erweitert werden wenn Signal(cond) icht unbedingt als letzte Anweisung einer Monitorprozedur stehen muss.

7

Monitorprozeduraufruf:

  • 1. Prozedur enthält weder Signal noch wait Operationen
    • Monitor aktiv, alle weiteren externen Prozesse werden beim Aufruf einer Monitorprozedur ausgeschlossen (M_WS), bis der Monitor wieder passiv wird.
  • 2. Prozedur enthält wait(cond) Operation
    • wenn cond=false Prozess im cond_WS, Monitor wieder passiv
  • 3a. Prozedur enthält Signal(cond) Operation als letzte Operation
    • Prozess setzt cond=true und verlässt Monitor, wobei der Prozess in cond_WS erweckt wird
  • 3b. nach Signal(cond) Operation weitere Anweisungen
    • Prozess setzt cond=true wobei der Prozess in cond_WS erweckt wird, der Signalisierende Prozess gelangt in eine Warteschlange

Warteschlangen:

  • Monitorwarteschlange M_WS
  • für jede Bedingung je eine cond_WS
  • selten implementiert: cond_WS für signal(cond)

8

noempty (cond)

  • Funktion gibt Rückgabewert true, wenn cond_WS voll ist

Anwendung:

  • in Kombination mit signal, wait und logischen Anweisungen können unterschiedliche Prioritäten implementiert werden.

9

 
wiki/study/scripts/pp/k3.txt · Last modified: 2005/07/18 18:10 (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