王道操作系统笔记，视频链接：2.3.5.2 读者-写者问题

问题描述

1. 问题描述：
   • 有读者和写者两组并发进程，共享一个文件，
   • 当两个或两个以上的读进程同时访问共享数据时不会产生副作用，
   • 但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。
   • 因此要求：
     • ①允许多个读者可以同时对文件执行读操作；
       • 与消费者进程不同，读者进程在读数据后并不会将数据清空，并不会改变数据，因此多个读者可同时访问共享数据
     • ②只允许一个写者往文件中写信息；
     • ③任一写者在完成写操作之前不允许其他读者或写者工作；
       • 读进程与写进程同时共享数据，可能导致读出的数据不一致的问题
       • 两个写进程同时共享数据，可能导致数据错误覆盖的问题
     • ④写者执行写操作前，应让已有的读者和写者全部退出。
2. 问题分析：
   - 两类进程：写进程、读进程
   - 互斥关系：写进程—写进程、写进程—读进程。读进程与读进程不存在互斥问题。
3. 第一步实现：

semaphore rw=1;      //用于实现对共享文件的互斥访问
int count = 0;       //记录当前有几个读进程在访问文件
writer (){
    while(1){
        P(rw);        //写之前“加锁”
        写文件...
        V(rw);        //写完了“解锁”
    }
}
reader (){
    while(1){
        if (count==0)      //由第一个读进程负责
            P(rw);         //读之前“加锁”
        count++;           //访问文件的读进程数+1
        读文件...
        count--;           //访问文件的读进程数-1
        if (count==0)      //由最后一个读进程负责
            V(rw);         //读完了“解锁”
    }
}
// 该代码实现了多个读者同时读文件，
// 但是由于if语句与P、V操作无法一气呵成，
// 所以可能导致多个读进程同时认为自己是第一个读进程，从而“加锁”
// 于是我们引入mutex，用于对count变量的互斥

4. 第二步实现：

semaphore rw=1;      //用于实现对共享文件的互斥访问
int count = 0;       //记录当前有几个读进程在访问文件
semaphore mutex = 1; //用于保证对count变量的互斥访问
writer (){
    while(1){
        P(rw);        //写之前“加锁”
        写文件...
        V(rw);        //写完了“解锁”
    }
}
reader (){
    while(1){
        P(mutex);          //各读进程互斥访问count
        if (count==0)      //由第一个读进程负责
            P(rw);         //读之前“加锁”
        count++;           //访问文件的读进程数+1
        V(mutex);
        读文件...
        P(mutex);          //各读进程互斥访问count
        count--;           //访问文件的读进程数-1
        if (count==0)      //由最后一个读进程负责
            V(rw);         //读完了“解锁”
        V(mutex);
    }
}
// 该代码解决了多个读进程冲突访问count的情况，逻辑上可行
// 但是依然存在潜在的问题：
// 只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”。
// 因此，这种算法中，读进程是优先的
// 所以，我们引入另一个信号量w，用于实现“写优先”

5. 第三步实现：

semaphore rw=1;      //用于实现对共享文件的互斥访问
int count = 0;       //记录当前有几个读进程在访问文件
semaphore mutex = 1; //用于保证对count变量的互斥访问
semaphore w = 1;     //用于实现“写优先”
writer () {
    while(1) {
        P(w);
        P(rw);
        写文件...
        V(rw);
        V(w);
    }
}
reader () {
    while(1) {
        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);
    }
}

6. 关于第三步实现的几种情况：
   • 分析以下并发执行 P(w) 的情况：（前几个略，可以自己慢慢分析）
   • 读者1→读者2
   • 写者1→写者2
   • 写者1→读者1
   • 读者1→写者1→读者2
   • 写者1→读者1→写者2
     • 因为读写都以P(w)开头，所以写者1没运行完之前，读者1、写者2都会被阻塞在P(w)
     • 因为记录型信息量会有一个阻塞队列，所以实际上写者1运行完后，会先唤醒读者1
     • 结论：
       • 在这种算法中，连续进入的多个读者可以同时读文件；
       • 写者和其他进程不能同时访问文件；
       • 写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务原则。
       • 有的书上把这种算法称为“读写公平法”
7. 真正的“写优先”算法：
   • 这里只是举个例子，写优先算法不止这一个。

semaphore rw=1;      //用于实现对共享文件的互斥访问
int count = 0;       //记录当前有几个读进程在访问文件
semaphore mutex = 1; //用于保证对count变量的互斥访问
semaphore w = 1;     //用于实现“写优先”的门控信号量

int write_count = 0;      // [新增] 记录当前等待或正在写的写进程数量
semaphore w_mutex = 1;    // [新增] 用于保护 write_count 变量的互斥访问

writer () {
    while(1) {
        P(w_mutex);                      // [新增] 互斥访问 write_count
        // [修改] 只有第一个写进程才执行 P(w) 关门，阻止新读者
        if (write_count == 0)            
            P(w);
        write_count++;                   // [新增] 写进程数量+1
        V(w_mutex);                      // [新增]
        P(rw);
        写文件...
        V(rw);
        P(w_mutex);                      // [新增] 互斥访问 write_count
        write_count--;                   // [新增] 写进程数量-1
        // [修改] 只有当最后一个写进程离开时，才执行 V(w) 开门，允许读者进入
        if (write_count == 0)            
            V(w);
        V(w_mutex);                      // [新增]
    }
}

reader () {
    while(1) {
        P(w);
        P(mutex);
        if(count==0)
            P(rw);
        count++;
        V(mutex);
        V(w);
        读文件...
        P(mutex);
        count--;
        if(count==0)
            V(rw);
        V(mutex);
    }
}
// 其实和读优先差不多，额外设置了write_count和w_mutex
// 用于控制让第一个写进程上锁，
// 最后一个写进程释放锁，
// 所以这种方法写进程一直到来时，会导致读进程“饥饿”
// 是真正的“写优先”

知识回顾与重要考点

1. 读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路：
   • 其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。
   • 我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。
   • 另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。
     • 这里的“一气呵成”和原语的开关中断不同，开关中断不会切换进程，这个会，只是保证了同一时间段只有一个进程能修改访问某变量。
   • 最后，还要认真体会我们是如何解决“写进程饥饿”问题的。
   • 绝大多数的考研PV操作大题都可以用之前介绍的几种生产者—消费者问题的思想来解决，
   • 如果遇到更复杂的问题，可以想想能否用读者—写者问题的这几个思想来解决。