(操作系统原理·第三章)生产者-消费者问题

时间:2022-07-24 14:26:00

生产者--消费者问题:

有n 个生产者和m 个消费者,连接在一个有k 个单位缓冲区的有界缓冲上,故又叫有界缓冲问题。其中,pi 和cj 都是并发进程,只要

缓冲区未满,生产者pi 生产的产品就可投入缓冲区;类似地,只要缓冲区不空,消费者进程cj 就可从缓冲区取走并消耗产品。

算法表述:

var k:integer;
type item:any;
buffer:array[0..k-1] of item;
in,out:integer:=0;
counter:integer:=0;
process producer
while (TRUE) /* 无限循环*/
produce an item in nextp; /* 生产一个产品*/
if (counter==k) sleep( ); /* 缓冲满时,生产者睡眠*/
buffer[in]:=nextp; /* 将一个产品放入缓冲区*/
in:=(in+1) mod k; /* 指针推进*/
counter:=counter+1; /* 缓冲内产品数加1*/
if (counter==1) wakeup( consumer); /* 缓冲为空了,加进一件产品并唤醒消费者*/
process consumer
while (TRUE) /* 无限循环*/
if (counter==0) sleep ( ); /* 缓冲区空,消费者睡眠*/
nextc:=buffer[out]; /* 取一个产品到nextc*/
out:=(out+1) mod k; /* 指针推进*/
counter:=counter-1; /* 取走一个产品,计数减1*/
if (counter==k-1) wakeup( producer); /* 缓冲满了,取走一件产品并唤醒生产者*/
consume thr item in nextc; /* 消耗产品*/

其中,假如一般的高级语言都有sleep( )和wakeup( )这样的系统调用。从上面的程序可以看出,算法是正确的,两组进程顺序执行结果也正确。但若并发执行,就会出现错误结果,出错的根子在于进程之间共享了变量counter,对counter 的访问未加限制。生产者和消费者进程对counter 的交替执行会使其结果不唯一。例如,counter 当前值为8,如果生产者生产了一件产品,投入缓冲区,拟做counter 加1 操作。同时消费者获取一个产品消费,拟做counter 减1 操作。假如两者交替执行加或减1 操作,取决于它们的进行速度,counter 的值可能是9,也可能是7,正确值应为8。

更为严重的是生产者和消费者进程的交替执行会导致进程永远等待,造成系统死锁。假定消费者读取counter 发现它为0。此时调度程序暂停消费者让生产者运行,生产者加入一个产品,将counter 加1,现在counter 等于1 了。它想当然地推想由于counter刚刚为0,所以,此时消费者一定在睡眠,于是生产者调用wakeup 来唤醒消费者。不幸的是,消费者还未去睡觉,唤醒信号被丢失掉。当消费者下次运行时,因已测到counter为0,于是去睡眠。这样生产者迟早会填满缓冲区,然后,去睡觉,形成了进程都永远处于睡眠状态。
出现不正确结果不是因为并发进程共享了缓冲区,而是因为它们访问缓冲区的速率不匹配,或者说pi,cj 的相对速度不协调,需要调整并发进程的进行速度。并发进程间的这种制约关系称进程同步,交互的并发进程之间通过交换信号或消息来达到调整相互速率,保证进程协调运行的目的。


解决方法:用记录型信号量实现互斥

Var A : ARRAY[1..m] of integer;
mutex : semaphore;
mutex:= 1;
cobegin
process Pi
var Xi:integer;
begin
L1:
按旅客定票要求找到A[j];
P(mutex);
Xi := A[j];
if Xi>=1
then begin
Xi:=Xi-1;A[j]:=Xi;
V(mutex);{输出一张票};
end;
else begin
V(mutex);{输出“票已售完”};
end;
goto L1;
end;
coend.


Var A : ARRAY[1..m] of integer;
s : ARRAY[1..m] of semaphore;
s[j] := 1;
cobegin
process Pi
var Xi:integer;
begin
L1:
按旅客定票要求找到A[j];
P(s[j]);
Xi := A[j];
if Xi>=1
then begin
Xi:=Xi-1;A[j]:=Xi;
V(s[j]);{输出一张票};
end;
else begin
V(s[j]);{输出“票已售完”};
end;
goto L1;
end;
coend.

左面的程序引入一个信号量mutex,用于管理票源数据,其初值为l。假设进程Tl首先调用P 操作,则P 操作将把信号量mutex 减l,T1 进入临界区;此时,若进程T2也想进入临界区而调用P 操作,那么,P 操作便会阻塞T2 并使它等待mutex。当T1离开临界区时,它调用V 操作,V 操作将唤醒等待mutex 的进程T2;于是T2 就可进入临界区执行。事实上,当进程T1 和T2 只有同时买一个航班的机票时才会发生与时间有关的错误,因此,临界区应该是与A[j]有关的,所以,可以对左面的程序进行改进,引入一组信号量s[j],从而,得到了右面的程序,不难看出,它提高了进程的并发程度。

要提醒注意的是:任何粗心地使用P、V 操作会违反临界区的管理要求。如忽略了else 部分的V 操作,将致使进程在临界区中判到条件不成立时无法退出临界区,而违反了对临界区的管理要求。