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

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

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

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

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

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

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

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

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