여러 개의 CPU가 사용 가능 → 여러 스레드가 병렬로 실행 가능 → 부하 공유(load sharing) 가능
스케줄링 문제는 그에 상응하여 더욱 복잡해짐
다중 처리기란?
여러 개의 물리적 프로세서를 제공하는 시스템
각 프로세서에는 하나의 단일 코어 CPU가 포함되어 있음
최신 컴퓨팅 시스템에서의 다중 처리기는 아래의 아키텍처들을 사용 가능
다중 코어 CPU
다중 스레드 코어
NUMA 시스템
이기종 다중 처리
다중 처리기 스케줄링에 대한 접근 방법
다중 처리기 시스템의 CPU 스케줄링에 관한 해결 방법
비대칭 다중 처리(asymmetric multiprocessing)
마스터 서버라는 하나의 처리기가 모든 스케줄링 결정과 I/O 처리, 다른 시스템의 활동을 취급
다른 처리기들은 사용자 코드만을 수행
하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단
단점 : 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 될 수 있음
대칭 다중 처리(Symmetric Multi-Processing)(SMP)
다중 처리기를 지원하기 위한 표준 접근 방식이며 각 프로세서는 스스로 스케줄링할 수 있다.
각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링이 진행됨
스케줄 대상이 되는 스레드를 관리하기 위한 두 가지 전략을 제공
모든 스레드가 공통 준비큐에 있을 수 있다. 공통 준비 큐
공유 준비 큐에서 경쟁 조건이 생길 수 있다.
→ 두 개의 다른 프로세스가 동일한 스레드를 스케줄 하지 않도록, 큐에서 스레드가 없어지지 않도록 보장해야 함
각 프로세서는 자신만의 스레드 큐를 가질 수 있다. 각 코어가 큐를 가짐
각 프로세서가 자신만의 실행 큐에서 스레드를 스케줄 하도록 허용 → 공유 실행 큐와 같은 성능 문제가 발생하지 않음 → SMP를 지원하는 시스템에서 가장 일반적인 접근 방식
자신만의 프로세스별 큐가 있어서 캐시 메모리를 보다 효율적으로 사용할 수 있다.
큐마다 부하의 양이 다를 수 있다. → 균형 알고리즘을 통해 프로세서 간에 부하를 균등하게 만들 수 있다.
다중 코어 프로세서(Multicore Processors)
다중 코어 프로세서 : 동일한 물리적인 칩 안에 여러 개의 처리 코어를 장착
각 코어는 구조적인 상태를 유지하고 있어, 운영체제 입장에서는 개별적인 논리적 CPU로 보임
다중 코어 프로세서를 사용하는 SMP 시스템은 속도가 빠르고 적은 전력을 소모
각 CPU가 자신의 물리 칩을 가지는 시스템과 비교해서 상대적으로 빠른 것
다중 코어 프로세서는 스케줄링 문제를 복잡하게 한다.
메모리 스톨(memory stall)
메모리 스톨 : 프로세서가 메모리에 접근할 때 데이터가 가용해질 때까지 대기하는 것
다중 코어 프로세서는 메모리 스톨에 많은 시간을 허비한다.
발생 원인
최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 주로 발생함
캐시 미스(캐시 메모리에 없는 데이터를 액세스)로 인해 발생할 수도 있음
메모리 스톨
위 그림에서 프로세서는 메모리의 데이터를 사용할 수 있을 때까지 최대 50% 시간을 허비할 수 있음
메모리 스톨 해결 방안 - 칩 다중 스레딩
최근 많은 하드웨어 설계는 다중 스레드 처리 코어를 구현 → 하나의 코어에 2개 이상의 하드웨어 스레드가 할당됨
메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환
이중 스레드 처리 코어 → 스레드 0과 1의 실행이 인터리브
이중 스레드 처리
칩 다중 스레딩(chip mutli-threading, CMT)
운영체제 관점에서 각 하드웨어 스레드는 소프트웨어 스레드를 실행할 수 있는 논리적 CPU로 보임
←각 하드웨어 스레드는 명령어 포인터 및 레지스터 집합과 같은 구조적 상태를 유지하기 때문
칩 다중 스레딩
- 해당 그림에서, 프로세서에는 4개의 컴퓨팅 코어가 있으며 각 코어에 2개의 하드웨어 스레드
- 운영체제 관점에서 볼 때는 8개의 논리적 CPU가 존재
- Intel 프로세서는 `하이퍼-스레딩(동시 다중 스레딩,SMT)` 이라는 용어를 사용
- 똑같이 단일 하드웨어 코어에 여러 하드웨어 스레드를 할당하는 것
처리기를 다중 스레드화 하는 2가지 방법
거친(coarse-grained) 다중 스레딩
스레드가 긴 지연시간을 가진 이벤트가 발생할 때까지 한 코어에서 수행됨.
긴 지연시간을 가진 이벤트 : 메모리 스톨 등
긴 지연시간을 가진 이벤트에 의한 지연에 의해 코어는 다른 스레드를 실행하게 됨
프로세서 코어에서 다른 스레드가 수행되기 전에 명령어 파이프라인이 완전히 정리되어야 함 → 스레드 간 교환에는 비용이 많이 듦
새로운 스레드가 실행을 시작하면 자신의 명령어들로 파이프라인을 채움
세밀한(fine-grained) 다중 스레딩
명령어 주기의 경계에서 같이 좀 더 세밀한 정밀도를 가진 시점에서 스레드 교환이 발생
세밀한 시스템의 구조적 설계는 스레드 교환을 위한 회로를 포함 → 스레드 교환 간 비용이 적음
다중 스레드 다중 코어 프로세서의 2단계 스케줄링
물리적 코어의 자원은 하드웨어 스레드 간에 공유되어야 함 → 처리 코어는 한 번에 하나의 하드웨어 스레드만 실행할 수 있다. → 결과적으로 다중 스레드 다중 코어 프로세서는 두 개의 다른 스케줄링 단계가 필요
2단계 스케줄링
1단계 : 운영체제가 각 하드웨어 스레드에서 실행할 소프트웨어 스레드를 선택하는 스케줄링 결정
이 스케줄링 수준에 대해 운영체제는 임의의 스케줄링 알고리즘을 선택
2단계 : 각 코어가 실행할 하드웨어 스레드를 결정하는 방법 명시
채택할 수 있는 몇 가지 전략이 존재
라운드 로빈 알고리즘 사용하여 처리 코어에 하드웨어 스레드를 스케줄 하는 것
가장 간단한 방법
UltraSPARC T3에 의해 채택된 접근법
각 하드웨어 스레드에는 0~7까지의 동적 긴급도가 배정(0 : 가장 낮음, 7: 가장 높음)
코어당 2개의 하드웨어 관리 스레드를 가준 이중 코어 프로세서인 Intel Itanium에서 사용
스레드 교환을 촉발할 수 있는 5가지 이벤트를 식별
이벤트 발생 시 → 스레드-교환 회로가 두 스레드 중 긴급도가 더 높은 스레드를 처리 코어에서 실행
1단계와 2단계가 상호배타적이지 않아도 된다. → 즉 동시에 발생해도 된다.
상호배타적 : 한 사건이 발생하면 다른 사건이 일어날 수 없는 것.
예 : CPU에 2개의 처리 코어가 있고 각 코어에 2개의 하드웨어 스레드가 있는 경우
이 시스템에서 두 개의 소프트웨어 스레드가 동일한 코어에서 실행되도록 스케줄 됨 → 프로세서 자원을 공유해야 하므로 다른 코어에서 스케줄 될 때보다 느리게 진행될 수 있음
운영체제가 프로세서 자원 공유 수준을 알고 있으면 자원을 공유하지 않는 논리 프로세서에 소프트웨어 스레드를 스케줄 할 수 있다.
부하 균등화(Load Balancing)
SMP 시스템에서 처리기가 여러 개인 것을 최대한 활용하려면, 부하를 균등하게 배분하는 것이 중요
부하 균등화 : SMP 시스템의 모든 처리기 사이에 부하가 고르게 배분되도록 시도하는 것
각 처리기가 실행할 스레드를 위한 자신만의 준비 큐를 가지고 있는 시스템에서만 필요한 기능임
공통의 실행 큐만 있는 시스템에서는 한 처리기가 쉬게 되면 곧바로 공통큐에서 새로운 프로세스를 선택하기 때문에 부하 균등화를 필요하지 않음
부하 균등화 방식
push 이주(migration) 방식 : 특정 태스크가 주기적으로 각 처리기의 부하를 검사
불균형 상태로 밝혀지면 과부하인 처리기에서 쉬고 있거나 한가한 처리기로 스레드를 이동(push) → 부하 분배
pull 이주(migration) 방식 : 쉬고 있는 처리기가 바쁜 처리기를 기다리고 있는 프로세스를 pull
push와 pull은 서로 상호 배타적일 필요 없음 → 실제로 부하 균등화 시스템에서 병렬적으로 구현
예 : Linux CFS 스케줄러, FreeBSD 시스템에서 가용한 ULE 스케줄러는 두 방식을 모두 구현
균등 부하의 관점
균등 부하의 개념은 다른 의미를 가질 수 있다.
모든 큐에 대략 같은 수의 스레드가 있어야 한다.
균등이란 모든 큐에 스레드 우선순위를 균등하게 분배해야 한다.
이러한 전략 중 어느 것도 충분하지 않을 수도 있다.
이러한 전략들은 스케줄링 알고리즘의 목표와 상충할 수 있다.
처리기 선호도(Processor Affinity)
스레드가 특정 처리기에서 실행중일 때 → 스레드에 의해 가장 최근에 접근된 데이터가 그 처리기의 캐시를 채우게 됨 → 스레드에 의한 잇따른 메모리 접근은 캐시 메모리에서 만족한다.(warm cache)
스레드가 다른 처리기로 이주한다면?
첫 번째 프로세서의 캐시 메모리 내용은 무효화 및 두 번째 프로세서의 캐시는 다시 채워져야 함 → 캐시 무효화 및 다시 채우는 비용은 많이 든다. → 이주 대신 같은 프로세서에서 계속 실행시키면서 warm cache 이용하려 함 → 프로세서 선호도
다른 프로세서로 이동시키지 않고 같은 프로세서에서 실행시키는 것이 더 이득이기 때문
SMP를 지원하는 대부분의 운영체제에서 사용하는 방법
프로세스는 현재 실행 중인 프로세서에 대한 선호도를 보인다.
공통 준비 큐 vs 각 큐를 가질 경우
공통 준비 큐 접근 방식
선택된 스레드는 어느 처리기에선 실행될 수 있다. → 스레드가 새 프로세서에 스케줄 되면 해당 프로세서의 캐시를 다시 채워야 한다.
프로세서마다 자신만의 큐를 사용
스레드는 항상 동일한 프로세서에 스케줄 되므로 warm cache의 내용을 활용 가능 → 기본적으로 프로세서 별 준비 큐는 프로세서 선호도를 무료로 제공
처리기 선호도의 여러 형태
약한 선호도 : 운영체제가 같은 처리기에서 프로세스를 실행시키기 위해 노력하지만 보장하지는 않음
운영체제는 프로세스를 특정 처리기에서 실행시키려고 하지만 처리기 사이를 이주하는 것이 가능
강한 선호도 : 프로세스는 자신이 실행될 처리기 집합을 명시할 수 있는 시스템콜
Linux 같은 몇몇 시스템이 사용
대부분의 시스템이 약한 선호도와 강한 선호도를 동시에 지원
Linux → 약한 선호도 지원 및 강한 선호도를 지원하는 sched_setafficnity() 제공
sched_setafficnity() : 스레드가 실행할 수 있는 CPU 집합을 지정할 수 있게 함
시스템의 메인 메모리 아키텍처와 프로세스 선호도 문제
시스템의 메인 메모리 아키텍처는 프로세서 선호도 문제에 영향을 줄 수 있다.
각각 고유한 CPU와 로컬 메모리를 가진 두 개의 물리적 프로세서 칩이 있는 NUMA를 특징으로 하는 아키텍처
모든 CPU가 하나의 물리적 주소 공간을 공유할 수 있음
CPU는 다른 CPU의 로컬 메모리보다 자신의 로컬 메모리에 더 빠르게 액세스 할 수 있다.
운영체제의 CPU 스케줄러 및 메모리 배치 알고리즘이 NUMA를 인식하고 협력하는 경우
특정 CPU에 스케줄 된 스레드를 CPU가 있는 위치에 가장 가까운 메모리에 할당하여 가능한 가장 빠른 메모리 액세스를 제공할 수 있다.
NUMA와 CPU 스케줄링
부하 균등화와 메모리 액세스 시간 최소화 사이에는 갈등이 생긴다.
프로세서 간에 스레드를 이주하면 NUMA 시스템에서 손해가 발생할 수 있다.
이 경우 스레드는 더 긴 메모리 액세스 시간이 필요한 프로세서로 이동될 수 있다. → 현대 다중 코어 NUMA 시스템에 대한 스케줄링 알고리즘은 상당히 복잡해짐
이기종 다중 처리(Heterogeneous Multiprocessing, HMP)
모바일 시스템은 현재 다중 코어 아키텍처가 채택되어 있지만 일부 시스템은 이기종 다중 처리로 설계
동일한 명령어 집합을 실행
전력 소비를 유휴 수준으로 조정하는 기능을 포함하여 클록 속도 및 전력 관리 측면에서 차이가 나는 코어를 사용하여 설계된 것
시스템 및 사용자 태스크는 모든 코어에서 실행될 수 있음 → 비대칭 다중 처리 형태는 아니다.
HMP의 목적
작업의 특정 요구에 따라 특정 코어에 작업을 할당하여 전력 소비를 더 잘 관리하는 것
big.LITTLE
이기종 다중 처리를 지원하는 ARM 프로세서의 경우 이 유형의 아키텍처를 big.LITTLE이라고 부름
고성능 big 코어 + 에너지 효율적인 LITTLE 코어
Big 코어 → 많은 에너지를 소비하므로 짧은 시간 동안만 사용해야 함
little 코어 → 더 적은 에너지를 사용하므로 더 오랫동안 사용할 수 있다.
장점
긴 시간 동안 실행해야 할 작업을 little코어에 할당하여 배터리 충전을 보존하는데 도움
