CPU 스케줄링 3

CPU 스케줄링 2에서 본 알고리즘들을 조합해, 실제 운영체제가 쓰는 스케줄러(scheduler)가 어떻게 동작하는지 이어서 다룬다. 실행 시간을 미리 알 수 없으니 프로세스(process)가 실제로 어떻게 행동하는지 보고 우선순위를 고치거나, CPU를 받은 몫을 기록해 가장 덜 받은 쪽에 먼저 준다. 끝에서 지금까지 본 알고리즘을 한 표로 비교한다.

다단계 큐와 MLFQ

다단계 큐(multilevel queue)는 준비 큐(ready queue)를 여러 개로 나누고, 큐마다 우선순위와 알고리즘을 따로 정한다. 예를 들어 대화형 프로세스 큐는 라운드 로빈(round robin)으로, 사용자와 주고받는 일 없이 몰아서 처리하는 배치 작업 큐는 FCFS(First-Come First-Served, 선입 선처리)로 돌리고, 위쪽 큐가 비었을 때만 아래쪽 큐를 실행한다. 한계는 프로세스가 처음 배정된 큐에 고정된다는 점이다. 그래서 계산만 하던 작업이 대화형으로 바뀌어도 위쪽 큐로 옮겨 갈 수 없고, 위쪽 큐에 작업이 계속 들어오면 아래쪽 큐는 기아(starvation)에 빠진다.

MLFQ(Multilevel Feedback Queue, 다단계 피드백 큐)는 프로세스가 큐 사이를 오가게 해서 이 한계를 푼다. 운영체제 교재 OSTEP(Operating Systems: Three Easy Pieces)이 정리한 핵심 규칙은 다음과 같다.

1. 새 프로세스는 우선순위가 가장 높은 큐에서 시작한다. 같은 큐 안에서는 라운드 로빈으로 돈다.
2. 한 단계에서 받은 타임 슬라이스(time slice)를 다 쓰면 한 단계 아래 큐로 내려간다. 중간에 CPU를 몇 번 내놓았는지와 상관없이 누적으로 센다. 그래야 타임 슬라이스가 끝나기 직전마다 일부러 입출력을 일으켜 CPU를 내놓는 꼼수로 높은 단계에 버틸 수 없다.
3. 일정 주기마다 모든 프로세스를 맨 위 큐로 올린다. 아래로 밀린 작업의 기아를 막는 장치로, 에이징(aging)과 같은 역할이다.

다이어그램 로딩…

금방 입출력을 요청하는 대화형 작업은 높은 단계에 머물고, 오래 계산하는 작업은 점점 아래로 내려간다. 결과적으로 MLFQ는 실행 시간을 몰라도 짧은 작업을 우대해 SJF(Shortest Job First, 최단 작업 우선)에 가까운 효과를 낸다.

리눅스의 스케줄러: CFS와 EEVDF

리눅스는 2.6.23부터 오랫동안 CFS(Completely Fair Scheduler, 완전 공정 스케줄러)를 썼다. CFS는 고정된 타임 슬라이스 대신 프로세스마다 가상 실행 시간(vruntime)을 기록하고, 지금까지 CPU를 가장 적게 쓴 프로세스를 다음에 실행한다. 프로세스들을 가상 실행 시간 순서로 레드-블랙 트리(red-black tree)에 정렬해 두고, 가장 왼쪽 노드(node)를 꺼낸다. 이 트리는 이진 탐색 트리(binary search tree)라 작은 값이 왼쪽에 모이므로, 가장 왼쪽이 가상 실행 시간이 가장 작은 프로세스다. 사용자가 프로세스에 매기는 우선순위 값인 nice(-20~19, 작을수록 우선)가 낮아 우선순위가 높은 프로세스는 가중치가 커서 가상 실행 시간이 천천히 늘어난다. 그래서 같은 시간 동안 CPU를 더 많이 받는다.

커널(kernel) 문서와 Linux 6.6 릴리스 노트에 따르면, 2023년 10월에 나온 6.6부터 CFS를 EEVDF(Earliest Eligible Virtual Deadline First, 자격 있는 것 중 가상 마감이 가장 이른 것 우선) 알고리즘으로 바꾸는 전환이 시작됐다. EEVDF도 CPU를 공정하게 나누는 목표는 같다. 다만 공정한 몫보다 CPU를 덜 받아 자격이 있는 프로세스들 가운데 가상 마감 시각이 가장 이른 것을 고른다. 가상 마감 시각은 차례를 받을 자격을 얻은 시각에, 요청한 시간 조각 길이를 가중치로 나눈 값을 더한 것이다. 그래서 시간 조각을 짧게 요청할수록 마감이 앞당겨져, 반응 중심 작업이 더 빨리 차례를 받는다. 면접에서 "리눅스 스케줄러는 CFS"라고 답해도 원리 설명으로는 통하지만, 최신 커널은 EEVDF라는 점을 덧붙이면 정확하다.

알고리즘 한눈에

표의 두 번째 열은 실행 중인 프로세스에게서 CPU를 도중에 빼앗는 선점(preemption) 방식인지, 스스로 내놓을 때까지 두는 비선점(non-preemptive) 방식인지를 적었다. CPU 버스트(CPU burst)는 프로세스가 입출력 없이 CPU로 계산만 하는 한 구간이다. SRTF(Shortest Remaining Time First, 최소 잔여 시간 우선)는 SJF의 선점 버전이고, 호위 효과(convoy effect)는 긴 작업 하나 뒤에 짧은 작업들이 줄줄이 묶여 기다리는 현상이다.

알고리즘	선점	다음 차례	좋은 점	문제
FCFS	비선점	먼저 온 순서	단순	호위 효과
SJF	비선점	CPU 버스트가 짧은 순서	평균 대기 시간 최소	길이를 미리 모름, 기아
SRTF	선점	남은 시간이 짧은 순서	늦게 온 짧은 작업도 바로 처리	길이를 모름, 기아, 전환 잦음
우선순위	둘 다	우선순위가 높은 순서	중요도 반영	기아(에이징으로 해결)
라운드 로빈	선점	돌아가며 타임 슬라이스만큼	응답 시간이 짧다	슬라이스 크기에 민감
MLFQ	선점	높은 큐부터, 행동 보고 강등	길이를 몰라도 짧은 작업 우대	매개변수 조정이 어렵다

면접 포인트

• "MLFQ는 실행 시간을 모르는데 어떻게 짧은 작업을 우대하나요?" → 타임 슬라이스를 다 쓴 프로세스를 한 단계씩 내리므로, 금방 입출력을 요청하는 작업은 위에 남고 오래 계산하는 작업은 아래로 간다.
• "기아는 어떻게 막나요?" → 에이징, MLFQ의 주기적 우선순위 올리기.
• "리눅스 스케줄러는?" → CFS는 가상 실행 시간(vruntime)이 가장 작은 프로세스를 레드-블랙 트리에서 꺼낸다. 6.6부터 EEVDF로 바꾸는 전환이 시작됐다.