В распределенных вычислениях системы с общей памятью и системы передачи сообщений являются двумя средствами межпроцессного взаимодействия, которые были тщательно изучены. В системах с общей памятью процессы взаимодействуют, обращаясь к общим структурам данных. Общий регистр (чтение/запись) , иногда называемый просто регистром, представляет собой фундаментальный тип общей структуры данных, в которой хранится значение и выполняется две операции: чтение , которая возвращает значение, хранящееся в регистре, и запись , которая обновляет значение . хранится. Другие типы общих структур данных включают чтение-изменение-запись, тестирование и установку, сравнение и замену и т. д. Ячейку памяти, к которой осуществляется одновременный доступ, иногда называют регистром.
Регистры можно классифицировать в соответствии с условием согласованности, которому они удовлетворяют при одновременном доступе, области возможных значений, которые могут быть сохранены, и количеству процессов, которые могут получить доступ с помощью операции чтения или записи , что приводит в общей сложности к 24 типам регистров. [1]
Когда чтение и запись происходят одновременно, значение, возвращаемое чтением, может быть определено не однозначно. Лэмпорт определил три типа регистров: безопасные регистры, обычные регистры и атомарные регистры. [1] Операция чтения безопасного регистра может возвращать любое значение, если она выполняется одновременно с операцией записи, и возвращает значение, записанное самой последней операцией записи , если операция чтения не перекрывается с операцией записи . Обычный регистр отличается от безопасного регистра тем, что операция чтения может возвращать значение, записанное либо самой последней завершенной операцией записи, либо операцией записи, с которой она перекрывается. Атомный регистр удовлетворяет более строгому условию линеаризации .
Регистры можно охарактеризовать тем, сколько процессов могут получить доступ к ним с помощью операций чтения или записи . Регистр с одной записью (SW) может быть записан только одним процессом, а регистр с несколькими записью (MW) может быть записан несколькими процессами. Аналогично, регистр с одним считывателем (SR) может быть прочитан только одним процессом, а регистр с несколькими считывателями (MR) может быть прочитан несколькими процессами. Для регистра SWSR не обязательно, чтобы процессы записи и процесса чтения были одинаковыми.
На рисунке ниже поэтапно показаны конструкции от реализации регистра SWSR в асинхронной системе передачи сообщений до реализации регистра MWMR с использованием объекта SW Snapshot . Подобную конструкцию иногда называют симуляцией или эмуляцией. [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 ] доступен для чтения Rj . Реализации чтения и записи показаны ниже.
T-значение операции — это значение t, которое она записывает, а операции линеаризуются с помощью t-значений. Если запись и чтение имеют одинаковое значение t, заказывайте запись перед чтением . Если несколько операций чтения имеют одинаковые значения t, упорядочите их по времени начала.
Мы можем использовать объект SW Snapshot размера n для создания регистра MWMR.
Порядок линеаризации следующий. Упорядочите операции записи по t-значениям. Если несколько операций записи имеют одинаковое значение t, закажите операцию с небольшим идентификатором процесса впереди. Вставьте read сразу после записи , значение которой они возвращают, разрывая связи по идентификатору процесса, а если они все еще связаны, разрывайте связь по времени начала.
![{\displaystyle {\ce {{\operatorname {Передача сообщений} \atop (MP)~System}->[][{\text{Stage 1}}]SWSR~atomic->[][{\text{Stage 2}}]SWMR->[][{\text{Stage 3}}]SW~снимок->[][{\text{Stage 4}}]MWMR}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/387091ecf014adf7ec21aba60eb20503b6caf4e5)