死锁的概念和发生原理 概念:多个同时进程争夺系统资源导致相互等待的现象发生。 原理:如果一系列进程中的每个进程都在等待某个事件的发生,并且此系列进程中只有其他进程可以触发该事件,则此系列进程称为发生死锁。 本质原因:1 ),系统资源有限。 2 )流程推进顺序不合理。
http://www.Sina.com/http://www.Sina.com /某个资源一次只能访问一个进程。 这意味着分配给某个进程的资源在该进程的访问结束之前将无法访问其他进程。死锁产生的4个必要条件两个进程本身占用了资源(一个或多个),同时资源还没有被填满,正在等待其他进程释放其资源。 1、互斥:因为别人已经占有了某个资源,所以不能因为自己也需要这个资源就夺走别人的资源。2、占有且等待:因为存在进程链,所以每个进程至少占用以下进程所需的一个资源: 如果满足所有这四个条件,则会发生死锁,发生死锁的进程将无法继续,拥有的资源也将无法释放。 这将降低CPU的吞吐量。 死锁情况会浪费系统资源,影响计算机的使用性能。 那么,解决死锁问题是相当必要的。
3358 www.Sina.com/http://www.Sina.com /发生死锁需要4个条件,除非满足至少一个条件,否则不发生死锁。 互斥条件是非共享资源所必须的,不仅不能变更而且应该保证,所以主要破坏产生死锁的其他三个条件。3、不可抢占:如何破坏“占用并等待”条件1 :所有进程在开始执行之前,必须一次性申请执行过程中所需的所有资源。 优点:简单易实施,安全。 缺点:由于某些资源未得到满足,进程无法启动。 另外,已经满足的其他资源也没有被利用,资源的利用率大幅降低,导致资源的浪费。 过程中经常发生饥饿现象。 方法2 )该方法是对第一种方法的改进,允许进程在运行初期只获得所需资源并开始运行,逐步释放运行过程中分配的已用资源,然后请求新资源。 这样可以提高资源利用率,也减少进程饥饿问题。4、循环等待:打破“不可抢占”的条件。 如果提出新的资源请求还不能满足已经拥有一些资源的进程,则必须释放已经拥有的所有资源,并在需要以后使用时重新申请。 这意味着进程占用的资源将暂时释放或断开连接。 这种方法实现起来很复杂,成本也很大。 释放已有的资源很可能会导致流程前工作的实效性等,重复申请和资源释放会无限延迟流程的执行,不仅会延长流程的周转周期,还会影响系统吞吐量。避免死锁的方法通过定义资源类型的线性顺序可以防止打破“循环等待”条件,可以对每个资源进行编号。 如果某个进程占用了编号为I的资源,则下一个申请资源的只有大于编号I的资源。 如图所示,该方法避免了循环等待,但该方法低效,降低了资源运行速度并在不需要的情况下可能拒绝资源访问。 例如,即使进程c试图申请资源1,如果资源1没有被其他进程占用,则分配进程c是没有问题的,但是为了不发生循环等待,申请将被拒绝。 由此,资源使用率为1、死锁预防 ----- 确保系统永远不会进入死锁状态的死锁避免通过利用额外的检查信息来判断在分配资源时是否发生死锁,并仅在不发生死锁时分配资源两种可能的解决方案可以是1、如果由一个进程的请求发生死锁,则不重新启动该进程2、如果由一个进程的资源添加请求发生死锁,则拒绝该申请。 死锁避免的具体实现,通常涉及存储库算法a、a、存储库算法的数据结构用于表示资源向量Available :系统中各种资源的剩余数量系统通常有各种类型的资源。 假设有m种。 因此,使用具有m个元素的数组来表示各种资源。 数组元素的初始值是位于系统中的该类的所有可用资源的数量,其值根据该类的资源的分配和回收而动态变化。 最大需求矩阵Max :用于表示每个流程对各种资源的最大需求。 进程可能有多个。 假设为n个。 然后,可以用一个nxm矩阵表示每个进程的多个资源的最大需求量分配矩阵Allocation。 顾名思义,它用于表示已经分配给每个进程的每个资源的数量。 也是nxm的矩阵。 需求矩阵Need :用于表示进程仍需要的资源数量,由nxm矩阵表示。
系统可能无法立即满足流程的最大需求。 流程对资源的最大需求通常也是整个执行周期所需的资源数量,并不是所有时间都需要这么多资源。 因此,为了推进进程的执行,通常系统会先
分配个进程一部分资源保证进程能够执行起来。那么,进程的最大需求减去已经分配给进程的数目,就得到了进程仍然需要的资源数目了。银行家算法通过对进程需求、占有和系统拥有资源的实时统计,确保系统在分配给进程资源不会造成死锁才会给与分配。 死锁避免的优点:不需要死锁预防中的抢占和重新运行进程,并且比死锁预防的限制要少。 死锁避免的限制: 必须事先声明每个进程请求的最大资源量 考虑的进程必须无关的,也就是说,它们执行的顺序必须没有任何同步要求的限制 分配的资源数目必须是固定的。 在占有资源时,进程不能退出 3、死锁检测与解除 ----- 在检测到运行系统进入死锁,进行恢复。 允许系统进入到死锁状态 死锁检测 下图截自《操作系统--精髓与设计原理》