第三章处理机调度_new_new

1、1 在多道程序环境中，主存中有多个进程，在多道程序环境中，主存中有多个进程，其数目往往多于处理机数目，这就要求其数目往往多于处理机数目，这就要求系统能按某种算法，动态地把处理机分系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行，配给就绪队列中的一个进程，使之执行，分配处理机的任务是由处理机调度程序分配处理机的任务是由处理机调度程序完成的。完成的。 由于处理机是重要的资源，提高处理机由于处理机是重要的资源，提高处理机的利用率及改善系统的性能，在很大程的利用率及改善系统的性能，在很大程度上取决于处理机调度性能的好坏。度上取决于处理机调度性能的好坏。2处理机调度的层次处理机调度的

2、层次进程调度进程调度3高级调度高级调度低级调度低级调度中级调度中级调度41、高级调度、高级调度 高级调度又称为作业调度，主要功能是根据某高级调度又称为作业调度，主要功能是根据某种算法，把外存上处于后备队列中的那些作业种算法，把外存上处于后备队列中的那些作业调入内存，调度的对象是作业。调入内存，调度的对象是作业。 作业：作业是比程序更为广泛的概念，它不仅作业：作业是比程序更为广泛的概念，它不仅包含了通常的程序和数据，还配有一个作业说包含了通常的程序和数据，还配有一个作业说明书，系统根据作业说明书来对程序的运行进明书，系统根据作业说明书来对程序的运行进行控制。行控制。 在批处理系统中，是以作业为基

3、本单位从外存在批处理系统中，是以作业为基本单位从外存调入内存的。调入内存的。51、高级调度、高级调度 在每次执行作业调度时，都须做出以下在每次执行作业调度时，都须做出以下两个决定。两个决定。 1) 接纳多少个作业：即允许多少个作业接纳多少个作业：即允许多少个作业同时在内存中运行。当内存中同时运行同时在内存中运行。当内存中同时运行的作业数目太多时，可能会影响到系统的作业数目太多时，可能会影响到系统的服务质量。的服务质量。 2) 接纳哪些作业：应将哪些作业从外存接纳哪些作业：应将哪些作业从外存调入内存，这取决于所采用的调度算法。调入内存，这取决于所采用的调度算法。 62、低级调度、低级调度 低级调

4、度也称为进程调度。低级调度也称为进程调度。 低级调度用于决定就绪队列中的哪个进低级调度用于决定就绪队列中的哪个进程获得处理机。程获得处理机。73、中级调度、中级调度 中级调度又称中程调度。中级调度又称中程调度。 引入中级调度的主要目的，是为了提高内存利引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。用率和系统吞吐量。 为此，应使那些暂时不为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重为就绪驻外存状态或挂起状态。当

5、这些进程重又具备运行条件、且内存又稍有空闲时，由中又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。就绪状态，挂在就绪队列上等待进程调度。 84、调度队列模型、调度队列模型 仅有进程调度的调度队列模型仅有进程调度的调度队列模型 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型9（1）仅有进程调度的调度队列模型）仅有进程调度的调度队列

6、模型10（2）具有高级和低级调度的调度队列模型）具有高级和低级调度的调度队列模型就就 绪绪 队队 列列 进程调度进程调度CPUCPU进程完成进程完成 等待事件等待事件1 1 作业作业调度调度事件事件1 1出现出现时间片完时间片完 等待事件等待事件2 2事件事件2 2出现出现 等待事件等待事件n n事件事件n n出现出现后后 备备 队队 列列 11（3）同时具有三级调度的调度队列模型）同时具有三级调度的调度队列模型12v进程调度需要解决三个主要问题：进程调度需要解决三个主要问题：v（1）什么时候分配处理机，即需要确定）什么时候分配处理机，即需要确定处理机调度时机；处理机调度时机； v（2）按什么

7、原则分配处理机，即需要确）按什么原则分配处理机，即需要确定处理机调度算法；定处理机调度算法；v（3）如何分配处理机，即需要给出处理）如何分配处理机，即需要给出处理机调度过程。机调度过程。13进程调度进程调度v进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队的竞争，即按一定的调度算法从就绪队列中选中一个进程，把列中选中一个进程，把CPU的使用权交的使用权交给被选中的进程。给被选中的进程。14 在单处理机多道程序设计系统中，进程在单处理机多道程序设计系统中，进程被作为占用处理机运行的执行单位。由被作为占用处理机运行的执行单位。由于处理机是最重要的

8、计算机资源，所以于处理机是最重要的计算机资源，所以合理、有效地选择进程占有处理机是进合理、有效地选择进程占有处理机是进程调度的重要任务。提高处理机的利用程调度的重要任务。提高处理机的利用率及改善系统响应时间、吞吐率，在很率及改善系统响应时间、吞吐率，在很大程度上取决于进程调度性能的好坏。大程度上取决于进程调度性能的好坏。15调度目标：调度目标： 公平保证每个进程得到合理的公平保证每个进程得到合理的CPU 时间时间 高效使高效使CPU 保持忙碌状态即总是有进程在保持忙碌状态即总是有进程在CPU 上运行上运行 响应时间使交互用户的响应时间尽可能短响应时间使交互用户的响应时间尽可能短 周转时间使批处

9、理用户等待输出的时间尽可能周转时间使批处理用户等待输出的时间尽可能短短 吞吐量使单位时间内处理的进程尽可能多吞吐量使单位时间内处理的进程尽可能多 由于这些目标的相互冲突，任一调度算法要想由于这些目标的相互冲突，任一调度算法要想同时满足上述目标是不可能的。同时满足上述目标是不可能的。16不同系统调度目标也不同：不同系统调度目标也不同： 在多道批处理系统中，为了提高处理机的效率在多道批处理系统中，为了提高处理机的效率和吞吐量，当调度一批作业运行时，尽可能使和吞吐量，当调度一批作业运行时，尽可能使作业搭配合理，充分利用资源。作业搭配合理，充分利用资源。 在分时系统中，由于用户使用交互式会话的工在分时

10、系统中，由于用户使用交互式会话的工作方式，系统必须要有较快的响应时间，使得作方式，系统必须要有较快的响应时间，使得每个用户都感到如同只有他自己一人在使用计每个用户都感到如同只有他自己一人在使用计算机，因此考虑的是公平性。算机，因此考虑的是公平性。 在实时系统中，首先要保证截止时间，即某任在实时系统中，首先要保证截止时间，即某任务必须开始执行的最迟时间，或必须完成的最务必须开始执行的最迟时间，或必须完成的最迟时间。迟时间。17调度性能评价调度性能评价 定性衡量：调度的可靠性、简洁性定性衡量：调度的可靠性、简洁性 可靠性：一次进程调度是否可能引起数据结构的破可靠性：一次进程调度是否可能引起数据结构

11、的破坏，这要求对调度时机的选择和保存坏，这要求对调度时机的选择和保存CPU现场十分现场十分谨慎。谨慎。 简洁性：调度会涉及到多个进程和上下文切换，如简洁性：调度会涉及到多个进程和上下文切换，如果调度程序过于繁琐和复杂，会耗去较大的系统开果调度程序过于繁琐和复杂，会耗去较大的系统开销。销。 定量评价：定量评价：CPU的利用率评价、进程在就绪队的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。列中的等待时间与执行时间之比等。18 衡量调度策略的最常用的几个指标是：衡量调度策略的最常用的几个指标是： 周转时间周转时间：指将一个作业提交给计算机系统开：指将一个作业提交给计算机系统开始，到作业完

12、成为止的这段时间间隔。始，到作业完成为止的这段时间间隔。 吞吐量吞吐量：指在单位时间内，一个计算机系统所：指在单位时间内，一个计算机系统所完成的作业数。完成的作业数。 响应时间响应时间：指从用户向计算机提交一个请求开：指从用户向计算机提交一个请求开始，直至系统首次产生响应为止的时间。始，直至系统首次产生响应为止的时间。191. 周转时间：周转时间：作业作业i的周转时间的周转时间Ti为为Ti=Tei-Tsi其中其中Tei为作业为作业i的完成时间，的完成时间，Tsi为作业的提交时间。为作业的提交时间。对于被测定作业流所含有的对于被测定作业流所含有的n（n=1）个作业来说，）个作业来说，其平均周转时

13、间为：其平均周转时间为：一个作业的周转时间说明了该作业在系统内停留的一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等待时间；执行时间，即：时间，包含两部分：等待时间；执行时间，即：Ti=TwiTri这里，这里，Twi主要指作业主要指作业i等待处理机的时间。等待处理机的时间。nii = 11T =Tn202. 带权周转时间带权周转时间作业的周转时间包含了两个部分，即等待时间和执作业的周转时间包含了两个部分，即等待时间和执行时间。为了更进一步反映调度性能，使用带权周行时间。为了更进一步反映调度性能，使用带权周转时间的概念。带权周转时间是作业周转时间与作转时间的概念。带权周转时间是作

14、业周转时间与作业执行时间的比：业执行时间的比：Wi=Ti/Tri对于被测定作业流所含有的几个作业来说，其平均对于被测定作业流所含有的几个作业来说，其平均带权周转时间为：带权周转时间为：对于分时系统，除了要保证系统吞吐量大、资源利对于分时系统，除了要保证系统吞吐量大、资源利用率高之外，还应保证有用户能够容忍的响应时间。用率高之外，还应保证有用户能够容忍的响应时间。因此，在分时系统中，仅仅用周转时间或带权周转因此，在分时系统中，仅仅用周转时间或带权周转时间来衡量调度性能是不够的。时间来衡量调度性能是不够的。nii=11W =Wn21对于分时系统和实时系统来说，对于分时系统和实时系统来说， 仅用周转

15、时间或带权周转时间衡量调度仅用周转时间或带权周转时间衡量调度性能是不够的，需要加平均响应时间作性能是不够的，需要加平均响应时间作为衡量调度策略优劣的标准。为衡量调度策略优劣的标准。 响应时间：指从用户向计算机提交一个响应时间：指从用户向计算机提交一个请求开始，直至系统首次产生响应为止请求开始，直至系统首次产生响应为止的时间。的时间。22评价指标：评价指标： 批处理系统来说，主要的性能指标是批处理系统来说，主要的性能指标是 周转时间，平均周转时间（等待时间、平均周转时间，平均周转时间（等待时间、平均等待时间）等待时间） 带权周转时间，平均带权周转时间带权周转时间，平均带权周转时间 分时系统来说，

16、主要的性能指标是分时系统来说，主要的性能指标是 响应时间，平均响应时间响应时间，平均响应时间 实时系统来说，主要的性能指标是实时系统来说，主要的性能指标是 截止时间截止时间23进程调度进程调度 何时调度？何时调度？ 选择谁运行选择谁运行调度算法？调度算法？ 调度时需要做什么？调度时需要做什么？24一、何时调度一、何时调度进程调度的原因进程调度的原因 (1) 正在执行的进程执行完毕。正在执行的进程执行完毕。 (2) 执行中进程自己调用阻塞原语将自执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。己阻塞起来进入睡眠等待状态。 (3) 执行中进程调用了执行中进程调用了P原语操作，从而原语操作

17、，从而因资源不足而被阻塞；或调用了因资源不足而被阻塞；或调用了V原语操原语操作激活了等待资源的进程队列进入就绪作激活了等待资源的进程队列进入就绪队列，并请求重新调度。队列，并请求重新调度。 (4) 执行中进程提出执行中进程提出IO请求后被阻塞。请求后被阻塞。25以上都是在以上都是在CPU执行不可剥夺方式下所引执行不可剥夺方式下所引起进程调度的原因。在起进程调度的原因。在CPU执行方式是执行方式是可剥夺时，还有：可剥夺时，还有：(5) 在分时系统中时间片已经用完。在分时系统中时间片已经用完。(6) 就绪队列中的某进程的优先级变得高就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引

18、于当前执行进程的优先级，从而也将引发进程调度。发进程调度。26二、调度时需要做什么二、调度时需要做什么进程调度的功能进程调度的功能 1保存保存“下降下降”进程现场进程现场 2选择将要运行的进程选择将要运行的进程“上升上升”进进程程 3恢复恢复“上升上升”进程的现场进程的现场27三、调度算法三、调度算法 v引入多道程序系统的直接目的就是想让处理机引入多道程序系统的直接目的就是想让处理机“忙忙”，一，一直以来处理机都是计算机系统中的瓶颈资源之一，特别是直以来处理机都是计算机系统中的瓶颈资源之一，特别是在单处理机系统中，处于就绪状态的多个进程竞争使用一在单处理机系统中，处于就绪状态的多个进程竞争使用

19、一台处理机，所以当处理机空闲时，系统需要从多个就绪进台处理机，所以当处理机空闲时，系统需要从多个就绪进程中挑选一个使其投入运行。选择哪一个呢？这需要按某程中挑选一个使其投入运行。选择哪一个呢？这需要按某一种算法。一种算法。调度算法的实质就是一种资源分配调度算法的实质就是一种资源分配。 v从资源的角度来看，该算法确定了处理机的分配策略，故从资源的角度来看，该算法确定了处理机的分配策略，故称其为处理机调度算法；称其为处理机调度算法；v而从资源使用者的角度看，该算法确定了进程运行的次序，而从资源使用者的角度看，该算法确定了进程运行的次序，故也称进程调度算法。故也称进程调度算法。 28不可抢占方式：在

20、这种方式下，一旦把处理机分不可抢占方式：在这种方式下，一旦把处理机分配给某进程后，便让他一直运行下去，直到进程配给某进程后，便让他一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给完成或发生某事件而阻塞时，才把处理机分配给另一进程。但存在明显的缺点：如当一个紧急任另一进程。但存在明显的缺点：如当一个紧急任务到达时，不能立即投入运行，实时性差。务到达时，不能立即投入运行，实时性差。进程调度有两种基本方式：进程调度有两种基本方式： 不可抢占方式不可抢占方式与可抢占方式可抢占方式 29 可抢占方式：在这种方式下，某个进程正在运可抢占方式：在这种方式下，某个进程正在运行时可以被系统以某种

21、原则抢占已分配给它的行时可以被系统以某种原则抢占已分配给它的处理机，将处理机分配给其他进程。抢占原则处理机，将处理机分配给其他进程。抢占原则可以是优先权原则，即高优先级进程可以剥夺可以是优先权原则，即高优先级进程可以剥夺低优先级的进程运行，也可以是时间片原则，低优先级的进程运行，也可以是时间片原则，在运行进程的时间片用完后被剥夺处理机，重在运行进程的时间片用完后被剥夺处理机，重新参与调度。新参与调度。30 基本的处理机调度算法有先来先服务基本的处理机调度算法有先来先服务法、优先级法和时间片轮转法等，现在也有法、优先级法和时间片轮转法等，现在也有些操作系统使用综合性的调度算法，比如多些操作系统使

22、用综合性的调度算法，比如多级反馈队列调度算法等。级反馈队列调度算法等。 311先来先服务调度算法（先来先服务调度算法（First Come First Served，FCFS） 该算法按照进程进入就绪队列的先后顺序选择最先进该算法按照进程进入就绪队列的先后顺序选择最先进入该队列的进程，把处理机分配给它，使之投入运行。入该队列的进程，把处理机分配给它，使之投入运行。一旦一个进程占有了处理机就一直运行下去，直到该一旦一个进程占有了处理机就一直运行下去，直到该进程完成或因等待某事件而不能继续运行才释放处理进程完成或因等待某事件而不能继续运行才释放处理机。机。DCBACPU完成32在单道环境下，某批处

23、理有四道作业，已知他们的进入在单道环境下，某批处理有四道作业，已知他们的进入系统的时刻、估计运算时间如下：系统的时刻、估计运算时间如下：进程进程到达时刻到达时刻执行时间执行时间开始时刻开始时刻完成时刻完成时刻 周转时间周转时间 带权周转带权周转ABCD0123110011000110110211011022021100100199111001.99短作业短作业C的带权周转时间高达的带权周转时间高达100。长作业长作业D的带权周转时间仅为的带权周转时间仅为1.99 33 这是一种不可抢占方式的调度算法，优点这是一种不可抢占方式的调度算法，优点是实现简单，缺点是后来的进程等待是实现简单，缺点是后来

24、的进程等待CPUCPU的时间的时间较长。即有利于长进程，不利于短进程。较长。即有利于长进程，不利于短进程。 在当今系统中，先进先出很少作为调度模在当今系统中，先进先出很少作为调度模式，而是常常嵌套在其它的调度模式中。式，而是常常嵌套在其它的调度模式中。 例如，许多调度模式根据优先级将处理机例如，许多调度模式根据优先级将处理机分配给进程，但具有相同优先级的进程却按先分配给进程，但具有相同优先级的进程却按先进先出进行分配。进先出进行分配。342.2.最短进程优先法（最短进程优先法（Shortest Process/Job Shortest Process/Job FirstFirst，SPF/SJ

25、FSPF/SJF）SPF/SJF:SPF/SJF:从就绪队列中选择估计运行时间最短的进程，从就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执行。先将处理机分配给它，使它立即执行。非抢占式。非抢占式。优点：减少了在就绪队列中等待的进程数，同时也降低优点：减少了在就绪队列中等待的进程数，同时也降低了进程的平均等待时间，提高了系统的吞吐量。了进程的平均等待时间，提高了系统的吞吐量。缺点：没有考虑到某些进程的紧迫程度。缺点：没有考虑到某些进程的紧迫程度。 用户作出的估计时间并不准确，带有很大的主观性。用户作出的估计时间并不准确，带有很大的主观性。 35例：例： 假设有假设有5道作业

26、，它们的提交时间及运行时间由下道作业，它们的提交时间及运行时间由下表给出：表给出：作业作业 提交时间（时）提交时间（时） 运行时间（小时）运行时间（小时）1 9 2 2 925 13 1005 0754 1225 055 125 025若采用若采用FCFS和和SJF两种调度算法，指出作业被调度两种调度算法，指出作业被调度顺序及平均周转时间。顺序及平均周转时间。 363.3.最高响应比优先算法（最高响应比优先算法（ Highest Highest Response Ratio NextResponse Ratio Next， HRNHRN） 是对是对FCFSFCFS方式和方式和SJFSJF方式的

27、一种综合平衡方式的一种综合平衡响应比。响应比。 FCFSFCFS只考虑了每个作业的等待时间而未只考虑了每个作业的等待时间而未考虑执行时间的长短，而考虑执行时间的长短，而SJFSJF只考虑执行只考虑执行时间而未考虑等待时间的长短。时间而未考虑等待时间的长短。 HRNHRN算法同时考虑每个作业的等待时间长算法同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。出响应比最高的作业投入执行。373.3.最高响应比优先算法最高响应比优先算法 响应比：响应比： R R( (作业等待时间需运行时间作业等待时间需运行时间)/ )/ 需运行

28、时间需运行时间 1 1已等待时间已等待时间 / / 需运行时间需运行时间 1 1W/TW/T由于由于R R与要求运行时间成反比，故对短作业是与要求运行时间成反比，故对短作业是有利的，另一方面，因有利的，另一方面，因R R与等待时间成正比，与等待时间成正比，故长作业随着其等待时间的增长，也可获的较故长作业随着其等待时间的增长，也可获的较高的响应比。这就克服了短作业优先数法的缺高的响应比。这就克服了短作业优先数法的缺点，既照顾了先来者，又优待了短作业，是上点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。述两种算法的一种较好的折中。384优先级调度算法（优先级调度算法（Prior

29、ity DrivenPriority Driven，PDPD） 总是选择具有总是选择具有最高优先级最高优先级的进程首先使用处理机的进程首先使用处理机。在这种算在这种算法中，首先考虑的问题是如何确定进程的优先数。法中，首先考虑的问题是如何确定进程的优先数。 分为分为： 静态优先级静态优先级：在创建进程的时候便确定的，且在进在创建进程的时候便确定的，且在进程的运行期间保持不变。（程的运行期间保持不变。（简单易行，系统开销小，简单易行，系统开销小，但不够精确，很可能出现优先权低的进程长期不被但不够精确，很可能出现优先权低的进程长期不被调度的情况。所以只在要求不太高的系统中，才使调度的情况。所以只在要

30、求不太高的系统中，才使用静态优先级用静态优先级） 动态优先级动态优先级：在创建进程时所赋予的优先级，可以在创建进程时所赋予的优先级，可以随进程的推进而改变，以便获得更好的调度性能随进程的推进而改变，以便获得更好的调度性能 39这是一种这是一种可抢占方式可抢占方式的调度算法，可防止一个长进程长的调度算法，可防止一个长进程长期的垄断处理机。期的垄断处理机。 若所有的进程具有相同的优先级初值，若所有的进程具有相同的优先级初值，则按照则按照FCFS算法，最先进入就绪队列的算法，最先进入就绪队列的进程最先获得处理机。进程最先获得处理机。40进程的静态优先级确定原则可以是：进程的静态优先级确定原则可以是：

31、(1) 系统根据进程要求资源情况确定优先系统根据进程要求资源情况确定优先级。例如根据估计所需处理机时间、内级。例如根据估计所需处理机时间、内存量大小、存量大小、IO设备类型及数量等，确设备类型及数量等，确定进程的优先级。定进程的优先级。(2) 按进程的类型给予不同的优先级。例按进程的类型给予不同的优先级。例如，在有些系统中，进程被划分为系统如，在有些系统中，进程被划分为系统进程和用户进程。系统进程享有比用户进程和用户进程。系统进程享有比用户进程高的优先级。进程高的优先级。41进程的动态优先级一般根据以下原则确定：进程的动态优先级一般根据以下原则确定：(1) 根据进程占有根据进程占有CPU时间的

32、长短来决定。一个时间的长短来决定。一个进程占有处理机的时间愈长，则在被阻塞之后进程占有处理机的时间愈长，则在被阻塞之后再次获得调度的优先级就越低，反之，其获得再次获得调度的优先级就越低，反之，其获得调度的可能性就会越大。调度的可能性就会越大。(2) 根据就绪进程等待根据就绪进程等待CPU的时间长短来决定。的时间长短来决定。一个就绪进程在就绪队列中等待的时间越长，一个就绪进程在就绪队列中等待的时间越长，则它获得调度选中的优先级就越高。则它获得调度选中的优先级就越高。由于动态优先级随时间的推移而变化，系统要经由于动态优先级随时间的推移而变化，系统要经常计算各进程的优先级，因此，系统要为此付常计算各

33、进程的优先级，因此，系统要为此付出一定的开销。出一定的开销。42例：例： 有有5个进程个进程P1、P2、P3、P4、P5，它们同时依次，它们同时依次进入就绪队列，它们的优先数和需要的处理机时间如下进入就绪队列，它们的优先数和需要的处理机时间如下（优先数越大代表优先级越高）（优先数越大代表优先级越高） ： 进程进程 处理机时间处理机时间 优先数优先数 P1 10 3P1 10 3 P2 1 1P2 1 1 P3 2 3P3 2 3 P4 1 4P4 1 4 P5 5 2P5 5 2 43忽略进程调度所花的时间，要求：忽略进程调度所花的时间，要求： （1 1）分别写出采用先来先服务调度算法和静态优

34、）分别写出采用先来先服务调度算法和静态优先级调度算法中进程的执行次序；先级调度算法中进程的执行次序； （2 2）分别计算各进程在就绪队列中的等待时间和）分别计算各进程在就绪队列中的等待时间和平均等待时间。平均等待时间。 解：（解：（1 1）采用先来先服务调度算法时各进程的执）采用先来先服务调度算法时各进程的执行次序为：行次序为：P1P1P2P2P3P3P4P4P5P5。 采用静态优先级调度算法时各进程的执行次序为：采用静态优先级调度算法时各进程的执行次序为： P4P1P3P5P2。 44（2 2）FCFSFCFS中，平均等待时间（中，平均等待时间（0+10+11+13+140+10+11+13

35、+14）/5/59.69.6；静态优先级法中，平均等待时间（静态优先级法中，平均等待时间（1+18+11+0+131+18+11+0+13）/5/58.68.6进程进程 处理机时间处理机时间 FCFSFCFS等待时间等待时间 静态优先级法等待时间静态优先级法等待时间 P1 10 0 1P1 10 0 1 P2 1 10 18P2 1 10 18 P3 2 11 11P3 2 11 11 P4 1 13 0P4 1 13 0 P5 5 14 13 P5 5 14 13 455时间片轮转调度算法时间片轮转调度算法Round-Robin (RR) 基本思想基本思想：系统把所有的就绪进程按系统把所有的

36、就绪进程按FCFS原则排成一个原则排成一个队列，且规定一个时间片作为进程每次使用处理机的最队列，且规定一个时间片作为进程每次使用处理机的最长时间单位，按时间片把处理机轮流分配给当前位于就长时间单位，按时间片把处理机轮流分配给当前位于就绪队列队首的进程使用，绪队列队首的进程使用，当该进程的时间片用完以后，当该进程的时间片用完以后，系统产生时钟中断，剥夺该进程的执行，将它送到就绪系统产生时钟中断，剥夺该进程的执行，将它送到就绪队列队尾，等待下一轮次的调度。队列队尾，等待下一轮次的调度。同时处理机调度程序同时处理机调度程序又去调度当前就绪队列的又去调度当前就绪队列的队首进程队首进程，也让它运行给定的

37、也让它运行给定的时间片，如此循环往复。时间片，如此循环往复。46FCB A .CPU完成 A B C时间片轮转算法图示 w该算法适合分时系统使用。该算法适合分时系统使用。47时间片选择时间片选择 在轮转法中，时间片长度的选取非常重要。首在轮转法中，时间片长度的选取非常重要。首先，时间片长度的选择会直接影响系统开销和先，时间片长度的选择会直接影响系统开销和响应时间。如果时间片长度过短，则调度程序响应时间。如果时间片长度过短，则调度程序剥夺处理机的次数增多。这将使进程上下文切剥夺处理机的次数增多。这将使进程上下文切换次数也大大增加，从而加重系统开销。反过换次数也大大增加，从而加重系统开销。反过来，

38、如果时间片长度选择过长，比方说一个时来，如果时间片长度选择过长，比方说一个时间片能保证就绪队列中所需执行时间最长的进间片能保证就绪队列中所需执行时间最长的进程能执行完毕，则轮转法变成了先来先服务法。程能执行完毕，则轮转法变成了先来先服务法。48 最佳时间片的确定最佳时间片的确定 这个最佳的时间片值是多少呢？显然，它将随这个最佳的时间片值是多少呢？显然，它将随系统而异。随负载而异，同时也随进程而异。系统而异。随负载而异，同时也随进程而异。 时间片的选取是实现各种调度算法的关键之处，时间片的选取是实现各种调度算法的关键之处，而时间片的选定通常应考虑终端数目，处理机能力、而时间片的选定通常应考虑终端

39、数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因各终端任务的急迫程度、外存传输速度等方面的因素。素。49例：例： 有有5个进程个进程P1、P2、P3、P4、P5，它们同时依次，它们同时依次进入就绪队列，请写出使用轮转法调度时的调度次序，进入就绪队列，请写出使用轮转法调度时的调度次序，各进程的周转时间和等待时间，其中时间片为各进程的周转时间和等待时间，其中时间片为2 2： 进程进程 处理机时间处理机时间 P1 10P1 10 P2 1P2 1 P3 2 P3 2 P4 1P4 1 P5 5P5 550RR算法算法 每个进程被分配一个时间段，称作它的每个进程被分配一个时间段，称作它的

40、时间片，即该进程允许运行的时间。如时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则果进程在时间片结束前阻塞或结束，则CPU当即进行切换。当即进行切换。 516多级反馈队列调度算法多级反馈队列调度算法 以上介绍的算法，都存在一定的局限性。以上介绍的算法，都存在一定的局限性。 现在主流的操作系统，如现在主流的操作系统，如UNIX、Windows NT、Linux等，都使用一种综合性的调度算等，都使用一种综合性的调度算法法多级反馈队列调度算法。该算法综

41、合了多级反馈队列调度算法。该算法综合了上述算法以及多队列调度算法的思想和优点，上述算法以及多队列调度算法的思想和优点，总体调度性能优越，但其实现也比较复杂。总体调度性能优越，但其实现也比较复杂。 52算法的基本思想（实施过程）是算法的基本思想（实施过程）是： 首先首先：系统按进程优先级设置了多级（比如系统按进程优先级设置了多级（比如n级，级，n2）就）就绪进程队列，从第一级队列到最后一级队列，优先级越来越绪进程队列，从第一级队列到最后一级队列，优先级越来越低。低。其次其次：每一级就绪队列对应一个不同的时间片。优先级越高：每一级就绪队列对应一个不同的时间片。优先级越高的队列，进程的时间片越小。的

42、队列，进程的时间片越小。再次再次：当一个新进程进入内存后，首先被放到第一级队列的当一个新进程进入内存后，首先被放到第一级队列的队尾。按照队尾。按照FCFS原则排队等待调度。当轮到该进程执行时，原则排队等待调度。当轮到该进程执行时，如能在时间片内完成，便可准备撤离系统；如果在时间片内如能在时间片内完成，便可准备撤离系统；如果在时间片内未完成，调度程序便将该进程转入第二队列的末尾，再依次未完成，调度程序便将该进程转入第二队列的末尾，再依次按照按照FCFS原则等待调度。原则等待调度。53最后最后：仅当第一级队列为空时，才调度第二级队列中仅当第一级队列为空时，才调度第二级队列中的进程；如此下去，仅当前

43、面的的进程；如此下去，仅当前面的n-1级队列全部为空级队列全部为空时，才去调度最后第时，才去调度最后第n级队列中的进程。级队列中的进程。 如果处理机正在第如果处理机正在第I队列中为某进程服务时，又有新的队列中为某进程服务时，又有新的进程进入优先级高的队列（第进程进入优先级高的队列（第1I-1中任何一队列），中任何一队列），则系统抢占正在运行的进程的处理机，由调度程序把则系统抢占正在运行的进程的处理机，由调度程序把正在运行的进程放回到刚才所在第正在运行的进程放回到刚才所在第I队列的队尾，重新队列的队尾，重新进行处理机调度。进行处理机调度。 54实时系统调度方法实时系统调度方法一、实时系统的特点：

44、一、实时系统的特点：实时系统与其他系统的最大区别在于，其处理和控实时系统与其他系统的最大区别在于，其处理和控制的正确性不仅仅取决于计算的逻辑结果，而且取制的正确性不仅仅取决于计算的逻辑结果，而且取决于计算和处理结果产生的时间。决于计算和处理结果产生的时间。实时系统中处理的外部事件可分为硬实时任务和软实时系统中处理的外部事件可分为硬实时任务和软实时任务。硬实时任务要求系统必须完全满足任务实时任务。硬实时任务要求系统必须完全满足任务的时限要求。软实时任务则允许系统对任务的时限的时限要求。软实时任务则允许系统对任务的时限要求有一定的延迟，其时限要求只是一个相对条件。要求有一定的延迟，其时限要求只是一

45、个相对条件。55一般来说，实时操作系统具有以下特点：一般来说，实时操作系统具有以下特点：(1) 有限等待时间有限等待时间(2) 有限响应时间有限响应时间(3) 可靠性高可靠性高(4) 系统出错处理能力强系统出错处理能力强56上述特性要求实时操作系统具有下述能力：上述特性要求实时操作系统具有下述能力：(1) 很快的进程切换速度很快的进程切换速度(2) 快速的外部中断响应能力快速的外部中断响应能力(3) 基于优先级的抢先式调度策略基于优先级的抢先式调度策略57二、实时调度算法的分类二、实时调度算法的分类(1) 静态表格驱动静态表格驱动Time Driven(TD算法算法)(2) 频率单调调度算法频

46、率单调调度算法Rate Monotonic（RM算法）算法）(3) 最早时间限优先调度算法最早时间限优先调度算法Early Deadline First （EDF算法）算法）58三、最早时间限优先调度算法与频率单调调度算法三、最早时间限优先调度算法与频率单调调度算法最早时间限优先调度算法是一种以满足用户要求的最早时间限优先调度算法是一种以满足用户要求的时限为调度原则的算法。时限为调度原则的算法。最早时间限优先调度算法最早时间限优先调度算法的基本思想是：按用户的的基本思想是：按用户的时限要求顺序设置优先级，优先级高者占据处理机，时限要求顺序设置优先级，优先级高者占据处理机，也就是说，时限要求最近

47、的任务优先占有处理机。也就是说，时限要求最近的任务优先占有处理机。59例子：设实时系统从两个不同的数据源例子：设实时系统从两个不同的数据源DA和和DB周期周期性地收集数据并进行处理，其中性地收集数据并进行处理，其中DA的时限要求以的时限要求以30 ms为周期，为周期，DB的时限要求以的时限要求以75 ms为周期。设为周期。设DA所所需处理时限为需处理时限为15 ms，DB所需处理时限为所需处理时限为38 ms。60图4.11 周期性任务的预计发生、执行与结束时限61在开始时，进程在开始时，进程DA（1）和）和DB（1）的结束时限比）的结束时限比较结果，较结果，DA（1）的结束时限最近，从而调度

48、进程）的结束时限最近，从而调度进程DA（1）执行。）执行。DA（1）的实际结束时间为）的实际结束时间为15，小，小于于30的时限要求。紧接着，进程的时限要求。紧接着，进程DB（1）被调度执）被调度执行。在执行到时间为行。在执行到时间为30 ms时，进程时，进程DA（2）进入）进入就绪状态。由于就绪状态。由于DA（2）的结束时限为）的结束时限为60，近于，近于DB（1）的结束时限）的结束时限75，从而，从而DB（1）被）被DA（2）抢）抢先。先。DA（2）的实际结束时间为）的实际结束时间为45，小于要求时限，小于要求时限60在在DA（2）结束之后，）结束之后，DB（1）再次占有处理机）再次占有处理机继续执行，当继续执行，当DB（1）执行到时间为）执行到时间为60 ms时，进时，进程程DA（3）进入就绪状态。但是，由于）进入就绪状态。但是，由于DA（3）的）的结束时限为结束时限为90，远于，远于DB（1）的结束时限）的结束时限75，从而，从而DB（1）继续执行。）继续执行。62频率单调调度算法是一种被广泛用于多周期性实时频率单调调度算法是一种被广泛用于多周期性实时处理的调度算法。处理的调度算法。频率单调调度算法的基本原理是频率越低（周期越频率单调调度算法的基本原理是频率越