The nesc Language:
A Holistic Approach to Networked Embedded Systems
David Gay, Philip Levis, Robert von Behren etl. al.
Summary, Class Discussion and Slides (14th March 2005)
CPSC 538A - Topics in Computer Systems
Presented By: Abhishek Gupta {agupta@cs.ubc.ca}
|
1) Introduction This
paper describes nesC which is a programming language for networked embedded
systems. An example of a networked embedded system is sensor networks, in
which thousands of tiny ‘motes’ execute concurrent, reactive programs that
must operate under severe memory constraints. A
key focus of nesC is holistic system design. Mote applications are deeply
tied to hardware, and each mote runs a single application at a time. This
approach yields three important properties. First, all resources are known
statically. Second, rather than employing a general purpose OS, applications
are built from a suite of reusable system components coupled with application
specific code. Third, hardware/software boundary varies on the application
and hardware platform. In
the domain of sensor networks there are a number of key challenges that nesC
must address: Driven by interaction with
environment: Firstly, unlike
traditional batch processing or interactive applications, sensor network
applications are about data collection and control of environment. This focus
leads to two observations. First, motes are fundamentally event-driven and
second, data arrival and data processing are concurrent activities in this
domain. Limited Resources: Motes have very limited physical resources, due to
the goals of small size, low cost, and low power consumption. In this
regards, Reliablity: Motes are quite susceptible to failure and therefore
it is important to design long-lived applications. The only mode for recovery
in this domain is usually a reboot. Soft-real time requirements: Typically, some components of sensor network
applications have hard real time requirements but it has been experienced
that timing constraints can normally be met by having tight control over
application and OS and limiting utilization. In
response to these challenges, nesC’s contribution
to this domain is a programming model that incorporates event driven
execution, a flexible concurrency model, and component oriented application
design. Restrictions on the programming language model allow the nesC compiler
to perform static analysis of the whole program which aids in the discovery
of data race conditions and aggressive function inlining. 2) Background
In
part the motivations behind designing nesC were to support and evolve
TinyOS’s programming model. TinyOS is an operating system for networked
embedded systems and has a very small memory footprint. TinyOS has several
important features that influenced nesC’s design.
One such feature is component based
architecture. TinyOS provides a set of reusable system components. An
application connects components using a wiring specification that is
independent of component implementation. Decomposing different OS services
into separate components allows unused services to be excluded from the
application. Another feature is a simple event
based concurrency model. There are two sources of concurrency In TinyOS:
events and tasks. Tasks represent deferred computation and are used when time
is not a constraint. Tasks are non-preemptive with respect to each other i.e.
one task cannot preempt the other. Events also run to completion but an event
may preempt the execution of a task or another event. Events signify either
completion of a split-phase operation
or an even from the environment. Split-phase operations are used for long
latency applications. In these applications operation request and operation
completion are separate functions. Resource contention is typically handled
through explicit rejection of concurrent requests. 3) nesc Design
nesC
has been designed as an extension of the C programming language. C was the
natural choice because it supports efficient code generation for all target
micro-controllers likely to be used in sensor networks. The disadvantage in
using C is that it is not safe and gives no structure to the application.
nesC addresses safety through reduced expressive power and structure through
components. nesC programs are subject to whole program analysis and
optimization and the limited application size on motes makes this approach
tractable. Further, nesC is a static language, which means that there is no
possibility of dynamic allocation, function pointers etc. As
mentioned previously, nesC’s programs comprise of
components. A component uses and provides interfaces. An interface models a
service and is specified by an interface type. Interfaces in nesC are
bidirectional: they contain commands and events, both of which are
essentially functions. Users of an interface have to implement the events
whereas providers of an interface have to implement the commands for the
interface. Further, there are two types of components in nesC: modules and
configurations. Modules provide implementations of one or more interfaces and
configurations are used to wire other components together, connecting
interfaces used by components to interfaces provided by others. Every nesC
implementation has a top level configuration that wires together the
components used. Concurrency
and atomicity in nesC applications is provided by two means. The first is
tasks and the other is a language construct that allows programmers to create
atomic blocks of code. Apart from this, for preventing race conditions the
compiler maintains the invariant that if a variable x is accessed from and
event handler (Asynchronous code) then it must be inside an atomic block, or
it is an error. A
unique aspect in nesC is the provision of parameterized interfaces for
introducing runtime command and event dispatch within a first order language.
Similar to the concept of active messages parameterized interfaces provide a
means to the programmer to customized interfaces for their different
components. Usually it is done in three phases, initially the declaration of
an interface must specify that it is a parameterized interface, next each use
of the interface must provide a compile time constant to uniquely identify
the interface and finally at run time the right id must be provided for
runtime dispatch of the interface. 4) Evaluation TinyOS consists of 172 components of which 108 are code modules and 64 are configurations. The number of modules per application ranges from 8 to 67 with an average of 24. Modules generally are quite small, with 120 lines of code on an average. While performing a race condition analyses on the TinyOS tree, there were 156 potential race conditions detected, out of which 53 were false positives. Each of the race conditions were fixed by either moving the code into tasks or atomic blocks. As with race condition, nesC exploits the restrictions of the component model to perform static analysis and optimization. nesC’s optimizations led to 15-34% reduction in the execution time and a 9-15% reduction in the overall footprint.
|