经典同步问题

🔥 高优先级
同步问题设计 是操作系统解答题必考题，本节的几个经典问题虽然不会直接考察，但是其中的设计思想还是需要深入掌握。

同步问题设计

同步问题设计题通常要求根据题目描述，用 信号量 + P/V 操作 写出若干进程的同步关系。它不是背某一道固定代码，而是把题目中的 互斥关系 和 前驱关系 翻译成信号量。

解题时可以按下面的模板展开，整体步骤与三类信号量的对应关系如下：

同步问题解题模板（信号量法）① 找进程与循环结构把题中角色 → 进程反复行为套 while(1)② 找互斥关系共享同一资源 + 同时仅一个→ 互斥信号量（初值 1）③ 找同步关系动作 A 必须先于 B→ 同步信号量（初值 0）④ 找资源数量约束缓冲区 / 座位 / 设备→ 资源信号量（初值=容量）⑤ 写 P/V 伪代码先资源信号量，后互斥信号量V 顺序通常对称即可⑥ 自检P/V 成对、方向一致无死锁、覆盖全部角色三类信号量怎么选？按 “保护对象” 划分互斥信号量初值 1保护对象：临界资源命名：mutex, rw, fork[i]P(mutex);// 临界区V(mutex);紧贴临界区，不要包多同步信号量初值 0保护对象：事件先后命名：s, done, readyA: ... V(s);B: P(s); ...前驱关系一条边 → 一个信号量谁等谁 P，谁完成谁 V资源信号量初值=资源总数 n保护对象：可数资源命名：empty, full, seatP(empty); P(mutex);// 放数据V(mutex); V(full);先资源、后互斥，防死锁核心：自然语言 → 互斥关系/前驱关系/资源约束 → 三类信号量与 P/V 顺序

找进程和循环结构

先把题目中的参与者抽象成进程，例如生产者、消费者、读者、写者、顾客、服务员等。

如果题目描述的是反复发生的行为，一般写成：

process_i() {
    while (1) {
        ...
    }
}

如果题目描述的是一次性流程，则按题目要求写出执行顺序即可，不一定要套 while (1)。

找互斥关系

只要多个进程会访问同一个共享资源，并且同一时刻只能有一个进程访问，就需要设置 互斥信号量。

常见写法是：

semaphore mutex = 1;

P(mutex);
...     // 访问临界资源
V(mutex);

这里 mutex 初值为 1，表示资源一开始可用。进入临界区前执行 P(mutex)，离开临界区后执行 V(mutex)。

提示

互斥信号量只保护真正的临界区，不要把无关操作也包进去，否则容易导致并发度下降，甚至造成死锁。

找同步关系

如果一个操作必须在另一个操作完成之后才能执行，就需要设置 同步信号量。

常见写法是：

semaphore s = 0;

process_A() {
    ...         // A 先执行的操作
    V(s);       // 通知 B 可以继续
}

process_B() {
    P(s);       // 等待 A 完成
    ...         // B 后执行的操作
}

同步信号量的初值通常是 0，表示条件一开始不满足。先发生的进程在完成关键操作后执行 V(s)，后发生的进程在执行前先 P(s) 等待。

找资源数量约束

如果题目中出现缓冲区、座位、车位、窗口、设备等有限数量资源，通常使用 计数信号量 表示资源个数。

例如缓冲区大小为 n 的生产者消费者问题中：

semaphore empty = n;   // 空缓冲区数量
semaphore full = 0;    // 已占用缓冲区数量
semaphore mutex = 1;   // 缓冲区互斥访问

生产者需要先申请空缓冲区，再进入临界区放入数据：

P(empty);
P(mutex);
...         // 放入数据
V(mutex);
V(full);

消费者需要先申请已占用缓冲区，再进入临界区取出数据：

P(full);
P(mutex);
...         // 取出数据
V(mutex);
V(empty);

这种题最容易出错的地方是 P 操作顺序：一般先申请 资源型信号量，再申请 互斥信号量，避免一个进程占着互斥锁等待资源，导致其他进程无法进入临界区改变资源状态。

整理 P/V 位置

写完代码后，可以按下面的规则检查：

  1. 互斥成对出现：P(mutex) 和 V(mutex) 是否包住了同一个临界区。
  2. 同步方向正确：谁等待就写 P(s)，谁唤醒就写 V(s)。
  3. 资源数守恒：申请资源用 P，释放资源用 V，资源总数不能凭空增加或减少。
  4. 避免死锁：不要在持有一个互斥锁时，长时间等待另一个可能由别人释放的条件。
  5. 不要遗漏并发角色：题目中每一类进程都要有对应伪代码。

常见信号量类型

类型初值作用常见命名
互斥信号量1保护临界资源mutex、rw、fork[i]
同步信号量0表示某个前驱事件尚未发生s1、done、ready
资源信号量资源数量表示还有多少个资源可用empty、full、seat
计数保护信号量1保护计数变量修改count_mutex、read_mutex
补充

同步问题设计题的核心不是代码语法，而是把自然语言翻译成信号量：互斥关系用初值为 1 的信号量，前驱关系用初值为 0 的信号量，有限资源用初值为资源数量的计数信号量。

生产者消费者问题

Producer
Producer
Consumer
ConsumerText is not SVG - cannot display

生产者消费者问题（Producer-Consumer Problem）是操作系统和并发程序设计中的经典同步问题。

在该问题中，一组 生产者 和一组 消费者 共享一个固定大小的缓冲区。生产者不断生成数据并放入缓冲区，消费者不断从缓冲区取出数据进行处理，两者通过缓冲区完成数据交换。

  • 生产者：负责生成数据并放入缓冲区。
  • 消费者：负责从缓冲区取出数据并进行消费。

由于生产者和消费者会并发访问共享缓冲区，因此需要解决以下两个问题：

  1. 互斥访问：同一时刻只能有一个线程修改缓冲区，防止多个线程同时读写导致数据不一致。
  2. 同步协作：
    • 当缓冲区已满时，生产者必须等待，直到有空闲位置后才能继续生产。
    • 当缓冲区为空时，消费者必须等待，直到有新的数据后才能继续消费。
semaphore mutex = 1;          // 临界区互斥信号量
semaphore empty = n;          // 空闲缓冲区数量
semaphore full  = 0;          // 忙缓冲区数量

producer() {
    while (1) {
        P(empty)              // 等待一个空位置
        P(mutex)              // 进入临界区前先获取mutex
        ....                  // 将数据项添加到缓冲区
        V(mutex)              // 离开临界区，释放mutex
        V(full)               // 增加一个数据项的计数
    }
}

consumer() {
    while (1) {
        P(full)               // 等待一个数据项
        P(mutex)              // 进入临界区前先获取mutex
        ...                  // 从缓冲区取出数据项并消费
        V(mutex)              // 离开临界区，释放mutex
        V(empty)              // 增加一个空位置的计数
    }
}

生产者消费者过程可以参考以下流程图理解：

ProducerConsumer生产者消费者问题cluster_semaphores信号量定义cluster_buffer共享缓冲区 (大小: n)cluster_producer生产者 (Producer)cluster_consumer消费者 (Consumer)mutexmutex = 1(互斥信号量)emptyempty = n(空闲缓冲区)fullfull = 0(忙缓冲区)buffer缓冲区[][][]...[](固定大小)cons_consume从缓冲区取出并消费数据buffer->cons_consume取出数据prod_start开始prod_wait_emptyP(empty)等待空位置prod_start->prod_wait_emptyprod_wait_empty->emptyP操作prod_wait_mutexP(mutex)获取互斥锁prod_wait_empty->prod_wait_mutexprod_wait_mutex->mutexP操作prod_produce生产数据放入缓冲区prod_wait_mutex->prod_produceprod_produce->buffer放入数据prod_release_mutexV(mutex)释放互斥锁prod_produce->prod_release_mutexprod_release_mutex->mutexV操作prod_signal_fullV(full)增加数据计数prod_release_mutex->prod_signal_fullprod_signal_full->fullV操作prod_signal_full->prod_wait_empty循环cons_start开始cons_wait_fullP(full)等待数据项cons_start->cons_wait_fullcons_wait_full->fullP操作cons_wait_mutexP(mutex)获取互斥锁cons_wait_full->cons_wait_mutexcons_wait_mutex->mutexP操作cons_wait_mutex->cons_consumecons_release_mutexV(mutex)释放互斥锁cons_consume->cons_release_mutexcons_release_mutex->mutexV操作cons_signal_emptyV(empty)增加空位计数cons_release_mutex->cons_signal_emptycons_signal_empty->emptyV操作cons_signal_empty->cons_wait_full循环note1关键点：• empty信号量防止缓冲区溢出• full信号量防止空缓冲区消费• mutex信号量保证临界区互斥

读者写者问题

reader
reader
reader
reader
writer
writer
x
reader
writer
writer
x
x
writer
可以多个读者一起读，
但是此时写者不能写
系统一个时刻最多允许一个写者在写，
并且此时其他读者和写者都不允许操作

在操作系统中，经常会出现多个进程或线程 共享同一份数据或资源 的情况。

例如，一个数据库文件可能同时被多个进程访问：

  • 读者（Reader）：只读取共享资源，不会修改数据。
  • 写者（Writer）：需要修改共享资源。

如果多个进程同时访问共享资源，就需要考虑它们之间的同步与互斥关系。

读者—写者问题（Readers-Writers Problem）研究的就是这样一种场景：

多个读者可以同时读取，但写者修改资源时必须独占访问。

为什么读者可以并发访问

多个读者都只是读取数据，并不会修改共享资源。

因此，只要没有写者正在修改数据：

Reader 1 ──┐
Reader 2 ──┼──→ 共享资源
Reader 3 ──┘

多个读者可以同时访问，不需要彼此互斥。

这样可以充分利用资源，提高系统的并发性能。

而写者不同：

Writer ──→ 修改共享资源

写者在修改数据的过程中，如果同时存在其他读者，就可能导致读者读取到不一致的数据；如果同时存在其他写者，则可能发生数据覆盖、丢失等问题。

因此，写者访问共享资源时必须独占资源。

由于多个读者和写者会并发访问共享资源，因此需要同时满足以下两个要求。

  1. 互斥访问：写者访问共享资源时必须具有独占访问权
    • 写者之间必须互斥：同一时刻最多只能有一个写者写入。
    • 写者与读者之间必须互斥：写者写入期间，不能有读者读取。
  2. 并发读取：读者之间不需要互斥，允许多个读者同时读取

在满足上述基本要求之后，还会产生一个新的问题：

当读者和写者同时等待资源时，应该优先让谁访问？

不同的选择会产生三种经典的同步策略。

算法核心思想可能的问题
读者优先有读者排队，就不允许新的写者加入写者可能饥饿
写者优先有写者排队，就不再允许新的读者加入读者可能饥饿
公平算法按照到达顺序公平访问不偏向任何一方
三种策略的具体解释

1. 读者优先

核心思想：

有读者排队，就不允许新的写者加入。

也就是说，只要已经有读者正在读取，后续到来的读者可以继续加入读者队列，而写者需要等待所有读者结束。

已有读者
  ↓
R → R → R → R
          ↑
        新读者可以加入

W → 等待
W → 等待

这样可以最大程度地保证读者的并发性。

但它可能导致：

写者饥饿（Writer Starvation）

如果读者不断到来，写者可能一直得不到执行机会。

2. 写者优先

核心思想：

有写者排队，就不再允许新的读者加入。

已经开始读取的读者可以继续完成读取，但一旦有写者等待，就阻止新的读者进入。

已有读者
R → R → R
    ↓
  正常完成

W → 等待
W → 等待

新 R → 等待

这样可以避免新的读者不断加入，从而让等待中的写者尽快获得资源。

因此：

写者优先主要解决读者优先算法中的写者饥饿问题。

但相应地，如果写者持续到来，也可能导致读者长期无法进入，即读者饥饿。

3. 公平算法

核心思想：

不人为偏向读者或写者，而是按照到达顺序公平地进行访问。

也就是说，后来到达的读者或写者不能随意插队：

R → W → R → W → R
↓   ↓   ↓   ↓   ↓
依次获得访问机会

这样可以避免长期偏向某一方，从而同时避免读者和写者长期饥饿。

int read_count = 0;
semaphore wrt  = 1;
semaphore mutex = 1;

reader() {
    while (1) {
        P(mutex)                     // 获取互斥访问权，以修改 read_count
        read_count += 1
        if (read_count == 1) {       // 如果这是第一个读者，需要锁定资源，防止写者写入
            P(wrt)
        }
        V(mutex)                     // 释放互斥访问权
        ...                          // 读取资源
        P(mutex)                     // 获取互斥访问权，以修改 read_count
        read_count -= 1
        if (read_count == 0) {       // 如果没有读者在读取，释放资源，允许写者写入
            V(wrt)
        }
        V(mutex)                     // 释放互斥访问权
    }
}

writer() {
    while (1) {
        P(wrt)                       // 获取资源的互斥访问权
        ...                          // 写入资源
        V(wrt)                       // 释放资源的互斥访问权
    }
}
int read_count = 0;
int write_count = 0;

semaphore wrt      = 1;     // 共享资源的互斥访问权
semaphore mutex    = 1;     // 保护 read_count
semaphore write_mutex = 1;  // 保护 write_count
semaphore readTry  = 1;     // 控制新的读者能否进入


reader() {
    while (1) {
        P(readTry);                    // 确保没有写者正在等待
        P(mutex);                      // 获取互斥访问权，以修改 read_count

        read_count += 1;
        if (read_count == 1) {         // 如果这是第一个读者，需要锁定资源，防止写者写入
            P(wrt);
        }

        V(mutex);                      // 释放互斥访问权
        V(readTry);                    // 允许其他读者进入

        ...                            // 读取资源

        P(mutex);                      // 获取互斥访问权，以修改 read_count
        read_count -= 1;
        if (read_count == 0) {         // 如果没有读者在读取，释放资源，允许写者写入
            V(wrt);
        }

        V(mutex);                      // 释放互斥访问权
    }
}


writer() {
    while (1) {
        P(write_mutex);                // 获取互斥访问权，以修改 write_count

        write_count += 1;
        if (write_count == 1) {        // 如果这是第一个写者，禁止新的读者进入
            P(readTry);
        }

        V(write_mutex);                // 释放互斥访问权

        P(wrt);                        // 获取资源的互斥访问权

        ...                            // 写入资源

        V(wrt);                        // 释放资源的互斥访问权

        P(write_mutex);                // 获取互斥访问权，以修改 write_count
        write_count -= 1;
        if (write_count == 0) {        // 如果没有其他写者等待或写入，允许新的读者进入
            V(readTry);
        }

        V(write_mutex);                // 释放互斥访问权
    }
}
int read_count = 0;
int write_count = 0;
semaphore wrt = 1;
semaphore mutex = 1;
semaphore queue = 1; // 新增队列信号量，以确保公平性

reader() {
    while (1) {
        P(queue);                 // 进入队列
        P(mutex);                 // 获取互斥访问权，以修改 read_count
        read_count += 1;
        if (read_count == 1) {
            P(wrt);               // 如果是第一个读者，锁定资源
        }
        V(mutex);
        V(queue);                 // 离开队列
        ...                       // 读取资源
        P(mutex);                 // 获取互斥访问权，以修改 read_count
        read_count -= 1;
        if (read_count == 0) {
            V(wrt);               // 如果是最后一个读者，释放资源
        }
        V(mutex);
    }
}

writer() {
    while (1) {
        P(queue);                 // 进入队列
        P(wrt);                   // 锁定资源
        ...                       // 写入资源
        V(wrt);                   // 释放资源
        V(queue);                 // 离开队列
    }
}

试题中如果考察读者写者问题的话，一般考察的还是读者优先，读者优先的同步实现方案可以通过以下流程图进行理解：

ReaderWriterProblemcluster_shared共享资源区域cluster_semaphores信号量cluster_reader读者进程流程cluster_writer写者进程流程cluster_legend图例说明shared_resource共享资源(数据文件/数据库)wrt_semwrt = 1(写入互斥)mutex_semmutex = 1(读者计数互斥)read_countread_count = 0(当前读者数)reader_start读者开始reader_p_mutex1P(mutex)获取计数器锁reader_start->reader_p_mutex1reader_p_mutex1->mutex_semreader_incread_count++reader_p_mutex1->reader_increader_inc->read_countreader_check1read_count == 1?reader_inc->reader_check1reader_p_wrtP(wrt)锁定资源reader_check1->reader_p_wrt是reader_v_mutex1V(mutex)释放计数器锁reader_check1->reader_v_mutex1否reader_p_wrt->wrt_sem竞争reader_p_wrt->reader_v_mutex1reader_read读取资源reader_v_mutex1->reader_readreader_read->shared_resource读取reader_p_mutex2P(mutex)获取计数器锁reader_read->reader_p_mutex2reader_p_mutex2->mutex_semreader_decread_count--reader_p_mutex2->reader_decreader_dec->read_countreader_check2read_count == 0?reader_dec->reader_check2reader_v_wrtV(wrt)释放资源锁reader_check2->reader_v_wrt是reader_v_mutex2V(mutex)释放计数器锁reader_check2->reader_v_mutex2否reader_v_wrt->reader_v_mutex2reader_end读者结束(循环)reader_v_mutex2->reader_endreader_end->reader_startwriter_start写者开始writer_p_wrtP(wrt)获取资源独占锁writer_start->writer_p_wrtwriter_p_wrt->wrt_sem竞争writer_write写入资源writer_p_wrt->writer_writewriter_write->shared_resource写入writer_v_wrtV(wrt)释放资源锁writer_write->writer_v_wrtwriter_end写者结束(循环)writer_v_wrt->writer_endwriter_end->writer_startlegend1🔵 读者操作legend2🔴 写者操作legend3🟡 信号量操作legend4🟢 共享资源note核心机制说明:1. 多个读者可以同时读取2. 写者需要独占访问3. 第一个读者锁定wrt4. 最后一个读者释放wrt5. mutex保护read_count

哲学家就餐问题

假设有 N 位哲学家围坐在一张圆桌旁，每两位相邻的哲学家之间放着一把叉子，因此一共有 N 把叉子。

每位哲学家的生活由 思考和吃饭 两种活动组成：

  • 思考：不需要任何资源。
  • 吃饭：需要同时获得自己左右两侧的两把叉子。

例如，对于某位哲学家：

左叉子 + 右叉子
       ↓
      吃饭
       ↓
    放下叉子

叉子属于共享资源，同一时刻只能被一位哲学家拿走。因此，当多个哲学家同时尝试吃饭时，就会产生资源竞争。

为什么可能发生死锁?

考虑最极端的情况：五位哲学家同时决定吃饭，并且都采用相同的策略：

先拿左边的叉子，再拿右边的叉子。

于是可能出现：

P1 拿左叉 → 等右叉
P2 拿左叉 → 等右叉
P3 拿左叉 → 等右叉
P4 拿左叉 → 等右叉
P5 拿左叉 → 等右叉

由于圆桌是一个环，每个人拿到的左叉子恰好都是下一个人需要的右叉子：

P1 → 等待 P2
P2 → 等待 P3
P3 → 等待 P4
P4 → 等待 P5
P5 → 等待 P1

因此形成了：

循环等待（Circular Wait）

每位哲学家都占有一把叉子，同时等待另一把叉子，而没有任何人能够获得两把叉子并开始吃饭。

这就产生了死锁。

一种直观的解决方法就是破坏 死锁产生的必要条件 中的 循环等待条件：

让最后一位哲学家与其他人采用相反的拿叉子顺序。

对于 N 位哲学家：

  • 前 N-1 位哲学家：先拿左边的叉子，再拿右边的叉子。
  • 最后 1 位哲学家：先拿右边的叉子，再拿左边的叉子。

伪代码如下：

semaphore fork[5] = {1, 1, 1, 1, 1};      // 五个叉子，初始都是可用的

void philosopher(int i) {
    if (i < 5) {
        // 对于前面的哲学家，先左后右
        first = i;
        second = (i + 1) % 5;
    } else {
        // 对于最后一个哲学家，先右后左
        first = (i + 1) % 5;
        second = i;
    }
    while (1) {
        think();
        P(fork[first]);
        P(fork[second]);
        eat();
        V(fork[first]);
        V(fork[second]);
    }
}

哲学家就餐过程可以参考以下流程图理解：

哲学家就餐问题流程图（非对称解法）开始判断哲学家编号 ii < N-1i = N-1思考P(fork[i])拿左叉子P(fork[(i+1)%N])拿右叉子吃饭（临界区）V(fork[i])放左叉子V(fork[(i+1)%N])放右叉子思考P(fork[(i+1)%N])拿右叉子P(fork[i])拿左叉子吃饭（临界区）V(fork[(i+1)%N])放右叉子V(fork[i])放左叉子前 N-1 个哲学家策略1. 先拿左边的叉子 (fork[i])2. 再拿右边的叉子 (fork[(i+1)%N])3. 进餐4. 按相同顺序放下叉子✓ 顺时针获取资源最后一个哲学家策略1. 先拿右边的叉子 (fork[(i+1)%N])2. 再拿左边的叉子 (fork[i])3. 进餐4. 按相同顺序放下叉子✓ 逆时针获取资源（打破循环等待）关键：非对称策略避免了循环等待，从而防止死锁