멀티프로세서 스케줄링

멀티프로세서 스케줄링(Multiprocessor Scheduling)은 CPU(코어)가 둘 이상인 시스템에서 실행할 프로세스·스레드를 어느 CPU 에서 언제 실행할지 정하는 운영체제의 프로세스 스케줄링이다.

개요

단일 프로세서 스케줄링은 "다음에 어떤 프로세스를 실행할까"만 정하면 된다. 멀티코어에서는 여기에 "어느 CPU 에서 실행할까"가 더해지고, 다음 문제가 새로 생긴다.

고려 사항	내용
부하 균형(Load Balancing)	어떤 CPU 는 놀고 어떤 CPU 는 밀려 있으면 전체 처리량이 떨어진다 → 부하 분산
캐시 친화성(Cache Affinity)	프로세스는 직전에 실행된 CPU 의 캐시 메모리에 데이터가 남아 있다. 다른 CPU 로 옮기면 캐시를 다시 채워야 해 느려진다
프로세서 친화성(Processor Affinity)	위 이유로 프로세스를 같은 CPU 에 묶어 두는 정책. 가능하면 같은 CPU 를 쓰는 소프트 친화성과 지정한 CPU 에서만 실행하는 하드 친화성이 있다
동기화	여러 CPU 가 같은 스케줄링 자료구조(준비 큐)를 고칠 때 락이 필요하고, 락 경합이 성능을 떨어뜨린다
캐시 일관성	공유 데이터를 여러 CPU 캐시가 가지면 일관성 유지 트래픽이 생긴다
메모리 구조	NUMA 시스템에서는 프로세스를 메모리가 가까운 CPU 에 배치해야 한다

비대칭 다중 처리(AMP): 한 CPU(마스터)가 스케줄링과 커널 작업을 모두 맡고 나머지는 사용자 코드만 실행한다. 단순하지만 마스터가 병목이 된다
대칭 다중 처리(SMP): 모든 CPU 가 스스로 스케줄링한다. 오늘날 범용 운영체제의 방식이며, 준비 큐를 하나로 둘지(SQMS) CPU 마다 둘지(MQMS)로 나뉜다

SQMS(Single Queue Multiprocessor Scheduling)는 모든 CPU 가 하나의 공유 준비 큐에서 다음에 실행할 작업을 꺼내 가는 방식이다. 단일 프로세서용 정책(라운드 로빈, 우선순위 등)을 거의 그대로 쓸 수 있다.

           ┌───────────────────┐
 CPU0 ◀──  │ 공유 준비 큐: A B C D E │  ──▶ CPU1
 CPU2 ◀──  └───────────────────┘  ──▶ CPU3

확장성 부족: 모든 CPU 가 큐 하나에 접근하므로 락 경합이 심해지고, CPU 가 늘수록 스케줄링 오버헤드가 커진다
캐시 친화성 부족: 작업이 매번 다른 CPU 로 옮겨 다니며 캐시를 재사용하지 못한다. 이를 줄이려 일부 작업은 같은 CPU 에 묶고 일부만 이동시키는 친화성 기법을 추가하면 구현이 복잡해진다

MQMS(Multi Queue Multiprocessor Scheduling)는 CPU 마다 별도의 준비 큐를 두는 방식이다. 새 작업은 어떤 규칙(무작위, 작업이 적은 큐 등)으로 하나의 큐에 배정되고, 이후 그 CPU 에서 독립적으로 스케줄링된다.

 CPU0 ◀── 큐0: A C        CPU1 ◀── 큐1: B D
 CPU2 ◀── 큐2: E          CPU3 ◀── 큐3: (비어 있음)

부하 불균형: 한 큐의 작업이 먼저 끝나면 그 CPU 는 놀고 다른 CPU 에는 작업이 밀린다(위 그림의 CPU3)
해결책으로 작업을 다른 큐로 옮기는 이주(Migration)가 필요하다
- 작업 훔치기(Work Stealing): 작업이 적은 큐가 주기적으로 다른 큐를 살펴 많으면 작업을 가져온다. 너무 자주 보면 SQMS 와 같은 오버헤드가 생기고, 너무 드물게 보면 불균형이 오래간다
- 밀어내기(Push Migration): 별도 작업이 주기적으로 부하를 확인해 바쁜 CPU 의 작업을 한가한 CPU 로 보낸다

구분	SQMS	MQMS
준비 큐	전체 공유 큐 1개	CPU 마다 1개
부하 균형	자동으로 유지	불균형 발생, 이주·작업 훔치기 필요
캐시 친화성	나쁨(작업이 CPU 를 옮겨 다님)	좋음(같은 CPU 에 머묾)
동기화 오버헤드	큼(단일 락 경합)	작음(큐별 락)
확장성	CPU 수가 많으면 나쁨	좋음
구현	단순	이주 정책 때문에 복잡
사례	리눅스 BFS(Brain Fuck Scheduler)	리눅스 O(1) 스케줄러, CFS, EEVDF, 윈도우·솔라리스 등 대부분의 범용 OS

갱 스케줄링(Gang Scheduling): 서로 통신하는 스레드 묶음을 여러 CPU 에서 동시에 실행해 서로 기다리는 시간을 줄인다
전용 프로세서 할당: 병렬 응용 프로그램에 실행 기간 동안 CPU 묶음을 전담시킨다
이기종 멀티코어 스케줄링: 고성능 코어와 고효율 코어가 섞인 프로세서(big.LITTLE 등)에서 작업 특성에 따라 코어를 고른다
실시간 멀티프로세서 스케줄링: 작업을 CPU 별로 고정 배치하는 분할(Partitioned) 방식과 전체 CPU 에서 이동을 허용하는 전역(Global) 방식이 있다. CPU 마다 RM 스케줄링·EDF 스케줄링을 적용할 수 있다

이름에 '큐'가 들어가 혼동되는 기법들이다.

기법	큐를 나누는 기준	목적
다단계 큐(MLQ, Multi-Level Queue)	프로세스 유형·우선순위(시스템, 대화형, 일괄 등). 프로세스는 큐 사이를 옮겨 다니지 않으며, 큐마다 다른 알고리즘(예: 대화형은 RR, 일괄은 FCFS)을 쓰고 큐 사이는 고정 우선순위나 시간 할당으로 스케줄링한다	프로세스 성격에 맞는 차등 처리. 하위 큐 기아 가능
다단계 피드백 큐(MLFQ)	MLQ 와 같되 실행 행태에 따라 큐 사이를 이동. CPU 를 오래 쓰면 아래 큐로 내리고, 오래 기다리면 위로 올린다(에이징)	사전 정보 없이 짧은 작업 우대, 기아 방지
SQMS·MQMS	CPU 기준(공유 1개 / CPU 별)	여러 CPU 에 작업 분배

MLQ·MLFQ 는 "어떤 프로세스를 먼저 실행할까"를 정하는 정책이고, SQMS·MQMS 는 "여러 CPU 에 준비 큐를 어떻게 둘까"를 정하는 구조이다. 그래서 MQMS 의 각 CPU 큐 안에서 MLFQ 를 쓰는 식으로 함께 적용된다.