ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

TRIỆU XUÂN HÒA

CÁC PHƯƠNG PHÁP DỰ PHÒNG
NÂNG CAO ĐỘ TIN CẬY CỦA HỆ THỐNG TÍNH TOÁN

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - 2014


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

TRIỆU XUÂN HÒA

CÁC PHƯƠNG PHÁP DỰ PHÒNG
NÂNG CAO ĐỘ TIN CẬY CỦA HỆ THỐNG TÍNH TOÁN
Ngành: Khoa học máy tính
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: TS. NGUYỄN VĂN ĐOÀN

THÁI NGUYÊN - 2014


LỜI CAM ĐOAN

Tôi xin cảm ơn các đồng nghiệp và người thân đã động viên, giúp đỡ
tôi trong quá trình nghiên cứu và thực hiện luận văn.
Quá trình thực hiện đề tài không tránh khỏi các thiếu sót, rất mong tiếp
tục nhận được sự đóng góp ý kiến của các thầy, các cô giáo, các bạn đồng
nghiệp đối với đề tài nghiên cứu của tôi để đề tài được hoàn thiện hơn.
Tôi xin trân trọng cảm ơn!
Thái Nguyên, ngày 28 tháng 8 năm 2014
Học viên

Triệu Xuân Hòa


MỤC LỤC
MỞ ĐẦU ....................................................................................................... 1
CHƯƠNG 1 KHÁI QUÁT VỀ ĐỘ TIN CẬY HỆ THỐNG VÀ BÀI TOÁN
DỰ PHÒNG ................................................................................................... 4
1.1. Khái quát về độ tin cậy của hệ thống .................................................... 4
1.1.1. Khái niệm về độ tin cậy của hệ thống ............................................. 4
1.1.2. Chỉ số độ tin cậy của hệ thống ........................................................ 5
1.1.3. Vai trò độ tin cậy của hệ thống ..................................................... 16
1.2. Bài toán dự phòng trong hệ thống....................................................... 17
1.2.1. Khái niệm ..................................................................................... 17
1.2.2. Các cách tiếp cận của dự phòng hệ thống ..................................... 17
CHƯƠNG 2 NÂNG CAO ĐỘ TIN CẬY CỦA HỆ THỐNG TÍNH TOÁN . 20
2.1. Các bước tính toán độ tin cậy của hệ thống ........................................ 20
2.1.1. Xây dựng sơ đồ logic theo cấu trúc hệ thống ................................ 20
2.1.2. Thuật toán chuyển đổi sơ đồ cấu trúc logic sang đồ thị liên kết .... 21
2.1.3. Thuật toán tìm tất cả các đường đi trong ma trận liên kết: ............ 23
2.1.4. Thuật toán tìm tất cả đường đi của ma trận liên kết theo lý thuyết đồ thị
............................................................................................................... 26

DANH MỤC KÝ HIỆU, TỪ VIẾT TẮT

Từ viết tăt

Từ tiếng Anh

Từ hoặc cụm từ

AP

Active Protection

Phương pháp dự phòng
chủ động

MTTF

Mean Time To Failure

Thời gian hoạt động an
toàn trung bình

MTBF

Mean Time Between Failure

Thời gian trung bình giữa
hai lần hỏng

MTTR

Hình 3.8: Cấu hình hệ thống với AP và nhân bản dự phòng 3 ...................... 57
Hình 3.9: Đồ thị xác suất khả năng hoạt động không có sự thất bại của hệ
thống với cấu hình số 1, số 21, số 24, số 25 theo thời gian ........................... 58


1

MỞ ĐẦU
1. Lý do chọn đề tài
Việc đánh giá độ tin cậy của hệ thống dựa trên cấu trúc của hệ thống,
thông qua độ tin cậy của từng thành phần hệ thống là một bài toán phức
tạp, để giải nó cần đến các công cụ như lý thuyết xác suất, lý thuyết đồ thị,
logic. Phương pháp đánh giá độ tin cậy của hệ thống dựa trên cơ sở lý
thuyết xác suất và quá trình ngẫu nhiên đã được áp dụng và đạt được những
kết quả khả quan.
Dự báo được độ tin cậy của hệ thống có thể sẽ có hiệu quả cao, liên
quan đến quá trình sản xuất và lập trình dự toán như thế nào, chi phí bảo
trì, các chi phí tối thiểu cấu hình hệ thống, hoặc cách khác, tổng số lợi
nhuận dự kiến sẽ được tối đa nếu độ tin cậy hệ thống được chọn theo một
công thức dựa trên tính toán tuổi thọ của thiết bị, dịch vụ đời sống thực tế
của thiết bị cho đến khi nó không hoạt động tốt. Để nâng cao độ tin cậy của
các yếu tố thành phần, người ta đã sử dụng một kỹ thuật là bổ sung các thành
phần dư thừa, hay còn gọi là hệ thống có dự phòng. Việc sử dụng các thành
phần dự phòng không còn là những hướng nghiên cứu mới, tuy nhiên việc đề
xuất sử dụng chúng trong các hệ thống có cấu trúc khác nhau, như hệ phân
tán, tính toán song song … hiện nay vẫn còn được nhiều nghiên cứu tập trung
phát triển.
Với mục tiêu tìm hiểu về việc nâng cao độ tin cậy của hệ thống, đặc biệt
là việc sử dụng các phương pháp dự phòng, tôi đã lựa chọn đề tài “Các
phương pháp dự phòng nâng cao độ tin cậy của hệ thống tính toán” làm

Khái niệm về độ tin cậy của hệ thống

1.2.

Bài toán dự phòng


3

Chương 2: NÂNG CAO ĐỘ TIN CẬY CỦA HỆ THỐNG TÍNH TOÁN
2.1. Các bước tính toán độ tin cậy của hệ thống
2.2. Tính độ tin cậy của hệ thống có dự phòng
2.3. Đảm bảo độ tin cậy của hệ thống
Chương 3:THỬ NGHIỆM NÂNG CAO ĐỘ TIN CẬY CỦA HỆ
THỐNG MÁY CHỦ NGÂN HÀNG
3.1. Bài toán
3.2. Sử dụng các phương pháp dự phòng nâng cao độ tin cậy của hệ
thống và xây dựng công thức tính độ tin cậy.
3.3. Xây dựng chương trình thử nghiệm
3.4. Nhận xét các phương án dự phòng
Phần kết luận: Tóm tắt các kết quả đạt được.


4

CHƯƠNG 1 KHÁI QUÁT VỀ ĐỘ TIN CẬY HỆ THỐNG VÀ BÀI
TOÁN DỰ PHÒNG
1.1.Khái quát về độ tin cậy của hệ thống
1.1.1.Khái niệm về độ tin cậy của hệ thống
a.Khái niệm hệ thống, phần tử

P(t) = P{t ≥ t}

(1.1)

Theo định nghĩa xác suất [2]thì xác suất không an toàn Q(t) hay còn gọi là
xác suất hỏng của hệ thống sẽ là:
Q(t) = 1-P(t)

(1.2)

1.1.2.Chỉ số độ tin cậy của hệ thống
Các hệ thống, thiết bị kỹ thuật (các phần tử) tồn tại trong thực tiễn thường
tồn tại dưới 2 dạng là phục hồi được và không phục hồi được. Và để dễ xác
định độ tin cậy của các phần tử ta cũng sẽ phân chia các phần tử thành 2 dạng
như trên.
1.1.2.1.Phần tử không phục hồi
Phần tử không phục hồi là phần tử khi được đưa vào sử dụng, nếu bị hư
hỏng thì sẽ loại bỏ ngay mà không tiến hành sửa chữa do không thể hoặc việc
sửa chữa không mang lại hiệu quả, ví dụ như: linh kiện điện trở, tụ điện, IC
… ta chỉ quan tâm đến sự kiện xảy ra sự cố đầu tiên.
Những thông số cơ bản của phần tử không phục hồi gồm có:
a) Thời gian vận hành an toàn t
Giả thiết ở thời điểm t = 0 phần tử bắt đầu hoạt động và đến thời điểm t =
t thì phần tử bị sự cố. Khoảng thời gian t được gọi là thời gian liên tục vận
hành an toàn của phần tử. Vì sự cố không xảy ra tất định nên t là một đại
lượng ngẫu nhiên có các giá trị trong khoảng 0 ≤ t ≤ ∞.
Giả thiết trong khoảng thời gian khảo sát t thì phần tử xảy ra sự cố với
xác suất Q(t). Khi đó:
Q(t) = P{t< t}



Trong đó thỏa mãn tính chất:
∞

( ).

=1

Vậy hàm mật độ phân phối xác suất của t là:
( ) = lim
→

1

( < τ ≤ t + t)(1.4)

Có q(t). t là xác suất để thời gian hoạt động t nằm trong khoảng (t t+ t)
với t đủ nhỏ.


7

b) Độ tin cậy của phần tử P(t)
Ta có hàm Q(t) mô tả xác suất sự cố của phần tử, vậy hàm mô tả độ tin
cậy của phần tử được ký hiệu là P(t) và sẽ được tính theo định nghĩa hàm xác
suất:
P(t) = 1 – Q(t) = P{ t ≥ t}

(1.5)



8

P(t)
1

0

t

Hình 1.3: Biểu diễn độ tin cậy của phần
Từ hai đồ thị trên ta thấy rằng Q(∞) = 1 và P(∞) = 0 chứng tỏ độ tin cậy
của phần tử giảm dần theo thời gian.
c) Cường độ hỏng hóc l(t)
Cường độ hỏng hóc [3] (hay cường độ trở ngại) là một trong những khái
niệm quan trọng khi nghiên cứu độ tin cậy, l(t) là một hàm theo thời gian.
Với t đủ nhỏ thì l(t). t chính là xác suất để phần tử đã hoạt động tốt đến
thời điểm t sẽ hỏng hóc trong khoảng thời gian t tiếp theo. Hay đó chính là
số lần hỏng hóc trên một đơn vị thời gian trong khoảng thời gian t.
( ) = lim
Δ →

(

→ 0 thì ta có: P(AB) = P(A)

(A kéo theo B: Nếu A xảy ra thì B xảy ra) theo giả thiết ban đầu

Và
(
)

)

< +
( > )

)

(1.9)

Từ (1.8) và (1.9) suy ra:
1

( ) = lim
Δ →

mật độ xác suất, hàm phân bố xác suất và độ tin cậy của phần tử.
Vậy độ tin cậy của phần tử được tính như sau:
Từ (1.3) và (1.5) ta có:
′(

( )=

′

)= 1

′(

( ) =

( )

)=

(do đạo hàm của 1 bằng 0)
Thay vào (1.10) ta có:

( )=
( )

=

( )
( )


phục hồi khi đã biết cường độ hỏng hóc l(t), mà cường độ hỏng hóc l(t) này


10

xác định được nhờ phương pháp thống kê quá trình hỏng hóc của phần tử
trong quá khứ.
Trong các hệ thống hiện giờ thường sử dụng điều kiện l(t) = l = hằng
số (λ tương đối nhỏ), thực hiện được nhờ bảo quản định kỳ. Khi đó cường độ
hỏng hóc là giá trị trung bình số lần sự cố xảy ra trong một đơn vị thời gian.
Khi đó: ( ) =

l

; ( )=1

l

l

; ( )= l

Biểu diễn mối quan hệ giữa các thông số trên như hình 1.4 sau:
Q(t)

P(t)

1
Q(t)


Miền 2: Mô tả giai đoạn sử dụng bình thường, cũng là giai đoạn chủ
yếu của tuổi thọ các phần tử. Ở giai đoạn này, các sự cố thường xảy ra ngẫu
nhiên, đột ngột do nhiều nguyên nhân khác nhau, vì vậy thường giả thiết
cường độ hỏng hóc l(t) bằng hằng số.
Miền 3: Mô tả giai đoạn già cỗi của phần tử theo thời gian, cường độ
hỏng hóc l(t) tăng dần, đó là điều tất yếu xảy ra sự cố khi t ∞.
d) Thời gian hoạt động an toàn trung bình THD
Thời gian hoạt động an toàn trung bình THD hay còn được gọi là thời gian
trung bình đến lúc hư hỏng (MTTF: Mean Time To Failure) là thời gian mà
phần tử đảm bảo hoạt động tốt.
Thời gian hoạt động được định nghĩa là giá trị trung bình của thời gian
vận hành an toàn t dựa trên số liệu thống kê t của nhiều phần tử cùng loại,
nghĩa là THD là kỳ vọng toán hay còn gọi là giá trị trung bình của biến ngẫu
nhiên t [9] và được xác định:
∞

=

=

(1.12)

t. q(t). dt

Từ (1.3) và (1.5) ta có:
∞

=

=


∞

P(t).dt =
0

P(t).dt
0

Do – t. ( )| ∞ = 0
l

Vậy với l(t) = hằng số, thì ( ) =

(phân bố hàm mũ)

∞

=

l

=

1
.
l

. dt =


Thời điểm xảy ra sự cố và thời gian sửa chữa sự cố tương ứng là những
đại lượng ngẫu nhiên, có thể mô tả trên trục thời gian như hình 1.6 dưới
đây.
t1

T1

t2

T2

t3

T3

t4

Hình 1.6: Các khoảng cách làm việc và khoảng cách phục hồi


13

Trong đó:
- T1, T2, T3 … biểu thị các khoảng thời gian hoạt động an toàn của các
phần tử giữa các lần sự cố xảy ra.
- t1, t2, t3 … là thời gian sửa chữa sự cố tương ứng.
Định nghĩa thông số dòng hỏng hóc (là cường độ hỏng hóc đối với các phần
tử không phục hồi):
( ) = lim


gian giữa hai lần sự cố liên tiếp là T1, T2 … cũng có phân bố mũ và thông số
dòng hỏng hóc là tối giản. Vậy thông số dòng hỏng hóc là: (t) = l = hằng số.
Vì vậy thông số dòng hỏng hóc và cường độ hỏng hóc thường hiểu là một,
trừ các trường hợp riêng khi thời gian hoạt động không tuân theo phân bố mũ
thì phải phân biệt.
Đối với các phần tử phục hồi thuật ngữ MTBF (Mean Time Between
Failure) được dùng thay thế cho MTTF (Mean Time To Failure).
a. Thời gian trung bình sửa chữa sự cốts
ts là kỳ vọng toán của t1, t2, t3 … là thời gian trung bình sửa chữa sự cố MTTR (Mean Time To Repair).
t =

=

t +t +
n

+t

(1.15)


14

Để đơn giản ta cũng xét xác suất của ts cũng tuân theo luật phân bố mũ.
l

Khi đó tương tự đối với xác suất hoạt động an toàn ( ) =

của phần tử,



(1.18)

Vậy thời gian trung bình sửa chữa sự cố là:
∞

t =

=

( ).

=

1

(1.19)

Phần tử có tính sửa chữa cao khi ts càng nhỏ ( càng lớn) nghĩa là chỉ
sau một khoảng thời gian ngắn phần tử đã có khả năng hoạt động lại.
T là kỳ vọng toán của T1, T2, T3, ..., Tn. Vì thời gian trung bình giữa hai
hư hỏng liên tiếp có một lần sửa chữa ngay nên:
MTBF = MTTR + MTTF  T = ts + THD
Với giả thiết T tuân theo luật phân bố mũ, giống như ở trên đã xét ta
có:
1
(1.20)
l
Dựa vào sơ đồ ở hình 1.7 ta có thể thấy được mối quan hệ giữa thời
= (T) =

thời gian t. Vậy R(t) là xác suất của giao hai sự kiện:
- Làm việc tốt tại t = 0
- Tin cậy trong khoảng 0 đến t
Giả thiết hai sự kiện này độc lập với nhau, ta có:
R(t) = A.P(t)

(1.22)

Theo luật phân bố mũ:
( )= .
Trong đó:

=

l

là hệ số sẵn sàng.

(1.23)


16

1.1.3. Vai trò độ tin cậy của hệ thống
Cuộc cách mạng khoa học kỹ thuật trong lĩnh vực công nghệ đã mở ra
một kỷ nguyên mới và bắt đầu tạo ra các hệ thống tính toán thay thế hoặc hỗ
trợ con người trong kỷ nguyên công nghệ. Nó tạo ra các hệ thống siêu phức
tạp trong các lĩnh vực về khoa học máy tính, giao thông vận tải, năng lượng
và các ngành khác của nền kinh tế. Hệ thống không đơn thuần chỉ là một hệ
thống đơn giản mà là hệ thống được đặc trưng bởi một số lượng lớn các yếu

nâng cao độ tin cậy của các hệ thống ở tất cả các giai đoạn thiết kế, thử
nghiệm, sản xuất và hoạt động là điều hết sức quan trọng và cần thiết.
1.2. Bài toán dự phòng trong hệ thống
1.2.1. Khái niệm
Dự phòng trong hệ thống hay là nâng cao độ tin cậy hệ thống bằng cách
đưa ra các đối tượng dư thừa là nguồn lực bổ sung để các đối tượng có thể
thực hiện chức năng, nhiệm vụ của mình.
Mục đích dự phòng tronghệ thống - để đảm bảo hệ thống hoạt động
bình thường sau khi xuất hiện của các lỗi trong các thành phần của nó.
1.2.2. Các cách tiếp cận của dự phòng hệ thống
Các thành phần của hệ thống phức tạp thường cho độ tin cậy thấp nên
đòi hỏi chúng ta phải có phương pháp phát triển đặc biệt như thế nào để đảm
bảo tăng cường và duy trì độ tin cậy của những hệ thống phức tạp.Để nâng
cao được độ tin cậy của các hệ thống như thế thì phải bao gồm cả sự phát
triển của phương pháp toán học, tính toán ưu tiên và đánh giá thử nghiệm.
Phương pháp tính toán về độ tin cậy của hệ thống dựa trên cơ sở lý thuyết xác
suất và quá trình ngẫu nhiên đã được áp dụng và đã đạt được những kết quả
khả quan. Từ những thông số về độ tin cậy của hệ thống thì chúng ta sẽ lập
nên các phương pháp dự phòng để nâng cao độ tin cậy của hệ thống.
Độ tin cậy và khả năng hoạt động an toàn của hệ thống là phụ thuộc vào
phần lớn vào cấu trúc hệ thống và độ tin cậy của các thành phần cấu thành hệ
thống. Các phương pháp nâng cao độ tin cậy của hệ thốngdựa trên cấu trúc của
hệ thống thông qua độ tin cậy của từng thành phần hệ thống là một bài toán
phức tạp mà để giải quyết bài toán đó thì cần đến các công cụ như lý thuyết xác