[OS] CPU Scheduling

Scheduling은 Process가 작업을 효율적으로 수행할 수 있도록, OS가 CPU 자원을 적절하게 분배하는 작업을 의미한다.

 

CPU Scheduling은 크게 Preemptive Scheduling 과 Non-preemptive Scheduling 으로 나뉜다.

---

<Preemptive Scheduling>

선점 스케줄링이라는 의미인 Preemptive Scheduling 은 단어의 의미 그대로 CPU 를 빼앗아 올 수 있는 스케줄링 방법이다.

 

A Process 가 이미 CPU 를 점유하고 있더라도, 우선 순위가 높은 B Process 가 나타나면, CPU 를 빼앗아 올 수 있다.

따라서, 우선 순위가 높은 Process 를 빠르게 처리해야하는 경우에 유리한 방식이다.

 

그러나 CPU 를 빼앗아오는 Preemptive 현상이 발생하면 기존에 처리하던 작업을 모두 멈추고, 새로운 Process 를 처리하는 작업을 수행해야 하므로, 오버헤드가 발생하며, 처리 시간을 예측하기 힘들어진다.

 

Preemptive Scheduling에 속하는 방식은 다음과 같다.

• SRT (Shortest Remaining Time) Scheduling - 작업 시간이 짧은 순서대로 Process 를 수행하는 방식이다. 남아 있는 처리 시간이 더 짧은 Process가 Ready Queue에 들어 오면, 해당 Process가 CPU를 선점하게 된다.
• RR (Round-Robin) Scheduling - 각 Process는 같은 크기의 CPU Time을 할당 받으며, FIFO 식으로 수행 된다. 만약 CPU Time이 너무 많이 할당되면, FCFS (FIFO) Scheduling 방식과 다를 바가 없으며, CPU Time을 너무 짧게 할당하면, 빈번한 Context Switching이 발생하게 되어, 오버헤드가 커진다는 문제가 있다. 
• Multi-level Queue Scheduling - 복수 개의 Ready Queue를 이용하는 방식이다. 각 Ready Queue는 자신만의 스케줄링 알고리즘을 수행하며, Queue와 Queue 사이에서도 우선 순위가 부여된다.
• Multi-level Feedback Queue Scheduling - Multi-level Queue 방식과 비슷하지만, Process가 Queue와 Queue 사이를 이동할 수 있다는 점이 특징이다.

 

<Non-preemptive Scheduling>

비선점 스케줄링이라는 의미인 Non-preemptive Scheduling은 Preemptive Scheduling과 정반대의 스케줄링 방법이라고 생각하면 쉽다.

 

A Process가 이미 CPU를 점유하고 있으면, A Process가 작업이 완료되는 등의 이유로, 스스로 CPU를 놓아주지 않는 이상, CPU를 빼앗아 올 수 없다.

 

Non-preemptive Scheduling에 속하는 방식은 다음과 같다.

• Priority Scheduling - Process에 우선 순위를 부여하여, 우선 순위가 높은 순서대로 처리한다. 우선 순위를 부여할 때는 동적으로도 부여할 수 있는데, 이 경우 구현이 복잡해지고 오버헤드가 많아지나, 시스템의 응답 속도를 높이는 장점이 있다.
• SJF (Shortest Job First) Scheduling - Ready Queue 내에 있는 Process 중에서, 처리 시간이 더 짧은 것을 먼저 수행한다. 이를 통해서 평균 대기 시간을 감소시킨다는 장점이 있다.
• HRN (Highest Response Ratio Next) Scheduling - 처리 시간이 긴 작업과 짧은 작업 사이의 차별이 발생하는 것을 보완하는 방식이다. 처리 시간의 길이와 대기 시간의 길이를 모두 고려해서 우선 순위를 할당한다.
• FCFS (First Comes First Served) Scheduling - FIFO (First In First Out) 라고도 불리며, Process가 Ready Queue에 도착한 순서대로 CPU Time을 할당받게 된다. 따라서 작업의 완료 시간을 예측하기가 매우 쉽다. 그러나 덜 중요한 작업이 먼저 오게 되면, 더 중요한 작업을 오래 기다리게 할 수도 있다는 단점이 있다.
• Deadline Scheduling - 말 그대로 작업이 완료되어야 하는 시간을 지정하여, 해당 시간 내에 작업이 끝나도록 계획하는 방식이다.