操作系统第2章习题分析.

进程同步与互斥习题分析解题步骤：1.确定进程的个数及每个进程的工作；2.确定关键工作步（需要控制的）；3.确定信号量表示的含义（开始或结束）；4.写出伪代码。1.单行隧道问题对一个单行的隧道进行模拟，为了避免碰撞，必须防止汽车同时从两端（A、B端）进入隧道。现要设计一个自动管理系统，管理规则如下：当隧道中有车辆在行驶时同方向的车可以驶入隧道，但另一方向的车必须在隧道外等待；当隧道中无车时，到达A端（或B端）的车辆可以进入隧道，但不能从A、B端同时驶入隧道；当某方向在隧道中行驶的车辆使出了隧道且无车辆进入隧道时，应让另一方向等待的车辆进入隧道行驶。请用PV操作设计一个算法实现这个控制。例：单行隧道问题。对一个单行的隧道进行模拟，为了避免死锁，必须防止汽车同时从两端进入隧道。如果一次只允许一辆车通过隧道，两个方向按车辆到达的先后顺序依次通过，请用pv操作设计一个算法实现这个控制。1.单行隧道问题P1(){通过隧道；}P2(){通过隧道；}分析：本题涉及两个进程：P1和P2。隧道是一个临界资源，一次只能被一辆车占有，可以把它看作互斥问题。设：一个互斥信号量sd=1，表示隧道是否可用。intsd=1;cobeginP1()//P2()coend1.单行隧道问题P1(){P(sd);通过隧道；V(sd);}P2(){P(sd);通过隧道；V(sd);}问题：两个方向车辆通过隧道的交换比较平凡，系统效率不高。分析：为了提高效率，把问题改为：一旦一辆车进入，则同一方向的车可以立即跟进。写出用信号量解决此问题的代码，不考虑“饥饿”的情况。(按照读者-写者问题处理)设：3个信号量：c表示计数器，m表示对临界资源计数器的控制，sd表示对临界资源隧道的控制，即隧道是否可用。intc=0,m=1,sd=1;cobeginP1()//P2()coend1.单行隧道问题P2(){P(sd);通过隧道；V(sd);}P1(){P(m);/*m控制计数器c*/if(c==0)P(sd);/*p1第一辆车通过时占有隧道*/c=c+1;V(m);通过隧道；P(m);c=c-1;if(c==0)V(sd);/*p1最后一辆车通过后释放隧道*/V(m);}问题：1.若P1过隧道，则后续车辆可以跟进；2.若p2过隧道，一次只能过一辆；3.P1不会产生“饥饿”的现象，而p2会产生“饥饿”的现象。分析：解决p2“饥饿”现象的方法：再设一个信号量k，让p1、p2排队，可以做到p1方向比p2方向晚来的车辆被k阻止。intc=0,m=1,sd=1,k=1;cobeginP1()//P2()coend1.单行隧道问题P2(){P(k);P(sd);通过隧道；V(sd);V(k);}P1(){P(k);/*与P2一起排队*/P(m);/*m1控制计数器c*/if(c==0)P(sd);/*P1第一辆车通过时占有隧道*/c=c+1;V(m);V(k);通过隧道；P(m);c=c-1;if(c==0)V(sd);/*P1最后一辆车通过后释放隧道*/V(m);}问题：1.若P1过隧道，则后续车辆可以跟进；2.若p2过隧道，一次只能过一辆。分析：解决p2可以过多辆车的方法：按照读者-读者问题处理。即：p1为读者，p2为读者，但两个读者不能同时读。intc1=c2=0,m1=m2=1,sd=1;//c1、c2为计数器，m1、m2、sd为互斥信号量cobeginP1()//P2()coend1.单行隧道问题P1(){P(m1);if(c1==0)P(sd);c1=c1+1;V(m1);通过隧道；P(m1);c1=c1-1;if(c1==0)V(sd);V(m1);}P2(){P(m2);if(c2==0)P(sd);c2=c2+1;V(m2);通过隧道；P(m2);c2=c2-1;if(c2==0)V(sd);V(m2);}1.单行隧道问题voidPab(){do{从A端驶入，到B端驶出；}while(TRUE);}voidPba(){do{从B端驶入，到A端驶出；}while(TRUE);}计数器：countab、countba分别表示A-B、B-A的车辆数;信号量：s、mutexab、mutexba；1.单行隧道问题intcountab=0，countba=0;Semaphores=1,mutexab=1,mutexba=1；voidPab(){do{wait(mutexab)；countab++；if(countab==1)thenwait(s);signal(mutexab)；从A端驶入，到B端驶出；wait(mutexab);countab--;if(countab==0)thensignal(s)signal(mutexab);}while(TRUE);}2.公交车行驶问题在公交车行驶过程中汽车司机与售票员之间必须协同工作。为了安全行驶规定：其一、只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车；其二、只有当汽车已经停下，售票员才能开门上下客，故司机停车后应通知售票员，汽车当前正在始发站停车上客。试设必要的信号灯及赋初值，用PV操作设计一个算法实现这个控制。voidDriver(){do{启动开车;正常行车;到站停车;}while(TRUE);}返回2.公交车行驶问题voidConductor(){do{开车门;关车门;卖票；}while(TRUE);}信号量设置：用两个信号量s1、s2，分别表示可以开门和可以开车，其初始值都为0。Semaphores1=0,s2=0;voidDriver(){do{wait(s2);启动开车;正常行车;到站停车;signal(s1);}while(TRUE);}返回2.公交车行驶问题voidConductor(){do{wait(s1);开车门;关车门;signal(s2);卖票；}while(TRUE);}3.和尚挑水问题寺庙里有多个大、小和尚，一水缸。小和尚取水，大和尚饮水。水缸容积10桶水，水取自同一水井，水井每次只容一个桶取水，桶总数3个，每次只能一个桶在水缸中入、取水。试用P、V操作描述小和尚取水、大和尚饮水的过程。3.和尚挑水问题voidshaveling(){do{从水井打水；往缸中放水}while(TRUE);}voidbonze(){do{从缸中取水；饮水；}while(TRUE);}信号量设置：mutex1=mutex2=1;分别代表可以用水井和水缸empty=10;水缸的容量full=0;水缸中的水量count=3;水桶个数3.和尚挑水问题voidshaveling(){do{wait(empty)；wait(count)；wait(mutex1)；从水井打水；signal(mutex1)；wait(mutex2)；往缸中放水；signal(mutex2)；signal(full)；signal(count)；}while(TRUE);}voidbonze(){do{wait(full)；wait(count)；wait(mutex2)；从水缸取水；signal(mutex2)；signal(count)；signal(empty)；饮水；}while(TRUE);}信号量设置：mutex1=mutex2=1;分别代表可以用水井和水缸empty=10;水缸的容量full=0;水缸中的水量count=3;水桶个数4.哲学家问题对教程描述的哲学家问题，规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子；而偶数号的哲学家则相反。按此规定，用P、V操作设计一个算法实现这个控制。4.哲学家问题semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){do{think();eat();}while(true);}4.哲学家问题semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();if(i%2==0){//偶数哲学家，先右后左。wait(chopstick[i+1]mod5);wait(chopstick[i]);eat();signal(chopstick[i+1]mod5);signal(chopstick[i]);}else{//奇数哲学家，先左后右。wait(chopstick[i]);wait(chopstick[i+1]mod5);eat();signal(chopstick[i]);signal(chopstick[i+1]mod5);}}例：单行隧道问题。对一个单行的隧道进行模拟，为了避免死锁，必须防止汽车同时从两端进入隧道。如果一次只允许一辆车通过隧道，两个方向按车辆到达的先后顺序依次通过，请用pv操作设计一个算法实现这个控制。单行隧道问题再分析P1(){通过隧道；}P2(){通过隧道；}分析：解决p2可以过多辆车的方法：按照读者-读者问题处理。即：p1为读者，p2为读者，但两个读者不能同时读。intc1=c2=0,m1=m2=1,sd=1;//c1、c2为计数器，m1、m2为互斥信号量cobeginP1()//P2()coend单行隧道问题再分析P1(){P(m1);if(c1==0)P(sd);c1=c1+1;V(m1);通过隧道；P(m1);c1=c1-1;if(c1==0)V(sd);V(m1);}问题：1.若P1过隧道，则后续车辆可以跟进，有可能使p2“饥饿”2.若P2过隧道，则后续车辆也可以跟进，有可能使p1“饥饿”P2(){P(m2);if(c2==0)P(sd);c2=c2+1;V(m2);通过隧道；P(m2);c2=c2-1;if(c2==0)V(sd);V(m2);}假设：问题改为：一旦一辆车进入，则同一方向的车可以立即跟进，隧道最多只能过4辆车，如何修改算法？intc1=c2=0,m1=m2=1,sd=1,k1=4,k2=4;//c1、c2为计数器，m1、m2为互斥信号量cobegin//k1、k2为控制各自方向上通过的车辆数P1()//P2()coend单行隧道问题再分析P1(){P(k1);P(m1);if(c1==0)P(sd);c1=c1+1;V(m1);通过隧道；P(m1);c1=c1-1;if(c1==0)V(sd);V(m1);V(k1);}问题：1.是p1优先或p2优先的方法。2.p1后续车辆可以跟进，p2后续车辆也能跟进。3.P1会产生“饥饿”的现象，p2也会产生“饥饿”的现象。P2(){P(k2);P(m2);if(c2==0)P(sd);c2=c2+1;V(m2);通过隧道；P(m2);c2=c2-1;if(c2==0)V(sd);V(m2);V(k2);}解决p1、p2“饥饿”现象的方法是：一方每过n（如4）辆车后，就允许对方也过n辆车。intc1=c2=0,m1=m2=1,sd=1,k1=4,k2=4,n1=0,n2=0;//n1、n2为计数器cobegin//k1、k2为控制各自方向上通过的车辆数P1()//P2()coend单行隧道问题再分析P1(){P(k1);P(m1);if(c1==0)P(sd);c1++;n1++;V(m1);通过隧道；P(m1);c1=c1-1;if(c1==0){V(sd);//让本方向再过4车for(i=1;i=n1;i++)V(k1);n1=0;}V(m1);V(k1);}P2(){P(k2);P(m2);if(c2==0)P(sd);c2++;n2++;V(m2);通过隧道；P(m2);c2=c2-1;if(c2==0){V(sd);//让本方向再过4车for(i=1;i=n2;i++)V(k2);n2=0;}V(m2);V(k2);}使用PV操作的规则：①分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。②对于互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，互斥信号量的个数只与临界