WIXLIB

module AppM { . }implementation {int sum 0;command void Init.init() {call Sensor1.sense();}event void Sensor1.senseDone(int val) {sum val;call Sensor2.sense();}event void Sensor2.senseDone(int val) {sum val;}}As this example shows, a command or event f of an interfaceI is named I.f and is similar to a C function except for theextra syntactic elements such as command, event and call. Modulesencapsulate their state: all of their variables (e.g., sum) are private.2.2ConfigurationsA configuration implements its specification by wiring other components together, and equating its own interfaces with interfacesof those components. Two components can interact only if someconfiguration has wired them together:configuration SensorsC {provides interface Sense as Light;provides interface Sense as Temp;}implementation {components Main, LightM, TempM;Main.Init - LightM.Init;Main.Init - TempM.Init;Light LightM.Sensor;Temp TempM.Sensor;}SensorsC “assembles” components LightM and TempM into a singlecomponent providing an interface for each sensor: Temp is equatedto TempM’s Sensor interface, Light with LightM’s Sensor interface.Additionally, SensorsC wires the system’s initialisation interface(Main.Init) to the initialisation interfaces of LightM and TempM.Finally, AppC, the configuration for the whole application, wiresmodule AppM (which uses two sensors) to SensorsC (which providestwo sensors), and ensures that AppM is initialised by wiring it toMain.Init:configuration AppC { }implementation {components Main, AppM, SensorsC;Main.Init - AppM.Init;AppM.Sensor1 - SensorsC.Light;AppM.Sensor2 - SensorsC.Temp;}In this application, interface Main.Init is multiply wired.AppC connects it to AppM.Init, while SensorsC connects it toLightM.Init and TempM.Init. The call Init.init() in moduleMain compiles to an invocation of all three init() commands.42.3Parameterised InterfacesA parameterised interface is an interface array. For example, thismodule has a separate instance of interface A for each value of id:module Example {provides interface Initialise as Inits[int id];uses interface Sense as Sensors[int id];} .4 If a multiply wired function has non-void result, nesC combines the resultsvia a programmer-specified function. [4]In a module, commands and events of parameterised interfaceshave an extra argument:command void Inits.init[int id1]() {call Sensors.sense[id1]();}event void Sensors.senseDone[int i](int v) {}A configuration can wire a single interface by specifying itsindex:configuration ExampleC {}implementation {components Main, Example;components TempM, LightM;Main.Init - Example.Inits[42];Example.Sensors[42] - TempM.Sensor;Example.Sensors[43] - LightM.Sensor;}When Main’s Init.init command is called, Example’s Inits.initcommand will be executed with id 42. This will cause Exampleto call Sensor[42].sense, which connects to TempM.sense.A configuration can wire or equate a parameterised interface toanother parameterised interface. This equates Example.Sensors[i]to ADC[i] for all values of i:provides interface Sense as ADC[int id];.Example.Sensors ADC;2.4unique and uniqueCountIn many cases, a programmer wants to use a single element of aparameterised interface, and does not care which one as long as noone else uses it. This functionality is supported by nesC’s uniqueconstruction:AppM.Timer1 - TimerC.Timer[unique("Timer")];AppM.Timer2 - TimerC.Timer[unique("Timer")];All uses of unique with the same argument string (a constant)return different values, from a contiguous sequence starting at 0. Itis also often useful to know the number of different values returnedby unique (e.g., a service may wish to know how many clients ithas). This number is returned by the uniqueCount construction:timer t timers[uniqueCount("Timer")];3.Design PatternsWe present five TinyOS design patterns: two behavioural (relating to component interaction): Dispatcher and Decorator, and threestructural (relating to how applications are structured): Service Instance, Placeholder and Facade. A more in-depth presentation ofthese and other patterns can be found on our website [5]; in particular we do not include any namespace (management of identifiers such as message types) patterns here. We follow the basicformat used in Design Patterns [3], abbreviated to fit in a researchpaper. Each pattern has an Intent, which briefly describes its purpose. A more in-depth Motivation follows, providing an exampledrawn from TinyOS. Applicable When provides a succinct list ofconditions for use and a component diagram shows the Structureof how components in the pattern interact. This diagram followsthe same format as Figure 1, with the addition of a folded sub-boxfor showing source code (a floating folded box represents sourcecode in some other, unnamed, component). Sample Code shows anexample nesC implementation; Consequences describes how thepattern achieves its goals, and notes issues to consider when usingit. Related Patterns compares to other relevant patterns.

3.1Behavioural: DispatcherIntent: Dynamically select between a set of operations based on anidentifier. Provides a way to easily extend or modify a system byadding or changing operations.Motivation: At a high level, sensor network applications executeoperations in response to environmental input such as sensor readings or network packets. The operation’s details are not importantto the component that presents the input. We need to be able to easily extend and modify what inputs an application cares about, aswell as the operation associated with an input.For example, a node can receive many kinds of active messages (packets). Active messages (AM) have an 8-bit type field,to distinguish between protocols. A flooding protocol uses one AMtype, while an ad-hoc routing protocol uses another. AMStandard,the component that signals the arrival of a packet, should not needto know what processing a protocol performs or whether an application supports a protocol. AMStandard just delivers packets, andthe application responds to those it cares about.The traditional approach to this problem is to use function pointers or objects, which are dynamically registered as callbacks. Inmany cases, even though registered at run time, the set of operationsis known at compile time. Thus these callbacks can be replaced bya dispatch table compiled into the executable, with two benefits.First, this allows better cross-function analysis and optimization,and secondly it conserves RAM, as no pointers or callback structures need to be stored.Such a dispatch table could be built for the active messageexample by using a switch statement in AMStandard. But this isvery inflexible: any change to the protocols used in an applicationrequires a change in a system component.A better approach in TinyOS is to use the Dispatcher pattern.A Dispatcher invokes operations using a parameterised interface,based on a data identifier. In the case of AMStandard, the interfaceis ReceiveMsg and the identifier is the active message type field.AMStandard is independent of what messages the application handles, or what processing those handlers perform. Adding a new handler requires a single wiring to AMStandard. If an application doesnot wire a receive handler for a certain type, AMStandard defaultsto a null operation.Another example of a Dispatcher is the scheduler of the Matévirtual machine. Each instruction is a separate component thatprovides the MateBytecode interface. The scheduler executes aparticular bytecode by dispatching to the instruction componentusing a parameterised MateBytecode interface. The instruction setcan be easily changed by altering the wiring of the scheduler.Applicable When: A component needs to support an externally customisable setof operations. A primitive integer type can identify which operation to per-form. The operations can all be implemented in terms of a [id]Op2Opcomponents Dispatcher, Op2;Dispatcher.Operations[KEY2] - Op2.Op;interface OperationSample Code: AMStandard is the radio stack component that dispatches received messages:module AMStandard {// Dispatcher interface for messagesuses interface ReceiveMsg as Recv[uint8 t id];}implementation {TOS MsgPtr received(TOS MsgPtr packet) {return signal Recv.receive[packet- type](packet);}.}and the App configuration registers AppM to handle two kinds ofmessages:configuration App {}implementation {components AppM, AMStandard;AppM.ClearIdMsg - AMStandard.Receive[AM CLEARIDMSG];AppM.SetIdMsg - AMStandard.Receive[AM SETIDMSG];}Consequences: By leaving operation selection to nesC wirings, thedispatcher’s implementation remains independent of what an application supports. However, finding the full set of supported operations can require looking at many files. Sloppy operation identifiermanagement can lead to dispatch problems: if two operations arewired with the same identifier, then a dispatch will call both, whichmay cause problems.The key aspects of the dispatcher pattern are: It allows you to easily extend or modify the functionality an ap-plication supports: adding an operation requires a single wiring. It allows the elements of functionality to be independently im-plemented and re-used. Because each operation is implementedin a component, it can be easily included in many applications.Keeping implementations separate can also simplify testing, asthe components will be smaller, simpler, and easier to pinpointfaults in. The nesC compiler will automatically inline small operations, or you can explicitly request inlining; thus this decomposition has no performance cost. It requires the individual operations to follow a uniform interface. The dispatcher is usually not well suited to operations thathave a wide range of semantics. As all implementations have tomeet the same interface, broad semantics leads to the interfacebeing overly general, pushing error checks from compile-timeto run-time. An implementor forgetting a run-time parametercheck can cause a hard to diagnose system failure.The compile-time binding of the operation simplifies programanalysis and puts dispatch tables in the compiled code, savingRAM. Dispatching provides a simple way to develop programs thatexecute in reaction to their environment.Related Patterns: Service Instance: a service instance creates many instances ofan implementation of an interface, while a dispatcher selectsbetween different implementations of an interface. Placeholder: a placeholder allows an application to select animplementation at compile-time, while a dispatcher allows it toselect an implementation at runtime.

3.2Structural: Service InstanceIntent: Allows multiple users to have separate instances of a particular service, where the instances can collaborate efficiently.Motivation: Sometimes many components or subsystems need touse a system abstraction, but each user wants a separate instance ofthat service. We don’t know how many users there will be until webuild a complete application. Each instance requires maintainingsome state, and the service implementation needs to access all ofthis state to make decisions.For example, a wide range of TinyOS components need timers,for everything from network timeouts to sensor sampling. Eachtimer appears independent, but they all operate on top of a singlehardware clock. An efficient implementation thus requires knowingthe state of all of the timers. If the implementation can easily determine which timer has to fire next, then it can schedule the underlying clock resource to fire as few interrupts as possible to meet thislowest timer’s requirement. Firing fewer interrupts reduces CPUload on the system and can allow it to sleep longer, saving energy.The traditional object-oriented approach to this problem is toinstantiate an object representing the service and use another classto coordinate state. This approach is not applicable in nesC as wecannot have multiple copies of components5 , and requires eithersharing state across objects, which is contrary to encapsulation, orstate copying, which uses additional RAM.Implementing each timer in a separate module leads to duplicated code and requires inter-module coordination in order to figure out how to set the underlying hardware clock. Just setting it ata fixed rate and maintaining a counter for each Timer is inefficient:timer fidelity requires firing at a high rate, but it’s pointless to fireat 1KHz if the next timer is in four seconds.The Service Instance pattern provides a solution to these problems. Using this pattern, each user of a service can have its own(virtual) instance, but instances share code and can access eachother’s state. A component following the Service Instance patternprovides its service in a parameterised interface; each user wiresto a unique instance of the interface using unique. The underlyingcomponent receives the unique identity of each client in each command, and can use it to index into a state array. The componentcan determine at compile-time how many instances exist using theuniqueCount function and dimension the state array accordingly.Applicable When: A component needs to provide multiple instances of a service,but does not know how many until compile time. Each service instance appears to its user to be independent ofthe others. The service implementation needs to be able to easily accessthe state of every Svc[id]User2SvcUsedResourceAResourceNUSERS uniqueCount(“Service”);StateType state[NUSERS];5 Thisconfiguration TimerC {provides interface Timer[uint8 t id];}implementation {components TimerM, ClockC;Timer TimerM.Timer;TimerM.Clock - ClockC.Clock;}and TimerM uses uniqueCount to determine how many timersto allocate and accesses them using unique IDs:module TimerM {provides interface Timer[uint8 t clientId];uses interface Clock;}implementation {// per-client statetimer t timers[uniqueCount("Timer")];command result t Timer.start[uint8 t clientId](.) {if (timers[clientId].busy).}}Clients wanting a timer wire using unique:C.Timer - TimerC.Timer[unique("Timer")];Consequences: The key aspects of the Service Instance pattern are: It allows many components to request independent instances ofa common system service: adding an instance requires a singlewiring. It controls state allocation, so the amount of RAM used is scaledto exactly the number of instances needed, conserving memory while preventing run-time failures due to many requests exhausting resources. It allows a single component to coordinate all of the instances,which enables efficient resource management and coordination.Because the pattern scales to a variable number of instances,the cost of its operations may scale linearly with the number ofusers. For example, if setting the underlying clock interrupt ratedepends on the timer with the shortest remaining duration, animplementation might determine this by scanning all of the timers,an O(n) operation.If many users require an instance of a service, but each of thoseinstances are used rarely, then allocating state for each one can bewasteful. The other option is to allocate a smaller amount of stateand dynamically allocate it to users as need be. This can conserveRAM, but requires more RAM per real instance (client IDs needto be maintained), imposes a CPU overhead (allocation and deallocation), can fail at run-time (if there are too many simultaneoususers), and assumes a reclamation strategy (misuse of which wouldlead to leaks). This long list of challenges makes the Service Instance an attractive – and more and more commonly used – way toefficiently support application requirements.Related Patterns: Dispatcher: a service instance creates many instances of an im-interface Servicecomponents User2, ServiceProvider;User2.Svc - ServiceProvider.Svc[unique(“Service”)];Sample Code: TimerC wires TimerM, which contains the actualtimer logic, to an underlying hardware clock and exports its Timerinterfaces:interface Resourcerestriction will be lifted in the next version of nesC (Section 4.4).plementation of an interface, while a dispatcher selects betweendifferent implementations of an interface.

3.3Structural: PlaceholderIntent: Easily change which implementation of a service an entireapplication uses. Prevent inadvertent inclusion of multiple, incompatible implementations.Motivation: Many TinyOS systems and abstractions have severalimplementations. For example, there are many ad-hoc tree routingprotocols (Route, MintRoute, ReliableRoute), but they all exposethe same interface, Send. The standardized interface allows applications to use any of the implementations without code changes.Simpler abstractions can also have multiple implementations. Forexample, the LedsC component actually turns the LEDs on and off,while the NoLedsC component, which provides the same interface,has null operations. During testing, LedsC is useful for debugging,but in deployment it is a significant energy cost and usually replaced with NoLedsC.Sometimes, the decision of which implementation to use needsto be uniform across an application. For example, if a networkhealth monitoring subsystem (HealthC) wires to MintRoute, whilean application uses ReliableRoute, two routing trees will be built,wasting resources. As every configuration that wires to a servicenames it, changing the choice of implementation in a large application could require changing many files. Some of these files, suchas HealthC, are part of the system; an application writer should nothave to modify them.One option is for every implementation to use the same component name, and put them in separate directories. Manipulating thenesC search order allows an application to select which version touse. This approach doesn’t scale well: each implementation of eachcomponent needs a separate directory. Streamlining this structureby bundling several implementations (e.g., the “safe” versions andthe “optimized” ones) in a single directory requires all-or-nothinginclusion. This approach also precludes the possibility of includingtwo implementations, even if they can interoperate.The Placeholder pattern offers a solution. A placeholder configuration represents the desired service through a level of namingindirection. All components that need to use the service wire to theplaceholder. The placeholder itself is just “a pass through” of theservice’s interfaces. A second configuration (typically provided bythe application) wires the placeholder to the selected implementation. This selection can then be changed centrally by editing asingle file. As the level of indirection is solely in terms of names– there is no additional code generated – it imposes no CPU overhead.Applicable When: A component or service has multiple, mutually exclusive im-plementations. Many subsystems and parts of your application need to use thiscomponent/service. You need to easily switch between the implementations.Sample Code: Several parts o

Phil Levis University of California at Berkeley pal@cs.berkeley.edu David Culler University of California at Berkeley culler@cs.berkeley.edu Abstract We present design patterns used by software components in the TinyOS sensor network operating system. They differ significantly from traditional software design patterns due to the constraints