读者写者问题—内含408真题

读者写者问题—含408

一、问题描述

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

二、解题思路

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

2.1 读者优先算法(一般意义上的读者写者问题)

为实现Reader和Writer进程之间在读或写时的互斥而设置了一个互斥信号量wmutex。再设置一个整型变量conut表示正在读的进程数目。
仅当count=0时，Reader进程才需要执行P(wmutex)操作；
仅当Reader进程在执行了count减一操作后其值为0时，才需要执行V(wmutex)操作
由于count是一个可被多个Reader进程访问的临界资源，因此为其设置一个互斥信号量cmutex；
其伪码描述如下：

semaphore cmutex=1,wmutex=1;
int count=0;

void Reader(){
	while(1){
		P(cmutex);
		if(count==0)
			P(wmutex);
		count++;
		V(cmutex);
		read;
		P(cmutex);
		count--;
		if(count==0)
			V(wmutex);
		V(cmutex);
	}
}

void Writer(){
	while(1){
		P(wmutex);
		write;
		V(wmutex);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

等待Reader进程全部结束之后才逐步执行Writer进程。我们称这样的算法为读者优先算法，也就是说，当存在读进程时，写操作将被延迟，并且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式下，会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

---

2.2 写者优先算法

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

• 在读者优先的基础上增加信号量rmutex，初值是1，用于禁止所有的读进程。
• 增加一个记数器，即整型变量writecount，记录写者数，初值是0（原count改为readcount）。
• writecount为多个写者共享的变量，是临界资源。用互斥信号量wmutex控制, wmutex初值是1
• mutex用于实现互斥访问缓冲区
  伪码描述如下：

semaphore rmutex=1,cmutex=1,wmutex=1,mutex=1;
int readcount=0,writecount=0;
 
void Reader(){
	while(1){
		/**新增代码**/
		P(rmutex);// 取到该信号量说明此时并没有写进程在等待
		          // 后续读者才可以共享访问临界区
		          // 但是前面已经进入的读进程不受影响
		/**********/
		P(cmutex);
		if(readcount==0)
			P(mutex);
		readcount++;
		V(cmutex);
		/**新增代码**/
		V(rmutex);// 已经取到过这个信号量了
		          // 那么就说明已经得到了对临界区的读访问权限
		          // 此时可以一起读
		/**********/		
		read;
		V(cmutex);
		readcount--;
		if(readcount==0)
			V(mutex);
		V(cmutex);
	}
}
 
void Writer(){
	while(1){
		/**新增代码**/
		P(wmutex);
		writecount++;
		if(writecount==1)// 第一个写进程进来等待以后就
			P(rmutex);	 // 禁止读进程继续读了
		V(wmutex);
		/***********/
		P(mutex);
		write;
		V(mutex);
		/**新增代码**/
		P(wmutex);
		writecount--;
		if(writecount==0)//当没有写进程时，才允许读进程继续读
			V(rmutex);
		V(wmutex);
		/***********/
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

---

2.3 读写公平

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

• 读者写者的优先级相同
• 读者、写者互斥访问
• 只允许有一个写者访问临界区
• 可以有多个读者同时访问临界区的资源
  为此，我们设置一个互斥信号量mutex，其作用是让每个Writer进程和Reader进程进行公平争夺
• 当Reader争夺到了，那么不管他是不是第一个Reader，他都有权利进入读操作（但是在进行读操作之前，需要释放这个互斥信号量，供后续的Reader和Writer继续公平争夺）
• 当Writer争夺到了，就等待之前的Reader全部执行完，就可以上处理机运行

semaphore cmutex=1,wmutex=1,mutex=1;
int count=0;

void Reader(){
	while(1){
		/**新增代码**/
		P(mutex);//争夺优先权
		/**********/
		P(cmutex);
		if(count==0)
			P(wmutex);
		count++;
		V(cmutex);
		/**新增代码**/
		V(mutex);
		/**********/
		read;
		P(cmutex);
		count--;
		if(count==0)
			V(wmutex);
		V(cmutex);
	}
}

void Writer(){
	while(1){
		/**新增代码**/
		P(mutex);//争夺优先权
		/**********/
		P(wmutex);
		write;
		V(wmutex);
		/**新增代码**/
		V(mutex);
		/**********/
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

这个最主要的思路就是让每一次运行的进程都有公平竞争的权利
因为读者优先算法，当读者上处理机运行后，写者就丧失了竞争的权利，只有当读者全部读完才可以重新竞争，这很不公平

2.4 双读者问题（2017年408真题）

先说明一下，双读者问题实际上并不存在，只是针对这道题提出的概念，由于使用常规的读者写者算法会导致并发度不够，所以特地将真题单独作为一个问题考虑

口说无凭，不如使用对比来更直观地展现其区别吧
首先是使用读者写者问题来解决该问题的算法：

semaphore mutex_x=1;// 对x的互斥访问
semaphore mutex_y=1;// 对y的互斥访问
semaphore mutex_z=1;// 对z的互斥访问
semaphore mutex_count=1;// 对计数器的互斥访问
int count=0;//计数器

void thread1(){
	cnum w;
	P(mutex_count);
	if(count==0)
		P(mutex_y);
	count++;
	V(mutex_count);
	P(mutex_x);
	w = add(x,y);
	V(mutex_x);
	P(mutex_count);
	count--;
	if(count==0)
		V(mutex_y);
	V(mutex_count);
	
}

void thread2(){
	cnum w;
	P(mutex_count);
	if(count==0)
		P_(mutex_y);
	count++;
	V(mutex_count);
	P(mutex_z);
	w = add(y,z);
	V(mutex_z);
	P(mutex_count);
	count--;	
	if(count==0)
		V(mutex_y);
	V(mutex_count);	
}

void thread3(){
	cnum w;
	w.a = 1;
	w.b = 1;
	P(mutex_z);
	z = add(z,w);
	V(mutex_z);
	P(mutex_y);
	y = add(y,w);
	V(mutex_y);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

乍一看好像没啥问题，但是有一个很重要的问题是，虽然对于y的访问，实现了读写互斥，同时读与读可以同时进行，但是count信号量限制了并发度，导致两个读操作并不能以最快的方式运行完。
下面是标准答案：

semaphore mutex_x=1;// 对x的互斥访问
semaphore mutex_y1=1;// 对y的互斥访问
semaphore mutex_y2=1;// 对y对互斥访问
semaphore mutex_z=1;// 对z的互斥访问
void thread1(){
	cnum w;
	P(mutex_y1);
	P(mutex_x);
	w = add(x,y);
	V(mutex_x);
	V(mutex_y1);
}

void thread2(){
	cnum w;
	P(mutex_y2);
	P(mutex_z);
	w = add(y,z);
	V(mutex_z);
	V(mutex_y2);	
}

void thread3(){
	cnum w;
	w.a = 1;
	w.b = 1;
	P(mutex_z);
	z = add(z,w);
	V(mutex_z);
	P(mutex_y1);// 只有同时拥有互斥信号量
	P(mutex_y2);// 才算是获取了访问权限
	y = add(y,w);
	V(mutex_y1);
	V(mutex_y2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

上面的代码，可以大大提高并发度，因为1，2两个线程也可以保证在读y时是绝对并行的