经典同步问题

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

同步问题设计

同步问题设计题通常要求根据题目描述，用 信号量 + 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

生产者消费者问题是并发编程中的经典问题，涉及到两种线程 —— 生产者 和 消费者，它们共享一个固定大小的缓冲区或存储区。

  • 生产者的任务是生成数据并将其 放入缓冲区。
  • 消费者的任务是 从缓冲区中取出 并消费这些数据。

关键的挑战在于确保生产者不会在缓冲区满时添加数据，同时确保消费者不会在缓冲区空时尝试消费数据。

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
可以多个读者一起读，
但是此时写者不能写
系统一个时刻最多允许一个写者在写，
并且此时其他读者和写者都不允许操作

读者写者问题 是另一个经典的并发编程问题，涉及到对 共享数据 或 资源 的访问，这些 资源 可以被 多个读者 同时读取，但只能被 一个写者 写入，而且当 写者 正在写入数据时，没有其他 读者 或 写者 可以访问该 资源。

这个问题的挑战在于两点：

  • 允许多个读者同时读取资源。
  • 确保当有一个写者访问资源时，没有其他读者或写者可以同时访问。
int read_count = 0;
semaphore wrt  = 1;
semphore 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;
semaphore write_mutex = 1;

reader() {
    while (1) {
        P(write_mutex)                  // 在读取之前，确保没有写者正在等待或写入
        P(mutex)                        // 获取互斥访问权，以修改 read_count
        read_count += 1
        if (read_count == 1) {
            P(wrt)
        }
        V(mutex)
        V(write_mutex)

        ...                             // 读取资源

        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(wrt)
        }
        V(write_mutex)

        ...                             // 写入资源

        P(write_mutex)                  // 获取互斥访问权，以修改write_count
        write_count -= 1
        if (write_count == 0) {         // 如果没有其他写者在等待或写入，释放资源
            V(wrt)
        }
        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-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. 按相同顺序放下叉子✓ 逆时针获取资源（打破循环等待）关键：非对称策略避免了循环等待，从而防止死锁