Является ли моя реализация блокировки спина правильной и оптимальной?

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

Мой текущий код выглядит следующим образом и предполагает x86 и GCC:

volatile int exclusion = 0;

void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) {
        // Do nothing. This GCC builtin instruction
        // ensures memory barrier.
    }
}

void unlock() {
    __sync_synchronize(); // Memory barrier.
    exclusion = 0;
}

Итак, мне интересно:

Правильно ли этот код? Правильно ли он обеспечивает взаимное исключение?
Работает ли он на всех операционных системах x86?
Работает ли он и на x86_64? Во всех операционных системах?
Это оптимально?
- Я видел реализацию блокировки спина, используя команду сравнения и замены, но я не уверен, что лучше.
- В соответствии с документацией по атомной сборке GCC (http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html) также __sync_lock_release. Я не специалист по барьерам памяти, поэтому я не уверен, что для меня это использовать вместо __sync_synchronize.
- Я оптимизирую для случая, в котором нет конкуренции.

Меня не волнует спор. Может быть, 1, может быть, 2 других потока, пытающихся заблокировать блокировку спина один раз в несколько дней.

Ответ 1

Итак, мне интересно:

* Is it correct?

В упомянутом контексте я бы сказал "да".

* Is it optimal?

Это загруженный вопрос. Заново изобретая колесо, вы также изобретаете множество проблем, которые были решены другими реализациями.

Я ожидаю, что цикл отказов произойдет, если вы не пытаетесь получить доступ к заблокированному слову.
Использование полного барьера в разблокировке требует только семантики выпуска (поэтому вы должны использовать __sync_lock_release, так что вы получите st1.rel на itanium вместо mf или lwsync на powerpc,...). Если вы действительно заботитесь только о x86 или x86_64, типы барьеров, используемых здесь или нет, не имеют большого значения (но если вы хотите совершить переход на Intel Itanium для порта HP-IPF, то вам этого не захочется).
у вас нет инструкции pause(), которую вы обычно ставите перед циклом отходов.
когда есть утверждение, что вы хотите что-то, semop или даже немой сон в отчаянии. Если вам действительно нужна производительность, которую вы покупаете, то предложение futex, вероятно, является хорошим. Если вам нужна производительность, вы покупаете достаточно плохо, чтобы поддерживать этот код, вам нужно много исследований.

Обратите внимание, что был комментарий, в котором говорилось, что барьер выпуска не требуется. Это неверно даже на x86, поскольку барьер выпуска также служит инструкцией для компилятора, чтобы не перетасовывать другие обращения к памяти вокруг "барьера". Очень похоже на то, что вы получили бы, если бы использовали asm ( ":" память").

* on compare and swap

В x86 sync_lock_test_and_set будет отображаться в инструкции xchg, которая имеет предполагаемый префикс блокировки. Определенно самый компактный сгенерированный код (особенно если вы используете байт для слова "lock word" вместо int), но не менее корректно, чем если бы вы использовали LOCK CMPXCHG. Использование сравнения и подкачки может использоваться для алькантимов fancier (например, положить ненулевой указатель на метаданные для первого "официанта" в ловушку при ошибке).

Ответ 2

Выглядит хорошо. Btw, вот учебник, который более эффективен даже в рассматриваемом случае.

void lock(volatile int *exclusion)
{
    while (__sync_lock_test_and_set(exclusion, 1))
        while (*exclusion)
            ;
}

Ответ 3

В ответ на ваши вопросы:

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

Ответ 4

Если вы используете последнюю версию Linux, вы можете использовать futex - "быстрое пользовательское пространство" мьютекс ":

Правильно запрограммированная блокировка на основе futex не будет использовать системные вызовы, за исключением случаев, когда заблокирована блокировка

В неоспоримом случае, который вы пытаетесь оптимизировать для своей спин-блокировки, futex будет вести себя точно так же, как спин-блокировка, не требуя syscall ядра. Если блокировка оспаривается, ожидание происходит в ядре без ожидания ожидания.

Ответ 5

Я не могу прокомментировать правильность, но заголовок вашего вопроса поднял красный флаг, прежде чем я даже прочитал вопрос. Синхронизация примитивов чертовски трудно обеспечить правильность... если это вообще возможно, вам лучше использовать хорошо разработанную/поддерживаемую библиотеку, возможно pthreads или boost:: thread.

Ответ 6

Интересно, правильна ли следующая реализация CAS на x86_64. Это почти в два раза быстрее на моем ноутбуке i7 X920 (fedora 13 x86_64, gcc 4.4.5).

inline void lock(volatile int *locked) {
    while (__sync_val_compare_and_swap(locked, 0, 1));
    asm volatile("lfence" ::: "memory");
}
inline void unlock(volatile int *locked) {
    *locked=0;
    asm volatile("sfence" ::: "memory");
}

Ответ 7

Одним из улучшений является использование TATAS (test-and-test-and-set). Использование CAS-операций считается довольно дорогостоящим для процессора, поэтому лучше избегать их, если это возможно. Другое дело, убедитесь, что вы не будете страдать от инверсии приоритета (что, если поток с высоким приоритетом пытается получить блокировку, а поток с низким приоритетом пытается освободить блокировку? В Windows, например, эта проблема в конечном итоге будет решена планировщик с использованием повышения приоритета, но вы можете явно отказаться от своего временного фрагмента потока, если вам не удалось получить блокировку в течение последних 20 попыток (например..)

Ответ 8

Ваша процедура разблокировки не требует барьера памяти; присваивание исключению является атомарным, если оно выровнено по x86.

Ответ 9

В конкретном случае x86 (32/64) я не думаю, что вам нужен забор памяти вообще в коде разблокировки. x86 не выполняет никакого переупорядочения, за исключением того, что хранилища сначала помещаются в буфер хранилища, и поэтому их видимость может быть отложена для других потоков. И поток, который делает хранилище, а затем читает из той же переменной, будет считывать из своего буфера хранения, если он еще не был сброшен в память. Итак, все, что вам нужно, это инструкция asm, чтобы предотвратить переупорядочивание компилятора. Вы рискуете, что один поток удерживает блокировку немного дольше, чем необходимо, с точки зрения других потоков, но если вы не заботитесь о конкуренции, это не имеет значения. Фактически, pthread_spin_unlock реализуется так же, как в моей системе (linux x86_64).

Моя система также реализует pthread_spin_lock с помощью lock decl lockvar; jne spinloop; вместо использования xchg (что используется __sync_lock_test_and_set), но я не знаю, есть ли разница в производительности.

Ответ 10

Есть несколько неправильных предположений.

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

В многопроцессорной системе может произойти одно и то же, но задача может мигрировать с одного процессора на другой. Короче говоря, использование блокировки спина является правильным, если вы гарантируете, что ваши задачи будут выполняться на разных CPU.

Во-вторых, блокировка мьютекса IS быстро (так же быстро, как прямая блокировка), когда он разблокирован. Блокировка муфток (и разблокировка) медленная (очень медленная), только если мьютекс уже заблокирован.

Итак, в вашем случае я предлагаю использовать мьютексы.