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

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

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

Для этого можнофиксировать на каждом процессоре максимальный номер витка, накотором переменной присваивается значение. При распределениивитков последовательными блоками между процессорамидостаточно фиксировать сам факт изменения переменной каждымпроцессором.Вне цикла приведение в консистентное состояние переменнойA[0] не требуется, поскольку на каждом процессоре выполняетсяодин и тот же оператор, который присваивает одно и то жезначение всем копиям переменной.6.5.3 DSM на базе объектов.Последнюю группу образуют многопроцессорные системы собъектной организацией распределенной общей памятью.

Вотличие от всех остальных рассмотренных систем, программыдля объектно-ориентированной DSM системы не могутнапрямую использовать общие переменные, а только черезспециальные функции-методы. Система поддержки выполненияпараллельных программ, получив запрос на использованиенекоторой общей переменной, обрабатывает его, поддерживаяпри этом консистентное состояние разделяемых данных. Веськонтроль осуществляется только программными средствами.В тех случаях, когда для балансировки загрузки процессоровприменяется миграция данных, воспользоваться соседствомрасположения данныхв локальной памяти процессоразатруднительно. В таких случаях потери эффективности из-задоступа к данным через функции могут быть вполнеприемлемыми, поскольку они могут сполна компенсироватьсятем выигрышем, который достигается балансировкой загрузки.7.Обеспечение надежности в распределенных системах.Отказомсистемыназываетсяповедениесистемы,неудовлетворяющее ее спецификациям.

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

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

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

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

Они различаются объемом запоминаемой информациейи временем, требуемым для восстановления.Применение подобных методов в распределенных системахнаталкивается на следующие трудности.7.1.1. Сообщения-сироты и эффект домино.Xx1y1YZx2z1y2z2x3tttНа рисунке показаны три процесса (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. Потеря сообщений.x1Xtmy1YxотказtПредположим, что контрольные точки x1 и y1 зафиксированы длявосстановления процессов X и Y, соответственно.Если процесс Y сломается после получения сообщения m, и обапроцесса будут восстановлены (x1,y1), то сообщение m будетпотеряно (его потеря будет неотличима от потери в канале).7.1.3.

Проблема бесконечного восстановления.Xx1tn1Yy1m1xотказ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.

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

При этом посылкасообщения и фиксация должны быть единой неделимой операцией(транзакцией). Множество последних локальных контрольныхточек является консистентным (но не строго консистентным).Чтобы избежать потерь сообщений при восстановлении сиспользованием консистентного множества контрольных точекнеобходимо повторить отправку тех сообщений, квитанции ополучении которых стали недействительными в результате отката.Используя временные метки сообщений можно распознаватьсообщения-призраки и избежать бесконечного восстановления.7.1.5. Синхроннаяфиксацияконтрольныхточекивосстановление.Ниже описываются алгоритмы создания консистентногомножества контрольных точек и использования их длявосстановления без опасности бесконечного зацикливания.Алгоритм создания консистентного множества контрольныхточек.К распределенной системе алгоритм предъявляет следующиетребования.(1) Процессы взаимодействуют посредством посылки сообщенийчерез коммуникационные каналы.(2) Каналы работают по алгоритму FIFO.

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

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

Приэтом процессу запрещается посылать неслужебные сообщенияпосле того, как он сделает пробную контрольную точку. Каждыйпроцесс извещает Pi о том, сделал ли он пробную контрольнуюточку. Если все процессы сделали пробные контрольные точки, тоPi принимает решение о превращении пробных точек впостоянные. Если какой-либо процесс не смог сделать пробнуюточку, то принимается решение об отмене всех пробных точек.2-ая фаза.Pi информирует все процессы о своем решении.

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

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