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

핵심 개념

우선순위 스케줄링(Priority Scheduling)은 각 프로세스에 **우선순위 값(정수)**을 부여하고, 가장 높은 우선순위의 프로세스에게 CPU를 할당하는 알고리즘이다. 같은 우선순위이면 FCFS로 결정한다. 일반적으로 낮은 숫자 = 높은 우선순위이다.

비유하면, 응급실에서 환자 치료 순서와 같다. 중증 환자(높은 우선순위)가 먼저 치료받는다.

동작 원리

우선순위 정의 방식

구분	설명	예시
내부적(Internal)	측정 가능한 양으로 계산	시간 제한, 메모리 요구량, I/O 대 CPU 버스트 비율
외부적(External)	OS 외부 기준으로 설정	프로세스 중요도, 비용, 정치적 요인

선점형 vs 비선점형

• 선점형: 높은 우선순위 프로세스 도착 시 현재 프로세스 선점
• 비선점형: 현재 프로세스가 CPU를 반납할 때까지 대기

기아(Starvation) 문제와 에이징(Aging)

문제: 높은 우선순위 프로세스가 계속 도착하면 낮은 우선순위 프로세스가 영원히 실행되지 못한다. MIT에서 1973년 IBM 7094 종료 시, 1967년에 제출된 낮은 우선순위 프로세스가 아직 실행되지 않았던 사례가 있다.

해결책 - 에이징(Aging):

• 대기 시간이 길어질수록 우선순위를 점진적으로 증가
• 예: 매 초마다 우선순위 +1
• 우선순위 127 → 0이 되는 데 약 2분 소요 (0~127 범위)

Priority + Round-Robin 결합

같은 우선순위 내에서는 Round-Robin으로 스케줄링한다:

우선순위 0: [P2]        ◀── 가장 먼저 실행
우선순위 1: [P5, P7]    ◀── RR로 교대 실행
우선순위 2: [P1, P3]
우선순위 n: [P4, P6]    ◀── 가장 나중에 실행

예시

프로세스	Burst	Priority
P1	10ms	3
P2	1ms	1 (최고)
P3	2ms	4
P4	1ms	5
P5	5ms	2

P2 P5     P1           P3  P4
├──┼──────┼────────────┼───┼──┤
0  1      6           16  18 19

평균 대기 시간 = (0+1+6+16+18)/5 = 8.2ms

관련 개념

• CPU 스케줄링 (CPU Scheduling) - 스케줄링의 일반 개념
• FCFS 스케줄링 - 도착 순서 기반 스케줄링
• 다단계 큐 스케줄링 - 우선순위별 큐 분리
• 우선순위 역전 (Priority Inversion) - 우선순위 기반 스케줄링의 문제