Cpu 스케줄링 2 (MLFQ ~ Linux Scheduler)

발전된 Cpu 스케줄링 기법부터 리눅스의 스케줄링 기법을 알아보기

Created Apr 9, 2024 - Last updated: Apr 9, 2024

서론

지난 글에서 여러가지 CPU 스케줄러를 제시하면서 스케줄러가 가져야할 특성들에 대해서 논의해보았습니다. 그리고 마지막으로 I/O aware STCF을 제시했지만 현실적으로 각 job의 runtime을 아는 것은 불가능하기에 스케줄러로 채택하기에는 무리가 있었죠.

그렇다면 어떤 스케줄러를 생각할 수 있을까요? 한번 일반적으로 적용가능한 스케줄러를 생각해보고, 리눅스에서는 어떤 것을 채택했는지 알아보겠습니다.

MLFQ (Multi-Level Feedback Queue)

이전에 보았던 Priority Scheduling Queue를 기억하시나요? job마다 priority를 부여한 뒤 그 priority에 따라서 스케줄링을 했었죠. 그런데 그 때는 priority가 한번 부여되고나면 조절하지는 못했습니다. 그래서 static priority라고 하기도 했습니다.

이번에는 priority가 조절되는 Dynamic priority를 사용할 것입니다. 그 후 각 priority마다 프로세스 큐를 만들어서 cpu를 스케줄링할 것입니다. 그러면 아래의 그림과 같이 Multi-level로 운용되는 상황이 될 것입니다.

그러므로 스케줄링 규칙은 다음과 같습니다.

If Priority(A) > Priority(B), A runs.

If Priority(A) = Priority(B), A & B run in RR.

Priority

한편 priority는 어떻게 정해질까요? 처음에 프로세스가 들어오면 그 프로세스에게 최고 priority를 부여합니다. 그런 뒤 주어진 time slice동안 프로세스가 다 실행되지못하면 priority를 낮춥니다.

여기서 이상함을 느끼실 수 있습니다. 프로세스가 주어진 time slice동안 끝나지않으면 긴 시간이 필요한건데 왜 prioirty를 낮추느냐 생각이 드실 것입니다.

이는 interactive한 프로세스의 priority를 높게 유지하기 위해서입니다. 예를 들어 사용자와 즉각적으로 상호작용해야하는 프로세스는 실행시간은 적게들고 우선 순위는 높아야하겠죠. 이를 위해서 time slice동안 프로세스가 끝나냐를 기준으로 priority를 낮추게 됩니다.

그러므로 추가적인 스케줄링 규칙은 다음과 같습니다.

When a job enters the system, it is placed at the highest priority (the topmost queue).

If a job uses up an entire time slice while running, its priority is reduced (i.e., moves down one queue).
If a job gives up the CPU before the time slice is up, it stays at the same priority level.

그리고 세개의 프로세스가 들어왔을 때 다음과 같이 유지될 것입니다.

Priority Boost

물론 이렇게 하는 것만으로는 모든 문제를 해결하지는 못합니다. 왜냐하면 만약 priority가 높은 job이 계속해서 들어온다면 priority가 낮은 job은 starvation이 발생하겠죠?

그래서 등장한 개념이 바로 Priority Boost입니다. 이는 모든 job이 실행될 수 있도록 일정 시간이 지나면 다시 모든 job의 priority를 최고레벨로 올려놓는 것입니다.

After some time period S, move all the jobs in the system to the topmost queue.

그러면 starvation 문제를 막고 아래와 같이 실행될 수 있겠죠.

Precise accounting

그런데 이렇게까지 했는데도 여전히 문제가 있습니다.

만약 악성 프로세스가 time slice 직전에 cpu를 놓아버려서 계속 높은 priority를 유지하면 그 프로세스는 계속 많은 시간을 점유하겠죠?

그래서 그냥 time slice를 주는 것보다는 실제로 그 job이 사용한 시간을 재서, 만약 그 priority 레벨에 주어진 시간을 초과했다면 priority를 내려버리는 방법을 사용합니다.

그러면 결과적으로 아래와 같이 정확한 스케줄링이 가능하겠죠.

정리

정리해보자면 MLFQ는 Preemptive dynamic priority scheduling이라고 볼 수 있겠습니다. 핵심 파라미터로 priority와 time slice를 사용하고 Cpu를 많이 쓸수록 priority를 내리는 aging이라는 방법을 사용하죠.

그래서 job이 어떻게 들어오든지 최대한 효율적으로 cpu를 운용할 수 있게되는 것입니다.

Linux Scheduler

그러면 마지막으로 실제로 Linux의 스케줄러에 대해 살펴보겠습니다. Linux 2.6.23부터는 CFS(Completely Fair Scheduler)를 사용합니다. 즉 모든 프로세스가 공평하게 cpu를 할당받을 수 있도록하는데 어떻게 그러게 가능한지 보곘습니다.

Linux Task Priority

Linux의 task는 총 140개의 priority value를 가질 수 있습니다. 그렇지만 우리가 사용하는 일반적인 프로세스들은 non-real-time task로 불리며100~ 139의 값을 가집니다. 그리고 이 priority value는 클수록 실제 우선순위는 낮습니다.

Priority가 아니라 priority value 입니다. {: .prompt-danger }

Nice

non-real-time task에 priority를 설정하는 nice라는 개념이 있는데요, 이 nice는 -20 ~ 19사이의 값을 가집니다.

nice가 0이라면 priority value가 120이고 nice가 -20이라면 priority value가 100인 식입니다.

즉 nice는 priority value를 세팅해주는 개념인데 왜 nice라는 이름이 붙었나 찾아보니까 nice가 높아서 우선순위가 낮아지면 다른 프로세스에게 시간을 양보해주기때문에 우선순위가 낮은 프로세스가 더 nice하다고 표현하기 위해 nice를 썼다고 합니다.

Weight

한편 이 nice라는 개념이 바로 그 task가 얼마나 cpu를 차지할지를 결정하지는 않고, nice를 weight라는 개념으로 치환한 뒤 그 weight를 바탕으로 그 task의 cpu 쉐어 비율을 결정하게됩니다.

nice가 어떻게 weight로 바뀌는지는 잠시 생략해두고, weight에 따라 cpu 쉐어비율이 어떻게 정해지는지 먼저 보겠습니다.

만약 4개의 task A, B, C, D가 있고, 각 task의 weight이 2, 1, 4, 1이라면 A의 cpu 쉐어비율은 다음과 같이 정해지게됩니다. 자신의 weight의 전체 weight의 합에 대한 비율이죠.

$$ Task,A’s,share = \frac{weight_{A}}{\sum_{i=1}^{n} weight_i} $$

Nice to weight

그럼 이제 nice가 어떻게 weight으로 바뀌는지 설명드리겠습니다. 우선 이 nice개념을 제시한 사람들이 원했던 것은 nice가 1 올라가면 cpu 점유 시간이 10프로 줄어들길 원했습니다.

그렇게 되려면 다음과 같은 결과가 성립해야 하고 이는 nice가 1 올라가면 weight가 25% 줄어야함을 의미합니다.

$$ \frac{weight_{i}}{weight_{i + 1}} = \frac{0.55}{0.45} $$

그래서 기본적으로 nice가 0일 때의 weight을 1024로 설정해놓고 nice가 증가하면 weight을 25%감소시키고, nice가 감소하면 weight을 25% 증가시킵니다.

weight을 빼면 기분이 nice해지니 합리적인듯합니다.

Virtual Runtime

많이 왔지만 여기서 끝은 아닙니다. 말씀드렸다시피 linux의 스케줄러는 CFS로 모든 프로세스에게 완벽하게 공정해야합니다. 그런데 지금 weight만 아는채로는 공정하기 어려울 것 같습니다.

정말로 공정하기 위해서는 모든 프로세스가 같은 비율만큼 돌아야하겠죠. 그러기 위해서는 어떤 실제 시간이 그 프로세스에게는 체감삼 어느정도로 느껴질지 측정해야합니다.

이 체감상 시간이 바로 virtual runtime입니다. virtual runtime은 다음과 같이 구합니다.

$$ VR(T)=\frac{Weight_{0}}{Weight_{T}} * PR(T) $$

즉 PR(T), physical time이 특정 weight을 가진 task에게 체감상 얼마정도로 느껴질지 구하는 것이죠.

Runqueue

이렇게 VR(T)를 구하고 나면 가장 작은 VR(T)를 가지고 있는 프로세슬르 실행시키면서 모든 프로세스를 공정하게 맞출 것입니다.

그렇게 하기 위해서 아래와 같이 red-black tree로 VR(T)를 관리해줄 것입니다.

마무리

가장 기본적인 CPU 스케줄러부터 시작해서 리눅스에서는 어떻게 스케줄링 방식을 유지하고 있는지 살펴보았습니다.

스케줄링을 하는 방식이 이렇게 보면 생각보다는 단순하지만 실제 운영체제의 코드를 뜯으보면 또 어떨지 모르겠습니다.

cpu 스케줄링에 대해 궁금한 점이 풀리셨으면 좋겠고 궁금한 점이 있으시면 댓글로 알려주세요!