进程经典同步问题

哲学家进餐问题 生产者消费者问题 读者-写者问题 银行家算法

生产者消费者问题：

①生产者—消费者之间的同步关系表现为：一旦缓冲池中所有缓冲区均装满产品时，生产者必须等待消费者提供空缓冲区；一旦缓冲池中所有缓冲区全为空时，消费者必须等待生产者提供满缓冲区。

②生产者—消费者之间还有互斥关系：由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。

PV操作题目分析的步骤：

1.关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

2.整理思路。根据各进程的操作流程确定PV操作的大致顺序。

3.设置信号量。设置需要的信号量，并根据题目条件确定信号量的初值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
semaphore mutex = 1;  //互斥信号量
semaphore empty = n;  //同步信号量。空闲缓冲区的数量
semaphore full = 0;   //同步信号量。产品的数量，非空缓冲区的数量
producer(){
    while(1){
      生成一个产品;
      P(empty); //消耗一个空闲缓冲区
      P(mutex);
      把产品放入缓冲区;
      V(mutex);
      V(full)   //增加一个产品
    }
}
consumer(){
    while(1){
      P(full);   //消耗一个产品
      P(mutex);
      从缓冲区取出一个产品;
      V(mutex);
      V(empty);  //增加一个空闲缓冲区
      使用产品;
    }
}

哲学家进餐问题：

问题描述：

5个哲学家围坐在一个圆桌上，每两个哲学家之间都有一只筷子，哲学家平时进行思考，只有当他们饥饿时，才拿起筷子吃饭。规定每个哲学家只能先取其左边筷子，然后取其右边筷子，然后才可以吃饭。

分析：

每一只筷子都是一个临界资源，设置5个互斥信号量。Semaphore stcik[5]={1,1,1,1,1}因为：只有占有左边筷子->占有右边筷子->吃饭所以p(左边筷子)->p(右边筷子)->吃饭

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
main(){
	philosopher(0);//注意不可以用循环，因为此中是4个并列的进程。
	philosopher(1);
	philosopher(2);
	philosopher(3);
	philosopher(4);
}
philosopher(int i){
	while(1){
		思考；
		p(stick[i]);//取左边筷子
		p(stick[i+1]);//取右边筷子

		进餐；
		V(stick[i]);
		v(stick[i+1]);
	}
}

问题：

如果5个哲学家同时拿起自己左边的筷子，就会发生死锁。

防止死锁的方法：

（1）方法一：

规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子， 等一段时间再重复整个过程。

问题：发生饥饿现象；

如果同时拿起左边筷子，则右边的筷子都不可用，则放下，然后再次拿起……则谁都无法就餐

（2）方法二：

最多允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。

伪码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
semaphore chopstick[5]={1，1，1，1，1};
semaphore room=4;
void philosopher(int i)
{
	while(true)
	{
		think();
		wait(room); //请求进入房间进餐
		wait(chopstick[i]); //请求左手边的筷子
		wait(chopstick[(i+1)%5]); //请求右手边的筷子
		eat();
		signal(chopstick[(i+1)%5]); //释放右手边的筷子
		signal(chopstick[i]); //释放左手边的筷子
		signal(room); //退出房间释放信号量room
	}
}

（3）方法三：将拿左筷子，与拿右筷子当做一个原子操作：（即只有当左右筷子均可以拿到时，才拿筷子。

（4）方法四：规定奇数号的哲学家先拿起他左边的筷子，然后再去拿他右边的筷子;而偶数号 的哲学家则相反。

伪码：

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
semaphore chopstick[5]={1，1，1，1，1};
void philosopher(int i)
	{
		while(true)
		{
			think();
			if(i%2 == 0) //偶数哲学家，先右后左。
				{
					P (chopstick[ i + 1 ] mod 5) ;
					P (chopstick[ i]) ;
					eat();
					V (chopstick[ i + 1 ] mod 5) ;
					V (chopstick[ i]) ;
				}
			Else //奇数哲学家，先左后右。
				{
					p (chopstick[ i]) ;
					p (chopstick[ i + 1 ] mod 5) ;
					eat();
					V (chopstick[ i]) ;
					V (chopstick[ i + 1 ] mod 5) ;
				}
		}
	}
}

读者-写者问题

读者优先：

互斥信号量wrt，初值是1，代表一个共享文件，解决“读－写”互斥，“写－写”互斥。一个记数器，即整型变量readcount，记录读者数，初值是0。 来一个读者， readcount加1 当readcount ＝1表示是第一个读者， 则需要执行p操作抢占文件；否则表示已有读者在安全的读数据。 走一个读者，readcount减1 当readcount ＝0表示是最后一个读者，则需要v操作释放资源；否则表示还有读者在读数据。readcount 为多个读者共享的变量，是临界资源。用互斥信号量mutex控制, mutex初值是1。

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
int readcount=0; 
semaphore mutex=1, wrt=1 ; 
 
读者进程：
        wait (mutex);
	readcount++;	
	if (readcount == 1)
	       wait(wrt);
	signal (mutex);
		…
	   reading is performed
		 …
	wait (mutex);
	readcount--;
	if (readcount == 0)
		signal (wrt);
	signal (mutex);
 
 
写者进程：     
      wait(wrt);
	    …
         writing is performed
	    …
      signal(wrt);

写者优先:

在读者优先的基础上,增加信号量r，初值是1：当至少有一个写进程准备访问数据区时，用于禁止所有的读进程。增加一个记数器，即整型变量writecount，记录写者数，初值是0。 writecount为多个写者共享的变量，是临界资源。用互斥信号量mutex2控制, mutex2初值是1。增加mutex3，初值是1：在r上不允许建造长队列，否则写进程将不能跳过这个队列，因此，只允许一个读进程在r上排队，而所有其他读进程在等待r之前，在信号量mutex3上排队。

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
int readcount=0, writecount=0; 
semaphore mutex1=1, mutex2=1, mutex3=1, w=1, r=1 ; 
 
读者进程：
P(mutex 3);
   P(r);
      P(mutex 1);
         readcount++;
         if (readcount == 1 ) 
            P(w);
      V(mutex 1);
    V(r);
V(mutex 3);
      reading is performed
P(mutex 1);
    readcount --;
    if (readcount == 0 )
             V(w);
V(mutex 1);
 
写者进程：     
P(mutex 2);
    writecount++;
    if (writecount == 1 )
           P(r);
V(mutex 2);
P(w);
    writing is performed
V(w);
P(mutex 2);
    writecount --;
    if (writecount == 0)
           V(r);

V(mutex 2);

读写公平:

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
int readcount=0; 
semaphore mutex=1, rw=1 w=1; 
 
读者进程：
        wait (w);
        wait (mutex);
        if (readcount == 0)
	       wait(rw);
    	readcount++;	
    	signal (mutex);
        signal (w);
		…
    	   reading is performed
		 …
    	wait (mutex);
    	readcount--;
    	if (readcount == 0)
    		signal (rw);
    	signal (mutex);
 
 
写者进程：     
    wait(w);
    wait(rw);
	    …
         writing is performed
	    …
    signal(rw);
    signal(w);

银行家算法：

参照该博客学的：
https://blog.csdn.net/qq_40693171/
article/details/84780224