《操作系统 单处理器调度.》由会员分享，可在线阅读，更多相关《操作系统 单处理器调度.（33页珍藏版）》请在金锄头文库上搜索。
1、1 Uniprocessor Scheduling Chapter 9 2 Aim of Scheduling nAssign processes to be executed by the processor(s) nScheduling Criteria(准则) Response time(响应时间) Throughput (吞吐量) Processor efficiency 3 Types of Scheduling 4 Scheduling and Process State Transitions 5 Levels of Scheduling 6 Long-Term Scheduli
2、ng nDetermines which programs are admitted to the system for processing nControls the degree of multiprogramming nMore processes, smaller percentage of time each process is executed 7 Medium-Term Scheduling nPart of the swapping function nBased on the need to manage the degree of multiprogramming 8
3、Short-Term Scheduling nKnown as the dispatcher nExecutes most frequently nInvoked when an event occurs Clock interrupts I/O interrupts Operating system calls Signals 9 Short-Tem Scheduling Criteria nUser-oriented Response Time nElapsed time between the submission of a request until there is output.
4、nSystem-oriented Effective and efficient utilization of the processor nPerformance-related Quantitative Measurable such as response time and throughput 10 Scheduling Criteria 11 Scheduling Criteria (Cont.) 12 Queues for Scheduling 13 Priorities nScheduler will always choose a process of higher prior
5、ity over one of lower priority nHave multiple ready queues to represent each level of priority nLower-priority may suffer starvation(饥饿) Allow a process to change its priority based on its age or execution history 14 Priority Queuing 15 Decision Mode nNonpreemptive Once a process is in the running s
6、tate, it will continue until it terminates or blocks itself for I/O nPreemptive Currently running process may be interrupted and moved to the Ready state by the operating system Allows for better service since any one process cannot monopolize the processor for very long 16 Process Scheduling Exampl
7、e 17 First-Come-First-Served (FCFS) nEach process joins the Ready queue nWhen the current process ceases to execute, the oldest process in the Ready queue is selected 18 First-Come-First-Served (Cont.) nA short process may have to wait a very long time before it can execute nFavors CPU-bound process
8、es I/O processes have to wait until CPU-bound process completes 19 Round-Robin (RR) nUses preemption based on a clock nAn amount of time is determined that allows each process to use the processor for that length of time 20 Round-Robin (Cont.) nClock interrupt is generated at periodic intervals nWhe
9、n an interrupt occurs, the currently running process is placed in the read queue Next ready job is selected nKnown as time slicing 21 Preemption Time Quantum 22 Virtual Round-Robin Scheduler nDrawback of RR CPU-bound I/O-bound Unfairness 23 Shortest Process Next nNonpreemptive policy nProcess with s
10、hortest expected processing time is selected next nShort process jumps ahead of longer processes 24 Shortest Process Next (Cont.) nPredictability of longer processes is reduced nIf estimated time for process not correct, the operating system may abort it nPossibility of starvation for longer process
11、es 25 Shortest Remaining Time nPreemptive version of shortest process next policy nMust estimate processing time 26 Highest Response Ratio Next (HRRN) nChoose next process with the greatest ratio time spent waiting + expected service time expected service time 27 Feedback nPenalize jobs that have be
12、en running longer nDont know remaining time process needs to execute 28 Feedback (Cont.) 29 Characteristics of Various Policies 30 Comparison of Scheduling Policies 31 Traditional UNIX Scheduling nMultilevel feedback using round robin within each of the priority queues nIf a running process does not
13、 block or complete within 1 second, it is preempted nPriorities are recomputed once per second nBase priority divides all processes into fixed bands of priority levels 32 Bands nDecreasing order of priority Swapper Block I/O device control File manipulation Character I/O device control User processes 33 Traditional UNIX Scheduling
