-->
当前位置:首页 > DayDayUp > 正文内容

死锁的产生原因及其避免和预防

Luz3个月前 (09-22)DayDayUp606

预防死锁和避免死锁是两种不同的方法,用于管理多线程或多进程环境中的死锁情况。它们的主要区别在于何时采取措施以防止死锁的发生以及如何处理已经发生的死锁。

死锁产生的原因

死锁(Deadlock)通常发生在多个进程或线程之间,这些进程或线程争夺有限的系统资源时,因为彼此的行为导致了一种相互等待的情况,使得它们都无法继续执行下去。死锁产生的主要原因包括以下几个方面:

互斥条件(Mutual Exclusion)

多个进程或线程需要访问某个资源,但这些资源只能被一个进程或线程占用。这种互斥条件导致了竞争,只有一个进程或线程能够获得资源的访问权。

请求和持有条件(Hold and Wait)

已经获得了一些资源的进程或线程可以继续请求其他资源,而且它们不会释放已经持有的资源。这意味着即使一个进程或线程暂时无法获得其他资源,也会一直等待,不释放已有资源。

不可抢占性(No Preemption)

一些资源不能被强制性地从一个进程或线程中夺取,只能由拥有它的进程或线程主动释放。这意味着如果一个进程或线程持有了某个资源,其他进程或线程无法将其抢占,只能等待。

循环等待(Circular Wait)

多个进程或线程形成了一个循环,每个进程或线程都在等待下一个进程或线程所持有的资源。这种循环等待的情况使得每个进程或线程都无法前进,从而导致死锁。


死锁举例

当涉及到具体资源分配时,可以使用经典的“哲学家就餐问题”作为一个例子来说明各种死锁产生的原因。

在这个问题中,有五位哲学家坐在圆桌上,每位哲学家面前放着一碗面条,他们要使用两只筷子来进餐。

image.png

以下是不同死锁条件如何在这个例子中发生的:

互斥条件

每只筷子只能被一位哲学家同时使用,这是互斥条件的例子。

请求和持有条件

当一个哲学家想要吃面条时,他会请求两只筷子,如果两只筷子都可用,他会持有这两只筷子,并进餐。

如果他不能同时获得两只筷子,他会等待,但他仍然持有已经获得的筷子。

这就是请求和持有条件,因为哲学家会持有某些资源并等待其他资源,而不释放已经持有的资源。

不可抢占性

在这个问题中,筷子是不可抢占的,一旦被一个哲学家拿起,其他哲学家无法强制夺取,只能等待直到筷子被放下。

循环等待

当五位哲学家都试图同时拿起左手边的筷子,然后等待右手边的筷子时,会形成一个循环等待条件。

例如,哲学家1拿起了左手的筷子,哲学家2拿起了左手的筷子,以此类推,直到哲学家5尝试拿起左手的筷子,但此时所有的筷子都已经被持有,每位哲学家都在等待右手的筷子,导致死锁。

预防死锁(Deadlock Prevention)

预防死锁是在设计阶段或系统运行时采取措施来防止死锁的发生。

这通常涉及到对资源分配策略的限制,以确保在任何时刻,系统的资源需求不会导致循环等待、互斥和不可剥夺性等死锁条件的同时发生。

预防死锁的方法可能包括资源申请的有序性、资源的静态分配和动态分配的限制等。

针对死锁不同情况的预防

  1. 互斥条件(Mutual Exclusion)

    • 互斥条件是资源分配的本质特性,通常不容易改变。

    • 预防互斥条件可能需要更改资源访问机制,但这不是通常情况下的最佳解决方案。

    • 在实际系统中,通常无法避免互斥条件,因为某些资源需要被独占性地访问,如硬件设备等。因此,对于互斥条件,通常需要关注其他死锁条件的预防。

  2. 请求和持有条件(Hold and Wait)

    • 预防请求和持有条件可以通过强制要求进程或线程在请求资源之前释放已经持有的资源,或者在没有足够资源的情况下不持有任何资源。

    • 一种常见的方法是实施资源分配策略,要求进程或线程在请求资源时释放已经持有的资源,然后再重新请求所需的所有资源,以确保资源分配是"一次性"完成的。

  3. 不可抢占性(No Preemption)

    • 预防不可抢占性条件可能需要引入资源的抢占机制,允许操作系统在需要时从进程或线程中夺取资源。

    • 这可能会引入复杂性和不确定性,因此在设计系统时需要仔细考虑资源的抢占策略。

    • 有些资源(如只读文件或计算结果)可以考虑允许抢占,但其他资源(如磁盘上的关键文件)则不应该被抢占。

  4. 循环等待(Circular Wait)

    • 预防循环等待通常涉及到为资源分配引入一个全局的资源分配顺序或层级结构。

    • 一种常见的方法是为资源分配引入一个优先级系统,强制进程或线程按照一定的顺序来请求资源,从而防止循环等待。

    • 也可以使用资源分配图等技术来监测和预防循环等待。

避免死锁(Deadlock Avoidance)

避免死锁是在系统运行时根据进程的资源需求和资源分配来动态地避免死锁的发生。

这通常需要使用算法来检查每个资源请求,以确保资源分配不会导致死锁。

常见的避免死锁算法包括银行家算法资源分配图算法。这些算法通过分析资源分配的状态来确保资源分配是安全的,不会导致死锁。


各种避免死锁算法

  1. 银行家算法(Banker's Algorithm)

    • 每个进程在开始时声明它所需要的最大资源数量。

    • 每个进程在运行时请求资源,但不能超过它声明的最大需求。

    • 系统维护一个可用资源的向量,以及每个进程已经分配的资源和尚需的资源向量。

    • 当一个进程请求资源时,系统模拟分配资源并检查是否导致系统进入不安全状态。如果是,请求会被拒绝;否则,资源被分配。

    • 银行家算法用于多进程环境中,其中每个进程都在运行时请求一定数量的资源。它是一种静态分配的算法。

    • 银行家算法的目标是确保系统在任何时刻都能分配资源而不会进入死锁状态。

  2. 资源分配图算法(Resource Allocation Graph Algorithm)

    • 进程和资源分别表示为节点。

    • 通过有向边表示资源请求和分配关系。

    • 系统周期性地扫描资源分配图以检测是否存在环路。如果存在环路,可能会有死锁发生。

    • 如果没有环路,系统允许资源分配。

    • 资源分配图算法用于动态分配资源的环境中。它通过维护资源分配图来检测和避免死锁。

    • 当资源请求被拒绝时,进程会等待并周期性地重新请求所需资源。

  3. 死锁避免算法(Deadlock Avoidance Algorithm)

    • 死锁避免算法通常涉及到定义资源分配的策略,以确保在系统运行时不会出现死锁。

    • 这些策略可以包括资源分配的优先级、资源的层次结构或资源的抢占性。

    • 死锁避免算法需要根据系统的资源和进程特性来选择和实施,以平衡性能和可用性的需求。

  4. 信号量和互斥锁

    • 在编程中,信号量和互斥锁可以用来避免死锁。

    • 使用信号量时,程序员可以明确规定资源的分配和释放顺序,以确保不会发生死锁。

    • 互斥锁用于确保同时只有一个线程访问某个资源,从而避免了互斥条件。



不同的避免死锁算法适用于不同的场景和系统需求。选择合适的算法通常需要深入了解系统的资源分配模式和性能需求。此外,死锁避免算法可能会引入一些开销,因此需要仔细权衡性能和死锁避免的成本。




总结来说,预防死锁是在系统设计或运行时通过限制资源分配来预防死锁的发生,而避免死锁是在系统运行时动态地根据资源需求和分配情况来避免死锁的发生。两者都旨在确保系统不会陷入死锁状态,但它们的实施方式和时机略有不同。选择哪种方法取决于系统的需求和资源管理策略。


发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。