Real-Time Systems - Chapter 2: Basic scheduling

Nội dung text: Real-Time Systems - Chapter 2: Basic scheduling

1. REAL-TIME SYSTEMS Chapter 2: Basic scheduling Computer Science Program
2. Outline • Overview of real-time scheduling algorithms – Clock-driven – Weighted round-robin – Priority driven • Dynamic vs. static • Deadline scheduling: EDF and LST • Outline relative strengths, weaknesses Real-time systems (c) Cuong Pham-Quoc 2
3. Task states • Ready: not executed, wait for scheduling point suspended suspend • Running: get scheduled to a called processor suspend • Blocked: not running & cannot be called scheduled at the next scheduling point ready running – Delay scheduled – Wait for data/resources suspend Events e.g., – called delay running out Blocking APIs • Suspended: user/system wants to called e.g. completely remove the task from blocked delay() being scheduled – E.g., user press the “pause” button Real-time systems (c) Cuong Pham-Quoc 3
4. Feasible schedule • A schedule that never misses any deadline is called feasible • A set of tasks is schedulable if there exists at least a feasible schedule • A scheduling algorithm is optimal if it always produces a feasible schedule in case a given set of tasks is schedulable T T1 T3 2 D1D2 D3 D1D2 D3 T Not T T3 T1 T1 T3 Feasible 2 feasible 2 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Real-time systems (c) Cuong Pham-Quoc 4
5. Approaches to Real-time scheduling • Different classes of scheduling algorithm used in real-time systems: – Weighted round-robin • Primarily used for scheduling real-time traffic in high-speed, switched networks • Rarely used in other real-time systems – Clock-driven (time-driven) • Primarily used for hard real-time systems • All properties of all jobs are known at design time – Offline (at design time) scheduling techniques (complicated) can be used – Priority-driven • Primarily used for more dynamic real-time systems with a mix of time-based and event-based activities • The system must adapt to changing conditions and events Real-time systems (c) Cuong Pham-Quoc 5
6. Weighted round-robin: overview • Regular round-robin scheduling is commonly used for scheduling time-shared applications – Every job joins a FIFO queue when it is ready for execution – When the scheduler runs, it schedules the job at the head of the queue to execute for at most one time slice • Sometimes called a quantum – typically O(tens of ms) – If the job has not completed by the end of its quantum, it is preempted and placed at the end of the queue – When there are n ready jobs in the queue, each job gets one slice every n time slices (n time slices is called a round) – Only limited use in real-time systems Real-time systems (c) Cuong Pham-Quoc 6
7. Weighted round-robin: overview • Weighted round-robin Each job is assigned a weight – Ji wi – The job will receive consecutive time slices each round wi • Equivalent to regular round robin if all weights equal 1 • Partitions capacity between jobs according to some ratio • Offers throughput guarantees – Each job makes a certain amount of progress each round Real-time systems (c) Cuong Pham-Quoc 7
8. Weighted round-robin: overview • Advantages: – Simple to implement, since it doesn’t require a sorted priority queue – Reasonable approach for jobs that can incrementally consume output from their predecessor • since they execute concurrently in a pipelined fashion • E.g. Jobs communicating using Unix pipes • E.g. Wormhole switching networks, where message transmission is carried out in a pipeline fashion and a downstream switch can begin to transmit an earlier portion of a message, without having to wait for the arrival of the later portion • Drawbacks: Real-time systems (c) Cuong Pham-Quoc 8
9. Weighted round-robin: example P1 P2 Weighted round-robin when time slice is small compared to 1 Weighted round-robin when time slice is 1 Real-time systems: scheduling - overview Real-time systems (c) Cuong Pham-Quoc 9
10. Clock-driven scheduling: overview • Scheduling decision time: point in time when scheduler decides which job to execute next • Scheduling decision time in clock-driven schedulers is defined a priori before the system begins execution – Hardware timer to periodically wake up the scheduler to generate a portion of the schedule • Special case: When job parameters are known a priori, schedule can be pre-computed off-line, and stored as a table (table-driven schedulers) – Scheduling overhead at run-time can be minimized – Simple and straight-forward, not flexible Real-time systems (c) Cuong Pham-Quoc 10
11. Priority scheduling: overview • Basic rule: never leave processor idle when there is work to be done: – Work conserving scheduling – Greedy scheduling – List scheduling • Possible implementation of preemptive priority-driven scheduling: – Assign priorities to jobs – Scheduling decisions are made when • Job becomes ready • Processor becomes idle • Priorities of jobs change – At each scheduling decision time, choose ready task with highest priority • In non-preemptive cases, scheduling decisions are made only when processor becomes idle Real-time systems (c) Cuong Pham-Quoc 11
12. Scheduling decision points • Scheduling decision points (priority driven): 1. The running process blocks, i.e. changes from running to waiting 2. The running thread terminates 3. A waiting thread becomes ready 4. The current thread is preempted, i.e. switches from running to ready Real-time systems (c) Cuong Pham-Quoc 12
13. Example Preemptive • Release times for all jobs are at 0, except J5 at 4 • Two processors, P1 & P2, communicate via a shared memory • Priority List = (J1, J2, . . . , J8) Non-preemptive Real-time systems (c) Cuong Pham-Quoc 13
14. Exercise • All jobs are released at time 0 • Used two processors (shared memory) for execution • Priority lists a. J1, J2, J3, J4, J5, J6, J7, J8 b. J5, J8, J2, J6, J1, J3, J4, J7 c. J8, J1, J2, J3, J4, J5, J6, J7 Real-time systems (c) Cuong Pham-Quoc 14
15. Priority scheduling • Note: The ability to preempt lower priority jobs slowed down the overall completion of the task – This is not a general rule, but shows that priority scheduling results can be non-intuitive – Different priority scheduling algorithms can have very different properties Real-time systems (c) Cuong Pham-Quoc 15
16. Priority scheduling • Most scheduling algorithms used in non/soft real-time systems are priority-driven – First-In-First-Out Assign priority based on release time – Last-In-First-Out – Shortest-Execution-Time-First Assign priority based on execution time – Longest-Execution-Time-First • Real-time priority scheduling assigns priorities based on deadline or some other timing constraint: – Earliest deadline first – Least slack time first Real-time systems (c) Cuong Pham-Quoc 16
17. Priority scheduling based on Deadlines • Earliest deadline first (EDF) — mainly used – Assign priority to jobs based on deadline – Earlier the deadline, higher the priority – Simple, just requires knowledge of deadlines • Least Slack Time first (LST) – Assign priority to jobs based on slack time: tslack – The smaller the slack time, the higher the priority – A job Ji has deadline di, execution time ei, and was released at time ri – At time t < di: Remaining execution time ; where is the amount of time the processor has processed the job • trem = ei − ei′ ei′ Slack time • tslack = di − t − trem = di − t − (ei − ei′) – More complex, requires knowledge of execution times and deadlines • Knowing the actual execution time is often difficult a priori, since it depends on the data, need to use worst case estimates (⇒ poor performance) Real-time systems (c) Cuong Pham-Quoc 17
18. Optimality of EDF & LST • These algorithms are optimal – i.e. they will always produce a feasible schedule if one exists – Constraints: • Single processor • Preemption • No resources contending Real-time systems (c) Cuong Pham-Quoc 18
19. Proof • Fact: any feasible schedule can be transformed into an EDF schedule – Why?: if Ji is scheduled to execute before Jk, but Ji’s deadline is later than Jk’s either: ⇒ • The release time of Jk is after the Ji completes they’re already in EDF order • The release time of Jk is before the end of the interval in which Ji executes: – Swap Ji and Jk (this is always possible, since Ji’s deadline is later than Jk’s) – Move any jobs following idle periods forward into the idle period – => the result is an EDF schedule Real-time systems (c) Cuong Pham-Quoc 19
20. Non-optimality of EDF & LST • Neither algorithm is optimal if jobs are non-preemptable or if there is more than one processor J1(r1 = 0; e1 = 3; d1 = 10); J1(r1 = 0; e1 = 1; d1 = 1); J2(r2 = 2; e2 = 6; d2 = 14); J2(r2 = 0; e2 = 1; d2 = 2); J3(r3 = 4; e3 = 4; d3 = 12); J3(r3 = 0; e3 = 5; d3 = 5); Real-time systems (c) Cuong Pham-Quoc 20
21. Dynamic vs. Static systems • Dynamic systems – A job can be dispatched to any processors in a multiprocessors system – A job can migrate (start executing on one processor and resuming on a different one) • Static system – Jobs are partitioned and bounded to a particular processor statically • Static systems have inferior performance (in terms of overall response time of the jobs) relative to dynamic systems – But, possible to validate – Most hard real-time systems are static Real-time systems (c) Cuong Pham-Quoc 21
22. Effective Release times and Deadlines • Sometimes the release time of a job may be later than that of its successors, or its deadline may be earlier than that specified for its predecessors • This makes no sense: derive an effective release time or effective deadline consistent with all precedence constraints, and schedule using that – Effective release time • If a job has no predecessors, its effective release time is its release time • If it has predecessors, its effective release time is the maximum of its release time and the effective release times of its predecessors – Effective deadline • If a job has no successors, its effective deadline is its deadline • It if has successors, its effective deadline is the minimum of its deadline and the effective deadline of its successors Real-time systems (c) Cuong Pham-Quoc 22
23. Effective Release times and Deadlines • Feasible to schedule any set of jobs according to their actual release times and deadline, iff feasible to schedule according to effective release times and deadlines – Ignore precedence constraints, schedule using effective release times and deadlines as if all jobs independent – Resulting schedule might meet deadlines but not precedence constraints • If so, always possible to swap order of jobs within the schedule to meet deadlines and precedence constraints Real-time systems (c) Cuong Pham-Quoc 23
24. Example • Find effective release time and effective deadlines Release time Deadline Real-time systems (c) Cuong Pham-Quoc 24
25. Exercises 1. The feasible interval of each job in the precedence graph in the following figure is given next to its name. The execution time of all jobs are equal to 1. a. Find the effective release times and deadlines of the jobs in the precedence graph in the figure. b. Find an EDF schedule of the jobs. c. A job is said to be at level i if the length of the longest path from the job to jobs that have no successors is i. So, jobs J3, J6, and J9 are at level 0, jobs J2 and J8 are at level 1, and so on. Suppose that the priorities of the jobs are assigned based on their levels: the higher the level, the higher the priority. Find a priority-driven schedule of the jobs in the according to this priority assignment. Real-time systems (c) Cuong Pham-Quoc 25
26. Exercises 2. Consider a system that has five periodic tasks, A, B, C, D, and , , E, and three processors P1 P2 and P3. The periods of A, B, and C are 2 and their execution times are equal to 1. The periods of D and E are 8 and their execution times are 6. The phase of every task is 0, that is, the first job of the task is released at time 0. The relative deadline of every task is equal to its period. a. Show that if the tasks are scheduled dynamically on three processors according to the LST algorithm, some jobs in the system cannot meet their deadlines. b. Find a feasible schedule of the five tasks on three processors. Real-time systems (c) Cuong Pham-Quoc 26
27. Exercises 3. A system contains nine non-preemptable jobs named Ji, for i = 1,2, ,9. Their execution times are 3, 2, 2, 2, 4, 4, 4, 4, and 9, respectively, their release times are equal to 0, and their deadlines are 12. J1 is the immediate predecessor of J9, and J4 is the immediate predecessor of , , J5 J6 J7, and J8. There is no other precedence constraints. For all the jobs, Ji has a higher priority than Jk if i < k. a. Draw the precedence graph of the jobs. b. Can the jobs meet their deadlines if they are scheduled on three processors? Explain your answer. Real-time systems (c) Cuong Pham-Quoc 27