Hardware Reference
In-Depth Information
and the schedulability condition is given by:
n
C
i
≤
T
1
.
(4.12)
i
=1
From Equations (4.11), the schedulability condition can also be written as
C
n
≤
2
T
1
−
T
n
(4.13)
Now, defining
R
i
=
T
i
+1
T
i
U
i
=
C
i
T
i
and
.
Equations (4.11) can be written as follows:
⎧
⎨
⎩
U
1
=
R
1
−
1
U
2
=
R
2
−
1
(4.14)
...
U
n−
1
=
R
n−
1
−
1
.
Now we notice that:
n−
1
R
i
=
T
2
T
1
T
3
T
2
···
T
n
T
n−
1
T
n
T
1
=
.
i
=1
If we divide both sides of the feasibility condition (4.13) by
T
n
, we get:
2
T
1
T
n
−
U
n
≤
1
.
Hence, the feasibility condition for a task set that fully utilizes the processor can be
written as
2
n−
1
i
=1
U
n
+1
≤
.
R
i
Since
R
i
=
U
i
+1for all
i
=1
,...,n
−
1,wehave
n−
1
(
U
n
+1)
(
U
i
+1)
≤
2
i
=1
and finally
n
(
U
i
+1)
≤
2
,
i
=1
which proves the theorem.
Search WWH ::
Custom Search