멀티 프로세서 스케줄링 (Multiprocessor Scheduling)
멀티코어 CPU 환경에서 운영체제가 작업을 여러 CPU에 어떻게 효율적으로 분배할지를 다룬 내용입니다.
1. 배경
현대 시스템은 멀티코어 CPU를 사용합니다. 그러나 하나의 CPU에서만 동작하도록 작성된 프로그램은 CPU가 여러 개여도 성능 향상을 누리지 못합니다. 이를 해결하려면 프로그램을 멀티스레드로 작성해야 합니다.
운영체제(OS) 입장에서는 단일 CPU 스케줄링과 달리, 여러 CPU가 동시에 동작하므로 새로운 문제가 발생합니다. 대표적으로는 캐시 일관성(Cache Coherence)과 동기화, 캐시 친화도(Cache Affinity) 같은 이슈가 있습니다.
2. 주요 문제
2.1 캐시 일관성 문제
여러 CPU가 각각의 캐시를 가지고 있을 때, 한 CPU가 데이터를 수정하면 다른 CPU 캐시에 있는 동일 데이터가 오래된 값이 될 수 있습니다. 이를 Cache Coherence Problem이라고 합니다.
하드웨어 수준에서 Bus Snooping 같은 기술로 이를 해결하며, 캐시를 무효화하거나 업데이트하여 일관성을 유지합니다.
2.2 동기화 문제
여러 CPU가 동시에 공유 데이터 구조를 수정하면 경쟁 상태(Race Condition)가 발생합니다. 이를 방지하기 위해 락(Lock)을 사용하여 원자적으로 데이터가 변경되도록 보장해야 합니다.
하지만 락은 CPU 수가 늘어날수록 병목(Bottleneck)이 되어 성능이 저하될 수 있습니다.
2.3 캐시 친화도(Cache Affinity)
한 프로세스가 특정 CPU에서 실행되면, 해당 CPU의 캐시에 많은 데이터를 남깁니다. 이후에도 같은 CPU에서 실행되면 캐시를 재활용해 성능이 향상됩니다. 하지만 다른 CPU에서 실행되면 캐시를 새로 채워야 하므로 성능이 떨어집니다.
따라서 스케줄러는 가능하면 같은 CPU에 프로세스를 유지하는 것이 좋습니다.
3. 스케줄링 기법
3.1 단일 큐 스케줄링 (SQMS)
모든 CPU가 하나의 공통 큐에서 작업을 꺼내 실행합니다.
- 장점: 구현이 간단하고, 로드 밸런싱이 자연스럽게 이루어짐
- 단점:
- 큐 접근 시 락이 필요 → CPU가 많아질수록 락 경합 심화
- 캐시 친화도 유지 어려움 (작업이 CPU 간 계속 이동)
해결책: 특정 프로세스를 같은 CPU에 유지하는 Affinity 메커니즘 추가
3.2 다중 큐 스케줄링 (MQMS)
각 CPU가 자신의 독립적인 큐를 가집니다.
- 장점:
- 락 경합 감소 → 확장성(Scalability) 높음
- 캐시 친화도 유지 용이
- 단점:
- CPU 간 작업 수 불균형 발생 가능 → 어떤 CPU는 놀고, 어떤 CPU는 과부하
해결: 작업 이동(Migration)
한 CPU에 작업이 몰리면 일부 작업을 다른 CPU로 옮깁니다. 이를 Work Stealing이라고 하며, 주기적으로 다른 큐를 확인해 작업을 훔쳐와 부하를 균형화합니다.
단, 너무 자주 훔치면 오버헤드가 커지고, 너무 적게 훔치면 불균형이 심해집니다. → 적절한 균형 필요
4. 리눅스 스케줄러 사례
- O(1) 스케줄러: MLFQ 기반, 우선순위를 동적으로 조정
- CFS (Completely Fair Scheduler): 비례적 CPU 할당, 보폭(Stride) 스케줄링과 유사
- BFS (Brain Fuck Scheduler): 단일 큐 기반, EEVDF 알고리즘 사용
최근 리눅스는 CFS를 기본 스케줄러로 사용합니다. MQMS 방식을 기반으로 캐시 친화도와 부하 균형을 모두 고려합니다.
5. 요약
- 멀티코어 환경에서는 락 경합, 캐시 친화도, 부하 불균형 문제가 발생
- SQMS: 간단하지만 확장성, 캐시 친화도 문제
- MQMS: 확장성과 캐시 친화도 우수, 대신 부하 균형 필요
- 리눅스는 MQMS + Work Stealing + Affinity 메커니즘 활용