CPU-Scheduling

CPU-Scheduling 이란?

모든 프로세스는 CPU를 필요로 하고 모든 프로세스는 먼저 CPU를 사용하고 싶어 하기에, 여러 프로세스들에게 합리적으로 CPU 자원을 할당하기 위해 운영체제는 어떤 프로세스에 어떤 CPU를 할당할지를 결정한다.

 

이렇게 운영체제가 프로세스들에게 합리적으로 CPU 자원을 배분하는 것을 CPU-Scheduling 이라고 한다. CPU-Scheduling 이 제대로 동작하지 않는다면, 반드시 실행되어야 할 프로세스들이 실행되지 못하거나, 중요하지 않은 프로세스들만 주로 실행되는 등 컴퓨터 성능에 직결되는 문제라고 볼 수 있다.

프로세스 우선순위

각 프로세스마다 우선순위가 다른데, 우선순위가 높은 프로세스일수록 빨리 처리해야 하는 프로세스들을 의미한다. 우선순위가 높은 프로세스에는 대표적으로 입출력 작업이 많은 프로세스가 있다.

 

프로세스의 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 있다. 입출력장치를 사용하는 경우가 많은 프로세스를 입출력 집중 프로세스, CPU를 사용하는 경우가 많은 프로세스를 CPU 집중 프로세스라고 하는데, 입출력 집중 프로세스는 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 된다. 반면에, CPU 집중 프로세스는 대기 상태보다는 실행 상태에 더 많이 머무르게 된다.

 

CPU 집중 프로세스와 입출력 집중 프로세스가 동시에 CPU 자원을 요구했을 때 입출력 집중 프로세스를 최대한 빨리 실행시켜 입출력장치를 꾸준히 작동시키고, 그다음 CPU 집중 프로세스에 CPU를 집중적으로 할당하는 것이 더 효율적이다. 입출력 집중 프로세스는 어차피 입출력장치가 입출력 작업을 완료하기 전까지는 대기 상태가 될 예정이기 때문에 입출력 집중 프로세스를 우선적으로 처리한다면 다른 프로세스가 CPU를 사용할 수 있기 때문이다.

 

이렇듯 운영체제는 프로세스의 중요도에 맞게 프로세스마다 우선순위를 부여하여 PCB에 명시한다.

Scheduling Queue

PCB에 적혀있는 우선순위를 확인하기 위해 모든 프로세스의 PCB를 운영체제가 탐색하는 것은 비효율적이다.

 

이를 위해 운영체제는 프로세스들을 CPU 사용, 메모리 적재, 입출력장치 사용 등의 목적을 통해 구분하여 Scheduling Queue에 삽입한다. 대표적인 Scheduling Queue에는 CPU 사용을 위한 프로세스들을 적재하는 Ready Queue와 입출력장치 사용을 위한 프로세스들을 적재하는 Waiting Queue 가 존재한다.

 

준비 상태에 있는 프로세스들의 PCB는 Ready Queue의 마지막에 삽입되어 CPU를 사용할 차례를 기다린다. 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행한다.

 

즉, 우선순위가 낮은 프로세스들이 먼저 큐에 삽입되었더라도 우선순위가 높은 프로스가 먼저 처리될 수 있다는 것이다.

Preemptive Scheduling (선점형 스케줄링)

선점형 스케줄링이란, 프로세스가 CPU를 비롯한 자원을 사용하고 있더라고 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에게 할당할 수 있는 스케줄링 방식을 의미한다.

 

프로세스마다 정해진 시간만큼 CPU를 사용하고, 정해진 시간을 모두 소비하여 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스로부터 CPU 자원을 빼앗아 다음 프로세스에게 할당하는 방식 또한 선점형 스케줄링의 일종으로 볼 수 있다.

 

선점형 스케줄링은 어느 한 프로세스의 자원 독점을 막고 프로세스들에게 골고루 자원을 배분할 수 있다는 장점이 있지만, 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다.

 

대부분의 운영체제에서는 선점형 스케줄링 방식을 차용하고 있다.

Non-Preemptive Scheduling (비선점형 스케줄링)

비선점형 스케줄링이란, 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식을 의미한다.

 

이는 특정 프로세스가 자원을 독점할 수 있는 스케줄링 방식이며, 만약 비선점형 방식으로 자원을 이용하는 프로세스가 존재한다면 다른 프로세스들은 그 프로세스의 사용이 모두 끝날 때까지 기다려야 한다.

 

비선점형 스케줄링은 선점형 스케줄링에 비해 문맥 교환의 횟수가 적기 때문에 발생할 수 있는 오버헤드가 적지만, 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 상황에서도 무작정 기다려야 하기 때문에 모든 프로세스가 골고루 자원을 사용할 수 없다는 단점이 있다.

Scheduling Algorithm

FCFS Scheduling (선입 선처리 스케줄링)

First Come First Served Scheduling 은 Scheduling Queue 에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다.

 

즉, CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 방식인데, 이는 언뜻 가장 공정해 보이는 방식이지만, 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 점에서 단점이 존재하는 방식이다.

SJF Scheduling (최단 작업 우선 스케줄링)

FCFS 에서 발생할 수 있는 단점을 최소화하기 위해 CPU 사용 시간이 짧은 프로세스를 먼저 실행하는 스케줄링 방식을 Shortest Job First 스케줄링이라고 한다. 기본적으로 비선점형 스케줄링으로 분류되지만, 선점형으로도 구현될 수 있다.

Round Robin Scheduling

Round Robin Scheduling 은 FCFS Scheduling 에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다.

 

타임 슬라이스란, 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다. 즉, Round Robin Scheduling 은 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.

 

큐에 삽입된 프로세스들은 삽입된 순서대로 CPU를 이용하되 정해진 시간만큼만 CPU를 이용하고, 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면, 다시 큐의 맨 뒤로 삽입된다. 이때 문맥 교환이 발생한다.

 

Round Robin Scheduling 에서는 타임 슬라이스의 크기가 매우 중요하다. 타임 슬라이스가 지나치게 크면 FCFS Scheduling 과 다를 바 없어지고, 타임 슬라이스가 지나치게 작으면 문맥 교환에 발생하는 비용이 커 CPU는 프로세스를 처리하는 일보다 프로세스를 전환하는데 더 많은 비용이 소모될 여지가 있기 때문이다.

SRT Scheduling (최소 잔여 시간 우선 스케줄링)

Shortest Remaining Time Scheduling 은 SJF Scheduling과 Round Robin Scheduling 을 합친 스케줄링 방식이다.

 

프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

Priority Scheduling (우선순위 스케줄링)

Priority Scheduling 은 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다.

 

SJF Scheduling, SRT Scheduling 이 넓은 의미에서 Priority Scheduling 의 일종으로 볼 수 있다. Priority Scheduling 은 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있다.

 

이를 기아 현상이라고 한다. 이를 방지하기 위한 대표적인 기법으로 에이징이 존재하는데, 이는 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.

Multilevel Queue Scheduling (다단계 큐 스케줄링)

Multilevel Queue Scheduling 은 Priority Scheduling의 발전된 형태로 우선순위별로 Ready Queue를 여러 개 사용하는 스케줄링 방식이다. 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스들을 처리한다.

 

큐를 여러 개 두면 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다. 또한 큐별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수 있다.

Multilevel Feedback Queue Scheduling (다단계 피드백 큐 스케줄링)

다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링의 발전된 형태로, 다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없다. 그렇기 때문에 우선순위가 낮은 프로세스들이 계속 연기되는 기아 현상이 발생할 수 있다.

 

다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링과 비슷하게 작동하지만, 프로세스들이 큐 사이를 이동할 수 있다는 점에서 차이가 존재한다. 다단계 피드백 큐 스케줄링에서 새로 준비 상태가 된 프로세스가 있다면 우선 우선순위가 가장 높은 우선순위 큐에 삽입되고 타임 슬라이스 동안 실행된다.

 

만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행된다. 결국 CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아진다. 이로 인해 CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고, CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 종료된다.

 

또한 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 존재한다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있다. 다단계 피드백 큐 스케줄링은 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘이다.

 

다단계 피드백 큐 스케줄링은 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘으로 알려져있다.