CPU 스케줄링
스케줄러는 "다음에 어떤 프로세스를 실행할 것인가?"라는 질문에 답한다. 스케줄링 정책을 평가하는 기본 지표로는 **반환 시간(turnaround time, 작업 완료 시점 - 도착 시점) 과 응답 시간(response time, 최초 실행 시점 - 도착 시점)**이 있다.
기본 정책들
FIFO(First In, First Out): 먼저 도착한 작업을 먼저 실행한다.
구현은 단순하지만 **호위 효과(convoy effect)**에 취약하다. 긴 작업이 먼저 도착하면 짧은 작업들이 전부 뒤에서 대기하게 되어 평균 반환 시간이 급격히 악화된다.
SJF(Shortest Job First): 실행 시간이 가장 짧은 작업을 먼저 실행한다. 모든 작업이 동시에 도착한다면 SJF가 최적이다.
하지만 비선점(non-preemptive) 방식이라 긴 작업이 이미 실행 중이면 짧은 작업이 도착해도 기다려야 한다.
STCF(Shortest Time-to-Completion First): SJF의 선점형 버전이다. 새로운 작업이 도착하면 남은 실행 시간이 가장 짧은 작업을 선택한다. 반환 시간에 대해서는 최적이지만, 응답 시간은 나쁠 수 있다.
Round Robin(RR): 각 프로세스에 짧은 **타임 슬라이스(time slice, 또는 스케줄링 퀀텀)**를 부여하고 순환 실행한다.
응답 시간에는 탁월하지만, 잦은 문맥 교환 비용과 반환 시간 악화가 트레이드오프다.
타임 슬라이스의 길이가 핵심 매개변수인데, 너무 짧으면 문맥 교환 오버헤드가 지배적이 되고, 너무 길면 응답성이 떨어진다.
일반적으로 10~100밀리초 수준을 사용한다.
MLFQ (Multi-Level Feedback Queue)
현실의 스케줄러는 작업의 실행 시간을 미리 알 수 없다. MLFQ는 과거의 행동으로부터 미래를 추정하는 접근법을 취한다.
MLFQ의 구조는 우선순위가 다른 여러 개의 큐로 구성된다. 기본 규칙은 다음과 같다.
규칙 1: 우선순위가 높은 큐의 작업이 먼저 실행된다.
규칙 2: 같은 큐 안에서는 Round Robin으로 돌아간다.
규칙 3: 새 작업은 최상위 큐에 진입한다.
규칙 4: 특정 큐에서 할당된 CPU 시간을 모두 소진하면 한 단계 아래 큐로 이동한다. (CPU 집약적 작업은 점점 낮은 우선순위로 내려간다)
규칙 5: 일정 주기(S)마다 모든 작업을 최상위 큐로 재배치한다. (부스트, boost) 이것이 기아(starvation) 문제와 행동 변화(처음엔 CPU 집약적이었다가 나중에 대화형으로 바뀌는 경우)를 해결한다.
다이어그램은 MLFQ의 3단계 큐 구조와 규칙을 보여준다. 대화형 프로세스(vim, ssh)는 짧게 실행되므로 상위 큐에 머무르며 빠른 응답을 받고, 배치 작업(렌더링, 컴파일)은 CPU를 오래 사용하므로 하위 큐로 강등된다. 왼쪽의 Boost 화살표는 주기적으로 모든 작업을 최상위로 끌어올려 기아를 방지하는 메커니즘이다.
이 설계의 우아함은 적응성에 있다. 규칙 4에서 "할당 시간을 모두 소진하면"이라는 조건은 단일 타임 슬라이스가 아니라 **해당 큐에서의 누적 사용 시간(time allotment)**을 기준으로 한다. 이전 판에서는 "타임 슬라이스를 다 쓰기 전에 CPU를 자발적으로 반납하면 같은 큐에 남는다"는 규칙이었는데, 악의적 프로그램이 타임 슬라이스가 끝나기 직전에 무의미한 I/O를 발생시켜 항상 높은 우선순위를 유지하는 게이밍(gaming) 공격이 가능했다. 누적 시간 기반 규칙이 이 허점을 막는다.
비례 배분 (Proportional Share)
- **로터리 스케줄링(Lottery Scheduling)**은 각 프로세스에 "티켓"을 부여하고, 스케줄링 결정 시 난수를 뽑아 당첨된 티켓의 소유 프로세스를 실행한다. 프로세스 A에 75장, B에 25장의 티켓이 있다면, 충분히 긴 시간 동안 A는 CPU의 75%, B는 25%를 점유한다.
티켓 메커니즘은 유연한 확장이 가능하다.
**티켓 양도(ticket transfer)**로 클라이언트가 서버에 자신의 티켓을 임시로 넘기거나, **티켓 인플레이션(ticket inflation)**으로 신뢰 관계의 프로세스끼리 상대적 비율을 조정할 수 있다.
티켓 통화(ticket currency) 개념으로 사용자별 자체 통화를 운용하고 글로벌 통화로 환산하는 것도 가능하다.
- **스트라이드 스케줄링(Stride Scheduling)**은 로터리의 결정론적 버전이다. 각 프로세스에 티켓 수에 반비례하는 스트라이드(stride) 값을 부여하고, 실행할 때마다 스트라이드만큼 패스(pass) 카운터를 증가시킨다. 항상 패스 값이 가장 낮은 프로세스를 선택한다. 로터리보다 정확하지만, 새 프로세스 진입 시 패스 카운터 초기값 설정이 어렵다는 단점이 있다(0으로 시작하면 CPU를 독점하게 됨).
리눅스의 **CFS(Completely Fair Scheduler)**는 비례 배분 사상을 실제 커널에 구현한 대표 사례다.
CFS는 각 프로세스의 **vruntime(virtual runtime)**을 추적하고, 항상 vruntime이 가장 작은 프로세스를 선택한다. nice 값으로 가중치를 조절하면 높은 우선순위 프로세스의 vruntime이 느리게 증가하여 더 많은 CPU 시간을 얻는다. 준비 큐를 레드-블랙 트리로 관리하여 O(log N)에 최솟값 검색이 가능하다.
CPU 가상화의 핵심은 **환상(illusion)**이다. 물리 CPU가 하나뿐이지만, 시분할과 문맥 교환을 통해 각 프로세스에게 자기만의 CPU가 있는 것처럼 보이게 만든다.
이를 가능하게 하는 두 축은 메커니즘과 정책이다. 메커니즘(문맥 교환, 이중 모드, 트랩)은 "어떻게" 프로세스를 전환할 것인가를, 정책(FIFO, SJF, RR, MLFQ, CFS)은 "어떤" 프로세스에게 CPU를 줄 것인가를 결정한다.
이 둘을 분리한 덕분에 정책만 교체하여 다양한 워크로드에 대응할 수 있다.
또 하나 잊지 말아야 할 것은 하드웨어와 OS의 협력이다. 타이머 인터럽트(HW)가 OS에 주기적으로 제어권을 돌려주고, 이중 모드(HW)가 사용자 프로그램의 특권 명령어를 차단한다. 성능에 민감한 공통 경로(프로세스의 일반 명령어 실행)는 하드웨어가 직접 처리하고, OS는 예외 상황(트랩, 인터럽트)에서만 개입한다.