[운영체제 아주 쉬운 세 가지 이야기 - Virtualization] 8. Multi-CPU Scheduling
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
이 장에서는 멀티 레벨 피드백 큐(Multi-Level Feedback Queue, MLFQ)로 알려진 가장 유명한 스케줄링 기법에 대해 논의한다. MLFQ 스케줄러는 1962년년에 최초로 소개되었고, 최고의 영예인 Turing Award를 안았다. 이 스케줄러는 수년 동안 다듬어져 일부 현대 시스템에까지 발전되었다.
MLFQ가 해결하려고 하는 기본적은 문제는 두 가지이다.
- 짧은 작업을 먼저 실행시켜 반환 시간을 최적화하고자 한다.
SJF나 STCF 같은 알고리즘은 작업의 실행 시간 정보를 필요로 하지만, 불행히도 운영체제는 이 실행 시간을 미리 알 수 없다. - MLFQ는 대화형 사용자 (즉, 화면 앞에 앉아 바라보면서 프로세스의 종료를 기다리는 사용자)에게 응답이 빠른 시스템이라는 느낌을 주고 싶었기 때문에 응답 시간을 최적화한다.
RR과 같은 알고리즘은 응답 시간을 단축시키지만 반환 시간은 거의 최악이다.
그렇기에 우리의 문제는 다음과 같다.
우리가 프로세스에 대한 정보가 없다면 이러한 스케줄러를 어떻게 만들 수 있을까?
실행 중인 작업의 특성을 알아내고 이를 이용하여 더 나은 스케줄링 결정을 하기 위한 방법은 무엇인가?
작업의 실행 시간에 대한 선행 정보 없이 대화형 작업의 응답 시간을 최소화하고 동시에 반환 시간을 최소화하는 스케줄러를 어떻게 설계할 수 있는가?
MLFQ : 기본 규칙
현재 구현되어 있는 여러 MLFQ들은 자세하게 살펴보면 차이가 있지만 기본적으로 비슷한 방법을 사용하고 있다. MLFQ의 기본 알고리즘은 다음과 같다.
MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위(priority level)가 배정된다.
실행 준비가 된 프로세스는 이 중 하나의 큐에 존재한다. MLFQ는 실행할 프로세스를 결정하기 위하여 우선순위를 사용한다. 높은 우선순위를 가진 작업이, 즉 높은 우선순위 큐에 존재하는 작업이 선택된다.큐에는 둘 이상의 작업이 존재할 수 있다.
이들은 모두 같은 우선순위를 가진다. 이 작업들 사이에는 RR 스케줄링 알고리즘이 사용된다.MLFQ는 각 작업에 고정된 우선순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다.
MLFQ 스케줄링의 핵심은 우선순위를 정하는 방식이다. 예를 들어, 어떤 작업이 키보드 입력을 기다리며 반복적으로 CPU를 양보하면 MLFQ는 해당 작업의 우선순위를 높게 유지한다. 이러한 패턴은 대화형 프로세스가 나타내는 패턴이다. 반대로 한 작업이 긴 시간 동안 CPU를 집중적으로 사용하면 MLFQ는 해당 작업의 우선순위를 낮춘다. 이렇게 MLFQ는 작업이 진행되는 동안 해당 작업의 정보를 얻고, 이 정보를 이용하여 미래 행동을 예측한다.
MLFQ의 두 가지 기본 규칙은 다음과 같다.
- 규칙 1 : 우선순위(A) > 우선순위(B)이면, A가 실행된다. (B는 실행 X)
- 규칙 2 : 우선순위(A) == 우선순위(B)이면, A와 B는 RR 방식으로 실행된다.
위 그림에서 규칙 1, 2를 적용시키면 A와 B를 번갈아가며 실행하지만, C와 D는 실행되지 않는다. 이제 규칙을 추가하여 작업의 우선순위를 바꿔보자.
1. 우선순위 변경
MLFQ가 작업의 우선순위를 변경하는 것은 작업이 존재할 큐를 결정하는 것과 마찬가지다. 이를 위해서 우리는 워크로드의 특성을 반영해야 한다.
짧은 실행 시간을 갖는 CPU를 자주 양보하는 대화형 작업과 많은 CPU 시간을 요구하지만 응답 시간은 중요하지 않은 긴 실행 시간의 CPU 위주 작업이 혼재되어 있다.
- 규칙 3 : 작업이 시스템에 진입하면, 맨 위의 큐인 가장 높은 우선 우선순위에 놓여진다.
- 규칙 4a : 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아져 한 단계 아래 큐로 이동한다.
- 규칙 4b : 타음 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.
e.g. 한 개의 긴 실행 시간을 가진 작업
우선, 긴 실행 시간을 가진 작업이 도착한다면, 작업은 가장 높은 우선순위로 진입하고, 점차 가장 낮은 우선순위로 이동한다.
e.g. 짧은 작업과 함께
짧은 작업과 함께 예시를 본다면 MLFQ가 어떻게 SJF와 유사하게 동작하는지 이해할 수 있다.
결론부터 말한다면, MLFQ는 작업이 짧은 작업이라고 가정하여 높은 우선순위를 부여한다. 진짜 짧은 작업이라면 빨리 실행되고 바로 종료할 것이고, 아니라면 천천히 우선순위가 낮아져 스스로 긴 배치형 작업이라는 것을 증명하게 된다.
예시에서는 A(검은 작업)는 오래 실행되는 CPU 위주 작업이고, B(회색 작업)은 짧은 대화형 작업이다. A는 이미 실행해 온 상태이고, B는 이제 도착했다.
A는 가장 낮은 우선순위 큐에서 실행되고 있고, B는 T=100에 시스템에 도착했기에 가장 높은 우선순위 큐에 놓여진다. 실행 시간이 짧기 때문에 두 번의 타임 슬라이스를 소모하면 B는 가장 우선순위가 낮은 큐에 도착하기 전에 종료한다. 그런 후, A는 낮은 우선순위에서 실행을 재개한다.
e.g. 입출력 작업에 대해서는 어떻게 할 것인가?
규칙 4b의 의도는 대화형 작업이 자주 입출력을 수행하면 타임 슬라이스가 종료되기 전에 CPU를 양도하게 될 것이고, 이런 경우 동일한 우선 순위를 유지하게 하는 것이다. 이렇게 함으로써 MLFQ는 대화형 작업을 빨리 실행시킨다는 목표에 근접할 수 있다.
회색은 대화형 작업으로서 입출력을 수행하기 전에 1msec 동안만 실행되고, 검정색은 긴 배치형 작업으로 B와 CPU를 사용하기 위하여 경쟁한다. B는 입출력 때문에 CPU를 계속해서 양도하고, MLFQ는 B의 우선순위를 유지한다.
현재 MLFQ의 문제점
첫째, 기아 상태(starvation)가 발생할 수 있다.
시스템에 너무 많은 대화형 작업이 존재한다면, 그들이 모든 CPU 시간을 소모하게 될 것이고, 다른 긴 실행 시간 작업은 CPU 시간을 할당 받지 못한다.
둘째, 사용자가 스케줄러를 자기의 프로그램의 우선순위에 유리하게 동작하도록 조작할 수 있다.
가령, 타임 슬라이스가 끝나기 전에 아무 파일을 대상으로 입출력 요청을 내서 CPU를 양도한다. 그렇다면 같은 큐에 머무를 수 있고 더 많은 CPU 시간을 할당받을 수 있다.
셋째, 프로그램은 시간 흐름에 따라 특성이 변할 수 있다.
CPU 위주 작업이 대화형 작업으로 바뀔 수 있지만, 현재 구현 방식으로는 그런 작업은 운이 없게도 다른 대화형 작업들과 같은 대우를 받을 수 없다.
2. 우선순위의 상향 조정
규칙을 추가하여 기아 문제를 방지해보자. CPU 위주 작업이 조금이라도 진행하는 것을 보장하기 위해서 무엇을 할 수 있는가?
간단한 아이디어는 주기적으로 모든 작업의 우선 순위를 상향 조정(boost)하는 것이다. 목적을 달성하기 위해 여러 방법이 존재하지만, 모두 최상위 큐로 보내는 간단한 방법을 사용하기로 하자.
- 규칙 5 : 일정 시간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.
규칙 5는 두 가지 문제를 한 번에 해결한다.
첫째, 프로세스는 굶지 않는다는 것을 보장받는다. 최상위 큐에 존재하는 동안 작업은 다른 높은 우선순위 작업들과 RR 방식으로 CPU를 공유하게 된다.
둘째, CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우, 우선순위 상향을 통해 스케줄러가 변경된 특성에 적합한 스케줄링 방법을 적용한다.
위 예시 사진에서 왼쪽 그래프는 우선순위 상향이 없는 경우이고, 긴 실행 시간 작업은 두 개의 짧은 작업이 도착한 이후에는 굶게 된다.
오른쪽 그래프는 50msec마다 우선순위 상향이 일어난다. (예를 위해 설정한 짧은 시간) 이 경우, 긴 실행 시간 작업도 꾸준히 진행된다는 것을 보장할 수 있다.
S 값은 **부두 상수(voo-doo constants)라고 불리는데, 이러한 값을 정확하게 결정하기 위해서는 흑마술이 필요한 것처럼 보이기 때문이다. 너무 크면 긴 실행 시간을 가진 작업은 기아 상태에 빠질 수 있고, 너무 작으면 대화형 작업이 적절한 CPU 시간을 사용할 수 없게 된다.
3. 더 나은 시간 측정
그럼 사용자가 스케줄러를 자신의 프로세스에게 유리하게 동작하게 조작하는 문제를 어떻게 막을 수 있을까? 이는 규칙 4a와 4b에서 타임 슬라이스가 끝나기 전에 CPU를 양보하여 우선 순위를 유지하는 것을 이용한다.
해결책은 MLFQ의 각 단계에서 CPU 총 사용 시간을 측정하는 것이다. 스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장한다. 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등된다. 타임 슬라이스를 한 번에 소진하든 짧게 여러 번 소진한든 상관 없다. 규칙 4a와 4b를 합쳐 하나의 규칙으로 재 정의한다.
- 규칙 4 : CPU를 몇 번 양도하였는지 상관없이, 주어진 단계에서 시간 할당량을 소진하면 우선순위는 낮아진다.
위 사진에서 왼쪽 그래프는 규칙 4a, 4b에서 스케줄러를 자신에게 유리하게 동작시키려고 조작한 모습이고, 오른쪽은 새로 만든 규칙 4를 적용한 모습이다.
규칙 4a, 4b에서는 타임 슬라이스가 끝나기 직전에 입출력 명령어를 내려 CPu 시간을 독점하는 모습이다. 규칙 4에서는 프로세스의 입출력 행동과 무관하게 아래 단계 큐로 천천히 이동하게 되어 CPU를 자기 몫 이상으로 사용할 수 없게 된다.
MLFQ 조정과 다른 쟁점들
MLFQ 스케줄링에는 여러 다른 쟁점들이 남아 있다. 필요한 변수들을 스케줄러가 어떻게 설정해야 하는지도 중요한 문제이다.
예를 들어, 몇 개의 큐가 존재해야 하는가? 큐당 타임 슬라이스의 크기는 얼마로 해야 하는가? 기아를 피하고 변화된 행동을 반영하기 위하여 얼마나 자주 우선순위가 상향 조정되어야 하는가?
이러한 질문들은 쉽게 정할 수 없고, 워크로드에 대해 충분히 겪어보며 균형점을 찾아야 한다.
예를 들어, 대부분의 MLFQ 기법들은 큐 별로 타임 슬라이스를 변경할 수 있다. 우선순위가 높은 큐는 보통 짧은 타임 슬라이스가 주어진다. 이 큐는 대화형 작업으로 구성되고, 결국 이 작업들을 빠르게 교체하는 것은 의미가 있다. 우선순위가 낮은 큐는 반대로 CPU 중심의 오래 실행되는 작업들을 포함하고, 긴 타임 슬라이스가 적합하다.
Solaris의 MFLQ 스케줄러는 이러한 설정 값을 변경할 수 있는 테이블을 통해 관리자가 스케줄러의 동작 방식을 바꿀 수 있다. 다른 MLFQ 스케줄러는 테이블이나 이 장에서 설명한 정확한 규칙 같은 것을 사용하지 않고, 수학 공식을 사용하여 우선순위를 조정한다.
예를 들어, FreeBSD의 스케줄러는 작업의 현재 우선순위를 계산하기 위하여 프로세스가 사용한 CPU 시간을 기초로 한 공식을 사용한다. CPU 사용은 시간이 지남에 따라 감쇠되어 이 장에서 설명한 방식과는 다른 방식으로 우선순위 상향을 제공한다. 이러한 감쇠-사용(decay-usage) 알고리즘의 특성으로 우선순위를 계산하기도 한다.
마지막으로, 스케줄러들은 다른 여러 기능을 제공한다. 예를 들어, 일부 스케줄러의 경우 가장 높은 우선순위를 운영체제 작업을 위해 예약해 둔다. 일반적인 사용자 작업은 시스템 내에서 가장 높은 우선순위를 얻을 수 없다. 일부 시스템은 사용자가 우선순위를 정하는데 도움을 줄 수 있도록 허용한다. 예를 들어, 명령어 라인 도구인 nice를 사용하여 작업의 우선순위를 조정할 수 있다.
정리
알고리즘은 멀티 레벨 큐를 가지고 있으며, 지정된 작업의 우선순위를 위하여 피드백을 사용한다. 피드백이란 과거에 보여준 행동이 우선순위 지정의 지침이 된다는 것을 의미한다.
멀티 레벨 피드백 큐(Multi-Level Feedback Queue, MLFQ)
- 작업의 특성에 대한 정보 없이, 작업의 실행을 관찰한 후 그에 따라 우선순위를 지정한다.
- 반환 시간과 응답 시간을 모두 최적화한다.
- 짧게 실행되는 대화형 작업에 대해서 우수한 성능을 제공한다. (SJF/STCF와 유사하게 동작)
- 오래 실행되는 CPU-집중 워크로드에 대해서는 공정하게 실행하고 조금이라도 진행하는 것을 보장한다.
규칙
- 규칙 1 : 우선순위(A) > 우선순위(B)이면, A가 실행된다. (B는 실행 X)
- 규칙 2 : 우선순위(A) == 우선순위(B)이면, A와 B는 RR 방식으로 실행된다.
- 규칙 3 : 작업이 시스템에 진입하면, 맨 위의 큐인 가장 높은 우선 우선순위에 놓여진다.
- 규칙 4 : CPU를 몇 번 양도하였는지 상관없이, 주어진 단계에서 시간 할당량을 소진하면 우선순위는 낮아진다.
- 규칙 5 : 일정 시간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.
참고