408 操作系统

Appearance

读者-写者问题 ​

考情分析 ​

读者-写者问题是 408 真题中的高频同步问题，常考读者优先方案的 PV 操作和 readcount 的互斥保护。🔥🔥🔥 高频核心。

数据库被很多人同时查询没问题，但一旦有人要修改数据，就必须独占——不能一边改一边让别人读到写了一半的脏数据。这种"读共享、写互斥"的场景，就是读者-写者问题。

问题描述 ​

  • 多个读者可以同时读取共享数据
  • 写者必须独占访问——写时不能有其他读者或写者
  • 读者和写者不能同时访问
关系说明
读者-读者不互斥（可以同时读）
读者-写者互斥
写者-写者互斥

读者优先方案 ​

semaphore rw_mutex = 1;   // 读写互斥信号量
semaphore mutex = 1;      // 保护 readcount 的互斥
int readcount = 0;        // 当前读者数量

// 写者进程
writer() {
    P(rw_mutex);          // 申请写权限
    写操作;
    V(rw_mutex);          // 释放写权限
}

// 读者进程
reader() {
    P(mutex);             // 保护 readcount
    readcount++;
    if (readcount == 1)   // 第一个读者到达
        P(rw_mutex);      // 阻止写者
    V(mutex);

    读操作;               // 多个读者可以同时读

    P(mutex);             // 保护 readcount
    readcount--;
    if (readcount == 0)   // 最后一个读者离开
        V(rw_mutex);      // 允许写者
    V(mutex);
}

关键点分析 ​

  • readcount 是共享变量，需要用 mutex 保护
  • 第一个读者到达时执行 P(rw_mutex) 锁住写者
  • 最后一个读者离开时执行 V(rw_mutex) 放行写者
  • 读者在读操作期间不持有 mutex，因此多个读者可以同时读

读者优先的问题 ​

如果不断有新读者到达，readcount 始终不为 0，写者可能永远等不到机会 → 写者饥饿。

读写公平方案 ​

增加一个信号量 w，让写者可以「排队」：

semaphore rw_mutex = 1;
semaphore mutex = 1;
semaphore w = 1;          // 新增：用于实现公平
int readcount = 0;

writer() {
    P(w);                 // 在 w 上排队
    P(rw_mutex);
    写操作;
    V(rw_mutex);
    V(w);
}

reader() {
    P(w);                 // 在 w 上排队
    P(mutex);
    readcount++;
    if (readcount == 1)
        P(rw_mutex);
    V(mutex);
    V(w);                 // 立即释放 w，让后续进程排队

    读操作;

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

这样写者到达后，后续的读者会在 P(w) 上等待，写者不会永远等待。

交互可视化 ​

加载可视化中...

考研高频考点 ​

  • 🔥🔥🔥 读者优先方案的完整 PV 操作（必须会默写）
  • 🔥🔥🔥 readcount 需要用 mutex 保护的原因
  • 🔥🔥🔥 第一个读者 P(rw_mutex)、最后一个读者 V(rw_mutex) 的逻辑
  • 🔥🔥 读者优先方案中写者可能饥饿
  • 🔥 读写公平方案的思路

读者-写者问题是两类角色的互斥。下一篇看一个更极端的场景——哲学家进餐问题，多个进程争夺多个资源，直接引出死锁。

相关文章