이 장에서는 멀티 프로세스 스케줄링의 기본을 소개한다. 더 자세한 내용은 이후에 병행성(concurrency) 부분에서 다루게 된다. 병행성 부분을 공부하고 다시 본다면 더 이해가 잘될 것이다.
현재는 여러개의 CPU 코어가 하나의 칩에 내장된 멀티코어 프로세서가 어디에서나 사용된다. 그러나 기존의 전통적인 응용 프로그램(c언어와 같은)은 하나의 CPU만 사용한다. 이를 해결하기 위해 응용 프로그램을 병렬(parrallel)로 실행되도록 다시 작성해야 되며, 보통 쓰레드를 이용한다.
당연하게도 멀티프로세서의 스케줄링 문제가 대두되었다. 여러 CPU에서 작업을 어떻게 스케줄 해야 할까?
1. 배경: 멀티프로세서 구조
멀티프로세서 스케줄링에 대한 새로운 문제점을 이해하기 위해서는 단일 CPU, 멀티 CPU 하드웨어의 근본적인 차이에 대한 이해가 필요하다.
다수의 프로세서 간의 데이터 공유, 하드웨어 캐시 사용 방식에서 차이
단일 CPU 시스템에서는 하드웨어 캐시 계층이 존재한다. 메인 메모리에서 자주 사용되는 작업의 저장본을 캐시라는 작고 빠른 메모리에 저장하여 프로그램의 빠른 실행을 돕는다.
또한 지역성이라는 개념에 기반한다. 데이터가 한번 접근 되면 가까운 미래에 다시 접근되기 쉽다는 시간 지역성과 주소 x에 데이터에 접근했다면 그 주변의 데이터가 접근되기 쉽다는 공간 지역성 개념을 이용한다.
그렇다면 하나의 시스템에 여러 멀티 프로세서가 존재하고 하나의 공유 메모리가 있다면 어떨까?
만약 CPU1가 주소 A를(D값) 읽는다고 가정하자. 데이터가 캐시에 존재하지 않기 때문에 시스템은 메모리에서 데이터를 불러오고 값 D를 얻는다. 이후 CPU1에서 D의 값을 D’로 변경한다. 메모리에 데이터를 쓰는 것은 시간이 오래 걸리기 때문에 우선 캐시에서만 값을 D’으로 변경 후 메모리 쓰기 작업은 미룬다.
이때 운영체제가 CPU 2로 이동하기로 결정하고, CPU2에서 주소 A의 값을 읽게된다면 어떻게 될까? 당연히 메모리에 있는 변경 전 값인 D를 읽게된다.
이를 캐시 일관성 문제(chace coherence)라고 부른다. 기본적인 해결책은 하드웨어에 의해 제공된다. 하드웨어는 메모리 주소를 계속 감시하고, 관리하는 방식이 있다. 특히, 여러개의 프로세스가 하나의 메모리에 갱신할 때에는 항상 공유되도록 한다.
버스 기반 시스템에서는 버스 스누핑이라는 기법을 사용하여 캐시는 자신과 메모리를 연결하는 버스를 계속 모니터링한다. 캐시에 데이터의 변경이 있을 때, 무효화, 갱신, 나중 쓰기 등을 고려해야해서 캐시 일관성 문제가 점점 복잡해진다.
2. 동기화를 잊지 마시오
일관성 유지에 대한 모든 일을 캐시가 담당한다면, 프로그램이나 운영체제는 공유 데이터에 접근할 때 걱정할 필요가 없을까? 당연히 걱정해야한다.
CPU들이 동일한 데이터 또는 구조체에 접근할 때, 올바른 연산 결과의 보장을 위해 상호 배제를 보장하는 동기화 기법을 사용한다. 예를 들어, 여러 CPU가 동시에 접근하는 공유 큐가 있다고 가정하자. 캐시의 일관성을 보장하는 프로토콜이 있다 하더라도 항목의 추가나 삭제와 같은 구조체의 원자적 갱신을 위해서는 락이 필요하다.
만약 두개의 CPU의 쓰레드가 위 작업을 수행한다고 가정하자. 두 작업이 원자적으로 실행된다면 각 쓰레드는 리스트의 head를 한번씩 제거해야할 것이다. 그러나 한 스레드에서 head가 다음 포인터로 이동(10행)하기 전(에 쓰레드 1,2 둘다 같은 head를 읽는다면(7행) 삭제는 한번만 발생할 것이다.
이러한 문제는 락(lock)을 통해 해결될 수 있기는 하지만, CPU 개수가 많아질 수록 연산이 느려진다.
3. 마지막 문제점: 캐시 친화성
CPU에서 실행되는 프로세스는 CPU 캐시와 TLB에 상당한 양의 상태 정보를 저장할 것이다. 그런데 프로세스가 매번 다른 CPU에서 실행된다면, 이런 정보들을 CPU를 옮겨갈 때 마다 새롭게 탑재해야 하기 때문에 프로세스의 성능이 오히려 나빠질 수 있다.
캐시 친화성을 고려하기 위해서는 가능한 한 프로세스를 동일한 CPU에서 실행할 수 있도록 해야할 것이다.
CPU 캐시의 경우 컴퓨터구조, TLB는 이후 VM 부분에서 자세히 배울 수 있다.
4. 단일 큐 스케줄링
멀티프로세서 시스템의 스케줄러에 대해 알아보자. 단일 프로세서에서 하던 것 처럼, 그대로 적용할 수 있다. 이러한 방식을 단일 큐 멀티프로세서 스케줄링(single queue multiprocessor scheduling, SQMS) 이라 부른다.
SQMS의 ****장점은 단순함이다. 만약 CPU가 2개라면, 2개의 실행할 작업을 선택하면 된다.
그러나 SQMS에는 명백한 단점이 있다.
- 확장성 결여 - SQMS에서는 락을 기반으로 다수의 CPU에 대한 스케줄링을 제어하는데, CPU가 많아질 수록 성능이 크게 저하된다.
- 캐시 친화성 - 실행할 5개의 작업이 있고 (A, B, C, D, E), 4개의 CPU가 있을 때, 스케줄링 결과는 다음과 같을 것이다.
같은 작업이 여러 CPU에서 실행되니 캐시 친화성 관점에서 잘못된 선택을 하는 것이다.
그래서 대부분의 SQMS 스케줄러는 가능한 한 프로세스가 동일한 CPU에서 재실행될 수 있도록 시도한다.
A~B 작업은 각각 자신의 CPU에서 실행되고, 오직 E만이 프로세서를 이동하며 실행된다. 이런 방식으로 대부분의 작업의 캐시 친화성을 보존하고 있다. 다음에는 다른 작업을 이동시키는 방식을 통해 친화성에 대한 형편성도 추구할 수 있겠지만 그 경우 구현이 복잡해질 수 있다.
5. 멀티 큐 스케줄링
단일 큐 방식의 문제 때문에, 일부 시스템은 CPU마다 큐를 하나씩 둔다. 이 방식을 멀티 큐 멀티프로세서 스케줄링(multi-queue multiprocessor scheduling, MQMS)이라고 부른다.
MQMS 방식은 여러 개의 스케줄링 큐로 구성되고, 각 큐는 RR과 같은 특정 스케줄링 규칙을 따른다. 작업이 시스템에 들어가면 하나의 스케줄링 큐에 배치된다.
예를 들어, 현재 시스템에 CPU 0, 1과 작업 A, B, C, D가 있다고 가정하자. 각각의 스케줄링 큐가 내린 작업 배치가 다음과 같다고 해보자
만약 각 큐의 스케줄링 정책이 RR이라면 다음과 같이 스케줄될 것이다.
MQMS가 SQMS에 비해 가지는 명확한 이점은 확장성이 좋다는 것이다. CPU가 많아질 수록 큐의 개수도 증가하기 때문에 락과 캐시 친화성에 대해 고민할 필요가 없다. MQMS에서 작업은 계속 같은 CPU에서 실행된다.
그렇다고 문제가 없는 것은 아닌다. 멀티 큐의 근본적인 문제는 워크로드의 불균형(load imbalance)이다. 위 예시와 같이 2개의 CPU, 4개의 작업이 존재한다고 가정했을 때, C가 종료된다면 어떨까?
RR 스케줄링 정책을 사용할 경우 스케줄 결과는 다음과 같다. A가 B,D보다 2배의 CPU를 차지하게 되고, 이는 바람직한 스케줄링이라고 할 수 없다. 여기에 A까지 종료된다면, CPU 0은 유후상태가 될 것이다.
이런 문제에 대한 당연한 해결방안은 이주(migration)이다. 작업을 다른 CPU로 이동시켜 워크로드의 균형을 달성한다.
다음과 같은 작업 상황에서는 B 또는 D를 CPU 0 으로 옮기면 된다.
이런 상황에서는 한 번의 이주만으로는 문제가 해결되지 않고, 작업들을 지속적으로 이주시켜 주어야 한다. 이주의 필요 여부를 결정하기 위해, 작업이 적은 큐가 다른 큐를 훔쳐본다. 더 많은 작업을 가지고 있다면 하나 이상의 작어을 가져오게 된다.
물론 큐를 너무 자주 검사하게 되면 이에따른 오버헤드로 인해 확장성에 문제가 생긴다. 적절한 주기를 찾는게 중요하겠지만 마법의 영역이다.
6. Linux 멀티프로세서 스케줄링
Linux에서 멀티프로세서 스케줄링은 크게 세가지 방법이 존재한다. O(1) 스케줄러, CFS 스케줄러, BFS 스케줄러.
- O(1) 스케줄러 - 멀티 큐 방식, 우선순위를 기반으로 우선순위를 시간에 따라 변경하며 우선순위가 높은 작업을 선택한다. (MLFQ와 유사), 특히 상호작용을 우선시한다.
- CFS 스케줄러 - 멀티 큐, 결정론적/비례배분 방식이다.
- BFS 스케줄러 - 단일 큐, 비례 배분 방식이다. EEVDF라는 알고리즘을 기반에 둔다.
7. 요약
멀티프로세서 스케줄링에는 크게 단일 큐 방식과 멀티 큐 방식이 있다.
- 단일 큐 방식: 구현이 간단하고 워크로드의 균형을 잘 맞추는 특징이 있다. 하지만, 많은 프로세서에 대한 확장성과 캐시 친화성이 좋지 않다.
- 멀티 큐 방식: 확장성이 좋고 캐시 친화성을 잘 다루는 반면, 워크로드의 불균형에 취약하고 구현이 복잡하다.
