Методика выбора контрольных точек при решении функциональных задач

Одним из путей построения надежных вычислительных комплексов (ВК) является введение резервирования на различных уровнях и организация рационального процесса обработки информации. В вычислительных системах (ВС) автоматизированной обработки данных могут происходить сбои и отказы, обесценивающие полученные результаты. Поэтому возникает необходимость запоминания промежуточных результатов в устройствах, где информация хорошо защищена от разрушения [1, 2, 3, 4]. В работах [5, 6] показано, что разбиение задания на этапы с запоминанием промежуточных результатов приводит не только к повышению производительности системы, но и к существенному повышению эффективности временного резервирования. Наиболее эффективная борьба с отказами осуществляется при использовании комплексных мер, в частности, таких, как одновременное использование резервирования системы и организации контрольных точек. В таких условиях возникает задача рационального выбора контрольных точек в ВС с резервированием. Вопросам выбора контрольных точек посвящен целый ряд работ [7, 8, 9, 10, 11, 12, 13, 14], однако в них не рассматриваются важные с практической точки зрения вопросы организации контрольных точек в вычислительных системах со структурной избыточностью.

Определение ФР времени восстановления системы при возникновении отказов

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

Fom(t) = -A- F , ( t ) + A- FA t ) ,                            (1)

^ + ^ 2       ^ + ^ 2

где   ^ - интенсивность отказов процессора и оперативной памяти;

^ - интенсивность отказов одного из эквивалентных параллельных элементов, описывающих периферийную часть ВС;

F1(t)  – ФР времени восстановления системы после отказов процессора и оперативной памяти;

F2(t) - ФР времени восстановления после отказов одного из эквивалентных параллельных элементов периферийной части ВС.

Пусть при решении задачи наступают отказы, разрушающие информацию с интенсивностью Х_от = X_{om t} + 2_om2 и сбои с интенсивностью

X

сб *

Длительность восстановления системы после отказов и сбоев случайные величины с конечными средними F^ uF®. Управление процессом решения задачи состоит в том, что в любой момент времени выполнения задачи может быть принято решение об остановке процесса наработки для запоминания промежуточных результатов, полученных к этому моменту. Длительность запоминания - случайная величина с конечным средним ф *

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

Вывод функциональных уравнений для оценки времени решения задачи с контрольными точками

Пусть задача уровня В делится на n сегментов b , b ,..., b_n ( В= j^b, ), i = 1

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

Используя метод катастроф, легко получить функциональные уравнения для преобразования Лапласа–Стильтьеса функции распределения времени выполнения сегмента с учетом отказов и сбоев (2)*

ПКS ) = exp { - b , Л „ + S + Л» - Л,F 6 ( S ) ]} + ----  ^        x

^Л от ⁺ S ^{+ Л} сб - ^Л сб ^Fc6 ⁽ S )

^(1 -exp { - b , [ Л -т. + s + Л .б - Л .б Р Сб ( S ) ]} . О * , ( S ) • «^ S )                   (2)

CO

Действительно, n * ( S ) = J e ^- s d n ( t ) есть вероятность того, что во время 0

выполнения к -го сегмента катастрофы не наступят.

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

J exp [- (Л-. + S + Л„ — Лс F» (S)>(b,)dt = exp [- bR (Л-,, + S + Лб - Лсб F* (S))], где   5(bK) - дельта функция.

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

( 1 - exp ^[- b , ( Л от + S + X„ - ^Л ,б F- б ( S )) •            ^{Л -т}

^Л от ⁺ S ^{+ Л} сб - ^Л сб ^Ьсб ⁽ S )

Во время восстановления системы после отказа катастрофы не наступили

f O                     ^

J e - “ dF -т ( t ) = F -т ( S )

1 0                        J

и во время обработки сегмента после

восстановления системы катастрофы не наступили ( 7 * ( S ) ) .

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

Преобразование Лапласа-Стильтьеса ФР времени выполнения задачи уровня В определяется из очевидного соотношения (3).

л",А S ) = П П к ( S ) ( ?•( S ) ) " ^{- 1}

К = 1

Моменты ФР времени выполнения задачи уровня В , имеющей n сегментов, легко определяются дифференцированием по S выражений (2) и (3).

Управление   процессом   запоминания   промежуточныхрезультатов

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

M B = nH \®PW / n) - ^{1 ] + (} n - ^X> ,

Лот где   H = 1 + ЛотFT + Л.,F> .

Для определения оптимального числа контрольных точек необходимо выбрать такое целое n, при котором значение М В минимально.

Данная задача имеет единственное решение.

Результаты исследования (расчетов) [15] показывают, что оптимальное число контрольных точек несущественно зависит от организации обеспечения функционирования технических средств при отказах и от использования резервирования системы.

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

nopt = LxJ x = (B -

Ф X  Л от (1 + Л ₁₆ FS )

-------------ТТГ ) *   ------------=----------

1 + Л ., F ®  \|       2 ф

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

Заключение

Разбиение задачи на этапы с запоминанием промежуточных результатов приводит к уменьшению дисперсии времени выполнения и к увеличению вероятности ее отработки в заданные директивные сроки.

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

• 1.    Для задачи заданного уровня определяется оптимальное число контрольных точек (целевая функция определяется выражением (4)).

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

• 3.    При удовлетворении ограничений процедура заканчивается, в противном случае число контрольных точек увеличивается на 1 и осуществляется переход к пункту 2.

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