大工20秋《操作系统》辅导资料八

易百网

操作系统辅导资料八主    题：第七章的辅导资料
学习时间：2020年11月16日--11月22日“不忘初心、牢记使命”主题理论学习：
“一带一路”是促进共同发展、实现共同繁荣的合作共赢之路，是增进理解信任、加强全方位交流的和平友谊之路。中国政府倡议，秉持和平合作、开放包容、互学互鉴、互利共赢的理念，全方位推进务实合作，打造政治互信、经济融合、文化包容的利益共同体、命运共同体和责任共同体。
摘选自《推动共建丝绸之路经济带和21世纪海上丝绸之路的愿景与行动》内    容：第七章
这周我们将学习课件第七章  死锁（死锁的必要条件，预防死锁，避免死锁）。本章的学习要求及需要掌握的重点内容如下：
基本要求：
1. 掌握死锁的必要条件
2. 了解预防死锁、避免死锁的基本方法
重点掌握内容：
1．重点：死锁的概念，死锁的必要条件，预防死锁，银行家算法。
2．难点：银行家算法。死锁的必要条件
        课前问题：
1.什么是死锁？
2.产生死锁的原因都有哪些？
3.死锁的必要条件是什么？1. 多个进程在并发执行过程中，因争夺资源而产生的一种僵局，当这种僵局状态出现时，所有进程都处于永远等待状态，若无外力作用，任何进程都无法继续向前推进，这种僵局就是死锁。
2. 产生死锁的原因：
竞争资源导致死锁   进程推进顺序不当导致死锁
（1）可剥夺资源和非剥夺资源
（2）竞争非剥夺性资源
系统配置的不可剥夺资源，由于数量有限，进程在使用这些资源过程中，有可能因争夺这些资源而导致系统出现死锁。
（3）竞争临时性资源
这些资源往往由一个进程产生，再被几个进程共享使用一暂短时间后便无用了，一些共享的数据结构（例如，共享的变量、共享的表）就是这类资源的例子。
/3．产生死锁的必要条件
（1）互斥条件：指进程要求对其获得的资源进行排他性使用，即在一段时间内某资源只能由一个进程占用。
（2）请求和保持条件：指进程至少已获得了一个资源，现在又提出新的资源请求，而该资源已被其他进程占用，于是请求进程只能阻塞等待，但等待时它又不释放已获得的资源。
（3）不剥夺条件：指进程所获得的资源在未使用完毕之前，不能被其他进程剥夺，只能由进程在使用完毕后自己释放。
（4）循环等待条件：指存在进程——资源循环等待环路，环路中的每个进程都在等待下一个进程占有的资源，从而导致每一个进程都处于永远等待状态。预防死锁
1. 什么是死锁的预防？
2. 如何预防死锁？1. 死锁的预防：属于死锁发生前的预防性措施。这种方法通过预先设置某些限制条件，破坏死锁发生的某个或几个必要条件，从而使死锁不可能再出现。优点是简单、容易实现，不足之处是人为给系统施加一些限制条件，会影响系统的资源利用率和系统的吞吐量。
/2. 预防死锁破坏“请求和保持”条件
采用资源预分配策略，每个进程在执行之前必须一次性申请它运行所需要的全部资源；只要系统具有足够的资源，就进行分配，这种就使得进程在执行过程中不会再提出新的资源请求，从而使请求条件不成立；但在分配时，只要系统有一种资源不能满足进程要求，即使其他资源空闲，也不进行分配，而让进程等待；由于进程等待时没有占用任何资源，所以保持条件也不成立。
优点：简单、容易实现、安全、 。
缺点：
1）系统资源浪费严重
2）导致一些进程延迟运行破坏“不剥夺”条件
进程执行过程中，根据需要提出资源请求，当一个已经占有了某些资源的进程，又提出新的资源请求而暂时得不到满足时，它必须释放原来已获得的全部资源，进入等待状态，以后需要时再重新申请。由于进程在等待时已释放了它占有的全部资源，于是可以认为该进程占有的资源被剥夺了，从而破坏了不剥夺条件。
存在问题：
（1）实现起来较复杂、代价太大。因为一个资源在使用一段时间后又强行剥夺，有可能造成前段时间的工作失效，即使采取一些补救措施，也有可能前后两次的执行结果不连续。
（2）进程反复申请和释放资源，致使进程执行被无限期推迟，延长了系统的周转时间，增加了系统开销，降低了系统性能。破坏“循环等待”条件
将系统中的资源按照大多数进程使用资源的顺序进行编号，每个进程只能严格按照编号递增的顺序申请资源。在这种分配策略下，进程在获得某个资源后，只能申请较高编号的资源，不能再申请低编号资源，于是，任何时候，在申请资源的诸进程中，总有一个进程占据了具有较高编号的资源，它继续申请的资源必然是空闲的，以至于在对应的资源分配图上，不可能形成进程—资源循环等待环路，从而破坏了循环等待条件。
与前两种策略相比，系统的资源利用率和吞吐量得到了明显改善。但也存在以下不足：
（1）进程实际使用资源的顺序不一定与编号的顺序一致，本分配策略会造成资源浪费；
（2）资源的编号必须相对稳定，当系统新增设备后，处理起来比较麻烦，限制了新设备的增加；
（3）这种严格的资源分配顺序使用户编程的自主性受到限制。避免死锁
课前问题：
1.什么是避免死锁？
2.如何判定系统安全与否？
3.什么是银行家算法？1. 避免死锁，也属于死锁发生前的预防性措施。这种方法不是通过预设限制条件破坏死锁产生的必要条件，而是采用某种手段避免系统进入不安全状态，从而防止死锁发生。因此不会对系统的资源利用率和吞吐量产生较大影响，但该方法实现起来难度要大一些。
基本思路：允许进程动态申请资源，但系统在进行资源分配之前，必须先计算此次分配的安全性，若此次分配不会导致系统进入不安全状态，则将资源分配给进程，否则，即使资源空闲，也不进行分配，而让进程等待。2. 系统安全状态和不安全状态
安全状态：
是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。
不安全状态：
如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
例题：
假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：
/分析后，当前时刻系统是安全的，因为存在一个安全序列（ P2， P1， P3） ，使得进程按此顺序申请资源都能得到满足并顺利执行
系统由安全状态向不安全状态的转换
如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。
/
因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。3. 利用银行家算法避免死锁
银行家算法中的数据结构
（1）系统可用资源向量Available。是一个含有m个数组元素的一维数组，其中的每一个数组元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［i］=K，则表示系统中现有i类资源K个。
(2) 最大需求矩阵Max。一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i][j]＝k ,则表示进程i需要j类资源的最大数目为K。
（3）分配矩阵Allocation。一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果若Allocation [i][j]＝k， 则表示进程i当前已分得j类资源的数目为K。
（4）需求矩阵Need。一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果若Need[i][j]＝k，则表示进程i还需要j类资源K个，方能完成其任务。
        Need[i][j]＝Max[i][j]－Allocation [i][j]   
             (i=1,2,……,n；j=1,2,……,m)
（5）请求向量Request[i] (i=1,2,……,n)：一个具有m个数组元素的一维数组，每个数组元素代表第i号进程当前请求某类资源的数量。若Request[i][j]＝k，则表示第i号进程正请求k个第j类资源。      
银行家算法
进程i提出资源请求Request[i]，银行家算法按照以下思路决定是否满足进程i的分配请求：
（1）如果Request[i]≤Need[i]，则继续往下执行，否则认为出错，因为它请求的资源数量超过了它目前还需要的数量。
（2）如果Request[i][j]≤Available[j]（j=1,2,……,m），则继续往下执行，否则表示目前尚无足够的资源，进程i必须等待。
（3）系统试探着将资源分配给进程i，并修改数据结构：
        Available[j]＝Available[j]－Request[i][j]              （ j=1,2,……,m）
       Allocation[i][j]＝Allocation[i][j]＋Request[i][j]    （ j=1,2,……,m）
       Need[i][j]＝Need[i][j]－Request[i][j]                     （ j=1,2,……,m）
（4）系统执行安全性算法，检查本次资源分配的安全性，若分配后系统仍处于安全状态，则正式将资源分配给进程i，否则本次分配作废，恢复原来的资源状态，让进程i等待。
安全性算法
（1）设置两个一维数组：Work包含m个数组元素，代表在检测过程中的某个时刻仍空闲的资源数量；初始值等于Available。Finish包含n个数组元素；Finish[i](i=1,2,……,n)代表进程i是否可以分得足够的资源而运行结束，若Finish[i]＝true，则表示进程i可以运行结束；刚开始进行试探时，Finish[i]＝false，若有足够的资源分配给进程i，再令Finish[i]＝true。
（2）从进程集合中找到一个能满足下述条件的进程：
         Finish[i]＝false且Need[i][j]≤Work[j](j=1,2,……,m)
     若找到，则执行第（3）步，否则执行第（4）步。
（3）由于进程i获得资源后可以执行完成，而执行完毕后会
    释放它占有的资源，故应修改以下数据结构：
         Work[j]＝Work[j]＋Allocation [i][j]           （j=1,2,……,m）
         Finish[i]＝true
  再转第（2）步。
（4）若所有进程的Finish数组元素值都等于true，则表示系统处于安全状态，否则系统处于不安全状态。重要考点
一、简答题
1.某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。若P1，P2，P3已申请到4台，2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程
/
  按照银行家算法
/
系统安全！二、单项选择题
1. 破坏死锁的四个必要条件之一就可以预防死锁。若规定一个进程请求新资源之前首先释放已经占有的资源，则是破坏了（     ）条件。
A．互斥使用
B．全部分配
C．不可剥夺
D．以上都不对
答：C本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986