Chương 1: Tổng quan về hệ thời gian thực Trình bày lí thuyết về hệ thời gian thực và các khái niệm trong hệ thời gian thực. Chương 2: Các phương pháp kiểm định sử dụng độ ưu tiên tĩnh Trình bày các khái niệm về kiểm định sử dụng độ ƣu tiên tĩnh. Các thuật toán kiểm định sử dụng độ ƣu tiên tĩnh. Phƣơng pháp kiểm định dựa trên phân tích thời gian phản ứng (RTA) và phƣơng pháp kiểm định dựa trên phân tích yêu cầu bộ vi xử lí (PDA).
Chương 3: Sử dụng Biểu đồ xấp xỉ để kiểm định khả năng lập lịch và tính xấp xỉ thời gian phản ứng của các nhiệm vụ cho hệ với kì hạn ràng buộc. Xây dựng phƣơng pháp kiểm định tính lập lịch và tính xấp xỉ thời gian phản ứng của các nhiệm vụ nhờ sử dụng Biểu đồ xấp xỉ cho hệ trƣờng hợp kỳ hạn ràng buộc. Chương 4: Mô phỏng đánh giá Biểu Đồ Xấp Xỉ Xây dựng mô phỏng để đánh giá Biểu đồ xấp xỉ bằng cách so sánh các kết quả thu đƣợc với các kết quả có đƣợc từ phƣơng pháp kiểm định xấp xỉ của Bini and Baruah. Chương 5: Kết luận 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1: TỔNG QUAN VỀ HỆ THỜI GIAN THỰC 1.1 Hệ thời gian thực [1, 2] 1.1 Khái niệm hệ thời gian thực Hệ thời gian thực là một hệ thống máy tính phải phản ứng kịp thời và chính xác với các sự kiện trong môi trƣờng.
Trong hệ thời gian thực thì kết quả đƣợc tạo ra phải đáp ứng đầy đủ hai yêu cầu là độ chính xác về giá trị và tính kịp thời về mặt thời gian. Một kết quả đƣợc tạo ra muộn có thể là vô ích hoặc thậm chí có thể gây ra những thảm họa cho hệ thống. Trong một hệ thời gian thực thì mỗi nhiệm vụ(task) có một kì hạn (deadline) riêng, là thời điểm chậm nhất mà kết quả phải đƣợc tạo ra. Một kết quả đƣợc tạo ra sau kì hạn của nhiệm vụ là vô ích hoặc thậm chí là có hại cho hệ thống.2 Các đặc điểm chính của một hệ thời gian thực Các đặc điểm chính của một hệ thời gian thực bao gồm: Tính bị động: Các nhiệm vụ có thể sản sinh thêm trong quá trình hoạt động của hệ thống.
Thời gian xuất hiện của các nhiệm vụ không thể biết trƣớc nên hệ thống luôn ở trong trạng thái bị động. Tính kịp thời: Vì các nhiệm vụ có thể phát sinh ở một thời điểm bất kì mà không dự đoán trƣớc đƣợc nên hệ thống đƣợc thiết kế để phản ứng kịp thời với các nhiệm vụ phát sinh. Tính đồng thời: Trong quá trình hoạt động của hệ thống thì tại một thời điểm có thể có nhiều nhiệm vụ đƣợc phát sinh. Vì vậy, hệ thống đƣợc thiết kế để phản ứng đồng thời với các nhiệm vụ đƣợc phát sinh đó.
Lập lịch dựa trên độ ưu tiên: Mỗi nhiệm vụ trong hệ thống sẽ đƣợc gán một độ ƣu tiên. Độ ƣu tiên sẽ cho biết tầm quan trọng của nhiệm vụ trong hệ thống. Nhiệm vụ có độ ƣu tiên cao hơn sẽ đƣợc thực hiện trƣớc. 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Phân loại hệ thời gian thực Thông thƣờng, một hệ thống thời gian thực có thể đƣợc phân thành một trong 2 loại sau: Hệ thời gian thực cứng (Hard realtime system): Là hệ thời gian thực mà việc sản sinh kết quả chậm trễ sẽ gây ra những hậu quả thảm khốc không những cho hệ thống mà còn trên nhiều phƣơng diện khác.
Trong một hệ thời gian thực cứng thì yêu cầu sản sinh kết quả kịp thời là đặc biệt quan trọng. Chính vì tính chất nhƣ vậy nên hệ thời gian thực cứng thƣờng là các hệ thống yêu cầu độ chính xác cao nhƣ phòng thủ tên lửa, điều khiển hàng không… Hệ thời gian thực mềm (Soft realtime system): Là hệ thời gian thực mà việc sản sinh kết quả chậm trễ thƣờng không gây ra tác hại và hệ thống vẫn có thể hoạt động bình thƣờng. Đôi khi, kết quả đƣợc tạo ra này vẫn còn có tác dụng cho hệ thống.4 Kiểm định khả năng lập lịch của một hệ thời gian thực Tính lập lịch được của hệ thời gian thực: Trong một hệ thời gian thực, số lƣợng các nhiệm vụ là tƣơng đối nhiều và nhiệm vụ có thể phát sinh thêm trong quá trình hoạt động của hệ thống. Nếu bằng một cách phân công thực hiện nào đó mà tất cả các nhiệm vụ đều đƣợc hoàn thành mà không bị lỡ kì hạn của chúng thì hệ thống đó đƣợc gọi là lập lịch đƣợc.
Để biết hệ thống có lập lịch đƣợc hay không ta phải sử dụng một thuật toán kiểm định nào đó. Thuật toán kiểm định: Ta có thể hiểu một tập hữu hạn các quy tắc và các phép toán để kiểm tra xem một hệ thời gian thực có lập lịch đƣợc hay không đƣợc gọi là một thuật toán kiểm định. 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Nhiệm vụ thời gian thực (task) 1.1 Khái niệm nhiệm vụ thời gian thực Một hệ thời gian thực thƣờng bao gồm nhiều nhiệm vụ thời gian thực. Việc kiểm định khả năng lập lịch của hệ thống thực chất là tiến hành kiểm định khả năng lập lịch của từng nhiệm vụ trong hệ thống từ đó kết luận đƣợc tính lập lịch của cả hệ thống.
Ở mức khái niệm ta có thể hiểu một nhiệm vụ thời gian thực là một yêu cầu cần đƣợc xử lí phát sinh trong môi trƣờng hoạt động của hệ thống. Thời gian xuất hiện của các nhiệm vụ là không biết trƣớc và mỗi nhiệm vụ đều có một kì hạn riêng. Trong trƣờng hợp có một nhiệm vụ mới phát sinh, việc thêm nhiệm vụ này vào có thể làm cho hệ thống không lập lịch đƣợc. Vì vậy, trƣớc khi quyết định chấp nhận thực hiện một nhiệm vụ mới phát sinh, ngƣời ta phải tính toán xem liệu sau khi thêm thì các kì hạn của các nhiệm vụ có đƣợc đáp ứng nữa hay không.2 Các thuộc tính của một nhiệm vụ thời gian thực 1.1 Các thuộc tính cơ bản Các thuộc tính cơ bản của một nhiệm vụ thời gian thực bao gồm: ai : Là thời điểm mà tại đó nhiệm vụ yêu cầu đƣợc thực hiện.
Ci : Thời gian thực thi. Là thời gian cần thiết để xử lí nhiệm vụ mà không bị gián đoạn. Là thời điểm chậm nhất mà kết quả phải đƣợc tạo ra. Sau mỗi chu kì thì nhiệm vụ lại yêu cầu thực hiện một lần (phát sinh một job).
Di : Kì hạn tƣơng đối. Là khoảng thời gian từ lúc nhiệm vụ yêu cầu đƣợc thực hiện với kì hạn. Di = di – ai. 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1: Minh họa một số thuộc tính của nhiệm vụ 1.2 Các thuộc tính dẫn xuất Các thuộc tính dẫn xuất là các thuộc tính chỉ xuất hiện trong quá trình thực hiện hoặc đƣợc tính thống qua các thuộc tính cơ bản của một nhiệm vụ.
Chúng bao gồm: Si : Là thời điểm mà nhiệm vụ bắt đầu đƣợc thực hiện. fi : Là thời điểm mà nhiệm vụ đƣợc thực hiện xong. Ri : Thời gian phản ứng. Là khoảng thời gian từ khi nhiệm vụ yêu cầu thực hiện đến khi nhiệm vụ đƣợc thực hiện xong.
Ri = fi – ai. ui : Là hệ số sử dụng bộ vi xử lí của nhiệm vụ, đƣợc tính bởi công thức ui = Ci / Ti. Trong một hệ thì tổng các ui = U ≤ 1.3 Phân loại nhiệm vụ thời gian thực Một nhiệm vụ thời gian thực có thể phân thành một trong các loại sau: Nhiệm vụ cứng (Hard task): Một nhiệm vụ thời gian thực đƣợc gọi là cứng nếu kết quả đƣợc tạo ra sau kì hạn của nó sẽ gây ra những thiệt hại to lớn cho hệ thống. Nhiệm vụ trung gian (Firm task): Một nhiệm vụ đƣợc gọi là một trung gian nếu kết quả đƣợc tạo ra sau kì hạn của nó không gây ra thiệt hại gì cho hệ thống.
6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nhiệm vụ mềm (Soft task): Một nhiệm vụ đƣợc gọi là mềm nếu kết quả đƣợc tạo ra sau kì hạn của nó vẫn còn có một chút tác dụng cho hệ thống. Tuy nhiên, đi kèm với nó là sự xuống cấp của hệ thống. Nhiệm vụ định kì: Là nhiệm vụ mà cứ sau mỗi khoảng thời gian nhƣ nhau(chu kì) thì lại yêu cầu đƣợc thực hiện. Mỗi lần yêu cầu đƣợc thực hiện đó đƣợc gọi là một job.
Nhiệm vụ không định kì: Là nhiệm vụ mà khoảng thời gian xuất hiện các job là không giống nhau. Trong nhiệm vụ không định kì thì không tồn tại thuộc tính chu kì. Nhiệm vụ với kì hạn ràng buộc: Là nhiệm vụ mà mối quan hệ giữa kì hạn và chu kì bị ràng buộc bởi điều kiện kì hạn ≤ chu kì. Nhiệm vụ với kì hạn không ràng buộc: Là nhiệm vụ mà mối quan hệ giữa kì hạn và chu kì không bị giới hạn bởi bất kì ràng buộc nào.
7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 2: CÁC PHƢƠNG PHÁP KIỂM ĐỊNH SỬ DỤNG ĐỘ ƢU TIÊN TĨNH 2.1 Độ ƣu tiên của các nhiệm vụ Một trong những đặc điểm của một hệ thời gian thực là lập lịch dựa trên độ ƣu tiên. Theo cách thực hiện đó, mỗi nhiệm vụ trong hệ thống đều có một độ ƣu tiên của riêng mình. Độ ƣu tiên sẽ cho biết độ quan trọng của nhiệm vụ trong hệ thống và nhiệm vụ nào quan trọng hơn sẽ đƣợc ƣu tiên thực hiện trƣớc. Nhƣ vậy, ở mức khái niệm ta có thể hiểu độ ƣu tiên của nhiệm vụ là một giá trị số đƣợc gán cho nhiệm vụ để cho biết tầm quan trọng của nhiệm vụ đó trong hệ thống.
Khi có một nhiệm vụ mới phát sinh có độ ƣu tiên cao hơn độ ƣu tiên của nhiệm vụ đang đƣợc thực hiện thì nhiệm vụ đang đƣợc thực hiện sẽ bị gián đoạn để nhƣờng CPU cho nhiệm vụ mới phát sinh. Việc tính độ ƣu tiên cho nhiệm vụ có thể thực hiện theo nhiều cách khác nhau.2 Các phƣơng pháp gán độ ƣu tiên cho nhiệm vụ 2.1 Phƣơng pháp gán độ ƣu tiên tĩnh Trong phƣơng pháp gán độ ƣu tiên tĩnh thì mỗi nhiệm vụ chỉ đƣợc gán độ ƣu tiên một lần và độ ƣu tiên này sẽ tồn tại trong suốt quá trình hoạt động của nhiệm vụ trong hệ thống. Việc gán độ ƣu tiên một lần cố định cho nhiệm vụ sẽ giúp cho việc lập lịch cũng nhƣ kiểm định cho hệ thống đƣợc thực hiện một cách thuận tiện.