하나의 예제로 여섯 알고리즘 비교하기

이 편은 독학사 2단계 운영체제에서 계산량이 가장 많은 단원이다. 같은 프로세스 다섯 개를 놓고 알고리즘만 바꿔가며 계산해 보면, “왜 이 알고리즘이 저 알고리즘보다 평균 대기 시간이 짧은가”가 숫자로 눈에 보인다. 7편에서 배운 반환 시간·대기 시간 공식을 그대로 쓴다.

앞으로 계속 쓸 공통 프로세스 집합은 다음과 같다. 도착 시간(Arrival Time, AT)과 실행 시간(Burst Time, BT)은 밀리초 단위로, 우선순위(Priority)는 숫자가 작을수록 우선순위가 높다는 규칙을 쓴다(독학사 시험에서 자주 쓰는 규칙이며, 문제마다 반대로 정의될 수도 있으니 항상 문제 지문의 정의를 먼저 확인해야 한다).

전체 실행 시간의 합은 8+4+9+5+2 = 29가 아니라 8+4+9+5+2 = 28이다. 어떤 알고리즘을 쓰든 유휴 시간(idle time) 없이 계속 무언가를 실행할 수 있다면(이 예제는 도착 시간이 촘촘해서 항상 그렇다) 모든 알고리즘의 마지막 완료 시각은 28로 같다. 이 점을 계산 후 검산 기준으로 삼는다.

FCFS (First Come First Served, 선입선출)

정의: 준비 큐에 도착한 순서대로 CPU를 배정한다. 한 번 시작한 프로세스는 끝날 때까지 CPU를 놓지 않는 비선점형(non-preemptive) 알고리즘이다.

쉽게 말하면: 은행 창구에 도착한 순서대로 번호표를 받아 처리하는 방식이다.

도착 순서가 그대로 실행 순서가 되므로 P1 → P2 → P3 → P4 → P5 순서로 실행한다.

결과 해석: P1이 실행 시간 8로 그리 길지 않은데도 뒤에 도착한 P3(실행 시간 9)이 끝날 때까지 P4, P5가 무작정 기다려야 했다. FCFS는 구현이 단순하지만, 먼저 도착했다는 이유만으로 긴 작업이 뒤에 도착한 짧은 작업들을 막아버리는 호위 효과(convoy effect)가 생긴다. 실제로 P5는 실행 시간이 2밖에 안 되는데 대기 시간이 22나 된다 — 이 비효율을 해결하려는 시도가 다음의 SJF다.

SJF (Shortest Job First, 최단 작업 우선) — 비선점형

정의: CPU가 비었을 때, 그 시점까지 도착한 프로세스 중 실행 시간이 가장 짧은 것을 고른다. 일단 선택되면 끝까지 실행하는 비선점형 알고리즘이다.

쉽게 말하면: 계산대에서 물건이 적은 손님을 먼저 계산해 주는 방식이다.

• t=0: 도착한 프로세스는 P1뿐이다. P1을 0부터 8까지 실행한다(비선점이므로 중간에 P2·P3·P4·P5가 도착해도 끼어들 수 없다).
• t=8: 이 시점까지 도착한 P2(4), P3(9), P4(5), P5(2) 중 실행 시간이 가장 짧은 P5(2)를 선택한다. 8부터 10까지 실행한다.
• t=10: 남은 P2(4), P3(9), P4(5) 중 가장 짧은 P2(4)를 선택한다. 10부터 14까지 실행한다.
• t=14: 남은 P3(9), P4(5) 중 가장 짧은 P4(5)를 선택한다. 14부터 19까지 실행한다.
• t=19: 남은 P3(9)을 실행한다. 19부터 28까지 실행한다.

결과 해석: FCFS보다 평균 대기 시간이 11.4에서 8.2로 크게 줄었다. 짧은 작업(P5, P2)을 먼저 처리해 전체적으로 대기 줄이 빨리 줄어들기 때문이다. 이론적으로 SJF는 비선점형 알고리즘 중 평균 대기 시간을 최소화하는 최적(optimal) 알고리즘으로 증명되어 있다. 다만 대가로 P3처럼 실행 시간이 긴 프로세스는 계속 뒤로 밀릴 위험이 있다 — 이는 이 편 마지막의 기아(starvation) 절에서 다시 다룬다.

자주 틀리는 점: SJF를 “도착한 순서와 무관하게 무조건 실행 시간이 짧은 프로세스부터 고른다”고 오해하면 안 된다. 아직 도착하지 않은 프로세스는 아무리 짧아도 후보가 될 수 없다. t=0 시점에는 P1만 도착해 있으므로 실행 시간이 가장 짧은 P5(BT=2)가 아니라 P1을 실행해야 한다.

SRTF (Shortest Remaining Time First) — 선점형

정의: SJF의 선점형 버전이다. 매 순간(또는 새 프로세스가 도착할 때마다) 남은 실행 시간이 가장 짧은 프로세스를 실행하며, 더 짧은 남은 시간을 가진 프로세스가 새로 도착하면 즉시 선점한다.

쉽게 말하면: 계산대에서 계산 중간에도 물건이 더 적은 손님이 오면 순서를 바꿔주는 방식이다.

1단위 시간마다 “현재 실행 중인 프로세스”와 “새로 도착한 프로세스”의 남은 시간을 비교하며 진행한다.

• [0,1): 도착한 것은 P1(남은 8)뿐. P1 실행. 1 지난 후 P1 남은 시간 = 7.
• t=1: P2(4) 도착. 후보 {P1=7, P2=4}. P2가 더 짧다 → 선점. [1,2) P2 실행. 남은 P2=3.
• t=2: P3(9) 도착. 후보 {P1=7, P2=3, P3=9}. 여전히 P2가 최단. [2,3) P2 실행. 남은 P2=2.
• t=3: P4(5) 도착. 후보 {P1=7, P2=2, P3=9, P4=5}. 여전히 P2가 최단. [3,4) P2 실행. 남은 P2=1.
• t=4: P5(2) 도착. 후보 {P1=7, P2=1, P3=9, P4=5, P5=2}. 여전히 P2가 최단. [4,5) P2 실행. 남은 P2=0 → P2 완료(t=5).
• t=5: 후보 {P1=7, P3=9, P4=5, P5=2}. 최단은 P5(2). [5,7) P5 실행. 남은 P5=0 → P5 완료(t=7).
• t=7: 후보 {P1=7, P3=9, P4=5}. 최단은 P4(5). [7,12) P4 실행. 남은 P4=0 → P4 완료(t=12).
• t=12: 후보 {P1=7, P3=9}. 최단은 P1(7). [12,19) P1 실행. 남은 P1=0 → P1 완료(t=19).
• t=19: 후보 {P3=9}. [19,28) P3 실행 → P3 완료(t=28).

P1은 두 구간(0–1, 12–19)으로 나뉘어 실행되었다는 점에 주의한다 — 선점형 알고리즘의 특징이다.

결과 해석: 평균 대기 시간이 SJF의 8.2보다도 더 낮은 6.6이 되었다. P2는 대기 시간이 0인데, 이는 P2가 도착하자마자(t=1) 당시 실행 중이던 P1(남은 7)보다 짧아서 즉시 선점해 실행을 시작했기 때문이다. SRTF는 선점형까지 포함한 모든 스케줄링 알고리즘 중 평균 대기 시간을 최소화하는 이론적 최적 알고리즘이다. 다만 P1이 두 번 끊겼다 이어졌다 하는 데서 보듯, 문맥 교환이 잦아 6편에서 배운 오버헤드가 커진다는 대가가 따른다.

우선순위 스케줄링 (Priority Scheduling) — 비선점형

정의: 각 프로세스에 매겨진 우선순위(priority) 값에 따라 CPU를 배정한다. 이 예제에서는 숫자가 작을수록 우선순위가 높다. 비선점형이므로 한 번 시작한 프로세스는 끝까지 실행한다.

• t=0: 도착한 것은 P1(우선순위3)뿐. P1을 0부터 8까지 실행.
• t=8: 도착한 P2(1), P3(4), P4(2), P5(5) 중 숫자가 가장 작은(가장 높은 우선순위) P2(1)를 선택. 8부터 12까지 실행.
• t=12: 남은 P3(4), P4(2), P5(5) 중 P4(2)를 선택. 12부터 17까지 실행.
• t=17: 남은 P3(4), P5(5) 중 P3(4)를 선택. 17부터 26까지 실행.
• t=26: 남은 P5(5)를 실행. 26부터 28까지.

결과 해석: 우선순위가 가장 낮은(숫자 5) P5는 도착이 가장 늦었을 뿐 아니라 우선순위까지 최하위라서 맨 마지막까지 밀려 대기 시간이 22나 된다. 만약 새로운 고우선순위 프로세스가 계속 도착한다면 P5는 영원히 실행되지 못할 수도 있다 — 이 문제가 이 편 마지막 절의 기아 현상이다.

RR (Round Robin, 라운드 로빈) — 선점형, 시간 할당량 4

정의: 준비 큐를 원형으로 돌면서 각 프로세스에게 정해진 시간 할당량(time quantum)만큼만 CPU를 주고, 그 시간이 끝나면 강제로 다음 프로세스에게 넘긴다(선점). 여기서는 시간 할당량을 4로 둔다. 실행 중 새로 도착한 프로세스는 큐의 맨 뒤에 추가하고, 시간 할당량을 다 쓰고도 끝나지 않은 프로세스도 큐의 맨 뒤에 다시 넣는다. 같은 시각에 도착과 재배치가 겹치면 새로 도착한 프로세스를 먼저 큐에 넣고, 그다음 시간 할당량이 끝난 프로세스를 넣는다는 규칙을 쓴다(문제마다 반대로 정의될 수 있으니 지문을 확인해야 한다).

• [0,4): 큐 [P1]. P1(남은 8) 실행. 이 사이 t=1에 P2, t=2에 P3, t=3에 P4가 도착해 큐 뒤에 순서대로 쌓인다. t=4에 P1이 남은 4로 재배치되기 직전, 마침 t=4에 P5도 도착한다 — 규칙대로 P5를 먼저, P1을 그다음에 넣는다. 4단위 실행 후 P1 남은 시간 = 8−4 = 4. 새 큐: [P2, P3, P4, P5, P1].
• [4,8): P2(남은 4) 실행. 4단위 만에 정확히 끝난다 → P2 완료(t=8). 새 큐: [P3, P4, P5, P1].
• [8,12): P3(남은 9) 실행. 시간 할당량 4를 다 쓰고 남은 시간 = 9−4 = 5. 새 큐: [P4, P5, P1, P3].
• [12,16): P4(남은 5) 실행. 4단위 실행 후 남은 시간 = 5−4 = 1. 새 큐: [P5, P1, P3, P4].
• [16,18): P5(남은 2) 실행. 2단위 만에 끝난다(시간 할당량 4보다 적게 필요) → P5 완료(t=18). 새 큐: [P1, P3, P4].
• [18,22): P1(남은 4) 실행. 4단위 만에 끝난다 → P1 완료(t=22). 새 큐: [P3, P4].
• [22,26): P3(남은 5) 실행. 4단위 실행 후 남은 시간 = 5−4 = 1. 새 큐: [P4, P3].
• [26,27): P4(남은 1) 실행. 1단위 만에 끝난다 → P4 완료(t=27). 새 큐: [P3].
• [27,28): P3(남은 1) 실행. 1단위 만에 끝난다 → P3 완료(t=28).

결과 해석: 이 예제에서는 RR의 평균 대기 시간(13)이 여섯 알고리즘 중 가장 크게 나왔다. 시간 할당량 4가 P3(실행 시간 9)처럼 긴 프로세스를 여러 조각으로 잘라 여러 번 재배치하는 과정에서, 짧은 프로세스들도 그 사이사이 순서를 기다리게 되었기 때문이다. RR의 성능은 시간 할당량 크기에 매우 민감하다.

• 시간 할당량이 너무 크면 한 프로세스가 오래 독점해 사실상 FCFS와 비슷해진다.
• 시간 할당량이 너무 작으면 문맥 교환이 지나치게 잦아져 6편에서 배운 오버헤드가 커진다.

그럼에도 RR은 모든 프로세스가 일정 시간 안에 반드시 한 번은 CPU를 받는다는 점에서 응답 시간이 고르고 공평하며, 이 때문에 시분할 시스템의 기본 알고리즘으로 널리 쓰인다. 평균 대기 시간만으로 알고리즘의 우열을 단정할 수 없는 이유이기도 하다.

HRRN (Highest Response Ratio Next) — 비선점형, 기아 방지형 SJF

정의: SJF는 실행 시간이 짧은 프로세스를 우대하지만, 그 부작용으로 긴 프로세스가 계속 밀릴 수 있다(기아). HRRN은 여기에 “얼마나 오래 기다렸는가”까지 반영한 응답률(response ratio)을 기준으로 다음 프로세스를 고른다. 비선점형이다.

• 대기 시간: 그 프로세스가 현재 시점까지 준비 큐에서 기다린 시간(현재 시각 − 도착 시각)
• 실행 시간: 그 프로세스의 CPU 버스트 시간

응답률이 가장 높은 프로세스를 다음에 실행한다. 오래 기다릴수록(대기 시간 증가) 응답률의 분자가 커지므로, 아무리 실행 시간이 길어도 기다리는 동안 응답률이 계속 올라가 언젠가는 반드시 선택된다 — 이것이 SJF와 달리 기아를 원천적으로 막는 구조다.

• t=0: 도착한 것은 P1뿐. P1을 0부터 8까지 실행.
• t=8: 대기 시간과 응답률을 계산한다.
  • P2: 대기 8−1=7, 응답률 (7+4)/4 = 11/4 = 2.75
  • P3: 대기 8−2=6, 응답률 (6+9)/9 = 15/9 ≈ 1.667
  • P4: 대기 8−3=5, 응답률 (5+5)/5 = 10/5 = 2.0
  • P5: 대기 8−4=4, 응답률 (4+2)/2 = 6/2 = 3.0
  • 최고 응답률 P5(3.0) 선택. 8부터 10까지 실행.
• t=10: 남은 P2, P3, P4의 응답률을 다시 계산한다.
  • P2: 대기 10−1=9, 응답률 (9+4)/4 = 13/4 = 3.25
  • P3: 대기 10−2=8, 응답률 (8+9)/9 = 17/9 ≈ 1.889
  • P4: 대기 10−3=7, 응답률 (7+5)/5 = 12/5 = 2.4
  • 최고 응답률 P2(3.25) 선택. 10부터 14까지 실행.
• t=14: 남은 P3, P4의 응답률을 다시 계산한다.
  • P3: 대기 14−2=12, 응답률 (12+9)/9 = 21/9 ≈ 2.333
  • P4: 대기 14−3=11, 응답률 (11+5)/5 = 16/5 = 3.2
  • 최고 응답률 P4(3.2) 선택. 14부터 19까지 실행.
• t=19: 남은 P3만 실행. 19부터 28까지.

이 예제에서는 공교롭게도 실행 순서가 SJF와 완전히 같게 나왔다. 그래서 완료 시각·반환 시간·대기 시간, 평균값 모두 SJF와 동일하다(평균 대기 시간 8.2, 평균 반환 시간 13.8). 하지만 계산 과정 자체는 SJF와 다르다는 점이 중요하다. P3의 응답률이 t=8일 때 1.667이었다가 t=14일 때 2.333으로 계속 올라간 것을 보라 — 만약 이후에도 짧은 프로세스가 계속 새로 도착했다면, 순수 SJF는 P3을 한없이 뒤로 미룰 수 있지만 HRRN은 P3의 응답률이 결국 다른 모든 후보보다 커지는 순간이 반드시 와서 P3을 선택하게 된다.

자주 틀리는 점: “HRRN은 항상 SJF와 다른 순서로 실행된다”고 생각하면 안 된다. 이 예제처럼 대기 시간이 아직 충분히 벌어지지 않은 상황에서는 결과가 SJF와 같을 수도 있다. HRRN의 가치는 결과가 다르다는 데 있는 것이 아니라, 긴 프로세스가 무한정 밀리지 않는다는 이론적 보장에 있다.

여섯 알고리즘 한눈에 비교

이 표에서 알 수 있듯 “선점형이 항상 더 좋다”는 명제는 성립하지 않는다. RR은 선점형인데도 이 예제에서는 평균 대기 시간이 가장 컸다. 반대로 SRTF는 선점형이면서 이론적 최적값을 보였다. 알고리즘 선택은 시스템의 목표(처리량 위주냐 응답성 위주냐, 대화형이냐 일괄 처리냐)에 따라 달라진다는 점이 독학사 시험에서 “다음 중 옳은 것은?” 유형으로 자주 나온다.

기아와 에이징

기아(starvation)는 특정 프로세스가 스케줄링 정책 때문에 CPU를 영원히, 혹은 매우 오랫동안 배정받지 못하는 현상이다. 위에서 본 우선순위 스케줄링의 P5(우선순위 최하위)나, SJF·SRTF에서 계속 짧은 프로세스에게 밀리는 긴 프로세스(P3 계열)가 그 예다. 만약 새로운 고우선순위(또는 짧은) 프로세스가 끊임없이 도착한다면, 낮은 우선순위(또는 긴) 프로세스는 이론상 무한정 대기할 수 있다.

쉽게 말하면: 기아는 계산대에서 “물건 적은 손님 먼저” 규칙 때문에, 카트 가득 채운 손님이 뒤에 온 빈손 손님들에게 계속 밀려 영원히 차례가 안 오는 상황이다.

에이징(aging)은 이 기아를 막기 위한 대표적인 해결책이다. 프로세스가 준비 큐에서 기다리는 시간이 길어질수록 그 프로세스의 우선순위를 점진적으로 높여주는 방식이다. 예를 들어 10단위 시간마다 대기 중인 프로세스의 우선순위 값을 1씩 낮춰준다면(숫자가 작을수록 높은 우선순위이므로), 아무리 우선순위가 낮게 시작한 프로세스라도 충분히 오래 기다리면 결국 가장 높은 우선순위를 얻어 실행된다.

이 편에서 다룬 HRRN은 별도의 “에이징 규칙”을 추가한 것이 아니라, 응답률 공식 자체에 대기 시간이 분자로 들어 있어서 자동으로 에이징 효과를 낸다. 이 점이 HRRN이 “SJF의 장점(짧은 작업 우대)은 살리면서 기아는 막는 절충안”으로 소개되는 이유다.

자주 틀리는 점: “에이징은 우선순위를 낮추는 것”으로 헷갈리는 경우가 있다. 에이징은 오래 기다린 프로세스를 우대하기 위해 우선순위를 높이는(숫자 규칙이면 숫자를 낮추는) 조치다. 방향을 반대로 외우면 정의를 묻는 문제에서 바로 틀린다.

핵심 정리

• FCFS는 단순하지만 호위 효과로 평균 대기 시간이 가장 크게 나올 수 있다(이 예제 11.4).
• SJF는 비선점형 중 평균 대기 시간을 최소화하는 최적 알고리즘이지만 긴 작업이 기아를 겪을 수 있다(이 예제 8.2).
• SRTF는 선점형까지 포함해 이론적으로 평균 대기 시간이 가장 짧은 알고리즘이지만 문맥 교환 오버헤드가 크다(이 예제 6.6).
• 우선순위 스케줄링은 중요 작업을 먼저 처리할 수 있지만 저우선순위 작업이 기아를 겪을 수 있다.
• RR은 공평한 응답성을 보장하지만 시간 할당량 설정에 따라 평균 대기 시간이 크게 달라진다(이 예제 13.0, 가장 큼).
• HRRN은 응답률 공식(대기 시간+실행 시간)/실행 시간으로 SJF의 효율과 기아 방지를 동시에 달성한다.
• 기아는 특정 프로세스가 무한정 CPU를 못 받는 현상이고, 에이징은 대기 시간에 비례해 우선순위를 높여 이를 막는 대표적 해법이다.

마무리 복습

참고 자료

• KOCW 운영체제 강의자료 - 스케줄링/동기화/가상메모리 
• 운영체제_Study 저장소 README 
• 한빛아카데미 운영체제 도서 정보