CSA404 – Example to perform the “Completion Time Test” based on CPU resource usage Wn(f) computation (R-T Theorem 2)
This is a step by step calculation of finding the minimal time interval required to schedule a number of tasks. A.k.a “trying to un-muddle your comprehension of the 26/10/98 lecture”. This is the same exampleas that presented during the lecture. I hope this clearer, and more personalised, presentation helps you better understand (no said faced relationships this time - I hope.). Just allow me to get this off my chest first….. GRRRR - I HATE THE MICROSOFT EQUATION EDITOR!…. mmmm, I feel better already. Well, down to the nitty-gritty…
Assume the following periodic tasks need to be scheduled:
Task Number / Completion time “C” (ms) / Period “T” (ms)1 / 40 / 100
2 / 30 / 200
3 / 200 / 2000
Generic initial assumptions for n tasks:
i: Iteration number (integer) 0 < i (iterations stop when ti = ti-1 - i.e. no revision done - see below)
j: Task number (integer) 0 < j n
t0 = C1 + C2 +…+ Cn
N0,1 = N0,2 = …= N0,n = 1
Relationships used in calculations within every iteration:
Assimilation of previous time:
ti = ti-1
Check if the estimated (current) time interval needs adjustment:
Tix Ni-1,j > ti
Compute the number of times a task j can be successfully scheduled in time interval [0, ti] based on the current value tiand the scheduling times of the previous iteration:
Ni,j = Ni-1,j + (ti – Tix Ni-1,j) / Ti
Revise the value of ti within the iteration using the scheduling difference Ni,j - Ni-1,j:
ti = ti+ Cj(Ni,j - Ni-1,j)
Check whether another iteration is required:
ti = ti-1 (?)
Initial example-specific assumptions:
j = 3
t0 = C1 + C2 + C3 = 270 ms
N0,1 = N0,2 = N0,3 = 1
Start iteration 1:
Assimilate previous time:t1 = t0 = 270 ms
Task 1
Check on schedulability of task 1 (iteration 1) – T1x N0,1 > t1
Is 100 x 1 > 270 ? (false adjust t1)
Compute how many times task 1 can be scheduled in time interval [0, t1]:
N1,1 = N0,1 + (t1 – T1x N0,1) / T1 = 1 + (270 – 100 x 1) / 100 = 1 + 2 = 3
Revise the current value of t1:
t1 = t1+ C1(N1,1 – N0,1) = 270 + 40(3 – 1) = 270 + 80 = 350 ms
Task 2
Check on schedulability of task 2 (iteration 1) – T2x N0,2 > t1
Is 200 x 1 > 350 ? (false adjust t1)
Compute how many times task 2 can be scheduled in time interval [0, t1]:
N1,2 = N0,2 + (t1 – T2x N0,2) / T2 = 1 + (350 – 200 x 1) / 200 = 1 + 1 = 2
Revise the current value of t1:
t1 = t1+ C2(N1,2 – N0,2) = 350 + 30(2 – 1) = 350 + 30 = 380 ms
Task 3
Check on schedulability of task 3 (iteration 1) – T3x N0,3 > t1
Is 2000 x 1 > 380 ? (true no need to adjust t1)
N1,3 = N0,3 = 1 (no scheduling change for task 3)
Check if another iteration is necessary:t1t0 do another iteration.
End iteration 1.
Start iteration 2:
Assimilate previous time:t2 = t1 = 380 ms
Task 1
Check on schedulability of task 1 (iteration 2) – T1x N1,1 > t2
Is 100 x 3 > 380 ? (false adjust t2)
Compute how many times task 1 can be scheduled in time interval [0, t2]:
N2,1 = N1,1 + (t2 – T1x N1,1) / T1 = 3 + (380 – 100 x 3) / 100 = 3 + 1 = 4
Revise the current value of t2:
t2 = t2+ C1(N2,1 – N1,1) = 380 + 40(4 – 3) = 380 + 40 = 420 ms
Task 2
Check on schedulability of task 2 (iteration 2) – T2x N1,2 > t2
Is 200 x 2 > 420 ? (false adjust t2)
Compute how many times task 2 can be scheduled in time interval [0, t2]:
N2,2 = N1,2 + (t2 – T2x N1,2) / T2 = 2 + (420 – 200 x 2) / 200 = 2 + 1 = 3
Revise the current value of t1:
t2 = t2+ C2(N2,2 – N1,2) = 420 + 30(3 – 2) = 420 + 30 = 450 ms
Task 3
Check on schedulability of task 3 (iteration 2) – T3x N1,3 > t2
Is 2000 x 1 > 450 ? (true no need to adjust t2)
N2,3 = N1,3 = N0,3 = 1 (no scheduling change for task 3)
Check if another iteration is necessary:t2t1 do another iteration.
End iteration 2.
Start iteration 3:
Assimilate previous time:t3 = t2 = 450 ms
Task 1
Check on schedulability of task 1 (iteration 3) – T1x N2,1 > t3
Is 100 x 4 > 450 ? (false adjust t3)
Compute how many times task 1 can be scheduled in time interval [0, t3]:
N3,1 = N2,1 + (t3 – T1x N2,1) / T1 = 4 + (450 – 100 x 4) / 100 = 4 + 1 = 5
Revise the current value of t3:
t3 = t3+ C1(N3,1 – N2,1) = 450 + 40(5 – 4) = 450 + 40 = 490 ms
Task 2
Check on schedulability of task 2 (iteration 3) – T2x N2,2 > t3
Is 200 x 3 > 490 ? (true no need to adjust t3)
N3,2 = N2,2= 3(no scheduling change for task 2)
Task 3
Check on schedulability of task 3 (iteration 3) – T3x N2,3 > t3
Is 2000 x 1 > 490 ? (true no need to adjust t3)
N3,3 = N2,3 = N1,3 = N0,3 = 1 (no scheduling change for task 3)
Check if another iteration is necessary:t3t2 do another iteration.
End iteration 3.
Start iteration 4:
Assimilate previous time:t4 = t3 = 490 ms
Task 1
Check on schedulability of task 1 (iteration 4) – T1x N3,1 > t4
Is 100 x 5 > 490 ? (trueno need to adjust t4)
N4,1= N3,1= 5(no scheduling change for task 1)
Task 2
Check on schedulability of task 2 (iteration 4) – T2x N3,2 > t4
Is 200 x 3 > 490 ? (true no need to adjust t4)
N4,2 = N3,2 = N2,2= 3(no scheduling change for task 2)
Task 3
Check on schedulability of task 3 (iteration 4) – T3x N3,3 > t4
Is 2000 x 1 > 490 ? (true no need to adjust t4)
N4,3 = N3,3 = N2,3 = N1,3 = N0,3 = 1 (no scheduling change for task 3)
Check if another iteration is necessary:t4=t3Stop – no more iterations.
End iteration 4.
ALL TASKS SCHEDULED - END OF COMPUTATION.
Therefore, final resultsread as follows:
t4 = 490 ms (Minimal time interval for all 3 tasks to complete successfully)
N4,1= 5 (task 1 will complete 5 times within 490 ms: Period = 10.20 s-1)
N4,2= 3 (task 2 will complete 3 times within 490 ms: Period = 6.12 s-1)
N4,3= 1 (task 1 will complete oncewithin 490 ms: Period = 2.04 s-1)