第10课进程间的制约关系(经典同步问题)

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

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

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

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

5、) n写者： P（wrt） 写者对数据进行修改 V（wrt）n设置信号量wrt，初始值为1;mutex,初始值1；n设置共享整型变量reader，初始值为0；“理发店理发店”问题问题n理发店中有k张理发椅和n张给等待理发的顾客坐的座椅。入口座椅座椅座椅座椅座椅理发椅n张理发椅 理发椅k张出口n若没有顾客，理发师就坐在理发椅上打盹；当顾客来时，就唤醒打盹的理发师进行理发；n若理发师全在工作，又来新顾客，则就坐在空座椅上等待理发，没有空座椅就离去。n试用信号量上的P、V操作描述理发师和顾客的行为，保证该过程的正确实现。“理发店理发店”问题问题 程序描述程序描述n理发师程序barber() cut_

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

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

8、s); P(barbs); get_haircut(); n理发师程序barber() P(custs); cut_hair(); V(barbs); “理发店理发店”问题问题-P、V信号量解法信号量解法n顾客程序customer() if(waitingn) waiting=waiting+1; V(custs); P(barbs); get_haircut(); n理发师程序barber() P(custs); cut_hair(); waiting=waiting-1; V(barbs); “理发店理发店”问题问题-P、V信号量解法信号量解法n设置同步信号量custs：记录等待理发的顾客

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

10、get_haircut(); else V(mutex);哲学家就餐问题n问题描述：有五个哲学家围坐在一圆桌旁，每人面前有一盘食物，每两人之间放一只筷子哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；哲学家就餐问题 程序描述n哲学家进程： think(); eat();哲学家就餐问题解法1n5个哲学家须互斥使用5只筷子，若其中一个拿到他右边的那只筷子，那么坐在他右边的哲学家的左手就暂时不能拿那只筷子。n为此，给每只筷子编号，为04 对应设置5个互斥信号量

11、：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); 为防止死锁发生可采取的措施：n最多允许4个哲学家同时坐在桌子周围n仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子n给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 哲学家就餐问题解法2设置5

12、个互斥信号量：chopsticki (0i4) /对应筷子 初值=1设置信号量seat / 代表了座位数初始值=4；0432143210哲学家编号筷子编号第i个哲学家的“思考-就餐-思考”过程可描述为： philosopher(i) while(TRUE) think(); P(seat); P(chopsticki); P(chopstick(i+1) mod 5); eat(); V(chopsticki); V(chopstick(i+1) mod 5); V(seat); 哲学家就餐问题解法3n仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子n把哲学家分为三种状态:THINKING

13、 思考状态：哲学家就餐后，就由就餐状态EATING转变成思考状态。 EATING 就餐状态：处于该状态的哲学家已拿到自己左右的两只筷子，由饥饿状态转变成为就餐状态。 HUNGRY 饥饿状态：当某哲学家在思考中想吃饭时，就由思考状态转变成为饥饿状态。哲学家就餐问题解法3 初始化n设置数组statei (0i4)每个哲学家一个，表示哲学家的状态。n设置信号量数组si (0i4)每个哲学家一个，表示是否可以就餐。初值都为0。在拿不到筷子就餐时，用它来与占用筷子的哲学家取得同步，以期归还筷子时，能唤醒受阻塞的哲学家。n设置两个变量，表示第i个哲学家左右相邻哲学家的编号：LEFT=(i+4) mod 5

14、，RIGHT=(i+1) mod 5(0i4)n设置互斥信号量mutex，初值为1。为保证各哲学家在测试他左右相邻者的状态和设置新状态时，能互斥地进行n哲学家 i 程序philosopher (i) while (true) thinking( ); take_chopstick(i)； eat； put _ chopstick(i); n测试状态子程序test(i) if(statei=HUNGRY & stateLEFT!=EATING & stateRIGHT!=EATING) statei=EATING; V(si); n归还筷子子程序put_chopstick(i) P(mutex); statei=THINKING; test(LEFT); test(RIGHT); V(mutex);n获取筷子子程序获取筷子子程序take_chopstick(i) P(mutex); statei=HUNGRY; test(i); V(mutex); P(si);n测试状态子程序test(i) if(statei=HUNGRY & state