5. 스케줄링 알고리즘

 

💡 1분 핵심 요약 (TL;DR)

• ✅ FCFS — 도착 순서대로 처리. 구현 단순하지만 콘보이 효과(convoy effect)가 단점
• ✅ SJF — 실행 시간 짧은 작업 먼저. 평균 대기 시간↓ 하지만 아사(starvation) 현상 발생
• ✅ SRT — SJF의 선점형 버전. 잔여 시간 가장 적은 프로세스 우선, 오버헤드↑
• ✅ HRN — 대기 시간 + 실행 시간 모두 고려. 우선순위 공식: (대기시간+실행시간) / 실행시간
• ✅ RR — 타임 슬라이스 단위로 순환. 시분할 시스템 최적, 슬라이스 크기가 성능의 핵심
• ✅ MLQ / MLFQ — 우선순위별 다단계 큐. MLFQ는 CPU 사용 후 우선순위 자동 강등

 

 

 

📋 스케줄링 알고리즘 전체 분류

 

구분	알고리즘 종류
비선점형	FCFS(선착순), SJF(최단 작업 우선), HRN(최고 응답률 우선)
선점형	RR(라운드 로빈), SRT(최소 잔류 시간), MLQ(다단계 큐), MLFQ(다단계 피드백 큐)
둘 다 가능	우선순위 스케줄링

 

 

 

01 FCFS 스케줄링 — First Come, First Served

먼저 온 프로세스가 먼저 CPU를 차지하는 가장 단순한 비선점형 방식

 

📖 핵심 개념
준비 큐(Ready Queue)에 도착한 순서대로 CPU를 할당합니다. 한 번 실행이 시작되면 그 프로세스가 완전히 끝나야만 다음 프로세스가 실행됩니다. 큐가 하나뿐이라 모든 프로세스의 우선순위가 동일합니다.

 

🚢 콘보이 효과 (Convoy Effect)
처리 시간이 긴 프로세스가 CPU를 차지하면 뒤에 대기 중인 짧은 프로세스들이 모두 기다려야 합니다. 마치 느린 트럭(콘보이) 뒤에 빠른 차들이 줄지어 막히는 현상과 같아 호위 효과라고도 합니다. FCFS의 대표적 단점입니다.

 

✅ 장점 · 스케줄링 이해와 구현이 단순 · 모든 프로세스가 결국 실행되므로 기아(Starvation) 없음 · 유용한 프로세스를 지속 수행하여 처리율 높음 · 일괄 처리 시스템(Batch system)에 효율적

❌ 단점 · 비선점식이라 대화식(Interactive) 프로세스에 부적합 · 장기 실행 프로세스가 뒤 프로세스를 모두 지연 · 평균 대기 시간이 길어질 수 있음 (최악의 대기 시간) · 콘보이 효과로 시스템 효율성 저하

 

 

 

 

02 SJF 스케줄링 — Shortest Job First

실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식

 

📖 핵심 개념
준비 큐의 프로세스 중 실행 시간(Burst Time)이 가장 짧은 작업에 CPU를 먼저 할당합니다. FCFS의 콘보이 효과를 완화하여 평균 대기 시간을 줄이는 것이 목적입니다. 길고 짧은 작업의 순서를 재배치하여 시스템 효율을 높입니다.

 

⚠️ 아사(Starvation) 현상 — 무한 봉쇄
짧은 작업의 프로세스가 계속 들어오면 실행 시간이 긴 프로세스는 영원히 CPU를 할당받지 못하는 아사(기아) 현상이 발생합니다. 공평성이 현저히 떨어지는 심각한 문제입니다.

해결 방법
① 프로세스가 자신의 작업 시간을 운영체제에 미리 알려줌
② 에이징(Aging, 나이 먹기) — 프로세스가 양보할 때마다 나이를 한 살씩 먹어, 최대 나이에 도달하면 더 이상 양보하지 않도록 상한선을 설정

 

❌ 실용적 한계
운영체제가 프로세스의 종료 시간을 정확히 예측하기 어렵습니다. 현대 운영체제에서는 프로세스의 작업 길이를 사전에 알 수 없어 실제 적용이 어렵습니다.

 

 

 

03 SRT (또는 SRTF) 스케줄링 — Shortest Remaining Time First

SJF의 선점형 버전 — 잔여 실행 시간이 가장 짧은 프로세스 우선

 

📖 핵심 개념
최소 잔류 시간 우선 스케줄링(SRTF, Shortest Remaining Time First)이라고도 합니다. CPU를 할당할 프로세스를 선택할 때 남아 있는 작업 시간(잔여 실행 시간, RT)이 가장 적은 프로세스를 선택합니다. 잔여 실행 시간이 더 적은 새 프로세스가 준비 상태가 되면 현재 실행 중인 프로세스를 선점(빼앗음)합니다.

 

구분	SJF	SRT
선점 여부	비선점형	선점형
기준	총 실행 시간(BT)	잔여 실행 시간(RT)
문맥 교환	없음	빈번하게 발생 (오버헤드↑)
아사 현상	발생	발생

 

⚠️ SRT의 한계
현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산·비교해야 하므로 SJF에는 없는 추가 작업이 필요합니다. 잔여 실행 시간을 계속 추적하다 보면 오버헤드(overhead)가 발생하고, 문맥 교환이 잦아 구현과 사용이 어렵습니다. SJF와 마찬가지로 종료 시간 예측이 어려워 실제로는 잘 사용하지 않습니다.

 

 

 

04 HRN 스케줄링 — Highest Response Ratio Next

대기 시간과 실행 시간을 함께 고려해 아사 현상을 해결한 비선점형 방식

 

📖 핵심 개념
최고 응답률 우선 스케줄링이라고도 합니다. SJF의 아사 현상을 해결하기 위해 설계된 비선점형 알고리즘입니다. 실행 시간만 보는 SJF와 달리, 기다린 시간(대기 시간)과 CPU 사용 시간을 모두 고려해 우선순위를 결정합니다. FCFS와 SJF 양쪽의 약점을 동시에 보완합니다.

 

🔢 HRN 우선순위 계산 공식

우선순위 = (대기 시간 + 실행 시간) ÷ 실행 시간
(대기 시간: WT, 실행 시간: BT 기준 / 값이 클수록 먼저 실행)

 

 

✓ 계산 예시
P1(도착 0, 작업 30), P2(도착 3, 작업 18), P3(도착 6, 작업 9) 일 때 P3의 우선순위 계산:
    · P3 대기 시간(WT) = 24, 실행 시간(BT) = 9 (강의 기준)
    · 우선순위 = (24 + 9) ÷ 9 = 3.67
※ 대기 시간이 길수록 우선순위 값이 높아져 CPU를 할당받을 확률이 높아집니다.

 

✅ 장점 · 자원을 효율적으로 활용 · 기아(Starvation)가 발생하지 않음 · 긴 작업과 짧은 작업 간 불평등 보완

❌ 단점 · 오버헤드가 높을 수 있음 · 매번 우선순위를 계산해야 하므로 메모리·프로세서 낭비 발생

 

 

 

05 RR 스케줄링 — Round Robin

타임 슬라이스 단위로 순환 실행하는 대표적인 선점형 방식

 

📖 핵심 개념
한 프로세스가 할당된 타임 슬라이스(Time Slice) 동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 이동해 차례를 기다립니다. 선점형 알고리즘 중 가장 단순하고 대표적이며, 시분할(Time-sharing) 시스템을 위해 설계되었습니다. 준비 큐를 순환 큐(Circular Queue)로 구성합니다.

 

타임 슬라이스 크기에 따른 동작 차이

 

타임 슬라이스	동작	결과
매우 큰 경우 (∞에 가까울 때)	하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보임	FCFS 스케줄링과 동일
적절한 경우 (보통 10~100ms)	프로세스들이 균등하게 CPU를 나눠 씀	최적의 시분할 효과
매우 작은 경우 (예: 1ms)	문맥 교환이 너무 자주 발생, 교환 시간이 작업 시간보다 커짐	오버헤드↑ 실제 작업 불가

 

 

✓ FCFS vs RR 비교
같은 조건에서 평균 대기 시간이 FCFS(23ms)와 RR(22.33ms)이 비슷하다면, 문맥 교환 오버헤드가 추가되는 RR이 오히려 더 비효율적입니다. RR이 효과를 발휘하려면 문맥 교환 시간을 고려한 적절한 타임 슬라이스 설정이 필수입니다.

 

 

 

06 MLQ / MLFQ 스케줄링 — 다단계 큐 / 다단계 피드백 큐

우선순위별로 복수의 준비 큐를 사용하는 고급 스케줄링 방식

 

MLQ — Multilevel Queue (다단계 큐)

 

📖 핵심 개념
우선순위에 따라 준비 큐를 여러 개 사용합니다. 프로세스는 OS로부터 부여받은 우선순위에 따라 해당 큐에 삽입되며, 상단 큐의 모든 프로세스가 끝나야 다음 우선순위 큐가 실행됩니다. 우선순위는 고정형으로, 한 번 배정된 큐에서 다른 큐로 이동하지 않습니다.

 

✅ 장점 · 응답 속도가 빠름 · 우선순위별로 다른 스케줄링 알고리즘 적용 가능

❌ 단점 · 여러 큐와 알고리즘으로 추가 오버헤드 발생 · 우선순위 낮은 큐의 프로세스는 무한 대기 (아사)

 

MLFQ — Multilevel Feedback Queue (다단계 피드백 큐)

 

📖 핵심 개념
MLQ의 아사 문제를 보완한 방식입니다. MLQ와 같이 우선순위를 가진 여러 큐를 사용하지만, CPU를 사용한 프로세스의 우선순위가 자동으로 낮아집니다. 실행 후 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 이동합니다. 사전 정보 없이도 최소 작업 우선(SJF) 효과를 냅니다. 단, 하위 큐에 머무는 긴 프로세스의 기아(Starvation) 현상을 막기 위해, 일정 주기가 지나면 모든 프로세스를 다시 최상위 큐로 끌어올리는 에이징(Aging, 우선순위 상향) 기법을 필수로 함께 사용합니다.

 

구분	MLQ	MLFQ
큐 간 이동	불가 (고정 우선순위)	가능 (CPU 사용 후 우선순위 강등)
아사 현상	발생	발생 가능 (단, 완화됨)
유연성	낮음	매우 높음 (시스템에 맞게 구성)
구현 복잡도	중간	복잡, 오버헤드 큼

 

 

 

 

📊 전체 알고리즘 한눈에 비교

 

알고리즘	선점 여부	스케줄링 기준	아사 현상	주요 특징
FCFS	비선점	도착 시간	없음	가장 단순, 콘보이 효과
SJF	비선점	실행 시간(BT)	발생	평균 대기↓, 예측 어려움
SRT	선점	잔여 시간(RT)	발생	SJF 선점판, 오버헤드↑
HRN	비선점	(WT+BT)/BT	없음	SJF 아사 해결, 오버헤드↑
RR	선점	타임 슬라이스	없음	시분할 최적, 슬라이스 크기가 핵심
MLQ	선점	고정 우선순위 큐	발생	응답 빠름, 큐 간 이동 불가
MLFQ	선점	동적 우선순위 큐	발생 가능 (에이징으로 완화)	MLQ 보완, 유연·복잡

 

 

📌 핵심 정리

· FCFS : 도착 순서대로 처리. 단순·공평하나 콘보이 효과로 비효율적
· SJF : 짧은 작업 먼저. 평균 대기 시간 최소화하나 아사 현상·예측 불가 문제
· SRT : SJF의 선점형 버전. 잔여 시간 기준 선점, 오버헤드 크고 잘 사용 안 함
· HRN : (WT+BT)/BT 공식으로 우선순위 계산. 대기 시간 반영해 아사 해결
· RR : 타임 슬라이스 단위 순환 실행. 슬라이스가 크면 FCFS, 작으면 오버헤드↑
· MLQ : 고정 우선순위 다단계 큐. 응답 빠르나 낮은 우선순위 아사 문제
· MLFQ : CPU 사용 후 우선순위 자동 강등. MLQ 보완, 설계·구현 복잡

 

 

태그 : 운영체제 스케줄링 알고리즘FCFS SJF 차이콘보이 효과란SRT 스케줄링이란HRN 우선순위 계산라운드로빈 타임슬라이스MLQ MLFQ 차이아사현상 해결방법선점형 비선점형 차이CPU 스케줄링 정리