В информатике инструкция test -and-set — это инструкция, используемая для записи (установки) 1 в ячейку памяти и возврата ее старого значения как единой атомарной (т. е. не прерываемой ) операции. Затем вызывающий может «проверить» результат, чтобы увидеть, было ли состояние изменено вызовом. Если несколько процессов могут получить доступ к одной и той же ячейке памяти, и если процесс в данный момент выполняет test-and-set, никакой другой процесс не может начать другой test-and-set, пока test-and-set первого процесса не будет завершен. Центральный процессор (ЦП) может использовать инструкцию test-and-set, предлагаемую другим электронным компонентом, таким как двухпортовая оперативная память ; сам ЦП также может предлагать инструкцию test-and-set.
Блокировку можно построить с помощью атомарной инструкции «проверить и установить » [1] следующим образом:
Этот код предполагает, что ячейка памяти была инициализирована значением 0 в какой-то момент до первой проверки и установки. Вызывающий процесс получает блокировку, если старое значение было равно 0, в противном случае цикл while продолжает вращаться, ожидая получения блокировки. Это называется спин- блокировкой . В любой момент держатель блокировки может просто установить ячейку памяти обратно на 0, чтобы снять блокировку для получения другим — это не требует какой-либо специальной обработки, поскольку держатель «владеет» этой ячейкой памяти. « Тест и проверка и установка » — еще один пример.
Морис Херлихи (1991) доказал, что метод test-and-set (1-битный компаран) имеет конечное число консенсуса и может решить проблему консенсуса без ожидания максимум для двух параллельных процессов. [2] Напротив, метод compare-and-swap (32-битный компаран) предлагает более общее решение этой проблемы, а в некоторых реализациях метод compare-double-and-swap (64-битный компаран) также доступен для расширенной полезности.
Инструкции DPRAM test-and-set могут работать многими способами. Вот два варианта, оба из которых описывают DPRAM, который предоставляет ровно 2 порта, позволяя 2 отдельным электронным компонентам (например, 2 ЦП) получать доступ к каждой ячейке памяти на DPRAM.
Когда CPU 1 выдает инструкцию test-and-set, DPRAM сначала делает "внутреннюю заметку" об этом, сохраняя адрес ячейки памяти в специальном месте. Если в этот момент CPU 2 случайно выдает инструкцию test-and-set для той же ячейки памяти, DPRAM сначала проверяет свою "внутреннюю заметку", распознает ситуацию и выдает прерывание BUSY, которое сообщает CPU 2, что он должен подождать и повторить попытку. Это реализация активного ожидания или спин-блокировки с использованием механизма прерываний. Поскольку все это происходит на аппаратных скоростях, ожидание CPU 2 для выхода из спин-блокировки очень короткое.
Независимо от того, пытался ли CPU 2 получить доступ к ячейке памяти или нет, DPRAM выполняет тест, заданный CPU 1. Если тест успешен, DPRAM устанавливает ячейку памяти в значение, заданное CPU 1. Затем DPRAM стирает свою «внутреннюю заметку», которую туда записывал CPU 1. В этот момент CPU 2 может выдать команду test-and-set, которая будет успешной.
CPU 1 выдает команду test-and-set для записи в "ячейку памяти A". DPRAM не сразу сохраняет значение в ячейке памяти A, а вместо этого одновременно перемещает текущее значение в специальный регистр, одновременно устанавливая содержимое ячейки памяти A в специальное "значение флага". Если в этот момент CPU 2 выдает команду test-and-set в ячейку памяти A, DPRAM обнаруживает специальное значение флага и, как в варианте 1, выдает прерывание BUSY.
Независимо от того, пытался ли CPU 2 получить доступ к ячейке памяти или нет, DPRAM теперь выполняет тест CPU 1. Если тест успешен, DPRAM устанавливает ячейку памяти A в значение, указанное CPU 1. Если тест не пройден, DPRAM копирует значение обратно из специального регистра в ячейку памяти A. Любая из этих операций стирает значение специального флага. Если CPU 2 теперь выдает команду test-and-set, она будет успешной.
Некоторые наборы инструкций имеют атомарную инструкцию машинного языка test-and-set. Примерами являются x86 [3] и IBM System/360 и ее последователи (включая z/Architecture ). [4] Те, у кого ее нет, все равно могут реализовать атомарную инструкцию test-and-set с помощью инструкции read-modify-write или compare-and-swap .
Инструкция test and set при использовании с булевыми значениями использует логику, подобную показанной в следующей функции, за исключением того, что функция должна выполняться атомарно . То есть никакой другой процесс не должен иметь возможности прервать функцию во время выполнения, тем самым увидев состояние, которое существует только во время выполнения функции. Для этого требуется аппаратная поддержка; это не может быть реализовано так, как показано. Тем не менее, показанный код помогает объяснить поведение test-and-set. ПРИМЕЧАНИЕ. В этом примере предполагается, что «lock» передается по ссылке (или по имени), но присвоение «initial» создает новое значение (а не просто копирование ссылки).
функция TestAndSet(boolean_ref lock) { начальный логический = блокировка; блокировка = истина; вернуть начальную букву;}Показанный код не только не атомарен в смысле инструкции test-and-set, он также отличается от описаний аппаратного test-and-set DPRAM выше. Здесь устанавливаемое значение и тест фиксированы и инвариантны, и значение обновляется независимо от результата теста, тогда как для test-and-set DPRAM память устанавливается только при успешном завершении теста, а устанавливаемое значение и условие теста указываются ЦП. Здесь устанавливаемое значение может быть только 1, но если 0 и 1 считаются единственными допустимыми значениями для ячейки памяти, а «значение не равно нулю» является единственным разрешенным тестом, то это соответствует случаю, описанному для аппаратного обеспечения DPRAM (или, более конкретно, случай DPRAM сводится к этому при этих ограничениях). С этой точки зрения это можно правильно назвать «test-and-set» в полном, общепринятом смысле этого термина. Важно отметить общее намерение и принцип проверки и установки: значение проверяется и устанавливается в одной атомарной операции, так что никакой другой программный поток или процесс не может изменить целевое расположение памяти после его проверки, но до его установки. (Это связано с тем, что расположение должно быть установлено только в том случае, если оно в данный момент имеет определенное значение, а не если оно имело это значение когда-то ранее.)
На языке программирования C реализация будет выглядеть так:
#define ЗАБЛОКИРОВАНО 1int test_and_set ( int * lockPtr ) { int oldValue ; // -- Начало атомарного сегмента -- // Это следует интерпретировать как псевдокод только в иллюстративных целях. // Традиционная компиляция этого кода не гарантирует атомарность, // использование общей памяти (т. е. некэшированных значений), защиту от оптимизаций компилятора // или другие требуемые свойства. oldValue = * lockPtr ; * lockPtr = LOCKED ; // -- Конец атомарного сегмента -- вернуть староеЗначение ; } Код также показывает, что на самом деле есть две операции: атомарное чтение-изменение-запись и проверка. Только чтение-изменение-запись должны быть атомарными. (Это верно, поскольку задержка сравнения значений на любое количество времени не изменит результат проверки после того, как будет получено значение для проверки. После того, как код запишет начальное значение, результат проверки будет установлен, даже если он еще не был вычислен — например, оператором ==.)
Одним из способов реализации взаимного исключения является использование блокировки на основе проверки и установки [5] [6] следующим образом:
изменчивая целая блокировка = 0 ; void critical () { // Спин-блокировка: цикл вечно, пока мы не получим блокировку; мы знаем, что блокировка была // успешно получена после выхода из этого цикла while, потому что функция // test_and_set() блокирует блокировку и возвращает предыдущее значение блокировки. Если предыдущее значение блокировки было 1, то блокировка была **уже** // заблокирована другим потоком или процессом. Однако, как только предыдущее значение блокировки // было 0, это означает, что блокировка была **не** заблокирована до того, как мы ее заблокировали, но теперь она **заблокирована**, потому что мы ее заблокировали, указывая, // что мы владеем блокировкой. while ( test_and_set ( & lock ) == 1 ); критическая секция // в этой секции одновременно может находиться только один процесс lock = 0 ; // снять блокировку по завершении работы с критической секцией } Переменная блокировки является общей переменной, то есть к ней могут обращаться все процессоры/потоки. Обратите внимание на ключевое слово volatile . При отсутствии volatile компилятор и/или ЦП могут оптимизировать доступ для блокировки и/или использования кэшированных значений, тем самым делая приведенный выше код ошибочным. И наоборот, и к сожалению, наличие volatile не гарантирует , что чтение и запись будут зафиксированы в памяти. Некоторые компиляторы выдают барьеры памяти , чтобы гарантировать, что операции будут зафиксированы в памяти, но поскольку семантика volatile в C/C++ довольно расплывчата, не все компиляторы будут это делать. Обратитесь к документации вашего компилятора, чтобы определить, делает ли это так.
Эта функция спин-блокировки может быть вызвана несколькими процессами, но гарантируется, что в критической секции будет находиться только один процесс в каждый момент времени. Остальные процессы будут продолжать выполняться до тех пор, пока не получат блокировку. Возможно, что процессу никогда не будет предоставлена блокировка. В таком случае он будет зацикливаться бесконечно. Это недостаток реализации спин-блокировки, поскольку она не обеспечивает справедливости. Эти вопросы более подробно рассматриваются в разделе производительности.
enter_region: ; Тег «перейти к»; точка входа в функцию. tsl reg , flag ; Тест и установка блокировки; flag — это ; общая переменная; она копируется ; в регистр reg и flag ; затем атомарно устанавливается в 1. cmp reg , #0; Был ли флаг равен нулю на entry_region? jnz enter_region ; Перейти к enter_region, если ; reg не равен нулю; т. е. ; флаг был не равен нулю при входе. ret ; Выход; т.е. флаг был равен нулю при ; входе. Если мы доберемся сюда, tsl ; установит его ненулевым; таким образом, ; мы затребовали ресурс , ; связанный с флагом. leave_region: переместить флаг , #0; сохранить 0 во флаге ret ; вернуться к вызывающему Вот tslатомарная инструкция и flagпеременная блокировки. Процесс не возвращается, пока не получит блокировку.
Четыре основных показателя оценки блокировок в целом — это задержка получения неконкурентной блокировки, трафик шины, справедливость и хранилище. [7]
Низкие баллы по двум из них: интенсивное движение автобусов и несправедливость.
Когда процессор P1 получил блокировку, а процессор P2 также ожидает блокировки, P2 будет продолжать выполнять транзакции шины в попытках получить блокировку. Когда процессор получил блокировку, все другие процессоры, которые также хотят получить ту же блокировку, продолжают пытаться получить блокировку, инициируя транзакции шины повторно, пока не получат блокировку. Это значительно увеличивает требования к трафику шины для test-and-set. Это замедляет весь остальной трафик из- за промахов кэша и когерентности . Это замедляет весь раздел, поскольку трафик перенасыщен неудачными попытками получения блокировки. Test-and-test-and-set является улучшением по сравнению с TSL, поскольку он не инициирует запросы на получение блокировки непрерывно.
Когда мы рассматриваем справедливость, мы рассматриваем, получает ли процессор справедливые шансы получить блокировку, когда она освобождается. В экстремальной ситуации процессор может голодать, т. е. он может не иметь возможности получить блокировку в течение длительного периода времени, даже если он освободился в течение этого времени.
Накладные расходы на хранение для TSL практически отсутствуют, поскольку требуется только одна блокировка. Неконкурентная задержка также низкая, поскольку требуется только одна атомарная инструкция и ветвь.