Войти
В Computer Science инструкция test-and-set инструкция, используемая для записи 1 (установки) в ячейку памяти и возврата ее старого значения в виде единственной атомарной (т. е. непрерываемой) операции. Если несколько процессов могут получить доступ к одной и той же области памяти, и если процесс в настоящее время выполняет тест-и-установку, ни один другой процесс не может начать еще один тест-и-набор, пока не завершится тестирование и настройка первого процесса. ЦП может использовать команду тестирования и установки, предлагаемую другим электронным компонентом, например, двухпортовым ОЗУ ; сам ЦП также может предлагать инструкцию по тестированию и установке.
Блокировка может быть построена с использованием атомарной инструкции проверки и установки следующим образом:
function Lock (boolean * lock) {while (test_and_set (lock) == 1); }Вызывающий процесс получает блокировку, если старое значение было 0, в противном случае цикл while вращается в ожидании получения блокировки. Это называется спин-блокировкой. «Тест и Тест-и-установка » - еще один пример.
Морис Херлихи (1991) доказал, что тест-и-набор имеет конечное число консенсуса и может решить проблему консенсуса без ожидания не более чем для двух одновременных процессы. Напротив, сравнение и замена предлагает более общее решение этой проблемы.
DPRAM test-and-set может работать разными способами. Вот два варианта, каждый из которых описывает DPRAM, который предоставляет ровно 2 порта, позволяя двум отдельным электронным компонентам (например, 2 CPU) получить доступ к каждой ячейке памяти DPRAM.
Когда ЦП 1 выдает команду тестирования и установки, DPRAM сначала делает «внутреннюю заметку» об этом, сохраняя адрес ячейки памяти в специальном месте. Если в этот момент CPU 2 выдает команду test-and-set для той же ячейки памяти, DPRAM сначала проверяет свою «внутреннюю заметку», распознает ситуацию и выдает прерывание BUSY, которое сообщает CPU 2, что он должен подождите и повторите попытку. Это реализация занятого ожидания или спин-блокировки с использованием механизма прерывания. Поскольку все это происходит на аппаратных скоростях, CPU 2 очень недолго ожидает выхода из спин-блокировки.
Независимо от того, пытался ли ЦП 2 получить доступ к ячейке памяти, DPRAM выполняет тест, заданный ЦП 1. Если тест завершается успешно, DPRAM устанавливает ячейку памяти на значение, указанное ЦП 1. Затем DPRAM стирает свою «внутреннюю заметку» о том, что CPU 1 писал туда. На этом этапе ЦП 2 может выполнить тестовую установку, которая завершится успешно.
ЦП 1 выдает команду тестирования и установки для записи в «ячейку памяти A». DPRAM не сразу сохраняет значение в ячейке памяти A, а вместо этого одновременно перемещает текущее значение в специальный регистр, устанавливая для содержимого ячейки памяти A особое «значение флага». Если в этот момент ЦП 2 выдает команду test-and-set для ячейки памяти A, DPRAM обнаруживает значение специального флага и, как в Варианте 1, выдает прерывание BUSY.
Независимо от того, пытался ли ЦП 2 получить доступ к ячейке памяти, DPRAM теперь выполняет тест ЦП 1. Если тест завершается успешно, DPRAM устанавливает ячейку памяти A на значение, указанное CPU 1. Если тест не удается, DPRAM копирует значение обратно из специального регистра в ячейку памяти A. Любая операция стирает значение специального флага. Если теперь ЦП 2 выполнит тест и настройку, он будет успешным.
Некоторые наборы инструкций имеют атомарную инструкцию на машинном языке для проверки и установки. Примеры включают x86 и IBM System / 360 и его преемники (включая z / Architecture ). Те, кто этого не делает, по-прежнему могут реализовать атомарную проверку и установку с помощью инструкции чтение-изменение-запись или сравнение-и-замена.
Команда проверки и установки при использовании с логическими значениями использует логику, подобную той, которая показана в следующей функции, за исключением того, что функция должна выполняться атомарно. То есть никакой другой процесс не должен иметь возможность прервать выполнение функции в середине выполнения, таким образом, увидев состояние, которое существует только во время выполнения функции. Это требует аппаратной поддержки; это не может быть реализовано, как показано. Тем не менее, показанный код помогает объяснить поведение test-and-set. ПРИМЕЧАНИЕ. В этом примере предполагается, что «lock» передается по ссылке (или по имени), но присвоение «initial» создает новое значение (а не просто копирование ссылки).
функция TestAndSet (boolean_ref lock) {boolean initial = lock; lock = true; вернуть начальный; }Мало того, что показанный код не является атомарным, в смысле инструкции по тестированию и установке, он также отличается от описаний аппаратного тестирования DPRAM, приведенных выше. Здесь устанавливаемое значение и тест являются фиксированными и инвариантными, и значение обновляется независимо от результата теста, тогда как для DPRAM test-and-set память устанавливается только при успешном завершении теста, а значение для установки и условия проверки задаются ЦП. Здесь устанавливаемое значение может быть только 1, но если 0 и 1 считаются единственными допустимыми значениями для области памяти, а «значение не равно нулю» является единственным допустимым тестом, то это соответствует случаю, описанному для оборудования DPRAM ( или, более конкретно, случай DPRAM сводится к этому при этих ограничениях). С этой точки зрения это можно правильно назвать «испытанием и установкой» в полном, общепринятом смысле этого термина. Важным моментом, на который следует обратить внимание, является общее намерение и принцип проверки и установки: значение одновременно проверяется и устанавливается в одной атомарной операции, так что никакой другой программный поток или процесс не может изменить целевое расположение памяти после его проверки, но до него. установлен. (Это связано с тем, что местоположение должно быть установлено только в том случае, если оно в настоящее время имеет определенное значение, а не если оно имело это значение когда-то раньше.)
В языке программирования C реализация будет такой: например:
#define LOCKED 1 int TestAndSet (int * lockPtr) {int oldValue; // - Начало атомарного сегмента - // Это следует интерпретировать как псевдокод только для иллюстративных целей. // Традиционная компиляция этого кода не гарантирует атомарности, // использования разделяемой памяти (т. Е. Некэшированных значений), защиты от // оптимизаций компилятора или других необходимых свойств. oldValue = * lockPtr; * lockPtr = ЗАБЛОКИРОВАНО; // - Конец атомарного сегмента - return oldValue; }Код также показывает, что на самом деле существует две операции: атомарное чтение-изменение-запись и проверка. Только чтение-изменение-запись должно быть атомарным. (Это верно, потому что задержка сравнения значений на любое время не изменит результат теста после того, как значение для тестирования было получено. После того, как код записывает начальное значение, результат теста был установлен, даже если он еще не вычислен - например, оператором ==.)
Один из способов реализации взаимного исключения - это с использованием блокировки на основе теста и установки следующим образом:
volatile int lock = 0; void Critical () {while (TestAndSet (lock) == 1); критическая секция // только один процесс может быть в этой секции одновременно lock = 0 // снять блокировку по завершении критической секции}Переменная блокировки - это переменная общего доступа, т.е. к ней могут получить доступ все процессоры / потоки. Обратите внимание на ключевое слово volatile. В отсутствие изменчивости компилятор и / или ЦП могут оптимизировать доступ для блокировки и / или использовать кэшированные значения, тем самым делая приведенный выше код ошибочным. И наоборот, к сожалению, наличие volatile не гарантирует, что операции чтения и записи будут сохранены в памяти. Некоторые компиляторы выдают барьеры памяти, чтобы гарантировать, что операции фиксируются в памяти, но поскольку семантика volatile в C / C ++ довольно расплывчата, не все компиляторы будут это делать. Обратитесь к документации вашего компилятора, чтобы определить, есть ли это.
Эта функция может вызываться несколькими процессами, но гарантируется, что только один процесс будет находиться в критической секции одновременно. Остальные процессы будут продолжать вращаться, пока не получат блокировку. Возможно, что процессу никогда не будет предоставлена блокировка. В таком случае цикл будет бесконечным. Это недостаток данной реализации, поскольку она не обеспечивает справедливости. Эти проблемы более подробно рассматриваются в разделе производительности.
enter_region:; Тег «перейти к»; точка входа в функцию. tsl reg, flag; Тестирование и установка блокировки; флаг - это; общая переменная; это скопировано; в регистр reg и flag; затем атомарно устанавливается на 1. cmp reg, # 0; Был ли нулевой флаг для entry_region? jnz enter_region; Перейти к enter_region, если; рег не равен нулю; т.е. при входе флаг был ненулевым. ret; Выход; т.е. флаг был установлен на ноль; вход. Если мы попали сюда, tsl; установит ненулевое значение; таким образом,; мы востребовали ресурс; связанный с флагом. leave_region: переместить флаг, # 0; сохранить 0 во флаге ret; возврат к вызывающему
Здесь tsl- это атомарная инструкция, а flag- это блокирующая переменная. Процесс не возвращается, пока не получит блокировку.
Четыре основных показателя оценки для блокировок в целом - это задержка получения неконтролируемой блокировки, трафик шины, справедливость и хранение.
Тестируй и ставь низкие баллы по двум из них, а именно, высокий автобусный трафик и несправедливость.
Когда процессор P1 получил блокировку, а процессор P2 также ожидает блокировки, P2 будет продолжать выполнять транзакции шины в попытках получить блокировку. Когда процессор получил блокировку, все остальные процессоры, которые также желают получить такую же блокировку, продолжают попытки получить блокировку, повторно инициируя транзакции шины, пока они не получат блокировку. Это значительно увеличивает требования к трафику шины при тестировании и настройке. Это замедляет весь другой трафик из кэша и пропускает согласованность. Это замедляет работу всего раздела, поскольку трафик насыщен неудачными попытками получения блокировки. Test-and-test-and-set является усовершенствованием по сравнению с TSL, поскольку он не инициирует запросы на получение блокировки постоянно.
Когда мы рассматриваем справедливость, мы принимаем во внимание, получает ли процессор реальный шанс получить блокировку, когда он освобождается. В экстремальной ситуации процессор может зависнуть, то есть он не сможет получить блокировку в течение длительного периода времени, даже если за это время он освободился.
Накладные расходы на хранилище для TSL практически отсутствуют, поскольку требуется только одна блокировка. Неконтролируемая задержка также мала, поскольку необходимы только одна атомарная инструкция и переход.
