Slack and Lateness

Di

i
ai si fi di t

Ri slacki = di - fi

Di lateness Li = fi - di

i
ai si di fi t

Ri

Task model Tasks and jobs

 Sequence of instructions that in the absence of
other activities is continuously executed by the A task running several times on different input
processor until completion. data generates a sequence of instances (jobs):

activation time Task i

Ci
start time Job 1 Job 2 Job 3
ai si fi t i,1 i,2 i,3
computation Response time Ri Ci
time i
ai,1 ai,k ai,k+1 t
finishing time

Real-Time Task Activation modes

 It is a task characterized by a timing constraint on
its response time, called deadline:  Time driven
The task is automatically activated by the
relative deadline Di operating system at predefined time instants.
i
ai si fi di
t  Event driven
absolute deadline The task is activated at an event arrival or by
response time Ri (di = ai + Di) explicitly invocating a system call.
A real-time task i is said to be feasible if it
completes within its absolute deadline, that is,
if fi  di, o equivalently, if Ri  Di

1
 Types of tasks Assumptions
 Aperiodic  Implicit deadlines
Activated by events. Task activation times are
unknown and unbounded. i Di = Ti

 Sporadic  Constrained deadlines

Activated by events.
events Task activation times are
unknown and bounded: consecutive activations are i Di ≤ Ti
separated by a minimum interarrival time.

 Periodic  Arbitrary deadlines

Activated by a timer. Task activation times are Deadlines can be less than,
known and bounded: Consecutive jobs are greater than, or equal to periods
separated by a constant interval (period).

Aperiodic/Sporadic task Analysis under fixed priority

interrupt
Let  = {1, …, n} be a set of n periodic tasks.
Ci computation time
Implicit deadlines
job ik

 
Ci Ci Ci n
… Utilization-based test
i [Liu & Layland, 1973] U i  n 21/ n  1 only
sufficient
ai,1 ai,k ai,k+1 t i 1

 Aperiodic: (Ci, Di) ai,k+1 > ai,k

n

 U  1  2
Hyperbolic Bound only
 Sporadic: (Ci, Di, Ti) ai,k+1  ai,k + Ti [Bini - Buttazzo2, 2001]
i 1
i sufficient

minimum
interarrival time
11

Periodic task Analysis under fixed priority

input Constrained deadlines
computation time
C
Ci Ui = i
Ti Response Time Analysis necessary
output
timer (period Ti ) [Audsley et al., 1993] i Ri  Di and
sync utilization factor sufficient

Ti jjob ik
Iterative solution:
Ci
i i

ai,1 = i ai,k ai,k+1 t Ri( 0 )  C

k 1
k
iterate while
task phase i 1
Ri( s 1)
ai,k = i + (k1) Ti R i
(s)
 Ci   Ck Ri( s )  Ri( s 1)
i (i , Ci, Ti, Di ) k 1 Tk
di,k = ai,k + Di
12

2
 Analysis under EDF Workload Analysis under FP
Constrained deadlines Arbitrary deadlines
necessary necessary
Processor Demand  t D dbf (t)  t Workload Analysis
[Baruah et al., 1990]
and
sufficient
i  t  Ai Wi (t)  t and
[Lehoczky et al., 1989] sufficient

 dbf(t) is called demand bound function and denotes the  Wi (t) is called workload in (0, t] at priority level Pi and
computation time of tasks with deadlines ≤ t denotes the computation time requested in (0, (0 t] by tasks
n
t + Ti  Di with priority higher than or equal to Pi
dbf (t) =
Ti Σ
Ck i–1
t
i=1
Wi (t) = Ci + Σ C
Tk k
 D is the set of points where the test has to be performed k=1

D = {dk | dk  Lb} Lb = max{Dmax, min(H, L*)}  Ai is the set of points where the test has to be performed,
equal to the activation times ≤ Di, including Di

n
(Ti  Di )U i
H = lcm(T1, … , Tn) L*  i 1
1U 13 16

EDF example Workload Analysis under FP

task Ci Ti Di Ti - Di Ui 1 1 1 25 1 1
A task i is feasible iff:
U    
1 1 4 2 2 1/4 4 2 7 28
2  t ≤ Di : Wi(t) ≤ t
5

2 3 6 5 1 1/2
3 2 14 9 5 1/7 H = 437 = 84
W2(t)
18

2 1 5 16
 

n
(T  Di )U i 12 28 14
L 
* i 1 i
 4 2 7    16 12
1U 3 7 3 10
28 8
6
Dmax = 9 Lb = max (9, min(84,16)) = 16 4
2
0

D = {dk | dk  Lb} = {2, 5, 6, 9, 10, 11, 14} 0 2 4 6 8 10 12 14 16 18 20

14 17

EDF example Workload Analysis under FP

1 1
1 1
A task i is feasible iff:
2 2  t ≤ Di : Wi(t) ≤ t
3 7

3 2

9 14 23 W2(t)
18
dbf(t)
()
16 16
14 14
12 12
10 10
8 8
6 6
4 4
2 2
0 0
0 2 4 6 8 10 12 14 16 18 20 22 24 0 2 4 6 8 10 12 14 16 18 20
Lb
15 18

3
 Workload Analysis under FP Workload Analysis under FP
1 3
A task i is feasible iff: 1 1

2  t ≤ Di : Wi(t) ≤ t 2
2 3

miss
3 2

W2(t) 9 14 23
18
W3((t))
16 16
14 14
12 12
10 10
8 8
6 6
4 4
2 2
0 0
0 2 4 6 8 10 12 14 16 18 20 0 2 4 6 8 10 12 14 16 18 20
A3 = {4, 6, 8, 9}
19 22

Workload Analysis under FP Workload Analysis under FP

1 1 Theorem [Bini-Buttazzo, 2002] AND OR

2 3
A task set is feasible under fixed priorities iff:
miss
3 2
Wi (t) ≤ t
9 14 23 i = 1...n t  Pi–1(Di)
W3((t))
16
14
12
Where Pi(t) is defined by:
10
8
6
In an unfeasible schedule: P0(t) = { t }
4  t ≤ Di : Wi(t) ≤ t t
2 Pi(t) = Pi-1 Ti
Ti U Pi-1(t)
0
0 2 4 6 8 10 12 14 16 18 20

20 23

Workload Analysis under FP Example

Theorem [Lehoczky-Sha-Ding, 1989] 1
3 6 9 12 15 18 21
2
A task set is feasible under fixed priorities iff: 8 16 24
3
 i = 1…n  t ≤ Di : Wi (t) ≤ t 20

1
Problem P0(t) = { t }
How many points need to be tested? t
Pi(t) = Pi-1 Ti
Ti U Pi-1(t)
1: P0(D1) = P0(3) = {3}
When checking i feasibility, we need to verify W(t) ≤ t for Di
and for all release times rhk ≤ Di of jobs hk with priority Ph ≥ Pi, 2: P1(D2) = P0(6) U P0(8) = {6, 8}
that is, for all t in Ai:
3: P2(D3) = P1(16) U P1(20)
Ai = rhk rhk = kTh, h = 1... i, k = 1... Ti U Di = [P0(15) U P0(16)] U [P0(18) U P0(20)]
Th
= {15, 16, 18, 20}
21 24

4
 Example Example
1
3 6 9 12 15 18 21 1
2
8 16 24 2
3
20
3
2
P0(t) = { t } N N N Y
t
Pi(t) = Pi-1 Ti
Ti U Pi-1(t) 1
1: P0(D1) = P0(3) = {3}
2
2: P1(D2) = P0(6) U P0(8) = {6, 8}
3
3: P2(D3) = P1(16) U P1(20)
= [P0(15) U P0(16)] U [P0(18) U P0(20)] N N Y N
= {15, 16, 18, 20}
25 28

Example Example
1
3 6 9 12 15 18 21 1
2
8 16 24 2
3
20
3
3
P0(t) = { t } N Y N N
t
Pi(t) = Pi-1 Ti
Ti U Pi-1(t) 1
1: P0(D1) = P0(3) = {3}
2
2: P1(D2) = P0(6) U P0(8) = {6, 8}
3
3: P2(D3) = P1(16) U P1(20)
= [P0(15) U P0(16)] U [P0(18) U P0(20)] Y N N N
= {15, 16, 18, 20}
26 29

Workload Analysis under FP Workload Analysis under FP

1 1

2 2
t1 t2
3
Wi((t)) ≤ t
i = 1...n t  Pi–1(Di)
P2(D3)
i=1 C1 ≤ T1
Pi-1(Di) is the minimum set of points t1
C2 + C ≤ t1
for checking the feasibility of i. T1 1 C2 + 2C1 ≤ 2 T1
i=2
t2 C2 + 3C1 ≤ T2
C2 + C ≤ t2
T1 1
27 30

5
 Workload Analysis under FP

C2

T2 C2 + 3C1 ≤ T2

FT1
C2 + 2C1 ≤ 2T1

C1
T2 – FT1 T2 T1
31
F+1

Workload Analysis under FP

C2

T2 C2 + (F+1)C1 ≤ T2
OR
FT1
C2 + FC1 ≤ FT1

C1
T2 – FT1 T2 T1
32
F+1

Analysis summary
Under EDF (Processor Demand Criterion):

 t D dbf (t)  t
n
t + Ti  Di
dbf (t) = Σ
i=1 Ti
Ck

Under Fixed Priorities (Workload Analysis):

i  1,..., n  t  Ai : Wi (t )  t
i–1
t
Wi (t) = Ci + Σ
k=1
C
Tk k