[OS 5장] 프로세스 관리 - 스케줄링

앞장에서 설명한 스케줄링의 종류가 3가지가 있었다.

 하지만 그 중 CPU 스케줄링이 가장 중요하다고 할 수 있다.

 이 점은 컴퓨터의 성능과 바로 직결되는 문제를 안고 있기 때문이다. 따라서 CPU 스케줄링이 어떻게 진행되는지에 대해 학습해 보고자 한다.

CPU 스케줄링은 크게 두 가지의 특징으로 나눌 수 있다.

선점하는 방식(Preemptive)과 비선점하는 방식(non-preemptive)이다. 선점하는 방식은 하나의 프로세스가 CPU를 할당받아 작업을 수행하고 있는 도중에 다른 프로세스가 새치기를 할 수 있는 방식을 말한다. 따라서 선점하는 방식을 사용하면 언제든지 CPU가 다른 프로세스에 할당될 수 있다. 하지만 비선점하는 방식을 사용하면 하나의 프로세스가 CPU 할당이 끝이 나야 다른 프로세스가 CPU를 할당 받을 수 있는 형식이다. 선점과 비선점에 의해서 컴퓨터의 성능에 영향을 끼친다.

우리는 이제부터 CPU 스케줄링의 다양한 알고리즘(방법)에 따라 어떻게 스케줄링이 되는지 성능은 어떻게 바뀌는지에 대해 배울 것이다. 그런데 성능을 비교하기 위해서는 기준이되는 비교 척도가 필요하다. 이에 대한 용어 정리를 먼저 해보자.

∙CPU 이용률 :

말 그대로 전체 프로세스를 돌리는 과정에서 CPU가 사용되는 시간을 퍼센트로 나타내는 것이다. 물론 CPU 이용률이 높을수록 CPU가 쉬지 않고 일을 하고 있는 것이니 효율 즉 성능이 좋다고 할 수 있다.

∙처리율 :

처리율은 단위 시간당 처리할 수 있는 프로세스의 양을 나타낸다. 값이 클수록 좋은 성능을 의미한다.

∙반환 시간 :

프로세스가 처음 new 상태로 들어가서 terminated 상태로 나올 때까지의 시간을 의미한다. 짧을수록 좋은 성능을 의미한다.

∙대기 시간 :

CPU를 기다리는 시간을 의미한다. 알고리즘을 비교할 때 대표적으로 비교대상이 되는 값이다. 짧을수록 성능이 좋다.

∙응답시간 :

interactive한 응답의 시간을 의미한다. 예를 들어 웹을 실행하였을 때 빈창에서 하나의 정보라도 모니터에 나올 때까지의 시간을 의미한다.

 

이제 다양한 CPU 스케줄링 알고리즘에 대해서 학습을 해보자.

우선 FCFS(First-Come, First-Served)이다.

말 그대로 먼저 들어온 프로세스를 먼저 실행하는 알고리즘이다. 어떻게 말해서는 가장 간단하고 공정한 알고리즘이 될 수 있지만 평균 대기시간을 비교하는 척도로 하면 좋은 알고리즘이라고 할 수 없다. FCFS는 비선점 스케줄링으로 프로세스가 끝날 때까지 다른 프로세스들이 기다려야한다. FCFS를 이용하게 되면 Convoy effort(호위 효과)를 발생시킬 수 있는데 이 효과는 CPU를 이용하는 시간이 긴 프로세스를 다른 프로세스들이 오래 기다리고 있는 효과로 마치 긴 프로세스를 호위하며 둘러싸고 있다고 해서 이런 이름이 붙여졌다.

다음은 Shortest-Job-First이다.

이 알고리즘도 이름에서 유추하듯이 가장 짧은 CPU 할당 시간을 가진 프로세스를 먼저 처리하는 방식이다. 평균 대기시간을 척도로 하면 가장 합리적인 방법이라고 할 수 있다. 하지만 실제로 CPU 할당 시간을 정확하게 알 수 없으므로 예측을 통해 진행해야한다. 이 알고리즘은 선점 방식일수도 있고 비선점 방식일수도 있다.

프로세스에 정수 값인 우선순위를 주어 CPU를 할당할 수 있는 알고리즘도 있다. 우선순위 스케줄링이라고 불리는데 내부적 외부적으로 다양한 조건들을 활용해 프로세스에 우선순위를 부여한다. 숫자가 작을수록 우선순위가 높아진다. 이 알고리즘도 선점 방식일수도 있고 비선점 방식일수도 있다. 하지만 이 알고리즘은 기아라는 프로세스를 발생시킬 수 있다. 이 프로세스는 우선순위가 낮은 프로세스로 계속해서 이 프로세스보다 우선순위가 높은 프로세스가 들어오게 되면 절대로 처리를 할 수 없게 된다. 이런 문제를 해결하기 위해 aging이라는 기법을 사용하는데 우선순위가 낮은 프로세스가 계속 처리를 못하고 있으면 우선순위를 높여주어 처리를 할 수 있게 해준다.

다음은 Round-Robin이라는 알고리즘이다. 시분할 시스템에서 사용하는 알고리즘으로 CPU를 할당하는 방법으로 Time quantum을 사용한다. Time quantum은 시간 양자라고 하는데 일정시간을 선정하여 CPU 할당을 모든 프로세스에게 동일하게 분담하는 것이다. 이러한 작업은 모든 프로세스가 동시에 할당되고 있는 것처럼 보이게 된다. 여기서 성능은 시간 양자를 얼마의 사이즈로 잡느냐에 따라 달라진다. 이 알고리즘은 시간 양자에 따라 다른 프로세스로 바꾸어주기 때문에 선점 방식이다.

다음으로는 위와 같은 알고리즘은 아니지만 프로세스의 종류에 따라 다른 level을 두어 스케줄링을 하는 Multilevel Queue Scheduling이다. 시스템 프로세스, Interative process, Interactive editing process 등등으로 프로세스 그룹을 나누게 된다. Queue를 여러 개 두어 각 Queue마다 처리하는 프로세스를 다르게 처리한다. Queue에도 우선순위가 존재하며 CPU 시간을 차등으로 배분하게 된다. 각 Queue들은 독립적인 스케줄링 알고리즘을 가지게 된다.

Multilevel Feedback Queue Scheduling도 있는데 Multilevel Queue Scheduling과 같이 복수 개의 Queue를 가지지만 다른 Queue로 점진적으로 이동한다는 점이 다르다. 하나의 입구로 진입하여 너무 많은 CPU time을 사용 시 다른 Queue로 이동하게 되고 기아 상태가 될려고 하면 다시 우선순위가 높은 Queue로 이동하게 된다.

먼저 Multilevel Queue Scheduling이고 다음이 Multilevel Feedback Queue Scheduling이다.