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 Phạm Đức Mạnh Trường Đại học Công ngh. Đại học Quốc gia Hà Nội
Luận văn ThS. Công nghệ thông tin: 60 48 10
Người hướng dẫn : TS. Nguyễn Thị Huyền Châu
Năm bảo vệ: 2013
48 tr .

Abstract. Hệ thống hóa cơ sở lý thuyết của đề tài. Đề cập đến mô hình nhiệm vụ hệ
thời gian thực. 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, đều đưa ra ý tưởng, thuật toán và ví dụ minh họa cụ
thể. Đư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ỉ.
Đề xuất 1 hàm RBF xấp xỉ để cải thiện chất lượng thuật toán. Giới thiệu 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. 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. 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
Keywords. Công nghệ thông tin; Công nghệ phần mềm; Lập lịch hệ thời gian thực
Content.
1.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,

tạp của thuật toán.
1.2. 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.
1.3. 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.
TÀI LIỆU THAM KHẢO
1. Bini, E., Buttazzo, G. (2005), “Measuring the performance of schedulability
tests”, Journal of Real-Time Systems 30(1-2), pp. 129–154.
2. Fisher, N., Baruah, S. (2005), “A polynomial-time approximation scheme for
feasibility analysis in static-priority systems with bounded relative deadlines”,

13. T.H.C.Nguyen, P.Richard, E.Bini (2009), “Approximation techniques for
response-time analysis of static-priority tasks”, Journal of Real-Time Systems
(RTSJ’09) 43(2), pp. 147 – 176.
14. T.H.C.Nguyen, P.Richard, N.Fisher (2010), “The fully polynomial-time
approximation scheme for feasibility analysis in static-priority systems with
arbitrary relative deadlines revisited”, Proc. Int. Conf. on Real-Time and
Network Systems (RTNS’10), pp. 21-30.