Real-Time Systems - Chapter 4: Priority-based scheduling - Part 3: Time demand analysis

Nội dung text: Real-Time Systems - Chapter 4: Priority-based scheduling - Part 3: Time demand analysis

1. REAL-TIME SYSTEMS Chapter4: Priority-based scheduling Part 3: Time demand analysis Computer Science Program
2. Outline • Assumptions • Fixed-priority algorithms – Rate monotonic – Deadline monotonic • Dynamic-priority algorithms – Earliest deadline first – Least slack time • Relative merits of fixed- and dynamic-priority scheduling • Schedulable utilization and proof of schedulability Real-time systems (c) Cuong Pham-Quoc 2
3. Optimality & Schedulability • We already know: – EDF and LST dynamic priority scheduling optimal: • Always produce a feasible scheduling if one exists – on a single processor as long as preemption is allowed – Fixed priority algorithms non-optimal in general: • RM and DM sometimes fail to schedule tasks that can be scheduled by other algorithms – Fixed priority is predictable while dynamic priority is not • Fixed priority algorithms do not suffer from scheduling anomalies – Schedulability tests for fixed priority: U < URM • How about task set whose U is greater than URM Real-time systems (c) Cuong Pham-Quoc 3
4. Optimality of RM and DM • Fixed priority algorithms can be optimal in restricted systems • Theorem: A system of simply periodic, independent, preemptable tasks with Di ≥ pi is schedulable on one processor using the RM algorithm if and only if U ≤ 1 – Corollary: The same is true for the DM algorithm Definition: A system of periodic tasks is simply periodic if the period of each task is an integer multiple of the period of the other tasks: pk = n × pi where pi < pk and n is a positive integer; for all Ti and Tk Real-time systems (c) Cuong Pham-Quoc 4
5. Proof • Consider the worst case: Di = pi • Assume that task Ti misses deadline at time t ⇒ t is an integer multiple of pi: t = n × pi • Due to simply periodic: – t = m × pk (∀k = 1 → i − 1 & pi > pk) (higher priority tasks) – In the worst case, there is no any task that is lower priority than Ti scheduled before t (processor busy 100%) – Total time required to complete jobs with deadline ≤ t is i t ∑ ek × = t × Ui k=1 pk – Only fail when Ui > 1 Real-time systems (c) Cuong Pham-Quoc 5
6. Schedulability of fixed-priority tasks • So far: Identified several simple schedulability tests for fixed- priority scheduling – U ≤ URM – Simply periodic • But: there are algorithms and regions of operation where we don’t have a schedulability test and must resort to exhaustive simulation – Is there a more general schedulability test? – Yes, extend the approach taken for simply periodic system schedulability Real-time systems (c) Cuong Pham-Quoc 6
7. Schedulability of fixed-priority tasks • Fixed priority algorithms are predictable and do not suffer from scheduling anomalies – The worst case execution time of the system occurs with the worst case execution time of the jobs, unlike dynamic priority algorithms which can exhibit anomalous behavior • Use this as the basis for a general schedulability test: – Find the critical instant when the system is most loaded, and has its worst response time – Use time demand analysis to determine if the system is schedulable at that instant – Prove that, if a fixed-priority system is schedulable at the critical instant, it is always schedulable Real-time systems (c) Cuong Pham-Quoc 7
8. Critical instant • A critical instant of a task Ti is a time instant which is such that: – The job in Ti released at the instant has the maximum response time of all jobs in Ti – If the job released at the critical instant meets deadline, all jobs in Ti will meet deadline • The response time of a job in Ti released at a critical instant is called the maximum (possible) response time, and is denoted by Wi Real-time systems (c) Cuong Pham-Quoc 8
9. Example • Consider two task T1 = (4,1) & T2 = (5,2) • The tasks are scheduled by RM • Critical instant of T2 at time t = 15 and t = 0 Real-time systems (c) Cuong Pham-Quoc 9
10. Finding critical instants Theorem: In a fixed-priority system where every job completes before the next job in the same task is released, a critical instant of any task Ti occurs when one of its job Ji,c is released at the same time with a job in every higher- priority task, that is, ri,c = rk,l for some l for every k = 1 → (i − 1) critical instants of T2 are t = 0 and t = 10 When is critical instant of T2 if phase of this task is 1? Real-time systems (c) Cuong Pham-Quoc 10
11. Time demand analysis • Having determined the critical instants, show that for each job Ji,c released at a critical instant, that job and all higher priority tasks complete executing before their relative deadlines • If so, the entire system be schedulable • That is: don’t simulate the entire system, simply show that it has correct characteristics following a critical instant – This process is called time demand analysis Real-time systems (c) Cuong Pham-Quoc 11
12. Time demand function • Consider task Ti, supposing that the release time t0 of the job is a critical instant of Ti • At time t0 + t (t ≥ 0), the time demand function wi(t) of this job and all the higher-priority job released in [t0, t0 + t] is given by i−1 t , for wi(t) = ei + ∑ ⌈ ⌉ × ek 0 < t ≤ pi k=1 pk • This job of Ti can meet its deadline t0 + Di if: – The supply of processor time, which is equal to t, becomes equal to or greater than the demand wi(t) for processor time – i.e., wi(t) ≤ t, for some t ≤ Di Real-time systems (c) Cuong Pham-Quoc 12
13. Time demand function: example • Consider three tasks scheduled by RM: T1 = (3,1), T2 = (5,2), T3 = (10,2) – U = 0.933 > URM – Not simply periodic • The graph show the time demand functions for these tasks i−1 t , for wi(t) = ei + ∑ ⌈ ⌉ × ek 0 < t ≤ pi k=1 pk Real-time systems (c) Cuong Pham-Quoc 13
14. Time demand analysis • Consider each task Ti in decreasing priority order (highest – lowest) • Compute the time demand function wi(t) • Check whether the inequality wi(t) ≤ t is satisfied for values of t that are equal to: p , d ; for ; i i – t = j × pk k = 1 → i j = 1 → min⌊ ⌋ pk – If this inequality is satisfied at any of these instants, Ti is schedulable i−1 t , for wi(t) = ei + ∑ ⌈ ⌉ × ek 0 < t ≤ pi k=1 pk Real-time systems (c) Cuong Pham-Quoc 14
15. Example • Question: Consider three tasks: T1 = (2,1), T2 = (3,1.2), T3 = (6,0.5); are these task feasible with RM? • Answer: – U = 0.983 > URM – The task set is not simply periodic – Use the time demand analysis: • Starting with the highest priority task T1 ⇒ calculate w1(t) • The second priority task is T2 ⇒ calculate w2(t) taking into account T1 • The final task is T3 ⇒ calculate w3(t) taking into account T1 & T2 Real-time systems (c) Cuong Pham-Quoc 15
16. Example (cont.) • Starting with task T1: p , d 1 1 – i = 1 ⇒ k = 1 & j = 1 − > min⌊ ⌋ = 1 p1 – Need to check at t = j × p1 = 1 × 2 = 2 – w1(2) = e1 = 1 ⇒ T1 meets deadline • Continuing with T2: – i = 2 ⇒ k = 1 & 2 p , d 2 2 • k = 1 : j = 1 → min⌊ ⌋ = 1 p1 p , d 2 2 • k = 2 : j = 1 → min⌊ ⌋ = 1 p2 – Need to check at t = j × p1 = 2 & t = j × p2 = 3 t 2 not meet! – w2(2) = e2 + ⌈ ⌉ × e1 = 1.2 + × 1 = 2.2 > 2 ⇒ p1 2 t 3 not meet!; is not schedulable – w2(3) = e2 + ⌈ ⌉ × e1 = 1.2 + ⌈ ⌉ × 1 = 3.2 > 3 ⇒ T2 p1 2 Real-time systems (c) Cuong Pham-Quoc 16
17. Alternative solution • Using the time demand graph – Critical instants of all tasks: 0 Time demand for T2 is always larger than tme supply during the executon of J2,1 Real-time systems (c) Cuong Pham-Quoc 17
18. Example • Question: Consider three tasks: T1 = (2,1), T2 = (3,1.0), T3 = (6,0.5); are these task feasible with RM? • Answer: – U = 0.917 > URM – The task set is not simply periodic – Use the time demand analysis: • Starting with the highest priority task T1 ⇒ calculate w1(t) • The second priority task is T2 ⇒ calculate w2(t) taking into account T1 • The final task is T3 ⇒ calculate w3(t) taking into account T1 & T2 Real-time systems (c) Cuong Pham-Quoc 18
19. Example (cont.) • Starting with task T1: p , d 1 1 – i = 1 ⇒ k = 1 & j = 1 → min⌊ ⌋ = 1 p1 – Need to check at t = j × p1 = 1 × 2 = 2 – w1(2) = e1 = 1 ⇒ T1 meets deadline • Continuing with T2: – i = 2 ⇒ k = 1 & 2 p , d 2 2 • k = 1 : j = 1 → min⌊ ⌋ = 1 p1 p , d 2 2 • k = 2 : j = 1 → min⌊ ⌋ = 1 p2 – Need to check at t = j × p1 = 2 & t = j × p2 = 3 t 2 meet deadline (no need to check ) – w2(2) = e2 + ⌈ ⌉ × e1 = 1.0 + × 1 = 2.0 = 2 ⇒ w2(3) p1 2 Real-time systems (c) Cuong Pham-Quoc 19
20. Example (cont.) • Continuing with T3: – i = 3 ⇒ k = 1,2,3 p , d 6 3 3 • k = 1 : j = 1 → min⌊ ⌋ = 1 → min⌊ ⌋ = 1,2,3 p1 2 – Need to check at t = j × p1 = 2,4,6 p , d 3 3 • k = 2 : j = 1 → min⌊ ⌋ = 1,2 p2 – Need to check at t = j × p2 = 3,6 p , d 3 3 • k = 3 : j = 1 → min⌊ ⌋ = 1 → t = j × p3 = 6 p3 – w3(2) = ?; w3(3) = ?; w3(4) = ?; w3(6) = ? • If there exists any wi(t) that satisfies, then we stop and conclude; otherwise the task is not schedulable Real-time systems (c) Cuong Pham-Quoc 20
21. Another example • Question: Consider three tasks: T1 = (3,1), T2 = (5,1.5), T3 = (7,1.25) are these task feasible with RM? • Answer: – Utilization? – Simply periodic? Real-time systems (c) Cuong Pham-Quoc 21
22. Exercises 1. Which of the following systems of periodic tasks are schedulable by the rate- monotonic algorithm? By the earliest-deadline-first algorithm? Explain your answer. a) T = {(8,3), (9,3), (15,3)} b) T = {(8,4), (12,4), (20,4)} c) T = {(8,4), (10,2), (12,3)} 2. Give two different explanations of why the periodic tasks (2, 1), (4, 1), and (8, 2) are schedulable by the rate-monotonic algorithm 3. The periodic tasks (3, 1), (4, 2), and (6, 1) are scheduled according to the rate- monotonic algorithm. a) Draw the time-demand functions of the tasks. b) Are the tasks schedulable? Why or why not? Real-time systems (c) Cuong Pham-Quoc 22