Моментальные снимки в разделяемой памяти: различия между версиями

Большинство приведенных ниже алгоритмов используют регистры чтения-записи – самый элементарный тип общих объектов. ''Однорайтерный регистр'' может быть записан только одним процессом; ''мультирайтерный'' – любым процессом. Некоторые алгоритмы, использующие более сильные типы базовых объектов, обсуждаются в разделе [[Не требующие ожидания реализации на основе небольших и более сильных объектов]].

Аттия и Фурэн [5] решают задачу решеточного согласования за O(n) шагов. (В этом случае вместо использования терминологии решеточного согласования алгоритм описывается в терминах реализации моментальных снимков, в котором каждый процесс выполняет не более одной операции снятия моментального снимка). В качестве структуры данных алгоритм использует двумерный массив из O(n2) матриц отражения. Матрица отражения – это объект, который может использоваться двумя процессами для обмена информацией. Каждая матрица отражения строится из двух больших однорайтерных регистров. Каждый процесс выбирает свой путь через массив матриц отражения таким образом, что каждую матрицу посещают не более двух процессов. Каждый элемент матрицы отражения в столбце i используется процессом i для обмена информацией с одним процессом j < i. Если процесс i достигает матрицы первым, то процесс j узнает об обновлении i (если оно было). Если первым ее достигает процесс j, то процесс i узнает всю информацию, которую уже собрал j. (Если оба процесса доходят до матрицы примерно в одно и то же время, то они получают информацию, описанную выше). По мере того как процессы перемещаются из столбца i - 1 в столбец i, процесс, который входит в столбец i в некоторой строке r, собирает всю информацию, которая была собрана любым процессом, который входит в столбец i ниже строки r (и, возможно, больше). Этот инвариант поддерживается соедующим образом: если процесс i передает информацию любому процессу j < i в строке r столбца i, то он также передает эту информацию всем процессам, которые вошли в столбец i выше строки r. Кроме того, процесс i выходит из столбца i в строке, соответствующей количеству информации, которую он узнал, перемещаясь по этому столбцу. Когда процессы достигают крайнего правого столбца массива, процессы, находящиеся в более высоких строках, знают строго больше, чем процессы, находящиеся в более низких строках. Таким образом, порядок линеаризации их сканирования – это порядок выхода из крайнего правого столбца, считая снизу вверх. Упомянутые выше методы Аттии, Херлихи и Рахмана [7, 8] могут быть использованы для снятия ограничения, которое гласит, что каждый процесс выполняет не более одной операции. При этом количество шагов на одну операцию по-прежнему остается O(n).

Все описанные выше реализации без ожидания используют регистры, которые могут хранить Q(m) бит каждый, и поэтому непрактичны в случаях, когда m велико. В этом разделе описываются некоторые реализации на основе небольших объектов, поддерживающих более сильные операции синхронизации, а не только чтения и записи. Объект считается небольшим, если он может хранить O(d + log n + log k) бит. Это означает, что он может содержать постоянное количество значений компонентов, идентификаторов процессов и порядковых номеров.

Аттия, Херлихи и Рахман [ ] предложили элегантное рекурсивное решение проблемы решеточного согласования по принципу «разделяй и властвуй». Разделение процессов на группы для рекурсии может быть выполнено динамически с помощью объектов типа «проверка и установка» (test&set). В результате получается алгоритм снятия моментального снимка, который выполняется за время O(n) на одну операцию и использует O(kn2 log n) небольших однорайтерных регистров и O(knlog2 n) объектов «проверка и установка». (Он требует модификации их предыдущей реализации для замены больших регистров, которые записываются только один раз, на несколько небольших). Используя рандомизацию, каждый объект «проверка и установка» можно заменить однорайтерными регистрами, чтобы получить реализацию моментального снимка, используя только регистры, с O(n) ожидаемых шагов на операцию.

Джаянти [13] представил мультирайтерную реализацию моментального снимка из O(mn2) небольших объектов типа «сравнение с обменом» (compare&swap), в которой обновление занимает O(1) шагов, а сканирование – O(m) шагов. Он начинается с очень простой односканерной и однорайтерной реализации моментального снимка из регистров, которая использует вспомогательный массив для хранения копий последних обновлений. Операция сканирования очищает этот массив, собирает основной массив, а затем собирает вспомогательный, чтобы найти пропущенные обновления. Для получения мультисканерного и мультирайтерного моментального снимка общего вида вводится несколько дополнительных механизмов. В частности, операции сравнения с обменом используются вместо операций записи для координации процессов-райтеров, обновляющих один и тот же компонент, а несколько сканеров координируются друг с другом для имитации работы одного сканера. Алгоритм Джаянти основывается на более ранней работе Риани, Шавита и Туиту [ ], в которой была приведена реализация, достигающая аналогичной сложности, но только для однорайтерного моментального снимка.

Сферы применения моментальных снимков включают распределенные базы данных, хранение контрольных точек или резервных копий для восстановления после ошибок, сборку мусора, обнаружение взаимоблокировок, отладку распределенных программ и получение согласованного представления значений, сообщаемых несколькими датчиками. Моментальные снимки применялись в качестве структурных элементов распределенных решений для задач поиска рандомизированного консенсуса и приближенного соответствия. Они также полезны в качестве примитива для построения других структур данных. Например, рассмотрим реализацию счетчика, который хранит целое число и поддерживает операции инкремента, декремента и чтения. Каждый процесс может хранить количество выполненных им инкрементов за вычетом количества декрементов в своем компоненте однорайтерного объекта типа «моментальный снимок», а счетчик может быть прочитан путем суммирования значений, полученных при сканировании. Ссылки на многие из упомянутых здесь областей применения можно найти в работе [ ].

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