Hàng đợi phản hồi đa cấp (MLFQ) là một thuật toán lập lịch CPU duy trì nhiều hàng đợi sẵn sàng, mỗi hàng có mức độ ưu tiên và giá trị lượng tử thời gian khác nhau. Các quy trình mới bắt đầu ở hàng đợi có mức độ ưu tiên cao nhất và dựa trên hành vi của chúng, chúng có thể được thăng cấp hoặc hạ cấp giữa các hàng đợi. Cách tiếp cận thích ứng này cân bằng nhu cầu của cả quy trình tương tác và quy trình sử dụng nhiều CPU.
Cấu trúc hàng đợi phản hồi đa cấp Hàng đợi 0 (Ưu tiên cao nhất) Lượng tử thời gian:1 Hàng đợi 1 (Mức độ ưu tiên trung bình) Lượng tử thời gian:2 Hàng đợi 2 (Ưu tiên thấp nhất) CPU FCFS Quy trình mới Giảm hạng nếu hết thời gian Lão hóa:Thăng cấp sau khi chờ đợi Quy tắc di chuyển quy trình ? Các quy trình mới bắt đầu trong Hàng đợi 0? Nếu lượng tử thời gian hết hạn? chuyển sang hàng đợi thấp hơn tiếp theo? Cơ chế lão hóa ngăn ngừa nạn đói
MLFQ hoạt động như thế nào
Thuật toán hoạt động với các nguyên tắc chính sau:
-
Lập lịch dựa trên mức độ ưu tiên Hàng đợi có mức độ ưu tiên cao hơn được phục vụ trước
-
Lượng tử thời gian thay đổi Hàng đợi có mức độ ưu tiên cao hơn có khoảng thời gian ngắn hơn
-
Điều chỉnh mức độ ưu tiên động Các quy trình di chuyển giữa các hàng đợi dựa trên hành vi
-
Cơ chế lão hóa Ngăn chặn nạn đói bằng cách thúc đẩy các quá trình chờ đợi lâu
Ví dụ
Hãy xem xét ba quy trình có đặc điểm sau:
Với Hàng đợi 0 có lượng tử thời gian =1, Hàng đợi 1 có lượng tử thời gian =2 và Hàng đợi 2 sử dụng FCFS:
Tiến trình thực hiện MLFQ P1 P2 P3 P2 P1 P2 P1 (Hàng đợi 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 các tình huống sau:
-
Ứng dụng tương tác Trình duyệt web, trình soạn thảo văn bản và ứng dụng GUI được hưởng lợi từ thời gian phản hồi nhanh chóng cho các tương tác của người dùng
-
Hệ thống chia sẻ thời gian Hệ thống nhiều người dùng trong đó cả quy trình tương tác và quy trình hàng loạt cùng tồn tại
-
Hệ thống thời gian thực Hệ thống yêu cầu mức độ ưu tiên khác nhau cho các nhiệm vụ quan trọng và không quan trọng
-
Ứng dụng trò chơi Trò chơi cần xử lý đầu vào nhạy bén trong khi quản lý các tác vụ nền như âm thanh và kết nối mạng
Ưu điểm
-
Cải thiện thời gian phản hồi Các quy trình ngắn nhanh chóng nhận được sự chú ý trong hàng đợi có mức độ ưu tiên cao
-
Điều chỉnh mức độ ưu tiên động Tự động thích ứng với các mẫu hành vi xử lý
-
Ngăn ngừa tình trạng đói Cơ chế lão hóa đảm bảo các quá trình chờ đợi lâu cuối cùng cũng nhận được thời gian của CPU
-
Thông lượng tốt Cân bằng nhu cầu tương tác và xử lý hàng loạt một cách hiệu quả
-
Cấu hình linh hoạt Lượng thời gian và số lượng hàng đợi có thể được điều chỉnh cho khối lượng công việc cụ thể
Nhược điểm
-
Độ phức tạp triển khai Quản lý nhiều hàng đợi với các chính sách khác nhau làm tăng độ phức tạp của hệ thống
-
Chi phí cao hơn &trừ
