🌱 Core 12. Thuật toán lập lịch RTOS

    Ở post trước chúng ta đã cùng tìm hiểu về cơ chế Multi-Task và Scheduling trong RTOS. Post này mình sẽ giới thiệu sâu hơn về bộ lập lịch Scheduler và một số thuật toán lập lịch - Scheduling.

    👉 Kernel là gì?

    Kernel - hay gọi là Nhân của hệ điều hành, thực chất là một quy ước có nhiệm vụ điều phối các công việc của RTOS (Mình gọi là quy ước vì thực tế nó vẫn là do mình code nên và nạp vào bộ nhớ, chứ không phải cái gì to tát nhúng từ bên ngoài vào bên trong vi điều khiển của mình). Việc lập trình ra các Kernel hay toàn bộ hoạt động của một OS trong vi điều khiển thường được thực hiện bằng ngôn ngữ Assembly, để đảm bảo tốc độ xử lý nhanh nhất của Kernel.

• Kernel sẽ điều phối hoạt động của các Task dựa vào bộ lập lịch - Scheduler và các thuật toán lập lịch (do con người quy định). 
• Kernel sẽ quản lý tài nguyên phần cứng - bộ nhớ, để lưu trữ hoạt động của các task. 
• Kernel quản lý các công việc giao tiếp giữa các task, xử lý ngắt, ... 

    Nói chung là mọi công việc của RTOS, Kernel sẽ đại diện để thực hiện mọi công việc.

    👉 Một số thuật toán lập lịch RTOS

    Kernel sẽ gọi bộ lập lịch khi cần biết tiếp theo đến lượt Task nào được thực thi, việc này dựa vào các thuật toán lập lịch. Thuật toán lập lịch sẽ có một list các task đang ở trạng thái READY, cái này giống như một hàng đợi, các task sẽ được phân bổ vào hàng đợi này dựa vào nhiều yếu tố khác nhau (Độ ưu tiên, đến trước hay đến sau, ...)

    Chẳng hạn, hệ thống có 3 task 1, 2, 3. Khi task 1 vừa kết thúc, hoặc hết thời gian thực hiện, thì Kernel cần gọi bộ lập lịch để biết tiếp theo task nào sẽ thực hiện. 

    Có khá nhiều thuật toán lập lịch, nên mình cũng chỉ giới thiệu một số thuật toán cơ bản và cách nó hoạt động:

1. Round-Robin: Lập lịch theo kiểu "công bằng", tức là mỗi task sẽ có một thời gian thực thi nhất định, gọi là Time Slice, hết khoảng thời gian này thì sẽ phải nhường CPU cho task khác thực hiện. 
   
   
   
   
   Có thể thấy cách làm này khá "dân chủ" 😂 nên freeRTOS (hệ điều hành RTOS hỗ trợ cho STM32) đã quyết định sử dụng nó. Các rất đơn giản mà chúng ta có thể nghĩ đến để thực thi thuật toán này, đó là dùng 1 Timer (cụ thể freeRTOS dùng Systick Timer) để đếm thời gian Time Slide, sau đó sinh ra một ngắt để gọi từng Task thực thi.
   💬 Tuy nhiên, vấn đề xảy ra là nếu như một Task quan trọng (chẳng hạn Task C trong hình), cần thực hiện ngay, mà lúc đó Task A mới bắt đầu chạy, thì Task C phải đợi hết gần 2 Time Slice mới đến lượt mình 😌 Điều này khiển cho các lập trình viên nghĩ ra thêm các thuật toán khác để bổ sung.
2. Preemptive: Người ta mong muốn những Task quan trọng sẽ được thực hiện trước, bằng cách gán cho chúng những quyền ưu tiên. Và task nào có quyền ưu tiên cao hơn, sẽ có thể chiếm quyền sử dụng CPU của task đang thực hiện khi cần. Đó chính là cơ chế của Preemptive.
   
   
   
   
   
   Task bị chiếm quyền (ở đây là Task 1) sẽ đưa vào trạng thái chờ, cho đến khi Task 2 (có độ ưu tiên cao hơn vừa chiếm quyền) thực thi xong. 
3. Cooperative: Cái này thì hơi giống lập trình mà không có RTOS, vì các task sẽ đợi task khác thực hiện xong thì mới đến lượt mình. 
   
   
   
   
   Có thể thấy ở đây mặc dù có độ ưu tiên cao hơn, nhưng Task 2 cũng không thể chiếm quyền điều khiển của Task 1, mà phải đợi Task 1 làm xong thì mới đến lượt.
   💬 Cơ chế này có thể dùng để tránh việc các task có quyền ưu tiên chiếm hết quyền sử dụng CPU, dẫn đến việc những task nhỏ, có quyền ưu tiên thấp, không được thực hiện. Điều này cũng giống nguyên tắc "bình đẳng" trong xã hội.
   💬 Tuy nhiên, khi mà bình đẳng như vậy, thì việc những Task có quyền ưu tiên thấp có nguy cơ "lấn tới", làm quá nhiều thứ, dẫn đến việc chiếm dụng quyền sở hữu CPU, và những Task quan trọng sẽ lại không được thực hiện.
   Vì vậy, cơ chế này phù hợp với hệ thống có những task ít quan trọng và thời gian thực hiện ngắn.

    👉 Nhìn chung, có rất nhiều thuật toán lập lịch, cũng có những tên gọi khác nhau về chúng. Trên đây là 3 cơ chế lập lịch cơ bản nhất, và thực tế thì người ta sẽ thiết kế Scheduler kết hợp những cơ chế đó lại với nhau để điều phối các task trong hệ thống hoạt động trơn tru nhất. Giống như freeRTOS sử dụng chủ đạo là phương pháp Round-Robin, và kết hợp cả 2 phương pháp còn lại. 

    Ở post sau mình sẽ giới thiệu về việc build một hệ điều hành trên nền Vi điều khiển (cụ thể là STM32).

>>>= Follow ngay =<<<

Để theo dõi những bài học miễn phí mới nhất nhé 😊

Chúc các bạn học tập tốt 😊