读者写者问题详解操作系统

2.16 读者写者问题

抽象解释

多个进程访问一个共享的数据区
读者（读进程）只能读数据，写者（写进程）只能写数据
适用于数据库、文件、内存、寄存器等数据区的访问模型
如12306购票系统，由于用户量庞大和数据量巨大，不可避免地会出现多个进程同时查询（读）或修改（写）同一条数据的情况

2.16.1 读者写者问题的三个约束条件

读者之间不互斥（你和室友可以同时查看元旦那天早上7点的高铁信息）
写者之间必须互斥（你和室友不能同时申请购买元旦那天早上七点G1234的6D号位置）
读者写者之间也互斥（假如你正在买G1234的6D座位，你的室友无法读到该位置的售票信息）

2.16.2 读者写者问题VS生产者消费者问题

能不能用生产者消费者问题解决读者写者问题？

不能
像生/消问题那样严格互斥读者写者虽然可以保证数据的正确，却无法实现同时读的特点

如何判断一个问题是生产者消费者问题，还是读者写者问题？

生产者消费者问题：数据消费后就没有了；读者写者问题：数据可多次读
生产者消费者问题：消费者彼此互斥；读者写者问题：读者可以同时读

2.16.3 解决读者写者问题的三种方案

策略一读者优先

有读者在读的话，随后的读者可以进入临界区一起读
待临界区全部读者退出后再轮到下一个写者
有越过写者的现象，造成写者饥饿

变量设置

wsem：互斥信号量
readcount：统计同时读的readers
x：对readcount的修改加锁

伪代码

	int readcount=0；semaphore x = 1, wsem=1;void reader() { while (1) {P(x);readcount++;
Ⅰ	  if (readcount==1) P(wsem); //第一个读者会执行此if语句，随后的会跳过P(wsem)直接进入临界区
Ⅱ	  V(x);READ;P(x);readcount--;
Ⅲ	   if (readcount==0) V(wsem);//最后退出的读者执行此语句，释放临界区权限
Ⅳ	  V(x);}}void writer() {while (1) {P(wsem);WRITE;V(wsem);}}

读者优先的相关思考

Ⅰ、Ⅱ语句能否互换？
答：不能，readcount的判断一定要在锁内，否则会出现读写不互斥：假设此时写者在临界区，第一个读者到来后readcount++，阻塞在P（wsem），第二个读者到来后直接可以修改count++，导致跨过P（wsem）直接进入临界区，读写不互斥。这时失去的条件是：先有一个读者进入临界区时等其进入后后面的读者才能修改count。
Ⅲ、Ⅳ语句能否互换？
答：不能，交换后考虑最后一个进程退出时又到来一个读者进程的情况：交换后readcount=0，尚未判断if时，读者仍会进入临界区，判断后释放临界区权限，写者也进入临界区，这时读写不互斥。这时失去的条件是:最后一个读者退出临界区时等其退出后才能修改count
考虑如下进程序列(设序列中从右到左为进程先后到达顺序)，下列哪一种情况下可能存在写者饥饿
1.R R R
2.W W W
3.R W
4.R R W
5.R R W R
6.W W R
7.W R R W
答：5.RRWR时有一个R先到临界区，后面的读者进程在等待时会越过P（wsem）直接进入临界区，也就是越过了W，造成写者饥饿

策略二公平优先

有读者在读的话，下一个写者之前的读者可以进入临界区一起读
写过程中，其他到来的进程按顺序处理
没有越过写者的现象，不会造成写者饥饿

变量设置

wsem：互斥信号量
readcount：统计同时读的readers
x：对readcount的修改加锁
wrsem：互斥信号量，reader和writer在这里排队，用处是在读者优先的基础上，不让读者越过写者

伪代码

	int readcount=0, semaphore x=l, wrsem=1, wsem=l;
void reader() {while (true) {P(wrsem);P(x);readercount++;if (readercount == 1)P(wsem);V(x);V(wrsem);READ;P(x);readercount--;if (readercount == 0)V(wsem);V(x);}
}
void writer() {while (true) {P(wrsem);P(wsem);WRITE;V(wsem);V(wrsem);}
}

与读者优先相比

在读者优先中，wsem只对第一个读者起阻塞作用，后续读者不受其影响。为了保证按照到达顺序处理，故公平优先方式设置wrsem,读者／写者按到达顺序在wrsem上排队。

策略三写者优先

有写者声明要写时，不允许读者再进入临界区
降低了并发度
有越过读者的现象，会造成读者饥饿

变量设置

rsem：互斥信号量，当至少有一个写者申请写数据时，互斥新的读者进入读数据
第一个写者受rsem影响，一旦有第一个写者，后续写者不受rsem其影响。但是读者需要在rsem上排队
writecount：用于控制rsem对写者的控制
y：对writecount的修改加锁

伪代码

int readcount = 0, writecount = 0;
semaphore x=l, y= 1, wsem=1, rsem=l;void reader( ) {while (1) {P(rsem);P(x);readcount++;if (readcount ==1) P(wsem);V(x);V(rsem)；READ;P(x);readcount--;if (readcount ==0) V(wsem);V(x);}}
void writer( ) {while (1) {P(y);writecount++;if (writecount ==1) P(rsem);V(y);P(wsem);WRITE;V(wsem);P(y);writecount--;if (writecount==0) V(rsem);V(y);}
}

与公平优先相比

在公平优先中，读者和写者都会受到wrsem的限制，而写者优先中，由于增加了if (writecount ==1) P(rsem)的语句，当写者到来时会比读者优先进入临界区，但WRRRR的情况写者不会优先

策略四写者优先改进

为了解决WRRRR中W不能优先的问题

变量设置

沿用写者优先的变量
增加z信号量，仅对写者有作用，让读者队列在z上排队，只有一个读者在rsem上排队

伪代码

int readcount=0,writecount=0; 
semaphore x=l, y= 1,z=1,wsem=1,rsem=l;void reader( ) {while (1) {P(z);P(rsem);P(x);readcount++;if (readcount ==1) P(wsem);V(x);V(rsem)；V(z);READ;P(x);readcount--;if (readcount ==0) V(wsem);V(x);}}
void writer( ) {while (1) {P(y);writecount++;if (writecount ==1) P(rsem);V(y);P(wsem);WRITE;V(wsem);P(y);writecount--;if (writecount==0) V(rsem);V(y);}
}

写者优先改进方法的思考

z信号量起到了什么作用？

在rsem上不允许建造读进程的长队列，否则写进程将不能跳过这个队列.
允许一个读进程在rsem上排队,其他读进程在信号量z上排队

P(z)和P(rsem)能否互换位置？
不能，否则P(z)失去限制作用

2.16.4 读者写者问题示例

示例一

情境描述

东西方向的独木桥，仅容一人过，不允许停留
东西方向都有人在等着过桥

请用P、V操作来实现东西两端行人过桥问题

分析

简单的写者互斥问题
多个写者共享数据
行人都是写者，桥是数据
信号量
s：互斥信号量

伪代码

semaphore s = 1;                       //互斥信号量void east_west( )
{while (true) {P(s);                                           //互斥其他人过桥walk across the bridge from east to west;      //行人从东向西过桥V(s);                                          //允许其他人过桥}
}void west_east( )
{while (true) {P(s);                                         //互斥其他人过桥walk across the bridge from west to east;      //行人从西向东过桥V(s);                                           //允许其他人过桥}
}

示例二

情境描述

东西方向的独木桥，仅容一人过，不允许停留
东西方向都有人在等着过桥
同一方向的行人可以连续过桥，另一方的行人必须等待

请用P、V操作来实现东西两端行人过桥问题

分析

读者优先问题
行人首先上桥的一方为读者，另一方为写者，桥是数据
信号量
x：互斥信号量,互斥读者写者
countR：统计读者数目（同时在桥上的行人数目）
mutexR：对变量countR加锁

伪代码

int countA=0, countB=0；
semaphore x=1, mutexA=1, mutexB=1;void east_west() { while (1) {P(mutexA);countA++;if (countA==1) P(x); V(mutexA);walk across the bridge from east to west;P(mutexA);countA--;if (countA==0) V(x);V(mutexA);}
}void west_east() { while (1) {P(mutexB);countB++;if (countB==1) P(x); V(mutexB);walk across the bridge from west to east;P(mutexB);countB--;if (countB==0) V(x);V(mutexB);}
}

示例三

情境描述

东西方向的独木桥，不允许停留
东西方向都有人在等着过桥
同一方向的行人可以连续过桥，另一方的行人必须等待
桥最大可承重四人

请用P、V操作来实现东西两端行人过桥问题

分析

读者优先问题
行人首先上桥的一方为读者，另一方为写者，桥是数据
与示例二不同在于不用一个一个过桥，只要桥没到承重限度就可以进入，这里承重限度就是临界区大小
信号量
x：互斥信号量,互斥读者写者
countR：统计读者数目（同时在桥上的行人数目）
mutexR：对变量countR加锁
count: 位于独木桥上的行人数目

伪代码

int countA=0, countB=0；
semaphore x=1, muteA=1, mutexB=1,count=4;void east_west() { while (1) {P(mutexA);countA++;if (countA==1) P(x); V(mutexA);P(count);walk across the bridge from east to west;V(count);P(mutexA);countA--;if (countA==0) V(x);V(mutexA);}
}
void west_east() { while (1) {P(mutexB);countB++;if (countB==1) P(x); V(mutexB);P(count);walk across the bridge from west to east;V(count);P(mutexB);countB--;if (countB==0) V(x);V(mutexB);}
}