Общий реестр

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

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

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

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

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

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

Конструкции

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

{\ce {{\operatorname {Message-passing}  \atop (MP)~System}->[][{\text{Stage 1}}]SWSR~atomic->[][{\text{Stage 2}}]SWMR->[][{\text{Stage 3}}]SW~snapshot->[][{\text{Stage 4}}]MWMR}}

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

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

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

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

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

Реализация атомного регистра SWSR в системе MP

The implementation given by Attiya, Bar-Noy and Dolev ^[3] требуется $n > 2 f$ , где $n$ — общее количество процессов в системе, а $f$ — максимальное количество процессов, которые могут завершиться сбоем во время выполнения. Алгоритм следующий:

Писатель	Читатель
WRITE(v) t++ send (v,t) to all processes wait until getting (n-f) acknowledgements	READ() send read request to all processes wait until getting (n-f) responses of them choose v with the biggest t

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

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

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

Реализация регистра SWMR с использованием регистров SWSR
Читатели Писатели	⁠ $R_{1}$ ⁠	⁠ $R_{2}$ ⁠	⋯	⁠ $R_{n}$ ⁠
⁠ $R_{1}$ ⁠	А[1,1]	А[1,2]	...	А[1,п]
⁠ $R_{2}$ ⁠	А[2,1]	А[2,2]	...	А[2,п]
⋮	...	...	...	...
⁠ $R_{n}$ ⁠	А[п,1]	А[n,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]$ доступен для $Rj чтения$ . Реализации чтения и записи показаны ниже.

Писатель

ш: ЗАПИСАТЬ(в)

for j = i..n 
    t++
    write (v,t) in A[n+1,j]
end for

Читатели

$Р я$ : ЧИТАТЬ()

for k = 1..(n+1)
    (V[k],T[k]) <- read A[k,i]
end for
take k such that for all l, T[k] >= T[l]
r <- V[k]
t <- T[k]
for j=1..n
    write (r,t) in A[i,j]
end for
return r

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

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

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

Писатель	Читатели
P _i : ЗАПИСАТЬ (v)	П _я : ЧИТАТЬ()
((v1, t1), ..., (vn, tn)) <- V.SCAN() let t = max(t1, ..., tn) + 1 V.UPDATE(i, (v, t))	V.SCAN return value with largest timestamp, in the result of the scan (разорвите связи, используя крайнюю правую пару наибольшей временной метки)

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

См. также

Ссылки

^ Перейти обратно: ^а ^б Кшемкальяни, Аджай Д.; Сингхал, Мукеш (2008). Распределенные вычисления: принципы, алгоритмы и системы . Кембридж: Издательство Кембриджского университета. стр. 435–437 . ISBN 9780521876346 .
^ Аттия, Хагит; Уэлч, Дженнифер (25 марта 2004 г.). Распределенные вычисления: основы, моделирование и дополнительные темы . Джон Уайли и сыновья, Inc. ISBN 978-0-471-45324-6 .
^ Аттия, Хагит; Бар-Ной, Амоц; Долев, Дэнни (1990). «Надежное совместное использование памяти в системах передачи сообщений». Материалы девятого ежегодного симпозиума ACM по принципам распределенных вычислений . Том. ПОДК '90. стр. 363–375. дои : 10.1145/93385.93441 . ISBN 089791404X . S2CID 1233774 .

[DCFSA-1] Перейти обратно: ^а ^б Кшемкальяни, Аджай Д.; Сингхал, Мукеш (2008). Распределенные вычисления: принципы, алгоритмы и системы . Кембридж: Издательство Кембриджского университета. стр. 435–437 . ISBN 9780521876346 .

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

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

[1]

[2]

[3]