Атомный счетчик в gcc

Question

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

Как правильно реализовать атомарный счетчик в GCC?

т.е. я хочу счетчик, который работает от нуля до 4 и является потокобезопасным.

Я делал это(который далее обернут в класс, но не здесь)

static volatile int _count = 0;
const int limit = 4;

int get_count(){
  // Create a local copy of diskid
  int save_count = __sync_fetch_and_add(&_count, 1);
  if (save_count >= limit){
      __sync_fetch_and_and(&_count, 0); // Set it back to zero
  }
  return save_count;
}

Но он работает с 1 по 1, включительно от 1 до 4, затем приближается к нулю.
Должен идти от 0 до 3. ОбычноЯ бы сделал счетчик с оператором модов, но я не знаю, как это сделать безопасно.

Возможно, эта версия лучше.Можете ли вы увидеть какие-либо проблемы с ним или предложить лучшее решение.

int get_count(){
   // Create a local copy of diskid
   int save_count = _count;
   if (save_count >= limit){
      __sync_fetch_and_and(&_count, 0); // Set it back to zero
      return 0;
   }

   return save_count;
 }

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

Answer 1

Ваш код не является атомарным (а ваш второй get_count даже не увеличивает значение счетчика)!

Скажем, count - это 3 в начале, и два потока одновременно вызывают get_count.Один из них сначала выполнит свое атомарное добавление и увеличит count до 4. Если второй поток достаточно быстр, он может увеличить его до 5, прежде чем первый поток сбросит его до нуля.

Такжепри обработке циклического сброса вы сбрасываете count в 0, но не save_count.Это явно не то, что задумано.

Это проще всего, если limit является степенью 2. Никогда не делайте уменьшение самостоятельно, просто используйте

return (unsigned) __sync_fetch_and_add(&count, 1) % (unsigned) limit;

или альтернативно

return __sync_fetch_and_add(&count, 1) & (limit - 1);

Это делает только одну атомарную операцию за вызов, безопасно и очень дешево.Для общих пределов вы все равно можете использовать %, но это нарушит последовательность, если счетчик переполнится.Вы можете попробовать использовать 64-битное значение (если ваша платформа поддерживает 64-битную атомарность) и просто надеяться, что оно никогда не переполнится;Это плохая идея.Правильный способ сделать это - использовать атомарную операцию сравнения-обмена.Вы делаете это:

int old_count, new_count;
do {
  old_count = count;
  new_count = old_count + 1;
  if (new_count >= limit) new_count = 0; // or use %
} while (!__sync_bool_compare_and_swap(&count, old_count, new_count));

Этот подход обобщает более сложные последовательности и операции обновления.

Тем не менее, этот тип операции без блокировки сложно реализовать правильно, полагаясь на неопределенное поведение дляв некоторой степени (все текущие компиляторы понимают это правильно, но никакого стандарта C / C ++ до C ++ 0x на самом деле не имеет четко определенной модели памяти), и его легко сломать.Я рекомендую использовать простой мьютекс / блокировку, если вы не профилировали его и не обнаружили, что это узкое место.

Answer 2

Вам повезло, потому что диапазон, который вы хотите, вписывается ровно в 2 бита.

Простое решение: пусть изменчивая переменная будет считаться вечно. Но после прочтения используйте только самые младшие два бита (val & 3). Presto, атомный счетчик от 0-3.

Answer 3

У вас есть две проблемы.

__sync_fetch_and_add вернет предыдущее значение (т. Е. Перед добавлением одного).Таким образом, на этапе, когда _count становится 3, ваша локальная переменная save_count возвращается 2.Таким образом, вам на самом деле нужно увеличить _count до 4, прежде чем оно вернется в виде 3.

Но даже вдобавок к этому, вы специально ищете, чтобы оно было >= 4 прежде чем вы вернете его обратно к 0. Это просто вопрос использования неправильного предела, если вы только ищете, чтобы он достиг целых трех.

Answer 4

Невозможно создать что-либо атомарное в чистом C, даже с volatile.Тебе нужен асм.C1x будет иметь специальные атомарные типы, но до тех пор вы застряли с asm.