🟣 순서를 정해야 하는 문제
커널이 타이머 인터럽트로 CPU를 되찾았다. 준비 상태의 프로세스가 여럿 줄 서 있다. 이제 누구를 실행할지 골라야 한다. 이 선택을 담당하는 것이 스케줄러이고, 어떤 규칙으로 고르느냐가 스케줄링 정책이다.
정책을 논하려면 먼저 무엇이 좋은 정책인지 잴 자가 있어야 한다. 두 가지 지표를 주로 쓴다. 하나는 반환 시간(turnaround time)으로, 작업이 도착한 뒤 끝날 때까지 걸린 시간이다. 배치 작업이나 계산 작업에서 중요하다. 다른 하나는 응답 시간(response time)으로, 작업이 도착한 뒤 처음 실행되기까지 걸린 시간이다. 키 입력에 화면이 반응해야 하는 대화형 작업에서 중요하다. 이 장의 이야기 대부분은 이 두 지표가 서로 충돌한다는 사실에서 나온다.
가장 단순한 정책부터 출발해서, 한 정책의 약점이 다음 정책을 부르는 사슬을 따라간다.
🟣 FIFO부터 STCF까지: 반환 시간을 줄이는 길
가장 단순한 정책은 도착한 순서대로 실행하고 끝날 때까지 안 바꾸는 FIFO다. 구현이 쉽지만 치명적인 약점이 있다. 오래 걸리는 작업이 맨 앞에 오면 뒤의 짧은 작업들이 전부 그 뒤에서 하염없이 기다린다. 마트에서 카트 가득 채운 사람 뒤에 우유 하나 든 사람이 선 상황이다. 이 현상을 호위 효과(convoy effect)라 부른다.
해법은 직관적이다. 짧은 작업을 먼저 돌리면 된다. 이것이 SJF(Shortest Job First)다. 짧은 것부터 처리하면 평균 반환 시간이 줄어든다. 그런데 SJF는 작업이 다 같은 시점에 도착한다고 가정한다. 긴 작업이 먼저 실행 중인데 짧은 작업이 뒤늦게 도착하면, SJF는 실행 중인 작업을 중간에 못 멈추므로 다시 호위 효과가 생긴다.
그래서 선점(preemption)을 도입한다. 새 작업이 도착했을 때 남은 실행 시간이 더 짧으면 지금 걸 멈추고 새 걸 실행한다. 이것이 STCF(Shortest Time-to-Completion First)다. 앞 장에서 본 타이머 인터럽트가 바로 이 선점을 가능하게 하는 하드웨어 장치다. STCF는 반환 시간 관점에서 최적에 가깝다.
STCF에는 두 가지 현실적 문제가 남는다. 하나는 작업이 얼마나 걸릴지 미리 알아야 한다는 것인데, 실제로는 알 수 없다. 다른 하나는 반환 시간만 최적화했다는 것이다. 대화형 작업에는 반환 시간보다 응답 시간이 중요하다.
🟣 응답 시간을 위한 라운드 로빈, 그리고 충돌
응답 시간을 줄이려면 발상을 바꿔야 한다. 한 작업을 끝까지 돌리지 말고, 아주 짧은 시간(타임 슬라이스)만 돌리고 다음 작업으로 넘긴다. 이렇게 돌아가며 조금씩 실행하는 것이 라운드 로빈(RR)이다. 작업이 열 개면 각자 금방 한 번씩 CPU를 맛보므로 응답 시간이 짧아진다.
여기서 앞서 말한 충돌이 정면으로 드러난다. RR은 응답 시간에는 좋지만 반환 시간에는 나쁘다. 모든 작업을 조금씩 늘려 실행하니 각 작업이 끝나는 시점이 뒤로 밀린다. 타임 슬라이스를 짧게 잡을수록 응답 시간은 좋아지지만, 문맥 교환이 잦아져 그 비용이 커진다. 슬라이스를 길게 잡으면 반대가 된다. 응답 시간과 반환 시간, 그리고 문맥 교환 비용 사이의 균형점을 잡는 것이 슬라이스 길이 결정의 핵심이다.
정리하면 이렇게 갈린다. 반환 시간을 원하면 STCF 계열, 응답 시간을 원하면 RR 계열이다. 하나의 스케줄러가 둘 다 잘하기는 어렵다. 게다가 지금까지의 정책은 전부 작업의 실행 시간을 안다고 가정했다. 이 두 한계를 동시에 풀어야 실전 스케줄러가 된다.
🟣 입출력을 겹쳐야 CPU가 논다
실전으로 가기 전에 짚을 것이 하나 있다. 지금까지는 작업이 CPU만 쓴다고 봤지만, 실제 작업은 중간에 디스크나 네트워크를 기다린다. 이때 CPU를 놀리면 낭비다.
스케줄러는 작업이 입출력을 요청해 대기 상태로 빠지면, 그 틈에 준비 상태의 다른 작업을 실행한다. 앞 장에서 본 상태 전이가 여기서 성능으로 직결된다. 한 작업의 입출력 시간과 다른 작업의 CPU 시간을 겹치는(overlap) 것이다. 그래서 스케줄러는 작업을 CPU를 오래 쓰는 부류와 입출력을 자주 하는 부류로 나눠 다루면 유리하다. 입출력이 잦은 작업에 우선권을 주면, 그 작업이 금방 다시 입출력으로 빠져 CPU를 비워 주므로 전체 활용률이 올라간다. 이 관찰이 다음 정책의 밑그림이 된다.
🟣 MLFQ: 과거를 보고 미래를 짐작한다
작업 길이를 미리 알 수 없다는 문제를, MLFQ(다단계 피드백 큐, Multi-Level Feedback Queue)는 과거 행동으로 짐작하는 방식으로 우회한다. 미래를 예측하지 말고, 지금까지 이 작업이 어떻게 굴었는지를 보고 우선순위를 조정하자는 것이다.
MLFQ는 우선순위가 다른 여러 큐를 둔다. 규칙은 이렇게 굴러간다. 새 작업은 일단 가장 높은 우선순위 큐에 넣는다. 같은 우선순위 큐 안에서는 라운드 로빈으로 돈다. 그리고 핵심 규칙 하나가 있다. 어떤 작업이 타임 슬라이스를 다 쓸 때까지 CPU를 놓지 않으면 우선순위를 한 단 낮추고, 슬라이스를 다 쓰기 전에 스스로 입출력으로 양보하면 우선순위를 유지한다.
이 규칙 하나로 두 부류가 자연스럽게 갈린다. 짧고 대화형인 작업은 금방 입출력으로 양보하니 높은 우선순위에 머물러 응답이 빠르다. CPU를 오래 붙잡는 계산 작업은 점점 아래 큐로 내려가 낮은 우선순위에서 길게 돈다. 작업 길이를 몰라도 행동을 보고 알아서 분류되는 셈이다.
이 단순한 규칙에는 허점이 있다. 계속 아래로 밀린 작업이 영영 CPU를 못 받는 기아(starvation)가 생길 수 있고, 슬라이스가 끝나기 직전에 일부러 입출력을 던져 우선순위를 유지하는 게이밍(gaming)도 가능하다. MLFQ는 두 규칙을 덧대 이를 막는다. 일정 시간마다 모든 작업의 우선순위를 최상위로 되돌리는 우선순위 상승(priority boost)으로 기아를 막고, 우선순위별 총 사용 시간을 누적해 슬라이스를 쪼개 쓴 작업도 강등시켜 게이밍을 막는다. 규칙을 세우고, 그 규칙의 빈틈을 다시 규칙으로 메우는 이 과정 자체가 스케줄러 설계의 실체다.
🟣 지분 스케줄링과 실무의 우선순위
MLFQ가 응답과 반환의 균형을 노렸다면, 다른 갈래는 자원을 정해진 비율로 나누는 데 집중한다. 지분 스케줄링(proportional share)이다. 추첨 스케줄링(lottery)은 각 작업에 복권을 나눠 주고 매번 무작위로 뽑아 그 작업을 실행한다. 복권을 많이 가진 작업이 장기적으로 더 많은 CPU를 가져간다. 확률에 기대는 대신 결정론적으로 같은 비율을 맞추는 것이 스트라이드(stride) 스케줄링이다.
실제 리눅스의 기본 스케줄러 CFS(Completely Fair Scheduler)도 이 지분 개념의 연장선에 있다. 각 작업이 실제로 CPU를 쓴 시간을 추적해서, 가장 적게 쓴 작업을 다음에 실행하는 식으로 공평함을 맞춘다.
이 우선순위 개념은 모바일 개발에서 매일 마주친다. iOS의 QoS(Quality of Service)가 바로 스케줄링 우선순위의 응용이다. 사용자가 지금 보는 화면을 그리는 작업에는 userInteractive처럼 높은 우선순위를 주고, 백그라운드 동기화에는 background처럼 낮은 우선순위를 준다. MLFQ에서 대화형 작업을 높은 큐에 두던 것과 발상이 같다. 반대로 QoS를 잘못 지정해 무거운 계산을 높은 우선순위 큐에 올리면, 메인 스레드가 밀려 화면이 버벅인다. 스케줄러가 왜 작업을 부류별로 나눴는지 이해하면, 어떤 작업에 어떤 QoS를 줘야 하는지도 같은 논리로 판단할 수 있다.
🟣 정리
- 스케줄링은 준비된 여러 프로세스 중 누구를 실행할지 정하는 문제다. 반환 시간과 응답 시간이라는 두 지표가 서로 충돌한다.
- FIFO의 호위 효과가 SJF를, SJF의 뒤늦은 도착 문제가 선점 기반 STCF를 부른다. STCF는 반환 시간에 강하지만 작업 길이를 알아야 하고 응답 시간에 약하다.
- 라운드 로빈은 짧게 돌아가며 응답 시간을 줄이지만 반환 시간을 희생한다. 타임 슬라이스를 얼마로 잡느냐가 응답 시간과 문맥 교환 비용 사이의 균형을 정한다.
- MLFQ는 작업의 과거 행동을 보고 우선순위를 조정해 길이를 몰라도 대화형과 계산 작업을 갈라낸다. 기아와 게이밍은 우선순위 상승과 누적 시간 규칙으로 막는다.
- 지분 스케줄링(lottery·stride·CFS)은 CPU를 정해진 비율로 나눈다. iOS의 QoS가 이 우선순위 개념의 실무 응용이다.
면접에서 "왜 무거운 작업을 백그라운드 큐에서 돌려야 하나"를 물으면, MLFQ가 대화형 작업을 우선하던 원리로 답을 이어 갈 수 있다. 스케줄링까지가 CPU를 나눠 쓰는 이야기였다. 다음은 자원의 다른 축, 메모리다. 물리 메모리는 유한한데 프로그램마다 넓은 주소가 필요한 이 모순을 어떻게 푸는지, 메모리 가상화로 넘어간다.