[스케줄링] Scheduling of Linux

어느 컴퓨터든 CPU의 자원은 한정되어 있다. 때문에, 프로세스를 분배하는 방식에 따라, CPU utilization, throughput, turnaround time, waiting time, response time은 가지각색으로 변할 수 있다. 하지만, 단순히 성능만을 기준으로 삼기에는, 프로세스들간의 우선순위, starvation, fairness, dead line 등 고려해야할 사항이 많고, 우리는 이 한정된 CPU 자원을 실행되어야 하는 프로세스들에 가장 효율적으로 분배하는 법에 대해, 고민해볼 수 있을 것이다. 운영체제는 이 방식에 저마다의 알고리즘을 가지고 있다. 우리는 그 중, 리눅스는 어떤 스케줄러를 선택해 왔는지, 최신 스케줄러의 이론적 분석, 그리고 그 스케줄러를 사용하는 것이 다른 스케줄러에 비해 얼마나 합리적인 것인지 알아보겠다.

 

1. 리눅스 스케줄러의 역사

2.4 version의 리눅스 스케줄링 알고리즘은 O(N) scheduling algorithm이었다. 모든 프로세스 목록을 스캔해 가장 우선순위 높은 프로세스를, 단순히 epoch 시간단위로 프로세스를 실행하고, 해당 epoch를 다 사용하지 못하면, 다음 epoch의 시간을 늘여주는, traditional unix scheduling algorithm의 변형이었다. O(N)이라는 알고리즘의 이름처럼, 최선의 프로세스를 선택하는데 걸리는 시간이 프로세스의 수에 따라, 달라진다는 점이 큰 단점이었다. 때문에, 매우 많은 프로세스가 실행되는 시스템에서는 저조한 성능을 보였다.

이 후, 리눅스 커널은 프로세스의 수와 상관없이, 시간이 독립적으로 결정되는 O(1) scheduling algorithm을 사용하게 된다. O(1) algorithm은 runqueue를 사용하는 알고리즘이다. TASK_RUNNING 상태의 프로세스를 자신의 우선순위에 맞는 runqueue에 넣어주고, time-quantum의 사용 유무에 따라, active list, expired list를 사용해, 관리한다. Runqueue를 사용해, 전체 프로세스를 스캔하지 않고도, 다음 실행할 프로세스를 식별할 수 있기 때문에, 프로세스의 수와 독립적으로 O(1)의 실행 시간을 가질 수 있었다.

2.6.23 버전에서는 O(1) 알고리즘에서 더 향상된 Red-Black 트리를 사용한 Completely Fair Scheduler가 사용되게 되었고, 본 레포트에서는 2.6.23 버전부터 사용된, CFS 알고리즘을 기준으로 다루도록 하겠다.

 

2. 리눅스 스케줄러의 스케줄링 클래스

리눅스 스케줄러는 각 클래스 별로 특정 우선순위를 부여하는 스케줄링 클래스 자료구조를 사용한다. 가장 높은 우선순위 클래스의, 가장 높은 우선순위 프로세스가 다음에 실행되는 방식으로 동작한다 :

pick_next_task() 함수에서 가장 높은 우선 순위를 시작으로 for문을 통해 각 스케줄러 클래스를 거쳐, 최고 우선순위 클래스에서 최고 우선순위 프로세스를 선택하는 것을 확인할 수 있다.

 기본적인 linux는, non real-time scheduling을 위한 클래스 하나, real-time scheduling을 위한 클래스 두 개를 구현하게 된다. Non real-time scheduling을 위한 클래스에서는 CFS 알고리즘을 사용하고, 리눅스는 real-time scheduling 에 POSIX를 따르기 때문에, SCHED_FIFO와 SCHED_RR 두 개의 클래스를 구현한다.

 

3. Completely Fairness Scheduler의 time-sharing technique

CFS도 기본적으로 컴퓨터 자원을 시간적으로 분할해, 사용하는 time-sharing technique을 사용한다. 이 때, time slice로 이산 값이 아닌, 수행 가능한 모든 프로세스가 적어도 한 번씩 실행할 수 있는 시간 간격인 targeted latency를 사용하기 때문에, starvation이 일어나는 것을 방지할 수 있다.

CFS는 이 targeted latency를 우선순위에 기반해, 프로세스마다 각기 다른 비중의 CPU time을 분배해준다. 우선순위를 결정하는 데에는, 프로세스마다 할당된 Nice값을 기반으로 결정된다. Nice값이 작을수록 더 높은 우선순위를 가진 프로세스가 되는데, 단순히 이 Nice값만을 가지고 우선순위를 결정하지 않기 때문에, 더 정교한 fairness를 실현한다고 할 수 있다.

더 구체적으로, CFS는 nice값과 decay factor를 사용해, 실행 시간을 조정한 virtual runtime을 활용해, 스케줄링한다. 우선순위가 높을수록, 더 낮은 decay rate를 갖게 되고, 때문에 같은 실행 시간을 실행해도, 더 높은 우선 순위를 가진 프로세스가 더 적은 virtual runtime을 갖게 된다. 소스코드를 통해 알아보자 :

update_curr()는 현재 프로세스의 vruntime을 계산해주는 함수이다. 현재 프로세스의 runtime을 __update_curr()로 전달해주어, 가중치를 부가해, vruntime으로 만들어준다. 이 update_curr()은 타이머에 의해 정기적으로 실행되고, 프로세스가 실행 가능, 혹은 실행 불가능해질 때 마다 호출되어, 다음 실행되어야 할 프로세스를 나타내주는 정확한 지표가 된다.

 

4. Completely Fairness Scheduler의 process selection

 이렇게 계산된 virtual runtime은 read-black tree로 관리된다. 이 중, 가장 왼쪽 leaf, 즉, virtual runtime이 가장 작은 프로세스를 가장 불공정한 분배를 받았다 판단하고, 가장 우선적으로 다음에 실행하게 된다. 다음 실행할 프로세스를 선택하는 __pick_next_entity 함수를 보자 :

          이론적으로, Red-black tree는 balanced tree이기 때문에, 실제로 트리를 타고, left-most node를 찾는다면, O(log N)의 시간이 걸릴 것이다. 하지만, 소스코드에서 볼 수 있듯, 스케줄러는 rb_leftmost에 가장 작은 virtual runtime의 프로세스를 캐싱하고 있기 때문에, 다음 실행할 프로세스를 선택하는 것은 log(N) 보다 더 적은 시간이 걸린다.

같은 우선 순위를 갖더라도, 짧게 실행되고 blocking되는 I/O burst task의 특성 상, I/O burst task가 더 작은 virtual runtime을 갖게 될 것이고, 때문에 I/O burst task는 같은 우선 순위를 가진 CPU burst task를 선점하게 된다.

 

5. Completely Fairness Scheduler의 load balancing

CFS는 또한, processing core간의 부하를 균등하게 맞춰주는 load balancing 기술을 지원한다. 스레드의 우선 순위와 평균 CPU 이용률을 조합해, 각 스레드의 부하를 결정하고, 큐에 있는 모든 스레드 부하의 합이 큐마다 균등하도록 조정해주는 방식을 취한다. 평균 CPU 이용률을 조합하기 때문에, I/O burst thread는 적은 부하 측정치를 갖게 된다.

일반적인 load balancing의 단점은, 프로세스가 migration하며, 캐시가 무효화되거나, NUMA 시스템에서, memory access time이 길어질 수 있다는 것이다. 하지만, CFS는 스케줄링 도메인을 사용해, 해당 문제점을 최대한 피해준다. 스케줄링 도메인이란, 시스템 자원의 공유에 따라, 그룹화된 CPU 코어의 집합이다. 해당 집합은, 계층적으로 이루어져 있고, CFS는 가장 낮은 수준의 층부터 부하의 균형을 맞춰주는 전략을 취한다. 다른 processor level domain간에 migration하는 것을 꺼리며, 일반적으로, 전체 시스템이 바쁜 경우, 각 코어의 local domain을 벗어나 load balancing하지 않는다.

 

6. Real-time scheduling

Linux의 real-time scheduling은 앞서 언급한대로, 표준 POSIX를 따른다. POSIX는 real-time thread를 위해, SCHED_FIFO와 SCHED_RR 두 스케줄링 클래스를 정의한다. SCHED_FIFO는 FIFO queue를 사용해, 먼저 온 스레드를 먼저 처리해주는 스케줄링이다. FIFO queue의 가장 앞에 있는 우선순위가 가장 높은 스레드는 종료되거나, block될 때 까지 CPU를 할당받는다. SCHED_RR은 프로세스마다 time quantum을 분배해, CPU를 할당해주는 라운드 로빈 스케줄링을 사용한다.

Real-time scheduling은 non real-time scheduling과 달리, response time이나 fairness보다는 deadline을 지키는 것이 매우 중요하다. 때문에, real-time scheduling 클래스는 non-real-time scheduling 클래스보다 항상 더 높은 우선순위를 갖는다. 일반적으로 Linux는 Real-time task에 0-99의 우선순위를 부여해주고, normal task에는 100-139의 우선순위를 부여한다. 앞서, CFS에서 언급한, 우선순위를 결정하는 수치 중 하나인 nice값은 이 100-139 사이에서 결정되는 것이다. (ex, nice값이 -20이면 우선순위 100, 19면 우선순위 139에 mapping)

 

7. Comparison of O(1) and CFS

더 fairness에 대해 치중을 둔 목표대로, CFS는 정말로 O(1) 스케줄링보다 더 fairness할까? 그리고, CFS를 사용하는 것이 늘 O(1) 스케줄러를 사용하는 것보다 합리적일까?

IEEE의 Fairness and Interactive Performance of O(1) and CFS Linux Kernel Schedulers의 연구에서, children process와 소요 시간의 표준 편차가 CFS가 더 작은 것으로 보아, CFS 알고리즘은 당초 목표를 두었던 fairness한 CPU 분배에 확실한 성능차이가 있는 것으로 보인다. 이는, CFS의 모든 프로세스에 나노 세컨드 단위의 매우 정확하고, fairly하게 시간을 자르는 처리 방식의 결과라고 볼 수 있다. 이러한 특성에 따라, 시스템 관리자 입장에서, CFS는 O(1) 보다 더 나은 선택이다.

하지만, Oslo and Akershus university의  A Comparison of Two Linux Schedulers를 보아, CPU-bound와 Interactive bound process를 실행할 때, CFS가 O(1)에 비해, 더 긴 경과시간을 보낼 수 있음을 알 수 있다. 때문에, 그저 빨리 모든 작업을 처리하고 싶은 User의 입장에서 CFS가 항상 O(1)보다 좋은 선택이라고 할 수는 없을 것이다. 어느 한 스케줄러가 무조건 더 뛰어나다고 하기 보다, 사용자, 사용 목적에 따라, 더 적합한 스케줄러를 고르는 것이 합리적이다. 더 많은 시뮬레이션 결과와 각 workload에 대한 구체적인 evaluation은 참고문헌에 남긴다. [참고문헌 4,5]

 

참고문헌

1.      Abraham Silberschats, Greg Gagne, Peter B. Galvin. (2018). Operating System Concepts (10/E, pp. 199-239). US : Wiley.

2.      Daniel P.Bovet, Marco Cesati. (2005). Understanding the linux kernel (3/E, pp. 258-293). US: O’reilly media.

3.      Robert Love. (2010). Linux Kernel Development (3/E, pp. 41-67). US: Addison-Wesley.

4.      Gang Cheng. (2012). A Comparison of Two Linux Schedulers. Oslo and Akershus University, Oslo.

5.      C.S. Wong, I.K.T. Tan, R.D. Kumari, J.W. Lam. (2008). Fairness and Interactive Performance of O(1) and CFS Linux Kernel Schedulers. NY: Institute of Electrical and Electronics Engineers.