Information about http://www.ist-runes.org/docs/publications/realwsn05.pdf
Using Protothreads for Sensor Node Programming …
Tags: adam dunkels, driven model, driven systems, explicit state, invocations, level operations, levis, memory usage, oliver schmidt, programming abstraction, resource constraints, science science, semantics, sensor network, sensor node, split phase, swedish institute, thiemo voigt, tiny devices, wireless sensor networks,Pages: 5
Language: english
Display cached document
Page 1
Page 2
Page 3
Page 4
Page 5
Using Protothreads for Sensor Node Programming
Adam Dunkels Oliver Schmidt Thiemo Voigt
Swedish Institute of Computer oliver@jantzer- Swedish Institute of Computer
Science Science
schmidt.de
adam@sics.se thiemo@sics.se
ABSTRACT run-to-completion semantics, the system can utilize a sin-
Wireless sensor networks consist of tiny devices that usually gle, shared stack. This reduces the memory overhead over
have severe resource constraints in terms of energy, process- a multi-threaded system, where memory must be allocated
ing power and memory. In order to work efficiently within for a stack for each running program.
the constrained memory, many operating systems for such
devices are based on an event-driven model rather than on The run-to-completion semantics of event-triggered systems
multi-threading. While event-driven systems allow for re- makes implementing certain high-level operations a complex
duced memory usage, they require programs to be developed task. When an operation cannot complete immediately, the
as explicit state machines. Since implementing programs as operation must be split across multiple invocations of the
explicit state machines is hard, developing, maintaining, and event handler. Levis et al. [10] refer to this as a split-phase
debugging programs for event-driven systems is difficult. operation. In the words of Levis et al.:
In this paper, we introduce protothreads, a programming
abstraction for event-driven sensor network systems. Pro- "This approach is natural for reactive pro-
tothreads simplify implementation of high-level functional- cessing and for interfacing with hardware, but
ity on top of event-driven systems, without significantly in- complicates sequencing high-level operations, as
creasing the memory requirements. The memory require- a logically blocking sequence must be written in
ment of a protothread is that of an unsigned integer. a state-machine style."
1. INTRODUCTION In this paper, we introduce the notion of using protothreads [3,
Wireless sensor networks consist of tiny devices that usually 6] as a method to reduce the complexity of high-level pro-
have severe resource constraints in terms of energy, process- grams in event-triggered sensor node systems. We argue
ing power and memory. Most programming environments that protothreads can reduce the number of explicit state
for wireless sensor network nodes today are based on an machines required to implement typical high-level sensor
event-triggered programming model rather than traditional node programs. We believe this reduction leads to programs
multi-threading. In TinyOS [7], the event-triggered model that are easier to develop, debug, and maintain, based on
was chosen over a multi-threaded model because of the mem- extensive experience with developing software for the event-
ory overhead of threads. According to Hill et al. [7]: driven uIP TCP/IP stack [4] and Contiki operating sys-
tem [5].
"In TinyOS, we have chosen an event model
so that high levels of concurrency can be handled The main contribution of this paper is the protothread pro-
in a very small amount of space. A stack-based gramming abstraction. We show that protothreads reduce
threaded approach would require that stack space the complexity of programming sensor nodes. Further, we
be reserved for each execution context." demonstrate that protothreads can be implemented in the C
programming language, using only standard C language con-
While the event-driven model and the threaded model can structs and without any architecture-specific machine code.
be shown to be equivalent [9], programs written in the two
models typically display differing characteristics [1]. The ad- The rest of this paper is structured as follows. Section 2
vantages and disadvantages of the two models are a debated presents a motivating example and Section 3 introduces the
topic [11, 14]. notion of protothreads. Section 4 discusses related work,
and the paper is concluded in Section 5.
In event-triggered systems, programs are implemented as
event handlers. Event handlers are invoked in response to 2. MOTIVATION
external or internal events, and run to completion. An event To illustrate how high-level functionality is implemented
handler typically is a programming language procedure or using state machines, we consider a hypothetical energy-
function that performs an action, and makes an explicit re- conservation mechanism for wireless sensor nodes. The mech-
turn to the caller. Because of the run-to-completion seman- anism switches the radio on and off at regular intervals. The
tics, an event-handler cannot execute a blocking wait. With mechanism works as follows:
enum { PT_THREAD(radio_wake_thread(struct pt *pt)) {
ON, PT_BEGIN(pt);
WAITING,
OFF while(1) {
} state; radio_on();
timer_set(&timer, T_AWAKE);
void radio_wake_eventhandler() { PT_WAIT_UNTIL(pt, timer_expired(&timer));
switch(state) {
timer_set(&timer, T_SLEEP);
case OFF: if(!communication_complete()) {
if(timer_expired(&timer)) { PT_WAIT_UNTIL(pt, communication_complete()
radio_on(); || timer_expired(&timer));
state = ON; }
timer_set(&timer, T_AWAKE);
} if(!timer_expired(&timer)) {
break; radio_off();
PT_WAIT_UNTIL(pt, timer_expired(&timer));
case ON: }
if(timer_expired(&timer)) { }
timer_set(&timer, T_SLEEP);
if(!communication_complete()) { PT_END(pt);
state = WAITING; }
} else {
radio_off();
state = OFF; Figure 2: The radio sleep cycle implemented with
} protothreads.
}
break;
To implement this state machine in C, we use an explicit
case WAITING:
if(communication_complete() state variable, state, that can take on the values OFF, ON,
|| timer_expired(&timer)) { and WAITING. We use a C switch statement to perform
state = ON; different actions depending on the state variable. The code
timer_set(&timer, T_AWAKE); is placed in an event handler function that is called whenever
} else { an event occurs. Possible events in this case are that a timer
radio_off(); expires and that communication completes. The resulting
state = OFF;
} C code is shown in Figure 1.
break;
} We note that this simple mechanism results in a fairly large
} amount of C code. The structure of the mechanism, as it is
described by the six steps above, is not immediately evident
from the C code.
Figure 1: The radio sleep cycle implemented with
events.
3. PROTOTHREADS
Protothreads [6] are an extremely lightweight stackless type
1. Turn radio on. of threads, designed for severely memory constrained sys-
tems. Protothreads provide conditional blocking on top of
2. Wait for tawake milliseconds. an event-driven system, without the overhead of per-thread
stacks.
3. Turn radio off, but only if all communication has com-
pleted. We developed protothreads in order to deal with the com-
4. If communication has not completed, wait until it has
completed. Then turn off the radio. t_awake timer expired
5. Wait for tsleep milliseconds. If the radio could not be OFF ON
turned off before tsleep milliseconds because of remain-
ing communication, do not turn the radio off at all. t_sleep timer expired
6. Repeat from step 1.
communicaion
completed communication
active
To implement this protocol in an event-driven model, we WAITING
first need to identify a set of states around which the state
machine can be designed. For this protocol, we can see three
states: on the radio is turned on, waiting waiting for any
remaining communication to complete, and off the radio Figure 3: State machine realization of the radio
is off. Figure 3 shows the resulting state machine, including sleep cycle protocol.
the state transitions.
plexity of explicit state machines in the event-driven uIP void radio_wake_thread(struct pt *pt) {
TCP/IP stack [4]. For uIP, we were able to substantially switch(pt->lc) {
reduce the number of state machines and explicit states case 0:
used in the implementations of a number of application level while(1) {
communication protocols. For example, the uIP FTP client radio_on();
could be simplified by completely removing the explicit state timer_set(&timer, T_AWAKE);
machine, and thereby reducing the number of explicit states
from 20 to one. pt->lc = 8;
case 8:
if(!timer_expired(&timer)) {
3.1 Protothreads versus events return;
Programs written for an event-driven model typically have }
to be implemented as explicit state machines. In contrast,
with protothreads programs can be written in a sequential timer_set(&timer, T_SLEEP);
if(!communication_complete()) {
fashion without having to design explicit state machines.
To illustrate this, we return to the radio sleep cycle example pt->lc = 13;
from the previous section. case 13:
if(!(communication_complete() ||
Figure 2 shows how the radio sleep cycle mechanism is im- timer_expired(&timer))) {
plemented with protothreads. Comparing Figure 2 and Fig- return;
}
ure 1, we see that the protothreads-based implementation
not only is shorter, but also more closely follows the spec- }
ification of the radio sleep mechanism. Due to the linear
code flow of this implementation, the overall logic of the if(!timer_expired(&timer)) {
sleep cycle mechanism is visible in the C code. Also, in the radio_off();
protothreads-based implementation we are able to make use
pt->lc = 18;
of regular C control flow mechanisms such as while loops case 18:
and if statements. if(!timer_expired(&timer)) {
return;
3.2 Protothreads versus threads }
The main advantage of protothreads over traditional 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 sys-
tems, where a stack for a thread might use a large part of the
available memory. In comparison, the memory requirements Figure 4: C switch statement expansion of the pro-
of a protothread that of an unsigned integer. No additional tothreads code in Figure 2
stack is needed for the protothread.
Control structures. One of the advantages of threads over
Unlike a thread, a protothread runs only within a single
events is that threads allow programs to make full use
C function and cannot span over other functions. A pro-
of the control structures (e.g., if conditionals and while
tothread may call normal C functions, but cannot block in-
loops) provided by the programming language. In the
side a called function. Blocking inside nested function calls
event-driven model, control structures must be bro-
is instead implemented by spawning a separate protothread
ken down into two or more pieces in order to imple-
for each potentially blocking function. Unlike threads, pro-
ment continuations [1]. In contrast, both threads and
tothreads makes blocking explicit: the programmer knows
protothreads allow blocking statements to be used to-
exactly which functions that potentially may yield.
gether with control structures.
3.3 Comparison Debug stack retained. Because the manual stack man-
Proto- agement and the free flow of control in the event-driven
Feature Events Threads threads model, debugging is difficult as the sequence of calls
Control structures No Yes Yes is not saved on the stack [1]. With both threads and
Debug stack retained No Yes Yes protothreads, the full call stack is available for debug-
Implicit locking Yes No Yes ging.
Preemption No Yes No
Automatic variables No Yes No Implicit locking. With manual stack management, as in
the event-driven model, all yield points are immedi-
Table 1: Qualitative comparison between events, ately visible in the code. This makes it evident to the
threads and protothreads programmer whether or not a structure needs to be
locked. In the threaded model, it is not as evident that
a particular function call yields. Using protothreads,
Table 1 summarizes the features of protothreads and com- however, potentially blocking statements are explicitly
pares them with the features of events and threads. implemented with a PT WAIT statement. Program code
between such statements never yields. 3.5 Implementation
Protothreads are based on a low-level mechanism that we
Preemption. The semantics of the threaded model allows call local continuations [6]. A local continuation is simi-
for preemption of a running thread: the thread's stack lar to ordinary continuations [12], but does not capture the
is saved, and execution of another thread can be con- program stack. Local continuations can be implemented in
tinued. Because both the event-driven model and pro- a variety of ways, including using architecture specific ma-
tothreads use a single stack, preemption is not possible chine code, C-compiler extensions, and a non-obvious use of
within either of these models. the C switch statement. In this paper, we concentrate on
the method based on the C switch statement.
Automatic variables. Since the threaded model allocates
a stack for each thread, automatic variables--variables A local continuation supports two operations; it can be ei-
with function local scope automatically allocated on ther set or resumed. When a local continuation is set, the
the stack--are retained even when the thread blocks. state of the function--all CPU registers including the pro-
Both the event-driven model and protothreads use a gram counter but excluding the stack--is captured. When
single shared stack for all active programs, and rewind the same local continuation is resumed, the state of the func-
the stack every time a program blocks. Therefore, with tion is reset to what it was when the local continuation was
protothreads, automatic variables are not saved across set.
a blocking wait. This is discussed in more detail below.
A protothread consists of a C function and a single local
3.4 Limitations continuation. The protothread's local continuation is set
While protothreads allow programs to take advantage of before each conditional blocking wait. If the condition is
a number of benefits of the threaded programming model, true and the wait is to be performed, the protothread ex-
ecutes an explicit return statement, thus returning to the
protothreads also impose some of the limitations from the
caller. The next time the protothread is invoked, the pro-
event-driven model. The most evident limitation from the
event-driven model is that automatic variables--variables tothread resumes the local continuation that was previously
with function-local scope that are automatically allocated set. This will effectively cause the program to jump to the
on the stack--are not saved across a blocking wait. While conditional blocking wait statement. The condition is re-
evaluated and, once the condition is false, the protothread
automatic variables can still be used inside a protothread,
continues to execute the function.
the contents of the variables must be explicitly saved before
executing a wait statement. The reason for this is that pro-
#define RESUME(lc) switch(lc) { case 0:
tothreads rewind the stack at every blocking statement, and
therefore potentially destroy the contents of variables on the #define SET(lc) lc = __LINE__; case __LINE__:
stack.
Many optimizing C compilers, including gcc, are able to de- Figure 5: The local continuation resume and set op-
tect if an automatic variable is unsafely used after a blocking erations implemented using the C switch statement.
statement. Typically a warning is produced, stating that
the variable in question "might be used uninitialized in this Local continuations can be implemented using standard C
function". While it may not be immediately apparent for language constructs and a non-obvious use of the C switch
the programmer that this warning is related to the use of au- statement. With this technique, the local continuation is
tomatic variables across a blocking protothreads statement, represented by an unsigned integer. The resume opera-
it does provide an indication that there is a problem with tion is implemented as an open switch statement, and the
the program. Also, the warning indicates the line number set operation is implemented as an assignment of the local
of the problem which assists the programmer in identifying continuation and a case statement, as shown in Figure 5.
the problem. Each set operation sets the local continuation to a value
that is unique within each function, and the resume oper-
The limitation on the use of automatic variables can be han- ation's switch statement jumps to the corresponding case
dled by using an explicit state object, much in the same way statement. The case 0: statement in the implementation
as is done in the event-driven model. The state object is a of the resume operation ensures that the resume statement
chunk of memory that holds the contents of all automatic does nothing if is the local continuation is zero.
variables that need to be saved across a blocking statement.
It is, however, the responsibility of the programmer to allo- Figure 4 shows the example radio sleep cycle mechanism
cate and maintain such a state object. from Section 2 with the protothreads statements expanded
using the C switch implementation of local continuations.
It should also be noted that protothreads do not limit the We see how each PT WAIT UNTIL statement has been replaced
use of static local variables. Static local variables are vari- with a case statement, and how the PT BEGIN statement
ables that are local in scope but allocated in the data section. has been replaced with a switch statement. Finally, the
Since these are not placed on the stack, they are not affected PT END statement has been replaced with a single right curly
by the use of blocking protothreads statements. For func- bracket, which closes the switch block that was opened by
tions that do not need to be re-entrant, using static local the PT BEGIN statement. We also note the similarity between
variables instead of automatic variables can be an accept- Figure 4 and the event-based implementation in Figure 1.
able solution to the problem. While the resulting C code is very similar in the two cases,
the process of arriving at the code is different. With the
event-driven model, the programmer must explicitly design 6. REFERENCES
and implement a state machine. With protothreads, the [1] A. Adya, J. Howell, M. Theimer, W. J. Bolosky, and
state machine is automatically generated. J. R. Douceur. Cooperative Task Management
Without Manual Stack Management. In Proceedings of
The non-obviousness of the C switch implementation of local the USENIX Annual Technical Conference, pages
continuations is that the technique appears to cause prob- 289302, 2002.
lems when a conditional blocking statement is used inside
a nested C control statement. For example, the case 13: [2] T. Duff. Re: Explanation please! Usenet news article,
statement in Figure 4 appears inside an if block, while the Message-ID: , August 1988.
corresponding switch statement is located at a higher block. [3] A. Dunkels. Protothreads web site. Web page. Visited
However, this is a valid use of the C switch statement: case 2005-03-18. http://www.sics.se/~adam/pt/
statements may be located anywhere inside a switch block.
They do not need to be in the same level of nesting, but [4] A. Dunkels. Full TCP/IP for 8-bit architectures. In
can be located anywhere, even inside nested if or for blocks. Proceedings of The First International Conference on
This use of the switch statement is likely to first have been Mobile Systems, Applications, and Services
publicly described by Duff [2]. The same technique has later (MOBISYS `03), May 2003.
been used by Tatham to implement coroutines in C [13].
[5] A. Dunkels, B. Gršnvall, and T. Voigt. Contiki - a
o
The implementation of protothreads using the C switch state- lightweight and flexible operating system for tiny
ments imposes a restriction on programs using protothreads: networked sensors. In Proceedings of the First IEEE
programs cannot utilize switch statements together with Workshop on Embedded Networked Sensors, Tampa,
protothreads. If a switch statement is used by the program Florida, USA, November 2004.
using protothreads, the C compiler will is some cases emit
[6] A. Dunkels and O. Schmidt. Protothreads
an error, but in most cases the error is not detected by
Lightweight Stackless Threads in C. Technical Report
the compiler. This is troublesome as it may lead to unex-
T2005:05, Swedish Institute of Computer Science.
pected run-time behavior which is hard to trace back to an
erroneous mixture of one particular implementation of pro- [7] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and
tothreads and switch statements. We have not yet found a K. Pister. System architecture directions for networked
suitable solution for this problem. sensors. In Proceedings of the 9th International
Conference on Architectural Support for Programming
4. RELATED WORK Languages and Operating Systems, November 2000.
Kasten and Ršmer [8] have also identified the need for new
o
abstractions for managing the complexity of event-triggered [8] O. Kasten and K. Ršmer. Beyond event handlers:
o
programming. They introduce OSM, a state machine pro- Programming wireless sensors with attributed state
gramming model based on Harel's StateCharts. The model machines. In The Fourth International Conference on
reduces both the complexity of the implementations and the Information Processing in Sensor Networks (IPSN),
memory usage. Their work is different from protothreads in Los Angeles, USA, April 2005.
that OSM requires support from an external OSM compiler [9] H. C. Lauer and R. M. Needham. On the duality of
to produce the resulting C code, whereas protothreads only operating systems structures. In Proc. Second
make use of the regular C preprocessor. International Symposium on Operating Systems,
October 1978.
5. CONCLUSIONS
Many operating systems for wireless sensor network nodes [10] P. Levis, S. Madden, D. Gay, J. Polastre,
are based on an event-triggered programming model. In R. Szewczyk, A. Woo, E. Brewer, and D. Culler. The
order to implement high-level operations under this model, Emergence of Networking Abstractions and
programs have to be written as explicit state machines. Soft- Techniques in TinyOS. In Proc. NSDI'04, March 2004.
ware implemented using explicit state machines is often hard
[11] J. K. Ousterhout. Why threads are a bad idea (for
to understand, debug, and maintain.
most purposes). Invited Talk at the 1996 USENIX
Technical Conference, 1996.
We have presented protothreads as a programming abstrac-
tion that reduces the complexity of implementations of high- [12] J. C. Reynolds. The discoveries of continuations. Lisp
level functionality for event-triggered systems. With pro- Symbol. Comput., 6(3):233247, 1993.
tothreads, programs can perform conditional blocking on top
of event-triggered systems with run-to-completion seman- [13] S. Tatham. Coroutines in C. Web page, 2000.
tics, without the overhead of full multi-threading. http://www.chiark.greenend.org.uk/
~sgtatham/coroutines.html
Acknowledgments [14] R. von Behren, J. Condit, and E. Brewer. Why events
This work was partly financed by VINNOVA, the Swedish are a bad idea (for high-concurrency servers). In
Agency for Innovation Systems, and the European Commis- Proceedings of the 9th Workshop on Hot Topics in
sion under contract IST-004536-RUNES. Operating Systems, May 2003.