嵌入式系统及应用：进程间的制约关系(经典同步问题)

1、经典进程同步问题经典进程同步问题读者-写者问题哲学家就餐问题“理发店”问题读者-写者问题数据对象可以为多个并发进程所共享 有两种并发进程: 读者：写者：共享一组数据区同步要求：同一时刻只允许一个写者写。同一时刻可允许多个读者读。不允许读者、写者同时操作。读者-写者问题 程序描述读者： 读者读取所需数据写者： 写者对数据进行修改读者优先的读者-写者问题如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待用P、V信号量来解决读者-写者问题读者： 读者读取

2、所需数据写者： 写者对数据进行修改设置信号量wrt，初始值为1;用P、V信号量来解决读者-写者问题读者： P（wrt） 读者读取所需数据 V（wrt）写者： P（wrt） 写者对数据进行修改 V（wrt）设置信号量wrt，初始值为1;不满足读者优先要求用P、V信号量来解决读者-写者问题读者： P（wrt） 读者读取所需数据 V（wrt）写者： P（wrt） 写者对数据进行修改 V（wrt）设置信号量wrt，初始值为1;添加共享变量reader，初始值为0；用P、V信号量来解决读者-写者问题读者： reader=reader+1 if reader=1 P（wrt） 读者读取所需数据 V（wrt

3、）写者： P（wrt） 写者对数据进行修改 V（wrt）设置信号量wrt，初始值为1;添加共享整型变量reader，初始值为0；问题：读者读完数据退出时数据是否需要更新？用P、V信号量来解决读者-写者问题读者： reader=reader+1 if reader=1 P（wrt） 读者读取所需数据 reader=reader-1 V（wrt） 写者： P（wrt） 写者对数据进行修改 V（wrt）设置信号量wrt，初始值为1;添加共享整型变量reader，初始值为0；用P、V信号量来解决读者-写者问题读者： reader=reader+1 if reader=1 P（wrt） 读者读取所需数据

4、 reader=reader-1 if reader=0 V（wrt） 写者： P（wrt） 写者对数据进行修改 V（wrt）设置信号量wrt，初始值为1;添加共享整型变量reader，初始值为0；用P、V信号量来解决读者-写者问题读者： P(mutex) reader=reader+1 if reader=1 P（wrt） V(mutex) 读者读取所需数据 P(mutex) reader=reader-1 if reader=0 V（wrt） v(mutex) 写者： P（wrt） 写者对数据进行修改 V（wrt）设置信号量wrt，初始值为1;mutex,初始值1；设置共享整型变量read

5、er，初始值为0；“理发店”问题理发店中有k张理发椅和n张给等待理发的顾客坐的座椅。入口座椅座椅座椅座椅座椅理发椅n张理发椅理发椅k张出口若没有顾客，理发师就坐在理发椅上打盹；当顾客来时，就唤醒打盹的理发师进行理发；若理发师全在工作，又来新顾客，则就坐在空座椅上等待理发，没有空座椅就离去。试用信号量上的P、V操作描述理发师和顾客的行为，保证该过程的正确实现。“理发店”问题 程序描述理发师程序barber() cut_hair();顾客程序customer() get_haircut(); “理发店”问题-P、V信号量解法设置同步信号量custs：记录等待理发的顾客数(不包括正在理发的顾客)，初

6、值为0；barbs：正在等待为顾客理发的理发师数，初值为k；“理发店”问题-P、V信号量解法理发师程序barber() P(custs); /申请顾客 cut_hair();顾客程序customer() P(barbs); /申请理发师 get_haircut();“理发店”问题-P、V信号量解法理发师程序barber() P(custs); /申请顾客 cut_hair(); V(barbs); /释放理发师 顾客程序customer() V(custs); /释放顾客 P(barbs); /申请理发师 get_haircut();“理发店”问题-P、V信号量解法设置同步信号量custs：记

7、录等待理发的顾客数(不包括正在理发的顾客)，初值为0；barbs：正在等待为顾客理发的理发师数，初值为k；设置变量waiting，它的初值为0。记录等待理发的顾客数“理发店”问题-P、V信号量解法顾客程序customer() if(waitingn) waiting=waiting+1; V(custs); P(barbs); get_haircut(); 理发师程序barber() P(custs); cut_hair(); V(barbs); “理发店”问题-P、V信号量解法顾客程序customer() if(waitingn) waiting=waiting+1; V(custs); P

8、(barbs); get_haircut(); 理发师程序barber() P(custs); cut_hair(); waiting=waiting-1; V(barbs); “理发店”问题-P、V信号量解法设置同步信号量custs：记录等待理发的顾客数(不包括正在理发的顾客)，初值为0；barbs：正在等待为顾客理发的理发师数，初值为k；设置变量waiting，它的初值为0。记录等待理发的顾客数设置互斥信号量mutex：互斥使用waiting“理发店”问题-P、V信号量解法理发师程序barber() P(custs); P(mutex); waiting=waiting-1; V(mute

9、x); cut_hair(); V(barbs); 顾客程序customer() P(mutex); if(waitingn) waiting=waiting+1; V(custs); V(mutex); P(barbs); get_haircut(); else V(mutex);哲学家就餐问题问题描述：有五个哲学家围坐在一圆桌旁，每人面前有一盘食物，每两人之间放一只筷子哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；哲学家就餐问题 程序描述哲学家进程

10、： think(); eat();哲学家就餐问题解法15个哲学家须互斥使用5只筷子，若其中一个拿到他右边的那只筷子，那么坐在他右边的哲学家的左手就暂时不能拿那只筷子。为此，给每只筷子编号，为04 对应设置5个互斥信号量：chopsticki (0i4) 初值为10432143210哲学家编号筷子编号第i个哲学家的“思考-就餐-思考”过程可描述为： philosopher(i) while(TRUE) think(); P(chopsticki); P(chopstick(i+1) mod 5); eat(); V(chopsticki); V(chopstick(i+1) mod 5); 为防

11、止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 哲学家就餐问题解法2设置5个互斥信号量：chopsticki (0i4) /对应筷子 初值=1设置信号量seat / 代表了座位数初始值=4；0432143210哲学家编号筷子编号第i个哲学家的“思考-就餐-思考”过程可描述为： philosopher(i) while(TRUE) think(); P(seat); P(chopsticki); P(chopstick(i+1) mod 5); eat();

12、V(chopsticki); V(chopstick(i+1) mod 5); V(seat); 哲学家就餐问题解法3仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子把哲学家分为三种状态:THINKING 思考状态：哲学家就餐后，就由就餐状态EATING转变成思考状态。 EATING 就餐状态：处于该状态的哲学家已拿到自己左右的两只筷子，由饥饿状态转变成为就餐状态。 HUNGRY 饥饿状态：当某哲学家在思考中想吃饭时，就由思考状态转变成为饥饿状态。哲学家就餐问题解法3 初始化设置数组statei (0i4)每个哲学家一个，表示哲学家的状态。设置信号量数组si (0i4)每个哲学家一个，表示

13、是否可以就餐。初值都为0。在拿不到筷子就餐时，用它来与占用筷子的哲学家取得同步，以期归还筷子时，能唤醒受阻塞的哲学家。设置两个变量，表示第i个哲学家左右相邻哲学家的编号：LEFT=(i+4) mod 5，RIGHT=(i+1) mod 5(0i4)设置互斥信号量mutex，初值为1。为保证各哲学家在测试他左右相邻者的状态和设置新状态时，能互斥地进行哲学家 i 程序philosopher (i) while (true) thinking( ); take_chopstick(i)； eat； put _ chopstick(i); 测试状态子程序test(i) if(statei=HUNGRY & stateLEFT!=EATING & stateRIGHT!=EATING) statei=EATING; V(si); 归还筷子子程序put_chopstick(i) P(mutex); statei=THINKING; test(LEFT); test(RIGHT); V(mutex);获取筷子子程序take_chopstick(i) P(mutex); statei=HUNGRY; test(i); V(mutex); P(si);测试状态子程序test(i) if(statei=HUNGRY & sta