CPU 스케줄링 기법 총정리

1. 스케줄링의 개념

컴퓨터 자원을 효율적으로 사용하기 위핸 정책을 계획하는 것이다. 말 그대로 스케줄을 관리하는 것이다. 특정 자우너을 요청하고 있는 프로세스들을 대상으로 CPU 자원을 할당해 주는 순서를 정하게 된다.

 

이를 통해 CPU 활용을 극대화할 수 있다. CPU의 유휴 시간을 최소화하기 때문이다. 또한 응답시간을 단축할 수 있다. 프로세스 평균 응답 시간이 단축된다. 공평한 자원 활용도 가능해지는데, 주어진 기간 동안 특정 자원 사용 효율을 높일 수 있다. 또한 멀티 테스킹 작업도 높은 효율을 얻는다. 다중 프로세스의 공평한 처리가 이를 가능케 한다.

 

2. 스케줄러의 구분 - 역할

스케줄러의 역할에 따라 장기 스케줄러, 중기 스케줄러, 단기 스케줄러로 구분할 수 있다.

장기 스케줄러는 상위 스케줄링, 작업 스케줄링이라고도 말하며, 어떤 작업이 시스템의 자원들을 차지할 것인지를 결정한다.

중기 스케줄러는 어떤 프로세스들이 CPU를 할당받을 것인지 결정한다. CPU를 사용하려는 프로세스 간 중재를 통해 일시 보류와 재활성화를 한다.

단기 스케줄러는 하위 스케줄링, CPU 스케줄링, 프로세스 스케줄링이라고도 하는데, CPU 스케줄러인 Dispatcher에 의해 동작된다.

 

2.1 스케줄러의 구분 - 점유 방식

이 방식으로 구분하는 것이 아마 가장 친숙할 것이다. 바로 선점 / 비선점이다.

선점 방식은 프로세스가 CPU 점유 중에도 다른 프로세스가 CPU를 점유할 수 있는 방식으로, 빠른 응답과 대화식 시분할에 적합하다는 장점을 지니지만 Overhead가 발생할 우려가 있다.

비선점 방식은 프로세스가 CPU를 해제할 때까지 다른 프로세스는 대기를 해야 하는 방식이다. 따라서 응답시간을 예상하기가 쉽고, Batch Process에 적합하며, 프로세스에 대한 요구를 공정하게 처리할 수 있다. 그러나 짧은 작업임에도 오랜 시간 대기할 수도 있을 것이다.

 

아래의 표를 통해 선점형과 비선점형을 더욱 쉽게 비교하여 이해할 수 있을 것이다.

기준	선점형	비선점형
인터럽트	중간에 프로세스가 중단될 수 있다.	프로세스가 자체적으로 종료되거나 시간이 다 될 때까지 프로세스를 중단할 수 없다.
오버헤드	프로세스를 스케줄링하는 과정에서 오버헤드가 발생한다.	오버헤드가 없다.
유연성	매우 유연하다.	매우 엄격하다.
응답시간	상대적으로 짧다.	상대적으로 길다.
의사결정	결정은 스케줄러에 의해 이뤄지며, 우선순위 및 시분할을 기반으로 한다.	결정은 프로세스 자체에서 이뤄지며, OS는 프로세스의 지시에 따른다.
프로세스 제어	OS는 프로세스 스케줄링을 더욱 효과적으로 제어할 수 있다.	OS는 프로세스 스케줄링에 대한 통제력이 적다.

 

3. CPU 스케줄링 기법

ㄱ. FCFS(First Come First Service)

쉽게 말해 선착순이다. 대기 큐에 도착한 순서에 따라 CPU를 할당한다. 일단 프로세스가 CPU를 차지하면 완료될 때까지 수행하므로 비선점형 스케줄링 기법에 속한다. FCFS는 구현 및 사용이 매우 쉽지만, 성능 측면에서는 그다지 효율적이라 말할 수는 없을 것이다.

 

ㄴ. SJF(Shortest Job First)

SJF는 비선점 스케줄링으로, 기다리고 있는 작업 중에서 수행 시간이 가장 짧다고 판단된 것을 먼저 수행한다. FCFS보다 평균 대기시간을 감소시키는 반면, 큰 작업에 대해서는 FCFS에 비해 대기시간 예측이 어렵다. 모든 운영체제 스케줄링 알고리즘 중에서 평균 대기시간이 최소라는 강점이 있기에 FCFS보다 우수하다고 할 수 있다. 다만, 앞서 말한 대기시간 예측이 어려워지는 것에 더해, 기아 현상이 발생할 수 있다는 단점이 있다.

 

ㄷ. LJF(Longest Job First)

이름에서도 알 수 있듯, SJF의 정반대인 알고리즘이다. 마찬가지로 비선점이며, 기다리고 있는 작업 중에서 수행 시간이 가장 길다고 판단된 것을 먼저 수행한다. 만일 동일하다면 그때는 FCFS를 적용하는 것이다. SJF의 반대라는 것은, SJF의 장점이 여기서는 단점으로 작용한다는 뜻일 것이다. LJF는 실제로 매우 높은 평균 대기시간과 처리시간을 자랑하는 알고리즘이다.

 

ㄹ. Priority

선점형인 우선순위 스케줄링은 프로세스의 우선순위에 따라 작동한다. 즉, 가장 중요한 프로세스를 먼저 수행함을 의미한다. 동일한 가치를 지니는 경우에는 앞서 다른 알고리즘 모두가 그러했듯, FCFS를 적용한다. 평균 대기시간은 FCFS보다 짧은 편이고, 복잡성도 적은 편이지만, 기아 현상이 발생할 수 있다.

 

ㅁ. Round Robin

일단 시작은 FCFS다. 그런데 각 프로세스에 같은 크기의 CPU 시간을 할당한다. CPU 시간이 만료될 때까지 처리를 완료하지 못하면, CPU는 대기 중인 다음 프로세스로 넘어가는 선점형이며, 실행 중이던 프로세스는 준비 오나료 리스트의 가장 뒤로 보내진다.

예시로 들면, CPU 시간을 2시간씩 할당하기로 정했다. 프로세스는 순서대로 A(5시간), B(2시간), C(4시간), D(3시간)이 있으면, A를 먼저 처리하되 2시간을 처리한다. 그럼 A는 3시간을 남긴 채로 대기 리스트 제일 뒤로 넘어가 BCDA로 진행하게 된다. 모든 프로세스가 균형 잡인 CPU 할당을 받기 때문에 간단하고 사용이 쉽다. 또한, 기아 현상이 발생하지 않게 된다. 그래서 CPU 스케줄링에서 가장 널리 사용되는 방법 중 하나이기도 하다. 

 

ㅂ. SRT(Shortest Remaining Time)

SJF와 마찬가지로 새로 도착한 프로세스를 포함하여, 처리가 완료되는 데까지 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행한다. SJF와 차이가 있다면, SRT는 선점형이기 때문에 실행 중인 프로세스라도 남은 처리 시간이 더 짧다고 판단되는 프로세스가 생기면 언제라도 해당 프로세스가 선점하여 처리된다. 결론적으로 SJF + 선점형인 것이다. 짧은 프로세스가 매우 빨리 처리되고, 시스템은 프로세스가 완료되거나 새 프로세스가 추가될 때만 결정을 내리기 때문에 오버헤드가 거의 발생하지 않는다고 볼 수 있다. 다만, 짧은 프로세스를 우선적으로 처리하다 보니 긴 프로세스가 무기한 보류될 수 있다는 약점은 존재한다.

 

ㅅ. LRT(Longest Remaining Time)

SRT의 반대 스케줄링으로 생각하면 된다. 언제든, 가장 오래 걸리는 작업부터 먼저 수행하는 선점형 알고리즘이다. 8시간 7시간 5시간 4시간 작업이 있다고 가정하면, 작업 완료 직전의 단계에서 1시간 1시간 1시간 1시간으로 각 작업이 남게 될 것이다. 그렇기에 모든 작업이나 프로세스가 거의 동시에 완료된다고 볼 수 있다. 그렇게 되면 자연스레 매우 높은 처리시간, 대기시간을 갖게 된다.

 

ㅇ. HRRN(Highest Response Ratio Next)

HRRN은 비선점형 스케줄링으로, 가장 최적의 스케줄링 알고리즘 중 하나로 꼽힌다. 모든 프로세스의 응답 비율을 찾고, 그 응답 비율이 가장 높은 프로세스를 선택하는 방식이다. 비선점형이므로 선택된 프로세스는 완료될 때까지 실행한다. HRRN은 (프로세스 대기시간 + 프로세스 서비스 시간) / 프로세스 대기시간으로 구할 수 있다.

이 HRRN은 기아 문제를 해결하기 위한 SJF의 변형 버전이라 할 수 있는데, 그래서 일반적으로 SJF보다 더 나은 성능을 제공한다 볼 수 있다. 다만 이 스케줄링은 CPU의 과부하를 야기할 수 있을 것이다.

 

ㅈ. MLQ(Multi Level Queue)

여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 스케줄링 기법이다. 그룹화된 작업들은 각각의 준비 큐에 넣어두고, 각 큐의 독자적인 스케줄링 알고리즘에 따라서 CPU를 할당받는 방법이다. 앞선 스케줄링과 다르게 여러 개의 큐가 있다는 것이 큰 차이일 것이다. 이 스케줄링은 오버헤드가 매우 낮은 장점이 있지만, 기아 현상을 해결할 수 없다는 단점이 있다.

 

ㅊ. MLFQ(Multi Level Feedback Queue)

입출력 위주와 CPU 위주인 프로세스의 특성에 따라 서로 다른 타임 슬라이스를 부여하는 방식이다. 새로운 프로그램이 들어오면 높은 우선순위를 할당해 단계 1에서 즉시 수행한다. 그렇게 점차 낮은 우선순위를 부여하며 단계가 어느정도 진행되면, 나중에는 그 작업이 완료될 때까지 라운드 로빈으로 순환한다. 결국, MLFQ는 우선순위 큐와 라운드 로빈이 더해진 하이브리드 방식의 스케줄링이라고 말할 수 있다. 이 스케줄링은 매우 유연하며, 서로 다른 프로세스가 서로 다른 대기열 사이를 이동할 수도 있지만, 그만큼 CPU 오버헤드가 발생하고, 가장 복잡한 알고리즘이기도 하다.

 

아래의 표를 통해 각 스케줄링 알고리즘을 비교하기 쉽게 정리하였다.

종류	CPU 할당	복잡성	평균 대기시간	선점 여부	기아	성능
FCFS	프로세스 도착 시간에 따라 할당	간단하고 쉬움	큼	X	X	느림
SJF	가장 낮은 CPU 서비스 시간 기준	FCFS보다 복잡	FCFS보다 작음	X	O	최소의 평균 대기시간
LJF	가장 높은 CPU 서비스 시간 기준	FCFS보다 복잡	도착시간, 프로세스 크기 등에 따라 달라짐	X	O	큰 처리시간
SRT	가장 낮은 CPU 서비스 시간 기준	FCFS보다 복잡	도착시간, 프로세스 크기 등에 따라 달라짐	O	O	단기 작업을 선호
LRT	가장 높은 CPU 서비스 시간 기준	FCFS보다 복잡	도착시간, 프로세스 크기 등에 따라 달라짐	O	O	장기 작업을 선호
RR	고정된 시간을 기준으로 공정한 순서	시간 할당량에 따라 다름	SJF나 Priority에 비해 큼	O	X	각 프로세스에 공정한 시간을 부여
선점형 Priority	우선순위 기준	상대적으로 단순	FCFS보다 작음	O	O	기아 문제를 제외하면 좋음
비선점형 Priority	새로 들어오는 상위 우선순위 작업에 따라 할당	선점형 Priority보다 단순	FCFS보다 작음	X	O	배치 시스템을 사용할 경우에는 가장 유용
HRRN	응답 비율 기준	FCFS보다 복잡	FCFS보다 작음	X	X	좋음
MLQ	더 큰 대기열 우선순위에 있는 프로세스 기준	Priority보다 복잡	FCFS보다 작음	X	O	기아 문제를 제외하면 좋음
MLFQ	더 큰 대기열 우선순위에 있는 프로세스 기준	가장 복잡하지만, 복잡도는 시간 할당 크기에 따라 다름	대부분의 경우에서 모든 스케줄링 타입보다 작음	X	X	좋음