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

进程同步与互斥习题分析;1.单行隧道问题;例：单行隧道问题。对一个单行的隧道进行模拟，为了避免死锁，必须防止汽车同时从两端进入隧道。如果一次只允许一辆车通过隧道，两个方向按车辆到达的先后顺序依次通过，请用pv操作设计一个算法实现这个控制。 ;分析：本题涉及两个进程：P1和P2。隧道是一个临界资源，一次只能被一辆车占有，可以把它看作互斥问题。 设：一个互斥信号量sd=1，表示隧道是否可用。 int sd=1; cobegin P1() // P2() coend;分析：为了提高效率，把问题改为：一旦一辆车进入，则同一方向的车可以立即跟进。写出用信号量解决此问题的代码，不考虑“饥饿”的情况。(按照读者-写者问题处理) 设：3个信号量：c表示计数器，m表示对临界资源计数器的控制，sd表示对临界资源隧道的控制，即隧道是否可用。 int c=0,m=1,sd=1; cobegin P1() // P2() coend;分析：解决p2“饥饿”现象的方法：再设一个信号量k，让p1、p2排队，可以做到p1方向比p2方向晚来的车辆被k阻止。 int c=0,m=1,sd=1,k=1; cobegin P1() // P2() coend;分析：解决p2可以过多辆车的方法：按照读者-读者问题处理。即：p1为读者，p2为读者，但两个读者不能同时读 。 int c1=c2=0,m1=m2=1,sd=1; //c1、c2为计数器，m1、m2、sd为互斥信号量 cobegin P1() // P2() coend;1.单行隧道问题;1.单行隧道问题;2.公交车行驶问题;void Driver () { do { 启动开车; 正常行车; 到站停车; } while(TRUE); };Semaphore s1=0, s2=0; void Driver () { do { wait (s2); 启动开车; 正常行车; 到站停车; signal (s1); } while(TRUE); } ;3. 和尚挑水问题;3. 和尚挑水问题;3. 和尚挑水问题;4. 哲学家问题;4. 哲学家问题;4. 哲学家问题;例：单行隧道问题。对一个单行的隧道进行模拟，为了避免死锁，必须防止汽车同时从两端进入隧道。如果一次只允许一辆车通过隧道，两个方向按车辆到达的先后顺序依次通过，请用pv操作设计一个算法实现这个控制。 ;分析：解决p2可以过多辆车的方法：按照读者-读者问题处理。即：p1为读者，p2为读者，但两个读者不能同时读 。 int c1=c2=0,m1=m2=1,sd=1; //c1、c2为计数器，m1、m2为互斥信号量 cobegin P1() // P2() coend;假设：问题改为：一旦一辆车进入，则同一方向的车可以立即跟进，隧道最多只能过4辆车，如何修改算法？ int c1=c2=0,m1=m2=1,sd=1,k1=4,k2=4 ;//c1、c2为计数器，m1、m2为互斥信号量 cobegin //k1、k2为控制各自方向上通过的车辆数 P1() // P2() coend;解决p1、p2“饥饿”现象的方法是：一方每过n（如4）辆车后，就允许对方也过n辆车。 int c1=c2=0,m1=m2=1,sd=1,k1=4,k2=4, n1=0,n2=0 ; //n1、n2为计数器 cobegin //k1、k2为控制各自方向上通过的车辆数 P1() // P2() coend;使用PV操作的规则： ① 分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。 ② 对于互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，互斥信号量的个数只与临界资源的种类有关。通常，有几类临界资源就设置几个互斥信号量，且初值为1，代表临界资源可用。 ③ 对于同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关，即同步关系涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。 ④ ??每个进程中用于实现互斥的PV操作必须成对出现；用于实现同步的PV操作也必须成对出现，但是，它们分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的P