进程同步与死锁

本文档旨在总结操作系统中关于进程同步与死锁的核心概念，基于陈亮老师《操作系统》课程第七讲“同步”与第八讲“并发: 死锁、饥饿”的PPT内容。

学习目标

• 理解并发执行中数据不一致性与竞争条件。
• 掌握临界区问题的概念及其解决方案的要求。
• 学习并比较多种同步机制：Peterson算法、硬件同步（中断禁用、原子指令）、互斥锁、信号量、管程和条件变量。
• 分析经典的同步问题：生产者-消费者、读者-写者、哲学家就餐。
• 理解死锁的定义、产生的四个必要条件。
• 掌握死锁处理的三种主要方法：预防、避免、检测与恢复。
• 学习资源分配图、安全状态、银行家算法等死锁相关概念与算法。

---

第七讲 — 同步 (Synchronization)

1. 背景与概述

在多道程序设计、多处理器及分布式处理环境中，多个进程或线程可能并发甚至并行执行。当这些并发实体访问共享数据时，若无适当控制，可能导致数据不一致性。

竞争条件 (Race Condition)

当多个进程并发访问和操作同一共享数据，并且最终的执行结果与特定访问顺序有关时，就称之为发生了竞争条件。竞争条件是不确定的，可能导致程序错误，是操作系统和并发编程中需要着重解决的问题。

与并发相关的关键术语 (Slide 30):

• 原子操作 (Atomic operation): 一个或一系列不可中断的操作。
• 临界区 (Critical section): 访问共享资源的代码段，一次只允许一个进程进入。
• 死锁 (Deadlock): 两个或多个进程无限期地等待一个只有该组中其他等待进程才能释放的事件。
• 活锁 (Livelock): 进程状态不断改变，但无法向前推进。
• 互斥 (Mutual exclusion): 当一个进程在临界区访问共享资源时，其他进程不能进入该临界区。
• 竞争条件 (Race condition): 如上定义。
• 饥饿 (Starvation): 一个可运行的进程尽管能够继续执行，但被调度器无限期地忽略，无法获得CPU时间。

2. 临界区问题 (Critical Section Problem)

对于 \(n\) 个进程 \(\{P_0, P_1, \dots, P_{N-1}\}\)，每个进程中都包含一段访问共享资源的代码，称为临界区。

典型进程结构:

do {
    // 入口区 (Entry Section)
    // --- 临界区 (Critical Section) ---
    // 退出区 (Exit Section)
    // --- 剩余区 (Remainder Section) ---
} while (TRUE);

临界区问题解决方案需满足的要求

1. 互斥 (Mutual Exclusion): 如果进程 \(P_i\) 在其临界区内执行，则其他任何进程都不能在其临界区内执行。
2. 推进 (Progress): 如果没有进程在其临界区执行，并且存在一些希望进入其临界区的进程，那么选择下一个将进入临界区的进程不能被无限期推迟。
3. 有限等待 (Bounded Waiting): 在一个进程发出进入其临界区的请求后，到该请求被批准之前，其他进程允许进入其临界区的次数必须存在一个上限。

3. 同步解决方案

3.1 Peterson解决方案 (软件方案)

一个经典的基于软件的、针对两个进程的临界区问题解决方案，满足上述三个要求。它使用共享变量 turn 和 flag 数组。

// 针对进程 Pi
do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j); // 忙等待
    // --- 临界区 ---
    flag[i] = false;
    // --- 剩余区 ---
} while (true);

// 针对进程 Pj
do {
    flag[j] = true;
    turn = i;
    while (flag[i] && turn == i); // 忙等待
    // --- 临界区 ---
    flag[j] = false;
    // --- 剩余区 ---
} while (true);

3.2 硬件同步

a. 中断禁用

在单处理器系统中，通过在进入临界区前禁用中断，并在退出时启用中断，可以保证互斥。

• 缺点: 代价高，降低效率；不适用于多处理器系统。

b. 特殊原子指令

硬件提供一些特殊的原子指令（不可中断）。

• test_and_set() 指令:

  boolean test_and_set(boolean *target) {
      boolean rv = *target;
      *target = TRUE;
      return rv;
  }
  

  使用共享布尔变量 lock (初始化为 false):

  do {
      while (test_and_set(&lock)); // 忙等待
      // --- 临界区 ---
      lock = false;
      // --- 剩余区 ---
  } while (true);
  

• compare_and_swap() 指令:

  int compare_and_swap(int *value, int expected, int new_value) {
      int temp = *value;
      if (*value == expected)
          *value = new_value;
      return temp;
  }
  

  使用共享整型变量 lock (初始化为 0):

  do {
      while (compare_and_swap(&lock, 0, 1) != 0); // 忙等待
      // --- 临界区 ---
      lock = 0;
      // --- 剩余区 ---
  } while (true);
  

硬件指令的局限性

• 上述基本硬件指令方案满足互斥，但不直接满足有限等待。
• 存在忙等待，消耗CPU时间。
• 可能导致饥饿或死锁（若使用不当）。
• 对程序员直接使用而言较为复杂。

3.3 互斥锁 (Mutex Locks)

操作系统提供的简单软件工具，用于解决临界区问题。 核心操作：

• acquire(): 获取锁，若锁已被占用则等待。
• release(): 释放锁。

这两个操作必须是原子的，通常通过硬件原子指令实现。

mutex_lock L; // 声明一个互斥锁

do {
    acquire(&L);
    // --- 临界区 ---
    release(&L);
    // --- 剩余区 ---
} while (true);

如果 acquire() 实现为忙等待，则称为自旋锁 (Spinlock)。自旋锁在锁持有时间很短的多处理器系统中有优势（避免上下文切换开销）。

3.4 信号量 (Semaphores)

一个更强大的同步工具，是一个整数变量 \(S\)，只能通过两个原子操作访问：

• wait(S) (或 P(S)):

  wait(S) {
      while (S <= 0)
          ; // 忙等待 (或阻塞进程)
      S--;
  }
  

  当 \(S \le 0\) 时，进程等待。若 \(S > 0\)，则 \(S\) 减 1，进程继续。

• signal(S) (或 V(S)):

  signal(S) {
      S++;
  }
  

  \(S\) 加 1。如果有进程因 \(S \le 0\) 而等待，则唤醒其中一个。

类型:

• 计数信号量 (Counting Semaphore): 整数值可以不受限制（非负）。
• 二元信号量 (Binary Semaphore): 整数值只能是 0 或 1，功能类似互斥锁，但加锁和解锁的主体可以不同。

实现无忙等待的信号量: 通过将等待的进程放入一个与信号量关联的等待队列，并使用 block() 和 wakeup() 操作。

// 信号量定义
typedef struct {
    int value;
    struct process *list; // 等待队列
} semaphore;

// wait 操作
wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // add this process to S->list;
        block(); // 阻塞当前进程
    }
}

// signal 操作
signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // remove a process P from S->list;
        wakeup(P); // 唤醒一个等待进程
    }
}

信号量使用不当的风险

• signal(S) 后于 wait(S)：可能导致多个进程同时进入临界区。
• wait(S) 替换 signal(S)：可能导致死锁。
• 遗漏 wait(S) 或 signal(S)：破坏互斥或导致死锁。

3.5 管程 (Monitors)

一种高级语言结构，提供了与信号量类似的功能，但更易于控制。它将共享数据以及对这些数据的操作封装起来。

特点:

• 管程内部的局部变量只能由管程内的过程访问。
• 在任一时刻，管程中只能有一个进程处于活动状态，确保了对共享数据的互斥访问。
• 通过条件变量 (Condition Variables) 实现更复杂的同步。条件变量有两种主要操作：
  • x.wait(): 调用此操作的进程被挂起，并释放管程的互斥权，直到另一个进程对 x 调用 x.signal()。
  • x.signal(): 唤醒一个（如果有的话）因 x 而等待的进程。如果没有进程等待，则 signal 操作无效。

MESA管程模型 (Java采用):

当一个进程P执行 x.signal() 唤醒等待在条件变量 x 上的进程Q时：

• P继续执行，Q从条件等待队列移到入口等待队列。
• 当Q重新获得管程锁并执行时，之前 x.wait() 的条件可能已不再满足。因此，x.wait() 通常放在 while 循环中检查条件：

  while (!condition) {
      x.wait();
  }
  

4. 经典同步问题

a. 有界缓冲区 (生产者-消费者) 问题

• 共享数据: 大小为 \(n\) 的缓冲区。
• 信号量:
  • mutex: (二元信号量，初值为1) 控制对缓冲区的互斥访问。
  • empty: (计数信号量，初值为 \(n\)) 记录空缓冲槽位数。
  • full: (计数信号量，初值为0) 记录满缓冲槽位数。

生产者伪代码:

do {
    // ... 生产一个项目 item ...
    wait(empty);     // 等待空槽位
    wait(mutex);     // 进入临界区
    // ... 将 item 添加到缓冲区 ...
    signal(mutex);   // 离开临界区
    signal(full);    // 通知有满槽位
} while (true);

消费者伪代码:

do {
    wait(full);      // 等待满槽位
    wait(mutex);     // 进入临界区
    // ... 从缓冲区取出一个 item ...
    signal(mutex);   // 离开临界区
    signal(empty);   // 通知有空槽位
    // ... 消费 item ...
} while (true);

b. 读者-写者问题

多个进程共享数据，分为读者和写者：

• 读者: 只读取数据，不修改。
• 写者: 可读取和修改数据。

同步约束:

1. 允许多个读者同时读取。
2. 一次只允许一个写者访问共享数据。
3. 当写者在访问数据时，不允许任何读者访问。

读者优先方案 (可能导致写者饥饿):

• 共享数据:
  • read_count: (整数，初值为0) 当前读者数量。
• 信号量:
  • rw_mutex: (二元信号量，初值为1) 控制写者互斥，或第一个/最后一个读者进入/退出。
  • mutex: (二元信号量，初值为1) 保护 read_count 的更新。

写者伪代码:

do {
    wait(rw_mutex);
    // ... 进行写操作 ...
    signal(rw_mutex);
} while (true);

读者伪代码:

do {
    wait(mutex);
    read_count++;
    if (read_count == 1) { // 第一个读者
        wait(rw_mutex);    // 阻止写者
    }
    signal(mutex);

    // ... 进行读操作 ...

    wait(mutex);
    read_count--;
    if (read_count == 0) { // 最后一个读者
        signal(rw_mutex);   // 允许写者
    }
    signal(mutex);
} while (true);

c. 哲学家就餐问题

五个哲学家围坐圆桌，每人面前一碗饭，每两位哲学家之间放一只筷子。哲学家交替思考和吃饭。吃饭需要同时拿起左右两边的筷子。

问题: 如何设计协议，使得哲学家可以吃饭，且不会发生死锁或饥饿。

简单信号量方案 (可能导致死锁):

• chopstick[5]: 信号量数组，每个元素初值为1。

哲学家 \(i\) 伪代码:

do {
    // ... 思考 ...
    wait(chopstick[i]);             // 拿起左筷子
    wait(chopstick[(i + 1) % 5]);   // 拿起右筷子
    // ... 吃饭 ...
    signal(chopstick[i]);             // 放下左筷子
    signal(chopstick[(i + 1) % 5]);   // 放下右筷子
} while (true);

如果所有哲学家同时拿起左筷子，则都会等待右筷子，导致死锁。

无死锁解决方案包括:

1. 最多允许四位哲学家同时坐在桌上。
2. 仅当哲学家的两根筷子都可用时，才允许他拿起它们（在临界区内完成）。
3. 非对称解决方案：奇数号哲学家先拿左筷子再拿右筷子，偶数号哲学家先拿右筷子再拿左筷子。
4. 使用管程。

---

第八讲 — 并发: 死锁、饥饿 (Deadlock & Starvation)

1. 死锁 (Deadlock)

死锁定义

当一组进程中的每个进程都在等待某个事件（通常是获取资源），而这个事件只能由该组中其他被阻塞的进程触发时，这组进程就发生了死锁。死锁是永久性的，涉及两个或多个进程对资源的冲突需求。

资源分类:

• 可重用资源 (Reusable Resource): 一次只能被一个进程安全使用，并且不会因使用而耗尽（如CPU、内存、磁盘驱动器、锁）。
• 可消耗资源 (Consumable Resource): 可以被创建（生产）和销毁（消费）的资源（如消息、信号、中断）。

进程使用资源顺序: 申请 (Request) -> 使用 (Use) -> 释放 (Release)

2. 死锁的必要条件

死锁的发生必须同时满足以下四个条件：

死锁的四个必要条件

1. 互斥 (Mutual Exclusion): 至少有一个资源必须以非共享模式持有，即一次只有一个进程可以使用。
2. 持有并等待 (Hold and Wait): 一个进程必须至少持有一个资源，并正在等待获取其他进程当前持有的额外资源。
3. 无抢占 (No Preemption): 资源不能被抢占；即，资源只能在持有它的进程完成任务后自愿释放。
4. 循环等待 (Circular Wait): 必须存在一组等待进程 \(\{P_0, P_1, \dots, P_n\}\)，使得 \(P_0\) 等待 \(P_1\) 持有的资源，\(P_1\) 等待 \(P_2\) 持有的资源，...，\(P_{n-1}\) 等待 \(P_n\) 持有的资源，而 \(P_n\) 等待 \(P_0\) 持有的资源。

3. 资源分配图 (Resource-Allocation Graph)

一种有向图，用于描述进程和资源之间的分配和请求关系。

• 节点: 进程节点 (圆圈 \(P_i\)) 和资源类型节点 (方框 \(R_j\)，方框内的点表示该类型资源的实例数)。
• 边:
  • 请求边 (Request Edge): 从进程 \(P_i\) 指向资源类型 \(R_j\) (\(P_i \to R_j\))，表示 \(P_i\) 请求 \(R_j\) 的一个实例。
  • 分配边 (Assignment Edge): 从资源类型 \(R_j\) 的一个实例指向进程 \(P_i\) (\(R_j \to P_i\))，表示 \(R_j\) 的一个实例已分配给 \(P_i\)。

资源分配图与死锁:

• 如果图中没有环： 系统一定没有死锁。
• 如果图中有环：
  • 若每种资源类型只有一个实例，则环的存在必然导致死锁。
  • 若每种资源类型有多个实例，则环的存在可能导致死锁。

4. 处理死锁的方法

1. 死锁预防 (Deadlock Prevention): 通过破坏死锁发生的四个必要条件之一来确保系统永远不会进入死锁状态。
2. 死锁避免 (Deadlock Avoidance): 系统在分配资源前，根据额外信息（如进程未来可能请求的最大资源量）判断此次分配是否会导致系统进入不安全状态，从而避免死锁。
3. 死锁检测与恢复 (Deadlock Detection and Recovery): 允许系统进入死锁状态，然后通过算法检测它，并采取措施恢复。
4. 忽略该问题: 假装系统中从未发生死锁。这是许多通用操作系统（如Windows、Linux）采用的方法，因为死锁发生概率较低，而预防或避免的代价较高。

5. 死锁预防策略

通过破坏四个必要条件之一：

• 破坏互斥: 对于可共享资源（如只读文件）可以，但对于本身不可共享的资源则不行。通常不能否定。
• 破坏持有并等待:
  • 策略1: 进程开始执行前，必须一次性请求并获得其所需的所有资源。
  • 策略2: 进程只有在不持有任何资源时，才允许请求资源。
  • 缺点: 资源利用率低；可能导致饥饿。
• 破坏无抢占:
  • 如果一个持有资源的进程请求另一个不能立即分配的资源，则它当前持有的所有资源都被隐式释放（被抢占）。
  • 或者，当进程P请求资源R时，如果R被进程Q持有，而Q又在等待其他资源，则可以抢占Q的资源R分配给P。
  • 缺点: 实现复杂，可能需要保存和恢复状态。
• 破坏循环等待:
  • 对所有资源类型进行完全排序，并要求每个进程按递增顺序请求资源。例如，若资源类型排序为 \(R_1 < R_2 < \dots < R_m\)，进程若持有 \(R_i\)，则下次只能请求 \(R_j\) 使得 \(j > i\)。
  • 缺点: 资源编号困难，可能不符合进程实际需求顺序。

6. 死锁避免策略

要求系统具有关于进程未来资源需求的先验信息。

安全状态 (Safe State)

如果系统可以按照某个顺序（称为安全序列 \(<P_1, P_2, \dots, P_n>\)）为每个进程分配资源（最多达到其声明的最大需求量），并且能避免死锁，则称系统处于安全状态。 具体来说，对于序列中的每个进程 \(P_i\)，它仍然可以请求的资源数量可以通过当前可用资源加上所有在它之前的进程 \(P_j (j < i)\) 持有的资源来满足。

• 安全状态 \(\implies\) 无死锁。
• 不安全状态 \(\implies\) 可能导致死锁。死锁避免算法确保系统永远不会进入不安全状态。

a. 资源分配图算法 (单实例资源)

• 引入需求边 (Claim Edge) \(P_i \dashrightarrow R_j\)，表示进程 \(P_i\) 将来可能请求资源 \(R_j\)。
• 当 \(P_i\) 实际请求 \(R_j\) 时，需求边变为请求边 \(P_i \to R_j\)。
• 当资源 \(R_j\) 分配给 \(P_i\) 时，请求边变为分配边 \(R_j \to P_i\)。
• 当 \(P_i\) 释放 \(R_j\) 时，分配边变回需求边。
• 分配决策: 只有当请求边转换为分配边后，图中不形成环路时，才允许分配。环路检测用于判断安全性。

b. 银行家算法 (多实例资源)

适用于每种资源类型有多个实例的系统。每个进程必须预先声明它可能需要的每种资源类型的最大数量。

数据结构 (设 \(n\) 个进程, \(m\) 种资源):

• Available[m]: 长度为 \(m\) 的向量。Available[j] = k 表示资源类型 \(R_j\) 有 \(k\) 个可用实例。
• Max[n][m]: \(n \times m\) 矩阵。Max[i][j] = k 表示进程 \(P_i\) 最多需要 \(k\) 个 \(R_j\) 实例。
• Allocation[n][m]: \(n \times m\) 矩阵。Allocation[i][j] = k 表示 \(P_i\) 当前已分配 \(k\) 个 \(R_j\) 实例。
• Need[n][m]: \(n \times m\) 矩阵。Need[i][j] = k 表示 \(P_i\) 还需 \(k\) 个 \(R_j\) 实例才能完成任务。 \(Need[i][j] = Max[i][j] - Allocation[i][j]\)

1. 安全性算法 (Safety Algorithm):

判断当前系统状态是否安全。

1. 初始化 Work[m] = Available，Finish[n] (布尔数组) Finish[i] = false for all \(i\).
2. 查找一个进程 \(P_i\) 满足: (a) Finish[i] == false (b) \(Need_i \le Work\) (其中 \(Need_i\) 是 Need 矩阵的第 \(i\) 行) 如果没有这样的 \(P_i\)，转到步骤 4。
3. Work = Work + Allocation_i (其中 \(Allocation_i\) 是 Allocation 矩阵的第 \(i\) 行) Finish[i] = true 返回步骤 2。
4. 如果对所有 \(i\)，Finish[i] == true，则系统处于安全状态。否则，不安全。

2. 资源请求算法 (Resource-Request Algorithm):

当进程 \(P_i\) 请求资源时 (设请求向量为 \(Request_i\)):

1. 如果 \(Request_i \le Need_i\)，转到步骤 2。否则，出错 (请求超过最大声明)。
2. 如果 \(Request_i \le Available\)，转到步骤 3。否则，\(P_i\) 必须等待 (资源不足)。
3. 假装分配资源给 \(P_i\): Available = Available - Request_i Allocation_i = Allocation_i + Request_i Need_i = Need_i - Request_i
4. 调用安全性算法检查新状态是否安全。
   • 如果安全，则实际分配资源给 \(P_i\)。
   • 如果不安全，\(P_i\) 必须等待，并恢复到第3步之前的状态。

7. 死锁检测

允许系统进入死锁状态，然后定期运行检测算法。

a. 单实例资源类型的等待图 (Wait-for Graph)

• 如果每种资源类型只有一个实例，可以构建等待图。
• 节点是进程。
• 从 \(P_i \to P_j\) 的边表示 \(P_i\) 正在等待 \(P_j\) 释放其所需的资源。
• 图中存在环 \(\iff\) 系统存在死锁。

b. 多实例资源类型的检测算法

类似银行家算法的安全性算法，但不使用 Max 或 Need。

1. 初始化 Work[m] = Available，Finish[n]。如果 Allocation_i 非零，则 Finish[i] = false；否则 Finish[i] = true (已完成或未开始的进程不参与死锁)。
2. 查找一个进程 \(P_i\) 满足: (a) Finish[i] == false (b) \(Request_i \le Work\) (其中 \(Request_i\) 是 \(P_i\) 当前的请求向量) 如果没有这样的 \(P_i\)，转到步骤 4。
3. Work = Work + Allocation_i Finish[i] = true 返回步骤 2。
4. 如果存在某个 \(i\) 使得 Finish[i] == false，则系统处于死锁状态，且所有 Finish[i] == false 的进程 \(P_i\) 都是死锁进程。

检测算法的调用时机:

• 死锁发生频率？
• 检测代价？
• 可以周期性调用，或当CPU利用率低于某个阈值时调用。

8. 死锁恢复

• 终止进程:
  • 终止所有死锁进程 (代价大)。
  • 一次终止一个进程，直到死锁环被打破。选择终止哪个进程基于代价最小原则（如优先级、已用CPU时间、预计剩余时间、已分配资源量等）。
• 资源抢占:
  • 逐步从一个或多个死锁进程中抢占资源分配给其他进程，直到死锁环被打破。
  • 选择牺牲者 (Victim Selection): 基于最小代价。
  • 回滚 (Rollback): 被抢占资源的进程需要回滚到某个安全状态并重新启动。
  • 饥饿 (Starvation): 确保同一进程不会总是被选为牺牲者（可在代价中计入回滚次数）。

评论