Hardware Reference
In-Depth Information
τ
case (a)
1
t
C
< T
- F T
1
2
1
τ
2
t
F T
T
1
2
τ
case (b)
1
t
>
C
T
- F T
1
2
1
τ
2
t
F T
T
1
2
Figure 4.7
Schedule produced by RM in two different conditions.
Case 2.
The computation time of
τ
1
(synchronously activated with
τ
2
) is long
enough to overlap with the second request of
τ
2
.
That is,
C
1
≥
T
2
−
FT
1
.
In this case, from Figure 4.7b, we can see that the task set is schedulable if
FC
1
+
C
2
≤
FT
1
.
(4.3)
Again, inequality (4.1) implies (4.3). 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
,
which satisfies (4.3).
Basically, it has been shown that, given two periodic tasks
τ
1
and
τ
2
, with
T
1
<T
2
,if
the schedule is feasible by an arbitrary priority assignment, then it is also feasible by
RM. That is, RM is optimal. This result can easily be extended to a set of
n
periodic
tasks. We now show how to compute the least upper bound
U
lub
of the processor
utilization factor for the RM algorithm. The bound is first determined for two tasks
and then extended for an arbitrary number of tasks.
Search WWH ::
Custom Search