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

Question

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

Мой текущий код выглядит следующим образом и предполагает 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 других потока, пытающихся заблокировать спин-блокировку один раз в несколько дней.

Answer 1

Вот мне и интересно

* Is it correct?

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

* Is it optimal?

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

• Я бы ожидал пустую петлю при сбое, когда вы не пытаетесь получить доступ к слову блокировки.

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

• у вас нет инструкции pause(), которую вы обычно помещаете перед циклом очистки.

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

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

* on compare and swap

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

Интересно, правильная ли следующая реализация 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");
}

Answer 5

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

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

Answer 6

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

Answer 7

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

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

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

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

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

Answer 8

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

      void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) yield(-1) ;
}

Answer 9

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

Answer 10

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

Answer 11

В конкретном случае 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 использует), но я не знаю, есть ли разница в производительности.