操作系统第三章

1、1 在多道程序系统中，进程数目往往多在多道程序系统中，进程数目往往多于处理机数目。要求系统能按某种算法，于处理机数目。要求系统能按某种算法，动态地把处理机分配给就绪队列中的进程，动态地把处理机分配给就绪队列中的进程，使之执行。而系统的运行性能，如吞吐量使之执行。而系统的运行性能，如吞吐量地大小、周转时间的长短、响应的及时性地大小、周转时间的长短、响应的及时性等，在很大程度上都取决于处理机调度。等，在很大程度上都取决于处理机调度。23处理器调度的三级模型如图处理器调度的三级模型如图3.33.3所示。所示。图图3.3 3.3 处理器三级调度模型处理器三级调度模型进程挂起就绪队列进程挂起就绪队列进

2、程 阻 塞进 程 阻 塞队列队列进程挂起阻塞队列进程挂起阻塞队列进程就绪队列进程就绪队列完成完成中 级中 级调度调度低级调度低级调度处理器处理器高级调度高级调度作业后备队列作业后备队列交互式用户交互式用户提交提交用户作业用户作业5 3.1.1 3.1.1 处理机调度的层次处理机调度的层次1 1 高级调度高级调度 又称为作业调度或长程调度又称为作业调度或长程调度(long-term (long-term scheduling),scheduling),用于决定把外存上处于后备队列中的用于决定把外存上处于后备队列中的作业调入内存，并为他们创建进程、分配必要的资作业调入内存，并为他们创建进程、分配必

3、要的资源，然后，再将新创建的进程排在就绪队列上，准源，然后，再将新创建的进程排在就绪队列上，准备执行。备执行。 作业作业: :用户提交给系统处理的一个任务用户提交给系统处理的一个任务. .包括用包括用户程序户程序数据数据对程序运行进行控制和处理有关的对程序运行进行控制和处理有关的信息信息. .分为批处理作业和终端型作业分为批处理作业和终端型作业. . 分时和实时系统中不设置高级调度。？分时和实时系统中不设置高级调度。？6 每次执行作业调度时，都需作出以下两每次执行作业调度时，都需作出以下两个决定：个决定： 接纳多个作业接纳多个作业: :取决于系统的多道程序度取决于系统的多道程序度. . 接纳哪

4、些作业接纳哪些作业: :取决于系统调度算法：先取决于系统调度算法：先来先服务来先服务, ,优先级优先级, ,响应比等响应比等. .72 2 低级调度（低级调度（low level Schedulinglow level Scheduling） 又称为进程调度或短程调度又称为进程调度或短程调度. .它决定就绪队列它决定就绪队列中的哪个进程将获得处理机，然后分派程序执行把中的哪个进程将获得处理机，然后分派程序执行把处理机分派给该进程的操作。可分为两种方式：处理机分派给该进程的操作。可分为两种方式：非抢占方式（非抢占方式（Non-preemaptive ModeNon-preemaptive Mod

5、e）: : 一旦把处理机分配给进程后便让该进程一直执一旦把处理机分配给进程后便让该进程一直执行行, ,直至完成或发生事件而被阻塞时直至完成或发生事件而被阻塞时, ,才再把处理机才再把处理机分配给其它进程分配给其它进程, ,不允许某进程抢占已经分配出去不允许某进程抢占已经分配出去的处理机的处理机. . 优点优点: :简单简单, ,系统开销小系统开销小, ,适合在批处理系统环境适合在批处理系统环境. . 缺点缺点: :实时性差实时性差. .8抢占方式（抢占方式（Preemptive ModePreemptive Mode）: : 允许调度程序根据某种原则去停止某个正允许调度程序根据某种原则去停止某

6、个正在执行的进程，将已分配的处理机重新分配给在执行的进程，将已分配的处理机重新分配给另一进程另一进程. . 抢占原则抢占原则: : a. a.优先权原则优先权原则. . b.b.短作业（进程）优先原则短作业（进程）优先原则. . c.c.时间片原则时间片原则. .9 3 3 中级调度（中级调度（Intermediate-Level Scheduling Intermediate-Level Scheduling ） 又称为中程调度。目的是提高内存的利用率又称为中程调度。目的是提高内存的利用率和系统吞吐量。和系统吞吐量。 操作是将暂时不能运行的进程从内存中调到操作是将暂时不能运行的进程从内存中调

7、到外存上去，该进程为外存就绪或外存挂起状态。外存上去，该进程为外存就绪或外存挂起状态。当这些进程重又具备运行条件、且内存又有空闲当这些进程重又具备运行条件、且内存又有空闲时，时，由中级调度来决定将外存上具备运行的就绪由中级调度来决定将外存上具备运行的就绪进程重新从外存调入到内存，修改状态为就绪，进程重新从外存调入到内存，修改状态为就绪，等待进程调度。等待进程调度。 10在这三种调度方式中：在这三种调度方式中：进程调度的运行频率最高：分时系统中进程调度的运行频率最高：分时系统中10-10010-100msms进行一次进程调度，所以进程调度算法不能太复进行一次进程调度，所以进程调度算法不能太复杂，

8、不能占用太多杂，不能占用太多CPUCPU时间。时间。作业调度往往发生在一个批处理作业运行完毕，作业调度往往发生在一个批处理作业运行完毕，作业调度的周期较长，大约几分钟。作业调度的周期较长，大约几分钟。中级调度介于以上两者之间。中级调度介于以上两者之间。11 3.1.23.1.2处理机调度算法的目标处理机调度算法的目标 1 1 处理机调度算法的共同目标处理机调度算法的共同目标（1）资源利用率；（2）公平性；（3）平衡性；（4）策略强制执行。 CPU的利用率:CPU的有效工作时间/(CPU的有效工作时间+CPU的等待时间）122 2 批处理系统的目标批处理系统的目标（1）平均周转时间短；（2）系统

9、吞吐量高；（3）处理机利用率高。周转时间：提交给系统开始到完成结束。133 3 分时系统的目标分时系统的目标（1）响应时间快；（2）均衡性。4 4 实时系统的目标实时系统的目标（1）截止时间的保证；（2）可预测性。14选择调度方式和算法的若干准则选择调度方式和算法的若干准则可分为面向用户和面向系统的准则：可分为面向用户和面向系统的准则： 1 1 面向用户准则：面向用户准则： （1 1）周转时间短周转时间短( (周转时间与平均周转时间概念周转时间与平均周转时间概念).). 带权周转时间带权周转时间: :作业的周转时间与系统为它实作业的周转时间与系统为它实际服务时间之比际服务时间之比.(.(大于等

10、于大于等于1,1,越小越好越小越好) ) （2 2）响应时间快）响应时间快( (响应时间概念响应时间概念).). （3 3）截止时间的保证）截止时间的保证( (截止时间概念截止时间概念).). （4 4）优先权准则）优先权准则. .15 2 2 面向系统准则：面向系统准则： (1) (1)系统吞吐量系统吞吐量. . (2) (2)处理机利用率好处理机利用率好. . (3) (3)各类资源的平衡利用各类资源的平衡利用. . 16 1 1 作业和作业步作业和作业步 作业：作业： 它不仅包含了通常的程序和数据，而且还它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程应配

11、有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中是以作业为基序的运行进行控制。在批处理系统中是以作业为基本单位从外存调入内存的。本单位从外存调入内存的。 作业步（作业步（JobJob stepstep）：）：各作业步之间存在着相互联各作业步之间存在着相互联系，往往是上一个作业步的输出作为下一个作业步系，往往是上一个作业步的输出作为下一个作业步的输入。的输入。17 2 2 作业控制块作业控制块 在多道批处理系统中，为每个作业设置了一个作业控制在多道批处理系统中，为每个作业设置了一个作业控制块块JCBJCB，以管理和调度作业。它是作业在系统中存在的标志。，以管理和调度作业。

12、它是作业在系统中存在的标志。 通常在通常在JCBJCB中包含的内容有：中包含的内容有： 作业标识、用户名称、用户账号、作业类型、作业状况、作业标识、用户名称、用户账号、作业类型、作业状况、调度信息、资源需求、资源使用情况等。调度信息、资源需求、资源使用情况等。18 3 3作业运行的三个阶段和三种状态作业运行的三个阶段和三种状态 作业从进入系统到运行结束，通常需要经历收容、运行作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有和完成三个阶段。相应的作业也就有“后备状态后备状态”、“运运行状态行状态”、“完成状态完成状态”。 （1 1）收容阶段；）收容阶段； （2 2

13、）运行阶段；）运行阶段； （3 3）完成阶段。）完成阶段。19 作业调度：也称接纳调度。其主要任务是根据作业调度：也称接纳调度。其主要任务是根据JCBJCB中的中的信息，检查系统中的资源能否满足作业对资源的需求，以信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后业调入内存，并为它们创建进程、分配必要的资源。然后在将新创建的进程排在就绪队列上等待调度。在将新创建的进程排在就绪队列上等待调度。 每次执行作业调度时，都需要做出以下两个决定：每次执行作

14、业调度时，都需要做出以下两个决定： 1 1、接纳多少个作业；、接纳多少个作业； 2 2、接纳哪些作业。、接纳哪些作业。20 1 1 先来先服务（先来先服务（FCFS)FCFS)调度算法调度算法 作业调度：作业调度： 每次调度是从后备作业队列中，选择每次调度是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内一个或多个最先进入该队列的作业，将它们调入内存，并分配资源、创建进程，然后放入就绪队列。存，并分配资源、创建进程，然后放入就绪队列。 进程调度：进程调度：每次调度是从就绪队列中，选择一个最每次调度是从就绪队列中，选择一个最先进入该队列的进程，把处理机分配给它，使之投先进入该队

15、列的进程，把处理机分配给它，使之投入运行。入运行。 21进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A010111B110011011001C21101102100100D31001022021991.99 FCFSFCFS算法比较有利于长作业（进程），而算法比较有利于长作业（进程），而不利于短作业（进程）。在应用中也就是利于不利于短作业（进程）。在应用中也就是利于CPUCPU繁忙型作业（进程），而不利于繁忙型作业（进程），而不利于I/OI/O繁忙型繁忙型作业（进程）。作业（进程）。22SJ(P)FSJ(P)F是指

16、对短作业或短进程优先调度的算法。是指对短作业或短进程优先调度的算法。 短作业短作业( (SJF)SJF)的调度算法可以照顾实际上占很的调度算法可以照顾实际上占很大比例的短作业大比例的短作业, ,使其能比长作业优先执行使其能比长作业优先执行. .从作从作业的后备队列中选则一个或若干个短作业到内存业的后备队列中选则一个或若干个短作业到内存就绪队列就绪队列. . 短进程短进程( (SPF)SPF)的调度算法从内存就绪队列中选的调度算法从内存就绪队列中选则一个运行时间最短的进程到处理机中执行则一个运行时间最短的进程到处理机中执行. .23 作业情况调度算法进程名ABCDE平均到达时间01234服务时间

17、43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.124SJ(P)FSJ(P)F调度算法存在的问题调度算法存在的问题: :该算法对长作业非常不利该算法对长作业非常不利. .可能长期得不到调可能长期得不到调度度. .该算法完全未考虑作业的紧迫程度该算法完全未考虑作业的紧迫程度, ,不能保证不能保证紧迫性作业或进程会得到及时处理紧迫性作业或进程会得到及时处理. .由于作业由于作业( (进程进程) )的长短只是根据用户所提供的的长短只是根据用户所提供的

18、估计执行时间而定估计执行时间而定, ,而用户又可能估计不准而用户又可能估计不准, ,致致使该算法不一定能真正作到短作业使该算法不一定能真正作到短作业( (进程进程) )优先优先调度调度. .25Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.04SJF (non-preemptive非抢占非抢占)Average waiting time = (0 + 6 + 3 + 7)/4 = 4P1P3P273160P481226Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.0

19、4SJF (preemptive抢占抢占)Average waiting time = (9 + 1 + 0 +2)/4 =3P1P3P242110P457P2P11627 此调度的算法是：当进程调度时，把处理机此调度的算法是：当进程调度时，把处理机分配给就绪队列中优先权最高的进程。分配给就绪队列中优先权最高的进程。 1 1 优先权调度算法类型优先权调度算法类型 a.a.非强占式非强占式: : 系统按照优先权的高低进行调度系统按照优先权的高低进行调度, ,进程调度时进程调度时把处理机分配给具有高优先权的进程把处理机分配给具有高优先权的进程, ,直到该进程直到该进程完成后才放弃处理机完成后才放弃

20、处理机. . 适用于实时性要求不严的实时系统中适用于实时性要求不严的实时系统中. . b. b.强占式强占式: : 在处理机分配上优先权高的进程会停止优先在处理机分配上优先权高的进程会停止优先权低的进程的执行而得到处理机权低的进程的执行而得到处理机. .282.2.优先权的类型：优先权的类型： （1 1）静态优先权）静态优先权, ,进程创建时确定，用一固定进程创建时确定，用一固定数值表示数值表示, ,在进程的整个执行期间保持不变在进程的整个执行期间保持不变. . 确定进程优先权的依据确定进程优先权的依据: :w进程类型进程类型: :系统进程高于用户进程系统进程高于用户进程. .w进程对资源的要

21、求进程对资源的要求: :运行时间短的进程优先权高运行时间短的进程优先权高. .w根据用户要求根据用户要求: :用户紧迫程度及用户付费情况用户紧迫程度及用户付费情况. . （2 2）动态优先权，优先权随进程的推进而改）动态优先权，优先权随进程的推进而改变变: :优先权初值相同的进程最先进入的进程会先得优先权初值相同的进程最先进入的进程会先得到处理机到处理机. .29 在批处理系统中在批处理系统中, ,作业调度的短作业优先作业调度的短作业优先算法是一个比较好的算法算法是一个比较好的算法, ,对长作业如果引入对长作业如果引入动态优先权机制动态优先权机制, ,则长作业在等待一定的时间则长作业在等待一定

22、的时间后后, ,必然有机会分配到处理机必然有机会分配到处理机. . 优先权的变化可描述为：优先权的变化可描述为： 30响应比响应比RpRp可表示为：可表示为：w该算法有利于短作业该算法有利于短作业: :等待时间相同等待时间相同, ,要求服务要求服务越短越短, ,其优先权越高其优先权越高. .w实现了先来先服务实现了先来先服务: :要求服务时间相同时要求服务时间相同时, ,作业作业的优先权决定于其等待时间的优先权决定于其等待时间. .w长作业当其等待时间足够长时长作业当其等待时间足够长时, ,优先权便可以优先权便可以升高升高, ,也可获得处理机也可获得处理机. .313.3.3.3.1 1 进程

23、调度的任务、机制和方式进程调度的任务、机制和方式 1 1、进程调度的任务、进程调度的任务 （1）保存处理机的现场消息；（2）按某种算法提取进程；（3）把处理器分配给进程。2 2、进程调度机制、进程调度机制（1）排队器；（2）分派器；（3）上下文切换器。32就绪进程进程控制块就绪队列排队器分派器上下文切换器CPU进程调度机制来自其他状态移出运行进程调度程序333 3、进程调度方式、进程调度方式1）非抢占方式2）抢占方式抢占方式遵循的主要原则有：优先权原则；短进程优先原则；时间片原则。非抢占方式存在着很大的局限性，很难满足交互性作业和实时任务的需求。341 1、轮转法的基本原理、轮转法的基本原理

24、在轮转法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。并保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。2 2、进程切换时机、进程切换时机 1）一个时间片尚未用完； 2）一个时间片用完时。353 3、时间片大小的确定、时间片大小的确定 时间分配给进程的时间片交互结束响应时间 s时间片 q时间片大于交互时间q-s363 3、时间片大小的确定、时间片大小的确定 时间分配给进程的时间片进程被抢占时间片 q时间片小于交互时间分配给进程的时间片交互完成其他进程运行37时间片轮转法时间片轮转法 在分时系统中，系统使每个进程依次地按时在分时系统中，系统使每个进程依次地按时

25、间片轮流的方式执行，就绪进程按先来先服务原间片轮流的方式执行，就绪进程按先来先服务原则；当执行的时间片用完时，由一个计时器发出则；当执行的时间片用完时，由一个计时器发出时钟中断，将它送就绪队列的末尾，等待下一次时钟中断，将它送就绪队列的末尾，等待下一次执行。执行。 时间片大小的确定因素：时间片大小的确定因素： a. a.系统对响应时间的要求；系统对响应时间的要求； b. b.就绪队列中进程的数目；就绪队列中进程的数目； c. c.系统的处理能力。系统的处理能力。 380 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 170 01 02 03 0

26、4 05 06 07 08 09 10 11 12 13 14 15 16 17A AB BD DC CE EA AB BD DC CE EA AB BD DC CE EA AC CE EA AB BC CE E时间片时间片q=1q=1时时时间片时间片q=4q=4时时39 作业情况调度算法进程名ABCDE平均到达时间01234服务时间43424RR(q=1)完成时间151216917周转时8带权周转时间 3.753.673.533.333.46RR(q=4)完成时间47111317周转时间46910138.4带权周转时间122.2553.332.540Turnarou

27、nd Time(周转时间）周转时间） Varies With The Time Quantum41 1 1. . 优先级调度算法的类型优先级调度算法的类型 非抢占式优先级调度算法； 抢占式优先级调度算法。2 2. . 优先级的类型优先级的类型 1）静态优先级 确定进程优先级大小的依据有：进程类型、 进程对资源的需求、用户要求。 2）动态优先级 42 在实际的计算机系统中在实际的计算机系统中, ,不少都配置了几种不少都配置了几种类型的操作系统类型的操作系统, ,既有批处理型作业既有批处理型作业, ,又有处理又有处理交互型作业的分时操作系统交互型作业的分时操作系统, ,前台交互型进程采前台交互型进

28、程采用时间片轮转调度算法用时间片轮转调度算法, ,后台批处理型作业的进后台批处理型作业的进程会采用优先权高者优先的算法程会采用优先权高者优先的算法. . 根据作业的性质或类型的不同根据作业的性质或类型的不同, ,将就绪进程将就绪进程队列再分为若干个独立子队列队列再分为若干个独立子队列, ,每个队列采用一每个队列采用一种算法种算法, ,不同的队列采用不同的调度算法不同的队列采用不同的调度算法. . 43Multilevel Queue Scheduling44 (1) (1)调度算法调度算法: :设置多个就绪队列并为各个队列赋予不同的优先权设置多个就绪队列并为各个队列赋予不同的优先权: :第一个

29、队列的优先权最高第一个队列的优先权最高, ,依次降低依次降低; ;赋予各个不同队列中进程执行时间片的大小也各不赋予各个不同队列中进程执行时间片的大小也各不相同相同, ,优先权越高的队列进程执行的时间片越短优先权越高的队列进程执行的时间片越短. .新进程进入内存后新进程进入内存后, ,首先放到第一队列的末尾首先放到第一队列的末尾, ,按按FCFSFCFS原则排队等待调度原则排队等待调度. .如果执行一个时间片不能完如果执行一个时间片不能完成成, ,则转入第二队列的末尾则转入第二队列的末尾, ,同样进行同样进行. .仅当第一队列空闲时仅当第一队列空闲时, ,调度程序才调度第二队列中的调度程序才调度

30、第二队列中的进程运行进程运行, ,依次类推依次类推. .4546(2)(2)调度性能调度性能: : 能够满足各种类型用户的需要能够满足各种类型用户的需要: :终端型作业终端型作业: :交互作业交互作业, ,作业通常较短小作业通常较短小, ,系统只系统只要能估计适合的时间片大小使作业要能估计适合的时间片大小使作业( (进程进程) )在第一在第一队列所规定的时间片完成队列所规定的时间片完成, ,便能满足用户便能满足用户. .短批处理作业用户短批处理作业用户: :通常会在第一或第二队列完通常会在第一或第二队列完成成, ,其周转时间仍然较短其周转时间仍然较短. .长批处理作业长批处理作业: :依次按不

31、同的队列和不同的时间依次按不同的队列和不同的时间片直到完成片直到完成, ,用户不必担心其作业得不到处理用户不必担心其作业得不到处理. .47 UNIXUNIX和和OS/2OS/2操作系统采用了该调度算法操作系统采用了该调度算法. .该调度算法是目前公认得较好的一种调度算该调度算法是目前公认得较好的一种调度算法法. .48 1 1 保证调度算法保证调度算法: : 保证调度算法是另外一种类型的调度算法，它向用户所做出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。 2 2 公平公享调度算法公平公享调度算法: : 分配给每个进程相同的处理机时间。 49 1 1 提供必要的调度信

32、息提供必要的调度信息: :w就绪时间就绪时间; ;w开始截止时间和完成截止时间开始截止时间和完成截止时间; ;w处理时间处理时间; ;w资源要求资源要求; ;w优先级优先级. . 502 2 系统处理能力强系统处理能力强 在实时系统中，通常有多个实时任务，如果处在实时系统中，通常有多个实时任务，如果处理机处理能力不强，则因处理机忙不过来而使得理机处理能力不强，则因处理机忙不过来而使得某些实时任务得不到及时处理。某些实时任务得不到及时处理。假定系统中有假定系统中有m m个周期性的硬实时任务，它们的处个周期性的硬实时任务，它们的处理时间可表示为理时间可表示为Ci,Ci,周期时间可表示为周期时间可表

33、示为Pi,Pi,则在单则在单处理机情况下，必须满足下面的限制条件系统才处理机情况下，必须满足下面的限制条件系统才是可调度的是可调度的: :11miiiPC51 如果系统中有如果系统中有6 6个硬实时任务个硬实时任务, ,它们的周期它们的周期时间都是时间都是5050ms,ms,而每次的处理时间为而每次的处理时间为1010ms,ms,则不则不能满足限制条件能满足限制条件, ,系统是不可调度的系统是不可调度的. . 解决的方法是提高系统的处理能力解决的方法是提高系统的处理能力: :w采用单处理机系统增强处理能力采用单处理机系统增强处理能力, ,减少每一任减少每一任务的处理时间务的处理时间; ;w采用

34、多处理机系统采用多处理机系统: :多处理机数目为多处理机数目为N,N,则限制则限制条件改为条件改为: :NPCmiii1523.3.采用抢占式调度机制采用抢占式调度机制: : 在含有硬实时任务的实时系统中在含有硬实时任务的实时系统中, ,广泛采用抢广泛采用抢占机制。当一个优先权更高的任务到达时，允许占机制。当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投将当前任务暂时挂起，而令高优先权任务立即投入运行。这样便可以满足硬实时任务对截止时间入运行。这样便可以满足硬实时任务对截止时间的要求。的要求。 小的实时系统，如果可以预知任务的开始截止小的实时系统，如果可以预知任务的

35、开始截止时间则实时任务的调度可采用非抢占调度方式时间则实时任务的调度可采用非抢占调度方式. .但但在设计调度机制时，应使所有的实时任务都比较在设计调度机制时，应使所有的实时任务都比较小，并在执行关键性程序和临界区后，能及时阻小，并在执行关键性程序和临界区后，能及时阻塞，释放出处理机，使得其它程序的截止时间要塞，释放出处理机，使得其它程序的截止时间要求能够满足。求能够满足。534 4 具有快速切换机制具有快速切换机制为了保证要求较高的硬实时任务能够及时运行，为了保证要求较高的硬实时任务能够及时运行，在实时系统中还应该具有快速切换机制。该机在实时系统中还应该具有快速切换机制。该机制具有如下能力：制

36、具有如下能力：（1 1）快速响应外部中断的能力）快速响应外部中断的能力. . (2) (2) 快速任务分派能力快速任务分派能力. .54 1. 1. 非抢占式调度算法非抢占式调度算法(1)(1)非抢占式轮转调度算法非抢占式轮转调度算法: :只适用于实时信息只适用于实时信息处理处理, ,群控系统，不适用于实时控制系统群控系统，不适用于实时控制系统. .(2)(2)非抢占优先权调度算法非抢占优先权调度算法: :调度要求严格的实调度要求严格的实时任务，为之分配高的优先权，使得其能够时任务，为之分配高的优先权，使得其能够处于调度队列之首。适用于一定要求的实时处于调度队列之首。适用于一定要求的实时控制系

37、统控制系统. .552 2 抢占式调度算法抢占式调度算法（1 1）基于时钟中断的抢占式优先调度算法）基于时钟中断的抢占式优先调度算法实时任务到达后，并不立即抢占处理机，优先级高实时任务到达后，并不立即抢占处理机，优先级高的任务在时钟中断到来时抢占处理机。一旦出现外的任务在时钟中断到来时抢占处理机。一旦出现外部中断部中断, ,只要当前任务未处于临界区只要当前任务未处于临界区, ,便能立即剥夺便能立即剥夺当前任务的执行当前任务的执行, ,把处理机分配给请求中断的紧迫把处理机分配给请求中断的紧迫任务任务. (3). (3)基于时钟中断抢占的优先级调度算法基于时钟中断抢占的优先级调度算法: :时时钟中

38、断到来时钟中断到来时, ,立即抢占处理机立即抢占处理机. .563.4.3.4.3 3 最早截止时间优先最早截止时间优先EDFEDF算法算法 1 1 非抢占式调度方式用于非周期实时任务非抢占式调度方式用于非周期实时任务1342EDF算法用于非抢占调度方式开始截止时间任务执行任务到达12341234573.4.3.4.4 4 最低松弛度优先最低松弛度优先LLFLLF算法算法 该算法在确定任务的优先级时，根据的是任务的紧急（或松弛）程度。任务紧急情况愈高，赋予该任务的优先级就愈高，以使之优先执行。tt1t2t3t4t5t6t7t801030407080A1(10)A2(10)A3(10)A4(10

39、)B1(20)B1(5)B2(15)B2(10)利用利用ELLFELLF算法进行调度的情况算法进行调度的情况583.4.3.4.5 5 优先级倒置优先级倒置 优先级倒置的形成优先级倒置的形成 高优先级P1因共享着“临界资源”的低优先级进程P3被阻塞了，又因为另一个地优先级进程P2的存在而延长了P1被阻塞的时间。由此所产生的“优先级倒置”。2.2. 优先级倒置的解决方法优先级倒置的解决方法 一种简单的解决方法是规定：P3在进入临界区后P3所占用的处理机就不允许被抢占。 一个比较实用的方法是建立在动态优先级继承基础上的。“优先级倒置”即高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞。59

40、 调度部分例题调度部分例题(1)(1)设一组作业，他们的提交时间及运行时间如下：设一组作业，他们的提交时间及运行时间如下： 作业名作业名 提交时间提交时间 运行时间（分钟）运行时间（分钟） A 8A 8：00 7000 70 B 8B 8：40 3040 30 C 8C 8：50 10 50 10 D 9D 9：10 5 10 5 在单道方式下，采用短作业优先调度算法，试指在单道方式下，采用短作业优先调度算法，试指出作业的执行顺序和周转时间及带权周转时间。出作业的执行顺序和周转时间及带权周转时间。60作业的执行顺序为作业的执行顺序为: :A,D,C,B.A,D,C,B.作业作业名名提交时提交时

41、间间运行运行时间时间(分钟分钟)开始执开始执行时间行时间完成时完成时间间周转周转时间时间(分钟分钟)带权周带权周转时间转时间(分钟分钟)A8:00708:009:10701B8:40309:259:55752.5C8:50109:159:25353.5D9:1059:109:155161 (2) (2) 设有四道作业，它们的到提交时间和执行时设有四道作业，它们的到提交时间和执行时间如下：间如下： 作业号作业号 提交时间提交时间 运行时间运行时间 A 9.0 2.0A 9.0 2.0 B 9.2 1.0B 9.2 1.0 C 9.4 0.5 C 9.4 0.5 D 9.5 0.3 D 9.5 0

42、.3 试计算在单道程序设计环境下，采用先来先服务试计算在单道程序设计环境下，采用先来先服务调度算法和短作业优先调度算法时它们的调度调度算法和短作业优先调度算法时它们的调度序列及平均周转时间和平均带权周转时间。序列及平均周转时间和平均带权周转时间。 62解：若采用先来先服务调度算法，其调度顺序解：若采用先来先服务调度算法，其调度顺序为为A A，B B，C C，D D。 作业作业号号提交提交时间时间运行时运行时间间开始执开始执行时间行时间完成时完成时间间周转周转时间时间带权周带权周转时间转时间A9.02.09.011.02.01.0B9.21.011.012.02.82.8C9.40.512.01

43、2.53.16.2D9.50.312.512.83.311.063平均周转时间平均周转时间T=T=（2.0+2.8+3.1+3.32.0+2.8+3.1+3.3）/4=2.8/4=2.8平均带权周转时间平均带权周转时间W=W=（1+2.8+6.2+111+2.8+6.2+11）/4=5.25/4=5.2564若采用短作业优先调度算法，其调度顺序为若采用短作业优先调度算法，其调度顺序为A A，D D，C C，B B。 作业作业号号提交时提交时间间运行运行时间时间开始执开始执行时间行时间完成时完成时间间周转周转时间时间带权周带权周转时间转时间A9.02.09.011.02.01.0D9.50.31

44、1.011.31.86.0C9.40.511.311.82.44.8B9.21.011.812.83.63.665平均周转时间平均周转时间T=T=（2.0+1.8+2.4+3.62.0+1.8+2.4+3.6）/4=2.45/4=2.45平均带权周转时间平均带权周转时间W=W=（1+6+4.8+3.61+6+4.8+3.6）/4=3.85/4=3.8566 (3) (3) 设有五道进程设有五道进程A,B,C,D,E,A,B,C,D,E,几乎同时提交，它几乎同时提交，它们的运行时间及优先级分别为们的运行时间及优先级分别为: : 作业号作业号 运行时间运行时间( (分钟分钟) ) 优先级优先级 A

45、 10 24A 10 24 B 6 30B 6 30 C 2 21 C 2 21 D 4 20D 4 20 E 8 28 E 8 28假如数字越大优先级越高假如数字越大优先级越高, ,试计算采用优先级调度试计算采用优先级调度算法和时间片为算法和时间片为1 1分钟的轮转调度算法的平均周分钟的轮转调度算法的平均周转时间和平均带权周转时间转时间和平均带权周转时间. .67进程进程号号运行运行时间时间优先优先级级开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A1024024242.4B6300661.0C2210262613D420030307.5E828014143

46、.6优先级调度算法调度顺序为优先级调度算法调度顺序为B B，E E，A A，C,DC,D。平均周转时间平均周转时间(24+6+26+30+14)/5=20(24+6+26+30+14)/5=20(分钟分钟) )68时间片调度算法调度顺序为时间片调度算法调度顺序为: :A B C D E A B C D E A B D A B C D E A B C D E A B D 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 E A B D E A B E A B E A EE A B D E A B E A B E A E13 14

47、15 16 17 18 19 20 21 22 23 24 2513 14 15 16 17 18 19 20 21 22 23 24 25A E A AA E A A27 28 29 3027 28 29 3069平均周转时间平均周转时间(30+22+7+16+28)/5=20.6(30+22+7+16+28)/5=20.6(分钟分钟) )作业作业号号运行运行时间时间优先优先级级开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间A1024030303.0B630022223.67C2210773.5D420016164.0E828028283.5703.5.13

48、.5.1 资源问题资源问题 在系统中有许多不同类型的资源，其中可以引起死锁的主要是，需要采用互斥访问方法的、不可以被抢占的资源。 可重用性资源；可重用性资源； 消耗性资源；消耗性资源； 可抢占性资源；可抢占性资源； 不可抢占性资源。不可抢占性资源。 713.5.23.5.2 计算机系统中的死锁计算机系统中的死锁(1)(1)竞争资源竞争资源 资源分为资源分为: :可剥夺性可剥夺性: :如处理机如处理机. . 非剥夺性非剥夺性: :如打印机如打印机. .n竞争非剥夺性资源引起死锁竞争非剥夺性资源引起死锁: : 例例: :两个进程两个进程P1,P2,P1,P2,两个非剥夺性资源两个非剥夺性资源R1,

49、R2;R1,R2; P1: P1: 得到得到R1;R1; P2:P2:得到得到R2;R2; 申请申请R2;R2; 申请申请R1;R1;72共享文件时的死锁情况P1P1F1F2P2P2P1Open(f1,w);Open(f2,w);P2Open(f2,w);Open(f1,w);73w竞争临时性资源引起死锁竞争临时性资源引起死锁: :临时性资源临时性资源: :一个进程产生一个进程产生, ,另一个进程暂时使用另一个进程暂时使用. .例例: :进程进程P1,P2,P3,P1,P2,P3,临时资源临时资源S1,S2,S3;S1,S2,S3; P1( P1(产生产生S1,S1,需要需要S3);S3);

50、P2( P2(产生产生S2,S2,需要需要S1);S1); P3( P3(产生产生S3,S3,需要需要S2);S2);74进程之间通信时的死锁P1P1m3m1P P3 3P1 send(P2,m1); receive(P3,m3);P2 send(P3,m2); receive(P1,m1);P3 send(P1,m3); receive(P2,m2);P2P2m275如果按顺序如果按顺序: : P1: P1:Release(S1);Request(S3);Release(S1);Request(S3); P2: P2:Release(S2);Request(S1);Release(S2);R

51、equest(S1); P3: P3:Release(S3);Request(S2);Release(S3);Request(S2);不会发生死锁不会发生死锁. .如果按顺序如果按顺序: : P1: P1:Request(S3);Release(S1);Request(S3);Release(S1); P2: P2:Request(S1);Release(S2);Request(S1);Release(S2); P3: P3:Request(S2);Release(S3);Request(S2);Release(S3);可能会发生死锁可能会发生死锁. .76(2)(2)进程推进顺序非法进程推进

52、顺序非法: :两个进程两个进程P1,P2,P1,P2,两个资源两个资源R1,R2;R1,R2;如果如果: :P1 Request(P1 Request(R1R1); ); P1 P1 Request(R2);Request(R2); P1 Release(R1); P1 Release(R1); P1P1 Release( Release(R2R2) ) P2 Request( P2 Request(R2R2); ); P2 P2 Request(R1);Request(R1); P2 Release(R2); P2 Release(R2); P2P2 Release( Release(R1R

53、1););不会发生死锁不会发生死锁. .77如果如果: :P1 Request(P1 Request(R1R1); ); P2 P2 Request(R2);Request(R2); P1P1 Request( Request(R2R2); ); P2 P2 Request(R1); Request(R1); 则可能会发生死锁则可能会发生死锁. .如果如果: :P2 P2 Request(R2);Request(R2); P1 Request(P1 Request(R1R1); ); P2 P2 Request(R1); Request(R1); P1P1 Request( Request(R

54、2R2); ); 则可能会发生死锁则可能会发生死锁. . 总之总之, ,系统进入不安全区则可能会发生死锁系统进入不安全区则可能会发生死锁. . 78 P P1 1Req(RReq(R1 1) P) P1 1Req(RReq(R2 2) P) P1 1Rel(RRel(R1 1) P) P1 1Rel(RRel(R2 2) ) P P2 2Rel(RRel(R1 1) )P P2 2Rel(RRel(R2 2) ) P P2 2Req(RReq(R1 1) ) P P2 2Req(RReq(R2 2) )1 12 23 34 4不安全区不安全区D D79定义：定义： 指多个进程因竞争资源而造成的

55、一种僵指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能局，若无外力作用，这些进程都将永远不能再向前推进。再向前推进。 80产生死锁的必要条件产生死锁的必要条件 同时具备下列四个必要条同时具备下列四个必要条件则会产生死锁件则会产生死锁: : (1) (1)互斥条件；互斥条件； (2) (2)请求和保持条件；请求和保持条件； (3) (3)不剥夺条件；不剥夺条件； (4) (4)环路等待条件；环路等待条件；81 处理死锁的基本方法处理死锁的基本方法(1)(1)预防死锁预防死锁: :事先破坏死锁的四个必要条件事先破坏死锁的四个必要条件. .(2)(2)避免死锁避免死锁: :资

56、源分配中防止系统进入不安全区资源分配中防止系统进入不安全区. .(3)(3)检测死锁检测死锁: :在系统的运行过程中检测死锁的发在系统的运行过程中检测死锁的发生生, ,并确定进程与有关的资源并确定进程与有关的资源, ,采取措施清除死锁采取措施清除死锁. .(4)(4)解除死锁解除死锁: :将进程从死锁转态解脱出来将进程从死锁转态解脱出来. .82基本思想基本思想: : 通过分析系统产生死锁的必要条件，通过分析系统产生死锁的必要条件，然后使之不成立或破坏条件。然后使之不成立或破坏条件。3.6 3.6 预防死锁预防死锁833 3.6.1.6.1 破坏破坏“请求和保持请求和保持”条件条件: : 系统

57、要求所有进程要一次性的申请在整个运系统要求所有进程要一次性的申请在整个运行过程所需要得全部资源行过程所需要得全部资源, ,在整个运行期间在整个运行期间, ,再不再不会提出资源要求会提出资源要求, ,从而摒弃了请求条件从而摒弃了请求条件. . 优点优点: :简单简单, ,易于实现易于实现, ,安全安全. . 缺点缺点: :资源严重浪费资源严重浪费, ,进程延迟运行进程延迟运行. .死锁的预防死锁的预防843 3.6.2.6.2 破坏破坏“不可抢占不可抢占”条件条件: : 进程在需要资源时才提出请求进程在需要资源时才提出请求, ,一个已经保一个已经保持了某些资源的进程当它再提出新的资源要求持了某些

58、资源的进程当它再提出新的资源要求而不能立即得到满足时而不能立即得到满足时, ,必须释放它已经保持的必须释放它已经保持的所有资源待以后需要时再申请所有资源待以后需要时再申请. .也就是认为资源也就是认为资源被剥夺了被剥夺了. . 缺点缺点: :实施复杂实施复杂, ,代价大代价大. . 反复申请和释放资源反复申请和释放资源, ,使进程的执行使进程的执行 无限地推迟无限地推迟, ,延长了进程的周转时间延长了进程的周转时间, , 增加了系统开销增加了系统开销, ,降低了系统吞吐量降低了系统吞吐量. .853.6.3 3.6.3 破坏破坏“循环循环等待等待”条件条件: : 系统将所有资源按类型进行线性排

59、队系统将所有资源按类型进行线性排队, ,并赋予并赋予不同的序号不同的序号, ,所有进程对资源的请求必须严格按资所有进程对资源的请求必须严格按资源序号递增的次序提出源序号递增的次序提出, ,在资源分配图中不可能再在资源分配图中不可能再出现环路出现环路. . 优点优点: :资源利用率和系统吞吐量提高资源利用率和系统吞吐量提高. . 缺点缺点: :资源序号必须相对稳定资源序号必须相对稳定, ,新设备类型增新设备类型增 加难加难. . 进程使用资源的顺序与系统规定的顺序进程使用资源的顺序与系统规定的顺序 不同造成资源浪费不同造成资源浪费. . 限制用户简单限制用户简单, ,自主编程自主编程. . 86

60、 3. 3.7 7. .1 1 系统的安全状态系统的安全状态(1)(1)安全状态安全状态: : 只要系统始终处于安全状态只要系统始终处于安全状态, ,便可避免死锁便可避免死锁. . 在系统资源分配前在系统资源分配前, ,先计算系统的安全性先计算系统的安全性. .若若此次分配不会导致系统进入不安全状态此次分配不会导致系统进入不安全状态, ,便将资源便将资源分配给进程分配给进程, ,否则进程等待否则进程等待. . 3.3.7 7 避免死锁避免死锁87安全状态定义安全状态定义: : 指系统按某种顺序指系统按某种顺序 Pn，来为每来为每个进程分配其所需资源，直至最大需求，使每个进个进程分配其所需资源，