L
Task A: vruntime 12ms
트리의 가장 왼쪽 노드다. CPU를 가장 적게 쓴 것으로 보고 먼저 선택한다.
런큐 안의 vruntime 정렬
M
Task B: vruntime 20ms
A가 실행되어 vruntime이 증가하면 다음 후보가 될 수 있다.
R
Task C: vruntime 28ms
이미 더 많이 실행된 태스크라 오른쪽에 머무른다.
선택 루프
1
가장 작은 vruntime 선택
레드-블랙 트리의 왼쪽 끝 노드를 캐시해 두므로 다음 태스크 선택은 빠르게 끝난다.
2
실행한 만큼 vruntime 증가
nice 값이 낮은 고우선순위 태스크는 vruntime이 천천히 증가해 더 자주 선택된다.
3
증가한 태스크를 다시 삽입
삽입과 삭제는 O(log n)이고, 태스크는 새 vruntime 위치로 이동한다.
pick leftmost → run slice → update vruntime → reinsert