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

StackOverflow https://stackoverflow.com/questions/1383363

Вопрос

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

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

Это было полезно?

Решение

Поэтому мне интересно:

* Is it correct?

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

* Is it optimal?

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

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

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

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

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

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

* on compare and swap

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

Другие советы

Мне кажется, все в порядке.Кстати, вот учебник реализация, которая более эффективна даже в спорном случае.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top