Практически беззамковый производитель-потребитель

У меня есть проблема производителя-потребителя, которую нужно решить с небольшой модификацией - есть много параллельных производителей, но только один потребитель в одном параллельном потоке. Когда у производителя нет места в буфере, он просто игнорирует элемент (не дожидаясь потребителя). Я написал некоторый псевдокод 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%, что этот код правильный. Видите ли вы какие-либо проблемы, которые могут возникнуть? Или, может быть, этот код можно было бы написать лучше?


thread-safety producer-consumer lockless
person rnd    schedule 27.12.2011    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Не используйте глобальную переменную для достижения своей цели, особенно в многопоточном приложении!!! Вместо этого используйте Semaphore и не делайте 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

Вы можете добиться функциональности TryLock, передав 0 в качестве времени ожидания функции WaitForSingleObject.

person SOReader    schedule 27.12.2011
comment
Я использую глобальные переменные и атомарные операции для выполнения синхронизации без блокировки. Это из соображений производительности. - person rnd; 27.12.2011
comment
Ну... на самом деле у вас есть только безопасное приращение. У вас все еще есть буфер[i].bNew грязных чтений. На мой взгляд, использование одного семафора является лучшей идеей вместо того, чтобы назначать производителей одному индексу места массива. - person SOReader; 27.12.2011

arrow_upward
0
arrow_downward

Пожалуйста, прочитайте это: http://en.wikipedia.org/wiki/Memory_barrier

Стандарты C и C++ не касаются нескольких потоков (или нескольких процессоров), поэтому полезность volatile зависит от компилятора и аппаратного обеспечения. Хотя volatile гарантирует, что операции чтения и записи volatile будут выполняться в точном порядке, указанном в исходном коде, компилятор может сгенерировать код (или ЦП может изменить порядок выполнения) так, что порядок чтения или записи volatile изменится с учетом -volatile читает или записывает, что ограничивает его полезность в качестве межпотокового флага или мьютекса. Более того, не гарантируется, что операции чтения и записи энергозависимых данных будут восприниматься другими процессорами в том же порядке из-за кэширования, протокола когерентности кэша и ослабленного порядка памяти, что означает, что переменные volatile могут даже не работать как межпоточные флаги или мьютексы.

Таким образом, в общем случае просто volatile не будет работать для C. Но это может работать для некоторых конкретных компиляторов/оборудования и других языков (например, Java 5).

См. также Является ли вызов функции барьером памяти?

person Vadzim    schedule 27.12.2011
comment
Прежде всего, блокированные операции поставят барьер памяти. Вторая проблема заключается в том, что я компилирую его на x86, где барьер памяти не нужен (например, MemoryBarrier имеет пустое тело) - person rnd; 27.12.2011
comment
А как насчет многоядерных кэшей? - person Vadzim; 27.12.2011
comment
На x86 все обновления видны на других ядрах в порядке записи. Таким образом, volatile достаточно, чтобы предотвратить изменение порядка. Но я думаю, что поле содержимого также должно быть изменчивым, так что, вероятно, это моя ошибка. - person rnd; 27.12.2011