CSE 120 Principles of Operating Systems Lecture 3 CPU Scheduling October 2 2003 Prof Joe Pasquale Department of Computer Science and Engineering University of California San Diego 2003 by Joseph Pasquale 1 Before We Begin Read Chapter 6 CPU Scheduling Programming Assignment 1 Will be available by midnight Sunday Due in two weeks Sunday October 19 midnight Midterm Tentative date week of October 20 2 The CPU Scheduling Problem We have multiple processes threads but only one CPU How 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 pay Which is the best policy 3 There is No Single Best Policy Depends on the goals of the system Different for your personal computer large time shared computer computer controlling a nuclear power plant Might even have multiple conflicting goals 4 Classifying Schedulers Preemptive vs non preemptive Real time non vs soft vs hard Interactive vs non interactive batch Mixture 5 Scheduling An Example Process 1 2 3 Arrival Time 0 0 0 Service Time 5 3 1 What order minimizes average turnaround time Turnaround time time between arrival and departure arrive wait for CPU waiting time use CPU service time depart 6 Longest First vs Shortest First Longest First P1 P2 P3 0 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 Shortest First P1 P2 P3 0 1 7 Shortest First Is Provably Optimal Given n processes with service times S1 S2 S3 Sn Average Turnaround Time ATT S1 S1 S2 S1 S2 S3 S1 Sn n n S1 n 1 S2 n 2 S3 Sn n S1 has maximum weight n minimize it S2 has next highest weight n 1 minimize it after S1 In general order by shortest to longest 8 Consider Different Arrival Times Process 1 2 3 P1 P2 P3 0 Arrival Time 0 1 3 1 2 3 waiting 4 5 Service Time 5 3 1 6 7 8 9 executing 9 First Come First Served Allocate CPU in the order that processes arrive P1 P2 P3 0 Process 1 2 3 1 2 3 4 5 Departure Time 5 8 9 6 7 8 9 Turnaround Time 5 7 6 Average Turnaround Time 5 7 6 3 6 0 Simple non preemptive poor for short processes 10 Round Robin Time slice CPU give each processes a quantum in turn P1 P2 P3 0 Process 1 2 3 1 2 3 4 5 Departure Time 9 7 4 6 7 8 9 Turnaround Time 9 6 1 Average Turnaround Time 9 6 1 3 5 3 Simple preemptive more overhead than FCFS 11 Shortest Process Next Select process with shortest execution time P1 P2 P3 0 Process 1 2 3 1 2 3 4 5 Departure Time 5 9 6 6 7 8 9 Turnaround Time 5 8 3 Average Turnaround Time 5 8 3 3 5 3 Optimal for non preemptive must know exec times 12 Shortest Remaining Time Select process with shortest remaining time P1 P2 P3 0 Process 1 2 3 1 2 3 4 5 Departure Time 9 5 4 6 7 8 9 Turnaround Time 9 4 1 Average Turnaround Time 9 4 1 3 4 7 Optimal must know execution times 13 Multi Level Feedback Queues Multiple ready queues 0 1 n Always select process in lowestnumbered queue Run selected process for 2i 20 21 22 quantums for queue i If process doesn t block place in 2n next higher queue except last 14 Example using Feedback Queues Select process in lowest numbered queue preemptive if a new process arrives current process goes back to queue it came from P1 P2 P3 0 1 2 3 4 5 6 7 8 Average Turnaround Time 9 5 1 3 5 0 Favors shorter processes over longer dynamic 9 15 Priority Scheduling Select process with highest priority Example P1 medium P2 high P3 low P1 P2 P3 0 1 2 3 4 5 6 7 8 9 Allows scheduling based on arbitrary criteria External e g based on who s willing to pay most Internal e g past CPU usage dynamic 16 Fair Share Proportional Share Processes get predetermined fraction of CPU time Example P1 gets 25 P2 gets 50 P3 gets 25 100 P1 P2 P3 0 1 50 25 40 100 100 67 50 2 33 3 4 5 33 6 43 7 50 8 56 9 Compute ratios of fraction of time used at time 2 P2 P1 100 50 2 1 fair share 17 Computing Fraction of Time Compute fraction Fn of CPU time used up to time n Fn a L 1 a Fn 1 L did process run during last interval 1 yes 0 no a number between 0 and 1 indicates importance of recent CPU usage relative to past large a give more weight to recent usage forget quickly small a give more weight to past usage forget slowly 18 Examples Fn a L 1 a Fn 1 a 1 means ignore the past Fn L a 0 5 recent usage and past equally important Fn 0 5 L 0 5 Fn 1 this is an exponential average typically a 0 2 a 1 n simple average over all intervals Fn 1 n L 1 1 n Fn 1 Fn L F1 F2 F3 Fn 1 n 19 Fair Share using Simple Average a 1 n Fn L F1 F2 F3 Fn 1 n Example P1 gets 25 P2 gets 50 P3 gets 25 100 P1 P2 P3 0 1 50 25 40 100 100 67 50 2 33 3 4 5 33 6 43 7 50 8 56 9 Note n is time intervals since process started 20 Fair Share using Exponential Average a 0 5 Fn 0 5 L 0 5 Fn 1 Example P1 gets 25 P2 gets 50 P3 gets 25 50 P1 P2 P3 0 1 25 13 6 53 50 75 38 19 2 3 4 5 27 6 63 7 82 8 91 9 21
View Full Document
Unlocking...