第3章处理机调度-ppt课件

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

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

3、上下文切换 一批作业从进入系统到作业运转终了能够阅历三级一批作业从进入系统到作业运转终了能够阅历三级调度调度高级、低级和中级调度。高级、低级和中级调度。一一. 高级调度高级调度(High Scheduling) 又称为作业调度接纳调度或长程调度又称为作业调度接纳调度或长程调度, 用于批处置用于批处置系统系统, 确定将外存后备队列中哪些作业调入内存确定将外存后备队列中哪些作业调入内存, 并为它并为它们创建进程。实时系统和分时系统的前台作业不需求作们创建进程。实时系统和分时系统的前台作业不需求作业调度。每次作业调度时业调度。每次作业调度时, 都必需做出两个决议都必需做出两个决议: 1) 接纳多少个

4、作业接纳多少个作业: 取决于多道程序度。取决于多道程序度。 2) 接纳哪些作业接纳哪些作业(用什么调度算法用什么调度算法): 先来先效力、短作业优先、优先权、呼应比优先。先来先效力、短作业优先、优先权、呼应比优先。3.1 处置机调度的根本概念处置机调度的根本概念 3.1.1 高级、低级和中级调高级、低级和中级调度度呼应呼应/运转运转二二. 低级调度低级调度(进程调度进程调度,短程调度短程调度) 进程调度的义务是控制协调进程对进程调度的义务是控制协调进程对CPU的竞争的竞争, 即即按照一定的调度算法从就绪队列中选中一个进程，把按照一定的调度算法从就绪队列中选中一个进程，把CPU的运用权交给被选中

5、的进程。它是最根本的一种的运用权交给被选中的进程。它是最根本的一种调度调度, 批处置系统批处置系统, 实时系统和分时系统都必需有进程实时系统和分时系统都必需有进程调度。它经过进程调度程序来完成。调度。它经过进程调度程序来完成。1. 进程调度程序的主要功能可描画如下：进程调度程序的主要功能可描画如下：(1) 记录系统中各进程的情况记录系统中各进程的情况 为了很好地实现进程调度为了很好地实现进程调度, 进程调度程序首先必需进程调度程序首先必需管理系统中各进程的管理系统中各进程的PCB，将进程的形状变化及资源，将进程的形状变化及资源需求情况及时地记录到需求情况及时地记录到PCB中。经过中。经过PCB

6、变化来准确变化来准确地掌握系统中一切进程的形状特征和执行情况。地掌握系统中一切进程的形状特征和执行情况。(2) 选择进程真正占有选择进程真正占有CPU 这是进程调度的本质这是进程调度的本质, 即按照系统规定的调度战略即按照系统规定的调度战略从就绪队列中选择一个进程占有从就绪队列中选择一个进程占有CPU执行。进程调度执行。进程调度根据的算法与系统的设计目的相一致。对于不同的系根据的算法与系统的设计目的相一致。对于不同的系统统, 通常采用不同的调度战略。对于批处置系统常采用通常采用不同的调度战略。对于批处置系统常采用短进程的进程优先短进程的进程优先, 以减少各进程的周转时间。对于分以减少各进程的周

7、转时间。对于分时系统时系统, 更多地采用时间片轮转。更多地采用时间片轮转。(3) 进展进程上下文的切换进展进程上下文的切换 当进程调度选中一个进程占有当进程调度选中一个进程占有CPU时时, 进程调度程进程调度程序要做的主要任务那么是进展进程上下文切换序要做的主要任务那么是进展进程上下文切换: 将正将正在执行进程的运转现场保管在该进程的在执行进程的运转现场保管在该进程的PCB中中, 以便以以便以后该进程恢复执行。将刚选中进程的运转现场恢复起后该进程恢复执行。将刚选中进程的运转现场恢复起来来, 并将并将CPU的控制权交给被选中进程的控制权交给被选中进程, 使其执行。使其执行。2. 进程调度方式进程

8、调度方式 (1)非抢占方式非抢占方式(Non preemptive mode) 在非抢占方式下在非抢占方式下, 调度程序一旦把调度程序一旦把 CPU分分配给某一进程后便让它不断运转下去配给某一进程后便让它不断运转下去, 直到进直到进程完成或发生某事件而不能运转时，才将程完成或发生某事件而不能运转时，才将CPU分给其它进程。分给其它进程。 这种调度方式通常用在批处置系统中。它这种调度方式通常用在批处置系统中。它的主要优点是简单、系统开销小。的主要优点是简单、系统开销小。 (2)抢占方式抢占方式(Preemptive mode) 当一个进程正在执行时，系统可以基于某当一个进程正在执行时，系统可以基

9、于某种战略剥夺种战略剥夺CPU给其它进程。剥夺的原那么有：给其它进程。剥夺的原那么有： 优先权原那么、短进程优先原那么、时间优先权原那么、短进程优先原那么、时间片原那么。片原那么。 显然这种调度方式多用在分时系统和实时显然这种调度方式多用在分时系统和实时系统中，以便及时呼应各进程的恳求。系统中，以便及时呼应各进程的恳求。3. 进程调度的时机进程调度的时机 所谓进程调度的时机，是指什么情况下引所谓进程调度的时机，是指什么情况下引起进程调度程序任务。进程调度的时机是与进起进程调度程序任务。进程调度的时机是与进程调度的方式有关的。进程调度的时机如下：程调度的方式有关的。进程调度的时机如下：正在执行的

10、进程正确完成正在执行的进程正确完成, 或由于某种错误而终或由于某种错误而终止运转止运转(圈套或中断圈套或中断) ；执行中的进程提出执行中的进程提出I/O恳求恳求, 等待等待I/O完成时完成时;在分时系统中在分时系统中, 按照时间片轮转按照时间片轮转, 分给进程的时分给进程的时间片用完时；间片用完时；按照优先级调度时按照优先级调度时, 有更高优先级进程变为就绪有更高优先级进程变为就绪时时(抢占方式抢占方式)；在进程通讯中在进程通讯中, 执行中的进程执行了某种原语操执行中的进程执行了某种原语操作作, 如如wait操作、阻塞原语和唤醒原语时操作、阻塞原语和唤醒原语时, 都能都能够引起进程调度。够引起

11、进程调度。三三. 中级调度中级调度(中程调度中程调度) 中级调度使暂时停顿的进程不再占用珍贵中级调度使暂时停顿的进程不再占用珍贵的内存资源的内存资源, 将它们调到外存上去成为挂起形将它们调到外存上去成为挂起形状。当处于挂起就绪的进程重新具备运转条件状。当处于挂起就绪的进程重新具备运转条件且内存稍有空闲时且内存稍有空闲时, 中级调度将它重新调入内中级调度将它重新调入内存存, 挂在活动就绪队列上等待进程调度。中级挂在活动就绪队列上等待进程调度。中级调度本质上就是存储管理中的对换功能。调度本质上就是存储管理中的对换功能。 进程调度频率最高进程调度频率最高(10100ms/次次)调度算法调度算法简单快

12、速简单快速; 作业调度频率最低约几分钟一次作业调度频率最低约几分钟一次,调调度算法允许破费较多的时间度算法允许破费较多的时间; 中级调度介于两中级调度介于两者之间。者之间。3.1.2. 调度队列模型调度队列模型1. 仅有进程调度的调度队列模型仅有进程调度的调度队列模型 在分时系统中在分时系统中, 通常仅有进程调度通常仅有进程调度, 采用采用FIFO算法。算法。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完进程调度进程调度等待事件等待事件事件事件出现出现交互用户交互用户完成完成2. 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 在批处置系统中在批处置系统中

13、,不仅需求进程调度而且需求不仅需求进程调度而且需求作业调度。作业调度。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完进程进程调度调度事件事件1出现出现 后备后备队列队列完成完成阻阻 塞塞 队队 列列事件事件2出现出现 阻阻 塞塞 队队 列列事件事件n出现出现 .等待事件等待事件1等待事件等待事件2等待事件等待事件n作业作业调度调度3. 具有三级调度的调度队列模型具有三级调度的调度队列模型 在具有三级调度系统中在具有三级调度系统中, 添加了在外存的挂起形状添加了在外存的挂起形状CPUCPU就就 绪绪 队队 列列就就 绪绪 挂挂 起起 时间片完时间片完进程进程调度调度事事件件出

14、出现现后备后备队列队列完成完成阻阻 塞塞 挂挂 起起阻阻 塞塞 队队 列列 挂起挂起等待事件等待事件作业作业调度调度事件出现事件出现中级中级调度调度交互作业交互作业调出调出 对于不同的系统对于不同的系统, 有不同的设计目的有不同的设计目的, 采用不同采用不同的调度算法。调度算法本质上是个战略问题的调度算法。调度算法本质上是个战略问题面向用户的准那么：面向用户的准那么： 周转时间短周转时间短 交互式系统的呼应时间快交互式系统的呼应时间快 截止时间保证截止时间保证 优先权准那么优先权准那么(公平合理公平合理)面向系统的准那么：面向系统的准那么： 单位时间内运转尽能够多的进程单位时间内运转尽能够多的

15、进程, 吞吐量高吞吐量高 使处置机尽能够坚持使处置机尽能够坚持“忙碌利用率高忙碌利用率高 使内外存、使内外存、I/O设备得以平衡、充分利用设备得以平衡、充分利用3.1.3. 调度算法的评价准那么调度算法的评价准那么进程进程(作业作业)平均周转时间周转时间、吞吐量平均周转时间周转时间、吞吐量 设某进程创建时间为设某进程创建时间为Si, 终了的时间为终了的时间为Ei 它的周转时间它的周转时间(全过程所用时间全过程所用时间)为为 Ti =Ei Si 系统为它提供的实践效力时间为系统为它提供的实践效力时间为Tsi 那么进程平均周转时间那么进程平均周转时间T,带权平均周转时间带权平均周转时间W为：为：

16、T W= 其中，其中，n为被测定进程流中的进程数为被测定进程流中的进程数 ni=1Tin1 ni=1Tin1Tsi 要设计一个理想的调度算法是一件非常困难的要设计一个理想的调度算法是一件非常困难的事事,在实践系统中在实践系统中, 调度算法往往折衷思索。调度算法往往折衷思索。 大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法3.2 调度算法调度算法1.先进先出调度算法先进先出调度算法(FIFO) (先来先效力先来先效力FCFS) 作业调度按照进入后备队列的先后次序调度作业调度按照进入后备队列的先后次序调度, 进程进程调度按照进入进程就绪队列的先后次序来调度调度按照进入

17、进程就绪队列的先后次序来调度 优点优点:实现简单实现简单 缺陷缺陷:不利于短作业不利于短作业(进程进程),紧迫性作业紧迫性作业(进程进程)得不到及得不到及时处置时处置2.短作业短作业(进程进程)优先调度算法优先调度算法(SJF,SPF) 选择就绪队列中估计运转时间最短的进程投入运转选择就绪队列中估计运转时间最短的进程投入运转 优点优点: 平均周转时间平均周转时间,带权平均周转时间都改善带权平均周转时间都改善 缺陷缺陷: 对长作业对长作业(进程进程)非常不利非常不利 不能保证紧迫性作业不能保证紧迫性作业(进程进程)得到及时处置得到及时处置 估计运转时间不准确估计运转时间不准确3. 优先权调度算法

18、优先权调度算法(HPFHighest Priority First)优先选择就绪队列中优先权最高的进程投入运优先选择就绪队列中优先权最高的进程投入运转转非抢占式优先权算法非抢占式优先权算法:仅在事件发生放弃处置机仅在事件发生放弃处置机时时抢占式优先权算法抢占式优先权算法: 可将正在运转的运转权剥夺可将正在运转的运转权剥夺 优先权的类型优先权的类型静态优先权静态优先权: 在进程创建时指定优先权在进程创建时指定优先权, 在进程在进程运转时优先数不变运转时优先数不变动态优先权动态优先权: 在进程创建时创建一个优先权，在进程创建时创建一个优先权，但在其生命周期内优先数可以动态变化。如等但在其生命周期内

19、优先数可以动态变化。如等待时间长优先数可改动待时间长优先数可改动 确定优先权的根据确定优先权的根据进程类型、对资源的需求、根据用户要求进程类型、对资源的需求、根据用户要求4. 高呼应比优先调度算法：高呼应比优先调度算法： 改良短作业改良短作业(进程进程)优先调度算法优先调度算法,优先权用优先权用下式动态计算出来下式动态计算出来 优先权优先权= =上式可看出上式可看出 等待时间一样要求效力的时间越短优先权越等待时间一样要求效力的时间越短优先权越高高, 有利于短作业有利于短作业 要求效力时间一样要求效力时间一样,等待时间越长优先权越高等待时间越长优先权越高,近似于先来先效力近似于先来先效力 长作业

20、的优先权会随等待时间加长而升高长作业的优先权会随等待时间加长而升高,长长作业也会得到执行作业也会得到执行等待时间等待时间+要求效力时间要求效力时间 呼应时间呼应时间 要求效力时间要求效力时间 要求效力时间要求效力时间 把把CPU划分成假设干时间片划分成假设干时间片,并且按顺序赋给就并且按顺序赋给就绪队列中的每一个进程，进程轮番占有绪队列中的每一个进程，进程轮番占有CPU，当时，当时间片用完时，即使进程未执行终了，系统也剥夺该间片用完时，即使进程未执行终了，系统也剥夺该进程的进程的CPU，将该进程排在就绪队列末尾。同时系，将该进程排在就绪队列末尾。同时系统选择另一个进程运转统选择另一个进程运转

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

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

23、CPU, 进入下一级就绪进入下一级就绪队列队列 实时系统中实时系统中, 对实时进程的调度有截止时间的要求对实时进程的调度有截止时间的要求1.实现实时调度的根本条件实现实时调度的根本条件 1) 提供必要的信息提供必要的信息 就绪时间、开场截止时间或完成截止时间、处置时就绪时间、开场截止时间或完成截止时间、处置时间、资源要求、优先级间、资源要求、优先级( 硬实时义务赋绝对优先级硬实时义务赋绝对优先级)。 2) 系统处置速度快系统处置速度快 假设系统中有假设系统中有m 个周期性硬实时义务个周期性硬实时义务, 处置时间为处置时间为Ci周期时间为周期时间为Pi , 那么处置机处置速度应到达可调度条那么处

24、置机处置速度应到达可调度条件件: 1 (单处置机单处置机) n (多处置机多处置机) 3) 采用抢占式调度机制以满足对截止时间的要求采用抢占式调度机制以满足对截止时间的要求 4) 具有快速切换机制具有快速切换机制: 快速中断呼应、快速义务分派快速中断呼应、快速义务分派3.3 实时调度实时调度CiPii=1nCiPii=1n2. 实时调度算法的分类实时调度算法的分类 1) 非抢占式调度算法非抢占式调度算法 非抢占式轮转调度算法非抢占式轮转调度算法(呼应时间数秒到数十秒呼应时间数秒到数十秒) 轮转一圈后调度轮转一圈后调度 非抢占式优先权调度算法非抢占式优先权调度算法(呼应时间数百毫秒呼应时间数百毫

25、秒) 当前进程完成当前进程完成(或被阻塞或被阻塞)后调度后调度 2) 抢占式调度算法抢占式调度算法 严厉要求的实时系统严厉要求的实时系统, 呼应时间在数十毫秒以内呼应时间在数十毫秒以内 基于时钟中断的抢占式调度算法基于时钟中断的抢占式调度算法 时钟中断到来时调度时钟中断到来时调度 立刻抢占的优先权调度算法立刻抢占的优先权调度算法 立刻剥夺当前进程立刻剥夺当前进程 调度时间见调度时间见P 83 图图3-63.几种常见的实时调度算法几种常见的实时调度算法 1) 最早截止时间优先算法最早截止时间优先算法(Earliest Deadline First) 根据义务的开场截止时间确定优先级。根据义务的开

26、场截止时间确定优先级。 2) 最低松弛度优先算法最低松弛度优先算法(Least Laxity First) 根据义务的松弛度根据义务的松弛度(紧急程度紧急程度)确定优先级确定优先级 根据义务完成截止时间和本身运转时间确定松弛度根据义务完成截止时间和本身运转时间确定松弛度 松弛度松弛度= 必需完成时间必需完成时间-本身运转时间本身运转时间-当前时间当前时间 P 85 图图 3-9 保管现场保管现场:顺序保管进程的上下文顺序保管进程的上下文, 包括程序计包括程序计数器和其它存放器数器和其它存放器 用新形状和相关信息更新正在运转进程的用新形状和相关信息更新正在运转进程的PCB 把该进程移至适宜的队列

27、把该进程移至适宜的队列-就绪、阻塞就绪、阻塞 选择另一个要执行的进程选择另一个要执行的进程,更新该进程的更新该进程的PCB 从被选中进程中重装入从被选中进程中重装入 CPU 上下文上下文,恢复现场恢复现场 假设无就绪进程假设无就绪进程,系统会安排一个闲逛进程系统会安排一个闲逛进程(idle), 不断运转不断运转, 在执行过程中可接纳中断。在执行过程中可接纳中断。3.4 CPU调度的实现调度的实现操作系统的中心操作系统的中心 向上提供无中断的虚拟机器向上提供无中断的虚拟机器, 在中心内不允许中断在中心内不允许中断特点特点: 中心常驻内存中心常驻内存, 短小精焊短小精焊, 为进程运转提供舞台为进程

28、运转提供舞台 中心的组成中心的组成中断处置中断处置: 时钟、时钟、I/O、虚拟存储器、虚拟存储器进程管理进程管理: 调度调度 控制控制 通讯通讯 互斥互斥 同步等同步等原语管理原语管理: 提供一系列原语提供一系列原语, 同步同步, 通讯通讯, 创建创建, 吊销等吊销等队列管理队列管理:中断之后调度之前中断之后调度之前(运转运转-就绪就绪-等待队列等待队列)现场管理现场管理: 保管现场、恢复现场保管现场、恢复现场时钟管理时钟管理: 绝对时钟、间隔时钟、虚时钟绝对时钟、间隔时钟、虚时钟 保管现场、分析中断源保管现场、分析中断源 处置中断处置中断原语管理、队列管理、时钟管理、进程调度原语管理、队列管

29、理、时钟管理、进程调度 恢复现场恢复现场中断中断中心入口中心入口中心处置流程中心处置流程 独一入口独一入口: :中断中断, ,由硬件完成由硬件完成 作业作业: P101 2, 3, 53.5死锁死锁死锁的根本概念死锁的根本概念死锁的处理方案死锁的处理方案 预防，防止，检测及解除预防，防止，检测及解除资源分配图资源分配图3.5.1 死锁的根本概念死锁的根本概念死锁死锁(Deadlock)的定义：的定义： 一组进程中，每个进程都无限等待被该组一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因此永远无法进程中另一进程所占有的资源，因此永远无法得到的资源，这种景象称为进程死锁，这一组得

30、到的资源，这种景象称为进程死锁，这一组进程就称为死锁进程进程就称为死锁进程阐明阐明: 参与死锁的进程最少是两个参与死锁的进程最少是两个参与死锁的进程至少有两个曾经占有资源参与死锁的进程至少有两个曾经占有资源参与死锁的一切进程都在等待资源参与死锁的一切进程都在等待资源留意：假设死锁发生，会浪费大量系统资源，留意：假设死锁发生，会浪费大量系统资源，甚至导致系统解体。甚至导致系统解体。死锁产生的缘由死锁产生的缘由1.竞争资源引起竞争资源引起永久性资源永久性资源:可被多个进程多次运用可被多个进程多次运用(可再用资可再用资源源) 剥夺性资源剥夺性资源(CPU、内存、内存 非剥夺性资源非剥夺性资源(磁带机

31、、打印机磁带机、打印机) 竞争非剥夺性资源会引起死锁竞争非剥夺性资源会引起死锁暂时性资源暂时性资源:只可运用一次的资源；只可运用一次的资源； 如信号量如信号量,中断信号中断信号,同步信号等同步信号等(可耗费性可耗费性资源资源) 竞争暂时性资源也会引起死锁竞争暂时性资源也会引起死锁2. 进程推进顺序不当引起进程推进顺序不当引起 对资源采用对资源采用“恳求恳求-分配分配-运用运用-释放方释放方式式, 由于推进顺序不当两进程都要恳求对方已由于推进顺序不当两进程都要恳求对方已占有的资源占有的资源P1： 恳求打印机恳求打印机恳求扫描仪恳求扫描仪运用运用释放打印机释放打印机释放扫描仪释放扫描仪P2： 恳求

32、扫描仪恳求扫描仪恳求打印机恳求打印机运用运用释放打印机释放打印机释放扫描仪释放扫描仪死锁的例子死锁的例子:竞争非剥夺性资源进程推进顺序不当引起死锁竞争非剥夺性资源进程推进顺序不当引起死锁Req(R1) Req(R2) Rel(R1) Rel(R2)Rel(R1)Rel(R2)Req(R1)Req(R2)P2P1不平安区不平安区竞争非剥夺性资源竞争非剥夺性资源推进顺序不当推进顺序不当进入不平安区进入不平安区3.5.2产生死锁的四个必要条件产生死锁的四个必要条件1) 互斥条件资源独占：互斥条件资源独占： 一个资源每次只能给一个进程运用一个资源每次只能给一个进程运用2) 恳求和坚持条件恳求和坚持条件

33、: (部分分配部分分配,占有恳求占有恳求) 在恳求新资源的同时坚持对原有资源的占有在恳求新资源的同时坚持对原有资源的占有3) 不可剥夺条件不可侵占：不可剥夺条件不可侵占： 资源恳求者不能强行的从资源占有者手中夺资源恳求者不能强行的从资源占有者手中夺取资源取资源, 资源只能由占有者自愿释放资源只能由占有者自愿释放4) 循环等待条件：循环等待条件： 存在进程存在进程-等待资源环形链等待资源环形链 P1 , P2 , , Pn, 其中其中P1等待等待P2占有的资源占有的资源, P2等待等待P3占有的资源占有的资源, , Pn等待等待P1占有的资源。占有的资源。3.6 死锁的预防死锁的预防 3.6.1

34、 强限制预防强限制预防 确定资源分配算法确定资源分配算法,保证不发生死锁。做法保证不发生死锁。做法是破坏产生死锁的四个必要条件之一。是破坏产生死锁的四个必要条件之一。1. 破坏破坏“恳求和坚持恳求和坚持(部分分配部分分配)条件条件 每个进程运转前必需一次性恳求运转期所需每个进程运转前必需一次性恳求运转期所需全部资源全部资源, 假设所需资源均可满足那么全部分配。假设所需资源均可满足那么全部分配。该进程运转中不再恳求资源该进程运转中不再恳求资源, 屏弃恳求条件。屏弃恳求条件。 简单、平安简单、平安; 但资源利用率低但资源利用率低,要长期等待。要长期等待。2. 破坏破坏“不可剥夺条件不可剥夺条件 在

35、允许进程动态恳求资源前提下在允许进程动态恳求资源前提下, 规定规定: 某某进程在恳求新的资源不能立刻满足而被阻塞之进程在恳求新的资源不能立刻满足而被阻塞之前前, 必需释放已占有的资源必需释放已占有的资源(能够呵斥前一段任能够呵斥前一段任务失效务失效), 假设需求再重新恳求假设需求再重新恳求(添加开销添加开销)。3.破坏破坏“循环等待条件循环等待条件 采用资源有序分配法采用资源有序分配法:允许进程动态恳求资允许进程动态恳求资源源, 对系统中一切资源编号对系统中一切资源编号, 进程恳求资源时应进程恳求资源时应严厉按资源编号递增次序进展严厉按资源编号递增次序进展,否那么不予分配。否那么不予分配。P1

36、：恳求恳求1恳求恳求3恳求恳求4P2：恳求恳求2恳求恳求4恳求恳求8Pn：恳求恳求1恳求恳求2恳求恳求8缺陷缺陷: 资源利用仍不充分资源利用仍不充分3.6.2 防止死锁的银行家算法防止死锁的银行家算法 前面的三种方法由于限制太强前面的三种方法由于限制太强, 资源利用率资源利用率都不太高。能否放宽限制条件？都不太高。能否放宽限制条件？ E.W.Dijkstra于于1968年提出银行家算法年提出银行家算法, 此此算法要事先知道每个进程对资源的最大需求量算法要事先知道每个进程对资源的最大需求量; 算法的根本思绪算法的根本思绪:允许进程动态恳求资源允许进程动态恳求资源,但在每但在每次分配资源前先对本次

37、分配的平安性进展检查次分配资源前先对本次分配的平安性进展检查, 以判别这种分配能否能够导致死锁以判别这种分配能否能够导致死锁, 假设分配能假设分配能够导致系统死锁够导致系统死锁, 那么不予分配那么不予分配, 否那么分配该否那么分配该资源。资源。(检查每次分配后能否仍存在平安分配序检查每次分配后能否仍存在平安分配序列列) 显然显然, 此法防止了死锁且资源利用率高。此法防止了死锁且资源利用率高。1. 平安序列：平安序列： 假设进程序列假设进程序列P1，Pn对每个对每个Pi(1in)进程进程, 它以后尚需求的资源量不超越系统当前剩余资源量与它以后尚需求的资源量不超越系统当前剩余资源量与一切一切Pj

38、(j Available(2,3,0),让让P4等待等待4) 假设假设P0恳求资源恳求资源,发出恳求向量发出恳求向量Request(0,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

39、 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检查此刻的平安性检查此刻的平安性 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)假定分

40、配假定分配, 资源变为资源变为: 进进 Work Allocation Need W+ A Finish 程程 A B C A B C A B C A B C P1 2 2 0 3 0 2 0 2 0 5 2 2 trueP3 5 2 2 2 1 1 0 1 1 7 3 3 trueP4 7 3 3 0 0 2 4 3 1 7 3 5 trueP0 7 3 5 0 2 0 7 3 3 7 5 5 trueP2 7 5 5 3 0 2 6 0 0 10 5 7 true3.7 死锁的检测与解除死锁的检测与解除 允许死锁发生，系统必需提供检测和解除死锁允许死锁发生，系统必需提供检测和解除死锁的手段

41、的手段, 操作系统应不断监视系统进展情况，判别死操作系统应不断监视系统进展情况，判别死锁能否发生。锁能否发生。3.7.1死锁的检测1. 资源分配图资源分配图用有向图描画进程的死锁用有向图描画进程的死锁: 准确、笼统准确、笼统 系统由假设干类资源构成，一类资源称为一个系统由假设干类资源构成，一类资源称为一个资源类；每个资源类中包含假设干个同种资源，资源类；每个资源类中包含假设干个同种资源，称为资源实例。称为资源实例。二元组二元组G=V，E V：结点集，分为：结点集，分为P，R两部分两部分 P=p1,p2,pn R=r1,r2,rm E：边的集合：边的集合, 其元素为有序二元组其元素为有序二元组

42、分配边分配边(rj,pi): 资源实例资源实例进程的一条有向边进程的一条有向边恳求边恳求边(pi,rj): 进程进程资源类的一条有向边资源类的一条有向边有环有死锁有环无死锁2. 死锁定理死锁定理 假设资源分配图中没有环路假设资源分配图中没有环路, 那么系统中那么系统中没有死锁没有死锁, 假设图中存在环路那么系统中能够假设图中存在环路那么系统中能够存在死锁。存在死锁。 假设每个资源类中只包含一个资源实例假设每个资源类中只包含一个资源实例, 那么资源分配图环路是死锁存在的充分必要那么资源分配图环路是死锁存在的充分必要条件。条件。资源分配图化简方法：资源分配图化简方法：1找一个非孤立点进程结点且只需

43、分配边，找一个非孤立点进程结点且只需分配边，去掉分配边，将其变为孤立结点。去掉分配边，将其变为孤立结点。2再把相应的资源分配给一个等待该资源的再把相应的资源分配给一个等待该资源的进程，即将某进程的恳求边变为分配边。进程，即将某进程的恳求边变为分配边。3反复反复(1) (2)操作直到无法再化简操作直到无法再化简, 假设一切假设一切结点都为孤立结点那么无死锁结点都为孤立结点那么无死锁, 否那么死锁发否那么死锁发生生3.7.2死锁的解除死锁的解除 一旦死锁发生那么采取专门的措施，解一旦死锁发生那么采取专门的措施，解除死锁并以最小的代价恢复操作系统运转。除死锁并以最小的代价恢复操作系统运转。死锁的解除

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

45、重新调入内存 2. 进程调度方式进程调度方式 (1)非抢占方式非抢占方式(Non preemptive mode) (2)抢占方式抢占方式(Preemptive mode)3. 进程调度的时机进程调度的时机 (1) 执行进程正确完成执行进程正确完成 或错误终止或错误终止 (2) 执行进程提出执行进程提出I/O恳求恳求, 等待等待I/O完成时完成时; (3) 分时系统时间片轮转分时系统时间片轮转, 分给进程的时间片用完时分给进程的时间片用完时 (4) 优先级调度优先级调度, 抢占方式中有更高优先级进程就绪抢占方式中有更高优先级进程就绪 (5) 执行进程执行执行进程执行wait、阻塞原语和唤醒原语

46、等操作、阻塞原语和唤醒原语等操作4. 调度算法调度算法(1)先进先出调度算法先进先出调度算法(FIFO) (先来先效力先来先效力FCFS)(2)短作业短作业(进程进程)优先调度算法优先调度算法(SJF,SPF)(3)优先权调度算法优先权调度算法(HPFHighest Priority First)(4)高呼应比优先调度算法高呼应比优先调度算法(5)时间片轮转调度算法时间片轮转调度算法(6)多队列反响调度算法多队列反响调度算法5. 常见的实时调度算法常见的实时调度算法(1) 最早截止时间优先算法最早截止时间优先算法(Earliest Deadline First)(2) 最低松弛度优先算法最低松

47、弛度优先算法(Least Laxity First)6. 调度的实现过程调度的实现过程 保管现进程现场、更新它的保管现进程现场、更新它的PCB、把它移至适宜队列、把它移至适宜队列 选择要执行的进程、更新它的选择要执行的进程、更新它的PCB、恢复新进程现场、恢复新进程现场7. 死锁死锁(Deadlock)的定义：的定义：进程组中各进程都无限等待被该组另一进程所占的资源进程组中各进程都无限等待被该组另一进程所占的资源留意：参与死锁的进程最少是两个、至少有两个留意：参与死锁的进程最少是两个、至少有两个 已占有资源、该组一切进程都在等待资源已占有资源、该组一切进程都在等待资源8.产生死锁的四个必要条件

48、产生死锁的四个必要条件 (1) 互斥条件互斥条件(资源独占资源独占): 一个资源只能给一个进程运用一个资源只能给一个进程运用 (2) 恳求和坚持条件恳求和坚持条件: 部分分配部分分配, 坚持原资源恳求新资源坚持原资源恳求新资源 (3) 不可剥夺条件不可剥夺条件: (不可侵占不可侵占, 只能由占有者自愿释放只能由占有者自愿释放) (4) 循环等待条件循环等待条件: 构成等待环构成等待环9. 死锁的预防死锁的预防(强限制强限制) 破坏产生死锁的四个必要条件之一破坏产生死锁的四个必要条件之一(后后3条条)10. 防止死锁的银行家算法防止死锁的银行家算法(宽限制宽限制) 检查每次分配后能否仍存在平安分配序列检查每次分配后能否仍存在平安分配序列 防止了死锁且资源利用率高防止了死锁且资源利用率高11. 死锁的检测死锁的检测 允许死锁发生允许死锁发生,OS应不断检测死锁能否发生应不断检测死锁能否发生12. 资源分配