计算机操作系统(汤子瀛)版chapter3

第三章 处理机调度与死锁

【教学目的】了解处理机调度的基本概 念、调度算法和类型及死锁的概念、产 生条件及检测与解除。 【教学重点】1、处理机调度原理及算法。 2、死锁的产生原因及检测与解除。 【分配课时】进度计划6学时

第三章 处理机调度与死锁3.1 处理机调度的基本概念 3.2 进程调度算法 3.3 实时调度

3.4 多处理机系统中的调度3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法和死锁避免 3.7 死锁的检测和解除

第一节 调度的类型和模型一、 调度类型 1、高级调度(High level Scheduling)(或作业//长程//接纳调度) (1)定义 把外存上处于后备队列中的那些作业调入内存，并为它们创建进程、 分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备 执行。 在批处理系统中，是先驻留在外存上的，因此需要有作业调度，以将 它们分批装入内存。在分时系统中，为了能及时响应，用户通过键 盘输入的命令或数据等，都是直接送入内存，因而无需配置作业调 度。 (2)决定作业调度的两个因素 ①接纳多少个作业 作业调度每次要接纳多少个作业进入内存，取决于多道程序度 (Degree of Multiprogramming),即允许有多少个作业同时在内存 中运行。 ②接纳哪些作业 应将哪些作业从外存调入内存，将取决于所采用的调度算法。最简 单的是先来先服务调度算法，较常用的一种是短作业优先调度算法， 还有基于作业优先权的调度算法、响应比高者优先的调度算法等。

第一节 调度的类型和模型 2、低级调度(Low Level Scheduling) 低级调度通常又称为进程调度、短程调度(ShortTerm Scheduling)在三种类型的OS中都必须配置这级 调度。进程调度可采取下述两种方法： (1)非抢占方式(Non-Preemptive Mode) 采取调度方式时，一旦处理机分配某进程后，便让该 进程一直执行，直至该进程完成或发生某事件而被阻 塞时，才再把处理机分配给其它进程，决不允许某进 程抢占已经分配出去的处理机。 这种调度方式的优点是实现简单、系统开销小，适用大 于多数的批处理系统环境。但它难于满足紧急任务的 要求。 (2)抢占方式(Preemptive Mode) 这种调度方式，允许调度程序根据某种原则，去停止 某个正在执行的进程，将已分配给该进程的处理机， 重新分陪另一进程。

第一节 调度的类型和模型 抢占的原则有： ①时间片原则 各进程按时间片运行，当一个时间片用完后，便停止 该进程的执行而重新进姓调度。这种原则适用于分时 系统、大多数实时系统，以及要求较高的批处理系统。 ②优先权原则 通常是对一些重要的和紧急的作业赋予

较高的优先权。 当这种作业到达时，如果其优先权比正在执行进程的 优先权高，便停止正在执行的进程，将处理机分配给 优先权高的进程，使之执行。 ③短作业(进程)优先原则 当新到达的作业(进程)比正在执行的作业(进程) 明显地短时，将剥夺长作业(进程)的执行，将处理 机分配给作业(进程),使之优先执行。

第一节 调度的类型和模型 3、中级调度 又称中程调度 (1)引入中级调度的目的 是为了提高内存的利用率和系统吐量。 (2)定义 应使那些暂时不能运行的进程不再占用宝贵的 内存空间，而将它们调至外存上去等待，称此 时的进程状态为就绪驻外存状态，或挂起状态。 当这些进程重又举备运行条件，且内存又稍有 空闲时，由中级调度决定，将外存上的那些重 又具备运动条件的就绪进程重新调入内存，并 修改其状态为就绪态，挂在就绪队列上，等待 进程调度。

第一节 调度的类型和模型 在上述三种调度中，进程调度的运行频率 最高，在分时系统中通常是10-100ms便进行 一次进程调度，因而进程调度算法不能太复 杂，以免占用太多的CPU时间。作业调度往 往是发生在一个(批)作业运行完毕，退出 系统又需要重新调入一个(批)作业进入内 存时，故作业调度的周期校长，大约几分钟 一次。因而也允许作业调度算法花费较多时 间，中级调度的运行频率基本上介入于上述 两种调度之间。

第一节 调度的类型和模型二、 调度队列模型 1、仅有进程调度的调度队列模型 在分时系统中通常仅 设置了进程调度。用户键入的命令和数据，都直接送 入内存。对于命令，由OS为之建立一个进程，并将它 排在就绪队列的末尾，然后按时间片轮转方式执行。 每个进程执行时，都可能出现这样三种可能。 (1)该任务在该时间片内已经完成，该进程释放处理机 后进入完成状态； (2)任务在本其对应的时间内尚未完成，OS便将任务放 在就绪队列的后面； (3)在执行期间，进程因某事件而被阻塞后，OS将它们 放入阻塞队列。

1.进程调度模型1)只有进程调度的调度队列模型

图 3 - 1 仅具有进程调度的调度队列模型

2、具有高级和低级调度的调度队列模型(见P99 图4-2) (1)在OS中不仅引入了进程调度，而且还进入 了作业调度。后者从外存的后备队列中选择一 批作业调入内存，为之创建进程后，送入就绪 队列； (2)在OS中设置多个阻塞队列。当系统中仅设 置一个阻塞队列时，可能会使该队列很长，尤 其当系统较大时，该队列中可能数百个进程。 为了提高队列的操作效率，通常都设置若干个 (1,2,...,n)阻塞队列，每个队列对应于

一种 引起进程阻塞的事件。。

2)具有高低级调度的调度队列模型

图 3-2 具有高、低两级调度的调度队列模型

3、同时具有三级调度的调度队列模型 当在OS中引入中级调度后，可把就绪态 分为内存就绪状态、外存就绪状态。可 把阻塞状态进一步分成内存阻塞和外存 阻塞两种状态。在调出操作的情况下， 可使内存就绪转变为外存就绪、内存阻 塞转变为外存阻塞；在中级调度的作用 下，外存就绪转变为内存就绪。

3)具有三级调度的调度队列模型

图 3-3 具有三级调度时的调度队列模型

三、选择调度方式和算法的 若干准则 面向用户的准则：周转时间短；响 应时间快；截止时间的保证；优先 权准则 面向系统的准则：系统吞吐量高；

处理机利用率好；各类资源的平衡利用

1、面向用户的准则 (1)周转时间短 通常把周转时间作为评价批处理系统的性能、选择作业调度方法与算法的准 则。 ①定义 是指从作业提交给系统开始，到作业完成为止这段时间间隔(称为作业周转 时间)。它包括： Ø作业在外存后备队列上等待(作业)调度的时间； Ø进程在就绪队列上等待进程调度的时间； Ø进程在CPU上执行的时间； Ø等待I/O操作完成的时间。 其中，第(2)、(3)、(4)项在一个作业处理过程中，可能发生多次。 对每个用户而言，作业的周转时间最短。但作为计算计系统的管理者， 希望平均周转时间最短；这不仅会有效地提高资源利用率，而且还可使 大多数用户满意。 平均周转时间： T= [ ] 带权周转时间: 作业周转时间T与系统为它提供的实际服务时间Ts之比，即W=T/Ts称为。而 平均带周转时间可表示为： W= [ ]

(2)响应时间快 响应时间是从用户通过键盘提交一个请求开始，直到在屏幕上显示 出结果为止的一段时间间隔。它包括： (1)从键盘输入的要求信息传送到处理机的时间； (2)处理机对请求信息进行处理的时间； (3)将所行成的响应回送到终端显示器的时间； (3)截止时间的保证 它是用来评价实时系统性的重要指标，因而是选择实时调度算法的 重要准则。 ①定义 截止时间：指某任务必须开始执行的最迟时间，或必须完成的最 迟时间，对于严格的实时系统，其调度方式和调度算法必须保证 这点。否则将可能引起难以预料的后果。 (4)优先权准则 让紧急的作业，得到及时的处理。

第二节 调度算法 调度算法是指：根据系统的资源分配策 略所规定的资源分配算法，对于不同的 系统和系统目标，通常采用不同的调度 算法。

调度算法 先进先出(FIFO)算法 最短CPU运行期优先调度算法

最高优先权优先调

度算法 轮转法

多级反馈队列

本文来源：https://www.bwwdw.com/article/4uei.html