Вероятностные методы оценки надежности, доступности компьютерных систем тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. Ломоносова

На правах рукописи

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

Вероятностные методы оценки надежности, доступности компьютерных

систем

Специальность 01 01 05 - теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

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

МОСКВА 2008

003164540

Работа выполнена на кафедре математической статистики факультета ВМиК МГУ имени М В Ломоносова

Научный руководитель доктор физико-математических наук, профессор Грушо А А

Официальные оппоненты доктор физико-математических наук, зам директора ИТМ и ВТ имени С А Лебедева, профессор Князев А В ,

кандидат физико-математических наук, старший научный сотрудник факультета ВМиК МГУ имени М В Ломоносова Уфимцев М В Ведущая организация Московский государственный институт электроники и математики

Защита состоится «_ Á9 * cpe£ft¿Í<sJ> 200<?года в 11— часов на заседании

диссертационного совета Д 501 001 44 при Московском государственном университете имени М В Ломоносова по адресу 119991 Москва ГСП-1, Ленинские горы, МГУ 2— учебный корпус, факультет ВМиК, аудитория 685 Автореферат разослал * 23 * ■MißajtJ? 200/?г С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ имени М В Ломоносова http //www eme msu ru в разделе „Наука"-"Работа диссертационных советов"-"Д 501 001 44"

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

профессор tfa^r**"^ Трифонов Н П

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

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

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

Основные результаты работы Основные результаты диссертационной работы, выносимые на защиту

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

2 Для случая N равноудаленных контрольных точек найдена величина среднего времени исполнения программы При N —> оо получено достаточное условие, при котором среднее время конечно

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

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

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

Публикации. Результаты диссертации опубликованы в 5 печатных работах, четыре из которых - в рецензируемых журналах, входящих в список ВАК

Структура диссертации. Диссертация состоит из введения, трех глав, состоящих в совокупности из 11 разделов, заключения, приложения и списка литературы Полный объем диссертации - 107 страниц

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

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

Таким образом, программа исполняется до тех пор, пока сбоя в течение времени ее исполнения не произойдет Пусть (П, А, Р) есть вероятностное пространство, где П есть множество элементарных исходов, А есть а - алгебра подмножеств множества П Пусть Хг есть случайная величина интервала времени между сбоями с номерами г - 1 и г, где г > 1. Хо = 0 Предполагаем, что случайные величины Х„г € N измеримы относительно а - алгебры А Также предполагаем, что случайные величины Х\,Х2, независимые, распределенные экспоненциально с параметром А Использование экспоненциального распределения для моделирования отказов в вычислительной технике регламентировано ГОСТ 27 402-95 „Надежность в технике" Определим время исполнения программы Т следующим образом

w.

если Х\(и) > w

T(u>) =

X\(uj) + w, если < w,X2(w) > w

Хг(ш) + Х2(ш) + w, если < w, X2M < w, Хз(ш) > w

(1)

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

В данной работе рассматривается метод контрольных точек (checkpoint), идея которого состоит в следующем Будем записывать состояние программы в одной из точек интервала (0,w), которую назовем контрольной точкой Тогда, если сбой произойдет позже момента записи состояния программы в контрольной точке, то возвращаться надо не в нулевую точку, а в контрольную Предполагаем, что время возврата работы программы в контрольную точку равно нулю Формально обозначим контрольную точку через aw (0 < а < 1), а время исполнения программы при применении метода контрольных точек через Та(и>) Определим Та(ш) следующим образом

Е [Т] = \ (еЛш - 1)

(2)

w,

если и 6 С

T«(w) = w + Х;^!1 Х,{и), если w е В„, п > 2 (3)

(1 - a) w + Х^1 Х,(ш), если шеАп,п> 2, где С = {ш Xi(uj) > ш},

Вп = {w Xi(ш) < aw, ,Xn-i(u) < aw,Xn(ui) >w}, n> 2,

Ап = {ш аад < ^(ш) < ад,Х2(ш) < (1 — а)ад, , Х„_1(ш) < (1 - а)гп, Хп{ш) > (1 - а)ад} и {ш Хх(ш) < аад, аад < Х2{и) < ю,Х3(и) < (1 - а)ад, < (1 - а)и

Х„Н > (1 — а)ад} и и {а; ^(а)) < аи>, Х2{ш) < аад, , Хп_2(ы) < аад,аад < Хп-\(ш) < ад, Хп{ш) > (1 — а)ад} , п > 2 Утверждение 1.5. Та(ш) есть случайная величина Утверждение 1.6. Для математического ожидания случайной величины Та(и) имеет место следующее выражение

Е [Та] = \ (еЛаш - 1) + ± (еАЧ~а>ш - 1) (4)

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

Теорема 1. 1) Математическое ожидание случайной величины Т„(ш) достигает минимума в точке а = 2) Е [Та] <Е\Т] при 0 < а < 1

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

Далее рассматривается модель, в которой время восстановления программы в контрольной точке после сбоя есть постоянная величина (5, а время восстановление программы в начальной точке после сбоя есть постоянная величина с Также время записи состояния программы в контрольной точке есть функция а = ад) Для случая равноудаленного размещения N контрольных точек на отрезке [0, ад], математическое ожидание случайной величины времени исполнения программы вычисляется в следующем утверждении

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

Ё [г-1] = + Нй) е^ - - т + (5)

+с (е А - 1 ^ + ЛГа (ЛГ, го)

Для предельного случая N —► оо справедлива следующая теорема Теорема 2 Пусть функция а = ю) = 0 < 6 < 1, тогда кт Ё = °°

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

Утверждение 1 9. Выражение для математического ожидания случайной величины V/(и) имеет вид

ГУ)

Е[\¥] = еХи,а е'^'йх (6)

Jo

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

1 Е[Щ=Е[Т\ приа=1,

2 Е [Ж] > Е [Т] при а > 1, ад > 1,

3 Е[Щ < £[Г]приа< 1,ги> 1

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

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

В диссертации проводится численный анализ величины (7) Оказывается, что при хи > 1, математическое ожидание случайной величины 1Уа(и1) возрастает по параметру а Вторая глава посвящена исследованию показателей надежности, доступности на примере компьютерной системы, состоящей из сервера и двух рабочих станций Под надежностью понимается вероятность события, состоящего в том, что система выполняет требуемую задачу на временном интервале [0,1] Доступность есть вероятность события, состоящего в том, что система выполняет требуемую задачу в определенный момент времени В диссертации рассматривается модель без восстановления рабочей станции после сбоя и модель с восстановлением Рассмотрим сначала случай без восстановления рабочей станции

Пусть (г, ]) есть состояние, в котором находится система Индекс г обозначает количество работоспособных рабочих станций (принимает значения 2,1,0), индекс ] принимает значения 1-сервер работает, 0-сервер находится в состоянии сбоя Считаем, что система находится в работоспособном состоянии, если сервер и хотя бы одна из рабочих станция работоспособны Множество возможных состояний системы есть А = {(0,1), (1,1), (1,0), (2,0), (2,1)} Пусть е К+ есть случаный про-

цесс, описывающий состояние работы системы, принимающий значения из множества А Пусть 7Г,(£) = Р (и> Х^и) = г),

г € {(2,1), (1,1), (0,1), (2,0), (1,0)} Предположим, что случайный про-

цесс Xt(w) есть марковская цепь со следующей диаграммой:

к

■2,1) MJ) (0,1

X,

X.

2,0) (1,0) (0,0^

Рис. 1.

Величина надежности R(t) для данной системы имеет вид

R(t) = T(2,i)(t) + T(i,i) (*) = 2е_'Л"+Л,'< - е-(2л»+л')'. (8)

Диаграмма марковской цепи для системы с восстановлением имеет вид:

"2Х......

2,1

2,0 1,0

('0,0 » V У

Рис. 2.

т =

Ни

ki -{- 2AW H- As

+ 1 ) C\eklt +

fJ'Vj

k2 + 2АШ + As

+ 1 ) (9)

(Ai! +2AM +As)(fc2 + 2ATO +As),

Q __ _

1 - fcl) C2 = -Ci;

, _ - (ЗАМ + 2А5 + ± у7А^ + /4 + бАшдт «1,2 - 2 ■

В диссертации проводится численное сравнение выражений (9) и (8). Оказывается, что величина надежности, определенная выражением (9)

больше величины, определенной выражением (8) Кроме того, исследуется асимптотическое свойство выражения (9) Это свойство приведено в следующем утверждении Утверждение 2 1 lim R(t) = e~A,i

Hvj—bOO

Условие pw —> оо подразумевает, что в случае сбоя одной из рабочих станций, осуществляется мгновенный переход в «идеальное» состояние (2,1) В этом случае показатель надежности R(t) достигает максимума и его предельное значение зависит лишь от параметра А„-среднего времени сбоя сервера Третья глава посвящена исследованию метода обновления работы программы Предполагаем, что с самого начала работы компьютерная система, на которой исполняется программа, находится в некотором идеальном состоянии Вероятность сбоев в этом состоянии близка к нулю Идеальное состояние обозначим через «О» Предполагаем, что пребывание системы в состоянии «О» не бесконечно и через некоторое время система переходит в состояние «Р», в котором вероятность сбоя уже отлична от нуля Происходит этот переход по причине того, что процесс функционирования системы со временем деградирует и начинает происходить постепенная утечка ресурсов компьютерной системы Из состояния «Р» система через некоторое время переходит в состояние «F», что соответствует сбою в работе системы Данный процесс можно формализовать с помощью следующей математической модели Пусть Xt(u)),t е R+ есть случайный процесс со значениями во множестве {О, Р, F} Предполагаем, что Xt(<j),t е R+ есть марковская цепь, диаграмма которой представлена на Рис 3

Рис. 3.

Пусть также процесс Xt(oj) однородный по времени и обладает марковским свойством. Обозначим щ(t) — Р (Xt(üj) = г), i 6 {О, Р, F}. Тогда справедлива система дифференциальных уравнений Колмогоровой = -r2n0(t) + rinF(t) ' TTp(i) =-Лтгр(г)+r27r0(i)

[ 7TF{t) = -nMt) + В силу эргодической теоремы

Зщ = lim TTi(t),ie {О,P,F}. t—* 00

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

-Г27Г0 +TlTlF = О

— Хттр + Г27Г0 = О

<

—Г\-кр + Хттр — О

Щ + -Кр + Пр — 1.

Отсюда

1

nF ~-п-гТ- V10)

1 + -f + — А г2

Величина ttf есть предельная вероятность пребывания системы в состоянии сбоя. С ее помощью можно оценить надежность работы ком-

пыотерной системы. Если величина жр велика, то это говорит о низкой надежности системы. Величина доступности системы определяется как 7гд = 1 — пр. Далее рассмотрим модель, в которой система из состояния «Р» может также переходить в состояние «Я», в котором осуществляется обновление работы системы. Пусть диаграмма переходов системы имеет вид:

о ■ <э

Рис. 4.

Считаем, что система во время пребывания в состоянии «Я» не функционирует. Тогда выражение для предельной вероятности сбоя системы примет вид

гф, = / А гЛ --1-^

гз/ 1 , Л , | Л + г4 П г3 г2

Величина доступности системы определяется как ■кГд3и" = 1 — пТрт. Теорема 3.

1. Если г3 > Г\ + то тф™ убывает по параметру г4.

2. Если Гз < Г\ + то 7Гр3их> возрастает по параметру п. Таким образом, последняя теорема указывает достаточное условие, при

котором метод обновления увеличивает величину предельной доступности системы

Список литературы

[1] К К Ключников Время исполнения программы в присутствии случайных сбоев Дискретная математика, Выпуск №4, 2007, стр 150157

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

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

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

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

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия 00510 от01 12 99 г Подписано к печати 28 01 2008 г Формат 60x90 1/16 Уел печл 1,0 Тираж 100 экз Заказ 022 Тел 939-3890 Тел/Факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им МВ Ломоносова, 2-й учебный корпус, 627 к