《操作系统同步例题》由会员分享，可在线阅读，更多相关《操作系统同步例题（40页珍藏版）》请在金锄头文库上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date操作系统同步例题操作系统同步例题13. 对于生产者消费者问题，假设缓冲区是无界的，试用信号灯与PV操作给出解法。答：由于是无界缓冲区，所以生产者不会因得不到缓冲区而被阻塞，不需要对空缓冲区进行管理，可以去掉在有界缓冲区中用来管理空缓冲区的信号量及其PV操作。semaphore mutex_in=1;semaphore mutex_out=1;semaphore emp
2、ty=0;int in=0，out=0;生产者活动：while(1)produce next product;P(mutex_in);add the product to bufferin;in+;v(mutex_in);V(empty); 消费者活动：while(1)P(empty);P(mutex_out);take the product from bufferout;out+;V(mutex_out);14. 设有一个可以装A、B两种物品的仓库，其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式:-MA物品数量B物品数量N其中M和N为正整数。 试用信号灯和PV操作描述A、B两
3、种物品的入库过程。答：已知条件 -MA物品数量B物品数量N 可以拆成两个不等式，即A物品数量B物品数量N，B物品数量A物品数量M。这两个不等式的含义是：仓库中A物品可以比B物品多，但不能超过N个；物品可以比A物品多，但不能超过M个。semaphore a=n;semaphore b=m;void main()createprocess(A,);createprocess(B,);A物品入库：void A()while(1)P(a);A物品入库;V(b);B物品入库：void B()while(1)P(b);B物品入库;V(a);15. 试用信号灯与PV操作实现司机与售票员之间的同步问题。设公共
4、汽车上有一个司机和一个售票员，其活动如下图所示。 为了安全起见，显然要求: (1)关车门后方能启动车辆；(2)到站停车后方能开车门。亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。解：如果进程P2尚未推进到处时，进程P1已经推进到处，则P1应等待直到P2推进到处为止；同样，如果进程P1尚未推进到处时，进程P2已经推进到处，则P2应等待直到P1推进到处为止。如果进程P1在处发生了等待，则当进程P2执行到处时应将P1唤醒；同样，如果进程P2在处发生了等待，则当进程P2执行到处时应将P1唤醒。用信号量和P、V操作解决这一问题，需要定义两个信号量
5、，一个信号量start表示是否允许司机启动车辆，另一个信号量open表示是否允许售票员开车门。初始状态是车停在始发站，车门开着，等待乘客上车。因此，两个信号量的初值都是0。semaphore start=0;semaphore open=0;司机的活动:P1: doP(start); 启动车辆;正常行车;到站停车;V(open);while (1);售票员的活动:P2: do关车门;V(start); 售票;P(open);开车门;while (1);16. 设有A、B、C三组进程，它们互斥地使用某一独占型资源R，使用前申请，使用后释放。资源分配原则如下:(1) 当只有一组申请进程时，该组申请
6、进程依次获得R；(2) 当有两组申请进程时，各组申请进程交替获得R，组内申请进程依次获得R；(3) 当有三组申请进程时，各组申请进程轮流获得R，组内申请进程依次获得R。试用信号灯和PV操作分别给出各组进程的申请活动程序段和释放活动程序段。解：int free=1;/设备状态标志semaphore mutex=1;semaphore qa=qb=qc=0; /各组等待队列int counta=countb=countc=0;/等待队列长度A组申请：P(mutex);if(free=1)free=0;V(mutex);elsecounta+;V(mutex);P(qa);A组释放：P(mutex)
7、;if(countb0)countb-;V(qb);elseif(countc0)countc-;V(qc);elseif(counta0)counta-V(qa);else free=1;A组进程活动可以给出B组和C组进程活动。17. 设自行车生产线上有一只箱子，其中有N个位置(N3)，每个位置可存放一个车架或一个车轮; 又设有三个工人，其活动分别为:工人1活动：do 加工一个车架;车架放入箱中;while(1)工人2活动：do 加工一个车轮;车轮放入箱中;while(1)工人3活动：do 箱中取一车架;箱中取二车轮;组装为一台车;while(1)试分别用信号灯与PV操作、管程、会合实现三个
8、工人的合作，要求解中不含死锁。解：用信号灯与PV操作实现三个工人的合作，管程与会合解法可仿照给出。首先不考虑死锁问题，工人1与工人3、工人2与工人3构成生产者与消费者关系，这两对生产/消费关系通过共同的缓冲区相联系。从资源的角度来看，箱子中的空位置相当于工人1和工人2的资源，而车架和车轮相当于工人3的资源。定义三个信号灯如下：semaphore empty=N;/空位置semaphore wheel=0;/车轮semaphore frame=0;/车架三位工人的活动分别为：工人1活动：do 加工一个车架;P(empty);车架放入箱中;V(frame);while(1)工人2活动：do 加工一
9、个车轮;P(empty);车轮放入箱中;V(wheel);while(1)工人3活动：do P(frame);箱中取一车架;V(empty);P(wheel);P(wheel);箱中取二车轮;V(empty);V(empty);组装为一台车;while(1)分析上述解法易见，当工人1推进速度较快时，箱中空位置可能完全被车架占满或只留有一个存放车轮的位置，而当此时工人3同时取2个车轮时将无法得到，而工人2又无法将新加工的车轮放入箱中；当工人2推进速度较快时，箱中空位置可能完全被车轮占满，而当此时工人3取车架时将无法得到，而工人1又无法将新加工的车架放入箱中。上述两种情况都意味着死锁。为防止死锁的
10、发生，箱中车架的数量不可超过N-2，车轮的数量不可超过N-1，这些限制可以用两个信号灯来表达。semaphore s1=N-2;semaphore s2=N-1;如此，可以给出不含死锁的完整解法如下：工人1活动：do 加工一个车架;P(s1);P(empty);车架放入箱中;V(frame);while(1)工人2活动：do 加工一个车轮;P(s2);P(empty);车轮放入箱中;V(wheel);while(1)工人3活动：do P(frame);箱中取一车架;V(empty);V(s1);P(wheel);P(wheel);箱中取二车轮;V(empty);V(empty);V(s2);V
11、(s2);组装为一台车;while(1)详细描述还应考虑对箱子单元的描述以及访问互斥问题。建议车架放在箱子的一端，车轮放在箱子的另一端，车架与车轮都采用后进先出的管理方式。18. 一座小桥(最多只能承重两个人)横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。试用信号灯和PV操作写出南、北两岸过桥的同步算法。解：桥上可能没有人，也可能有一人，也可能有两人。(a) 两人同时过桥(b) 两人都到中间(c) 南(北)来者到北(南)段共需要三个信号量，load用来控制桥上人数，初值为2，表示桥上最多有2人；north用来控制北段桥的
12、使用，初值为1，用于对北段桥互斥；south用来控制南段桥的使用，初值为1，用于对南段桥互斥。semaphore load=2;semaphore north=1;semaphore south=1;tosouth()P(load);P(north);过北段桥;到桥中间;V(north);P(south);过南段桥;到达南岸V(south);V(load);tonorth()P(load);P(south);过南段桥;到桥中间V(south);P(north);过北段桥;到达北岸V(north);V(load);19.某寺庙，有小和尚、老和尚若干庙内有一水缸，由小和尚提水入缸，供老和尚饮用。水
13、缸可容纳 30 桶水，每次入水、取水仅为1桶，不可同时进行。水取自同一井中，水井径窄，每次只能容纳一个水桶取水。设水桶个数为5个，试用信号灯和PV操作给出老和尚和小和尚的活动。semaphore empty=30;/ 表示缸中目前还能装多少桶水，初始时能装30桶水semaphore full=0;/ 表示缸中有多少桶水，初始时缸中没有水semaphore buckets=5;/ 表示有多少只空桶可用，初始时有5只桶可用semaphore mutex_well=1;/ 用于实现对井的互斥操作semaphore mutex_bigjar=1; / 用于实现对缸的互斥操作young_monk()wh
14、ile(1)P(empty);P(buckets);go to the well;P(mutex_well);get water;V(mutex_well);go to the temple;P(mutex_bigjar);pure the water into the big jar;V(mutex_bigjar);V(buckets);V(full);old_monk()while()P(full);P(buckets);P(mutex_bigjar);get water;V(mutex_bigjar);drink water;V(buckets);V(empty);20. 设系统中有5台类型相同的打印机，依次编号为
