기본 스케줄링 알고리즘

이 절에서는 스케줄링의 기본적인 세 가지 알고리즘(FCFS, SJF, 라운드 로빈)을 살펴봅니다.

이 알고리즘들은 개념적 기초이면서, 현대 스케줄러의 구성 요소로도 사용됩니다.

단일 CPU, 고정된 CPU 버스트, I/O·문맥 전환 비용 없음이라는 계산 모델로 실행 순서와 대기 시간을 비교합니다. 아래 텍스트 간트 표기의 숫자는 시간 경계이며, 문자의 폭은 시간에 비례하지 않습니다.

FCFS (First-Come, First-Served)

가장 단순한 알고리즘입니다.

먼저 도착한 프로세스를 먼저 실행합니다.

FIFO 큐 하나로 구현할 수 있어서 코드가 극도로 단순합니다.

세 프로세스가 시간 0에 동시에 도착하고, P1 → P2 → P3 순서로 큐에 들어왔다고 합시다.

P1 → P2 → P3 순서로 실행하면:

|--- P1 (24ms) ---|-- P2 (3ms) --|-- P3 (3ms) --|
0                 24             27              30

대기 시간: P1 = 0ms, P2 = 24ms, P3 = 27ms.

만약 P2 → P3 → P1 순서였다면:

|P2 (3)|P3 (3)|--- P1 (24ms) ---|
0      3      6                 30

대기 시간: P2 = 0ms, P3 = 3ms, P1 = 6ms.

모두 시간 0에 도착한 작업의 큐 삽입 순서만 바뀌었는데 평균 대기 시간이 17ms에서 3ms로 급감했습니다.

이것이 FCFS의 근본적 문제인 호위 효과(Convoy Effect)입니다.

실행 시간이 긴 프로세스가 앞에 있으면, 뒤의 짧은 프로세스들이 줄줄이 기다립니다.

마치 고속도로에서 대형 트럭 뒤에 승용차들이 줄지어 따라가는 것과 같습니다.

FCFS는 비선점형이므로, 한 번 CPU를 받으면 I/O 요청이나 종료 전까지 빼앗기지 않습니다.

FCFS의 실무적 의미

FCFS가 단독으로 사용되는 현대 시스템은 거의 없지만, 같은 우선순위 내에서의 스케줄링에 자주 사용됩니다.

멀티레벨 큐의 배치 작업 큐에서 FCFS를 사용하는 것이 대표적입니다.

또한 단순한 요청 큐의 기본 모델로 쓰입니다. Linux의 SCHED_FIFO는 같은 실시간 우선순위 안에서 FIFO를 쓰며, 더 높은 우선순위에 의해 선점될 수 있으므로 이 절의 비선점 FCFS와 구분합니다.

SJF (Shortest Job First)

실행 시간이 가장 짧은 프로세스를 먼저 실행합니다.

모든 작업이 동시에 도착하고 각각의 CPU 버스트를 미리 아는 위 모델에서는 평균 대기 시간을 최소화합니다.

위의 예에서 SJF를 적용하면 P2(3ms) → P3(3ms) → P1(24ms) 순서가 됩니다.

|P2 (3)|P3 (3)|--- P1 (24ms) ---|
0      3      6                 30

평균 대기 시간 = (0 + 3 + 6) / 3 = 3ms — 이 세 작업을 P1부터 실행한 FCFS의 17ms와 비교하면 극적인 차이입니다.

SJF의 근본적 문제: 미래를 알 수 없다

SJF가 최적이라면 왜 모든 OS가 SJF를 안 쓸까요?

프로세스의 다음 CPU 버스트 시간을 미리 알 수 없기 때문입니다.

프로세스가 CPU를 얼마나 사용할지는 실행해 봐야 알 수 있습니다.

실제로는 과거 데이터를 기반으로 예측합니다.

예측 방법의 하나가 지수 이동 평균(Exponential Moving Average)입니다.

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

$t_n$은 n번째 실제 CPU 버스트 시간, $\tau_n$은 n번째 예측값, $\alpha$는 가중치(0~1)입니다.

$\alpha = 0.5$면 최근 값과 과거 예측을 동일하게 반영합니다.

$\alpha$가 클수록 최근 값을 더 중시합니다.

예측값 10ms, 직전 실제 버스트 6ms, α=0.5라면 다음 예측은 0.5×6 + 0.5×10 = 8ms입니다. 이어 실제 버스트가 4ms라면 새 예측 8ms를 사용하여 0.5×4 + 0.5×8 = 6ms로 갱신합니다. 원래 예측 10ms를 매번 다시 넣는 계산과 다릅니다. 예측이 6ms라는 사실은 다음 실제 버스트가 반드시 6ms라는 보장이 아닙니다.

기아(Starvation) 문제

짧은 프로세스가 계속 도착하면, 긴 프로세스는 영원히 실행되지 못할 수 있습니다.

이것이 기아(Starvation)입니다.

5-3절에서 다룰 에이징(Aging)으로 해결합니다.

SRTF (Shortest Remaining Time First)

SJF의 선점형 버전입니다.

새 프로세스가 도착할 때, 그 프로세스의 예상 실행 시간이 현재 실행 중인 프로세스의 남은 시간보다 짧으면 CPU를 빼앗습니다.

예를 들어 보겠습니다.

t=1에 도착한 P2의 4ms가 P1의 남은 7ms보다 짧아 P1을 선점합니다. t=2와 t=3에 도착한 P3·P4는 당시 P2의 남은 시간보다 길므로 P2가 계속 실행됩니다.

I/O가 없는 이 모델에서 대기 시간은 완료 − 도착 − CPU 버스트입니다. P1~P4의 값은 각각 9, 0, 15, 2ms이므로 평균은 6.5ms입니다.

SRTF의 P1은 t=1에 선점된 뒤 t=10까지 준비 큐에서 기다리므로 대기는 9ms입니다. P3는 도착 t=2부터 첫 실행 t=17까지 15ms 기다립니다. P4는 t=3부터 t=5까지 2ms 기다리고, P2는 도착과 동시에 첫 실행하여 대기 0ms입니다. P1의 응답 시간은 첫 실행 t=0 기준으로 0ms이므로, 선점 후 9ms 대기를 응답 시간에 다시 더하지 않습니다.

비선점형 SJF는 P1 → P2 → P4 → P3 순서로 실행하여 평균 대기 시간이 7.75ms입니다. 이는 이 작업 집합의 모델 계산이며 운영체제 실측은 아닙니다.

라운드 로빈 (Round Robin)

라운드 로빈(RR)은 시분할 시스템을 위해 설계된 알고리즘으로, FCFS에 선점을 추가한 것입니다.

각 프로세스에게 동일한 타임 퀀텀(Time Quantum)을 할당하고, 시간이 다 되면 CPU를 빼앗아 Ready Queue의 끝으로 보냅니다.

타임 퀀텀 = 4ms, P1(24ms), P2(3ms), P3(3ms)일 때:

|P1(4)|P2(3)|P3(3)|P1(4)|P1(4)|P1(4)|P1(4)|P1(4)|
0     4     7     10    14    18    22    26    30

• P2: 4ms에 시작, 7ms에 완료 → 대기 4ms
• P3: 7ms에 시작, 10ms에 완료 → 대기 7ms
• P1: 0ms, 10ms, 14ms, 18ms, 22ms, 26ms에 실행 → 총 대기 6ms

이 예에서는 P1의 긴 버스트가 짧은 두 작업의 첫 실행을 끝까지 막지 않습니다.

P2와 P3는 4ms와 7ms만 기다리면 됩니다.

타임 퀀텀의 선택

타임 퀀텀의 크기가 라운드 로빈의 성능을 결정합니다.

퀀텀이 너무 크면: 모든 프로세스가 퀀텀 내에 끝나므로 FCFS와 동일해집니다.

호위 효과가 다시 발생합니다.

퀀텀이 문맥 전환 비용에 비해 너무 작으면: 컨텍스트 스위칭이 너무 잦아져 유효 CPU 시간이 줄어듭니다.

매 퀀텀마다 10μs의 전환이 발생한다고 가정하면, 퀀텀 1ms에서 전환 비용의 비율은 10 / (1000 + 10)으로 약 1%입니다.

퀀텀이 10μs까지 줄면, CPU 시간의 50%가 스위칭에 사용됩니다.

적절한 퀀텀은 전환 비용과 응답 목표에 따라 달라집니다. 실행할 작업이 하나뿐이면 퀀텀이 끝나도 다른 작업으로 전환할 필요가 없습니다.

Linux의 공정 스케줄러는 이 단순 RR 모델과 다릅니다. CFS와 이후 EEVDF는 5-4절에서 구분합니다.

RR의 특성

라운드 로빈은 SJF보다 평균 반환 시간이 길 수 있습니다.

시간 분할은 긴 작업 뒤에 있는 작업의 첫 실행 대기를 줄이는 데 도움이 됩니다.

단일 CPU에서 동일 우선순위의 준비 작업 n개가 고정되어 있고 전환 비용을 무시하면, 큐 끝 작업은 앞의 n−1개가 각 q 이하를 사용한 뒤 CPU를 받습니다. 이때 한 차례 대기의 상한이 $(n-1) \times q$입니다. 높은 우선순위 작업이나 추가 대기까지 포함한 실제 응답 상한은 아닙니다.

또한 공정합니다.

준비된 작업에는 동일한 최대 퀀텀을 줍니다. 먼저 끝나거나 블로킹되는 작업은 퀀텀을 모두 쓰지 않으므로 실제 사용 시간까지 같지는 않습니다.

짧은 작업이든 긴 작업이든 차별 없이 돌아가면서 실행됩니다.

세 알고리즘 비교

세 알고리즘은 어느 기준을 먼저 보는지에 따라 선택이 달라집니다.

같은 P1·P2·P3를 사용한 아래 시간축에서 막대는 실제 모델의 CPU 실행 구간입니다. FCFS는 제출 순서를 유지하고, SJF는 같은 도착 시각의 짧은 버스트부터 고르며, RR은 아직 남은 작업을 큐 뒤로 보냅니다. RR에서 t=10 이후에는 P1만 남으므로 퀀텀 경계마다 다른 작업으로 문맥 전환한다고 세지 않습니다. 원래의 문자 시간축은 그대로 두고 세 정책을 비례 막대로 함께 비교합니다.

독립 확인: 모든 작업이 t=0에 도착하고 제출 순서는 A(5ms), B(2ms), C(1ms)입니다. I/O·문맥 전환 비용을 무시할 때 FCFS와 비선점 SJF의 실행 구간과 평균 대기 시간을 구하세요.

타임 퀀텀 1ms와 작업 전환 비용 10μs를 비교할 때 단위를 먼저 맞춥니다. 매 퀀텀 뒤 실제 다른 작업으로 전환한다고 가정하면 한 주기는 CPU 실행 1000μs + 전환 10μs이고, 전환 비율은 10/1010 ≈ 0.99%입니다. 퀀텀도 10μs로 줄이면 10/(10+10)=50%가 됩니다. 준비 작업이 하나만 남은 구간에는 같은 전환 횟수를 적용하지 않습니다.

Python으로 시뮬레이션

아래 코드는 모든 작업이 시간 0에 도착하는 모델입니다. 비어 있지 않은 목록, 중복 없는 이름, 양수 버스트와 양수 퀀텀을 전제로 하며 실제 스레드나 운영체제 스케줄러를 실행하지 않습니다.

def fcfs(processes):
    """FCFS 스케줄링 시뮬레이션
    processes: [(name, burst_time), ...]
    """
    time = 0
    total_wait = 0
    for name, burst in processes:
        print(f"{name}: 대기 {time}ms, 실행 {time}~{time + burst}ms")
        total_wait += time
        time += burst
    avg = total_wait / len(processes)
    print(f"평균 대기 시간: {avg:.1f}ms\n")
    return avg

def sjf(processes):
    """SJF(비선점) 스케줄링 시뮬레이션"""
    sorted_procs = sorted(processes, key=lambda p: p[1])
    return fcfs(sorted_procs)

def round_robin(processes, quantum):
    """라운드 로빈 시뮬레이션"""
    remaining = {name: burst for name, burst in processes}
    queue = [name for name, _ in processes]
    time = 0
    wait_time = {name: 0 for name, _ in processes}
    last_run = {name: 0 for name, _ in processes}

    while queue:
        name = queue.pop(0)
        wait_time[name] += time - last_run[name]
        run = min(remaining[name], quantum)
        print(f"t={time}: {name} 실행 {run}ms (남은 {remaining[name] - run}ms)")
        time += run
        remaining[name] -= run
        last_run[name] = time
        if remaining[name] > 0:
            queue.append(name)

    total = sum(w - processes[0][1] * 0 for w in wait_time.values())
    avg = sum(wait_time.values()) / len(processes)
    print(f"평균 대기 시간: {avg:.1f}ms\n")

procs = [("P1", 24), ("P2", 3), ("P3", 3)]

print("=== FCFS ===")
fcfs(procs)

print("=== SJF ===")
sjf(procs)

print("=== Round Robin (q=4) ===")
round_robin(procs, 4)

먼저 앞의 시간축에서 FCFS 평균 17ms, SJF 평균 3ms, RR 평균 (6 + 4 + 7) / 3ms를 예상하고 출력과 비교하세요. 이 코드는 평균을 소수점 한 자리로 표시하므로 각각 17.0ms, 3.0ms, 5.7ms가 나옵니다. FCFS·SJF 출력에는 개별 대기가 직접 표시되고, RR 출력에는 실행 시각과 남은 버스트가 표시됩니다. RR의 P1은 4~10ms 동안 6ms, P2는 0~4ms 동안 4ms, P3는 0~7ms 동안 7ms 기다렸다는 것을 실행 시각에서 확인할 수 있습니다.

다음 절에서는 실제 OS에서 사용되는 고급 스케줄링 알고리즘을 살펴보겠습니다.