Операционные системы распределенных вычислительных систем
Асинхронная фиксация контрольных точек и восстановление.
Синхронная фиксация упрощает восстановление, но связана с большими накладными расходами:
(1) Дополнительные служебные сообщения для реализации алгоритма.
(2) Синхронизационная задержка - нельзя посылать неслужебные сообщения во время работы алгоритма.
Если отказы редки, то указанные потери совсем не оправданы.
Фиксация может производиться асинхронно. В этом случае множество контрольных точек может быть неконсистентным. При откате происходит поиск подходящего консистентного множества путем поочередного отката каждого процесса в ту точку, в которой зафиксированы все посланные им и полученные другими сообщения (для ликвидации сообщений-сирот). Алгоритм опирается на наличие в стабильной памяти для каждого процесса журнала, отслеживающего номера посланных и полученных им сообщений, а также на некоторые предположения об организации взаимодействия процессов, необходимые для исключения «эффекта домино» (например, организация приложения по схеме сообщение-реакция-ответ).
7.2. Отказоустойчивость.
Изложенные выше методы восстановления после отказов для некоторых систем непригодны (управляющие системы, транзакции в on-line режиме) из-за прерывания нормального функционирования.
Чтобы избежать эти неприятности, создают системы, устойчивые к отказам. Такие системы либо маскируют отказы, либо ведут себя в случае отказа заранее определенным образом (пример - изменения, вносимые транзакцией в базу данных, становятся невидимыми при отказе).
Два механизма широко используются при обеспечении отказоустойчивости - протоколы голосования и протоколы принятия коллективного решения.
Протоколы голосования служат для маскирования отказов (выбирается правильный результат, полученный всеми исправными исполнителями).
Протоколы принятия коллективного решения подразделяются на два класса. Во-первых, протоколы принятия единого решения, в которых все исполнители являются исправными и должны либо все принять, либо все не принять заранее предусмотренное решение. Примерами такого решения являются решение о завершении итерационного цикла при достижении всеми необходимой точности, решение о реакции на отказ (этот протокол уже знаком нам - он использовался для принятия решения об откате всех процессов к контрольным точкам).
Во-вторых, протоколы принятия согласованных решений на основе полученных друг от друга данных. При этом необходимо всем исправным исполнителям получить достоверные данные от остальных исправных исполнителей, а данные от неисправных исполнителей проигнорировать.
Ключевой подход для обеспечения отказоустойчивости - избыточность (оборудования, процессов, данных).
7.2.1. Использование режима «горячего резерва» (второй пилот, резервное ПО).
Проблема переключения на резервный исполнитель.
7.2.2. Использование активного размножения.
Наглядный пример - тройное дублирование аппаратуры в бортовых компьютерах и голосование при принятии решения.
Другие примеры – размножение страниц в DSM и размножение файлов в распределенных файловых системах. При этом очень важным моментом является наличие механизма неделимых широковещательных рассылок сообщений (они должны приходить всем в одном порядке).
Алгоритмы голосования.
Общая схема использования голосования при размножении файлов может быть представлена следующим образом.
Файл может модифицироваться разными процессами только последовательно, а читаться всеми одновременно (протокол писателей-читателей). Все модификации файла нумеруются и каждая копия файла характеризуется номером версии – количеством ее модификаций. Каждой копии приписано некоторое количество голосов Vi. Пусть общее количество приписанных всем копиям голосов равно V. Определяется кворум записи Vw и кворум чтения Vr так, что
Vw > V/2 и Vw +Vr > V
Для записи требуется запросить разрешение у всех серверов и получить соответствующее количество (Vw) голосов от тех из них, кто владеет текущей версией копии (при получении разрешения процесс одновременно с количеством приписанных копии голосов получает и ее номер версии). Если его копия устарела (имеет меньший номер версии, чем максимальный из полученных номеров), то до модификации копии ее надо обновить.
Кворум записи выбран так, что два процесса не смогут одновременно получить разрешение на запись.
Выполнив модификацию, процесс рассылает ее всем владельцам текущей версии файла.
Для чтения достаточно получить необходимое число голосов (Vr) от любых серверов. Кворум чтения выбран так, что хотя бы один из тех серверов, от которых получено разрешение, является владельцем текущей копии файла. Необходимо отметить, что при одновременном запросе разрешений на запись несколькими процессами, возможна ситуация, когда голоса разделятся и ни один из процессов не получит кворума. Для выхода из таких ситуаций процессы должны по истечению тайм-аута отказаться от своего запроса (сообщить об этом всем серверам, приславшим им разрешения), а затем повторить запрос.
Описанная схема базируется на статическом распределении голосов. Различие в голосах, приписанных разным серверам, позволяет учесть их особенности (надежность, эффективность). Еще большую гибкость предоставляет метод динамического перераспределения голосов.
Для того, чтобы выход из строя некоторых серверов не привел к ситуации, когда невозможно получить кворум, применяется механизм изменения состава голосующих.
Протоколы принятия единого решения
Необходимо отметить, что в условиях отсутствия надежных коммуникаций (с ограниченным временем задержки) не может быть алгоритма достижения единого решения. Рассмотрим известную «проблему двух армий».
Армия зеленых численностью 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.
2-ой шаг. Каждый формирует свой вектор из имеющейся информации.
Получается:
vect1 (1,2,x,4)
vect2 (1,2,y,4)
vect3 (1,2,3,4)
vect4 (1,2,z,4)
3-ий шаг. Каждый посылает свой вектор всем остальным (генерал-3 посылает опять произвольные значения).
Генералы получают следующие вектора:
|
g1 |
g2 |
g3 |
g4 |
|
(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) |
Все лояльные генералы получают один вектор (1,2,»неизвестен»,4) - согласие достигнуто.
Если рассмотреть случай n=3 и m=1, то согласие не будет достигнуто.
Lamport доказал, что в системе с m неверно работающими процессорами можно достичь согласия только при наличии 2m+1 верно работающих процессоров (более 2/3).
Другие авторы доказали, что в распределенной системе с асинхронными процессорами и неограниченными коммуникационными задержками согласие невозможно достичь даже при одном неработающем процессоре (даже если он не подает признаков жизни).
Применение алгоритма - надежная синхронизация часов.
Алгоритм надежных неделимых широковещательных рассылок сообщений.
Алгоритм выполняется в две фазы и предполагает наличие в каждом процессоре очередей для запоминания поступающих сообщений. В качестве уникального идентификатора сообщения используется его начальный приоритет - логическое время отправления, значение которого на разных процессорах различно.
1-ая фаза.
Процесс- отправитель посылает сообщение группе процессов (список их идентификаторов содержится в сообщении).
При получении этого сообщения процессы:
· Приписывают сообщению приоритет, помечают сообщение как «недоставленное» и буферизуют его. В качестве приоритета используется временная метка (текущее логическое время).
· Информируют отправителя о приписанном сообщению приоритете.
2-ая фаза.
При получении ответов от всех адресатов, отправитель:
· Выбирает из всех приписанных сообщению приоритетов максимальный и устанавливает его в качестве окончательного приоритета сообщения.
· Рассылает всем адресатам этот приоритет.
Получив окончательный приоритет, получатель:
a) Приписывает сообщению этот приоритет.
b) Помечает сообщение как «доставленное».
c) Упорядочивает все буферизованные сообщения по возрастанию их приписанных приоритетов.
d) Если первое сообщение в очереди отмечено как «доставленное», то оно будет обрабатываться как окончательно полученное.
Если получатель обнаружит, что он имеет сообщение с пометкой «недоставленное», отправитель которого сломался, то он для завершения выполнения протокола осуществляет следующие два шага в качестве координатора.
1. Опрашивает всех получателей о статусе этого сообщения.
Получатель может ответить одним из трех способов:
· Сообщение отмечено как «недоставленное» и ему приписан такой-то приоритет.
· Сообщение отмечено как «доставленное» и имеет такой-то окончательный приоритет.
· Он не получал это сообщение.
2. Получив все ответы координатор выполняет следующие действия:
· Если сообщение у какого-то получателя помечено как «доставленное», то его окончательный приоритет рассылается всем. (Получив это сообщение каждый процесс выполняет шаги фазы 2).
· Иначе координатор заново начинает весь протокол с фазы 1. (Повторная посылка сообщения с одинаковым приоритетом не должна вызывать коллизий).
Необходимо заметить, что алгоритм требует хранения начального и окончательного приоритетов даже для принятых и уже обработанных сообщений.
