Slide 1Slide 2Types of SchedulingShort-Term SchedulingShort-Term Scheduling CriteriaShort Term Scheduling PoliciesSelection FunctionDecision ModeProcess Scheduling ExampleFCFS/FIFO PolicySlide 11Virtual Round Robin PolicySlide 13Shortest Process Next PolicyShortest Remaining Time PolicyHRRN PolicyMulti-Level Feedback PolicySlide 18Quantum = 1Quantum = 2iUniprocessor SchedulingScheduling of Processes2Types of SchedulingLong-term (least frequent decision)When an new process is created, will it be admitted to the ready queue?Controls degree of multiprogramming (balances response/turnaround time and processor utilization)Can consider priority, expected execution time, I/O requirements, etc.Responds to requests for interactive sessionsMedium-termWhich processes should have frames allocated?Also affects degree of multiprogrammingAlready discussed in context of memory managementShort-term (most frequent decision)Which process should execute next?Focus of this lessonI/O – next lesson3Short-Term SchedulingPerformed by part of kernel referred to as dispatcherInvoked in response toTimer interruptsI/O interruptsSystem callsSignals (e.g. from semaphores)Some long-term and medium-term scheduling events4Short-Term Scheduling CriteriaPerformance RelatedOtherUser OrientedTurnaround timeResponse timeDeadlinesPredictabilitySystem OrientedThroughputProcessor utilizationFairnessEnforcing prioritiesBalancing resources5Short Term Scheduling PoliciesCan be described in terms of Selection functionDecision mode6Selection FunctionDetermines which of the ready processes to executeExample inputs:s: total service time required by the processe: time spent so far in executionw: time spent so far in system (executing and waiting)May also consider resource management or other execution characteristics of processes7Decision ModeSpecifies times at which selection function is invokedNonpreemptiveSelection function used only when running process Blocks for I/O Requests OS serviceTerminatesPreemptiveSelection function is used at other timesTimer interruptsProcess admission8Process Scheduling Example9FCFS/FIFO Policy0510 15 20ABCDE10NonpreemptiveAlways select the process that has been in the ready queue the longest0510 15 20ABCDE11Round Robin PolicyPreemptive -- processes run for a time-slice or quantumAlways select the process that has been in the ready queue the longestVirtual Round Robin PolicyI/O-bound processes typically do not use a complete quantumPut processes with pending I/O in auxiliary queue, remember how much time remains in their time sliceGive preference to processes in auxiliary queueAllow to run for remainder of time slice1213Shortest Process Next Policy0510 15 20ABCDE14Nonpreemptive Always select process with shortest estimated processing timeShortest Remaining Time Policy0510 15 20ABCDE15Preemptive When a new process enters the system, or when the running process leaves the running state Select process with shortest estimated remaining processing timeHRRN Policy16ABCDE0510 15 20HRRN = Highest Response Ratio NextNonpreemptiveAlways select the process that has the highest value ofss e) - (w ratio ResponseMulti-Level Feedback PolicyPreemptive based on time quantumMaintain a ready queue for each priorityWhen a process is preempted, move it to a lower priority queueNote: If there are no processes waiting, don’t preempt current processWith quantum = 1, long processes will have very large turnaround timeGive processes from queue RQi quantum = 2i1718Quantum = 1190510 15 20ABCDEQuantum =
View Full Document
Unlocking...