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

 

여러 CPU가 사용 가능하면, 여러 스레드가 병렬로 실행될 수 있으므로 부하 공유(load sharing)가 가능하다.

 

multiprocessor라는 용어는 다음과 같은 시스템 아키텍처에서 사용할 수 있다.

1) multicore CPUs

2) multithreaded cores

3) NUMA systems

4) Heterogeneous multiprocessing

 

이때, 1), 2), 3)의 경우에는 각 코어의 동작이 기능적으로 동일하고, 4)의 경우에는 각 코어의 동작이 기능적으로 동일하지 않다.

 

 

 

 

 

 

multiprocessor 스케줄링에 대한 접근 방법

---

 

multiprocessor 시스템에서의 CPU 스케줄링 방법

 

1. 비대칭 다중 처리(asymmetric multiprocessing, AMP)

master server라는 하나의 프로세서가 모두 처리하고, 나머지 프로세서는 사용자 코드만을 실행한다.

(모두 처리한다는 것은 모든 스케줄링 결정과 I/O처리, 다른 시스템의 활동을 모두 취급하는 것이다.)

 

장점- 하나의 코어만 시스템 자료구조에 접근하고, 데이터 공유를 배제하므로 간단하다.

단점 - master server가 시스템의 성능을 저하시킬 수 있는 병목이 될 수 있다.

 

 

2. 대칭 다중 처리(symmetric multiprocessing, SMP)

각 프로세서는 스스로 스케줄링 할 수 있다. 따라서 각 프로세서의 스케줄러가 ready큐를 확인하고, 실행할 스레드를 선택한다.

 

스케줄링 대상이 되는 스레드를 관리하기 위한 두 가지 전략

 

1) 모든 스레드가 공통 ready 큐에 존재한다. (common ready queue)

- 공통 ready 큐에 경쟁 조건이 발생할 수 있으므로, 다른 프로세서에 동일한 스레드를 스케줄링하지 않도록, 큐에서 스레드가 없어지지 않도록 보장해야 한다.

 

2) 각 프로세서는 자신만의 스레드 큐를 가진다. (per-core run queue)

- 큐 공유로 인한 성능 저하가 없다.

- 캐시 메모리를 더 효율적으로 사용할 수 있다.(한 프로세스는 하나의 코어에서 실행되기 때문이다.)

- 큐마다 부하의 양이 다르므로 부하를 균등하게 하는 균형 알고리즘이 필요하다.

  (놀고 있는 코어에게 실행 중인 코어의 프로세스를 넘겨주는 알고리즘)

 

 

 

 

 

multicore 프로세서

---

 

SMP 시스템은 여러 물리 프로세서들을 제공하여 여러 프로세스들이 병렬로 실행되게 한다.

 

하지만 오늘날의 컴퓨터 하드웨어는 하나의 물리적 칩 안에 여러 개의 코어를 장착하고 있는 multicore 프로세서이다.

 

이때, 각 코어는 구조적 상태(instruction pointer, register set)을 가지고 있어서 OS에게는 개별적인 논리적 CPU처럼 보이게 된다. 

 

 

 

multicore 프로세서는 스케줄링이 복잡하다.

 

프로세서가 메모리에 접근할 때, 데이터가 사용 가능해지기를 기다리며 많은 시간을 허비한다. 이를 memory stall이라고 한다.

 

memory stall은 프로세서가 메모리보다 훨씬 빠른 속도로 작동함에 의해, 캐시 메모리에 없는 데이터에 접근하는 cache miss에 의해 발생한다.

 

 

 

memory stall을 해결하기 위해서 최근의 많은 하드웨어 설계는 multithreaded processig core를 구현한다.

 

multithreaded processing core는 둘 이상의 하드웨어 스레드를 하나의 코어에 할당하는 것으로, 만약 한 하드웨어 스레드가 메모리를 기다리며 중단되면, 코어가 다른 스레드로 전환할 수 있다.

 

OS는 각 하드웨어 스레드를 논리적 CPU로 보고 스케줄링한다.

 

이 기술은 chip multithreading(CMT)로 알려져 있다.

 

예시) 프로세서는 4개의 컴퓨팅 코어가 있고, 각 코어는 2개의 하드웨어 스레드를 가진다. 이때, 운영체제의 관점에서 8개의 논리적 CPU가 있다.

 

Operating System Concepts by Silberschatz A. & Galvin P. B. & Gagne G.

 

 

 

multithreadig의 두 가지 방법

 

1. coarse-grained multithreading(거친 멀티스레딩)

스레드가 memory stall과 같은 긴 지연시간을 가진 이벤트가 발생할 때까지 한 코어에서 실행되다가, 이벤트 발생 시 코어는 다른 스레드를 실행한다.

 

이 방식은 코어에서 다른 스레드가 수행되기 전에 파이프라인을 비워져야 하므로, 교환 비용(switching cost)이 많이 든다.

 

 

2. fine-grained multithreading(세밀한 멀티스레딩)

instruction cycle의 경계와 같이 좀 더 세밀한 단위에서 스레드 교환이 발생한다.

 

이 방식은 구조적인 설계에서 스레드 교환 회로를 포함하므로, 교환 비용이 적어진다.

 

 

 

스케줄링의 두 가지 단계

 

1. OS가 각 하드웨어 스레드에서 실행할 소프트웨어 스레드를 선택하는 단계

OS는 임의의 스케줄링 알고리즘을 사용할 수 있다.

 

 

2. 각 코어가 실행할 하드웨어 스레드를 선택하는 단계

이 상황에서 선택할 수 있는 두 가지 전략이 있다.

 

1) round-robin 알고리즘을 사용하여 코어에 하드웨어 스레드를 스케줄링한다.

2) 각 하드웨어 스레드에는 0(highest) - 7(lowest)사이의 긴급도가 배정되고, 스레드 교환을 발생시키는 다섯 가지 이벤트 중 하나가 발생하면, 긴급도를 비교해서 높은 긴급도를 가진 스레드를  코어에 스케줄링한다.

 

 

 

1단계에서 OS의 스케줄러가 자원 공유 정보를 안다면 효과적으로 스케줄링 할 수 있다.

 

만약 CPU가 두 개의 코어를 가지고, 각 코어에 두 개의 하드웨어 스레드가 있고, 두 개의 소프트웨어 스레드가 실행 중이라고 가정하면,

 

두 개의 소프트웨어 스레드가 동일한 코어 혹은 다른 코어에서 실행될 수 있다.

 

동일한 코어에서 실행되는 경우, 프로세서의 자원을 공유해야 하므로 다른 코어에서 실행될 때보다 더 느리게 진행될 수 있다.

 

이때, OS가 프로세서 자원 공유 정보를 안다면, 자원을 공유하지 않는 논리적 프로레서에 스레드를 스케줄링할 수 있다.