[OS] CPU 스케줄링 알고리즘

운영체제에서 CPU 스케줄러는 여러 프로세스가 동시에 실행되려고 할 때, 어떤 프로세스(혹은 그 안의 스레드)에게 CPU 소유권을 줄지 결정하는 핵심 역할을 합니다.

 

이 결정은 CPU 스케줄링 알고리즘에 의해 이루어지며, 프로그램 실행 시 성능과 반응 속도에 큰 영향을 미칩니다.

---

CPU 스케줄링 알고리즘의 목표

CPU 스케줄링 알고리즘은 다음과 같은 목표를 달성하기 위해 설계됩니다.

1. CPU 이용률 최대화 – 가능한 한 CPU가 쉬지 않고 일하게 함
2. 처리량 향상 – 주어진 시간 내에 가능한 많은 작업을 처리
3. 대기 시간 최소화 – 준비 큐에 있는 프로세스 수를 줄임
4. 응답 시간 최소화 – 사용자 요청에 빠르게 반응

---

비선점형 스케줄링 (Non-Preemptive)

비선점형 방식은 프로세스가 자발적으로 CPU를 반납할 때까지 강제로 중단하지 않습니다.

컨텍스트 스위칭 오버헤드가 적어 안정적이지만, 실시간 처리에는 한계가 있습니다.

 

1. FCFS (First Come, First Served)

• 가장 먼저 도착한 프로세스를 먼저 처리
• 단순하지만, 긴 작업 하나가 준비 큐 전체를 지연시키는 Convoy Effect가 발생할 수 있음

2. SJF (Shortest Job First)

• 예상 실행 시간이 가장 짧은 작업을 먼저 처리
• 평균 대기 시간이 가장 짧은 이상적인 알고리즘
• 단점: 실행 시간을 정확히 알 수 없어 예측에 의존
• 긴 작업이 계속 밀리는 기아 현상(Starvation) 발생 가능

3. 우선순위 스케줄링

• 각 프로세스에 우선순위를 부여하여 높은 우선순위 작업부터 처리
• SJF는 ‘실행 시간’을 우선순위로 본 특수한 경우
• 선점형/비선점형 모두 가능
• 기아 현상을 해결하기 위해 오래된 작업의 우선순위를 점차 높이는 에이징(Aging) 기법 사용

---

선점형 스케줄링 (Preemptive)

선점형 방식은 현재 실행 중인 프로세스를 중단하고, 더 우선순위가 높은 프로세스나 정책상 더 적합한 프로세스를 먼저 실행합니다.

현대의 대부분 OS에서 사용되는 방식입니다.

 

1. 라운드 로빈 (Round Robin)

• 각 프로세스에 동일한 시간 할당량(Time Quantum) 부여
• 주어진 시간 내 종료하지 못하면 준비 큐 끝으로 이동
• 시간 할당량이 너무 크면 FCFS처럼 되고, 너무 짧으면 컨텍스트 스위칭 오버헤드 증가
• 로드 밸런서의 트래픽 분산 방식으로도 응용됨

2. SRTF (Shortest Remaining Time First)

• SJF의 선점형 버전
• 실행 도중 더 짧은 남은 시간을 가진 작업이 도착하면 현재 작업을 중단하고 새로운 작업 수행
• 반응 속도가 뛰어나지만, 예측 오류에 민감하고 기아 현상 발생 가능

3. 다단계 큐 (Multilevel Queue)

• 우선순위별로 여러 개의 준비 큐를 운영
• 각 큐는 다른 스케줄링 알고리즘(예: 높은 우선순위는 라운드 로빈, 낮은 우선순위는 FCFS)을 사용 가능
• 큐 간 이동이 불가능하기 때문에 유연성은 낮지만 구현이 단순하고 성능 예측이 쉬움

---

마무리

CPU 스케줄링은 운영체제 성능에 직접적인 영향을 주는 중요한 요소입니다.

각 스케줄링 알고리즘은 상황과 목적에 따라 적합한 방식이 달라지며, 응답 속도가 중요한 시스템에서는 선점형 방식, 처리 순서가 중요한 시스템에서는 비선점형 방식을 사용하는 경우가 많습니다.

 

여러 알고리즘의 장단점을 이해하면, 시스템 구조나 애플리케이션 특성에 맞는 전략을 세우는 데 큰 도움이 됩니다.