3.4 CPU 스케줄링 알고리즘

*내용이 짧아, 상세 구분 없이 한번에 정리

CPU 스케줄링 알고리즘은 여러 프로세스가 CPU를 공유하는 환경에서 어떤 프로세스를 언제 실행할지 결정하는 알고리즘. 이를 선점형과 비선점형으로 구분할 수 있음.

구분	알고리즘	주요 특징
비선점형	FCFS, SJF, Priority Scheduling, RR	자원 점유 중인 프로세스가 CPU를 선점하지 않음
선점형	SRTF, Preemptive Priority Scheduling, Round Robin, Multilevel Queue	프로세스가 CPU를 강제로 빼앗길 수 있음

• 비선점형 알고리즘은 간단하지만, 긴 프로세스가 다른 프로세스를 지연시키는 문제가 있음.
• 선점형 알고리즘은 프로세스가 CPU를 강제로 빼앗길 수 있어 공정성이 높지만, starvation이나 과도한 context switching 문제가 발생할 수 있음.

---

1. 비선점형 CPU 스케줄링 알고리즘

비선점형 알고리즘에서는 프로세스가 자원을 점유한 상태에서 다른 프로세스가 강제로 CPU를 빼앗을 수 없음. 즉, 프로세스가 완료될 때까지 CPU를 독점적으로 사용.

 

알고리즘	특징	장점	단점
FCFS (First-Come, First-Served)	먼저 도착한 프로세스를 먼저 실행. 큐에서 먼저 도착한 순서대로 실행.	간단하고 직관적.	긴 프로세스가 먼저 실행되면 짧은 프로세스가 대기하게 되어 convoy effect 발생.
SJF (Shortest Job First)	가장 짧은 실행 시간을 가진 프로세스를 먼저 실행.	평균 대기 시간이 최소화됨.	실행 시간 예측이 어려움. 실행 시간을 정확히 알 수 없으면 사용하기 어려움.
Priority Scheduling	프로세스에 우선순위를 부여하고, 높은 우선순위를 가진 프로세스를 먼저 실행.	중요한 작업을 우선 실행 가능.	starvation(기아 현상) 발생 가능. 우선순위가 낮은 프로세스는 영원히 실행되지 않을 수 있음.
RR (Round Robin)	각 프로세스에 고정된 시간 할당량(time quantum)을 주고, 순차적으로 실행.	공정하고, 프로세스가 CPU를 효율적으로 공유.	시간 할당량이 너무 짧거나 길면 성능이 저하될 수 있음.

---

2. 선점형 CPU 스케줄링 알고리즘

선점형 알고리즘에서는 프로세스가 실행 중일 때 다른 프로세스가 CPU를 강제로 빼앗을 수 있음. 프로세스가 자원을 강제로 할당받을 수 있어, 실시간 성능이 중요한 환경에 적합함.

 

알고리즘	특징	장점	단점
SRTF (Shortest Remaining Time First)	현재 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행.	평균 대기 시간이 최소화됨.	프로세스가 계속 선점되어 starvation 발생 가능.
Preemptive Priority Scheduling	프로세스의 우선순위에 따라, 우선순위가 높은 프로세스가 실행되며, CPU를 빼앗을 수 있음.	우선순위 높은 프로세스를 즉시 실행 가능.	starvation 문제 발생 가능.
Round Robin (RR)	고정된 시간 할당량을 주고 순차적으로 실행. 선점형 방식으로, 각 프로세스가 차례대로 실행되며, 시간이 다되면 다른 프로세스에게 CPU를 넘김.	공정한 스케줄링, 모든 프로세스가 동일하게 실행될 기회가 있음.	할당된 시간만큼 처리할 수 없는 작업에 비효율적일 수 있음.
Multilevel Queue Scheduling	여러 개의 큐를 만들어 우선순위에 따라 프로세스를 배정. 높은 우선순위 큐에서 실행되며, 낮은 우선순위 큐는 낮은 우선순위를 가진 프로세스들이 실행됨.	여러 종류의 프로세스를 다룰 수 있음. 높은 우선순위의 프로세스를 신속히 실행.	우선순위 큐마다 자원이 고정되어 있어, 낮은 우선순위 큐는 CPU를 빼앗기 어려울 수 있음.