10 Multiprocessor Scheduling (Advanced)

thread를 이용하여 응용 프로그램을 parallel하게 실행, 성능을 개선시켰다.

하지만 이럴 경우 문제점이 발생한다.

cache는 CPU가 가지는 작고 빠른 메모리인데 main memory에서 자주 사용되는 데이터의 복사본을 저장한다.

현재 사용중인 데이터의 근처에 있는 정보를 주로 저장하는데 이는 locality에 기반한 결과이다.

temporal locality와 spatial locality의 두 종류가 있다.

 

 

CPU는 이렇게 main memory를 공유하는데 만약 두 CPU에서 각각 실행중인 두 개의 프로그램이 동시간에 특정 메모리의 값을 읽어오고 수정하는 작업을 한다면?

그 값을 각자의 cache에 저장한뒤 수정하는 등의 작업을 수행하기 때문에 이상한 결과가 초래될 것이다.

이러한 문제를 cache coherence라고 부르는데

이를 방지하기 위해서 bus snooping이라는 기법을 사용한다.

cache가 자신과 main memory를 연결하는 bus를 계속 모니터링해서 자신이 사용하는 메모리 영역의 값에 변화가 발생하면 자신이 가지고 있는 복사본의 값을 변경(갱신)시키거나 invalidate 시킨다.

 

두 CPU의 thread가 동시에 특정 값이나 루틴에 접근하지 못하도록 하는 lock 기능을 사용할 수도 있다.

 

mulitprocessor cache scheduler에서 고려해야 할 문제점은 cache affinity이다.

한 프로그램이 여러 CPU를 왔다갔다하면서 실행된다면 그때마다 cache값을 새로 세팅해줘야하기 때문에 비효율적이라는 것이다.

 

단일 큐 스케줄링 (single queue multiprocessor scheduling, SQMS)

이 방식은 단일 processor scheduling의 기본 프레임워크를 그대로 사용하는 방식이다.

scheduler는 일정 형태의 lock을 코드에 삽입하여 프로그램이 올바르게 작동하도록 한다.

하지만 이러한 방식은 CPU 개수가 늘어날수록 시스템이 lock을 위해 소요되는 시간이 늘어나 scalability(확장성)이 좋지 않다.

큐에 있는 작업을 단순히 여러 CPU에 나눠주는 방식은 cache affinity 측면에서 심각한 손실을 초래할 수 있기에 작업 분산 정책도 사용한다. (아래의 그림처럼)

멀티 큐 스케줄링 (multi-queue multiprocessor scheduling, MQMS)

CPU마다 큐를 하나씩 두는 등, 여러 개의 큐를 사용하는 방식이다.

CPU마다 큐를 별개로 두고 각각의 CPU가 자신의 큐에 있는 작업만 수행한다면 캐시 친화적이고 확장성을 걱정할 필요가 없다.

하지만 여러 큐에 들어있는 작업의 개수가 달라지면 workload imbalance 가 발생할 수도 있다.

이를 해결하기 위해 scheduler는 적당한 migration 정책을 사용한다.

큐가 다른 큐들을 검사하여 자신의 작업 개수보다 많은 수의 작업을 보유한 큐를 발견하게 된다면 그 큐에서 하나 이상의 작업을 가져오는 work stealing 기법을 이용할 수 있다.

물론 이러한 검사를 너무 자주할 경우 오버로드가 높아져 확장성이 낮아질 수 있고 검사를 너무 드물게 한다면 workload imbalance가 초래되기 때문에 그 주기는 아주 적절하게 설정해야 한다.

 

Linux 멀티프로세서 스케줄러

O(1) 스케줄러, Completely Fair Scheduler(CFS), BF Scheduler(BFS) 등이 있다.

 

O(1)과 CFS는 멀티 큐를 사용하고 BFS는 단일 큐를 사용한다.

O(1)은 priority-based 방식이고 CFS는 proportional share 방식이다.

nice값이라는 것을 설정해서 사용하기도 한다.

CPU를 빨리 양도하는 프로그램은 nice값이 크고 그렇지 않은 프로그램은 nice값이 작다.