TinyOS-related projects General intro ------------- nesC is an extension to C designed to embody the structuring concepts and execution model of TinyOS. TinyOS is an event-driven operating system designed for sensor network nodes that have very limited resources (e.g., 8K bytes of program memory, 512 bytes of RAM). Links: http://berkeley.intel-research.net/dgay/nesc (nesC) http://webs.cs.berkeley.edu (TinyOS) Contact: David Gay (dgay@intel-research.net) Projects 1-4 below are language design projects, projects 5-6 are more in the analysis/implementation category. Project 1: Continuations ------------------------ Background: In TinyOS, all operations are non-blocking. Operations that would normally block are instead split-phase: a message is sent by the "send" command, the completion of the send is signaled by a "sendDone" event. As a result, code (e.g., calling send) often stashes away intermediate results in global storage for use in the event handler (e.g., for sendDone). This is tedious, and error-prone. Goal: Add a continuation-like mechanism to nesC to automate this process, however the requirement is that this mechanism use constant space (if variable space were allowed we would probably just be recreating a thread-like system). Optionally: (Contributed by George Necula.) It is very convenient to program multi-tasking applications using an event-driven model. In this model a long running computation is split into several short subtasks (often the split occurs at IO points). Each subtask is invoked by a common event loop. (If you have programmed Windows 3.1 you probably remember this). Is it possible to take a regular C program and split it (semi-)automatically into subtasks? Project 2: Component Instantiation ---------------------------------- Background: nesC programs are built out of components, which provide and use services (described by interfaces, which are sets of functions). An application is built by "wiring" components together via their interfaces. The current definition of nesC only allows one instance of a given component and resolves all wiring at compile-time. However, this is often restrictive. Goal: Extend the semantics of nesC to allow multiple instances of a component to be created. Two kinds of instantiation should be considered: compile-time-only creation, and compile or runtime creation. Some form of type polymorphism for components could also be considered. Project 3: State Machines ------------------------- Background: Many TinyOS components include a state machine in their implementation, partly because all TinyOS operations are non-blocking (see Project 1), partly because they are interacting with stateful hardware. This code is often hard to read and debug because these state machines are implemented by ad-hoc C code. Goal: Extend nesC to incorporate some facility for declaring and implementing state machines. These state machines might possibly interact with specification of components. Project 4: Ownership -------------------- Background: TinyOS programs do not use dynamic memory allocation, and the scope of nesC global variables is a single component. It is thus somewhat meaningful to say that a particular storage item "belongs" to a particular component. However, the TinyOS networking layer extends this model somewhat: on reception of a message (in a buffer "belonging" to the networking layer), the component receiving the message can elect to "exchange ownership" of this buffer with one of its own (this allows the component to subsequently read contents from the received message without worrying about them being overwritten). Goal: Define a clear semantics for "belonging" and "exchanging ownership" of storage items. Preliminary ideas have involved something like a `pass' type qualifier for function arguments or results... Project 5: Timing Analysis -------------------------- Background: TinyOS applications run on embedded systems and have various real-time requirements (e.g., in radio-based communication). Additionally, some apparently-possible data races in TinyOS are precluded because the potentially concurrent code fragments cannot run concurrently because of timing considerations (e.g., a task that runs for 1/10s every second cannot conflict with itself). Goal: Analyse the execution time of code in nesC applications. This is more tractable than it sounds because of two factors: the hardware used (mica motes) has predictable per-instruction timing, and most TinyOS code is simple (no unbounded loops or recursion). Project 6: Debugging -------------------- Background: The hardware (mica mote) on which nesC programs run does not support traditional debugging techniques: it is not possible to set breakpoints (code cannot (easily) be modified during runtime, and there are no hardware breakpoint registers). Goal: Allow breakpoints to be set on the mica mote, by transforming the compiled code so that it includes explicit tests for breakpoints (note: a full implementation is probably too large for CS263, but a complete design should be of reasonable size).