CPU 스케줄링 알고리즘 (FCFS, SJF, SRT, RR, 우선순위)

🔥 매회 출제 (priority 3)

🌱 왜 배우나

CPU(Central Processing Unit, 중앙처리장치)는 한 번에 프로세스(실행 중인 프로그램) 하나만 처리할 수 있다. 그런데 컴퓨터 안에는 수십~수백 개의 프로세스가 동시에 CPU를 달라고 줄 서 있다. 규칙 없이 순서를 정하면 오래 걸리는 작업 뒤에 선 짧은 작업은 한참을 기다려야 한다. 은행 창구에 비유해 보자. “먼저 온 사람 먼저”, “간단한 업무 먼저”, “번호표를 일정 시간 단위로 돌려 가며” 이 중 어느 규칙을 쓰느냐에 따라 평균 대기시간이 완전히 달라진다. 이 “순서 정하기 규칙”이 CPU 스케줄링 알고리즘이다.

📖 핵심 개념

CPU 스케줄링은 준비 큐(CPU를 기다리는 프로세스 대기열)에서 누구에게 먼저 CPU를 줄지 정하는 규칙이다. 크게 두 방식이 있다.

• 비선점(Non-preemptive): 한 프로세스가 CPU를 잡으면 스스로 끝낼 때까지 빼앗기지 않는다.
• 선점(Preemptive): 더 급한 프로세스가 오면 실행 중인 프로세스를 중단시키고 CPU를 넘긴다.

알고리즘마다 순서를 정하는 기준이 다르다. 시험에서는 프로세스별 도착시간과 실행시간(버스트 시간)을 주고, 평균 대기시간이나 평균 반환시간을 계산하게 한다.

🔍 시각화

 준비 큐 (CPU를 기다리는 줄)
 ┌────┬────┬────┐
 │ P3 │ P2 │ P1 │ ──→ CPU ──→ 완료
 └────┴────┴────┘

 [FCFS] 먼저 온 순서대로:  P1 → P2 → P3
 [SJF]  짧은 작업 먼저:    P3 → P2 → P1
 [RR]   돌아가며 조금씩:   P1(2) → P2(2) → P3(2) → P1(2) → P2(2) → P1(2)

 ※ 괄호 안 숫자 = 타임퀀텀(한 번에 실행하는 시간 단위)

↔️ 이웃 개념 구분

• SJF vs SRT: SJF(Shortest Job First)는 비선점이라 한 번 시작하면 끝까지 간다. SRT(Shortest Remaining Time)는 SJF의 선점 버전으로, 실행 도중 남은 시간이 더 짧은 프로세스가 도착하면 바로 교체한다.
• FCFS vs RR: FCFS(First Come First Served)는 먼저 온 순서대로 끝까지 처리한다(비선점). RR(Round Robin)은 정해진 시간(타임퀀텀)만큼만 실행하고 다음 프로세스에게 넘긴다(선점). 타임퀀텀이 아주 크면 FCFS와 똑같아진다.

🔑 핵심 용어

• 도착시간(Arrival Time): 프로세스가 준비 큐에 도착한 시각
• 버스트 시간(Burst Time, 실행시간): CPU를 사용하는 데 필요한 시간
• 완료시간(Completion Time): 프로세스가 실행을 끝낸 시각
• 반환시간(Turnaround Time): 도착부터 완료까지 걸린 전체 시간 = 완료시간 - 도착시간
• 대기시간(Waiting Time): 준비 큐에서 기다린 시간 = 반환시간 - 버스트시간
• 선점(Preemptive): 실행 중인 프로세스를 강제로 중단시킬 수 있는 방식
• 비선점(Non-preemptive): 프로세스가 스스로 CPU를 반납할 때까지 기다리는 방식
• 타임퀀텀(Time Quantum): RR(Round Robin, 라운드 로빈)에서 한 프로세스가 한 번에 CPU를 쓰는 시간 단위
• 에이징(Aging): 오래 기다린 프로세스의 우선순위를 점차 올려 기아(Starvation, 영원히 실행되지 못하는 상태)를 방지하는 기법
• 콘보이 효과(Convoy Effect): FCFS에서 긴 작업 뒤에 짧은 작업들이 오래 기다리는 현상

✅ 스스로 가르쳐보기

FCFS, SJF, RR 세 알고리즘을 은행 창구 상황에 빗대어 본인 말로 설명해 보세요. 같은 프로세스 집합을 돌릴 때 어떤 알고리즘이 평균 대기시간이 제일 짧은지, 왜 그런지까지 친구에게 이어서 말해 보면 이해가 단단해집니다.

체크포인트:

• 선점과 비선점의 차이를 한 줄로 말할 수 있나요?
• SJF가 평균 대기시간을 가장 짧게 만드는 이유를 설명할 수 있나요?
• RR에서 타임퀀텀이 너무 작으면 어떤 문제가 생기는지 말할 수 있나요?
• 기아(Starvation)와 에이징(Aging)의 관계를 설명할 수 있나요?

🎯 기출 포인트

2025-2회: SJF/SRT 비교와 라운드 로빈 타임퀀텀=3일 때 평균 반환시간 11.75ms 계산 출제. 2025-2회: 라운드 로빈은 타임퀀텀이 클수록 FCFS에 가까워지고, 작을수록 문맥교환 오버헤드가 커진다. 2024-2회: SRT 평균 대기시간 6.5ms 계산 — 각 타임슬롯마다 남은 버스트시간을 다시 계산해야 한다. 계산 문제는 **간트 차트(Gantt Chart)**를 직접 그려 타임라인을 시각화하면 실수를 줄일 수 있다.

🔗 연결 개념

• mt-os-001