Для чего используется Test-and-Set?

Question

После прочтения "Тест-и-набор" Запись в Википедии у меня все еще остается вопрос "Для чего будет использоваться тест-и-набор?"

Я понимаю, что вы можете использовать его для реализации Mutex (как описано в википедии), но для чего еще он нужен?

Answer 1

Хорошим примером является «приращение»

Скажем, два потока выполнить a = a + 1. Скажем, a начинается со значения 100. Если оба потока работают одновременно (многоядерный), оба загружают a как 100, увеличивают до 101 и сохраняют его обратно в a. Неправильно!

При использовании команды test-and-set вы говорите «Установите a на 101, но только если в данный момент оно имеет значение 100». В этом случае один поток пройдет этот тест, а другой потерпит неудачу. В случае сбоя поток может повторить весь оператор, на этот раз загружая a как 101. Успех.

Это обычно быстрее, чем использование мьютекса, потому что:

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

Test-and-set - это операция, которая может быть выполнена с двумя другими инструкциями, не атомарными и более быстрыми (атомарность несет аппаратные издержки, когда в многопроцессорных системах), поэтому обычно вы не будете использовать ее по другим причинам.

Answer 5

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

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

Почему вы используете TestAndSet, а не мьютекс? Потому что это обычно требует меньше накладных расходов, чем мьютекс. Там, где мьютекс требует вмешательства ОС, TestAndSet может быть реализован как единая атомарная инструкция на процессоре. При работе в параллельных средах с сотнями потоков один мьютекс в критической секции кода может вызвать серьезные узкие места.