Even infinite sequences rewrite steps, as in the \cleaninline{blink} example, are perfectly fine.
The \gls{MTASK} system does proper tail-call optimizations to facilitate this.
-\section{Task scheduling in the \gls{MTASK} language}
+\section{Rewrite interval}
Some \gls{MTASK} examples contain one or more explicit \cleaninline{delay} primitives, offering a natural place for the node executing it to pause.
However, there are many \gls{MTASK} programs that just specify a repeated set of primitives.
A typical example is the program that reads the temperature for a sensor and sets the system \gls{LED} if the reading is below some given \cleaninline{goal}.
\begin{lstClean}[caption={A basic thermostat task.},label={lst:thermostat}]
thermostat :: Main (MTask v Bool) | mtask v
thermostat = DHT I2Caddr \dht->
- {main = rpeat ( temperature dht >>~. \temp.
- writeD builtInLED (goal <. temp))}
+ {main = rpeat (temperature dht >>~. \temp.
+ writeD builtInLED (goal <. temp))}
\end{lstClean}
This program repeatedly reads the \gls{DHT} sensor and sets the on-board \gls{LED} based on the comparison with the \cleaninline{goal} as fast as possible on the \gls{MTASK} node.
Fortunately, \gls{MTASK} also contains machinery to do this automatically.
The key of this solution is to associate dynamically an evaluation interval with each task.
-The interval $\refreshrate{low}{high}$ indicates that the evaluation can be safely delayed by any number of milliseconds in that range.
+The interval $\rewriterate{low}{high}$ indicates that the evaluation can be safely delayed by any number of milliseconds within that range.
Such an interval is just a hint for the \gls{RTS}.
It is not a guarantee that the evaluation takes place in the given interval.
Other parts of the task expression can force an earlier evaluation of this part of the task.
When the system is very busy with other work, the task might even be executed after the upper bound of the interval.
-The system calculates the refresh rates from the current task expression.
+The system calculates the rewrite rates from the current task expression.
This has the advantage that the programmer does not have to deal with them and that they are available in each and every \gls{MTASK} program.
\subsection{Basic tasks}
-We start by assigning default refresh rates to basic tasks.
-These refresh rates reflect the expected change rates of sensors and other inputs.
-Writing to basic \gls{GPIO} pins and actuators has refresh rate $\refreshrate{0}{0}$, this is never delayed.
+We start by assigning default rewrite rates to basic tasks.
+These rewrite rates reflect the expected change rates of sensors and other inputs.
+Basic tasks to one-shot set a value of a sensor or actuator usually have a rate of $\rewriterate{0}{0}$, this is never delayed, e.g.\ writing to a \gls{GPIO} pin.
+Basic tasks that continuously read a value or otherwise interact with a peripheral have default rewrite rates that fit standard usage of the sensor.
+\Cref{tbl:rewrite} shows the default values for the basic tasks.
+I.e.\ reading \glspl{SDS} and fast sensors such as sound or light aim for a rewrite every \qty{100}{\ms}, medium slow sensors such as gesture sensors every \qty{1000}{\ms} and slow sensors such as temperature or air quality every \qty{2000}{\ms}.
\begin{table}
\centering
- \caption{Default refresh rates of basic tasks.}%
- \label{tbl:refresh}
+ \caption{Default rewrite rates of basic tasks.}%
+ \label{tbl:rewrite}
\begin{tabular}{ll}
\toprule
- task & default interval \\
+ task & default interval\\
\midrule
- reading \pgls{SDS} & $\refreshrate{0}{2000}$ \\
- slow sensor, like temperature & $\refreshrate{0}{2000}$ \\
- gesture sensor & $\refreshrate{0}{1000}$ \\
- fast sensor, like sound or light & $\refreshrate{0}{100}$ \\
- reading GPIO pins & $\refreshrate{0}{100}$ \\
+ reading \pgls{SDS} & $\rewriterate{0}{2000}$\\
+ slow sensor & $\rewriterate{0}{2000}$\\
+ medium sensor & $\rewriterate{0}{1000}$\\
+ fast sensor & $\rewriterate{0}{100}$\\
\bottomrule
\end{tabular}
\end{table}
-\subsection{Deriving refresh rates}\label{sec:deriving_refresh_rates}
-Based on these refresh rates, the system can automatically derive refresh rates for composed \gls{MTASK} expressions using $\mathcal{R}$.
-We use the operator $\cap_{\textit{safe}}$ to compose refresh ranges.
-When the ranges overlap the result is the overlapping range.
-Otherwise, the result is the range with the lowest numbers.
-The rationale is that subtasks should not be delayed longer than their refresh range.
-Evaluating a task earlier should not change its result but can consume more energy.
-
-\begin{align}
- \cap_{\textit{safe}} :: \refreshrate{\mathit{Int}}{\mathit{Int}} \; \refreshrate{\mathit{Int}}{\mathit{Int}} & \shortrightarrow \refreshrate{\mathit{Int}}{\mathit{Int}} & \notag \\
- R_1 \cap_{\textit{safe}} R_2 & = R_1 \cap R_2 & \text{if } R_1 \cap R_2 \neq \emptyset \\
- \refreshrate{l_1}{h_1} \cap_{\textit{safe}} \refreshrate{l_2}{h_2} & = \refreshrate{l_2}{h_2} & \text{if } h_2 < l_1 \\
- R_1 \cap_{\textit{safe}} R_2 & = R_1 & \text{otherwise}
-\end{align}
-
-\begin{align}
- \mathcal{R} :: (\mathit{MTask}~v~a) & \shortrightarrow \refreshrate{\mathit{Int}}{\mathit{Int}} \notag \\
- \mathcal{R} (t_1~{.||.}~t_2) & = \mathcal{R}(t_1) \cap_{\textit{safe}} \mathcal{R}(t_2) \label{R:or} \\
- \mathcal{R}(t_1~{.\&\&.}~t_2) & = \mathcal{R}(t_1) \cap_{\textit{safe}} \mathcal{R}(t_2) \label{R:and}\\
- \mathcal{R}(t_1~{>\!\!>\!|.}~t_2) & = \mathcal{R}(t_1) \label{R:seq} \\
- \mathcal{R}(t~{>\!\!>\!=.}~f) & = \mathcal{R}(t) \label{R:bind} \\
- \mathcal{R}(t~{>\!\!>\!\!*.}~[a_1 \ldots a_n]) & = \mathcal{R}(t) \label{R:step} \\
- \mathcal{R}(\mathit{rpeat}~t) & = \refreshrate{0}{0} \label{R:rpeat} \\
- \mathcal{R}(\mathit{rpeatEvery}~d~t) & = \refreshrate{0}{0} \label{R:rpeatevery} \\
- \mathcal{R}(delay~d) & = \refreshrate{d}{d} \label{R:delay} \\
- \mathcal{R}(t) & =
- \left\{%
+\subsection{Deriving rewrite rates}\label{sec:deriving_rewrite_rates}
+Based on these default rewrite rates, the system automatically derives rewrite rates for composed \gls{MTASK} expressions using the function $\mathcal{R}$ as shown in \cref{equ:r}.
+
+\begin{equ}
+ \begin{align}
+ \mathcal{R} :: (\mathit{MTask}~v~a) & \shortrightarrow \rewriterate{\mathit{Int}}{\mathit{Int}} \notag \\
+ \mathcal{R} (t_1~{.||.}~t_2) & = \mathcal{R}(t_1) \cap_{\textit{safe}} \mathcal{R}(t_2) \label{R:or} \\
+ \mathcal{R}(t_1~{.\&\&.}~t_2) & = \mathcal{R}(t_1) \cap_{\textit{safe}} \mathcal{R}(t_2) \label{R:and}\\
+ \mathcal{R}(t~{>\!\!>\!\!*.}~[a_1 \ldots a_n]) & = \mathcal{R}(t) \label{R:step} \\
+ \mathcal{R}(\mathit{rpeat}~t~\mathit{start}) & =
+ \left\{\begin{array}{ll}
+ \mathcal{R}(t) & \text{if $t$ is unstable}\\
+ \rewriterate{r_1-\mathit{start}}{r_2-\mathit{start}} & \text{otherwise}\\
+ \end{array}\right.\\
+ \mathcal{R} (\mathit{waitUntil}~d) & = \rewriterate{e-\mathit{time}}{e-\mathit{time}}\label{R:delay}\\
+ \mathcal{R} (t) & =
+ \left\{%
+ \begin{array}{ll}
+ \rewriterate{\infty}{\infty}~& \text{if}~t~\text{is Stable} \\
+ \rewriterate{r_l}{r_u} & \text{otherwise}
+ \end{array}
+ \right.\label{R:other}
+ \end{align}
+ \caption{Function $\mathcal{R}$ for deriving refresh rates.}%
+ \label{equ:r}
+\end{equ}
+
+\subsubsection{Parallel combinators}
+For parallel combinators, the \emph{or}-combinator (\cleaninline{.\|\|.}) in \cref{R:or} and the \emph{and}-combinator (\cleaninline{.&&.}) in \cref{R:and}, the safe intersection (see \cref{equ:safe_intersect}) of the rewrite rates is taken to determine the rewrite rate of the complete task.
+The conventional intersection does not suffice here because it yields an empty intersection when the intervals do not overlap.
+In that case, the safe intersection behaves will return the range with the lowest numbers.
+The rationale is that subtasks should not be delayed longer than their rewrite range.
+Evaluating a task earlier should not change its result but just consumes more energy.
+
+\begin{equ}
+ \[
+ X \cap_{\textit{safe}} Y = \left\{%
\begin{array}{ll}
- \refreshrate{\infty}{\infty}~& \text{if}~t~\text{is Stable} \\
- \refreshrate{r_l}{r_u} & \text{otherwise}
+ X\cap Y & X\cap Y \neq \emptyset\\
+ Y & Y_2 < X_1\\
+ X & \text{otherwise}\\
\end{array}
- \right.\label{R:other}
-\end{align}
-
-We will briefly discuss the various cases of deriving refresh rates together with the task semantics of the different combinators
-
-\subsubsection{Parallel combinators} For the parallel composition of tasks we compute the intersection of the refresh intervals of the components as outlined in the definition of $\cap_{\textit{safe}}$.
-The operator \cleaninline{.\|\|.} in \cref{R:or} is the \emph{or}-combinator; the first subtask that produces a stable value determines the result of the composition.
-The operator \cleaninline{.&&.} in \cref{R:and} is the \emph{and}-operator. The result is the tuple containing both results when both subtasks have a stable value.
-The refresh rates of the parallel combinators have no direct relation with their task result.
+ \right.
+ \]
+ \caption{Safe intersection operator}\label{equ:safe_intersect}
+\end{equ}
\subsubsection{Sequential combinators}
-For the sequential composition of tasks we only have to look at the refresh rate of the current task on the left.
-The sequential composition operator \cleaninline{>>\|.} in \cref{R:seq} is similar to the monadic sequence operator \cleaninline{>>\|}.
-The operator \cleaninline{>>=.} in \cref{R:bind} provides the stable task result to the function on the right-hand side, similar to the monadic bind.
-The operator \cleaninline{>>~.} steps on an unstable value and is otherwise equal to \cleaninline{>>=.}.
-The step combinator \cleaninline{>>*.} in \cref{R:step} has a list of conditional actions that specify a new task.
+For the step combinator (\cref{R:step})---and all other derived sequential combinators---the refresh rate of the left-hand side task is taken since that is the only task that is rewritten.
+Only after stepping, the combinator rewrites to the right-hand side.
-\subsubsection{Repeat combinators}
+\subsubsection{Repeating combinators}
The repeat combinators repeats their argument indefinitely.
-The combinator \cleaninline{rpeatEvery} guarantees the given delay between repetitions.
-The refresh rate is equal to the refresh rate of the current argument task.
-Only when \cleaninline{rpeatEvery} waits between the iterations of the argument the refresh interval is equal to the remaining delay time.
-
-\subsubsection{Other combinators}
-The refresh rate of the \cleaninline{delay} in \cref{R:delay} is equal to the remaining delay.
-Refreshing stable tasks can be delayed indefinitely, their value never changes.
-For other basic tasks, the values from \cref{tbl:refresh} apply.
-The values $r_l$ and $r_u$ in \cref{R:other} are the lower and upper bound of the rate.
-
-The refresh intervals associated with various steps of the thermostat program from \cref{lst:thermostat} are given in \cref{tbl:intervals}.
+As the \cleaninline{rpeat} task tree node already includes a rewrite rate (set to $\rewriterate{0}{0}$ for a default \cleaninline{rpeat}), both \cleaninline{rpeat} and \cleaninline{rpeatEvery} use the same task tree node and thus only one entry is required here.
+The derived refresh rate of the repeat combinator is the refresh rate of the child if it is unstable.
+Otherwise, the refresh rate is the embedded rate time minus the start time.
+In case of the \cleaninline{rpeat} task, the default refresh rate is $\rewriterate{0}{0}$ so the task immediately refreshes and starts the task again.
+\todo{netter opschrijven}
+
+\subsubsection{Delay combinators}
+Upon installation, a \cleaninline{delay} task is stored as a \cleaninline{waitUntil} task tree containing the time of installation added to the specified time to wait.
+Execution wise, it waits until the current time exceeds the time is greater than the argument time.
+
+\subsubsection{Other tasks}
+All other tasks are captured by \cref{R:other}.
+If the task is stable, rewriting can be delayed indefinitely since the value will not change anyway.
+In all other cases, the values from \cref{tbl:rewrite} apply where $r_l$ and $r_u$ represent the lower and upper bound of this rate.
+
+The rewrite intervals associated with various steps of the thermostat program from \cref{lst:thermostat} are given in \cref{tbl:intervals}.
Those rewrite steps and intervals are circular, after step 2 we continue with step 0 again.
Only the actual reading of the sensor with \cleaninline{temperature dht} offers the possibility for a non-zero delay.
+\subsection{Example}
%%\begin{table}[tb]
\begin{table}
\centering
writeD builtInLED (goal <. temp)
)\end{lstClean}
&
- $\refreshrate{0}{0}$ \\
+ $\rewriterate{0}{0}$ \\
%\hline
1 &
\begin{lstClean}[aboveskip=-2ex,belowskip=-2ex,frame=]
rpeat ( temperature dht >>~. \temp.
writeD builtInLED (goal <. temp)
)\end{lstClean}
- & $\refreshrate{0}{2000}$ \\
+ & $\rewriterate{0}{2000}$ \\
%\hline
2 &
\begin{lstClean}[aboveskip=-2ex,belowskip=-2ex,frame=]
rpeat ( temperature dht >>~. \temp.
writeD builtInLED (goal <. temp)
)\end{lstClean}
- & $\refreshrate{0}{0}$ \\
+ & $\rewriterate{0}{0}$ \\
\bottomrule
\end{tabular}
\end{table}
-\subsection{Tweaking refresh rates}
+\subsection{Tweaking rewrite rates}
A tailor-made \gls{ADT} (see \cref{lst:interval}) determines the timing intervals for which the value is determined at runtime but the constructor is known at compile time.
During compilation, the constructor of the \gls{ADT} is checked and code is generated accordingly.
If it is \cleaninline{Default}, no extra code is generated.
\begin{lstClean}[caption={The \gls{ADT} for timing intervals in \gls{MTASK}.},label={lst:interval}]
:: TimingInterval v = Default
- | BeforeMs (v Int) // yields [+$\refreshrate{0}{x}$+]
- | BeforeS (v Int) // yields [+$\refreshrate{0}{x \times 1000}$+]
- | ExactMs (v Int) // yields [+$\refreshrate{x}{x}$+]
- | ExactS (v Int) // yields [+$\refreshrate{0}{x \times 1000}$+]
- | RangeMs (v Int) (v Int) // yields [+$\refreshrate{x}{y}$+]
- | RangeS (v Int) (v Int) // yields [+$\refreshrate{x \times 1000}{y \times 1000}$+]
+ | BeforeMs (v Int) // yields [+$\rewriterate{0}{x}$+]
+ | BeforeS (v Int) // yields [+$\rewriterate{0}{x \times 1000}$+]
+ | ExactMs (v Int) // yields [+$\rewriterate{x}{x}$+]
+ | ExactS (v Int) // yields [+$\rewriterate{0}{x \times 1000}$+]
+ | RangeMs (v Int) (v Int) // yields [+$\rewriterate{x}{y}$+]
+ | RangeS (v Int) (v Int) // yields [+$\rewriterate{x \times 1000}{y \times 1000}$+]
\end{lstClean}
\subsubsection{Sensors and \texorpdfstring{\glspl{SDS}}{shared data sources}}
-In some applications, it is necessary to read sensors or \glspl{SDS} at a different rate than the default rate given in \cref{tbl:refresh}, i.e.\ to customise the refresh rate.
-This is achieved by calling the access functions with a custom refresh rate as an additional argument (suffixed with the backtick (\cleaninline{`}))
+In some applications, it is necessary to read sensors or \glspl{SDS} at a different rate than the default rate given in \cref{tbl:rewrite}, i.e.\ to customise the rewrite rate.
+This is achieved by calling the access functions with a custom rewrite rate as an additional argument (suffixed with the backtick (\cleaninline{`}))
The adaptions to other classes are similar and omitted for brevity.
-\Cref{lst:dht_ext} shows the extended \cleaninline{dht} and \cleaninline{dio} class definition with functions for custom refresh rates.
+\Cref{lst:dht_ext} shows the extended \cleaninline{dht} and \cleaninline{dio} class definition with functions for custom rewrite rates.
\begin{lstClean}[caption={Auxiliary definitions to \cref{lst:gpio,lst:dht} for \gls{DHT} sensors and digital \gls{GPIO} with custom timing intervals.},label={lst:dht_ext}]
class dht v where
\subsubsection{Repeating tasks}
The task combinator \cleaninline{rpeat} restarts the child task in the evaluation if the previous produced a stable result.
However, in some cases it is desirable to postpone the restart of the child.
-For this, the \cleaninline{rpeatEvery} task is introduced which receives an extra argument, the refresh rate, as shown in \cref{lst:rpeatevery}.
+For this, the \cleaninline{rpeatEvery} task is introduced which receives an extra argument, the rewrite rate, as shown in \cref{lst:rpeatevery}.
Instead of immediately restarting the child once it yields a stable value, it checks whether the lower bound of the provided timing interval has passed since the start of the task\footnotemark.
\footnotetext{In reality, it also compensates for time drift by taking into account the upper bound of the timing interval.
If the task takes longer to stabilise than the upper bound of the timing interval, this upper bound is taken as the start of the task instead of the actual start.}
\end{lstClean}
\section{Task scheduling in the \texorpdfstring{\gls{MTASK}}{mTask} engine}
-The refresh rates from the previous section only tell us how much the next evaluation of the task can be delayed.
+The rewrite rates from the previous section only tell us how much the next evaluation of the task can be delayed.
An \gls{IOT} edge devices executes multiple tasks may run interleaved.
In addition, it has to communicate with a server to collect new tasks and updates of \glspl{SDS}.
-Hence, the refresh intervals cannot be used directly to let the microcontroller sleep.
+Hence, the rewrite intervals cannot be used directly to let the microcontroller sleep.
Our scheduler has the following objectives.
\begin{itemize}
\item
- Meet the deadline whenever possible, i.e.\ the system tries to execute every task before the end of its refresh interval.
+ Meet the deadline whenever possible, i.e.\ the system tries to execute every task before the end of its rewrite interval.
Only too much work on the device might cause an overflow of the deadline.
\item
Achieve long sleep times. Waking up from sleep consumes some energy and takes some time.
\item
The scheduler tries to avoid unnecessary evaluations of tasks as much as possible.
A task should not be evaluated now when its execution can also be delayed until the next time that the device is active.
- That is, a task should preferably not be executed before the start of its refresh interval.
- Whenever possible, task execution should even be delayed when we are inside the refresh interval as long as we can execute the task before the end of the interval.
+ That is, a task should preferably not be executed before the start of its rewrite interval.
+ Whenever possible, task execution should even be delayed when we are inside the rewrite interval as long as we can execute the task before the end of the interval.
\item
The optimal power state should be selected.
Although a system uses less power in a deep sleep mode, it also takes more time and energy to wake up from deep sleep.
When the system knows that it can sleep only a short time it is better to go to light sleep mode since waking up from light sleep is faster and consumes less energy.
\end{itemize}
-The algorithm $\mathcal{R}$ from \cref{sec:deriving_refresh_rates} computes the evaluation rate of the current tasks.
+The algorithm $\mathcal{R}$ from \cref{sec:deriving_rewrite_rates} computes the evaluation rate of the current tasks.
For the scheduler, we transform this interval to an absolute evaluation interval; the lower and upper bound of the start time of that task measured in the time of the \gls{IOT} edge device.
-We obtain those bounds by adding the current system time to the bounds of the computed refresh interval by algorithm $\mathcal{R}$.
+We obtain those bounds by adding the current system time to the bounds of the computed rewrite interval by algorithm $\mathcal{R}$.
For the implementation, it is important to note that the evaluation of a task takes time.
Some tasks are extremely fast, but other tasks require long computations and time-consuming communication with peripherals as well as with the server.
#define INTERRUPTPIN 11
#define DEBOUNCE 30[+\label{lst:arduino_interrupt:defs_to}+]
-volatile byte state = LOW;[+\label{lst:arduino_interrupt:state}+]
+volatile int state = LOW;[+\label{lst:arduino_interrupt:state}+]
volatile bool cooldown = true;[+\label{lst:arduino_interrupt:cooldown}+]
void setup() {[+\label{lst:arduino_interrupt:setup_fro}+]
:: InterruptMode = Change | Rising | Falling | Low | High
\end{lstClean}
-When the \gls{MTASK} device executes this task, it installs an \gls{ISR} and sets the refresh rate of the task to infinity, $\refreshrate{\infty}{\infty}$.
-The interrupt handler is set up in such a way that the refresh rate is changed to $\refreshrate{0}{0}$ once the interrupt triggers.
+When the \gls{MTASK} device executes this task, it installs an \gls{ISR} and sets the rewrite rate of the task to infinity, $\rewriterate{\infty}{\infty}$.
+The interrupt handler is set up in such a way that the rewrite rate is changed to $\rewriterate{0}{0}$ once the interrupt triggers.
As a consequence, the task is executed on the next execution cycle.
The \cleaninline{pirSwitch} function in \cref{lst:pirSwitch} creates, given an interval in \unit{\ms}, a task that reacts to motion detection by a \gls{PIR} sensor (connected to \gls{GPIO} pin 0) by lighting the \gls{LED} connected to \gls{GPIO} pin 13 for the given interval.
pirSwitch =
declarePin D13 PMOutput \ledpin->
declarePin D0 PMInput \pirpin->
- {main = rpeat ( interrupt high pirpin
- >>|. writeD ledpin false
- >>|. delay (lit interval)
- >>|. writeD ledpin true) }
+ {main = rpeat ( interrupt high pirpin
+ >>|. writeD ledpin false
+ >>|. delay (lit interval)
+ >>|. writeD ledpin true) }
\end{lstClean}
\subsection{\texorpdfstring{\Gls{MTASK}}{MTask} engine}
Interrupt event flags are processed at the beginning of the event loop, before tasks are executed.
For each subscribed task, the task tree is searched for nodes listening for the particular interrupt.
When found, the node is flagged and the pin status is written.
-Afterwards, the evaluation interval of the task is set to $\refreshrate{0}{0}$ and the task is reinsterted at the front of the scheduling queue to ensure rapid evaluation of the task.
+Afterwards, the evaluation interval of the task is set to $\rewriterate{0}{0}$ and the task is reinsterted at the front of the scheduling queue to ensure rapid evaluation of the task.
Finally, the event is removed from the registration and the interrupt is disabled.
The interrupt can be disabled as all tasks waiting for the interrupt become stable after firing.
More occurrences of the interrupts do not change the value of the task as stable tasks keep the same value forever.
repositories / phd-thesis.git / blobdiff