信号量解决五个哲学家吃通心面问题

题型一

有五个哲学家围坐在一圆桌旁，桌中央有盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。

 

Semaphore fork[5]={1,1,1,1,1}；
Semaphore footman=4;
//最多允许4个哲学家进程同时进行 
cobegin
process philosopher_i(){/*i=0,1,2,3,4 */while(true){P(footman); Think(); P(fork[i]);  P(fork[(i+1)%5]);Eat(); V(fork[i]); V(fork[(i+1)%5]);   V(footman); }} 
coend

题型二

哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全体到齐后开始讨论；在讨论的间隙四位哲学家进餐，每人进餐时都需使用刀、叉各一把，餐桌上的布置如下图所示。用信号量机制说明四位哲学家的同步互斥过程。

 

分析

标准的哲学家进餐问题，只是哲学家人数和餐具及分布与经典哲学家进餐问题略有不同

数据结构

semaphore fork1,fork2,knife1,knife2;

frok表示叉，knife表示刀，初值均为1

pa //哲学家甲
do{P(knife1);P(fork1);进餐；V(knife1);V(fork1);讨论问题；
}while(1);

pb //哲学家乙
do{P(knife2);P(fork1);进餐；V(knife2);V(fork1);讨论问题；
}while(1);

pa //哲学家丙
do{P(knife2);P(fork2);进餐；V(knife2);V(fork2);讨论问题；
}while(1);

pb //哲学家丁
do{P(knife1);P(fork2);进餐；V(knife1);V(fork2);讨论问题；
}while(1);

理发师问题

理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子

如果没有顾客，理发师便在理发椅上睡觉

一个顾客到来时，它必须叫醒理发师

如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开

int waiting=0;//等候理发顾客数
int CHAIRS=N; //为顾客准备的椅子数
semaphore customers,barbers,mutex;
customers=0;barbers=0;mutex=1;cobegin
process barber( ) {while(true) {P(customers);       //有顾客吗？若无顾客，理发师睡眠P(mutex);           //若有顾客时，进入临界区waiting--;          //等候顾客数少一个V(barbers);         //理发师准备为顾客理发V(mutex);           //退出临界区cut_hair();         //理发师正在理发(非临界区)}
}process customer_i( ) {P(mutex);             //进入临界区if(waiting<CHAIRS) {  //有空椅子吗waiting++;          //等候顾客数加1V(customers);       //唤醒理发师V(mutex);           //退出临界区P(barbers);         //理发师忙，顾客坐下等待get_haircut();      //否则顾客坐下理发}else V(mutex);        //人满了，走吧！
}
coend

运行过程： 

1. customer : p(mutex)
2. customer : waiting
3. customer : v(customers)
4. barber : p(customers) → p(mutex) & waiting
5. customer : v(mutex)
6. barber : p(mutex)
7. barber : wating - -
8. barber : v(barbers)
9. barber : v(mutex)
10. customer : p(barbers)
11. barber : cut_hair( )
12. customer : get_haircut( )

生产者消费者问题

①一个生产者、一个消费者共享一个缓冲区 ②一个生产者、一个消费者共享多个缓冲区 ③多个生产者、多个消费者共享多个缓冲区

一个生产者、一个消费者共享一个缓冲区

int B;
semaphore empty;  //可以使用的空缓冲区数
semaphore full;  //缓冲区内可以使用的产品数
empty=1;         //缓冲区内允许放入一件产品
full=0;          //缓冲区内没有产品

****cobegin
process producer(){       while(true){               produce( );                P(empty);                  append( ) to B;            V(full);                   }                         
}                         
coend****

****cobegin
process consumer(){while(true) { P(full);take( ) from B;V(empty);consume( );}
}
coend****

多个生产者/消费者、共享多个缓冲区的解

桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；儿子专等吃盘中的香蕉，而女儿专等吃盘中的苹果。

item B[k];
semaphore empty;	
empty=k;  
semaphore full; 
full=0;      
semaphore mutex=1;  //互斥信号量
int in=0;	//放入缓冲区指针
int out=0;   //取出缓冲区指针
cobegin

cobegin
process producer_i ( ){while(true) {produce( );P(empty);P(mutex);append to B[in]; in=(in+1)%k;  V(mutex);            V(full);                }
}
coend

cobegin
process consumer_j ( ){    while(true) {P(full);P(mutex);take( ) from B[out];out=(out+1)%k;V(mutex);V(empty);consume( );}
}
coend

读者写者问题

 

有两组并发进程：读者和写者，共享一个文件F

允许多个读者同时执行读操作

任一写者在完成写操作之前不允许其它读者或写者工作

写者执行写操作前，应让已有的写者和读者全部退出

int readcount=0;//读进程计数
semaphore writeblock = 1;
semaphore mutex= 1;

cobegin
process reader_i( ){          P(mutex);readcount++; if(readcount==1)P(writeblock); V(mutex);{读文件};P(mutex);readcount--;if(readcount==0)V(writeblock);V(mutex);
}
coend

cobegin
process writer_j( ){P(writeblock);{写文件};V(writeblock);
}
coend

某小型超级市场有一个出入口，出入口处有80个篮子，每个购物者拿到一只篮子后可入内购物，购物结束后在出入口处结账，并归还篮子。出入口处禁止多人同时通行，试用信号量和P、V操作写出购物物者进程的同步算法

semaphore  count=80,mutex = 1; 
shopping( )//购物者进程{P(count)    P(mutex)   进入超市购物       V(mutex)P(mutex)结账离开  V(mutex)V(count)  }

某车站售票厅有一个售票窗口，窗口不允许同时有多个人买票，任何时刻最多可容纳20名购票者进入售票厅排队，当售票厅内已有20名购票者时，其余购票者需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

(1)用PV操作管理这些并发进程时，写出信号量的定义及初值;

(2)根据所定义的信号量，在下面程序段中合适的位置加上PV操作，以保证进程能正确地并发执行。

semaphore  mutex = 1 ;//用于购票窗口互斥    
semaphore  count = 20 ;//用于表示可容纳20人购票进程同步  
cobegin
PROCESSPI(I=1，2，……)//购票者进程1,2.......{P(count)  进入售票厅；P(mutex)   购票；V(mutex);  退出；V(count);   
}
coend

设公共汽车上，司机和售票员的活动分别如下：司机的活动：启动车辆：正常行车：到站停车。售票员的活动：关车门：售票：开车门。在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系?用信号量和P、V操作实现它们的同步。

semaphore  door = 0 , stop  = 0 ; 
process driver()
{P(door)启动车辆，正常行车车辆到站停车V(stop)
}
process saler()
{关车门V(door) 售票P(stop)开车门
}

另一个经典同步问题：吸烟者问题(patil , 1971 )。三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另-一个吸烟者。试采用:(1 )信号量和P、V操作编写他们同步工作的程序。

Semaphore a=b=c=0，s=1;
Cobegin
Process P1(){while(1){P(a)卷烟，抽烟V(s)
}}Process p2(){while(1){P(b)卷烟，抽烟V(s)
}}Process p3(){while(1){P(c)卷烟，抽烟V(s)
}}Process supply(){
while(1){P(s)if(放烟草和纸)  V(c)else if(放烟草和胶水)  V(b)else V(a)
}}
Coend