В распределенных вычислениях системы с общей памятью и системы передачи сообщений являются двумя широко изученными методами межпроцессного взаимодействия. В системах с общей памятью процессы взаимодействуют путем доступа к общим структурам данных. Общий (чтение/запись) регистр , иногда называемый просто регистром, является фундаментальным типом общей структуры данных, которая хранит значение и имеет две операции: чтение , которая возвращает значение, сохраненное в регистре, и запись , которая обновляет сохраненное значение. Другие типы общих структур данных включают чтение–изменение–запись, проверку и установку, сравнение и обмен и т. д. Ячейка памяти, к которой осуществляется одновременный доступ, иногда называется регистром.
Регистры можно классифицировать в соответствии с условием согласованности, которому они удовлетворяют при одновременном доступе, областью возможных значений, которые могут быть сохранены, и количеством процессов, которые могут получить доступ с помощью операции чтения или записи , что в общей сложности приводит к 24 типам регистров. [1]
Когда чтение и запись происходят одновременно, возвращаемое чтением значение может быть определено неоднозначно. Лэмпорт определил три типа регистров: безопасные регистры, обычные регистры и атомарные регистры. [1] Операция чтения безопасного регистра может возвращать любое значение, если она совпадает с операцией записи, и возвращает значение, записанное последней операцией записи , если операция чтения не перекрывается ни с одной записью . Обычный регистр отличается от безопасного регистра тем, что операция чтения может возвращать значение, записанное либо последней завершенной операцией записи, либо операцией записи, с которой она перекрывается. Атомарный регистр удовлетворяет более сильному условию линеаризуемости .
Регистры можно охарактеризовать по тому, сколько процессов могут получить доступ к операции чтения или записи . Регистр с одной записью (SW) может быть записан только одним процессом, а регистр с несколькими записями (MW) может быть записан несколькими процессами. Аналогично регистр с одной записью (SR) может быть прочитан только одним процессом, а регистр с несколькими записями (MR) может быть прочитан несколькими процессами. Для регистра SWSR не обязательно, чтобы процесс записи и процесс чтения были одинаковыми.
Рисунок ниже иллюстрирует конструкции поэтапно от реализации регистра SWSR в асинхронной системе передачи сообщений до реализации регистра MWMR с использованием объекта моментального снимка SW . Этот вид конструкции иногда называют симуляцией или эмуляцией. [2] На каждом этапе (кроме этапа 3) тип объекта справа может быть реализован более простым типом объекта слева. Конструкции каждого этапа (кроме этапа 3) кратко представлены ниже. Существует статья, в которой обсуждаются детали построения объектов моментального снимка .
Реализация линеаризуема , если для каждого выполнения существует порядок линеаризации, удовлетворяющий следующим двум свойствам:
Атомарный (линеаризуемый) регистр SWSR может быть реализован в асинхронной системе передачи сообщений, даже если процессы могут аварийно завершиться. Для процессов нет ограничений по времени доставки сообщений получателям или выполнения локальных инструкций. Другими словами, процессы не могут различать процессы, которые отвечают медленно или просто аварийно завершаются.
Реализация, данная Аттия, Бар-Ноем и Долевым [3], требует n > 2 f , где n — общее количество процессов в системе, а f — максимальное количество процессов, которые могут выйти из строя во время выполнения. Алгоритм выглядит следующим образом:
Порядок линеаризации операций таков: линеаризовать записи в том порядке, в котором они происходят, и вставить чтение после записи , значение которой оно возвращает. Мы можем проверить, что реализация линеаризуема. Мы можем проверить свойство 2, особенно когда op1 — это запись , а op2 — это чтение , а чтение следует сразу после записи . Мы можем показать от противного. Предположим, что чтение не видит запись , и тогда согласно реализации у нас должно быть два непересекающихся набора размера ( n - f ) среди n процессов. Так что 2 * ( n - f ) ≤ n , что приводит к n ≤ 2 f , что противоречит тому факту, что n > 2 f . Так что чтение должно прочитать по крайней мере одно значение, записанное этой записью .
Регистр SWMR может быть записан только одним процессом, но может быть прочитан несколькими процессами.
Пусть n — количество процессов, которые могут читать регистр SWMR. Пусть R i , 0 < i ≤ n , относится к читателям регистра SWMR. Пусть w — единственный писатель SWMR. На рисунке справа показана конструкция регистра SWMR с использованием массива из n ( n + 1) регистров SWSR. Обозначим массив как A . Каждый регистр SWSR A[ i , j ] доступен для записи R i , когда 0 < i ≤ n , и доступен для записи w , когда i = n + 1 . Каждый регистр SWSR A[ i , j ] доступен для чтения R j . Реализации чтения и записи показаны ниже.
Значение t операции — это значение t, которое она записывает, и операции линеаризуются значениями t. Если запись и чтение имеют одинаковое значение t, упорядочьте запись перед чтением . Если несколько чтений имеют одинаковые значения t, упорядочьте их по времени начала.
Мы можем использовать объект SW Snapshot размера n для создания регистра MWMR.
Порядок линеаризации следующий. Упорядочить операции записи по t-значениям. Если несколько записей имеют одинаковое t-значение, упорядочить операцию с небольшим идентификатором процесса впереди. Вставить операции чтения сразу после записи , значение которой они возвращают, разрывая связи по идентификатору процесса, и если связь все еще сохраняется, разрывать связи по времени начала.
![{\displaystyle {\ce {{\operatorname {Передача сообщений} \atop (MP)~Система}->[][{\text{Этап 1}}]SWSR~атомарный->[][{\text{Этап 2}}]SWMR->[][{\text{Этап 3}}]SW~моментальный снимок->[][{\text{Этап 4}}]MWMR}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/387091ecf014adf7ec21aba60eb20503b6caf4e5)