In many embedded systems, memory is severely constrained. RAM sizes on the order of a few hundreds of bytes or less is very common. Full multithreading may not be an option because of the memory required for thread stacks. For such systems, the newly released Protothreads Library provides a very lightweight alternative: protothreads are a stackless type of threads with only two bytes of RAM overhead per protothread. The library is implemented in pure C without any machine specific code. Protothreads are currently used in the Contiki OS and will be used in the upcoming version of the uIP embedded TCP/IP stack.
Protothreads: extremely lightweight, stackless threads in C
About The Author
Eugenia Loli
Ex-programmer, ex-editor in chief at OSNews.com, now a visual artist/filmmaker.
Follow me on Twitter @EugeniaLoli
This is an implementation of coroutines as demonstrated by Knuth in the Art of Computer Programming. Here’s an example of how they work:
#define crBegin static int state=0; switch(state) { case 0:
#define crReturn(i,x) do { state=i; return x; case i:; } while (0)
#define crFinish }
int function(void) {
static int i;
crBegin;
for (i = 0; i < 10; i++)
crReturn(1, i);
crFinish;
}
It’s a rather creative and obfuscated use of the switch() statement to achieve coroutines, except this implementation is substantially more elegant.
However, I think there’s considerably more to be gained through the use of microthreads, specifically in regards to asynchronous programming. Windows implements microthreads in the form of “Fibers” and POSIX implements them in the form of ucontexts. I’d love to see a BSD-licensed implementation providing abstract microthreading across Windows and POSIX, and tried to write one myself as part of one of my projects (http://usri.pdtp.org/) but I failed to create an interface that properly abstracts between ucontexts and fibers.
You might want to check out this:
http://www.cs.indiana.edu/~dfried/dfried/mex.pdf
Yes, that is a very elegant implementation of coroutines. It is, to the best of my knowledge, done by Simon Tatham (see http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html), even though the swich() trick itself seems to be invented by Tom Duff (http://groups-beta.google.com/group/comp.lang.c/msg/bb78298175c4241…). In fact, protothreads can be implemented using the exact same trick – see the lc-switch.h file from the source distribution.
“I’d love to see a BSD-licensed implementation providing abstract microthreading across Windows and POSIX”
Well maybe not really what you need but .NET 2.0 will have fiber support (managed) so mono should enventually also have it.
Anyway that screenshot of contiki running on an ethernet card with only 32K ram is very, very impressive. Congrats.
AFAIK you can’t use these threads for asynchronous things, as they are (at least they look) cooperative, not preemptive.
Anyway, this looks really cool; I’ll definitely take a closer look at them!
Yes, they are cooperative, as is Contiki.
I think Contiki is excellent: running an OS with webserver and GUI on a C64. Go figure. It even has a GUI-based webbrowser that only needs about 13KB of RAM (9KB code, 4KB data) and no disk.
Correct, protothreads can not preempt each other. This is actually by design: blocking is always explicit, so you are always sure whether or not a specific function may block (i.e., switch to another protothread).
Regarding preemption and Contiki, in the development version there is now support for “real” multithreading in Contiki. These threads may even be preempted (if the architecture has support for timer interrupts), even though the Contiki kernel itself does not support preemption. The preemption mechanism is hidden inside the multithreading library, which also means that preemption can be turned on or off on a per-process basis. Only programs that explicitly need preemption will need to turn it on, whereas other programs need not be burdened by the overhead of preemption or even cooperative multithreading.
It would be awesome if we can create a complete desktop OS similar to the QNX Desktop. If this is possible, Adam, do we have someone or a team already working on this goal? I have always envision that someday we can have a PDA Desktop OS size that you can easily transform into a laptop or table pc by just buying the laptop dock with screen attached.
Another aswsome idea is a portable multimedia player and viewer that supports all many video, auido, and graphic formats.
-Kenneth
This is a very interesting library – I love it’s lack of overheads for embedded systems systems use where one block of code equates to one physical object or concept.
I’ve used coop-thread systems before (they’re used internally by at least one commercial embedded web browser I’ve worked with), and they do have their uses in this area (notably in writing portable embedded code), and although the usual “setjmp/longjmp with a stack frame hack” approach is more genericly useful (it allows local variables as each coop-thread has it’s own stack), this stack-free approach looks perfect for occasions where you’d only ever have one instance of a thread.
It’d be nice to have some more facilities from a signalling and thread enumeration perspective (although I’m aware that’d increase per-thread overhead slightly, although it wouldn’t increase context switch overheads).
Still, very clever stuff – Adam is a genius (but anyone familiar with his work on lwIP knew that already….)
From my experience with developing Contiki, I would expect that having a complete graphical OS that would run smootly both on a PDA and a fully fledged PC would probably be the worst of two worlds: too bloated for the PDA and too simple for the PC. For instance, it is possible to put a modern look on Contiki, but the design of the system is far too constrained to actually feel good to use on a modern PC.
Regarding cooperative threads: yes, they are as you say more powerful than protothreads, but at the price of requiring more RAM. In fact, protothreads can be seen the in-between of cooperative threading and event-based programming. For event-based programming, you usually have to allocate a structure for holding the state of the program between event invokations. This same principle can be used with protothreads: allocate a structure holding the state, and pass this with your protothreads. This is exactly how the web server in Contiki works. For every incoming connection, a state object is allocated (from a fixed size pool of objects). This object holds all state that would otherwise be held in local variables if the web server was fully threaded. Memorywise, the advantage of doing this explicit allocation is that there is a better chance that memory will be used for live state.
I’m not sure that more facilities would necessarily increase the per-protothread overhead, as it may be possible to build such facilities without having to alter the protothreads library at all. For instance, take a look at the protothreads semaphores, which are implemented without changing the protothreads at all. In any case, I would love to hear what kinds of facilities you had in mind.
Very nice. Cooperative multithreading is very neat.
It is worth looking at Symbian’s “Active Objects” approach – Symbian is a true preemptive kernel, but within a thread there is a standard structure for cooperative multitasking where each task is a CActive object. They can wait on external events (e.g. from other threads, e.g. servers).