CSC 4320/6320 Operating Systems Lecture 5 CPU SchedulingChapter 5: CPU SchedulingObjectivesBasic ConceptsCPU-I/O Burst CycleAlternating Sequence of CPU And I/O BurstsHistogram of CPU-burst TimesCPU SchedulerSlide 9Slide 10DispatcherSlide 12Slide 13First-Come, First-Served (FCFS) SchedulingFCFS Scheduling (Cont)Slide 16CPU SCHEDULINGShortest-Job-First (SJF) SchedulingSlide 19Example of SJFSlide 21Determining Length of Next CPU BurstExamples of Exponential AveragingPrediction of the Length of the Next CPU BurstSlide 25Slide 26Slide 27Priority SchedulingSlide 29What about fairness ?Fair Share SchedulingLottery SchedulingLottery Scheduling ExampleRound Robin (RR)Example of RR with Time Quantum = 4Time Quantum and Context Switch TimeTurnaround Time Varies With The Time QuantumMultilevel QueueMultilevel Feedback QueueExample of Multilevel Feedback QueueThread Scheduling : Contention ScopeContention ScopePthread SchedulingSlide 44Multiple-Processor SchedulingNUMA and CPU SchedulingMultiple-Processor Scheduling : Load BalancingMulticore ProcessorsVirtualizationAlgorithm EvaluationDeterministic ModellingQueueing ModelsEvaluation of CPU schedulers by SimulationLinux SchedulingList of Tasks Indexed According to PrioritiesSolaris SchedulingEnd of Lecture 5Saurav KarmakarChapter 5: CPU SchedulingBasic ConceptsScheduling Criteria Scheduling AlgorithmsThread SchedulingMultiple-Processor SchedulingOperating Systems ExamplesAlgorithm EvaluationObjectivesTo introduce CPU scheduling, which is the basis for multiprogrammed operating systemsTo describe various CPU-scheduling algorithmsTo discuss evaluation criteria for selecting a CPU-scheduling algorithm for a particular systemBasic ConceptsUniprocessor system one process may run at a timeObjective of multiprogramming some process running at all times  to maximize CPU utilizationWhen one process has to wait, the operating system takes the CPU away from that process and gives the CPU to another processAlmost all computer resources are scheduled before useCPU-I/O Burst CycleSuccess of CPU scheduling follows :Process execution  CPU–I/O Burst Cycle○ Consists of a cycle of CPU execution and I/O waitBasically While a process waits for I/O, CPU sits idle if no multiprogrammingInstead the OS can give CPU to another processCPU burst distribution Distribution for frequency vs duration of CPU bursts.Exponential or hyperexpoinential in natureAlternating Sequence of CPU And I/O BurstsHistogram of CPU-burst TimesCPU SchedulerSelects from among the processes in memory that are ready to execute, and allocates the CPU to one of them : Short-term SchedulerThe ready queue is not necessarily a FIFO queueCPU scheduling decisions may take place when a process:1.Switches from running to waiting state2.Switches from running to ready state3.Switches from waiting to ready4. TerminatesScheduling under 1 and 4 leaves us no choiceBut option 2 and 3 does.CPU SchedulerNonpreemptive : once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU eitherScheduling under 1 and 4 is Nonpreemptive/CooperativeAll other scheduling is PreemptivePreemptive Scheduling incurs some costs :Access to shared dataEffects on the design of operating system kernelEffects of interruptsDispatcher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 runningFirst-Come, First-Served (FCFS) SchedulingProcess Burst Time P124 P2 3 P3 3 Suppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is:Waiting time for P1 = 0; P2 = 24; P3 = 27Average waiting time: (0 + 24 + 27)/3 = 17P1P2P324 27 300FCFS Scheduling (Cont)Suppose that the processes arrive in the order P2 , P3 , P1 The Gantt chart for the schedule is:Waiting time for P1 = 6; P2 = 0; P3 = 3Average waiting time: (6 + 0 + 3)/3 = 3Much better than previous caseSo Average waiting time vary substantially if the burst time for processes vary – Generally quite long.This is non-preemptive in nature  troublesome for time sharing systemP1P3P263 3005: CPU-Scheduling 17Process Arrival Service Time Time 1 0 8 2 1 4 3 2 9 4 3 50 8 12 21 26P1 P2 P3 P4FCFSAverage wait = ( (8-0) + (12-1) + (21-2) + (26-3) )/4 = 61/4 = 15.25FCFSAlgorithmResidence Timeat the CPUShortest-Job-First (SJF) SchedulingAssociate with each process the length of its next CPU burst. Using these lengths to schedule the process with the shortest timeIf two processes have the same length next CPU burst, FCFS scheduling is used to break the tie.Scheduling depends on the length of the next CPU burst(lower the better)SJF is optimal – gives minimum average waiting time for a given set of processesDifficulty knowing the length of the next CPU requestShortest-Job-First (SJF) SchedulingExample of SJFProcessBurst Time P16 P2 8 P37 P43SJF scheduling chartAverage waiting time = (3 + 16 + 9 + 0) / 4 = 7By moving a short process before a long one, the waiting time of the short process decreases more than it increases the waiting time of the long process. Consequently, the average waiting time decreases.SJF scheduling is used frequently in long-term scheduling.P4P3P131609P224Determining Length of Next CPU BurstHow to implement it at short-term scheduler ?Can only estimate the lengthCan be done by using the length of previous CPU bursts, using exponential averaging:Define 4.10 , 3.burst CPU next the for value predicted 2.burst CPU of length actual 1.1nthnnt .1 1 nnntExamples of Exponential Averaging =0n+1 = nRecent history does not count =1 n+1 =  tnOnly the actual last CPU burst countsIf we expand the formula, we get:n+1 =  tn+(1 - ) tn -1 + … +(1 -  )j  tn -j + … +(1 -  )n +1 0Since both  and (1 - ) are less than or equal to 1, each successive term has less weight than its predecessorPrediction of the Length of the Next CPU Burst5: