Page 1CS162Operating Systems andSystems ProgrammingLecture 10Thread SchedulingMarch 3, 2008Prof. Anthony D. Josephhttp://inst.eecs.berkeley.edu/~cs162Lec 10.23/3/08 Joseph CS162 ©UCB Spring 2008Goals for Today• Scheduling Policy goals• Policy Options• Implementation ConsiderationsNote: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne Note: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne. Many slides generated from my lecture notes by Kubiatowicz.Lec 10.33/3/08 Joseph CS162 ©UCB Spring 2008CPU Scheduling• Earlier, we talked about the life-cycle of a thread– Active threads work their way from Ready queue to Running to various waiting queues.• 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• Scheduling: deciding which threads are given access to resources from moment to moment Lec 10.43/3/08 Joseph CS162 ©UCB Spring 2008Scheduling 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? » If I run one compilation job and you run five, you get five times as much CPU on many operating systems• The high-level goal: Dole out CPU time to optimize some desired parameters of systemUSER1 USER2 USER3 USER1 USER2TimePage 2Lec 10.53/3/08 Joseph CS162 ©UCB Spring 2008Assumption: CPU Bursts• Execution model: programs alternate between bursts of CPU and I/O– 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 burstWeighted toward small burstsLec 10.63/3/08 Joseph CS162 ©UCB Spring 2008Scheduling Policy Goals/Criteria• Minimize Response Time– Minimize elapsed time to do an operation (or job)– Response time is what the user sees:» 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– Two parts to maximizing throughput» Minimize overhead (for example, context-switching)» Efficient use of resources (CPU, disk, memory, etc)• Fairness– Share CPU among users in some equitable way– Fairness is not minimizing average response time:» Better averageresponse time by making system lessfairLec 10.73/3/08 Joseph CS162 ©UCB Spring 2008First-Come, First-Served (FCFS) Scheduling• First-Come, First-Served (FCFS)– Also ―First In, First Out‖ (FIFO) or ―Run until done‖» In early systems, FCFS meant one program scheduled until done (including I/O)» Now, means keep CPU until thread blocks • Example: Process Burst TimeP124P23P33– Suppose processes arrive in the order: P1, P2, P3 The Gantt Chart for the schedule is:– 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•Convoy effect:short process behind long processP1P2P324 27 300Lec 10.83/3/08 Joseph CS162 ©UCB Spring 2008FCFS Scheduling (Cont.)• Example continued:– Suppose that processes arrive in order: P2, P3, P1Now, the Gantt chart for the schedule is:– 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• In second case:– average waiting time is much better (before it was 17)– Average completion time is better (before it was 27) • FIFO Pros and Cons:– Simple (+)– Short jobs get stuck behind long ones (-)» Safeway: Getting milk, always stuck behind cart full of small items. Upside: get to read about space aliens!P1P3P263 300Page 3Lec 10.93/3/08 Joseph CS162 ©UCB Spring 2008Administrivia• Midterm #1– Mean 73.2, Std dev 12.8•30.0 - 35.0: 1 *•35.0 - 40.0: 1 *•40.0 - 45.0: 1 *• 45.0 - 50.0: 0 • 50.0 - 55.0: 5 *****• 55.0 - 60.0: 11 **********• 60.0 - 65.0: 9 *********• 65.0 - 70.0: 7 *******• 70.0 - 75.0: 13 ************• 75.0 - 80.0: 19 ******************• 80.0 - 85.0: 22 ********************• 85.0 - 90.0: 11 **********• 90.0 - 95.0: 7 *******Lec 10.103/3/08 Joseph CS162 ©UCB Spring 2008Administrivia• Course resources– Staff office hours– Peer tutoring (contact hkn@eecs)• Project 1 code due tonight– Conserve your slip days!!! – It’s not worth it yet• Group Participation: Required!– Group evaluations (with TA oversight) used in computing grades– Zero-sum game!Lec 10.113/3/08 Joseph CS162 ©UCB Spring 2008Round Robin (RR)• FCFS Scheme: Potentially bad for short jobs!– 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…• Round Robin Scheme– 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.–nprocesses in ready queue and time quantum is q » Each process gets 1/nof the CPU time » In chunks of at most qtime units » No process waits more than (n-1)q time units• Performance–qlarge FCFS–q small Interleaved (really small hyperthreading?)–q must be large with respect to context switch, otherwise overhead is too high (all overhead)Lec 10.123/3/08 Joseph CS162 ©UCB Spring 2008Example of RR with Time Quantum = 20• Example: Process Burst TimeP153P28P368P424– The Gantt chart is:– Waiting time for P1=(68-20)+(112-88)=72P2=(20-0)=20P3=(28-0)+(88-48)+(125-108)=85P4=(48-0)+(108-68)=88– Average waiting time = (72+20+85+88)/4=66¼– Average completion time = (125+28+153+112)/4 = 104½• Thus, Round-Robin Pros and Cons:– Better for short jobs, Fair (+)– Context-switching time adds up for long jobs (-)P1P2P3P4P1P3P4P1P3P30 20 28 48 68 88
View Full Document
Unlocking...