Multiple-Processor Scheduling (다중 처리기 스케줄링)

Multiple-Processor (다중 처리기)

• 여러 개의 CPU가 있는 다중 처리기 시스템

 

1. 비대칭 다중 처리 (Asymmetric Multiprocessing)

오직 하나의 코어만 시스템 자료구조에 접근한다.

• 하나의 처리기만 시스템 자료구조에 접근하여 처리기 간의 자료들을 공유할 필요 없다.
•  단점
  • master server가 전체 시스템 성능을 저하할 수 있는 병목 발생할 수 있다.

 

2. 대칭 다중 처리 (Symmetric Multiprocessing : SMP)

각 처리기(Processor)가 독자적인 스케줄링을 수행하는 방식

• 다중 처리기를 지원하기 위한 표준 접근 방식
• 각 Processor는 스스로 스케줄링할 수 있다.
• 스케줄 대상이 되는 스레드를 관리하기 위한 두 가지 가능한 전략
  • 모든 스레드가 공통 준비 큐에 있을 수 있다. (common ready queue)
  • 각 프로세서는 자신만의 스레드 큐를 가질 수 있다. (per-core run queues)

 

3. 부하 균등화 (Load Balancing)

부하가 각 처리기에서 균등하도록 배분하는 시스템

• Processor가 하나 이상이라는 것을 최대한 활용하려면, 부하를 모든 처리기에 균등하게 배분하는 것이 중요하다.
• push migration과 pull migration은 서로 상호 배타적인 것이 아니다. 실제로 병렬적으로 구현된다.

(1) push migration

• 특정 작업이 주기적으로 각 처리기의 부하를 검사하고 만일 불균형 상태로 밝혀지면 과부하인 처리기에서 상대적으로 덜 바쁜 처리기로 프로세스를 이동시킨다. (push)

(2) pull migration

• 쉬고 있는 처리기가 바쁜 처리기의 처리를 기다리고 있는 프로세스를 가져온다. (pull)

 

 

4. 처리기 선호도 (Processor Affinity)

Process가 Processor 이주(migration)를 하지 않고 같은 Processor에서 계속 실행하려는 정도

• 프로세스가 수행될 때는 가장 최근에 접근한 데이터가 해당 프로세서(CPU)의 cache에 올라간다.
• 프로세스가 migration 되면 원래 사용하던 처리기에서의 캐시 내용을 사용할 수 없게 된다.
• 이 때문에 프로세서를 이주하는 것은 상당한 비용이 드는 작업이다.
• 그러므로 migration을 피하고 대신 같은 처리기에서 프로세스를 실행시키려고 한다.

(1) 약한 선호도 (soft Affinity)

• 가급적 동일 프로세서에서 수행하려 하나, 이주(migration)를 허용한다.

(2) 강한 선호도 (Hard Affinity)

• 시스템 호출을 사용하여, 프로세스는 처리기 사이를 이주하지 않는다고 명시할 수 있다.
• migration을 금지한다.

(3) NUMA(Non-Uniform Memory Access) 구조

• 각각 고유한 CPU와 Memory를 가진다.
• 다른 Processor(CPU)의 Memory보다 자신의 Memory에 더 빠르게 접근할 수 있다.
• 운영체제의 CPU 스케줄러 및 메모리 배치 알고리즘이 NUMA를 인식하는 경우 특정 CPU에 스케줄 된 스레드를 CPU가 있는 위치에 가장 가까운 메모리에 할당한다.

 

5. 다중 코어 프로세서 (Multicore Processors)

하나의 Processor 칩 내에 여러 개의 처리 코어를 내장한다.

• 각 코어는 구조적인 상태를 유지하고 있어서 운영체제 입장에서는 개별적인 논리적 CPU처럼 보이게 된다.
• 다중 코어 프로세서는 코어가 하나만 가지고 있는 프로세서보다 속도도 빠르고 적은 전력을 소모한다.

(1) 메모리 스톨 (Memory Stall)

프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리는 것

• Processor가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 주로 발생
• 또는 캐시 미스(캐시 메모리에 없는 데이터를 접근)로 인해 발생

(2) 칩 다중 스레드 (Chip Multithreading : CMT)

단일 하드웨어 코어에 여러 하드웨어 스레드를 할당하는 것

• 메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환할 수 있다.
• memory stall 문제를 해결할 수 있다.
• OS 관점에서, 각각의 하드웨어 스레드는 소프트웨어 스레드를 동작시키기 위해 사용 가능한 논리적 프로세서로 보인다.
• Ex) 프로세서에 4개의 컴퓨팅 코어가 있으며 각 코어에 2개의 하드웨어 스레드가 있다면 OS 관점에서 볼 때 8개의 논리적 CPU가 있다.

(3) 멀티 스레드 다중코어 2단계 스케줄링

• 물리적 코어의 자원은 하드웨어 스레드 간에 공유되어야 하므로 처리 코어는 한 번에 하나의 하드웨어 스레드만 실행할 수 있다.

• 위 그림은 하나의 코어에 2개의 하드웨어 thread를 할당하는 코어 시스템이라 가정한다.
• level 1 : 운영체제가 논리적 CPU에서 동작할 소프트웨어 스레드를 결정한다 - CPU 스케줄링
• level 2 : 각 코어는 물리적 코어에서 실행될 하드웨어 스레드를 결정한다.