기본 스케줄링 알고리즘

앞 글에서 작업 셋을 어떤 순서로 실행하느냐에 따라 평균 응답 시간이 17ms에서 3ms까지 달라지는 것을 보았습니다. 이 글에서는 그 순서를 정하는 대표적인 규칙 네 가지를 살펴봅니다. 도착한 순서대로 실행하는 FCFS, 짧은 작업부터 실행하는 SJF와 그 선점형인 SRTF, 그리고 정해진 시간씩 돌아가며 실행하는 라운드 로빈입니다. 이 알고리즘들은 그 자체로 쓰이기보다는 실제 운영체제 스케줄러의 부품으로 쓰이므로, 각각이 무엇을 잘하고 무엇을 못하는지 알아 두면 뒤에서 볼 복잡한 스케줄러를 이해하기 쉬워집니다.

계산을 단순하게 하려고 다음과 같이 가정합니다. CPU는 하나이고, 각 작업이 CPU를 쓰는 시간(CPU 버스트)은 미리 정해져 있으며, 입출력과 컨텍스트 스위칭 비용은 없습니다. 이 가정에서는 작업의 대기 시간이 "끝난 시각 − 도착 시각 − CPU 버스트"로 계산됩니다. 아래에 나오는 글자로 그린 시간 막대에서 숫자는 구간이 시작하고 끝나는 시각이며, 글자의 폭은 시간의 길이에 비례하지 않습니다.

FCFS: 먼저 온 작업부터

FCFS(first-come, first-served)는 가장 단순한 규칙으로, 준비 큐에 먼저 들어온 작업을 먼저 실행하고 그 작업이 끝나거나 스스로 CPU를 내놓을 때까지 계속 실행합니다. 선입선출(FIFO) 큐 하나로 구현할 수 있습니다. 세 작업이 모두 0ms에 P1, P2, P3 순서로 큐에 들어왔다고 합시다.

FCFS로 실행하면 다음과 같습니다.

|------ P1 ------|-- P2 --|-- P3 --|
0                24       27       30

P1은 도착하자마자 실행되어 대기 시간이 0ms이고, P2는 P1이 끝나는 24ms까지, P3는 P2가 끝나는 27ms까지 기다립니다. 평균 대기 시간은 (0 + 24 + 27) ÷ 3 = 17ms입니다. 같은 세 작업이 P2, P3, P1 순서로 들어왔다면 대기 시간은 0, 3, 6ms가 되어 평균이 3ms로 줄어듭니다. 작업도 같고 CPU도 같은데, 들어온 순서 하나로 평균 대기 시간이 다섯 배 넘게 달라진 것입니다.

이처럼 실행 시간이 긴 작업이 앞에 있으면 짧은 작업들이 그 뒤에 줄줄이 묶여 기다리게 되는 현상을 호위 효과(convoy effect)라고 합니다. 한 차선 도로에서 느린 화물차 뒤에 승용차들이 줄지어 따라가는 모습과 비슷합니다. 실제 시스템에서는 CPU를 오래 쓰는 작업 하나 때문에 입출력을 자주 하는 작업들이 CPU를 기다리느라 다음 입출력을 늦게 시작하고, 그동안 장치는 놀게 됩니다.

FCFS를 단독으로 쓰는 범용 운영체제는 없지만, 같은 우선순위의 작업들 사이에서 순서를 정하는 규칙으로는 자주 쓰입니다. Linux의 실시간 정책인 SCHED_FIFO도 같은 우선순위 안에서는 먼저 온 작업을 먼저 실행합니다. 다만 SCHED_FIFO의 작업은 더 높은 우선순위의 작업이 준비되면 선점되므로, 여기서 다룬 비선점형 FCFS와 완전히 같지는 않습니다.

SJF: 짧은 작업부터

SJF(shortest job first)는 준비된 작업 가운데 CPU 버스트가 가장 짧은 작업을 먼저 실행합니다. 앞의 세 작업에 적용하면 P2와 P3를 먼저, P1을 마지막에 실행하게 됩니다.

|- P2 -|- P3 -|------ P1 ------|
0      3      6                30

평균 대기 시간은 (0 + 3 + 6) ÷ 3 = 3ms로, FCFS의 17ms보다 훨씬 짧습니다. 짧은 작업을 앞에 두면 그 작업이 뒤의 모든 작업에 더하는 대기 시간이 작아지기 때문입니다. 실제로 모든 작업이 동시에 도착하고 버스트를 정확히 안다면, SJF는 평균 대기 시간을 가장 작게 만드는 순서임이 알려져 있습니다. 어떤 순서에서든 긴 작업이 짧은 작업 앞에 있다면, 둘의 자리를 바꾸는 것만으로 평균 대기 시간이 줄어들기 때문입니다.

버스트를 미리 알 수 없다는 문제

SJF가 그렇게 좋다면 왜 모든 운영체제가 쓰지 않을까요? 작업이 CPU를 얼마나 쓸지는 실행해 보기 전에는 알 수 없기 때문입니다. 그래서 실제로는 과거의 버스트로 다음 버스트를 예측해 씁니다. 대표적인 방법이 지수 평균(exponential average)입니다.

$\tau_{n+1} = \alpha \cdot t_n + (1 - \alpha) \cdot \tau_n$

여기서 $t_n$은 방금 끝난 $n$번째 버스트의 실제 길이, $\tau_n$은 그 버스트에 대한 예측값, $\alpha$는 0과 1 사이의 가중치입니다. $\alpha$가 크면 최근 버스트를 더 많이 반영하고, 작으면 과거의 예측을 더 오래 유지합니다. 예측값은 매번 새로 계산한 값을 다음 계산에 이어서 쓰므로, 오래된 버스트의 영향은 계산을 거듭할수록 $(1 - \alpha)$배씩 줄어듭니다. 다음 코드는 첫 예측이 10ms이고 $\alpha = 0.5$일 때, 실제 버스트가 차례로 들어오면 예측이 어떻게 바뀌는지 계산합니다.

def predict(first_guess, actual_bursts, alpha=0.5):
    guess = first_guess
    for burst in actual_bursts:
        guess = alpha * burst + (1 - alpha) * guess
        print(f"실제 {burst}ms를 반영한 다음 예측: {guess:g}ms")

predict(10, [6, 4, 4, 13])

실제 6ms를 반영한 다음 예측: 8ms
실제 4ms를 반영한 다음 예측: 6ms
실제 4ms를 반영한 다음 예측: 5ms
실제 13ms를 반영한 다음 예측: 9ms

실제 버스트가 6ms로 나오자 예측이 10ms와 6ms의 가운데인 8ms가 되고, 다음에는 그 8ms와 실제 4ms의 가운데인 6ms가 됩니다. 처음 예측한 10ms를 매번 다시 쓰는 것이 아니라 직전 예측을 이어서 쓴다는 점에 주의해야 합니다. 짧은 버스트가 이어지면 예측이 점점 내려가다가, 갑자기 13ms짜리 버스트가 나오자 예측이 9ms로 올라갑니다. 예측은 어디까지나 추정이므로, 다음 버스트가 정말 그 길이라는 보장은 없습니다.

긴 작업이 밀리는 기아

SJF에는 또 다른 문제가 있습니다. 짧은 작업이 계속 들어오면, 긴 작업은 순서가 계속 밀려 영원히 실행되지 못할 수 있습니다. 이를 기아(starvation)라고 합니다. 오래 기다린 작업의 순위를 점점 올려 주는 에이징(aging)으로 이 문제를 풀 수 있으며, 이는 다음 글의 우선순위 스케줄링에서 다룹니다.

SRTF: 남은 시간이 가장 짧은 작업부터

SJF는 한번 고른 작업을 끝까지 실행하는 비선점형입니다. 그래서 긴 작업이 실행되는 도중에 짧은 작업이 도착해도 긴 작업이 끝날 때까지 기다려야 합니다. SRTF(shortest remaining time first)는 SJF의 선점형으로, 새 작업이 도착할 때마다 그 작업의 버스트와 지금 실행 중인 작업의 남은 시간을 비교해, 새 작업이 더 짧으면 CPU를 넘깁니다. 도착 시각이 서로 다른 네 작업으로 확인해 보겠습니다.

0ms에는 P1만 있으므로 P1이 실행됩니다. 1ms에 P2가 도착하는데, P2의 버스트 4ms가 P1의 남은 시간 7ms보다 짧으므로 P1을 선점하고 P2가 실행됩니다. 2ms에 도착한 P3(9ms)와 3ms에 도착한 P4(5ms)는 그 시각 P2의 남은 시간 3ms와 2ms보다 길므로 P2가 계속 실행되어 5ms에 끝납니다. 이때 남은 후보는 P1 7ms, P3 9ms, P4 5ms이므로 P4가 실행되어 10ms에 끝나고, 이어서 P1이 17ms에, 마지막으로 P3가 26ms에 끝납니다.

대기 시간을 계산하면 P1은 17 − 0 − 8 = 9ms, P2는 5 − 1 − 4 = 0ms, P3는 26 − 2 − 9 = 15ms, P4는 10 − 3 − 5 = 2ms이고, 평균은 6.5ms입니다. P1의 대기 9ms는 1ms에 선점된 뒤 10ms에 다시 실행될 때까지 기다린 시간입니다. 응답 시간으로 보면 P1은 0ms에 처음 실행되었으므로 0ms이며, 선점된 뒤의 대기를 응답 시간에 다시 넣지는 않습니다.

같은 작업 묶음을 비선점형 SJF로 실행하면, 0ms에 P1만 있으므로 P1이 8ms까지 실행되고, 그 뒤 남은 작업 가운데 짧은 순서인 P2, P4, P3가 실행되어 평균 대기 시간은 7.75ms가 됩니다. 선점으로 짧은 작업을 먼저 끝낸 SRTF가 평균 대기 시간을 줄였지만, 그 대가로 P1을 멈추고 다시 실행하는 전환이 생겼습니다. SRTF도 SJF처럼 남은 시간을 미리 알아야 하고, 긴 작업이 기아에 빠질 수 있다는 문제를 그대로 가집니다.

라운드 로빈: 정해진 시간씩 돌아가며

라운드 로빈(round robin, RR)은 시분할 시스템을 위해 만들어진 알고리즘으로, FCFS에 선점을 더한 것입니다. 준비된 작업들에 타임 퀀텀(time quantum)이라는 같은 길이의 시간을 차례로 주고, 퀀텀을 다 쓰고도 끝나지 않은 작업은 CPU를 빼앗아 준비 큐의 맨 뒤로 보냅니다. 퀀텀이 4ms일 때 앞의 P1(24ms), P2(3ms), P3(3ms)를 실행하면 다음과 같습니다.

|-- P1 --|-- P2 --|-- P3 --|---------- P1 ----------|
0        4        7        10                       30

P1이 퀀텀 4ms를 다 쓰고 큐 뒤로 가면, P2가 4ms에 실행을 시작해 퀀텀을 다 쓰기 전인 7ms에 끝납니다. P3도 7ms부터 10ms까지 실행해 끝납니다. 그 뒤에는 P1만 남으므로, P1은 퀀텀이 끝날 때마다 큐 뒤로 갔다가 곧바로 다시 선택되어 30ms까지 실행됩니다. 이 구간에서는 퀀텀이 끝나도 다른 작업으로 바뀌지 않으므로 컨텍스트 스위칭도 일어나지 않습니다. 대기 시간은 P1이 4ms부터 10ms까지 기다린 6ms, P2가 4ms, P3가 7ms이고 평균은 약 5.67ms입니다.

라운드 로빈의 평균 대기 시간 5.67ms는 SJF의 3ms보다 길지만, 실행 시간을 미리 알 필요가 없다는 큰 장점이 있습니다. 그리고 FCFS와 달리 긴 작업이 앞에 있어도 짧은 작업들이 퀀텀 하나만 기다리면 차례를 받습니다. 일반적으로 같은 우선순위의 준비된 작업이 $n$개이고 퀀텀이 $q$라면, 큐의 맨 뒤에 있는 작업은 앞의 $n - 1$개가 각자 최대 $q$씩 쓴 뒤에 차례를 받으므로, 한 번 차례를 기다리는 시간은 $(n - 1) \times q$를 넘지 않습니다. 컨텍스트 스위칭 비용과 더 높은 우선순위의 작업은 무시한 상한입니다. 또 모든 작업이 같은 최대 퀀텀을 받으므로 긴 작업이든 짧은 작업이든 차별받지 않습니다. 다만 일찍 끝나거나 입출력을 기다리는 작업은 퀀텀을 다 쓰지 않으므로, 실제로 쓴 CPU 시간까지 같아지는 것은 아닙니다.

퀀텀은 얼마가 적당할까

라운드 로빈의 성질은 퀀텀의 길이로 정해집니다. 퀀텀이 아주 길면 대부분의 작업이 퀀텀 안에 끝나므로 FCFS와 같아지고, 호위 효과도 다시 나타납니다. 반대로 퀀텀이 너무 짧으면 작업을 너무 자주 바꾸게 되어 컨텍스트 스위칭 비용이 CPU 시간의 큰 몫을 차지합니다. 전환 한 번에 10μs가 든다고 가정하고, 퀀텀이 끝날 때마다 실제로 다른 작업으로 바뀐다고 해 보겠습니다. 퀀텀이 1ms(1,000μs)라면 한 주기 1,010μs 가운데 10μs, 약 0.99%를 전환에 씁니다. 퀀텀을 10μs로 줄이면 한 주기 20μs 가운데 10μs, 곧 절반을 전환에 쓰게 됩니다.

그래서 퀀텀은 전환 비용보다 충분히 길게, 그러면서도 대화형 작업이 느리다고 느끼지 않을 만큼 짧게 정합니다. 흔히 대부분의 CPU 버스트가 퀀텀 안에 끝나도록 정하라는 경험칙이 쓰이는데, 그러면 입출력을 자주 하는 작업은 퀀텀이 끝나기 전에 스스로 CPU를 내놓으므로 선점이 꼭 필요한 긴 작업에만 일어나기 때문입니다. Linux의 일반 프로세스 스케줄러는 고정된 퀀텀의 라운드 로빈이 아니라 작업들이 받은 실행 시간을 비교하는 방식을 쓰며, 이는 5장의 마지막 글에서 다룹니다.

더 깊이: Linux의 라운드 로빈 퀀텀은 얼마일까

Linux에서 정해진 퀀텀으로 돌아가는 정책은 실시간 정책인 SCHED_RR입니다. sched_rr_get_interval(2)에 따르면 이 퀀텀의 기본값은 100ms이고, Linux 3.9부터는 /proc/sys/kernel/sched_rr_timeslice_ms 파일로 밀리초 단위의 값을 읽고 바꿀 수 있습니다. 이 파일에 0을 쓰면 기본값으로 돌아갑니다. 프로그램 안에서 어떤 프로세스의 퀀텀을 알고 싶을 때는 이름 그대로 sched_rr_get_interval()을 부릅니다.

그 전의 커널에서는 nice 값으로 퀀텀을 조절했습니다. nice 값을 음수로 주어 우선순위를 높이면 퀀텀이 길어지고, 양수로 주면 짧아지는 방식이었으며, 기본 퀀텀은 지금과 같은 0.1초였습니다. nice 값이 퀀텀을 얼마나 바꾸는지는 커널 버전마다 조금씩 달랐고, 이 방법은 Linux 2.6.24부터 없어졌습니다.

네 알고리즘 비교

어느 알고리즘이 가장 좋은지는 앞 글에서 본 기준 가운데 무엇을 먼저 보느냐에 달려 있습니다. 평균 대기 시간만 본다면 SJF 계열이 가장 좋지만 실행 시간을 미리 알아야 하고, 대화형 시스템의 고른 응답이 중요하다면 라운드 로빈이 알맞습니다. 실제 운영체제는 이 규칙들을 섞어 씁니다.

시뮬레이터로 계산 확인하기

지금까지 손으로 계산한 결과를 코드로 확인해 보겠습니다. 다음 시뮬레이터는 앞의 가정, 곧 CPU 하나, 정해진 버스트, 입출력과 전환 비용 없음을 그대로 따릅니다. 같은 작업이 이어서 실행되는 구간은 하나로 합쳐 출력합니다.

from collections import deque

def report(title, timeline, arrival, burst):
    finish = {name: end for name, _, end in timeline}
    waits = {n: finish[n] - arrival[n] - burst[n] for n in burst}   # 입출력이 없는 모델
    print(f"{title}: " + " | ".join(f"{n} {s}-{e}" for n, s, e in timeline))
    print(f"  대기 {waits}, 평균 {sum(waits.values()) / len(waits):.2f}ms")

def add(timeline, name, start, end):
    if timeline and timeline[-1][0] == name and timeline[-1][2] == start:
        timeline[-1] = (name, timeline[-1][1], end)   # 같은 작업이 이어지면 한 구간으로
    else:
        timeline.append((name, start, end))

def in_order(order, burst):                 # FCFS와 SJF: 고른 순서대로 끝까지 실행
    t, timeline = 0, []
    for name in order:
        add(timeline, name, t, t + burst[name])
        t += burst[name]
    return timeline

def round_robin(order, burst, quantum):
    queue, left, t, timeline = deque(order), dict(burst), 0, []
    while queue:
        name = queue.popleft()
        run = min(quantum, left[name])
        add(timeline, name, t, t + run)
        t, left[name] = t + run, left[name] - run
        if left[name]:
            queue.append(name)              # 남은 일이 있으면 큐 뒤로
    return timeline

def srtf(arrival, burst):                   # 1ms마다 남은 시간이 가장 짧은 작업을 고른다
    left, t, timeline = dict(burst), 0, []
    while any(left.values()):
        ready = [n for n in left if left[n] and arrival[n] <= t]
        if ready:
            name = min(ready, key=lambda n: (left[n], arrival[n]))
            add(timeline, name, t, t + 1)
            left[name] -= 1
        t += 1
    return timeline

def sjf(arrival, burst):                    # 도착한 작업 가운데 가장 짧은 것을 끝까지
    left, t, timeline = set(burst), 0, []
    while left:
        ready = [n for n in left if arrival[n] <= t]
        if not ready:
            t = min(arrival[n] for n in left)
            continue
        name = min(ready, key=lambda n: (burst[n], arrival[n]))
        add(timeline, name, t, t + burst[name])
        t += burst[name]
        left.remove(name)
    return timeline

burst = {"P1": 24, "P2": 3, "P3": 3}
arrival = dict.fromkeys(burst, 0)
report("FCFS", in_order(["P1", "P2", "P3"], burst), arrival, burst)
report("SJF", in_order(sorted(burst, key=burst.get), burst), arrival, burst)
report("RR(q=4)", round_robin(["P1", "P2", "P3"], burst, 4), arrival, burst)

arrival = {"P1": 0, "P2": 1, "P3": 2, "P4": 3}
burst = {"P1": 8, "P2": 4, "P3": 9, "P4": 5}
report("SJF", sjf(arrival, burst), arrival, burst)
report("SRTF", srtf(arrival, burst), arrival, burst)

FCFS: P1 0-24 | P2 24-27 | P3 27-30
  대기 {'P1': 0, 'P2': 24, 'P3': 27}, 평균 17.00ms
SJF: P2 0-3 | P3 3-6 | P1 6-30
  대기 {'P1': 6, 'P2': 0, 'P3': 3}, 평균 3.00ms
RR(q=4): P1 0-4 | P2 4-7 | P3 7-10 | P1 10-30
  대기 {'P1': 6, 'P2': 4, 'P3': 7}, 평균 5.67ms
SJF: P1 0-8 | P2 8-12 | P4 12-17 | P3 17-26
  대기 {'P1': 0, 'P2': 7, 'P3': 15, 'P4': 9}, 평균 7.75ms
SRTF: P1 0-1 | P2 1-5 | P4 5-10 | P1 10-17 | P3 17-26
  대기 {'P1': 9, 'P2': 0, 'P3': 15, 'P4': 2}, 평균 6.50ms

다섯 줄의 결과가 모두 앞의 손 계산과 같습니다. 라운드 로빈에서 P1의 실행이 10ms부터 30ms까지 한 구간으로 나오는 것은, P1만 남은 뒤로는 퀀텀이 끝나도 같은 작업이 이어서 실행되기 때문입니다. srtf는 1ms마다 남은 시간이 가장 짧은 작업을 다시 고르는 방식이라 단순하지만 느리며, 실제 스케줄러는 작업이 도착하거나 끝날 때만 다시 고릅니다. 남은 시간이 같은 작업이 여럿이면 먼저 도착한 작업을 고르도록 했는데, 이런 동점 처리 규칙에 따라 결과가 달라질 수 있다는 점도 알아 둘 만합니다.

정리

• FCFS는 도착 순서대로 끝까지 실행합니다. 단순하지만 긴 작업이 앞에 있으면 짧은 작업들이 줄줄이 기다리는 호위 효과가 생깁니다.
• SJF는 버스트가 가장 짧은 작업부터 실행해, 모든 작업이 함께 도착할 때 평균 대기 시간을 가장 짧게 합니다. 버스트를 미리 알 수 없으므로 지수 평균으로 예측하며, 긴 작업이 기아에 빠질 수 있습니다.
• SRTF는 SJF의 선점형으로, 새 작업의 버스트가 지금 작업의 남은 시간보다 짧으면 CPU를 넘깁니다.
• 라운드 로빈은 퀀텀씩 돌아가며 실행해 실행 시간을 몰라도 고른 응답을 줍니다. 퀀텀이 너무 길면 FCFS와 같아지고, 너무 짧으면 전환 비용이 커집니다.

연습 문제

1. 작업 셋의 FCFS와 SJF

작업 A(5ms), B(2ms), C(1ms)가 모두 0ms에 이 순서로 도착했습니다. 입출력과 전환 비용을 무시할 때 FCFS와 비선점형 SJF의 실행 구간과 평균 대기 시간을 구하세요.

2. 퀀텀을 바꾼 라운드 로빈

앞의 P1(24ms), P2(3ms), P3(3ms)를 퀀텀 2ms의 라운드 로빈으로 실행합니다. 실행 구간과 각 작업의 대기 시간, 평균 대기 시간을 구하고, 퀀텀 4ms일 때의 결과와 비교하세요. 컨텍스트 스위칭 비용은 무시합니다.

3. 계속 들어오는 짧은 작업

SRTF로 운영하는 시스템에 20ms짜리 작업 L이 0ms에 도착했고, 그 뒤 1ms부터 2ms마다 3ms짜리 짧은 작업이 끊임없이 도착합니다. L은 언제 끝날까요? 이 문제를 줄이는 방법도 제안하세요.

다음 글 고급 스케줄링 알고리즘에서는 우선순위 스케줄링과 에이징, 여러 큐를 쓰는 멀티레벨 큐와 멀티레벨 피드백 큐, 마감 시각을 지켜야 하는 실시간 스케줄링을 살펴봅니다.