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

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

Методы имитационного моделирования

Целью данной работы является разработка многоуровневых аналитических и аналитико-имитационных моделей анализа вероятностно-временных характеристик переработки информации в МВК АСОД с учетом отказов в условиях информационной, структурной и временной избыточности для автоматизации определения показателей качества функционирования МВК при многовариантном анализе различных схем обработки информации с учетом надежности.

При разработке математического аппарата исследования многоуровневых моделей решаются задачи:

- декомпозиции многоуровневых формализованных моделей;

- разработки математических моделей функционирования ресурсов МВК с учетом отказов, отвечающие требованиям параметрической настраиваемости;

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

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

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

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

Взаимодействия между аппаратными и программными ресурсами МВК в процессе обработки заявок сводятся к двум видам. Первый вид взаимодействия – передача заявок на обработку от ресурса к ресурсу, то есть взаимодействие через информационные потоки. Второй вид взаимодействия проявляется в изменении параметров законов обработки информации в отдельных ресурсах. Такие взаимодействия возникают при комплексировании ЭВМ с помощью адаптеров «канал-канал» и двухвходовых устройств управления внешними устройствами. Методы структурной декомпозиции, позволяют представить многомашинный ВК в виде совокупности подструктур, каждая из которых описывает структуру отдельной ЭВМ, входящей в МВК. Структурная декомпозиция основана на принципе корректировки функций распределения времени выполнения требований обрабатывающих программ на аппаратном уровне. При корректировке учитывается дополнительная задержка начала обслуживания требования, обусловленная обслуживанием требований альтернативного канала другой ЭВМ. Отметим, что методы структурной декомпозиции остаются в силе и при формализации процесса обработки с учётом отказов, если комплексирование осуществляется на уровне внешних устройств. Однако в этом случае при определении вероятности того, что устройство комплексирования занято обслуживанием заявки альтернативного канала, необходимо учитывать дополнительные потоки, обусловленные отказами другой ЗВМ. Отметим, что при случайном характере запросов на обмен информацией , где – стационарная загрузка устройства комплексирования заявками альтернативного канала. Необходимость структурной декомпозиции возникает в режиме распределения задач. Метод структурной декомпозиции в условиях отказов описывается следующей процедурой:

1. Осуществить декомпозицию МВК на подструктуры в условиях надёжной работы, пользуясь соотношением настройки:

(1)

где – преобразование Лапласа-Стильтьеса (ПЛС) функции распределения (ФР) времени обмена;

– ПЛС ФР времени дообслуживания заявки альтернативного канала.

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

3. Осуществить корректировку моментов  с помощью соотношения (1), используя значение , определенное в пункте 2.

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

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

Интенсивность потока требований обрабатывающих программ к процессору и каналам определяется соотношениями:

(2)

где  – интенсивность потока заявок j-го типа;

 – число обращений i-ой программы к процессору при обработке j-ой заявки;

 – число обращений i-ой программы к каналу ввода-вывода при обработке j-ой заявки.

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

(3)

где  – ПЛС ФР времени выполнения требований i-ой программы в процессоре;

 – в канале.

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

- задачи преобразования многофазных СМО с ненадёжными ОА в эквивалентные многофазные СМО с надёжными ОА;

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

- задачи исследования возможности декомпозиции модели проблемного уровня на элементарные базисные модели {М/G/1} на основе допущения о пуассоновском характере потоков на проблемном уровне.

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

Время обмена в канале определяется соотношениями:

(4)

где  – моменты ФР времени поиска информации на ВУ;

 – моменты ФР объема обмениваемой информации;

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

Моменты времени обработки требований в процессоре определяются выражением:

(5)

где – 1-ый и 2-ой моменты числа команд, выполняемых процессором при обработке требований i-ой программы;

– производительность процессора;

– коэффициент замедления производительности процессора.

Замедление производительности процессора при обработке команд обусловлено ожиданием запросов процессора к блокам оперативной памяти из-за конфликтов с каналами.

– 1.002 - 1.02 для различных типов ЭВМ. Поэтому при практическом использовании многоуровневых моделей можно принять и не рассматривать командный уровень обработки заявок.

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

Модели и алгоритмы учёта сбоев рассмотрены в работах

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

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

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

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

(6)

где  – ФР времени обработки j-го сообщения с учетом отказов аппаратуры;

 – вероятность того, что во время обработки j-го сообщения не произойдет программных отказов.

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

(7)

где  – интенсивность программных отказов при выполнении i-ой обрабатывающей программы;

 – ФР времени обработки j-го сообщения i-ой программой в однопрограммном режиме.

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

(8)

где – коэффициент пропорциональности;

– первоначальное количество программных ошибок;

– число ошибок, обнаруженных при тестировании.

Плотность вероятности для интервалов времени между ошибками, обнаруженными при тестировании , для кусочно-экспоненциальной модели определяется выражением:

(9)

Соотношение (9) справедливо в том случае, если при устранении обнаруженных ошибок в программное обеспечение не вносят новые ошибки

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

(10)

Заменив в (10) дискретный параметр непрерывным и приравняв частные производные по и нулю, получим:

(11)

(12)

где .

Из (11) и (12) следует:

(13)

Уравнение (13) можно решить относительно численными методами. Корень уравнения принадлежит интервалу , где и целочисленные величины: . Разность правой и левой частей уравнения (13) меняет знак при переходе от к , где сколько угодно малая величина.

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

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

Вероятность того, что во время обработки j-го сообщения i-ой программой не произойдет отказ внешних устройств, используемых i-ой программой, определяется соотношением:

(14)

где  – ФР времени пребывания i-ой заявки в процессоре;

– ФР времени пребывания i-ой заявки в канале.

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

(15)

Здесь  – интенсивность потока заявок j-го типа, поступающих на обработку в ВК.

(16)

Соотношения (14) ÷ (16) служат для настройки модели структурного уровня. Отметим, что при определении загрузки процессора и каналов необходимо учитывать дополнительные потоки, обусловленные отказами других типов , что легко сделать, заменив в выражениях (14) – (15)  на .

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

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

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

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

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

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

Преобразование Лапласа-Стильтьеса функции распределения времени обработки i–го сообщения j–ым ОА проблемного уровня с учетом отказов определяется следующим соотношением:

(17)

где – функция распределения времени обработки j–го сообщения i–ой программой (моменты ФР определяются с помощью модели структурного уровня);

– ФР времени восстановления поле отказов.

Выражение (17) можно легко получить, воспользовавшись методом катастроф

(18)

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

(19)

Параметры  и  следующим образом связаны с первыми двумя моментами функции распределения :

(20)

Отметим, что преобразование Лапласа-Стильтьеса гамма–распределения определяется выражением:

(21)

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

(22)

Используя соотношения (19) и (22), получим следующее выражение для :

(23)

Дифференцируя (23) по s и произведя соответствующие выкладки, получим следующие соотношения для моментов функции распределения :

(24)

(25)

(26)

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

(27)

Выражения (27) совпадают с известными соотношениями для  и  при

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

(28)

где  и  – производные по z производящей функции при z = 1.

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

и – моменты ФР времени обработки заявки в ОА. В установившемся режиме  и  определяются выражениями:

(29)

где  – интенсивность поступления в систему заявок j–го типа;

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

Из (28) и (29), учитывая, что , получим следующие выражения для первых двух моментов дополнительного времени ожидания:

(30)

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

Как показано в работах

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

Вероятность того, что во время обработки j–ой заявки i–ым ОА проблемного уровня не произойдет отказ равна:

(31)

Зная значение , легко определить вероятность того, что во время обработки заявки произойдет ровно n отказов:

(32)

В работе

(33)

(34)

(35)

(36)

Преобразование Лапласа-Стильтьеса условной функции распределения времени обработки заявки  при условии, что произошло n отказов определяется выражением:

(37)

Аппроксимирующее распределение для имеет вид:

(38)

где – гамма-распределение, аппроксимирующее условную ФР .

Моменты  определяются путем дифференцирования (37) по с использованием соотношений (34) и (36). Параметры аппроксимирующего распределения определяются из выражений (22).

Параметр  определяется из условий нормировки:

(39)

 – гамма распределение, параметры которого определяются из условий равенства первых двух моментов соответствующим моментам результирующего аппроксимирующего распределения (38). Отметим, что если точность аппроксимации недостаточна, в результирующее распределение следует добавить член  и т.д.

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

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

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

Рассмотренные выше модели явились основой для разработки системы автоматизации проектирования МВК информационно-аналитических центров на базе многоуровневых аналитических и аналитико-имитационных моделей