Abstractions for safe concurrent programming in networked embedded systems

ABSTRACT

Over the last several years, large-scale wireless mote networks have made possible the exploration of a new class of highly-concurrent and highly-distributed applications. As the horizon of what kinds of applications can be built on these networked embedded systems keeps expanding, there is a need to keep the activity of programming such systems easy, efficient, and scalable. We make three major contributions in this paper. First, we present a library for TinyOS and nesC that enables true multi-threading on a mote. This library includes support for all mote platforms in use currently (AVR, MSP). Second, we present a tool that can effectively and accurately compute stack requirements for multithreaded programs. Such analysis ensures that the stacks allocated to individual threads are correctly sized. Finally, we present a collection of programming abstractions that simplifies the construction of concurrent systems for the mote platform. We also present experimental results obtained from several example systems built using our concurrent programming abstractions and the underlying thread library.

REFERENCES

• 1: 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
• 2: Atmel Corporation. Atmega128(l) data sheet. www.atmel.-com/dyn/resources/prod_documents/doc2467.pdf.
• 3: Shah Bhatti , James Carlson , Hui Dai , Jing Deng , Jeff Rose , Anmol Sheth , Brian Shucker , Charles Gruenwald , Adam Torgerson , Richard Han, MANTIS OS: an embedded multithreaded operating system for wireless micro sensor platforms, Mobile Networks and Applications, v.10 n.4, p.563-579, August 2005 [doi>10.1145/1160162.1160178]
• 4: Dennis Brylow , Niels Damgaard , Jens Palsberg, Static checking of interrupt-driven software, Proceedings of the 23rd International Conference on Software Engineering, p.47-56, May 12-19, 2001, Toronto, Ontario, Canada
• 5: David R. Butenhof, Programming with POSIX threads, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 6: Chipcon, Texas Instruments. Cc2420 data sheet. www.chipcon.com/files/CC2420_Data_Sheet_1_3.pdf.
• 7: A. Dunkels, O. Schmidt, and T. Voigt. Using Protothreads for Sensor Node Programming. In REALWSN'05, Stockholm, Sweden, June 2005.
• 8: Adam Dunkels , Bjorn Gronvall , Thiemo Voigt, Contiki - A Lightweight and Flexible Operating System for Tiny Networked Sensors, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04), p.455-462, November 16-18, 2004 [doi>10.1109/LCN.2004.38]
• 9: R.S. Engelschall. Portable multithreading: The signal stack trick for user-space thread creation. In 2000 USENIX Annual Technical Conference, 2000.
• 10: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 11: R. Gummadi, O. Gnawali, and R. Govindan. Macro-programming wireless sensor networks using kairos. In DCOSS '05, June 2005.
• 12: 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
• 13: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 14: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 15: 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
• 16: Hugh C. Lauer , Roger M. Needham, On the duality of operating system structures, ACM SIGOPS Operating Systems Review, v.13 n.2, p.3-19, April 1979 [doi>10.1145/850657.850658]
• 17: 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
• 18: P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks. In NSDI '04, 2004.
• 19: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 20: T.D. May, S.H. Dunning, G.A. Dowding, and J.O. Hall-strom. An rpc design for wireless sensor networks. J. Pervasive Computing and Communication, March 2006.
• 21: Moteiv Corporation. Tmote Sky data sheet. moteiv.com/products/docs/tmote-sky-datasheet.pdf.
• 22: Ryan Newton , Matt Welsh, Region streams: functional macroprogramming for sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052213]
• 23: C. Nitta, R. Pandey, and Y. Ramin. Y-Threads: Supporting concurrency in wireless sensor networks. In LNCS 4026 (DCOSS '06), pages 169--184, jun 2006.
• 24: John Regehr , Alastair Reid, HOIST: a system for automatically deriving static analyzers for embedded systems, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 25: John Regehr , Alastair Reid , Kirk Webb, Eliminating stack overflow by abstract interpretation, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.751-778, November 2005 [doi>10.1145/1113830.1113833]
• 26: Texas Instruments. MSP430x1xx family user's guide (rev. f). www-s.ti.com/sc/psheets/slau049f/slau049f.pdf.
• 27: J.R. von Behren, J. Condit, and E.A. Brewer. Why events are a bad idea (for high-concurrency servers). In M.B. Jones, editor, HotOS, pages 19--24. USENIX, 2003.
• 28: 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
• 29: M. Welsh and G. Mainland. Programming sensor networks using abstract regions. In NSDI, pages 29--42. USENIX, 2004.
• 30: Kamin Whitehouse , Cory Sharp , Eric Brewer , David Culler, Hood: a neighborhood abstraction for sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990079]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Design, Experimentation, Languages, Measurement, Performance

Keywords:
multi-threading, programming methodology, static analysis, wireless sensor networks