MLFQ
이전 포스팅 CPU 스케줄링에서 여러 스케줄링 방법에 대해 글을 썼다. 스케줄링 방식은 SJF, STCF, RR 등을 소개했는데 각 스케줄링 들은 반환 시간, 응답 시간 중 하나를 개선하면 다른 하나의 성능이 떨어지는 문제가 있었다.
그 뿐 아니라 SJF, STCF 를 동작하기 위해서 프로세스의 작업시간도 알고 있어야 했다.
MLFQ는 반환 시간, 응답 시간 둘다 만족하고, 프로세스 작업시간에 대한 정보 없이도 동작하기 위해 고안되었다.
기본 규칙
여러개의 우선순위가 있는 큐를(높은 우선순위의 큐 - 낮은 우선순위의 큐) 만들어 각 작업들이 특성에 맞게 동적으로 우선순위가 부여된다.
우선순위는 아래 규칙에 맞게 정해진다.
규칙 1
우선순위(A) > 우선순위(B) 일 때, A가 실행되고 B는 실행되지 않는다.
규칙 2
우선순위(A) == 우선순위(B) 일 때, A와 B는 RR(라운드 로빈) 방식으로 실행된다.
예시: 기본 우선순위 실행
3개의 큐(Q2: 최고 우선순위, Q1: 중간, Q0: 최저)가 있고,
- A: Q2에 있음
- B, C: Q1에 있음
- D: Q0에 있음
큐 구조:
Q2(높음): [A]
Q1(중간): [B, C]
Q0(낮음): [D]
실행 순서:
시간: 0 10 20 30 40 50 60 70
|--A--|--B--|--C--|--B--|--C--|--D--|--D--|
설명:
- 0-10ms: A 실행 (Q2가 최고 우선순위)
- A 완료 후, Q1의 B, C가 RR로 실행
- B, C 완료 후, 마지막으로 D 실행핵심: 상위 큐가 비어야 하위 큐의 작업이 실행된다
규칙 3
작업이 시스템에 진입하면 가장 높은 우선순위를 갖는다. 프로세스에 대한 선행 정보를 모르기 때문에 해당 작업이 짧다 가정하고 먼저 높은 우선순위를 부여한다.
예시: 새 작업의 진입
작업 A가 실행 중이고, t=20ms에 새로운 작업 B가 도착:
초기 상태:
Q2(높음): [A]
Q1(중간): []
Q0(낮음): []
시간: 0 10 20 30 40
|--A--|--A--|
t=20ms에 B 도착 → B는 Q2로 진입:
Q2(높음): [A, B]
Q1(중간): []
Q0(낮음): []
시간: 0 10 20 30 40 50
|--A--|--A--|--A--|--B--|--B--|
↑
B 도착 (Q2에 진입)
결과:
- B는 작업 길이를 모르지만 "짧을 것"이라고 낙관적으로 가정
- 최고 우선순위로 시작해서 빠른 응답 시간 확보핵심: 모든 프로세스는 처음 시작은 높은 우선순위
동적 우선순위 관리
MLFQ의 핵심은 과거 행동을 바탕으로 동적인 우선순위를 부여하는 것이다. 높은 우선순위를 부여 후 향후 행동에 따라 낮은 우선순위로 내려가는 방식이다.
규칙 4
작업에게 할당된 시간이 소진되면(CPU를 포기한 횟수와 관계없이) 낮은 우선순위의 큐로 내려간다. 만약 위의 규칙이 없다면 타임 슬라이스 마다 CPU를 포기해서 낮은 우선순위로 내려가지 않고 계속해서 스케줄링에서 이점을 얻을 수 있다.
스케줄러 조작(scheduler manipulation)을 막기위해 필요.
예시 1: 짧은 작업 vs 긴 작업
가정: 각 큐는 타임 슬라이스 10ms, 할당 시간(allotment) 20ms
짧은 작업 A (15ms CPU 필요):
시간: 0 10 20 30
Q2: |A(10)|A(5) | | A 완료! (Q2에서 끝남)
Q1: | | | |
Q0: | | | |
- A는 Q2에서 10ms 사용
- 다시 Q2로 돌아와서 5ms 더 사용 후 완료
- Q2에서만 실행 → 빠른 응답 시간긴 작업 B (100ms CPU 필요):
시간: 0 10 20 30 40 50 60 70 80 90 100 110
Q2: |B(10)|B(10)| | | | | | | | |
↓ allotment(20ms) 소진, Q1으로 이동
Q1: | | |B(10)|B(10)| | | | | | |
↓ allotment(20ms) 소진, Q0으로 이동
Q0: | | | | |B(10)|B(10)|B(10)|B(10)|B(10)|B(10)|
- B는 Q2에서 20ms 사용 후 Q1으로 강등
- Q1에서 20ms 더 사용 후 Q0으로 강등
- 나머지 60ms는 Q0에서 실행
- CPU 집약적 작업은 자연스럽게 낮은 우선순위로 내려감예시 2: 스케줄러 조작 방지
악의적인 작업 C (규칙 4가 없다면):
규칙 4 없는 경우 (구 버전):
- C가 타임 슬라이스(10ms) 중 9ms만 사용하고 I/O 요청으로 CPU 양보
- 다시 돌아오면 여전히 Q2에 위치
- 이를 반복하면 영원히 Q2에서 실행 가능! (Gaming the scheduler)
규칙 4 적용:
시간: 0 9 19 29
Q2: |C(9) |C(9) |C(2) | 총 20ms 사용 → Q1으로 강등!
I/O I/O ↓
Q1: | | |C(9) |
I/O
- CPU 사용 시간을 누적 추적
- I/O로 속이더라도 allotment 소진되면 강등
- 공정한 스케줄링 보장핵심: 작업의 행동 패턴을 학습하여 적절한 우선순위 부여
규칙 5
일정 주기 S가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동 규칙 5의 경우 낮은 우선순위의 프로세스가 실행되지 못하고 높은 우선순위의 프로스세만 실행되는 **기아상태(starvation)**에 빠질 수 있다.
예시: Priority Boost로 기아 상태 방지
가정: S = 50ms마다 모든 작업을 Q2로 이동
시나리오: 긴 작업 A와 짧은 작업들 B, C, D가 계속 도착
규칙 5 없이:
시간: 0 10 20 30 40 50 60 70 80 90 100
Q2: |B |C |D |B2 |C2 |D2 |B3 |C3 | | |
Q1: | | | | | | | | | | |
Q0: |A |A |A |A |A |A |A |A |A... |A... | ← A는 영원히 실행 못함!
문제: 새로운 짧은 작업들이 계속 Q2에 들어오면 A는 기아 상태!규칙 5 적용 (S=50ms):
시간: 0 10 20 30 40 50 60 70 80 90 100
Q2: |B |C |D |B2 |C2 |A! |A |D2 | | |
Q1: | | | | | | | | | | |
Q0: |A |A |A |A |A | ↑ |
50ms 경과 → 모든 작업 Q2로 Boost
t=50ms에 Priority Boost 발생:
- A가 Q0에서 Q2로 승격
- B2, C2와 함께 RR로 실행
- A도 CPU 시간을 받을 수 있음!
시각화:
t=0: Q2:[B] Q1:[] Q0:[A]
t=10: Q2:[C] Q1:[] Q0:[A]
t=20: Q2:[D] Q1:[] Q0:[A]
t=30: Q2:[B2] Q1:[] Q0:[A]
t=40: Q2:[C2] Q1:[] Q0:[A]
t=50: Q2:[A,C2,D2] Q1:[] Q0:[]핵심:
- 기아 방지: 낮은 우선순위 작업도 주기적으로 기회 부여
- 적응성: 작업 특성이 변해도 재평가 가능
- 공정성: 모든 작업에 “동등한 기회”
MLFQ 주의할 점
- 큐를 몇개 만들 것인가
- 타임 슬라이스를 얼만큼 설정할 것인지
- 높은 우선순위 큐: 짧은 타임 슬라이스가 좋음 (응답성)
- 낮은 우선순위 큐: 긴 타임 슬라이스가 좋음 (오버헤드 감소)
- Priority Boost 주기(S)를 얼마로 설정할 것인가
- 너무 짧으면: 성능 저하
- 너무 길면: 기아 상태 위험