CSE 120 Principles of Operating Systems Lecture 3 Scheduling January 18 2006 Prof Joe Pasquale Department of Computer Science and Engineering University of California San Diego 2006 by Joseph Pasquale 1 Before 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 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 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 5 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 6 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 7 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 8 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 9 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 10 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 11 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 12 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 next higher queue except last 2n 13 Example using Feedback Queues 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 9 Average Turnaround Time 9 5 1 3 5 0 Favors shorter processes over longer dynamic 14 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 15 Fair Share Proportional Share 100 P1 P2 P3 50 33 25 40 100 100 67 50 33 43 50 56 100 0 1 2 3 4 5 6 7 8 9 Processes get predetermined fraction of CPU time Example 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 get 16 Computing Ratios for Fair Share Determine utilization fraction of CPU time received Compute 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 FS Example P1 Utilization 40 Promised 25 Ratio 40 25 1 6 P2 40 50 40 50 0 8 P3 15 25 15 25 0 6 Process with lowest ratio needs CPU most schedule it 17 Example of Fair Share Scheduling 100 P1 P2 P3 Time 50 33 25 40 100 100 67 50 33 43 50 56 100 0 1 2 3 4 P3 5 6 7 8 9 P1 P2 Action 1 100 25 0 50 2 50 25 100 50 3 33 25 100 50 4 25 25 67 50 P3 done schedule P1 5 40 25 50 50 schedule P2 P2 smallest schedule P2 tie schedule either 0 25 schedule P3 18 Calculating Exponential Averages Exponential 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 history Example for P1 utilization 0 25 assume A0 5 Mi Ai True 1 63 1 0 47 50 0 35 33 0 26 25 1 45 40 0 34 33 1 50 45 19 Real Time Scheduling Correctness of real time systems depend on logical result of computations the timing of these results Type of real time systems Hard vs soft real time Periodic vs aperiodic Scheduling Earliest deadline Rate monotonic scheduling 20 Periodic Processes or Tasks P1 P2 0 1 2 3 4 5 6 7 8 9 10 11 12 Periodic processes perform computation at certain rate C compute time T period U C T utilization Can processes be ordered so that deadlines are met Should P1 run before or after P2 21 Periodic Processes or Tasks P1 P2 0 1 2 3 4 5 6 Example C T U P1 P2 15 10 30 20 50 50 7 8 9 10 11 12 Sum of utilizations does not exceed 100 P1 running before P2 causes P2 to miss all deadlines 22 Periodic Processes P1 P2 0 1 2 3 4 5 6 Example C T U P1 P2 15 10 30 20 50 50 7 8 9 10 11 12 Sum of utilizations does not exceed 100 P2 before P1 causes P2 to miss three deadlines 23 Earliest Deadline P1 P2 P3 0 1 2 3 4 5 6 7 8 9 10 11 12 Schedule the process that has the earliest deadline …
View Full Document
Unlocking...