OS-04 进程同步与死锁

一、同步与互斥的基本概念

当多个进程并发执行时，它们之间可能产生相互影响。这种影响分为两类：同步和互斥。

同步（Synchronization）：多个进程在执行顺序上需要遵循一定的约束关系。例如，如果进程B需要使用进程A产生的数据，那么进程A必须在进程B之前完成数据的生产。这种"先后顺序"的约束就是同步。经典的例子是生产者-消费者问题——消费者必须在生产者生产了商品之后才能消费。

互斥（Mutual Exclusion）：多个进程不能同时使用某个共享资源（称为"临界资源"）。例如，打印机在任何时刻只能为一个进程服务，如果两个进程同时向打印机输出，打印出来的内容会交错在一起。需要互斥访问的资源就是临界资源。

临界区与临界资源的访问规则

访问临界资源的代码段称为"临界区"。对临界区的访问必须遵循四条规则：

  1. 空闲让进：当没有进程在临界区时，允许一个进程进入
  2. 忙则等待：当已有进程在临界区时，其他进程必须等待
  3. 有限等待：等待进入临界区的进程不会无限期等待
  4. 让权等待：当进程不能进入临界区时，应释放CPU（切换到阻塞态）

二、信号量与PV操作

信号量是Dijkstra提出的一种解决同步与互斥问题的经典机制。信号量本质上是一个整型变量，它代表某种资源的可用数量。操作系统提供了两个原子操作（不可中断的操作）来操作信号量。

信号量的含义：

  • S ≥ 0：表示当前可用的资源数
  • S < 0：|S| 表示正在等待该资源的进程数

P操作（wait操作，荷兰语"proberen"，意为"尝试"）：

S = S - 1
如果 S < 0，则进程进入阻塞状态（等待队列）

V操作（signal操作，荷兰语"verhogen"，意为"增加"）：

S = S + 1
如果 S ≤ 0，则从等待队列中唤醒一个进程

用信号量实现互斥

semaphore mutex = 1;  // 互斥信号量，初始为1

// 进程A                          // 进程B
P(mutex);                         P(mutex);
// 临界区操作                      // 临界区操作
V(mutex);                         V(mutex);

当第一个进程执行P(mutex)时，mutex变为0，进程进入临界区。第二个进程再执行P(mutex)时，mutex变为-1，进程阻塞。当第一个进程执行V(mutex)后，mutex变为0，唤醒第二个进程。这样就实现了"同一时间只有一个进程进入临界区"。

经典问题：生产者-消费者问题

生产者-消费者是最经典的多进程同步问题。生产者和消费者共享一个容量为n的缓冲区，生产者向缓冲区放入数据，消费者从缓冲区取出数据。需要保证：

  1. 缓冲区满时，生产者不能继续放入（同步约束）
  2. 缓冲区空时，消费者不能取出（同步约束）
  3. 生产者和消费者不能同时操作缓冲区（互斥约束）
semaphore mutex = 1;   // 互斥访问缓冲区
semaphore empty = n;   // 空缓冲区数量，初始为n
semaphore full = 0;    // 满缓冲区数量，初始为0

producer() {
  while (true) {
    produce_item();      // 生产数据
    P(empty);            // 申请一个空位
    P(mutex);            // 锁定缓冲区
    put_item();          // 放入数据
    V(mutex);            // 解锁缓冲区
    V(full);             // 增加一个满位
  }
}

consumer() {
  while (true) {
    P(full);             // 申请一个满位
    P(mutex);            // 锁定缓冲区
    get_item();          // 取出数据
    V(mutex);            // 解锁缓冲区
    V(empty);            // 增加一个空位
    consume_item();      // 消费数据
  }
}

注意：P(empty)必须在P(mutex)之前执行。如果颠倒了顺序，缓冲区满时会发生死锁——生产者持有mutex后等待empty，而消费者因为无法获取mutex而无法消费。这就是"死锁"的一个活生生例子。

三、死锁

3.1 死锁的四个必要条件

死锁是指多个进程因竞争资源而陷入相互等待的状态——每个进程都在等待对方释放资源，但谁都无法推进。死锁的产生必须同时满足四个条件：

  1. 互斥条件：至少有一个资源只能被一个进程同时使用（即资源是不可共享的）
  2. 请求与保持条件：进程已经获得了一些资源，同时在请求其他资源（在等待时不释放已获得的资源）
  3. 不剥夺条件：进程已获得的资源在未使用完之前不能被强行剥夺
  4. 循环等待条件：存在一个进程—资源的循环等待链，链中的每个进程都在等待下一个进程释放资源

这四个条件缺一不可，破坏任何一个条件就可以预防死锁。

3.2 死锁的预防策略

  • 破坏互斥条件：如果资源可以共享，就不会有死锁。但很多资源（如打印机）天生就是独占的，无法共享。这个策略的实用性不强。

  • 破坏请求与保持条件：要求进程在运行前一次性申请所有需要的资源。如果有一个资源申请不到，就释放所有已获得的资源。这种策略的缺点是资源利用率低，因为进程可能在很长时间内占用着暂时用不到的资源。

  • 破坏不剥夺条件：当一个进程申请的资源被其他进程占有时，系统可以强行剥夺已分配给其他进程的资源。这种策略实现复杂，且可能导致进程状态丢失。

  • 破坏循环等待条件：给所有资源编号，要求进程必须按编号升序申请资源。这样就不会形成循环等待。例如，打印机编号1，磁盘编号2，CD-ROM编号3，进程必须按1→2→3的顺序申请资源。

3.3 银行家算法

银行家算法是Dijkstra提出的死锁避免算法。它类似于银行贷款的审批过程——银行不会把所有资金都贷出去，而是保留一部分以应对突发的还款需求。

输入：Available, Max, Allocation, Need Work=Available, 所有Finish[i]=false 存在Finish[i]=false且Need[i]<=Work？ 否 Pi完成, Work+=Allocation[i] Finish[i]=true 所有Finish[i]=true？ 否 系统安全 系统不安全

算法的核心思想是：在系统分配资源之前，先判断分配后系统是否处于安全状态。如果是，才进行分配；否则，让进程等待。

典型例题：

系统有A、B、C三类资源共10、5、7个单位。五个进程的分配情况如下：

| 进程 | Allocation(A,B,C) | Max(A,B,C) | Need(A,B,C) |
|------|------|------|------|------|------|------|
| P0 | 0,1,0 | 7,5,3 | 7,4,3 |
| P1 | 2,0,0 | 3,2,2 | 1,2,2 |
| P2 | 3,0,2 | 9,0,2 | 6,0,0 |
| P3 | 2,1,1 | 2,2,2 | 0,1,1 |
| P4 | 0,0,2 | 4,3,3 | 4,3,1 |

Available(A,B,C) = (3,3,2)

验证系统是否安全：

  1. 寻找Need ≤ Available的进程。P1的Need=(1,2,2) ≤ (3,3,2)，假设P1获得资源并完成，释放(2,0,0)，Available=(5,3,2)
  2. P3的Need=(0,1,1) ≤ (5,3,2)，P3完成，释放(2,1,1)，Available=(7,4,3)
  3. P4的Need=(4,3,1) ≤ (7,4,3)，P4完成，释放(0,0,2)，Available=(7,4,5)
  4. P0的Need=(7,4,3) ≤ (7,4,5)，P0完成，释放(0,1,0)，Available=(7,5,5)
  5. P2的Need=(6,0,0) ≤ (7,5,5)，P2完成

所有进程均可完成 → 系统处于安全状态，安全序列为 P1→P3→P4→P0→P2

3.4 死锁的资源计算

假设系统中有n个进程，每个进程最多需要m个某类资源，问系统至少需要多少个该类资源才能保证不会发生死锁？

公式：R ≥ n×(m-1) + 1

推理过程：最坏情况下，每个进程已经分到了(m-1)个资源，共n×(m-1)个资源。此时，只要还有一个空闲资源，任何进程都可以获得第m个资源后完成，释放资源后其他进程也能继续。如果资源数等于n×(m-1)，最坏情况是所有进程都差一个资源，谁都完成不了 → 死锁。

例题：系统有4个进程和5台磁带机，每个进程最多需要2台，问是否会死锁？

R = 5, n×(m-1)+1 = 4×(2-1)+1 = 5
5 ≥ 5，所以不会死锁。但如果只有4台，则4 < 5，存在死锁风险。