Hệ điều hành & Lập lịch

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 3)

Hệ điều hành & Lập lịch

Completely Fair Scheduler (CFS - Linux)

Thời gian (Time) O(log N)
Không gian (Space) O(N)

Mô tả nguyên lý

Thuật toán lập lịch CPU mặc định của Linux dựa trên mô hình công bằng phân chia thời gian lý tưởng.

Cài đặt mẫu (Implementation)

// Sử dụng cây đỏ-đen (Red-Black tree) quản lý thời gian thực thi ảo (vruntime) của các tiến trình.
Hệ điều hành & Lập lịch

Linux CFS (Completely Fair Scheduler)

Thời gian (Time) O(log N)
Không gian (Space) O(N)

Mô tả nguyên lý

Thuật toán lập lịch CPU dựa trên mô hình thời gian thực thi ảo (vruntime) trên cây đỏ-đen.

Cài đặt mẫu (Implementation)

// Lựa chọn tiến trình có vruntime nhỏ nhất để cấp phát thời gian chạy CPU kế tiếp.
Hệ điều hành & Lập lịch

Multilevel Feedback Queue Scheduler

Thời gian (Time) O(1)
Không gian (Space) O(Queues)

Mô tả nguyên lý

Thuật toán lập lịch phân tầng nhiều hàng đợi với các mức ưu tiên khác nhau cho tiến trình I/O và CPU.

Cài đặt mẫu (Implementation)

// Tự động hạ bậc ưu tiên tiến trình nếu chiếm dụng CPU quá lâu và thăng bậc nếu chờ I/O.