[운영체제] 멀티 프로세서 스케줄링(Multiple Processor Scdeduling)

참고도서: Operating System Concepts (10/E) Abraham Silberschatz, Peter B. Galvin, Greg Gagne

이전 수업에서 다뤘던 내용은 모두 단일한 프로세서와 단일한 코어인 환경에서의 스케줄링 전략들이었다. 하지만 현재 상황에서는 프로세서를 하나만 쓰거나 코어를 하나만 사용하는 일은 전무하다. 실제 상황에서는 여러 개의 프로세서가 사용되는것이 일반적이기 때문에 이 경우에서의 스케줄링 기법들을 보자.

Types

프로세서가 여러개 있는 상황에서는 프로세스를 위한 ready queue 를 어떻게 관리할 것인지, 그리고 각 프로세서가 어떤 역할을 할 것인지에 따라 두 종류로 기법을 나눌 수 있다.

1. Asymmetric Multiprocessing : 여러 프로세서 중 하나의 프로세서가 스케줄링 과정을 처리한다. 나머지 프로세서들은 master 가 되는 프로세서에게 역할을 분담받아 작업을 수행한다. Master 프로세서에게 너무 많은 역할이 주어지게 되면 bottleneck 이 발생할 여지가 있다.
2. Symmetric Multiprocessing(SMP) : 가장 보편적으로 사용하는 기법이다. 모든 프로세서가 각자의 스케줄링을 하게되는데, 이때 준비 큐의 상태에 따라 다시 두 종류로 나뉜다. 한 종류는 프로세서들의 공통된 준비 큐를 사용하는 방법이고, 다른 방법은 각 프로세서마다 각자의 준비큐를 사용하는 방법이다.

Mulicore Processor

위에서 다뤘던 멀티프로세서는 한 시스템안에 다수의 CPU가 있고, 각 프로세서마다 각각 단일한 코어를 가지고 있는 경우였다. 하지만 지금은 한 프로세서 안에 여러 코어가 포함되고 이 코어들이 각각 하나의 프로세서처럼 동작하게 된다.

Scheduling in Multicore Processor

최신의 프로세서들은 엄청난 속도로 작업을 처리한다. 이런 발전된 속도 때문에 오히려 한가지 이슈가 생겼는데, 프로세서가 메모리에 접근하게 되면, 데이터가 곧바로 준비되어 있지 않고 어느정도 기다려야하는 상황이 된 것이다. 이렇게 데이터가 사용이 가능하기까지 기다려야 하는 현상을 Memory Stall 이라고 한다.

이런 이슈를 해결하기 위해서 프로세서의 각 core 가 다수의 하드웨어 thread 를 가질 수 있도록 하는 설계전략이 사용된다. 하나의 스레드가 Memory Stall 과정에서 중단되면, 다른 스레드를 사용하여 다른 작업을 수행하는 것이다. 인텔 프로세서에서 이렇게 하나으 코어가 여러개의 하드웨어 스레드를 가지게 하는 것을 Hyper Threading 이라고 한다.

한 코어가 여러 스레드를 가지게 할 때, 두 가지 방법으로 설계할 수 있다.

1. Coarse-grained Multithreading : 이 방식에서는 스레드가 지연시간이 긴 어떤 이벤트를 만날 때까지 계속 실행된다. 그리고 Memory stall 같은 지연시간이 긴 이벤트를 만나면 다른 스레드로 전환해서 작업을 수행한다. 그리고 스레드를 교체하는 과정에서 파이프를 완전히 비우고 새로운 스레드의 명령어들로 채워주어야 하기 때문에 스레드의 교환비용이 크다.
2. Fine-grained Multithreading : 이 방식에서는 스레드를 교체하는 과정에서 명령어어 등을 보고 더 정밀한 시점에서 스레드 교환을 진행한다. 따라서 스레드의 교환비용이 Coarse-grained 방식보다는 적게 된다.

Load Balancing

다중코어 시스템에서 각 프로세서가 독자적인 준비큐를 가지고 운영될 때, 각각의 코어에 작업이 균등하게 분배되는 것이 매우 중요할 것이다. 어떤 코어는 너무 많은 일을 하고, 어떤 코어는 아무 일도 하고 있지 않다면, 시스템의 효율성이 크게 떨어질 것이다. 이렇게 모든 프로세서에 대해서 작업이 균등하게 분배되게 하는 것을 Load Balancing 이라고 한다. 그리고 이것이 가능하게 하기 위해서 두 방식을 사용한다.

1. Push Migration : 주기적으로 각 프로세서의 과부하를 검사하고 균등하게 배분된 상태가 아니라면 과부하된 프로세서에서 작업이 상대적으로 적은 프로세서로 스레드를 이동시키는 작업
2. Pull Migration : 작업이 덜한 프로세서가 과부하된 프로세서를 기다리다가 프로세스를 자신에게 할당하는 작업

Processor Affininty

컴퓨터 구조에서 배웠던 것 처럼, CPU안에는 고속메모리인 캐시가 있어서 자주 사용되는 리소스들을 주기적으로 교환하면서 넣어준다. SMP에서는 여러개의 프로세서가 작업을 함께 수행하고 있는 구조이기 때문에, 하나 스레드에서 실행되던 프로세스가 다른 프로세스로 이동해서 실행되는 경우도 있을 것이다.

그런데 만약 이런 상황이 발생하게 되면, 새로은 프로세스를 이주받은 프로세서의 캐시가 새로운 프로세스의 정보로 초기화 되어야 할 것이고, 기존에 프로세스를 실행하던 프로세서의 캐시 역시 무효화되는 문제가 생긴다. 따라서 대부분의 운영체제에서는 같은 프로세서가 동일한 프로세스에 대한 작업을 수행하도록 하는데, 이것을 Processor Affinity 라고 한다. Processor Affinity는 그 강도에 따라 종류가 두 가지로 나뉜다.

1. Soft Affinity : 운영체제가 같은 프로세스를 동일한 프로세서에서 계속 실행시키려고 시도하지만 그것을 완전히 보장하지는 않는다.
2. Hard Affinity : System call을 통해서 프로세스가 자신이 처리될 프로세서를 명시한다.

Non-Uniform Memory Access(NUMA) Archetecture

NUMA 아키텍쳐로 불리는 이 구조는 시스템 안에 있는 모든 프로세서가 메모리 공간을 공유하게 되지만 각 프로세서 내부에 있는 메모리에는 더 빠른 접근을 보이는 시스템이다. 이 시스템구조는 운영체제와 함께 특정한 스레드를 계속해서 가장 가까이있는 프로세서에 할당하게 된다. 이렇게 하면 지속적으로 메모리 접근을 빠른 속도로 유지할 수 있게 된다.

Conflicts

그렇지만 위에서 설명한 기법들을 서로 충돌하는 부분들이 있다. Professor Affinity 를 위해 같은 프로세서에 계속해서 같은 프로세스를 할당하게 되면, Load Balancing 을 하는 것이 의미가 없어진다, 또, NUMA System 을 사용하는 것 역시 Load Balancing 관점에서는 효과적이지 않다.

Heterogeneouse Multiprocessing

HMP 로 불리는 이기종 다중 처리 방식은 여러 프로세스간에 속도와 전력 소비에 차이를 두게끔 설계하는 것이다. 예를 들어, 고성능이 처리가 요구되지 않는 작업들은 굳이 좋은 프로세서에서 실행시킬 필요 없이 전력을 덜 소모하지만 성능은 떨어지는 프로세스에 할당하고, 고성능 작업이 요구될 때는 고성능 프로세스를 사용한다. 이런 방식을 사용하면, 모바일 시스템처럼 전력소모량이 크게 고려되는 환경에서 전력의 효과적인 운용이 가능해진다.