다단계 피드백 큐
더 많은 작업
다단계 피드백 큐(Multi-Level Feedback Queue, MLFQ, MFQ)는 우선순위가 다른 준비 큐를 여러 개 두고, 프로세스가 실제로 CPU 를 어떻게 쓰는지에 따라 큐 사이를 오르내리게 해 짧은 작업과 대화형 작업을 우대하는 CPU 스케줄링 기법이다.
SJF 스케줄링처럼 짧은 작업을 먼저 하면 평균 반환 시간이 줄지만, 운영체제는 작업이 얼마나 걸릴지 미리 알지 못한다. 다단계 피드백 큐는 과거 실행 행태를 보고 우선순위를 고쳐 가며 이 문제를 푼다. 처음에는 모든 작업을 짧은 작업으로 가정해 가장 높은 큐에 넣고, 주어진 시간을 다 쓰면 긴 작업으로 보고 아래 큐로 내린다. 입출력을 하느라 CPU 를 일찍 내놓는 대화형 작업은 높은 큐에 머문다.[1]
프로세스 유형별로 큐를 고정해 두는 다단계 큐(MLQ)와 달리, 프로세스가 큐 사이를 이동할 수 있다는 것이 이름의 '피드백'이다. 오래 기다린 프로세스를 위 큐로 올리는 에이징(aging)도 이 이동으로 구현한다.[2]
OSTEP 은 MLFQ 를 다음 규칙으로 정리한다.[1]
- 우선순위가 높은 큐의 프로세스가 먼저 실행된다. 높은 큐가 비어 있지 않으면 CPU 는 항상 그 큐의 프로세스에 할당된다.
- 같은 큐 안에서는 라운드 로빈으로 돌아가며 실행한다.
- 새 프로세스는 가장 높은 큐에 들어간다.
- 한 큐에서 받은 시간 할당량을 다 쓰면(중간에 CPU 를 내놓은 시간까지 합쳐) 한 단계 아래 큐로 내려간다.
- 일정 시간마다 모든 프로세스를 가장 높은 큐로 올린다(우선순위 상향). 아래 큐에서 굶는 기아 현상을 막고, 행태가 바뀐 작업이 다시 기회를 얻는다.
상위 큐에 프로세스가 도착하면 하위 큐에서 실행 중이던 프로세스는 선점된다.
큐 세 개로 구성한 예이다.[2]
| 큐 | 알고리즘 | 시간 할당량 |
|---|---|---|
| Q0(가장 높음) | 라운드 로빈 | 8ms |
| Q1 | 라운드 로빈 | 16ms |
| Q2(가장 낮음) | FCFS | 끝날 때까지 |
새 작업은 Q0 에 들어가 8ms 를 받는다. 그 안에 끝나지 않으면 Q1 로 내려가 16ms 를 더 받고, 그래도 남으면 Q2 로 내려간다. Q1 은 Q0 가 비어 있을 때만, Q2 는 Q0·Q1 이 모두 비어 있을 때만 실행된다. 그래서 8ms 안에 끝나는 짧은 작업이 가장 빨리 처리된다.
| 구분 | 다단계 큐(MLQ) | 다단계 피드백 큐(MLFQ) |
|---|---|---|
| 큐 배정 | 프로세스 유형(시스템, 대화형, 일괄)에 따라 고정 | 처음엔 최상위 큐, 이후 실행 행태로 바뀜 |
| 큐 사이 이동 | 없다 | 있다(강등, 에이징에 의한 승격) |
| 큐별 알고리즘·할당량 | 다르게 둘 수 있다 | 다르게 둘 수 있다 |
| 큐 사이 스케줄링 | 고정 우선순위 또는 시간 분할 | 고정 우선순위(상위 큐 우선) |
| 기아 | 하위 큐가 굶을 수 있다 | 주기적 승격으로 막는다 |
"프로세스는 처음 배정된 큐에 계속 머문다"는 것은 다단계 큐의 성질이며, 다단계 피드백 큐에는 맞지 않는다. 여러 CPU 에 준비 큐를 어떻게 둘지 정하는 방식은 멀티프로세서 스케줄링에서 다룬다.
- ↑ 1.0 1.1 Remzi H. Arpaci-Dusseau·Andrea C. Arpaci-Dusseau, 「Scheduling: The Multi-Level Feedback Queue」, Operating Systems: Three Easy Pieces, 위스콘신 대학교, https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf, 확인일: 2026-11-04.
- ↑ 2.0 2.1 2.2 「Chapter 6: CPU Scheduling」 Multilevel Feedback Queue, Operating System Concepts 9th Edition 강의자료, Silberschatz·Galvin·Gagne, https://www.os-book.com/OS9/slide-dir/PDF-dir/ch6.pdf, 확인일: 2026-11-04.