멀티 레벨 피드백 큐(MLFQ) 스케줄링 — 한눈에 정리

목표: 짧은 작업은 빠르게, 대화형(상호작용) 작업은 즉시 반응하게, 긴 작업도 꾸준히 진행되게 만드는 스케줄러.
핵심 아이디어: “과거의 실행 행동을 관찰해 우선순위를 동적으로 조정”한다.

1) 왜 MLFQ인가?

반환 시간(throughput/turnaround) 최적화: SJF/STCF처럼 짧은 작업을 먼저 처리하고 싶지만, 실제로 작업 길이를 사전에 모를 때가 많다.
응답 시간(response) 단축: RR은 반응성 좋지만, 긴 작업이 많을 때 전체 효율이 떨어질 수 있다.
해법: 작업의 실행 패턴(CPU 오래 씀? I/O 자주 함?)을 관찰하여 우선순위를 동적으로 바꾼다.

규칙	설명
Rule 1	우선순위가 높은 큐의 작업이 먼저 실행된다.
Rule 2	같은 큐 안에서는 `RR(Round-Robin)`으로 순환 실행한다.

큐는 여러 레벨(높음→낮음)로 구성되고, 각 큐는 보통 서로 다른 타임슬라이스를 갖는다.

규칙	의도/효과
Rule 3 (입장)	새로운 작업은 최상위 큐에서 시작한다. → 짧은 작업이면 빠르게 끝난다(SJF 유사 효과).
Rule 4 (강등)	현재 단계에서 부여된 시간 할당량을 누적해 모두 소진하면 한 단계 아래 큐로 내려간다. (I/O로 자주 양보해도 누적합이 기준)

예시

주의
Rule 4를 “양보하면 유지”로만 두면 악용 가능 (슬라이스 끝 직전에 의도적 I/O로 계속 상위 큐에 머무는 트릭). → 누적 사용시간 기준으로 강등해야 공정성 보장.

대화형 프로세스가 너무 많으면, CPU를 오래 사용하는 배치(Batch) 작업은 계속 하위 큐에 머물게 되고, 실행 기회를 거의 얻지 못합니다. 그 결과 배치 작업이 기아 상태에 빠질 수 있습니다.

해결: 일정 시간마다 모든 프로세스를 최상위 큐로 올리는 우선순위 상향(Priority Boost, Rule 5)을 적용합니다. 이렇게 하면 긴 작업도 주기적으로 CPU를 사용할 수 있게 되어 기아 상태가 방지됩니다.

S 값(부스트 주기)은 워크로드에 따라 튜닝이 필요합니다. 너무 길면 여전히 기아, 너무 짧으면 대화형 성능 저하.

프로세스가 일부러 타임 슬라이스가 끝나기 직전에 I/O 요청을 보내 CPU를 양보하면, 계속 상위 큐에 머물게 되어 CPU를 독점할 수 있습니다. 이것을 악용하면 사실상 최고 우선순위에서 계속 실행되며 다른 프로세스가 CPU를 얻지 못하는 상황이 발생합니다.

해결: CPU 사용을 누적 시간으로 측정하여, 타임 슬라이스를 여러 번 나눠 쓰더라도 누적 사용량이 임계치를 넘으면 강등되도록 합니다. 즉, CPU를 짧게 여러 번 쓰든 한 번에 오래 쓰든 총량만 기준으로 공정하게 처리합니다.

프로세스의 성격은 시간이 지남에 따라 변할 수 있습니다. 예를 들어 CPU 중심 작업이 어느 순간 I/O 중심으로 바뀌기도 합니다. 하지만 기존 MLFQ는 과거 기록만 보기 때문에 이런 변화를 적절히 반영하기 어렵습니다.

해결: Rule 5인 우선순위 상향을 통해 주기적으로 모든 프로세스를 최상위 큐로 이동시킵니다. 이렇게 하면 새로운 행동 패턴을 가진 작업을 대화형 프로세스처럼 다시 처리할 수 있습니다.

MLFQ는 강력한 스케줄링 알고리즘이지만, 현실 시스템에서는 기아 방지와 공정성 보장을 위해 규칙 4(누적 사용 시간)와 규칙 5(우선순위 상향) 같은 보완 장치가 필수적으로 사용됩니다.