计算机操作系统 第四版 汤小丹 梁红兵 哲凤屏_第3章(2016-2017-1)

1、第三章 处理机调度与死锁 第三章处理机调度与死锁 3.1 处理机调度的层次与调度算法的目标处理机调度的层次与调度算法的目标 3.2 作业与作业调度作业与作业调度 3.3 进程调度进程调度 3.4 实时调度实时调度 3.5 死锁概述死锁概述 3.6 预防死锁预防死锁 3.7 避免避免死锁死锁 3.8 死锁死锁的检测与解除的检测与解除 第三章 处理机调度与死锁 3.1 处理机调度的层次和调度算法的目标处理机调度的层次和调度算法的目标 3.1.1 处理机调度的层次处理机调度的层次 1. 高级调度高级调度(High Level Scheduling) 又称长程调度或作业调度，调度对象是作业。涉及 两个

2、决定： 1) 接纳多少个作业 ； 2) 接纳哪些作业。 l 在多道程序系统中，调度的实质是一种资源分配，处 理机调度是对处理机资源进行分配。处理机调度算法 是根据处理机分配策略所规定的处理机分配算法。 第三章 处理机调度与死锁 3.1.1 处理机调度的层次处理机调度的层次 2. 低级调度低级调度(Low Level Scheduling) 又称短程调度或进程调度，调度对象是进程。主要 功能是根据算法，决定就绪队列中的哪个进程应获得 处理机，并由分派程序将处理机分配给被选中的进程。 3. 中级调度中级调度(Intermediate Scheduling) 又称内存调度。主要目的是为了提高内存利用

3、率和系 统吞吐量。将那些暂时不能运行的进程调至外存上去等 待，称为就绪驻外存状态或挂起状态；把外存上的又具 备运行条件的就绪进程，重新调入内存，并修改其状态 为就绪状态，挂在就绪队列上等待进程调度。 第三章 处理机调度与死锁 3.1.2 处理机调度算法的目标处理机调度算法的目标 1. 处理机调度算法的共同目标处理机调度算法的共同目标 (1) 资源利用率。为提高系统的资源利用率，应使系统中 的处理机和其它所有资源都尽可能保持忙碌状态。 空闲等待时间有效工作时间 有效工作时间 的利用率 CPUCPU CPU CPU (2) 公平性 使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。 (3) 平

4、衡性 保持系统资源使用的平衡性。 (4) 策略强制执行 第三章 处理机调度与死锁 3.1.2 处理机调度算法的目标处理机调度算法的目标 2. 批处理系统的目标批处理系统的目标 平均周转时间短 周转时间，指从作业被提交给系统开始，到作业完 成为止的这段时间间隔。包括四部分时间：作业在 外存后备队上等待调度的时间；进程在就绪队列上 等待进程调度的时间，进程在CPU上执行的时间， 进程等待I/O操作完成的时间。 (2) 系统吞吐量高 吞吐量，指在单位时间内系统所完成的作业数。 (3) 处理机利用率高 第三章 处理机调度与死锁 3.1.2 处理机调度算法的目标处理机调度算法的目标 3. 分时系统的目标

5、分时系统的目标 响应时间快 响应时间快是选择分时系统中进程调度算法的重要 准则。响应时间，从用户通过键盘提交一个请求开始， 直到屏幕上显示出处理结果为止的一段时间间隔。 (2) 均衡性 系统响应时间的快慢应与用户所请求的复杂性相适应。 第三章 处理机调度与死锁 3.1.2 处理机调度算法的目标处理机调度算法的目标 4. 实时系统的目标实时系统的目标 截止时间的保证 截止时间：某任务必须开始执行的最迟时间，或必须 完成的最迟时间。调度算法必须保证实时任务对截止时 间的要求。 (2) 可预测性 第三章 处理机调度与死锁 3.2 作业和作业调度作业和作业调度 3.2.1 批处理系统中的作业批处理系统

6、中的作业 1. 作业和作业步作业和作业步 在作业运行期间，每个作业都必须经过若干个相对独 立，又相互关联的顺序加工步骤才能得到结果，每一 个加工步骤称为一个作业步。 2. 作业控制块（作业控制块（Job Control Block, JCB） 作业在系统中存在的标志，其中保存了系统对作业进 行管理和调度所需的全部信息。 第三章 处理机调度与死锁 3.2.1 批处理系统中的作业批处理系统中的作业 3. 作业运行的三个阶段和三种状态作业运行的三个阶段和三种状态 （1）收容阶段 用户提交的作业输入到硬盘上，再为该作业建立JCB， 并把它放入作业后备队列中。作业处于“后备状态”。 （2）运行阶段 作业

7、调度选中作业后，为其分配必要的资源和建立进 程，并放入就绪队列。一个作业从第一次进入就绪状 态开始，直到它运行结束前，处于“运行状态”。 （3）完成阶段 第三章 处理机调度与死锁 3.2.3 先来先服务先来先服务(FCFS)和短作业优先和短作业优先(SJF)调度算法调度算法 1. 先来先服务（先来先服务（first-come first-served,FCFS）调度算法）调度算法 最简单的调度算法，既可用于作业调度，也可用于进程调 度。当在作业调度中采用该算法时，系统将从后备队列中选 择最先进入该队列的作业，将它们调入内存；当在进程调度 采用FCFS算法时，从就绪的进程队列选择最先进入的进程。

8、 第三章 处理机调度与死锁 2. 短作业优先短作业优先(short job first, SJF)调度算法调度算法 SJF算法以作业的长短计算优先级，作业越短，其优 先级越高。 3.2.3 先来先服务先来先服务(FCFS)和短作业优先和短作业优先(SJF)调度算法调度算法 uSJF算法的缺点： (1) 必须预知作业的运行时间。 (2) 对长作业非常不利，长作业的周转时间会明显地增长。 (3) 在采用SJF算法时，人-机无法实现交互。 (4) 该调度算法完全未考虑作业的紧迫程度，故不能保 证紧迫性作业能得到及时处理。 第三章 处理机调度与死锁 3.2.4 优先级调度算法和高响应比优先调度算法优先

9、级调度算法和高响应比优先调度算法 1. 优先级调度算法优先级调度算法(priority-scheduling algorithm, PSA) PSA基于作业的紧迫程度，由外部赋予作业相应 的优先级，调度算法根据该优先级进行调度。PSA 可作为作业调度算法，也可作为进程调度算法。 第三章 处理机调度与死锁 要求服务时间 要求服务时间等待时间 优先权 优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应 时间，故该优先权又相当于响应比RP。据此，又可表示为： 要求服务时间 响应时间 要求服务时间 要求服务时间等待时间 优先权 2. 高响应比优先调度算法高响应比优先调度算法

10、(Higher Response Ratio Next, HRRN) 3.2.4 优先级调度算法和高响应比优先调度算法优先级调度算法和高响应比优先调度算法 HRRN考虑了作业的等待时间和作业运行时间。 第三章 处理机调度与死锁 3.3 进程调度进程调度 3.3.1 进程调度的任务、机制和方式进程调度的任务、机制和方式 1. 进程调度的任务进程调度的任务 (1) 保存处理机的现场信息 (2) 按某种算法选取进程 (3) 把处理器分配给进程 2. 进程调度机制进程调度机制 为了实现进程调度，应具有如下三个基本机制： (1)排队器。将系统中所有的就绪进程按照一定的方 式排成一个或多个队列。 第三章

11、处理机调度与死锁 3.3.1 进程调度的任务、机制和方式进程调度的任务、机制和方式 2. 进程调度机制进程调度机制 (2) 分派器。从就绪队列中取出由进程调度程序所选定的进 程，然后进行从分派器到新选出进程间的上下文切换，将 处理机分配给该进程。 (3) 上下文切换机制。两对上下文切换：操作系统将保 存当前进程的上下文，而装入分派程序的上下文，以便分 派程序运行；移出分派程序的上下文，而把新选进程的 CPU现场信息装入到处理机的各个相应寄存器中。 第三章 处理机调度与死锁 3进程调度方式进程调度方式 1) 非抢占方式(Nonpreemptive Mode) 在采用这种调度方式时，一旦把处理机分

12、配给某进程后， 不管它要运行多长时间，都一直让它运行下去，决不会因为 时钟中断等原因而抢占正在运行进程的处理机，也不允许其 它进程抢占已经分配给它的处理机。直至该进程完成，自愿 释放处理机，或发生某事件而被阻塞时，才再把处理机分配 给其他进程。 3.3.1 进程调度的任务、机制和方式进程调度的任务、机制和方式 自行分析：引起进程调度的原因。自行分析：引起进程调度的原因。 第三章 处理机调度与死锁 2) 抢占方式抢占方式(Preemptive Mode) 允许调度程序根据某种原则去暂停某个正在执行的进程， 将已分配给该进程的处理机重新分配给另一进程。抢占调 度方式是基于一定原则的，主要有如下几条

13、： 3进程调度方式进程调度方式 优先权原则。允许优先权高的新到进程抢占当前进 程的处理机。 短进程优先原则。允许新到的短进程短可以抢占当前 较长进程的处理机。 时间片原则。各进程按时间片轮流运行，当一个时间 片用完后，便停止该进程的执行而重新进行调度。 第三章 处理机调度与死锁 3.3.2 轮转调度算法轮转调度算法 1轮转法的基本原理轮转法的基本原理 基于时间片的轮转(Round Robin, RR)调度算法。就绪 队列上的每个进程每次仅运行一个时间片。 系统将所有的就绪进程按FCFS策略排成一个就绪队列, 每次调度时，把CPU分配给队首进程，并令其执行一个时 间片。当执行的时间片用完时，调度

14、程序便把处理机分配 给就绪队列中新的队首进程，同时也让它执行一个时间片。 这样就可以保证就绪队列中的所有进程，在一给定的时间 内，均能获得一时间片的处理机执行时间。 第三章 处理机调度与死锁 3.3.2 轮转调度算法轮转调度算法 2进程切换时机进程切换时机 若一个时间片未用完，正在运行的进程便已经完成， 则立即激活调度程序，将它从就绪队列中删除，再调度 就绪队列中队首的进程运行，并启动一个新的时间片。 在一个时间片用完时，计时器中断处理程序被激活。 3时间片大小的确定时间片大小的确定 时间片的大小对系统性能有很大的影响。可取的时间 片大小是略大于一次典型的交互所需要的时间，使大多 数交互式进程

15、能在一个时间片内完成。 第三章 处理机调度与死锁 3.3.3 优先级调度算法优先级调度算法 1. 优先级调度算法的类型优先级调度算法的类型 (1) 非抢占式优先级调度算法 (2) 抢占式优先级调度算法 把处理机分配给优先级最高的进程，使之执行。但在 执行期间，只要出现了另一个其优先级更高的进程，调 度程序就将处理机分配给新到的优先级最高的进程。 第三章 处理机调度与死锁 3.3.3 优先级调度算法优先级调度算法 2. 优先级的类型优先级的类型 (1) 静态优先级 静态优先级是在创建进程时确定的，在进程的整个运行 期间保持不变。确定优先级大小的依据有： 进程类型。通常系统进程的优先级高于一般用户

16、进 程；进程对资源的需求。对资源要求少的进程应赋 予较高的优先级；用户要求。 (2) 动态优先级 在创建进程初赋予一个优先级，然后其值随进程的推 进或等待时间的增加而改变。 第三章 处理机调度与死锁 3.3.3 多队列调度算法多队列调度算法 该算法将系统中的进程就绪队列从一个拆分为若 干个，将不同类型或性质的进程固定分配在不同的 就绪队列，不同的就绪队列采用不同的调度算法， 一个就绪队列中的进程可以设置不同的优先级，不 同的就绪队列也可设置不同的优先级。 第三章 处理机调度与死锁 图 3-5 多级反馈队列调度算法 就绪队列1 就绪队列2 就绪队列3 就绪队列n S1 S2 S3 至CPU 至C

17、PU 至CPU 至CPU (时间片：S1S2S3) 3.3.4 多级反馈队列多级反馈队列(multileved feedback queue)调度算法调度算法 1. 调度机制调度机制 第三章 处理机调度与死锁 (1) 设置多个就绪队列，并为各个队列赋予不同的优先级。 第一个队列的优先级最高，第二个队列次之，其余各队列 的优先权逐个降低。该算法赋予各个队列中进程执行时间 片的大小也各不相同。 3.3.4 多级反馈队列多级反馈队列(multileved feedback queue)调度算法调度算法 1. 调度机制调度机制 第三章 处理机调度与死锁 (2) 每个队列都采用FCFS算法。当一个新进程

18、进入内存 后，首先将它放入第一队列的末尾，按FCFS原则排队等 待调度。当轮到该进程执行时，如它能在该时间片内完 成，便可准备撤离系统；否则，调度程序便将该进程转 入第二队列的末尾，再同样地按FCFS原则等待调度执行； 如果它在第二队列中运行一个时间片后仍未完成，再依 次将它放入第三队列，如此下去，当一个长进程从 第一队列依次降到第n队列后，在第n队列中便采取按RR 方式运行。 3.3.4 多级反馈队列多级反馈队列(multileved feedback queue)调度算法调度算法 1. 调度机制调度机制 第三章 处理机调度与死锁 (3) 按队列优先级调度。仅当第一队列空闲时，调度程 序才调

19、度第二队列中的进程运行； 仅当第1(i-1) 队列 均空时，才会调度第i队列中的进程运行。如果处理机 正在第i队列中为某进程服务时，又有新进程进入优先 权较高的队列，则此时新进程将抢占正在运行进程的处 理机，即由调度程序把正在运行的进程放回到第i队列 的末尾，把处理机分配给新到的高优先权进程。 3.3.4 多级反馈队列多级反馈队列(multileved feedback queue)调度算法调度算法 1. 调度机制调度机制 第三章 处理机调度与死锁 3.3.6 基于公平原则的调度算法基于公平原则的调度算法 1. 保证调度算法保证调度算法 向用户所做出的保证并不是优先运行，而是明确的 性能保证，

20、该算法做到调度的公平性。在实施公平调 度算法时系统须具有的功能： (1) 跟踪计算每个进程自创建以来已经执行的处理时间。 (2) 计算每个进程应获得的处理机时间。 (3) 计算进程获得处理机时间的比率。 (4) 比较各进程获得处理机时间的比率。 (5) 调度程序应选择比率最小的进程将处理机分配给它， 并让该进程一直运行，直到超过最接近它的进程比率为止。 第三章 处理机调度与死锁 3.3.6 基于公平原则的调度算法基于公平原则的调度算法 2. 公平分享调度算法公平分享调度算法 在该调度算法中，调度的公平性主要是针对用户 而言，使所有用户能获得相同的处理机时间，或所 要求的时间比例。 第三章 处理

21、机调度与死锁 3.4 实实 时时 调调 度度 3.4.1实现实时调度的基本条件实现实时调度的基本条件 1提供必要的信息提供必要的信息 (1) 就绪时间。该任务成为就绪状态的起始时间； (2) 开始截止时间和完成截止时间；(3) 处理时间； (4) 资源要求；(5) 优先级。如果某任务的开始截止时间 已经错过，则为该任务赋予“绝对”优先级；如果开始截 止时间的推迟对任务的继续运行无重大影响，则可为该 任务赋予“相对”优先级。 第三章 处理机调度与死锁 2系统处理能力强系统处理能力强 在实时系统中，通常都有着多个实时任务。假定系统 中有m个周期性的硬实时任务，它们的处理时间可表示为 Ci，周期时间

22、表示为Pi，则在单处理机情况下，必须满足 下面的限制条件： 3.4.1实现实时调度的基本条件实现实时调度的基本条件 1 1 m i i i P C 提高系统处理能力的途径：其一是增强单处理机系统 的处理能力，以显著地减少对每一个任务的处理时间； 其二是采用多处理机系统。 N P C m i i i 1 第三章 处理机调度与死锁 3.4.1实现实时调度的基本条件实现实时调度的基本条件 3采用抢占式调度机制采用抢占式调度机制 在含有硬实时任务的实时系统中，广泛采用抢占机制。 当一个优先权更高的任务到达时，允许将当前任务暂时挂 起，而令高优先权任务立即投入运行，这样便可满足该硬 实时任务对截止时间的

23、要求。 4具有快速切换机制具有快速切换机制 (1)对外部中断的快速响应能力。具有快速硬件中断机构 (2) 快速的任务分派能力。适当地减小每个运行功能单位， 以减少任务切换的时间开销。 第三章 处理机调度与死锁 3.4.2实时调度算法的分类实时调度算法的分类 1非抢占式调度算法非抢占式调度算法 1) 非抢占式轮转调度算法 该算法常用于工业生产的群控系统中，由一台计算机控 制若干个相同的(或类似的)对象，为每一个被控对象建立 一个实时任务，并将它们排成一个轮转队列。 2) 非抢占式优先调度算法 针对较为严格的实时任务，采用该算法为这些任务赋予 较高的优先级。当这些实时任务到达时，把它们安排在就 绪

24、队列的队首，等待当前任务自我终止或运行完成后才能 被调度执行。 第三章 处理机调度与死锁 3.4.2实时调度算法的分类实时调度算法的分类 2抢占式调度算法抢占式调度算法 1) 基于时钟中断的抢占式优先权调度算法 在某实时任务到达后，如果该任务的优先级高于 当前任务的优先级，这时并不立即抢占当前任务的处 理机，而是等到时钟中断到来时，调度程序才剥夺当 前任务的执行，将处理机分配给新到的高优先权任务。 第三章 处理机调度与死锁 3.4.2实时调度算法的分类实时调度算法的分类 2抢占式调度算法抢占式调度算法 2) 立即抢占(Immediate Preemption)的优先权调度算法 在这种调度策略中

25、，要求操作系统具有快速响应外 部事件中断的能力。一旦出现外部中断，只要当前任 务未处于临界区，便立即剥夺当前任务的执行，把处 理机分配给请求中断的紧迫任务。 第三章 处理机调度与死锁 图3-5 实时进程调度 (a) 非抢占式轮转调度 当前进程实时进程 实时进程请求调度 实时进程抢占当前 进程并立即执行 (d) 立即抢占的优先权调度 调度时间 进程 1进程 2 实时进程要求调度 进程 n实时进程 调度实时进程运行 (b) 非抢占式优先权调度 当前进程实时进程 实时进程请求调度 当前进程运行完成 调度时间 当前进程 实时进程请求调度 时钟中断到来时 调度时间 (c) 基于时钟中断抢占的优先权抢占调

26、度 调度时间 实时进程 第三章 处理机调度与死锁 3.4.3最早截止时间优先最早截止时间优先EDF(Earliest Deadline First)算法算法 该算法是根据任务的开始截止时间来确定任务的优 先级。截止时间愈早，其优先级愈高。该算法要求在系 统中保持一个实时任务就绪队列，该队列按各任务截止 时间的早晚排序；当然，具有最早截止时间的任务排在 队列的最前面。调度程序在选择任务时，总是选择就绪 队列中的第一个任务，为之分配处理机，使之投入运行。 最早截止时间优先算法既可用于抢占式调度，也可用于 非抢占式调度方式中。 第三章 处理机调度与死锁 图 3-6EDF算法用于非抢占调度的调度方式

27、1342 开始截止时间 任务执行 任务到达 12 34 1342 t 3.4.3最早截止时间优先最早截止时间优先EDF(Earliest Deadline First)算法算法 1. 非抢占式调度方式用于非周期实时任务 第三章 处理机调度与死锁 2. 抢占式调度方式用于周期实时任务抢占式调度方式用于周期实时任务 A1B1A2B1A3 B2 A4B2A5 B1A2A3B2A5 A1 B1 B1A2B1A3B2A4B2A5 B2 A1A2 B2 A3A4A5 B1 最后期限 B2 最后期限 A1 最后期限 A2 最后期限 A3 最后期限 A4 最后期限 A5 最后期限 到达时间、执行时间 和最后期

28、限 A1 固定优先级调度 固定优先级调度 A2B1A3A4A5，B2 A5，B2A4A1 (错过) A2B1A3 (错过) A1A2B1 (错过) A3A4A5，B2 0102030405060708090100时间t/ms 使用完成最后期限 最早和最后期限调度 (A有较高优先级) (B有较高优先级) 图3-7 EDF 算法 用于 抢占 调度 方式 第三章 处理机调度与死锁 3.4.4 最低松弛度优先最低松弛度优先LLF(Least Laxity First)算法算法 该算法是根据任务紧急的程度，来确定任务的优先 级。任务的紧急程度愈高，为该任务所赋予的优先级 就愈高，以使之优先执行。 在实现

29、该算法时要求系统中有一个按松弛度排序的 实时任务就绪队列，松弛度最低的任务排在队列最前 面，调度程序总是选择就绪队列中的队首任务执行。 该算法主要用于可抢占调度方式中。 第三章 处理机调度与死锁 A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 20406080100120140160 B 1 B 2 B 3 t 0 3.4.4 最低松弛度优先最低松弛度优先LLF(Least Laxity First)算法算法 图 3-8A和B任务每次必须完成的时间 u例：假如在一个实时系统中，有两个周期性实 时任务A和B，任务A要求每20ms执行一次，执 行时间为10ms；任务B只要求每50m

30、s执行一次， 执行时间为25ms。 第三章 处理机调度与死锁 t1 A1(10) 10203040506080 t 0 t10 B1(20) t2t3 70 A2(10)A3(10)A4(10) t4t5t6t7t8 B1(5)B2(15)B2(10) 图 3-9利用LLF算法进行调度的情况 3.4.4 最低松弛度优先最低松弛度优先LLF(Least Laxity First)算法算法 为保证不遗漏任何一次截止时间，应采用最低松 弛度优先的抢占调度策略。 松弛度=必须完成时间-其本身的运行时间-当前时间 第三章 处理机调度与死锁 u调度算法总结调度算法总结 1.1.先来闲服务算法（先来闲服务算

31、法（FCFSFCFS） 2.2.短作业优先（短作业优先（SJFSJF） 3. 优先级调度算法（优先级调度算法（PSA） 4.高响应比优先调度算法（高响应比优先调度算法（HRRN） 5.时间片轮转法（时间片轮转法（RR） 6.多级队列调度算法多级队列调度算法 7.多级反馈队列调度算法多级反馈队列调度算法 第三章 处理机调度与死锁 u问题分析问题分析 1. 有一个内存中只能装入两道作业的批处理系统，作业调度 采用短作业优先的调度算法，进程调度采用以优先数为基础 的抢占式调度算法。有下表所示的作业序列，表中所列的优 先数是指进程调度的优先数，且优先数越小优先级越高。 作业数作业数 到达时间到达时间估

32、计运行时间估计运行时间优先数优先数 A B C D 10: 00 10: 20 10: 30 10: 50 40分分 30分分 50分分 20分分 5 3 4 6 列出所有作业进入内存的时刻以及结束的时刻。 计算作业的平均周转时间。 第三章 处理机调度与死锁 u问题分析问题分析 2. 对下面的5个非周期性实时任务，按最早开始截止时 间优先调度算法应如何进行CPU调度？ 进程 到达时间执行时间开始截止时间 A B C D E 10 20 40 50 60 20 20 20 20 20 110 20 50 90 70 第三章 处理机调度与死锁 u问题分析问题分析 3. 若有3个周期性任务，任务A要

33、求每20ms执行一次， 执行时间为10ms；任务B要求每50ms执行一次，执行时 间为15ms，应如何按最低松弛优先算法对它们进行CPU 调度？ 第三章 处理机调度与死锁 3.5死死 锁锁 概概 述述 3.5.1 资源问题资源问题 系统中有许多不同类型的资源，其中需要采用互斥方法 访问的、不可以被抢占的资源常常会引起死锁。 1. 可重用性资源和消耗性资源可重用性资源和消耗性资源 2. 可抢占性资源和不可抢占性资源可抢占性资源和不可抢占性资源 l可重用性资源，一种可供用户重复使用多次的资源。其 请求和释放通常利用系统调用，系统大多数资源属于可重 用性资源。 l消耗性资源，又称临时性资源。是在进程

34、运行期间， 由进程动态地创建和消耗。如进程间通信的消息。 第三章 处理机调度与死锁 3.5.2 计算机系统中的死锁计算机系统中的死锁 死锁的起因源于多个进程对不可抢占资源或可消耗资源 的争夺。 1. 竞争不可抢占性资源引起死锁竞争不可抢占性资源引起死锁 系统中所拥有的不可抢占性资源不能满足诸进程运行 的需要，会使得进程在运行过程中，因争夺这些资源而 陷入僵局。例：两进程P1和P2准备写两文件f1和f2. P1 P2 Open(f1, w) Open(f2, w) Open(f2, w) Open(f1, w) 第三章 处理机调度与死锁 R 1 R 2 P 1 P 2 1. 竞争不可抢占性资源引

35、起死锁竞争不可抢占性资源引起死锁 例：两进程P1和P2准备写两文件R1和R2. P1 P2 Open(R1, w) Open(R2, w) Open(R2, w) Open(R1, w) 图3-12共享文件时的死锁情况 第三章 处理机调度与死锁 2. 竞争可消耗资源引起死锁竞争可消耗资源引起死锁 3.5.2 计算机系统中的死锁计算机系统中的死锁 S 2 P 1 S 3 P 3 S 1 P 2 图中S1、S2和S3是临时性资源。进程P1产生 消息S1，利用Send(P2, S1)原语将它发送给P2； 又要求从P3接收消息S3；进程P2产生消息S2， 利用Send(P3, S2)原语将它发送给P3

36、，又需要 接收进程P1所产生的消息S1；进程P3产生消息 S3，又要求从进程P2接收其所产生的消息S2； P1： send(P2, S1)； receive(P3, S3)； P2： send(P3, S2)； receive(P1, S1)； P3： send(P1, S3)； receive(P2, S2)； 如果三个进程间的消息通信如下：如果三个进程间的消息通信如下： P1： receive (P3, S3)； send(P2, S1)； P2： receive(P1, S1)； send(P3, S2)； P3： receive(P2, S2)； send(P1, S3)； 第三章 处

37、理机调度与死锁 3 3进程推进顺序不当引起死锁进程推进顺序不当引起死锁 进程在运行过程中，对资源进行申请和释放的顺序是否 合法，也是系统中是否会产生死锁的一个重要因素。 3.5.2 计算机系统中的死锁计算机系统中的死锁 进程推进顺序合法进程推进顺序合法 P1：Request(R1)P1：Request(R2) P1：Release(R1) P1： Release(R2) P2：Request(R2) P2：Request(R1) P2： Release(R2) P2：Release(R1)； 举例：系统中只有一台打印机R1和一台磁带机R2，供进 程P1和P2共享. 第三章 处理机调度与死锁 图

38、3-14进程推进顺序对死锁的影响 P 2Rel(R1) P 2Rel(R2) P 2Req(R1) P 2Req(R2) P 1Req(R1) P 1Req(R2) P 1Rel(R1) P1Rel(R2) D 3.5.2 计算机系统中的死锁计算机系统中的死锁 若并发进程若并发进程P1和和P2按曲线按曲线 所示的顺序推进，它们所示的顺序推进，它们 将进入不安全区将进入不安全区D内。内。 第三章 处理机调度与死锁 2) 进程推进顺序非法进程推进顺序非法 若并发进程P1和P2按曲线所示的顺序推进，它们将进 入不安全区D内。此时P1保持了资源R1，P2保持了资源R2， 系统处于不安全状态。因为这时两

39、进程再向前推进，便可 能发生死锁。例如，当P1运行到P1：Request(R2)时，将因 R2已被P2占用而阻塞；当P2运行到P2：Request(R1)时，也 将因R1已被P1占用而阻塞，于是发生了进程死锁。 3 3进程推进顺序不当引起死锁进程推进顺序不当引起死锁 3.5.2 计算机系统中的死锁计算机系统中的死锁 第三章 处理机调度与死锁 3.5.3 死锁的定义、必要条件和处理方法死锁的定义、必要条件和处理方法 如果一组进程中的每一个进程都在等待仅由该组进程 中的其它进程才能引发的事件，则该组进程是死锁的。 2. 产生死锁的必要条件产生死锁的必要条件 (1)互斥条件：指进程对所分配到的资源进

40、行排它性使 用，即在一段时间内某资源只由一个进程占用。如果 此时还有其它进程请求该资源，则请求者只能等待， 直至占有该资源的进程用毕释放。 1.死锁（死锁（Deadlock）的定义）的定义 第三章 处理机调度与死锁 (2) 请求和保持条件 指进程已经保持了至少一个资源，但又提出了新的 资源请求，而该资源又已被其它进程占有，此时请求 进程阻塞，但又对自己已获得的其它资源保持不放。 (3) 不可抢占条件 指进程已获得的资源，在未使用完之前，不能被剥夺， 只能在使用完时由自己释放。 2. 产生死锁的必要条件产生死锁的必要条件 (4) 循环等待条件 指在发生死锁时，必然存在一个进程资源的环形链。 3.

41、5.3 死锁的定义、必要条件和处理方法死锁的定义、必要条件和处理方法 第三章 处理机调度与死锁 3. 处理死锁的方法处理死锁的方法 3.5.3 死锁的定义、必要条件和处理方法死锁的定义、必要条件和处理方法 (1) 预防死锁。通过设置某些限制条件，破坏产生死锁的 四个必要条件中的一个或几个条件。 (2) 避免死锁。在资源的动态分配过程中，用某种方法去 防止系统进入不安全状态，从而避免发生死锁。 (3) 检测死锁。通过系统所设置的检测机构，及时地检测 出死锁的发生，并精确地确定与死锁有关的进程和资源； 然后，采取适当措施，从系统中将已发生的死锁清除掉。 (4) 解除死锁，与检测死锁相配套。 第三章

42、 处理机调度与死锁 3.6预预 防防 死死 锁锁 3.6.1破坏破坏“请求和保持请求和保持”条件条件 系统保证：当一个进程在请求资源时，它不能持有不可 抢占资源。可采用两种协议： 1 1第一种协议第一种协议 系统规定所有进程在开始运行之前，都必须一次性地申 请其在整个运行过程所需的全部资源。 通过破坏产生死锁的四个必要条件中的一个或几个。 第三章 处理机调度与死锁 3.6.1摒弃摒弃“请求和保持请求和保持”条件条件 2 2第二种协议第二种协议 允许一个进程只获得运行初期所需的资源后，便开始 运行。进程运行过程中再逐步释放已分配给自己的、且 已用毕的饿全部资源，然后再请求新的所需资源。 问题讨论

43、问题讨论：有一个进程，它所要完成的任务是，先将数 据从磁带尚复制到磁盘文件上，然后对磁盘文件进行排 序，最后把结果打印出来。 第三章 处理机调度与死锁 3.6.2破坏破坏“不可抢占不可抢占”条件条件 在采用这种方法时系统规定，进程是逐个地提出对资源 的要求的。当一个已经保持了某些资源的进程，再提出新 的资源请求而不能立即得到满足时，必须释放它已经保持 了的所有资源，待以后需要时再重新申请。 这意味着某一进程已经占有的资源，在运行过程中会被 暂时地释放掉，也可认为是被剥夺了，从而摒弃了“不可 抢占”条件。 第三章 处理机调度与死锁 3.6.3破坏破坏“循环循环等待等待”条件条件 系统将所有资源按

44、类型进行线性排队，并赋予不同的序 号。所有进程对资源的请求必须严格按照：资源序号递增 的次序提出。例如：一个进程在开始时，可以请求某类资 源Ri的单元。以后，当且仅当F(Rj)F(Ri)时，进程才可以请 求资源Rj的单元。这样，不可能再出现环路，破坏了“循 环等待”条件。 在采用这种策略时，应如何来规定每种资源的序号十分 重要。 第三章 处理机调度与死锁 3.7避免死锁避免死锁 3.7.1系统安全状态系统安全状态 1 1安全状态安全状态 在资源动态分配过程中，防止系统进入不安全状态。 安全状态安全状态指系统能按某种进程顺序(P1,P2,Pn) 来为 每个进程Pi分配其所需资源，直至满足每个进程

45、对资源 的最大需求，使每个进程都可顺利地完成。如果系统无 法找到这样一个安全序列，则称系统处于不安全状态不安全状态。 第三章 处理机调度与死锁 2 2安全状态举例安全状态举例 假定系统中有三个进程P1、P2和P3，共有12台磁带机。进 程P1总共要求10台磁带机，P2和P3分别要求4台和9台。在T0 时刻，资源分配如下表所示： 进 程 最 大 需 求 已 分 配 可 用 P1 10 5 3 P2 4 2 P3 9 2 3.7.1系统安全状态系统安全状态 u在T0时刻，存在一个安全序列，因此是安全的。 u若在T0时刻以后P3又请求1个资源，系统将资源分配 给P3，则进入不安全状态。 第三章 处理

46、机调度与死锁 3.7.2利用银行家算法避免死锁利用银行家算法避免死锁 银行家算法是一种最有代表性的避免死锁的算法， 该算法原本为银行系统设计的，以确保银行在发放现 金贷款时，不会发生不能满足所有客户需求的情况。 在避免死锁方法中允许进程动态地申请资源，但系统 在进行资源分配之前，应先计算此次分配资源的安全 性，若分配不会导致系统进入不安全状态，则分配， 否则等待。 第三章 处理机调度与死锁 3.7.2利用银行家算法避免死锁利用银行家算法避免死锁 1 1银行家算法中的数据结构银行家算法中的数据结构 (1)可利用资源向量Available，是一个含有m个元素的数组。 其中每一个元素代表一类可利用的

47、资源数目，其数值随该 类资源的分配和回收而动态地改变。如Availablej=K. (3) 分配矩阵Allocation，nm的矩阵。如果Allocationi,j=K， 则表示进程i当前已分得R j类资源的数目为K。 (4) 需求矩阵Need，nm的矩阵。如果Needi,j=K，则表 示进程i还需要R j类资源K个，方能完成其任务。 (2)最大需求矩阵Max，一个nm的矩阵。如果Maxi,j=K， 则表示进程i需要Rj类资源的最大数目为K。 第三章 处理机调度与死锁 2银行家算法银行家算法 设Request i是进程Pi的请求向量。当P i发出资源请求后， 系统按下述步骤进行检查： (3)

48、系统试探着把资源分配给进程Pi，并修改： Availablej= Availablej-Request ij； Allocationi,j=Allocationi,j+Request ij；Needi,j=Needi,j-Request ij； (4) 系统执行安全性算法，检查此次资源分配后系统是否 处于安全状态。 (1) 如果Request ijNeedi,j，转向步骤(2)；否则认为出错。 (2) 如果RequestijAvailablej，转向步骤(3)；否则，Pi须等待。 3.7.2利用银行家算法避免死锁利用银行家算法避免死锁 第三章 处理机调度与死锁 3 3安全性算法安全性算法 3.

49、7.2利用银行家算法避免死锁利用银行家算法避免死锁 (2)(2)从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程： Finishi=false； Needi,jWorkj； 若找到，执行步骤若找到，执行步骤(3)(3) 否则，执行步骤否则，执行步骤(4)(4)。 (1)(1)设置两个向量：工作向量设置两个向量：工作向量Work，Work=Available; Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。它表示系统是否有足够的资源分配给进程，使之运行完成。 (3)(3)当进程当进程Pi获得资源，可顺利执行，直至完成，并释放出分配给它获得资源

50、，可顺利执行，直至完成，并释放出分配给它 的资源，故应执行：的资源，故应执行：Workj=Workj+Allocationi,j； Finishi=true； go to step 2； (4)(4)如果所有进程的如果所有进程的Finishi=true都满足，则表示系统处于安全状态；都满足，则表示系统处于安全状态； 否则，系统处于不安全状态。否则，系统处于不安全状态。 第三章 处理机调度与死锁 4银行家算法之例银行家算法之例 假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C， 各资源的数量分别为10、5、7，在T0时刻的资源分配情况如图。 3.7.2利用银行家算法避免死锁利

51、用银行家算法避免死锁 Max Allocation Need Available 资源 情况 进 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 图3-15 T0时刻的资源分配表 第三章 处理机调度与死锁 (1) T0时刻的安全性：利用安全性算法对T0时刻的资源分配 情况进行分析可知，在T0时刻存在着一个安全序列P1，P3，

52、 P4，P2，P0，故系统是安全的。 图3-16T0时刻的安全序列 Work Need Allocation Work+Allocation 资源 情况 进 程 A B C A B C A B C A B C Finish P1 3 3 2 1 2 2 2 0 0 5 3 2 true P3 5 3 2 0 1 1 2 1 1 7 4 3 true P4 7 4 3 4 3 1 0 0 2 7 4 5 true P2 7 4 5 6 0 0 3 0 2 10 4 7 true P0 10 4 7 7 4 3 0 1 0 10 5 7 true 4银行家算法之例银行家算法之例 第三章 处理机调度

53、与死锁 再利用安全性算法检查此时系统是否安全。如图3-17所示。 图3-17P1申请资源时的安全性检查 Work Need Allocation Work+Allocation 资源 情况 进 程 A B C A B C A B C A B C Finish P1 2 3 0 0 2 0 3 0 2 5 3 2 true P3 5 3 2 0 1 1 2 1 1 7 4 3 true P4 7 4 3 4 3 1 0 0 2 7 4 5 true P0 7 4 5 7 4 3 0 1 0 7 5 5 true P2 7 5 5 6 0 0 3 0 2 10 5 7 true 4银行家算法之例银

54、行家算法之例 (2) P1 请求资源： P1 发出请求向量Request1(1,0,2)，系统按银 行家算法进行检查： Request1(1,0,2) Need1(1,2,2); Request1(1,0,2) Available1(3,3,2); 系统先假定可为P1分配资 源，并修改Available, Allocation1和Need1向量。 第三章 处理机调度与死锁 (3)P4请求资源：P4发出请求向量Request4(3,3,0)，系统按银行 家算法进行检查： Request4(3,3,0)Need4(4,3,1)； Request4(3,3,0)Available(2,3,0)，让P

55、4等待。 (4)P0请求资源：P0发出请求向量Requst0(0,2,0)，系统按银行 家算法进行检查： Request0(0,2,0)Need0(7,4,3)； Request0(0,2,0)Available(2,3,0)； 系统暂时先假定可为P0分配资源，并修改有关数据，如图 4银行家算法之例银行家算法之例 Allocation Need Available 资源 情况 进 程 A B C A B C A B C P0 0 3 0 7 3 2 2 1 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 第三章 处理机调度与死锁 (5)进行安全性检查：可用资源Available(2,1,0)已不能 满足任何进程的需要，故系统进入不安全状态，此时系统不 分配资源。 思考：思考：如果在银行家算法中，把P0发出的请求向量改为 Request0(0,1,0)，系统是否能将资源分配给它？ 4银行家算法之例银行家算法之例