CFS는 가상 실행 시간으로 공정성을 근사한다

Linux CFS는 고정 time slice 대신 vruntime이 가장 작은 작업을 고릅니다. nice 값은 vruntime 증가 속도를 바꿉니다.

A
12ms B
20ms C
28ms
CPU
A + 6ms
A
18ms B
20ms C
28ms
01

실행 시간을 가상화한다

실제 실행 시간에 가중치를 반영해 vruntime을 늘리고 작업별 CPU 몫을 비교합니다.

vruntime
02

가장 작은 값 선택

red-black tree의 왼쪽에 있는, 가장 적게 실행된 작업을 다음 실행 후보로 고릅니다.

pick next
03

가중치를 반영한다

nice 값이 낮은 작업은 더 큰 CPU 몫을 받도록 vruntime 증가가 다르게 계산됩니다.

weight
04

지연 목표를 조정한다

sched_latency와 min_granularity는 공정성과 문맥 전환 비용 사이 균형을 잡습니다.

latency
vruntime
공정성 판단용 누적 실행 시간 작을수록 CPU를 덜 받은 것으로 보아 먼저 실행될 가능성이 큽니다.
fairness
RB tree
다음 작업을 빠르게 찾기 위한 정렬 구조 vruntime 기준으로 작업을 정렬해 왼쪽 끝을 선택합니다.
structure
nice
사용자가 CPU 몫의 상대 우선순위를 조정 절대적인 강제 순서가 아니라 가중치 기반 몫에 가깝습니다.
weight