Общие объекты моментального снимка

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

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

Общий

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

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

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

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

Выполнение

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

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

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

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

обновление функции (i, v) М[i] := v;конец

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

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

Основная идея алгоритма моментального снимка swmr Афека и др. заключается в том, что процесс может определить, изменил ли другой процесс свое местоположение в памяти, и что процессы помогают друг другу. Чтобы определить, изменил ли другой процесс свое значение, к каждому регистру присоединяется счетчик, и процесс увеличивает счетчик при каждом обновлении. Вторая идея заключается в том, что каждый процесс, который обновляет свое местоположение в памяти, также выполняет scan()операцию и предоставляет свой «вид памяти» в своем регистре другим процессам. Процесс сканирования может заимствовать этот scanрезультат и возвращать его.

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

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

функция scan() // возвращает согласованный вид памяти для j = 1 to n do moved[j] := 0 end  while true do a[1..n] := collect; // собирает (данные, последовательность, представление) тройки b[1..n] := collect; // собирает (данные, последовательность, представление) тройки if (∀j∈{1, ..., n}) (a[j].seq = b[j].seq) then  return (b[1].data, ..., b[n].data) // ни один процесс не изменил память else for j = 1 to n do  if a[j].seq ≠ b[j].seq then // процесс перемещен if moved[j] = 1 then // процесс уже перемещен ранее return b[j].view; else moved[j] := moved[j] + 1; end  end end function

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

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

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

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

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

function scan() // возвращает согласованное представление памяти  for j=1 to n do moved[j] := 0 end  while true do  for j=1 to n do q _i,j  := r _j .p _j,i end a[1..n] := collect; // собирает (данные, битовый вектор, переключение, представление) тройки b[1..n] := collect; // собирает тройки (данные, битовый вектор, переключение, представление)  if (∀j∈{1, ...,n}) (a[j].p _j,i = b[j].p _j,i = q _i,j ) and a[j].toggle = b[j].toggle then  return (b[1].data, ..., b[n].data) // ни один процесс не изменил память  else for j=1 to n do  if (a[j].p _j,i ≠ q _i,j ) or (b[j].p _j,i ≠ q _i,j ) or (a[j].toggle ≠ b[j].toggle) then  // процесс j выполнил обновление  if moved[j] = 2 then  // процесс уже перемещен до этого  return b[j].view; else moved[j] := moved[j] + 1; end  end end function

procedure update( i , v ) // обновляет регистры значением данных, "состоянием записи" всех регистров, инвертирует бит переключения и встроенное сканирование  для j = 1 до n do f[j] := ¬q _j,i end s[1..n] := scan; // встроенное сканирование r _i  := (v, f[1..n], ¬r _i .toggle, s[1..n]); конец процедуры

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

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

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

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

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

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

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

Сложность

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

Приложения

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

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

Ссылки

^ abcdefghijk Афек, Иегуда ; Аттия, Хагит ; Долев, Дэнни ; Гафни, Эли; Мерритт, Майкл; Шавит, Нир (сентябрь 1993 г.). «Атомные снимки общей памяти». Дж. АКМ . 40 (4): 873–890. дои : 10.1145/153724.153741 . S2CID 52150066.
^ ab Fich, Faith Ellen (2005). "How Hard is It to Take a Snapshot?". SOFSEM 2005: Theory and Practice of Computer Science . Lecture Notes in Computer Science. Vol. 3381 (ред. SOFSEM 2005: Theory and Practice of Computer Science). Springer Berlin Heidelberg. стр. 28–37. doi :10.1007/978-3-540-30577-4_3. ISBN 978-3-540-24302-1.
^ Ли, Минг; Тромп, Джон; Витаний, Пол МБ (июль 1996 г.). «Как совместно использовать параллельные переменные без ожидания». J. ACM . 43 (4): 723–746. CiteSeerX 10.1.1.56.3236 . doi :10.1145/234533.234556. S2CID 15035117.
^ Петерсон, Гэри Л.; Бернс, Джеймс Э. (1987). «Одновременное чтение во время письма ii: случай нескольких авторов». Основы компьютерной науки, 1987., 28-й ежегодный симпозиум по . стр. 383–392.
^ Андерсон, Джеймс Х (1993). «Составные регистры». Распределенные вычисления . 6 (3): 141–154. doi :10.1007/BF02242703. S2CID 1688458.
^ Аттия, Хагит; Хелихи, Морис; Рахман, Офир (1995). «Атомные снимки с использованием соглашения о решетке». Распределенные вычисления . 8 (3): 121–132. дои : 10.1007/BF02242714. S2CID 26538026.
^ Израэли, Амос; Ширази, Асаф (1992). «Эффективный протокол моментального снимка с использованием соглашения о двух решетках». Рукопись .
^ ab Attiya, Hagit; Rachman, Ophir (апрель 1998 г.). «Атомарные снимки в операциях O( n log n )». SIAM Journal on Computing . 27 (2): 319–340. doi :10.1145/164051.164055. S2CID 15199715.
^ Израэли, Амос; Шахам, Амнон; Ширази, Асаф (1993). «Протоколы моментальных снимков с линейным временем для несбалансированных систем». Распределенные алгоритмы . Springer. стр. 26–38. doi :10.1007/3-540-57271-6_25. ISBN 978-3-540-57271-8.
^ Иноуэ, Мичико; Масудзава, Тошимицу; Чен, Вэй; Токура, Нобуки (1994). Линейный моментальный снимок с использованием регистров с несколькими записями и несколькими чтениями . Т. 857. Springer. С. 130–140. doi :10.1007/BFb0020429. ISBN 978-3-540-58449-0. {{cite book}}: |work=проигнорировано ( помощь )
^ Долев, Дэнни; Гафни, Эли; Шавит, Нир (1988). «К неатомной эре: l-исключение как тестовый случай». Труды двадцатого ежегодного симпозиума ACM по теории вычислений . С. 78–92.
^ Katseff, Howard P (1978). «Новое решение проблемы критической секции». Труды десятого ежегодного симпозиума ACM по теории вычислений . С. 86–88.
^ Лампорт, Лесли (1988). «Проблема взаимного исключения: часть II — утверждение и решения». Журнал ACM . 33 (2): 327–348. CiteSeerX 10.1.1.32.9808 . doi :10.1145/5383.5385. S2CID 7387839.
^ Долев, Дэнни; Шавит, Нир (1989). «Ограниченные параллельные системы с временными метками являются конструируемыми». Труды двадцать первого ежегодного симпозиума ACM по теории вычислений . ACM. С. 454–466.
^ Аттия, Хагит; Линч, Нэнси; Шавит, Нир (1990). «Являются ли алгоритмы без ожидания быстрыми?». Основы компьютерной науки, 1990. Труды., 31-й ежегодный симпозиум по . стр. 55–64.
^ Абрахамсон, Карл (1988). «О достижении консенсуса с использованием общей памяти». Труды седьмого ежегодного симпозиума ACM по принципам распределенных вычислений . С. 291–302.
^ Аттия, Хагит; Долев, Дэнни; Шавит, Нир (1989). Ограниченный полиномиальный рандомизированный консенсус . С. 281–293. {{cite book}}: |work=проигнорировано ( помощь )
^ Аспнес, Джеймс; Херлихи, Морис (1990). «Структуры данных без ожидания в асинхронной модели PRAM». Труды второго ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам . ACM. С. 340–349.