Operating Systems: Internals and Design Principles, 6/E William Stallings - Chapter 9: Uniprocessor Scheduling

Chapter 9Uniprocessor SchedulingOperating Systems:Internals and Design Principles, 6/EWilliam StallingsDave BremerOtago Polytechnic, N.Z.©2008, Prentice HallRoadmapTypes of Processor SchedulingScheduling AlgorithmsTraditional UNIX SchedulingSchedulingAn OS must allocate resources amongst competing processes.The resource provided by a processor is execution timeThe resource is allocated by means of a scheduleOverall Aim of SchedulingThe aim of processor scheduling is to assign processes to be executed by the processor over time, in a way that meets system objectives, such as response time, throughput, and processor efficiency. Scheduling ObjectivesThe scheduling function shouldShare time fairly among processesPrevent starvation of a processUse the processor efficientlyHave low overheadPrioritise processes when necessary (e.g. real time deadlines)Types of SchedulingTwo Suspend StatesRemember this diagram from Chapter 3Scheduling and Process State TransitionsNesting of Scheduling FunctionsQueuing DiagramLong-Term SchedulingDetermines which programs are admitted to the system for processingMay be first-come-first-servedOr according to criteria such as priority, I/O requirements or expected execution timeControls the degree of multiprogrammingMore processes, smaller percentage of time each process is executedMedium-Term SchedulingPart of the swapping functionSwapping-in decisions are based on the need to manage the degree of multiprogrammingShort-Term SchedulingKnown as the dispatcherExecutes most frequentlyInvoked when an event occursClock interruptsI/O interruptsOperating system callsSignalsRoadmapTypes of Processor SchedulingScheduling AlgorithmsTraditional UNIX SchedulingAim of Short Term SchedulingMain objective is to allocate processor time to optimize certain aspects of system behaviour.A set of criteria is needed to evaluate the scheduling policy.Short-Term Scheduling Criteria: User vs SystemWe can differentiate between user and system criteriaUser-orientedResponse TimeElapsed time between the submission of a request until there is output.System-orientedEffective and efficient utilization of the processorShort-Term Scheduling Criteria: PerformanceWe could differentiate between performance related criteria, and those unrelated to performancePerformance-relatedQuantitative, easily measuredE.g. response time and throughputNon-performance relatedQualitativeHard to measureInterdependent Scheduling CriteriaInterdependent Scheduling Criteria cont.PrioritiesScheduler will always choose a process of higher priority over one of lower priorityHave multiple ready queues to represent each level of priorityPriority QueuingStarvationProblem:Lower-priority may suffer starvation if there is a steady supply of high priority processes.SolutionAllow a process to change its priority based on its age or execution historyAlternative Scheduling PoliciesSelection FunctionDetermines which process is selected for executionIf based on execution characteristics then important quantities are:w = time spent in system so far, waiting e = time spent in execution so far s = total service time required by the process, including e;Decision ModeSpecifies the instants in time at which the selection function is exercised.Two categories:NonpreemptivePreemptiveNonpreemptive vs PremeptiveNon-preemptiveOnce a process is in the running state, it will continue until it terminates or blocks itself for I/OPreemptive Currently running process may be interrupted and moved to ready state by the OSPreemption may occur when new process arrives, on an interrupt, or periodically.Process Scheduling ExampleExample set of processes, consider each a batch jobService time represents total execution timeFirst-Come-First-ServedEach process joins the Ready queueWhen the current process ceases to execute, the longest process in the Ready queue is selectedFirst-Come-First-ServedA short process may have to wait a very long time before it can executeFavors CPU-bound processesI/O processes have to wait until CPU-bound process completesRound RobinUses preemption based on a clockalso known as time slicing, because each process is given a slice of time before being preempted.Round RobinClock interrupt is generated at periodic intervalsWhen an interrupt occurs, the currently running process is placed in the ready queueNext ready job is selectedEffect of Size of Preemption Time QuantumEffect of Size of Preemption Time Quantum‘Virtual Round Robin’Shortest Process NextNonpreemptive policyProcess with shortest expected processing time is selected nextShort process jumps ahead of longer processesShortest Process NextPredictability of longer processes is reducedIf estimated time for process not correct, the operating system may abort itPossibility of starvation for longer processesCalculating Program ‘Burst’Where:Ti = processor execution time for the ith instance of this process Si = predicted value for the ith instanceS1 = predicted value for first instance; not calculatedExponential AveragingA common technique for predicting a future value on the basis of a time series of past values is exponential averagingExponential Smoothing CoefficientsUse Of Exponential AveragingUse Of Exponential AveragingShortest RemainingTimePreemptive version of shortest process next policyMust estimate processing time and choose the shortestHighest Response Ratio NextChoose next process with the greatest ratioFeedback SchedulingPenalize jobs that have been running longerDon’t know remaining time process needs to executeFeedback PerformanceVariations exist, simple version pre-empts periodically, similar to round robinBut can lead to starvationPerformance ComparisonAny scheduling discipline that chooses the next item to be served independent of service time obeys the relationship:FormulasOverall Normalized Response TimeNormalized Response Time for Shorter ProcessNormalized Response Time for Longer ProcessesNormalized Turnaround TimeFair-Share SchedulingUser’s application runs as a collection of processes (threads)User is concerned about the performance of the applicationNeed to make scheduling decisions based on process setsFair-Share SchedulerRoadmapTypes of Processor SchedulingScheduling AlgorithmsTraditional UNIX SchedulingTraditional UNIX SchedulingMultilevel feedback using round robin within each of the priority queuesIf a running process does not block or complete within 1 second, it is preemptedPriority is based on process type and execution history.Scheduling FormulaBandsPriorities are recomputed once per secondBase priority divides all processes into fixed bands of priority levelsSwapper (highest)Block I/O device controlFile manipulationCharacter I/O device controlUser processes (lowest)Example of Traditional UNIX Process Scheduling