stringtranslate.com

Спинлок

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

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

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

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

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

; Синтаксис Intelзаблокировано: ; Переменная блокировки. 1 = заблокировано, 0 = разблокировано. дд 0   spin_lock: mov eax , 1 ; Установите для регистра EAX значение 1. xchg eax , [ locked ] ; Атомарно поменять регистр EAX с помощью ; переменная блокировки. ; Это всегда будет сохранять 1 в блокировке, оставляя ; предыдущее значение в регистре EAX. тест eax , eax ; Проверьте EAX на себе. Среди прочего, это будет ; установить нулевой флаг процессора, если EAX равен 0. ; Если EAX равен 0, то замок был разблокирован и ; мы просто заперли его. ; В противном случае EAX равен 1, и мы не получили блокировку. jnz spin_lock ; Вернитесь к инструкции MOV, если нулевой флаг равен ; не задано; замок ранее был заперт, и так ; нам нужно крутить до тех пор, пока он не разблокируется. РЭТ ; Блокировка получена, вернитесь к вызову ; функция.                           spin_unlock: xor eax , eax ; Установите регистр EAX в 0. xchg eax , [ locked ] ; Атомарно поменять регистр EAX с помощью ; переменная блокировки. РЭТ ; Замок снят.

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

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

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

; В C: while (!__sync_bool_compare_and_swap(&locked, 0, 1)) while (locked) __builtin_ia32_pause(); spin_lock: mov ecx , 1 ; Установите регистр ECX на 1. повторите попытку: xor eax , eax ; Обнулите EAX, поскольку cmpxchg сравнивается с EAX. XACQUIRE lock cmpxchg [ заблокировано ], ecx ; решить атомарно: если lock равен нулю, записать в него ECX. ; XACQUIRE намекает процессору, что мы получаем блокировку. я вышел ; Если мы его заблокировали (старое значение равно EAX:0), возвращаемся. пауза: mov eax , [ заблокировано ] ; Чтение заблокировано в EAX. тест eax , eax ; Выполните нулевую проверку, как и раньше. джз повторить попытку ; Если оно равно нулю, мы можем повторить попытку. повтор нет ; Сообщите процессору, что мы ждём в спин-лупе, чтобы он мог ; работайте сейчас над другой веткой. Также пишется как «пауза». джмп пауза ; Продолжайте проверять-паузу. выход: Рет ; Все сделано.                                      spin_unlock: XRELEASE mov [ заблокировано ], 0 ; Предполагая, что правила упорядочивания памяти применяются, отпустите ; переменная блокировки с подсказкой «снятие блокировки». РЭТ ; Замок снят.

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

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

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

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

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

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

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

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

Смотрите также

Рекомендации

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

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