1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<!--Converted with LaTeX2HTML 2K.1beta (1.48)
original version by: Nikos Drakos, CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>Schedulability Analysis</TITLE>
<META NAME="description" CONTENT="Schedulability Analysis">
<META NAME="keywords" CONTENT="rtic">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="LaTeX2HTML v2K.1beta">
<META HTTP-EQUIV="Content-Style-Type" CONTENT="text/css">
<LINK REL="STYLESHEET" HREF="rtic.css">
<LINK REL="next" HREF="node6.html">
<LINK REL="previous" HREF="node4.html">
<LINK REL="up" HREF="node3.html">
<LINK REL="next" HREF="node6.html">
</HEAD>
<BODY bgcolor="white">
<!--Navigation Panel-->
<A NAME="tex2html173"
HREF="node6.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html171"
HREF="node3.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html165"
HREF="node4.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html174"
HREF="node6.html">Remarks</A>
<B> Up:</B> <A NAME="tex2html172"
HREF="node3.html">Real Time Systems</A>
<B> Previous:</B> <A NAME="tex2html166"
HREF="node4.html">Scheduling Theory</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H2><A NAME="SECTION00122000000000000000">
Schedulability Analysis</A>
</H2>
<P>
Real time scheduling of periodic tasks (such as AMB controllers) often
uses the rate-monotonic algorithm [<A
HREF="node64.html#liu_and_layland">LL73</A>]. This
algorithm has been shown to be optimal in the literature for
uniprocessor systems and periodic tasks. The most important feature
about this algorithm is that it introduces the ability to find, <I>a
priori</I>, whether or not a given set of tasks will be schedulable -
that is, whether or not they will meet all their deadlines.
<P>
Liu and Layland showed that for <IMG
WIDTH="18" HEIGHT="20" ALIGN="BOTTOM" BORDER="0"
SRC="img17.png"
ALT="$n$"> independent tasks - all of which
have the same start time at some point in time, whose execution time is
smaller than their deadline, and which, most importantly, are completely
independent one of the other - all tasks are schedulable if the
following is true:
<P>
<BR>
<DIV ALIGN="RIGHT">
<!-- MATH
\begin{equation}
\sum_{i=1}^{n} \frac{C_i}{P_i} \leq n(2^{1/n} -1 )
\end{equation}
-->
<TABLE WIDTH="100%" ALIGN="CENTER">
<TR VALIGN="MIDDLE"><TD ALIGN="CENTER" NOWRAP><A NAME="RMA_test"></A><IMG
WIDTH="362" HEIGHT="55" BORDER="0"
SRC="img20.png"
ALT="\begin{displaymath}
\sum_{i=1}^{n} \frac{C_i}{P_i} \leq n(2^{1/n} -1 )
\end{displaymath}"></TD>
<TD WIDTH=10 ALIGN="RIGHT">
(1.1)</TD></TR>
</TABLE>
<BR CLEAR="ALL"></DIV><P></P>
<P>
where <IMG
WIDTH="26" HEIGHT="37" ALIGN="MIDDLE" BORDER="0"
SRC="img21.png"
ALT="$C_i$"> is the worst case execution time of the task,
<IMG
WIDTH="24" HEIGHT="37" ALIGN="MIDDLE" BORDER="0"
SRC="img22.png"
ALT="$P_i$"> is the period of the task, and the left hand side of
(<A HREF="node5.html#RMA_test">1.1</A>) is called the total CPU utilization. Of most use is
the fact that:
<P>
<BR>
<DIV ALIGN="RIGHT">
<!-- MATH
\begin{equation}
\lim_{n \rightarrow \infty } \sum_{i=1}^{n} \frac{C_i}{P_i} \leq 69.34\%
\end{equation}
-->
<TABLE WIDTH="100%" ALIGN="CENTER">
<TR VALIGN="MIDDLE"><TD ALIGN="CENTER" NOWRAP><IMG
WIDTH="367" HEIGHT="55" BORDER="0"
SRC="img23.png"
ALT="\begin{displaymath}
\lim_{n \rightarrow \infty } \sum_{i=1}^{n} \frac{C_i}{P_i} \leq 69.34\%
\end{displaymath}"></TD>
<TD WIDTH=10 ALIGN="RIGHT">
(1.2)</TD></TR>
</TABLE>
<BR CLEAR="ALL"></DIV><P></P>
<P>
or equivalently, if CPU utilization is less than 69.3%, all
tasks will meet their deadlines. This relation describes a worst case
sufficient condition for a rate-monotonic algorithm and is thus
pessimistic. An exact characterization was obtained by Lehoczky, Sha,
and Ding [<A
HREF="node64.html#lehoczky_sha_ding">LSD89</A>] but is not quoted here due to its
somewhat more complex nature.
<P>
Equation <A HREF="node5.html#RMA_test">1.1</A> provides conditions under which a set of
periodic tasks can be scheduled taking into account the effect of a
task being preempted exclusively by higher priority tasks. However,
(<A HREF="node5.html#RMA_test">1.1</A>) can be extended to include blocking of higher
priority tasks by lower priority tasks
[<A
HREF="node64.html#sha_rajkumar_lehoczky">SRL90</A>]. That is, assuming that the priority
ceiling protocol is used to eliminate priority inversion, then
(<A HREF="node5.html#RMA_test">1.1</A>) can be extended as:
<P>
<BR>
<DIV ALIGN="RIGHT">
<!-- MATH
\begin{equation}
\sum_{i=1}^{n} \frac{C_i}{P_i} + max\left
( \frac{B_1}{P_1},\ldots,\frac{B_{(n-1)}}{P_{(n-1)}},\right)
\leq n(2^{1/n} -1 )
\end{equation}
-->
<TABLE WIDTH="100%" ALIGN="CENTER">
<TR VALIGN="MIDDLE"><TD ALIGN="CENTER" NOWRAP><IMG
WIDTH="472" HEIGHT="56" BORDER="0"
SRC="img24.png"
ALT="\begin{displaymath}
\sum_{i=1}^{n} \frac{C_i}{P_i} + max\left
( \frac{B_1}{P_1},\ldots,\frac{B_{(n-1)}}{P_{(n-1)}},\right)
\leq n(2^{1/n} -1 )
\end{displaymath}"></TD>
<TD WIDTH=10 ALIGN="RIGHT">
(1.3)</TD></TR>
</TABLE>
<BR CLEAR="ALL"></DIV><P></P>
<P>
where <IMG
WIDTH="28" HEIGHT="37" ALIGN="MIDDLE" BORDER="0"
SRC="img25.png"
ALT="$B_j$"> denotes the worst case blocking time that may
occur from any of the lower priority tasks (where increasing <IMG
WIDTH="16" HEIGHT="36" ALIGN="MIDDLE" BORDER="0"
SRC="img26.png"
ALT="$j$"> denotes
tasks with decreasing priority).
<P>
The most important point to note about these scheduling tests is that we
now have an effective method of selecting a CPU for a given application
(or determining that no CPU will handle the given controller at the
given sampling rate). That is, if we know the target execution periods
(for example, a controller may repeat itself every 100 <IMG
WIDTH="27" HEIGHT="36" ALIGN="MIDDLE" BORDER="0"
SRC="img13.png"
ALT="$\mu s$">) and the
worst case execution time for each of our control tasks (for example,
the execution time of the aforementioned controller may be 80 <IMG
WIDTH="27" HEIGHT="36" ALIGN="MIDDLE" BORDER="0"
SRC="img13.png"
ALT="$\mu s$">),
then by use of the aforementioned schedulability tests, we can
scientifically select a computer that is appropriate for our
application. Stated differently, if the left hand side of these tests is
much smaller than the right hand side, then we know that the target CPU
is much too fast for our application and thus we can select a lower cost
system. Alternatively, if the left hand side is too large compared with
the right, then we should either consider upgrading to a faster CPU or
redesigning the controller given that our given CPU cannot compute this
controller at the given rate). From our example and (<A HREF="node5.html#RMA_test">1.1</A>), we
find that <!-- MATH
$80/100 = 0.8 \leq 1.0$
-->
<IMG
WIDTH="161" HEIGHT="40" ALIGN="MIDDLE" BORDER="0"
SRC="img27.png"
ALT="$80/100 = 0.8 \leq 1.0$">, therefore our individual task is
schedulable in this CPU and will meet all of its deadlines.
<P>
Real Time Systems literature is too vast to be summarized in this
paper. Interested readers are encouraged to pursue further reading in
many of the excellent books and papers on the subject.
<P>
<HR>
<!--Navigation Panel-->
<A NAME="tex2html173"
HREF="node6.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html171"
HREF="node3.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html165"
HREF="node4.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html174"
HREF="node6.html">Remarks</A>
<B> Up:</B> <A NAME="tex2html172"
HREF="node3.html">Real Time Systems</A>
<B> Previous:</B> <A NAME="tex2html166"
HREF="node4.html">Scheduling Theory</A>
<!--End of Navigation Panel-->
<ADDRESS>
Michael Barabanov
2001-06-19
</ADDRESS>
</BODY>
</HTML>
|
