Review Last Time Scheduling selecting a waiting process from the ready queue and allocating the CPU to it CS162 Operating Systems and Systems Programming Lecture 8 FCFS Scheduling Run threads to completion in order of submission Pros Simple Cons Short jobs get stuck behind long ones CPU Scheduling Protection Address Spaces Round Robin Scheduling February 14 2011 Ion Stoica http inst eecs berkeley edu cs162 Give each thread a small amount of CPU time when it executes cycle between all ready threads Pros Better for short jobs Cons Poor when jobs are same length 2 14 Goals for Today Ion Stoica CS162 UCB Spring 2011 Lec 8 2 Round Robin Discussion How do you choose time slice Finish discussion of Scheduling Kernel vs User Mode What is an Address Space How is it Implemented What if too big Response time suffers What if infinite Get back FIFO 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 echo each keystroke In practice need to balance short job performance and longjob throughput Typical time slice today is between 10ms 100ms Typical context switching overhead is 0 1ms 1ms Roughly 1 overhead due to context switching Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and Gagne 2 14 Ion Stoica CS162 UCB Spring 2011 2 14 Lec 8 3 Page 1 Ion Stoica CS162 UCB Spring 2011 Lec 8 4 Earlier Example with Different Time Quantum Comparisons between FCFS and Round Robin Assuming zero cost context switching time is RR always better than FCFS Simple example 10 jobs each takes 100s of CPU time Completion Times P2 P4 Best FCFS 8 24 0 RR scheduler quantum of 1s All jobs start at the same time Job FIFO RR 1 100 991 2 200 992 9 900 999 10 1000 1000 Bad when all jobs same length Also Cache state must be shared between all jobs with RR but can be devoted to each job with FCFS Total time for RR longer even for zero cost switch Ion Stoica CS162 UCB Spring 2011 32 P3 68 85 153 Quantum P1 P2 P3 P4 Average Best FCFS 32 0 85 8 31 P1 P2 P3 P4 P1 P3 P4 P1 P3 P4 P1 P3 P1 P3 P1 P3 P1 P3 P3 P3 Q 1 84 22 85 57 62 120 128 133 141 149 153 0 8 16 24 32 64 72 20 80 88 96 Q 40 5 48 56 82 85 104 112 58 61 Wait Q 8 80 8 85 56 57 Time Q 10 82 10 85 68 61 Q 20 72 20 85 88 66 Worst FCFS 68 145 0 121 83 Best FCFS 85 8 153 32 69 Q 1 137 30 153 81 100 Q 5 135 28 153 82 99 Completion Q 8 133 16 153 80 95 Time Q 10 135 18 153 92 99 Q 20 125 28 153 112 104 Worst FCFS 121 153 68 145 121 Both RR and FCFS finish at the same time Average response time is much worse under RR 2 14 8 P1 53 2 14 Lec 8 5 What if we Knew the Future Ion Stoica CS162 UCB Spring 2011 Lec 8 6 Discussion Could we always mirror best FCFS Shortest Job First SJF SJF SRTF are the best you can do at minimizing average response time Run whatever job has the least amount of computation to do Provably optimal SJF among non preemptive SRTF among preemptive Since SRTF is always at least as good as SJF focus on SRTF Shortest Remaining Time First SRTF Preemptive version of SJF if job arrives and has a shorter time to completion than the remaining time on the current job immediately preempt CPU Comparison of SRTF with FCFS and RR What if all jobs the same length These can be applied either to a whole program or the current CPU burst of each program SRTF becomes the same as FCFS i e FCFS is best can do if all jobs the same length Idea is to get short jobs out of the system Big effect on short jobs only small effect on long ones Result is better average response time 2 14 Ion Stoica CS162 UCB Spring 2011 What if jobs have varying length SRTF and RR short jobs not stuck behind long ones 2 14 Lec 8 7 Page 2 Ion Stoica CS162 UCB Spring 2011 Lec 8 8 Example to illustrate benefits of SRTF RR vs SRTF C A or B C s I O Three jobs C s I O C C s I O A RR 100ms time slice C s I O CABAB C A B CPU bound each run for a week C I O bound loop 1ms CPU 9ms disk I O If only one at a time C uses 90 of the disk A or B could use 100 of the CPU Once A or B get in keep CPU for one week each C s I O C s I O C A A What about RR or SRTF Easier to see with a timeline Ion Stoica CS162 UCB Spring 2011 Disk Utilization 9 201 C 4 5 DiskC s Utilization 90 but lots of I O wakeups RR 1ms time slice With FIFO 2 14 B C s C s I O I O 2 14 Lec 8 9 Disk Utilization 90 A SRTF Ion Stoica CS162 UCB Spring 2011 Lec 8 10 Multi Level Feedback Scheduling SRTF Further discussion Starvation SRTF can lead to starvation if many small jobs Large jobs never get to run Long Running Compute Tasks Demoted to Low Priority Somehow need to predict future How can we do this Some systems ask the user When you submit a job have to say how long it will take To stop cheating system kills job if takes too long Multiple queues each with different priority Higher priority queues often considered foreground tasks But even non malicious users have trouble predicting runtime of their jobs Each queue has its own scheduling algorithm Bottom line can t really know how long job will take e g foreground RR background FCFS However can use SRTF as a yardstick for measuring other policies Optimal so can t do any better Adjust each job s priority as follows details vary SRTF Pros Cons 2 14 Optimal average response time Hard to predict future Unfair Ion Stoica CS162 UCB Spring 2011 Job starts in highest priority queue If it doesn t finish in its time quantum drop one level If it finishes push up one level or to top 2 14 Lec 8 11 Page 3 Ion Stoica CS162 UCB Spring 2011 Lec 8 12 Scheduling Fairness Lottery Scheduling What about fairness Yet another alternative Lottery Scheduling Strict fixed priority scheduling between queues is unfair run highest then next etc Give each job some number of lottery tickets On each time slice randomly pick a winning ticket On …
View Full Document
Unlocking...