CPU 스케줄링 — 공정함과 응답성 사이의 거래

한 줄 요약

스케줄러는 처리량, 대기 시간, 응답 시간, 공정성이라는 서로 충돌하는 목표 사이에서 무엇을 포기할지 정하는 정책이다.

왜 이게 필요했나

실행 가능한 프로세스가 코어보다 많으면 누군가는 기다려야 한다. 어떤 순서로 태울지에 따라 같은 작업 묶음의 평균 대기 시간이 몇 배씩 달라진다. 유명한 예를 보자.

세 프로세스의 CPU 버스트가 24, 3, 3 이고 모두 동시에 도착했다고 하자.

• P1, P2, P3 순서로 실행하면 대기 시간은 0, 24, 27 이고 평균은 17 이다.
• P2, P3, P1 순서로 실행하면 대기 시간은 6, 0, 3 이고 평균은 3 이다.

같은 일을 같은 시간에 끝내는데 평균 대기 시간이 5배 이상 차이난다. 긴 작업 뒤에 짧은 작업이 줄서는 이 현상을 호위 효과(convoy effect) 라 하며, 먼저 온 순서대로 처리하는 FCFS 의 대표적 약점이다.

어떻게 동작하나

주요 알고리즘의 성격은 이렇게 정리된다.

| 알고리즘 | 선점 | 기아 | 장점 | 약점 |
| --- | --- | --- | --- | --- |
| FCFS | 없음 | 없음 | 단순함 | 호위 효과 |
| SJF | 없음 | 있음 | 평균 대기 시간 최적 | 다음 버스트를 알 수 없음 |
| SRTF | 있음 | 있음 | SJF 보다 나은 응답 | 예측 필요, 스위치 증가 |
| 우선순위 | 둘 다 | 있음 | 정책 반영 가능 | 기아, 에이징 필요 |
| 라운드 로빈 | 있음 | 없음 | 응답 시간 균등 | 할당량 선택이 어려움 |
| 다단계 피드백 큐 | 있음 | 가능 | 가장 유연 | 매개변수가 많음 |

SJF 가 평균 대기 시간에서 최적임은 증명할 수 있지만 치명적인 문제가 있다. 다음 CPU 버스트 길이를 미리 알 수 없다. 그래서 실제 구현은 과거 버스트의 지수 평균으로 예측한다. 다음 예측값 = 알파 곱하기 최근 실측값 더하기 (1 빼기 알파) 곱하기 이전 예측값 형태이고 보통 알파는 0.5 를 쓴다.

라운드 로빈에서는 시간 할당량 선택이 전부다. 할당량이 너무 크면 FCFS 와 같아지고, 너무 작으면 컨텍스트 스위치 비용이 실제 작업 시간을 잡아먹는다. 경험적으로는 CPU 버스트의 80퍼센트가 할당량 안에 끝나도록 잡는다.

리눅스 CFS 는 조금 다른 각도로 접근한다. 각 태스크의 가상 실행 시간(vruntime) 을 추적하고 그 값이 가장 작은 태스크를 다음에 실행한다. vruntime 은 실제 실행 시간을 가중치로 나눈 값이고, 가중치는 nice 값에서 나온다. nice 가 낮으면(우선순위가 높으면) 가중치가 커서 vruntime 이 천천히 증가하므로 더 자주 선택된다. 이 구조를 레드블랙 트리로 관리하니 삽입과 삭제가 로그 시간이고, 다음 실행 대상은 언제나 가장 왼쪽 노드다.

현장에서 만나는 모습

컨테이너 환경에서 CPU 제한을 걸 때 이 개념이 그대로 등장한다. cgroup 의 CPU 몫(shares/weight)은 CFS 의 가중치에 해당해 경합이 있을 때의 비율을 정하고, CPU 쿼터는 주기마다 쓸 수 있는 시간의 상한을 정한다. 둘을 혼동해 "몫을 낮췄는데 왜 여전히 CPU 를 다 쓰지"라고 묻는 경우가 많은데, 몫은 경합할 때만 의미가 있고 놀고 있는 CPU 를 막지는 않는다.

쿼터 쪽에는 다른 함정이 있다. 스레드가 많은 애플리케이션은 주기 초반에 쿼터를 다 써 버리고 남은 기간 동안 통째로 멈추는 스로틀링을 겪는다. 평균 CPU 사용률은 낮은데 응답 지연의 꼬리만 튀는 증상이 나오면 스로틀 카운터를 먼저 봐야 한다.

이어지는 퀴즈에서 확인할 것

같은 작업 집합에서 순서만 바꿔도 평균 대기 시간이 왜 달라지는지 계산할 수 있는지, CFS 의 vruntime 이 우선순위를 어떻게 표현하는지 확인한다.