1

Các phương pháp đánh giá độ tin cậy
của hệ thống tính toán qua cấu trúc hệ thống
NXB H. : ĐHCN, 2012 Số trang 67 tr. +

Lê Thị Hải Yến Trường Đại học Công nghệ
Luận văn ThS ngành: Công nghệ phần mềm; Mã số: 60 48 10
Người hướng dẫn: Tiến sĩ Lê Quang Minh
Năm bảo vệ: 2012

Abstract: Trình bày một số khái niệm cơ bản về độ tin cậy, các chỉ số liên quan đến độ tin
cậy và phương pháp tính độ tin cậy của hệ thống qua cấu trúc nối tiếp và song song.
Nghiên cứu một số bài toán cơ bản, các thuật toán cũng như các phương pháp để giải
quyết chúng. Trình bày việc xây dựng bài toán tính toán độ tin cậy của hệ thống, đưa ra
các hàm chức năng cần thiết để xây dựng và giải quyết bài toán đánh giá độ tin cậy của hệ
thống mạng máy tính. Đưa ra ví dụ về một hệ thống mạng máy tính thực, đặc tả hệ thống
đó và xét các trường hợp cơ bản có thể ảnh hưởng đến độ tin cậy của hệ thống.

Keywords: Công nghệ phần mềm; Cấu trúc hệ thống; Mạng máy tính

Content
CHƢƠNG 1
CƠ SỞ LÝ THUYẾT
1.1 Khái niệm cơ bản về độ tin cậy
Tổng quan
“Hệ thống là một tập hợp gồm nhiều phần tử tương tác, có các mối quan hệ ràng buộc lẫn
nhau và cùng hoạt động hướng tới một mục tiêu chung thông qua chấp thuận các đầu vào, biến

sửa chữa phục hồi.
Trong phần này sẽ nói đến những thông số cơ bản của phần tử không phục hồi và cách tính
các thông số đó dựa vào lý thuyết xác suất và thống kê.
1.3 Phương pháp tính độ tin cậy của hệ thống qua cấu trúc hệ thống
Cấu trúc của một hệ thống dù phức tạp đến đâu thì cũng chỉ quy về 2 dạng là cấu trúc nối tiếp
hoặc cấu trúc song song [4] (Phương pháp tính độ tin cậy của hệ thống không có dự phòng và có
dự phòng của hệ thống [2]).
Phương pháp này xây dựng mối quan hệ trực tiếp giữa độ tin cậy của hệ thống với độ tin cậy
của các phần tử đã biết. Sơ đồ khối độ tin cậy (Reliability Block Diagrams - RBD) của hệ thống
được xây dựng trên cơ sở phân tích ảnh hưởng của hỏng hóc phần tử đến hỏng hóc của hệ thống.
1.3.1 Sơ đồ khối độ tin cậy của các phần tử nối tiếp
Cấu trúc đơn giản hơn cả là cấu trúc không có dự phòng của một hệ thống được tạo nên bởi n
phần tử, mỗi trở ngại của một phần tử riêng biệt đều dẫn đến trở ngại của cả hệ thống.

Thời gian hoạt động an toàn trung bình của hệ thống là:

Xác suất trạng thái hỏng của hệ thống:

3

1.3.2 Sơ đồ khối độ tin cậy của các phần tử song song
Trong sơ đồ các phần tử song song [8] (hệ thống có dự phòng), sự cố của 1 phần tử nào đó
không nhất định là sẽ dẫn đến sự cố cho toàn hệ thống, ở sơ đồ này hệ thống sẽ gặp sự cố khi tất
cả các phần tử gặp sự cố.

Độ tin cậy của hệ thống: Thời gian hoạt động an toàn trung bình của hệ thống là:


Giai đoạn đầu: Xây dựng sơ đồ cấu trúc logic;
Giai đoạn 2: Tìm tất cả các đường đi thành công của hệ thống.
Giai đoạn 3: Tất cả các đường đi thành công của hệ thống sẽ được ghi lại dưới dạng các toán tử
logic cơ bản, tối thiểu hoá các toán tử logic đó.
Giai đoạn 4: Trực giao hoá các toán tử logic, chuyển đổi mô hình logic sang đại số và tính toán
xác suất hệ thống hoạt động an toàn, thời gian trung bình giữa các lần hỏng hóc và các chỉ số khác
của độ tin cậy.
2.1 BÀI TOÁN TÌM ĐƯỜNG ĐI TRONG ĐỒ THỊ HỆ THỐNG
2.1.1 Thuật toán chuyển đổi sơ đồ cấu trúc logic thành sơ đồ khối
Sơ đồ cấu trúc logic là biểu diễn cấu trúc logic của hệ thống bằng sơ đồ theo các quy ước về
cách mã hoá và biểu diễn mối quan hệ giữa các thành phần dưới dạng các ký hiệu. Việc xây dựng
thành công sơ đồ cấu trúc logic của hệ thống cho ta một hình ảnh trực quan về cấu trúc hệ thống
và sẽ là điều kiện tiên đề để có thể phân tích và đánh giá độ tin cậy của hệ thống.
2.1.2 Phân loại các đỉnh và các cạnh của đồ thị liên kết
Việc phân loại các đỉnh, các cạnh sẽ giúp ta xây dựng sơ đồ cấu trúc logic một cách chính xác.
2.1.3 Thuật toán chuyển đổi sơ đồ cấu trúc logic sang đồ thị liên kết
Trường hợp sơ đồ cấu trúc logic vô hướng thì việc biến đổi là đơn giản nhưng nếu sơ đồ cấu
trúc logic có hướng thì việc quan trọng là phải xác định hướng của các cung và xây dựng làm sao
cho hệ thống đạt hiệu quả.
2.1.4 Thuật toán tìm tất cả các đƣờng đi trong ma trận liên kết
Thuật toán để tìm tất cả các đường đi trong ma trận kề dựa trên thao tác nhân ma trận liên kết
một cột tương ứng của ma trận đó được thể hiện như sau:
B
k
= A B
*

k- 1
(*)
Trong đó:

bởi giá trị 0. Nếu đường đi xuất hiện trong B
k
là đường đi đầy đủ thì thay thế B
k
=0. Kết quả là
B
*
k
.
+) Bước 5: Kiểm tra B
*
k
. Nếu B
*
k
=0 thì thực hiện tiếp bước 7. Nếu B
*
k
≠0 thì thực hiện tiếp bước 6.
+) Bước 6: Kiểm tra điều kiện k ≤ n-1. Nếu thoả mãn điều kiện k < n-1 thì tăng k lên 1 và thực
hiện tiếp bước 3. Nếu điều kiện k = n-1thì thực hiện tiếp bước 7.
+) Bước 7: Kiểm tra lại danh sách đường đi và kết quả nhận được là danh sách các đường đi có
thể có từ đỉnh đầu đến đỉnh cuối.
2.1.5 Thuật toán tìm tất cả đƣờng đi của ma trận liên kết trong lý thuyết đồ thị.
Tư tưởng của tìm kiếm theo chiều sâu là: Từ đỉnh nguồn (đỉnh đầu) của đồ thị ta di chuyển
đến một đỉnh khác (một đỉnh bất kỳ mà có thể đi từ đỉnh đầu). Từ đỉnh này ta tiếp tục đi đến khác
đỉnh khác. Nếu không thể đi tiếp được nữa thì quay lại đỉnh trước đó và đi đến đỉnh khác. Cứ như
vậy cho đến khi đến đỉnh cuối của đồ thị.
2.1.6 Kết luận
Dựa vào những kết quả các thuật toán đã trình bày, ta có thể rút ra một vài kết luận như sau:

đều bằng 0.
2.3.1 Các phƣơng pháp giảm thiểu các hàm đại số logic đối với các hình thức trực giao và
trực giao không lặp.
a) Thuật toán cắt giảm
Thuật toán này dựa trên việc triển khai các hàm logic cho ta kết quả là các hàm logic đã trực
giao, trực giao không lặp và trường hợp đặc biệt đó là dạng chuẩn tắc tuyển trực giao.
b) Thuật toán trực giao hoá theo công thức của Poresky
Thuật toán trực giao hoá theo công thức của Poresky [10] gồm các bước sau:
1. Hàm logic được viết dưới dạng chuẩn tắc tuyển như sau:
f(x
n
) = K
1
˅ K
2
˅ …˅ K
j
˅ ….˅ K
R

Trong đó: K
j
là mệnh đề sơ cấp có số thứ tự là j.
2. Tất cả các biến trong hàm logic khi được viết dưới dạng chuẩn tắc tuyển thì phải được sắp
xếp theo thứ tự tăng dần, bắt đầu với bậc thấp nhất của biến.
3. Dạng chuẩn tắc tuyển được viết dưới dạng công thức Poresky như sau:
f(x
n
) = K
1

quả trung gian.
7

- Việc sử dụng thuật toán cắt giảm để đưa về dạng chuẩn tắc tuyển có thể nhìn sẽ dài dòng hơn
nhưng nó lại dễ dàng hơn khi lập trình trên máy tính.
- Thuật toán trực giao hoá theo công thức Poresky không đơn giản khi giải bằng tay vì số lượng
các biến khi khai triển khá dài.

CHƢƠNG 3
THIẾT LẬP VÀ XÂY DỰNG CHƢƠNG TRÌNH
TÍNH ĐỘ TIN CẬY CỦA HỆ THỐNG MẠNG MÁY TÍNH

Sau khi đã hiểu rõ về cách thức cũng như phương pháp để tính toán độ tin cậy của hệ thống
thì ta sẽ phải cụ thể hoá các phương pháp đó bằng một ngôn ngữ lập trình cụ thể.
3.1 Thiết lập bài toán
3.1.1 Viết chƣơng trình để tìm các đƣờng đi trong ma trận liên kết
3.1.1.1 Các yêu cầu đối với chƣơng trình và xây dựng chƣơng trình
Chương trình được thiết kế với mục đích là tìm tất cả các đường đi giữa hai nút trong ma trận
liên kết, mà ma trận liên kết này được xây dựng từ đồ thị liên kết.
Tham số đầu vào của chương trình là ma trận liên kết được xây dựng từ đồ thị liên kết.
Chương trình phải hoạt động sao cho tìm được các đường đi của ma trận liên kết.
Tham số đầu ra của chương trình là tất cả các đường đi được viết dưới dạng các phép hội sơ cấp.
Để có thể chạy được ứng dụng này thì máy tính của bạn phải có bộ nhớ tối thiểu là 32MB.
3.1.1.2 Lựa chọn thuật toán để viết chƣơng trình tìm tất cả các đƣờng đi giữa hai nút trong
ma trận liên kết
Trong chương 2 chúng ta có nói đến thuật toán tìm tất cả các đường đi giữa hai nút. Thuật
toán ở phần 2.1.4 nói về việc tìm tất cả đường đi giữa hai nút trong ma trận liên kết, còn thuật toán
ở phần 2.1.5 nói về việc tìm tất cả các đường đi giữa hai nút của ma trận liên kết trong lý thuyết
đồ thị. Hai thuật toán đó đều có những ưu và nhược điểm riêng. Ta sẽ sử dụng thuật toán 2.1.5 để
xây dựng chương trình tìm tất cả các đường đi giữa hai nút trong ma trận kết nối.

3.1.2.1 Các yêu cầu đối với chƣơng trình và xác định các vấn đề
Tham số đầu vào của chương trình là hàm đại số logic được thiết lập từ tập các biến mà mô tả
đặc điểm chức năng của một trạng thái hoạt động tốt trong một hệ thống phức tạp.
Tham số đầu ra của chương trình là hàm đại số logic đã được giảm thiểu, viết dưới dạng trực
giao hoặc trực giao không lặp.
3.1.2.2 Phân tích và lựa chọn thuật toán trực giao hoá
Ta thấy thuật toán trực giao hoá theo công thức Poresky là phù hợp để viết chương trình hơn
cả. Công thức Poresky được sử dụng trong thuật toán là:
K
1
˅ K
2
˅ …˅ K
j
˅ ….˅ K
n
=
Công thức có thể viết dưới dạng khác như sau:
K
1
˅ K
2
˅ …˅ K
j
˅ ….˅ K
n
=

3.1.2.3 Thiết kế các hàm chức năng cho thuật toán trực giao hoá
/* Function Ortogonal: Truc giao hoa tat ca cac thanh phan cua K1, ket qua luu trong ma tran AB,
ma van giu duoc dang CTT truc giao.*/
void ortogonal(
unsigned int K1[maxN][maxK], //input
unsigned int i_line,
unsigned int LengK1[maxN],
unsigned int AB[maxN][maxK], //output
unsigned int &i_line_AB,
unsigned int Leng_AB[maxN] );
3.2 Các ví dụ sử dụng các hàm đã xây dựng
Ví dụ 1:

a

b
Hình 3.4a: Sơ đồ cấu trúc logic; 3.4b: Đồ thị liên kết tương ứng
Ví dụ 2: Xét hệ thống máy chủ có cấu trúc như hình 3.5:
- 0: Là máy chủ (server);
- 1,2,3: Là các máy chủ thứ cấp mà kết nối trực tiếp với server;
- 4,5: Các đường truyền;
- 6,7,8: Các Bus;
- 9,10, ,14: Các trạm trung chuyển;
- 15,16,17: Các máy trạm (client) là người sử dụng cuối.

10
13
12
17
14
16
15
Hình 3.5 Đồ thị liên kết hệ thống
3.3 Phát triển các chức năng và các yêu cầu cần thiết bổ sung cho việc tính toán
Để giải quyết một số phép toán cộng và nhân ta sử dụng một số quy tắc trong toán logic sau:
- x.x = x hay x˄x = x;
- x+x = x hay x˅x = x;
- = 0, hay = 0;
- Nếu x
i
* K(x
i
) = K(x
i
) thì * K(x
i
) = 0, trong đó K(x
i
) là một phép tuyển mà có liên quan đến
biến logic x
i
.
3.4 Kết luận
Chương này nói đến các yêu cầu để thiết lập, hướng giải quyết và xây dựng các hàm chức
năng của bài toán –xây dựng hệ thống tính toán độ tin cậy và khả năng sống sót (khả năng hoạt

8 11
9
10
13
12
17
14
16
15

Hình 4.1 Sơ đồ cấu trúc logic của hệ thống
Trong đó:
- 0: Là máy chủ (server);
- 1,2,3: Là các máy chủ thứ cấp mà kết nối trực tiếp với server;
- 4,5: Các đường truyền;
- 6,7,8: Các Bus;
- 9,10, ,14: Các trạm trung chuyển;
- 15,16,17: Các máy trạm (client) là người sử dụng cuối.
Yêu cầu đặt ra của bài toán là:
Tính P(t) và T
HD
, biết cường độ hỏng hóc của các phần tử trong hệ thống máy chủ trên như
sau:
- 
i
= 0.0001 (1/năm) với i = (1, 2, 3,15,16,17);
- 
i
= 0.00001 (1/năm) với i = (4,5,6,7,8);
- 

1,15
*f
2,15
)*f
3,15
= f
12,15
*f
3,15

Sau đó sử dụng thuật toán trực giao hoá để chuyển đổi mô hình logic sang đại số và tính các
giá trị xác suất P(t) và T
HD
.
Trường hợp 2: Sử dụng tính chất kết hợp trong đại số Boole:
F= f
1,15
˅f
2,15
˅f
3,15
= (f
1,15
˅f
2,15
)˅f
3,15
= f
12,15
˅f
Hình 4.10 Sự phụ thuộc của P(t) vào thời gian t
+) Để hiểu rõ hơn về khả năng tồn tại của hệ thống ta xét tiếp một trường hợp: Hệ thống đang hoạt
động bình thường thì không nhận được tín hiệu phản hồi của máy chủ số 3 vào giờ thứ 3000 và
máy chủ số 1 vào giờ thứ 3500, chỉ nhận được tín hiệu từ máy chủ số 2.

Hình 4.13 Sự phụ thuộc P(t) vào thời gian t
4.4 Kết luận
Với việc phát triển thành công chương trình tính toán độ tin cậy ta đã nghiên cứu được độ tin
cậy cũng như khả năng sống sót của hệ thống, thông qua kết quả của chương trình có thể thấy kết
quả hoàn toàn phù hợp với sự mong đợi của chúng ta, điều này có nghĩa rằng chương trình ta đang
phát triển đã làm việc một cách chính xác và đó sẽ là cơ sở cho việc phát triển phần mềm tính toán
độ tin cậy của các hệ thống phức tạp hơn.
Qua ví dụ cụ thể ở trên càng chứng minh một điều là các thành phần của hệ thống đóng vai
trò vô cùng quan trọng, độ tin cậy cũng như khả năng sống sót của hệ thống phụ thuộc vào chúng.
Việc loại bỏ bớt các thành phần của hệ thống sẽ làm cho hệ thống hoạt động kém an toàn hơn.
14 KẾT KUẬN
1. Kết luận
Luận văn này đã đưa ra và phân tích được các lý thuyết liên quan đến độ tin cậy của hệ thống
và xây dựng thành công phần mềm ứng dụng giải quyết bài toán tính các chỉ số liên quan đến độ
tin cậy của hệ thống, bao gồm việc xây dựng bài toán, chỉ ra các giai đoạn giải quyết bài toán, các
thuật toán đã được phát triển trong quá trình tìm đường đi trong đồ thị, tối thiểu hoá các toán tử
logic, phương pháp trực giao hoá và các quy tắc để chuyển đổi về hàm xác suất để tính toán các
giá trị cần tìm.
Chương trình được viết bằng ngôn ngữ lập trình C++ là ngôn ngữ khá phá biến hiện nay, đã
giải quyết được yêu cầu đặt ra của bài toán, với tập hợp các tham số đầu vào sẽ cho các kết quả,

Associates Pty Ltd, pp.5-7, 8,9.
[8]. Mahesh Pandey, Mikko Jyrkama (2008), System Reliability Analysis, University of
Waterloo, pp.2-5, 23.
Tiếng Nga
[9]. Le Quang Minh (2007), “Анализ методов обеспечения отказоустойчивости и живучести
вычислительных систем”, Естественные науки и технологии- №5. (Phân tích các phương
pháp bảo đảm độ tin cậy và độ hoạt động của hệ thống tính toán, Tạp chí “Khoa học tự nhiên và
công nghệ”, số 5 – 2007).
[10]. Le Quang Minh (2007), “Анализ эффективности применения методов повышения
отказоустойчивости ИВС реального времени”, Микроэлектроники и информатики,
Тез. докл. Всероссийской конференции. (Phân tích hiệu quả của việc ứng dụng các phương
pháp nâng cao độ tin cậy cho hệ thống thời gian thực có cấu trúc dạng cây. Hội thảo khoa học
toàn LB Nga, Mátxcơva).