操作系统原理方敏死锁电子教案

《操作系统原理方敏死锁电子教案》由会员分享，可在线阅读，更多相关《操作系统原理方敏死锁电子教案（45页珍藏版）》请在金锄头文库上搜索。

1、第四章 死 锁,操作系统课程组,第2页,内容回顾,UNIX进程模型 进程结构：proc结构，数据段，正文段。 进程状态 调度算法：动态优先级调度算法。 进程创建与终止：fork(), exit()。 进程通信：pipe; sleep, wakeup; wait, exit。 死锁,第3页,一、什么是死锁？,死锁(deadlock)定义：,在多道程序中，由于多个并发进程共享系统的资源，如果使用不当可能会造成一种僵局，即当某个进程提出资源的使用请求后，使得系统中一些进程处于无休止的阻塞状态，在无外力的作用下，这些进程将无法继续进行下去，这就是死锁。,第5页,二、为什么会产生死锁？,进程申请顺序不当

2、 同类资源分配不当,第6页,二、为什么会产生死锁？,进程通信不当 资源的类型 独占资源 VS 非独占资源 永久性资源 VS 临时性资源 独占资源分类 可剥夺式资源 不可剥夺式资源,第7页,二、为什么会产生死锁？,必要条件(Coffman 1971年指出) 资源互斥使用(资源独占) 非剥夺控制(不可强占) 零散请求 循环等待,第8页,三、如何解决死锁问题？,死锁的危害 轻则系统资源利用率严重下降，重则系统崩溃。 解决死锁的策略 置之不理法鸵鸟政策,优点：简单，简化系统设计，节约成本。 缺点：安全性欠佳。,第9页,三、如何解决死锁问题？,积极防御法不让死锁发生 思想：以积极的遏制为出发点。 手段：

3、 破坏产生死锁的必要条件。 分类： 静态策略：进程创建时就由系统分配了所有需要的资源，然后才执行，并且以后没有资源申请要求。缺点：系统效率低，并发性下降，资源浪费严重。 动态策略：执行时动态改变资源分配策略。缺点：实现复杂。优点：灵活，资源利用率高。,第10页,三、如何解决死锁问题？,事后处理法让死锁发生，事后处理 提出原因：预防策略虽然可以杜绝死锁发生，但是它提出的策略可能会或多或少影响到系统效率。 思想：可以容忍死锁的发生，事后处理。 优点：灵活，效率高。,第11页,四、死锁的预防,破坏死锁产生的必要条件 破坏互斥条件,局限：破坏“互斥”比较困难，而且对很多资源行不通。,第12页,四、死锁

4、的预防,破坏不可剥夺条件 思想：允许进程还未执行完成时释放已经占有的资源。 方法: 已经占有部分资源，还需要资源，如果得不到满足，则释放自己所占有的所有资源，以后再申请。 正在使用资源，有高优先级的进程请求相同资源，则低优先级进程放弃资源。 局限：实现困难，为了恢复现场需要耗费很多时间和空间。因此只适合类似CPU、存储器这样的资源。,第13页,四、死锁的预防,破坏零散请求条件 常常采用静态策略：进程创建时就由系统分配了所有需要的资源，然后才执行，并且以后没有资源申请要求，进程执行完后，释放资源。 缺点：系统效率低，并发性下降，资源浪费严重。 破坏循环等待条件 方法：给资源编号，进程必须按序申请

5、资源。,第14页,四、死锁的预防,局限： 资源编号困难：尽管资源的按序分配方法消除了死锁的问题，但给资源编号很困难，很难满足每一个进程的要求。 资源的编号很难和进程申请资源的顺序一致：资源顺序分配法是按资源编号申请资源，可能与实际使用资源的顺序不一致，使得一些先申请的资源因暂时不用，而长时间闲置，降低了系统资源利用率。 结论 死锁的预防是以破坏死锁产生的必要条件为基本方法，从而防止死锁发生的。其中由于对资源的申请加上了诸多的限制，因此这种策略虽有一定的效果，但其资源的利用率和效率比较低，很难令人满意。,第15页,五、死锁的避免,思想 允许死锁产生的条件存在，但通过动态的、明智的选择在分配资源之

6、前，系统判断假若满足进程的要求是否会发生死锁，如果会，资源就不予分配，从而确保永远不会到达死锁点，避免死锁的发生。 优点：比预防策略更为灵活实用，允许更多的并发，其资源利用率和效率也更高。,第16页,五、死锁的避免,系统的状态,安全状态,不安全状态,死锁,安全状态：指在某个时刻，当多个进程动态的申请资源时，如果存在一种顺序，使得系统按照这种顺序逐次地为每个进程分配所需资源后每个进程都可以在最终得到最大需求量后，依次顺利地完成。,避免死锁的关键就是：让系统在动态分配资源的过程中，不要进入不安全状态。,第17页,五、死锁的避免,单银行家算法（Bankers Algorithm） 1965年由Dij

7、kstra为T.H.E系统设计 基本思想：借用了银行借贷系统的分配策略。基于这样一些规则：,第18页,举例：假设一个银行拥有资金数量为10（单位省略），现在有4个客户a, b, c, d要来贷款，所需最大资金需求量为8，5，6，7，为方便期间我们用图形表示如下。,五、死锁的避免,0,8,8,0,5,5,0,6,6,0,7,7,银行剩余资金,10,初始状态,客户,已用资金,最大需求,仍需资金,a,b,c,d,1,8,7,2,5,3,1,6,5,2,7,5,银行剩余资金,4,状态1,Q：如何分配才能保证银行资金能够顺利周转？,第19页,五、死锁的避免,第20页,五、死锁的避免,分配策略：bcad,

8、第21页,五、死锁的避免,算法流程,第22页,五、死锁的避免,以上讨论的是单银行家算法只涉及到了一种资源，实际中资源的种类是多样的，一个进程往往需要申请多个资源才能完成工作。解决这一问题需要使用多银行家算法。,第23页,五、死锁的避免,多项资源银行家算法 举例：系统中有以下资源：5台打印机，7个手写板，8台扫描仪，9个读卡器，共有5个进程T1、T2、T3、T4、T5共享这些资源。各进程所需最大资源量和当前各进程请求资源情况如下：,各进程所需最大资源量,当前各进程请求资源,第24页,1、sum向量：表示系统资源总量 sum = （5，7，8，9） 2、allocation向量：表示当前系统已分配

9、资源 allocation =（3，5，7，7） 3、available向量：表示系统剩余资源 available = sum allocation =（2，2，1，2） 4、claim(i)向量：表示第i个进程还需申请资源数 claim(i) = sum(i) allocation(i),五、死锁的避免,为方面讨论，我们用向量来表示资源分配及占用情况：,sum,allocation,claim(i),第25页,五、死锁的避免,步骤： 比较claim(i)和available向量，寻找满足下列关系的进程 claim(i) available,available = （2，2，1，2）,allo

10、cation,available = （2，5，5，2）,第26页,五、死锁的避免,available = （2，6，7，3）,available = （3，7，7，5）,第27页,五、死锁的避免,available = （5，7，7，6）,available = （5，7，8，9）,第28页,五、死锁的避免,第29页,六、死锁的检测和解除,死锁的检测 检测工具资源分配图 定义：是描述进程申请资源和资源分配情况的关系模型图。表示系统中某个时刻进程对资源的申请和占有情况。 示例：,规则： （1）圆表示一个进程； （2）方块表示一个资源类，其中的圆点表示该类型资源中的单个资源； （3）从资源指向进

11、程的箭头表示资源被分配给了这个进程； （4）从进程指向资源的箭头表示进程申请一个这类资源；,第30页,六、死锁的检测和解除,一张合理的资源分配图应当满足如下条件 设资源类Rj有资源Wj个，用|(Rj, Pi)|表示Rj分配给进程Pi的资源个数；用|(Pi, Rj)|表示进程Pi申请Rj资源的资源个数。,第31页,六、死锁的检测和解除,检测方法化简算法,第32页,六、死锁的检测和解除,举例,结论：系统不会发生死锁。,第33页,六、死锁的检测和解除,临时资源的死锁检测 临时性资源：即可消耗的资源。如信号、消息、邮件等。 特点： 没有固定数目； 不需要释放。,第34页,六、死锁的检测和解除,临时性资

12、源分配的表述方式重定义的资源分配图 定义： 圆表示一个进程； 方块表示一个资源类，其中的圆点表示该类型资源中的单个资源； 由资源类指向进程的箭头表示该进程产生这种资源，一个箭头可表示产生一到多个资源，每个资源类至少有一个生产者进程； 由进程指向资源的箭头表示该进程申请这种资源，一个箭头只表示申请一个资源。,第35页,六、死锁的检测和解除,死锁判断标准 分析： 一个进程死锁意味着永久被阻塞。 对于临时性资源来讲，它有生产者，生产者会源源不断的生产资源，因此只要生产者进程不被阻塞，可以认为资源最终一定是充分的，可以满足各消费进程的需要。 需要的资源可以满足则进程一定不会死锁。 结论：判断系统是否死

13、锁的关键在于判断生产者进程的状态，若生产者进程不被阻塞，则可以认为它总会生产出该类资源，也就是说，某类资源的生产者进程只要不被阻塞，申请这类资源的所有申请者进程都可以得到满足。,第36页,六、死锁的检测和解除,检测方法化简 方法： 从那些没有阻塞的进程入手，删除那些没有阻塞的进程的请求边，并使资源类中资源数（图中黑点的数目）减1。 重复以上步骤直至： a. 图中所有的请求边都已经删除，则不会死锁 b. 图中仍然存在请求边但无法再化简，系统死锁。,第37页,六、死锁的检测和解除,死锁的解除 重新启动：这是一种常用但比较粗暴的方法，虽然实现简单，但会使之前的工作全部白费，造成很大的损失和浪费。 撤

14、消进程：死锁发生时，系统撤消造成死锁的进程，解除死锁。 一次性撤消所有的死锁进程。损失较大。 逐个撤消，分别收回资源。具体做法：系统可以先撤消那些优先级低的、已占有资源少或已运行时间短的、还需运行时间较长的进程，尽量减少系统的损失。,第38页,六、死锁的检测和解除,剥夺资源：死锁时，系统保留死锁进程，只剥夺死锁进程占有的资源，直到解除死锁。选择被剥夺资源进程的方法和选择被撤消进程相同。 进程回退：死锁时，系统可以根据保留的历史信息，让死锁的进程从当前状态向后退回到某种状态，直到死锁解除。 实现方法：可以通过结合检查点或回退（checkpoint/Rollback）机制实现。进程某一时刻的瞬间状

15、态叫做检查点，可以定期设置检查点。系统保存所有的检查点。一旦系统检查到有某个进程卷入了死锁，该进程就会被终止，剥夺它占有的所有资源。然后，系统查看保存的检查点信息，重新建立该进程的状态，从上次检查点的位置重新执行。目前发展已比较成熟，广泛用于DBMS中。,第39页,六、死锁的检测和解除,死锁检测举例 例1：以下有两个资源分配图，图a表示的是永久性资源，图b表示临时性资源，请分别化简并说明是否会发生死锁。,第40页,六、死锁的检测和解除,(a),Step1.检测有无环路,第41页,六、死锁的检测和解除,(b),查找非阻塞进程,结论：会发生死锁,第42页,六、死锁的检测和解除,例2：某一时刻，一个

16、系统中有T1、T2、T3、T4这四个进程，永久性资源有R1两个、R2三个，临时性资源有S1、S2各一个。 T1产生S1，申请两个单位的R2； T2占有两个单位的R1和一个单位的R2，同时申请两个单位的S2； T3占有一个单位的R2，同时申请一个单位的S1； T4生产S2，申请一个单位的S1和一个单位的R1。 根据以上的叙述画出资源分配图，并说明是否有死锁，如果有，请指出涉及哪些进程。,第43页,六、死锁的检测和解除,资源分配图,系统中有T1、T2、T3、T4这四个进程，永久性资源有R1两个、R2三个，临时性资源有S1、S2各一个。 (1)T1产生S1，申请两个单位的R2； (2)T2占有两个单位的R1和一个单位的R2，同时申请两个单位的S2； (3)T3占有一个单位的R2，同时申请一个单位的S1； (4)T4生产S2，申请一个单位的S1和一个单位的R1。,第44页,六、死锁的检测和解除,分析：T1 的执行有赖于R2 资源的释放；R2 释放资源需要T2 或T3 执行完；T3 执行需要S1资源，显然T3 不是一个阻塞进程，T3 可以首先执行完。,T3