11.1 멀티 레벨 피드백 큐 (MLFQ): 기본 규칙
MLFQ 개념
- 여러 개의 우선순위 큐로 구성되며, 각 큐는 다른 우선순위를 가짐.
- 스케줄링 기본 원칙:
- 규칙 1: 높은 우선순위 큐에 있는 작업이 먼저 실행됨.
- 규칙 2: 동일 우선순위 작업은 라운드 로빈 (RR) 방식으로 실행.
11.2 우선순위 변경: 시도 1
우선순위 조정 규칙
- 규칙 3: 시스템에 새로 진입한 작업은 최상위 큐에서 시작.
- 규칙 4a: 주어진 타임 슬라이스를 소진하면 우선순위가 하락.
- 규칙 4b: 타임 슬라이스 소진 전 CPU 양보 시 동일 우선순위 유지.
예제
-
긴 작업 (CPU 집중형 작업):
- 최상위 큐(Q2)에서 시작 → 타임 슬라이스를 소진 → 한 단계 아래 큐(Q1)로 이동 → 최하위 큐(Q0)에 정착.
- 최상위 큐(Q2)에서 시작 → 타임 슬라이스를 소진 → 한 단계 아래 큐(Q1)로 이동 → 최하위 큐(Q0)에 정착.
-
짧은 작업 (대화형 작업):
- 대화형 작업(B)은 짧은 실행 시간 덕분에 높은 우선순위를 유지.
- 짧은 시간 내 종료하여 최하위 큐로 이동하지 않음.
-
입출력 중심 작업:
- 타임 슬라이스 전에 CPU를 양보 → 동일 우선순위 유지 → 높은 우선순위에서 빠른 실행 보장.
- 타임 슬라이스 전에 CPU를 양보 → 동일 우선순위 유지 → 높은 우선순위에서 빠른 실행 보장.
11.3 기아 상태와 우선순위 상향: 시도 2
기아 상태 문제
- 긴 작업이 낮은 우선순위 큐에 머물러 실행되지 못하는 기아 상태 (starvation) 발생 가능.
해결 방안
- 규칙 5: 일정 주기(S)가 지나면 모든 작업을 최상위 큐로 이동.
- 긴 작업도 주기적으로 CPU를 할당받아 기아 상태 방지.
- 특성이 바뀌는 작업(CPU 집중형 → 대화형)도 재평가 가능.
11.4 조작 방지: 시도 3
문제: 스케줄러 악용
- 타임 슬라이스 종료 직전에 CPU 양보를 반복 → 높은 우선순위 유지 → CPU 독점 가능.
해결 방안
- 규칙 4 개정:
- 각 단계에서 누적 CPU 사용 시간을 기록.
- 누적 시간이 타임 슬라이스를 초과하면 우선순위 강등.
- CPU를 양보하더라도 강등을 피할 수 없음.
11.5 추가 조정 및 변수 설정
설정해야 할 변수
- 큐의 개수: 우선순위 세분화 수준 결정.
- 타임 슬라이스 크기:
- 높은 우선순위 큐 → 짧은 타임 슬라이스 (대화형 작업에 적합).
- 낮은 우선순위 큐 → 긴 타임 슬라이스 (CPU 집중형 작업에 적합).
- 우선순위 상향 주기 (S):
- 너무 길면 긴 작업이 기아 상태에 빠질 가능성.
- 너무 짧으면 대화형 작업의 우선순위 유지 어려움.
11.6 MLFQ 요약
MLFQ 핵심 규칙
- 규칙 1: 높은 우선순위 작업이 먼저 실행.
- 규칙 2: 동일 우선순위 작업은 RR 방식으로 실행.
- 규칙 3: 새 작업은 최상위 큐에서 시작.
- 규칙 4: CPU 사용 시간 소진 시 우선순위 하락.
- 규칙 5: 일정 주기마다 모든 작업의 우선순위를 상향 조정.
MLFQ의 장점
- 작업 특성에 대한 사전 정보 없이도 효율적으로 스케줄링.
- 반환 시간 최적화 (SJF/STCF 근사).
- 응답 시간 최적화 (대화형 작업 우선).
- 널리 사용되는 스케줄링 방식:
- BSD Unix, Solaris, Windows NT 등.
