操作系统：读者写者问题
操作系统：读者写者问题@[TOC](操作系统：读者写者问题)问题：一、读者-写者问题: 读者优先二、读者-写者问题：写进程优先三、读者写者问题的应用---独木桥问题类型1.一次只能过一辆车类型2.一次能过多辆车四、总结附代码：//读者优先//写者优先//公平竞争教材原文：问题：在操作系统中，我们处理各种过程，这些过程可能会使用系统中存在的文件。基本上，我们对文件执行两个操作，即读取和写入。所...
操作系统：读者写者问题
问题：
在操作系统中，我们处理各种过程，这些过程可能会使用系统中存在的文件。基本上，我们对文件执行两个操作，即读取和写入。所有这些过程都可以执行这两个操作。但是这里出现的问题是：
- 如果一个进程正在某个文件上写入内容，而另一个进程也同时开始在同一文件上写入内容，则系统将进入不一致状态。在特定的时间仅应允许一个进程更改文件中存在的数据的值。
- 另一个问题是，如果一个进程正在读取文件，而另一个进程同时在同一文件上写入，则可能会导致读取不干净，因为在该文件上写入的进程会更改文件的值，但是读取该文件的过程将读取文件中存在的旧值。因此，应避免这种情况。
一、读者-写者问题: 读者优先
1.问题描述
有两组并发进程：读者和写者，共享一个文件F，要求:
- 允许多个读者同时执行读操作
- 任一写者在完成写操作之前不允许其它读者或写者工作
- 写者执行写操作前，应让已有的写者和读者全部退出
2.问题分析
- 共享数据（文件、记录）由Reader和Writer是两组并发进程共享
- Reader和Writer两组并发进程
- 同组的Reader进程可同时对文件进行读，不用互斥
- 写-写互斥
- 读-写互斥
3.读者写者问题–读者优先
对于读者优先，应满足下列条件：
①如果新读者到：但有其它读者正在读，则新读者也可以读；
②有写者等待，但有其它读者正在读，则新读者也可以读；
③有写者写，新读者等待。
如果新写者到：
①无读者，新写者可以写；
②有读者，新写者等待；
③有其它写者，新写者等待。
4.信号量及变量设计
- 对读进程计数变量：readcount=0
- 对计数器操作的互斥信号量：rc_mutex=1
- 读写互斥、写写互斥信号量：writeblock=1
5.读者优先算法设计
int readcount=0; //读进程计数器
semaphore writeblock, rc_mutex ;
writeblock=1; rc_mutex=1;
main() {
cobegin
process reader_i( )//i=1,2,…n
process writer_j( ) //j=1,2,…m
coend
}
process reader_i()
{
P(rc_mutex);
readcount++;
if(readcount==1)
P(writeblock);
V(rc_mutex);
{读文件};
P(rc_mutex);
readcount--;
if(readcount==0)
V(writeblock);
V(rc_mutex);
}
process writer_j( )
{
P(writeblock);
{写文件};
V(writeblock);
}
6.问题分析
(1)读者优先，当有读者时，写者将被推迟
(2)会出现写者饥饿现像
二、读者-写者问题：写进程优先
1.信号量设置
（1）信号量x：readcount的互斥操作信号量
（2）信号量y：writecount的互斥操作信号量
（3）信号量wsem:写写互斥、读写互斥信号量
（4）信号量rsem:读者、写者竞争的信号量，读者每次都释放，最后一个写者才释放。
（5）信号量z：读者排队的信号量
2.算法设计
int readcount，writecount;
semaphore x=1,y=1,z=1,wsem=1,rsem=1;
void reader()
{
Wait(z) ;
Wait(rsem);
Wait(x);
readcount++;
if(readcount==1) Wait(wsem);
Signal(x);
Signal(rsem);
signal(z);
readunit();
Wait(x);
readcount--;
if(readcount==0) Signal(wsem);
Signal(x);
}
Void writer()
{
{
Wait(y);
writecount++;
if(writecount==1) Wait(rsem);
signal(y);
wait(wsem);
writeunit();
signal(wsem);
Wait(y);
writecount--;
if(writecount==0) signal(rsem);
Signal(y);
}
Void main()
{
readcount=writecount=0;
parbegin(reader,writter);
}
三、读者写者问题的应用—独木桥问题
类型1.一次只能过一辆车
1.问题描述
东西向汽车驶过独木桥，为了保证交通安全，只要桥上无车，则允许一方的汽车过桥，待其全部过完后才允许另一方的汽车过桥，限制桥面上一次只过一辆车。请用信号量和pv操作写出汽车过独木桥问题的同步算法。
2.问题分析
（1）系统中的进程
两类：从东向西行驶的汽车；从西向东行驶的汽车
（2）进程间的关系
①同向行驶的汽车需要排队；
②对向行驶的汽车需要同步，保证不能在独木桥上相遇
3.信号量设计
（1）mutexA：用于同向（从东向西）行驶的汽车对统计信息进行修改时的互斥信用量，初值为 1
（2）mutexB：用于同向（从西向东）行驶的汽车行驶的汽车对统计信息进行修改时的互斥信用量，初值为 1
（3）bridge：两个方向的汽车过桥的时的信号量，两个方向竞争此信号量，竞争成功的一方获得过桥资格，初值为 1
（4）mutex：过桥时的互斥信号量
4.算法设计
semaphore mutexA,mutexB,bridge,mutex;
mutexA=1,mutexB=1,bridge=1,mutex=1;
int countA=0,countB=0;
main() {
cobegin
process east-to-west-i();//i=1,2,3…n
process west-to-east-j();//j=1,2,3…m
coend
}
process east-to-west-i();//i=1,2,3…n
{ p(mutexA);
countA++;
if(countA==1) p(bridge);
v(mutexA);
p(mutex);
过桥；
v(mutex);
p(mutexA); countA--;
if(countA==0) v(bridge);
v(mutexA);
}
process west-to-east-j();//j=1,2,3…..
{
{ p(mutexB);
countB++;
if(countB==1) p(bridge);
v(mutexB);
p(mutex);
过桥；
v(mutex);
p(mutexB);
countB--;
if(countB==0) v(bridge);
v(mutexB);
}
类型2.一次能过多辆车
1.问题描述
东西向汽车驶过独木桥，为了保证交通安全，只要桥上无车，则允许一方的汽车过桥，待其全部过完后才允许另一方的汽车过桥，桥面上一次能过多辆车。请用信号量和pv操作写出汽车过独木桥问题的同步算法。
2.进程设计
两类进程：从东到西的汽车 PA 和从西到东的汽车 PB
(1)PA 进程：每辆汽车从东到西过桥的一次活动为一个进程
(2)PB 进程：每辆汽车从西到东过桥的一次活动为一个进程
3.信号量设计
（1）mutex1：用于 PA 进程之间对统计信息进行修改时的互斥信用量，初值为 1
（2）mutex2：用于 PB 进程之间对统计信息进行修改时的互斥信用量，初值为 1
（3）bridge：两个方向的汽车过桥的时的信号量，两个方向竞争此信号量，竞争成功的一方获得过桥资格，初值为 1
（4）number：同一方向过桥时的信号量，初值为 k
4.算法设计
semaphore mutex1=1, mutex2=1,bridge=1，number=k;int count1=0，count2=0；
cobegin
process PA_i()//i=1,2,…..
{
p(mutex1); //对统计量 count1 写操作的互斥信号量
count1++；
If（count1==1）
p（bridge）//第一个从东到西的汽车竞争桥的互斥信号量
v(mutex1);
p（number）；// 同一方向的汽车过桥，同时可以过 k 辆
过桥；
V(number);
p(mutex1); //对统计量 count1 写操作的互斥信号量
coun1--；
If（count1==0）
v（bridge）//最后一个从东到西的汽车释放桥的互斥信号量
v(mutex1);
}
process PB_j()//j=1,2,…..
{
p(mutex2); //对统计量 count1 写操作的互斥信号量
count2++；
If（count2==1） p（bridge）//第一个从东到西的汽车竞争桥的互斥信号量
v(mutex2);
p（number）；// 同一方向的汽车过桥，同时可以过 k 辆
过桥；
V(number);
p(mutex2); //对统计量 count1 写操作的互斥信号量
coun2--；
If（count2==0）
v（bridge）//最后一个从东到西的汽车释放桥的互斥信号量
v(mutex2);
}
coend
四、总结
读者写者问题和生产者消费者问题的区别在于：
（1）同一时期内生产者消费者问题可以交替执行；而读者写者问题在同一时期内只能由一方执行，当开始执行时必须执行完所有读者（或写者），另外一方才能开始执行。
（2）生产者消费者共享的缓存区必须要互斥；读者写者共享的文件不一定需要互斥，当限制只有不可同时读或不可同时写时共享的文件才需要互斥。
（3）独木桥问题有点特殊，代码中未体现出同步，当一方的车辆全部通过桥面时，释放桥的使用权，由于全部车辆已经通过，目前这一方已经没有车辆了，自然另一方就会抢到桥的使用权，然后开始过桥，如此反复，从而体现出了同步。
附代码：
//读者优先
/**
1、首先当读者获得临界区的访问权，则此时的readcount > 0 则读者尚未释放fmutex则写者就不能获得临界区的访问权，有一个被阻塞在fumtex信号中，其余的被塞 在Entmutex信号中，则只有当读者访问完毕，写者才有机会获得临界区的访问权
2、若写者获得临界区的访问权，而且有源源不断的写着进程过来，那么读者能不能抢得临界区的访问权呢？答案是肯定的，因为考虑此时的读者进程阻塞情况，有一个读者进程阻塞在fmutex中，其余的读者均阻塞在Rmutex，而写者进程呢，由于Entemutex的存在每个时刻只有一个一个写者进程阻塞在fmutex中，其余的全被阻塞在Entmutex中，则当写者进程访问完毕后，此时阻塞在fmutex中的进程只有读者进程，则也就只有读者进程先被激活访问
*/
mutex = 1 //读者、写者进程访问文件信号量变量，保证了读者与写者、写者与写者之间的互斥访问
Rmutex = 1 //实现对readcount的互斥访问
Entmutex =1 //若写者获得临界区的访问权，而且不断有写者进程过来，
//那么读者将不能抢得临界区的访问权
readcount = 0
Read()
{
while(1)
{
wait(Rmutex) ;
if(0 == readcount)
wait(mutex) ;
readcount ++ ;
signal(Rmutex) ;
-----------------------------
| perform reading operation |
-----------------------------
wait(Rmutex);
readcount --;
if(0 == readcount)
signal(mutex)
signal(Rmutex) ;
}
}
Writer()
{
while(1)
{
//保证每次阻塞在mutex中的写者进程只有一个，
//确保当前写者写完，若还有写者等待，则会被卡在Entmutex，读者不需要等待
wait(Entmutex)
wait(mutex)
-----------------------------
| perform writing operation |
-----------------------------
signal(mutex)
signal(Entmutex)
}
}
//写者优先
/**
1.当读者获得了访问临界区的权利时，且读者进程访问的很密集时(即很多读者都需要访问)，写者如何抢得访问权。
由于Entmutex的存在每次阻塞在Quemutex中的读者进程最多只有一个，而当读者进程访问时，写着进程一个被阻塞在Quemutex中，其余的全部阻塞在Wcount中，当读者访问完毕，释放Quemutex，此时，阻塞在其中的进程只有写者进程，则写着进程得到激活
2.当写者获得临界区的访问权时，读者只能等到临界区空闲时才能得到临界区访问权。
因为当写者获得临界区时，所有的读者都会阻塞在Entmutex信号和QUemutex信号中。 而只有最后一个写者访问完临界区时，才会Signal(Qmutex)， 使得阻塞在fmutex中唯一的读者获得临界区访问权。
*/
Entemutex = 1
Quemutex = 1
Rmutex = 1
Wmutex = 1
mutex = 1
readcount = 0
Reader()
{
while(1)
{
wait(Entemutex)
wait(Quemutex)
wait(Rmutex)
if(0 == readcount)
wait(mutex)
readcount++
signal(Rmutex)
signal(Quemutex)
signal(Entemutex)
-----------------------------
| perform reading operation |
-----------------------------
wait(Rmutex)
readcount--
if(readcount == 0)
signal(mutex)
signal(Rmutex)
}
}
writer()
{
while(1)
{
wait(Wmutex)
if(writecount == 0)
wait(Quemutex)
writecount++
signal(Wmutex)
wait(mutex)
-----------------------------
| perform writing operation |
-----------------------------
signal(mutex)
wait(Wmutex)
writecount--
if(writecount == 0)
signal(Quemutex)
signal(Wmutex)
}
}
//公平竞争
Reader()
{
while(1)
{
wait(Quemutex)
wait(Rmutex)
if(0 == readcount)
wait(mutex)
readcount++
signal(Rmutex)
signal(Quemutex)
-----------------------------
| perform reading operation |
-----------------------------
wait(Rmutex)
readcount--
if(readcount == 0)
signal(mutex)
signal(Rmutex)
}
}
writer()
{
while(1)
{
wait(Quemutex)
wait(mutex)
-----------------------------
| perform writing operation |
-----------------------------
signal(mutex)
signal(Quemutex)
}
}
教材原文：
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
9
0- 0
已为社区贡献16条内容
所有评论(0)