3-4. CPU 스케줄링 알고리즘 - 비선점형 방식, 선점형 방식

0. CPU 스케줄링 알고리즘

CPU 스케줄링은 운영체제가 CPU 자원을 프로세스들에게 공정하고 효율적으로 할당하기 위해 사용하는 메커니즘이다. CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다. 높은 CPU 이용률과 시간 대비 많은 일, 준비 큐에 할당되는 적은 프로세스, 짧은 응답시간을 목표로 한다.

 

 

 

1. 비선점형 방식

비선점형 방식은 한 프로세스가 이미 CPU가 할당받아 사용 중이라면, 스스로 CPU 사용을 중단하는 방식이다. 즉, 운영체제가 CPU를 강제로 중지하지 않는 방식이다. 응답 시간이 느려질 수 있지만, 컨텍스트 스위칭 횟수가 적어 오버헤드가 적은 장점이 있다.

 

1) FCFS

가장 먼저 요청한 프로세스를 가장 먼저 CPU에 할당하는 알고리즘이다. 가장 단순하고 공평하지만, 긴 작업이 먼저 들어오면 뒤에 들어오는 짧은 작업들이 오래 기다리는 호그 현상이 발생할 수 있다.

 

2) SJF

실행 시간이 가장 짧은 프로세스를 CPU에 먼저 할당하는 알고리즘이다. 평균 대기 시간과 평균 반환 시간이 가장 짧은 최적의 알고리즘이지만, 프로세스 실행 시간을 미리 알 수 없어 예측에 의존해야 한다.

 

3) 우선순위

프로세스별로 우선순위를 부여하여, 우선순위가 높은 프로세스를 CPU에 먼저 할당하는 알고리즘이다. 우선순위가 낮은 프로세스는 영원히 실행되지 못하는 기아 현상이 발생할 수 있다.

 

 

 

2. 선점형 방식

선점형 방식은 한 프로세스가 CPU를 사용 중이더라도, 운영체제가 CPU를 강제로 회수하여 다른 프로세스에게 할당할 수 있는 방식이다. 응답성이 빠르고 공정성을 확보할 수 있지만, 컨텍스트 스위칭 횟수가 많아 오버헤드가 크다.

 

1) 라운드 로빈

가장 대표적인 시분할 시스템 알고리즘으로, 각 프로세스에게 동일한 시간 할당량을 부여하고, 시간이 만료되면 CPU를 빼앗아 준비 큐의 맨 뒤로 보내는 알고리즘이다. 할당 시간이 너무 크면 FCFS가 되고, 너무 작으면 컨텍스트 스위칭 횟수가 늘어나 오버헤드가 일어난다.

 

2) SRF

남은 실행 시간이 가장 짧은 프로세스에게 CPU를 할당하며, 새로운 프로세스 도착 시 현재 실행 중인 프로세스와 남은 시간을 비교하여 CPU를 선점하는 알고리즘이다. SJF보다 평균 대기 시간이 짧다.

 

3) 다단계 큐

프로세스들을 특성에 따라 여러 개의 큐로 나누고, 각 큐는 라운드 로빈이나 FCFS 등과 같은 다른 스케줄링 알고리즘을 사용하는 알고리즘이다. 큐 간에 우선순위를 부여하며, 큐 간의 프로세스 이동이 불가하여 스케줄링 부담이 적지만 유연성이 떨어진다.