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

《操作系统第2章习题分析.ppt》由会员分享，可在线阅读，更多相关《操作系统第2章习题分析.ppt（24页珍藏版）》请在一课资料网上搜索。

1、进程同步与互斥习题分析进程同步与互斥习题分析解题步骤：解题步骤： 确定进程的个数及每个进程的工作；确定进程的个数及每个进程的工作； 确定关键工作步（需要控制的）；确定关键工作步（需要控制的）； 确定信号量表示的含义（开始或结束）；确定信号量表示的含义（开始或结束）；1.1. 写出伪代码。写出伪代码。1.单行隧道问题对一个单行的隧道进行模拟，为了避免碰撞，必须对一个单行的隧道进行模拟，为了避免碰撞，必须防止汽车同时从两端（防止汽车同时从两端（A A、B B端）进入隧道。现要设计一个端）进入隧道。现要设计一个自动管理系统，管理规则如下：当隧道中有车辆在行驶时自动管理系统，管理规则如下：当隧道中有车

2、辆在行驶时同方向的车可以驶入隧道，但另一方向的车必须在隧道外同方向的车可以驶入隧道，但另一方向的车必须在隧道外等待；当隧道中无车时，到达等待；当隧道中无车时，到达A A 端（或端（或B B端）的车辆可以进端）的车辆可以进入隧道，但不能从入隧道，但不能从A A、B B端同时驶入隧道；当某方向在隧道端同时驶入隧道；当某方向在隧道中行驶的车辆使出了隧道且无车辆进入隧道时，应让另一中行驶的车辆使出了隧道且无车辆进入隧道时，应让另一方向等待的车辆进入隧道行驶。请用方向等待的车辆进入隧道行驶。请用PVPV操作设计一个算法操作设计一个算法实现这个控制。实现这个控制。例：单行隧道问题例：单行隧道问题。对一个单

3、行的隧道进行模拟，为了避免。对一个单行的隧道进行模拟，为了避免死锁，必须防止汽车同时从两端进入隧道。如果一次只允死锁，必须防止汽车同时从两端进入隧道。如果一次只允许一辆车通过隧道，两个方向按车辆到达的先后顺序依次许一辆车通过隧道，两个方向按车辆到达的先后顺序依次通过，请用通过，请用pv操作设计一个算法实现这个控制。操作设计一个算法实现这个控制。 分析分析：本题涉及两个进程：本题涉及两个进程：P1和和P2。隧道是一个临界资源。隧道是一个临界资源，一次只能被一辆车占有，可以把它看作互斥问题。，一次只能被一辆车占有，可以把它看作互斥问题。 设设：一个互斥信号量：一个互斥信号量sd=1，表示隧道是否可

4、用。，表示隧道是否可用。 int sd=1; cobegin P1() / P2() coend问题：问题：两个方向车辆通过隧道的交换比较平凡，系统效率不高。两个方向车辆通过隧道的交换比较平凡，系统效率不高。分析分析：为了提高效率，把问题改为：一旦一辆车进入，则同一方向的车为了提高效率，把问题改为：一旦一辆车进入，则同一方向的车可以立即跟进。写出用信号量解决此问题的代码，不考虑可以立即跟进。写出用信号量解决此问题的代码，不考虑“饥饿饥饿”的的情况。情况。(按照读者按照读者-写者问题处理写者问题处理)设设：3个信号量：个信号量：c表示计数器，表示计数器，m表示对临界资源计数器的控制，表示对临界资

5、源计数器的控制，sd表表示对临界资源隧道的控制，即隧道是否可用。示对临界资源隧道的控制，即隧道是否可用。 int c=0,m=1,sd=1; cobegin P1() / P2()coend问题：问题： 若若P1过隧道，则后续车辆可以跟进；过隧道，则后续车辆可以跟进； 若若p2过隧道，一次只能过一辆；过隧道，一次只能过一辆；1. P1不会产生不会产生“饥饿饥饿”的现象，而的现象，而p2会产生会产生“饥饿饥饿”的现象。的现象。分析分析：解决解决p2“饥饿饥饿”现象的方法现象的方法：再设一个信号量：再设一个信号量k，让，让p1、p2排队，可排队，可以做到以做到p1方向比方向比p2方向晚来的车辆被方

6、向晚来的车辆被k阻止。阻止。int c=0,m=1,sd=1,k=1; cobegin P1() / P2()coend问题：问题： 若若P1过隧道，则后续车辆可以跟进；过隧道，则后续车辆可以跟进；1. 若若p2过隧道，一次只能过一辆过隧道，一次只能过一辆 。分析分析：解决解决p2可以过多辆车的方法可以过多辆车的方法：按照读者：按照读者-读者问题处理。即：读者问题处理。即：p1为读者，为读者，p2为读者，但两个读者不能同时读为读者，但两个读者不能同时读 。int c1=c2=0,m1=m2=1,sd=1; /c1、c2为计数器，为计数器，m1、m2、sd为互为互斥信号量斥信号量cobegin

7、P1() / P2()coend1.单行隧道问题void Pab() do 从从A端驶入，到端驶入，到B端驶出；端驶出； while(TRUE);void Pba () do 从从B端驶入，到端驶入，到A端驶出；端驶出； while(TRUE);计数器：计数器：countab、countba分别表示分别表示A-BA-B、B-AB-A的车辆数的车辆数; ; 信号量：信号量：s、mutexab、mutexba；1.单行隧道问题int countab=0，countba=0; Semaphore s=1, mutexab=1,mutexba=1；void Pab() do wait(mutexab)

8、countab+； if (countab=1) then wait(s); signal(mutexab)； 从从A端驶入，到端驶入，到B端驶出；端驶出； wait(mutexab); countab- -; if (countab=0) then signal(s) signal(mutexab); while(TRUE);2.公交车行驶问题 在公交车行驶过程中汽车司机与售票员之间在公交车行驶过程中汽车司机与售票员之间必须协同工作。为了安全行驶规定：其一、只有必须协同工作。为了安全行驶规定：其一、只有售票员把车门关好了司机才能开车，因此，售票售票员把车门关好了司机才能开车，因此，售票员关

9、好车门应通知司机开车；其二、只有当汽车员关好车门应通知司机开车；其二、只有当汽车已经停下，售票员才能开门上下客，故司机停车已经停下，售票员才能开门上下客，故司机停车后应通知售票员，汽车当前正在始发站停车上客。后应通知售票员，汽车当前正在始发站停车上客。试设必要的信号灯及赋初值，用试设必要的信号灯及赋初值，用PVPV操作设计一个操作设计一个算法实现这个控制。算法实现这个控制。void Driver () do 启动开车启动开车; 正常行车正常行车; 到站停车到站停车; while(TRUE);返回2.公交车行驶问题void Conductor () do 开车门开车门; 关车门关车门; 卖票；卖

10、票； while(TRUE);信号量设置：信号量设置：用两个信号量用两个信号量s1s1、s2s2，分别表示可以，分别表示可以开门和可以开车，其初始值都为开门和可以开车，其初始值都为0 0。Semaphore s1=0, s2=0;void Driver () do wait (s2); 启动开车启动开车; 正常行车正常行车; 到站停车到站停车; signal (s1); while(TRUE); 返回2.公交车行驶问题void Conductor () do wait (s1); 开车门开车门; 关车门关车门; signal (s2); 卖票；卖票； while(TRUE);3. 和尚挑水问题

11、 寺庙里有多个大、小和尚，一水缸。小和寺庙里有多个大、小和尚，一水缸。小和尚取水，大和尚饮水。水缸容积尚取水，大和尚饮水。水缸容积1010桶水，水取桶水，水取自同一水井，水井每次只容一个桶取水，桶总自同一水井，水井每次只容一个桶取水，桶总数数3 3个，每次只能一个桶在水缸中入、取水。试个，每次只能一个桶在水缸中入、取水。试用用P P、V V操作描述小和尚取水、大和尚饮水的过操作描述小和尚取水、大和尚饮水的过程。程。3. 和尚挑水问题void shaveling() do 从水井打水；从水井打水； 往缸中放水往缸中放水 while(TRUE);void bonze() do 从缸中从缸中取取水水

12、 饮水；饮水； while(TRUE);信号量设置：信号量设置：mutex1=mutex2=1;mutex1=mutex2=1;分别代表分别代表可以用可以用水井和水缸水井和水缸empty=10; empty=10; 水缸的水缸的容量容量full=0; full=0; 水缸水缸中中的水量的水量count=3;count=3;水桶个数水桶个数3. 和尚挑水问题void shaveling() do wait (empty)； wait (count)； wait (mutex1)； 从水井打水；从水井打水； signal (mutex1)； wait (mutex2)； 往缸中放水往缸中放水；

13、signal (mutex2)； signal (full)； signal (count)； while(TRUE);void bonze() do wait (full)； wait (count)； wait (mutex2)； 从水缸取水从水缸取水； signal (mutex2)； signal (count)； signal (empty)； 饮水；饮水； while(TRUE);信号量设置：信号量设置：mutex1=mutex2=1;mutex1=mutex2=1;分别代表分别代表可以用可以用水井和水缸水井和水缸empty=10; empty=10; 水缸的水缸的容量容量full

14、0; full=0; 水缸水缸中中的水量的水量count=3;count=3;水桶个数水桶个数4. 哲学家问题 对教程描述的哲学家问题，规定奇数号的哲对教程描述的哲学家问题，规定奇数号的哲学家先拿起他左边的筷子学家先拿起他左边的筷子, ,然后再去拿他右边的筷然后再去拿他右边的筷子；而偶数号的哲学家则相反。按此规定，用子；而偶数号的哲学家则相反。按此规定，用P P、V V操作设计一个算法实现这个控制。操作设计一个算法实现这个控制。4. 哲学家问题semaphore chopstick5=1，1，1，1，1;void philosopher(int i) do think(); eat(); w

15、hile(true);4. 哲学家问题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

16、 (chopstick i + 1 mod 5) ; eat(); signal (chopstick i) ; signal (chopstick i + 1 mod 5) ; 例：单行隧道问题例：单行隧道问题。对一个单行的隧道进行模拟，为了避免。对一个单行的隧道进行模拟，为了避免死锁，必须防止汽车同时从两端进入隧道。如果一次只允死锁，必须防止汽车同时从两端进入隧道。如果一次只允许一辆车通过隧道，两个方向按车辆到达的先后顺序依次许一辆车通过隧道，两个方向按车辆到达的先后顺序依次通过，请用通过，请用pv操作设计一个算法实现这个控制。操作设计一个算法实现这个控制。 分析分析：解决解决p2可以过多

17、辆车的方法可以过多辆车的方法：按照读者：按照读者-读者问题处理。即：读者问题处理。即：p1为读者，为读者，p2为读者，但两个读者不能同时读为读者，但两个读者不能同时读 。int c1=c2=0,m1=m2=1,sd=1; /c1、c2为计数器，为计数器，m1、m2为互斥信为互斥信号量号量cobegin P1() / P2()coend问题：问题： 若若P1过隧道，则后续车辆可以跟进，有可能使过隧道，则后续车辆可以跟进，有可能使p2“饥饿饥饿”1. 若若P2过隧道，则后续车辆也可以跟进，有可能使过隧道，则后续车辆也可以跟进，有可能使p1“饥饿饥饿”假设假设：问题改为：一旦一辆车进入，则同一方向的

18、车可以立即跟进，隧道最多只能过：问题改为：一旦一辆车进入，则同一方向的车可以立即跟进，隧道最多只能过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优先的方法。优先的方法。 p1后续车辆可以跟进，后续车辆可以跟进，p2后续车辆也能跟进。后续车辆也能跟进。1. P1会产生会产生“饥饿饥饿”的现象，的现象，p2也会

19、产生也会产生“饥饿饥饿”的现象。的现象。解决解决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操作的规则操作的规则： 分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行

20、顺序要求的）。前后执行顺序要求的）。 对于互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类对于互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，互斥信号量的个数只与临界资源的种类有关。通常，有几类临界资源，互斥信号量的个数只与临界资源的种类有关。通常，有几类临界资源就设置几个互斥信号量，且初值为就设置几个互斥信号量，且初值为1，代表临界资源可用。，代表临界资源可用。 对于同步问题要设置同步信号量，通常同步信号量的个数与参与同步的对于同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关，即同步关系涉及几类进程，就有几个同步信号量。同步进程种类有关，即同步关系

21、涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。信号量表示该进程是否可以开始或该进程是否已经结束。 在每个进程中用于实现互斥的在每个进程中用于实现互斥的PV操作必须成对出现；用于实现同步的操作必须成对出现；用于实现同步的PV操作也必须成对出现，但是，它们分别出现在不同的进程中；在某个进操作也必须成对出现，但是，它们分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的程中如果同时存在互斥与同步的P操作，则其顺序不能颠倒。必须先执行操作，则其顺序不能颠倒。必须先执行对同步信号量的对同步信号量的P操作，再执行对互斥信号量的操作，再执行对互斥信号量的P操作。但是，操作。但是，V操作的操作的顺序没有严格要求。顺序没有严格要求。