24. CPU Scheduling(4)

안녕하세요. 저번 포스팅에서는 multicore 스케쥴링 방식에 대해 알아보았습니다. 오늘은 조금 더 깊게 Linux 스케쥴링에 대해 알아볼까 합니다. 

 

24.01. Linux CFS(Completely Fiar Scheduler)

Linux 스케쥴러는 오랫동안 발전을 해왔습니다. 현재는 상당히 안정적이고 공평한 스케쥴러가 있는데요. CFS입니다. Multi queue 개념을 적용하여 starvation없이 작동하는데요. 프로세스의 수에 따라 period를 계산(Default : 24ms, # of process * 3ms)합니다. Time slice는 weight로 계산하는데요. 여기서 weight는 priority입니다. 각 프로세스가 얼마의 time period를 가지는지 나오고 동일한 ratio면 단순하게 1/n이 되겠죠.(Based on its load weight : default 1024)

 

Time slice = period * (process wight / weight sum of # process)

 

프로세스의 execution time을 측정합니다. 우선순위는 vruntime을 계산하여 accumulation합니다. 우선순위가 높으면 process weight가 높은 것이고 그러면 vruntime이 줄어듭니다.(즉, 실제로 실행한 시간보다 더 적게 실행했으니 더 실행해야 한다고 주장하는거죠.) 따라서 적게 수행되거나 높은 우선순위를 가진 프로세스가 수행될 확률이 높아집니다. 

 

vruntime += execution time

 

이렇게 예측된 vruntime이 time slice를 초과하면 preempted됩니다. 즉, 스케쥴러는 lowest vruntime을 가진 프로세스를 선택합니다.(High weight > small vruntime)

 

간단하게 알아보았는데 CFS의 목표는 무엇일까요?

Interactive한 것은 빨리 처리해주고 오래 수행된 job들은 우선순위를 떨어뜨려 vruntime을 증가시킵니다. 선택할 가능성을 감소시키는거죠. Multiqueue 스케쥴러에서는 여러 개의 queue를 만들어 사용하는 개념이였다면 CFS는 간단한 수식으로 알고리즘화 한 것이라고 생각하시면 됩니다. Time slice를 도입한 것은 다른 스케쥴러와 유사하고 차이점은 time slice를 조정가능하게 했다는 점, selection criteria에 있어서 vruntime이라는 변수가 priority에 연동되게 했다는 것이 있습니다. 

 

Multiqueue 스케쥴러와 유사하다고 하였는데 장점은요?

프로세스가 많아지면 queue를 sorting하는데 시간이 많이 걸릴 것입니다. CFS는 red-black tree라는 것을 사용해서 insertion time과 deletion time을 단축할 수 있습니다.

 

왜 RB tree일까요?

흔히 자료구조 과목에서 배우는 AVL tree와 비교해주자면 사실 두 tree모두 삽입과 삭제, 검색 시 O(log N)의 시간이 소요되는 것은 같습니다. 하지만 AVL tree는 tree의 balance를 좀 더 엄격하게 유지하기 때문에 탐색에 유리하고 RB tress는 balancing을 느슨하게 하기 때문에 삽입과 삭제에 유리합니다. 조금 더 자세히 rebalancing 과정을 비교해보자면 AVL tree같은 경우 삽입할 때 parent node를 차례대로 비교하며 rebalancing 하는 과정이 포함되기 때문에 최악과 평균의 경우 O(log N)의 시간복잡도를 지니지만 RB tree의 경우 color가 추가되었기 때문에 무조건 tree를 rotation하는 것이 아니라 color만 바꾸는 방법 등으로 느슨하게 rebalacing을 하므로 tree의 rotation 횟수가 감소합니다. 따라서 RB tree는 삽이 한번당 실제로 구현할 때 2-3 tree와 같이 color pionter만 바꾸어 O(1)인 경우도 있고 AVL tree와 같이 재귀를 사용하지 않아도 되어 CPU의 오버헤드가 적기 때문에 일반적으로 많이 사용합니다.(이보다 더 자세한 내용은 자료구조 과목에서 배우시게 될 겁니다.)

 

 

24.02. Linux Scheduling의 과거

예전 version에 대한 스케쥴링이 어땟는지도 한번 살펴보겠습니다. 컴퓨터공학 과목에서 역사를 톺아보는 것은 상당히 재미난 일입니다. 현재 사용하는 기술이 갑자기 하늘에서 뚝 떨어진게 아닌 만큼 과거 기술에 대한 이해는 현재 기술에 대한 이해를 높여주기 때문입니다.(비교대상으로 존재가치가 충분합니다.)

 

Kernel version 2.5이전에는 UNIX 스케쥴링 알고리즘의 변형을 사용하면서 SMP 시스템을 위한 적절한 지원을 제공하진 않았습니다. Task 수가 증가하면 성능이 저하되었습니다.(O(N) 알고리즘이였습니다.) Kernel version 2.5와 2.6에서는 O(1) 스케쥴링 time이였는데 앞서 task 수에 영향을 받았던 version 2.5에 비해 발전한 것입니다. 또 지난 포스팅에서 설명한 프로세스 친화도, 부하균등화 기능을 포함하여 SMP에 대한 지원이 높아졌습니다. 선점형, 우선순위 기반 스케쥴링 이였고 우선순위에는 두개의 영역이 있었습니다. Real-time과 Time sharing 영역이였는데요. 한번쯤 들어보셨을 nice value(100~140)가 바로 time sharing 영역의 value 입니다.(참고로 다른 OS와 달리 우선순위가 높을수록 큰 time quantum을 부여했습니다.) 

 

24.02.1. Version 2.5 & 2.6

Version 2.5와 2.6의 스케쥴링을 조금 더 자세히 설명하고 넘어가겠습니다.

Epoch 기반 스케쥴링으로 time slice가 남아있으면 task는 실행가능(active)했고 남아있지 않으면 다른 task가 time slice를 모두 사용할 때까지 실행을 할 수 없었습니다(expired). 모든 runnable tasks는 per-CPU runqueu data structure로 관리하였고요. 우선순위를 index로 사용하여 active array가 참조되었고 active task가 없으면 active와 expired array를 서로 교환하였습니다.

여기서도 단점을 살펴봐야겠죠. 무엇이 단점이였을까요?

물론 잘 동작하는 스케쥴링입니다만 interactive 프로세스의 응답시간이 느리다는 것이 단점입니다.

 

 

24.03. Version 2.623+

이제부터 완전 공평 스케쥴러라고 이름붙여진 CFS가 적용되었습니다. Nice value에 따라서 CPU 시간 비율을 결정하였는데요. 두개의 스케쥴링 class를 두었습니다. Default는 CFS 스케쥴링을 사용하였고 real-time class가 더 있습니다.

 

Time quantum은 -20 ~ +19 범위를 가지는 nice value를 기반으로 계산하는데요. Target latency를 계산하여 모든 수행 가능한 task가 최소 한번 실행될 수 있는 시간간격을 설정하고 CPU 자원을 할당합니다.(물론 target latenct도 default 값과 최소값을 가지고 active task가 일정 수준 이상이라면 target latency가 증가할 수 있습니다. Target latency를 통해 starvation도 방지할 수 있습니다.)

 

또 앞서 설명드린대로 CFS 스케쥴러는 task별로 virtual run time을 관리하는데요. vruntime이라는 변수를 사용하여 task의 우선순위에 따라 decay factor를 결정합니다.(우선순위가 높을수록 가상 실행시간이 실제 실행시간보다 작아집니다.) Ready state의 task들은 bruntime을 key value로 하여 red-black tree로 관리하여 O(log N) 시간복잡도로 빠른 탐색을 제공합니다.

정리하자면 CFS는 nice value와 decay factor를 사용해 virtual runtime을 조정하고 virtual runtime을 사용해 스케쥴링을 합니다. 조금 더 깊게 들어가자면 vruntime이 red-black tree로 관리될 때 가장 작은 virtual runtime의 프로세스를 caching하고 있어 log(N)보다 더 작은 시간으로 다음 실행할 프로세스를 선택합니다. 또 같은 우선순위를 갖더라도 1번의 실행시간이 짧은 I/O burst task의 특성으로 더 작은 virtual runtime을 I/O burst task가 갖게 되고 같은 우선순위를 갖는 CPU burst task를 선점하게 됩니다.

 

24.03.1. Load balancing

CFS는 core간 load balancing도 지원하는데요. Thread의 우선순위와 평균 CPU 사용률을 이용해 각 스레드의 부하를 결정합니다. 그 후 queue에 담긴 스레드 부하 합이 queue마다 균등하도록 조정합니다. 저번 포스팅에서도 말씀드렸듯이 load balancing은 프로세스 migration, cache invalidation가 발생하는데요. CFS는 시스템 자원의 공유에 따라 그룹화된 CPU core의 집합을 사용해 그런 단점을 최소화합니다.(다른 level domain간 migration을 최소화합니다.) 또한 시스템이 busy한 경우, 각 core의 local domain을 벗어나 load balancing을 하지 않습니다.

 

24.03.2. Fairness and Interactive Performance of O(1) and CFS

IEEE에 게제된 하나의 논문을 소개해드릴까 합니다. CFS가 기존 알고리즘에 비해 CPU 자원 분배에 있어 공평한 분배가 이루어 졌는지에 대한 분석입니다. Linux 스케쥴러의 비교에 관한 논문은 꽤 있는 편이니 직접 찾아보시는 것도 재미가 있을 것 같습니다.

새 창에서 열기

 

 

오늘은 Linux의 스케쥴링에 대해 알아보았습니다. 특히 CFS를 중점으로 알아보았는데요. Reference마다 다르지만 스케쥴링 작업이 CPU 실행 시간의 약 5%를 차지한다고 하니 효율적인 스케쥴러는 중요한 topic입니다. 물론 공평한 스케쥴러 또한 중요한 topic입니다. 또한 아주아주 공부할 내용이 많고 생각해볼 issue들도 많이 던져주는 topic이라서 저도 포스팅하면서 재미있었던 주제였습니다. 물론 복학 전 갈길이 멀어 이정도만 정리를 하고 넘어갑니다만 시간이 되면 작은 프로젝트로 참신한 idea를 내기 좋은 주제인 것 같습니다.(물론 다른 분들이 많이 연구해놓으셨겠죠.) 실제 code와 관련해서는 여러분께 reference를 하나 특별히 추천드리고자 합니다. http://rousalome.egloos.com/ 입니다.(kernel/sched_fair.c와 linux/sched.h에 정의된 struct sched_entity code를 한번 뜯어보는 것도 재미난 시간이 될 것 같습니다.) 제 포스팅이 여러분의 지식의 탑에 조금이나마 보탬이 되었으면 좋겠고 질문과 오류지적은 언제나 환영이니 댓글로 남겨주시면 감사하겠습니다.