CPU 스케줄링

CPU 가상화의 핵심 질문은 "프로세스를 효율적으로 실행하면서도 OS가 제어권을 어떻게 잃지 않느냐"야. 이걸 이해하면 스케줄링까지 자연스럽게 이어지거든.

가장 단순한 방법은 직접 실행(Direct Execution) — 프로그램을 CPU에서 바로 돌리는 거야. 에뮬레이션 없이 네이티브 속도로 도는데, 문제가 두 개 있어. 프로그램이 나쁜 짓(디스크 직접 접근, 메모리 무단 침입)을 하면 어떡하지? 프로그램이 CPU를 독점하면 다른 프로세스는? 이 두 문제를 해결하기 위해 **제한적 직접 실행(Limited Direct Execution)**이 필요해.

첫 번째 문제의 해결책은 **이중 모드(dual mode)**야. 유저 모드에서는 할 수 있는 일이 제한되고, **특권 명령어(privileged instruction)**를 실행하면 프로세서가 예외를 발생시켜. 커널 모드에서만 모든 명령어를 실행할 수 있지. 프로세스가 특권 작업을 하고 싶으면 시스템 콜을 사용하는데, 내부적으로 trap 명령어를 실행해서 유저 모드에서 커널 모드로 전환해. OS가 요청을 처리한 후 return-from-trap으로 유저 모드로 돌아가지. 핵심은 trap table이야 — 부팅 시에 OS가 각 trap 번호에 대응하는 핸들러 주소를 설정하거든. 프로세스가 아무 커널 코드나 실행하는 게 아니라, OS가 미리 정해둔 진입점으로만 들어갈 수 있어. trap이 발생하면 하드웨어가 호출한 프로세스의 레지스터를 **커널 스택(kernel stack)**에 저장하고, return-from-trap 시 복원하지.

두 번째 문제는 **타이머 인터럽트(timer interrupt)**로 해결해. 프로세스가 CPU에서 돌고 있으면 정의상 OS는 돌고 있지 않거든. 하드웨어 타이머가 일정 간격(보통 수 밀리초)마다 인터럽트를 발생시키면, 실행 중인 프로세스가 중단되고 OS의 인터럽트 핸들러가 실행돼. 이제 OS가 다른 프로세스로 전환할지 결정할 수 있지. 협조적 방식(프로세스가 시스템 콜할 때 OS에게 제어권이 넘어감)도 있지만, 무한 루프에 빠진 프로세스를 생각하면 타이머 인터럽트가 필수야.

OS가 CPU를 되찾으면, 스케줄러가 현재 프로세스를 계속 돌릴지 다른 프로세스로 바꿀지 결정하고, 바꾸기로 했으면 컨텍스트 스위치를 수행해. 현재 프로세스의 레지스터를 커널 스택에 저장하고, 다음 프로세스의 레지스터를 복원하고, 커널 스택 포인터를 교체하고, return-from-trap으로 새 프로세스의 유저 코드로 점프하지. 주의할 점은 실제로 두 번의 레지스터 저장/복원이 일어난다는 거야 — 첫 번째는 하드웨어가 trap 발생 시 유저 레지스터를 커널 스택에 저장하는 것, 두 번째는 OS가 프로세스 간 커널 레지스터를 교체하는 것.

이제 "누구를 먼저 돌릴 것인가"라는 스케줄링 정책을 보자. 스케줄러를 평가하는 기준은 두 가지야. **반환 시간(turnaround time)**은 작업을 얼마나 빨리 끝내느냐, **응답 시간(response time)**은 사용자 입력에 얼마나 빨리 반응하느냐. 이 둘은 서로 상충하거든.

**FIFO(First In, First Out)**는 가장 단순해. 먼저 온 작업을 먼저 실행하는 건데, 실행 시간이 100초인 작업 뒤에 10초짜리가 줄 서면 **호위 효과(convoy effect)**가 생겨. **SJF(Shortest Job First)**는 짧은 작업부터 실행해서 호위 효과를 해결하지만, 비선점적이라 긴 작업이 이미 돌고 있으면 소용없어. **STCF(Shortest Time-to-Completion First)**는 선점형 SJF인데, 반환 시간은 최적이지만 응답 시간은 끔찍할 수 있어. **라운드 로빈(Round Robin)**은 각 작업을 타임 슬라이스(보통 10~100ms) 동안만 실행하고 다음으로 넘겨서 응답 시간을 극적으로 개선하지만, 반환 시간은 최악이야. 모든 작업이 조금씩 진행되니까 어떤 것도 빨리 안 끝나거든.

**MLFQ(Multi-Level Feedback Queue)**는 반환 시간과 응답 시간 둘 다 잡으려는 시도야. 여러 우선순위 큐가 있고, 작업의 관찰된 행동에 따라 우선순위가 바뀌지. 새 작업은 최상위 큐에서 시작하고, 타임 슬라이스를 다 쓰면(CPU-bound) 우선순위가 내려가고, 일찍 양보하면(I/O-bound) 높은 우선순위를 유지해. 작업의 실행 시간을 몰라도 과거 행동으로 미래를 예측하는 거지. 문제점도 있어 — 기아(starvation), 게이밍(타임 슬라이스 끝나기 직전에 I/O로 우선순위 유지), 행동 변화 대응 불가. Priority Boost(주기적으로 모든 작업을 최상위 큐로 리셋)로 기아와 행동 변화를 해결하고, 누적 시간 측정으로 게이밍을 방지해. 실제 OS들(Solaris, FreeBSD)이 이 MLFQ 아이디어를 변형해서 쓰지.

**추첨 스케줄링(lottery scheduling)**은 다른 목표를 가져 — 각 프로세스에게 CPU 시간의 일정 비율을 보장하는 **비례 배분(proportional-share)**이야. 각 프로세스에게 티켓을 나눠주고, 무작위 추첨으로 다음 실행할 프로세스를 고르지. A가 75장, B가 25장이면 A는 75%의 CPU를 받아. 구현이 놀라울 정도로 단순한 게 장점인데(난수 생성기와 프로세스 리스트면 끝), 단기 공정성은 보장 못 하고 장기적으로 대수의 법칙에 의해 수렴해. 스트라이드 스케줄링은 이걸 결정적으로 만든 버전이야 — 티켓이 많을수록 보폭(stride)이 짧아서 더 자주 실행되는데, 새 프로세스 합류 시 초기값 설정이 까다로워. 리눅스의 **CFS(Completely Fair Scheduler)**도 비례 배분 아이디어를 쓰는데, vruntime이 가장 작은 프로세스를 다음에 실행하고, 레드-블랙 트리로 O(log n)에 찾고, nice 값(-20~+19)으로 가중치를 조절하지.

멀티코어 환경에서는 새로운 문제들이 터져. 각 CPU에 자기만의 캐시가 있고 모든 CPU가 메인 메모리를 공유하니까, 캐시 일관성(coherence) 문제가 생기지 — CPU 1이 데이터를 바꿨는데 CPU 2는 옛날 값을 볼 수 있어. 하드웨어가 버스 스누핑 같은 프로토콜로 해결하긴 하지만, 소프트웨어 수준에서도 락 같은 동기화가 필요해. **캐시 친화성(cache affinity)**도 중요한데, 프로세스를 같은 CPU에서 계속 실행하면 캐시 히트율이 높아져서 빠르거든.

멀티프로세서 스케줄링 방식은 크게 두 가지야. **SQMS(Single Queue)**는 하나의 큐에서 모든 CPU가 가져가는 건데, 락 경합이 심하고 캐시 친화성을 지키기 어려워. **MQMS(Multi Queue)**는 CPU마다 자기 큐를 가져서 락 경합도 없고 캐시 친화성도 자연스럽지만, 부하 불균형이 문제야. 이건 work stealing — 한가한 CPU가 바쁜 CPU의 큐에서 작업을 훔쳐오는 것 — 으로 해결하지. 리눅스 CFS도 MQMS 기반이야.

---

정리

3장 읽고 기억할 거 세 가지:

1. 이중 모드 + trap table + 타이머 인터럽트가 CPU 가상화의 뼈대야. 프로세스는 제한된 환경에서 돌고, OS는 하드웨어의 도움으로 주기적으로 제어권을 되찾지
2. 반환 시간과 응답 시간은 상충해. FIFO/SJF는 반환 시간에, RR은 응답 시간에 좋고, MLFQ는 관찰된 행동으로 둘 다 잡으려고 해. 만능은 없어
3. 멀티코어에서는 캐시 친화성과 부하 균형이 핵심이야. MQMS + work stealing이 현대 OS의 주류 접근법이지