c第三章处理机调度与死锁

1、1 1操作系统操作系统2 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 死锁的检测与解除死锁的检测与解除 3 33.1.1 3.1.1 高级调度高级调度3.1.2 3.1.2 低级调度低级调度3.1.3 3.1.3 中级调度中级调度4 43.1.1 3.1.1 高级调度高级调度高级调度高级调度(High Schedulin

2、g)(High Scheduling)，又称为又称为作业调度作业调度或或长长程调度程调度(Long-Term Scheduling)，它调度的对象为它调度的对象为作作业。业。n将外存上（处于后备队列上的）作业调入内存将外存上（处于后备队列上的）作业调入内存, ,并创并创建进程、分配资源建进程、分配资源, ,安排在就绪队列上安排在就绪队列上n一般用于批处理系统，分一般用于批处理系统，分/实时系统一般直接入内存，实时系统一般直接入内存，无此环节。无此环节。有时也称为有时也称为接纳调度接纳调度(Admission Scheduling)(Admission Scheduling)5 5在每次执行作业

3、调度时在每次执行作业调度时, ,都须做出以下两个都须做出以下两个决定决定。(1)(1)接纳多少个作业接纳多少个作业 取决于取决于多道程序度多道程序度(Degree of Multiprogramming),(Degree of Multiprogramming),即允许多少个作业同时在内存中运行即允许多少个作业同时在内存中运行作业太少作业太少资源利用率低资源利用率低作业太多作业太多服务质量下降服务质量下降(2)(2)接纳哪些作业接纳哪些作业 即作业调度算法即作业调度算法先来先服务先来先服务短作业优先短作业优先优先权高优先优先权高优先6 6低级调度低级调度(Low Level Schedulin

4、g)(Low Level Scheduling)，也称为，也称为进程调进程调度度或或短程调度短程调度(Short-Term Scheduling),(Short-Term Scheduling),决定就绪决定就绪队列中的哪个进程应获得处理机，队列中的哪个进程应获得处理机，然后再由分派程序然后再由分派程序（DispatcherDispatcher）执行把处理机分配给该进程的具体操作）执行把处理机分配给该进程的具体操作。它所调度的对象是进程（或内核级线程）。它所调度的对象是进程（或内核级线程）。是最基本的一种调度，在多道批处理、分时和实时是最基本的一种调度，在多道批处理、分时和实时3 3种类型的种

5、类型的OSOS中，都必须配置这级调度。中，都必须配置这级调度。7 7（1 1）保存处理机的现场信息。）保存处理机的现场信息。指当前进程的，存入其指当前进程的，存入其PCBPCB中。中。（2 2）按某种算法选取进程。）按某种算法选取进程。如优先数算法、轮转法等。改如优先数算法、轮转法等。改变选中进程的状态，即从就绪态为运行态，准备把处理变选中进程的状态，即从就绪态为运行态，准备把处理机分配给它。机分配给它。（3 3）把处理机分配给进程。）把处理机分配给进程。由分派程序把处理机分配给进由分派程序把处理机分配给进程。程。8 8为了实现进程调度，应具有以下三个基本机制：为了实现进程调度，应具有以下三个

6、基本机制：（1 1）排队器。排队器。将系统中所有的就绪进程按照一定的方式将系统中所有的就绪进程按照一定的方式排成一个或多个队列。排成一个或多个队列。（2 2）分派器（分派程序）分派器（分派程序）。把由进程调度所选定的进程，。把由进程调度所选定的进程，从就绪队列中取出，然后进行上下文切换，将处理机从就绪队列中取出，然后进行上下文切换，将处理机分配给它。分配给它。（3 3）上下文切换上下文切换。当对处理机进行切换时，会发生两次。当对处理机进行切换时，会发生两次上下文切换操作。上下文切换操作。 第一次切换时，第一次切换时，OSOS将保存当前进程的上下文，而装将保存当前进程的上下文，而装入分派程序的上

7、下文，以便分派程序运行；入分派程序的上下文，以便分派程序运行； 第二次切换时，将移出分派程序，而把新选进程的第二次切换时，将移出分派程序，而把新选进程的CPUCPU现场信息装入到处理机的各个相应寄存器中。现场信息装入到处理机的各个相应寄存器中。9 9 常见的低级调度有常见的低级调度有非抢占方式非抢占方式和和抢占方式抢占方式两种两种(1)(1)非抢占方式非抢占方式(Non-preemptive Mode)(Non-preemptive Mode)(非剥夺方式非剥夺方式) )一旦将处理机分配给某进程一旦将处理机分配给某进程, ,便让该进程一直执行便让该进程一直执行, ,直直至该进程完成或阻塞时再分

8、配给其他进程至该进程完成或阻塞时再分配给其他进程引起进程调度的引起进程调度的因素因素有以下几种有以下几种正在执行的进程执行完毕正在执行的进程执行完毕, ,或因发生某事件而不能或因发生某事件而不能再继续执行再继续执行执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行请求而暂停执行; ;在进程通信或同步过程中执行了某种原语操作在进程通信或同步过程中执行了某种原语操作, ,如如P P操作操作(wait(wait操作操作) )、BlockBlock原语等原语等优点优点: :简单简单, ,系统开销小系统开销小缺点缺点: :不适合时间要求严格的实时系统不适合时间要求严格的实时系统1010(2)

9、(2)抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)(剥夺方式剥夺方式) 允许调度程序根据某种原则允许调度程序根据某种原则, ,暂停正在执行的进程暂停正在执行的进程, ,将将处理机分配给其他进程处理机分配给其他进程抢占式调度主要有以下抢占式调度主要有以下原则原则优先权原则优先权原则: :重要作业赋予高优先权重要作业赋予高优先权, ,优先占用处理机优先占用处理机短作业短作业( (进程进程) )优先原则优先原则: :执行时间短的进程优执行时间短的进程优先先执执行行时间片原则时间片原则: :时间片用完后停止执行时间片用完后停止执行, ,适用于适用于分时系统分时系

10、统特点特点:它增加了进程调度的次数它增加了进程调度的次数,增加了系统的开销增加了系统的开销,但保但保证了系统的实时性证了系统的实时性1111中级调度中级调度又称又称中程调度中程调度(Medium-Term Scheduling)(Medium-Term Scheduling)系统吞吐量系统吞吐量内存利用率内存利用率使那些暂时不能运行的进程不再占用宝贵的内存资源使那些暂时不能运行的进程不再占用宝贵的内存资源, ,而将它而将它们调至外存上去等待们调至外存上去等待, ,把此时的进程状态称为把此时的进程状态称为就绪驻外存就绪驻外存状态或状态或挂起挂起状态。状态。当这些进程重又具备运行条件、且内存又稍有

11、空闲时当这些进程重又具备运行条件、且内存又稍有空闲时, ,由中级由中级调度来决定把外存上的哪些又具备运行条件的就绪进程调度来决定把外存上的哪些又具备运行条件的就绪进程, ,重新调重新调入内存入内存, ,并修改其状态为并修改其状态为就绪就绪状态状态, ,挂在就绪队列上等待进程调度挂在就绪队列上等待进程调度对换功能对换功能1212运行频率运行频率: :低级调度低级调度 中级调度中级调度 高级调度高级调度13133.4.1 3.4.1 调度队列模型调度队列模型3.4.2 3.4.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则14143.4.1 3.4.1 调度队列模型调度队列模

12、型 1.1.仅有进程调度的调度队列模型仅有进程调度的调度队列模型 在在分时系统分时系统中中,通常仅设有进程调度通常仅设有进程调度,用户键入命令和数据用户键入命令和数据,都直接进入内存都直接进入内存,系统可以把就绪进程组织成一个队列系统可以把就绪进程组织成一个队列每个进程在每个进程在执行执行时时,可能有以下三种情况可能有以下三种情况 进程在给定时间片内已完成进程在给定时间片内已完成,释放处理机后为完成状释放处理机后为完成状态态 进程在时间片内未完成进程在时间片内未完成,进入就绪队列末尾进入就绪队列末尾 进程在执行期间因某事件而阻塞进程在执行期间因某事件而阻塞,进入阻塞队列进入阻塞队列1515图图

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

14、列提高效率1717图图3-2 3-2 具有高、低两级调度的调度队列模型具有高、低两级调度的调度队列模型 1818图图3-2 3-2 两级调度简化调度队列模型两级调度简化调度队列模型图图19193.3.同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 在引入在引入中级调度中级调度后后, ,可把就绪分为内存就绪和外存就绪可把就绪分为内存就绪和外存就绪( (就绪挂起就绪挂起););阻塞也可分为内存阻塞和外存阻塞阻塞也可分为内存阻塞和外存阻塞( (阻塞挂起阻塞挂起) ) 图图3-3 3-3 具有三级调度时的调度队列模型具有三级调度时的调度队列模型 20203.4.1 3.4.1 调度队列模

15、型调度队列模型3.4.2 3.4.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则21211. 1. 面向用户的准则面向用户的准则 周转时间短（常用于批处理系统）周转时间短（常用于批处理系统） 概念：作业从提交概念：作业从提交 完成的时间完成的时间. .分为：分为：（1 1）驻外等待调度时间）驻外等待调度时间（2 2）驻内等待调度时间）驻内等待调度时间（3 3）执行时间）执行时间（4 4）阻塞时间）阻塞时间22221. 1. 面向用户的准则面向用户的准则 (1) (1) 周转时间短。周转时间短。 可把平均周转时间描述为可把平均周转时间描述为: : n11iiTnTniSii

16、TTnW11 作业的周转时间作业的周转时间T T与系统为它提供服务的时间与系统为它提供服务的时间T TS S之比之比, ,即即W W= =T/TT/TS S , ,称为称为带权周转时间带权周转时间, ,而而平均平均带权周转时间带权周转时间则可则可表示为表示为: : 可见带权可见带权W越小越好越小越好23231.1.面向用户的准则面向用户的准则 (2)(2)响应时间快响应时间快 响应时间响应时间是指从用户通过键盘提交一个请求开始是指从用户通过键盘提交一个请求开始, ,直至直至 系统中首次产生响应为止的时间系统中首次产生响应为止的时间 响应时间包括响应时间包括键盘输入请求信息传送到处理机的时间键盘

17、输入请求信息传送到处理机的时间、处理机对请求的处理时间处理机对请求的处理时间和和响应信息送回到终端的时间响应信息送回到终端的时间(3)(3)截止时间保证截止时间保证 截止时间截止时间是指某任务必须开始执行的最迟时间或必须是指某任务必须开始执行的最迟时间或必须完成的最迟时间完成的最迟时间 截止时间是截止时间是实时系统实时系统中的重要指标中的重要指标(4)(4)优先权准则优先权准则 在在批处理批处理、实时实时和和分时系统分时系统中都可以选择优先权准则中都可以选择优先权准则, ,以便让紧急任务先处理以便让紧急任务先处理 有时还选择抢占式调度方式有时还选择抢占式调度方式常用于评价常用于评价分时系统分时

18、系统24242. 2. 面向系统的准则面向系统的准则 (1)(1)系统吞吐量高系统吞吐量高 吞吐量吞吐量指单位时间内系统所完成的作业数指单位时间内系统所完成的作业数 作业调度的方式和算法对吞吐量的大小有较大影响作业调度的方式和算法对吞吐量的大小有较大影响(2)(2)处理机利用率高处理机利用率高(3)(3)各类资源的平衡利用各类资源的平衡利用 使内存、外存和使内存、外存和I/OI/O设备的利用率高设备的利用率高2525内容概述内容概述3.1 3.1 处理机调度的层次处理机调度的层次3.2 3.2 调度队列模型和调度准则调度队列模型和调度准则3.3 3.3 调度算法调度算法 3.4 3.4 实时调

19、度实时调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 2626 在在OSOS中调度的中调度的实质实质是一种资源分配是一种资源分配, ,因而因而调度算法调度算法是指是指: :根根据系统的资源分配策略所规定的资源分配算法据系统的资源分配策略所规定的资源分配算法 对不同的系统和系统目标对不同的系统和系统目标, ,通常采用通常采用不同不同的的算法算法, ,如短作业如短作业优先优先, ,时间片轮转等时间片轮转等 有些算法适用于作业调度有些算法适用于作业调度, ,有些适用于进程调度有些适

20、用于进程调度, ,有些两者有些两者皆可皆可27273.4.1 3.4.1 先来先服务和短作业优先算法先来先服务和短作业优先算法3.4.2 3.4.2 高优先权优先调度算法高优先权优先调度算法3.4.3 3.4.3 基于时间片的轮转调度算法基于时间片的轮转调度算法28283.4.1 3.4.1 先来先服务和短作业先来先服务和短作业( (进程进程) )优先调度算法优先调度算法 1.1.先来先服务调度算法先来先服务调度算法(FCFS)(FCFS) 按照作业进入系统的按照作业进入系统的先后次序先后次序进行调度进行调度, ,先进入系统先进入系统者先调度者先调度; ;即启动等待时间最长的作业即启动等待时间

21、最长的作业 是一种最简单的调度算法是一种最简单的调度算法, ,即可用于即可用于作业调度作业调度, ,也可用也可用于于进程调度进程调度 FCFSFCFS算法比较有利于算法比较有利于长作业长作业( (进程进程) ), ,而不利于而不利于短作业短作业( (进程进程) ) FCFSFCFS算法有利于算法有利于CPUCPU繁忙型作业繁忙型作业( (进程进程),),而不利于而不利于I/OI/O繁忙型作业繁忙型作业( (进程进程) )2929内存内存无限大无限大, ,作业调度和进程调度都采用作业调度和进程调度都采用FCFSFCFS作业名作业名 进入磁盘进入磁盘 需要服务需要服务 装入主存装入主存 开始执行开

22、始执行 结束执行结束执行 周转周转 带权周转带权周转时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 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.991.991011011021021001001

23、00100平均值平均值:100:10025.997525.997530302.2.短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)FSJ(P)F短作业短作业( (进程进程) )优先调度算法优先调度算法SJ(P)F,SJ(P)F,以要求以要求运行时间长运行时间长短短进行调度进行调度, ,即启动要求运行时间最短的作业即启动要求运行时间最短的作业可以分别用于可以分别用于作业调度作业调度和和进程调度进程调度短作业优先短作业优先(SJF)(SJF)的调度算法的调度算法, ,是从后备队列中选择一是从后备队列中选择一个或若干个估计运行时间最短的作业个或若干个估计运行时间最短的作业, ,将它

24、们调入内存将它们调入内存运行运行; ;而短进程优先而短进程优先(SPF)(SPF)调度算法调度算法, ,则是从就绪队列中则是从就绪队列中选出一选出一估计运行时间估计运行时间最短的进程最短的进程, ,将处理机分配给它将处理机分配给它, ,使它立即执行并一直执行到完成使它立即执行并一直执行到完成, ,或发生某事件而被阻或发生某事件而被阻塞放弃处理机时塞放弃处理机时, ,再重新调度再重新调度3131内存内存无限大无限大, ,作业调度和进程调度都采用作业调度和进程调度都采用FCFSFCFS作业名作业名 进入磁盘进入磁盘 需要服务需要服务 装入主存装入主存 开始执行开始执行 结束执行结束执行 周转周转

25、带权周转带权周转时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 时间时间 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 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周转时间周转时间= =结束执行时间结束执行时间- -进入磁盘时间进入磁盘时间带权周转时间带权周转时间= =周转时间周转时间/ /服务时间服务时

26、间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 913139 99/49/4平均值平均值: 9 92.82.8平均值平均值: 8 82.12.1执行顺序执行顺序: :A-D-B-E-CA-D-B-E-C3232 SJ(P)F SJ(P)F调度算法也存在不容忽视的缺点调度算法也存在不容忽视的缺点: : (1)(

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

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

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

30、不严的实时系统中。的实时系统中。3535(2)(2)抢占式抢占式优先权调度算法优先权调度算法系统同样是把处理机分配给优先权最高的进程系统同样是把处理机分配给优先权最高的进程, ,使使之执行。但在其执行期间之执行。但在其执行期间, ,只要又出现了另一个其只要又出现了另一个其优先权更高的进程优先权更高的进程, ,进程调度程序就立即停止当前进程调度程序就立即停止当前进程进程( (原优先权最高的进程原优先权最高的进程) )的执行的执行, ,重新将处理机重新将处理机分配给新到的分配给新到的优先权最高优先权最高的进程。的进程。在采用这种调度算法时在采用这种调度算法时, ,每当系统中出现一个新的每当系统中出

31、现一个新的就绪进程就绪进程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进程投入执行。进程投入执行。抢占式的优先权调度算法抢占式的优先权调度算法, ,能更好地满足能更好地满足紧迫紧迫作业作业的要求的要求, ,故而常用于故而常用于要求比较要求比较严格严格的实时系统中的实时系统中, , 以及

32、对性能要求较高的批处理和分时系统中。以及对性能要求较高的批处理和分时系统中。36362.2.优先权的类型优先权的类型 1) 1)静态优先权静态优先权 静态优先权静态优先权是在是在创建进程创建进程时时确定确定的的, ,且在进程的整个且在进程的整个运行期间保持不变。一般地运行期间保持不变。一般地, ,优先权是利用某一范围内的优先权是利用某一范围内的一个整数来表示的一个整数来表示的, ,例如例如,07,07或或02550255中的某一整数中的某一整数, ,又把又把该整数称为该整数称为优先数优先数。只是具体用法各异。只是具体用法各异: :有的系统用有的系统用“0 0”表示表示最高优先权最高优先权, ,

33、当当数值愈大数值愈大时时, ,其其优先权愈低优先权愈低; ;而有的系而有的系统恰恰相反。统恰恰相反。3737确定进程优先权的依据有如下三个方面确定进程优先权的依据有如下三个方面: :(1)(1)进程类型进程类型系统系统进程优先级进程优先级高高于于用户用户进程进程(2)(2)进程对资源的需求进程对资源的需求执行时间执行时间短短, ,内存要求内存要求小小的进程的进程, ,有较有较高高优先权。优先权。 (3)(3)用户要求用户要求根据用户进程根据用户进程紧迫紧迫程度及用户所付程度及用户所付费用费用的多少来确定。的多少来确定。静态优先权静态优先权特点特点: :(1)(1)系统简单易行。系统简单易行。(

34、2)(2)系统开销小。系统开销小。(3)(3)不够精确。不够精确。(4)(4)一般用在要求不高的系统中。一般用在要求不高的系统中。38382)2)动态优先权动态优先权在创建进程时所赋予的优先权在创建进程时所赋予的优先权, ,是可以随是可以随进程的推进进程的推进或或随其随其等待时间等待时间的增加而改变的的增加而改变的, ,以便获得更好的调度性以便获得更好的调度性能。能。例如例如, ,我们可以规定我们可以规定, ,在就绪队列中的进程在就绪队列中的进程, ,随其随其等待时等待时间的增长间的增长, ,其优先权以速率其优先权以速率a a提高。提高。若所有的进程都具有若所有的进程都具有相同相同的优先权的优

35、先权初值初值, ,则显然是最先则显然是最先进入就绪队列的进程进入就绪队列的进程, ,将因其动态优先权变得最高而优将因其动态优先权变得最高而优先获得处理机先获得处理机, ,此即先来先服务此即先来先服务FCFSFCFS算法。算法。若所有的就绪进程具有各若所有的就绪进程具有各不相同不相同的优先权的优先权初值初值, ,那么那么, ,对于优先权初值低的进程对于优先权初值低的进程, ,在等待了足够的在等待了足够的时间时间后后, ,其其优先权便可能升为最高优先权便可能升为最高, ,从而可以获得处理机从而可以获得处理机当采用抢占式优先权调度算法时当采用抢占式优先权调度算法时, ,如果再规定当前进程如果再规定当

36、前进程的优先权以速率的优先权以速率b b下降下降, ,则可则可防止一个长作业长期地防止一个长作业长期地垄垄断断处理机。处理机。39393.3.高响应比优先调度算法高响应比优先调度算法(HRF)(HRF)该算法是该算法是FCFSFCFS和和SJFSJF的结合的结合, ,克服了两种算法的缺点克服了两种算法的缺点响应比响应比最高的作业优先启动最高的作业优先启动由于由于等待时间等待时间与与服务时间服务时间之和之和, ,就是系统对该作业的就是系统对该作业的响响应时间应时间, ,故该优先权又相当于故该优先权又相当于响应比响应比R RP P。据此。据此, ,又可表又可表示为示为要求服务时间要求服务时间等待时

37、间优先权要求服务时间响应时间要求服务时间要求服务时间等待时间优先权4040对高响应比优先调度算法对高响应比优先调度算法(HRF)(HRF)的的解释解释 (1)(1)如果作业的如果作业的等待时间等待时间相同相同, ,则要求则要求服务的时间服务的时间愈愈短短, ,其优先权愈高其优先权愈高, ,因而该算法有利于短作业。因而该算法有利于短作业。 (2)(2)当当要求服务的时间要求服务的时间相同相同时时, ,作业的优先权决定于作业的优先权决定于其等待时间其等待时间, ,等待时间愈等待时间愈长长, ,其优先权愈其优先权愈高高, ,因而它实现的因而它实现的是是先来先服务先来先服务。 (3)(3)对于长作业对

38、于长作业, ,作业的优先级可以随作业的优先级可以随等待时间等待时间的的增增加加而提高而提高, ,当其等待时间足够长时当其等待时间足够长时, ,其优先级便可升到很其优先级便可升到很高高, ,从而也可获得处理机。从而也可获得处理机。 高响应比高响应比1 =1 =等待时间等待时间/ /服务时间服务时间41413.4.1 3.4.1 先来先服务和短作业优先算法先来先服务和短作业优先算法3.4.2 3.4.2 高优先权优先调度算法高优先权优先调度算法3.4.3 3.4.3 基于时间片的轮转调度算法基于时间片的轮转调度算法42423.4.3 3.4.3 基于时间片的轮转调度算法基于时间片的轮转调度算法 1

39、.1.时间片轮转法时间片轮转法 在早期的时间片轮转法中在早期的时间片轮转法中, ,系统将所有的就绪进程按系统将所有的就绪进程按先来先服务的原则先来先服务的原则, ,排成一个队列排成一个队列, ,每次调度时每次调度时, ,把把CPUCPU分配给队首进程分配给队首进程, ,并令其执行一个时间片并令其执行一个时间片, ,时间片的大时间片的大小从几小从几msms到几百到几百msms 当执行的时间片用完时当执行的时间片用完时, ,由一个由一个计时器计时器发出发出时钟中断时钟中断请求请求, ,调度程序便据此信号来停止该进程的执行调度程序便据此信号来停止该进程的执行, ,并将并将它送往就绪队列的末尾它送往就

40、绪队列的末尾; ;然后然后, ,再把处理机分配给就绪再把处理机分配给就绪队列中新的队首进程队列中新的队首进程, ,同时也让它执行一个时间片同时也让它执行一个时间片 可以保证就绪队列中的所有进程可以保证就绪队列中的所有进程, ,在一给定的时间内在一给定的时间内, ,均能获得一时间片的处理机执行时间均能获得一时间片的处理机执行时间4343图图3-5 3-5 多级反馈队列调度算法多级反馈队列调度算法 2.2.多级反馈队列调度算法多级反馈队列调度算法优先级高优先级高4444设置设置多个就绪队列多个就绪队列, ,并为各个队列赋予不同的优先级并为各个队列赋予不同的优先级第一个队列的优先级第一个队列的优先级

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

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

43、队列,如如此下去此下去, ,当一个长作业当一个长作业( (进程进程) )从第一队列依次降到第从第一队列依次降到第n n队列后队列后, ,在第在第n n队列中便采取按时间片轮转的方式运行。队列中便采取按时间片轮转的方式运行。4545仅当仅当第一队列空闲第一队列空闲时时, ,调度程序才调度第二队列中的进调度程序才调度第二队列中的进程运行程运行; ;仅当第仅当第1(i-1) 1(i-1) 队列均空时队列均空时, ,才会调度第才会调度第i i队列队列中的进程运行。中的进程运行。如果处理机正在第如果处理机正在第i i队列中为某进程服务时队列中为某进程服务时, ,又有新进又有新进程进入优先权较高的队列程进

44、入优先权较高的队列( (第第1(i-1)1(i-1)中的任何一个队中的任何一个队列列),),则此时新进程将则此时新进程将抢占抢占正在运行进程的处理机正在运行进程的处理机, ,即由即由调度程序把正在运行的进程放回到第调度程序把正在运行的进程放回到第i i队列的末尾队列的末尾, ,把把处理机分配给新到的高优先权进程。处理机分配给新到的高优先权进程。46463.3.多级反馈队列调度算法的性能多级反馈队列调度算法的性能(1)(1)终端型作业用户终端型作业用户终端型作业用户所提交的作业多属于终端型作业用户所提交的作业多属于交互型作业交互型作业, ,通常较通常较小小, ,系统只要能使这些作业在第一队列所规

45、系统只要能使这些作业在第一队列所规定的时间片内完成即可定的时间片内完成即可(2)(2)短批处理作业用户短批处理作业用户若若在第在第1 1队列中执行队列中执行一个时间片一个时间片即可完成即可完成, ,便可获得便可获得与终端型作业一样的响应时间与终端型作业一样的响应时间如在第一个队列中如在第一个队列中不能完成不能完成, ,只需在第只需在第2 2、3 3队列中队列中各执行一个时间片各执行一个时间片(3)(3)长批处理作业用户长批处理作业用户长作业将依次在第长作业将依次在第1,2,3,n1,2,3,n队列中执行队列中执行, ,最终按轮最终按轮转方式运行转方式运行4747内容概述内容概述3.1 3.1

46、处理机调度的层次处理机调度的层次3.2 3.2 调度队列模型和调度准则调度队列模型和调度准则3.3 3.3 调度算法调度算法 3.4 3.4 实时调度实时调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 48483.4.1 3.4.1 实现实时调度的基本条件实现实时调度的基本条件3.4.2 3.4.2 实时调度算法的分类实时调度算法的分类3.4.3 3.4.3 常用的几种实时调度算法常用的几种实时调度算法49493.4.1 3.4.1 实现实时调度的基本条件实现实时调度的基本条

47、件 1.1.提供必要的信息提供必要的信息 (1)(1)就绪时间就绪时间该任务成为就绪状态的起始时间。该任务成为就绪状态的起始时间。(2)(2)开始截止时间开始截止时间和和完成截止时间完成截止时间(3)(3)处理时间处理时间指一个任务从开始执行直至完成所需要的时间。指一个任务从开始执行直至完成所需要的时间。(4)(4)资源要求资源要求执行时所需资源。执行时所需资源。(5)(5)优先级优先级重大任务重大任务, ,赋予赋予“绝对绝对”优先级优先级, ,无重大影响无重大影响, ,可赋予可赋予“相对相对”优先级。优先级。50502.2.系统处理能力强系统处理能力强 在实时系统中在实时系统中, ,通常都有

48、着通常都有着多个多个实时任务。若处理机的实时任务。若处理机的处理能力处理能力不够强不够强, ,则有可能则有可能因处理机因处理机忙不过来而使某些实时忙不过来而使某些实时任务任务不能不能得到及时处理得到及时处理, ,从而导致发生难以预料的后果。假从而导致发生难以预料的后果。假定系统中有定系统中有m m个个周期性的硬实时任务周期性的硬实时任务, ,它们的处理时间可表示它们的处理时间可表示为为C Ci i, ,周期时间表示为周期时间表示为P Pi i, ,则在则在单处理机单处理机情况下情况下, ,必须满足下必须满足下面的限制条件面的限制条件, ,系统才是可调度的。系统才是可调度的。miiiPC1151

49、51 假如系统中有假如系统中有6 6个个硬实时任务硬实时任务, ,它们的周期时间都是它们的周期时间都是50 50 msms, ,而每次的处理时间为而每次的处理时间为10 ms10 ms, ,则不难算出则不难算出, ,此时是不能满此时是不能满足上式的足上式的, ,因而系统是因而系统是不可调度不可调度的。的。 解决的方法解决的方法是提高系统的处理能力是提高系统的处理能力, ,其途径有其途径有二二: :其一其一仍是采用单处理机系统仍是采用单处理机系统, , 但须但须增强其处理能力增强其处理能力, ,以显著地减以显著地减少对每一个任务的处理时间少对每一个任务的处理时间; ;其二是采用其二是采用多处理机

50、多处理机系统。假系统。假定系统中的处理机数为定系统中的处理机数为N N, ,则应将上述的限制条件改为则应将上述的限制条件改为: : miiiNPC152523.3.采用抢占式调度机制采用抢占式调度机制 当一个优先权更高的任务到达时当一个优先权更高的任务到达时, ,允许将当前任务暂时挂允许将当前任务暂时挂起起, ,而令高优先权任务立即投入运行而令高优先权任务立即投入运行, ,这样便可满足该这样便可满足该硬实时任硬实时任务对截止时间务对截止时间的要求。但这种调度机制比较复杂。的要求。但这种调度机制比较复杂。 对于一些对于一些小的小的实时系统实时系统, ,如果能预知任务的开始截止时间如果能预知任务的

51、开始截止时间, ,则对实时任务的调度可采用则对实时任务的调度可采用非抢占调度机制非抢占调度机制, ,以简化调度程序以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时和对任务调度时所花费的系统开销。但在设计这种调度机制时, ,应使所有的实时任务都比较小应使所有的实时任务都比较小, ,并在执行完关键性程序和临界并在执行完关键性程序和临界区后区后, ,能及时地将自己阻塞起来能及时地将自己阻塞起来, ,以便释放出处理机以便释放出处理机, ,供调度程供调度程序去调度那种序去调度那种开始截止时间开始截止时间即将到达的任务。即将到达的任务。 53534.4.具有快速切换机制具有快速切换机制

52、 该机制应具有如下两方面的能力该机制应具有如下两方面的能力: : (1)(1)对外部中断的快速响应能力对外部中断的快速响应能力。 为使在紧迫的外部事件请求中断时系统能及时响应为使在紧迫的外部事件请求中断时系统能及时响应, ,要求系统具有快速要求系统具有快速硬件中断机构硬件中断机构, ,还应使禁止中断的时间还应使禁止中断的时间间隔尽量短间隔尽量短, ,以免耽误时机以免耽误时机( (其它紧迫任务其它紧迫任务) )。 (2)(2)快速的任务分派能力快速的任务分派能力。 在完成任务调度后在完成任务调度后, ,便应进行任务切换。为了提高分便应进行任务切换。为了提高分派程序进行任务切换时的速度派程序进行任

53、务切换时的速度, ,应使系统中的每个运行功应使系统中的每个运行功能单位适当的小能单位适当的小, ,以减少任务切换的时间开销。以减少任务切换的时间开销。 54543.4.1 3.4.1 实现实时调度的基本条件实现实时调度的基本条件3.4.2 3.4.2 实时调度算法的分类实时调度算法的分类3.4.3 3.4.3 常用的几种实时调度算法常用的几种实时调度算法55553.4.2 3.4.2 实时调度算法的分类实时调度算法的分类 根据根据实时任务性质实时任务性质的不同的不同, ,可将实时调度算法分为可将实时调度算法分为: :(1)(1)硬实时调度算法硬实时调度算法(2)(2)软实时调度算法软实时调度算

54、法按按调度方式调度方式的不同的不同, ,可将实时调度算法分为可将实时调度算法分为: :(1)(1)非抢占调度算法非抢占调度算法(2)(2)抢占调度算法抢占调度算法因因调度程序调度时间调度程序调度时间的不同的不同, ,可将实时调度算法分为可将实时调度算法分为: :(1)(1)静态调度算法静态调度算法(2)(2)动态调度算法动态调度算法在在多处理机环境多处理机环境下下, ,可将实时调度算法分为可将实时调度算法分为: :(1)(1)集中式调度算法集中式调度算法(2)(2)分布式调度算法分布式调度算法56561.1.非抢占式调度算法非抢占式调度算法(1)(1)非抢占式非抢占式轮转轮转调度算法调度算法

55、常用于工业生产的群控系统中常用于工业生产的群控系统中调度程序每次选择队列中的调度程序每次选择队列中的第一个第一个任务运行任务运行一个一个任务运行后任务运行后排在轮转队列的排在轮转队列的末尾末尾, ,等待下次调度等待下次调度可用于要求可用于要求不太严格不太严格的实时控制系统中的实时控制系统中可获得仅可获得仅数秒数秒至至数十秒数十秒的响应时间的响应时间按按调度方式调度方式的不同的不同,可将实时调度算法分为可将实时调度算法分为:图图3-6 3-6 实时进程调度实时进程调度 57571.1.非抢占式调度算法非抢占式调度算法(1)(1)(2)(2)非抢占式非抢占式优先优先调度算法调度算法为时间要求严格的

56、任务分配为时间要求严格的任务分配较高优先级较高优先级当优先权当优先权高高的实时任务到来时的实时任务到来时, ,排在排在就绪队列就绪队列的队首的队首等待调度等待调度有可能获得仅有可能获得仅数秒数秒至至数百毫秒级数百毫秒级的响应时间的响应时间图图3-6 3-6 实时进程调度实时进程调度 (b) 非抢占优先权调度非抢占优先权调度当前进程当前进程实时进程实时进程实时进程请求调度实时进程请求调度当前进程运行完成当前进程运行完成调度时间调度时间58582.2.抢占式调度算法抢占式调度算法( (根据根据抢占发生时间抢占发生时间的不同的不同) )(1)(1)基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占

57、式优先权调度算法 某实时任务到达后某实时任务到达后, ,若优先级若优先级高于高于当前正在执行任当前正在执行任务的优先级务的优先级, ,并并不立即抢占不立即抢占当前任务的处理机当前任务的处理机, ,而而是等到是等到时钟中断时钟中断到来后调度程序才剥夺当前任务到来后调度程序才剥夺当前任务的执行的执行( (几十几十至至几几毫米毫米) )图图3-6 3-6 实时进程调度实时进程调度 59592.2.抢占式调度算法抢占式调度算法( (根据根据抢占发生时间抢占发生时间的不同的不同) )(1)(1)(2)(2)立即抢占立即抢占(Immediate Preemption)(Immediate Preempti

58、on)的优先权调度算法的优先权调度算法 一旦有外部中断一旦有外部中断, ,只要当前任务只要当前任务不在临界区内不在临界区内, ,便便立即剥夺当前任务的执行立即剥夺当前任务的执行, ,交处理机分配给要求中交处理机分配给要求中断的紧迫任务断的紧迫任务( (几几至至0.10.1毫米毫米)图图3-6 3-6 实时进程调度实时进程调度 60603.4.1 3.4.1 实现实时调度的基本条件实现实时调度的基本条件3.4.2 3.4.2 实时调度算法的分类实时调度算法的分类3.4.3 3.4.3 常用的几种实时调度算法常用的几种实时调度算法61613.4.3 3.4.3 常用的几种实时调度算法常用的几种实时

59、调度算法 图图3-7 EDF3-7 EDF算法用于算法用于非抢占非抢占调度方式调度方式 1.1.最早截止时间优先最早截止时间优先EDF(Earliest Deadline FirstEDF(Earliest Deadline First) )算法算法根据任务的根据任务的开始截止时间开始截止时间来确定任务的优先级来确定任务的优先级, ,截止时截止时间越早优先级越高间越早优先级越高既可用于既可用于抢占式调度抢占式调度也可用于也可用于非抢占式调度非抢占式调度方式方式1342开始截止时间开始截止时间任务执行任务执行任务到达任务到达12 341342t62622.2.最低松弛度优先即最低松弛度优先即LL

60、F(Least Laxity First)LLF(Least Laxity First)算法算法根据任务紧急根据任务紧急( (或松弛或松弛) )的程度的程度, ,来确定任务的优先级来确定任务的优先级。任务的紧急程度愈高任务的紧急程度愈高, ,为该任务所赋予的优先级就愈高为该任务所赋予的优先级就愈高, , 以使之优先执行以使之优先执行例如例如, ,一个任务在一个任务在200ms200ms时必须完成时必须完成, ,而它本身所需的运而它本身所需的运行时间就有行时间就有100ms100ms, ,因此因此, ,调度程序必须在调度程序必须在100 ms100 ms之前调之前调度执行度执行, ,该任务的紧急