[CS기초] Multi-Level Feedback Queue Scheduler (MLFQS)

Multi-Level Feedback Queue Scheduler (MLFQS)

운영체제는 CPU 자원을 효율적으로 분배하기 위해 다양한 스케줄링 알고리즘을 사용하는데요. 그중에서도 MLFQ (Multi-Level Feedback Queue)는 사용자 프로그램의 특성을 파악해 동적으로 우선순위를 조정하는 고급 스케줄링 기법입니다.

 

 

MLFQ의 핵심 아이디어

MLFQ는 이름 그대로 여러 개의 우선순위 큐(priority queue)를 사용하여 프로세스를 스케줄링합니다.

• 여러 개의 큐
  • 각 큐는 서로 다른 우선순위를 가짐
  • 위쪽 큐일수록 높은 우선순위
• Time Quantum
  • 높은 우선순위 큐일수록 time slice(할당 시간)가 작음
• Feedback
  • CPU를 오래 사용하는 프로세스는 하위 큐로 강등, 입출력 위주 프로세스는 상위 큐 유지 또는 승급

 

동작 방식 요약

1. 새로운 프로세스는 최상위 큐부터 시작
2. 할당 시간보다 빨리 종료되면 → 상위 큐 유지
3. 시간 초과 시 → 하위 큐로 이동 (우선순위 낮아짐)
4. 오래 기다린 프로세스는 다시 승급 → Starvation 방지

 

장점과 단점

장점

• 다양한 프로세스 특성에 대응 가능하다
• 반응성이 뛰어나다
• 자동으로 CPU-bound(CPU 연산이 많은 프로세스)와 I/O-bound(입출력 작업이 많은 프로세스)를 판단

단점

• 구현이 복잡하다
• 정책 설계 실패 시 성능이 저하될 수 있다
• 과도한 피드백은 비효율적일 수 있다

 

Pintos에서의 활용

Pintos 프로젝트에서는 기본적으로 Round Robin 스케줄러가 사용되지만, mlfqs 플래그를 활성화하면 MLFQ 기반으로 다음 요소들이 계산되어 우선순위가 결정됩니다.

• load_avg: 시스템 평균 부하
• recent_cpu: 해당 스레드가 사용한 CPU 시간
• nice: 스레드의 사용자 정의 우선순위 편향값

이 값들을 바탕으로 동적으로 우선순위를 재계산하며, 이를 통해 CPU 점유 시간이 많은 스레드는 낮은 우선순위로, 입출력 위주의 짧은 CPU 점유 시간을 요구하는 스레드는 높은 우선순위로 유지되어 시스템 반응성을 높입니다.

 

 

마치면서

MLFQ는 운영체제가 '누구에게 CPU를 먼저 줄까?'라는 질문에 대해, 스스로 학습하며 판단하는 방식이라고 볼 수 있습니다. 곧 프로세스의 과거 행동, 즉 CPU 사용량이나 입출력 대기 시간을 기반으로 우선순위를 동적으로 조정하게 되죠. 이를 통해 짧고 빠른 작업은 우선적으로 처리하고, 긴 작업은 낮은 우선순위로 내려간 뒤 에이징 기법을 통해 점진적으로 CPU를 다시 할당받도록 유도합니다.