Общий регистр

Тип общей структуры данных

В распределенных вычислениях системы с общей памятью и системы передачи сообщений являются двумя широко изученными методами межпроцессного взаимодействия. В системах с общей памятью процессы взаимодействуют путем доступа к общим структурам данных. Общий (чтение/запись) регистр , иногда называемый просто регистром, является фундаментальным типом общей структуры данных, которая хранит значение и имеет две операции: чтение , которая возвращает значение, сохраненное в регистре, и запись , которая обновляет сохраненное значение. Другие типы общих структур данных включают чтение–изменение–запись, проверку и установку, сравнение и обмен и т. д. Ячейка памяти, к которой осуществляется одновременный доступ, иногда называется регистром.

Классификация

Регистры можно классифицировать в соответствии с условием согласованности, которому они удовлетворяют при одновременном доступе, областью возможных значений, которые могут быть сохранены, и количеством процессов, которые могут получить доступ с помощью операции чтения или записи , что в общей сложности приводит к 24 типам регистров. ^[1]

Классификация общего регистра
Условие согласованности	Домен	Писать	Читать
безопасный регулярный атомный	двоичное целое число	один писатель много писатель	одиночный ридер многоридерный

Когда чтение и запись происходят одновременно, возвращаемое чтением значение может быть определено неоднозначно. Лэмпорт определил три типа регистров: безопасные регистры, обычные регистры и атомарные регистры. ^[1] Операция чтения безопасного регистра может возвращать любое значение, если она совпадает с операцией записи, и возвращает значение, записанное последней операцией записи , если операция чтения не перекрывается ни с одной записью . Обычный регистр отличается от безопасного регистра тем, что операция чтения может возвращать значение, записанное либо последней завершенной операцией записи, либо операцией записи, с которой она перекрывается. Атомарный регистр удовлетворяет более сильному условию линеаризуемости .

Регистры можно охарактеризовать по тому, сколько процессов могут получить доступ к операции чтения или записи . Регистр с одной записью (SW) может быть записан только одним процессом, а регистр с несколькими записями (MW) может быть записан несколькими процессами. Аналогично регистр с одной записью (SR) может быть прочитан только одним процессом, а регистр с несколькими записями (MR) может быть прочитан несколькими процессами. Для регистра SWSR не обязательно, чтобы процесс записи и процесс чтения были одинаковыми.

Конструкции

Рисунок ниже иллюстрирует конструкции поэтапно от реализации регистра SWSR в асинхронной системе передачи сообщений до реализации регистра MWMR с использованием объекта моментального снимка SW . Этот вид конструкции иногда называют симуляцией или эмуляцией. ^[2] На каждом этапе (кроме этапа 3) тип объекта справа может быть реализован более простым типом объекта слева. Конструкции каждого этапа (кроме этапа 3) кратко представлены ниже. Существует статья, в которой обсуждаются детали построения объектов моментального снимка .

{\ce {{\operatorname {Передача сообщений} \atop (MP)~Система}->[][{\text{Этап 1}}]SWSR~атомарный->[][{\text{Этап 2}}]SWMR->[][{\text{Этап 3}}]SW~моментальный снимок->[][{\text{Этап 4}}]MWMR}}

Общий реестр этапов строительства

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

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

Реализация атомарного регистра SWSR в системе передачи сообщений

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

Внедрение атомного регистра SWSR в систему MP

Реализация, данная Аттия, Бар-Ноем и Долевым ^[3], требует $n > 2 f$ , где $n$ — общее количество процессов в системе, а $f$ — максимальное количество процессов, которые могут выйти из строя во время выполнения. Алгоритм выглядит следующим образом:

Писатель

Читатель

ПИШИТЕ(v) т++ отправить (v,t) всем процессам дождитесь получения (nf) подтверждений

ЧИТАТЬ() отправить запрос на чтение всем процессам дождитесь получения (nf) ответов от них выберите v с наибольшим t

Порядок линеаризации операций таков: линеаризовать записи в том порядке, в котором они происходят, и вставить чтение после записи , значение которой оно возвращает. Мы можем проверить, что реализация линеаризуема. Мы можем проверить свойство 2, особенно когда op1 — это запись , а op2 — это чтение , а чтение следует сразу после записи . Мы можем показать от противного. Предположим, что чтение не видит запись , и тогда согласно реализации у нас должно быть два непересекающихся набора размера $(n - f)$ среди n процессов. Так что $2 * (n - f) \leq n$ , что приводит к $n \leq 2 f$ , что противоречит тому факту, что $n > 2 f$ . Так что чтение должно прочитать по крайней мере одно значение, записанное этой записью .

Реализация регистра SWMR из регистров SWSR

Регистр SWMR может быть записан только одним процессом, но может быть прочитан несколькими процессами.

Реализация регистра SWMR с использованием регистров SWSR
Читатели Писатели	⁠ ⁠ $R_{1}$	⁠ ⁠ $R_{2}$	⋯	⁠ ⁠ $R_{n}$
⁠ ⁠ $R_{1}$	А[1,1]	А[1,2]	...	А[1,n]
⁠ ⁠ $R_{2}$	А[2,1]	А[2,2]	...	А[2,n]
⋮	...	...	...	...
⁠ ⁠ $R_{n}$	А[н,1]	А[н,2]	...	А[н,н]
$ж$	А[n+1,1]	А[n+1,2]	...	А[n+1,n]

Пусть n — количество процессов, которые могут читать регистр SWMR. Пусть $R i$ , $0 < i \leq n$ , относится к читателям регистра SWMR. Пусть $w$ — единственный писатель SWMR. На рисунке справа показана конструкция регистра SWMR с использованием массива из $n (n + 1)$ регистров SWSR. Обозначим массив как $A$ . Каждый регистр SWSR $A[i, j]$ доступен для записи $R i ,$ когда $0 < i \leq n$ , и доступен для записи $w ,$ когда $i = n + 1$ . Каждый регистр SWSR $A[i, j]$ доступен для чтения $R j$ . Реализации чтения и записи показаны ниже.

Писатель

ж: ЗАПИСЬ(v)

для j = i..n т++ записать (v,t) в A[n+1,j]конец для

Читатели

$R i$ : ЧИТАТЬ()

для к = 1..(n+1) (V[k],T[k]) <- читать A[k,i]конец длявозьмите k такое, что для всех l, T[k] >= T[l]г <- В[к]т <- Т[к]для j=1..n записать (r,t) в A[i,j]конец длявозврат г

Значение t операции — это значение t, которое она записывает, и операции линеаризуются значениями t. Если запись и чтение имеют одинаковое значение t, упорядочьте запись перед чтением . Если несколько чтений имеют одинаковые значения t, упорядочьте их по времени начала.

Реализация регистра MWMR из объекта SW Snapshot

Мы можем использовать объект SW Snapshot размера n для создания регистра MWMR.

Писатель

Читатели

P _i : ЗАПИСЬ(v)

P _i : ЧИТАТЬ()

((v1, t1), ..., (vn, tn)) <- V.СКАН()пусть t = max(t1, ..., tn) + 1V.ОБНОВЛЕНИЕ(i, (v, t))

В.СКАНвозвращаемое значение с наибольшей временной меткой в результате сканирования

(для разрешения ничьих используйте самую правую пару с наибольшей временной меткой)

Порядок линеаризации следующий. Упорядочить операции записи по t-значениям. Если несколько записей имеют одинаковое t-значение, упорядочить операцию с небольшим идентификатором процесса впереди. Вставить операции чтения сразу после записи , значение которой они возвращают, разрывая связи по идентификатору процесса, и если связь все еще сохраняется, разрывать связи по времени начала.

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

Ссылки

^ ab Kshemkalyani, Ajay D.; Singhal, Mukesh (2008). Распределенные вычисления: принципы, алгоритмы и системы . Кембридж: Cambridge University Press. С. 435–437. ISBN 9780521876346.
^ Аттия, Хагит; Уэлч, Дженнифер (25 марта 2004 г.). Распределенные вычисления: основы, моделирование и продвинутые темы. John Wiley & Sons, Inc. ISBN 978-0-471-45324-6.
^ Аттия, Хагит; Бар-Ной, Амоц; Долев, Дэнни (1990). «Надежное разделение памяти в системах передачи сообщений». Труды девятого ежегодного симпозиума ACM по принципам распределенных вычислений . Том PODC '90. С. 363–375. doi :10.1145/93385.93441. ISBN 089791404X. S2CID 1233774.

[DCFSA-1] Kshemkalyani, Ajay D.; Singhal, Mukesh (2008). Распределенные вычисления: принципы, алгоритмы и системы . Кембридж: Cambridge University Press. С. 435–437. ISBN 9780521876346.

[2] Аттия, Хагит; Уэлч, Дженнифер (25 марта 2004 г.). Распределенные вычисления: основы, моделирование и продвинутые темы. John Wiley & Sons, Inc. ISBN 978-0-471-45324-6.

[3] Аттия, Хагит; Бар-Ной, Амоц; Долев, Дэнни (1990). «Надежное разделение памяти в системах передачи сообщений». Труды девятого ежегодного симпозиума ACM по принципам распределенных вычислений . Том PODC '90. С. 363–375. doi :10.1145/93385.93441. ISBN 089791404X. S2CID 1233774.