三_处理机调度与死锁.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1) 资源分配表和进程等待表 资源分配表 进程等待表 r1 p2 p1 r1 r2 p5 p2 r3 r3 p4 p4 r4 r4 p1 … … … …  2)资源分配表和进程等待表 当进程P4申请资源3时，会产生死锁吗？  3)检测算法 3.死锁的解除 重要的是以最小的代价恢复系统的运行。方法如下： 1）重新启动 2）撤消进程 3）剥夺资源 4）进程回退 4.资源分配图 用有向图描述进程的死锁 系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例 资源分配图 二元组G=（V，E） V：结点集，分为P，R两部分 P={p1,p2,…,pn}, R={r1,r2,…,rm} E：边的集合，其元素为有序二元组: (pi,rj)或(rj,pi) 表示法: 资源类:用方框表示（资源的不同类型） 资源实例:用方框中的黑圆点表示（存在于每个 资源中） 进程 :用圆圈中加进程名表示 分配边：资源实例?进程的一条有向边 申请边：进程?资源类的一条有向边 5. 死锁定理 如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。 如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。 有环有死锁 有环无死锁 2. 死锁定理 图 3-12 资源分配图的简化 6. 资源分配图化简 方法如下: 1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点 2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边 7.解除死锁 当发现有进程死锁后，便应立即把它从死锁状态中解脱出来，常采用的方法有： 剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态； 撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等。 死锁的解除 图 3-13 付出代价最小的死锁解除方法 * * * * * * * * * * * * * * * * * * * 【进程推进顺序不当引起死锁】 资源少也未必一定产生死锁。就如同两个人过独木桥，如果两个人都要先过，在独木桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，那么问题就解决了。 所以，如果程序设计得不合理，造成进程推进的顺序不当，也会出现死锁。 思考题： 一个OS有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能产生死锁，为什么？ 答：不可能。因为死锁产生的原因有两点：系统资源不足或推进顺序不当，在本题中，进程所需的最大资源数为60，而系统共有该类资源65个，其资源数已足够系统内各进程使用。 1)互斥条件： 每一资源被分配给一个进程，或者空闲。 2)占有并请求条件： 已分配到了一些资源的进程可以申请新的资源。 3)不可剥夺条件： 进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。 4)循环等待条件： 链中的每一个进程都在等待相邻进程所占用的资源。 3. 产生死锁的必要条件 4. 死锁的解决办法 ①死锁的预防； ?②?死锁的避免； ??③?死锁的检测和恢复?????? 这种办法是在系统运行之前就采取措施，即在系统设计时确定资源分配算法，消除发生死锁的任何可能性。 该方法虽然比较保守、资源利用率低，但因简单明了并且安全可靠，仍被广泛采用。 产生死锁的四个必要条件中，互斥条件由设备的固有特性所决定的，不仅不能改变，相反还应加以保证，因此实际上只有三种方法。 3.5.2 死锁的防止 1．静态资源分配法（摒弃“占有并请求条件”） 系统规定每一个进程在开始运行前，都必须一次性地申请其在