[운영체제] 선점 CPU 스케줄링 (Preemptive CPU Scheduling)

CPU 스케줄링 기법으로 크게 아래와 같이 나눌 수 있다.

• 비선점 CPU 스케줄링 (Nonpreemptive CPU Scheduling) 
• 선점 CPU 스케줄링 (Preemptive CPU Scheduling) 

이번에는 선점 CPU 스케줄링 (Preemptive CPU Scheduling)에 대해 알아보도록 하자.

비선점 CPU 스케줄링 기법에 대한 설명은 아래의 글을 참고해주세요!

[운영체제] 비선점 CPU 스케줄링 (Nonpreemptive CPU Scheduling)

---

선점 CPU 스케줄링 (Preemptive CPU Scheduling)이란?

'선점'이란 남보다 앞서서 차지하는 것으로 선점 CPU 스케줄링은 말 그대로, CPU를 선점한다는 뜻이다. 이는 Process Scheduler가 특정 프로세스를 CPU에서 실행하도록 하면, 해당 프로세스가 끝나지 않아도 중간에 다른 프로세스가 끼어들 수 있다. 이러한 특징으로 선점 CPU 스케줄링은 Interrupt를 허용한다고 한다.

 

쉽게 예를 들어 보면, 우리의 사무실에 프린터기가 딱 하나 있다고 가정해보자.

모든 직원이 이 프린터기를 공유하고 있으며, 한 직원이 프린터기를 사용하는 중임에도 다른 직원이 자신의 작업을 먼저 사용할 수 있도록 허용해주는 상황으로 비유할 수 있다. 현재 진행 중인 나의 작업보다 다른 직원의 작업이 긴급한 상황이라면 자신의 출력 작업을 멈추고 새로운 출력 작업을 시작한다는 뜻이다.

 

어떤게 선점 CPU 스케줄링인데?

선점 CPU 스케줄링에서 어떤 프로세스가 선점하느냐에 따라 SRT, RR, MLQ, MFQ 스케줄링 기법이 있다. 

하나씩 천천히 여러 스케줄링 기법에 대해 알아보자.

 

1. SRT (Shortest Reamaining Time)

SRT는 프로세스 중 CPU 요구 시간이 가장 적게 남은 프로세스가 먼저 실행된다. 실행 중인 프로세스가 끝나거나 새로운 프로세스가 들어올 때마다 남은 CPU 요구 시간을 계산한다. 이때, CPU 요구 시간이 가장 적게 남는 프로세스가 선점하여 Interrupt를 발생하는 것이다. CPU 요구 시간이 짧은 것부터 실행하다보니 대기 시간을 최소화할 수 있으나, 반복적으로 모든 프로세스의 CPU 요구 시간을 확인해야 하며 문맥 교환이 자주 일어나 프로세스 실행 상태 복사 및 복구 등의 오버헤드가 발생할 수 있다. 이를 조금이나마 해결하기 위해 임계 시간 값을 설정하여 현재 실행 중인 프로세스의 CPU 요구 시간이 임계 시간 값보다 작을 때는 새로운 프로세스에 대해 스케줄링을 하지 않고 해당 프로세스를 종료할 수 있도록 한다.

2. RR (Round Robin)

RR는 프로세스가 큐에 입력된 순서대로 정해진 Time Slice만큼 실행된다. 여기서, Time Slice란 프로세스가 CPU를 할당 받는 시간으로 시스템 상에서 정해져 있다. Time Slice 내에서 프로세스의 실행이 끝나지 않는 경우, 해당 프로세스는 다시 큐로 들어가 자신의 차례가 올때까지 대기한다. Time Slice가 너무 큰 경우에는 비선점 프로세스의 FCFS 방식과 유사해지며 작은 경우에는 문맥 교환 비용이 증가하여 오버헤드가 발생하므로 적절한 Time Slice 설정이 중요하다.

 

3. MLQ (Multi Level Queue) / MFQ (Multi level Feedback Queue)

MLQ와 MFQ는 모두 우선 순위가 다른 여러 개의 큐를 사용한다는 점에서 동일하다.

 

먼저, MLQ는 우선 순위가 서로 다른 여러 개의 큐를 사용하며 우선순위가 높은 순서대로, 큐에 입력된 순으로 프로세스가 실행된다. 프로세스가 도착할 때마다 우선 순위를 판단하여 올바른 큐에 넣는 과정을 반복한다. 주로 CPU 점유 시간이 큰 프로세스는 우선 순위 낮게, I/O 위주의 프로세스는 우선 순위를 높게 설정한다. MLQ는 우선 순위를 설정하기에 시스템 내의 유연성이 크다는 장점이 있으나, 우선 순위가 낮은 큐에 있는 프로세스에 대해 기아 현상이 발생한다.

 

이러한 현상을 줄이기 위해 MFQ가 사용되며 우선 순위가 다른 여러 개의 큐를 사용하지만, 도중에 우선 순위가 변경 가능하며 우선 순위 큐마다 정해진 Time Slice가 다르다는 점에서 차별적이다. 이에 우선 순위가 낮은 큐에 있으면서 대기 시간이 길어진 프로세스의 우선 순위를 높은 큐로 옮기면서 기아 현상의 발생을 줄인다. 또한, 우선 순위가 높은 큐에 비해 낮은 큐는 CPU가 할당될 확률이 적으므로 낮은 큐에 대해서 더 긴 Time Slice를 설정하여 빈도 수는 낮더라도 할당 되었을 때 오랜 시간 CPU 할당이 가능하도록 한다.