Multithreading - Nebenläufigkeit und Systemarchitektur - Proactor basiertes Render Management

Multithreading und Systemarchitektur

Nebenläufigkeit und Systemarchitektur

Warum sollte sich Software-Systemarchitektur mit Nebenläufigkeit und paralleler Verarbeitung beschäftigen?

Moores Gesetz (Gordon Moore,1960) besagt das die Leistung der Prozessoren sich alle 18 Monate verdoppeln wird. Dieses Gesetz steht heute unter geänderten Vorzeichen. So setzen die Prozessor Hersteller weniger auf Beschleunigung und komplexere Prozessoren, sondern setzen mehrere CPUs in einem Chip ein. Die Gründe sind vielseitig, wie Hitze, Leistungsaufnahme oder physikalische Grenzen, d.h. weniger Energieverbrauch. Die neuen Mehrkernprozessoren sind kostengünstiger in der Herstellung und effizienter im Betrieb. Mehrkernprozessoren finden sich heute bei Servern, Desktop-PCs, Mobiltelefonen oder PDA. 

Dieser Entwicklung muss in der Softwareentwicklung Rechnung getragen werden. Oft sind die Anwendungen für Single Prozessor Umgebungen geschrieben, alle Berechnungsschritte und Prozesse laufen serialisiert ab. In den vergangenen Jahren wurden einige grundlegende Architekturmuster und Idiome für Mehrprozessor Architektur entwickelt. Ein Beispiel ist das Proactor-Architekturmuster welches in INSPIRE-XNA, einer eigenentwickelten Grafikengine, angewendet wird und weiter unten vorgestellt wird, zuvor einige Definitionen.

Nebenläufigkeit ist nach (Buschmann, et al., 2000 S. 19) definiert:

„Der Begriff Nebenläufigkeit (engl. Concurrency) bezeichnet eine »Familie« von Verfahrensweisen und Mechanismen, die es einem oder mehreren Ablauffäden (Thread) oder Prozessen ermöglichen, die ihnen zugeteilten Aufgaben gleichzeitig auszuführen.“

Dabei definiert sich ein Prozess wie folgt:

„Ein Prozess ist eine Ansammlung von Betriebsmitteln, die es erlaubt, Programminstruktionen auszuführen.“(Buschmann, et al., 2000 S. 19)

In der IT-Fachsprache wird der englische Begriff »Multithreading« verwendet, wenn die Programausführung mit mehreren Ablauffäden realisiert ist. Ein (Programm-) Ablauffaden (engl. Thread) ist wie folgt definiert:

„Ein Ablauffaden ist eine konkrete Folge von Programmschritten, die innerhalb eines Prozesses ausgeführt werden. Ein Ablauffaden verwaltet ebenfalls eine Reihe von Betriebsmitteln. Diese umfassen neben einem Befehlszähler auch einen Laufzeitkellerspeicher zur Verwaltung von Funktionsaufrufen, verschiedene Register sowie ablauffadenspezifische Daten.“(Buschmann, et al., 2000 S. 19).

David W. Bustard (Bustard, 1990) beschreibt Nebenläufigkeit und parallele Programme. Danach hat ein  »Nebenläufiges Programm« bei der Ausführung mehr als einen Handlungsfaden (Kontrollfluss). Er spricht in diesem Fall von »logischer Gleichzeitigkeit«. Dazu gehört das die Programme „potentiell“ parallel ausgeführt werden können oder auf einer CPU nacheinander, z.B. im Zeitscheibenverfahren.

Nach Bustard wird ein »Paralleles Programm« auf mehreren Prozessoren gleichzeitig ausgeführt. Dabei spricht man von „Daten-Parallelität“ wenn jedes Programm einen Teil der Daten zugewiesen bekommt. Bekommt jedes Programm einen Teil der Aufgaben zugewiesen liegt eine „Kontroll-Parallelität“ vor. Laufen die Programme gleichzeitig auf mehreren Rechnern oder CPU-Kernen ab spricht man von „physikalischer Gleichzeitigkeit“(Bustard, 1990)

Welche Vorteile hat ein Framework wie INSPIRE-XNA durch nebenläufige Methoden?

Zum einen verspricht die bessere Auslastung der Mehrkernprozessoren Leistungsvorteile bei der Programmausführung. Die Bereitstellung dedizierter Threads für die IO-Verarbeitung kann Latenzzeiten überbrücken. Zum einen können in Echtzeit Benutzereingaben verarbeitet werden zum anderen können parallele Threads mit weiteren Aufgaben betraut werden. Ein weiteres Beispiel sind Ausgaben auf der Grafikhardware, die IO-Operationen zwischen CPU, Hauptspeicher sowie GPU und Grafikartenspeicher stellen oft einen Flaschenhals dar, der mittels nebenläufiger Programmierung umgangen werden kann.

Multithreading Architektur - Proactor basiertes Render Management

Wie oben beschrieben können nebenläufige Verfahrensweisen für interaktive, grafische Anwendungen eingesetzt werden und große Vorteile bringen. Am Beispiel des Proactor Architekturmusters soll dieses verdeutlicht werden.

Situation und Anforderung: Die Hauptanwendungsschleife des INSPIRE-XNA Framework ruft bei jedem Durchlauf eine Update und eine Draw Methode (Rendering) auf. Die Update Methode ist für die Aktualisierung und das Fortschreiten der Objektzustände zuständig. Dazu kann unter anderem die Eingabedatenverarbeitung, physikalische Berechnungen, Kollisionsabfragen der Welt Objekte und anderes mehr gehören. Die Update Aktivitäten fasse ich unter dem Begriff »Simulation« zusammen.

Die Draw Methode (Rendering) ist dabei für die Aufbereitung der grafischen Daten, die Ausführung von Effekten (Shader) und die Darstellung auf der Grafikkarte zuständig. Dazu gehört auch die Übertragung (IO) der Daten zwischen Hauptspeicher der CPU und Grafikkartenspeicher der GPU. Bei dem Zugriff auf die Grafikkartenhardware kann es zu Wartezeiten kommen, trotzdem soll im Hintergrund der Update Mechanismus weiter Eingabedaten entgegennehmen und die Simulation aktualisieren. Wie können nun Update- und Rendering so entworfen werden, das Latenzzeiten überbrückt und eine optimale Auslastung des/der Prozessoren erreicht wird?

Die INSPIRE-XNA Architektur verwendet hierzu zwei (Haupt-) Threads, einen Thread für das Rendering und einen weiteren Thread um die Simulation fortzuführen. Jedem Thread steht ein aktueller Nachrichten Puffer (engl. Message Buffer) zur Verfügung, welcher die aktuellen Objektzustände speichert. Innerhalb der Update Routine wird ein Puffer gefüllt und mit aktuellen Informationen (z.B. Position, Orientierung) der Welt Objekte gefüllt.

Der Render Thread nimmt seinen Puffer und bringt die in im enthaltenen Welt Objekte zur Anzeige. Nach dem aktuellen Zeichenvorgang tauschen Update und Render Thread ihre Puffer aus. Im Idealfall läuft dieser Vorgang mit einer Frequenz von > 30 Hz, damit das Rendering eine störungsfreie (d.h. ohne Aussetzer bei dem Bildaufbau) Wiedergabe von dynamischen Szenen bieten kann.

Um den Anforderungen Rechnung zu tragen wurde das Proactor Muster (Buschmann, et al., 2000 S. 237) für diesen Bereich angewandt. Das Proactor Muster wird vorrangig dort angewandt wo eine einzelne Komponente zahlreiche Anfragen parallel verarbeiten muss und eine hohe Performance gewährleistet werden muss. 

Im INSPIRE-XNA Framework ist diese Komponente das Update Management. Die Verwendung des Musters soll eine optimale Prozessorauslastung und ein Minimum an Latenzzeiten gewährleisten, da auf teure Kontextwechsel einer reinen Thread basierten Anwendung verzichtet wird.

Bild 28: Sequenzdiagramm Proactor 

Der Ablauf im Einzelnen:

1. Dabei initiiert ein Update Handler (auch engl. Proactive Initiator) eine asynchrone Operation, d.h. die Update Methoden werden asynchron gestartet und mit einer Callback Adresse versehen.
2. Die asynchrone Methode wird in einem Hintergrund Thread ausgeführt und die bearbeiteten Daten in einem Zwischenspeicher abgelegt.
3. Die Callback Adresse führt zu einem Ereignis-Demulitplexer (auch engl. Completion Dispatcher) Objekt.
4. Dieser Demultiplexer erhält dann den Callback Ausruf nachdem die asynchrone Operation beendet wurde.
5. Im Anschluss kann der Ereignis-Demultiplexer ein Completion Handler aufrufen, welcher die Ergebnisdaten aus dem Zwischenspeicher verarbeitet oder weiterleitet.

Bild 29: Klassendiagramm Proactor Pattern

Das Sequenzdiagramm des Update-Prozesses (Bild 30) zeigt wie eine Instanz des AsynchOperationProzessor einen asynchronen Methodenaufruf für ein Update durchführt. Im Hintergrund verarbeitet das .NET Framework, in Verbindung mit dem Betriebssystem, die aufgerufene Operation in einem eigenen Thread. Nach Ausführung wird die AsynchOperationProzessor.CallbackMethode() angesprungen und das Ergebnis in eine Instanz der CompletionEventQueue abgelegt.

Bild 30: Sequenzdiagramm DoubleBuffering Update Prozess Proactor

Die Proactor Instanz läuft in einem eigenen Thread und liest die CompletionEventQueue aus. Jeder CompletionEvent hat einen Bezeichner (Handle), welches auf einen CompletionEventHandler verweist. Dieser wird instanziiert und ausgeführt. Dieser Aufbau ermöglicht den hierarchischen Prozessaufbau von nebenläufigen Prozessen.

Autor: Friedhelm Feisel

 

Literaturverzeichnis

Alexander, Christopher. 1977. A Pattern Language. New York : Oxford University Press, 1977.

Balzert, Helmut. 2000. Lehrbuch der Softwaretechnik : Basiskonzepte und Requirements-Engineering. Heidelberg : Spektrum, Akad. Verl., 2000. Vol. 2. Aufl.

Bartle, Richard. 2003. Designing Virtual Worlds. s.l. : New Riders, 2003.

Beck, Kent. 1996. Smalltalk Best Practice Patterns. Upper Saddle River  : Prentice Hall, 1996.

Buschmann, Frank, et al. 2001. A System of Patterns: Pattern-Oriented Software Architecture: 1. West Sussex PO19 IUD. England : John Wiley & Sons, 2001.

Buschmann, Frank, et al. 1998. Pattern-orientierte Software-Architektur. Bonn : Addison-Wesley, 1998.

—. 2000. Pattern-orientierte Software-Architektur. Bonn : Addison-Wesley, 2000.

Bustard, David W. 1990. Concepts of Concurrent Programming. s.l. : Software Engineering Institute, Carnegie Mellon University, Curriculum Module SEI-CM-24, 1990.

Carter, Chad. 2008. Microsoft XNA Unleashed:Graphics and Game Programming XBox 360 and Windows. Indianapolis, Indiana : SAMS, 2008. 0-672-32964-6.

Center, Microsoft News. 2004. Microsoft: Next Generation of Games Starts With XNA. Microsoft News Center. [Online] 03 24, 2004. [Cited: 09 01, 2010.] https://www.microsoft.com/presspass/press/2004/mar04/03-24xnalaunchpr.mspx.

Coplien, J. 1994. Advanced C++ Programming Styles and Idioms. s.l. : Addison-Wesley, 1994.

Coplien, James. 1992. Advanced C++ Programming Styles and Idioms. 1992.

Eberly, David H. 2005. 3D game engine architecture - Engineering real-time applications with Wild Magic. Boston : Morgan Kaufman Publishers, 2005.

Endrei, Mark, et al. 2004. Patterns: Service-Oriented Architecture and Web Services. IBM RedBooks. s.l. : International Business Machines Corporation, 2004.

Fowler, Martin. 1997. Analysis Patterns. s.l. : Addison-Wesley, 1997.

Gamma, Erich, et al. 1995. Elemente wiederverwendbarer objektorientierter Software. s.l. : Addison Wesley in Pearson Education Deutschland GmbH, 1995.

—. 2009. Entwurfsmuster : Elemente wiederverwendbarer objektorientierter Software. s.l. : Addison Wesley in Pearson Education Deutschland GmbH, 2009. Vol. Ausgabe 1. Aufl.

Grootjans, Riemer. 2009. Xna 3.0 game programming recipes : a problem-solution approach. Berkeley, CA : Apress, 2009.

IEEE Standard 610.12-1990. IEEE Standard 610.12-1990.

J.Coplien, D.Schmidt, et.al. (eds.),. 1995. Pattern Languages of Program design: (PLoP 1-4). s.l. : Addison-Wesley, 1995.

Krzysztof Cwalina, Brad Abrams. 2009. Framework design guidelines : conventions, idioms, and patterns for reusable .NET libraries. Upper Saddle River, NJ  : Addison-Wesley, 2009. Vol. 2nd ed.

M.Shaw and Garlan, D. 1993. An Introduction to software architecture. In Advances in Software Engineering and Knowledge Engineering. Singapore : World Scientific Publishing Company, 1993.

Mary Shaw, David Garlan. 1996. Software Architecture: Perspectives on an Emerging. s.l. : Prentice Hall, 1996.

MSDN 2010, Microsoft. MSDN Library. MSDN. [Online] Microsoft. [Cited: 09 18, 2010.] http://msdn.microsoft.com/en-us/library/ff729722(VS.85).aspx.

Oestereich, Bernd. 2009. Analyse und Design mit UML 2.1 - Objektorientierte Softwareentwicklung. Oldenbourg : s.n., 2009. Vol. 9. aktualisierte und erw. Aufl.

Oliver Vogel, Ingo Arnold, Arif Chughtai, Markus Völter. 2009. Software-Architektur. Grundlagen - Konzepte - Praxis. Heidelberg : Spektrum Akademischer Verlag, 2009. Vol. 2. Auflage.

Ortega-Arjona, Jorge Luis. 2009. Patterns for parallel software design. Hoboken, NJ  : John Wiley, 2009.

Perry, Dewayne E. and L.Wolf, Alexander. 1992. Foundations for the Study of Software. s.l. : ACM SIGSOFT Software Engineering Notes, 1992.

Schmidt, Douglas C. 2002. Pattern-orientierte Software-Architektur: Muster für nebenläufige und vernetzte Objekte. Heidelberg : dpunkt-Verl., 2002. Vol. 1. Auflg.

The Free Lunch Is Over, A Fundamental Turn Toward Concurrency in Software. Sutter, Herb. 2005. 30(3), s.l. : Dr. Dobb's Journal, 2005, Vol. 30(3).

Thilmany, Christian. 2003. .NET Patterns: Architecture, Design, and Process . s.l. : Addison Wesley, 2003.

Timothy G. Mattson, Beverly A. Sanders, Berna L. Massingill. 2005. Patterns for parallel programming. Boston : Addison-Wesley, 2005.

Zhou, Marc Andre. 2009. Parallel Computing in .NET : Multicore-Programmierung von .Net 2.0 bis 4.0. Frankfurt, M. : Entwickler.press, 2009.