i
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
ĐINH ÚT ĐIỆP
NGHIÊN CỨU BÀI TOÁN
TÍNH ĐỘ TIN CẬY CỦA HỆ THỐNG
THÔNG QUA CẤU TRÚC CỦA HỆ THỐNG
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60 48 01 01
2014
ii
LỜI CẢM ƠN
Để hoàn thành chương trình cao học và viết luận văn này, tôi đã nhận được sự
Đinh Út Điệp iv MỤC LỤC
MỞ ĐẦU 1
CHƢƠNG 1: CƠ SỞ LÝ THUYẾT 6
1.1 Khái niệm cơ bản về độ tin cậy 6
1.1.1 Tổng quan 6
1.1.2 Định nghĩa về độ tin cậy 6
1.1.3 Dạng chung của xác suất an toàn 7
1.2 Chỉ số độ tin cậy của hệ thống 7
1.2.1 Phần tử không phục hồi 7
1.2.2 Phần tử phục hồi 13
1.3 Phƣơng pháp tính độ tin cậy của hệ thống thông qua cấu trúc của hệ thống 16
1.3.1 Sơ đồ khối độ tin cậy của các phần tử nối tiếp 17
1.3.2 Sơ đồ khối độ tin cậy của các phần tử song song 19
1.4 Các biện pháp để nâng cao độ tin cậy của hệ thống 21
1.5 Kết luận 22
CHƢƠNG 2. PHƢƠNG PHÁP ĐÁNH GIÁ ĐỘ TIN CẬY CỦA HỆ THỐNG
QUA CẤU TRÚC HỆ THỐNG 23
2.1 Bài toán tìm đƣờng đi trong đồ thị hệ thống 24
2.1.1 Thuật toán chuyển đổi sơ đồ cấu trúc logic thành sơ đồ khối 24
2.1.2 Phân loại các đỉnh và các cạnh của đồ thị liên kết 24
2.1.3 Thuật toán chuyển đổi sơ đồ cấu trúc logic sang đồ thị liên kết: 25
2.1.4 Thuật toán tìm tất cả các đƣờng đi trong ma trận liên kết 25
MỞ ĐẦU
1. Lý do chọn đề tài
Xã hội hiện đại ngày càng phát triển kéo theo đó là đời sống của con ngƣời ngày
càng đi lên, nhƣng bên cạnh còn tồn tại những thách thức và khó khăn mà cuộc
sống hiện đại mang lại. Phải kể đến công cuộc bùng nổ cách mạng khoa học kỹ
thuật đã bắt đầu tạo ra các hệ thống phức tạp trong 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ế. Đây là những hệ thống có
tính ứng dụng cao, tham gia vào trong tất cả các lĩnh vực của đời sống của con
ngƣời. Tuy nhiên, cũng chính vì điều này mà xã hội luôn phải đối mặt với nguy cơ
các thiết bị không sẵn sàng để hoạt động một cách đúng đắn, việc thao tác sai cùng
với những sai lầm đáng tiếc trong quá trình thiết kế, chế tạo thiết bị, làm cho cấu
trúc hệ thống bị phá vỡ, các chức năng của hệ thống hoạt động không chính xác. Mà
nhƣ ta đã biết nó không đơn thuần chỉ là một hệ thống đơn giản mà là hệ thống bao
gồm một số lƣợng lớn các yếu tố thành phần có cấu trúc phức tạp với các chƣơng
trình điều khiển các hoạt động của nó.
Thấy đƣợc quy cơ tiềm tàng đang xảy ra đối với mỗi hệ thống, ta càng hiểu rõ
hơn tầm quan trọng của các vấn đề liên quan đến độ tin cậy, khả năng sống sót và
việc phát triển nhanh chóng các phƣơng pháp để đảm bảo độ tin cậy cao 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. Trong các
hệ thống kỹ thuật hiện đại nếu không đảm bảo đƣợc độ tin cậy thì hệ thống coi nhƣ
không tồn tại. Chính điều này đòi hỏi phải phát triển phƣơng pháp đặc biệt để đảm
bảo, tăng cƣờng và duy trì độ tin cậy của những hệ thống này, các phƣơng pháp
toán học dựa trên tính toán ƣu tiên và đánh giá thử nghiệm, phƣơng pháp đánh giá
dựa trên cơ sở lý thuyết xác suất và quá trình ngẫu nhiên, đã và đang đƣợc áp dụng
và đạt đƣợc những kết quả khả quan. 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 khó, mà để giải nó cần đến các công cụ nhƣ lý thuyết xác suất, lý thuyết đồ thị,
logic. Vấn đề độ tin cậy tiếp tục là một trong những chìa khóa để phát triển công
nghệ hiện đại.
đầu tiên là nghiên cứu thuật toán chuyển từ sơ đồ cấu trúc logic của hệ thống sang
sơ đồ khối, sau đó sử dụng đồ thị và ma trận liên kết lƣu trữ các kết quả trung gian
làm cơ sở để tính toán, các thuật toán tối thiểu hàm logic, thuật toán trực giao hoá
các toán tử logic và chuyển từ mô hình logic sang mô hình đại số để tính các giá trị
xác suất có liên quan. Và để chứng minh hệ thống đã xây dựng hoạt động đúng đắn
tôi sẽ đi xét ví dụ về một hệ thống máy chủ, từ đó đƣa ra các kết quả để chứng minh
lập luận của mình.
3
Hy vọng luận văn sẽ là một tài liệu tham khảo có ích đối với tất cả các bạn sinh
viên, các thầy cô khi nghiên cứu về lĩnh vực này.
2. Mục đích nghiên cứu
Mục đích nghiên cứu của đề tài là nghiên cứu các bài toán tính độ tin cậy của hệ
thống thông qua cấu trúc hệ thống và xây dựng thành công phần mềm đánh giá độ
tin cậy của hệ thống. Khi biết đƣợc độ tin cậy của hệ thống chúng ta có thể lên kế
hoạch bảo trì, lên kế hoạch dự phòng, nâng cao độ tin cậy, tránh đƣợc các sự cố lỗi
có thể gây ra.
3. Giả thuyết khoa học
Nếu xây dựng thành công phần mềm đánh giá độ tin cậy của hệ thống có sử
dụng phƣơng pháp đánh giá độ tin cậy một cách đúng đắn sẽ là cơ sở, nền tảng cho
sự ra đời của các phần mềm đánh giá độ tin cậy của các hệ thống phức tạp sau này.
4. Nhiệm vụ nghiên cứu
Xuất phát từ mục đích trên, nhiệm vụ của đề tài đặt ra nhƣ sau:
- Nghiên cứu các khái niệm liên quan đến độ tin cậy của hệ thống, phƣơng pháp
tính độ tin cậy qua cấu trúc hệ thống.
- Phƣơng pháp đánh giá độ tin cậy của hệ thống qua cấu trúc hệ thống.
- 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.
- Sử dụng chƣơng trình tính độ tin cậy đã xây dựng để tính độ tin cậy và khả
năng hệ thống hoạt động an toàn thông qua ví dụ cụ thể.
5
CHƢƠNG 1: CƠ SỞ LÝ THUYẾT
1.1 Khái niệm cơ bản về độ tin cậy
1.1.1 Tổng quan
Độ tin cậy là đặc tính then chốt trong sự phát triển kỹ thuật, đặc biệt là khi xuất
hiện những hệ thống phức tạp nhằm hoàn thành những chức năng quan trọng trong
các lĩnh vực công nghiệp khác nhau. Định lƣợng độ tin cậy của phần tử hoặc của cả
hệ thống đƣợc đánh giá bằng cách phân tích, tính toán các chỉ số của độ tin cậy, dựa
trên hai yếu tố cơ bản là: Tính làm việc an toàn và tính sửa chữa đƣợc.
Quan niệm về hệ thống, thiết bị kỹ thuật theo cách nhìn của độ tin cậy sẽ làm
cơ sở cho việc tính toán các chỉ số của độ tin cậy cho các hệ thống với các mức độ
và phƣơng pháp dự phòng khác nhau.
“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 đổi có tổ chức để tạo kết quả đầu ra”.
Hay “Hệ thống là một tập hợp gồm nhiều phần tử có các mối quan hệ ràng
buộc tương tác lẫn nhau để thực hiện một mục đích chung”[6].
“Hệ thống thông tin là một tập hợp và kết hợp của các phần cứng, phần mềm và
các hệ mạng truyền thông đƣợc xây dựng và sử dụng để thu thập, tạo, tái tạo, phân
phối và chia sẻ các dữ liệu, thông tin và tri thức nhằm phục vụ các mục tiêu của tổ
chức”[10,11].
Phần tử là một bộ phận tạo thành hệ thống mà trong quá trình nghiên cứu độ tin
cậy nhất định nó đƣợc xem nhƣ là một tổng thể không chia cắt đƣợc (ví dụ nhƣ: linh
kiện, thiết bị… ) mà độ tin cậy đã cho trƣớc, hoặc xác định dựa trên những số liệu
thống kê.
Phần tử ở đây có thể hiểu theo một cách rộng rãi hơn, bản thân phần tử cũng có
thể có cấu trúc phức tạp, nếu xét riêng nó là một hệ thống.
1.2.1 Phần tử không phục hồi
Phần tử không phục hồi[2] 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.
8
Những thông số cơ bản của phần tử không phục hồi là:
a. Thời gian vận hành an toàn .
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 = thì
phần tử bị sự cố. Khoảng thời gian đƣợ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 là một đại lƣợng ngẫu nhiên có
các giá trị trong khoảng 0 ≤ ≤ ∞.
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} (1.2)
Vì là đại lƣợng ngẫu nhiên liên tục nên:
- Q(t) đƣợc gọi là hàm phân phối của biến ngẫu nhiên liên tục .
- q(t) là hàm mật độ phân phối xác suất của .
Trên hình 1.1[1], biểu diễn hàm mật độ phân phối xác suất của thời gian trung
bình vận hành an toàn. Theo tính chất của hàm mật độ phân phối xác suất của biến
ngẫu nhiên liên tục, ta có:
q(t)=Q’(t) {Đạo hàm bậc 1của hàm phân phối xác suất }, do đó:
Trong đó thỏa mãn tính chất :
q(t)
t
dQ(t)
0
Hình 1.1: Biểu diễn hàm mật độ phân phối xác suất
vị thời gian trong khoảng thời gian ∆t.
là xác suất có điều kiện, là xác suất để phần tử hỏng hóc
trong khoảng thời gian từ t đến (sự kiện A) nếu phần tử đó hoạt động tốt
đến thời điểm t (sự kiện B).
Theo lý thuyết xác suất, xác suất nhân giữa hai sự kiện A và B là:
P(AB) = P(A).P(B|A) = P(B).P(A|B)
Hay:
Nếu (A kéo theo B: Nếu A xảy ra thì B xảy ra) theo giả thiết ban đầu khi
thì ta có: P(AB) = P(A)
Và
Từ (1.8) và (1.9) suy ra: Công thức (1.10) cho ta quan hệ giữa bốn đại lƣợng: cƣờng độ hỏng hóc, hàm 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ó:
(do đạo hàm của 1 bằng 0)
Thay vào (1.10) ta có: <=>
11 Do P(0) = 1
Công thức (1.11) cho phép tính đƣợc độ tin cậy của phần tử không phục hồi
khi đã biết cƣờng độ hỏng hóc (t), mà cƣờng độ hỏng hóc (t) này 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 (t) = = 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.
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 dựa trên số liệu thống kê của nhiều phần tử cùng loại, nghĩa là T
HD
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 [9] và đƣợc
xác định:
Từ (1.3) và (1.5) ta có:
Sử dụng phƣơng pháp tính tích phân từng phần:
Đặt u=t; dv=P’(t)dt ta có:
Do
Vậy với (t) = hằng số, thì (phân bố hàm mũ)
Trong đó: Ngƣời ta thƣờng chọn [ ] = 1/giờ và [T
HD
] = giờ
13 1.2.2 Phần tử phục hồi
Phần tử phục hồi [2] là phần tử khi đƣa vào sử dụng đến khi xảy ra sự cố có thể
đƣợc đem đi sửa chữa phục hồi. Trong quá trình vận hành phần tử chỉ nhận một
trong hai trạng thái: Trạng thái hoạt động an toàn và trạng thái sửa chữa định kỳ
hoặc sửa chữa sự cố.
Những thông số cơ bản của phần tử phục hồi là:
a. Thông số dòng hỏng hóc
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
1
2
3
4
T
1
T
2
T
3
Hình 1.4
14
bố mũ, với cƣờng độ hỏng hóc = hằng số, khi đó khoảng thời gian giữa hai lần sự
cố liên tiếp là T
1
, T
2
… 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) = = 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.
Và hàm mật độ phân bố xác suất là:
Vậy thời gian trung bình sửa chữa sự cố là:
15
Phần tử có tính sửa chữa cao khi
s
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 T
1
, T
2
, T
3
, , T
n
. 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 =
s
+ T
HD
Với giả thiết T tuân theo luật phân bố mũ, giống nhƣ ở trên đã xét ta có:
Dựa vào sơ đồ ở hình 1.5[7] ta có thể thấy đƣợc mối quan hệ giữa thời gian
trung bình để bị lỗi, phát hiện lỗi và sửa lỗi:
- Các nhánh: Đƣợc vẽ bằng các khối hình chữ nhật mô tả trạng thái tốt của
phần tử. Phần tử bị hỏng tƣơng ứng với việc xóa khối của phần tử đó ra khỏi sơ đồ.
Nhánh và nút tạo thành mạng lƣới nối liền nút phát và nút tải của sơ đồ. Có thể
có nhiều đƣờng nối từ nút phát đến nút tải, mỗi đƣờng gồm nhiều nhánh nối tiếp, vì
vậy số đƣờng đi từ nút phát đến nút tải là rất lớn đối với các hệ thống phức tạp.
Theo sơ đồ:
- Trạng thái tốt của hệ thống là trạng thái trong đó có ít nhất một đƣờng có thể
đi từ nút phát đến nút tải.
- Trạng thái hỏng của hệ thống khi nút phát bị tách rời với nút tải do hỏng hóc
của phần tử trung gian.
17
1.3.1 Sơ đồ khối độ tin cậy của các phần tử nối tiếp
Lúc này coi các phần tử có độ tin cậy cần đƣợc xác định sẽ đƣợc xem nhƣ một
hệ thống phức tạp S đƣợc tạo nên bởi các phần tử (khối) riêng biệt [8], ví dụ nhƣ
trong các hệ thống tự động hoặc thông tin đƣợc xây dựng trên cơ sở các phần tử
rơle hoặc các phần tử bán dẫn. Nhiệm vụ tính toán độ tin cậy của một hệ thống sẽ là
việc xác định các chỉ số độ tin cậy của nó nếu nhƣ đã biết các chỉ số độ tin cậy của
các phần tử riêng biệt và cấu trúc của hệ thống, tức là đặc tính liên hệ giữa các phần
tử theo cách nhìn của độ tin cậy.
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. Trong trƣờng hợp này hệ thống S đƣợc tạo nên bởi bởi các phần tử
nối tiếp nhau. Xét sơ đồ tin cậy của hệ thống gồm n phần tử nối tiếp nhƣ hình
1.6[8]:
Trong đó N là nút nguồn (nút phát) và T là nút tải. Cho rằng trở ngại của các
phần tử là độc lập với nhau. Giả sử đã biết cƣờng độ hỏng hóc của n phần tử lần
lƣợt là
1
và đã biết cƣờng độ hỏng hóc của chúng. Nhƣ thế toàn bộ hệ thống tuân theo quy
luật hàm số mũ độ tin cậy [7]s: Trong đó: đƣợc gọi là cƣờng độ hỏng hóc của hệ thống và bằng tổng các cƣờng
độ hỏng hóc các phần tử của nó:
Thời gian hoạt động an toàn trung bình của hệ thống là:
Giả thiết thời gian phục hồi (thời gian sửa chữa sự cố) của phần tử có phân bố
mũ, khi đó cƣờng độ phục hồi
i
= 1/
i
, từ đây có thể xác định đƣợc thời gian phục
hồi trung bình của hệ thống là:
Hoặc:
Trong đó: = 1/
H
và ta thấy T
H
>>
H
Hệ số sẵn sàng của hệ thống là:
Hàm tin cậy của toàn hệ thống sẽ là:
Xác suất trạng thái hỏng của hệ thống:
Các công thức trên cho phép ta đẳng trị các phần tử nối tiếp thành một phần tử
tƣơng đƣơng khi biến đổi sơ đồ.
Ta có xác suất sự cố Q
H
(t) [2] của toàn hệ thống, hệ thống có sự cố khi toàn bộ n
phần tử bị sự cố:
Trong đó Q
i
(t) với i = 1 n là xác suất sự cố của phần tử thứ i trong khoảng thời
gian t khảo sát
Giả thiết độ tin cậy tuân theo quy luật hàm số mũ:
Thì ta có xác suất sự cố của toàn hệ thống [7] là:
Hình 1.7: Sơ đồ song song
1
2
n
N
T
20
Độ tin cậy của hệ thống: So sánh công thức 1.35 này với công thức 1.24 ở trên ta thấy rõ ràng xác suất làm
việc không có sự cố của hệ thống song song luôn cao hơn xác suất làm việc không
có sự cố của hệ thống nối tiếp.
Cƣờng độ hỏng hóc của hệ thống:
Nếu n phần tử hoàn toàn nhƣ nhau thì
Vì mọi hƣ hỏng đều có nguồn gốc là các lỗi gây trở ngại đến hoạt động của hệ
thống ta phải lựa chọn và phối hợp nhiều giải pháp bảo vệ chống lỗi. Các giải pháp
có thể là:
- Ngăn trở các lỗi có thể xuất hiện trong hệ thống bằng cách sử dụng các hệ
thống tiêu chuẩn hóa, việc này có tác dụng giảm các lỗi do thiết kế hệ thống.
- Chọn các linh kiện có độ tin cậy cao, cải thiện điều kiện làm việc của chúng
nhƣ tản nhiệt, tránh nhiễu điện từ, bảo vệ chống dao động điện áp nguồn.
- Sử dụng các phần cứng và phần mềm quen thuộc đối với ngƣời sử dụng sẽ
giảm đƣợc các lỗi tƣơng tác.
- Loại trừ các lỗi bằng cách phát hiện và sửa lỗi sớm, trƣớc khi các lỗi có thể
gây ra sai lệch.
- Chấp nhận lỗi trong hệ thống bằng có chế dự phòng (redundancy).
- Hệ thống có dự phòng cho phép tồn tại các lỗi bằng cơ chế sống chung với
lỗi, có khả năng che chắn các lỗi. Việc dự phòng có thể chỉ tác động lên một bộ
phận hệ thống hoặc dự phòng toàn bộ. Nhiều nhà chế tạo theo phƣơng pháp dự
phòng bộ phận vì nó kinh tế hơn.
Sau khi đã nhận dạng các chức năng dễ mắc lỗi trong hệ thống bằng cách
nghiên cứu xác suất hƣ hỏng của từng bộ phận ta tạo nên các hệ con có dự phòng.
Ví dụ đối với server là có hai nguồn cấp, đĩa gƣơng… Giải pháp này đƣợc dự kiến
trong thiết kế hệ thống, tuy nhiên trong quá trình làm việc có thể sau vài năm hệ
thống không còn đủ khả năng che chắn lỗi cho các hệ con. Ví dụ một nguồn hƣ
hỏng do quá điện áp làm nguồn dự phòng mắc song song với nó cũng bị ảnh hƣởng.
Nguồn dự phòng này có thể chỉ che chắn đƣợc 9 trong 10 lỗi có thể xảy ra.
Dự phòng có thể là bậc n, nghĩa là số hệ con có thể lớn hơn 1. Dự phòng đơn
giản nhất là dự phòng kép nghĩa là có hai hệ con đƣợc điều khiển để thay thế cho
nhau. Một hệ có dự phòng có thể bao gồm các hệ con giống nhau gọi là hệ đồng
nhất (homogeneous redundancy) hoặc không đồng nhất (heterogeneous
Copyright: Tài liệu đại học ©