Спинлок

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

Поскольку спин-блокировки позволяют избежать накладных расходов, связанных с операционной системы перепланированием процессов или переключением контекста , они эффективны, если потоки могут блокироваться только на короткие периоды времени. По этой причине ядра операционных систем часто используют спин-блокировки. Однако спин-блокировки становятся расточительными, если они удерживаются в течение длительного времени, поскольку они могут помешать запуску других потоков и потребовать перепланирования. Чем дольше поток удерживает блокировку, тем выше риск того, что поток будет прерван планировщиком ОС во время удержания блокировки. Если это произойдет, другие потоки останутся «вращающимися» (неоднократно пытаясь получить блокировку), в то время как поток, удерживающий блокировку, не продвигается к ее освобождению. Результатом является неопределенная отсрочка до тех пор, пока поток, удерживающий блокировку, не завершит работу и не освободит ее. Это особенно верно в однопроцессорной системе, где каждый ожидающий поток с одинаковым приоритетом, вероятно, будет тратить свой квант (выделенное время, в течение которого поток может работать) на вращение до тех пор, пока поток, удерживающий блокировку, наконец не завершится.

Правильная реализация спин-блокировок является сложной задачей, поскольку программисты должны учитывать возможность одновременного доступа к блокировке, что может вызвать состояние гонки . Как правило, такая реализация возможна только с помощью специальных инструкций языка ассемблера , таких как атомарные (т.е. непрерывные) операции проверки и установки , и не может быть легко реализована на языках программирования, не поддерживающих истинно атомарные операции. ^[1] В архитектурах без таких операций или если требуется реализация языка высокого уровня, может использоваться неатомарный алгоритм блокировки, например алгоритм Петерсона . Однако такая реализация может потребовать больше памяти , чем спин-блокировка, быть медленнее, чтобы обеспечить прогресс после разблокировки, и может быть нереализуема на языке высокого уровня, если выполнение вне порядка разрешено .

Пример реализации

В следующем примере для реализации спин-блокировки используется язык ассемблера x86. Он будет работать на любом процессоре, совместимом с Intel 80386 .

; Intel syntax

locked:                      ; The lock variable. 1 = locked, 0 = unlocked.
     dd      0

spin_lock:
     mov     eax, 1          ; Set the EAX register to 1.
     xchg    eax, [locked]   ; Atomically swap the EAX register with
                             ;  the lock variable.
                             ; This will always store 1 to the lock, leaving
                             ;  the previous value in the EAX register.
     test    eax, eax        ; Test EAX with itself. Among other things, this will
                             ;  set the processor's Zero Flag if EAX is 0.
                             ; If EAX is 0, then the lock was unlocked and
                             ;  we just locked it.
                             ; Otherwise, EAX is 1 and we didn't acquire the lock.
     jnz     spin_lock       ; Jump back to the MOV instruction if the Zero Flag is
                             ;  not set; the lock was previously locked, and so
                             ; we need to spin until it becomes unlocked.
     ret                     ; The lock has been acquired, return to the calling
                             ;  function.

spin_unlock:
     xor     eax, eax        ; Set the EAX register to 0.
     xchg    eax, [locked]   ; Atomically swap the EAX register with
                             ;  the lock variable.
     ret                     ; The lock has been released.

Значительные оптимизации

Приведенная выше простая реализация работает на всех процессорах, использующих архитектуру x86. Однако возможен ряд оптимизаций производительности:

В более поздних реализациях архитектуры x86 spin_unlock может безопасно использовать разблокированный MOV вместо более медленного заблокированного XCHG. Это связано с тонкими правилами упорядочения памяти , которые поддерживают это, хотя MOV не является полным барьером памяти . Однако некоторые процессоры (некоторые процессоры Cyrix , некоторые версии Intel Pentium Pro (из-за ошибок) и более ранние системы Pentium и i486 SMP ) будут работать неправильно, и данные, защищенные блокировкой, могут быть повреждены. В большинстве архитектур, отличных от x86, необходимо использовать явный барьер памяти или атомарные инструкции (как в примере). В некоторых системах, таких как IA-64 , существуют специальные инструкции «разблокировки», которые обеспечивают необходимое упорядочивание памяти.

между процессорами Чтобы уменьшить трафик по шине , код, пытающийся получить блокировку, должен зацикливать чтение, не пытаясь ничего записать, пока не будет прочитано измененное значение. Из-за протоколов кэширования MESI строка кэша для блокировки становится «Общей»; тогда трафик по шине практически отсутствует, пока ЦП ожидает блокировки. Эта оптимизация эффективна для всех архитектур ЦП, в которых имеется кэш для каждого ЦП, поскольку MESI широко распространен. На процессорах с поддержкой Hyper-Threading приостановка с помощью rep nop дает дополнительную производительность, намекая ядру, что оно может работать с другим потоком, пока блокировка ожидает вращения. ^[2]

Расширения транзакционной синхронизации и другие наборы инструкций аппаратной транзакционной памяти в большинстве случаев служат для замены блокировок. Хотя блокировки по-прежнему необходимы в качестве запасного варианта, они могут значительно повысить производительность, заставляя процессор обрабатывать целые блоки атомарных операций. Эта функция встроена в некоторые реализации мьютексов, например в glibc . Аппаратная блокировка (HLE) в x86 — это ослабленная, но обратно совместимая версия TSE, и мы можем использовать ее здесь для блокировки без потери совместимости. В этом конкретном случае процессор может отказаться от блокировки до тех пор, пока два потока фактически не конфликтуют друг с другом. ^[3]

В более простой версии теста можно использовать cmpxchg инструкция на x86 или __sync_bool_compare_and_swap встроен во многие компиляторы Unix.

С применением оптимизации образец будет выглядеть так:

; In C: while (!__sync_bool_compare_and_swap(&locked, 0, 1)) while (locked) __builtin_ia32_pause();
spin_lock:
    mov     ecx, 1             ; Set the ECX register to 1.
retry:
    xor     eax, eax           ; Zero out EAX, because cmpxchg compares against EAX.
    XACQUIRE lock cmpxchg [locked], ecx
                               ; atomically decide: if locked is zero, write ECX to it.
                               ;  XACQUIRE hints to the processor that we are acquiring a lock.
    je      out                ; If we locked it (old value equal to EAX: 0), return.
pause:
    mov     eax, [locked]      ; Read locked into EAX.
    test    eax, eax           ; Perform the zero-test as before.
    jz      retry              ; If it's zero, we can retry.
    rep nop                    ; Tell the CPU that we are waiting in a spinloop, so it can
                               ;  work on the other thread now. Also written as the "pause".
    jmp     pause              ; Keep check-pausing.
out:
    ret                        ; All done.

spin_unlock:
    XRELEASE mov [locked], 0   ; Assuming the memory ordering rules apply, release the 
                               ;  lock variable with a "lock release" hint.
    ret                        ; The lock has been released.

В любой многопроцессорной системе, использующей конфликтный протокол MESI , такая блокировка «проверка-проверка-установка» (TTAS) работает намного лучше, чем простая блокировка «проверка-установка» (TAS). ^[4]

Благодаря большому количеству процессоров добавление случайной экспоненциальной задержки перед повторной проверкой блокировки работает даже лучше, чем TTAS. ^[4]^[5]

Некоторые многоядерные процессоры имеют команду «спин-блокировки с учетом энергопотребления», которая переводит процессор в спящий режим, а затем пробуждает его в следующем цикле после снятия блокировки. Спин-блокировка с использованием таких инструкций более эффективна и использует меньше энергии, чем спин-блокировка с петлей отсрочки или без нее. ^[6]

Альтернативы

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

Не приобретайте замок. Во многих ситуациях можно спроектировать структуры данных, которые не требуют блокировки , например, используя данные для каждого потока или каждого процессора и отключив прерывания .
Во время ожидания переключитесь на другой поток. Обычно это предполагает присоединение текущего потока к очереди потоков, ожидающих блокировки, с последующим переключением на другой поток, готовый выполнить некоторую полезную работу. Преимущество этой схемы также состоит в том, что она гарантирует, что нехватка ресурсов не произойдет до тех пор, пока все потоки в конечном итоге откажутся от полученных блокировок, и можно будет принять решения по планированию о том, какой поток должен выполняться первым. Спин-блокировки, которые никогда не влекут за собой переключение и которые можно использовать в операционных системах реального времени , иногда называют необработанными спин-блокировками . ^[7]

Большинство операционных систем (включая Solaris , Mac OS X и FreeBSD ) используют гибридный подход, называемый «адаптивный мьютекс ». Идея состоит в том, чтобы использовать спин-блокировку при попытке доступа к ресурсу, заблокированному текущим потоком, и переходить в режим сна, если поток в данный момент не работает. (Последнее всегда имеет место в однопроцессорных системах.) ^[8]

OpenBSD попыталась заменить спин-блокировки блокировками билетов , которые обеспечивали принцип «первым пришел — первым обслужен» , однако это привело к увеличению использования ЦП в ядре, а более крупные приложения, такие как Firefox , стали намного медленнее. ^[9]^[10]

См. также

Ссылки

^ Зильбершац, Авраам; Гэлвин, Питер Б. (1994). Концепции операционной системы (Четвертое изд.). Аддисон-Уэсли. стр. 176–179. ISBN 0-201-59292-4 .
^ «gcc — спин-блокировка x86 с использованием cmpxchg» . Переполнение стека .
^ «Новые технологии в архитектуре рук» (PDF) . Архивировано (PDF) из оригинала 2 апреля 2019 г. Проверено 26 сентября 2019 г.
^ Jump up to: ^а ^б Морис Херлихи и Нир Шавит. «Искусство многопроцессорного программирования». «Спин-локировки и конфликты» .
^ «Boost.Fiber Tuning: Экспоненциальное замедление» .
^ Джон Гудакр и Эндрю Н. Слосс. «Параллелизм и архитектура набора команд ARM» . п. 47.
^ Джонатан Корбет (9 декабря 2009 г.). «Именование Spinlock разрешено» . LWN.net . Архивировано из оригинала 7 мая 2013 года . Проверено 14 мая 2013 г.
^ Зильбершац, Авраам; Гэлвин, Питер Б. (1994). Концепции операционной системы (Четвертое изд.). Аддисон-Уэсли. п. 198. ИСБН 0-201-59292-4 .
^ Тед Унангст (01 июня 2013 г.). "src/lib/librthread/rthread.c — Версия 1.71" . Архивировано из оригинала 27 февраля 2021 г. Проверено 25 января 2022 г.
^ Тед Унангст (06 мая 2016 г.). «Комментарий Теду к блокировке в WebKit — Lobsters» .

Внешние ссылки

Документация pthread_spin_lock из Базовых спецификаций открытой группы, выпуск 6, IEEE Std 1003.1, издание 2004 г.
Разнообразие реализаций спин-блокировок из Concurrency Kit
Статья « Спин-блокировки на уровне пользователя — потоки, процессы и IPC », Герт Боддарт
Статья Пример Spin Lock на Java
Статья « Производительность альтернатив спин-блокировки для мультипроцессоров с общей памятью » Томаса Э. Андерсона
Статья « Алгоритмы масштабируемой синхронизации на мультипроцессорах с общей памятью » Джона М. Меллора-Крамми и Майкла Л. Скотта . Эта статья получила премию Дейкстры в области распределенных вычислений в 2006 году .
Блокировка Spin-Wait от Джеффри Рихтера
Справочник классов SpinLock в Австрии C++
Блокированный доступ к переменным (Windows)
Операционные системы: три простых элемента (Глава: Блокировки)

[1] Зильбершац, Авраам; Гэлвин, Питер Б. (1994). Концепции операционной системы (Четвертое изд.). Аддисон-Уэсли. стр. 176–179. ISBN 0-201-59292-4 .

[2] «gcc — спин-блокировка x86 с использованием cmpxchg» . Переполнение стека .

[3] «Новые технологии в архитектуре рук» (PDF) . Архивировано (PDF) из оригинала 2 апреля 2019 г. Проверено 26 сентября 2019 г.

[herlihy-4] Jump up to: ^а ^б Морис Херлихи и Нир Шавит. «Искусство многопроцессорного программирования». «Спин-локировки и конфликты» .

[5] «Boost.Fiber Tuning: Экспоненциальное замедление» .

[6] Джон Гудакр и Эндрю Н. Слосс. «Параллелизм и архитектура набора команд ARM» . п. 47.

[7] Джонатан Корбет (9 декабря 2009 г.). «Именование Spinlock разрешено» . LWN.net . Архивировано из оригинала 7 мая 2013 года . Проверено 14 мая 2013 г.

[8] Зильбершац, Авраам; Гэлвин, Питер Б. (1994). Концепции операционной системы (Четвертое изд.). Аддисон-Уэсли. п. 198. ИСБН 0-201-59292-4 .

[9] Тед Унангст (01 июня 2013 г.). "src/lib/librthread/rthread.c — Версия 1.71" . Архивировано из оригинала 27 февраля 2021 г. Проверено 25 января 2022 г.

[10] Тед Унангст (06 мая 2016 г.). «Комментарий Теду к блокировке в WebKit — Lobsters» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]