读者写者问题

问题描述

有一组读者进程和一组写者进程，共享一个文件。有如下要求：

• 允许多个读者可以同时对文件执行读操作
• 只允许一个写者往文件中写信息
• 任一写者在完成写操作之前，不允许其他读者或写者工作
• 写者在执行任务之前，应让已有的读者和写者全部退出
• 额外要求：要求同时访问共享文件的读者数不超过 n(n>=1)

问题分析

• 一个初值为 0 的 int 型变量 readers，记录当前正在访问共享文件的读者数量
• 既然多个读者进程都可以修改 readers，那么对于 readers 的访问也应该是互斥的，所以需要一个初值为 1 的信号量 r_mutex，用于对 readers 的互斥访问
• 为了满足额外要求，需要一个初值为 n 的信号量 n_r_mutex，用于控制同时访问共享文件的读者数量不超过 n
• 一个初值为 1 的信号量 rw_mutex 控制读者与写者之间、写者与写者之间对共享文件的互斥访问

为了实现写者优先，我们还需要：

• 一个初值为 0 的 int 型变量 writers，记录当前试图访问共享文件的写者数量
• 类似的，我们需要一个初值为 1 的信号量 w_mutex，控制写者进程对于 writers 的互斥访问
• 为了实现读者优先，需要一个初值为 1 的信号量 queue，表示当前正在排队的写者数量。如果 queue 为 0，表明现在存在正在排队的写者进程，此时没有读者进程可以开始执行，以实现写者优先。

为了实现读写公平，我们可以复用 queue

问题解决

读者优先

int readers = 0;
semaphore r_mutex = 1;
semaphore n_r_mutex = n;
semaphore rw_mutex = 1;

process reader() {
    while (1) {
        P(n_r_mutex);
        V(r_mutex); // 当要修改readers时，需要互斥访问
        if (readers == 0) {
            P(rw_mutex); // 第一个尝试访问共享文件的读进程负责获取文件的互斥锁
        }
        readers++;
        V(r_mutex); // 对于readers的访问结束，释放锁
        // 执行读文件的方法
        read_file();
        // 读文件结束，更改计数器，需要互斥访问
        P(r_mutex);
        readers--;
        if (readers == 0) {
            V(rw_mutex); // 最后一个结束的读者进程负责恢复对于文件的访问
        }
        V(r_mutex);
        V(n_r_mutex);
    }
}

process writer() {
    while (1) {
        P(rw_mutex);
        // 开始写文件
        write_file();
        // 写文件结束，释放锁
        V(rw_mutex);
    }
}

这种算法之所以称为读者优先，是因为当存在读进程时，写操作将被延迟，且只要有一个读进程尚未结束，即 readers > 0时，随后而来的读进程都将被允许在写进程之前访问文件。这可能会导致写进程迟迟不能访问文件而出现「饿死」的现象

写者优先

int readers = 0;
int writers = 0;
semaphore r_mutex = 1;
semaphore w_mutex = 1;
semaphore n_r_mutex = n;
semaphore rw_mutex = 1;
semaphore queue = 1;

process reader() {
    while (1) {
        P(n_r_mutex);
        P(queue);
        
        P(r_mutex);
        if (readers == 0) {
            P(rw_mutex);
        }
        readers++;
        V(r_mutex);
        V(queue);
        
        read_file();
        
        P(r_mutex);
        writers--;
        if (writers == 0) {
            V(rw_mutex);
        }
        V(r_mutex);
        
        V(n_r_mutex);
    } 
}

process writer() {
    while (1) {
        P(w_mutex);
        if (writers == 0) {
            P(queue);
        }
        writers++;
        V(w_mutex);
        
        P(rw_mutex);
        write_file();
        V(rw_mutex);
        
        P(w_mutex);
        writers--;
        if (writers == 0) {
            V(queue);
        }
        V(w_mutex);
    }
}

这种算法之所以称为写者优先，是因为当前排队的进程中，如果在某个读进程之前，存在写进程，那么后续排队的写进程将优先于读进程进行。这可能会导致读进程迟迟不能访问文件呢而出现「饿死」的现象。

再思考一种情况，如果先有几个读进程开始执行了，此时到达一个写进程的请求，那么当这几个读进程执行完毕后，写进程将立即执行。并且，与读者优先算法类似，如果有任何一个写进程尚未结束，即 writers>0 时，任何后续的读进程都得不到执行

尽管是写者优先算法，但是根据要求（写进程只有在正在执行的其他进程全部执行完毕后才能继续执行），仍然要等待当前仍在执行的全部读者进程执行完毕后，写进程才能继续执行

读写公平

int readers = 0;
int writers = 0;
semaphore r_mutex = 1;
semaphore w_mutex = 1;
semaphore n_r_mutex = n;
semaphore rw_mutex = 1;
semaphore queue = 1;

process reader() {
    P(n_r_mutex);
    P(queue);
    
    P(r_mutex);
    if (readers == 0) {
        P(rw_mutex);
    }
    readers++;
    V(r_mutex);
    V(queue);
    
    read_file();
    
    P(r_mutex);
    readers--;
    if (readers == 0) {
        V(rw_mutex);
    }
    V(r_mutex);
    
    V(n_r_mutex);
}

process writer() {
    P(queue);
    P(rw_mutex);
    
    write_file();
    
    V(rw_mutex);
    V(queue);
}

这种算法中，当有读进程正在读共享文件时，如果出现写进程请求访问，那么会禁止后续读进程的请求，等到当前剩余的读进程执行完毕后，立即让写进程执行，只有在后续无写进程执行的情况下，才允许新的读进程执行。可以实现读写进程的轮流访问