top/green.tex

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