Электронный коспект лекций (1162752), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

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

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

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

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

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

Во-вторых, протоколы принятия согласованныхрешений на основе полученных друг от друга данных. При этомнеобходимо всем исправным исполнителям получитьдостоверные данные от остальных исправных исполнителей, аданные от неисправных исполнителей проигнорировать.Ключевой подход для обеспечения отказоустойчивостиизбыточность (оборудования, процессов, данных).-7.2.1. Использование режима «горячего резерва» (второйпилот, резервное ПО).Проблема переключения на резервный исполнитель.7.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 посылает опять произвольные значения).Генералы получают следующие вектора: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-ый шаг. Каждый генерал проверяет каждый элемент во всехполученных векторах.

Если какое-то значение совпадает поменьшей мере в двух векторах, то оно помещается врезультирующий вектор, иначе соответствующий элементрезультирующего вектора помечается «неизвестен».Все лояльные генералы получают один вектор (1,2,»неизвестен»,4)- согласие достигнуто.Если рассмотреть случай n=3 и m=1, то согласие не будетдостигнуто.Lamport доказал, что в системе с m неверно работающимипроцессорами можно достичь согласия только при наличии 2m+1верно работающих процессоров (более 2/3).Другие авторы доказали, что в распределенной системе сасинхроннымипроцессорамиинеограниченнымикоммуникационными задержками согласие невозможно достичьдаже при одном неработающем процессоре (даже если он неподает признаков жизни).Применение алгоритма - надежная синхронизация часов.Алгоритм надежных неделимых широковещательных рассылоксообщений.Алгоритм выполняется в две фазы и предполагает наличие вкаждом процессоре очередей для запоминания поступающихсообщений.

Характеристики

Список файлов лекций