Multicore: Parallele Programmierung [1 ed.] 9783540731139, 354073113X, 9783540731146, 3540731148 [PDF]

Zitiervorschau

Informatik im Fokus

Herausgeber: Prof. Dr. O. Günther Prof. Dr. W. Karl Prof. Dr. R. Lienhart Prof. Dr. K. Zeppenfeld

Informatik im Fokus

Rauber, T.; Rünger, G. Multicore: Parallele Programmierung. 2008 El Moussaoui, H.; Zeppenfeld, K. AJAX. 2008 Behrendt, J.; Zeppenfeld, K. Web 2.0. 2008 Bode, A.; Karl, W. Multicore-Architekturen. 2008

Thomas Rauber · Gudula Rünger

Multicore: Parallele Programmierung

123

Prof. Dr. Thomas Rauber Universität Bayreuth LS Angewandte Informatik II Universitätsstr. 30 95447 Bayreuth [email protected]

Prof. Dr. Gudula Rünger TU Chemnitz Fakultät für Informatik Straße der Nationen 62 09107 Chemnitz [email protected]

Herausgeber: Prof. Dr. O. Günther Humboldt Universität zu Berlin

Prof. Dr. R. Lienhart Universität Augsburg

Prof. Dr. W. Karl Universität Karlsruhe (TH)

Prof. Dr. K. Zeppenfeld Fachhochschule Dortmund

ISBN 978-3-540-73113-9

e-ISBN 978-3-540-73114-6

DOI 10.1007/978-3-540-73114-6 ISSN 1865-4452 Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar. © 2008 Springer-Verlag Berlin Heidelberg Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte, insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. September 1965 in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Text und Abbildungen wurden mit größter Sorgfalt erarbeitet. Verlag und Autor können jedoch für eventuell verbliebene fehlerhafte Angaben und deren Folgen weder eine juristische Verantwortung noch irgendeine Haftung übernehmen. Einbandgestaltung: KünkelLopka Werbeagentur, Heidelberg Gedruckt auf säurefreiem Papier 987654321 springer.com

Vorwort

Nach vielen Jahren stetigen technologischen Fortschritts in der Mikroprozessorentwicklung stellt die Multicore-Technologie die neueste Entwickungsstufe dar. F¨ uhrende Hardwarehersteller wie Intel, AMD, Sun oder IBM liefern seit 2005 Mikroprozessoren mit mehreren unabh¨ angigen Prozessorkernen auf einem einzelnen Prozessorchip. Im Jahr 2007 verwendet ein typischer Desktop-PC je nach Ausstattung einen Dualcore- oder Quadcore-Prozessor mit zwei bzw. vier Prozessorkernen. Die Ank¨ undigungen der Prozessorhersteller zeigen, dass dies erst der Anfang einer l¨anger andauernden Entwicklung ist. Eine Studie von Intel prognostiziert, dass im Jahr 2015 ein typischer Prozessorchip aus Dutzenden bis Hunderten von Prozessorkernen besteht, die zum Teil spezialisierte Aufgaben wie Verschl¨ usselung, Grafikdarstellung oder Netzwerkmanagement wahrnehmen. Ein Großteil der Prozessorkerne steht aber f¨ ur Anwendungsprogramme zur Verf¨ ugung und kann z.B. f¨ ur B¨ uro- oder Unterhaltungssoftware genutzt werden. Die von der Hardwareindustrie vorgegebene Entwicklung hin zu Multicore-Prozessoren bietet f¨ ur die Software-

VI

Vorwort

entwickler also neue M¨ oglichkeiten, die in der Bereitstellung zus¨ atzlicher Funktionalit¨ aten der angebotenen Software liegen, die parallel zu den bisherigen Funktionalit¨aten ausgef¨ uhrt werden k¨ onnen, ohne dass dies beim Nutzer zu Wartezeiten f¨ uhrt. Diese Entwicklung stellt aber auch einen Paradigmenwechsel in der Softwareentwicklung dar, weg von der herk¨ ommlichen sequentiellen Programmierung hin zur parallelen oder Multithreading-Programmierung. Beide Programmierformen sind nicht neu. Der Paradigmenwechsel besteht eher darin, dass diese Programmiertechniken bisher nur in speziellen Bereichen eingesetzt wurden, nun aber durch die Einf¨ uhrung von Multicore-Prozessoren in alle Bereiche der Softwareentwicklung getragen werden und so f¨ ur viele Softwareentwickler eine neue Herausforderung entsteht. Das Ziel dieses Buches ist es, dem Leser einen ersten Einblick in die f¨ ur Multicore-Prozessoren geeigneten parallelen Programmiertechniken und -systeme zu geben. Programmierumgebungen wie Pthreads, Java-Threads und OpenMP werden vorgestellt. Die Darstellung geht dabei davon aus, dass der Leser mit Standardtechniken der Programmierung vertraut ist. Das Buch enth¨ alt zahlreiche Hinweise auf weiterf¨ uhrende Literatur sowie neuere Entwicklungen wie etwa neue Programmiersprachen. F¨ ur Hilfe bei der Erstellung des Buches und Korrekturen danken wir J¨org D¨ ummler, Monika Glaser, Marco H¨ obbel, Raphael Kunis und Michael Schwind. Dem Springer-Verlag danken wir f¨ ur die gute Zusammenarbeit.

Bayreuth, Chemnitz, August 2007

Thomas Rauber Gudula R¨ unger

Inhaltsverzeichnis

1

Kurz¨ uberblick Multicore-Prozessoren . . . . . . 1 1.1 Entwicklung der Mikroprozessoren . . . . . . . . . 1 1.2 Parallelit¨ at auf Prozessorebene . . . . . . . . . . . . 4 1.3 Architektur von Multicore-Prozessoren . . . . . 8 1.4 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2

Konzepte paralleler Programmierung . . . . . . 2.1 Entwurf paralleler Programme . . . . . . . . . . . . 2.2 Klassifizierung paralleler Architekturen . . . . . 2.3 Parallele Programmiermodelle . . . . . . . . . . . . . 2.4 Parallele Leistungsmaße . . . . . . . . . . . . . . . . . .

21 22 27 29 35

3

Thread-Programmierung . . . . . . . . . . . . . . . . . . 3.1 Threads und Prozesse . . . . . . . . . . . . . . . . . . . . 3.2 Synchronisations-Mechanismen . . . . . . . . . . . . 3.3 Effiziente und korrekte Thread-Programme . 3.4 Parallele Programmiermuster . . . . . . . . . . . . . 3.5 Parallele Programmierumgebungen . . . . . . . .

39 39 46 51 54 61

VIII

Inhaltsverzeichnis

4

Programmierung mit Pthreads . . . . . . . . . . . . 4.1 Threaderzeugung und -verwaltung . . . . . . . . . 4.2 Koordination von Threads . . . . . . . . . . . . . . . . 4.3 Bedingungsvariablen . . . . . . . . . . . . . . . . . . . . . 4.4 Erweiterter Sperrmechanismus . . . . . . . . . . . . 4.5 Implementierung eines Taskpools . . . . . . . . . .

63 63 66 70 75 78

5

Java-Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.1 Erzeugung von Threads in Java . . . . . . . . . . . 85 5.2 Synchronisation von Java-Threads . . . . . . . . . 91 5.3 Signalmechanismus in Java . . . . . . . . . . . . . . . 101 5.4 Erweiterte Synchronisationsmuster . . . . . . . . . 109 5.5 Thread-Scheduling in Java . . . . . . . . . . . . . . . . 113 5.6 Paket java.util.concurrent . . . . . . . . . . . . 115

6

OpenMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.1 Programmiermodell . . . . . . . . . . . . . . . . . . . . . . 125 6.2 Spezifikation der Parallelit¨ at . . . . . . . . . . . . . . 127 6.3 Koordination von Threads . . . . . . . . . . . . . . . . 139

7

Weitere Ans¨ atze . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 7.1 Sprachans¨ atze . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 7.2 Transaktionsspeicher . . . . . . . . . . . . . . . . . . . . . 150

Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

1 Kurzu ¨ berblick Multicore-Prozessoren

Die Entwicklung der Mikroprozessoren hat in den letzten Jahrzehnten durch verschiedene technologische Innovationen immer leistungsst¨ arkere Prozessoren hervorgebracht. Multicore-Prozessoren stellen einen weiteren Meilenstein in der Entwicklung dar.

1.1 Entwicklung der Mikroprozessoren Prozessorchips sind intern aus Transistoren aufgebaut, deren Anzahl ein ungef¨ ahres Maß f¨ ur die Komplexit¨at und Leistungsf¨ ahigkeit des Prozessors ist. Das auf empirischen Beobachtungen beruhende Gesetz von Moore besagt, dass die Anzahl der Transistoren eines Prozessorchips sich alle 18 bis 24 Monate verdoppelt. Diese Beobachtung wurde 1965 von Gordon Moore zum ersten Mal gemacht und gilt nun seit u ¨ ber 40 Jahren. Ein typischer Prozessorchip aus dem Jahr 2007 besteht aus ca. 200-400 Millionen Transistoren: beispielsweise besteht ein Intel Core 2 Duo Prozessor

2

1 Kurz¨ uberblick Multicore-Prozessoren

aus ca. 291 Millionen Transistoren, ein IBM Cell-Prozessor aus ca. 250 Millionen Transistoren. Die Erh¨ ohung der Transistoranzahl ging in der Vergangenheit mit einer Erh¨ ohung der Taktrate einher. Dies steigerte die Verarbeitungsgeschwindigkeit der Prozessoren und die Taktrate eines Prozessors wurde oftmals als alleiniges Merkmal f¨ ur dessen Leistungsf¨ ahigkeit wahrgenommen. Gemeinsam f¨ uhrte die Steigerung der Taktrate und der Transistoranzahl zu einer durchschnittlichen j¨ahrlichen Leistungssteigerung der Prozessoren von ca. 55% (bei Integer-Operationen) bzw. 75% (bei Floating-PointOperationen), was durch entsprechende Benchmark-Programme gemessen wurde, siehe [32] und www.spec.org f¨ ur eine Beschreibung der oft verwendeten SPEC-Benchmarks. Eine Erh¨ ohung der Taktrate im bisherigen Umfang ist jedoch f¨ ur die Zukunft nicht zu erwarten. Dies ist darin begr¨ undet, dass mit einer Erh¨ ohung der Taktrate auch die Leistungsaufnahme, also der Energieverbrauch des Prozessors, ansteigt, wobei ein Großteil des verbrauchten Stroms in W¨ arme umgewandelt wird und u ufter abgef¨ uhrt ¨ ber L¨ werden muss. Das Gesetz von Moore scheint aber bis auf weiteres seine G¨ ultigkeit zu behalten. Die steigende Anzahl verf¨ ugbarer Transistoren wurde in der Vergangenheit f¨ ur eine Vielzahl weiterer architektonischer Verbesserungen genutzt, die die Leistungsf¨ahigkeit der Prozessoren erheblich gesteigert hat. Dazu geh¨oren u.a. • • •

die Erweiterung der internen Wortbreite auf 64 Bits, die Verwendung interner Pipelineverarbeitung f¨ ur die ressourcenoptimierte Ausf¨ uhrung aufeinanderfolgender Maschinenbefehle, die Verwendung mehrerer Funktionseinheiten, mit denen voneinander unabh¨ angige Maschinenbefehle parallel zueinander abgearbeitet werden k¨ onnen und

1.1 Entwicklung der Mikroprozessoren

•

3

die Vergr¨ oßerung der prozessorlokalen Cachespeicher.

Wesentliche Aspekte der Leistungssteigerung sind also die Erh¨ ohung der Taktrate und der interne Einsatz paralleler Abarbeitung von Instruktionen, z.B. durch das Duplizieren von Funktionseinheiten. Die Grenzen beider Entwicklungen sind jedoch abzusehen: Ein weiteres Duplizieren von Funktionseinheiten und Pipelinestufen ist zwar m¨oglich, bringt aber wegen vorhandener Abh¨ angigkeiten zwischen den Instruktionen kaum eine weitere Leistungssteigerung. Gegen eine weitere Erh¨ ohung der prozessoreigenen Taktrate sprechen mehrere Gr¨ unde [36]: •

•

•

Ein Problem liegt darin, dass die Speicherzugriffsgeschwindigkeit nicht im gleichen Umfang wie die Prozessorgeschwindigkeit zunimmt, was zu einer Erh¨ohung der Zyklenanzahl pro Speicherzugriff f¨ uhrt. So brauchte z.B. um 1990 ein Intel i486 f¨ ur einen Zugriff auf den Hauptspeicher zwischen 6 und 8 Maschinenzyklen, w¨ ahrend 2006 ein Intel Pentium Prozessor u ¨ ber 220 Zyklen ben¨ otigt. Die Speicherzugriffszeiten stellen daher einen kritischen limitierenden Faktor f¨ ur eine weitere Leistungssteigerung dar. Zum Zweiten wird die Erh¨ ohung der Transistoranzahl durch eine erh¨ ohte Packungsdichte erreicht, mit der aber auch eine gesteigerte W¨ armeentwicklung pro Fl¨acheneinheit verbunden ist. Diese wird zunehmend zum Problem, da die notwendige K¨ uhlung entsprechend aufwendiger wird. Zum Dritten w¨ achst mit der Anzahl der Transistoren auch die prozessorinterne Leitungsl¨ ange f¨ ur den Signaltransport, so dass die Signallaufzeit eine wichtige Rolle spielt. Dies sieht man an folgender Berechnung: Ein mit 3GHz getakteter Prozessor hat eine Zykluszeit von 0.33 ns = 0.33 ·10−9 sec. In dieser Zeit kann ein Signal eine

4

1 Kurz¨ uberblick Multicore-Prozessoren

Entfernung von 0.33 ·10−9 s·0.3 · 109m/s ≈ 0.1m zur¨ ucklegen, wenn wir die Lichtgeschwindigkeit im Vakuum als ¨ Signalgeschwindigkeit ansetzen. Je nach Ubergangsmedium ist die Signalgeschwindigkeit sogar deutlich niedriger. Damit k¨ onnen die Signale in einem Takt nur eine relativ geringe Entfernung zur¨ ucklegen, so dass der Layout-Entwurf der Prozessorchips entsprechend gestaltet werden muss. Um eine weitere Leistungssteigerung der Prozessoren im bisherigen Umfang zu erreichen, setzen die Prozessorhersteller auf eine explizite Parallelverarbeitung innerhalb eines Prozessors, indem mehrere logische Prozessoren von einem physikalischen Prozessor simuliert werden oder mehrere vollst¨ andige, voneinander nahezu unabh¨ angige Prozessorkerne auf einen Prozessorchip platziert werden. Der Einsatz expliziter Parallelverarbeitung innerhalb eines Prozessors hat weitreichende Konsequenzen f¨ ur die Programmierung: soll ein Programm von der verf¨ ugbaren Leistung des Multicore-Prozessors profitieren, so muss es die verf¨ ugbaren Prozessorkerne entsprechend steuern und effizient ausnutzen. Dazu werden Techniken der parallelen Programmierung eingesetzt. Da die Prozessorkerne eines Prozessorchips ein gemeinsames Speichersystem nutzen, sind Programmierans¨ atze f¨ ur gemeinsamen Adressraum geeignet.

1.2 Parallelit¨ at auf Prozessorebene Explizite Parallelit¨ at auf Prozessorebene wird durch eine entsprechende Architekturorganisation des Prozessorchips erreicht. Eine M¨ oglichkeit ist die oben erw¨ ahnte Platzierung mehrerer Prozessorkerne mit jeweils unabh¨ angigen Ausf¨ uhrungseinheiten auf einem Prozessorchip, was als Multicore-

1.2 Parallelit¨ at auf Prozessorebene

5

Prozessor bezeichnet wird. Ein anderer Ansatz besteht darin, mehrere Kontrollfl¨ usse dadurch gleichzeitig auf einem Prozessor oder Prozessorkern auszuf¨ uhren, dass der Prozessor je nach Bedarf per Hardware zwischen den Kontrollfl¨ ussen umschaltet. Dies wird als simultanes Multithreading (SMT) oder Hyperthreading (HT) bezeichnet [43]. Bei dieser Art der Parallelit¨ at werden die Kontrollfl¨ usse oft als Threads bezeichnet. Dieser Begriff und die Unterschiede zu Prozessen werden in den folgenden Abschnitten n¨ aher erl¨ autert; zun¨ achst reicht es aus, einen Thread als Kontrollfluss anzusehen, der parallel zu anderen Threads desselben Programms ausgef¨ uhrt werden kann. Simultanes Multithreading (SMT) Simultanes Multithreading basiert auf dem Duplizieren des Prozessorbereiches zur Ablage des Prozessorzustandes auf der Chipfl¨ ache des Prozessors. Zum Prozessorzustand geh¨oren die Benutzer- und Kontrollregister sowie der InterruptController mit seinen zugeh¨ origen Registern. Damit verh¨alt sich der physikalische Prozessor aus der Sicht des Betriebssystems und des Benutzerprogramms wie zwei logische Prozessoren, denen Prozesse oder Threads zur Ausf¨ uhrung zugeordnet werden k¨ onnen. Diese k¨onnen von einem oder mehreren Anwendungsprogrammen stammen. Jeder logische Prozessor legt seinen Prozessorzustand in einem separaten Prozessorbereich ab, so dass beim Wechsel zu einem anderen Thread kein aufwendiges Zwischenspeichern des Prozessorzustandes im Speichersystem erforderlich ist. Die logischen Prozessoren teilen sich fast alle Ressourcen des physikalischen Prozessors wie Caches, Funktions- und Kontrolleinheiten oder Bussystem. Die Realisierung der SMT-Technologie erfordert daher nur eine ge-

6

1 Kurz¨ uberblick Multicore-Prozessoren

ringf¨ ugige Vergr¨oßerung der Chipfl¨ ache. F¨ ur zwei logische Prozessoren w¨ achst z.B. f¨ ur einen Intel Xeon Prozessor die erforderliche Chipfl¨ ache um weniger als 5% [44, 67]. Die gemeinsamen Ressourcen des Prozessorchips werden den logischen Prozessoren reihum zugeteilt, so dass die logischen Prozessoren simultan zur Verf¨ ugung stehen. Treten bei einem logischen Prozessor Wartezeiten auf, k¨onnen die Ausf¨ uhrungs-Ressourcen dem anderen logischen Prozessor zugeordnet werden, so dass aus der Sicht des physikalischen Prozessors eine verbesserte Nutzung der Ressourcen gew¨ ahrleistet ist. Untersuchungen zeigen, dass die verbesserte Nutzung der Ressourcen durch zwei logische Prozessoren je nach Anwendungsprogramm Laufzeitverbesserungen zwischen 15% und 30% bewirken kann [44]. Da alle Ressourcen des Chips von den logischen Prozessoren geteilt werden, ist beim Einsatz von wesentlich mehr als zwei logischen Prozessoren f¨ ur die meisten Einsatzgebiete keine weitere signifikante Laufzeitverbesserung zu erwarten. Der Einsatz simultanen Multithreadings wird daher voraussichtlich auf wenige logische Prozessoren beschr¨ ankt bleiben. Zum Erreichen einer Leistungsverbesserung durch den Einsatz der SMT-Technologie ist es erforderlich, dass das Betriebssystem in der Lage ist, die logischen Prozessoren anzusteuern. Aus Sicht eines Anwendungsprogramms ist es erforderlich, dass f¨ ur jeden logischen Prozessor ein separater Thread zur Ausf¨ uhrung bereitsteht, d.h. f¨ ur die Implementierung des Programms m¨ ussen Techniken der parallelen Programmierung eingesetzt werden. Multicore-Prozessoren Neue Prozessorarchitekturen mit mehreren Prozessorkernen auf einem Prozessorchip werden schon seit vielen Jah-

1.2 Parallelit¨ at auf Prozessorebene

7

ren als die vielversprechendste Technik zur weiteren Leistungssteigerung angesehen. Die Idee besteht darin, anstatt eines Prozessorchips mit einer sehr komplexen internen Organisation mehrere Prozessorkerne mit einfacherer Organisation auf dem Prozessorchip zu integrieren. Dies hat den zus¨ atzlichen Vorteil, dass der Stromverbrauch des Prozessorchips dadurch reduziert werden kann, dass vor¨ ubergehend ungenutzte Prozessorkerne abgeschaltet werden [27]. Bei Multicore-Prozessoren werden mehrere Prozessorkerne auf einem Prozessorchip integriert. Jeder Prozessorkern stellt f¨ ur das Betriebssystem einen separaten logischen Prozessor mit separaten Ausf¨ uhrungsressourcen dar, die getrennt angesteuert werden m¨ ussen. Das Betriebssystem kann damit verschiedene Anwendungsprogramme parallel zueinander zur Ausf¨ uhrung bringen. So k¨ onnen z.B. mehrere Hintergrundanwendungen wie Viruserkennung, Verschl¨ usselung und Kompression parallel zu Anwendungsprogrammen des Nutzers ausgef¨ uhrt werden [58]. Es ist aber mit Techniken der parallelen Programmierung auch m¨ oglich, ein rechenzeitintensives Anwendungsprogramm (etwa aus dem Bereich der Computerspiele, der Bildverarbeitung oder naturwissenschaftlicher Simulationsprogramme) auf mehreren Prozessorkernen parallel abzuarbeiten, so dass die Berechnungszeit im Vergleich zu einer Ausf¨ uhrung auf einem Prozessorkern reduziert werden kann. Damit k¨ onnen auch Standardprogramme wie Textverarbeitungsprogramme oder Computerspiele zus¨atzliche, im Hintergrund ablaufende Funktionalit¨ aten zur Verf¨ ugung stellen, die parallel zu den Haupt-Funktionalit¨aten auf einem separaten Prozessorkern durchgef¨ uhrt werden und somit f¨ ur den Nutzer nicht zu wahrnehmbaren Verz¨ogerungen f¨ uhren. F¨ ur die Koordination der innerhalb einer Anwendung ablaufenden unterschiedlichen Funktionalit¨aten

8

1 Kurz¨ uberblick Multicore-Prozessoren

m¨ ussen Techniken der parallelen Programmierung eingesetzt werden.

1.3 Architektur von Multicore-Prozessoren F¨ ur die Realisierung von Multicore-Prozessoren gibt es verschiedene Implementierungsvarianten, die sich in der Anzahl der Prozessorkerne, der Gr¨ oße und Anordnung der Caches, den Zugriffm¨ oglichkeiten der Prozessorkerne auf die Caches und dem Einsatz von heterogenen Komponenten unterscheiden [37]. Dabei werden zur Zeit drei unterschiedliche Architekturmodelle eingesetzt, von denen auch Mischformen auftreten k¨ onnen. Hierarchisches Design

Cache/Speicher

Cache Kern

Kern

Cache Kern

Kern

hierarchisches Design

Abbildung 1.1. Hierarchisches Design.

Bei einem hierarchischen Design teilen sich mehrere Prozessorkerne mehrere Caches, die in einer baumartigen Konfiguration angeordnet sind, wobei die Gr¨ oße der Caches von den Bl¨ attern zur Wurzel steigt. Die Wurzel repr¨ asentiert die Verbindung zum Hauptspeicher. So kann z.B. jeder Prozessorkern einen separaten L1Cache haben, sich aber mit anderen Prozessorkernen einen L2-Cache teilen. Alle Prozessorkerne k¨ onnen auf den gemeinsamen externen Hauptspeicher zugreifen, was eine

1.3 Architektur von Multicore-Prozessoren

9

dreistufige Hierarchie ergibt. Dieses Konzept kann auf mehrere Stufen erweitert werden und ist in Abbildung 1.1 f¨ ur drei Stufen veranschaulicht. Zus¨ atzliche Untersysteme k¨ onnen die Caches einer Stufe miteinander verbinden. Ein hierarchisches Design wird typischerweise f¨ ur ServerKonfigurationen verwendet. Ein Beispiel f¨ ur ein hierarchisches Design ist der IBM Power5 Prozessor, der zwei 64-Bit superskalare Prozessorkerne enth¨ alt, von denen jeder zwei logische Prozessoren durch Einsatz von SMT simuliert. Jeder Prozessorkern hat einen separaten L1-Cache (f¨ ur Daten und Programme getrennt) und teilt sich mit dem anderen Prozessorkern einen L2-Cache (1.8 MB) sowie eine Schnittstelle zu einem externen 36 MB L3-Cache. Andere Prozessoren mit hierarchischem Design sind die Intel Core 2 Prozessoren und die Sun UltraSPARC T1 (Niagara) Prozessoren. Pipeline-Design

Abbildung 1.2. PipelineDesign.

Bei einem Pipeline-Design werden die Daten durch mehrere Prozessorkerne schrittweise weiterverarbeitet, bis sie vom letzten Prozessorkern im Speichersystem abgelegt werden, vgl. Abbildung 1.2. Hochspezialisierte Netzwerk-Prozessoren und Grafikchips arbeiten oft nach diesem Prinzip. Ein Beispiel sind die X10 und X11 Prozessoren von Xelerator zur Verarbeitung von Netzwerkpaketen in HochleistungsRoutern. Der Xelerator X10q,

10

1 Kurz¨ uberblick Multicore-Prozessoren

eine Variante des X10, enth¨ alt z.B. 200 separate Prozessorkerne, die in einer logischen linearen Pipeline miteinander verbunden sind. Die Pakete werden dem Prozessor u uhrt und dann ¨ ber mehrere Netzwerkschnittstellen zugef¨ durch die Prozessorkerne schrittweise verarbeitet, wobei jeder Prozessorkern einen Schritt ausf¨ uhrt. Die X11 Netzwerkprozessoren haben bis zu 800 Pipeline-Prozessorkerne. Netzwerkbasiertes Design Bei einem netzwerkbasierten Design sind die Prozessorkerne und ihre lokalen Caches oder Speicher u ¨ ber ein Verbindungsnetzwerk mit den anderen Prozessorkernen des Chips verbunden, so dass der gesamte Datentransfer zwischen den Prozessorkernen u ¨ber das Verbindungsnetzwerk l¨auft, vgl. Abbildung 1.3. Der Einsatz eines prozessorinternen Netzwerkes ist insbesondere Abbildung 1.3. Netzwerk- dann sinnvoll, wenn eine Vielbasiertes Design. zahl von Prozessorkernen verwendet werden soll. Ein netzwerkorientiertes Design wird z.B. f¨ ur den Intel TeraflopProzessor verwendet, der im Rahmen der Intel Tera-ScaleInitiative entwickelt wurde, vgl. unten, und in dem 80 Prozessorkerne eingesetzt werden. Weitere Entwicklungen Das Potential der Multicore-Prozessoren wurde von vielen Hardwareherstellern wie Intel und AMD erkannt und

1.3 Architektur von Multicore-Prozessoren

11

seit 2005 bieten viele Hardwarehersteller Prozessoren mit zwei oder mehr Kernen an. Ab Ende 2006 liefert Intel Quadcore-Prozessoren und ab 2008 wird mit der Auslieferung von Octcore-Prozessoren gerechnet. IBM bietet mit der Cell-Architektur einen Prozessor mit acht spezialisierten Prozessorkernen, vgl. Abschnitt 1.4. Der seit Dezember 2005 ausgelieferte UltraSPARC T1 Niagara Prozessor von Sun hat bis zu acht Prozessorkerne, von denen jeder durch den Einsatz von simultanem Multithreading, das von Sun als CoolThreads-Technologie bezeichnet wird, vier Threads simultan verarbeiten kann. Damit kann ein UltraSPARC T1 bis zu 32 Threads simultan ausf¨ uhren. Das f¨ ur 2008 angek¨ undigte Nachfolgemodell des Niagara-Prozessors (ROCK) soll bis zu 16 Prozessorkerne enthalten. Intel Tera-Scale-Initiative Intel untersucht im Rahmen des Tera-scale Computing Programs die Herausforderungen bei der Herstellung und Programmierung von Prozessoren mit Dutzenden von Prozessorkernen [27]. Diese Initiative beinhaltet auch die Entwicklung eines Teraflop-Prozessors, der 80 Prozessorkerne enth¨ alt, die als 8×10-Gitter organisiert sind. Jeder Prozessorkern kann Floating-Point-Operationen verarbeiten und enth¨ alt neben einem lokalen Cachespeicher auch einen Router zur Realisierung des Datentransfers zwischen den Prozessorkernen und dem Hauptspeicher. Zus¨ atzlich kann ein solcher Prozessor spezialisierte Prozessorkerne f¨ ur die Verarbeitung von Videodaten, graphischen Berechnungen und zur Verschl¨ usselung von Daten enthalten. Je nach Einsatzgebiet kann die Anzahl der spezialisierten Prozessorkerne variiert werden. Ein wesentlicher Bestandteil eines Prozessors mit einer Vielzahl von Prozessorkernen ist ein effizientes Verbin-

12

1 Kurz¨ uberblick Multicore-Prozessoren

dungsnetzwerk auf dem Prozessorchip, das an eine variable Anzahl von Prozessorkernen angepasst werden kann, den Ausfall einzelner Prozessorkerne toleriert und bei Bedarf das Abschalten einzelner Prozessorkerne erlaubt, falls diese f¨ ur die aktuelle Anwendung nicht ben¨ otigt werden. Ein solches Abschalten ist insbesondere zur Reduktion des Stromverbrauchs sinnvoll. F¨ ur eine effiziente Nutzung der Prozessorkerne ist entscheidend, dass die zu verarbeitenden Daten schnell zu den Prozessorkernen transportiert werden k¨ onnen, so dass diese nicht auf die Bereitstellung der Daten warten m¨ ussen. Dazu sind ein leistungsf¨ ahiges Speichersystem und I/O-System erforderlich. Das Speichersystem setzt private L1-Caches ein, auf die nur von jeweils einem Prozessorkern zugegriffen werden kann, sowie gemeinsame, evtl. aus mehreren Stufen bestehende L2-Caches ein, die Daten verschiedener Prozessorkerne enthalten. F¨ ur einen Prozessorchip mit Dutzenden von Prozessorkernen muss voraussichtlich eine weitere Stufe im Speichersystem eingesetzt werden [27]. Das I/O-System muss in der Lage sein, Hunderte von Gigabytes pro Sekunde zum Prozessorchip zu transportieren. Hier arbeitet z.B. Intel an der Entwicklung geeigneter Systeme. ¨ Tabelle 1.1 gibt einen Uberblick u ¨ ber aktuelle MulticoreProzessoren. Zu bemerken ist dabei, dass der Sun UltraSPARC T1-Prozessor im Gegensatz zu den drei anderen Prozessoren kaum Unterst¨ utzung f¨ ur Floating-PointBerechnungen bietet und somit u ur den Ein¨ berwiegend f¨ satz im Serverbereich, wie Web-Server oder ApplikationsServer, geeignet ist. F¨ ur eine detailliertere Behandlung der Architektur von Multicore-Prozessoren und weiterer Beispiele verweisen wir auf [10, 28].

1.4 Beispiele

13

¨ Tabelle 1.1. Uberblick u ¨ber verschiedene Multicore-Prozessoren, vgl. auch [28]. Intel Prozessor Core 2 Duo Prozessorkerne 2 Instruktionen 4 pro Zyklus SMT nein L1-Cache I/D 32/32 in KB per core L2-Cache 4 MB shared Taktrate (GHz) 2.66 Transistoren 291 Mio Stromverbrauch 65 W

IBM AMD Power 5 Opteron 2 2 4 3 ja 64/32 1.9 MB shared 1.9 276 Mio 125 W

nein 64/64

Sun T1 8 1 ja 16/8

1 MB 3 MB per core shared 2.4 1.2 233 Mio 300 Mio 110 W 79 W

1.4 Beispiele Im Folgenden wird die Architektur von Multicore-Prozessoren anhand zweier Beispiele verdeutlicht: der Intel Core 2 Duo-Architektur und dem IBM Cell-Prozessor. Intel Core 2 Prozessor Intel Core 2 bezeichnet eine Familie von Intel-Prozessoren mit ¨ ahnlicher Architektur. Die Intel Core-Architektur basiert auf einer Weiterentwicklung der Pentium M Prozessoren, die viele Jahre im Notebookbereich eingesetzt wurden. Die neue Architektur l¨ ost die bei den Pentium 4 Prozessoren noch eingesetzte NetBurst-Architektur ab. Signifikante Merkmale der neuen Architektur sind:

14

• • •

•

1 Kurz¨ uberblick Multicore-Prozessoren

eine drastische Verk¨ urzung der internen Pipelines (maximal 14 Stufen anstatt maximal 31 Stufen bei der NetBurst-Architektur), damit verbunden eine Reduktion der Taktrate und damit verbunden auch eine deutliche Reduktion des Stromverbrauchs: die Reduktion des Stromverbrauches wird auch durch eine Power-Management-Einheit unterst¨ utzt, die das zeitweise Ausschalten ungenutzter Prozessorteile erm¨oglicht [48] und die Unterst¨ utzung neuer Streaming-Erweiterungen (Streaming SIMD Extensions, SSE).

Intel Core 2 Prozessoren werden zur Zeit (August 2007) als Core 2 Duo bzw. Core 2 Quad Prozessoren mit 2 bzw. 4 unabh¨ angigen Prozessorkernen in 65nm-Technologie gefertigt. Im Folgenden wird der Core 2 Duo Prozessor kurz beschrieben [24]. Die Core 2 Quad Prozessoren haben einen a ¨hnlichen Aufbau, enthalten aber 4 statt 2 Prozessorkerne. Da die Core 2 Prozessoren auf der Technik des Pentium M Prozessors basieren, unterst¨ utzen sie kein Hyperthreading. Die allgemeine Struktur der Core 2 Duo Architektur ist in Abb. 1.4 wiedergegeben. Der Prozessorchip enth¨alt zwei unabh¨ angige Prozessorkerne, von denen jeder separate L1-Caches anspricht; diese sind f¨ ur Instruktionen (32K) und Daten (32K) getrennt realisiert. Der L2-Cache (4 MB) ist dagegen nicht exklusiv und wird von beiden Prozessorkernen gemeinsam f¨ ur Instruktionen und Daten genutzt. Alle Zugriffe von den Prozessorkernen und vom externen Bus auf den L2-Cache werden von einem L2-Controller behandelt. F¨ ur die Sicherstellung der Koh¨ arenz der auf den verschiedenen Stufen der Speicherhierarchie abgelegten Daten wird ein MESI-Protokoll (Modified, Exclusive, Shared, Invalid) verwendet, vgl. [17, 47, 59] f¨ ur eine detaillierte Erkl¨arung. Alle Daten- und I/O-Anfragen zum oder vom externen Bus

1.4 Beispiele

15

(Front Side Bus) werden u ¨ ber einen Bus-Controller gesteuert. Core 2 Duo Prozessor Core 0

Core 1

Architektur−Ressourcen

Architektur−Ressourcen

Ausführungs−Ressourcen

Ausführungs−Ressourcen

L1−Caches (I/O) Cache−Controller

L1−Caches (I/O) Cache−Controller

Power−Management−Controller L2−Cache mit Controller (shared) Bus−Interface und −Controller

FrontSideBus

¨ Abbildung 1.4. Uberblick Core 2 Duo Architektur.

Ein wichtiges Element ist die Kontrolleinheit f¨ ur den Stromverbrauch des Prozessors (Power Management Controller) [48], die den Stromverbrauch des Prozessorchips durch Reduktion der Taktrate der Prozessorenkerne oder durch Abschalten (von Teilen) des L2-Caches reduzieren kann. Jeder Prozessorkern f¨ uhrt einen separaten Strom von Instruktionen aus, der sowohl Berechnungs- als auch Speicherzugriffsinstruktionen (load/store) enthalten kann. Dabei kann jeder der Prozessorkerne bis zu vier Instruktionen gleichzeitig verarbeiten. Die Prozessorkerne enthalten separate Funktionseinheiten f¨ ur das Laden bzw. Speichern von

16

1 Kurz¨ uberblick Multicore-Prozessoren

Daten, die Ausf¨ uhrung von Integeroperationen (durch eine ALU, arithmetic logic unit), Floating-Point-Operationen sowie SSE-Operationen. Instruktionen k¨ onnen aber nur dann parallel zueinander ausgef¨ uhrt werden, wenn keine Abh¨ angigkeiten zwischen ihnen bestehen. F¨ ur die Steuerung der Ausf¨ uhrung werden komplexe Schedulingverfahren eingesetzt, die auch eine Umordnung von Instruktionen (out-of-order execution) erlauben, um eine m¨oglichst gute Ausnutzung der Funktionseinheiten zu verwirklichen [28]. Laden von Instruktionen Instruktionsschlange Mikrocode ROM

Dekodiereinheit

L2− Cache (shared)

Register−Umbenennung und −Allokierung Umordnungspuffer Instruktions−Scheduler ALU Branch MMX/SSE FPMove

ALU FPAdd MMX/SSE FPMove

ALU FPMul MMX/SSE FPMove

Load

Store

Speicherzugriffspuffer

L1−Datencache

Abbildung 1.5. Instruktionsverarbeitung und Speicherorganisation eines Prozessorkerns des Intel Core 2 Prozessors.

Abbildung 1.5 veranschaulicht die Organisation der Abarbeitung von Instruktionen durch einen der Prozessorkerne [20]. Jeder der Prozessorkerne l¨ adt x86-Instruktionen in eine Instruktionsschlange, auf die die Dekodiereinheit zugreift und die Instruktionen in Mikroinstruktionen zer-

1.4 Beispiele

17

legt. F¨ ur komplexere x86-Instruktionen werden die zugeh¨ origen Mikroinstruktionen u ¨ ber einen ROM-Speicher geladen. Die Mikroinstruktionen werden vom InstruktionsScheduler freien Funktionseinheiten zugeordnet, wobei die Instruktionen in einer gegen¨ uber dem urspr¨ unglichen Programmcode ge¨ anderten Reihenfolge abgesetzt werden k¨onnen. Alle Speicherzugriffsoperationen werden u ¨ ber den L1Datencache abgesetzt, der Integer-und Floating-Point-Daten enth¨ alt. F¨ ur Ende 2007 bzw. Anfang 2008 sollen Intel Core 2Prozessoren mit verbesserter Core-Architektur eingef¨ uhrt werden (Codename Penryn). Voraussichtlich f¨ ur Ende 2008 ist eine neue Generation von Intel-Prozessoren geplant, die auf einer neuen Architektur basiert (Codename Nehalem). Diese neuen Prozessoren sollen neben mehreren Prozessorkernen (zu Beginn acht) auch einen Graphikkern und einen Speichercontroller auf einem Prozessorchip integrieren. Die neuen Prozessoren sollen auch wieder die SMT-Technik (simultanes Multithreading) unterst¨ utzen, so dass auf jedem Prozessorkern gleichzeitig zwei Threads ausgef¨ uhrt werden k¨ onnen. Diese Technik wurde teilweise f¨ ur Pentium 4 Prozessoren verwendet, nicht jedoch f¨ ur die Core 2 Duo und Quad Prozessoren. IBM Cell-Prozessor Der Cell-Prozessor wurde von IBM in Zusammenarbeit mit Sony und Toshiba entwickelt. Der Prozessor wird u.a. von Sony in der Spielekonsole PlayStation 3 eingesetzt, siehe [39, 34] f¨ ur ausf¨ uhrlichere Informationen. Der CellProzessor enth¨ alt ein Power Processing Element (PPE) und 8 Single-Instruction Multiple-Datastream (SIMD) Prozessoren. Das PPE ist ein konventioneller 64-Bit-Mikroprozessor auf der Basis der Power-Architektur von IBM mit relativ

18

1 Kurz¨ uberblick Multicore-Prozessoren

einfachem Design: der Prozessor kann pro Takt zwei Instruktionen absetzen und simultan zwei unabh¨angige Threads ausf¨ uhren. Die einfache Struktur hat den Vorteil, dass trotz hoher Taktrate eine geringe Leistungsaufnahme resultiert. F¨ ur den gesamten Prozessor ist bei einer Taktrate von 3.2 GHz nur eine Leistungsaufnahme von 60-80 Watt erforderlich. Auf der Chipfl¨ ache des Cell-Prozessors sind neben dem PPE acht SIMD-Prozessoren integriert, die als SPE (Synergetic Processing Element) bezeichnet werden. Jedes SPE stellt einen unabh¨ angigen Vektorprozessor mit einem 256KB großen lokalem SRAM-Speicher dar, der als Local Store (LS) bezeichnet wird. Das Laden von Daten in den LS und das Zur¨ uckspeichern von Resultaten aus dem LS in den Hauptspeicher muss per Software erfolgen. Jedes SPE enth¨ alt 128 128-Bit-Register, in denen die Operanden von Instruktionen abgelegt werden k¨onnen. Da auf die Daten in den Registern sehr schnell zugegriffen werden kann, reduziert die große Registeranzahl die Notwendigkeit von Zugriffen auf den LS und f¨ uhrt damit zu einer geringen mittleren Speicherzugriffszeit. Jedes SPE hat vier Floating-Point-Einheiten (32 Bit) und vier IntegerEinheiten. Z¨ ahlt man eine Multiply-Add-Instruktion als zwei Operationen, kann jedes SPE bei 3.2 GHz Taktrate pro Sekunde u ¨ ber 25 Milliarden Floating-Point-Operationen (25.6 GFlops) und u ¨ ber 25 Milliarden Integer-Operationen (25.6 Gops) ausf¨ uhren. Da ein Cell-Prozessor acht SPE enth¨ alt, f¨ uhrt dies zu einer maximalen Performance von u ¨ ber 200 GFlops, wobei die Leistung des PPE noch nicht ber¨ ucksichtigt wurde. Eine solche Leistung kann allerdings nur bei guter Ausnutzung der LS-Speicher und effizienter Zuordnung von Instruktionen an Funktionseinheiten der SPE erreicht werden. Zu beachten ist auch, dass sich diese Angabe auf 32-Bit Floating-Point-Zahlen bezieht. Der Cell-

1.4 Beispiele

19

Prozessor kann durch Zusammenlegen von Funktionseinheiten auch 64-Bit Floating-Point-Zahlen verarbeiten, dies resultiert aber in einer wesentlich geringeren maximalen Performance. Zur Vereinfachung der Steuerung der SPEs und zur Vereinfachung des Schedulings verwenden die SPEs intern keine SMT-Technik. Die zentrale Verbindungseinheit des Cell-Prozessors ist ein Bussystem, der sogenannte Element Interconnect Bus (EIB). Dieser besteht aus vier unidirektionalen Ringverbindungen, die eine Wortbreite von 16 Bytes haben und mit der halben Taktrate des Prozessors arbeiten. Zwei der Ringe werden in entgegengesetzter Richtung zu den anderen beiden Ringe betrieben, so dass die maximale Latenz im schlechtesten Fall durch einen halben Ringdurchlauf bestimmt wird. F¨ ur den Transport von Daten zwischen benachbarten Ringelementen k¨ onnen maximal drei Transferoperationen simultan durchgef¨ uhrt werden, f¨ ur den Zyklus des Prozessors ergibt dies 16 · 3/2 = 24 Bytes pro Zyklus. F¨ ur die vier Ringverbindungen ergibt dies eine maximale Transferrate von 96 Bytes pro Zyklus, woraus bei einer Taktrate von 3.2 GHz eine maximale Transferrate von u ¨ ber 300 GBytes/Sekunde resultiert. Abbildung 1.6 zeigt einen schematischen Aufbau des Cell-Prozessors mit den bisher beschriebenen Elementen sowie dem Speichersystem (Memory Interface Controller, MIC) und dem I/O-System (Bus Interface Controller, BIC). Das Speichersystem unterst¨ utzt die XDR-Schnittstelle von Rambus. Das I/O-System unterst¨ utzt das Rambus RRAC (Redwood Rambus Access Cell) Protokoll. Zum Erreichen einer guten Leistung ist es wichtig, die SPEs des Cell-Prozessors effizient zu nutzen. Dies kann f¨ ur spezialisierte Programme, wie z.B. Videospiele, durch direkte Verwendung von SPE-Assembleranweisungen erreicht werden. Da dies f¨ ur die meisten Anwendungsprogramme

20

1 Kurz¨ uberblick Multicore-Prozessoren Synergetic Processing Elements SPU

SPU

SPU

SPU

SPU

SPU

SPU

SPU

LS

LS

LS

LS

LS

LS

LS

LS

16B/ Zyklus

EIB (bis 96 B/Zyklus)

L2

L1

MIC

BIC

Dual XDR

RRAC I/O

PPU

64−Bit Power Architektur

Abbildung 1.6. Schematischer Aufbau des Cell-Prozessors.

zu aufwendig ist, werden f¨ ur das Erreichen einer guten Gesamtleistung eine effektive Compilerunterst¨ utzung sowie die Verwendung spezialisierter Programmbibliotheken z.B. zur Verwaltung von Taskschlangen wichtig sein.

2 Konzepte paralleler Programmierung

Die Leistungsverbesserung der Generation der MulticoreProzessoren wird technologisch durch mehrere Prozessorkerne auf einem Chip erreicht. Im Gegensatz zu bisherigen Leistungsverbesserungen bei Prozessoren hat diese Technologie jedoch Auswirkungen auf die Softwareentwicklung: Konnten bisherige Verbesserungen der Prozessorhardware zu Leistungsgewinnen bei existierenden (sequentiellen) Programmen f¨ uhren, ohne dass die Programme ge¨andert werden mussten, so ist zur vollen Ausnutzung der Leistung der Multicore-Prozessoren ein Umdenken hin zur parallelen Programmierung notwendig [62]. Parallele Programmiertechniken sind seit vielen Jahren im Einsatz, etwa im wissenschaftlichen Rechnen auf Parallelrechnern oder im Multithreading, und stellen somit keinen wirklich neuen Programmierstil dar. Neu hingegen ist, dass durch die k¨ unftige Allgegenw¨ artigkeit der MulticoreProzessoren ein Ausbreiten paralleler Programmiertechniken in alle Bereiche der Softwareentwicklung erwartet wird und diese damit zum R¨ ustzeug eines jeden Softwareentwicklers geh¨ oren werden.

22

2 Konzepte paralleler Programmierung

Ein wesentlicher Schritt in der Programmierung von Multicore-Prozessoren ist das Bereitstellen mehrerer Berechnungsstr¨ ome, die auf den Kernen eines Multicore-Prozessors simultan, also gleichzeitig, abgearbeitet werden. Zun¨ achst ist die rein gedankliche Arbeit durchzuf¨ uhren, einen einzelnen Anwendungsalgorithmus in solche Berechnungsstr¨ ome zu zerlegen, was eine durchaus langwierige, schwierige und kreative Aufgabe sein kann, da es eben sehr viele M¨ oglichkeiten gibt, dies zu tun, und insbesondere korrekte und effiziente Software resultieren soll. Zur Erstellung der parallelen Software sind einige Grundbegriffe und -kenntnisse hilfreich: • • • • •

Wie wird beim Entwurf eines parallelen Programmes vorgegangen? Welche Eigenschaften der parallelen Hardware sollen zu Grunde gelegt werden? Welches parallele Programmiermodell soll genutzt werden? Wie kann der Leistungsvorteil des parallelen Programms gegen¨ uber dem sequentiellen bestimmt werden? Welche parallele Programmierumgebung oder -sprache soll genutzt werden?

2.1 Entwurf paralleler Programme Die Grundidee der parallelen Programmierung besteht darin, mehrere Berechnungsstr¨ ome zu erzeugen, die gleichzeitig, also parallel, ausgef¨ uhrt werden k¨ onnen und durch koordinierte Zusammenarbeit eine gew¨ unschte Aufgabe erledigen. Liegt bereits ein sequentielles Programm vor, so spricht man auch von der Parallelisierung eines Programmes.

2.1 Entwurf paralleler Programme

23

Zur Erzeugung der Berechnungsstr¨ ome wird die auszuf¨ uhrende Aufgabe in Teilaufgaben zerlegt, die auch Tasks genannt werden. Tasks sind die kleinsten Einheiten der Parallelit¨ at. Beim Entwurf der Taskstruktur eines Programmes m¨ ussen Daten- und Kontrollabh¨ angigkeiten beachtet und eingeplant werden, um ein korrektes paralleles Programm zu erhalten. Die Gr¨ oße der Tasks wird Granularit¨ at genannt. F¨ ur die tats¨ achliche parallele Abarbeitung werden die Teilaufgaben in Form von Threads oder Prozessen auf physikalische Rechenressourcen abgebildet. Die Rechenressourcen k¨ onnen Prozessoren eines Parallelrechners, aber auch die Prozessorkerne eines MulticoreProzessors sein. Die Zuordnung von Tasks an Prozesse oder Threads wird auch als Scheduling bezeichnet. Dabei kann man zwischen statischem Scheduling, bei dem die Zuteilung beim Start des Programms festgelegt wird, und dynamischem Scheduling, bei dem die Zuteilung w¨ahrend der Abarbeitung des Programms erfolgt, unterscheiden. Die Abbildung von Prozessen oder Threads auf Prozessorkerne, auch Mapping genannt, kann explizit im Programm bzw. durch das Betriebssystem erfolgen. Abbildung 2.1 zeigt eine Veranschaulichung. Software mit mehreren parallel laufenden Tasks gibt es in vielen Bereichen schon seit Jahren. So bestehen Serveranwendungen h¨ aufig aus mehreren Threads oder Prozessen. Ein typisches Beispiel ist ein Webserver, der mit einem Haupt-Thread HTTP-Anfragenachrichten von beliebigen Clients (Browsern) entgegennimmt und f¨ ur jede eintreffende Verbindungsanfrage eines Clients einen separaten Thread erzeugt. Dieser Thread behandelt alle von diesem Client eintreffenden HTTP-Anfragen und schickt die zugeh¨ origen HTTP-Antwortnachrichten u ¨ ber eine Clientspezifische TCP-Verbindung. Wird diese TCP-Verbindung

24

2 Konzepte paralleler Programmierung

Tasks

Prozessor− Kerne

Threads Schedu− ling

T1

T2

Mapping

T1 T2

P1

T3

Task− Zerlegung

Thread− Zuordnung

T3

P2

Abbildung 2.1. Veranschaulichung der typischen Schritte zur Parallelisierung eines Anwendungsalgorithmus. Der Algorithmus wird in der Zerlegungsphase in Tasks mit gegenseitigen Abh¨ angigkeiten aufgespalten. Diese Tasks werden durch das Scheduling Threads zugeordnet, die auf Prozessorkerne abgebildet werden.

geschlossen, wird auch der zugeh¨ orige Thread beendet. Durch dieses Vorgehen kann ein Webserver gleichzeitig viele ankommende Anfragen nebenl¨ aufig erledigen oder auf verf¨ ugbaren Rechenressourcen parallel bearbeiten. F¨ ur Webserver mit vielen Anfragen (wie google oder ebay) werden entsprechende Plattformen mit vielen Rechenressourcen bereitgehalten. Abarbeitung paralleler Programme F¨ ur die parallele Abarbeitung der Tasks bzw. Threads oder Prozesse gibt es verschiedene Ans¨ atze, vgl. z.B. auch [3]: •

Multitasking: Multitasking-Betriebssysteme arbeiten mehrere Threads oder Prozesse in Zeitscheiben auf demselben Prozessor ab. Hierdurch k¨ onnen etwa die Latenzzeiten von I/O-Operationen durch eine verschachtelte Abarbeitung der Tasks u ¨ berdeckt werden. Diese Form

2.1 Entwurf paralleler Programme

•

•

•

25

der Abarbeitung mehrerer Tasks wird als Nebenl¨aufigkeit (Concurrency) bezeichnet; mehrere Tasks werden gleichzeitig bearbeitet, aber nur eine Task macht zu einem bestimmten Zeitpunkt einen tats¨ achlichen Rechenfortschritt. Eine simultane parallele Abarbeitung findet also nicht statt. Multiprocessing: Die Verwendung mehrerer physikalischer Prozessoren macht eine tats¨ achliche parallele Abarbeitung mehrerer Tasks m¨ oglich. Bedingt durch die hardwarem¨ aßige Parallelit¨ at mit mehreren physikalischen Prozessoren kann jedoch ein nicht unerheblicher zeitlicher Zusatzaufwand (Overhead) entstehen. Simultanes Multithreading (SMT): Werden mehrere logische Prozessoren auf einem physikalischen Prozessor ausgef¨ uhrt, so k¨ onnen die Hardwareressourcen eines Prozessors besser genutzt werden und es kann eine teilweise beschleunigte Abarbeitung von Tasks erfolgen, vgl. Kap. 1. Bei zwei logischen Prozessoren sind Leistungssteigerungen durch Nutzung von Wartezeiten eines Threads f¨ ur die Berechnungen des anderen Threads um bis zu 30 % m¨ oglich. Chip-Multiprocessing: Der n¨ achste Schritt ist nun, die Idee der Threading-Technologie auf einem Chip mit dem Multiprocessing zu verbinden, was durch MulticoreProzessoren m¨ oglich ist. Die Programmierung von Multicore-Prozessoren vereint das Multiprocessing mit dem simultanen Multithreading in den Sinne, dass Multithreading-Programme nicht nebenl¨ aufig sondern tats¨ achlich parallel auf einen Prozessor abgearbeitet werden. Dadurch sind im Idealfall Leistungssteigerungen bis zu 100 % f¨ ur einen Dualcore-Prozessor m¨oglich.

F¨ ur die Programmierung von Multicore-Prozessoren werden Multithreading-Programme eingesetzt. Obwohl viele

26

2 Konzepte paralleler Programmierung

moderne Programme bereits Multithreading verwenden, gibt es doch Unterschiede, die gegen¨ uber der Programmierung von Prozessoren mit simultanem Multithreading zu beachten sind: •

•

•

Einsatz zur Leistungsverbesserung: Die Leistungsverbesserungen von SMT-Prozessoren wird meistens zur Verringerung der Antwortzeiten f¨ ur den Nutzer eingesetzt, indem etwa ein Thread zur Beantwortung einer oder mehrerer Benutzeranfragen abgespalten und nebenl¨ aufig ausgef¨ uhrt wird. In Multicore-Prozessoren hingegen wird die gesamte Arbeit eines Programmes durch Partitionierung auf die einzelnen Kerne verteilt und gleichzeitig abgearbeitet. Auswirkungen des Caches: Falls jeder Kern eines Multicore-Prozessors einen eigenen Cache besitzt, so kann es zu dem beim Multiprocessing bekannten False Sharing kommen. Bei False Sharing handelt es sich um das Problem, dass zwei Kerne gleichzeitig auf Daten arbeiten, die zwar verschieden sind, jedoch in derselben Cachezeile liegen. Obwohl die Daten also unabh¨angig sind, wird die Cachezeile im jeweils anderen Kern als ung¨ ultig markiert, wodurch es zu Leistungsabfall kommt. Thread-Priorit¨ aten: Bei der Ausf¨ uhrung von Multithreading-Programmen auf Prozessoren mit nur einem Kern wird immer der Thread mit der h¨ ochsten Priorit¨at zuerst bearbeitet. Bei Prozessoren mit mehreren Kernen k¨ onnen jedoch auch Threads mit unterschiedlichen Priorit¨ aten gleichzeitig abgearbeitet werden, was zu durchaus unterschiedlichen Resultaten f¨ uhren kann.

Diese Beispiele zeigen, dass f¨ ur den Entwurf von Multithreading-Programmen f¨ ur Multicore-Prozessoren nicht nur die Techniken der Threadprogrammierung gebraucht werden, sondern Programmiertechniken, Methoden und Design-

2.2 Klassifizierung paralleler Architekturen

27

entscheidungen der parallelen Programmierung eine erhebliche Rolle spielen.

2.2 Klassifizierung paralleler Architekturen Unter paralleler Hardware wird Hardware zusammengefasst, die mehrere Rechenressourcen bereitstellt, auf denen ein Programm in Form mehrerer Berechnungsstr¨ome abgearbeitet wird. Die Formen paralleler Hardware reichen also von herk¨ ommlichen Parallelrechnern bis hin zu parallelen Rechenressourcen auf einem Chip, wie z.B. bei MulticoreProzessoren. Eine erste Klassifizierung solcher paralleler Hardware hat bereits Flynn in der nach ihm benannten Flynnschen Klassifikation gegeben [23]. Diese Klassifikation unterteilt parallele Hardware in vier Klassen mit unterschiedlichen Daten- und Kontrollfl¨ ussen: •

•

•

Die SISD (Single Instruction, Single Data) Rechner besitzen eine Rechenressource, einen Datenspeicher und einen Programmspeicher, entsprechen also dem klassischen von-Neumann-Rechner der sequentiellen Programmierung. Die MISD (Multiple Instruction, Single Data) Rechner stellen mehrere Rechenressourcen, aber nur einen Programmspeicher bereit. Wegen der geringen praktischen Relevanz spielt diese Klasse keine wesentliche Rolle. Die SIMD (Single Instruction, Multiple Data) Rechner bestehen aus mehreren Rechenressourcen mit jeweils separatem Zugriff auf einen Datenspeicher, aber nur einem Programmspeicher. Jede Ressource f¨ uhrt dieselben Instruktionen aus, die aus dem Programmspeicher geladen werden, wendet diese aber auf unterschiedliche Daten an. F¨ ur diese Klasse wurden in der Vergangenheit Parallelrechner konstruiert und genutzt.

28

•

2 Konzepte paralleler Programmierung

Die MIMD (Multiple Instruction, Multiple Data) Rechner sind die allgemeinste Klasse und zeichnen sich durch mehrere Rechenressourcen mit jeweils separatem Zugriff auf einen Datenspeicher und jeweils lokalen Programmspeichern aus. Jede Rechenressource kann also unterschiedliche Instruktionen auf unterschiedlichen Daten verarbeiten.

Zur Klasse der MIMD-Rechner geh¨ oren viele der heute aktuellen Parallelrechner, Cluster von PCs aber auch Multicore-Prozessoren, wobei die einzelnen Prozessoren, die PCs des Clusters oder die Kerne auf dem Chip eines Multicore-Prozessors die jeweiligen Rechenressourcen bilden. Dies zeigt, dass die Flynnsche Klassifizierung f¨ ur die heutige Vielfalt an parallelen Rechenressourcen zu grob ist und weitere Unterteilungen f¨ ur den Softwareentwickler n¨ utzlich sind. Eine der weiteren Unterschiede der Hardware von MIMD-Rechnern ist die Speicherorganisation, die sich auf den Zugriff der Rechenressourcen auf die Daten eines Programms auswirkt: Rechner mit verteiltem Speicher bestehen aus Rechenressourcen, die jeweils einen ihnen zugeordneten lokalen bzw. privaten Speicher haben. Auf Daten im lokalen Speicher hat jeweils nur die zugeordnete Rechenressource Zugriff. Werden Daten aus einem Speicher ben¨otigt, der zu einer anderen Rechenressource lokal ist, so werden Programmiermechanismen, wie z. B. Kommunikation u ¨ ber ein Verbindungsnetzwerk, eingesetzt. Clustersysteme, aber auch viele Parallelrechner geh¨ oren in diese Klasse. Rechner mit gemeinsamem Speicher bestehen aus mehreren Rechenressourcen und einem globalen oder gemeinsamen Speicher, auf den alle Rechenressourcen u ¨ ber ein Verbindungsnetzwerk auf Daten zugreifen k¨onnen. Dadurch kann jede Rechenressource die gesamten Daten des

2.3 Parallele Programmiermodelle

29

parallelen Programms zugreifen und verarbeiten. ServerArchitekturen und insbesondere Multicore-Prozessoren arbeiten mit einem physikalisch gemeinsamen Speicher. Die durch die Hardware gegebene Organisation des Speichers in verteilten und gemeinsamen Speicher kann f¨ ur den Programmierer in Form privater oder gemeinsamer Variable sichtbar und nutzbar sein. Es ist prinzipiell jedoch mit Hilfe entsprechender Softwareunterst¨ utzung m¨oglich, das Programmieren mit gemeinsamen Variablen (shared variables) auch auf physikalisch verteiltem Speicher bereitzustellen. Ebenso kann die Programmierung mit verteiltem Adressraum und Kommunikation auf einem physikalisch gemeinsamen Speicher durch zus¨ atzliche Software m¨oglich sein. Dies ist nur ein Beispiel daf¨ ur, dass die gegebene Hardware nur ein Teil dessen ist, was dem Softwareentwickler als Sicht auf ein paralleles System dient.

2.3 Parallele Programmiermodelle Der Entwurf eines parallelen Programmes basiert immer auch auf einer abstrakten Sicht auf das parallele System, auf dem die parallele Software abgearbeitet werden soll. Diese abstrakte Sicht wird paralleles Programmiermodell genannt und setzt sich aus mehr als nur der gegebenen parallelen Hardware zusammen: Ein paralleles Programmiermodell beschreibt ein paralleles Rechensystem aus der Sicht, die sich dem Softwareentwickler durch Systemsoftware wie Betriebssystem, parallele Programmiersprache oder -bibliothek, Compiler und Laufzeitbibliothek bietet. Entsprechend viele durchaus unterschiedliche parallele Programmiermodelle bieten sich dem Softwareentwickler an. Folgende Kriterien erlauben jedoch eine systematische Her-

30

2 Konzepte paralleler Programmierung

angehensweise an diese Vielfalt der Programmiermodelle [59]: • • •

•

• •

Auf welcher Ebene eines Programmes sollen parallele Programmteile ausgef¨ uhrt werden? (z.B. Instruktionsebene, Anweisungsebene oder Prozedurebene) Sollen parallele Programmteile explizit angegeben werden? (explizit oder implizit parallele Programme) In welcher Form werden parallele Programmteile angegeben? (z.B. als beim Start des Programmes erzeugte Menge von Prozessen oder etwa Tasks, die dynamisch erzeugt und zugeordnet werden) Wie erfolgt die Abarbeitung der parallelen Programmteile im Verh¨ altnis zueinander? (SIMD oder SPMD (Single Program, Multiple Data); synchrone oder asynchrone Berechnungen) Wie findet der Informationsaustausch zwischen parallelen Programmteilen statt? (Kommunikation oder gemeinsame Variable) Welche Formen der Synchronisation k¨ onnen genutzt werden? (z.B. Barrier-Synchronisation oder Sperrmechanismen)

Ebenen der Parallelit¨ at Unabh¨ angige und damit parallel abarbeitbare Aufgaben k¨ onnen auf sehr unterschiedlichen Ebenen eines Programms auftreten, wobei f¨ ur die Parallelisierung eines Programmes meist jeweils nur eine Ebene genutzt wird. •

Parallelit¨ at auf Instruktionsebene kann ausgenutzt werden, falls zwischen zwei Instruktionen keine Datenabh¨ angigkeit besteht. Diese Form der Parallelit¨at kann durch Compiler auf superskalaren Prozessoren eingesetzt werden.

2.3 Parallele Programmiermodelle

•

•

•

31

Bei der Parallelit¨ at auf Anweisungsebene werden mehrere Anweisungen auf denselben oder verschiedenen Daten parallel ausgef¨ uhrt. Eine Form ist die Datenparallelit¨ at, bei der Datenstrukturen wie Felder in Teilbereiche unterteilt werden, auf denen parallel zueinander dieselben Operationen ausgef¨ uhrt werden. Diese Arbeitsweise wird im SIMD Modell genutzt, in dem in jedem Schritt die gleiche Anweisung auf evtl. unterschiedlichen Daten ausgef¨ uhrt wird. Bei der Parallelit¨ at auf Schleifenebene werden unterschiedliche Iterationen einer Schleifenanweisung parallel zueinander ausgef¨ uhrt. Besondere Auspr¨agungen sind die forall und dopar Schleife. Bei der forallSchleife werden die Anweisungen im Schleifenrumpf parallel in Form von Vektoranweisungen nacheinander abgearbeitet. Die dopar-Schleife f¨ uhrt alle Anweisungen einer Schleifeniteration unabh¨ angig vor den anderen Schleifeniterationen aus. Je nach Datenabh¨angigkeiten zwischen den Schleifeniterationen kann es durch die Parallelit¨ at auf Schleifenebene zu unterschiedlichen Ergebnissen kommen als bei der sequentiellen Abarbeitung der Schleifenr¨ umpfe. Als parallele Schleife wird eine Schleife bezeichnet, deren Schleifenr¨ umpfe keine Datenabh¨ angigkeit aufweisen und somit eine parallele Abarbeitung zum gleichen Ergebnis f¨ uhrt wie die sequentielle Abarbeitung. Parallele Schleifen spielen bei Programmierumgebungen wie OpenMP eine wesentliche Rolle. Bei der Parallelit¨ at auf Funktionsebene werden gesamte Funktionsaktivierungen eines Programms parallel zueinander auf verschiedenen Prozessoren oder Prozessorkernen ausgef¨ uhrt. Bestehen zwischen parallel auszuf¨ uhrenden Funktionen Daten- oder Kontrollabh¨angigkeiten, so ist eine Koordination zwischen den Funktionen erforderlich. Dies erfolgt in Form von Kommunika-

32

2 Konzepte paralleler Programmierung

tion und Barrier-Anweisungen bei Modellen mit verteiltem Adressraum. Ein Beispiel ist die Programmierung mit MPI (Message Passing Interface) [59, 61]. Bei Modellen mit gemeinsamem Adressraum ist Synchronisation erforderlich; dies ist also f¨ ur die Programmierung von Multicore-Prozessoren notwendig und wird in Kapitel 3 vorgestellt. Explizite oder implizite Parallelit¨ at Eine Voraussetzung f¨ ur die parallele Abarbeitung auf einem Multicore-Prozessor ist das Vorhandensein mehrerer Berechnungsstr¨ ome. Diese k¨ onnen auf recht unterschiedliche Art erzeugt werden [60]. Bei impliziter Parallelit¨ at braucht der Programmierer keine Angaben zur Parallelit¨ at zu machen. Zwei unterschiedliche Vertreter impliziter Parallelit¨ at sind parallelisierende Compiler oder funktionale Programmiersprachen. Parallelisierende Compiler erzeugen aus einem gegebenen sequentiellen Programm ein paralleles Programm und nutzen dabei Abh¨ angigkeitsanalysen, um unabh¨ angige Berechnungen zu ermitteln. Dies ist in den meisten F¨allen eine komplexe Aufgabe und die Erfolge parallelisierender Compiler sind entsprechend begrenzt [55, 66, 5, 2]. Programme in einer funktionalen Programmiersprache bestehen aus einer Reihe von Funktionsdefinitionen und einem Ausdruck, dessen Auswertung das Programmergebnis liefert. Das Potential f¨ ur Parallelit¨ at liegt in der parallelen Auswertung der Argumente von Funktionen, da funktionale Programme keine Seiteneffekte haben und sich die Argumente somit nicht beeinflussen k¨ onnen [33, 64, 8]. Implizite Parallelit¨at wird teilweise auch von neuen Sprachen wie Fortress eingesetzt, vgl. Abschnitt 7.1.

2.3 Parallele Programmiermodelle

33

Explizite Parallelit¨ at mit impliziter Zerlegung liegt vor, wenn der Programmierer zwar angibt, wo im Programm Potential f¨ ur eine parallele Bearbeitung vorliegt, etwa eine parallele Schleife, die explizite Kodierung in Threads oder Prozesse aber nicht vornehmen muss. Viele parallele FORTRAN-Erweiterungen nutzen dieses Prinzip. Bei einer expliziten Zerlegung muss der Programmierer zus¨ atzlich angeben, welche Tasks es f¨ ur die parallele Abarbeitung geben soll, ohne aber eine Zuordnung an Prozesse oder explizite Kommunikation formulieren zu m¨ ussen. Ein Beispiel ist BSP [65]. Die explizite Zuordnung der Tasks an Prozesse wird in Koordinationssprachen wie Linda [12] zus¨ atzlich angegeben. Bei Programmiermodellen mit expliziter Kommunikation und Synchronisation muss der Programmierer alle Details der parallelen Abarbeitung angeben. Hierzu geh¨ ort das Message-Passing-Programmiermodell mit MPI, aber auch Programmierumgebungen zur Benutzung von Threads, wie Pthreads, das in Kap. 4 vorgestellt wird. Angabe paralleler Programmteile Sollen vom Programmierer die parallelen Programmteile explizit angegeben werden, so kann dies in ganz unterschiedlicher Form erfolgen. Bei der Angabe von Teilaufgaben in Form von Tasks werden diese implizit Prozessoren oder Kernen zugeordnet. Bei vollkommen explizit paralleler Programmierung sind die Programmierung von Threads oder von Prozessen die weit verbreiteten Formen. Thread-Programmierung: Ein Thread ist eine Folge von Anweisungen, die parallel zu anderen Anweisungsfolgen, also Threads, abgearbeitet werden k¨ onnen. Die Threads eines einzelnen Programmes besitzen f¨ ur die Abarbeitung jeweils eigene Ressourcen, wie Programmz¨ahler, Sta-

34

2 Konzepte paralleler Programmierung

tusinformationen des Prozessors oder einen Stack f¨ ur lokale Daten, nutzen jedoch einen gemeinsamen Datenspeicher. Damit ist das Thread-Modell f¨ ur die Programmierung von Multicore-Prozessoren geeignet. Message-Passing-Programmierung: Die MessagePassing-Programmierung nutzt Prozesse, die Programmteile bezeichnen, die jeweils auf einem separaten physikalischen oder logischen Prozessor abgearbeitet werden und somit jeweils einen privaten Adressraum besitzen. Abarbeitung paralleler Programmteile Die Abarbeitung paralleler Programmteile kann synchron erfolgen, indem die Anweisungen paralleler Threads oder Prozesse jeweils gleichzeitig abgearbeitet werden, wie etwa im SIMD-Modell, oder asynchron, also unabh¨angig voneinander bis eine explizite Synchronisation erfolgt, wie etwa im SPMD-Modell. Diese Festlegung der Abarbeitung wird meist vom Programmiermodell der benutzten Programmierumgebung vorgegeben. Dar¨ uber hinaus gibt es eine Reihe von Programmiermustern, in denen parallele Programmteile angeordnet werden, z.B. Pipelining, MasterWorker oder Produzenten-Konsumenten-Modell, und die vom Softwareentwickler explizit ausgew¨ ahlt werden. Informationsaustausch Ein wesentliches Merkmal f¨ ur den Informationsaustausch ist die Organisation des Adressraums. Bei einem verteilten Adressraum werden Daten durch Kommunikation ausgetauscht. Dies kann explizit im Programm angegeben sein, aber auch durch einen Compiler oder das Laufzeitsystem erzeugt werden. Bei einem gemeinsamen Adressraum kann

2.4 Parallele Leistungsmaße

35

der Informationsaustausch einfach u ¨ ber gemeinsame Variable in diesem Adressraum geschehen, auf die lesend oder schreibend zugegriffen werden kann. Hierdurch kann es jedoch auch zu Konflikten oder unerw¨ unschten Ergebnissen kommen, wenn dies unkoordiniert erfolgt. Die Koordination von parallelen Programmteilen spielt also eine wichtige Rolle bei der Programmierung eines gemeinsamen Adressraums und ist daher ein wesentlicher Bestandteil der Thread-Programmierung und der Programmierung von Multicore-Prozessoren. Formen der Synchronisation Synchronisation gibt es in Form von Barrier-Synchronisation, die bewirkt, dass alle beteiligten Threads oder Prozesse aufeinander warten, und im Sinne der Koordination von Threads. Letzteres hat insbesondere mit der Vermeidung von Konflikten beim Zugriff auf einen gemeinsamen Adressraum zu tun und setzt Sperrmechanismen und bedingtes Warten ein.

2.4 Parallele Leistungsmaße Ein wesentliches Kriterium zur Bewertung eines parallelen Programms ist dessen Laufzeit. Die parallele Laufzeit Tp (n) eines Programmes ist die Zeit zwischen dem Start der Abarbeitung des parallelen Programmes und der Beendigung der Abarbeitung aller beteiligten Prozessoren. Die parallele Laufzeit wird meist in Abh¨ angigkeit von der Anzahl p der zur Ausf¨ uhrung benutzten Prozessoren und einer Problemgr¨ oße n angegeben, die z.B. durch die Gr¨oße der Eingabe gegeben ist. F¨ ur Multicore-Prozessoren mit gemeinsamem Adressraum setzt sich die Laufzeit eines parallelen Programmes zusammen aus:

36

• • •

2 Konzepte paralleler Programmierung

der Zeit f¨ ur die Durchf¨ uhrung von Berechnungen durch die Prozessorkerne, der Zeit f¨ ur die Synchronisation beim Zugriff auf gemeinsame Daten, den Wartezeiten, die z.B. wegen ungleicher Verteilung der Last oder an Synchronisationspunkten entstehen.

Kosten: Die Kosten eines parallelen Programmes, h¨aufig auch Arbeit oder Prozessor-Zeit-Produkt genannt, ber¨ ucksichtigen die Zeit, die alle an der Ausf¨ uhrung beteiligten Prozessoren insgesamt zur Abarbeitung des Programmes verwenden. Die Kosten Cp (n) eines parallelen Programms sind definiert als Cp (n) = Tp (n) · p und sind damit ein Maß f¨ ur die von allen Prozessoren durchgef¨ uhrte Arbeit. Ein paralleles Programm heißt kostenoptimal, wenn Cp (n) = T ∗ (n) gilt, d.h. wenn insgesamt genauso viele Operationen ausgef¨ uhrt werden wie vom schnellsten sequentiellen Verfahren, das Laufzeit T ∗ (n) hat. Speedup: Zur Laufzeitanalyse paralleler Programme ist insbesondere ein Vergleich mit einer sequentiellen Implementierung von Interesse, um den Nutzen des Einsatzes der Parallelverarbeitung absch¨ atzen zu k¨ onnen. F¨ ur einen solchen Vergleich wird oft der Speedup-Begriff als Maß f¨ ur den relativen Geschwindigkeitsgewinn herangezogen. Der Speedup Sp (n) eines parallelen Programmes mit Laufzeit Tp (n) ist definiert als Sp (n) =

T ∗ (n) , Tp (n)

wobei p die Anzahl der Prozessoren zur L¨ osung des Problems der Gr¨ oße n bezeichnet. Der Speedup einer parallelen Implementierung gibt also den relativen Geschwindigkeitsvorteil an, der gegen¨ uber der besten sequentiellen

2.4 Parallele Leistungsmaße

37

Implementierung durch den Einsatz von Parallelverarbeitung auf p Prozessoren entsteht. Theoretisch gilt immer Sp (n) ≤ p. Durch Cacheeffekte kann in der Praxis auch der Fall Sp (n) > p (superlinearer Speedup) auftreten. Effizienz: Alternativ zum Speedup kann der Begriff der Effizienz eines parallelen Programmes benutzt werden, der ein Maß f¨ ur den Anteil der Laufzeit ist, den ein Prozessor f¨ ur Berechnungen ben¨ otigt, die auch im sequentiellen Programm vorhanden sind. Die Effizienz Ep (n) eines parallelen Programms ist definiert als Ep (n) =

Sp (n) T ∗ (n) T ∗ (n) = = Cp (n) p p · Tp (n)

wobei T ∗ (n) die Laufzeit des besten sequentiellen Algorithmus und Tp (n) die parallele Laufzeit ist. Liegt kein superlinearer Speedup vor, gilt Ep (n) ≤ 1. Der ideale Speedup Sp (n) = p entspricht einer Effizienz Ep (n) = 1. Amdahlsches Gesetz: Die m¨ ogliche Verringerung von Laufzeiten durch eine Parallelisierung sind oft begrenzt. So stellt etwa die Anzahl der Prozessoren die theoretisch obere Schranke des Speedups dar. Weitere Begrenzungen liegen im zu parallelisierenden Algorithmus selber begr¨ undet, der neben parallelisierbaren Anteilen auch durch Datenabh¨ angigkeiten bedingte, inh¨ arent sequentielle Anteile enthalten kann. Der Effekt von Programmteilen, die sequentiell ausgef¨ uhrt werden m¨ ussen, auf den erreichbaren Speedup wird durch das Amdahlsche Gesetz quantitativ erfasst [6]: Wenn bei einer parallelen Implementierung ein (konstanter) Bruchteil f (0 ≤ f ≤ 1) sequentiell ausgef¨ uhrt werden muss, setzt sich die Laufzeit der parallelen Implementierung aus der Laufzeit f · T ∗ (n) des sequentiellen Teils und der Laufzeit des parallelen Teils, die mindestens agt, zusammen. F¨ ur den erreichbaren (1 − f )/p · T ∗ (n) betr¨

38

2 Konzepte paralleler Programmierung

Speedup gilt damit Sp (n) =

1 T ∗ (n) 1 = ≤ . 1−f ∗ 1−f ∗ f f · T (n) + p T (n) f+ p

Bei dieser Berechnung wird der beste sequentielle Algorithmus verwendet und es wurde angenommen, dass sich der parallel ausf¨ uhrbare Teil perfekt parallelisieren l¨asst. Durch ein einfaches Beispiel sieht man, dass nicht parallelisierbare Berechnungsteile einen großen Einfluss auf den erreichbaren Speedup haben: Wenn 20% eines Programmes sequentiell abgearbeitet werden m¨ ussen, betr¨ agt nach Aussage des Amdahlschen Gesetzes der maximal erreichbare Speedup 5, egal wie viele Prozessoren eingesetzt werden. Nicht parallelisierbare Teile m¨ ussen insbesondere bei einer großen Anzahl von Prozessoren besonders beachtet werden. Skalierbarkeit: Das Verhalten der Leistung eines parallelen Programmes bei steigender Prozessoranzahl wird durch die Skalierbarkeit erfasst. Die Skalierbarkeit eines parallelen Programmes auf einem gegebenen Parallelrechner ist ein Maß f¨ ur die Eigenschaft, einen Leistungsgewinn proportional zur Anzahl p der verwendeten Prozessoren zu erreichen. Der Begriff der Skalierbarkeit wird in unterschiedlicher Weise pr¨ azisiert, z.B. durch Einbeziehung der Problemgr¨ oße n. Eine h¨ aufig beobachtete Eigenschaft paralleler Algorithmen ist es, dass f¨ ur festes n und steigendes p eine S¨ attigung des Speedups eintritt, dass aber f¨ ur festes p und steigende Problemgr¨ oße n ein h¨ oherer Speedup erzielt wird. In diesem Sinne bedeutet Skalierbarkeit, dass die Effizienz eines parallelen Programmes bei gleichzeitigem Ansteigen von Prozessoranzahl p und Problemgr¨oße n konstant bleibt.

3 Thread-Programmierung

Die Programmierung von Multicore-Prozessoren ist eng mit der parallelen Programmierung eines gemeinsamen Adressraumes und der Thread-Programmierung verbunden. Mehrere Berechnungsstr¨ ome desselben Programms k¨onnen parallel zueinander bearbeitet werden und greifen dabei auf Variablen des gemeinsamen Speichers zu. Diese Berechnungsstr¨ ome werden als Threads bezeichnet. Die Programmierung mit Threads ist ein seit vielen Jahren bekanntes Programmierkonzept [9] und kann vom Softwareentwickler durch verschiedene Programmierumgebungen oder -bibliotheken wie Pthreads, Java-Threads, OpenMP oder Win32 f¨ ur Multithreading-Programme genutzt werden.

3.1 Threads und Prozesse Die Abarbeitung von Threads h¨ angt eng mit der Abarbeitung von Prozessen zusammen, so dass beide zun¨achst nochmal genauer definiert und voneinander abgegrenzt werden.

40

3 Thread-Programmierung

Prozesse Ein Prozess ist ein sich in Ausf¨ uhrung befindendes Programm und umfasst neben dem ausf¨ uhrbaren Programmcode alle Informationen, die zur Ausf¨ uhrung des Programms erforderlich sind. Dazu geh¨ oren die Daten des Programms auf dem Laufzeitstack oder Heap, die zum Ausf¨ uhrungszeitpunkt aktuellen Registerinhalte und der aktuelle Wert des Programmz¨ ahlers, der die n¨ achste auszuf¨ uhrende Instruktion des Prozesses angibt. Jeder Prozess hat also seinen eigenen Adressraum. Alle diese Informationen ¨andern sich w¨ ahrend der Ausf¨ uhrung des Prozesses dynamisch. Wird die Rechenressource einem anderen Prozess zugeordnet, so muss der Zustand des suspendierten Prozesses gespeichert werden, damit die Ausf¨ uhrung dieses Prozesses zu einem sp¨ ateren Zeitpunkt mit genau diesem Zustand fortgesetzt werden kann. Dies wird als Kontextwechsel bezeichnet und ist je nach Hardwareunterst¨ utzung relativ aufwendig [54]. Prozesse werden bei Multitasking im Zeitscheibenverfahren von der Rechenressource abgearbeitet; es handelt sich also um Nebenl¨ aufigkeit und keine Gleichzeitigkeit. Bei Multiprozessor-Systemen ist eine tats¨ achliche Parallelit¨at m¨ oglich. Beim Erzeugen eines Prozesses muss dieser die zu seiner Ausf¨ uhrung erforderlichen Daten erhalten. Im UNIXBetriebssystem kann ein Prozess P1 mit Hilfe einer forkAnweisung einen neuen Prozess P2 erzeugen. Der neue Kindprozess P2 ist eine identische Kopie des Elternprozesses P1 zum Zeitpunkt des fork-Aufrufes. Dies bedeutet, dass der Kindprozess auf einer Kopie des Adressraumes des Elternprozesses arbeitet und das gleiche Programm wie der Elternprozess ausf¨ uhrt, und zwar ab der der forkAnweisung folgenden Anweisung. Der Kindprozess hat jedoch eine eigene Prozessnummer und kann in Abh¨angigkeit

3.1 Threads und Prozesse

41

von dieser Prozessnummer andere Anweisungen als der Elternprozess ausf¨ uhren, vgl. [46]. Da jeder Prozess einen eigenen Adressraum hat, ist die Erzeugung und Verwaltung von Prozessen je nach Gr¨ oße des Adressraumes relativ zeitaufwendig. Weiter kann bei h¨ aufiger Kommunikation der Austausch von Daten (¨ uber Sockets) einen nicht unerheblichen Anteil der Ausf¨ uhrungszeit ausmachen. Threads Das Threadmodell ist eine Erweiterung des Prozessmodells. Jeder Prozess besteht anstatt nur aus einem aus mehreren unabh¨ angigen Berechnungsstr¨ omen, die w¨ ahrend der Abarbeitung des Prozesses durch ein Schedulingverfahren der Rechenressource zugeteilt werden. Die Berechnungsstr¨ome eines Prozesses werden als Threads bezeichnet. Das Wort Thread wurde gew¨ ahlt, um anzudeuten, dass eine zusammenh¨ angende, evtl. sehr lange Folge von Instruktionen abgearbeitet wird. Ein wesentliches Merkmal von Threads besteht darin, dass die verschiedenen Threads eines Prozesses sich den Adressraum des Prozesses teilen, also einen gemeinsamen Adressraum haben. Wenn ein Thread einen Wert im Adressraum ablegt, kann daher ein anderer Thread des gleichen Prozesses diesen unmittelbar darauf lesen. Damit ist der Informationsaustausch zwischen Threads im Vergleich zur Kommunikation zwischen Prozessen u ¨ ber Sockets sehr schnell. Da die Threads eines Prozesses sich einen Adressraum teilen, braucht auch die Erzeugung von Threads wesentlich weniger Zeit als die Erzeugung von Prozessen. Das Kopieren des Adressraumes, das z.B. in UNIX beim Erzeugen von Prozessen mit einer fork-Anweisung notwendig ist, entf¨ allt. Das Arbeiten mit mehreren Threads innerhalb eines Prozesses ist somit wesentlich flexibler als das Arbei-

42

3 Thread-Programmierung

ten mit kooperierenden Prozessen, bietet aber die gleichen Vorteile. Insbesondere ist es m¨ oglich, die Threads eines Prozesses auf verschiedenen Prozessoren oder Prozessorkernen parallel auszuf¨ uhren. Threads k¨ onnen auf Benutzerebene als Benutzer-Threads oder auf Betriebssystemebene als BetriebssystemThreads implementiert werden. Threads auf Benutzerebene werden durch eine Thread-Bibliothek ohne Beteiligung des Betriebssystems verwaltet. Ein Wechsel des ausgef¨ uhrten Threads kann damit ohne Beteiligung des Betriebssystems erfolgen und ist daher in der Regel wesentlich schneller als der Wechsel bei Betriebssystem-Threads. T T

Bibliotheks− Scheduler

BP

T T

Prozess 1 T T T

Prozess n

BP

Bibliotheks− Scheduler

Betriebssystem− Scheduler

BP

P

BP

P

BP

P

BP

P

BP

Prozessoren

Betriebssystem− Prozesse

Abbildung 3.1. N:1-Abbildung – Thread-Verwaltung ohne Betriebssystem-Threads. Der Scheduler der Thread-Bibliothek w¨ ahlt den auszuf¨ uhrenden Thread T des Benutzerprozesses aus. Jedem Benutzerprozess ist ein Betriebssystemprozss BP zugeordnet. Der Betriebssystem-Scheduler w¨ ahlt die zu einem bestimmten Zeitpunkt auszuf¨ uhrenden Betriebssystemprozesse aus und bildet diese auf die Prozessoren P ab.

3.1 Threads und Prozesse

43

Der Nachteil von Threads auf Benutzerebene liegt darin, dass das Betriebssystem keine Kenntnis von den Threads hat und nur gesamte Prozesse verwaltet. Wenn ein Thread eines Prozesses das Betriebssystem aufruft, um z.B. eine I/O-Operation durchzuf¨ uhren, wird der CPU-Scheduler des Betriebssystems den gesamten Prozess suspendieren und die Rechenressource einem anderen Prozess zuteilen, da das Betriebssystem nicht weiß, dass innerhalb des Prozesses zu einem anderen Thread umgeschaltet werden kann. Dies gilt f¨ ur Betriebssystem-Threads nicht, da das Betriebssystem die Threads direkt verwaltet. T

BT

T

BT

T

Betriebssystem− Scheduler

BT

P

BT

P

BT

P

T

BT

P

T

BT

T

Prozess 1

T

Prozess n

Prozessoren

Betriebssystem− Threads

Abbildung 3.2. 1:1-Abbildung – Thread-Verwaltung mit Betriebssystem-Threads. Jeder Benutzer-Thread T wird eindeutig einem Betriebssystem-Thread BT zugeordnet.

44

3 Thread-Programmierung T T

Bibliotheks− Scheduler

BT

T T

Prozess 1 T T T

Prozess n

BT

Betriebssystem− Scheduler

BT

P

BT

P

BT

P

BT

P

BT

Bibliotheks− Scheduler

Prozessoren

Betriebssystem− Threads

Abbildung 3.3. N:M-Abbildung – Thread-Verwaltung mit Betriebssystem-Threads und zweistufigem Scheduling. BenutzerThreads T verschiedener Prozesse werden einer Menge von Betriebssystem-Threads BT zugeordnet (N:M-Abbildung).

Ausf¨ uhrungsmodelle f¨ ur Threads Wird eine Thread-Verwaltung durch das Betriebssystem nicht unterst¨ utzt, so ist die Thread-Bibliothek f¨ ur das Scheduling der Threads verantwortlich. Alle Benutzer-Threads eines Prozesses werden vom Bibliotheks-Scheduler auf einen Betriebssystem-Prozess abgebildet, was N:1-Abbildung genannt wird, siehe Abb. 3.1. Stellt das Betriebssystem eine Thread-Verwaltung zur Verf¨ ugung, so gibt es f¨ ur die Abbildung von Benutzer-Threads auf Betriebssystem-Threads zwei M¨ oglichkeiten: Die erste ist die 1:1-Abbildung, die f¨ ur jeden Benutzer-Thread einen Betriebssystem-Thread erzeugt, siehe Abb. 3.2. Der Betriebssystem-Scheduler w¨ahlt den jeweils auszuf¨ uhrenden Betriebssystem-Thread aus und verwaltet bei Mehr-Prozessor-Systemen die Ausf¨ uhrung der Betriebssystem-Threads auf den verschiedenen Prozesso-

3.1 Threads und Prozesse

45

ren. Die zweite M¨ oglichkeit ist die N:M-Abbildung, die ein zweistufiges Schedulingverfahren anwendet, siehe Abb. 3.3. Der Scheduler der Thread-Bibliothek ordnet die verschiedenen Threads der verschiedenen Prozesse einer vorgegebenen Menge von Betriebssystem-Threads zu, wobei ein Benutzer-Thread zu verschiedenen Zeitpunkten auf verschiedene Betriebssystem-Threads abgebildet werden kann. Zust¨ ande eines Threads Ob ein Thread gerade von einem Prozessor oder Prozessorkern abgearbeitet wird, h¨ angt nicht nur vom Scheduler, sondern auch von seinem Zustand ab. Threads k¨onnen sich in verschiedenen Zust¨ anden befinden: • • • • •

neu erzeugt lauff¨ ahig laufend wartend beendet

beendet

neu

Start

Ende Unterbrechung

lauf− fähig

laufend Zuteilung

Au Abbildung 3.4 verg un fw er ec ki ke anschaulicht die Zuoc l n B stands¨ uberg¨ ange. Die wartend ¨ Uberg¨ ange zwischen lauff¨ahig und laufend Abbildung 3.4. Zust¨ande eines Threwerden vom Schedu- ads. ler bestimmt. Blockierung bzw. Warten kann durch I/OOperationen, aber auch durch die Koordination zwischen den Threads eintreten.

Sichtbarkeit von Daten Die Threads eines Prozesses teilen sich einen gemeinsamen Adressraum, d.h. die globalen Variablen und alle dynamisch

46

3 Thread-Programmierung Stackdaten Stackdaten Stackdaten

} } }

Stackbereich für Hauptthread Stackbereich für Thread 1 Stackbereich für Thread 2

... Heapdaten globale Daten Programmcode

Adresse 0

Abbildung 3.5. Laufzeitverwaltung f¨ ur ein Programm mit mehreren Threads.

erzeugten Datenobjekte sind von allen erzeugten Threads des Prozesses zugreifbar. F¨ ur jeden Thread wird jedoch ein eigener Laufzeitstack gehalten, auf dem die von dem Thread aufgerufenen Funktionen mit ihren lokalen Variablen verwaltet werden, siehe Abb. 3.5. Die auf dem Laufzeitstack verwalteten, also statisch deklarierten Daten, sind lokale Daten des zugeh¨origen Threads und k¨ onnen von anderen Threads nicht zugegriffen werden. Da der Laufzeitstack eines Threads nur so lange existiert, wie der Thread selbst, kann ein Thread einen m¨ oglichen R¨ uckgabewert an einen anderen Thread nicht u ¨ber seinen Laufzeitstack u ¨ bergeben und es m¨ ussen andere Techniken verwendet werden.

3.2 Synchronisations-Mechanismen Wichtig bei der Thread-Programmierung ist die Koordination der Threads, die durch Synchronisations-Mechanismen erreicht wird. Die Koordination der Threads eines Multithreading-Programms wird vom Softwareentwick-

3.2 Synchronisations-Mechanismen

47

ler eingesetzt, um eine gew¨ unschte Ausf¨ uhrungsreihenfolge der beteiligten Threads zu erreichen oder um den Zugriff auf gemeinsame Daten zu gestalten. Die Koordination des Zugriffs auf den gemeinsamen Speicher dient der Vermeidung von unerw¨ unschten Effekten beim gleichzeitigen Zugriff auf dieselbe Variable. Dies trifft f¨ ur MultithreadingProgramme auf einer Rechenressource mit nebenl¨aufiger Abarbeitung im Zeitscheibenverfahren zu, aber auch auf eine tats¨ achlich parallele Abarbeitung auf mehreren Rechenressourcen. Da die Threads eines Prozesses im Wesentlichen u ¨ ber gemeinsame Daten kooperieren, bewirkt eine bestimmte Ausf¨ uhrungsreihenfolge einen speziellen Zustand des gemeinsamen Speichers, also eine bestimmte Belegung der gemeinsamen Variablen mit Werten, die f¨ ur alle Threads sichtbar sind. Die Effekte der Kooperation und Koordination k¨ onnen jedoch bei Nebenl¨ aufigkeit anders sein als bei Parallelit¨ at. Koordination der Berechnungsstr¨ ome Eine Barrier-Synchronisation bewirkt, dass alle beteiligten Threads aufeinander warten und keiner der Threads eine nach der Synchronisationsanweisung stehende Anweisung ausf¨ uhrt, bevor alle anderen Threads diese erreicht haben. Dadurch erscheint den Threads der gemeinsame Speicher aller beteiligten Threads in dem Zustand, der durch die Abarbeitung aller Anweisungen aller Threads vor der Barrier-Synchronisation erreicht wird. Zeitkritische Abl¨ aufe Das lesende und schreibende Zugreifen verschiedener Threads auf dieselbe gemeinsame Variable kann zu sogenannten zeitkritischen Abl¨ aufen f¨ uhren. Dies bedeutet, dass

48

3 Thread-Programmierung

das Ergebnis der Ausf¨ uhrung eines Programmst¨ ucks durch mehrere Threads von der relativen Ausf¨ uhrungsgeschwindigkeit der Threads zueinander abh¨ angt: Wenn das Programmst¨ uck zuerst von Thread T1 und dann von Thread T2 ausgef¨ uhrt wird, kann ein anderes Ergebnis berechnet werden als wenn dieses Programmst¨ uck zuerst von Thread uhrt wird. Das AufT2 und dann von Thread T1 ausgef¨ treten von zeitkritischen Abl¨ aufen ist meist unerw¨ unscht, da die relative Ausf¨ uhrungsreihenfolge von vielen Faktoren abh¨ angen kann (z.B. der Ausf¨ uhrungsgeschwindigkeit der Prozessoren, dem Auftreten von Interrupts oder der Belegung der Eingabedaten), die vom Programmierer nur bedingt zu beeinflussen sind. Es entsteht ein nichtdeterministisches Verhalten, da f¨ ur die Ausf¨ uhrungsreihenfolge und das Ergebnis verschiedene M¨ oglichkeiten eintreten k¨ onnen, ohne dass dies vorhergesagt werden kann. Kritischer Bereich Ein Programmst¨ uck, in dem Zugriffe auf gemeinsame Variablen vorkommen, die auch konkurrierend von anderen Threads zugegriffen werden k¨ onnen, heißt kritischer Bereich. Eine fehlerfreie Abarbeitung kann dadurch gew¨ahrleistet werden, dass durch einen wechselseitigen Ausschluss (oder mutual exclusion) jeweils nur ein Thread auf Variablen zugreifen kann, die in einem kritischen Bereich liegen. Programmiermodelle f¨ ur einen gemeinsamen Adressraum stellen Operationen und Mechanismen zur Sicherstellung des wechselseitigen Ausschlusses zur Verf¨ ugung, mit denen erreicht werden kann, dass zu jedem Zeitpunkt nur ein Thread auf eine gemeinsame Variable zugreift. Die grundlegenden Mechanismen, die angeboten werden, sind Sperrmechanismus und Bedingungs-Synchronisation.

3.2 Synchronisations-Mechanismen

49

Sperrmechanismus Zur Vermeidung des Auftretens zeitkritischer Abl¨aufe mit Hilfe eines Sperrmechanismus wird eine Sperrvariable (oder Mutex-Variable von mutual exclusion) s eines speziell vorgegebenen Typs verwendet, die mit den Funktionen lock(s) und unlock(s) angesprochen wird. Vor Betreten des kritischen Bereichs f¨ uhrt der Thread lock(s) zur Belegung der Sperrvariable s aus; nach Verlassen des Programmsegments wird unlock(s) zur Freigabe der Sperrvariable aufgerufen. Nur wenn jeder Prozessor diese Vereinbarung einh¨alt, werden zeitkritische Abl¨ aufe vermieden. Der Aufruf lock(s) hat den Effekt, dass der aufrufende Thread T1 nur dann das dieser Sperrvariablen zugeordnete Programmsegment ausf¨ uhren kann, wenn gerade kein anderer Thread diese Sperrvariable belegt hat. Hat jedoch ein uhrt und die Sperranderer Thread T2 zuvor lock(s) ausgef¨ variable s noch nicht mit unlock(s) wieder freigegeben, so wird Thread T1 so lange blockiert, bis Thread T2 unlock(s) aufruft. Der Aufruf unlock(s) bewirkt neben der Freigabe der Sperrvariablen auch das Aufwecken anderer bzgl. der Sperrvariablen s blockierter Threads. Die Verwendung eines Sperrmechanismus kann also zu einer Sequentialisierung f¨ uhren, da Threads durch ihn nur nacheinander auf eine gemeinsame Variable zugreifen k¨ onnen. Sperrmechanismen sind in Laufzeitbibliotheken wie Pthreads, JavaThreads oder OpenMP auf leicht unterschiedliche Art realisiert. Bedingungs-Synchronisation Bei einer Bedingungs-Synchronisation wird ein Thread T1 so lange blockiert bis eine bestimmte Bedingung eingetreten ist. Das Aufwecken des blockierten Threads kann

50

3 Thread-Programmierung

nur durch einen anderen Thread T2 erfolgen. Dies geschieht sinnvollerweise nachdem durch die Ausf¨ uhrung von Thread T2 diese Bedingung eingetreten ist. Da jedoch mehrere Threads auf dem gemeinsamen Adressraum arbeiten und dadurch zwischenzeitlich wieder Ver¨ anderungen der Bedingung erfolgt sein k¨ onnten, muss die Bedingung durch den uft werden. Die aufgeweckten Thread T1 nochmal u ¨ berpr¨ Bedingungs-Synchronisation wird durch Bedingungsvariablen realisiert; zum Schutz vor zeitkritischen Abl¨aufen wird zus¨ atzlich ein Sperrmechanismus verwendet. Semaphor-Mechanismus Ein weiterer Mechanismus zur Realisierung eines wechselseitigen Ausschlusses ist der Semaphor [19]. Ein Semaphor ist eine Struktur, die eine Integervariable s enth¨alt, auf die zwei atomare Operationen P (s) und V (s) angewendet werden k¨ onnen. Ein bin¨ arer Semaphor kann nur die Werte 0 und 1 annehmen. Werden weitere Werte angenommen, spricht man von einem z¨ ahlenden Semaphor. Die Operation P (s) (oder wait(s)) wartet bis der Wert von s gr¨oßer als 0 ist, dekrementiert den Wert von s anschließend um 1 und erlaubt dann die weitere Ausf¨ uhrung der nachfolgenden Berechnungen. Die Operation V (s) (oder signal(s)) inkrementiert den Wert von s um 1. Der genaue Mechanismus der Verwendung von P und V zum Schutz eines kritischen Bereiches ist nicht streng festgelegt. Eine u ¨ bliche Form ist: wait(s) kritischer Bereich signal(s) Verschiedene Threads f¨ uhren die Operationen P und V auf s aus und koordinieren so ihren Zugriff auf kritische Berei-

3.3 Effiziente und korrekte Thread-Programme

51

che. F¨ uhrt etwa Threads T1 die Operation wait(s) aus um danach seinen kritischen Bereich zu bearbeiten, so wird jeder andere Threads T2 beim Aufruf von wait(s) am Eintritt in seinen kritischen Bereich so lange gehindert, bis T1 die Operation signal(s) ausf¨ uhrt. Monitor Ein abstrakteres Konzept stellt der Monitor dar [31]. Ein Monitor ist ein Sprachkonstrukt, das Daten und Operationen, die auf diese Daten zugreifen, in einer Struktur zusammenfasst. Auf die Daten eines Monitors kann nur durch dessen Monitoroperationen zugegriffen werden. Da zu jedem Zeitpunkt die Ausf¨ uhrung nur einer Monitoroperation erlaubt ist, wird der wechselseitige Ausschluss bzgl. der Daten des Monitors automatisch sichergestellt.

3.3 Effiziente und korrekte Thread-Programme Je nach Applikation kann durch Synchronisation eine enge und komplizierte Verzahnung von Threads entstehen, was zu Problemen wie Leistungseinbußen durch Sequentialisierung oder sogar zu Deadlocks f¨ uhren kann. Anzahl der Threads und Sequentialisierung Die Laufzeit eines parallelen Programms kann je nach Entwurf und Umsetzung sehr verschieden sein. Um ein effizientes paralleles Programm zu erhalten, sollte schon beim Entwurf darauf geachtet werden, dass •

eine geeignete Anzahl von Threads genutzt wird und

52

•

3 Thread-Programmierung

Sequentialisierungen nach M¨ oglichkeit vermieden werden.

Die Erzeugung von Threads bewirkt Parallelit¨at, so dass eine hinreichend große Anzahl von Threads im parallelen Programm vorhanden sein sollte, um alle Prozessorkerne mit Arbeit zu versorgen und so die verf¨ ugbaren parallelen Ressourcen gut auszunutzen. Andererseits sollte die Anzahl der Threads auch nicht zu groß werden, da erstens der Anteil der Arbeit f¨ ur einen einzelnen Thread im Vergleich zum Overhead f¨ ur Erzeugung, Verwaltung und Terminierung des Threads zu gering werden kann, und da zweitens viele Hardwareressourcen (vor allem Caches) von den Prozessorkernen geteilt werden und es so zu Leistungsverlusten bei der Lese/Schreib-Bandbreite kommen kann. Aufgrund der notwendigen Kooperationen zwischen den Threads kann die vorgegebene Parallelit¨ at nicht immer ausgenutzt werden, da zur Vermeidung von zeitkritischen Abl¨ aufen Synchronisations-Mechanismen eingesetzt werden m¨ ussen. Bei h¨ aufiger Synchronisation kann es jedoch dazu kommen, dass immer nur einer oder wenige der Threads aktiv sind, w¨ ahrend alle anderen auf Grund der Synchronisation warten, so dass eine Nacheinanderausf¨ uhrung, also Sequentialisierung, auftritt. Deadlock Die Nutzung von Sperr- und anderen SynchronisationsMechanismen hilft Nichtdeterminismus und zeitkritische Abl¨ aufe zu vermeiden. Die Nutzung von Sperren kann jedoch zu einem Deadlock (Verklemmung) im Anwendungsprogramm f¨ uhren, wenn die Abarbeitung in einen Zustand kommt, in dem jeder Thread auf ein Ereignis wartet, das nur von einem anderen Thread ausgel¨ ost werden kann, der aber auch vergeblich auf ein Ereignis wartet.

3.3 Effiziente und korrekte Thread-Programme

53

Allgemein ist ein Deadlock f¨ ur eine Menge von Aktivit¨ aten dann gegeben, wenn jede der Aktivit¨ aten auf ein Ereignis wartet, das nur durch eine der anderen Aktivit¨aten hervorgerufen werden kann, so dass ein Zyklus des gegenseitigen Aufeinanderwartens entsteht. Ein Beispiel f¨ ur einen Deadlock ist folgende Situation: • •

Thread T1 versucht zuerst Sperre s1 und dann Sperre s2 zu belegen; nach Sperrung von s1 wird er unterbrochen; Thread T2 versucht zuerst Sperre s2 und dann Sperre s1 zu belegen; nach Sperrung von s2 wird er unterbrochen;

Nachdem T1 Sperre s1 und T2 Sperre s2 belegt hat, warten beide Threads auf die Freigabe der fehlenden Sperre durch den jeweils anderen Thread, die nicht eintreten kann. Die Verwendung von Sperrmechanismen sollte also gut geplant sein, um diesen Fall etwa durch eine spezielle Reihenfolge der Sperrbelegung zu vermeiden, vgl. auch [59]. Speicherzugriffszeiten und Cacheeffekte Speicherzugriffszeiten k¨ onnen einen hohen Anteil an der parallelen Laufzeit eines Programms haben. Die Speicherzugriffe eines Programms f¨ uhren zum Transfer von Daten zwischen Speicher und den Caches der Prozessorkerne. Dieser Datentransfer wird durch Lese- und Schreiboperationen der Kerne ausgel¨ ost und kann nicht direkt vom Programmierer gesteuert werden. Zwischen Datenzugriffen verschiedener Prozessorkerne k¨ onnen verschiedene Abh¨ angigkeiten auftreten: Lese-LeseAbh¨ angigkeiten, Lese-Schreib-Abh¨ angigkeiten und SchreibSchreib-Abh¨ angigkeiten. Lesen zwei Prozessorkerne dieselben Daten, so kann dies evtl. ohne Speicherzugriff aus den jeweiligen Caches erfolgen. Die beiden anderen Abh¨angigkeiten l¨ osen Speicherzugriffe aus, da die Daten zwischen

54

3 Thread-Programmierung

den Prozessorkernen ausgetauscht werden m¨ ussen. Die Anzahl der Speicherzugriffe kann reduziert werden, indem der Zugriff der Prozessorkerne auf gemeinsame Daten so gestaltet wird, dass die Kerne auf verschiedene Daten zugreifen. Dies sollte bereits beim Entwurf des parallelen Programms ber¨ ucksichtigt werden. False Sharing, bei dem zwei verschiedene Threads auf verschiedene Daten zugreifen, die jedoch in derselben Cachezeile liegen, l¨ost jedoch ebenfalls Speicheroperationen aus. False Sharing kann vom Programmierer nur schwer beeinflusst werden, da auch eine weit auseinandergezogene Abspeicherung von Daten nicht immer zum Erfolg f¨ uhrt.

3.4 Parallele Programmiermuster Parallele oder verteilte Programme bestehen aus einer Ansammlung von Tasks, die in Form von Threads auf verschiedenen Rechenressourcen ausgef¨ uhrt werden. Zur Strukturierung der Programme k¨ onnen parallele Muster verwendet werden, die sich in der parallelen Programmierung als sinnvoll herausgestellt haben, siehe z.B. [56] oder [45]. Diese Muster geben eine spezielle Koordinationsstruktur der beteiligten Threads vor. Erzeugung von Threads Die Erzeugung von Threads kann statisch oder dynamisch erfolgen. Im statischen Fall wird meist eine feste Anzahl von Threads zu Beginn der Abarbeitung des parallelen Programms erzeugt, die w¨ ahrend der gesamten Abarbeitung existieren und erst am Ende des Gesamtprogramms beendet werden. Alternativ k¨ onnen Threads zu jedem Zeitpunkt der Programmabarbeitung (statisch oder dynamisch) erzeugt

3.4 Parallele Programmiermuster

55

und beendet werden. Zu Beginn der Abarbeitung ist meist nur ein einziger Thread aktiv, der das Hauptprogramm abarbeitet. Fork-Join Das Fork-Join-Konstrukt ist eines der einfachsten Konzepte zur Erzeugung von Threads oder Prozessen [15], das von der Programmierung mit Prozessen herr¨ uhrt, aber als Muster auch f¨ ur Threads anwendbar ist. Ein bereits existierender Thread T1 spaltet mit einem Fork-Aufruf einen weiteren Thread T2 ab. Bei einem zugeordneten Join-Aufruf des Threads T1 wartet dieser auf die Beendigung des Threads T2 . Das Fork-Join-Konzept kann explizit als Sprachkonstrukt oder als Bibliotheksaufruf zur Verf¨ ugung stehen und wird meist in der Programmierung mit gemeinsamem Adressraum verwendet. Die Spawn- und Exit-Operationen der Message-Passing-Programmierung, also der Programmierung mit verteiltem Adressraum, bewirken im Wesentlichen dieselben Aktionen wie die Fork-Join-Operationen. Obwohl das Fork-Join-Konzept sehr einfach ist, erlaubt es durch verschachtelte Aufrufe eine beliebige Struktur paralleler Aktivit¨ at. Spezielle Programmiersprachen und Programmierumgebungen haben oft eine spezifische Auspr¨ agung der beschriebenen Erzeugung von Threads. Parbegin-Parend Eine strukturierte Variante der Thread-Erzeugung wird durch das gleichzeitige Erzeugen und Beenden mehrerer Threads erreicht. Dazu wird das Parbegin-Parend-Konstrukt bereitgestellt, das manchmal auch mit dem Namen Cobegin-Coend bezeichnet wird. Zwischen Parbegin und

56

3 Thread-Programmierung

Parend werden Anweisungen angegeben, die auch Funktionsaufrufe beinhalten k¨ onnen und die Threads zur Ausf¨ uhrung zugeordnet werden k¨ onnen. Erreicht der ausf¨ uhrende Thread den Parbegin-Befehl, so werden die von ParbeginParend umgebenen Anweisungen separaten Threads zur Ausf¨ uhrung zugeordnet. Der Programmtext nach dem Parend-Befehl wird erst ausgef¨ uhrt, wenn alle so gestarteten Threads beendet sind. Die Threads innerhalb des ParbeginParend-Konstrukts k¨ onnen gleichen oder verschiedenen Programmtext haben. Ob und wie die Threads tats¨achlich parallel ausgef¨ uhrt werden, h¨ angt von der zur Verf¨ ugung stehenden Hardware und der Implementierung des Konstrukts ab. Die Anzahl und Art der zu erzeugenden Threads steht meist statisch fest. Auch f¨ ur dieses Konstrukt haben spezielle parallele Sprachen oder Umgebungen ihre spezifische Syntax und Auspr¨ agung, wie z.B. in Form von parallelen Bereichen (parallel sections), vgl. auch OpenMP. SPMD und SIMD Im SIMD- (Single Instruction, Multiple Data) und SPMDProgrammiermodell (Single Program, Multiple Data) wird zu Programmbeginn eine feste Anzahl von Threads gestartet. Alle Threads f¨ uhren dasselbe Programm aus, das sie auf verschiedene Daten anwenden. Durch Kontrollanweisungen innerhalb des Programmtextes kann jeder Thread verschiedene Programmteile ausw¨ ahlen und ausf¨ uhren. Im SIMDAnsatz werden die einzelnen Instruktionen synchron abgearbeitet, d.h. die verschiedenen Threads arbeiten dieselbe Instruktion gleichzeitig ab. Der Ansatz wird auch h¨aufig als Datenparallelit¨at im engeren Sinne bezeichnet. Im SPMDAnsatz k¨ onnen die Threads asynchron arbeiten, d.h. zu einem Zeitpunkt k¨ onnen verschiedene Threads verschiedene Programmstellen bearbeiten. Dieser Effekt tritt ent-

3.4 Parallele Programmiermuster

57

weder durch unterschiedliche Ausf¨ uhrungsgeschwindigkeiten oder eine Verz¨ ogerung des Kontrollflusses in Abh¨angigkeit von lokalen Daten auf. Der SPMD-Ansatz ist z.Zt. einer der popul¨ arsten Ans¨ atze der parallelen Programmierung, insbesondere in der Programmierung mit verteiltem Adressraum mit MPI. Besonders geeignet ist die SPMDProgrammierung f¨ ur Anwendungsalgorithmen, die auf Feldern arbeiten und bei denen eine Zerlegung der Felder die Grundlage einer Parallelisierung ist. Master-Slave oder Master-Worker Bei diesem Ansatz kontrolliert ein einzelner Thread die gesamte Arbeit eines Programms. Dieser Master-Thread entspricht oft dem Hauptprogramm des Anwendungsprogramms. Der Master-Prozess erzeugt mehrere, meist gleichartige Worker- oder Slave-Threads, die die eigentlichen Berechnungen ausf¨ uhren, siehe Abb. 3.6. Diese WorkerThreads k¨ onnen statisch oder dynamisch erzeugt werden. Die Zuteilung von Arbeit an die Worker-Threads kann durch den Master-Thread erfolgen. Die Worker-Threads k¨ onnen aber auch eigenst¨ andig Arbeit allokieren. In diesem Fall ist der Master-Thread nur f¨ ur alle u ¨ brigen Koordinationsaufgaben zust¨ andig, wie etwa Initialisierung, Zeitmessung oder Ausgabe. Client-Server-Modell Programmierstrukturierungen nach dem Client-Server-Prinzip ¨ ahneln dem MPMD-Modell (Multiple Program, Multiple Data). Es stammt aus dem verteilten Rechnen, wo mehrere Client-Rechner mit einem als Server dienenden Mainframe verbunden sind, der etwa Anfragen an eine Datenbank bedient. Parallelit¨ at kann auf der Server-Seite

3 Thread-Programmierung Master

Slave 3

rt tw o An

Client 1

Antwort

ge An f ra

Steuerung

Slave 2

ng eru eu

Slave 1

St

Ste ue r un

g

Server Anfrage

58

An

fra

An

ge

tw

or

t

Client 3

Client 2

Abbildung 3.6. Veranschaulichung Master-Slave-Modell (links) und Client-Server-Modell (rechts).

auftreten, indem mehrere Client-Anfragen verschiedener Clients nebenl¨ aufig oder parallel zueinander beantwortet werden. Eine parallele Programmstrukturierung nach dem Client-Server-Prinzip nutzt mehrere Client-Threads, die Anfragen an einen Server-Thread stellen, siehe Abb. 3.6. Nach Erledigung der Anfrage durch den Server-Thread geht die Antwort an den jeweiligen Client-Thread zur¨ uck. Das ClientServer-Prinzip kann auch weiter gefasst werden, indem etwa mehrere Server-Threads vorhanden sind oder die Threads des Programmes die Rolle von Clients und von Servern u ¨ bernehmen und sowohl Anfragen stellen als auch beantworten k¨ onnen. Pipelining Der Pipelining-Ansatz beschreibt eine spezielle Form der Zusammenarbeit verschiedener Threads, bei der Daten zwischen den Threads weitergereicht werden. Die beteiligten Threads T1 , . . . , Tp sind dazu logisch in einer vorgegebealt die Ausgabe nen Reihenfolge angeordnet. Thread Ti erh¨ von Thread Ti−1 als Eingabe und produziert eine Ausgabe, die dem n¨ achsten Thread Ti+1 , i = 2, . . . , p − 1 als Eingaalt die Eingabe von anderen Probe dient; Thread T1 erh¨ grammteilen und Tp gibt seine Ausgabe an wiederum ande-

3.4 Parallele Programmiermuster

59

re Progammteile weiter. Jeder Thread verarbeitet also einen Strom von Eingaben in einer sequentiellen Reihenfolge und produziert einen Strom von Ausgaben. Somit k¨onnen die Threads durch Anwendung des Pipeline-Prinzips trotz der Datenabh¨ angigkeiten parallel zueinander ausgef¨ uhrt werden. Pipelining kann als spezielle Form einer funktionalen Zerlegung betrachtet werden, bei der die Threads Funktionen eines Anwendungsalgorithmus bearbeiten, die durch ihre Datenabh¨ angigkeiten nicht nacheinander ausgef¨ uhrt werden, sondern auf die beschriebene Weise gleichzeitig abgearbeitet werden k¨ onnen. Das Pipelining-Konzept kann prinzipiell mit gemeinsamem Adressraum oder mit verteiltem Adressraum realisiert werden. Taskpools Ein Taskpool ist eine Datenstruktur, in der die noch abzuarbeitenden Programmteile (Tasks) eines Programms etwa in Form von Funktionen abgelegt sind. F¨ ur die Abarbeitung der Tasks wird eine feste Anzahl von Threads verwendet, die zu Beginn des Programms vom Haupt-Thread erzeugt werden und bis zum Ende des Programms existieren. F¨ ur die Threads ist der Taskpool eine gemeinsame Datenstruktur, auf die sie zugreifen k¨ onnen, um die dort abgelegten Tasks zu entnehmen und anschließend abzuarbeiten, siehe Abb. 3.7. W¨ ahrend der Abarbeitung einer Task kann ein Thread neue Tasks erzeugen und diese in den Taskpool einf¨ ugen. Der Zugriff auf den Taskpool muss synchronisiert werden. Die Abarbeitung des parallelen Programms ist beendet, wenn der Taskpool leer ist und jeder Thread seine Tasks abgearbeitet hat. Der Vorteil dieses Abarbeitungsschemas besteht darin, dass auf der einen Seite nur ein feste Anzahl von Threads erzeugt werden muss und daher der

60

3 Thread-Programmierung

1

Aufwand zur Thread-Erzeugung unabh¨ angig von der Problemgr¨ oße und relativ gering ist, dass aber auf der anderen Seite Tasks dynamisch erzeugt werden k¨ onnen und so auch adaptive und irregul¨ are Anwendungen effizient abgearbeitet werden k¨ onnen.

Daten−

2

bl a A

Produzent 3

e hm

ad

re

re

Th

Konsument 2

puffer

ge

Produzent 2

Konsument 1

a tn En

4

ge

Th

ad

hm e

a bl

3

Th

A

ad

re

re

Produzent 1 En tn a

ad

Th

Ta − sk e ab sk− Ta lag T la en as ge ab sk− me tn k− Ta ah ah Task− tn m en e pool Ta − k ab sk s e Ta lag k− e en Ta lag − tn sk e ab Tas hm ah − a m tn e en

Konsument 3

Abbildung 3.7. Veranschaulichung eines Taskpool-Konzepts (links) und eines Produzenten-Konsumenten-Modells (rechts).

Produzenten-Konsumenten-Modell Das Produzenten-Konsumenten-Modell nutzt ProduzentenThreads und Konsumenten-Threads, wobei die Produzenten-Threads Daten erzeugen, die von Konsumenten-Threads ¨ als Eingabe genutzt werden. F¨ ur die Ubergabe der Daten wird eine gemeinsame Datenstruktur vorgegebener L¨ange als Puffer benutzt, auf die beide Threadtypen schreibend bzw. lesend zugreifen. Die Produzenten-Threads legen die von ihnen erzeugten Eintr¨ age in den Puffer ab, die Konsumenten-Threads entnehmen Eintr¨ age aus dem Puffer und verarbeiten diese weiter, siehe Abb. 3.7. Die Produzenten k¨ onnen nur Eintr¨ age im Puffer ablegen, wenn dieser nicht voll ist. Entsprechend k¨ onnen die Konsumenten nur Eintr¨ age entnehmen, wenn der Puffer nicht leer ist. Zum korrekten Ablauf ist f¨ ur den Zugriff auf die Pufferdatenstruktur eine Synchronisation der zugreifenden Threads erforderlich.

3.5 Parallele Programmierumgebungen

61

3.5 Parallele Programmierumgebungen F¨ ur die parallele Programmierung steht eine Vielzahl von Umgebungen zur Verf¨ ugung. Die verbreitetsten sind: Posix Threads: Posix Threads (auch Pthreads genannt) ist eine portable Thread-Bibliothek, die f¨ ur viele Betriebssysteme nutzbar ist. Mittlerweile ist Pthreads die StandardSchnittstelle f¨ ur Linux und wird auch f¨ ur Unix-Plattformen h¨ aufig genutzt. F¨ ur Windows ist eine Open-Source-Version pthreads-win32 verf¨ ugbar. Die Programmiersprache ist C. Kapitel 4 stellt Pthreads detaillierter vor. Win32/MFC Thread API: Das Win32/MFC API bietet dem Softwareentwickler eine C/C++-Umgebung zur Entwicklung von Windows-Anwendungen. Es werden Mechanismen zur Erzeugung und Verwaltung von Threads zur Verf¨ ugung gestellt sowie Kommunikations- und Synchronisations-Mechanismen. Wir verweisen u.a. auf [3] f¨ ur eine genauere Beschreibung. Threading API f¨ ur Microsoft.NET: Das .NET-Framework bietet umfangreiche Unterst¨ utzung f¨ ur die Programmierung mit Threads f¨ ur die Sprachen C++, Visual Basic, .NET, JScript.NET oder C#. Das Laufzeitsystem wird als Common Language Runtime (CLR) bezeichnet; CLR arbeitet mit einer Zwischencodedarstellung ¨ ahnlich zu Java Bytecode, siehe [3] f¨ ur eine detailliertere Beschreibung. Java-Threads: Die Programmiersprache Java unterst¨ utzt die Erzeugung, Verwaltung und Synchronisation von Threads auf Sprachebene bzw. durch Bereitstellung spezieller Klassen und Methoden. Das Paket java.util.concurrent (ab Java 1.5) stellt eine Vielzahl zus¨ atzlicher Synchronisations-Mechanismen zur Verf¨ ugung. Kapitel 5 enth¨alt eine detailliertere Einf¨ uhrung. OpenMP: OpenMP ist ein API zur Formulierung portierbarer Multithreading-Programme, das Fortran, C und

62

3 Thread-Programmierung

C++ unterst¨ utzt. Das Programmiermodell wird durch eine plattformunabh¨ angige Menge von Compiler-Pragmas und -Direktiven, Funktionsaufrufen und Umgebungsvariablen realisiert, die die Erstellung paralleler Programme verein¨ fachen sollen. Kapitel 6 gibt einen genaueren Uberblick. Message Passing Interface (MPI): MPI [26, 59] wurde als Standard f¨ ur die Kommunikation zwischen Prozessen mit jeweils separatem Adressraum definiert und stellt eine Vielzahl von Kommunikationsoperationen zur Verf¨ ugung, die sowohl Einzeltransfers (mit jeweils zwei Kommunikationspartnern) als auch globale Kommunikationsoperationen wie Broadcast- oder Reduktionsoperationen umfassen. Sprachanbindungen wurden f¨ ur C, C++ und Fortran definiert, es gibt aber auch MPI-Implementierungen f¨ ur Java. Obwohl MPI f¨ ur einen verteilten Adressraum entworfen wurde, kann es im Prinzip auch f¨ ur die Programmierung von Multicore-Prozessoren mit gemeinsamem Adressraum verwendet werden. Dazu wird auf jedem Prozessorkern ein separater Prozess mit privaten Daten gestartet. Der Datenbzw. Informationsaustausch zwischen den Prozessen erfolgt mit MPI-Kommunikationsoperationen, Zugriffe auf den gemeinsamen Speicher und damit auch die damit verbundenen Synchronisationsoperationen entfallen. Im Vergleich zu Threads stellt dies ein v¨ ollig anderes Programmiermodell dar, das je nach Anwendungsprogramm aber durchaus zu einer ¨ ahnlichen Prozessorauslastung wie die Verwendung eines Threadmodells f¨ uhren kann. Das MPI-Modell ist insbesondere f¨ ur solche Programme geeignet, in denen jeder Berechnungsstrom auf einen ihm zuzuordnenden Datenbereich zugreift und relativ selten Daten anderer Datenbereiche braucht. Wir gehen im Folgenden nicht n¨ aher auf MPI ein und verweisen auf [59, 26] f¨ ur eine detaillierte Beschreibung.

4 Programmierung mit Pthreads

Posix Threads (auch Pthreads genannt) ist ein Standard zur Programmierung im Threadmodell mit der Programmiersprache C. Dieser Abschnitt f¨ uhrt in den PthreadsStandard kurz ein; vollst¨ andigere Behandlungen sind in [11, 35, 42, 49, 56] zu finden. Die von einer Pthreads-Bibliothek verwendeten Datentypen, Schnittstellendefinitionen und Makros sind u ¨ blicherweise in der Headerdatei abgelegt, die somit in jedes Pthreads-Programm eingebunden werden muss. Alle Pthreads-Funktionen liefern den Wert 0 zur¨ uck, wenn sie fehlerfrei durchgef¨ uhrt werden konnten. Wenn bei der Durchf¨ uhrung ein Fehler aufgetreten ist, wird ein Fehlercode aus zur¨ uckgegeben. Diese Headerdatei sollte daher ebenfalls eingebunden werden.

4.1 Threaderzeugung und -verwaltung Beim Start eines Pthreads-Programms ist ein Haupt-Thread (main thread) aktiv, der die main()-Funktion des Pro-

64

4 Programmierung mit Pthreads

gramms ausf¨ uhrt. Ein Thread ist in der Pthreads-Bibliothek durch den Typ pthread t dargestellt. Der Haupt-Thread kann weitere Threads erzeugen, indem jeweils die Funktion int pthread create (pthread t *thread, const pthread attr t *attr, void *(*start routine)(void *), void *arg)

aufgerufen wird. Das erste Argument ist ein Zeiger auf ein Datenobjekt vom Typ pthread t. In diesem Argument wird eine Identifikation des erzeugten Threads ablegt, die auch als Thread-Name (thread identifier, TID) bezeichnet wird und mit der dieser Thread in nachfolgenden Aufrufen von Pthreads-Funktionen angesprochen werden kann. Das zweite Argument ist ein Zeiger auf ein Attributobjekt vom Typ pthread attr t, mit dessen Hilfe das Verhalten des Threads (wie z.B. Scheduling, Priorit¨ aten, Gr¨oße des Laufzeitstacks) beeinflusst werden kann. Die Angabe von NULL bewirkt, dass ein Thread mit den Default-Attributen erzeugt wird. Sollen die Attribute abweichend gesetzt werden, muss die Attributdatenstruktur vor dem Aufruf von ¨ pthread create() entsprechend besetzt werden. Ublicherweise reicht die Verwendung der Default-Attribute aus. Das dritte Argument bezeichnet die Funktion start routine(), die der Thread nach seiner Erzeugung ausf¨ uhrt. Diese Funktion hat ein einziges Argument vom Typ void * und liefert einen Wert des gleichen Typs zur¨ uck. Das vierte Argument ist ein Zeiger auf das Argument, mit dem die Funktion uhrt werden soll. start routine() ausgef¨ Um mehrere Argumente an die Startfunktion eines Threads zu u ussen diese in eine Datenstruktur ge¨ bergeben, m¨ packt werden, deren Adresse an die Funktion u ¨ bergeben wird. Sollen mehrere Threads die gleiche Funktion mit unterschiedlichen Argumenten ausf¨ uhren, so sollte jedem

4.1 Threaderzeugung und -verwaltung

65

Thread ein Zeiger auf eine separate Datenstruktur als Argument der Startfunktion mitgegeben werden, um zu vermeiden, dass Argumentwerte zu fr¨ uh u ¨ berschrieben werden oder dass verschiedene Threads ihre Argumentwerte konkurrierend ver¨ andern. Ein Thread wird beendet, indem er die auszuf¨ uhrende Startfunktion vollst¨ andig abarbeitet oder aber die Bibliotheksfunktion void pthread exit (void *valuep) aufruft, wobei valuep den R¨ uckgabewert bezeichnet, der an den aufrufenden Thread oder einen anderen Thread zur¨ uckgegeben wird, wenn dieser mit pthread join() auf die Beendigung des Threads wartet. Wenn ein Thread seine Startfunktion beendet, wird die Funktion pthread exit() implizit aufgerufen, und der R¨ uckgabewert der Startfunktion wird zur¨ uckgegeben. Da nach dem Aufruf von pthread exit() der aufgerufene Thread und damit auch der von ihm verwendete Laufzeitstack nicht mehr existiert, sollte f¨ ur den R¨ uckgabewert valuep keine lokale Variable der Startfunktion oder einer anderen Funktion verwendet werden. Diese werden auf dem Laufzeitstack aufgehoben und k¨onnen nach dessen Freigabe durch einen anderen Thread u ¨ berschrieben werden. Stattdessen sollte eine globale oder eine dynamisch allokierte Variable verwendet werden. Ein Thread kann auf die Beendigung eines anderen Threads warten, indem er die Bibliotheksfunktion int pthread join (pthread t thread, void **valuep)

aufruft, wobei thread die Identifikation des Threads angibt, auf dessen Beendigung gewartet wird. Der aufrufende Thread wird so lange blockiert, bis der angegebene Thread beendet ist. Die Funktion pthread join bietet also eine

66

4 Programmierung mit Pthreads

M¨ oglichkeit der Synchronisation von Threads. Der R¨ uckgabewert des beendeten Threads thread wird dem wartenden Thread in der Variable valuep zur¨ uckgeliefert. Die Pthreads-Bibliothek legt f¨ ur jeden erzeugten Thread eine interne Datenstruktur an, die die f¨ ur die Abarbeitung des Threads notwendigen Informationen enth¨ alt. Diese Datenstruktur wird von der Bibliothek auch nach Beendigung eines Threads aufgehoben, damit ein anderer Thread eine uhren kann. pthread join()-Operation erfolgreich durchf¨ Durch den Aufruf von pthread join() wird auch die interne Datenstruktur des angegebenen Threads freigegeben und kann danach nicht mehr verwendet werden.

4.2 Koordination von Threads Die Threads eines Prozesses teilen sich einen gemeinsamen Adressraum und k¨ onnen daher konkurrierend auf gemeinsame Variablen zugreifen. Um dabei zeitkritische Abl¨aufe zu vermeiden, m¨ ussen die Zugriffe der beteiligten Threads koordiniert werden. Als wichtigste Hilfsmittel stellen Pthreads-Bibliotheken Mutexvariablen und Bedingungsvariablen zur Verf¨ ugung. Eine Mutexvariable bezeichnet eine Datenstruktur des vorgegebenen Typs pthread mutex t, die dazu verwendet werden kann, den wechselseitigen Ausschluss beim Zugriff auf gemeinsame Variablen sicherzustellen. Eine Mutexvariable kann zwei Zust¨ ande annehmen: gesperrt (locked) und ungesperrt (unlocked). Um einen wechselseitigen Ausschluss beim Zugriff auf gemeinsame Datenstrukturen sicherzustellen, m¨ ussen die beteiligten Threads jeweils folgendes Verhalten aufweisen: Bevor ein Thread eine Manipulation der gemeinsamen Datenstruktur startet, sperrt er die zugeh¨ orige Mutexvariable mit einem speziellen Funkti-

4.2 Koordination von Threads

67

onsaufruf. Wenn ihm dies gelingt, ist er der Eigent¨ umer der Mutexvariable und er hat die Kontrolle u ¨ber sie. Nach Beendigung der Manipulation der gemeinsamen Datenstruktur gibt der Thread die Sperre der Mutexvariable wieder frei. Versucht ein Thread die Kontrolle u ¨ ber eine von einem anderen Thread kontrollierte Mutexvariable zu erhalten, wird er so lange blockiert, bis der andere Thread die Mutexvariable wieder freigegeben hat. Die Thread-Bibliothek stellt also sicher, dass jeweils nur ein Thread die Kontrolle u ¨ ber eine Mutexvariable hat. Wenn das beschriebene Verhalten beim Zugriff auf eine Datenstruktur eingehalten wird, wird dadurch eine konkurrierende Manipulation dieser Datenstruktur ausgeschlossen. Sobald jedoch ein Thread die Datenstruktur manipuliert ohne vorher die Kontrolle u ¨ ber die Mutexvariable erhalten zu haben, ist ein wechselseitiger Ausschluss nicht mehr garantiert. Die Zuordnung zwischen einer Mutexvariablen und der ihr zugeordneten Datenstruktur erfolgt implizit dadurch, dass die Zugriffe auf die Datenstruktur durch Sperren bzw. Freigabe der Mutexvariablen gesch¨ utzt werden; eine explizite Zuordnung existiert nicht. Die Lesbarkeit eines Programms kann jedoch dadurch erleichtert werden, dass die Datenstruktur und die f¨ ur deren Kontrolle verwendete Mutexvariable in einer gemeinsamen Struktur gespeichert werden. Mutexvariablen k¨ onnen wie alle anderen Variablen deklariert oder dynamisch erzeugt werden. Bevor eine Mutexvariable benutzt werden kann, muss sie durch Aufruf der Funktion int pthread mutex init (pthread mutex t *mutex, const pthread mutexattr t *attr)

initialisiert werden. F¨ ur attr = NULL wird eine Mutexvariable mit den Default-Eigenschaften zur Verf¨ ugung ge-

68

4 Programmierung mit Pthreads

stellt. Eine statisch deklarierte Mutexvariable mutex kann auch durch die Zuweisung mutex = PTHREAD MUTEX INITIALIZER

mit den Default-Attributen initialisiert werden. Eine initialisierte Mutexvariable kann durch Aufruf der Funktion int pthread mutex destroy (pthread mutex t *mutex)

wieder zerst¨ ort werden. Eine Mutexvariable sollte erst dann zerst¨ ort werden, wenn kein Thread mehr auf ihre Freigabe wartet. Eine zerst¨ orte Mutexvariable kann durch eine erneute Initialisierung weiterverwendet werden. Ein Thread erh¨ alt die Kontrolle u ¨ ber eine Mutexvariable, indem er diese durch Aufruf der Funktion int pthread mutex lock (pthread mutex t *mutex)

sperrt. Wird die angegebene Mutexvariable mutex bereits von einem anderen Thread kontrolliert, so wird der nun die Funktion pthread mutex lock() aufrufende Thread blockiert, bis der momentane Eigent¨ umer die Mutexvariable wieder freigibt. Wenn mehrere Threads versuchen, die Kontrolle u ¨ ber eine Mutexvariable zu erhalten, werden die auf deren Freigabe wartenden Threads in einer Warteschlange gehalten. Welcher der wartenden Threads nach der Freigabe der Mutexvariable zuerst die Kontrolle u ¨ ber diese erh¨alt, kann von den Priorit¨ aten der wartenden Threads und dem verwendeten Scheduling-Verfahren abh¨ angen. Ein Thread kann eine von ihm kontrollierte Mutexvariable mutex durch Aufruf der Funktion int pthread mutex unlock (pthread mutex t *mutex)

4.2 Koordination von Threads

69

wieder freigeben. Wartet zum Zeitpunkt des Aufrufs von pthread mutex unlock() kein anderer Thread auf die Freigabe der Mutexvariable, so hat diese nach dem Aufruf keinen Eigent¨ umer mehr. Wenn andere Threads auf die Freigabe der Mutexvariable warten, wird einer dieser Threads aufgeweckt und Eigent¨ umer der Mutexvariablen. In manchen Situationen ist es sinnvoll, dass ein Thread feststellen kann, ob eine Mutexvariable von einem anderen Thread kontrolliert wird, ohne dass er dadurch blockiert wird. Dazu steht die Funktion int pthread mutex trylock (pthread mutex t *mutex)

zur Verf¨ ugung. Beim Aufruf dieser Funktion erh¨alt der aufrufende Thread die Kontrolle u ¨ ber die Mutexvariable mutex, wenn diese frei ist. Wenn diese zur Zeit von einem anderen Thread gesperrt ist, liefert der Aufruf EBUSY zur¨ uck; dies f¨ uhrt aber nicht wie beim Aufruf von pthread mutex lock() zu einer Blockierung des aufrufenden Threads. Daher kann der aufrufende Thread so lange versuchen, die Kontrolle u ¨ ber die Mutexvariable zu erhalten, bis er erfolgreich ist (spinlock). Beim gleichzeitigen Sperren mehrerer Mutexvariablen durch mehrere Threads besteht die Gefahr, dass Deadlocks auftreten, siehe Kapitel 3. Das Auftreten von Deadlocks kann durch Verwenden einer festen Sperr-Reihenfolge oder das Verwenden einer Backoff-Strategie vermieden werden, vgl. [11, 59]. Mutexvariablen werden in erster Linie dazu verwendet, den wechselseitigen Ausschluss beim Zugriff auf globale Datenstrukturen sicherzustellen. Ist der wechselseitige Ausschluss f¨ ur eine gesamte Funktion sichergestellt, wird sie als thread-sicher bezeichnet. Eine thread-sichere Funktion kann also gleichzeitig von mehreren Threads aufgerufen werden, ohne dass die beteiligten Threads zur Vermeidung

70

4 Programmierung mit Pthreads

von zeitkritischen Abl¨ aufen zus¨ atzliche Operationen beim Funktionsaufruf ausf¨ uhren m¨ ussen. Im Prinzip k¨onnen Mutexvariablen jedoch auch dazu verwendet werden, auf das Eintreten einer Bedingung zu warten, die vom Zustand globaler Datenstrukturen abh¨angt. Dazu verwendet der zugreifende Thread eine oder mehrere Mutexvariablen zum Schutz des Zugriffs auf die globalen Daten und wertet die gew¨ unschte Bedingung von Zeit zu Zeit aus, indem er mit Hilfe der Mutexvariablen gesch¨ utzt auf die entsprechenden globalen Daten zugreift. Wenn die Bedingung erf¨ ullt ist, kann der Thread die beabsichtigte Operation ausf¨ uhren. Diese Vorgehensweise hat den Nachteil, dass der auf das Eintreten der Bedingung wartende Thread die Bedingung evtl. sehr oft auswerten muss, bis diese erf¨ ullt ist, und dabei CPU-Zeit verbraucht (aktives Warten). Um diesen Nachteil zu beheben, stellt der Pthreads-Standard Bedingungsvariablen zur Verf¨ ugung.

4.3 Bedingungsvariablen Eine Bedingungsvariable ist eine Datenstruktur, die es einem Thread erlaubt, auf das Eintreten einer beliebigen Bedingung zu warten. F¨ ur Bedingungsvariablen wird ein Signalmechanismus zur Verf¨ ugung gestellt, der den wartenden Thread w¨ ahrend der Wartezeit blockiert, so dass er keine CPU-Zeit verbraucht, und wieder aufweckt, sobald die angegebene Bedingung erf¨ ullt ist. Um diesen Mechanismus zu verwenden, muss der ausf¨ uhrende Thread neben der Bedingungsvariablen einen Bedingungsausdruck angeben, der die Bedingung bezeichnet, auf deren Erf¨ ullung der Thread wartet. Eine Mutexvariable wird verwendet, um die Auswertung des Bedingungsausdrucks zu sch¨ utzen. Letzteres ist notwendig, da der Bedingungsausdruck in der

4.3 Bedingungsvariablen

71

Regel auf globale Datenstrukturen zugreift, die von anderen Threads konkurrierend ver¨ andert werden k¨ onnen. Bedingungsvariablen haben den Typ pthread cond t. Nach der Deklaration oder der dynamischen Erzeugung einer Bedingungsvariablen muss diese initialisiert werden, bevor sie verwendet werden kann. Dies kann dynamisch durch Aufruf der Funktion int pthread cond init (pthread cond t *cond, const pthread condattr t *attr)

geschehen. Dabei ist cond ein Zeiger auf die Bedingungsvariable und attr ein Zeiger auf eine Attribut-Datenstruktur f¨ ur Bedingungsvariablen. F¨ ur attr = NULL erfolgt eine Initialisierung mit den Default-Attributen. Die Initialisierung kann auch bei der Deklaration einer Bedingungsvariablen durch Verwendung eines Makros erfolgen: pthread cond t cond = PTHREAD COND INITIALIZER.

Eine mit pthread cond init() dynamisch initialisierte Bedingungsvariable cond sollte durch Aufruf der Funktion int pthread cond destroy (pthread cond t *cond) zerst¨ ort werden, wenn sie nicht mehr gebraucht wird, damit das Laufzeitsystem die f¨ ur die Bedingungsvariable abgelegte Information freigeben kann. Statisch initialisierte Bedingungsvariablen m¨ ussen nicht freigegeben werden. Eine Bedingungsvariable muss eindeutig mit einer Mutexvariablen assoziiert sein. Alle Threads, die zur gleichen Zeit auf die Bedingungsvariable warten, m¨ ussen die gleiche Mutexvariable verwenden, d.h. f¨ ur eine Bedingungsvariable d¨ urfen von verschiedenen Threads nicht verschiedene Mutexvariablen verwendet werden. Eine Mutexvariable kann jedoch verschiedenen Bedingungsvariablen zugeordnet werden. Nach dem Sperren der Mutexvariablen mit

72

4 Programmierung mit Pthreads

pthread mutex lock() kann ein Thread durch Aufruf der Funktion int pthread cond wait (pthread cond t *cond, pthread mutex t *mutex)

auf das Eintreten einer Bedingung warten. Dabei bezeichnet cond die Bedingungsvariable und mutex die assoziierte Mutexvariable. Eine Bedingungsvariable sollte nur mit einer Bedingung assoziiert sein, da sonst die Gefahr von Deadlocks oder zeitkritischen Abl¨ aufen vorliegt [11]. Die typische Verwendung hat folgendes Aussehen: pthread mutex lock (&mutex); while (!Bedingung) pthread cond wait (&cond, &mutex); pthread mutex unlock (&mutex);

Die Auswertung der Bedingung wird zusammen mit dem Aufruf von pthread cond wait() unter dem Schutz der Mutexvariablen mutex ausgef¨ uhrt, um sicherzustellen, dass die Bedingung sich zwischen ihrer Auswertung und dem Aufruf von pthread cond wait() nicht durch Berechnungen anderer Threads ver¨ andert. Daher muss durch das Programm auch gew¨ahrleistet sein, dass jeder andere Thread eine Manipulation einer in den Bedingungen auftretenden gemeinsamen Variable mit der gleichen Mutexvariablen sch¨ utzt. •

•

Wenn bei der Ausf¨ uhrung des Programmsegments die angegebene Bedingung erf¨ ullt ist, wird die pthread cond wait()-Funktion nicht aufgerufen, und der ausf¨ uhrende Thread arbeitet nach pthread mutex unlock() das nachfolgende Programm weiter ab. Wenn dagegen die Bedingung nicht erf¨ ullt ist, wird pthread cond wait() aufgerufen mit dem Effekt, dass

4.3 Bedingungsvariablen

73

der ausf¨ uhrende Thread T1 gleichzeitig die Kontrolle u uglich ¨ ber die Mutexvariable freigibt und so lange bez¨ der Bedingungsvariable blockiert, bis er von einem anderen Thread T2 mit einer pthread cond signal()Anweisung aufgeweckt wird, siehe unten. Wird Thread T1 durch diese Anweisung wieder aufgeweckt, versucht er automatisch, die Kontrolle u ¨ ber die Mutexvariable mutex zur¨ uckzuerhalten. Hat bereits ein anderer Thread Kontrolle u ¨ ber die Mutexvariable mutex, so wird der aufgeweckte Thread T1 unmittelbar nach dem Aufwecken so lange bzgl. der Mutexvariable blockiert, bis er diese sperren kann. Erst wenn der aufgeweckte Thread die Mutexvariable erfolgreich gesperrt hat, kann er mit der Abarbeitung seines Programms fortfahren, was zun¨ achst die erneute Abarbeitung der Bedingung ist. Das Programm sollte sicherstellen, dass der blockierte Thread nur dann aufgeweckt wird, wenn die angegebene Bedingung erf¨ ullt ist. Trotzdem ist es sinnvoll, die Bedingung nach dem Aufwecken noch einmal zu u ufen, ¨ berpr¨ da ein gleichzeitig aufgeweckter oder zeitgleich arbeitender Thread, der die Kontrolle u ¨ ber die Mutexvariable zuerst erh¨ alt, die Bedingung oder in der Bedingung enthaltene gemeinsame Daten modifizieren kann und so die Bedingung nicht mehr erf¨ ullt ist. Zum Aufwecken von bzgl. einer Bedingungsvariable wartenden Threads stehen die beiden folgenden Funktionen zur Verf¨ ugung: int pthread cond signal (pthread cond t *cond) int pthread cond broadcast (pthread cond t *cond) Ein Aufruf von pthread cond signal() weckt einen bzgl. der Bedingungsvariable cond wartenden Thread auf, wenn die Bedingung erf¨ ullt ist. Wartet kein Thread, so hat der

74

4 Programmierung mit Pthreads

Aufruf keinen Effekt. Warten mehrere Threads, wird ein Thread anhand der Priorit¨ aten der Threads und der verwendeten Scheduling-Strategie ausgew¨ ahlt. Ein Aufruf der Funktion pthread cond broadcast() weckt alle bzgl. der Bedingungsvariablen cond wartenden Threads auf. Dabei kann aber h¨ ochstens einer dieser Threads die Kontrolle u ¨ber die mit der Bedingungsvariablen assoziierten Mutexvariable erhalten; alle anderen bleiben bzgl. der Mutexvariablen blockiert. Als Variante von pthread cond wait() steht die Funktion int pthread cond timedwait (pthread cond t *cond, pthread mutex t *mutex, const struct timespec *time)

zur Verf¨ ugung. Der Unterschied zu pthread cond wait() besteht darin, dass die Blockierung bzgl. der Bedingungsvariable cond aufgehoben wird, wenn die in time angegebene absolute Zeit abgelaufen ist. In diesem Fall wird die Fehlermeldung ETIMEDOUT zur¨ uckgeliefert. Die Datenstruktur vom Typ timespec ist definiert als struct timespec { time t tv sec; long tv nsec; } wobei tv sec die Anzahl der Sekunden und tv nsec die zus¨ atzliche Anzahl von Nanosekunden der verwendeten Zeitscheiben angibt. Der Parameter time von pthread cond timedwait() gibt eine absolute Tageszeit und kein relatives Zeitintervall an. Eine typische Benutzung ist in Abbildung 4.1 angegeben. In diesem Beispiel wartet der ausf¨ uhrende Thread maximal zehn Sekunden auf das Eintreten der Bedingung. Zur

4.4 Erweiterter Sperrmechanismus

75

pthread mutex t m = PTHREAD MUTEX INITIALIZER; pthread cond t c = PTHREAD COND INITIALIZER; struct timespec time; pthread mutex lock (&m); time.tv sec = time (NULL) + 10; time.tv nsec = 0; while (!Bedingung) if (pthread cond timedwait (&c, &m, &time) == ETIMEDOUT) timed out work(); pthread mutex unlock (&m); Abbildung 4.1. Typische Verwendung von Bedingungsvariablen.

Besetzung von time.tv sec wird die Funktion time aus benutzt. (Der Aufruf time (NULL) gibt die absolute Zeit in Sekunden zur¨ uck, die seit dem 1. Januar 1970 vergangen ist.) Wenn die Bedingung nach zehn Sekunden noch nicht erf¨ ullt ist, wird die Funktion timed out work() ausgef¨ uhrt, und die Bedingung wird erneut u uft. ¨ berpr¨

4.4 Erweiterter Sperrmechanismus Bedingungsvariablen k¨ onnen dazu verwendet werden, komplexere Synchronisationsmechanismen zu implementieren. Als Beispiel hierf¨ ur betrachten wir im Folgenden einen Lese/Schreib-Sperrmechanismus, der als Erweiterung des von Mutexvariablen zur Verf¨ ugung gestellten Sperrmechanismus aufgefasst werden kann. Wird eine gemeinsame Datenstruktur von einer normalen Mutexvariable gesch¨ utzt, so kann zu einem Zeitpunkt jeweils nur ein Thread die gemeinsame Datenstruktur lesen bzw. auf die gemeinsame Datenstruktur schreiben. Die Idee des Lese/Schreib-

76

4 Programmierung mit Pthreads

Sperrmechanismus besteht darin, dies dahingehend zu erweitern, dass zum gleichen Zeitpunkt eine beliebige Anzahl von lesenden Threads zugelassen wird, ein Thread zum Beschreiben der Datenstruktur aber das ausschließliche Zugriffsrecht haben muss. Wir werden im Folgenden eine einfache Variante eines solchen modifizierten Sperrmechanismus beschreiben, vgl. auch [50]. F¨ ur eine komplexere und effizientere Implementierung verweisen wir auf [11, 35]. F¨ ur die Implementierung des erweiterten Sperrmechanismus werden RW-Sperrvariablen (read/write lock variables) verwendet, die mit Hilfe einer Mutex- und einer Bedingungsvariablen wie folgt definiert werden k¨onnen: typedef struct rw lock { int num r, num w; pthread mutex t mutex; pthread cond t cond; } rw lock t; Dabei gibt num r die Anzahl der momentan erteilten Leseberechtigungen und num w die Anzahl der momentan erteilten Schreibberechtigungen an. Letztere hat h¨ochstens den Wert Eins. Die Mutexvariable soll diese Z¨ ahler der Leseund Schreibzugriffe sch¨ utzen. Die Bedingungsvariable regelt den Zugriff auf die neu definierte RW-Sperrvariable. Abbildung 4.2 gibt Funktionen zur Verwaltung von RWSperrvariablen an. Die Funktion rw lock init() dient der Initialisierung einer RW-Sperrvariable vom Typ rw lock t. Die Funktion rw lock rlock() fordert einen Lesezugriff auf die gemeinsame Datenstruktur an. Der Lesezugriff wird nur dann gew¨ ahrt, wenn kein anderer Thread eine Schreibberechtigung erhalten hat. Hat ein anderer Thread eine Schreibberechtigung, wird der anfordernde Thread blockiert, bis die Schreibberechtigung wieder zur¨ uckgegeben wird. Die Funktion rw lock wlock() dient der Anforde-

4.4 Erweiterter Sperrmechanismus

77

int rw lock init (rw lock t *rwl) { rwl->num r = rwl->num w = 0; pthread mutex init (&(rwl->mutex),NULL); pthread cond init (&(rwl->cond),NULL); return 0; } int rw lock rlock (rw lock t *rwl) { pthread mutex lock (&(rwl->mutex)); while (rwl->num w > 0) pthread cond wait(&(rwl->cond),&(rwl->mutex)); rwl->num r ++; pthread mutex unlock (&(rwl->mutex)); return 0; } int rw lock wlock (rw lock t *rwl) { pthread mutex lock (&(rwl->mutex)); while ((rwl->num w > 0) || (rwl->num r > 0)) pthread cond wait(&(rwl->cond),&(rwl->mutex)); rwl->num w ++; pthread mutex unlock (&(rwl->mutex)); return 0; } int rw lock runlock (rw lock t *rwl) { pthread mutex lock (&(rwl->mutex)); rwl->num r --; if (rwl->num r == 0) pthread cond signal (&(rwl->cond)); pthread mutex unlock (&(rwl->mutex)); return 0; } int rw lock wunlock (rw lock t *rwl) { pthread mutex lock (&(rwl->mutex)); rwl->num w --; pthread cond broadcast (&(rwl->cond)); pthread mutex unlock (&(rwl->mutex)); return 0; } Abbildung 4.2. Funktionen zur Verwaltung von RWSperrvariablen (read/write lock variables).

78

4 Programmierung mit Pthreads

rung einer Schreibberechtigung. Diese wird nur gew¨ahrt, wenn kein anderer Thread eine Lese- oder eine Schreibberechtigung erhalten hat. uckgabe Die Funktion rw lock runlock() dient der R¨ einer Leseberechtigung. Sinkt durch die R¨ uckgabe einer Leseberechtigung die Anzahl der lesend zugreifenden Threads auf Null, so wird ein auf eine Schreibberechtigung wartender Thread durch einen Aufruf von pthread cond signal() aufgeweckt. Die Funktion rw lock wunlock() dient entsprechend der R¨ uckgabe einer Schreibberechtigung. Da maximal ein schreibender Thread erlaubt ist, hat nach dieser R¨ uckgabe kein Thread mehr eine Schreibberechtigung, und alle auf einen Lesezugriff wartenden Threads k¨onnen durch pthread cond broadcast() aufgeweckt werden. Die skizzierte Implementierung von RW-Sperrvariablen gibt Lesezugriffen Vorrang vor Schreibzugriffen: Wenn ein Thread T1 eine Leseerlaubnis erhalten hat und Thread T2 auf eine Schreiberlaubnis wartet, erhalten andere Threads auch dann eine Leseerlaubnis, wenn diese nach der Schreiberlaubnis von T2 beantragt wird. Thread T2 erh¨alt erst dann eine Schreiberlaubnis, wenn kein anderer Thread mehr eine Leseerlaubnis beantragt hat. Je nach Anwendung kann es sinnvoll sein, den Schreibzugriffen Vorrang vor Lesezugriffen zu geben, damit die Datenstruktur immer auf dem aktuellsten Stand ist. Wie dies erreicht werden kann, ist in [11] skizziert.

4.5 Implementierung eines Taskpools Eine naheliegende Gestaltung eines Thread-Programms besteht darin, f¨ ur jede abzuarbeitende Aufgabe oder Funktion (also allgemein Task) genau einen Thread zu erzeugen, der diese Task abarbeitet und anschließend wieder zerst¨ort

4.5 Implementierung eines Taskpools

79

wird. Dies kann je nach Anwendung dazu f¨ uhren, dass sehr viele Threads erzeugt und wieder zerst¨ ort werden, was einen nicht unerheblichen Zeitaufwand verursachen kann, insbesondere wenn jeweils pro Task nur wenige Berechnungen auszuf¨ uhren sind. Eine effizientere parallele Implementierung kann mit Hilfe eines Taskpools erreicht werden, siehe auch Kapitel 3. Die Idee eines Taskpools besteht darin, eine Datenstruktur anzulegen, in der die noch abzuarbeitenden Programmteile (Tasks) abgelegt sind. F¨ ur die Abarbeitung der Tasks wird eine feste Anzahl von Threads verwendet, die zu Beginn des Programms vom Haupt-Thread erzeugt werden und bis zum Ende des Programms existieren. F¨ ur die Threads stellt der Taskpool eine gemeinsame Datenstruktur dar, auf die sie zugreifen und die dort abgelegten Tasks entnehmen und anschließend abarbeiten. W¨ahrend der Abarbeitung einer Task kann ein Thread neue Tasks erzeugen und diese in den Taskpool einf¨ ugen. Die Abarbeitung des parallelen Programms ist beendet, wenn der Taskpool leer ist und jeder Thread seine Tasks abgearbeitet hat. Wir beschreiben im Folgenden eine einfache Implementierung eines Taskpools, vgl. [49]. Weitere Implementierungen sind zum Beispiel in [11, 35, 38, 30] beschrieben. Abbildung 4.3 zeigt die Datenstruktur eines Taskpools und die Funktion tpool init() zur Initialisierung des Taskpools. Der Datentyp work t beschreibt eine einzelne Task des Taskpools. Diese Beschreibung besteht aus je einem Zeiger auf die auszuf¨ uhrende Funktion und auf das Argument dieser Funktion. Die einzelnen Tasks sind durch Zeiger next in Form einer einfach verketteten Liste miteinander verbunden. Der Datentyp tpool t beschreibt die gesamte Datenstruktur eines Taskpools. Dabei bezeichnet num thr die Anzahl der f¨ ur die Abarbeitung verwendeten Threads; das Feld threads enth¨ alt Zeiger auf die abarbeitenden Threads. Die Eintr¨ age max size und current size geben die maxi-

80

4 Programmierung mit Pthreads

male bzw. aktuelle Anzahl von eingetragenen Tasks an. Die Zeiger head und tail zeigen auf den Anfang bzw. das Ende der Taskliste. Die Mutexvariable lock wird verwendet, um den wechselseitigen Ausschluss beim Zugriff auf den Taskpool durch die Threads sicherzustellen. Wenn ein Thread versucht, eine Task aus einem leeren Taskpool zu entnehmen, wird er ugt ein bzgl. der Bedingungsvariable not empty blockiert. F¨ Thread einen Task in einen leeren Taskpool ein, wird ein bzgl. der Bedingungsvariable not empty blockierter Thread aufgeweckt. Wenn ein Thread versucht, eine Task in einen vollen Taskpool einzuf¨ ugen, wird er bzgl. der Bedingungsvariable not full blockiert. Entnimmt ein Thread eine Task aus einem vollen Taskpool, wird ein evtl. bzgl. der Bedingungsvariable not full blockierter Thread aufgeweckt. Die Funktion tpool init() in Abbildung 4.3 initialisiert einen Taskpool, indem sie die Datenstruktur allokiert, mit den als Argument mitgelieferten Werten initialisiert und die zur Abarbeitung vorgesehene Anzahl von Threads tpl->threads[i], i=0,...,num thr-1, erzeugt. Jeder dieser Threads erh¨ alt eine Funktion tpool thread() als Startroutine, die einen Taskpool tpl als Argument hat. Die in Abb. 4.4 angegebene Funktion tpool thread() dient der Abarbeitung von im Taskpool abgelegten Tasks. In jedem Durchlauf der Schleife von tpool thread() wird versucht, eine Task vom Anfang der Taskliste des Taskpools zu entnehmen. Wenn der Taskpool zur Zeit leer ist, wird der ausf¨ uhrende Thread bzgl. der Bedingungsvariable not empty blockiert. Sonst wird eine Task wl vom Anfang der Taskschlange entnommen. War der Taskpool vor der Entnahme voll, werden alle Threads, die blockiert sind, weil sie eine Task abzulegen versuchen, mit einer pthread cond broadcast()-Anweisung aufgeweckt. Die Zugriffe von tpool thread auf den Taskpool werden durch die

4.5 Implementierung eines Taskpools

81

typedef struct work { void (*routine)(); void *arg; struct work *next; } work t; typedef struct tpool { int num thr, max size, current size; pthread t *threads; work t *head, *tail; pthread mutex t lock; pthread cond t not empty, not full; } tpool t; tpool t *tpool init (int num thr, int max size) { int i; tpool t *tpl; tpl = (tpool t *) malloc (sizeof (tpool t)); tpl->num thr = num thr; tpl->max size = max size; tpl->current size = 0; tpl->head = tpl->tail = NULL; pthread mutex init (&(tpl->lock), NULL); pthread cond init (&(tpl->not empty), NULL); pthread cond init (&(tpl->not full), NULL); tpl->threads = (pthread t *) malloc(sizeof(pthread t)*num thr); for (i=0; ithreads[i]), NULL, tpool thread, (void *) tpl); return tpl; } Abbildung 4.3. Implementierung eines Taskpools: Datenstrukturen und Initialisierung.

82

4 Programmierung mit Pthreads void *tpool thread (tpool t *tpl) { work t *wl; for( ; ; ) { pthread mutex lock (&(tpl->lock)); while (tpl->current size == 0) pthread cond wait (&(tpl->not empty), &(tpl->lock)); wl = tpl->head; tpl->current size --; if (tpl->current size == 0) tpl->head = tpl->tail = NULL; else tpl->head = wl->next; if (tpl->current size == tpl->max size - 1) pthread cond broadcast (&(tpl->not full)); pthread mutex unlock (&(tpl->lock)); (*(wl->routine))(wl->arg); free(wl); } }

Abbildung 4.4. Funktion tpool thread() zur Taskpoolimplementierung.

Mutexvariable lock gesch¨ utzt. Die Abarbeitung der Funktion routine einer entnommenen Task wl wird danach ausgef¨ uhrt. Diese Abarbeitung kann die Erzeugung neuer Tasks beinhalten, die durch die Funktion tpool insert in den Taskpool tpl eingetragen werden. ugt eiDie Funktion tpool insert() in Abbildung 4.5 f¨ ne Task in den Taskpool ein. Falls der Taskpool voll ist, wird der ausf¨ uhrende Thread bzgl. der Bedingungsvariable not full blockiert. Ist der Taskpool nicht voll, so wird eine Task mit den entsprechenden Daten belegt und an das Ende der Taskschlange geh¨ angt. War diese vor dem Anh¨angen

4.5 Implementierung eines Taskpools

83

void tpool insert (tpool t *tpl, void (*routine)(), void *arg) { work t *wl; pthread mutex lock (&(tpl->lock)); while (tpl->current size == tpl->max size) pthread cond wait (&(tpl->not full), &(tpl->lock)); wl = (work t *) malloc (sizeof (work t)); wl->routine = routine; wl->arg = arg; wl->next = NULL; if (tpl->current size == 0) { tpl->tail = tpl->head = wl; pthread cond signal (&(tpl->not empty)); } else { tpl->tail->next = wl; tpl->tail = wl; } tpl->current size ++; pthread mutex unlock (&(tpl->lock)); } Abbildung 4.5. Funktion tpool insert() zur Taskpoolimplementierung.

leer, wird ein Thread, der bzgl. der Bedingungsvariable not empty blockiert ist, aufgeweckt. Die Manipulationen des Taskpools tpl werden wieder durch die Mutexvariable gesch¨ utzt. Die skizzierte Implementierung eines Taskpools ist insbesondere f¨ ur ein Master-Slave-Modell geeignet, in dem ein unschte Anzahl Master-Thread mit tpool init() die gew¨

84

4 Programmierung mit Pthreads

von Slave-Threads erzeugt, von denen jeder die Funktion tpool thread() abarbeitet. Die zu bearbeitenden Tasks werden entsprechend der zu realisierenden Anwendung definiert und k¨ onnen vom Master-Thread durch Aufruf von tpool insert() in den Taskpool eingetragen werden. Werden bei der Bearbeitung einer Task neue Tasks erzeugt, k¨ onnen diese auch vom ausf¨ uhrenden Slave-Thread eingetragen werden. Die Beendigung der Slave-Threads nach vollst¨ andiger Abarbeitung aller Tasks wird vom MasterThread u ¨bernommen. Dazu werden alle bzgl. der beiden Bedingungsvariablen not empty und not full blockierten Threads aufgeweckt und beendet. Sollte ein Thread gerade eine Task bearbeiten, wird auf die Beendigung der Abarbeitung gewartet bevor der Thread beendet wird.

5 Java-Threads

Die Entwicklung von aus mehreren Threads bestehenden Programmen wird in der objektorientierten Programmiersprache Java auf Sprachebene unterst¨ utzt. Java stellt dazu u.a. Sprachkonstrukte f¨ ur die synchronisierte Ausf¨ uhrung von Programmbereichen bereit und erlaubt die Erzeugung und Verwaltung von Threads durch Verwendung vordefinierter Klassen. Im Folgenden wird die Verwendung von Java-Threads zur Entwicklung paralleler Programme f¨ ur einen gemeinsamen Adressraum kurz vorgestellt, wobei nur auf f¨ ur Threads wesentliche Aspekte eingegangen wird. F¨ ur eine ausf¨ uhrliche Behandlung der Programmiersprache Java verweisen wir auf [22].

5.1 Erzeugung von Threads in Java Jedes ausgef¨ uhrte Java-Programm besteht aus mindestens einem Thread, dem Haupt-Thread. Dieses ist der Thread, der die main()-Methode der Klasse ausf¨ uhrt, die als Startargument der Java Virtual Machine (JVM) angegeben

86

5 Java-Threads

wird. Weitere Benutzer-Threads werden von diesem HauptThread oder von bereits erzeugten Threads explizit erzeugt und gestartet. Dazu steht die vordefinierte Klasse Thread aus dem Standardpaket java.lang zur Verf¨ ugung, die zur Repr¨ asentation von Threads verwendet wird und die Mechanismen und Methoden zur Erzeugung und Verwaltung von Threads bereitstellt. Das Interface Runnable aus java.lang repr¨ asentiert den von einem Thread auszuf¨ uhrenden Code, der in einer run()-Methode zur Verf¨ ugung gestellt wird. F¨ ur die Definition einer run()-Methode, die von einem Thread asynchron ausgef¨ uhrt wird, gibt es zwei M¨ oglichkeiten: das Erben von der Klasse Thread oder die Implementierung des Interfaces Runnable. Erben von der Klasse Thread Bei diesem Vorgehen wird eine neue Klasse NewClass definiert, die von der vordefinierten Klasse Thread erbt und die enthaltene Methode run() mit den Anweisungen des auszuf¨ uhrenden Threads u atzlich enth¨alt ¨ berschreibt. Zus¨ die Klasse Thread eine Methode start(), die einen neuen Thread erzeugt, der dann die Methode run() ausf¨ uhrt. Der neu erzeugte Thread wird asynchron zum aufrufenden Thread ausgef¨ uhrt. Nach Ausf¨ uhrung von start() wird die Kontrolle direkt an den aufrufenden Thread zur¨ uckgegeben. Dies erfolgt evtl. vor der Beendigung des neu erzeugten Threads, so dass erzeugender und erzeugter Thread asynchron zueinander arbeiten. Der neu erzeugte Thread terminiert, sobald seine run()-Methode vollst¨ andig abgearbeitet ist. Dieses Vorgehen ist in Abbildung 5.1 am Beispiel einer Klasse NewClass illustriert, deren main-Methode ein Objekt der Klasse NewClass erzeugt und dessen run()Methode durch Aufruf von start aktiviert wird.

5.1 Erzeugung von Threads in Java

87

import java.lang.Thread; public class NewClass extends Thread { // Vererbung public void run() { // ¨ Uberschreiben von run() der Thread-Klasse System.out.println(”hello from new thread”); } public static void main (String args[]) { NewClass nc = new NewClass(); nc.start(); } }

¨ Abbildung 5.1. Erzeugung eines Threads durch Uberschreiben der run()-Methode der Klasse Thread.

Bei der gerade beschriebenen Methode zur Erzeugung eines Threads muss die neue Klasse von der Klasse Thread erben. Da Java keine Mehrfach-Vererbung zul¨ asst, hat dies den Nachteil, dass die neue Klasse von keiner weiteren Klasse erben kann, was die Entwicklung von Anwendungsprogrammen einschr¨ ankt. Dieser Nachteil der fehlenden Mehrfach-Vererbung wird in Java durch die Bereitstellung von Interfaces ausgeglichen, wof¨ ur im Falle der Klasse Thread das Interface Runnable genutzt wird. Verwendung des Interface Runnable Das Interface Runnable enth¨ alt eine parameterlose run()Methode: public interface Runnable { public abstract void run(); }

88

5 Java-Threads

Die vordefinierte Klasse Thread implementiert das Interface Runnable, d.h. jede von Thread abgeleitete Klasse implementiert ebenfalls das Interface Runnable. Eine neu erzeugte Klasse NewClass kann daher auch direkt das Interface Runnable implementieren anstatt von der Klasse Thread abgeleitet zu werden. Objekte einer solchen Klasse NewClass sind aber keine Threadobjekte, so dass zur Erzeugung eines Threads immer noch ein Objekt der Klasse Thread erzeugt werden muss, das allerdings als Parameter ein Objekt der neuen Klasse NewClass hat. Dazu enth¨alt die Klasse Thread einen Konstruktor public Thread (Runnable target). Bei Verwendung dieses Konstruktors ruft die start()Methode von Thread die run()-Methode des Parameterobjektes vom Typ Runnable auf. Dies wird durch die run()Methode von Thread erreicht, die wie folgt definiert ist: public void run() { if (target != null) target.run(); } Die run()-Methode wird in einem separaten, neu erzeugten Thread asynchron zum aufrufenden Thread ausgef¨ uhrt. Die Erzeugung eines neuen Threads kann somit in drei Schritten erfolgen: (1) Definition einer neuen Klasse NewClass, die Runnable implementiert und f¨ ur die eine run()-Methode definiert wird, die die von dem neu zu erzeugenden Thread auszuf¨ uhrende Anweisungsfolge enth¨ alt; (2) Erzeugung eines Objektes der Klasse Thread mit Hilfe des Konstruktors Thread(Runnable target) und ei¨ nes Objektes der Klasse NewClass sowie Ubergabe dieses Objektes an den Thread-Konstruktor; (3) Aufruf der start()-Methode des Thread-Objektes.

5.1 Erzeugung von Threads in Java

89

Dieses Vorgehen ist in Abbildung 5.2 am Beispiel einer Klasse NewClass illustriert. Ein Objekt dieser Klasse wird dem Konstruktor von Thread als Parameter u ¨ bergeben. import java.lang.Thread; public class NewClass implements Runnable { public void run() { System.out.println(”hello from new thread”); } public static void main (String args[]) { NewClass nc = new NewClass(); Thread th = new Thread(nc); th.start(); // start() ruft nc.run() auf } } Abbildung 5.2. Erzeugung eines Threads mit Hilfe des Interface Runnable und Verwendung einer neuen Klasse NewClass.

Weitere Methoden der Klasse Thread Ein Java-Thread kann auf die Beendigung eines anderen Java-Threads t warten, indem er t.join() aufruft. Durch diesen Aufruf blockiert der aufrufende Thread so lange, bis der Thread t beendet ist. Die join()-Methode wird in drei Varianten zur Verf¨ ugung gestellt: • •

void join(): der aufrufende Thread wird blockiert, bis der angegebene Thread beendet ist; void join(long timeout): der aufrufende Thread wird blockiert; die Blockierung wird aufgehoben, sobald der

90

•

5 Java-Threads

angegebene Thread beendet ist oder wenn die angegebene Zeit timeout abgelaufen ist (Angabe in Millisekunden); void join(long timeout, int nanos): das Verhalten entspricht dem von void join(long timeout); der zus¨ atzliche Parameter erm¨ oglicht eine genauere Angabe des Zeitintervalls durch die zus¨ atzliche Angabe von Nanosekunden.

Wurde der angegebene Thread noch nicht gestartet, findet bei keiner der join()-Varianten eine Blockierung statt. Die Methode boolean isAlive() der Klasse Thread erm¨ oglicht die Abfrage des Ausf¨ uhrungsstatus eines Threads: die Methode liefert true zur¨ uck, falls der angegebene Thread gestartet wurde, aber noch nicht beendet ist. Weder die isAlive()-Methode noch die verschiedenen Varianten der join-Methode haben einen Einfluss auf den Thread, der Ziel des Aufrufes ist. Nur der ausf¨ uhrende Thread ist betroffen. Die Thread-Klasse definiert einige statische Methoden, die den aktuell ausgef¨ uhrten Thread betreffen oder Informationen u ber das Gesamtprogramm liefern. ¨ Da diese Methoden statisch sind, k¨ onnen sie aufgerufen werden, auch wenn kein Objekt der Klasse Thread verwendet wird. Der Aufruf der Methode static Thread currentThread(); liefert eine Referenz auf das Thread-Objekt des aufrufenden Threads. Diese Referenz kann z.B. dazu verwendet werden, nicht-statische Methoden dieses Thread-Objektes aufzurufen. Die Methode static void sleep (long milliseconds);

5.2 Synchronisation von Java-Threads

91

blockiert den ausf¨ uhrenden Thread vor¨ ubergehend f¨ ur die angegebene Anzahl von Millisekunden, d.h. der Prozessor kann einem anderen Thread zugeteilt werden. Nach Ablauf des Zeitintervalls wird der Thread wieder ausf¨ uhrungsbereit und kann wieder einem Prozessor zur weiteren Ausf¨ uhrung zugeteilt werden. Die Methode static void yield(); ist ein Hinweis an die Java Virtual Machine (JVM), dass ein anderer ausf¨ uhrungsbereiter Thread gleicher Priorit¨at dem Prozessor zugeteilt werden soll. Wenn ein solcher Thread existiert, kann der Scheduler der JVM diesen zur Ausf¨ uhrung bringen. Die Anwendung von yield() ist sinnvoll f¨ ur JVM-Implementierungen ohne Scheduling mit Zeitscheibenverfahren, falls Threads langlaufende Berechnungen ohne Blockierungsm¨ oglichkeit ausf¨ uhren. Die Methode static int enumerate (Thread[] th_array); liefert eine Liste aller Thread-Objekte des Programms. Der R¨ uckgabewert gibt die Anzahl der im Parameterfeld th array abgelegten Thread-Objekte an. Mit der Methode static int activeCount(); kann die Anzahl der Thread-Objekte des Programms bestimmt werden. Die Methode kann z.B. verwendet werden, um vor Aufruf von enumerate() die erforderliche Gr¨oße des Parameterfeldes zu ermitteln.

5.2 Synchronisation von Java-Threads Die Threads eines Java-Programms arbeiten auf einem gemeinsamen Adressraum. Wenn auf Variablen durch mehrere Threads zugegriffen werden kann, m¨ ussen also zur Ver-

92

5 Java-Threads

meidung zeitkritischer Abl¨ aufe geeignete Synchronisationsmechanismen angewendet werden. Zur Sicherstellung des wechselseitigen Ausschlusses von Threads beim Zugriff auf gemeinsame Daten stellt Java synchronized-Bl¨ocke und -Methoden zur Verf¨ ugung. Wird ein Block oder eine Methode als synchronized deklariert, ist sichergestellt, dass keine gleichzeitige Ausf¨ uhrung durch zwei Threads erfolgen kann. Eine Datenstruktur kann also dadurch vor konkurrierenden Zugriffen mehrerer Threads gesch¨ utzt werden, dass alle Zugriffe auf die Datenstruktur in synchronized Methoden oder Bl¨ ocken erfolgen. Die synchronisierte Inkrementierung eines Z¨ ahlers kann beispielsweise durch folgende Methode incr() realisiert werden: public class Counter { private int value = 0; public synchronized int incr() { value = value + 1; return value; } } In der JVM wird die Synchronisation dadurch realisiert, dass jedem Java-Objekt implizit eine Mutexvariable zugeordnet wird. Jedes Objekt der allgemeinen Klasse Object besitzt eine solche implizite Mutexvariable. Da jede Klasse direkt oder indirekt von der Klasse Object abgeleitet ist, besitzt somit jedes Objekt eine Mutexvariable. Der Aufruf einer synchronized-Methode bez¨ uglich eines Objektes Ob hat den folgenden Effekt: •

Beim Start der synchronized-Methode durch einen Thread t wird die Mutexvariable von Ob implizit belegt. Wenn die Mutexvariable bereits von einem anderen Thread belegt ist, wird der ausf¨ uhrende Thread t blockiert. Der blockierte Thread wird wieder ausf¨ uhrungs-

5.2 Synchronisation von Java-Threads

•

93

bereit, wenn die Mutexvariable freigegeben wird. Die aufgerufene synchronized-Methode wird nur bei erfolgreicher Sperrung der Mutexvariablen von Ob ausgef¨ uhrt. Beim Verlassen der Methode wird die Mutexvariable von Ob implizit wieder freigegeben und kann damit von einem anderen Thread gesperrt werden.

Damit kann ein synchronisierter Zugriff auf ein Objekt dadurch realisiert werden, dass alle Methoden, die konkurrierend durch mehrere Threads aufgerufen werden k¨onnen, als synchronized deklariert werden. Zur Sicherstellung des wechselseitigen Ausschlusses ist es wichtig, dass nur u utzende Objekt zuge¨ ber diese Methoden auf das zu sch¨ griffen wird. Neben synchronized-Methoden k¨onnen auch synchronized-Bl¨ ocke verwendet werden. Dies ist dann sinnvoll, wenn nur ein Teil einer Methode auf kritische Daten zugreift, eine synchronisierte Ausf¨ uhrung der gesamten Methode aber nicht notwendig erscheint. Bei synchronizedBl¨ ocken erfolgt die Synchronisation meist bez¨ uglich des Objektes, in dessen Methode der synchronized-Block steht. Die obige Methode zur Inkrementierung eines Z¨ahlers kann mit Hilfe eines synchronized-Blocks folgendermaßen formuliert werden: public int incr() { synchronized (this) { value = value + 1; return value; } } Der Synchronisationsmechanismus von Java kann zur Realisierung voll-synchronisierter Objekte, auch atomare Objekte genannt, verwendet werden, die von einer beliebigen Anzahl von Threads ohne Synchronisation zugegriffen werden k¨ onnen. Damit dabei keine zeitkritischen Abl¨aufe entstehen, muss die Synchronisation in der definierenden

94

5 Java-Threads

Klasse enthalten sein. Diese muss folgende Bedingungen erf¨ ullen: • • • •

alle Methoden m¨ ussen synchronized sein, es d¨ urfen keine public-Felder enthalten sein, die ohne Aufruf einer Methode zugegriffen werden k¨onnen, alle Felder werden in Konstruktoren der Klasse konsistent initialisiert, der Zustand der Objekte bleibt auch beim Auftreten von Ausnahmen in einem konsistenten Zustand.

Abbildung 5.3 zeigt das Konzept voll-synchronisierter Objekte am Beispiel einer Klasse ExpandableArray, die eine vereinfachte Version der vordefinierten synchronisierten Klasse java.util.Vector ist, vgl. auch [40]. Die Klasse realisiert ein adaptierbares Feld mit beliebigen Objekten, dessen Gr¨ oße entsprechend der Anzahl abgelegter Objekte wachsen oder schrumpfen kann. Dies ist in der Methode add() realisiert: wird beim Hinzuf¨ ugen eines neuen Elementes festgestellt, dass das Feld data voll belegt ist, wird dieses entsprechend vergr¨ oßert. Dazu wird ein gr¨oßeres Feld neu angelegt und das bisherige Feld wird mit Hilfe der Methode arraycopy() aus der System-Klasse umkopiert. Ohne die Synchronisationsoperationen k¨ onnte die Klasse nicht sicher von mehreren Threads gleichzeitig genutzt werden. Ein Konflikt k¨ onnte z.B. auftreten, wenn zwei Threads zum gleichen Zeitpunkt versuchen, eine add-Operation durchzuf¨ uhren. Auftreten von Deadlocks Die Verwendung voll synchronisierter Klassen vermeidet zwar das Auftreten zeitkritischer Abl¨ aufe, es k¨onnen aber Deadlocks auftreten, wenn Threads bzgl. mehrerer Objekte

5.2 Synchronisation von Java-Threads

95

import java.lang.*; import java.util.*; public class ExpandableArray { private Object[] data; private int size = 0; public ExpandableArray(int cap) { data = new Object[cap]; } public synchronized int size() { return size; } public synchronized Object get(int i) throws NoSuchElementException { if (i < 0 || i >= size) throw new NoSuchElementException(); return data[i]; } public synchronized void add(Object x) { if (size == data.length) { // Feld zu klein Object[] od = data; data = new Object[3 * (size + 1) / 2]; System.arraycopy(od, 0, data, 0, od.length); } data[size++] = x; } public synchronized void removeLast() throws NoSuchElementException { if (size == 0) throw new NoSuchElementException(); data[--size] = null; } } Abbildung 5.3. Beispiel f¨ ur eine voll synchronisierte Klasse.

96

5 Java-Threads pulic class Account { private long balance; synchronized long getBalance() {return balance;} synchronized void setBalance(long v) { balance = v; } synchronized void swapBalance(Account other) { long t = getBalance(); long v = other.getBalance(); setBalance(v); other.setBalance(t); } }

Abbildung 5.4. Beispiel f¨ ur das Auftreten eines Deadlocks.

synchronisiert werden. Dies ist in Abb. 5.4 am Beispiel eines Kontos (Klasse Account) veranschaulicht, bei dem die Methode swapBalance() die Kontost¨ ande austauscht, vgl. auch [40]. Bei der Bearbeitung von swapBalance() ist beim Einsatz von zwei Threads T1 und T2 das Auftreten eines Deadlocks m¨ oglich, wenn ein Thread a.swapBalance(b), der andere Thread b.swapBalance(a) aufruft und die beiden Threads auf unterschiedlichen Prozessorkernen eines Prozessors ablaufen. Der Deadlock tritt bei folgender Abarbeitungsreihenfolge auf: (A) Zeitpunkt 1: Thread T1 ruft a.swapBalance(b) auf und erh¨ alt die Mutexvariable von Objekt a; ur Objekt (B) Zeitpunkt 2: Thread T1 ruft getBalance() f¨ a auf und f¨ uhrt die Funktion aus; (C) Zeitpunkt 2: Thread T2 ruft b.swapBalance(a) auf und erh¨ alt die Mutexvariable von Objekt b;

5.2 Synchronisation von Java-Threads

97

(D) Zeitpunkt 3: Thread T1 ruft b.getBalance() auf und blockiert bzgl. der Mutexvariable von Objekt b; (E) Zeitpunkt 3: Thread T2 ruft getBalance() F¨ ur Objekt b auf auf f¨ uhrt die Funktion aus; (F) Zeitpunkt 4: Thread T2 ruft a.getBalance() auf und blockiert bzgl. der Mutexvariable von Objekt a. Der Ablauf ist in Abb. 5.5 veranschaulicht. Zum Zeitpunkt 4 sind beide Thread blockiert: Thread T1 ist bzgl. der Mutexvariable von b blockiert. Diese ist von Thread T2 belegt und kann nur von Thread T2 freigegeben werden. Thread T2 ist bzgl. der Mutexvariablen von a blockiert, die nur von Thread T1 freigegeben werden kann. Somit warten die beiden Threads gegenseitig aufeinander und es ist ein Deadlock eingetreten. Zeitpunkt 1 2 3 4

Thread T1

Thread T2

a.swapBalance(b) t = getBalance() b.swapBalance(a) Blockierung bzgl. b t = getBalance() Blockierung bzgl. a

Abbildung 5.5. Deadlockablauf zu Abb. 5.4.

Deadlocks treten typischerweise dann auf, wenn unterschiedliche Threads die Mutexvariablen derselben Objekte in unterschiedlicher Reihenfolge zu sperren versuchen. Im Beispiel von Abb. 5.5 versucht Thread T1 zuerst a und dann b zu sperren, Thread T2 versucht das Sperren in umgekehrter Reihenfolge. In dieser Situation kann das Auftreten eines Deadlocks dadurch vermieden werden, dass die beteiligten Threads die Objekte immer in der gleichen Reihenfolge zu sperren versuchen. In Java kann diese

98

5 Java-Threads

dadurch realisiert werden, dass die zu sperrenden Objekte beim Sperren eindeutig angeordnet werden; dazu kann z.B. die Methode System.identityHashCode() verwendet werden, die sich immer auf die Default-Implementierung Object.hashCode() bezieht [40]; diese liefert eine eindeutige Indentifizierung des Objektes. Es kann aber auch eine beliebige andere eindeutige Anordnung der Objekte verwendet werden. Damit kann eine alternative Formulierung von swapBalance() angegeben werden, bei der keine Deadlocks auftreten k¨ onnen, vgl. Abb. 5.6. Die neue Formulierung enth¨alt ¨ auch eine Alias-Uberpr¨ ufung, so dass die Operation nur ausgef¨ uhrt wird, wenn unterschiedliche Objekte beteiligt sind. Die Methode swapBalance() ist jetzt nicht mehr als synchronized deklariert. public void swapBalance(Account other) { if (other == this) return; else if (System.identityHashCode(this) < System.identityHashCode(other)) this.doSwap(other); else other.doSwap(this); } protected synchronized void doSwap(Account other) { long t = getBalance(); long v = other.getBalance(); setBalance(v); other.setBalance(t); } Abbildung 5.6. Deadlockfreie Realisierung von swapBalance() aus Abb. 5.4.

5.2 Synchronisation von Java-Threads

99

Bei der Synchronisation von Java-Methoden sollten ein paar Hinweise beachtet werden, die die resultierenden Programme effizienter und sicherer machen: •

•

•

•

•

•

Synchronisation ist teuer. Synchronisierte Methoden sollten daher nur dann verwendet werden, wenn die Methoden von mehreren Threads aufgerufen werden kann und wenn innerhalb der Methoden gemeinsame Objektdaten ver¨ andert werden k¨ onnen. Wenn f¨ ur die Anwendung sichergestellt ist, dass eine Methode jeweils nur von einem Thread zugegriffen wird, kann eine Synchronisation zur Erh¨ ohung der Effizienz vermieden werden. Die Synchronisation sollte auf die kritischen Bereiche beschr¨ ankt werden, um so die Zeit der Sperrung von Objekten zu reduzieren. Anstelle von synchronizedMethoden sollten bevorzugt synchronized-Bl¨ocke verwendet werden. Die Mutexvariable eines Objektes sollte nicht zur Synchronisation nicht zusammenh¨ angender kritischer Bereiche verwendet werden, da dies zu unn¨ otigen Sequentialisierungen f¨ uhren kann. Einige Java-Klassen sind bereits intern synchronisiert; Beispiele sind Hashtable, Vector und StringBuffer. Zus¨ atzliche Synchronisation ist f¨ ur Objekte dieser Klassen also u ussig. ¨ berfl¨ Ist f¨ ur ein Objekt Synchronisation erforderlich, sollten die Daten in private oder protected Feldern abgelegt werden, damit kein unsynchronisierter Zugriff von außen m¨ oglich ist; alle zugreifenden Methoden m¨ ussen synchronized sein. Greifen Threads eines Programms in unterschiedlicher Reihenfolge auf Objekte zu, k¨ onnen Deadlocks durch Verwendung der gleichen Sperr-Reihenfolge verhindert werden.

100

5 Java-Threads

Die Realisierung von synchronized-Bl¨ ocken mit Hilfe der impliziten Mutexvariablen, die jedem Objekt zugeordnet sind, funktioniert f¨ ur alle Methoden, die bzgl. eines Objektes aktiviert werden. Statische Methoden einer Klasse werden jedoch nicht bzgl. eines speziellen Objektes aktiviert und eine implizite Objekt-Mutexvariable existiert daher nicht. Nichtsdestotrotz k¨ onnen auch statische Methoden als synchronized deklariert werden. Die Synchronisation erfolgt dann u ¨ ber die Mutexvariable des zugeh¨origen Klassenobjektes der Klasse java.lang.Class, das f¨ ur die Klasse, in der die statische Methode deklariert wird, automatisch erzeugt wird. Statische und nicht-statische synchronized Methoden einer Klasse verwenden also unterschiedliche Mutexvariablen f¨ ur die Synchronisation. Eine statische synchronized-Methode kann sowohl die Mutexvariable der Klasse als auch die Mutexvariable eines Objektes der Klasse sperren, indem sie eine nicht-statische Methode bzgl. eines Objektes der Klasse aufruft oder ein Objekt der Klasse zur Synchronisation nutzt. Dies wird in Abb. 5.7 anhand der Klasse MyStatic illustriert. Eine nicht-statische synchronized Methode kann durch den Aufruf einer statischen synchronized Methode ebenfalls neben der Objekt-Mutexvariablen auch die KlassenMutexvariable sperren. F¨ ur eine Klasse Cl kann die Synchronisation bzgl. der Klassen-Mutexvariablen auch direkt durch synchronized (Cl.class) erfolgen.

{

/* Rumpf*/ }

5.3 Signalmechanismus in Java

101

public class MyStatic { public static synchronized void staticMethod(MyStatic obj) { // hier wird die Klassen-Sperre verwendet obj.nonStaticMethod(); synchronized(obj) { // zus¨ atzliche Verwendung der Objekt-Sperre } } public synchronized void nonStaticMethod() { // Verwendung der Objekt-Sperre } } Abbildung 5.7. Synchronisation von statischen Methoden.

5.3 Signalmechanismus in Java In manchen Situationen ist es sinnvoll, dass ein Thread auf das Eintreten einer anwendungsspezifischen Bedingung wartet. Sobald die Bedingung erf¨ ullt ist, f¨ uhrt der Thread eine festgelegte Aktion aus. So lange die Bedingung noch nicht erf¨ ullt ist, wartet der Thread darauf, dass ein anderer Thread durch entsprechende Berechnungen das Eintreten der Bedingung herbeif¨ uhrt. In Pthreads konnten f¨ ur solche Situationen Bedingungsvariablen eingesetzt werden. Java stellt u ¨ ber die Methoden wait() und notify(), die in der vordefinierten Klasse Object deklariert sind, einen ¨ahnlichen Mechanismus zur Verf¨ ugung. Diese Methoden stehen somit f¨ ur jedes Objekt zur Verf¨ ugung, da jedes Objekt direkt oder indirekt von der Klasse Object abgeleitet ist. Beide Methoden d¨ urfen nur innerhalb eines synchronizedBlocks oder einer synchronized-Methode aufgerufen werden. Das typische Verwendungsmuster f¨ ur wait() ist:

102

5 Java-Threads

synchronized (lockObject) { while (!Bedingung) { lockObject.wait(); } Aktion; } Der Aufruf von wait() blockiert den aufrufenden Thread so lange, bis er von einem anderen Thread per notify() aufgeweckt wird. Die Blockierung bewirkt auch die Freigabe der impliziten Mutexvariable des Objektes, bzgl. der der Thread synchronisiert. Damit kann diese Mutexvariable von einem anderen Thread gesperrt werden. Ein Aufruf von notify() weckt einen bez¨ uglich des zugeh¨origen Objektes blockierten Thread auf. Der aufgeweckte Thread wird ausf¨ uhrungsbereit und versucht, die Kontrolle u ¨ ber die implizite Mutexvariable des Objektes wieder zu erhalten. Erst wenn ihm dies gelingt, f¨ uhrt er die nach Eintreten der Bedingung durchzuf¨ uhrende Aktion aus. Wenn dies nicht gelingt, blockiert der Thread bzgl. der Mutexvariablen, bis diese von dem Thread, der sie gesperrt hat, wieder freigegeben wird. Die Arbeitsweise von wait() und notify() ¨ahnelt der Arbeitsweise von Pthread-Bedingungsvariablen und den Operationen pthread cond wait() und pthread cond signal(), vgl. Seite 70. Die Implementierung von wait() und notify() erfolgt mit Hilfe einer impliziten Warteliste, in der f¨ ur jedes Objekt eine Menge von wartenden Threads gehalten wird. Die Warteliste enth¨ alt jeweils die Threads, die zum aktuellen Zeitpunkt durch Aufruf von wait() bez¨ uglich dieses Objektes blockiert wurden. Nicht in der Warteliste enthalten sind die Threads, die blockiert wurden, weil sie auf Zuteilung der impliziten Mutexvariable des Objektes warten. Welcher der Threads in der impliziten Warteliste beim Aufruf von notify() aufgeweckt wird, ist von der Java-Sprachspezifikation nicht festgelegt. Mit Hilfe der Me-

5.3 Signalmechanismus in Java

103

thode notifyAll() werden alle in der Warteliste abgelegten Threads aufgeweckt und ausf¨ uhrungsbereit; die analoge Pthreads-Funktion ist pthread cond broadcast(). Ebenso wie notify() muss notifyAll() in einem synchronizedBlock oder einer synchronized-Methode aufgerufen werden. Produzenten-Konsumenten-Muster Der Java-Signalmechanismus kann etwa zur Realisierung eines Produzenten-Konsumenten-Musters mit Ablage- bzw. Entnahmepuffer fester Gr¨ oße verwendet werden, in den Produzenten-Threads Datenobjekte ablegen und aus dem Konsumenten-Threads Daten zur Weiterverarbeitung entnehmen k¨ onnen. Abbildung 5.8 zeigt eine threadsichere Implementierung eines Puffermechanismus mit Hilfe des Java-Signalmechanismus, vgl. auch [40]. Beim Erzeugen eines Objektes vom Typ BoundedBufferSignal wird ein Feld array vorgegebener Gr¨ oße capacity erzeugt, das als Puffer dient. Zentrale Methoden der Klasse sind put() zur Ablage eines Datenobjektes im Puffer und take() zur Entnahme eines Datenobjektes aus dem Puffer. Ein Pufferobjekt kann in einem der drei Zust¨ ande voll, teilweise voll und leer sein, siehe ¨ 5.9 f¨ ur eine Veranschaulichung der Uberg¨ ange zwischen den Zust¨ anden. Die Zust¨ ande sind durch folgende Bedingungen charakterisiert: Zustand

Bedingung

put take m¨ oglich m¨oglich voll size == capacity nein ja teilweise voll 0 < size < capacity ja ja leer size == 0 ja nein

104

5 Java-Threads

public class BoundedBufferSignal { private final Object[] array; private int putptr = 0; private int takeptr = 0; private int numel = 0; public BoundedBufferSignal (int capacity) throws IllegalArgumentException { if (capacity