06_aperiodicAndPeriodicScheduling.tex 16 KB
Newer Older
Jonas Künzli's avatar
Jonas Künzli committed
1
% !TeX root = ../main.tex
theova's avatar
theova committed
2
3
\section{Aperiodic and Periodic Scheduling (6)}
\subsection{Real-Time Systems (6-3)}
4
\begin{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
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.
7
\end{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
8

theova's avatar
theova committed
9
\subsection{Schedule (6-4)}
Jonas Künzli's avatar
Jonas Künzli committed
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's avatar
theova committed
25
\subsection{Metrics (6-6) and (6-13)}
Jonas Künzli's avatar
Jonas Künzli committed
26
\textbf{For a task}:
27
\begin{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
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: $
34
\end{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
35
36

\textbf{For a schedule}:
37
\begin{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
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)$
44
\end{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
45

theova's avatar
theova committed
46
\subsection{Classification of Scheduling Algorithms (6-11)}
47
\begin{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
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
55
\end{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
56

theova's avatar
theova committed
57
\section{Scheduling algorithms for aperiodic Tasks (6-17)}
Jonas Künzli's avatar
Jonas Künzli committed
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's avatar
theova committed
69
\subsection{Earliest Deadline Due (Jackson's Rule) (6-18)}
rene.zurbruegg undefined's avatar
rene.zurbruegg undefined committed
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's avatar
Jonas Künzli committed
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's avatar
theova committed
73
\subsection{Latest Deadline First (Lawler's Rule)}
Jonas Künzli's avatar
Jonas Künzli committed
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's avatar
rene.zurbruegg undefined committed
79
	\item non-preemptive
Jonas Künzli's avatar
Jonas Künzli committed
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's avatar
theova committed
88
\subsection{Earliest Deadline First (Horn's Rule) (6-22)}
rene.zurbruegg undefined's avatar
rene.zurbruegg undefined committed
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's avatar
Jonas Künzli committed
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's avatar
Theo von Arx committed
100
  Algorithm: EDF_guarantee (set of jobs $J$, job $j_{new}$)
Jonas Künzli's avatar
Jonas Künzli committed
101
	{
Theo von Arx's avatar
Theo von Arx committed
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's avatar
Jonas Künzli committed
108
109
110
111
112
113
		}
		return(FEASIBLE);
	}
\end{python}
A new task is accepted if the schedule remains feasible. \newline

theova's avatar
theova committed
114
\subsection{EDF* (6-27)}
Jonas Künzli's avatar
Jonas Künzli committed
115
Determines a feasible schedule for tasks with precedence constraints if one exists. \newline
homsm's avatar
homsm committed
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's avatar
Jonas Künzli committed
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's avatar
theova committed
137
\section{Scheduling Algorithms for periodic tasks (6-32)}
Jonas Künzli's avatar
Jonas Künzli committed
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}
148
\begin{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
149
150
    \item $\Gamma$: denotes a set of periodic tasks
    \item $\tau_i$: denotes a periodic task
Jonas Künzli's avatar
Jonas Künzli committed
151
    \item $\tau_{i,j}$ : denotes the $j$th instance of task $i$
Jonas Künzli's avatar
Jonas Künzli committed
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's avatar
Jonas Künzli committed
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$
158
\end{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
159
160
\end{definition}

theova's avatar
theova committed
161
\subsection{Rate Monotonic Scheduling (RM, 6-37)}
Theo von Arx's avatar
Theo von Arx committed
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's avatar
Jonas Künzli committed
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's avatar
Jonas Künzli committed
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's avatar
Jonas Künzli committed
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's avatar
Jonas Künzli committed
175
\vspace{2mm}
Jonas Künzli's avatar
Jonas Künzli committed
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's avatar
theova committed
180
\subsection{Deadline Monotonic Scheduling (6-49)}
Jonas Künzli's avatar
Jonas Künzli committed
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's avatar
theova committed
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's avatar
Jonas Künzli committed
203
204
This condition is both necessary and sufficient.
\begin{python}
theova's avatar
theova committed
205
	Algorithm: DM_guarantee(ordered list $\Gamma$){
Jonas Künzli's avatar
Jonas Künzli committed
206
207
208
209
		for (each $\tau_i \in \Gamma$) {
			I=0;
			do {	$R=I+C_i;$
				if ($R>D_i$) return(UNSCHEDULABLE);
theova's avatar
theova committed
210
				I= $ \sum_{j=1}^{i-1}\lceil R/T_j \rceil \cdot C_j$;
Theo von Arx's avatar
Theo von Arx committed
211
			} while ($I+C_i>R$);
Jonas Künzli's avatar
Jonas Künzli committed
212
213
214
215
216
217
			//while previous operation had any effect
		}
		return(SCHEDULABLE);
	}
\end{python}

theova's avatar
theova committed
218
\subsection{EDF Scheduling (6-56)}
Jonas Künzli's avatar
Jonas Künzli committed
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's avatar
Jonas Künzli committed
231
232


theova's avatar
theova committed
233
\section{Real‐Time Scheduling of Mixed Task Sets (6-63)}
Jonas Künzli's avatar
Jonas Künzli committed
234
For applications with both aperiodic and periodic tasks.
235
\begin{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
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.
239
\end{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
240

theova's avatar
theova committed
241
\subsection{Background Scheduling (6-65)}
Jonas Künzli's avatar
Jonas Künzli committed
242
Schedule periodic tasks with RM or EDF. Process aperiodic task in the background, that is, when there is no periodic task request.
243
\begin{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
244
245
\item Good: Periodic tasks not affected
\item Bad: Aperiodic task may have huge response times and cannot be prioritized.
246
\end{itemize}
Jonas Künzli's avatar
Jonas Künzli committed
247
248
249
250
\begin{center}
	\includegraphics[width=0.8\columnwidth]{sched2}
\end{center}

theova's avatar
theova committed
251
\subsection{RM Polling Server (6-67)}
Jonas Künzli's avatar
Jonas Künzli committed
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's avatar
theova committed
261
\subsection{EDF Total Bandwidth Server (6-71)}
Jonas Künzli's avatar
Jonas Künzli committed
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's avatar
Jonas Künzli committed
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's avatar
Jonas Künzli committed
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's avatar
Jonas Künzli committed
275
276
sufficient).\newline
The worst case finishing time of an aperiodic task is the calculated deadline.
Jonas Künzli's avatar
Jonas Künzli committed
277

theova's avatar
theova committed
278
\subsection{Comparison RM,TT,EDF}
homsm's avatar
homsm committed
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's avatar
theova committed
301
    \item implementation effort minimal
homsm's avatar
homsm committed
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's avatar
theova committed
308
\end{itemize}