mate-manual.tex

无线通信的主要编程软件,是无线通信工作人员的必备工具,关天相关教程我会在后续传上.

is distinct from {\tt MateTypes}, which is type-checking). To
transform a variable between in-memory and network represntations,
components can invoke {\tt MTypeManager}. {\tt MTypeManager}'s
interface is a pass-through to the implementing components: a
component that supports a given type (such as {\tt MBuffer}, which
supports TinyScript's data buffers) wires to {\tt MTypeManager} so
calls will be forwarded properly. If a VM tries to transform a type
for which there is no support, then {\tt MTypeManager} indicates that
the type is not supported: this will generally trigger an error
condition in the VM.

\subsection{Concurrency Management: {\tt MContextSynchProxy}}


\begin{figure}
\centering
\includegraphics[width=6in]{fig/MContextSynchProxy.jpg}
\caption{{\tt MContextSynchProxy} wiring diagram.}
\label{fig:mcontext-synch-proxy}
\end{figure}

{\tt MContextSynchProxy} is encapsulates {\tt MContextSynch} and wires
it to needed services. {\tt MContextSynch} is responsible for
analyzing code to determine when handlers can safely run
concurrently. ome instructions represent shared resources. For
example, {\tt bpush3} and {\tt getvar4} access shared variables. For
race free program, the VM execution engine must be aware of this and
control scheduling appropriately.

When a component wants a context to run, it submits the
context to {\tt MContextSynch}; based on its analyses, {\tt
MContextSynch} either forwards the context on to {\tt MateEngine} for
execution, or puts it on a wait queue. If a context holding shared
resources halts, {\tt MContextSynch} has it release the resources and
checks if that allows any waiting contexts to run.

{\tt MContextSynch} keeps track of shared resources through the
MateBytecodeLock interface. If an instruction manages a shared
resource, then it must provide this interface. Additionally, in its
ODF, it must have the optional element ``locks'' set to true.

For example, let's look at OPbpush3. This instruction pushes the eight
shared buffers, buffer0-7, onto the operand stack. It is not a library
function; instead, it is an element of the instruction set that
TinyScript compiles to. In {\tt tscript.ldf}
(Section~\ref{sec:language} describes language files in greater
depth), it lists

{\scriptsize
\begin{verbatim}
<OPCODE opcode="bpush3" locks=true>
\end{verbatim}
}

Then, in OPbpush3M:

{\scriptsize
\begin{verbatim}
module OPbpush3M {
  provides interface MateBytecode;
  provides interface MateBytecodeLock;
}
\end{verbatim}
}

{\tt MateBytecodeLock} has a single command:

{\scriptsize
\begin{verbatim}
interface MateBytecodeLock {
  command int16_t lockNum(uint8_t instr);
}
\end{verbatim}
}

This takes a instruction opcode and returns a unique lock
number. The idea is that certain opcodes have a lock associated with
them. {\tt bpush3}, for example, has three bits of embedded operand, for
the eight buffers. If {\tt bpush3 0} is passed to {\tt OPbpush3M.nc},
then it returns the lock number for buffer zero, while {\tt bpush3 1}
will return the lock number for buffer one.

The full {\tt OPbpush1M.nc} logic:

{\scriptsize
\begin{verbatim}
module OPbpush3M {
  ...
  provides interface MateBytecodeLock;
  ...
}


implementation {
  typedef enum {
    BOMB_BUF_LOCK_3_0 = unique("MateLock"),
    BOMB_BUF_LOCK_3_1 = unique("MateLock"),
    ...
    BOMB_BUF_LOCK_3_7 = unique("MateLock"),
  } BufLockNames;
  ...
  command int16_t MateBytecodeLock.lockNum(uint8_t instr) {
    uint8_t which = instr - OPbpush3;
    switch (which) {
    case 0:
      return BOMB_BUF_LOCK_3_0;
    case 1:
      return BOMB_BUF_LOCK_3_1;
    ...
    case 7:
      return BOMB_BUF_LOCK_3_7;
    default:
      return 255;
    }
  }
  ...
}
\end{verbatim}
}

It declares eight unique lock numbers with the nesC unique function. When
lockNum() is called, it returns the lock number associated with the
corresponding buffer. Every context has

{\scriptsize
\begin{verbatim}
  uint8_t heldSet[(BOMB_LOCK_COUNT + 7) / 8];
  uint8_t releaseSet[(BOMB_LOCK_COUNT + 7) / 8];
  uint8_t acquireSet[(BOMB_LOCK_COUNT + 7) / 8];
\end{verbatim}
}

where BOMB\_LOCK\_COUNT is defined to be uniqueCount("MateLock");

\subsubsection{Synchronization Algorithms}

\mate's concurrency manager is responsible for ensuring that handlers
execute atomically. Although it may allow them to run concurrently,
atomicity requires that doing so should be indistinguishable from
their running serially. The concurrency manager maintains a bitmask of
the shared resoures each handler uses (the {\it uses set}), and each
context has three bitmasks: the set of resources it holds (the {\it
held set}), the set of resources it can release (the {\it release
set}), and the set of resources it needs to acquire (the {\it acquire
set}). Initializing a context through {\tt
MateContextSynch.initializeContext} sets a context's acquire set to
its handler's uses set. Every time MContextSynch acquires a lock for a
context, it adds that resource to the context's held set.

When new code for a handler arrives, the concurrency manager runs a
context and flow insensitive program analysis to determine the set of
shared resources that handler uses. It iterates over each instruction
in the handler, using the {\tt MateBytecodeLock} interface to
determine whether an instruction requires a shared resource, updating
the uses set of the handler. 

The concurrency manager maintains a lock for each shared resource;
only one context may access a shared resource. When a component
submits a context to run through the {\tt
MateContextSynch.resumeContext} command, MContextSynch checks the
acquire set of the context. If every resource in the acquire set is
available, MContextSynch atomically acquires all of the locks for the
context and submits it to the scheduler to run. If one or more of the
resources in the context's acquire set are already held, then
MContextSynch puts the context on a wait queue and sets its state to
{\tt MATE\_STATE\_WAITING}.

While they execute, contexts may add resources to their release
set. This does not release those resources. When a context yields,
through the {\tt MateContextSynch.yield} command, MContextSynch has it
unlock each of the resources in its release set, then clears the
set. MContextSynch then tests each context on the wait queue to see if
it is now runnable (the release of locks means all locks in its
acquire set are free). If a context is runnable, MContextSynch resumes
it.

When a context adds a resource to its release set, it may also add it
to its acquire set. This means that the context will release those
resources at the next yield point, but will not continue execution
until it can reacquire them: it can temporarily release the resources.

Currently, TinyScript does not manipulate context release sets,
although it has instructions for doing so. This is an area for future
work.

Because, once it starts running, the acquire set of a context is
always a subset of its release set, the set of resources a context
holds while running is montonically decreasing. A context can never
hold a resource that it did not hold when it started running. This
ensures that contexts can run deadlock-free, while the program
analysis (barring incorrect lock releases at runtime) ensures
race-free execution.


\subsection{Code Propagation: {\tt MHandlerStoreProxy}}


\begin{figure}
\centering
\includegraphics[width=6in]{fig/MHandlerStoreProxy.jpg}
\caption{{\tt MHanderStoreProxy} wiring diagram.}
\label{fig:handler-store}
\end{figure}

The MHandlerStoreProxy component encapsulates \mate's code storage and
propagation. Figure~\ref{fig:handler-store} contains its wiring
diagram, and the component has the following signature:

{\scriptsize
\begin{verbatim}
configuration MHandlerStoreProxy {
  provides {
    interface StdControl;
    interface MateHandlerStore as HandlerStore[uint8_t id];
  }
}
\end{verbatim}
}

Every component that has a handler should wire to HandlerStore, with a
unique ID (the handler ID). VMBuilder automatically generates handler
IDs for contexts, with {\tt unique("MateHandlerID")}; if other
components need to register handlers, they should use the same key for
{\tt unique}.

{\tt MateHandlerStore} has the following signature:

{\scriptsize
\begin{verbatim}
interface MateHandlerStore {
  command result_t initializeHandler();
  command MateHandlerOptions getOptions();
  command MateHandlerLength getCodeLength();
  command MateOpcode getOpcode(uint16_t which);
  event void handlerChanged();
}
\end{verbatim}
}

It provides accessor functions for handlers, and notifies its user
when the code for the handler has changed. Currently, MHandlerStore
allocates a static amount of memory for each handler's code (the
default is 128 bytes), but by controlling access through an interface,
this can easily be changed.

MHandlerStore provides access to code at handler granularity, but
\mate propagates code in terms of capsules, which contain one or more
handlers. The default implementation has a one-to-one handler-capsule
mapping, but languages or compilers may require other
implementations. For example, motlle, due to its semantics, requires
that all handlers propagate together in a single capsule.

MHandlerStore is responsible for triggering program analysis via
MContextSynchProxy when a capsule arrives. MHandlerStore sits on top
of MVirus, which handles capsule propagation. The idea is that a
particular MHandlerStore implementation determines the format of the
data regions of capsules and can parse them into handlers.

\begin{figure}
\centering
\vspace*{-.5cm}
\includegraphics[width=2in]{fig/virus-states.jpg}
\vspace*{-.5cm}
\caption{State diagram for \mate capsule propagation.}
\label{fig:prog_state}
\end{figure}

MVirus uses an epidemic-like approach to propagate capsules: a node
that has newer code will broadcast it to local neighbors. The Trickle
algorithm is used to broadcast three types of data: version packets,
which contain the 32-bit version numbers of all installed capsules,
capsule status packets which describes fragments of a capsule that a
mote needs (essentially, a bitmask), and capsule fragments that are
short segments of a capsule. Figure~\ref{fig:prog_state} contains the
state diagram used by motes for code propagation. A mote can be in one
of three states: maintain (exchanging version packets), request
(sending capsule status packets), or respond (sending
fragments). Nodes start in the maintain state. They enter the request
state if they hear something that indicates someone has a newer
capsule, whether it be a version, capsule status, or fragment
packet. A requesting node returns to the maintain state once it
receives the entire capsule. A node enters the respond state if it is
in the maintain state and hears that someone has an older capsule
(through a version packet), or needs part of its current capsule
(through a capsule status packet). These state transitions mean that
nodes prefer requesting over responding; a node will defer forwarding
capsules until it thinks it is completely up to date.

Trickle's suppression operates on each type of packet (version,
capsule status, and capsule fragment) individually. That is, a capsule
fragment transmission will suppress all other fragment transmissions,
but will not suppress version packets. This allows meta-data exchanges
during propagation: sending a fragment will not cause someone to
suppress a message saying what fragments it needs. Trickling fragments
means that code propagates in a slow and controlled fashion, instead
of as quickly as possible. This is unlikely to significantly disrupt
any existing traffic, and prevents network overload.

\subsubsection{Trickle: The Code Propagation Algorithm}

The Trickle algoithm uses broadcast-based suppressions to quickly
propagate new data but minimize transmissions when nodes share
data. The algorithm operates on an time interval $t$, which has an
upper length of $t_{h}$ and a lower length of $t_{l}$.When an interval
completes, Trickle doubles the size of an interval, up to
$t_{h}$. When it learns of new code (e.g., by overhearing a capsule
fragment, version vector, or capsule status packet with a higher
version number), it shrinks the interval to $t_{l}$.

Essentially, when there's nothing new to say, \mate VMs gossip
infrequently: $\tau$ is set to $\tau_{h}$. However, as soon as a mote
hears something new, it gossips more frequently, so those who haven't
heard it yet find out. The chatter then dies down, as $\tau$ grows
from $\tau_{l}$ to $\tau_{h}$.

Trickle maintains a redundancy constant $k$ and a counter
$c$. Whenever it hears a packet that would suppress its own
transmission (e.g., a capsule fragment if in the respond state), it
increments $c$. At the beginning of an interval, the algorithm resets
$c$ to zero, and picks a random time in the range of
$[\frac{t}{2},t]$. When it reaches that time, it transmits data if and
only if $c < k$. 

\section{\mate Operations}

MateEngine executes programs in terms of operations. Every operation
has one or more one-byte opcodes, which map to a component that
implements the {\tt MateBytecode} interface. An operation can have
embedded operands, which cause it to exist as more than one
opcode. For example, the {\tt bpush3} operation (which the TinyScript
language uses) has three bits of embedded operand, corresponding to
the eight data buffers TinyScript makes available.

The \mate tutorials describe how to write new functions, which are a
particular kind of operation: they never have embedded operands, and
are generally expected to provide language-independent
functionality. In addition to functions, operations can also be
primitives, which are the operations that compose a language. This is
why function components have the prefix ``OP,'' such as {\tt OPid}.


\subsection{Operation Component Naming Convention}

Operation components have the following naming convention:

{\scriptsize