操作系统四道算法题

《操作系统四道算法题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、考虑有三个吸烟者进程和一个经销商进程的系统。每个吸烟者连续不断地做烟卷并抽他做好的烟卷。做一支烟卷需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可做烟卷并抽烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此反复。试设计同步算法来描述他们的活动。本题是一个有限缓冲区的生产者消费者问题，关键是找到缓冲区资源，以及谁是生产者、谁是消费者。　　本题中烟草、纸和火柴应该看作是产品，桌子是缓冲区。问题是有几种产品。烟草、纸

2、和火柴三种原料又不能简单地看成是三种产品，因为它们并不是以单独的形式被三个吸烟者进程所竞争的，而是以固定的组合被三个进程所申请的。因此可以考虑：设置三个信号量r、s和t，分别代表三种原料组合，即r表示烟草和纸，s表示纸和火柴，t表示烟草和火柴，初值均为0；桌面上一次只能放一种组合，可以看作是放一个产品的缓冲区，设置信号量empty初值为1，控制经销商往桌子上放原料；对于三个吸烟者的申请动作也要加以判断，用三个变量smoker1、smoker2、smoker3，初值为false，当为true时，表示申请资源，得到资源后置为false。四个

3、进程循环往复，并发执行。　　　　经销商进程：　　　　吸烟者1进程：　　　　吸烟者2进程：　　　　吸烟者3进程：　　1、a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点(或b点)的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量为工具，对ab段实现正确管理以保证行驶安全。 读者－写

4、着问题的变形。我们设置3个信号量S1、S2和Sab，分别用于从a点进入的车互斥访问共享变量ab（用于记录当前ab段上由a点进入的车辆的数量），从b点进入的车互斥访问共享变量ba（用于记录当前ab段上由b点进入的车辆的数量）和a、b点的车辆互斥进入ab段。3个信号量的初值分别为1、1和1，两个共享变量ab和ba的初值分别为0、0。SemaphoreS1=1,S2=1,Sab=1;intab=ba=0;voidPab(){while(1){wait(S1);if(ab==0)wait(Sab);ab=ab+1;signal(S1);车辆从a

5、点驶向b点;wait(S1);ab=ab-1;if(ab==0)signal(Sab);signal(S1);}}voidPba(){while(1){wait(S2);if(ba==0)wait(Sab);ba=ba+1;signal(S2);车辆从b点驶向a点;wait(S2);ba=ba-1;if(ba==0)signal(Sab);signal(S2);}}main(){cobegin{Pab();Pba();}}2、如果有三个进程R、W1、W2共享一个缓冲器B，而B中每次只能存放一个数。当缓冲器中无数时，进程R可以将从输入设备

6、上读入的数存放到缓冲器中。若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。同时规定：进程R必须等缓冲区中的数被取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器的数只能打印一次；W1和W2都不能从空缓冲中取数。写出这三个并发进程能正确工作的程序。信号量：customers表示正在等待复印的顾客数量（不包括正在复印的顾客）operator记录正在等候顾客的操作员数，只有1和0mutex用于对waiting的访问;变量：waiting表示等待的顾客数量。它实际上是custo

7、mers的一个副本。之所以使用waiting是因为无法读取信号量的当前值。semaphorecustomers=0,operator=0,mutex=1;waiting=0；processoperator()//操作员进程{while(1){wait(customers);//等待顾客到来复印；signal(operator);//通知顾客已经完成复印}}processcusotmeri()//顾客进程i{wait(mutex);if(waiting<5){waiting++;signal(customers);signal(mutex

8、);wait(operator);wait(mutex);waiting--;signal(mutex);}else{signal(mutex);离开复印室；}}main(){cobegin{operato