tep134.txt

tinyos-2.x.rar

  typedef struct thread_regs {
    ...
  } thread_regs_t;

(2) A typedef of a ``stack_ptr_t`` type.  For example, the msp430 microconroller
has 16 bit memory addresses, so ``stack_prt_t`` is typedefed as follows.::

  typedef uint16_t* stack_ptr_t;
  
(3) Definitions of the following MACROS for use by the TOSThreads thread
scheduler.::

  PREPARE_THREAD(thread, start_function)
  SWITCH_CONTEXTS(current_thread, next_thread)
  RESTORE_TCB(next_thread)
  STACK_TOP(stack, size)
  
As explained in Section 4.2, state manipulated by these MACROS is
carried around by a thread as part of its *Thread Control Block (TCB)*, defined
as type 'thread_t'.
  
``PREPARE_THREAD()`` takes two parameters: 'thread' and 'start_function'.  The
'thread' parameter MUST be of type ``thread_t``, and 'start_function' MUST be of
type ``void (*start_function)(void)``.  The purpose of ``PREPARE_THREAD()`` is
to get a thread ready for the first time it starts to execute.  Primarily, it is
used to set the top of the stack associated with 'thread' to its
'start_function'.  When it comes time for the thread to begin executing, the
address pointed to by 'start_function' will be popped off and it will start executing.

As an example, consider the definition of ``PREPARE_THREAD()`` for the msp430
microcontroller::

  #define PREPARE_THREAD(t, thread_ptr)		\
    *((t)->stack_ptr) = (uint16_t)(&(thread_ptr));	\
    SAVE_STATUS(t)
    
In this case, the status register is also saved with its initial setup, but this
may not be necessary for all microcontrollers.
  
``SWITCH_CONTEXTS()`` takes two parameters: current_thread and next_thread. Both
parameters MUST be of type 'thread_t'.The purpose of ``SWITCH_CONTEXTS()`` is to
store the state of the thread associated with the 'current_thread', and swap it
out with the state of the 'next_thread'.  The amount and type of state saved,
and how it is actually swapped out varies from microcontroller to microcontroller.

``RESTORE_TCB()`` takes just one parameter: next_thread.  This parameter MUST be
of type 'thread_t'. ``RESTORE_TCB()`` is similar to ``SWITCH_CONTEXTS()`` except
that no state is stored about the current thread before swapping in the state
associated with 'next_thread'.  This MACRO is primarily called at the time a
thread is either killed or has run to completion.  
  
``STACK_TOP()`` takes two parameters: 'stack' and 'size'.  The 'stack' parameter
MUST be of type ``stack_ptr_t`` and 'size' MUST be an integer type (i.e.
uint8_t, uint16_t, etc).  As explained in Section 4.2, whenever a thread is
created, it is allocated its own stack space with a given size.  As a thread
executes, local variables, register values, and the return address of procedure
calls are pushed onto this stack. Depending on the microcontroller in use, the
*top* of a thread's stack might exist at either the highest address (stack grows
down) or lowest address (stack grows up) of the data structure allocated to the
stack.  The purpose of ``STACK_TOP()`` is to return a pointer of type
``uint8_t*`` to the location of the *top* of the stack.  ``STACK_TOP()`` is only
called once at the time a thread is first initialized.

There are only two choices for the definition of this MACRO, and both are shown
below.::

  //Stack grows down (i.e. need to return pointer to bottom of structure (highest address))
  #define STACK_TOP(stack, size)    \
    (&(((uint8_t*)stack)[size - sizeof(stack_ptr_t)]))
    
::

  //Stack grows up (i.e. need to return pointer to top of structure (lowest address))
  #define STACK_TOP(stack, size)    \
    (&(((uint8_t*)stack)[0]))

As an example, consider the msp430 and atmega128 microcontrollers. On both of
these microcontrollers, a thread's stack grows down as it executes, so
``STACK_TOP()`` is defined using the first macro.
  
4. The TOSThreads Library Implementation
====================================================================

This section describes the implementation of TOSThreads, including the
internals of the thread scheduler, the thread and system call
data structures, and their corresponding interfaces.

4.1 The Thread Scheduler
----------------------------------------------------------------------

The thread scheduler is the first component to take control of the
microcontroller during the boot process. As mentioned previously, its job is to
encapsulate TinyOS inside a thread and trigger the normal TinyOS boot sequence.
Once TinyOS boots and processes all of its initial tasks, control returns to the
thread scheduler which begins scheduling application threads. The scheduler
keeps threads ready for processing on a ready queue, while threads blocked on
I/O requests or waiting on a lock are kept on different queues. 

The default TOSThreads scheduler implements a fully preemptive round-robin
scheduling policy with a time slice of 5 msec. We chose this value to achieve
low latency across multiple application-level computing tasks. While application
threads currently run with the same priority, one can easily modify the
scheduler to support other policies.

As explained in the following section, TOSThreads exposes a relatively 
standard API for creating and manipulating threads: ``create(), 
destroy(), pause() and resume()``. These functions form part of the system 
call API, and can be invoked by any application program.

Internally, TOSThreads library components use the following ``ThreadScheduler``
interface to interact with a thread.::

  interface ThreadScheduler {
    async command uint8_t currentThreadId();
    async command thread_t* currentThreadInfo();
    async command thread_t* threadInfo(thread_id_t id);
  
    command error_t initThread(thread_id_t id);
    command error_t startThread(thread_id_t id);
    command error_t stopThread(thread_id_t id);
    
    async command error_t interruptCurrentThread();
  
    async command error_t suspendCurrentThread();
    async command error_t wakeupThread(thread_id_t id);
  }
  
The thread scheduler itself does not exist in any particular execution context
(i.e., it is not a thread and does not have its own stack). Instead, any
TOSThreads library component that invokes one of the above commands executes in
the context of the calling thread. Due to the sensitive nature of these
commands, ONLY the interrupt handler post-ambles and blocking system call API
wrappers invoke them directly.
  
The first three commands are used to get information associated with an instance
of a thread.  Calling ``currentThreadId()`` returns a unique identifier
associated with the currently running thread.  Calling ``currentThreadInfo()``
or ``threadInfo()`` on a particular thread returns a pointer to the complete
*Thread Control Block (TCB)* associated with a thread.  Details about the TCB
structure returned by these comamnds are given in section 4.2.

The rest of the commands in this interface are used to manipulate the state of a
thread, putting it into one of 4 distinct states and starting / stopping its
execution as necessary.  At any given time, a thread may exist in one of the 
following states (INACTIVE, ACTIVE, READY, SUSPENDED).  

Threads are initialized into the INACTIVE state via a call to ``initThread()``. 
This command MUST only be called once at the time a thread is first created.  A
call to ``initThread()`` MUST be followed by a call to ``startThread()`` at some
point later in order to start the actual execution of the thread.  Calls to
``initThread()`` always return SUCCESS;

Calls to ``startThread()`` return either SUCCESS or FAIL, depending on the state
a thread is in when it is called.  If a thread is in the INACTIVE state, calling
this command puts a thread into the READY state and places it on a ready queue.
Threads are scheduled for execution by puling threads off this ready queue in
FCFS order.  If a thread is in any state other than INACTIVE, FAIL is returned, 
and no other side effects occur.

Calls to ``stopThread()`` only return SUCCESS if called on a thread that is in
the READY state (and thereby implicitly on the ready queue) and currently holds
no mutexes.  The ``mutex_count`` field in a thread's TCB is used to determine if
any mutexes are currently held.  If both of these conditions are met, a thread
is removed from the READY queue and its state is set to INACTIVE.  If either of
these conditions are not met, calling ``stopThread()`` returns FAIL and no other
side effects occur.

Calls to ``interruptCurrentThread()`` are made in order to preempt a currently
running thread. Calling ``interruptCurrentThread()`` returns SUCCESS if the
currently running thread is in the ACTIVE state (SHOULD always be true),
otherwise it returns FAIL.  Upon FAIL no side effects occur.  Upon SUCCESS, the
currently running thread is put into the READY state and placed on the thread
scheduler's ready queue.  Threads in the READY state are not blocked, and will
be scheduled for execution again the next time their turn comes up.  The
``interruptCurrentThread()`` function is currently only called in two places. 
At the bottom of the interrupt ``postAmble()`` (as shown before), and in the
code implementing the round-robin preemption scheme.

Calls to ``suspendCurrentThread()`` return SUCCESS if the currently running
thread is in the ACTIVE state (SHOULD always be true), otherwise they return
FAIL.  Upon SUCCESS, the currently running thread is put into the SUSPEND state
and its execution is stopped.  A thread in the SUSPEND state will not be
scheduled for execution again until a call to ``wakeupThread()`` is made at some
later point in time. Calls to ``suspendCurrentThread()`` SHOULD only be made
from within the body of blocking system call API wrappers or synchronization
primitives.  

Calls to ``wakeupThread()`` take one parameter: 'thread_id'. ``wakeupThread()``
returns SUCCESS if the thread associated with 'thread_id' is successfully woken up
and returns FAIL otherwise.  For all threads other than the TinyOS thread, SUCCESS 
will only be returned if the thread being woken up is in the SUSPEND state.  For the
TinyOS thread, it must be both in the SUSPEND state and have tasks waiting on it
task queue.  Upon SUCCESS, a thread is put in the READY state and placed on the ready 
queue.  Upon FAIL, no side effects occur. 

.. Note::
  Most times calls to `suspendCurrentThread()`` are paired with placing the
  suspended thread on a queue.  Calls to ``wakeupThread()`` are then paired with
  removing a thread from that queue.  The queue used is matianed externally by
  the component issuing the suspend and wakeup.  For example, every mutex
  variable has its own queue associated with it. Everytime a thread calls the
  ``lock()`` function associated with a mutex, it is placed onto the queue
  associated with that mutex if someone already holds the lock.  When the owner
  of the lock eventually calls ``unlock()`` this queue is then checked and
  requesters are removed from the queue in FCFS order.  

4.2 Threads 
----------------------------------------------------------------------

Section 4 discusses the API provided to an application that allows it to create
and destroy theads, as well as invoke blocking system calls.  This section
details the internals of the thread implementation itself, focusing on the data
structure used to actually represent threads.

Regardless of the API used to create a thread (either *statically* or
*dynamically* as discussed in the following section), TOSThreads allocates a
Thread Control Block (TCB) and stack memory for each thread at the time it is
created.  Each thread has a fixed stack size that does not grow over time.  The
code snippet below shows the structure of a TOSThreads TCB.::

  struct thread {
    thread_id_t thread_id;
    init_block_t* init_block;
    struct thread* next_thread;
   
    //thread_state
    uint8_t state;
    uint8_t mutex_count;
    thread_regs_t regs;
  
    //start_function
    void (*start_ptr)(void*);
    void* start_arg_ptr;
  
    stack_ptr_t stack_ptr;
    syscall_t* syscall;
  };

**thread_id**: This field stores a thread's unique identifier.
It is used primarily by system call implementations and synchronization
primitives to identify the thread that should be blocked or woken up.

**init_block**: Applications implemented using the TOSThreds library have the
ability to be dynamically loaded onto a mote at runtime.  It is beyond the scope
of this TEP to go into the details of this process, but applications use this
field whenever they are dynamically loaded onto a mote. Whenever the system
dynamically loads a TOSThreads application, the threads it creates must all
receive the state associated with its global variables. An initialization block
structure stores these global variables and 'init_block' points to this structure.
 
**next_thread**: TOSThreads uses thread queues to keep track of threads waiting
to run. These queues are implemented as linked lists of threads connected
through their next_thread' pointers. By design, a single pointer suffices:
threads are *always* added to a queue just before they are interrupted and
are removed form a queue just before they wake up. This approach conserves
memory.

**thread_state** This set of fields store information about the thread's current
state. It contains a count of the number of mutexes the thread currently holds;
a state variable indicating the state the thread is in (INACTIVE, READY,
SUSPENDED, or ACTIVE); and a set of variables that store a processor's register