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

운영체제는 컴퓨터 시스템의 자원을 관리하여 Throughput을 증진시키는 것이 목적이다.

 

Throughput이란 '정해진 시간 동안 처리할 수 있는 작업의 정도'를 의미하며,

즉, 운영체제는 컴퓨터가 효율적으로 일할 수 있게끔 관리해주는 감독이라고 생각하면 편하다.

 

컴퓨터 시스템의 대표적인 자원으로 CPU가 있으며, CPU는 매 시점마다 단 하나의 프로세스만을 실행 가능하다.

그러한 이유로 CPU로 어떤 프로세스를 실행할지 선정하는 스케줄링 기법이 매우 중요하다.

 

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

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

먼저, 비선점 CPU 스케줄링 (Nonpreemptive CPU Scheduling)부터 알아보도록 하자.

---

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

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

 

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

모든 직원이 이 프린터기를 공유하고 있으며, 한 직원이 프린터기를 사용하면 다른 직원이 사용할 수 없는 상황으로 비유할 수 있다.

아무리 다른 직원이 긴급한 상황이더라도 기존의 출력 작업이 끝날 때까지 기다려야 새로운 출력 작업을 시작할 수 있다.

 

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

비선점 CPU 스케줄링에서 어떤 프로세스를 먼저 선택하느냐에 따라 FCFS, SJF, HRRN, Priorty, Deadline 스케줄링 기법이 있다. 

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

 

1. FCFS (First Come First Service)

FCFS는 프로세스가 대기 큐에 들어온 순서대로 프로세스가 실행된다. 큐의 FIFO (First In, First Out) 특징에 따라 먼저 들어온 것을 먼저 처리해주는 방식이다. 이러한 스케줄링 기법은 단순하면서도 실행 시간 예측이 용이하다는 점에서 이롭지만, 실행 시간이 짧은 프로세스에 대해 기아 현상이 발생한다. 이는 큐에 들어온 순서에 따라 우선 순위가 결정되므로 실행 시간이 긴 프로세스가 먼저 있을 경우, CPU를 조금만 사용하면 되는데도 너무 오래 기다려야 한다는 문제점을 가진다.

 

2. SJF (Shortest Job First)

SJF는 프로세스의 CPU 요구 시간이 짧은 순으로 프로세스가 실행된다. CPU 버스트가 작은 것부터 처리하여 CPU 요구 시간이 짧은 프로세스가 FCFS 스케줄링 기법에서 오래 기다려야한다는 점을 해결할 수 있다. CPU 사용이 빨리 끝나는 것부터 빠르게 끝낸다는 점에서 효율적이다. 그러나 SJF에서는 CPU 요구 시간이 긴 프로세스에 대해 기아 현상이 발생한다. 이는 CPU 요구 시간이 긴 프로세스가 짧은 프로세스에게 자꾸 밀리면서 실행되지 못하는 상태로 남는다는 한계가 있다.

 

3. HRRN (Highest Response Rate Next)

HRNN는 응답 비율인 Response Rate이 높은 순으로 프로세스가 실행된다. 응답 비율은 다음과 같은 수식으로 도출할 수 있다.

 

응답 비율 (Response Rate) = (대기 시간 + CPU 요구 시간) / (CPU 요구 시간)

 

수식에서 알 수 있다시피, 큐에서 대기한 시간과 CPU 요구 시간을 응답 비율을 통해 모두 고려한다. 

• 대기 시간이 동일한 경우) CPU 요구 시간이 짧은 순서대로 처리
• CPU 요구 시간이 동일한 경우) 대기 시간이 긴 순서대로 처리

이를 통해서, 앞서 SJF에서 요구 시간이 긴 프로세스로 인해 큐에 오래 머문 짧은 프로세스가 기아 현상이 되지 않도록 한다. 

 

4. Priority 

Priority 스케줄링 기법은 각 프로세스마다 정해진 우선순위에 따라 프로세스가 실행된다. 우선순위는 시스템 설계자나 사용자, 운영체제에서 우선순위를 정하며 내부적, 외부적 우선순위로 나뉜다.

• 내부적 우선 순위 : 시스템 내부 요인 (주기억 장치 메모리 사용량 ↓, CPU 버스트 ↓, I/O 버스트 ↑, 파일의 수 ↑ = 우선순위 ↑)
• 외부적 우선 순위 : 시스템 외부 요인 (업무 별 중요도 등)

이를 통해 시스템을 유연하게 관리할 수 있으며, 마찬가지로 우선 순위가 낮은 프로세스에 대해 기아 현상이 나타날 수 있기에 Dynamic Priority 기법으로 대기 시간에 따라 우선 순위를 올려주며 관리하기도 한다.

 

5. Deadline

Deadline 스케줄링 기법은 각 프로세스마다 데드라인에 맞추어 프로세스가 실행된다. 이는 실시간 처리 시스템에서 필수적인 스케줄링으로 데드라인의 유형이 다음과 같이 2가지로 나눌 수 있다.

• Soft 데드라인 : 데드라인 내에 프로세스를 최선을 다해 지키기 위해 우선 순위를 높이며 제약이 약하다.
• Hard 데드라인 : 데드라인 내에 프로세스를 처리하기 위해 CPU를 독점하며 엄격하다.