Как предотвратить состояние гонки БЕЗ использования блокировок на C++?

Question

Как предотвратить состояние гонки БЕЗ блокировки или использования мьютексов/семафоров в C++? Я имею дело с вложенным циклом, в котором я буду заходящим значение в массиве:

for (int i = 0; i < m; ++i) 
    for (int j = 0; j < n; ++j) 
    for (int k = 0; k < o; ++k) 
     array[k] += foo(...); 

Более или менее, я хочу иметь дело с этим, так что я могу обеспечить различные темы, работаю одновременно не записывать в массив [k] одновременно. Любые предложения о том, как подойти к этому?

Редактировать: Я бегу на машине Linux, и мне также нужно использовать компилятор Intel. Я буду использовать «icc» вместо «gcc» для компиляции кода.

Answer 1

Предполагая, что окна и что array содержит элементы типа LONG вы могли бы сделать что-то вроде:

for (int i = 0; i < m; ++i) 
    for (int j = 0; j < n; ++j) 
     for (int k = 0; k < o; ++k) { 
      LONG val = foo(...); 
      InterlockedAdd(&array[k], val); 
     } 

Если вы не работаете в Windows, платформы могут иметь подобный набор API. Пока ваша платформа имеет тип API InterlockedCompareExchange(), вы можете написать свою собственную версию InterlockedAdd().

Что-то вроде следующей (оговорки - непроверенное):

int InterlockedAdd(int volatile* pDest, int operand) 
{ 
     int curval = *pDest; 
     int oldval; 

     do { 
      oldval = curval; 
      curval = InterlockedCompareExchange(pDest, oldval + operand, oldval); 
     } while (curval != oldval); 

     return oldval+operand; 
} 

Насколько я знаю, Повысьте имеет лишь ограниченную поддержку атомные/сблокированы операции, по-видимому, достаточно только поддерживать атомную манипуляцию ссылочных графов. Я не думаю, что поддержка взаимосвязанных операций в Boost больше, чем детализация реализации (в настоящее время я имею дело с несколько более старой версией Boost, поэтому вполне возможно, что это уже не так).

Есть некоторые портативные библиотеки, которые поддерживают атомное сравнения и обмена и другие атомарные операции, как документированных части интерфейса:

• Apache АТР: http://apr.apache.org/docs/apr/1.4/group__apr__atomic.html
• бойким: http://library.gnome.org/devel/glib/stable/glib-Atomic-Operations.html
• Intel темы Строительные блоки: http://www.threadingbuildingblocks.org/

Также обратите внимание, что C++ 0x будет поддерживать атомные операции, такие как compa re/exchange - я не уверен, какой уровень поддержки находится в текущих компиляторах C++ (он не выглядит как VS 2010).

Answer 2

Предполагая, что массив содержит целые числа, используйте gcc atomic builtins. __sync_fetch_and_add должен сделать трюк.

Answer 3

Для этого конкретного контура поверните его наизнанку. Положите k снаружи, то вы можете поместить k=0 в другую тему, чем k=1 и так далее.

Пока foo() не зависит от массива [k], где k! = Это ток k, тогда вы золотой.

Answer 4

Разделите самую внутреннюю петлю между нитями. Thread T1 обрабатывает индексы в диапазоне [0, L), потоки T2 обрабатывают индексы в диапазоне [L, 2L) и т. Д. L = o/n, где n - количество потоков. Это предполагает, что вызов foo() не использует другие местоположения, которые могут быть вычислены одновременно.

EDIT: использование взаимосвязанных операций, как предложили другие, даст правильный результат, но это может сильно ухудшить производительность. (Если внутренний цикл короток, многие потоки будут конкурировать за несколько мест памяти, что эффективно сериализует вашу программу.)

Answer 5

Самый простой способ (хотя и не самый эффективный!) - обернуть цикл в «критический» раздел.

См. Здесь Wikipedia. Это ограничит цикл кода одним потоком в любой момент времени.

Answer 6

То, как вы этого хотите, не может быть сделано! (см. комментарий sbi)

Вы можете использовать общую память, но все равно будут блокировки.
Вы также можете использовать только один поток для записи и чтения в массив. Если вы считаете, что для этого проще настроить правильный протокол, продолжайте.

Во всяком случае, уже есть хорошие решения с использованием замков (прямо или косвенно). Просто выберите один :)

Answer 7

с использованием ВЗАИМОСВЯЗАННЫХ операций, а других предположили, даст правильного результата, но это может ухудшить производительность плохо. (Если внутренний цикл короток, многие темы будут конкурируют за несколько ячеек памяти, , которые будут эффективно сериализующей программой .) Ссылка | флаг

Не правда, мой друг. На самом деле блокированные операции превосходят все виды блокировки. Точнее: все объекты синхронизации (критические разделы, мьютексы, события и т. Д.), Безусловно, реализованы с точки зрения взаимосвязанных операций. Фактически блокированные операции являются единственными инструкциями процессора, которые могут гарантировать согласованность синхронизации. Это просто невозможно реализовать объект синхронизации без использования взаимосвязанных операций вообще.

Другой вопрос: scope блокировки. Вероятно, вы хотели сказать, что область синхронизации (реализованная либо с объектами синхронизации, либо непосредственно с заблокированными операциями) внутри внутреннего цикла может привести к ухудшению производительности, поскольку она выполняется много раз.

Ну, это правда. Но, с другой стороны, вы блокируете только то, что вам нужно, только на необходимую продолжительность. Следовательно, вы предотвращаете потенциальные столкновения синхронизации.