操作系统chapter(3)课件

《操作系统chapter(3)课件》由会员分享，可在线阅读，更多相关《操作系统chapter(3)课件（156页珍藏版）》请在装配图网上搜索。

1、操作系统chapter(3)第三章第三章 处理机调度与处理机调度与死锁死锁操作系统chapter(3)第三章 处理机调度与死锁3.1 3.1 处理机调度的层次处理机调度的层次3.23.2调度队列模型和调度准则调度队列模型和调度准则3.33.3调度算法调度算法3.43.4实时调度实时调度3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.6 3.6 预防死锁的方法预防死锁的方法3.7 3.7 死锁的检测和解除死锁的检测和解除操作系统chapter(3) 3.1 处理机调度的层次 在多道程环境下，进程数目往往多于在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要

2、处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。是操作系统设计的中心问题之一。操作系统chapter(3) 进程调度要解决的问题WHATWHAT：按什么原则分配：按什么原则分配CPUCPU 进程调度算法进程调度算法WHENWHEN：何时分配：何时分配CPUCPU 进程调度的时机进程调度的时机HOWHOW： 如何分配如何分配CPUCPU CPU CPU

3、调度过程（进程的上下文切换）调度过程（进程的上下文切换）操作系统chapter(3)3.1 处理机调度的层次l处理机是计算机系统中的重要资源处理机是计算机系统中的重要资源l处理机调度算法对整个计算机系统的综处理机调度算法对整个计算机系统的综合性能指标有重要影响合性能指标有重要影响l可把处理机调度分成三个层次：可把处理机调度分成三个层次： 高级调度高级调度 中级调度中级调度 低级调度低级调度操作系统chapter(3)操作系统chapter(3)3.1.1高级调度高级调度高级调度又称为作业调度或长程调度。高级调度又称为作业调度或长程调度。长程长程调度决定哪些作业可参与竞争调度决定哪些作业可参与竞

4、争CPUCPU和和其他资源，即决定给哪个作业分配一台其他资源，即决定给哪个作业分配一台虚拟处理机，它的调度对象是作业，它虚拟处理机，它的调度对象是作业，它是处理机的宏观调度。是处理机的宏观调度。操作系统chapter(3)1作业和作业步(1)作业作业(Job)。它不仅包含了通常的。它不仅包含了通常的程序程序和数据和数据，而且还应配有一份，而且还应配有一份作业说明作业说明书书，系统根据该说明书来对程序的运，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。作业为基本单位从外存调入内存的。操作系统chapter(3)l(2)

5、 作业步作业步(Job Step)。通常，在作业运行。通常，在作业运行期间，每个作业都必须经过期间，每个作业都必须经过若干若干个个相对独相对独立立，又，又相互关联相互关联的顺序的顺序加工步骤加工步骤才能得到才能得到结果，我们把其中的结果，我们把其中的每一个加工步骤每一个加工步骤称为称为一个一个作业步作业步，各作业步之间存在着相互联，各作业步之间存在着相互联系，往往是把上一个作业步的输出作为下系，往往是把上一个作业步的输出作为下一个作业步的输入。一个作业步的输入。1作业和作业步操作系统chapter(3)1作业和作业步(3) 作业流。若干个作业进入系统后，被依次作业流。若干个作业进入系统后，被依

6、次存放在外存上，这便形成了存放在外存上，这便形成了输入的作业流输入的作业流；在操作系统的控制下，逐个作业进行处理，在操作系统的控制下，逐个作业进行处理，于是便形成了于是便形成了处理作业流。处理作业流。操作系统chapter(3)2作业控制块JCB(Job Control Block)l每个作业进入系统时由系统为其建立一个每个作业进入系统时由系统为其建立一个作业控制块作业控制块JCBJCB（Job Control Block)Job Control Block)，其其中保存了系统对作业进行管理和调度所需中保存了系统对作业进行管理和调度所需的全部信息的全部信息. .l通常包含的内容有：作业标识、用

7、户名称、通常包含的内容有：作业标识、用户名称、用户帐户、作业类型、作业状态、调度信用户帐户、作业类型、作业状态、调度信息、资源需求、进入系统时间、开始处理息、资源需求、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资时间、作业完成时间、作业退出时间、资源使用情况等。源使用情况等。 操作系统chapter(3)3.作业调度作业调度的主要功能是作业调度的主要功能是根据作业控制块中的信息根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按审查系统能否满足用户作业的资源需求，以及按照一定的算法，照一定的算法，从外存的后备队列中选取某些作从外存的后备队列中选取某些作业调入内存业调

8、入内存，并为它们，并为它们创建进程创建进程、分配必要的资、分配必要的资源。然后再将新创建的进程插入就绪队列，准备源。然后再将新创建的进程插入就绪队列，准备执行。因此，有时也把作业调度称为接纳调度执行。因此，有时也把作业调度称为接纳调度(Admission Scheduling)。 操作系统chapter(3)3作业调度l作业调度的主要任务是完成作业从后备状态到执作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。行状态和从执行状态到完成状态的转变。l作业调度功能：作业调度功能：l1.1.记录已进入系统的各作业的情况记录已进入系统的各作业的情况（JCB，Job Cont

9、rol Block）；）；l2.2.按一定的调度算法，从后备作业中选择一个或按一定的调度算法，从后备作业中选择一个或几个作业进入系统内存；几个作业进入系统内存；l3.3.为被选中的作业创建进程，并且为其申请系统为被选中的作业创建进程，并且为其申请系统资源；资源；l4.4.作业结束后作善后处理工作。作业结束后作善后处理工作。操作系统chapter(3)3作业调度l每次执行作业调度时，都须做出以下两个决定每次执行作业调度时，都须做出以下两个决定1) 决定接纳多少个作业决定接纳多少个作业 作业调度每次要接纳多少个作业进入内存，取决作业调度每次要接纳多少个作业进入内存，取决于多道程序度于多道程序度(D

10、egree of Multiprogramming)，2) 决定接纳哪些作业决定接纳哪些作业 应将哪些作业从外存调入内存，这将取决于所采应将哪些作业从外存调入内存，这将取决于所采用的调度算法。用的调度算法。操作系统chapter(3)作业与进程的关系 l每一个作业将动态地转换成了一组运行实每一个作业将动态地转换成了一组运行实体体进程组，并由此来完成该作业所需进程组，并由此来完成该作业所需要完成的一系列加工步骤，当作业所对应要完成的一系列加工步骤，当作业所对应的进程完成时，作业便进入了完成状态，的进程完成时，作业便进入了完成状态，整个作业也就完成了。整个作业也就完成了。操作系统chapter(3

11、)3.1.2 低级调度通常也把低级调度称为进程调度或短程调度，通常也把低级调度称为进程调度或短程调度，它所调度的对象是进程它所调度的对象是进程(或内核级线程或内核级线程)。进程调度是最基本的一种调度，在多道批进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的处理、分时和实时三种类型的OS中，都必中，都必须配置这级调度。须配置这级调度。操作系统chapter(3)1低级调度的功能l低级调度的低级调度的任务是控制协调进程对任务是控制协调进程对CPUCPU的竞争的竞争, ,按按一定的调度算法一定的调度算法决定就绪队列中的哪个进程应获决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执

12、行把处理机分配得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。给该进程的具体操作。l(1) 保存处理机的现场信息。保存处理机的现场信息。l(2) 按某种算法选取进程。按某种算法选取进程。l(3) 把处理器分配给进程。把处理器分配给进程。操作系统chapter(3)2进程调度中的三个基本机制为了实现进程调度，应具有如下三个基本机制：为了实现进程调度，应具有如下三个基本机制：(1) 排队器。排队器。将系统中所有的就绪进程按照一定的方将系统中所有的就绪进程按照一定的方式排成一个或多个队列，以便调度程序能最快地式排成一个或多个队列，以便调度程序能最快地找到它。找到它。(2) 分派器。分派

13、器。分派器把由进程调度程序所选定的进程，分派器把由进程调度程序所选定的进程，从就绪队列中取出该进程，然后将处理机分配给从就绪队列中取出该进程，然后将处理机分配给它它 (3) 上下文切换机制。上下文切换机制。当对处理机进行切换时，会发当对处理机进行切换时，会发生两对上下文切换操作。生两对上下文切换操作。操作系统chapter(3)3进程调度方式l进程调度可采用下述两种调度方式。进程调度可采用下述两种调度方式。1) 非抢占方式非抢占方式(Nonpreemptive Mode)l在采用这种调度方式时，一旦把处理机分在采用这种调度方式时，一旦把处理机分配给某进程后，不管它要运行多长时间，配给某进程后，

14、不管它要运行多长时间，都一直让它运行下去，决不会因为时钟中都一直让它运行下去，决不会因为时钟中断等原因而抢占正在运行进程的处理机，断等原因而抢占正在运行进程的处理机，也不允许其它进程抢占已经分配给它的处也不允许其它进程抢占已经分配给它的处理机。理机。操作系统chapter(3)3进程调度方式l在采用非抢占调度方式时，可能引起进程调在采用非抢占调度方式时，可能引起进程调度的因素可归结为如下几个：度的因素可归结为如下几个：(1) 正在执行的进程执行完毕，或因发生某事正在执行的进程执行完毕，或因发生某事件而不能再继续执行；件而不能再继续执行；(2) 执行中的进程因提出执行中的进程因提出I/O请求而暂

15、停执行；请求而暂停执行；(3) 在进程通信或同步过程中执行了某种原语在进程通信或同步过程中执行了某种原语操作，如操作，如P操作操作(wait操作操作)、Block原语、原语、Wakeup原语等。原语等。操作系统chapter(3)3进程调度方式l非抢占方式的优点：非抢占方式的优点：系统开销小；系统开销小；采采用非抢占方式时，程序员可以在某种程度用非抢占方式时，程序员可以在某种程度上预知进程的运行轨迹，程序设计相应简上预知进程的运行轨迹，程序设计相应简化。化。 l缺点：损失了系统的并发性，使系统不缺点：损失了系统的并发性，使系统不能根据内部的并发事件及时实施进程调度，能根据内部的并发事件及时实施

16、进程调度，难以实现要求比较严格的实时调度要求。难以实现要求比较严格的实时调度要求。操作系统chapter(3)3进程调度方式l2) 抢占方式抢占方式(Preemptive Mode)l这种调度方式允许调度程序根据某种原则去这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占方式的优点是，处理机重新分配给另一进程。抢占方式的优点是，可以防止一个长进程长时间占用处理机，能为大可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响多数进程提供更公平的服务，特别是能满足对响

17、应时间有着较严格要求的实时任务的需求。抢占应时间有着较严格要求的实时任务的需求。抢占调度方式是基于一定原则的：调度方式是基于一定原则的：操作系统chapter(3)3进程调度方式(1) 优先权原则。优先权原则。通常是对一些重要的和紧急通常是对一些重要的和紧急的作业赋予较高的优先权。允许优先权高的作业赋予较高的优先权。允许优先权高的新到进程抢占当前进程的处理机。的新到进程抢占当前进程的处理机。(2) 短作业短作业(进程进程)优先原则。优先原则。短作业短作业(进程进程)可可以抢占当前较长作业以抢占当前较长作业(进程进程)的处理机。的处理机。(3) 时间片原则。时间片原则。各进程按时间片轮流运行，各

18、进程按时间片轮流运行，当一个时间片用完后，便停止该进程的执当一个时间片用完后，便停止该进程的执行而重新进行调度。行而重新进行调度。操作系统chapter(3)3.1.3 中级调度又称中程调度，对换调度。为提高内存的又称中程调度，对换调度。为提高内存的利用率和系统的呑吐量，中级调度决定利用率和系统的呑吐量，中级调度决定哪些进程被允许参与竞争处理器资源，哪些进程被允许参与竞争处理器资源，哪些进程调至外存上去等待，在合适的哪些进程调至外存上去等待，在合适的情况下，再重新调入内存，并将其挂在情况下，再重新调入内存，并将其挂在就绪队列上，以恢复对处理器资源的竞就绪队列上，以恢复对处理器资源的竞争。争。操

19、作系统chapter(3)3.2 调度队列模型和调度准则3.2.1调度队列模型1仅有进程调度的调度队列模型l在分时系统中，通常仅设置了进程调度，用户键在分时系统中，通常仅设置了进程调度，用户键入的命令和数据都直接送入内存。对于命令，是入的命令和数据都直接送入内存。对于命令，是由由OS为之建立一个进程。系统可以把处于就绪状为之建立一个进程。系统可以把处于就绪状态的进程组织成栈、树或一个无序链表，至于到态的进程组织成栈、树或一个无序链表，至于到底采用其中哪种形式，则与底采用其中哪种形式，则与OS类型和所采用的调类型和所采用的调度算法有关。度算法有关。操作系统chapter(3)1仅有进程调度的调度

20、队列模型l每个进程在执行时都可能出现以下三种情况：每个进程在执行时都可能出现以下三种情况：l(1) 任务在给定的时间片内已经完成，该进程便在任务在给定的时间片内已经完成，该进程便在释放处理机后进入完成状态；释放处理机后进入完成状态；l(2) 任务在本次分得的时间片内尚未完成，任务在本次分得的时间片内尚未完成，OS便便将该任务再放入就绪队列的末尾；将该任务再放入就绪队列的末尾；l(3) 在执行期间，进程因为某事件而被阻塞后，被在执行期间，进程因为某事件而被阻塞后，被OS放入阻塞队列。放入阻塞队列。操作系统chapter(3)就 绪 队 列阻 塞 队 列进程调度CPU进程完成等待事件交互用户事件出

21、现时间片完图图 仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型操作系统chapter(3)2具有高级和低级调度的调度队列模型在批处理系统中，不仅需要进程调度，而且在批处理系统中，不仅需要进程调度，而且还需有作业调度，由后者按一定的作业调还需有作业调度，由后者按一定的作业调度算法，从外存的后备队列中选择一批作度算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就业调入内存，并为它们建立进程，送入就绪队列，然后才由进程调度按照一定的进绪队列，然后才由进程调度按照一定的进程调度算法选择一个进程，把处理机分配程调度算法选择一个进程，把处理机分配给该进程。给该进程。操作系统c

22、hapter(3)操作系统chapter(3)3同时具有三级调度的调度队列模型当在当在OS中引入中级调度后，人们可把进程的就绪状中引入中级调度后，人们可把进程的就绪状态分为内存就绪态分为内存就绪(表示进程在内存中就绪表示进程在内存中就绪)和外存和外存就绪就绪(进程在外存中就绪进程在外存中就绪)。类似地，也可把阻塞。类似地，也可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下

23、，又可使外存就绪转为内存就绪。级调度的作用下，又可使外存就绪转为内存就绪。操作系统chapter(3)3同时具有三级调度的调度队列模型操作系统chapter(3)3.2.2选择调度方式和调度算法的若干准则1面向用户的准则l(1)周转时间短周转时间短l 所谓所谓周转时间周转时间是指从作业被提交给系统是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。开始，到作业完成为止的这段时间间隔。包括：包括：1、作业在外存、作业在外存后备队列上等待调度后备队列上等待调度的时间的时间，2、进程在就绪队列上、进程在就绪队列上等待进程调等待进程调度的时间度的时间,3 、进程在、进程在CPU上上执行的时间执行

24、的时间，4 、进程、进程等待等待I/O操作完成的操作完成的时间时间。操作系统chapter(3)1面向用户的准则l作业的周转时间：作业的周转时间：l ti i = tcici-tsisil ti i:作业周转时间作业周转时间l tcici：作业完成时间：作业完成时间l tsisi: 作业提交时间作业提交时间 其中，其中，n为被测定作业流中的作业数为被测定作业流中的作业数操作系统chapter(3)1面向用户的准则 T：衡量不同调度算法对同一个作业流的性能：衡量不同调度算法对同一个作业流的性能 W：同一调度算法对不同作业流的性能衡量：同一调度算法对不同作业流的性能衡量 操作系统chapter(3

25、)1面向用户的准则l(2)响应时间快响应时间快l 所谓所谓响应时间响应时间是指从用户通过键盘是指从用户通过键盘提交提交一个请求开始一个请求开始，直至，直至系统首次产生响应系统首次产生响应为为止的时间。止的时间。包括：包括：1、从键盘输入的、从键盘输入的请求信请求信息传送到处理机息传送到处理机的时间，的时间，2、处理机对请求、处理机对请求信息信息进行处理进行处理的时间，的时间，3、以及将所形成的、以及将所形成的响应信息响应信息送回到终端显示器送回到终端显示器的时间。的时间。操作系统chapter(3)1面向用户的准则l(3)截至时间的保证截至时间的保证l 所谓所谓截止时间截止时间是指某任务是指某

26、任务必须开始执行的必须开始执行的最迟时间最迟时间，或者，或者必须完成的最迟时间必须完成的最迟时间。l(4)优先权准则优先权准则l 为了便于让某些为了便于让某些紧急的作业紧急的作业能得到能得到及时的及时的处理处理，在选择调度算法时还应该遵循优先，在选择调度算法时还应该遵循优先权准则。权准则。操作系统chapter(3)2面向系统的准则l(1)系统吞吐量高系统吞吐量高l 所谓所谓吞吐量吞吐量是指在单位时间内系是指在单位时间内系统所完成的工作量。统所完成的工作量。 l(2)处理机利用率好处理机利用率好l(3)各类资源的平衡使用各类资源的平衡使用操作系统chapter(3)3.3调 度 算 法l先进先

27、出先进先出(FIFO)(FIFO)算法算法l短作业短作业( (进程进程) )优先调度算法优先调度算法l高优先权优先调度算法高优先权优先调度算法 l时间片轮转法时间片轮转法 l多级反馈队列多级反馈队列操作系统chapter(3)3.2.1先来先服务和短作业(进程)优先调度算法1先来先服务调度算法l将用户作业和就绪进程按将用户作业和就绪进程按提交顺序提交顺序或或变为变为就绪状态的先后就绪状态的先后排成队列，并按照先来先排成队列，并按照先来先服务的方式进行调度处理，是一种服务的方式进行调度处理，是一种最普遍最普遍和最简单和最简单的方法。它优先考虑在系统中的方法。它优先考虑在系统中等等待时间待时间最长

28、的作业，而最长的作业，而不管不管要求要求运行时间运行时间的长短。的长短。操作系统chapter(3)1先来先服务调度算法l该调度方式属于非抢占方式，获得处理机该调度方式属于非抢占方式，获得处理机的进程将一直运行，直到该进程完成或因的进程将一直运行，直到该进程完成或因进程本身发生某事件而阻塞后，才放弃处进程本身发生某事件而阻塞后，才放弃处理机。理机。DCBACPU完完成成操作系统chapter(3)1先来先服务调度算法FCFS算法比较有利于长作业算法比较有利于长作业(进程进程)，而不利，而不利于短作业于短作业(进程进程)。下表列出了。下表列出了JOB1、JOB2、JOB3、JOB4四个作业分别到

29、达系统的时四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时各自的完成时间，并计算出各自的周转时间和带权周转时间。间和带权周转时间。操作系统chapter(3)作作业业进进入入时时间间估估计计运运行行时时间间（分分钟钟）开开始始时时间间结结束束时时间间周周转转时时间间（分分钟钟）带带权权周周转转时时间间JOB18：001208：0010：001201JOB28：505010：0010：501202.4JOB39：001010：5011：0012012JOB49：502011：0011：20904.5作作业业平平均

30、均周周转转时时间间 T = 112.5作作业业带带权权平平均均周周转转时时间间 W = 4.97545019.9操作系统chapter(3)1先来先服务调度算法l这种调度从形式上讲是公平的，但它使这种调度从形式上讲是公平的，但它使短作业短作业要等待长作业的完成要等待长作业的完成，重要的重要的作业要作业要等待不重等待不重要要作业的完成。从这个意义上讲又是不公平的。作业的完成。从这个意义上讲又是不公平的。l 先进先出调度使响应时间的变化较小，因此先进先出调度使响应时间的变化较小，因此它比其它大多数调度都可预测。由于这种调度它比其它大多数调度都可预测。由于这种调度方法方法不能保证良好的响应时间不能保

31、证良好的响应时间，在处理交互式，在处理交互式用户时很少用这种方法。用户时很少用这种方法。l这种调度算法突出的优点是这种调度算法突出的优点是实现简单实现简单，但，但效率效率较低较低。操作系统chapter(3)2短作业(进程)优先调度算法l短作业优先调度算法短作业优先调度算法(SJF)是指对短作是指对短作业优先调度，即从后备队列中选择一个业优先调度，即从后备队列中选择一个或若干个或若干个估计运行时间最短估计运行时间最短的作业，将的作业，将它们调入内存。它们调入内存。 l短进程优先调度算法短进程优先调度算法(SPF)，是指对短，是指对短进程优先调度，即从就绪队列中选择一进程优先调度，即从就绪队列中

32、选择一个或若干个个或若干个估计运行时间最短估计运行时间最短的进程，的进程，为它们分配处理机，使之投入运行。为它们分配处理机，使之投入运行。操作系统chapter(3)2短作业(进程)优先调度算法作作业业进进入入时时间间估估计计运运行行时时间间（分分钟钟）开开始始时时间间结结束束时时间间周周转转时时间间（分分钟钟）带带权权周周转转时时间间JOB18：001208：0010：001201JOB28：505010：3011：201503JOB39：001010：0010：10707JOB49：502010：1010：30402作作业业平平均均周周转转时时间间 T = 95作作业业带带权权平平均均周周

33、转转时时间间 W = 3.2538013操作系统chapter(3)图 FCFS和SJF调度算法的性能 FCFS和SJF的性能比较 进程名 A B C D E 平 均 到达时间 0 1 2 3 4 作业 情况 调度 算法 服务时间 4 3 5 2 4 完成时间 4 7 12 14 18 周转时间 4 6 10 11 14 9 FCFS (a) 带权周转时间 1 2 2 5.5 3.5 2.8 完成时间 4 9 18 6 13 周转时间 4 8 16 3 9 8 SJF (b) 带权周转时间 1 2.67 3.1 1.5 2.25 2.1 操作系统chapter(3)2短作业(进程)优先调度算法

34、SJ(P)F调度算法也存在不容忽视的缺点：调度算法也存在不容忽视的缺点：该算法对长作业不利。该算法对长作业不利。(2) 该算法完全未考虑作业的紧迫程度，因而该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业不能保证紧迫性作业(进程进程)会被及时处理。会被及时处理。(3) 由于作业由于作业(进程进程)的长短只是根据用户所提的长短只是根据用户所提供的估计执行时间而定的，使该算法不一供的估计执行时间而定的，使该算法不一定能真正做到短作业优先调度。定能真正做到短作业优先调度。操作系统chapter(3)3.3.2高优先权优先调度算法l使用该算法前，系统将根据某些因素赋予每一使用该算法前，系统将根据

35、某些因素赋予每一个作业或进程一个对应的优先权，当用于作业个作业或进程一个对应的优先权，当用于作业调度时，从后备队列中选择若干个优先权最高调度时，从后备队列中选择若干个优先权最高的作业调入内存；当用于进程调度时，则把处的作业调入内存；当用于进程调度时，则把处理机分配给就绪队列中优先权最高的进程。理机分配给就绪队列中优先权最高的进程。 l优先权在调度过程中所起的作用与系统对优先权在调度过程中所起的作用与系统对进程调度采用非抢占式调度策略还是抢占式调进程调度采用非抢占式调度策略还是抢占式调度策略有关度策略有关操作系统chapter(3)1优先权调度算法的类型l1) 非抢占式优先权算法非抢占式优先权算

36、法l在这种方式下，系统一旦把处理机分配给就在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便绪队列中优先权最高的进程后，该进程便一直执一直执行下去行下去，直至完成；或因发生某，直至完成；或因发生某事件事件使该进程使该进程放放弃处理机弃处理机时，系统方可再将处理机重新分配给另时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的处理系统中；也可用于某些对实时性要求不严的实时系统中。实时系统中。操作系统chapter(3)1优先权调度算法的类型l2) 抢占式优先权调度算

37、法抢占式优先权调度算法l在这种方式下，系统同样是把处理机分配给在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，优先权最高的进程，使之执行。但在其执行期间，只要又只要又出现出现了另一个其了另一个其优先权更高的进程优先权更高的进程，进程，进程调度程序就调度程序就立即停止当前进程立即停止当前进程(原优先权最高的进原优先权最高的进程程)的执行，重新将处理机分配给新到的优先权最的执行，重新将处理机分配给新到的优先权最高的进程。高的进程。操作系统chapter(3)2优先权的类型 该算法总是把处理机分配给就绪队列中该算法总是把处理机分配给就绪队列中具有最高优先权的进程。具

38、有最高优先权的进程。首先考虑的问首先考虑的问题是题是如何确定进程的优先数，如何确定进程的优先数，一种是静一种是静态优先数，另一种是动态优先数。态优先数，另一种是动态优先数。l静态优先数法：静态优先数法：静态优先权是在创建进静态优先权是在创建进程时确定的，在整个运行期间不再改变。程时确定的，在整个运行期间不再改变。操作系统chapter(3)2优先权的类型l确定进程优先权的依据有如下三个方面：确定进程优先权的依据有如下三个方面：l(1) 进程类型。进程类型。通常，系统进程通常，系统进程(如接收进程、对如接收进程、对换进程、磁盘换进程、磁盘I/O进程进程)的优先权高于一般用户进的优先权高于一般用户

39、进程的优先权。程的优先权。l(2) 进程对资源的需求。进程对资源的需求。如进程的估计执行时间及如进程的估计执行时间及内存需要量的多少，对这些要求少的进程应赋予内存需要量的多少，对这些要求少的进程应赋予较高的优先权。较高的优先权。l(3) 用户要求。用户要求。这是由用户进程的紧迫程度及用户这是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。所付费用的多少来确定优先权的。操作系统chapter(3)2优先权的类型l动态优先权是指在创建进程时所赋予的动态优先权是指在创建进程时所赋予的优先权，优先权，但在其生命周期内优先权可以但在其生命周期内优先权可以动态变化动态变化。如随进程的推进或随其等待

40、如随进程的推进或随其等待时间的增加而改变的，以便获得更好的时间的增加而改变的，以便获得更好的调度性能。调度性能。操作系统chapter(3)3高响应比优先调度算法l先来先服务和短作业优先算法都有其片面先来先服务和短作业优先算法都有其片面性，先来先服务调度算法只考虑作业的等性，先来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间，短作待时间，而忽视了作业的运行时间，短作业优先算法则相反，只考虑了作业的运行业优先算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间。响应比时间，而忽视了作业的等待时间。响应比高者优先调度算法是介于这两种算法之间高者优先调度算法是介于这两种算法之间的一

41、种拆衷的算法。的一种拆衷的算法。操作系统chapter(3) 3.高响应比优先调度算法 优先权的变化规律可描述为：优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应该作业的响应时间，故该优先权又相当于响应比比RP。据此，又可表示为：。据此，又可表示为： 操作系统chapter(3)算法特点l(1) 作业的等待时间相同作业的等待时间相同，则要求服务的时间愈短，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。其优先权愈高，因而该算法有利于短作业。l(2) 服务的时间相同时服务的时间相同时，作业

42、的优先权决定于其等，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。实现的是先来先服务。l(3) 对于长作业对于长作业，作业的优先级可以随等待时间的，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。便可升到很高，从而也可获得处理机。 操作系统chapter(3)作业作业进入时间进入时间估计运行估计运行时间时间（分钟）（分钟）开始时间开始时间结束时间结束时间周转时间周转时间（分钟）（分钟）带权周转带权周转时间时间JOB18

43、：001208：0010：001201JOB28：503010：1011：00701.4JOB39：001010：0010：10707JOB49：502011：0011：20904.5作业平均周转时间作业平均周转时间 T = 87.5作业带权平均周转时间作业带权平均周转时间 W = 4.07535016.3操作系统chapter(3)3.3.3基于时间片的轮转调度算法1时间片轮转法1）基本原理）基本原理进程调度程序总是选择就绪队列中的第一个进程，进程调度程序总是选择就绪队列中的第一个进程，也就是说也就是说按照先来先服务原则调度按照先来先服务原则调度，但一旦进程，但一旦进程占用处理机则占用处理机

44、则仅使用一个时间片仅使用一个时间片。在使用完一个。在使用完一个时间片后，进程还没有完成其运行，它必须释放时间片后，进程还没有完成其运行，它必须释放出处理机给下一个就绪的进程，出处理机给下一个就绪的进程，返回到就绪队列返回到就绪队列的末尾的末尾重新排队等待再次运行。重新排队等待再次运行。操作系统chapter(3) 简单轮转法的调度模型操作系统chapter(3)1时间片轮转法2) 时间片大小的确定时间片大小的确定l在轮转法中，时间片长度的选取非常重要，时间在轮转法中，时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间。片长度的选择会直接影响系统开销和响应时间。l当当时间片很

45、大时时间片很大时，每个进程，每个进程得到比完成该进程得到比完成该进程多多的处理机时间，此时轮转调度模式的处理机时间，此时轮转调度模式退化为先进退化为先进先出模式先出模式。l当当时间片非常小时时间片非常小时，进程间的，进程间的转换开销转换开销就成了就成了决定因素，系统性能降低，大多数时间都消耗在决定因素，系统性能降低，大多数时间都消耗在处理机的转换上，只有少许用在用户的计算上。处理机的转换上，只有少许用在用户的计算上。操作系统chapter(3)1时间片轮转法l时间片的大小是该算法中的一个重要因素。应综合时间片的大小是该算法中的一个重要因素。应综合考虑以下几个因素来确定：考虑以下几个因素来确定：

46、 系统对响应时间的要求系统对响应时间的要求。系统要求对用户的响应时。系统要求对用户的响应时间短，则时间片要短；反之，时间片可以长一些。间短，则时间片要短；反之，时间片可以长一些。 就绪队列中进程的数目就绪队列中进程的数目。进程数目多，则时间片应。进程数目多，则时间片应短一些。短一些。 系统的处理能力系统的处理能力。 CPU运行速度快运行速度快,则时间片可以则时间片可以短；反之，时间片可以长一些。短；反之，时间片可以长一些。操作系统chapter(3)ABCDEABCDEABCEACE(a) q1(b) q412345678910 11 12 13 14 15 16 17t图图 q=1和和q=4

47、时的进程运行情况时的进程运行情况 操作系统chapter(3)图图 q=1和和q=4时进程的周转时间时进程的周转时间 进程名进程名 A B C D E 平均平均 到达时间到达时间 0 1 2 3 4 作业作业 情况情况 时时 间间 片片 服务时间服务时间 4 3 4 2 4 完成时间完成时间 15 12 16 9 17 周转时间周转时间 15 11 14 6 13 11.8 RR q=1 带权周转时间带权周转时间 3.75 3.67 3.5 3 3.33 3.46 完成时间完成时间 4 7 11 13 17 周转时间周转时间 4 6 9 10 13 8.4 RR q=4 带权周转时间带权周转时

48、间 1 2 2.25 5 3.33 2.5 操作系统chapter(3)2多级反馈队列调度算法l在多级反馈队列调度下，就绪队列被分在多级反馈队列调度下，就绪队列被分为若干个独立子队列。为若干个独立子队列。l但进程不是根据其性质或类型固定但进程不是根据其性质或类型固定地分属于一个队列，而是根据其使用地分属于一个队列，而是根据其使用CPU时间的长短来动态地决定进程属于时间的长短来动态地决定进程属于哪级队列。哪级队列。操作系统chapter(3)2多级反馈队列调度算法（1 1）* * 首先系统中设置多个就绪队列首先系统中设置多个就绪队列* * 每个就绪队列分配给不同时间片，优先每个就绪队列分配给不同

49、时间片，优先级高的为第一级队列，时间片最小，随着级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大队列级别的降低，时间片加大* * 各个队列按照先进先出调度算法，最后各个队列按照先进先出调度算法，最后一级采用时间片轮转一级采用时间片轮转操作系统chapter(3)（2 2）* * 一个新进程就绪后进入第一级队列一个新进程就绪后进入第一级队列末尾末尾* * 进程由于等待而放弃进程由于等待而放弃CPUCPU后，进入等待队后，进入等待队列，一旦等待的事件发生，则回到原来的列，一旦等待的事件发生，则回到原来的就绪队列就绪队列* * 如果它在一个时间片结束时尚未完成，调如果它在一个时间片结束

50、时尚未完成，调度程序便将该进程转入第二队列的末尾，度程序便将该进程转入第二队列的末尾，如果它在第二队列中运行一个时间片后仍如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，未完成，再依次将它放入第三队列，2多级反馈队列调度算法操作系统chapter(3)2多级反馈队列调度算法（3 3）* *系统从第一级调度，系统从第一级调度，仅当第一队列空闲时，仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；调度程序才调度第二队列中的进程运行；仅当第仅当第1(i-1)队列均空时，才会调度第队列均空时，才会调度第i队队列中的进程运行。列中的进程运行。* * 当有一个优先级更高的进程就绪

51、时，可以当有一个优先级更高的进程就绪时，可以抢占抢占CPUCPU，被抢占进程回到原来一级就绪队，被抢占进程回到原来一级就绪队列末尾。列末尾。操作系统chapter(3)2多级反馈队列调度算法操作系统chapter(3)3多级反馈队列调度算法的性能l多级反馈队列调度算法具有较好的性能，多级反馈队列调度算法具有较好的性能，能很好地满足各种类型用户的需要。能很好地满足各种类型用户的需要。l(1) 终端型作业用户终端型作业用户。由于终端型作业用户。由于终端型作业用户所提交的作业大多属于交互型作业，作业所提交的作业大多属于交互型作业，作业通常较小，系统只要能使这些作业通常较小，系统只要能使这些作业(进程

52、进程)在在第一队列所规定的时间片内完成，便可使第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。终端型作业用户都感到满意。操作系统chapter(3)(2) 短批处理作业用户短批处理作业用户。对于很短的批处理型。对于很短的批处理型作业，开始时像终端型作业一样，如果仅作业，开始时像终端型作业一样，如果仅在第一队列中执行一个时间片即可完成，在第一队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间。便可获得与终端型作业一样的响应时间。(3) 长批处理作业用户长批处理作业用户。对于长作业，它将依。对于长作业，它将依次在第次在第1，2，n个队列中运行，然后再个队列中运行，然后再

53、按轮转方式运行，用户不必担心其作业长按轮转方式运行，用户不必担心其作业长期得不到处理。期得不到处理。3多级反馈队列调度算法的性能操作系统chapter(3) 进程调度的时机当一个进程运行完毕，或由于某种错误而终止当一个进程运行完毕，或由于某种错误而终止运行运行当一个进程在运行中处于等待状态（等待当一个进程在运行中处于等待状态（等待I/OI/O）分时系统中时间片到分时系统中时间片到当有一个优先级更高的进程就绪（可抢占式）当有一个优先级更高的进程就绪（可抢占式）在进程通信中，执行中的进程执行了某种原语在进程通信中，执行中的进程执行了某种原语操作（操作（P P操作，阻塞原语，唤醒原语）操作，阻塞原语

54、，唤醒原语）操作系统chapter(3)3.4实 时 调 度l3.4.1实现实时调度的基本条件1提供必要的信息2系统处理能力强3采用抢占式调度机制4具有快速切换机制操作系统chapter(3)1提供必要的信息(1) 就绪时间。就绪时间。(2) 开始截止时间和完成截止时间。开始截止时间和完成截止时间。(3) 处理时间。处理时间。(4) 资源要求。资源要求。(5) 优先级。优先级。操作系统chapter(3)2系统处理能力强在实时系统中，若处理机的处理能力不够强，则在实时系统中，若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不有可能因处理机忙不过来而使某些实时任务不能得到及时处

55、理。假定系统中有能得到及时处理。假定系统中有m个周期性的个周期性的硬实时任务，它们的处理时间可表示为硬实时任务，它们的处理时间可表示为Ci，周，周期时间表示为期时间表示为Pi，则在单处理机情况下，必须，则在单处理机情况下，必须满足下面的限制条件：满足下面的限制条件： 11miiiPC操作系统chapter(3)2系统处理能力强l对于不能满足实时性要求的解决方法是提高系对于不能满足实时性要求的解决方法是提高系统的处理能力，其途径有二：其一仍是采用单统的处理能力，其途径有二：其一仍是采用单处理机系统，但须处理机系统，但须增强其处理能力增强其处理能力，以显著地，以显著地减少对每一个任务的处理时间；其

56、二是减少对每一个任务的处理时间；其二是采用多采用多处理机系统处理机系统。假定系统中的处理机数为。假定系统中的处理机数为N，则，则应将上述的限制条件改为：应将上述的限制条件改为：NPCmiii1操作系统chapter(3)3采用抢占式调度机制l在含有硬实时任务的实时系统中，广泛采用抢在含有硬实时任务的实时系统中，广泛采用抢占机制。这样便可满足该硬实时任务对截止时占机制。这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。间的要求。但这种调度机制比较复杂。l对于一些小型实时系统，如果能预知任务的开对于一些小型实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢始截止时

57、间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度时占调度机制，以简化调度程序和对任务调度时所花费的系统开销。所花费的系统开销。操作系统chapter(3)4具有快速切换机制为保证要求较高的硬实时任务能及时运行，为保证要求较高的硬实时任务能及时运行，在实时系统中还应具有快速切换机制。该在实时系统中还应具有快速切换机制。该机制应具有如下两方面的能力：机制应具有如下两方面的能力：l(1) 对外部中断的快速响应能力。对外部中断的快速响应能力。l(2) 快速的任务分派能力。快速的任务分派能力。 操作系统chapter(3)3.4.2实时调度算法的分类1非抢占式调度算法1) 非抢占式

58、轮转调度算法非抢占式轮转调度算法该算法常用于工业生产的群控系统中，由一台该算法常用于工业生产的群控系统中，由一台计算机控制若干个相同的计算机控制若干个相同的(或类似的或类似的)对象，为每对象，为每一个被控对象建立一个实时任务，并将它们排成一个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列中的第一一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行，而调度程轮转队列的末尾，等待下次调度运行，而调度程序再选择下一个序再选择下一个(队首队首)任务运行。任务运行。 操作系

59、统chapter(3)1非抢占式调度算法l2) 非抢占式优先调度算法非抢占式优先调度算法l如果在实时系统中存在着要求较为严格如果在实时系统中存在着要求较为严格(响应时间为数百毫秒响应时间为数百毫秒)的任务，则可采用非的任务，则可采用非抢占式优先调度算法为这些任务赋予较高抢占式优先调度算法为这些任务赋予较高的优先级。当这些实时任务到达时，把它的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。自我终止或运行完成后才能被调度执行。操作系统chapter(3)2抢占式调度算法在要求较严格的实时系统中，应采用抢

60、占式优先权在要求较严格的实时系统中，应采用抢占式优先权调度算法。可根据抢占发生时间的不同而进一步调度算法。可根据抢占发生时间的不同而进一步分成以下两种调度算法。分成以下两种调度算法。1) 基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占式优先权调度算法l在某实时任务到达后，如果该任务的优先级高于在某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢占当前任务当前任务的优先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断到来时。的处理机，而是等到时钟中断到来时。操作系统chapter(3)2抢占式调度算法l2) 立即抢占的优先权调度算法立即抢占的优先权调度算法l在这

61、种调度策略中，要求操作系统具在这种调度策略中，要求操作系统具有快速响应外部事件中断的能力。一旦出有快速响应外部事件中断的能力。一旦出现外部中断，只要当前任务未处于临界区，现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分便立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。这种算法能获配给请求中断的紧迫任务。这种算法能获得非常快的响应。得非常快的响应。操作系统chapter(3)图 实时进程调度 操作系统chapter(3) 时钟l时钟（时钟（clockclock），又称为定时器（），又称为定时器（timertimer） (1) (1) 时钟负责提供一天的时间时钟

62、负责提供一天的时间 (2) (2) 防止一个进程垄断防止一个进程垄断CPUCPU 时钟既不是块设备，也不是字符设备，时钟既不是块设备，也不是字符设备，但时钟软件通常也采用设备驱动程序的但时钟软件通常也采用设备驱动程序的形式形式操作系统chapter(3)1) 时钟硬件两种类型：两种类型：l比较简单的时钟被连到比较简单的时钟被连到110V110V或或220V220V的电源线上，的电源线上，每个电压周期产生一个中断，频率是每个电压周期产生一个中断，频率是50Hz50Hz或或60Hz60Hzl另一种时钟由三个部件构成：晶体振荡器、计另一种时钟由三个部件构成：晶体振荡器、计数器和存储寄存器数器和存储寄

63、存器 石英晶体产生的精确的周期信号，典型的范石英晶体产生的精确的周期信号，典型的范围是围是5 5到到100MHz100MHz 信号送到到计数器，使其递减计数至信号送到到计数器，使其递减计数至0 0。当。当计数器变为计数器变为0 0时，产生一个时，产生一个CPUCPU中断信号中断信号操作系统chapter(3)l可编程时钟操作方式：在单脉冲方式（可编程时钟操作方式：在单脉冲方式（one-shot one-shot modemode）下，当时钟启动时，它把存储寄存器的值）下，当时钟启动时，它把存储寄存器的值拷贝到计数器中，然后，晶体的每一个脉冲使计拷贝到计数器中，然后，晶体的每一个脉冲使计数器减数

64、器减1 1。当计数器为。当计数器为0 0时，产生一个中断，并停时，产生一个中断，并停止工作，直到软件再一次显式启动它。止工作，直到软件再一次显式启动它。l在方波方式（在方波方式（square-wave modesquare-wave mode）下，当计数器）下，当计数器为为0 0并产生中断时，存储寄存器的值自动拷贝到计并产生中断时，存储寄存器的值自动拷贝到计数器，这个过程不断地重复下去。周期性的中断数器，这个过程不断地重复下去。周期性的中断称为时钟滴答（称为时钟滴答（clock tick clock tick ）l可编程时钟的优点是其中断频率可由软件控制。可编程时钟的优点是其中断频率可由软件控

65、制。操作系统chapter(3)2) 时钟软件时钟硬件所做的工作是每隔一定的时间间隔产时钟硬件所做的工作是每隔一定的时间间隔产生一个中断。生一个中断。涉及时间的其他所有工作都必须由软件涉及时间的其他所有工作都必须由软件-时钟时钟驱动程序完成驱动程序完成操作系统chapter(3)3) 时钟软件功能 1维护日期时间维护日期时间 2防止进程超时运行防止进程超时运行 3对对CPU的使用情况记帐的使用情况记帐 4处理用户进程提出的处理用户进程提出的ALARM系统调用系统调用 5为系统本身各部分提供监视定时器为系统本身各部分提供监视定时器 6绘制绘制CPU运行直方图，完成监视和统计运行直方图，完成监视和

66、统计信息收集信息收集l系统的其他部分也需要定时器称为监视定时系统的其他部分也需要定时器称为监视定时器（器（watchdog timer）。）。操作系统chapter(3)3.4.3常用的几种实时调度算法l1 1最早截止时间优先即最早截止时间优先即EDFEDF算法算法l该算法是根据任务的开始截止时间来确定任务的该算法是根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。就绪队优先级。截止时间愈早，其优先级愈高。就绪队列按各任务截止时间的早晚排序。调度程序在选列按各任务截止时间的早晚排序。调度程序在选择任务时，总是选择就绪队列中的第一个任务。择任务时，总是选择就绪队列中的第一个任务。该算法既可用于抢占式调度，也可用于非抢占式该算法既可用于抢占式调度，也可用于非抢占式调度方式中。调度方式中。操作系统chapter(3)1最早截止时间优先算法l1) 非抢占式调度方式用于非周期实时任务非抢占式调度方式用于非周期实时任务l 有四个非周期任务，它们先后到达。系统首先调有四个非周期任务，它们先后到达。系统首先调度任务度任务1执行，在任务执行，在任务1执行期间，任务执行期间，任务2、3