Объекты общих снимков - Shared snapshot objects

В распределенных вычислений, а общий объект моментального снимка это тип структура данных, который используется несколькими потоки или процессы. Для многих задач важно иметь структура данных, который может обеспечить непротиворечивое представление о состоянии памяти. На практике оказывается, что невозможно получить такое согласованное состояние памяти, просто обращаясь к одному общий регистр после другого, поскольку значения, хранящиеся в отдельных регистрах, могут быть изменены в любое время в течение этого процесса. Чтобы решить эту проблему, объекты моментальных снимков хранят вектор п компоненты и предоставьте следующие два атомный операции: обновление (я, v) изменяет значение в яй компонент v, и сканирование () возвращает значения, хранящиеся во всех п составные части.^[1][2]Объекты моментальных снимков могут быть построены с использованием атомарной системы чтения с одной записью и несколькими устройствами чтения. общие регистры.

В общем, различают объекты моментальных снимков с одним записывающим устройством и несколькими устройствами чтения (swmr) и объекты моментальных снимков с несколькими записывающими устройствами и несколькими устройствами чтения (mwmr). В объекте моментального снимка swmr количество компонентов соответствует количеству процессов, и только один процесс п_я разрешена запись в позицию памяти я а всем остальным процессам разрешено читать память. Напротив, в объекте моментального снимка mwmr всем процессам разрешена запись во все позиции памяти, а также разрешено чтение памяти.

Общий

А Общая память разделен на несколько частей. Каждая из этих частей содержит одно значение данных. В случае с одним писателем и несколькими читателями каждый процесс п_я имеет позицию памяти я назначен, и только этому процессу разрешена запись в позицию памяти. Однако каждому процессу разрешено читать любую позицию в памяти. В случае с несколькими записывающими устройствами и несколькими считывающими устройствами ограничение изменяется, и любому процессу разрешается изменять любую позицию в памяти. Любой процесс п_я ${\displaystyle \in }$ {1,...,п} в п-процессная система может выполнять две операции над объектом моментального снимка: сканирование () и обновление (я, v). В сканировать операция не имеет аргументов и возвращает согласованное представление памяти. В обновление (я, v) операция обновляет память в позиции я со значением v.

Считается, что оба типа операций выполняются атомарно между вызовом процессом и возвратом из памяти. Вообще говоря, в векторе данных ${\displaystyle {\overline {d}}}$ каждая запись d_k соответствует аргументу последнего линеаризованный Обновить операция, обновляющая часть k памяти.^[1]

Чтобы получить все преимущества общих объектов моментальных снимков, с точки зрения упрощения проверок и построений, к построению объектов моментальных снимков добавлены два других ограничения.^[1] Первое ограничение является архитектурным, то есть любой объект моментального снимка создается только с регистры с одной записью и несколькими считывателями как основной элемент. Это возможно для моментальных снимков с одной записью и несколькими читателями. Для объектов моментальных снимков с несколькими записывающими устройствами и несколькими устройствами чтения можно использовать регистры с несколькими считывателями и несколькими записывающими устройствами, который, в свою очередь, может быть построен из регистров с одной записью и несколькими считывателями.^[1][3][4]

В распределенных вычислениях построение системы обусловлено целью, чтобы вся система прогрессировала во время выполнения. Таким образом, поведение процесса не должно приводить к остановке всей системы (Блокировка-свобода ). Более сильная версия этого - свойство ждать-свобода, что означает, что ни один процесс не может помешать другому процессу завершить свою работу. В более общем смысле это означает, что каждая операция должна завершаться после конечного числа шагов независимо от поведения других процессов. Очень простой алгоритм моментальных снимков гарантирует прогресс в масштабах всей системы, но без блокировки. Этот алгоритм легко расширить до без ожидания. Алгоритм Afek et al.,^[1] который представлен в разделе Выполнение имеет это свойство.

Выполнение

Существует несколько методов реализации общих объектов моментальных снимков. Первый представленный алгоритм обеспечивает принципиальную реализацию объектов моментального снимка. Однако эта реализация предоставляет только свойство свобода от замков. Вторая представленная реализация, предложенная Afek et al.^[1] имеет более сильное свойство, называемое ждать-свобода. Обзор других реализаций дан Fich.^[2]

Базовый алгоритм моментальных снимков swmr

Основная идея этого алгоритма состоит в том, что каждый процесс, выполняющий сканирование () операций, дважды читает все значения из памяти. Если алгоритм дважды считывает одно и то же содержимое памяти, никакой другой процесс не изменил промежуточное значение, и он не может вернуть результат. Процесс, который выполняет обновление (я, v) операции, просто обновите его значение в памяти.

функция сканирование () пока истинный        a [1..n]: = собирать; b [1..n]: = собрать; если (∀i∈ {1, .., n} местоположение i не было изменено между его чтениями во время двух сборов)) тогда            return b; // успешный двойной сбор петляконец

функция update (i, v) M [i]: = v;конец

Рис.1: Один процесс всегда обновляет память во время двойного сбора данных другим процессом. Таким образом, процесс сканирования никогда не может завершиться.

Этот алгоритм обеспечивает очень простую реализацию объектов моментальных снимков. Это гарантирует, что система продолжает работать, в то время как отдельные потоки могут зависнуть из-за поведения отдельных процессов. Процесс п_я может предотвратить другой процесс п_j от прекращения сканирование () операция, всегда меняя свое значение, между двумя накоплениями памяти. Таким образом, алгоритм без блокировки, но нет без ожидания. Чтобы усилить это свойство, ни один процесс не должен останавливаться из-за поведения других процессов. Рисунок 1 иллюстрирует проблему. Пока п₁ пытается выполнить сканирование () операция, второй процесс п₂ всегда беспокоит "двойной сбор". Таким образом, процесс сканирования всегда должен перезапускать операцию и никогда не может прекратиться и прекратиться.

Реализация Single-Writer Multi-Reader от Afek et al.

Основная идея алгоритма моментальных снимков swmr, разработанная Afek et al. заключается в том, что процесс может определить, изменил ли другой процесс свое расположение в памяти, и что процессы помогают друг другу. Чтобы определить, изменил ли другой процесс свое значение, к каждому регистру прикрепляется счетчик, и процесс увеличивает счетчик при каждом обновлении. Вторая идея заключается в том, что каждый процесс, который обновляет свою позицию в памяти, также выполняет сканирование () операции и предоставляет свое "представление о памяти" в своем регистре другим процессам. Процесс сканирования может позаимствовать это сканировать результат и вернуть его.

На основе безграничной памяти

Используя эту идею, можно построить без ожидания алгоритм, использующий регистры неограниченного размера. Процесс, выполняющий операцию обновления, может помочь процессу завершить сканирование. Основная идея заключается в том, что если процесс видит, что другой процесс дважды обновляет ячейку памяти, этот процесс должен выполнить полное, линеаризованный, операция обновления между ними. Для реализации этого каждый Обновить операция сначала выполняет сканировать памяти, а затем атомарно записывает значение моментального снимка вместе с новым значением v и порядковый номер. Если процесс выполняет сканирование памяти и обнаруживает, что процесс обновил часть памяти дважды, он может «позаимствовать» «встроенное» сканирование обновления для завершения сканировать операция.^[1]

функция scan () // возвращает согласованный вид памяти за j = 1 к п делать перемещен [j]: = 0 конец    пока истинный делать        a [1..n]: = собирать; // собирает (данные, последовательность, представление) троек b [1..n]: = collect; // собирает (данные, последовательность, представление) троек если (∀j∈ {1, ..., n}) (a [j] .seq = b [j] .seq) тогда            возвращаться (b [1] .data, ..., b [n] .data) // ни один процесс не изменил память еще для  j = 1 к п делать            если a [j] .seq ≠ b [j] .seq тогда                 // процесс перемещен если перемещен [j] = 1 тогда                    // процесс уже перемещался раньше возвращаться b [j] .view; еще перемещено [j]: = перемещено [j] + 1; конец    конецконечная функция

процедура Обновить(я,v) // обновляет регистры значениями данных, обновляет порядковый номер, встроенное сканирование s [1..n]: = scan; // встроенное сканирование rя : = (v, rя.seq = rя.seq + 1, s [1..n]);конец процедуры

Рис.2: Пример порядка линеаризации для объекта моментального снимка с одним записывающим устройством и несколькими читателями. Первое сканирование () может успешно выполнить двойной сбор, в то время как «двойной сбор» второго сканирования дважды прерывается вторым процессом. Таким образом, процесс заимствует встроенное сканирование.

Каждый регистр состоит из поля для значения данных, порядкового номера и поля для результата последнего встроенного сканирования, собранного перед последним обновлением. В каждой операции сканирования процесс п_я может решить, изменил ли процесс свою память, используя порядковый номер. Если во время двойного сбора в памяти нет изменений, п_я может вернуть результат второго сканирования. Как только процесс замечает, что другой процесс обновил память между ними, он сохраняет эту информацию в перемещенном поле. Если процесс п_j дважды менял свою память во время выполнения сканирования (), процесс сканирования п_я может вернуть встроенное сканирование процесса обновления, которое он сохранил в собственном реестре во время операции обновления.

Эти операции могут быть линеаризованный путем линеаризации каждой операции update () при ее записи в регистр. Операцию сканирования сложнее линеаризовать. Если двойной сбор операции сканирования успешен, операция сканирования может быть линеаризована в конце второго сканирования. В другом случае - один процесс обновил свой регистр два раза - операция может быть линеаризована в то время, когда процесс обновления собирает свое встроенное сканирование перед записью его значения в регистр.^[1]

На основе ограниченной памяти

Одним из ограничений представленного алгоритма является то, что он основан на безграничная память поскольку порядковый номер будет постоянно увеличиваться. Чтобы преодолеть это ограничение, необходимо ввести другой способ определения того, дважды ли процесс менял свою позицию в памяти. Каждая пара процессов ${\displaystyle \langle P_{i},P_{j}\rangle }$ обменивается данными с помощью двух регистров с одной записью и одним считывателем (swsr), которые содержат два атомных бита. Прежде чем процесс начинает выполнять «двойной сбор», он копирует значение своего партнерского процесса в свой собственный регистр. Если сканер-процесс п_я замечает после выполнения "двойного сбора", что ценность партнерского процесса п_j изменилось, это указывает на то, что процесс выполнил операцию обновления памяти.^[1]

функция сканирование () // возвращает согласованный вид памяти    за j = 1 к п делать перемещен [j]: = 0 конец    пока истинный делать        за j = 1 к п делать qя, j : = rj.пj, я конец        a [1..n]: = собирать; // собирает троек (данные, бит-вектор, переключение, просмотр)        b [1..n]: = собрать; // собирает троек (данные, бит-вектор, переключение, просмотр)        если (∀j∈ {1, ..., n}) (a [j] .pj, я = b [j] .pj, я = qя, j) и a [j] .toggle = b [j] .toggle тогда            возвращаться (b [1]. данные, ..., b [n]. данные) // ни один процесс не изменил память        еще для  j = 1 к п делать            если (a [j] .pj, я ≠ qя, j) или же (b [j] .pj, я ≠ qя, j) или же (a [j] .toggle ≠ b [j] .toggle) тогда // процесс j выполнил обновление                если перемещено [j] = 2 тогда                   // процесс уже перемещался раньше                    возвращаться b [j] .view; еще перемещено [j]: = перемещено [j] + 1; конец    конецконечная функция

процедура Обновить(я,v)                        // обновляет регистры значением данных, "состояние записи" всех регистров, инвертирует бит переключения и встроенное сканирование    за j = 1 к п делать f [j]: = ¬qj, я конец    s [1..n]: = сканирование; // встроенное сканирование    ря : = (v, f [1..n], ¬rя.toggle, s [1..n]);конец процедуры

Неограниченный порядковый номер заменяется двумя рукопожатие биты для каждой пары процессов. Эти биты подтверждения основаны на регистрах swsr и могут быть выражены матрицей M, где процесс п_я разрешено писать в строку я и ему разрешено читать биты подтверждения в столбце я. Прежде чем процесс сканирования выполнит двойной сбор, он собирает все биты подтверждения из всех регистров, считывая свой столбец. Впоследствии он может решить, изменил ли процесс свое значение во время двойного значения или нет. Следовательно, процессу просто нужно снова сравнить столбец с первоначально прочитанными битами подтверждения. Если бы только один процесс п_j написал дважды, во время сбора п_я возможно, что биты подтверждения не изменятся во время сканирования. Таким образом, необходимо ввести еще один бит, называемый «бит переключения», этот бит изменяется при каждой записи. Это позволяет различать две последовательные записи, даже если ни один другой процесс не обновил свой регистр. Этот подход позволяет заменять неограниченные порядковые номера битами подтверждения, не изменяя ничего другого в процедуре сканирования.

Пока процесс сканирования п_я использует бит подтверждения, чтобы определить, может ли он использовать свой двойной сбор или нет, другие процессы также могут выполнять операции обновления. В качестве первого шага они снова считывают биты подтверждения, предоставленные другими процессами, и генерируют их дополнение. Впоследствии эти процессы снова генерируют встроенное сканирование и сохраняют обновленное значение данных, собранные - дополненные - биты подтверждения, дополненный бит переключения и встроенное сканирование в регистр.

Поскольку биты квитирования эквивалентно заменяют порядковые номера, линеаризация то же, что и в случае неограниченной памяти.

Реализация Multi-Writer Multi-Reader, разработанная Afek et al.

Создание объекта моментального снимка с несколькими записывающими устройствами и несколькими читателями предполагает, что п процессам разрешено писать в любое место в памяти, которое состоит из м регистры. Таким образом, между идентификатором процесса и местом в памяти больше нет корреляции. Следовательно, больше невозможно связывать биты подтверждения или встроенное сканирование с полями данных. Следовательно, биты подтверждения, память данных и встроенное сканирование не могут храниться в одном регистре, и запись в память больше не является атомарной операцией.

Рис.3: Показывает примерную линеаризацию для объекта моментального снимка с несколькими записывающими устройствами и несколькими читателями.

Следовательно Обновить() процесс должен обновлять три разных регистра независимо. Сначала он должен сохранить считанные биты подтверждения, затем выполнить встроенное сканирование и, наконец, сохранить свое значение в назначенной позиции памяти. Кажется, что каждая запись независимо выполняется атомарно, но вместе это не так. Новый Обновить() процедура приводит к некоторым изменениям в сканирование () функция. Уже недостаточно просто прочитать биты подтверждения и дважды собрать содержимое памяти. Чтобы обнаружить начало Обновить Процесс должен собрать биты подтверждения во второй раз после сбора содержимого памяти.

Если двойной сбор не удается, теперь необходимо, чтобы процесс видел, как другой процесс перемещается три раза, прежде чем заимствовать встроенное сканирование. Рисунок 3 иллюстрирует проблему. Первый двойной сбор не удается, потому что Обновить процесс запущен до того, как операция сканирования завершит запись в память во время первого двойного сбора. Однако встроенное сканирование этой записи выполняется и сохраняется до п₁ начинает сканирование памяти и, следовательно, нет действительной точки линеаризации. Второй двойной сбор не выполняется, потому что процесс п₂ начинает вторую запись и обновляет биты квитирования. В сценарии swmr мы теперь заимствуем встроенное сканирование и возвращаем его. В сценарии mwmr это невозможно, потому что встроенное сканирование со второго записывать все еще не линеаризуется в пределах интервала сканирования (начало и конец операции). Таким образом, процесс должен увидеть третье изменение от другого процесса, чтобы быть полностью уверенным, что по крайней мере одно встроенное сканирование было линеаризовано в течение интервала сканирования. После третьего изменения одним процессом процесс сканирования может заимствовать старое значение памяти без нарушения критерия линеаризации.

Сложность

Базовая представленная реализация общих объектов моментальных снимков Afek et al. потребности ${\displaystyle O(n^{2})}$ операции с памятью.^[1] Другая реализация Андерсона, которая была разработана независимо, требует экспоненциального количества операций. ${\displaystyle O(2^{n})}$.^[5] Существуют также рандомизированные реализации объектов моментальных снимков на основе регистров swmr с использованием ${\displaystyle O(n\log ^{2}n)}$ операции.^[6] Другая реализация Израиля и Ширази, использующая неограниченную память, требует ${\displaystyle O(n^{3/2}\log ^{2}n)}$ операции с памятью.^[7][8] Israel et al. покажите в другой работе нижнюю границу низкоуровневых операций для любой операции обновления. Нижняя граница ${\displaystyle \Omega (\min\{w,r\})}$, куда ш количество обновлений и р количество сканеров. Аттия и Рахман представляют детерминированный алгоритм моментальных снимков, основанный на регистрах swmr, который использует ${\displaystyle O(n\log n)}$ операций на обновление и сканирование.^[8] Применение общего метода по Израилю, Шахаму и Ширази ^[9] это может быть улучшено до неограниченного алгоритма моментального снимка, который требует только ${\displaystyle O(n\log n)}$ операций за сканирование и ${\displaystyle O(n)}$ операций на обновление. Есть дальнейшие улучшения, внесенные Иноуэ и др.,^[10] используя только линейное количество операций чтения и записи. В отличие от других представленных методов, этот подход использует регистры mwmr, а не регистры swmr.

Приложения

Есть несколько алгоритмы в распределенных вычислений которые можно упростить в дизайне и / или проверке с помощью общих объектов моментальных снимков.^[1] Примеры этого - проблемы исключения,^[11][12][13] параллельные системы отметок времени,^[14] примерное согласие,^[15] рандомизированный консенсус^[16][17] и реализации других структур данных без ожидания.^[18] С помощью объектов моментальных снимков mwmr также можно создать атомарный мульти-писатель и мульти-ридер. регистры.

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

• Общий реестр
• Общая память (межпроцессное взаимодействие)
• Общая архитектура памяти
• Распределенная разделяемая память
• Линеаризуемость

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

1. Афек, Иегуда; Аттия, Хагит; Долев, Дэнни; Гафни, Эли; Мерритт, Майкл; Шавит, Нир (сентябрь 1993 г.). «Атомарные снимки общей памяти». J. ACM. 40 (4): 873–890. Дои:10.1145/153724.153741.
2. Фич, Фейт Эллен (2005). «Насколько сложно сделать снимок?». СОФСЕМ 2005: Теория и практика информатики. Конспект лекций по информатике. 3381 (SOFSEM 2005: Теория и практика компьютерных наук ред.). Springer Berlin Heidelberg. С. 28–37. Дои:10.1007/978-3-540-30577-4_3. ISBN  978-3-540-24302-1.
3. Ли, Мин; Тромп, Джон; Витани, Пол М. Б. (июль 1996 г.). «Как совместно использовать параллельные переменные без ожидания». J. ACM. 43 (4): 723–746. CiteSeerX  10.1.1.56.3236. Дои:10.1145/234533.234556.
4. Петерсон, Гэри Л; Бернс, Джеймс Э. (1987). «Одновременное чтение во время записи II: случай нескольких писателей». Основы компьютерных наук, 1987., 28-й ежегодный симпозиум по. С. 383–392.
5. Андерсон, Джеймс Х (1993). «Составные регистры». Распределенных вычислений. 6 (3): 141–154. Дои:10.1007 / BF02242703.
6. Аттия, Хагит; Хелихи, Морис; Рахман, Офир (1995). «Атомные снимки с использованием решеточного соглашения». Распределенных вычислений. 8 (3): 121–132. Дои:10.1007 / BF02242714.
7. Израильский, Амос; Ширази, Асаф (1992). «Эффективный протокол моментальных снимков с использованием 2-решеточного соглашения». Рукопись.
8. Аттия, Хагит; Рахман, Офир (апрель 1998 г.). «Атомарные снимки за O (n log n) операций». SIAM Журнал по вычислениям. 27 (2): 319–340. Дои:10.1145/164051.164055.
9. Израильский, Амос; Шахам, Амнон; Ширази, Асаф (1993). «Протоколы моментальных снимков в линейном времени для несбалансированных систем». Распределенные алгоритмы. Springer. С. 26–38. Дои:10.1007/3-540-57271-6_25. ISBN  978-3-540-57271-8.
10. Иноуэ, Мичико; Масудзава, Тосимицу; Чен, Вэй; Токура, Нобуки (1994). Снимок в линейном времени с использованием регистров с несколькими записывающими устройствами и несколькими считывающими устройствами. Распределенные алгоритмы. 857. Springer. С. 130–140. Дои:10.1007 / BFb0020429. ISBN  978-3-540-58449-0.
11. Долев, Дэнни; Гафни, Эли; Шавит, Нир (1988). «К неатомной эре: l-исключение как тестовый пример». Материалы двадцатого ежегодного симпозиума ACM по теории вычислений. С. 78–92.
12. Кацефф, Говард П. (1978). «Новое решение проблемы критического сечения». Материалы десятого ежегодного симпозиума ACM по теории вычислений.. С. 86–88.
13. Лэмпорт, Лесли (1988). «Проблема взаимного исключения: часть II - постановка и решения». Журнал ACM. 33 (2): 327–348. CiteSeerX  10.1.1.32.9808. Дои:10.1145/5383.5385.
14. Долев, Дэнни; Шавит, Нир (1989). «Ограниченные одновременные системы отметок времени могут быть сконструированы». Материалы двадцать первого ежегодного симпозиума ACM по теории вычислений. ACM. С. 454–466.
15. Аттия, Хагит; Линч, Нэнси; Шавит, Нир (1990). «Быстро ли работают алгоритмы без ожидания?». Основы компьютерных наук, 1990. Труды., 31-й ежегодный симпозиум по. С. 55–64.
16. Абрахамсон, Карл (1988). «О достижении консенсуса с использованием общей памяти». Материалы седьмого ежегодного симпозиума ACM по принципам распределенных вычислений. С. 291–302.
17. Аттия, Хагит; Долев, Дэнни; Шавит, Нир (1989). Ограниченный полиномиальный рандомизированный консенсус. Материалы восьмого ежегодного симпозиума ACM по принципам распределенных вычислений. С. 281–293.
18. Аспнес, Джеймс; Херлихи, Морис (1990). «Структуры данных без ожидания в асинхронной модели PRAM». Материалы второго ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам. ACM. С. 340–349.