TEP: | 110 |
---|---|
Group: | Core Working Group |
Type: | Documentary |
Status: | Draft |
TinyOS-Version: | 2.x |
Author: | Philip Levis |
Draft-Created: | 20-Jun-2005 |
Draft-Version: | 1.5 |
Draft-Modified: | 2006-12-12 |
Draft-Discuss: | TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu> |
Note
This memo documents a part of TinyOS for the TinyOS Community, and requests discussion and suggestions for improvements. Distribution of this memo is unlimited. This memo is in full compliance with TEP 1.
This memo desribes how TinyOS 2.0 virtualizes common abstractions through a combination of static allocation and runtime arbitration. It describes the benefits and tradeoffs of this approach and how it is used in several major abstractions.
The TinyOS component model allows flexible composition, but that flexibility is often limited by reasons which are not explicitly stated in components. These implicit assumptions can manifest as buggy behavior. In TinyOS 1.x, on the Telos platform, if a program simultaneously initializes non-volatile storage and the radio, one of them will fail: a program has to initialize them serially. They can also manifest as compile-time errors: if two separate communication services happen to receive packets of the same AM type, the nesC compiler will issue a warning due to the buffer swap semantics.
On one hand, the flexbility components provide allows expert users to build complex and intricate applications. On the other, it can make managing complexity and intricacy very difficult when building very simple and basic applications. To promote this latter class of development, TinyOS 2.x has the notion of "distributions," which are collections of system abstractions that are designed to be used together. As long as a user implements an application in terms of the distribution, the underlying components will operate correctly and there will be no unforseen failures.
This memo documents an example distribution, named OSKI (Operating System Key Interfaces). It describes the services OSKI provides and how their implementations are structured to simplify application writing.
A distribution presents services to the programmer. A service is a set of generic (instantiable) components that represent API abstractions. To use an abstraction, a programmer instantiates the generic. For example, OSKI has the AMSenderC abstraction for sending active messages. The AMSender generic component takes a single parameter, the AM type. For example, if a programmer wants a component named AppM to send active messages of type 32, the configuration would look something like this:
Services often present abstractions at a fine grain. For example, the active message service has AMSender, AMReceiver, and AMSnooper, each of which is a separate abstraction.
Every service has two abstractions: ServiceC, for powering it on and off, and ServiceNotifierC, for learning when the service's power state has changed. For example, active messages have the AMServiceC and AMServiceNotifierC abstractions. A service abstraction provides the Service interface
while a notifier abstraction provides the ServiceNotify interface
For example, if a routing layer wants to be able to turn the active message layer on and off, then it needs to instantiate an AMServiceC. However, many components may be using active messages and have their own instances of AMServiceC; while routing might consider it acceptable to turn off active messages, other components might not. Therefore, a service abstraction does not necessarily represent explicit control; instead, each service has a policy for how it deals with control requests. When a service changes its activity state, it MUST signal all instances of its ServiceNotifierC.
For example, the active messages service has an "OR" policy; the service remains active if any of its ServiceC instances are in the on state, and goes inactive if and only if all of its ServiceC instances are in the off state. This is an example timeline for active messages being used by two components, RouterA and RouterB:
By default, a service that has a control interface MUST be off. For an application to use the service, at least one component has to call Service.start().
Because distributions are collections of services that are designed to work together, they can avoid many of the common issues that arise when composing TinyOS programs. For example, user code does not have to initialize a service; this is done automatically by the distribution. If a user component instantiates a service abstraction, the distribution MUST make sure that the service is properly initialized. Section 4 goes into an example implementation of how a distribution can achieve this.
This section briefly describes the services that OSKI, an example distribution provides. It is intended to give a feel for how a distribution presents its abstractions.
OSKI provides timers at one fidelity: milliseconds. Timers do not have a Service abstraction, as their use implicitly defines whether the service is active or not (the timer service is off if there are no pending timers). The OSKITimerMsC component provides the abstraction: it provides a single interface, Timer<TMilli>.
This is an example code snippet for instantiating a timer in a configuration:
OSKI provides four functional active messaging abstractions: AMSender, AMReceiver, AMSnooper, and AMSnoopingReceiver. Each one takes an am_id_t as a parameter, indicating the AM type. Following the general TinyOS 2.x approach to networking, all active message abstractions provide the Packet and AMPacket interfaces.
This snippet of code is an example of a configuration that composes a routing layer with needed active message abstractions. This implementation snoops on data packets sent by other nodes to improve its topology formation:
The active messages layer has control abstractions, named AMServiceC and AMServiceNotifierC. Active messages follow an OR policy.
In addition to active messages, OSKI provides a broadcasting service. Unlike active messages, which are addressed in terms of AM addresses, broadcasts are address-free. Broadcast communication has two abstractions: BroadcastSenderC and BroadcastReceiverC, both of which take a parameter, a broadcast message type. This parameter is similar to the AM type in active messages. Both abstractions provide the Packet interface. The broadcast service has control abstractions, named BroadcastServiceC and BroadcastServiceNotifierC, which follow an OR policy.
NOTE: These services are not supported as of the 2.x prerelease. They will be supported by the first full release.
OSKI's third communication service is tree-based collection routing. This service has four abstractions:
All of the collection routing communication abstractions take a parameter, similar to active messages and broadcasts, so multiple components can independelty use collection routing. In addition to communication, collection routing has an additional abstraction:
Finally, collection routing has CollectionServiceC and CollectionServiceNotifierC abstractions, which follow an OR policy.
NOTE: These services are not supported as of the 2.x prerelease. They will be supported by the first full release. They will be fully defined pending discussion/codification of UART interfaces.
Presenting services through abstractions hides the underlying wiring details and gives a distribution a great deal of implementation freedom. One issue that arises, however, is initialization. If a user component instantiates a service, then a distribution MUST make sure the service is initialized properly. OSKI achieves this by encapsulating a complete service as a working component; abstractions export the service's interfaces.
For example, the timer service provides a single abstraction, OskiTimerMilliC, which is a generic component. OskiTimerMilliC provides a single instance of the Timer<TMilli> interface. It is implemented as a wrapper around the underlying timer service, a component named TimerMilliImplP, which provides a parameterized interface and follows the Service Instance design pattern[sipattern]_:
TimerMilliImplP is a fully composed and working service. It takes a platform's timer implementation and makes sure it is initialized through the TinyOS boot sequence[boot]_:
This composition means that if any component instantiates a timer, then TimerMilliImplP will be included in the component graph. If TimerMilliImplP is included, the TimerMilliP (the actual platform HIL implementation) will be properly initialized at system boot time. In this case, the order of initialization isn't important; in cases where there are services that have to be initialized in a particular sequence to ensure proper ordering, the Impl components can orchestrate that order. For example, a distribution can wire Main.SoftwareInit to a DistributionInit component, which calls sub-Inits in a certain order; when a service is included, it wires itself to one of the sub-Inits.
The user does not have to worry about unique strings to manage the underlying Service Instance pattern: the abstractions take care of that.
Active messaging reprsent a slightly more complex service, as it has several abstractions and a control interface. However, it follows the same basic pattern: abstractions are generics that export wirings to the underlying service, named ActiveMessageImplP:
For example, this is the AMSender abstraction:
AMReceiver is similar, except that it wires to the Receive interface, while AMSnooper wires to the Snoop interface, and AMSnoopingReceiver provides a single Receive that exports both Snoop and Receive (the unidirectional nature of the Receive interface makes this simple to achieve, as it represents only fan-in and no fan-out).
ActiveMessageImplP does not provide a Service interface; it provides the SplitControl interface of the underlying active message layer. OSKI layers a ServiceController on top of SplitControl. As the active message service follows an OR policy, OSKI uses a ServiceOrControllerM, which is a generic component with the following signature:
ServiceOrControllerM follows the Service Instance pattern[sipattern]; it calls its underlying SplitControl based on the state of each of its instances of the Service interface. The parameter denotes the string used to generate the unique service IDs. The active messages service controller implementation, AMServiceImplP, instantiates a ServiceOrControllerM, wires it to ActiveMessageImplP:
AMServiceC then provides an instance of AMServiceImplP.Service:
Note that the two strings are the same, so that the uniqueCount() in the ServiceOrControllerM is correct based on the number of instances of AMServiceC. As with timers, encapsulating the service instance pattern in generic components relieves the programmer of having to deal with unique strings, a common source of bugs in TinyOS 1.x code.
OSKI is a layer on top of system components: it presents a more usable, less error-prone, and simpler interface to common TinyOS functionality. For OSKI to work properly, a platform MUST be compliant with the following TEPs:
o TEP 102: Timers o TEP 106: Schedulers and Tasks o TEP 107: TinyOS 2.x Boot Sequence o TEP 1XX: Active Messages o TEP 1XX: Collection Routing
Not following some of these TEPS MAY lead to OSKI services being inoperable, exhibit strange behavior, or being uncompilable.
The basic notion of a distribution is that it provides a self-contained, tested, and complete (for an application domain) programming interface to TinyOS. Layers can be added on top of a distribution, but as a distribution is a self-contained set of abstractions, adding new services can lead to failures. A distribution represents a hard line above which all other code operates. One SHOULD NOT add new services, as they can disrupt the underlying organization. Of course, one MAY create a new distribution that extends an existing one, but this is in and of itself a new distribution.
Generally, as distributions are intended to be higher-level abstractions, they SHOULD NOT provide any asynchronous (async) events. They can, of course, provide async commands. The idea is that no code written on top of a distribution should be asynchronous, due to the complexity introduced by having to manage concurrency. Distributions are usually platform independent; if an application needs async events, then chances are it is operating close to the hardware, and so is not platform independent.
[rst] | reStructuredText Markup Specification. <http://docutils.sourceforge.net/docs/ref/rst/restructuredtext.html> |
[sipattern] | The Service Instance Pattern. In Software Design Patterns for TinyOS. David Gay, Philip Levis, and David Culler. Published in Proceedings of the ACM SIGPLAN/SIGBED 2005 Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'05). |
[boot] | TEP 107: TinyOS 2.x Boot Sequence. |