Gidhub BE Developer

CFS 스케줄러

2018-10-07
goodGid
OS

CFS 스케줄러란?

  • 스케줄러는 CPU 자원을 프로세스들에게 분배하는 OS의 중요한 일부분이다.

  • 2007년 발표 된 리눅스 커널스케줄러인 CFS(Completely Fiar Scheduler)
    RSDL(Rotating Staircase Deadline) 스케줄러를 기초로 한 RB-트리(Red-Black Tree) 데이터 구조를 사용하는 O(logN) 성능을 가지는 스케줄러이다.

  • CFS는 시간단위나노초를 사용한다.

특징

공평한 CPU 시간

  • 만약 A, B 두 개의 태스크가 진행되고 있다면 A와 B의 CPU 사용시간은 항상 1:1로 같아야한다.

  • 그러나 두 태스크가 번갈아 가며 수행되므로 임의의 시점에 두 태스크의 CPU 사용 시간이 항상 1:1로 같을 수 없다.

  • 따라서 CFS는 정해진 ‘시간 단위’로 봤을때 시스템에 존재하는 태스크들에게 공평한 CPU 시간을 할당하는 것을 목표로 한다.

  • 만약 1초를 ‘시간 단위’로 한다면 0.5초 동안 A 태스크를 수행시키고, 그런 뒤 0.5초간 B 태스크를 수행시킴으로써 1초가 지난 이후 A와 B의 CPU 사용시간이 1:1이 되도록 하는 것이다.

  • CFS의 기본 개념은 작업에 프로세서 시간을 제공할 때 밸런스(공평성)를 유지하는 것이다.

  • 즉 프로세스에 공평한 양의 프로세서(=CPU)가 제공되어야 한다.

  • 작업 시간의 밸런스가 무너진 경우에는(다른 작업에 비해 하나 이상의 작업에 공평한 양의 시간이 주어지지 않은 경우) 작업 시간이 적게 지정된 작업에 실행 시간이 주어져야 한다.


가상 런타임

  • CFS에서는 밸런스를 결정하기 위해 가상 런타임이라는 지정된 작업에 제공된 시간의 양을 관리한다.

  • 작업의 가상 런타임이 작을수록 즉, 프로세서에 액세스할 수 있도록 허용된 시간이 작은 작업일수록 더 많은 프로세서 시간이 필요하다.


대기자 공평성

  • 또한 CFS에는 대기자 공평성이라는 개념도 포함되어 있다.

  • 이 개념은 현재 실행할 수 없는 작업(예를 들어, I/O를 대기 중인 작업)이 나중에 프로세서가 필요할 때 대기했던 시간에 상응하는 프로세서 시간을 받을 수 있도록 보장한다.


RB-트리

  • 하지만 CFS는 이전 Linux 스케줄러와는 달리 실행 큐에서 작업관리하지 않고 시간순으로 정렬된 RB-트리를 유지한다.

  • Red-Black 트리에는 흥미롭고 유용한 두 가지 특성이 있다.

  • 첫 번째는 스스로 밸런스조절한다는 것이다.

  • 즉, 이 트리의 모든 경로는 다른 경로보다 두 배 이상 길어지지 않는다.

  • 두 번째는 트리에 대한 작업O(log n) 시간(여기서 n는 트리의 노드 수임) 내에 발생한다는 것이다.

  • 따라서 작업을 빠르고 효율적으로 삽입하거나 삭제할 수 있다.


참고


Comments

Content