Protothreads: simplifying event-driven programming of memory-constrained embedded systems

ABSTRACT

Event-driven programming is a popular model for writing programs for tiny embedded systems and sensor network nodes. While event-driven programming can keep the memory overhead down, it enforces a state machine programming style which makes many programs difficult to write, maintain, and debug. We present a novel programming abstraction called protothreads that makes it possible to write event-driven programs in a thread-like style, with a memory overhead of only two bytes per protothread. We show that protothreads significantly reduce the complexity of a number of widely used programs previously written with event-driven state machines. For the examined programs the majority of the state machines could be entirely removed. In the other cases the number of states and transitions was drastically decreased. With protothreads the number of lines of code was reduced by one third. The execution time overhead of protothreads is on the order of a few processor cycles.

REFERENCES

• 1: T. Abdelzaher, J. Stankovic, S. Son, B. Blum, T. He, A. Wood, and C. Lu. A communication architecture and programming abstractions for real-time embedded sensor networks. In Workshop on Data Distribution for Real-Time Systems, Providence, RI, USA, May 2003.
• 2: H. Abrach , S. Bhatti , J. Carlson , H. Dai , J. Rose , A. Sheth , B. Shucker , J. Deng , R. Han, MANTIS: system support for multimodAl NeTworks of in-situ sensors, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941358]
• 3: Atul Adya , Jon Howell , Marvin Theimer , William J. Bolosky , John R. Douceur, Cooperative Task Management Without Manual Stack Management, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.289-302, June 10-15, 2002
• 4: Elaine Cheong , Judy Liebman , Jie Liu , Feng Zhao, TinyGALS: a programming model for event-driven embedded systems, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952668]
• 5: R. Cunningham and E. Kohler. Making events less slippery with eel. In Proceedings of the 10th Workshop on Hot Topics in Operating Systems (HotOS-X), Santa Fee, New Mexico, June 2005. IEEE Computer Society.
• 6: Frank Dabek , Nickolai Zeldovich , Frans Kaashoek , David Mazières , Robert Morris, Event-driven programming for robust software, Proceedings of the 10th workshop on ACM SIGOPS European workshop: beyond the PC, July 01-01, 2002, Saint-Emilion, France [doi>10.1145/1133373.1133410]
• 7: A.L. de Moura and R. Ierusalimschy. Revisiting coroutines. MCC 15/04, PUC-Rio, Rio de Janeiro, RJ, June 2004.
• 8: T. Duff. Unwinding loops. Usenet news article, net.lang.c, MessageID: <[e-mail]>, May 1984.
• 9: A. Dunkels. Protothreads web site. Web page. Visited 2006-04-06. http://www.sics.se/~adam/pt/
• 10: Adam Dunkels, Full TCP/IP for 8-bit architectures, Proceedings of the 1st international conference on Mobile systems, applications and services, p.85-98, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066118]
• 11: Adam Dunkels , Niclas Finne , Joakim Eriksson , Thiemo Voigt, Run-time dynamic linking for reprogramming wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182810]
• 12: A. Dunkels, B. Grönvall, and T. Voigt. Contiki - a lightweight and flexible operating system for tiny networked sensors. In Proceedings of the First IEEE Workshop on Embedded Networked Sensors, Tampa, Florida, USA, November 2004.
• 13: A. Dunkels, O. Schmidt, and T. Voigt. Using protothreads for sensor node programming. In Proc. of the Workshop on Real-World Wireless Sensor Networks (REALWSN'05), Stockholm, Sweden, June 2005.
• 14: J. Ganssle. The embedded muse. Monthly newsletter. http://www.ganssle.com/tem-back.htm
• 15: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 16: R. Gummadi, O. Gnawali, and R. Govindan. Macro-programming wireless sensor networks using kairos. In Proc. of Distributed Computing in Sensor Systems (DCOSS)'05, Marina del Rey, CA, USA, June 2005.
• 17: Chih-Chieh Han , Ram Kumar , Roy Shea , Eddie Kohler , Mani Srivastava, A dynamic operating system for sensor nodes, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067188]
• 18: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 19: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 20: J. Jeong. Analysis of xnp network reprogramming module. Web page, October 2003. Visited 2006-04-06. http://www.cs.berkeley.edu/~jaein/cs294 1/xnp anal.htm
• 21: Oliver Kasten , Kay Römer, Beyond event handlers: programming wireless sensors with attributed state machines, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 22: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 23: Framework Labs. Protothreads for Objective-C/Cocoa. Visited 2006-04-06. http://www.frameworklabs.de/protothreads.html
• 24: H.C. Lauer and R.M. Needham. On the duality of operating systems structures. In Proc. Second International Symposium on Operating Systems, October 1978.
• 25: Philip Levis , David Culler, Maté: a tiny virtual machine for sensor networks, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 26: P. Levis, S. Madden, D. Gay, J. Polastre, R. Szewczyk, A. Woo, E. Brewer, and D. Culler. The Emergence of Networking Abstractions and Techniques in TinyOS. In Proc. NSDI'04, March 2004.
• 27: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 28: M. Melkonian. Get by Without an RTOS. Embedded Systems Programming, 13(10), September 2000.
• 29: Ryan Newton , Arvind , Matt Welsh, Building up to macroprogramming: an intermediate language for sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 30: J. Paisley and J. Sventek. Real-time detection of grid bulk transfer traffic. In Proceedings of the 10th IEEE/IFIP Network Operations Management Symposium, 2006.
• 31: John C. Reynolds, The discoveries of continuations, Lisp and Symbolic Computation, v.6 n.3-4, p.233-248, Nov. 1993 [doi>10.1007/BF01019459]
• 32: Z.B. Simpson. State machines: Cooperative mini-kernels with yielding. In Computer Game Developer's Conference, Austin, TX, November 1999.
• 33: S. Tatham. Coroutines in C. Web page, 2000. http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
• 34: Tijs van Dam , Koen Langendoen, An adaptive energy-efficient MAC protocol for wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958512]
• 35: R. von Behren, J. Condit, and E. Brewer. Why events are a bad idea (for high-concurrency servers). In Proceedings of the 9th Workshop on Hot Topics in Operating Systems, May 2003.
• 36: Rob von Behren , Jeremy Condit , Feng Zhou , George C. Necula , Eric Brewer, Capriccio: scalable threads for internet services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 37: M. Welsh and G. Mainland. Programming sensor networks using abstract regions. In Proc. USENIX/ACM NSDI'04, San Francisco, CA,, March 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
embedded systems, threads, wireless sensor networks