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

В асинхронной распределенной системе с разделяемой памятью набор из n процессов взаимодействует между собой, обращаясь к общим структурам данных, называемым объектами. Система предоставляет базовые типы общих объектов; другие необходимые типы должны быть построены на их основе. Один из подходов использует блокировки для обеспечения эксклюзивного доступа к базовым объектам, но этот подход не является отказоустойчивым, чреват возникновением взаимоблокировок и «живых» блокировок, а также вызывает задержки, когда процесс, осуществляющий блокировку, работает медленно. Алгоритмы без блокировок позволяют избежать этих проблем, но создают новые трудности. Например, если процесс читает два общих объекта, считываемые им значения могут быть несовместимы, если между двумя считываниями объекты были обновлены.

Объект типа «моментальный снимок» (snapshot) хранит вектор из m значений, каждое из которых принадлежит некоторой области D. Он поддерживает две операции, сканирование (scan) и обновление (update(i, v)), где 1 < i < m и v 2 D. Если операции вызываются последовательно, то операция update(i, v) изменяет значение i-го компонента хранимого вектора на v, а операция scan возвращает хранимый вектор.

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

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

Далее описываются реализации моментальных снимков более базовых типов, которые также являются линеаризуемыми и не имеют блокировок. Были изучены два типа моментальных снимков. В случае однорайтерных моментальных снимков (single-writer snapshot) каждый компонент принадлежит одному процессу, и только этот процесс может его обновлять. (Таким образом, для однорайтерных моментальных снимков m = n.) В случае мультирайтерных моментальных снимков (multi-writer snapshot) любой процесс может обновлять любой компонент. Существуют также алгоритмы для односканерных моментальных снимков, когда в любой момент времени только один процесс может выполнять сканирование [10, 13, 14, 16]. Моментальные снимки ввели такие авторы, как Афек и др. [ ], Андерсон [2], а также Аспнес и Херлихи [4].

Пространственная сложность измеряется количеством используемых базовых объектов и их размером (в битах); временная сложность измеряется максимальным количеством шагов, которые должен выполнить процесс, чтобы завершить сканирование или обновление, где шагом является обращение к базовому общему объекту. (Локальные вычисления и обращения к локальной памяти обычно не учитываются). Границы сложности будут выражаться в терминах n;m;d = log jDj и k – количества операций, вызываемых в процессе выполнения. Ограничение на k обычно отсутствует.

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