CPU 스케줄링 알고리즘

CPU 스케줄러는 운영 체제의 중요한 구성 요소로, 프로세스가 CPU를 효율적으로 사용할 수 있도록 관리한다. 이 글에서는 CPU 스케줄링 알고리즘의 두 가지 주요 방식인 비선점형과 선점형에 대해 알아보겠다.

목차

• 비선점형 방식
• 선점형 방식

비선점형 방식

비선점형(Non-Preemptive) 방식은 프로세스가 CPU를 점유한 상태에서 다른 프로세스가 CPU를 강제로 빼앗을 수 없는 방식이다. 이 방식에서는 프로세스가 CPU를 사용하고 있는 동안에는 다른 프로세스가 대기해야 한다. 비선점형 방식의 예로는 다음과 같은 알고리즘이 있다:

FCFS(First-Come, First-Served)

FCFS는 가장 먼저 도착한 프로세스가 가장 먼저 CPU를 할당받는 방식이다. 이 방식은 구현이 간단하지만, 짧은 프로세스가 긴 프로세스에 의해 지연되는 문제를 가지고 있다.

SJF(Shortest Job First)

SJF는 가장 짧은 실행 시간을 가진 프로세스가 CPU를 먼저 할당받는 방식이다. 이 방식은 평균 대기 시간을 최소화할 수 있지만, 긴 프로세스가 계속해서 지연될 수 있는 문제(Starvation)를 가지고 있다. 하지만, 실제로는 프로세스의 실행 시간을 정확히 알 수 없기 때문에 과거의 실행 시간을 기반으로 예측하는 방법을 사용한다.

우선 순위(Priority Scheduling)

기존 SJF 스케줄링의 경우 실행 시간이 긴 프로세스의 경우 오랜 시간 동안 CPU를 할당받지 못하는 문제(Starvation)가 발생할 수 있다. 우선순위 알고리즘은 이를 해결하기 위해 오래 대기한 프로세스에 우선순위를 높이는 방법(Aging)을 사용한 알고리즘이다. 우선순위 알고리즘은 SJF 뿐 아니라 FCFS와 Round Robin과 같은 다른 선점형, 비선점형 알고리즘 모두에서 사용될 수 있다.

선점형 방식

선점형(Preemptive) 방식은 현대 운영 체제에서 널리 사용되는 방식으로, 프로세스가 CPU를 점유하고 있는 동안에도 다른 프로세스가 CPU를 강제로 빼앗을 수 있다. 이 방식은 프로세스의 우선순위나 시간 할당량에 따라 CPU를 할당한다.

Round Robin

Round Robin은 각 프로세스에 동일한 시간 할당량(Time Quantum)을 주고, 이 시간 동안 프로세스가 CPU를 사용한 후 다음 프로세스로 전환하는 방식이다. 부여 받은 시간 할당량이 끝나면 프로세스는 대기열의 맨 뒤로 이동하고, 다음 프로세스가 CPU를 사용한다. 이 방식은 공정성을 보장하지만, 시간 할당량이 너무 길면 FCFS와 유사한 문제를 발생시킬 수 있고, 너무 짧으면 컨텍스트 스위칭이 빈번하게 발생하여 오버헤드가 증가할 수 있다. 일반적으로 전체 작업 시간은 길어지지만, 평균 응답 시간은 짧아지는 특징이 있어 로드밸런서에서 트래픽 분산 알고리즘에도 활용된다.

SRF(Shortest Remaining Time First)

SRF는 SJF의 선점형 버전으로, 현재 실행 중인 프로세스보다 짧은 실행 시간을 가진 프로세스가 도착하면 CPU를 강제로 빼앗는 방식이다. 이 방식은 평균 대기 시간을 최소화할 수 있지만, 긴 프로세스가 계속해서 지연될 수 있는 문제(Starvation)를 가지고 있다. SRF는 SJF와 마찬가지로 프로세스의 실행 시간을 정확히 알 수 없기 때문에 과거의 실행 시간을 기반으로 예측하는 방법을 사용한다.

다단계 큐(Multi-Level Queue)

다단계 큐는 프로세스를 여러 개의 큐로 나누고, 각 큐에 다른 스케줄링 알고리즘을 적용하는 방식이다. 예를 들어, 상위 큐는 FCFS를 사용하고, 하위 큐는 Round Robin을 사용하는 식이다. 이 방식은 프로세스의 특성에 따라 적절한 스케줄링 알고리즘을 적용할 수 있어 유연성을 제공한다. 다단계 큐는 일반적으로 우선순위 기반으로 동작하며, 각 큐의 프로세스는 해당 큐의 스케줄링 알고리즘에 따라 CPU를 할당받는다.