Luận Văn Thạc Sĩ: Phân Tích Khả Năng Lập Lịch Hệ Thời Gian Thực Với Độ Ưu Tiên Cố Định

Luận văn thạc sĩ phân tích khả năng lập lịch hệ thời gian thực với độ ưu tiên cố định, kỳ hạn không ràng buộc và độ trễ phát hành.

• Tác giả: Phạm Đức Mạnh
• Người hướng dẫn: TS. Nguyễn Thị Huyền Châu
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Phân Tích Khả Năng Lập Lịch Hệ Thời Gian Thực Với Độ Ưu Tiên Cố Định
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2013
• Địa điểm: Hà Nội

Mục lục chi tiết

• 1. CHƯƠNG 1: BỐI CẢNH NGHIÊN CỨU
• 1.1. Mục tiêu nghiên cứu
• 1.2. Cấu trúc luận văn
• 1.3. Mô hình nhiệm vụ hệ thời gian thực
• 1.4. Hệ thống thời gian thực
• 1.5. Tầm quan trọng của hệ thời gian thực
• 1.6. Phân loại nhiệm vụ thời gian thực
• 1.7. Các tham số đặc trưng cho hệ thời gian thực
• 1.8. Các phương pháp kiểm định dựa trên độ Ưu tiên cố định
• 1.9. Một số khái niệm về lập lịch
• 1.10. Lập lịch là gì
• 1.11. Phân loại lập lịch
• 1.12. Lập lịch dựa trên độ Ưu tiên cố định
• 1.13. Những kết quả cơ bản
• 1.14. Bài toán nghiên cứu
• 1.15. Hàm Request Bound Function (RBF)
• 1.16. Hàm Workload Function (W)
• 1.17. Thời điểm ngặt nghèo (Critical Instant)
• 1.18. Khoảng bận rộn mức i (level-i busy period)
• 1.19. Các phương pháp kiểm định chính xác hệ có độ Ưu tiên cố định
• 1.20. Response Time Analysis (RTA)
• 1.21. Processor Demand Analysis (PDA)
• 2. 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
• 2.1. Một số khái niệm
• 2.2. Các kết quả ban đầu
• 2.3. 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ỉ
• 2.4. Thuật toán: Approx(τ, i, k)
• 2.5. Ví dụ minh họa
• 2.6. Tính đúng đắn của thuật toán
• 3. THỰC NGHIỆM VÀ ĐÁNH GIÁ HIỆU QUẢ CỦA BIỂU ĐỒ XẤP XỈ
• 3.1. Phương pháp thực nghiệm
• 3.2. Phương pháp đánh giá
• 3.3. Kết quả thực nghiệm
• 3.4. Xuất xứ bài toán nghiên cứu
• 3.5. Phương pháp đề xuất và kết quả đạt được
• 3.6. Hướng phát triển trong tương lai
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Bối cảnh nghiên cứu

Trong những năm gần đây, hệ thống thời gian thực đã trở thành một phần không thể thiếu trong nhiều lĩnh vực ứng dụng như tự động hóa công nghiệp, điều khiển giao thông, và quân sự. Các nhiệm vụ thời gian thực thường không thể dự đoán chính xác, dẫn đến việc cần có khả năng xử lý các tình huống quá tải tạm thời. Để đảm bảo tính khả thi của lập lịch hệ thống, các phương pháp phân tích như Response Time Analysis (RTA) và Processor Demand Analysis (PDA) đã được phát triển. Tuy nhiên, với các hệ thống có độ ưu tiên cố định, việc áp dụng các phương pháp này có thể trở nên chậm chạp. Do đó, nghiên cứu này hướng đến việc phát triển một thuật toán mới có độ phức tạp đa thức, sử dụng phương pháp biểu đồ xấp xỉ để phân tích khả năng lập lịch cho các nhiệm vụ có độ ưu tiên cố định với kỳ hạn không ràng buộc và độ trễ phát hành.

II. Mục tiêu nghiên cứu

Mục tiêu chính của nghiên cứu này là 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 đề xuất sẽ có độ phức tạp đa thức, cung cấp 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. Nghiên cứu cũng sẽ giới thiệu hàm Request Bound Function (RBF) xấp xỉ để cải thiện chất lượng thuật toán. Cuối cùng, các kết quả thực nghiệm sẽ được trình bày để đánh giá hiệu quả của phương pháp xấp xỉ so với các phương pháp kiểm định đã biết.

III. Cấu trúc luận văn

Luận văn được chia thành các chương chính. Chương 1 giới thiệu bối cảnh và mục tiêu nghiên cứu. Chương 2 trình bày cơ sở lý thuyết về hệ thống thời gian thực, các tham số đặc trưng và các phương pháp kiểm định khả năng lập lịch. Chương 3 sẽ đi sâu vào phương pháp phân tích khả năng lập lịch của hệ thống có độ ưu tiên cố định với kỳ hạn không ràng buộc và độ trễ phát hành. Chương 4 sẽ trình bày các kết quả thực nghiệm và đánh giá hiệu quả của phương pháp đề xuất. Cuối cùng, Chương 5 sẽ tóm tắt các kết quả đạt được và hướng phát triển trong tương lai.

IV. Phân loại nhiệm vụ thời gian thực

Nhiệm vụ thời gian thực được phân loại thành ba loại chính: cứng, mềm, và trung gian. Nhiệm vụ cứng yêu cầu phải hoàn thành đúng thời hạn, nếu không sẽ gây ra hậu quả nghiêm trọng. Nhiệm vụ mềm có thể chấp nhận một số độ trễ mà không gây ra thiệt hại lớn. Nhiệm vụ trung gian là những nhiệm vụ mà độ trễ không gây ra thiệt hại nhưng sẽ trở nên vô ích. Nghiên cứu này tập trung vào hệ thống thời gian thực cứng, nơi việc đảm bảo hoàn thành đúng kỳ hạn là rất quan trọng. Việc phân tích khả năng lập lịch cho các nhiệm vụ này sẽ được thực hiện thông qua các phương pháp kiểm định chính xác.

V. Các phương pháp kiểm định dựa trên độ ưu tiên cố định

Các phương pháp kiểm định khả năng lập lịch cho hệ thống thời gian thực với độ ưu tiên cố định bao gồm Rate Monotonic (RM) và Deadline Monotonic (DM). Trong phương pháp RM, độ ưu tiên được gán dựa trên chu kỳ của nhiệm vụ, trong khi DM gán độ ưu tiên dựa trên kỳ hạn tương đối. Cả hai phương pháp này đều có những ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp sẽ phụ thuộc vào đặc điểm của hệ thống cụ thể. Nghiên cứu này sẽ áp dụng phương pháp DM để gán độ ưu tiên cho các nhiệm vụ trong các thực nghiệm.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển nhanh chóng của công nghệ, các hệ thống thời gian thực ngày càng đóng vai trò quan trọng trong nhiều lĩnh vực như tự động hóa công nghiệp, robot, điều khiển giao thông, quân sự và y tế. Theo ước tính, các hệ thống này phải xử lý các nhiệm vụ với yêu cầu thời gian nghiêm ngặt, trong đó việc lập lịch chính xác và kịp thời là yếu tố quyết định hiệu quả và an toàn của hệ thống. Vấn đề nghiên cứu trọng tâm của luận văn là phân tích 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, nhằm đảm bảo các nhiệm vụ được hoàn thành đúng hạn trong điều kiện thực tế phức tạp.

Mục tiêu cụ thể của nghiên cứu là đề xuất một thuật toán kiểm định xấp xỉ dựa trên biểu đồ xấp xỉ, có độ phức tạp đa thức, giúp cân bằng giữa độ chính xác và hiệu quả tính toán trong việc đánh giá khả năng lập lịch của hệ. Thuật toán này được thiết kế để xử lý các hệ thống với các tham số như thời gian thực hiện, chu kỳ, độ trễ phát hành và kỳ hạn tương đối của các nhiệm vụ tuần hoàn. Phạm vi nghiên cứu tập trung vào các hệ thời gian thực cứng, với dữ liệu và mô hình được xây dựng dựa trên các tham số thực nghiệm từ các hệ thống thời gian thực hiện đại, trong khoảng thời gian nghiên cứu từ năm 2010 đến 2013 tại Việt Nam.

Ý nghĩa của nghiên cứu được thể hiện qua việc cải thiện hiệu quả kiểm định khả năng lập lịch, giúp các nhà phát triển và quản lý hệ thống thời gian thực có công cụ đánh giá nhanh chóng và chính xác hơn, từ đó nâng cao độ tin cậy và an toàn cho các ứng dụng quan trọng.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình nền tảng trong lĩnh vực lập lịch hệ thời gian thực, bao gồm:

• Mô hình nhiệm vụ tuần hoàn: Mỗi nhiệm vụ được đặc trưng bởi các tham số như thời gian thực hiện (𝐶𝑖), chu kỳ kích hoạt (𝑇𝑖), độ trễ phát hành (𝐽𝑖) và kỳ hạn tương đối (𝐷𝑖). Nhiệm vụ tuần hoàn gồm chuỗi các tác vụ (jobs) được kích hoạt đều đặn theo chu kỳ.

• Lập lịch dựa trên độ ưu tiên cố định: Độ ưu tiên của các nhiệm vụ được xác định trước và không thay đổi trong quá trình thực thi. Thuật toán Deadline Monotonic (DM) được sử dụng để gán độ ưu tiên dựa trên nghịch đảo của kỳ hạn tương đối.

• Hàm Request Bound Function (RBF) và Hàm Workload Function (W): RBF biểu diễn tổng thời gian CPU yêu cầu thực hiện của một nhiệm vụ trong khoảng thời gian nhất định, còn W biểu diễn tổng thời gian CPU yêu cầu thực hiện của các nhiệm vụ có độ ưu tiên cao hơn cộng với thời gian thực hiện của các tác vụ đầu tiên của nhiệm vụ đang xét.

• Phương pháp kiểm định chính xác: Bao gồm Response Time Analysis (RTA) và Processor Demand Analysis (PDA), cả hai đều có độ phức tạp giả đa thức và được sử dụng để xác minh tính khả thi của hệ thống thời gian thực.

• Phương pháp biểu đồ xấp xỉ: Được đề xuất nhằm giảm độ phức tạp tính toán bằng cách sử dụng hàm RBF xấp xỉ, cho phép điều chỉnh độ chính xác thông qua tham số 𝜀, giúp cân bằng giữa độ chính xác và hiệu quả.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu bao gồm các tham số mô phỏng hệ thống thời gian thực được sinh ngẫu nhiên dựa trên thuật toán UFitting, đảm bảo tính khách quan và đa dạng của các trường hợp thử nghiệm. Các tham số chính gồm hệ số sử dụng CPU (U), số lượng nhiệm vụ (n), chu kỳ kích hoạt, thời gian thực hiện, kỳ hạn tương đối và độ trễ phát hành.

Phương pháp phân tích sử dụng thuật toán Approx(𝜏, 𝑖, 𝑘) dựa trên biểu đồ xấp xỉ, trong đó:

• 𝜏 là tập các nhiệm vụ tuần hoàn,
• 𝑖 là chỉ số nhiệm vụ cần phân tích,
• 𝑘 là số bước chính xác cần xét để điều chỉnh độ chính xác của thuật toán.

Thuật toán xây dựng tập các điểm lập lịch 𝑆𝑖, kiểm tra khả năng lập lịch của từng tác vụ trong các khoảng thời gian nguyên tố, đồng thời xác định khoảng bận rộn mức i đã kết thúc hay chưa. Quá trình thực nghiệm được thực hiện với 300 lần lặp cho mỗi bộ tham số, thay đổi hệ số sử dụng CPU từ 0.9 đến gần 1, số lượng nhiệm vụ từ 5 đến 50, và các giá trị khác nhau của tham số 𝑟𝑎𝑡𝑖𝑜𝐽 để đánh giá ảnh hưởng của độ trễ phát hành.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả thuật toán biểu đồ xấp xỉ: Thuật toán đề xuất đạt tỉ lệ chấp nhận (acceptance ratio) cao hơn từ 7% đến 10% so với phương pháp cận trên tuyến tính SupD của Davis khi số lượng nhiệm vụ tăng lên trên 10. Ví dụ, với 30 nhiệm vụ, tỉ lệ chấp nhận của thuật toán xấp xỉ đạt gần 95%, trong khi SupD chỉ khoảng 85%.

2. Ảnh hưởng của hệ số sử dụng CPU: Khi hệ số sử dụng CPU tăng từ 0.8 đến 1, tỉ lệ chấp nhận của cả hai phương pháp đều giảm, nhưng thuật toán biểu đồ xấp xỉ duy trì tỉ lệ cao hơn, dao động từ 80% đến 100%, trong khi SupD giảm xuống dưới 85%.

3. Ảnh hưởng của độ trễ phát hành (ratioJ): Với giá trị ratioJ thay đổi từ 1 đến 9, tỉ lệ chấp nhận của SupD không ổn định, giảm xuống dưới 82% tại các giá trị 6 và 7, trong khi thuật toán xấp xỉ duy trì tỉ lệ chấp nhận ổn định và cao hơn, trên 90%.

4. Ảnh hưởng của số bước chính xác k: Khi tăng số bước k từ 3 đến 5, tỉ lệ chấp nhận của thuật toán xấp xỉ tăng lên gần 100% với số lượng nhiệm vụ lớn, cho thấy khả năng điều chỉnh độ chính xác linh hoạt của thuật toán.

Thảo luận kết quả

Nguyên nhân chính của việc thuật toán biểu đồ xấp xỉ đạt hiệu quả cao hơn là do sử dụng hàm RBF xấp xỉ tuyến tính sau một số bước tính toán, giúp giảm đáng kể độ phức tạp mà vẫn giữ được độ chính xác cần thiết. So với các phương pháp kiểm định chính xác như RTA và PDA có độ phức tạp giả đa thức, thuật toán xấp xỉ có độ phức tạp đa thức, phù hợp với các hệ thống có số lượng nhiệm vụ lớn và yêu cầu tính toán nhanh.

Kết quả thực nghiệm được minh họa qua các biểu đồ tỉ lệ chấp nhận theo số nhiệm vụ, hệ số sử dụng CPU và ratioJ, cho thấy xu hướng ổn định và ưu việt của thuật toán đề xuất. So sánh với các nghiên cứu trước đây, luận văn đã mở rộng phạm vi áp dụng 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, một trường hợp chưa được nghiên cứu sâu.

Ý nghĩa của kết quả là cung cấp một công cụ kiểm định khả năng lập lịch hiệu quả, có thể ứng dụng trong các hệ thống thời gian thực phức tạp, giúp giảm thiểu rủi ro do lỗi lập lịch và nâng cao độ tin cậy của hệ thống.

Đề xuất và khuyến nghị

1. Triển khai thuật toán biểu đồ xấp xỉ trong phần mềm lập lịch thời gian thực: Động từ hành động là "ứng dụng", mục tiêu là tăng tốc độ kiểm định khả năng lập lịch, thời gian thực hiện trong vòng 6 tháng, chủ thể thực hiện là các nhóm phát triển phần mềm hệ thống thời gian thực.

2. Tối ưu hóa tham số 𝜀 và số bước k trong thuật toán: Động từ "điều chỉnh", nhằm cân bằng giữa độ chính xác và hiệu quả tính toán, thực hiện trong 3 tháng, chủ thể là các nhà nghiên cứu và kỹ sư phần mềm.

3. Mở rộng nghiên cứu cho các hệ đa bộ xử lý và nhiệm vụ không tuần hoàn: Động từ "mở rộng", mục tiêu là áp dụng thuật toán cho các hệ thống phức tạp hơn, thời gian dự kiến 1 năm, chủ thể là các viện nghiên cứu và trường đại học.

4. Phát triển công cụ mô phỏng và đánh giá trực quan: Động từ "phát triển", nhằm hỗ trợ người dùng dễ dàng đánh giá khả năng lập lịch qua giao diện đồ họa, thời gian 6 tháng, chủ thể là các công ty phần mềm và nhóm nghiên cứu.

Đối tượng nên tham khảo luận văn

1. Nhà phát triển phần mềm hệ thống thời gian thực: Có thể áp dụng thuật toán để kiểm tra và tối ưu lịch trình các nhiệm vụ, giảm thiểu lỗi lập lịch gây ảnh hưởng đến hiệu suất và an toàn.

2. Nhà nghiên cứu trong lĩnh vực công nghệ phần mềm và hệ thống nhúng: Sử dụng luận văn làm cơ sở lý thuyết và phương pháp để phát triển các thuật toán lập lịch mới hoặc mở rộng nghiên cứu.

3. Kỹ sư thiết kế hệ thống điều khiển tự động: Áp dụng kết quả để đảm bảo các nhiệm vụ điều khiển được thực hiện đúng thời hạn, nâng cao độ tin cậy của hệ thống.

4. Giảng viên và sinh viên ngành công nghệ thông tin, công nghệ phần mềm: Tham khảo để hiểu sâu về lập lịch hệ thời gian thực, các phương pháp kiểm định khả năng lập lịch và ứng dụng thuật toán xấp xỉ.

Câu hỏi thường gặp

1. Thuật toán biểu đồ xấp xỉ có ưu điểm gì so với các phương pháp truyền thống?
   Thuật toán có độ phức tạp đa thức, cho phép kiểm định nhanh hơn trong các hệ có số lượng nhiệm vụ lớn, đồng thời duy trì độ chính xác cao với tỉ lệ chấp nhận trên 90%, vượt trội so với các phương pháp cận trên tuyến tính.

2. Phương pháp này có áp dụng được cho hệ đa bộ xử lý không?
   Hiện tại, nghiên cứu tập trung vào hệ đơn bộ xử lý. Tuy nhiên, phương pháp có thể được mở rộng trong tương lai để áp dụng cho hệ đa bộ xử lý với các điều chỉnh phù hợp.

3. Làm thế nào để lựa chọn tham số 𝜀 và số bước k trong thuật toán?
   Tham số 𝜀 và k được điều chỉnh dựa trên yêu cầu về độ chính xác và thời gian tính toán. Thực nghiệm cho thấy k từ 3 đến 5 là phù hợp để đạt hiệu quả cao mà không làm tăng quá nhiều chi phí tính toán.

4. Độ trễ phát hành ảnh hưởng thế nào đến khả năng lập lịch?
   Độ trễ phát hành làm tăng độ phức tạp trong việc xác định thời điểm sẵn sàng thực hiện nhiệm vụ, ảnh hưởng đến tính khả thi của lịch trình. Thuật toán xấp xỉ được thiết kế để xử lý hiệu quả trường hợp này.

5. Có thể áp dụng thuật toán cho các nhiệm vụ không tuần hoàn không?
   Luận văn tập trung vào nhiệm vụ tuần hoàn. Việc áp dụng cho nhiệm vụ không tuần hoàn đòi hỏi nghiên cứu thêm để điều chỉnh mô hình và thuật toán cho phù hợp.

Kết luận

• Đã đề xuất thành công thuật toán kiểm định khả năng lập lịch xấp xỉ cho hệ thời gian thực với độ ưu tiên cố định, 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 kết quả xấp xỉ với tỉ lệ chấp nhận cao, vượt trội so với các phương pháp cận trên tuyến tính hiện có.
• Thực nghiệm với 300 lần lặp cho các bộ tham số khác nhau cho thấy tính ổn định và hiệu quả của thuật toán trong nhiều điều kiện thực tế.
• Thuật toán có khả năng điều chỉnh độ chính xác thông qua tham số 𝜀 và số bước k, phù hợp với yêu cầu đa dạng của các hệ thống thời gian thực.
• Hướng phát triển tiếp theo là mở rộng thuật toán cho hệ đa bộ xử lý và nhiệm vụ không tuần hoàn, đồng thời phát triển công cụ hỗ trợ mô phỏng và đánh giá trực quan.

Để nâng cao hiệu quả quản lý và vận hành hệ thống thời gian thực, các nhà nghiên cứu và kỹ sư được khuyến khích áp dụng và phát triển thêm dựa trên kết quả luận văn này.

Trích đoạn nội dung tài liệu

ĐẠ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 z ĐẠ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 z 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). 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 z 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). z 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 z 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. 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. 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. 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. Tầm quan trọng của hệ thời gian thực Ngày nay, các hệ thống thời gian thực đóng một vai trò quan trọng trong xã hội vì ngày càng có nhiều hệ thống phức tạp dựa một phần hoặc hoàn toàn vào sự điều khiển của máy tính.