В программной инженерии спин -блокировка — это блокировка , которая заставляет поток, пытающийся ее получить, просто ждать в цикле («спин»), постоянно проверяя, доступна ли блокировка. Поскольку поток остается активным, но не выполняет полезную задачу, использование такой блокировки является своего рода занятым ожиданием . После получения спин-блокировки обычно удерживаются до тех пор, пока не будут явно сняты, хотя в некоторых реализациях они могут автоматически сниматься, если ожидающий поток (тот, который удерживает блокировку) блокируется или «переходит в спящий режим».
Поскольку они избегают накладных расходов из-за перепланирования процессов операционной системы или переключения контекста , спин-блокировки эффективны, если потоки, вероятно, будут блокироваться только на короткие периоды. По этой причине ядра операционных систем часто используют спин-блокировки. Однако спин-блокировки становятся расточительными, если удерживаются в течение более длительного времени, так как они могут помешать выполнению других потоков и требуют перепланирования. Чем дольше поток удерживает блокировку, тем больше риск того, что поток будет прерван планировщиком ОС во время удержания блокировки. Если это произойдет, другие потоки останутся «вращающимися» (повторно пытаясь получить блокировку), в то время как поток, удерживающий блокировку, не продвигается к ее освобождению. Результатом является неопределенная задержка, пока поток, удерживающий блокировку, не сможет завершить и освободить ее. Это особенно верно в однопроцессорной системе, где каждый ожидающий поток с одинаковым приоритетом, вероятно, будет тратить свой квант (выделенное время, в течение которого поток может выполняться) на вращение, пока поток, удерживающий блокировку, окончательно не завершится.
Корректная реализация спин-блокировок является сложной задачей, поскольку программисты должны учитывать возможность одновременного доступа к блокировке, что может вызвать состояние гонки . Как правило, такая реализация возможна только с помощью специальных инструкций языка ассемблера , таких как атомарные (т. е. непрерываемые) операции проверки и установки , и не может быть легко реализована в языках программирования, не поддерживающих по-настоящему атомарные операции. [1] На архитектурах без таких операций или если требуется реализация языка высокого уровня, может использоваться неатомарный алгоритм блокировки, например алгоритм Петерсона . Однако такая реализация может потребовать больше памяти , чем спин-блокировка, быть медленнее, чтобы обеспечить прогресс после разблокировки, и может быть нереализуема на языке высокого уровня, если разрешено выполнение вне очереди .
Следующий пример использует язык ассемблера x86 для реализации спин-блокировки. Он будет работать на любом процессоре, совместимом с Intel 80386 .
; Синтаксис Intelзаблокировано: ; Переменная блокировки. 1 = заблокировано, 0 = разблокировано. dd 0 spin_lock: mov eax , 1 ; Установить регистр EAX в 1. xchg eax , [ locked ] ; Атомарно поменять местами регистр EAX с ; переменной lock. ; Это всегда будет сохранять 1 в lock, оставляя ; предыдущее значение в регистре EAX. test eax , eax ; Проверит EAX с самим собой. Помимо прочего, это ; установит нулевой флаг процессора, если EAX равен 0. ; Если EAX равен 0, то блокировка была разблокирована и ; мы просто заблокировали ее. ; В противном случае EAX равен 1, и мы не получили блокировку. jnz spin_lock ; Вернуться к инструкции MOV, если нулевой флаг ; не установлен; блокировка была ранее заблокирована, и поэтому ; нам нужно вращать ее, пока она не станет разблокированной. ret ; Блокировка получена, вернуться к вызывающей ; функции. spin_unlock: xor eax , eax ; Установить регистр EAX в 0. xchg eax , [ locked ] ; Атомарно поменять местами регистр EAX с ; переменной блокировки. ret ; Блокировка снята. Простая реализация выше работает на всех процессорах с архитектурой x86. Однако возможен ряд оптимизаций производительности:
В более поздних реализациях архитектуры x86 spin_unlock может безопасно использовать разблокированный MOV вместо более медленного заблокированного XCHG. Это связано с тонкими правилами упорядочения памяти , которые поддерживают это, хотя MOV не является полным барьером памяти . Однако некоторые процессоры (некоторые процессоры Cyrix , некоторые версии Intel Pentium Pro (из-за ошибок) и более ранние системы Pentium и i486 SMP ) будут делать что-то неправильно, и данные, защищенные блокировкой, могут быть повреждены. В большинстве архитектур, отличных от x86, необходимо использовать явный барьер памяти или атомарные инструкции (как в примере). В некоторых системах, таких как IA-64 , существуют специальные инструкции «разблокировки», которые обеспечивают необходимый порядок памяти.
Чтобы уменьшить трафик шины между ЦП , код, пытающийся получить блокировку, должен зацикливать чтение, не пытаясь ничего записать, пока не прочитает измененное значение. Из-за протоколов кэширования MESI это приводит к тому, что строка кэша для блокировки становится «общей»; тогда, как ни странно, трафик шины отсутствует , пока ЦП ожидает блокировки. Эта оптимизация эффективна на всех архитектурах ЦП, имеющих кэш на ЦП, поскольку MESI широко распространен. На процессорах с технологией Hyper-Threading пауза с rep nopдает дополнительную производительность, намекая ядру, что оно может работать в другом потоке, пока блокировка вращается в ожидании. [2]
Transactional Synchronization Extensions и другие наборы инструкций аппаратной транзакционной памяти служат для замены блокировок в большинстве случаев. Хотя блокировки по-прежнему требуются в качестве резерва, они могут значительно повысить производительность, заставляя процессор обрабатывать целые блоки атомарных операций. Эта функция встроена в некоторые реализации мьютексов, например, в glibc . Hardware Lock Elision (HLE) в x86 — это ослабленная, но обратно совместимая версия TSE, и мы можем использовать ее здесь для блокировки без потери совместимости. В этом конкретном случае процессор может выбрать не блокировать, пока два потока фактически не конфликтуют друг с другом. [3]
Более простая версия теста может использовать cmpxchgинструкцию x86 или __sync_bool_compare_and_swapвстроенную во многие компиляторы Unix.
После применения оптимизаций пример будет выглядеть так:
; На языке C: while (!__sync_bool_compare_and_swap(&locked, 0, 1)) while (locked) __builtin_ia32_pause(); spin_lock: mov ecx , 1 ; Установить регистр ECX в 1. retry: xor eax , eax ; Обнулить EAX, так как cmpxchg сравнивается с EAX. XACQUIRE lock cmpxchg [ locked ], ecx ; Атомарно решить: если locked равен нулю, записать в него ECX. ; XACQUIRE намекает процессору, что мы получаем блокировку. je out ; Если мы заблокировали его (старое значение равно EAX: 0), возврат. pause: mov eax , [ locked ] ; Прочитать заблокированное в EAX. test eax , eax ; Выполнить проверку на ноль, как и раньше. jz retry ; Если равен нулю, можно повторить попытку. rep nop ; Сообщаем процессору, что мы ждем в спин-цикле, чтобы он мог ; работать в другом потоке сейчас. Также обозначается как "пауза". jmp pause ; Продолжаем проверку-паузу. out: ret ; Все сделано. spin_unlock: XRELEASE mov [ locked ], 0 ; Предполагая, что правила упорядочивания памяти применяются, освободить переменную блокировки с подсказкой «снятие блокировки». ret ; Блокировка снята. На любой многопроцессорной системе, использующей протокол конкуренции MESI , такая блокировка «тест-тест-установка» (TTAS) работает намного лучше, чем простой подход «тест-установка» (TAS). [4]
При большом количестве процессоров добавление случайной экспоненциальной задержки перед повторной проверкой блокировки работает даже лучше, чем TTAS. [4] [5]
Несколько многоядерных процессоров имеют инструкцию "энергосберегающей спин-блокировки", которая переводит процессор в спящий режим, а затем пробуждает его на следующем цикле после освобождения блокировки. Спин-блокировка, использующая такие инструкции, более эффективна и потребляет меньше энергии, чем спин-блокировки с циклом отката или без него. [6]
Основной недостаток спин-блокировки в том, что, ожидая получения блокировки, она тратит время, которое можно было бы продуктивно потратить в другом месте. Есть два способа избежать этого:
Большинство операционных систем (включая Solaris , Mac OS X и FreeBSD ) используют гибридный подход, называемый «адаптивным мьютексом ». Идея заключается в использовании спин-блокировки при попытке доступа к ресурсу, заблокированному текущим потоком, и в переходе в режим сна, если поток в данный момент не выполняется. (Последнее всегда имеет место в однопроцессорных системах.) [8]
OpenBSD попыталась заменить спин-блокировки на блокировки тикетов , которые обеспечивали поведение «первым пришел — первым вышел» , однако это привело к большей загрузке ЦП в ядре и более крупным приложениям, таким как Firefox , которые стали работать намного медленнее. [9] [10]