OSTEP: 10. Multiprocessor Scheduling (Advanced)

이 글은 OSTEP(Operating Systems: Three Easy Pieces)의 ‘Multiprocessor Scheduling (Advanced)’ 문서를 직접 읽고 정리한 내용이다.

---

1) 배경과 핵심 문제

• 문제 정의: “여러 개의 CPU에서 작업을 어떻게 배치·이동·실행할 것인가?”
• 단일 CPU 대비 차이: 코어마다 캐시가 있어 스레드가 코어를 자주 바꾸면 캐시가 비워져 성능 저하.
• 캐시 일관성(Coherence): 하드웨어(예: 버스 스누핑/디렉터리)가 공유 메모리의 일관성을 유지하지만, 스케줄링 자유도를 제약.
• 동기화 필요: 공유 자료구조에 접근할 때 락/원자적 연산이 필수. 코어 수가 늘수록 락 경합·캐시 라인 바운스 비용 증가.
• 캐시 친화성(Cache affinity): 한 번 코어에 올려 캐시에 워킹셋을 만든 태스크는 같은 코어에서 계속 돌릴수록 유리.

---

2) 설계 축: 큐를 하나로? 여러 개로?

A. 단일 큐 멀티프로세서 스케줄링(SQMS)

• 아이디어: 모든 준비 태스크를 전역 단일 큐에 넣고, 가용 코어 수만큼 꺼내 실행.
• 장점
  • 구현이 단순: 기존 단일 CPU 스케줄러 확장으로 시작 가능.
  • 전역 시야로 공정성/정책 적용이 직관적.
• 단점
  • 확장성 한계: 단일 큐 보호 락 경합이 코어 수 증가에 따라 병목.
  • 캐시 친화성 악화: 각 코어가 전역 큐에서 무작위로 태스크를 집어가면 태스크가 코어 사이를 핑퐁.
• 보완
  • Affinity 메커니즘(최근 실행 코어 우선 배정)
  • 부분적 마이그레이션(소수 태스크만 이동)

B. 멀티 큐 멀티프로세서 스케줄링(MQMS)

• 아이디어: 코어(또는 코어 그룹)마다 별도 준비 큐. 태스크는 입장 시 하나의 큐에 바인딩.
• 장점
  • 확장성 우수: 각 큐가 독립이라 락/캐시 경합 감소.
  • 자연스런 캐시 친화성: 태스크가 같은 코어에 머물 가능성 증가.
• 단점
  • 부하 불균형: 어떤 큐는 태스크가 몰리고, 다른 큐는 한가해질 수 있음(유휴 코어 발생).
• 핵심 과제: 마이그레이션(이동) 정책 설계.

---

3) 부하 불균형 해소: 마이그레이션 설계

• 언제 이동할까?
  • 즉시형: 한 큐가 비면 곧바로 다른 큐에서 훔쳐오기.
  • 주기형: 주기적으로 점검해 격차가 크면 이동.
• 무엇을 이동할까?
  • 긴 태스크 위주(캐시 웜업 비용이 덜 아까움).
  • 최근에 덜 실행된 태스크(공정성) 또는 캐시 풋프린트가 작은 태스크(친화성 희생 최소화).
• 얼마나 자주?
  • 너무 자주면 오버헤드/캐시 미스 증가, 너무 드물면 불균형 지속 → 시스템/워크로드에 맞춘 휴리스틱 임계값 필요.

Work Stealing(작업 훔치기)

• 개념: 일이 부족한 “가난한” 큐가 이웃 “부자” 큐를 엿보고 태스크 일부를 훔침.
• 트레이드오프
  • 탐색 빈도 높음: 빠른 균형 회복 vs. 조회 오버헤드/확장성 저하
  • 탐색 빈도 낮음: 오버헤드 감소 vs. 길어진 불균형 기간

---

4) 실전 이슈: NUMA · 상호작용 · 배치 혼재

• NUMA 인식: 소켓(노드)마다 메모리 접근 비용이 다름 → 마이그레이션은 “동일 노드 우선, 교차 노드는 최후”.
• 상호작용(인터랙티브) 태스크: 짧고 빈번한 웨이크업 → 레이턴시 중심 튜닝 필요.
• 배치(긴 CPU-bound) 태스크: 처리량·자원 효율 중심.
• 혼재 워크로드: 큐 분리(클래스 기반) 또는 우선순위/가상 런타임 보정으로 공정성·친화성 균형.

---

5) 리눅스 사례(개요)

• O(1) 스케줄러: 다중 큐 + 우선순위 기반(MLFQ 유사), 상호작용성 강조.
• CFS(Completely Fair Scheduler): 다중 큐 + 비례할당(가상 런타임 기반 공정성 근사), 범용 기본 스케줄러.
• BFS(Brian Fordyce/Brain F… Scheduler): 단일 큐 + 비례할당(EEVDF 계열), 낮은 레이턴시/단순성 지향 대안.

포인트: 같은 커널 생태계 안에서도 단일 큐 vs 멀티 큐 모두 실전 채택 예가 존재. 목표(대화형 지연, 처리량, 확장성)에 따라 선택이 갈린다.

---

6) 정리 포인트

• SQMS: 정책 일관성과 구현 단순함이 장점. 그러나 락 병목과 친화성 악화가 약점.
• MQMS: 확장성과 친화성이 자연스럽게 확보되지만, 부하 불균형을 반드시 다뤄야 함.
• 마이그레이션과 워크 스틸링은 MQMS의 필수 구성요소. 빈도·대상·임계값이 성능을 좌우.
• 범용 스케줄러는 작은 정책 변화가 큰 행동 차이를 만들 수 있으니, 목표 지표를 명확히 하고 측정 기반으로 조정해야 한다.

---

7) 실무 체크리스트

• NUMA 고려: 큐를 소켓(노드) 단위로 두고, 마이그레이션은 먼저 동일 노드 내에서 시도.
• Affinity 윈도우: 최근 코어를 선호하되, 장기 불균형 시엔 과감히 이동.
• 락/자료구조: 전역 구조 최소화, per-CPU 큐, per-CPU counter + 주기적 merge.
• 부하 지표: 단순 큐 길이만 보지 말고 남은 실행시간(또는 가상 런타임), I/O 비율, 우선순위를 함께 보정.
• I/O-bound 처리: 짧고 빈번한 웨이크업 태스크는 레이턴시 최적 경로에, CPU-bound는 처리량 경로에.
• 진단 도구: 스케줄링 트레이스(perf/sched, ftrace), 런큐 길이, 마이그레이션율, 캐시/NUMA miss, p95/p99 지연 함께 관찰.

---

[의견]

• 목표를 먼저 고정: 대화형 워크로드면 레이턴시(특히 p99) 우선, 배치면 처리량/자원효율 우선. 목표 없이 “균형 마이그레이션”만 키우면 캐시 미스/NUMA 페널티로 역효과.
• 하이브리드 전략 권장: “멀티 큐 + 소프트 글로벌 시야”가 실전에 잘 맞는다. per-CPU 큐를 기본으로 두되, 주기적·조건부로 전역 통계를 참고해 선별적 마이그레이션을 수행.
• 휴리스틱은 데이터로 검증: 마이그레이션 임계값/빈도, 스틸 단위(태스크 수 또는 누적 가상 런타임)는 워크로드별 민감도가 높다. A/B나 카나리로 실측 최적화가 필수.
• NUMA 1순위: 소켓 간 이동은 마지막 카드. 동일 노드 내 균형이 안 잡히는 경우에만 cross-node 이동을 허용하고, 이동 후 메모리 바인딩(policy) 재평가를 자동화.
• 락·통계의 로컬화: 전역 락/카운터가 보이기 시작하면 확장성은 끝난다. per-CPU 데이터와 배경 merge로 “전역 보기는 약하게, 로컬 실행은 강하게”.