7.1 Avoidance&Detection

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

ch7 Deadlocks.pdf 操作系统（本）2024-11-14 第 7-8 节

Avoidance algorithms

Resource-Allocation Graph Algorithm

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

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

转化规则如下：

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

[!NOTE] 算法

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

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

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

否则进程必须等待

注意虚线的需求边也会参与 loop 的组成

Banker’s Algorithm

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

该算法新增 5 个数据结构

n = number of processes

m = number of resources types

Available [j]: Vector of length m.
- If Available [j] = k, then k instances of Rj available
Max: n x m matrix.
- If Max [i, j] = k, then process Pi may request at most k instances of Rj.
Allocation: n x m matrix.
- If Allocation [i, j] = k then Pi is currently allocated k instances of Rj
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]
Request：n x m matrix.

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

[!IMPORTANT] Safety Algorithm 安全算法

银行家算法首先需要一个安全算法，用于检测一个系统当前是否处于安全状态

Let Work and Finish be vectors of length m and n

1-Initialize

Work = Available 即当前空余资源总和

Finish [i] = false for i = 1,2,3, …, n

2-Allocate

Find an index i such that

Finish [i] = false

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

[!IMPORTANT] Safety Algorithm 安全算法

If Request [i] $\le$ Need [i], go to step 2.

Otherwise, raise error condition, since process has exceeded its maximum claim.

If Request [i] $\le$ Available, go to step 3.

Otherwise Pi must wait, since resources are not available.

Pretend to allocate requested resources to Pi:

Available = Available - Request [i];

Allocation [i] = Allocation [i] + Request [i];

Need [i] = Need [i] – Request [i]

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

[!EXAMPLE] 还没看

Review Questions

死锁
按序分配/按需分配/银行家算法

安全
不能

不安全？
没说

Deadlock Detection

Single Instance of Each Resource Type

使用 wait-for graph 等待图，是资源分配图的变形

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

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

[!EXAMPLE] res-alloc -> wait-for

Several Instances of a Resource Type

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

Available: A vector of length m
- indicates the number of available resources of each type.
Allocation: An n x m matrix
- defines the number of resources of each type currently allocated to each process.
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.

[!IMPORTANT] Detection Algorithm

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.

??????????????????????????????????????????????

[!EXAMPLE]