408 操作系统

Appearance

我的博客收藏我的博客批注

读者-写者问题 ​

2026 大纲 二（三）6 经典同步问题的读者-写者部分（生产者-消费者见《生产者-消费者问题》）。

第二个经典问题：这次不是"要么你要么我" ​

生产者—消费者里，缓冲区这份资源是纯粹互斥的：谁在动它，别人就得等。

读者—写者问题换了个条件：读和读不冲突。 一百个人同时读同一份数据毫无问题， 真正冲突的是读-写与写-写。

这种"半互斥"，一个普通信号量表达不了——信号量只有"能进"和"不能进"两档， 说不出"你们这一伙可以一起进，但另一伙来了就都得出去"。

破局的思路是换一个争锁的主体：不让每个读者各自去抢锁， 而是让"读者这一整群"作为一个整体去和写者争。

具体做法就是记个数：第一个读者进来时替全体 P(rw_mutex)， 最后一个读者离开时替全体 V(rw_mutex)，中间的读者直接进、直接出。

⚠️ 这个计数器 readcount 自己又成了新的临界资源（两个读者可能同时改它）， 所以还要再套一个 mutex。而这里有两处必错点：

"改计数 + 判断是不是第一个"必须整体放在 mutex 里—— 拆开的话两个人可能都认为自己是第一个（都去 P），或都认为自己不是（谁也没 P）。

读操作本身必须在 mutex 之外——否则读者又变成一个一个来了， 多读者并行这个全部意义就没了。

最后还有一层：这个写法写者会饥饿（只要读者络绎不绝，写者永远等不到）。 三种方案的差别只在加不加一道闸门、闸门什么时候关。

交互可视化 ​

加载可视化中...

一、读者优先方案 ​

semaphore rw_mutex = 1;   // 读者群与写者之间、写者与写者之间的互斥
semaphore mutex    = 1;   // 保护 readcount 这个共享变量
int readcount = 0;        // 当前正在读的进程数

// 写者进程
writer() {
    do {
        P(rw_mutex);      // 申请独占权
        perform write operation;
        V(rw_mutex);
    } while (TRUE);
}

// 读者进程
reader() {
    do {
        P(mutex);             // 保护 readcount
        readcount++;
        if (readcount == 1)   // 我是第一个读者
            P(rw_mutex);      //   替整群读者把写者挡在门外
        V(mutex);

        perform read operation;   // 多个读者可以同时读

        P(mutex);
        readcount--;
        if (readcount == 0)   // 我是最后一个读者
            V(rw_mutex);      //   放行写者
        V(mutex);
    } while (TRUE);
}

它的代价是写者饥饿：只要新读者源源不断到达，readcount 就始终不为 0，V(rw_mutex) 永远不执行。判据是——写者能不能进场取决于 readcount 会不会归零，而没有任何机制阻止新读者加入，所以只要读者到达率足够高，写者饥饿必然发生。要补救就必须找地方挡住后来的读者，三种方案的差别全在"挡在哪里"。

二、写者优先方案 ​

思路：写者一到，就先把"读者入口"关上，已经在读的读者读完即可，新读者一律拦在门外。

semaphore rw_mutex = 1;   // 读写互斥（同上）
semaphore mutexR   = 1;   // 保护 readcount
semaphore mutexW   = 1;   // 保护 writecount
semaphore readTry  = 1;   // 读者入口闸门：有写者在就关上
int readcount = 0, writecount = 0;

writer() {
    do {
        P(mutexW);
        writecount++;
        if (writecount == 1)  P(readTry);   // 第一个写者关闭读者闸门
        V(mutexW);

        P(rw_mutex);
        perform write operation;
        V(rw_mutex);

        P(mutexW);
        writecount--;
        if (writecount == 0)  V(readTry);   // 最后一个写者打开读者闸门
        V(mutexW);
    } while (TRUE);
}

reader() {
    do {
        P(readTry);           // 闸门关着就进不来
        P(mutexR);
        readcount++;
        if (readcount == 1)  P(rw_mutex);
        V(mutexR);
        V(readTry);           // 立即放开闸门，不阻塞后面的读者

        perform read operation;

        P(mutexR);
        readcount--;
        if (readcount == 0)  V(rw_mutex);
        V(mutexR);
    } while (TRUE);
}

写者一到就把 readTry 拿走，此后新读者全部卡在 P(readTry)，readcount 因此能归零、写者随即拿到 rw_mutex；而只要还有写者排队（writecount > 0），闸门就一直关着。代价是轮到读者饥饿。穷举检验（2 个读者 + 2 个写者的完整交错）：可达状态 4056，死锁态 0，"写者与读者同时在临界区"或"两个写者同时在临界区"的状态 0。

三、读写公平方案 ​

思路取中：读者和写者都在同一个信号量 w 上排队，先到先得。

semaphore rw_mutex = 1;
semaphore mutex    = 1;
semaphore w        = 1;   // 公共排队闸门
int readcount = 0;

writer() {
    P(w);
    P(rw_mutex);
    perform write operation;
    V(rw_mutex);
    V(w);
}

reader() {
    P(w);                 // 和写者在同一条队上排
    P(mutex);
    readcount++;
    if (readcount == 1)  P(rw_mutex);
    V(mutex);
    V(w);                 // 立即释放，不挡住已在读的同伴

    perform read operation;

    P(mutex);
    readcount--;
    if (readcount == 0)  V(rw_mutex);
    V(mutex);
}

写者一旦在 w 上排上队，后到的读者就被挡在 P(w) 前、接不上 readcount；当前这批读者读完后 readcount 归零，写者获得机会。

四、三种方案的完整矩阵 ​

读者优先写者优先读写公平
新增信号量无（基准方案）mutexW、readTry + 变量 writecountw
挡住后来读者的地方不挡有写者时挡在 P(readTry)有人排队时挡在 P(w)
写者到达后要等多久可能无限期（readcount 不归零）当前这批读者读完即可排在它前面的那些请求完成即可
谁会饥饿写者读者都不会
读的吞吐量最高最低居中
判据：什么时候选它读远多于写，且写可以推迟（如缓存统计）写的时效性关键，数据必须尽快更新（如配置下发）两类请求都不能长期饿着（通用场景）
变形：最多允许 RN 个读者同时读，用信号量集怎么写（想看"测试而不占用"这一能力怎么用时展开）

实际系统常给并发读数设一个上限（避免读者太多把写者拖垮）。教材用信号量集给出这个变形：引入信号量 L，初值为 RN，读者进入前执行 Swait(L, 1, 1) 使 L 减 1；当 RN 个读者进入后 L 减为 0，第 RN+1 个读者会因 Swait(L, 1, 1) 失败而阻塞。

int RN;                          // 允许的最大并发读者数
semaphore L = RN, mx = 1;

void reader() {
    do {
        Swait(L, 1, 1);          // 占一个读名额
        Swait(mx, 1, 0);         // 只测试 mx >= 1，不占用它（d = 0）
        perform read operation;
        Ssignal(L, 1);           // 归还名额
    } while (TRUE);
}

void writer() {
    do {
        Swait(mx, 1, 1; L, RN, 0);   // 要求 mx>=1 且占用它；同时要求 L 达到满额 RN 但不占用
        perform write operation;
        Ssignal(mx, 1);
    } while (TRUE);
}

两处用到了信号量集的特殊形态：

写法含义起什么作用
Swait(mx, 1, 0)（读者）只测试 mx ≥ 1，不占用（d=0）就是那个"可控开关"：没有写者时（mx = 1）允许多个读者通过；写者占走 mx 后（mx = 0）后续读者全被挡住
Swait(mx, 1, 1; L, RN, 0)（写者）占用 mx；同时要求 L 恢复到满额 RN 但不占用它L = RN 等价于"当前一个读者也没有"，写者靠这一条确认读者全部退场

这个变形把"测试而不占用"这一能力用到了极致——普通记录型信号量做不到"多个进程同时通过同一个初值为 1 的信号量"。

考点速记 ​

  1. 半互斥：读-读不互斥，读-写与写-写互斥。⚠️一个普通信号量表达不了——它只有能进/不能进两档。
  2. 破局思路是换争锁的主体：让读者整群作为整体去和写者争锁，因此引入计数器 readcount——第一个读者 P(rw_mutex)、最后一个读者 V(rw_mutex)。
  3. ⚠️两处最容易写错："改计数 + 判断"必须整体放在 mutex 里（否则两人都以为自己是第一个、或都以为自己不是）；读操作必须在 mutex 之外（这是多读者能并行的前提）。
  4. 三种方案共享同一套骨架，差别只在有没有闸门、闸门何时关：
    • 不加闸门 → 写者饥饿（读者络绎不绝时写者永远等不到）；
    • 加 readTry、写者一到就关 → 读者饥饿（写优先）；
    • 加信号量 w、先到先得 → 都不饥饿（公平）。
  5. 公平方案里读者提前 V(w)、写者写完才 V(w)——判据是这个角色本身允不允许并行：读者放行后别的读者可以一起进，写者必须独占到底。

这一节在真题里被考过的形式：

classic-sync-problems 只有 3 道题、由三篇经典问题共享， 本页练习区渲染的题不全是本节内容，属正常。 读者—写者本身至今没单独出过大题，但它是 PV 大题里一类固定变形的原型—— 凡题面出现"若干角色可以同时做某事、另一些角色必须独占"，走的都是本节的骨架。

典型的映射："多人可同时进入阅览室、管理员整理时必须清场"、 "多个线程可同时读缓存、更新时必须独占"——把"读者"替换成允许并行的那一方即可。

复习优先级：读懂骨架即可，重点是速记第三条那两处必错点。 "改计数和判断要放在一起""读操作要在 mutex 之外"这两句在动手写代码时立刻用得上。 第四条那三种方案的差别属于理解层面，408 至今只在选项里出现过，不必背代码。

易错：把"改 readcount "和"判断是不是第一个"拆开写。必须整体放在 mutex 里。

易错：把读操作也放进 mutex 里。那样读者就变成一个一个来，多读者并行的意义全没了。

易错：认为一个信号量就能表达读者—写者。它只有两档，说不出"这一伙可以一起进"。

易错：认为最基础的读者优先方案没有问题。它会饿死写者。

教材出处
  • 问题定义与记录型信号量解法：汤小丹《计算机操作系统》2.5.3 节，印刷 p65——"允许多个进程同时读一个共享对象……但不允许一个 Writer 进程和其他 Reader 进程或 Writer 进程同时访问共享对象"；"读者-写者问题常被用来测试新同步原语"。代码为 semaphore rmutex=1, wmutex=1; int readcount=0;，读者段写作 wait(rmutex); if(readcount==0) wait(wmutex); readcount++; signal(rmutex);。
  • 带 RN 上限的信号量集解法：同书印刷 p66——"增加了一个限制，即最多只允许 RN 个读者同时读。为此，又引入了一个信号量 L，并赋予其初值为 RN"，代码为读者 Swait(L,1,1); Swait(mx,1,0);、写者 Swait(mx,1,1; L,RN,0);。
  • Swait(S,1,0) 是可控开关：同书 2.4.3 节，印刷 p55。

相关知识 ​

生产者-消费者问题｜哲学家进餐问题｜信号量

真题练习 ​

相关真题（3题）

2019Q438分2014Q478分2009Q457分

相关文章