操作系统 作业答案.doc

第九题 设有两个生产者进程A、B和一个销售者进程C，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售；销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库，也不允许边入库边出库；而且要求生产和消费A产品和B产品的件数都满足以下关系：-n≤A的件数－B的件数≤m，其中n、m是正整数。

分析：生产者A、B和消费者之间不能同时将产品入库和出库，故仓库是一个临界资源。
生产的A、B产品必须满足：-n≤A的件数－B的件数≤m，如练习5中，同样的方法管理，分别使用了信号量SAB和SBA；
仓库的管理只要求出入库互斥，由于仓库无限大入库只需操作互斥就可以完成，出库要考虑有无产品，SA对应于仓库中的A产品量，SB对应于仓库中的B产品量；
销售要满足：-n≤A的件数－B的件数≤m，用difference表示A的件数－B的件数，即difference= A的件数－B的件数;difference==-n的时候，不能取产品B，只能取A；difference==m的时候，不能取产品A，只能取B；-n<difference<m，即可以取产品A也可以取产品B；

答：为了互斥地入库和出库，需为仓库设置一初值为1的互斥信号量mutex；为了使生产的产品件数满足-n≤A的件数－B的件数≤m，须设置两个同步的信号量，其中SAB表示当前允许A生产的产品数量，其初值为m，SBA表示当前允许B生产的产品数量，其初值为n；另外，还需设置一个整数difference表示所销售的A、B产品数量之差，而为了同步生产者和销售者并使销售的A、B产品的件数-n≤A的件数－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)
{//生产产品，-n≤A的件数－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)
{//生产产品，-n≤A的件数－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<=-n时只能取A产品一件，无A产品则需阻塞
//出库操作，满足出入库操作互斥
wait(mutex);
take a product A from storehouse;
signal(mutex);
difference++; //取A产品一件，difference++
}
else if(difference>=m)
{ wait(SB); // difference>=m时只能取B产品一件，无B产品则需阻塞
//出库操作，满足出入库操作互斥
wait(mutex);
take a product B from storehouse;
signal(mutex);
difference--; //取B产品一件，difference--
}
else
{ //-n<difference<m，即可以取产品A也可以取产品B，随意取一件产品出来，之后再根据取得产品是A还是B进行处理
//出库操作，满足出入库操作互斥
wait(mutex);
take a product A 或B from storehouse;
signal(mutex);
if（product_type==A）
{//取的是产品A，则信号量SA减1，这里不可能发生没有A产品，进程C需要阻塞的情况
wait(SA);
difference++;//取A产品一件，difference++
}
else
{//取的是产品B，则信号量SB减1，这里不可能发生没有B产品，进程C需要阻塞的情况
wait(SB);
difference--;//取B产品一件，difference--
}
}
Sell the product;
}
}
main()
{
cobegin{
A();
B();
C();
}
}

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

　　经销商进程：

　　吸烟者1进程： 

　　吸烟者2进程： 

　　吸烟者3进程：

第一题44. a、b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当a、b之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点(或b点)的车辆可以进入ab段，但不能从a点和b点同时驶入；当某方向在ab段驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。
现定义两个计数器CountE和CountW分别记录东行和西行车辆进程数。用PV操作进行管理时的三个信号量为S、SE、SW，程序结构如下：
begin
S, SE, SW: semaphore;
CountE, CountW: Integer;
CountE := ____(1)_0___; CountW := ____(2)_0___;
S := ____(3)_1___; SE := ____(4)_1___; SW := ____(5)1____;

cobegin

5
Process EASTi (i=1, 2, 3, …)
begin
____(6)_P（SE）___;
if CountE = 0 then____(7)P（S）____;
CountE := CountE+1;
____(8)_V（SE）___;
pass(ab);
____(9)_P（SE）___;
CountE := CountE-1;
if CountE = 0 then ____(10)_V（S）___;
____(11)_V（SE）___;
end;
Process WESTj(j=1, 2, 3, …)
Begin
____(12)_P（SW）___;
if CountW = 0 then ____(13)_P（S）___;
CountW := CountW+1;
____(14)_V（SW）___;
pass(ba);
____(15)_P(SW)___;
CountW := CountW-1;
if CountW = 0 then ____(16)_V(S)___;
____(17)_V(SW)___;
end;

coend;
end;
44. (1) 0 (2) 0 (3) 1 (4) 1 (5) 1 (6) P(SE) (7) P(S) (8) V(SE) (9) P(SE) (10) V(S)
(11) V(SE) (12) P(SW) (13) P(S) (14) V(SW) (15) P(SW) (16) V(S) (17) V(SW)

3、如果有三个进程R、W1、W2共享一个缓冲器B，而B中每次只能存放一个数。当缓冲器中无数时，进程R可以将从输入设备上读入的数存放到缓冲器中。若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。同时规定：进程R必须等缓冲区中的数被取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器的数只能打印一次；W1和W2都不能从空缓冲中取数。写出这三个并发进程能正确工作的程序。
答：S为互斥信号量，用来对缓冲器的互斥使用；
SO和SE为资源信号量，SO表示是否允许进程W1打印；SE表示是否允许进程W2打印。
semaphore S=1,SO=SE=0;
buffer B;
process R（）
{ int x;
while(1)
{从输入设备上读一个数;
x=接收的数;
wait(S);
B=x;
if B=奇数 then signal(SO);
else signal(SE); }
}
process W1()
{ int y;
while(1)
{ wait(SO);
y=B;
signal(S);
打印y中数;}
}
process W2()
{ int z;
while(1)
{ wait(SE);
z=B;
signal(S);
打印z中数 ;}
}
main()
{cobegin
{ R();
W1();
W2();}
}