Hệ điều hành - Chapter 9: Uniprocessor scheduling

Chapter 9Uniprocessor SchedulingTypes of Processor SchedulingScheduling AlgorithmsSchedulingAn OS must allocate resources amongst competing processes.The resource is allocated by means of scheduling - determines which processes will wait and which will progress.The resource provided by a processor is execution time.Overall 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 SchedulingScheduling and Process State TransitionsLong-term scheduling is performed when a new process is created. Medium-term scheduling is a part of the swapping function.Short-term scheduling is the actual decision of which ready process to execute next.Focus of this chapterNesting of Scheduling FunctionsQueuing DiagramScheduling is a matter of managing queues to minimize queuing delay and to optimize performance.Long-Term SchedulingDetermines which programs are admitted to the system for processingMay be first-come-first-servedAccording 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 multiprogrammingthe memory requirements of the swapped-out processesShort-Term SchedulingShort-term scheduler is known as the dispatcher.Executes most frequently to decide which process to execute nextInvoked when an event occursClock interruptsI/O interruptsOperating system callsRoadmapTypes of Processor SchedulingScheduling AlgorithmsAim 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. SystemUser-oriented Behavior of the system as perceived by individual user or processExample: response time (in an interactive system)Elapsed time between the submission of a request until there is outputSystem-orientedEffective and efficient utilization of the processorExample: throughputProcess completion rateShort-Term Scheduling Criteria: PerformancePerformance-relatedQuantitativeEasily measuredExample: response time and throughputNon-performance relatedQualitativeHard to measureExample: predictabilityInterdependent Scheduling CriteriaMore scheduling criteria can be found in Table 9.2.Impossible to optimize all criteria simultaneously.Example: response time vs. throughputDesign of a scheduling policy involves compromising among competing requirements.PrioritiesIn many systems, each process is assigned a priority.Scheduler will always choose a process of higher priority over one of lower priority.Have multiple ready queues to represent each level of priority.Priority Queuingpriority[RQi] > priority[RQj] for i<j; larger priority values represent lower priority processes.The scheduler will start at the highest-priority ready queue.StarvationProblemLower-priority processes 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 history.Alternative Scheduling PoliciesSelection FunctionDetermines which process is selected for execution.If based on execution characteristics then important quantities are:w = time spent in system so far, waitinge = time spent in execution so fars = total service time required by the process, including eDecision ModeSpecifies the instants in time at which the selection function is exercised.Two categories:Non-preemptivePreemptiveNon-preemptive vs. PreemptiveNon-preemptiveOnce a process is in the running state, it will continue until it terminates or blocks itself for I/O or OS service.Preemptive Currently running process may be interrupted and moved to ready state by the OS.Preemption may occur when new process arrives, on an interrupt, or periodically.Process Scheduling ExampleExample set of processes, consider each a batch jobService time (Ts) represents total execution timeFirst-Come-First-Served (FCFS)Each ready process joins the ready queue.When the current process ceases to execute, the process in the ready queue the longest is selected.FCFS A short process may have to wait a very long time before it can execute. Favors CPU-bound processes (mostly use processor) over I/O-bound processes.I/O processes have to wait until CPU-bound process completesmay result in inefficient use of both the processor and the I/O devicesRound Robin (RR) Reduce penalty that short jobs suffer with FCFS by using clock interrupts generated at periodic intervals.When an interrupt occurs, the currently running process is placed in the ready queue and the next ready job is selected on a FCFS basis.Also known as time slicing because each process is given a slice of time before being preempted.RREffect of Size of Preemption Time Quantum There is processing over-head involved in handling the clock interrupt and performing the scheduling and dispatching function.The time quantum should be slightly greater than the time required for a typical interaction.RR Generally, I/O-bound process has a shorter processor burst (amount of time spent executing between I/O operations) than a CPU-bound processresults in poor performance, inefficient use of I/O devices, and an increase in the variance of response time.Virtual Round RobinA fair approach: similar to RR except processes in the auxiliary queue get preference over those in the main ready queue. Shortest Process Next (SPN)Non-preemptive policyProcess with shortest expected processing time is selected next. Reduce the bias in favor of long processes in FCFS by allowing short processes jump ahead of longer processes.SPN Predictability of longer processes is reduced. Need to know or estimate the required processing time for each process.Programmers may be required to supply an estimate for batch jobs.Statistics may be gathered for repeating jobs.If estimated processing time is not correct, OS may abort it.Calculating  ‘Burst’ for interactive processesA running average of each “burst” for each process 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 AveragingRecent bursts more likely reflect future behavior.A common technique for predicting a future value on the basis of a time series of past values is exponential averaging. where 0 <  < 1Exponential Smoothing CoefficientsThe larger the value of , the greater the weight given to the more recent observations.Use Of Exponential AveragingExponential averaging tracks changes faster than simple averaging.The larger value of  results in a more rapid reaction to the change.Shortest RemainingTime (SRT)Preemptive version of SPN: chooses the process with the shortest expected remaining processing time.SRT SRT does not have the bias in favor of long processes found in FCFS.  Unlike round robin, no additional interrupts are generated, reducing overhead.  SRT should give superior turnaround time performance to SPN, because a short job is given immediate preference to a running longer job.  Must estimate processing time and record elapsed service time. A risk of starvation of longer processes.Highest Response Ratio Next (HRRN)Choose next process with the greatest response ratio, trying to minimize the normalized turnaround time.HRRN Shorter jobs are favored (a smaller denominator yields a larger ratio). Longer processes will eventually get past competing shorter jobs (aging without service also increases the ratio). As with SRT and SPN, the expected service time must be estimated.Feedback Scheduling (FB)Penalize jobs that have been running longer by demoting to the next lower-priority queue. Scheduling with preemptive and dynamic priority mechanism.FB PerformanceVariations exist, simple version preempts periodically, similar to round robinlonger processes may suffer starvation if new jobs are entering the system frequentlyNormalized Turnaround TimeIt is impossible to make definitive comparisons because relative performance will depend on a variety of factors.short processeslong processesFair-Share SchedulingUser’s application runs as a collection of processes (threads).User is concerned about the performance of the application.Fair-share scheduling: Make scheduling decisions based on process sets.The concept can be extended to groups of users. Fair-Share SchedulingEach user is assigned a weighting that defines that user’s share of system resources. Objective: To give fewer resources to users who have had more than their fair share and more to those who have had less than their fair share.Fair-Share SchedulerCPUj(i)=measure of CPU utilization by process j through interval iGCPUk(i)=measure of CPU utilization of group k through interval iPj(i)=priority of process j at beginning of interval i; lower values equal higher prioritiesBasej=base priority of process jWk=weighting assigned to group k (share of resources)The user community is divided into a set of fair-share groups and a fraction of the processor resource is allocated to each group.For process j in group k, we haveFair-Share SchedulerGiven:W1=W2=0.5Base1=Base2=Base3=60The CPU count is incremented 60 times per secondPriorities are recalculated once per second