1 Операционные системы и оболочки Одинцов Игорь Олегович ст. преподаватель кафедры информатики весна 2006 Слайды можно взять на сайтах: и

2 Лекция 11 Специализированные ОС Грид

3 План лекции Отказоустойчивые системы Системы реального времени Грид

4 Отказы Отказом системы называется поведение системы, не удовлетворяющее ее спецификациям Последствия отказа могут быть различными Незначительные … Катастрофические Необходимо предотвращать отказы!

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

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

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

8 Подходы к решению проблемы отказов Для обеспечения надежного решения задач в условиях отказов системы применяются два принципиально различающихся подхода: восстановление решения после отказа системы (или ее компонента) предотвращение отказа системы (отказоустойчивость)

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

10 Проблемы: сообщения-сироты и эффект домино Если процесс X сломается, то он может быть восстановлен с состояния x3 без какого-либо воздействия на другие процессы. Предположим, что процесс Y сломался после посылки сообщения m и был возвращен в состояние y2. В этом случае получение сообщения m зафиксировано в x3, а его посылка не отмечена в y2. Такая ситуация, возникшая из-за несогласованности глобального состояния, не должна допускаться (пример - сообщение содержит сумму, переводимую с одного счета на другой). Сообщение m в таком случае называется сообщением-сиротой. Процесс X должен быть возвращен в предыдущее состояние x2 и конфликт будет ликвидирован. Предположим, что процесс Z сломается и будет восстановлен в состояние z2. Это приведет к откату процесса Y в y1, а затем и процессов X и Z в начальные состояния x1 и y1. Этот эффект известен как эффект домино. На рисунке показаны три процесса (X,Y,Z), взаимодействующие через сообщения. Вертикальные черточки показывают на временной оси моменты запоминания состояния процесса для восстановления в случае отказа. Стрелочки соответствуют сообщениям и показывают моменты их отправления и получения.

11 Проблемы: потеря сообщений Предположим, что контрольные точки x1 и y1 зафиксированы для восстановления процессов X и Y, соответственно. Если процесс Y сломается после получения сообщения m, и оба процесса будут восстановлены (x1,y1), то сообщение m будет потеряно (его потеря будет неотличима от потери в канале).

12 Проблемы: бесконечное восстановление Процесс Y сломался до получения сообщения n1 от X. Когда Y вернулся в состояние y1, в нем не оказалось записи о посылке сообщения m1. Поэтому X должен вернуться в состояние x1 После отката Y посылает m2 и принимает n1 (сообщение- призрак). Процесс X после отката к x1 посылает n2 и принимает m2. Однако X после отката уже не имеет записи о посылке n1. Поэтому Y должен повторно откатиться к y1. Теперь X должен откатиться к x1, поскольку он принял m2, о посылке которого в Y нет записи. Эта ситуация будет повторяться бесконечно…

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

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

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

16 Протоколы принятия единого решения В условиях отсутствия надежных коммуникаций (с ограниченным временем задержки) не может быть алгоритма достижения единого решения. Рассмотрим известную «проблему двух армий» Я имею план – давай атаковать завтра на рассвете

17 Протокол принятия согласованных решений Задача «Византийских генералов». В этой задаче армия «оранжевых» находится в долине, а n «синих» генералов возглавляют свои армии, расположенные в горах. Связь осуществляется по телефону и является надежной, но из n генералов m являются предателями. Предатели активно пытаются воспрепятствовать согласию лояльных генералов. Нападать! Отступать! Нападать! Отступать! Нападать! Генерал 1 Генерал 2 Генерал 3 Предатель Генерал 4

18 Алгоритм Лампорта Проиллюстрируем его для случая 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)

19 Алгоритм Лампорта 3-ий шаг. Каждый посылает свой вектор всем остальным (генерал-3 посылает опять произвольные значения). 4-ый шаг. Каждый генерал проверяет каждый элемент во всех полученных векторах. Если какое-то значение совпадает по меньшей мере в двух векторах, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается «неизвестен». Все лояльные генералы получают один вектор (1,2,«неизвестен»,4) - согласие достигнуто. Г1Г2Г3Г4 (1,2,y,4)(1,2,x,4) (a,b,c,d)(e,f,g,h)(1,2,y,4) (1,2,z,4) (i,j,k,l) Если рассмотреть случай n=3 и m=1, то согласие не будет достигнуто. Лампорт доказал, что в системе с m неверно работающими процессорами можно достичь согласия только при наличии 2m+1 верно работающих процессоров (более 2/3).

20 План лекции Отказоустойчивые системы Системы реального времени Грид

21 Системы реального времени В ответ на событие система должна отреагировать определенным образом до определенного времени Когда дается ответ так же важно, как и какой Два типа систем (по степени серьезности ограничений) Мягкие ограничения Жесткие ограничения

22 Проблемы проектирования систем реального времени Выбор источника инициации Событие (событие-сенсор-прерывание) Время (прерывание только по таймеру) Предсказуемость (все ли будет вовремя в момент пиковой загрузки?) Отказоустойчивость Языковая поддержка максимум времени исполнения переложить на время компиляции язык не должен поддерживать циклы типа while, цикл for только с константными параметрами отказ от рекурсии специальная переменная clock периодические события every (…) {…} …

23 План лекции Отказоустойчивые системы Системы реального времени Грид

24 Грид-вычисления и Грид-технологии Grid-вычисления – это один из методов распределенных вычислений, базирующийся на идеях использования распределенных процессорных мощностей, приложений, данных, систем хранения и сетевых ресурсов. Метод стал во многом популярным благодаря возможности использовать незанятые вычислительные ресурсы, разбросанные по всему миру. В основу современного понимания Grid-технологий ставится следующий принцип: пользователь не должен задумываться о том, на каком физическом компьютере хранятся данные и исполняются программы. В задачу программного обеспечения Grid-системы входит обеспечение соответствующего уровня абстракции, а также - решение возникающих в связи с этим вопросов безопасности, надежности и поиска ресурсов. Интерес к Grid есть практически у всех лидирующих технологических компаний (IBM, HP, Sun Microsystems, Intel, …)

25 Кластеры и грид КластерыГрид Локальные узлы, гомогенная архитектура, высокоскоростная связь между узлами (сильно- связная архитектура) Распределенные и удаленные узлы, гетерогенная архитектура, LAN/WAN/Internet (слабо- связная архитектура) Явное предоставление архитектуры и ресурсов Скрывает детали архитектуры, виртуализация ресурсов Управляется как единое целое, одна организация Распределенное управление, несколько организаций Статическое распределение ресурсов Динамический поиск ресурсов Не требует повышенных мер обеспечения безопасности, поскольку находится в защищенной сети Обеспечение целостности и конфиденциальности информации, устойчивость к сетевым атакам

26 Некоторые возможные классификации грид По организационной структуре Intra–Grid: ограничен рамками одной организации (не требует высокого уровня безопасности) Inter–Grid: включает многие организации По функциональности (ориентация на типы приложений) Вычислительный Grid Grid данных … По моделям использования …

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

28 Проблемы текущего состояния (2) Одной из важных проблем развития грид-технологий до сих пор являлась проблема наполнения грид-систем приложениями. Трудности возникали в связи с тем, что грид для многих до сих пор оставался скорее инструментом для научных исследований, и разработкой соответствующего программного обеспечения в основном занимались люди, более близкие к прикладным областям, нежели к современному системному программированию. (Еще раз, как следствие, отметим, что грид-системы долгое время действовали вне рамок каких-либо общепринятых стандартов) Необходим высокоуровневый инструментарий, облегчающий перенос приложений на грид- системы

29 Проблемы текущего состояния (3) Существует большое количество международных исследовательских проектов: UniGridS: Переносимый WSRF-совместимый аналог системы UNICORE NextGrid: Следующее поколение грид-архитектур SimDAT: Грид инфраструктуры для различных областей приложений Анализ конкретных проектов и сбор требований к средам программирования Инструментарий должен являться продуктом с открытым исходным кодом.

30 Стандартизация (1) Отдельные компоненты современных Grid-систем второго поколения представляют собой веб-сервисы. Общение между ними осуществляется с использованием стандартных Интернет-протоколов. При этом широко используются интерфейсы и шаблоны проектирования, определенные семейством стандартов Web Services Resource Framework (WSRF) - управление ресурсами с помощью Веб-сервисов. Базовые принципы построения архитектуры Grid- системы получили общее название Open Grid Services Architecture (OGSA) - построение открытой архитектуры Grid-сервисов.

31 Технологии и спецификации: веб и грид Grid Web WSRF OGSI GT2 GT1 HTTP WSDL, WS-* WSDL 2, WSDM Слияние!

32 Стандартизация (2) Для описания взаимодействия ресурсов Grid используется Business Process Execution Language (BPEL) - стандарт описания взаимодействия web- сервисов. Отдельные задачи определяются с использованием Job Submission Description Language (JSDL) - стандартный язык, используемый для описания атомарных задач. Планируется реализация поддержки Common Information Model (CIM) - стандартного языка описания состояния Интернет-ресурсов, активно используемого в задачах конфигурирования распределенных систем

33 Типичная компонентная структура

34 Спасибо! Вопросы?

35 P.S. Экзаменационные вопросы: Отказоустойчивые системы Системы реального времени Грид