Chapter 5.1: CPU SchedulingChapter 5: CPU SchedulingBasic ConceptsSlide 4CPU and I/O BurstsHistogram of CPU-burst TimesCPU Scheduler (short-term scheduler)Preemptive / Non-preemptive SchedulingPreemptive / Non-Premptive Scheduling - moreProblems in Preemptive SchedulingDispatcherScheduling Criteria - MetricsOptimization CriteriaFirst-Come, First-Served (FCFS) SchedulingFCFS Scheduling (Cont.)Shortest-Job-First (SJF) SchedulingExample of Non-Preemptive SJFExample of Preemptive SJFDetermining Length of Next CPU BurstPriority SchedulingPriority Scheduling - MoreRound Robin (RR)Round Robin Process Scheduling - moreExample of RR with Time Quantum = 20 msecTime Quantum and Context Switch TimeTime Quantum and Turnaround Time - VariesMultilevel QueueMultilevel Queue SchedulingMultilevel Feedback QueueExample of Multilevel Feedback QueueMultilevel Feedback QueuesEnd of Chapter 5.1Chapter 5.1: CPU SchedulingChapter 5.1: CPU Scheduling5.2Silberschatz, Galvin and Gagne ©2005Operating System ConceptsChapter 5: CPU SchedulingChapter 5: CPU SchedulingChapter 5.1Basic ConceptsScheduling Criteria Scheduling AlgorithmsChapter 5.2Multiple-Processor SchedulingReal-Time SchedulingThread SchedulingOperating Systems ExamplesJava Thread SchedulingAlgorithm Evaluation5.3Silberschatz, Galvin and Gagne ©2005Operating System ConceptsBasic ConceptsBasic ConceptsThe goal of multiprogramming is to maximize CPU utilization - constrained by other needs too.So, we speak of CPU scheduling…We want to keep that CPU computing! How do we keep this expensive resource chugging!This means we look at the way the CPU is dispatched to processes. Equivalently, then, we need to look at the scheduling algorithms.We will speak of process scheduling in discussing ‘general’ issues and thread scheduling when we speak of issues directly related to threads only.We know that in a single processor system, only a single process can execute at any instant in time;That is, a single instruction from a single process can execute at any instant in time.When the CPU must wait for some other event, it is idle.In most instances (there are exceptions), this practice is to be avoided!We want to keep this resource busy rather than let it set idle!5.4Silberschatz, Galvin and Gagne ©2005Operating System ConceptsBasic ConceptsBasic ConceptsNormally a process continues executing until it issues a system call like for a read or write, … or the process is interrupted for maybe the timer or other reason by the operating system.Once a system call is issued, we normally do NOT want the processor to wait for system call completion. Rather than have the CPU wait, we want to dispatch the CPU to another ‘ready’ process.This switching of context - is central to the smooth running of a computing environment!5.5Silberschatz, Galvin and Gagne ©2005Operating System ConceptsCPU and I/O BurstsCPU and I/O BurstsReality is that many processes have repeating cycles of what are called ‘cpu bursts’ where computing is taking place, followed by ‘I/O bursts’ where an I/O operation occurs.Typically, CPU bursts are very short-lived (since computers process so quickly) while an I/O request is made.“CPU-bound processes” may have a few long CPU bursts with less frequent I/O bursts, while an “I/O bound process” may have many short CPU-bursts but a much higher number of I/O bursts.5.6Silberschatz, Galvin and Gagne ©2005Operating System ConceptsHistogram of CPU-burst TimesHistogram of CPU-burst TimesLonger and more frequent CPU bursts characterize scientific, engineering applications where shorter CPU bursts and much more frequent I/O bursts characterize business and commercial applications.Relate to file / database processing vis a vis computationally-intense processing.5.7Silberschatz, Galvin and Gagne ©2005Operating System ConceptsCPU Scheduler (short-term scheduler)CPU Scheduler (short-term scheduler)This scheduler selects from among processes in memory ready to execute, and allocates the CPU to one of them.“Ready” means that these processes can use the CPU immediately! They are not waiting on an I/O or a keyboard input or some kind of transmission!Selection is not necessarily accessing a FIFO queue, as there are a number of scheduling algorithms (fifo, priority, tree, unordered linked list, and more) These queues consist of the PCBs representing processes.These PCBs are linked up in various ways: links, ordered array, etc. as we shall see.CPU scheduling decisions may take place when a process:1. Switches from running to waiting state (like after process or thread issues a system call)2. Switches from running to ready state (like after a timer interrupt or other interrupt)3. Switches from waiting to ready state (like when an I/O is completed; process is ‘made’ ready to resume)4. A Process terminatesNow let’s look at ‘how’ this scheduling takes place:5.8Silberschatz, Galvin and Gagne ©2005Operating System ConceptsPreemptive / Non-preemptive SchedulingPreemptive / Non-preemptive SchedulingChanging from running state to wait state – non-preemptiveOften occurs due to an I/O request from the running process, orInvocation of a ‘wait’ for termination of a child process (threads)Process currently undergoing execution is not interrupted (preempted)!Changing state from running to ready state – preemptiveMay occur as a result of an interrupt. Running process is cut off and moves from ‘running’ to ‘ready.’Changing state from wait state to a ready state – preemptiveMay occur once an I/O has been completed Process in wait state may now be ‘rescheduled’ (thus moved to ‘ready’ state.Changing state because process terminates – non-preemptive.This is clear.5.9Silberschatz, Galvin and Gagne ©2005Operating System ConceptsPreemptive / Non-Premptive Scheduling - morePreemptive / Non-Premptive Scheduling - moreIn non-preemptive scheduling, once a process receives the CPU, this process / thread continues until it releases the CPU (I/O, switch to wait, timer, terminates…) It cannot be ‘bumped.’Most newer operating systems use preemptive scheduling.Preemptive scheduling requires additional hardware – a timer that keeps track of how long a process receives CPU cycles.So, non-preemptive (cooperative) scheduling can be used on all hardware configuration;