tep108.txt

tinyos-2.x.rar

============================
Resource Arbitration
============================

:TEP: 108
:Group: Core Working Group
:Type: Documentary
:Status: Final
:TinyOS-Version: 2.x
:Authors: Kevin Klues, Philip Levis, David Gay, David Culler, Vlado Handziski

.. 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.

Abstract
====================================================================

This memo documents the general resource sharing mechanisms for TinyOS
2.x. These mechanisms are used to allow multiple software components to
arbitrate access to shared abstractions.

1. Introduction
====================================================================

TinyOS 1.x has two mechanisms for managing shared resources:
virtualization and completion events. A virtualized resource appears
as an independent instance of an abstraction, such as the Timer
interface in TimerC. A client of a Timer instance can use it
independently of the others: TimerC virtualizes the underlying
hardware clock into N separate timers.

Some abstractions, however, are not well suited to virtualization:
programs need the control provided by a physical abstraction. For
example, components in 1.x share a single communication stack,
GenericComm.  GenericComm can only handle one outgoing packet at a
time. If a component tries to send a packet when GenericComm is
already busy, then the call returns FAIL. The component needs a way to 
tell when GenericComm is free so it can retry. TinyOS
1.x provides the mechanism of a global completion event which is
signaled whenever a packet send completes. Interested components can
handle this event and retry.

This approach to physical (rather than virtualized) abstractions 
has several drawbacks:

- If you need to make several requests, you have to handle the
  possibility of a request returning FAIL at any point. This complicates  
  implementations by adding internal states.

- You have no control over the timing of a sequence of operations. One
  example of when this can be a problem is timing-sensitive use of an 
  A/D converter.  You need a way to pre-reserve the use of the ADC so
  that its operations can be run at the exact moment they are desired.

- If a hardware resource supports reservation, you cannot express this
  via this software interface. For instance, I2C buses have a
  concept of "repeated start" when doing multiple bus transactions,
  but it is not clear how to use this in TinyOS 1.x's I2C abstraction.

- Most TinyOS 1.x services do not provide a very convenient way of
  monitoring an abstraction's availability for the purpose of retries,
  nor very clear documentation of which requests could happen simultaneously.

It should be clear that a single approach to resource sharing is not appropriate 
for all circumstances. For instance, requiring explicit reservation of a
resource allows programs to have better timing guarantees for access to an A/D
converter. If a program does not need precise timing guarantees, however (e.g.,
when measuring temperature in a biological monitoring application), this extra
resource reservation step unnecessarily complicates code and can be handled
nicely using virtualization. The following section introduces the concept of
resource classes in order to address this issue.  The sharing policy used by a
particular resource abstraction is dictated by the resource class it belongs to.

2. Resource Classes
====================================================================

TinyOS 2.x distinguishes between three kinds of abstractions: 
*dedicated*, *virtualized*, and *shared*.  Components offer resource 
sharing mechanisms appropriate to their goals and level of abstraction.

.. Note::
  It is important to point out that Hardware Presentation Layer (HPL)
  components of the HAA [1]_ can never be virtualized, as virtualization
  inevitably requires state. Depending on their
  expected use, HPL abstractions can either be dedicated or
  shared. For example, while hardware timers are rarely
  multiplexed between multiple components, buses almost always are.
  This can be seen on the MSP430 microcontroller, where the compare and 
  counter registers are implemented as dedicated resources, and the USARTs 
  are shared ones.

2.1 Dedicated
-------------------------------

An abstraction is *dedicated* if it is a resource
which a subsystem needs exclusive access to at all times. 
In this class of resources, no sharing policy is needed since only 
a single component ever requires use of the resource.  Examples of
dedicated abstractions include interrupts and counters.

Dedicated abstractions MAY be annotated with the nesC attribute 
@atmostonce or @exactlyonce to provide compile-time checks that
their usage assumptions are not violated.

Please refer to Appendix A for an example of how a dedicated 
resource might be represented, including the use of 
the nesC @exactlyonce attribute.

2.2 Virtualized
-------------------------------

*Virtual* abstractions hide multiple clients from each other
through software virtualization. Every client of a virtualized resource 
interacts with it as if it were a dedicated resource, with all virtualized
instances being multiplexed on top of a single underlying resource. Because
the virtualization is done in software, there is no upper bound on the number
of clients using the abstraction, barring memory or efficiency constraints.
As virtualization usually requires keeping state that scales with the number 
of virtualized instances, virtualized resources often use the Service Instance 
pattern [3]_, which is based on a parameterized interface.

Virtualization generally provides a very simple interface to its clients.  
This simplicity comes at the cost of reduced efficiency and an inability to 
precisely control the underlying resource. For example, a virtualized
timer resource introduces CPU overhead from dispatching and maintaining 
each individual virtual timer, as well as introducing jitter whenever two 
timers happen to fire at the same time. Please refer to Appendix A for an 
example of how such a virtualized timer resource might be implemented.

2.3 Shared
-------------------------------

Dedicated abstractions are useful when a resource is
always controlled by a single component. Virtualized abstractions are
useful when clients are willing to pay a bit of overhead and sacrifice
control in order to share a resource in a simple way. There are
situations, however, when many clients need precise control of a
resource. Clearly, they can't all have such control at the same time:
some degree of multiplexing is needed.

A motivating example of a shared resource is a bus.
The bus may have multiple peripherals on it, corresponding to 
different subsystems. For example, on the Telos platform the flash
chip (storage) and the radio (network) share a bus. The storage and
network stacks need exclusive access to the bus when using it,
but they also need to share it with the other subsystem. In this
case, virtualization is problematic, as the radio stack needs to be
able to perform a series of operations in quick succession without
having to reacquire the bus in each case. Having the bus be a
shared resource allows the radio stack to send a series of operations 
to the radio atomically, without having to buffer them all up 
in memory beforehand (introducing memory pressure in the process).

In TinyOS 2.x, a resource *arbiter* is responsible for multiplexing
between the different clients of a shared resource. It determines 
which client has access to the resource at which time. While a client 
holds a resource, it has complete and unfettered control. Arbiters assume 
that clients are cooperative, only acquiring the resource when needed 
and holding on to it no longer than necessary. Clients explicitly 
release resources: there is no way for an arbiter to forcibly reclaim it.
The following section is dedicated to describing the arbiter and its 
interfaces.

3. Resource Arbiters
====================================================================

Every shared resource has an arbiter to manage which client
can use the resource at any given time. Because an arbiter is a
centralized place that knows whether the resource is in use, it can also
provide information useful for a variety of other services, such as
power management. An arbiter MUST provide a parameterized Resource
interface as well as an instance of the ArbiterInfo interface. The Resource
interface is instantiated by different clients wanting to gain access to a 
resource.  The ArbiterInfo interface is used by components that wish to 
retrieve global information about the status of a resource (i.e. if it is in 
use, who is using it, etc.).  An arbiter SHOULD also provide a parameterized 
ResourceRequested interface and use a parameterized ResourceConfigure interface. 
It MAY also provide an instance of the ResourceDefaultOwner interface or 
any additional interfaces specific to the particular arbitration policy 
being implemented.  Each of these interfaces is explained in greater detail below::

 Resource     ArbiterInfo ResourceRequested     ResourceDefaultOwner 
    |                |         |                        |
    |                |         |                        |
    |               \|/       \|/                       |
    |             \---------------/                     |
    |--------------|   Arbiter   |----------------------|
                  /---------------\
                          |
                          |      
                         \|/
                   ResourceConfigure
                                
3.1 Resource
-------------------------------

Clients of an arbiter request access 
to a shared resource using the Resource interface::

  interface Resource {
    async command error_t request();
    async command error_t immediateRequest();
    event void granted();
    async command error_t release();
    async command bool isOwner();
  }
  
A client lets an arbiter know it needs access to a resource by 
making a call to request(). If the resource is free,
SUCCESS is returned, and a granted event is signaled 
back to the client.  If the resource is busy, SUCCESS will 
still be returned, but the request will be queued 
according to the queuing policy of the arbiter. Whenever a client is 
done with the resource, it calls the release() command, and the next 
client in the request queue is given access to the resource and 
is signaled its granted() event. If a client ever makes multiple 
requests before receiving a granted event, an EBUSY value is returned, 
and the request is not queued.  Using this policy, clients are not able to 
monolopize the resource queue by making multiple requests, but they may still be
able to monopolize the use of the resource if they do not release it in a 
timely manner.

Clients can also request the use of a resource through the 
immediateRequest() command.  A call to immediateRequest() can either 
return SUCCESS or FAIL, with requests made through this command never being 
queued.  If a call to immediateRequest() returns SUCCESS, the client is granted 
access to the resource immediately after the call has returned, and no granted 
event is ever signaled.  If it returns FAIL, the client is not granted access to 
the resource and the request does not get queued.  The client will have to try 
and gain access to the resource again later.  

A client can use the isOwner command of the Resource interface to 
check if it is the current owner of the resource.  This command is mostly 
used to perform runtime checks to make sure that clients not owning a resource
are not able to use it.  If a call to isOwner fails, then no call
should be made to commands provided by that resource.

The diagram below shows how a simple shared resource can be 
built from a dedicated resource by using just the Resource interface 
provided by an arbiter.::

           /|\                    /|\
            |                      |
            | Data Interface       | Resource
            |                      |  
  --------------------------------------------
  |               Shared Resource            |
  --------------------------------------------
           /|\                    /|\
            |                      |
            | Data Interface       | Resource
            |                      |
  ----------------------      ----------------
  | Dedicated Resource |      |    Arbiter   |
  ----------------------      ----------------

An arbiter MUST provide exactly one parameterized Resource interface,
where the parameter is a client ID, following the Service
Instance pattern[3]_.  An arbitrated component SomeNameP MUST
#define SOME_NAME_RESOURCE to a string which can be passed to unique() 
to obtain a client id.  This #define must be placed in a separate file
because of the way nesC files are preprocessed: including the
SomeNameP component isn't enough to ensure that macros #define'd in
SomeNameP are visible in the referring component.

Please refer to Appendix B for an example of how to wrap a component of this type