Hardware Reference
In-Depth Information
τ
1
t
τ
2
t
Figure 4.6
Tasks scheduled by an algorithm different from RM.
is depicted in Figure 4.6, from which it is easy to see that, at critical instants, the
schedule is feasible if the following inequality is satisfied:
C
1
+
C
2
≤
T
1
.
(4.1)
On the other hand, if priorities are assigned according to RM, task
T
1
will receive
the highest priority. In this situation, illustrated in Figure 4.7, in order to guarantee a
feasible schedule two cases must be considered. Let
F
=
be the number
1
of
T
2
/T
1
periods of
τ
1
entirely contained in
T
2
.
Case 1.
The computation time of
τ
1
(synchronously activated with
τ
2
) is short
enough that all its requests are completed before the second request of
τ
2
. That is,
C
1
<T
2
−
FT
1
.
In this case, from Figure 4.7a, we can see that the task set is schedulable if
(
F
+1)
C
1
+
C
2
≤
T
2
.
(4.2)
We now show that inequality (4.1) implies (4.2). In fact, by multiplying both sides of
(4.1) by
F
we obtain
FC
1
+
FC
2
≤
FT
1
,
and, since
F
≥
1, we can write
FC
1
+
C
2
≤
FC
1
+
FC
2
≤
FT
1
.
Adding
C
1
to each member we get
(
F
+1)
C
1
+
C
2
≤
FT
1
+
C
1
.
Since we assumed that
C
1
<T
2
−
FT
1
,wehave
(
F
+1)
C
1
+
C
2
≤
FT
1
+
C
1
<T
2
,
which satisfies (4.2).
1
x
denotes the largest integer smaller than or equal to
x
, whereas
x
denotes the smallest integer
greater than or equal to
x
.
Search WWH ::
Custom Search