tep134.txt

tinyos-2.x.rar

====================================================================
The TOSThreads Thread Library
====================================================================

:TEP: 134
:Group: Core Working Group 
:Type: Documentary
:Status: Draft
:TinyOS-Version: 2.x
:Author: Kevin Klues, Chieh-Jan Liang, Jeongyeup Paek, Razvan Musaloiu-E, Ramesh Govindan, Andreas Terzis, Philip Levis

:Draft-Created: 13-May-2008
:Draft-Version: $Revision: 1.1 $
:Draft-Modified: $Date: 2008/06/12 13:02:08 $
:Draft-Discuss: TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu>

.. 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 TOSThreads thread library for TinyOS

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

TOSThreads is an attempt to combine the ease of a threaded programming model 
with the efficiency of a fully event-based OS. Unlike earlier threads packages 
designed for TinyOS, TOSThreads supports fully-preemptive application level 
threads, does not require explicit continuation management, and neither 
violates TinyOS's concurrency model nor limits its concurrency.  Additionally,
adding support for TOSThreads requires minimal changes to the existing TinyOS 
code base, and bringing up a new platform to support the use of TOSThreads 
is a fairly easy process.  

In TOSThreads, TinyOS runs inside a single high priority kernel thread, while all 
application logic is implemented using user-level threads, which execute 
whenever the TinyOS core becomes idle. This approach is a natural extension 
to the existing TinyOS concurrency model, adding support for long-running 
computations while preserving the timing-sensitive nature of TinyOS itself. 

In this model, application threads access underlying TinyOS services using a 
kernel API of blocking system calls. The kernel API defines the set of TinyOS 
services provided to applications (e.g. time-sync [TEP133]_, collection [TEP119]_, 
and dissemination [TEP118]_). Each system call in the API is comprised 
of a thin blocking wrapper built on top of one of these services.  TOSThreads 
allows systems developers to re-define the kernel API by appropriately 
selecting (or implementing their own) custom set of blocking system call wrappers.

The following section describes the details of how TOSThreads interacts with
TinyOS to provide each of the features described above.

2. Basic Architecture
====================================================================

The existing TinyOS concurrency model has two execution contexts: synchronous
(tasks) and asynchronous (interrupts). These two contexts follow a strict
priority scheme: asynchronous code can preempt synchronous code but not
vice-versa. TOSThreads extends this concurrency model to provide a third execution
context in the form of user-level application threads. Application threads run 
at the lowest priority, with the ability to only preempt one another.  They are
preemptable at any time by either synchronous code or asynchronous code, and 
synchronize amongst each other using standard synchronization primitives
such as mutexes, semaphores, barriers, condition variables, and blocking
reference counters (a custom mechanism we have developed ourselves).  Take a look
in ``tos/lib/tosthreads/interfaces`` to see the interfaces providing these 
primitives.

The basic TOSThreads architecture, consists of five key elements: the TinyOS 
task scheduler, a single kernel-level TinyOS thread, a thread scheduler, a 
set of user-level application threads, and a set of system call APIs and their 
corresponding implementations. Any number of application threads can 
concurrently exist (barring memory constraints), while a single kernel thread 
runs the TinyOS task scheduler. The thread scheduler manages concurrency 
between application threads, while a set of system calls provides them 
access to the TinyOS kernel.  

In order to preserve the timing-sensitive operation of TinyOS, the kernel 
thread has higher priority than application threads. This *TinyOS thread*
therefore always takes precedence over application threads as long as the TinyOS
task queue is non-empty. Once the TinyOS task queue empties, control passes to
the thread scheduler and application threads can run. The processer goes to
sleep only when either all application threads have run to completion, or when
all threads are waiting on synchronization primitives or blocked on I/O
operations.

There are two ways in which posted events can cause the TinyOS thread to wake
up. First, an application thread can issue a blocking system call into the
TinyOS kernel. This call internally posts a task, implicitly waking up the
TinyOS thread to process it. Second, an interrupt handler can post a task for
deferred computation. Since interrupt handlers have higher priority than the
TinyOS thread, the TinyOS thread will not wake up to process the task until
after the interrupt handler has completed. Because interrupts can arrive at 
anytime, it is important to note that waking up the TinyOS thread may require 
a context switch with an interrupted application thread. Control eventually 
returns to the application thread after the TinyOS thread has emptied the 
task queue.

3. Modifications to the Standard TinyOS Code Base
====================================================================

Only two changes to the existing TinyOS code base are required to support
TOSThreads: a modification to the boot sequence and the addition of a post-amble
for every interrupt handler.  Changes to the boot sequence only need to be made
once and are independent of any platforms supported by TinyOS. Changes to the
interrupt handlers MUST be handled on a microcontroller to microntroller basis. 
Additionally, a custom ``chip_thread.h`` file MUST be created for each
microcontroller and place in its top level directory, e.g. ``tos/chips/msp430``

3.1 Changes to the Boot Sequence
----------------------------------------------------------------------

Instead of directly running the TinyOS boot sequence inside of main() as
done previously, main() now calls out to a Boot.booted() event 
associated with booting up the thread scheduler.::

  event void ThreadSchedulerBoot.booted() {
    //Thread sceduler specific init stuff
    ...
    ...
    
    //Encapsulate TinyOS inside a thread
    tos_thread = call ThreadInfo.get[TOSTHREAD_TOS_THREAD_ID]();
    tos_thread->id = TOSTHREAD_TOS_THREAD_ID;
    
    //Set the TinyOS thread as the current thread and activate it
    current_thread = tos_thread;
    current_thread->state = TOSTHREAD_STATE_ACTIVE;
    
    //Signal the boot sequence
    signal TinyOSBoot.booted();
  }
  
This change is made in order to encapsulate TinyOS inside the single 
kernel-level thread and set it as the initial thread that starts running. 
Once this is done, the normal TinyOS boot sequence is ran by signaling the 
TinyOSBoot.booted() event. 

At the bottom of the existing TinyOS boot sequence, we enter an infinite
loop that continuously checks the TinyOS task scheduler to see if it 
has any tasks to run.  If it does, it runs the next task in its queue.
If it does not, it puts the microcontroller into its lowest possible power
state and goes to sleep [TEP112]_.::

  command void Scheduler.taskLoop() {
    for (;;) {
      uint8_t nextTask;

      atomic {
        while ((nextTask = popTask()) == NO_TASK)
          call McuSleep.sleep();
      }
      signal TaskBasic.runTask[nextTask]();
    }
  }

By adding threads as a lowest priority execution context, we need to change 
these semantics slightly.  Instead of going directly to sleep, we want to 
allow the thread scheduler to take control of the microcontroller and start
scheduling any threads it has to run.  Only once all application threads 
have run to completion, or when all threads are waiting on synchronization 
primitives or blocked on I/O operations is the microcontroller put to sleep.

We achieve such functionality by replacing the call to McuSleep.sleep() shown 
above, by a call that signals the thread scheduler to suspend the currently 
running thread (the TinyOS kernel thread).::

  command void TaskScheduler.taskLoop() {
    for (;;) {
      uint8_t nextTask;

      atomic {
        while((nextTask = popTask()) == NO_TASK)
          call ThreadScheduler.suspendCurrentThread();
      }
      signal TaskBasic.runTask[nextTask]();
    }
  }

Once the TinyOS thread has been suspended, the thread scheduler is free to 
begin scheduling application level threads however it sees fit.

3.2 Interrupt Handler Post-Ambles
----------------------------------------------------------------------

With the changes described above, the only other *non-self-contained* 
TinyOS code necessary to support TOSThreads is the addition of a post-amble 
at the bottom of every interrupt handler.  Since the number and type
of interrupt handlers, as well as the semantics required for implementing 
them, differ from platform to platform, the way in which this post-amble is 
is added is highly dependent on the microcontroller in use.  The post-amble 
itself, however, is completely platform-independent, and is provided via a 
``postAmble()`` command included in the ``PlatformInterrupt`` interface.::

  command void PlatformInterrupt.postAmble() {
    atomic {
    if(call ThreadScheduler.wakeupThread(TOSTHREAD_TOS_THREAD_ID) == SUCCESS)
      if(call ThreadScheduler.currentThreadId() != TOSTHREAD_TOS_THREAD_ID)
        call ThreadScheduler.interruptCurrentThread();
    }
  }
  
As described in the following section, the call to ``wakeupThread()`` returns
SUCCESS iff the TinyOS task queue has any tasks to process (i.e. the interrupt
handler posted some tasks), otherwise it returns FAIL.  Upon FAIL, we simply
return from this function, and continue execution from the point at which the
currently running thread was interrupted.  Upon SUCCESS, we preempt the current
thread, immediately scheduling the TinyOS thread for execution.  The check to
make sure that the current thread isn't already the TinyOS thread is simply an
optimization used to bypass ''rescheduling'' the already running thread.

This ``postAmble()`` command MUST be called at the bottom of EVERY interrupt
handler provided by a platform.  This interface is provided by the 
``PlatformInterruptC`` component, and MUST be wired into every component which
implements an interrupt handler.  Calls to ``postAmble()`` MUST then be made 
just before any return points in the given interrupt handler.

.. Note::
  Attempts were made to try and simplify / automate the inclusion of the 
  post amble through the use of MACROS and other means. It was determined in 
  the end, however, that this was the simplest and most readable way 
  to keep the implementation of the post-amble platform independent, while 
  allowing it to be included on a platform by platform basis for differing
  interrrupt handler implementations.
  
As an example, consider the case of the interrupt handlers for the 
TIMERA0_VECTOR and ADC_VECTOR on the msp430 microcontroller::

  TOSH_SIGNAL(TIMERA0_VECTOR) {
    //Body of interrupt handler
    ...
    ...
    
    call PlatformInterrupt.postAmble();
  }
  
  TOSH_SIGNAL(ADC_VECTOR) {
    //Body of interrupt handler
    ...
    ...
    
    call PlatformInterrupt.postAmble();
  }
  
The component in which each of these handlers is defined MUST wire in 
the ``PlatformInterrupt`` interface provided by ``PlatformInterruptC``
and call ``postAmble()`` at the bottom of their interrupt handlers.

3.3 The ``chip_thread.h`` file
----------------------------------------------------------------------

A ``chip_thread.h`` MUST be created in the chips directory for each
microcontroller supporting the TOSThreads library.  This file MUST contain
definitions of the following:

(1) A structure containing space for saving any microcontroller specific 
registers needed to save state when doing a context switch.::