Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

멀티코어 프로세서가 발전함에 따라 멀티프로세서 시스템은 점점 흔해지고 있는데, 이에 따라 단일 CPU를 사용할 때는 발생하지 않았던 여러 문제들도 발생했다. 그 중 가장 근본적인 문제는 보통의 응용 프로그램들이 단일 CPU만을 사용하기 때문에, CPU를 추가하는 것이 해당 응용 프로그램을 더 빠르게 만들지 못한다는 것이다.

이 문제를 해결하기 위한 방법으로는, 해당 프로그램을 스레드 등을 사용해 병렬적으로 실행될 수 있도록 재작성하는 것이 있다. 멀티 스레드 프로그램은 여러 CPU에 작업을 분산시키기 때문에, 더 많아진 CPU 자원이 주어졌을 때 더 빠르게 실행될 수 있기 때문이다.

프로그램들이 가지고 있는 문제는 그렇다치고, 멀티 프로세서를 사용함에 따라 OS도 해결해야 할 다른 문제를 가지게 됐다. 지금까지는 싱글 프로세서 스케줄링에 대해 이야기해왔는데, 멀티 프로세서를 사용하게 된 경우에는 어떻게 프로세스들을 스케줄링 해야할까? 단일 CPU에서의 스케줄링을 어떻게 여러 CPU에서의 스케줄링으로 확장할 수 있을까?

1. Background : Multiprocessor Architecture

멀티프로세서 스케줄링과 관련된 이슈들을 이해하기 위해서는 우선 싱글 CPU 하드웨어와 멀티 CPU 하드웨어의 근본적인 차이에 대해 알아야 한다. 이 차이는 하드웨어 캐시와 데이터가 여러 프로세서들 사이에서 공유되는 방식에 기인한다.

싱글 CPU 시스템에는 프로세서가 프로그램을 더 빠르게 실행시키도록 돕는 하드웨어 캐시 계층이 있다. 캐시는 시스템 메인 메모리에서 자주 쓰이는 데이터의 복제본이 저장되는, 작고 빠른 메모리이며, 메인 메모리는 반대로, 모든 데이터들을 가지고 있지만 캐시에 비해 접근이 느리다. 우리는 자주 접근되는 데이터들을 캐시에 저장함으로써 시스템은 더 크고 느린 메모리를 좀 더 빠른 것처럼 보이게 할 수 있다.

캐시 예시
명시적인 로드 명령어를 통해 메모리로부터 값을 가져오는 프로그램이 있고, 시스템은 단일 CPU를 사용한다고 하자. CPU는 작은 캐시를 가지고 있고 큰 메인 메모리를 가지고 있다. 처음 프로그램이 이 명령어를 불러올 때, 메인 메모리에 있는 데이터를 가져오는 데에는 오랜 시간이 걸린다. 프로세서는 불러온 데이터를 나중에 다시 사용할 것이라 기대하며 불러온 데이터의 복제본을 CPU 캐시에 저장한다. 만약 프로그램이 나중에 같은 데이터를 다시 가져오려 하면 CPU는 이 데이터가 캐시에 있는지를 우선 체크하고, 만약에 있다면 메인 메모리가 아닌 캐시에서, 해당 데이터를 좀 더 빠르게 가져올 수 있게 한다.

Locality

캐시는 지역성 개념에 기반하고 있다. 이 지역성에는 시간적 지역성과 공간적 지역성이 있는데, 이 둘은 다음의 가정에 기반하며, 그 덕에 하드웨어 시스템은 어떤 데이터를 캐시에 집에넣을지를 잘 판단할 수 있다.

• 시간적 지역성
  - 한 번 접근된 데이터는 가까운 시간 안에 다시 접근될 가능성이 높다.
• 공간적 지역성
  - 프로그램은 어떤 데이터에 접근할 때, 그 근처에 있는 데이터에도 접근할 가능성이 높다.

문제는 여러 프로세서들이 한 메인 메모리를 공유하면서 하나의 시스템을 구성할 때다. 여러 CPU에서의 캐싱은 어렵다.

캐시 일관성(cache coherence) 문제

예시
어떤 프로그램이 CPU1를 통해 주소 A에 있는, 값 D를 가진 데이터에 접근하려한다 하자. 데이터는 CPU1의 캐시에 있지 않으므로 시스템은 이를 메인 메모리에서 가져올 것이다. 프로그램이 A에 있는 데이터의 값 D'으로 바꾼다. 보통 시스템은 성능의 이유로 변경 사항을 메인 메모리에 바로 반영하지 않고, 모아뒀다가 나중에 한 번에 처리한다.
OS가 프로그램 실행을 중단하고 이를 CPU2로 옮겼다고 해보자. 프로그램이 다시 주소 A의 데이터를 읽으면, 이 데이터는 CPU2의 캐시에 없기 때문에 시스템은 해당 데이터를 메인 메모리로부터 가져온다. 그런데 주소 A에는 아직 CPU1에서 변한 D'값이 반영되지 않아 D'가 아닌 D가 들어가있다.

위와 같은 문제를 캐시 일관성의 문제라고 하는데, 이에 대해서는 하드웨어를 통한 기본적 해결법이 있다. 하드웨어는 메모리 접근을 모니터링함으로써, 항상 제대로 된 상황만 일어나도록 시스템을 관리하며, 여러 프로세서들 사이의 메모리 공유를 유지할 수 있게 한다.

버스 기반 시스템에서의 한 해결책은 버스 스누핑(bus snooping) 이라는 테크닉을 사용하는 것이다. 각 캐시는 자신을 메인 메모리에 연결하는 버스를 감시함으로써 메인 메모리의 업데이트에 주의를 기울이고, CPU는 자신이 가지고 있는 캐시에서의 업데이트를 감지하면 자신의 캐시에 있는 복사본을 무효화하고 새로운 값으로 업데이트한다.

2. Don't Forget Synchronization

캐시 일관성 문제가 해결된다고 해서 멀티프로세서 시스템이 갖는 문제가 모두 해결되는 것은 아니다.

CPU들 사이에서 공유되는 데이터에 접근하려 때에는 제대로 된 연산을 보장하기 위해서 상호 배제 기법들이 사용되어야 한다. 여러 CPU에서 동시에 공유하는 큐에 접근하려 할 때, 락과 같은 상호 배제 기법을 사용하지 않고서는 큐에 데이터를 동시에 쓰거나 지우는 일을 제대로 하기는 힘들다.

간단하게 공유 데이터가 있는 특정 코드를 실행하기 전에 잠그고 끝나면 푸는 방법을 이용하면 동기화 문제를 해결할 수 있지만, 성능 하락의 문제가 발생한다.

3. One Final Issue: Cache Affinity

멀티프로세서 캐시 스케줄러를 설계하는 데에 있어서의 마지막 문제는 캐시 친화성(cache affinity) 이라 불리는 것이다. 개념은 간단하다. 프로세스는 한 특정한 CPU에서 실행되고 있을 때 CPU 캐시에 자신에 대한 여러 정보들을 올려놓기 때문에, 다음에 실행될 때에도 같은 CPU에서 돌아가는 것이 유리하다는 것이다.
그런데 만약 이 프로세스를 각 시간마다 다른 CPU에서 실행한다면, 이 프로세스는 실행될 때마다 자신의 상태를 다시 캐시에 로드해야하므로 낮은 성능은 가지게 될 것이다. 그러므로 멀티프로세서 스케줄러는 스케줄링 결정을 내릴 때, 가능하다면 한 프로세스를 같은 CPU에서 실행할 수 있도록, 캐시 친화성에 대해서도 신경을 써야한다.

4. Single-Queue Scheduling

지금까지의 배경 지식을 바탕으로 멀티프로세서의 스케줄러를 어떻게 설계해야 할지 알아보자. 가장 기본적인 접근법은 싱글 프로세서 스케줄링에서 했던 것과 같이 스케줄링이 필요한 모든 작업들을 하나의 큐에다가 집어넣는 것으로, single-queue multiprocessor scheduling(SQMS)라 부른다.

이 접근법은 기존의 정책들에 대한 큰 변화 없이 사용할 수 있다는 점에서 간단하다는 이점을 가진다. 하지만 SQMS는 명확한 단점들도 가지고 있는데, 그 첫 번째는 확장성이 부족하다는 것이다. 스케줄러가 여러 CPU들에서도 잘 작동됨을 보장하기 위해서, 락과 같은 것들을 코드에 삽입해 사용할 수 있고, 락은 단일 큐를 사용하는 경우 제대로된 결과를 나옴을 보장할 수 있다.

하지만 락은 시스템 내에서 사용하는 CPU의 수가 많아질수록 성능을 급격히 저하시킨다. 단일 락에 대한 경쟁이 심해질수록 시스템은 락에 더 많은 시간을 쓰게 되고, 정작 원래 해야했던 작업들에는 시간을 덜 쓰게 되기 때문이다.

SQMS의 두 번째 문제점은 캐시 친화성이다. 단일 큐 내에 5개의 작업들, A, B, C, D, E가 있고, CPU는 4개, CPU0, CPU1, CPU2, CPU3이 있다고 하자. 각 작업들이 time slice만큼 돌아가고 다음 작업들을 고른다고 가정하면, 작업들은 다음과 같이 스케줄링 될 수 있다.

CPU	t1	t2	t3	t4	t5
CPU0	A	E	D	C	B
CPU1	B	A	E	D	C
CPU2	C	B	A	E	D
CPU3	D	C	B	A	E

이는 한 프로세스는 되도록이면 동일한 CPU에서 실행되어야 한다는 캐시 친화성에 정확히 반대된다.

이 문제를 해결하기 위해서 대부분의 SQMS는 캐시 친화성을 보장하기 위한 메커니즘들을 포함한다. 예를 들면 다음과 같이 A에서 D까지의 작업들은 동일한 프로세서를 사용하게 하고, 작업 E만 프로세서를 바꿔가면서 실행되게 함으로써 친화성을 최대한 보존하는 것이다. 물론 이런 기법을 구현하는 것은 어려운 일이다.

CPU	t1	t2	t3	t4	t5
CPU0	A	E	A	A	A
CPU1	B	B	E	B	B
CPU2	C	C	C	E	C
CPU3	D	D	D	D	E

결론적으로 SQMS는 구현하기에 쉽다는 명확한 장점을 가지고는 있지만, 확장 가능성과 캐시 가능성에 있어서의 명확한 단점도 가지고 있다.

5. Multi-Queue Scheduling

SQMS의 문제점들로 인해 몇몇 시스템들은 여러 개의 큐를 사용하기로 했는데, 이러한 접근법을 multi-queue multiprocessor scheduling(MQMS)라 부른다.

MQMS에서는 여러 개의 큐를 사용하며, 각 큐는 특정한 스케줄링 기법을 사용한다. 작업은 시스템에 들어오면 휴리스틱을 통해 정확히 하나의 스케줄링 큐에 들어가고, 각각 독립적으로 스케줄링 되므로 SQMS에서 일어나는 정보 공유 및 동기화의 문제를 피할 수 있다.

예를 들어, 이제는 두 개의 CPU를 사용하는 한 시스템에 작업 A, B, C, D가 들어온다고 하자. 각 CPU가 스케줄링 큐를 가지고 있다고 할 때, OS는 각 작업을 어떤 큐에 넣을지를 결정해야 한다. CPU0의 큐 Q0에는 A, C, CPU1의 큐 Q1에는 B, D가 들어간다고 해보자. 만약 RR을 사용한다면 다음과 같은 스케줄이 만들어질 수 있다.

CPU	t1	t2	t3	t4	t5	t6	t7	t8	t9
CPU0	A	A	C	C	A	A	C	C	A
CPU1	B	B	D	D	B	B	D	D	B

SQMS와 비교했을 때, MQMS는 확장 가능성의 측면에서 분명한 이점을 가진다. CPU의 개수가 많아지면 큐의 양도 많아지고, 락에 의한 성능 하락이나 캐시 경합은 더 이상 큰 문제가 되지 않는다. 게다가 MQMS는 같은 작업들은 같은 CPU에서 실행하므로 CPU 캐시의 내용을 재사용할 수 있고, 따라서 본질적으로 캐시 친화성을 제공하기도 한다.

부하 불균형(load imbalance)

하지만 또 새로운 문제가 있는데, 바로 부하 불균형(load imbalance) 이다. 위 예에서 작업 C가 종료됐다고 하자. 각 큐에서 RR 정책을 이용한다면 CPU 0에서는 A만이 돌아가게 될 것이다. 더욱이 만약 작업 A까지 종료된다면 CPU0은 동작하지 않는 상태를 유지하게 될 것이다.

MQMS는 이 부하 불균형 문제를 어떻게 해결할까? 답은 작업들을 이리저리로 이동시키는 것이다. 이를 가리켜 이주(migration) 이라 부르는데, 작업을 한 CPU에서 다른 CPU로 이주시키면서 부하의 균형을 얻을 수 있게 된다. 예컨대 Q0에 0개, Q1에 2개의 작업이 있다면 Q1의 작업 중 하나를 Q0으로 이주시켜 스케줄링하면 바로 부하 균형을 이룰 수 있게 된다.

한편 Q0에 하나, Q1 두 개의 작업이 있는 경우는 좀 더 까다롭다. 이때는 하나 이상의 작업을 계속 이주시켜야 한다. 작업 A만 CPU0에 있고, 작업 B, D는 CPU1에 있다고 하자. 어느 정도의 time slice가 지나면 B는 CPU0의 큐로 이주해 A와 경쟁하고, D는 CPU1에서 단독으로 실행된다. 또 얼마간의 time slice 후에는 A가 CPU1로 이주해 D와 경쟁한다. 이런 방식으로 부하 균형이 이뤄진다.

CPU	t1	t2	t3	t4	t5	t6	t7	t8	t9
CPU0	A	A	A	A	B	A	B	A	B
CPU1	B	D	B	D	D	D	D	D	A

물론 다른 여러 이주 패턴들도 많이 있다. 문제는 어떻게 시스템이 그런 이주 여부를 어떻게 결정하느냐 하는 것이다. 한 기본적인 접근법은 작업 훔치기(work stealing) 이라는 테크닉을 사용하는 것이다. 이 접근법에서 작업의 개수가 적은 큐는 다른 큐를 보고 해당 큐가 얼마나 차있는지를 확인하고, 대상 큐가 자신보다 더 차있다면, 하나 이상의 작업을 해당 큐에서 훔쳐온다.

물론 이 접근법에서는 다른 큐들을 얼마나 자주 확인할 것인지에 대한 문제가 있다. 만약 다른 큐들을 너무 자주 살펴보게 되면 오버헤드가 너무 커져 확장에 있어서의 문제를 겪게 될 것이고, 반대로 다른 큐를 너무 오랫동안 보지 않게 되면 심각한 부하 불균형에 빠질 수 있기 때문이다. 다른 시스템 정책 설계에서와 마찬가지로 적절한 균형점을 찾는 문제가 남아있는 것이다.

6. Linux Multiprocessor Schedulers

리눅스에는 멀티프로세서 스케줄러에 대해 일치된 해결책이 없다. 시간이 흐르면서 세 종류의 스케줄러가 등장했는데, 바로 O(1) 스케줄러, CFS, BF 스케줄러다. 이 중 O(1)과 CFS는 여러 개의 큐들을 사용하지만, BFS는 단일 큐만 사용한다.

O(1) 스케줄러는 우선 순위에 기반한 스케줄러로, 시간에 따라 프로세스의 우선순위를 바꾸고 가장 높은 우선순위 순으로 프로세스들을 정렬한다. 바로 전에 다룬 CFS는 결정론적인 비례 배분 스케줄러다.

BFS는 단일 큐 비례 배분 스케줄러인데, Earliest Eligible Virtual Deadline First라는 좀 더 복잡한 기법을 사용한다.

7. Summary

SQMS는 설계하기에 좀 더 직관적이고 부하도 균형적이지만 여러 프로세서들로 확장하기 어렵고 캐시 친화성에 문제가 있다. 한편 MQMS는 확장성이 좋고 캐시 친화성도 잘 처리하지만, 부하 불균형의 문제가 있고 구현하기에도 더 복잡하다. 두 방법 모두 일장일단이 있으므로, 문제가 없는 간단한 정답은 없다.