Спин-замок против семафора


каковы основные различия между семафором и spin-lock?

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

10 103

10 ответов:

Spinlock и семафор отличаются в основном в четырех вещах:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

помимо того, что сказали Йоав Авирам и gbjbaanb, другим ключевым моментом было то, что вы никогда не будете использовать спин-блокировку на однопроцессорной машине, тогда как семафор будет иметь смысл на такой машине. В настоящее время вы часто испытываете трудности с поиском машины без нескольких ядер, или гиперпоточности, или эквивалента, но в условиях, когда у вас есть только один процессор, вы должны использовать семафоры. (Я верю, что причина очевидна. Если один процессор занят ожиданием чего-то в противном случае, чтобы освободить spin-lock, но он работает на единственном процессоре, блокировка вряд ли будет освобождена, пока текущий процесс или поток не будет вытеснен O/S, Что может занять некоторое время, и ничего полезного не произойдет, пока не произойдет вытеснение.)

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

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

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

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

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

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

Раман Chalotra.

Spinlock относится к реализации блокировки между потоками с использованием машинно-зависимых инструкций по сборке (таких как test-and-set). Он называется spinlock, потому что поток просто ждет в цикле ("спины") многократно проверяя, пока блокировка не станет доступной (занято ожидание). Спин-блокировки используются в качестве замены мьютексов, которые являются средством, поставляемым операционными системами (а не процессором), потому что спин-блокировки работают лучше, если они заблокированы в течение короткого периода времени.

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

Что сказал-реализация splinlocks в сборке является сложным, а не портативным.

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

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

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

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

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

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

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

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

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

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

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

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

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

нет абсолютно никакой причины для пользовательского приложения вращаться. Это не имеет смысла. Вы собираетесь вращаться, чтобы произошло какое-то событие, и это событие должно быть завершено другим приложением уровня пользователя, которое никогда не гарантируется в течение быстрого периода времени. Итак, я не буду вращаться вообще в пользовательском режиме. Мне лучше спать () или mutexlock() или semaphore lock () в пользовательском режиме.

С в чем разница между спин-блокировок и семафоров? by Мачей Piechotka:

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

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

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)

разница между семафором, мьютексом и spinlock?

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