🔗 Vì phần này yêu cầu kiến thức cơ bản của phần định thời CPU nên mình nghĩ các bạn nên đọc qua trước bài viết của Ren: Các Tiến Trình Trong Hệ Điều Hành Máy Tính
🌐 Để tìm về hệ điều hành và các kiến thức liên quan, hãy khám phá thêm trên trang web của tôi: Quan Notes
Định thời là chiến lược lựa chọn tiến trình phù hợp để được thực thi sao cho đạt được hiệu quả cao nhất.
Hệ thống thời gian thực là các hệ thống thực hiện các nhiệm vụ thời gian thực. Những nhiệm vụ này cần được thực hiện ngay lập tức với một mức độ khẩn cấp nhất định.
Định thời CPU cho thời gian thực có nhiều thách thức do yêu cầu về tính chất thời gian thực.
Có hai dạng hệ thống thời gian thực:
-
Soft real-time systems: Các tác vụ quan trọng sẽ được cấp độ ưu tiên lớn nhất, nhưng không đảm bảo bất cứ điều gì khác.
-
Hard real-time systems: Các tác vụ phải được hoàn thành trước deadline. Nếu một tác vụ không hoàn thành trong deadline, nó được coi là thất bại, và việc thực thi sau deadline không mang lại giá trị hoặc có thể bị hệ thống hủy bỏ.
Trong bài viết này, chúng ta sẽ tìm hiểu về một vài vấn đề liên quan đến định thời tiến trình trong cả hệ thống Soft và Hard real-time systems.
⏳I/ Giảm thiểu độ trễ
Hệ thống thời gian thực hoạt động theo mô hình hướng sự kiện (event-driven), chờ các sự kiện từ phần mềm (như bộ đếm thời gian hết hạn) hoặc phần cứng (như phương tiện điều khiển từ xa phát hiện chướng ngại vật). Khi sự kiện xảy ra, hệ thống phải phản hồi và xử lý nhanh chóng. Độ trễ sự kiện ** (event latency)** là thời gian từ khi sự kiện xảy ra đến khi được phục vụ.
Các sự kiện trong hệ thống thời gian thực có yêu cầu độ trễ khác nhau. Ví dụ, hệ thống phanh chống bó cứng yêu cầu độ trễ 3-5 mili giây để phản hồi khi bánh xe trượt, nếu không ô tô có thể mất kiểm soát. Ngược lại, hệ thống radar trên máy bay có thể chấp nhận độ trễ vài giây. Có hai chế đô quyết định trong định thời:
- Không trưng dụng (Non-preemptive): Khi ở trạng thái running, tiến trình sẽ thực thi cho đến khi kết thúc hoặc bị ngắt do yêu cầu I/O.
- Trưng dụng (Preemptive): Tiến trình đang thực thi (ở trạng thái running) có thể bị ngắt giữa chừng và chuyển về trạng thái ready.
Hiệu suất hệ thống thời gian thực bị ảnh hưởng bởi hai loại độ trễ:
1. Độ trễ ngắt (Interrupt latency):
- Độ trễ ngắt là thời gian từ khi ngắt đến CPU đến khi bắt đầu routine phục vụ ngắt (ISR).
- Hệ điều hành phải hoàn thành lệnh hiện tại, xác định loại ngắt, lưu trạng thái quá trình hiện tại, rồi mới xử lý ngắt.
- Giảm thiểu và giới hạn độ trễ ngắt là rất quan trọng, đặc biệt trong hard real-time, và ngắt chỉ được phép tắt trong thời gian rất ngắn để cập nhật cấu trúc dữ liệu kernel.
2. Độ trễ phân phối (Dispatch latency):
Độ trễ phân phối là thời gian để bộ định thời dừng một quá trình và khởi động một quá trình khác. Kỹ thuật hiệu quả nhất để giữ độ trễ phân phối thấp là cung cấp kernel có thể trưng dụng. Bao gồm:
- Giai đoạn xung đột: Tạm dừng các tác vụ kernel và giải phóng tài nguyên từ các quá trình ưu tiên thấp.
- Giai đoạn phân phối: Định thời quá trình ưu tiên cao lên CPU.
Hệ thống thời gian thực cần giảm thiểu cả độ trễ ngắt và độ trễ phân phối để đảm bảo phản hồi tức thời cho các tác vụ thời gian thực.
🎯II/ Định thời dựa trên độ ưu tiên
Tính năng cốt lõi của hệ điều hành thời gian thực là phản hồi ngay lập tức với tiến trình thời gian thực khi yêu cầu CPU. Do đó, bộ định thời phải hỗ trợ định thời theo độ ưu tiên với chế độ trưng dụng.
- Các thuật toán này gán ưu tiên cho tiến trình dựa trên mức độ quan trọng; nhiệm vụ quan trọng hơn có ưu tiên cao hơn.
- Nếu hỗ trợ trưng dụng, tiến trình đang chạy sẽ bị tạm dừng khi có tiến trình ưu tiên cao hơn sẵn sàng.
Ví dụ:
- Các hệ điều hành như Windows, Linux, Solaris gán ưu tiên cao nhất cho tiến trình thời gian thực.
- Windows có 32 mức ưu tiên, với mức 16-31 dành riêng cho tiến trình thời gian thực. Linux và Solaris có cơ chế tương tự.
Hạn chế:
- Định thời dựa trên ưu tiên với trưng dụng chỉ đảm bảo chức năng hệ thống thời gian thực mềm.
- Hệ thống thời thực cứng đảm bảo thêm rằng các tác vụ được phục vụ đúng hạn chót, đòi hỏi các tính năng định thời bổ sung.
📐III/ Mô hình tác vụ trong thời gian thực
1/ Tác vụ chu kỳ (Periodic Tasks):
- Là các tác vụ thời gian thực lặp lại sau một khoảng thời gian cố định, được gọi là chu kỳ (period).
- Các tác vụ này được điều khiển bởi ngắt đồng hồ (clock interrupts). Ví dụ: Thu thập dữ liệu từ cảm biến cứ mỗi 5 giây.
a/ Rate Monotonic:
- Độ ưu tiên được gán dựa trên nghịch đảo của chu kỳ => Chu kỳ ngắn thì độ ưu tiên cao và ngược lại.
- Một tập hợp tiến trình có thể được định thời nếu thỏa mãn công thức:
Để hiểu được các hoạt động của Rate Monotonic thì chúng ta có ví dụ bảng này:
Tính U:
Ngưỡng RMS cho n = 3:
Kết quả: U = 0.75 ≤ 0.7797, do đó tập hợp tiến trình này có thể định thời được được với Dựa trên chu kỳ: • P1 (T1 = 20): Ưu tiên thấp nhất. • P2 (T2 = 5): Ưu tiên cao nhất. • P3 (T3 = 10): Ưu tiên thứ hai.
Thứ tự ưu tiên là: P2 > P3 > P1.
Hình minh họa trên biểu diễn rằng trong hệ thống, P2 chạy 2 lần mỗi 5 đơn vị thời gian, P3 chạy 2 lần mỗi 10 đơn vị thời gian và P1 chạy 3 lần trong 20 đơn vị thời gian.
b/ Earliest Deadline First:
Earliest Deadline First Là thuật toán định thời ưu tiên động tối ưu trong hệ thống thời gian thực, áp dụng cho cả định thời tĩnh và động.
- Nguyên tắc ưu tiên: Tiến trình có thời hạn hoàn thành sớm nhất được gán ưu tiên cao nhất, tiến trình có thời hạn muộn hơn được ưu tiên thấp hơn.
- Hiệu quả cao: Có thể đạt 100% sử dụng CPU mà vẫn đảm bảo tất cả tiến trình đáp ứng thời hạn, miễn là lịch trình khả thi.
- Điều chỉnh ưu tiên: Khi tiến trình mới sẵn sàng chạy, nó thông báo thời hạn cho hệ thống, và ưu tiên của các tiến trình hiện tại được điều chỉnh động dựa trên thời hạn mới.
2/ Tác vụ phi chu kỳ (Aperiodic Tasks):
Tác vụ phi chu kỳ là các tác vụ thời gian thực xảy ra tại các thời điểm ngẫu nhiên, không theo chu kỳ cố định.
- Khoảng thời gian giữa hai lần xuất hiện có thể rất ngắn (thậm chí bằng 0) hoặc rất dài.
- Các tác vụ này thường là tác vụ thời gian thực mềm (soft real-time) và liên quan đến tương tác ngẫu nhiên. Ví dụ: Nhấn phím trên bàn phím để nhập liệu.
- Các giải thuật định thời của tác vụ chu kỳ: Total Bandwidth Server, Enhanced Virtual Release Advancing (Các thuật toán này các bạn có thể tự tìm hiểu thêm nha).
📚 Nguồn
GeeksforGeeks: Rate-monotonic scheduling
Silberschatz, A., Gagne, G., & Galvin, P. B. (n.d.). Operating System Concepts. [Edition number if known, e.g., 10th ed.]. Wiley.
📝 Liên hệ với mình
✍️ Blog: Quan Notes
💼 Linkedin: Võ Minh Quân