Лекции - Надежность информационных систем
Подождите немного. Документ загружается.
Минимальное кодовое расстояние является основным параметром, характеризующим
корректирующие способности данного кода. Если код используется только для обнаружения ошибок
кратностью g
0
, то необходимо и достаточно, чтобы минимальное кодовое расстояние было равно
d
mln
≥ g
0
+ 1.000 0000000000000000000000000000000000000000000(4.11)
В этом случае никакая комбинация из g
0
ошибок не может перевести одну разрешённую кодовую
комбинацию в другую разрешённую. Таким образом, условие обнаружения всех ошибок кратностью g
0
можно записать в виде:
g
0
≤ d
min
– 1.0000000000000 0000000000000000000000000000000(4.12)
Чтобы можно было исправить все ошибки кратностью g
i
и менее, необходимо иметь минимальное
расстояние, удовлетворяющее условию:
d
min
≥ 2 ∙ g
u
+ 1.000000000000000000000000 00000000000000000(4.13)
В этом случае любая кодовая комбинация с числом ошибок g
u
отличается от каждой разрешённой
комбинации не менее чем в g
u
+ 1 позициях. Если условие (4.13) не выполнено, возможен случай, когда
ошибки кратности g исказят переданную комбинацию так, что она станет ближе к одной из разрешённых
комбинаций, чем к переданной или даже перейдёт в другую разрешённую комбинацию. В соответствии с
этим, условие исправления всех ошибок кратностью не более g
u
можно записать в виде:
g
u
≤ (d
min
– 1)/2.0000000000000000000000000000000000000000 (4.14)
Из (4.11) и (4.13) следует, что если код исправляет все ошибки кратностью g
u
, то число ошибок,
которые он может обнаружить, равно g
0
= 2 ∙ g
u
. Следует отметить, что соотношения (4.11) и (4.13)
устанавливают лишь гарантированное минимальное число обнаруживаемых или исправляемых ошибок при
заданном d
min
и не ограничивают возможность обнаружения ошибок большей кратности. Например,
простейший код с проверкой на чётность с d
min
= 2 позволяет обнаруживать не только одиночные ошибки, но
и любое нечётное число ошибок в пределах g
0
n.
При независимых ошибках полная вероятность ошибки кратности g, учитывающая все сочетания
ошибочных символов определяется выражением [8]:
,0000000000000 000000000000000000000(4.15)
где
00
;
/– вероятность искажения одного символа.
Отсюда вероятность отсутствия ошибок в кодовой комбинации, т.0е. вероятность правильного
приема равна
00 0000000000000000000000000000000000000000000(4.16)
и вероятность правильного корректирования ошибок равна
.000000000000000000000000 (4.17)
Здесь суммирование производится по всем значениям кратности ошибок g, которые
обнаруживаются и исправляются. Таким образом, вероятность некорректируемых ошибок будет равна
.00 0000(4.18)
Анализ формулы (4.18) показывает, что при малой величине P
0
/и небольших значениях n, наиболее
вероятны ошибки малой кратности, которые необходимо корректировать в первую очередь.
Вопрос о минимально необходимой избыточности, при которой код обладает нужными
корректирующими свойствами, является одним из важнейших в теории кодирования. Этот вопрос до сих пор
не получил полного решения. В настоящее время получен лишь ряд верхних и нижних оценок (границ),
которые устанавливают связь между максимально возможным минимальным расстоянием
корректирующего кода и его избыточностью.
Так, граница Плоткина даёт верхнюю границу кодового расстояния d
min
при заданном числе
разрядов n в кодовой комбинации и числе информационных разрядов k, и для двоичных кодов:
d
min
≤ (n ∙2 ∙ k – 1 ) ∕ (2 ∙ k -1)000000000000000000000000000000000 (4.19)
или
r ≥ 2 ∙ (d
min
- 1) – log
2
d
min
,0000000000000000 0000000000000000000(4.20)
при n ≥ 2 ∙ d
min
– 1.
Верхняя граница Хемминга устанавливает максимально возможное число разрешённых кодовых
комбинаций (2k) любого помехоустойчивого кода при заданных значениях n и d
min
:
,000000000000 0000000000000000000000000000(4.21)
где 0– число сочетаний из n элементов по i элементам.
Отсюда можно получить выражение для оценки числа проверочных символов:
.00000000000000000000000000000000000000 (4.22)
Для значений (d
min
/ n) ≤ 0,3 разница между границей Хемминга и границей Плоткина сравнительно
невелика.
Граница Варшамова – Гильберта для больших значений n определяет нижнюю границу для числа
проверочных разрядов, необходимого для обеспечения заданного кодового расстояния:
.00000000000000000000000000000000000000 (4.23)
Отметим, что для некоторых частных случаев Хемминг получил простые соотношения,
позволяющие определить необходимое число проверочных символов:
r ≥ log
2
(n + 1) для/ d
min
= 3;
r ≥ log
2
(2 ∙ n) для/ d
min
= 4.
Блочные коды с d
min
= 3 и 4 в литературе обычно называют кодами Хемминга.
Все приведённые выше оценки дают представление о верхней границе числа d
min
при
фиксированных значениях n и k или оценку снизу числа проверочных символов r при заданных k и d
min
.
Существующие методы построения избыточных кодов решают, в основном, задачу нахождения
такого алгоритма кодирования и декодирования, который позволял бы наиболее просто построить и
реализовать код с заданным значением d
min
. Поэтому различные корректирующие коды при одинаковых d
min
сравниваются по сложности кодирующего и декодирующего устройств. Этот критерий является, в ряде
случаев, определяющим при выборе того или иного кода.
Корректирующие коды Хемминга
Построение кодов Хемминга базируется на принципе проверки на чётность веса W (числа
единичных символов) в информационной группе кодового блока.
Поясним идею проверки на чётность на примере простейшего корректирующего кода, который так
и называется, кодом с проверкой на чётность или кодом с проверкой по паритету (равенству).
В таком коде к кодовым комбинациям безызбыточного первичного двоичного k-разрядного кода
добавляется один дополнительный разряд (символ проверки на чётность, называемый проверочным, или
контрольным). Если число символов «1» в исходной кодовой комбинации чётное, то в дополнительном
разряде формируют контрольный символ «0», а если число символов «1» нечётное, то в дополнительном
разряде формируют символ «1». В результате общее число символов «1» в любой передаваемой кодовой
комбинации всегда будет чётным.
Таким образом, правило формирования проверочного символа cводится
к следующему:
r
1
= i
1
/i
2
/. . . /i
k
,
где i – соответствующий информационный символ (0 или 1); k – общее их число, а под операцией 0
здесь и далее понимается сложение по модулю 2.
Очевидно, что добавление дополнительного разряда увеличивает общее число возможных
комбинаций вдвое по сравнению с числом комбинаций исходного первичного кода, а условие чётности
разделяет все комбинации на разрешённые и неразрешённые. Код с проверкой на чётность позволяет
обнаруживать одиночную ошибку при приёме кодовой комбинации, так как такая ошибка нарушает условие
чётности, переводя разрешённую комбинацию в запрещённую.
Критерием правильности принятой комбинации является равенство нулю результата S
суммирования по модулю 2 всех n символов кода, включая проверочный символ r
i
. При наличии одиночной
ошибки S принимает значение 1:
S = r
1
/i
1
/i
2
/. . . /i
k
= 0 – ошибки нет;
S = r
1
/i
1
/i
2
/. . . /i
k
/= 1 – однократная ошибка.
Этот код является (k + 1, k)-кодом, или (n, n - 1)-кодом. Минимальное расстояние кода равно двум
(d
min
= 2), и, следовательно, никакие ошибки не могут быть исправлены. Простой код с проверкой на
чётность может использоваться только для обнаружения (но не исправления) однократных ошибок.
Увеличивая число дополнительных проверочных разрядов и формируя по определённым правилам
проверочные символы r, равные 0 или 1, можно усилить корректирующие свойства кода так, чтобы он
позволял не только обнаруживать, но и исправлять ошибки. На этом и основано построение кодов
Хемминга. Рассмотрим эти коды, позволяющие исправлять одиночную ошибку, с помощью непосредственного
описания. Для каждого числа проверочных символов r = 3, 4, 5... существует классический код Хемминга с
маркировкой
(n, k) = (2
r
– 1, 2
r
– 1 - r),00000000000000000000000000000000000 (4.24)
т.0е. – (7,4), (15,11), (31,26).
При других значениях числа информационных символов k получаются так
называемые усечённые (укороченные) коды Хемминга. Так, для международного телеграфного кода МТК-2,
имеющего 5 информационных символов, потребуется использование корректирующего кода (9,5),
являющегося усечённым от классического кода Хемминга (15,11), так как число символов в этом коде
уменьшается (укорачивается) на 6. Для примера рассмотрим классический код Хемминга (7,4), который
можно сформировать и описать с помощью кодера, представленного на рис. 4.2.
Рис. 4.2
0
0
В простейшем варианте при заданных четырёх (k = 4) информационных символах (i
1
, i
2
, i
3
, i
4
) будем
полагать, что они сгруппированы в начале кодового слова, хотя это и не обязательно. Дополним эти
информационные символы тремя проверочными символами (r = 3), задавая их следующими равенствами
проверки на чётность, которые определяются соответствующими алгоритмами
r
1
= i
1
/i
2
/i
3;
r
2
= i
2
/i
3
/i
4;
r
3
= i
1
/i
2
/i
4,
где знак « » означает сложение по модулю 2.
На рис. 4.3 приведена схема декодера для (7,4)-кода Хемминга, на вход которого поступает кодовое
слово:
V = (i′
1
, i′
2
, i′
3
, i′
4
, r′
1
, r′
2
, r
′
3
).
Апостроф означает, что любой символ слова может быть искажён помехой в канале передачи.
Рис. 4.3
0
0
В декодере, в режиме исправления ошибок, строится последовательность:
s
1
= r
1
’/
/i
1
’
/i
2
’
/i
3
’
;
s
2
= r
2
’/
/i
2
’
/i
3
’
/i
4
’
;
s
3
= r
3
’/
/i
1
’
/i
2
’
/i
4
’
.
Трёхсимвольная последовательность (s
1
, s
2
, s
3
) называется синдромом. Термин «синдром»
используется и в медицине, где он обозначает сочетание признаков, характерных для определённого
заболевания. В данном случае синдром S = (s
1
, s
2
, s
3
) представляет собой сочетание результатов проверки на
чётность соответствующих символов кодовой группы и характеризует определённую конфигурацию
ошибок (шумовой вектор).
Кодовые слова кода Хемминга для k = 4 и r = 3 приведены в табл. 4.1.
Число возможных синдромов определяется выражением
S = 2
r
.00000000000000000000000000000000000000000000000000 (4.25)
При числе проверочных символов r = 3, имеется восемь возможных синдромов (2
3
= 8). Нулевой
синдром (000) указывает на то, что ошибки при приёме отсутствуют или не обнаружены. Всякому
ненулевому синдрому соответствует определённая конфигурация ошибок, которая и исправляется.
Классические коды Хемминга (4.20) имеют число синдромов, точно равное их необходимому числу,
позволяют исправить все однократные ошибки в любом информативном и проверочном символах и
включают один нулевой синдром. Такие коды называются плотноупакованными.
0
Таблица 4.1
k = 4 r = 3
i
1
i
2
i
3
i
4
r
1
r
2
r
3
0 0 0 0 0 0 0
0 0 0 1 0 1 1
0 0 1 0 1 1 0
0 0 1 1 1 0 1
0 1 0 0 1 1 1
0 1 0 1 1 0 0
0 1 1 0 0 0 1
0 1 1 1 0 1 0
1 0 0 0 1 0 1
1 0 0 1 1 1 0
1 0 1 0 0 1 1
1 0 1 1 0 0 0
1 1 0 0 0 1 0
1 1 0 1 0 0 1
1 1 1 1 1 0 0
1 1 1 1 1 1 1
0
Усечённые коды являются неплотноупакованными, так как число синдромов у них превышает
необходимое. Так, в коде (9,5) при четырёх проверочных символах число синдромов будет равно 2
4
= 16, в
то время как необходимо всего 10. Лишние 6 синдромов свидетельствуют о неполной упаковке кода (9,5).
Для рассматриваемого кода (7,4) в табл. 4.2 представлены ненулевые синдромы и соответствующие
конфигурации ошибок.
Таблица 4.2
Синдром
0
001
0
010
0
011
0
100
0
101
0
110
0
Конфигураци
я ошибок
0
0000001
0
0000010
0
0001000
0
0000100
0
1000000
0
0010000
0
Ошибка в
символе
0
r
3
r
2
i
4
r
1
i
1
i
0
Таким образом, код (7,4) позволяет исправить все одиночные ошибки. Простая проверка
показывает, что каждая из ошибок имеет свой единственный синдром. При этом возможно создание такого
цифрового корректора ошибок (дешифратора синдрома), который по соответствующему синдрому
исправляет соответствующий символ в принятой кодовой группе. После внесения исправления проверочные
символы r
i
можно на выход декодера не выводить. Две или более ошибки превышают возможности
корректирующего кода Хемминга, и декодер будет ошибаться. Это означает, что он будет вносить
неправильные исправления и выдавать искажённые информационные символы.
Идея построения подобного корректирующего кода, естественно, не меняется при перестановке
позиций символов в кодовых словах. Все такие варианты также называются (7,4) – кодами Хемминга.
0
Основные выводы использования корректирующих кодов
Анализируя применение кодов, контролирующих ошибки, и корректирующих кодов в
информационных системах можно сделать следующие выводы:
- можно построить такую систему связи, что вероятность ошибки при передаче данных будет
достаточно малой. При этом затраты на аппаратуру будут несоизмеримо ниже, чем затраты на создание
аппаратуры, повышающей соотношение сигнал – шум;
- применение кодов, контролирующих ошибки, и корректирующих кодов приводит к снижению
скорости передачи информации, и поэтому необходимо идти на определенный компромисс между скоростью
передачи информации и ее безошибочностью;
- выбор и применение типов кодов, контролирующих ошибки и корректирующих, зависит от
характера возникновения ошибок, их вероятности появления и существенно влияет на ценовую и
надежностную составляющую аппаратуры кодирования-декодирования.
Учитывая изложенное, можно построить информационную систему с высокими показателями
надежности передачи информации как внутри отдельных устройств системы, так и распределенной
информационной системы.
0
НАДЕЖНОСТЬ ПРОГРАММНЫХ КОМПЛЕКСОВ
Модели надежности программных комплексов
Для прогнозирования надёжности используемого программного комплекса могут применяться
различные модели надёжности. В моделях надёжности программного комплекса используется информация
о числе ошибок, вызывающих отказы, устранённые в процессе разработки программного комплекса. На
основе такой информации определяются параметры модели, которая может затем использоваться для
прогнозирования ожидаемого числа ошибок (отказов программного комплекса) или некоторого другого
показателя надёжности. Показателем надёжности программного комплекса может служить вероятность
отсутствия обнаружения программных ошибок в течение определённого промежутка времени при
эксплуатации программы в расчётном режиме в информационной системе.
Одна из моделей основана на следующих допущениях:
- общее число команд в программе на машинном языке постоянно;
- в начале компоновочных испытаний число ошибок равно некоторой постоянной величине, и по
мере исправления ошибок их становится меньше. В ходе испытаний программы новые ошибки не вносятся;
- ошибки изначально различимы, по суммарному числу исправленных ошибок можно судить об
оставшихся;
- интенсивность отказов программы пропорциональна числу остаточных ошибок.
На основе этих допущений получаем:
,000000 00000000000000000000000000000000000(5.1)
где 0t – продолжительность отладки программы, отсчитываемая от момента начала компоновки
системы программного обеспечения;
0– число остаточных ошибок в момент времени t, отнесённое к общему числу команд I;
0– отношение числа ошибок E
0
, имеющихся в программе в момент t = 0, к общему числу
команд на машинном языке I, т.0е. ;
0– суммарное число ошибок, исправленных к моменту времени t, отнесённое к общему
числу команд I.
Используя последнее допущение, имеем:
,000 000000000000000000000000000000000000000(5.2)
где /t – время работы системы;
0– интенсивность отказов в течение интервалов времени t;
K
s
– коэффициент пропорциональности,
Определив с помощью формулы (5.2) интенсивность отказов программы (частоту появления
ошибок), найдём выражение для вероятности безошибочной работы:
.0000000 000000000000(5.3)
Поскольку в данной модели частота появления ошибок считается независящей от времени t, она
принимается постоянной и, следовательно, среднее время безошибочной работы программы равно:
.000000000000000000000000000000000000 (5.4)
Для оценки параметров модели подставим соотношение (5.1) в формулу (5.4), получим следующие
выражение для среднего времени безошибочной работы:
.00000000000000000000 (5.5)
Выражение (5.5) содержит два неизвестных параметра – К
s
и Е
о
, которые можно оценить, используя
метод согласования моментов. Рассматривая два периода откладки программы t
1
и t
2
, такие, что t
1
< t
2
,
получаем:
,00 0000000000000000000000000000000000000(5.6)
,00000 000000000000000000000000000000000(5.7)
где 0t
1
и t
2
– продолжительность работы системы;
m
1
и m
2
– число ошибок в программном обеспечении, обнаруженных соответственно в периодах t
1
и
t
2
.
Из отношений (5.6) и (5.7) следует, что
,0000000000000000000000000000000000 (5.8)
где 0 ,
T
0i
– среднее время безошибочной работы, соответствующее периоду откладки программы и
определяемое как T
0i
= t
i
/ m
i
.
Заменяя отношение 0на T
1
в формуле (5.6), найдем K
s
:
.000000000 000000000000000000000000000(5.9)
Другим методом оценивания параметров E
0
и K
s
является использование оценок максимального
правдоподобия.
0
Вторая модель, как и первая, основана на допущении об экспоненциальном распределении
вероятности безошибочной работы программного комплекса.
Предполагается, что частота появления ошибок пропорциональна числу остаточных ошибок, т.0е.
,000 0000000000000000000000000(5.10)
где 0– коэффициент пропорциональности;
t – интервал времени между i-й и (i-1)-й обнаруженными ошибками.
С помощью формулы (5.10) можно найти вероятность безошибочной работы:
,0000000000000000000000000 (5.11)
и среднее время безошибочной работы:
. (5.12)
Третья модель основана на допущении о том, что частота появления ошибок пропорциональна
числу остаточных ошибок и времени отладки программы, т.0е.
,0000000000000000000000000000000000 (5.13)
где t
1
– промежуток времени между(i-1)-й и i-й ошибками.
Вероятность безошибочной работы равна:
.000000000000000000000 (5.14)
Среднее время безошибочной работы определяется по формуле:
.0 (5.15)
Существуют доводы как за, так и против принятия допущения о том, что частота появления ошибок
пропорциональна времени отладки программы.
Истинную ценность той или иной модели можно измерить по её прогнозирующей способности. В
большинстве случаев, обсуждение относительной ценности моделей обычно основывается на интуиции и
проверке логической непротиворечивости. Тот факт, что число попыток экспериментально проверить эти
модели невелико, объясняется отсутствием необходимых данных об ошибках в программах или
противоречивостью имеющихся данных.
Из всех рассмотренных моделей, наилучшие прогнозы остаточных ошибок для крупномасштабных
разработок программ или проектов с продолжительным периодом отладки даёт третья модель.
Следует иметь в виду, что, хотя это сравнительное исследование позволило получить некоторые
полезные результаты, необходимы новые исследования такого рода.
Типы отказов и сбоев при исполнении комплекса программ
Отказы и сбои, по степени их влияния на функционирование комплекса программ и на всю систему
управления в целом, делятся на несколько крупных групп:
- искажения вычислительного процесса и данных, вызывающие полное прекращение выполнения
функций системой управления на длительное или неопределённое время;
- отказ, в значительной степени обесценивающий результаты предыдущего функционирования;
- искажения, кратковременно прерывающие функционирование системы
и мало искажающие накопленные данные и выдаваемые результаты;
- частичный отказ или длительный сбой, в некоторой степени, обесценивающий предыдущие
результаты;
- искажения кратковременные и малоотражающиеся на вычислительном процессе и
обрабатываемых данных;
- сбои, практически не обесценивающие результаты функционирования комплекса программ.
В зависимости от глубины контроля и длительности запаздывания в обнаружении отказа, а также в
зависимости от качества средств, осуществляющих восстановление, одни и те же ситуации искажений могут
быть отнесены к разным типам отказов или сбоев. Наиболее типичными полными отказами при
функционировании сложных комплексов программ являются:
- зацикливание, т.0е. последовательное, повторяющееся исполнение группы команд, которое не
прекращается без внешнего вмешательства, блокируя функционирование всех остальных программ данного
комплекса;
- остановка ЭВМ и полное прекращение решения функциональных задач, при этом может
сохраниться возможность приёма и выдачи информации и выполнения некоторых функций, стимулируемых
прерываниями;
- значительное искажение или полная потеря накопленных данных о состоянии внешних абонентов
и процессе их функционирования;
- прекращение или недопустимое снижение темпа решения некоторых задач, пропуск или потеря
необработанных групп сообщений вследствие перезагрузки ЭВМ.
Эти отказы существенно влияют на выполнение основных функций комплексом программ. В
несколько меньшей степени, на вычислительный процесс и обрабатываемые данные влияют искажения,
приводящие к следующим типам частичных отказов или длительных сбоев:
- искажения заданной последовательности вызова подпрограмм, приводящие к пропуску
исполнения отдельных подпрограмм или их частей, что приводит, в свою очередь, к неправильному или
неполному решению некоторых задач и к искажению выходных данных;
- использование и обработка искажённых исходных данных, отражающиеся на логике решения
задач и приводящие к искажению отдельных накопленных и выдаваемых данных.
Эти типы искажений заключаются в кратковременном нарушении нормального вычислительного
процесса, либо в искажении исходных, промежуточных или результирующих данных. В зависимости от
повторяемости и глубины распространения, искажения квалифицируются как частичные отказы, либо как
отказы с длительными последствиями.
В наименьшей степени на надёжность функционирования информационных систем влияют сбои,
которые незначительно искажают общие результаты. Не нарушая практически логики функционирования
комплекса программ, такие сбои искажают преимущественно отдельные обрабатываемые и
результирующие данные. При поступлении аналогичных данных, в последующие моменты времени можно
ликвидировать последствия сбоев, не проводя специальных восстановительных работ.
Основные факторы, влияющие на надежность функционирования комплекса
программ
Одни и те же типы сбоев и отказов при исполнении комплексов программ могут быть вызваны
различными факторами, которые можно разделить на три группы. В первую группу входят факторы,
непосредственно вызывающие сбой или отказ при исполнении программы, причинами которых могут быть:
- искажение исходной информации, поступающей от внешних абонентов,
в том числе, и ошибочные действия операторов;
- самоустраняющиеся отказы или сбои в вычислительной системе;
- невыявленные ошибки в комплексе программ.
Ко второй группе факторов относятся архитектура комплекса программ
и структурное построение его компонент. Структура программ определяет возможность расширения
последствий искажений информации или вычислительного процесса, влияет на вероятность превращения
искажения в отказ и на время восстановления после отказа.
Третья группа факторов влияет на длительность восстановления и глубину последствий от
возникающих отказов. В эту группу входят факторы, определяющие качество контроля вычислительного
процесса и обрабатываемых данных, запаздывание в обнаружении искажений, качество классификации
искажений и длительность проявлений их последствий. Они определяют длительность восстановления,
время наработки на отказ и способствуют быстрой локализации искажений.
Искажения исходной информации, в большинстве случаев, не влияют на надежность выполнения
программ. Причинами искажений данных, поступающих от внешних абонентов, могут быть:
- искажение данных на первичных носителях информации;
- сбои и частичные отказы в аппаратуре ввода данных с первичных носителей информации;
- шумы и сбои в каналах связи при передаче или приёме телекодовой информации;
- потери или искажения сообщений в ограниченных буферных накопителях вычислительной
системы;
- ошибки в документах, используемых для подготовки данных, вводимых
в вычислительную систему.
Самоустраняющиеся отказы и сбои в аппаратуре вычислительных систем являются фактором,
существенно влияющим на надёжность функционирования комплексов программ. Значительно чаще
происходят сбои или трудно обнаруживаемые кратковременные отказы. Большинство из них выявляется и
устраняется средствами аппаратурного контроля и не влияет на исполнение программ. Однако, некоторая
часть аппаратурных сбоев может приводить к искажениям переменных. Причинами таких сбоев и отказов
являются преимущественно внешние воздействия на аппаратуру, влияющие на нарушение контактов и
пропадание сигналов, или индустриальные электрические помехи. Чаще происходят сбои, которые не
удаётся обнаружить и зафиксировать при функционировании комплекса программ в процессе нормальной
обработки информации и управления. Такие сбои проявляются в случайные промежутки времени, и
практически невозможно добиться их повторяемости.
Невыявленные ошибки являются основной причиной ненадёжности функционирования. В процессе
отладки основная часть ошибок в программах обнаруживается и устраняется, но есть риск пропуска
нескольких ошибок. Любая отладка «может показать наличие ошибок, но не может показать их отсутствие».
В процессе тестирования и отладки программ практически невозможно выполнение абсолютно полных
проверок. В результате в программах всегда существует некоторое количество невыявленных ошибок.
Обеспечение надежности и повышение качества программ
Моделирование является лишь одним аспектом обеспечения надёжности программных комплексов
и имеет цель – прогнозирование числа ошибок, остающихся в системе, на основе использования
статической информации о процессе обнаружения и устранения ошибок. Не менее важное значение имеют
две другие области обеспечения надёжности программных средств, безошибочное проектирование и
испытания, ориентированные на обеспечение надёжности.
Вероятно, самым лучшим способом получить надёжное программное обеспечение является
сведение к минимуму числа ошибок и их последствий
в ходе разработки комплекса программ. Однако не существует какого-либо проверенного способа создания
надёжного программного обеспечения. Отсутствует пока и какая-либо теоретическая основа методики
разработки безошибочных программ. Тем не менее, по общему мнению, существует целый ряд методов
разработки программ и управления этим процессом, которые позволяют создавать надёжные программы. К
этим методам, обычно, относится структурное программирование и некоторые, связанные с ним приёмы.
Идея структурного (модульного) программирования базируется на стремлении упорядочить
сложные комплексы программ и их проектирование. Строгое определение термина «структурное
программирование» не существует. Имеется несколько определений структурного (модульного)
программирования. Чаще всего оно определяется как программирование без использования операторов GO
TO, с применением нисходящего метода разработки программ и с использованием принципа модульного
конструирования программ. Указанные три приёма повышают надёжность, удобочитаемость и удобство
обслуживания программного обеспечения.
Программирование без использования операторов GO TO. Сам по себе оператор безусловного
перехода не приводит к ошибкам. Однако передача управления с помощью этого оператора может вызвать
усложнение логической схемы программы и сделать её трудночитаемой. Наоборот, исключение операторов
GO TO позволяет получить более понятную и удобочитаемую программу. Кроме того, программу, не
содержащую операторов безусловного перехода, легче проверить.
Нисходящее программирование. По существу, имеется два способа составления программ: снизу
вверх и сверху вниз. Классическим способом составления большинства программ является движение снизу
вверх. При таком подходе руководитель группы программистов рассматривает проект в целом,
формулирует цели системы, а затем определяет элементы, необходимые для системы программного
обеспечения. Задаются средства сопряжения, и отдельные части программы распределяются между
программистами. Каждый программист отвечает за проверку своей подсистемы или модуля до момента
объединения последних в единую систему. Интеграция модулей в систему выполняется последовательно по
уровням и поручается самому квалифицированному из авторов стыкуемых программ. Такой подход к
составлению программ аналогичен способу разработки аппаратного оборудования.
Более надёжные программные комплексы позволяет получить «нисходящее» программирование. В
этом случае руководитель группы программистов не только осуществляет контроль над работой, но и
участвует в составлении программ.
Модульное конструирование программ. Обычно при составлении сложной программы её
разбивают на отдельные модули так, что каждый из них может использоваться во многих других. Но при
этом увеличивается вероятность возникновения всякого рода недоразумений и ошибок. Этот источник
ошибок можно свести к минимуму, если вход в каждый модуль будет осуществляться только в его начало
(сверху), а выход только в его конец (снизу).
Структурирование данных. Неотъемлемой компонентой0 комплексов программ являются данные,
которые поступают на обработку, преобразуются, хранятся и выдаются внешним абонентам.
Структурирование данных способствует уменьшению сложности комплекса программ и снижает
вероятность появления ошибок из-за неправильного использования. В ряде систем сложность массивов
данных превышает логическую0 сложность программ и обуславливает основную массу ошибок, выявляемых
в процессе отладки. Поэтому большое значение при проектировании программ имеет строгое описание
переменных и простота структурного построения массивов.
Всю совокупность данных можно разделить на два иерархических уровня: простые переменные и
массивы. Простые переменные представляют собой минимальную компоненту данных, имеющую имя и
описание. Массивы образуются из нескольких простых переменных по некоторым правилам объединения и
упорядочивания и имеют собственное описание, структуру и имя. Основными символами для описания
данных являются буквы, цифры и ограничители. Наиболее часто используются следующие типы
переменных:
- вещественные, принимающие действительные положительные и отрицательные значения в
заданных пределах;
- целые, в заданных интервалах принимающие только целые положительные и отрицательные
численные значения;
- булевы, принимающие только два значения: да или нет (истина или ложь);
- двоичные, представляющие собой последовательность бит;
- символьные, образующиеся из последовательности байтовых кодов, каждый из которых
соответствует некоторому символу языка программирования или описания данных.
Из простых переменных по заданным правилам упорядочения образуются массивы, размеры
которых задаются списками граничных пар. Структура массивов и правила упорядочения переменных
различны и определяются следующими факторами:
- типами и структурой простых переменных, а также областью значений, которые могут принимать
переменные;
- мощностью массива – наибольшим числом значений, которые могут принимать переменные, а
также объемом памяти, необходимым для хранения массива в любой момент времени;
- способом заполнения и уплотнения переменных в памяти, используемой для хранения массива;
- методом и частотой заполнения и выборочного обновления компонентов массива и затратами
производительности ЭВМ, необходимыми для обращения к массиву;
- типом реальной памяти, используемой для хранения массива.
Для повышения надёжности комплексов программ целесообразно использовать простейшие
структуры массивов. При работе с массивами наибольшие затраты производительности ЭВМ связаны с
поиском простых переменных или частных массивов, признаки которых удовлетворяют некоторому
условию.
Тестирование и испытание программ
Вполне вероятно, что даже при использовании самых лучших способов программирования,
программные комплексы всё же будут содержать те или иные ошибки. Целью испытаний программы
является подтверждение того, что она соответствует проектным замыслам. Любая корректировка
программы может быть сведена к трём типовым операциям:
- исключение части или всей подпрограммы;
- вставка компонент или новой целой подпрограммы на имеющееся свободное место;
- замена части или всей подпрограммы в пределах освобождающегося свободного места или с
расширением программы и использованием дополнительной памяти.
Необходимые исправления вводятся в текст программы, программа перетранслируется и повторно
тестируется данными. После подтверждения правильности выполненной корректировки продолжается
отладка по новым тестам, либо программа передаётся на эксплуатацию. В больших комплексах программ
внесение изменений усложняется и требует проведения дополнительных работ. Роль дополнительных работ
возрастает, когда комплекс программ отлажен и проводятся завершающие стадии проверок.
Экспериментальный анализ выполненных при этом корректировок показывает, что около 30% внесённых
изменений являются неправильными и не устраняют ошибку, либо вносят новую ошибку в программу. Эти
новые ошибки трудно обнаружить, так как их последствия не проявляются на тестах повторяющихся
проверок и связаны
с функционированием комплекса программ в иных режимах. Поэтому при корректировке программ
необходимы дополнительные работы по анализу возможных последствий внесённых изменений.
Средства проверки состоят из двух основных модулей: инструментального модуля и анализатора.
Исходная программа испытуемого модуля вначале поступает в инструментальный модуль, который
снабжает проверяемый модуль дополнительными операторами. Эти операторы называются датчиками и
счётчиками, а сам процесс введения указанных операторов носит название инструментального оснащения. В
процессе инструментального оснащения исходной программы её функции должны оставаться неизменными,
т.0е. оператор-датчик и оператор-счётчик не должны менять функционального назначения программы.
Снабжёнными дополнительными операторами блок программы транслируется обычным способом, а