[OSTEP] 가상화 CH08- CH09
CH08 스케줄링 - 멀티 레벨 피드백 큐
멀티 레벨 피드백 큐 Multi-level Feedback Queue, MLFQ
MLFQ가 해결하려고 하는 기본적인 문제는 두 가지이다
첫째, 짧은 작업을 먼저 실행시켜 반환 시간을 최적화하고자 한다
SJF나 STCF 같은 알고리즘은 작업의 실행 시간 정보를 필요로 하지만, 운영체제는 이 실행 시간을 미리 알 수 없다
둘째, MLFQ는 대화형 사용자에게 응답이 빠른 시스템이라는 느낌을 주고 싶었기 때문에 응답 시간을 최적화한다
(대화형 사용자 - 화면 앞에 앉아 바라보면서 프로세스의 종료를 기다리는 사용자)
RR은 응답 시간을 단축시키지만 반환 시간은 거의 최악이다
핵심 질문 - 정보 없이 스케줄하는 방법은 무엇인가
작업의 실행 시간에 대한 선행 정보 없이 대화형 작업의 응답 시간을 최소화하고
동시에 반환 시간을 최소화하는 스케 줄러를 어떻게 설계할 수 있는가?
8.1 MLFQ 기본 규칙
MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위 Priority 가 배정된다
실행 준비가 된 프로세스는 이 중 하나의 큐에 존재하고, MLFQ 는 실행할 프로세스를 결정하기 위하여 우선순위를 사용한다
큐에 둘 이상의 작업이 존재할 수도 있는데 이들은 모두 같은 우선순위를 지니고, 이 작업들 사이에서 RR이 적용된다
MLFQ 스케줄링의 핵심은 우선순위를 정하는 방식이다
각 작업에 고정된 우선순위를 부여하는 것이라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다
-> MLFQ는 다양한 프로세스 요구에 유연하게 대응하며, 높은 우선순위의 프로세스가 신속하게 실행될 수 있도록 설계되어 있다
MLFQ 의 두 가지 기본 규칙은 다음과 같다
규칙 1. Prioirty (A) > Priority (B) 이면, A가 실행된다 (B는 실행되지 않는다)
규칙 2. Prioirty (A) = Priority (B) 이면, A와 B는 RR 방식으로 실행된다
8.2 시도 1 - 우선순위의 변경
작업의 우선순위를 변경하는 것은 작업이 존재할 큐를 결정하는 것과 마찬가지이다
워크로드의 특성을 반영하여, 짧은 실행 시간을 갖는 CPU를 자주 양보하는 대화형 작업과 많은 CPU 시간을 요구하지만 응답 시간은 중요하지 않은 긴 실행 시간의 CPU 작업이 혼재되어 있을 때 우선순위 조정 알고리즘을 위한 첫번째 시도는 다음과 같다
규칙 3. 작업이 시스템에 진입하면, 가장 높은 순위 (맨 위의 큐) 에 놓여진다
규칙 4a. 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다 (한 단계 아래 큐로 이동)
규칙 4b. 타임 슬라이스를 소진하기 전에 CPU를 양보하면 같은 우선순위를 유지한다
그림 11.1 에서 작업은 최고 우선순위로 진입하고 10msec 타임 슬라이스가 하나 지나면 스케줄러는 작업의 우선순위를 한 단계 낮추어 해당 작업을 Q1으로 이동시킨다, 다시 하나의 타임 슬라이스 동안 Q1에서 실행한 후 작업은 마침내 가장 낮은 우선순위를 가지고 Q0으로 이동해서 이후에는 Q0에 계속 머무르게 된다
그림 11.2 에서 오래 실행되는 CPU 위주 작업은 가장 낮은 우선순위 큐에서 실행되고, 짧은 대화형 작업이 늦게 도착했을 때 가장 높은 우선순위 큐에 놓여진다, 실행 시간이 짧기 때문에 Q2->Q1 두 번의 타임 슬라이스를 소모하면 바닥의 큐에 도착하기 전에 작업이 종료되고, 다시 오래 걸리는 작업이 낮은 우선순위에서 실행을 재개한다
이 알고리즘은 작업이 짧은 작업인지 긴 작업인지 알 수 없기 때문에 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여한다, 진짜 짧은 작업이면 빨리 실행하고 종료되고, 짧은 작업이 아니라면 천천히 아래 큐로 이동하게 되면서 스스로 긴 배치형 작업이라는 것을 증명하게 된다
현재 MLFQ의 문제점
첫째. 기아 상태 Starvation 이 발생할 수 있다
시스템에 너무 많은 대화형 작업이 존재하면, 긴 실행 시간 작업은 CPU 시간을 할당받지 못할 것이다 (굶어 죽는다)
둘째. 스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있다
타임 슬라이스가 끝나기 전에 아무 파일을 대상으로 입출력 요청을 내려 CPU를 양도하면 CPU를 거의 사용하지 않은 것으로 간주되어 (낮은 우선순위큐로 이동하지 않고) CPU를 거의 독점할 수 있다
-> CPU를 양도한다는 것은 현재 CPU를 사용 중인 작업이 스스로 CPU 사용을 멈추고 다른 작업에게 CPU 사용 권한을 넘기는 것
마지막으로, 프로그램은 시간 흐름에 따라 특성이 변할 수 있다
CPU 위주 작업이 대화형 작업으로 바뀔 수 있다
-> 만약 CPU 위주 작업이 대화형 작업으로 바뀔 수 있다면 운이 좋을 때는 스케줄러가 이를 인지하고 우선순위가 높은 큐로 이동하여 CPU를 빨리 사용할 수 있지만, 이는 스케줄러가 프로그램의 특성 변화를 얼마나 빠르게 감지하는지에 달려있으며, 즉시 감지하지 못 하면 대화형 작업임에도 낮은 우선순위 큐에 머무를 수 있다는 점에서 운이 좌우될 수 있다는 의미
8.3 시도 2 - 우선순위의 상향 조정
기아 문제를 방지하기 위해, 주기적으로 모든 작업의 우선순위를 상향 조정 Boost 할 수 있다
규칙 5. 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다
규칙 5는 아래 두 가지 문제를 한 번에 해결한다
첫째. 프로세스는 굶지 않는다는 것을 보장받는다
둘째. CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우 우선순위 상향을 통해 스케줄러가 변경된 특성에 적합한 스케줄링 방법을 적용한다
S 값의 결정을 위해, 이러한 종류의 값을 부두 상수 voo-doo constants 라고 부르며, 흑마술이 필요한 변수이다
너무 크면 긴 실행 시간을 가진 작업은 굶을 수 있으며 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없게 된다
8.4 시도 3 - 더 나은 시간 측정
규칙 4a, 4b 에 의해 생긴 스케줄러를 자신에게 유리하게 동작시키는 문제를 막기 위해
MLFQ의 각 단계에서 CPU 총 사용 시간을 측정할 수 있다
스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장하고, 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등된다
규칙 4a, 4b 를 합쳐 아래로 정의할 수 있다
규칙 4. 주어진 단계에서 시간 할당량을 소진하면 (CPU 양도 횟수와 무관하게)
우선순위는 낮아진다 (아래의 큐로 이동한다)
8.5 MLFQ 조정과 다른 쟁점들
필요한 변수들을 스케줄러가 어떻게 설정해야 하는지를 포함해서 여러 쟁점들이 있는데
워크로드에 대해 충분히 경험하고 계속 조정해 나가면서 균형점을 찾아야 한다
대부분의 MLFQ 기법들은 큐 별로 타임 슬라이스를 변경할 수 있다
Solaris의 MLFQ 구현, 시분할 스케줄링 클래스 또는 TS는 설정이 쉽다
Solars는 프로세스의 우선순위가 일생 동안 어떻게 변하는지, 타임 슬라이스의 길이는 얼마인지,
작업의 우선순위는 얼마나 자주 상향되는지를 결정하는 테이블을 제공한다 [Arp00]
관리자는 이 테이블을 수정하여 스케줄러의 동작 방식을 바꿀 수 있다
FreeBSD의 스케줄러 (버전 4.3) 는 작업의 현재 우선순위를 계산하기 위하여 프로세스가 사용한 CPU 시간을 기초로 한 공식을 사용한다
CPU 사용은 시간이 지남에 따라 감쇠되어 이 장에서 설명한 다른 방식으로 우선순위 상향을 제공한다
마지막으로, 스케줄러들은 다른 여러 기능을 제공한다
예를 들어, 일부 스케줄러의 경우 가장 높은 우선순위를 운영체제 작업을 위해 예약해 둔다
일반적인 사용자 작업은 시스템 내에서 가장 높은 우선순위를 얻을 수 없고
일부 시스템은 사용자가 우선순위를 정하는 데 도움을 줄 수 있도록 허용한다
8.6 MLFQ 요약
알고리즘은 멀티 레벨 큐를 가지고 있으며, 지정된 작업의 우선순위를 정하기 위하여 피드백을 사용한다
과거에 보여준 행동이 우선순위 지정의 지침이 되기 때문에 시간이 지남에 따라 작업이 어떻게 행동하고
그에 맞게 어떻게 처리하는지 주의를 기울이면 도움이 된다
규칙 1. Prioirty (A) > Priority (B) 이면, A가 실행되고 B는 실행되지 않는다
규칙 2. Prioirty (A) = Priority (B) 이면, A와 B는 RR 방식으로 실행된다
규칙 3. 작업이 시스템에 진입하면, 가장 높은 순위 (맨 위의 큐) 에 놓여진다
규칙 4. CPU 양도 횟수와 무관하게 주어진 단계에서 시간 할당량을 소진하면
우선순위는 낮아진다 (아래의 큐로 이동한다)
규칙 5. 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다
MLFQ는 작업의 특성에 대한 정보 없이,
작업의 실행을 관찰한 후 그에 따라 우선순위를 지정하고 반환 시간과 응답 시간을 모두 최적화하여
짧게 실행되는 대화형 작업에 대해서는 우수한 전반적인 성능을 제공하고
오래 실행되는 CPU-집중 워크로드에 대해서는 공정하게 실행하고 조금이라도 진행되도록 한다
이런 이유로 BSD Unix와 여기서 파생된 다양한 운영체제 [Lef+89; Bac86], Solaris [McD06],
Windows NT 및 이후 Windows 운영체제 [CS97]를 포함한 많은 시스템이 기본 스케줄러로 MLFQ를 사용한다
CH09 스케줄링 - 비례 배분
비례 배분 Proportional Share, 공정 배분 Fair Share 스케줄러
비례 배분 - 반환 시간이나 응답 시간을 최적화하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장
비례 배분 스케줄링의 좋은 예는 추첨 스케줄링 Lottery Scheduling 으로 알려진 Whalspurger and Weihl [WW94] 의 연구이다
다음 실행될 프로세스를 추첨을 통해 결정한다, 더 자주 수행되어야 하는 프로세스는 당첨 기회를 더 많이 준다
핵심 질문 - 어떻게 CPU를 정해진 비율로 배분할 수 있는가?
특정 비율로 CPU를 배분하는 스케줄러를 어떻게 설계할 수 있는가?
그렇게 하기 위한 중요한 기법은 무엇인가? 그 기법은 얼마나 효과적인가?
9.1 기본 개념 - 추첨권이 당신의 몫을 나타낸다
추첨권 (티켓) 이라는 기본적인 개념이 추첨 스케줄링의 근간을 이룬다
추첨권은 프로세스가 (또는 사용자 또는 그 무엇이든) 받아야 할 자원의 몫을 나타내는 데 사용된다
프로세스가 소유한 티켓의 개수와 전체 티켓에 대한 비율이 자신의 몫을 나타낸다
추첨 스케줄링은 (타임 슬라이스가 끝날 때마다) 확률적으로 (하지만 결정적이지는 않게) 추첨을 결정한다
스케줄러는 전체 추첨권의 수를 알고 있으며, 이 중 하나를 선택한다
선택된 추첨권의 값에 따라 실행할 프로세스가 결정되고 스케줄러는 당첨된 스케줄러를 실행한다
무작위성이 원하는 비율을 정확히 보장하지는 않지만, 작업들이 장시간 실행될수록 원하는 비율을 달성할 가능성이 높아진다
9.2 추첨 기법
추첨권 화폐 Ticket Currency
사용자가 추첨권을 자신의 화폐 가치로 추첨권을 자유롭게 할당할 수 있도록 허용하고, 시스템은 자동적으로 화폐 가치를 변환한다
사용자 A, B가 각각 추첨권 100장을 받았다고 가정할 때,
A는 A1/ A2 두 개의 작업을 실행 중이고 자신이 정한 화폐로 전체 1000장의 추첨권 중에 각각 500장의 추첨권을 할당하였고
B는 하나의 작업을 실행 중이고 자신의 기준 화폐 10장 중 10장을 할당하였다
시스템은 A1과 A2의 몫을 A의 기준 화폐 500장에서 전역 기준 화폐 각각 50장으로 변환한다
B1의 추첨권 10장은 추첨권 100장으로 변환된다, 전역 추첨권 화폐랑 (총 200장) 기준으로 추첨한다
추첨권 양도 Ticket Transfer
양도를 통하여 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다
클라이언트 프로세스는 서버에게 메시지를 보내 자신을 대신해 특정 작업을 해달라고 요청한다, 작업이 빨리 완료될 수 있도록 클라이언트는 서버에게 추첨권을 전달하고 서버가 자신의 요청을 수행하는 동안 서버의 성능을 극대화하려고 한다, 요청을 완수하면 서버는 추첨권을 다시 클라이언트에게 되돌려 주고 먼저와 같은 상황이 된다
추첨권 팽창 Ticket Inflation
이 기법에서 프로세스는 일시적으로 자신이 소유한 추첨권의 수를 늘이거나 줄일 수 있다
하지만 하나의 욕심 많은 프로세스가 매우 많은 양의 추첨권을 자신에게 할당하고 컴퓨터를 장악할 수 있기 때문에
서로 신뢰하지 않는 프로세스들이 상호 경쟁하는 시나리오에서는 이 방법이 효과적이지 않다
그러나 프로세스들이 서로 신뢰하는 상황에서는, 어떤 프로세스가 더 많은 CPU 시간을 필요로 한다면
시스템에게 이를 알리는 방법으로 다른 프로세스들과 통신하지 않고 혼자 추첨권의 가치를 상향 조정한다
9.3 구현
추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 점이고,
필요한 것은 난수 발생기, 프로세스들의 집합을 표현하는 자료 구조 (예, 리스트), 추첨권의 전체 개수 뿐이다
-> 추첨 스케줄링에서는 난수를 사용해 프로세스를 선택하는데, 각 프로세스가 가진 추첨권의 수에 따라 당첨 확룔이 결정된다
리스트에 프로세스와 추첨권 수를 저장한 후, 난수를 뽑고 리스트를 순회하며 각 프로세스의 추첨권을 누적해 당첨자를 찾는다
내림차순으로 정렬하면 적은 수의 프로세스가 많은 추첨권을 가지고 있는 경우 검색 속도가 빨라진다
9.4 예제
CPU를 공유하는 두 개의 작업이 같은 개수의 추첨권 (100) 을 가지고, 동일한 실행 시간 R을 가지고 있다고 가정하자
두 작업을 거의 동시에 종료시키고자 하지만, 추첨 스케줄링의 무작위성 때문에 한 작업이 다른 작업보다 먼저 종료될 수 있다
이 차이를 정량화하기 위해, 간단한 불공정 지표 Unfairness Metric 인 U 를 정의한다
U 는 첫번째 작업이 종료된 시간을 두번째 작업이 종료된 시간으로 나눈 값이다 (ex. 첫번째 작업이 시간 10에 종료, 두번째 작업이 시간 20에 종료하면 U = 10/20 = 0.5 이다)
두 작업이 거의 동시에 종료하면 U는 1에 근접해진다, 완벽한 공정 스케줄러에서는 U = 1 을 얻게 된다
작업 길이가 길지 않은 경우, 평균 불공정 정도가 심각하며, 작업이 충분한 기간 동안 실행되어야 추첨 스케줄러는 원하는 결과에 가까워진다
9.5 추첨권 배분 방식
시스템 동작이 추첨권 할당 방식에 따라 크게 달라지기 때문에,
주어진 작업 집합에 대한 "추첨권 할당 문제" 는 여전히 미해결 상태이다
9.6 왜 결정론적 (Deterministic) 방법을 사용하지 않는가
무작위성을 이용하면 스케줄러를 단순하게 만들 수 있지만, 정확한 비율을 보장할 수 없고 짧은 기간만 실행되는 경우는 더욱 그렇기 때문에 Waldspurger 는 결정론적 공정 배분 스케줄러인 보폭 스케줄링 Stride Scheduling [Wal95] 을 고안하였다
시스템의 각 작업은 보폭을 가지고 있으며, 보폭은 자신이 가지고 있는 추첨권 수에 반비례하는 값이다
프로세스가 실행될 때마다 pass 라는 값을 보폭만큼 증가시켜 얼마나 CPU를 사용하였는지를 추적한다
스케줄러는 가장 작은 pass 값을 가진 프로세스를 선택하고, 프로세스를 실행시킬 때마다 pass 값을 보폭만큼씩 증가시킨다
예를 들어 작업 A, B, C가 각각 100, 50, 250의 추첨권을 가지고 있을 때 10,000 (임의의 큰 값) 을 각자의 추첨권 개수를 나누면
각 작업의 보폭은 100, 200, 40이 되고, 각자의 pass 값은 모두 0에서 시작한다
처음에는 pass 값이 같기 때문에 아무 프로세스나 실행될 수 있다, A를 선택했다고 가정하고 실행하면, 타임 슬라이스만큼 실행되고 종료될 때 pass 값을 100으로 갱신한다, 다음에 B가 실행되면 해당 pass 값이 200으로 갱신되고, C를 실행하면 pass 값이 40으로 갱신된다,
이 시점에서 알고리즘은 가장 작은 pass 값을 가진 C를 선택하고 80 으로 갱신한다, 다음 C가 다시 실행되고 (아직 최소 pass 값) 120으로 갱신된다, 이제 A가 실행되고 200으로 갱신된다 (이제 B와 같아진다) 다음 C가 2번 더 실행되고 pass 값은 160을 거쳐 200으로 갱신된다, 이 시점에서 모든 pass 값은 다시 같아지게 되고 이런 선택 과정이 계속 반복된다
C는 5번, A는 2번, B는 한 번만 실행되었고, 이 횟수는 각자 가진 추첨권의 개수 250, 100, 50과 정확히 비례한다
추첨 스케줄링은 정해진 비율에 따라 확률적으로 CPU를 배분하고,
보폭 스케줄링은 각 스케줄링 주기마다 정확한 비율로 CPU를 배분한다
추첨 스케줄링은 보폭 스케줄링과 다르게 상태 정보가 필요 없고, 프로세스 상태 (CPU 사용 현황, pass 값) 를 유지할 필요가 없다
새 프로세스를 추가할 때, 새로운 프로세스가 가진 추첨권의 개수, 전체 추첨권의 개수만 갱신하고 스케줄하기 때문에
추첨 스케줄링에서는 새 프로세스를 쉽게 추가할 수 있다
9.7 리눅스 CFS, Completely Fair Scheduler
Linux에서 구현한 완전 공정 스케줄러 CFS, Completely Fair Scheduler 의 장점은 효율성과 확장성이다
CFS는 최적의 내부 설계와 자료 구조 사용을 통해 스케줄링 결정을 매우 신속하고 효율적으로 수행한다
CFS는 모든 프로세스들에게 CPU를 공평하게 배분하는 것을 목표로 하고
사용자나 관리자가 프로세스의 우선순위를 조정하여 다른 프로세스들보다 더 많은 CPU 시간을 할당받게 할 수 있다
또한 CFS는 프로세스 관리에 Red-Black Tree를 이용함으로서 효율성 문제를 해결했다
9.8 요약
추첨권 스케줄링은 무작위성 Randomness 을 사용하고, 보폭 스케줄링은 같은 목적을 결정적 방법으로 달성한다
두 방법 모두 접근 방식이 특히 입출력과 맞물렸을 때, 제대로 동작하지 않고 [AC97]
추첨권 할당이라는 어려운 문제가 미해결 상태로 남아 있어서 CPU 스케줄러로 널리 사용되지 않는다
앞서 언급한 MLFQ 과 다른 유사 Linux 스케줄러 같은 범용 스케줄러는
그러한 문제를 더 직관적으로 해결하기 때문에 더 널리 사용되고 있다
비례 배분 스케줄러는 추첨권 할당량을 비교적 정확하게 결정할 수 있는 환경에서
(CPU 자원을 비교적 정확하게 할당할 수 있는 환경에서) 유용하게 사용된다