Lập lịch CPU (CPU Scheduling)
1. Tổng quan
A. Định nghĩa
Lập lịch CPU là kỹ thuật quản lý tài nguyên cốt lõi của hệ điều hành, qua đó chọn một tiến trình/luồng sẽ chiếm giữ CPU tiếp theo trong số nhiều tiến trình/luồng ở trạng thái sẵn sàng (ready), rồi bộ điều phối (dispatcher) thực hiện chuyển ngữ cảnh để trao luồng thực thi.
Lý do căn bản khiến hệ điều hành hiện đại cần lập lịch CPU là đa chương trình (multiprogramming). Một CPU đơn chỉ có thể thực thi một lệnh tại một thời điểm, trong khi tiến trình thường xuyên dừng lại để yêu cầu I/O giữa chừng. Nếu CPU cũng rảnh rỗi theo trong lúc một tiến trình chờ đĩa phản hồi thì tài nguyên tính toán đắt đỏ bị lãng phí. Bộ lập lịch nắm bắt đoạn chờ này để trao CPU cho một tiến trình sẵn sàng khác, nhờ đó người dùng thấy như nhiều tác vụ chạy đồng thời và thông lượng tổng thể được nâng cao.
B. Bối cảnh ra đời và sự cần thiết
Trong thời kỳ xử lý theo lô (batch) ban đầu, các công việc được chạy lần lượt đến hết theo thứ tự nộp nên hầu như không có gì gọi là lập lịch. Tuy nhiên, khi hệ thống chia sẻ thời gian (time-sharing) xuất hiện, nhiều người dùng cùng chia sẻ một CPU, và các vấn đề như "công việc ngắn bị kẹt sau công việc dài phải chờ vô tận" hay "tác vụ tương tác không phản hồi tức thì" nổi lên rõ rệt. Lập lịch CPU đã phát triển như lời giải cho câu hỏi làm thế nào phân bổ tài nguyên xử lý hữu hạn một cách công bằng và hiệu quả cho nhiều công việc cạnh tranh. Ngày nay, từ điện thoại thông minh đến máy chủ quy mô lớn và bộ điều khiển thời gian thực, trong môi trường đòi hỏi đồng thời tính đáp ứng, công bằng và hiệu quả năng lượng, chất lượng bộ lập lịch là yếu tố quyết định hiệu năng cảm nhận của hệ thống.
Tiền đề để lập lịch CPU phát huy hiệu quả là sự xen kẽ giữa cụm CPU (CPU burst) và cụm I/O (I/O burst). Việc thực thi chương trình xuất hiện luân phiên giữa "đoạn dùng CPU (tính toán)" và "đoạn chờ I/O"; khi các công việc thiên về tính toán (CPU-bound) và thiên về xuất nhập (I/O-bound) trộn lẫn, nếu bộ lập lịch kết hợp chúng khéo léo thì CPU và thiết bị I/O cùng bận rộn đồng thời, tối đa hóa mức sử dụng tài nguyên. Do đó, lập lịch tốt không chỉ là "chọn ai trước" mà còn là việc đọc tính chất công việc để tối đa hóa song song giữa các thiết bị.
C. Đặc điểm của lập lịch CPU
Lập lịch CPU mang một số đặc điểm bản chất. Thứ nhất là tính thường xuyên. Bộ lập lịch ngắn hạn được gọi mỗi vài mili-giây nên bản thân thuật toán chọn phải nhẹ; nếu chi phí chọn lớn thì chính nó trở thành overhead (vì vậy CFS của Linux cũng dùng cấu trúc dữ liệu O(log n)). Thứ hai là phân bổ tài nguyên không khoan nhượng: CPU chỉ có thể bị chiếm giữ bởi một đối tượng tại một thời điểm, nên việc chọn đồng nghĩa với việc những đối tượng còn lại phải chờ. Thứ ba là tính bất định của dự đoán: không thể biết chính xác độ dài cụm CPU kế tiếp hay thời điểm I/O, nên việc ước lượng/thích nghi dựa trên hành vi quá khứ là không thể tránh khỏi. Thứ tư là tách biệt chính sách và cơ chế: thiết kế tách rời "chọn ai (chính sách)" và "chuyển ngữ cảnh thế nào (cơ chế dispatcher)" để có thể thay đổi nhiều chính sách khác nhau trên cùng một hạ tầng.
2. Chuyển trạng thái tiến trình và các tầng lập lịch
Tiến trình luân chuyển qua nhiều trạng thái từ khi tạo đến khi kết thúc, và lập lịch can thiệp đúng tại những điểm then chốt của sự chuyển trạng thái này. Dưới đây là mô hình 5 trạng thái điển hình.
stateDiagram-v2
[*] --> New
New --> Ready: "chấp nhận (admit)"
Ready --> Running: "điều phối (scheduler)"
Running --> Ready: "trưng dụng (time-out/preempt)"
Running --> Waiting: "chờ I/O·sự kiện"
Waiting --> Ready: "hoàn thành I/O"
Running --> Terminated: "kết thúc (exit)"
Terminated --> [*]
Tại đây, việc chuyển Running→Ready (trưng dụng) có khả thi hay không sẽ phân định tính chất của chính sách lập lịch. Nếu cho phép trưng dụng thì ngay cả tiến trình đang chạy cũng có thể bị tước CPU bởi công việc cấp bách hơn hoặc do hết lát thời gian (time slice); nếu không cho phép thì nó giữ CPU đến khi tự yêu cầu I/O hoặc kết thúc. Ngoài ra, thời điểm ngay sau khi chuyển Waiting→Ready là điểm quyết định quan trọng để trao lại cơ hội cho các công việc thiên về I/O.
Lập lịch được chia thành ba tầng theo thang thời gian. Sơ đồ cấu trúc dưới đây cho thấy vai trò và vị trí của mỗi bộ lập lịch.
flowchart LR
J["hàng đợi công việc (new)"] -->|"bộ lập lịch dài hạn<br/>quyết định mức độ đa chương trình"| R["hàng đợi sẵn sàng (ready)"]
R -->|"bộ lập lịch ngắn hạn<br/>chọn theo đơn vị mili-giây"| D["bộ điều phối"]
D --> C["CPU thực thi (running)"]
C -->|"yêu cầu I/O"| W["hàng đợi chờ (waiting)"]
W -->|"hoàn thành"| R
C -.->|"hoán đổi ra"| M["bộ lập lịch trung hạn<br/>điều tiết quá tải bộ nhớ"]
M -.->|"hoán đổi vào"| R
Bộ điều phối thực hiện tuần tự những việc sau ngay khi chọn xong, và thời gian cho toàn bộ quá trình này là độ trễ điều phối.
- Lưu·khôi phục ngữ cảnh: lưu thanh ghi·PC của tiến trình rời đi vào PCB, và nạp trạng thái của tiến trình đi vào.
- Chuyển chế độ: chuyển từ chế độ nhân (kernel) sang chế độ người dùng.
- Chuyển không gian địa chỉ: thay bảng trang·TLB theo tiến trình mới (bảo vệ địa chỉ ảo).
- Nhảy: rẽ nhánh tới vị trí program counter đã khôi phục để tiếp tục mã người dùng.
Bộ lập lịch dài hạn (long-term) quyết định nạp công việc nào vào bộ nhớ để kích hoạt, qua đó điều tiết mức độ đa chương trình; còn bộ lập lịch trung hạn (medium-term) hoán đổi một số tiến trình ra đĩa khi bộ nhớ bị ép rồi đưa trở lại, làm phẳng tải. Cái mà ta thường gọi là "lập lịch CPU" chính là bộ lập lịch ngắn hạn (short-term) hoạt động thường xuyên nhất theo đơn vị mili-giây, và vai trò thực sự chuyển ngữ cảnh sang tiến trình đã chọn do bộ điều phối (dispatcher) đảm nhiệm. Thời gian bộ điều phối tiêu tốn gọi là độ trễ điều phối (dispatch latency); nếu overhead này lớn thì lập lịch càng thường xuyên càng thiệt, nên nó liên quan trực tiếp đến việc thiết kế lát thời gian.
3. Tiêu chí hiệu năng lập lịch và vấn đề trưng dụng
Điểm cốt lõi là các thước đo đánh giá bộ lập lịch đánh đổi (trade-off) lẫn nhau. Các chỉ số tiêu biểu như sau.
- Mức sử dụng CPU (utilization): tỷ lệ CPU làm việc không nghỉ. Càng cao càng tốt.
- Thông lượng (throughput): số công việc hoàn thành trên một đơn vị thời gian. Máy chủ xử lý theo lô coi trọng.
- Thời gian hoàn thành (turnaround time): tổng thời gian từ khi nộp công việc đến khi hoàn thành.
- Thời gian chờ (waiting time): tổng thời gian chờ trong hàng đợi sẵn sàng. Là lượng mà bộ lập lịch có thể trực tiếp giảm được.
- Thời gian đáp ứng (response time): thời gian từ khi yêu cầu đến khi có phản hồi đầu tiên. Là cốt lõi của hệ thống tương tác·thời gian thực.
Nếu dùng lát thời gian dài để nâng thông lượng thì overhead chuyển ngữ cảnh giảm nhưng tính đáp ứng kém đi; ngược lại, nếu chia nhỏ thì phản hồi tương tác nhanh hơn nhưng chi phí chuyển tăng khiến mức sử dụng giảm. Vì vậy việc đặt chỉ số nào làm ưu tiên hàng đầu chính là việc chọn chính sách; OS đa dụng nhắm cân bằng nhiều chỉ số, còn hệ thống thời gian thực tuyệt đối ưu tiên tuân thủ hạn chót. Ánh xạ ưu tiên theo từng chỉ số với loại hệ thống như sau.
| Loại hệ thống | Chỉ số ưu tiên nhất | Chính sách tiêu biểu |
|---|---|---|
| Máy chủ xử lý theo lô | Thông lượng·mức sử dụng | Xấp xỉ SJF |
| Chia sẻ thời gian·tương tác | Thời gian đáp ứng | RR·MLFQ |
| Điều khiển thời gian thực | Tuân thủ hạn chót | EDF·RMS |
| Thiết bị di động | Tính đáp ứng·hiệu quả năng lượng | Bộ lập lịch kết hợp EAS |
| Phân loại | Không trưng dụng (Non-preemptive) | Trưng dụng (Preemptive) |
|---|---|---|
| Trả CPU | Tự nguyện (khi I/O·kết thúc) | Có thể cưỡng chế thu hồi |
| Tính đáp ứng | Thấp (công việc dài độc chiếm) | Cao |
| Overhead chuyển ngữ cảnh | Ít | Nhiều |
| Nhất quán tài nguyên dùng chung | Đơn giản | Cần điều kiện tranh chấp·đồng bộ |
| Áp dụng | Xử lý theo lô đơn giản | Chia sẻ thời gian·thời gian thực |
Loại trưng dụng đạt được tính đáp ứng nhưng phải trả giá bằng tính nhất quán của dữ liệu dùng chung. Nếu bị trưng dụng giữa lúc đang cập nhật cấu trúc dữ liệu nhân, tiến trình khác có thể đọc trạng thái dở dang, nên cần đồng thời bảo vệ vùng tới hạn (semaphore·spinlock) và thiết kế điểm trưng dụng trong nhân.
Mặt khác, mọi trưng dụng·chuyển đều ẩn chứa chi phí chuyển ngữ cảnh (context switch). Khi chuyển, OS lưu thông tin thanh ghi·program counter·bản đồ bộ nhớ của tiến trình rời đi vào PCB (Process Control Block) và khôi phục trạng thái của tiến trình đi vào; trong thời gian làm việc này CPU hoàn toàn không làm được việc hữu ích nào. Chi phí ẩn lớn hơn là ô nhiễm cache·TLB: tiến trình mới không thể dùng cache đã được "hâm nóng" nên ban đầu số lần trượt cache bùng nổ. Vì vậy, thiết kế nâng tần suất lập lịch để đạt công bằng chỉ chính đáng khi cân bằng với chi phí gián tiếp này, và đây là căn cứ thực tiễn để đặt lượng tử thời gian ở mức "gấp hàng chục lần trở lên thời gian chuyển ngữ cảnh".
4. Các thuật toán lập lịch chính
A. FCFS (First-Come, First-Served)
Là chính sách không trưng dụng đơn giản nhất, lấy ra khỏi hàng đợi theo thứ tự đến và chạy đến hết. Ưu điểm là dễ hiện thực và không có đói tài nguyên (starvation), nhưng hiệu ứng đoàn hộ tống (convoy effect) — khi một công việc dài chặn phía trước làm toàn bộ các công việc ngắn phía sau bị dồn lại — là chí mạng. Chẳng hạn P1·P2·P3 có cụm 24·3·3ms đến theo thứ tự này thì thời gian chờ trung bình là (0+24+27)/3 = 17ms, nhưng nếu theo thứ tự P2·P3·P1 thì là (0+3+6)/3 = 3ms, giảm mạnh. Cùng một tập công việc mà chỉ nhờ thứ tự, hiệu năng chênh nhau hơn 5 lần; ví dụ này cho thấy ấn tượng rằng "thứ tự đến trước" không liên quan đến hiệu quả.
B. SJF / SRTF (Shortest Job First / Shortest Remaining Time First)
Là chính sách xử lý trước công việc có cụm CPU còn lại ngắn nhất, và là thuật toán tối ưu đã được chứng minh về mặt toán học rằng tối thiểu hóa thời gian chờ trung bình. Phiên bản không trưng dụng là SJF, phiên bản trưng dụng là SRTF. Tuy nhiên trên thực tế có hạn chế căn bản là không thể biết trước độ dài cụm kế tiếp, nên ta dự đoán xấp xỉ bằng làm trơn hàm mũ (exponential averaging, τ(n+1)=α·t(n)+(1-α)·τ(n)) dựa trên các cụm quá khứ. Một điểm yếu khác là đói tài nguyên: nếu công việc ngắn liên tục đi vào thì công việc dài có thể mãi mãi không được chọn. Cơ chế giảm nhẹ điều này là lão hóa (aging) sẽ bàn ở sau. Trong thực tế, bộ lập lịch hàng đợi build·công việc lô vay mượn tư tưởng SJF bằng ưu tiên dựa trên thời gian thực thi dự kiến.
C. Lập lịch theo ưu tiên (Priority Scheduling)
Gán ưu tiên cho mỗi công việc và chạy công việc có ưu tiên cao hơn trước (SJF cũng là trường hợp đặc biệt với "cụm càng ngắn thì ưu tiên càng cao"). Có thể cả trưng dụng lẫn không trưng dụng, và linh hoạt vì có thể đối xử phân biệt giữa daemon hệ thống·công việc người dùng·công việc nền. Cạm bẫy cốt lõi vẫn là chặn vô thời hạn (đói tài nguyên), và để ngăn điều này người ta kết hợp lão hóa nhằm dần nâng ưu tiên của công việc chờ lâu. Ngoài ra có thể xảy ra đảo ngược ưu tiên (priority inversion) khi công việc ưu tiên thấp giữ tài nguyên dùng chung và chặn công việc ưu tiên cao, nên ta đối phó bằng giao thức kế thừa ưu tiên (priority inheritance) (sự cố reset của tàu thăm dò Sao Hỏa Mars Pathfinder là ví dụ tiêu biểu).
D. Round Robin (RR) và MLFQ
RR là chuẩn mực của chia sẻ thời gian, là FCFS trưng dụng trao cho mỗi công việc một lượng tử thời gian (time quantum) như nhau và khi dùng hết thì đẩy về cuối hàng đợi. Nhờ ưu điểm công bằng và thời gian đáp ứng có thể dự đoán, nó phù hợp với hệ thống tương tác. Hiệu năng nhạy với kích thước lượng tử: quá lớn thì thoái hóa thành FCFS, quá nhỏ thì overhead chuyển ngữ cảnh bùng nổ. Thông thường đặt gấp hàng chục lần chi phí chuyển (vài ms~vài chục ms) để điều chỉnh sao cho "80% cụm kết thúc trong một lượng tử". Ví dụ cụm 24·3·3ms, lượng tử 4ms thì P1 bị trưng dụng sau 4ms để P2·P3 chen vào nhanh, nên thời gian đáp ứng trung bình cải thiện lớn so với FCFS.
Nguyên tắc thực tiễn thiết lập lượng tử thời gian được tóm tắt như sau.
- Đủ lớn so với chi phí chuyển: đặt gấp hàng chục lần trở lên thời gian chuyển ngữ cảnh để kìm tỷ lệ overhead xuống dưới mức 1%.
- Khớp với phân bố cụm: đặt sao cho đa số (khoảng 80%) cụm CPU kết thúc trong một lượng tử nhằm giảm trưng dụng không cần thiết.
- Phân biệt theo khối lượng công việc: tương tác thì nhỏ (phản hồi nhanh), thiên tính toán thì lớn (giảm chuyển) — MLFQ tự động hóa điều này.
Hàng đợi phản hồi đa cấp (MLFQ, Multi-Level Feedback Queue) là chính sách thích nghi xếp chồng nhiều hàng đợi RR theo ưu tiên và di chuyển công việc giữa các hàng đợi bằng cách quan sát hành vi của nó. Công việc CPU-bound dùng hết lượng tử bị hạ xuống hàng đợi dưới (lượng tử dài), còn công việc I/O-bound·tương tác trả CPU sớm được giữ ở hàng đợi trên (lượng tử ngắn, ưu tiên cao), nhằm đồng thời đạt tính đáp ứng và thông lượng. Điểm mạnh là dù không biết trước tính chất công việc, nó vẫn tự phân loại như thể tự học, và ngăn đói tài nguyên bằng tái điều chỉnh ưu tiên định kỳ (boosting).
| Thuật toán | Trưng dụng | Chờ trung bình | Đói tài nguyên | Đặc điểm |
|---|---|---|---|---|
| FCFS | X | Kém | Không | Đơn giản, hiệu ứng đoàn hộ tống |
| SJF/SRTF | Tùy chọn | Tối ưu | Có | Cần dự đoán |
| Priority | Tùy chọn | Thay đổi | Có | Cần lão hóa |
| RR | O | Trung bình | Không | Nhạy lượng tử, công bằng |
| MLFQ | O | Xuất sắc | Không (boosting) | Thích nghi, chuẩn OS đa dụng |
E. Ví dụ so sánh tổng hợp — cùng công việc, kết quả khác
Để cảm nhận bằng con số sự khác biệt giữa các chính sách, ta so sánh kết quả chạy ba tiến trình P1(24ms)·P2(3ms)·P3(3ms) cùng đến (thời điểm 0) lần lượt bằng FCFS·SJF·RR (lượng tử 4ms). Bảng dưới tổng hợp thời điểm hoàn thành và thời gian chờ (= thời điểm hoàn thành − cụm) của mỗi chính sách. Cần chú ý rằng dù cùng đầu vào, thời gian chờ trung bình chênh nhau hơn 3 lần tùy chính sách.
| Chính sách | P1 hoàn thành/chờ | P2 hoàn thành/chờ | P3 hoàn thành/chờ | Thời gian chờ trung bình |
|---|---|---|---|---|
| FCFS(P1→P2→P3) | 24 / 0 | 27 / 24 | 30 / 27 | 17ms |
| SJF(P2→P3→P1) | 30 / 6 | 3 / 0 | 6 / 3 | 3ms |
| RR(lượng tử 4) | 30 / 6 | 10 / 7 | 13 / 10 | 7.7ms |
FCFS có P1 dài chặn phía trước nên chờ trung bình tệ nhất do hiệu ứng đoàn hộ tống. SJF đưa công việc ngắn lên trước nên tối thiểu hóa chờ trung bình (tối ưu), nhưng nếu công việc ngắn liên tục đổ vào thì P1 mang rủi ro rơi vào đói tài nguyên. RR tuy chờ trung bình không bằng SJF nhưng thời gian đáp ứng đến khi P2·P3 nhận phản hồi đầu tiên ngắn (lần lượt trong 4ms, 8ms), nên trong môi trường tương tác hiệu năng cảm nhận là tốt nhất. Tức "thời gian chờ trung bình nhỏ" và "phản hồi nhanh" là những mục tiêu khác nhau, và ví dụ này cho thấy rõ việc chọn bộ lập lịch chính là quyết định hy sinh chỉ số nào để đạt được gì.
5. Chuyên sâu — bộ lập lịch thực tiễn và xu hướng đa lõi
OS đa dụng thực tế không dùng nguyên các thuật toán cổ điển trên mà vận hành bộ lập lịch tinh vi kết hợp công bằng·khả mở rộng·năng lượng. Linux đã giới thiệu CFS (Completely Fair Scheduler) từ năm 2007; thay vì lát thời gian, nó tích lũy thời gian CPU mà mỗi công việc nhận được thành thời gian thực thi ảo (vruntime) và chọn công việc có vruntime nhỏ nhất trong cây đỏ-đen với O(log n), qua đó xấp xỉ "phần CPU đều nhau cho mọi công việc". Từ Linux 6.6 năm 2024, nó được thay bằng EEVDF (Earliest Eligible Virtual Deadline First) xử lý tốt hơn các công việc nhạy độ trễ, cải thiện cân bằng giữa tính đáp ứng và công bằng bằng khái niệm hạn chót ảo. Windows kết hợp bộ lập lịch trưng dụng dựa trên ưu tiên 32 cấp với nâng ưu tiên (priority boosting) (tạm nâng khi cửa sổ tiền cảnh·hoàn thành I/O).
Hiệu quả của bước tiến này thể hiện bằng con số cụ thể. Khi Linux chuyển từ bộ lập lịch O(1) sang CFS, dù hàng nghìn công việc chạy đồng thời chi phí chọn vẫn bị kìm ở quy mô logarit nên độ trễ đuôi (tail latency) của máy chủ web quy mô lớn được cải thiện, và sau khi đưa EEVDF vào có các báo cáo rằng sụt khung hình của những công việc nhạy độ trễ như âm thanh·trò chơi giảm đi. Ngược lại, nếu xử lý bộ lập lịch sai thì hiệu năng sụp đổ. Ví dụ thực tiễn tiêu biểu là vấn đề điều tiết băng thông CFS của Kubernetes (CPU throttling): nếu đặt CPU limit thấp cho container thì CFS cưỡng chế dừng container đó khi cạn hạn mức mỗi chu kỳ 100ms, khiến p99 thời gian đáp ứng vọt lên hàng trăm ms dù CPU còn dư. Nhiều tổ chức vì hiện tượng này đã đặt hướng dẫn vận hành là gỡ bỏ hoặc nâng CPU limit ở các dịch vụ nhạy độ trễ, đây là minh chứng cho thấy không hiểu nguyên lý lập lịch của OS thì cũng không thể tinh chỉnh hiệu năng đám mây.
Đa lõi dị chủng của di động·máy chủ bổ sung một chiều kích mới. ARM big.LITTLE / DynamIQ trộn lẫn lõi hiệu năng cao và lõi tiết kiệm điện, bộ lập lịch chọn lõi theo tải công việc và ngân sách điện (EAS, Energy-Aware Scheduling) để kéo dài tuổi thọ pin. Ngoài ra, vì trong môi trường đa lõi đặt hàng đợi sẵn sàng trên mỗi lõi sẽ sinh ra mất cân bằng tải, nên phải quản lý đánh đổi giữa cân bằng tải (load balancing) định kỳ và ái lực cache (processor affinity) vốn gắn công việc vào lõi đã được hâm cache. Trong ảo hóa·đám mây, do hypervisor lập lịch lại vCPU lên CPU vật lý, nên cả vấn đề lập lịch kép (double scheduling) và trưng dụng người giữ khóa (lock-holder preemption) cũng trở thành đối tượng cân nhắc. Trong lĩnh vực thời gian thực, để bảo đảm hạn chót của các công việc định kỳ, các chính sách dựa trên hạn chót như RMS (Rate Monotonic)·EDF (Earliest Deadline First) được dùng riêng.
6. Cân nhắc và hàm ý (góc nhìn Kỹ sư chuyên nghiệp)
- Chiến lược áp dụng — chọn chính sách phù hợp mục đích: thiết bị tương tác phải ưu tiên hàng đầu thời gian đáp ứng (RR·MLFQ), máy chủ lô ưu tiên thông lượng (xấp xỉ SJF), bộ điều khiển thời gian thực ưu tiên tuân thủ hạn chót (EDF·RMS). Không có "bộ lập lịch tốt nhất" duy nhất, phải phân tích đặc tính khối lượng công việc trước.
- Quản lý đánh đổi: lượng tử thời gian là điểm cân bằng giữa tính đáp ứng (ngắn) và overhead chuyển ngữ cảnh (dài), trưng dụng cho tính đáp ứng nhưng gây chi phí đồng bộ và ô nhiễm cache. Đòi hỏi năng lực đo lường định lượng sự đánh đổi giữa các chỉ số (utilization·độ trễ p99) và tinh chỉnh.
- Thể chế hóa việc ngăn đói tài nguyên·đảo ngược ưu tiên: chính sách dựa trên ưu tiên nhất thiết phải thiết kế kèm lão hóa và kế thừa ưu tiên để chặn một cách có cấu trúc việc chặn vô thời hạn và đảo ngược ưu tiên (trong hệ thống thực thi nhiệm vụ, điều này liên quan trực tiếp đến sự cố an toàn).
- Liên kết năng lượng·bền vững: lập lịch nhận biết năng lượng kết hợp với lõi dị chủng·DVFS ảnh hưởng trực tiếp đến pin di động và chi phí điện trung tâm dữ liệu (Green IT). Trong tương lai, bộ lập lịch sẽ tiến hóa theo hướng tối ưu đồng thời không chỉ hiệu năng mà cả hiệu năng trên mỗi watt và hiệu quả carbon.
- Mở rộng sang công nghệ liên quan: nguyên lý tương tự được áp dụng mở rộng tới container (hạn mức CPU của cgroups·điều khiển băng thông CFS)·yêu cầu/giới hạn của Kubernetes, lập lịch vCPU của ảo hóa, cho đến lập lịch công việc GPU·NPU, nên hiểu biết về lập lịch OS trở thành nền tảng của quản lý tài nguyên đám mây.
- Nhu cầu về hệ thống quan trắc·kiểm chứng: chất lượng lập lịch bộc lộ không phải qua giá trị trung bình mà qua độ trễ đuôi (p99·p99.9) và độ trễ lập lịch (scheduling latency), nên phải trang bị đồng thời hệ thống quan trắc đo đạc phân bố độ trễ thực tế bằng
perf sched·truy vết dựa trên eBPF và quản lý gắn với SLO thì việc tinh chỉnh chính sách mới có căn cứ.
Tài liệu tham khảo
- Operating System Concepts (Silberschatz et al.), chương CPU Scheduling
- Linux Kernel Documentation, "CFS Scheduler" / "Scheduler" — https://docs.kernel.org/scheduler/
- Arpaci-Dusseau, "Operating Systems: Three Easy Pieces" — Scheduling(MLFQ) — https://pages.cs.wisc.edu/~remzi/OSTEP/
Tóm tắt một câu: Lập lịch CPU là kỹ thuật chọn đối tượng thực thi tiếp theo trong số các công việc của hàng đợi sẵn sàng để khai thác hiệu quả của đa chương trình, trong đó FCFS·SJF·ưu tiên·RR·MLFQ cân đo tính đáp ứng·thông lượng·công bằng mỗi thứ một khác, và trong thực tế đang phát triển thành CFS/EEVDF của Linux cùng lập lịch nhận biết năng lượng·đa lõi.