dd {
margin-bottom: 0.5em }
-/* Uncomment (& remove this text!) to get bold-faced definition list terms
-dt {
- font-weight: bold }
-*/
-
div.abstract {
margin: 2em 5em }
<tr class="field"><th class="docinfo-name">Type:</th><td class="field-body">Documentary</td>
</tr>
<tr><th class="docinfo-name">Status:</th>
-<td>Draft</td></tr>
+<td>Final</td></tr>
<tr class="field"><th class="docinfo-name">TinyOS-Version:</th><td class="field-body">2.x</td>
</tr>
<tr><th class="docinfo-name">Author:</th>
<td>Philip Levis and Cory Sharp</td></tr>
-<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">10-Dec-2004</td>
-</tr>
-<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.1.2.9</td>
-</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2006-06-13</td>
-</tr>
-<tr class="field"><th class="docinfo-name">Draft-Discuss:</th><td class="field-body">TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu></td>
-</tr>
</tbody>
</table>
<div class="note">
<p>Using this task interface, a component could post a task with a
<tt class="docutils literal"><span class="pre">uint16_t</span></tt> parameter. When the scheduler runs the task, it will
signal the <tt class="docutils literal"><span class="pre">runTask</span></tt> event with the passed parameter, which contains
-the task's logic. Note, however, that this does not save any RAM: if
-anything, it will cost RAM as space must be allocated in the scheduler
-and may then also be allocated in the component. Furthermore, as
+the task's logic. Note, however, that this does not save any RAM:
+the scheduler must have RAM allocated for the parameter. Furthermore, as
there can only be one copy of a task outstanding at any time, it
is just as simple to store the variable in the component. E.g.,
rather than:</p>
</pre>
<p>A scheduler MUST provide a parameterized TaskBasic interface.
If a call to TaskBasic.postTask() returns SUCCESS, the scheduler MUST run it
-eventually. The scheduler MUST return SUCCESS to a TaskBasic.postTask()
+eventually, so that starvation is not a concern. The scheduler MUST
+return SUCCESS to a TaskBasic.postTask()
operation unless it is not the first call to TaskBasic.postTask() since
that task's TaskBasic.runTask() event has been signaled. The
McuSleep interface is used for microcontroller power management;
runNextTask(TRUE) always return TRUE. The taskLoop() command tells
the scheduler to enter an infinite task-running loop, putting the MCU
into a low power state when the processor is idle: it never returns.</p>
+<p>The scheduler is repsonsible for putting the processor to sleep
+predominantly for efficiency reasons. Including the sleep call
+within the scheduler improves the efficiency of the task loop,
+in terms of the assembly generated by the TinyOS toolchain.</p>
<p>This is the TaskBasic interface:</p>
<pre class="literal-block">
interface TaskBasic {
void event runTask();
}
</pre>
-<p>When a component declares a task with the task keyword in nesC, it
+<p>When a component declares a task with the <tt class="docutils literal"><span class="pre">task</span></tt> 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
<tt class="docutils literal"><span class="pre">post</span></tt> keyword, it calls the postTask command. Each TaskBasic MUST be
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.</p>
+<p>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.</p>
</div>
<div class="section">
<h1><a id="replacing-the-scheduler" name="replacing-the-scheduler">5. Replacing the Scheduler</a></h1>
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 SHOULD provide a parameterize TaskBasic
+scheduler implementations MUST provide a parameterize TaskBasic
interface, as SchedulerBasicP does; this supports nesC post statements
-and task declarations. If a scheduler does not provide the TaskBasic
-interface, compiling applications requires modifying the standard
-ncc scheduler parameters (as described in Appendix A). All scheduler
+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.</p>
<p>For example, imagine a hypothetical scheduler that provides earliest
deadline first tasks, which are provided through the TaskEdf
TaskEdf interface. Its configuration SHOULD wire it to TinySchedulerC.
The key used for task unique identifiers MUST be "TinySchedulerC.TaskInterface",
where <em>TaskInterface</em> is the name of the new task interface as presented
-by the scheduler. For example, the module SomethingP requires two EDF
+by the scheduler. A common way to make sure a consistent string is used
+is to #define it. For example, TaskEdf.nc might include:</p>
+<pre class="literal-block">
+#define UQ_TASK_EDF "TinySchedulerC.TaskEdf"
+</pre>
+<p>In this example, the module SomethingP requires two EDF
tasks:</p>
<pre class="literal-block">
configuration SomethingC {
}
implementation {
components SomethingP, TinySchedulerC;
- SomethingP.SendTask -> TinySchedulerC.TaskEdf["TinySchedulerC.TaskEdf"];
- SomethingP.SenseTask -> TinySchedulerC.TaskEdf["TinySchedulerC.TaskEdf"];
+ SomethingP.SendTask -> TinySchedulerC.TaskEdf[unique(UQ_TASK_EDF)];
+ SomethingP.SenseTask -> TinySchedulerC.TaskEdf[unique(UQ_TASK_EDF)];
}
</pre>
<p>The module SomethingP also has a basic task. The nesC compiler
}
}
</pre>
+<p>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.</p>
<p>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 always selects a task
+tasks and high-priority tasks. The scheduler usually selects a task
for the high priority queue before the standard queue:</p>
<pre class="literal-block">
configuration TinySchedulerC {
provides interface TaskBasic[uint8_t taskID] as TaskHighPriority;
}
</pre>
-<p>A component that uses a high priority task would then wire to
-TaskHighPriority with the key "TinySchedulerC.TaskHighPriority":</p>
+<p>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":</p>
<pre class="literal-block">
configuration SomethingElseC {}
implementation {