广东工业大学实验指导：理解操作系统的死锁理论与实践


参考资源链接：[广东工业大学 操作系统四个实验（报告+代码）](https://wenku.csdn.net/doc/6412b6b0be7fbd1778d47a07?spm=1055.2635.3001.10343)
# 1. 操作系统死锁的基本概念

## 死锁的定义
死锁是多个进程在执行过程中因争夺资源而造成的一种僵局，当进程处于此状态时，它们将无限期地等待其他进程释放资源。这种现象的发生，严重时将导致系统整体功能的停止。

## 死锁的四个必要条件
为了系统发生死锁，必须同时满足以下四个条件：
1. **互斥条件**：至少有一个资源必须处于非共享模式，即一次只有一个进程可以使用。如果另一个进程请求该资源，请求者只能等待直到资源被释放。
2. **持有和等待条件**：一个进程至少持有一个资源，并且正在等待获取其他进程持有的附加资源。
3. **非抢占条件**：资源只能由占有它的进程释放；不能被强行从占有它的进程那里抢占。
4. **循环等待条件**：存在一种进程资源的循环链，每个进程都至少持有一个链中下一个进程所需要的资源。

理解死锁的基本概念是预防和避免死锁的第一步。在接下来的章节中，我们将进一步探讨死锁的理论基础、预防策略、检测与恢复以及在实验中的应用实践。

# 2. ```
# 第二章：死锁的理论基础

死锁是操作系统中一种常见而又复杂的问题，涉及到多进程资源竞争以及互斥使用。为了更好地理解死锁及其预防、避免和解决策略，本章将深入探讨死锁的理论基础，包括死锁的定义、条件、预防策略以及避免算法。通过这些理论知识的学习，我们可以构建一个更稳定、更高效的系统环境。

## 2.1 死锁的定义和条件

### 2.1.1 死锁的定义

死锁（Deadlock）是指两个或两个以上的进程，在执行过程中，因争夺资源而造成一种僵局。当进程处于这种状态时，它们将无限期地阻塞等待，无法向前推进。死锁可以发生在任何需要共享资源的环境中，包括操作系统、数据库管理系统、分布式系统以及网络协议等。

### 2.1.2 死锁的四个必要条件

为了形成死锁，必须同时满足以下四个条件：

- **互斥条件**：至少有一个资源必须处于非共享模式，即一次只有一个进程可以使用。如果另一个进程请求该资源，请求者只能等待直到资源被释放。
- **持有并等待条件**：一个进程至少持有一个资源，并且正在等待获取其他进程持有的额外资源。
- **非抢占条件**：资源不能被强行从一个进程中抢夺，只能由进程在使用完毕后自愿释放。
- **循环等待条件**：存在一种进程资源的循环等待链，每个进程持有下一个进程所需要的至少一个资源。

## 2.2 死锁的预防策略

### 2.2.1 预防死锁的资源分配策略

预防死锁的最简单和最直接的方法是破坏死锁发生的四个必要条件中的至少一个。常见的预防策略包括：

- **破坏互斥条件**：尽可能使资源能够被共享，或者通过设计，使它们不会引起冲突。
- **破坏持有并等待条件**：一次性地申请所有需要的资源，否则进程将不会开始执行。
- **破坏非抢占条件**：允许系统抢占已分配给进程的资源。如果一个新请求的资源无法立即分配给进程，则现有资源可被抢占，以供其他进程使用。
- **破坏循环等待条件**：对所有资源类型进行排序，并强制进程按照一定的顺序请求资源。

### 2.2.2 死锁预防的系统设计

除了上述策略之外，还可以通过系统设计来预防死锁。例如：

- **资源分配图分析**：通过构建资源分配图来监测系统中是否存在循环等待。如果检测到循环等待，系统可以采取措施来打破循环。
- **资源请求限制**：设计系统时可以限制资源请求的方式，避免持有并等待条件的发生。

## 2.3 死锁的避免算法

### 2.3.1 银行家算法原理和实现

银行家算法是一种避免死锁的算法，它模拟了银行家的贷款策略，即在分配资源前检查这是否会导致系统进入不安全状态。如果分配后系统处于安全状态，则可以分配；否则，进程必须等待。

银行家算法涉及到几个关键数据结构：

- `Available`：表示每种资源类型的可用数量。
- `Max`：每个进程可能请求的最大资源数量。
- `Allocation`：每个进程当前已分配的资源数量。
- `Need`：每个进程还需要的资源数量。

算法的执行逻辑：

1. 当进程请求资源时，检查`Request`是否小于等于`Need`，如果是，则继续；否则，报告错误。
2. 检查`Request`是否小于等于`Available`，如果满足，则尝试分配资源，并更新`Available`，`Allocation`和`Need`。
3. 执行安全算法检查系统是否处于安全状态。如果处于安全状态，分配资源；否则，拒绝分配请求并让进程等待。

代码示例：

def is_safe_state(available, max, allocation, need):
    work = list(available)
    finish = [False] * len(allocation)
    while True:
        found = False
        for i, (alloc, req) in enumerate(zip(allocation, need)):
            if not finish[i] and all(req[j] <= work[j] for j in range(len(work))):
                for k in range(len(work)):
                    work[k] += alloc[k]
                finish[i] = True
                found = True
        if not found:
            break
    return all(finish)

# 示例数据
available = [10, 5, 7]
max = [[7, 5, 3], [3, 2, 2]]
allocation = [[0, 1, 0], [2, 0, 0]]
need = [[7, 4, 3], [1, 2, 2]]

# 检查是否可以安全分配
request = [3, 3, 3]
if is_safe_state(available, max, allocation, need):
    # 分配资源并更新
    ...
else:
    print("拒绝分配，不安全！")

### 2.3.2 死锁避免的其他算