개발 공부

손승열(Son Seungyeol)

2023년 6월 26일

[운영체제][OSTEP] 멀티 레벨 피드백 큐

작업의 실행 시간에 대한 선행 정보 없이 스케줄링하는 방법에 대해 공부해봅니다.

업데이트됨: 2023년 6월 29일 오후 08:58

🚪 들어가며

멀티 레벨 피드백 큐(Multi-level Feedback Queue, MLFQ)가 해결하고자 하는 기본적인 문제는 두 가지이다.

짧은 작업을 먼저 실행시켜 반환 시간을 최적화하고자 한다.
대화형 사용자에게 응답이 빠른 시스템이라는 느낌을 주도록 응답 시간을 최적화한다.

앞서서 살펴본 SJF, STCF, RR 등의 스케줄러를 살펴볼 때는 스케줄러가 작업의 실행 시간에 대한 선행 정보를 알고 있다고 가정했었지만, 이는 현실적으로는 상당히 비현실적인 이야기이다.

멀티 레벨 피드백 큐를 통해 작업의 실행 시간에 대한 선행 정보가 없을 때, 응답 시간과 반환 시간을 모두 최소화하는 스케줄러를 어떻게 설계할 수 있는지 알아보자!

1️⃣ MLFQ: 기본 규칙

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

MLFQ는 실행할 프로세스를 결정하기 위해 우선순위를 사용한다.
➡️ 높은 우선순위 큐에 존재하는 작업이 선택됨.

동일한 큐 안에 있는 작업들은 같은 우선순위를 가진다.
➡️ 이러한 작업들 사이에서는 RR 스케줄링 알고리즘이 사용됨.

MLFQ 스케줄링의 핵심은 우선순위를 정하는 방식
➡️ 각 작업의 특성에 따라 동적으로 우선순위를 부여함.
예시1) 어떤 작업이 키보드 입력을 기다리며 반복적으로 CPU를 양보 ➡️ 높은 우선순위 유지
예시2) 한 작업이 긴 시간 동안 CPU를 집중적으로 사용 ➡️ 우선순위가 낮아짐.

MLFQ의 두 가지 기본 규칙

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

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

2️⃣ 시도 1: 우선순위의 변경

작업의 우선순위를 변경하는 것 = 작업이 존재할 큐를 결정하는 것

시스템상에는 "짧은 실행 시간 & CPU 자주 양보"의 특성을 갖는 대화형 작업과 "많은 CPU 시간 요구 & 응답 시간 중요X"의 특성을 갖는 작업 등 다양한 작업이 혼재되어 있음.

우선순위 조정 알고리즘을 위한 첫 번째 시도는 위 MLFQ의 규칙에서 새로운 규칙들을 더하여 이루어진다.
이를 아래의 예시와 함께 살펴보자.

[High Priority] Q8 → [A] → [B]
                Q6
                Q5
                Q4 → [C]
                Q3
                Q2
[Low Priority]  Q1 → [D]

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

[규칙 4a] 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다.(한 단계 아래 큐)

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

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

다음 예시와 함께 긴 실행 시간을 가진 작업 A의 우선순위가 어떻게 변하는지 살펴보자.
스케줄러는 총 세 개의 큐로 이루어져있고, 타임 슬라이스는 10시간 단위라고 가정하자.

Q2 [ A ]
Q1      [ A ]
Q0           [          A          ]
   |   |    |                      |
   0   10   20                     100 ...
시간의 흐름 →

작업은 먼저 최고 우선순위(Q2)로 진입한다.

10 크기의 타임 슬라이스가 하나 지난 후 스케줄러는 A의 우선순위를 한 단계 낮추어 Q1으로 이동시킨다.

다시 하나의 타임 슬라이스가 지난 후 작업은 가장 낮은 우선순위의 큐인 Q0로 이동하여 계속 머무르게 된다.

예 2: 짧은 작업과 긴 작업이 함께 있는 경우

다음 예시와 함께 MLFQ가 어떻게 SJF와 근접하게 동작하는지 살펴보자.
예 1과 동일한 환경에서 이미 실행 중인 CPU 위주의 긴 작업 A와 짧은 대화형 작업 B가 있다고 가정하자.

Q2          [ B ]
Q1               [ B ]
Q0 [   A   ]          [          A          ]
   |       |    |    |                      |
   0       20   30   40                     100 ...
시간의 흐름 →

이미 오래 실행해 온 A는 가장 낮은 우선순위 큐에서 실행되고 있다.

B는 T = 20에 시스템에 도착 후 가장 높은 우선순위 큐에 놓여진다.

B는 실행 시간이 20 크기이므로 두 번의 타임 슬라이스를 소모 후 가장 낮은 우선순위의 큐에 놓이기 전에 종료된다.

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

💡 여기서 알 수 있는 MLFQ 알고리즘의 주요 목표!

스케줄러는 작업의 실행 시간을 알 수 없음.
➡️ 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여

짧은 작업이 아니라면 천천히 아래 큐로 이동
➡️ 이러한 방식으로 MLFQ는 SJF와 근접하게 동작

예 3: I/O가 있는 작업과 CPU 위주의 작업이 함께 있는 경우

[규칙 4b] "타임 슬라이스 소진 전 CPU 양도 시 우선순위 유지"의 의도
➡️ I/O를 자주 수행(대화형 작업)하는 경우 타임 슬라이스가 종료되기 전에 CPU를 양도하므로 대화형 작업이 계속 빨리 실행됨.

다음의 예시와 함께 이를 살펴보자.
이번에도 예 1과 동일한 환경이라고 가정한다.

Q2 [B]       [B]       [B]       [B]       [B]
Q1          
Q0    [  A  ]   [  A  ]   [  A  ]   [  A  ]   [  A  ]
   | |      |  |      |  |      |  |      |  |      |
   0 1      11 12     22 23     33 34     44 45     55 ...
시간의 흐름 →

B는 대화형 작업으로서 I/O 수행 전 1 크기 동안만 실행된다.

A는 긴 배치형 작업으로 B와 CPU를 사용하기 위해 경쟁한다.

B는 CPU를 계속 양도하므로 MLFQ 방식은 B를 가장 높은 우선순위로 유지한다.

현재 MLFQ의 문제점

[문제점 1] 기아 상태(starvation)가 발생할 수 있다.

시스템에 너무 많은 대화형 작업이 존재하는 경우
➡️ 긴 실행 시간 작업은 CPU 시간을 할당받지 못할 수 있음.(우선 순위가 낮으므로)

이를 해결하기 위해선 우선순위 상향을 해주어야 하는데 다음 예시와 함께 살펴보자.

우선순위 상향이 없는 경우

Q2 [  A  ]                    [ B ][ C ][ B ][ C ][ B ][ C ]
Q1        [  A  ]
Q0               [     A     ]
   |     |      |            |    |    |    |    |    |    |
   0     10     20           50   55   60   65   70   75   80 ...
시간의 흐름 →

우선순위 상향이 있는 경우(50시간 단위 마다 Boost)

Q2 [A]          [A]          [A][B][C][B][C][A][B][C][B][C]
Q1    [A]          [A]
Q0       [  A  ]      [  A  ]
   | |  |      |  |  |      |              |              |
   0 10 20     50 60 70     100            150            200 ...
시간의 흐름 →

[문제점 2] 사용자가 스케줄러를 자신에게 유리하게 동작하도록 재작성할 수 있다.

스케줄러를 유리하게 동작시킴 = 지정된 몫보다 더 많은 시간을 할당하도록 스케줄러를 속임.

지금까지 설명한 MLFQ 알고리즘은 다음과 같은 공격에 취약
타임슬라이스가 끝나기 전에 아무 파일을 대상으로 I/O 요청을 내려 CPU를 양도
➡️ 같은 큐에 머무름으로써 더 높은 퍼센트의 CPU 시간을 얻게 됨.

예시) 타임 슬라이스의 99%를 실행하고 CPU 양도 ➡️ CPU를 거의 독점

또한 프로그램은 시간 흐름에 따라 특성이 변할 수 있음.

현재 MLFQ 방식으로는 CPU 위주 작업이 대화형 작업으로 바뀐 경우 다른 대화형 작업들과 같은 대우를 받을 수 없음.

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

기아 문제의 방지 ➡️ 주기적으로 모든 작업의 우선순위를 상향 조정(boost)

다양한 방법이 존재하지만 모두 최상위 큐로 보내는 간단한 방법을 사용해보자.

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

이 새로운 규칙은 두 가지 문제를 한 번에 해결함.

[1] 프로세스는 기아 상태에 놓이지 않는다는 것을 보장받는다.
➡️ 작업이 최상위 큐에 존재하는 동안 다른 높은 우선순위 작업들과 RR 방식으로 CPU를 공유

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

그렇다면 S 값을 얼마로 해야 하는가?

일종의 부두 상수(voo-doo constants): 값을 정확하게 결정하기가 어려움.

너무 크면 긴 실행 시간을 가진 작업은 기아 상태에 놓일 수 있고 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없게 됨.

Ousterhout's Law: 디폴트 값으로 가득 찬 설정 파일을 사용하되, 정확히 동작하지 않을 때 풍부한 경험의 관리자가 조정 가능하지만 대부분 있는 그대로 사용되며 디폴트 값이 현장에서 잘 작동하기를 바랄 뿐이다.

4️⃣ 시도 3: 더 나은 시간 측정

아직 [문제점 2]인 "사용자가 스케줄러를 자신에게 유리하게 동작하도록 재작성"을 해결해야 한다.

[문제점 2]의 원인은 [규칙 4a]와 [규칙 4b]이다.(타임 슬라이스가 끝나기 전 CPU 양보 시 우선 순위 유지)

해결책은 MLFQ의 각 단계에서 CPU 총 사용 시간을 측정하는 것이다. 다음과 같은 과정으로 진행한다.

현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장
프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등

이를 위해 다음과 같이 [규칙 4a]와 [규칙 4b]를 합쳐 하나의 규칙으로 재정의한다.

[규칙 4] 주어진 단계에서 시간 할당량을 소진하면(CPU 양도 횟수와 상관X), 우선순위는 낮아진다.

다음의 두 예시를 통해 [규칙 4]가 [문제점 2]를 해결하는 방법을 살펴보자.

[규칙 4a]와 [규칙 4b]가 적용된 경우(조작에 취약)

Q2    [    B    ]   [    B    ]   [    B    ]   [   B   ]
Q1          
Q0 [A]           [A]           [A]           [A]       
시간의 흐름 →

[규칙 4]가 적용된 경우(조작에 강력)

Q2 [  B  ]   [B]
Q1              [  B  ]   [B]
Q0        [A]          [A]   [  A  ][  B  ][A][B]
시간의 흐름 →

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

5️⃣ MLFQ 조정과 다른 쟁점들

다음과 같은 쟁점들이 아직 남아 있다.

[쟁점 1] 몇 개의 큐가 존재해야 하는가?
[쟁점 2] 큐당 타임 슬라이스의 크기는 얼마로 해야 하는가?
[쟁점 3] 기아를 피하고 변화된 행동을 반영하기 위해 얼마나 자주 우선순위가 상향 조정되어야 하는가?

워크로드에 대해 충분히 경험하고 계속 조정해 나가면서 균형점을 찾아야 함.

예를 들어 [쟁점 2]의 경우 대부분의 MLFQ 기법들은 큐 별로 타임 슬라이스를 변경할 수 있기 때문에 다음과 같은 양상을 띄고 있다.

높은 우선순위의 큐: 짧은 타임 슬라이스가 주어짐.
- 대화형 작업으로 구성 ➡️ 작업들을 빠르게 교체하는 것이 의미있음.
낮은 우선순위의 큐: 긴 타임 슬라이스가 주어짐.
- CPU 위주의 오래 실행되는 작업으로 구성

각종 운영체제들의 MLFQ 조정

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

FreeBSD의 스케줄러(버전 4.3)는 작업의 현재 우선순위를 계산하기 위하여 프로세스가 사용한 CPU 시간을 기초로 한 공식을 사용한다.(감쇠-사용(decay-usage) 알고리즘)

스케줄러가 제공하는 다른 기능들

일부 스케줄러의 경우 가장 높은 우선순위를 운영체제 작업을 위해 예약
일부 시스템은 사용자가 우선순위를 정하는 데 도움을 줄 수 있도록 허용

🧺 MLFQ 내용 정리

MLFQ 규칙 다시 보기

[규칙 1] Priority(A) > Priority(B) 이면, A가 실행된다.(B는 실행X)
[규칙 2] Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.
[규칙 3] 작업이 시스템에 진입하면, 우선순위가 가장 높은 큐에 놓여진다.
[규칙 4] 주어진 단계에서 시간 할당량을 소진하면(CPU 양도 횟수와 상관X), 우선순위는 낮아진다.
[규칙 5] 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

MLFQ 특징 다시 보기

작업의 특성에 대한 정보 없이 작업의 실행 관찰 후 우선순위를 지정
반환 시간과 응답 시간을 모두 최적화
대화형 작업(짧은 실행)에 대해 전반적으로 우수한 성능 제공(SJF/STCF와 유사)
CPU 위주 작업(긴 실행)에 대해 공정한 실행과 작업이 조금이라도 진행되도록 조치
많은 시스템이 기본 스케줄러로 MLFQ를 사용(Solaris, Windows NT 등)

📚 참고 문헌

Operating Systems: Three Easy Pieces ― 8: Scheduling: The Multi-Level Feedback Queue

운영체제 아주 쉬운 세 가지 이야기 ― 11: 스케줄링 : 멀티 레벨 피드백 큐