1Lecture 3SchedulingJanuary 18, 2006Prof. Joe PasqualeDepartment of Computer Science and EngineeringUniversity of California, San Diego© 2006 by Joseph PasqualeCSE 120: Principles of Operating Systems2Before We Begin …Read Chapter 5 (CPU Scheduling)Programming Assignment 2• Due Friday, January 27 (midnight)Homework Assignments• Hwk 1 due on Sunday, January 22 (midnight)• Hwk 2 due on Sunday, January 29 (midnight)3The CPU Scheduling ProblemWe have multiple processes/threads, but only one CPUHow much time does each process/thread get on CPU?Possibilities• Keep it till done• Each uses it a bit and passes it on• Each gets proportional to what they payWhich is the best policy?4There is No Single Best PolicyDepends on the goals of the systemDifferent for• your personal computer• large time-shared computer• computer controlling a nuclear power plantMight even have multiple (conflicting) goals5Scheduling: An ExampleProcess Arrival Time Service Time1 0 52 0 33 0 1What order minimizes average turnaround time?Turnaround time: time between arrival and departure• Arrive, wait for CPU (waiting time)• Use CPU (service time), depart6P1P2P30 1 2 3 4 5 6 7 8 9Longest First vs. Shortest FirstLongest FirstShortest FirstP1P2P30 1 2 3 4 5 6 7 8 97Shortest First Is Provably OptimalGiven n processes with service times S1, S2, S3, … , SnAverage Turnaround Time (ATT)= [S1 + (S1 + S2) + (S1 + S2 + S3) + … + (S1 + … + Sn)] / n= [(n × S1) + ((n-1) × S2) + ((n-2) × S3) + … + Sn] / nS1 has maximum weight (n), minimize itS2 has next-highest weight (n-1), minimize it after S1In general: order by shortest to longest8P1P2P301 2 3 4 5 6 7 8 9waiting executingConsider Different Arrival TimesProcess Arrival Time Service Time1 0 52 1 33 3 19First-Come First-ServedAllocate CPU in the order that processes arriveProcess Departure Time Turnaround Time1 5 52 8 73 9 6Average Turnaround Time = (5 + 7 + 6)/3 = 6.0Simple, non-preemptive, poor for short processesP1P2P301 2 3 4 5 6 7 8 910Round RobinTime-slice CPU: give each processes a quantum in turnProcess Departure Time Turnaround Time1 9 92 7 63 4 1Average Turnaround Time = (9 + 6 + 1)/3 = 5.3Simple, preemptive, more overhead than FCFSP1P2P301 2 3 4 5 6 7 8 911Shortest Process NextSelect process with shortest execution timeProcess Departure Time Turnaround Time1 5 52 9 83 6 3Average Turnaround Time = (5 + 8 + 3)/3 = 5.3Optimal for non-preemptive, must know exec timesP1P2P301 2 3 4 5 6 7 8 912Shortest Remaining TimeSelect process with shortest remaining timeProcess Departure Time Turnaround Time1 9 92 5 43 4 1Average Turnaround Time = (9 + 4 + 1)/3 = 4.7Optimal, must know execution timesP1P2P301 2 3 4 5 6 7 8 913…2021222nMulti-Level Feedback QueuesMultiple ready queues 0, 1, …, nAlways select process in lowest-numbered queueRun selected process for 2iquantums (for queue i)If process doesn’t block, place innext higher queue (except last)14Example using Feedback QueuesPreemptive: if a new process arrives, current processgoes back to queue it came fromAverage Turnaround Time = (9 + 5 + 1)/3 = 5.0Favors shorter processes over longer, dynamicP1P2P301 2 3 4 5 6 7 8 915Priority SchedulingSelect process with highest priorityExample: P1 = medium, P2 = high, P3 = lowAllows scheduling based on arbitrary criteria• External, e.g., based on who’s willing to pay most• Internal, e.g., past CPU usage (dynamic)P1P2P30 1 2 3 4 5 6 7 8 916Fair Share (Proportional Share)Processes get predetermined fraction of CPU timeExample: P1 to get 25%, P2 to get 50%, P3 to get 25%Each quantum, which process got least of its fair share?What is fair share? Getting what you’re supposed to getP1P2P30 1 2 3 4 5 6 7 8 9100% 50%100%33%100% 67%25% 40%50%33% 43% 50% 56%100%17Computing Ratios for Fair ShareDetermine utilization: fraction of CPU time receivedCompute ratio: utilization to fraction promised• If ratio < 1, process getting less than its FS• If ratio > 1, process getting more than its FS• If ratio == 1, process getting exactly its FSExample P1P2P3• Utilization 40% 40% 15%• Promised 25% 50% 25%• Ratio 40/25=1.6 40/50=0.8 15/25=0.6Process with lowest ratio needs CPU most: schedule it18Example of Fair Share SchedulingTime P1P2P3Action1 100/25 0/50 P2 smallest, schedule P22 50/25 100/50 tie, schedule either3 33/25 100/50 0/25 schedule P34 25/25 67/50 P3 done, schedule P15 40/25 50/50 schedule P2P1P2P30 1 2 3 4 5 6 7 8 9100% 50%100%33%100% 67%25% 40%50%33% 43% 50% 56%100%19Calculating Exponential AveragesExponential average: Ai+1 = α Mi + (1 - α) Ai• Ai = exponential average at time i• Mi = measurement at time i• α = weight (0 - 1) on recent vs. past history– large α emphasizes recent history– small α emphasizes past historyExample for P1 utilization (α = 0.25, assume A0 = .5)• Mi: 1 0 0 0 1 0 1• Ai: .63 .47 .35 .26 .45 .34 .50• True: 1 .50 .33 .25 .40 .33 .4520Real Time SchedulingCorrectness of real-time systems depend on• logical result of computations• the timing of these resultsType of real-time systems• Hard vs. soft real-time• Periodic vs. aperiodicScheduling• Earliest deadline• Rate monotonic scheduling21P1P20 1 2 3 4 5 6 7 8 9 10 11 12Periodic Processes (or Tasks)Periodic processes: perform computation at certain rateC = compute time, T = period, U = C/T = utilizationCan processes be ordered so that deadlines are met?• Should P1 run before or after P2?22P1P20 1 2 3 4 5 6 7 8 9 10 11 12Periodic Processes (or Tasks)Example C T UP115 30 50%P210 20 50%Sum of utilizations does not exceed 100%P1 running before P2 causes P2 to miss all deadlines!23P1P20 1 2 3 4 5 6 7 8 9 10 11 12Periodic ProcessesExample C T UP115 30 50%P210 20 50%Sum of utilizations does not exceed 100%P2 before P1 causes P2 to miss three deadlines24P1P2P30 1 2 3 4 5 6 7 8 9 10 11 12Earliest DeadlineSchedule the process that has the earliest deadlineRequires sorting of deadlines, O(n log n) complexityAlso works for aperiodic processes25P1P2P30 1 2 3 4 5 6 7 8 9 10 11 12Earliest DeadlineExample: C T UP130 60 50%P210 40 25%P37.5 30 25%Meets all deadlines (sum of utilizations = 100%)26P1P2P30 1 2 3 4 5 6 7 8 9 10 11 12Rate Monotonic SchedulingPrioritize based on rates (rate = 1/period) - no sorting!Deadlines guaranteed met if:U1 + U2 + … + Un ≤ n (21/n - 1)Limited to periodic processes27P1P2P30 1 2 3 4 5 6 7 8 9 10 11 12Rate Monotonic SchedulingExample: C T U RateP130 60 50% 1/60 = 0.017P210 40 25% 1/40 = 0.025P37.5 30 25% 1/30 =
View Full Document
Unlocking...