1、26. 假定有如下独木桥问题:过桥时,同一方向的行人可连续过桥,当某一方向有人过桥时,另一方向的行人必须等待;当某一方向无人过桥时,另一方向的行人可以过桥。试用信号量机制解决。答:(1) 将独木桥的两个方向分别标记为 A 和 B。用整型变量 countA 和 countB 分别表示 A、B 方向上已在独木桥上的行人数,初值都设置为 0。需要设置三个初值都为 1 的互斥信号量:MA 用来实现对 countA 的互斥访问,MB 用来实现对 countB 的互斥访问,mutex 用来实现两个方向的行人对独木桥的互斥使用。(2)以下使用信号量机制对 A 方向上的行人过桥和 B 方向上的行人过桥的算法进
2、行描述:int countA, countB;countA = 0; countB = 0; Semaphore MA,MB,mutex; /定义了三个互斥信号量MA.value=1; MB.value=1; mutex.value=1;cobeginprocess A_direction_cross_bridge_person /A 方向上过独木桥的行人进程P(MA); /实现对临界资源 countA 的互斥访问/当 A 方向上没有行人过独木桥时,这时有可能存在 B 方向上的行人在过独木桥。if (countA = 0) P(mutex); /如果当前独木桥正在被使用,说明 B 方向上的行人
3、正在过桥,则 A 方向上的行人必须等待。countA=countA+1; /当 B 方向上没有行人过桥时,则 A 方向上的行人可以过独木桥。因此 A方向上已在独木桥上的行人数增加 1 个V(MA); /退出临界区过桥; /A 方向上的行人通过独木桥P(MA); /实现对临界资源 countA 的互斥访问countA=countA-1; /当 A 方向上的行人已经通过了独木桥时,则 A 方向上在独木桥上的行人数需要减少 1 个if(countA=0) /如果 A 方向上在独木桥上的行人数减少到 0,则V(mutex); /需要释放独木桥临界资源,唤醒第一个由于在等待独木桥而处于等待状态的B 方向
4、上过独木桥的行人进程(如果此进程存在)V(MA); /退出临界区process B_direction_cross_bridge_person /B 方向上过独木桥的行人进程P(MB); /实现对临界资源 countB 的互斥访问/当 B 方向上没有行人过独木桥时,这时有可能存在 A 方向上的行人在过独木桥。 if (countB=0) P(mutex); /如果当前独木桥正在被使用,说明 A 方向上的行人正在过桥,则 B 方向上的行人必须等待。countB=countB+1; /当 A 方向上没有行人过桥时,则 B 方向上的行人可以过独木桥。因此B 方向上已在独木桥上的行人数增加 1 个V(
5、MB); /退出临界区过桥;/B 方向上的行人通过独木桥P(MB); /实现对临界资源 countB 的互斥访问countB=countB-1; /当 B 方向上的行人已经通过了独木桥时,则 B 方向上在独木桥上的行人数需要减少 1 个if(countB=0) /如果 B 方向上在独木桥上的行人数减少到 0,则V(mutex); /需要释放独木桥临界资源,唤醒第一个由于在等待独木桥而处于等待状态的A 方向上过独木桥的行人进程(如果此进程存在)V(MB); /退出临界区coend27.有 7 个并发执行的进程 Pi(i=1,2, ,7) ,若希望它们按照如下图所示的次序执行,试写出进程并发执行的
6、算法。Semaphore S8; /定义一个大小等于 8 的结构型信号量数组for(int i=0;i8;i+) Si.Value=0;process PP()cobegin /伪代码 cobegin 和 coend 表示夹在它们之间的语句可以并发执行P1; V(S1);P2; V(S0);P(S0); P(S1); P3; V(S2); V(S3); V(S4);P(S2); P4; V(S5);P(S4); P5; V(S6);P(S5); P(S3); P6; V(S7);P(S7); P(S6); P7;coend29.在公共汽车上,司机的活动描述为:启动汽车、正常行车、到站停车;售票
7、员的活动描述为:关车门、售票、开车门;试写出司机与售票员之间的同步算法。答:在汽车行驶过程中,司机活动与售票员活动之间的同步关系为:售票员关车门后,向司机发开车信号,司机接到开车信号后启动汽车,在汽车正常行驶过程中售票员售票,到站时司机停车,售票员在车停后开车门让乘客上下车。因此司机启动汽车的动作必须与售票员关车门的动作取得同步,而售票员开车门的动作也必须与司机到站停车的动作取得同步。在本题中,应设置两个信号量 S1 和 S2。S1 表示是否允许司机启动汽车(或表示售票员是否已经关好车门) ,其初值为 0;S2 表示是否允许售票员开门(或表示司机是否已经到站停车了) ,其初值为 0.S0S1S
8、2S3S4S5S6S7P2 P3 P4 P6 P7 P5 P1 采用信号量机制描述司机与售票员之间的同步算法如下:Semaphore S1,S2; /首先定义两个信号量 S1 和 S2S1.value=0; S2.value=0;cobeginprocess driver() process conductor() while(1) while(1) P(S1); 关车门;启动汽车; V(S1);正常行车; 售票; 到站停车; P(S2);V(S2); 开车门; 上下乘客 ; coend我们来分析这个过程,首先将信号量 S1 和 S2 的初值都设为 0.然后进行以下分析:1.P(S1) :S1
9、.value = S1.value - 1 = -1 0 ,那么司机进程就自己阻塞起来,等待售票员进程,售票员关车门。2.V(S1) :S1.value = S1.value + 1 = 0 = 0,唤醒司机进程,那么司机就开始启动汽车、正常行车;在此期间,售票员也可以同时进行售票。3.P(S2) :S2.value = S2.value - 1 = -1 0 ,那么售票员在售完票后,售票员进程就会自己阻塞起来,等待司机进程。这样就能避免当司机还没到站停车时,售票员就已经将车门打开了。而这是不允许的。4.V(S2) :S2.value = S2.value + 1 = 0 = 0,司机到站停车
10、之后,就唤醒售票员进程,那么售票员就开启车门让乘客上下车。那么这个进程就完成了。30一个阅览室共有 100 个座位,用一张表来管理,每个表目记录座位号和读者姓名。读者进入时要先在表上登记,离开时要注销登记。试写出读者“进入”和“注销”之间的同步算法。答:读者的动作有两个,一是填表进入阅览室读书,这时要考虑阅览室里是否有座位;二是读者阅读完毕,需要注销登记再离开阅览室,这时的操作要考虑阅览室里是否有读者存在。读者在阅览室读书时,由于没有引起资源的变动,不算动作变化。因此,设置算法所涉及的三个信号量:empty 资源信号量 表示阅览室里的空座位的数目,初值为 100;full 资源信号量 表示阅览
11、室里有人的座位的数目(或表示阅览室里的读者的数目) ,初值为 0;mutex 互斥信号量表示对登记表这个临界资源的互斥访问,初值设为 1。使用信号量机制对读者“进入”阅览室和“注销”登记之间的同步算法描述如下:Semaphore empty,full,mutex; /首先定义两个资源信号量 empty、full 和一个互斥信号量 mutexempty.value=100; full.value=0;mutex.value=1;cobeginprocess getin() /读者“进入”阅览室的进程while(1)P (empty); /没有座位则离开P (mutex); /进入临界区填写登记表
12、;进入阅览室读书;V (mutex); /离开临界区V (full); /释放一个读者资源process getout () /读者“注销”登记、离开阅览室的进程while(1)P(full); /阅览室是否有人在读书(是否存在有人的座位)P(mutex); /进入临界区注销登记;离开阅览室; V(mutex); /离开临界区V(empty); /释放一个座位资源 coend32.假定有 3 个进程 R、W1、W2 共享一个缓冲区 B,B 中每次只能存放一个整数。进程R 从输入设备读入一个数进缓冲区 B。若读入的是奇数,则由进程 W1 取出打印;若读入的是偶数,则由进程 W2 取出打印。规定不
13、能重复从 B 中取数打印。试写出同步算法。答:需要设置 3 个信号量:(1)信号量 empty 用于表示进程 R 可向缓冲区 B 中读入的整数个数,初值为 1,表示进程 R 能读入一个整数到缓冲区 B 中。(2)信号量 SW1 的初值为 0,表示开始时缓冲区 B 中没有奇数可供进程 W1 读取。SW1 控制 R与 W1 之间的同步。(3)信号量 SW2 的初值为 0,表示开始时缓冲区 B 中没有偶数可供进程 W2 读取。SW2 控制 R与 W2 之间的同步。使用信号量机制对这三个进程的同步算法描述如下:Semaphore empty,SW1,SW2; /首先定义 3 个信号量empty.val
14、ue=1;SW1.value=0;SW2.value=0;cobeginprocess R()int x;while(1)从输入设备上读一个整数到 x;P(empty); /判断进程 R 能否向缓冲区 B 中读入一个整数。如果不可以,则 R 进程阻塞起来等待。否则,继续向下执行。B=x; /把读入到变量 x 中的整数赋值给缓冲区 Bif(x%2=1) V(SW1); /如果读入的是奇数,则向进程 W1 发出信号else V(SW2); /如果读入的是偶数,则向进程 W2 发出信号process W1()int y;while(1)P(SW1); /收到 R 发过来的信号,已产生一个奇数y=B; /取出缓冲区 B 中的奇数到变量 y 中打印 y 中的数;V(empty); /向 R 发出信号,使进程 R 又可以向缓冲区 B 读入一个整数process W2()int z;while(1)P(SW2); /收到进程 R 发过来的信号,已产生一个偶数z=B; /取出缓冲区 B 中的偶数到变量 z 中打印 z 中的数;V(empty); /向 R 发出信号,使进程 R 又可以向缓冲区 B 读入一个整数coend