几乎无锁的生产者消费者

Question

我有一个生产者和消费者问题需要稍微修改一下来解决——有许多并行生产者，但在一个并行线程中只有一个消费者。当生产者在缓冲区中没有位置时，它就直接忽略元素(不等待消费者)。我写了一些C伪代码:

struct Element
{
   ULONG content;
   volatile LONG bNew;
}
ULONG max_count = 10;
Element buffer* = calloc(max_count, sizeof(Element));
volatile LONG producer_idx = 0;
LONG consumer_idx = 0;
EVENT NotEmpty;
BOOLEAN produce(ULONG content)
{
  LONG idx = InterlockedIncrement(&consumer_idx) % max_count;
  if(buffer[idx].bNew)
    return FALSE;
  buffer[idx].content = content;
  buffer[idx].bNew = TRUE;
  SetEvent(NotEmpty);
  return TRUE;
}
void consume_thread()
{
  while(TRUE)
  {
    Wait(NotEmpty);
    while(buffer[consumer_idx].bNew)
    {
      ULONG content = buffer[consumer_idx].content;
      InterlockedExchange(&buffer[consumer_idx].bNew, FALSE);
      //Simple mechanism for preventing producer_idx overflow
      LONG tmp = producer_idx;
      InterlockedCompareExchange(&producer_idx, tmp%maxcount, tmp);
      consumer_idx = (consumer_idx+1)%max_count;
      doSth(content);
    }
  }
}

我不能100%肯定这段代码是正确的。你能看到可能出现的问题吗?或者这段代码可以用更好的方式编写?

Answer 1

不要使用全局变量来实现您的目标，特别是在多线程应用程序中!!用信号量代替，不要用Lock，而是用TryLock。如果TryLock失败，则意味着没有空间容纳另一个元素，因此可以跳过它。

你可以在这里找到一些关于WinAPI中信号量的内容，因为你可能会使用它:http://msdn.microsoft.com/en-us/library/windows/desktop/ms686946 (v = vs.85) . aspx
http://msdn.microsoft.com/en-us/library/windows/desktop/ms687032 (v = vs.85) . aspx

您可以通过将0作为超时传递给WaitForSingleObject函数来实现TryLock功能。

Answer 2

请阅读:http://en.wikipedia.org/wiki/Memory_barrier

C和c++标准不处理多线程(或多线程)处理器)，因此，volatile的有用性取决于编译器和硬件。虽然易失性保证易失性读和易失性写将按照中指定的顺序进行源代码，编译器可以生成代码(或者CPU可以重新排序执行)，使易失性读或写被重新排序关于非易失性的读或写，从而限制了它的可用作线程间标志或互斥锁。而且，事实并非如此保证易失性读取和写入将在相同的顺序由其他处理器由于缓存，缓存一致性协议和轻松的内存排序，意味着易失性变量本身可能不均匀作为线程间标志或互斥体。

所以在一般情况下，volatile对C语言不起作用。但它可以为某些特定的编译器/硬件和其他语言(例如Java 5)工作。

参见函数调用是内存屏障吗?