Тест и установка - Test-and-set

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

Блокировку можно построить с помощью атомарной инструкции проверки и установки следующим образом:

function Lock(boolean *lock) { 
    while (test_and_set(lock) == 1); 
}

Этот код предполагает, что ячейка памяти была инициализирована до 0 в какой-то момент до первого теста и установки. Вызывающий процесс получает блокировку, если старое значение было 0, в противном случае цикл while вращается в ожидании получения блокировки. Это называется спин-блокировкой . В любой момент владелец блокировки может просто установить для ячейки памяти значение 0, чтобы разблокировать блокировку для захвата другим - это не требует какой-либо специальной обработки, поскольку держатель «владеет» этой ячейкой памяти. Другой пример - « Тест и тест-и-набор ».

Морис Херлихи (1991) доказал, что тест-и-набор (1-битное сравнение) имеет конечное число консенсуса и может решить проблему консенсуса без ожидания не более чем для двух параллельных процессов. Напротив, сравнение и замена (32-битное сравнение) предлагает более общее решение этой проблемы, а в некоторых реализациях сравнение-двойное-и-обменное (64-битное сравнение) также доступно для расширенной утилиты.

Аппаратная реализация test-and-set

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

Вариант 1

Когда CPU 1 выдает команду test-and-set, DPRAM сначала делает «внутреннюю заметку» об этом, сохраняя адрес ячейки памяти в специальном месте. Если в этот момент CPU 2 выдает команду test-and-set для той же области памяти, DPRAM сначала проверяет свою «внутреннюю заметку», распознает ситуацию и выдает прерывание BUSY, которое сообщает CPU 2, что он должен подождите и повторите попытку. Это реализация активного ожидания или спин-блокировки с использованием механизма прерывания. Поскольку все это происходит на аппаратных скоростях, ЦП 2 очень быстро ждет выхода из спин-блокировки.

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

Вариант 2

CPU 1 выдает команду test-and-set для записи в «ячейку памяти A». DPRAM не сразу сохраняет значение в ячейке памяти A, а вместо этого одновременно перемещает текущее значение в специальный регистр, одновременно устанавливая содержимое ячейки памяти A на специальное «значение флага». Если в этот момент ЦП 2 выдает команду test-and-set для ячейки памяти A, DPRAM обнаруживает значение специального флага и, как и в Варианте 1, выдает прерывание BUSY.

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

Программная реализация test-and-set

В некоторых наборах инструкций есть атомарная инструкция на машинном языке "тест и установка". Примеры включают x86 и IBM System / 360 и их преемников (включая z / Architecture ). Те, кто этого не делает, по-прежнему могут реализовать атомарную проверку и установку с использованием инструкций чтения-изменения-записи или сравнения и замены .

Команда проверки и установки при использовании с логическими значениями использует логику, подобную той, которая показана в следующей функции, за исключением того, что функция должна выполняться атомарно . То есть никакой другой процесс не должен иметь возможность прервать выполнение функции в середине выполнения, тем самым увидев состояние, которое существует только во время выполнения функции. Это требует аппаратной поддержки; это не может быть реализовано, как показано. Тем не менее, показанный код помогает объяснить поведение test-and-set. ПРИМЕЧАНИЕ. В этом примере предполагается, что «lock» передается по ссылке (или по имени), но присвоение «initial» создает новое значение (а не просто копирование ссылки).

function TestAndSet(boolean_ref lock) {
    boolean initial = lock;
    lock = true;
    return initial;
}

Мало того, что показанный код не является атомарным, в смысле инструкции по тестированию и установке, он также отличается от описаний аппаратного тестирования DPRAM, приведенных выше. Здесь устанавливаемое значение и тест являются фиксированными и неизменными, и значение обновляется независимо от результата теста, тогда как для DPRAM test-and-set память устанавливается только при успешном завершении теста, а значение для установки и условия проверки задаются ЦП. Здесь устанавливаемое значение может быть только 1, но если 0 и 1 считаются единственными допустимыми значениями для области памяти, а «значение не равно нулю» является единственным допустимым тестом, то это соответствует случаю, описанному для оборудования DPRAM ( или, более конкретно, случай DPRAM сводится к этому при этих ограничениях). С этой точки зрения, это можно правильно назвать «проверкой и установкой» в полном, общепринятом смысле этого термина. Важным моментом, на который следует обратить внимание, является общее намерение и принцип проверки и установки: значение одновременно проверяется и устанавливается в одной атомарной операции, так что никакой другой программный поток или процесс не может изменить целевое расположение памяти после его проверки, но до него. установлен. (Это потому, что местоположение должно быть установлено только в том случае, если оно в настоящее время имеет определенное значение, а не если оно имело это значение когда-то ранее.)

На языке программирования C реализация будет такой:

#define LOCKED 1

int test_and_set(int* lockPtr) {
    int oldValue;

    // -- Start of atomic segment --
    // This should be interpreted as pseudocode for illustrative purposes only.
    // Traditional compilation of this code will not guarantee atomicity, the
    // use of shared memory (i.e., non-cached values), protection from compiler
    // optimizations, or other required properties.
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    // -- End of atomic segment --

    return oldValue;
}

Код также показывает, что на самом деле существует две операции: атомарное чтение-изменение-запись и проверка. Только чтение-изменение-запись должно быть атомарным. (Это верно, потому что задержка сравнения значений на любой промежуток времени не изменит результат теста после того, как значение для тестирования было получено. После того, как код записывает начальное значение, результат теста был установлен, даже если он еще не вычислен - например, оператором ==.)

Взаимное исключение с использованием метода проверки и набора

Один из способов реализовать взаимное исключение - использовать блокировку на основе теста и установки следующим образом:

Реализация псевдо-C

volatile int lock = 0;

void critical() {
    while (test_and_set(&lock) == 1);
    critical section  // only one process can be in this section at a time
    lock = 0;  // release lock when finished with the critical section
}

Переменная блокировки - это общая переменная, т.е. к ней могут получить доступ все процессоры / потоки. Обратите внимание на ключевое слово volatile . В отсутствие изменчивости компилятор и / или ЦП могут оптимизировать доступ к блокировке и / или использовать кэшированные значения, тем самым делая приведенный выше код ошибочным. С другой стороны , и , к сожалению, присутствие летучих вовсе не гарантирует , что чтение и запись привержен памяти. Некоторые компиляторы создают барьеры памяти, чтобы гарантировать, что операции фиксируются в памяти, но поскольку семантика volatile в C / C ++ довольно расплывчата, не все компиляторы будут это делать. Обратитесь к документации вашего компилятора, чтобы определить, есть ли это.

Эта функция может быть вызвана несколькими процессами, но гарантируется, что только один процесс будет одновременно находиться в критической секции . Остальные процессы будут продолжать вращаться, пока не получат блокировку. Возможно, что процессу никогда не будет предоставлена ​​блокировка. В таком случае цикл будет бесконечным. Это недостаток данной реализации, поскольку она не обеспечивает справедливости. Эти вопросы более подробно рассматриваются в разделе производительности .

Реализация сборки

enter_region:        ; A "jump to" tag; function entry point.

  tsl reg, flag      ; Test and Set Lock; flag is the
                     ; shared variable; it is copied
                     ; into the register reg and flag
                     ; then atomically set to 1.

  cmp reg, #0        ; Was flag zero on entry_region?

  jnz enter_region   ; Jump to enter_region if
                     ; reg is non-zero; i.e.,
                     ; flag was non-zero on entry.

  ret                ; Exit; i.e., flag was zero on
                     ; entry. If we get here, tsl
                     ; will have set it non-zero; thus,
                     ; we have claimed the resource
                     ; associated with flag.

leave_region:
  move flag, #0      ; store 0 in flag
  ret                ; return to caller

Вот tslатомарная инструкция и flagблокирующая переменная. Процесс не возвращается, пока не получит блокировку.

Оценка работоспособности замков типа "испытание и установка"

Четыре основных показателя оценки для блокировок в целом - это задержка при обнаружении блокировки, трафик шины, справедливость и объем хранилища.

По двум из них, а именно, высокий автобусный трафик и несправедливость, получены низкие баллы Test-and-Set.

Когда процессор P1 получил блокировку, а процессор P2 также ожидает блокировки, P2 будет продолжать выполнять транзакции шины в попытках получить блокировку. Когда процессор получил блокировку, все другие процессоры, которые также желают получить такую ​​же блокировку, продолжают попытки получить блокировку, повторно инициируя транзакции шины, пока они не овладеют блокировкой. Это значительно увеличивает требования к трафику шины при тестировании и настройке. Это замедляет весь остальной трафик из кеша и пропускает согласованность . Это замедляет работу всего раздела, поскольку трафик перегружен неудачными попытками получения блокировки. Test-and-test-and-set - это улучшение по сравнению с TSL, поскольку он не инициирует запросы на получение блокировки непрерывно.

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

Накладные расходы на хранилище для TSL практически отсутствуют, поскольку требуется только одна блокировка. Неконтролируемая задержка также мала, поскольку требуется только одна атомарная инструкция и ветвь.

Смотрите также

использованная литература

  1. ^ Anderson, TE (1990-01-01). «Производительность альтернативы спин-блокировки для мультипроцессоров с разделяемыми деньгами». Транзакции IEEE в параллельных и распределенных системах . 1 (1): 6–16. DOI : 10.1109 / 71.80120 . ISSN  1045-9219 .
  2. ^ Herlihy, Морис (январь 1991). «Синхронизация без ожидания» (PDF) . ACM Trans. Программа. Lang. Syst . 13 (1): 124–149. CiteSeerX  10.1.1.56.5659 . DOI : 10.1145 / 114005.102808 . Проверено 20 мая 2007 .
  3. ^ «BTS - Bit Test and Set» . www.felixcloutier.com . Проверено 21 ноября 2016 .
  4. ^ «Центр знаний IBM» . www.ibm.com . Проверено 21 ноября 2016 .
  5. ^ Ремзи H. Arpaci-Dusseau и Андреа С. Arpaci-Dusseau (2015). Операционные системы: Three Easy Pieces (0.91 ed.). Книги Арпачи-Дюссо - через http://www.ostep.org/ .
  6. ^ Solihin, Ян (2009). Основы параллельной компьютерной архитектуры: многокристальные и многоядерные системы . п. 252. ISBN. 9780984163007.
  7. ^ Солихин, Ян (2016). Основы параллельной архитектуры . Бока-Ратон, Флорида: CRC Press. ISBN 978-1-4822-1118-4.

внешние ссылки