进程同步习题全.pptx

进程管理进程管理设有设有n n个进程共享一个程序段，对如下两种情况：个进程共享一个程序段，对如下两种情况：（1)1)如果每次只允许一个进程进入该程序段；如果每次只允许一个进程进入该程序段；(2)(2)如果每次最多允许如果每次最多允许m m个进程个进程(M(Mn)n)同时进入该同时进入该程序段。程序段。试问：所采用的信号量初值是否相同试问：所采用的信号量初值是否相同?信号量值的变信号量值的变化范围如何化范围如何?所采用信号量的初值不相同。所采用信号量的初值不相同。在情况在情况(1)(1)中，信号量的初值为中，信号量的初值为1 1，信号量值的变化范围是信号量值的变化范围是l l，0 0，-1-1-(n-1)-(n-1)。在情况在情况(2)(2)中，信号量的初值为中，信号量的初值为M M，信号量值的变化范围是信号量值的变化范围是M M，m-1m-1，m-2m-2(m-n)(m-n)。进程同步习题进程同步习题进程管理进程管理【例】一个buffer,一个生产者，一个消费者，生产者只生产一个东西，消费者只进行一次消费，即：生产者只进行一次putdata操作，消费者只进行一次getdata操作。进程管理进程管理【解答】设置信号量full,表示buffer是否有数据,初值为0生产者消费者putdataP(full)V(full)getdata进程管理进程管理【例】一个buffer,一个生产者，一个消费者，生产者不断进行putdata操作，消费者不断进行getdata操作，即生产者不断生产，消费者不断消费。【解答】buffer为空时，才能进行putdata操作，只有buffer有数据时，才能进行getdata操作信号量full:是否有数据初值为0empty:是否为空，初值为1进程管理进程管理生产者：repeatP(empty)putdataV(full)消费者：repeat P(full)getdata V(empty)进程管理进程管理【例】一个buffer,多个生产者，多个消费者，多个生产者和消费者都在不断地存取buffer，即生产者不断地进行putdata操作，消费者不断进行getdata操作。【解答】只有buffer为空时能进行putdata操作，只有buffer有数据时能进行putdata操作。不允许多个进程同时操作buffer,即不允许多个消费者同时进行getdata,不允许多个生产者进行putdata操作信号量full:buffer是否有数据，初值为0empty:buffer是否为空，初值为1mutex:buffer是否可操作，初值为1进程管理进程管理生产者irepeatP(empty)P(mutex)putdataV(mutex)V(full)消费者irepeat P(full)P(mutex)getdata V(mutex)V(empty)进程管理进程管理【例】多个生产者，多个消费者，N个buffer，多次循环存取buffer,即多个生产者不断进行putdata操作，多个消费者不断进行getdata操作【解答】只有buffer有空间时才能进行putdata操作只有buffer有数据时才能进行getdata操作不允许多个消费者和多个生产者同时操作信号量full:表示buffer是否有数据，初值为0empty:表示buffer是否为空，初值为nmutex:表示buffer是否可操作，初值为1进程管理进程管理生产者irepeatP(empty)P(mutex)putdataV(mutex)V(full)消费者j repeat P(full)P(mutex)putdata V(mutex)V(empty)进程管理进程管理【改进】putdata和getdata操作都在临界区中，因此多个进程对多个buffer的操作不能并行进行的，进程间并行操作的程度很低。实际上只要保证多个进程同时操作不同buffer就可以实现对整个buffer的并行操作。getEBuffer()返回空的buffer号getEBuffer()return(pbuffer+1)modngetDBuffer()返回有数据的buffer号getDBuffer()return(pdata+1)modn进程管理进程管理semaphoremutex,empty,full=1,n,0integerpbuff,pdata=0,0生产者i消费者jrepeatrepeatP(empty)P(full)P(mutex)P(mutex)in=getEBuffer()out=getDBuffer()V(mutex)V(mutex)putdata(in)getdata(out)V(full)V(empty)进程管理进程管理【练习】如图，有多个PUT操作同时向Buff1放数据，有一个MOVE操作不断地将Buff1的数据移到Buff2,有多个GET操作不断地从Buff2中将数据取走。Buff1的容量是m,Buff2的容量是n,PUT,MOVE,GET每次操作一个数据，在操作的过程中要保证数据不丢失。试用P,V原语协调PUT,MOVE操作，并说明每个信号量的含义和初值。进程管理进程管理Buff1Buff2MOVEPUTGET进程管理进程管理【解答】三类进程：多个PUT类进程，一个MOVE类进程，多个GET类进程操作规则1只有buff1有空间才能进行PUT操作2只有buff1有数据，buff2有空间才能进行MOVE操作3只有buff2有数据才能进行GET操作4不允许多个进程同时操作buff15不允许多个进程同时操作buff2进程管理进程管理操作流程repeat判断buff1是否有空间，没有则等待是否可操作buff1PUT设置buff1可操作标志设置buff1有数据的标志untilfalse进程管理进程管理repeat判断buff1是否有数据，没有则等待判断buff2是否有空间，没有则等待是否可操作buff1是否可操作buff2MOVE设置buff1可操作标志设置buff2可操作标志设置buff1有空间标志设置buff2有空间标志进程管理进程管理repeat判断buff2是否有数据，没有则等待是否可操作buff2GET设置buff1可操作标志设置buff1有空间标志进程管理进程管理4信号量设置6个信号量full1:buff1是否有数据，初值为0empty1:buff1有空间，初值为mmutex1:buff1是否可操作，初值为1full2:buff2是否有数据，初值为0empty2:buff2有空间，初值为nmutex2:buff2是否可操作，初值为1进程管理进程管理5PV操作实现repeatp(empty1);/判断buff1是否有空间，没有则等待p(mutex1);/是否可操作buff1PUT;v(mutex1);/设置buff1可操作标志v(full);/设置buff1有数据标志进程管理进程管理repeatP(full1）；判断buff1是否有数据，没有则等待P(empty2);/判断buff2是否有空间，没有则等待P(mutex1);/是否可操作buff1P(mutex2);/是否可操作buff2MOVE;V(mutex1);/设置buff1可操作标志V(mutex2);/设置buff2可操作标志V(empty1);/设置buff1有空间标志V(full2);/设置buff2有数据标志进程管理进程管理repeatP(empty2);/判断buff2是否有空间，没有则等待P(mutex2);/是否可操作buff2GETV(mutex2);/设置buff2可操作标记V(full2);/设置buff2有数据标记进程管理进程管理【例】现有4个进程R1，R2，W1，W2。它们共享可以存放一个数据的缓冲器B。进程R1每次把磁盘上读出的一个数据存到缓冲器B中，供进程W1打印输出；进程R2每次从键盘上读一个数据存放到缓冲器B，供W2打印输出。当一个进程把数据存放到缓冲器后，在该数据还没有打印输出之前不准任何进程再想缓冲器中存数据。当一个进程已把缓冲器中的数据打印输出后，在缓冲器中还没有存如新数据之前不准任何进程再从缓冲器中取数打印。问怎样用PV操作使这4个进程并发执行时能相互协作地工作？进程管理进程管理R1R2W1W2进程管理进程管理【解答】4个进程互斥，R1，W1同步，R2，W2同步mutex：表示能否把数据存如缓冲器，初始化时缓冲器为空，故初值为1S1：进程R1是否已向缓冲器存入一个数据，初值为0S2：进程R2是否已向缓冲器存入一个数据，初值为0进程管理进程管理beginmutex,s1,s2:semaphore;s:=1;s2:=0;s2:=0;cobeginprocessR1beginL1:从磁盘上读数据送x1;P(mutex);B:=x1;V(s1);gotoL1end;processW1beginL3:P(s1);y:=B;V(mutex);打印ygotoL3end;进程管理进程管理processR2beginL2:从键盘上读数据送x2;P(mutex);B:=x2;V(s2);gotoL2end;processW2beginL4:P(s2);z:=B;V(mutex);打印z;gotoL4end;进程管理进程管理【例】假定有3个进程R，W1，W2共享一个缓冲器，而B中每次只能存放一个数，当缓冲器中无数时，进程R可将M输入设备上读入的数存放到缓存器B中，若存放到缓存器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将取出打印。同时规定：进程R必须等缓冲器中的数被取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器中的数只能打印一次；W1和W2都不能从空的缓冲器中取数。写出这3个并发进程能正确工作的程序。进程管理进程管理【分析】把进程R看作是生产者，把进程W1和W2看作是消费者。现在有一个生产者（进程R)能生产不同的产品（读入奇数或偶数），把生产的产品存放在缓冲器B中，供不同的消费者（进程W1和进程W2）取用。可以看出，当进程R读入的是整数，则要把有奇数的消息发送给进程W1；当进程R读入的是偶数，则要把有偶数的消息发送给W2，在进程W1或进程W2从缓冲器中取出数后，应把缓冲器中又可有一个数的消息告诉进程R，于是，可以定义如下3个信号量：S表示是否可以把数存入缓冲器，由于缓冲器中每次只能放一个数，所以其初值取为”1“SO：表示缓冲器中是否有奇数，初值为”0“，表示无奇数SE：表示缓冲器是否偶数，初值为0，表示无偶数进程管理进程管理【解答】integerB;semaphoreS,SO,SESO=0;SE=0:integerxL1:从输入设备读入一个数X=读入的数P(S);B=Xif(B=偶数）V(SO)elseV(SE)gotoL1进程管理进程管理进程管理进程管理【例】设有一个具有N个信息元素的环形缓冲区，A进程顺序地把信息写入缓冲区，B进程依次从缓冲区读出信息。回答下列问题：1叙述A，B两进程的相互制约关系2判别下列用PV操作表示的同步算法是否正确？如不正确，试说明理由，并修改成正确的算法。设置信号量初值:S10，S2N;设置变量初值：in=out=0;进程管理进程管理【例】进程P1使用缓冲区buffer向进程P2,P3,P4发送消息，要求每当P1向buffer中发消息时，只有当P2,P3,P4进程都读取这条消息后才可再向buffer中发送消息。利用PV原语描述进程的动作序列P1bufferP2P3P4进程管理进程管理【解答】设置信号量初值S1=S2=S3=0,S=3进程P1进程P2进程P3进程P4P(S)P(S1)P(S2)P(S3)P(S)读消息读消息读消息P(S)V(S)V(S)V(S)发送消息到BufferV(S1)V(S2)V(S3)进程管理进程管理【例】设A，B为两个并发进程，它们共享一个临界区，其执行临界区的算法框图如下。试判断该算法是否有错？请说明理由。如果有错，请改正。S1，S2的初值为0，CSA,CSB为临界区。CSAV(S1)P(S2)A进程P(S1)CSBV(S2)B进程进程管理进程管理【分析】系统启动时，S1,S2为0，则B执行P(S1)被阻塞，而A进程可直接访问临界资源。故A，B两个并发进程不可能同时操作临界资源，该算法是可以保证互斥的。按题目要求，两个进程对临界资源的操作是没有先后顺序的，但是，在上面的实现中，只有A进程先操作完资源后，B资源才能操作。进程管理进程管理【解答】该算法错误若A进程用不要求访问临界资源，则不会折行V(S1),意味着B进程的申请永远得不到操作临界资源的机会；同理，若B不要求访问临界资源，则不会执行V(S2),意味着进程A下次也得不到操作临界资源的机会。所以，问题在于本应该互斥控制而使用的却是同步控制。实现改正：进程管理进程管理信号量mutex=1A进程B进程repeatrepeatP(mutex);P(mutex);CSA;CSB;V(mutex);V(mutex);进程管理进程管理【例】当进程X和进程Y共享某个资源r,进程并发执行时的程序如下：semaphore=1ProcessXProcessYL1:P(S)L2:P(S)使用资源r使用资源rV(S)V(S)gotoL1gotoL2进程管理进程管理请回答：1两个进程并发执行时，能否保证互斥使用资源？为什么？2若要使两个进程交替使用资源，仍使用PV操作来进行管理，写出应定义的信号量机器初值3修改上述程序，使两个进程能交替使用资源r进程管理进程管理【解答】1能保证互斥使用资源。因为在两个进程中，“使用资源r”都是作为临界区，由P(S)和V(S)操作保证互斥执行，S的初值定义为1，符合要求。2要使两个进程交替使用资源，仅仅保证互斥使用是不够的，必须要两个进程相互等待互相通知。为此，必须定义新的信号量。定义两个私有信号量S1和S2。假定进程X先使用资源，那么进程X的私有信号量S1的初值定义为1，进程Y的私有信号量S2的初值为0.轮流使用可以保证互斥，因此信号量S可以不要。进程管理进程管理3两个进程可以改为semaphoreS1=1semaphoreS2=0ProcessXProcessYL1:P(s1)L2:P(S2)使用资源r使用资源rV(S2)V(S1)gotoL1gotoL2进程管理进程管理【例】桌上有一空盘，只允许存放一个水果。爸爸可向盘中放苹果，也可向盘中放橘子。儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘中空时一次只能放一只水果供吃者取用，请用PV原语实现爸爸，儿子，女儿三个并发进程的同步进程管理进程管理【解答】信号量mutex:盘子是否为空信号量So:盘中是否有橘子信号量Sa:盘中是否有苹果Sempahoremutex=1,So=0,Sa=0进程管理进程管理fatherP(mutex);将水果放入盘中if(放入的是橘子)V(So)elseV(Sa)儿子 P(So);从盘中取橘子 V(mutex)吃橘子女儿 P(Sa);从盘中取苹果 V(mutex)吃苹果进程管理进程管理读者写者介绍读者写者介绍读者写者（readerwriter)，共享文件要求：1允许多个读者同时对文件执行读操作2只允许一个写者对文件执行写操作3任何写者在完成写操作前不允许其他读者或写者工作4写者在执行写操作前，应让已有的写者和读者全部退出进程管理进程管理单纯使用信号量不能解决问题，引入计数器readcount对读进程计算，mutex是用于对计数器readcount操作的互斥信号量，writeblock表示是否允许写的信号量进程管理进程管理intreadcount=0semaphorewriteblock,mutex;writeblock=1;mutex=1进程管理进程管理读者iP(mutex)readcount+if(readcount=1)P(writeblock)V(mutex)读文件P(mutex);readcountif(readcount=0)V(writeblock)V(mutex)写者j P(writeblock)写文件 V(writeblock)进程管理进程管理进程同步习题进程同步习题1.1.一条小河上有一座独木桥，规定每次只允许一一条小河上有一座独木桥，规定每次只允许一人过桥。如果把每个过桥这看作一个进程，为人过桥。如果把每个过桥这看作一个进程，为保证安全，请用信号量操作实现正确管理。保证安全，请用信号量操作实现正确管理。进程管理进程管理进程同步习题进程同步习题begins:semaphore;s：=1;cobeginbeginwait(s);过桥；signal(s)；endCoendend进程管理进程管理v桌子上有一只盘子，最多可容纳两个水果，每次桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹只能放入或取出一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，两个儿子专等吃盘果，妈妈专向盘子中放橘子，两个儿子专等吃盘子中的橘子，两个女儿专等吃盘子中的苹果。请子中的橘子，两个女儿专等吃盘子中的苹果。请用信号量操作来实现爸爸、妈妈、儿子、女儿之用信号量操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。间的同步与互斥关系。进程管理进程管理ParbeginFather:begin L1:p(empty);p(mutex);放苹果；v(mutex);v(apple);goto l1;end;Mather:begin L2:p(empty)；p(mutex);放橘子；v(mutex);v(orange);goto l2;end;Daughter:begin L3:p(apple);p(mutex);取苹果；v(mutex);v(empty);goto l3;end;进程管理进程管理L4:p(orange);p(mutex);取橘子；v(mutex);v(empty);Goto l4;end;进程管理进程管理桌上有一个空的水果盘，盘中一次只能放一个桌上有一个空的水果盘，盘中一次只能放一个水果，服务员、男顾客和女顾客共用这个盘子。水果，服务员、男顾客和女顾客共用这个盘子。服务员向盘中放草莓和香蕉，男顾客专等吃盘服务员向盘中放草莓和香蕉，男顾客专等吃盘中的草莓，女顾客专等吃盘中的香蕉。规定每中的草莓，女顾客专等吃盘中的香蕉。规定每次当盘子空时只能放一个水果供顾客食用。请次当盘子空时只能放一个水果供顾客食用。请用信号量机制实现服务员、男顾客和女顾客三用信号量机制实现服务员、男顾客和女顾客三个进程的同步。个进程的同步。进程管理进程管理题解：盘子是三个人的公有信号量，设为题解：盘子是三个人的公有信号量，设为mutex,mutex,初值为初值为1 1，服务员的私有信号量设为，服务员的私有信号量设为emptyempty初值为初值为1 1，男顾客的私有，男顾客的私有信号量为信号量为baba，初值为，初值为0 0，女顾客的私有信号量为，女顾客的私有信号量为cmcm，初值，初值为为0 0。waiter:begin L1:p(empty);p(mutex);放香蕉或草莓；v(mutex);如果放香蕉 则v(ba);否则v(cm);goto L1;end;Woman:begin L3:p(cm);p(mutex);取草莓；v(mutex);v(empty);goto L2;end；Man:begin L2:p(ba);p(mutex);取香蕉；v(mutex);v(empty);goto L2;end;进程管理进程管理汽车司机与售票员之间必须协同工作，一方面只有售汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车。另一方面，只有当汽车已经停车门应通知司机开车。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应通知售下，售票员才能开门上下客，故司机停车后应通知售票员，汽车当前正在始发站停车上客，试设必要的信票员，汽车当前正在始发站停车上客，试设必要的信号灯及赋初值，写出他们的同步过程。号灯及赋初值，写出他们的同步过程。进程管理进程管理解答：可以用两个信号量解答：可以用两个信号量s1s1、s2s2，分别表示可以开，分别表示可以开门和可以开车，其初始值都为门和可以开车，其初始值都为0 0，用，用PVPV操作实现为：操作实现为：司机：司机：售票员：售票员：L0:L0:正常行车正常行车 L1:L1:售票售票 到站停车到站停车 P(S1)P(S1)V(S1)V(S1)开车门开车门 P(S2)P(S2)关车门关车门 启动开车启动开车 V(S2)V(S2)goto L0 goto L1 goto L0 goto L1 进程管理进程管理和尚挑水问题：寺庙里有多个小、老和尚，一水缸。和尚挑水问题：寺庙里有多个小、老和尚，一水缸。小和尚取水，老和尚饮水。水缸容积小和尚取水，老和尚饮水。水缸容积1010桶水，水取自桶水，水取自同一水井，水井每次只容一个桶取水，桶总数同一水井，水井每次只容一个桶取水，桶总数3 3个，每个，每次入、取水缸水仅为一桶。试用次入、取水缸水仅为一桶。试用P P、V V操作描述和尚取操作描述和尚取水、饮水的互斥与同步过程。水、饮水的互斥与同步过程。mumutex1=mutex2=1;tex1=mutex2=1;分别代表水井和水缸分别代表水井和水缸empty=10;empty=10;水缸的入水量水缸的入水量full=0;full=0;水缸的取水量水缸的取水量count=3;count=3;水桶个数水桶个数进程管理进程管理打水：打水：begin p(empty)p(count)p(mutex1)从水井打水；从水井打水；v(mutex1)p(mutex2)往缸中放水往缸中放水 v(mutex2)v(full)v(count)end取水：取水：begin p(full)p(count)p(mutex2)从水缸取水从水缸取水 v(mutex2)v(count)v(empty)end进程管理进程管理哲学家进餐问题哲学家进餐问题设有5个哲学家，共享一张放有五把椅子的桌子，每人分得一把椅子。但是，桌子上总共只有5支筷子，在每人两边分开各放一支。哲学家们在肚子饥饿时才试图分两次从两边拾起筷子就餐。条件：(1)只有拿到两支筷子时，哲学家才能吃饭。(2)如果筷子已在他人手上，则该哲学家必须等待到他人吃完之后才能拿到筷子。(3)任一哲学家在自己未拿到两支筷子吃饭之前，决不放下自己手中的筷子。试:进程管理进程管理(1)描述一个保证不会出现两个邻座同时要求吃饭的通信算法。(2)描述一个既没有两邻座同时吃饭，又没有人饿死（永远拿不到筷子）的算法。(3)在什么情况下，5个哲学家全部吃不上饭？进程管理进程管理1.begin 2.begin 3.begin 4.begin 5.beginP(s1)；p(s2)；p(s3)；p(s4)；p(s5)；P(s2)；p(s3)；p(s4)；p(s5)；p(s1)；吃饭；吃饭；吃饭；吃饭；吃饭；V(s1)；v(s2)；v(s3)；v(s4)；v(s1)；V(s2)；v(s3)；v(s4)；v(s5)；v(s5)；End end end end end进程管理进程管理Pi:Repeat Think for while p(mutex);p(si);p(s(i+1)mod5);v(mutex);eat for while;v(si)v(s(i+1)mod 5);until false进程管理进程管理利用AND型信号量机制实现:semaphorechopstick5=1，1，1，1，1;while(true)think();Swait(chopstick(I+1)%5,chopstickI);eat();Ssignal(chopstick(I+1)%5,chopstickI);进程管理进程管理限制人数semaphorechopstick5=1，1，1，1，1;semaphoremutex=4;Repeatthink();wait(mutex);/请求进餐wait(chopsticki);/请求左手边的筷子wait(chopstick(i+1)%5);/请求右手边的筷子eat();signal(chopstick(i+1)%5);/释放右手边的筷子signal(chopsticki);/释放左手边的筷子signal(mutex);/释放信号量mutexuntilfalse进程管理进程管理原理：规定奇数号的哲学家先拿起他左边的筷子原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去然后再去拿他右边的筷子拿他右边的筷子;而偶数号的哲学家则相反而偶数号的哲学家则相反.按此规定按此规定,将是将是1,21,2号哲学家竞争号哲学家竞争1 1号筷子号筷子,3,4,3,4号哲学家竞争号哲学家竞争3 3号筷子号筷子.即五个即五个哲学家都竞争奇数号筷子哲学家都竞争奇数号筷子,获得后获得后,再去竞争偶数号筷子再去竞争偶数号筷子,最最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根哲学家进入阻塞等待队列，根FIFOFIFO原则，则先申请的哲学家原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。会较先可以吃饭，因此不会出现饿死的哲学家。进程管理进程管理semaphore chopstick5=1，1，1，1，1;void philosopher(int i)while(true)think();if(i%2=0)/偶数哲学家，先右后左。偶数哲学家，先右后左。wait(chopstick i+1 mod 5);wait(chopstick i);eat();signal(chopstick i+1 mod 5);signal(chopstick i);Else/奇数哲学家，先左后右。奇数哲学家，先左后右。wait(chopstick i);wait(chopstick i+1 mod 5);eat();signal(chopstick i);signal(chopstick i+1 mod 5);进程管理进程管理（经典理发师问题）（经典理发师问题）（经典理发师问题）（经典理发师问题）v假设后街有家理发店，店里有一个理发师、一把理发假设后街有家理发店，店里有一个理发师、一把理发椅和椅和n把等候理发的顾客椅子。把等候理发的顾客椅子。（1）.如果没有顾客则理发师便在理发椅上看报纸；如果没有顾客则理发师便在理发椅上看报纸；（2）.当有一个顾客到达时，首先查看理发师在干什当有一个顾客到达时，首先查看理发师在干什么，如果在看报纸则告诉理发师理发，然后坐到理发么，如果在看报纸则告诉理发师理发，然后坐到理发椅上开始理发；如果理发师正在理发，则查看是否有椅上开始理发；如果理发师正在理发，则查看是否有空的椅子可坐，如果有，他就坐下等待，如果没有，空的椅子可坐，如果有，他就坐下等待，如果没有，则离开；则离开；（3）.理发师为一位顾客理完发后，查看是否有人等理发师为一位顾客理完发后，查看是否有人等待，如有则唤醒一位为其理发，如没有则在理发椅上待，如有则唤醒一位为其理发，如没有则在理发椅上看报纸；看报纸；（4）.顾客不分优先级顾客不分优先级进程管理进程管理v有一间酒吧里有3个音乐爱好者队列，第一队的音乐爱好者只有随身听，第二队的音乐爱好者只有音乐磁带，第三队的音乐爱好者只有电池。然而，要听音乐就必须随身听、音乐磁带和电池三种物品俱全。酒吧老板一次出售这三种物品中的任意两种。当一名音乐爱好者得到这三种物品并听完一首乐曲后，酒吧老板才能再一次出售这三种物品中的任意两种，于是第2名音乐爱好者得到这三种物品，并开始听乐曲。全部买卖就这样进行下去。试用信号量实现它们之间的同步关系。进程管理进程管理进程同步算法习题课进程管理进程管理【例题例题1 1】司机进程：司机进程：while(1)while(1)启动车辆启动车辆正常驾驶正常驾驶到站停车到站停车 售票员进程：售票员进程：while(1)while(1)关门关门售票售票开门开门 用用waitwait、signalsignal操作解决司机与售票员的问题操作解决司机与售票员的问题进程管理进程管理分析：分析：为保证车辆行驶安全，售票员必须关好车门，然后通知司机启动车辆，在行驶过程中售票员不能打开车门，待车到站停稳后，司机通知售票员才能打开车门，如此不断重复。为此，须设置两个信号量S1，S2用来控制司机和售票员的行为，初值都为0。进程管理进程管理解解解解:算法如下：算法如下：算法如下：算法如下：司机进程：司机进程：while(1)wait(S1)启动车辆启动车辆正常驾驶正常驾驶 到站停车到站停车 signal(S2)售票员进程：售票员进程：while(1)关门关门 signal(S1)售票售票 wait(S2)开门开门进程管理进程管理【例题例题2 2】1.用wait、signal操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑getcopyputst进程管理进程管理解解:设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0；get：while（1）wait(Sin）;将数放入将数放入S;signal(Sout);copy：while（1）wait(Sout）;wait(Tin）;将数从将数从S取出放入取出放入T;signal(Tout);signal(Sin);put：while（1）wait(Tout）;将数从将数从T取走取走;signal(Tin);进程管理进程管理思考题：如果S和T是由多个缓冲区组成的缓冲池，上述算法将如何修改？进程管理进程管理【例题例题3 3】桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用wait、signal操作实现爸爸、儿子、女儿三个并发进程的同步。进程管理进程管理分析：分析：设置一个信号量S表示空盘子数，一个信号量So表示盘中桔子数，一个信号量Sa表示盘中苹果数，初值分别为1，0，0。进程管理进程管理解解:算法如下：算法如下：算法如下：算法如下：Father()while(1)wait(S);将水果放入盘中;if(是桔子)signal(So);elsesignal(Sa);Son()while(1)wait(So)取桔子signal(S);吃桔子;Daughter()while(1)wait(Sa)取苹果signal(S);吃苹果;进程管理进程管理【例题例题4 4】有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）（2）NA产品数量B产品数量M。其中，N和M是正整数。试用wait、signal操作描述产品A与B的入库过程。进程管理进程管理解解:分析：分析：设两个同步信号量Sa、Sb，其中：Sa表示允许A产品比B产品多入库的数量，初值为M-1。Sb表示允许B产品比A产品多入库的数量，初值为N-1。设互斥信号量mutex，初值为1。进程管理进程管理 B产品入库进程：产品入库进程：j=0;while(1)wait(Sb);wait(mutex);B产品入库产品入库 signal(mutex);signal(Sa);消费产品消费产品;A产品入库进程：产品入库进程：i=0;while(1)生产产品生产产品;wait(Sa);wait(mutex);A产品入库产品入库 signal(mutex);signal(Sb);算法如下：算法如下：进程管理进程管理例题例题5 进程A1、A2，An1通过m个缓冲区向进程B1、B2、Bn2不断发送消息。发送和接收工作遵循下列规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度。（2）对每个消息，B1，B2，Bn2都须各接收一次，读入各自的数据区内。（3）m个缓冲区都满时，发送进程等待，没有可读消息时，接收进程等待。试用wait、signal操作组织正确的发送和接收工作。进程管理进程管理分分析析：每个缓冲区只要写一次但要读n2次，因此，可以看成n2组缓冲区，每个发送者要同时写n2个缓冲区，而每个接收者只要读它自己的缓冲区。Sinn2=m；表示每个读进程开始有m个空缓冲区。Soutn2=0；表示每个读进程开始有0个可接收的消息。进程管理进程管理解：解：先将问题简化：v设缓冲区的大小为1v有一个发送进程A1v有二个接收进程B1、B2v设有信号量Sin1、Sin2初值为1v设有信号量Sout1、Sout2初值为0进程管理进程管理Bi：while(1)wait(Souti);从缓冲区取数从缓冲区取数 signal(Sini);A1:while(1)wait(Sin1);wait(Sin2);将数据放入缓冲区signal(Sout1);signal(Sout2);进程管理进程管理向目标前进一步向目标前进一步:v设缓冲区的大小为mv有一个发送进程A1v有二个接收进程B1、B2v设有信号量Sin1、Sin2初值为mv设有信号量Sout1、Sout2初值为0进程管理进程管理Bi：while(1)wait(Souti);wait(mutex);从缓冲区取数从缓冲区取数 signal(mutex);signal(Sini);A1:while(1)wait(Sin1);wait(Sin2);wait(mutex);将数据放入缓冲区signal(mutex);signal(Sout1);signal(Sout2);进程管理进程管理到达目标到达目标v设缓冲区的大小为mv有n1个发送进程A1.An1v有n2个接收进程B1Bn2v设有n2个信号量Sinn2初值均为mv设有n2个信号量Soutn2初值均为0进程管理进程管理Bi：while(1)wait(Souti);wait(mutex);从缓冲区取数从缓冲区取数 signal(mutex);signal(Sini);Aj:while(1)for(i=1;i=n2;i+)wait(Sini);wait(mutex);将数据放入缓冲区signal(mutex);for(i=1;i=n2;i+)signal(Sout2);进程管理进程管理进程同步算法补充作业：进程同步算法补充作业：1.设有两个优先级相同的进程p1与p2，令信号量s1、s2的初值为0，已知z=2，试问p1、p2并发运行后x=?,y=?,z=?进程p1：y=1;进程p2：x=1;y=y+2;x=x+1;signal(s1);wait(s1);z=y+1;x=x+y;wait(s2);signal(s2);y=z+y;z=z+x;2请按下列方法分别写出非死锁的哲学家进餐算法：（1）最多允许4个哲学家同时进餐。（2）奇数号哲学家先拿其左边的筷子，然后再那其右边的筷子；而偶数号哲学家先拿其右边的筷子，然后再那其左边的筷子。进程管理进程管理3.有桥如下图所示，车流方向如箭头所示。假设桥上不允许两车交会，但允许同方向多辆车依次通过（即桥上可有多个相同方向行驶的车辆），试用wait和signal操作实现桥上的交通管理。4某银行人民币储蓄业务由若干个柜员负责。每个顾客进入银行后先取一个号，并且等着叫号，当一个柜员空闲下来时，就叫下一个号，持该号的顾客被服务。试用wait、signal操作正确编写柜台人员进程和顾客进程的同步算法。