Linux Process Scheduling

프로세스 스케줄링

리눅스에서의 프로세스 스케줄링 전에 전반적으로 프로세스 스케줄링에 있어서 고려사항들을 살펴보자. 프로세스 스케줄링에 있어서 고려할 사항은 프로세스를 언제 스위칭할건인지, 그리고 어떠한 기준으로 다음으로 돌릴 프로세스를 결정할 것인지, 프로세스가 돌아갈적에 한번 할당된 자원을 끝까지 놓치게 할지/말지 와 같은 고려사항이 있을 수 있다. 스케줄링을 하기 직전에 스케줄링을 당하는 프로세스의 종류에 대해서도 한번 보면 I/O 작업이 많은 프로세스가 있을 것이고, CPU 작업이 많은 작업이 많은 프로세스가 있을 것이고, 특정 시간전에 무조건 끝내야 될 프로세스가 있을것이다. 이러한 다양한 프로세스가 존재하는 와중에 리눅스에서의 프로세스 스케줄링은

1. time slicing : 프로세스는 스케줄러 부터 타임 퀀텀을 할당 받는 방식으로 스케줄링 된다.
2. priority : 각각의 프로세스는 우선순위에 기반해 다음 돌아갈 프로세스를 정하게 된다.
3. static/dynamic priority : 우선순위의 경우 고정되는 방식과 돌아가는 도중에 바뀌는 우선순위 두가지 방법을 다 지원한다.
4. preemptive : 자신의 프로세스보다 우선순위가 높은 프로세스가 존재할 경우 도중에 실행을 중단하고 자원을 넘겨줄 수 있다.

을 따르고 있다.

리눅스 스케줄러의 종류

이제 구체적으로 리눅스 스케줄러에 대해서 알아보자. 리눅스 스케줄러 역사에 대해서 전체적으로 보면 다음과 같이 볼 수 있다.

1. O(N) 스케줄러
2. 2.6.0 의 O(1) 스케줄러
3. 2.6.23의 O(logN) cfs 스케줄러

O(N) 스케줄러의 경우 모든 프로세스가 단일 큐에서 관리되는 스케줄러로 매우 비효율적이라고 볼 수 있다, 2번째 O(1) 스케줄러에 대해서 먼저 알아보자.

2.6.0 O(1) 리눅스 스케줄러

2.6.0 O(1) 스케줄러에 대한 특징이라고 하면

1. 우선순위에 기반한 preemptive 한 스케줄러
2. IO bound 프로세스의 경우 할당된 타임 퀀텀을 다 소진하게 되면 blocking 상태에 들어가 기존에 할당된 타임 퀀텀을 다 소진하지 못하게 되는데, 이러한 IO bound/CPU bound 프로세스의 특성을 고려해서 설계된 스케줄러

인 점이다. O(1) 스케줄러에 대해서 자세하게 들어가기전에 POSIX 스케줄러에 대해서 애기하자면 기본적으로 리눅스의 스케줄러는 POSIX 스케줄러 표준을 따르도록 설게되어 있으며 크게 3가지로 나뉘어진다.

1. SCHED_FIFO
2. SCHED_RR
3. SCHED_OTHER

real time job을 위한 first-int-first-out과 round-robin의 스케줄러를 둘다 지원해야 하며 sched_other를 통해서 최적의 스케줄러를 제공해야 하며 2.6.0 O(1) 스케줄러에서는 sched_other의 스케줄러에 O(1) 스케줄러를 사용하고 있다. O(1) 스케줄러에서는 기본적으로 140개의 우선순위르 기반으로 설계되어 있는데, 0~99의 우선순위는 sched_fifo, sched_rr을 위한 우선순위이고, 실질적으로 O(1) 스케줄러는 100~139의 우선순위를 가지고 프로세스를 스케줄링하게 된다. 그리고 각각의 우선순위별로 run queue로 프로세스를 관리하고 있으며 높은 우선순위별로 각 큐에 있는 프로세스를 탐색하여 높은 우선순위 별로 탐색하게 된다. 다음 프로세스를 특정하기 위해선 140개의 run queue만 탐색하게 해당 run queue가 비어있지 않게 된다면 가장 앞쪽에 위치한 프로세스만 수행하면 되기 때문에 시간복잡도가 O(1)가 된다. 실제로 하나의 run queue에 의해 스케줄러가 관리되게 되면 우선순위가 높아서 우선 한번 스케줄링 된 프로세스가 계속 돌게 되어 우선순위가 낮은 프로세스가 평생 돌지 못하게 되는 starvation의 문제점이 발생할 수 있다. 이 때문에 두개의 큐를 통해서 관리하게 된다. active, expired 두개의 큐를 이용해 스케줄러가 동작하게 되며 스케줄링은 active 큐에 의해서 스케줄링 되게 된다. sched_fifo, sched_rr의 스케줄러에 의해 스케줄 된 프로세스의 경우에는 active큐에서 타임퀀텀을 다시 소진하게 되면 다시 active큐에 해당 프로세스가 돌아오지만, sched_normal에 의해 스케줄된 프로세스의 경우 active큐에 존재했다가 스케줄된 경우 다시 expired queue에 돌아오게 된다. 계속 active큐를 기존을 스케줄 되다가 active 큐가 비게 될경우 포인터의 교환 방식을 통해서 active 큐와 expired큐가 바뀌게 된다. 이때 sched_fifo, sched_rr의 프로세스의 경우 스케줄 된 다음에 다시 active 큐에 돌아오게 되기 때문에 O(1) 스케줄러는 sched_normal인 프로세스에 한해서 starvation문제점을 해결한거라고 볼수 있다.

O(1) 스케줄러에서 우선순위에 따라서 타임퀀텀을 배정하고 있으며, 우선순위가 높을수록 타임퀀텀을 배정하고 있다. sched_normal의 경우 기본적으로 프로세스의 우선순위는 따로 설정하지 않을 경우 120으로 고정되어 있으며, IO bound process에 대한 배려를 해주기 위해서 동적으로 우선순위를 변화시키기도 한다. O(1) 스케줄러는 IO bound process에 대해서 sleep time이 존재하는 프로세스에 대해서 해당 프로세스에 '보너스'의 개념으로 우선순위를 올려서 다음 스케줄 과정에서 이점을 준다.

O(1) 스케줄러의 단점으로는 우선순위에 따라서 프로세의 스위칭 주기가 다르다는 것이다. 똑같은 우선순위 120인 프로세스 3개와 우선순위 139인 프로세스 3개를 비교해 봤을때, 상대적인 우선순위는 똑같지만 139인경우 우선순위에 따라사 배정되는 타임퀀텀이 달라지기 때문에 139일때 스위칭 주기가 훨씬 빨라진다. 또 다른 문제점으로는 같은 우선순위의 1차이에 대해서 배정되는 타임퀀텀의 비율이 급격하게 달라진다. 120,121의 우선순위의 프로세스가 있는 스케줄러와 138,139의 우선순위의 프로세스가 있는 스케줄러를 비교해봤을때, 전자의 경우 5퍼 정도의 타임퀀텀의 차이 밖에 존재하지 않지만 후자의 경우 2배의 타임퀀텀의 차이를 보인다. 이러한 불균형을 해결하기 위해서 다음 O(logn)의 시간 복잡도를 갖는 cfs scheduler가 제시된다.

2.6.23 O(logn) cfs 스케줄러

cfs 스케줄러는 기존의 O(1) 스케줄러에서 발생하는 프로세스별로 cpu의 불균형한 분배의 문제점을 해결하고자 한다. cfs 스케줄러에서는 'weight'를 부여하고, 이에 비례하게 프로세스의 타임퀀텀을 분배하고자 한다. 각각의 우선순위별로 weight를 부여하고, 이떄 wegith는 우선순위별로 1올라갈때마다 weight가 25프로 증가하는 식으로 배정했다. 이는 기존의 O(1) 스케줄러에서 상대적인 우선순위가 동일함에도 불구하고 cpu의 타임퀀텀이 불균형하게 배정되는 문제점을 해결하고자 하는것으로 보인다. 각각의 프로세스별로 우선순위에 해당하는 weight가 배정되게 되면 이를 기반으로 virtual run time이 계산된다. virtual run time은 프로세스가 실제로 돌아간 run time에 프로세스의 weight를 고려한 run time을 계산한것으로, weight가 클수록 우선순위가 높아 적게 virtual run time이 적게 계산되는 형식으로 run time을 계산하게 된다. 이러한 virtual run time을 기준으로 cfs 스케줄러는 가장 작은 virtual run time을 가지는 프로세스를 선택하게 된다. 스케줄러에서 배정하는 타임퀀텀의 경우 현재 스케줄러에 존재하는 모든 프로세스의 weight를 추적한 다음 weight에 비례하게 타임 퀀텀을 배정하게 된다.

cfs 스케줄러는 virtual run time을 기준으로 red-black tree를 통해서 스케줄러를 관리하게되며, O(1)에서 sched_normal에서 우선순위별로 run queue를 관리했던 것과는 별개로 통채로 red-black tree를 통해서 관리하게 된다.

preemptive kernel vs non-preemptive kernel

kernel이 preemptive한지 안하는지에 대해서 알아보면 기본적으로 kernel 코드가 수행될 때 다른 프로세스로 스위칭이 일어나게 되면 바로 넘어가지 못하고 kernel 쪽에서 마무리 작업을 한 뒤에 넘어가는 것이 일반적이다. 여기서 preemptive kernel의 경우 바로 다른 프로세스로 스위칭이 가능한 kernel을 뜻하며 preemptive kernel의 경우 원래는 non-preemptive kernel의 리눅스와는 다르게 다른 상용화된 운영체제들의 장점으로 꼽혔다. 하지만 현재 리눅스는 kernel preemption을 지원하고 있으며, 만약 preemption이 위험한 상황의 코드의 경우 lock을 걸어서 preemption을 방지하고, 만약 lock이 걸려있지 않으면 kernel preemption을 허용하는 방법으로 이를 지원하고 있다.