기본 스케줄링 알고리즘

기본 스케줄링 알고리즘에서는 준비 큐, 선택 기준, 선점/응답 시간 변화를 추적합니다.

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

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

각각의 동작을 간트 차트로 시각화하고, 수치로 비교해 보겠습니다.

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.

도착 순서가 바뀌었을 뿐인데 평균 대기 시간이 17ms에서 3ms로 급감했습니다.

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

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

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

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

FCFS의 실무적 의미

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

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

또한 프린터 큐, 디스크 요청 큐 등 단순한 작업 큐에서 여전히 쓰입니다.

SJF (Shortest Job First)

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

수학적으로 증명할 수 있는 최적 알고리즘입니다 — 모든 프로세스가 동시에 도착한다고 가정할 때, 평균 대기 시간을 최소화합니다.

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

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

평균 대기 시간 = (0 + 3 + 6) / 3 = 3ms — 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$가 클수록 최근 값을 더 중시합니다.

기아(Starvation) 문제

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

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

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

SRTF (Shortest Remaining Time First)

SJF의 선점형 버전입니다.

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

예를 들어 보겠습니다.

SRTF 동작:

• t=0: P1 시작 (남은 8ms)
• t=1: P2 도착 (4ms). P1의 남은 시간 7ms > P2의 4ms → P1 선점, P2 실행
• t=2: P3 도착 (9ms). P2 남은 3ms < P3의 9ms → P2 계속 실행
• t=3: P4 도착 (5ms). P2 남은 2ms < P4의 5ms → P2 계속 실행
• t=5: P2 완료. 남은 중 가장 짧은 P4(5ms) 실행
• t=10: P4 완료. P1(남은 7ms) 실행
• t=17: P1 완료. P3(9ms) 실행
• t=26: P3 완료

평균 대기 시간 = ((10-1) + (1-1) + (17-2) + (5-3)) / 4 = 6.5ms

비선점형 SJF라면 P1이 끝까지 실행되어 평균 대기 시간이 더 길어집니다.

라운드 로빈 (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

FCFS(최악)의 호위 효과가 사라졌습니다.

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

타임 퀀텀의 선택

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

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

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

퀀텀이 너무 작으면 (예: 1ms): 컨텍스트 스위칭이 너무 잦아져 유효 CPU 시간이 줄어듭니다.

컨텍스트 스위칭에 10μs가 걸리고 퀀텀이 1ms라면, CPU 시간의 약 1%가 스위칭에 낭비됩니다.

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

경험적으로 10~100ms가 적합합니다.

컨텍스트 스위칭 시간의 10배 이상이어야 효율적입니다.

Linux의 CFS는 고정 퀀텀 대신 동적 타임 슬라이스를 사용합니다(5-4절 참조).

RR의 특성

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

하지만 응답 시간은 탁월합니다.

n개의 프로세스, 타임 퀀텀 q일 때, 어떤 프로세스든 최대 $(n-1) \times q$ 시간 안에 CPU를 받습니다.

또한 공정합니다.

모든 프로세스가 동일한 크기의 CPU 시간을 받습니다.

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

세 알고리즘 비교

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

아래 표는 상황별로 어떤 알고리즘을 먼저 의심해 볼지 정리한 것입니다.

Python으로 시뮬레이션

스케줄링 알고리즘의 차이를 실감하기 위해 간단한 시뮬레이터를 만들어 보겠습니다.

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)

이 시뮬레이터를 실행하면 각 알고리즘의 프로세스별 대기 시간과 평균 대기 시간을 비교할 수 있습니다.

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

아래 다이어그램은 기본 스케줄링 알고리즘의 선택 기준과 상충 관계를 압축해 비교한 것입니다.

turnaround = completion - arrival
waiting = turnaround - burst
response = first_run - arrival