Alle Fäden in der Hand

Thread Programmierung unter Linux in C und C++ (Teil 2)

Wolfgang Schreiner
Die Thread-Programmierung in C nach dem POSIX Standard P1003.1c ist vor allem für die Systemprogrammierung bzw. für die Erstellung von Client/Server-Anwendungen geeignet. Unter Ausnutzung der Eigenschaften von C++ ist es möglich, wesentlich abstrakterere Programmiermodelle für Threads zu implementieren. Insbesondere können Threads streng getypte Schnittstellen erhalten und mittels automatischer Speicherbereinigung alle belegten Resourcen wieder freigeben.
Parallele Programmiermodelle auf Basis von C++ sind zum Teil schon längere Zeit verfügbar [1] aber weit weniger abstrakt als dies für viele Anwendungen wünschenswert wäre. Im zweiten Teil dieses Artikels zur Thread-Programmierung stellen wir die selbst entwickelte C++ Klassenbibliothek RT++ [3] vor, die eine abstrakte Thread-Schnittstelle auf verschiedenen Workstations und Multiprozessor-Systemen implementiert. Insbesondere ist diese Bibliothek auch unter Linux verfügbar (tatsächlich wurde sie zu großen Teilen darauf entwickelt); sobald die zur Zeit im Alpha-Test befindliche Multiprozessor-Version des Linux-Kernels verfügbar ist, laufen mit RT++ entwickelte Programme damit auch unter Linux "echt" parallel.

Das Ausführungsmodell

Bevor wir auf die Programmierung in RT++ eingehen, müssen wir uns ein ungefähres Bild vom Ausführungsmodell machen, auf dem diese Klassenbibliothek beruht:

Die Unterscheidung zwischen aktivierten und nicht-aktivierten Threads ergibt sich aus den unterschiedlichen Resourcen-Anforderungen: Noch nicht aktivierte Threads sind um eine Größenordnung kleiner (im Bereich von 100 bytes) als bereits aktivierte Threads (10 KB und mehr); damit können Zehntausende Threads im nicht-aktivierten Zustand gehalten werden, aber nur wenige Hunderte aktivierte Threads. Das Laufzeit-System hält deshalb Threads so lange im nicht aktivierten Zusatand, als die Prozesse mit genügend aktiven Threads ausgelastet sind.

Im Unterschied zu Thread-Implementierungen im Kern des Betriebssystems werden in RT++ Threads auf der Benutzer-Ebene realisiert (siehe Teil 1 des Artikels) und zwischen verschiedenen Prozessen zur Ausführung geschaltet. Da aber jeder Prozeß einen eigenen Adreßraum besitzt, müssen sowohl die Threads selbst als auch alle Objekte, auf denen die Threads operieren im gemeinsamen Heap gehalten werden.

Ein Programm-Beispiel

Zum Einstieg in die Programmierung mit der RT++ Bibliothek beschreiben wir ein kleines Programm zum Sortieren von Feldern durch eine parallele Variante des QuickSort Algorithmus. Das Programm unterteilt das Feld in zwei Teile und startet zwei Threads zum parallelen Sortieren dieser beiden Teile. Die Threads wenden den Algorithmus rekursiv so lange an (und erzeugen damit neue Threads), bis die Feldlänge zu klein wird und das Feld sequentiell sortiert werden kann.
  // Header Files
  #include <rt++.h>     // RT++ header file
  #include <iostream.h> // C++ header file

  // Registrierung der Typen
  Atom(int);            // int ist Atom
  Atom(float);          // float ist Atom
  Ref(Array<float>);    // Array ist Referenz

  // Registrierung der Threads
  ThreadRes(int);       // Ergebnis-Typ
  ThreadArg3(A, int, Array<float>, int, int);

  // teile a[l..r] durch e in a[l..m0], a[m0..m1], a[m1..r]
  void partition(Array<float> a, int l, int r, 
    float e, int *m0, int *m1);

  // sortiere a[l..r]
  int qsort(Array<float> a, int l, int r)
  {
    if (r-l < 1000) return(sort(a, l, r));

    int m0, m1;
    partition(a, l, r, a[(l+r)/2], &m0, &m1);

    Thread3<int, Array<float>, int, int> t0(qsort, a, l, m0);
    Thread3<int, Array<float>, int, int> t1(qsort, a, m1, r);

    return(Wait(t0)+Wait(t1));
  }

  // RT++ Hauptprogramm
  int qmain(int argc, char *argv[]) 
  {
    int L = atoi(argv[1]);
    for (int i = 0; i < 1000; i++)
    {
      Array<float> a(L);
      for (int j = 0; j < L; j++)
        a[j] = rand();
      int n = qsort(a, 0, L);
    }
    return(0);
  }

  // C++ Hauptprogramm
  int main(int argc, char *argv[]) 
  {
    RT_Argument rt_arg;      // RT++ Argumente
    RT_Result rt_res;        // RT++ Ergebnis
    rt_arg.proc = 3;         // 3 Prozesse
    rt_arg.memory = 1000000; // 1 MB gemeinsamer Speicher
    rt_arg.heap = 100000;    // 100 KB Heap zu Beginn
    rt_arg.blocks = 4;       // 4 Blocks/Prozess
    rt_arg.stack = 15000;    // 15 KB Stack/Thread
    rtarg.verbose = 1;       // Drucke Statistik
    exit(rt_main(qmain, argc, argv, rt_arg, &rt_res));
  }
Das Programm ist aus folgenden Bestandteilen aufgebaut: Wird das Programm übersetzt und gestartet, liefert es eine Ausgabe der folgenden Art:
------------------------------------------------------------------------------
RT++ 1.0 (C) 1996 Wolfgang Schreiner <Wolfgang.Schreiner@risc.uni-linz.ac.at>
proc: 3, mem: 1000000, heap: 100032, blocks: 12, stack: 5000
------------------------------------------------------------------------------
RT++ GC 1 (1360 ms): 8 blocks with 42560 bytes in 30 (+ 0) ms.
RT++ GC 2 (1820 ms): 11 blocks with 64112 bytes in 20 (+ 0) ms.
RT++ GC 3 (2640 ms): 9 blocks with 53456 bytes in 20 (+ 0) ms.
RT++ GC 4 (3200 ms): 3 blocks with 15984 bytes in 30 (+ 0) ms.
RT++ GC: less than 25008 bytes heap (1 block per process) free.
RT++ GC: increase heap by 100032 bytes.
RT++ GC 5 (4670 ms): 7 blocks with 33520 bytes in 50 (+ 0) ms.
...
RT++ GC 13 (13170 ms): 41 blocks with 243984 bytes in 70 (+ 0) ms.
------------------------------------------------------------------------------
RT++ execution
        Return code:    0
        Real time(ms):  16650
        Proc time(ms):  16620
        All procs(ms):  46900
RT++ garbage collections
        Number:         13
        Increments:     3
        Waiting(ms):    30
        Collecting(ms): 570
        Blocks:         167
        Bytes:          880464
------------------------------------------------------------------------------
Die Kopfzeilen werden beim Start der RT++ Laufzeitumgebung ausgegeben und geben die für die Initialisierung verwendeten Parameter an. Jede während der Programmausführung ausgeführte Speicherbereinigung druckt Information über deren Dauer und über die Größe des wiedergewonnenen Speichers aus. Ist zu wenig freier Speicher vorhanden oder dieser zu fragmentiert für die weitere Verwendung, kann der Heap auch vergrößert werden. Bei Beendigung der RT++ Laufzeitumgebung wird Status-Information über das Programm und über die durchgeführten Speicherbereinigungen ausgegeben.

Daß obiges Beispiel auf einem Multiprozessor ausgeführt wurde zeigt sich darin, daß die real time um fast ein Drittel kleiner als die gesamte Ausführungszeit aller Prozesse war; die Prozesse liefen also auf mehreren Prozessoren echt parallel.

Die Bibliothek

RT++ stellt im wesentlichen eine Bibliothek von Datentypen für die parallele Programmierung zu verfügung. Zwei dieser Datentypen, Thread und Array haben wir im vorigen Beispiel schon kurz vorgestellt. Im folgenden wollen wir eine etwas ausführlichere Darstellung geben: Alle Typen, die aus obigen Typ-Konstruktoren und C++ Basis-Typen (int, float, char, ...) aufgebaut sind, sind zulässige RT++ Typen und können ihrerseits als Argumente für weitere RT++ Typ-Konstruktionen bilden. Insbesondere können auch Threads selbst als Argumente und Ergebnise anderer Threads dienen oder können als Objekte in Feldern, Listen und Zeiger-Objekten gespeichert werden. Alle derartig aufgebauten Objekte (auch Threads) werden von der automatischen Speicherbereinigung verwaltet und deren Speicher freigegeben, sobald die Objekte nicht mehr referenziert werden.

Weitere Programm-Beispiele

Um den von RT++ ermöglichten Programmierstil zu veranschaulichen, skizzieren wir parallele Lösungen des Problems der Multiplikation langer Zahlen, wobei jede Zahl durch ein Feld von Ziffern repräsentiert ist. Das Programm beruht auf dem Schul-Algorithmus für Multiplikation, indem je eine Thread jede Ziffer der zweiten Zahl mit der ersten Zahl multipliziert und die so parallel bestimmten Ergebnisse summiert werden.

Der Kern eines solchen Programms könnte in RT++ folgendermaßen aussehen:

  typedef char Digit;
  typedef Array<Digit> Number;

  Number mult(Number a, Number b)
  {
    int lb = Length(b);
    List< Thread<Number> > l;
    for (int i = 0; i < lb; i++)
      {
        Thread2<Number, Number, Digit> t(prod, a, b[i]);
        l.cons(t, l); // l = Cons(t, l);
      }
    int n = 2*lb-1;
    for (int j = 0; j < n-2 ; j += 2)
      {
        Thread<Number> ta(Head(l)); 
        l.tail();     // l = Tail(l);
        Thread<Number> tb(Head(l)); 
        l.tail();     // l = Tail(l);
        Thread2<Number, Thread<Number>, Thread<Number> > t(sum, ta, tb);
        l.cons(t, l); // l = Cons(t, l);
      }
    return(Wait(Head(l)));
  }
Diese Lösung verwendet eine Liste l vom Typ List<Thread<Number>> die beliebige Threads vom Ergebnis-Typ Number aufnehmen kann (der Typ Thread<Number> ist zuweisungs-kompatibel zu jedem Typ Threadn<Number, ...>). Das Programm läuft in der ersten Schleife über alle Ziffern der Zahl b, start eine neue Thread für die Ausführung von prod(a, b[i]) und speichert die Thread in der Liste l.

In der zweiten Schleife läuft das Programm über alle Threads in dieser Liste, nimmt je zwei Threads heraus und startet eine neue Thread für die Ausführung von sum(ta, tb), die die Ergebnisse der beiden Threads t_a und t_b addieren soll. Die neue Thread wird ebenfalls wieder in diese Liste gestellt (um einen balanizerten Thread-Baum zu erzeugen, sollte die neue Thread allerdings nicht wie oben dargestellt am Anfang sondern am Ende der Liste eingefügt werden). Das Ergebnis der letzten Thread ist das Gesamtergebnis des Programms.

Ein wesentlicher Punkt in obigem Programm ist, daß nicht auf das Ergebnis der prod Threads gewartet wird, um die sum Threads zu erzeugen. Vielmehr erhalten die sum Threads die prod Threads als Argumente und sind für die Synchronisation selbst verantwortlich:

  Number sum(Thread<Number> ta, Thread<Number> tb)
  {
    Number a = Wait(ta); 
    Number b = Wait(tb);
    return(sum(a,b));
  }
Unter Verwendung von Bags kann unsere Lösung noch eleganter gestaltet werden:
  Number mult(Number a, Number b)
  {
    int lb = Length(b);
    int n = 2*lb-1;
    ThreadBag<Number> bag(n);
    for (int i = 0; i < lb; i++)
      {
        ThreadBag2<Number, Number, Digit>(bag, prod, a, b[i]);
      }
    for (int j = 0; j < n-2 ; j += 2)
      {
        ThreadBag2<Number, ThreadBag<Number>, int>(bag, sum, bag, j); 
      }
    return(Wait(bag, n-1));
  }
Das Programm verwendet an stelle einer Liste eine Bag (der optionale Parameter n in der Deklaration gibt die Maximalgröße der Bag an und wird für die Optimierung des Zugriffs verwendet). In der ersten Schleife werden die prod Threads erzeugt und in die Bag gestellt, in der zweiten Schleife werden die sum Threads erzeugt und ihr die Bag und der Index der entsprechenden Argument-Threads als Argument übergeben:
  Number sum(ThreadBag<Number> a, int j)
  {
    Number a = Wait(bag, j);
    Number b = Wait(bag, j+1);
    return(sum(a,b));
  }
Jede sum Thread wartet damit nicht auf die Ergebnisse eines bestimmten Thread-Paars sondern auf die Ergebnisse der Threads, die in Position j bzw. j+1 "ins Ziel gekommen sind". Das Programm ist damit sehr viel abstrakter und eleganter als die erste Lösung.

Diese Beispiele illustrieren sehr schön den Programmierstil, der von RT++ vorgeschlagen wird: Threads sind Objekte, die benutzt und herumgereicht werden können wie alle anderen Arten von Objekten. Es ist für den Erzeuger einer Thread nicht notwendig, Synchronisationsabhängigkeiten selbst aufzulösen; er kann diese Aufgabe auch an die Threads übertragen, die die jeweiligen Ergebnisse benötigen. Außerdem kümmert sich das Programm nicht selbst um Anlegen und Freigeben von Resourcen; diese Aufgabe wird vom darunterliegenden Speicherverwaltungs-System gelöst. Der daraus resultierende Programmierstil ähnelt in gewisser Weise dem funktionalen Datenfluß-Stil der parallelen Programmierung.

Die Implementierung

Die RT++ Klassenbibliothek wurde zum wesentlichen Teil auf einem Linux-Rechner mit dem GNU G++ compiler und der QuickThreads Library [2] implementiert. Für den verwendeten Mechanismus zur automatischen Speicherbereinigung ist es wichtig, daß der Typ jedes durch Zeiger referenzierten Objekts bekannt ist. Die Bibliothek beruht daher ganz wesentlich auf dem C++ template Konstrukt zur Implementierung generischer Datentypen.

Der Aufbau von RT++ Threads ist in folgendem Bild skizziert:

Nicht aktivierte Threads unterscheiden sich von obigem Bild nur durch das Fehlen des Stacks, der erst bei der Aktivierung angelegt wird.

Der Mechanismus zur Speicherbereinigung beruht auf einem parallelisierten mark&sweep Verfahren bei dem im ersten Schritt alle erreichbaren Objekte markiert werden und im zweiten Schritt der Heap nach nicht markierten Objekten durchsucht wird, deren Speicher freigegeben werden kann. Dieses Verfahren setzt allerdings voraus, daß einerseits die Menge der Zeiger bekannt ist, über die alle im Heap angelegten Objekte direkt oder indirekt erreicht werden können (root set), und daß andererseits die Menge der in einem Objekt enthaltenen Zeiger auf andere Objekte bestimmt werden kann.

RT++ verwendet eine Methode, bei der jede Variable mit Hilfe des entsprechenden Klassen-Konstruktors bei ihrer Erzeugung ihre Stack-Adresse und ihren Typ registriert. Die "root set" eines Programs ist damit der Stack der Haupt-Thread; alle Objekte (und alle Threads), die nicht über diese Thread referenzierbar sind, können nichts zum Ergebnis beitragen und ihr Speicher kann freigegeben werden.

Bei der registierten Typ-Information handelt es sich um die scan-Function des jeweiligen Typs, einer Funktion, die alle von der jeweiligen Variable aus erreichbaren Zeiger durchläuft und die referenzierten Objekte markiert. Während der ersten Phase der Speicherbereinigung wird bei der Markierung einer Thread für alle auf dem Stack angelegten Variablen die jeweilige scan-Funktion aufgerufen.

Jeder RT++ Typ-Konstruktor besitzt eine solche scan-Funktion; die Deklaration Ref(T) ist der Aufruf eines Makros, der im wesentlichen in die Initialisierung

  Type<T>::scan = T::scan;
der statischen Komponente scan der Klasse Type<T> aufgelöst wird. Eine Deklaration Atom(T) dagegen sagt, daß Typ T atomar ist und eine solche Funktion nicht besitzt; die Auflösung lautet daher
  Type<T>::scan = 0;
und wird von der Speicherbereinigung entsprechend behandelt. Der GNU G++ Compiler unterstützt leider noch nicht das Konzept der "Initializer" für statische Mitglieder einer Template-Klasse, damit würden die lästigen Ref Deklarationen überflüssig.

Bisher haben wir noch nicht erklärt, wo Adressen und Typen der von einer Thread auf ihrem Stack angelegten Variablen eigentlich registriert werden. Die Lösung ist ganz einfach: es wird dafür ein zweiter Stack verwendet, der am anderen Ende des für den Thread-Stack angelegten Speicherbereiches liegt und in die entgegengesetzte Richtung wächst. Für jede Referenz-Variable, die auf dem Stack angelegt wird, werden zwei Zeiger auf diesem "Spiegel-Stack" registriert: die Adresse der Variable und die scan-Funktion des entsprechenden Typs. Das folgende Bild veranschaulicht diese Idee:

Die eigentliche Speicherbereinigung wird von allen Prozessen des RT++ Laufzeitsystems parallel vorgenommen: in der ersten Phase werden referenzierte Stacks (und die von Variablen auf diesen Stacks referenzierten Objekte) parallel markiert, in der zweiten Phase werden die Blöcke, in die der Heap unterteilt ist, parallel nach unmarkierten Objekten untersucht und deren Speicher freigegeben. Ist nach der Speicherbereinigung der freie Speicher zu gering oder zu fragmentiert, wird ein neuer Cluster von Blöcken aus dem gemeinsamen Speicher allokiert und dem Heap hinzugefügt.

Fazit

Ziel der Entwicklung von RT++ war es, eine Schnittstelle zur Verfügung zu stellen, die ein elegantes, sicheres und effizientes parallels Programmieren unter C++ erlaubt. Die vergleichbar hohe Abstraktionsstufe mit Unterstützung von automatischer Speicherbereinigung erlaubt es, sich eher auf das wesentliche einer parallelen Anwendung zu konzentrieren, als dies vielleicht bei anderen Paketen der Fall ist. Dennoch ist das System vergleichsweise klein und überschaubar. Die freie Verfügbarkeit des Quellcodes, die leichte Portierbarkeit, und die einfache Einbettung in C++ Programme sollten es erlauben, RT++ zur Basis eigener Entwicklungen zu machen.

Die Klassenbibliothek ist unter der GNU Library Public License auf einer Vielzahl von Architekturen, Workstations und Multiprozessoren, verfügbar.

Nähere Informationen finden sich auf der entsprechenden Web Seite [3].

Literatur und Software

 
[1]
Peter A. Buhr, Glen Ditchfield, and Richard A. Stroobosscher. µC++: Concurrency in the Object-Oriented Language C++, 1992. Software und Dokumentation, ftp://plg.uwaterloo.ca/pub/uSystem.

 

[2]
David Keppel. Tools and Techniques for Building Fast Portable Thread Packages, 1993. Software (QuickThreads) ftp://ftp.cs.washington.edu/pub/qt-002.tar.gz, Dokumentation ftp://ftp.cs.washington.edu/tr/1993/05/UW-CSE-93-05-06.PS.Z.

 

[3]
Wolfgang Schreiner. RT++ -- Higher Order Threads for C++, 1996. Software und Dokumentation http://www.risc.uni-linz.ac.at/software/rt++.

Wolfgang Schreiner ist am Research Institute for Symbolic Computation (RISC-Linz) der Johannes Kepler Universität Linz tätig und beschäftigt sich mit Parallelem und Verteilten Rechnen für Symbolische Anwendungen. Zu erreichen ist er unter Wolfgang.Schreiner@risc.uni-linz.ac.at.