Scheduler · Linux 6.18.37 LTS · source + diagram note

load balancing

최신 LTS 기준: kernel.org longterm 6.18.37 기준으로 파일 위치와 링크를 맞춘 원본 코드 분석 노트입니다. sched domain, cpu capacity, migration.

전체 흐름

CPU 사이의 runnable load와 capacity를 비교하고, 실제로 옮길 수 있는 task가 있을 때만 이동한다. v6.18.37에서는 주기적 softirq, NOHZ idle balancing, 새로 idle이 된 CPU의 pull을 먼저 구분해야 한다. 세 경로가 매번 한 줄로 이어지는 것은 아니다.

판단 단위

sched_domain의 주기와 lb_env의 목적지·후보 CPU 집합·imbalance를 함께 본다.

종료도 결과

balance를 시도해도 후보 group/rq가 없거나 affinity 때문에 이동량이 0일 수 있다. 이때도 interval·통계·상위 domain 처리 조건을 확인한다.

그림 1. v6.18.37의 세 진입 경로
경로진입 및 조건이어지는 처리
주기적sched_balance_trigger가 기한을 확인해 SCHED_SOFTIRQ 요청sched_balance_softirq; NOHZ 선행 처리에서 반환하지 않으면 일반 domain 순회
NOHZ원격 tick의 idle-balance kick이 softirq 처리로 연결nohz_idle_balance가 처리하면 그 자리에서 반환; false이면 일반 경로
새로 idlesched_balance_newidle가 pending wakeup·overload·비용·domain 조건을 확인조건을 통과한 domain에서 sched_balance_rq(..., CPU_NEWLY_IDLE, ...) 호출

진입 분류는 fair.c:12970–13059, 13114–13155를 따른다. NOHZ의 내부 작업과 new-idle pull은 서로 별도 경로다.

소스 코드 위치

먼저 확인할 Linux 6.18.37 LTS 소스 파일

원본 코드:
Linux 6.18.37 LTS: kernel/sched/fair.c
Linux 6.18.37 LTS: kernel/sched/topology.c
Linux 6.18.37 LTS: kernel/sched/sched.h

설명: fair.c의 sched_balance_softirq, sched_balance_newidle, sched_balance_domains, sched_balance_rq를 따라 분기와 종료를 확인한다. topology.c와 sched.h는 sched domain 구성과 구조체를 보조 확인할 때 연다.

v6.6과 v6.18.37의 대응 지점

이름이 비슷한 함수의 목적은 비교할 수 있지만 두 버전의 조건과 내부 분기를 같은 코드로 취급하지 않는다. v6.6 글과 각 버전의 공식 v6.6 fair.c·보존 v6.18.37 fair.c를 함께 대조한다.

단계v6.6v6.18.37
주기적 요청·softirqtrigger_load_balance · run_rebalance_domainssched_balance_trigger · sched_balance_softirq
새로 idle인 CPUnewidle_balancesched_balance_newidle
source 선택과 이동load_balance · find_busiest_group · find_busiest_queuesched_balance_rq · sched_balance_find_src_group · sched_balance_find_src_rq

대표 코드

이전 카드의 두 제목은 구버전 함수명이고, 붙은 코드는 함수 본문이 아니었다. 아래는 로컬에 고정된 Linux v6.18.37 kernel/sched/fair.c에서 복사한 연속 범위다.

sched_balance_rq

원본 코드: kernel/sched/fair.c 11947–11975행 (함수 시작 11920행)
redo:
	if (!should_we_balance(&env)) {
		*continue_balancing = 0;
		goto out_balanced;
	}

	if (!need_unlock && (sd->flags & SD_SERIALIZE)) {
		int zero = 0;
		if (!atomic_try_cmpxchg_acquire(&sched_balance_running, &zero, 1))
			goto out_balanced;

		need_unlock = true;
	}

	group = sched_balance_find_src_group(&env);
	if (!group) {
		schedstat_inc(sd->lb_nobusyg[idle]);
		goto out_balanced;
	}

	busiest = sched_balance_find_src_rq(&env, group);
	if (!busiest) {
		schedstat_inc(sd->lb_nobusyq[idle]);
		goto out_balanced;
	}

	WARN_ON_ONCE(busiest == env.dst_rq);

	update_lb_imbalance_stat(&env, sd, idle);

읽는 법: should_we_balance가 거부하면 domain의 계속 여부를 바꾸고 balanced 출구로 간다. source group 또는 source rq가 없을 때도 migration으로 진행하지 않는다. 후보 rq를 찾은 다음에야 imbalance 통계와 이동 조건을 본다.

sched_balance_find_src_group

원본 코드: kernel/sched/fair.c 11464–11485행
static struct sched_group *sched_balance_find_src_group(struct lb_env *env)
{
	struct sg_lb_stats *local, *busiest;
	struct sd_lb_stats sds;

	init_sd_lb_stats(&sds);

	/*
	 * Compute the various statistics relevant for load balancing at
	 * this level.
	 */
	update_sd_lb_stats(env, &sds);

	/* There is no busy sibling group to pull tasks from */
	if (!sds.busiest)
		goto out_balanced;

	busiest = &sds.busiest_stat;

	/* Misfit tasks should be dealt with regardless of the avg load */
	if (busiest->group_type == group_misfit_task)
		goto force_balance;
같은 함수의 반환 분기: 11589–11597행
force_balance:
	/* Looks like there is an imbalance. Compute it */
	calculate_imbalance(env, &sds);
	return env->imbalance ? sds.busiest : NULL;

out_balanced:
	env->imbalance = 0;
	return NULL;
}

읽는 법: domain 통계로 source group 후보를 찾고 imbalance를 계산한다. 후보가 없거나 계산 결과가 0이면 NULL이다. misfit 등은 평균 load만으로 판단하지 않는 별도 분기가 있다.

함수별 분석

정상 이동만 따라가면 NOHZ의 조기 반환과 후보 없음·affinity 제한을 놓친다. 그림은 주요 판단만 요약하며 상세 domain 순회, pinned 재시도, active balancing은 원문 분기를 따른다.

그림 2. 진입 경로와 source 후보·이동 판단
주기적 및 NOHZ softirq와 별도 new-idle 진입, source group과 rq 선택, 이동 없음 또는 detach·attach 분기를 표시한 Linux v6.18.37 결정도

NOHZ가 처리되어 nohz_idle_balance가 true를 반환하면 일반 domain 경로는 실행하지 않는다. 새로 idle 경로는 softirq를 반드시 거치지 않는다.

1. softirq의 선행 NOHZ 처리

sched_balance_softirq는 NOHZ work를 먼저 확인한다. 처리 완료(true)면 즉시 반환하고, false일 때만 blocked average 갱신 후 sched_balance_domains로 간다 (fair.c:13122–13140).

2. 새로 idle인 CPU의 별도 pull

sched_balance_newidle은 pending wakeup, active CPU, overloaded root domain, 예상 비용, SD_BALANCE_NEWIDLE을 확인한다. 해당 domain을 실제로 시도할 때 CPU_NEWLY_IDLE로 sched_balance_rq를 호출한다 (fair.c:12970–13059).

3. source와 이동량 판단

sched_balance_rq는 담당 CPU인지 확인한 뒤 source group과 rq를 찾는다. 후보가 없으면 balanced 출구로 가며, 후보가 있어도 detach_tasks가 0개를 반환하면 attach_tasks는 호출하지 않는다. affinity로 모두 막힌 경우나 active balancing은 별도 분기다 (fair.c:11947–12015, 12062–12143).

판단조건결과
NOHZ 선행 처리nohz_idle_balance가 truesoftirq에서 반환; 일반 domain 순회 없음
domain 방문balance interval 도래해당 domain의 sched_balance_rq 시도
source group / rq후보 없음 또는 imbalance 0migration 없이 balanced 출구
pull 가능한 taskcur_ld_moved > 0detach된 task를 목적지 rq에 attach

구조체와 필드

아래는 호출 순서가 아니라 한 번의 balance 판단에서 함께 쓰는 객체다. domain 범위와 CPU capacity, lb_env의 source·destination, 각 CPU의 rq 상태를 구분한다.

그림 3. 각 객체의 역할과 판단
객체담당 정보원문에서 확인할 조건
sched_domainCPU 묶음, flag, balance 간격for_each_domain과 SD_BALANCE_NEWIDLE
sched_group / capacity그룹의 load·capacity 비교sched_balance_find_src_group의 busy/imbalanced/misfit 판단
lb_envdst/src rq, 후보 CPU mask, imbalance, 이동 제약should_we_balance와 LBF_ALL_PINNED
rqCPU별 runnable 상태source rq 선택과 detach_tasks 결과

네 객체는 순서대로 생성되는 단계가 아니다. fair.c:11464–11596, 11602–11685, 11920–12015.

실행 단계와 상태 변화

후보를 찾았다는 사실과 task를 실제 이동했다는 결과를 분리해 읽는다. 각 출구는 실패 복구가 아니라 이 반복에서 내린 유효한 판단일 수 있다.

그림 4. 같은 balance 시도의 가능한 결과
출구조건 예시관찰 결과
일반 경로 미진입NOHZ 선행 처리 후 true 반환해당 softirq의 일반 domain 순회 생략
balanced담당 CPU 아님, group/rq 후보 없음task 이동 없이 종료
pinned / 0개 이동affinity 또는 이동 가능한 task 없음재시도·상위 domain·active 경로는 별도 조건에 따름
이동detach_tasks가 양수 반환attach_tasks 실행

fair.c:11947–12015, 12062–12143, 13122–13140. 위 표는 모든 내부 분기를 열거하지 않는다.

source 후보 있음 ≠ 이동 완료; cur_ld_moved > 0일 때만 detach 결과를 attach한다.

불변 조건과 실패 사례

담당 CPU

should_we_balance는 active CPU mask와 domain의 선택 규칙을 확인한다. 새로 idle인 경우에도 이미 runnable task나 pending wakeup이 있으면 pull을 건너뛴다.

group 비교

평균 load 하나로만 결정하지 않는다. capacity, group type, misfit, local/busiest 비교와 계산된 imbalance가 source group 반환을 좌우한다.

affinity

source rq를 찾았어도 pull할 task가 전부 pinned일 수 있다. 이 경우 다른 source CPU를 시험하거나 상위 domain에 imbalance를 남기는 경로가 있다.

이동 완료

detach_tasks의 반환이 양수일 때만 attach_tasks한다. 0개 이동과 조기 반환을 성공적 migration으로 계산하지 않는다.

주의

NOHZ softirq 처리와 new-idle pull을 매번 이어지는 호출 사슬로 읽지 않는다.

주의

source group 발견만으로 affinity와 capacity 제약이 해소된 것으로 보지 않는다.

계측과 검증

계측은 printk 위치 경쟁이 아니라 가설 검증이다. 먼저 위 상태표에서 멈춘 state를 정하고, 그 state를 바꾸는 함수와 그 결과를 소비하는 함수를 동시에 본다.

로그가 찍힌 위치를 완료 시점으로 단정하지 말고, 바로 앞뒤 필드 변경을 원본에서 확인.

도구보는 것
sched_migrate_task실제로 task가 CPU를 옮긴 사건을 확인한다. 후보 없음이나 0개 이동은 이 사건만으로 설명되지 않는다.
perf sched mapCPU별 실행 이력을 보고 이동 결과를 대조한다. 내부 imbalance 계산은 별도 통계·함수 추적이 필요하다.
/proc/sched_debug구성에서 제공할 때 rq와 domain 상태를 확인한다. 존재 여부와 내용은 커널 설정에 좌우된다.
schedstat lb_count / lb_nobusyg / lb_nobusyq / lb_failed시도, source 후보 없음, 이동 실패를 각각 구분한다 (fair.c:11945–12092; schedstats가 켜진 구성에서 확인).
기본 추적 경로:
# 예시: tracefs가 켜진 보드에서 토픽별 event를 좁혀 본다.
mount -t tracefs nodev /sys/kernel/tracing
echo function_graph > /sys/kernel/tracing/current_tracer
echo ':mod:*' > /sys/kernel/tracing/set_ftrace_filter
cat /sys/kernel/tracing/trace_pipe

추가 확인 사항

  • load balancing 의 state machine을 네 단계로 줄였을 때, 실제 코드에서 빠지는 intermediate state는 무엇인가?
  • load balancing 의 fast path가 생략한 검사는 어느 init path 또는 slow path에서 보증되는가?
  • 실험으로 확인한다면 '평균 load만 보고 capacity를 무시함' 문제를 어떤 tracepoint와 counter로 분리할 수 있는가?
  • 실험으로 확인한다면 'task affinity와 cpuset 제약을 늦게 확인함' 문제를 어떤 tracepoint와 counter로 분리할 수 있는가?