Kapitel 3.3 - 3.5

Die (Gesamt-)Ausführungszeit T (Execution Time) eines parallelen Programms ist die Zeit zwischen dem Starten der Programmausführung auf einem der Prozessoren bis zu dem Zeitpunkt, an dem der letzte Prozessor die Arbeit an dem Programm beendet hat

Während der Programmausführung sind alle Prozessoren in einem der drei Zustände

• Rechnend

• Kommunizierend

• Wartend auf Kommunikation (idle)

Relative Beschleunigung (relative Effizienz)

• Algorithmenabhängig

• Man benutzt zur Ermittlung von T(1) den parallelen Algorithmus so, als sei er sequentiell, und misst dessen Laufzeit auf einem Multiprozessorsystem

Absolute Beschleunigung (absolute Effizienz)

• Algorithmenunabhängig

• Man benutzt zur Ermittlung von T(1) den besten bekannten sequentiellen Algorithmus und misst dessen Laufzeit auf einem Multiprozessorsystem

Skalierbarkeit eines Parallelrechners

• Das Hinzufügen von weiteren Verarbeitungselementen führt zu einer kürzeren Gesamtausführungszeit, ohne dass das Programm geändert werden muss

• Insbesondere meint man damit eine lineare Steigerung der Beschleunigung mit einer Effizienz nahe bei Eins

• Wichtig für die Skalierbarkeit ist eine angemessene Problemgröße

strong scaling:

• Bei fester Problemgröße und steigender Prozessorzahl wird ab einer bestimmten Prozessorzahl eine Sättigung eintreten

• Die Skalierbarkeit ist in jedem Fall beschränkt

weak scaling:

• Skaliert man mit der Anzahl der Prozessoren auch die Problemgröße (scaled problem analysis), so tritt dieser Effekt bei gut skalierenden Hardware- oder Software-Systemen nicht auf

• Der Speed-up lässt sich dann allerdings nicht direkt messen

• Messung der Gesamtausführungszeit & max. Problemgröße

• Um Speedup abzuschätzen

• Sei q der Anteil der Operationen, der parallel ausgeführt werden kann

Verzicht auf Forderung nach sequentieller Ausführung von Anweisungen kann zweierlei bedeuten

• Anweisungen können parallel von mehreren Prozessoren ausgeführt werden

• Anweisungen können in einer beliebigen Folge sequentiell von einem Prozessor ausgeführt werden

  • Begriff: nebenläufig (concurrent)

Parallelität ist damit eine spezielle Form der Nebenläufigkeit

• Nebenläufige Anweisungen sind nur dann parallel, wenn für ihre Ausführung tatsächlich mehrere Prozessoren zur Verfügung stehen

Jedoch zu beachten

• Meist laxerer Sprachgebrauch – „nebenläufig“ und „parallel“ oft gleichgesetzt

• Im folgenden: „Parallelität“ ist eine Kurzform für die Möglichkeit der parallelen (gleichzeitigen) Ausführung mehrerer Operationen

Ein Prozess (Rechenprozess) ist eine sequentielle Folge von Aktivitäten, durch die eine in sich abgeschlossene Aufgabe bearbeitet wird

• Programme, aus denen mehrere Prozesse resultieren, werden auch als parallele Programmsysteme bezeichnet

• Definition (nach Wolfgang K. Giloi. Rechnerarchitektur. Springer, 1993, ISBN 3-540-56355-5):

Ein Prozess wird als eine funktionelle Einheit definiert, die aus

• einem zeitlich invarianten Programm

• einem Satz von Daten, mit denen der Prozess initialisiert wird

• einem zeitlich varianten Zustand besteht

Prozessumgebung: die geschützten Adressbereiche eines Prozesses

• Jeder Prozess hat seine eigenen Code- und Datenbereiche im Speicher, deren Zugang allen anderen Prozessen verwehrt ist

• Die Adressbereiche sind in Seiten- oder Segmenttabellen niedergelegt, deren Inhalte bei einem Umgebungswechsel ausgetauscht werden müssen

• Ein Prozesswechsel bedingt somit in der Regel einen Umgebungswechsel

Prozesskontext: die Registerwerte des mit der Prozessausführung beschäftigten Prozessors

Zum Kontext gehören

• der Befehlszähler,

• Zeiger auf den Ausführungskeller (stack) oder den Aktivierungssatz,

• weitere Zustandsinformationen und Datenwerte, die bei der Wiederaufnahme einer Prozessausführung gebraucht werden

Ein Prozesswechsel bedingt somit auch immer einen Kontextwechsel

Aus Betriebssystemsicht führt das Prozesskonzept zu erheblichem Laufzeitaufwand

• Das Erzeugen eines Prozesses erfordert zeitaufwendige Aufrufe des Betriebssystems

• Falls Prozesse mehrerer Benutzer gleichzeitig ablaufen sollen, sind Zugriffsschutzmechanismen nötig

• Ein Prozesswechsel ist oft – bedingt durch einen Kontext- und Umgebungswechsel – eine relativ langsame Operation

• Falls Prozesse miteinander kommunizieren, müssen Kommunikationswege und Synchronisationsoperationen eingerichtet werden

Schwergewichtige Prozesse sind Prozesse im klassischen Sinne

• Typisch hierfür sind die Prozesse des Linux/Unix-Betriebssystems

Leichtgewichtige Prozesse (Kontrollfäden, threads of control, threads)

• Ziel: Bilden einer Programmeinheit, die parallel zu anderen Programmeinheiten arbeiten kann

• Eine Anzahl von Threads teilt sich eine gemeinsame (Prozess-) Umgebung, d.h. Adressraum des umgebenden Prozesses, geöffnete Dateien und andere Betriebsmittel

• Geschützte Speicherbereiche existieren zwar noch für den umschließenden UNIX-Prozess, jedoch nichtmehr für den einzelnen Thread

• Thread-Wechsel ist somit kein Umgebungswechsel, sondern nur ein Kontextwechsel

Mehrfädige ("multi-threaded") Betriebssysteme

• Innerhalb der Linux/Unix-Prozesse können Threads als parallele Kontrollfäden vom Programmierer genutzt werden

• Beispiele:

  • Praktisch alle Workstation-Betriebssysteme: Solaris, HP-UX, IBM-AIX

  • Aber auch die PC-Betriebssysteme: Windows95/98, Windows NT/2000/XP/Vista/7 und alle folgenden Versionen…

  • Und natürlich Linux

• Zu Anfangs definierte jedes Betriebssystem seine eigene Thread- Bibliothek mit untereinander leicht variierender Syntax und Semantik

• Standardisierung POSIX 1003.1c-1995: 1995 wurde vom POSIX- Komitee eine Thread-Schnittstelle geschaffen, die als Pthreads (POSIX-Thread) bezeichnet wird

Prozesse/Threads sind voneinander abhängig („interdependent“), wenn sie in einer bestimmten Reihenfolge ausgeführt werden müssen

Gründe für die Abhängigkeit von Prozessen/Threads

• Kooperation: Prozesse/Threads erfüllen jeweils bestimmte Teilaufgaben im Rahmen der vorgegebenen Gesamtaufgabe

• Produzenten/Konsumenten-System oder Erzeuger/Verbraucher-System

• Auftraggeber/Auftragnehmer-System (client/server)

Konkurrenz: Die Aktivitäten eines Prozesses (oder Threads) drohen die eines anderen zu behindern

• Koordination der Kooperation und Konkurrenz zwischen Prozessen (oder Threads) wird Synchronisation genannt

  • Synchronisation bringt die Aktivitäten verschiedener Prozesse (oder Threads) in eine Reihenfolge

  • Kommunikation: Datenaustausch über Prozess- (oder Thread)grenzen hinweg

• Möglichkeit der Kommunikation mit gemeinsamen Variablen, auf die Prozesse schreibend und lesend zugreifen können

• Reihenfolge der einzelnen Lese- oder Schreib- zugriffe wird dadurch bestimmt, wie schnell es den Prozessoren gelingt, ihre Zugriffsoperationen durchzuführen

  • Prozessoren liefern sich ein Wettrennen (race)

  • Programmsysteme sollen im allgemeinen determinierte Ergebnisse liefern, egal welche Zugriffsfolge durch das Wettrennen entsteht

    • Ausgaben sollen unabhängig von den Umständen des Wettrennens (race conditions) sein

• Synchronisation schränkt das Wettrennen unter den Prozessen ein, um dadurch entstehende Fehler zu vermeiden

Einseitige Synchronisation

• Zwei Aktivitäten A1 und A2 sind voneinander abhängig A1 bildet die Voraussetzung für das richtige Ergebnis von A2 → A1 muss vor A2 ausgeführt werden

Mehrseitige Synchronisation

• Zeitliche Abfolge zwischen zwei Aktivitäten A1 und A2 ist gleichgültig Aufgrund von Schreib-/Schreib- oder Schreib-/Lese-Konflikten besteht jedoch eine Abhängigkeit zwischen den Aktivitäten

  • A1 darf nicht zusammen mit A2 ausgeführt werden

  • Aktivitäten stehen in einem gegenseitigen Ausschluss (mutual exclusion)

• Anweisungen, deren Ausführungen einen gegenseitigen Ausschluss erfordern, heißen kritische Abschnitte (critical sections)

Verklemmung (deadlock)

• Situation, in der Prozesse auf Ereignisse warten, die nicht mehr eintreten können

Aussperrung

• Prozess wird undefinierbar lang verzögert

Voraussetzungen für das Auftreten einer Verklemmung

1) Die umstrittenen Betriebsmittel sind nur exklusiv nutzbar

2) Die umstrittenen Betriebsmittel können nicht entzogen werden

3) Prozesse belegen die schon zugewiesenen Betriebsmittel auch dann, wenn sie auf die Zuweisung weiterer Betriebsmittel warten

4) Zyklische Kette von Prozessen existiert, von denen jeder mindestens ein Betriebsmittel besitzt, das der nächste Prozess der Kette benötigt

Verklemmungsvermeidung durch Regeln

• Man kann versuchen, die Verklemmung zu vermeiden, indem man darauf achtet, dass immer mindestens eine der 4 o.g. Voraussetzungen nicht erfüllt ist

Verklemmungsvermeidung durch Bedarfsanalyse

• Man kann versuchen, die Verklemmung zu vermeiden, indem man die zukünftigen Betriebsmittelanforderungen der Prozesse analysiert und Zustände verbietet, die zu Verklemmungen führen können

Verklemmungserkennung

• Man kann versuchen, eine Verklemmung festzustellen und sie – sollte sie eingetreten sein – dann zu beseitigen

• Um den Zugang zu kritischen Abschnitten / critical sections zu regeln, versieht man diese mit einem Schloss / Lock, das von Prozessen aufgesperrt und verriegelt werden kann

• Eine Schlossvariable (lock variable) ist eine abstrakte Datenstruktur, auf die alle Prozesse zugreifen müssen, die kritische Abschnitte betreten wollen

Zugehörige Operationen:

• lock (verschließen): Ein Prozess wartet so lange, bis das zugehörige Schloss offen ist, dann betritt er den kritischen Abschnitt und verriegelt das Schloss (quasi von innen), so dass ihm kein anderer Prozess folgen kann

• unlock (aufschließen): Hat der Prozess den kritischen Abschnitt beendet, sperrt der Prozess das Schloss wieder auf

• Eine unlock-Operation muss von demselben Prozess ausgeführt werden, der das Schloss vorher geschlossen hat

lock-Operation besteht aus zwei unterschiedlichen Operationen: Prüfen und Setzen einer Schlossvariablen

• lock stellt also selbst wiederum einen kritischen Abschnitt dar

Spezielle Maschineninstruktionen nötig, die nicht unterbrechbar sind:

• test_and_set(a,b) liest den Wert der Booleschen Variablen a, kopiert ihn nach b und setzt a auf true in einer unteilbaren Aktivität

• swap tauscht den Inhalt eines Registers und eines Speicherplatzes, ohne dass er während seiner Ausführung unterbrochen werden kann

  • Falls ein kritischer Bereich durch einen anderen Prozess oder Thread belegt ist, wird der swap-Befehl solange wiederholt, bis der kritische Bereich freigegeben wird → aktives Warten (spin lock) verbraucht Systemressourcen

• Bei mehreren wartenden Prozessen/Threads: zufällige Auswahl eines Prozesses/Threads bei Freigabe des kritischen Bereichs

• Suspend lock: Betriebssystem verwaltet wartende Prozesse/Threads und aktiviert erst bei Freigabe des kritischen Bereichs einen der wartenden Prozesse/Threads

Ziel: Synchronisation paralleler Prozesse

• Ein Semaphor S ist ein abstrakter Datentyp, der aus einer nichtnegativen Integer-Variablen (dem Semaphorzähler) und zwei Operationen besteht, die traditionell mit P und V bezeichnet werden

  • Niederländisch: „passeeren“, „vrijgeven“

Nachdem bei der Initialisierung des Semaphors S dem Semaphor- zähler einmal ein Wert zugewiesen worden ist, kann er nur noch mit den zwei primitiven Operationen P(S) und V(S) manipuliert werden

Namensherkunft:

• Telegraphendienst zu Land und See, um Nachrichten über große Distanzen zu übermitteln Formsignale mechanischer Eisenbahnsignale

• Lösen Synchronisationsprobleme auf einer sehr niedrigen Ebene

• Nachteil

• Es kann zu einem Zusammenbruch des gesamten Systems kommen, falls nur ein einzige Semaphoroperation falsch programmiert ist (z.B. das Freigeben wurde vergessen)

• Lässt sich Verhindern, wenn Synchronisationswerkzeuge höherer Ebene, z.B. Monitore, verwendet werden

• Was ist der Unterschied zwischen einem binären Semaphor und einer Schlossvariablen?

• Neben der Syntax im Wesentlichen, dass ein unlock nur von dem Prozess/Thread durchgeführt werden kann, der die lock Operation ausgeführt hat, während diese Beschränkung bei der V-Operationen von Semaphoren nicht gilt!

• Der Eintritt eines Prozesses in einen Programmbereich (Anweisungsfolge s1,...,sn) wird davon abhängig gemacht, dass kein weiterer Prozess bereits eingetreten ist

  • Zu jedem Zeitpunkt befindet sich höchstens ein Prozess im kritischen Bereich

• Der Eintritt kann auch noch von der Erfüllung einer weiteren Bedingung b abhängig gemacht werden

  • Ist eine Bedingung b vorhanden, so wird diese zuerst berechnet

  • Wenn b „wahr“ ist, dann kann der Prozess in den Wettbewerb um den Eintritt in den kritischen Bereich einsteigen

  • Ist b „falsch“, so muss sich der Prozess zu den wartenden Prozessen einreihen

• Wenn mehrere Prozesse versuchen, gleichzeitig einzutreten, so kann nur einer erfolgreich eintreten und die anderen müssen warten

• Sobald ein Prozess den kritischen Bereich freigibt, werden alle wartenden Prozesse wieder aufgenommen

  • Die Prozesse mit einer Eintrittsbedingung müssen diese neu berechnen

• Prozesse mit zu „wahr“ ausgewerteten Bedingungen sowie Prozesse ohne Bedingung bewerben sich dann um den Eintritt in den kritischen Bereich

• Implementierung sollte sicherstellen, dass dieser Wettbewerb fair verläuft

• Ein Monitor ist eine abstrakte Datenstruktur mit impliziten Synchronisationseigenschaften

• Den Benutzern eines Monitors bleibt nicht nur die Implementierung der Zugriffsfunktionen auf gemeinsame Daten, sondern auch die Realisierung des gegenseitigen Ausschlusses für diese Funktion verborgen

• Alle Zugriffsoperationen eines Monitors werden im gegenseitigen Ausschluss durchgeführt

• Die im Monitor vereinbarten Variablen können aufgrund dieses gegenseitigen Ausschlusses nie gleichzeitig benutzt werden – sie stellen exklusive Betriebsmittel für Prozesse dar

Monitor besteht aus

• Anzahl von Monitorvariablen

• Anzahl von Prozeduren oder Funktionen

  • Monitorprozeduren haben nur Zugriff zu den monitorgebundenen Variablen und die Aktualparameter (Argument eines Funktions-/Prozeduraufrufes)

• Auf monitorgebundene Variablen kann von außen nicht zugegriffen werden

Monitorkörper

• Folge von Befehlen, die direkt nach dem Start des Programms durchlaufen werden, und die dazu benutzt werden, die Monitorvariablen zu initialisieren

• Danach besteht der Monitor nur noch als Paket/Modul von Daten und Prozeduren – vgl. einer Java-Klasse

Ein Prozess kann einen Monitor nur durch Aufruf einer Monitorprozedur betreten Dabei geschieht der Eintritt in einen Monitor unter Ausschluss aller anderen Prozesse

• Falls ein weiterer Prozess den Monitor betreten will, wird er suspendiert und wartet außen auf die Freigabe des Monitors

Vorteil Monitor gegenüber Semaphor

• Ein einmal korrekt programmierter Monitor kann durch weitere hinzugenommene Anwenderprozesse nicht gestört werden (Semaphor V-Operation bei einem neuen Prozess falsch → Stillstand)

Vorteil Monitor gegenüber einem bedingtem, kritischen Abschnitt

• Ein Monitor kann nicht nur eine Befehlsfolge beinhalten, sondern ganze Prozeduren inkl. Variablen und Parametern

• Eine Barriere (barrier) ist ein Synchronisationspunkt für mehrere Prozesse

• Bei der Barrieren-Synchronisation warten alle Prozesse, welche die Barrieren-Synchronisation aufrufen, so lange, bis auch der letzte einer Gruppe von Prozessen an der Barriere angekommen ist (UND-Barriere)

• Eine Barriere wird als Barrieren-Variable angelegt und muss vor dem ersten Benutzen initialisiert werden

  • Eine init-barrier-Anweisung weist der Barrieren-Variable die Zahl der Prozesse zu, auf die gewartet werden soll

• Eine wait-barrier-Anweisung muss dann von jedem dieser Prozesse ausgeführt werden

  • Dabei wird die Prozessanzahl aus der Initialisierung dekrementiert und der Prozess suspendiert, sofern die Prozessanzahl noch größer als Null ist

• Wenn der letzte der Prozesse an der Barriere angekommen ist (Prozessanzahl gleich Null), so werden alle wartenden Prozesse (und natürlich der zuletzt angekommene) wieder aufgenommen und die Barriere wird wieder auf den Initialwert zurückgesetzt

• In der Cray T3E wird neben der üblichen Barriere auch eine ODER-Barriere beschrieben, die als Eureka-Mechanismus bezeichnet wird

• Häufig kann die Verbindungsstruktur eines Parallelrechners ausgenutzt werden, um eine sehr schnelle Implementierung der Barrieren-Operation zu gewährleisten

• In allen nachrichtengekoppelten Programmierschnittstellen/- modellen bilden die sogenannten globalen Operationen Barrieren

  • Z.B. ein globales Aufsummieren, eine globale Multiplikation, etc.

  • Globale Synchronisation als die einfachste aller globalen Operationen synchronisiert alle Prozesse einer Prozessgruppe, z.B. MPI_barrier