[Tinyos-2.0wg] TinyOS 2.x WG/07.5.2006 Meeting Notes

[Kevin Klues]

Based on many many discussions about the proper interfaces to have for
performing resource arbitration in tinyos-2.x, the folllowing interfaces are
now being proposed.  There have been many arguments as to whether the
existence of immediateRequest is necssary in the Resource interface since
its presence can complicate the state machine of the arbiter when a resource
controller is present.  The "new" interfaces defined below provide a way to
keep immediateRequest around, by reducing the overhead it brings to the
state machine in the Arbiter.  As you will see, there are, in fact no
changes to the existing Resource interface (which is good since now none of
the code using the Resource interface will have to change).  The changes are
in the ResourceController interface, and the introduction of a
ResourceRequested interface.

Interface Definitions

interface Resource {
  async command error_t request();
  async command error_t immediateRequest();
  event void granted();
  async command error_t release();
  async command bool isOwner();
}

interface ResourceController {
  async event void granted();
  async command error_t release();
  async command bool isOwner();
  async event void requested();
  async event void immediateRequested();
}

interface ResourceRequested {
  async event void requested();
  async event void immediateRequested();
}

The ResourceController interface has been changed in the following ways:

   - the request() and immediateRequest commands have been removed
   - the idle() event has been replaced by the granted() event
   - a separate immediateRequested() event has been introduced to
   distinguish requests made by normal clients using the request() or the
   immediateRequest() command


These changes have been motivated by the fact that a ResourceController
should always gain control of a resource immediately after the last client
has released it.  Previously, after the final release, an idle event would
be sent back to the component using the ResourceController interface and it
would have to explicitly call either request or immediateRequest to gain
access to the resource.  This introduced a tiny window of time in which the
resource went idle before the ResourceController would take it over.
Because of this small window of availability, it was possible that
asynchronous calls to request/immediateRequest could occur between the
resource going idle and the ResourceController taking it over.  In a sense,
the ResourceContoller would be competing for the resource just like any
other resource client.  With these new interfaces, this is no longer
possible. Instead, the ResourceController will be granted immediate access
to the resource, and it will be signalled the ResourceController.granted()
event.  With this new definiton of the ResourceController interface, there
is no true idle state of the arbiter.  It is always owned by someone at some
point.

A new immediateRequested() event has also been added to the
ResourceController interface.  The fact that normal requests are queued and
immediateRequests are not allows the user of the ResourceController
interface to distinguish between them.  For example, a PowerManager
requiring a split phase power up operation may decide to power a device up
based on a normal requested() event since a granted event can be deferred to
this user until some later point in time.  immediateRequested() events may
need to either be ignored or follow some other sort of semantics, however,
as they have tighter time constraints and need to return either SUCCESS or
FAIL immediately.  Previously, it was necessary to keep extra state both
inside tha power manager as well as in the Arbiter itself in order to take
the appropriate action based on the two types of requests.  By adding this
extra event, the state machines in both components are simplified
significantly.

Having a ResourceController that gets control of the resource whenever it
would normally go idle may not necessarily be only component that could
benefit from the use of the requested and immediateRequested events.  For
this reason, the ResourceRequested interface has been introduced.  As can be
seen in the arbiter signatures given below, a parameterized
ResourceRequested interface can be provided along side the normal Resource
interface and wired to by normal clients.  Providing this interface allows
components using it to react on the these events and possibly release the
resource if somone else requests it.  With this parameterized interface
present it's possible to implement a sort of high priority user that always
gets access to the resource if it wants to and holds onto it as long as it
wants to (no preemption, rather that it jumps to the front of the queue if
it makes a request).  It can use the information provided by the
ResourceRequested interface to decide if/when it wants to release it.
Implementing such a policy can be done inside the implementation of a
separate Queue component without any changes needed to the actual Arbiter
itself.

Arbiter Signatures

generic module ArbiterP() {
  provides {
    interface Resource[uint8_t id];
    interface ResourceRequested[uint8_t id];
    interface ArbiterInfo;
  }
  uses {
    interface ResourceConfigure[uint8_t id];
    interface AsyncQueue<uint8_t> as Queue;
  }
}

generic module ControlledArbiterP(uint8_t controller_id) {
  provides {
    interface Resource[uint8_t id];
    interface ResourceRequested[uint8_t id];
    interface ResourceController;
    interface ArbiterInfo;
  }
  uses {
    interface ResourceConfigure[uint8_t id];
    interface AsyncQueue<uint8_t> as Queue;
  }
}

generic configuration ControlledFcfsArbiterC(char resourceName[]) {
  provides {
    interface Resource[uint8_t id];
    interface ArbiterInfo;
  }
  uses interface ResourceConfigure[uint8_t id];
}
implementation {
  components MainC;
  components new AsyncFcfsQueueC(uniqueCount(resourceName)) as Queue;
  components new ControlledArbiterP(uniqueCount(resourceName)) as Arbiter;

  MainC.SoftwareInit -> Queue;

  Resource = Arbiter;
  ArbiterInfo = Arbiter;
  ResourceConfigure = Arbiter;

  Arbiter.Queue -> Queue;
}

Just as the AsyncFcfsQueueC component is wired into this arbiter, a priority
queue imlementation could be made based on Resource id.  Or even a policy in
which the first user (id=0) is a "high priority" user who always sits at the
top of the queue if he's put a request in while everyone else runs in Fcfs
order (this is what is currently required by the eyes platform).  The point
is though, that it is a matter of changing the queuing component rather than
the arbiter itself.  The last hurdle involves ensuring that the proper
compoentn receives id 0 when uniques are intermixed with this explicit
priority user at id==0.

------------------------------------------------------------
------------------------------------------------------------

I'm sure I may have missed some things in this email, but I think the basic
ideas are all here now.  Feel free to make comments and suggest improvements
as necessary.

Kevin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.millennium.berkeley.edu/pipermail/tinyos-2.0wg/attachments/20060707/5fa3b2db/attachment.htm