리눅스 커널의 Completely Fair Scheduler(CFS)는 공정성을 유지하면서도 처리량을 극대화하기 위해 어떤 핵심적인 원리들을 적용하고 있습니까? 특히, `vruntime`과 레드-블랙 트리를 활용한 스케줄링 큐 관점에서 CFS의 동작 방식을 심층적으로 설명해 주십시오.

Completely Fair Scheduler(CFS)는 공정성과 처리량 극대화를 위해 몇 가지 핵심 원리를 사용합니다. 가장 중요한 것은 vruntime이라는 가상 실행 시간 개념입니다. 각 태스크는 CPU를 사용한 시간에 비례하여 vruntime이 증가하는데, 이 값이 작을수록 더 높은 스케줄링 우선순위를 갖습니다.

CFS는 모든 태스크를 레드-블랙 트리에 저장하여 스케줄링 큐를 관리합니다. 레드-블랙 트리는 균형 잡힌 트리 구조이므로, vruntime이 가장 작은 태스크(즉, 다음에 실행될 태스크)를 O(log n) 시간 안에 효율적으로 찾을 수 있습니다.

스케줄러는 항상 레드-블랙 트리에서 가장 왼쪽 노드(가장 작은 vruntime을 가진 태스크)를 선택하여 실행합니다. 태스크가 실행되면 vruntime이 증가하고, 다시 레드-블랙 트리에 삽입되어 자신의 위치를 찾습니다. 이러한 과정을 통해 CFS는 모든 태스크에게 공정한 CPU 시간을 할당하면서도 전체 시스템의 처리량을 높입니다. CFS는 나노초 단위의 정밀도로 작동하여 매우 세밀한 스케줄링이 가능합니다.