175. SJF (Shortest Job First) 스케줄링 - 최적의 평균 대기 시간

핵심 인사이트 (3줄 요약)

본질: SJF (Shortest Job First) 스케줄링은 Ready Queue에 있는 프로세스들 중 다음 CPU (Central Processing Unit) burst가 가장 짧은 작업을 먼저 실행하는 정책이다.

가치: burst 길이를 정확히 안다는 가정 아래 평균 대기 시간 (Average Waiting Time)을 최소화하므로, 스케줄링 이론에서 가장 중요한 기준선 역할을 한다.

판단 포인트: 실제 운영체제는 미래 burst를 완벽히 알 수 없고 긴 작업의 starvation 위험도 있으므로, SJF 자체보다 "짧은 작업을 우대한다"는 원리가 예측 기반 스케줄러와 Multilevel Feedback Queue에 흡수되어 쓰인다.

Ⅰ. 개요 및 필요성

SJF 스케줄링은 이름 그대로 가장 빨리 끝날 작업을 먼저 보내는 정책이다. 여기서 기준은 프로세스의 전체 수명보다 "다음 CPU burst 길이"다. 즉 지금 Ready Queue에 서 있는 작업들 중 CPU를 가장 짧게 점유할 것으로 보이는 작업을 먼저 실행해, 짧은 일들이 긴 일 뒤에서 불필요하게 묶이지 않도록 만든다.

이 정책이 등장한 이유는 First-Come, First-Served (FCFS) 스케줄링의 convoy effect 때문이다. 도착 순서만 지키면 긴 CPU-bound 작업 하나가 맨 앞을 막고, 뒤의 짧은 interactive 작업 여러 개가 모두 늦어진다. SJF는 긴 작업 하나의 대기 증가보다 짧은 작업 다수의 대기 감소가 더 크다는 점에 착안해, 시스템 전체의 평균 불만도를 낮추는 방향으로 줄을 다시 세운다.

아래 그림은 같은 작업 집합이라도 정렬 기준이 바뀌면 대기 비용이 어떻게 달라지는지 보여 준다.

┌────────────────────────────────────────────────────────────────────┐
│ Same jobs, different ordering cost                                │
├────────────────────────────────────────────────────────────────────┤
│ jobs : P1(12)  P2(2)  P3(1)  P4(3)                                │
│ FCFS : [P1............][P2][P3][P4]                               │
│ SJF  : [P3][P2][P4][P1............]                               │
│ idea : many short waits shrink more than one long wait grows      │
└────────────────────────────────────────────────────────────────────┘

즉 SJF의 핵심은 "공정한 도착 순서"보다 "총 대기 시간의 합"을 더 중요하게 본다는 점이다. 배치 처리처럼 처리량과 평균 대기 시간이 중요한 환경에서는 이 기준이 강력한 설계 논리가 된다.

📢 섹션 요약 비유: SJF는 카트 가득 담은 손님 한 명보다 물건 한두 개만 든 손님 여러 명을 먼저 계산해 전체 줄을 빨리 줄이는 계산대 전략과 같다.

Ⅱ. 아키텍처 및 핵심 원리

SJF가 평균 대기 시간을 줄이는 이유는 교환 논리로 설명할 수 있다. 현재 줄에서 긴 작업 A와 짧은 작업 B가 인접해 있고 A > B라면, A를 먼저 두는 것보다 B를 먼저 두는 편이 뒤에 누적되는 대기 시간이 더 작다. 이 교환을 가능한 곳마다 반복하면 결국 burst 길이 오름차순 배열이 되고, 그것이 SJF 순서다.

┌────────────────────────────────────────────────────────────────────┐
│ Why shorter-first lowers average waiting                          │
├────────────────────────────────────────────────────────────────────┤
│ current order : A(long) -> B(short)                               │
│ total wait    : W + (W + A)                                       │
│ swapped order : B(short) -> A(long)                               │
│ total wait    : W + (W + B)                                       │
│ since A > B, swapped total wait is smaller                        │
└────────────────────────────────────────────────────────────────────┘

예를 들어 동시에 도착한 네 프로세스 P1=6ms, P2=8ms, P3=7ms, P4=3ms를 생각해 보자.

정책	실행 순서	대기 시간 합	평균 대기 시간
FCFS	`P1 -> P2 -> P3 -> P4`	`0 + 6 + 14 + 21 = 41`	`10.25ms`
SJF	`P4 -> P1 -> P3 -> P2`	`0 + 3 + 9 + 16 = 28`	`7.00ms`

같은 작업 집합인데도 긴 작업을 뒤로 보내자 평균 대기 시간이 크게 줄어든다. 이 때문에 SJF는 "알고리즘이 좋다"는 수준을 넘어, 스케줄링 최적화의 수학적 기준점으로 취급된다.

한편 SJF의 기본형은 비선점형 (Non-preemptive)이다. 이미 CPU를 잡은 작업은 끝날 때까지 수행한다. 여기에 선점 기능을 추가한 것이 SRTF (Shortest Remaining Time First)이며, 실행 중에도 더 짧은 남은 시간을 가진 작업이 도착하면 CPU를 빼앗긴다. 즉 SJF는 "시작 전 정렬", SRTF는 "실행 중에도 계속 재정렬"이라고 이해하면 된다.

📢 섹션 요약 비유: SJF는 빨리 끝나는 진료를 먼저 처리해 대기실 전체를 비우는 방식이고, SRTF는 더 짧은 응급 처치가 들어오면 현재 진료를 잠깐 멈추고 순서를 다시 조정하는 방식과 같다.

Ⅲ. 비교 및 연결

SJF를 제대로 이해하려면 FCFS, Round Robin (RR), 우선순위 스케줄링과 함께 봐야 한다. SJF는 사실상 "우선순위 = 예상 burst 길이의 역수"인 특수한 priority scheduling이다. 즉 burst가 짧을수록 더 높은 우선순위를 주는 셈이다.

정책	기준	평균 대기 시간	응답성	한계
FCFS	도착 순서	불리함	낮음	convoy effect
SJF	가장 짧은 다음 burst	매우 유리	중간	burst 예측 필요, starvation
SRTF	가장 짧은 남은 시간	더 유리	높음	선점 오버헤드, starvation
RR	time quantum 순환	보통	높음	문맥 교환 비용
MLFQ (Multilevel Feedback Queue)	과거 행동에 따라 큐 이동	현실적 타협	높음	정책 튜닝 복잡

이 비교에서 드러나는 핵심은 SJF가 평균 대기 시간 최적화에는 강하지만 공정성과 예측 가능성에서는 약하다는 점이다. 긴 CPU-bound 작업은 짧은 작업이 계속 들어오면 끝없이 밀릴 수 있고, 사용자는 "언제쯤 내 차례가 오는지"를 알기 어렵다. 반대로 RR은 평균 대기 시간은 다소 손해 보더라도 모든 작업에 기회를 빠르게 나눠 준다.

현대 범용 운영체제가 SJF를 그대로 쓰지 않는 이유도 여기에 있다. 대신 MLFQ나 fair scheduler는 최근 CPU 사용 패턴을 보고 "짧게 쓰고 자주 I/O로 빠지는 작업"을 자연스럽게 우대한다. 즉 SJF는 구현 자체보다 철학이 살아남아 현대 정책에 스며들었다고 보는 편이 맞다.

📢 섹션 요약 비유: SJF는 가장 효율적인 특급 차선이고, RR은 모두가 조금씩이라도 빨리 움직이게 하는 회전문이라서, 무엇을 최우선으로 보느냐에 따라 선택이 달라진다.

Ⅳ. 실무 적용 및 기술사 판단

실무에서 SJF를 직접 채택할 수 있는지는 "작업 길이를 미리 어느 정도나 아는가"에 달려 있다. 일괄 배치 작업, 인쇄 큐, 일부 데이터 처리 파이프라인처럼 job size가 사전에 주어지거나 꽤 잘 예측되는 환경에서는 SJF 계열이 유효하다. 반대로 사용자 프로그램의 다음 CPU burst처럼 변화가 큰 대상은 정확히 알기 어렵기 때문에, 범용 운영체제는 예측과 time quantum을 섞은 타협형 정책을 쓴다.

대표적인 근사 방법이 지수 평균 (Exponential Averaging)이다. 과거 CPU burst 길이를 이용해 다음 burst를 예측한다.

┌────────────────────────────────────────────────────────────────────┐
│ Burst prediction for SJF-like behavior                             │
├────────────────────────────────────────────────────────────────────┤
│ tau(n+1) = alpha * t(n) + (1 - alpha) * tau(n)                    │
│                                                                    │
│ t(n)   : last actual burst                                         │
│ tau(n) : previous prediction                                       │
│ alpha  : weight for recency                                        │
└────────────────────────────────────────────────────────────────────┘

아래 판단 흐름은 SJF를 직접 쓸지, 근사할지, 피할지를 정리한 것이다.

┌────────────────────────────────────────────────────────────────────┐
│ Can SJF be used directly?                                          │
├────────────────────────────────────────────────────────────────────┤
│ burst length known or predictable?                                 │
│   ├─ yes -> SJF / SRTF candidate                                   │
│   │         └─ add aging or wait cap if starvation risk is high    │
│   └─ no  -> RR / MLFQ / fair scheduling                            │
└────────────────────────────────────────────────────────────────────┘

실무 판단 기준

burst 예측 가능성: 작업 길이를 모르면 SJF는 이론에 머문다.
최적화 목표: 평균 대기 시간 최소화가 1순위인지, 응답성·공정성이 더 중요한지 확인한다.
starvation 허용 여부: 긴 작업이 오래 밀려도 되는 환경인지 본다.
선점 비용: SRTF를 쓰면 timer interrupt와 context switch 비용이 추가된다.
보정 장치: aging, 최대 대기 시간 제한, 클래스 분리 같은 보호장치가 있는지 확인한다.

자주 나오는 안티패턴

"평균 대기 시간이 최적"이라는 이유만으로 interactive workload에 그대로 도입하는 것
전체 job length와 다음 CPU burst length를 구분하지 않는 것
예측 오차와 starvation을 무시하고 SJF를 절대 해법처럼 설명하는 것

기술사 답안에서는 SJF를 단순 암기형 알고리즘으로 쓰기보다, 왜 최적인지, 왜 현실에서는 그대로 쓰기 어려운지, 현대 스케줄러가 어떤 방식으로 그 철학을 차용했는지까지 연결해야 깊이가 생긴다.

📢 섹션 요약 비유: SJF는 오늘 주문량을 대충 아는 주방에서 빨리 끝나는 메뉴를 먼저 내는 전략이고, 언제 긴 주문이 튀어나올지 모르는 식당이라면 대기 제한과 순번 조정 장치가 함께 필요하다.

Ⅴ. 기대효과 및 결론

SJF 계열이 잘 맞는 환경에서는 평균 대기 시간과 평균 turnaround time이 모두 좋아질 수 있다. 짧은 작업이 빨리 빠져나가므로 큐 적체가 줄고, 시스템은 같은 시간에 더 많은 작업을 처리하는 것처럼 보인다. 특히 batch workload에서는 이 효과가 매우 크다.

하지만 그 이득은 정확한 burst 정보와 긴 작업에 대한 보호 장치가 있을 때만 유지된다. 정보가 불완전한 범용 환경에서는 예측 오차, starvation, 선점 비용이 곧바로 현실 문제로 바뀐다. 그래서 현대 운영체제는 SJF를 그대로 구현하기보다, 짧은 작업에 초기 우대를 주되 지나치게 오래 기다리지는 않게 하는 방향으로 진화했다.

정리하면 SJF는 실무 운영체제의 최종 답안이라기보다, 스케줄링 설계가 어디를 향해야 하는지를 보여 주는 이상적인 기준선이다. 기억할 핵심은 명확하다. 짧은 작업을 먼저 처리하면 평균은 좋아지지만, 현실 시스템은 평균만으로 운영되지 않으므로 공정성과 예측의 장치를 함께 가져야 한다.

📢 섹션 요약 비유: SJF는 "가장 효율적인 줄 세우기"를 보여 주는 모범답안이고, 실제 운영체제는 그 모범답안을 현실 교통법규와 섞어 운행하는 도시 도로와 같다.

📌 관련 개념 맵

개념	연결 포인트
CPU burst	SJF가 정렬 기준으로 삼는 직접 대상이다.
FCFS (First-Come, First-Served)	SJF가 극복하려는 convoy effect의 출발점이다.
SRTF (Shortest Remaining Time First)	SJF의 선점형 확장으로, 남은 시간 기준으로 더 적극적으로 최적화한다.
지수 평균 (Exponential Averaging)	미래 burst를 근사 예측해 SJF 철학을 현실에 가져오는 방법이다.
starvation	긴 작업이 짧은 작업에게 계속 밀려나는 SJF의 대표적 부작용이다.
MLFQ (Multilevel Feedback Queue)	짧은 작업 우대 철학을 범용 운영체제에 타협적으로 적용한 구조다.

📈 관련 키워드 및 발전 흐름도

convoy effect in FCFS
    │
    ▼
CPU burst length as priority
    │
    ▼
SJF ordering
    │
    ├──────────────▶ lower average waiting time
    │
    ├──────────────▶ SRTF preemption
    │
    └──────────────▶ burst prediction + MLFQ approximation

이 흐름도는 SJF가 FCFS의 병목을 해결하기 위해 등장했고, 이후 선점형 확장과 예측 기반 정책으로 진화해 현대 스케줄러 설계 원리로 남았음을 보여 준다.

👶 어린이를 위한 3줄 비유 설명

SJF는 금방 끝나는 숙제부터 선생님이 먼저 봐주는 규칙이에요.
그러면 짧은 숙제를 한 친구들이 오래 기다리지 않아 반 전체 평균 기다림이 줄어요.
하지만 긴 숙제는 계속 뒤로 밀릴 수 있어서 차례를 너무 늦추지 않게 도와주는 규칙도 필요해요.