Введение

Инструкция ЦПУ для установки ячейки памяти в 1 и возврата её предыдущего значения.

В информатике инструкция "проверка и установка" (test and set) – это инструкция, используемая для записи (установки) значения 1 в ячейку памяти и возврата её предыдущего значения в виде единой атомарной (т.е. неделимой) операции. Вызывающая сторона может затем "проверить" результат, чтобы определить, изменилось ли состояние. Если несколько процессов могут обращаться к одной и той же ячейке памяти, и если один процесс в данный момент выполняет инструкцию "проверка и установка", ни один другой процесс не может начать другую инструкцию "проверка и установка", пока первая не завершится. Центральный процессор (ЦП) может использовать инструкцию "проверка и установка", предоставляемую другим электронным компонентом, например, двухпортовой оперативной памятью; сам ЦП также может предоставлять такую инструкцию. Блокировка может быть реализована с использованием атомарной инструкции "проверка и установка" следующим образом:

Этот код предполагает, что ячейка памяти была инициализирована значением 0 до первого выполнения инструкции "проверка и установка". Вызывающий процесс получает блокировку, если предыдущее значение было 0, в противном случае цикл while будет выполняться, ожидая получения блокировки. Это называется спинлоком. В любой момент владелец блокировки может просто установить ячейку памяти обратно в 0, чтобы освободить блокировку для захвата другим процессом – это не требует специальной обработки, поскольку владелец "контролирует" эту ячейку памяти. "Проверка, проверка и установка" (test, test and set) – ещё один пример. Морис Эрлихи (1991) доказал, что "проверка и установка" (сравнение с 1 битом) имеет конечное число согласия и может решить задачу консенсуса без блокировок для не более чем двух параллельных процессов. В отличие от этого, "сравнение и обмен" (сравнение с 32 битами) предлагает более общее решение этой задачи, а в некоторых реализациях также доступна операция "двойное сравнение и обмен" (сравнение с 64 битами) для расширенной функциональности.

Аппаратная реализация метода "тест-и-набор"

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

Вариант 1

Когда CPU 1 выдает инструкцию "проверить и установить", DPRAM сначала делает "внутреннюю пометку" об этом, сохраняя адрес ячейки памяти в специальном месте. Если в этот момент CPU 2 случайно выдает инструкцию "проверить и установить" для той же ячейки памяти, DPRAM сначала проверяет свою "внутреннюю пометку", распознает ситуацию и выдает прерывание BUSY, которое сообщает CPU 2, что он должен ждать и повторить попытку. Это реализация ожидания занятости или спинлока с использованием механизма прерываний. Поскольку все это происходит на аппаратной скорости, время ожидания CPU 2 для выхода из спинлока очень мало. Независимо от того, пытался ли CPU 2 получить доступ к ячейке памяти, DPRAM выполняет проверку, заданную CPU 1. Если проверка успешна, DPRAM устанавливает ячейку памяти в значение, заданное CPU 1. Затем DPRAM удаляет свою "внутреннюю пометку" о том, что CPU 1 записывал туда данные. В этот момент CPU 2 может выдать инструкцию "проверить и установить", которая будет выполнена успешно.

Вариант 2

ЦП 1 выдает инструкцию "проверить и установить" для записи в "ячейку памяти A". DPRAM не сохраняет значение в ячейке памяти A немедленно, а вместо этого одновременно перемещает текущее значение в специальный регистр, устанавливая содержимое ячейки памяти A на специальное "флаг-значение". Если в этот момент ЦП 2 выдает инструкцию "проверить и установить" для ячейки памяти A, DPRAM обнаруживает специальное флаг-значение и, как в Варианте 1, генерирует прерывание BUSY. Независимо от того, пытался ли ЦП 2 получить доступ к ячейке памяти, DPRAM теперь выполняет проверку, инициированную ЦП 1. Если проверка успешна, DPRAM устанавливает ячейку памяти A на значение, указанное ЦП 1. Если проверка не удалась, DPRAM копирует значение обратно из специального регистра в ячейку памяти A. Любая из этих операций стирает специальное флаг-значение. Если ЦП 2 теперь выдаст инструкцию "проверить и установить", она будет выполнена успешно.

Оценка характеристик испытательных и наборных замков

Четыре основных показателя оценки блокировок в целом – это задержка захвата блокировки в отсутствие конкуренции, трафик шины, справедливость и использование памяти. Метод "проверки и установки" показывает низкие результаты по двум из них: высокий трафик шины и несправедливость. Когда процессор P1 захватил блокировку, а процессор P2 также ожидает её, P2 будет продолжать генерировать транзакции шины в попытках её получить. Когда процессор захватил блокировку, все остальные процессоры, желающие получить ту же блокировку, продолжают пытаться это сделать, многократно инициируя транзакции шины, пока не получат её. Это значительно увеличивает требования к трафику шины для метода "проверки и установки". Это замедляет весь остальной трафик, связанный с промахами кэша и когерентностью. Это замедляет выполнение всего участка кода, поскольку трафик насыщается неудачными попытками захвата блокировки. Метод "проверки и установки" является улучшением по сравнению с TSL, поскольку он не инициирует запросы на захват блокировки непрерывно. При оценке справедливости рассматривается, имеет ли процессор равные возможности для захвата блокировки, когда она освобождается. В экстремальной ситуации процессор может испытывать "голодание", то есть не сможет захватить блокировку в течение длительного периода времени, даже если она становится свободной. Затраты памяти для TSL минимальны, поскольку требуется только одна блокировка. Задержка в отсутствие конкуренции также низкая, поскольку требуется только одна атомарная инструкция и переход.