Goals for Today Scheduling Policy goals Policy Options Implementation Considerations CS162 Operating Systems and Systems Programming Lecture 10 Thread Scheduling March 3 2008 Prof Anthony D Joseph http inst eecs berkeley edu cs162 Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and Gagne Gagne Many slides generated from my lecture notes by Kubiatowicz 3 3 08 Joseph CS162 UCB Spring 2008 CPU Scheduling Lec 10 2 Scheduling Assumptions CPU scheduling big area of research in early 70 s Many implicit assumptions for CPU scheduling One program per user One thread per program Programs are independent Clearly these are unrealistic but they simplify the problem so it can be solved For instance is fair about fairness among users or programs Earlier we talked about the life cycle of a thread If I run one compilation job and you run five you get five times as much CPU on many operating systems Active threads work their way from Ready queue to Running to various waiting queues The high level goal Dole out CPU time to optimize some desired parameters of system Question How is the OS to decide which of several tasks to take off a queue Obvious queue to worry about is ready queue Others can be scheduled as well however USER1 Scheduling deciding which threads are given access to resources from moment to moment 3 3 08 Joseph CS162 UCB Spring 2008 USER2 USER3 USER1 USER2 Time 3 3 08 Lec 10 3 Page 1 Joseph CS162 UCB Spring 2008 Lec 10 4 Assumption CPU Bursts Scheduling Policy Goals Criteria Minimize Response Time Minimize elapsed time to do an operation or job Response time is what the user sees Weighted toward small bursts Time to echo a keystroke in editor Time to compile a program Real time Tasks Must meet deadlines imposed by World Maximize Throughput Maximize operations or jobs per second Throughput related to response time but not identical Minimizing response time will lead to more context switching than if you only maximized throughput Execution model programs alternate between bursts of CPU and I O Two parts to maximizing throughput Minimize overhead for example context switching Efficient use of resources CPU disk memory etc Program typically uses the CPU for some period of time then does I O then uses CPU again Each scheduling decision is about which job to give to the CPU for use by its next CPU burst With timeslicing thread may be forced to give up CPU before finishing current CPU burst 3 3 08 Joseph CS162 UCB Spring 2008 Fairness Share CPU among users in some equitable way Fairness is not minimizing average response time 3 3 08 Lec 10 5 Suppose that processes arrive in order P2 P3 P1 Now the Gantt chart for the schedule is In early systems FCFS meant one program scheduled until done including I O Now means keep CPU until thread blocks Example Process Burst Time P1 24 P2 3 P3 3 P2 0 0 24 30 FIFO Pros and Cons 30 Simple Short jobs get stuck behind long ones Convoy effect short process behind long process Joseph CS162 UCB Spring 2008 6 average waiting time is much better before it was 17 Average completion time is better before it was 27 Waiting time for P1 0 P2 24 P3 27 Average waiting time 0 24 27 3 17 Average Completion time 24 27 30 3 27 3 3 08 3 P1 In second case P3 27 P3 Waiting time for P1 6 P2 0 P3 3 Average waiting time 6 0 3 3 3 Average Completion time 3 6 30 3 13 Suppose processes arrive in the order P1 P2 P3 The Gantt Chart for the schedule is P2 Lec 10 6 Example continued Also First In First Out FIFO or Run until done P1 Joseph CS162 UCB Spring 2008 FCFS Scheduling Cont First Come First Served FCFS Scheduling First Come First Served FCFS Better average response time by making system less fair 3 3 08 Lec 10 7 Page 2 Safeway Getting milk always stuck behind cart full of small items Upside get to read about space aliens Joseph CS162 UCB Spring 2008 Lec 10 8 Administrivia Administrivia Midterm 1 Mean 73 2 Std dev 12 8 30 0 35 0 35 0 40 0 40 0 45 0 45 0 50 0 55 0 60 0 65 0 70 0 75 0 80 0 85 0 90 0 3 3 08 50 0 55 0 60 0 65 0 70 0 75 0 80 0 85 0 90 0 95 0 Course resources Staff office hours Peer tutoring contact hkn eecs 1 1 1 0 5 11 9 7 13 19 22 11 7 Project 1 code due tonight Conserve your slip days It s not worth it yet Joseph CS162 UCB Spring 2008 Group Participation Required Group evaluations with TA oversight used in computing grades Zero sum game 3 3 08 Lec 10 9 Round Robin RR FCFS Scheme Potentially bad for short jobs Example Round Robin Scheme Burst Time 53 8 68 24 P1 P2 P3 P4 P1 0 P2 20 P3 28 P4 48 P1 68 P3 88 108 P4 P1 P3 P3 112 125 145 153 Waiting time for P1 68 20 112 88 72 P2 20 0 20 P3 28 0 88 48 125 108 85 P4 48 0 108 68 88 Average waiting time 72 20 85 88 4 66 Average completion time 125 28 153 112 4 104 Each process gets 1 n of the CPU time In chunks of at most q time units No process waits more than n 1 q time units Performance q large FCFS q small Interleaved really small hyperthreading q must be large with respect to context switch Joseph CS162 UCB Spring 2008 Process The Gantt chart is Each process gets a small unit of CPU time time quantum usually 10 100 milliseconds After quantum expires the process is preempted and added to the end of the ready queue n processes in ready queue and time quantum is q 3 3 08 Lec 10 10 Example of RR with Time Quantum 20 Depends on submit order If you are first in line at supermarket with milk you don t care who is behind you on the other hand otherwise overhead is too high all overhead Joseph CS162 UCB Spring 2008 Thus Round Robin Pros and Cons Better for short jobs Fair Context switching time adds up for long jobs 3 3 08 Lec 10 11 Page 3 Joseph CS162 UCB Spring 2008 Lec 10 12 Round Robin Discussion Comparisons between FCFS and Round Robin Assuming zero cost context switching time is RR always better than FCFS Simple example 10 jobs each take 100s of CPU time How do you choose time slice What if too big Response time suffers What if infinite Get back FIFO Completion Times What if time slice too small Throughput suffers Actual choices of timeslice Initially UNIX timeslice one second Worked ok when UNIX was used by one or two people What if three compilations going on 3 seconds to …
View Full Document
Unlocking...