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

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

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

Источник

9 ответов

Решение

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

Источник

Хороший пример - "приращение".

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

С тестом и набором, вы говорите "Установить a в 101, но только если он имеет значение 100Msgstr "В этом случае один поток пройдет этот тест, а другой не удастся. В случае отказа поток может повторить весь оператор, на этот раз загрузка a как 101, Успех.

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

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

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

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

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

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

Источник

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

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

Источник

Блокировка «проверить и установить» (TLS) используется для входа в критическую секцию.

      TLS <destination> <origin>

В общих чертах, TLS — это атомарная операция, состоящая из двух шагов:

  1. Скопируйте значение из в destination
  2. Установите значение originдо 1

Давайте посмотрим, как мы можем реализовать простой мьютекс для входа в критическую секцию с помощью инструкции ЦП TLS.

Нам нужна ячейка памяти, которая будет использоваться как общий ресурс. Назовем это. Для нас важно, что мы можем установить значение 0 или 1 в эту ячейку памяти.

Тогда вход в критическую секцию будет выглядеть так:

      enter_critical_section:
    TLS <tmp>, <lock>           ; copy value from <lock> to <tmp> and set <lock> to 1
    CMP <tmp>, #0               ; check if previous <lock> value was 0
    JNE enter_critical_section  ; if previous <lock> value was 1, it means that we didn't enter the critical section, and must try again
    RET                         ; if previous <lock> value was 0, we entered critical section, and can return to the caller

Чтобы покинуть критическую секцию, просто установите значение lockвернуться к 0:

      leave_critical_section:
  MOV <lock>, #0  
  RET

PS

Например, в x86 есть инструкция XCHG , позволяющая обменять значение реестра/памяти на другой регистр.

      XCHG <destination> <origin>

Реализация входа в критическую секцию с инструкцией XCHG:

      enter_critical_section:
    MOV <tmp>, #1
    XCHG <tmp>, <lock>
    CMP <tmp>, #0
    JNE enter_critical_section
    RET
Источник

Объекты Test and Set (TAS) можно использовать для реализации других параллельных объектов, таких как выборка и приращение (FAI). В . (подраздел 3.4.1), FAI реализуется с использованием объектов TAS.

11. Рашид Геррауи, Петр Кузнецов; Алгоритмы для параллельных систем

Источник

Тест и установка – это механизм синхронизации.

Источник

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

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

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

Источник

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

      void spin_lock(struct spinlock *lock)
{
        while (test_and_set(&lock->locked));
}
Источник
Другие вопросы по тегам