读者-写者问题

问题描述
读者-写者问题（Reader-Writer Problem）是操作系统中一个经典的并发同步问题。它模拟了一种场景：多个进程（或线程）并发地访问一个共享数据区（如文件、数据库等），这些进程被分为两类：

1. 读者（Reader）：只读取数据，不会修改数据。
2. 写者（Writer）：会写入（修改）数据。

问题的核心在于需要保证同步，以满足以下要求：

• 正确性要求：
  1. 写写互斥：任意两个写者不能同时访问共享数据。
  2. 读写互斥：一个写者和一个读者也不能同时访问共享数据。
• 性能要求：
  1. 读读并发：多个读者可以同时访问共享数据，因为这不会导致数据不一致。
  2. 公平性：应避免读者或写者发生“饥饿”（Starvation）现象。例如，如果一直有新的读者到来，可能会导致写者长时间无法执行。

解题过程（解决方案的演进）

我们将从最简单的方案开始，逐步优化，最终实现一个公平的解决方案。

第一步：第一类读者-写者问题（读者优先）

这种方案优先考虑读者的并发性，但可能导致写者饥饿。

1. 核心思路：

   • 使用一个互斥锁（mutex）来保护一个计数器（read_count）。
   • 使用一个写锁（wrt）来实现写写互斥和读写互斥。
   • 计数器 read_count 用来记录当前正在读取的读者数量。

2. 需要的变量：

   • int read_count = 0; （当前活跃的读者数）
   • semaphore mutex = 1; （用于保护 read_count 的互斥锁）
   • semaphore wrt = 1; （用于写者之间、读者与写者之间的互斥锁）

3. 算法流程：

   写者进程：

   do {
       wait(wrt);   // 申请写锁
       // ... 执行写操作 ...
       signal(wrt); // 释放写锁
   } while (true);
   

   • 写者很简单，在写之前必须先独占 wrt 锁。只要持有这个锁，其他写者和读者都无法进入临界区。

   读者进程：

   do {
       wait(mutex);           // 申请修改 read_count 的权限
       read_count++;          // 增加读者计数
       if (read_count == 1) { // 如果我是第一个读者
           wait(wrt);         // 我需要去申请写锁，目的是为了阻塞写者
       }
       signal(mutex);         // 释放修改 read_count 的权限，允许其他读者进来修改计数
   
       // ... 执行读操作 ...   // 多个读者可以同时在此处读
   
       wait(mutex);           // 申请修改 read_count 的权限
       read_count--;          // 减少读者计数
       if (read_count == 0) { // 如果我是最后一个离开的读者
           signal(wrt);       // 释放写锁，允许写者进入
       }
       signal(mutex);         // 释放修改 read_count 的权限
   } while (true);
   

4. 工作原理解析：

   • 第一个读者：当第一个读者到来时，它会获取 wrt 锁。这之后到来的所有写者都会被阻塞在 wait(wrt) 上。
   • 后续读者：后续的读者在第一个读者之后到来，它们只会增加 read_count，而不会再去尝试获取 wrt 锁（因为 if (read_count == 1) 条件不成立），因此它们可以立即开始读操作。这样就实现了“读读并发”。
   • 读者离开：每个读者离开时都会减少计数。只有当最后一个读者离开时，才会释放 wrt 锁。
   • 写者饥饿：如果读者源源不断地到来（即在前一批读者全部离开之前，总有新的读者到达），那么 read_count 永远不会降为0，wrt 锁也就永远不会被释放，导致写者无限期等待（饥饿）。

第二步：第二类读者-写者问题（写者优先）

这种方案旨在提高写者的优先级，避免写者饥饿。当有写者在等待时，新到达的读者必须等待。

1. 核心思路：

   • 在“读者优先”的基础上，增加一个信号量（read_try）和一个计数器（write_count）及其保护锁。
   • read_try 信号量用于实现“写者优先”的规则：当有写者准备写时，它会阻止新的读者进入队列。

2. 需要的变量（在第一步基础上增加）：

   • int write_count = 0; （等待或正在写的写者数）
   • semaphore mutex2 = 1; （用于保护 write_count）
   • semaphore read_try = 1; （实现“写者优先”的关键信号量）

3. 算法流程：

   写者进程：

   do {
       wait(mutex2);          // 保护 write_count
       write_count++;
       if (write_count == 1) {
           wait(read_try);    // 第一个写者阻止新读者
       }
       signal(mutex2);
   
       wait(wrt);            // 申请写锁
       // ... 执行写操作 ...
       signal(wrt);          // 释放写锁
   
       wait(mutex2);
       write_count--;
       if (write_count == 0) {
           signal(read_try); // 没有写者了，允许新读者
       }
       signal(mutex2);
   } while (true);
   

   读者进程：

   do {
       wait(read_try);       // 尝试读，但可能被写者阻塞
       wait(mutex);
       read_count++;
       if (read_count == 1) {
           wait(wrt);
       }
       signal(mutex);
       signal(read_try);     // 一旦进入准备读的状态，就释放 read_try
   
       // ... 执行读操作 ...
   
       wait(mutex);
       read_count--;
       if (read_count == 0) {
           signal(wrt);
       }
       signal(mutex);
   } while (true);
   

4. 工作原理解析：

   • 写者到来：第一个写者会获取 read_try 锁。这之后新来的读者会被阻塞在 wait(read_try)，无法进入排队序列，从而实现了写者优先。
   • 现有读者：在写者到来之前已经开始读的读者，或者已经通过 wait(read_try) 的读者，可以继续执行。但新的读者必须等待。
   • 这解决了写者饥饿问题，但可能会导致读者饥饿（如果写者源源不断）。

第三步：公平的读者-写者问题

最公平的解决方案是遵循“先来先服务”原则，无论是读者还是写者。这可以通过一个额外的互斥信号量来实现。

1. 核心思路：

   • 使用一个全局的排队信号量（queue）。所有进程（读者和写者）在尝试访问共享数据前，都必须先在这个信号量上排队。
   • 这个信号量不关心你是读者还是写者，只保证申请的先后顺序。

2. 需要的变量：

   • semaphore queue = 1; （全局排队锁）
   • semaphore wrt = 1; （写锁）
   • int read_count = 0;
   • semaphore mutex = 1; （保护 read_count）

3. 算法流程：

   写者进程：

   do {
       wait(queue);   // 进入全局队列
       wait(wrt);     // 申请写锁
       signal(queue); // 释放队列锁，允许后面的人排队
   
       // ... 执行写操作 ...
   
       signal(wrt);   // 释放写锁
   } while (true);
   

   读者进程：

   do {
       wait(queue);   // 进入全局队列
   
       wait(mutex);
       read_count++;
       if (read_count == 1) {
           wait(wrt); // 第一个读者申请写锁
       }
       signal(mutex);
   
       signal(queue); // 释放队列锁，允许后面的人排队
   
       // ... 执行读操作 ...
   
       wait(mutex);
       read_count--;
       if (read_count == 0) {
           signal(wrt); // 最后一个读者释放写锁
       }
       signal(mutex);
   } while (true);
   

4. 工作原理解析：

   • 公平性：queue 信号量形成了一个“走廊”。无论是读者还是写者，都必须先在这个“走廊”排队。这就保证了严格的先来先服务。
   • 例如，如果执行顺序是 读者A -> 写者B -> 读者C：
     1. 读者A先拿到 queue 锁，然后拿到 wrt 锁，之后释放 queue 锁，开始读。
     2. 写者B到达，它拿到了释放后的 queue 锁，但随后尝试获取 wrt 锁时被阻塞（因为读者A正拿着），于是写者B在 queue 锁后等待。
     3. 读者C到达，它尝试获取 queue 锁，但此时锁在写者B手里，所以读者C被阻塞在 queue 上。
     4. 读者A读完，释放 wrt 锁。
     5. 被阻塞的写者B获得 wrt 锁，执行写操作，写完后再释放 wrt 和 queue 锁。
     6. 读者C终于拿到 queue 锁，然后开始它的流程。
   • 这种方式有效地防止了任何一方的饥饿，实现了公平访问。