Моментальные снимки в разделяемой памяти: различия между версиями
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 7 промежуточных версий 1 участника) | |||
| Строка 9: | Строка 9: | ||
''Объект типа «моментальный снимок»'' (snapshot) хранит вектор из m значений, каждое из которых принадлежит некоторой области D. Он поддерживает две операции, сканирование (scan) и обновление (update(i, v)), где <math>1 \le i \le m</math> и <math>v \in D</math>. Если операции вызываются последовательно, то операция update(i, v) изменяет значение i-го компонента хранимого вектора на v, а операция scan возвращает хранимый вектор. | ''Объект типа «моментальный снимок»'' (snapshot, далее «снимок») хранит вектор из m значений, каждое из которых принадлежит некоторой области D. Он поддерживает две операции, сканирование (scan) и обновление (update(i, v)), где <math>1 \le i \le m</math> и <math>v \in D</math>. Если операции вызываются последовательно, то операция update(i, v) изменяет значение i-го компонента хранимого вектора на v, а операция scan возвращает хранимый вектор. | ||
| Строка 18: | Строка 18: | ||
Далее описываются реализации моментальных снимков других базовых типов, которые также являются линеаризуемыми и не имеют блокировок. Были изучены два типа | Далее описываются реализации моментальных снимков других базовых типов, которые также являются линеаризуемыми и не имеют блокировок. Были изучены два типа снимков. В случае ''однорайтерных'' снимков (single-writer snapshot) каждый компонент принадлежит одному процессу, и только этот процесс может его обновлять. (Таким образом, для однорайтерных снимков m = n.) В случае ''мультирайтерных'' снимков (multi-writer snapshot) любой процесс может обновлять любой компонент. Существуют также алгоритмы для ''односканерных'' снимков, когда в любой момент времени только один процесс может выполнять сканирование [10, 13, 14, 16]. Моментальные снимки ввели такие авторы, как Афек и др. [1], Андерсон [2], а также Аспнес и Херлихи [4]. | ||
| Строка 29: | Строка 29: | ||
'''Простая неблокирующая реализация на основе небольших регистров''' | '''Простая неблокирующая реализация на основе небольших регистров''' | ||
Предположим, что каждый компонент однорайтерного объекта моментального снимка представлен однорайтерным регистром. Процесс i выполняет операцию обновления update(i, v), записывая v и порядковый номер в регистр i и увеличивая его порядковый номер. Выполнить операцию сканирования сложнее, чем просто прочитать каждый из m регистров, поскольку в ходе чтения некоторые регистры могут измениться. Чтобы выполнить сканирование, процесс неоднократно считывает все регистры. Последовательность считываний всех регистров называется ''сбором''. Если два сбора возвращают один и тот же вектор, то сканирование возвращает этот вектор (с обрезанными порядковыми номерами). Порядковые номера гарантируют, что если одно и то же значение читается в регистре дважды, то регистр содержал это значение в течение всего интервала между двумя считываниями. Сканирование может быть назначено точкой линеаризации между двумя одинаковыми сборами, а обновления линеаризуются при выполнении операции записи. Этот алгоритм является неблокирующим, поскольку сканирование продолжается только в том случае, если во время каждого сбора завершается хотя бы одна операция обновления. Аналогичный алгоритм с идентификаторами процессов, добавляемыми к номерам последовательностей, реализует неблокирующий мультирайтерный | Предположим, что каждый компонент однорайтерного объекта моментального снимка представлен однорайтерным регистром. Процесс i выполняет операцию обновления update(i, v), записывая v и порядковый номер в регистр i и увеличивая его порядковый номер. Выполнить операцию сканирования сложнее, чем просто прочитать каждый из m регистров, поскольку в ходе чтения некоторые регистры могут измениться. Чтобы выполнить сканирование, процесс неоднократно считывает все регистры. Последовательность считываний всех регистров называется ''сбором''. Если два сбора возвращают один и тот же вектор, то сканирование возвращает этот вектор (с обрезанными порядковыми номерами). Порядковые номера гарантируют, что если одно и то же значение читается в регистре дважды, то регистр содержал это значение в течение всего интервала между двумя считываниями. Сканирование может быть назначено точкой линеаризации между двумя одинаковыми сборами, а обновления линеаризуются при выполнении операции записи. Этот алгоритм является неблокирующим, поскольку сканирование продолжается только в том случае, если во время каждого сбора завершается хотя бы одна операция обновления. Аналогичный алгоритм с идентификаторами процессов, добавляемыми к номерам последовательностей, реализует неблокирующий мультирайтерный снимок из m мультирайтерных регистров. | ||
'''Не требующие ожидания реализации на основе больших регистров''' | '''Не требующие ожидания реализации на основе больших регистров''' | ||
Афек и др. [1] предложили способ модификации неблокирующего однорайтерного алгоритма выполнения моментального снимка, позволяющий сделать его свободным от ожидания, встроив сканирование в операции обновления. Обновление update(i, v) сначала выполняет сканирование, а затем записывает тройку, содержащую результат сканирования, v и порядковый номер, в регистр i. Пока процесс P неоднократно выполняет процесс сбора для выполнения сканирования, имеет место одна из двух ситуаций: либо два сбора возвращают один и тот же вектор (который P может вернуть), либо P в конце концов увидит три разные тройки в регистре какого-то другого процесса. В последнем случае третья тройка, которую увидел P, должна содержать вектор, являющийся результатом сканирования, начавшегося уже после сканирования P, поэтому сканирование P выводит этот вектор. Обновлениям и сканированиям, которые завершаются после просмотра двух идентичных сборов, назначаются точки линеаризации описанным ранее способом. Если одна операция сканирования получает свое выходное значение из встроенного сканирования, то им обоим назначается одна и та же точка линеаризации. Это не требующая ожидания реализация однорайтерного | Афек и др. [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 регистров, хранящих по <math>\Theta(nd \; + \; log \; k)</math> бит, в котором каждая операция завершается за O(mn) шагов. (Этот алгоритм в явном виде приведен в работе [9]). Ни один алгоритм не может использовать меньше m регистров, если <math>n \ge m</math> [9]. Если вместо этого используются биты рукопожатия, то алгоритм мультирайтерного | Та же идея может быть использована для создания мультирайтерных снимков из мультирайтерных регистров. Использование неограниченных порядковых номеров позволяет получить алгоритм без ожидания, использующий 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]. | ||
Геррауи и Рупперт [12] представили аналогичную реализацию мультирайтерного | Геррауи и Рупперт [12] представили аналогичную реализацию мультирайтерного снимка без ожидания, которая является анонимной, то есть не использует идентификаторы процессов, и все процессы программируются идентичным образом. | ||
Андерсон [3] предложил реализацию мультирайтерного | Андерсон [3] предложил реализацию мультирайтерного снимка из однорайтерного. Каждый процесс хранит свое последнее обновление каждого компонента мультирайтерного снимка в однорайтерном снимке с соответствующими данными временной метки, вычисленными путем сканирования однорайтерного снимка. Операция сканирования выполняется с помощью однократного сканирования однорайтерного снимка. Для обновления требуется дважды выполнить сканирование и обновление однорайтерного снимка. Реализация предполагает некоторое увеличение размеров компонентов, т. е. для реализации мультирайтерного снимка с областью D требуется однорайтерный снимок с гораздо большей областью D'. Если целью является реализация мультирайтерных снимков из однорайтерных регистров (а не мультирайтерных), то построение Андерсона дает более эффективное решение, чем у Афека и коллег. | ||
Аттия, Херлихи и Рахман [3] определили объект ''«решеточное согласование»'' (lattice agreement), очень тесно связанный с задачей реализации однорайтерного | Аттия, Херлихи и Рахман [3] определили объект ''«решеточное согласование»'' (lattice agreement), очень тесно связанный с задачей реализации однорайтерного снимка при известной верхней границе на k. Затем они показали, как построить однорайтерный снимок (без ограничения на k) из бесконечной последовательности таких объектов. Каждая операция с моментальным снимком дважды обращается к объекту решеточного согласования и выполняет O(n) дополнительных шагов. Их реализации решеточных согласований обсуждаются в разделе «Не требующие ожидания реализации на основе небольших и более сильных объектов». | ||
Аттия и Рахман [8] использовали аналогичный подход для реализации однорайтерного | Аттия и Рахман [8] использовали аналогичный подход для реализации однорайтерного снимка из больших однорайтерных регистров, используя O(n log n) шагов на операцию. Каждое обновление имеет свой порядковый номер. Сканер обходит бинарное дерево высоты log k от корня к листьям (в этом случае требуется ограничение на k). Каждый узел дерева содержит массив из n однорайтерных регистров. Процесс, прибывший в узел, записывает свой текущий вектор в однорайтерный регистр, связанный с этим узлом, а затем получает новый вектор, комбинируя информацию, считанную из всех n регистров. В зависимости от суммы порядковых номеров в этом векторе он переходит к левому или правому дочернему узлу. Таким образом, все сканеры могут быть линеаризованы в порядке листьев, до которых они доходят. Обновления выполняются путем аналогичного обхода дерева. Ограничение на k может быть снято, как в работе [7]. Аттия и Рахман также предлагают более прямолинейную реализацию, которая получает результат путем переработки объекта «моментальный снимок», предполагающего ограничение на k. Их алгоритм также был адаптирован для решения задачи о консенсусе на основе условий [15]. | ||
| Строка 55: | Строка 55: | ||
Аттия и Фурэн [5] решают задачу решеточного согласования за O(n) шагов. (В этом случае вместо использования терминологии решеточного согласования алгоритм описывается в терминах реализации моментальных снимков, в | Аттия и Фурэн [5] решают задачу решеточного согласования за O(n) шагов. (В этом случае вместо использования терминологии решеточного согласования алгоритм описывается в терминах реализации моментальных снимков, в которой каждый процесс выполняет не более одной операции взятия снимка). В качестве структуры данных алгоритм использует двумерный массив из <math>O(n^2)</math> ''матриц отражения''. Матрица отражения – это объект, который может использоваться двумя процессами для обмена информацией. Каждая матрица отражения строится из двух больших однорайтерных регистров. Каждый процесс выбирает свой путь через массив матриц отражения таким образом, чтобы каждую матрицу посещало не более двух процессов. Каждый элемент матрицы отражения в столбце 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). | ||
| Строка 63: | Строка 63: | ||
Аттия, Херлихи и Рахман [7] предложили элегантное рекурсивное решение | Аттия, Херлихи и Рахман [7] предложили элегантное рекурсивное решение задачи решеточного согласования по принципу «разделяй и властвуй». Разделение процессов на группы для рекурсии может быть выполнено динамически с помощью объектов типа «проверка и установка» (test&set). В результате получается алгоритм взятия снимка, который выполняется за время O(n) на одну операцию и использует <math>O(kn^2 \; log \; n)</math> небольших однорайтерных регистров и <math>O(kn \; log^2 \; n)</math> объектов «проверка и установка». (Он требует модификации их предыдущей реализации для замены больших регистров, которые записываются только один раз, на несколько небольших). Используя рандомизацию, каждый объект «проверка и установка» можно заменить однорайтерными регистрами, чтобы получить реализацию моментального снимка, используя только регистры, с O(n) ожидаемых шагов на операцию. | ||
Джаянти [13] представил мультирайтерную реализацию моментального снимка из <math>O(mn^2)</math> небольших объектов типа «сравнение с обменом» (compare&swap), в которой обновление занимает O(1) шагов, а сканирование – O(m) шагов. Он | Джаянти [13] представил мультирайтерную реализацию моментального снимка из <math>O(mn^2)</math> небольших объектов типа «сравнение с обменом» (compare&swap), в которой обновление занимает O(1) шагов, а сканирование – O(m) шагов. Он начинает с очень простой односканерной и однорайтерной реализации моментального снимка из регистров, которая использует вспомогательный массив для хранения копии недавних обновлений. Операция сканирования очищает этот массив, собирает основной массив, а затем собирает вспомогательный, чтобы найти пропущенные обновления. Для получения мультисканерного и мультирайтерного снимка общего вида вводится несколько дополнительных механизмов. В частности, операции сравнения с обменом используются вместо операций записи для координации процессов-райтеров, обновляющих один и тот же компонент, а несколько сканеров координируются друг с другом для имитации работы одного сканера. Алгоритм Джаянти основывается на более ранней работе Риани, Шавита и Туиту [16], в которой была приведена реализация, достигающая аналогичной сложности, но только для однорайтерного снимка. | ||
== Применение == | == Применение == | ||
| Строка 72: | Строка 72: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Некоторые нижние границы сложности для реализаций из регистров известны [9], но | Некоторые нижние границы сложности для реализаций из регистров известны [9], но разрыв между лучшими известными алгоритмами и лучшими нижними границами сохраняется. В частности, неизвестно, существует ли эффективная реализация моментальных снимков из небольших регистров без ожидания. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
| Строка 83: | Строка 83: | ||
См. также обзорную статью Фич о сложности реализации моментальных снимков [11]. | См. также обзорную статью Фич о сложности реализации моментальных снимков [11]. | ||
== Литература == | |||
1. Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. Assoc. Comput. Mach. 40,873-890(1993) | 1. Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. Assoc. Comput. Mach. 40,873-890(1993) | ||
2. Anderson, J.H.: Composite registers. Distrib. Comput. 6, 141-154(1993) | 2. Anderson, J.H.: Composite registers. Distrib. Comput. 6, 141-154(1993) | ||
3. Anderson, J.H.: Multi-writer composite registers. Distrib. Comput. 7,175-195 (1994) | 3. Anderson, J.H.: Multi-writer composite registers. Distrib. Comput. 7,175-195 (1994) | ||
4. Aspnes, J., Herlihy, M.: Wait-free data structures in the asynchronous PRAM model. In: Proc. 2nd ACM Symposium on Parallel Algorithms and Architectures, Crete, July 1990. pp. 340-349. ACM, New York, 1990 | 4. Aspnes, J., Herlihy, M.: Wait-free data structures in the asynchronous PRAM model. In: Proc. 2nd ACM Symposium on Parallel Algorithms and Architectures, Crete, July 1990. pp. 340-349. ACM, New York, 1990 | ||
5. Attiya, H., Fouren, A.: Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput. 31, 642-664 (2001) | 5. Attiya, H., Fouren, A.: Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput. 31, 642-664 (2001) | ||
6. Attiya, H., Fouren, A., Gafni, E.: An adaptive collect algorithm with applications. Distrib. Comput. 15,87-96 (2002) | 6. Attiya, H., Fouren, A., Gafni, E.: An adaptive collect algorithm with applications. Distrib. Comput. 15,87-96 (2002) | ||
7. Attiya, H., Herlihy, M., Rachman, O.: Atomic snapshots using lattice agreement. Distrib.Comput.8,121-132 (1995) | 7. Attiya, H., Herlihy, M., Rachman, O.: Atomic snapshots using lattice agreement. Distrib.Comput.8,121-132 (1995) | ||
8. Attiya, H., Rachman, O.: Atomic snapshots in O(n log n) operations. SIAM J. Comput. 27, 319-340 (1998) | 8. Attiya, H., Rachman, O.: Atomic snapshots in O(n log n) operations. SIAM J. Comput. 27, 319-340 (1998) | ||
9. Ellen, F., Fatourou, P., Ruppert, E.: Time lower bounds for implementations of multi-writer snapshots. J. Assoc. Comput. Mach. 54(6) article 30 (2007) | 9. Ellen, F., Fatourou, P., Ruppert, E.: Time lower bounds for implementations of multi-writer snapshots. J. Assoc. Comput. Mach. 54(6) article 30 (2007) | ||
10. Fatourou, P., Kallimanis, N.D.: Single-scanner multi-writer snapshot implementations are fast! In: Proc. 25th ACM Symposium on Principles of Distrib. Comput. Colorado, July 2006 pp. 228-237. ACM, New York (2006) | 10. Fatourou, P., Kallimanis, N.D.: Single-scanner multi-writer snapshot implementations are fast! In: Proc. 25th ACM Symposium on Principles of Distrib. Comput. Colorado, July 2006 pp. 228-237. ACM, New York (2006) | ||
11. Fich, F.E.: How hard is it to take a snapshot? In: SOFSEM 2005: Theory and Practice of Computer Science. Liptovsky Jan, January 2005, LNCS, vol. 3381, pp. 28-37. Springer (2005) | 11. Fich, F.E.: How hard is it to take a snapshot? In: SOFSEM 2005: Theory and Practice of Computer Science. Liptovsky Jan, January 2005, LNCS, vol. 3381, pp. 28-37. Springer (2005) | ||
12. Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. 20(3) 165-177 (2007) | 12. Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. 20(3) 165-177 (2007) | ||
13. Jayanti, P.: An optimal multi-writer snapshot algorithm. In: Proc. 37th ACM Symposium on Theory of Computing. Baltimore, May 2005, pp. 723-732. ACM, New York (2005) | 13. Jayanti, P.: An optimal multi-writer snapshot algorithm. In: Proc. 37th ACM Symposium on Theory of Computing. Baltimore, May 2005, pp. 723-732. ACM, New York (2005) | ||
14. Kirousis, L.M., Spirakis, P., Tsigas, P.: Simple atomic snapshots: A linear complexity solution with unbounded time-stamps. Inf. Process. Lett. 58,47-53 (1996) | 14. Kirousis, L.M., Spirakis, P., Tsigas, P.: Simple atomic snapshots: A linear complexity solution with unbounded time-stamps. Inf. Process. Lett. 58,47-53 (1996) | ||
15. Mostefaoui, A., Rajsbaum, S., Raynal, M., Roy, M.: Condition-based consensus solvability: a hierarchy of conditions and efficient protocols. Distrib. Comput. 17,1 -20 (2004) | 15. Mostefaoui, A., Rajsbaum, S., Raynal, M., Roy, M.: Condition-based consensus solvability: a hierarchy of conditions and efficient protocols. Distrib. Comput. 17,1 -20 (2004) | ||
16. Riany, Y., Shavit, N., Touitou, D.: Towards a practical snapshot algorithm. Theor. Comput. Sci. 269,163-201 (2001) | 16. Riany, Y., Shavit, N., Touitou, D.: Towards a practical snapshot algorithm. Theor. Comput. Sci. 269,163-201 (2001) | ||
[[Категория: Совместное определение связанных терминов]] | |||
Текущая версия от 08:58, 25 ноября 2024
Ключевые слова и синонимы
Атомарное сканирование
Постановка задачи
Реализация объекта «моментальный снимок» – это абстракция задачи получения согласованного представления нескольких общих переменных, в то время как другие процессы параллельно обновляют эти переменные.
В асинхронной распределенной системе с разделяемой памятью набор из n процессов взаимодействует между собой, обращаясь к общим структурам данных, называемым объектами. Система предоставляет базовые типы общих объектов; другие необходимые типы должны быть построены на их основе. Один из подходов использует блокировки для обеспечения эксклюзивного доступа к базовым объектам, но этот подход не является отказоустойчивым, чреват возникновением взаимоблокировок и «живых» блокировок, а также вызывает задержки в случаях, когда осуществляющий блокировку процесс работает медленно. Алгоритмы без блокировок позволяют избежать этих проблем, но создают новые трудности. Например, если процесс читает два общих объекта, считываемые им значения могут быть несовместимы, если между двумя считываниями объекты были обновлены.
Объект типа «моментальный снимок» (snapshot, далее «снимок») хранит вектор из m значений, каждое из которых принадлежит некоторой области D. Он поддерживает две операции, сканирование (scan) и обновление (update(i, v)), где [math]\displaystyle{ 1 \le i \le m }[/math] и [math]\displaystyle{ v \in D }[/math]. Если операции вызываются последовательно, то операция update(i, v) изменяет значение i-го компонента хранимого вектора на v, а операция scan возвращает хранимый вектор.
Корректность в случаях, когда операции с моментальными снимками, выполняемые разными процессами, перекрываются по времени, описывается условием линеаризуемости, которое гласит, что операции должны казаться происходящими мгновенно. Более формально, для каждого выполнения можно выбрать момент времени для каждой операции (называемый точкой линеаризации) между вызовом и завершением операции. (Незавершенная операция может либо не иметь точки линеаризации, либо получить точку линеаризации в любой момент после ее вызова). Ответы, возвращаемые всеми завершенными операциями в процессе выполнения, должны возвращать тот же результат, что и при последовательном выполнении всех операций в порядке их точек линеаризации.
Реализация также должна удовлетворять свойству прогресса. Свобода от ожиданий требует, чтобы каждый процесс завершал каждое сканирование или обновление за конечное число собственных шагов. Более слабое условие неблокируемости прогресса гласит, что система не может работать вечно без завершения какой-либо операции.
Далее описываются реализации моментальных снимков других базовых типов, которые также являются линеаризуемыми и не имеют блокировок. Были изучены два типа снимков. В случае однорайтерных снимков (single-writer snapshot) каждый компонент принадлежит одному процессу, и только этот процесс может его обновлять. (Таким образом, для однорайтерных снимков m = n.) В случае мультирайтерных снимков (multi-writer snapshot) любой процесс может обновлять любой компонент. Существуют также алгоритмы для односканерных снимков, когда в любой момент времени только один процесс может выполнять сканирование [10, 13, 14, 16]. Моментальные снимки ввели такие авторы, как Афек и др. [1], Андерсон [2], а также Аспнес и Херлихи [4].
Пространственная сложность измеряется количеством используемых базовых объектов и их размером (в битах); временная сложность измеряется максимальным количеством шагов, которые должен выполнить процесс, чтобы завершить сканирование или обновление, где шагом является обращение к базовому общему объекту. (Локальные вычисления и обращения к локальной памяти обычно не учитываются). Границы сложности будут выражаться в терминах n, m, d = log |D| и k – количества операций, вызываемых в процессе выполнения. Ограничение на k обычно отсутствует.
Большинство приведенных ниже алгоритмов используют регистры чтения-записи – самый элементарный тип общих объектов. Однорайтерный регистр может быть записан только одним процессом; мультирайтерный – любым процессом. Некоторые алгоритмы, использующие более сильные типы базовых объектов, обсуждаются в разделе «Не требующие ожидания реализации на основе небольших и более сильных объектов».
Основные результаты
Простая неблокирующая реализация на основе небольших регистров
Предположим, что каждый компонент однорайтерного объекта моментального снимка представлен однорайтерным регистром. Процесс 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 бит каждый. Операции выполняются за [math]\displaystyle{ O(n^2) }[/math] шагов. Афек и др. в работе [1] также говорят о том, как заменить неограниченные порядковые номера битами «рукопожатия». Для этого требуется [math]\displaystyle{ n \Theta \; (nd) }[/math]-битных регистров и [math]\displaystyle{ n^2 }[/math] 1-битных регистров; операции по-прежнему выполняются за [math]\displaystyle{ O(n^2) }[/math] шагов.
Та же идея может быть использована для создания мультирайтерных снимков из мультирайтерных регистров. Использование неограниченных порядковых номеров позволяет получить алгоритм без ожидания, использующий m регистров, хранящих по [math]\displaystyle{ \Theta(nd \; + \; log \; k) }[/math] бит, в котором каждая операция завершается за O(mn) шагов. (Этот алгоритм в явном виде приведен в работе [9]). Ни один алгоритм не может использовать меньше m регистров, если [math]\displaystyle{ n \ge m }[/math] [9]. Если вместо этого используются биты рукопожатия, то алгоритм мультирайтерного снимка использует [math]\displaystyle{ n^2 }[/math] 1-битных регистров, m(d + log n)-битных регистров и n (md)-битных регистров, а каждая операция требует [math]\displaystyle{ O(nm + n^2) }[/math] шагов [1].
Геррауи и Рупперт [12] представили аналогичную реализацию мультирайтерного снимка без ожидания, которая является анонимной, то есть не использует идентификаторы процессов, и все процессы программируются идентичным образом.
Андерсон [3] предложил реализацию мультирайтерного снимка из однорайтерного. Каждый процесс хранит свое последнее обновление каждого компонента мультирайтерного снимка в однорайтерном снимке с соответствующими данными временной метки, вычисленными путем сканирования однорайтерного снимка. Операция сканирования выполняется с помощью однократного сканирования однорайтерного снимка. Для обновления требуется дважды выполнить сканирование и обновление однорайтерного снимка. Реализация предполагает некоторое увеличение размеров компонентов, т. е. для реализации мультирайтерного снимка с областью D требуется однорайтерный снимок с гораздо большей областью D'. Если целью является реализация мультирайтерных снимков из однорайтерных регистров (а не мультирайтерных), то построение Андерсона дает более эффективное решение, чем у Афека и коллег.
Аттия, Херлихи и Рахман [3] определили объект «решеточное согласование» (lattice agreement), очень тесно связанный с задачей реализации однорайтерного снимка при известной верхней границе на k. Затем они показали, как построить однорайтерный снимок (без ограничения на k) из бесконечной последовательности таких объектов. Каждая операция с моментальным снимком дважды обращается к объекту решеточного согласования и выполняет O(n) дополнительных шагов. Их реализации решеточных согласований обсуждаются в разделе «Не требующие ожидания реализации на основе небольших и более сильных объектов».
Аттия и Рахман [8] использовали аналогичный подход для реализации однорайтерного снимка из больших однорайтерных регистров, используя O(n log n) шагов на операцию. Каждое обновление имеет свой порядковый номер. Сканер обходит бинарное дерево высоты log k от корня к листьям (в этом случае требуется ограничение на k). Каждый узел дерева содержит массив из n однорайтерных регистров. Процесс, прибывший в узел, записывает свой текущий вектор в однорайтерный регистр, связанный с этим узлом, а затем получает новый вектор, комбинируя информацию, считанную из всех n регистров. В зависимости от суммы порядковых номеров в этом векторе он переходит к левому или правому дочернему узлу. Таким образом, все сканеры могут быть линеаризованы в порядке листьев, до которых они доходят. Обновления выполняются путем аналогичного обхода дерева. Ограничение на k может быть снято, как в работе [7]. Аттия и Рахман также предлагают более прямолинейную реализацию, которая получает результат путем переработки объекта «моментальный снимок», предполагающего ограничение на k. Их алгоритм также был адаптирован для решения задачи о консенсусе на основе условий [15].
Аттия, Фурэн и Гафни [6] предложили адаптировать алгоритм Аттии и Рахмана [8] таким образом, чтобы количество шагов, необходимых для выполнения операции, зависело от количества процессов, которые фактически обращаются к объекту, а не от общего количества процессов в системе.
Аттия и Фурэн [5] решают задачу решеточного согласования за O(n) шагов. (В этом случае вместо использования терминологии решеточного согласования алгоритм описывается в терминах реализации моментальных снимков, в которой каждый процесс выполняет не более одной операции взятия снимка). В качестве структуры данных алгоритм использует двумерный массив из [math]\displaystyle{ O(n^2) }[/math] матриц отражения. Матрица отражения – это объект, который может использоваться двумя процессами для обмена информацией. Каждая матрица отражения строится из двух больших однорайтерных регистров. Каждый процесс выбирает свой путь через массив матриц отражения таким образом, чтобы каждую матрицу посещало не более двух процессов. Каждый элемент матрицы отражения в столбце 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).
Не требующие ожидания реализации на основе небольших и более сильных объектов
Все описанные выше реализации без ожидания используют регистры, которые могут хранить [math]\displaystyle{ \Omega(m) }[/math] бит каждый, и поэтому непрактичны в случаях, когда m велико. В этом разделе описываются некоторые реализации на основе небольших объектов, поддерживающих более сильные операции синхронизации, а не только чтения и записи. Объект считается небольшим, если он может хранить O(d + log n + log k) бит. Это означает, что он может содержать постоянное количество значений компонентов, идентификаторов процессов и порядковых номеров.
Аттия, Херлихи и Рахман [7] предложили элегантное рекурсивное решение задачи решеточного согласования по принципу «разделяй и властвуй». Разделение процессов на группы для рекурсии может быть выполнено динамически с помощью объектов типа «проверка и установка» (test&set). В результате получается алгоритм взятия снимка, который выполняется за время O(n) на одну операцию и использует [math]\displaystyle{ O(kn^2 \; log \; n) }[/math] небольших однорайтерных регистров и [math]\displaystyle{ O(kn \; log^2 \; n) }[/math] объектов «проверка и установка». (Он требует модификации их предыдущей реализации для замены больших регистров, которые записываются только один раз, на несколько небольших). Используя рандомизацию, каждый объект «проверка и установка» можно заменить однорайтерными регистрами, чтобы получить реализацию моментального снимка, используя только регистры, с O(n) ожидаемых шагов на операцию.
Джаянти [13] представил мультирайтерную реализацию моментального снимка из [math]\displaystyle{ O(mn^2) }[/math] небольших объектов типа «сравнение с обменом» (compare&swap), в которой обновление занимает O(1) шагов, а сканирование – O(m) шагов. Он начинает с очень простой односканерной и однорайтерной реализации моментального снимка из регистров, которая использует вспомогательный массив для хранения копии недавних обновлений. Операция сканирования очищает этот массив, собирает основной массив, а затем собирает вспомогательный, чтобы найти пропущенные обновления. Для получения мультисканерного и мультирайтерного снимка общего вида вводится несколько дополнительных механизмов. В частности, операции сравнения с обменом используются вместо операций записи для координации процессов-райтеров, обновляющих один и тот же компонент, а несколько сканеров координируются друг с другом для имитации работы одного сканера. Алгоритм Джаянти основывается на более ранней работе Риани, Шавита и Туиту [16], в которой была приведена реализация, достигающая аналогичной сложности, но только для однорайтерного снимка.
Применение
Сферы применения моментальных снимков включают распределенные базы данных, хранение контрольных точек или резервных копий для восстановления после ошибок, сборку мусора, обнаружение взаимоблокировок, отладку распределенных программ и получение согласованного представления значений, сообщаемых несколькими датчиками. Моментальные снимки применялись в качестве структурных элементов распределенных решений для задач поиска рандомизированного консенсуса и приближенного соответствия. Они также полезны в качестве примитива для построения других структур данных. Например, рассмотрим реализацию счетчика, который хранит целое число и поддерживает операции инкремента, декремента и чтения. Каждый процесс может хранить количество выполненных им инкрементов за вычетом количества декрементов в своем компоненте однорайтерного объекта типа «моментальный снимок», а счетчик может быть прочитан путем суммирования значений, полученных при сканировании. Ссылки на многие из упомянутых здесь областей применения можно найти в работе [10].
Открытые вопросы
Некоторые нижние границы сложности для реализаций из регистров известны [9], но разрыв между лучшими известными алгоритмами и лучшими нижними границами сохраняется. В частности, неизвестно, существует ли эффективная реализация моментальных снимков из небольших регистров без ожидания.
Экспериментальные результаты
Риани, Шавит и Туиту привели результаты оценки производительности для нескольких реализаций [16].
См. также
См. также обзорную статью Фич о сложности реализации моментальных снимков [11].
Литература
1. Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. Assoc. Comput. Mach. 40,873-890(1993)
2. Anderson, J.H.: Composite registers. Distrib. Comput. 6, 141-154(1993)
3. Anderson, J.H.: Multi-writer composite registers. Distrib. Comput. 7,175-195 (1994)
4. Aspnes, J., Herlihy, M.: Wait-free data structures in the asynchronous PRAM model. In: Proc. 2nd ACM Symposium on Parallel Algorithms and Architectures, Crete, July 1990. pp. 340-349. ACM, New York, 1990
5. Attiya, H., Fouren, A.: Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput. 31, 642-664 (2001)
6. Attiya, H., Fouren, A., Gafni, E.: An adaptive collect algorithm with applications. Distrib. Comput. 15,87-96 (2002)
7. Attiya, H., Herlihy, M., Rachman, O.: Atomic snapshots using lattice agreement. Distrib.Comput.8,121-132 (1995)
8. Attiya, H., Rachman, O.: Atomic snapshots in O(n log n) operations. SIAM J. Comput. 27, 319-340 (1998)
9. Ellen, F., Fatourou, P., Ruppert, E.: Time lower bounds for implementations of multi-writer snapshots. J. Assoc. Comput. Mach. 54(6) article 30 (2007)
10. Fatourou, P., Kallimanis, N.D.: Single-scanner multi-writer snapshot implementations are fast! In: Proc. 25th ACM Symposium on Principles of Distrib. Comput. Colorado, July 2006 pp. 228-237. ACM, New York (2006)
11. Fich, F.E.: How hard is it to take a snapshot? In: SOFSEM 2005: Theory and Practice of Computer Science. Liptovsky Jan, January 2005, LNCS, vol. 3381, pp. 28-37. Springer (2005)
12. Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. 20(3) 165-177 (2007)
13. Jayanti, P.: An optimal multi-writer snapshot algorithm. In: Proc. 37th ACM Symposium on Theory of Computing. Baltimore, May 2005, pp. 723-732. ACM, New York (2005)
14. Kirousis, L.M., Spirakis, P., Tsigas, P.: Simple atomic snapshots: A linear complexity solution with unbounded time-stamps. Inf. Process. Lett. 58,47-53 (1996)
15. Mostefaoui, A., Rajsbaum, S., Raynal, M., Roy, M.: Condition-based consensus solvability: a hierarchy of conditions and efficient protocols. Distrib. Comput. 17,1 -20 (2004)
16. Riany, Y., Shavit, N., Touitou, D.: Towards a practical snapshot algorithm. Theor. Comput. Sci. 269,163-201 (2001)