비선점형 CPU 스케줄링 완전 정리: FCFS, SJF, Priority

CPU 스케줄링이란?

CPU 스케줄링은 여러 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정하는 운영체제의 핵심 기능입니다.
멀티태스킹 시스템에서는 프로세스가 동시에 실행되는 것처럼 보이지만, 실제로는 CPU가 매우 빠른 속도로 프로세스 간 전환(Context Switching)을 통해 처리하고 있습니다.

스케줄링 방식은 선점형(Preemptive)과 비선점형(Non-preemptive)으로 나뉘며, 여기서는 비선점형 알고리즘 중 대표적인 FCFS, SJF, 우선순위에 대해 다뤄보겠습니다!

---

비선점형 스케줄링의 개념

비선점형(Non-preemptive) 스케줄링은 한 번 CPU를 할당받은 프로세스가 자신의 작업을 모두 끝낼 때까지 CPU를 점유하는 방식입니다.
다른 프로세스가 아무리 급한 작업이라도, 현재 실행 중인 프로세스를 중간에 강제로 중단하지 않습니다.

---

1. FCFS(First-Come, First-Served) 스케줄링

개념

• 프로세스가 도착한 순서대로 CPU를 할당
• FIFO(선입선출) 큐 구조와 유사

예시

프로세스	도착 시간	실행 시
P1	0	5
P2	1	3
P3	2	8
P4	3	6

Gantt 차트

|  P1  |  P2  |    P3    |   P4   |
0     5     8         16       22

• 실행 순서: P1 → P2 → P3 → P4

프로세스	시작 시간	종료 시간	대기 시간	반환 시간
P1	0	5	0	5
P2	5	8	4	7
P3	8	16	6	14
P4	16	22	13	19

• 평균 대기 시간 = (0 + 4 + 6 + 13) / 4 = 5.75
• 평균 반환 시간 = (5 + 7 + 14 + 19) / 4 = 11.25

장점

• 구현이 쉽고 간단함
• 도착 순서대로 실행되어 공정하게 보임

단점

• Convoy Effect(호위 효과) 발생: 긴 작업 때문에 짧은 작업들이 지연됨
• 평균 대기 시간이 길어질 수 있음

---

2. SJF(Shortest Job First) 스케줄링 – 비선점형

개념

• 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당
• 실행 시간이 같을 경우 도착 순서 기준

예시

프로세스	도착 시간	실행 시간
P1	0	6
P2	2	4
P3	4	2
P4	5	8

 

Gantt

|  P1  |  P3  |  P2  |    P4    |
0     6     8     12       20

• 실행 순서: P1 → P3 → P2 → P4

각 프로세스별 대기 시간, 반환 시간

프로세스	시작 시간	종료 시간	대기 시간	반환 시간
P1	0	6	0	6
P3	6	8	2	4
P2	8	12	6	10
P4	12	20	7	15

• 평균 대기 시간 = (0 + 2 + 6 + 7) / 4 = 3.75
• 평균 반환 시간 = (6 + 4 + 10 + 15) / 4 = 8.75

장점

• 평균 대기 시간을 최소화하는 이론적으로 가장 효율적인 알고리즘
• 짧은 작업을 빠르게 처리해 시스템 반응성을 높임

단점

• 실행 시간(버스트 타임)을 미리 알아야 함
• 긴 작업은 계속 뒤로 밀리는 기아(Starvation) 문제 발생 가능

---

3. 우선순위(Priority) 스케줄링 – 비선점형

개념

• 각 프로세스에 우선순위(Priority)를 부여하고, 우선순위가 높은 프로세스에게 CPU를 먼저 할당
• 같은 우선순위이면 FCFS 방식으로 처리

예시

프로세스	도착 시간	실행 시간	우선순위 (낮을수록 높음)
P1	0	10	2
P2	1	1	1
P3	2	2	3
P4	3	1	4

Gantt

|  P1  |  P2  |  P3  |  P4  |
0     10    11    13    14

• 실행 순서: P1 → P2 → P3 → P4

각 프로세스별 대기 시간, 반환 시간

프로세스	시작 시간	종료 시간	대기 시간	반환 시간
P1	0	10	0	10
P2	10	11	9	10
P3	11	13	9	11
P4	13	14	10	11

 

• 평균 대기 시간 = (0 + 9 + 9 + 10) / 4 = 7.0
• 평균 반환 시간 = (10 + 10 + 11 + 11) / 4 = 10.5

장점

• 중요한 작업을 빠르게 처리할 수 있어 유연한 작업 처리 가능
• 서비스 우선순위가 필요한 시스템에 적합

단점

• 기아 현상 발생 가능 (낮은 우선순위 프로세스가 무기한 대기)
• 우선순위 기준 설정이 애매하면 효율성 저하

---

성능 지표 비교

알고리즘	평균 대기 시간	평균 반환 시간	응답 시간	구현 용이	기아 가능성
FCFS	5.75	11.25	느림	매우 쉬움	낮음
SJF	3.75	8.75	빠름	보통	있음
Priority	7.00	10.50	보통	어려움	있음

---

면접 대비 자주 묻는 질문과 예시 답변

Q1. 비선점형 스케줄링의 장점과 단점은?
A. 장점은 구현이 단순하고, 프로세스 전환 오버헤드가 낮습니다. 단점은 긴 작업이 짧은 작업을 막고, 응답성이 떨어질 수 있다는 점입니다.

Q2. SJF는 평균 대기 시간이 최소인 이유는 무엇인가요?
A. 짧은 작업부터 처리하므로 후속 프로세스의 대기 시간이 최소화되어 전체 평균 대기 시간이 작아집니다.

Q3. 우선순위 기반 스케줄링에서 기아 상태를 방지하려면?
A. Aging 기법을 도입해 오래 대기한 프로세스의 우선순위를 점진적으로 높이는 방식이 효과적입니다.

---

정리

• 비선점형 스케줄링은 프로세스가 CPU를 점유하면 스스로 종료할 때까지 CPU를 계속 사용합니다.
• FCFS는 단순하지만 비효율적일 수 있고, SJF는 효율적이지만 실행 시간 예측이 필요합니다.
• 우선순위 스케줄링은 유연하지만 기아 문제에 주의해야 합니다.
• 비선점형 방식은 선점형보다 컨텍스트 스위칭 오버헤드가 적고, 단순한 시스템이나 실시간성 요구가 낮은 환경에서 사용됩니다.