운영체제 8. 멀티 프로세서 스케줄링(Multi Processor Scheduling)

운영체제

멀티 프로세서 스케줄링(Multi Processor Scheduling)

8.1 배경 : 멀티프로세서 구조

• 단일 CPU 시스템에는 하드웨어 캐시 계층이 존재한다.
• 캐시는 지역성(locality)에 기반한다. 지역성에는 시간지역성(temporal locality)과 공간지역성(spartial locality)의 두 종류가 있다. 시간적 지역성의 기본아이디어는 데이터가 한번 접근되면 가까운 미래에 다시 접근되기 쉽다는 것이다.
• 멀티프로세서 시스템에서 캐시를 사용하는 것은 훨씬 더 복잡하다. 캐시일관성(cache coherence) 문제가 생길 수 있다.
• 기본적인 해결책은 하드웨어에 의해 제공된다. 하드웨어는 메모리 주소를 계속 감시하고 항상 ‘올바른’ 순서로 처리되도록 시스템을 관리한다. 특히, 여러개의 프로세스들이 하나의 메모리에 갱신할 때는 항상 공유되도록 한다.
• 버스 기반 시스템에서는 버스스누핑(bus snooping)이라는 오래된 기법을 사용한다. 캐시는 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링한다. 캐시 데이터에 대한 변경이 발생하면, 자신의 복사본을 무효화(invalidate) 시키거나(자신의 캐시에서 삭제) 갱신(새로운 값을 캐시에 기록) 한다. 나중쓰기(write-back) 캐시는 메인메모리에 쓰기 연산이 지연되기 때문에 캐시 일관성 문제를 훨씬 더 복잡하게 만든다.

8.2 동기화를 잊지마시오

• CPU들이 동일한 데이터 또는 구조체에 접근할 때(특히, 갱신), 올바른 연산결과를 보장하기 위해 락과 같은 상호 배제를 보장하는 동기화 기법이 많이 사용된다. 락 - 프리(lock-free)데이터 구조등의 다른 방식은 복잡할 뿐 아니라 특별한 경우에만 사용한다.

8.3 마지막 문제점 : 캐시 친화성(cache affinity)

• CPU에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB에 상당한 양의 상태정보를 올려놓게 된다. 다음번에 프로세스가 실행될 때 동일한 CPU에서 실행되는 것이 유리하다. 해당 CPU 캐시에 일부 정보가 이미 존재하고 있기 때문에 더 빨리 실행될 것이기 때문이다. 반면 프로세스가 매번 다른 CPU에서 실행되면 실행될 때마다 필요한 정보를 캐시에 다시 탑재해야만 하기 때문에 프로세스의 성능은 더 나빠질 것이다. 멀티프로세서 스케줄러는 스케줄링 결정을 내릴 때 캐시친화성을 고려해야 한다. 가능한 한 프로세스를 동일한 CPU에서 실행하려고 노력하는 방향으로 결정해야 한다.

8.4 단일 큐 스케줄링

단일 큐 멀티프로세스 스케줄링(SQMS : Single-Queue MultiProcessor Scheduling)

장점

• 단순하다. 기존 정책을 다시 CPU에서 동작하도록 하는데는 많은 변경이 필요치 않다.

단점

• 첫 번째 문제, 확장성(Scalability) 결여
  • 스케줄러가 다수의 CPU에서 제대로 동작하게 하기 위해 코드에 일정 형태의 락을 삽입한다. 락은 SQMS코드가 단일 큐를 접근할 때,(즉, 실행시킬 다음 작업을 찾을 때) 올바른 결과가 나오도록 한다.
  • 불행히 작은 성능을 크게 저하 시킬 수 있고, 시스템의 CPU개수가 증가 할 수록 더욱 그렇다. 단일 락에 대한 경쟁이 증가 할수록 시스템은 락에 점점 더 많은 시간을 소모하게 되고, 실제 필요한 일에 쓰는 시간이 줄어들게 된다.
• 두 번째 문제, 캐시친화성
  • 각 CPU는 공유 큐에서 다음 작업을 선택하기 때문에 각 작업은 CPU를 옮겨 다니게 된다. 캐시 친화성 관점에서 보면 잘못된 선택을 하는 것이다.
  • 이 문제의 해결을 위해 SQMS는 가능한 한 프로세스가 동일한 CPU에서 재 실행될 수 있도록 시도한다. 특정 작업들에 대해서 캐시 친화성을 고려하여 스케줄링하고 다른 작업들을 오버헤드를 균등하게 하기 위해 여러군데로 분산시키는 정책을 사용한다.
• 기존의 단일 CPU 스케줄러가있다면 하나의 큐 밖에 없기 때문에 구현이 간단하다. 그러나 동기화 오베헤드 때문에 이 방식은 확장성이 좋지 않고, 캐시 친화성에 문제가 있다.

8.5 멀티 큐 스케줄링

멀티 큐 멀티프로세서 스케줄링(MQMS : Multi-Queue MultiProcessor Scheduling)

• MQMS에서 기본적인 스케줄링 프레임 워크는 여러 개의 스케줄링 큐로 구성된다. 작업이 시스템에 들어가면 하나의 스케줄링 큐에 배치된다. 배치될 큐의 결정은 적당한 방법을 따른다. 그 후에는 각각이 독립적으로 스케줄 되기 때문에 단일 큐 방식에서 보았던 정보의 공유 및 동기화 문제를 피할 수 있다.
• MQMS가 SQMS에 비해 가지는 명확한 이점은 확장성이 좋다는 것이다. CPU개수가 증가할수록, 큐의 개수도 증가하므로 락과 캐시경합(Cache contention)은 더 이상 문제가 되지 않는다. 또한, MQMS는 본질적으로 캐시 친화적이다. 작업이 같은 CPU에서 계속 실행되기 떄문에 캐시에 저장된 내용을 재사용하는 이점을 얻게된다.
• 멀티 큐 기반 방식의 근본적인 문제는 워크로드의 불균형(load imbalance)이다. 불균형은 이주(migration)을 통해 워크로드 균형을 달성한다.
• 이주 필요 여부를 어떻게 결정할까?
  • 한 가지 기본 접근 방식은 작업훔치기(work stealing)라는 기술이다. 작업 훔치기에서는 작업의 개수가 낮은(소스) 큐가 가끔 다른(대상) 큐에 훨씬 많은 수의 작업이 있는지를 검사한다. 대상 큐가 소스 큐보다 더 가득 차있다면 워크로드 균형을 맞추기 위해 소스는 대상에서 하나 이상의 작업을 가져온다.
  • 물론 이런 방식에는 자연스러운 문제가 있다. 큐를 너무 자주 검사하면 높은 오버헤드로 확장성에 문제가 생기게 된다. 확장성은 멀티 큐 스케줄링의 가장 중요한 목적이다. 반면 다른 큐를 자주 검사하지 않으면 심각한 워크로드 불균형을 초래할 가능성이 있다.

8.6 Linux 멀티 프로세서 스케줄러

• O(1)과 CFS(Completely Fair Scheduler)는 멀티 큐를 BFS는 단일 큐를 사용하기 때문에 두 방식 모두 실제 시스템에서 성공적으로 사용할 수 있다는것을 보이고 있다.
• O(1) 스케줄러는 우선순위 기반 스케줄러로서 프로세스의 우선순위를 시간에 따라 변경하여 우선순위가 가장 높은 작업을 선택하여 다양한 목적을 만족시킨다. 특히, 상호작용을 가장 우선시 한다.
• CFS는 결정론적(deteministic) 비례배분(proportional share) 방식이다. 그러나 Earliest Eligible Virtual Deadline First(EEVDF)라고 알려진 더 복잡한 방식에 기반을 둔다.