ICS 143 - Principles of Operating SystemsOutlineScheduling ObjectivesProgram Behavior IssuesBasic ConceptsCPU Burst DistributionLevels of SchedulingLevels of Scheduling(cont.)CPU SchedulerCPU Scheduling DecisionsCPU scheduling decisionsDispatcherScheduling CriteriaScheduling Criteria (cont.)Optimization CriteriaFirst Come First Serve (FCFS) SchedulingFirst-Come, First-Served(FCFS) SchedulingFCFS Scheduling (cont.)Shortest-Job-First(SJF) SchedulingNon-Preemptive SJF SchedulingPreemptive SJF Scheduling(SRTF)Determining Length of Next CPU BurstExponential Averaging(cont.)Priority SchedulingPriority Scheduling (cont.)Round Robin (RR)Round Robin ExampleMultilevel QueueMultilevel QueuesMultilevel Feedback QueueMultilevel Feedback QueuesSlide 32Multiple-Processor SchedulingReal-Time SchedulingIssues in Real-time SchedulingReal-time Scheduling - Dispatch LatencyAlgorithm EvaluationPrinciples of Operating Systems - CPU Scheduling 1ICS 143 - Principles of Operating SystemsLecture 5 - CPU SchedulingProf. Dmitri V. Kalashnikovdvk (@) ics.uci.eduSlides © Prof. Nalini Venkatasubramanian.Principles of Operating Systems - CPU Scheduling 2OutlineScheduling ObjectivesLevels of SchedulingScheduling CriteriaScheduling AlgorithmsFCFS, Shortest Job First, Priority, Round Robin, MultilevelMultiple Processor SchedulingReal-time SchedulingAlgorithm EvaluationPrinciples of Operating Systems - CPU Scheduling 3Scheduling ObjectivesEnforcement of fairness •in allocating resources to processesEnforcement of prioritiesMake best use of available system resourcesGive preference to processes holding key resources.Give preference to processes exhibiting good behavior.Degrade gracefully under heavy loads.Principles of Operating Systems - CPU Scheduling 4Program Behavior IssuesI/O boundednessshort burst of CPU before blocking for I/OCPU boundednessextensive use of CPU before blocking for I/OUrgency and PrioritiesFrequency of preemptionProcess execution timeTime sharing amount of execution time process has already received.Principles of Operating Systems - CPU Scheduling 5Basic ConceptsMaximum CPU utilization obtained with multiprogramming.CPU-I/O Burst CycleProcess execution consists of a cycle of CPU execution and I/O wait.Principles of Operating Systems - CPU Scheduling 6CPU Burst DistributionPrinciples of Operating Systems - CPU Scheduling 7Levels of SchedulingHigh Level Scheduling or Job SchedulingSelects jobs allowed to compete for CPU and other system resources.Intermediate Level Scheduling or Medium Term SchedulingSelects which jobs to temporarily suspend/resume to smooth fluctuations in system load.Low Level (CPU) Scheduling or DispatchingSelects the ready process that will be assigned the CPU.Ready Queue contains PCBs of processes.Principles of Operating Systems - CPU Scheduling 8Levels of Scheduling(cont.)Principles of Operating Systems - CPU Scheduling 9CPU SchedulerSelects from among the processes in memory that are ready to execute, and allocates the CPU to one of them.Non-preemptive SchedulingOnce CPU has been allocated to a process, the process keeps the CPU until•Process exits OR•Process switches to waiting statePreemptive SchedulingProcess can be interrupted and must release the CPU.•Need to coordinate access to shared dataPrinciples of Operating Systems - CPU Scheduling 10CPU Scheduling DecisionsCPU scheduling decisions may take place when a process:•switches from running state to waiting state•switches from running state to ready state•switches from waiting to ready•terminatesScheduling under 1 and 4 is non-preemptive.All other scheduling is preemptive.Principles of Operating Systems - CPU Scheduling 11CPU scheduling decisionsnewnewadmittedinterruptI/O oreventcompletionSchedulerdispatchI/O orevent waitexitreadyrunningterminatedwaitingPrinciples of Operating Systems - CPU Scheduling 12DispatcherDispatcher module gives control of the CPU to the process selected by the short-term scheduler. This involves:•switching context•switching to user mode•jumping to the proper location in the user program to restart that programDispatch Latency:time it takes for the dispatcher to stop one process and start another running.Dispatcher must be fast.Principles of Operating Systems - CPU Scheduling 13Scheduling CriteriaCPU Utilization Keep the CPU and other resources as busy as possibleThroughput # of processes that complete their execution per time unit.Turnaround time amount of time to execute a particular process from its entry time.Principles of Operating Systems - CPU Scheduling 14Scheduling Criteria (cont.)Waiting time amount of time a process has been waiting in the ready queue.Response Time (in a time-sharing environment)amount of time it takes from when a request was submitted until the first response is produced, NOT output.Principles of Operating Systems - CPU Scheduling 15Optimization CriteriaMax CPU UtilizationMax ThroughputMin Turnaround timeMin Waiting timeMin response timePrinciples of Operating Systems - CPU Scheduling 16First Come First Serve (FCFS) SchedulingPolicy: Process that requests the CPU FIRST is allocated the CPU FIRST.FCFS is a non-preemptive algorithm.Implementation - using FIFO queues•incoming process is added to the tail of the queue.•Process selected for execution is taken from head of queue.Performance metric - Average waiting time in queue.Gantt Charts are used to visualize schedules.Principles of Operating Systems - CPU Scheduling 17First-Come, First-Served(FCFS) SchedulingExampleProcess Burst TimeP1 24P2 3P3 3Suppose the arrival order for the processes is P1, P2, P3Waiting time P1 = 0;P2 = 24;P3 = 27;Average waiting time(0+24+27)/3 = 17024 27 30P1 P2 P3Gantt Chart for SchedulePrinciples of Operating Systems - CPU Scheduling 18FCFS Scheduling (cont.)ExampleProcess Burst TimeP1 24P2 3P3 3Suppose the arrival order for the processes is P2, P3, P1Waiting time P1 = 6; P2 = 0; P3 = 3;Average waiting time(6+0+3)/3 = 3 , better..Convoy Effect:•short process behind long process, e.g. 1 CPU bound process, many I/O bound processes.0 3 630P1P2 P3Gantt Chart for SchedulePrinciples of Operating Systems - CPU Scheduling 19Shortest-Job-First(SJF) SchedulingAssociate with each process the length of its next CPU burst.