Operating System/Language Co-Design

Kevin Klues, Maria Kazandjieva
and Philip Levis

Collaborators: John Regehr, William Archer, Vlado Handziski, David Gay, Prabal Dutta, Rodrigo Fonseca, Ion Stoica, David Culler

Introduction:

Embedded systems are among the most difficult computer platforms for programmers to work with. The need to meet hard real-time deadlines, fit programs into a small amount of memory, be robust to failures, and conserve energy wherever possible, make programming these types of systems extremely difficult.

Wireless sensor networks are a special type of embedded system particulary sensitive to these issues. The need to quickly build large and complex systems that meet these constraints raises novel challenges in isolating independent subsystems from one another in the absence of virtualization. TinyOS, the de-facto standard OS for embedded sensor networks, was designed specifically to help programmers overcome these problems. By co-designing the language within which TinyOS is implemented in parallel with the OS itself, we are able to add language primitives to help analysis, as well as design the OS so that it is more checkable.

TinyOS and nesC:

The language we have created to implement TinyOS is a dialect of C called nesC. NesC defines a component model that allows for the efficient implementation of individual components that communicate through narrow interfaces. Since individual components enable fine grained code reuse, this approach has been successful in creating applications that make very efficient use of limited code and data memory. Other features of the nesC language make implementing highly energy efficient applications possible, as well as helping to make them more reliable.

Energy Efficiency:
To allow for highly energy efficient implementations, TinyOS is completely event-driven, relying on nesC primitives to help define the flow of information through an executing program. Using nesC, programmers define split-phase operations for all long-running system calls and I/O operations. These split-phase operations are similar to traditional asynchronous I/O calls with one important difference: they know exactly when an application is aware that an I/O operation has completed. In a threaded system, a device driver will resume threads blocked on select (or a similar function), but the scheduler may not run the thread immediately. An application making split-phase I/O requests, on the other hand, receives explicit notification from a device driver upon its completion through a direct upcall. This subtle but important difference allows a device driver to know exactly when an application has been notified about the completion of an I/O event. We leverage this knowledge, using application I/O requests to precisely control a device's power state.

We are currently in the process of exploring how to effectively achieve the same level of energy efficency that split-phase operations allow us, but do so inside a threaded OS. The first step in this exploration involves taking TinyOS and building a thread library on top of it. Once we understand what is necessary to make such energy savings possible we hope to push this work into OSs designed for other embedded systems such as mobile phones and PDAs.

Reliability:
To make TinyOS more reliable, nesC defines concurrency primitives in the form of atomic blocks, automatically detecting potential race conditions on shared variables. Programmers use these atomic blocks to isolate access to variables shared between different execution contexts. Whenever a potential race-condition exists, the nesC compiler issues a warning, allowing the programmer to immediately become aware of its existence.

A recent addition to the nesC language allows safety checks of another type to be performed as well. In TinyOS, many component interfaces have implied usage constraints that can be the source of frustrating program errors. Developers are commonly forced to read the source code for components, partially defeating the purpose of using components in the first place. By explicitly specifying and enforcing component interface contracts, programmers are able to regain the trust in the isolation assumed between component boundaries.

Due to the extensive reuse of the most common interfaces, implementing contracts for a small number of frequently reused interfaces permits us to extensively check a large number of applications. Doing so retroactively has even helped to uncover some subtle and previously unknown bugs in applications that have been in common use for years. In the future we plan to add more reliability features to the nesC language making TinyOS applications safer for future programmers.

Publications:


[1] K. Klues, V. Handziski, C. Lu, A. Wolisz, D. Culler, D. Gay, and P. Levis. "Integrating Concurrency Control and Energy Management in Device Drivers.", Proc. of the 21st ACM Symposium on Operating System Principles (SOSP) 2007, Stevenson, WA, Oct. 2007.

[2] W. Archer, P. Levis, and J. Regehr. "Interface Contracts for TinyOS.", Proc. of the 6th International Conference on Information Processing in Sensor Networks (IPSN) 2007, SPOTS track, Boston, MA, May 2007.

[3] Rodrigo Fonseca, Prabal Dutta, Philip Levis, and Ion Stoica. "Quanto: Tracking Energy in Networked Embedded Systems.", Proc. of the Eighth USENIX Symposium on Operating System Design and Implementation (OSDI), 2008.

[4] Yang Chen, Omprakash Gnawali, Maria Kazandjieva, Philip Levis, and John Regehr. "Surviving Sensor Network Software Faults." In Proceedings of the 22nd ACM Symposium on Operating System Principles (SOSP), 2009, Big Sky, Montana, Oct. 2009