[Operating Systems] Multiprocessor Scheduling

우리 주변의 컴퓨터들을 보더라도, 대부분의 컴퓨터들은 듀얼코어 이상의 CPU를 사용하고 있다.

게다가, 요즘에는 일반 데스크탑 용도의 컴퓨터에도 6코어, 8코어 CPU를 사용하고 있으니,

단순히 Single core에 대한 scheduling 뿐만 아니라 Multi core에 대한 Scheduling도 교려해야 한다.

먼저 Single Core 환경에 대해 간단히 살펴보면

(CPU - Cache) ------Memory 형태로 되어 있다

Cache는 Main Memory보다 용량은 작지만, 주요 data들을 모아 둔 작고 빠른 임시저장장치이다.

이 Cache를 이용함으로써 CPU와 Memory간의 다소 느린 속도를 보완해줄 수 있다.

Cache는 다음과 같은 Idea에서 탄생하였다.

1. temporal locality

어떤 data에 접근했을 때, 가까운 미래에도 그 data를 사용할 것이라고 예상

2. spatial locality

어떤 data에 접근했을 때, 그 근처에 있는 데이터에도 접근할 것이라고 예상

그런데 어떻게 이런 Idea가 현실적리고 할 수 있는가?

어떤 대용량의 데이터를 처리할 때를 살펴보면, 주로 반복문과 배열을 사용해서 데이터를 처리하기 때문에 위와 같은 가정이 어느정도 들어맞는 것이다.

단순히 정렬 알고리즘에서도, 첨자 i(temporal locality)와 정렬 대상이 되는 배열(spatial locality)이 존재함을 직관적으로 알 수 있다.

이 Cache가 어떤 방식으로 구현되어 있는지는 논외로 한다.

(이것은 아주 고수준의 학습을 요구하며, 아마도 대학원 과정에서 학습하게 될 것이다.)

그렇다면 Multi Core에서는 어떨까?

(CPU - Cache) ------

                            | -------Memory

(CPU - Cache) ------

와 같은 형태가 될 것이다. (Core는 더 많을 수도 있다)

이 경우에는 문제가 복잡해진다.

CPU1에서 CPU2로 작업을 옮기려면 CPU2에서 다시 필요한 정보를 Memory에서 Cache로 가져오고,

또 Context Switch가 발생하면 CPU1의 Cache로 필요한 정보를 가져오게 되면서

problem of cache coherence(캐시 일관성 문제)가 발생하게 되어 Overhead 떄문에 Single Core보다 훨씬 더 형편없는 성능을 보일 지도 모른다.

그렇다면 이 문제는 어떻게 해결되는가?

이 역시 Hardware 단에서 해결되는 문제이므로 여기에서는 다루지 않겠다.

(오래된 방법 중 하나로 bus snooping이라는 방법이 있다)

우리가 다루어야 할 문제는 무엇인가?

Problem 1: Synchronization

Scheduling을 위해, 하나의 Queue를 두고 enqueue와 dequeue를 하는 모습을 상상해 보자.

Core가 n개라면 최대 n개의 Core가 각각 Queue에 접근하여 enqueue하거나 dequeue하는 상황이 생길 것이다.

그럴 경우엔, lock과 unlock으로 synchronization을 보장해 주어야만 의도치 않은 behavior가 발생하지 않을 것이다.

그런데, lock과 unlock으로 이것을 보장하게 되면 구현은 간단해지지만 performance에는 아주 부정적인 영향을 끼칠 것이다.

Problem 2: Cache Affinity

만약 어떤 작업이, CPU1에서 실행되고 다음 번에도 같은 CPU에서 실행된다면, Memory에서 필요한 정보를 Cache로 가져오는 과정이 필요하지 않기 때문에

매우 우수한 성능을 가질 수 있게 된다.

그러므로, Single Core에서와는 다르게, 가능한 한 같은 process는 같은 processor에서 실행되도록 노력해야 한다.

이것을 Cache Affinity(캐시-친화적인) 이라고 한다.

Solution 1: Single Queue Multiprocessor Scheduling(SQMS)

하나의 Queue를 두고 n개의 코어로 작업하는 방법이다.

만약 Queue에 A B C D E 라는 작업이 있다면

CPU1: AEDCB

CPU2: BAEDC

CPU3: CBAED

CPU4: DCBAE

처럼, 그냥 CPU1부터 시작해서 Queue로 부터 Job을 Dequeue하고, Time Slice가 끝나면 순차적으로 Enqueue하고... 이것이 반복되는 것이다.

그러나 이것은 Cache Affinity에 있어서는 아주 최악이다.

조금 바꾸어 보면

CPU1: AEAAA

CPU2: BBEBB

CPU3: CCCEC

CPU4: DDDDE

처럼 E만 옮겨다니게 하는 방법이다.

어느 정도의 Cache Affinity가 제공되어서 위보다는 더 우수한 성능을 낼 것이다.

그러나 이것은 Synchronization문제에 관해서, 하나의 Queue를 대상으로 하므로 lock/unlock을 사용함으로써 생기는 Overhead가 너무 크다.

Solution 2: Multi Queue Multiprocessor Scheduling(MQMS)

그렇다면 1개의 Queue가 아니라 1개의 CPU당 1개의 Queue를 가지게 한다면 어떨까?

그렇다면 Synchonization 문제에 관해서도 어느 정도 자유로워 질 수 있을 것이다.

Q1에 A B 가 있고

Q2에 C D가 있다면

CPU1: AABBAABBAABB...

CPU2: CCDDCCDDCCDD...

처럼 작동하여, Cache Affinity도 어느 정도 보장될 것이다.

(각각의 Queue는 본질적으로 독립적으로 관리된다)

그러나 이러한 상태에서는 몇몇 단점이 존재한다.

위와 같은 작업상황에서, B가 먼저 끝나버린다면

CPU1: AAAAAAAAAAAAA....

CPU2: CCDDCCDDCCDD...

처럼 CPU2에 비해 CPU1에서는 모든 CPU 사용권을 A가 독점하게 되어 Unfair한 상태가 된다.

게다가 여기에서 A마저 작업이 종료된다면

CPU1: 

CPU2: CCDDCCDDCCDD...

처럼 CPU1이라는 자원을 사용할 수 있음에도 전혀 사용하지 않게 된다.

이는 심각한 낭비이다.

Solution of Solution 2: Migration

말 그대로 Queue 속의 Job을 Queue간에 이동시키는 방법이다.

Q1이 텅 비어 있고, Q2에 C D가 있다면, Q1으로 C를 이동시켜서

CPU1: CCCCCCCCCCCCC...

CPU2: DDDDDDDDDDDD...

처럼 Fair한 상태가 될 수 있다.

설령 Q1에 A가 있고 Q2에 C D가 있는 애매한 상황일지라도 완벽에 가까운 Fair를 보장해야 하기 때문에

CPU1: AAAAAACCCCCAAAA

CPU2: BBBCCCCDDDDDAAD

처럼 Job을 계속적으로 다른 Queue로 옮겨가면서 수행하게 된다.

Migration을 어떻게 할 것인지에 관한 방법은 여러 가지가 있는데, Work stealing에서는 만약 다른 Queue가 자신의 Queue보다 더 꽉 차있다면 Job을 빼앗아오는(steal) 방법으로 Fair해지기를 기대한다.

--------------------------------------------------

Reference

Operating Systems: Three Easy Pieces (Remzi H. Arpaci-Dusesdau, Andrea C. Arpaci-Dusesdau)