操作系统原理之死锁 #

目录 #

死锁的介绍 #

操作系统中的一个进程以下列方式使用资源：

• 请求一个资源
• 使用该资源
• 释放该资源

死锁是（Deadlock）指一组进程被阻塞的情况，因为每个进程都持有一个资源并等待其他进程以获得的另一个资源。考虑一个例子，当两辆火车在同一条轨道上向对方驶去，而只有一条轨道，一旦它们在碰面，没有一辆火车可以移动。类似的情况也发生在操作系统中，当有两个或更多的进程持有一些资源并等待其他进程持有的资源时。例如，在下图中，进程 1 持有资源 1，并等待由进程 2 获得的资源 2，而进程 2 正在等待资源 1。

如果以下四个条件同时成立，就会出现死锁（必要条件，Necessary Conditions）：

• 相互排斥（Mutual Exclusion）。两个或多个资源是不可共享（non-shareable）的（每次只有一个进程可以使用）
• 持有并等待（Hold and Wait）：一个进程至少持有一个资源并等待资源。
• 不抢占（No Preemption）。除非进程释放资源，否则不能从该进程中获取资源。
• 循环等待（Circular Wait）：一组进程以循环形式互相等待。

处理死锁的方法：

有三种处理死锁的方法。

• 预防或避免死锁。我们的想法是不要让系统进入死锁状态。我们可以单独放大每个类别，预防（Prevention）是通过否定上述死锁的必要条件之一来实现的。 避免（Avoidance）是一种未来主义（futuristic）的性质。通过使用 "避免" 的策略，我们必须做出一个假设。我们需要确保在执行进程之前，所有关于进程所需资源的信息都是我们知道的。我们使用 Banker 算法（Banker’s algorithm）以避免僵局。

• 死锁检测（detection）和恢复（recovery）。允许死锁发生，一旦发生，就进行抢占（preemption）处理。

• 完全忽略这个问题。如果死锁非常罕见，那么就让它发生并重启系统。这是 Windows 和 UNIX 都采取的方法。

参考：

• Operating Systems: Deadlocks

死锁避免 #

如果一个系统没有采用预防死锁或避免死锁的算法，那么就可能出现死锁情况。在这种情况下：

• 应用一种算法来检查系统的状态，以确定死锁是否已经发生。
• 应用一种算法从死锁中恢复。

死锁避免算法 #

死锁避免算法（Deadlock Avoidance Algorithm）/ 银行家算法（Bankers Algorithm）：

该算法采用了若干次不同的数据结构：

• 可用的（Available）：一个长度为 m 的向量表示每种类型的可用资源的数量。
• 分配（Allocation）：一个 n*m 矩阵定义了当前分配给进程的每种类型的资源数量。列代表资源，行代表进程。
• 请求（Request）：一个 n*m 的矩阵表示每个进程的当前请求。如果 request [i][j] 等于 k，那么进程 Pi 正在请求 Rj 类型资源的 k 个实例。

现在，Bankers 算法包括一个安全算法（Safety Algorithm）/ 死锁检测算法（Deadlock Detection Algorithm）。找出系统是否处于安全状态的算法可以描述如下：

算法的步骤：

• 让 Work 和 Finish 分别为长度为 m 和 n 的向量。初始化 Work=Available 。对于 i=0, 1, ...., n-1 ，如果 Request(i)=0 ，则 Finish[i] = true ；否则， Finish[i]= false 。
• 找到一个索引 i，使其同时 Finish[i] == false 、 Request(i) <= Work ，如果不存在这样的 i，则进入第 4 步。
• Work= Work+ Allocation(i) ， Finish[i]= true ，转到第 2 步。
• 如果对于某些 i Finish[i]== false ，其中 0<=i<n ，那么系统就处于死锁状态（deadlocked state）。此外，如果 Finish[i]==false ，进程 Pi 就处于死锁状态。

例如：

1. 在此例中，Work = [0, 0, 0] & Finish = [false, false, false, false, false]
2. i=0 被选择当同时满足 Finish [0] = false 和 [0, 0, 0]<=[0, 0, 0] 时。
3. Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] & Finish = [true, false, false, false, false].
4. i=2 被选择当同时满足 Finish [2] = false 和 [0, 0, 0]<=[0, 1, 0] 时。
5. Work =[0, 1, 0]+[3, 0, 3] =>[3, 1, 3] & Finish = [true, false, true, false, false].
6. i=1 被选择当同时满足 Finish [1] = false 和 [2, 0, 2]<=[3, 1, 3] 时。
7. Work =[3, 1, 3]+[2, 0, 0] =>[5, 1, 3] & Finish = [true, true, true, false, false].
8. i=3 被选择当同时满足 Finish [3] = false 和 [1, 0, 0]<=[5, 1, 3] 时。
9. Work =[5, 1, 3]+[2, 1, 1] =>[7, 2, 4] & Finish = [true, true, true, true, false].
10. i=4 被选择当同时满足 Finish [4] = false 和 [0, 0, 2]<=[7, 2, 4] 时。
11. Work =[7, 2, 4]+[0, 0, 2] =>[7, 2, 6] & Finish = [true, true, true, true, true].
12. 由于 Finish 是一个全部为真的向量，这意味着在这个例子中没有死锁。

银行家算法 #

银行家算法（Banker’s algorithm）是一种资源分配（resource allocation）和避免死锁的算法（deadlock avoidance algorithm）。该算法测试安全，模拟所有资源的预定最大可能数量的分配，然后进行 "s-state" 检查（an “s-state” check）以测试可能的活动，然后决定是否允许继续分配。

简单地说，它检查任何资源的分配是否会导致死锁，或者将资源分配给一个进程是否安全，如果不安全，则不将资源分配给该进程。确定一个安全序列（safe sequence）（即使只有一个）将确保系统不会进入死锁。

银行家算法通常被用来寻找是否存在安全序列（safe sequence）。但在这里我们将确定安全序列的总数并打印所有的安全序列。

所用的数据结构是：

• Available vector
• Max Matrix
• Allocation Matrix
• Need Matrix

银行家算法示例 #

示例：

Output: Safe sequences are:
P2--> P4--> P1--> P3
P2--> P4--> P3--> P1
P4--> P2--> P1--> P3
P4--> P2--> P3--> P1

There are total 4 safe-sequences 

解释:

Total resources 为 R1 = 10, R2 = 5, R3 = 7， allocated resources 为 R1 = (0+2+3+2 =) 7, R2 = (1+0+0+1 =) 2, R3 = (0+0+2+1 =) 3. 因此，remaining resources 为 R1 = (10 – 7 =) 3, R2 = (5 – 2 =) 3, R3 = (7 – 3 =) 4.

• Remaining available = Total resources – allocated resources
• Remaining need = max – allocated

因此，我们可以从 P2 或 P4 开始。在银行家算法的第一或第二尝试步骤中，我们无法从 P1 或 P3 的可用资源中满足剩余需求。只有四个可能的安全序列为：

P2--> P4--> P1--> P3 
P2--> P4--> P3--> P1 
P4--> P2--> P1--> P3 
P4--> P2--> P3--> P1

银行家算法实现 #

Python 实现：

# Python3 program to print all
# possible safe sequences
# using banker's algorithm

# Total number of process
P = 4

# Total number of resources
R = 3

# Total safe-sequences
total = 0

# Function to check if process
# can be allocated or not
def is_available(process_id, allocated,
    max, need, available):
     
 flag = True

 # Check if all the available resources
 # are less greater than need of process
 for i in range(R):
  if (need[process_id][i] > available[i]):
   flag = False

 return flag

# Print all the safe-sequences
def safe_sequence(marked, allocated,
    max, need, available, safe):
 
 global total, P, R
 
 for i in range(P):
  
  # Check if it is not marked
  # already and can be allocated
  if (not marked[i] and
   is_available(i, allocated, max,
      need, available)):
       
   # mark the process
   marked[i] = True

   # Increase the available
   # by deallocating from process i
   for j in range(R):
    available[j] += allocated[i][j]

   safe.append(i)
   
   # Find safe sequence by taking process i
   safe_sequence(marked, allocated, max,
      need, available, safe)
   safe.pop()

   # unmark the process
   marked[i] = False

   # Decrease the available
   for j in range(R):
    available[j] -= allocated[i][j]
  
 # If a safe-sequence is found, display it
 if (len(safe) == P):
  total += 1
  
  for i in range(P):
   print("P" + str(safe[i] + 1), end = '')
   
   if (i != (P - 1)):
    print("--> ", end = '')
   
  print()

# Driver code 
if __name__=="__main__":
 
 # Allocated matrix of size P*R
 allocated = [ [ 0, 1, 0 ],
    [ 2, 0, 0 ],
    [ 3, 0, 2 ],
    [ 2, 1, 1 ]]

 # max matrix of size P*R
 max = [ [ 7, 5, 3 ],
   [ 3, 2, 2 ],
   [ 9, 0, 2 ],
   [ 2, 2, 2 ] ]

 # Initial total resources
 resources = [ 10, 5, 7 ]

 # Available vector of size R
 available = [0 for i in range(R)]
 
 for i in range(R):
  sum = 0
  
  for j in range(P):
   sum += allocated[j][i]

  available[i] = resources[i] - sum
 

 # Safe vector for displaying a
 # safe-sequence
 safe = []

 # Marked of size P for marking
 # allocated process
 marked = [False for i in range(P)]

 # Need matrix of size P*R
 need = [[0 for j in range(R)]
   for i in range(P)]
 
 for i in range(P):
  for j in range(R):
   need[i][j] = (max[i][j] -
     allocated[i][j])
 
 print("Safe sequences are:")
 
 safe_sequence(marked, allocated, max,
    need, available, safe)
 
 print("\nThere are total " + str(total) +
  " safe-sequences")

JavaScript 实现：

<script>
 
let n, m, i, j, k;
n = 5; // Number of processes
m = 3; // Number of resources
let alloc = [ [ 0, 1, 0 ], // P0 // Allocation Matrix
    [ 2, 0, 0 ], // P1
    [ 3, 0, 2 ], // P2
    [ 2, 1, 1 ], // P3
    [ 0, 0, 2 ] ]; // P4

let max = [ [ 7, 5, 3 ], // P0 // MAX Matrix
   [ 3, 2, 2 ], // P1
   [ 9, 0, 2 ], // P2
   [ 2, 2, 2 ], // P3
   [ 4, 3, 3 ] ]; // P4

let avail = [ 3, 3, 2 ]; // Available Resources

let f = [], ans = [], ind = 0;
for (k = 0; k < n; k++) {
 f[k] = 0;
}
let need = [];
for (i = 0; i < n; i++) {
 let need1 = [];
 for (j = 0; j < m; j++)
 need1.push(max[i][j] - alloc[i][j]);
 need.push(need1);
}

let y = 0;
for (k = 0; k < 5; k++) {
 for (i = 0; i < n; i++) {
 if (f[i] == 0) {

  let flag = 0;
  for (j = 0; j < m; j++) {
  if (need[i][j] > avail[j]){
   flag = 1;
   break;
  }
  }

  if (flag == 0) {
  ans[ind++] = i;
  for (y = 0; y < m; y++)
   avail[y] += alloc[i][y];
  f[i] = 1;
  }
 }
 }
}

document.write("Following is the SAFE Sequence" + "<br>");
for (i = 0; i < n - 1; i++)
 document.write(" P" + ans[i] + " ->");
document.write( " P" + ans[n - 1] + "<br>");
</script>

银行家算法演示 #

视频演示：

单一资源的银行家算法：

多资源的银行家算法：

参考：

• Banker's Algorithm in Operating System - GeeksforGeeks

死锁检测和恢复 #

死锁检测（Deadlock Detection）:

在这种情况下，对于死锁检测，我们可以运行一个算法来检查资源分配图（Resource Allocation Graph）中的周期（cycle）。图中存在的循环是死锁的充分条件：

在上图中，资源 1 和资源 2 有单个实例。有一个 R1→P1→R2→P2 的循环。所以，死锁被确认。

如果有多个资源实例：

循环检测（Detection of the cycle）是死锁检测的必要条件，但不是充分条件，在这种情况下，系统可能处于死锁，也可能不处于死锁，根据不同的情况而有所不同。

死锁恢复（Deadlock Recovery）：

传统的操作系统如 Windows 不处理死锁恢复，因为它是一个耗费时间和空间的过程。实时操作系统使用死锁恢复。

• 杀死进程（Killing the process）：杀死所有参与死锁的进程。一个接一个地杀死进程，在杀死每个进程后，再次检查死锁，不断重复这个过程，直到系统从死锁中恢复过来。逐一杀死所有进程有助于系统打破循环等待条件。
• 资源抢占（Resource Preemption）：从涉及死锁的进程中抢占资源，抢占的资源被分配给其他进程，这样就有可能将系统从死锁中恢复。在这种情况下，系统会进入饥饿状态（starvation）。

死锁的预防和避免 #

死锁的特点：

• 相互排斥（Mutual Exclusion）
• 保持和等待（Hold and Wait）
• 没有抢占（No preemption）
• 循环等待（Circular wait）

预防死锁：我们可以通过消除上述四个条件中的任何一个来防止死锁。

破坏相互排斥的条件：不可能消除互斥，因为有些资源，如磁带机和打印机，本来就是不可共享的。

破坏保持和等待的条件：

• 在进程开始执行之前，将所有需要的资源分配给进程，这种方式消除了保持和等待的条件，但会导致设备利用率低。例如，如果一个进程在稍后的时间需要打印机，而我们在它开始执行之前已经分配了打印机，那么打印机将保持阻塞状态直到它完成执行。
• 进程将在释放当前的资源集后对资源进行新的请求。这种解决方案可能会导致饥饿。

破坏无抢占的条件：当其他高优先级进程需要资源时，抢占该进程的资源。

消除循环等待的条件：每个资源将被分配一个数字编号。进程可以要求增加 / 减少资源，并按照编号顺序。例如，如果 P1 进程被分配了 R5 资源，那么下次如果 P1 要求 R4、R3 小于 R5 的资源，这样的请求将不会被批准，只有大于 R5 的资源请求会被批准。

死锁避免：死锁的避免可以通过银行家算法来完成。

银行家算法：银行家算法是一种资源分配和避免死锁的算法，它测试所有进程对资源的请求，它检查安全状态，如果满足资源请求后系统仍处于安全状态，则允许请求，如果没有安全状态（路径），则不允许进程的请求。

银行家算法的输入：

• 每个进程对资源的最大需求（Max need of resources）。
• 目前，每个进程所分配的资源（allocated resources）。
• 系统中最大的可用资源（Max free available resources）。

只有在以下条件下，该请求才会被批准：

• 如果进程提出的请求小于等于该进程的最大需求。
• 如果进程提出的请求小于等于系统中可自由使用的资源。

注意：死锁预防（Deadlock prevention）比死锁避免（Deadlock Avoidance）更严格。

资源分配图（RAG） #

什么是 RAG #

正如银行家算法使用某种表格，如分配（allocation）、请求（request）、可用资源（available）等来理解系统的状态是什么。同样的，如果你想了解系统的状态，而不是使用这些表格，你就可以用图来表示相同的信息。该图被称为资源分配图（RAG，Resource Allocation Graph）。

所以，资源分配图向我们解释了系统在进程和资源方面的状态是什么。比如有多少资源可用，有多少资源被分配，每个进程的请求是什么。一切都可以用图来表示。图的好处之一是，有时通过使用 RAG 可以直接看到死锁，但你可能无法通过看表知道。如果系统包含大量的进程和资源，表格就比较好，如果系统包含较少的进程和资源，图就比较好。

我们知道，任何图形都包含顶点（vertices）和边（edges）。因此，RAG 也包含顶点和边。在 RAG 中，顶点有两种类型：

• 进程顶点（Process vertex）：每个进程都将被表示为一个进程顶点。
• 资源顶点（Resource vertex）：每个资源将被表示为一个资源顶点。它也有两种类型。
  • 单实例类型资源（Single instance type resource ）：它表示为一个方框，在方框内将有一个点，点的数量表示每种资源类型有多少实例。
  • 多实例类型资源（Multi-resource instance type resource）：它也表示为一个框，里面会有许多点存在。

现在来看看 RAG 的边。RAG 中有两种类型的边：

• 分配边（Assign Edge） - 如果你已经为一个流程分配了资源，那么它就被称为分配边。
• 请求边（Request Edge） - 这意味着在未来进程可能需要一些资源来完成执行，这被称为请求边。

如果一个进程正在使用一个资源，一个箭头将从资源节点画到进程节点。如果一个进程正在请求一个资源，则一个箭头将从进程节点画到资源节点。

单实例 RAG 示例 #

如果在资源分配图中存在一个循环，并且循环中的每个资源只提供一个实例，那么进程将处于死锁状态。例如，如果进程 P1 持有资源 R1，进程 P2 持有资源 R2，并且进程 P1 正在等待 R2，进程 P2 正在等待 R1，那么进程 P1 和进程 P2 将处于死锁状态。

下面是另一个例子，显示资源 R1 和 R2 分别分配给进程 P1 和 P2，而进程 P3 正在等待获取两个资源。在这个例子中，不存在死锁，因为不存在循环依赖。所以在单实例资源类型中，循环是死锁的充分条件。

多实例 RAG 示例 #

从上面的例子来看，不可能说 RAG 处于安全状态或不安全状态。所以为了看到这个 RAG 的状态，让我们构建分配矩阵（allocation matrix）和请求矩阵（request matrix）。

进程总数为三个：P1、P2 和 P3，资源总数为两个：R1 和 R2。

分配矩阵：为了构建分配矩阵，只需去看资源，看它被分配到哪个进程。R1 被分配给 P1，因此在分配矩阵中写 1，同样，R2 被分配给 P2 和 P3，剩下的元素写 0 即可。

请求矩阵：为了找出请求矩阵，你必须到进程中去看看出站（outgoing）的边。P1 正在请求 R2 资源，所以在矩阵中写 1，同样，P2 请求 R1，其余元素写 0。

所以现在可用的资源是 =（0，0）。

检查死锁（安全与否）：

因此，在这个 RAG 中不存在死锁。即使存在循环，也不存在死锁。因此，在多实例资源中，循环不是死锁的充分条件。

上面的例子与前面的例子相同，只是进程 P3 请求资源 R1。因此，表格变成如下所示。

所以，可用资源 =（0，0），但需求是（0，1），（1，0）和（1，0）。因此，你不能满足任何一个需求。

因此，多实例资源类型图中的每个循环都不一定是死锁，但是如果有死锁，就必须有循环。因此，在多实例资源类型的 RAG 中，循环是死锁的必要条件，但不是充分条件。