КРИТЕРИИ ОПТИМАЛЬНОСТИ МНОГОУРОВНЕВЫХ ОТКАЗОУСТОЙЧИВЫХ КОМПЬЮТЕРНЫХ СИСТЕМ
КРИТЕРИИ ОПТИМАЛЬНОСТИ МНОГОУРОВНЕВЫХ ОТКАЗОУСТОЙЧИВЫХ КОМПЬЮТЕРНЫХ СИСТЕМ
7 КОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 681.3
КРИТЕРИИ ОПТИМАЛЬНОСТИ МНОГОУРОВНЕВЫХ ОТКАЗОУСТОЙЧИВЫХ КОМПЬЮТЕРНЫХ СИСТЕМ
В.А. Богатырев, С.В. Богатырев
Рассмотрены варианты формирования частных и обобщенных критериев при решении задачи векторной оптимизации многоуровневых компьютерных систем с учетом надежности, времени обработки запросов и стоимости реализации системы. Показана возможность применения коэффициента сохранения эффективности в качестве объективного обобщенного критерия векторной оптимальности. Ключевые слова: надежность, отказоустойчивость, векторная оптимизация, критерий оптимальности, коэффициент сохранения эффективности.
Введение Проектирование отказоустойчивых компьютерных систем связано с решением задачи оптимального резервирования. При многоуровневой структуре компьютерных систем задача оптимизации сводится к определению кратности резервирования узлов каждого уровня, при котором эффективность системы максимальна, а затраты на ее реализацию не превышают допустимого предела. Результат оптимизации во многом зависит от выбора критерия эффективности, формируемого с учетом требований по надежности, производительности (времени ожидания) и стоимости системы. В связи с этим рассматриваются варианты формирования частных и обобщенных критериев эффективности многоуровневых компьютерных систем. Актуальность выбора объекта оптимизации обусловливается тем, что в настоящее время многоуровневая организация широко используется в компьютерных системах, в том числе кластерной архитектуры (рис. 1).
Рис. 1. Многоуровневая компьютерная система
92 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2009, № 5(63)
В.А. Богатырев, С.В. Богатырев
Постановка задачи оптимизации
В качестве объекта оптимизации рассмотрим вычислительную систему, в которой
выделены М уровней. Требуется найти число (кратность резервирования) узлов на каж-
дом уровне (m1, m2,..., mM ) , при котором обеспечивается максимум надежности систе-
мы, минимум среднего времени пребывания запросов в системе, а стоимость реализа-
ции системы не превышает выделенных средств:
M
∑P(m1, m2 ,..., mM ) → max при T (m1, m2 ,..., mM ) → min , C(m1, m2 ,..., mM ) = mi ≤ C0 . i =1
Возможна также другая постановка задачи. Требуется найти число узлов на каж-
дом уровне, при котором обеспечивается минимум стоимости реализации:
C(m1, m2 ,..., mM ) → min при P(m1, m2 ,..., mM ) ≥ P0 , T (m1, m2 ,..., mM ) ≤ T0 .
При этом Т0, P0, C0 – предельно допустимые значения среднего времени ожидания, надежности и стоимости системы. При оптимизации будем считать заданными интен-
сивность входного потока запросов λ, показатели надежности узлов p1, p2, p3, ..., pM и
средние времена выполнения запросов узлами каждого уровня v1, v2, v3, ..., vM .
Рассматриваемая задача оптимизации является векторной, и ее сложность обуслов-
лена тем, что одно решение (альтернатива) может превосходить другую по одним пока-
зателям и уступать по другим. В задачах принятия решений по векторному показателю
главное внимание уделяется выработке решающего правила, основанного на компромис-
се между значениями компонент векторного показателя. Таким образом, проблема при-
нятия решений по векторному показателю сопряжена с поиском концептуально обосно-
ванного критерия выбора наилучшего решения, который для отказоустойчивых систем
должен характеризовать эффективность процесса деградации системы при накоплении
отказов. Формальное определение обобщенного критерия в виде аддитивной или муль-
типликативной свертки показателей надежности и производительности не отражает воз-
можную потерю производительности по мере накопления отказов и дает завышенный
результат, что может привести к необоснованному выбору структуры системы.
Для многоуровневых отказоустойчивых систем с возможностью накопления отка-
зов узлов различных уровней и с образованием работоспособных состояний системы с
разным уровнем ее эффективности искомый комплексный показатель будем искать в
виде математического ожидания эффективности (производительности) с учетом веро-
ятностей всех работоспособных состояний в форме
m1 m2 m3
mM
∑ ∑ ∑ ∑K *(m1, m2, m3,..., mM ,δ ) =
... E(k1, k2 , k3,..., kM )P(k1, k2 , k3,..., kM , δ) ,
k1 =1 k2 =1 k3 =1 kM =1
где δ – условие работоспособности состояний системы, которое может зависеть от
предельно допустимого среднего времени пребывания запросов в системе δ(T0 ) ;
E(k1, k2, k3,..., kM ) = 1/ T (k1, k2 , k3,..., kM ) характеризует эффективность состояния при ис-
правности k1, k2 , k3,..., kM узлов на соответствующих уровнях системы. Для систем с де-
градацией потерю эффективности относительно исходного состояния (при исправности
всех m1, m2, m3,..., mM узлов системы) можно охарактеризовать выражением
E(k1, k2 , k3,..., kM ) = T (m1, m2 , m3,..., mM ) / T (k1, k2 , k3,..., kM ) .
Решение задач векторной оптимизации
Известны различные подходы к решению задач векторной оптимизации [1]: − методы скалярной свертки на основе аддитивного критерия, мультипликативного
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 5(63)
93
КРИТЕРИИ ОПТИМАЛЬНОСТИ МНОГОУРОВНЕВЫХ ОТКАЗОУСТОЙЧИВЫХ КОМПЬЮТЕРНЫХ СИСТЕМ
критерия, отклонения от идеала;
− методы, основанные на ранжировании критериев, в том числе метод главного критерия, лексикографическая оптимизация, метод последовательной уступки;
− методы, основанные на использовании функции полезности;
− минимаксные методы. Перечисленные методы являются эвристическими и не исключают субъекти-
визм лица принимающего решение (ЛПР). Субъективность методов может привести к выбору не лучшего решения. В связи с этим целесообразна разработка объективного результирующего показателя эффективности, устанавливаемого на основе анализа назначения проектируемой системы, качество которой может характеризоваться единым показателем, зависимым от частных показателей. Сложность получения такого показателя сопряжена с тем, что требуется точно представлять назначение системы как составной части надсистемы и необходимы знания зависимости обобщенного показателя от частных. Как правило, результирующий показатель должен иметь некоторый физический смысл, подтверждающий соответствие системы ее функциональному назначению с позиции надсистемы [2].
Частные показатели качества системы
Возможности системы по обработке запросов определим по среднему времени
пребывания запросов в системе. В простейшем случае каждый узел представим систе-
мой массового обслуживания типа M/M/1. Считая, что каждый запрос последовательно
обслуживается одним из исправных узлов на каждом уровне системы, среднее время
∑пребывания
запросов
в
системе
оценим
как
T (m1, m2 , m3,...mM ) =
M vi i=1 1 − viλ
mi
,
где
(m1, m2 , m3,..., mM ) – число узлов на каждом уровне. Надежность системы оценим по вероятности сохранения работоспособности, ко-
торая зависит от формулировки условия отказа (сохранения функционирования Y).
Если система работоспособна, когда исправен хотя бы один узел на каждом уров-
не, то вероятность работоспособности системы определяется по формуле
M
∏P (m1 , m 2 , m3 , ..., m M ) = (1 − (1 − pi ) mi ), где pi – вероятность работоспособности i =1
узла, находящегося на i-м уровне системы.
Если система работоспособна, когда запрос обслуживается за время, не превосхо-
дящее заданный предельный уровень (ограничение на допустимое время выполнения
запросов), то надежность системы оценим как
m1 m2 m3
mM
∑ ∑ ∑ ∑P(m1, m2 , m3,..., mM ) =
...
δ(k1, k2 , k3,..., kM
)C C C ...Ck1 k2 k3 m1 m2 m3
kM mM
×
k1 =1 k2 =1 k3 =1 kM =1
×
p k1 1
p k2 2
p3k3 ... pM kM
(1 −
p1 )m1−k1 (1 −
p2 )m2 −k2 (1 −
p3
)m3 −k3 ...(1 −
pM )mM −kM ,
где
C ki mi
= mi !
ki !(mi
− ki )!
,
а
δ(k1,
k2
,
k3
,
...,
kM
)
=
⎧⎪1, ⎪⎩⎨0,
if if
T (k1, k2 , k3,..., kM ) ≤ T0 , T (k1, k2 , k3,..., kM ) > T0.
Здесь δ(k1, k2, k3,..., kM ) – условие работоспособности состояний системы при ог-
раничении на допустимое время выполнения запросов T0, а T (k1, k2, k3,..., kM ) – среднее
время пребывания запросов в системе при исправности k1, k2 , k3,..., kM узлов соответствующих уровней. При особых требованиях к времени реакции (реальный масштаб вре-
94 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2009, № 5(63)
В.А. Богатырев, С.В. Богатырев
мени) в качестве условия работоспособности состояний δ(k1, k2, k3,..., kM ) может использоваться вероятность непревышения времени реакции (пребывания запросов в системе) за предельное время T0.
Сравним результаты расчета надежности с учетом ограничений на время пребывания запросов в системе. Для трехуровневой системы (М=3) будем считать p1 = p2 = p3 = 0,9 , m1 = m2 = m3 = 4 шт., v1 = 1 c, v2 = 2 c, v3 = 1 c . Зависимость надежности P(T0) от предельно допустимого среднего времени пребывания запросов в системе T0 приведена на рис. 2, на котором кривая 1 соответствует значению интенсивности входного потока λ=1,3 1/с, а кривая 2 – λ=1,7 1/с.
Рис. 2. Надежность системы с учетом предельного времени пребывания запросов
Формирование скалярного критерия
Скалярная свертка, используемая при решении задач векторной оптимизации, со-
ставляется формально на основе субъективных предпочтений ЛПР, и часто ее физиче-
ский смысл не просматривается. В качестве скалярной свертки обычно используют
мультипликативный и аддитивный критерии, определяемые для рассматриваемых сис-
тем как
M
(m1, m2 ,..., mM
)
=
P(m1, m2 ,..., mM )α1 T (m1, m2 ,..., mM )α2
,
A(m1,
m2,...,
mM
)
=
α1P(m1,
m2
,...,
mM
)
+α2
T(m1,
T0 m2,...,
mM
)
,
где коэффициенты α1, α2 учитывают субъективную оценку ЛПР важности частных
критериев, причем α1 + α2 = 1 (стоимость учитывается как ограничение).
Показатели сохранения эффективности
Эффективность каждого работоспособного состояния оценим величиной, обрат-
ной среднему времени пребывания запросов в системе при прохождении запроса через
узлы каждого уровня:
m1
∑ ∑ ∑ ∑ [ ]K * (m1, m2 , m3 ,..., mM ) =
m2
m3 mM
...
1 / T (k1, k2 , k3 ,..., kM )
C C C ...Ck1 k2 k3 m1 m2 m3
kM mM
×
k1 =1 k2 =1 k3 =1 kM =1
×
p k1 1
p k2 2
p k3 3
... pM
kM
(1 −
p1 )m1 −k1 (1 −
p2 )m2 −k2 (1 −
p3
)m3 −k3 ...(1 −
pM )mM −kM .
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 5(63)
95
КРИТЕРИИ ОПТИМАЛЬНОСТИ МНОГОУРОВНЕВЫХ ОТКАЗОУСТОЙЧИВЫХ КОМПЬЮТЕРНЫХ СИСТЕМ
Оценивая каждое работоспособное состояние отношением его эффективности относительно эффективности исходного состояния системы (когда все узлы исправны), коэффициент сохранения эффективности определим как математическое ожидание:
∑ ∑ ∑ ∑K (m1, m2 , m3,..., mM
)
=
m1 k1 =1
m2 k2 =1
m3 k3 =1
mM
...
kM =1
⎡ ⎢ ⎣
T( T
m1, m2 (k1, k2
, ,
m3 ,..., mM k3,..., kM )
)
⎤ ⎥ ⎦
C
k1 m1
C k2 m2
C
k3 m3
...CmkMM
×
×
p k1 1
p k2 2
p3k3 ... pM kM
(1 −
p1 )m1 −k1 (1 −
p2 )m2 −k2 (1 −
p3
)m3 −k3 ...(1 −
pM )mM −kM .
Коэффициент сохранения эффективности с учетом условия выполнения запроса
за время, не превышающее T0 , вычислим как
∑∑∑ ∑K(m1,m2,m3,...,mM
)
=
m1 m2 m3 mM
... δ(k1,k2,...,kM
k1=1 k2 =1 k3=1 kM =1
)
⎢⎣⎡TT((mk11,,mk22,,......,,kmMM))
⎤ ⎥ ⎦
C Ck1 k2 m1 m2
Ck3 m3
...CmkMM
×
×p1k1
p k2 2
p k3 3
...
pM
kM
(1−
p1)m1−k1 (1−
p2)m2−k2 (1−
p3
)m3−k3 ...(1−
p )mM −kM M
.
Зависимость коэффициента сохранения эффективности K(T0) от предельно допус-
тимого времени пребывания запросов в системе T0 приведена на рис 3, где кривая 1 со-
ответствует интенсивности входного потока λ = 1,8 1/с, а кривая 2 – λ = 1,5 1/с.. Расчет
проведен при М=3, p1 = p2 = p3 = 0,9 , m1 = m2 = m3 = 4 шт., v1 = 1 c, v2 = 2 c, v3 = 1 c .
Рис. 3. Зависимость коэффициента сохранения эффективности K(T0) от предельно допустимого времени пребывания запросов в системе T0
Результаты оптимизации
Проведем оптимизацию трехуровневой компьютерной системы по критерию максимума коэффициента сохранения эффективности, а также по максимуму аддитивного и мультипликативного критериев. Будем считать заданными С = (450, 150, 450) у.е., С0 = 6000 у.е., V = (1, 4, 1) c, T0 = 80 c. Результаты оптимизации сведены в таблицу. Для каждого варианта исходных данных определено распределение числа узлов на каждом уровне, которое обеспечивает соответственно максимум коэффициента сохранения эффективности, аддитивного и мультипликативного критерия при ограничении расходов на реализацию системы С0. Оценены потенциальные потери D значения коэффициента сохранения эффективности при нахождении оптимального числа узлов на каждом уровне m1, m2, m3 по максимуму аддитивного и мультипликативного критериев.
Анализ полученных данных позволяет сделать вывод о влиянии выбора критерия на результат принятия решения по построению многоуровневых компьютерных систем. При этом предпочтительно использование коэффициента сохранения эффективности, объективно отражающего требования системы по обеспечению производительности системы даже в условиях деградации производительности вследствие отказов.
96 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2009, № 5(63)
В.А. Богатырев, С.В. Богатырев
λ, Критерий
P=(0,9; 0,95; 0,9)
P=(0,8; 0,95; 0,9)
1/c m1, m2 , m3 , шт. К (m1, m2 , m3 ) ,D m1, m2 , m3 , шт. К (m1, m2 , m3 ) , D
1,45 Аддитивный 3,19,4
K=0,89928
4,19,3
K=0,85679811
D=0,0365
D=0,059073881
Мультиплика- 4,19,3
K=0,89928
4,19,3
K=0,856798
тивный
D=0,0365
D=0,0590738
Сохранения
5,13,4
K=0,93578
5,13,4
K=0,91587199
эффективности
D=0
D=0
0,45 Аддитивный 3,22,3
K=0,9821
3,22,3
K=0,96700
D=0,0057
D=0,016971
Мультиплика- 3,22,3
K=0,9821
4,19,3
K=0,978363
тивный
D=0,0057
D=0,00561
Сохранения
4,16,16
K=0,9879
5,13,4
K=0,983976
эффективности
D=0
D=0
Таблица. Результаты оптимизации
Таким образом, показано, что при векторной оптимизации с учетом надежности, производительности и стоимости целесообразно использование обобщенного критерия на основе коэффициента сохранения эффективности. Из таблицы видна неточность решения на основе аддитивного и мультипликативного критериев (не учитывающих, что работоспособные состояния могут характеризоваться разным качеством функционирования). Следовательно, скалярные критерии мультипликативного и аддитивного типа могут использоваться при приближенном решении задачи оптимизации.
Заключение
Рассмотрены варианты формирования частных и обобщенных критериев при решении задачи векторной оптимизации многоуровневых компьютерных систем с учетом их стоимости, надежности и времени обработки запросов. Показана целесообразность применения при решении задач векторной оптимизации многоуровневых компьютерных систем критерия на основе коэффициента сохранения эффективности, учитывающего накопление отказов узлов различных уровней и наличие работоспособных состояний системы с разным уровнем эффективности (с разным средним временем пребывания запросов в системе). Оценена разница определения оптимального числа узлов на каждом уровне (кратность резервирования) при использовании в качестве целевой функции рассматриваемого критерия на основе коэффициента сохранения эффективности, а также на основе мультипликативного и аддитивного критериев.
Результаты исследований могут использоваться при проектировании и обосновании выбора многоуровневых высоконадежных компьютерных систем, в том числе кластерной архитектуры.
Литература
1. Черноруцкий И.Г. Методы принятия решений. – СПб: БХВ, 2005. – 408 с. 2. Гуткин Л.С. Оптимизация радиоэлектронных устройств по совокупности показате-
лей качества. – М.: Сов. радио, 1975. – 368 с.
Богатырев Владимир – Санкт-Петербургский государственный университет информационных
Анатольевич
технологий, механики и оптики, доктор технических наук, профессор,
bva@tinuviel.ru
Богатырев Станислав – Санкт-Петербургский государственный университет информационных
Владимирович
технологий, механики и оптики, аспирант, realloc@gmail.com
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 5(63)
97
7 КОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 681.3
КРИТЕРИИ ОПТИМАЛЬНОСТИ МНОГОУРОВНЕВЫХ ОТКАЗОУСТОЙЧИВЫХ КОМПЬЮТЕРНЫХ СИСТЕМ
В.А. Богатырев, С.В. Богатырев
Рассмотрены варианты формирования частных и обобщенных критериев при решении задачи векторной оптимизации многоуровневых компьютерных систем с учетом надежности, времени обработки запросов и стоимости реализации системы. Показана возможность применения коэффициента сохранения эффективности в качестве объективного обобщенного критерия векторной оптимальности. Ключевые слова: надежность, отказоустойчивость, векторная оптимизация, критерий оптимальности, коэффициент сохранения эффективности.
Введение Проектирование отказоустойчивых компьютерных систем связано с решением задачи оптимального резервирования. При многоуровневой структуре компьютерных систем задача оптимизации сводится к определению кратности резервирования узлов каждого уровня, при котором эффективность системы максимальна, а затраты на ее реализацию не превышают допустимого предела. Результат оптимизации во многом зависит от выбора критерия эффективности, формируемого с учетом требований по надежности, производительности (времени ожидания) и стоимости системы. В связи с этим рассматриваются варианты формирования частных и обобщенных критериев эффективности многоуровневых компьютерных систем. Актуальность выбора объекта оптимизации обусловливается тем, что в настоящее время многоуровневая организация широко используется в компьютерных системах, в том числе кластерной архитектуры (рис. 1).
Рис. 1. Многоуровневая компьютерная система
92 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2009, № 5(63)
В.А. Богатырев, С.В. Богатырев
Постановка задачи оптимизации
В качестве объекта оптимизации рассмотрим вычислительную систему, в которой
выделены М уровней. Требуется найти число (кратность резервирования) узлов на каж-
дом уровне (m1, m2,..., mM ) , при котором обеспечивается максимум надежности систе-
мы, минимум среднего времени пребывания запросов в системе, а стоимость реализа-
ции системы не превышает выделенных средств:
M
∑P(m1, m2 ,..., mM ) → max при T (m1, m2 ,..., mM ) → min , C(m1, m2 ,..., mM ) = mi ≤ C0 . i =1
Возможна также другая постановка задачи. Требуется найти число узлов на каж-
дом уровне, при котором обеспечивается минимум стоимости реализации:
C(m1, m2 ,..., mM ) → min при P(m1, m2 ,..., mM ) ≥ P0 , T (m1, m2 ,..., mM ) ≤ T0 .
При этом Т0, P0, C0 – предельно допустимые значения среднего времени ожидания, надежности и стоимости системы. При оптимизации будем считать заданными интен-
сивность входного потока запросов λ, показатели надежности узлов p1, p2, p3, ..., pM и
средние времена выполнения запросов узлами каждого уровня v1, v2, v3, ..., vM .
Рассматриваемая задача оптимизации является векторной, и ее сложность обуслов-
лена тем, что одно решение (альтернатива) может превосходить другую по одним пока-
зателям и уступать по другим. В задачах принятия решений по векторному показателю
главное внимание уделяется выработке решающего правила, основанного на компромис-
се между значениями компонент векторного показателя. Таким образом, проблема при-
нятия решений по векторному показателю сопряжена с поиском концептуально обосно-
ванного критерия выбора наилучшего решения, который для отказоустойчивых систем
должен характеризовать эффективность процесса деградации системы при накоплении
отказов. Формальное определение обобщенного критерия в виде аддитивной или муль-
типликативной свертки показателей надежности и производительности не отражает воз-
можную потерю производительности по мере накопления отказов и дает завышенный
результат, что может привести к необоснованному выбору структуры системы.
Для многоуровневых отказоустойчивых систем с возможностью накопления отка-
зов узлов различных уровней и с образованием работоспособных состояний системы с
разным уровнем ее эффективности искомый комплексный показатель будем искать в
виде математического ожидания эффективности (производительности) с учетом веро-
ятностей всех работоспособных состояний в форме
m1 m2 m3
mM
∑ ∑ ∑ ∑K *(m1, m2, m3,..., mM ,δ ) =
... E(k1, k2 , k3,..., kM )P(k1, k2 , k3,..., kM , δ) ,
k1 =1 k2 =1 k3 =1 kM =1
где δ – условие работоспособности состояний системы, которое может зависеть от
предельно допустимого среднего времени пребывания запросов в системе δ(T0 ) ;
E(k1, k2, k3,..., kM ) = 1/ T (k1, k2 , k3,..., kM ) характеризует эффективность состояния при ис-
правности k1, k2 , k3,..., kM узлов на соответствующих уровнях системы. Для систем с де-
градацией потерю эффективности относительно исходного состояния (при исправности
всех m1, m2, m3,..., mM узлов системы) можно охарактеризовать выражением
E(k1, k2 , k3,..., kM ) = T (m1, m2 , m3,..., mM ) / T (k1, k2 , k3,..., kM ) .
Решение задач векторной оптимизации
Известны различные подходы к решению задач векторной оптимизации [1]: − методы скалярной свертки на основе аддитивного критерия, мультипликативного
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 5(63)
93
КРИТЕРИИ ОПТИМАЛЬНОСТИ МНОГОУРОВНЕВЫХ ОТКАЗОУСТОЙЧИВЫХ КОМПЬЮТЕРНЫХ СИСТЕМ
критерия, отклонения от идеала;
− методы, основанные на ранжировании критериев, в том числе метод главного критерия, лексикографическая оптимизация, метод последовательной уступки;
− методы, основанные на использовании функции полезности;
− минимаксные методы. Перечисленные методы являются эвристическими и не исключают субъекти-
визм лица принимающего решение (ЛПР). Субъективность методов может привести к выбору не лучшего решения. В связи с этим целесообразна разработка объективного результирующего показателя эффективности, устанавливаемого на основе анализа назначения проектируемой системы, качество которой может характеризоваться единым показателем, зависимым от частных показателей. Сложность получения такого показателя сопряжена с тем, что требуется точно представлять назначение системы как составной части надсистемы и необходимы знания зависимости обобщенного показателя от частных. Как правило, результирующий показатель должен иметь некоторый физический смысл, подтверждающий соответствие системы ее функциональному назначению с позиции надсистемы [2].
Частные показатели качества системы
Возможности системы по обработке запросов определим по среднему времени
пребывания запросов в системе. В простейшем случае каждый узел представим систе-
мой массового обслуживания типа M/M/1. Считая, что каждый запрос последовательно
обслуживается одним из исправных узлов на каждом уровне системы, среднее время
∑пребывания
запросов
в
системе
оценим
как
T (m1, m2 , m3,...mM ) =
M vi i=1 1 − viλ
mi
,
где
(m1, m2 , m3,..., mM ) – число узлов на каждом уровне. Надежность системы оценим по вероятности сохранения работоспособности, ко-
торая зависит от формулировки условия отказа (сохранения функционирования Y).
Если система работоспособна, когда исправен хотя бы один узел на каждом уров-
не, то вероятность работоспособности системы определяется по формуле
M
∏P (m1 , m 2 , m3 , ..., m M ) = (1 − (1 − pi ) mi ), где pi – вероятность работоспособности i =1
узла, находящегося на i-м уровне системы.
Если система работоспособна, когда запрос обслуживается за время, не превосхо-
дящее заданный предельный уровень (ограничение на допустимое время выполнения
запросов), то надежность системы оценим как
m1 m2 m3
mM
∑ ∑ ∑ ∑P(m1, m2 , m3,..., mM ) =
...
δ(k1, k2 , k3,..., kM
)C C C ...Ck1 k2 k3 m1 m2 m3
kM mM
×
k1 =1 k2 =1 k3 =1 kM =1
×
p k1 1
p k2 2
p3k3 ... pM kM
(1 −
p1 )m1−k1 (1 −
p2 )m2 −k2 (1 −
p3
)m3 −k3 ...(1 −
pM )mM −kM ,
где
C ki mi
= mi !
ki !(mi
− ki )!
,
а
δ(k1,
k2
,
k3
,
...,
kM
)
=
⎧⎪1, ⎪⎩⎨0,
if if
T (k1, k2 , k3,..., kM ) ≤ T0 , T (k1, k2 , k3,..., kM ) > T0.
Здесь δ(k1, k2, k3,..., kM ) – условие работоспособности состояний системы при ог-
раничении на допустимое время выполнения запросов T0, а T (k1, k2, k3,..., kM ) – среднее
время пребывания запросов в системе при исправности k1, k2 , k3,..., kM узлов соответствующих уровней. При особых требованиях к времени реакции (реальный масштаб вре-
94 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2009, № 5(63)
В.А. Богатырев, С.В. Богатырев
мени) в качестве условия работоспособности состояний δ(k1, k2, k3,..., kM ) может использоваться вероятность непревышения времени реакции (пребывания запросов в системе) за предельное время T0.
Сравним результаты расчета надежности с учетом ограничений на время пребывания запросов в системе. Для трехуровневой системы (М=3) будем считать p1 = p2 = p3 = 0,9 , m1 = m2 = m3 = 4 шт., v1 = 1 c, v2 = 2 c, v3 = 1 c . Зависимость надежности P(T0) от предельно допустимого среднего времени пребывания запросов в системе T0 приведена на рис. 2, на котором кривая 1 соответствует значению интенсивности входного потока λ=1,3 1/с, а кривая 2 – λ=1,7 1/с.
Рис. 2. Надежность системы с учетом предельного времени пребывания запросов
Формирование скалярного критерия
Скалярная свертка, используемая при решении задач векторной оптимизации, со-
ставляется формально на основе субъективных предпочтений ЛПР, и часто ее физиче-
ский смысл не просматривается. В качестве скалярной свертки обычно используют
мультипликативный и аддитивный критерии, определяемые для рассматриваемых сис-
тем как
M
(m1, m2 ,..., mM
)
=
P(m1, m2 ,..., mM )α1 T (m1, m2 ,..., mM )α2
,
A(m1,
m2,...,
mM
)
=
α1P(m1,
m2
,...,
mM
)
+α2
T(m1,
T0 m2,...,
mM
)
,
где коэффициенты α1, α2 учитывают субъективную оценку ЛПР важности частных
критериев, причем α1 + α2 = 1 (стоимость учитывается как ограничение).
Показатели сохранения эффективности
Эффективность каждого работоспособного состояния оценим величиной, обрат-
ной среднему времени пребывания запросов в системе при прохождении запроса через
узлы каждого уровня:
m1
∑ ∑ ∑ ∑ [ ]K * (m1, m2 , m3 ,..., mM ) =
m2
m3 mM
...
1 / T (k1, k2 , k3 ,..., kM )
C C C ...Ck1 k2 k3 m1 m2 m3
kM mM
×
k1 =1 k2 =1 k3 =1 kM =1
×
p k1 1
p k2 2
p k3 3
... pM
kM
(1 −
p1 )m1 −k1 (1 −
p2 )m2 −k2 (1 −
p3
)m3 −k3 ...(1 −
pM )mM −kM .
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 5(63)
95
КРИТЕРИИ ОПТИМАЛЬНОСТИ МНОГОУРОВНЕВЫХ ОТКАЗОУСТОЙЧИВЫХ КОМПЬЮТЕРНЫХ СИСТЕМ
Оценивая каждое работоспособное состояние отношением его эффективности относительно эффективности исходного состояния системы (когда все узлы исправны), коэффициент сохранения эффективности определим как математическое ожидание:
∑ ∑ ∑ ∑K (m1, m2 , m3,..., mM
)
=
m1 k1 =1
m2 k2 =1
m3 k3 =1
mM
...
kM =1
⎡ ⎢ ⎣
T( T
m1, m2 (k1, k2
, ,
m3 ,..., mM k3,..., kM )
)
⎤ ⎥ ⎦
C
k1 m1
C k2 m2
C
k3 m3
...CmkMM
×
×
p k1 1
p k2 2
p3k3 ... pM kM
(1 −
p1 )m1 −k1 (1 −
p2 )m2 −k2 (1 −
p3
)m3 −k3 ...(1 −
pM )mM −kM .
Коэффициент сохранения эффективности с учетом условия выполнения запроса
за время, не превышающее T0 , вычислим как
∑∑∑ ∑K(m1,m2,m3,...,mM
)
=
m1 m2 m3 mM
... δ(k1,k2,...,kM
k1=1 k2 =1 k3=1 kM =1
)
⎢⎣⎡TT((mk11,,mk22,,......,,kmMM))
⎤ ⎥ ⎦
C Ck1 k2 m1 m2
Ck3 m3
...CmkMM
×
×p1k1
p k2 2
p k3 3
...
pM
kM
(1−
p1)m1−k1 (1−
p2)m2−k2 (1−
p3
)m3−k3 ...(1−
p )mM −kM M
.
Зависимость коэффициента сохранения эффективности K(T0) от предельно допус-
тимого времени пребывания запросов в системе T0 приведена на рис 3, где кривая 1 со-
ответствует интенсивности входного потока λ = 1,8 1/с, а кривая 2 – λ = 1,5 1/с.. Расчет
проведен при М=3, p1 = p2 = p3 = 0,9 , m1 = m2 = m3 = 4 шт., v1 = 1 c, v2 = 2 c, v3 = 1 c .
Рис. 3. Зависимость коэффициента сохранения эффективности K(T0) от предельно допустимого времени пребывания запросов в системе T0
Результаты оптимизации
Проведем оптимизацию трехуровневой компьютерной системы по критерию максимума коэффициента сохранения эффективности, а также по максимуму аддитивного и мультипликативного критериев. Будем считать заданными С = (450, 150, 450) у.е., С0 = 6000 у.е., V = (1, 4, 1) c, T0 = 80 c. Результаты оптимизации сведены в таблицу. Для каждого варианта исходных данных определено распределение числа узлов на каждом уровне, которое обеспечивает соответственно максимум коэффициента сохранения эффективности, аддитивного и мультипликативного критерия при ограничении расходов на реализацию системы С0. Оценены потенциальные потери D значения коэффициента сохранения эффективности при нахождении оптимального числа узлов на каждом уровне m1, m2, m3 по максимуму аддитивного и мультипликативного критериев.
Анализ полученных данных позволяет сделать вывод о влиянии выбора критерия на результат принятия решения по построению многоуровневых компьютерных систем. При этом предпочтительно использование коэффициента сохранения эффективности, объективно отражающего требования системы по обеспечению производительности системы даже в условиях деградации производительности вследствие отказов.
96 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2009, № 5(63)
В.А. Богатырев, С.В. Богатырев
λ, Критерий
P=(0,9; 0,95; 0,9)
P=(0,8; 0,95; 0,9)
1/c m1, m2 , m3 , шт. К (m1, m2 , m3 ) ,D m1, m2 , m3 , шт. К (m1, m2 , m3 ) , D
1,45 Аддитивный 3,19,4
K=0,89928
4,19,3
K=0,85679811
D=0,0365
D=0,059073881
Мультиплика- 4,19,3
K=0,89928
4,19,3
K=0,856798
тивный
D=0,0365
D=0,0590738
Сохранения
5,13,4
K=0,93578
5,13,4
K=0,91587199
эффективности
D=0
D=0
0,45 Аддитивный 3,22,3
K=0,9821
3,22,3
K=0,96700
D=0,0057
D=0,016971
Мультиплика- 3,22,3
K=0,9821
4,19,3
K=0,978363
тивный
D=0,0057
D=0,00561
Сохранения
4,16,16
K=0,9879
5,13,4
K=0,983976
эффективности
D=0
D=0
Таблица. Результаты оптимизации
Таким образом, показано, что при векторной оптимизации с учетом надежности, производительности и стоимости целесообразно использование обобщенного критерия на основе коэффициента сохранения эффективности. Из таблицы видна неточность решения на основе аддитивного и мультипликативного критериев (не учитывающих, что работоспособные состояния могут характеризоваться разным качеством функционирования). Следовательно, скалярные критерии мультипликативного и аддитивного типа могут использоваться при приближенном решении задачи оптимизации.
Заключение
Рассмотрены варианты формирования частных и обобщенных критериев при решении задачи векторной оптимизации многоуровневых компьютерных систем с учетом их стоимости, надежности и времени обработки запросов. Показана целесообразность применения при решении задач векторной оптимизации многоуровневых компьютерных систем критерия на основе коэффициента сохранения эффективности, учитывающего накопление отказов узлов различных уровней и наличие работоспособных состояний системы с разным уровнем эффективности (с разным средним временем пребывания запросов в системе). Оценена разница определения оптимального числа узлов на каждом уровне (кратность резервирования) при использовании в качестве целевой функции рассматриваемого критерия на основе коэффициента сохранения эффективности, а также на основе мультипликативного и аддитивного критериев.
Результаты исследований могут использоваться при проектировании и обосновании выбора многоуровневых высоконадежных компьютерных систем, в том числе кластерной архитектуры.
Литература
1. Черноруцкий И.Г. Методы принятия решений. – СПб: БХВ, 2005. – 408 с. 2. Гуткин Л.С. Оптимизация радиоэлектронных устройств по совокупности показате-
лей качества. – М.: Сов. радио, 1975. – 368 с.
Богатырев Владимир – Санкт-Петербургский государственный университет информационных
Анатольевич
технологий, механики и оптики, доктор технических наук, профессор,
bva@tinuviel.ru
Богатырев Станислав – Санкт-Петербургский государственный университет информационных
Владимирович
технологий, механики и оптики, аспирант, realloc@gmail.com
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2009, № 5(63)
97