操作系统中的进程同步：读者-写者问题的读写锁实现

题目描述

读者-写者问题（Reader-Writer Problem）是进程同步中的经典场景，要求保证多个进程（线程）对共享资源（如文件、内存区）的访问满足以下条件：

1. 允许多个读者同时读取资源。
2. 同一时间只允许一个写者写入资源，且写入时禁止任何读者或其他写者访问。
3. 避免写者饥饿（即写者不会因读者持续到来而无限等待）。

本题重点讨论如何通过读写锁（Read-Write Lock）实现这一需求，并分析其公平性策略。

解题过程

1. 基本读写锁的设计

读写锁需要维护两种状态：

• 读者计数（read_count）：当前正在读取的进程数量。
• 写者标志（write_flag）：是否有写者正在写入。

通过互斥锁保护共享变量：

• mutex：保护read_count的原子性。
• wrt：写者独占锁，用于阻塞其他写者和读者。

伪代码实现（初版，可能导致写者饥饿）：

// 全局变量  
int read_count = 0;  
semaphore mutex = 1;  // 保护read_count  
semaphore wrt = 1;    // 写者锁  

// 读者进程  
void reader() {  
    wait(mutex);        // 申请read_count的访问权  
    read_count++;  
    if (read_count == 1)  
        wait(wrt);      // 第一个读者阻塞写者  
    signal(mutex);      // 释放read_count的访问权  

    // 执行读取操作  

    wait(mutex);  
    read_count--;  
    if (read_count == 0)  
        signal(wrt);    // 最后一个读者释放写者锁  
    signal(mutex);  
}  

// 写者进程  
void writer() {  
    wait(wrt);          // 申请写者锁  
    // 执行写入操作  
    signal(wrt);  
}  

问题：若读者持续到达，read_count始终不为0，写者可能无限等待（写者饥饿）。

2. 解决写者饥饿的公平策略

引入排队机制，确保先到达的进程（读者或写者）优先获得资源。常用方法：

• 增加一个信号量queue，所有进程先申请queue，再按类型分配资源。

公平读写锁伪代码：

semaphore queue = 1;   // 公平排队锁  
// 其他变量同上  

void reader() {  
    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);  
}  

void writer() {  
    wait(queue);        // 写者排队  
    wait(wrt);          // 直接申请写者锁  
    signal(queue);      // 释放排队锁（写者已获得wrt，无需继续排队）  

    // 写入操作  

    signal(wrt);  
}  

关键改进：

• queue信号量强制所有进程按到达顺序排队，避免读者“插队”导致写者饥饿。
• 写者获得wrt后释放queue，允许后续读者或写者进入排队。

3. 读写锁的变体与权衡

实际实现中需根据场景权衡读者和写者的优先级：

• 读者优先：上述初版方案，适合读多写少的场景，但可能写者饥饿。
• 写者优先：当写者等待时，阻塞新读者（如通过额外信号量），适合写操作要求及时性的场景。
• 公平策略：如上文的排队方案，保证先到先服务，但增加了锁开销。

总结

读写锁通过分离读、写操作的需求，提高了并发性能。实现时需注意：

1. 读者计数需通过互斥锁保护其原子性。
2. 写者锁需在第一个读者到达时申请，最后一个读者离开时释放。
3. 公平性通过排队机制解决写者饥饿问题，但可能降低吞吐量。

理解读写锁的实现有助于设计高并发场景下的数据访问策略，如数据库事务管理、文件系统缓存同步等。