操作系统四道算法题.doc

考虑有三个吸烟者进程和一个经销商进程的系统。每个吸烟者连续不断地做烟卷并抽他做好的烟卷。做一支烟卷需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可做烟卷并抽烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此反复。试设计同步算法来描述他们的活动。本题是一个有限缓冲区的生产者消费者问题，关键是找到缓冲区资源，以及谁是生产者、谁是消费者。本题中烟草、纸和火柴应该看作是产品，桌子是缓冲区。问题是有几种产品。烟草、纸和火柴三种原料又不能简单地看成是三种产品，因为它们并不是以单独的形式被三个吸烟者进程所竞争的，而是以固定的组合被三个进程所申请的。因此可以考虑：设置三个信号量r、s和t，分别代表三种原料组合，即r表示烟草和纸，s表示纸和火柴，t表示烟草和火柴，初值均为0；桌面上一次只能放一种组合，可以看作是放一个产品的缓冲区，设置信号量empty初值为1，控制经销商往桌子上放原料；对于三个吸烟者的申请动作也要加以判断，用三个变量smoker1、smoker2、smoker3，初值为false，当为true时，表示申请资源，得到资源后置为false。四个进程循环往复，并发执行。经销商进程：吸烟者1进程： 吸烟者2进程： 吸烟者3进程：1、a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点(或b点)的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量为工具，对ab段实现正确管理以保证行驶安全。读者写着问题的变形。我们设置3个信号量S1、S2和Sab，分别用于从a点进入的车互斥访问共享变量ab（用于记录当前ab段上由a点进入的车辆的数量），从b点进入的车互斥访问共享变量ba（用于记录当前ab段上由b点进入的车辆的数量）和a、b点的车辆互斥进入ab段。3个信号量的初值分别为1、1和1，两个共享变量ab和ba的初值分别为0、0。 Semaphore S1=1,S2=1,Sab=1; int ab=ba=0;void Pab () while(1) wait(S1); if(ab=0) wait(Sab); ab=ab+1; signal(S1); 车辆从a点驶向b点; wait(S1); ab=ab-1; if(ab=0) signal(Sab); signal(S1); void Pba () 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可以将从输入设备上读入的数存放到缓冲器中。若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。同时规定：进程R必须等缓冲区中的数被取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器的数只能打印一次；W1和W2都不能从空缓冲中取数。写出这三个并发进程能正确工作的程序。信号量：customers表示正在等待复印的顾客数量（不包括正在复印的顾客）operator记录正在等候顾客的操作员数，只有1和0mutex用于对waiting的访问; 变量：waiting表示等待的顾客数量。它实际上是customers的一个副本。之所以使用waiting是因为无法读取信号量的当前值。semaphore customers=0,operator=0,mutex=1;waiting=0；process operator( )/操作员进程 while(1) wait(customers); /等待顾客到来 复印； signal(operator); /通知顾客已经完成复印 process cusotmeri( )/顾客进程i wait(mutex); if(waiting5) waiting+; signal(customers); signal(mutex); wait(operator); wait(mutex); waiting-; signal(mutex); elsesignal(mutex); 离开复印室； main( )cobegin operator( ); customeri( ); 设有两个生产者进程A、B和一个销售者进程C，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售；销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库，也不允许边入库边出库；而且要求生产和消费A产品和B产品的件数都满足以下关系：-nA的件数B的件数m，其中n、m是正整数。分析：生产者A、B和消费者之间不能同时将产品入库和出库，故仓库是一个临界资源。生产的A、B产品必须满足：-nA的件数B的件数m，如练习5中，同样的方法管理，分别使用了信号量SAB和SBA；仓库的管理只要求出入库互斥，由于仓库无限大入库只需操作互斥就可以完成，出库要考虑有无产品，SA对应于仓库中的A产品量，SB对应于仓库中的B产品量；销售要满足：-nA的件数B的件数m，用difference表示A的件数B的件数，即difference= A的件数B的件数;difference=-n的时候，不能取产品B，只能取A；difference=m的时候，不能取产品A，只能取B；-ndifferencem，即可以取产品A也可以取产品B；答：为了互斥地入库和出库，需为仓库设置一初值为1的互斥信号量mutex；为了使生产的产品件数满足-nA的件数B的件数m，须设置两个同步的信号量，其中SAB表示当前允许A生产的产品数量，其初值为m，SBA表示当前允许B生产的产品数量，其初值为n；另外，还需设置一个整数difference表示所销售的A、B产品数量之差，而为了同步生产者和销售者并使销售的A、B产品的件数-nA的件数B的件数m，还需要设置三个资源信号量，其中S对应于仓库中的总的产品量，SA对应于仓库中的A产品量，SB对应于仓库中的B产品量，它们的初值都为0.Semaphore SAB=m,SBA=n,S=0,SA=0,SB=0,mutex=1;process A( ) while(1)/生产产品，-nA的件数B的件数m，方法同第4题wait(SAB);Produce a product A;signal(SBA);/入库操作，满足出入库操作互斥即可wait(mutex);add the product A to the storehouse;signal(mutex);signal(SA); /入库产品A一件，所以给SA增值signal(S); /入库产品一件，所以给S增值，S是仓库中全部产品的数量 process B( ) while(1)/生产产品，-nA的件数B的件数m，方法同第4题wait(SBA);Produce a product B;signal(SAB);/入库操作，满足出入库操作互斥即可wait(mutex);add the product A to the storehouse;signal(mutex);signal(SB); /入库产品A一件，所以给SA增值signal(S); /入库产品一件，所以给S增值，S是仓库中全部产品的数量 process C( ) while(1) wait(S); /首先检查有无产品，无产品阻塞，有产品，下面操作将会取走一件产品，所以S减1 if(difference=-n) wait(SA); / difference=m) wait(SB); / difference=m时只能取B产品一件，无B产品则需阻塞 /出库操作，满足出入库操作互斥wait(mutex); take a product B from storehouse; signal(mutex); difference-; /取B产品一件，difference- else /-ndifferencem，即可以取产品A也可以取产品B，随意取一件产品出来，之后再根据取得产品是A还是B进行处理 /出库操作，满足出入库操作互斥wait(mutex); take a product A 或B from storehouse; signal(mutex); if（product_type=A） /取的是产品A，则信号量SA减1，