Общий реестр - Shared register

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

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

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

Классификация общего реестра

Условие согласованности	Домен	Написать	Читать
безопасный обычный атомный	двоичный целое число	писатель-одиночка мульти-писатель	один читатель мульти-ридер

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

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

Конструкции

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

${\displaystyle {\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}}}$
 

Этапы строительства с общим регистром

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

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

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

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

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

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

Писатель	Читатель
ЗАПИСЫВАТЬ(v) т++ Отправить (v,т) к все процессы ждать до того как получающий (п-ж) благодарности	ЧИТАТЬ() Отправить читать запрос к все процессы ждать до того как получающий (п-ж) ответы из их выберите v с то самый большой т

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

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

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

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

Читатели Писатели	${\displaystyle R_{1}}$	${\displaystyle R_{2}}$	⋯	${\displaystyle R_{1}}$
${\displaystyle R_{1}}$	А [1,1]	А [1,2]	⋯	A [1, n]
${\displaystyle R_{2}}$	A [2,1]	А [2,2]	⋯	A [2, n]
⋮	⋯	⋯	⋯	⋯
${\displaystyle R_{n}}$	A [n, 1]	A [n, 2]	⋯	Анна]
ш	А [n + 1,1]	A [n + 1,2]	⋯	A [n + 1, n]

Пусть n будет количеством процессов, которые могут читать регистр SWMR. Пусть R_я, 0 я когда 0 j. Реализации читать и записывать показаны ниже.

Писатель	w: ЗАПИСАТЬ (v)	для j = i..n t ++ напишите (v, t) в A [n + 1, j] конец для
Читатели	ря: ЧИТАТЬ()	for k = 1 .. (n + 1) (V [k], T [k]) <- читать A [k, i] end для такого k, что для всех l, T [k]> = T [l] r <- V [k] t <- T [k] для j = 1..n записываем (r, t) в A [i, j] end for return r

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

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

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

Писатель	Читатели
пя: ЗАПИСАТЬ (v)	пя: ЧИТАТЬ()
((v1, t1),…, (vn, tn)) <- V.SCAN () пусть t = max (t1,…, tn) + 1V.UPDATE (i, (v, t))	V.SCAN - вернуть значение с наибольшей отметкой времени в результате сканирования. (разорвать связи, используя крайнюю правую пару наибольших отметок времени)

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

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

• Регистр оборудования
• Распределенная разделяемая память
• Объекты общих снимков

Рекомендации

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