В.А. Крюков - Операционные системы распределенных вычислительных систем, страница 11
Описание файла
PDF-файл из архива "В.А. Крюков - Операционные системы распределенных вычислительных систем", который расположен в категории "". Всё это находится в предмете "распределённые системы" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 11 страницы из PDF
Для этого можнофиксировать на каждом процессоре максимальный номер витка, на котором переменнойприсваивается значение. При распределении витков последовательными блоками междупроцессорами достаточно фиксировать сам факт изменения переменной каждым процессором.Вне цикла приведение в консистентное состояние переменной A[0] не требуется, посколькуна каждом процессоре выполняется один и тот же оператор, который присваивает одно и тоже значение всем копиям переменной.6.5.3 DSM на базе объектов.Последнюю группу образуют многопроцессорные системы с объектной организациейраспределенной общей памятью.
В отличие от всех остальных рассмотренных систем,программы для объектно-ориентированной DSM системы не могут напрямую использоватьобщие переменные, а только через специальные функции-методы. Система поддержкивыполнения параллельных программ, получив запрос на использование некоторой общейпеременной, обрабатывает его, поддерживая при этом консистентное состояниеразделяемых данных. Весь контроль осуществляется только программными средствами.В тех случаях, когда для балансировки загрузки процессоров применяется миграцияданных, воспользоваться соседством расположения данныхв локальной памятипроцессора затруднительно.
В таких случаях потери эффективности из-за доступа к даннымчерез функции могут быть вполне приемлемыми, поскольку они могут сполнакомпенсироваться тем выигрышем, который достигается балансировкой загрузки.437.Обеспечение надежности в распределенных системах.Отказом системы называется поведение системы, не удовлетворяющее ее спецификациям.Последствия отказа могут быть различными.Отказ системы может быть вызван отказом (неверным срабатыванием) каких-то еекомпонентов (процессор, память, устройства ввода/вывода, линии связи, или программноеобеспечение).Отказ компонента может быть вызван ошибками при конструировании, при производстве илипрограммировании.
Он может быть также вызван физическим повреждением, изнашиваниемоборудования, некорректными входными данными, ошибками оператора, и многими другимипричинами.Отказы могут быть случайными, периодическими или постоянными.Случайные отказы (сбои) при повторении операции исчезают.Причиной такого сбоя может служить, например, электромагнитная помеха от проезжающегомимо трамвая. Другой пример - редкая ситуация в последовательности обращений коперационной системе от разных задач.Периодические отказы повторяются часто в течение какого-то времени, а затем могут долго непроисходить.
Примеры - плохой контакт, некорректная работа ОС после обработкиаварийного завершения задачи.Постоянные (устойчивые) отказы не прекращаются до устранения их причины - разрушениядиска, выхода из строя микросхемы или ошибки в программе.Отказы по характеру своего проявления подразделяются на «византийские» (система активнаи может проявлять себя по-разному, даже злонамеренно) и «пропажа признаков жизни»(частичная или полная). Первые распознать гораздо сложнее, чем вторые. Свое название ониполучили по имени Византийской империи (330-1453 гг.), где расцветали конспирация,интриги и обман.Для обеспечения надежного решения задач в условиях отказов системы применяются двапринципиально различающихся подхода - восстановление решения после отказа системы (илиее компонента) и предотвращение отказа системы (отказоустойчивость).7.1.
Восстановление после отказа.Восстановление может быть прямым (без возврата к прошлому состоянию) и возвратное.Прямое восстановление основано на своевременном обнаружении сбоя и ликвидации егопоследствий путем приведения некорректного состояния системы в корректное. Такоевосстановление возможно только для определенного набора заранее предусмотренных сбоев.При возвратном восстановлении происходит возврат процесса (или системы) изнекорректного состояния в некоторое из предшествующих корректных состояний. При этомвозникают следующие проблемы.(1)Потери производительности, вызванные запоминанием состояний, восстановлениемзапомненного состояния и повторением ранее выполненной работы, могут быть слишкомвысоки.(2)Нет гарантии, что сбой снова не повторится после восстановления.(3)Для некоторых компонентов системы восстановление в предшествующее состояниеможет быть невозможно (торговый автомат).Тем не менее этот подход является более универсальным и применяется гораздо чаще первого.Дальнейшее рассмотрение будет ограничено только данным подходом.44Для восстановления состояния в традиционных ЭВМ применяются два метода (и ихкомбинация), основанные на промежуточной фиксации состояния либо ведении журналавыполняемых операций.
Они различаются объемом запоминаемой информацией и временем,требуемым для восстановления.Применение подобных методов в распределенных системах наталкивается на следующиетрудности.7.1.1. Сообщения-сироты и эффект домино.Xx1y1YZx2x3y2z1ttz2tНа рисунке показаны три процесса (X,Y,Z), взаимодействующие через сообщения.Вертикальные черточки показывают на временной оси моменты запоминания состоянияпроцесса для восстановления в случае отказа. Стрелочки соответствуют сообщениям ипоказывают моменты их отправления и получения.Если процесс X сломается, то он может быть восстановлен с состояния x3 без какого-либовоздействия на другие процессы.Предположим, что процесс Y сломался после посылки сообщения m и был возвращен всостояние y2.
В этом случае получение сообщения m зафиксировано в x3, а его посылка неотмечена в y2. Такая ситуация, возникшая из-за несогласованности глобального состояния, недолжна допускаться (пример - сообщение содержит сумму, переводимую с одного счета надругой). Сообщение m в таком случае называется сообщением-сиротой.
Процесс X долженбыть возвращен в предыдущее состояние x2 и конфликт будет ликвидирован.Предположим теперь, что процесс Z сломается и будет восстановлен в состояние z2. Этоприведет к откату процесса Y в y1, а затем и процессов X и Z в начальные состояния x1 и y1.Этот эффект известен как эффект домино.7.1.2. Потеря сообщений.x1XtmYy1xотказtПредположим, что контрольные точки x1 и y1 зафиксированы для восстановления процессовX и Y, соответственно.45Если процесс Y сломается после получения сообщения m, и оба процесса будутвосстановлены (x1,y1), то сообщение m будет потеряно (его потеря будет неотличима отпотери в канале).7.1.3.
Проблема бесконечного восстановления.Xx1tn1Ym1y1xотказtПроцесс Y сломался до получения сообщения n1 от X. Когда Yвернулся в состояние y1, в нем не оказалось записи о посылке сообщения m1. Поэтому Xдолжен вернуться в состояние x1.Xtn2n1Yy1m2x2-ой откатtПосле отката Y посылает m2 и принимает n1 (сообщение-призрак). Процесс X после отката кx1 посылает n2 и принимает m2.
Однако X после отката уже не имеет записи о посылке n1.Поэтому Y должен повторно откатиться к y1. Теперь X должен откатиться к x1, поскольку онпринял m2, о посылке которого в Y нет записи. Эта ситуация будет повторяться бесконечно.7.1.4. Консистентное множество контрольных точек.Описанные выше трудности показывают, что глобальная контрольная точка, состоящая изпроизвольной совокупности локальных контрольных точек, не обеспечивает восстановлениявзаимодействующих процессов.Для распределенных систем запоминание согласованного глобального состояния являетсясерьезной теоретической проблемой.Множество контрольных точек называется строго консистентным, если во время егофиксации никаких обменов между процессами не было.
Оно соответствует понятию строгоконсистентного глобального состояния, когда все посланные сообщения получены и нетникаких сообщений в каналах связи. Множество контрольных точек называетсяконсистентным, если для любой зафиксированной операции приема сообщения,соответствующая операция посылки также зафиксирована (нет сообщений-сирот).Простой метод фиксации консистентного множества контрольных точек - фиксациялокальной контрольной точки после каждой операции посылки сообщения. При этом посылкасообщения и фиксация должны быть единой неделимой операцией (транзакцией). Множествопоследних локальных контрольных точек является консистентным (но не строгоконсистентным).Чтобы избежать потерь сообщений при восстановлении с использованием консистентногомножества контрольных точек необходимо повторить отправку тех сообщений, квитанции о46получении которых стали недействительными в результате отката. Используя временныеметки сообщений можно распознавать сообщения-призраки и избежать бесконечноговосстановления.7.1.5.
Синхронная фиксация контрольных точек и восстановление.Ниже описываются алгоритмы создания консистентного множества контрольных точек ииспользования их для восстановления без опасности бесконечного зацикливания.Алгоритм создания консистентного множества контрольных точек.К распределенной системе алгоритм предъявляет следующие требования.(1) Процессы взаимодействуют посредством посылки сообщений через коммуникационныеканалы.(2) Каналы работают по алгоритму FIFO.
Коммуникационные протоколы точка-точкагарантируют невозможность пропажи сообщений из-за ошибок коммуникаций или отката кконтрольной точке. (Другой способ обеспечения этого - использование стабильной памяти дляжурнала посылаемых сообщений и фиксации идентификатора последнего полученного поканалу сообщения).Алгоритм создает в стабильной памяти два вида контрольных точек - постоянные и пробные.Постоянная контрольная точка - это локальная контрольная точка, являющаяся частьюконсистентной глобальной контрольной точки.
Пробная контрольная точка - это временнаяконтрольная точка, которая становится постоянной только в случае успешного завершенияалгоритма. Алгоритм исходит из того, что только один процесс инициирует созданиемножества контрольных точек, а также из того, что никто из участников не сломается вовремя работы алгоритма.Алгоритм выполняется в две фазы.1-ая фаза.Инициатор фиксации (процесс Pi) создает пробную контрольную точку и просит всеостальные процессы сделать то же самое.