[운영체제] CPU 스케줄링 알고리즘(FCFS, SJF, RR, Priority) 개념 및 평가 기준 완전 정리

컴퓨터공학과 운영체제 과목에서 "어떤 프로세스에게 CPU 자원을 먼저 할당할 것인가?"를 결정하는 CPU 스케줄링(CPU Scheduling)은 시험의 단골 출제 파트입니다.

"비선점형과 선점형 스케줄링의 차이는 무엇일까?"

"반환 시간(Turnaround Time)과 대기 시간(Waiting Time)은 어떻게 계산하고, 각 알고리즘의 장단점은 무엇일까?"

스케줄링의 기본 평가 기준부터 4가지 대표 알고리즘, 그리고 기아 현상(Starvation)과 에이징(Aging) 개념까지 깔끔하게 정리해 드립니다!

1. CPU 스케줄링 평가 기준 (Scheduling Criteria)

시험에서 각 프로세스의 대기 시간, 반환 시간, 응답 시간을 계산하라는 간트 차트(Gantt Chart) 문제가 단골로 출제됩니다. 계산식 기준을 정확히 알고 있어야 합니다.

• CPU 이용률 (CPU Utilization): 전체 시간 중 CPU가 실제로 일한 시간의 비율 (최대화)
• 처리량 (Throughput): 단위 시간당 완료된 프로세스의 개수 (최대화)
• 반환 시간 (Turnaround Time): 프로세스가 제출된 시점부터 완료될 때까지 걸린 전체 시간 (최소화)
• $$\text{반환 시간} = \text{종료 시간} - \text{도착 시간}$$
• 대기 시간 (Waiting Time): 프로세스가 준비 큐(Ready Queue)에서 기다린 시간의 총합 (최소화)
• $$\text{대기 시간} = \text{반환 시간} - \text{실행 시간(CPU Burst Time)}$$
• 응답 시간 (Response Time): 프로세스가 요청된 후 첫 번째 응답이 나올 때까지 걸린 시간 (최소화)

2. 선점 vs 비선점 스케줄링

구분	비선점형 (Non-Preemptive)	선점형 (Preemptive)
개념	한 프로세스가 CPU를 할당받으면 스스로 종료되거나 I/O 대기 상태가 될 때까지 CPU를 독점	OS가 강제로 CPU 사용권을 빼앗아 다른 프로세스에게 할당 가능
장단점	오버헤드가 적지만 시분할 시스템에 불리함	응답 속도가 빠르지만 문맥 교환(Context Switch) 오버헤드가 크음
대표 알고리즘	FCFS, SJF(비선점형), HRN	Round Robin(RR), SRTF, Priority(선점형)

3. 대표 CPU 스케줄링 알고리즘 4가지

시분할 시스템의 대표적 선점형 알고리즘인 라운드 로빈(Round Robin) 동작 구조. 출처: Gate Vidyalay

1️⃣ FCFS (First-Come, First-Served)

• 방식: 비선점형 / 준비 큐에 먼저 도착한 프로세스를 먼저 처리하는 가장 단순한 방식.
• 문제점 (호위 효과, Convoy Effect): 실행 시간이 매우 긴 프로세스가 먼저 도착하면, 뒤에 있는 짧은 프로세스들이 계속 대기하게 되어 평균 대기 시간이 극도로 늘어나는 현상이 발생합니다.

2️⃣ SJF (Shortest Job First)

• 방식: 비선점형 / CPU 실행 시간(Burst Time)이 가장 짧은 프로세스에게 우선 할당.
• 장점: 주어진 프로세스 집합에 대해 최소 평균 대기 시간(Minimum Average Waiting Time)을 보장하는 이상적인 알고리즘입니다.
• 문제점:
  • 실제 환경에서는 프로세스의 다음 CPU Burst Time을 사전에 정확히 알 수 없습니다.
  • 기아 현상 (Starvation): 실행 시간이 긴 프로세스는 짧은 프로세스가 계속 들어올 경우 영원히 CPU를 할당받지 못할 수 있습니다.

3️⃣ RR (Round Robin)

• 방식: 선점형 / 현대 OS에서 널리 쓰이는 시분할 방식. 동일한 크기의 할당 시간(Time Quantum / Time Slice)을 부여하고, 시간이 지나면 CPU를 반납하고 큐의 맨 뒤로 이동합니다.
• 특징:
  • 응답 시간이 매우 빨라 다중 사용자 / 시분할 시스템에 적합합니다.
  • Time Quantum 크기가 핵심:
    • 너무 크면 $\rightarrow$ FCFS와 동일하게 동작
    • 너무 작으면 $\rightarrow$ 빈번한 문맥 교환(Context Switch)으로 오버헤드가 극대화됨

4️⃣ 우선순위 스케줄링 (Priority Scheduling)

• 방식: 각 프로세스마다 우선순위(Priority)를 부여하여 가장 높은 프로세스에게 CPU를 할당 (선점/비선점 모두 가능).
• 문제점: 우선순위가 낮은 프로세스는 CPU를 할당받지 못하는 기아 현상(Starvation) 발생.
• 해결책 (에이징, Aging): 대기 시간이 길어질수록 프로세스의 우선순위를 순차적으로 높여주는 기법.

4. 한눈에 끝내는 핵심 요약표 (★시험 필수)

알고리즘	선점 여부	핵심 특징 및 기준	주요 이슈 및 해결책
FCFS	비선점	도착 순서대로 처리	호위 효과 (Convoy Effect) 발생
SJF	비선점/선점	실행 시간(Burst Time)이 짧은 순	평균 대기 시간 최소, 기아 현상 발생
RR	선점	타임 퀀텀(Time Quantum) 단위 교대	타임 슬라이스 크기 설정이 핵심
Priority	선점/비선점	부여된 우선순위가 높은 순	기아 현상 $\rightarrow$ **에이징(Aging)**으로 해결

5. 시험 단골 출제 유형 체크

1. Q. 실행 시간이 긴 프로세스가 CPU를 독점하여 뒤따르는 짧은 프로세스들의 대기 시간이 늘어나는 현상은?
2. 👉 호위 효과 (Convoy Effect)라고 하며, FCFS 알고리즘에서 주로 발생합니다.
3. Q. 우선순위 스케줄링이나 SJF에서 발생할 수 있는 기아 현상(Starvation)을 해결하기 위한 대표 기법은?
4. 👉 오래 대기한 프로세스의 우선순위를 높여주는 에이징 (Aging) 기법입니다.
5. Q. 이론적으로 평균 대기 시간을 최소화하는 CPU 스케줄링 알고리즘은?
6. 👉 SJF (Shortest Job First) 알고리즘입니다.