Multi-Level Feedback Queue Scheduler (MLFQS)

스레드 우선순위(priority)를 동적으로 조정하며, 여러 개의 큐에서 스레드를 관리하는 스케줄링 기법입니다.

피드백이라는 말처럼, CPU 사용량에 따라 스레드의 우선순위를 낮추거나 높이며, 사용자 개입 없이 스레드의 실행 순서를 자동으로 조정합니다.

주요 변수 (초기값 0)

nice: 스레드의 우선순위 조절 민감도로 숫자가 높을 수록 덜 우선시됨. (-20 ~ +20)
recent_cpu: 해당 스레드가 최근 사용한 CPU 시간 (시간 누적값)
long_avg: 시스템 평균 로드 (CPU 점유 스레드 수의 평균)

왜 필요하나요?

기본 스케줄러 (thread_set_priority)는 우선순위를 수동으로 설정해야합니다.
그러나 MLFQS는 nice 값과 recent_cpu 값을 바탕으로 자동으로 우선 순위를 관리해줍니다.
→ 사용자가 우선순위를 직접 조정하지 않아도 공정한 CPU 분배를 할 수 있습니다.

MLFQS 우선순위 계산식

1. `nice` 계산 (스레드 우선순위)

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)

PRI_MAX는 63 (최고 우선순위)
우선순위는 0 ~ 63 사이로 제한

2. `recent_cpu` 계산 (최근 사용한 CPU 시간)

recent_cpu = (2*load_avg)/(2*load_avg + 1) * recent_cpu + nice

CPU를 오래 사용하면 recent_cpu 증가

3. `long_avg` 계산 (평균 로드)

load_avg = (59/60)*load_avg + (1/60)*ready_threads

ready_threads는 (ready 상태의 스레드 수 + running 상태)의 하나 포함

갱신 시기

매 tick (4 tick): recent_cpu++ 갱신 (running 상태인 스레드만)
매 초 (100tick): load_avg, recent_cpu, 모든 스레드의 priority 재계산하며 갱신
ready 상태 변경 시: priority 즉시 갱신 필요 (삽입 시 정렬용)

PintOS에서

MLFQS 관련 코드는 다음 파일에 구현됩니다.

threads/thread.c
threads/fixed-point.h/.c ← 실수 계산용 유틸
threads/synch.c (간접 연관)

thread_priority 필드를 MLFQS 계산값으로 자동 덮어씌워야 하므로, 다음 함수들의 조건 분기 처리도 필요합니다.

thread_set_priority() → MLFQS 켜져 있으면 무시
thread_get_priority() → MLFQS 값 사용

→ 구현 방식은 힌트가 포함되어 있어서 넘어가겠습니다.

요약

항목	내용
정의	여러 우선순위 큐에서 스레드를 피드백 기반으로 재조정하는 스케줄러
핵심 변수	`nice`, `recent_cpu`, `load_avg`
우선순위 식	`PRI_MAX - (recent_cpu / 4) - (nice * 2)`
주기적 갱신	매 tick, 매 4 tick, 매 100 tick마다 갱신
Pintos 구현	`thread.c`, `fixed-point.c`, `timer.c` 등
고려사항	고정소수점 사용, 우선순위 정렬, 조건 분기 처리 필수

728x90

Multi-Level Feedback Queue Scheduler