다중 프로세서 스케줄링
다중 프로세서 스케줄링 접근 방식
다중 프로세서 시스템에서 CPU 스케줄링에는 몇 가지 접근 방식이 있습니다.
비대칭 다중 처리 (Asymmetric Multiprocessing)
이 방식에서는 모든 스케줄링 결정, I/O 처리, 기타 시스템 활동을 단일 프로세서(마스터 서버)가 담당합니다. 다른 프로세서들은 사용자 코드만 실행합니다. 이 접근 방식은 하나의 코어만 시스템 데이터 구조에 접근하므로 데이터 공유의 필요성이 줄어들어 구현이 간단합니다. 그러나 마스터 서버가 잠재적인 병목 지점이 되어 전체 시스템 성능이 저하될 수 있다는 단점이 있습니다.
대칭 다중 처리 (Symmetric Multiprocessing, SMP)
다중 프로세서 지원을 위한 표준 접근 방식은 대칭 다중 처리입니다. 여기서는 각 프로세서가 자체 스케줄링을 수행합니다. 각 프로세서의 스케줄러는 준비 큐를 검사하고 실행할 스레드를 선택합니다. 스케줄링 가능한 스레드를 구성하는 두 가지 전략이 있습니다:
모든 스레드가 공통 준비 큐에 있을 수 있습니다.
각 프로세서가 자체적인 스레드 큐를 가질 수 있습니다.
첫 번째 옵션을 선택하면 공유 준비 큐에서 잠재적인 경쟁 조건이 발생하므로, 두 개의 개별 프로세서가 동일한 스레드를 스케줄링하지 않고 큐에서 스레드가 손실되지 않도록 해야 합니다. 잠금 메커니즘을 사용하여 공통 준비 큐를 보호할 수 있지만, 모든 접근에 잠금 소유권이 필요하므로 성능 병목이 될 수 있습니다. 두 번째 옵션은 각 프로세서가 자체 실행 큐에서 스레드를 스케줄링하도록 허용하므로 공유 실행 큐와 관련된 잠재적인 성능 문제에 영향을 받지 않습니다. 따라서 이는 SMP를 지원하는 시스템에서 가장 일반적인 접근 방식입니다.
멀티코어 프로세서
전통적으로 SMP 시스템은 여러 물리적 프로세서를 제공하여 여러 프로세스를 병렬로 실행할 수 있도록 했습니다. 그러나 대부분의 현대 컴퓨터 하드웨어는 이제 동일한 물리적 칩에 여러 컴퓨팅 코어를 배치하여 멀티코어 프로세서를 만듭니다. 각 코어는 자체 아키텍처 상태를 유지하므로 운영체제에는 별도의 논리적 CPU로 보입니다.
멀티코어 프로세서는 스케줄링 문제를 복잡하게 만들 수 있습니다. 프로세서가 메모리에 접근할 때 데이터가 사용 가능해지기를 기다리는 데 상당한 시간을 보냅니다. 이러한 상황을 **메모리 정지(memory stall)**라고 하며, 주로 현대 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 발생합니다. 그러나 캐시 미스(캐시 메모리에 없는 데이터에 접근하는 경우) 때문에도 메모리 정지가 발생할 수 있습니다. 프로세서는 시간의 최대 50%를 메모리에서 데이터를 사용할 수 있게 되기를 기다리는 데 보낼 수 있습니다.
이러한 상황을 해결하기 위해 최근의 많은 하드웨어 설계는 멀티스레드 처리 코어를 구현했습니다. 여기서 두 개(또는 그 이상)의 하드웨어 스레드가 각 코어에 할당됩니다. 따라서 하나의 하드웨어 스레드가 메모리를 기다리는 동안 정지되면, 코어는 다른 스레드로 전환할 수 있습니다. 운영체제 관점에서 각 하드웨어 스레드는 명령어 포인터 및 레지스터 세트와 같은 아키텍처 상태를 유지하므로, 소프트웨어 스레드를 실행할 수 있는 논리적 CPU로 보입니다. 이러한 기술을 **칩 멀티스레딩(chip multithreading, CMT)**이라고 합니다. 인텔 프로세서는 단일 처리 코어에 여러 하드웨어 스레드를 할당하는 것을 설명하기 위해 **하이퍼스레딩(hyper-threading)**이라는 용어를 사용합니다.
일반적으로 처리 코어를 멀티스레드하는 두 가지 방법이 있습니다:
굵은 입도 멀티스레딩(coarse-grained multithreading): 메모리 정지와 같은 긴 지연 시간 이벤트가 발생할 때까지 스레드가 코어에서 실행됩니다. 긴 지연 시간 이벤트로 인한 지연 때문에 코어는 실행을 시작하기 위해 다른 스레드로 전환해야 합니다. 그러나 스레드 간 전환 비용은 명령어 파이프라인이 플러시되어야 하므로 높습니다.
미세 입도 멀티스레딩(fine-grained multithreading): 스레드 간에 훨씬 더 미세한 수준의 전환이 이루어집니다. 일반적으로 명령어 주기 경계에서 전환이 발생합니다. 그러나 미세 입도 시스템의 아키텍처 설계에는 스레드 전환을 위한 로직이 포함되어 있습니다. 결과적으로 스레드 간 전환 비용은 적습니다.
로드 밸런싱
SMP 시스템에서는 둘 이상의 프로세서가 있다는 이점을 완전히 활용하기 위해 모든 프로세서 간에 워크로드를 균형 있게 유지하는 것이 중요합니다. 그렇지 않으면 하나 이상의 프로세서가 유휴 상태인 반면, 다른 프로세서들은 높은 워크로드를 가지며 CPU를 기다리는 스레드 큐를 가질 수 있습니다. **로드 밸런싱(Load Balancing)**은 SMP 시스템의 모든 프로세서에 걸쳐 워크로드를 균등하게 분산시키려고 시도합니다. 이는 일반적으로 각 프로세서가 실행 가능한 스레드의 자체적인 비공개 준비 큐를 가지고 있는 시스템에서만 필요합니다. 공통 실행 큐를 가진 시스템에서는 로드 밸런싱이 불필요합니다.
로드 밸런싱에는 두 가지 일반적인 접근 방식이 있습니다:
푸시 마이그레이션(Push Migration): 특정 태스크가 주기적으로 각 프로세서의 로드를 확인하고, 불균형이 발견되면 과부하된 프로세서에서 유휴 또는 덜 바쁜 프로세서로 스레드를 이동(푸시)하여 로드를 균등하게 분산시킵니다.
풀 마이그레이션(Pull Migration): 유휴 프로세서가 바쁜 프로세서에서 대기 중인 태스크를 가져옵니다.
푸시 마이그레이션과 풀 마이그레이션은 상호 배타적일 필요는 없으며, 실제로 로드 밸런싱 시스템에서 종종 병렬로 구현됩니다.
프로세서 친화도
스레드가 특정 프로세서에서 실행될 때 캐시 메모리에 어떤 일이 발생하는지 고려해 봅시다. 스레드가 가장 최근에 접근한 데이터는 해당 프로세서의 캐시를 채웁니다. 결과적으로 스레드의 연속적인 메모리 접근은 종종 캐시 메모리에서 해결됩니다. 이를 **따뜻한 캐시(warm cache)**라고 합니다. 로드 밸런싱 등으로 인해 스레드가 다른 프로세서로 마이그레이션되면, 첫 번째 프로세서의 캐시 메모리 내용은 무효화되어야 하고, 두 번째 프로세서의 캐시는 다시 채워져야 합니다. 캐시 무효화 및 다시 채우는 데 드는 높은 비용 때문에, 대부분의 운영체제는 스레드를 한 프로세서에서 다른 프로세서로 마이그레이션하는 것을 피하고, 대신 스레드를 동일한 프로세서에서 실행하여 따뜻한 캐시의 이점을 활용하려고 합니다. 이를 **프로세서 친화도(processor affinity)**라고 합니다.
프로세서 친화도는 여러 형태로 나타납니다:
소프트 친화도(soft affinity): 운영체제가 프로세스를 동일한 프로세서에서 실행하려고 시도하지만, 그렇게 할 것을 보장하지는 않습니다. 로드 밸런싱 중에 프로세스가 프로세서 간에 마이그레이션될 수 있습니다.
하드 친화도(hard affinity): 일부 시스템은 프로세스가 실행될 수 있는 프로세서의 하위 집합을 지정할 수 있는 시스템 호출을 제공합니다.
비균일 메모리 접근(NUMA) 시스템에서는 CPU가 자체 로컬 메모리에 더 빠르게 접근할 수 있지만, 다른 CPU의 로컬 메모리에 접근하는 데는 더 오래 걸립니다. 스케줄러와 메모리 배치 알고리즘이 NUMA를 인지하고 함께 작동한다면, 특정 CPU에 스케줄링된 스레드가 해당 CPU와 가장 가까운 메모리를 할당받아 가장 빠른 메모리 접근을 제공할 수 있습니다. 로드 밸런싱은 종종 프로세서 친화도의 이점을 상쇄합니다.
Last updated