史上最清楚！读者，写者问题（操作系统os）

读者-写者问题是另一个里程碑式的同步互斥问题。它比生产者-消费者更复杂，因为它引入了不对称的访问权限：读者和读者之间是共享的，但写者和任何人（包括读者和其他写者）之间都是互斥的。

我们用一个生动的比喻来解析这个经典问题：一个公共阅览室里的一本珍贵孤本。

• 共享文件：阅览室里唯一的一本珍贵孤本。
• 读者进程：只想阅读这本书的人。他们只是看，不会损坏书。
• 写者进程：想要修订或批注这本书的人。他们的操作会改变书的内容。

1. 规则分析：阅览室的“规章制度”

为了保护这本孤本，阅览室管理员制定了以下四条严格的规定：

1. 允许多个读者同时读：只要书没被修订，可以有很多个读者围在一起同时看。这不影响什么。
2. 只允许一个写者写：任何时候，最多只能有一个修订者在书上写字。
3. 写者工作时，不许任何人打扰：如果一个修订者正在工作，那么任何读者都不能来看，任何其他修订者也不能来写。必须保证修订过程的绝对独立。
4. 有读者在看时，写者必须等待：如果已经有一群读者在看书，那么新来的修订者必须在门外等待，直到所有读者都离开。

2. 初步尝试：最简单的“一刀切”方案

最简单的管理办法就是：阅览室一次只许进一个人，不管你是读者还是写者。

• 实现：设置一个互斥信号量 rw，初始值为1。
  • P(rw)：进门前申请。
  • V(rw)：出门后归还。
• 问题：这个方案虽然安全，但效率极低。它违反了规则1，明明可以多个读者一起看，现在却变成了读者也要一个个排队。这大大降低了阅览室的利用率。

3. 核心突破：引入“读者计数器”

为了实现“允许多个读者同时读”，我们需要知道当前有多少个读者在阅览室里。

• 思路：我们引入一个整数变量 count，初始为0，用来记录读者数量。
  • 第一个读者到来时，他有特殊的责任：他需要负责把阅览室的门锁上，防止任何写者进来。
  • 后续的读者到来时，发现门已经被第一个读者锁了（为读者们锁的），他们只需要把 count 加一，然后直接进去就行。
  • 读者离开时，也需要把 count 减一。
  • 最后一个读者离开时，他也有特殊的责任：他需要负责把阅览室的门打开，好让在外面等待的写者能有机会进来。

4. 再次碰壁：计数器本身的“互斥”问题

上面的思路很好，但在并发环境下，对 count 的“读-改-写”操作（比如 if(count==0) 然后 count++）不是原子的！

• 场景：

  1. 读者A执行 if(count==0)，发现条件成立。
  2. 此时发生切换，读者B也执行 if(count==0)，发现条件也成立。
  3. 结果：A和B都认为自己是“第一个”读者，他们俩都去执行了“锁门”操作（P(rw)）。第一个人锁成功了，第二个人就会被永远锁在门外。

• 解决方案：引入一个新的互斥信号量 mutex，初始值为1，专门用来保护对 count 变量的访问。任何想修改 count 的人，都得先拿到 mutex 这把“钥匙”。

5. “读者优先”的解决方案（会导致写者饿死）

结合以上思路，我们得到了第一个可行的、但有缺陷的方案。

semaphore rw = 1;      // 用于实现读写互斥，也叫“阅览室大门锁”
semaphore mutex = 1;   // 用于保护count变量的互斥锁
int count = 0;         // 读者计数器reader() {P(mutex);          // 1. 锁住计数器，准备修改if (count == 0) {  // 2. 如果我是第一个读者P(rw);         //    就负责锁上阅览室大门，阻止写者}count++;           // 3. 读者数量加一V(mutex);          // 4. 解锁计数器// --- 临界区 ---读文件...// --- 临界区 ---P(mutex);          // 5. 锁住计数器，准备修改count--;           // 6. 读者数量减一if (count == 0) {  // 7. 如果我是最后一个读者V(rw);         //    就负责打开阅览室大门，允许写者进入}V(mutex);          // 8. 解锁计数器
}writer() {P(rw);             // 1. 锁上阅览室大门// --- 临界区 ---写文件...// --- 临界区 ---V(rw);             // 2. 打开阅览室大门
}

• 问题所在（写者饿死）：
  • 假设一个写者正在等待 P(rw)。此时，阅览室里至少有一个读者（count>0），所以 rw 锁被占着。
  • 如果在这个时候，不断有新的读者到来。他们可以成功通过 P(mutex)，把 count 从1变成2，从2变成3... 他们根本不需要去碰那把被写者等待的 rw 锁。
  • 结果就是，只要有任何一个读者在阅览室里，后续源源不断的读者流都可以直接进入，而那个可怜的写者，就永远等不到 count 变成0的那一刻，永远也进不了门。这就是“读者优先”导致的“写者饿死”。

6. 最终解决方案：引入“写者优先”机制（读写公平法）

为了解决写者饿死的问题，我们需要一个机制，当一个写者在等待时，后续新来的读者不能“插队”。

• 思路：我们再增加一把“门外的大门锁” w，初始值为1。
  • 写者想写时，先锁上这把 w 锁。
  • 读者想读时，也得先尝试获取 w 锁。
• 这样，一旦一个写者在等待（即他已经成功执行了P(w)，但在等P(rw)），那么后续所有新来的读者都会被 P(w) 挡在门外，无法插队。他们只能等这个写者完成工作，释放了 w 锁之后，才能和其他等待的读者一起公平竞争。

最终的、读写相对公平的解决方案：

semaphore rw = 1;
semaphore mutex = 1;
semaphore w = 1;       // 新增的“写者优先”锁
int count = 0;reader() {P(w);              // (新增) 在读者队列外再加一道关卡P(mutex);if (count == 0) {P(rw);}count++;V(mutex);V(w);              // (新增) 读者进入后立刻释放w，允许其他读者或写者排队读文件...P(mutex);count--;if (count == 0) {V(rw);}V(mutex);
}writer() {P(w);              // 1. 写者优先获取w锁P(rw);             // 2. 再获取文件锁写文件...V(rw);V(w);              // 3. 写完后，释放两把锁
}

• 效果分析：
  • 这个方案并非绝对的“写者优先”，因为它不会抢占已经在读的读者。
  • 它实现的是一种相对公平的排队机制。当一个写者开始排队（执行P(w)）后，后续新来的读者也必须排在他后面，等待 w 锁。这保证了先来后到的公平性，避免了写者饥饿。因此也被称为读写公平法。

现在，我们来对这个被称为“读写公平法”的最终解决方案，进行一次详细、清晰的流程化文字介绍。

算法名称

读写公平法 (亦常被某些教材描述为一种“写者优先”的实现思路，但其效果更接近于公平排队)。

算法目标

在解决读者-写者问题的基础上，额外解决“读者优先”方案中可能出现的写者饥饿问题。其核心思想是：当一个写者已经表示了想要写入的意图后，后续新到达的读者不能“插队”抢先进入，必须等待该写者完成操作。

所需的信号量和变量

1. int count = 0;

   • 角色：读者计数器。
   • 作用：记录当前正在读取共享文件的读者进程数量。
   • 初始值：0，表示初始时没有读者。

2. semaphore mutex = 1;

   • 角色：互斥信号量。
   • 作用：专门用于保护共享变量 count 的访问。确保对 count 的检查和修改操作是原子的，防止多个读者并发修改 count 时出错。
   • 初始值：1，表示 count 的“修改权”可用。

3. semaphore rw = 1;

   • 角色：互斥信号量。
   • 作用：用于实现读者与写者之间、写者与写者之间的互斥。可理解为共享文件本身的“读写锁”。一旦被加锁，只有持有锁的进程（或一群读者）可以访问文件。
   • 初始值：1，表示文件当前可供访问。

4. semaphore w = 1;

   • 角色：同步/互斥信号量（关键所在）。
   • 作用：这是一个实现“公平排队”的关键信号量。它可以被看作是一个在所有读者和写者之上的、更高级别的“通行证”。它保证了当一个写者正在等待时，后续的读者无法越过它。
   • 初始值：1，表示“通行证”可用。

读者进程的详细执行流程

一个读者进程想要读取文件，需要执行以下步骤：

1. 申请“排队资格” (P(w)):

   • 在尝试读取之前，首先要申请w这个“通行证”。如果此时有一个写者正在写或正在等待，那么w锁很可能已经被占用，该读者就会在此处被阻塞，进入一个统一的等待队列。这一步确保了读者不会插队到已在等待的写者前面。

2. 锁住计数器 (P(mutex)):

   • 成功通过w关卡后，为了安全地修改读者计数器count，进程需要先获取mutex锁。

3. 判断并锁住文件（如果是第一个读者）:

   • 检查count的值。如果count == 0，说明自己是当前第一个到达的读者。作为“先锋”，它有责任通过执行P(rw)来锁住共享文件，以阻止任何写者进入。

4. 更新计数器 (count++):

   • 将count加一，表明现在阅览室里又多了一位读者。

5. 解锁计数器 (V(mutex)):

   • 对count的修改已经完成，立刻释放mutex锁，以便其他（已通过w关卡的）读者可以进来更新count。

6. 释放“排队资格” (V(w)):

   • 这是非常关键的一步。在进入读操作之前，读者会立刻释放w锁。这使得在它自己正在读书时，其他进程（无论是读者还是写者）可以继续竞争w锁并排队。如果不释放，就会变成一次只允许一个进程（或一批读者）通过，大大降低并发性。

7. 执行读操作 (reading is performed):

   • 这是读者的临界区。此时，文件锁rw已经被第一个读者锁上，可以安全地读取文件，并且允许多个读者同时处于这个阶段。

8. 锁住计数器（准备离开） (P(mutex)):

   • 读完后，准备离开。再次获取mutex锁，以安全地修改count。

9. 更新计数器 (count--):

   • 将count减一，表明有一位读者离开了。

10. 判断并解锁文件（如果是最后一个读者）:

    • 检查count的值。如果count == 0，说明自己是最后一个离开的读者。作为“殿后”者，它有责任通过执行V(rw)来解开文件锁，以便在外等待的写者可以进入。

11. 解锁计数器 (V(mutex)):

    • 对count的修改完成，释放mutex锁。读者进程的整个流程结束。

写者进程的详细执行流程

一个写者进程想要写入文件，流程相对简单，但权力更大：

1. 申请“排队资格” (P(w)):

   • 与读者一样，写者首先也需要获取w这个“通行证”。一旦它成功获取了w（或正在等待w），就能有效阻止新来的读者插队。

2. 锁住文件 (P(rw)):

   • 获取了w之后，接着申请对文件的“独占写权限”，即rw锁。此时，如果仍有读者在文件内（即rw锁被读者们持有），写者会在此处被阻塞，直到最后一个读者离开并执行V(rw)。

3. 执行写操作 (writing is performed):

   • 这是写者的临界区。此时，写者同时持有了w锁和rw锁，保证了没有任何其他读者或写者可以进入。

4. 解锁文件 (V(rw)):

   • 写操作完成，首先释放文件锁rw。

5. 释放“排队资格” (V(w)):

   • 最后释放w锁，允许在w上等待的其他进程（可能是读者也可能是写者）继续竞争。

通过这一套精密的、由多个信号量协同工作的流程，该算法在保证数据一致性的前提下，既允许多个读者并发读取，又通过一个公平的排队机制，有效避免了写者进程被饿死的问题。

必会题与详解

题目一：在“读者优先”的解决方案中，互斥信号量mutex的作用是什么？如果去掉它会发生什么？

答案详解：

1. mutex的作用：互斥信号量 mutex 在这里的作用是保护共享变量 count 的访问。对 count 的操作，如“检查 count 是否为0”和“count++”，在逻辑上必须是一个原子操作。P(mutex) 和 V(mutex) 将这两步操作捆绑在一起，确保在任何时刻只有一个读者能修改 count 的值。

2. 去掉mutex的后果：如果去掉 mutex，两个读者进程可能会并发地执行对 count 的修改，导致 count 值不正确，并可能引发死锁或互斥失效。

   • 一个典型的错误场景：
     1. 初始时 count = 0。
     2. 读者A执行 if (count == 0)，判断为真。
     3. 此时发生进程切换，读者B执行 if (count == 0)，判断也为真。
     4. 读者A继续执行，执行 P(rw) 成功，然后 count++，count 变为1。
     5. 切换回读者B，它也执行 P(rw)。但此时 rw 已经被A锁住，因此读者B被永久阻塞在了 P(rw) 这里，因为它错误地认为自己是第一个读者，而去尝试获取一个已经被占用的锁。

题目二：在最终的“读写公平”解决方案中，新增的信号量 w 是如何解决写者饥饿问题的？

答案详解：

信号量 w 解决写者饥饿问题的核心机制是建立了一个在所有读者和写者之上的、统一的“排队关卡”。

1. 形成排队：无论是读者还是写者，在真正尝试访问文件（或 count 变量）之前，都必须先通过 P(w) 这一关。这相当于在阅览室的大门口设置了一个取号机，保证了先来后到的基本顺序。

2. 阻止读者插队：

   • 当没有写者等待时，w 锁是开着的，读者可以自由通过。
   • 当一个写者到来并开始等待时，它会首先执行 P(w) 并成功获取 w 锁（或者被阻塞在 w 上）。一旦 w 锁被某个写者持有或等待，任何后续新来的读者在执行它们自己的 P(w) 时，都会被阻塞。
   • 这就阻止了读者无限插队的情况。新来的读者必须等到当前正在等待的写者（以及在他之前排队的进程）完成操作、释放了 w 锁之后，才有机会进入。

3. 实现公平：通过这种方式，w 保证了当一个写者已经“挂号”等待后，系统不会无视他而去服务那些后来的读者。这大大提高了写者被服务的机会，避免了饥饿，实现了读写进程间相对公平的竞争。

题目三：读者-写者问题和生产者-消费者问题在本质上有什么不同？

答案详解：

两者都是经典的同步互斥问题，但它们处理的“关系”有本质的不同。

1. 关系对称性不同：

   • 生产者-消费者问题是对称的。生产者之间是互斥的，消费者之间也是互斥的（因为它们都要操作同一个缓冲区指针或计数器），生产者和消费者之间也是互斥的。所有进程对缓冲区的访问都是完全互斥的。
   • 读者-写者问题是不对称的。读者和读者之间是共享的（可以并发），而写者与读者、写者与写者之间都是互斥的。这种不对称性使得其逻辑比前者复杂得多。

2. 解决核心不同：

   • 生产者-消费者的核心是资源（产品和空位）的计数与同步。它主要通过两个同步信号量（full 和 empty）来协调生产者和消费者的步调，防止从空缓冲区取或向满缓冲区放。
   • 读者-写者的核心是身份识别与权限管理。它需要区分进程是“读者”还是“写者”，并根据身份赋予不同的访问权限。其解决方案的核心是一个 count 计数器，用来动态地判断“第一个读者”和“最后一个读者”，从而实现复杂的、有条件的加锁和解锁。