1、Chapter 6 CPU的調(diào)度,Basic Concepts 基本概念 Scheduling Criteria 調(diào)度程序的評價標(biāo)準(zhǔn) Scheduling Algorithms 調(diào)度算法 Multiple-Processor Scheduling 多處理機(jī)的調(diào)度 Real-Time Scheduling 實時調(diào)度 Algorithm Evaluation 算法評價,CPU調(diào)度,why？ 計算機(jī)得以完成計算，必須依賴CPU 需要運(yùn)行的程序數(shù)計算機(jī)CPU個數(shù) Possible？ CPU的速度用戶的速度 CPU與I/O可以并發(fā) Principle 讓CPU不停地忙，公平地做有用功，考慮任務(wù)的輕重緩急

2、,車輪戰(zhàn)，以一敵百,Basic Concepts,Maximum CPU utilization obtained with multiprogramming （通過多道程序設(shè)計得到CPU的最高利用率） CPUI/O Burst Cycle Process execution consists of a cycle of CPU execution and I/O wait. （CPU-I/O脈沖周期 - 進(jìn)程的執(zhí)行包括進(jìn)程在CPU上執(zhí)行和等待I/O） CPU burst distribution （CPU脈沖的分布）,Alternating Sequence of CPU And I/O B

3、ursts,Histogram of CPU-burst Times,CPU Scheduling,兩個重要角色 CPU scheduler Dispatcher,CPU Scheduler,Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them.（選擇內(nèi)存中的就緒進(jìn)程，并分配CPU給其中之一）,preemptive and nonpreemptive,nonpreemptive once CPU given to the process

4、 it cannot be preempted until completes its CPU burst（非搶占式調(diào)度 一旦進(jìn)程擁有CPU，它的使用權(quán)限只能在該CPU 脈沖結(jié)束后讓出). Preemptive if a new process arrives with CPU burst length less than remaining time of current 法executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF).（搶占式調(diào)度 發(fā)生在有比當(dāng)前進(jìn)程剩余

5、時間片更短的進(jìn)程到達(dá)時，也稱為最短剩余時間優(yōu)先調(diào)度）,什么時候調(diào)度？,記得我們的原則：讓CPU不停忙、公平做有用功、考慮輕重緩急,讓出 CPU,讓出 CPU,剝奪 CPU,可能 剝奪 別的 CPU,什么時候調(diào)度？,CPU scheduling decisions may take place when a process （CPU調(diào)度可能發(fā)生在當(dāng)一個進(jìn)程）: 1. Switches from running to waiting state（從運(yùn)行轉(zhuǎn)到等待）. 2. Switches from running to ready state（從運(yùn)行轉(zhuǎn)到就緒）. 3. Switches from

6、waiting to ready（從等待轉(zhuǎn)到就緒）. 4. Terminates（終止運(yùn)行）. Scheduling under 1 and 4 is nonpreemptive （發(fā)生在1、4兩種情況下的調(diào)度稱為非搶占式調(diào)度）. All other scheduling is preemptive （其他情況下發(fā)生的調(diào)度稱為搶占式調(diào)度）.,Dispatcher,Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves（進(jìn)程調(diào)度模塊負(fù)

7、責(zé)將對CPU的控制權(quán)轉(zhuǎn)交給由CPU調(diào)度程序，包括）: switching context（切換上下文） switching to user mode（切換到用戶態(tài)） jumping to the proper location in the user program to restart that program（跳轉(zhuǎn)到用戶程序的適當(dāng)位置并重新運(yùn)行之） Dispatch latency time it takes for the dispatcher to stop one process and start another running（調(diào)度時間 調(diào)度程序終止一個進(jìn)程的運(yùn)行并啟動另一個進(jìn)程

8、運(yùn)行所花的時間）.,Scheduling Criteria調(diào)度好壞的評判,CPU utilization keep the CPU as busy as possible （CPU利用率 使CPU盡可能的忙碌） Throughput the number of processes that complete their execution per time unit（吞吐量 單位時間內(nèi)運(yùn)行完的進(jìn)程數(shù)） Turnaround time the interval from submission to completion （周轉(zhuǎn)時間 進(jìn)程從提交到運(yùn)行結(jié)束的全部時間 ） Waiting time a

9、mount of time a process has been waiting in the ready queue（等待時間 進(jìn)程在就緒隊列中等待調(diào)度的時間片總和 ） Response time amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)（響應(yīng)時間 從進(jìn)程提出請求到 首次被響應(yīng)而不是輸出結(jié)果的時間段在分時系統(tǒng)環(huán)境下 ）,Optimization Criteria

10、,Max CPU utilization （最大的CPU利用率） Max throughput （最大的吞吐量） Min turnaround time （最短的周轉(zhuǎn)時間） Min waiting time （最短的等待時間） Min response time （最短的響應(yīng)時間）,First-Come, First-Served (FCFS) Scheduling,Example: Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes arrive in the order（假定進(jìn)程到達(dá)順序如下）: P1 , P2 , P

11、3 The Gantt Chart for the schedule is（該調(diào)度的Gantt圖為）: Waiting time（等待時間） for P1 = 0; P2 = 24; P3 = 27 Average waiting time（平均等待時間）: (0 + 24 + 27)/3 = 17,First-Come, First-Served (FCFS) Scheduling,Example: Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes arrive in the order（假定進(jìn)程到達(dá)順序如下）: P1

12、 , P2 , P3 The Gantt Chart for the schedule is（該調(diào)度的Gantt圖為）: Waiting time（等待時間） for P1 = 0; P2 = 24; P3 = 27 Average waiting time（平均等待時間）: (0 + 24 + 27)/3 = 17,First-Come, First-Served (FCFS) Scheduling,Example: Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes arrive in the order（假定進(jìn)程到達(dá)

13、順序如下）: P1 , P2 , P3 The Gantt Chart for the schedule is（該調(diào)度的Gantt圖為）: Waiting time（等待時間） for P1 = 0; P2 = 24; P3 = 27 Average waiting time（平均等待時間）: (0 + 24 + 27)/3 = 17,First-Come, First-Served (FCFS) Scheduling,Example: Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes arrive in the ord

14、er（假定進(jìn)程到達(dá)順序如下）: P1 , P2 , P3 The Gantt Chart for the schedule is（該調(diào)度的Gantt圖為）: Waiting time（等待時間） for P1 = 0; P2 = 24; P3 = 27 Average waiting time（平均等待時間）: (0 + 24 + 27)/3 = 17,First-Come, First-Served (FCFS) Scheduling,Example: Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes arrive i

15、n the order（假定進(jìn)程到達(dá)順序如下）: P1 , P2 , P3 The Gantt Chart for the schedule is（該調(diào)度的Gantt圖為）: Waiting time（等待時間） for P1 = 0; P2 = 24; P3 = 27 Average waiting time（平均等待時間）: (0 + 24 + 27)/3 = 17,First-Come, First-Served (FCFS) Scheduling,Example: Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes

16、 arrive in the order（假定進(jìn)程到達(dá)順序如下）: P1 , P2 , P3 The Gantt Chart for the schedule is（該調(diào)度的Gantt圖為）: Waiting time（等待時間） for P1 = 0; P2 = 24; P3 = 27 Average waiting time（平均等待時間）: (0 + 24 + 27)/3 = 17,FCFS Scheduling (Cont.),Suppose that the processes arrive in the order （假定進(jìn)程到達(dá)順序如下） P2 , P3 , P1 . The G

17、antt chart for the schedule is （該調(diào)度的Gantt圖為） : Waiting time （等待時間） for P1 = 6; P2 = 0; P3 = 3 Average waiting time （平均等待時間） : (6 + 0 + 3)/3 = 3 Much better than previous case（比前例好得多）. Convoy effect short process behind long process （此種結(jié)果產(chǎn)生是由于長進(jìn)程先于短進(jìn)程到達(dá) “同牌不同命”）,P1,P3,P2,6,3,30,0,30,Shortest-Job-Firs

18、t (SJF) Scheduling,金手指-化偶然為必然 Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time.（關(guān)聯(lián)到每個進(jìn)程下次運(yùn)行的CPU脈沖長度，調(diào)度最短的進(jìn)程） SJF is optimal gives minimum average waiting time for a given set of processes.（SJF是最優(yōu)的 對一組指定的進(jìn)程而言，它給出了最短的平均等待時間）

19、,Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (non-preemptive) Average waiting time = (0 + 6 + 3 + 7)/4 = 4,Example of Non-Preemptive SJF,P1,P3,P2,7,3,16,0,P4,8,12,16,Example of Preemptive SJF（更徹底SJF）,Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF

20、(preemptive) Average waiting time = (9 + 1 + 0 +2)/4 = 3,P1,P3,P2,4,2,11,0,P4,5,7,P2,P1,16,5,4,5,2,1,5,2,4,5,16,5,4,Determining Length of Next CPU Burst,Examples of Exponential Averaging(略),Prediction of the Length of the Next CPU Burst,Priority Scheduling,A priority number (integer) is associated w

21、ith each process（每個進(jìn)程都有自己的優(yōu)先數(shù)整數(shù)） The CPU is allocated to the process with the highest priority (smallest integer highest priority)（CPU分配給最高優(yōu)先級的進(jìn)程假定最小的整數(shù) 最高的優(yōu)先級）. Preemptive（搶占式） Nonpreemptive （非搶占式） Problem Starvation low priority processes may never execute （問題 饑餓 低優(yōu)先級的可能永遠(yuǎn)得不到運(yùn)行）. Solution Aging as

22、 time progresses increase the priority of the process （解決方法 老化 視進(jìn)程等待時間的延長提高其優(yōu)先數(shù)）.,Round Robin (RR),Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue （每個進(jìn)程將得到小單位的CPU時間時間

23、片，通常為10-100毫 秒。時間片用完后，該進(jìn)程將被搶占并插入就緒隊列末尾）. Performance（特性） q large FIFO q small q must be large with respect to context switch, otherwise overhead is too high（q相對于切換上下文的時間而言不許足夠長，否則將導(dǎo)致系統(tǒng)開銷過大）.,Round Robin (RR),Example: RR with Time Quantum = 20,Process Burst Time P1 53 P2 17 P3 68 P4 24 The Gantt char

24、t is: Typically, higher average turnaround than SJF, but better response（典型的說，RR的平均周轉(zhuǎn)時間比SJF長，但響應(yīng)時間要短一些）.,0,20,37,57,77,97,117,121,134,154,162,Time Quantum and Context Switch Time,Multilevel Queue多級隊列,Ready queue is partitioned into separate queues（就緒隊列分為）: foreground (interactive)（前臺）交互式 background

25、(batch) （后臺） 批處理 Each queue has its own scheduling algorithm （每個隊列有自己的調(diào)度算法） foreground RR background FCFS,Multilevel Queue Scheduling,Multilevel Feedback Queue,A process can move between the various queues; aging can be implemented this way（進(jìn)程能在不同的隊列間移動；可實現(xiàn)老化）. Scheduling must be done between the qu

26、eues（調(diào)度須在隊列間進(jìn)行）. Fixed priority scheduling; i.e., serve all from foreground then from background. Possibility of starvation（固定優(yōu)先級調(diào)度，即前臺運(yùn)行完后再運(yùn)行后臺。有可能產(chǎn)生饑餓）. Time slice each queue gets a certain amount of CPU time which it can schedule amongst its processes; e.g.,80% to foreground in RR 20% to backgrou

27、nd in FCFS （給定時間片調(diào)度，即每個隊列得到一定的CPU時間，進(jìn)程在給定時間內(nèi)執(zhí)行；如，80%的時間執(zhí)行前臺的RR調(diào)度，20%的時間執(zhí)行后臺的FCFS調(diào)度）,Example of Multilevel Feedback Queue,Three queues: Q0 time quantum 8 milliseconds Q1 time quantum 16 milliseconds Q2 FCFS Scheduling A new job enters queue Q0 which is served FCFS. When it gains CPU, job receives 8 m

28、illiseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1. At Q1 job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2.,Multilevel Feedback Queues,Multiple-Processor Scheduling,CPU scheduling more c

29、omplex when multiple CPUs are available（多個CPU可用時，CPU調(diào)度將更為復(fù)雜）. Homogeneous processors within a multiprocessor （多處理器內(nèi)的同類處理器）. Load sharing （負(fù)載共享）,Multiple-Processor Scheduling,Symmetric Multiprocessing (SMP) each processor makes its own scheduling decisions（對稱多處理器 每個處理器決定自己的調(diào)度方案）. Asymmetric multiproc

30、essing only one processor accesses the system data structures, alleviating the need for data sharing. （非對稱多處理器 僅一個處理器能處理系統(tǒng)數(shù)據(jù)結(jié)構(gòu)，這就減輕了對數(shù)據(jù)的共享需求）,Real-Time Scheduling,實時調(diào)度是調(diào)度算法中的一種，在實時系統(tǒng)中應(yīng)用較多，在現(xiàn)代系統(tǒng)中也得到了更多的應(yīng)用。 實時進(jìn)程的實時是指與外部的事件的實時性的關(guān)系，它或者是控制外部事件或者是與外部事件有交互作用。因此它必須在時間上與外部事件相一致。因此通常有一個基線與實時進(jìn)程相關(guān)，基線有兩種：開始的基線（進(jìn)

31、程必須在某時間前開始執(zhí)行），完成的基線（進(jìn)程必須在某時間前完成執(zhí)行產(chǎn)生出結(jié)果）。,Real-Time Scheduling,Hard real-time systems required to complete a critical task within a guaranteed amount of time. （硬件實現(xiàn)的實時系統(tǒng) 用于實現(xiàn)要求在給定的時間內(nèi)執(zhí)行完臨界進(jìn)程的場合）不按照基線要求 比如航天中的宇宙飛船的控制等就是現(xiàn)實中這樣的系統(tǒng) . Soft real-time computing requires that critical processes receive priori

32、ty over less fortunate ones. （軟件實現(xiàn)的實時計算 當(dāng)要求臨界進(jìn)程得到比其他進(jìn)程更高的優(yōu)先級時）軟件實現(xiàn)的基線應(yīng)能以一個可計算的概率得到滿足，偶然的不能滿足也能忍受,Dispatch Latency 分派的時間間隔,當(dāng)前Linux在實時內(nèi)核方面的發(fā)展,1)兼容內(nèi)核方法。即含有一個兼容Linux內(nèi)核，符合POSIX的API層的實時內(nèi)核 2)雙內(nèi)核方法。雙內(nèi)核系統(tǒng)在硬件平臺上增加一個實時內(nèi)核，建立雙內(nèi)核，如現(xiàn)在流行的RT-Linux 3)內(nèi)核修改方法。通過修改Linux內(nèi)核源碼來實現(xiàn)。如RED-Linux就采用該方法。在內(nèi)核代碼中增加搶占點(diǎn)，從而減少內(nèi)核搶占延遲。 4）

33、基線驅(qū)動調(diào)度,Algorithm Evaluation 算法評價,Deterministic modeling takes a particular predetermined workload and defines the performance of each algorithm for that workload. 確定性的模型-按事先確定的負(fù)荷和基于這樣的負(fù)荷每個算法都有一定的性能。 Queueing models 排隊的模型 Simulation 模擬仿真 Implementation實現(xiàn) 請判斷P131的例題是否正確？,Evaluation of CPU Schedulers b

34、y Simulation 通過模擬的方法評價CPU調(diào)度程序,Solaris 2 Scheduling,Windows 2000 Priorities,Summary,Why，進(jìn)程數(shù)CPU When，四個時機(jī) Who and whom，cpu scheduler/dispatcher, processes in ready queue How，F(xiàn)CFS，SJF，priority，RR，RT Criteria，Turnaround time、Waiting time、CPU utilization、Throughput、Response time,作業(yè),1. A CPU scheduling al

35、gorithm determines an order for the execution of its scheduled processes. Given n processes to be scheduled on one processor, how many possible different schedules are there? Give a formula in terms of n. 2. Define the difference between preemptive and nonpreemptive scheduling. State why strict nonp

36、reemptive scheduling is unlikely to be used in a computer center. 3. Consider the following set of processes, with the length of the CPU-burst time given in milliseconds: The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0. a. Draw four Gantt charts illustrating

37、the execution of these processes using FCFS, SJF, a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling. b. What is the turnaround time of each process for each of the scheduling algorithms in part a? c. What is the waiting time of each proce

38、ss for each of the scheduling algorithms in part a? d. Which of the schedules in part a results in the minimal average waiting time (over all processes)?,4. Suppose that the following processes arrive for execution at the times indicated. Each process will run the listed amount of time. In answering

39、 the questions, use nonpreemptive scheduling and base all decisions on the information you have at the time the decision must be made. a. What is the average turnaround time for these processes with the FCFS scheduling algorithm? b. What is the average turnaround time for these processes with the SJ

40、F scheduling algorithm? c. The SJF algorithm is supposed to improve performance, but notice that we chose to run process P1 at time 0 because we did not know that two shorter processes would arrive soon. Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit an

41、d then SJF scheduling is used. Remember that processes P1 and P2 are waiting during this idle time, so their waiting time may increase. This algorithm could be known as future-knowledge scheduling.,5. Consider the following preemptive priority-scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready