操作系统第3章处理机调度

1、2022-3-282022-3-281 1操作系统操作系统2022-3-282022-3-282 2内容概述内容概述3.1 3.1 处理机调度的基本概念处理机调度的基本概念 3.2 3.2 调度算法调度算法 3.3 3.3 实时调度实时调度 3.4 3.4 多处理机系统中的调度多处理机系统中的调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 2022-3-282022-3-283 33.1.1 3.1.1 高级、中级和低级调度高级、中级和低级调度3.1.2 3.1.2 调度队列

2、模型调度队列模型3.1.3 3.1.3 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则2022-3-282022-3-284 43.1.1 3.1.1 高级、中级和低级调度高级、中级和低级调度1.1.高级调度高级调度(High Scheduling)(High Scheduling)又称为又称为作业调度作业调度或或长程调度长程调度(Long-Term Scheduling)(Long-Term Scheduling) 将外存上处于后备队列上的作业调入内存将外存上处于后备队列上的作业调入内存, ,并创并创建进程、分配资源建进程、分配资源, ,安排在就绪队列上安排在就绪队列上有时

3、也称为有时也称为接纳调度接纳调度(Admission Scheduling)(Admission Scheduling)2022-3-282022-3-285 5在每次执行作业调度时在每次执行作业调度时, ,都须做出以下两个都须做出以下两个决定决定。(1)(1)接纳多少个作业接纳多少个作业 取决于取决于多道程序度多道程序度(Degree of Multiprogramming),(Degree of Multiprogramming),即允许多少个作业同时在内存中运行即允许多少个作业同时在内存中运行作业太少作业太少 资源利用率低资源利用率低作业太多作业太多 服务质量下降服务质量下降(2)(2)

4、接纳哪些作业接纳哪些作业 作业调度算法作业调度算法先来先服务先来先服务短作业优先短作业优先优先权高优先优先权高优先2022-3-282022-3-286 6也称为也称为进程调度进程调度或或短程调度短程调度(Short-Term Scheduling),(Short-Term Scheduling),决定就决定就绪队列中的哪个进程应获得处理机。绪队列中的哪个进程应获得处理机。常见的低级调度有常见的低级调度有非抢占方式非抢占方式和和抢占方式抢占方式两种两种(1)(1)非抢占方式非抢占方式(Non-preemptive Mode)(Non-preemptive Mode)(非剥夺方式非剥夺方式) )

5、一旦将处理机分配给某进程一旦将处理机分配给某进程, ,便让该进程一直执行便让该进程一直执行, ,直至该直至该进程完成或阻塞时再分配给其他进程进程完成或阻塞时再分配给其他进程引起进程调度的引起进程调度的因素因素有以下几种有以下几种正在执行的进程执行完毕正在执行的进程执行完毕, ,或因发生某事件而不能再继或因发生某事件而不能再继续执行续执行执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行请求而暂停执行; ;在进程通信或同步过程中执行了某种原语操作在进程通信或同步过程中执行了某种原语操作, ,如如P P操作操作(wait(wait操作操作) )、BlockBlock原语等原语等优点优点

6、: :简单简单, ,系统开销小系统开销小缺点缺点: :不适合时间要求严格的实时系统不适合时间要求严格的实时系统2022-3-282022-3-287 7(2)(2)抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)(剥夺方式剥夺方式) 允许调度程序根据某种原则允许调度程序根据某种原则, ,暂停正在执行的进程暂停正在执行的进程, ,将将处理机分配给其他进程处理机分配给其他进程抢占式调度主要有以下抢占式调度主要有以下原则原则优先权原则优先权原则: :重要作业赋予高优先权重要作业赋予高优先权, ,优先占用处理机优先占用处理机短作业短作业( (进程进程) )优先原则优

7、先原则: :执行时间短的进程优执行时间短的进程优先执先执行行时间片原则时间片原则: :时间片用完后停止执行时间片用完后停止执行, ,适用于适用于分时系统分时系统特点特点:它增加了进程调度的次数它增加了进程调度的次数,增加了系统的开销增加了系统的开销,但保但保证了系统的实时性证了系统的实时性2022-3-282022-3-288 8中级调度又称中级调度又称中程调度中程调度(Medium-Term Scheduling)(Medium-Term Scheduling)引入中级调度的主要目的引入中级调度的主要目的, ,是为了提高是为了提高内存利用率内存利用率和和系统吞吐量系统吞吐量使那些暂时不能运行

8、的进程不再占用宝贵的内存资源使那些暂时不能运行的进程不再占用宝贵的内存资源, ,而将它们而将它们调至外存上去等待调至外存上去等待, ,把此时的进程状态称为把此时的进程状态称为就绪驻外存就绪驻外存状态或状态或挂挂起起状态。当这些进程重又具备运行条件、且内存又稍有空闲时状态。当这些进程重又具备运行条件、且内存又稍有空闲时, ,由中级调度来决定把外存上的哪些又具备运行条件的就绪进程由中级调度来决定把外存上的哪些又具备运行条件的就绪进程, ,重新调入内存重新调入内存, ,并修改其状态为并修改其状态为就绪就绪状态状态, ,挂在就绪队列上等待进挂在就绪队列上等待进程调度程调度对换功能对换功能2022-3-

9、282022-3-289 9运行频率运行频率: :低级调度低级调度 中级调度中级调度 高级调度高级调度2022-3-282022-3-2810103.1.1 3.1.1 高级、中级和低级调度高级、中级和低级调度3.1.2 3.1.2 调度队列模型调度队列模型3.1.3 3.1.3 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则2022-3-282022-3-2811113.1.2 3.1.2 调度队列模型调度队列模型1.1.仅有进程调度的调度队列模型仅有进程调度的调度队列模型在在分时系统分时系统中中,通常仅设有进程调度通常仅设有进程调度,用户键入命令和数据用户键入命令和数据,

10、都直都直接进入内存接进入内存,系统可以把就绪进程组织成一个队列系统可以把就绪进程组织成一个队列每个进程在每个进程在执行执行时时,可能有以下三种情况可能有以下三种情况 进程在给定时间片内已完成进程在给定时间片内已完成,释放处理机后为完成状态释放处理机后为完成状态 进程在时间片内未完成进程在时间片内未完成,进入就绪队列末尾进入就绪队列末尾 进程在执行期间因某事件而阻塞进程在执行期间因某事件而阻塞,进入阻塞队列进入阻塞队列2022-3-282022-3-281212图图3-1 3-1 仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型 2022-3-282022-3-2813132.2.具有高

11、级和低级调度的调度队列模型具有高级和低级调度的调度队列模型在在批处理系统批处理系统中中,不仅需要进程调度不仅需要进程调度,而且还要有作业调度而且还要有作业调度该模型与上一模型主要区别在于该模型与上一模型主要区别在于: (1)就绪队列的形式就绪队列的形式 在批处理系统中在批处理系统中,常用常用优先权队列优先权队列。进程进入就绪。进程进入就绪队列时队列时,按优先权高低插入相应位置按优先权高低插入相应位置 (2)设置多个阻塞队列设置多个阻塞队列 根据事件的不同设置多个队列提高效率根据事件的不同设置多个队列提高效率2022-3-282022-3-281414图图3-2 3-2 具有高、低两级调度的调度

12、队列模型具有高、低两级调度的调度队列模型 2022-3-282022-3-281515图图3-23-2 两级调度简化调度队列模型图两级调度简化调度队列模型图2022-3-282022-3-2816163.3.同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 在引入在引入中级调度中级调度后后, ,可把就绪分为内存就绪和外存就绪可把就绪分为内存就绪和外存就绪( (就绪就绪挂起挂起););阻塞也可分为内存阻塞和外存阻塞阻塞也可分为内存阻塞和外存阻塞( (阻塞挂起阻塞挂起) ) 图图3-3 3-3 具有三级调度时的调度队列模型具有三级调度时的调度队列模型 2022-3-282022-3-2

13、817173.1.1 3.1.1 高级、中级和低级调度高级、中级和低级调度3.1.2 3.1.2 调度队列模型调度队列模型3.1.3 3.1.3 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则2022-3-282022-3-2818181. 1. 面向用户的准则面向用户的准则(1) (1) 周转时间短。周转时间短。 可把平均周转时间描述为可把平均周转时间描述为: : n11iiTnTniSiiTTnW11作业的周转时间作业的周转时间T T与系统为它提供服务的时间与系统为它提供服务的时间T TS S之比之比, ,即即W W= =T/TT/TS S , ,称为称为带权周转时间带权

14、周转时间, ,而而平均平均带权周转时间带权周转时间则可表则可表示为示为: : 2022-3-282022-3-281919面向用户的准则面向用户的准则 (2)(2)响应时间快响应时间快 响应时间响应时间是指从用户通过键盘提交一个请求开始是指从用户通过键盘提交一个请求开始, ,直至直至系统中首次产生响应为止的时间。系统中首次产生响应为止的时间。 响应时间包括响应时间包括键盘输入请求信息传送到处理机的时间键盘输入请求信息传送到处理机的时间、处理机对请求的处理时间处理机对请求的处理时间和和响应信息送回到终端的时间响应信息送回到终端的时间(3)(3)截止时间保证截止时间保证 截止时间截止时间是指某任务

15、必须开始执行的最迟时间或必须是指某任务必须开始执行的最迟时间或必须完成的最迟时间完成的最迟时间 截止时间是截止时间是实时系统实时系统中的重要指标中的重要指标(4)(4)优先权准则优先权准则 在在批处理批处理、实时实时和和分时系统分时系统中都可以选择优先权准则中都可以选择优先权准则, ,以便让紧急任务先处理以便让紧急任务先处理 有时还选择抢占式调度方式有时还选择抢占式调度方式常用于评价常用于评价分时系统分时系统2022-3-282022-3-2820202. 2. 面向系统的准则面向系统的准则 (1)(1)系统吞吐量高系统吞吐量高 吞吐量吞吐量指单位时间内系统所完成的作业数指单位时间内系统所完成

16、的作业数 作业调度的方式和算法对吞吐量的大小有较大影响作业调度的方式和算法对吞吐量的大小有较大影响(2)(2)处理机利用率高处理机利用率高(3)(3)各类资源的平衡利用各类资源的平衡利用 使内存、外存和使内存、外存和I/OI/O设备的利用率高设备的利用率高2022-3-282022-3-282121内容概述内容概述3.1 3.1 处理机调度的基本概念处理机调度的基本概念 3.2 3.2 调度算法调度算法 3.3 3.3 实时调度实时调度 3.4 3.4 多处理机系统中的调度多处理机系统中的调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防

17、死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 2022-3-282022-3-282222在在OSOS中调度的中调度的实质实质是一种资源分配是一种资源分配, ,因而因而调度算法调度算法是指是指: :根根据系统的资源分配策略所规定的资源分配算法据系统的资源分配策略所规定的资源分配算法对不同的系统和系统目标对不同的系统和系统目标, ,通常采用通常采用不同不同的的算法算法, ,如短作业如短作业优先优先, ,时间片轮转等时间片轮转等有些算法适用于作业调度有些算法适用于作业调度, ,有些适用于进程调度有些适用于进程调度, ,有些两者有些两者皆可皆可2022-3-282022-3-2823

18、23内存总量内存总量:100K,:100K,采用不移动的可变分区方式。采用不移动的可变分区方式。作业名作业名 进入磁盘时间进入磁盘时间 需要服务时间需要服务时间 主存量要求主存量要求 A A10:0610:06 42 42分分15K15K B B10:1810:18 30 30分分60K60K C C10:3010:30 24 24分分50K50K D D10:3610:36 24 24分分10K10K E E10:4210:42 12 12分分20K20K周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服

19、务时间高响应比高响应比=(=(等待时间等待时间+ +服务时间服务时间)/)/服务时间服务时间 或或= =等待时间等待时间/ /服务时间服务时间2022-3-282022-3-2824243.2.1 3.2.1 先来先服务和短作业优先算法先来先服务和短作业优先算法3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法3.2.3 3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法2022-3-282022-3-2825253.2.1 3.2.1 先来先服务和短作业先来先服务和短作业( (进程进程) )优先调度算法优先调度算法 1.1.先来先服务调度算法先来先服务调度算法(FCF

20、S)(FCFS) 按照作业进入系统的按照作业进入系统的先后次序先后次序进行调度进行调度, ,先进入系统先进入系统者先调度者先调度; ;即启动等待时间最长的作业即启动等待时间最长的作业 是一种最简单的调度算法是一种最简单的调度算法, ,即可用于即可用于作业调度作业调度, ,也可用也可用于于进程调度进程调度 FCFSFCFS算法比较有利于算法比较有利于长作业长作业( (进程进程) ), ,而不利于而不利于短作业短作业( (进程进程) )2022-3-282022-3-282626内存内存无限大无限大, ,作业调度和进程调度都采用作业调度和进程调度都采用FCFSFCFS作业名作业名 进入磁盘进入磁盘

21、 需要服务需要服务 装入主存装入主存 开始执行开始执行 结束执行结束执行 周转周转 带权周转带权周转时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 A A 0 1 0 1 B B 1 1 100 100 C C 2 2 1 1 D D 3 3 100 100执行顺序执行顺序: :A-B-C-DA-B-C-D周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间0 00 01 11 11 11 13 31 11011011001001 12 21021022022021991991.9

22、91.99101101102102100100100100平均值平均值:100:10025.997525.99752022-3-282022-3-282727内存总量内存总量: :100K100K, ,采用不移动的可变分区方式。采用不移动的可变分区方式。作业调度和进程调度都采用作业调度和进程调度都采用FCFSFCFS作业名作业名 进入磁盘进入磁盘 需要服务需要服务 主存量主存量 装入主存装入主存 开始执行开始执行 结束执行结束执行 周转周转 带权周转带权周转时间时间 时间时间 要求要求 时间时间 时间时间 时间时间 时间时间 时间时间 A A10:06 4210:06 42分分 15K15K

23、B B10:1810:18 30 30分分 60K60K C C10:3010:30 24 24分分 50K50K D D10:3610:36 24 24分分 10K10K E E10:4210:42 12 12分分 20K20K执行顺序执行顺序: :A-B-D-C-EA-B-D-C-E周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间10:0610:0610:0610:0610:4810:4842421 110:1810:1810:3610:3610:4810:4811:1811:1860602 2

24、11:1811:1811:1811:1811:1811:1811:4211:4266662.752.7511:4211:4212:0612:0696964 412:0612:0612:1812:1896968 8平均值平均值: 72723.553.552022-3-282022-3-2828282.2.短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)FSJ(P)F短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)F,SJ(P)F,以要求以要求运行时间长运行时间长短短进行调度进行调度, ,即启动要求运行时间最短的作业即启动要求运行时间最短的作业可以分别用于可以分

25、别用于作业调度作业调度和和进程调度进程调度短作业优先短作业优先(SJF)(SJF)的调度算法的调度算法, ,是从后备队列中选择一是从后备队列中选择一个或若干个估计运行时间最短的作业个或若干个估计运行时间最短的作业, ,将它们调入内存将它们调入内存运行运行; ;而短进程优先而短进程优先(SPF)(SPF)调度算法调度算法, ,则是从就绪队列中则是从就绪队列中选出一选出一估计运行时间估计运行时间最短的进程最短的进程, ,将处理机分配给它将处理机分配给它, ,使它立即执行并一直执行到完成使它立即执行并一直执行到完成, ,或发生某事件而被阻或发生某事件而被阻塞放弃处理机时塞放弃处理机时, ,再重新调度

26、再重新调度2022-3-282022-3-282929内存内存无限大无限大, ,作业调度和进程调度都采用作业调度和进程调度都采用FCFSFCFS作业名作业名 进入磁盘进入磁盘 需要服务需要服务 装入主存装入主存 开始执行开始执行 结束执行结束执行 周转周转 带权周转带权周转时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 A A 0 4 0 4 B B 1 1 3 3 C C 2 2 5 5 D D 3 3 2 2 E E 4 4 4 4执行顺序执行顺序: :A-B-C-D-EA-B-C-D-E作业调度作业调度FCFSFCFS和进程调度都采用和进程调度都采用SJFSJF A

27、 A 0 4 0 4 B B 1 1 3 3 C C 2 2 5 5 D D 3 3 2 2 E E 4 4 4 4周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间0 00 04 44 41 11 13 34 47 76 62 22 21212141411115.55.57 7121210102 24 41414181814143.53.50 00 04 44 41 11 13 36 69 98 88/38/32 24 46 63 31.51.513131818161616/516/54 49 91

28、3139 99/49/4平均值平均值: 9 92.82.8平均值平均值: 8 82.12.1执行顺序执行顺序: :A-D-B-E-CA-D-B-E-C2022-3-282022-3-283030内存总量内存总量: :100K100K, ,采用不移动的可变分区方式。采用不移动的可变分区方式。作业调度采用作业调度采用SJFSJF和进程调度采用和进程调度采用FCFSFCFS作业名作业名 进入磁盘进入磁盘 需要服务需要服务 主存量主存量 装入主存装入主存 开始执行开始执行 结束执行结束执行 周转周转 带权周转带权周转时间时间 时间时间 要求要求 时间时间 时间时间 时间时间 时间时间 时间时间 A A

29、10:06 4210:06 42分分 15K15K B B10:1810:18 30 30分分 60K60K C C10:3010:30 24 24分分 50K50K D D10:3610:36 24 24分分 10K10K E E10:4210:42 12 12分分 20K20K执行顺序执行顺序: :A-B-D-E-CA-B-D-E-C周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间高响应比高响应比=(=(等待时间等待时间+ +服务时间服务时间)/)/服务时间服务时间 或或= =等待时间等待时间/

30、 /服务时间服务时间10:0610:0610:0610:0610:4810:4842421 110:1810:1810:3610:3610:4810:4811:1811:1860602 211:1811:1811:1811:1811:1811:1811:4211:4266662.752.7511:5411:5412:1812:181081084.54.511:4211:4211:5411:5472726 6平均值平均值: 69.669.63.253.252022-3-282022-3-283131 SJ(P)F SJ(P)F调度算法也存在不容忽视的调度算法也存在不容忽视的缺点缺点: : (1)

31、 (1)该算法对该算法对长作业不利长作业不利, ,如作业如作业C C的周转时间由的周转时间由1010增至增至16,16,其带权周转时间由其带权周转时间由2 2增至增至3.23.2。更严重的是。更严重的是, ,如果有一长如果有一长作业作业( (进程进程) )进入系统的后备队列进入系统的后备队列( (就绪队列就绪队列),),由于调度程序由于调度程序总是优先调度那些总是优先调度那些( (即使是后进来的即使是后进来的) )短作业短作业( (进程进程),),将导致将导致长作业长作业( (进程进程) )长期不被调度。长期不被调度。 (2)(2)该算法完全未考虑作业的该算法完全未考虑作业的紧迫程度紧迫程度,

32、 ,因而不能保证因而不能保证紧迫性作业紧迫性作业( (进程进程) )会被及时处理。会被及时处理。 (3)(3)由于作业由于作业( (进程进程) )的长短只是根据用户所提供的的长短只是根据用户所提供的估计估计执行时间执行时间而定的而定的, ,而用户又可能会有意或无意地缩短其作业而用户又可能会有意或无意地缩短其作业的估计运行时间的估计运行时间, ,致使该算法不一定能真正做到短作业优先致使该算法不一定能真正做到短作业优先调度。调度。2022-3-282022-3-2832323.2.1 3.2.1 先来先服务和短作业优先算法先来先服务和短作业优先算法3.2.2 3.2.2 高优先权优先调度算法高优先

33、权优先调度算法3.2.3 3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法2022-3-282022-3-2833331.1.优先权调度算法的类型优先权调度算法的类型 (1)(1)非抢占式非抢占式优先权算法优先权算法系统一旦把处理机分配给就绪队列中优先权最高的系统一旦把处理机分配给就绪队列中优先权最高的进程后进程后, ,该进程便该进程便一直执行下去一直执行下去, ,直至完成直至完成; ;或因发或因发生某事件使该进程放弃处理机时生某事件使该进程放弃处理机时, ,系统方可再将处系统方可再将处理机重新分配给另一优先权最高的进程。理机重新分配给另一优先权最高的进程。主要用于主要用于批处理系

34、统批处理系统中中, ,也可用于某些对实时性要也可用于某些对实时性要求求不严不严的实时系统中。的实时系统中。2022-3-282022-3-283434(2)(2)抢占式抢占式优先权调度算法优先权调度算法系统同样是把处理机分配给优先权最高的进程系统同样是把处理机分配给优先权最高的进程, ,使使之执行。但在其执行期间之执行。但在其执行期间, ,只要又出现了另一个其只要又出现了另一个其优先权更高的进程优先权更高的进程, ,进程调度程序就立即停止当前进程调度程序就立即停止当前进程进程( (原优先权最高的进程原优先权最高的进程) )的执行的执行, ,重新将处理机重新将处理机分配给新到的分配给新到的优先权

35、最高优先权最高的进程。的进程。在采用这种调度算法时在采用这种调度算法时, ,每当系统中出现一个新的每当系统中出现一个新的就绪进程就绪进程i i时时, ,就将其优先权就将其优先权P Pi i与正在执行的进程与正在执行的进程j j的的优先权优先权P Pj j进行进行比较比较。如果。如果P Pi iPPj j, ,原进程原进程P Pj j便继续执便继续执行行; ;但如果是但如果是P Pi iP Pj j, , 则立即停止则立即停止P Pj j的执行的执行, ,做进程做进程切换切换, ,使使i i进程投入执行。进程投入执行。抢占式的优先权调度算法抢占式的优先权调度算法, ,能更好地满足能更好地满足紧迫

36、紧迫作业作业的要求的要求, ,故而常用于要求比较故而常用于要求比较严格严格的实时系统中的实时系统中, , 以及对性能要求较高的批处理和分时系统中。以及对性能要求较高的批处理和分时系统中。2022-3-282022-3-2835352.2.优先权的类型优先权的类型 1) 1)静态优先权静态优先权 静态优先权静态优先权是在是在创建进程创建进程时时确定确定的的, ,且在进程的整个且在进程的整个运行期间保持不变。一般地运行期间保持不变。一般地, ,优先权是利用某一范围内的优先权是利用某一范围内的一个整数来表示的一个整数来表示的, ,例如例如,07,07或或02550255中的某一整数中的某一整数, ,

37、又把又把该整数称为该整数称为优先数优先数。只是具体用法各异。只是具体用法各异: :有的系统用有的系统用“0 0”表示表示最高优先权最高优先权, ,当当数值愈大数值愈大时时, ,其其优先权愈低优先权愈低; ;而有的系而有的系统恰恰相反。统恰恰相反。2022-3-282022-3-283636确定进程优先权的依据有如下三个方面确定进程优先权的依据有如下三个方面: :(1)(1)进程类型进程类型系统系统进程优先级进程优先级高高于于用户用户进程进程(2)(2)进程对资源的需求进程对资源的需求执行时间执行时间短短, ,内存要求内存要求小小的进程的进程, ,有较有较高高优先权。优先权。 (3)(3)用户要

38、求用户要求根据用户进程根据用户进程紧迫紧迫程度及用户所付程度及用户所付费用费用的多少来确定。的多少来确定。静态优先权静态优先权特点特点: :(1)(1)系统简单易行。系统简单易行。(2)(2)系统开销小。系统开销小。(3)(3)不够精确。不够精确。(4)(4)一般用在要求不高的系统中。一般用在要求不高的系统中。2022-3-282022-3-2837372)2)动态优先权动态优先权在创建进程时所赋予的优先权在创建进程时所赋予的优先权, ,是可以随是可以随进程的推进程的推进进或随其或随其等待时间等待时间的增加而改变的的增加而改变的, ,以便获得更好以便获得更好的调度性能。的调度性能。例如例如,

39、,我们可以规定我们可以规定, ,在就绪队列中的进程在就绪队列中的进程, ,随其随其等等待时间的增长待时间的增长, ,其优先权以速率其优先权以速率a a提高。提高。若所有的进程都具有若所有的进程都具有相同相同的优先权的优先权初值初值, ,则显然是则显然是最先进入就绪队列的进程最先进入就绪队列的进程, ,将因其动态优先权变得将因其动态优先权变得最高而优先获得处理机最高而优先获得处理机, ,此即先来先服务此即先来先服务FCFSFCFS算法。算法。若所有的就绪进程具有各若所有的就绪进程具有各不相同不相同的优先权的优先权初值初值, ,那那么么, ,对于优先权初值低的进程对于优先权初值低的进程, ,在等待

40、了足够的在等待了足够的时间时间后后, ,其优先权便可能升为最高其优先权便可能升为最高, ,从而可以获得处理机从而可以获得处理机当采用抢占式优先权调度算法时当采用抢占式优先权调度算法时, ,如果再规定当前如果再规定当前进程的优先权以速率进程的优先权以速率b b下降下降, ,则可防止一个长作业长则可防止一个长作业长期地期地垄断垄断处理机。处理机。2022-3-282022-3-2838383.3.高响应比优先调度算法高响应比优先调度算法(HRF)(HRF)该算法是该算法是FCFSFCFS和和SJFSJF的结合的结合, ,克服了两种算法的缺点克服了两种算法的缺点响应比响应比最高的作业优先启动最高的作

41、业优先启动由于由于等待时间等待时间与与服务时间服务时间之和之和, ,就是系统对该作业的就是系统对该作业的响响应时间应时间, ,故该优先权又相当于故该优先权又相当于响应比响应比R RP P。据此。据此, ,又可表又可表示为示为要求服务时间要求服务时间等待时间优先权要求服务时间响应时间要求服务时间要求服务时间等待时间优先权2022-3-282022-3-283939作业名作业名 进入磁盘时间进入磁盘时间 需要服务时间需要服务时间 响应比响应比1 1 响应比响应比2 2 A A 8:50 90 8:50 90分分 B B 9:00 9:00 24 24分分 C C 9:30 9:30 60 60分分

42、 高响应比高响应比1 1 = =等待时间等待时间/ /服务时间服务时间高响应比高响应比2 2 =(=(等待时间等待时间+ +服务时间服务时间)/)/服务时间服务时间40/90=4/940/90=4/9高响应比优先调度算法高响应比优先调度算法(40+90)/90=4/9+1(40+90)/90=4/9+130/24=5/430/24=5/4(30+24)/24=5/4+1(30+24)/24=5/4+10/60=00/60=0(0+60)/60=1(0+60)/60=1设设9:30进行调度进行调度:作业名作业名 进入磁盘时间进入磁盘时间 需要服务时间需要服务时间 响应比响应比1 1 响应比响应比

43、2 2 A A 8:50 90 8:50 90分分 C C 9:30 9:30 60 60分分 64/90=32/4564/90=32/45(64+90)/90=32/45+1(64+90)/90=32/45+124/60=2/524/60=2/5(24+60)/60=2/5+1(24+60)/60=2/5+1当当B执行完后执行完后,又要在又要在9:54进行调度进行调度:2022-3-282022-3-284040对高响应比优先调度算法对高响应比优先调度算法(HRF)(HRF)的的解释解释 (1)(1)如果作业的如果作业的等待时间等待时间相同相同, ,则要求则要求服务的时间服务的时间愈愈短短,

44、 ,其优先权愈高其优先权愈高, ,因而该算法有利于短作业。因而该算法有利于短作业。 (2)(2)当当要求服务的时间要求服务的时间相同相同时时, ,作业的优先权决定于作业的优先权决定于其等待时间其等待时间, ,等待时间愈等待时间愈长长, ,其优先权愈其优先权愈高高, ,因而它实现的因而它实现的是是先来先服务先来先服务。 (3)(3)对于长作业对于长作业, ,作业的优先级可以随作业的优先级可以随等待时间等待时间的的增增加加而提高而提高, ,当其等待时间足够长时当其等待时间足够长时, ,其优先级便可升到很其优先级便可升到很高高, ,从而也可获得处理机。从而也可获得处理机。高响应比高响应比1 =1 =

45、等待时间等待时间/ /服务时间服务时间2022-3-282022-3-284141进程进程名名到达到达时间时间服务服务时间时间静态优静态优先权先权开始开始时间时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间平均平均静态优先权，静态优先权，非抢占式非抢占式（1 1为高优先权）为高优先权）0 04 4A A4 41 13 3B B2 22 25 5C C3 33 32 2D D5 54 44 4E E1 10 04 44 41 14 48 84 41 18 81111101010/310/311111616141414/514/516161818151515/215/29.49.42.

46、932.93考虑一下考虑一下抢占式抢占式，情况如何？，情况如何？2022-3-282022-3-2842423.2.1 3.2.1 先来先服务和短作业优先算法先来先服务和短作业优先算法3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法3.2.3 3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法2022-3-282022-3-2843433.2.3 3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法 1.1.时间片轮转法时间片轮转法 在早期的时间片轮转法中在早期的时间片轮转法中, ,系统将所有的就绪进程按系统将所有的就绪进程按先来先服务的原则先来先服务的原则,

47、 ,排成一个队列排成一个队列, ,每次调度时每次调度时, ,把把CPUCPU分配给队首进程分配给队首进程, ,并令其执行一个时间片并令其执行一个时间片, ,时间片的大时间片的大小从几小从几msms到几百到几百msms 当执行的时间片用完时当执行的时间片用完时, ,由一个由一个计时器计时器发出发出时钟中断时钟中断请求请求, ,调度程序便据此信号来停止该进程的执行调度程序便据此信号来停止该进程的执行, ,并将并将它送往就绪队列的末尾它送往就绪队列的末尾; ;然后然后, ,再把处理机分配给就绪再把处理机分配给就绪队列中新的队首进程队列中新的队首进程, ,同时也让它执行一个时间片同时也让它执行一个时间

48、片 可以保证就绪队列中的所有进程可以保证就绪队列中的所有进程, ,在一给定的时间内在一给定的时间内, ,均能获得一时间片的处理机执行时间均能获得一时间片的处理机执行时间2022-3-282022-3-284444内存内存无限大无限大。作业调度采用。作业调度采用FCFSFCFS和进程调度采用时间片的轮转和进程调度采用时间片的轮转q=1q=1作业进入作业进入 需要需要 装入装入 开始开始 执行执行 执行执行 开始开始 执行执行 执行执行 开始开始 执行执行 执行执行 开始开始 执行执行 执行执行 完成完成 周转周转 带权带权名名磁盘磁盘 服务服务 主存主存 执行执行 时间时间 后后 执行执行 时间

49、时间 后后 执行执行 时间时间 后后 执行执行 时间时间 后后 周转周转A 0 4A 0 4 B 1 3B 1 3 C 2 4C 2 4 D 3 2D 3 2 E 4 4E 4 4 完成顺序完成顺序: :D-B-A-C-ED-B-A-C-E周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间高响应比高响应比=(=(等待时间等待时间+ +服务时间服务时间)/)/服务时间服务时间 或或= =等待时间等待时间/ /服务时间服务时间0 00 01 11 13 31 11 12 24 43 31 12 21 14

50、 41 1平均值平均值: 11.811.83.433.431 12 24 43 35 55 56 68 87 79 91 11 11 11 11 16 67 79 98 8101010101111121213131 11 11 11 111111212131314141414151516161 11 11 11515161617179 96 63 31212 1111 3.673.671515 1515 3.753.751717 1313 3.253.251616 1414 3.53.5第三版书第三版书2727次印刷，新来进程排在队头次印刷，新来进程排在队头第三版书第三版书3030多次印刷，新

51、来进程排在队尾多次印刷，新来进程排在队尾, ,新来进程排在刚执行完进程前新来进程排在刚执行完进程前2022-3-282022-3-284545内存内存无限大无限大。作业调度采用。作业调度采用FCFSFCFS和进程调度采用时间片的轮转和进程调度采用时间片的轮转q=4q=4作业进入作业进入 需要需要 装入装入 开始开始 执行执行 执行执行 开始开始 执行执行 执行执行 开始开始 执行执行 执行执行 开始开始 执行执行 执行执行 完成完成 周转周转 带权带权名名磁盘磁盘 服务服务 主存主存 执行执行 时间时间 后后 执行执行 时间时间 后后 执行执行 时间时间 后后 执行执行 时间时间 后后 周转周

52、转A 0 4A 0 4 B 1 3B 1 3 C 2 4C 2 4 D 3 2D 3 2 E 4 4E 4 4 完成顺序完成顺序: :A-B-C-D-EA-B-C-D-E周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时间高响应比高响应比=(=(等待时间等待时间+ +服务时间服务时间)/)/服务时间服务时间 或或= =等待时间等待时间/ /服务时间服务时间0 00 04 41 13 34 43 32 24 411112 27 74 413134 4平均值平均值: 8.48.42.72.74 47 713

53、13111117171313 1010 5 57 76 62 24 44 41 11717 1313 3.253.251111 9 92.252.25第三版书第三版书2727次印刷，新来进程排在队尾次印刷，新来进程排在队尾新来进程排在刚执行完进程前新来进程排在刚执行完进程前2022-3-282022-3-284646Page Page 46462022-3-282022-3-282. 2. 多级队列调度多级队列调度前台前台的就绪队列是交互性作业的进程，采用时间片轮转。的就绪队列是交互性作业的进程，采用时间片轮转。后台后台的就绪队列是批处理作业的进程，采用优先权或短作的就绪队列是批处理作业的进程

54、，采用优先权或短作业优先算法。业优先算法。调度方式有两种：调度方式有两种：(1) (1) 优先调度前台，若前台无可运行进程，才调度后台。优先调度前台，若前台无可运行进程，才调度后台。(2) (2) 分配占用分配占用CPUCPU的时间比例，如：前台的时间比例，如：前台80%80%，后台，后台20%20%。2022-3-282022-3-284747图图3-7 3-7 多级反馈队列调度算法多级反馈队列调度算法 2.2.多级反馈队列调度算法多级反馈队列调度算法优先级高优先级高2022-3-282022-3-284848设置多个就绪队列设置多个就绪队列, ,并为各个队列赋予不同的优先级并为各个队列赋予

55、不同的优先级第一个队列的优先级第一个队列的优先级最高最高, ,第二个队列次之第二个队列次之, ,其余各其余各队列的优先权逐个队列的优先权逐个降低降低。该算法赋予各个队列中进程执行该算法赋予各个队列中进程执行时间片时间片的的大小大小也各也各不相同不相同, ,在优先权愈高的队列中在优先权愈高的队列中, ,为每个进程所规定为每个进程所规定的执行时间片就愈小。例如的执行时间片就愈小。例如, ,第二个队列的时间片第二个队列的时间片要比第一个队列的时间片长一倍要比第一个队列的时间片长一倍, , ,第第i i+1+1个队列个队列的时间片要比第的时间片要比第i i个队列的时间片长一倍。个队列的时间片长一倍。调

56、度方式调度方式当一个新进程进入内存后当一个新进程进入内存后, ,首先将它放入第一队列首先将它放入第一队列的末尾的末尾, ,按按FCFSFCFS原则排队等待调度原则排队等待调度当轮到该进程执行时当轮到该进程执行时, ,如它能在该时间片内完成如它能在该时间片内完成, ,便便可准备撤离系统可准备撤离系统; ;如果它在一个时间片结束时尚未如果它在一个时间片结束时尚未完成完成, ,调度程序便将该进程转入第二队列的末尾调度程序便将该进程转入第二队列的末尾, ,再再同样地按同样地按FCFSFCFS原则等待调度执行原则等待调度执行; ;如果它在第二队如果它在第二队列中运行一个时间片后仍未完成列中运行一个时间片

57、后仍未完成, ,再依次将它放入再依次将它放入第三队列第三队列, , ,如此下去如此下去, ,当一个长作业当一个长作业( (进程进程) )从第从第一队列依次降到第一队列依次降到第n n队列后队列后, ,在第在第n n队列中便采取按队列中便采取按时间片轮转的方式运行。时间片轮转的方式运行。2022-3-282022-3-284949仅当仅当第一队列空闲第一队列空闲时时, ,调度程序才调度第二队列中的进调度程序才调度第二队列中的进程运行程运行; ;仅当第仅当第1(i-1) 1(i-1) 队列均空时队列均空时, ,才会调度第才会调度第i i队列队列中的进程运行。中的进程运行。如果处理机正在第如果处理机

58、正在第i i队列中为某进程服务时队列中为某进程服务时, ,又有新进又有新进程进入优先权较高的队列程进入优先权较高的队列( (第第1(i-1)1(i-1)中的任何一个队中的任何一个队列列),),则此时新进程将则此时新进程将抢占抢占正在运行进程的处理机正在运行进程的处理机, ,即由即由调度程序把正在运行的进程放回到第调度程序把正在运行的进程放回到第i i队列的末尾队列的末尾, ,把把处理机分配给新到的高优先权进程。处理机分配给新到的高优先权进程。2022-3-282022-3-2850503.3.多级反馈队列调度算法的性能多级反馈队列调度算法的性能(1)(1)终端型作业用户终端型作业用户终端型作业

59、用户所提交的作业多属于终端型作业用户所提交的作业多属于交互型作业交互型作业, ,通常较通常较小小, ,系统只要能使这些作业在第一队列所规系统只要能使这些作业在第一队列所规定的时间片内完成即可定的时间片内完成即可(2)(2)短批处理作业用户短批处理作业用户若若在第在第1 1队列中执行队列中执行一个时间片一个时间片即可完成即可完成, ,便可获得便可获得与终端型作业一样的响应时间与终端型作业一样的响应时间如在第一个队列中如在第一个队列中不能完成不能完成, ,只需在第只需在第2 2、3 3队列中队列中各执行一个时间片各执行一个时间片(3)(3)长批处理作业用户长批处理作业用户长作业将依次在第长作业将依

60、次在第1,2,31,2,3,n,n队列中执行队列中执行, ,最终按轮最终按轮转方式运行转方式运行2022-3-282022-3-285151内容概述内容概述3.1 3.1 处理机调度的基本概念处理机调度的基本概念 3.2 3.2 调度算法调度算法 3.3 3.3 实时调度实时调度 3.4 3.4 多处理机系统中的调度多处理机系统中的调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 2022-3-282022-3-2852523.3.1 3.3.1 实现实时调度的基本条件实现实时