(1.25)--第2章2操作系统原理.ppt

1经典经典IPC问题问题 Inter-Process-Communication生产者消费者问题生产者消费者问题有界缓冲区问题有界缓冲区问题 哲学家进餐问题哲学家进餐问题多进程同步问题多进程同步问题读者写者问题读者写者问题数据库互斥访问问题数据库互斥访问问题2经典问题：生产者经典问题：生产者-消费者问题消费者问题 生产者与消费者问题生产者与消费者问题 DijkstraDijkstra把广义同步问题抽象成一种把广义同步问题抽象成一种“生产者与消费者问生产者与消费者问题题”（The producer-consumer-The producer-consumer-problemproblem）的抽象模型）的抽象模型.事实上事实上,计算机系统中的许多问题都可计算机系统中的许多问题都可归结为生产者与消费者问题归结为生产者与消费者问题.(1)(1)计算进程和打印进程计算进程和打印进程 计算进程不断产生数据计算进程不断产生数据,是生产者；是生产者；打印进程不断打印数据打印进程不断打印数据,是消费者。是消费者。(2)(2)通信问题通信问题 发消息进程发消息进程 sendsend不断产生消息，是生产者；不断产生消息，是生产者；收消息进程收消息进程 receivereceive不断接收消息，是消费者不断接收消息，是消费者.3经典问题：生产者经典问题：生产者-消费者问题消费者问题同步问题：同步问题：生产者进程不能往满的缓冲区中放东西生产者进程不能往满的缓冲区中放东西消费者进程不能从空的缓冲区中取东西消费者进程不能从空的缓冲区中取东西4经典问题：生产者经典问题：生产者-消费者问题消费者问题情况情况1:1:一个一个bufferbuffer，一个生产者，一个消费者，生产者只生产一，一个生产者，一个消费者，生产者只生产一个东西，消费者只进行一次消费，即：生产者只进行一次个东西，消费者只进行一次消费，即：生产者只进行一次putdataputdata操作，消费者只进行一次操作，消费者只进行一次getdatagetdata操作。操作。情况情况2:2:一个一个bufferbuffer，一个生产者，一个消费者，生产者不断地进，一个生产者，一个消费者，生产者不断地进行行putdataputdata操作，消费者不断地进行操作，消费者不断地进行getdatagetdata操作，即：生操作，即：生产者不断地生产，消费者不断地消费产者不断地生产，消费者不断地消费情况情况3:3:一个一个bufferbuffer，多个生产者，多个消费者，多个生产者和消，多个生产者，多个消费者，多个生产者和消费者都在不断地存取费者都在不断地存取bufferbuffer，即生产者不断地进行，即生产者不断地进行putdatputdata a操作，消费者不断地进行操作，消费者不断地进行getdatagetdata操作。操作。情况情况4:4:多个生产者，多个消费者，多个生产者，多个消费者，n n个个bufferbuffer，多次循环存取，多次循环存取bufbufferfer，即，即多个生产者不断地进行，即，即多个生产者不断地进行putdataputdata操作，多个消操作，多个消费者不断地进行费者不断地进行getdatagetdata操作。操作。5（情况（情况1）P、V操作实现操作实现semaphore full=0;producer:putdata；V(full);customer:P(full);getdata;经典问题：生产者经典问题：生产者-消费者问题消费者问题6经典问题：生产者经典问题：生产者-消费者问题消费者问题情况情况2:2:一个一个bufferbuffer，一个生产者，一个消费者，生产者，一个生产者，一个消费者，生产者不断地进行不断地进行putdataputdata操作，消费者不断地进行操作，消费者不断地进行getdgetdataata操作，即：生产者不断地生产，消费者不断地操作，即：生产者不断地生产，消费者不断地消费消费7(情况情况2)P、V操作实现操作实现 semaphore full=0，empty=1;producer：while(1)P(empty)；putdata；V(full);consumer：while(1)P(full)；getdata；V(empty)；经典问题：生产者经典问题：生产者-消费者问题消费者问题8经典问题：生产者经典问题：生产者-消费者问题消费者问题情况情况3:3:一个一个bufferbuffer，多个生产者，多个消费者，多个生，多个生产者，多个消费者，多个生产者和消费者都在不断地存取产者和消费者都在不断地存取bufferbuffer，即生产者，即生产者不断地进行不断地进行putdataputdata操作，消费者不断地进行操作，消费者不断地进行getdgetdataata操作。操作。9(情况情况3)P、V操作实现操作实现 semaphore full=0,empty=1,mutex=1;producer：while(1)P(empty)；P(mutex)；putdata；v(mutex)；V(full);consumer：while(1)P(full)；P(mutex)；getdata；v(mutex)；V(empty)；经典问题：生产者经典问题：生产者-消费者问题消费者问题信号量信号量mutex可以省略吗？可以省略吗？10经典问题：生产者经典问题：生产者-消费者问题消费者问题情况情况4:多个生产者，多个消费者，多个生产者，多个消费者，n个个buffer，多次循环，多次循环存取存取buffer，即，即多个生产者不断地进行，即，即多个生产者不断地进行putdata操作，多个消费者不断地进行操作，多个消费者不断地进行getdata操作。操作。生产者进程生产者进程消费者进程消费者进程11经典问题：生产者经典问题：生产者-消费者问题消费者问题(1)操作规则操作规则 假设缓冲池中有假设缓冲池中有n n个缓冲区，每个缓冲区存放一个个缓冲区，每个缓冲区存放一个消息消息（一个数据）；（一个数据）；又假定又假定这些生产者和消费者互相等效，只要缓冲这些生产者和消费者互相等效，只要缓冲池池未满未满，生产者可将消息送入缓冲池；只要缓冲，生产者可将消息送入缓冲池；只要缓冲池池未空未空，消费者可从缓冲池取走一个消息。，消费者可从缓冲池取走一个消息。这时这时BufferPoolBufferPool变成了临界资源变成了临界资源，不允许多个进，不允许多个进程同时对其操作。程同时对其操作。(任意时刻，只允许任意时刻，只允许1 1个生产者或个生产者或1 1个消费者进入的个消费者进入的算法算法)12(2)操作流程操作流程 repeat 判断缓冲池是否有空缓冲判断缓冲池是否有空缓冲区，没有则等待；区，没有则等待；是否可操作缓冲池；是否可操作缓冲池；putdata；设置缓冲池可操作标志；设置缓冲池可操作标志；增加满缓冲区的数量；增加满缓冲区的数量；until false repeat 判断缓冲池是否有满缓冲判断缓冲池是否有满缓冲区，没有则等待；区，没有则等待；是否可操作缓冲池；是否可操作缓冲池；getdata；设置缓冲池可操作标志；设置缓冲池可操作标志；增加空缓冲区的数量；增加空缓冲区的数量；until false 经典问题：生产者经典问题：生产者-消费者问题消费者问题13经典问题：生产者经典问题：生产者-消费者问题消费者问题（3）信号量）信号量 可可利利用用互互斥斥信信号号量量mutex使使诸诸进进程程对对缓缓冲冲池池实实现现互互斥斥访访问问；利利用用empty和和full计数信号量分别表示空缓冲及满缓冲的数量。计数信号量分别表示空缓冲及满缓冲的数量。互斥信号量互斥信号量 mutex：防止多个进程同时进入临界区：防止多个进程同时进入临界区，初值为，初值为1.同步信号量同步信号量 empty和和full：保证事件发生的顺序：保证事件发生的顺序，初值分别为，初值分别为n和和0.full=n，缓冲区缓冲区都都满时，满时，Producer停止运行停止运行 empty=n，缓冲区缓冲区都都空时，空时，Consumer停止运行停止运行14(4)P、V操作实现操作实现 semaphore full=0,empty=n,mutex=1;producer：while(1)P(empty)；P(mutex)；putdata；v(mutex)；V(full);consumer：while(1)P(full)；P(mutex)；getdata；v(mutex)；V(empty)；经典问题：生产者经典问题：生产者-消费者问题消费者问题15(4)P、V操作实现操作实现 semaphore full=0,empty=n,mutex=1;producer：while(1)P(empty)；P(mutex)；putdata；v(mutex)；V(full);consumer：while(1)P(full)；P(mutex)；getdata；v(mutex)；V(empty)；经典问题：生产者经典问题：生产者-消费者问题消费者问题16semaphore full=0,empty=n,mutex=1;int in=out=0；producerproducer：while(1)while(1)produce an item in nextp;produce an item in nextp;P(empty)P(empty)；P(mutex)P(mutex)；buffer(in)=nextp;buffer(in)=nextp;in=(in+1)mod n;in=(in+1)mod n;v(mutex)v(mutex)；V(full);V(full);consumerconsumer：while(1)while(1)P(full)P(full)；P(mutex)P(mutex)；nextc=buffer(out);nextc=buffer(out);out=(out+1)mod n;out=(out+1)mod n;v(mutex)v(mutex)；V(empty)V(empty)；consumconsum the item in nextc;the item in nextc;生产者生产者-消费者问题消费者问题P61的的P，V操作实现操作实现17P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)mod n;Signal(mutex);signal(full);empty=nfull=0mutex=1in,out=0临界区。临界区。生产者在生产时，防止生产者在生产时，防止其他其他进程同时进入临界进程同时进入临界区区生产者生产者-消费者问题消费者问题18P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)mod n;Signal(mutex);signal(full);empty=nfull=0mutex=1in,out=0控制：控制：缓冲区满时不能继续缓冲区满时不能继续生产，制约生产者进生产，制约生产者进程程P。生产者生产者-消费者问题消费者问题19C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)mod n;Signal(mutex);signal(empty);empty=nfull=0mutex=1in,out=0临界区。临界区。消费者消费者在在消费消费时，防止时，防止其他其他进程同时进入临界进程同时进入临界区区生产者生产者-消费者问题消费者问题20C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)mod n;Signal(mutex);signal(empty);empty=nfull=0mutex=1in,out=0控制：控制：缓冲区空时不能继续缓冲区空时不能继续消费，制约消费者进消费，制约消费者进程程C。生产者生产者-消费者问题消费者问题21说明说明waitwait和和signalsignal操作成对出现；操作成对出现；对对资源信号量资源信号量的的waitwait操作在前操作在前对对互斥信号量互斥信号量的的waitwait操作在后操作在后P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)mod n;Signal(mutex);signal(full);C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)mod n;Signal(mutex);signal(empty);生产者生产者-消费者问题消费者问题思考：思考：互换两个互换两个P P操作会操作会产生什么结果？产生什么结果？互换两个互换两个V V操作对操作对结果有影响么？结果有影响么？互换两个互换两个p(wait)p(wait)操作可能会导致死锁，但互换操作可能会导致死锁，但互换两个两个v(signal)v(signal)操作从逻辑上讲应该是一样的。操作从逻辑上讲应该是一样的。2223课堂练习课堂练习修改下面生产者修改下面生产者-消费者问题解法中的错误消费者问题解法中的错误 Producer:begin;repeat;produce an item in nextp;wait(mutex);wait(full);buffer(in):=nextp;signal(mutex);until false;end;consumer:begin;repeat;wait(mutex);wait(empty);nextc:=buffer(out);out:=out+1;signal(mutex);consume item in nextc;until false;end;24课堂练习答案课堂练习答案Producer:begin;repeat;produce an item in nextp;wait(mutex);wait(full);/*应为应为wait(empty),而且还应该在而且还应该在wait(mutex)的前面的前面*/buffer(in):=nextp;/*缓冲池数组游标应前移缓冲池数组游标应前移:in:=(in+1)mod n;*/signal(mutex);/*signal(full);*/until false;end;25课堂练习答案课堂练习答案consumer:begin;repeat;wait(mutex);wait(empty);/*应为应为wait(full),而且还应该在而且还应该在wait(mutex)的前面的前面*/nextc:=buffer(out);out:=out+1;/*考虑循环，应改为考虑循环，应改为:out:=(out+1)mod n;*/signal(mutex);/*signal(empty);*/consume item in nextc;until false;end;26P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)mod n;Signal(mutex);signal(full);P：Wait(empty,mutex);Buffer(in)=nextp;in:=(in+1)mod n;Signal(mutex,full);2.4.1 2.4.1 生产者生产者-消费者问题消费者问题用用AND型信号量解决同一问题型信号量解决同一问题27C：SWait(full,mutex);netxc=buffer(out);out:=(out+1)mod n;SSignal(mutex,empty);2.4.1 2.4.1 生产者生产者-消费者问题消费者问题用用AND型信号量解决同一问题型信号量解决同一问题C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)mod n;Signal(mutex);signal(empty);2829分析分析设设A、B为两个并发进程，它们共享一个临界资为两个并发进程，它们共享一个临界资源，其执行临界区的算法框图如下图所示。试判源，其执行临界区的算法框图如下图所示。试判断该算法是否有错？请说明理由。如果有错，请断该算法是否有错？请说明理由。如果有错，请改正。改正。S1、S2的初值为的初值为0,CSA、CSB为临界区。为临界区。CSAV(S1)P(S2)P(S1)CSBV(S2)A A进程程B B进程程31semaphore mutex=1;begin cobegin A进程：进程：Begin repeat P(mutex);CSA;V(mutex);until falseEndB进程：进程：Begin repeat P(mutex);CSB;V(mutex);until false;End coend end分析分析32经典问题：哲学家就餐问题经典问题：哲学家就餐问题问题描述问题描述有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子每个人只能直接从自己的左边或右边去取筷子1 10 01 12 23 34 40 02 23 34 433 假设这假设这5 5只筷子与椅子相应也按逆时针方向从只筷子与椅子相应也按逆时针方向从0 0开始连续编开始连续编号，即第号，即第i i号哲学家左边摆着第号哲学家左边摆着第i i号筷子，右边摆着第号筷子，右边摆着第(i+1(i+1)mod 5)mod 5)号筷子，这里的号筷子，这里的modmod代表模运算，即整除取余。代表模运算，即整除取余。显然，在这个问题中筷子是哲学家进餐竞争的临界资源，显然，在这个问题中筷子是哲学家进餐竞争的临界资源，5 5个筷子应分别用一个初值为个筷子应分别用一个初值为1 1的信号量表示，这的信号量表示，这5 5个信号量个信号量构成一个信号量数组构成一个信号量数组chopstick chopstick。每个哲学家只有同时获得两只筷子才能就餐。每个哲学家只有同时获得两只筷子才能就餐。semaphore chopstick0 semaphore chopstick0，4=1,1,1,1,1;4=1,1,1,1,1;2.4.2 2.4.2 哲学家就餐问题哲学家就餐问题34所有信号量均被初始化为所有信号量均被初始化为1，第，第i位哲学家的活动可描述为位哲学家的活动可描述为：repeatwait(chopsticki)；wait(chopstick(i+1)mod 5)；eat；signal(chopsticki)；signal(chopstick(i+1)mod 5)；think；until false；2.4.2 2.4.2 哲学家就餐问题哲学家就餐问题35经典问题：哲学家就餐问题经典问题：哲学家就餐问题问题描述问题描述有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子每个人只能直接从自己的左边或右边去取筷子1 10 01 12 23 34 40 02 23 34 40 04 4 4 43 32 21 1死锁死锁!36特殊情况考虑特殊情况考虑死锁：如果每个哲学家都拿起一只筷子，都饿死死锁：如果每个哲学家都拿起一只筷子，都饿死并行程度：五只筷子允许两人同时进餐并行程度：五只筷子允许两人同时进餐2.4.2 2.4.2 哲学家就餐问题哲学家就餐问题37为防止死锁发生可采取的措施：为防止死锁发生可采取的措施：最多允许最多允许4 4个哲学家同时个哲学家同时去拿左边的筷子去拿左边的筷子仅当一个哲学家左右两边的筷子都可用时，才允仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子；许他拿筷子；（ANDAND型信号量）型信号量）给所有哲学家编号，奇数号的哲学家必须首先拿给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，左边的筷子，然后再拿右边的筷子，然后再拿右边的筷子，偶数号的哲学偶数号的哲学家则反之；家则反之；2.4.2 2.4.2 哲学家就餐问题哲学家就餐问题38第一种方法思想第一种方法思想Var chopstick:array0，4 of semaphore:=(1,1,1,1,1);Var sm:semaphore:=4;begincobegin process1()process2()process5()coendProcessi:beginrepeat wait(sm);wait(chopsticki);wait(chopstick(i+1)mod 5);eat;signal(chopsticki);signal(chopstick(i+1)mod 5);signal(sm);think;until false;endend39第二种方法思想第二种方法思想Var chopsiick array0，4 of semaphore:=(1,1,1,1,1)；begincobegin process1()process2()process5()coend processirepeat Sswait(chopstick(i+1)mod 5，chopsticki)；eat；Ssignal(chopstick(i+1)mod 5，chopsticki)；think；until false；end 40第三种方法思想第三种方法思想Var chopstick:array0，4 of semaphore:=(1,1,1,1,1);Var sm:semaphore:=4;begincobegin process1()process2()process5()coend41经典问题：哲学家就餐问题经典问题：哲学家就餐问题问题描述问题描述有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子每个人只能直接从自己的左边或右边去取筷子1 10 01 12 23 34 40 02 23 34 41 13 30 01 13 342第三种方法思想第三种方法思想Processi:beginrepeat if i mod 2=1 wait(chopsticki);wait(chopstick(i+1)mod 5);eat;signal(chopstick(i+1)mod 5);signal(chopsticki);Elsewait(chopstick(i+1)mod 5);wait(chopsticki);eat;signal(chopsticki);signal(chopstick(i+1)mod 5);think;until false；endend43经典问题：读者经典问题：读者-写者问题写者问题问题描述问题描述写者向数据区放数据，读者从数据区获取数据写者向数据区放数据，读者从数据区获取数据多个读者可同时读取数据多个读者可同时读取数据多个写者不能同时写数据多个写者不能同时写数据44读者读者-写者问题写者问题有两组并发进程有两组并发进程:读者和写者读者和写者,共享一组数据区共享一组数据区要求：要求：允许多个读者同时执行读操作允许多个读者同时执行读操作不允许读者、写者同时操作不允许读者、写者同时操作不允许多个写者同时操作不允许多个写者同时操作45信号量描述信号量描述互斥关系分析互斥关系分析读者和写者读者和写者不能不能同时进入共享数据区同时进入共享数据区多个写者多个写者不能不能同时进入共享数据区同时进入共享数据区多个读者可以同时进入共享数据区多个读者可以同时进入共享数据区同步关系分析同步关系分析读者进入缓冲区，写者必须等待读者进入缓冲区，写者必须等待写者进入缓冲区，读者必须等待写者进入缓冲区，读者必须等待读者读者优先优先：一旦有读者进入，则后续读者均可进入：一旦有读者进入，则后续读者均可进入写者写者优先优先：只要有写者等待，则后续读者必须等待：只要有写者等待，则后续读者必须等待46信号量描述信号量描述如果读者来：如果读者来：1 1）无读者、写者，新读者可以读）无读者、写者，新读者可以读2 2）有写者等，但有其它读者正在读，则新读者也）有写者等，但有其它读者正在读，则新读者也可以读可以读3 3）有写者写，新读者等）有写者写，新读者等如果写者来：如果写者来：1 1）无读者，新写者可以写）无读者，新写者可以写2 2）有读者，新写者等待）有读者，新写者等待3 3）有其它写者，新写者等待）有其它写者，新写者等待47两个进程：两个进程：ReaderReader、WriterWriter控制控制读读/写写，写，写/写写互斥互斥的的信号量：信号量：WmutexWmutex1 1多个读者间的互斥信号量：多个读者间的互斥信号量：RmutexRmutex1 1（用于读者互斥修改（用于读者互斥修改r readcounteadcount）readcount：正在读取的进程数目：正在读取的进程数目readcountreadcount0 0时允许写时允许写读者读者-写者问题写者问题48wait(rmutex);If readcount=0 then wait(wmutex);readcount:=readcount+1;signal(rmutex);执行读取操作wait(rmutex);readcount:=readcount-1if readcount=0 then signal(wmutex);signal(rmutex);读者读者-写者问题写者问题读者部分读者部分wait(wmutex);执行写操作signal(wmutex);写者部分写者部分会产生饥饿吗？谁会会产生饥饿吗？谁会饥饿？饥饿？49 设置信号量：设置信号量：允许的最大读者个数信号量允许的最大读者个数信号量L L，初值为，初值为RNRN；写者与写者、写者与第一读者互斥访问共享数据对象的信写者与写者、写者与第一读者互斥访问共享数据对象的信号量号量mxmx，初值为，初值为1 1。读者：读者：当访问共享数据对象的读者个数未超过当访问共享数据对象的读者个数未超过RNRN，并且无写者时，并且无写者时，可以进行读操作；，可以进行读操作；写者：写者：无一个写者并且无一个读者时，可以进行写操作。无一个写者并且无一个读者时，可以进行写操作。用信号量集机制解决用信号量集机制解决50Swait(L,1,1)；Swait(mx,1,0)；执行读取操作 Ssignal(L,1)；读者读者请求读操作，使请求读操作，使L的值的值减减1判断有无写者在进行判断有无写者在进行写操作写操作使允许的读者数目加使允许的读者数目加151仅当既无写者在写仅当既无写者在写(mx=1)，又无读者在读，又无读者在读(L=RN)时，写者才能进入时，写者才能进入临界区写。临界区写。Swait(mx,1,1；L,RN,0)；执行写操作 Ssignal(mx,1)；置为无写者在写置为无写者在写52作业作业1 1用用P P、V V原语实现东西向单行道上车辆的正确行驶：原语实现东西向单行道上车辆的正确行驶：当当有有车车自自东东向向西西方方向向（或或自自西西向向东东方方向向）行行驶驶，另一方向上的车辆须等待；另一方向上的车辆须等待；同一方向上的车可以连续通过；同一方向上的车可以连续通过；当当某某一一方方向向上上已已经经没没有有车车辆辆在在单单行行道道上上行行驶驶时时，另一方向上的车辆即可以进入单行道。另一方向上的车辆即可以进入单行道。请完善这个程序：请完善这个程序：(可参考读写者问题）可参考读写者问题）53作业作业1 1begin semaphore mutex，westeast，eastwest=1,int eastcount=0;int westcount=0；Cobegin east_west;west_east;Coend;54作业作业1 1Process east_west()begin _;eastcount=eastcount+1;if eastcount=1 then _;_;通过单行道；通过单行道；_;eastcount=eastcount-1;if eastcount=0 then _;V(eastwest);End;Process west_east()begin _;westcount=westcount+1;If westcount=1 then _;_;通过单行道；通过单行道；_;westcount=westcount-1;If westcount=0 then _;V(westeast);End;55作业作业1 1Process east_west()begin P（eastwest）;eastcount:=eastcount+1;if eastcount=1 then P（mutex）;V（eastwest）;通过单行道；通过单行道；P（eastwest）;eastcount=eastcount-1;if eastcount=0 then V（mutex）;V(eastwest);End;Process west_east()begin P（westeast）;westcount:=westcount+1;If westcount=1 then P（mutex）;V（westeast）;通过单行道；通过单行道；P（westeast）;westcount=westcount-1;If westcount=0 then V（mutex）;V(westeast);End;56网络工程师相关考题（网络工程师相关考题（0404下半年）下半年）进程进程PA不断地向管道写数据，进程不断地向管道写数据，进程PB从管道中读数据从管道中读数据并加工处理，如下图所示。如果采用并加工处理，如下图所示。如果采用P、V操作来实现操作来实现进程进程PA和进程和进程PB间的管道通信，并且保证这两个进程间的管道通信，并且保证这两个进程并发执行的正确性，则至少需要并发执行的正确性，则至少需要_(26)_。(26)A1个信号量，信号量的初值为个信号量，信号量的初值为0B2个信号量，信号量的初值分别为个信号量，信号量的初值分别为0、1C3个信号量，信号量的初值分别为个信号量，信号量的初值分别为0、0、1 D4个信号量，信号量的初值分别为个信号量，信号量的初值分别为0、0、1、1答案：答案：B57网络工程师相关考题（网络工程师相关考题（0303年）年）在某超市里有一个收银员，且同时最多允许有在某超市里有一个收银员，且同时最多允许有n n个顾客购物，我们可以个顾客购物，我们可以将顾客和收银员看成是两类不同的进程，且工作流程如下图所示。为了将顾客和收银员看成是两类不同的进程，且工作流程如下图所示。为了利用利用PVPV操作正确地协调这两类进程之间的工作，设置了三个信号量操作正确地协调这两类进程之间的工作，设置了三个信号量S1S1、S2S2和和SnSn，且初值分别为，且初值分别为0 0、0 0和和n n。这样图中的。这样图中的a a应填写应填写_(24)_(24)_，图中的，图中的b1b1、b2b2应分别填写应分别填写_(25)_(25)，图中的，图中的c1c1、c2c2应分别填写应分别填写_(26)_(26)_。(24)A.P(S1)BP(S2)C P(Sn)D P(Sn)、P(S1)(25)AP(Sn)、V(S2)BP(Sn)、V(S1)C P(S2)、V(S1)D V(S1)、P(S2)(26)AP(S1)、V(S2)BP(Sn)、V(S1)C P(S2)、V(S1)D V(S1)、P(S2)答案：答案：CDA58网络工程师相关考题（网络工程师相关考题（0808上半年）上半年）某火车票销售系统有某火车票销售系统有 n 个售票点，该系统为每个售票点创建一个进程个售票点，该系统为每个售票点创建一个进程。假设。假设Hi单元存放某日某车次的剩余票数，单元存放某日某车次的剩余票数，Temp 为为Pi进程的临时工作单元，进程的临时工作单元，x为某用户的订票张数。初始化为某用户的订票张数。初始化时系统应将信号量时系统应将信号量S赋值为赋值为(23)。Pi进程的工作流程如下，若用进程的工作流程如下，若用 P 操作和操作和 V 操作实现进程间的同步与互斥，则图中操作实现进程间的同步与互斥，则图中 a、b 和和 c应分别填入应分别填入(24)。59(23)A.0 B.1 C.2 D.3(24)A.P(S)、V(S)和和V(S)B.P(S)、P(S)和和V(S)C.V(S)、P(S)和和P(S)D.V(S)、V(S)和和P(S)答案：答案：BA60网络工程师相关考题（网络工程师相关考题（0404上半年）上半年）若有一个仓库，可以存放若有一个仓库，可以存放P1、P2两种产品，但是每次只能两种产品，但是每次只能存放一种产品要求：存放一种产品要求：w=P1的数量的数量-P2的数量的数量-iwk(i、k为正整数为正整数)若用若用PV操作实现操作实现P1和和P2产品的入库过程，至少需要产品的入库过程，至少需要_(23)_个同步信号量及个同步信号量及_(24)_个互斥信号量，其中，个互斥信号量，其中，同步信号量的初值分别为同步信号量的初值分别为_(25)_，互斥信号量的初值分别为，互斥信号量的初值分别为_(26)_。(23)A0B1C2 D3(24)A0B1C2 D3(25)A0Bi,k,0Ci,k Di-1,k-1(26)A1B1,1C1,1,1 Di,k 答案：答案：CBDA6162我们以生产者消费者为例，来说明学习此我们以生产者消费者为例，来说明学习此重点问题时应了解和掌握什么。重点问题时应了解和掌握什么。（1）该问题用于解决什么问题。）该问题用于解决什么问题。生产者消费者问题是用于解决生产者和消生产者消费者问题是用于解决生产者和消费者之间的进程互斥和进程同步问题。首先费者之间的进程互斥和进程同步问题。首先应了解哪些资源属于临界资源，并为它们设应了解哪些资源属于临界资源，并为它们设置了哪些信号量，信号量的初值应如何设置置了哪些信号量，信号量的初值应如何设置；其次，应了解哪些地方需要同步，并需为；其次，应了解哪些地方需要同步，并需为它们设置哪些信号量，信号量的初值又应如它们设置哪些信号量，信号量的初值又应如何设置等。何设置等。重点与难点重点与难点63（2）如何实现进程互斥）如何实现进程互斥.为实现对缓冲池的互斥访问为实现对缓冲池的互斥访问,应为它设置一互斥信号量应为它设置一互斥信号量 mutex，在生产者进程和消费者进程中都有成对的用于实现，在生产者进程和消费者进程中都有成对的用于实现互斥的互斥的P(mutex)和和V(mutex)操作操作.（3）如何实现进程同步）如何实现进程同步.为实现进程同步为实现进程同步,应为缓冲池设置表示缓冲区空和满的应为缓冲池设置表示缓冲区空和满的 empty 和和 full 信号量，读者应在相互合作的进程中找到成对的信号量，读者应在相互合作的进程中找到成对的