[운영체제] CPU 스케줄링 알고리즘

CPU 스케줄러는 CPU 스케줄링 알고리즘을 기반으로, 프로세스를 스레드 단위로 CPU에 할당하는 역할을 합니다.

프로그램이 실행될 때 어떤 프로그램이 CPU를 사용할지 결정하는 것이 바로 CPU 스케줄링 알고리즘입니다. 이러한 알고리즘은 CPU 이용률을 높이고, 주어진 시간 동안 많은 작업을 처리하며 준비 큐(ready queue)에 있는 프로세스를 최소화하고, 응답 시간을 짧게 설정하는 것을 목표로 합니다.

CPU 스케줄링 알고리즘은 크게 비선점형(non-preemptive)과 선점형(preemptive) 방식으로 나눌 수 있습니다.

1. 비선점형 방식 (Non-preemptive)

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기할 때까지 실행하는 방식으로, 강제로 프로세스를 중단하지 않습니다. 이 방식은 컨텍스트 스위칭(Context Switching)으로 인한 부하가 적다는 장점이 있습니다.

1-1. 비선점형 방식의 종류

1) FCFS (First Come, First Served)

가장 먼저 도착한 프로세스를 먼저 처리하는 알고리즘입니다. 이 방식은 간단하지만 긴 실행 시간을 가진 프로세스 때문에 준비 큐에서 오래 기다리는 현상(convoy effect)이 발생할 수 있다는 단점이 있습니다.

2) SJF (Shortest Job First)

실행 시간이 가장 짧은 프로세스를 우선 실행하는 알고리즘입니다. 이 방식은 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 발생할 수 있으며 평균 대기 시간이 가장 짧은 것이 특징입니다. 하지만 실제로는 실행 시간을 미리 알 수 없기 때문에, 과거의 실행 시간을 토대로 추측해서 사용합니다.

3) 우선순위 (Priority)

기존 SJF를 보완한 알고리즘으로, 오래된 작업일수록 우선순위를 높이는 방식으로 우선순위를 보완한 알고리즘입니다.

2. 선점형 방식 (Preemptive)

선점형 방식은 현대 운영체제에서 많이 사용되며 현재 실행 중인 프로세스를 강제로 중단시키고 다른 프로세스에 CPU 소유권을 할당하는 방식입니다.

2-1. 선점형 방식의 종류

1) 라운드 로빈 (RR, Round Robin)

현대 운영체제에서 사용되는 선점형 스케줄링 알고리즘으로, 각 프로세스에 동일한 할당 시간을 주고, 그 시간 내에 완료되지 않으면 다시 준비 큐(Ready Queue)의 뒤로 보내는 방식입니다.

할당 시간이 너무 크면 FCFS와 비슷해지고, 너무 짧으면 컨텍스트 스위칭이 잦아져 오버헤드가 커집니다. 일반적으로 전체 작업 시간은 길어지지만, 평균 응답 시간은 짧아지는 특징이 있습니다.

라운드 로빈 알고리즘은 로드 밸런서의 트래픽 분산 알고리즘으로도 사용됩니다.

2) SRF (Shortest Remaining Time First)

남은 실행 시간이 가장 짧은 프로세스를 우선 실행하는 방식입니다. 작업 도중 더 짧은 작업이 들어오면 현재 수행 중이던 프로세스를 중지하고 새로운 프로세스를 실행합니다.

3) 다단계 큐 (Multilevel Queue)

프로세스를 우선순위에 따라 여러 개의 큐로 분리하고, 각 큐에 다른 스케줄링 방식을 적용하는 알고리즘입니다. 각 큐는 서로 다른 프로세스 그룹을 처리하며, 프로세스 그룹에 따라 우선순위와 처리 방법이 달라집니다. 이를 통해 우선순위가 높은 작업을 먼저 처리할 수 있습니다.