Атомная семантика

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

Регистр чтения/записи R хранит значение, и доступ к нему осуществляется двумя основными операциями: чтение и запись (v). Операция чтения возвращает значение, хранящееся в R, а запись(v) изменяет значение, хранящееся в R, на v. Регистр называется атомарным, если он удовлетворяет двум следующим свойствам:

1) Каждая операция вызова операции чтения или записи:

• Должно выглядеть так, как если бы оно было выполнено в один момент времени τ(op).

•τ (op) работает следующим образом: τb(op) ≤ τ (op) ≤ τe(op): где τb(op) и τe(op) обозначают время начала и окончания операции op.

• Если op1 ≠ op2, то τ (op1)≠τ (op2)

2) Каждая операция чтения возвращает значение, записанное последней операцией записи перед чтением, в той последовательности, в которой все операции упорядочены по их значениям τ.

Атомный/линеаризуемый регистр:

Завершение: когда узел правильный, рано или поздно каждая операция чтения и записи завершится.

Свойство безопасности (точки линеаризации для операций чтения и записи, а также неудачных операций):

Операция чтения: Похоже, что она произошла на всех узлах в некоторые моменты времени между вызовом и временем ответа.

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

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

Пример: мы знаем, что атомарный регистр — это тот, который линеаризуется в последовательный безопасный регистр.

На следующем рисунке показано, где мы должны поставить точку линеаризации для каждой операции:

Атомарный регистр может быть определен для переменной с одним записывающим устройством, но с несколькими устройствами чтения (SWMR), с одним устройством записи и одним устройством чтения (SWSR) или с несколькими устройствами записи и несколькими устройствами чтения (MWMR). Вот пример атомарного регистра с несколькими устройствами чтения и записи, к которому обращаются три процесса (P1, P2, P3). Обратите внимание, что R. read() → v означает, что соответствующая операция чтения возвращает v, которое является значением регистра. Следовательно, следующее выполнение регистра R может удовлетворять определению атомарных регистров: R.write(1), R.read()→1, R.write(3), R.write(2), R.read()→2, R.read()→2.

См. также

Ссылки

Атомная семантика формально определена в книге Лэмпорта «О межпроцессном взаимодействии» Distributed Computing 1, 2 (1986), 77–101. (Также опубликовано как Отчет об исследовании SRC 8).