欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PV经典问题之读写者问题

程序员文章站 2022-07-05 08:05:30
...

问题描述

有一个许多进程共享的数据区,这个数据区可以是一个文件或者主存 的一块空间;有一些只读取这个数据区的进程(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  
    }
}

相关标签: 操作系统---PV