06_aperiodicAndPeriodicScheduling.tex 16 KB
 Jonas Künzli committed Jun 28, 2019 1 % !TeX root = ../main.tex  theova committed Jul 29, 2019 2 3 \section{Aperiodic and Periodic Scheduling (6)} \subsection{Real-Time Systems (6-3)}  Theo von Arx committed Jul 29, 2019 4 \begin{itemize}  Jonas Künzli committed Jun 28, 2019 5 6 \item A real-time task is said to be \textcolor{red}{hard}, if missing its deadline may cause catastrophic consequences on the environment under control. \item A real-time task is called \textcolor{red}{soft}, if meeting its deadline is desirable for performance reasons, but missing its deadline is not catastrophic.  Theo von Arx committed Jul 29, 2019 7 \end{itemize}  Jonas Künzli committed Jun 28, 2019 8   theova committed Jul 29, 2019 9 \subsection{Schedule (6-4)}  Jonas Künzli committed Jun 28, 2019 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 A \textcolor{red}{schedule} is an assignment of tasks $J=\{J_1,J_2,...\}$ to the processor, such that each task is executed until completion. It can be defined as a function $$\sigma: \mathbb{R} \rightarrow \mathbb{N}, t \mapsto \sigma(t)$$ where $\sigma(t)$ denotes the task which is executed at time $t$. If $\sigma(t)=0$, the processor is called \textcolor{red}{idle}.\newline If $\sigma$ changes its value, the processor performs a \textcolor{red}{context switch}. Each interval in which $\sigma$ is constant is called a \textcolor{red}{time slice}. \\ A \textcolor{red}{preemptive schedule} is a schedule in which the running task can be suspended at any time. \\ A schedule is said to be \textcolor{red}{feasible}, if all tasks can be completed according to a set of specified constraints. \\ A set of tasks is \textcolor{red}{schedulable} if there exists an algorithm that can produce a feasible schedule. \\ \textcolor{red}{Arrival time} $a_i$ or \textcolor{red}{release time} $r_i$ is the time at which a task becomes ready for execution. \\ \textcolor{red}{Computation} time $C_i$ is the time necessary to the processor for executing the task without interruption. \\ \textcolor{red}{Deadline} $d_i$ is the time at which a task should be completed. \\ \textcolor{red}{Start time} $s_i$ is the time at which a task starts its execution. \\ \textcolor{red}{Finishing time} $f_i$ is the time at which a task finishes its execution.  theova committed Jul 29, 2019 25 \subsection{Metrics (6-6) and (6-13)}  Jonas Künzli committed Jun 28, 2019 26 \textbf{For a task}:  Theo von Arx committed Jul 29, 2019 27 \begin{itemize}  Jonas Künzli committed Jun 28, 2019 28 29 30 31 32 33 \item \textbf{Response time}: $R_i = f_i - r_i$ \item \textbf{Interference}: $I_i = s_i - r_i$ \item \textbf{Lateness} (positive if too late) $L_i = f_i-d_i:$ \item \textbf{Tardiness}/Exceeding Time $E_i=\max\{0,L_i\}:$ \item \textbf{Laxity/Slack time} (maximum time a task can be delayed)\\ $X_i=d_i-a_i-C_i:$  Theo von Arx committed Jul 29, 2019 34 \end{itemize}  Jonas Künzli committed Jun 28, 2019 35 36  \textbf{For a schedule}:  Theo von Arx committed Jul 29, 2019 37 \begin{itemize}  Jonas Künzli committed Jun 28, 2019 38 39 40 41 42 43 \item Avg. response time: $\overline{t_R} = \frac{1}{n}\sum_{i=1}^{n}(f_i-r_i)$ \item Total completion time: $t_c = \max_{i}\{f_i\} - \min_{i}\{r_i\}$ \item Weighted sum of response time:\\ $t_w = \Big(\sum_{i=1}^{n}w_i(f_i-r_i)\Big)\cdot\Big(\sum_{i=1}^{n}w_i\Big)^{-1}$ \item Maximum Lateness: $L_{max} = \max_{i}\{f_i-d_i\}$ \item Number of late tasks: $N_{late} = \sum_{i=1}^{n}miss(f_i)$  Theo von Arx committed Jul 29, 2019 44 \end{itemize}  Jonas Künzli committed Jun 28, 2019 45   theova committed Jul 29, 2019 46 \subsection{Classification of Scheduling Algorithms (6-11)}  Theo von Arx committed Jul 29, 2019 47 \begin{itemize}  Jonas Künzli committed Jun 28, 2019 48 49 50 51 52 53 54 \item \textcolor{red}{Preemptive Algorithms:} The running task can be interrupted at any time to assign the processor another active task \item \textcolor{red}{Non-preemptive Algorithms:} A task, once started, is executed by the processor until completion \item \textcolor{red}{Static Algorithms:} Scheduling decisions are based on fixed parameters, assigned to tasks before their activation (constant priorities) \item \textcolor{red}{Dynamic Algorithms:} Scheduling decisions based on dynamic parameters that may vary during system execution \item An algorithm is called \textcolor{red}{optimal}, if it minimizes some given cost function defined over the task set \item An algorithm is called \textcolor{red}{heuristic}, if it tends to but does not guarantee to find an optimal schedule \item \textcolor{red}{Acceptance test}: Check for every task if when it is accepted, the schedule will still be feasible  Theo von Arx committed Jul 29, 2019 55 \end{itemize}  Jonas Künzli committed Jun 28, 2019 56   theova committed Jul 29, 2019 57 \section{Scheduling algorithms for aperiodic Tasks (6-17)}  Jonas Künzli committed Jun 28, 2019 58 59 60 61 62 63 64 65 66 67 68  \begin{tabularx}{\columnwidth}{|p{1.7cm} | p{2.7cm} | X|} \hline \textbf{Aperiodic \newline Tasks} & Equal arrival times \newline non-preemptive & Arbitrary arrival times \newline preemptive \\ \hline Independent \newline tasks \vspace{0.2cm} & EDD \newline (Jackson's Rule) & EDF \newline (Horn's Rule) \\ Dependent \newline tasks & (LDF) \newline (Lawler's Rule) & EDF* \newline (Chetto's Rule) \\ \hline \end{tabularx} ~\newline  theova committed Jul 29, 2019 69 \subsection{Earliest Deadline Due (Jackson's Rule) (6-18)}  rene.zurbruegg undefined committed Jul 02, 2019 70 \textbf{Algorithm: }Task with earliest deadline is processed first. (Arrival times are equal for all tasks,tasks are independent, Scheduling is non-preemptive.)\newline  Jonas Künzli committed Jun 28, 2019 71 72 \textbf{Jackson's Rule: }Given a set of $n$ independent tasks. Processing in order of non-decreasing deadlines is optimal with respect to minimizing the maximum lateness. \newline  theova committed Jul 29, 2019 73 \subsection{Latest Deadline First (Lawler's Rule)}  Jonas Künzli committed Jun 28, 2019 74 75 76 77 78 \textbf{Optimization goal:} Minimize the maximum lateness\\ \textbf{Assumptions on the task set:} \begin{itemize} \item tasks with precedence relations \item synchronous arrival times  rene.zurbruegg undefined committed Jul 02, 2019 79  \item non-preemptive  Jonas Künzli committed Jun 28, 2019 80 81 82 83 84 85 86 87 \end{itemize} \textbf{Algorithm:} \begin{itemize} \item proceed from tail to head \item among the tasks without successors or whose successors have been all scheduled, select the task with the latest deadline to be scheduled last \item repeat the procedure until all tasks in the set are selected \end{itemize}  theova committed Jul 29, 2019 88 \subsection{Earliest Deadline First (Horn's Rule) (6-22)}  rene.zurbruegg undefined committed Jul 02, 2019 89 90 91 92 93 94 \textbf{Algorithm:} Task with earliest deadline is processed first. If new task with earlier deadline arrives, current task is preempted. \vspace{2mm} \textbf{Optimization goal:} It is is optimal in sense of feasibility (it minimizes the maximum lateness under following assumptions: scheduling algorithm is preemptive, the tasks are independent and may have different arrival times)\vspace{2mm} \textbf{Horn's Rule: }Given a set of $n$ independent tasks with arbitrary arrival times. An algorithm that at any instant executes the task with the earliest absolute deadline among the ready tasks is optimal with respect to minimizing the maximum lateness. \newline  Jonas Künzli committed Jun 28, 2019 95 96 97 98 99  \textbf{Acceptance test:} \\ worst case finishing time of task i: $f_i = t + \sum_{k=1}^i c_k(t)$ \\ EDF guarantee condition: $\forall i = 1,\dots ,n \quad t + \sum_{k=1}^i c_k(t)\leq d_i$ \begin{python}  Theo von Arx committed Jul 29, 2019 100  Algorithm: EDF_guarantee (set of jobs $J$, job $j_{new}$)  Jonas Künzli committed Jun 28, 2019 101  {  Theo von Arx committed Jul 29, 2019 102 103 104 105 106 107  $J'$ = $J \cup \{j_{new}\}$; /*ordered by deadline*/ $t$ = current_time(); $f_0$ = $t$; for (each $j_i$ in $J'$) { $f_i = f_{i-1} + c_i(t)$; if ($f_i >d_i$) return(UNFEASIBLE);  Jonas Künzli committed Jun 28, 2019 108 109 110 111 112 113  } return(FEASIBLE); } \end{python} A new task is accepted if the schedule remains feasible. \newline  theova committed Jul 29, 2019 114 \subsection{EDF* (6-27)}  Jonas Künzli committed Jun 28, 2019 115 Determines a feasible schedule for tasks with precedence constraints if one exists. \newline  homsm committed Jul 02, 2019 116 \textbf{Algorithm: }Modify release times and deadlines (in that way we get a problem without precedence constraints and can use the normal EDF algorithm. Precedence constraints are still satisfied). Then use EDF. \newline  Jonas Künzli committed Jun 28, 2019 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 \textbf{Modification of release times:}\newline Task must start not earlier than its release time and not earlier than the minimum finishing time of its predecessor. \begin{compactenum} \item Start at initial nodes = sources of precedence graph and set $r^*_i=r_i$ \item Select a task $j$ with all its predecessors having already been modified. \item Set $r^*_j = \max\{r_j,\max_{i}\{r^*_i+C_i: J_i \rightarrow J_j\}\}$ \item Return to 2 \end{compactenum} \textbf{Modification of deadlines:} \newline Task must finish execution within its deadline and not later than the maximum start time of its successor. \begin{compactenum} \item Start at terminal nodes = sinks of precedence graph and set $d^*_i=d_i$ \item Select a task $i$ with all successors having already been modified. \item Set $d^*_i = \min\{d_i, \min_{j}\{d^*_j-C_j: J_i \rightarrow J_j\}\}$ \item Return to 2 \end{compactenum} \textcolor{red}{\textbf{$\to$ For response time etc. calculations use the original release times and deadlines}}  theova committed Jul 29, 2019 137 \section{Scheduling Algorithms for periodic tasks (6-32)}  Jonas Künzli committed Jun 28, 2019 138 139 140 141 142 143 144 145 146 147 \begin{tabularx}{\columnwidth}{|p{1.7cm} | p{2.7cm} | X|} \hline \textbf{Periodic \newline Tasks} & Deadline $=$ Period & Deadline $<$ Period \\ \hline Static \newline priority \vspace{0.2cm} & RM \newline (rate-monotonic) & DM \newline (deadline-monotonic) \\ Dynamic \newline priority & EDF & (EDF*) \\ \hline \end{tabularx} \\ \begin{definition}{Model of Periodic Tasks}  Theo von Arx committed Jul 29, 2019 148 \begin{itemize}  Jonas Künzli committed Jun 28, 2019 149 150  \item $\Gamma$: denotes a set of periodic tasks \item $\tau_i$: denotes a periodic task  Jonas Künzli committed Jun 28, 2019 151  \item $\tau_{i,j}$ : denotes the $j$th instance of task $i$  Jonas Künzli committed Jul 26, 2019 152 153 154  \item $r_{i,j}, s_{i,j}, f_{i,j}, d_{i,j}$: denote the release time, start time, finishing time, absolute deadline of the $j$th instance of task $i$\\ $r_{i,j}=\phi_i+(j-1)T_i$\\ $d_ij=\phi_i+(j-1)T_i+D_i$\\  Jonas Künzli committed Jun 28, 2019 155 156 157  \item $\Phi_i$: denotes the phase of task $i$ (release time of its first instance) \item $D_i$: denotes the relative deadline of task $i$ \item $T_i$: denotes the period of task $i$  Theo von Arx committed Jul 29, 2019 158 \end{itemize}  Jonas Künzli committed Jun 28, 2019 159 160 \end{definition}  theova committed Jul 29, 2019 161 \subsection{Rate Monotonic Scheduling (RM, 6-37)}  Theo von Arx committed Jul 01, 2019 162 163 RM is optimal, meaning that if any static-priority scheduling algorithm can meet all the deadlines, then the rate-monotonic algorithm can too.  Jonas Künzli committed Jun 28, 2019 164 165 166 167 168 169 Fixed / static priorities, independent, preemptive, deadlines equal the periods, $D_i=T_i$. Tasks can't suspend themselves, kernel overhead is assumed 0. \textbf{Algorithm:} Tasks with the higher request rates (=shorter periods) have higher priorities and interrupt tasks with lower priority. RM is optimal w.r.t. schedulability. \textbf{Schedulability Condition: } (sufficient but not necessary) $$U=\sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(2^{1/n}-1) \implies \text{schedulability}$$  Jonas Künzli committed Jul 26, 2019 170 where $U$ is the \textcolor{red}{processor utilization factor}= fraction of processor time spent in execution of tasks. $\lim\limits_{n \to \infty} n(2^{1/n}-1) \approx 0.7$  Jonas Künzli committed Jun 28, 2019 171 172 173 174  \includegraphics[width=0.5\linewidth]{RM_sufficiency} As a sufficient and necessary test, you can simulate it or do algorithm of DM section.  Jonas Künzli committed Jul 26, 2019 175 \vspace{2mm}  Jonas Künzli committed Jun 28, 2019 176 177 178 179  \textbf{Critical Instant}: The time at which the release of the task will produce the largest response time. It is if that task is simultaneously released with all higher priority tasks. $\implies$ If there are no phase shifts, simulate the beginning (till all deadlines have passed). If that works, the schedule is feasible.  theova committed Jul 29, 2019 180 \subsection{Deadline Monotonic Scheduling (6-49)}  Jonas Künzli committed Jun 28, 2019 181 182 183 184 185 186 187 Fixed / static priorities, independent, preemptive, deadlines can be smaller than periods, $C_i\leq D_i\leq T_i$. \textbf{Algorithm}: Tasks with smaller relative deadlines have higher priorities and interrupt tasks with lower priority. \textbf{Schedulability analysis}: (sufficient but not necessary) $$\sum_{i=1}^{n} \frac{C_i}{D_i} \leq n(2^{1/n}-1) \implies \text{schedulability}$$  theova committed Jul 16, 2019 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 \textbf{Schedulatbility Condition: (sufficient and necessary)}:\\ The worst-case is the critical instance (critical instance of a task occurs whenever the task is released simultaneously with all higher priority tasks). Assume that tasks are ordered according to relative deadlines $D_i$ such that \begin{align} m < n \quad &\Leftrightarrow \quad D_m < D_n,\\ \intertext{then the \textcolor{red}{worst case interference} for task $i$ is} I_i &= \sum_{j=1}^{i-1} \Big\lceil\frac{t}{T_j}\Big\rceil C_j\\ I_1&=0 \end{align} The \textcolor{red}{longest response time} $R_i$ of a periodic task $i$ is at critical instance, $R_i=C_i+I_i$. Hence, compute in ascending order (=highest priority first) the smallest $R_i, ~i=1,...,n$ that satisfy $$R_i=C_i+\sum_{j=1}^{i-1}\Big\lceil\frac{R_i}{T_j}\Big\rceil C_j$$ and check whether $$\forall i=1,...,n: \qquad R_i\leq D_i.$$  Jonas Künzli committed Jun 28, 2019 203 204 This condition is both necessary and sufficient. \begin{python}  theova committed Jul 16, 2019 205  Algorithm: DM_guarantee(ordered list $\Gamma$){  Jonas Künzli committed Jun 28, 2019 206 207 208 209  for (each $\tau_i \in \Gamma$) { I=0; do { $R=I+C_i;$ if ($R>D_i$) return(UNSCHEDULABLE);  theova committed Jul 16, 2019 210  I= $\sum_{j=1}^{i-1}\lceil R/T_j \rceil \cdot C_j$;  Theo von Arx committed Jul 01, 2019 211  } while ($I+C_i>R$);  Jonas Künzli committed Jun 28, 2019 212 213 214 215 216 217  //while previous operation had any effect } return(SCHEDULABLE); } \end{python}  theova committed Jul 29, 2019 218 \subsection{EDF Scheduling (6-56)}  Jonas Künzli committed Jun 28, 2019 219 220 221 222 223 224 225 226 227 228 229 230 Dynamic priority assignment, intrinsically preemptive, deadlines can be smaller than periods: $D_i \leq T_i$ \textbf{Algorithm:} The currently executing task is preempted whenever another periodic instance with earlier deadline becomes active EDF is optimal w.r.t. schedulability (no set of periodic tasks can be scheduled if it can't be scheduled by EDF). \textbf{Schedulability condition}: \begin{itemize} \item if $T_i=D_i$: $$U=\sum_{i=1}^{n}\frac{C_i}{T_i}\leq1$$ is both necessary and sufficient. \item if $T_i\neq D_i$: $$U=\sum_{i=1}^{n}\frac{C_i}{D_i}\leq1$$ is only sufficient. \end{itemize}  Jonas Künzli committed Jun 28, 2019 231 232   theova committed Jul 29, 2019 233 \section{Real‐Time Scheduling of Mixed Task Sets (6-63)}  Jonas Künzli committed Jun 28, 2019 234 For applications with both aperiodic and periodic tasks.  Theo von Arx committed Jul 29, 2019 235 \begin{itemize}  Jonas Künzli committed Jun 28, 2019 236 237 238 \item \textcolor{red}{Periodic Tasks:} time-driven, hard timing constraints \item \textcolor{red}{Aperiodic Tasks:} event-driven, may have hard, soft or no real-time requirements \item \textcolor{red}{Sporadic Tasks:} Aperiodic task with a maximum arrival rate (or minimum time between two arrivals) assumed.  Theo von Arx committed Jul 29, 2019 239 \end{itemize}  Jonas Künzli committed Jun 28, 2019 240   theova committed Jul 29, 2019 241 \subsection{Background Scheduling (6-65)}  Jonas Künzli committed Jun 28, 2019 242 Schedule periodic tasks with RM or EDF. Process aperiodic task in the background, that is, when there is no periodic task request.  Theo von Arx committed Jul 29, 2019 243 \begin{itemize}  Jonas Künzli committed Jun 28, 2019 244 245 \item Good: Periodic tasks not affected \item Bad: Aperiodic task may have huge response times and cannot be prioritized.  Theo von Arx committed Jul 29, 2019 246 \end{itemize}  Jonas Künzli committed Jun 28, 2019 247 248 249 250 \begin{center} \includegraphics[width=0.8\columnwidth]{sched2} \end{center}  theova committed Jul 29, 2019 251 \subsection{RM Polling Server (6-67)}  Jonas Künzli committed Jun 28, 2019 252 253 254 255 256 257 258 259 260 Introduce an artificial periodic task (\textcolor{red}{server}) to service aperiodic requests. The server is characterized by a period $T_s$ and a computation time $C_s$ and scheduled with the same algorithm used for periodic tasks. \\ Schedulability condition is the same as for normal RM. \\ Disadvantage: If an aperiodic requests arrives just after the server has suspended, it must wait until the beginning of the next polling period. \\ \textbf{Schedulability analysis - sufficient but not necessary} $$\frac{C_s}{T_s}+\sum_{i=1}^n\frac{C_i}{T_i}\leq \left(n+1\right)\left(2^{1/(n+1)}-1\right)$$ \textbf{Aperiodic Guarantee: } Assumption: An aperiodic task is finished before a new one arrives. Computation time $C_a$, deadline $D_a$: $$(1+\Big\lceil\frac{C_a}{C_s}\Big\rceil)T_s\leq D_a$$  theova committed Jul 29, 2019 261 \subsection{EDF Total Bandwidth Server (6-71)}  Jonas Künzli committed Jun 28, 2019 262 263 264 265 266 267 268 269 270 \textbf{Schedulability test}: Given a set of $n$ periodic tasks with processor utilization $U_p$ and a total bandwidth server with utilization $U_s$, the whole set is schedulable by EDF if and only if $$U_p+U_s\leq 1$$ \begin{align} \shortintertext{Utilization of periodic tasks:} U_p &= \sum_i \frac{C_i}{T_i}\\ \shortintertext{Utilization of aperiodic tasks:} U_s &= \frac{C_s}{T_s} \end{align}  Jonas Künzli committed Jul 15, 2019 271 272 When the $k$-th aperiodic request arrives at time $t=r_k$ , it receives a deadline (Tasks nach arrival times ordnen und deadlines berechnen) $$d_k=\max\{r_k,d_{k-1}\}+\frac{C_k}{U_s}$$ where $C_k$ is the  Jonas Künzli committed Jun 28, 2019 273 274 execution time of the request and $U_s$ the server utilization factor (=bandwidth). $U_S$ can be chosen such that $U_s\leq 1-U_p$ (necessary and  Jonas Künzli committed Jul 15, 2019 275 276 sufficient).\newline The worst case finishing time of an aperiodic task is the calculated deadline.  Jonas Künzli committed Jun 28, 2019 277   theova committed Jul 29, 2019 278 \subsection{Comparison RM,TT,EDF}  homsm committed Jul 16, 2019 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 \textbf{Time Triggered Cyclic Executive:} \begin{itemize} \item No RTOs necessary \item Preemption $\rightarrow$ No context switch overhead \item few scheduling overhead \item slow, cheap processor can be used \item implementation difficult for many tasks \item inflexible (new tasks can't be added easily) \end{itemize} \textbf{Rate Monotonic:} \begin{itemize} \item implementation not complex \item few scheduling overhead \item needs RTOS \item context switch overhead \item needs faster and more expensive processor than TT \item flexible (few changes (in priority list) needed if a new task is added) \end{itemize} \textbf{Earliest Deadline First:} \begin{itemize}  theova committed Jul 16, 2019 301  \item implementation effort minimal  homsm committed Jul 16, 2019 302 303 304 305 306 307  \item a lot scheduling overhead \item needs RTOS \item context switch overhead \item needs faster and more expensive processor than TT and RM \item very flexible (no changes are needed if a new task is added) \item new task set can have utilization $U_new=1-U_old$ in that way processor is completely busy (ausgelastet)  theova committed Jul 16, 2019 308 \end{itemize}