프로세스 스케줄링_5 (멀티프로세서 스케줄링)

요즘 나오는 대부분의 컴퓨터들은 하나의 프로세서(CPU)로만 동작하는 것이 아니라, 여러개의 프로세서들로 이루어져있다.

 

멀티프로세서 환경에서 스케줄링 시 고려해야 할 점들을 한번 짚어보자.

 

 

1. multiple-processor

 

먼저, 멀티프로세서의 종류와 특징에 대하여 한번 살펴보자.

 

• 프로세싱 기법에 따른 구분

1) Asymmetric multiprocessing

 

- 하나의 master 프로세스가 다른 프로세스들을 관리감독하는 형태

- master 프로세서가 load balancing을 다 결정한다. (load balancing은 조금 있다가 나온다.)

 

2) Symmetric multiprocessing (SMP)

 

- 각각의 프로세스가 동등한 권한으로 프로세싱하는 형태

- 각각의 프로세서는 각자 스케줄링을 진행한다.

- 프로세스들은 하나의 ready queue에 저장되어있거나, 각각의 프로세서의 private queue에 저장되어있다.

- 대부분의 멀티프로세스가 이러한 형태다.

 

 

• 메모리 접근에 따른 구분

1) Uniform Memory Access

 

- 하나의 공유된 메모리에 여러개의 프로세서가 할당된 형태.

- 하나의 메모리를 공유하여 사용한다.

- 프로세서가 어느 메모리를 참조하든 접근속도가 동일하다

 

2) Non-Uniform Memory Access (NUMA)

 

NUMA

 

- 각각의 프로세서에 메모리가 따로 담겨있는 형태.

- 만약 다른 프로세서에서 자신의 메모리를 참조할 때 속도가 느리므로, 스케줄링 시 이를 고려해주어야 한다.

- 이 때 필요한 개념이 Affinity 이다.

 

 

 

2. Processor Affinity

 

프로세스 스케줄링 시에, 특정 프로세서에 지정을 해주는것. 프로세스는 특정 프로세서에서만 실행되게 된다.

 

프로세스는 현재 돌고있는 프로세서의 메모리에 address space등의 메모리를 차지할 것이다. (NUMA의 경우)

 

이 때, 다른 프로세서의 메모리에 있는 데이터를 참조한다면, 시간이 오래걸릴것이다.

 

따라서 자신이 현재 돌고있는 프로세서의 메모리와, 자신이 접근하려는 데이터가 있는 메모리를 같도록 만들어줄 때 Processor Affinity를 활용하기도 한다.

 

1) soft Affinity : 같은 프로세서에서 돌 수 있도록 priority를 높여주는 등 노력은 하지만, 보장은 안되는 경우.

 

2) hard Affinity : 특정 프로세서에만 돌도록 완전히 보장시켜주는 경우.

 

 

 

3. Load balancing

 

특정 프로세서(CPU)가 너무 많은 프로세스를 돌린다 싶으면, 스케줄러가 적절히 분배해주는 행위.

 

processor Affinity 등에 의해 특정 프로세서가 너무 많은 프로세스를 돌리는 경우에, 스케줄러가 적절히 분배해주는 것을 load balancing이라 한다. 앞서 말했듯이 Asymmetric multiprocessor에서는 master 프로세서가 load balancing 해준다.

 

1) Push migration : 바쁜 프로세서가 자기의 일을 던지는 것.

 

2) Pull migration : 노는 프로세서가 다른 일 가져오는 것.

 

 

 

4. 멀티코어 프로세서

 

앞서 살펴본 경우는, 하나의 컴퓨터에 여러개의 프로세서가 있는 경우이다. 이제부터는 하나의 프로세서에 여러개의 코어가 있는 경우를 살펴보자.

 

한 프로세서 내에있는 코어들은 메모리를 공유할 것이다. (e.g. the last level cache (LLC))

 

이 때, 메모리에서 데이터를 가져오는 동안, 코어들이 잠시동안 동작을 멈추는데 이것을 Memory Stall 이라고 한다.

 

 

 

5. 멀티쓰레딩

 

보통 하나의 코어에 하나의 쓰레드가 실행된다고 알고 있었다. 하지만, Intel사의 hypherthreading과 같은 경우, 하나의 코어에 여러개의 쓰레드가 실행된다.

 

그 원리는 앞서 살펴본 memory stall을 이용하는 것이다. 하나의 코어가 메모리에 접근하는동안, 다른 코어를 실행시켜주는 것인데, 그림으로 나타내보면 아래와 같다.

 

Multi Threading

 

 

 

6. 스케줄러의 종류

 

1) Short-term Scheduler (= CPU Scheduler)

 

- 다음틱에 어떤 프로세스가 CPU에 할당될 지 고르는 스케줄러

- 틱의 간격이 매우 짧기 때문에, 굉장히 빠르고 overhead가 낮아야한다.

- 때로는 시스템의 유일한 스케줄러가 될 수도 있다.

 

2) Long-term Scheduler (= Job Scheduler)

 

- 어느 프로세스가 ready queue에 들어갈지 결정하는 스케줄러

- 즉, 멀티 프로그래밍의 degree를 정하는 스케줄러

- CPU 스케줄러에 비해, 덜 빈번하게 사용한다.

- CPU와 I/O device를 빡세게 활용하기 위해서 잘 고려해야한다.

 

3) Midum-term Scheduler

 

- Long-term Scheduler는 멀티프로그래밍의 degree를 올려주기만 한다면, 이 스케줄러는 degree를 내려주는 역할을 한다.

- 메모리에서 프로세스를 내리고, 다시 disk에 집어넣는 역할을 한다.

- swapping 기법을 이용한다.

 

 

 

7. 모바일에서의 멀티태스킹

 

어떤 모바일 환경에서는 한번에 오직 하나만의 프로세스만 실행시켜준다. (나머지는 그냥 대기)

 

멀티태스킹을 지원하는 환경에서도, foreground에 있는 프로세스를 background에 있는 프로세스보다 빠르게 만들어주는 경우가 많다.

 

 

 

8. Algorithm Evaluation

 

만약 자신이 만든 CPU 스케줄러의 알고리즘을 평가하고 싶다면, 다음과 같은 방법들이 있다.

 

1) Deterministic evaluation : 프로세스 진입시점, lifespan등이 고정되어있을 경우, 직접 그려서 계산해보는 방법

2) Queuing Model : ready queue를 수학적으로 모델링하여 평가

3) Simulation : 직접 데이터를 줘서 시뮬레이션 돌려보는 방법

4) Implementation : 직접 실제 컴퓨터에 구현해보는 방법

 

 

오늘 배운 내용을 정리해보면,

 

1. 멀티프로세서 환경에서 스케줄링 시 고려해야 할 점들이 많다. (load balancing, processor affinity)

 

2. 멀티코어 환경에서 하나의 코어에 멀티 쓰레딩을 사용할 수 있다. (memory stall 이용)

 

3. 스케줄러는 크게 Short-term, long-term, midium Scheduler로 구분할 수 있다.

 

 

본 내용은 공부하며 정리한 것으로, 오류가 있을 수 있습니다.