《OS调度与死锁》PPT课件.ppt

1 第 3 章 调度与死锁 操作系统原理与 Windows 2003实践教程 2 第三章 调度与死锁 3.1 处理机调度 3.2 调度算法 3.3 死锁 3.4 死锁的预防 3.5 死锁的避免和银行家算法 3.6 死锁的检测与解除 3.7 Windows2003处理器 3.8 本章小结 3 3.1 处理器调度 3.1.1 调度的层次 3.1.2 进程调度 3.1.3 调度队列模型 4 调度的层次 高级调度：也称作业调度 中级调度：即交换调度 低级调度：也称进程调度 5 processer processer RAM memory 高级调度 中级调度 低 级 调 度 6 高级调度也称为作业调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天 中级调度涉及进程在内外存间的交换，从存储器资 源管理的角度来看，把进程的部分或全部换出到外 存上，可为当前运行进程的执行提供所需内存空间， 将当前进程所需部分换入到内存。指令和数据必须 在内存里才能被处理机直接访问 低级调度也称微观调度，从处理机资源分配的角度 来看，处理机需要经常选择就绪进程或线程进入运 行状态，低级调度的时间尺度通常是毫秒级的。由 于低级调度算法的频繁使用，要求在实现时做到高 效 7 处理机的三级调度 8 作业调度与进程调度 9 处理机调度与进程状态转换 10 进程调度 进程调度的功能 记录系统中所有进程的状态、优先数和资源需求 确定调度算法 分配处理器给进程 11 进程调度的时机： 正在执行的进程执行完毕 执行进程调用阻塞原语将自己阻塞起来变为阻塞状态 执行进程调用 P操作，因资源不足而被阻塞；或调用 V操作激活了等待资源的进程队列。 执行进程提出 I/O请求，被阻塞 分时系统中时间片用完 执行系统调用完毕，由系统程序返回用户进程时，可 认为系统进程执行完毕，从而可调度选择一新的用户 进程执行。 12 调度队列模型 具有一级调度的调度队列模型 13 两级调度简化队列图 14 具有高、低两级调度的调度队列模型 15 具有三级调度的调度队列模型 16 3.2 调度算法 3.2.1 算法的衡量 3.2.2 先来先服务调度算法 3.2.3 短者优先调度算法 3.2.4 最短剩余时间优先调度算法 3.2.5 最高响应比优先调度算法 3.2.6 时间片轮转法 3.2.7 优先级调度算法 3.2.8 多级反馈队列调度算法 17 确定调度策略时应考虑的主要因素： 所用算法应保证实现系统的设计目标 公平性原则 均衡使用资源 兼顾响应时间和资源利用率 基于相对优先级，但避免无限延期 系统开销不应大大 18 算法的衡量 常用的评价准则包括： CPU利用率 吞吐量 周转时间 就绪等待时间 响应时间 19 CPU利用率： CPU利用率 CPU有效工作时间 CPU总运行时间 CPU总运行时间 CPU有效工作时间 CPU空闲时间 20 吞吐量： 单位时间内 CPU完成作业的数量 21 周转时间： Ti t ci t si 其中， t si表示作业 i的提交时间，即作业 i到达系统的 时间； t ci表示作业 i的完成时刻 平均周转时间： 22 就绪等待时间 ： 作业在就绪队列中的等待时间 23 响应时间： 从提交第一个请求到产生第一个响应所用的时间 24 先来先服务调度算法 实现思想： “排队买票”，即按照作业到达系统或是进程进入就 绪队列的先后次序作为选择 依据 就绪队列（后备队列）按照进入的先后次序为序， 选择时选取队列的队首进程（作业） 25 【 例 3-1】 假设一个系统有 5个进程 P1、 P2、 P3、 P4、 P5， 已知它们的到达时间和运行时间，用 FCFS算法进行调 度。 26 27 周转时 间 /服 务时间 28 FCFS的优点： 简单、容易实现 有利于长进程（作业），不利于短进程（作业） 有利于 CPU型作业，不利于 I/O型作业 FCFS的缺点： 属于不可抢占策略，表面上对于所有的作业和进程 都是公平的 ，但系统吞吐量不大，效率较低 29 短者优先调度算法 实现思想： 从就绪队列中挑选所需的运行时间（估计时间）最短 的进程（作业）运行 就绪队列（后备队列）按照进程（作业）的运 行为序，选择时选取队列的队首进程（作业） 即为最短者，新来的进程（作业）依据运行时 间的长短插入到队列的合适位置。 30 【 例 3-2】 设系统中有 5个进程中 A， B， C， D， E，它们 到来的时间依次为 0， 1， 2， 3， 4，运行时间依次为 4， 3， 5， 2， 4，试用 FCFC算法和短者优先调度算法调度。 FCFS：进程的执行顺序依次为 ABCDE SJF：进程的执行顺序依次为 ADBEC 。 31 32 SJF（ SPF）的优点： 简单、容易实现 有利于短进程（作业），不利于长进程（作业） 有利于保障系统吞吐量 SJF（ SPF）的缺点： 对于长进程（作业）是不公平的 33 最短剩余时间优先调度算法 实现思想： 让运行到进程完成时所需运行时间最短的进程优先得 到处理，其中包括新进入系统的进程 。 就绪队列（后备队列）按照进程（作业）的剩余运行 时间的长短为序，选择时选取队列的队首进程（作业） 即为最短者，新入队的进程（作业）依据剩余运行时 间的长短插入到队列的合适位置。 34 优点： 可以用于分时系统，保证及时响应用户要求 属于可抢占策略，使短进程一进入系统就能立即得 到服务，从而降低作业的平均等待时间 缺点： 系统开销增加 需要保存进程的运行情况记录，以比较其剩余时间大小 抢占本身消耗处理器时间 35 最高响应比优先调度算法 实现思想： 综合 FCFS和短者优先算法的特点 就绪队列（后备队列）按照进程（作业）到来 的先后次序为序，选择时计算队列全部进程的 响应比，选择最高响应比的进程（作业）运行。 36 【 例 3-3】 假设一个系统有 4个进程 P1、 P2、 P3、 P4，已 知它们的到达时间和运行时间，试用最高响应比优先 算法进行调度。 37 38 39 HRF的优点： 短进程（作业）由于计算响应比的分 母大而可以 得到大的响应比，优先执行，长进程（作业）的响 应比会随着等待时间的加长越来越大，得到执行机 会。 40 时间片轮转法 实现思想： 从就绪队列中的每个运行指定的时间片，时间片到， 无论是否运行完毕都执行下一个进程。 就绪队列（后备队列）按照进程（作业）到来 的先后为序，选择时选取队列的队首进程（作 业）运行一个时间片。 41 【 例 3-4】 设系统中有四个进程 P1， P2， P3， P4依次进 入系统，但彼此相差时间很小，可以近似看作“同时” 到达。四个进程分别需要运行 12， 5， 3和 6个时间单位， 时间片分别为 1和 4时系统运行的情形： 42 43 时间片的大小是关键 过大：时间片轮转法退化成先来先服务算法 过小：处理器在进程间的转接工作过于频繁，开销 变大，而处理器真正用于运行用户程序的时间将会 减少 44 优先级调度算法 实现思想： 按照进程（作业）的优先级大小来调度，使高优先级 进程（作业）得到优先处理 就绪队列（后备队列）按照进程（作业）的优 先级从高到低，选择时选取队列的队首进程 （作业）即为优先级最高的，新进程据其优先 级大小入就绪队列相应位置 45 进程调度策略： 非抢占优先级调度 抢占优先级调度 优先级的确定： 静态优先级 动态优先级 46 【 例 3-5】 假设一个系统有 5个进程 P1、 P2、 P3、 P4、 P5， 已知它们的到达时间、运行时间和优先数如表 3-7所示， 试用静态优先级调度算法进行调度。 47 48 49 多级反馈队列调度算法 50 3.3 死锁 3.3.1 死锁的定义 3.3.2 产生死锁的必要条件 3.3.3 对死锁采取的对策 51 交通死锁 52 死锁的定义 死锁，是指两个或两个以上的进程，因竞争系 统共享资源而产生的无止境地相互等待的状态， 此时计算机系统所处的状态即处于死锁状态。 陷入死锁状态的进程称之为死锁进程 53 例：现有两个进程 PA和 PB，各自按以下顺序使用 PV操 作并行运行，其中 S1和 S2分别代表系统中一台打印机 和一台扫描仪的信号量，初值均为 1 进程 PA： P(S1)； P(S2)； V(S1)； V(S2)； 进程 PB： P(S2)； P(S1)； V(S2)； V(S1)； 54 产生死锁的根本原因： 资源有限 进程推进的顺序不合理 55 产生死锁的必要条件 互斥条件：进程访问的临界资源是互斥的 不可抢占条件：一个资源仅能被占有它的进程 主动释放，不能被其他进程强行抢占。 占有且申请：进程在申请新资源的同时，保持 对已有资源的占有。 环路等待条件：存在一个进程资源的环形链 56 对死锁采取的对策 置之不理 驼鸟策略 运行前预防 死锁的预防。 运行中避免 死锁的避免。 运行中解除 死锁的检测与恢复。 57 3.4 死锁的预防 设法破坏产生死锁的四个必要条件之一，从而保证系 统不发生死锁 破坏互斥条件 破坏不可抢占条件 破坏占有且申请条件 破坏环路等待条件 此方法较容易实现 ， 但由于所施加的限制往往太严格 ， 可能导致系统资源利用率和系统吞吐量的降低 。 58 “资源一性分配策略”算法 规定任一进程必须预先申请所需要的全部资源，而 且当且仅当该进程的全部要求都能得到满足时，系 统才一次性分配，然后启动该进程运行 。 59 “资源有序分配策略”算法 把资源事先分类编号，按序分配，使进程在申请、 占用资源时不会形成环路。 60 3.5 死锁的避免和银行家算法 3.5.1 系统安全状态 3.5.2 银行家算法 3.5.3 银行家算法的例子 61 系统安全状态 安全状态 是指系统中的所有进程能按某种顺序 （ P1， P2， ， Pn）分配其所需的资源，直到的有进 程都可以运行完毕。 此进程序列（ P1， P2， ， Pn）称为安全序列 若存在这样一个安全序列，则系统是安全的；否则， 如果在系统中无法找到这样一个安全序列，则称系统 处于不安全状态。 62 死锁与不安全状态的关系 63 银行家算法 基本思想：当一个新的进程进入系统时，其所需要每 种资源的最大数目，不能超过系统中资源的总数。当 用户申请资源时，系统判断此资源分配是否使系统仍 处于安全状态，若是则分配，否则该进程等待，直到 其他进程释放足够的资源。 64 使用的数据结构：（系统中有 n个进程， m类资源） Available：长度为 m的向量 Availablej为系统中资源类 Rj的当前可用数（ j=1,2,m) Max： n m阶矩阵 Mi,j=K表示进程 Pi需要 Rj类资源最大数目为 K。 Allocation： n m阶矩阵 Allocationi,j=K，表示进程 Pi当前已分得 Rj类资源数为 K。 Need： n m阶矩阵 Needi,j=K，表示进程 Pi还需要 Rj类资源数目为 K 显然 Needi,j=Maxi,j-Allocationi,j。 65 银行家算法 设 Requesti是进程 Pi提出的资源申请向量 当进程 Pi提出资源申请 Requesti K时，按照银 行家算法，系统将执行下列步骤： 1）若 RequestiNeedi，转 2），否则错误返回。 2）若 RequestiAvailable，转 3），否则资源不足，进 程 Pi需要等待。 66 3）假设系统满足 Pi的请求为其分配资源，则： Available Available Requesti； Allocationi Allocationi Requesti； Needi Needi Request i； 4）执行安全性算法，若系统新状态是安全的，则分 配完成；如果系统处于不安全状态，那么进程 Pi等 待 Requesti，并且恢复到系统原来的状态。 67 安全性算法 1） Work=Available； Finishi=False， i=1,2,n 2）存在 Pi满足： Finishi=False, NeediWork, 执 行 3)；否则执行 4）。 3）修改： Work=Work+Allocationi； Finishi=True；转向 2）。 4）若所有： Finishi=True， i=1， 2， ， n，则 该系统处于安全状态。否则处于不安全状态。 68 银行家算法的优点： 采用死锁动态策略，系统资源利用率提高了 银行家算法的缺点： 要求被分配每类资源数量、客户数固定不变，这在 多道程序系统中是难以做到的。 算法保证客户请求在有限的时间内得到满足，但无 法满足实时客户的快速响应要求。 寻找安全序列，增加了系统的开销。 69 银行家算法的例子 【 例 3-6】 假设系统中有五个进程 P0， P1， P2， P3， P4和 三种类型的资源 A， B， C，每一种资源的数量 分别为 10、 5、 7,在 T0时刻系统的资源分配情况如表： 70 A， B， C =10， 5， 7 T0时刻的资源分配表 资源情况 进程 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 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 71 （ 1） T0时刻的安全性：利用安全性算法有： Work=Available（ 3， 3， 2）； Finishi=False， i=1， 2， 3， 4， 5。 1）有 Finish1=False， Need1Work，即（ 1， 2， 2） （ 3， 3， 2），所以 Work=Work+Allocation（ 3， 3， 2） +（ 2， 0， 0）（ 5， 3， 2）； Finish1=True。 2）有 Finish3=False， Need3Work，即（ 0， 1， 1） （ 5， 3， 2），所以 Work=Work+Allocation（ 5， 3， 2） +（ 2， 1， 1）（ 7， 4， 3）； Finish3=True。 3）有 Finish4=False， Need4Work，即（ 4， 3， 1） （ 7， 4， 3），所以 Work=Work+Allocation（ 7， 4， 3） +（ 0， 0， 2）（ 7， 4， 5）； Finish4=True。 4）有 Finish2=False， Need2Work，即（ 6， 0， 0） （ 7， 4， 5），所以 Work=Work+Allocation（ 7， 4， 5） +（ 3， 0， 2）（ 10， 4， 7）； Finish2=True。 5）有 Finish0=False， Need0Work，即（ 7， 4， 3） （ 10， 4， 7），所以 Work=Work+Allocation（ 10， 4， 7） +（ 0， 1， 0）（ 10， 5， 7）； Finish0=True。 所以，有安全序列 P1， P3， P4， P2， P0，使得对 i=1， 2， 3， 4， 5，均 有 Finishi=True，则 T0时刻该系统处于安全状态。 72 安全性算法的计算可简化为下表： T0时刻的安全序列 Work Need Allocation Work+Allocation Finish A B C A B C A B C A B C 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 73 （ 2） P1请求资源 Request1（ 1， 0， 2） 对于 P1的请求，按照银行家算法有： 1） Request1（ 1， 0， 2） Need1（ 1， 2， 2）。 2） Request1（ 1， 0， 2） Available（ 3， 3， 2）。 3）假设满足 P1的请求为其分配资源，则： Available Available Request1 （ 3， 3， 2）（ 1， 0， 2）（ 2， 3， 0）； Allocationi Allocationi Requesti （ 2， 0， 0） +（ 1， 0， 2）（ 3， 0， 2）； Needi Needi Request i （ 1， 2， 2）（ 1， 0， 2）（ 0， 2， 0）； 由此形成的系统资源分配情况表。 74 P1申请资源时的资源分配表 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 2 3 0 ( 3 3 2) P1 3 2 2 3 0 2 (2 0 0) 0 2 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 75 执行安全性算法，检测新状态是否安全 P1申请资源时的安全性检查 存在安全序列 P1， P3， P4， P0， P2，因此，系统在将资源 分配给 P1后是安全的，故可以立即将 P1所申请的资源分配给它。 Work Need Allocation Work+Allocation Finish A B C A B C A B C A B C 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 76 （ 3） P4请求资源 Request4（ 3， 3， 0） 对于 P4的请求，按照银行家算法有： 1） Request4（ 3， 3， 0） Need4（ 4， 3， 1）。 2） Request4（ 3， 3， 0） Available（ 2， 3， 0）， 故让 P4等待。 77 （ 4） P0请求资源 Request0（ 0， 2， 0），按照银行家算 法有： 1） Request0（ 0， 2， 0） Need0（ 7， 4， 3）。 2） Request0（ 0， 2， 0） Available（ 2， 3， 0）。 3）假设满足 P0的请求，则： Available Available Request0 （ 2， 3， 0）（ 0， 2， 0）（ 2， 1， 0）； Allocation0 Allocation0 Request0 （ 0， 1， 0） +（ 0， 2， 0）（ 0， 3， 0）； Need0 Need0 Request 0 （ 7， 4， 3）（ 0， 2， 0）（ 7， 2， 3）； 78 P0申请资源时的资源分配表 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 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 79 4）利用安全性算法，检测此时系统是否安全。从表中可 以看出： 可用资源 Available（ 2， 1， 0）已经不能满足任何进程 的需要，故系统进入不安全状态。 因此，系统不能满足进程 P0申请资源的请求，为其分配 资源。 80 【 练习 3-1】 1）该状态是否安全？ 2）如果进程 P2提出 Request2（ 1， 2， 2， 2）后，系统能否将资源 分配给它？为什么？ Allocation Need Available P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 81 3.6 死锁的检测与解除 3.6.1 死锁的检测 3.6.2 死锁检测的时机 3.6.3 死锁的恢复 82 死锁检测与恢复： 是指系统设有专门的机构，当死锁发生 时，该机构能够检测到死锁发生的位置和原因， 并能通过外力破坏死锁发生的必要条件，从而 使得并发进程从死锁状态中恢复出来。 83 死锁的检测 检测死锁实质上是确定是否存在环路等 待，一旦发现这种环路便认定死锁存在，并识 别出该环路所涉及的有关进程，以供系统采用 适当的措施来解除死锁。 84 资源分配图 85 死锁定理：如果资源分配图中不存在环路，则 系统不存在死锁；反之，如果资源分配图中存 在环路，则系统中可能存在死锁，也可能不存 在死锁。 86 图中存在着两个环路： P1R1P2R3P3R2 P1 P2R3P3R2P2 分析后可知系统处于 死锁状态，进程 P1、 P2和 P3参与了死锁。 87 图中也有一个环路： P1R1P3R2P1 但并不存在死锁状态， 因为资源类 R2中有一个资 源被进程 P4占有，如果进 程 P4释放这一资源，该资 源可能会被分配给进程 P3， 从而断开环路。 88 可以用对资源分配图简化的方法，来检测当前系 统状态是否为死锁状态。 死锁定理： 当前系统状态 S为死锁状态的充分条件是，当且仅当 S状 态的资源分配图是不可完全简化的。 89 死锁检测的时机 进程等待时检测 定时检测 资源利用率降低时检测 90 死锁的恢复 重新启动 终止进程 一次性撤销所有参与死锁的进程 逐一参与死锁的进程 剥夺资源 逐步剥夺 一次剥夺 进程回退 91 课堂练习 1. 操作系统 中的作业管理是一种（ ）。 A）宏观的高级管理 B）宏观的低级管理 C）系统开始加电 D）初始化引导完成 2. 定义：进程的周转时间进程完成时间进程到达时间。 现有三个进程同时到达，每个进程的计算时间均为 1小时，它 们在一台处理器上按单道方式运行，则平均周转时间为 （ ）。 A） 1小时 B） 2小时 C） 3小时 D） 6小时 3. 设系统中有两个进程共享 3个同类资源，为使系统不会发生 死锁，每个进程最多可以申请（ ）资源。 A） 0个 B） 1个 C） 2个 D） 3个 92 4. 在下列进程调度算法中，（ ）算法会对优先权进行调整。 A）先来先服务 B）短进程优先 C）高响应比优先 D）时间片轮转 5. 进程 P1使用资源情况：申请资源 r1， ，申请资源 r2， ， 释放资源 r1；进程 P2使用资源情况：申请资源 r2， ，申请资 源 r1， ，释放资源 r2。系统并发执行进程 P1、 P2，则系统将 （ ）。 A）不会发生死锁 B）可能发生死锁 C）必定产生死锁 D）不能给出答案 6. 资源的按序分配策略可以破坏（ ）条件。 A）互斥使用资源 B）占有且等待资源 C）非抢占资源 D）环路等待 93 7. 银行家算法是一种（ ）算法。 A）死锁解除 B）死锁避免 C）死锁预防 D）死锁检测 8. 在下列解决死锁的方法中，属于死锁预防策略的是（ ）。 A）银行家算法 B）资源有序分配 C）死锁检测 D）资源分配图化简法