top/green.tex

   1 \documentclass[../thesis.tex]{subfiles}
   2
   3 \input{subfilepreamble}
   4
   5 \setcounter{chapter}{7}
   6
   7 \begin{document}
   8 \input{subfileprefix}
   9 \chapter{Green computing with mTask}%
  10 \label{chp:green_computing_mtask}
  11 \begin{chapterabstract}
  12         This chapter demonstrates the energy-saving features of \gls{MTASK} by:
  13         \begin{itemize}
  14                 \item giving an overview of general green computing measures for edge devices;
  15                 \item explaining task scheduling in \gls{MTASK}, and how to tweak it so suit the applications and energy needs;
  16                 \item showing how to use interrupts in \gls{MTASK} to reduce the need for polling.
  17         \end{itemize}
  18 \end{chapterabstract}
  19
  20 The edge layer of the \gls{IOT} is built from energy-efficient devices that sense and interact with the world.
  21 While individual devices consume little energy, the sheer number of devices in total amounts to a lot.
  22 Furthermore, many of these devices operate on batteries and higher energy consumption increases the amount of e-waste as \gls{IOT} edge devices are often hard to reach and consequently hard to replace \citep{nizetic_internet_2020}.
  23 It is therefore crucial to lower their energy consumption.
  24
  25 To reduce the power consumption of an \gls{IOT} edge device, the specialised low-power sleep modes of the microprocessors can be leveraged.
  26 Different sleep modes achieve different power reductions because of their run time characteristics.
  27 These specifics range from disabling or suspending the \gls{WIFI} radio; stop powering (parts) of the \gls{RAM}; disabling peripherals; or even turning off the processor completely, requiring an external signal to wake up again.
  28 Determining exactly when, and for how long it is safe to sleep is expensive in the general case.
  29 In practise, it means that either annotations in the source code, a \gls{RTOS}, or a scheduler is required.
  30
  31 \Cref{tbl:top_sleep} shows the properties and current consumption of two commonly used microcontrollers in their various sleep modes.
  32 It uncovers that switching the \gls{WIFI} radio off yields the biggest energy saving.
  33 In most \gls{IOT} applications, we need \gls{WIFI} for communications.
  34 It is fine to switch it off when not communicating, but after switching it on, the \gls{WIFI} protocol needs to transmit a number of messages to re-establish the connection.
  35 This implies that it is only worthwhile to switch the radio off when this can be done for some time.
  36 The details vary per system and situation.
  37 As a rule of thumb, derived from experimentation, it is only worthwhile to switch the \gls{WIFI} off when it is not needed for at least some tens of seconds.
  38
  39 \begin{table}
  40         \centering
  41         \caption{Current use (\unit{\milli\ampere}) of two microprocessor boards in various sleep modes.}%
  42         \label{tbl:top_sleep}
  43         \small
  44         \begingroup
  45         % default is 6pt but this gives an overflow of 4.25816pt
  46         \setlength\tabcolsep{5.5pt}
  47         \begin{tabular}{ccccccccc}
  48                 \toprule
  49                                   & \multicolumn{4}{c}{\Gls{WEMOS} D1 mini}
  50                                   & \multicolumn{4}{c}{Adafruit Feather M0 \gls{WIFI}} \\
  51                 \midrule
  52                           & active   & modem & light & deep  & active & modem & light & deep\\
  53                           &          & sleep & sleep & sleep &        & sleep & sleep & sleep\\
  54                 \midrule
  55                 \gls{WIFI}& on       & off   & off   & off   & on     & off   & off   & off\\
  56                 CPU       & on       & on    & pend. & off   & on     & on    & idle  & idle\\
  57                 \gls{RAM} & on       & on    & on    & off   & on     & on    & on    & on\\
  58                 \midrule
  59                 current   & \numrange{100}{240} & \num{15} & \num{0.5} & \num{0.002} & \numrange{90}{300} & \num{5} & \num{2} &  \num{0.005}\\
  60                 \bottomrule
  61         \end{tabular}
  62         \endgroup
  63 \end{table}
  64
  65 \section{Green \IOT{} computing}
  66 The data in \cref{tbl:top_sleep} shows that it is worthwhile to put the system in some sleep mode when there is temporarily no work to be done.
  67 A deeper sleep mode saves more energy, but also requires more work to restore the software to its working state.
  68 A processor like the ESP8266 driving the \gls{WEMOS} D1 mini loses the content of its \gls{RAM} in deep sleep mode.
  69 As a result, after waking up, the program itself is preserved, since it is stored in flash memory, but the program state is lost.
  70 When there is a program state to be preserved, we must either store it elsewhere, limit us to light sleep, or use a microcontroller that keeps the \gls{RAM} intact during deep sleep.
  71 For mTasks this implies that the \gls{MTASK} \gls{RTS} is preserved during deep sleep, but all shipped tasks and their states are lost.
  72
  73 For edge devices executing a single task, explicit sleeping to save energy can be achieved without too much hassle.
  74 This becomes much more challenging as soon as multiple independent tasks run on the same device.
  75 Sleeping of the device induced by one task prevents progress of all tasks.
  76 This is especially annoying when the other tasks are executing time critical parts, like communication protocols.
  77 Such protocols control the communication with sensors and actuators.
  78 Without the help of an \gls{OS}, the programmer is forced to combine all subtasks into one big system that decides if it is safe to sleep for all subtasks.
  79
  80 The \gls{MTASK} language offers abstractions for edge layer-specific details such as the heterogeneity of architectures, platforms and frameworks; peripheral access; and multitasking but also for energy consumption and scheduling.
  81 In the \gls{MTASK} system, tasks are implemented as a rewrite system, where the work is automatically segmented in small atomic bits and stored as a task tree.
  82 Each cycle, a single rewrite step is performed on all task trees.
  83 During rewriting, each step, tasks do a bit of their work and progress steadily, allowing interleaved and seemingly parallel operation.
  84 Atomic blocks, such as \gls{IO}, are always contained within a rewrite step.
  85 This is very convenient, since the system can inspect the current state of all \gls{MTASK} expressions after a rewrite and decide if sleeping and how long is possible.
  86 After each loop, the \gls{RTS} knows which task is waiting on which triggers.
  87 With this information, the system determines when it is possible and safe to sleep, and chooses the optimal sleep mode according to the sleeping time.
  88 %As a consequence, we cannot have fair multitasking.
  89 %When a single rewrite step would take forever due to an infinite sequence of function calls, this would block the entire \gls{IOT} node.
  90 %Even infinite sequences rewrite steps are perfectly fine.
  91 %The \gls{MTASK} system does proper tail-call optimisations to facilitate this.
  92
  93 \section{Rewrite interval}
  94 Some \gls{MTASK} programs contain one or more explicit \cleaninline{delay} primitives, offering a natural pause.
  95 However, there are many \gls{MTASK} programs that just specify a repeated set of primitives.
  96 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}.
  97
  98 \begin{lstClean}[caption={A basic thermostat task.},label={lst:thermostat}]
  99 thermostat :: Main (MTask v Bool) | mtask, dht v
 100 thermostat = declarePin D8 PMOutput \ledPin->
 101         DHT (DHT_DHT (i2c 0x36)) \dht->
 102         {main = rpeat (temperature dht >>~. \temp->
 103                        writeD ledPin (goal <. temp))}
 104 \end{lstClean}
 105
 106 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.
 107 The \gls{MTASK} machinery ensures that if there are other tasks running on the device, they make progress.
 108 However, this solution is far from perfect when we take power consumption into account.
 109 In most applications, it is very unlikely that the temperature changes significantly within one minute, let alone within some milliseconds.
 110 Hence, it is sufficient to repeat the measurement with an appropriate interval.
 111
 112 There are various ways to improve this program.
 113 The simplest solution is to add an explicit delay to the body of the repeat loop.
 114 A slightly more sophisticated option is to add a repetition period to the \cleaninline{rpeat} combinator.
 115 The combinator implementing this is called \cleaninline{rpeatEvery}.
 116 Both solutions rely on an explicit action of the programmer.
 117
 118 Fortunately, \gls{MTASK} also contains machinery to do this automatically.
 119 The key of this solution is to associate an evaluation interval with each task dynamically.
 120 The interval $\rewriterate{low}{high}$ indicates that the evaluation can be safely delayed by any number of milliseconds within that range.
 121 Such an interval is just a hint for the \gls{RTS}.
 122 It is not a guarantee that the evaluation takes place in the given interval.
 123 For example, other parts of the task expression can force an earlier evaluation of this part of the task.
 124 On the other hand, when the system is very busy with other work, the task might even be executed after the upper bound of the interval.
 125 The system calculates the rewrite rates from the current state of the task, i.e.\ the task tree.
 126 This has the advantage that the programmer does not have to deal with them explicitly and that they are available in each and every \gls{MTASK} program.
 127
 128 \subsection{Basic tasks}
 129 We start by assigning default rewrite rates to basic tasks.
 130 These rewrite rates reflect the expected change rates of sensors and other inputs.
 131 Basic tasks to set a value of a sensor or actuator have a rate of $\rewriterate{0}{0}$, i.e.\ this is never delayed.
 132 An example of such a one-shot task in the task that writes to a \gls{GPIO} pin.
 133 Basic tasks that continuously read a sensor or otherwise interact with a peripheral have default rewrite rates that fit standard usage of the sensor.
 134 \Cref{tbl:rewrite} shows the default values for the basic tasks.
 135 Reading \glspl{SDS} and measuring fast sensors such as sound or light aim for a rewrite every \qty{100}{\ms}.
 136 Medium slow sensors such as gesture sensors are expected to rewrite every \qty{1000}{\ms}.
 137 Slow sensors such as temperature or air quality have an upper bound of \qty{2000}{\ms}.
 138 In \cref{sec:tweak_rewrite} we show how the programmer can tweak these rewrite rates to match specific needs.
 139
 140 \begin{table}
 141         \centering
 142         \caption{Default rewrite rates of basic tasks.}%
 143         \label{tbl:rewrite}
 144         \begin{tabular}{ll}
 145                 \toprule
 146                 task & default interval\\
 147                 \midrule
 148                 reading \pgls{SDS} & $\rewriterate{0}{2000}$\\
 149                 slow sensor & $\rewriterate{0}{2000}$\\
 150                 medium sensor & $\rewriterate{0}{1000}$\\
 151                 fast sensor & $\rewriterate{0}{100}$\\
 152                 \bottomrule
 153         \end{tabular}
 154 \end{table}
 155
 156 \subsection{Deriving rewrite rates}\label{sec:deriving_rewrite_rates}
 157 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}.
 158
 159 \begin{equ}
 160         \begin{align}
 161                 \mathcal{R} :: (\mathit{MTask}~v~a)    & \shortrightarrow \rewriterate{\mathit{Int}}{\mathit{Int}} \notag \\
 162                 \mathcal{R} (t_1~{.||.}~t_2)  & = \mathcal{R}(t_1) \cap_{\textit{safe}} \mathcal{R}(t_2) \label{R:or} \\
 163                 \mathcal{R}(t_1~{.\&\&.}~t_2) & = \mathcal{R}(t_1) \cap_{\textit{safe}} \mathcal{R}(t_2) \label{R:and}\\
 164                 \mathcal{R}(t~{>\!\!>\!\!*.}~[a_1 \ldots a_n]) & = \mathcal{R}(t) \label{R:step} \\
 165                 \mathcal{R}(\mathit{rpeat}~t~\mathit{start})   & =
 166                         \left\{\begin{array}{ll}
 167                                 \mathcal{R}(t) & \text{if $t$ is unstable}\\
 168                                 \rewriterate{r_1-\mathit{start}}{r_2-\mathit{start}} & \text{otherwise}\\
 169                                                                                                                                          & \text{\bf where } \mathcal{R}(t) = \rewriterate{r_1}{r_2}\\
 170                         \end{array}\right.\\
 171                 \mathcal{R} (\mathit{waitUntil}~d) & = \rewriterate{e-\mathit{time}}{e-\mathit{time}}\label{R:delay}\\
 172                 \mathcal{R} (t) & =
 173                         \left\{%
 174                                 \begin{array}{ll}
 175                                         \rewriterate{\infty}{\infty}~& \text{if}~t~\text{is Stable} \\
 176                                         \rewriterate{r_l}{r_u} & \text{otherwise}
 177                                 \end{array}
 178                         \right.\label{R:other}
 179         \end{align}
 180         \caption{Function $\mathcal{R}$ for deriving refresh rates.}%
 181         \label{equ:r}
 182 \end{equ}
 183
 184 \subsubsection{Parallel combinators}
 185 For parallel combinators, the disjunction combinator (\cleaninline{.\|\|.}) in \cref{R:or} and the conjunction 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.
 186 The conventional intersection does not suffice here because it yields an empty intersection when the intervals do not overlap.
 187 In that case, the safe intersection returns the range with the lowest numbers.
 188 The rationale is that subtasks should preferably not be delayed longer than their rewrite range.
 189 Evaluating a task earlier should not change its result but just consumes more energy.
 190
 191 \begin{equ}
 192         \[
 193                 X \cap_{\textit{safe}} Y = \left\{%
 194                         \begin{array}{lll}
 195                                 X\cap Y & X\cap Y \neq \emptyset\\
 196                                 Y & Y_2 < X_1 & \text{\bf where } Y = \rewriterate{Y_1}{Y_2} \text{ and } X = \rewriterate{X_1}{X_2}\\
 197                                 X & \text{otherwise}\\
 198                         \end{array}
 199                         \right.
 200         \]
 201         \caption{Safe intersection operator}\label{equ:safe_intersect}
 202 \end{equ}
 203
 204 \subsubsection{Sequential combinators}
 205 For the step combinator (\cref{R:step})---and all other derived sequential combinators\nobreak---\nobreak\hskip0ptthe refresh rate of the left-hand side task is taken since that is the only task that is rewritten during evaluation.
 206 Only after stepping, the combinator rewrites to the result of evaluating the right-hand side expression.
 207
 208 \subsubsection{Repeating combinators}
 209 The repeat combinator repeats its argument indefinitely.
 210 There are two repeating combinators, \cleaninline{rpeat} and \cleaninline{rpeatEvery} that both use the same task tree node.
 211 The \cleaninline{rpeat} task combinator is a special type of \cleaninline{rpeatEvery}, i.e.\ the rewrite rate is fixed to $\rewriterate{0}{0}$.
 212 The derived refresh rate of the repeat combinator is the refresh rate of the child if it is unstable.
 213 Otherwise, the refresh rate is the embedded rate time minus the start time.
 214 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.
 215
 216 \subsubsection{Delay combinators}
 217 Upon installation, a \cleaninline{delay} task is stored as a \cleaninline{waitUntil} task, containing the time of installation added to the specified time to wait.
 218 Execution wise, it waits until the current time exceeds the time the argument time.
 219
 220 \subsubsection{Other tasks}
 221 All other tasks are captured by \cref{R:other}.
 222 If the task is stable, rewriting can be delayed indefinitely since the value will not change anyway.
 223 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.
 224
 225 \subsection{Example}
 226 The rewrite intervals associated with various steps of the thermostat program from \cref{lst:thermostat} are given in \cref{tbl:intervals}.
 227 The rewrite steps and intervals are circular.
 228 After step 2 we continue with step 0 again.
 229 Only the actual reading of the sensor with \cleaninline{temperature dht} offers the possibility for a non-zero delay.
 230
 231 %%\begin{table}[tb]
 232 \begin{table}
 233         \centering
 234         \caption{Rewrite steps of the thermostat from \cref{lst:thermostat} and associated intervals.}%
 235         \label{tbl:intervals}
 236         \begin{tabular}{cp{20em}c}
 237                 \toprule
 238                 Step & Expression & Interval \\
 239                 \midrule
 240                 0  &
 241                 \begin{lstClean}[aboveskip=-2ex,belowskip=-2ex,frame=]
 242 rpeat ( temperature dht >>~. \temp.
 243         writeD builtInLED (goal <. temp)
 244 )\end{lstClean}
 245                    &
 246                    $\rewriterate{0}{0}$ \\
 247                    %\hline
 248                 1  &
 249                 \begin{lstClean}[aboveskip=-2ex,belowskip=-2ex,frame=]
 250 temperature dht >>~. \temp.
 251 writeD builtInLED (goal <. temp) >>|.
 252 rpeat ( temperature dht >>~. \temp.
 253         writeD builtInLED (goal <. temp)
 254 )\end{lstClean}
 255                    & $\rewriterate{0}{2000}$ \\
 256                    %\hline
 257                 2  &
 258                 \begin{lstClean}[aboveskip=-2ex,belowskip=-2ex,frame=]
 259 writeD builtInLED false >>|.
 260 rpeat ( temperature dht >>~. \temp.
 261         writeD builtInLED (goal <. temp)
 262 )\end{lstClean}
 263                 & $\rewriterate{0}{0}$ \\
 264                 \bottomrule
 265         \end{tabular}
 266 \end{table}
 267
 268 \subsection{Tweaking rewrite rates}\label{sec:tweak_rewrite}
 269 A tailor-made \gls{ADT} (see \cref{lst:interval}) is used to tweak the timing intervals.
 270 The value is determined at runtime, but the constructor is known at compile time.
 271 During compilation, the constructor of the \gls{ADT} is checked and code is generated accordingly.
 272 If it is \cleaninline{Default}, no extra code is generated.
 273 In the other cases, code is generated to wrap the task tree node in a \emph{tune rate} node.
 274 In the case that there is a lower bound, i.e.\ the task must not be executed before this lower bound, an extra \emph{rate limit} task tree node is generated that performs a no-op rewrite if the lower bound has not passed but caches the task value.
 275
 276 \begin{lstClean}[caption={The \gls{ADT} for timing intervals in \gls{MTASK}.},label={lst:interval}]
 277 :: TimingInterval v = Default
 278                     | BeforeMs (v Int)         // yields [+$\rewriterate{0}{x}$+]
 279                     | BeforeS  (v Int)         // yields [+$\rewriterate{0}{x \times 1000}$+]
 280                     | ExactMs  (v Int)         // yields [+$\rewriterate{x}{x}$+]
 281                     | ExactS   (v Int)         // yields [+$\rewriterate{0}{x \times 1000}$+]
 282                     | RangeMs  (v Int) (v Int) // yields [+$\rewriterate{x}{y}$+]
 283                     | RangeS   (v Int) (v Int) // yields [+$\rewriterate{x \times 1000}{y \times 1000}$+]
 284 \end{lstClean}
 285
 286 \subsubsection{Sensors and shared data sources}
 287 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.
 288 This is achieved by calling the access functions with a custom rewrite rate as an additional argument (suffixed with the backtick (\cleaninline{`}))
 289 The adaptions to other classes are similar and omitted for brevity.
 290 \Cref{lst:dht_ext} shows the extended \cleaninline{dht} and \cleaninline{dio} class definition with functions for custom rewrite rates.
 291
 292 \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}]
 293 class dht v where
 294         ...
 295         temperature` :: (TimingInterval v) (v DHT) -> MTask v Real
 296         temperature  ::                    (v DHT) -> MTask v Real
 297         humidity`    :: (TimingInterval v) (v DHT) -> MTask v Real
 298         humidity     ::                    (v DHT) -> MTask v Real
 299
 300 class dio p v | pin p where
 301         ...
 302         readD` :: (TimingInterval v) (v p) -> MTask v Bool | pin p
 303         readD  ::                    (v p) -> MTask v Bool | pin p
 304 \end{lstClean}
 305
 306 As an example, we define an \gls{MTASK} that updates the \gls{SDS} \cleaninline{tempSds} in \gls{ITASK} in a tight loop.
 307 The \cleaninline{temperature`} reading dictates that this happens at least once per minute.
 308 Without other tasks on the device, the temperature \gls{SDS} is updated once per minute.
 309 Other tasks can cause a slightly more frequent update.
 310
 311 \begin{lstClean}[caption={Updating \pgls{SDS} in \gls{ITASK} at least once per minute.},label={lst:updatesds2}]
 312 delayTime :: TimingInterval v | mtask v
 313 delayTime = BeforeS (lit 60) // 1 minute in seconds
 314
 315 devTask :: Main (MTask v Real) | mtask, dht, lowerSds v
 316 devTask =
 317         DHT (DHT_DHT pin DHT11) \dht =
 318         lowerSds \localSds = tempSds
 319         In {main = rpeat (temperature` delayTime dht >>~. setSds localSds)}
 320 \end{lstClean}
 321
 322 \subsubsection{Repeating tasks}
 323 The task combinator \cleaninline{rpeat} restarts the child task in the evaluation if the previous produced a stable result.
 324 However, in some cases it is desirable to postpone the restart of the child.
 325 For this, the \cleaninline{rpeatEvery} task is introduced which receives an extra argument, the rewrite rate, as shown in \cref{lst:rpeatevery}.
 326 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.
 327 \footnotetext{In reality, it also compensates for time drift by taking into account the upper bound of the timing interval.
 328 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.}
 329
 330 \begin{lstClean}[caption={Repeat task combinator with a timing interval.},label={lst:rpeatevery}]
 331 class rpeat v where
 332         rpeat :: (MTask v t) -> MTask v t
 333         rpeatEvery v :: (TimingInterval v) (MTask v t) -> MTask v t
 334 \end{lstClean}
 335
 336 \Cref{lst:rpeateveryex} shows an example of an \gls{MTASK} task utilising the \cleaninline{rpeatEvery} combinator that would be impossible to create with the regular \cleaninline{rpeat}.
 337 The \cleaninline{timedPulse} function creates a task that sends a \qty{50}{\ms} pulse to the \gls{GPIO} pin 0 every second.
 338 The task created by the \cleaninline{timedPulseNaive} functions emulates the behaviour by using \cleaninline{rpeat} and \cleaninline{delay}.
 339 However, this results in a time drift because rewriting tasks trees takes some time and the time it takes can not always be reliably predicted due to external factors.
 340 E.g.\ writing to \gls{GPIO} pins takes some time, interrupts may slow down the program (see \cref{lst:interrupts}), or communication may occur in between task evaluations.
 341
 342 \begin{lstClean}[caption={Example program for the repeat task combinator with a timing interval.},label={lst:rpeateveryex}]
 343 timedPulse :: Main (MTask v Bool) | mtask v
 344 timedPulse = declarePin D0 PMOutput \d0->
 345         in {main = rpeatEvery (ExactSec (lit 1)) (
 346                      writeD d0 true
 347                 >>|. delay (lit 50)
 348                 >>|. writeD d0 false
 349                 )
 350         }
 351
 352 timedPulseNaive :: Main (MTask v Bool) | mtask v
 353 timedPulseNaive = declarePin D0 PMOutput \d0->
 354         {main = rpeat (
 355                      writeD d0 true
 356                 >>|. delay (lit 50)
 357                 >>|. writeD d0 false
 358                 >>|. delay (lit 950))
 359         }
 360 \end{lstClean}
 361
 362 \section{Task scheduling in the mTask engine}\label{sec:scheduling}
 363 The rewrite rates from the previous section only tell us how much the next evaluation of the task can be delayed.
 364 In the \gls{MTASK} system, an \gls{IOT} edge device can run multiple tasks.
 365 In addition, it has to communicate with a server to collect new tasks and updates of \glspl{SDS}.
 366 Hence, the rewrite intervals cannot be used directly to let the microcontroller sleep, so a scheduler is involved.
 367 Our scheduler has the following objectives.
 368
 369 \begin{itemize}
 370         \item
 371                 Meet the deadline whenever possible, i.e.\ the system tries to execute every task before the end of its rewrite interval.
 372                 Only too much work on the device might cause an overflow of the deadline.
 373         \item
 374                 Achieve long sleep times. Waking up from sleep consumes some energy and takes some time.
 375                 Hence, we prefer a single long sleep over splitting the sleep interval into several smaller pieces.
 376         \item
 377                 The scheduler tries to avoid unnecessary evaluations of tasks as much as possible.
 378                 A task should not be evaluated now when its execution can also be delayed until the next time that the device is active.
 379                 That is, a task should preferably not be executed before the start of its rewrite interval.
 380                 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.
 381         \item
 382                 The optimal power state should be selected.
 383                 Although a system uses less power in a deep sleep mode, it also takes more time and energy to wake up from deep sleep.
 384                 When the system knows that it can sleep only for a short time it is better to go to light sleep mode since waking up from light sleep is faster and consumes less energy.
 385 \end{itemize}
 386
 387 The algorithm $\mathcal{R}$ from \cref{sec:deriving_rewrite_rates} computes the evaluation rate of the current tasks.
 388 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.
 389 We obtain those bounds by adding the current system time to the bounds of the computed rewrite interval by algorithm $\mathcal{R}$.
 390
 391 For the implementation, it is important to note that the evaluation of a task takes time.
 392 Some tasks are extremely fast, but other tasks require longer computations and time-consuming communication with peripherals as well as with the server.
 393 These execution times can yield a considerable and noticeable time drift in \gls{MTASK} programs.
 394 For instance, a task like \cleaninline{rpeatEvery (ExactMs 1) t} should repeat \cleaninline{t} every millisecond.
 395 The programmer might expect that \cleaninline{t} will be executed for the ${(N+1)}$th time after $N$ milliseconds.
 396 Uncompensated time drift makes this considerably later.
 397 The \gls{MTASK} \gls{RTS} does not pretend to be a hard \gls{RTOS}, and gives no firm guarantees with respect to evaluation time.
 398 Nevertheless, we try to make time handling as reliable as possible.
 399 This is achieved by adding the start time of this round of task evaluations rather than the current time to compute absolute execution intervals.
 400
 401 \subsection{Scheduling Tasks}
 402 Apart from the task to execute, the device maintains the connection with the server and checks there for new tasks and updates of \gls{SDS}.
 403 When the microcontroller is active, the connection is checked and updates from the server are processed.
 404 After that, the tasks that are within the execution window are executed.
 405 Next, the microcontroller goes to light sleep for the minimum of a predefined interval and the task delay.
 406
 407 In general, the microcontroller executes multiple \gls{MTASK} tasks at the same time.
 408 The \gls{MTASK} device repeatedly checks for inputs from the server and executes all tasks that cannot be delayed to the next evaluation round one step.
 409 The tasks are stored in a priority queue to check efficiently which of them need stepping.
 410 The \gls{MTASK} tasks are ordered at their latest start time in this queue; earliest deadline first.
 411 We use the earliest deadline to order tasks with equal latest deadline.
 412
 413 It is very complicated to make an optimal scheduling algorithm for tasks to minimise the energy consumption.
 414 We use a simple heuristic to evaluate tasks and determine sleep time rather than wasting energy on a fancy evaluation algorithm.
 415 \Cref{lst:evalutionRound} gives this algorithm in pseudo code.
 416 First the edge device checks for new tasks and updates of \glspl{SDS}.
 417 This communication adds the new task to the queue, if there were any.
 418 The \cleaninline{stepped} set contains all tasks evaluated in this evaluation round.
 419 Next, we evaluate tasks from the queue until we encounter a task that has an evaluation interval that has not started.
 420 This may result in evaluating tasks earlier than required, but maximises the opportunities to sleep after this evaluation round.
 421 %Using the \prog{stepped} set ensures that we evaluate each task at most once during an evaluation round.
 422 Executed tasks are temporarily stored in the \cleaninline{stepped} set instead of inserted directly into the queue to ensure that they are evaluated at most once in an evaluation round to ensure that there is frequent communication with the server.
 423 A task that produces a stable value is completed and is not queued again.
 424
 425 \begin{algorithm}
 426 %\DontPrintSemicolon
 427 \SetKwProg{Repeatt}{repeat}{}{end}
 428 \KwData{queue = []\;}
 429 \Begin{
 430         \Repeatt{}{
 431                 time = currentTime()\;
 432                 queue += communicateWithServer()\;
 433                 stepped = []\tcp*{tasks stepped in this round}
 434                 \While{$\neg$empty(queue) $\wedge$ earliestDeadline(top(queue)) $\leq$ time}{
 435                         (task, queue) = pop(queue)\;
 436                         task2 = step(task)\tcp*{computes new execution interval}
 437                         \If(\tcp*[f]{not finished after step}){$\neg$ isStable(task2)}{
 438                                 stepped += task2\;
 439                         }
 440                 }
 441                 queue = merge(queue, stepped)\;
 442                 sleep(queue)\;
 443         }
 444 }
 445 \caption{Pseudo code for the evaluation round of tasks in the queue.}
 446 \label{lst:evalutionRound}
 447 \end{algorithm}
 448
 449 The \cleaninline{sleep} function determines the maximum sleep time based on the top of the queue.
 450 The computed sleep time and the characteristics of the microprocessor determine the length and depth of the sleep.
 451 For very short sleep times it is not worthwhile to put the processor in sleep mode.
 452 In the current \gls{MTASK} \gls{RTS}, the thresholds are determined by experimentation but can be tuned by the programmer.
 453 On systems that lose the content of their \gls{RAM} it is not possible to go to deep sleep mode.
 454
 455 \section{Interrupts}\label{lst:interrupts}
 456 Most microcontrollers have built-in support for processor interrupts.
 457 These interrupts are hard-wired signals that interrupt the normal flow of the program or sleep state in order to execute a small piece of code, the \gls{ISR}.
 458 While the \glspl{ISR} look like regular functions, they do come with some limitations.
 459 For example, they must be very short, in order not to miss future interrupts; can only do very limited \gls{IO}; cannot reliably check the clock; and they operate in their own stack, and thus communication must happen via global variables.
 460 After the execution of the \gls{ISR}, the normal program flow is resumed.
 461 Interrupts are heavily used internally in the firmware of microcontrollers to perform timing critical operations such as \gls{WIFI}, \gls{I2C}, or \gls{SPI} communication; completed \gls{ADC} conversions; software timers; exception handling; \etc.
 462
 463 Using interrupts in an \gls{MTASK} task offer two substantial benefits: fewer missed events and better energy usage.
 464 Sometimes an external event such as a button press only occurs for a small duration, making it possible to miss it due to it happening right between two polls.
 465 Using interrupts is not a fool-proof way of never missing an event.
 466 Events could still be missed if they occur during the execution of an \gls{ISR} or while the microcontroller was in the process of waking up from a triggered interrupt.
 467 There are also some sensors, such as the CCS811 air quality sensor, with support for triggering interrupts when a measurement exceeds a critical limit.
 468
 469 There are several different types of interrupts possible that each fire in slightly different circumstances (see \cref{tbl:gpio_interrupts}).
 470
 471 \begin{table}
 472         \centering
 473         \caption{Overview of \gls{GPIO} interrupt types.}%
 474         \label{tbl:gpio_interrupts}
 475         \begin{tabular}{ll}
 476                 \toprule
 477                 type    & triggers\\
 478                 \midrule
 479                 change  & input changes\\
 480                 falling & input becomes low\\
 481                 rising  & input becomes high\\
 482                 low     & input is low\\
 483                 high    & input is high\\
 484                 \bottomrule
 485         \end{tabular}
 486 \end{table}
 487
 488 \subsection{\Gls{ARDUINO} platform}
 489 \Cref{lst:arduino_interrupt} shows an exemplatory program utilising interrupts written using the \ccpp{} dialect of \gls{ARDUINO}.
 490 The example shows a debounced light switch for the built-in \gls{LED} connected to \gls{GPIO} pin 13.
 491 When the user presses the button connected to \gls{GPIO} pin 11, the state of the \gls{LED} changes.
 492 As buttons sometimes induce noise shortly after pressing, events within \qty{30}{\ms} after pressing are ignored.
 493 In between the button presses, the device goes into deep sleep using the \arduinoinline{LowPower} library to handle the processor specific sleep interface.
 494
 495 \Crefrange{lst:arduino_interrupt:defs_fro}{lst:arduino_interrupt:defs_to} define the pin and debounce constants.
 496 \Cref{lst:arduino_interrupt:state} defines the current state of the \gls{LED}, it is declared \arduinoinline{volatile} to exempt it from compiler optimisations because it is accessed in the interrupt handler.
 497 \Cref{lst:arduino_interrupt:cooldown} flags whether the program is in debounce state, i.e.\ events should be ignored for a short period of time.
 498
 499 In the \arduinoinline{setup} function (\crefrange{lst:arduino_interrupt:setup_fro}{lst:arduino_interrupt:setup_to}), the pinmode of the \gls{LED} and interrupt pins are set.
 500 Furthermore, the microcontroller is instructed to wake up from sleep mode when a \emph{rising} interrupt occurs on the interrupt pin and to call the \gls{ISR} at \crefrange{lst:arduino_interrupt:isr_fro}{lst:arduino_interrupt:isr_to}.
 501 This \gls{ISR} checks if the program is in cooldown state.
 502 If this is not the case, the state of the \gls{LED} is toggled.
 503 In any case, the program goes into cooldown state afterwards.
 504
 505 In the \arduinoinline{loop} function, the microcontroller goes to low-power sleep immediately and indefinitely.
 506 Only when an interrupt triggers, the program continues, writes the state to the \gls{LED}, waits for the debounce time, and finally disables the \arduinoinline{cooldown} state.
 507
 508 \begin{lstArduino}[numbers=left,label={lst:arduino_interrupt},caption={Light switch using interrupts.}]
 509 #define LEDPIN 13[+\label{lst:arduino_interrupt:defs_fro}+]
 510 #define INTERRUPTPIN 11
 511 #define DEBOUNCE 30[+\label{lst:arduino_interrupt:defs_to}+]
 512
 513 volatile int state = LOW;[+\label{lst:arduino_interrupt:state}+]
 514 volatile bool cooldown = true;[+\label{lst:arduino_interrupt:cooldown}+]
 515
 516 void setup() {[+\label{lst:arduino_interrupt:setup_fro}+]
 517         pinMode(LEDPIN, OUTPUT);
 518         pinMode(INTERRUPTPIN, INPUT);
 519         LowPower.attachInterruptWakeup(INTERRUPTPIN, buttonPressed, RISING);
 520 }[+\label{lst:arduino_interrupt:setup_to}+]
 521
 522 void loop() {[+\label{lst:arduino_interrupt:loop_fro}+]
 523         LowPower.sleep();
 524         digitalWrite(LEDPIN, state);
 525         delay(DEBOUNCE);
 526         cooldown = false;
 527 }[+\label{lst:arduino_interrupt:loop_to}+]
 528
 529 void buttonPressed() { /* ISR */ [+\label{lst:arduino_interrupt:isr_fro}+]
 530         if (!cooldown)
 531                 state = !state;
 532         cooldown = true;
 533 }[+\label{lst:arduino_interrupt:isr_to}+]
 534 \end{lstArduino}
 535
 536 \subsection{The mTask language}
 537 \Cref{lst:mtask_interrupts} shows the interrupt interface in \gls{MTASK}.
 538 The \cleaninline{interrupt} class contains a single function that, given an interrupt mode and a \gls{GPIO} pin, produces a task that represents this interrupt.
 539 Lowercase variants of the various interrupt modes such as \cleaninline{change :== lit Change} are available as convenience macros (see \cref{sec:expressions}).
 540 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}$.
 541 The interrupt handler is set up in such a way that the rewrite rate is changed to $\rewriterate{0}{0}$ once the interrupt triggers.
 542 As a consequence, the task is executed on the next execution cycle.
 543
 544 \begin{lstClean}[label={lst:mtask_interrupts},caption={The interrupt interface in \gls{MTASK}.}]
 545 class interrupt v where
 546         interrupt :: (v InterruptMode) (v p) -> MTask v Bool | pin p
 547
 548 :: InterruptMode = Change | Rising | Falling | Low | High
 549 \end{lstClean}
 550
 551 The \cleaninline{pirSwitch} function in \cref{lst:pirSwitch} creates, given an interval in milliseconds, 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.
 552 The system turns on the \gls{LED} again when there is still motion detected after this interval.
 553 By changing the interrupt mode in this program text from \cleaninline{high} to \cleaninline{rising} the system lights the \gls{LED} only one interval when it detects motion, no matter how long this signal is present at the \gls{PIR} pin.
 554
 555 \begin{lstClean}[caption={Example of a toggle light switch using interrupts.},label={lst:pirSwitch}]
 556 pirSwitch :: Int -> Main (MTask v Bool) | mtask v
 557 pirSwitch =
 558         declarePin D13 PMOutput \ledpin->
 559         declarePin D0 PMInput \pirpin->
 560         {main = rpeat (     interrupt high pirpin
 561                        >>|. writeD ledpin false
 562                        >>|. delay (lit interval)
 563                        >>|. writeD ledpin true) }
 564 \end{lstClean}
 565
 566 \subsection{The mTask engine}
 567
 568 While interrupt tasks have their own node type in the task tree, they differ slightly from other node types because they require a more elaborate setup and teardown.
 569 Enabling and disabling interrupts is done in a general way in which tasks register themselves after creation and deregister after deletion.
 570 Interrupts should be disabled when there are no tasks waiting for that kind of interrupt because unused interrupts can lead to unwanted wake-ups, and only one kind of interrupt can be attached to a pin at the time.
 571
 572 \subsubsection{Event registration}
 573 The \gls{MTASK} \gls{RTS} contains an event administration to register which task is waiting on which event.
 574 During the setup of an interrupt task, the event administration in the \gls{MTASK} \gls{RTS} is checked to determine whether a new \gls{ISR} for the particular pin needs to be registered.
 575 Furthermore, this registration allows for a quick lookup in the \gls{ISR} to find the tasks listening to the events.
 576 Conversely, during the teardown, the \gls{ISR} is disabled again when the last interrupt task of that kind is deleted.
 577 The registration is light-weight and consists only of an event identifier and task identifier.
 578 This event registration is stored as a linked list of task tree nodes so that the garbage collector cleans them up when they become unused.
 579
 580 Registering and deregistering interrupts is a device-specific procedure, although most supported devices use the \gls{ARDUINO} \gls{API} for this.
 581 Which pins support which interrupt differs greatly from device to device, but this information is known at compile time.
 582 At the time of registration, the \gls{RTS} checks whether the interrupt is valid and throws an \gls{MTASK} exception if it is not.
 583 Moreover, an exception is thrown if multiple types of interrupts are registered on the same pin.
 584
 585 \subsubsection{Triggering interrupts}
 586 Once an interrupt fires, tasks registered to that interrupt are not immediately evaluated because it is usually not safe.
 587 For example, the interrupt could fire in the middle of a garbage collection process, resulting in corrupt memory.
 588 Furthermore, to ensure the \gls{ISR} to be very short, just a flag in the event administration is set to be processed later.
 589 Interrupt event flags are processed at the beginning of the event loop, before tasks are executed.
 590 For each subscribed task, the task tree is searched for nodes listening for the particular interrupt.
 591 When found, the node is flagged and the pin status is written.
 592 Afterwards, the evaluation interval of the task is set to $\rewriterate{0}{0}$ and the task is reinserted at the front of the scheduling queue to ensure rapid evaluation of the task.
 593 Finally, the event is removed from the registration and the interrupt is disabled.
 594 The interrupt can be disabled as all tasks waiting for the interrupt become stable after firing.
 595 More occurrences of the interrupts do not change the value of the task as stable tasks keep the same value forever.
 596 Therefore, it is no longer necessary to keep the interrupt enabled, and it is relatively cheap to enable it again if needed in the future.
 597 Evaluating an interrupt task node in the task tree is trivial because all the work was already done when the interrupt was triggered.
 598 The task emits the status of the pin as a stable value if the information in the task shows that it was triggered.
 599 Otherwise, no value is emitted.
 600
 601 \section{Conclusion}
 602 This chapter shows how we can automatically associate execution intervals to tasks.
 603 Based on these intervals, we can delay the executions of those tasks.
 604 When all task executions can be delayed, the microprocessor executing those tasks can go to sleep mode to reduce its energy consumption.
 605 This is a rather difficult problem that must be solved dynamically, since we make no assumptions on the number and nature of the tasks that will be allocated to an \gls{IOT} device.
 606 Furthermore, the execution intervals offer an elegant and efficient way to add interrupts to the language.
 607 Those interrupts offer a more elegant and energy efficient implementation of watching an input than polling this input.
 608
 609 The actual reduction of the energy is of course highly dependent on the number and nature of the task shipped to the edge device.
 610 Our examples show a reduction in energy consumption of two orders of magnitude (see \citep*{crooijmans_reducing_2022}).
 611 Those reductions are a necessity for edge devices running on battery power.
 612 Given the exploding number of \gls{IOT} edge devices, such savings are also mandatory for other devices to limit the total power consumption of the \gls{IOT}.
 613
 614 \input{subfilepostamble}
 615 \end{document}