임베디드 스터디 - 단일 프로세서 스케줄링 알고리즘

게시 2026/05/23

By Su Lee

5 분읽는 시간

FCFS (First Come First Served)

먼저 도착한 프로세스를 먼저 처리 — 가장 단순한 알고리즘
비선점형 : 일단 CPU를 할당받으면 완료까지 실행
단점 : 호위 효과 (Convoy Effect) — 실행시간이 긴 프로세스 뒤에 짧은 프로세스들이 줄 서서 대기

P1(10ms) → P2(4ms) → P3(2ms) 순서로 도착 시

│    P1(10ms)    │  P2(4ms)  │P3│
0               10          14  16

P2 대기시간 = 10 - 1 = 9ms (Convoy Effect 발생)

SJF (Shortest Job First)

실행시간이 짧은 프로세스를 먼저 처리 → 평균 대기시간 최소화
실행시간은 예측값 사용 (실행 전 정확한 시간을 알 수 없으므로)
한계 : 실행시간 예측이 어려워 실제 OS에서 완전한 형태로 구현하기 어려움

비선점형 SJF

CPU를 할당받으면 완료까지 실행
새 프로세스 도착 시 : 현재 실행 중인 프로세스가 끝난 후 Ready Queue에서 가장 짧은 것 선택

선점형 SJF — SRTF (Shortest Remaining Time First)

새 프로세스 도착 시 : 현재 프로세스의 남은 실행시간과 비교하여 더 짧으면 즉시 선점

P1 실행 중 (남은시간 10ms)
새 프로세스 P2 도착 (예측 실행시간 3ms)
3ms < 10ms → P1 선점, P2 즉시 실행

Priority 스케줄링

각 프로세스에 우선순위를 부여하여 높은 순서대로 실행
문제 : 기아 현상 (Starvation) — 낮은 우선순위 프로세스가 계속 밀려 영원히 실행되지 못함
해결 : 에이징 (Aging) — 오래 기다린 프로세스의 우선순위를 점진적으로 높임

Round Robin (RR)

모든 프로세스에게 동일한 타임 퀀텀(Time Quantum)을 순서대로 할당
타임 퀀텀 만료 시 강제 선점 → 다음 프로세스로 이동
선점형, 응답시간이 중요한 인터랙티브 시스템에 적합

타임 퀀텀 크기의 영향

타임 퀀텀	문제
너무 큼	FCFS와 동일해짐 → 호위 효과 재발
너무 작음	컨텍스트 스위칭 오버헤드 폭증
적절 (일반적으로 10~100ms)	응답시간·오버헤드 균형

간트차트 계산 예제

프로세스 정보:

프로세스	도착시간	실행시간
P1	0	10
P2	1	4
P3	2	2

FCFS

│      P1(10)      │   P2(4)   │P3│
0                 10          14  16

프로세스	대기시간
P1	0ms
P2	10 - 1 = 9ms
P3	14 - 2 = 12ms

\[\text{평균 대기시간} = \frac{0 + 9 + 12}{3} = 7\text{ms}\]

SJF (비선점형)

t=10에 Ready Queue: P2(4ms), P3(2ms) → P3 먼저 실행

│      P1(10)      │P3│   P2(4)   │
0                 10 12          16

프로세스	대기시간
P1	0ms
P3	10 - 2 = 8ms
P2	12 - 1 = 11ms

\[\text{평균 대기시간} = \frac{0 + 8 + 11}{3} \approx 6.33\text{ms}\]

Round Robin (타임 퀀텀 = 4ms)

│ P1 │ P2 │P3│      P1      │
0    4    8  10             16

프로세스	대기시간
P1	16 - 0 - 10 = 6ms
P2	8 - 1 - 4 = 3ms
P3	10 - 2 - 2 = 6ms

\[\text{평균 대기시간} = \frac{6 + 3 + 6}{3} = 5\text{ms}\]

비교 요약

알고리즘	선점 여부	특징	단점
FCFS	비선점형	구현 단순	호위 효과 (Convoy Effect)
SJF	비선점형	평균 대기시간 최소	실행시간 예측 어려움
SRTF	선점형	SJF의 선점 버전	실행시간 예측 어려움
Priority	선점/비선점	우선순위 기반	기아 현상 (Starvation)
Round Robin	선점형	응답시간 균등	타임 퀀텀 설정 중요

Study, Embedded Platform