05-Process and thread scheduling

1 .Operating Systems 1 5. Process and thread scheduling 5.1 Organization of Schedulers Embedded and Autonomous Schedulers 5.2 Scheduling Methods A Framework for Scheduling Common Scheduling Algorithms Comparison of Methods 5.3 Priority Inversion

2 .Operating Systems 2 Process and Thread Scheduling Scheduling occurs at two levels: Process/job scheduling Long term scheduling (seconds, minutes, …) Move process to Ready List (RL) after creation (When and in which order?) Dispatching Short term scheduling (milliseconds) Select process from Ready List to run We use the term scheduling to refer to both

3 .Operating Systems 3 Organization of Schedulers Embedded Called as function at end of kernel call Runs as part of calling process Autonomous Separate process Multiprocessor : m ay have dedicated CPU Single-processor : scheduler and other processes alternate (every quantum)

4 .Operating Systems 4 An Embedded Scheduler Scheduler() { do { find highest priority process p with p.status == ready_a ; find a free cpu ; if ( cpu != NIL) Allocate_CPU ( p,cpu ); } while ( cpu != NIL); do { find highest priority process p with p.status == ready_a ; find lowest priority process q with p.status ==running ; if (Priority(p) > Priority(q)) Preempt( p,q ); } while (Priority(p) > Priority(q)); if (self-> Status.Type !=running) Preempt( p,self ); }

5 .Operating Systems 5 Scheduling Methods Priority determines who runs Can be static or dynamic Given by Priority function: P = Priority(p) p are parameters Arbitration rule to break ties Random Chronological (FIFO ) Cyclic (Round Robin = RR) When is scheduler invoked ?—Decision mode Preemptive : scheduler called periodically (quantum-oriented) or when system state changes Nonpreemptive : scheduler called when process terminates or blocks

6 .Operating Systems 6 Priority function Parameters Possible parameters: Attained service time ( a ) Real time in system ( r ) Total service time ( t ) Period ( d ) Deadline (explicit or implied by period) External priority ( e ) System load (not process-specific)

7 .Operating Systems 7 Scheduling algorithms Name Decision mode Priority Arbitration FIFO : nonpreemptive P = r random SJF : nonpreemptive P = –t chronological/random SRT : preemptive P = –( t–a) chronological/random RR : preemptive P = 0 cyclic ML : preemptive P = e cyclic nonpreemptive P = e chronological n fixed priority levels level P is serviced when n through P+1 empty

8 .Operating Systems 8 Scheduling algorithms MLF (Multilevel Feedback) Like ML, but priority changes dynamically Every process enters at highest level n Each level P prescribes maximum time t P t P increases as P decreases Typically: t n = T ( a constant) t P = 2  t P+1

9 .Operating Systems 9 Scheduling algorithms MLF priority function : depends on level n, and attained time, a P = n– log 2 (a/T+1) derivation is in the book b ut note: there is no need to ever compute P priority is known automatically by position in queue MLF is preemptive : CPU is taken away whenever process exhausts t P Arbitration rule (at highest non-empty level): cyclic (at quantum) or chronological (at t P )

10 .Operating Systems 10 Scheduling Algorithms RM ( Rate Monotonic): Intended for periodic (real-time) processes Preemptive Highest priority : shortest period : P = –d EDF ( Earliest Deadline First ): Intended for periodic (real-time) processes Preemptive Highest priority : shortest time to next deadline: P = –(d – r % d ) derivation r  d number of completed periods r % d time in current period d – r % d time remaining in current period

11 .Operating Systems 11 Comparison of Methods FIFO, SJF, SRT: Primarily for batch systems total length of computation is the same for all FIFO simplest SJF & SRT have better average turnaround times : (r1+r2+…+ rn )/ n Example: Average turnaround times: FIFO: ((0+5 )+( 3+2))/2 = 5.0 SRT: (( 2+5 )+( 0+2))/2 = 4.5 SJF: same as FIFO (p1 arrived first, non-preemptive)

12 .Operating Systems 12 Comparison of Methods Time-sharing systems Response time is critical Use RR or MLF with RR within each queue Choice of quantum determines overhead When q   , RR approaches FIFO When q  0, context switch overhead  100% When q is much greater than context switch overhead, n processes run concurrently at 1/n CPU speed

13 .Operating Systems 13 Comparison of Methods Real-time systems Feasible schedule: All deadlines are met CPU utilization is defined as: U= ∑ t i /d i for all p i If schedule is feasible, U  1 (but not vice versa): EDF always yields feasible schedule if U  1. RM yields feasible schedule if U <0.7 ( approximately), otherwise, it may fail

14 .Operating Systems 14 Comparison of Methods Example p1 has service time 1.5, period 4 p2 has service time 3, period 5 U=(1.5/4) +3/5=.975 < 1 EDF succeeds but RM fails

15 .Operating Systems 15 Priority Inversion Problem Assume priority order p1>p2>p3 p3 enters CS ; p2 preempts p3 ; p1 preempts p2 ; p1 blocks on CS Effect: process p2 , unrelated to p1 and of lower priority , may delay p1 indefinitely. Note: problem is not simply that p3 blocks. This is unavoidable. The problem is that p1 is waiting on p2 . Problem would not occur if p3 in CS had priority greater than p2

16 .Operating Systems 16 Priority Inversion Problem Naïve “solution”: Always run CS at priority of highest process that shares the CS. Problem: p1 cannot interrupt a lower-priority process inside its CS even if p1 is not trying to enter its CS. This is a different form of priority inversion. Better solution: “Dynamic Priority Inheritance”…

17 .Operating Systems 17 Priority Inversion Problem Dynamic Priority Inheritance: When p3 is in its CS and p1 attempts to enter its CS… p3 inherits p1 ’s (higher) priority for the duration of CS Figure 5-11