COS 318: Operating Systems CPU Scheduling (http://www.cs.princeton.edu/courses/cos318/)2 Today’s Topics CPU scheduling basics CPU Scheduling algorithmsWhen to Schedule? Process/thread creation Process/thread exit Blocking on I/O or synchronization I/O interrupt Clock interrupt (pre-emptive scheduling) 34 Preemptive vs. Non-Preemptive Scheduling Preemptive scheduling Running ⇒ ready Blocked ⇒ ready Running ⇒ blocked Terminate Non-preemptive scheduling Running ⇒ blocked Terminate Batch vs interactive vs real-time Running Blocked Ready Resource free, I/O completion interrupt (move to ready queue) Create Terminate (call scheduler) Yield, Interrupt (call scheduler) Block for resource (call scheduler) Scheduler dispatch ExitedScheduling Criteria Assumptions One program per user and one thread per program Programs are independent Goals for batch and interactive systems Provide fairness Everyone makes some progress; no one starves Maximize CPU utilization • Not including idle process Maximize throughput • Operations/second (min overhead, max resource utilization) Minimize turnaround time • Batch jobs: time to execute (from submission to completion) Shorten response time • Interactive jobs: time response (e.g. typing on a keyboard) Proportionality • Meets user’s expectationsScheduling Criteria Questions: What are the goals for PCs versus servers? Average response time vs. throughput Average response time vs. fairness7 Problem Cases Completely blind about job types No CPU and I/O overlap. Optimization involves favoring jobs of type “A” over “B” Lots of A’s? B’s starve. Interactive process trapped behind others Response time bad for no good reason. Priorities: A depends on B and A’s priority > B’s B never runs.Scheduling Algorithms Simplified view of scheduling: Save process state (to PCB) Pick which process to run next Dispatch process 8First-Come-First-Serve (FCFS) Policy What does it mean? Run to completion (old days) Run until blocked or yields Example 1 P1 = 24sec, P2 = 3sec, and P3 = 3sec, submitted together Average response time = (24 + 27 + 30) / 3 = 27 Example 2 Same jobs but come in different order: P2, P3 and P1 Average response time = (3 + 6 + 30) / 3 = 13 P1 P2 P3 P2 P3 P1 (Gantt Graph)STCF and SRTCF Shortest Time to Completion First Non-preemptive Shortest Remaining Time to Completion First Preemptive version Example P1 = 6sec, P2 = 8sec, P3 = 7sec, P4 = 3sec All arrive at the same time Can you do better than SRTCF in terms of average response time? Issues with this approach? P1 P2 P3 P4Round Robin Similar to FCFS, but add a time slice for timer interrupt FCFS for preemptive scheduling Real systems also have I/O interrupts in the mix How do you choose time slice? Current processFCFS vs. Round Robin Example 10 jobs and each takes 100 seconds FCFS (non-preemptive scheduling) job 1: 100s, job2: 200s, ... , job10: 1000s Round Robin (preemptive scheduling) time slice 1sec and no overhead job1: 991s, job2: 992s, ... , job10: 1000s Comparisons Round robin is much worse (turnaround time) for jobs about the same length Round robin is better for short jobsResource Utilization Example A, B, and C run forever (in this order) A and B each uses 100% CPU forever C is a CPU plus I/O job (1ms CPU + 10ms disk I/O) Time slice 100ms A (100ms CPU), B (100ms CPU), C (1ms CPU + 10ms I/O), … Time slice 1ms A (1ms CPU), B (1ms CPU), C (1ms CPU), A (1ms CPU), B (1ms CPU), C(10ms I/O) || A, B, …, A, B What do we learn from this example?14 Virtual Round Robin Aux queue is FIFO I/O bound processes go to aux queue (instead of ready queue) to get scheduled Aux queue has preference over ready queue CPU Admit Timeout Dispatch I/O wait I/O wait I/O wait Aux queue I/O completion15 Priority Scheduling Obvious Not all processes are equal, so rank them The method Assign each process a priority Run the process with highest priority in the ready queue first Adjust priority dynamically (I/O wait raises the priority, reduce priority as process runs) Why adjusting priorities dynamically T1 at priority 4, T2 at priority 1 and T2 holds lock L Scenario • T1 tries to acquire L, fails, blocks. • T3 enters system at priority 3. • T2 never gets to run!Multiple Queues Jobs start at highest priority queue If timeout expires, drop one level If timeout doesn’t expires, stay or pushup one level What does this method do? Priority 4 3 2 1 Time slices 1 2 4 8Lottery Scheduling Motivations SRTCF does well with average response time, but unfair Lottery method Give each job a number of tickets Randomly pick a winning tickets To approximate SRTCF, give short jobs more tickets To avoid starvation, give each job at least one ticket Cooperative processes can exchange tickets Question How do you compare this method with priority scheduling?18 Multiprocessor and Cluster Multiprocessor architecture Cache coherence Single OS Cluster or multicomputer Distributed memory An OS in each box … CPU L1 $ L2 $ CPU L1 $ L2 $ … Memory Network19 Multiprocessor/Cluster Scheduling Design issue Process/thread to processor assignment Gang scheduling (co-scheduling) Threads of the same process will run together Processes of the same application run together Dedicated processor assignment Threads will be running on specific processors to completion Is this a good idea?20 Real-Time Scheduling Two types of real-time Hard deadline • Must meet, otherwise can cause fatal error Soft Deadline • Meet most of the time, but not mandatory Admission control Take a real-time process only if the system can
View Full Document