SRTF (Shortest Remaining Time First) 스케줄링

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

본질: SRTF (Shortest Remaining Time First)는 가장 짧은 작업을 우선시하는 SJF(Shortest Job First) 알고리즘에 타이머 인터럽트를 결합한 '선점형(Preemptive)' 변종이다.

가치: 현재 실행 중인 프로세스의 남은 실행 시간(Remaining Time)보다 더 빨리 끝날 수 있는 새로운 프로세스가 Ready 큐에 도착하면, 얄짤없이 즉각적으로 CPU를 빼앗아 교체하므로 수학적 최적의 평균 대기 시간을 극한까지 뽑아낸다.

융합: 그러나 SJF와 마찬가지로 미래의 실행 시간을 완벽히 알 수 없다는 근본 한계, 무거운 프로세스는 영원히 실행되지 못하는 기아 상태(Starvation), 그리고 빈번한 선점(Preemption)으로 인한 문맥 교환 오버헤드 폭발로 인해 현대 OS에서는 쓰이지 않는 이론적 방어선 모델이다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: SRTF 알고리즘은 매 스케줄링 시점마다 Ready 큐에 있는 모든 프로세스와 현재 Running 중인 프로세스의 **"남은 잔여 시간(Remaining Time)"**을 비교하여, 가장 숫자가 작은 프로세스에게 무조건 CPU를 할당하는 선점형 스케줄링 기법이다.
필요성: 기본 비선점형 SJF는 한 번 긴 작업이 CPU를 잡으면, 그 뒤에 1ms짜리 초단기 작업이 수백 개 도착해도 끝날 때까지 멍청하게 기다려야 했다. 이는 SJF의 철학(짧은 놈부터 끝내서 대기시간을 줄이자)에 정면으로 위배되는 호위 효과(Convoy Effect)의 잔재였다. 이를 부수기 위해 "새로운 짧은 놈이 나타나면 하던 걸 멈추고 즉시 갈아타자"는 강력한 강제력(선점)이 필요했다.
💡 비유: 주유소에서 내 차에 기름을 10분째 넣고 있는데 (잔여 5분), 오토바이가 와서 "저 1분이면 끝나요!"라고 하면 주유기를 뽑아서 오토바이 먼저 주유해 주고 내 차는 다시 뒤로 밀려나는 **'궁극의 새치기 허용 시스템'**과 같다.
등장 배경: 시스템 처리량 중심의 메인프레임 시대를 지나 시분할 대화형 시스템이 도래하면서, 사용자의 짧은 입력(I/O 바운드)에 최대한 빨리 반응해야 했다. 비선점 방식은 응답 시간(Response Time) 방어가 불가능했기에, 인터럽트 하드웨어의 지원을 받아 실행 중인 놈을 끌어내리는 SRTF의 개념이 이론적으로 확립되었다.

  [비선점 SJF vs 선점형 SRTF의 운명적 갈림길]

  (상황: 100ms짜리 P1이 실행된 지 10ms 경과. 남은 시간=90ms)
  (갑자기 5ms짜리 P2 도착!)
  
  [비선점 SJF의 대답]
  P1 : "나 한 번 시작했으니 90ms 남은 거 다 끝날 때까지 절대 못 비켜. P2 너 큐에서 기다려."
  결과 : P2 응답 시간 박살.
  
  [선점형 SRTF의 대답 (스케줄러 개입)]
  스케줄러 : "잠깐! P1 남은 시간(90) > P2 남은 시간(5) 이네? 
           P1 당장 내려오고 P2부터 5ms 돌려버려!"
  결과 : P2 즉시 완료 후 퇴장, P1은 5ms 뒤에 남은 90ms 재개.

[다이어그램 해설] 비선점형 SJF는 타이머 인터럽트가 없어서 중간에 더 짧은 작업이 들어와도 상황 변화에 대처할 능력이 없다. 반면 SRTF는 새로운 프로세스가 Ready 큐에 진입할 때마다(트리거) 즉시 스케줄러가 깨어나 남은 시간을 저울질하는 기민함을 보여준다.

📢 섹션 요약 비유: 수술 도중(CPU 연산 중)이라도 바깥에서 더 금방 끝날 수 있는 위급 환자가 도착하면, 즉시 수술 부위를 임시로 덮어두고(Context Switch) 새 환자부터 수술하는, 철저하게 '가장 빨리 끝낼 수 있는 타깃'만 쫓는 사냥꾼입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

SRTF의 깐깐한 간트 차트 (Gantt Chart) 증명

SRTF의 동작은 프로세스가 '도착'할 때마다 선점 여부를 확인하므로, 시뮬레이션이 매우 역동적으로 변한다.

[시뮬레이션 조건]

프로세스	도착 시간 (Arrival)	CPU 버스트 (Burst)
P1	0 ms	8 ms
P2	1 ms	4 ms
P3	2 ms	9 ms
P4	3 ms	5 ms

  ┌───────────────────────────────────────────────────────────────────────────┐
  │         SRTF (선점형) 스케줄링 시뮬레이션 타임라인                        │
  ├───────────────────────────────────────────────────────────────────────────┤
  │                                                                           │
  │  0      1      2       3               5             10          17     26│
  │  │ P1 │ P2 │ P2 │ P2  │ P2 종료    │ P4 종료   │ P1 종료   │ P3 종료      │
  │  │(1ms)│(1ms)│(1ms)│(2ms)│           │ (5ms)     │ (7ms)     │ (9ms)      │
  │  └──────┴──────┴───────┴───────────────┴───────────┴───────────┴──────────┘
  │                                                                           │
  │  [시간별 스케줄러 두뇌 분석]                                              │
  │  - 0ms: P1밖에 없으므로 P1 실행 (남은 시간: 8)                            │
  │  - 1ms: P2(4) 도착! P1 남은시간(7) > P2(4). 💥P1 쫓겨나고 P2 실행!        │
  │  - 2ms: P3(9) 도착! P2 남은시간(3) < P3(9). P2 계속 실행.                 │
  │  - 3ms: P4(5) 도착! P2 남은시간(2) < P4(5). P2 계속 실행.                 │
  │  - 5ms: P2 종료! 이제 남은 건 P1(7), P3(9), P4(5). 제일 짧은 P4 실행!     │
  │  - 10ms: P4 종료! 남은 건 P1(7), P3(9). 짧은 P1 이어서 실행!              │
  │                                                                           │
  │  ▶ 평균 대기 시간: P1(9)+P2(0)+P3(15)+P4(2) / 4 = 6.5 ms                  │
  │    (동일 조건에서 비선점 SJF는 7.75 ms, SRTF가 승리!)                     │
  └───────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] P1 입장에서 보면 환장할 노릇이다. 0ms에 1등으로 도착해서 1ms 돌렸는데 P2한테 뺏기고, P2가 끝나니까 이번엔 새로 온 P4한테 또 밀려서 10ms가 지나서야 겨우 다시 CPU를 잡았다. 반면 시스템 전체 입장에서는, 가벼운 P2와 P4가 도착하자마자 순식간에 시스템을 뚫고 나가버렸으므로 평균 대기 시간이 비선점 방식보다 훨씬 더 수학적인 극솟값에 수렴하게 된다.

📢 섹션 요약 비유: 이 알고리즘은 오직 "누가 지금 당장 가장 빨리 방을 뺄 수 있는가?"만 묻습니다. 방금 들어온 사람이라도 제일 빨리 나갈 수 있다면 무조건 최고 VIP 대우를 해주고, 오래 있던 덩치 큰 사람은 찬밥 신세로 굴립니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

SRTF의 3대 치명적 약점 (오버헤드 붕괴 지점)

SRTF가 모든 알고리즘을 압살하는 '대기 시간의 신'임에도 버려진 이유는, 그 대기 시간을 줄이기 위해 지불해야 하는 **세금(오버헤드)**이 너무 막대했기 때문이다.

약점	상세 설명 및 치명타 요인
1. 잦은 문맥 교환 (Context Switch)	짧은 놈이 계속 연달아 들어오면 CPU는 1ms마다 프로세스를 교체(선점)해야 한다. 레지스터 저장/복원과 TLB 플러시에 걸리는 디스패치 지연 때문에 정작 연산은 못 하고 스케줄러 뻘짓만 하다가 처리량(Throughput)이 수직 낙하한다.
2. 영원한 기아 (Starvation)	SJF보다 훨씬 악랄하다. 100ms 남은 작업은 뒤에 99ms, 98ms짜리가 계속 쏟아져 들어오면 시스템 전원이 꺼질 때까지 단 한 틱(Tick)도 전진하지 못하고 Ready 큐에 박제된다.
3. 미래 예측 불가의 벽	"남은 시간"을 빼기(-) 하려면 처음에 전체 길이를 알아야 하는데, OS는 프로세스가 언제 끝날지 절대 알 수 없다. 지수 평균법으로 추측할 순 있지만, 예측이 빗나갈 때마다 선점이 뒤틀려 커널이 대혼란에 빠진다.

라운드 로빈 (RR) 과의 비교

둘 다 선점형(Preemptive)이지만 목적이 완전히 다르다.

라운드 로빈(RR): "모두에게 공평하게 10ms씩만 썰어줄 테니 공평하게 뺑뺑이 돌자." (시간 분할, 타이머 기반 선점, 퀀텀 소진 시 강제 쫓겨남)
SRTF: "시간 쪼개기 그딴 거 없고, 무조건 짧은 놈부터 끝장낸다. 더 짧은 놈 오면 그때만 뺏는다." (크기 기반 선점)
📢 섹션 요약 비유: 성적(남은 시간)에 따라 1등부터 밥을 주는 철저한 약육강식의 급식소입니다. 공부 못하는 덩치 큰 학생(긴 프로세스)은 전교 1등들이 끝없이 전학을 오면 1년 내내 밥을 굶어야 하는 디스토피아가 펼쳐집니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

SRTF의 유산, 최단 잔여 시간의 부활 (Redis, DB 쿼리): OS 커널에서는 쫓겨났지만, 실행 시간이 명확히 보이는 애플리케이션 세계에서는 이 개념이 광범위하게 쓰인다. 데이터베이스 시스템에서 락(Lock) 경합이 발생하여 교착상태(Deadlock)를 강제로 끊어내야 할 때(희생자 선택), DBMS는 롤백(Rollback) 비용을 최소화하기 위해 "가장 작업 진행률이 낮은 (또는 남은 작업이 많은) 트랜잭션을 킬(Kill)하고, 남은 작업이 짧은 놈을 살려주는" 사실상의 SRTF 판단 로직을 채택한다.
리눅스 CFS (Completely Fair Scheduler)의 가상 실행 시간 (vruntime): 현대 리눅스는 이 끔찍한 기아 현상을 막으면서도 SRTF의 장점(짧은 I/O 바운드의 빠른 응답성)을 가져오기 위해 천재적인 해법을 냈다. 남은 시간이 아니라 **"지금까지 CPU를 쓴 누적 시간(vruntime)"**이 가장 적은 놈을 RB-트리 맨 왼쪽에 위치시켜 제일 먼저 선점형으로 실행시킨다. 짧게 치고 빠지는 I/O 바운드는 누적 시간이 항상 적으므로, 큐에 돌아오자마자 SRTF처럼 즉각적으로 무거운 놈을 쫓아내고 CPU를 탈취할 수 있게 된다.

  ┌──────────────────────────────────────────────────────────────────┐
  │     SJF/SRTF 철학이 현대 OS(Linux CFS)로 진화한 타협의 궤적      │
  ├──────────────────────────────────────────────────────────────────┤
  │                                                                  │
  │   [과거: 절대적 크기 비교 (SRTF)]                                │
  │   - 기준: "미래에 남은 길이" (예측 불가!)                        │
  │   - 문제: 1. 예측 불가, 2. 무거운 놈은 평생 굶음 (기아)          │
  │                │                                                 │
  │                ▼ (철학의 전환: 과거를 보고 빚진 만큼 갚아주자)   │
  │                                                                  │
  │   [현대: 누적 사용량 비교 (Linux CFS - vruntime)]                │
  │   - 기준: "과거에 내가 CPU를 얼마나 썼는가?" (100% 팩트 추적)    │
  │   - 효과 1 (I/O 바운드): 타이핑/마우스 하느라 대기만 한 놈은     │
  │           vruntime이 극도로 낮아, 깨어나면 즉시 CPU를 선점함!    │
  │           (▶ SRTF의 '짧은 놈 즉각 응답' 효과 완벽 재현)          │
  │   - 효과 2 (CPU 바운드): 굶고 있으면 남들 vruntime이 높아져서    │
  │           결국 내 순서가 돌아옴 (▶ 기아 상태 완벽 방어)          │
  └──────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 커널 해커들이 "미래를 알 수 없다면, 과거의 빈곤함(대기 시간)을 기준으로 짧은 놈들을 우대해 주자"라고 방향을 튼 역사적 진화를 보여준다. I/O 바운드는 본질적으로 CPU 연산 시간이 극도로 짧은(Shortest) 작업들이기 때문에, vruntime을 적게 올리는(빚을 적게 지는) 방식으로 스케줄러를 속여 사실상 SRTF와 똑같이 무거운 놈들을 새치기하며 시스템 응답성을 극한으로 올릴 수 있게 된 것이다.

📢 섹션 요약 비유: 옛날엔 "네가 얼마나 빨리 달릴 수 있니?"를 물어보고 먼저 출발시켰다면(SRTF, 사기 치기 쉬움), 지금은 "너 지금까지 얼마나 못 뛰고 쉬었니?"를 기록해 놓고(CFS), 많이 쉰 사람을 무조건 앞줄에 세워주는 완벽하게 공정한 시스템으로 진화했습니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

SRTF가 만약 완벽하게 구현된다면, 사용자 인터페이스 창에서 마우스를 클릭하는 수많은 초단기 이벤트들이 큐에 들어오는 즉시 무거운 백그라운드 작업을 밀어내고 즉각 응답하므로, 지연율(Latency)이 0에 수렴하는 궁극의 시스템을 경험할 수 있다.

결론 및 미래 전망

SRTF는 "문맥 교환 오버헤드가 제로(0)이고 미래를 알 수 있다"는 불가능한 두 가지 전제가 있어야만 성립하는 공상과학 속 알고리즘이다. 그러나 컴퓨터 공학에서 이러한 극한의 이상적 수학 모델(Theoretical Lower Bound)은 필수적이다. 새로운 스케줄링 알고리즘을 개발할 때마다, 그 성능이 "완벽한 SRTF의 몇 퍼센트 수준까지 근접했는가?"를 평가하는 벤치마크 잣대로 영원히 쓰일 것이기 때문이다.

📢 섹션 요약 비유: 빛의 속도(SRTF)로 우주를 여행하는 건 현재 기술로 불가능하지만, 빛의 속도라는 절대적인 기준선이 있어야 우리가 만든 로켓(현대 스케줄러)이 우주에서 얼마나 빠르고 효율적인지 채점할 수 있는 것과 같습니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
SJF (Shortest Job First)	SRTF의 뼈대가 되는 비선점형 부모 알고리즘으로, 여기에 '선점'이라는 무기를 쥐여준 것이 SRTF다.
선점형 스케줄링 (Preemptive)	SRTF가 무거운 놈을 강제로 쫓아낼 수 있게 해주는 합법적 폭력(타이머 인터럽트와 우선순위 강탈) 시스템이다.
기아 상태 (Starvation)	SRTF의 치명적 결함으로, 새롭고 짧은 프로세스가 끝없이 유입될 때 덩치 큰 프로세스가 평생 레디 큐에 갇히는 현상이다.
문맥 교환 (Context Switch)	짧은 놈이 계속 들어오면 SRTF가 미친 듯이 스위칭을 유발하여 오히려 전체 시스템을 마비시키는 최악의 오버헤드다.
가상 실행 시간 (vruntime)	리눅스가 미래 예측(SRTF)을 포기하고, 과거의 실행 시간(팩트)을 바탕으로 짧은 프로세스를 즉각 선점시키기 위해 고안한 천재적 지표다.

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

내가 레고를 2시간째 만들고 있는데, 갑자기 동생이 와서 "나 1분만 레고 블록 하나만 꽂을래!"라고 해요.
이때 부모님(스케줄러)이 "동생이 훨씬 빨리 끝나니까 네가 쓰던 레고판 당장 비켜줘!"라고 강제로 뺏어서 동생 먼저 하게 해주는 게 SRTF 예요.
짧게 끝나는 친구들은 바로바로 다 놀고 나가니까 너무 행복하지만, 큰 레고를 만드는 나는 동생 친구들이 올 때마다 계속 비켜줘야 해서 밤샐 때까지 레고를 완성 못하는 슬픈 단점이 있어요.