В.А. Крюков - Операционные системы распределенных вычислительных систем, страница 12

При этом процессу запрещается посылатьнеслужебные сообщения после того, как он сделает пробную контрольную точку. Каждыйпроцесс извещает Pi о том, сделал ли он пробную контрольную точку. Если все процессысделали пробные контрольные точки, то Pi принимает решение о превращении пробных точекв постоянные. Если какой-либо процесс не смог сделать пробную точку, то принимаетсярешение об отмене всех пробных точек.2-ая фаза.Pi информирует все процессы о своем решении. В результате либо все процессы будут иметьновые постоянные контрольные точки, либо ни один из процессов не создаст новойпостоянной контрольной точки.

Только после выполнения принятого процессом Pi решениявсе процессы могут посылать сообщения.Корректность алгоритма очевидна, поскольку созданное всеми множество постоянныхконтрольных точек не может содержать не зафиксированных операций посылки сообщений.Оптимизация: если процесс не посылал сообщения с момента фиксации предыдущейпостоянной контрольной точки, то он может не создавать новую.Алгоритм отката (восстановления).Алгоритм предполагает, что его инициирует один процесс и он не будет выполнятьсяпараллельно с алгоритмом фиксации.47Выполняется в две фазы.1-ая фаза.Инициатор отката спрашивает остальных, готовы ли они откатываться.

Когда все будутготовы к откату, то он принимает решение об откате.2-ая фаза.Pi сообщает всем о принятом решении. Получив это сообщение, каждый процесс поступаетуказанным образом. С момента ответа на опрос готовности и до получения принятогорешения процессы не должны посылать сообщения (нельзя же посылать сообщение процессу,который уже мог успеть откатиться).Оптимизация: если процесс не обменивался сообщениями с момента фиксации предыдущейпостоянной контрольной точки, то он может к ней не откатываться.7.1.5.

Асинхронная фиксация контрольных точек и восстановление.Синхронная фиксация упрощает восстановление, но связана с большими накладнымирасходами:(1) Дополнительные служебные сообщения для реализации алгоритма.(2) Синхронизационная задержка - нельзя посылать неслужебные сообщения во время работыалгоритма.Если отказы редки, то указанные потери совсем не оправданы.Фиксация может производиться асинхронно.

В этом случае множество контрольных точекможет быть неконсистентным. При откате происходит поиск подходящего консистентногомножества путем поочередного отката каждого процесса в ту точку, в которой зафиксированывсе посланные им и полученные другими сообщения (для ликвидации сообщений-сирот).Алгоритм опирается на наличие в стабильной памяти для каждого процесса журнала,отслеживающего номера посланных и полученных им сообщений, а также на некоторыепредположения об организации взаимодействия процессов, необходимые для исключения«эффекта домино» (например, организация приложения по схеме сообщение-реакция-ответ).7.2.

Отказоустойчивость.Изложенные выше методы восстановления после отказов для некоторых систем непригодны(управляющие системы, транзакции в on-line режиме) из-за прерывания нормальногофункционирования.Чтобы избежать этих неприятностей, создают системы, устойчивые к отказам. Такие системылибо маскируют отказы, либо ведут себя в случае отказа заранее определенным образом(пример - изменения, вносимые транзакцией в базу данных, становятся невидимыми приотказе).Два механизма широко используются при обеспечении отказоустойчивости - протоколыголосования и протоколы принятия коллективного решения.Протоколы голосования служат для маскирования отказов (выбирается правильный результат,полученный всеми исправными исполнителями).Протоколы принятия коллективного решения подразделяются на два класса.

Во-первых,протоколы принятия единого решения, в которых все исполнители являются исправными идолжны либо все принять, либо все не принять заранее предусмотренное решение.Примерами такого решения являются решение о завершении итерационного цикла при48достижении всеми необходимой точности, решение о реакции на отказ (этот протокол ужезнаком нам - он использовался для принятия решения об откате всех процессов кконтрольным точкам). Во-вторых, протоколы принятия согласованных решений на основеполученных друг от друга данных. При этом необходимо всем исправным исполнителямполучить достоверные данные от остальных исправных исполнителей, а данные отнеисправных исполнителей проигнорировать.Ключевой подход для обеспечения отказоустойчивости - избыточность (оборудования,процессов, данных).7.2.1.

Использование режима «горячего резерва» (второй пилот, резервное ПО).Проблема переключения на резервный исполнитель.7.2.2. Использование активного размножения.Наглядный пример - тройное дублирование аппаратуры в бортовых компьютерах иголосование при принятии решения.Другие примеры – размножение страниц в DSM и размножение файлов в распределенныхфайловых системах. При этом очень важным моментом является наличие механизманеделимых широковещательных рассылок сообщений (они должны приходить всем в одномпорядке).Алгоритмы голосования.Общая схема использования голосования при размножении файлов может быть представленаследующим образом.Файл может модифицироваться разными процессами только последовательно (при открытиифайла на запись процесс-писатель будет ждать закрытия файла другим писателем или всемичитателями), а читаться всеми одновременно (протокол писателей-читателей).

Всемодификации файла нумеруются и каждая копия файла характеризуется номером версии –количеством ее модификаций. Каждой копии приписано некоторое количество голосов Vi.Пусть общее количество приписанных всем копиям голосов равно V. Определяется кворумзаписи Vw и кворум чтения Vr так, чтоVw +Vr > VДля записи информации в файл писатель рассылает ее всем владельцам копий файла и долженполучить Vw голосов от тех, кто успешно выполнил запись.Для получения права на чтение читателю достаточно получить необходимое число голосов(Vr) от любых серверов. Кворум чтения выбран так, что хотя бы один из тех серверов, откоторых получено разрешение, является владельцем текущей копии файла. За чтениеминформации из файла читатель может обратиться к любому владельцу текущей копии файла.Описанная схема базируется на статическом распределении голосов.

Различие в голосах,приписанных разным серверам, позволяет учесть их особенности (надежность,эффективность). Еще большую гибкость предоставляет метод динамическогоперераспределения голосов.Для того, чтобы выход из строя некоторых серверов не привел к ситуации, когда невозможнополучить кворум, применяется механизм изменения состава голосующих.49Протоколы принятия единого решенияНеобходимо отметить, что в условиях отсутствия надежных коммуникаций (с ограниченнымвременем задержки) не может быть алгоритма достижения единого решения. Рассмотримизвестную «проблему двух армий».Армия зеленых численностью 5000 воинов располагается в долине.Две армии синих численностью по 3000 воинов находятся далеко друг от друга в горах,окружающих долину. Если две армии синих одновременно атакуют зеленых, то они победят.Если же в сражение вступит только одна армия синих, то она будет полностью разбита.Предположим, что командир 1-ой синей армии генерал Александр посылает (с посыльным)сообщение командиру 2-ой синей армии генералу Михаилу «Я имею план - давай атаковатьзавтра на рассвете».

Посыльный возвращается к Александру с ответом Михаила - «Отличнаяидея, Саша. Увидимся завтра на рассвете». Александр приказывает воинам готовиться к атакена рассвете.Однако, чуть позже Александр вдруг осознает, что Михаил не знает о возвращениипосыльного и поэтому может не отважиться на атаку. Тогда он отправляет посыльного кМихаилу чтобы подтвердить, что его (Михаила) сообщение получено Александром и атакадолжна состояться.Посыльный прибыл к Михаилу, но теперь тот боится, что не зная о прибытии посыльногоАлександр может не решиться на атаку. И т.д.

Ясно, что генералы никогда не достигнутсогласия.Предположим, что такой протокол согласия c конечным числом сообщений существует.Удалив избыточные последние сообщения, получим минимальный протокол. Самое последнеесообщение является существенным (поскольку протокол минимальный). Если это сообщениене дойдет по назначению, то войны не будет. Но тот, кто посылал это сообщение, не знает,дошло ли оно. Следовательно, он не может считать протокол завершенным и не можетпринять решение об атаке. Даже с надежными процессорами (генералами), принятие единогорешения невозможно при ненадежных коммуникациях.Теперь предположим, что коммуникации надежны, а процессоры нет.Классический пример протокола принятия согласованных решений - задача «Византийскихгенералов».В этой задаче армия зеленых находится в долине, а n синих генералов возглавляют своиармии, расположенные в горах. Связь осуществляется по телефону и является надежной, но изn генералов m являются предателями.

Предатели активно пытаются воспрепятствоватьсогласию лояльных генералов.Согласие в данном случае заключается в следующем. Каждый генерал знает, сколько воиновнаходится под его командой. Ставится цель, чтобы все лояльные генералы узналичисленности всех лояльных армий, т.е. каждый из них получил один и тот же вектор длины n,в котором i-ый элемент либо содержит численность i-ой армии (если ее командир лоялен)либо не определен (если командир предатель).Соответствующий рекурсивный алгоритм был предложен в 1982 г. (Lamport).Проиллюстрируем его для случая n=4 и m=1.

В этом случае алгоритм осуществляется в 4шага.1 шаг. Каждый генерал посылает всем остальным сообщение, в котором указываетчисленность своей армии. Лояльные генералы указывают истинное количество, а предателимогут указывать различные числа в разных сообщениях. Генерал-1 указал 1 (одна тысячавоинов), генерал-2 указал 2, генерал-3 указал трем остальным генералам соответственно x,y,z,а генерал-4 указал 4.502-ой шаг.

Каждый формирует свой вектор из имеющейся информации.Получается:vect1 (1,2,x,4)vect2 (1,2,y,4)vect3 (1,2,3,4)vect4 (1,2,z,4)3-ий шаг. Каждый посылает свой вектор всем остальным (генерал-3 посылает опятьпроизвольные значения).Генералы получают следующие вектора:g1g2g3g4(1,2,y,4)(1,2,x,4)(1,2,x,4)(1,2,x,4)(a,b,c,d)(e,f,g,h)(1,2,y,4)(1,2,y,4)(1,2,z.4)(1,2,z.4)(1,2,z.4)(i,j,k.l)4-ый шаг. Каждый генерал проверяет каждый элемент во всех полученных векторах.