Атомная меновая стоимость по результату сравнения - PullRequest
Новая
       40

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

6 голосов
/ 18 августа 2011

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

if (a > b)
  b = a

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

РЕДАКТИРОВАТЬ: и местный.

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

Спасибо!

Ответы [ 4 ]

8 голосов
/ 18 августа 2011

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

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

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

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

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

4 голосов
/ 18 августа 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;
}
0 голосов
/ 20 августа 2018

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

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

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

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

Если a > b == false, то после любой повторной попытки оно не будет trueb только увеличивается) и обмен может быть пропущен, поскольку 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 - таким образом, «свободный» в названии.Это также не сработает, если вам нужно сообщить только последнее из серии тесно сгруппированных a s - что можно назвать "debouncing" , связанной, но отличной проблемой.

0 голосов
/ 18 августа 2011

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

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

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

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

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

lock (lockObject)
{
   if (a > b)
   {
      b = a
   }
}
...