CPSC 410/611: Operating Systems 1 Tutorial: Intro to Scheduling CPU Scheduling!•! Schedulers in the OS!•! Structure of a CPU Scheduler!–! Scheduling = Selection + Dispatching!•! Scheduling Algorithms!–! FIFO/FCFS!–! SPF / SRTF!–! Priority - Based!Schedulers!start!blocked!ready! running!suspended!ready!suspended!blocked!long-term (admission) scheduler!medium-term (memory) scheduler!short-term (CPU) scheduler!CPSC 410/611: Operating Systems 2 Tutorial: Intro to Scheduling Focus: Short-Term Scheduling!•! Recall: Motivation for multiprogramming -- have multiple processes in memory to keep CPU busy.!•! Typical execution profile of a process/thread:!CPU burst wait for I/O CPU burst wait for I/O CPU burst wait for I/O CPU burst start terminate •! CPU scheduler is managing the execution of CPU bursts, represented by processes in ready or running state.!Scheduling Decisions!“Who is going to use the CPU next?!”!ready! running!waiting!3! 1!2!4!Scheduling decision points:!–! 1. The running process changes from running to waiting (current CPU burst of that process is over).!–! 2. The running process terminates.!–! 3. A waiting process becomes ready (new CPU burst of that process begins).!–! 4. The current process switches from running to ready .!non-preemptive preemptiveCPSC 410/611: Operating Systems 3 Tutorial: Intro to Scheduling Structure of a Scheduler!PCB scheduler dispatcher CPU select process start new process ready queue First-Come-First-Served (FCFS/FIFO)!PCB CPU append at the end of queue head tail •! Advantages:!–! very simple!•! Disadvantages:!–! long average and worst-case waiting times!–! poor dynamic behavior (convoy effect)!CPSC 410/611: Operating Systems 4 Tutorial: Intro to Scheduling (Fixed) Priority Scheduling!•! Whenever CPU is idle, picks process with highest priority.!•! Priority:!–! process class, urgency, pocket depth.!•! Unbounded blocking: Starvation!–! Increase priority over time: aging!CPU high priority low priority Selector (compare priorities) Selector!(compare priorities)!•! Conceptually low priority!high priority!•! Priority Queues Selector!(compare priorities)!q=f(p)!priority queue!priority!CPU! CPU!low priority!high priority!CPSC 410/611: Operating Systems 5 Tutorial: Intro to Scheduling Round-Robin!•! FIFO with preemption after time quantum!•! Method for time sharing!•! Choice of time quantum:!–! large: FCFS!–! small: Processor sharing!•! Time quantum also defines context-switching overhead!CPU!terminate!end of!time quantum!FIFO queue!Selector!(compare priorities)!low priority!high priority!Multilevel Feedback Queue Scheduling!FCFS (quantum = infinity)!quantum = 16 ms!quantum = 2 ms!quantum =