第1页：第三章 处理机调度与死锁封面
第三章 处理机调度与死锁：本页为《计算机操作系统》课件封面，标注课程名称与英文名称 Operating Systems，并列出 WINDOWS、UNIX、LINUX 等常见操作系统类型。
第2页：3.5产生死锁的原因和必要条件
3.5产生死锁的原因和必要条件
- 死锁
- 在多进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们都将无法再向前推进
第3页：3.5.1产生死锁的原因
3.5.1产生死锁的原因
- 竞争资源
- 当系统中供多个进程共享的资源，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁
- 进程间推进顺序非法
- 进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁
第4页：3.5.2产生死锁的必要条件
3.5.2产生死锁的必要条件
- 互斥条件
- 进程互斥使用资源
- 请求和保持条件：部分分配条件
- 申请新资源时不释放已占有资源
- 不剥夺条件
- 一个进程不能抢夺其他进程占有的资源
- 环路条件
- 存在一组进程循环等待资源S1S3S2P2P3P1
第5页：3.5.3处理死锁的基本方法
3.5.3处理死锁的基本方法
- 预防死锁
- 破坏产生死锁的四个必要条件中的一个或几个条件
- 避免死锁
- 在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁
- 检测死锁
- 通过系统所设置的检测机构，及时地检测出死锁的发生；采取适当措施，从系统中将已发生的死锁清除掉
- 解除死锁。这是与检测死锁相配套的一种措施
第6页：3.6.1预防死锁
3.6.1预防死锁
- 一种较简单和直观的事先预防的方法
- 设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁
- 互斥条件
- 请求和保持条件
- 不剥夺条件
- 环路条件
第7页：3.6.2系统安全状态
3.6.2系统安全状态
- 3.6.2系统安全状态1.安全状态
- 如果系统无法找到这样一个安全序列，则称系统处于不安全状态
- 当系统进入不安全状态后，便有可能进而进入死锁状态
- 避免死锁的实质在于
- 系统在进行资源分配时，如何使系统不进入不安全状态
第8页：安全状态之例（一）
安全状态之例（一）
- 2．安全状态之例
- 假定系统中有三个进程P1、P2和P3，共有12台磁带机
- T0时刻是安全的？+2-2=1
第9页：安全状态之例（二）
安全状态之例（二）
- 2．安全状态之例
- 假定系统中有三个进程P1、P2和P3，共有12台磁带机。+5-5=0
第10页：安全状态之例（三）
安全状态之例（三）
- 2．安全状态之例
- 假定系统中有三个进程P1、P2和P3，共有12台磁带机
- T0时刻是安全的。+7-7=3
第11页：安全状态向不安全状态转换（一）
安全状态向不安全状态转换（一）
- 3．由安全状态向不安全状态的转换
- 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。+1-1=2
第12页：安全状态向不安全状态转换（二）
安全状态向不安全状态转换（二）
- 3．由安全状态向不安全状态的转换
- 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。+2-2=0
第13页：安全状态向不安全状态转换（三）
安全状态向不安全状态转换（三）
- 3．由安全状态向不安全状态的转换
- 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态
第14页：安全状态向不安全状态转换（四）
安全状态向不安全状态转换（四）
- 3．由安全状态向不安全状态的转换
- 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态
- 从给P3分配了第3台磁带机开始，系统便又进入了不安全状态
第15页：3.6.3利用银行家算法避免死锁
3.6.3利用银行家算法避免死锁
- 3.6.3利用银行家算法避免死锁1．银行家算法中的数据结构
- (1)可利用资源向量Available
- 每类资源未分配数量向量
- 含有m个元素的数组
- 如果Available[j]=K，则表示系统中现有Rj类资源K个
第16页：最大需求矩阵Max
最大需求矩阵Max
第17页：分配矩阵Allocation
分配矩阵Allocation
- 银行家算法中的数据结构
- 也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数
第18页：需求矩阵Need
需求矩阵Need
- 银行家算法中的数据结构
- (4)需求矩阵Need
- 一个n×m的矩阵，用以表示每一个进程尚需的各类资源数
- 如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务
第19页：银行家算法的步骤（一）
银行家算法的步骤（一）
- 2．银行家算法
- (1)
- Pi发出资源请求Requesti后，系统按下述步骤进行检查
- (2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值
- (3)；否则，表示尚无足够资源，Pi须等待
第20页：银行家算法的步骤（二）
银行家算法的步骤（二）
2．银行家算法 (2) (4)执行安全性算法，检查此次资源分配后系统是否处于安全状态 若安全，将资源正式分配给进程Pi 否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待
第21页：安全性算法的步骤（一）
安全性算法的步骤（一）
3.安全性算法 (1) (1)设置两向量 ①可供进程继续运行所需各类资源数的Work初始时Work:=Available
第22页：安全性算法的步骤（二）
安全性算法的步骤（二）
3.安全性算法 (2) (2)寻找一个能满足下述条件的进程 (3)，否则执行步骤 (4) (4)如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态
第23页：银行家算法实例的系统状态
银行家算法实例的系统状态
- 实例说明系统所处的安全或不安全状态
- 假定系统中有五个进程{P0，P1，P2，P3，P4}
- 三类资源{A，B，C}
- A类资源共有10个
- B类资源共有5个
- C类资源共有7个
第24页：T0时刻的资源分配情况
T0时刻的资源分配情况：（1）在时刻T0,系统目前资源分配情况如下。
第25页：安全性检查中的Work与Need
安全性检查中的Work与Need：进程Work NeedAllocation Work=Work+allocationA B C A B C A B C A B C5 3 23 3 21 2 22 0 05 3 20 1 12 1 17 4 37 4 3P1P3P4P2P04 3 10 0 27 4 57 4 56 0 03 0 210 4 710 4 74 3 00 1 010 5 7NeedA B CP0 7 4 3P1 1 2 2A B CP2 6 0 0P3 0 1 1A B CP4 4 3 1。
第26页：T0时刻处于安全状态
T0时刻处于安全状态
- 可以断言T0时刻，系统处于安全状态
- 因为序列{P1,P3,P4,P2,P0}能满足安全性条件
- （2）进程P1申请资源request1=(1,0,2)，系统能将资源分配给它吗？
第27页：各进程的Need矩阵数据
各进程的Need矩阵数据
- NeedA B C7 4 36 0 00 1 14 3 1进程MaxAllocation AvailableA B C A B C A B CP0 7 5 3 0 1 0P1 3 2 2P2 9 0 2 3 0 2P3 2 2 2 2 1 1P4 4 3 3 0 0 2
- 检查: request1(1,0,2) ≤ Need1(1,2,2) andrequest1(1,0,2) ≤ Available(3,3,2)结果满足条件，试分配。3 0 20 2 02 3 0得到新状态：2 0 03 3 21 2 2
第28页：P1申请资源后的安全性判定
P1申请资源后的安全性判定
第29页：P4申请资源的检查
P4申请资源的检查
- （3）进程P4申请资源request4=(3,3,0)
- 检查: request4(3,3,0) ≤ Need4(4,3,1) andrequest4(3,3,0) ≥ Available(2,3,0)
- 让P4等待NeedA B C7 4 30 2 06 0 00 1 14 3 1进程MaxAllocation AvailableA B C A B C A B CP0 7 5 3 0 1 0 2 3 0P1 3 2 2 3 0 2P2 9 0 2 3 0 2P3 2 2 2 2 1 1P4 4 3 3 0 0 2
第30页：P0请求资源的检查
P0请求资源的检查
- （4）P0请求资源request0=(0,2,0)
- 检查: request0(0,2,0) ≤ Need0(7,4,3) andrequest0(0,2,0) ≤ Available(2,3,0)结果满足条件，试分配。0 3 07 2 32 1 0得到新状态：NeedA B C7 4 30 2 06 0 00 1 14 3 1进程MaxAllocation AvailableA B C A B C A B CP0 7 5 3 0 1 0 2 3 0P1 3 2 2 3 0 2P2 9 0 2 3 0 2P3 2 2 2 2 1 1P4 4 3 3 0 0 2系统已处于不安全状态了
第31页：作业
作业：作业。
