[운영체제] CPU 스케줄링: multiprocessor 스케줄링 - (2)

 

load balancing(부하 균등화)

---

 

SMP 시스템에서, multiprocessor의 이점을 최대한 활용하기 위해서, 부하를 모든 프로세서에서 균등하게 유지하는 것이 중요하다.

 

그렇지 않으면, 다른 프로세서들이 ready 큐에서 기다리는 스레드들이 많은 부하가 큰 상태일때, 하나 이상의 프로세서가 유휴(idle) 상태일 수 있다.

 

부하 균등화(load balancing)는 SMP 시스템에서 모든 프로세서들의 부하를 동일하게 유지하도록 노력한다.

 

부하 균등화는 각 프로세서별로 자신만의 ready 큐를 가지는 시스템에서 필요하지만, 공통 ready 큐를 가지는 경우에는 필요하지 않다.

 

 

 

부하 균등화의 두 가지 방법

 

1. push migration (push 이주)

특정 task가 주기적으로 각 프로세서의 부하를 검사하고, 만약 불균형이 발견되면, 스레드를 이동(or push)함으로써 부하를 분배한다.

 

2. pull migration (pull 이주)

idle 프로세서가 busy 프로세서를 기다리고 있는 프로세스를 pull함으로써 부하를 분배한다.

 

pull과 push migration은 상호 배타적일 필요 없이, 병렬로 구현 가능하다.

 

 

 

균등 부하(balance load)의 두 가지 의미

 

1. 모든 큐에 대략 동일한 수의 스레드가 있다.

 

2. 모든 큐에 스레드 우선순위를 균등하게 분포한다.

 

 

 

 

 

 

processor affinity(프로세서 선호도)

---

 

부하 균등화로 인해 스레드가 다른 프로세서로 이주하게 되면,  이주 이전 프로세서의 캐시 메모리는 무효화되어야 하고, 이주 이후 프로세서의 캐시는 다시 채워져야 한다.

 

캐시 무효화(invalidating) 및 다시 채우는(repopulating) 비용이 많이 들기 때문에, SMP를 지원하는 대부분의 OS는 스레드를 이주시키지 않고, 같은 프로세서에서 실행시키면서 warm cache를 이용하고자 한다.   

 

이를 프로세서 선호도(processor affinity)라고 한다. 즉, 프로세스는 현재 실행 중인 프로세서에 대한 선호를 가진다.

 

 

 

스레드 큐의 구성을 위한 두 가지 전략이 프로세서 선호도에 미치는 영향

 

1. common ready queue

스레드는 어떤 코어에서도 실행 가능하다.

따라서, 스레드가 새로운 프로세서에 스케줄링되면, 캐시가 새로 채워져야 한다.

 

2. private, per-procesor ready queue

스레드는 항상 같은 프로세서에서 실행된다.

따라서, warm cache의 내용을 활용할 수 있고, 프로세서 선호도를 제공한다.

 

 

 

프로세서 선호도(processor affinity)의 두 가지 형태

 

1. soft affinity(약한 선호도)

OS가 프로세스가 동일한 프로세서에서 실행되도록 노력하지만, 보장하지는 않는다. 

이 경우 부하 균등화로 프로세서 간 이주가 가능하다.

 

2. hard affinity(강한 선호도)       

프로세스가 실행될 수 있는 프로세서의 집합을 지정하는 시스템 콜을 제공한다.

 

 

많은 시스템은 약한 선호도와 강한 선호도를 모두 지원한다.

 

 

 

메인 메모리의 구조가 프로세서 선호도에 영향을 미친다.

 

NUMA 시스템에서, 특정 CPU에 스케줄링된 스레드를 CPU가 있는 위치에 가장 가까운 메모리에 할당해 가장 빠른 메모리 접근을 제공할 수 있다.

 

 

 

부하 균등은 종종 프로세서 선호도의 이점을 상쇄시킨다.