Intent

Allows multiple users to have an instance of a particular service, managing their state and enabling those instances to efficiently collaborate.

Also Known As

Virtual services

Example TinyOS Components

TimerM, MateHandlerStore, DripM

Motivation

Sometimes many components or subsystems need to use a system service, but each user wants a separate instance of that service. Additionally, the service may have state associated with each user, and needs to make decisions based on the state of all of the users.

The TinyOS Timer is an example of this problem: many components, such as network protocols, need timers for timeouts, rate-based operations, or coordination. Each of these timers must be independent from the others: a data sampler starting its timer should not cause a network protocol's timer to fire earlier or later than desired.

Although, from the users of the timers perspective, each timer is independent, their implementation requires knowing the 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 before meeting this lowest timer's requirement. Firing fewer interrupts reduces CPU load on the system and can allow it to sleep longer, saving energy.

Implementing each timer as a seperate component has two major problems: code copying and state coordination. Every time a component needs a timer, the programmer has to make a copy of a timer component and rename it. With nesC 1.2, the timer could just be a generic module, so there is a single copy of the nesC code text, but the final code image will still have multiple copies of the binary. Additionally, the modules need some way to communicate, in order to figure out how to set the underlying hardware clock. Just setting it at a fixed rate and maintaining a counter for each Timer is inefficient: timer fidelity requires firing at a high rate, but it's pointless to fire at 1KHz if the next timer is in four seconds.

Allocating a constant number of instances of the service (e.g., 16 timers) is either prone to failure or wasteful. If the system needs fewer than the number allocated, then RAM is wasted. If the system needs more than the number allocated, then detection of the mismatch is left until run-time, when the component implementing the service refuses a request.

The service instance pattern provides a solution to this problem. Using this pattern, each user of a service can have a virtual instance of it, but those instances share an implementation and can easily share state. Each instance has a unique name, generated with the local keyset pattern.

A component following the service instance pattern provides the desired service in a parameterized interface; each user of the service wires to a separate instance of the interface, using the unique() function (generating the local keyset). In nesC 1.1 and earlier, each user of the service must know the key to pass to the call to unique(); in nesC 1.2 and later, the call to unique() can be encapsulated in a generic configuration.

The underlying component can determine how many instances of the service exist using the uniqueCount() function. It can use this value to allocate state for each instance of the service, and the key each instance has (obtained with unique()) can index which state element to use.

Applicability

Use the service instance pattern when:

• A component needs to provide multiple instances of a service, but does not know how many.
• Each instance of the service appears to its user to be independent of the others.
• The provider of the service needs to be able easily access the state of each instance.

Structure

Participants

• ServiceProvider: allocates state for each instance of the service and coordinates underlying resources based on all of the instances.
• ServiceUser: users of the service.
• Resource: an underlying system resource that ServiceProvider multiplexes/demultiplexes service instances on.

Collaborations

When a ServiceUser makes calls on its instance of its service, the ServiceProvider modifies its internal state of the instance accordingly. Addittionally, it may change the operation of the underlying Resource to meet the changed needs.

Consequences

Because ServiceProvider allocates the state for every instance of the service, it can easily perform operations that require access to each instance. Additionally, the amount of state allocated is determined at compile time to meet the number of instances.

However, because the pattern scales to a variable number of instances, the cost of its operations may scale linearly with the number of users, and can't be known until an application is composed. For example, if setting the underlying clock interrupt rate in a timer ServiceProvider depends on the timer with the shortest remaining duration, ServiceProvider 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 those instances are used rarely, then allocating state for each one can be wasteful. The other option is to allocate a smaller amount of state and dynamically allocate it to users as need be. This can conserve RAM, but requires more RAM per real instance (client IDs need to be maintained), imposes a CPU overhead (allocation and deallocation), and can fail at run-time (if more requests come in than can be handled). The standard TinyOS task queue is similar to this dynamic approach, although it does not follow the ServiceProvider pattern: allocating state for every task is prohibitive.

Implementation

The ServiceProvider provides the service as a parameterized interface. Users that need an instance of the service wire to the parameterized interface with a unique identifier using the unique() function provided by nesC. The ServiceProvider allocates state for each client using an array of size determined by the uniqueCount() function, so that the unique identifiers can map onto elements of the array.

One common pitfall in the using a service instance is the key passed to unique(); every user of the service must be wired with the same key. For example, this code will work:

components Provider, User1, User2;

User1.Service -> Provider.Service[unique("Service")];
User2.Service -> Provider.Service[unique("Service")];

While this code will have run-time issues:

components Provider, User1, User2;

User1.Service -> Provider.Service[unique("User1")];
User2.Service -> Provider.Service[unique("User2")];

Because User1M and User2 use different keys in the second example, the calls to unique() will not return values that are unique with respect to one another. Two components may inadvertently be mapping to the same instance of the service. Additionally, the ServiceProvider component may allocate too few instances, and so access memory inappropriately.

In nesC 1.2, the call to unique() can be encapsulated in a generic configuration; this solves simple problems like typographic errors in the key or mistaken wirings.

Sample Code

Consider the TinyOS Timer abstraction. Various components in an application, from an ADC calibrator to networking protocols to application triggers, need timers to operate properly. However, motes generally have a small number of hardware timers, many fewer than the number of application timers needed. A component therefore needs to multiplex/demultiplex multiple software timers on one or more hardware timers.

The ServiceProvider, TimerM, needs to maintain state for each software timer: whether it is running, is a repeating timer, and what its remaining time is. A configuration, TimerC, exports TimerM's interface and wires it to an underlying clock resource. Individual clients wire to TimerC.Timer, using "Timer" as a key for the call to unique. The TimerM implementation:

module TimerM {
  provides interface Timer[uint8_t id];
  ...
  uses interface Clock;
}
implementation {
  enum {
    NUM_TIMERS = uniqueCount("Timer"),
  }

  struct timer_s {
    uint8_t type;           // one-short or repeat timer
    int32_t ticks;          // clock ticks for a repeat timer 
    int32_t ticksLeft;      // ticks left before the timer expires
  } mTimerList[NUM_TIMERS];


  command result_t Timer.start[uint8_t id](char type, uint32_t interval) {
    if (id >= NUM_TIMERS) return FAIL;
    if (type > TIMER_REPEAT) return FAIL;
    mTimerList[id].ticks = interval ;
    mTimerList[id].type = type;

    /* See if the underlying Clock needs to be adjusted */
    return SUCCESS;
  }

}

TimerC is a configuration that wires TimerM up to the clock and exports TimerM's Timers:

configuration TimerC {
  provides interface Timer[uint8_t id];
}

implementation {
  components TimerM, ClockC;

  TimerM.Clock -> ClockC;
  StdControl = TimerM;
  Timer = TimerM;
}
		  

Finally, clients that want a Timer wire using unique():

configuration GenericComm {
  ...
}
implementation {
  components TimerC, AMStandard;
  ...

  AMStandard.Timer -> TimerC.Timer[unique("Timer")];
  ...
}
		  

Known Uses

TimerM, as detailed above, uses a service instance pattern to manage various application timers.

The viral code propagation subsystem of the Maté framework uses a service instance to manage version metadata for code capsules. As the VM is customizable, the number of needed capsules isn't known until the VM is actually composed.

In a similar vein, the epidemic dissemination protocol Drip uses the service instance pattern to maintain epidemic state for each disseminated value.

Related Patterns

Service instances use a local keyset for counting the number of instances. If the service requires global identifiers, then a key map can map from the global to local identifiers.

A service instance may seem similar to a dispatcher at first glance, but its purpose is very different. A dispatcher allows the set of functionality a system supports to be easily extended, while a service instance allows instantiation of a particular piece of functionality. Additionally, a core part of the service instance pattern is state allocation and management.