리눅스는 어떤 CPU 스케쥴링 알고리즘을 사용할까?

---

1. 왜 이걸 알아야 할까?

• 백엔드 서버, 컨테이너, 마이크로서비스를 운영할 때 시스템이 느려지는 원인을 파악하려면 CPU가 어떻게 태스크를 선택해서 실행하는지 알아야한다.
• top, htop, pidstat, pref 등 시스템 모니터링 도구에서 나오는 load average, context switch, CPU 사용률은 결국 스케줄링 알고리즘의 결정 결과값이다.
• 멀티스레딩, 병렬처리, 비동기 서버 개발 시 스케줄링 정책의 특성을 모르면 CPU 낭비, starvation, 성능 저하 발생이 이어진다.

📌 즉, CPU 알고리즘은 성능 디버깅, 병렬 시스템 설계, 실시간 서비스 운영을 위해 꼭 알아야 한다.

---

2. 어떤 알고리즘이 있고, 리눅스에는 어떤걸 쓸까?

이해의 출발을 위해 고전 알고리즘을 알아보자

알고리즘	특징
FCFS (First-Come First-Served)	단순하지만 비효율적, Convoy 효과 발생
SJF (Shortest Job First)	이론상 최적이지만, 실행 시간 예측 어려움
Round Robin	시분할 시스템의 기본, 일정 시간마다 태스크 전환
Priority Scheduling	우선순위에 따라 실행, starvation 가능

그래서 리눅스의 알고리즘은?

리눅스 우분투에서는 기본적으로 CFS(Completely Fair Scheduler)를 사용한다. 이는 Round Robin + Weight 기반 Priority Scheduling을 조합한 현대적 알고리즘이다.

음… 말이 어렵고 잘 와닿지 않는다… 완전히 공정한 스케줄러라는거 같다. 도대체 뭐가 공정하고 어떻게 스케줄링하는지 알아보자

---

3. CFS(Completely Fair Scheduler)란?

리눅스 커널 2.6.23부터 기본 스케줄러로 채택된 CPU 스케줄러이며 Round Robin처럼 번갈아 주지만, 사용한 시간(vruntime)을 고려해서 덜 쓴 놈에게 먼저 기회를 주는 구조
즉, 공정하게 CPU를 나눠 쓰도록 만드는 알고리즘이다.

왜 만들어 졌을까?

기존의 스케줄러들은 문제점이 많았다고 한다.

• Round Robin: 모든 프로세스에 똑같은 시간 주는데, 작업량 차이가 커도 무시해버림
• Priority Scheduler: 높은 우선순위가 낮은 우선순위를 굶기기도 함(starvation)
• O(1) Scheduler: 매우 빠르지만 비선형적인 스케줄러 동작과 CPU 사용률 편향 문제
  그래서 등장한게 CFS라고 합니다.

공정하게 동작하는 과정

가상 실행 시간 vruntime을 통해 파악하고 균형을 맞춥니다.

• 모든 태스크는 CPU를 사용한 시간이 저장됩니다. → vruntime
• 이 값이 작은 프로세스일 수록 CPU를 적게 썻다는 뜻입니다. → 우선 실행 대상
• 즉, CPU를 적게 쓴 프로레스를 먼저 실행 시켜서 균형을 맞추는 겁니다.

📌 “CPU 사용량을 추적하고, 가장 적게 사용한 놈부터 돌려준다”

태스크 관리는 어떻게 할까?

• 모든 태스크는 vruntime 기준으로 Red-Black Tree에 정렬됩니다.
• 루트 노드 = 가장 vruntime이 작은 태스크 → 이걸 먼저 실행
• 실행되면 vruntime이 늘어나고, 다시 트리 재정렬 되며 위 과정을 반복합니다.
  
  키워드: Red-Black Tree

Time Slice가 없습니다??!

기존 Round Robin은 “10ms씩 돌아가자” 식이었는데, CFS는 그런 고정 time slice 개념이 없습니다.
대신:

• sched_latency_ns: 전체 프로세스가 한 바퀴 도는데 걸리는 총 시간
• min_granularity_ns: 한 태스크가 최소로 보장받는 실행 시간

CFS는 이 값을 기준으로 동적으로 태스크를 교체합니다.

조정 가능한 CFS 파라미터

파일	의미
/proc/sys/kernel/sched_latency_ns	전체 태스크가 한 번씩 실행되는 주기 (기본: 6ms)
/proc/sys/kernel/sched_min_granularity_ns	한 태스크가 최소 실행할 시간 (기본: 750µs)
nice 값	우선순위 가중치 (vruntime 계산 시 반영됨)

예시: CFS 동작 방식

프로세스 3개: A, B, C

• A: CPU-bound(연산 많은)
• B: I/O-bound(대기 많음)
• C: 중간 정도

CFS는 A가 CPU를 오래 쓰면 vruntime이 빨리 증가하고
→ B, C는 상대적으로 vruntime이 작아져 우선 배정됨

실전 명령어

ps -eo pid,ni,psr,cmd --sort=ni  # nice 우선순위 확인

---

4. CPU, I/O bound에 적합한 스케줄러 무엇인가?

이런 고민을 해볼 것이다.

CFS는 둘중에 어디에 적합하다고 생각하는지 고민해보자
vrutime 이 적은 값이고 자주 태스크가 스위칭 되면 vruntime이 작아질것이다.
.
.
.
.
.
그렇다면 I/O bound이다, 비동기나 외부 자원 대기, API 요청 등 Waiting 상태가 많은 작업에 적합하다.
즉, 짧고 자주 실행되는 작업이 유리하다.
그래서 CFS는 I/O-bound 태스크를 더 자주, 더 빨리 실행시키는 구조로 되어있다.

어떻게 판단할 수 있을까?

리눅스 기준 명령어

명령어	설명
top, htop	CPU 사용률, 상태 (R: Running / S: Sleeping 등)
pidstat -p 1	특정 프로세스의 사용자/시스템 CPU 사용률
iostat -xz 1	디스크 I/O 대기율 확인
vmstat 1	us, sy, wa → CPU, 시스템, 대기 비율 분석

📌 "wa"(IO Wait)가 높으면 I/O-bound 프로세스가 많은 것

📌 us(User CPU)가 높으면 CPU-bound 작업이 많다는 뜻

반대로 CPU-bound는?

Real-Time Priority 기반 스케줄링으로 실시간 우선순위 기반인 스케줄러를 이용하는 것이다.

---

추가적으로 공부해볼것들

• Convoy 효과
• Red-Black Tree