04-2. Multi-Level-Feedback 스케줄링

멀티 레벨 피드백 큐(Multi-level Feedback Queue, MLFQ)

복습¶

선점형 스케줄링과 비선점형 스케줄링¶

선점형 스케줄링 방식은 실행 상태에 있는 작업을 중단시키고 새로운 작업 실행 가능, 비선점형 스케줄링은 실행 상태에 있는 작업이 완료될 때까지 다른 작업이 불가능하다

선점형은 시분할 방식 스케줄러에서 사용
비선점형은 일괄 방식 스케줄러에서 사용

장점: 선점형은 프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템이 적합하다.
비선점형은 CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다.

단점: 선점형은 문맥 교환의 오버헤드가 많고, 비선점형은 기다리는 프로세스가 많아 처리율이 떨어진다.
중요도 측면: 선전형은 중요도가 높다, 반면 비선점형은 낮다.

비선점형 스케줄링을 사용하는 알고리즘¶

• FCFS(First Come First Served)스케줄링: 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식, 선입선출 스케줄링이라고도 함. 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스가 실행할 수 있다. 게다가 큐가 하나라 모든 프로세스는 우선순위가 동일하다.
• SJF(Shortest Job First) 스케줄링:
  준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식(최단 작업 우선 스케줄링)
  SPF(Shortest Process First) 또는 최단 프로세스 우선 스케줄링 이라고도 함

장점: 작은 작업을 먼저 실행하기 때문에 시스템의 효율성이 좋아진다. 먼저 도착한 큰 작업으로 인해 작은 작업이 지연되는 FCFS 스케줄링보다 평균 대기 시간이 줄어들어 시스템의 효율성이 높아지는 것
단점:

1. 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
   현대의 운영체제에서는 프로셋의 작업 길이를 추정하는 것이 어렵기 때문
2. 공평하지 못하다.
   프로세스 P2는 P3보다 준비 큐에 먼저 도착하지만 가장 나중에 실행되었다.
   만약 프로세스 P3같은 작은 작업이 계속 준비 큐에 들어오면 프로세스 P2의 작업이 계속 연기되는데 이를 아사 (starvation) 현상 또는 무한 봉쇄 (infinite blocking) 현상이라고 한다. 작업 시간이 길다는 이유만으로 계속 뒤로 밀린다면 공평성이 현저히 떨어진다.

• HRN(Highest Response Ratio Next):
  HRN(Highest Response Ratio Next) 스케줄링은 SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘, 최고 응답률 우선 스케줄링이라고도 한다.
  서비스를 받기 위해 기다린 시간과 CPU 사용시간을 고려하여 스케줄링한다.
  프로세스의 우선순위를 결정하는 기준은 아래와 같다.

선점형 스케줄링을 사용하는 알고리즘¶

Round Robin 스케줄링:

• 라운드 로빈 방식(Round Robin, RR):프로세스가 할당받은 시간(타임 슬라이스)동안 작업하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 다음 자기 차례가 올 때까지 기다리는 선점형 스케줄링 알고리즘
  한 프로세스가 할당받은 타임 슬라이스 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식. 선점형 알고리즘 중 가장 단순하고 대표적인 방식. 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행. 우선순위가 적용되지 않은 가장 단순한 선점형 스케줄링 방식

FCFS 스케줄링과 유사한데, 차이점은 각 프로세스마다 CPU를 사용할 수 있는 최대 시간, 즉 타임 슬라이스가 있다는 것. 프로세스는 자신에게 주어진 타임 슬라이스 동안만 작업할 수 있으며, 작업이 다 끝나지 않으면 큐의 뒤쪽 tail에 다시 삽입된다.

타임 슬라이스가 큰 경우

타임 슬라이스가 너무 크면 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보인다. 이 경우 FCFS 스케줄링과 다를 게 없는데, 실제로 라운드 로빈 스케줄링에서 타임 슬라이스가 무한대이면 FCFS 스케줄링이 된다.
타임 슬라이스가 1,000밀리초(1초)인 시스템에서 비디오 플레이어와 워드프로세서가 동시에 실행된다고 가정했을 떄, 비디오 플레이어 1초, 워드프로세서 1초씩 두 프로그램이 1초 간격으로 실행되어 비디오가 끊겨 보이고 워드프로세서의 반응 속도가 매우 느릴 것이다.

타임 슬라이스가 작은 경우

타임 슬라이스를 1밀리초와 같이 매우 작은 값으로 설정하면 사용자는 여러 프로그램이 동시에 실행되는 것처럼 느낄 것이다.
그러나 타임 슬라이스를 너무 작게 설정하면 시스템의 전반적인 성능이 떨어진다. 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생한다.

• SRT(Shortest Remaining Time) 스케줄링: 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아있는 작업 시간이 가장 적은 프로세스를 선택한다. 하지만 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가된다. 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사현상이 일어날 수 있다.

• 다단계 큐(Multilevel Queue) 스케줄링: 우선순위에 따라 준비 큐를 여러개 사용하는 방식. 우선순위는 고정형 우선순위를 사용하며, 상단의 큐에 잇는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다. 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있을뿐더러 우선 순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수도 있다.

• 다단계 피드백 큐 스케줄링: 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다. 또한 우선순위에 따라 타임 슬라이스의 크기가 다르다. 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커진다. 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 우선순위가 낮은 큐의 타임 슬라이스를 크게 설정한다.

멀티 레벨 피드백 큐 (MLFQ: Multilevel Feedback queue) 스케줄러¶

멀티 레벨 피드백 큐 (MLFQ) 스케줄러는 Compatible Time-Sharing System(CTSS)에 사용되며 Corbato 등에 의해 1962년에 최초로 소개되었다.

우선순위에 따라 준비 큐를 여러 개 사용하며, 프로세스가 CPU를 사용한 후 우선순위가 낮아 진다.
다단계 피드백 큐 스케줄링에서 우선순위가 낮아질수록 타임 슬라이스의 크기는 프로세스의 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커진다.
이 스케줄러는 수년 동안 다듬어져 일부 현대 시스템에까지 발전되었다.

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

첫째, 짧은 작업을 먼저 실행시켜 반환 시간을 최적화하고자 한다.
SJF 나 STCF 같은 알고리즘은 작업의 실행 시간 정보를 필요로 하지만, 실제로 운영체제는 이 실행 시간을 미리 알 수 없다.

둘째, MLFQ는 대화형 사용자 (즉, 화면 앞에 앉아 바라보면서 프로세스의 종료를 기다리는 사용자)에게 응답이 빠른 시스템이라는 느낌을 주고 싶었기 때문에 응답 시간을 최적화한다.

RR과 같은 알고리즘은 응답 시간을 단축시키지만 반환 시간은 거의 최악이다.

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

핵심 질문 : 정보 없이 스케줄 하는 방법은 무엇인가
작업의 실행 시간에 대한 선행 정보 없이 대화형 작업의 응답 시간을 최소화하고
동시에 반환 시간을 최소화하는 스케줄러를 어떻게 설계할 수 있는가?

MLFQ: 기본 규칙¶

팁 : 역사로부터 배우다
멀티 레벨 피드백 큐는 미래를 예측하기 위해 과거의 경험을 활용하는 훌륭한 예이다.
이러한 접근 방식은 운영체제 (하드웨어 분기 예측기와 캐시 알고리즘을 포함한 컴퓨터
과학의 다른 많은 분야에서도) 분야에서 흔히 사용된다.
이러한 방식은 작업이 단계별로 진행되어 예측 가능할 때 잘 동작한다.

MLFQ는 여러 개의 큐로 구성된다.
각각의 큐는 각각 다른 우선순위(priority level)가 배정된다.

실행 준비가 된 프로세스는 이 중 하나의 큐에 존재한다.
MLFQ는 실행할 프로세스를 결정하기 위하여 우선순위를 사용한다.

높은 우선순위를 가진 작업이, 즉 높은 우선순위 큐에 존재하는 작업이 선택된다.
큐에 둘 이상의 작업이 존재할 수 있다. 이들은 모두 같은 우선순위를 가진다.
이 작업들 사이에서는 라운드 로빈 (Round-Robin, RR) 스케줄링 알고리즘이 사용된다. MLFQ 스케줄링의 핵심은 우선순위를 정하는 방식이다.

MLFQ는 각 작업에 고정된 우선순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다.
MLFQ는 작업이 진행되는 동안 해당 작업의 정보를 얻고, 이 정보를 이용하여 미래 행동을 예측한다.

Example:
어떤 작업이 키보드 입력을 기다리며 반복적으로 CPU를 양보 → 우선순위를 높게 유지
한 작업이 긴 시간 동안 CPU를 집중적으로 사용 → 우선순위를 낮춘다.

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

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

임의의 시간에 큐의 모양은 그림 11.1과 같다.

그림에서 두 작업 (A와 B)이 가장 높은 우선순위에 존재하고, C는 중간, D는 가장 낮은 우선순위 큐에 존재한다.

우리가 알고 있는 MLFQ의 동작을 고려하면 스케줄러는 가장 높은 우선순위의 큐의 A와 B를 번갈아 실행할 것이다. 작업 C와 D는 실행되지 않는다.

정적인 스냅 사진만으로는 MLFQ가 어떻게 동작하는지 알 수 없다.
MLFQ가 작업의 우선순위를 어떻게 바꿀 것인지 결정해야 한다.

[1] 우선순위 변화¶

작업 우선순위가 시간에 따라 어떻게 변화하는지 알아보자.
작업의 우선순위를 변경하는 것은 작업이 존재할 큐를 결정하는 것과 마찬가지다.

이를 위해서 우리는 워크로드의 특성을 반영해야 한다.

짧은 실행 시간을 갖는 CPU를 자주 양보하는 대화형 작업과 많은 CPU 시간을 요구하지만 응답 시간은 중요하지 않은 긴 실행 시간의 CPU 위주 작업이 혼재되어 있다.

이를 해결하기 위해 MLFQ priority 는 다음과 같은 규칙을 도입하였다.

• 규칙 3: 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓여진다.
• 규칙 4a: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
• 규칙 4b: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

이때 MLFQ 는 SJF (준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당)와 동작 방식이 비슷하다.

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

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

그림 11.2에서는 타임 슬라이스가 10ms인 세 개의 큐로 이루어진 스케줄러이다.
여기에서 시간이 지남에 따라 작업의 우선순위가 어떻게 변하는지 볼 수 있다.

변화는 다음과 같다.

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

이후에는 Q0에 계속 머무르게 된다.

예 2: 짧은 작업과 함께 할 경우¶

좀 더 복잡한 예를 살펴보자. MLFQ가 어떻게 SJF에 근접할 수 있는지 이해하기 바란다.

이 예에서는 2개의 작업이 존재한다.

A, B 작업을 이렇게 가정 해보자.
time slice = 10ms,

• A 작업: 오래 실행되는 CPU 위주 작업 | 얼마 동안 이미 실행해 온 상태
• B 작업: 짧은 대화형 작업 | 이제 도착한 상태 (20 ms runtime)
  B는 T = 100일때 도착한다.

그림 11.3은 이 시나리오의 결과를 보인다.

다른 오래 실행되는 CPU 위주 작업들처럼 A(검은색)는 가장 낮은 우선순위 큐에서 실행되고 있다.
B(회색)는 T = 100에 시스템에 도착하고 가장 높은 우선순위 큐에 놓여진다.

실행 시간이 짧기 때문에 (단지 20 ms), 두 번의 타임 슬라이스를 소모하면 B는 바닥의 큐에 도착하기 전에 종료한다.

그런 후에 A는 낮은 우선순위에서 실행을 재개한다.

이 예에서 이 알고리즘의 주요 목표를 알 수 있다.
스케줄러는 작업이 짧은 작업인지 긴 작업인지 알 수 없기 때문에 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여 한다.

짧은 작업이면 빨리 실행되고 바로 종료할 것이다.

짧은 작업이 아니라면 천천히 아래 큐로 이동하게 되고 스스로 긴 배치형 작업이라는 것을 증명하게 된다.

이러한 방식으로 MLFQ는 SJF를 근사하여 수행할 수 있다.

예 3: 입출력 작업에 대해서는 어떻게 할 것인가?¶

다음으로 입출력 작업을 수행하는 예를 살펴보자.

규칙 4b(규칙 4b: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지)가 말하는 것처럼, 프로세스가 타임 슬라이스를 소진하기 전에 프로세서를 양도하면 같은 우선순위를 유지하게 한다.

이 규칙의 의도는 간단하다.

대화형 작업이 키보드나 마우스로부터 사용자 입력을 대기하며 자주 입출력을 수행하면 타임 슬라이스가 종료되기 전에 CPU를 양도하게 될 것이다.
그런 경우 동일한 우선순위를 유지하게 하는 것이다.

그림 11.4는 이 규칙이 동작하는 예를 보이고 있다.

• 작업 A(CPU-집중 작업): 긴 배치형 작업으로 B 와 CPU를 사용하기 위하여 경쟁한다.
• 작업 B(입출력-집중 작업): 대화형 작업으로서 입출력을 수행하기 전에 1 msec 동안만 실행

B는 CPU를 계속해서 양도하기 때문에 MLFQ 방식은 B를 가장 높은 우선순위로 유지한다. B가 대화형 작업이라면 MLFQ는 대화형 작업을 빨리 실행시킨다는 목표에 더 근접하게 된다.

즉, CPU를 긴 작업들과 짧은 작업들 사이에 잘 공유하고, 입출력중점 대화형 작업을 빨리 실행시킨다.

현재 MLFQ의 문제점¶

• 기아 상태(starvation)
  시스템에 너무 많은 대화형 작업이 존재하면 그들이 모든 CPU 시간을 소모하게 될 것이고 따라서 긴 실행 시간 작업은 CPU 시간을 할당받지 못할 것이다.

• 스케줄러 정책에 따라 프로그램을 유리하게 맞춰서 작성하기
  스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있다.
  스케줄러를 자신에게 유리하게 동작시킨다는 것은 일반적으로 스케줄러를 속여서 지정된 몫보다 더 많은 시간을 할당하도록 할 수 있다.

예를 들어서 다음과 같은 공격에 취약하다.
타임 슬라이스가 끝나기 전에 아무 파일을 대상으로 입출력 요청을 내려 CPU를 양도한다.

그렇게 하면 같은 큐에 머무를 수 있고 따라서 더 높은 퍼센트의 CPU 시간을 얻게 된다.
제대로 된다면, 예를 들어 타임 슬라이스의 99%를 실행하고 CPU를 양도하게 되면 CPU를 독점할 수 있다.

• 프로그램은 시간 흐름에 따라 특성이 변할 수 있다.
  CPU 위주 작업이 대화형 작업으로 바뀔 수 있다.

[2] 우선순위의 상향 조정¶

규칙을 보완하여 기아 문제를 방지할 수 있는지 살펴보자.

CPU 위주 작업이 조금이라도 진행하는 것을 보장하기 위해서 무엇을 할 수 있는가?

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

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

새 규칙은 두 가지 문제를 한 번에 해결한다.

첫째, 프로세스는 굶지 않는다는 것을 보장받는다. 최상위 큐에 존재하는 동안 작업은 다른 높은 우선순위 작업들과 라운드 로빈 방식으로 CPU를 공유하게 되고 서비스를 받게 된다.

둘째, CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우 우선순위 상향을 통해 스케줄러가 변경된 특성에 적합한 스케줄링 방법을 적용한다.

예를 들어 보자. 긴 실행 시간을 가진 작업이 두 개의 대화형 작업과 CPU를 두고 경쟁할 때의 행동을 보여주는 시나리오다.

이 두 개의 그래프가 그림 11.5에 나와 있다.

왼쪽 그래프는 우선순위 상향이 없는 경우를 보이고 있다. 긴 실행 시간 작업은 두 개의 짧은 작업이 도착한 이후에는 실행되지 못한다.

오른쪽 그래프는 50 msec 마다 우선순위 상향이 일어난다.

긴 실행 시간 작업도 꾸준히 진행된다는 것을 보장할 수 있으며, 50 msec 마다 상향되고 따라서 주기적으로 실행된다.

물론 S 값의 결정이 필요하다. S 를 얼마로 해야 하는가?

존경받는 시스템 연구자인 John Ousterhout는 이러한 종류의 값을 부두 상수(voo-doo constants)라고 불렀다.
이러한 값을 정확하게 결정하기 위해서는 흑마술이 필요한 것처럼 보이기 때문이다. (경험이 중요하다.)

너무 크면 긴 실행 시간을 가진 작업은 굶을 수 있으며 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없게 된다.

[3] 더 나은 시간 측정¶

Recall: 규칙들
- 규칙 1: Priority(A) > Priority(B) 이면, A가 실행된다 (B는 실행되지 않는다).
- 규칙 2: Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.
- 규칙 3: 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓여진다.
- 규칙 4a: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
- 규칙 4b: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.
- 규칙 5: 일정 기간 S 가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

해결해야 할 문제가 하나 더 있다. 스케줄러를 자신에게 유리하게 동작시키는 것을 어떻게 막을 수 있는가?

이러한 일을 가능하게 만든 주범은 규칙 4a와 4b이다.
두 규칙은 작업이 타임 슬라이스가 끝나기 전에 CPU를 양보하여 우선 순위를 유지가 가능하게 한다. 우리는 무엇을 해야 하는가?

여기서의 해결책은 MLFQ의 각 단계에서 CPU 총 사용 시간을 측정하는 것이다.

스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장한다.
프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등된다.
타임 슬라이스를 한 번에 소진하든 짧게 여러 번 소진하든 상관 없다.

규칙 4a와 4b를 합쳐 하나의 규칙으로 재정의한다.

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

예를 살펴보도록 하자.

그림 11.6은 워크로드가 스케줄러를 자신에게 유리하게 동작시키려고 할 때 예전 규칙 4a와 4b일 때의 행동과 (왼쪽) 새로운 조작 방지 규칙 4일 때의 행동 양식을 보이고 있다.

이런 자신에게 유리하도록 조작하는 데 대한 방지책이 없다면 프로세스는 타임 슬라이스가 끝나기 직전에 입출력 명령어을 내릴 수 있어서 CPU 시간을 독점할 수 있다.

방지책이 마련되면 프로세스의 입출력 행동과 무관하게 아래 단계 큐로 천천히 이동하게 되어 CPU를 자기 몫 이상으로 사용할 수 없게 된다.

MLFQ 조정과 다른 쟁점들¶

팁 : 부두 상수 피하기 (Ousterhout’s Law): 기본 값 사용
가능하다면 부두 상수를 피하는 것이 좋은 생각이다.
그러나 앞의 예처럼, 피할 수 없는 경우가 더 자주 일어난다. 더 좋은 값을 찾는 방법도 쉽지는 않다.
흔한 결과: 디폴트 값으로 가득 찬 설정 파일. 설정 파일의 값들은 무언가 정확히 동작하지 않을 때 풍부한 경험의 관리자가 조정 가능하다.
그러나 이 값은 대부분 있는 그대로 사용되며 디폴트 값이 현장에서 잘 작동하기를 바랄 뿐이다. 이 팁은 오래된 운영체제 교수 John Ousterhout에 의해 알려졌기 때문에 Ousterhout’s Law라고 부른다.

MLFQ 스케줄링에는 여러 다른 쟁점들이 남아 있다.

필요한 변수들을 스케줄러가 어떻게 설정해야 하는지도 중요한 문제다.

예를 들어, 몇 개의 큐가 존재해야 하는가?
큐당 타임 슬라이스의 크기는 얼마로 해야 하는가?
기아 현상을 피하고 변화된 행동을 반영하기 위하여 얼마나 자주 우선순위가 상향 조정되어야 하는가?
이러한 문제들은 워크로드에 대해 충분히 경험하고 계속 조정해 나가면서 균형점을 찾아야 한다.

대부분의 MLFQ 기법들은 큐 별로 타임 슬라이스를 변경할 수 있다.

• 우선순위가 높은 큐는 보통 짧은 타임 슬라이스가 주어진다.
  이 큐는 대화형 작업으로 구성되고, 결국 이 작업들을 빠르게 교체하는 것은 의미가 있다.
  (예, 10 msec 이하)

• 낮은 우선순위 큐는 반대로 CPU-중심의 오래 실행되는 작업들을 포함한다.
  긴 타임 슬라이스(예, 수백 msec)가 적합하다.

그림 11.7은 가장 높은 우선순위 큐는 10 ms, 중간 큐는 20 ms, 가장 낮은 큐는 40 ms의 스케줄러에서 두 개의 작업이 실행되는 모양을 보인다.

The Solaris MLFQ Implementation¶

Solaris의 MLFQ (=시분할 스케줄링 클래스, TS)는 설정이 쉽다.

Solaris 는 프로세스의 우선순위가 일생 동안 어떻게 변하는지, 타임 슬라이스의 길이는 얼마인지, 작업의 우선순위는 얼마나 자주 상향되는지를 결정하는 테이블을 제공한다.

관리자는 이 테이블을 수정하여 스케줄러의 동작 방식을 바꿀 수 있다.

• 큐의 개수: 60개
• 각 큐의 타임 슬라이스 크기
  • 가장 높은 우선순위 큐가 20 msec
  • 가장 낮은 우선순위 큐가 수백 msec까지 천천히 증가
• 우선순위 상향 조정은 1초 정도마다 일어난다.

다른 MLFQ 스케줄러는 테이블이나 이 장에서 설명한 정확한 규칙 같은 것은 사용하지 않는다.
수학 공식을 사용하여 우선순위를 조정한다.

FreeBSD Scheduler (버전 4.3)¶

예를 들어, FreeBSD의 스케줄러 (버전 4.3)는 작업의 현재 우선순위를 계산하기 위하여 큐 대신 프로세스가 사용한 CPU 시간을 기초로 한 공식을 사용한다.

• How much CPU a process has used.
• Boost priority by decay.
• Take the advice from the user. (nice)

CPU 사용은 시간이 지남에 따라 감쇠되어 이 장에서 설명한 방식과는 다른 방식으로 우선순위 상향을 제공한다.

마지막으로, 스케줄러들은 다른 여러 기능을 제공한다.

예를 들어, 일부 스케줄러의 경우 가장 높은 우선순위를 운영체제 작업을 위해 예약해 둔다.

일반적인 사용자 작업은 시스템 내에서 가장 높은 우선순위를 얻을 수 없다.

일부 시스템은 사용자가 우선순위를 정하는 데 도움을 줄 수 있도록 허용한다.

예를 들어, 명령어 라인 도구인 nice를 사용하여 작업의 우선순위를 높이거나 낮출 수 있다. 작업의 실행 순서를 바꿀 수 있다.

팁 : 가능하면 조언을 이용하시오
운영체제 시스템이 모든 프로세스에게 어떤 것이 최선인지 알 수는 없다. 사용자 또는 관리자가 힌트를 전달할 수 있는 인터페이스를 제공하는 것이 도움이 된다.

우리는 그러한 힌트(hint)를 조언(advice)이라고 부른다.
운영체제가 힌트를 반드시 고려할 필요는 없지만 더 나은 결정을 내리는 데 힌트가 도움이 될 수는 있기 때문이다.
이러한 힌트는 스케줄러 (예, nice), 메모리 관리자 (예, madvise), 파일 시스템 (예, 제공 정보에 기초한 선반입과 캐싱) 등을 포함한 운영체제의 여러 부분에서 유용하다.

MLFQ: 요약¶

알고리즘은 멀티 레벨 큐를 가지고 있으며, 지정된 작업의 우선순위를 정하기 위하여 피드백을 사용한다. 과거에 보여준 행동이 우선순위 지정의 지침이 된다.

최종적인 규칙:

• 규칙 1 : 우선순위 (A)> 우선순위 (B) 일 경우, A가 실행, B는 실행되지 않는다.
• 규칙 2 : 우선순위 (A) = 우선순위 (B), A와 B는 RR 방식으로 실행된다.
• 규칙 3 : 작업이 시스템에 들어가면 최상위 큐에 배치된다.
• 규칙 4 : 작업이 지정된 단계에서 배정받은 시간을 소진하면
  (CPU를 포기한 횟수와 상관없이), 작업의 우선순위는 감소한다 (즉, 한 단계 아래 큐로 이동한다).
• 규칙 5 : 일정 주기 S 가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

MLFQ는 작업의 특성에 대한 정보 없이, 작업의 실행을 관찰한 후 그에 따라 우선순위를 지정할 수 있다.

또한 MLFQ는 반환 시간과 응답 시간을 모두 최적화한다.
짧게 실행되는 대화형 작업에 대해서는 우수한 전반적인 성능을 제공한다 (SJF/ STCF와 유사).
오래 실행되는 CPU-집중 워크로드에 대해서는 공정하게 실행하고 조금이라도 진행되도록 한다.

이런 이유로 BSD Unix와 여기서 파생된 다양한 운영체제 Solaris, Windows NT 및 이후 Windows 운영체제를 포함한 많은 시스템이 기본 스케줄러로 MLFQ를 사용한다.

• 참고 자료
  쉽게 배우는 운영체제_ch4_CPU 스케줄링