ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM ĐỨC MẠNH PHÂN TÍCH XẤP XỈ KHẢ NĂNG LẬP LỊCH CỦA HỆ THỜI GIAN THỰC TRONG TRƢỜNG HỢP ĐỘ ƢU TIÊN CỐ ĐỊNH VỚI KỲ HẠN KHÔNG RÀNG BUỘC VÀ ĐỘ TRỄ PHÁT HÀNH LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - 2013 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM ĐỨC MẠNH PHÂN TÍCH XẤP XỈ KHẢ NĂNG LẬP LỊCH CỦA HỆ THỜI GIAN THỰC TRONG TRƢỜNG HỢP ĐỘ ƢU TIÊN CỐ ĐỊNH VỚI KỲ HẠN KHÔNG RÀNG BUỘC VÀ ĐỘ TRỄ PHÁT HÀNH Ngành: Công nghệ thông tin Chuyên ngành: Công nghệ phần mềm Mã số: 60 48 10 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. NGUYỄN THỊ HUYỀN CHÂU Hà Nội - 2013 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC MỤC LỤC DANH MỤC CÁC TỪ VIẾT TẮT DANH MỤC CÁC BẢNG DANH MỤC CÁC HÌNH VẼ CHƢƠNG 1. Bối cảnh nghiên cứu. Mục tiêu nghiên cứu.
Cấu trúc luận văn. Mô hình nhiệm vụ hệ thời gian thực. Hệ thống thời gian thực. Tầm quan trọng của hệ thời gian thực.
Phân loại nhiệm vụ thời gian thực. Các tham số đặc trƣng cho hệ thời gian thực. Các phƣơng pháp kiểm định dựa trên độ ƣu tiên cố định. Một số khái niệm về lập lịch.
Lập lịch là gì. Phân loại lập lịch. Lập lịch dựa trên độ ƣu tiên cố định. Những kết quả cơ bản.
Bài toán nghiên cứu. Hàm Request Bound Function (𝑅𝐵𝐹). Hàm Workload Function (𝑊). Thời điểm ngặt nghèo (Critical Instant).
Khoảng bận rộn mức i (level-i busy period). Các phƣơng pháp kiểm định chính xác hệ có độ ƣu tiên cố định. Response Time Analysis (RTA) .12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Processor Demand Analysis (PDA).
PHÂN TÍCH XẤP XỈ KHẢ NĂNG LẬP LỊCH CỦA HỆ THỜI GIAN THỰC TRONG TRƢỜNG HỢP ĐỘ ƢU TIÊN CỐ ĐỊNH VỚI KỲ HẠN KHÔNG RÀNG BUỘC VÀ ĐỘ TRỄ PHÁT HÀNH. Một số khái niệm. Các kết quả ban đầu. Phân tích khả năng lập lịch của hệ thời gian thực sử dụng biểu đồ xấp xỉ.
Thuật toán: Approx(𝜏, 𝑖, 𝑘). Ví dụ minh họa. Tính đúng đắn của thuật toán. THỰC NGHIỆM VÀ ĐÁNH GIÁ HIỆU QUẢ CỦA BIỂU ĐỒ XẤP XỈ.
Phƣơng pháp thực nghiệm. Phƣơng pháp đánh giá. Kết quả thực nghiệm. Xuất xứ bài toán nghiên cứu.
Phƣơng pháp đề xuất và kết quả đạt đƣợc. Hƣớng phát triển trong tƣơng lai .45 TÀI LIỆU THAM KHẢO. 47 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH MỤC CÁC TỪ VIẾT TẮT RTA Phƣơng pháp phân tích thời gian đáp ứng của nhiệm vụ (Response Time Analysis). PDA Phƣơng pháp phân tích lƣợng công việc yêu cầu bộ xử lý thực hiện (Processor Demand Analysis).
RBF Hàm lƣợng công việc mà nhiệm vụ yêu cầu CPU thực hiện (Request Bound Function). W Hàm lƣợng công việc mà các nhiệm vụ yêu cầu CPU thực hiện (Workload). RM Thuật toán gán độ ƣu tiên dựa vào tỉ lệ yêu cầu của các nhiệm vụ (Rate Monotonic). DM Thuật toán gán độ ƣu tiên tỉ lệ nghịch với kỳ hạn tƣơng đối của nhiệm vụ (Deadline Monotonic).
CPU Bộ xử lý trung tâm (Central Processing Unit). LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH MỤC CÁC BẢNG Số hiệu Tên bảng Trang bảng 2.1 Tập các nhiệm vụ có độ ƣu tiên cố định 8 2.2 Tập các nhiệm vụ đƣợc kích hoạt từ thời điểm 𝑡 = 0 8 2.3 Tập các nhiệm vụ với kỳ hạn không ràng buộc 8 2.4 Hệ với kỳ hạn không ràng buộc và độ trễ phát hành 14 3.1 Hệ với kỳ hạn không ràng buộc và độ trễ phát hành 31 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH MỤC CÁC HÌNH VẼ Số hiệu Tên hình vẽ Trang hình vẽ 2.1 Các tham số đặc trƣng của một nhiệm vụ thời gian thực 𝜏𝑖 .2 Nhiệm vụ tuần hoàn với độ trễ phát hành.3 Chuỗi các tác vụ của một nhiệm vụ tuần hoàn 𝜏𝑖 .6 Thời điểm ngặt nghèo.7 Khoảng thời gian bận rộn mức i.8 Hàm W (Workload Function) trong phƣơng pháp RTA.9 Hàm W (Workload Function) trong phƣơng pháp PDA.1 Hàm RBF xấp xỉ đối với nhiệm vụ 𝜏𝑖 .2 Hàm tải công việc cho tác vụ 𝜏𝑖,𝑙 .3 Các tác vụ hoàn thành trong khoảng thời gian nguyên tố.4 Tác vụ đầu tiên hoàn thành trong khoảng thời gian nguyên tố.5 Tác vụ cuối cùng hoàn thành trong khoảng thời gian nguyên tố. 31 Tỉ lệ chấp nhận của SupD và thuật toán đề xuất theo số nhiệm vụ 4. Tỉ lệ chấp nhận của SupD và thuật toán đề xuất theo hệ số sử dụng 4.3 Tỉ lệ chấp nhận của SupD và thuật toán đề xuất dựa trên ratioJ.
43 Tỉ lệ chấp nhận của SupD và thuật toán đề xuất theo số nhiệm vụ 4.4 43 của hệ và k. Tỉ lệ chấp nhận của SupD và thuật toán đề xuất theo hệ số sử dụng 4. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 1 CHƢƠNG 1. Bối cảnh nghiên cứu Trong những năm gần đây, các hệ thống thời gian thực đóng vai trò ngày càng quan trọng trong nhiều lĩnh vực ứng dụng.
Hệ thống thời gian thực đã và đang đƣợc ứng dụng rộng rãi trong các dây chuyền sản xuất tự động, robot, điều khiển lƣu thông, điều khiển các thí nghiệm tự động, truyền thông, điều khiển trong quân sự … Với những hệ thống này, lƣợng công việc cần thực hiện có thể không đƣợc dự báo chính xác, các nhiệm vụ có thể sinh ra thêm trong thời gian chạy. Do đó mà hệ thống cần có khả năng giải quyết những tình huống quá tải tạm thời. Điều này đƣợc thực hiện thông qua một bộ điều khiển gia nhập có khả năng quyết định chấp nhận hay từ chối một nhiệm vụ nào đó nhằm điều tiết lƣợng công việc dựa trên các tính toán về khả năng lập lịch. Những tính toán này đòi hỏi phải đủ nhanh do chúng đƣợc thực hiện thƣờng xuyên trong suốt thời gian tồn tại của hệ thống.
Tồn tại 2 phƣơng pháp phân tích chính xác khả năng lập lịch của một hệ thống thời gian thực với độ ƣu tiên cố định là Response Time Analysis (RTA - [4, 6]) và Processor Demand Analysis (PDA - [5, 6]). Mặc dù có độ phức tạp giả đa thức nhƣng cả 2 phƣơng pháp này đều đƣợc cài đặt rất hiệu quả trong thực tế. Tuy nhiên, với những hệ mà các nhiệm vụ đƣợc sản sinh động, các test kiểm định đƣợc gọi liên tiếp với số lƣợng lớn, một thuật toán với độ phức tạp giả đa thức trở nên quá chậm. Thay vào đó, chúng ta hƣớng đến một thuật toán có độ phức tạp đa thức.
Một trong số đó là phƣớng pháp biểu đồ xấp xỉ mà luận văn sử dụng. Việc sử dụng phƣơng pháp xấp xỉ để phân tích tính khả thi của hệ đã đƣợc trình bày trong [2] cho trƣờng hợp các nhiệm vụ có độ ƣu tiên cố định với kỳ hạn ràng buộc và đƣợc mở rộng cho hệ với kỳ hạn không ràng buộc trong [3]. Những kiểm định xấp xỉ này chạy trong thời gian đa thức và đƣợc điều khiển bởi một tham số chính xác 𝜀. Tiếp đó, [14] đã trình bày và sửa chữa các vấn đề kỹ thuật trong [3], đồng thời đề xuất một thuật toán xấp xỉ cải thiện cho hệ với kỳ hạn không ràng buộc.
Nó cũng đƣợc mở rộng để tính toán cận trên thời gian phản ứng trong [11]. Nhƣ vậy, hiện chƣa có phƣơng pháp kiểm định xấp xỉ nào cho hệ có độ ƣu tiên cố định với kỳ hạn không ràng buộc và độ trễ phát hành. Do đó, luận văn nghiên cứu đề xuất một thuật toán kiểm định xấp xỉ cho hệ này, với mức độ xấp xỉ đƣợc tham số hóa, cho phép chúng ta “co dãn” thuật toán để cân bằng giữa độ chính xác và độ phức tạp của thuật toán. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Mục tiêu nghiên cứu Trong đề tài này, tôi sử dụng phƣơng pháp biểu đồ xấp xỉ để kiểm định khả năng lập lịch của hệ thời gian thực trong trƣờng hợp độ ƣu tiên cố định với kỳ hạn không ràng buộc và độ trễ phát hành. Thuật toán có độ phức tạp đa thức, cung cấp một kết quả “xấp xỉ” về khả năng lập lịch của các nhiệm vụ trong hệ thống. Thêm vào đó, luận văn cũng đƣa ra hàm RBF xấp xỉ thay thế để cải thiện thuật toán xấp xỉ đã đƣợc trình bày trong [14]. Cuối cùng, luận văn trình bày các kết quả thực nghiệm để đánh giá hiệu quả của biểu đồ xấp xỉ so với những phƣơng pháp kiểm định đã đƣợc biết đến khác.
Cấu trúc luận văn Trong các phần tiếp theo của luận văn, tôi sẽ trình bày những nội dung sau: Chƣơng 2 trình bày về cơ sở lý thuyết của đề tài. Chƣơng này đề cập đến mô hình nhiệm vụ hệ thời gian thực. Tiếp đến, tôi mô tả các phƣơng pháp kiểm định chính xác cho hệ có độ ƣu tiên cố định. Trong mỗi phƣơng pháp, luận văn đều đƣa ra ý tƣởng, thuật toán và ví dụ minh họa cụ thể.
Chƣơng 3 đƣa ra phƣơng pháp phân tích khả năng lập lịch của hệ thời gian thực có độ ƣu tiên cố định với kỳ hạn không ràng buộc và độ trễ phát hành sử dụng biểu đồ xấp xỉ. Trong chƣơng này, luận văn sẽ đề xuất 1 hàm RBF xấp xỉ để cải thiện chất lƣợng thuật toán. Phần cuối chƣơng, tôi sẽ trình bày 1 ví dụ minh họa cũng nhƣ phân tích tính đúng đắn của phƣơng pháp mà luận văn đề xuất. Chƣơng 4 trình bày các kết quả thực nghiệm để đánh giá hiệu quả của biểu đồ xấp xỉ so với các phƣơng pháp kiểm định đã đƣợc biết đến khác.
Chƣơng 5 tóm tắt những kết quả đạt đƣợc cũng nhƣ hƣớng phát triển trong tƣơng lại. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 CHƢƠNG 2. Mô hình nhiệm vụ hệ thời gian thực 2. Hệ thống thời gian thực 2.
Khái niệm Hệ thống thời gian thực là hệ thống máy tính có khả năng phản ứng chính xác và kịp thời với các sự kiện trong môi trƣờng. Một phản ứng xảy ra quá muộn sẽ vô ích hoặc gây nguy hiểm cho hệ thống. Nhƣ vậy, hệ thời gian thực đƣợc hiểu nhƣ là một mô hình xử lý mà tính đúng đắn của nó không chỉ phụ thuộc vào sự chính xác của kết quả mà còn phụ thuộc vào thời điểm đƣa ra kết quả đó. Hệ thống bị cho là có lỗi khi yêu cầu về thời gian không đƣợc đáp ứng.