2-4장. 스케줄링 : 멀티 레벨 피드백 큐(MLFQ)

멀티 레벨 피드백큐(Multi Level Feedback Queue) 스케줄러가 해결하려고 하는 기본적인 문제는 두 가지이다. 첫째, 짧은 작업을 먼저 실행시켜 반환시간을 최적화하고자 한다. 전 장의 SJF나 STCF 같은 알고리즘은 작업의 실행 시간 정보를 필요로 하지만, 불행히도 운영체제는 이 실행 시간을 미리 알 수 없다. 둘째, MLFQ는 대화형 사용자(즉, 컴퓨터 사용자)에게 응답이 빠른 시스템이라는 느낌을 주고 싶기 때문에 응답 시간을 최적화 한다. 불행히도 RR과 같은 알고리즘은 응답시간을 단축시키지만 반환 시간은 거의 최악이다. 

 

그러면 프로세스에 대한 정보가 없다면 이러한 스케줄러를 어떻게 만들 수 있을까? 실행 중인 작업의 특성을 알아내고 이를 이용하여 더 나은 스케줄링 결정을 하기 위한 방법은 무엇일까?

 

MLFQ : 기본 규칙

MLFQ의 기본 알고리즘을 설명한다. 현재 구현되어 있는 여러 MLFQ들은 자세하게 살펴보면 차이가 있지만, 기본적으로 비슷한 방법을 사용하고 있다. 

 

MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위(Priority level)가 배정된다. 실행 준비가 된 프로세스는 이 중 하나의 큐에 존재한다. MLFQ는 실행할 프로세스를 결정하기 위하여 우선순위를 사용한다. 높은 우선순위를 가진 작업, 즉 높은 우선순위 큐에 존재하는 작업이 선택된다. 

 

큐에 둘 이상의 작업이 존재할 수 있다. 이들은 모두 같은 우선순위를 가진다. 이 작업들 사이에서는 라운드 로빈(RR) 스케줄링 알고리즘이 사용된다.

 

MLFQ 스케줄링의 핵심은 우선순위를 정하는 방식이다. MLFQ는 각 작업에 고정된 우선순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다.

 

예를 들어, 어떤 작업이 키보드 입력을 기다리며 반복적으로 CPU를 양보하면 MLFQ는 해당 작업의 우선순위를 높게 유지한다. 이러한 패턴은 대화형 프로세스가 나타내는 패턴과 같다. 대신에 한 작업이 긴 시간 동안 CPU를 집중적으로 사용하면 MLFQ는 해당 작업의 우선순위를 낮춘다. 이렇게 MLFQ는 작업이 진행되는 동안 해당 작업의 정보를 얻고, 이 정보를 이용하여 미래 행동을 예측한다. 

 

MLFQ의 두 가지 기본 규칙은 다음과 같다.

 

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

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

MLFQ의 예

위 그림은 MLFQ 특성상 우선 순위가 높은 A와 B가 RR 방식으로 실행되고 있다. 중간 순위인 C와 가장 낮은 순위의 D는 실행되지 않는다. 아직 이것 만으로는 MLFQ가 어떻게 동작하는지 알 수 없다. 작업 우선순위가 시간에 따라 어떻게 변화하는지 알아보자.

 

시도 1 : 우선순위 변경

MLFQ가 작업의 우선순위를 어떻게 바꿀 것인지 결정해야 한다. 작업의 우선순위를 변경하는 것은 작업이 존재할 큐를 결정하는 것과 마찬가지이다. 이를 위해 워크로드의 특성을 반영해야 한다. 짧은 실행 시간을 갖는 CPU를 자주 양보하는 대화형 작업과 많은 CPU 시간을 요구하지만 응답 시간은 중요하지 않은 긴 실행 시간의 CPU 위주 작업이 혼재되어 있다. 

 

위의 MLFQ의 규칙을 좀 더 추가하면 다음과 같다.

 

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

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

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

 

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

몇 가지 예를 살펴보도록 하겠다. 우선 긴 실행 시간을 가진 작업이 도착했을 때 어떤 일이 일어나는지 알아보자. 

 

그림은 세 개의 큐로 이루어진 스케줄러에서 시간이 지남에 따라 작업의 우선순위가 어떻게 변화하는지 보여준다.

 

예에서 보는 것처럼 작업은 최고 우선순위로 진입한다.(Q2) 10msec 타임 슬라이스가 하나 지나면 스케줄러는 작업의 우선순위를 한 단계 낮추어 해당 작업을 Q1로 이동시킨다. 다시 타임 슬라이스 동안 Q에서 실행한 후 작업은 마침내 가장 낮은 우선순위를 가지게 되고 Q0으로 이동된다. 이후에는 Q0에 계속 머무르게 된다.

 

예 2 : 짧은 작업과 함께

좀 더 복잡한 예를 살펴보겠다. 이 예에서는 2가지 작업이 존재한다. A는 오래 실행되는 CPU 위주 작업이고 B는 짧은 대화형 작업이다. A는 얼마 동안 이미 실행해 온 상태이고 B는 이제 도착했다고 가정하자. 어떤 일이 벌어질까? MLFQ는 SJF와 근사하게 동작해서 B를 선호할 것인가?

 

이 그림에서는 그 예에 대한 결과를 보여준다. 다른 오래 실행되는 CPU 위주 작업들처럼 A는 가장 낮은 우선순위 큐에서 실행되고 있다. B는 T = 100에 시스템에 도착하고 가장 높은 우선순위 큐에 놓여진다. 실행 시간이 짧기 때문에, 두 번의 타임 슬라이스를 소모하면 B는 바닥의 큐에 도착하기 전에 종료한다. 그런 후 A는 낮은 우선순위에서 실행을 재개한다.

 

이 예에서 이 알고리즘의 주요 목표를 알 수 있다. 스케줄러는 작업이 짧은 작업인지, 긴 작업인지 알 수 없기 때문에 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여한다. 진짜 짧은 작업이면 빨리 실행되고 바로 종료될 것이다. 짧은 작업이 아니라면, 천천히 아래 큐로 이동하게 되고 스스로 긴 배치형 작업이라는 것을 증명하게 된다. 이러한 방식으로 MLFQ는 SJF를 근사할 수 있다.

 

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

입출력 작업을 수행하는 예를 살펴보자. 규칙 4b가 말하는 것처럼, 프로세스가 타임 슬라이스를 소진하기 전에 프로세서를 양도하면 같은 우선순위를 유지하게 된다. 이 규칙의 의도는 간단하다. 대화형 작업이 키보드나 마우스로부터 사용자 입력을 대기하며 자주 입출력을 수행하면 타임 슬라이스가 종료되기 전에 CPU를 양도하게 될 것이다. 그런 경우 동일한 우선순위를 유지하게 하는 것이다.

 

다음 그림은 이 규칙이 동작하는 예를 보여준다. B는 대화형 작업으로서 입출력(I/O)을 수행하기 전에 1 msec 동안만 실행된다. A는 긴 배치형 작업(CPU 중심 작업)으로서 B와 CPU를 사용하기 위하여 경쟁한다. B는 CPU를 계속해서 양도하기 때문에 MLFQ방식은 B를 가장 높은 우선순위로 유지한다. B가 대화형 작업이라면 MLFQ는 대화형 작업을 빨리 실행시킨다는 목표에 더 근접하게 된다. 

 

현재 MLFQ의 문제점

현재 MLFQ는 단순하다. CPU를 긴 작업들과 짧은 작업들 사이에 잘 공유하고, 입출력-중점 대화형 작업을 빨리 실행시키기 때문에 잘 동작하는 것처럼 보인다. 하지만 이 방식은 심각한 결점을 가진다.

 

첫째, 기아 상태(Starvation)가 발생할 수 있다. 시스템에 너무 많은 대화형 작업이 존재하면 그들이 모든 CPU 시간을 소모하게 될 것이고 따라서 긴 실행 시간 작업은 CPU 시간을 할당받지 못할 것이다. 이러한 시나리오에서도 긴 실행 시간 작업들이 진행이 되도록 만들고 싶으면 어떻게 해야 할까?

 

둘째, 똑똑한 사용자라면 스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있다. 스케줄러를 자신에게 유리하게 동작시킨다는 것은 일반적으로 스케줄러를 속여서 지정된 몫보다 더 많은 시간을 할당하도록 하게 만드는 것을 가리킨다. 지금까지 논의한 알고리즘은 이러한 공격에 취약하다. 타임 슬라이스가 끝나기 전에 아무 파일을 대상으로 입출력 요청을 내려 CPU를 양도한다. 그렇게 하면 같은 큐에 머무르며 높은 퍼센트의 CPU 시간을 얻게 된다. 제대로 된다면, CPU를 거의 독점할 수 있게 된다.

 

마지막으로 프로그램은 시간 흐름에 따라 특성이 변할 수 있다. CPU 위주 작업이 대화형 작업으로 바뀔 수 있다. 현재 구현 방식으로는 그런 작업은 운이 없게도 다른 대화형 작업들과 같은 대우를 받을 수 없다.

 

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

규칙을 보완하여 기아 문제를 방지할 수 있는지 살펴보자. CPU 위주 작업이 조금이라도 진행하는 것을 보장하기 위해서 무엇을 할 수 있을까?

 

간단한 아디어는 주기적으로 모든 작업의 우선순위를 상향 조정(Boost) 하는 것이다. 목적을 달성하기 위해 여러 방법이 존재하지만 간단한 방법을 사용하기로 하자. 모두 최상위 큐로 보내는 것이다. 새로운 규칙을 추가하면 다음과 같다.

 

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

새 규칙은 두 가지 문제를 한 번에 해결한다. 첫째, 프로세스는 굶지 않는다는 것을 보장받는다. 최상위 큐에 존재하는 동안 작업은 다른 높은 우선순위 작업들과 라운드 로빈 방식으로 CPU를 공유하게 되고 서비스를 받게 된다. 둘째, CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우 우선순위 상향을 통해 스케줄러가 변경된 특성에 적합한 스케줄링 방법을 적용한다.

 

물론 S값의 결정이 필요하다. S를 얼마로 해야 하는가? 이러한 종류의 값을 부두 상수(voo-doo constants)라고 불렀다. 이러한 값을 정확하게 결정하기 위해서는 흑마술이 필요한 것처럼 보이기 때문이다. 불행하게도 S는 그러한 종류의 변수이다. 너무 크면 긴 실행 시간을 가진 작업은 굶을 수 있으며 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없게 된다.

 

시도 3 : 더 나은 시간 측정

해결해야 할 문제가 하나 더 있다. 스케줄러를 자신에게 유리하게 동작시키는 것을 어떻게 막을 수 있을까? 이러한 일을 가능하게 만든 주범은 규칙 4a와 4b이다. 두 규칙은 작업이 타임 슬라이스가 끝나기 전에 CPU를 양보하여 우선 순위를 유지가 가능하게 한다. 무엇을 해야 할까?

 

여기서 해결책은 MLFQ의 각 단계에서 CPU 총 사용 시간을 측정하는 것이다. 스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장한다. 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등된다. 타임 슬라이스를 한 번에 소진하든 짧게 여러 번 소진하든 상관 없다. 4a와 4b를 합쳐 규칙을 재정의하자.

 

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

이런 자신에게 유리하도록 조작하는 것에 대한 방지책이 없다면 프로세스는 타임 슬라이스가 끝나기 직전에 입출력 명령어를 내릴 수 있어서 CPU 시간을 독점할 수 있다. 방지책이 마련되면 프로세스의 입출력 행동과 무관하게 아래 단계 큐로 천천히 이동하게 되어 CPU를 자기 몫 이상으로 사용할 수 없게 된다.

 

MLFQ 조정과 다른 쟁점들

MLFQ 스케줄링에는 여러 다른 쟁점들이 남아 있다. 필요한 변수들을 스케줄러가 어떻게 설정해야 하는지도 중요한 문제이다. 예를 들면 이런 것들이 있다.

 

• 몇 개의 큐가 존재하는가?

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

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

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

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

 

 

솔라리스의 MLFQ 구현

솔라리스는 프로세스의 우선순위가 일생 동안 어떻게 변하는지, 타임 슬라이스의 길이는 얼마인지, 작업의 우선 순위는 얼마나 자주 상향되는지를 결정하는 테이블을 제공한다. 관리자는 이 테이블을 수정하여 스케줄러의 동작 방식을 바꿀 수 있다. 

 

테이블의 기본 값은 큐의 개수는 60, 각 큐의 타임 슬라이스 크기는 가장 높은 우선순위 큐가 20msec에서 가장 낮은 우선수위 큐가 수백 msec까지 천천히 증가하고, 우선순위 상향 조정은 1초 정도마다 일어난다. 

 

그 외

스케줄러들은 다른 여러 기능을 제공한다. 예를 들어, 일부 스케줄러의 경우 가장 높은 우선순위를 운영체제 작업을 위해 예약해 둔다. 일반적인 사용자 작업은 시스템 내에서 가장 높은 우선순위를 얻을 수 없다. 일부 시스템은 사용자가 우선순위를 정하는 데 도움을 줄 수 있도록 허용한다. 예를 들어, 명령어 라인 도구인 nice를 사용하여 작업의 우선순위를 높이거나 낮출 수 있다. (작업의 실행 순서를 바꿀 수 있다.)

 

MLFQ : 요약

계속해서 살펴 보았던 MLFQ의 규칙을 보기 쉽도록 다시 적어 보겠다.

 

• 규칙 1 : 우선순위(A) > 우선순위(B) 이면 A실행. B는 실행되지 않음

• 규칙 2 : 우선순위(A) = 우선순위(B) 이면 A, B를 RR로 실행

• 규칙 3 : 작업이 도착하면 가장 높은 우선순위에서 시작

• 규칙 4 : 작업이 지정된 단계에서 배정받은 시간을 소진하면 (CPU 포기 횟수 무관) 우선순위 감소 (한단계 아래 큐로 이동)

• 규칙 5 : 일정 주기 S 마다 모든 작업을 가장 높은 우선순위 큐로 이동