🥔 Multi-Level Feedback Queue Scheduler (MLFQS)
운영체제에서 CPU 스케줄링은 프로세스의 실행 순서와 시간을 결정하는 중요한 메커니즘이다. 그중 MLFQS(Multi-Level Feedback Queue Scheduler) 는 다단계 큐 방식에 '피드백' 기능이 추가된 동적 스케줄링 알고리즘으로, 다양한 종류의 프로세스를 공정하게 처리하고 시스템 반응성을 높이기 위해 사용된다.
특히 4.4BSD 기반의 Unix 시스템이나 교육용 운영체제인 Pintos에서도 사용된다.
🥔 기본 개념 요약
| 항목 | 설명 |
|---|---|
| 다단계 큐 (MLQ) | 여러 개의 우선순위 큐로 나누어 작업을 분산 |
| 피드백 기능 (Feedback) | 프로세스의 실행 특성에 따라 우선순위를 자동 조정 |
| 선점형 (Preemptive) | 더 높은 우선순위가 도착하면 선점 가능 |
| 공정성 (Fairness) | CPU 점유가 많은 프로세스는 우선순위 하락, 적은 프로세스는 상승 |
🥔 스케줄링 큐 구조
MLFQS는 여러 개의 우선순위 큐(priority queue) 를 가지고 있다. 각 큐는 시간 할당량(time slice) 이 다르고, 높은 우선순위 큐일수록 짧은 타임슬라이스를 가지며 빠르게 처리된다.
| 큐 번호 | 우선순위 | 타임슬라이스 | 특성 |
|---|---|---|---|
| Q0 | 가장 높음 | 짧음 | I/O-bound 프로세스 적합 |
| Q1 | 중간 | 보통 | 일반 프로세스 |
| Q2 | 가장 낮음 | 김 | CPU-bound 프로세스 적합 |
→ 프로세스는 CPU 사용 시간이나 대기 시간에 따라 상하 큐로 이동하면서 동적으로 우선순위가 조정된다.
🥔 피드백 메커니즘
📌 핵심 규칙
- 처음 생성된 프로세스는 최상위 큐(Q0)에 배치
- 시간 할당을 초과하면 하위 큐로 강등
- 오랜 시간 대기 시 우선순위 상승 가능
이러한 규칙 덕분에 짧고 자주 실행되는 프로세스(I/O-bound) 는 빠르게 처리되고, CPU 자원을 많이 사용하는 프로세스(CPU-bound) 는 점차 낮은 큐에서 처리되게 된다.
🥔 nice 값과의 관계
Unix 계열 시스템에서는 nice 값을 통해 프로세스의 기본 우선순위(priority) 를 조정할 수 있다.
| nice 값 | 의미 | 우선순위 영향 |
|---|---|---|
| -20 | 가장 호의적 (높은 우선순위) | 우선순위 ↑ |
| 0 | 기본값 | 중립 |
| 19 | 가장 비호의적 (낮은 우선순위) | 우선순위 ↓ |
nice 값이 낮을수록 CPU를 더 많이 점유할 수 있는 프로세스로 간주되며, MLFQS에서도 이를 기반으로 초기 priority 가 계산된다.
🥔 4.4BSD 스케줄러와 MLFQS
4.4BSD 스케줄러는 MLFQS의 대표적인 구현체 중 하나로 다음과 같은 특징을 가진다:
-
각 프로세스의 우선순위는 다음을 기반으로 계산됨:
priority = max_priority - (recent_cpu / 4) - (nice * 2) -
recent_cpu: 최근 사용한 CPU 시간
-
nice: 우선순위 힌트 값
이 수식은 CPU 사용량이 많을수록, nice 값이 클수록 우선순위가 낮아지도록 설계되어 있다.
또한, load_avg 와 같은 시스템 부하 값을 주기적으로 업데이트하여 전체적인 동적 우선순위 관리를 수행한다.
🥔 MLFQS 장단점
✅ 장점
- 다양한 작업 패턴(I/O-bound, CPU-bound)에 유연하게 대응
- 사용자 개입 없이도 자동으로 우선순위 조정
- 시스템 응답성과 효율성 모두 향상
❌ 단점
- 구현이 복잡함
- 일부 긴 작업이 너무 늦게 실행되는 기아(starvation) 문제가 생길 수 있음 (보통 aging으로 해결)
🥔 정리
- MLFQS는 선점형, 동적 우선순위, 피드백 큐 기반 스케줄러
- nice 값, recent_cpu, system load 등을 이용하여 우선순위를 조정
- 4.4BSD 스케줄러는 MLFQS의 대표적 사례로, 많은 운영체제에서 영향을 받음
- 다양한 프로세스 유형을 공정하고 효율적으로 스케줄링하기 위한 강력한 전략
