操作系统-PV操作.ppt

,1、用P.V操作解决下面的同步问题,get,copy,put,f,s,t,g,要解决的同步问题：Get不能向“满”的S中放；Copy不能从“空”的S中取；不能向“满”的T中放；Put不能从“空”的T中取,有3个进程：get,copy和put，它们对4个存储区域f、s、t和g进行操作：其中：f有取之不尽的数据可以get；g有用之不完的空间可以puts和t则只有一个存储空间。,3,4,.,m,2,2,(1,2),2,3,4,.,m,1,1,(1),1,2,3,4,.,m,(),（同步）信号量：实际上也起到互斥作用S_Empty,T_Empty，初值为1S_Full,T_Full;初值为0,Get进程:Begin Repeat P(S_Empty)T_get_S();V(S_Full);Until false;End,Copy进程:Begin Repeat P(S_Full);P(T_Empty);S_copy_T();V(T_Full);V(S_Empty);Until false;End,Put进程:Begin Repeat P(T_Full);T_put_G();V(T_Empty);Until false;End,2、重新研究司机和售票员问题，分别写出司机和售票员进程，从而实现该问题的同步,司机进程：Begin Repeat P(S_Door);行驶；停车；V(S_Stop);Until false;End,乘务员进程:Begin Repeat 关门；V(S_Door);售票；P(S_Stop);开门；Until false;End,Var S_Door,S_Stop:Semaphore:=0,0,司机进程：Begin Repeat P(door);行驶；停车;V(stop);Until false;End,乘务员进程:Begin RepeatP(stop);开门；关门；V（door）；售票;Until false;End,Var door，stop:semaphore：1，0,3、桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。,分析：本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种变形：这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品,S：表示盘子是否为空，其初值为l；So：表示盘中是否有桔子，其初值为0；Sa：表示盘中是否有苹果，其初值为0。,设置三个信号量:S、So、Sa，,Daughter进程：while(1)P(Sa);从盘中取出苹果;V(S);吃苹果;,Father进程：while(1)P(S);将水果放入盘中;if（放入的是桔子）V(So);else V(Sa);,Son进程：while(1)P(So);从盘中取出桔子;V(S);吃桔子;,分析问题中涉及的进程；分析问题中的同步关系（竞争，合作）；（其中，合作关系的解决也是通过转化为对资源的竞争完成的。）参照所竞争的资源设置信号量，并赋予初值；写出各个进程的描述；检查每个进程的描述，看是否会出现死锁现象并改正之。,小结：同步问题解法,具体的规范格式如下（以苹果桔子题目为例：）,int S1;int Sa0;int So0;main()cobegin father();/*父亲进程*/son();/*儿子进程*/daughter();/*女儿进程*/coend,解：设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为l；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下：,father()while(1)P(S);将水果放入盘中;if（放入的是桔子）V(So);else V(Sa);,son()while(1)P(So);从盘中取出桔子;V(S);吃桔子;,daughter()while(1)P(Sa);从盘中取出苹果;V(S);吃苹果;,作业：睡眠理发师问题,作业：睡眠理发师问题,问题描述（经典理发师问题）假设后街有家理发店，店里有一个理发师、一把理发椅和n把等候理发的顾客椅子。（1）.如果没有顾客则理发师便在理发椅上睡觉（看报纸）；（2）.当有一个顾客到达时，首先查看理发师在干什么，如果在睡觉（看报纸）则告诉理发师理发，然后坐到理发椅上开始理发；如果理发师正在理发，则查看是否有空的椅子可坐，如果有，他就坐下等待，如果没有，则离开；（3）.理发师为一位顾客理完发后，查看是否有人等待，如有则唤醒一位为其理发，如没有则在理发椅上睡觉（看报纸）；（4）.顾客不分优先级,作业：睡眠理发师问题,问题分析 题目中要求描述理发师和顾客的行为，因此需要两类进程Barber()和Customer()分别描述理发师和顾客的行为。当理发师看报时顾客近来需要唤醒理发师为其理发，当有顾客时理发师为其理发，没有的时候理发师看报，因此理发师和顾客之间是同步的关系，由于每次理发师只能为一个人理发，且可供等侯的椅子有限只有n个，即理发师和椅子是临界资源，所以顾客之间是互斥的关系。故引入3个信号量和一个控制变量：1)控制变量waiting用来记录等候理发的顾客数，初值均为0；2)信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；3)信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为0；4)信号量mutex用于互斥，初值为1,作业：睡眠理发师问题,问题实现 PV操作代码如下:int waiting=0；/等候理发的顾客数 int chairs=n；/为顾客准备的椅子数 semaphore customers=0,barbers=0,mutex=1;barber()while(TRUE);/理完一人,还有顾客吗?P(cutomers);/若无顾客,理发师睡眠 P(mutex);/进程互斥 waiting:=waiting 1;/等候顾客数少一个 V(barbers);/理发师去为一个顾客理发 V(mutex);/开放临界区 cut-hair();/正在理发,作业：睡眠理发师问题,问题实现（接上页）customer()P(mutex);/进程互斥 if(waiting)waiting:=waiting+1;/等候顾客数加1 V(customers);/必要的话唤醒理发师 V(mutex);/开放临界区 P(barbers);/无理发师,顾客坐着养神 get-haircut();/一个顾客坐下等理/else V(mutex);/人满了,走吧!,