Protothreads


Detailed Description

Protothreads are a type of lightweight stackless threads designed for severly memory constrained systems such as deeply embedded systems or sensor network nodes.

Protothreads provides linear code execution for event-driven systems implemented in C. Protothreads can be used with or without an RTOS.

Protothreads are a extremely lightweight, stackless type of threads that provides a blocking context on top of an event-driven system, without the overhead of per-thread stacks. The purpose of protothreads is to implement sequential flow of control without complex state machines or full multi-threading. Protothreads provides conditional blocking inside C functions.

The advantage of protothreads over a purely event-driven approach is that protothreads provides a sequential code structure that allows for blocking functions. In purely event-driven systems, blocking must be implemented by manually breaking the function into two pieces - one for the piece of code before the blocking call and one for the code after the blocking call. This makes it hard to use control structures such as if() conditionals and while() loops.

The advantage of protothreads over ordinary threads is that a protothread do not require a separate stack. In memory constrained systems, the overhead of allocating multiple stacks can consume large amounts of the available memory. In contrast, each protothread only requires between two and twelve bytes of state, depending on the architecture.

Note:
Because protothreads do not save the stack context across a blocking call, local variables are not preserved when the protothread blocks. This means that local variables should be used with utmost care - if in doubt, do not use local variables inside a protothread!
Main features:

Examples applications:

The protothreads API consists of four basic operations: initialization: PT_INIT(), execution: PT_BEGIN(), conditional blocking: PT_WAIT_UNTIL() and exit: PT_END(). On top of these, two convenience functions are built: reversed condition blocking: PT_WAIT_WHILE() and protothread blocking: PT_WAIT_THREAD().

See also:
Protothreads API documentation
The protothreads library is released under a BSD-style license that allows for both non-commercial and commercial usage. The only requirement is that credit is given.

Authors

The protothreads library was written by Adam Dunkels <adam@sics.se> with support from Oliver Schmidt <ol.sc@web.de>.

Protothreads

Protothreads are a extremely lightweight, stackless threads that provides a blocking context on top of an event-driven system, without the overhead of per-thread stacks. The purpose of protothreads is to implement sequential flow of control without using complex state machines or full multi-threading. Protothreads provides conditional blocking inside a C function.

In memory constrained systems, such as deeply embedded systems, traditional multi-threading may have a too large memory overhead. In traditional multi-threading, each thread requires its own stack, that typically is over-provisioned. The stacks may use large parts of the available memory.

The main advantage of protothreads over ordinary threads is that protothreads are very lightweight: a protothread does not require its own stack. Rather, all protothreads run on the same stack and context switching is done by stack rewinding. This is advantageous in memory constrained systems, where a stack for a thread might use a large part of the available memory. A protothread only requires only two bytes of memory per protothread. Moreover, protothreads are implemented in pure C and do not require any machine-specific assembler code.

A protothread runs within a single C function and cannot span over other functions. A protothread may call normal C functions, but cannot block inside a called function. Blocking inside nested function calls is instead made by spawning a separate protothread for each potentially blocking function. The advantage of this approach is that blocking is explicit: the programmer knows exactly which functions that block that which functions the never blocks.

Protothreads are similar to asymmetric co-routines. The main difference is that co-routines uses a separate stack for each co-routine, whereas protothreads are stackless. The most similar mechanism to protothreads are Python generators. These are also stackless constructs, but have a different purpose. Protothreads provides blocking contexts inside a C function, whereas Python generators provide multiple exit points from a generator function.

Local variables

Note:
Because protothreads do not save the stack context across a blocking call, local variables are not preserved when the protothread blocks. This means that local variables should be used with utmost care - if in doubt, do not use local variables inside a protothread!

Scheduling

A protothread is driven by repeated calls to the function in which the protothread is running. Each time the function is called, the protothread will run until it blocks or exits. Thus the scheduling of protothreads is done by the application that uses protothreads.

Implementation

Protothreads are implemented using local continuations. A local continuation represents the current state of execution at a particular place in the program, but does not provide any call history or local variables. A local continuation can be set in a specific function to capture the state of the function. After a local continuation has been set can be resumed in order to restore the state of the function at the point where the local continuation was set.

Local continuations can be implemented in a variety of ways:

  1. by using machine specific assembler code,
  2. by using standard C constructs, or
  3. by using compiler extensions.

The first way works by saving and restoring the processor state, except for stack pointers, and requires between 16 and 32 bytes of memory per protothread. The exact amount of memory required depends on the architecture.

The standard C implementation requires only two bytes of state per protothread and utilizes the C switch() statement in a non-obvious way that is similar to Duff's device. This implementation does, however, impose a slight restriction to the code that uses protothreads in that the code cannot use switch() statements itself.

Certain compilers has C extensions that can be used to implement protothreads. GCC supports label pointers that can be used for this purpose. With this implementation, protothreads require 4 bytes of RAM per protothread.


Files

file  pt.h
 Protothreads implementation.

Modules

 Local continuations
 Local continuations form the basis for implementing protothreads.

Data Structures

struct  pt

Initialization

#define PT_INIT(pt)
 Initialize a protothread.

Declaration and definition

#define PT_THREAD(name_args)
 Declaration of a protothread.
#define PT_BEGIN(pt)
 Declare the start of a protothread inside the C function implementing the protothread.
#define PT_END(pt)
 Declare the end of a protothread.

Blocked wait

#define PT_WAIT_UNTIL(pt, condition)
 Block and wait until condition is true.
#define PT_WAIT_WHILE(pt, cond)
 Block and wait while condition is true.

Hierarchical protothreads

#define PT_WAIT_THREAD(pt, thread)
 Block and wait until a child protothread completes.
#define PT_SPAWN(pt, child, thread)
 Spawn a child protothread and wait until it exits.

Exiting and restarting

#define PT_RESTART(pt)
 Restart the protothread.
#define PT_EXIT(pt)
 Exit the protothread.

Calling a protothread

#define PT_SCHEDULE(f)
 Schedule a protothread.

Yielding from a protothread

#define PT_YIELD(pt)
 Yield from the current protothread.
#define PT_YIELD_UNTIL(pt, cond)
 Yield from the protothread until a condition occurs.

Defines

#define PT_WAITING   0
#define PT_EXITED   1
#define PT_ENDED   2
#define PT_YIELDED   3


Define Documentation

#define PT_BEGIN pt   ) 
 

Declare the start of a protothread inside the C function implementing the protothread.

This macro is used to declare the starting point of a protothread. It should be placed at the start of the function in which the protothread runs. All C statements above the PT_BEGIN() invokation will be executed each time the protothread is scheduled.

Parameters:
pt A pointer to the protothread control structure.
Examples:
dhcpc.c.

Definition at line 115 of file pt.h.

#define PT_END pt   ) 
 

Declare the end of a protothread.

This macro is used for declaring that a protothread ends. It must always be used together with a matching PT_BEGIN() macro.

Parameters:
pt A pointer to the protothread control structure.
Examples:
dhcpc.c.

Definition at line 127 of file pt.h.

#define PT_EXIT pt   ) 
 

Exit the protothread.

This macro causes the protothread to exit. If the protothread was spawned by another protothread, the parent protothread will become unblocked and can continue to run.

Parameters:
pt A pointer to the protothread control structure.

Definition at line 246 of file pt.h.

#define PT_INIT pt   ) 
 

Initialize a protothread.

Initializes a protothread. Initialization must be done prior to starting to execute the protothread.

Parameters:
pt A pointer to the protothread control structure.
See also:
PT_SPAWN()
Examples:
dhcpc.c.

Definition at line 80 of file pt.h.

Referenced by httpd_appcall().

#define PT_RESTART pt   ) 
 

Restart the protothread.

This macro will block and cause the running protothread to restart its execution at the place of the PT_BEGIN() call.

Parameters:
pt A pointer to the protothread control structure.
Examples:
dhcpc.c.

Definition at line 229 of file pt.h.

#define PT_SCHEDULE  ) 
 

Schedule a protothread.

This function shedules a protothread. The return value of the function is non-zero if the protothread is running or zero if the protothread has exited.

Parameters:
f The call to the C function implementing the protothread to be scheduled

Definition at line 271 of file pt.h.

#define PT_SPAWN pt,
child,
thread   ) 
 

Spawn a child protothread and wait until it exits.

This macro spawns a child protothread and waits until it exits. The macro can only be used within a protothread.

Parameters:
pt A pointer to the protothread control structure.
child A pointer to the child protothread's control structure.
thread The child protothread with arguments

Definition at line 206 of file pt.h.

#define PT_THREAD name_args   ) 
 

Declaration of a protothread.

This macro is used to declare a protothread. All protothreads must be declared with this macro.

Parameters:
name_args The name and arguments of the C function implementing the protothread.
Examples:
dhcpc.c, and smtp.c.

Definition at line 100 of file pt.h.

#define PT_WAIT_THREAD pt,
thread   ) 
 

Block and wait until a child protothread completes.

This macro schedules a child protothread. The current protothread will block until the child protothread completes.

Note:
The child protothread must be manually initialized with the PT_INIT() function before this function is used.
Parameters:
pt A pointer to the protothread control structure.
thread The child protothread with arguments
See also:
PT_SPAWN()

Definition at line 192 of file pt.h.

#define PT_WAIT_UNTIL pt,
condition   ) 
 

Block and wait until condition is true.

This macro blocks the protothread until the specified condition is true.

Parameters:
pt A pointer to the protothread control structure.
condition The condition.
Examples:
dhcpc.c.

Definition at line 148 of file pt.h.

#define PT_WAIT_WHILE pt,
cond   ) 
 

Block and wait while condition is true.

This function blocks and waits while condition is true. See PT_WAIT_UNTIL().

Parameters:
pt A pointer to the protothread control structure.
cond The condition.

Definition at line 167 of file pt.h.

#define PT_YIELD pt   ) 
 

Yield from the current protothread.

This function will yield the protothread, thereby allowing other processing to take place in the system.

Parameters:
pt A pointer to the protothread control structure.
Examples:
dhcpc.c.

Definition at line 290 of file pt.h.

#define PT_YIELD_UNTIL pt,
cond   ) 
 

Yield from the protothread until a condition occurs.

Parameters:
pt A pointer to the protothread control structure.
cond The condition.
This function will yield the protothread, until the specified condition evaluates to true.

Definition at line 310 of file pt.h.


Generated on Mon Jun 12 10:23:02 2006 for uIP 1.0 by  doxygen 1.4.6