Атомарно обменивать значение на результат сравнения

У меня есть очень простая операция, которую нужно выполнить атомарно:

if (a > b)
  b = a

где a и b - целые числа

EDIT: и a является локальным.

Есть ли быстрый способ сделать это на С#? Я хотел бы избежать блокировки вручную, если это возможно. Я просмотрел Interlocked.CompareExchange, но, насколько я понимаю, это только тесты на равенство.

Спасибо!


person dckrooney    schedule 17.08.2011    source источник
comment
Обязательная старая новая ссылка: blogs.msdn.com/ б/oldnewthing/archive/2004/09/15/229915.aspx   -  person vcsjones    schedule 18.08.2011
comment
@vcsjones: Интересная статья, спасибо за это. Однако в моей ситуации b записывается только в вышеуказанных обстоятельствах. Я думаю, что подход типа Interlocked здесь уместен.   -  person dckrooney    schedule 18.08.2011
comment
@dcrooney - Interlocked может быть уместным, и вы увидите, что решение, используемое для его решения (CompareExchange в цикле), является ответом Хеннинга Макхолма.   -  person vcsjones    schedule 18.08.2011
comment
аналогично заголовку stackoverflow.com/questions/3731088/   -  person Brian Gideon    schedule 18.08.2011
comment
@Brian Gideon: выглядит не совсем похоже, вот у нас есть одна локальная переменная без доступа к ней нескольких потоков.   -  person sll    schedule 18.08.2011


Ответы (4)


Канонический способ - использовать блокировку сравнения-обмена в цикле:

int oldvalue, newvalue ;
do {
  oldvalue = b ; // you'll want to force this to be a volatile read somehow
  if( a > oldvalue )
    newvalue = a ;
  else
    break ;
} while( interlocked replace oldvalue with newvalue in b does NOT succeed );

(Псевдокод, потому что я не утруждаю себя поиском правильного способа выполнения заблокированного обмена на С#).

Как видите, если у вас нет первостепенных проблем с эффективностью, использование простых старых мьютексов намного проще и читабельнее.

Изменить: предполагается, что a является локальной переменной или, по крайней мере, не подлежит асинхронной записи. И a, и b могут быть изменены за вашей спиной, тогда не существует безблокировочного способа выполнить это обновление атомарно. (Спасибо silev за указание на это).

person hmakholm left over Monica    schedule 17.08.2011
comment
Но это будет ручная блокировка и много чего с петлями, излишество, как вы думаете? - person sll; 18.08.2011
comment
Я понял, что избегать блокировки вручную означает, что он не хотел использовать ключевое слово lock или явные мьютексы. Если это граничное условие (и я не одобряю его, как должно быть ясно), то использование цикла неизбежно, по крайней мере, с моделью блокировки x86. - person hmakholm left over Monica; 18.08.2011
comment
Только представьте себе THREAD#1: прочитать значение 'a', скажем, 10 после строки if( a › oldvalue ) ==› переключатель потока ==› THREAD#2: присвоить -1 для 'a' ==› переключатель потока ==› THREAD#1: попытка присвоить 'a' для newValue == результат будет -1, но изначально THREAD#1 читал 10 - person sll; 18.08.2011
comment
@sllev: выполнение нескольких итераций цикла (даже 100) быстрее, чем ожидание в критической секции или даже просто попытка войти в критическую секцию. - person vcsjones; 18.08.2011
comment
@vcsjones: абсолютно (я понимаю, что скрывается за блокировкой()), но есть ли другой вариант? - person sll; 18.08.2011
comment
Спасибо большое. Я понимаю, что проще реализовать простой оператор блокировки, но в этой ситуации главной проблемой является эффективность. Похоже, это путь. :) - person dckrooney; 18.08.2011
comment
Может ли кто-нибудь описать шаг за шагом, как оба утверждения if( a › oldvalue ) newvalue = a ; будет выполняться в одиночной атомарной операции без состояния гонки? - person sll; 18.08.2011
comment
@ Хеннинг Махольм: я считаю, что есть много предположений, так что это не будет настоящей атомной операцией, этого по своей природе НЕ МОЖЕТ БЫТЬ, и в результате решение не ясно, и более того - 2 минуса для меня, черт :) - person sll; 18.08.2011
comment
@sllev - В целом это не атомарная операция, мы выполняем операцию, получаем значение; и атомарно сравнить старые/новые значения с их оригиналами. Если они изменились; затем позвольте циклу повторить попытку. Если они не изменились, замените вычисленное значение как атомарную операцию. Вы не заботитесь о том, чтобы вся операция была атомарной; все, о чем вы заботитесь, это атомарная проверка, изменилось ли что-либо после выполнения ваших вычислений, и обменяйте его, если нет. - person vcsjones; 18.08.2011
comment
@ Хеннинг Махольм, sllev: a местный. Обновлен исходный пост, чтобы отразить это. - person dckrooney; 18.08.2011
comment
@vcsjones: OP сказал, что это одна операция, а вы перевели ее в цикл и сказали, что это атомарно, я не согласен с таким подходом. Атомарное среднее - это то, которое всегда наблюдается как выполненное или не выполненное, но никогда не выполненное наполовину, в вашем случае многое может произойти во время выполнения цикла, даже EPIC Fail. ИСХОДНЫЙ ВОПРОС - очень простая операция - 1 операция, атомарно - в любом случае не следует делить на несколько шагов..... поэтому я бы остался, что это не атомарная операция в целом - person sll; 18.08.2011
comment
@vcsjones: Насколько я понимаю, и в последний раз, когда я смотрел, критический раздел Windows является спин-блокировкой с ограниченным количеством циклов. Это должно быть почти так же быстро, как выполнение этой операции сравнения-обмена, если конкуренция не настолько высока, что операция должна выполняться в ядре. - person Zan Lynx; 18.08.2011
comment
@Zan, но если мы говорим о микрооптимизации, обновление с помощью спин-блокировки повлечет за собой три записи в разделяемую память даже на быстром пути: один раз для получения блокировки, один раз для обновления b и еще один раз для снятия блокировки. При прочих равных это увеличивает нагрузку на протокол когерентности кэша. (Не то чтобы я уверен, какие протоколы используются современным оборудованием). - person hmakholm left over Monica; 18.08.2011

Хеннинг прав. Я предоставлю подробности, поскольку они относятся к C#. Шаблон может быть обобщен с помощью следующей функции.

public static T InterlockedOperation<T>(ref T location, T operand)
{
  T initial, computed;
  do
  {
    initial = location;
    computed = op(initial, operand); // where op is replaced with a specific implementation
  } 
  while (Interlocked.CompareExchange(ref location, computed, initial) != initial);
  return computed;
}

В вашем конкретном случае мы можем определить такую ​​функцию InterlockedGreaterThanExchange.

public static int InterlockedGreaterThanExchange(ref int location, int value)
{
  int initial, computed;
  do
  {
    initial = location;
    computed = value > initial ? value : initial;
  } 
  while (Interlocked.CompareExchange(ref location, computed, initial) != initial);
  return computed;
}
person Brian Gideon    schedule 18.08.2011
comment
MemoryBarrier требуется только в многопроцессорных системах со слабым порядком памяти (например, в системе, использующей несколько процессоров Intel Itanium). В большинстве случаев инструкция блокировки C#, инструкция Visual Basic SyncLock или класс Monitor обеспечивают более простые способы синхронизации данных. msdn.microsoft.com/en-us/library/ - person sll; 18.08.2011
comment
Итак, вы считаете, что это было бы проще и быстрее, чем lock() ? - person sll; 18.08.2011
comment
Барьер памяти определенно нужен. Это вызов Thread.MemoryBarrier, который можно опустить, потому что Interlocked.CompareExchange уже генерирует вызов, который предотвращает удаление чтения location (путем оптимизации) за пределы цикла. Вы правы, аппаратное обеспечение x86 имеет жесткие гарантии, но CLI (согласно спецификации ECMA) имеет слабые гарантии, что означает, что оптимизация может происходить на уровне JIT. Вы должны кодировать более слабую модель. Вот почему Thread.MemoryBarrier и тому подобное существуют в первую очередь. - person Brian Gideon; 18.08.2011
comment
Я думаю, что старый добрый lock был бы проще, и именно поэтому я проголосовал за ваш ответ, но цикл с операцией CAS, вероятно, будет быстрее, особенно в системах с высокой степенью параллельности и многими ядрами. - person Brian Gideon; 18.08.2011

Не существует такой атомарной операции, которая выполняла бы как сравнение, так и присваивание по-настоящему атомарно. В C# настоящими атомарными операциями могут быть операции Interlocked, такие как CompareExchenge() и Exchange(), для обмена двумя целочисленными значениями (32-битные для 32-битной архитектуры и 64-битные для 64-битной архитектуры процессора).

Очевидно, что простое присваивание a = b представляет собой две операции — чтение и запись. Таким образом, нет возможности выполнить сравнение + присваивание за один атомарный шаг... Возможно ли это на любом другом языке/архитектуре, я имею в виду настоящий атомарный? ;)

РЕДАКТИРОВАТЬ: в исходном вопросе не указано, что 'a' является локальной переменной... э-э-э, такое небольшое исправление... в любом случае я оставлю свой ответ как есть, потому что я верю в природу истинных атомарных операций, а не в какие-то «трюки», которые претендуют на атомарность

Итак, подведем итог:

  • мы не можем делать такие операции как одну атомарную операцию
  • только один способ - синхронизировать его с помощью механизма блокировки (при условии, что в исходном вопросе не указано, что a является локальным, поэтому и a, и b потенциально могут быть доступны другому потоку
object lockObject = new object();
int a = 10;
int b = 5;

lock (lockObject)
{
   if (a > b)
   {
      b = a
   }
}
person sll    schedule 17.08.2011
comment
Я нейтрально отношусь к этому ответу, поскольку он правильный, и, хотя он самоуверен, он дает неплохую причину для этого. Но я ненавижу видеть, как он получает отрицательные голоса, поэтому голосую за 0. - person Marc L.; 09.08.2018

Это пара оптимизированных рецептов, которые я придумал после прочтения других ответов. Не имеет прямого отношения к вопросу, но добавляет сюда, так как именно здесь приземлились похожие поиски. Пытался сохранить это значение a > b или a >= b, чтобы оно соответствовало исходному вопросу. И сделать их общими, чтобы не отклонять описания от других связанных проблем. Оба могут быть обернуты в методы.

Оптимизация - монотонная b

Если это единственная операция, которая выполняется для b или b в противном случае монотонно возрастает, вы можете оптимизировать блокировку присваивания и повторных попыток, где a > b == false:

int initial;
do 
{
  initial = b;
}
while ((a > initial) && Interlocked.CompareExchange(ref b, a, initial) != initial);

Если a > b == false, то после повторной попытки не будет true (b только увеличивается), и обмен можно пропустить, так как b это не повлияет.

Связанная с оптимизацией проблема: слабое регулирование

Действие signal() следует вызывать один раз каждый раз, когда локальная переменная a (например, отсчет системного времени) увеличивается на некоторую константу threshold >= 1 с момента последнего вызова signal(). Здесь b — это пороговый заполнитель по сравнению с a и устанавливается равным a + threshold, если a >= b. Только победившая нить должна вызывать signal().

var initial = b;
if ((a > initial) && Interlocked.CompareExchange(ref b, a + threshold, initial) == initial)
{
  signal();
}

Здесь b снова является монотонным, но теперь мы можем полностью отказаться от цикла повторных попыток, так как мы хотим только знать, выиграл ли локальный поток гонку с другими потоками, соблюдая threshold. Этот метод эффективно блокирует сигнализацию любого другого потока в пределах определенного порога.

Предостережения по регулированию

Этот не сработает, если вам нужен строгий дроссель, то есть наименьшее a, где a >= b, поэтому в заголовке свободная. Это также не сработает, если вам нужно сообщить только о последнем из серии тесно сгруппированных as — то, что можно назвать debouncing, родственная, но отдельная проблема.

person Marc L.    schedule 20.08.2018