Имитационное моделирование надежности
Конечный автомат "в чистом виде" - это математическая модель устройства с конечной памятью, преобразующего дискретную информацию. Конечный автомат является одним из важнейших видов управляющих систем.
Содержательно конечный автомат можно охарактеризовать как устройство, имеющее входной и выходной каналы и находящееся в каждый из моментов дискретного времени, называемых тактовыми моментами, в одном из состояний. По входному каналу в каждый тактовый момент в устройство поступают сигналы a - буквы входного алфавита A; в те же моменты по выходному каналу устройство выдает сигналы b - буквы выходного алфавита B, причем b определяется состоянием s из алфавита состояний S и буквой а; внутреннее состояние яСв следующий тактовый момент также определяется состоянием s и буквой а из предыдущего момента. Таким образом, для некоторых функций j и f имеет место:
b = j (a,s), sC= f(a,s).
Эти функции называются соответственно выходной и переходной функциями; они определяют закон "переработки" слов в алфавите A, подаваемых побуквенно на входной канал устройства при условии задания начального состояния устройства.
Полное описание конечного автомата - описание, при котором функции перехода и выхода всюду определены.
Для конечных автоматов предполагается конечность алфавитов A, S, B. Если считать указанную "переработку" слов главной характеристикой устройства, то его можно отождествить с набором (A, S, B, j, f), который и называют конечным автоматом. Для этой формы описания конечного автомата характерно отношение исследователя к устройству как внешнего наблюдателя.
Само задание конечного автомата называется при этом абстрактным конечным автоматом. В случае, когда устройство рассматривается с учетом того, что оно собрано по некоторым композиционным правилам из абстрактных конечных автоматов, приходят к понятию структурного конечного автомата, который в итоге также реализует некоторый абстрактный конечный автомат.
Автомат вообще (от греческого automatoz - самодействующий) - управляющая система, являющаяся конечным автоматом или некоторой его модификацией, полученной путем изменения его компонентов или функционирования. Основное понятие - конечный автомат - возникло в середине XX в. в связи с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных автоматов.
Характерной особенностью такого описания является дискретность соответствующих математических моделей и конечность областей значений их параметров, что приводит к понятию конечного автомата.
Наряду с понятием конечного автомата рассматриваются различные его обобщения и модификации, отражающие те или иные особенности реальных устройств. Для конечного автомата (A, S, B, j, f) существующие модификации можно разбить на следующие три основные группы.
К первой группе относятся автоматы, у которых некоторые из алфавитов A (входной), S (состояний) или B (выходной) бесконечны, в связи с чем такие автоматы называются бесконечными. Ко второй группе относятся автоматы, у которых вместо выходной и переходной функций j и f допускаются произвольные отношения или случайные функции. Таковы частичные, недетерминированные, вероятностные и другие автоматы. К третьей группе относятся автоматы со специфическими множествами входных объектов.
Таковы, например, автоматы с переменной структурой. Существуют автоматы, принадлежащие одновременно разным группам. Наряду с этим большую роль играют специальные подклассы конечных автоматов, например, автоматы без памяти. Кроме того, использование понятий и методов из других разделов математики также приводит к появлению специфических классов автоматов и связанных с ними задач.
Например, при применении алгебраических средств возникают понятия автоматов: линейного, группового, свободного и других автоматов; вопросы теории кодирования порождают понятия самонастраивающихся, обратимых автоматов и других.
Пример. Рассмотрим следующий конкретный конечный автомат M = [A, S, B, j, f]. Входной алфавит A = {0, 1}; выходной алфавит B = {0, 1}; три внутренних состояния S = {s0, s1, s2}; функции выхода и перехода задаются предписаниями:
| ф: | f: |
| (so, 0) a si | (so, 0) a 0 |
| (so, 1) a so | (so, 1) a 1 |
| (si, 0) a s2 | (si, 0) a 1 |
| (si, 1) a si | (s1, 1) a 0 |
| (s2, 0) a so | (s2, 0) a 1 |
| (s2, 1) a s2 | (s2, 1) a 0 |
работу в состоянии s2, имея на выходной ленте последовательность 0, 0, 1, О.Таким образом, автомат преобразовал вход 0, 1,0, 1 (или, короче, 0101) в 0, 0, 1, 0 (или 0010).
Есть два удобных способа описать этот автомат. Прежде всего можно построить диаграмму состояния автомата - описание конечного автомата с помощью помеченного ориентированного графа (рис.
2.3) - орграфа.
Вершины этого орграфа помечены символами, обозначающими внутренние состояния. Каждая дуга помечена парой символов a, b, где a - входной символ, вызывающий переход в следующее состояние, отвечающее этому ребру, а b - выходной символ, который автомат выпечатывает. таблица состояний и табличное представление функций j и f (табл. 1):
| Таблица 1 | ||||||||||||||||||||||||||||||||||
|
это раздел теории управляющих систем, изучающий математические модели преобразователей дискретной информации, называемых автоматами. С определенной точки зрения такими преобразователями являются как реальные устройства (вычислительные машины, автоматы, живые организмы и т.д.), так и абстрактные системы (например, формальная система, аксиоматические теории и т.д.). Наиболее тесно теория автоматов связана с теорией алгоритмов.
Большинство задач теории автоматов - общие для основных видов управляющих систем. К ним относятся задачи анализа и синтеза автоматов, задачи полноты, минимизации, эквивалентных преобразований автоматов и другие. Задача анализа состоит в том, чтобы по заданному автомату описать его поведение или по неполным данным об автомате и его функционированию установить те или иные его свойства. Задача синтеза автоматов состоит в построении автомата с наперед заданным поведением или функционированием. Задача полноты состоит в выяснении, обладает ли подмножество МФавтоматов свойством полноты, т.е. совпадает ли с М множество всех автоматов, которые получаются путем конечного числа применений некоторых операций к автоматам из заданного подмножества автоматов МФ Задача эквивалентных преобразований в общем виде состоит в том, чтобы найти систему правил преобразований (так называемую полную систему правил) автоматов, которые удовлетворяют опреде-
ленным условиям и позволяют преобразовать произвольный автомат в любой эквивалентный ему автомат (два автомата эквивалентны, если они имеют одинаковое поведение автомата. Поведение автомата - математическое понятие, описывающее взаимодействие автомата с внешней средой. Примером внешней среды конечного автомата является множество входных слов, а поведением - словарная функция, реализуемая автоматом, или событие, представимое автоматом).
Помимо перечисленных, в теории автоматов имеются специфические проблемы, характерные для автоматов. Так, в зависимости от условий задачи поведение автомата удобно задавать на разных языках, в связи с чем важными являются выбор достаточно удобного адекватного языка и перевод с одного языка на другой. В тесной связи с задачами синтеза и эквивалентных преобразований находится задача минимизации числа состояний автомата, а также получение соответствующих оценок. Близкий круг вопросов возникает в связи с моделированием поведения автоматов одного класса с автоматами другого класса. Здесь также представляют интерес вопросы минимизации моделирующих автоматов и оценки их сложности. Специальный раздел теории автоматов связан с так называемыми экспериментами с автоматами (т.е. способами получения информации о внутренней структуре автоматов по их поведению). Основная задача здесь состоит в том, чтобы получить определенные сведения о строении автомата путем наблюдения за его реакцией на те или иные внешние воздействия. При этом возникает большой круг задач, связанный с классификацией экспериментов и с вопросами разрешимости задач определенными видами экспериментов, а также с оценками длин минимальных экспериментов, достаточных для решения тех или иных задач. Понятие эксперимента с автоматами используется также в задачах надежности управляющих систем и их контроля, в частности автоматов.
Модель надежности на основе конечных автоматов - модель работоспособных состояний объекта, основанная на описании и (или) диаграмме состояния конечного автомата. Многие из перечисленных выше задач могут рассматриваться как алгоритмические проблемы. Для конечных автоматов большинство из них имеют положительное решение.
Имитационное моделирование надежности
На протяжении XX в. в СССР и России при разработке проблем теоретико-интерпретационного плана формировалось все более ясное и четкое понимание роли и значения имитационного моделирования - как при оценке эффективности существующих и предлагаемых новых методов решения задач, возникающих в рамках интерпретационного процесса, так и при оценке
надежности и точности решений задач, получаемых на практике по конкретным данным; вместе с тем следует признать, что имитационное моделирование все еще используется в недостаточном объеме. Этот вывод легко получить из анализа специальной литературы; он имеет важное ориентирующее значение.
Имитационная модель надежности - модель, отображающая состояния и функционирование объекта, в которой переменные, принятые в качестве характеристик исследуемого объекта, характеризуют свойства, составляющие надежность объекта.
В тех случаях, когда решаемые задачи допускают строгую математическую формулировку, задачи имитационного моделирования всегда оказываются некорректно поставленными, т.е. фактически требующими использования не только строгих математических методов, но также и использования дополнительных процедур эвристического характера (типа процедур распознавания образов).
Построение интерпретационных моделей всегда осуществляется по двум линиям:
а) сбора имеющихся данных, относящихся ко всем элементам интерпретационной модели, прежде всего о строении изучаемого объекта, а также к характеристикам, определяющим его работоспособность, и связанных с ними априорных ограничений;
б) проведения специальных расчетов (решения вспомогательных задач), позволяющих внутренними средствами уточнить модельные представления об объекте, характеристиках и связях между характеристиками и объектом.
Как правило, на этапе построения интерпретационных моделей основное значение имеют задачи нахождения (явных) аппроксимаций изучаемых свойств и специальные обработки построенных аппроксимаций (чаще всего, хотя и не обязательно, линейных). Что касается этапа собственно нахождения интерпретаций в рамках принятых интерпретационных моделей, то здесь основное значение имеют процедуры аппроксимационной оптимизации (параметров изучаемого объекта по экспериментальным данным о характеристиках); при этом с очевидностью должны использоваться регулярные (регуляризующие) алгоритмы.
После нахождения интерпретации по необходимости используются процедуры - обычно эвристические, типа распознавания образов, а также (но далеко не всегда!) имитационное моделирование в целях нахождения оценок точности и надежности построенной интерпретации.
НАДЕЖНОСТЬ АВТОМАТИЗИРОВАННЫХ ИНФОРМАЦИОННЫХ СИСТЕМ
Комплексные показатели надежности АИС.
Надежность компонентов АИС и технических средств
Комплексные показатели надежности АИС - показатели, которые обеспечивают достижение основных целей функционирования АИС, определенных в нормативно-технической и (или) проектной документации. Комплексные показатели надежности АИС разрабатываются на этапе формирования технического задания.
Коэффициент готовности АИС - вероятность того, что АИС и все ее компоненты окажутся в работоспособном состоянии в произвольный момент времени, кроме планируемых периодов, в течение которых применение АИС или отдельных компонентов по назначению не предусматривается.
Повышение готовности АИС предполагает подавление в определенных пределах влияния отказов и сбоев на работу системы с помощью средств контроля и коррекции ошибок, а также средств автоматического восстановления вычислительного процесса после проявления неисправности, включая аппаратурную и программную избыточность, на основе которой реализуются различные варианты отказоустойчивых архитектур. Повышение готовности - есть способ борьбы за снижение времени простоя системы.
Единицей измерения здесь является коэффициент готовности, который определяет вероятность пребывания системы в работоспособном состоянии в любой произвольный момент времени. Статистически коэффициент готовности определяется как MTBF/(MTBF+MTTR), где MTTR (Mean Time To Repair) - среднее время восстановления (ремонта), т.е. среднее время между моментом обнаружения неисправности и моментом возврата системы к полноценному функционированию.
В последние годы в литературе по вычислительной технике все чаще употребляются термины "системы высокой готовности", "системы высокой степени готовности", "системы с высоким коэффициентом готовности". Все эти термины по существу являются синонимами, однако как и многие термины в области вычислительной техники, термин "высокая готовность" понимается по-разному отдельными поставщиками и потребителями вычислительных систем. Совершенно аналогично некоторые слова, связанные с термином "высокая готовность", такие, например, как "кластеризация", также употребляются в различных значениях.
Важно иметь стандартный набор определений для того, чтобы предложения различных поставщиков можно было сравнивать между собой на основе одинаковых терминов.
Ниже приведены общепринятые в настоящее время определения, которые мы будем использовать для различных типов систем, свойством которых является та или иная форма снижения планового и непланового времени простоя:
- Высокая готовность (High Availability). Настоящие конструкции с высоким коэффициентом готовности для минимизации планового и непланового времени простоя используют обычную компьютерную технологию. При этом конфигурация системы обеспечивает ее быстрое восстановление после обнаружения неисправности, для чего в ряде мест используются избыточные аппаратные и программные средства.
Длительность задержки, в течение которой программа, отдельный компонент или система простаивает, может находиться в диапазоне от нескольких секунд до нескольких часов, но более часто в диапазоне от 2 до 20 мин. Обычно системы высокой готовности хорошо масштабируются, предлагая пользователям большую гибкость, чем другие типы избыточности.
- Эластичность к отказам (Fault Resiliency). Ряд поставщиков компьютерного оборудования делит весь диапазон систем высокой готовности на две части, при этом в верхней его части оказываются системы эластичные к отказам.
Ключевым моментом в определении эластичности к отказам является более короткое время восстановления, которое позволяет системе быстро откатиться назад после обнаружения неисправности.
- Устойчивость к отказам (Fault Tolerance). Отказоустойчивые системы имеют в своем составе избыточную аппаратуру для всех функциональных блоков, включая процессоры, источники питания, подсистемы ввода/вывода и подсистемы дисковой памяти. Если соответствующий функциональный блок неправильно функционирует, всегда имеется горячий резерв.
В наиболее продвинутых отказоустойчивых системах избыточные аппаратные средства можно использовать для распараллеливания обычных работ. Время восстановления после обнаружения неисправности для переключения отказавших компонентов на избыточные для таких систем обычно меньше одной секунды.
- Непрерывная готовность (Continuous Availability). Вершиной линии отказоустойчивых систем являются системы, обеспечивающие непрерывную готовность.
Продукт с непрерывной готовностью, если он работает корректно, устраняет любое время простоя (как плановое, так и неплановое). Разработка такой системы охватывает как аппаратные средства, так и программное обеспечение и позволяет проводить модернизацию (upgrade) и обслуживание в режиме on-line.
Дополнительным требованием к таким системам является отсутствие деградации в случае отказа. Время восстановления после отказа не превышает одной секунды.
- Устойчивость к стихийным бедствиям (Disaster Tolerance). Широ-
кий ряд продуктов и услуг связан с обеспечением устойчивости к стихийным бедствиям. Иногда устойчивость к стихийным бедствиям рассматривается в контексте систем высокой готовности.
Смысл этого термина в действительности означает возможность рестарта или продолжения операций на другой площадке, если основное месторасположение системы оказывается в нерабочем состоянии из-за наводнения, пожара или землетрясения. В простейшем случае продукты, устойчивые к стихийным бедствиям, могут просто представлять собой резервные компьютеры, расположенные вне основного местоположения системы, сконфигурированные по спецификациям пользователя и доступные для использования в случае стихийного бедствия на основной площадке.
В более сложных случаях устойчивость к стихийным бедствиям может означать полное (зеркальное) дублирование системы вне основного местоположения, позволяющее принять на себя работу немедленно после отказа системы на основной площадке.
Все упомянутые типы систем высокой готовности имеют общую цель - минимизацию времени простоя. Имеются два типа времени простоя компьютера: плановое и неплановое. Минимизация каждого из них требует различной стратегии и технологии.
Плановое время простоя обычно включает время, принятое руководством, для проведения работ по модернизации системы и для ее обслуживания. Неплановое время простоя является результатом отказа системы или компонента.
Хотя системы высокой готовности возможно больше ассоциируются с минимизацией неплановых простоев, они оказываются также полезными для уменьшения планового времени простоя.
Современные АИС строятся или, скорее, будут строиться из компонентов. (Компонент - самостоятельный программный или аппаратный продукт, поддерживающий объектную парадигму, реализующий отдельную область логики и умеющий взаимодействовать с другими компонентами с помощью открытых интерфейсов.) Такая технология позволит ответить на самые острые проблемы компьютерного мира - сокращение времени разработки автоматизированной системы, облегчение процесса внедрения и поддержка гибкости внедренного решения. На рис.
3.1 изображены этапы жизненного цикла АИС.
требования к надежности автоматизированных систем, описываемые в техническом задании на систему, включают в себя:
1) состав и количественные значения показателей надежности для системы в целом или ее подсистем;
2) перечень аварийных ситуаций, по которым должны быть регламентированы требования к надежности, и значения соответствующих показателей;
3) требования к надежности технических средств и программного обеспечения;
4) требования к методам оценки показателей надежности и их контролю на разных стадиях создания системы в соответствии с действующими нормативно-техническими документами.
Перечисленные требования позволяют обеспечить необходимый (заложенный при проектировании) для АИС в целом уровень надежности.
Методы надежности программного обеспечения
Надежность сложных программных средств определяется теми же факторами, что и надежность любых технических объектов, однако доминирующими являются дефекты и ошибки проектирования, так как физическое хранение программ на магнитных носителях характеризуется очень высокой надежностью. Программа любой сложности и назначения при строго фиксированных исходных данных и абсолютно надежной аппаратуре исполняется по однозначно определенному маршруту и дает на выходе строго определенный результат. Однако случайное изменение исходных данных и накопленной при обработке информации, а также множество условных переходов в программе создают огромное число различных маршрутов исполнения каждого сложного ПС. Источниками ненадежности являются непроверенные сочетания исходных данных, при которых функционирующее ПС дает неверные результаты или отказы. В результате комплекс программ не соответствует требованиям функциональной пригодности и работоспособности.При применении понятий надежности к программным средствам следует учитывать особенности и отличия этих объектов от традиционных технических систем, для которых первоначально разрабатывалась теория на-
дежности:
- не для всех видов программ применимы понятия и методы теории надежности - их можно использовать только к программным средствам, функционирующим в реальном времени и непосредственно взаимодействующим с внешней средой;
- при разработке и оценке качества программных компонентов к ним не применимы понятия надежности функционирования, если при обработке информации они не используют значения реального времени и не взаимодействуют непосредственно с внешней средой;
- доминирующими факторами, определяющими надежность программ, является количество дефектов и ошибок проектирования и разработки; второстепенное значение имеет физическое разрушение программных компонентов при внешних воздействиях;
- относительно редкое разрушение программных компонентов и необходимость их физической замены приводят к принципиальному изменению понятий сбоя и отказа программ и к разделению их по длительности восстановления относительно некоторого допустимого времени простоя для функционирования информационной системы;
- для повышения надежности комплексов программ особое значение имеют методы автоматического сокращения длительности восстановления и преобразования отказов в кратковременные сбои путем введения в программные средства временной, программной и информационной избыточности;
- непредсказуемость места, времени и вероятности проявления дефектов и ошибок, а также их редкое обнаружение при реальной эксплуатации достаточно надежных программных средств не позволяют эффективно использовать традиционные методы априорного расчета показателей надежности сложных систем, ориентированные на стабильные, измеряемые значения надежности составляющих компонентов;
- традиционные методы форсированных испытаний надежности систем путем физического воздействия на их компоненты не применимы для программных средств и их следует заменять на методы форсированного воздействия информационных потоков внешней среды.
С учетом перечисленных особенностей применение основных понятий теории надежности сложных систем к жизненному циклу и оценке качества комплексов программ позволяет адаптировать и развивать эту теорию в особом направлении - надежности программных средств. Предметом изучения теории надежности комплексов программ (Software Reliability) является работоспособность сложных программ обработки информации в реальном времени. К задачам теории и анализа надежности сложных программных средств можно отнести следующие:
- формулирование основных понятий, используемых при исследовании и применении показателей надежности программных средств;
- выявление и исследование основных факторов, определяющих характеристики надежности сложных программных комплексов;
- выбор и обоснование критериев надежности для комплексов программ различного типа и назначения;
