Спин-блокировка

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

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

Физическая реализация

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

Пример реализации спинлока на ассемблере x86:

    mov eax, spinlock_address
    mov ebx, SPINLOCK_BUSY

wait_cycle:
    xchg [eax], ebx  ; xchg - единственная инструкция, являющаяся атомарной без префикса lock
    cmp ebx, SPINLOCK_FREE
    jnz wait_cycle

    ; < критическая секция захвачена данным потоком, здесь идёт работа с разделяемым ресурсом >

    mov eax, spinlock_address
    mov ebx, SPINLOCK_FREE
    xchg [eax], ebx  ; используется xchg для атомарного изменения
    ; последние 3 инструкции лучше заменить на mov [spinlock_address], SPINLOCK_FREE -
    ; это увеличит скорость за счёт отсутствия лишней блокировки шины, а mov и так выполнится атомарно
    ; (но только если адрес spinlock_address выровнен по границе двойного слова)

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

Также используются т. н. queued spinlocks — «спинлоки с очередью». В них вместо присвоения 0 или 1 в атомарную переменную используется атомарное добавление структуры на голову списка, при том, что голова списка есть атомарная переменная типа «указатель».

Полезные свойства queued spinlockов:

• гарантия порядка предоставления в порядке запроса, гарантия от «голоданий»
• в цикле опроса каждый процессор опрашивает свою локальную переменную
• ровно 1 атомарная операция при захвате и ровно 1 при освобождении

Спинлоки применяются для синхронизации небольших участков кода, когда использование более сложных механизмов неоправданно или невозможно. Реализация примитивов синхронизации и диспетчера потоков обязательно требует блокировок, защищающих списки потоков, готовых к исполнению, и списки потоков, ожидающих на объектах. Такая блокировка может быть только спинлоком ввиду её очень низкого уровня. Таким образом, спинлок есть низший примитив синхронизации, на котором основана реализация всех остальных.

Версии Windows от Windows 7 включительно используют парадигму lock-free data structures для реализации диспетчера/планировщика. Тем самым, они избавлены от единственного глобального спинлока KiDispatcherLock, одного из самых высоконагруженных в ядре ОС.

Специфика многопроцессорных и однопроцессорных конфигураций

Бытует распространённое мнение о том, что в пользовательских приложениях, работающих под управлением многозадачных ОС, использование спинлоков недопустимо, так как ожидание освобождения спинлока приводит к активному ожиданию в цикле, впустую расходующему вычислительные ресурсы процессора, а для синхронизации пользовательских программ должны применяться высокоуровневые примитивы, которые предполагают пассивное ожидание — если данная нить не может продолжить выполнение, то она отдаёт управление ОС, а не крутится в цикле ожидания спинлока (который потенциально может быть бесконечным). На самом деле данное утверждение является справедливым на 100 % только для однопроцессорных систем. Во многих случаях применение спинлоков в SMP-конфигурациях ведёт к повышению эффективности в случае, если опрос и захват спинлока оказываются быстрее, чем вызов захвата мьютекса в ядре.

Главным критерием здесь является contention — «жёсткость» соревнования за ресурс. Слабонагруженный ресурс, не являющийся популярным местом исполнения, ведёт себя иначе, чем сильно нагруженный, захватываемый и освобождаемый очень часто.

Кроме того, в той же Windows есть разновидности мьютексов (например, общеизвестная CRITICAL_SECTION/EnterCriticalSection/LeaveCriticalSection, или же её синоним в ядре ОС — FAST_MUTEX/ExAcquireFastMutex/ExReleaseFastMutex), которые сначала работают как spinlock, используя опрос значения в памяти, и только потом, по истечении большого количества опросов, переходят в ядро к блокирующему ожиданию. Такие объекты сочетают лучшие качества спинлоков (минимальная цена захвата) и мьютексов (отсутствие растраты ресурса процессора на опрос).

Применение спинлоков

Случаи, когда применение в пространстве пользователя спинлоков даёт ощутимый эффект:

• Внутри участка защищаемого кода находится несколько связанных переменных, время модификации которых может быть в сотни и даже тысячи раз меньше, чем переключение контекста процессором, что является особенно дорогой операцией, особенно на современных системах.
• Блокировка не участков кода, а данных (с каждой структурой данных, которая должна атомарно изменяться как единое целое, связан спинлок, её защищающий)
• Оптимизация кода, когда необходимо уменьшить нагрузку, возникающую за счёт слишком частого переключения контекста

Однако, использование «быстрых мьютексов», таких, как CRITICAL_SECTION в Win32, делает все вышеперечисленное ненужным в пространстве пользователя.

Случаи, когда применение спинлоков не оправдано и является пустой тратой процессорных ресурсов:

• Длительные блокирующие операции внутри защищаемого участка кода (дисковый и сетевой ввод-вывод может выполняться очень долго по процессорным меркам)
• Однопроцессорные конфигурации — весь остаток кванта времени процессор проводит в холостом цикле.

Проблемы спинлоков и методы их решения

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

В Pentium 4 и последующих моделях процессоров Intel введена специальная ассемблерная команда для вставки внутрь цикла pause (опкод 0xf3 0x90, аналогичный команде rep nop для совместимости со старыми процессорами) предназначение которой — проинструктировать процессор, что данный цикл является циклом ожидания, и позволяет процессору с поддержкой нескольких потоков на одном ядре перейти к следующему потоку.

Версии Windows от Windows 7 оптимизированы на работу в качестве «гостя» в виртуальной машине, и в них вместо pause в случаях, когда ОС исполняется как гость, используется специальный вызов «уведомить гипервизор о том, что мы в цикле ожидания».

Альтернативы спинлоков

• Спинлоки служат для обеспечения монопольного доступа потока к защищаемой структуре данных. При этом не делается различия ни между самими потоками, ни между производимыми операциями. Однако, зачастую в реальных приложениях потоки можно разделить на «читающие» и «пишущие». Для данного несимметричного случая более целесообразно применять блокировки чтения-записи. Структура может одновременно использоваться неограниченным количеством потоков в режиме «только чтение», вместе с тем давая защиту целостности данных при приходе «пишущего» потока.
• Существуют также алгоритмы без блокировок, основанные на атомарном детектировании коллизий. Они оптимизированы под оптимистичный случай, при котором вся проверка на коллизию сводится к одной атомарной ассемблерной операции (Compare And Swap, на x86-архитектуре — команда cmpxchg)

Прочие модификации спинлоков

Спинлок с автоматическим наращиванием до захвата полноценного мьютекса после истечения какого-то количества оборотов цикла применяется, например, в критических секциях Windows для оптимизации, заключающейся в отсутствии обращений к мьютексу при отсутствии соревнования за ресурс.

См. также

• Dispatch level
• DPC
• IRQL

Литература

• М. Руссинович, Д. Соломон. 1 // Внутреннее устройство Microsoft Windows. — 6-е изд.. — СПб.: Питер, 2013. — С. 218—222. — 800 с. — ("Мастер-класс"). — ISBN 978-5-459-01730-4.
• Уолтер Они. Использование Microsoft Windows Driver Model. — 2-е изд.. — СПб.: Питер, 2007. — С. 173-178. — 764 с. — ISBN 978-5-91180-057-4.
• Эндрю С. Таненбаум. Современные операционные системы = Modern Operating Systems. — 3-е издание. — СПб: Питер : Издательский дом «Питер», 2011. — С. 165–170. — 1117 с. — (Классика computer science). — ISBN 9785459007572.