进程同步互斥问题

本文主要是对经典的进程同步互斥问题的分析，学习之前先了解临界资源，信号量的概念。

一. 纯互斥问题

1. 读者写者问题

1.1 读者优先

所谓读者优先是指读者可以同时读，除非目前有写者在写

分析：

• 读者可以搭便车，意味着首个占用资源的读者和最后一个使用完资源的读者很重要
• 对读者数量的计数是互斥，设readCount计数，mutex实现对其的互斥访问
• 再设一个信号量write，实现对文件资源的互斥

读者：
    begin
    	P(mutex);
		readCount := readCount + 1;
		if readCount == 1
			then P(write);//第一个读者处理后，其余读者可以搭便车
		V(mutex);
		读文件;
		P(mutex);
		readCount := readCount - 1;
		if readCount == 0
            then V(write);
		V(mutex);
	end
写者：
    begin
    	P(write);
		写文件;
		V(write);
	end

1.2 写者优先

写者优先是指一旦有个写者到来，他应该尽快对文件进行写操作，也就是一个写者在等待则新来的读者不允许进行读操作了

分析：

• 写者到达，读者后续不可搭便车。设置w信号量，实现读写平权

读者：
    begin
    	P(w);//与读者优先的区别，读者来时判断有无写者在等待
    	P(mutex);
		readCount := readCount + 1;
		if readCount == 1
			then P(write);
		V(mutex);
		V(w);
		读文件;
		P(mutex);
		readCount := readCount - 1;
		if readCount == 0
            then V(write);
		V(mutex);
	end
写者：
    begin
        P(w);
    	P(write);
		写文件;
		V(write);
		V(w);
	end

2. 船闸问题

巴拿马运河，建在太平洋和大西洋之间，由于太平洋和大西洋水面高度不同，有巨大落差，所以运河中修建有t级船闸，并且只允许单向通行，船闸依次编号为，1,2,3,,,T。由大西洋来的船，需经由船闸T,T-1,2,,,1，通过运河到太平洋，由太平洋来的船，需经由船闸1,2,3,,,T通过运河到大西洋。试用pv操作，正确解决大西洋和太平洋的船只通航问题

分析：

• 制约关系是在经过相同的某一号船闸时，PtoA应该互斥AtoP，纯互斥问题

int S[T+1]=1;//为每一个船闸设置一个信号量
int countAtoP[T+1]=0;
int countPtoA[T+1]=0;
AtoP:
    begin
        for(j=1;j<=T;j++){
            P(mutex);
            if(countAtoP[j]==0)//A到P没船
                P(S[j]);升闸门;
            countAtoP[j]++;
            V(mutex);
            过船;
            P(mutex);
            countAtoP[j]--;
            if(countAtoP[j]==0)//A到P没船
                降闸门;V(S[j]);
            V(mutex);
        }
	end
PtoA:
	begin
        for(j=1;j<=T;j++){
            P(mutex);
            if(countPtoA[j]==0)
                P(S[j]);升闸门;
            countPtoA[j]++;
            V(mutex);
            过船;
            P(mutex);
            countPtoA[j]--;
            if(countPtoA[j]==0)
                降闸门;V(S[j]);
            V(mutex);
        }
	end

3. 甲乙地自行车问题

二. 进程同步

1. 次序同步问题

有几个入就P几次，有几个出就V几次

变体1：
学生两人一组上机问题，到达两人后进，做完后出

转化为时序图

2. 共享缓冲区同步问题(单缓冲区)

2.1 简单的生产者消费者问题

生产者——> 缓冲区 <—– 消费者

S1=0 S2=1
生产者:
	P(S2);
	生产一个产品;
	放入;
	V(S1);
消费者:
	P(S1);
	拿产品;
	V(S2);

2.2 酒吧音乐粉丝问题

纯同步问题，boss产生一个资源（三类资源中的一个） vs 三类fans物品的排列组合

分析：

• 听音乐的爱好者不听完，老板不会新一轮借出
• 老板不借出2/3的物品，对应的拥有1/3物品的爱好者不能开始听音乐，关键问题在于，要根据借出的2/3物品，将各种物品组合分开
• 制约关系，设音乐爱好者私有信号量wait，代表是否听完音乐，初值为0
• 制约关系，各个fans受boss制约：设老板的私有信号量S{s1,s2,s3}对应三种物品组合S1:CD+电池vs缺随身听的fans；S2：电池+随身听vs缺cd的fans；S3：CD+随身听vs缺电池的fans，s1,s2,s3初值都为0

Boss()
{
	int s=genservice();//伪函数，生成三种物品组合
	if(s==1) v(S1);
    else if(S==2) v(S2);
    else v(S3);
	P(wait);
}
Fans(i)  //i=1~3
{
	P(Si);
	听音乐；
	V(wait);
}

2.3 医生-化验员问题

分析：

• 化验员受医生制约在没有化验单的时候，为医生设置私有信号量Sd=0,代表有无化验单
• 医生受化验员制约，在没有化验结果的。为化验员设私有信号量Sh=0,代表有无化验结果

P医生(){             
	接待病人；      
	问诊；          
	开化验单；       
	V(Sd);          
	P(Sy);            
	开处方；
}
P化验员(){
    P(Sd);
    化验;
    得到化验结果;
    V(Sy);
}

2.4 司机-售票员问题

分析：

• 只有司机到站停车后，售票员才能开车门；为司机设私有信号量Sd=1，代表是否到站停车；
• 只有售票员关门后，司机才能启动车辆、行车；为售票员设私有信号量Sc=0，代表是否关车门；

driver(){
	P(Sc);
    启动;
    到站停车;
    V(Sd);
}
conductor{
    P(Sd);
    开车门;
    上下乘客;
    关门;
    V(Sc);
}

2.5 复杂仓库问题

三个进程,Pa生产零件A,Pb生产零件B,Pc获取零件A和B,三类进程之间需要同步，同类进程访问货架需要互斥

分析：

• 货架F1全满，Pa要受到Pc制约：为进程Pc设私有信号量Sc1,代表F1是否有空位，初值为10
• 货架F2全满，Pb受到Pc制约：为进程Pc设私有信号量Sc2,代表F2是否有空位，初值为10
• 货架F1全空，Pc受到Pa制约：为Pa设私有信号量Sa,代表零件A的数目；初值为0
• 货架F2全空，Pc受到Pb制约：设私有信号量Sb,代表零件B个数。初值为0
• 互斥因素：任1进程访问货架F1或F2,需互斥:设互斥信号量mutex1=1,货架F2,mutex2=1

Pa()                Pb()                     Pc()
{  while(1){          { while(1){              { while(1){
	P(Sc1);            P(Sc2);                   P(Sa);
	P(mutex1);         P(mutex2);                P(mutex1); 
	A-->F1;            B-->F2;                   F1-->A;
	V(mutex1);         V(mutex2);                V(mutex1);
	V(Sa);             V(Sb);                    V(Sc1);
}}                    }}                         P(sb);
                                                 P(mutex2);
                                                 F2-->B;
                                                 V(mutex2);
                                                 V(Sc2);
                                                 开始装配A+B;
                                                }}

2.6 两同步共享一互斥

桌子上有一个盘子，每次只放/取一个水果，爸爸专门放苹果，妈妈专门放桔子，女儿专吃苹果，儿子专吃桔子

father(){
  	P(empty);
  	放苹果
	V(apple);
}
daughter(){
  	P(apple);
  	拿苹果
	V(empty);
}
mother(){
  	P(empty);
  	放桔子
	V(orange);
}
son(){
  	P(orange);
  	拿桔子
	V(empty);
}

3. 双缓冲区问题

誊抄问题，打印机问题

A–>B–>C

Get()               copy()                 Put()
{                   {                      	{
产生一条data;        	P(S1);                 	P(S3); 
P(S2);                 buf1->data;             buf2->data;
Data-buf1;             V(S2);                  V(S4);
V(S1);                 P(S4);               }
}                      data->buf2;
                       V(s3);}

4. 多缓冲vs多进程的同步

多缓冲 生产者-消费者

Pi(i)                 	Qj(j)  //j=1~n
{//当buf全满时,k=0        {//buf全空，引发死锁
产生一条data;               P(full);
P(empty);                  p(mutex);
P(mutex);                  buf->data;
Data->buf;                 v(empty);
V(full);                   v(mutex);
V(mutex);                }
}

注意：信号量的p操作的顺序，一定是先私后公。如果先公后私，在buf全满或全空的情况下，会引发死锁。

5. 拓展

5.1 理发师问题

N把椅子+1个barber

baber()							customer()
{								{ p(mutex);//进来首先看有无空位，访问count
p(customer);看看有无顾客，否则睡觉。  if(count>0)
P(mutex);若有，准备理发         		{count--; //临界区
count++;座位加一					   v(mutex);
V(mutex);							  v(customer);//告诉理发师有顾客来到
开始理发；							   p(barber);//看理发师有无空闲
理发完成；                              理发；}
V(barber);	                       else{v(mutex);exit;}
}								}

5.2 银行柜员问题

n个柜员，有空闲就叫一个号

Teller()
{P(Sc);
P(mutex);
叫号;
V(mutex);
为顾客服务;
服务完成；
V(St);}
customer()
{
P(mutex);
取号;
V(mutex);
V(Sc);
P(St);
接受服务;
}