Спинлок против Семафора

Question

Каковы основные различия между семафором и спин-блокировкой?

Когда мы будем использовать семафор поверх спин-блокировки?

Answer 1

Спинлок и семафор отличаются в основном четырьмя вещами:

1. Какие они
spinlock является одной из возможных реализаций блокировки, а именно той, которая реализуется в режиме ожидания ожидания («вращение»). Семафор - это обобщение блокировки (или, наоборот, блокировка - это особый случай семафора). Обычно, , но не обязательно , спин-блокировки действительны только в пределах одного процесса, тогда как семафоры также могут использоваться для синхронизации между различными процессами.

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

Поскольку блокировку можно считать частным случаем семафора с максимальным значением 1.

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

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

3. Как они ведут себя при наличии скопления
Распространенным заблуждением является то, что спин-блокировки или алгоритмы без блокировок «обычно быстрее» или что они полезны только для «очень коротких задач» (в идеале, объект синхронизации не должен удерживаться дольше, чем это абсолютно необходимо).
Одно важное различие заключается в том, как различные подходы ведут себя при наличии скопления .

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

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

С другой стороны, учитывая высокую загруженность или если блокировка удерживается в течение длительных периодов (иногда вы просто не можете с этим поделать!), Спин-блокировка сожжет безумное количество циклов ЦП, ничего не добившись.
В этом случае гораздо лучше выбрать семафор (или мьютекс), поскольку он позволяет другому потоку запускать полезных задач в течение этого времени. Или, если ни у какого другого потока нет чего-то полезного, это позволяет операционной системе снизить нагрузку на ЦП и снизить потребление тепла / энергосбережение.

Кроме того, в одноядерной системе спин-блокировка будет весьма неэффективной при наличии перегрузки блокировки, поскольку вращающаяся нить будет тратить свое полное время на ожидание изменения состояния, которое не может произойти (не до тех пор, пока не будет запланирован выпуск потока). , чего не происходит во время работы ожидающего потока!). Следовательно, учитывая любое количество разногласий, получение блокировки занимает около 1 1/2 временных интервалов в лучшем случае (при условии, что освобождающий поток является следующим запланированным потоком), что не очень хорошее поведение.

4. Как они реализованы
Семафор в настоящее время обычно переносит sys_futex под Linux (опционально с спин-блокировкой, которая завершается после нескольких попыток).
Спин-блокировка обычно реализуется с использованием атомарных операций и без использования чего-либо, предоставляемого операционной системой. В прошлом это означало использование встроенных функций компилятора или непереносимых инструкций ассемблера. Между тем и C ++ 11, и C11 имеют атомарные операции как часть языка, поэтому, помимо общей сложности написания корректно корректного кода без блокировки, теперь можно реализовать код без блокировки в полностью переносимом и (почти) безболезненно.

Answer 2

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

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

Обычно, если вы вращаетесь дольше, чем квант нити, вам следует использовать семафор.

Answer 3

Помимо того, что сказали Yoav Aviram и gbjbaanb, другой ключевой момент состоял в том, что вы никогда не использовали бы спин-блокировку на машине с одним процессором, тогда как семафор имел бы смысл на такой машине. В настоящее время вам часто бывает трудно найти машину без нескольких ядер, с гиперпоточностью или с аналогами, но в тех случаях, когда у вас всего один процессор, вам следует использовать семафоры. (Полагаю, причина очевидна. Если один ЦП занят, ожидая, пока что-то еще освободит спин-блокировку, но работает на единственном ЦП, блокировка вряд ли будет снята, пока текущий процесс или поток не будет прерван O / S, что может занять некоторое время, и ничего полезного не произойдет, пока не произойдет вытеснение.)

Answer 4

Из драйверов устройств Linux от Rubinni

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

Answer 5

Я не эксперт по ядру, но вот несколько моментов:

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

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

В основном, спин-блокировка должна использоваться, если критическая секция мала (меньше, чем накладные расходы сна / пробуждения), и критическая секция не вызывает ничего, что может спать! Семафор должен использоваться, если критическая секция больше и может спать.

Раман Чалотра.

Answer 6

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

Semaphor - это средство, снабжаемое операционными системами для IPC, поэтому его основным назначением является межпроцессное взаимодействие. Будучи средством, обеспечиваемым операционной системой, его производительность не будет такой же хорошей, как у спин-блокировки для внутренней блокировки (хотя и возможно). Семафоры лучше блокировать на более длительные периоды времени.

Тем не менее, реализовать сплинлоки в сборке сложно, а не переносимо.

Answer 7

Я хотел бы добавить свои наблюдения, более общие и не очень специфичные для Linux.

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

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

Однако, поскольку разрабатываются простые / дешевые многоядерные системы (я работаю во встроенных системах), не все архитектуры памяти поддерживают такие многоядерные / многопроцессорные функции, только тестирование и установка или эквивалент. Тогда реализация может быть следующей:

• получить спин-блокировку (занят в ожидании)
• попытаться приобрести семафор
• отпустить спин-блокировку
• если семафор не был успешно получен, приостановите текущий поток, пока семафор не будет освобожден; в противном случае перейдите к критическому разделу

Освобождение семафора должно быть реализовано следующим образом:

• получить спин-замок
• освободить семафор
• отпустить спин-блокировку

Да, и для простых двоичных семафоров на уровне ОС можно было бы использовать только спин-блокировку в качестве замены. Но только если защищаемые участки кода действительно очень малы.

Как уже было сказано, если и когда вы внедряете свою собственную ОС, будьте осторожны. Отладка таких ошибок - это весело (на мой взгляд, многие не разделяют), но в основном это очень утомительно и сложно.

Answer 8

От В чем разница между спин-блокировками и семафорами? от Maciej Piechotka :

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

Спин-блокировки выполняют ожидание занятости - то есть он продолжает работать в цикле:

while (try_acquire_resource ()); 
 ...  
release();

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

if (!try_lock()) {
    add_to_waiting_queue ();
    wait();
}
...
process *p = get_next_process_from_waiting_queue ();
p->wakeUp ();

Следовательно, если поток попытается получить заблокированный ресурс, он будет приостановлен, пока не станет доступным для него. Блокировка / разблокировка намного тяжелее, но ожидание «бесплатно» и «честно».

Семафор - это блокировка, которую разрешено использовать несколько раз (известно из инициализации) - например, 3 потокам разрешено одновременно удерживать ресурс, но не более. Это используется, например, в проблеме производителя / потребителя или вообще в очередях:

P(resources_sem)
resource = resources.pop()
...
resources.push(resources)
V(resources_sem)

Разница между семафором, мьютексом и спин-блокировкой?

Блокировка в Linux

Answer 9

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

Пример: в модуле драйвера устройства драйвер записывает «0» в аппаратном регистре R0, и теперь ему нужно дождаться, пока этот регистр R0 станет 1. H / W читает R0, выполняет некоторую работу и пишет «1» в R0. Это обычно быстро (в микросекундах). Теперь спиннинг намного лучше, чем идти спать и прерывается H / W. Конечно, во время вращения необходимо позаботиться о неисправности H / W!

Абсолютно нет причин для того, чтобы приложение пользователя вращалось. Это не имеет смысла. Вы собираетесь вращаться, чтобы произошло какое-то событие, и это событие должно быть завершено другим приложением пользовательского уровня, которое никогда не будет гарантировано в короткие сроки. Так что я вообще не буду крутиться в режиме пользователя. Я лучше спать () или mutexlock () или семафор блокировки () в режиме пользователя.

Answer 10

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

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