Atomicity and visibility in tiny embedded systems

ABSTRACT

Visibility is a property of a programming language's memory model that determines when values stored by one concurrent computation become visible to other computations. Our work exploits the insight that in nesC, a C-like language with explicit atomicity, the traditional way of ensuring timely visibility---volatile variables---can be entirely avoided. This is advantageous because the volatile qualifier is a notorious source of programming errors and misunderstandings. Furthermore, the volatile qualifier hurts performance by inhibiting many more optimizations than are necessary to ensure visibility. In this paper we extend the semantics of nesC's atomic statements to include a visibility guarantee, we show two ways that these semantics can be implemented, and we also show that our better implementation has no drawbacks in terms of resource usage.

REFERENCES

• 1: Andrei Alexandrescu, Hans Boehm, Kevlin Henney, Doug Lea, and Bill Pugh. Memory model for multithreaded C++, September 2004. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1680.pdf.
• 2: AVR C Runtime Library Project. AVR libc Frequently Asked Questions, 2006. http://www.nongnu.org/avr-libc/user-manual/FAQ.html.
• 3: Hans-J. Boehm, Threads cannot be implemented as a library, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 4: Crossbow Technology, Inc. http://xbow.com.
• 5: 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
• 6: 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
• 7: Herb Sutter. Prism: A principle-based sequential memory model for microsoft native code platforms, July 2006. Draft, available from http://www.gotw.ca/memmodel/Prism%20-%20draft%200.8.pdf.
• 8: Ben L. Titzer , Daniel K. Lee , Jens Palsberg, Avrora: scalable sensor network simulation with precise timing, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 9: Linus Torvalds. Anti-volatile diatribe, July 2006. Linux-Kernel Mailing List posting, http://lkml.org/lkml/2006/7/6/159.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages

General Terms:
Design, Languages