Almost lockless producer consumer

Question

I have producer consumer problem to solve with slight modification - there are many parallel producers but only one consumer in one parallel thread. When producer has no place in buffer then it simply ignore element (without waiting on consumer). I have writtent some C pseudocode:

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);
    }
  }
}

I am no 100% sure that this code is correct. Can you see any problems that could occur? Or maybe this code could be written in better way?

score 0 · Answer 1 · answered Dec 27 '11 at 11:08

0

Don't use global variable to accomplish your goal, especially in multithreaded application!!! Use Semaphore instead and don't do Lock but TryLock instead. If TryLock fails it means there's no room for another element, so you can skip it.

Here you can find something to read about semaphores in WinAPI because you would probably use it: 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

You can achieve TryLock functionality by passing 0 as timeout to WaitForSingleObject function.

answered Dec 27 '11 at 11:08

SOReader

5,697
5
31
53

I am using global variables and atomic operations to perform lockless synchronization. This is for performance reasons. – rnd Dec 27 '11 at 11:10
Well... actually you only have the increment safe. You still have the buffer[i].bNew dirty reads. In my opinion using single semaphore is a better idea instead of assigning producers to a single place index of an array – SOReader Dec 27 '11 at 12:16

score 0 · Answer 2 · edited May 23 '17 at 12:11

Please, read this: http://en.wikipedia.org/wiki/Memory_barrier

The C and C++ standards do not address multiple threads (or multiple processors), and as such, the usefulness of volatile depends on the compiler and hardware. Although volatile guarantees that the volatile reads and volatile writes will happen in the exact order specified in the source code, the compiler may generate code (or the CPU may re-order execution) such that a volatile read or write is reordered with regard to non-volatile reads or writes, thus limiting its usefulness as an inter-thread flag or mutex. Moreover, it is not guaranteed that volatile reads and writes will be seen in the same order by other processors due to caching, cache coherence protocol and relaxed memory ordering, meaning volatile variables alone may not even work as inter-thread flags or mutexes.

So in common case just volatile won't work for C. But it could work for some specific compilers/hardware and other languages (Java 5, for example).

See also Is function call a memory barrier?

First of all Interlocked operations will put memory barrier. The second issue is that I am compiling it on x86 where memory barrier is not needed (e.g. MemoryBarrier has empty body) — rnd, Dec 27 '11 at 12:47
On x86 all updates are seen on other cores in order of writes. So volatile is enough to prevent reordering. But I think content field should also be volatile so probably this is my mistake. — rnd, Dec 27 '11 at 13:37

Almost lockless producer consumer

2 Answers2