CFS(Completely Fair Scheduler)

CFS(Completely Fair Scheduler)란?

CFS(Completely Fair Scheduler)는 Linux 커널에서 사용되는 기본 프로세스 스케줄러입니다. CFS는 CPU 시간을 여러 프로세스에 공정하게 분배하도록 설계된 스케줄링 알고리즘입니다. Linux 커널 2.6.23 버전부터 기본 스케줄러로 채택되었습니다.

---

CFS의 주요 특징

1. 공정성(Fairness)

   • 모든 프로세스가 동일한 우선순위를 가진 경우, CPU 시간을 가능한 공평하게 나누도록 설계되었습니다.
   • 프로세스가 사용한 CPU 시간을 추적하며, 더 적게 사용한 프로세스에게 CPU를 우선 할당합니다.

2. 가상 런타임(Virtual Runtime)

   • 각 프로세스마다 가상 런타임(Vruntime) 값을 유지합니다.
   • vruntime은 프로세스가 사용한 CPU 시간과 우선순위에 따라 증가합니다.
   • 프로세스가 CPU를 사용하면 vruntime이 증가하며, 가장 작은 vruntime을 가진 프로세스가 실행됩니다.

3. Red-Black Tree 자료구조

   • CFS는 Red-Black Tree(균형 이진 탐색 트리)를 사용하여 프로세스를 관리합니다.
   • 트리의 각 노드는 실행 가능한 프로세스를 나타내며, vruntime 값으로 정렬됩니다.
   • O(log N)의 시간 복잡도로 가장 적게 실행된 프로세스를 선택할 수 있습니다.

4. 비선점형 기반

   • CFS는 기본적으로 비선점형(non-preemptive) 방식으로 작동하며, 각 프로세스는 일정한 시간 동안 실행됩니다.
   • 하지만 sched_yield와 같은 시스템 호출로 선점할 수도 있습니다.

5. 우선순위 지원

   • 프로세스의 우선순위를 고려하여 vruntime 증가 속도를 조정합니다.
   • 우선순위가 높은 프로세스는 더 적은 vruntime 증가를 가지므로 더 자주 CPU를 할당받습니다.

---

CFS의 동작 원리

1. 프로세스 추가

   • 새로운 프로세스가 실행 대기열에 들어오면, 해당 프로세스의 vruntime 값이 초기화됩니다.
   • Red-Black Tree의 적절한 위치에 삽입됩니다.

2. 스케줄링 결정

   • 트리의 루트(최소 vruntime을 가진 프로세스)가 선택되어 실행됩니다.

3. 실행 후 업데이트

   • 실행 중인 프로세스의 vruntime이 증가하며, 이를 기준으로 다시 Red-Black Tree에서 위치가 재조정됩니다.

4. 시간 분배

   • 실행 가능한 프로세스가 많을수록 각 프로세스에 할당되는 CPU 시간은 줄어듭니다.
   • 프로세스 수에 따라 동적으로 시간 쿼텀이 조정됩니다.

---

CFS의 주요 파라미터

1. sched_latency_ns

   • 모든 프로세스가 한 번씩 실행되기까지 걸리는 시간(대기 시간)을 정의. 기본값은 6ms.

2. sched_min_granularity_ns

   • 프로세스에 최소한 할당되는 CPU 시간. 기본값은 1ms.
   • 실행 가능한 프로세스가 많아도, 최소한 이 값은 보장됩니다.

3. nice 값

   • 프로세스의 우선순위를 정의. 기본값은 0이며, 범위는 -20(높음) ~ +19(낮음).
   • 낮은 nice 값은 높은 우선순위를 의미합니다.

---

CFS의 장점

1. 공정한 스케줄링

   • 모든 프로세스가 균등한 CPU 시간을 받을 수 있습니다.

2. 효율적인 시간 분배

   • Red-Black Tree를 사용하여 스케줄링 작업이 효율적으로 처리됩니다.

3. 다양한 워크로드 지원

   • CPU 바운드 및 I/O 바운드 작업 모두를 효율적으로 처리합니다.

---

CFS의 단점

1. 완벽한 공정성은 어려움

   • I/O 바운드 프로세스는 CPU를 적게 사용하므로 vruntime이 적게 증가해, CPU를 더 자주 사용할 수 있습니다. 이는 완벽한 공정성에 도전이 됩니다.

2. 복잡성 증가

   • Red-Black Tree 사용으로 인해 기존의 간단한 FIFO 방식에 비해 복잡합니다.

---

CFS와 다른 스케줄링 알고리즘 비교

특징	CFS	FIFO(First In, First Out)	RR(Round Robin)
공정성	높은 공정성	공정하지 않음	프로세스 간 공정성 유지
우선순위 지원	지원	지원	지원
효율성	Red-Black Tree로 효율적 관리	단순한 구조, 효율적	낮은 효율성
시간 복잡도	O(log N)	O(1)	O(1)

---

CFS의 사용 사례

• 데스크탑 환경:

  • 다양한 프로세스가 동시에 실행되는 일반 사용자 환경에서 공정하게 CPU 자원을 나누기 위해 사용.

• 서버 환경:

  • 여러 서비스가 동시에 실행되며, 모든 서비스가 일정한 성능을 보장받아야 할 때.

• 실시간 시스템이 아닌 환경:

  • 특정 프로세스가 정해진 시간에 반드시 실행되어야 하는 실시간 시스템에는 적합하지 않음.

---

요약

CFS는 모든 프로세스가 공정하게 CPU를 사용하도록 설계된 Linux의 기본 스케줄링 알고리즘입니다. vruntime을 기반으로 Red-Black Tree에서 가장 적게 실행된 프로세스를 선택해 실행하며, 효율적이고 공정한 스케줄링을 보장합니다.