处理机调度最新PPT课件

1、处理机调度最新 第三章第三章 处理机调度处理机调度(CPU调度调度) 无论在多道批处理系统还是分时系统中无论在多道批处理系统还是分时系统中, 系统中系统中 的用户进程数都远远超过处理机数的用户进程数都远远超过处理机数, 除用户进程要占除用户进程要占 用处理机外用处理机外, 操作系统还要建立若干个系统进程完成操作系统还要建立若干个系统进程完成 系统功能。这么多的进程竞争处理机系统功能。这么多的进程竞争处理机, 就要求系统提就要求系统提 供进程调度功能供进程调度功能, 以便采用一些策略以便采用一些策略, 将处理机动态将处理机动态 地分配给系统中的各个就绪进程地分配给系统中的各个就绪进程, 使之执行

2、。分配处使之执行。分配处 理机的任务是由处理机调度程序完成的理机的任务是由处理机调度程序完成的; 处理机是计处理机是计 算机最重要的资源算机最重要的资源, 如何提高处理机的利用率及改善如何提高处理机的利用率及改善 系统性能系统性能, 在很大程度上取决于处理机调度性能的好在很大程度上取决于处理机调度性能的好 坏坏, 处理机调度成为操作系统设计中心工作。处理机调度成为操作系统设计中心工作。 处理机调度最新 要解决的问题要解决的问题 WHAT：按什么原则分配按什么原则分配CPU 进程调度算法进程调度算法 WHEN：何时分配何时分配CPU 进程调度的时机进程调度的时机 HOW： 如何分配如何分配CPU

3、 CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换） 处理机调度最新 一批作业从进入系统到作业运行完毕可能经历三级一批作业从进入系统到作业运行完毕可能经历三级 调度调度高级、低级和中级调度。高级、低级和中级调度。 一一. 高级调度高级调度(High Scheduling) 又称为作业调度接纳调度或长程调度又称为作业调度接纳调度或长程调度, 用于批处理用于批处理 系统系统, 确定将外存后备队列中哪些作业调入内存确定将外存后备队列中哪些作业调入内存, 并为它并为它 们创建进程。实时系统和分时系统的前台作业不需要作们创建进程。实时系统和分时系统的前台作业不需要作 业调度。每次作业调度时业

4、调度。每次作业调度时, 都必须做出两个决定都必须做出两个决定: 1) 接纳多少个作业接纳多少个作业: 取决于多道程序度。取决于多道程序度。 2) 接纳哪些作业接纳哪些作业(用什么调度算法用什么调度算法): 先来先服务、短作业优先、优先权、响应比优先。先来先服务、短作业优先、优先权、响应比优先。 3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 高级、低级和中级调度高级、低级和中级调度 响应响应/运行运行 处理机调度最新 二二. 低级调度低级调度(进程调度进程调度,短程调度短程调度) 进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对CPU的竞争的竞争, 即即 按照一定的调

5、度算法从就绪队列中选中一个进程，把按照一定的调度算法从就绪队列中选中一个进程，把 CPU的使用权交给被选中的进程。它是最基本的一种的使用权交给被选中的进程。它是最基本的一种 调度调度, 批处理系统批处理系统, 实时系统和分时系统都必须有进程实时系统和分时系统都必须有进程 调度。它通过进程调度程序来完成。调度。它通过进程调度程序来完成。 1. 进程调度程序的主要功能可描述如下：进程调度程序的主要功能可描述如下： (1) 记录系统中各进程的状况记录系统中各进程的状况 为了很好地实现进程调度为了很好地实现进程调度, 进程调度程序首先必须进程调度程序首先必须 管理系统中各进程的管理系统中各进程的PCB

6、，将进程的状态变化及资源，将进程的状态变化及资源 需求情况及时地记录到需求情况及时地记录到PCB中。通过中。通过PCB变化来准确变化来准确 地掌握系统中所有进程的地掌握系统中所有进程的状态特征和执行情况状态特征和执行情况。 处理机调度最新 (2) 选择进程真正占有选择进程真正占有CPU 这是进程调度的实质这是进程调度的实质, 即按照系统规定的调度策略即按照系统规定的调度策略 从就绪队列中选择一个进程占有从就绪队列中选择一个进程占有CPU执行。进程调度执行。进程调度 依据的算法与系统的设计目标相一致。对于不同的系依据的算法与系统的设计目标相一致。对于不同的系 统统, 通常采用不同的调度策略。对于

7、批处理系统常采用通常采用不同的调度策略。对于批处理系统常采用 短进程的进程优先短进程的进程优先, 以减少各进程的周转时间。对于分以减少各进程的周转时间。对于分 时系统时系统, 更多地采用时间片轮转。更多地采用时间片轮转。 (3) 进行进程上下文的切换进行进程上下文的切换 当进程调度选中一个进程占有当进程调度选中一个进程占有CPU时时, 进程调度程进程调度程 序要做的主要工作则是进行进程上下文切换序要做的主要工作则是进行进程上下文切换: 将正在将正在 执行进程的运行现场保留在该进程的执行进程的运行现场保留在该进程的PCB中中, 以便以后以便以后 该进程恢复执行。将刚选中进程的运行现场恢复起来该进

8、程恢复执行。将刚选中进程的运行现场恢复起来, 并将并将CPU的控制权交给被选中进程的控制权交给被选中进程, 使其执行。使其执行。 处理机调度最新 2. 进程调度方式进程调度方式 (1)非抢占方式非抢占方式(Non preemptive mode) 在非抢占方式下在非抢占方式下, 调度程序一旦把调度程序一旦把 CPU分配给某分配给某 一进程后便让它一直运行下去一进程后便让它一直运行下去, 直到进程完成或发生直到进程完成或发生 某事件而不能运行时，才将某事件而不能运行时，才将CPU分给其它进程。分给其它进程。 这种调度方式通常用在批处理系统中。它的主要这种调度方式通常用在批处理系统中。它的主要 优

9、点是简单、系统开销小。优点是简单、系统开销小。 (2)抢占方式抢占方式(Preemptive mode) 当一个进程正在执行时，系统可以基于某种策略当一个进程正在执行时，系统可以基于某种策略 剥夺剥夺CPU给其它进程。剥夺的原则有：给其它进程。剥夺的原则有： 优先权原则、短进程优先原则、时间片原则。优先权原则、短进程优先原则、时间片原则。 显然这种调度方式多用在分时系统和实时系统中，显然这种调度方式多用在分时系统和实时系统中， 以便及时响应各进程的请求。以便及时响应各进程的请求。 处理机调度最新 3. 进程调度的时机进程调度的时机 所谓进程调度的时机，是指什么情况下引起进所谓进程调度的时机，是

10、指什么情况下引起进 程调度程序工作。进程调度的时机是与进程调度的程调度程序工作。进程调度的时机是与进程调度的 方式有关的。进程调度的时机如下：方式有关的。进程调度的时机如下： 正在执行的进程正确完成正在执行的进程正确完成, 或由于某种错误而终或由于某种错误而终 止运行止运行(陷阱或中断陷阱或中断) ； 执行中的进程提出执行中的进程提出I/O请求请求, 等待等待I/O完成时完成时; 在分时系统中在分时系统中, 按照时间片轮转按照时间片轮转, 分给进程的时分给进程的时 间片用完时；间片用完时； 按照优先级调度时按照优先级调度时, 有更高优先级进程变为就绪有更高优先级进程变为就绪 时时(抢占方式抢占

11、方式)； 在进程通讯中在进程通讯中, 执行中的进程执行了某种原语操执行中的进程执行了某种原语操 作作, 如如wait操作、阻塞原语和唤醒原语时操作、阻塞原语和唤醒原语时, 都可都可 能引起进程调度。能引起进程调度。 处理机调度最新 三三. 中级调度中级调度(中程调度中程调度) 中级调度使暂时停止的进程不再占用宝贵中级调度使暂时停止的进程不再占用宝贵 的内存资源的内存资源, 将它们调到外存上去成为挂起状将它们调到外存上去成为挂起状 态。当处于挂起就绪的进程重新具备运行条件态。当处于挂起就绪的进程重新具备运行条件 且内存稍有空闲时且内存稍有空闲时, 中级调度将它重新调入内中级调度将它重新调入内 存

12、存, 挂在活动就绪队列上等待进程调度。中级挂在活动就绪队列上等待进程调度。中级 调度实质上就是存储管理中的对换功能。调度实质上就是存储管理中的对换功能。 进程调度频率最高进程调度频率最高(10100ms/次次)调度算法调度算法 简单快速简单快速; 作业调度频率最低约几分钟一次作业调度频率最低约几分钟一次,调调 度算法允许花费较多的时间度算法允许花费较多的时间; 中级调度介于两中级调度介于两 者之间。者之间。 处理机调度最新 3.1.2. 调度队列模型调度队列模型 1. 仅有进程调度的仅有进程调度的调度队列模型调度队列模型 在分时系统中在分时系统中, 通常仅通常仅有进程调度有进程调度, 采用采用

13、FIFO算法。算法。 CPU就就 绪绪 队队 列列 阻阻 塞塞 队队 列列 时间片完时间片完 进程调度进程调度 等待事件等待事件 事件事件 出现出现 交互用户交互用户 完成完成 处理机调度最新 2. 具有高级和低级调度的具有高级和低级调度的调度队列模型调度队列模型 在批处理系统中在批处理系统中,不仅需要不仅需要进程调度而且需进程调度而且需 要作业调度。要作业调度。 CPU就就 绪绪 队队 列列 阻阻 塞塞 队队 列列 时间片完时间片完 进程进程 调度调度 事件事件1出现出现 后备后备 队列队列 完成完成 阻阻 塞塞 队队 列列事件事件2出现出现 阻阻 塞塞 队队 列列事件事件n出现出现 . 等

14、待事件等待事件1 等待事件等待事件2 等待事件等待事件n 作业作业 调度调度 处理机调度最新 3. 具有三级调度的具有三级调度的调度队列模型调度队列模型 在在具有三级调度具有三级调度系统中系统中, 增加了在外存的挂起状态增加了在外存的挂起状态 CPUCPU 就就 绪绪 队队 列列 就就 绪绪 挂挂 起起 时间片完时间片完 进程进程 调度调度 事事 件件 出出 现现 后备后备 队列队列 完成完成 阻阻 塞塞 挂挂 起起 阻阻 塞塞 队队 列列 挂起挂起 等待事件等待事件 作业作业 调度调度 事件出现事件出现 中级中级 调度调度 交互作业交互作业 调出调出 处理机调度最新 对于不同的系统对于不同的

15、系统, 有不同的设计目标有不同的设计目标, 采用不同采用不同 的调度算法。调度算法实质上是个策略问题的调度算法。调度算法实质上是个策略问题 面向用户的准则：面向用户的准则： l 周转时间短周转时间短 l 交互式系统的响应时间快交互式系统的响应时间快 l 截止时间保证截止时间保证 l 优先权准则优先权准则(公平合理公平合理) 面向系统的准则：面向系统的准则： l 单位时间内运行尽可能多的进程单位时间内运行尽可能多的进程, 吞吐量高吞吐量高 l 使处理机尽可能保持使处理机尽可能保持“忙碌忙碌”利用率高利用率高 l 使内外存、使内外存、I/O设备得以均衡、充分利用设备得以均衡、充分利用 3.1.3.

16、 调度算法的评价准则调度算法的评价准则 处理机调度最新 进程进程(作业作业)平均周转时间平均周转时间（周转时间、吞吐量）（周转时间、吞吐量） 设某进程创建时间为设某进程创建时间为Si, 结束的时间为结束的时间为Ei 它的周转时间它的周转时间(全过程所用时间全过程所用时间)为为 Ti =Ei Si 系统为它提供的实际服务时间为系统为它提供的实际服务时间为Tsi 则进程平均周转时间则进程平均周转时间T,带权平均周转时间带权平均周转时间W为：为： T W= = 其中，其中，n为被测定进程流中的进程数为被测定进程流中的进程数 n i=1 Ti n 1 n i=1 Ti n 1 Tsi 要设计一个理想的

17、调度算法是一件十分困难的要设计一个理想的调度算法是一件十分困难的 事事,在实际系统中在实际系统中, 调度算法往往折衷考虑。调度算法往往折衷考虑。 大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法 处理机调度最新 3.2 调度算法调度算法 1.先进先出调度算法先进先出调度算法(FIFO) (先来先服务先来先服务FCFS) 作业调度按照进入后备队列的先后次序调度作业调度按照进入后备队列的先后次序调度, 进程进程 调度按照进入进程就绪队列的先后次序来调度调度按照进入进程就绪队列的先后次序来调度 优点优点:实现简单实现简单 缺点缺点:不利于短作业不利于短作业(进程进程),紧

18、迫性作业紧迫性作业(进程进程)得不到得不到 及时处理及时处理 2.短作业短作业(进程进程)优先调度算法优先调度算法(SJF,SPF) 选择就绪队列中估计运行时间最短的进程投入运行选择就绪队列中估计运行时间最短的进程投入运行 优点优点: 平均周转时间平均周转时间,带权平均周转时间都改善带权平均周转时间都改善 缺点缺点: 对长作业对长作业(进程进程)非常不利非常不利 不能保证紧迫性作业不能保证紧迫性作业(进程进程)得到及时处理得到及时处理 估计运行时间不准确估计运行时间不准确 处理机调度最新 3. 优先权调度算法优先权调度算法(HPFHighest Priority First) 优先选择就绪队列

19、中优先权最高的进程投入运行优先选择就绪队列中优先权最高的进程投入运行 非抢占式优先权算法非抢占式优先权算法:仅在事件发生放弃处理机时仅在事件发生放弃处理机时 抢占式优先权算法抢占式优先权算法: 可将正在运行的运行权剥夺可将正在运行的运行权剥夺 优先权的类型优先权的类型 静态优先权静态优先权: 在进程创建时指定优先权在进程创建时指定优先权, 在进程运行在进程运行 时优先数不变时优先数不变 动态优先权动态优先权: 在进程创建时创立一个优先权，但在在进程创建时创立一个优先权，但在 其生命周期内优先数可以动态变化。如等待时间长其生命周期内优先数可以动态变化。如等待时间长 优先数可改变优先数可改变 确定

20、优先权的依据确定优先权的依据 进程类型、对资源的需求、根据用户要求进程类型、对资源的需求、根据用户要求 处理机调度最新 4. 高响应比优先调度算法：高响应比优先调度算法： 改进短作业改进短作业(进程进程)优先调度算法优先调度算法,优先权用下式动优先权用下式动 态计算出来态计算出来 优先权优先权= = 上式可看出上式可看出 等待时间相同要求服务的时间越短优先权越高等待时间相同要求服务的时间越短优先权越高, 有利于短作业有利于短作业 要求服务时间相同要求服务时间相同,等待时间越长优先权越高等待时间越长优先权越高,近近 似于先来先服务似于先来先服务 长作业的优先权会随等待时间加长而升高长作业的优先权

21、会随等待时间加长而升高,长作长作 业也会得到执行业也会得到执行 等待时间等待时间+要求服务时间要求服务时间 响应时间响应时间 要求服务时间要求服务时间 要求服务时间要求服务时间 处理机调度最新 把把CPU划分成若干时间片划分成若干时间片,并且按顺序赋给就绪并且按顺序赋给就绪 队列中的每一个进程，进程轮流占有队列中的每一个进程，进程轮流占有CPU，当时间，当时间 片用完时，即使进程未执行完毕，系统也剥夺该进片用完时，即使进程未执行完毕，系统也剥夺该进 程的程的CPU，将该进程排在就绪队列末尾。同时系统，将该进程排在就绪队列末尾。同时系统 选择另一个进程运行选择另一个进程运行 分时系统中常用时间片

22、轮转法分时系统中常用时间片轮转法 时间片选择问题：时间片选择问题： 固定时间片、可变时间片固定时间片、可变时间片 确定时间片大小的因素：确定时间片大小的因素： 系统响应时间、就绪进程个数、系统响应时间、就绪进程个数、CPU能力能力 5.时间片轮转调度算法时间片轮转调度算法 处理机调度最新 6.多队列反馈调度算法：多队列反馈调度算法： 系统按优先级设置多级就绪队列第一级优先级最高系统按优先级设置多级就绪队列第一级优先级最高 各就绪队列分配不同的时间片各就绪队列分配不同的时间片,优先级高的第一级队优先级高的第一级队 列时间片最小列时间片最小, 随着队列优先级的降低随着队列优先级的降低, 时间片加大

23、时间片加大 各个队列按照先进先出调度算法各个队列按照先进先出调度算法 一个新进程就绪后进入第一级就绪队列一个新进程就绪后进入第一级就绪队列 进程由于等待事件而放弃进程由于等待事件而放弃CPU后后, 进入等待队列进入等待队列, 一一 旦等待的事件发生旦等待的事件发生, 则回到原来的就绪队列则回到原来的就绪队列 当有一个优先级更高的进程就绪时当有一个优先级更高的进程就绪时, 可以抢占可以抢占CPU, 被抢占进程回到原来一级就绪队列末尾被抢占进程回到原来一级就绪队列末尾 当第一级队列空时当第一级队列空时, 就去调度第二级队列就去调度第二级队列, 如此类推如此类推 时间片用完后进程放弃时间片用完后进程

24、放弃CPU, 进入下一级就绪队列进入下一级就绪队列 处理机调度最新 实时系统中实时系统中, 对实时进程的调度有截止时间的要求对实时进程的调度有截止时间的要求 1.实现实时调度的基本条件实现实时调度的基本条件 1) 提供必要的信息提供必要的信息 就绪时间就绪时间、开始截止时间开始截止时间或或完成截止时间完成截止时间、处理时处理时 间间、资源要求资源要求、优先级优先级( 硬实时任务赋绝对优先级硬实时任务赋绝对优先级)。 2) 系统处理速度快系统处理速度快 若系统中有若系统中有m 个周期性硬实时任务个周期性硬实时任务, 处理时间为处理时间为Ci 周期时间为周期时间为Pi , 则处理机处理速度应达到可

25、调度条件则处理机处理速度应达到可调度条件: 1 (单处理机单处理机) n (多处理机多处理机) 3) 采用抢占式调度机制以满足对截止时间的要求采用抢占式调度机制以满足对截止时间的要求 4) 具有快速切换机制具有快速切换机制: 快速中断响应、快速任务分派快速中断响应、快速任务分派 3.3 实时调度实时调度 Ci Pii=1 n Ci Pii=1 n 处理机调度最新 2. 实时调度算法的分类实时调度算法的分类 1) 非抢占式调度算法非抢占式调度算法 非抢占式轮转调度算法非抢占式轮转调度算法(响应时间数秒到数十秒响应时间数秒到数十秒) 轮转一圈后调度轮转一圈后调度 非抢占式优先权调度算法非抢占式优先

26、权调度算法(响应时间数百毫秒响应时间数百毫秒) 当前进程完成当前进程完成(或被阻塞或被阻塞)后调度后调度 2) 抢占式调度算法抢占式调度算法 严格要求的实时系统严格要求的实时系统, 响应时间在数十毫秒以内响应时间在数十毫秒以内 基于时钟中断的抢占式调度算法基于时钟中断的抢占式调度算法 时钟中断到来时调度时钟中断到来时调度 立即抢占的优先权调度算法立即抢占的优先权调度算法 立即剥夺当前进程立即剥夺当前进程 调度时间见调度时间见P 83 图图3-6 处理机调度最新 3.几种常见的实时调度算法几种常见的实时调度算法 1) 最早截止时间优先算法最早截止时间优先算法(Earliest Deadline

27、First) 根据任务的开始截止时间确定优先级。根据任务的开始截止时间确定优先级。 2) 最低松弛度优先算法最低松弛度优先算法(Least Laxity First) 根据任务的松弛度根据任务的松弛度(紧急程度紧急程度)确定优先级确定优先级 根据任务完成截止时间和根据任务完成截止时间和本身运行时间本身运行时间确定松弛度确定松弛度 松弛度松弛度= 必须完成时间必须完成时间-本身运行时间本身运行时间-当前时间当前时间 P 85 图图 3-9 处理机调度最新 保存现场保存现场:顺序保存进程的上下文顺序保存进程的上下文, 包括程序计包括程序计 数器和其它寄存器数器和其它寄存器 用新状态和相关信息更新正

28、在运行进程的用新状态和相关信息更新正在运行进程的PCB 把该进程移至合适的队列把该进程移至合适的队列-就绪、阻塞就绪、阻塞 选择另一个要执行的进程选择另一个要执行的进程,更新该进程的更新该进程的PCB 从被选中进程中重装入从被选中进程中重装入 CPU 上下文上下文,恢复现场恢复现场 若无就绪进程若无就绪进程,系统会安排一个闲逛进程系统会安排一个闲逛进程(idle), 一直运行一直运行, 在执行过程中可接收中断。在执行过程中可接收中断。 3.4 CPU调度的实现调度的实现 处理机调度最新 操作系统的核心操作系统的核心 向上提供无中断的虚拟机器向上提供无中断的虚拟机器, 在核心内不允许中断在核心内

29、不允许中断 特点特点: 核心常驻内存核心常驻内存, 短小精焊短小精焊, 为进程运行提供舞台为进程运行提供舞台 核心的组成核心的组成 中断处理中断处理: 时钟、时钟、I/O、虚拟存储器、虚拟存储器 进程管理进程管理: 调度调度 控制控制 通讯通讯 互斥互斥 同步等同步等 原语管理原语管理: 提供一系列原语提供一系列原语, 同步同步, 通信通信, 创建创建, 撤消等撤消等 队列管理队列管理:中断之后调度之前中断之后调度之前(运行运行-就绪就绪-等待队列等待队列) 现场管理现场管理: 保存现场、恢复现场保存现场、恢复现场 时钟管理时钟管理: 绝对时钟、间隔时钟、绝对时钟、间隔时钟、虚时钟虚时钟 处理

30、机调度最新 保存现场、分析中断源保存现场、分析中断源 处理中断处理中断 原语管理、队列管理、时钟管理、进程调度原语管理、队列管理、时钟管理、进程调度 恢复现场恢复现场 中断中断 核心入口核心入口 核心处理流程核心处理流程 唯一入口唯一入口: : 中断中断, ,由硬件完成由硬件完成 作业作业: P101 2, 3, 5 处理机调度最新 3.5死锁死锁 死锁的基本概念死锁的基本概念 死锁的解决方案死锁的解决方案 （预防，避免，检测及解除）（预防，避免，检测及解除） 资源分配图资源分配图 处理机调度最新 3.5.1 死锁的基本概念死锁的基本概念 死锁死锁(Deadlock)的定义：的定义： 一组进程

31、中，每个进程都无限一组进程中，每个进程都无限等待等待被该组被该组 进程中进程中另一进程所占有的资源另一进程所占有的资源，因而永远无法，因而永远无法 得到的资源，这种现象称为进程死锁，这一组得到的资源，这种现象称为进程死锁，这一组 进程就称为死锁进程进程就称为死锁进程 说明说明: 参与死锁的进程最少是两个参与死锁的进程最少是两个 参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源 注意：注意：如果死锁发生，会浪费大量系统资源，如果死锁发生，会浪费大量系统资源， 甚至导致系统崩溃。甚至导致系统崩溃。 处理机调度最新

32、 死锁产生的原因死锁产生的原因 1.竞争资源引起竞争资源引起 永久性资源永久性资源:可被多个进程多次使用可被多个进程多次使用(可再用资源可再用资源) 剥夺性资源剥夺性资源(CPU、内存）、内存） 非剥夺性资源非剥夺性资源(磁带机、打印机磁带机、打印机) 竞争非剥夺性资源会引起死锁竞争非剥夺性资源会引起死锁 临时性资源临时性资源:只可使用一次的资源；只可使用一次的资源； 如信号量如信号量,中断信号中断信号,同步信号等同步信号等(可消耗性资源可消耗性资源) 竞争临时性资源也会引起死锁竞争临时性资源也会引起死锁 2. 进程推进顺序不当引起进程推进顺序不当引起 对资源采用对资源采用“申请申请-分配分配

33、-使用使用-释放释放”模式模式, 由由 于推进顺序不当两进程都要申请对方已占有的资源于推进顺序不当两进程都要申请对方已占有的资源 处理机调度最新 P1： 申请打印机申请打印机 申请扫描仪申请扫描仪 使用使用 释放打印机释放打印机 释放扫描仪释放扫描仪 P2： 申请扫描仪申请扫描仪 申请打印机申请打印机 使用使用 释放打印机释放打印机 释放扫描仪释放扫描仪 死锁的例子死锁的例子: 竞争非剥夺性资源进程推进顺序不当引起死锁竞争非剥夺性资源进程推进顺序不当引起死锁 处理机调度最新 Req(R1) Req(R2) Rel(R1) Rel(R2) Rel(R1) Rel(R2) Req(R1) Req(

34、R2) P2 P1 不安全区不安全区 竞争非剥夺性资源竞争非剥夺性资源 推进顺序不当推进顺序不当 进入进入不安全区不安全区 处理机调度最新 3.5.2产生死锁的四个必要条件产生死锁的四个必要条件 1) 互斥条件（资源独占）：互斥条件（资源独占）： 一个资源每次只能给一个进程使用一个资源每次只能给一个进程使用 2) 请求和保持条件请求和保持条件: (部分分配部分分配,占有申请占有申请) 在申请新资源的同时保持对原有资源的占有在申请新资源的同时保持对原有资源的占有 3) 不可剥夺条件（不可强占）：不可剥夺条件（不可强占）： 资源申请者不能强行的从资源占有者手中夺资源申请者不能强行的从资源占有者手中

35、夺 取资源取资源, 资源只能由占有者自愿释放资源只能由占有者自愿释放 4) 循环等待条件：循环等待条件： 存在进程存在进程-等待资源环形链等待资源环形链 P1 , P2 , , Pn, 其中其中P1等待等待P2占有的资源占有的资源, P2等待等待P3占有的资源占有的资源, , Pn等待等待P1占有的资源。占有的资源。 处理机调度最新 3.6 死锁的预防死锁的预防 3.6.1 强限制预防强限制预防 确定资源分配算法确定资源分配算法,保证不发生死锁。做法保证不发生死锁。做法 是破坏产生死锁的四个必要条件之一。是破坏产生死锁的四个必要条件之一。 1. 破坏破坏“请求和保持请求和保持(部分分配部分分配

36、)”条件条件 每个进程运行前必须一次性申请运行期所需每个进程运行前必须一次性申请运行期所需 全部资源全部资源, 若所需资源均可满足则全部分配。该若所需资源均可满足则全部分配。该 进程运行中不再请求资源进程运行中不再请求资源, 屏弃请求条件。屏弃请求条件。 简单、安全简单、安全; 但资源利用率低但资源利用率低,要长期等待。要长期等待。 2. 破坏破坏“不可剥夺不可剥夺”条件条件 在允许进程动态申请资源前提下在允许进程动态申请资源前提下, 规定规定: 某某 进程在申请新的资源不能立即满足而被阻塞之进程在申请新的资源不能立即满足而被阻塞之 前前, 必须释放已占有的资源必须释放已占有的资源(可能造成前

37、一段工可能造成前一段工 作失效作失效), 若需要再重新申请若需要再重新申请(增加开销增加开销)。 处理机调度最新 3.破坏破坏“循环等待循环等待”条件条件 采用资源有序分配法采用资源有序分配法:允许进程动态申请资允许进程动态申请资 源源, 对系统中所有资源编号对系统中所有资源编号, 进程申请资源时应进程申请资源时应 严格按资源编号递增次序进行严格按资源编号递增次序进行,否则不予分配。否则不予分配。 P1： 申请申请1 申请申请3 申请申请4 P2： 申请申请2 申请申请4 申请申请8 Pn： 申请申请1 申请申请2 申请申请8 缺点缺点: 资源利用仍不充分资源利用仍不充分 处理机调度最新 3.

38、6.2 避免死锁的避免死锁的银行家银行家算法算法 前面的三种方法由于前面的三种方法由于限制太强限制太强, 资源利用率资源利用率 都不太高。能否放宽限制条件？都不太高。能否放宽限制条件？ E.W.Dijkstra于于1968年提出年提出银行家算法银行家算法, 此此 算法要事先知道每个进程对资源的最大需求量算法要事先知道每个进程对资源的最大需求量; 算法的基本思路算法的基本思路:允许进程动态申请资源允许进程动态申请资源,但在每但在每 次分配资源前先对本次分配的安全性进行检查次分配资源前先对本次分配的安全性进行检查, 以判断这种分配是否可能导致死锁以判断这种分配是否可能导致死锁, 若分配可能若分配可

39、能 导致系统死锁导致系统死锁, 则不予分配则不予分配, 否则分配该资源。否则分配该资源。 (检查每次分配后是否仍存在安全分配检查每次分配后是否仍存在安全分配序列序列) 显然显然, 此法避免了死锁且资源利用率高。此法避免了死锁且资源利用率高。 处理机调度最新 1. 安全序列：安全序列： 如果进程序列如果进程序列P1，Pn对每个对每个Pi(1in)进程进程, 它以后尚需要的资源量不超过系统当前剩余资源量与它以后尚需要的资源量不超过系统当前剩余资源量与 所有所有Pj (j Available(2,3,0),让让P4等待等待 4) 若若P0请求资源请求资源,发出请求向量发出请求向量Request(0,

40、2,0)假定分配假定分配, 资源为资源为: 检查此刻的安全性：检查此刻的安全性：Available(2,1,0)已不满足任何已不满足任何 进程的需要进程的需要, 不安全不安全; 不予分配不予分配Available 仍为仍为(2,3,0) 。 Max Allocation Need Available 进程进程 A B C A B C A B C A B C P0 7 5 3 0 3 0 7 2 3 2 1 0 P1 3 2 2 2 0 0 1 2 2 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 处理机调度最新 检

41、查此刻的安全性检查此刻的安全性 Max Allocation Need Available 进程进程 A B C A B C A B C A B C P0 7 5 3 0 2 0 7 3 3 2 2 0 P1 3 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 安全安全, 可将可将(0,1,0)分配给分配给P0 若将若将P0请求改为请求改为Request(0,1,0)假定分配假定分配, 资源变为资源变为: 进进 Work Allocation Need W+ A Finish 程程 A

42、 B C A B C A B C A B C P1 2 2 0 3 0 2 0 2 0 5 2 2 true P3 5 2 2 2 1 1 0 1 1 7 3 3 true P4 7 3 3 0 0 2 4 3 1 7 3 5 true P0 7 3 5 0 2 0 7 3 3 7 5 5 true P2 7 5 5 3 0 2 6 0 0 10 5 7 true 处理机调度最新 3.7 死锁的检测与解除死锁的检测与解除 允许死锁发生，系统必须提供检测和解除死锁允许死锁发生，系统必须提供检测和解除死锁 的手段的手段, 操作系统应不断监视系统进展情况，判断死操作系统应不断监视系统进展情况，判断死

43、 锁是否发生。锁是否发生。 处理机调度最新 3.7.1死锁的检测死锁的检测 1. 资源分配图资源分配图 用有向图描述进程的死锁用有向图描述进程的死锁: 准确、形象准确、形象 系统由若干类资源构成，一类资源称为一个资源类；系统由若干类资源构成，一类资源称为一个资源类； 每个资源类中包含若干个同种资源，称为资源实例。每个资源类中包含若干个同种资源，称为资源实例。 二元组二元组G=（V，E） V：结点集，分为：结点集，分为P，R两部分两部分 P=p1,p2,pn R=r1,r2,rm E：边的集合：边的集合, 其元素为有序二元组其元素为有序二元组 分配边分配边(rj,pi): 资源实例资源实例进程的

44、一条有向边进程的一条有向边 申请边申请边(pi,rj): 进程进程资源类的一条有向边资源类的一条有向边 处理机调度最新 有环有死锁 处理机调度最新 有环无死锁 处理机调度最新 2. 死锁定理死锁定理 如果资源分配图中没有环路如果资源分配图中没有环路, 则系统中没有死锁则系统中没有死锁, 如果图中存在环路则系统中可能存在死锁。如果图中存在环路则系统中可能存在死锁。 如果每个资源类中只包含一个资源实例如果每个资源类中只包含一个资源实例, 则资源则资源 分配图环路是死锁存在的充分必要条件。分配图环路是死锁存在的充分必要条件。 资源分配图化简方法：资源分配图化简方法： 1）找一个非孤立点进程结点且只有

45、分配边，去掉分）找一个非孤立点进程结点且只有分配边，去掉分 配边，将其变为孤立结点。配边，将其变为孤立结点。 2）再把相应的资源分配给一个等待该资源的进程，）再把相应的资源分配给一个等待该资源的进程， 即将某进程的申请边变为分配边。即将某进程的申请边变为分配边。 3）重复）重复(1) (2)操作直到无法再化简操作直到无法再化简, 若所有若所有结点都为结点都为 孤立结点则无孤立结点则无死锁死锁, 否则死锁发生否则死锁发生 处理机调度最新 3.7.2死锁的解除死锁的解除 一旦死锁发生则采取专门的措施，解除一旦死锁发生则采取专门的措施，解除 死锁并以最小的代价恢复操作系统运行。死锁并以最小的代价恢复

46、操作系统运行。 死锁的解除死锁的解除(关键是代价最小关键是代价最小)： 1）重新启动）重新启动 2）撤消进程）撤消进程 3）剥夺资源）剥夺资源 4）进程回退）进程回退 处理机调度最新 处理机调度处理机调度 (1) 高级调度高级调度(作业调度接纳调度或长程调度作业调度接纳调度或长程调度) 将后备队列中作业调入内存将后备队列中作业调入内存,并创建进程。并创建进程。 (2)低级调度低级调度(进程调度进程调度,短程调度短程调度) 从就绪队列中选中一进程从就绪队列中选中一进程,把把CPU使用权交给它。使用权交给它。 (3)中级调度中级调度: 内存紧张时将内存的进程挂起调到外存内存紧张时将内存的进程挂起调

47、到外存 或内存稍有空闲时将它激活重新调入内存或内存稍有空闲时将它激活重新调入内存 2. 进程调度方式进程调度方式 (1)非抢占方式非抢占方式(Non preemptive mode) (2)抢占方式抢占方式(Preemptive mode) 3. 进程调度的时机进程调度的时机 (1) 执行进程正确完成执行进程正确完成 或错误终止或错误终止 (2) 执行进程提出执行进程提出I/O请求请求, 等待等待I/O完成时完成时; (3) 分时系统时间片轮转分时系统时间片轮转, 分给进程的时间片用完时分给进程的时间片用完时 (4) 优先级调度优先级调度, 抢占方式中有更高优先级进程就绪抢占方式中有更高优先级

48、进程就绪 (5) 执行进程执行执行进程执行wait、阻塞原语和唤醒原语等操作、阻塞原语和唤醒原语等操作 处理机调度最新 4. 调度算法调度算法 (1)先进先出调度算法先进先出调度算法(FIFO) (先来先服务先来先服务FCFS) (2)短作业短作业(进程进程)优先调度算法优先调度算法(SJF,SPF) (3)优先权调度算法优先权调度算法(HPFHighest Priority First) (4)高响应比优先调度算法高响应比优先调度算法 (5)时间片轮转调度算法时间片轮转调度算法 (6)多队列反馈调度算法多队列反馈调度算法 5. 常见的实时调度算法常见的实时调度算法 (1) 最早截止时间优先算

49、法最早截止时间优先算法(Earliest Deadline First) (2) 最低松弛度优先算法最低松弛度优先算法(Least Laxity First) 6. 调度的实现过程调度的实现过程 保存现进程现场、更新它的保存现进程现场、更新它的PCB、把它移至合适队列、把它移至合适队列 选择要执行的进程、更新它的选择要执行的进程、更新它的PCB、恢复新进程现场、恢复新进程现场 处理机调度最新 7. 死锁死锁(Deadlock)的定义：的定义： 进程组中各进程都无限等待被该组另一进程所占的资源进程组中各进程都无限等待被该组另一进程所占的资源 注意：注意：参与死锁的进程最少是两个、至少有两个参与死

50、锁的进程最少是两个、至少有两个 已占有资源、该组所有进程都在等待资源已占有资源、该组所有进程都在等待资源 8.产生死锁的四个必要条件产生死锁的四个必要条件 (1) 互斥条件互斥条件(资源独占资源独占): 一个资源只能给一个进程使用一个资源只能给一个进程使用 (2) 请求和保持条件请求和保持条件: 部分分配部分分配, 保持原资源申请新资源保持原资源申请新资源 (3) 不可剥夺条件不可剥夺条件: (不可强占不可强占, 只能由占有者自愿释放只能由占有者自愿释放) (4) 循环等待条件循环等待条件: 形成等待环形成等待环 9. 死锁的预防死锁的预防(强限制强限制) 破坏产生死锁的四个必要条件之一破坏产生死锁的四个必要条件之一(后后3条条) 10. 避免死锁的银行家算法避免死锁的银行家算法(宽限制宽限制) 检查每次分配后是否仍存在安全分配序列检查每次分配后是否仍存在安全分配序列 避免了死锁且资源利用率高避免了死锁且资源利用率高 处理机调度最新 11. 死锁的检测死锁的检测 允许死锁发生允许死锁发生,OS应不断检测死锁是否发生应不断检测死锁是否发生 12. 资源分配图资源分配图 结点集结点集: 各进程结点各进程结点P, 各资源类结点各资源类结点R 边集边集: 元素为有序