[OS] CPU 스케줄링 기법: FCFS, SJF, SRT, 라운드 로빈, Multi Level (Feedback) Queue

 CPU 스케줄링 기법에는 선점형과 비선점형이 있습니다. 어떠한 특성인지 살펴보고, 특성별 스케줄링 기법에 대해서도 알아보겠습니다.

 

[ Contents ]

 

 

1. 스케줄러 구분

1) 선점형 (Preemptive)

다른 프로세스가 점유 중인 CPU를 사용가능

 

 빠른 응답이나 모바일, 대화식 시분할 시스템에 적합한 방식입니다.

 하지만 CPU를 교대로 사용하는 과정에서 오버헤드(Overhead)가 발생하는 단점이 있습니다. 이를 Context Switching이라고 합니다.

 작업을 번갈아가며 하려면, 이전 작업의 맥락을 파악하는 시간이 필요하겠죠. CPU도 작업을 교체할 때 현재 진행하고 있는 작업의 상태를 저장하고, 다음 진행할 작업의 상태를 읽고 준비하는 시간이 소요됩니다.

 

 

2) 비선점형 (Non-preemptive)

다른 프로세스의 CPU 할당이 끝날 때까지 대기

 

 한번에 다 끝내는 '배치 프로세스'에서 주로 사용합니다. 순차적으로 작업을 수행하므로 응답 시간을 예상하기도 용이합니다.

 다만, 짧은 작업이나 중요한 작업이 장시간 대기될 수 있는 단점이 있습니다.

 

 

 

2. CPU 스케줄링 종류

1. FCFS (First Come First Service)

대기 큐에 도착한 순서대로 CPU가 처리

 

 일명 '선착순' 처리방식입니다.

 일상에서는 공정한 방식으로 여겨져 많이 사용하지만, CPU효율이 중요한 스케줄링에서는 부적합할 수 있습니다. 먼저 온 긴 작업을 수행하느라 짧은 작업들이 밀릴 수 있으며, 중요한 작업을 못할 수도 있기 때문입니다. (비선점형 스케줄링 기법)

 

 

2. SJF (Shortest Job First)

작업시간이 짧은 순서대로 CPU가 처리

 

 수행시간이 짧은 작업부터 해치우는 스케줄링 방식입니다. (비선점형 스케줄링 기법)

 FCFS보다 평균 대기시간은 짧지만, 수행시간이 긴 작업은 계속해서 밀리는 단점이 있습니다.

 

 

3. SRT (Shortest Remaining Time)

작업시간이 짧은 순서대로 CPU가 처리하되, 더 짧은 작업이 오면 진행중이던 프로세싱도 멈추고 처리

 

 SJF와 비슷하지만, SRT는 선점형 스케줄링 기법입니다. 새로운 프로세스가 진행중이던 프로세스 작업시간보다 짧으면 멈추고 더 짧은 작업부터 수행합니다.

 이러한 작업 방식은 실시간 시스템에 적합합니다.

 

 

4. 라운드 로빈 (Round Robin)

대기 큐의 순서대로 처리하되, 정해진 시간만큼만 작업을 처리하고 다음 작업으로 넘김

 

 마치 CPU Clock처럼 정해진 시간만큼만 골고루 작업을 수행하는 방식입니다. 진행중인 프로세스를 다 처리하지 못하더라도, 정해진 시간이 지나면 다음 작업으로 넘어갑니다. (선점형 스케줄링 기법)

 돌아가며 작업을 수행하기 때문에 짧은 작업이 적체되지 않을 뿐더러, 효율도 좋아서 많이 사용하는 방식입니다. 이론적으로는 짧은 작업부터 처리하는 게 최적이겠지만, 실제로는 작업 예상시간을 계산해야하는 오버헤드가 있습니다.

 

 

5. Multi Level Queue

작업 그룹별로 별개의 큐를 운용하는 스케줄링 기법

 

 작업별로 우선순위를 부여하여, 따로 대기 큐를 운용하는 방식입니다.

 각 작업별 큐는 개별 스케줄링 알고리즘에 따라 CPU를 할당받습니다.

 

 

6. Multi Level Feedback Queue

새로운 프로세스에 높은 우선권을 주되, 점차 낮은 우선순위로 밀려나 라운드 로빈

 

 뉴비에게 우선권을 주는 라운드 로빈 방식입니다.

 레벨(우선순위) 별로 여러 개의 큐가 있으며, 새로운 프로세스가 들어오면 높은 우선순위 큐에 배정하여 즉시 수행합니다. 이후 점차 낮은 우선순위 큐로 내려가며 작업이 완료될 때까지 순환합니다.