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

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

0 голосов
/ 26 апреля 2010

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

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» для компиляции кода.

Ответы [ 7 ]

4 голосов
/ 26 апреля 2010

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

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

3 голосов
/ 26 апреля 2010

Предполагая, что окна и что 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 - это больше, чем просто детали реализации (в настоящее время я имею дело с несколько более старой версией Boost, поэтому возможно, что это уже не так).

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

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

2 голосов
/ 26 апреля 2010

Так, как вы хотите, это невозможно! (см. комментарий sbi)

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

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

2 голосов
/ 26 апреля 2010

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

0 голосов
/ 26 апреля 2010

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

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

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

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

0 голосов
/ 26 апреля 2010

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

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

0 голосов
/ 26 апреля 2010

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

РЕДАКТИРОВАТЬ: использование взаимосвязанных операций, как предлагали другие, даст правильный результат, но может сильно ухудшить производительность. (Если внутренний цикл короткий, многие потоки будут конкурировать за небольшое количество областей памяти, что будет эффективно сериализовать вашу программу.)

...