MLFQ - Multi-Level Feedback Scheduling

1962년, Fernando J. Corbató (MIT)
→ 시분할 운영체제(Time Sharing OS)의 선구자
CTSS (MIT Compatible Time-Sharing System)
→ 여러 사용자가 동시에 컴퓨터를 쓰는 환경을 처음 본격적으로 구현

이로부터 다중 사용자 환경에서의 체감 성능 문제가 중요해졌다.

Round Robin의 한계

RR은 공정성(fairness)는 좋으나 응답시간(reponse time), 반환 시간(turn around time)이 짧은 작업 입장에서는 최악이 될 수 있다.

모든 작업을 똑같이 취급하기에, 금방 끝날 작업도 오래 대기하게 되는 문제 발생

SJF, SPN, STCF, SRT, SRTF 의 문제점

위 알고리즘들은 가장 짧은 작업을 먼저 실행하면 평균 반환시간이 최소화된다는 공통점이 있다.

그러나 작업의 실행 시간을 미리 알아야만 하는데, 현실에서는 미래 실행 시간을 알 수 없음 즉, 실제 시스템에서는 사용 불가능하다.

MLFQ는?

짧은 작업을 유추해서 우선 처리한다!

MLFQ의 목표

Turnaround time 최소화
- 짧은 작업을 빠르게 끝내자
대화식(interactive) 사용자 응답 시간 최소화
- 사용자가 “시스템이 빠르다"고 느끼게 하자

결과적으로: - Time-sharing 시스템에서 체감 성능을 극대화

MLFQ의 기본 규칙

여러 개의 큐가 있다. 큐 자체에 우선순위가 매겨져 있다.

하나의 큐에 있는 프로세스들은 우선순위가 동일하다. => 이들끼리는 RR 형태로 스케줄링 된다.

상위 큐 : 높은 우선순위 상위 큐로 올라갈수록 CPU 차지할 확률 높아짐

하위 큐 : 낮은 우선순위 하위 큐로 내려갈수록 CPU 차지하는 시간 (TQ)가 길어짐

이때 프로세스의 우선순위는 고정 방식이 아니다. 프로세스의 특성에 따라 우선순위는 변화한다.

IO Bound Job vs CPU Bound Job

IO를 하며 다른 프로세스에게 CPU를 양보하는 프로세스는 우선순위를 높인다.
CPU를 집중적으로 사용하는 프로세스는 우선수위를 낮춘다.

같은 큐의 프로세스들은 RR을 통해 스케줄링 된다.

MLFQ는 우선순위 기반 선점형(preemptive) 스케줄러이다. 현재 실행 중인 프로세스보다 높은 우선순위 큐에 프로세스가 도착하면, 즉시 현재 수행중인 프로세스를 중지시키고 cpu를 넘긴다.

MLFQ의 우선순위 변경

MLFQ는 프로세스를 미리 “짧은 작업 / 긴 작업"으로 구분하지 않는다. 실행 결과를 보고 판단한다.

CPU를 짧게 쓰고 자주 양보 → 대화형 작업일 가능성 ↑ CPU를 길게 연속 사용 → 계산 위주(배치형) 작업일 가능성 ↑

※대화형 작업이란 사용자 입력을 자주 기다리고, 입력이 들어오면 짧은 계산을 수행한 뒤 다시 대기 상태로 돌아가는 작업을 말한다.

규칙 1 : 시스템에 들어오면 가장 높은 우선순위 큐에 배치

기회를 먼저 줌

규칙 2 : CPU를 오래 쓰면 강등.

주어진 Time Quantum을 끝까지 사용하면 우선순위 하락
Time Quantum이 끝나기 전에 CPU를 양보하면 같은 우선순위 유지

입출력 작업은 어떻게 처리하는가?

프로세스가 Time Quantum 전에 IO로 인해 CPU를 양도하면, 같은 우선순위가 유지된다. CPU를 자주 양도하는 프로세스는 높은 우선순위에 머물며 준비될 때마다 실행되는 형식.

IO 위주 작업인 회색 프로세스가 준비될 때마다 cpu를 뺏는 경우.

기본 MLFQ의 문제점

시스템 내에 너무 많은 대화형 작업이 있을 경우 긴 작업은 CPU를 할당받지 못할 수 있다. - 기아 상태 발생
프로그램을 Time Quantum의 99%까지만 실행하고, 의미 없는 IO를 진행하여 CPU를 양도하는 식으로 스케줄러를 속일 수 있다.
MLFQ의 기본 원칙에서는, 한 번 낮아진 우선순위를 올려줄 기회가 없다. CPU 위주의 작업이 대화형 직업으로 바뀌어도 우선순위는 낮다.

새로운 시도

규칙 3 : 일정 시간 S가 지나면, 시스템의 모든 작업들을 최상위 큐로 이동시킴 우선순위 올림, boosting

아무리 낮은 큐에 있던 작업이라도 S 시간마다 반드시 CPU 기회 확보 => 기아 해결

voodoo constants, black magic -> 완벽한 boosting 주기 s

s 값은 너무 크면 기아 발생, 너무 작으면 RR과 유사해짐. CPU 위주 작업도 계속 상위 큐 유지

따라서 이론적으로 완벽한 값이 없다. 경험적인 튜닝이 필요하다.

부스팅 주기마다 끌어 올려지는 검은 프로세스

Gaming Tolerance

MLFQ의 2번 문제점처럼 프로세스는 time quantum 끝나기 전에 일부러 IO를 호출하며 스케줄러를 속일 수 있음(gaming)

해결책 : 같은 큐 레벨에서 사용한 CPU 시간의 누적합을 추적 한 번의 연속 실행만 보지 않음

새로운 규칙 4:

각 큐 레벨마다 허용 CPU 사용량을 정해 둠 프로세스가 CPU를 양보했는지 여부와 상관 없이 누적 CPU 사용 시간이 각 큐의 허용 time quantum을 초과하면 우선순위 강등

MLFQ의 여러 이슈들

MLFQ는 파라미터 기반 스케줄러이다.
MLFQ는 이론적으로 고정된 알고리즘이 아니라, 설정 값에 따라 성능이 크게 달라진다.
이때 필요 변수 설정은, workload의 heruistic(경험)에 기반하여 적절한 값을 찾아야 한다.
큐의 개수, 큐당 time quantum, 우선순위 boosting 간격 …
높은 우선순위 큐는 짧은 time quantum 낮은 우선순위 큐는 긴 time quantum

실제 예시

Solaris

큐 개수 : 약 60개
time quantum : 큐마다 다름
boosting 주기 : 약 1초

이 값들은 하드 코딩되지 않고, 테이블 기반으로 관리된다.

프로세스 우선순위가 실행 중 어떻게 변하는지
각 큐의 Time Quantum 길이
우선순위 올림 주기 이걸 테이블로 제공해서 관리자가 테이블 수정이 가능하다.

BSD, 초기 Unix

decay factor 이용 : 과거 CPU 사용량의 영향력을 시간이 지남에 따라 점점 줄이는 방식