8 / 13
Г.П. Можаров
48
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6
неисправности
F
, если алгоритм
A
выполним
.
F
КСС
Компьютерная система
является толерантной относительно множества алгоритмов
1 2
,
, ...,
p
A A A
и мно-
жества неисправностей
1 2
, , ...,
,
q
F F F
если алгоритм
i
A
выполним
КСС
j
F
при
всех
i
и
j
,
1
,
i p
1
;
j q
КСС является
s
-толерантной относительно алгорит-
мов
1 2
,
, ...,
,
p
A A A
если при любой
s
-кратной неисправности
F
в КСС, алгорит-
мы
i
A
выполнимы
,
F
КСС
1
i p
[2, 6, 12].
Рис. 1.
Сеть, основанная на BIB-дизайне,
с параметрами (
n
= 7,
b
= 7,
r
=
k
=3,
= 1):
b
1
= {1, 2, 4},
b
2
= {2, 3, 5},
b
3
= {3, 4, 6},
b
4
=
= {4, 5, 7},
b
5
= {5, 6, 1},
b
6
= {6, 7, 2},
b
7
= {7, 1, 3}
Рис. 2.
Сеть, основанная на блок-дизайне,
с параметрами (
n
= 9,
b
= 12,
r
=
k
= 3,
=1):
b
1
= {1, 2, 3},
b
2
= {4, 5, 6},
b
3
= {7, 8, 9},
b
4
=
= {1, 4, 7},
b
5
= {2, 5, 8},
b
6
= {3, 6, 9},
b
7
= {1, 5, 9},
b
8
= {2, 6, 7},
b
9
= {3, 4, 8},
b
10
= {1, 6, 8},
b
11
=
= {2, 4, 9},
b
12
= {3, 5, 7}
В данной модели исследования отказоустойчивости неявно предполагается,
что в КСС имеется некоторое заведомо исправное ядро, которое выполняет функ-
ции обнаружения и локализации неисправностей, реконфигурации и восстановле-
ния информации. Поэтому при оценке толерантности КСС относительно целевого
алгоритма
A
учитываются только следующие два момента: содержит ли
КСС
F
все необходимые ресурсы, необходимые для выполнения алгоритма
A
и достаточ-
ны ли связи между ресурсами в
КСС
F
для его исполнения.
Сначала рассмотрим отказ линии связи между любыми двумя процессора-
ми в КСС (cм. рис. 1, 2). Прежде всего, число процессоров, которым необходимо
сообщить об отказе линии связи и изменении маршрута передачи сообщения,
ограничено лишь теми
k
3
k
процессорами, на маршруте которых находит-
ся отказавшая связь. Когда процессор получает сообщение о том, что линия
связи отказала, он передает его по произвольно выбранной исправной линии
связи одному из соседних процессоров.
Использование подобного алгоритма маршрутизации ограничивает сбои,
которые могут происходить в сетях при переключении некоторых процессоров
на новый алгоритм маршрутизации, в то время как оставшиеся процессоры все
еще используют старый алгоритм.