Page 1 CS162!Operating Systems and!Systems Programming!Lecture 8!CPU Scheduling, Protection Address Spaces"February 14, 2011!Ion Stoica!http://inst.eecs.berkeley.edu/~cs162!Lec 8.2!2/14! Ion Stoica CS162 ©UCB Spring 2011!Review: Last Time"• Scheduling: selecting a waiting process from the ready queue and allocating the CPU to it!• FCFS Scheduling:!– Run threads to completion in order of submission!– Pros: Simple (+)!– Cons: Short jobs get stuck behind long ones (-)!• Round-Robin Scheduling: !– 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 (-)!Lec 8.3!2/14! Ion Stoica CS162 ©UCB Spring 2011!Goals for Today"• Finish discussion of Scheduling!• Kernel vs User Mode!• What is an Address Space?!• How is it Implemented?!Note: Some slides and/or pictures in the following are"adapted from slides ©2005 Silberschatz, Galvin, and Gagne "Lec 8.4!2/14! Ion Stoica CS162 ©UCB Spring 2011!Round-Robin Discussion"• How do you choose time slice?!– 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 long-job throughput:!» Typical time slice today is between 10ms – 100ms!» Typical context-switching overhead is 0.1ms – 1ms!» Roughly 1% overhead due to context-switching!Page 2 Lec 8.5!2/14! Ion Stoica CS162 ©UCB Spring 2011!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#!RR scheduler quantum of 1s#!All jobs start at the same time!• Completion Times:!– Both RR and FCFS finish at the same time!– Average response time is much worse under RR!!» 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!!Job # FIFO RR 1 100 991 2 200 992 … … … 9 900 999 10 1000 1000 Lec 8.6!2/14! Ion Stoica CS162 ©UCB Spring 2011!Quantum!Completion!Time!Wait!Time!Average!P4!P3!P2!P1!Earlier Example with Different Time Quantum"P2![8]!P4![24]!P1![53]!P3![68]!0! 8! 32! 85! 153!Best FCFS:"62!57!85!22!84!Q = 1!104½!112!153!28!125!Q = 20!100½!81!153!30!137!Q = 1!66¼ !88!85!20!72!Q = 20!31¼!8!85!0!32!Best FCFS!121¾!145!68!153!121!Worst FCFS!69½!32!153!8!85!Best FCFS!83½!121!0!145!68!Worst FCFS!95½!80!153!16!133!Q = 8!57¼!56!85!8!80!Q = 8!99½!92!153!18!135!Q = 10!99½!82!153!28!135!Q = 5!61¼!68!85!10!82!Q = 10!61¼!58!85!20!82!Q = 5!P1!0! 8!56!P2! P3! P4! P1! P3! P4! P1! P3! P4! P1! P3! P1! P3! P3!P3!16"24! 32! 40! 48! 64! 72! 80"88! 96!104! 112!P1! P3! P1!120! 128! 133" 141!149!P3!153"Lec 8.7!2/14! Ion Stoica CS162 ©UCB Spring 2011!What if we Knew the Future?"• Could we always mirror best FCFS?!• Shortest Job First (SJF):!– Run whatever job has the least amount of #computation to do!• 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!• These can be applied either to a whole program or the current CPU burst of each program!– 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!Lec 8.8!2/14! Ion Stoica CS162 ©UCB Spring 2011!Discussion"• SJF/SRTF are the best you can do at minimizing average response time!– Provably optimal (SJF among non-preemptive, SRTF among preemptive)!– Since SRTF is always at least as good as SJF, focus on SRTF!• Comparison of SRTF with FCFS and RR!– What if all jobs the same length?!» SRTF becomes the same as FCFS (i.e. FCFS is best can do if all jobs the same length)!– What if jobs have varying length?!» SRTF (and RR): short jobs not stuck behind long ones!Page 3 Lec 8.9!2/14! Ion Stoica CS162 ©UCB Spring 2011!Example to illustrate benefits of SRTF"• Three jobs:!!– 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!• With FIFO:!– Once A or B get in, keep CPU for one week each!• What about RR or SRTF?!– Easier to see with a timeline!C C’s I/O C’s I/O C’s I/O A or B Lec 8.10!2/14! Ion Stoica CS162 ©UCB Spring 2011!RR vs. SRTF"Cʼs "I/O"CABAB…" C"Cʼs "I/O"RR 1ms time slice"Cʼs "I/O"Cʼs "I/O"C"A" B"C"RR 100ms time slice"Cʼs "I/O"A"C"Cʼs "I/O"A"A"SRTF"Disk Utilization:"~90% but lots of wakeups!"Disk Utilization:"90%"Disk Utilization:"9/201 ~ 4.5%"Lec 8.11!2/14! Ion Stoica CS162 ©UCB Spring 2011!SRTF Further discussion"• Starvation!– SRTF can lead to starvation if many small jobs!!– Large jobs never get to run!• 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!– But: even non-malicious users have trouble predicting runtime of their jobs!• Bottom line, canʼt really know how long job will take!– However, can use SRTF as a yardstick #for measuring other policies!– Optimal, so canʼt do any better!• SRTF Pros & Cons!– Optimal (average response time) (+)!– Hard to predict future (-)!– Unfair (-)!Lec 8.12!2/14! Ion Stoica CS162 ©UCB Spring 2011!Multi-Level Feedback Scheduling"• Multiple queues, each with different priority!– Higher priority queues often considered “foreground” tasks!• Each queue has its own scheduling algorithm!– e.g. foreground – RR, background – FCFS!• Adjust each jobʼs priority as follows (details vary)!– 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)!Long-Running
View Full Document
Unlocking...