Real-Time Systems - Chapter 4: Priority-based scheduling - Part 1: Rate monotonic & Deadline monotonic

Nội dung text: Real-Time Systems - Chapter 4: Priority-based scheduling - Part 1: Rate monotonic & Deadline monotonic

1. REAL-TIME SYSTEMS Chapter4: Priority-based scheduling Part 1: Rate monotonic & Deadline monotonic 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. Disadvantages of clock-based scheduling • Off-line scheduling => low flexibility – Changes in functionality in the C code => varying in execution time – Changes in data deadline void decoder(){ F = readFile(); 1920x1080 getFrames(F); Consider worst-case execution decode(F); 1280x720 time with clock-based scheduling close(F); } 1 2 3 4 5 6 7 8 9 10 Real-time systems (c) Cuong Pham-Quoc 3
4. Priority-based scheduling • On-line scheduler => scheduling decisions at run-time – Event driven: timer interrupt, release of a task, completion of a task, • CPU is idle only when no jobs are ready for execution – Optimized execution further than clock-based scheduling • Job selection: at scheduling points – The highest priority and ready task • High flexibility => tasks can be deleted or updated runtime • Require more complex scheduling Real-time systems (c) Cuong Pham-Quoc 4
5. Assumptions • Priority-driven scheduling of periodic tasks on a single processor • Assume a restricted periodic task model: – A fixed number of independent periodic tasks exist • Are ready for execution as soon as they are released • Can be pre-empted at any time • Never suspend themselves – New tasks only admitted after an acceptance test; may be rejected – The period of a task defined as minimum inter-release time of jobs in task – There are no aperiodic or sporadic tasks – Scheduling decisions made immediately upon job release and completion – Context switch overhead negligibly small; unlimited priority levels Real-time systems (c) Cuong Pham-Quoc 5
6. Why focus on uniprocessor scheduling? • Poor worst-case performance of priority-driven algorithms in dynamic environments • Resource access is very complicated to analyze Real-time systems (c) Cuong Pham-Quoc 6
7. Fixed priority vs. Dynamic priority • A priority-driven scheduler is an on-line scheduler – It does not pre-compute a schedule of tasks/jobs: instead assigns priorities to jobs when released, places them on a run queue in priority order – When pre-emption is allowed, a scheduling decision is made whenever a job is released or completed – At each scheduling decision time, the scheduler updates the run queues and executes the job at the head of the queue Fixed (static) priority: All jobs in task have same priority Dynamic priority: May assign different priorities to individual jobs Real-time systems (c) Cuong Pham-Quoc 7
8. Rate-Monotonic (RM) algorithm • Best known fixed-priority algorithm is rate monotonic scheduling • Assigns priorities to tasks based on their periods – The shorter the period, the higher the priority – The rate (of job releases) is the inverse of the period, so jobs with higher rate have higher priority • Very widely studied and used Real-time systems (c) Cuong Pham-Quoc 8
9. RM example • Consider a system of 3 tasks: • Exercise: consider a system of 1 – T = (4,1) ⇒ rate = 2 tasks: 1 4 1 – T = (2,0.9) – T2 = (5,2) ⇒ rate = 1 5 1 – T2 = (5,2.3) – T3 = (20,5) ⇒ rate = 20 – Relative priorities: T1 > T2 > T3 Real-time systems (c) Cuong Pham-Quoc 9
10. Deadline-Monotonic (DM) algorithm • The deadline monotonic algorithm assigns task priority according to relative deadlines – The shorter the relative deadline, the higher the priority • When relative deadline of every task matches its period, then rate monotonic and deadline monotonic give identical results • When the relative deadlines are arbitrary: – Deadline monotonic can sometimes produce a feasible schedule in cases where rate monotonic cannot – But, rate monotonic always fails when deadline monotonic fails • Deadline monotonic outperforms to rate monotonic – If deadline ≠ period Real-time systems (c) Cuong Pham-Quoc 10
11. DM example • Consider the following task set: – T1 = (50,50,25,100); – T2 = (0,62.5,10,20); – T3 = (0,125,25,50) • Scheduling interval: H = lcm(50,62.5,120) = 250 – Total utilization: 0.86 • Priority list: T2 > T3 > T1 Real-time systems (c) Cuong Pham-Quoc 11
12. RM vs. DM • Consider the previous task set – DM can find a feasible schedule – RM cannot (priority list: T1 > T2 > T3) • Real-time systems (c) Cuong Pham-Quoc 12
13. Schedulability tests • How to verifying a scheduling? – Simulate: 2 × H long timeline => too expensive • Schedulability test: – A test to demonstrate that all deadlines are met, when scheduled using a particular algorithm – An efficient schedulability test can be used as an on-line acceptance test Real-time systems (c) Cuong Pham-Quoc 13
14. Schedulable utilization • Recall: a periodic task Ti is defined by the 4-tuple (ϕi, pi, ei, Di) ei with utilization ui = pi • Total utilization of the system where 0 ≤ U ≤ 1 • A scheduling algorithm can feasibly schedule any system of periodic tasks on a processor if U is equal to or less than the maximum schedulable utilization of the algorithm, Ualg – If Ualg = 1, the algorithm is optimal • Why is knowing of Ualg important? It gives a schedulability test, where a system can be validated by showing that U ≤ Ualg Real-time systems (c) Cuong Pham-Quoc 14
15. Schedulable utilization of RM • Theorem: a system of n independent preemptable periodic tasks with Di = pi can be feasibly scheduled on one processor 1 using RM if U ≤ n × (2 n − 1) 1 n – URM(n) = n × (2 − 1) – n large, URM → ln 2 = 0.693 • Note: U ≤ URM(n) is a sufficient, but not necessary, condition – i.e., a feasible rate monotonic schedule is guaranteed to exist if U ≤ URM(n), but might still be possible if U > URM(n) Real-time systems (c) Cuong Pham-Quoc 15
16. Examples • Consider a system with the task set: – T1 = (5,1); T2 = (4,0.5); T3 = (6,1.2) 1 0.5 1.2 – Total utilization U = + + = 0.525 ≤ 0.693 5 4 6 – System is guaranteed feasible, priority list: T2 > T1 > T3 • Consider another system with the task set: – T1 = (4,1); T2 = (6,1); T3 = (2,1) – U = 0.917 > URM – More tests must be applied • next lectures Real-time systems (c) Cuong Pham-Quoc 16
17. Exercises 1. Verify the schedulability and construct the schedule according to the RM algorithm for the following set of periodic tasks: – T1 = (6,2); T2 = (8,2); T3 = (12,2) – T1 = (5,3); T2 = (8,1); T3 = (10,1) – T1 = (4,1); T2 = (6,2); T3 = (10,3) – T1 = (6,2,5); T2 = (8,2,4); T3 = (12,4,8) 2. A system consists of three periodic tasks: (3, 1), (5, 2), (8, 3) – What is the total utilization? – Construct a RM schedule for this system in the interval [0 : 32]. Label any missed deadlines – Suppose we want to reduce the execution time of the task with period 3 so that the system is schedulable with the RM algorithm. What is the minimum amount of reduction necessary? 3. Given a system consists four tasks T1 = (8,1); T2 = (15,3); T3 = (20,4); and T3 = (22,6), draw the initial segment in the time interval [0 : 50]. Real-time systems (c) Cuong Pham-Quoc 17