스케줄링의 개념과 기준

노트북에서 top을 실행해 보면 프로세스가 수백 개 떠 있는데, CPU 코어는 몇 개뿐입니다. 이 가운데 대부분은 입력이나 타이머를 기다리며 잠들어 있지만, 실행할 준비가 된 작업이 코어 수보다 많은 순간은 언제든 생깁니다. 그때마다 운영체제는 누구에게 CPU를 줄지, 얼마나 오래 줄지를 정해야 합니다. 이 결정을 CPU 스케줄링(CPU scheduling)이라고 합니다.

같은 하드웨어와 같은 프로그램이라도 이 결정을 어떻게 내리느냐에 따라 사용자가 느끼는 속도가 크게 달라집니다. 키보드 입력이 바로 화면에 나타나는지, 큰 일괄 작업이 언제 끝나는지, 어떤 작업이 한없이 밀리지는 않는지가 모두 스케줄링에 달려 있습니다. 이 글에서는 스케줄링이 언제 일어나고 무엇을 기준으로 좋고 나쁨을 따지는지 정리하고, 다음 글부터 구체적인 알고리즘을 비교합니다.

고르는 일과 넘기는 일

CPU를 다음 작업에 넘기는 일은 두 부분으로 나뉩니다. 스케줄러(scheduler)는 준비 큐에 있는 작업 가운데 다음에 실행할 작업을 고릅니다. "누구에게 CPU를 줄 것인가"라는 정책(policy)의 결정입니다. 디스패처(dispatcher)는 스케줄러가 고른 작업에 실제로 CPU를 넘깁니다. 3장에서 본 컨텍스트 스위칭이 여기에 해당하며, 지금 작업의 문맥을 저장하고, 고른 작업의 문맥을 되살리고, 필요하면 사용자 모드로 돌아가 그 작업이 멈추었던 명령어부터 실행을 이어 가게 합니다. 이렇게 고르는 정책과 넘기는 방법(mechanism)을 나누어 두면, 넘기는 방법은 그대로 둔 채 정책만 바꿀 수 있습니다.

디스패처가 한 작업을 멈추고 다음 작업을 실행하기 시작할 때까지 걸리는 시간을 디스패치 지연(dispatch latency)이라고 합니다. 이 시간은 하드웨어, 주소 공간을 바꾸는지, 캐시와 TLB의 상태, 커널 구현에 따라 달라지므로 일정한 값으로 외울 수 없습니다. 다만 작업을 자주 바꿀수록 이 비용이 자주 들고, 그만큼 실제 작업에 쓰이는 CPU 시간이 줄어든다는 점은 기억해 둘 만합니다.

스케줄링이 일어나는 시점

스케줄러가 다음 작업을 고르는 계기는 작업의 상태가 바뀌는 순간입니다. 3장에서 본 상태 전이 가운데 다음 네 가지가 해당합니다.

1. 실행 중인 작업이 입출력을 요청하거나 자식의 종료를 기다리느라 대기 상태가 될 때
2. 실행 중인 작업이 타이머 인터럽트로 선점되거나 스스로 양보해 준비 상태로 돌아갈 때
3. 기다리던 입출력이 끝나 대기 상태의 작업이 준비 상태가 될 때
4. 실행 중인 작업이 끝날 때

1번과 4번은 지금 작업이 더 실행할 수 없는 경우이므로, 스케줄러는 반드시 다른 작업을 골라야 합니다. 준비된 작업이 하나도 없다면 CPU는 유휴(idle) 상태로 들어갑니다. 2번과 3번은 지금 작업이 계속 실행할 수 있는데도 다시 고를 기회가 생기는 경우입니다. 특히 3번에서 주의할 점이 있습니다. 입출력이 끝난 작업은 준비 큐에 들어갈 뿐이고, 지금 실행 중인 작업을 밀어낼지는 정책이 따로 정합니다.

단계 개념도처럼 입출력을 기다리느라 실행을 멈춘 작업은, 입출력이 끝나면 준비 상태로 돌아가 준비 큐에 합류합니다. 이 순간 지금 실행 중인 작업이 바로 밀려난다는 보장은 없습니다. 깨어난 작업이 실제로 CPU를 받아 실행을 이어 가는 것은 스케줄러가 그 작업을 골라 디스패치한 뒤입니다.

선점형과 비선점형

비선점형(non-preemptive) 스케줄링에서는 작업이 스스로 CPU를 내놓을 때까지 실행합니다. 앞의 네 시점 가운데 1번과 4번, 그리고 작업이 명시적으로 양보할 때만 다음 작업을 고르며, 운영체제가 실행 중인 작업을 강제로 멈추지 않습니다. 구현이 단순하지만, 오래 계산하는 작업 하나가 CPU를 독차지하면 뒤의 작업들은 그 작업이 끝날 때까지 기다려야 합니다. 10분짜리 계산이 먼저 시작되면, 키 입력 하나를 처리하는 데 필요한 1ms짜리 작업도 10분을 기다리는 셈입니다.

선점형(preemptive) 스케줄링에서는 작업이 양보하기 전에도 운영체제가 CPU를 빼앗아 다른 작업에 줄 수 있습니다. 주어진 실행 시간이 다 되었다는 타이머 인터럽트나, 더 높은 우선순위의 작업이 준비 상태가 된 것이 계기가 됩니다. 오늘날의 범용 운영체제인 Linux, Windows, macOS는 모두 선점형입니다. 긴 작업이 CPU를 독차지하지 못하게 되지만, 선점할 수 있다는 것만으로 모든 작업의 응답 시간이나 공정성이 보장되지는 않으며, 그것은 어떤 정책으로 고르느냐에 달려 있습니다.

선점에는 대가가 있습니다. 작업이 공유 데이터를 고치는 도중에 멈추고 다른 작업이 같은 데이터를 고칠 수 있으므로, 데이터가 어긋날 수 있습니다. 이것이 6장에서 다룰 동기화 문제입니다. 커널 자신도 이 문제를 피해야 합니다. Linux 커널은 preempt_disable()과 preempt_enable()로 지금 CPU에서 커널 코드가 선점되지 않는 구간을 만들 수 있는데, 이것은 같은 CPU에서의 선점만 막을 뿐 다른 CPU의 접근이나 인터럽트까지 막지는 못하므로 잠금과 함께 씁니다. 반대로 비선점형이라고 동기화가 필요 없어지는 것도 아닙니다. CPU가 여러 개이거나, 작업이 양보하는 지점 사이에 걸쳐 공유 데이터를 고친다면 여전히 보호해야 합니다.

더 깊이: 커널 안에서 실행 중인 작업도 선점될까

작업이 시스템 콜을 처리하느라 커널 안에서 실행되는 동안에도 선점할지는 별개의 문제이며, Linux는 이를 커널을 빌드할 때 고르는 선점 모델로 정합니다. Linux 6.12의 선점 설정 파일에는 네 가지 모델이 있습니다. PREEMPT_NONE은 처리량을 앞세운 전통적인 모델로 서버와 계산용 시스템을 위한 것이고, PREEMPT_VOLUNTARY는 커널 코드에 명시적인 선점 지점을 더해 데스크톱의 반응을 빠르게 합니다. PREEMPT는 임계 영역이 아닌 모든 커널 코드를 선점할 수 있게 해, 밀리초 단위의 지연이 필요한 데스크톱과 임베디드 시스템을 겨냥합니다.

네 번째인 PREEMPT_RT는 실시간 시스템을 위한 모델입니다. 스핀락 같은 잠금을 선점할 수 있고 우선순위 상속을 아는 잠금으로 바꾸고, 인터럽트 처리를 스레드에서 실행하게 하며, 오래 선점되지 않던 구간을 잘게 나눕니다. 그 결과 진입 코드, 스케줄러, 낮은 수준의 인터럽트 처리 같은 일부 코드를 빼면 커널 거의 전체가 선점할 수 있게 되고, 대부분의 실행 문맥이 스케줄러의 통제를 받습니다.

배포판 커널은 하나의 바이너리로 서버와 데스크톱을 함께 지원해야 하므로, PREEMPT_DYNAMIC을 켜고 빌드하면 부팅할 때 preempt=none, preempt=voluntary, preempt=full 같은 커널 매개변수로 모델을 바꿀 수 있습니다. 6.13에서는 스케줄러가 선점 시점을 정하는 PREEMPT_LAZY가 더해졌습니다. 이 모델은 full과 비슷하지만 일반 작업을 즉시 선점하는 대신 한 틱 동안 스스로 양보할 기회를 주는데, 잠금을 쥔 작업이 선점되는 일을 줄여 voluntary 모델의 성능을 일부 되찾으려는 것입니다.

좋은 스케줄링을 재는 기준

좋은 스케줄링이 무엇인지는 무엇을 중요하게 보느냐에 따라 다릅니다. 알고리즘을 비교할 때는 다음 기준들을 씁니다.

CPU 이용률은 top의 %Cpu(s) 줄에서 id(idle) 값이 낮을수록 높은 것입니다. 하지만 이용률이 높다고 사용자가 만족하는 것은 아닙니다. CPU가 늘 바쁜데 짧은 요청이 긴 작업 뒤에서 오래 기다린다면 이용률은 높아도 응답은 나쁩니다. 처리량은 일괄 처리 시스템에서 중요하고, 응답 시간은 사람이 결과를 기다리는 대화형 시스템에서 중요합니다. 이 장의 알고리즘 계산에서는 응답 시간을 작업이 도착한 뒤 처음으로 CPU에서 실행되기까지의 시간으로 정의합니다. 웹에서 말하는 응답 시간은 네트워크와 서버의 처리까지 포함하므로 같은 값이 아닙니다.

세 시간을 직접 계산하기

반환 시간, 대기 시간, 응답 시간은 이름이 비슷해 섞이기 쉬우므로 예를 들어 계산해 보겠습니다. 작업 A가 0ms에 도착해 준비 큐에서 2ms 기다리고, 2ms부터 5ms까지 CPU를 쓴 뒤 입출력을 요청해 9ms까지 기다립니다. 입출력이 끝났지만 다른 작업이 실행 중이어서 준비 큐에서 1ms 더 기다리고, 10ms부터 12ms까지 CPU를 써서 끝납니다. 컨텍스트 스위칭 비용은 무시합니다. 다음 코드는 이렇게 구간별로 적은 기록에서 세 시간을 계산합니다.

def metrics(arrival, segments):
    """segments는 (시작, 끝, 상태)의 목록이며, 상태는 'ready', 'cpu', 'io' 가운데 하나다."""
    finish = segments[-1][1]
    waiting = sum(end - start for start, end, state in segments if state == "ready")
    first_run = min(start for start, _, state in segments if state == "cpu")
    return finish - arrival, waiting, first_run - arrival

a = [(0, 2, "ready"), (2, 5, "cpu"), (5, 9, "io"), (9, 10, "ready"), (10, 12, "cpu")]
turnaround, waiting, response = metrics(0, a)
print(f"A: 반환 {turnaround}ms, 대기 {waiting}ms, 응답 {response}ms")

A: 반환 12ms, 대기 3ms, 응답 2ms

반환 시간은 도착부터 끝날 때까지이므로 12 − 0 = 12ms입니다. 대기 시간은 준비 큐에 있던 구간만 더하므로 2 + 1 = 3ms이고, 입출력을 기다린 4ms는 들어가지 않습니다. 입출력 대기는 CPU를 받아도 실행할 수 없는 대기 상태였고, 스케줄러가 줄일 수 있는 준비 큐의 대기와는 성격이 다르기 때문입니다. 응답 시간은 처음 CPU를 받은 2ms에서 도착 시각을 뺀 2ms입니다. 반환 시간이 CPU 사용 5ms, 입출력 4ms, 준비 큐 대기 3ms의 합과 같다는 것으로 계산을 확인할 수도 있습니다.

기준들은 서로 맞바꾸어진다

이 기준들은 한꺼번에 좋아지지 않는 경우가 많습니다. 라운드 로빈(round robin, RR)을 예로 들어 보겠습니다. 라운드 로빈은 준비된 작업들에 타임 퀀텀(time quantum)이라는 정해진 시간만큼씩 차례로 CPU를 주는 정책으로, 다음 글에서 자세히 다룹니다. 퀀텀을 짧게 하면 준비된 작업들이 더 빨리 첫 차례를 받으므로 응답 시간이 줄어듭니다. 대신 작업을 더 자주 바꾸게 되어 컨텍스트 스위칭 비용이 늘고, 그만큼 실제 작업에 쓰이는 CPU 시간과 처리량이 줄어듭니다. 전환 한 번에 0.1ms가 든다고 가정하면, 퀀텀이 1ms일 때는 CPU 시간의 약 9%를, 10ms일 때는 약 1%를 전환에 씁니다. 퀀텀을 길게 하면 이 비용은 줄지만, 긴 작업 뒤의 작업은 첫 차례를 더 오래 기다립니다.

전환 횟수를 바꾸지 않고 순서만 바꾸어도 응답 시간은 크게 달라집니다. 작업 P1, P2, P3가 모두 0ms에 도착했고 각각 CPU를 24ms, 3ms, 3ms 써야 한다고 합시다. 고른 작업은 끝까지 실행하고, 입출력과 전환 비용은 없다고 가정합니다. 다음 코드는 두 가지 순서로 실행할 때 각 작업이 처음 실행되는 시각과 평균 응답 시간을 계산합니다.

def first_run_times(order, burst):
    t, first = 0, {}
    for name in order:          # 고른 작업은 끝까지 실행한다
        first[name] = t
        t += burst[name]
    return first

burst = {"P1": 24, "P2": 3, "P3": 3}
for order in (["P1", "P2", "P3"], ["P2", "P3", "P1"]):
    first = first_run_times(order, burst)
    average = sum(first.values()) / len(first)
    print(" -> ".join(order), first, f"평균 응답 {average:g}ms")

P1 -> P2 -> P3 {'P1': 0, 'P2': 24, 'P3': 27} 평균 응답 17ms
P2 -> P3 -> P1 {'P2': 0, 'P3': 3, 'P1': 6} 평균 응답 3ms

긴 P1을 먼저 실행하면 짧은 P2와 P3가 24ms를 넘게 기다려 평균 응답 시간이 17ms가 되지만, 짧은 작업부터 실행하면 평균이 3ms로 줄어듭니다. 두 순서 모두 30ms에 모든 작업이 끝나고 전환 횟수도 같으므로, 처리량은 같은데 응답 시간만 달라진 것입니다. 짧은 작업을 먼저 실행하는 이 생각이 다음 글에서 볼 SJF 알고리즘의 바탕이 됩니다. 다만 짧은 작업만 계속 앞세우면 긴 작업이 한없이 밀리는 기아(starvation)가 생길 수 있으므로, 공정성(fairness)이라는 기준도 함께 따져야 합니다.

그래서 어떤 기준을 앞세울지는 시스템의 목적에 따라 정합니다.

CPU 버스트와 I/O 버스트

대부분의 프로그램은 CPU를 쓰는 구간과 입출력을 기다리는 구간을 번갈아 오갑니다. CPU를 쓰는 구간을 CPU 버스트(CPU burst), 입출력을 기다리는 구간을 I/O 버스트(I/O burst)라고 합니다. CPU 버스트가 길고 입출력이 드문 작업을 CPU 바운드(CPU-bound) 작업이라고 하며, 과학 계산이나 영상 인코딩이 그 예입니다. CPU 버스트가 짧고 대부분의 시간을 기다리는 작업은 I/O 바운드(I/O-bound) 작업이라고 하며, 텍스트 편집기나 웹 서버가 그 예입니다. 편집기는 키 입력 하나를 처리하는 데 CPU를 잠깐 쓰고 다음 입력을 기다립니다.

스케줄러는 이 차이를 이용합니다. I/O 바운드 작업은 CPU를 잠깐만 쓰고 다시 입출력을 시작하므로, 이런 작업을 먼저 실행하면 다음 입출력을 일찍 시작시켜 장치와 CPU가 동시에 일하게 할 수 있습니다. 반대로 CPU 바운드 작업이 계속 먼저 실행되면, I/O 바운드 작업은 다음 입출력을 늦게 시작하므로 그동안 장치가 놀고, 사용자는 화면이 늦게 반응한다고 느낍니다. 그래서 오늘날의 범용 스케줄러는 대화형 작업, 곧 I/O 바운드 작업이 CPU를 빨리 받도록 설계됩니다. 그 구체적인 방법은 5장의 뒤쪽 글에서 다룹니다.

정리

• 스케줄러는 준비 큐에서 다음에 실행할 작업을 고르는 정책이고, 디스패처는 고른 작업에 실제로 CPU를 넘기는 방법입니다.
• 스케줄링은 작업이 대기 상태가 되거나, 선점되거나, 입출력이 끝나 준비 상태가 되거나, 끝날 때 일어납니다. 입출력이 끝난 작업은 준비 큐에 들어갈 뿐이고, 언제 실행될지는 정책이 정합니다.
• 비선점형은 작업이 스스로 CPU를 내놓을 때만 바꾸고, 선점형은 운영체제가 실행 중인 작업에서 CPU를 빼앗을 수 있습니다. 선점은 응답성을 높이는 대신 동기화 문제를 낳습니다.
• 반환 시간은 도착부터 완료까지, 대기 시간은 준비 큐에 있던 시간의 합, 응답 시간은 도착부터 처음 실행까지입니다. 입출력 대기는 대기 시간에 넣지 않습니다.
• 응답 시간, 처리량, 공정성은 서로 맞바꾸어지므로, 시스템의 목적에 따라 앞세울 기준을 정합니다.
• I/O 바운드 작업을 먼저 실행하면 CPU와 장치가 함께 일할 수 있어, 범용 스케줄러는 대화형 작업을 우대합니다.

연습 문제

1. 작업 B의 세 시간

작업 B는 1ms에 도착해 4ms부터 6ms까지 처음 실행하고, 6ms부터 8ms까지 입출력을 기다립니다. 8ms부터 9ms까지 준비 큐에서 기다린 뒤 9ms부터 10ms까지 실행하고 끝납니다. 컨텍스트 스위칭 비용은 무시할 때 B의 반환 시간, 대기 시간, 응답 시간을 구하세요.

2. 퀀텀과 전환 비용

컨텍스트 스위칭 한 번에 0.5ms가 드는 시스템에서 라운드 로빈의 퀀텀을 2ms로 할 때와 20ms로 할 때, CPU 시간 가운데 전환에 쓰이는 비율을 각각 구하세요. 준비된 작업이 항상 여럿 있어서 퀀텀이 끝날 때마다 전환한다고 가정합니다. 각 설정의 장단점도 설명하세요.

3. 이용률이 높으면 좋은 서버인가

두 서버의 CPU 이용률이 모두 95%입니다. 서버 X는 짧은 웹 요청만 처리하고 요청의 평균 응답 시간이 50ms입니다. 서버 Y는 웹 요청과 함께 몇 시간짜리 통계 작업을 같은 우선순위로 실행하며, 웹 요청의 평균 응답 시간이 900ms입니다. 이용률만 보고 두 서버가 똑같이 잘 운영되고 있다고 말할 수 있을까요? Y를 개선할 방법도 제안하세요.

다음 글 기본 스케줄링 알고리즘에서는 FCFS, SJF, SRTF, 라운드 로빈을 같은 작업 묶음으로 실행해 보며 각 기준에서 어떻게 다른지 비교합니다.