Надежность параллельных вычислений

1. Число ошибок в программе - величина "ненаблюдаемая", наблюдаются не сами ошибки, а результат их проявления.

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

3. Ошибки могут компенсировать друг друга, так что после исправления какой-то одной ошибки программа может начать "работать хуже".

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

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

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

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

Модель последовательности испытаний Бернулли

Рассмотрим для простоты класс программ, имеющих единственный вход и выход, т.е. не содержащих бесконечных циклов. Фазу выполнения программы от начала до завершения будем называть запуском. Все возможные результаты запуска разобьем на два класса: правильные и неправильные (ошибочные). Будем считать, что любой результат всегда можно отнести к одному из этих классов. (Ясно, что по этому вопросу возможны разногласия между изготовителями программы и пользователями, однако будем предполагать, что имеется какой-то общий критерий, например, "клиент всегда прав".) Рассмотрим классическую вероятностную модель последовательности испытаний Бернулли. Пространство элементарных событий в этой модели содержит 2n точек, где n - число испытаний (в данном случае под испытанием подразумевается запуск программы). Каждый запуск программы имеет два исхода: правильный и неправильный. Обозначим вероятность неправильного исхода р, а вероятность правильного - (1-p). Вероятность того, что из n запусков К приведут к неправильному результату, выражается хорошо известной формулой биномиального распределения.

B(р,n,k) = C(n,k) * pk * (1-р)(n-k), (5.1)

где С(n,k) - число сочетаний. Вероятность р априори неизвестна, но по результатам запусков известны n и k. Величина В как функция р имеет максимум при

р = k/n. (5.2)

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

R = 1 - k/n = (n-k)/n, (5.3)

значения которой (от 0 до 1) согласуются с общепринятым смыслом термина надежность: например, если все запуски окончились с ошибочным результатом (k = n), то надежность - нулевая.

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

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

Некоторые следствия

Формула (3) позволяет оценить надежность программы по результатам ее запусков. Следует особо остановиться на двух предельных случаях: k = n (нулевая надежность) и k = 0 (абсолютная надежность). В обоих случаях результаты не следует интерпретировать буквально: нет никаких гарантий того, что очередной запуск приведет к тому же результату, что и предыдущие. Однако с точки зрения пользователя эти случаи совершенно разные. Если нулевая надежность свидетельствует о том, что программа явно непригодна для эксплуатации, то показатель абсолютной надежности не должен вводить в заблуждение: такой вывод нельзя делать по результатам даже очень большого числа запусков. Следует подчеркнуть, что для оценки надежности в этом случае необходимо рассмотреть другие вероятностные модели.

Из формулы (3) следует, что оценка надежности программы растет с увеличением числа ее запусков по гиперболическому закону. Это подтверждает интуитивно ясное соображение о том, что программа тем надежнее, чем больше опыт ее эксплуатации, который зависит как от интенсивности использования программы, так и от тиража компьютера, на котором она запускается. Таким образом, надежность программ для персональных компьютеров типа IBM РС, общий тираж которых составляет в настоящее время около 100 миллионов, на несколько порядков выше аналогичных программ для специализированных процессоров (если, конечно, такие программы действительно существуют и эксплуатируются).

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

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

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

Марковская модель надежности ПО смешанного типа

Рассмотрим надежность ПО как надежность системы смешанного типа. На практике чаще встречаются ситуации смешанного типа (программный комплекс (ПК) сравнительно прост и его состояния сравнительно немногочис­ленны и ПК, состоит из многочисленных модулей). Для таких ПК и на­пишем уравнения. Эта модель применима для ПК, который состоит из элементов-мо­дулей разного типа: немногочисленных (уникальных) (например, в архитектуре клиент-сервер это – сервер) и многочисленных (в архитектуре клиент-сервер это – клиенты), причем состояния тех и других взаимообусловлены.

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

Рассмотрим ПК S, состоящий из большого количества N одинаковых клиентских программ и одного сервера, который координирует работу всех клиентских программ. Как сервер, так и отдельные клиенты могут отказывать (зависать). Интенсивность потока отказов сервера зависит от числа x работающих программ-клиентов (то есть фактически зависит от интенсивности входных данных и их диапазона):               (5.4)

Интенсивность потока неисправностей каждого модуля при работающем сервере равна l` (например, можно предположить, что интенсивность обнаружения ошибок уменьшается со временем из-за того, что ошибки исправляются и уменьшаются по законуили ). Среднее время устранения ошибки в сервере зависит от количества, найденных ошибок в модулях y:

              (5.5)

и для простоты полагаем константой.

Среднее время исправления ошибки в модуле зависит от количества обнаруженных ошибок y:

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

Опишем процесс, протекающий в ПК с помощью уравнений смешанного типа, в которых неизвестными функциями будут:

-         вероятности состояний сервера;

-         средние численности состояний клиентов.

Опишем нашу систему при помощи графа, показанного на рисунке:

Рисунок 5.1 – Граф смешанной системы

Этот граф распадается на два подграфа. Первый (верхний) – это подграф состояний сервера, который может быть в одном из двух состояний:

C(t) – работает;

С’(t) – не работает (ошибка обнаружена и исправляется).

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

П1С(t) – клиент работает при работающем сервере;

П2С(t) – клиент не работает при работающем сервере;

П2С’(t) – клиент не работает при не работающем сервере;

Состояние сервера характеризуется в момент времени t одним из событий C(t) и C’(t). Вероятности этих событий обозначим через p(t)  и p’(t) = 1 – p(t), а численности состояний П1С(t), П2С(t) и П2С’(t)  соответственно:  X1С(t), X 2С(t) и X 2С’(t).

Соответствующие математические ожидания обозначим как:

              (А)

Очевидно, для любого момента времени t:               (5.6)

где N – число клиентов, работающих с сервером.

Определим интенсивности потоков событий для графа (см. Рисунок 5.1). Прежде всего, по условию задачи (5.6):

                (5.7)

Из (5.7) следует:               (5.8)

Далее, программа-клиент переходит из состояния П1С(t) в состояние П2С’(t) не сама по себе, а только вместе и одновременно с сервером (когда тот зависает). Поэтому:               (5.9)

Аналогично:               (5.10)

где S – коэффициент сложности сервера по отношению к программе-клиенту.

Для остальных переходов не трудно установить соответствующие интенсивности:               (5.11)

              (5.12)

              (5.13)

Теперь можно написать дифференциальные уравнения смешанного типа, приближенно описывающие нашу систему (аргумент t для краткости записи опущен):

              (5.14)

Отметим, что, положив в (11)  все левые части 0, можно найти решение для стационарного режима, а он существует, так как система эргодическая.

Заметим, что из этой системы уравнений можно исключить два уравнения: одно из первых двух, пользуясь уравнением p + p’ = 1, и одно – из последующих трех, пользуясь соотношением (3).

Эти уравнения решаются при условии, что в начале сервер и все программы-клиенты работают: t = 0; p = 1; p’ = 0; ;               (5.15)

В случае, если важно исследовать, скажем, как быстро система восстанавливается при выходе из строя сервера, то начальные условия нужно выбрать другими: t = 0; p = 0; p’ = 1; ; ,               (5.16)

Разрешим систему уравнений (11) для конкретных функций j и y, выбрав их как приближенно описывающих процесс работы ПК типа клиент-сервер в простейшем случае.

Еще раз нарисуем 5.2 с отражением полученных результатов (формулы (4 – 9)):

Рисунок 5.2 – Утонченный граф смешанной системы

Найдем решение для следующих зависимостей  f, y, j:

- сервер «зависает» пропорционально числу клиентов работающих с ним. Интенсивность ошибок в сервере уменьшается со временем по параболическому закону () от количества исправленных в нем ошибок. l0 – первоначальная интенсивность ошибок в ПК;

- время, затрачиваемое на исправление ошибки в клиенте;

- время, затрачиваемое на исправление ошибки в сервере (y = S×f);

m0 – интенсивность исправления ошибки в ПК одним программистом;

P – число программистов, сопровождающих ПК;