반환시간이나 응답시간을 최적화하기보다는 잡들이 cpu를 일정 비율로 나눠 사용하는 것을 목적으로 하는 정책들 중, Stride 스케줄링이 있다.

잡들이 이제까지 몇번의 보폭(stride)을 거쳐서 얼마나 왔는지(pass)를 관리하고, 이에 따라 아직 덜 온 잡에게 cpu를 할당해주는 방식이다.

큐에 여러 잡들이 들어가있고, 각 잡들에는 패스값이 담겨있기 때문에 그들 중 가장 패스값이 작은 잡을 우선적으로 스케줄링하여 실행시켜준 뒤, 해당 잡의 패스값을 스트라이드만큼 증가시킴으로써 그 다음에 실행될 잡들을 다시 결정해나간다.

이 때 잡들의 스트라이드는 우선순위에 따라 결정되는데, 스트라이드가 클수록 우선순위가 낮아진다.

스트라이드가 크다는 것은 그만큼 한번 걸을 때(cpu를 한번 사용할 때) 패스값이 크게 누적되면서, 다른 잡들에 비해 스케줄링 될 기회가 적어지게 되기 때문이다.

예를 들어 3개 잡 A, B, C의 스트라이드가 각각 200, 50, 100인 상황이라고 할 경우에는 아래와 같이 스케줄된다.

처음엔 모든 패스값들이 0으로 동일하기 때문에 우선 A를 실행시키고, A는 한번 cpu를 할당받은 뒤 스트라이드인 200만큼 패스값이 증가한다.

같은 방식으로 B와 C가 스케줄링 되어 각자의 스트라이드값만큼 패스값이 갱신되면, 4번 과정에서는 패스값이 가장 낮은 B가 스케줄되고, 5번에서도 패스값이 동일하기 때문에 다시한번 B가 스케줄링 된다.

이런 방식으로 현재 패스값에 따라 스케줄링이 되기 때문에, 보폭이 커서 cpu를 한번 사용할 때 패스값을 크게 증가시키는 잡 A의 경우에는 다른 잡들에 비해 덜 스케줄링이 되는 것이다.

이런 Stride 스케줄링 정책을 기반으로 하여, 리눅스에서는 CFS(Complete Fair Share) 스케줄러를 사용한다.

CFS에서는 패스값을 vruntime이라고 하며, 보폭은 프로세스마다 지정되는 우선순위인 nice값(niceness)에 의하여 결정된다.

nice 값은 -20 ~ 19 까지의 범위 안에서 설정되는데, nice값으로 -20(가장 우선순위가 높은 값)은 88761의 우선순위를 갖는 반면에 19(가장 낮은)의 경우는 15까지 내려간 낮은 우선순위를 갖게 된다.

이 때 특정 프로세스의 stride는, nice값 0(실제 우선순위값 1024) / 자신의 우선순위 값이 되는데, 우선순위가 높을수록 보폭은 그만큼 작아지고, 낮을수록 보폭은 그만큼 커지는 효과를 갖는다.

이렇게 보폭에 차이를 둠으로써 우선순위가 높은 잡들이 더 자주 cpu를 할당받게 된다.

뿐만 아니라 cpu를 제공해줄 때 타이머 인터럽트를 거는 타임 슬라이스를 다르게 준다.

타임 슬라이스 값 = 자신의 우선순위 값 / 모든 잡들의 우선순위값의 합으로 나눈 값으로 지정하기 때문에, 우선순위가 낮은 잡들은 높은 잡보다 cpu를 상대적으로 짧게 사용하게 되는 것이다.

즉 우선순위가 높으면 cpu 할당을 더 자주 받고, 한번 사용할 때도 더 오래 쓰지만, 우선순위가 낮으면 더 짧게 더 적게 사용하는 구조로, 어떻게든 억까를 당하도록 잘 설계되어있다.

아무튼 CFS도 stride 스케줄링과 마찬가지로, 큐에 있는 레디 프로세스들 중 vruntime(패스값)이 가장 낮은 프로세스에게 cpu를 할당해준다.

그러나 시스템에 사실상 레디상태로 대기중인 프로세스들은 수백, 수천개가 되기 때문에, 이를 일반적인 연결리스트 등으로 관리할 경우 매번 일어나는 삽입과 삭제 연산 등에서 불리하다.

이 때 큐를 균형잡힌 이진탐색트리인 Red-Black Tree로 구현함으로써, 다음 실행할 잡을 찾는 복잡도를 O(logN)으로 맞춤으로써 효율적인 탐색을 가능하게 한다.

리눅스 커널에서 관리하는 vruntime에 대해서는 /usr/src/linux-4.20.11/include/linux/sched.h 아래에서 찾아볼 수 있다.

bconfiden2@h01:~$ cat /usr/src/linux-headers-5.8.0-43-generic/include/linux/sched.h
# ...
struct sched_entity {
        u64                             exec_start;
        u64                             sum_exec_runtime;
        u64                             vruntime;
        u64                             prev_sum_exec_runtime;
        # 기타 등등...
};
# ...