[OS] CPU Scheduling

Terminology

CPU Scheduling은 운영체제가 시스템의 여러 프로세스들 사이에서 CPU 자원을 효율적으로 분배하기 위해 사용하는 메커니즘이다. 이는 여러 프로세스가 동시에 실행되고자 할 때, 어떤 프로세스가 CPU를 사용할지를 결정하는 과정이다.

 

왜 필요한가? (Policy)

 

실행 중인 프로세스는 CPU burst와 I/O burst를 무한히 반복한다. I/O burst로 이동할 때에는 context switch한 후 이동하는데, I/O burst가 얼마나 길어질지 모르기 때문이다. Context switch가 발생하기 이전에 운영체제는 미리 scheduler를 통해 ready queue에 있는 프로세스 중에서 다음에 실행할 프로세스를 선택한다. 어떤 기준으로 결정된 프로세스를 얼마나 길게 실행시킬 것인지는 multi-programming에서 매우 중요하며, 이는 kernel의 중요한 기능 중 하나로 설정되어 있다.

 

적절한 CPU Scheduling을 사용하면, 하드웨어 자원을 최대한으로 활용할 수 있으며, CPU utilization과 throughput을 극대화할 수 있다. 추가로 적절한 기법을 사용하여 waiting time과 response time을 최소화할 수 있다.

Five State Process Model

 

Mechanism

CPU Scheduling 기법에는 여러가지가 있는데, 앞서 기법들을 크게 나누는 기준에 대해 소개하겠다. CPU를 점유하는 동안 다른 프로세스가 CPU를 강제로 빼앗을 수 있는지 여부에 따라 구분되는데, 빼앗을 수 없으면 Non-Preemptive이고, 빼앗을 수 있다면 preemptive이다.

Non-Preemptive 스케줄링에서는 일단 프로세스가 CPU를 할당받으면, 그 프로세스가 자발적으로 CPU를 반환할 때까지 다른 프로세스가 CPU를 빼앗을 수 없다. 프로세스가 종료되거나 I/O 작업을 위해 대기 상태로 전환될 때만 CPU가 반환된다. 주요 Non-Preemptive 스케줄링 알고리즘으로는 FCFS, SJF가 있다.

Preemptive 스케줄링에서는 운영체제가 현재 실행 중인 프로세스를 강제로 중단시키고, 다른 프로세스에 CPU를 할당할 수 있다. 이는 더 높은 우선순위를 가진 프로세스가 도착하거나, 시간 할당량(time slice)이 끝났을 때 발생할 수 있다. 주요 Preemptive 스케줄링 알고리즘으로는, Round Robin, SRTF가 있다.

 

1. FCFS (First Come First Served)

FCFS는 프로세스가 도착한 순서대로 CPU를 할당하는 비선점형 스케줄링 기법이다. 첫 번째로 도착한 프로세스가 CPU를 먼저 사용하며, 그 프로세스가 완료될 때까지 다른 프로세스들은 대기한다.

• Response Time: 긴 프로세스가 앞에 나오면 길어질 수 있다. 이를 Convoy effect라고 하는데, cpu 이용률과 처리량도 저하되는 현상을 불러온다.
• Starvation: 발생하지 않는다. 모든 프로세스가 결국에는 CPU를 할당받기 때문이다.
• Fairness: 공정하지만, 긴 프로세스가 먼저 오면 다른 프로세스들이 오랫동안 대기하게 되어 비효율적일 수 있다.
• Overhead: 스케줄링 결정이 단순하기에 매우 적다.

 

2. SJF (Shortest Job First)

SJF는 가장 짧은 CPU burst 시간을 가진 프로세스에 CPU를 할당하는 비선점형 스케줄링 기법이다. 이를 통해 평균 대기 시간을 최소화할 수 있다. (convoy effect 최소화)

• Response Time: 짧은 작업의 경우 매우 좋다.
• Starvation: 긴 작업은 계속 대기하게 되어 기아현상이 발생할 수 있다.
• Fairness: 짧은 작업에 유리하여 긴 작업은 불공정할 수 있다.
• Overhead: cpu time을 예측해야 하기에 높을 수도 있다.

 

3. Round Robin

Round Robin은 각 프로세스가 일정한 시간 할당량(time quantum) 동안 CPU를 사용하고, 그 시간이 끝나면 다음 프로세스에 CPU를 넘기는 선점형 스케줄링 기법이다. time slice가 작으면 context switch가 빈번해지고, 크면 FCFS와 유사해진다. (fcfs + preemptive)

• Response Time: 시간 할당량에 따라 다르지만, 짧은 할당량이면 반응 시간이 빠르다.
• Starvation: 모든 프로세스가 일정하게 CPU를 할당받기에 발생하지 않는다.
• Fairness: 매우 공정하다. 모든 프로세스가 균등하게 CPU를 사용한다.
• Overhead: context switch가 자주 발생하여 오버헤드가 크다. 다만, 다른 기법들에 비해 낮다.

 

4. SRTF (Shortest Remaining Time First)

SRTF는 남은 실행 시간이 가장 짧은 프로세스에 CPU를 할당하는 선점형 스케줄링 기법이다. 새로운 프로세스가 도착하면 현재 실행 중인 프로세스의 남은 시간과 비교하여 CPU를 할당한다.

• Response Time: 짧은 작업의 경우 매우 좋다.
• Starvation: 긴 작업은 기아(starvation) 현상이 발생할 수 있다.
• Fairness: 짧은 작업에 유리하여 불공정할 수 있다.
• Overhead: 빈번한 context switch로 인해 오버헤드가 크다.

 

5. Priority Scheduling

각 프로세스에 우선순위를 부여하고, 우선순위가 높은 프로세스에게 CPU를 할당하는 스케줄링 기법이다. 선점형과 비선점형 두 가지 방식이 있다.

• Response Time: 우선순위가 높은 프로세스는 반응 시간이 빠르다.
• Starvation: 우선순위가 낮은 프로세스는 기아(starvation) 현상이 발생할 수 있다.
• Fairness: 우선순위에 따라 공정성이 떨어질 수 있다.
• Overhead: 우선순위를 관리하고 스케줄링하는 오버헤드가 있다.

 

6. Multilevel Queue Scheduling

프로세스를 여러 개의 큐로 나누고, 각 큐에 다른 스케줄링 알고리즘을 적용하는 방식이다. 큐 간의 우선순위가 설정될 수 있다.

• Response Time: 큐의 우선순위와 내부 스케줄링 알고리즘에 따라 다르다.
• Starvation: 낮은 우선순위 큐의 프로세스는 기아(starvation) 현상이 발생할 수 있다.
• Fairness: 큐 간의 우선순위 설정에 따라 공정성이 달라진다.
• Overhead: 큐를 관리하고 스케줄링하는 오버헤드가 크다.

 

7. Multilevel Feedback Queue Scheduling

Multilevel Queue Scheduling의 변형으로, 프로세스가 다양한 큐 사이를 이동할 수 있게 하여 더 유연한 스케줄링을 제공하는 방식이다. 프로세스의 행동에 따라 우선순위를 조정한다.

• Response Time: 동적인 조정을 통해 반응 시간이 최적화될 수 있다.
• Starvation: 기아 현상이 발생할 가능성이 낮다. 우선순위가 동적으로 조정되기 때문이다.
• Fairness: 매우 공정하다. 프로세스의 특성에 따라 유연하게 대응한다.
• Overhead: 큐의 관리와 프로세스 이동에 따른 오버헤드가 크다.