Конспект лекций по дисциплине: распределенные вычислительные системы и сетевые технологии раздел icon

Конспект лекций по дисциплине: распределенные вычислительные системы и сетевые технологии раздел



Смотрите также:
Конспект лекций по дисциплине «сетевые технологии» (дополненная версия) для студентов...
Первое информационное сообщение 8 российская конференция с международным участием «новые...
Конспект лекций по дисциплине «Информационные технологии. Часть 1»...
Учебное пособие по курсу вычислительные системы, сети и телекоммуникации раздел...
Конспект лекций по дисциплине информационные технологии на транспорте Нижний Новгород...
Конспект лекций по дисциплине «Детерминационный анализ и интеллектуальные системы (да и ис)»...
Конспект лекций по дисциплине «Автоматизированный электропривод»...
Учебно-методический комплекс по дисциплине вычислительные системы...
Конспект лекций Конспект лекций по дисциплине "Организационное поведение"...
Конспект лекций по дисциплине Автоматизированные системы управления на автомобильном транспорте...
Программа по дисциплине «Сетевые технологии» по направлениям: «Математика. Компьютерные науки»...
Конспект лекций Чебоксары 2006 удк 004 Составитель: В. Г...



страницы:   1   2   3
скачать


МИНИСТЕРСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ

ПО СВЯЗИ И ИНФОРМАТИЗАЦИИ


Московский технический университет связи и информатики

_______________________________________________________

Кафедра вычислительной техники и управляющих систем


Е.Н. ТУРУТА


КОНСПЕКТ ЛЕКЦИЙ

по дисциплине:

РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ И СЕТЕВЫЕ ТЕХНОЛОГИИ


Раздел

ОТКАЗОУСТОЙЧИВОСТЬ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ


Москва – 2001


УДК 681.324

План УМД 2001/2002 уч.г.


КОНСПЕКТ ЛЕКЦИЙ

по дисциплине:

" Распределенные вычислительные системы и сетевые технологии"


Раздел

"ОТКАЗОУСТОЙЧИВОСТЬ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ"


(специальность 220100 и направление магистерской подготовки 552800)


Автор Е.Н. Турута, доктор технических наук

Издание утверждено методическим советом университета в качестве конспекта лекций.


Протокол № от 16. 03. 2001 г.


Рецензенты В.Д. Малюгин, доктор технических наук, профессор,

Б.Д. Пичкур, кандидат технических наук, доцент


ВВЕДЕНИЕ

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

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

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

В курсе РВСиСТ раздел "Отказоустойчивость распределенных вычислительных систем" занимает важное место. В нем рассматриваются как традиционные методы построения ОУ-систем , т.е. сложившиеся достаточно "давно" (в 60-70-е годы) и занимающие прочное место в практических разработках, так и более новые тенденции и направления. К традиционным методам относят различные виды резервирования, N-модульную избыточность с голосованием, дублирование ПМ со сравнением результатов и др. Эти методы широко освещены в литературе, они совершенствуются и развиваются. Однако, в чистом виде они не учитывают распределенность структуры современных ВС и наличие в них "естественной " аппаратной и временной избыточности, которая может быть использована для обеспечения отказоустойчивости. Вследствие этого при высоких требованиях к надежности ВС применение этих методов приводит к чрезмерной избыточности и большим дополнительным затратам, а часто и не позволяет достичь поставленных требований к надежности при заданных стоимостных, аппаратурных, весо-габаритных, технологических и других ограничениях.

Это обстоятельство стимулирует развитие таких подходов к построению отказоустойчивых РВС, которые учитывают их структурную и функциональную распределенность и позволяют наиболее полно использовать естественные избыточные ресурсы, являющиеся следствием такой распределенности. Это достигается с помощью гибкого изменения структуры РВС при отказах ее ПМ ("реконфигурации") с целью блокирования отказавших ПМ и перераспределения выполняемых системой задач между неотказавшими ПМ при учете допустимости функционирования РВС с ухудшенными в заданных пределах показателями качества ("постепенная деградация"). В этом направлении выполнено достаточно большое количество исследований и создан ряд практических разработок, отраженных напр., в [1,2], а также в трудах международных конференций по отказоустойчивости ВС, наиболее авторитетной из которых является Ежегодный международный симпозиум по отказоустойчивым вычислительным системам (Annual International Symposium on FAULT-TOLERANT COMPUTING SYSTEMS - FTCS). Однако целостная концепция построения отказоустойчивых РВС на базе этих свойств начала формироваться только в последние годы. Важное место в ней занимают модели и методы рационального (т.е. оптимизированного) перераспределения задач при отказах ПМ.

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


^ 1. БЕЗОТКАЗНОСТЬ И ОТКАЗОУСТОЙЧИВОСТЬ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (ВС)


Надежность ВС (как и любых технических объектов) характеризуется совокупностью свойств безотказности, ремонтопригодности, сохраняемости и долговечности [3,4].

Безотказность - это свойство системы непрерывно сохранять работоспособность (работоспособное состояние) в течение некоторого времени, т.е. свойство не допускать отказов.

^ Отказ - событие, заключающееся в нарушении работоспособности ВС, т.е. вызывающее ее переход из работоспособного состояния в неработоспособное. Эти состояния характеризуются следующим образом.

^ Работоспособное состояние: значения всех существенных параметров (т.е. характеризующих способность ВС выполнять заданные функции), соответствуют требованиям научно-технической документации (НТД).

^ Неработоспособное состояние: значение хотя бы одного из существенных параметров не соответствует требованиям НТД.

Безотказность ВС характеризуется рядом показателей, основанных на понятии наработки, т.е. продолжительности или объема работы, выполненной системой [3 - 6]. К ним относятся вероятность безотказной работы ВС в течение заданного интервала времени, среднее время работы до отказа (для невосстанавливаемых ВС), среднее время безотказной работы (для восстанавливаемых ВС), коэффициент готовности - комплексный показатель, оценивающий безотказность и ремонтопригодность восстанавливаемых ВС.

Безотказность невосстанавливаемых элементов обычно оценивается интенсивностью отказов, восстанавливаемых - параметром потока отказов.

Термин "отказоустойчивость" (Fault-Tolerance), прочно утвердившийся к настоящему времени, впервые появился в конце 60-х гг. в работах А. Авижениса, сформулировавшего основы этого направления [7,8]. Однако отсутствие строгого определения данного понятия позволяет различным авторам вкладывать в него разный смысл. При этом теряются четкие различия между этим понятием и понятиями "надежность", "безотказность", "живучесть". Нами предлагается следующая трактовка понятия "отказоустойчивость", базирующаяся на его соотношении с известными понятиями теории надежности.

Понятие безотказности системы предполагает, что отказ системы является следствием отказов ее элементов. Однако, обратное в общем случае неверно: наличие отказов элементов не всегда приводит к отказу системы. Существуют системы, сохраняющие работоспособное состояние при отказах некоторых элементов.

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

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

^ ОтказоНЕустойчивая система - это система, не обладающая свойством отказоустойчивости по отношению ни к одному из возможных подмножеств ее элементов. Эта система сохраняет свое работоспособное состояние только при отсутствии отказов всех ее элементов.

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

Таким образом, безотказность - это способность системы сохранять работоспособное состояние в течение некоторого времени как при отсутствии, так и при наличии отказов элементов в течение этого времени, отказоустойчивость - это способность системы сохранять работоспособное состояние в течение определенного времени только при условии, что в течение этого времени имеют место отказы ее элементов.

Рассматриваем далее только внезапные отказы элементов ВС [3-6], независимые друг от друга, и полагаем, что каждый элемент может находиться только в одном из двух состояний - работоспособном или неработоспособном (т.е. в состоянии отказа).

^ Структурное состояние (s-состояние) ВС, состоящей из n элементов, представляется вектором s = 1,...,n,, где i, {0,1}, i = 0, если i-й элемент работоспособен, i = 1, если i-й элемент отказал, i = 1,...,n; = 1,...,2n. Начальным называется s-состояние s0 = 0,...,0; искаженным - любое s-состояние s  s0 (далее обозначаемое s), конечным - s-состояние s1 = 1,..,1 (отказ всех элементов).

Пусть s = {s }, = 1, ...,2n, - множество всех s-состояний ВС. На основе принятого критерия отказа оно разбивается на два непересекающихся подмножества: s = S  SF, где S - подмножество работоспособных s-состояний, SF - подмножество неработоспособных s-состояний (соответствующих отказу ВС). Для отказоНЕустойчивой ВС подмножество S включает только начальное s-состояние s0, для отказоустойчивой ВС - кроме s0 еще хотя бы одно искаженное s-состояние s , не совпадающее с s1 . Отказоустойчивость ВС можно оценивать с помощью известных показателей безотказности.

Таким образом, есть два пути повышения безотказности систем:

(1) увеличение вероятности сохранения системой начального s-состояния, т.е. вероятности отсутствия отказов всех элементов в течение определенного времени за счет повышения безотказности элементов (совершенствование технологии и т.п.);

(2) обеспечение для системы свойства отказоустойчивости.

Итак, отказоустойчивость - это одно из свойств, характеризующих надежность системы (в дополнение к указанным выше четырем свойствам). Понятие отказоустойчивости не заменяет понятия безотказности, а тем более надежности, а лишь дополняет их. Оно имеет смысл только по отношению к системе, т.е. к объекту, в котором можно выделить составные части - элементы, и выявить влияние состояний элементов на состояние системы. Понятия же надежности и безотказности применимы к любым объектам, в том числе и неделимым. Однако, эти понятия не раскрывают в явном виде, хотя и учитывают, свойство устойчивости системы к отказам элементов, так как надежность и безотказность могут достигаться и другими средствами. Введение понятия отказоустойчивости дает возможность четко выделить одно из важнейших направлений работ по созданию высоконадежных систем - разработку методов построения систем, устойчивых к отказам своих элементов. Далее излагаются основы концепции построения отказоустойчивых РВС на базе рационального статического перераспределения задач и ряд методов, разработанных в рамках этой концепции [9,10,11].


2. ОСНОВЫ КОНЦЕПЦИИ ОБЕСПЕЧЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ РАСПРЕДЕЛЕННЫХ ВС НА БАЗЕ РАЦИОНАЛЬНОГО ПЕРЕРАСПРЕДЕЛЕНИЯ ВЫПОЛНЯЕМЫХ ЗАДАЧ


^ 2.1. Взаимосвязь качества функционирования и отказоустойчивости

ВС. Виды перераспределения задач (ПЗ).


Произвольную РВС рассматриваем как множество H={M1,...,Mi,...,Mn}. процессорных модулей (ПМ), взаимодействующих посредством некоторой системы связи. Каждый ПМ Mi, содержит один или несколько процессоров, индивидуальную память и устройства интерфейса. Система взаимодействует с внешней средой (объекты управления, операторы и др.) с помощью выделенных для этого ПМ, имеющих необходимые периферийные устройства. Возможно наличие в системе общих ресурсов (внешняя память, базы данных, периферийные устройства и др.). Система выполняет фиксированное задание , т.е. известное множество задач = {U1,..,Uj,..,UL} с заданными требованиями к порядку их выполнения и взаимосвязи, определяющими класс задания ..

Качество функционирования системы характеризуется векторным показателем K=(K1,..,Kh,..,Km), где Kh, h =1,..,m, - частные показатели, оценивающие отдельные свойства системы (функциональные способности, производительность, среднее время выполнения задачи, время ответа, точность, выходной эффект и др.). Полагаем, что известно конечное множество возможных значений каждого частного показателя Kh, для данной системы, среди которых выделим два значения: номинальное - K0h, которое соответствует стандартным требованиям к функционированию системы в "штатном" режиме (т.е. при отсутствии каких-либо внешних или внутренних нарушений), и граничное - K*h, т.е. наихудшее значение частного показателя, которое может быть допущено при любых отклонениях о "штатного" режима. Для удобства анализа полагаем, что частные показатели определены таким образом, что ухудшение любого из рассматриваемых свойств системы, вызванное отклонениями от штатного режима, характеризуется уменьшением значения соответствующего показателя.

^ Состоянием качества системы (-состоянием) назовем произвольное значение векторного показателя - K = (K1,..,Kh,..,Km). Пусть K={K} - конечное множество всех возможных состояний системы, среди которых выделим номинальное состояние K0=(K01, ..., K0h, ..., K0m) и граничное -состояние K* = (K1,..,Kh,..,Km), т.е. такое, для которого хотя бы одно значение Kh = Kh .

Область работоспособности системы (Р-область) - это подмножество R={KR}, R K, таких -состояний KR = (KR1,..,KRh,..,KRm) для каждого из которых значения всех частных показателей KRh находятся в пределах заданных границ: K0h KRh K*h. Любое KRR называется работоспособным K-состоянием, а любое KRR - неработоспособным.

Отказом системы является событие, вызывающее ее выход за пределы области работоспособности, т.е. переход в любое из неработоспособных K-состояний.

В качестве элементов РВС, подверженных отказам, рассматриваем ее ПМ, полагая, что отказавший ПМ не способен выполнять никакие задачи, но его отказ не влияет на взаимодействие других ПМ. Отказы ПМ - это единственные рассматриваемые нами отклонения от штатного режима, вызывающие ухудшение частных показателей качества. Тогда функционирование системы в каждом s-состоянии (определяемом как набор отказавших и неотказавших ПМ) можно характеризовать некоторым значением векторного показателя качества K, полагая, что начальному s-состоянию s0 соответствует номинальное значение K0=(K01, ..., K0h, ..., K0m) , т.е. s0 K0 , а любому искаженному s-состоянию s - некоторое ухудшенное значение

K =(K1,..,Kh,..,Km), где каждое Kh K0h, т.е. s K .

Таким образом, каждому s-состоянию можно поставить в соответствие некоторое -состояние, т.е. можно построить отображение множества S всех s-состояний в множество K всех -состояний, обозначаемое : SK. При заданной области работоспособности R это отображение и определяет разбиение множества S на подмножества работоспособных и неработоспособных s-состояний (см. разд.1): S = S  SF, где S = {sr}, - структурная область работоспособности, т.е. подмножество таких s-состояний sr, каждое из которых отображается в некоторое K-состояние KRR; SF = {sf}, - подмножество s-состояний sf, отображаемых в K-состояния KRR..

Критерием отказа системы здесь является уменьшение значения хотя бы одного из частных показателей качества Kh за пределы его граничного значения Kh , и отказ системы формально может быть описан как событие:

F= {K1K1}  ...  {KhKh }  ...  {KmKm },

Очевидно, что отображение : SK определяет уровень отказоустойчивости системы. Ясно так же, что значения частных показателей качества функционирования системы в каждом s-состоянии sr (набор которых определяет -состояние KR, сопоставляемое с данным sr) зависят как от множества задач, выполняемых в состоянии sr, так и от распределения этих задач по работоспособным ПМ. Следовательно, отображение может быть реализовано в системе с помощью определенного распределения задач между работоспособными ПМ в каждом s-состоянии sr S. Под распределением задач (РЗ), понимается назначение каждой задачи множества в тот или иной ПМ для ее выполнения, в результате чего формируется план распределения задач для данного s-состояния. Процедуру построения таких планов для тех или иных искаженных s-состояний, являющихся следствием отказов ПМ, назовем перераспределением задач (ПЗ) при отказах ПМ.

Существуют два основных класса стратегий РЗ: статическое РЗ и динамическое РЗ. Обеспечение отказоустойчивости РВС может базироваться на стратегии того или другого из этих классов, т.е. на статическом или динамическом ПЗ.

Статическое ПЗ. До начала выполнения системой задания (т.е. при ее проектировании или подготовке к работе) для каждого s-состояния sr  S вычисляется рациональный план РЗ Dr, отвечающий заданным требованиям к отображению . Все задачи, которые должны быть назначены для выполнения в некоторый ПМ M i в соответствии с каждым из этих планов Dr, в совокупности образуют множество i. Задача Uj называется размещенной в ПМ M i, если Uj i, независимо от того, храниться ли программный модуль этой задачи в памяти данного ПМ или загружается в нее по мере необходимости.

Основным назовем такое размещение задач (РмЗ), при котором каждая из задач Uj 0, называемых основными, размещена в одном и только в одном ПМ. Это размещение совпадает с начальным планом РЗ (т.е. для начального состояния s0) и задается двоичной матрицей из L строк и n столбцов X=xji Ln = D0 = d 0ji Ln, где: xji = d0ji = 1, если задача Uj назначена в начальном состоянии для выполнения в ПМ M i и размещена в нем, xji = d0ji = 0 в противном случае.

Собственными задачами ПМ Mi назовем множество i задач, размещенных в ПМ Mi в соответствии с основным РмЗ (и выполняемых этим ПМ в состоянии s0).

Структурную область работоспособности S представим как S = s0  S, где S={s} - множество искаженных работоспособных s-состояний, т.е. состояний отображенных в Р-область .

^ Дополнительное РмЗ Y = yji Ln – это размещение резервных копий задач, которое формируется путем совмещения по правилу «дизъюнкции» планов РЗ D = d ji Ln , найденных для всех искаженных состояний sS:

.

Отказоустойчивое размещение задач (ОУ-РмЗ) Z=zji Ln строится на основе размещений X и Y по правилу: zji = xji yji . Оно приводит к резервированию задач, т.е. к размещению в различных ПМ нескольких резервных копий одной и той же задачи (не более одной копии каждой задачи в одном ПМ).

В начальном s-состоянии s0 выполняются только основные задачи в соответствии с начальным планом РЗ D0 (основным РмЗ). В случае перехода системы (вследствие отказов некоторой совокупности ПМ) в искаженное s-состояние s режим ее функционирования должен быть изменен в соответствии с планом РЗ D для этого состояния, что предполагает активизацию резервных копий задач в работоспособных ПМ в соответствии с данным планом и их выполнение наряду с основными задачами.

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

Далее рассматривается статическое ПЗ (СПЗ).





Скачать 0,58 Mb.
оставить комментарий
страница1/3
Е.Н. Турута
Дата29.09.2011
Размер0,58 Mb.
ТипКонспект, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3
Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх