CPU 스케줄링 알고리즘
CPU 스케줄링 알고리즘
CPU 스케줄링은 여러 프로세스가 CPU를 사용하려고 할 때, 어떤 프로세스에게 언제, 어떻게 CPU를 할당할지 결정하는 운영체제의 핵심 정책입니다. 스케줄링의 목표는 CPU 이용률과 처리량을 높이고, 총처리 시간, 대기 시간, 응답 시간을 최소화하여 시스템의 전반적인 성능과 공정성을 보장하는 것입니다.
- 선점형(Preemptive) vs 비선점형(Non-preemptive)
> * 비선점형 : 한 프로세스가 CPU를 할당받으면, 그 작업이 끝날 때까지 다른 프로세스가 CPU를 빼앗을 수 없습니다. > * 선점형 : 한 프로세스가 CPU를 사용하고 있더라도, 우선순위가 더 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있습니다.
⚙️ 주요 CPU 스케줄링 알고리즘
- FCFS (First-Come, First-Served)
> * '방식': 준비 큐에 먼저 도착한 프로세스부터 순서대로 CPU를 할당합니다. (비선점형) > * '단점': 실행 시간이 긴 프로세스가 먼저 도착하면, 뒤따르는 짧은 프로세스들이 오래 기다려야 하는 '호위 효과(Convoy Effect)'가 발생하여 평균 대기 시간이 길어집니다.
- SJF (Shortest Job First)
> * '방식': 실행 시간이 가장 짧을 것으로 예상되는 프로세스에게 먼저 CPU를 할당합니다. (비선점형, 선점형(SRTF) 모두 가능) > * '장점': 평균 대기 시간을 최소화하는 최적의 알고리즘입니다. > * '단점': 실행 시간이 긴 프로세스는 계속해서 새로운 짧은 프로세스들에게 밀려 무한정 기다릴 수 있는 '기아 현상(Starvation)'이 발생할 수 있습니다. 또한, 실제 실행 시간을 미리 정확히 예측하기 어렵습니다.
- 라운드 로빈 (Round Robin, RR)
> * '방식': 각 프로세스에 동일한 크기의 '시간 할당량(Time Quantum)'을 부여하고, 할당된 시간 안에 작업을 마치지 못하면 준비 큐의 맨 뒤로 가서 다음 차례를 기다립니다. (선점형) > * '장점': 모든 프로세스가 공평하게 CPU 시간을 보장받아 응답 시간이 빠르므로, 대화형 시스템에 적합합니다. > * '단점': 시간 할당량이 너무 크면 FCFS처럼 동작하고, 너무 작으면 잦은 컨텍스트 스위칭으로 오버헤드가 커집니다.
- 우선순위 스케줄링 (Priority Scheduling)
> * '방식': 각 프로세스에 부여된 우선순위에 따라 CPU를 할당합니다. (비선점형, 선점형 모두 가능) > * '단점': '기아 현상'이 발생할 수 있습니다. 이를 해결하기 위해 '노화(Aging)' 기법(오래 기다린 프로세스의 우선순위를 점차 높여줌)을 함께 사용합니다.
💡 개발자 핵심 Point
- 현대 운영체제는 단일 알고리즘만 사용하기보다, 여러 스케줄링 알고리즘을 결합한 다단계 큐 스케줄링(Multi-level Queue Scheduling)이나 다단계 피드백 큐 스케줄링(Multi-level Feedback Queue Scheduling)을 사용합니다.
- 다단계 피드백 큐는 프로세스를 여러 큐에 나누어 배치하고, 각 큐마다 다른 스케줄링 알고리즘(e.g., 상위 큐는 RR, 하위 큐는 FCFS)을 적용합니다. 또한, 프로세스가 큐 사이를 이동할 수 있어, CPU 사용 패턴에 따라 동적으로 우선순위를 조정하고 기아 현상을 해결할 수 있습니다.
- CPU 스케줄링은 운영체제의 핵심 기능으로, 시스템의 전반적인 성능과 사용자 경험에 직접적인 영향을 미칩니다.
