Skip to content

Deadlocks

:material-circle-edit-outline: 约 1612 个字 :material-clock-time-two-outline: 预计阅读时间 5 分钟

A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set

Deadlock Characterization

产生死锁的四个必要条件：

  1. Mutual exclusion（互斥）
    • 每个资源只能有一个进程使用
  2. Hold and wait
    • 拿了资源，但还需要更多资源，等待时不会释放已经拿了的资源
  3. No preemption（不可抢占、不剥夺）
  4. Circular wait（循环等待）
    • 你在等我释放，我也在等你释放

Resource-Allocation Graph 资源分配图

圆圈表示进程，方框表示资源

一个资源可能会有多个 instance，所以方框里面会有小方框

  • request edge – Pi → R，指向资源表示该进程请求资源
  • assignment edge – Rj → Pi，指向进程表示该资源已被分配

S 为死锁状态的充分条件是：尚且仅当 S 状态的资源分配图是不可完全简化的

  • 如果图里 没有环路，则一定不会有死锁
  • 如果图里有环路
    • 如果环路里的 resource type 均只有一个 instance，则必死锁
    • 否则不确定，只能说有可能死锁

[!EXAMPLE]

Resource Allocation Graph With A Deadlock

image-20241114112220808

Resource Allocation Graph With A Cycle But No Deadlock

image-20241114112658668

资源分配图的简化

  1. 找到那些目前情况下有足够资源能够执行的进程
  2. 把不阻塞的进程的所有边都去掉，形成一个孤立的点，表示他们执行完并释放资源了
  3. 看剩下的进程有哪些是不阻塞的，然后把它们逐个变成孤立的点。

  4. 最后

    • 如果所有的资源和进程都变成孤立的点，这样的图就叫做可完全简化
      • 如果一个图可完全简化，则不会产生死锁
    • 如果图中还有边存在，则不可完全简化，会产生死锁

[!EXAMPLE] 没有死锁的化简例子

image-20241114113207756

image-20241114113225933

image-20241114113232696

Methods for Handling Deadlocks

死锁处理的策略：

  1. Prevention 死锁预防
  2. Avoidance 死锁避免
  3. Detection 死锁检测 + Recovery 死锁解除

Deadlock Prevention

就从四个必要条件分别下手咯

  1. 互斥是不能破坏的，共享资源必须互斥
  2. Hold and wait，这个的破坏之前讲过，线程随机 超时后释放资源
    • Low resource utilization; starvation possible
  3. No Preemption，需要 wait 就先释放已经拿到的资源，空手 wait
  4. Circular Wait ，这个就得对进程执行、申请顺序进行排序了

Deadlock Avoidance

一个进程在申请资源时，检查这个申请是否会造成 circular wait，会就不给申请

Safe State 安全状态

每次分配资源时就先检查分配后系统是否处于 Safe State

安全状态是指，此时存在某种序列（如 P1、 P2……Pn），按这个顺序分配资源，能顺利执行完所有进程，这个序列（P1、P2…….Pn）称为安全序列

任意 Pi 都可以等它前面的进程执行完后得到所需资源

若系统某个状态下不存在安全序列，则称系统处于不安全状态

image-20241114115818373

Resource-Allocation Graph Algorithm

资源分配图算法，使用于 Single instance of a resource type

基于资源分配图，增加 Claim edge（需求边），指示一个 process 可能会请求一个 resource，用虚线 dashed line

相关的转化规则如下：

  1. Claim edge converts to request edge（请求边） when the process requests resource
  2. Request edge converted to an assignment edge （分配边） when the resource is allocated to the process
  3. When a resource is released by a process, assignment edge reconverts to a claim edge

进程 Pi 申请资源 Rj 时，会形成一条需求边 Claim edge

我们尝试将需求边 Pi → Rj 变成分配边 Rj → Pi 后，检查会不会形成环

如果没有环存在，那么资源分配会使系统处于安全状态，就允许申请

否则撤销更改，进程必须等待

Banker’s Algorithm

银行家算法，适用于 Multiple instances of a resource type

新增 5 个数据结构：

设 n = number of processes，m = number of resources types

  1. Available [j]: Vector of length m.

    • If Available [j] = k, then k instances of Rj available

  2. Max: n x m matrix.

    • If Max [i, j] = k, then process Pi may request at most k instances of Rj.

  3. Allocation: n x m matrix.

    • If Allocation [i, j] = k then Pi is currently allocated k instances of Rj

  4. Need: n x m matrix.

    • If Need [i, j] = k, then Pi may need k more instances of Rj to complete its task.
    • Need [i, j] = Max [i, j] – Allocation [i, j]

  5. Request：n x m matrix.

    If Request [i, j] = k then Pi wants k instances of Rj

Safety Algorithm 安全算法

安全算法用于检测一个系统当前是否处于安全状态

Let Work and Finish be vectors of length m and n

1-Initialize

  1. Work = Available 即当前空余资源总和
  2. Finish [i] = false for i = 1,2,3, …, n

2-Allocate

Find an index i such that

  1. Finish [i] = false
  2. Need [i] \(\le\) Work 即该进程需求资源总和小于当前空余资源

If no such i exists, go to step 4

3-Release

Work = Work + Allocation [i]

Finish [i] = true

go to step 2

4-Finish

If Finish [i] == true for all i,

then the system is in a safe state

算法

  1. If Request [i] \(\le\) Need [i], go to step 2.
    • Otherwise, raise error condition, since process has exceeded its maximum claim.
  2. If Request [i] \(\le\) Available, go to step 3.
    • Otherwise Pi must wait, since resources are not available.
  3. Pretend to allocate requested resources to Pi:
    • Available = Available - Request [i];
    • Allocation [i] = Allocation [i] + Request [i];
    • Need [i] = Need [i] – Request [i]
  4. Call Safety Algorithm
    • If safe $\rightarrow $ the resources are allocated to Pi.
    • If unsafe $\rightarrow $ Pi must wait, and the old resource-allocation state is restored

image-20241118201007934

Deadlock Detection

Single Instance of Each Resource Type

使用 wait-for graph 等待图，可由资源分配图转换得到：

image-20241118201343939

图里的 node 都是 process，Pi → Pj if Pi is waiting for Pj

定期使用算法检测是否有 cycle，如果有 cycle 就说明存在 deadlock

Several Instances of a Resource Type

还是增加几个类似 banker algo 的数据结构

  1. Available: A vector of length m
    • indicates the number of available resources of each type.
  2. Allocation: An n x m matrix
    • defines the number of resources of each type currently allocated to each process.
  3. Request: An n x m matrix
    • indicates the current request of each process.
    • If Request [i, j] = k, then process Pi is requesting k more instances of resource type.

算法如下：

  • Let Work be vectors of length m
  • Let Finish be vectors of length n

1-Initialize

Work = Available

For i = 1,2, …, n,

  • if Allocation [i] \(\ne\) 0, Finish [i] = false;
  • otherwise, Finish [i] = true

2-Find an index i such that

Finish [i] == false

Request [i] \(\le\) Work

If no such i exists, go to step 4.

3-

Work = Work + Allocation [i]

Finish [i] = true

go to step 2

4-

If Finish [i] == false, for some i, 1 \(\le\) i \(\le\) n, then the system is in deadlock state.

Moreover, if Finish [i] == false, then Pi is deadlocked.

Recovery from Deadlock

打破/解除死锁两种方法： 进程终止，抢占资源

Process Termination 进程终止

要么全部关，要么一个个关直到打破死锁

Resource Preemption 资源抢占

要么选一个 victim，其它进程抢占它

要么直接回退到 safe state