Операционные системы распределенных вычислительных систем
Консистентное множество контрольных точек.
Описанные выше трудности показывают, что глобальная контрольная точка, состоящая из произвольной совокупности локальных контрольных точек, не обеспечивает восстановления взаимодействующих процессов.
Для распределенных систем запоминание согласованного глобального состояния является серьезной теоретической проблемой.
Множество контрольных точек называется строго консистентным, если во время его фиксации никаких обменов между процессами не было. Оно соответствует понятию строго консистентного глобального состояния, когда все посланные сообщения получены и нет никаких сообщений в каналах связи. Множество контрольных точек называется консистентным, если для любой зафиксированной операции приема сообщения, соответствующая операция посылки также зафиксирована (нет сообщений-сирот).
Простой метод фиксации консистентного множества контрольных точек - фиксация локальной контрольной точки после каждой операции посылки сообщения. При этом посылка сообщения и фиксация должны быть единой неделимой операцией (транзакцией). Множество последних локальных контрольных точек является консистентным (но не строго консистентным).
Чтобы избежать потерь сообщений при восстановлении с использованием консистентного множества контрольных точек необходимо повторить отправку тех сообщений, квитанции о получении которых стали недействительными в результате отката. Используя временные метки сообщений можно распознавать сообщения-призраки и избежать бесконечного восстановления.
7.1.5. Синхронная фиксация контрольных точек и восстановление.
Ниже описываются алгоритмы создания консистентного множества контрольных точек и использования их для восстановления без опасности бесконечного зацикливания.
Алгоритм создания консистентного множества контрольных точек.
К распределенной системе алгоритм предъявляет следующие требования.
(1) Процессы взаимодействуют посредством посылки сообщений через коммуникационные каналы.
(2) Каналы работают по алгоритму FIFO. Коммуникационные протоколы точка-точка гарантируют невозможность пропажи сообщений из-за ошибок коммуникаций или отката к контрольной точке. (Другой способ обеспечения этого - использование стабильной памяти для журнала посылаемых сообщений и фиксации идентификатора последнего полученного по каналу сообщения).
Алгоритм создает в стабильной памяти два вида контрольных точек - постоянные и пробные.
Постоянная контрольная точка - это локальная контрольная точка, являющаяся частью консистентной глобальной контрольной точки. Пробная контрольная точка - это временная контрольная точка, которая становится постоянной только в случае успешного завершения алгоритма. Алгоритм исходит из того, что только один процесс инициирует создание множества контрольных точек, а также из того, что никто из участников не сломается во время работы алгоритма.
Алгоритм выполняется в две фазы.
1-ая фаза.
Инициатор фиксации (процесс Pi) создает пробную контрольную точку и просит все остальные процессы сделать то же самое. При этом процессу запрещается посылать неслужебные сообщения после того, как он сделает пробную контрольную точку. Каждый процесс извещает Pi о том, сделал ли он пробную контрольную точку. Если все процессы сделали пробные контрольные точки, то Pi принимает решение о превращении пробных точек в постоянные. Если какой-либо процесс не смог сделать пробную точку, то принимается решение об отмене всех пробных точек.
2-ая фаза.
Pi информирует все процессы о своем решении. В результате либо все процессы будут иметь новые постоянные контрольные точки, либо ни один из процессов не создаст новой постоянной контрольной точки. Только после выполнения принятого процессом Pi решения все процессы могут посылать сообщения.
Корректность алгоритма очевидна, поскольку созданное всеми множество постоянных контрольных точек не может содержать не зафиксированных операций посылки сообщений.
Оптимизация: если процесс не посылал сообщения с момента фиксации предыдущей постоянной контрольной точки, то он может не создавать новую.
Алгоритм отката (восстановления).
Алгоритм предполагает, что его инициирует один процесс и он не будет выполняться параллельно с алгоритмом фиксации.
Выполняется в две фазы.
1-ая фаза.
Инициатор отката спрашивает остальных, готовы ли они откатываться. Когда все будут готовы к откату, то он принимает решение об откате.
2-ая фаза.
Pi сообщает всем о принятом решении. Получив это сообщение, каждый процесс поступает указанным образом. С момента ответа на опрос готовности и до получения принятого решения процессы не должны посылать сообщения (нельзя же посылать сообщение процессу, который уже мог успеть откатиться).
Оптимизация: если процесс не обменивался сообщениями с момента фиксации предыдущей постоянной контрольной точки, то он может к ней не откатываться.
