Real-Time Systems - Chapter 4: Priority-based scheduling - Part 2: Dynamic priority algorithms

Nội dung text: Real-Time Systems - Chapter 4: Priority-based scheduling - Part 2: Dynamic priority algorithms

1. REAL-TIME SYSTEMS Chapter4: Priority-based scheduling Part 2: Dynamic priority algorithms 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. Dynamic priority algorithm • Discussed several dynamic-priority algorithms in lecture 3: – Earliest deadline first (EDF): The job queue is ordered by earliest deadline – Least slack time first (LST): The job queue is ordered by least slack time • Strict LST – scheduling decisions are made also whenever a queued job’s slack time becomes smaller than the executing job’s slack time – huge overheads, not used • Non-strict LST – scheduling decisions made only when jobs release or complete – First in, first out (FIFO): Job queue is first-in-first-out by release time – Last in, first out (LIFO): Job queue is last-in-first-out by release time • Focus on EDF as commonly used example Real-time systems (c) Cuong Pham-Quoc 3
4. EDF Example • Consider three tasks: T1 = (6,2,4); T2 = (8,2,5); & T3 = (9,3,7) – At t = 0: priority list T1 > T2 > T3 – At t = 6: priority list T3 > T1 > T2 EDF is task-level dynamic priority (job-level fixed priority): when released, priority level of a job is unchanged compared to other existing jobs Real-time systems (c) Cuong Pham-Quoc 4
5. Warm-up exercise • Schedule the following task set using the EDF algorithm – T1 = (2,0.5); T2 = (4,1); T3 = (5,1.5) Real-time systems (c) Cuong Pham-Quoc 5
6. LST example • Slack time at time t of a job whose remaining execution time is k and whose deadline is d is equal to d − t − x • Consider three tasks: T1 = (2,0.8); T2 = (5,1.5); T3 = (5.1,1.5) – At time t = 0, the priority list J1,1 > J2,1 > J3,1 – At time t = 2 (J1,2 is released), the priority list J1,2 > J3,1 > J2,1 LST is job-level dynamic priority: when released, priority level of a job is changeable compared to other existing jobs Real-time systems (c) Cuong Pham-Quoc 6
7. Comparing different algorithms • Compare performance of RM, EDF, LST and FIFO scheduling – Assume a single processor system with 2 tasks: T1 = (2,1) & ⇒ T2 = (5,2.5) H = 10 • The total utilization is 1.0 ⇒ no slack time – Expect some of these algorithms to lead to missed deadlines! – This is one of the cases where EDF works better than RM/ DM Real-time systems (c) Cuong Pham-Quoc 7
8. Example: FIFO, LST, EDF, and RM • Static-priority is not optimal • So: Why bother with static-priority? – Simplicity – Predictability Real-time systems (c) Cuong Pham-Quoc 8
9. Unpredictability of EDF Scheduling • Over-running jobs in EDF hold on their priorities • Consider three tasks: T1 = (2,1), T2 = (4,1) & T3 = (8,2) Normal execution; all deadlines meet Real-time systems (c) Cuong Pham-Quoc 9
10. Unpredictability of EDF Scheduling T3 over-runs How about RM/DM scheduling? T3 over-runs longer Real-time systems (c) Cuong Pham-Quoc 10
11. EDF – anomalies example • Consider the following setup: ri di [ei-,ei+] – EDF scheduling J1 0 10 5 J2 0 10 [2, 6] – 2 processors J3 4 15 8 – Preemptable jobs J4 0 20 10 – Jobs cannot change CPU once mapped What is the best case in term of • Scheduling interval [0, 20] execution time of the entire system? • Will all jobs meet the deadlines? Real-time systems (c) Cuong Pham-Quoc 11
12. EDF – anomalies example ri di [ei-,ei+] • Assume that e2 = 6 J1 0 10 5 • Total execution time is 16 J2 0 10 [2, 6] – All jobs meet deadlines J3 4 15 8 J4 0 20 10 Real-time systems (c) Cuong Pham-Quoc 12
13. EDF – anomalies example ri di [ei-,ei+] • Assume that e2 = 2 J1 0 10 5 • Total execution time is 20 J2 0 10 [2, 6] (increased) J3 4 15 8 – All jobs meet deadlines J4 0 20 10 Real-time systems (c) Cuong Pham-Quoc 13
14. EDF – anomalies example ri di [ei-,ei+] • Assume that e2 = 3 J1 0 10 5 • Total execution time is 21 J2 0 10 [2, 6] (increased) J3 4 15 8 – J4 misses the deadline J4 0 20 10 Real-time systems (c) Cuong Pham-Quoc 14
15. EDF – anomalies example ri di [ei-,ei+] • Assume that e2 = 5 J1 0 10 5 • Total execution time is 15 J2 0 10 [2, 6] (decreased) J3 4 15 8 – The best case J4 0 20 10 Real-time systems (c) Cuong Pham-Quoc 15
16. EDF advantages vs. disadvantages • Advantages: – Very flexible (arrival times and deadlines do not need to be known before implementation) – Moderate complexity – Able to handle aperiodic jobs • Disadvantages: – Difficult to verify – Hard to determine the best EDF schedule • Sometime, what we think would make the system worse actually make it better – . (discuss later) Real-time systems (c) Cuong Pham-Quoc 16
17. Schedulable utilization: EDF • Theorem: a system of independent preemptable periodic tasks with Di = pi can be feasibly scheduled on one processor using EDF if and only if U ≤ 1 – UEDF = 1 for independent, preemptable periodic tasks with Di = pi [Expected since EDF proved optimal in lecture 2] – Corollary: result also holds if deadline longer than period: UEDF = 1 for independent preemptable periodic tasks with Di ≥ pi Real-time systems (c) Cuong Pham-Quoc 17
18. Schedulable utilization: EDF • What happens if Di 1 (would have to run the ⇒ exhaustive simulation to prove) T1 = (2,0.6,1); T2 = (5,2.3) Real-time systems (c) Cuong Pham-Quoc 18
19. Exercises 1. For each following task set, verify the schedulability under EDF and construct the schedule a) T1 = (4,1); T2 = (6,2); T3 = (8,3) b) T1 = (6,2,5); T2 = (8,2,4); T3 = (12,4,8) 2. Construct the initial segments in the time interval [0,750] using RM and EDF for the following task set. Comment the results! a) T1 = (100,20); T1 = (150,50); T3 = (250,100) b) T1 = (100,20); T2 = (150,50); T3 = (250,120) Real-time systems (c) Cuong Pham-Quoc 19