PV经典问题之读写者问题
问题描述
有一个许多进程共享的数据区,这个数据区可以是一个文件或者主存 的一块空间;有一些只读取这个数据区的进程(Reader)和一些只往数据区写数据的进 程(Writer),此外还需要满足以下条件:
(1)任意多个读进程可以同时读这个文件;
(2)一次只有一个写进程可以往文件中写;
(3)如果一个写进程正在进行操作,禁止任何读进程度文件。
读者优先算法
关系分析:由题⽬分析可知,读者和写者是互斥的,写者和写者也是互斥的,⽽读者和读者不存在互斥问题。
整理思路:写者是⽐较简单的,它与任何线程互斥,⽤互斥信号量的 PV 操作即可解决。读者的问题⽐较复杂,它 必须实现与写者的互斥,多个读者还可以同时读。所以,在这⾥⽤到了⼀个计数器,⽤它来判断当前是否有读者读 ⽂件。当有读者的时候写者是⽆法写⽂件的,此时读者会⼀直占⽤⽂件,当没有读者的时候写者才可以写⽂件。同 时,不同的读者对计数器的访问也应该是互斥的。
故问题完整解答如下(读进程优先算法):
设置⼀个计数变量count,⽤来记录当前的读者数量,初值为0;
设置互斥信号量mutex,⽤于保护更新count变量时的互斥,初值为1;
设置互斥信号量rw⽤于保证读者和写者的互斥访问,初值为1。
int count = 0; //⽤用于记录当前的读者数量量
semaphore mutex = 1; //⽤用于保护更更新count变量量时的互斥 semaphore rw = 1; //⽤用于保证读者和写者互斥地访问⽂文件
writer () { //写者进程
while (1) {
P(rw); //互斥访问共享⽂文件
Writing; //写⼊入
V(rw); //释放共享⽂文件
}
}
reader () { // 读者进程
while (1) {
P(mutex); //互斥访问count变量量
if (count == 0) { //当第⼀一个读进程读共享⽂文件时
P(rw); //阻⽌止写进程写
}
count++; //读者计数器器加1
V(mutex); //释放互斥变量量count
reading; //读取
P(mutex); //互斥访问count变量量
count--; //读者计数器器减1
if (count == 0) { //当最后⼀一个读进程读完共享⽂文件
V(rw); //允许写进程写
}
V(mutex); //释放互斥变量量count
}
}
问题解答分析: 在上⾯的算法中,读进程是优先的,也就是说,当存在读进程时,写操作将被延迟,并且只要有⼀个读进程 活跃,随后⽽来的读进程都将被允许访问⽂件(读者插队)。这样的⽅式下,会导致写进程可能长时间等待, 且存在写进程“饿死”的情况。 为什么需要设置互斥信号量mutex,⽤于保护更新count变量时的互斥呢? 分析如下: 如果没有设置互斥信号量mutex,那么可能存在多个读者进程同时访问count变量,这样的话,可能 导致多次P(rw);操作⽽使得写进程长时间⽆法访问⽂件,并且此时的count计数变量的值可能也会不 准确。
写者优先算法
算法描述如下:
1、只要有⼀个写者申请写数据,则不再允许新的读者进⼊读数据
2、写者会插队
故问题完整解答如下:
设置⼀个计数变量readercount,⽤来记录当前的读者数量,初值为0;
设置⼀个计数变量writercount,⽤于控制rsem信号量,初值为0;
设置互斥信号量rmutex,⽤于保护更新readercount变量时的互斥,初值为1;
设置互斥信号量wmutex,⽤于控制对writercount的互斥加减操作,初值为1;
设置互斥信号量rw⽤于保证读者和写者的互斥访问,初值为1。
设置互斥信号量rsem,当⾄少有⼀个写者申请写数据时互斥新的读者进⼊读数据,初值为1。
解决该问题的代码如下:
int readercount = 0; //⽤用于记录当前的读者数量量
int writercount = 0; //⽤用于控制rsem信号量量
semaphore rmutex = 1; //⽤用于保护更更新readercount变量量时的互斥 semaphore wmutex = 1; //⽤用于保护更更新writercount变量量时的互斥
semaphore rw = 1; //⽤用于保证读者和写者互斥地访问⽂文件
semaphore rsem = 1; //当⾄至少有⼀一个写者申请写数据时互斥新的读者进⼊入读数据
writer() {
while (1) {
P(wmutex);
if (writercount == 0) {
P(rsem);
}
writercount++;
V(wmutex);
P(rw);
writing;
V(rw);
P(wmutex);
writercount--;
if (writercount == 0) {
V(rsem);
}
V(wmutex);
}
}
reader() {
while (1) {
P(rsem);
P(rmutex);
if (readercount == 0) {
P(rw);
}
readercount++;
V(rmutex);
V(rsem);
reading;
P(rmutex);
readercount--;
if (readercount == 0) {
V(rw);
}
V(rmutex);
}
}
读写公平算法
读写公平算法即当有读进程正在读共享⽂件时,有写进程请求访问,这时应禁⽌后续读进程的请求,等待到已在共 享⽂件的读进程执⾏完毕则⽴即让写进程执⾏。同时读写公平算法也要遵循”先来后到“的准则,当⼀个写进程访问 ⽂件时,如果先有⼀些读进程要求访问⽂件, ⽽再有另⼀个写讲程要求访问⽂件,那么当当前访问⽂件的进程结 束对⽂件的写操作时,会是个读进程占⽤⽂件⽽不是写进程(在信号量w的阻塞队列上,因为读进程先来,⽽排在 阻塞队列队⾸,⽽V操作唤醒进程时唤醒的是队⾸进程)。
故问题完整解答如下:
设置⼀个计数变量count,⽤来记录当前的读者数量,初值为0;
设置互斥信号量mutex,⽤于保护更新count变量时的互斥,初值为1;
设置互斥信号量rw⽤于保证读者和写者的互斥访问,初值为1;
设置信号量w以实现读者写者之间的读写公平,初值为1。
代码如下:
int count = 0; //⽤用于记录当前的读者数量量
semaphore mutex = 1; //⽤用于保护更更新count变量量时的互斥
semaphore rw = 1; //⽤用于保证读者和写者互斥地访问⽂文件
semaphore w = 1; //⽤用于实现读者写者之间的读写公平
writer () { //写者进程
while (1) {
P(w);
P(rw); //互斥访问共享⽂文件
Writing; //写⼊入
V(rw); //释放共享⽂文件
V(w);
}
}
reader () { // 读者进程
while (1) {
P(w);
P(mutex); //互斥访问count变量量
if (count == 0) { //当第⼀一个读进程读共享⽂文件时
P(rw); //阻⽌止写进程写
}
count++; //读者计数器器加1
V(mutex); //释放互斥变量量count
V(w);
reading; //读取
P(mutex); //互斥访问count变量量
count--; //读者计数器器减1
if (count == 0) { //当最后⼀一个读进程读完共享⽂文件
V(rw); //允许写进程写
}
V(mutex); //释放互斥变量量count
}
}