Тест и настройка

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

Замок . можно построить с помощью атомарного теста и установки ^[1] инструкция следующая:

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

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

Аппаратная реализация теста и настройки

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

Вариант 1

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

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

Вариант 2

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

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

Программная реализация теста и настройки

Некоторые наборы команд содержат атомарные инструкции машинного языка «проверь и установи». Примеры включают x86. ^[3] и IBM System/360 и его преемники (включая z/Architecture ). ^[4] Те, кто этого не делает, все равно могут реализовать атомарное тестирование и установку с использованием инструкций чтения-изменения-записи или сравнения и замены .

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

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

Показанный код не только не является атомарным в смысле инструкции тестирования и установки, он также отличается от описаний аппаратного тестирования и установки DPRAM выше. Здесь устанавливаемое значение и тест фиксированы и инвариантны, и значение обновляется независимо от результата теста, тогда как для теста и установки DPRAM память устанавливается только в случае успешного завершения теста, и значение которые необходимо установить, и условия тестирования задаются ЦП. Здесь устанавливаемое значение может быть только 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;
}

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

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

Одним из способов реализации взаимного исключения является использование блокировки на основе проверки и установки. ^[5]^[6] следующее:

Реализация спин-блокировки на псевдо-C

volatile int lock = 0;

void critical() {
    // Spin lock: loop forever until we get the lock; we know the lock was
    // successfully obtained after exiting this while loop because the 
    // test_and_set() function locks the lock and returns the previous lock 
    // value. If the previous lock value was 1 then the lock was **already**
    // locked by another thread or process. Once the previous lock value
    // was 0, however, then it indicates the lock was **not** locked before we
    // locked it, but now it **is** locked because we locked it, indicating
    // we own the lock.
    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
}

Переменная блокировки является общей переменной, т.е. к ней могут обращаться все процессоры/потоки. Обратите внимание на ключевое слово Volatible . При отсутствии энергозависимого компилятор и/или ЦП могут оптимизировать доступ к блокировке и/или использованию кэшированных значений, тем самым делая приведенный выше код ошибочным. И наоборот, к сожалению, наличие летучих данных не гарантирует , что операции чтения и записи будут зафиксированы в памяти. Некоторые компиляторы устанавливают барьеры памяти , чтобы гарантировать, что операции будут зафиксированы в памяти, но поскольку семантика изменчивости в 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 — переменная блокировки. Процесс не вернется, пока не получит блокировку.

Оценка эффективности тестовых и установочных замков

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

Тестирование и установка показали низкие оценки по двум из них, а именно: высокая интенсивность автобусного движения и несправедливость.

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

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

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

См. также

Ссылки

^ Андерсон, TE (1 января 1990 г.). «Производительность альтернатив спин-блокировки для мультипроцессоров с общими деньгами». Транзакции IEEE в параллельных и распределенных системах . 1 (1): 6–16. дои : 10.1109/71.80120 . ISSN 1045-9219 .
^ Херлихи, Морис (январь 1991 г.). «Синхронизация без ожидания» (PDF) . АКМ Транс. Программа. Ланг. Сист . 13 (1): 124–149. CiteSeerX 10.1.1.56.5659 . дои : 10.1145/114005.102808 . S2CID 2181446 . Проверено 20 мая 2007 г.
^ «BTS — проверка и установка битов» . www.felixcloutier.com . Проверено 21 ноября 2016 г.
^ «Центр знаний IBM» . www.ibm.com . Проверено 21 ноября 2016 г.
^ Ремзи Х. Арпачи-Дюссо и Андреа К. Арпачи-Дюссо (2015). Операционные системы: три простых части (изд. 0,91). Книги Арпачи-Дюссо.
^ Солихин, Ян (2009). Основы параллельной компьютерной архитектуры: многокристальные и многоядерные системы . п. 252. ИСБН 9780984163007 .
^ Солихин, Ян (2016). Основы параллельной архитектуры Бока-Ратон, Флорида: CRC Press. ISBN 978-1-4822-1118-4 .

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

Описание из Энциклопедии систем, нечувствительных к задержке.
« Тестирование и настройка без ожидания », автор: Иегуда Афек
int testandset(int *lock) — вызываемая C-программа, написанная на языке ассемблера Sun SPARC
Руководство разработчика Intel

[1] Андерсон, TE (1 января 1990 г.). «Производительность альтернатив спин-блокировки для мультипроцессоров с общими деньгами». Транзакции IEEE в параллельных и распределенных системах . 1 (1): 6–16. дои : 10.1109/71.80120 . ISSN 1045-9219 .

[2] Херлихи, Морис (январь 1991 г.). «Синхронизация без ожидания» (PDF) . АКМ Транс. Программа. Ланг. Сист . 13 (1): 124–149. CiteSeerX 10.1.1.56.5659 . дои : 10.1145/114005.102808 . S2CID 2181446 . Проверено 20 мая 2007 г.

[3] «BTS — проверка и установка битов» . www.felixcloutier.com . Проверено 21 ноября 2016 г.

[4] «Центр знаний IBM» . www.ibm.com . Проверено 21 ноября 2016 г.

[5] Ремзи Х. Арпачи-Дюссо и Андреа К. Арпачи-Дюссо (2015). Операционные системы: три простых части (изд. 0,91). Книги Арпачи-Дюссо.

[6] Солихин, Ян (2009). Основы параллельной компьютерной архитектуры: многокристальные и многоядерные системы . п. 252. ИСБН 9780984163007 .

[Solihin-7] Солихин, Ян (2016). Основы параллельной архитектуры Бока-Ратон, Флорида: CRC Press. ISBN 978-1-4822-1118-4 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]