CS학습2026년 9월 8일

SJF: 최단 작업 우선으로 평균 대기시간을 최소화하는 스케줄링

SJF(Shortest Job First)는 CPU 버스트 시간이 가장 짧은 프로세스를 먼저 실행하는 스케줄링 알고리즘이다. 비선점형과 선점형(SRTF) 두 방식이 있으며, 이론적으로 평균 대기시간을 최소화하는 최적 알고리즘으로 증명되어 있다. 다만 미래의 버스트 시간을 정확히 알아야 한다는 전제가 현실에서는 성립하기 어렵고, 긴 작업이 계속 밀리는 기아(

송민성6분 읽기

1. 개념

SJF(Shortest Job First, 최단 작업 우선 스케줄링)는 준비 큐(ready queue)에 있는 프로세스 중 다음 CPU 버스트 시간(CPU burst time)이 가장 짧은 프로세스를 먼저 실행하는 CPU 스케줄링 알고리즘이다.

두 가지 변형이 있다.

비선점형 SJF(Non-preemptive SJF): 한 프로세스가 CPU를 잡으면 종료(또는 I/O 대기)까지 실행을 마친다. 새 프로세스가 더 짧은 버스트 시간을 가지고 도착해도 끼어들 수 없다.
선점형 SJF(Preemptive SJF): SRTF(Shortest Remaining Time First)라고도 부른다. 새 프로세스가 도착했을 때 남은 실행 시간이 현재 실행 중인 프로세스보다 짧으면 즉시 선점(preemption)한다.

2. 왜 사용하는가

FCFS(First Come First Served)는 도착 순서대로만 처리하기 때문에 긴 작업 뒤에 짧은 작업이 밀리는 호위 효과(convoy effect)가 발생한다. 예를 들어 버스트 시간 100인 프로세스 뒤에 버스트 시간 1인 프로세스 여러 개가 대기하면, 짧은 작업들의 평균 대기시간이 비정상적으로 커진다.

SJF는 짧은 작업을 먼저 배치해서 이 문제를 완화한다. 수학적으로 SJF(비선점형 기준)는 주어진 프로세스 집합에 대해 평균 대기시간을 최소화하는 최적 알고리즘으로 증명되어 있다. 짧은 작업을 앞으로 당기면 뒤따르는 여러 프로세스의 대기시간이 동시에 줄어들기 때문이다.

3. 동작 원리

비선점형 SJF의 동작 순서는 다음과 같다.

준비 큐에 있는 프로세스들의 버스트 시간을 확인한다.
버스트 시간이 가장 짧은 프로세스를 선택해서 CPU에 할당한다.
해당 프로세스가 끝날 때까지 CPU를 점유한다.
종료 후 다시 준비 큐에서 가장 짧은 프로세스를 선택한다.

선점형 SRTF는 3번 단계에서 차이가 있다. 매 시간 단위(또는 새 프로세스 도착 시점)마다 현재 실행 중인 프로세스의 남은 시간과 새로 도착한 프로세스의 버스트 시간을 비교해서, 더 짧은 쪽으로 즉시 전환한다.

핵심 전제는 각 프로세스의 CPU 버스트 시간을 스케줄러가 미리 알고 있어야 한다는 점이다. 실제 운영체제에서는 이를 정확히 알 수 없으므로, 과거 버스트 시간의 지수 평균(exponential average)으로 다음 버스트 시간을 예측하는 방식을 함께 쓴다.

4. 코드 예제

python

from dataclasses import dataclass, field


@dataclass
class Process:
    pid: str
    arrival_time: int
    burst_time: int
    remaining_time: int = field(init=False)

    def __post_init__(self):
        self.remaining_time = self.burst_time


def non_preemptive_sjf(processes: list[Process]) -> list[tuple[str, int, int]]:
    """비선점형 SJF. (pid, start_time, end_time) 리스트를 반환한다."""
    procs = sorted(processes, key=lambda p: p.arrival_time)
    completed = []
    ready_queue = []
    current_time = 0
    remaining = procs.copy()

    while remaining or ready_queue:
        # 현재 시각까지 도착한 프로세스를 준비 큐로 이동
        arrived = [p for p in remaining if p.arrival_time <= current_time]
        for p in arrived:
            ready_queue.append(p)
            remaining.remove(p)

        if not ready_queue:
            # 아직 도착한 프로세스가 없으면 시간을 다음 도착 시점으로 점프
            current_time = remaining[0].arrival_time
            continue

        # 버스트 시간이 가장 짧은 프로세스 선택
        ready_queue.sort(key=lambda p: p.burst_time)
        proc = ready_queue.pop(0)

        start = current_time
        end = start + proc.burst_time
        completed.append((proc.pid, start, end))
        current_time = end

    return completed


def preemptive_srtf(processes: list[Process]) -> list[tuple[str, int, int]]:
    """선점형 SJF(SRTF). 1 타임 유닛 단위로 시뮬레이션한다."""
    procs = [Process(p.pid, p.arrival_time, p.burst_time) for p in processes]
    time_slices: list[tuple[str, int, int]] = []
    total_burst = sum(p.burst_time for p in procs)
    current_time = 0
    finished = 0
    prev_pid = None
    slice_start = 0

    while finished < len(procs):
        available = [p for p in procs if p.arrival_time <= current_time and p.remaining_time > 0]

        if not available:
            current_time += 1
            continue

        proc = min(available, key=lambda p: p.remaining_time)

        if proc.pid != prev_pid:
            if prev_pid is not None:
                time_slices.append((prev_pid, slice_start, current_time))
            slice_start = current_time
            prev_pid = proc.pid

        proc.remaining_time -= 1
        current_time += 1

        if proc.remaining_time == 0:
            finished += 1

    time_slices.append((prev_pid, slice_start, current_time))
    return time_slices


if __name__ == "__main__":
    jobs = [
        Process("P1", arrival_time=0, burst_time=8),
        Process("P2", arrival_time=1, burst_time=4),
        Process("P3", arrival_time=2, burst_time=9),
        Process("P4", arrival_time=3, burst_time=5),
    ]

    print("비선점형 SJF:", non_preemptive_sjf(jobs))
    print("선점형 SRTF :", preemptive_srtf(jobs))

실행 결과 예시:

text

비선점형 SJF: [('P1', 0, 8), ('P2', 8, 12), ('P4', 12, 17), ('P3', 17, 26)]
선점형 SRTF : [('P1', 0, 1), ('P2', 1, 5), ('P1', 5, 12), ('P4', 12, 17), ('P3', 17, 26)]

5. 시간 복잡도 또는 성능 특성

스케줄링 결정 자체: 준비 큐에서 최솟값을 찾는 연산은 최소 힙(min-heap)을 쓰면 O(log n), 선형 탐색이면 O(n)이다 (n은 준비 큐에 있는 프로세스 수).
전체 스케줄 계산: 프로세스가 n개일 때 비선점형 SJF는 정렬 기반 구현 시 O(n log n)이다.
선점형 SRTF 시뮬레이션: 위 예제처럼 시간 단위로 도는 방식은 O(T × n) (T는 전체 실행 시간)이며, 실제 커널 구현에서는 이벤트 기반(프로세스 도착/종료 시점에만 재계산)으로 처리해 훨씬 효율적으로 만든다.
평균 대기시간: 동일한 프로세스 집합에 대해 어떤 비선점형 스케줄링 알고리즘보다도 SJF의 평균 대기시간이 작거나 같다(최적성 증명됨). 단, 이는 버스트 시간을 정확히 안다는 가정 하에서만 성립한다.

6. 실무 사용 사례

배치 처리 시스템: 예상 실행 시간이 사전에 파악된 배치 잡(batch job)을 스케줄링할 때 SJF와 유사한 정책을 적용한다. 예를 들어 짧은 리포트 생성 작업을 긴 데이터 마이그레이션 작업보다 먼저 처리하는 식이다.
CPU 버스트 예측: 리눅스의 CFS(Completely Fair Scheduler)나 다양한 실시간 스케줄러는 SJF 자체를 그대로 쓰지는 않지만, "짧은 작업을 우대한다"는 아이디어를 vruntime 계산이나 우선순위 보정에 참고 개념으로 활용한다.
네트워크 큐잉: 패킷 크기가 작은 것을 먼저 처리하는 SJF 유사 정책이 일부 QoS(Quality of Service) 스케줄러에 응용된다.
작업 예측 모델: 실무에서는 버스트 시간을 모르기 때문에, 과거 실행 이력을 지수 평균으로 추정하는 방식(τ(n+1) = α·t(n) + (1-α)·τ(n))을 함께 구현해서 SJF에 근접한 스케줄링을 시도한다.

7. 주의할 점

기아(starvation) 문제: 짧은 프로세스가 계속 도착하면 긴 프로세스는 무한히 뒤로 밀릴 수 있다. 이를 완화하려면 에이징(aging) 기법으로 대기 시간에 비례해 우선순위를 점진적으로 높여야 한다.
버스트 시간을 미리 알 수 없다: 실제 운영체제는 프로세스가 얼마나 CPU를 쓸지 실행 전에 정확히 알 수 없다. 따라서 순수 SJF는 이론적 모델에 가깝고, 실무에서는 예측값을 사용하는 근사 알고리즘을 쓴다.
컨텍스트 스위칭 비용: 선점형 SRTF는 새 프로세스가 도착할 때마다 선점이 일어날 수 있어 컨텍스트 스위칭(context switching) 오버헤드가 FCFS보다 커질 수 있다.
공정성(fairness) 부재: 평균 대기시간은 최적화되지만 개별 프로세스 입장에서는 불공정할 수 있다. 응답 시간의 예측 가능성이 중요한 대화형 시스템에는 부적합하다.

8. 핵심 정리

SJF는 CPU 버스트 시간이 짧은 프로세스를 우선 실행해서 평균 대기시간을 이론적으로 최소화하는 스케줄링 알고리즘이다. 비선점형과 선점형(SRTF) 두 형태가 있으며, 후자는 더 짧은 작업이 도착하면 즉시 선점한다. 실무에서는 버스트 시간을 정확히 알 수 없다는 근본적 한계와 긴 작업의 기아 문제 때문에 순수한 형태로 쓰이기보다, 예측 기법이나 에이징과 결합된 변형 알고리즘으로 응용된다.