生产者消费者算法使用满缓冲区

Question

我正在阅读 Galvin OS 关于生产者消费者问题的书，并通过这段代码来理解。

全局定义

#define BUFFER_SIZE 10
typedef struct {
    . . .
} item;

int in  = 0;
int out = 0;

制作人

while (((in + 1) % BUFFER_SIZE) == out)
    ; /* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE ;

消费者

while (in == out)
    ; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;

高尔文的书是这样写的：

This scheme allows at most BUFFER_SIZE − 1 items in the buffer at the same time. We leave it as an exercise for you to provide a solution in which BUFFER_SIZE items can be in the buffer at the same time.

这是我想到的。这是正确的吗？

制作人

buffer[in] = next_produced;  //JUST MOVED THIS LINE!
while (((in + 1) % BUFFER_SIZE ) == out)
    ; /* do nothing */
in = (in + 1) % BUFFER_SIZE;

消费者

while (in == out)
    ; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;

我认为这解决了问题，但这是否正确？还有其他更好的解决方案吗？

Answer 1

在原来的代码中，当in == out时，可能表示缓冲区为空或已满。所以为了避免这种歧义，原始代码不允许缓冲区满，总是至少留下一个空项。

我不确定您是否通过更改解决了这个问题：您将能够放置 BUFFER_SIZE 项，但您将无法使用它们。所以，你确实解决了它，但它无法正常运行。

基本上，要解决这个问题，您应该有一条额外的信息，这样您就可以区分空缓冲区和满缓冲区。有多种解决方案，最明显的是添加一个额外的标志。

最优雅的 IMO 是按原样使用 in 和 out 计数器，将它们包装起来仅用于访问缓冲区，因此：

当in == out -- 缓冲区为空
当abs(in - out) == BUFFER_SIZE -- 缓冲区已满
访问缓冲区我们应该使用buffer[in % BUFFER_SIZE]或buffer[out % BUFFER_SIZE]

我们将其作为练习留给您提供完整的解决方案 ;)

生产者消费者算法使用满缓冲区

Producer-consumer algorithm to use full buffer

c

algorithm

producer-consumer