第三章：进程同步与互斥

3.1 基本概念

想象你和室友共用一个厨房。如果两个人同时用刀切菜，可能会撞到一起受伤——这就好比两个进程同时访问共享资源，需要互斥。如果你在煮面，室友等面煮好后才能用锅炒菜——这就是同步。

3.1.1 临界资源与临界区

临界资源：一次只允许一个进程使用的资源（如打印机、共享变量）。

临界区：访问临界资源的那段代码。每个进程在进入临界区之前需要检查是否可以进入。

do {
    entry section;     // 进入区（检查是否可以进入临界区）
    critical section;  // 临界区（访问临界资源）
    exit section;      // 退出区（释放资源）
    remainder section; // 剩余区（其他代码）
} while (true);

临界区访问的四个原则：

  1. 空闲让进（无进程在临界区时，应允许一个进程进入）
  2. 忙则等待（有进程在临界区时，其他进程必须等待）
  3. 有限等待（等待进入临界区的进程不能无限等待）
  4. 让权等待（不能进入时，应释放CPU——不是必须的，但推荐）

3.1.2 同步与互斥

概念 含义 类比
互斥 同一时刻只能有一个进程访问临界资源 一个厕所一次只能进一个人
同步 进程间有先后执行顺序关系 生产了数据之后才能消费

3.2 互斥的实现方法

3.2.1 软件实现方法

单标志法（谦让法）

设置一个公用变量turn，表示允许哪个进程进入临界区。

  • 问题：必须交替访问，违反"空闲让进"——若P0访问完后turn=1但P1不在临界区，P0也不能再进入（因为turn=1）。
双标志先检查法

设置flag[]数组表示进程是否想进入临界区。进程先检查对方flag再进入。

  • 问题：检查后、进入前可能被调度——导致两个进程同时进入临界区（违反"忙则等待"）。
双标志后检查法

先设置自己的flag为true，再检查对方flag。

  • 问题：双方同时设置→同时检查→互相谦让→死锁（谁也进不去）。
Peterson算法

结合了单标志和双标志：设置flag[2]表示意愿，turn表示谁谦让。

// Pi进程（i=0或1，j=1-i）
flag[i] = true;   // 我想进入
turn = j;         // 但我把机会让给你
while (flag[j] && turn == j) // 如果你也想进且轮到你
    ;              // 等待
// 临界区
flag[i] = false;  // 退出

Peterson算法正确地实现了互斥，满足了空闲让进、忙则等待、有限等待三个条件。

3.2.2 硬件实现方法

中断屏蔽方法

进入临界区前关中断（"关中断"指令），退出时开中断。

  • 问题：关中断权力太大（限制CPU切换），不适合多核系统。
TestAndSet（TS指令/TSL指令）

硬件支持的原子操作：读取并设置锁定标志。

boolean TS(boolean *lock) {
    boolean old = *lock;
    *lock = true;   // 加锁
    return old;     // 返回旧值
}
  • 如果返回false（未锁定），进入临界区。
  • 问题：不满足"让权等待"（忙等）。
Swap指令（XCHG）

交换两个变量的值（原子操作），原理类似TS。

3.3 信号量机制

信号量是1965年由Dijkstra提出的，是OS中最经典的同步互斥工具。

3.3.1 整型信号量

用一个整型变量表示资源数量，仅通过两个原子操作访问：

  • wait(S) / P操作：while(S <= 0); S--;
  • signal(S) / V操作：S++;

问题：不满足"让权等待"（P操作忙等）。

3.3.2 记录型信号量（重点）

typedef struct {
    int value;           // 资源数量
    struct process *L;   // 等待队列
} semaphore;

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // 资源不足，阻塞自己
        block(S->L);  // 进入等待队列
    }
}

void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // 等待队列非空，唤醒一个
        wakeup(S->L);
    }
}
  • value为正：表示剩余资源数量。
  • value为负：表示等待队列中的进程数量。
  • value为0：资源刚好用完，无等待进程。

💡 记忆技巧：P操作=Proberen（检查/减少），V操作=Verhogen（增加）。可以这样记：P是"拿"资源（所以减1），V是"放"资源（所以加1）。

3.3.3 用信号量实现同步与互斥

实现互斥：

semaphore mutex = 1;  // 互斥信号量
// 进程Pi：
P(mutex);   // 进入临界区前P
// 临界区
V(mutex);   // 退出临界区后V

实现同步：比如P2必须在P1的S1语句之后执行。

semaphore sync = 0;
// P1:
S1;
V(sync);   // 告诉P2：我完成了

// P2:
P(sync);   // 等待P1完成
S2;

实现前驱关系：每对前驱后继设置一个同步信号量。如果有n个前驱，P操作要执行n次检查。

📌 408考点提示：P、V操作实现同步互斥是408大题的必考点。关键步骤：

  1. 分析同步关系（谁等谁）
  2. 分析互斥关系（哪些资源必须互斥访问）
  3. 设置信号量并赋初值
  4. 在合适位置插入P、V操作

3.4 经典同步问题

3.4.1 生产者-消费者问题（重点中的重点）

问题描述：多个生产者进程生产数据放入缓冲区，多个消费者进程从缓冲区取数据消费。缓冲区满时生产者等待，缓冲区空时消费者等待。

semaphore mutex = 1;  // 互斥访问缓冲区
semaphore empty = n;  // 空缓冲区数量
semaphore full = 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操作的顺序不能错！ 先P(empty/full)再P(mutex)——如果反过来，可能出现：缓冲区满时生产者先P(mutex)获得锁，然后P(empty)阻塞，但消费者无法进入临界区取数据，造成死锁。

扩展：多生产者-多消费者问题 如果有多个不同类型的产品（如苹果和橘子），需要设置两个同步信号量分别管理。

3.4.2 读者-写者问题

问题描述：多个读者可同时读共享数据，但写者必须独占访问（写时不能读，读时不能写）。

读者优先方案（读者不释放读锁时写者可能饿死）：

semaphore rw = 1;    // 用于写者互斥
semaphore mutex = 1; // 保护count
int count = 0;       // 当前读者数量

// 写者
writer() {
    P(rw);            // 申请写
    write();          // 写操作
    V(rw);            // 释放写
}

// 读者
reader() {
    P(mutex);
    if (count == 0)
        P(rw);        // 第一个读者锁住写者
    count++;
    V(mutex);
    
    read();           // 读操作（多个读者可同时）
    
    P(mutex);
    count--;
    if (count == 0)
        V(rw);        // 最后一个读者释放写者
    V(mutex);
}

写者优先方案：增加一个信号量用于写者优先排队。

📌 408考点提示：读者-写者问题考查信号量设计，注意分析读者共享和写者互斥的细节。

3.4.3 哲学家进餐问题

问题描述：5个哲学家围坐圆桌，每人面前一碗面，每两人之间一支筷子。哲学家思考（不拿筷子）或进餐（需要拿左右两支筷子）。

semaphore chopstick[5] = {1,1,1,1,1};

// 哲学家i（可能死锁的版本）
philosopher(int i) {
    while (true) {
        P(chopstick[i]);          // 拿左筷子
        P(chopstick[(i+1)%5]);    // 拿右筷子
        eat();
        V(chopstick[i]);          // 放左筷子
        V(chopstick[(i+1)%5]);    // 放右筷子
        think();
    }
}

问题：如果所有哲学家同时拿左筷子，会死锁（每人等右筷子）。

解决方案：

  1. 最多允许4个哲学家同时进餐（设一个count信号量=4）
  2. 奇数号先拿左、偶数号先拿右（破坏循环等待条件）
  3. 仅当两支筷子都可用时才拿（用mutex保护拿筷子的过程）

3.4.4 吸烟者问题

问题描述：一个供应商进程和三个吸烟者进程。供应商随机提供两种原料，吸烟者需要三种原料才能卷烟吸（每种吸烟者缺少一种不同的原料）。

解决方案：四个信号量（供应信号量×3 + 互斥信号量），供应商通过信号量通知对应的吸烟者，吸烟者完成后通知供应商。

3.5 管程

3.5.1 管程的基本概念

信号量的P、V操作分布在各个进程中，容易出错。管程（Monitor） 把共享资源和操作封装在一起，所有进程只能通过管程提供的入口访问共享资源。

管程的特性：

  1. 管程内的共享变量只能被管程内的过程访问。
  2. 每次只允许一个进程进入管程（编译器保证互斥）。
  3. 提供条件变量（condition）和wait/signal操作来实现同步。

3.5.2 管程 vs 信号量

对比 管程 信号量
编程难度 低（封装性好） 高（P/V容易错）
编译器支持 需要 不需要
互斥保证 自动（进入管程互斥） 手动（设置mutex）
使用场景 高级并发编程语言 操作系统内核

示例题

示例1（生产者-消费者变体）：有一个容量为n的缓冲区，有m个生产者和k个消费者。请用P、V操作实现同步与互斥。

解：前面给出的标准解法即可，注意多个生产者之间也需要互斥（buffer是共享资源）。上述代码中的mutex信号量保证了生产者之间的互斥，也保证了消费者之间的互斥，同时保证了生产者和消费者之间的互斥。

示例2（同步问题）：设有三个进程P1、P2、P3，执行顺序要求：P1执行完后P2才能执行，P2执行完后P3才能执行。请用信号量实现。

解：

semaphore S12 = 0; // P1→P2的同步
semaphore S23 = 0; // P2→P3的同步

P1() { P2() { P3() {
    work1;     P(S12);    P(S23);
    V(S12);    work2;     work3;
}              V(S23);    }
}

示例3（复杂同步）：有A、B两个进程共享一个缓冲区。A负责从输入设备读数据到缓冲区，B负责从缓冲区取数据进行计算。缓冲区只能存放一个数据。请用信号量实现。

解：这是单缓冲区的生产者-消费者问题。

semaphore empty = 1;  // 缓冲区空
semaphore full = 0;   // 缓冲区满

A() {
    while (true) {
        read_data();
        P(empty);
        buffer = data;
        V(full);
    }
}

B() {
    while (true) {
        P(full);
        data = buffer;
        V(empty);
        compute(data);
    }
}

本章小结

进程同步与互斥是并发编程的核心。信号量的P、V操作是408大题的必考内容，必须熟练掌握：生产者-消费者问题、读者-写者问题、哲学家进餐问题是三大经典模型。解题的关键是：先分析同步和互斥关系，再设置信号量，最后插入P、V操作。注意P操作的顺序问题——"申请资源在前，加锁在后"避免死锁。