tep106.txt

tinyos-2.x.rar

within the scheduler improves the efficiency of the task loop,
in terms of the assembly generated by the TinyOS toolchain. 

This is the TaskBasic interface::

  interface TaskBasic {  
    async command error_t postTask();  
    void event runTask();  
  }  

When a component declares a task with the ``task`` keyword in nesC, it
is implicitly declaring that it uses an instance of the TaskBasic
interface: the task body is the runTask event. When a component uses the
``post`` keyword, it calls the postTask command. Each TaskBasic MUST be
wired to the scheduler with a unique identifier as its parameter. 
The parameter MUST be obtained with the ``unique`` function in nesC, 
with a key of ``"TinySchedulerC.TaskBasic"``. The nesC compiler
automatically does this wiring when the ``task`` and ``post``
keywords are used.

The SchedulerBasicP implementation uses these identifiers as its queue
entries. When TinyOS tells the scheduler to run a task, it pulls the
next identifier off the queue and uses it to dispatch on the
parameterized TaskBasic interface.

While the default TinyOS scheduler uses a FIFO policy, TinyOS
components MUST NOT assume a FIFO policy. If two tasks must run
in a particular temporal order, this order should be enforced by
the earlier task posting the later task.

5. Replacing the Scheduler
====================================================================

The TinyOS scheduler is presented as a component named TinySchedulerC.
The default TinyOS scheduler implementation is a module named
SchedulerBasicP; the default scheduler component is a configuration
that provides wire-through of SchedulerBasicP.

To replace the scheduler for a particular application, a developer
SHOULD put a configuration named TinySchedulerC in the application
directory: this will replace the default. The scheduler component
provides a wire-through of the desired scheduler implementation. All
scheduler implementations MUST provide a parameterize TaskBasic
interface, as SchedulerBasicP does; this supports nesC post statements
and task declarations and enables TinyOS core systems to operate
properly. Generally, TinyOS core code needs to be able to run unchanged
with new scheduler implementations.  All scheduler 
implementations MUST provide the Scheduler interface.

For example, imagine a hypothetical scheduler that provides earliest
deadline first tasks, which are provided through the TaskEdf
interface::

  interface TaskEdf {  
    async command error_t postTask(uint16_t deadlineMs);  
    event void runTask();  
  }  

The scheduler implementation is named SchedulerEdfP, and provides both
TaskBasic and TaskEdf interfaces::

  module SchedulerEdfP {  
    provides interface Scheduler;  
    provides interface TaskBasic[uint8_t taskID];  
    provides interface TaskEdf[uint8_t taskID];  
  }  

An application that wants to use SchedulerEdfP instead of
SchedulerBasicP includes a configuration named TinySchedulerC, which
exports all of SchedulerEdfP's interfaces::

  configuration TinySchedulerC {  
    provides interface Scheduler;  
    provides interface TaskBasic[uint8_t taskID];  
    provides interface TaskEdf[uint8_t taskID];  
  }  
  implementation {  
    components SchedulerEdfP;  
    Scheduler = SchedulerEdf;  
    TaskBasic = SchedulerEdfP;  
    TaskEDF   = SchedulerEdfP;  
  }  

For a module to have an earliest deadline first task, it uses the
TaskEdf interface. Its configuration SHOULD wire it to TinySchedulerC.
The key used for task unique identifiers MUST be "TinySchedulerC.TaskInterface",
where *TaskInterface* is the name of the new task interface as presented
by the scheduler.  A common way to make sure a consistent string is used
is to #define it. For example, TaskEdf.nc might include::

#define UQ_TASK_EDF "TinySchedulerC.TaskEdf"

In this example, the module SomethingP requires two EDF
tasks::
  
  configuration SomethingC {  
    ...  
  }  
  implementation {  
    components SomethingP, TinySchedulerC;  
    SomethingP.SendTask -> TinySchedulerC.TaskEdf[unique(UQ_TASK_EDF)];  
    SomethingP.SenseTask -> TinySchedulerC.TaskEdf[unique(UQ_TASK_EDF)];  
  }  

The module SomethingP also has a basic task. The nesC compiler
automatically transforms task keywords into BasicTask interfaces and
wires them appropriately. Therefore, for basic tasks, a component
author can either use the ``task`` and ``post`` keywords or use a TaskBasic
interface. A component SHOULD use the keywords whenever possible, and it
MUST NOT mix the two syntaxes for a given task.  This is an example
implementation of SomethingP that uses keywords for basic tasks::

  module SomethingP {  
    uses interface TaskEdf as SendTask  
    uses interface TaskEdf as SenseTask  
  }  
  implementation {  
    // The TaskBasic, written with keywords  
    task void cleanupTask() { ... some logic ... }  
    event void SendTask.runTask() { ... some logic ... }  
    event void SenseTask.runTask() { ... some logic ... }  

    void internal_function() {  
      call SenseTask.postTask(20);  
      call SendTask.postTask(100);  
      post cleanupTask();  
    }  
  }  

The requirement that basic tasks not be subject to starvation
requires that a scheduler supporting EDF tasks must ensure that
basic tasks run eventually even if there is an unending stream of
short deadline tasks to run. Quantifying "eventually" is difficult,
but a 1% share of the MCU cycles (or invocations) is a reasonable 
approximation. 

If the scheduler provides two instances of the same task interface,
their unique keys are based on the name of the interface as the 
scheduler presents it (the "as" keyword). For example, imagine
a scheduler which provides two instances of TaskBasic: standard
tasks and high-priority tasks. The scheduler usually selects a task
for the high priority queue before the standard queue::

  configuration TinySchedulerC {  
    provides interface Scheduler;  
    provides interface TaskBasic[uint8_t taskID];  
    provides interface TaskBasic[uint8_t taskID] as TaskHighPriority;  
  }  

It cannot always select a high priority task because that could
starve basic tasks.  A component that uses a high priority task would 
wire to TaskHighPriority with the key "TinySchedulerC.TaskHighPriority"::

  configuration SomethingElseC {}  
  implementation {  
    components TinySchedulerC as Sched, SomethingElseP;  
    SomethingElseP.RetransmitTask -> Sched.TaskHighPriority[unique("TinySchedulerC.TaskHighPriority")];  
  }  

6. Implementation
====================================================================

The following files in ``tinyos-2.x/tos/system`` contain the reference
implementations of the scheduler:
 
  * ``SchedulerBasicP.nc`` is the basic TinyOS scheduler, providing
    a parameterized TaskBasic interface. 
  * ``TinySchedulerC.nc`` is the default scheduler configuration
    that wires SchedulerBasicP to McuSleepC [3]_.


A prototype of a scheduler that supports EDF tasks can be obtained
at the URL ``http://csl.stanford.edu/~pal/tinyos/edf-sched.tgz.``

7. Author's Address
====================================================================

| Philip Levis
| 358 Gates Hall
| Stanford University
| Stanford, CA 94305
|
| phone - [phone] 
| email - [e-mail]
|
| Cory Sharp
| 410 Soda Hall
| UC Berkeley
| Berkeley, CA 94720
|
| email - [e-mail]

8. Citations
====================================================================

.. [1] Erik Cota-Robles and James P. Held.  "A Comparison of Windows 
   Driver Model Latency Performance on Windows NT and Windows 98." In
   *Proceedings of the Third Symposium on Operating System Design
   and Implementation (OSDI).*

.. [2] David Gay, Philip Levis, Rob von Behren, Matt Welsh, Eric Brewer
   and David Culler. "The *nesC* Language: A Holistic Approach to Networked
   Embedded Systems." In *Proceedings of the ACM SIGPLAN 2003 Conference on
   Programming Language Design and Implementation (PLDI).* 

.. [3] TEP 112: Microcontroller Power Management.

 
Appendix A: Changing the Scheduler
====================================================================

The nesC compiler transforms the   post   and   task   keywords into
nesC interfaces, wirings, and calls. By default, the statement::

  module a {
    ...
  }
  implementation {
    task x() {
      ...
      post x();
    } 
  
  }


is effectively::

  module a {
    ...
    provides interface TaskBasic as x;
  }
  implementation {
    event void x.runTask() {
      ...
      call x.postTask();
    }
  }

Specifically, TinyOS maps a task with name *T* to a TaskBasic
interface with name *T*. Posting *T* is a call to T.postTask(), and
the task body is T.runTask(). Finally, *T* is automatically wired to
TinySchedulerC with a unique() call.

While the fact that tasks are transformed into interfaces is built in
to the nesC compiler, the exact names can be configured. Each
platform's   .platform   file passes the   -fnesc-scheduler   option
to the compiler. The standard option is::

  -fnesc-scheduler=TinySchedulerC,TinySchedulerC.TaskBasic,TaskBasic,TaskBasic,runTask,postTask

There are 6 strings passed. They are:

  1) The name of the scheduler component to wire the interface
     to (TinySchedulerC).
  2) The unique string used when wiring to the scheduler component's
     parameterized interface (TinySchedulerC.TaskBasic).
  3) The name of the interface on the scheduler component (TaskBasic).
  4) The name of the interface type (TaskBasic).
  5) The name of the event for running the task (runTask).
  6) The name of the command for posting the task (postTask).


The nescc man page has further details.