Надежность комплексов программ

 

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

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

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

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

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

 

Критерии надежности

 

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

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

Вероятностью отказа Q (t) = 1 - P (t) является вероятность того, что в течение заданного времени произойдет хотя бы один отказ.

Интегральным критерием является интенсивность отказов (t), которая характеризует плотность распределения наработки до первого отказа, рассчитанную при условии, что до рассмотренного момента времени система проработала безотказно:

 

                             (t) =  , t  0.

 

Для оценки надежности восстанавливаемых систем используют характеристики: H(t) - среднее количество отказов за время t; Т (t) - наработка на отказ

                                   Т (t) = .

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

 

Сбой, отказ, восстановление

 

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

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

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

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

Для решения задачи восстановления в комплексе программ должны быть средства, позволяющие:

 

· проводить систематический контроль и оперативно обнаруживать аномалии процесса функционирования или состояния программ и данных;

· диагностировать обнаруженные искажения;

· вырабатывать решения и выбирать методы и средства восстановления;

· реализовывать оперативное восстановление нормальной работоспособности;

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

 

Таблица 2.3.

Факторы, определяющие надежность программ	Методы проектирования корректных программ	Методы контроля
Особенности внешних абонентов и пользователей:   · требования к показателям надежности; · инерционность внешних абонентов; · необходимое время отклика на входные данные.   Искажения исходных данных: · искажения данных, поступающих от человека; · искажение данных, поступающих по телекодовым каналам связи; · искажение данных в процессе накопления и хранения в ЭВМ.   Ошибки в программах и их проявление:   · статистические характеристики ошибок и искажений: · программ; · массивов данных; · вычислительного процесса.	Структурное проектирование программ и данных:   · структурное проектирование программных модулей; · структурное проектирование взаимодействия модулей; · структурирование данных   Тестирование программ:   · детерминированное тестирование; · статистическое тестирование; · динамическое тестирование и контроль пропускной способности в реальном времени.	Методы использования  избыточности: · временной; · информационной; · программной.   Методы контроля программ, данных и вычислительного процесса: · предпусковой контроль; · оперативный контроль. Методы программного восстановления: · восстановление текстов программ; · исправление данных; · корректировка вычислительного процесса. Методы испытаний на  надежность: · испытания в нормальных условиях эксплуатации; · форсированные испытания; · расчетно-экспериментальные методы определения надежности. Методы обеспечения надежности при сопровождении: · обеспечение сохранности программ эталонных версий; · обеспечение корректности внесения изменений и развитии версий.

Алгоритмы сортировки

Введение

 

Почти во всех машинных приложениях множество объектов должно быть размещено в соответствии с некоторым заранее определенным порядком. Например, расположить данные по алфавиту или по возрастанию номеров.

Пусть имена x ₁, …, x_n заданы в виде таблицы. Каждое имя x_i принимает значение из пространства имен, на котором определен линейный порядок. Далее мы считаем, что никакие 2 имени не имеют одинаковых значений, т.е. любые x_i, x_j обладают тем свойством, что если i ¹ j, то либо x_i предшествует x_j, либо наоборот [3].

Ограничение x_i ¹ x_j при i ¹ j упрощает анализ без потери общности, т.е. корректность идей и алгоритмов не нарушается. Цель сортировки состоит в том, чтобы выполнить перестановку , для которой .

В задачах частичной сортировки требуется извлечь либо частичную информацию о П (например, p_i для нескольких значений i), либо полностью определить П по заданной частичной информации о ней (так обстоит дело при слиянии двух упорядоченных таблиц).С каждой записью x_i в последовательности x ₁, …, x_n сопоставим некоторый ключ ‘ k ’. Ключом обычно является некоторое поле внутри записи. Говорят, что файл отсортирован по ключу, если для i < j следует, что k_i предшествует k_j при некоторой упорядоченной последовательности по ключам. В качестве примера рассмотрим телефонный справочник. Файл состоит из всех строчек этого справочника. Каждая строчка является записью. Ключом, по которому отсортирован этот файл, является поле фамилия в записи. Каждая запись содержит также поле для адреса и номера телефона.

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

Вполне возможно, что две записи в некотором файле имеют одинаковый ключ. Метод сортировки называется устойчивым, если для всех записей i и j таких, что k (i) = k (j), выполняется условие, что в отсортированном файле x_i предшествует x_j, если x_i предшествует x_j в первоначальном файле.

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

 

Пример.

а) первоначальный файл               б) отсортированный файл

 

ключ	информация		ключ	информация
4	DDD		1	AAA
2	BBB		2	BBB
1	AAA		3	CCC
5	EEE		4	DDD
3	CCC		5	EEE

                                                              

Рис. 3.1. Сортировка записей

 

 

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

 

Рис. 3.2. Сортировка, использующая вспомогательную таблицу указателей

 

 таблица указателей, так что вместо перемещения самих данных перемещаются эти указатели. Это называется сортировкой таблицы адресов.

 

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

 

Внутренняя сортировка

 

Существует, по крайней мере, пять широко известных способов, применяемых в алгоритмах внутренней сортировки.

1. Вставка. На i -м этапе i -е имя помещается на надлежащее место c i -1 уже отсортированными именами.

2. Обмен. Два имени, расположение которых не соответствует порядку, меняются местами (обмен). Эта процедура повторяется, пока существуют такие пары.

3. Выбор. На i -м этапе из неотсортированных имен выбирается i -е наибольшее (наименьшее) имя и помещается на соответствующее место.

4. Распределение. Имена распределяются по группам, и содержимое групп затем объединяется таким образом, чтобы частично отсортировать таблицу; процесс повторяется до тех пор, пока таблица не будет отсортирована полностью.

5. Слияние. Таблица делится на подтаблицы, которые сортируются по отдельности и затем сливаются в одну.

Эти классы нельзя назвать ни взаимоисключающими, ни исчерпывающими. Они

удобны для классификации алгоритмов сортировки. В рассматриваемых алгоритмах имена образуют последовательность x ₁, …, x_n. Значением x_i является любое текущее имя i позиции последовательности. В каждом из рассматриваемых алгоритмов будем считать, что имена нужно сортировать на месте, т.е. перемещение имен должно происходить внутри последовательности x ₁, …, x_n. При этом существует одна или две дополнительные ячейки, в которых временно размещается значение имени.

Ограничение «сортировка на месте» основано на предположении, что число имен настолько велико, что во время сортировки не допускается перенос их в другую область памяти.

 

3.3. Сравнение эффективности алгоритмов сортировки

Чтобы получить некоторое представление об ожидаемой эффективности, рассмотрим задачу сортировки с теоретической точки зрения.

Один из способов оценки эффективности алгоритмов сортировки состоит в подсчете числа сравнений имен ‘ x_i: x_j ’ за время сортировки. Эта характеристика не всегда является определяющей, но для большинства алгоритмов она является хорошей мерой производимой работы. Будем рассматривать алгоритмы, основанные на абстрактном линейном упорядочении пространства имен: для любой пары имен x_i, x_j при i ¹ j либо x_i < x_j, либо x_i > x_j.

Любой такой алгоритм можно представить в виде расширенного бинарного дерева решений, в котором каждый внутренний узел соответствует сравнению имен, и каждый лист (внешний узел) — исходу алгоритма. Это дерево можно рассматривать как блок-схему алгоритма сортировки, в котором все циклы «размотаны» и показаны только сравнения имен.

Пример. Рассмотрим сортировку элементов массива { x ₁, x ₂, x ₃ } с использованием бинарного дерева.

Рис. 3.3. Бинарное дерево решений для сортировки трех имен

В любом таком дереве решений каждая перестановка определяет единственный путь от корня к листу. Листья, соответствующие разным перестановкам, должны быть разными. Тогда ясно, что в дереве решений для сортировки n имен должно быть по крайней мере n! листьев (n! — количество перестановок из n).

Заметим, что высота дерева решений h равна числу сравнений, требующихся алгоритму в наихудшем случае.

Поскольку бинарное дерево высоты h может иметь не больше 2 ^h листьев, заключаем что

  т.к.

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

Длина внешних путей дерева решений равна сумме всех расстояний от корня до листьев, деление ее на n! дает среднее число сравнений для соответствующего алгоритма.