리눅스 완전 공정 스케줄러(CFS: Completely Fair Scheduler)

CFS

리눅스의 완전 공정 스케줄러(CFS: Completely Fair Scheduler)는 리눅스 커널 2.6.23(2007년)에서 도입된 프로세스 스케줄링 알고리즘입니다. 기존의 O(1) 스케줄러를 대체하여 시스템의 CPU를 프로세스에 보다 공정하게 분배하는 것을 목표로 설계되었습니다.

CFS의 주요 특징

1. 공정성 보장
   • CFS는 "공정"함을 강조하며, 각 프로세스가 실제로 소비한 CPU 시간을 기준으로 스케줄링합니다.
   • 모든 프로세스가 가상 런타임(Virtual Runtime) 값을 가지며, CPU를 더 많이 사용한 프로세스는 가상 런타임이 증가합니다. CFS는 가상 런타임이 가장 낮은 프로세스를 우선적으로 실행하여 공정성을 유지합니다.
2. RB-Tree 자료구조 사용
   • CFS는 레드-블랙 트리(Red-Black Tree)라는 자료구조를 사용하여 실행 가능한 태스크를 관리합니다.
   • 레드-블랙 트리는 균형 이진 탐색 트리로, 삽입, 삭제, 탐색 연산이 O(log n)의 시간 복잡도를 가집니다.
   • 트리에서 가장 작은 가상 런타임 값을 가진 프로세스가 루트에 위치하며, 이를 기준으로 다음에 실행될 프로세스를 빠르게 결정합니다.
3. 가상 런타임 (vruntime)
   • CFS는 vruntime(가상 런타임) 값을 사용하여 프로세스의 CPU 사용량을 추적합니다.
   • vruntime은 CPU를 소비할 때마다 증가하며, 프로세스의 우선순위(nice 값)에 따라 증가 속도가 조정됩니다. 예를 들어, 높은 우선순위(nice 값이 낮음)를 가진 프로세스는 vruntime이 더 천천히 증가합니다.
4. 우선순위 관리
   • CFS는 프로세스의 우선순위를 반영하여 공정성을 동적으로 조정합니다. 우선순위가 높은 프로세스는 더 많은 CPU 시간을 받을 수 있습니다.
   • 우선순위는 nice 값을 통해 조정할 수 있으며, -20(가장 높은 우선순위)에서 19(가장 낮은 우선순위)까지 범위가 있습니다.
     ※ nice 값은 리눅스와 유닉스 계열 운영체제에서 프로세스의 우선순위(priority)를 조정하는 데 사용되는 값입니다. 이 값은 프로세스가 CPU를 얼마나 자주 사용할 수 있는지를 간접적으로 결정합니다.
5. 타임 슬라이스 제거
   • CFS는 기존 스케줄링 방식에서 사용되던 고정된 타임 슬라이스 개념을 없애고, 대신 프로세스가 CPU를 얼마나 사용했는지에 따라 실행을 제어합니다.

CFS의 동작 원리

1. 프로세스 준비
   • 실행 가능한 프로세스들은 레드-블랙 트리에 삽입되며, 각 프로세스의 vruntime 값이 저장됩니다.
2. 스케줄링 결정
   • 레드-블랙 트리의 루트 노드에 위치한 프로세스(가장 작은 vruntime 값)가 다음에 실행됩니다.
3. CPU 실행 및 vruntime 업데이트
   • 실행 중인 프로세스의 vruntime 값은 CPU 사용량에 따라 증가합니다.
   • 특정 조건(예: CPU 시간 초과, I/O 요청 등)에서 프로세스가 중단되면 다시 트리에 삽입됩니다.
4. 반복
   • CFS는 지속적으로 트리의 루트 노드를 기준으로 실행 대상을 결정합니다.

CFS의 장점

1. 높은 공정성
   • CPU 시간을 균등하게 분배하며, 특정 프로세스가 과도하게 CPU를 독점하지 않도록 설계되었습니다.
2. 효율적 스케줄링
   • 레드-블랙 트리를 사용하여 O(log n)의 시간 복잡도로 프로세스 관리가 가능합니다.
3. 동적 우선순위 조정
   • 프로세스의 우선순위를 동적으로 반영하여 유연성을 제공합니다.

CFS의 단점

1. 실시간 태스크 처리 제한
   • CFS는 공정성을 기반으로 하기 때문에, 실시간 태스크의 요구를 만족시키기 어려운 경우가 있습니다.
   • 리눅스에서는 이러한 문제를 보완하기 위해 별도의 실시간 스케줄링 클래스를 제공합니다.
2. 높은 오버헤드
   • O(log n)의 시간 복잡도는 프로세스가 많아질수록 스케줄링 오버헤드가 증가할 가능성이 있습니다.

nice

nice 값은 리눅스 및 유닉스 계열 운영체제에서 프로세스의 우선순위를 조정하는 데 사용되는 값입니다. 이를 통해 특정 프로세스가 CPU를 더 많이 또는 더 적게 사용할 수 있도록 조정할 수 있습니다.

• nice 값은 리눅스에서 프로세스의 우선순위를 조정하는 값입니다.
• nice 값이 낮을수록(예: -20) 우선순위가 높아져 CPU를 더 많이 사용할 수 있습니다.
• nice 값이 높을수록(예: 19) 우선순위가 낮아져 CPU 사용량이 줄어듭니다.
• CFS에서는 nice 값에 따라 가상 런타임(vruntime) 증가 속도를 조정하여 공정한 CPU 분배를 수행합니다.

1. nice 값의 기본 개념

• nice 값은 -20(가장 높은 우선순위)부터 19(가장 낮은 우선순위)까지 범위를 가집니다.
• 기본적으로 모든 프로세스의 nice 값은 0으로 설정됩니다.
• 값이 낮을수록(예: -10, -20) 더 높은 우선순위를 가지며, CPU 시간을 더 많이 할당받습니다.
• 값이 높을수록(예: 10, 19) 우선순위가 낮아지며, CPU를 덜 사용하게 됩니다.

2. nice 값과 CFS의 관계

CFS(Completely Fair Scheduler)는 nice 값을 사용하여 가상 런타임(vruntime) 증가 속도를 조정합니다.
즉, nice 값이 낮은(우선순위가 높은) 프로세스는 vruntime이 더 천천히 증가하고, 높은(우선순위가 낮은) 프로세스는 vruntime이 더 빠르게 증가합니다.

• 예제:
  • P1 (nice = 0) → 기본 우선순위, vruntime 증가 속도 보통
  • P2 (nice = 10) → 낮은 우선순위, vruntime 증가 속도 빠름 → P1보다 적은 CPU 시간 할당

즉, nice 값이 낮은 프로세스는 CPU를 더 오래 사용할 수 있고, 높은 프로세스는 CPU를 덜 사용할 수 있습니다.

3. nice 값 확인 및 변경 방법

(1) 현재 실행 중인 프로세스의 nice 값 확인

ps -eo pid,comm,nice

위 명령을 실행하면 프로세스 ID(PID), 명령어(COMM), 그리고 nice 값을 확인할 수 있습니다.

(2) 새로운 프로세스를 특정 nice 값으로 실행

nice -n 10 ./my_program

위 명령어는 my_program을 nice 값 10으로 실행합니다.

(3) 실행 중인 프로세스의 nice 값 변경

renice -n -5 -p 1234

위 명령어는 PID가 1234인 프로세스의 nice 값을 -5로 변경하여 우선순위를 높입니다.
(단, 낮은 nice 값을 설정하려면 root 권한이 필요합니다.)

4. nice 값과 우선순위의 관계

리눅스 커널은 nice 값과 내부 우선순위(priority)를 다르게 관리합니다.

• 스케줄링 우선순위(priority) 계산 공식

  priority = 20 + nice 값

  • 예제:
    • nice = 0 → priority = 20 (기본값)
    • nice = -10 → priority = 10 (우선순위 높음)
    • nice = 10 → priority = 30 (우선순위 낮음)

즉, nice 값이 낮을수록 프로세스의 스케줄링 우선순위가 높아지며, CPU를 더 많이 할당받습니다.

vruntime

CFS(Completely Fair Scheduler)는 전통적인 스케줄링 알고리즘과 달리 고정된 디폴트 시간(타임 슬라이스) 개념을 사용하지 않습니다. 대신, 각 스레드가 공정하게 CPU를 사용할 수 있도록 가상 런타임(vruntime)에 따라 동적으로 스케줄링합니다.

그러나, 실질적으로 CPU를 사용할 수 있는 시간은 다음과 같은 요인에 의해 결정됩니다:

1. CFS 타겟 라틴시(Target Latency)

• CFS 타겟 라틴시는 모든 실행 가능한 태스크들이 한 번씩 CPU를 사용하기 위해 필요한 최대 시간입니다.
• 기본적으로 이 값은 리눅스 커널에서 설정되며, /proc/sys/kernel/sched_latency_ns 파일에서 확인하거나 조정할 수 있습니다.
  • 기본 값: 20ms (10개의 태스크가 있다고 가정하면, 각 태스크는 약 2ms를 사용)
• 타겟 라틴시는 실행 가능한 프로세스 수가 적으면 늘어나고, 많으면 줄어듭니다.

2. CFS 최소 그랜룰러티(Minimum Granularity)

• 각 태스크가 CPU를 사용할 수 있는 최소 시간은 최소 그랜룰러티로 제한됩니다.
• /proc/sys/kernel/sched_min_granularity_ns 파일에서 확인할 수 있으며, 기본 값은 약 1ms입니다.
• 실행 가능한 태스크 수가 너무 많아도 각 태스크가 최소한 1ms는 CPU를 사용할 수 있도록 보장합니다.

3. 실제 CPU 사용 시간 계산

CFS가 스레드의 CPU 사용 시간을 결정하는 기본 원리는 다음과 같습니다:

1. Target Latency를 실행 가능한 태스크 수로 나눔
   • 예: 타겟 라틴시가 20ms이고 실행 가능한 태스크가 5개라면, 각 태스크는 약 4ms씩 CPU를 사용할 수 있습니다.
2. 우선순위(nice 값)에 따라 조정
   • 스레드의 nice 값이 낮을수록 더 많은 CPU 시간을 할당받으며, 높은 nice 값은 적은 시간을 받습니다.
   • CPU 사용 시간은 nice 값에 기반하여 동적으로 가중치를 조정합니다.

 

디폴트 시간 예제

• 타겟 라틴시: 20ms
• 실행 가능한 태스크 수: 4개
• nice 값이 같음:
  • 각 태스크는 20ms ÷ 4 = 5ms씩 CPU를 사용.
• nice 값이 다름:
  • P1: nice = 0 (기본 우선순위, 더 많은 시간)
  • P2: nice = 10 (낮은 우선순위, 적은 시간)
  • P1은 P2보다 더 많은 CPU 시간을 받으며, 정확한 비율은 커널의 weight 계산에 따라 결정.

예시: nice 값과 vruntime

• 두 프로세스가 실행 중이라고 가정:
  • P1: nice = 0 (기본 우선순위)
  • P2: nice = 10 (낮은 우선순위)
• CFS는 P1의 vruntime을 더 천천히 증가시키므로, P1이 더 많은 CPU 시간을 받게 됩니다.

 

CFS에서 스레드가 CPU를 사용할 수 있는 "디폴트 시간"은 고정된 값이 아닌, 시스템의 타겟 라틴시, 최소 그랜룰러티, 실행 가능한 태스크 수, 그리고 우선순위(nice 값)에 따라 동적으로 조정됩니다.

이를 통해, 각 스레드가 공정하게 CPU를 사용할 수 있도록 보장하며, 시스템 환경에 따라 유연하게 변화합니다.