Cheap Threads

I always wish I could focus on a single “kind” of code, but I don’t seem to have that luxury. Although I’ve gotten used to it, I find it mildly disconcerting to switch gears from Microchip assembly language, to Java, to PHP, and then over to C code on an ARM processor.

One thing I have noticed, though, is that it is actually easier to make big shifts than it is to make little shifts. So switching between C++ and Java is murder. Switching between AVR assembly code and Java is trivial because it is clear you are in a different environment and you just context switch.

The same is true for switching classes of computers with the same language. When you are writing C++ on a big 64-bit Linux box, you develop certain habits. Those habits can be hard to break when you downshift to GCC on a little 8-bit processor like an AVR. Sure, it’s still C++, but you can’t do things the same way and you have to mentally shift gears.

Sometimes you just have to give up your creature comforts when you are working on restricted hardware. Sometimes you can find alternatives that might have limitations, but let you use tools you want to use. One example that comes to mind is protothreads.

I first ran into protothreads when I was looking at the ConTiki operating system and the related uIP stack. Both ConTiki and uIP use protothreads. As you might expect, the protothread library is a way of implementing threads, but because it can work on severely restricted hardware, the threads are limited compared to, say, POSIX pThreads. The BSD license makes it easy to include with your code and it is lightweight and generic enough that it should work just about anywhere you have a C compiler.

On the plus side, protothreads take no direct stack space, and require 2 or 4 bytes of overhead per thread. On the down side, they are cooperative only, threads lose their local variables and stack context when they block, and you can’t use a switch statement inside of a thread.

Actually, library is a misnomer. The entire system is a clever use of C macros and unusual usage of C constructs like switch and while. Here is a simple protothread (lifted from one of the examples that ships with the library).:

static int
protothread1(struct pt *pt)
  /* A protothread function must begin with PT_BEGIN() which takes a
     pointer to a struct pt. */

  /* We loop forever here. */
  while(1) {
    /* Wait until the other protothread has set its flag. */
    PT_WAIT_UNTIL(pt, protothread2_flag != 0);
    printf("Protothread 1 running\n");

    /* We then reset the other protothread's flag, and set our own
       flag so that the other protothread can run. */
    protothread2_flag = 0;
    protothread1_flag = 1;

    /* And we loop. */

  /* All protothread functions must end with PT_END() which takes a
     pointer to a struct pt. */

Essentially every protothread is a function that follows this PT_BEGIN, while loop, PT_END pattern. The main program creates pt structures for each thread and initializes them with PT_INIT. Then it simply calls each protothread functions in turn with the correct structure. You don’t have to fairly schedule, of course. You might call thread A, thread B, thread A, and finally thread C if you wanted thread A to run more often than the other threads. But typically, you just round-robin the threads like this:

static struct pt pt1, pt2;
  /* Initialize the protothread state variables with PT_INIT(). */
   * Then we schedule the two protothreads by repeatedly calling their
   * protothread functions and passing a pointer to the protothread
   * state variables as arguments.
  while(1) {

This is a simple example and doesn’t really show off everything protothreads can do, but it makes it easy to see how to get started. The example this is excerpted from has two threads, and each waits for a flag set by the other thread (in such a way as to avoid deadlock, of course).

The basic implementation of the magic macros essentially put a switch statement inside each function. Each function call gets a 2-byte “token” that allows the switch to put the function back at the point it was supposed to continue. So your code looks more or less like this:

int athread(int *token)
   switch (*token)
      case 0:   
          while (1) { …...

                return 0;
       case RESUME_POINT1:
              /* code after the last blocking call */
	return 0;
       case RESUME_POINT2:
         . . .

This does mean you don’t have any stack context when you run. So any local variables are garbage after you block (use global variables, or better still, a global structure for each thread instance with variables within). While your thread can call functions, those functions can’t block (there would be no way to return).

Technically, th ***a***is is more like coroutines than real threads. But it is a nice abstraction. The API has more macros you can use (full documentation at There’s also a simple semaphore system available. Here is a synopsis:

***a***void PT_INIT(struct pt *pt);
Initialize a protothread. This is usually done early in your program.
void PT_BEGIN(struct pt *pt);
Declare the start of a protothread inside the C function implementing the protothread. Every protothread function starts with this macro.
void PT_WAIT_UNTIL(struct pt *pt, condition);
Block and wait until condition is true.
void PT_WAIT_WHILE(struct pt *pt, condition);
Block and wait while condition is true.
void PT_WAIT_THREAD(struct pt *pt, thread);
Block and wait until a child protothread completes.
void PT_SPAWN(struct pt *pt, struct pt *child, thread);
Spawn a child protothread and wait until it exits. Only usable inside a protothread.
void PT_RESTART(struct pt *pt);
Restart the protothread. That is, block and on the next execution, start back at PT_BEGIN.
void PT_EXIT(struct pt *pt);
Exit the protothread.
void PT_END(struct pt *pt);
Declare the end of a protothread. Always at the end of a protothread.
int PT_SCHEDULE(protothread);
Schedule a protothread. The return value indicates if the protothread is running or not.
void PT_YIELD(struct pt *pt);
Yield from the current protothread.
void PT_YIELD_UNTIL(struct pt *pt, condition);
Yield from the current protothread until the condition is true.
PT_SEM_INIT(semaphore, count);
Initialize a semaphore.
PT_SEM_WAIT(struct pt *pt, semaphore);
Wait on a semaphore.
PT_SEM_SIGNAL(struct pt *pt, semaphore);
Signal a semaphore.

The local variables getting lost on each resume is probably the worst feature of these threads. It is easy enough, though, to extend the structure so that each thread has its own private data area, which is still global, but a little easier to deal with:

static struct 
  int a;
  int b;
/* whatever local variables you want */
} local1,local3;

static struct 
  int x;
  int y;
/* whatever local variables you want */
} local2;

  /* Initialize the protothread state variables with PT_INIT(). */
  PT_INIT(&pt1); ***a***local1;
In this case, I modified pt.h like this:

struct pt {
  lc_t lc;
  void *data;

Of course, that’s an extra pointer’s worth of data per thread, but it’s a small price to pay for the extra convenience. Naturally, you could craft these coroutines by hand. But the abstraction is pleasant enough and it can help you switch gears between “big iron” and “little silicon.”