7-Fault_T (1158857), страница 2
Текст из файла (страница 2)
Наглядный пример - тройное дублирование аппаратуры в бортовых компьютерах и голосование при принятии решения.
Другие примеры – размножение страниц в DSM и размножение файлов в распределенных файловых системах. При этом очень важным моментом является наличие механизма неделимых широковещательных рассылок сообщений (они должны приходить всем в одном порядке).
Алгоритмы голосования.
Общая схема использования голосования при размножении файлов может быть представлена следующим образом.
Файл может модифицироваться разными процессами только последовательно (при открытии файла на запись процесс-писатель будет ждать закрытия файла другим писателем или всеми читателями), а читаться всеми одновременно (протокол писателей-читателей). Все модификации файла нумеруются и каждая копия файла характеризуется номером версии – количеством ее модификаций. Каждой копии приписано некоторое количество голосов Vi. Пусть общее количество приписанных всем копиям голосов равно V. Определяется кворум записи Vw и кворум чтения Vr так, что
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) |
4-ый шаг. Каждый генерал проверяет каждый элемент во всех полученных векторах. Если какое-то значение совпадает по меньшей мере в двух векторах, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается «неизвестен».
Все лояльные генералы получают один вектор (1,2,»неизвестен»,4) - согласие достигнуто.
Если рассмотреть случай n=3 и m=1, то согласие не будет достигнуто.
Lamport доказал, что в системе с m неверно работающими процессорами можно достичь согласия только при наличии 2m+1 верно работающих процессоров (более 2/3).
Другие авторы доказали, что в распределенной системе с асинхронными процессорами и неограниченными коммуникационными задержками согласие невозможно достичь даже при одном неработающем процессоре (даже если он не подает признаков жизни).
Применение алгоритма - надежная синхронизация часов.
Алгоритм надежных неделимых широковещательных рассылок сообщений.
Алгоритм выполняется в две фазы и предполагает наличие в каждом процессоре очередей для запоминания поступающих сообщений. В качестве уникального идентификатора сообщения используется его начальный приоритет - логическое время отправления, значение которого на разных процессорах различно.
1-ая фаза.
Процесс-отправитель посылает сообщение группе процессов (список их идентификаторов содержится в сообщении).
При получении этого сообщения процессы:
-
Приписывают сообщению приоритет, помечают сообщение как «недоставленное» и буферизуют его. В качестве приоритета используется временная метка (текущее логическое время).
-
Информируют отправителя о приписанном сообщению приоритете.
2-ая фаза.
При получении ответов от всех адресатов, отправитель:
-
Выбирает из всех приписанных сообщению приоритетов максимальный и устанавливает его в качестве окончательного приоритета сообщения.
-
Рассылает всем адресатам этот приоритет.
Получив окончательный приоритет, получатель:
-
Приписывает сообщению этот приоритет.
-
Помечает сообщение как «доставленное».
-
Упорядочивает все буферизованные сообщения по возрастанию их приписанных приоритетов.
-
Если первое сообщение в очереди отмечено как «доставленное», то оно будет обрабатываться как окончательно полученное.
Если получатель обнаружит, что он имеет сообщение с пометкой «недоставленное», отправитель которого сломался, то он для завершения выполнения протокола осуществляет следующие два шага в качестве координатора.
1. Опрашивает всех получателей о статусе этого сообщения.
Получатель может ответить одним из трех способов:
-
Сообщение отмечено как «недоставленное» и ему приписан такой-то приоритет.
-
Сообщение отмечено как «доставленное» и имеет такой-то окончательный приоритет.
-
Он не получал это сообщение.
2. Получив все ответы координатор выполняет следующие действия:
-
Если сообщение у какого-то получателя помечено как «доставленное», то его окончательный приоритет рассылается всем. (Получив это сообщение каждый процесс выполняет шаги фазы 2).
-
Иначе координатор заново начинает весь протокол с фазы 1. (Повторная посылка сообщения с одинаковым приоритетом не должна вызывать коллизий).
Необходимо заметить, что алгоритм требует хранения начального и окончательного приоритетов даже для принятых и уже обработанных сообщений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
