4511
правок
Моментальные снимки в разделяемой памяти: различия между версиями
Материал из WEGA
Моментальные снимки в разделяемой памяти (посмотреть исходный код)
Версия от 18:37, 16 сентября 2024
, 16 сентябрь→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
'''Простая неблокирующая реализация на основе небольших регистров''' | '''Простая неблокирующая реализация на основе небольших регистров''' | ||
Предположим, что каждый компонент однорайтерного объекта моментального снимка представлен однорайтерным регистром. Процесс i выполняет операцию обновления update(i, v), записывая v и порядковый номер в регистр i и увеличивая его порядковый номер. Выполнить операцию сканирования сложнее, чем просто прочитать каждый из m регистров, поскольку в процессе чтения некоторые регистры могут измениться. Чтобы выполнить сканирование, процесс неоднократно считывает все регистры. Последовательность считываний всех регистров называется сбором. Если два сбора возвращают один и тот же вектор, то сканирование возвращает этот вектор (с удаленными порядковыми номерами). Порядковые номера гарантируют, что если одно и то же значение читается в регистре дважды, то регистр имел это значение в течение всего интервала между двумя считываниями. Сканирование может быть назначено точкой линеаризации между двумя одинаковыми сборами, а обновления линеаризуются при выполнении записи. Этот алгоритм является неблокирующим, поскольку сканирование продолжается только в том случае, если во время каждого сбора завершается хотя бы одна операция обновления. Аналогичный алгоритм с идентификаторами процессов, добавляемыми к номерам последовательностей, реализует неблокирующий мультирайтерный моментальный снимок из m мультирайтерных регистров. | Предположим, что каждый компонент однорайтерного объекта моментального снимка представлен однорайтерным регистром. Процесс i выполняет операцию обновления update(i, v), записывая v и порядковый номер в регистр i и увеличивая его порядковый номер. Выполнить операцию сканирования сложнее, чем просто прочитать каждый из m регистров, поскольку в процессе чтения некоторые регистры могут измениться. Чтобы выполнить сканирование, процесс неоднократно считывает все регистры. Последовательность считываний всех регистров называется ''сбором''. Если два сбора возвращают один и тот же вектор, то сканирование возвращает этот вектор (с удаленными порядковыми номерами). Порядковые номера гарантируют, что если одно и то же значение читается в регистре дважды, то регистр имел это значение в течение всего интервала между двумя считываниями. Сканирование может быть назначено точкой линеаризации между двумя одинаковыми сборами, а обновления линеаризуются при выполнении записи. Этот алгоритм является неблокирующим, поскольку сканирование продолжается только в том случае, если во время каждого сбора завершается хотя бы одна операция обновления. Аналогичный алгоритм с идентификаторами процессов, добавляемыми к номерам последовательностей, реализует неблокирующий мультирайтерный моментальный снимок из m мультирайтерных регистров. | ||
'''Не требующие ожидания реализации на основе больших регистров''' | '''Не требующие ожидания реализации на основе больших регистров''' | ||
Афек и др. [1] предложили способ модификации неблокирующего однорайтерного алгоритма выполнения моментального снимка, позволяющий сделать его свободным от ожидания, используя сканирование, встроенное в операции обновления. Обновление update(i, v) сначала выполняет сканирование, а затем записывает тройку, содержащую результат сканирования, v и порядковый номер, в регистр i. Пока процесс P неоднократно выполняет процесс сбора для выполнения сканирования, имеет место одна из двух ситуаций: либо два сбора возвращают один и тот же вектор (который P может вернуть), либо P в конце концов увидит три разные тройки в регистре какого-то другого процесса. В последнем случае третья тройка, которую увидел P, должна содержать вектор, являющийся результатом сканирования, начавшегося уже после сканирования P, поэтому сканирование P выводит этот вектор. Обновлениям и сканированиям, которые завершаются после просмотра двух идентичных сборов, назначаются точки линеаризации описанным ранее способом. Если один скан получает свой вывод от встроенного скана, то оба скана получают одну и ту же точку линеаризации. Это не требующая ожидания реализация однорайтерного моментального снимка из n однорайтерных регистров по (n + 1)d + log k бит каждый. Операции выполняются за O( | Афек и др. [1] предложили способ модификации неблокирующего однорайтерного алгоритма выполнения моментального снимка, позволяющий сделать его свободным от ожидания, используя сканирование, встроенное в операции обновления. Обновление update(i, v) сначала выполняет сканирование, а затем записывает тройку, содержащую результат сканирования, v и порядковый номер, в регистр i. Пока процесс P неоднократно выполняет процесс сбора для выполнения сканирования, имеет место одна из двух ситуаций: либо два сбора возвращают один и тот же вектор (который P может вернуть), либо P в конце концов увидит три разные тройки в регистре какого-то другого процесса. В последнем случае третья тройка, которую увидел P, должна содержать вектор, являющийся результатом сканирования, начавшегося уже после сканирования P, поэтому сканирование P выводит этот вектор. Обновлениям и сканированиям, которые завершаются после просмотра двух идентичных сборов, назначаются точки линеаризации описанным ранее способом. Если один скан получает свой вывод от встроенного скана, то оба скана получают одну и ту же точку линеаризации. Это не требующая ожидания реализация однорайтерного моментального снимка из n однорайтерных регистров по (n + 1)d + log k бит каждый. Операции выполняются за <math>O(n^2)</math> шагов. Афек и др. в работе [1] также говорят о том, как заменить неограниченные порядковые номера битами «рукопожатия». Для этого требуется <math>n \Theta(nd)</math>-битных регистров и <math>n^2</math> 1-битных регистров; операции по-прежнему выполняются за <math>O(n^2)</math> шагов. | ||
Та же идея может быть использована для создания мультирайтерных снимков из мультирайтерных регистров. Использование неограниченных порядковых номеров позволяет получить алгоритм без ожидания, использующий m регистров, хранящих по | Та же идея может быть использована для создания мультирайтерных снимков из мультирайтерных регистров. Использование неограниченных порядковых номеров позволяет получить алгоритм без ожидания, использующий m регистров, хранящих по <math>\Theta(nd \; + \; log \; k)</math> бит, в котором каждая операция завершается за O(mn) шагов. (Этот алгоритм в явном виде приведен в работе [9]). Ни один алгоритм не может использовать меньше m регистров, если <math>n \ge m</math> [9]. Если вместо этого используются биты рукопожатия, то алгоритм мультирайтерного моментального снимка использует <math>n^2</math> 1-битных регистра, m(d + log n)-битных регистра и n (md)-битных регистров, а каждая операция требует <math>O(nm + n^2)</math> шагов [1]. | ||
| Строка 43: | Строка 43: | ||
Андерсон [ ] предложил реализацию мультирайтерного моментального снимка из однорайтерного моментального снимка. Каждый процесс хранит свое последнее обновление каждого компонента мультирайтерного моментального снимка в однорайтерном с соответствующими данными временной метки, вычисленными путем сканирования однорайтерного снимка. Операция сканирования выполняется с помощью однократного сканирования однорайтерного моментального снимка. Для обновления требуется дважды просканировать и обновить однорайтерный снимок. Реализация предполагает некоторое увеличение размеров компонентов, т. е. для реализации мультирайтерного моментального снимка с областью D требуется однорайтерный снимок с гораздо большей областью D0. Если целью является реализация мультирайтерных снимков из однорайтерных регистров (а не мультирайтерных), то построение Андерсона дает более эффективное решение, чем у Афека и коллег. | Андерсон [3] предложил реализацию мультирайтерного моментального снимка из однорайтерного моментального снимка. Каждый процесс хранит свое последнее обновление каждого компонента мультирайтерного моментального снимка в однорайтерном с соответствующими данными временной метки, вычисленными путем сканирования однорайтерного снимка. Операция сканирования выполняется с помощью однократного сканирования однорайтерного моментального снимка. Для обновления требуется дважды просканировать и обновить однорайтерный снимок. Реализация предполагает некоторое увеличение размеров компонентов, т. е. для реализации мультирайтерного моментального снимка с областью D требуется однорайтерный снимок с гораздо большей областью D0. Если целью является реализация мультирайтерных снимков из однорайтерных регистров (а не мультирайтерных), то построение Андерсона дает более эффективное решение, чем у Афека и коллег. | ||
Аттия, Херлихи и Рахман [ ] определили объект «решеточное согласование» (lattice agreement), очень тесно связанный с проблемой реализации однорайтерного моментального снимка при известной верхней границе на k. Затем они показали, как построить однорайтерный снимок (без ограничения на k) из бесконечной последовательности таких объектов. Каждая операция с моментальным снимком дважды обращается к объекту решеточного согласования и выполняет O(n) дополнительных шагов. Их реализации решеточных согласований обсуждаются в разделе «Не требующие ожидания реализации на основе небольших и более сильных объектов». | Аттия, Херлихи и Рахман [3] определили объект ''«решеточное согласование»'' (lattice agreement), очень тесно связанный с проблемой реализации однорайтерного моментального снимка при известной верхней границе на k. Затем они показали, как построить однорайтерный снимок (без ограничения на k) из бесконечной последовательности таких объектов. Каждая операция с моментальным снимком дважды обращается к объекту решеточного согласования и выполняет O(n) дополнительных шагов. Их реализации решеточных согласований обсуждаются в разделе «Не требующие ожидания реализации на основе небольших и более сильных объектов». | ||
Аттия и Рахман [ ] использовали аналогичный подход для реализации однорайтерного моментального снимка из больших однорайтерных регистров, используя O( | Аттия и Рахман [8] использовали аналогичный подход для реализации однорайтерного моментального снимка из больших однорайтерных регистров, используя O(n log n) шагов на операцию. Каждое обновление имеет свой порядковый номер. Сканер обходит бинарное дерево высоты log k от корня к листьям (в этом случае требуется ограничение на k). Каждый узел дерева содержит массив из n однорайтерных регистров. Процесс, прибывший в узел, записывает свой текущий вектор в однорайтерный регистр, связанный с этим узлом, а затем получает новый вектор, комбинируя информацию, считанную из всех n регистров. В зависимости от суммы порядковых номеров в этом векторе он переходит к левому или правому дочернему узлу. Таким образом, все сканеры могут быть линеаризованы в порядке листьев, до которых они доходят. Обновления выполняются путем аналогичного обхода дерева. Ограничение на k может быть снято, как в работе [7]. Аттия и Рахман также предлагают более прямолинейную реализацию, которая получает результат путем переработки объекта «моментальный снимок», предполагающего ограничение на k. Их алгоритм также был адаптирован для решения задачи о консенсусе на основе условий [15]. | ||
Аттия, Фурэн и Гафни [ ] предложили адаптировать алгоритм Аттии и Рахмана [ ] таким образом, чтобы количество шагов, необходимых для выполнения операции, зависело от количества процессов, которые фактически обращаются к объекту, а не от общего количества процессов в системе. | Аттия, Фурэн и Гафни [6] предложили адаптировать алгоритм Аттии и Рахмана [8] таким образом, чтобы количество шагов, необходимых для выполнения операции, зависело от количества процессов, которые фактически обращаются к объекту, а не от общего количества процессов в системе. | ||
Аттия и | Аттия и Фурэн [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). | ||
| Строка 67: | Строка 67: | ||
Джаянти [13] представил мультирайтерную реализацию моментального снимка из O(mn2) небольших объектов типа «сравнение с обменом» (compare&swap), в которой обновление занимает O(1) шагов, а сканирование – O(m) шагов. Он начинается с очень простой односканерной и однорайтерной реализации моментального снимка из регистров, которая использует вспомогательный массив для хранения копий последних обновлений. Операция сканирования очищает этот массив, собирает основной массив, а затем собирает вспомогательный, чтобы найти пропущенные обновления. Для получения мультисканерного и мультирайтерного моментального снимка общего вида вводится несколько дополнительных механизмов. В частности, операции сравнения с обменом используются вместо операций записи для координации процессов-райтеров, обновляющих один и тот же компонент, а несколько сканеров координируются друг с другом для имитации работы одного сканера. Алгоритм Джаянти основывается на более ранней работе Риани, Шавита и Туиту [ ], в которой была приведена реализация, достигающая аналогичной сложности, но только для однорайтерного моментального снимка. | Джаянти [13] представил мультирайтерную реализацию моментального снимка из O(mn2) небольших объектов типа «сравнение с обменом» (compare&swap), в которой обновление занимает O(1) шагов, а сканирование – O(m) шагов. Он начинается с очень простой односканерной и однорайтерной реализации моментального снимка из регистров, которая использует вспомогательный массив для хранения копий последних обновлений. Операция сканирования очищает этот массив, собирает основной массив, а затем собирает вспомогательный, чтобы найти пропущенные обновления. Для получения мультисканерного и мультирайтерного моментального снимка общего вида вводится несколько дополнительных механизмов. В частности, операции сравнения с обменом используются вместо операций записи для координации процессов-райтеров, обновляющих один и тот же компонент, а несколько сканеров координируются друг с другом для имитации работы одного сканера. Алгоритм Джаянти основывается на более ранней работе Риани, Шавита и Туиту [ ], в которой была приведена реализация, достигающая аналогичной сложности, но только для однорайтерного моментального снимка. | ||
== Применение == | == Применение == | ||
