网站突然在百度消失了,最新百度新闻,建立导购网站,桂林建网站哪家好目录 死锁#xff08;1#xff09;
一、死锁的定义
二、产生死锁的原因
三、产生死锁的四个必要条件
四、解决死锁的方法
死锁#xff08;2#xff09;
第三节 死锁避免
一、死锁避免的概念
二、安全状态与安全序列
三、银行家算法
第四节、死锁的检测与解除 …目录 死锁1
一、死锁的定义
二、产生死锁的原因
三、产生死锁的四个必要条件
四、解决死锁的方法
死锁2
第三节 死锁避免
一、死锁避免的概念
二、安全状态与安全序列
三、银行家算法
第四节、死锁的检测与解除
一、死锁的检测和解除
二、死锁检测的算法
三、解除死锁的方法
死锁3
第五节 资源分配图
一、资源分配图
二、死锁定理
第六节 哲学家就餐问题 死锁1
在多道程序系统中同时有多个进程并发执行共享系统资源从而提高了系统资源利用率提高了系统的处理能力。 但是在进行资源分配时会产生一个随机性的错误--死锁。 在许多应用中如实时控制和监视系统中遇到死锁会带来很大的危害。
一、死锁的定义
指在多道程序系统中一组进程中的每一个进程均无限期地等待被该组进程中另一个进程所占用且永远不会释放的资源。 处于死锁状态的进程称为死锁进程。
二、产生死锁的原因
1.资源的概念 1永久性资源可重用资源如内存、外部设备、处理器等硬件资源各种数据文件、表格、共享程序代码等软件资源。 2临时性资源消耗性资源指由某个进程产生、只为另一个进程使用一次或经过短暂时间后便不再使用的资源。 如I/O和时钟中断信号、同步信号、消息等。 2.产生死锁的原因 1竞争资源系统在资源分配时出现失误进程间对资源的相互争夺而造成僵局。 2进程推进顺序不合理如P、V操作的信号量 3.死锁的例子 例5.1申请不同类资源产生死锁进程P1和P2在运行中使用输入、输出设备假定系统中只有一台输入设备和一台输出设备则进程P1和P2可能有如下形式 若进程交替执行如下 P1申请一台输入设备 P2申请一台输出设备 P1申请一台输出设备 P2申请一台输入设备 例5.2申请同类资源产生死锁假设有一类可重用资源R如内存它包含m个页面由n个进程P1、P2、……Pn2mn共享。假定每个进程按下述顺序一次申请和释放页面 ①申请一个页面 ②申请一个页面 ③释放一个页面 ④释放一个页面 例5.3 P、V操作使用不当产生的死锁对于第四章生产者--消费者问题如果把Pmutex放在Pempty和Pfull之前就会产生死锁。 考虑当①empty0,fulln的情况第一种情况假设生产者进程占有处理器此时执行完Pmutex再执行Pempty时生产者进程阻塞让出处理器消费者进程执行Pmutex也会阻塞此时产生死锁。 例5.4 对临时性资源的使用不加限制产生的死锁在进程通信时使用的信件可以看作是一种临时性资源如果对信件的发送和接收不加限制则可能引起死锁。 比如进程P1等待进程P3的信件S3S3到来后再向进程P2发送信件S1P2又要等待P1的信件S1到来后再向P3发送信件S2P3进程也要等待进程P2的信件到来后才能发送信件S3。 三、产生死锁的四个必要条件
对于永久性资源产生死锁的四个必要条件 ①互斥条件一个资源每次只能被一个进程使用资源独立 ②不可剥夺条件进程已获得的资源在未使用之前不能强行剥夺抢夺资源 ③请求和保持条件一个进程因请求资源而阻塞时对已获得的资源保持不放不释放锁 ④循环等待条件若干进程之间形成一种头尾相接的循环等待的资源关闭死循环 四、解决死锁的方法
①预防死锁②避免死锁③检测与解除死锁④忽略死锁
死锁2
第三节 死锁避免
前面讨论的死锁预防策略总体上是增加了较强的限制条件从而使实现较为简单但却严重地影响了系统性能。
一、死锁避免的概念
基本思想系统对进程发出的每一个系统能够满足的资源申请进行动态检查并根据检查结果决定是否分配资源如果分配后系统不会发生死锁则予以分配否则不予以分配。
和死锁预防的区别死锁预防是破坏产生死锁的四个必要条件之一严格地防止死锁的出现。而死锁避免是在系统运行过程中注意避免死锁的发生即使死锁的必要条件存在也不一定发生死锁。
二、安全状态与安全序列
1.安全状态如果操作系统能保证所有的进程在有限的时间内得到所需的全部资源则称系统处于“安全状态”否则说系统是不安全的。 判别如果存在一个由系统中所有进程构成的安全序列{P1、P2、……Pn}则系统处于安全状态。 2.安全序列系统能按某种进程推进顺序{P1、P2、……Pn}为每个进程Pi分配其所需资源直至满足每个进程对资源的最大需求使每个进程都可顺利地完成。此时称{P1、P2、……Pn}为安全序列。 3.安全状态与不安全状态的关系系统中不存在安全序列则称系统为不安全状态。 例5.5安全状态与不安全状态现有12个同类资源供3个进程共享进程P1总共需要9个资源但第一次先申请2个进程P2总共需要10个资源第一次要求分配5个资源P3总共需要4个资源第一次请求2个资源。经过第一次分配后系统还有3个资源未分配系统状态如图5-5所示。 该状态是否安全 答该状态安全系统剩余资源3而P3还需要2个资源把2个资源分配给P3后当P3执行完毕释放4个资源此时系统资源为5这5个资源可以分配给P2P2运行结束释放10个资源此时可满足P1进程需求进程P1执行完毕。存在安全序列{P1P2P3} 若进程P1提出再申请一个资源的要求系统从剩余资源中分配1个给P1后剩余2个资源如下图所示 答该状态不安全找不到安全序列因为剩余资源分配给P3进程P3进程用完后释放此时剩余资源为4资源数量不能满足P1和P2进程的需求量故状态不安全
三、银行家算法
愿意确保银行在发放现金贷款时不会发生不能满足所有客户需要的情况。 操作系统中保证系统不会进入不安全状态的算法
例5.6银行家算法应用示例 假定系统中有5个进程{P1P2P3P4P5}和三类资源{ABC}各种资源的数量分别是1057资源分配情况如图所示 答存在安全序列{P2P4,P5,P3,P1},该状态安全 在此状态下进程P2又提出请求102此时状态如图5-8 答在此状态下系统剩余资源不能满足任何进程的请求P2的请求不予满足P2等待。 单项选择题 某系统中有3个并发进程都需要同类资源3个试问该系统不会发生死锁的最少资源数是。 A.6 B.7 C.8 D.9 答案B 解析3个进程都需要同类资源3个。假定3个进程都得到了2个总共得到6个资源如果再有一个资源即7个时系统不会发生死锁。这类问题都可以用这个方法进行计算。
第四节、死锁的检测与解除
一、死锁的检测和解除
1.死锁的检测和解除 假如系统为进程分配资源时不采取任何限制性措施来避免和预防死锁而是在操作系统运行过程中不断地监督程序的执行和资源占用情况判断是否发生死锁一旦发生死锁采取专门的措施解除死锁并以最小代价使系统恢复正常。 2.死锁检测时机 1检测的实质检测算法检测是否存在“循环等待”条件
2时机 ①一次资源分配后②每次调度后③定时器定时运行检测程序④当某个进程长期处于阻塞状态或阻塞程序过多时
二、死锁检测的算法
算法规则当任一进程Pj申请一个已被占用的资源Ri时操作系统进行死锁检测反复查找资源分配表和等待进程表来确定Pj对资源Ri的请求是否导致形成环路若是出现死锁。 三、解除死锁的方法
1.剥夺资源一旦死锁挂起一些进程剥夺它们占用的资源给死锁进程以解除死锁。 2.撤销进程撤销部分死锁进程将它们占有的资源分配给另一些死锁进程直到死锁解除为止。 可以一次撤销所有死锁进程也可以逐个撤销。
死锁3
第五节 资源分配图
一、资源分配图
1.作用描述系统中资源分配和申请情况对死锁进行分析并采取对策 2.SRAG定义是一张有向图可定义为一个二元组即SRAEVE其中V是顶点的集合包括进程集合、资源集合E是有向边的集合是一个有序对Pi,ri,如图5-10所示 矩形表示资源圆点表示资源的数据量箭头从矩形内圆点出发表示该资源被占用箭头从其他处指向矩形表示有进程请求资源。 圆形表示进程矩形内的箭头指向进程表示进程占用该资源进程的箭头指向资源表示申请该资源。 二、死锁定理
1.作用判定死锁的法则 2.死锁定理1如果资源分配图中没有环路则系统无死锁 2如果资源分配图中出现了环路则可能存在死锁。具体判断如下 ①如果处于环路中的每个资源类中均包含一个资源实例表示矩形内的圆点数量则环路存在意味死锁的存在。此时环路是死锁的充分必要条件。如下图 如果处于环路中的每个资源类中实例的个数不全为1则环路存在是死锁的必要条件而非充分条件。如图5-11和图5-12所示 存在两个环路P1-r1-P2-r2-P3-r3-P1环路P2-r2-P3-r3-P2。P1、P2、P3都陷入了死锁。 存在环路P1-r1-P3-r2-P1但无死锁。 可以使用资源分配图简化方法来检测系统是否为死锁状态。步骤如下1在资源分配中找出一个既不阻塞又非独立的进程节点Pi。在顺利的情况下Pi可获得所需资源而继续运行直至运行完毕再释放其占有的全部资源这相当于消去Pi的请求边和分配边使之成为孤立的节点。 2将Pi释放的资源分配给申请它的进程若该进程能顺利运行完释放资源再次称为孤立节点。 3重复12步直到找不到符合条件的进程节点。经过简化后若能消去所有的边则该图可完全简化系统不存在死锁否则不可能完全简化存在死锁。 第六节 哲学家就餐问题
1.问题描述1有五个哲学家围坐在一圆桌旁每人面前有一只碗碗里有面条每两人之前放一只筷子 2每个哲学家的行为都是思考感到饥饿然后吃饭 3为了吃饭每个哲学家必须拿到两只筷子并且每个人只能直接从自己的左边或右边去取筷子 2.算法描述为每个筷子设置一个互斥信号量 semaphore chopstick[5]{1,1,1,1,1}
3.存在问题死锁 4.改进采用资源有序分配算法给每个筷子编号规定每个哲学家先拿编号小的筷子再拿编号大的筷子。哲学家i(1i4)不变第五个哲学家的程序改进如下
