CPU 스케줄링 2

OS가 CPU를 스케줄링하는 과정에 대해 배운 내용을 정리해보았다.

지난 글에서 기본적인 CPU 스케줄러에 대해서 알아보았다. 이번 글에서는 실제로 비교적 최근의 OS가 CPU 스케줄러를 구현하는 방식인 Priority Scheduling에 대해서 알아보자.

Priority Scheduling

실제 OS에서는 모든 job의 우선순위를 동일하게 두지 않는다. 수행해야 할 job의 정보가 제한적이기 때문에, OS의 scheduler는 각 job에 대해 우선순위를 부여하고 우선순위에 따라 실행하는 방식으로 구현되어있다. 먼저 각 job의 우선순위가 변하지 않는 Static Priority Scheduling을 살펴보고, 다음으로 우선순위가 변하면서 스케줄링되는 Dynamic Priority Scheduling을 알아보도록 하자.

Static Priority Scheduling

Static Priority Scheduling에서는 각 job이 변하지 않는 우선순위를 가진다. 이 우선순위에 따라 가장 높은 우선순위를 가진 job이 다음에 실행되고, 같은 우선순위를 가진 job들은 Round-Robin 이나 FIFO로 실행한다. preemptive와 non-preemptive 두 가지 방법 모두로 구현할 수 있다.

하지만 우선순위가 먼저인 job만 실행하게 된다면 Starvation이 발생할 수 있다.

Dynamic Priority Scheduling

따라서 위의 단점을 보완하기 위해, job의 우선순위를 바꿔가며 스케줄링을 할 수 있다. 몇 가지 예시를 보자.

MLFQ (Multi-Level Feedback Queue)

MLFQ는 Priority별로 Queue를 따로 두어 높은 우선순위의 큐에 있는 job들을 실행하는 방식이다. 우선순위가 다른 두 프로세스가 있다면 높은 프로세스가 돌아갈 것이고, 우선순위가 같은 프로세스가 있다면 프로세스들은 RR로 실행된다. 이것만으로는 Static Priority Scheduling이라고 할 수 있는데, 우선순위를 변경하는 기준을 생각할 수 있다.

보통의 workload는 interactive jobs와 CPU-intensive jobs가 섞인 형태이다. 여기서 interactive jobs는 실행 시간이 짧고, 빠르게 반응해야 하는 특징을 가진다. 이에 반해 CPU-intensive는 CPU를 많이 사용해야 하므로 response time은 조금 늦어도 괜찮다.

여기서 다음과 같은 Rule을 적용해 볼 수 있다.

1. If Priority(A) > Priority(B), A 실행
2. If Priority(A) = Priority(B), A & B Round-Robin으로 실행
3. 어떤 job이 들어왔을 때, 가장 높은 우선순위를 부여
4. 그 job이 실행되는 동안 time slice를 모두 사용하면, 우선순위를 한 단계 낮춤
5. time slice가 끝나기 전에 CPU를 놓으면 같은 우선순위 레벨에 둠.

A는 실행시간이 긴 job, B는 실행시간이 짧은 job, C는 interactive한 job이라고 할 때, MLFQ는 다음과 같이 실행한다.

Priority Boost

위 그래프에서는 전혀 문제가 없어보이지만, 이 정책을 적용할 경우 interactive jobs가 CPU를 모두 사용할 수 도 있다. 따라서 Rule 5을 다음처럼 고쳐볼 수 있다.

• time period S가 지난 뒤, 모든 job의 우선순위를 가장 높은 우선순위 큐로 올린다.

Better Accounting

또한 어떤 프로세스가 악의적으로 time slice가 끝나기 직전에 CPU를 놓아 우선순위가 낮아지는 것을 방지할 수도 있다. 이를 막기 위해 Rule 4를 고쳐보자.

• 어떤 job이 사용하는 시간에 비례해서 job의 우선순위를 낮춘다.

Linux CFS

이를 바탕으로 리눅스의 Completely Fair Scheduler를 알아보자. Linux 2.6.23버전부터 사용된 스케줄러로, Priority에 따라 task를 수행하는 스케줄러이다.

Linux Task Priority에는 총 140레벨이 있다. 0으로 갈수록 priority가 높아지는 것인데, 일반적으로 사용자가 Non-real-time에 부여할 수 있는 우선순위는 nice 값으로 나타낸다. nice 값은 priority 값 100부터 139까지로, 99 이하의 값은 사용자가 부여할 수 없고 리눅스가 부여한다.

리눅스는 이 priority 값에 따라 CPU를 점유하는 시간의 차등을 두어 프로세스를 실행시킨다. 이 값이 1정도 차이나면 CPU를 점유하는 시간이 10%정도 차이나도록 하는데, 그 차이는 Virtual Runtime으로 계산한다.

$$ VR(T) = \frac{Weight_0}{Weight(T)} \times PR(T) $$

여기서 \(Weight_0\) 는 nice값이 0인 프로세스의 weight이다. 각 우선순위에 따라 부여된 Weight로 Virtual Runtime을 계산하면, 같은 Virtual Runtime 10ms라도 우선순위가 높은 프로세스는 10ms보다 많이 실행되고, 우선순위가 낮은 프로세스는 적게 실행된다. Linux의 CFS는 이렇게 계산한 Virtual Runtime 값을 key로 하는 RB Tree로 관리하여 그 값이 가장 적은, 즉 지금까지 실행된 Virtual Runtime이 가장 적은 프로세스를 실행하도록 스케줄링한다.