CFS và EEVDF – Hai thế hệ bộ lập lịch CPU của Linux

Bộ lập lịch (scheduler) quyết định tiến trình nào được chạy trên CPU, chạy trong bao lâu và khi nào bị nhường chỗ. Trong hơn 15 năm, Linux dùng CFS (Completely Fair Scheduler) làm bộ lập lịch mặc định cho các tiến trình thông thường. Từ Linux 6.6, CFS được thay bằng EEVDF (Earliest Eligible Virtual Deadline First). Bài này ghi lại ngắn gọn ý tưởng của cả hai và lý do có sự thay đổi này.

CFS: chia đều thời gian CPU

CFS xuất hiện từ Linux 2.6.23 (2007), do Ingo Molnar viết, thay thế bộ lập lịch O(1) trước đó. Ý tưởng cốt lõi: mô phỏng một CPU lý tưởng mà mọi tiến trình chạy song song với tốc độ bằng nhau (tỉ lệ theo trọng số).

Để làm được điều này, CFS theo dõi vruntime (virtual runtime) của mỗi tiến trình:

• Tiến trình chạy càng lâu thì vruntime càng tăng.
• Trọng số (weight) lấy từ giá trị nice. Tiến trình có weight cao thì vruntime tăng chậm hơn, nên được chạy nhiều hơn.
• Các tiến trình sẵn sàng chạy được lưu trong một cây đỏ đen (red-black tree) sắp theo vruntime.
• Khi cần chọn tiến trình tiếp theo, scheduler lấy nút ngoài cùng bên trái, tức là tiến trình có vruntime nhỏ nhất, vì nó đang bị thiệt nhất.

Công thức cập nhật đơn giản:

vruntime += thoi_gian_da_chay * NICE_0_WEIGHT / weight

Thời gian mỗi tiến trình được chạy phụ thuộc vào hai tham số: sched_latency (khoảng thời gian mục tiêu để mọi tiến trình đều được chạy ít nhất một lần) và min_granularity (lát cắt tối thiểu, tránh chuyển ngữ cảnh quá dày).

Hạn chế của CFS

CFS công bằng về tổng lượng CPU, nhưng không có khái niệm rõ ràng về độ trễ (latency). Một tiến trình cần phản hồi nhanh, như tác vụ giao diện hoặc audio, không có cách chính thống nào để nói điều đó với scheduler. Nice chỉ đổi phần chia CPU chứ không đổi độ trễ.

Vì vậy, qua nhiều năm CFS tích tụ khá nhiều heuristic để bù: ưu tiên tiến trình vừa thức dậy (wakeup preemption), điều chỉnh vruntime cho tiến trình ngủ lâu, các cơ chế "sleeper fairness"... Những heuristic này khó lập luận về tính đúng đắn và thường phải chỉnh tay cho từng workload.

EEVDF: công bằng có thêm hạn chót

EEVDF bắt nguồn từ một bài báo năm 1995 của Ion Stoica và Hussein Abdel-Wahab. Peter Zijlstra đưa nó vào nhân Linux, và nó được merge trong bản 6.6. EEVDF vẫn giữ mục tiêu chia CPU công bằng theo trọng số, nhưng dựa trên hai khái niệm chặt chẽ hơn.

Lag. Lag của một tiến trình là hiệu số giữa thời gian CPU nó đáng lẽ được nhận (theo mô hình lý tưởng) và thời gian nó thực sự nhận. Lag dương nghĩa là tiến trình đang bị thiệt, lag âm nghĩa là nó đã nhận dư.

Eligible. Một tiến trình chỉ được xem xét chạy khi lag của nó không âm, tức là nó không đang chạy quá phần của mình.

Virtual deadline. Mỗi tiến trình có một hạn chót ảo, tính từ thời điểm nó bắt đầu đủ điều kiện cộng với lát cắt (slice) mà nó yêu cầu, chia cho weight:

virtual_deadline = virtual_eligible_time + slice / weight

Quy tắc chọn rất gọn: trong các tiến trình eligible, chọn tiến trình có virtual deadline sớm nhất. Đó cũng chính là tên của thuật toán.

Slice điều khiển độ trễ

Đây là điểm khác biệt quan trọng nhất. Slice càng ngắn thì deadline càng sớm, nên tiến trình được chạy sớm hơn, nhưng mỗi lần chạy được ít hơn. Tổng lượng CPU vẫn do weight quyết định.

Ví dụ hai tiến trình A và B cùng weight, cùng eligible tại một thời điểm:

• A yêu cầu slice 3ms, deadline là T + 3ms.
• B yêu cầu slice 10ms, deadline là T + 10ms.

A sẽ được chọn trước, dù cả hai về lâu dài nhận lượng CPU như nhau. Nhờ vậy, tiến trình nhạy độ trễ có thể xin slice ngắn để phản hồi nhanh mà không cần "ăn gian" phần CPU của tiến trình khác. Từ Linux 6.12, ứng dụng có thể đặt slice riêng qua sched_setattr() (trường sched_runtime).

Ngoài ra, các bản kernel mới còn có cơ chế delayed dequeue: tiến trình đi ngủ mà còn lag âm vẫn được giữ lại trong hàng đợi cho đến khi lag về không, để việc ngủ/thức không bị lợi dụng nhằm lấy lại phần CPU đã dùng dư.

So sánh nhanh

Kết luận

CFS trả lời câu hỏi "ai đang bị thiệt nhất?", còn EEVDF trả lời thêm "trong những ai bị thiệt, ai cần được chạy sớm nhất?". Việc tách bạch giữa phần CPU được chia (weight) và độ trễ mong muốn (slice) giúp scheduler dễ suy luận hơn và bớt phụ thuộc vào các heuristic rời rạc. Với người dùng thông thường, sự khác biệt thể hiện ở chỗ hệ thống phản hồi ổn định hơn khi tải cao, còn với người viết ứng dụng thì đã có thêm một công cụ để nói cho kernel biết tác vụ của mình cần gì.

Tham khảo

• Tài liệu kernel: "CFS Scheduler" và "EEVDF Scheduler" tại docs.kernel.org
• Stoica, Abdel-Wahab, "Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation" (1995)