CFS Scheduler

1. OVERVIEW

CFS는 "Complete Fair Scheduler"의 약자로, Ingo Molnar에 의해 구현되고 Linux 2.6.23에서 병합된 새로운 "데스크탑" 프로세스 스케줄러입니다. 이전 바닐라 스케줄러의 SCHED_OTHER 상호작용 코드를 대체합니다.

CFS 설계의 80%는 한 문장으로 요약할 수 있습니다. CFS는 기본적으로 실제 하드웨어에서 "이상적이고 정밀한 멀티태스킹 CPU"를 모델링합니다.

"이상적인 멀티태스킹 CPU"는 (존재하지 않는 :-) CPU로 100%의 물리적 파워를 가지며, 각 태스크를 정확하게 동일한 속도로, 병렬로, 각각 1/nr_running speed 로 실행할 수 있습니다. 예를 들어, 실행 중인 태스크가 2개라면 각각 50%의 물리적 파워로, 즉 실제로 병렬로 실행됩니다.

실제 하드웨어에서는 한 번에 하나의 태스크만 실행할 수 있으므로 "가상 런타임"이라는 개념을 도입해야 합니다. 태스크의 가상 런타임은 다음 타임슬라이스가 위에서 설명한 이상적인 멀티태스킹 CPU에서 실행을 시작하는 시점을 지정합니다. 실제로 태스크의 가상 런타임은 실행 중인 태스크의 총 수에 정규화된 실제 런타임입니다.

 

2. FEW IMPLEMENTATION DETAILS

CFS에서 가상 런타임은 태스크 단위 p->se.vruntime(nanosec-unit) 값을 통해 표현되고 추적됩니다. 이렇게 하면 태스크가 얻어야 할 "예상 CPU 시간"을 정확하게 타임스탬프하고 측정할 수 있습니다.

작은 세부사항: "이상적인" 하드웨어에서 모든 작업은 언제든지 동일한 p->se.vruntime 값을 가질 것입니다. 즉, 작업은 동시에 실행되고 CPU 시간의 "이상적인" 공유에서 "균형에서 벗어나는" 작업은 없을 것입니다.

CFS의 태스크 피킹 로직은 이 p->se.vruntime 값을 기반으로 하므로 매우 간단합니다. 즉, 항상 가장 작은 p->se.vruntime 값으로 태스크를 실행하려고 합니다. CFS는 항상 실행 가능한 태스크 간에 "이상적인 멀티태스킹 하드웨어"에 가깝게 CPU 시간을 나누려고 합니다.

CFS의 나머지 대부분의 디자인은 정말 단순한 개념에서 벗어나 있습니다. 훌륭한 수준, 다중 처리 및 수면자를 인식하기 위한 다양한 알고리즘 변형과 같은 몇 가지 추가 장식이 있습니다.

 

3. THE RBTREE

CFS의 설계는 상당히 급진적입니다: 실행 대기열에 기존 데이터 구조를 사용하지 않지만 시간 순서의 rb트리를 사용하여 향후 작업 실행의 "타임라인"을 구축하므로 "어레이 스위치" 아티팩트(이전 바닐라 스케줄러와 RSDL/SD 모두 영향을 받는)가 없습니다.

또한 CFS는 rq->cfs.min_vruntime 값을 유지하는데, 이 값은 rq->cfs.min_vruntime 값은 런큐의 모든 작업 중에서 가장 작은 vruntime을 추적하는 단조 증가 값입니다. 시스템에서 수행한 총 작업량은 min_vruntime을 사용하여 추적되며, 이 값은 트리의 왼쪽에 새로 활성화된 엔티티를 최대한 배치하는 데 사용됩니다.

런큐에서 실행 중인 작업의 총 수는 rq->cfs.load 값을 통해 설명되며, 이 값은 런큐에서 대기 중인 작업의 가중치의 합입니다.

CFS는 모든 실행 가능한 태스크가 p->se.vruntime 키로 정렬되는 시간 순서의 rbtree를 유지합니다. CFS는 이 트리에서 "가장 왼쪽" 태스크를 선택하고 이 태스크를 고수합니다. 시스템이 진행됨에 따라 실행된 태스크는 점점 더 오른쪽으로 트리에 추가됩니다. 천천히 그러나 확실히 모든 태스크가 "가장 왼쪽" 태스크가 되어 결정적인 시간 내에 CPU에 오를 수 있는 기회를 제공합니다.

요약하면, CFS는 다음과 같이 작동합니다. 태스크를 약간 실행하고 태스크 스케줄(또는 스케줄러 틱이 발생하면) 태스크의 CPU 사용량이 "계정"됩니다. 물리적 CPU를 사용한 지 얼마 되지 않은 (작은) 시간이 p->se.vruntime에 추가됩니다. p->se.vruntime이 충분히 높아지면 다른 태스크가 시간 순서가 지정된 rbtree의 "가장 왼쪽 태스크"가 되고(게다가 태스크를 과도하게 스케줄링하고 캐시를 낭비하지 않도록 가장 왼쪽 태스크에 대한 작은 양의 "과립성" 거리), 새로운 가장 왼쪽 태스크가 선택되고 현재 태스크가 선점됩니다.

 

4. SOME FEATURES OF CFS

CFS는 나노초 세분화 회계를 사용하며, 어떤 지피나 다른 HZ 디테일에도 의존하지 않습니다. 따라서 CFS 스케줄러는 이전 스케줄러가 그랬던 것처럼 "타임슬라이스"라는 개념이 없으며, 휴리스틱도 전혀 없습니다. 중앙 조정 변수는 하나뿐입니다(CONFIG_SCHED_DEBUG을 켜야 합니다):

 

/sys/kernel/debug/sched/base_slice_ns

 

스케줄러를 "데스크탑"에서 "서버"(즉, 좋은 배치) 워크로드로 조정하는 데 사용할 수 있습니다. 기본적으로 데스크톱 워크로드에 적합한 설정으로 설정됩니다. SCHED_BATCH는 CFS 스케줄러 모듈에서도 처리됩니다.

설계상 CFS 스케줄러는 50pc, thud.c, chew.c, ring-test.c, massive_intr.c 모두 정상적으로 작동하며 상호작용성에 영향을 주지 않으며 예상 동작을 생성합니다.

CFS 스케줄러는 이전 바닐라 스케줄러보다 훨씬 강력한 수준 및 SCHED_BATCH를 처리합니다. 두 종류의 워크로드가 모두 훨씬 더 공격적으로 분리됩니다.

SMP 로드 밸런싱이 재작업/위생화되었습니다. 이제 로드 밸런싱 코드에서 런큐 워킹 가정이 사라지고 스케줄링 모듈의 반복기가 사용됩니다. 그 결과 밸런싱 코드가 상당히 간단해졌습니다.

 

5. Scheduling policies

CFS는 세 가지 스케줄링 정책을 구현합니다:

• SCHED_NORMAL (traditionally called SCHED_OTHER): The scheduling policy that is used for regular tasks.
• SCHED_BATCH: Does not preempt nearly as often as regular tasks would, thereby allowing tasks to run longer and make better use of caches but at the cost of interactivity. This is well suited for batch jobs.
• SCHED_IDLE: This is even weaker than nice 19, but its not a true idle timer scheduler in order to avoid to get into priority inversion problems which would deadlock the machine.

SCHED_FIFO/_RR은 sched/rt.c로 구현되며 POSIX에서 지정한 대로입니다.
util-linux-ng 2.13.1.1.1의 명령어 chrt는 SCHED_IDLE을 제외한 모든 것을 설정할 수 있습니다.

 

6. SCHEDULING CLASSES

새로운 CFS 스케줄러는 스케줄러 모듈의 확장 가능한 계층인 "Scheduling Classes(스케줄링 클래스)"를 도입하는 방식으로 설계되었습니다. 이 모듈들은 스케줄링 정책 세부사항을 캡슐화하고 너무 많은 것을 가정하지 않고 스케줄러 코어에 의해 처리됩니다.

sched/fair.c는 위에서 설명한 CFS 스케줄러를 구현합니다.

sched/rt.c는 이전 바닐라 스케줄러보다 더 간단한 방식으로 SCHED_FIFO 및 SCHED_RR 시맨틱스를 구현합니다. 이전 스케줄러의 140개 대신 100개의 RT 우선 순위 레벨에 대해 100개의 런큐를 사용하며 만료된 배열이 필요하지 않습니다.

스케줄링 클래스는 sched_class 구조를 통해 구현되며, 이 구조는 흥미로운 이벤트가 발생할 때마다 호출해야 하는 함수에 대한 후크를 포함합니다.

 

This is the (partial) list of the hooks:

• enqueue_task(...)
• Called when a task enters a runnable state. It puts the scheduling entity (task) into the red-black tree and increments the nr_running variable.
• dequeue_task(...)
• When a task is no longer runnable, this function is called to keep the corresponding scheduling entity out of the red-black tree. It decrements the nr_running variable.
• yield_task(...)
• This function is basically just a dequeue followed by an enqueue, unless the compat_yield sysctl is turned on; in that case, it places the scheduling entity at the right-most end of the red-black tree.
• check_preempt_curr(...)
• This function checks if a task that entered the runnable state should preempt the currently running task.
• pick_next_task(...)
• This function chooses the most appropriate task eligible to run next.
• set_curr_task(...)
• This function is called when a task changes its scheduling class or changes its task group.
• task_tick(...)
• This function is mostly called from time tick functions; it might lead to process switch. This drives the running preemption.

 

7. GROUP SCHEDULER EXTENSIONS TO CFS

일반적으로 스케줄러는 개별 태스크에 대해 동작하며, 각 태스크에 공정한 CPU 시간을 제공하기 위해 노력합니다. 때로는 태스크를 그룹화하여 이러한 태스크 그룹 각각에 공정한 CPU 시간을 제공하는 것이 바람직할 수 있습니다. 일 예로, 시스템 상의 각 사용자에게 먼저 공정한 CPU 시간을 제공한 후 사용자에게 속한 각 태스크에게 공정한 CPU 시간을 제공하는 것이 바람직할 수 있습니다.

CONFIG_CGROUP_SCHED는 이를 정확히 달성하기 위해 노력합니다. 작업을 그룹화하고 이러한 그룹 간에 CPU 시간을 공평하게 분배합니다.

CONFIG_RT_GROUP_SCHED는 실시간(즉, SCHED_FIFO 및 SCHED_RR) 태스크를 그룹화할 수 있습니다.

CONFIG_FAIR_GROUP_SCHED는 CFS(즉, SCHED_NORMAL 및 SCHED_BATCH) 작업을 그룹화할 수 있도록 허용합니다.

이러한 옵션은 CONFIG_CGROUP을 정의해야 하며 관리자가 "cgroup" 의사 파일 시스템을 사용하여 임의의 작업 그룹을 만들 수 있습니다. 이 파일 시스템에 대한 자세한 내용은 제어 그룹을 참조하십시오.

CONFIG_FAIR_GROUP_SCHED가 정의되면 의사 파일 시스템을 사용하여 생성된 각 그룹에 대해 "cpu.shares" 파일이 생성됩니다. "cgroups" 의사 파일 시스템을 사용하여 작업 그룹을 생성하고 CPU 공유를 수정하려면 다음의 예시 단계를 참조하십시오:

# mount -t tmpfs cgroup_root /sys/fs/cgroup
# mkdir /sys/fs/cgroup/cpu
# mount -t cgroup -ocpu none /sys/fs/cgroup/cpu
# cd /sys/fs/cgroup/cpu

# mkdir multimedia      # create "multimedia" group of tasks
# mkdir browser         # create "browser" group of tasks

# #Configure the multimedia group to receive twice the CPU bandwidth
# #that of browser group

# echo 2048 > multimedia/cpu.shares
# echo 1024 > browser/cpu.shares

# firefox &     # Launch firefox and move it to "browser" group
# echo <firefox_pid> > browser/tasks

# #Launch gmplayer (or your favourite movie player)
# echo <movie_player_pid> > multimedia/tasks

 

참고문헌

CFS Scheduler — The Linux Kernel documentation