目录

一、问题描述

二、解题思路

2.1 读者优先算法

2.2 写者优先算法

2.3 读写公平

三、源码实现

3.1 读者优先

3.2 写者优先

3.3 读写平等

一、问题描述

一个数据问价或记录可以被多个进程共享，我们把只读该文件的进程称为“读者进程”，其他进程为“写者进程”。允许多个进程同时读一个共享对象，但不允许一个写者进程和其他写者进程或读者进程同时访问共享对象。即：保证一个写者进程必须与其他进程互斥的访问共享对象的同步问题；读者-写者问题常用来测试新同步原语。

二、解题思路

首先对于上述问题进行抽象：读者和写者是互斥的，写者和写者是互斥的，读者和读者不互斥；两类进程，一种是写者，另一种是读者。写者很好实现，因为它和其他任何进程都是互斥的，因此对每一个写者进程都给一个互斥信号量的P、V操作即可；而读者进程的问题就较为复杂，它与写者进程是互斥的，而又与其他的读者进程是同步的，因此不能简单的利用P、V操作解决。

下面我们给出三种方案来解决读者和写者之间、读者和读者之间、写者和写者之间的同步与互斥问题：

2.1 读者优先算法

为实现Reader和Writer进程之间在读或写时的互斥而设置了一个互斥信号量wmutex。再设置一个整型变量conut表示正在读的进程数目。

• 仅当count=0时，Reader进程才需要执行wait(wmutex)操作；同理，仅当Reader进程在执行了count减一操作后其值为0时，才需要执行signal(wmutex)操作，以便让Writer进程操作；
• 由于count是一个可被多个Reader进程访问的临界资源，因此为其设置一个互斥信号量rmutex；

其伪码描述如下：

semaphore rmutex=1,wmutex=1;int count=0;void Reader(){while(1){wait(rmutex);if(count==0)wait(wmutex);count++;signal(rmutex);read;wait(rmutex);count--;if(count==0)signal(wmutex);signal(rmutex);}}void Writer(){while(1){wait(wmutex);write;signal(wmutex);}}

在Linux系统环境下多次运行3.1中的源码，会出现以下情况：

由于测试文本数目较小，仅试运行5次，当训练集数目较大时，则Writer亦有可能出现如上情况，即：等待Reader进程全部结束之后才逐步执行Writer进程。我们称这样的算法为读者优先算法，也就是说，当存在读进程时，写操作将被延迟，并且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式下，会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

2.2 写者优先算法

所谓写者优先，即：当有读者进程正在执行，写者进程发出申请，这时应该拒绝其他读者进程的请求，等待当前读者进程结束后立即执行写者进程，只有在无写者进程执行的情况下才能够允许读者进程再次运行。为此，增加一个信号量并且在上面的程序中 writer()和reader()函数中各增加一对PV操作，就可以得到写进程优先的解决程序。

在读者优先的基础上

• 增加信号量r，初值是1，用于禁止所有的读进程。
• 增加一个记数器，即整型变量writecount，记录写者数，初值是0（原count改为readcount）。 writecount为多个写者共享的变量，是临界资源。用互斥信号量wmutex控制, wmutex初值是1（原wmutex改为mutex1）。

伪码描述如下：

semaphore rmutex=1,wmutex=1,mutex1=1;int readcount=0,writecount=0;void Reader(){while(1){wait(r);wait(rmutex);if(count==0)wait(mutex1);count++;signal(rmutex);signal(r);read;wait(rmutex);count--;if(count==0)signal(mutex1);signal(rmutex);}}void Writer(){while(1){wait(wmutex);writecount++;if(writecount==1)wait(r);signal(wmutex);wait(mutex1);write;signal(mutex1);wait(wmutex);writecount--;if(writecount==0)wait(r);signal(wmutex);signal(r);}}

2.3 读写公平

为实现读写公平，我们必须要同时满足以下四个条件：

1. 读者写者的优先级相同
2. 读者、写者互斥访问
3. 只允许有一个写者访问临界区
4. 可以有多个读者同时访问临界区的资源

为此，我们设置一个互斥信号量queue，其作用是让Writer进程和Reader进程进行排队，当有Reader进程执行时，queue=0，因此Writer进程会进入等待，直到queue变为1；当Writer进程执行时，同理；因此我们借助queue实现了读写进程的优先级平等。其余的保持3.1中算法不变。

在Linux环境下运行，可得结果：

很明显的区别于3.1和3.2中的结果。

三、源码实现

3.1 读者优先

#include #include #include #include #include #include #include #define N 5int count=0,a=5,b=5;int r[N]={0,1,2,3,4};sem_t wmutex,rmutex;void delay(){int time = rand() % 10 + 1;//随机使程序睡眠0点几秒 usleep(time * 100000);}void Reader(void *arg){int i=*(int *)arg;while(a>0){a--;delay();sem_wait(&rmutex);if(count==0)sem_wait(&wmutex);count++;sem_post(&rmutex);printf("Reader%d is reading!\n",i);printf("Reader%d reads end!\n",i);sem_wait(&rmutex);count--;if(count==0)sem_post(&wmutex);sem_post(&rmutex);}}void Writer(){while(b>0){b--;delay();sem_wait(&wmutex);printf("writer is writing!\n");printf("writer writes end!\n");sem_post(&wmutex);}}int main(){int i;pthread_t writer,reader[N];srand((unsigned int)time(NULL));sem_init(&wmutex,0,1);//互斥锁初始化 sem_init(&rmutex,0,1);for(i=0;i<5;i++)//创建线程 {pthread_create(&reader[i],NULL,(void *)Reader,&r[i]);} pthread_create(&writer,NULL,(void *)Writer,NULL);pthread_join(writer,NULL);//线程等待 sem_destroy(&rmutex); //互斥锁的销毁sem_destroy(&wmutex); return 0;} 

3.2 写者优先

#include #include #include #include #include #include #include #define N 5int readcount=0,writecount=0,a=5,b=2;int r[N]={0,1,2,3,4};int w[N]={0,1};sem_t wmutex,rmutex,mutex1,num;void delay(){int time = rand() % 10 + 1;//随机使程序睡眠0点几秒 usleep(time * 100000);}void Reader(void *arg){int i=*(int *)arg;while(a>0){a--;delay();//延迟 //进入共享文件前的准备 sem_wait(&num);//在无写者进程时进入 sem_wait(&rmutex);//与其他读者进程互斥的访问readcount if(readcount==0)sem_wait(&mutex1);//与写者进程互斥的访问共享文件 readcount++;sem_post(&rmutex);sem_post(&num); //readerprintf("Reader%d is reading!\n",i);printf("Reader%d reads end!\n",i);//退出共享文件后的处理 sem_wait(&rmutex);readcount--;if(readcount==0)sem_post(&mutex1);sem_post(&rmutex);}}void Writer(void *arg){int i=*(int *)arg;while(b>0){b--;delay();//进入共享文件前的准备 sem_wait(&wmutex);//保证多个写者进程能够互斥使用writecount writecount++;if(writecount==1)sem_wait(&num);//用于禁止读者进程 sem_post(&wmutex);//writersem_wait(&mutex1);//与其他所有进程互斥的访问共享文件 printf("writer%d is writing!\n",i); printf("writer%d writes end!\n",i);sem_post(&mutex1);//退出共享文件后的处理 sem_wait(&wmutex);writecount--;if(writecount==0)sem_post(&num);sem_post(&wmutex);}}int main(){int i;pthread_t writer[N],reader[N];srand((unsigned int)time(NULL));sem_init(&wmutex,0,1);//互斥锁初始化 sem_init(&rmutex,0,1);sem_init(&mutex1,0,1);sem_init(&num,0,1);for(i=0;i<5;i++)//创建线程 {pthread_create(&reader[i],NULL,(void *)Reader,&r[i]);} for(i=0;i<2;i++)//创建线程 {pthread_create(&writer[i],NULL,(void *)Writer,&w[i]);}for(i=0;i<2;i++)//等待线程 {pthread_join(writer[i],NULL);}for(i=0;i<5;i++)//等待线程 {pthread_join(reader[i],NULL);}sem_destroy(&rmutex); //互斥锁的销毁sem_destroy(&wmutex); sem_destroy(&mutex1);sem_destroy(&num);return 0;} 

3.3 读写平等

#include #include #include #include #include #include #include #define N 5int readcount=0,a=5,b=5;int r[N]={0,1,2,3,4};sem_t wmutex,rmutex,queue;void delay(){int time = rand() % 10 + 1;//随机使程序睡眠0点几秒 usleep(time * 100000);}void Reader(void *arg){int i=*(int *)arg;while(a>0){a--;delay();sem_wait(&queue);//让写者进程排队，读写进程具有相同的优先级 sem_wait(&rmutex);//与其他读者进程互斥的访问readcount if(readcount==0)//最开始的时候readcount=0 sem_wait(&wmutex);//与写者进程互斥的访问共享文件 readcount++;sem_post(&rmutex);sem_post(&queue);//使得写者进程进入准备状态 //Readerprintf("Reader%d is reading!\n",i);printf("Reader%d reads end!\n",i);sem_wait(&rmutex);readcount--;if(readcount==0)sem_post(&wmutex);sem_post(&rmutex);}}void Writer(){while(b>0){b--;delay();sem_wait(&queue); sem_wait(&wmutex);printf("writer is writing!\n");printf("writer writes end!\n");sem_post(&wmutex);sem_post(&queue);}}int main(){int i;pthread_t writer,reader[N];srand((unsigned int)time(NULL));sem_init(&wmutex,0,1);//互斥锁初始化 sem_init(&rmutex,0,1);sem_init(&queue,0,1);for(i=0;i<5;i++)//创建线程 {pthread_create(&reader[i],NULL,(void *)Reader,&r[i]);} pthread_create(&writer,NULL,(void *)Writer,NULL);pthread_join(writer,NULL);//线程等待 sem_destroy(&rmutex); //互斥锁的销毁sem_destroy(&wmutex); sem_destroy(&queue); return 0;}