<!DOCTYPE doctype PUBLIC "-//w3c//dtd html 4.0 transitional//en">\r
<html>\r
<head>\r
- <title>TinyOS Tutorial Lesson 8: Concurrency in TinyOS</title>\r
+ <title>TinyOS Tutorial Lesson 8: Resource Arbitration and Power Management </title>\r
<link href="../../stylesheets/tutorial.css" rel="stylesheet" type="text/css">\r
</head>\r
<body>\r
\r
-<div class="title">Lesson 2: </div>\r
-<div class="subtitle">Last updated 29 January 2006</div>\r
-\r
-<p>Commands and events that are executed as part\r
-of a hardware event handler must be declared with the <b>async</b>\r
-keyword (more about the async keyword in Lesson 8). </p>\r
-\r
-<p>Because tasks and hardware event handlers may be preempted by other\r
-asynchronous code, nesC programs are susceptible to certain race\r
-conditions. Races are avoided either by accessing shared data\r
-exclusively within tasks, or by having all accesses within <b>atomic</b>\r
-statements. The nesC compiler reports potential <b>data races</b> to the\r
-programmer at compile-time. It is possible the compiler may report a\r
-false positive. In this case a variable can be declared with the <b>norace</b>\r
-keyword. The norace keyword should be used with extreme caution. </p>\r
-\r
-<p>Please see the <a href="../../doc/nesc/ref.pdf">nesC Language\r
-Reference Manual</a> for more information on programming in nesC. <br>\r
-
\ No newline at end of file
+<div class="title">Lesson 8: Resource Arbitration and Power Management </div>\r
+<div class="subtitle">Last updated 30 October 2006</div>
+
+<h1>Introduction</h1>
+
+<p>
+TinyOS distinguishes between three kinds of resource abstractions: <b>dedicated</b>, <b>virtualized</b>, and <b>shared</b>. Two fundamental questions must be asked about each type of abstraction.
+<ol>
+<li>How can a client gain access to the resource provided through this abstraction?</li>
+<li>How can the power state of that resource be controlled?</li>
+</ol>
+Components offer resource sharing mechanisms and power mangement capabilites according to the goals and level of abstraction required by their clients.
+</p>
+
+<hr>
+
+<p>
+An abstraction is dedicated if it represents 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. Resource clients simply call commands from the interfaces provided by the resource just as they would with any other TinyOS component. Resources of this type provide either an <tt>AsyncStdControl</tt>, <tt>StdControl</tt>, or <tt>SplitControl</tt> interface for controlling their power states. The definition of each of these interfaces can be found in <tt>tinyos-2.x/tos/interfaces</tt>.
+</p>
+
+<pre>
+interface AsyncStdControl {
+ async command error_t start();
+ async command error_t stop();
+}
+</pre>
+
+<pre>
+interface StdControl {
+ command error_t start();
+ command error_t stop();
+}
+</pre>
+
+<pre>
+interface SplitControl {
+ async command error_t start();
+ async command void startDone(error_t error);
+ async command error_t stop();
+ async command void stopDone(error_t error);
+}
+</pre>
+
+<p>
+Currently, the power states of all dedicated resources are controlled by one of these three interfaces. They are only allowed to enter one of two logical power states (on/off), regardless of the number of physical power states provided by the hardware on top of which their resource abstraction has been built. Which of these interfaces is provided by a particular resource depends on the timing requirements for physically powering it on or off.
+<p>
+
+<hr>
+
+<p>
+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. The power states of a virtualized resource are handled automatically, and no interface is provided to the user for explicity controlling its power state. As they are built on top of shared resources, the reason their power states can be automatically controlled will become clearer after reading the following section.
+</p>
+
+<hr>
+
+<p>
+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.
+</p>
+
+<p>
+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).
+</p>
+
+<p>
+In TinyOS, a resource <b>arbiter</b> 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.
+</p>
+
+<p>
+Shared resources are essentially built on top of dedicated resources, with access to them being controlled by an arbiter component. In this way, <b>power managers</b> can be used to automatically control the power state of these resources through their <tt>AsyncStdControl</tt>, <tt>StdControl</tt>, or <tt>SplitControl</tt> interfaces. They communicate with the arbiter (through the use of a <tt>ResourceController</tt> interface), monitoring whether the resource is being used by any of its clients and powering it on/off accordingly. The figure below shows how an arbiter component and a power manager can be wired together to provide arbitration and automatic power management for a shared resource.
+</p>
+
+<center>
+<img src="img/arbiter_pm_graph.png",
+ alt="This is a picture of how an arbiter and power manager work together",
+ height=225
+ center
+></img><br>
+Figure 1: Arbiters and Power Managers
+</center>
+
+<p>
+The arbiter component provides the <tt>Resource</tt>, <tt>ArbiterInfo</tt>, <tt>ResourceRequested</tt>, and <tt>ResourceController</tt> interfaces and uses the <tt>ResourceConfigure</tt> interface. The power manager doesn't provide any interfaces, but uses one of either the <tt>AsyncStdControl</tt>, <tt>StdControl</tt>, or <tt>SplitControl</tt> interfaces from the underlying resource, as well as the <tt>ResourceController</tt> interface provided by the arbiter. The figure below shows how these interface are then wired together with the implementation of a shared resource. Please refer to TEP 108 for more information on arbiters and TEP 115 for more information on Power Managers.
+</p>
+
+<center>
+<img src="img/shared_resource_graph.png",
+ alt="This is a picture of how a shared resource works together with an arbiter and a power manager",
+ height=450
+ center
+></img><br>
+Figure 2: Shared Resource Configuration
+</center>
+
+<p>
+From this figure, we see that the only interfaces exposed to a client through the shared resource abstraction are the <tt>Resource</tt> and <tt>ResourceRequested</tt> interfaces provided by the arbiter as well as any resource specific interfaces provided by the resource itself. It also uses a <tt>ResourceConfigure</tt> interface, expecting it to be implemented on a client by client basis depending on their requirements. A client requests access to a shared resource through the <tt>Resource</tt> interface and runs operations on it using whatever resource specific interfaces are provided. A client may choose to wire itself to the <tt>ResourceRequested</tt> interface if it wishes to hold onto a resource indefinitely and be informed whenever other clients request its use.
+</p>
+
+<p>
+The rest of this tutorial is dedicated to teaching users how to use shared resources and show them how wiring is done between all components that make them up.</p>
+<p>
+Specifically, this tutorial will teach users how to:
+<ol>
+<li> Wire in a shared resource for use by a client.
+<li> Use the <tt>Resource</tt> interface to gain access to a shared resource.</li>
+<li> Change the arbitration policy used by a particular shared resource.</li>
+<li> Wire up a power manager for use by a shared resource.</li>
+</ol>
+</p>
+
+<h1>Working with Shared Resources</h1>
+<p>This section shows you how to gain access to and use shared resources in TinyOS. It walks through the process of making a request through the <code>Resource</code> interface and handling the <tt>granted</tt> event that is signaled back. We will connect multiple clients to a single shared resources and see how access to each of them gets arbitrated. We also show how to hold onto a resource until another client has requested it by implementing the <tt>ResourceRequested</tt> interface.
+</p>
+
+<p>To begin, go to the <tt>tinyos-2.x/apps/tests/TestSharedResource</tt> directory and install this application on a mote. After installing the application you should see three leds flashing in sequence.</p>
+
+<p>Let's take a look at the different components contained in this directory to see whats going on. Start with the top level application component: <code>TestSharedResourceAppC</code></p>
+
+<pre>
+configuration TestSharedResourceAppC{
+}
+implementation {
+ components MainC,LedsC, TestSharedResourceC as App,
+ new TimerMilliC() as Timer0,
+ new TimerMilliC() as Timer1,
+ new TimerMilliC() as Timer2;
+ App -> MainC.Boot;
+ App.Leds -> LedsC;
+ App.Timer0 -> Timer0;
+ App.Timer1 -> Timer1;
+ App.Timer2 -> Timer2;
+
+ components
+ new SharedResourceC() as SharedResource0,
+ new SharedResourceC() as SharedResource1,
+ new SharedResourceC() as SharedResource2;
+ App.Resource0 -> SharedResource0;
+ App.Resource1 -> SharedResource1;
+ App.Resource2 -> SharedResource2;
+ App.ResourceOperations0 -> SharedResource0;
+ App.ResourceOperations1 -> SharedResource1;
+ App.ResourceOperations2 -> SharedResource2;
+}
+</pre>
+
+<p>Other than the instantiation and wiring of the interfaces provided by the <code>SharedResourceC</code> component, this configuration is identical to the one presented in Lesson 1 for the Blink Application.</p>
+
+<p>All shared resources in TinyOS are provided through a generic component similar to the <code>SharedResourceC</code> component. A resource client simply instantiates a new instance of this component and wires to the interfaces it provides. In this application, three instances of the <code>SharedResourceC</code> component are instantiated and wired to three different clients from the <code>TestSharedResourceC</code> component. Each instantiation provides a <tt>Resource</tt>, <tt>ResourceOperations</tt>, and <tt>ResourceRequested</tt> interface, and uses a <tt>ResourceConfgigure</tt> interface. In this example, no wiring is done to the <tt>ResourceConfigure</tt> or <tt>ResourceRequested</tt> interface as wiring to to these interfaces is optional. The <tt>ResourceOperations</tt> interface is an <b>EXAMPLE</B> of a resource specific interface that a resource may provide to perform operations on it. Calls to commands through this interface will only succeed if the client calling them happens to have access to the resource when they are called.
+</p>
+
+<p>Let's take a look at the <code>TestSharedResourceC</code> to see how access is actually granted to a Resource.
+</p>
+
+<pre>
+module TestSharedResourceC {
+ uses {
+ interface Boot;
+ interface Leds;
+ interface Timer<TMilli> as Timer0;
+ interface Timer<TMilli> as Timer1;
+ interface Timer<TMilli> as Timer2;
+
+ interface Resource as Resource0;
+ interface ResourceOperations as ResourceOperations0;
+
+ interface Resource as Resource1;
+ interface ResourceOperations as ResourceOperations1;
+
+ interface Resource as Resource2;
+ interface ResourceOperations as ResourceOperations2;
+ }
+}
+</pre>
+
+<p>Each pair of <code>Resource/ResourceOperations</code> interfaces reperesents a different client of the shared resource used by this application. At boot time, we put in a request for the shared resource through each of these clients in the order (0,2,1).</p>
+
+<pre>
+event void Boot.booted() {
+ call Resource0.request();
+ call Resource2.request();
+ call Resource1.request();
+}
+</pre>
+
+<p>Each of these requests is serviced in the order of the arbitration policy used by the shared resource. In the case of <code>SharedResourceC</code>, a Round-Robin policy is used, so these requests are serviced in the order (0,1,2). If a first-come-first-serve policy were in use, they would we be serviced in the order the were put in, i.e. (0,2,1).</p>
+
+<p>Whenever a client's request for a resource has been granted, the <code>Resource.granted()</code> event for that client gets signaled. In this application, the body of the granted event for each client simply performs an operation on the resource as provided through the <code>ResourceOperations</code> interface.</p>
+
+<pre>
+event void Resource0.granted() {
+ call ResourceOperations0.operation();
+}
+event void Resource1.granted() {
+ call ResourceOperations1.operation();
+}
+event void Resource2.granted() {
+ call ResourceOperations2.operation();
+}
+</pre>
+
+<p>Whenever one of these operations completes, a <code>ResourceOperations.operationDone()</code> event is signaled. Once this event is received by each client, a timer is started to hold onto the resource for 250 (binary) ms and an LED corresponding to that client is toggled.</p>
+
+<pre>
+#define HOLD_PERIOD 250
+
+event void ResourceOperations0.operationDone(error_t error) {
+ call Timer0.startOneShot(HOLD_PERIOD);
+ call Leds.led0Toggle();
+}
+event void ResourceOperations1.operationDone(error_t error) {
+ call Timer1.startOneShot(HOLD_PERIOD);
+ call Leds.led1Toggle();
+}
+event void ResourceOperations2.operationDone(error_t error) {
+ call Timer2.startOneShot(HOLD_PERIOD);
+ call Leds.led2Toggle();
+}
+</pre>
+
+<p>Whenever one of these timers goes off, the client that started it releases the resource and immediately puts in a request for it again.</p>
+
+<pre>
+event void Timer0.fired() {
+ call Resource0.release();
+ call Resource0.request();
+}
+event void Timer1.fired() {
+ call Resource1.release();
+ call Resource1.request();
+}
+event void Timer2.fired() {
+ call Resource2.release();
+ call Resource2.request();
+}
+</pre>
+
+<p>In this way, requests are continuously put in by each client, allowing the application to continuously flash the LEDs in the order in which requests are being serviced. As stated before, the <code>SharedResourceC</code> component services these requests in a round-robin fashion. If you would like to see the requests serviced in the order they are received (and see the LEDs flash accordingly), you can open up the <code>SharedResourceP</code> component in the <tt>apps/tests/TestSharedResource</tt> directory and replace the <code>RoundRobinArbiter</code> component with the <code>FcfsArbiter</code> component.</p>
+
+<table>
+ <tr><td><b>RoundRobinArbiter</b></td><td width=10></td><td><b>FcfsArbiter</b></td></tr>
+ <tr><td>
+<pre>
+configuration SharedResourceP {
+ provides interface Resource[uint8_t id];
+ provides interface ResourceRequested[uint8_t id];
+ provides interface ResourceOperations[uint8_t id];
+ uses interface ResourceConfigure[uint8_t id];
+}
+implementation {
+ components new RoundRobinArbiterC(TEST_SHARED_RESOURCE) as Arbiter;
+ ...
+ ...
+}
+</pre>
+</td>
+<td></td>
+<td>
+<pre>
+configuration SharedResourceP {
+ provides interface Resource[uint8_t id];
+ provides interface ResourceRequested[uint8_t id];
+ provides interface ResourceOperations[uint8_t id];
+ uses interface ResourceConfigure[uint8_t id];
+}
+implementation {
+ components new FcfsArbiterC(TEST_SHARED_RESOURCE) as Arbiter;
+ ...
+ ...
+}
+</pre>
+</td>
+</tr>
+</table>
+</center>
+</table>
+
+<p>Looking through the rest of this component, you can see how its wiring matches the connections shown in Figure 2.</p>
+
+<pre>
+#define TEST_SHARED_RESOURCE "Test.Shared.Resource"
+configuration SharedResourceP {
+ provides interface Resource[uint8_t id];
+ provides interface ResourceRequested[uint8_t id];
+ provides interface ResourceOperations[uint8_t id];
+ uses interface ResourceConfigure[uint8_t id];
+}
+implementation {
+ components new RoundRobinArbiterC(TEST_SHARED_RESOURCE) as Arbiter;
+ components new SplitControlPowerManagerC() as PowerManager;
+ components ResourceP;
+ components SharedResourceImplP;
+
+ ResourceOperations = SharedResourceImplP;
+ Resource = Arbiter;
+ ResourceRequested = Arbiter;
+ ResourceConfigure = Arbiter;
+ SharedResourceImplP.ArbiterInfo -> Arbiter;
+ PowerManager.ResourceController -> Arbiter;
+
+ PowerManager.SplitControl -> ResourceP;
+ SharedResourceImplP.ResourceOperations -> ResourceP;
+}
+</pre>
+
+<p>
+Four different components are instantiated by this configuration:
+</p>
+
+<pre>
+components new RoundRobinArbiterC(TEST_SHARED_RESOURCE) as Arbiter;
+components new SplitControlPowerManagerC() as PowerManager;
+components ResourceP;
+components SharedResourceImplP;
+</pre>
+
+<p>
+As we've already seen, the <tt>RoundRobinArbiterC</tt> component is used to provide arbitration between clients using <tt>SharedResourceC</tt>. The <tt>SplitControlPowerManagerC</tt> component is used to perform automatic power management of the resource to turn it on whenever a new client requests its use and shut it down whenever it goes idle. The <tt>ResourceP</tt> component is the implementation of a dedicated resource which provides a <tt>SplitControl</tt> interface and a <tt>ResourceOperations</tt> interface. This dedicated resource is wrapped by the <tt>SharedResourceImplP</tt> component in order to provide protected shared access to it. <tt>SharedResourceImplP</tt> wraps all the commands provided by the dedicated resource, and uses the <tt>ArbiterInfo</tt> interface to keep clients from calling them without first being granted access to the resource.
+</p>
+
+<p>
+If you would like to see more examples of how to use the different arbiters and power managers provided in the default TinyOS distribution, please refer to the test applications located in <tt>tinyos-2.x/apps/tests/TestArbiter</tt> and <tt>tinyos-2.x/apps/tests/TestPowerManager</tt>. This tutorial has provided enough background information on how to use these components in order for you to sift through these applications on your own.
+</p>
+
+<h1>Conclusion</h1>
+<p>
+This tutorial has given an overview of how resource arbitration and mechanisms for performing power management on those resources is provided in TinyOS. It walked us through the steps necessary for:
+<ol>
+<li> Wiring in a shared resource for use by a client.
+<li> Using the <tt>Resource</tt> interface to gain access to a shared resource.</li>
+<li> Changing the arbitration policy used by a particular shared resource.</li>
+<li> Wrapping a dedicated resource and wiring in a power manager in order to create a shared resource.</li>
+</ol>
+</p>
+
+<p>
+While the power managers presented in this tutorial are powerful components for providing power management of shared reosurces, they are not the only power management mechanisms provided by TinyOS. Microcontroller power management is also preformed as outlined in TEP115. Whenever the task queue empties, the lowest power state that the microcontroller is capapble of dropping to is automatically calculated and then switched to. In this way, the user is not burdened with explicity controlling these power states. The cc1000 and cc2420 radio implementations also provide "Low Power Listening" (LPL) interfaces for controlling their duty cycles. Although the LPL interface used by each radio stack differs somewhat, they are both able to provide energy savings not achieveable through other means. Ultimately we would like to see the components providing this LPL interface implemented as power manager components for the "radio resource" and be wired to the radio in the same way as the other power managers described in this tutorial. The LPL implementation for the cc2420 can be found under <tt>tinyos-2.x/tos/chips/cc2420_lpl</tt> and the LPL implementation for the cc1000 can be found under <tt>tinyos-2.x/tos/chips/cc1000</tt>. As these interfaces begin to mature and merge into one, this tutorial will be updated appropriately to accomodate the change.
+</p>
+
+<!-- Related Docs -->
+<p>
+<a name=#related_docs>
+<h1>Related Documentation</h1>
+</a>
+<ul>
+<li> <a href="http://csl.stanford.edu/~pal/pubs/tinyos-programming-1-0.pdf">TinyOS Programming Guide
+ <i>Sections 6.2 and 7.4</i></a>
+<li> <a href="../tep108.html">TEP 108: Resource Arbitration</a>
+<li> <a href="../tep112.html">TEP 112: Microcontroller Power Management</a>
+<li> <a href="../tep115.html">TEP 115: Power Management of Non-Virtualized Devices</a>
+</ul>
+
+<p>
+<hr>
+
+<!-- Begin footer -->
+<br>
+<hr>
+<center>
+<p>< <b><a href="lesson7.html">Previous Lesson</a></b> | <b><a
+ href="index.html">Top</a></b> | <b><a href="lesson9.html">Next Lesson </a> ></b>
+</center>
+
+</body>
+</html>
projects / tinyos-2.x.git / commitdiff