netzstaub

Über das Weblog von Chris Double bin ich heute auf die Multithreading Library Protothreads gestossen, die wirklich sehr interessant ist. Protothreads bietet “stackless”-Threads, die man einsetzen kann, um eine Art Poor-Man’s Multithreading zu haben. Stackless Threads haben keinen eigenen Stack, und müssen explizit geschedulet werden, verbrauchen dafür aber nur 2 Bytes im RAM, und lassen sich mit normalen C-Konstrukten implementieren. Die meisten anderen C-Multithreading-Libraries verwenden dafür entweder Assembler Code, um z.B. den Prozessorstatus zu sichern oder den Stack zu wechseln, oder andere sehr “weirde” C-Konstrukte wie z.B. longjmp und co.

Anwendungsbeispiel

In der Dokumentation zu Protothreads geben die Entwickler Adam Dunkels und Oliver Schmidt, der ihm geholfen hat, 3 Beispiele an. Das einfachste dieser Beispiele ist ein einfacher Thread, der auf das Kippen eines Flags wartet, dann kurz nochmal wartet, und einen anderen Thread umkippt. Code sieht dann so aus:

PT_THREAD(timed_event_thread(struct pt *pt))
{
  PT_BEGIN(pt);

  while(1) {
    flag1 = 0
    PT_WAIT_UNTIL(pt, flag1);
    timer_set(&timer, TIMEOUT);
    PT_WAIT_UNTIL(pt, timer_expired(&timer));
    flag2 = 1;
  }

  PT_END(pt);
}

Lokale Continuations



Protothreads benutzt als unterliegende Struktur “lokale Continuations”, um das Multithreading zu implementieren. Klassischerweise ist eine Continuation ein Konstrukt, dass die “Zukunft” einer Berechnung festhält, wenn ich z.B. die Berechnung “foobar(a) + blorg(b)” habe, dann ist die Zukunft der Berechnung foobar(a) in dem Kontext die Berechnung “+ blorg(b)”. D.h, wenn foobar(a) ausgeführt wurde, muss das Ergebnis mit blorg(b) addiert werden, um die Berechnung abzuschliessen. Diese Continuation kann man in Sprachen wie Scheme z.B. explizit manipulieren, und z.B. irgendwo speichern. Nachdem eine Continuation gespeichert ist, kann man ganz was anderes machen (z.B. zu einem anderen Thread wechseln), und später dann die gespeichert Continuation wieder aufrufen, und so praktisch einen Thread-wechsel implementieren. Ich hoffe, dass ich das mit einem kleinen Bildchen veranschaulichen kann, ich hab mit Continuations auch echt lange gekämpft, bis ich das gepeilt habe (und so 100% sicher bin ich mir da immer noch nicht :).

Hier sieht man, wie foobar(a) + blorg(b) ausgewertet wird. In Grün sind die Schritte, die ausgeführt worden sind, in Lila die dazugehörige Continuation. Wenn man jetzt diese Continuation abspeichert, und später wieder aufruft, hat man Multithreading. Bei lokalen Continuations existiert kein Stack per Continuation, so dass die Ergebnisse, die hier in Grün sind, explizit in globale Variable abgespeichert werden müssen, sonst gehen sie beim Threadswitch verloren. Protothreads bietet 2 Implementierungen von lokalen Continuations in C. Die eine missbraucht das switch Konstrukt, die auf der C-Koroutinen-Implementierung von Simon Tatham, die andere benutzt die GCC-Compiler Extension für “Labels as Values“. Über die Implementierung von lokalen Continuations werde ich in einem weiteren Posting bloggen. Eine wichtige Beschränkung der Switch-implementierung ist, dass innerhalb der lokalen Continuation kein switch-Konstrukt verwendet werden darf. Die Switch-Implementierung basiert auf so eine Art Trick wie Duff’s device.

Protothreads

Wie lokale Continuations sind auch Protothreads in mehreren C-Makros implementiert. Ein Protothread besteht trivialerweise aus einer lokalen Continuation, über die die “Berechnungszukunft” des Threads festgehalten wird, wenn ein Threadswitch stattfindet. Protothreads werden mit der Makro PT_THREAD deklariert. Das Makro PT_INIT initialisiert die lokale Continuation von dem Thread, und muss vor dem Aufrufen des Protothreads ausgeführt werden. Ein Protothread ist also eine einfache C-Funktion, er kann sich auch nicht über mehrere Funktionen verteilen, weil das die Implementierung der lokalen Continuations nicht zulässt. Also, es ist immer noch möglich aus einem Protothread andere Funktionen aufzurufen, nur dürfen diese Funktionen keinen Thread-Voodoo machen (keinen Threadswitch auslösen).

Innerhalb der Protothreadfunktion muss das Makro PT_BEGIN benutzt werden (und ihr Pendant PT_END). PT_BEGIN ruft dann die gespeicherte Zukunft des Threads auf. Alles was vor dem Einsatz von PT_BEGIN geschieht wird bei jedem Schedulen des Protothreads ausgeführt. Wenn man in das Headerfile “pt.h” guckt, sieht man, das PT_THREAD eigentlich eine Funktion mit Returntyp char deklariert. In diesem char wird der Zustand des Threads zurückgegeben, also entweder PT_THREAD_WAITING (der Thread wartet auf irgendwas, und will irgendwann mal wieder aufgerufen werden, um weiter zu machen), oder PT_THREAD_EXITED (der Thread ist fertig). Die Implementierung von PT_WAIT_UNTIL (lass einen anderen Thread laufen, solange eine Bedingung nicht erfüllt ist) ist dann relativ einfach:

#define PT_WAIT_UNTIL(pt, condition)	        \
  do {						\
    LC_SET((pt)->lc);				\
    if(!(condition)) {				\
      return PT_THREAD_WAITING;			\
    }						\
  } while(0)

Hier wird die jetzige Zukunft der Berechnung gespeichert (mit LC_SEC), die Bedingung geprüft, und wenn diese falsch ist, wird signalisiert, dass der Thread warten will, und bitte ein weiterer an die Reihe kommen soll.

Mit PT_WAIT_THREAD kann man einen Unterthread starten, und warten, bis dieser hier sich komplett ausgeführt hat. Jedes Schedulen von dem Oberthread wird gleich wieder zum Unterthread führen. Letztendlich kann man mit PT_RESTART die unterliegende lokale Continuation resetten, und somit praktisch den Protothread wieder von vorne laufen lassen. Mit PT_EXIT wird signalisiert, dass der Thread zuende ist. Als Hauptschleife muss man da ein Konstrukt wie dieses hier verwenden (aus example-buffer.c):

int
main(void)
{
  struct pt driver_pt;

  PT_INIT(&driver_pt);

  while(PT_SCHEDULE(driver_thread(&driver_pt))) {
    /*
     * When running this example on a multitasking system, we must
     * give other processes a chance to run too and therefore we call
     * usleep() here. On a dedicated embedded system, we usually do
     * not need to do this.
     */
    usleep(10);
  }
  return 0;
}

Besonders interessant dürften Protothreads auf Embedded-Systemen sein, bei denen man auf Platz achten muss, aber trotzdem sehr oft ein einfaches Multithreadingsystem braucht, um verschiedenen Eingaben zu verarbeiten. Auch interessant dürfte der Einsatz in Netzwerkservern sein, mal sehen, was man da so machen kann.