Повышение эффективности функционирования вычислительных систем на основе аналитических методов оценки влияния сбоев программного обеспечения

Ключников, Константин Константинович

Системный анализ, управление и обработка информации (по отраслям)

автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Повышение эффективности функционирования вычислительных систем на основе аналитических методов оценки влияния сбоев программного обеспечения

кандидата физико-математических наук: Ключников, Константин Константинович
город: Москва
год: 2011
специальность ВАК РФ: 05.13.01

Диссертация по информатике, вычислительной технике и управлению на тему «Повышение эффективности функционирования вычислительных систем на основе аналитических методов оценки влияния сбоев программного обеспечения»

Автореферат диссертации по теме "Повышение эффективности функционирования вычислительных систем на основе аналитических методов оценки влияния сбоев программного обеспечения"

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ имени В. А. ТРАПЕЗН7

УДК 519.873

484110'

Ключников Константин Константинович

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ НА ОСНОВЕ АНАЛИТИЧЕСКИХ МЕТОДОВ ОЦЕНКИ ВЛИЯНИЯ СБОЕВ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

Специальность 05.13.01. - „Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)"

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2011

2 А (.".'.р 2011

4841157

Работа выполнена в Учреждении Российской Академии Наук Институте проблем управления имени В. А. Трапезникова РАН

Научный руководитель: доктор технических'наук,

профессор Волик Борис Григорьевич.

Официальные оппоненты: доктор физико-математических наук, зав. лабораторией N'21 ИПУ имени В.А. Трапезникова, профессор Добровидов Александр Викторович;

кандидат физико-математических наук, руководитель отдела консалтинга "InterSystems International Corporation" Грачёв Андрей Юрьевич

Ведущая организация: Федеральное Государственное Унитарное Предприятие Научно - Исследовательский Институт "Субмикрон".

Защита состоится 28 марта 2011 года в 14® часов на заседании Диссертационного совета N«2 (Д002.226.02) при Учреждении Российской Академии наук Институте проблем управления имени В. А. Трапезникова РАН по адресу: 117997, Москва, ул. Профсоюзная, д. 65. Телефон Сонета: (495) 334-93-29

Автореферат разослан 26 февраля 2011 г.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской Академии наук Института проблем управления имени В. А. Трапезникова РАН.

Ученый секретарь Диссертационного совета Д002.226.02 кандидат технических наук

В. Н. Лебедев.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Большинство вычислительных систем, используемых для технических, инженерных, коммерческих, научных целей, имеют сложную архитектуру. Множество компонентов и их взаимодействие зачастую приводит к тому, что ошибка, возникающая в работе одной из компонент, приводит к сбою1 всей системы. В исследованиях надежности вычислительных систем 80-х годов прошлого века говорится о том, что более 60% сбоев происходит но причине неполадок в оборудовании. Однако, уже в середине 90-х годов исследователи снизили эту долю до 10% и основное их внимание сфокусировалось на программном обеспечении (всюду далее ПО), ошибки в котором являлись причинами сбоев как минимум в 70% случаев.

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

Кроме детерминированных сбоев, в ПО также бывают сбои, чьё возникновение носит случайный характер. Более того, в большинстве случаев, если даже воспроизвести условия (входные данные, параметры настройки программы), при которых произошел этот сбой, то во второй раз его может не произойти. В западной литературе класс ошибок в ПО, по причине которых происходят случайные сбои получил название МзепЫщв3. Причиной возникновения случайных сбоев в ПО является определенный характер его взаимодействия с другими компонентами вычислительной системы: операционной системой, оборудованием, другими программами. В некоторых случаях взаимодействие ПО с перечисленными компонентами имеет случайный характер. Ниже приведены примеры ситуаций, в ко-

1 Согласно ГОСТ 27.002-89, характерным примером сбоя служит остановка ЭВМ, устраняемая повторным пуском программы с места останова или ее перезапуском сначала.

2В честь создателя первой квантовой теории атома Ннльса Бора.

3В честь В. Гейзенберга, автора принципа неопределенности квантовой механики. В некоторых работах их именуют ..Магн1е1Ьи^", в честь исследователя фракталов Б. Мандельброта.

торых могут возникать случайные сбои4.

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

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

Локализация ошибок „ЬЫвепЬ^в" усугубляется и тем, что сбои, произошедшие по их причине, случаются по истечении длительного времени. Обычно, если исполняется фрагмент программы, содержащий ошибку класса „Не!зепЬ1^8", то система ведет себя некоторым образом, отличным от того, что декларирован инструкцией и пользователь может этого не замечать. Дальнейшее исполнение программы может также перейти на фрагменты кода, содержащие ошибки, и в результате вызвать сбой. Такая функциональная цепочка от исполнения первого фрагмента программы, содержащего ошибку, до сбоя носит название распространение ошибки.

В диссертации рассматриваются следующие методы, нацеленные на снижение влияния сбоев программного обеспечения на работу вычислительных систем:

• метод перезапуска;

• метод контрольных точек.

4Одним из способов обнаружения случайных сбоев является периодический мониторинг состояния исполняемой программы.

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

Цель работы состоит в исследовании и оптимизации критериев оценки эффективности методов снижения влияния сбоев программного обеспечения на работу вычислительных систем. Основные задачи работы:

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

• найти оптимальное количество контрольных точек;

« оценить верхний к нижний интервалы времени работы программы с контрольными точками;

• формализовать задачу поиска оптимального интервала между последовательными перезапусками веб-сервера, при котором увеличивается его готовность;

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

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

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

2. Исследовано асимптотическое поведение величины среднего времени работы программы. Найдено соотношение между параметрами модели, при выполнении которого величина среднего времени работы программы имеет конечный предел.

3. В рамках построенной математической модели оценки среднего времени работы программы найдена функция вероятностного распределения случайной величины времени работы программы и исследованы ее свойства. Также получена двухсторонняя оценка квантили найденного распределения.

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

Практическая и теоретическая ценность заключается в том, что реализация результатов, полученных в диссертационной работе, позволяет достигнуть технико-экономический эффект от внедрения методов снижения влияния сбоев программного обеспечения на работу вычислительных систем. Апробация работы и публикации. Результаты диссертации опубликованы в 6 печатных работах, пять из которых - в рецензируемых журналах, входящих в список ВАК. Основные результаты диссертации докладывались на III Международной конференции «Информационные системы и технологии» (ноябрь 2006 г., Минск).

Связи исследований с научными программами. Исследования по теме диссертации проводились в соответствии с проектом ИПУ РАН «Теоретические основы и технологии реализации высоконадежных информационно-управляющих систем и повышения реакционной способности для автономных систем управления», входящим в направление №5 «Методы моделирования, анализа и синтеза высоконадежных, отказоустойчивых информационно-управляющих систем движущихся объектов» программы фундаментальных исследований Отделения ЭММиПУ РАН №15 «Управление движением, теория сложных информационно-управляющих систем (2009-2012 гг.)», а также проектом ИПУ РАН «Теория и методы прогнозирования работоспособности сложных управляющих технических систем», входящим в направление №2 «Разработка методов анализа надежности и эффективности систем сложной структуры» программы фундаментальных исследований Отделения ЭММиПУ РАН №15 «Управление движением, теория слож-

пых информационно-управляющих систем (2005-2008 гг.)». Структура диссертации. Диссертация состоит из введения, трех глав, состоящих в совокупности из 10 разделов, заключения, приложения и списка литературы. Полный объем диссертации - 105 страниц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, определены объект, цель и задачи исследования, научная новизна и практическая значимость работы, а также представлены основные положения, выносимые на защиту.

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

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

Рис. 1. Вычислительная система с многоуровневой архитектурой

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

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

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

• приложения интеллектуального анализа данных6;

6(англ. Data Mining) — выявление скрытых закономерностей или взаимосвязей между переменны-

• приложения инженерных расчетов, анализа и симуляции физических процессов.7

Следует отметить, что применение метода контрольных точек не всегда снижает время работы программы. Например, в случае когда запись контрольных точек происходит часто, а длительности времени записи и времени восстановления программы после сбоя велики, то время работы программы может и возрасти. В этой связи возникает необходимость разработки критериев оценки эффективности метода контрольных точек и их оптимизации. В диссертации формируется математическая модель оценки времени работы программы с контрольными точками и разрабатываются критерии оценки эффективности метода контрольных точек. Данный подход к решению задачи оценки эффективности метода контрольных точек использовал профессор Дюкского университета К. S. Trivedi. В своих работах он исследовал задачу минимизации среднего времени работы программы в предположении, что интервалы времени между сбоями есть независимые случайные величины, распределенные по закону Вейбулла. Результат, полученный в его работе, состоял в численном решении задачи поиска оптимального интервала между контрольными точками. В работе X. Glien, М. R. Lyu также исследовались численные методы нахождения оптимального интервала между контрольными точками. В работе Y. Huang найдена верхняя оценка для оптимального интервала между контрольными точками.

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

Полагаем, что время работы программы в отсутсвии сбоев есть постоянная величина w. Если сбой случается в какой-либо точке Xq, то работа программы

ми в больших массивах необработанных данных. Наиболее распространенными приложениями являются SPSS, SAS, KXEN.

7САЕ (англ. Computer-aided engineering). Расчётная часть чаще всего основана на численных методах решения дифференциальных уравнений (метод конечных элементов, метод конечных объёмов, метод конечных разностей и др.). Примером такового приложения является открытая интегрируемая платформа для численного моделирования SALOME (http1.//-www.salome-platform-oig/).

начинается заново и время хц, в течении которого исполнялась программа, проходит безрезультатно. Повторный запуск программы осуществляется до тех пор, пока на временном интервале [0, ш] сбоя не произойдёт.

Пусть Х\ есть интервал времени от начала работы программы до первого сбоя, а Х2, А'з, • ■ • есть интервалы времени между сбоями. Предполагаем, что случайные величины Х1, Хо,...... независимые, распределенные экспоненциально8 с

параметром Л. Определим время работы программы Т следующим образом:

ги. если Х^ш) > и>

Т(ш) = < ^^ + 6СЛИ К Щ ~ У) (1)

Х1(и) + Хг(ш) + ю, если Х\(ы) < и>, < то, Хз(ш) > и)

Утверждение 1.2. Т{ш) есть случайная величина.9

Утверждение 1.3. Для математического ожидания случайной величины Т(ш) имеет место следующее выражение:

Е[Т\ = А(еАц,-1). (2)

Будем записывать состояние программы в одной из точек интервала (0^), которую назовем контрольной точкой. Тогда, если сбой произойдет позже момента записи состояния программы в контрольной точке, то возвращаться надо не в нулевую точку, а в контрольную.

Для начала предположим, что время возврата работы программы в контрольную точку равно нулю. Формально обозначим момент записи контрольной точки через аы (0 < а < 1), а время работы программы с одной контрольной точкой через Та{и>). Определим Та(и) следующим образом:

ад -

ги, если и; 6 С

И» + если Ш е Д,, П > 2 (3)

(1 - а) ш + ^¿М- если шбЛ„,п>2,

м Данное предположение означает, что величина количества сбоев в единицу времени постоянна. Модели, основанные на этом предположении, описаны в ГОСТ Р 51901.16-2005 „Менеджмент риска. Повышение надежности. Статистические критерии и методы оценки."

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

где

Вп = {а.' : АГ1 (и) < аи:, ■ • ■ . Хп] (ш) < аш, Л'„ (ы) > «)} , п > 2,

А, = {ы : аи < А'1(и) < ш. Х3(и) < (1 - а)ш, • • • , Л'„_1(ш) < (1 - а)и>, Хп(ы) > (1 - а)ш} и

и{ы : < аш, аш < Л'2(ы) < ш, Лз(ш) < (1 - о)ш. ■■• .^„-¡(ы) < (1 - о)и\ А'„(ш) > (1 - а)ш} и

■ ■ - и {и : А'^ш) < аи',Х>{и) < аи',-- - ,ЛГ„_2(ш) < ши.ате < Х„_1(ш) < то, Л'„(ш) > (1 - а)ш} ,п > 2.

Для величины Та(ш) справедливы следующие утверждения. Утверждение 1.5. Та(и) есть случайная величина.

Утверждение 1.6. Для математического ожидания случайной величины Та(и>) имеет место следующее выражение:

Е [Та] = 1 (еХаш - 1) + 1 (е^"«'" - 1) . (4)

Задача поиска момента записи контрольной точки, при котором величина среднего времени работы программы достигает минимума, решается в следующей теореме. Теорема 1.

1. Математическое ожидание случайной величины Та(и) достигает минимума в точке а = 2/

2. Е [Та] <Е\Т] при 0 < а < 1.

Таким образом, из Теоремы 1 следует, что оптимальная контрольная точка это середина временного отрезка работы программы. Подобные задачи оптимизации также рассматривались и в других областях применения. Например, в статье А. Бойкая рассматривалась проблема минимизации времени работы источника энергии при передаче потребителю заданного количестве энергии.

Далее в диссертации рассматривается модель программы с N контрольными точками, в которой время восстановления программы в контрольной точке после сбоя есть постоянная величина с1, а время восстановление программы в начальной точке после Сбоя есть постоянная величина с. Обозначим интервал времени между началом работы программы и первой контрольной точкой через и>1, а интервал времени между контрольными точками с номерами г — 1 и г, г > 2 через ги;. Случайную величину времени работы программы обозначим через Т^.

Утверждение 1.8. Для математического ожидания случайной величины Ту* (ш) справедливо выражение

Е [П>] = ЕЙ11 (еА- - 1) + Е™ Л (еАш' - 1) + с (е^ - 1), (5)

¿^¡=1 ад = ш, Wi > 0.

Задача минимизации математического ожидания случайной величины Тд-^. решается в следующей теореме.

Теорема 2. Минимум функции Е переменных щ, - ■■ , №.\Ч1 пРи ограни-

чениях с = <1,щ> 0, = и> достигается при ш,- = ^, г = 1, • • ■ , N+1.

Если предположить, что время, потраченное на запись состояния программы в контрольных точках, есть некоторая функция а = зависящая от ко-

личества контрольных точек и времени работы программы в отсутствии сбоев, то выражение для математического ожидания случайной величины времени работы программы Тс^т при равномерном расположении контрольных точек имеет вид

+с (е^ - + М* (М и).

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

Случай, в котором время работы программы в отсутствии сбоев составляет хи =150 часов, сбои случаются в среднем каждые =125 часов, восстановление после сбоя длится с — й—2 часа, а продолжительность записи контрольной точки составляет а —2 часа представлен на Рис.2. Оптимальным для этого случая является N =6 контрольных точек, но при этом когда количество контрольных точек N >68, то время работы программы становится больше, чем в случае когда контрольные точки отсутствуют. В другом случае, представленном на Рис.3, время работы программы в отсутствии сбоев составляет ги =40 часов, сбои случаются в среднем каждые ^ =200 часов, восстановление после сбоя длится с = й =4 часа, а продолжительность записи контрольной точки составляет а =2 часа. Метод контрольных точек для данного случая оказывается неприменимым, так как при любом количестве контрольных точек время работы программы увеличивается.

10 19 28 37 46 55 &4 73 8 • Время работы С кокт. точками — — Время работы бе» кокт. точек

Рис. 2. Время работы программы Е [т^j. w—150, А—0.008, c — d =2, а =2.

■тя.

Время работы с копт. точками — - — Время работы Без коит. точек

Рис. 3. Время работы программы Е ^Гу^]. \у=40, А=0.005, с = й =4,

В следующей теореме рассмотрен предельный случай N оо. Теорема 3. Пусть функция а = а(Лг, и>) = -Хц, 0 < 6 < 1,

q =2.

тогда lim Е \ Т)

Лг-*оо

■N+l,w

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

Утверждение 1.9. Выражение для математического ожидания случайной величины IV (ш) имеет вид

E[W] = eXw" e'^dx. Jo

(7)

В следующем утверждении проводится сравнение величин (7) и (2). Утверждение 1.10. Справедливы следующие соотношения между математическими ожиданиями случайных величин Т(ш) и \>У(и) :

1. ЕЩ = Е[Т\приа=\;

2. ЕЩ > Е[Т) при а > 1,ги > 1,3. ЕЩ < Е[Т] при а < 1.ш > 1.

Обозначим случайную величину времени работы программы с контрольной точкой через И^Дш). Определение ее аналогично (3).

Утверждение 1.11. Выражение для математического ожидания случайной величины имеет вид

В диссертации проводится численный анализ величины (8). Оказывается, что при ю > 1, математическое ожидание случайной величины \¥а{ш) возрастает по параметру а.

Вторая глава диссертации посвящена исследованию вероятностного распределения времени работы программы. Рассматривается случайная величина времени работы программы вида:

Здесь, как и прежде, Х^Хъ, ■■■ есть случайные величины интервалов времени между сбоями, одинаково распределенные по экспоненциальному закону. Параметр с есть величина времени восстановления работы программы после сбоя, которое предполагается быть постоянным. При с = 0 справедливы следующие утверждения. Утверждение 2.1

1. Функция распределения случайной величины Т имеет вид

(8)

и1,

если Хх > и)

Т =

Х\ + с + и>, если Х\ < хи, Л*2 > №

Х\ + Х2 + 2с + и>, если Х\ < ш, Хо < V), Х3 > то

О)

если х > ги, если х < ю,

2. Для плотности случайной величины Т имеет место выражение

\е~Хт (1 - е-Ам) е->-л"(*-<«) + е~Лий(.т - и>), если х > хи,

Р(х) = , п

U, если х < w.

Здесь 5{х) - функция Дирака.

Далее рассматривается случай программы с N-контрольными точками. Контрольные точки делят отрезок [0, w] на N+1 равные части длины ^ каждая. Время работы программы на i-м отрезке времени (г = 1, ■ • • , TV-f-l) есть случайная величина Tî, имеющая распределение (10). Обозначим TN = ^¿lî1^- Справедливо следующее утверждение.

Утверждение 2.2 Пусть Х{, Л'0, ■ • • есть случайные величины интервалов времени между сбоями в работе программы на отрезке времени

_ ^Ж+Т'^Ж+г]' ^ = " ' Случайные величины Х[, Х^, ■ ■ ■ незави-

симы и одинаково распределены по экспоненциальному закону. Тогда случайные величины TN~l и 7V+i независимы.

На основе Утверждений 2.1, 2.2 получено Утверждение 2.3, в котором найдена функция вероятностного распределения случайной величины TN. Утверждение 2.3 Плотность распределения случайной величины ТЛ имеет вид

PN (х)

+е~л"'Л {x - w),

о,

если x > tu, если x <w.

а для функции распределения имеет место выражение

{ ^ Е1о - 1)Л+,_* + 1 - - «о) +

Рд-(х)=< есЛи X > Ш,

^ 0, если х < ш.

Здесь=

Далее рассматривается задача оценки квантили уровня р для распределения (11). Квантиль уровня р есть решение хр уравнения гр) = р. Справедливо следующее утверждение.

Утверждение 2.5 Пусть хр есть квантиль уровня р распределения Ек(х),

р > е Справедливы следующие оценки: + ^ + 1)\

где о =

На Рис.4,5 приведены диаграммы изменения величин верхней и нижней оценок квантили хр для некоторых значений параметра N. В случае N — 2 (Рис.4) интервал между верхней и нижней оценками небольшой и с ростом параметра р увеличивается незначительно. При N — 20 (Рис.5) интервал между оценками достаточно велик и возрастает с ростом р. Поэтому при больших значениях N интервальные оценки из Утверждения 2.5 оказываются достаточно грубыми.

1 - рл

1 - (

(12)

X 1 200 .......................................- -.......-........................................................^

900

/ /

300

» нижняяоивша -»»врхияяощим

Рис. 4. Оценки квантили хр. \у=100,А=0.025,К=2

Рис. 5. Оценки квантили хр. \у=100,А=0.025,М=20

При с ф 0, в силу сложности сформированной модели, получен результат только для функции распределения времени работы программы без контрольных точек (9). Данный результат представлен в следующем утверждении. Утверждение 2.6 Выражение для функции распределения случайной величины

Т (9) при с ф 0 имеет вид

F(I) = ^e + I» 1 ] , еглих>ь..

[ 0. если х < и1,

Результат, полученный в последнем утверждении, позволяет оценить влияние параметра с-времени восстановления работы программы после сбоя. На Рис.С представлена диаграмма функции распределения (13) для различных значений параметра с. Из представленной ниже диаграммы можно сделать вывод о влиянии параметра с на вероятностное распределение времени работы программы. Например, для значений «0.5» и «20» графики функции распределения плотно прилегают друг к другу, тогда как уже для значения «30», расхождение графиков достаточно велико.

Рис. G. Функция распределения F(x) при с ф О

В третьей главе исследуется проблема влияния сбоев на работу веб-сервера, и в качестве метода снижения влияния сбоев рассматривается перезапуск.

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

Анализ случайных сбоев в известном веб-сервере APACHE10 с открытым ис-

10По данным исследования компании Netcraft является самым распространенным веб-сервером в мире. В мае 2009 г. APACHE работал на 46% всех веб-серверов.

ходиым кодом был подробно проведен в работе S. Chandra и P.M. Chen. Большинство сбоев APACHE, перечисленных в данной работе, можно предотвратить перезапуском веб-сервера.

В течение совершения перезапуска веб-сервер недоступен пользователям, поэтому если совершать перезапуск часто, то это может привести к существенному увеличению времени простоя веб-сервера. В этой связи возникает задача выбора оптимального интервала времени между перезапусками веб-сервера. Один из подходов решения данной задачи состоит в построении математической модели, описывающей поведение веб-сервера и последующей разработке критериев оценки эффективности метода перезапуска. В работе T. Dohi был рассмотрен ценовой критерий оценки эффективности метода перезапуска. Решалась задача минимизации величины отношения суммарной стоимости простоя системы в течение интервала времени к величине этого интервала. Решение данной задачи оптимизации сводилось к анализу численных величин. S. Mercier и M. Roussignol исследовали вероятностные модели вычислительной системы с перезапуском. В их работе поведение системы описывалось некоторым случайным процессом с конечным числом состояний, а интервалы времени между наблюдениями за системой были независимыми случайными величинами с произвольным распределением. Доказывалось, что метод перезапуска повышает готовность системы.

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

Готовность A(t) есть вероятность события, состоящего в том, что вычислительная система выполнит требуемую задачу в момент времени tn.

Предполагаем, что с самого начала работы веб-сервер находится в некотором идеальном состоянии. Вероятность сбоев в этом состоянии равна пулю. Идеальное состояние обозначим через «О». Предполагаем, что пребывание веб-сервера в состоянии «О» не бесконечно и через некоторое время он переходит в состояние «Р», в котором вероятность сбоя уже отлична от нуля. Этот переход связан с на-

иПодход к построению математических моделей с данным критерием, описан в ГОСТ Р 51901.15-2005 ..Менеджмент риска. Применение марковских методов."

чалом распространения ошибок веб-сервера. Из состояния «Р» веб-ссрвер через некоторое время переходит в состояние «К», что соответствует сбою в его работе.

Данный процесс можно формализовать с помощью следующей математической модели. Пусть < 6 есть случайный процесс со значениями во множестве {О,Р, Предполагаем, что 6 есть марковская цепь, диаграмма которой представлена на Рис.7.

Рис. 7. Диаграмма изменения состояний веб-сервера без перезапуска

Пусть также процесс ЛГДо;) однородный по времени и обладает марковским свойством. Обозначим щ(Ь) = Р {Х^ы) = г), г 6 {О, Р, Р}. Тогда система дифференциальных уравнений Колмогорова имеет вид (14).

В силу эргодической теоремы Зтг* = ИттгЖг е {О,Р,Р}.

£-+оо

Таким образом, имеем следующую систему уравнения для предельных вероятностей:

—Г27Го + Т\7Гр = О

—Хпр + г27ГО = О

( ""ой = -Г2щЦ) + Г1ТГр^) | Я>(0 = -Аттр(^ + Г27Г0(«> я>(«) = -ПТТР(1) + Лтг р{1)

(14)

—г\т:р + Хтгр = О

Щ + ЖР + Яр — 1-Отсюда

Величина ттр есть предельная вероятность пребывания веб-сервера в состоянии сбоя. Величина готовности определяется как тгл = 1 — пр.

Тепер перейдем к построению математической модели, описывающей поведение веб-сервера с перезапуском. В отличие от предыдущей математической модели, здесь возможен переход из состояния «Р» в состояние «Я», соответствующее перезапуску. Диаграмма переходов представлена на Рис. 8.

' Г3

0 ©

Рис. 8. Диаграмма изменения состояний веб-сервера с перезапуском

Поскольку перезапуск останавливает работу веб-сервера, то во время пребывания в состоянии «И.» веб-сервер простаивает. Предполагаем, что длительность времени пребывания в состоянии сбоя больше длительности времени пребывания в состоянии перезапуска. В терминах построенной модели это предположение выражается в виде неравенства ^ >

Выражение для предельной вероятности сбоя веб-сервера имеет вид

. 1 Л4, . (16) П гг) г + _А + п + Л + т-4

П г3 г2

Величина готовности определяется как кГд:>иь = 1 — кгр3иг. Теорема 4.

1. Если г3 > гх + ^, то пвозрастает по параметру г4.

2. Если Г3 < 7"1 4- ^, то 1гт^их> убывает по параметру Г4.

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

ЗАКЛЮЧЕНИЕ

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

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

2. Для случая N равноудаленных контрольных точек найдена величина среднего времени работы программы. Для некоторых значений параметров модели найдено оптимальное количество контрольных точек. При АГ оо получено достаточное условие, при котором среднее время работы программы конечно.

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

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

Публикации по теме диссертации:

[1] К. К. Ключников. Минимизация времени исполнения программы в условиях случайных сбоев // Информационные системы и технологии (IST'2006).-Материалы III Междунар. конф. (Минск, 1-3 ноября 2006 г.), Секция «Компьютерная безопасность и надежность информационных систем.», материалы в 2 ч. 4.1. —Мн.: Акад. Упр. при Президенте Респ. Беларусь, 2006, стр. 92-97.

[2] К.К. Ключников. Время исполнения программы в присутствии случайных сбоев // Дискретная математика, Выпуск №4, 2007, стр. 150-157.

[3] К. К. Ключников. Минимизация времени исполнения программы // Информационные технологии моделирования и управления, №5(39) 2007, стр. 574578.

[4] К. К. Ключников. Старение процесса исполнения программного приложения // Открытое образование, №4, 2007, стр. 38-43.

[5] К. К. Ключников. Методы снижения влияния сбоев в работе биллинговой системы // Мобильные системы, №08 2007, стр. 46-48.

[6] К. К. Ключников. Асимптотическое поведение метода контрольных точек, минимизирующего среднее время исполнения программы // Системы управления и информационные технологии, №3.1(29) 2007, стр. 155-158.

[7] К. К. Ключников. Анализ вероятностного распределения случайной величины времени работы программы в присутствии случайных сбоев // Автоматика и телемеханика, №7, 2009, стр. 175-185.

Линым вкладом соискателя в работе [2] является нахождение величины среднего времени работы программы с одной контрольной точкой. В работах [3, 5, 6] найдена величина среднего времени работы программы с N контрольными точками и исследовано ее асимптотическое поведение при N —> со. Задача поиска оптимального количества контрольных точек рассмотрена в работе [6]. Решение задачи оптимального расположения N контрольных точек и исследование вероятностного распределения случайной величины времени работы программы приведено в работе [7]. Построение и исследование математической модели вычислительной системы с перезапуском содержится в работе [4].

Подписано в печать:

25.02.2011

Заказ № 5042 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Оглавление автор диссертации — кандидата физико-математических наук Ключников, Константин Константинович

Введение

1 Оценка времени работы программы с контрольными точками

1.1 Время работы программы при сбоях.

1.2 Метод контрольных точек.

1.3 Оптимальный выбор контрольной точки

1.4 Дополненная модель.

1.5 N контрольных точек.

1.6 Старение работы программы, моделируемое распределением Вейбулла.

2 Вероятностное распределение времени работы программы с контрольными точками

2.1 Модель с нулевым временем восстановления после сбоя

2.2 Модель с ненулевым временем восстановления после сбоя

3 Готовность веб-сервера с перезапуском

3.1 Величина готовности.

3.2 Оценка готовности веб-сервера.

3.2.1 Математическая модель оценки готовности веб-сервера без перезапуска.

3.2.2 Математическая модель оценки готовности веб-сервера с перезапуском.

3.2.3 Численные результаты.

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

Большинство вычислительных систем, используемых для технических, инженерных, коммерческих, научных целей, имеют сложную архитектуру. Множество компонентов и их взаимодействие зачастую приводит к тому, что ошибка, возникающая в работе одной из компонент, приводит к сбою1 всей системы. В исследованиях надежности вычислительных систем 80-х годов прошлого века говорится о том, что более 60% сбоев происходит по причине неполадок в оборудовании. Однако, уже в середине 90-х годов исследователи снизили эту долю до 10% и основное их внимание сфокусировалось на программном обеспечении, ошибки в котором являлись причинами сбоев как минимум в 70% случаев [8]. Обычной практикой предотвращения сбоев программного обеспечения (всюда далее ПО) является локализация ошибок в исходном коде ПО и их исправление. Разработчики прилагают огромные усилия к тестированию ПО, в ходе которого большинство ошибок локализуется и исправляется.

Тот класс ошибок в программе, которые приводят к сбоям в ее работе на заранее определенном наборе входных данных (который может быть априори неизвестным разработчику), в западной литературе получил название „ВоЬгЫ^в"2 [9]. Сбои, вызванные ошибками данного класса, имеют детерминированный характер возникновения. Детерминированность здесь означает то, что если на каком-то наборе входных данных произошел сбой ПО, то на этом же наборе он произойдет и в следующий раз. Для устранения ошибок данного класса разработчику в болыпин

2В честь создателя первой квантовой теории атома Нильса Бора. стве случаев достаточно лишь определить фрагменты программного кода, в котором содержатся эти ошибки.

Кроме детерминированных сбоев, в ПО также бывают сбои, чьё возникновение носит случайный характер. Более того, в большинстве случаев, если воспроизвести условия (входные данные, параметры настройки программы), при которых произошел этот сбой, то во второй раз его может не произойти. В западной литературе класс ошибок в ПО, по причине которых происходят случайные сбои получил название Не1зепЫ^83[10, 11]. Причиной возникновения случайных сбоев в ПО является определенный характер его взаимодействия с другими компонентами вычислительной системы: операционной системой, оборудованием, другими программами. В некоторых случаях взаимодействие ПО с перечисленными компонентами имеет случайный характер. Ниже приведены примеры ситуаций, в которых могут возникать случайные сбои4.

3В честь В. Гейзенберга, автора принципа неопределенности квантовой механики. В некоторых работах их именуют „Мапс1е1Ь1^з", в честь исследователя фракталов Б. Мандельброта.

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

Локализация ошибок „ЬМвепЫ^э" усугубляется и тем, что сбои, произошедшие по их причине, случаются по истечении длительного времени [10]. Обычно, если исполняется фрагмент программы, содержащий ошибку класса „Не18епЬ1^8", то система ведет себя некоторым образом, отличным от того, что декларировано инструкцией и пользователь может этого не замечать. Дальнейшее исполнение программы может также перейти на фрагменты кода, содержащие ошибки, и в результате вызвать сбой. Такая функциональная цепочка от исполнения первого фрагмента программы, содержащего ошибку, до сбоя носит название распространение ошибки [10].

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

Так как большинство ошибок исправляется на этапе тестирования

ПО, то разумно было бы предположить, что основное количество сбоев, выявленных на этапе эксплуатации ПО, имеют случайную природу. Тем не менее, в работах исследователей проблем надежности ПО данные о распределении количества сбоев на детерминированные и случайные различаются. Например, в работе [14] сказано, что случайный характер имеют 29% сбоев. В работе [13] был проведен анализ характера возникновения сбоев и их классификация и показано, что 9% всех сбоев ПО являются случайными.

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

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

Рис. 1. Вычислительная система с многоуровневой архитектурой

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

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

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

• метод перезапуска;

• метод контрольных точек.

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

Анализ случайных сбоев в известном HTTP-сервере APACHE6 с открытым исходным кодом был в подробности проведен в работе [13]. Предотвратить большинство случайных сбоев HTTP-сервера APACHE (см. Рис.2) можно перезапуском сервера или его подсистем. Другим распространенным ПО, рассмотренным в работе [13], является СУБД MySQL.7 В СУБД

6По данным исследования компании Netcraft является самым распространенным веб-сервером в мире. В мае 2009 г. APACHE работал на 46% всех веб-серверов.

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

Описание сбоя Исправление сбоя

Обращение к DNS-серверу возвращает ошибку. Перезапуск DNS-сервера.

Во время пиковой нагрузки на сервер подпроцессы APACHE. полностью запоняют таблицу родительского процесса Администратор должен остановить все подпроцессы APACHE.

Пользователь нажимает в интернет-браузере кнопку СТОП в период открытия веб-страницы. После перезапуска сервера данный сбой (вызванный ошибкой типа состояние гонки) не повторяется.

Подпроцессы APACHE полностью занимают все сетевые порты. Перезапуск APACHE.

Медленный ответ от DNS-сервера. Либо перезапуск DNS-сервера, либо устранение проблем в сети.

Медленное соединение с сетью. Перезапуск APACHE.

Рис. 2. Случайные сбои HTTP-сервера APACHE

MySQL отмечены два вида случайных сбоев, являющихся следствием состояния гонки.

Одним из решений, автоматизирующим процесс перезапуска вычислительной системы, является продукт компании IBM Director. Алгоритм его работы состоит в периодическом контроле параметров вычислительной системы, и если параметры выходят за область допустимых значений, то инициируется процесс перезапуска.

В отчете компании ЮС8 приведены данные о средних потерях, которые несет каждая коммерческая компания при сбоях ПО вычислительных систем. При сбое ПО системы, предоставляющей некоторый сервис клиентам, час ее простоя оценивается в среднем в 25 000$ потерянной прибыли, а в год каждая компания в среднем несет потерю прибыли в 650 000$. В том же отчете говорится, что при внедрении продукта IBM Director доступность систем в среднем повышается на 25%, что приносит 162 500$ дополнительной прибыли. Метод перезапуска находит применение и для крупных вычислительных систем: телекоммуникационные international Data Corporation (IDC) — аналитическая фирма, специализирующаяся на исследованиях рынка информационных технологий. системы [20], серверные кластеры [21], аэрокосмические системы [22].

В течение совершения перезапуска веб-сервер недоступен пользователям, поэтому если совершать перезапуск часто, то это может привести к существенному увеличению времени простоя веб-сервера. В этой связи возникает задача выбора оптимального интервала времени между перезапусками веб-сервера. Один из подходов решения данной задачи состоит в построении математической модели, описывающей поведение веб-сервера и последующей разработке критериев оценки эффективности метода перезапуска. В работе T. Dohi [130] был рассмотрен ценовой критерий оценки эффективности метода перезапуска. Решалась задача минимизации величины отношения суммарной стоимости простоя системы в течение интервала времени к величине этого интервала. S. Mercier и M. Roussignol [122] исследовали вероятностные модели вычислительной системы с перезапуском. В их работе поведение системы описывалось некоторым случайным процессым с конечным числом состояний, а интервалы времени между наблюдениями за системой были независимыми случайные величины с произвольным распределением. Доказывалось, что метод перезапуска повышает готовность системы. В работе R. Cleroux [125] для системы с перезапуском исследовано поведение величины отношения времени простоя в течение интервала времени к величине этого интервала. Однако, в силу сложности построенной модели, задача минимизации не решена, а лишь предложен алгоритм для ее численного решения.

Для снижения влияния случайных сбоев на работу аналитической программы применяется метод контрольных точек. Суть этого метода состоит в записи состояния исполняемой программы в некоторый момент времени, который называется контрольной точкой. Тогда, если в дальнейшем происходит сбой в работе программы, то ее исполнение продолжается с момента записи последней контрольной точки. Тем самым, периодическое сохранение промежуточного результата работы аналитической программы позволяет сократить суммарное время ее исполнения. Под записью состояния исполняемой программы понимается процесс, который сохраняет на внешний носитель содержимое программного стека, статических и динамических сегментов данных, файлов и т.д. Среди работ предшественников, посвященных технической реализации отказоустойчивого ПО с контрольными точками, можно выделить исследования В. Г Хорощевского [92], В. О. Чуканова, Ю. В. Бородакий [93].

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

В диссертации исследуется применение метода контрольных точек

9Примсром является утилита Libckpt (http://www.cs.utk.edu/ plank/plank/www/libckpt.htral) для Unix операционных систем, разработанная в университете Теннесси.

10В качестве примера можно привести библиотеку функций Porch (http://supertech.csail.mit.edu/porch/), разработанную в- Массачусетском технологическом институте.

11Примером является библиотека функций ЕРСКРТ (http://www.research.rutgers.edu/ edpin/epckpt/), разработанная для Linux операционных систем. для аналитической программы с длительным временем исполнения. К данному классу программ относятся различные приложения моделирования сложных процессов и обработки данных:

• приложения интеллектуального анализа данных12;

• приложения инженерных расчетов, анализа и симуляции физических процессов.13

• моделирование процессов молекулярной динамики;14

• моделирование процессов гидродинамики.15

12 (англ. Data Mining) — выявление скрытых закономерностей или взаимосвязей между переменными в больших массивах необработанных данных. Наиболее распространенными приложениями являются SPSS, SAS, KXEN.

13CAE (англ. Computer-aided engineering). Расчётная часть чаще всего основана на численных методах решения дифференциальных уравнений (метод конечных элементов, метод конечных объёмов, метод конечных разностей и др.). Примером такового приложения является открытая интегрируемая платформа для численного моделирования SALOME (http://www.salome-platform.org/).

14Англ. Carr-Parrinello Molecular Dynamics application (www.cpmd.org). Метод, в котором временная эволюция системы взаимодействующих атомов или частиц отслеживается интегрированием уравнения их движения.

15Англ. NekSOOO computational fluid dynamics application (http://nek5000.mcs.anl.gov/). Один из численных методов и алгоритмов решения задачи моделирования течения жидкости. чек. Данный подход к решению задачи оценки эффективности метода контрольных точек использовал профессор Дюкского университета К. S. Trivedi [23]. В своих работах он исследовал задачу минимизации среднего времени работы программы в предположении, что интервалы времени между сбоями есть независимые случайные величины, распределенные по закону Вейбулла. Результат, полученный в его работе, состоял в численном решении задачи поиска оптимального интервала между контрольными точками. В работе X. Chen, М. R. Lyu [118] также исследовались численные методы нахождения оптимального интервала между контрольными точками. В работе Y. Huang [117] найдена верхняя оценка для оптимального интервала между контрольными точками.

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

• найти оптимальное количество контрольных точек;

• оценить верхний и нижний интервалы времени работы программы с контрольными точками;

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

Научная новизна.

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

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

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

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

Заключение диссертация на тему "Повышение эффективности функционирования вычислительных систем на основе аналитических методов оценки влияния сбоев программного обеспечения"

Заключение

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

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

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

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

Библиография Ключников, Константин Константинович, диссертация по теме Системный анализ, управление и обработка информации (по отраслям)

1. К.К. Ключников. Время исполнения программы в присутствии случайных сбоев // Дискретная математика, Выпуск №4, 2007, стр. 150-157.

2. К.К. Ключников. Минимизация времени исполнения программы // Информационные технологии моделирования и управления, №5(39) 2007, стр. 574-578.

3. К.К. Ключников. Старения процесса исполнения программного приложения // Открытое образование. №4 2007, стр. 38-43.

4. К. К. Ключников. Методы снижения влияния сбоев в работе бил-линговой системы // Мобильные системы, №08 2007, стр. 46-48.

5. К.К. Ключников. Асимптотическое поведение метода контрольныхточек, минимизирующего среднее время исполнения программы // Системы управления и информационные технологии, №3.1(29) 2007, стр. 155-158.

6. К. К. Ключников. Анализ вероятностного распределения случайной величины времени работы программы в присутствии случайных сбоев // Автоматика и телемеханика, №7, 2009, стр. 175-185.

7. М. Sullivan and R. Chillarege. Software Defects and Their Impact on System Availability A Study of Field Failures in Operating Systems // Proc. 21st IEEE Int. Symp. Fault-Tolerant Computing, 1991, pp. 2-9.

8. J. Gray Why do Computers Stop and What Can Be Done About It? // Proc. Fifth Symp. Reliability in Distributed Software and Database Systems, Jan. 1986, pp. 3-12.

9. M. Grottke and K. S. Trivedi. Fighting Bugs: Remove, Retry, Replicate, and Rejuvenate // IEEE Computer, Vol. 40, No. 2, 2007, pp. 107-109.

10. M. Winslett. Bruce Lindsay Speaks Out // ACM SIGMOD Record, June 2005, pp. 71-79.

11. I. Lee and R. K. Iyer. Software Dependability in the Tandem GUARDIAN System // IEEE Trans. Software Eng., vol 21 no 5, May 1995, pp. 455-467.

12. S. Chandra, P.M. Chen. Whither Generic Recovery from Application Faults? A Fault Study using Open-Source Software // Proceedings of the 2000 Int. Conf. on Dependable Systems and Networks.

13. I. Lee, R. Iyer. Faults, Symptoms, and Software Fault Tolerance in the Tandem GUARDIAN Operating System //In International Symposium on Fault-Tolerant Computing (FTCS), pp. 20-29, 1993.

14. A. Avizieriis. The n-version approach to fault-tolerant software // IEEE Trans, on Software Engineering, vol. SE-11, No. 12, December 1985, pp. 1491-1501.i

15. B. Randell. System structure for software fault tolerance // IEEE Trans, on Software Engineering, vol. SE-1, June 1975, pp.220-232.

16. Y. Huang and C.M.R. Kintala. Software Implemented Fault Tolerance: Technologies and Experience // Proceedings of 23rd International Simposium on Fault-Tolerant Computing. Toulouse, France, June 1993, pp.2-9.

17. E.N. Elnozahy, L. Alvisi, Y.-M. Wang, D.B. Johnson. A Survey of Rollback-Recovery Protocols in Message-Passing Systems // Technical Report CMU-CS-99-148, Carnegie Mellon University, June 1999.

18. L. Li, K. Vaidyanathan and K. S. Trivedi. An Approach to Estimation of Software Aging in a Web Server // Proc. International Symposium Empirical Software Engineering, October 2002, pp. 91-100.

19. A. Avritzer, E.J. Weyuker. Monitoring smoothly degrading systems for increased dependability // Empirical Software Engineering, vol.2, no.l, pp. 59-77, 1997.

20. V. Castelli, R.E. Harper, P. Heidelberger, S.W. Hunter, K.S. Trivedi, K. Vaidyanathan, W.P. Zeggert. Proactive management of software aging // IBM Journal of Research and Development, vol. 45, no. 2, pp.311-332, 2001.

21. A.T. Tai, L. Alkalaj, S.N. Chau. On-board preventive maintenance: a design-oriented analytic study for long-life applications // Performance Evaluation, vol.35, no.3-4, pp. 215-232, 1999.

22. S. Garg, Y. Huang, C. Kintala and K. S. Trivedi. Minimizing Completion Time of a Program by Checkpointing and Rejuvenation // ACM SIGMETRICS 1996, May 1996, pp. 252-261.

23. E. Gelenbe. On the Optimum Checkpoint Interval // Journal of the Association for Computing Machinery, Vol. 26, No. 2, April 1979, pp. 259-270.

24. J. Hong, S. Kim, Y. Cho. Cost Analysis of Optimistic Recovery Model for Forked Checkpointing // IEICE TRANS. INF. SYST., VOL.E85-A, N0.1 JANUARY 2002, pp. 1-8.

25. D. Nurmi, R. Wolski, J. Brevik. Model-Based Checkpoint Scheduling for Volatile Resource Environments // UCSB Computer Science Technical Report Number 2004-25, Santa Barbara, CA, 93106.

26. D. Nurmi, J. Brevik, R. Wolski. Minimizing the Network Overhead of Checkpointing in Cycle-harvesting Cluster Environments // IEEE1.ternational Conference on Cluster Computing (Cluster 2005),Boston, Massachusetts, USA, September 27 30, 2005, pp. 1-10.

27. Nitin H. Vaidya. On staggered checkpointing //In Eighth IEEE Symposium on Parallel and Distributed Processing(SPDP), October 1996, pp. 572-580.

28. Nitin H. Vaidya. On checkpoint latency // Technical Report: TR95-015, December 1995.

29. Y. M. Wang and W. K. Fuchs. Lazy checkpoint coordination for bounding rollback propagation //In Symposium on Reliable Distributed Systems, October 1993, pp. 78-85.

30. Y. M. Wang, Y. Huang and W. K. Fuchs. Progressive retry for software error recovery in distributed systems //In Digest of papers: the 23rd International Symposium Fault-Tolerant Computers, 1993, pp. 138144.

31. R. E. Strom and S. A. Yemini. Optimistic recovery: An asynchronous approach to fault-tolerance in distributed systems // Digest of papers: The 14-th Int. Symp. Fault-Tolerant Comp., 1984, pp.374-379.

32. J. S. Plank, M. Beck, G. Kingsley and K. Li. Libckpt: Transparent checkpointing under Unix // In Usenix Winter 1995 Technical Conference, New Orleans, January 1995.

33. J. S. Plank. Efficient Checkpoiting on MIMD Architectures // PhD thesis, Dept. of Computer Science, Princeton University, June 1993.

34. Y. M. Wang, Y. Huang, K. P. Vo, P. Y. Chung and C. Kintala.

35. Checkpointing and Its Applications //In Proc. IEEE Fault-Tolerant Computing Symp. (FTCS-25), June 1995, pp.22-31.

36. J. S. Plank, K. Li, M. Puening. Diskless Checkpointing // Technical Report UT-CS-97-380, University of Tennessee, December 12 1997.

37. J. S. Plank and M. G. Thomason. The average availability of the parallel checkpointing systems and its importance in selecting runtime parameters //In 29-th International Symposium on Fault-Tolerate Computing, Madison, WI, June 1999, pp. 250-259.

38. J. S. Plank and M. G. Thomason. Processor Allocation and Checkpoint Interval Selection in Cluster Computing Systems // Journal of Parallel and Distributed Computing in 2001, pp. 1570 1590.

39. A. L. Goel Software reliability models: Assumptions, limitations and applicability //In IEEE Tran. Software Engineering, vol SE-11, Dec 1985, pp. 1411-1423.

40. T. Heath, P. M. Martin and T. D. Nguyen. The shape of failure // Proceedings of the First Workshop on Evaluating and Architecting System dependability (EASY), July 2001, pp. 1-4.

41. Y. Ling, J. Mi and X. Lin. A variational calculus approach to optimal checkpoint placement // IEEE Trans, on Computers, Volume 50, Issue 7, Jul 2001, pp. 699 708.

42. I. Lee, D. Tang, R. K. Iyer and M. C. Hsueh. Measurement-based evaluation of operating system fault tolerance //In IEEE Trans, on Reliability, Volume 42, Issue 2, June 1993, pp. 238-249.

43. A. Acharya and B. R. Badrinath. Checkpointing Distributed Applications on Mobile Computers // Proc. Third Int. Conf. Parallel and Distributed Information Systems, Sept. 1994, pp. 73-80.

44. B. Bhargava, S. R. Lian and P. J. Leu. Experimental Evaluation of Concurrent Checkpointing Rollback-Recovery Algorithms // Proc. Int. Conf. Data Engineering, 1990, pp.182-189.

45. G. Cao and M. Singhal. Low-Cost Checkpointing with Mutable Checkpoints in Mobile Computing Systems // Proc. 18th Int. Conf. Distributed Computing Systems, May 1998, pp. 464-471.

46. G. Cao and M. Singhal. On Coordinated Checkpointing in Distributed Systems // IEEE Trans. Parallel and Distributed System, December 1998, pp. 1213-1225.

47. Philip F. Chimento, K. S. Trivedi . The Completion Time of Programs on Processors Subject to Failure and Repair // IEEE TRANSACTIONS ON COMPUTERS, VOL. 42, NO. 10, OCTOBER1993, pp. 1184-1194.

48. F. Cristian and F. Jahanian. A Timestamp-Based Checkpointing Protocol for Long-Lived Distributed Computations // Proc. IEEE Symp. Reliable Distributed Systems, 30 Sep-2 Oct 1991, pp. 12-20.

49. H. Karl, M. Werner. An Optimal Checkpointing Interval for RealTime Systems // Technical Report Informatik-Berichte Nr. 92, Institut fur Informatik, Humboldt-Universitat, Berlin, 1997.

50. Y. Deng and E. K. Park. Checkpointing and Rollback-Recovery Algorithms in Distributed Systems //J. Systems and Software, April1994, pp. 59-71.

51. E. N. Elnozahy, D. B. Johnson and W. Zwaenepoel. The Performance of Consistent Checkpointing // Proc. 11th Symp. Reliable Distributed Systems, Oct. 1992, pp. 86-95.

52. S. T. Huang. Detecting Termination of Distributed Computations by External Agents // Proc. Ninth International Conference Distributed Computing Systems, 1989, pp. 79-84.

53. J. L. Kim and T. Park. An Efficient Protocol for Checkpointing Recovery in Distributed Systems // IEEE Trans. Parallel and Distributed Systems, Aug. 1993, pp. 955-960.

54. D. Johnson. Distributed System Fault Tolerance Using Message Logging and Checkpointing // PhD Thesis, Rice University, Dec. 1989.

55. R. Koo and S. Toueg. Checkpointing and Rollback-Recovery for Distributed Systems // IEEE Trans. Software Eng., Jan. 1987, pp. 23-31.

56. P. Krishna, N. H. Vaidya and D. K. Pradhan. Recovery in Distributed Mobile Environments // Proc. IEEE Workshop Advances in Parallel and Distributed System, Oct. 1993, pp. 83-88.

57. D. Manivannan and M. Singhal A Low-Overhead Recovery Technique Using Quasi-Synchronous Checkpointing // Proc. 16th Int. Conf. Distributed Computing Systems, May 1996, pp. 100-107.

58. R. Prakash and M. Singhal. Low-Cost Checkpointing and Failure Recovery in Mobile Computing Systems // IEEE Trans. Parallel and Distributed Systems, Oct. 1996, pp. 1035-1048.

59. Malhotra M., Trivedi K. S. Power-hierarchy of dependability-model types // IEEE Transactions on Reliability, Volume 43, Issue 3, Sep 1994, pp. 493-502.

60. Goyal A., Lavenberg S. S. Modeling and analysis of computer system availability // IBM Journal of Research and Development, Volume 31, Issue 6, December 1987, pp. 651 664.

61. Birnbaum Z. W. On the importance of different components in a multicomponent system // In: Multivariative Analysis:II. Academic Press, New York, 1969, pp. 581-592.

62. A. E. Gera. The modified exponentiated-Weibull distribution for lifetime modeling //In Proc. Annual Reliability and Maintainability Symp., 1997, pp. 149-152.

63. D. B. Kececioglu and W. Wang. Parameter estimation for mixed-Weibull distribution //In Proc. Annual Reliability and Maintainability Symp., 1998, pp. 247-252.

64. S. Srinivasan and R. Subramanian. Probabilistic Analysis of Redundant System's // Springer-Verlag, 1980, Lecture Notes in Economics and Mathematical Systems.

65. L. C. Tang, Y. S. Sun, T. N. Goh and H. L. Ong. Analysis of step-stress accelerated-life-test // IEEE Trans. Reliability, vol 45, 1996, pp. 69-74.

66. K. S. Trivedi. Probability and Statistics with Reliability, Queueing and Computer Science Applications // 2nd. edition. New York: Wiley, 2002.

67. Y. Cao, H. Sun, K. S. Trivedi, J. J. Han. System Availability With Non-Exponentially Distributed Outages // IEEE Trans, on Reliability, vol 51, no 2, June 2002, pp. 193-198.

68. Chen D-Y, Trivedi K. S. Analysis of periodic preventive maintenance with general component failure distribution / / Pacific Rim International Symposium on Dependable Computing (PRDC'01), Seoul, Korea, December 2001.

69. Vaurio J. K. On time-dependent availability and maintenance optimization of standby units under various maintenance policies // Reliab. Engng. Syst. Saf, 1997, vol. 56, pp. 79-89.

70. Légat V., Zaludova A. H., Cervenka V., J urea V. Contribution to optimization of preventive maintenance // Reliab. Engng. Syst. Saf. 1996, vol. 51, pp. 259-266.

71. Sahner R. A., Trivedi K. S., Puliafito A. Performance and reliability analysis of computer systems // Dordrecht: Kluwer Academic Publishers, 1996.

72. Sim S. H., Endrenyi J. Optimal preventive maintenance with repair // IEEE Trans. Reliab, 1988, vol. 37 issue 1, pp. 92-96.

73. Hosseini M. M., Kerr R. M., Randall R. B. An inspection model with minimal and major maintenance for a system with deterioration and Poisson failures // IEEE Trans. Reliab, 2000, vol. 49, issue 1, pp. 88-98.

74. Pulcini G. On the overhaul effect for repairable mechanical units: a Bayes approach // Reliab. Engng. Syst. Saf., October 2000, volume 70, issue 1, pp. 85-94.

75. Aven Т., Dekker R. A. A useful framework for optimal replacement models. Reliab // Engng. Syst. Saf., October 1997, volume 58, Number 1, , pp. 61-67.

76. Marseguerra M., Zio E. Optimizing maintenance and repair policies via a combination of genetic algorithms and Monte Carlo simulation // Reliab. Engng. Syst. Saf., April 2000, volume 68, number 1, pp. 69-83.

77. D. Chen, K. S. Trivedi. Closed-form analytical results for condition-based maintenance // Reliability Engineering and System Safety, April 2002, vol. 76, num. 1, pp. 43-51.

78. A. Goyal, S. S. Lavenberg and K. S. Trivedi. Probabilistic Modeling of Computer System Availability // Annals of Operations Research, vol. 8, num. 1, December 1987, pp. 285-306.

79. M. D. Beaudry. Performance-related reliability measures for computing systems // IEEE Trans, on Computers, vol. 27, issue 6, June 1978, pp. 540-547.

80. JI. Э. Элъсголъц. Дифференциальные уравнения и вариационное исчисление // Изд. УРСС, 2000 г.

81. A. Goyal and А. N. Tantawi. A measure of guaranteed availability and its numerical evaluation // IEEE Trans. Comput., vol C-37, 1988, pp. 25-32.

82. G. Rubino and B. Sericola. Interval availability analysis using operational periods // Perform. Eval., vol 14, 1992, pp. 257-272.

83. E. de Souza c Silva and H. R. Gail. Calculating cumulative operational time distributions of repairable computer systems // IEEE Trans. Comput., vol. C-35,1986, pp. 322-332.

84. G. Rubino and B. Sericola. Interval availability distribution computation //In Proc. IEEE 23-th Fault-Tolerant Computing Symp., Toulouse, France, 1993, pp. 49-55.

85. G. Rubino and B. Sericola. Interval Availability Analysis Using Denumerable Markov Processes: Application to Multiprocessor Subject to Breakdowns and Repair // IEEE Trans, on Computers, vol. 44, no. 2, February 1995, pp. 286-291.

86. J. K. Muppala, M. Malhotra and K. S. Trivedi. Markov dependability models of complex systems: Analysis techniques // In S. Ozekici, editor, Reliability and Maintenance of Complex Systems, Berlin, Germany, 1996, pp. 442-486. Springer.

87. J. K. Muppala, S. P. Woolet and K. S. Trivedi. On modeling performance of real-time systems in the presence of failures //In Readings in Real-Time Systems, Los Alamitos, CA, USA, 1993, pp. 219-239.

88. K. Shen and M. Xie. On the increase of system reliability by parallel redundancy // IEEE Transactions on Reliability, vol. 39, issue 5, December 1990, pp. 607-611.

89. S. Garg, A. van Moorsel, K. Vaidyanathan, K. Trivedi. A Methodology for Detection and Estimation of Software Aging // Proc. Ninth International Symp. Software Reliability Eng., Nov. 1998, pp. 282-292.

90. M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables // New York: Dover, 1972.

91. Y. Bao, X. Sun and K. Trivedi. Adaptive Software Rejuvenation: Degradation Models and Rejuvenation Schemes // Proc. International Conference Dependable Systems and Networks, June 2003, pp. 241-248.

92. А. Е. Александрович, Ю. В. Вородакий, В. О. Чуканов. Проектирование высоконадежных информационно-вычислительных систем // Издательство „Радио и связь", 2004 г.

93. Y. Hong, D. Chen, L. Li and К. S. Trivedi. Closed Loop Design for Software Rejuvenation // Proc. Workshop Self-Healthing, Adaptive and Self-Managed Systems (SHAMAN 2002), June 2002.

94. A. Avizienis, J.-C. Laprie and B. Randell. Fundamental Concepts of Dependability // LAAS Technical Report No. 01-145, LAAS, France, Apr. 2001.

95. Y. Huang, P. Jalote and C. Kintala. Two Techniques for Transient Software Error Recovery // Lecture Notes in Computer Science, vol. 774, 1994, pp. 159-170.

96. J. Gray. A Census of Tandem System Availability between 1985 and 1990 // IEEE Trans. Reliability, vol. 39, Oct. 1990, pp. 409-418.

97. K. Vaidyanathan and K. S. Trivedi. A Measurement-Based Model for Estimation of Resource Exhaustion in Operational Software Systems // Proc. 10th IEEE Int. Symp. Software Reliability Eng., Nov. 1999, pp. 84-93.

98. S. S. Gokhale, K. S. Trivedi. A time/structure based software reliability model // Annals of Software Engineering 8(1999) pp. 85-121.

99. J. Gray and D. P. Siewiorek. High-availability computer systems // IEEE Computer Mag, Sept. 1991, pp. 39-48.

100. J: Huang, C. R. Miller and O. G. Okogbaa. Optimal preventive replacement intervals for the Weibull life distributions: Solutions and applications //In Proceedings of annual reliability and maintainability symposium, 1995, pp. 370-377.

101. S. Yamada, M. Ohba and S. Osaki. S-Shaped Reliability Growth Modeling for Software Error Detection // IEEE Trans, on Reliability, R-32(5), Dec. 1983, pp. 475-485.

102. J-C. Laprie, J. Arlat, C. Beounis and K. Kanoun. Architectural issues in software fault-tolerance // Software Fault Tolerance. Ed. M. R. Lyu, John, Wiley&; sons ltd., 1995, pp. 47-80.

103. K. Vaidyanathan and K. S. Trivedi. A Comprehensive Model for Software Rejuvenation // IEEE Transactions on Dependable and Secure Computing, vol 2 no 2, April-June 2005, pp. 124-137.

104. International Telecommunication Unit. http://www.itu.int/ITU-R

105. J. Gray Why do Computers Stop and What Can Be Done About It? // Proc. Fifth Symp. Reliability in Distributed Software and Database Systems, Jan. 1986, pp. 3-12.

106. H. Sun, X. Zang and K. S. Trivedi. A BDD-based Algorithm for Reliability Analysis of Phased-Mission Systems // IEEE Transactions on Reliability vol 48 no 1, March 1999, pp. 50-60.108. http://www.ee.duke.edu/kst/ Software Packages for Modeling.

107. M. Malhotra and K. S. Trivedi. Dependability Modeling Using Petri-Nets // IEEE Transactions on Reliability vol 44 no 3, September 1993, pp. 428-440.

108. L. Bernstein. Innovative Technologies for Preventing Network Outages // AT&T Technical Journal, Vol. 72, No.4, July 1993, pp. 4-10.

109. J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques // Morgan Kaufmann Publishers, San Mateo, CA, 1993.

110. G. Arfken. Mathematical Methods for Physicists // 3rd ed. Orlando, FL: Academic Press, 1985.

111. A. H. Колмогоров, С. В. Фомин. Элементы теории функций и функционального анализа // Издательство „Наука", Москва 1976.

112. Б. В. Гнеденко, Ю. К. Беляев, А. Д. Соловьев. Математические методы в теории надежности // Издательство „Наука", Москва 1965.

113. Дж. JI. Дуб. Вероятностные процессы // Издательство ИНОСТРАННОЙ ЛИТЕРАТУРЫ, Москва 1956.

114. Tadashi Dohi, Naoto Kaio. The Optimal Age-Dependent Checkpoint Strategy for a Stochastic System Subject to General Failure Mode // Journal of Mathematical Analysis and Applications 249, 2000, p. 80-94.

115. Y. Huang Autonomic Web-Based Simulation // Dissertation for the degree of Doctor of Philosophy, Notre Dame, Indiana, March 2005.

116. X. Chen, M.R. Lyu. Performance and Effectiveness Analysis of Checkpointing in Mobile Environments // Proceedings of the 22nd International Symposium on Reliable Distributed Systems, 6-18 Oct. 2003, pp. 131 140.

117. A. Boukas. Minimal Operation Time of Energy Devices // Applied Mathematics E-Notes, 5(2005), pp. 269-274.

118. И.В. Машечкин, А.А. Смирнов. Поиск мест создания консистентных контрольных точек в параллельных программах путем анализа трассы программы // Вестн. Моск. ун-та. Сер. 15. Вычислительная математика и кибернетика. 2007. №2, стр. 46-52.

119. S. Mercier and М. Roussignol. Asymptotic failure rate of a Markov deteriorating system with preventive maintenance // Journal of Applied Probability, vol.40, Num. 1(2003), pp. 1-19

120. Y. Bao, X. Sun, and K.S. Trivedi. A Workload-based analysis ofsoftware aging, and rejuvenation // IEEE Trans, on Reliability, vol.54, no.3, Sept. 2005, pp. 541-548.

121. H. Liao, L.Y. Chang, E.A. Elsayed. Maintenance of Continuously Monitored Degrading Systems // European Journal of Operational Research, vol. 175, issue 2, 1 December 2006, pp. 821-835.

122. R. Cleroux. On Modelling Preventive Replacements of Randomly Deteriorating Systems // Investigación Operativa,6, 1998, pp.55-66.

123. C.T. Chen, M.H. Lin, C.P. Wang, J. Yuan. Study of Real time Dynamic Preventive Maintenance Policy for Deteriorating Production Systems // International Journal of The Computer, the Internet and Management, vol.l5#l, Jan.-Apr. 2007, pp.1-14.

124. A. Grail, C. Berenguer, L. Dieulle. A condition-based maintenance policy for stochastically deteriorating systems // Reliability Engineering and System Safety, vol. 76, no.2, May 2002, pp. 167180.

125. A. Grail, L. Dieulle, C. Berenguer, M. Roussingnol. Continuous-Time Predictive-Maintenance Scheduling for a Deteriorating System // IEEE Transactions on Reliability, vol. 51, no.2, June 2002, pp. 141 150.

126. V. Makis, X. Jiang. Optimal Replacement under Partial Observations // Mathematics of Operations Research, June 6, 2002, pp.1-13.

127. T. Dohi, K. Goseva-Popstojanova, K.S. Trivedi. Analysis of Software Cost Models with Rejuvenation // Fifth International Symposium on HASE 2000, pp. 25-34.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00