[OS] Process Scheduling V (Multiprocessor Scheduling, SQMS, MQMS, O(1), WFQ, CFS)

Multiprocessor Scheduling

우리는 지금까지 단일 처리기, 즉 Uniprocessor 에서의 Scheduling에 대해 다루었다. 단일 처리기에서는 단순히 Ready, Block, Running State를 결정하는 문제를 살펴보았다. 반면에 다중 처리기에서는 고려햐애 할 것들이 너무 많다. 우리가 일반적으로 사용했던 Ready Queue는 전역변수 형태로 선언이 되어있다. 따라서 다중 처리기가 하나의 Queue에 접근하려고 하면 동시에 메모리에 접근하게 되는 Race Condition이 생길 수도 있다. 또한 Cache 친화력 문제, 어떻게 다중 처리기에 Process를 할당할 것이며, Process의 Heterogeneity를 어떻게 다룰 것이며, Process를 어떻게 Balanced Workload를 부여할 것인지 등등 수많은 문제를 다루어야한다. 

Cache Affinity (HW)

Cache Affinity는 캐시 친화력이라는 것이다. 우리는 이전에 캐시에 대해서 다뤄본 적이 있다. Cache는 직전에 수행된 Process에 대해 Memory에 있는 정보들을 캐시에 올려놓았을 것이다. Uniprocessor에서는 어차피 CPU가 하나이기 때문에 캐시 친화력이 크게 문제가 되지 않았지만 다중 처리기에서는 이제 Cache 친화력을 고려하는 것이 좋을 것이다. Cache는 L1, L2 캐시가 각 CPU 별로 달려있기 때문에 Process가 하나의 Process만 다룰 수 있다면 Memory Bus나 I/O Bus를 많이 타지 않고 빠르게 연산을 할 수 있을 것이다. 예를 들어 CPU A, CPU B가 각각 P1, P2, P1, P2, P1, P2 / P1, P2, P1, P2, P1, P2 이렇게 처리하는 것이 아니라 P1, P1, P1, P1, P1, P1 / P2, P2, P2, P2, P2, P2 를 처리할 수 있다면 캐시 친화력을 극대화 해서 Cache라는 한정되고 매우 빠른 자원을 효율적으로 사용할 수 있을 것이다. 

Concurrency (SW)

우리는 또한 Concurrency를 생각해보아야한다. Ready Queue는 전역변수로 선언이 되어 있다. 따라서 다수의 처리기가 이 Queue에 접근을 한다면 누구는 front()를, 누구는 pop()을 동시에 수행하려고 한다면 이는 절대 안전하지 않다. Shared Data를 처리하기 위해서는 상호배제(Mutual Exclusion)이 필요하게 된다. 이 기법에 대해서는 동기화 파트에서 자세히 다루겠다. 어째뜬 중요한 것은 임계 영역에 있는 Queue를 한번에 하나의 처리기만 사용하는 것을 보장해야 Correct한 결과를 도출해낼 수 있다. 

SQMS (Single Queue Multiprocessor Scheduling)

우리가 가장 쉽게 생각해볼 수 있는 다중 처리기 스케줄링 알고리즘이다. Ready Queue가 하나일때 이 기법을 사용하게 된다. 각 CPU에 연속적으로 Queue에 있는 Process를 할당하면 된다. 단순히 Processor에서 Running이 끝났으면 Queue에서 pop한 것을 할당해주면 된다. 정말 간단하기 때문에 구현의 난이도가 낮고 단순하다는 장점이 있는 반면, 특정 알고리즘을 사용하지 않으면 Cache Affinity를 보장해줄 수 없다. 이는 결국 효율성의 문제로 넘어가게 되며 Uniprocessor만큼 성능이 하락할 가능성이 있다. 또한 여기에는 무조건 상호배제가 들어가야 한다. Processor가 4개인데, 두 개의 Processor가 Running을 끝냈다면 차례대로 하나씩 Queue에서 Process를 선택해야되기 때문에 Scalability 역시 떨어지게 된다. 

MQMS (Multi Queue Multiprocessor Scheduling)

따라서 SQMS의 해결책으로 등장한 것이 MQMS이다. Processor는 HW 자원이기 때문에 그 숫자가 고정되어 있다. 따라서 Processor마다 Queue를 가지게 하는 전략이다. 그리고 Process가 하나의 Queue에만 들어가게 하고, 만약 Process가 Time Out되거나 마치게 되면 해당 Queue로 다시 돌아가게 하는 전략이다. 즉, Process가 Processor에 Mapping이 될 수 있다는 것이다. 이 방식을 채택함으로서 Cache Affinity를 확보할 수 있게 된다. 또한 Race Condition을 줄일 수 있기 때문에 확장성 문제도 어느정도 해결할 수 있다. 또한 각각의 Queue를 지니고 있기 때문에 여기에 대해서 서로 다른 Scheduling Policy를 사용할 수 있다는 장점을 지니고 있다. 

그러나 항상 장점만 있는 것이 아니다. 이렇게 구현된 MQMS는 Load Imbalance라는 문제를 지니고 있다. 이는 부하 불균등이라는 뜻인데 Process를 각 Queue에 Mapping하는 경우 CPU마다 Run할 수 있는 Process의 수가 달라진다. 

그림의 위쪽을 보자. 0번 Processor는 현재 A 혹은 B Process가 들어오지 않아서 Idle한 상태이다. 이때 CPU0의 Utilization은 매우 떨어지게 된다. 반면에 CPU1은 항상 Busy한 상태이다. 그 아래 그림을 보면 CPU0은 Process A를 독점하고 있는 상태이다. 이렇게 되면 Fairness 측면에서 Process들이 공평하게 수행하고 있냐고 질문을 해봤을 때 대답은 아니오이다. 따라서 이러한 문제점들이 생길 수 있기 때문에 MQMS Migration이라는 전략이 필요하게 된다. 

 

Migration 전략은 Work Stealing, 혹은 Pull Migration이라고도 한다. Preemption과 비슷하게 Process를 뺐어오는 것이다. 특히 CPU가 Idle해지는 것을 막기 위해 많이 사용이 된다. OS는 Queue의 상태를 보고 Migrating을 시전해서 Process를 분담시켜줄 수 있다. 따라서 부하를 결정하는 것은 Queue의 길이가 될 것이다. 위 그림의 CPU0처럼 Idle한 경우에는 Queue가 empty하기 때문에 Queue의 길이가 Workload를 결정해줄 수 있다. 그러나 우리가 항상 고려해야 할점은 Trade-off가 있다는 것이다. 먼저 Migration Policy는 Cache Affinity를 포기하는 전략이기 때문에 CPU0과 같이 Process A,B에 맞춰저 있던 Cache에 Process C가 들어오게 된다면 Cache Pollution으로 인해 친화력은 떨어질 것이다. 또한 얼마나 자주 OS가 Load Imbalance를 볼 것인가의 문제도 생긴다. 어째뜬 모든 Queue의 길이를 비교해야 하기 때문에 O(n)의 시간을 필연적으로 걸리게 된다. 따라서 빈번히 이를 검사하게 되면 Overhead가 크다고 할 수 있다. 반면에 Overhead에 대한 검사를 별로 하지 않는 다면 CPU Utilization이 떨어지는 CPU가 분명히 존재하게 되어 Idle해질 수도 있다. 따라서 적절한 Threshhold를 정해야 한다. 

O(1) Scheduler

O(1) Scheduling 방법은 RTOS, LINUX 2.5에서 사용되었던 조금은 오래된 방법이다. 그러나 이 Scheduling에도 분명히 배울 점은 있다. 이 방식에서는 Bitmap으로 구현된 shced_find_first_bit()은 0~139까지 약 140개의 우선순위를 나타낸다. 이 Bitmap의 숫자가 낮을 수록 우선순위가 높다. 이 Bitmap에는 Queue에 대한 Pointer가 달려있는데 이 Queue는 List형태로 구현되어 task, 즉 Process들이 들어갈 수 있다. 조금 쉽게 설명하자면 Priority Queue라고 이해하면 좋겠다. 따라서 Bitmap에서 낮은 번호에 있는 Queue의 task를 수행하는 것이다. LINUX에서는 Bitmap이라는 자료구조를 통해 0, 1로 구분하여 Queue에 task가 있는지 없는지를 결정하게 된다. 

출처: https://github.com/draveness/linux-archive/blob/master/2.6.8.1/include/asm-x86_64/bitops.h

Bitmap도 중요하지만 주목해야 할 점은 이 알고리즘의 Running 방식이다. 선택된 Process를 실행하는 Run Queue가 Active, Expired Queue 두 개로 구성이 된다. 하나의 task를 선택하면 Time Slice가 주어지게 되는데, 먼저 Active Queue에 들어가 수행한다. 이 Time Slice를 전부 다 소진하게 되면 그 task는 Expired Queue로 이동하게 된다. 만약 Time Slice를 전부 소진하기 않는다면 다시 Active Queue로 돌아가게 된다. 이제 Active Queue에 있는 Process들이 전부 다 소진이 되면 Expired Queue와 Pointer를 단순히 바꾸어 서로 바뀌게 된다. 이는 Starvation에 대한 방지인 것이다. 조금은 특이한 스케줄러이다. 그러나 이는 예전의 스케줄링이고 이제는 CFS Scheduler를 사용한다고 한다. 이에 대해서는 뒤에서 다뤄보겠다. timeslice 계산 과정중 상수 시간 알고리즘을 적용하기도 하고 고정된 Bitmap 크기만을 탐색하면 되기 때문에 O(1)이라는 이름이 붙었다고 한다. 

Proportional Share Scheduling

그러나 지금까지 다뤄본 스케줄링들이 CPU 별로 진정한 Fairness를 보장한다고 할 수 있을까? Process마다 PCB에는 해당 Process의 Weight이 담겨있다. 이제 이 Weight에 비례하는 Scheduling을 다뤄볼 것이다. 이는 CPU Bandwidth를 정확하게 보장하는 것이다. 예를 들어 P1의 Weight는 2, P2의 Weight는 1이라면 CPU에게 각각 2/3, 1/3씩 할당해주는것이 어쩌면 진정한 의미의 Fairness를 추구하는 방식이 아닐까? 따라서 Proportional Share Scheduling은 두 가지 맥락에서 살펴볼 수 있다. 하나는 Fair Queueing이다. 진정한 의미의 Fair을 추구하는 것이다. Packet Scheduling에서 사용되는데 WFQ, WRR 스케줄링이 이에 해다왼다. 다른 하나는 Proportional Share이다. OS 관점에서 바라본다면 Process를 정확한 비율로 맞춰 효율성을 극대화 하는 맥락으로 Lottery, Stride Scheduling, CFS가 이에 해당된다. 링크는 Lottery, Stride에 대해 자세히 정리해놓은 분의 블로그이다. 따라서 이 알고리즘들의 Criteria는 얼마나 정확하게 그 Weight에 비례해서 Fairness를 보장할 수 있는지 정량적인 평가가 필요하다. 

따라서 Service Time Error를 줄이는 것이 최종 목표이다. 예시를 들어 Error를 구해본다면 (0, 10)구간에 P1:P2 = 2:1이라고 해보고, W1(0, 10)이 7이라고 해보자. 그러면 참값은 10 * (2/3)으로서 E1(0, 10)은 약 0.3으로 매우 작을 것이다. 

WFQ (Weighted Fair Queueing)

WFQ에서는 가장 작은 Virtual Time을 선택해나가는 알고리즘이다. 

Criteria는 VT(Virtual Time), VFT(Vitrual Finish Time)이 있다. VT는 어떤 Process의 t시간 까지의 누적 시간의 정규화이다. 예를 들어 A:B:C:D = 4:3:2:1 의 Weight를 지닌 Process들이 있다면 Process A와 Process D가 같은 1초를 부여받더라도 느껴지는 시간이 다를 것이다. 자신의 Weight로 할당받은 초를 나누기 때문이다. 따라서 수행시간을 정규회된 누적 시간이 가장 작은 값을 우선적으로 선택해나간다. 따라서 0시간에는 VFT(0)이 A가 1/4이, B가 1/3, C가 1/2, D가 1/1 이기 때문에 min(VFTi)가 기준이 되어 수행하게 되는것이다. 이때 역시 Tie Breaking 상황이 있을 수 있는데, 이는 OS마다 다르게 될 수 있다. 따라서 10ms동안 VFT를 min하게 성택해나간다면 A,B,A,C,B,A,A,B,C,D 순으로 Process들이 수행이 될 것이다. 

 

그러나 이제 이러한 의구심이 들 수 있다. 그러면 A,A,A,A,B,B,B,C,C,D 순으로 수행하는 것과 뭐가 다른지라는 질문이 있을 수 있다. 이러한 스케줄링은 WRR(Weighted Round Robin)이라고도 부른다. 이는 당연한 질문이 될 수도 있다. 어째뜬 마지막 10ms 관점에서는 전부 다 제대로 수행된 것처럼 보이기 때문이다. 그러나 우리가 주목해야 할 것은 위의 Criteria중 하나인 Service Time Error이다. 예를 들어 선형적으로 수행이 되었을 때 4ms에서 B Process의 Eb(0, 4)를 계산해보면 0 - 4 * (3/10) = -1.2이다. 다시말해 4초동안 1.2의 Process는 수행해야하는데 그렇지 못한다는 것이다. 반면 이를 WFQ의 Error율을 본다면 Eb(0, 4)는 1-4*(3/10) = -0.2로 Error를 낮출 수 있다. 따라서 WFQ에서의 Error값은 아래의 범위 안에서 보장이 된다. 

CFS (Completely Fair Scheduler)

WFQ와 마찬가지로 Virtual Time이 가장 적은 것을 선택하는 스케줄링이다. LINUX 2.6.23 버전부터는 이 스케줄링을 사용한다. Virtual Time의 최솟값을 찾는 문제임으로 Binary Search Tree나 Heap으로 구현을 할 수도 있겠지만, Workload에 따른 Imbalance문제를 해결하기 위해 Red-Black Tree를 사용한다. 링크는 내가 알고리즘 수업시간때 많이 참조한 블로그인데 설명이 잘 되어 있어 남긴다. Red Black Tree는 스스로 높이가 Balancing되기 때문에 최솟값은 항상 left most leaf에 있기에 이를 탐색하는데에는 O(n log n)시간 밖에 걸리지 않는다. Multiprocessor에서의 사용을 위해 Queue의 개수도 여러개를 지원하며 각 CPU마다 Run Queue가 있어 효율적으로 동작한다.