Задачи оптимального резервирования компьютерных систем

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

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

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

.

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

Обычно в задачах оптимального резервирования предполагается, что стоимость резерва для системы в целом:

где – число резервных блоков в i-ой подсистеме КС;

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

где – стоимость одного блока в i-ой подсистеме КС.

При наличии одного ограничивающего фактора (стоимости) возможны постановки двух следующих задач оптимального резервирования [1, 3, 13].

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

.

2. Обратная задача. Раздельным резервированием системы, состоящей из m-резервных групп, добиться того, чтобы при максимально возможном показателе надежности системы R стоимость всего резерва не превысила заданного значения С_зад, т.е.:

,

если в качестве показателя надежности выбрать ВБР Р_с, то:

,

где С_i – стоимость одного блока в i-й подсистеме компьютера или КС;

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

C_зад – заданное значение стоимости резервных блоков машины или КС;

P_c – вероятность безотказной работы КС за время Т.

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

В более сложных случаях, когда резервные группы содержат различное число элементов, а сами элементы в различных группах различаются и по показателям надежности, и по стоимости, для определения оптимального состава резервных элементов в системе требуется использовать специальные алгоритмы решения оптимизационных задач [13, 15, 18].

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

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

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

Задача оптимизации компьютерных систем по показателю надежности заключается в таком резервировании каждой из подсистем, которое доставляет максимальную безотказность всей системы при заданных ограничениях на ее стоимость – С(m_i) ≤ С_зад, или можно найти вектор m_i, представляющий собой решение задачи:

где m_i – число резервных блоков в i-й подсистеме ВС;

С_i – стоимость одного блока в i-й подсистеме;

C_зад – заданное значение стоимости резервных блоков ВС;

P_c – вероятность безотказной работы КС за время Т.

Может быть решена и обратная задача.

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

Пусть имеем систему с нагруженным резервом, подключенным по схеме поэлементного резервирования. Каждая из n-подсистем (процессоры, ОЗУ, ПУ и др.) имеют m_i -1 резервов. Вероятность безотказной работы (ВБР) i-й подсистемы ( ) обозначается через Р_i. Тогда ВБР системы Р_с выражается как:

. (1)

Чтобы упростить формулу, допустим, что , где q_i – вероятность отказа i-й подсистемы. Тогда вероятность отказа системы Q:

, (2)

где m = (m₁, m₂,…, m_n).

Масса, габариты или стоимость системы выражается в виде линейной зависимости:

, (3)

где c_i – стоимость i-й подсистемы.

Необходимо определить min Q(m) при условии, что C(m) ≤ С_зад, где С_зад – заданное значение стоимости системы. Искомыми являются значения m_i, минимизирующие вероятность отказа Q. Поскольку Q(m) и C(m) монотонные зависимости, то условие типа неравенства может быть заменено условием типа равенства, а задача решена методом неопределенных множителей Лагранжа.

Функция Лагранжа F(m) имеет следующий вид:

, (4)

где ξ – неопределенный множитель Лагранжа.

Совместное решение необходимых условий экстремума (4):

, (5)

и условие типа равенства:

, (6)

позволяют определить n оптимальных значений m_i и соответствующее им значение неопределенного множителя ξ.

Подставляя Q(m), C(m), из (2), (3) в 4, а F(m) из (4) в (5) получим следующую систему уравнений:

, откуда, , (7)

где α_i = c_i / ln(q_i).

Для определения ξ поставим m_i, из в (6), тогда:

. (8)

В последнем выражении изменены знаки сомножителей ξ и α_i, т.е. вместо ξ и α_i написано (-ξ) и (-α_i) для того, чтобы можно было логарифмировать, так как α_i ≤ 0.

Следовательно, решение существует только в случае, когда ξ – отрицательная величина. Выражая ln(-ξ) и подставляя, получим окончательное выражение для оптимальных значений m_i:

, (9)

При второй постановке задачи решение осуществляется согласно (min(max) φ(x),

где Н – ограничение, налагаемое на показатель надежностиП(х)) на основании следующей функции Лагранжа:

,

где η – неопределенный множитель Лагранжа;

Q_зад – заданное значение вероятности отказа.

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

. (10)

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