[OS] MLFQ: Multi Level Feedback Queue

멀티 레벨 피드백 큐에 대해 자세히 알아보자.

Apr 14, 2024

Contents

✅ 멀티 레벨 피드백 큐란?기본 MLFQ 시도 1: 우선 순위 변경 현재 MLFQ의 문제점!!시도 2: 우선순위의 상향 조정 시도 3: 더 나은 시간 측정 ✅ 더 고려해야 할 사항들 ✅ 요약

✅ 멀티 레벨 피드백 큐란?

MLFQ로 해결하려고 하는 기본적인 문제는 두 가지다.

짧은 작업을 먼저 실행시켜 반환 시간을 최적화하고자 한다.

→ STCF는 반환 시간은 좋지만 불행히도 운영체제는 각 작업의 실행 시간을 미리 알 수 없다.

MLFQ는 대화형 사용자에게 응답이 빠른 시스템이라는 느낌을 주고 싶었기 때문에 응답 시간을 최적화한다.

→ RR은 응답 시간은 좋지만 반환 시간이 최악이라 안 된다.

❓

작업의 실행 시간에 대한 선행 정보 없이 대화형 작업의 응답 시간을 최소화하고 동시에 반환 시간을 최소화하는 스케쥴러를 어떻게 설계할 수 있을까?

기본 MLFQ

기본 규칙은 다음과 같다.

규칙 1: Priority(A) > Priority(B) 이면, A가 실행된다. (B는 실행되지 않는다)

규칙 2: Priority(A) == Priority(B) 이면, A와 B는 RR 방식으로 실행된다.

시도 1: 우선 순위 변경

→ 기본 규칙에 따르면, 위 사진의 경우 C와 D는 A와 B가 끝나기 전까지 전혀 실행되지 않을 것이다! 이 문제를 해결하기 위해 다음과 같은 규칙을 추가한다.

규칙 3: 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓여진다.

규칙 4a: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.

규칙 4b: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

예 1: 한 개의 긴 실행 시간을 가진 작업

→ 긴 실행 시간을 가진 작업은 시간이 지날 수록 규칙 4a에 따라 우선순위가 점점 내려갈 것이다.

예 2: 짧은 작업과 함께 실행

→ 짧은 작업은 우선순위가 제일 낮아지기 전에 작업이 종료될 것이다. 이러한 방식으로 MLFQ를 SJF로 근사할 수 있다.

예 3: 입출력 작업에 대해서는 어떻게?

→ 규칙 4b에 따라 입출력을 수행하면 타임 슬라이스가 종료되기 전에 CPU를 양도하게 되어 동일한 우선순위를 유지할 수 있다.

현재 MLFQ의 문제점!!

기아 상태(starvation)가 발생할 수 있다.

→ 대화형 작업이 많이 존재하면, 그들이 모든 CPU 시간을 소모할 것이고 긴 실행 시간 작업은 CPU 시간을 할당받지 못할 것이다.

스케쥴러를 자신에게 유리하게 동작하도록 악의적으로 프로그램을 작성할 수 있다.

→ 자신의 작업의 우선순위를 유지하기 위해, 타임 슬라이스 시간을 넘기 전에 CPU를 양도할 수 있다. 이렇게 되면 CPU를 독점하게 될 것이다.

시도 2: 우선순위의 상향 조정

위와 같은 문제점들을 피하기 위해, 주기적으로 모든 작업의 우선순위를 상향 조정하는 것이다. 새로운 규칙은 다음과 같다.

규칙 5: 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

→ 프로세스는 이제 더 이상 굶지 않는다!

→ 프로세스의 작업이 CPU 위주의 작업이었다가, 대화형 작업으로 특성이 변할 경우 우선순위 상향을 통해 적합한 스케쥴링을 적용할 수 있다!

물론 S 값의 결정이 필요하다. S 값은 얼마로 해야하는가? S는 정확하게 결정할 수 없다. 그래서 부두 상수라고 불렸다. 너무 크면 긴 실행 시간을 가진 작업은 굶을 수 있으며, 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없게 된다. → 프로그램 작업 유형에 따라 알잘딱깔센!

시도 3: 더 나은 시간 측정

아직 해결해야 할 문제가 남았다. 스케쥴러를 의도적으로 자신에게 유리하게 동작시키는 것을 어떻게 막을 수 있을까? 이 일을 가능하게 한 주범은 규칙 4a와 4b이다. 두 규칙은 작업이 타임 슬라이스가 끝나기 전에 CPU를 양보하여 우선 순위를 유지할 수 있도록 한다.

해결책은 각 단계에서 CPU 총 사용 시간을 측정하는 것이다! 이제 타임 슬라이스를 한 번에 소진하든 짧게 여러 번 소진하든 상관 없이 다음 우선순위 큐로 강등된다. 규칙 4a와 4b를 하나로 합쳐 다음과 같이 재정의한다.

규칙 4: 주어진 단계에서 시간 할당량을 소진하면 (CPU를 몇 번 양도했는지 상관없이), 우선순위는 낮아진다.

✅ 더 고려해야 할 사항들

MLFQ 스케쥴링에는 아직 여러 다른 쟁점들이 남아 있다. 예를들어,

몇 개의 큐가 존재해야 하는가?

큐당 타임 슬라이스의 크기는 얼마로 해야 하는가?

기아를 피하고 변화된 행동을 반영하기 위해 얼마나 자주 우선순위가 상향 조정되어야 하는가?

이러한 질문들에는 쉽게 대답할 수 없다. 워크로드에 대해 충분히 경험하고 계속 조정해 나가면서 균형점을 찾아야 한다.

그 예로, 대부분의 MLFQ 기법들은 큐 별로 타임 슬라이스를 변경할 수 있다. 우선순위가 높은 큐는 보통 짧은 타임 슬라이스가 주어진다. 이 큐는 대화형 작업으로 구성되고, 결국 이 작업들을 빠르게 교체하는 것은 의미가 있다. 반대로 낮은 우선순위는 CPU-중심의 오래 실행되는 작업들을 포함한다. 긴 타임 슬라이스가 적합하다.

또, 일부 스케쥴러의 경우 가장 높은 우선순위를 운영체제 작업을 위해 예약해둔다. 일반적인 사용자 작업은 가장 높은 우선순위를 얻을 수 없는 것이다.