Thuật toán lập lịch tác vụ trong RTOS

Trong hệ điều hành thời gian thực, bộ lập lịch tác vụ (task scheduler) giữ vai trò quan trọng, quyết định thứ tự và thời điểm thực thi các tác vụ. Việc lựa chọn thuật toán lập lịch phù hợp không chỉ ảnh hưởng đến hiệu suất và tính ổn định của hệ thống mà còn đảm bảo các yêu cầu thời gian thực được đáp ứng đúng hạn. Bài viết này sẽ giới thiệu về các thuật toán lập lịch phổ biến trong RTOS và hiểu được cách sử dụng của các thuật toán này để hệ thống vận hành mượt mà, chính xác.

Khái niệm lập lịch và bộ lập lịch

Lập lịch tác vụ (Scheduling) là quá trình xác định thứ tự thực thi các tác vụ, bao gồm việc quản lý và thực thi nhiều tác vụ với mục tiêu đảm bảo các tác vụ luôn đáp ứng đúng hạn. Mỗi tác vụ trong hệ thống đều có các thuộc tính liên quan, bao gồm mức độ ưu tiên, thời gian thực hiện và chu kỳ. Bộ lập lịch sử dụng các thuộc tính này để xác định thứ tự thực thi các tác vụ. Mục tiêu chính của lập lịch thời gian thực là giảm thiểu độ trễ của tác vụ và đảm bảo hoàn thành các tác vụ quan trọng trong giới hạn thời gian đã chỉ định

Các đặc điểm chính của lập lịch RTOS

• Hành vi xác định (Deterministic Behavior): Hệ thống phải xử lý các tác vụ một cách có thể dự đoán được, trong giới hạn thời gian đã xác định trước.
• Đa nhiệm ưu tiên (Preemptive Multitasking): Các tác vụ có mức ưu tiên cao có thể tạm dừng các tác vụ có mức ưu tiên thấp hơn để đảm bảo đáp ứng đúng hạn.
• Ưu tiên hóa (Prioritization): Các tác vụ được thực thi dựa trên mức độ ưu tiên, thường được xác định dựa trên các ràng buộc thời gian.

Để thực hiện được các đặc tính trên, hệ điều hành thời gian thực cần một thành phần trung tâm gọi là bộ lập lịch (scheduler). Bộ lập lịch là một thành phần phần mềm của hệ điều hành chịu trách nhiệm xác định thứ tự mà các tác vụ, tiến trình hoặc luồng sẽ được CPU thực thi. Trong hệ điều hành thời gian thực RTOS, bộ lập lịch đóng vai trò đặc biệt quan trọng trong việc quản lý các tác vụ để đảm bảo các tác vụ được thực hiện đúng theo các ràng buộc thời gian. Bộ lập lịch sử dụng nhiều thuật toán lập lịch khác nhau để quyết định tác vụ nào được cấp quyền sử dụng CPU và trong thời gian bao lâu.

Chức năng chính của bộ lập lịch

• Lựa chọn tác vụ (Task Selection): Xác định tác vụ nào sẽ được thực thi tiếp theo dựa trên thuật toán lập lịch được sử dụng.
• Tạm dừng và chuyển đổi tác vụ (Preemption and Context Switching): Thực hiện chuyển đổi giữa các tác vụ nếu thuật toán cho phép ưu tiên ngắt.
• Quản lý thời gian (Time Management): Theo dõi thời hạn (deadline), thời gian thực thi và chu kỳ lặp lại của các tác vụ định kỳ.
• Ưu tiên hóa (Priorization): Gán và quản lý mức độ ưu tiên để đảm bảo các tác vụ quan trọng hơn nhận được thời gian xử lý phù hợp.
• Quản lý tài nguyên (Resource Management): Phân bổ và thu hồi tài nguyên CPU một cách hiệu quả giữa các tác vụ nhằm tối ưu hiệu suất hệ thống.

Ngoài hai khái niệm quan trọng Scheduling và Scheduler, trước khi đi vào các thuật toán lập lịch cụ thể, chúng ta cần hiểu các đặc trưng cơ bản của một tác vụ, cụ thể là:

• Chu kỳ (Period): Chu kỳ của một tác vụ là khoảng thời gian giữa hai lần xuất hiện liên tiếp của tác vụ.
• Deadline: Deadline là khoảng thời gian mà trong đó tác vụ phải được thực hiện xong. Nếu tác vụ không hoàn thành đúng hạn thì bị coi là thất bại.
• Thời gian thực thi (Execution time): Thời gian thực thi đo lường khoảng thời gian cần thiết để hoàn thành toàn bộ tác vụ.

Phân loại thuật toán lập lịch

Có rất nhiều thuật toán lập lịch khác nhau được sử dụng để sắp xếp việc thực thi các tác vụ trên CPU. Chúng được chia thành hai loại chính: thuật toán lập lịch ưu tiên (preemptive) và thuật toán lập lịch không ưu tiên (non-preemptive).

Lập lịch ưu tiên (Preemptive Scheduling)

Lập lịch ưu tiên cho phép tạm dừng một tác vụ đang chạy để nhường chỗ cho một tác vụ khác có mức “ưu tiên cao hơn”. Tác vụ bị gián đoạn sẽ được bộ lập lịch chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng. Cơ chế chuyển đổi linh hoạt này giữa các tác vụ chính là một dạng đa nhiệm (multitasking). Thuật toán này yêu cầu gán mức độ ưu tiên cho từng tác vụ, và nếu trong hàng đợi xuất hiện một tác vụ có ưu tiên cao hơn, tác vụ đang chạy sẽ bị ngắt để nhường quyền điều khiển CPU cho tác vụ đó.

Lấy ví dụ, giả sử chúng ta có ba tác vụ: Task 1, Task 2 và Task 3. Trong đó, Task 1 có mức ưu tiên thấp nhất, còn Task 3 có mức ưu tiên cao nhất. Thời điểm bắt đầu và thời gian thực thi của từng tác vụ được liệt kê trong bảng dưới đây.

Trong hình, có thể thấy Task 1 là tác vụ đầu tiên bắt đầu thực thi, vì Task 1 là tác vụ đến trước (tại t = 10 μs). Task 2 đến tại t = 40 μs và do có mức ưu tiên cao hơn, bộ lập lịch sẽ tạm dừng Task 1 và chuyển Task 2 sang trạng thái đang chạy. Task 3, tác vụ có mức ưu tiên cao nhất, đến tại t = 60 μs. Lúc này, Task 2 bị tạm dừng và Task 3 được chuyển sang trạng thái đang chạy. Vì là tác vụ có ưu tiên cao nhất, Task 3 chạy cho đến khi hoàn thành tại t = 100 μs. Sau đó, Task 2 tiếp tục thực thi vì là tác vụ có ưu tiên cao nhất hiện tại. Cuối cùng, Task 1 là tác vụ hoàn thành sau cùng.

Lập lịch không ưu tiên (hay còn gọi là Lập lịch hợp tác)

Trong lập lịch không ưu tiên, bộ lập lịch có quyền kiểm soát các tác vụ hạn chế hơn. Bộ lập lịch chỉ có thể khởi chạy một tác vụ và phải chờ cho đến khi tác vụ đó hoàn thành hoặc tác vụ tự nguyện trả quyền điều khiển. Một tác vụ đang chạy không thể bị bộ lập lịch dừng lại.

Tương tự với lập lịch ưu tiên, chúng ta cũng có ba tác vụ, tuy nhiên ba tác vụ này thực hiện lập lịch theo thuật toán không ưu tiên. Khi bắt đầu, mỗi tác vụ sẽ hoàn thành trước khi tác vụ tiếp theo bắt đầu. Lập lịch không ưu tiên có thể đơn giản việc đồng bộ hóa giữa các tác vụ, nhưng điều này đi kèm với thời gian phản hồi đối với các sự kiện tăng lên, vì vậy phương pháp này thường ít được sử dụng trong các hệ thống thời gian thực phức tạp.

So sánh giữa lập lịch ưu tiên và lập lịch không ưu tiên

Sự khác nhau cơ bản giữa hai cơ chế này nằm ở cách CPU được phân bổ cho các tác vụ:

• Với lập lịch ưu tiên, CPU chỉ được cấp phát cho tác vụ trong một khoảng thời gian giới hạn.
• Còn lập lịch không ưu tiên sẽ cấp CPU cho tác vụ cho đến khi tác vụ đó hoàn tất hoặc chuyển sang trạng thái chờ.

Trong lập lịch ưu tiên, tác vụ đang chạy có thể bị tạm dừng nếu có một tác vụ có mức ưu tiên cao hơn sẵn sàng thực thi. Ngược lại, trong lập lịch không ưu tiên, tác vụ sẽ tiếp tục chạy đến khi hoàn tất, không bị gián đoạn giữa chừng. Lập lịch ưu tiên thường đi kèm với chi phí xử lý cao hơn, do hệ thống phải thực hiện chuyển đổi ngữ cảnh liên tục và duy trì hàng đợi sẵn sàng. Trong khi đó, lập lịch không ưu tiên đơn giản hơn, vì không cần chuyển đổi ngữ cảnh thường xuyên.

Một hạn chế của lập lịch ưu tiên là nếu các tác vụ ưu tiên cao xuất hiện liên tục, các tác vụ ưu tiên thấp có thể bị trì hoãn kéo dài, thậm chí không được thực thi. Tương tự, trong lập lịch không ưu tiên, nếu CPU đang xử lý một tác vụ có thời gian chạy dài, các tác vụ ngắn hơn cũng phải chờ đợi. Lập lịch ưu tiên được xem là linh hoạt hơn, vì tác vụ quan trọng có thể truy cập CPU ngay khi sẵn sàng, bất kể CPU đang chạy tác vụ nào. Trong khi đó, lập lịch không ưu tiên lại cứng nhắc hơn, vì CPU chỉ được cấp phát lại sau khi tác vụ hiện tại hoàn tất. Ngoài ra, lập lịch ưu tiên còn tốn kém hơn về mặt tài nguyên, do cần duy trì tính toàn vẹn của dữ liệu chia sẻ giữa các tác vụ — điều mà lập lịch không ưu tiên ít gặp phải.

Những thuật toán lập lịch phổ biến sử dụng trong RTOS

Không phải tất cả đều phù hợp để sử dụng trong các hệ thống nhúng thời gian thực. Hiện tại, các thuật toán được dùng nhiều nhất trong các hệ thống RTOS thực tế là lập lịch không ưu tiên, lập lịch vòng tròn (round-robin) và lập lịch ưu tiên có khả năng tạm dừng (preemptive priority scheduling).

First Come, First Served (FCFS)

FCFS là một thuật toán lập lịch không ưu tiên, không gán mức độ ưu tiên cho các tác vụ. Tác vụ nào đến trước trong hàng đợi lập lịch (tức là vào trạng thái sẵn sàng) sẽ được chuyển vào trạng thái đang chạy trước và bắt đầu sử dụng CPU. Đây là một thuật toán khá đơn giản, đảm bảo rằng tất cả các tác vụ cuối cùng đều sẽ được thực hiện. Tuy nhiên, thời gian phản hồi tương đối cao vì đây là loại thuật toán không ưu tiên.

Shortest Job First (SJF)

Trong thuật toán SJF, bộ lập lịch cần biết trước thời gian thực thi của mỗi tác vụ và sau đó chọn tác vụ có thời gian thực thi ngắn nhất để chạy tiếp theo. SJF là một thuật toán không ưu tiên, nhưng cũng có phiên bản ưu tiên (preemptive), còn gọi là “shortest remaining time”, trong đó tiêu chí lập lịch dựa trên thời gian thực thi còn lại của tác vụ. Nếu một tác vụ đang chạy và một tác vụ khác có thời gian thực thi còn lại ngắn hơn xuất hiện, tác vụ đang chạy có thể bị tạm dừng. Một hạn chế của thuật toán này là cần biết trước tổng thời gian thực thi của tác vụ trước khi chạy.

Priority Scheduling

Priority Scheduling là một trong những thuật toán phổ biến nhất. Mỗi tác vụ được gán một mức ưu tiên, và nguyên tắc cơ bản là tác vụ có ưu tiên cao nhất sẽ được sử dụng CPU trước. Trong phiên bản preemptive, tác vụ đang chạy có thể bị dừng nếu một tác vụ có ưu tiên cao hơn xuất hiện. Còn đối với trường hợp non-preemptive, một khi tác vụ đã bắt đầu chạy, tác vụ này sẽ không bị gián đoạn bởi tác vụ có ưu tiên cao hơn. Tuy nhiên, không phải tất cả các tác vụ đều có mức ưu tiên duy nhất, nên sẽ có những tác vụ cùng mức ưu tiên. Khi đó, các phương pháp khác nhau có thể được áp dụng để xử lý, chẳng hạn như lập lịch FCFS hoặc round-robin.

Round-Robin Scheduling

Round-robin là một thuật toán lập lịch chia sẻ thời gian, trong đó mỗi tác vụ được gán một khoảng thời gian cố định. Mỗi tác vụ sẽ chạy trong thời gian được chỉ định, và nếu chưa hoàn thành khi hết khoảng thời gian đó, tác vụ sẽ bị đưa xuống cuối hàng đợi để các tác vụ khác được thực thi. Round-robin hữu ích nhưng không phù hợp cho các hệ thống thời gian thực có các deadline nghiêm ngặt.

Trong minh họa ở trên, ta có thể thấy rằng mỗi tác vụ chỉ được phép chạy trong khoảng thời gian cố định cho mỗi lần thực thi. Tác vụ 1 chạy trong 0,5 đơn vị thời gian và bị tạm dừng để nhường cho tác vụ 2, sau đó là tác vụ 3 sau khi hoàn thành khoảng thời gian được phân bổ. Vì khoảng thời gian phân bổ cho tác vụ 2 vừa đủ cho thời gian thực thi, nên tác vụ này luôn được thực hiện một lần liên tục. Ngược lại, khoảng thời gian phân bổ cho tác vụ 3 nhỏ hơn thời gian thực thi, nên tác vụ này phải được thực hiện qua nhiều lần.

Lựa chọn thuật toán lập lịch

Các phiên bản RTOS khác nhau có thể hỗ trợ nhiều thuật toán lập lịch khác nhau. Không có thuật toán chung nào phù hợp cho mọi trường hợp sử dụng. Mỗi thuật toán lập lịch sẽ có ưu và nhược điểm riêng, liên quan đến tốc độ phản hồi, độ phức tạp khi triển khai,... Thuật toán được lựa chọn phải luôn đáp ứng được các yêu cầu về thời gian của tác vụ. Chính vì những lý do này mà việc lựa chọn thuật toán trước khi phát triển ứng dụng là vô cùng quan trọng. Việc chọn thuật toán lập lịch phù hợp cho một hệ thống RTOS phụ thuộc vào nhiều yếu tố:

• Đặc điểm tác vụ: Cần xem xét bản chất của các tác vụ: định kỳ (periodic), không định kỳ (aperiodic) hay ngẫu nhiên (sporadic). Một số thuật toán, như rate-monotonic, tối ưu cho các tác vụ định kỳ, trong khi EDF lại xử lý các tác vụ không định kỳ hiệu quả hơn.
• Yêu cầu hệ thống: Phân tích các yêu cầu thời gian thực, bao gồm thời hạn (deadline), thời gian phản hồi và thông lượng (throughput). Thuật toán được chọn phải đảm bảo đáp ứng các yêu cầu này.
• Hạn chế tài nguyên: Đánh giá các tài nguyên phần cứng sẵn có như số lõi CPU, bộ nhớ và thiết bị I/O. Một số thuật toán sử dụng tài nguyên hiệu quả hơn các thuật toán khác.
• Khả năng dự đoán: Mức độ dự đoán của các thuật toán khác nhau. Thuật toán ưu tiên cố định (fixed-priority) thường dễ dự đoán, trong khi các thuật toán động như EDF phản ứng nhanh hơn nhưng phân tích phức tạp hơn.
• Độ phức tạp: Cân nhắc độ phức tạp của thuật toán so với khả năng tính toán sẵn có. Các thuật toán đơn giản dễ triển khai và gỡ lỗi hơn.

Lập lịch (scheduling) là một yếu tố then chốt trong các hệ điều hành thời gian thực, giúp đảm bảo các tác vụ được thực thi đúng thời điểm trong những ứng dụng đòi hỏi tính xác định cao. Việc lựa chọn thuật toán lập lịch phù hợp đóng vai trò quan trọng trong việc đáp ứng các yêu cầu thời gian thực của hệ thống. Cần xem xét cẩn trọng đặc điểm của các tác vụ, yêu cầu của hệ thống và tài nguyên sẵn có trước khi chọn thuật toán lập lịch thích hợp. Cuối cùng, thuật toán được chọn phải phù hợp với nhu cầu và giới hạn cụ thể của hệ thống, nhằm đảm bảo hiệu năng ổn định, đáng tin cậy và có thể dự đoán được. Nếu bạn thấy bài viết hữu ích, hãy like, share và để lại bình luận để cùng thảo luận thêm nhé!

Link tham khảo: https://open4tech.com/rtos-scheduling-algorithms/ https://www.educative.io/answers/multi-thread-scheduling-in-real-time-operating-systems-rtos https://share.google/5NjPvU8gGbtswWSdQ