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

한 줄 요약

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

왜 이게 필요했나

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

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

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

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

흐름 강조 재생 · 다시 보려면 해제 후 선택

1. 1긴 것부터 태우면대기 시간이 0, 24, 27 이고 평균은 17 이다.
2. 2짧은 것부터 태우면대기 시간이 6, 0, 3 이고 평균은 3 이다.
3. 3무엇이 달라졌나끝나는 총 시간은 같다. 달라진 것은 짧은 일이 긴 일 뒤에 줄을 섰는가뿐이다.

여기서 구분할 것 긴 작업 뒤에 짧은 작업이 줄서는 이것을 호위 효과라 한다. 먼저 온 순서대로 처리하는 방식의 대표적 약점이다.

잠깐, 예측해 보세요 짧은 것부터 태우는 것이 평균에 최적이라면 왜 그대로 쓰지 않는가?

설명 확인 · 채점 없는 자가 점검

다음 버스트 길이를 미리 알 수 없기 때문이다. 실제 구현은 과거 버스트의 지수 평균으로 예측한다.

근거 문서

어떻게 동작하나

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

알고리즘	선점	기아	장점	약점
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 사용률은 낮은데 응답 지연의 꼬리만 튀는 증상이 나오면 스로틀 카운터를 먼저 봐야 한다.

CPU 를 안 쓰는 대기가 훨씬 흔하다

여기까지는 실행할 준비가 된 프로세스들이 CPU 를 두고 다투는 이야기였다. 그런데 실제 서버에서 프로세스가 기다리는 시간의 대부분은 CPU 차례가 아니라 입출력이 끝나기를 기다리는 시간이다. 이 구분을 못 하면 성능 문제를 통째로 잘못 진단하게 된다.

부하 평균(load average)이 대표적인 오해의 자리다. 리눅스의 부하 평균은 실행 가능한 프로세스뿐 아니라 디스크 입출력을 기다리는 프로세스까지 함께 센다. 그래서 CPU 사용률이 20% 인데 부하 평균이 30 인 상황이 정상적으로 나온다. 이때 CPU 를 늘려도 아무 효과가 없고, 봐야 할 것은 디스크나 네트워크 쪽이다.

프로세스의 상태를 보면 이 구분이 그대로 드러난다. R 은 실행 중이거나 차례를 기다리는 것이고, D 는 되돌릴 수 없는 대기다. D 상태가 오래 지속되면 그 프로세스는 신호로도 죽지 않으므로, 스토리지가 멎었을 때 종료조차 되지 않는 프로세스가 쌓이는 상황이 여기서 나온다.

그리고 대기 자체가 스케줄링에 영향을 준다. 오래 기다렸다가 깨어난 프로세스는 그동안 CPU 를 쓰지 않았으므로 앞에서 본 vruntime 이 작고, 그래서 깨어나자마자 우선적으로 실행된다. 대화형 프로그램이 반응이 빠른 것이 이 성질 덕분이다. 키 입력을 기다리는 동안 vruntime 이 늘지 않아, 입력이 들어오면 계산만 하고 있던 프로세스들을 제치고 먼저 돈다.

진단의 순서로 옮기면 이렇게 된다. 응답이 느릴 때 CPU 사용률만 보고 넘어가지 않는다. 실행 대기 줄이 긴지, 입출력 대기가 긴지, 아니면 앞에서 본 스로틀링에 걸려 있는지를 먼저 가른다. 셋은 원인도 대응도 완전히 다르고, 대시보드의 CPU 그래프 하나로는 셋을 구별할 수 없다.

• 몫(shares·weight)경합이 있을 때의 비율을 정한다. 놀고 있는 CPU 를 막지는 않는다 — 몫을 낮춰도 혼자 돌면 다 쓴다.
• 쿼터(quota)주기마다 쓸 수 있는 시간의 상한이다. 경합이 없어도 그 이상은 못 쓴다.

여기서 구분할 것 몫을 낮췄는데 왜 여전히 CPU 를 다 쓰냐는 물음이 여기서 나온다. 몫은 경합할 때만 의미가 있다.

잠깐, 예측해 보세요 지연 시간이 주기마다 톱니 모양으로 튄다. 무엇을 의심하겠는가?

설명 확인 · 채점 없는 자가 점검

쿼터를 본다. 스레드가 많은 애플리케이션은 주기 초반에 쿼터를 몰아 쓰고 남은 구간을 통째로 기다리게 된다.

근거 문서

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

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