Лабораторная работа №4
.pdfСанкт-Петербургский Государственный Электротехнический Университет
(ЛЭТИ)
кафедра МО ЭВМ
Отчет по лабораторной работе №4
Оценка параметров надежности программ по временным моделям обнаружения ошибок
Выполнил студент группы 1382, ФКТИ |
Пухкал И. |
Санкт-Петербург 2006
1 Постановка задачи |
2 |
1. Постановка задачи
Выполнить исследование показателей надежности программ, характеризуемых моделью обнаружения ошибок Джелинского-Моранды для различных законов распределения времени между соседними отказами и различного числа используемых для анализа данных. Для проведения исследования требуется:
1.Сгенерировать массивы данных {Хi}, где Xi — длительность интервала времени между обнаружением (i − 1)-ой и i-ой ошибок (i [1, 30]), в соответствии с:
• равномерным законом распределения в интервале [0, 20]; при
этом cреднее время между ошибками будет E = 10, σ = 20 = 5.8.
√
2 3
• экспоненциальным законом распределения (E = 10, σ = 10)
W(y) = be−by , y ≥ 0, b = 0.1
•релеевским законом распределения ((E = 8 π/2, σ = 8 2 − π/2))
|
y |
y2 |
||
W (y) = |
|
e− |
2c2 |
, y ≥ 0, c = 8 |
c2 |
2.Для каждого из 3-х массивов {Хi} оценить значение первоначального числа ошибок в программе B. При этом для каждого закона использовать 100%, 80% и 60% входных данных (то есть в массивах {Х i} использовать 30, 24 и 18 элементов). Кроме того, если B > n, оценить
значения средних времен Xj , j = n + 1, n + 2 . . . , n + k до обнаружения k ≤ 5 следующих ошибок.
Модель Джелинского-Моранды основана на следующих предположени-
ях:
1.Интенсивность обнаружения ошибок R(t) пропорциональна текущему количеству ошибок в программе, то есть изначальному количеству ошибок за вычетом количества ошибок, уже обнаруженных на данный момент.
2.Все ошибки в программе равновероятны и не зависят друг от друга.
3.Все ошибки имеют одинаковую степень важности.
4.Время до следующего отказа программы распределено экспоненциально.
5.Исправление ошибок происходит без внесения в программу новых ошибок.
6.R(t) = const в промежутке между любыми двумя соседними моментами обнаружения ошибок.
2 Выполнение работы |
3 |
Согласно этим предположениям, функция риска будет представлена как:
R(t) = K(B − (i − 1))
В этой формуле t — это произвольный момент времени между обнаружением (i −1)-й и i-й ошибок; K — неизвестный коэффициент масштабирования; B — начальное количество оставшихся в программе ошибок (также неизвестное). Таким образом, если в течении времени t было обнаружено (i − 1) ошибок, это означает, что в программе еще остается B − (i − 1) необнаруженных ошибок.
2. Выполнение работы
2.1. Переход от равномерного закона распределения
К экспоненциальному
Если ti (0, 1] — очередное значение процесса, подчиняющегося равномерному закону распределения, то для получения значения процесса, подчиняющегося экспоненциальному закону (zi)
ti
zi = λe−λx dx = −e−λx t0i = −e−λti + 1
0
ti = −λ1 ln (zi − 1)
К релеевскому
Если ti (0, 1] — очередное значение процесса, подчиняющегося равномерному закону распределения, то для получения значения процесса, подчиняющегося экспоненциальному закону (zi)
ti |
|
2 |
|
2 |
ti |
|
t2 |
|
|
zi = |
c2 e− |
dx = −e− |
= −e− |
+ 1 |
|||||
2c2 |
2c2 |
0 |
2c2 |
||||||
|
x |
x |
|
x |
|
|
i |
|
0
ti = c −2ln(1 − zi)
2.2.Оценка первоначального числа ошибок в программе
2.2.1. 100 %
Порядок определен так: слева направо, построчно. Левый верхний угол — первое значение, правый нижний — последнее.
2 Выполнение работы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
||||||||||
Равномерное распределение |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1,0 |
1,0 |
1,0 |
|
2,0 |
|
2,0 |
|
2,0 |
|
|
|
|
|
|
|
|
|
|
||||||||
3,0 |
3,0 |
4,0 |
|
5,0 |
|
7,0 |
|
7,0 |
|
|
|
|
|
|
|
|
|
|
||||||||
8,0 |
8,0 |
8,0 |
|
9,0 |
|
9,0 |
|
9,0 |
|
|
|
|
|
|
|
|
|
|
||||||||
9,0 |
9,0 |
10,0 |
|
11,0 |
|
13,0 |
|
13,0 |
|
|
|
|
|
|
|
|
|
|
||||||||
13,0 |
13,0 |
15,0 |
|
16,0 |
|
17,0 |
|
17,0 |
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
n = 30; |
n + 1 |
|
= 15, 5 |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
in |
2 |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
A = |
|
|
|
|
|
= 20, 64 > 15, 5 |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
n=1(iXi) |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
i=1(Xi) |
|
|
|
|
|
|
|
|
|
|
|
|||
Рассмотрим функции fn(m) и gn(m, A) (m > n). |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
1 |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
fn(m) = |
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
m i |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i=1 |
− |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
gn(m, A) = |
|
|
n |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
m − A |
|
|||||||||||||
|
m |
fm |
|
gm(A) |
|
|fm − gm(A)| |
|
|
|
|
|
|
|
|
|
|
||||||||||
|
31 |
|
3,99 |
|
2,89 |
|
|
|
|
1,1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
32 |
|
3,03 |
|
2,64 |
|
|
|
|
0,39 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
33 |
|
2,56 |
|
2,43 |
|
|
|
|
0,13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
34 |
|
2,26 |
|
2,24 |
|
|
|
|
0,01 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
35 |
|
2,03 |
|
2,09 |
|
|
|
|
0,05 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Наименьшая разность (0,01) достигается при значении m = 34. |
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
ˆ |
= 33 ошибок |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
B |
|
|||||||||||||
|
|
|
|
|
|
ˆ |
= |
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
= 0, 010 |
|||
|
|
|
|
|
|
K |
(Bˆ + 1) xi − i · xi |
|
Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:
ˆ |
= |
1 |
≈ 34 дней |
|
Xn+1 |
|
ˆ ˆ |
||
|
|
K(B − n) |
|
И время до полного завершения тестирования:
|
1 |
4 |
1 |
|
ttst = |
|
i=1 |
|
≈ 185 дней |
Kˆ |
i |
Таким же образом можно определить время до обнаружения (n+2)-й и так далее ошибок. Сведем эти данные в таблицу.
Номер ошибки |
Через дней |
31 |
34 |
32 |
50 |
33 |
101 |
2 Выполнение работы |
|
5 |
||||
Экспоненциальное распределение |
|
|
||||
|
|
|
|
|
|
|
0,51 |
0,51 |
0,51 |
1,05 |
1,05 |
1,05 |
|
1,63 |
1,63 |
2,23 |
2,88 |
4,31 |
4,31 |
|
5,11 |
5,11 |
5,11 |
5,98 |
5,98 |
5,98 |
|
5,98 |
5,98 |
6,93 |
7,99 |
10,5 |
10,5 |
|
10,5 |
10,5 |
13,86 |
16,09 |
18,97 |
18,97 |
|
A = 22, 11 > 15, 5
Рассмотрим функции fn(m) и gn(m, A) (m > n).
m fm |
gm(A) |
|fm − gm(A)| |
|
31 |
3,99 |
3,37 |
0,62 |
32 |
3,03 |
3,03 |
0,01 |
33 |
2,56 |
2,75 |
0,2 |
Наименьшая разность (0,01) достигается при значении m = 32.
ˆ = 31 ошибок
B
ˆ = 0 018
K ,
Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:
ˆ |
= 57 дней |
Xn+1 |
И время до полного завершения тестирования:
ttst = 57 дней Больше ошибок по модели не ожидается.
Рэлеевское распределение |
|
|
|||
|
|
|
|
|
|
2,56 |
2,56 |
2,56 |
3,67 |
3,67 |
3,67 |
4,56 |
4,56 |
5,34 |
6,07 |
7,43 |
7,43 |
8,09 |
8,09 |
8,09 |
8,75 |
8,75 |
8,75 |
8,75 |
8,75 |
9,42 |
10,11 |
11,59 |
11,59 |
11,59 |
11,59 |
13,32 |
14,35 |
15,58 |
15,58 |
A = 19, 38 > 15, 5
Рассмотрим функции fn(m) и gn(m, A) (m > n).
m fm |
gm(A) |
|fm − gm(A)| |
|
31 |
3,99 |
2,58 |
1,41 |
32 |
3,03 |
2,38 |
0,65 |
33 |
2,56 |
2,2 |
0,36 |
34 |
2,26 |
2,05 |
0,2 |
35 |
2,03 |
1,92 |
0,11 |
36 |
1,86 |
1,8 |
0,06 |
37 |
1,72 |
1,7 |
0,02 |
38 |
1,61 |
1,61 |
0,0 |
39 |
1,51 |
1,53 |
0,02 |
Наименьшая разность (0,0) достигается при значении m = 38.
2 Выполнение работы |
6 |
ˆ = 37 ошибок
B
ˆ = 0 007
K ,
Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:
ˆ |
= 21 дней |
Xn+1 |
И время до полного завершения тестирования:
ttst = 376 дней Сведем данные по ошибкам в таблицу.
Номер ошибки |
Через дней |
31 |
21 |
32 |
24 |
33 |
29 |
34 |
36 |
35 |
48 |
2.2.2. 80 %
Порядок определен так: слева направо, построчно. Левый верхний угол — первое значение, правый нижний — последнее.
n = 24; n + 1 = 12, 5 2
Равномерное распределение |
|
||||
|
|
|
|
|
|
1,0 |
1,0 |
1,0 |
2,0 |
2,0 |
2,0 |
3,0 |
3,0 |
4,0 |
5,0 |
7,0 |
7,0 |
8,0 |
8,0 |
8,0 |
9,0 |
9,0 |
9,0 |
9,0 |
9,0 |
10,0 |
11,0 |
13,0 |
13,0 |
|
|
|
|
A = 16, 47 > 12, 5 |
|
Рассмотрим функции fn(m) и gn(m, A) (m > n). |
|||||
|
m |
fm |
gm(A) |
|fm − gm(A)| |
|
|
25 |
3,78 |
2,81 |
0,96 |
|
|
26 |
2,82 |
2,52 |
0,3 |
|
|
27 |
2,35 |
2,28 |
0,07 |
|
|
28 |
2,06 |
2,08 |
0,02 |
|
|
29 |
1,84 |
1,92 |
0,07 |
|
|
Наименьшая разность (0,02) достигается при значении m = 28. |
||||
|
|
|
|
ˆ |
|
|
|
|
|
B = 27 ошибок |
ˆ = 0 015
K ,
Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:
2 Выполнение работы |
7 |
ˆ |
= 23 дней |
Xn+1 |
И время до полного завершения тестирования:
ttst = 124 дней Сведем данные по ошибкам в таблицу.
Номер ошибки |
Через дней |
25 |
23 |
26 |
34 |
27 |
68 |
Экспоненциальное распределение |
|
||||
|
|
|
|
|
|
0,51 |
0,51 |
0,51 |
1,05 |
1,05 |
1,05 |
1,63 |
1,63 |
2,23 |
2,88 |
4,31 |
4,31 |
5,11 |
5,11 |
5,11 |
5,98 |
5,98 |
5,98 |
5,98 |
5,98 |
6,93 |
7,99 |
10,5 |
10,5 |
A = 17, 1 > 12, 5
Рассмотрим функции fn(m) и gn(m, A) (m > n).
m fm |
gm(A) |
|fm − gm(A)| |
|
25 |
3,78 |
3,04 |
0,74 |
26 |
2,82 |
2,7 |
0,12 |
27 |
2,35 |
2,43 |
0,07 |
28 |
2,06 |
2,2 |
0,14 |
Наименьшая разность (0,07) достигается при значении m = 27.
ˆ = 26 ошибок
B
ˆ = 0 026
K ,
Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:
ˆ |
= 19 дней |
Xn+1 |
И время до полного завершения тестирования:
ttst = 57 дней Сведем данные по ошибкам в таблицу.
|
Номер ошибки |
Через дней |
|
|
|
|||||
|
|
25 |
|
|
|
19 |
|
|
|
|
|
|
26 |
|
|
|
38 |
|
|
|
|
Рэлеевское распределение |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
2,56 |
2,56 |
2,56 |
|
3,67 |
|
3,67 |
|
3,67 |
|
|
4,56 |
4,56 |
5,34 |
|
6,07 |
|
7,43 |
|
7,43 |
|
|
8,09 |
8,09 |
8,09 |
|
8,75 |
|
8,75 |
|
8,75 |
|
|
8,75 |
8,75 |
9,42 |
|
10,11 |
|
11,59 |
|
11,59 |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 Выполнение работы |
8 |
|
|
|
|
A = 15, 23 > 12, 5 |
|
Рассмотрим функции fn(m) и gn(m, A) (m > n). |
|||||
|
m |
fm |
gm(A) |
|fm − gm(A)| |
|
|
25 |
3,78 |
2,46 |
1,32 |
|
|
26 |
2,82 |
2,23 |
0,59 |
|
|
27 |
2,35 |
2,04 |
0,31 |
|
|
28 |
2,06 |
1,88 |
0,18 |
|
|
29 |
1,84 |
1,74 |
0,1 |
|
|
30 |
1,68 |
1,63 |
0,05 |
|
|
31 |
1,54 |
1,52 |
0,02 |
|
|
32 |
1,43 |
1,43 |
0,0 |
|
|
33 |
1,34 |
1,35 |
0,01 |
|
|
Наименьшая разность (0,0) достигается при значении m = 32. |
||||
|
|
|
|
ˆ |
|
|
|
|
|
B = 31 ошибок |
ˆ = 0 009
K ,
Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:
ˆ |
= 15 дней |
Xn+1 |
И время до полного завершения тестирования:
ttst = 281 дней Сведем данные по ошибкам в таблицу.
Номер ошибки |
Через дней |
25 |
15 |
26 |
18 |
27 |
22 |
28 |
27 |
29 |
36 |
2.2.3. 60 %
Порядок определен так: слева направо, построчно. Левый верхний угол — первое значение, правый нижний — последнее.
|
|
|
|
|
n = 18; |
n + 1 |
= 9, 5 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
2 |
|
||
Равномерное распределение |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
1,0 |
1,0 |
1,0 |
2,0 |
2,0 |
2,0 |
|
|
|
3,0 |
3,0 |
4,0 |
5,0 |
7,0 |
7,0 |
|
|
|
8,0 |
8,0 |
8,0 |
9,0 |
9,0 |
9,0 |
|
|
|
|
|
|
|
|
A = 12, 62 > 9, 5 |
Рассмотрим функции fn(m) и gn(m, A) (m > n).
2 Выполнение работы |
9 |
||||
|
|
|
|
|
|
|
m fm |
gm(A) |
|fm − gm(A)| |
||
|
19 |
3,5 |
2,82 |
0,67 |
|
|
20 |
2,55 |
2,44 |
0,11 |
|
|
21 |
2,1 |
2,15 |
0,05 |
|
|
22 |
1,81 |
1,92 |
0,11 |
|
Наименьшая разность (0,05) достигается при значении m = 21.
ˆ = 20 ошибок
B
ˆ = 0 027
K ,
Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:
ˆ |
= 18 дней |
Xn+1 |
И время до полного завершения тестирования:
ttst = 55 дней Сведем данные по ошибкам в таблицу.
|
Номер ошибки |
Через дней |
|
|
|||||
|
|
19 |
|
|
|
18 |
|
|
|
|
|
20 |
|
|
|
37 |
|
|
|
Экспоненциальное распределение |
|
|
|||||||
|
|
|
|
|
|
|
|
||
0,51 |
0,51 |
0,51 |
|
1,05 |
1,05 |
|
1,05 |
||
1,63 |
1,63 |
2,23 |
|
2,88 |
4,31 |
|
4,31 |
||
5,11 |
5,11 |
5,11 |
|
5,98 |
5,98 |
|
5,98 |
A = 12, 94 > 9, 5
Рассмотрим функции fn(m) и gn(m, A) (m > n).
m fm |
gm(A) |
|fm − gm(A)| |
|
19 |
3,5 |
2,97 |
0,53 |
20 |
2,55 |
2,55 |
0,0 |
21 |
2,1 |
2,23 |
0,13 |
Наименьшая разность (0,0) достигается при значении m = 20.
ˆ = 19 ошибок
B
ˆ = 0 054
K ,
Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:
ˆ |
= 19 дней |
Xn+1 |
И время до полного завершения тестирования:
ttst = 19 дней Больше ошибок по модели не ожидается.
3 Заключение |
|
|
10 |
|||
Рэлеевское распределение |
|
|
|
|||
|
|
|
|
|
|
|
2,56 |
2,56 |
2,56 |
3,67 |
3,67 |
3,67 |
|
4,56 |
4,56 |
5,34 |
6,07 |
7,43 |
7,43 |
|
8,09 |
8,09 |
8,09 |
8,75 |
8,75 |
8,75 |
|
A = 11, 51 > 9, 5
Рассмотрим функции fn(m) и gn(m, A) (m > n).
m fm |
gm(A) |
|fm − gm(A)| |
|
19 |
3,5 |
2,4 |
1,09 |
20 |
2,55 |
2,12 |
0,43 |
21 |
2,1 |
1,9 |
0,2 |
22 |
1,81 |
1,72 |
0,1 |
23 |
1,61 |
1,57 |
0,04 |
24 |
1,45 |
1,44 |
0,01 |
25 |
1,33 |
1,33 |
0,01 |
26 |
1,22 |
1,24 |
0,02 |
Наименьшая разность (0,01) достигается при значении m = 25.
ˆ = 24 ошибок
B
ˆ = 0 014
K ,
Тогда среднее время до обнаружения (n + 1)-й ошибки составляет:
ˆ |
= 12 дней |
Xn+1 |
И время до полного завершения тестирования:
ttst = 178 дней Сведем данные по ошибкам в таблицу.
Номер ошибки |
Через дней |
19 |
12 |
20 |
15 |
21 |
18 |
22 |
24 |
23 |
36 |
3.Заключение
Врезультате выполнения работы были исследованы показатели надежности программ, характеризуемых моделью обнаружения ошибок ДжелинскогоМоранды для различных законов распределения времени между соседними отказами и различного числа используемых для анализа данных.
Установлено, что:
•наименьшее число ошибок ожидается при распределении интервалов времени по экспоненциальному закону;
•равномерное распределение интервалов дает величину ожидаемых ошибок большую, чем экспоненциальное, но меньшую, чем рэлеевское;