BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - LUẬN VĂN THẠC SỸ KHOA HỌC NGHIÊN CỨU KỸ THUẬT XÂY DỰNG PHẦN MỀM CHỊU LỖI ÁP DỤNG CHO HỆ THỐNG NHÚNG NGÀNH: CÔNG NGHỆ THÔNG TIN MÃ SỐ:…………… ĐÀO NGỌC KIÊN Người hướng dẫn khoa học: PGS.TS HUỲNH QUYẾT THẮNG HÀ NỘI 2009 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng LỜI CAM ĐOAN Tôi – Đào Ngọc Kiên, học viên lớp Cao học CNTT 2006-2008 Trường Đại học Bách Khoa Hà Nội – cam kết Luận văn tốt nghiệp cơng trình nghiên cứu thân hướng dẫn PGS.TS Huỳnh Quyết Thắng, Viện CNTT-TT, Trường Đại học Bách Khoa Hà Nội Các kết nêu Luận văn tốt nghiệp trung thực, khơng chép tồn văn cơng trình khác Hà Nội, ngày 30, tháng 10, năm 2009 Học viên: Đào Ngọc Kiên Lớp : Cao Học CNTT 06-08 Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng LỜI CẢM ƠN Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo, PGS.TS Huỳnh Quyết Thắng, Viện Công Nghệ Thông Tin Truyền Thông, trường Đại học Bách Khoa Hà Nội, khuyến khích tận tình hướng dẫn tơi suốt trình thực luận văn Nhờ quan tâm bảo ý kiến đóng góp quý báu thầy, tơi hồn thành luận văn Tôi xin chân thành cảm ơn tập thể thầy, cô giáo trường Đại học Bách Khoa Hà Nội nói chung Viện Cơng Nghệ Thơng Tin Truyền Thơng nói riêng tận tình giảng dạy truyền đạt cho kiến thức, kinh nghiệm quý báu suốt năm học vừa qua Tôi xin cảm ơn đồng nghiệp công ty tạo điều kiện thời gian để tơi học tập hồn thành luận văn Cuối cùng, tơi xin chân thành cảm ơn gia đình, người thân hết lịng giúp đỡ hỗ trợ vật chất lẫn tinh thần giúp yên tâm học tập nghiên cứu suốt trình học tập thực luận văn Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng MỤC LỤC LỜI CAM ĐOAN LỜI CẢM ƠN MỤC LỤC DANH MỤC CÁC HÌNH VẼ DANH MỤC CÁC BẢNG DANH MỤC CÁC TỪ VIẾT TẮT MỞ ĐẦU 10 Tính cấp thiết đề tài 10 Mục đích nghiên cứu 11 Nhiệm vụ nghiên cứu 12 Phạm vi nghiên cứu 12 Cấu trúc luận văn 12 Phương pháp nghiên cứu 13 CHƯƠNG - TỔNG QUAN VỀ XÂY DỰNG PHẦN MỀM CHỊU LỖI 14 1.1 Độ tin cậy phần mềm 14 1.2 Tư tưởng “Dự phòng” xây dựng phần mềm chịu lỗi 19 1.2.1 Dự phòng phần mềm 19 1.2.2 Dự phòng liệu 19 1.3 Biện pháp phục hồi phần mềm lỗi 20 1.3.1 Phục hồi quay lui 20 1.3.2 Phục hồi tiến 21 1.4 Các hướng tiếp cận kỹ thuật xây dựng phần mềm chịu lỗi 21 1.4.1 Kỹ thuật đa thiết kế 22 1.4.1.1 Kỹ thuật lập trình N phiên NVP (N-version programming) 23 1.4.1.2 Kỹ thuật khối phục hồi RcB (Recovery Block) 24 1.4.2 Kỹ thuật đa liệu 26 TỔNG KẾT CHƯƠNG 29 CHƯƠNG – TỔNG QUAN VỀ HỆ THỐNG NHÚNG THỜI GIAN THỰC 30 2.1 Khái niệm thời gian thực 31 2.2 Cơ chế ngắt 32 2.3 Các tác vụ task 33 2.4 Cơ chế lập lịch 36 2.4.1 Lập lịch có chu kỳ 37 2.4.2 Lập lịch không theo chu kỳ 37 2.4.3 Lập lịch theo kiểu chiếm quyền thực thi không chiếm quyền thực thi 37 2.4.4 Phương thức xử lý task có mức ưu tiên 39 2.4.5 Lập lịch ưu tiên deadline sớm 39 2.5 Cơ chế truyền thông 40 2.5.1 Semaphore 40 2.5.2 Hộp thư mailbox 41 2.5.3 Hàng đợi đường ống (Queues Pipe) 42 2.6 Khác biệt hệ thống nhúng thời gian thực so với hệ thống nói chung 42 2.7 Các lỗi thường gặp hệ thống nhúng 43 TỔNG KẾT CHƯƠNG 45 CHƯƠNG – KỸ THUẬT XÂY DỰNG PHẦN MỀM CHỊU LỖI ÁP DỤNG CHO HỆ THỐNG NHÚNG 47 3.1 Ý tưởng ban đầu xây dựng phần mềm chịu lỗi cho hệ thống nhúng 47 Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng 3.2 Lỗi hệ thống nhúng chế xử lý 49 3.2.1 Xử lý lỗi thời gian (Deadline error) 49 3.2.2 Xử lý lỗi lập trình (Programming error) 50 3.2.3 Xử lý lỗi phần cứng (Hardware error) 51 3.3 Mơ hình chịu lỗi cho hệ thống nhúng đơn nút 51 3.3.1 Mơ hình hệ thống chịu lỗi mức task 52 3.3.2 Mô hình hệ thống chịu lỗi mức ứng dụng 53 3.3.3 Chuyển đổi chế độ ứng dụng 54 3.4 Kiến trúc chịu lỗi cho hệ thống nhúng đơn nút 55 3.4.1 Bộ điều khiển ftcontroller 57 3.4.2 Bộ giám sát ứng dụng ftappmon 58 3.4.3 Tương tác thành phần 59 3.4.4 Luồng xử lý thành phần chịu lỗi 61 3.4.5 Tương tác góc nhìn thread 62 3.5 Mơ hình chịu lỗi dự phịng cho hệ thống nhúng đa nút 63 3.5.1 Mơ hình chịu lỗi dự phịng 63 3.5.2 Các loại hình dự phịng 64 3.5.3 Lựa chọn loại hình dự phịng áp dụng cho hệ thống nhúng 65 3.6 Kiến trúc chịu lỗi dự phòng cho hệ thống nhúng đa nút 66 3.6.1 Kiến trúc phần mềm chịu lỗi nút 67 3.6.2 Kiến trúc phần mềm chịu lỗi nhiều nút 67 3.6.3 Bộ quản lý dự phòng FTRedundancy 69 3.6.4 Bộ quản lý FTreplicamngr 69 3.6.5 Tương tác thành phần chịu lỗi 70 3.6.6 Cơ chế đảm bảo tính quán ngữ cảnh task 72 TỔNG KẾT CHƯƠNG 75 CHƯƠNG – THỬ NGHIỆM VÀ ĐÁNH GIÁ 77 4.1 Thử nghiệm ứng dụng áp dụng mơ hình chịu lỗi 77 4.1.1 Giới thiệu tốn vệ tinh thám khơng gian 77 4.1.2 Thử nghiệm đánh giá kết 78 4.2 Thử nghiệm độ tin cậy hệ thống 86 4.2.1 Mơ tả chương trình 86 4.2.2 Thử nghiệm nhận xét kết 88 TỔNG KẾT CHƯƠNG 90 KẾT LUẬN 91 Các nội dung hoàn thành luận văn 91 Các đóng góp khoa học 92 Hướng phát triển luận văn 93 TÀI LIỆU THAM KHẢO 95 TÓM TẮT LUẬN VĂN 96 THESIS SUMARY 97 Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng DANH MỤC CÁC HÌNH VẼ Hình 1.1 Kỹ thuật nâng cao độ tin cậy phần mềm pha phát triển 16 Hình 1.2 Mối quan hệ fault, error failure 17 Hình 1.3 Mối quan hệ fault, error failure 18 Hình 1.4 Cấu trúc hoạt động kỹ thuật N phiên lập trình (NVP) 24 Hình 1.5 Cấu trúc hoạt động kỹ thuật khối phục hồi (RcB) 26 Hình 1.6 Mơ hình kỹ thuật đa liệu 27 Hình 1.7 Mơ hình kỹ thuật đa liệu 27 Hình 1.8 Mơ hình kỹ thuật đa liệu 28 Hình 2.1 Vòng lặp pooling 32 Hình 2.2 Cơ chế ngắt 33 Hình 2.3 Cấu trúc task 34 Hình 2.4 Cấu trúc mã lệnh task 35 Hình 2.5 Mơ hình trạng thái task 37 Hình 2.6 Lập lịch có khơng có chiếm quyền thực thi 38 Hình 2.7 Cơ chế truyền thông qua semafore 41 Hình 3.1 Giản đồ trạng thái task chịu lỗi 52 Hình 3.2 Mơ hình task chịu lỗi 53 Hình 3.3 Chuyển đổ chế độ ứng dụng có lỗi 54 Hình 3.4 Kiến trúc chịu lỗi cho hệ thống nhúng đơn nút 56 Hình 3.5 Bộ điều khiển ftcontroller 57 Hình 3.6 Bộ giám sát ứng dụng ftappmon 58 Hình 3.7 Tương tác thành phần chịu lỗi 59 Hình 3.8 Tương tác thành phần chịu lỗi 60 Hình 3.9 Luồng xử lý thành phần chịu lỗi 61 Hình 3.10 Tương tác thành phần chịu lỗi góc nhìn thread 62 Hình 3.11 Đặc tả triển khai ứng dụng mơ hình dự phịng 64 Hình 3.12 Kiến trúc phần mềm chịu lỗi nút 67 Hình 3.13 Kiến trúc phần mềm chịu lỗi nhiều nút 68 Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng Hình 3.14 Bộ quản lý dự phòng FTRedundancy 69 Hình 3.15 Bộ quản lý FTreplicamngr 70 Hình 3.16 Tương tác thành phần chịu lỗi 71 Hình 3.17 Xử lý thay dự phịng có lỗi nút 72 Hình 3.18 Cơ chế hoạt động kiến trúc chịu lỗi dự phòng 73 Hình 4.1 Các thành phần ứng dụng chịu lỗi mô 79 Hình 4.2 Các task ứng dụng chịu lỗi mơ 80 Hình 4.3 Mơ hình ứng dụng chịu lỗi với hai chế độ 81 Hình 4.4 Quá trình chuyển đổi chế độ chịu lỗi có lỗi 82 Hình 4.5 Giao diện cấu hình hệ thống 83 Hình 4.6 Kết chương trình chạy (1) 84 Hình 4.7 Kết chương trình chạy (2) 85 Hình 4.8 Cấu trúc hoạt động chương trình mơ kỹ thuật RcB 87 Hình 4.9 Giao diện chương trình mơ kỹ thuật RcB 88 Hình 4.10 Số lỗi khơng phát chương trình mơ kỹ thuật RcB 89 Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng DANH MỤC CÁC BẢNG Bảng 1.1 Các khái niệm liên quan đến độ tin cậy phần mềm 17 Bảng 3.1 Bảng chuyển đổi chế độ ứng dụng lỗi 54 Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng DANH MỤC CÁC TỪ VIẾT TẮT STT Từ viết tắt B 0B 10 11 12 13 14 15 16 FT NCP NVP OMG QoS RCB RTB Giải nghĩa 2B Fault Tolerant N- Copy Programming N- Version Programming Object management group Quality of Services Recovery block Retry block Acceptance test AT RTOS Real-time operating system EDF Earlest deadline first ft_task Fault tolerant task ftcontroller Fault tolerant task controler ftappmon Fault tolerant application monitor ftredundancymgr Fault tolerant redundancy manager ftreplicamngr Fault tolerant replica manager FTAppli Fault tolerant application Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng MỞ ĐẦU Tính cấp thiết đề tài Hệ thống nhúng sử dụng rộng rãi nhiều lĩnh vực, chẳng hạn điều khiển điện tử, tự động hóa nhà, văn phịng, cơng nghiệp tơ Mặc dù khơng tồn định nghĩa xác thuật ngữ nói chung hệ thống nhúng xem hệ thống phần cứng, phần mềm thực chức cụ thể, thường phần hệ thống lớn Điều ngụ ý giải thích cho chữ "nhúng" thuật ngữ (là phần nhúng vào hệ thống lớn hơn) Ngoài hệ thống nhúng thiết kế để thực chức cụ thể xác định trước, trái với mục đích chung chung hệ thống máy tính bình thường (mainframe, máy tính để bàn, máy tính xách tay, vv…) Hầu hết hệ thống nhúng thời gian thực phải thỏa mãn ràng buộc thời gian Một số hệ thống nhúng có u cầu độ tin cậy, tính sẵn sàng an toàn cao hỏng hóc hệ thống gây nguy hiểm cho tính mạng người làm tổn hại đến hoạt động chung toàn hệ thống Những hệ thống phân loại thành hệ thống an toàn cao (safety-critical) hệ thống quan trọng (mission-critical) Ví dụ hệ thống critical system hệ thống công nghiệp ô tô, điện tử hàng không, điều khiển quân hay không gian vũ trụ Các hệ thống critical có độ tin cậy cao nhiều so với hệ thống thương mại thơng thường Ví dụ thiết bị vận chuyển hành khách hàng không thiết kế với 10-9 lỗi hoạt động (tương đương với lỗi sau 114.000 năm) Yêu cầu tương tự áp dụng hệ thống điều khiển đường sắt Ngoài hệ thống điều khiển vệ tinh không gian lại yêu cầu độ tin cậy cao hầu hết hệ thống phải hoạt động điều kiện q trình bảo dưỡng Vì hệ thống nhúng critical kết hợp phần cứng phần mềm nên nhu cầu cấp thiết giảm thiểu hỏng hóc liên quan đến hai lĩnh vực Mặc dù độ tin cậy phần cứng ngày phát triển nhiên lỗi thời xảy ra, đặc biệt mơi trường lượng cao hay có xạ lớn chẳng hạn hệ thống không gian Về lỗi phần mềm, gia tăng không ngừng chức hệ thống làm tăng lên độ phức tạp phần mềm thường nguyên nhân gây lỗi phần mềm Bất chấp nhiều nỗ lực áp dụng nhiều pha phát triển bao gồm pha test, nhiều lỗi phần mềm Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 10 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng Kết thử nghiệm thể đây: Hình 4.5 Giao diện cấu hình hệ thống Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 83 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng mbuff: kernel shared memory driver v0.7.2 for Linux 2.4.18-ocera-1.0.0 mbuff: (C) Tomasz Motylewski et al., GPL mbuff: registered as MISC device minor 254 RTLinux Extensions Loaded (http://www.fsmlabs.com/) ***************** FT_Controller ****************** ****************** FT_Appli_Monitor ****************** ********** FT_Appli ********** FT_Appli_Monitor : ft_tasks_tab[ft_task_id].ft_normal_routine=-121588740 ft_normal_routine=-121588740 FT_Appli_Monitor : ft_tasks_tab[ft_task_id].ft_normal_routine=-121588740 ft_normal_routine=-121588740 Application : ap_i=2 ap_task_behavior=FT_TASK_NORMAL Application : ft-task 2, thread -144637952 start, ứng xử normal chưa start Application : ft-task 2, thread -144637952 chuyển sang trạng thái chờ, ứng xử normal chưa start Application : ft-task 2, thread -144637952 chuyển sang trạng thái chạy, ứng xử normal Application : ft-task 2, thread -144637952, no_cycle 1, ứng xử normal Application : ap_i=1 ap_task_behavior=FT_TASK_NOT_STARTED Application : ft-task 1, thread -146178048 start, ứng xử normal chưa start Application : ft-task 1, thread -146178048 chuyển sang trạng thái chờ, ứng xử normal chưa start Application : ft-task 2, thread -144637952, no_cycle 2, ứng xử normal Application : ft-task 2, thread -144637952, no_cycle 3, ứng xử normal Application : ft-task 2, thread -144637952, no_cycle 4, ứng xử normal Application : ft-task 2, thread -144637952, no_cycle 5, ứng xử normal Application : ft-task 2, thread -144637952 cancelling, ứng xử normal Hình 4.6 Kết chương trình chạy (1) Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 84 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng FT_Controller : System call : task (-144637952) syscall PTHREAD_KILL (2) FT_Controller : Hủy normal thread !!! ft task id ft normal thread kid -144637952 FT_Controller : Tạo degraded thread định kỳ!!! ft task id ft degraded thread kid -145915904 FT_Appli_Monitor : Hàm ft_notify_failed_thread FT_Appli_Monitor : trước chuyển ft_current_appli_mode= {1 , FT_MODE_INIT} FT_Appli_Monitor : ft_new_appli_mode= {2 , FT_MODE_DEGRADED} FT_Controller : Tạo normal thread định kỳ!!! ft task id ft normal thread kid -146178048 FT_Controller : Hủy normal thread !!! ft task id ft normal thread kid -144637952 FT_Controller : Tạo degraded thread định kỳ !!! ft task id ft degraded thread kid -145915904 Application : ft-task 1, thread -146178048 chuyển sang trạng thái chạy, ứng xử normal Application : ft-task 1, thread -146178048, n Application : ft-task 1, thread -146178048, no_cycle 2, ứng xử normal Application : ft-task 1, thread -146178048, no_cycle 3, ứng xử normal Application : ft-task 1, thread -146178048, no_cycle 4, ứng xử normal Application : ft-task 1, thread -146178048, no_cycle 5, ứng xử normal Application : ft-task 1, thread -146178048, no_cycle 20, ứng xử normal Application : ft-task 2, thread -145915904, no_cycle 20, ứng xử degraded Hình 4.7 Kết chương trình chạy (2) Nhận xét: Với ứng dụng thử nghiệm ta thấy kết chạy theo thiết kế chịu lỗi đề Ứng dụng chạy môi trường hệ điều hành thời gian thực RTLinux với hai mức độ chịu lỗi mức ứng dụng mức task Ở mức độ ứng dụng, có kiện bất thường xảy kiện PTHREAD_KILL khiến thread bị hủy ứng dụng nhận biết tiến hành chuyển từ chế độ bình thường sang chế độ chịu lỗi FT_MODE_DEGRADED Ở mức độ task, ft-task có hai chế độ hoạt động chế độ bình thường chế độ chịu lỗi Khi kiện bất thường xảy ft-task chuyển từ cách ứng xử bình thường sang cách ứng xử chịu lỗi Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 85 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng Hoạt động ứng dụng thể khả chịu lỗi hệ thống, chứng minh tính khả thi việc áp dụng kỹ thuật chịu lỗi mơ hình chịu lỗi đề xuất cho hệ thống nhúng thời gian thực 4.2 Thử nghiệm độ tin cậy hệ thống Ngoài vấn đề thử nghiệm áp dụng kỹ thuật chịu lỗi chứng minh tính khả thi áp dụng vào hệ thống nhúng, câu hỏi đặt thêm độ tin cậy hệ thống Việc áp dụng kỹ thuật chịu lỗi RcB với khối chương trình khối thay làm tăng độ tin cậy hệ thống Ở mơ hình chịu lỗi dựa kỹ thuật RcB mà ta áp dụng cho hệ thống nhúng, khối thay cách ứng xử cách ứng xử thay task Hiện ta sử dụng cách ứng xử cho task, ứng xử bình thường ứng xử chịu lỗi Tuy nhiên ta biết kỹ thuật RcB, số lượng khối thay không giới hạn Câu hỏi đặt để đảm bảo độ tin cậy hệ thống số lượng khối thay hợp lý? Đặc biệt hệ thống nhúng với tài nguyên giới hạn số lượng cách ứng xử cho task hợp lý? Chính từ câu hỏi nên ta xây dựng ứng dụng thử nghiệm kỹ thuật RcB với số khối thay khác để tìm mối liên hệ số khối thay với độ tin cậy hệ thống Từ trả lời câu hỏi hệ thống nhúng với tài nguyên giới hạn số lượng cách ứng xử cho task hợp lý 4.2.1 Mơ tả chương trình Chương trình xây dựng nhằm mơ hoạt động phần mềm áp dụng kỹ thuật chịu lỗi RcB kỹ thuật sử dụng mơ hình chịu lỗi cho hệ thống nhúng Mơ hình chương trình mô tả sau: Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 86 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng Hình 4.8 Cấu trúc hoạt động chương trình mơ kỹ thuật RcB Mơ hoạt động: Khi có u cầu gửi đến chương trình, kiểm tra chấp nhận tiếp nhận yêu cầu kích hoạt khối thay để thực u cầu Kết mà khối thay trả kiểm tra tính đắn Nếu kết đắn kết trả cho chương trình Nếu kết khơng đắn, khối thực kích hoạt khối thay để thực yêu cầu Các kết trả khối thay kiểm tra chấp nhận xem xét Nếu tất kết trả khơng hệ thống rơi vào trạng thái lỗi phát Nhằm thể tính chất ngẫu nhiên không nhớ lỗi phần mềm chịu lỗi, chương trình mơ lỗi khối thực biến thiên theo số lượng yêu cầu định gửi tới Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 87 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng 4.2.2 Thử nghiệm nhận xét kết Giao diện chương trình mơ kỹ thuật RcB: Hình 4.9 Giao diện chương trình mơ kỹ thuật RcB Tiến hành thử nghiệm với: • Số lượng yêu cầu cố định 1.000.000 yêu cầu • Tốc độ gây lỗi khối thay 0.08 • Số phiên phần mềm: n = 2, 3, 4, Tất hoạt động xảy lỗi phần mềm ghi lại nhằm biểu diễn biến thiên lỗi phần mềm với số lượng yêu cầu Kết thể hình sau: Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 88 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng Hình 4.10 Số lỗi khơng phát chương trình mơ kỹ thuật RcB Từ hình 4.6, ta nhận thấy rằng: số lỗi không phát không giảm sử dụng thêm nhiều khối thay Do độ tin cậy hệ thống khơng thể cải thiện cách tăng số lượng khối thay Ngược lại việc sử dụng khối thay phần mềm chịu lỗi giúp hệ thống đạt tính sẵn sàng cao trường hợp Từ kết luận ta thấy việc sử dụng cách ứng xử cho task mơ hình chịu lỗi cho hệ thống nhúng đắn Điều chứng minh cho tính hợp lý mơ hình chịu lỗi đề xuất Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 89 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng TỔNG KẾT CHƯƠNG Ở chương ta xây dựng ứng dụng chịu lỗi để thử nghiệm tính khả thi kỹ thuật mơ hình chịu lỗi đề xuất Hệ thống vệ tinh thám khơng gian mang tính mơ nhằm chứng minh cho ý tưởng nghiên cứu hệ thống thực tế Đó hệ thống nhúng thời gian thực hoạt động với thiết bị phần cứng cảm ứng, phát tín hiệu, … Vấn đề xảy hệ thống hoạt động khơng bình thường tai họa xảy lúc đưa đến thiệt hại khôn lường người tài sản Ta áp dụng nghiên cứu kỹ thuật chịu lỗi chương trước để xây dựng hệ thống mô Ứng dụng ftappli hệ thống có ft-task đặt tên FT_TASK_1, FT_TASK_2, task có cách ứng xử ứng xử bình thường (normal) ứng xử chịu lỗi (degrade) thể thread khác Xét mức ứng dụng có chế độ hoạt động FT_MODE_INIT, FT_MODE_DEGRADED Ta mơ tình bất thường (tình gây lỗi) cách tự tạo kiện hủy hoạt động hàm pthread_cancel() Bộ điều khiển ftcontroller nhận kiện PTHREAD_KILL thông báo đến giám sát ứng dụng ftappmon Bộ giám sát ứng dụng chuyển chế độ ứng dụng từ chế độ FT_MODE_INIT sang chế độ chịu lỗi FT_MODE_DEGRADED Với ứng dụng thử nghiệm ta thấy kết chạy theo thiết kế chịu lỗi đề Hoạt động ứng dụng thể khả chịu lỗi hệ thống, chứng minh tính khả thi việc áp dụng kỹ thuật mơ hình chịu lỗi đề xuất cho hệ thống nhúng thời gian thực Ngoài thử nghiệm câu hỏi đặt thêm độ tin cậy hệ thống Ở mơ hình chịu lỗi dựa kỹ thuật RcB, khối chương trình cách ứng xử task Câu hỏi đặt để đảm bảo độ tin cậy hệ thống, đặc biệt hệ thống nhúng với tài nguyên giới hạn số lượng cách ứng xử cho task hợp lý? Thử nghiệm cho thấy số lỗi không phát không giảm sử dụng thêm nhiều khối thay Do độ tin cậy hệ thống cải thiện cách tăng số lượng khối thay Từ kết luận ta thấy việc sử dụng cách ứng xử cho task mơ hình chịu lỗi cho hệ thống nhúng đắn Điều chứng minh cho tính hợp lý mơ hình chịu lỗi đề xuất Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 90 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng KẾT LUẬN Các nội dung hoàn thành luận văn Đào sâu nghiên cứu tìm hiểu tư tưởng kỹ thuật chịu lỗi nói chung chẳng hạn tư tưởng dự phịng, biện pháp phục hồi tiến, phục hồi quay lui, kỹ thuật đa thiết kế NVP, RcB, kỹ thuật đa liệu Tìm hiểu chế hoạt động hệ điều hành nhúng thời gian thực chẳng hạn chế ngắt, mơ hình hoạt động dựa tác vụ (task), chế lập lịch (scheduling), chế truyền thông Đưa điểm khác biệt so với hệ điều hành thông thường chẳng hạn ràng buộc thời gian vấn đề tài nguyên giới hạn địi hỏi hệ thống nhúng phải có tính “tiền định” hoạt động Phân tích đưa mơ hình phần mềm chịu lỗi áp dụng cho hệ thống nhúng dựa kỹ thuật RcB kỹ thuật RcB mở rộng (cịn gọi DRB, distributed recovery block) Mơ hình thiết kế chịu lỗi với lưu ý ràng buộc thời gian tài nguyên hệ thống nhúng thời gian thực Mặt khác mơ hình thể tính suốt với người dùng để trình phát triển bảo trì hệ thống khơng q khó khăn Thử nghiệm tính khả thi mơ hình chịu lỗi cách xây dựng ứng dụng mô hệ điều hành thời gian thực RTLinux Ngoài để đánh giá độ tin cậy hệ thống dựa số lượng phiên kỹ thuật RcB (ở số cách ứng xử task) cho phù hợp với hệ thống nhúng, ứng dụng thử nghiệm khác xây dựng đưa đánh giá số cách ứng xử cần thiết task Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 91 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng Các đóng góp khoa học Tổng hợp nghiên cứu lý thuyết: • Trong nghiên cứu thực luận văn tác giả đào sâu nghiên cứu tìm hiểu kỹ thuật chịu lỗi đa thiết kế NVP, RcB Tác giả tổng hợp trình bày khác biệt hệ điều hành thời gian thực so với hệ điều hành thơng thường tính “tiền định” ứng xử Điều dẫn quan trọng áp dụng kỹ thuật chịu lỗi vào hệ thống nhúng thời gian thực • Luận văn đề xuất mơ hình chịu lỗi cho hệ thống nhúng nhiều mức, cụ thể hai mức, mức ứng dụng mức task Mô hình giúp hệ thống linh hoạt chịu lỗi từ nâng cao độ tin cậy • Luận văn phân tích đề xuất lựa chọn kỹ thuật RcB kỹ thuật hợp lý để áp dụng cho hệ thống nhúng vốn có tài nguyên giới hạn • Luận văn mở rộng kỹ thuật RcB thành kỹ thuật DRB cách phân tán task máy khác Kỹ thuật giúp hệ thống xử lý lỗi gây hỏng hóc nút (một máy) • Luận văn phân tích thử nghiệm đưa đánh giá số lượng khối chương trình kỹ thuật RcB cho hệ thống nhúng Kết luận cho thấy số lượng cách ứng xử cho task số lượng hợp lý đảm bảo độ tin cậy hệ thống Thực nghiệm: Luận văn tiến hành xây dựng hai ứng dụng thử nghiệm • Ứng dụng thứ ứng dụng chịu lỗi hoạt động hệ điều hành thời gian thực RTLinux chứng minh tính khả thi mơ hình chịu lỗi đề xuất • Ứng dụng thứ hai ứng dụng mô hoạt động kỹ thuật RcB Thử nghiệm chứng minh số lỗi không phát không giảm sử dụng thêm nhiều khối thay Do độ tin cậy hệ thống khơng thể cải thiện cách tăng số lượng khối thay Từ kết luận ta thấy việc sử dụng cách ứng xử cho task mơ hình chịu lỗi cho hệ thống nhúng đắn Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 92 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng Hướng phát triển luận văn Hướng phát triển luận văn theo số hướng sau: • Nghiên cứu bổ sung định kỹ thuật RcB vào mơ hình nhằm đánh giá tính đắn kết output task • Tìm hiểu nghiên cứu mơ hình kỹ thuật chịu lỗi cho hệ thống nhúng cỡ nhỏ đơn giản • Nghiên cứu phương pháp đánh giá độ tin cậy hệ thống nhúng sau áp dụng kỹ thuật chịu lỗi Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 93 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng PHỤ LỤC CÁC TỪ ĐIỂN STT Tiếng Anh Tiếng Việt Application mode Chế độ ứng dụng Components Các thành phần Checkpoint Điểm đánh dấu hệ thống Consistency Tính quán Distributed enviroment Môi trường phân tán Fault Analysis Bộ phân tích lỗi Fault tolerant Chịu lỗi Application monitoring Giám sát ứng dụng Multiple Data Kỹ thuật đa liệu 10 Multiple version programming Kỹ thuật đa thiết kế 11 Non-functional requirements Các yêu cầu không mang tính chức 12 Node Nút 13 Pipe and Queue Đường ống hàng đợi 14 Passive replication Kiểu nhân thụ động 15 Recovery Khôi phục, phục hồi 16 Real time systems Các hệ thống thời gian thực 17 Replica Một đối tượng 18 Task Tác vụ 19 Redundancy Dự phòng 20 Scheduling Lập lịch 21 Software component Thành phần phần mềm 22 System architecture Kiến trúc hệ thống 23 Transition Chuyển đổi 24 Timing error Lỗi thời gian Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 94 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng TÀI LIỆU THAM KHẢO Tiếng Việt: [1] [2] [3] [4] [5] [6] Phạm Bá Quang Đánh giá so sánh kỹ thuật xây dựng phần mềm chịu lỗi Luận văn thạc sỹ ĐH Bách khoa Hà Nội-2004 Người hướng dẫn: TS Huỳnh Quyết Thắng Huỳnh Quyết Thắng - Phạm Bá Quang - Lương Thanh Bình So sánh đánh giá kỹ thuật xây dựng phần mềm chịu lỗi Proceedings of ICT.rda'04 Hanoi Sep 24-25, 2004 Đào Ngọc Kiên, Phạm Bá Quang, Huỳnh Quyết Thắng Mơ hình phần mềm chịu lỗi BK-FTS: thử nghiệm, so sánh đánh giá Tạp chí tin học điều khiển học, Tập 21, Số 4, 2005, Trang 323-336 Nguyễn Hữu Nam Dương Đánh giá độ tin dùng phần mềm chịu lỗi sử dụng mơ hình Markov Đồ án tốt nghiệp ĐH Bách Khoa Hà Nội - 2009 Người hướng dẫn: PGS.TS Huỳnh Quyết Thắng Tiếng Anh: http://www.ocera.org Open components for embedded real-time applications OCERA Project Francisco Afonso - Carlos Silva - Nuno Brito - Sergio Montenegro Adriano Tavares Application-Level Fault Tolerance in Real-Time Embedded Systems Portuguese Foundation for Science and Technology [7] [8] [9] [10] [11] [12] Ian Sommerville “Software Engineering 7”, ISBN:0-321-21026-3 Jean-Claude Laprie, “Dependable Computing and Fault Tolerance”, IEEE Proceedings of FTCS-25, Volume III Page(s):2-11 George A Reis, et al , “SWIFT: Software Implemented Fault Tolerance”, Departments of Electrical Engineering and Computer Science, Princeton University Min Xie, Yuan-Shun Dai, Kim-Leng Poh,” Computing System Reliability -Models and Analysis” - ©2004 Kluwer Academic Publishers Wilfredo Torres-Pomales, “Software Fault Tolerance: A Tutorial”, Langley Research Center, Hampton, Virginia Zaipeng Xie, et al., “A Survey of software fault tolerance techniques” , University of Wisconsin-Madison/Department of Electrical and Computer Engineering, 2005 Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 95 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng TĨM TẮT LUẬN VĂN Mục đích luận văn nghiên cứu tìm hiểu phương pháp kỹ thuật nhằm cung cấp khả chịu lỗi cho hệ thống nhúng thời gian thực Trước tiên tư tưởng phần mềm chịu lỗi kỹ thuật chịu lỗi nói chung chẳng hạn tư tưởng dự phòng, kỹ thuật NVP, RcB đào sâu nghiên cứu, phân tích Tiếp theo, mục tiêu áp dụng cho hệ thống nhúng nên luận văn tìm hiểu chế hoạt động bên hệ điều hành nhúng thời gian thực chẳng hạn mơ hình hoạt động dựa tác vụ (task), chế lập lịch, chế khác Luận văn đưa điểm khác biệt hệ điều hành nhúng thời gian thực so với hệ điều hành thông thường chẳng hạn ràng buộc thời gian vấn đề tài nguyên giới hạn Những khác biệt đòi hỏi hệ thống nhúng phải có tính “tiền định” hoạt động Luận văn phân tích đề xuất mơ hình phần mềm chịu lỗi áp dụng cho hệ thống nhúng dựa kỹ thuật RcB kỹ thuật RcB mở rộng, gọi kỹ thuật khối phục hồi phân tán DRB (distributed recovery block) Mơ hình thiết kế chịu lỗi với lưu ý ràng buộc thời gian tài nguyên hệ thống nhúng thời gian thực Mặt khác cần thiết kế mơ hình cho chế chịu lỗi phải suốt với người dùng để trình phát triển bảo trì hệ thống khơng q khó khăn Có hai mức chịu lỗi mức ứng dụng mức task Mỗi task có hai cách ứng xử, cách ứng xử bình thường chịu lỗi Có thể phân tán nhiều task máy khác Một ứng dụng nhúng thử nghiệm chạy hệ điều hành nhúng thời gian thực RTLinux xây dựng để thử nghiệm tính khả thi mơ hình Kết thử nghiệm cho thấy ứng dụng có khả chịu lỗi mong đợi Ngoài để đánh giá độ tin cậy hệ thống dựa số lượng phiên kỹ thuật RcB (được xem số cách ứng xử task ứng dụng chịu lỗi), ứng dụng thử nghiệm khác xây dựng đưa phân tích đánh giá số cách ứng xử cần thiết task để đảm bảo độ tin cậy hệ thống Thử nghiệm cho thấy số cách ứng xử task mà ta đề xuất mơ hình chịu lỗi hợp lý Từ khóa: fault tolerant, embedded application, real time, passive replication, recovery block Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 96 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng THESIS SUMARY The goal of this thesis is to find technique methods to improve fault tolerant ability of real-time embedded application At first, ideology of fault tolerant software and basic fault tolerant techniques such as N-Version Programming (NVP) and Recovery Block (RcB) are deeply studied and analyzed Second, because our purpose is to apply fault tolerant characteristic to embedded application so we study internal mechanisms of real-time operating system, for example task-based model, scheduling algorithm and so on We also present main different points between real-time operating system and generalpurpose operating system such as real-time constraint and resource limitation These difference require embedded application to have “deterministic” characteristic in its operation As the analysis consequence, a fault tolerant software model for real-time embedded application is proposed It is developed based on RcB technique and its extend called DRB technique (distributed recovery block) We design the model with care of timing constraint and resource limitation of real-time embedded application in mind Beside, it is necessary to design the model so that the fault tolerant mechanism is transparent to developers to help system’s implementation and maintenance There are two level of fault tolerant, application level and task level Each task has two behavior, normal behavior and degraded behavior Multiple replica of a task can be distributed in different machine (node) An experiment embedded application running on a real-time operating system called RTLinux is built in order to evaluated the feasibility of this model Experiment result shows that embedded application gains fault tolerant ability as expected In addition, to evaluate dependability of system base on the number of block in RcB technique (consider as the number of behavior of a task later) , another experiment application is built and evaluate the number of behavior of a task needed to guarantee system dependability Experiment result proves the number of behavior of a task that we proposed in above model is reasonable Keyword: fault tolerant, embedded application, real-time, passive replication, recovery block Đào Ngọc Kiên - Lớp Cao Học CNTT 06-08 – ĐH Bách Khoa Hà Nội 97 ... 46 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng CHƯƠNG – KỸ THUẬT XÂY DỰNG PHẦN MỀM CHỊU LỖI ÁP DỤNG CHO HỆ THỐNG NHÚNG 3.1 Ý tưởng ban đầu xây dựng phần mềm chịu lỗi. .. Khoa Hà Nội 12 Nghiên cứu kỹ thuật xây dựng phần mềm chịu lỗi áp dụng cho hệ thống nhúng • Chương 3: Kỹ thuật mơ hình phần mềm chịu lỗi áp dụng cho hệ thống nhúng Chương nghiên cứu, phân tích... chịu lỗi áp dụng cho hệ thống nhúng Kỹ thuật loại bỏ lỗi Kỹ thuật dự đoán lỗi Kỹ thuật chịu lỗi Kỹ thuật tránh lỗi Kỹ thuật thực trình xây dựng phần mềm nhằm giảm bớt lỗi xảy sau phần mềm hoạt