Multilevel Feedback Queue (MLFQ) là thuật toán lập lịch CPU duy trì nhiều hàng đợi sẵn sàng, mỗi hàng với mức ưu tiên và time quantum khác nhau. Tiến trình mới bắt đầu ở hàng ưu tiên cao nhất, và dựa trên hành vi, chúng có thể được thăng/hạ cấp giữa các hàng. Cách thích nghi này cân bằng nhu cầu tiến trình tương tác và CPU-intensive.
Multilevel Feedback Queue Structure
Queue 0 (Ưu tiên cao nhất) Time Quantum: 1
Queue 1 (Ưu tiên trung bình) Time Quantum: 2
Queue 2 (Ưu tiên thấp nhất) FCFS
CPU
Tiến trình mới
Hạ cấp nếu hết quantum
Aging: Thăng cấp sau chờ
Quy Tắc Di Chuyển Tiến Trình
• Tiến trình mới bắt đầu Queue 0
• Nếu hết time quantum → chuyển hàng thấp hơn
• Cơ chế aging ngăn chặn đói
Cách MLFQ Hoạt Động
Thuật toán vận hành với nguyên tắc then chốt:
- Lập lịch dựa trên ưu tiên: Hàng ưu tiên cao được phục vụ trước
- Time quantum biến đổi: Hàng ưu tiên cao có time slice ngắn hơn
- Điều chỉnh ưu tiên động: Tiến trình di chuyển giữa hàng dựa trên hành vi
- Cơ chế aging: Ngăn chặn đói bằng cách thăng cấp tiến trình chờ lâu
Ví Dụ
Xét ba tiến trình với đặc điểm sau:
| Tiến trình | Thời gian đến | Burst Time | Hàng ban đầu |
|---|---|---|---|
| P1 | 0 | 8 | Queue 0 |
| P2 | 1 | 4 | Queue 0 |
| P3 | 2 | 2 | Queue 0 |
Với Queue 0 quantum = 1, Queue 1 quantum = 2, Queue 2 dùng FCFS:
MLFQ Execution Timeline
P1 P2 P3 P2 P1 P2 P1 (Queue 2 - FCFS)
0 1 2 3 4 6 8 14
Q0 Q0 Q0 Q1 Q1 Q1 Q2
Trường Hợp Sử Dụng
MLFQ đặc biệt hiệu quả trong kịch bản sau:
- Ứng dụng tương tác: Web browser, text editor, GUI app hưởng thời gian phản hồi nhanh cho tương tác user
- Hệ thống chia sẻ thời gian: Hệ thống multi-user nơi tiến trình tương tác và batch cùng tồn tại
- Hệ thống real-time: Hệ thống yêu cầu mức ưu tiên khác nhau cho task critical và non-critical
- Ứng dụng game: Game cần xử lý input phản hồi nhanh trong khi quản lý task nền như audio và network
Ưu Điểm
- Cải thiện thời gian phản hồi: Tiến trình ngắn được chú ý nhanh ở hàng ưu tiên cao
- Điều chỉnh ưu tiên động: Tự thích nghi với pattern hành vi tiến trình
- Ngăn chặn đói: Cơ chế aging đảm bảo tiến trình chờ lâu cuối cùng có CPU time
- Throughput tốt: Cân bằng hiệu quả nhu cầu xử lý tương tác và batch
- Cấu hình linh hoạt: Time quantum và số hàng có thể tune cho workload cụ thể
Nhược Điểm
- Độ phức tạp triển khai: Quản lý nhiều hàng với chính sách khác nhau tăng độ phức tạp hệ thống
- Overhead cao hơn
