《bal[工学]操作系统讲稿ch6》由会员分享，可在线阅读，更多相关《bal[工学]操作系统讲稿ch6（17页珍藏版）》请在金锄头文库上搜索。
1、Ch6 死锁,何为死锁? 死锁的必要条件:四条 死锁的预防:预先静态分配法,有序资源使用法 死锁的避免:银行家算法 死锁的检测:资源分配图 死锁的恢复:强制性撤消进程,挂起和解挂机构,6.1 死锁问题的提出,死锁:计算机系统中两个或多个进程无限期地等待永远 不会发生的条件,称此系统处于死锁状态. 环境:某些资源互斥地使用. 原因:(1)系统资源不足;(2)进程推进的顺序不合适. 乙进程 Y 共同进展路径1 的进展 死锁点 占用 输入机 禁区 占用打印机 危险区 3 2 占用输入机 X 占用打印机 甲进程的进展,6.2 死锁的必要条件,资源的概念 分配方式: “可抢占”资源, “不可抢占”资源
2、使用方式: “共享”资源, “独占”资源 使用期限: 永久资源, 临时资源 资源的共同性质:一个进程由于请求一个资源而未被满足,从而该进程被阻塞. 定义: 一个逻辑资源(简称资源)是指可以引起一个进 程进入等待状态的事物.,死锁的必要条件: 互斥条件: 一个资源一次只能被一个进程所使用 不可抢占条件:一个资源仅能被占有它的进程所释放,而不能被 别的进程强行强占. 部分分配条件:一个进程已占有了分给它的资源,但仍然要求其 它资源. 循环等待条件:若干个进程构成环行请求链,其中每个进程均占 有若干种资源中的某一种,同时每个进程还要求 (链上)下一进程所占有的资源.,P1,P2,R1,R2,防止死锁
3、发生(破坏条件之一),死锁的必要条件: 防止死锁发生 互斥条件 允许多个进程同时访问资源 不可抢占条件 强迫进程暂时释放资源给其它进程 部分分配条件 “预先静态分配法” 循环等待条件 “有序资源使用法”,6.3 死锁的预防,之一:预先静态分配法(破坏部分分配条件) 策略: 作业调度时,仅当系统满足作业运行时所需的全 部资源时,才把该作业调入内存运行.在作业运行前 一次性将其所需的全部资源分配给它,于是在作业 运行过程中不再会提出新的资源请求. 缺点: 资源浪费! 改进: 程序 - 程序步; 资源分配以程序步为单位! 优点: 资源利用率提高,减少资源浪费! 不足: - 增加了应用系统的设计和执行
4、开销! - 作业所需资源不能一次性满足可能无限延迟! - 作业所需资源逐步积累 占而不用- 资源浪费!,死锁的预防之二,有序资源使用法: (破坏循环等待条件) 策略: 把系统中的全部资源分别分给一个特定的序号,并且要求每个进程均应严格地按照序号递增的次序请求资源. 优点: 基于动态分配方法,资源利用率较前法提高. 关键: 小心安排资源序号! 问题: 1) 各类资源序号一经安排,不宜经常地随意改动; 2) 资源序号尽可能反映多数作业的实际使用资源的顺序,但总有不合适的作业而造成资源浪费.,6.4 死锁的避免和银行家算法,预防:破坏死锁必要条件之一,保证死锁不发生(限制条件较强,实现简单,但严重损
5、害了系统性能) 避免: 不严格限制必要条件(限制条件较弱,可能获得满意结果) 安全状态：指系统按某种进程顺序（如P1,P2,Pn）来为每个进程分配其所需资源，直到最大需求，使每个进程都可以顺利完成，此时系统所处状态为安全状态。该进程顺序称为安全序列.-至少具有一个安全序列的状态是安全状态! 不安全状态：若系统没有这样一个安全序列，则系统处于不安全状态。即无论再按照什么方式分配都将最后导致死锁! 每次分配资源之前先要判断此分配方式是否最终导致系统可能由安全状态进入不安全状态。按照安全序列分配资源!,银行家算法,问题：一个银行家在若干个顾客间共享他的资金(capital),每个顾客所需借款总额ne
6、ed=capital. 任务：银行家应能使他当前的全部顾客在有限时间内完成他们的交易（也就归还了他们的借款！） 顾客状态：（claim,loan）,claim=need-loan 银行家状态：(capital,cash) ,cash=capital-loan 银行家算法：保证银行家状态从一个安全状态转向另一个安全状态不死锁！（判断状态是否安全） 从当前状态S（顾客状态银行家状态）出发，逐个检查各顾客中谁的claim=cash,若其得到资源后能完成工作且归还全部借款，再进而检查谁又能完成工作,如果所有顾客均能完成，则状态是安全的。,单种资源银行家算法,已使用 要求数 已使用 仍要求数 已使用仍要
7、求数 Andy 0 6 1 5 1 5 Barbara 0 5 1 4 2 3 Marvin 0 4 2 2 2 2 Susan 0 7 4 3 4 3 可用 10 2 1 状态 安全 安全 不安全 cash 2 4 8 10 1 3 loan(claim) A A A A 4(4) 4(4) 4(4) 4(4) B B 2(1) 2(1) C C C C C 2(7) 2(7) 2(7) 3(6) 3(6),Marvin:2-4 Susan:3-8 Barbara:4-9 Andy:5-10,T0时刻系统状态： 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 T0时刻
8、系统安全，因为存在安全序列（P2,P1,P3）如下：给P2分配2个单位资源，P2完成后释放个单位的资源，则可用资源数为个； 给P1分配个单位资源，P1完成后释放个单位资源，则可用资源数为10个。 给P3分配7个单位资源，P3完成后释放9个单位资源，则可用资源数为12个。 若T0时刻P3请求分配一个，分给它则可用资源剩个单位；分配给P2后，完成释放个，此后P1和P3均因得不到足够的资源而等待死锁！= T0时刻P3申请而分配一个单位的资源，使系统进入不安全状态！为避免系统发生死锁,此请求不能满足, P3将因资源请求未满足而阻塞!,多种资源银行家算法,系统中有五个进程P0,P1,P2,P3,P4和三
9、种资源A,B,C,每一种资源的数量分别为10，5，7。在T0时刻的资源分配情况为： Max Allocation Need Available Finish ABC ABC ABC ABC P0 7 5 3 0 1 0 7 4 3 3 3 2 false P1 3 2 2 2 0 0 1 2 2 false P2 9 0 2 3 0 2 6 0 0 false P3 2 2 2 2 1 1 0 1 1 false P4 4 3 3 0 0 2 4 3 1 false 试探性分配，存在安全序列（P1,P3,P4,P2,P0）： 给P1分配（1,2,2）-完成任务而释放（3,2,2）-可用资源向量
10、为(5,3,2); 给P3分配（0,1,1）-完成任务而释放（2,2,2）-可用资源向量为(7,4,3);给P4分配（4,3,1）-完成任务而释放（4,3,3）-可用资源向量为(7,4,5);给P2分配（6,0,0）-完成任务而释放（9,0,2）-可用资源向量为(10,4,7);给P0分配（7,4,3）-完成任务而释放（7,5,3）-可用资源向量为(10,5,7). 若此时P1请求资源 Request(1,0,2)? 若之后P0再请求资源 Request(0,2,0)?,P1请求资源 Request(1,0,2)? Max Allocation Need Available Finish AB
11、C ABC ABC ABC P0 7 5 3 0 1 0 7 4 3 2 3 0 false P1 3 2 2 3 0 2 0 2 0 false P2 9 0 2 3 0 2 6 0 0 false P3 2 2 2 2 1 1 0 1 1 false P4 4 3 3 0 0 2 4 3 1 false 存在安全序列:( P1, P3, P4, P2, P0 ):可分配! 给P1分配（0,2,0）-完成任务而释放（3,2,2）-可用资源向量为(5,3,2); 给P3分配（0,1,1）-完成任务而释放（2,2,2）-可用资源向量为(7,4,3); 给P4分配（4,3,1）-完成任务而释放（4
12、,3,3）-可用资源向量为(7,4,5); 给P2分配（6,0,0）-完成任务而释放（9,0,2）-可用资源向量为(10,4,7);给P0分配（7,4,3）-完成任务而释放（7,5,3）-可用资源向量为(10,5,7). 若之后P0再请求资源 Request(0,2,0)?,P0再请求资源 Request(0,2,0)?,Max Allocation Need Available Finish ABC ABC ABC ABC P0 7 5 3 0 3 0 7 2 3 2 1 0 false P1 3 2 2 3 0 2 0 2 0 false P2 9 0 2 3 0 2 6 0 0 fals
13、e P3 2 2 2 2 1 1 0 1 1 false P4 4 3 3 0 0 2 4 3 1 false 不安全状态!所以不能分配!,6.5 死锁检测,条件：允许死锁必要条件存在，也未采用避免死锁的算法（提高资源利用率）故死锁可能发生，需检测！ 定义：实际地检查系统中是否存在死锁，并标出那些进程和资源被牵扯在死锁中。 应用：允许前三个死锁的必要条件存在的系统中，检查系统中是否存在循环等待条件。 方法：资源分配图 P1 R P2 R1 P1 P2 R2 资源 进程 资源分配 资源请求,资源分配图化简,化简：一个进程的所有资源要求均能被满足，则该进程得到其所需全部资源从而不断取得进展，直至完
14、成全部任务并释放出全部资源。 在有向图中找到既非阻塞又非孤立的结点，分配它所需的全部资源后，当它继续执行并完成然后释放其全部资源而使之成为孤立结点。 把孤立结点释放的资源分配给阻塞进程，使之能继续运行，并且在有限时间后完成，再释放其全部资源而成为新的鼓励结点。 经过一系列上述步骤，若能消去图中所有的边，使所有进程都成为孤立结点，则图可完全化简。否则为不可完全化简。 死锁定理：当且仅当系统某状态S所对应的资源分配图是不可化简的，则S是死锁状态。而不可被化简的进程即是被死锁的进程。反之，若状态S所对应的资源分配图是可化简的，则S是安全状态。 资源分配图的化简结果与化简顺序无关，最终结果是相同的！,6.6 死锁恢复,强制性地从系统中撤消进程并剥夺它们的资源给剩下的进程使用。 撤消进程的原则： 进程的优先数； 重新启动它并运行到当前撤消点所需的代价； 作业的外部代价：即与此进程相关的作业类型都可以有其相应的固定撤消代价。 挂起和解挂机构： 从被挂起进程那里强占资源以解除死锁。,
