操作系统 单处理器调度.

1、1Uniprocessor SchedulingChapter 92Aim of SchedulingnAssign processes to be executed by the processor(s)nScheduling Criteria(准则)Response time(响应时间)Throughput (吞吐量)Processor efficiency3Types of Scheduling4Scheduling and Process State Transitions5Levels of Scheduling6Long-Term SchedulingnDetermines whi

2、ch programs are admitted to the system for processingnControls the degree of multiprogrammingnMore processes, smaller percentage of time each process is executed7Medium-Term SchedulingnPart of the swapping functionnBased on the need to manage the degree of multiprogramming8Short-Term SchedulingnKnow

3、n as the dispatchernExecutes most frequentlynInvoked when an event occursClock interruptsI/O interruptsOperating system callsSignals9Short-Tem Scheduling CriterianUser-orientedResponse TimenElapsed time between the submission of a request until there is output.nSystem-orientedEffective and efficient

4、 utilization of the processornPerformance-relatedQuantitativeMeasurable such as response time and throughput10Scheduling Criteria11Scheduling Criteria (Cont.)12Queues for Scheduling13PrioritiesnScheduler will always choose a process of higher priority over one of lower prioritynHave multiple ready q

5、ueues to represent each level of prioritynLower-priority may suffer starvation(饥饿)Allow a process to change its priority based on its age or execution history14Priority Queuing15Decision ModenNonpreemptiveOnce a process is in the running state, it will continue until it terminates or blocks itself f

6、or I/OnPreemptiveCurrently running process may be interrupted and moved to the Ready state by the operating systemAllows for better service since any one process cannot monopolize the processor for very long16Process Scheduling Example17First-Come-First-Served (FCFS)nEach process joins the Ready que

7、uenWhen the current process ceases to execute, the oldest process in the Ready queue is selected18First-Come-First-Served (Cont.)nA short process may have to wait a very long time before it can executenFavors CPU-bound processesI/O processes have to wait until CPU-bound process completes19Round-Robi

8、n (RR)nUses preemption based on a clocknAn amount of time is determined that allows each process to use the processor for that length of time20Round-Robin (Cont.)nClock interrupt is generated at periodic intervalsnWhen an interrupt occurs, the currently running process is placed in the read queueNex

9、t ready job is selectednKnown as time slicing21Preemption Time Quantum22Virtual Round-Robin SchedulernDrawback of RRCPU-boundI/O-boundUnfairness23Shortest Process NextnNonpreemptive policynProcess with shortest expected processing time is selected nextnShort process jumps ahead of longer processes24

10、Shortest Process Next (Cont.)nPredictability of longer processes is reducednIf estimated time for process not correct, the operating system may abort itnPossibility of starvation for longer processes25Shortest Remaining TimenPreemptive version of shortest process next policynMust estimate processing

11、 time26Highest Response Ratio Next (HRRN)nChoose next process with the greatest ratiotime spent waiting + expected service timeexpected service time27FeedbacknPenalize jobs that have been running longernDont know remaining time process needs to execute28Feedback (Cont.)29Characteristics of Various P

12、olicies30Comparison of Scheduling Policies31Traditional UNIX SchedulingnMultilevel feedback using round robin within each of the priority queuesnIf a running process does not block or complete within 1 second, it is preemptednPriorities are recomputed once per secondnBase priority divides all processes i