使用完整缓冲区的生产者-消费者算法

Question

我正在阅读 Galvin OS 关于生产者消费者问题的书，并浏览了这段代码。

\n\n

全局定义

\n\n

#define BUFFER_SIZE 10\ntypedef struct {\n    . . .\n} item;\n\nint in  = 0;\nint out = 0;\n

\n\n

制片人

\n\n

while (((in + 1) % BUFFER_SIZE) == out)\n    ; /* do nothing */\nbuffer[in] = next_produced;\nin = (in + 1) % BUFFER_SIZE ;\n

\n\n

消费者

\n\n

while (in == out)\n    ; /* do nothing */\nnext_consumed = buffer[out];\nout = (out + 1) % BUFFER_SIZE;\n

\n\n

这就是加尔文书中所说的：

\n\n

\n

此方案最多允许缓冲区中同时存在 BUFFER_SIZE \xe2\x88\x92 1 个项目。我们将其作为练习，让您提供一个解决方案，\n BUFFER_SIZE 项可以同时位于缓冲区中。

\n

\n\n

这就是我想出来的。它是否正确？

\n\n

制片人

\n\n

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

\n\n

消费者

\n\n

while (in == out)\n    ; /* do nothing */\nnext_consumed = buffer[out];\nout = (out + 1) % BUFFER_SIZE;\n

\n\n

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

\n

Answer 1

在原始代码段中，in == out它可能意味着缓冲区为空或已满。因此，为了避免这种歧义，原始代码不允许缓冲区已满，总是留下至少一个空项。

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

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

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

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

我们将其作为练习，让您提供完整的解决方案；）