sched_ext 확장형 scheduler

sched_ext의 목적과 복구 특성

sched_ext는 BPF program 집합으로 scheduling 동작을 정의할 수 있는 scheduler class다. BPF scheduler가 사용할 전체 scheduling interface를 노출하므로 임의의 알고리즘을 구현할 수 있다.

task는 wakeup 순간 특정 CPU에 영구 결박되지 않으므로 BPF scheduler가 CPU를 원하는 방식으로 묶고 함께 schedule할 수 있다. scheduler는 runtime에 동적으로 load하거나 unload할 수 있다.

잘못된 BPF scheduler가 system integrity를 무너뜨리지 않도록 내부 오류, runnable task stall 또는 SysRq-S가 감지되면 sched_ext를 중단하고 기본 fair-class scheduling을 복원한다.

BPF scheduler error가 발생하면 scheduler userspace binary가 debug dump를 받아 출력한다. 같은 dump는 sched_ext_dump tracepoint에서도 읽을 수 있다. SysRq-D는 scheduler를 종료하지 않고 dump만 trigger하며, 이 경우 tracepoint를 통해서만 읽는다.

sched_ext 활성화와 상태 확인

CONFIG_SCHED_CLASS_EXT가 sched_ext를 활성화하며 example scheduler는 tools/sched_ext에 있다. BPF syscall, JIT, BTF와 pahole 기능을 함께 켠다.

CONFIG_BPF=y
CONFIG_SCHED_CLASS_EXT=y
CONFIG_BPF_SYSCALL=y
CONFIG_BPF_JIT=y
CONFIG_DEBUG_INFO_BTF=y
CONFIG_BPF_JIT_ALWAYS_ON=y
CONFIG_BPF_JIT_DEFAULT_ON=y
CONFIG_PAHOLE_HAS_SPLIT_BTF=y
CONFIG_PAHOLE_HAS_BTF_TAG=y

BPF scheduler가 load되어 실행 중일 때만 sched_ext를 사용한다. 그 전에 task가 policy를 SCHED_EXT로 명시해도 SCHED_NORMAL처럼 fair class가 schedule한다.

BPF scheduler가 load되고 ops->flags에 SCX_OPS_SWITCH_PARTIAL이 없으면 SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE, SCHED_EXT task 모두 sched_ext로 전환된다. flag가 있으면 policy가 명시적으로 SCHED_EXT인 task만 sched_ext가 처리하고 나머지는 fair class에 남는다.

scheduler process 종료, SysRq-S, 내부 오류 또는 runnable task stall은 BPF scheduler를 abort하고 모든 task를 fair class로 되돌린다. example scheduler는 다음처럼 build하고 실행한다.

# make -j16 -C tools/sched_ext
# tools/sched_ext/build/bin/scx_simple
local=0 global=3
local=5 global=24
local=9 global=44
local=13 global=56
local=17 global=72
^CEXIT: BPF scheduler unregistered

/sys/kernel/sched_ext/state는 현재 enable 상태를, root/ops는 active ops 이름을 보여 준다. enable_seq는 boot 이후 BPF scheduler가 load될 때마다 증가하므로 0이면 한 번도 load되지 않은 것이다.

# cat /sys/kernel/sched_ext/state
enabled
# cat /sys/kernel/sched_ext/root/ops
simple
# cat /sys/kernel/sched_ext/enable_seq
1

tools/sched_ext/scx_show_state.py는 drgn으로 ops, enabled, switching_all, switched_all, enable_state, bypass_depth, rejected count와 sequence를 표시한다. 특정 task의 /proc/<pid>/sched에서 ext.enabled가 1인지 확인하면 sched_ext 적용 여부를 알 수 있다.

# tools/sched_ext/scx_show_state.py
ops           : simple
enabled       : 1
switching_all : 1
switched_all  : 1
enable_state  : enabled (2)
bypass_depth  : 0
nr_rejected   : 0
enable_seq    : 1

# grep ext /proc/self/sched
ext.enabled                                  :                    1

최소 BPF scheduler와 struct sched_ext_ops

userspace loader는 struct sched_ext_ops를 구현하는 BPF program 집합을 load한다. mandatory field는 유효한 BPF object 이름인 ops.name뿐이고 모든 operation callback은 optional이다.

아래 코드는 tools/sched_ext/scx_simple.bpf.c에서 가져온 최소 global FIFO scheduler다. simple_select_cpu()는 기본 select_cpu와 동일하게 idle CPU candidate를 찾는다. direct가 true면 선택한 CPU의 SCX_DSQ_LOCAL에 task를 바로 넣고 enqueue callback을 건너뛴다. verifier가 모든 path에서 초기화된 값을 요구하므로 direct=false로 초기화한다.

s32 BPF_STRUCT_OPS(simple_select_cpu, struct task_struct *p,
                   s32 prev_cpu, u64 wake_flags)
{
	s32 cpu;
	/* 초기화하지 않으면 BPF verifier가 거부 */
	bool direct = false;

	cpu = scx_bpf_select_cpu_dfl(p, prev_cpu, wake_flags, &direct);
	if (direct)
		scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, SCX_SLICE_DFL, 0);
	return cpu;
}

idle core direct insertion에 실패한 task만 simple_enqueue()로 온다. 이 callback은 task를 SCX_DSQ_GLOBAL FIFO에 넣는다. 기본 enqueue도 같은 동작을 하므로 callback을 생략해도 결과는 같다.

void BPF_STRUCT_OPS(simple_enqueue, struct task_struct *p, u64 enq_flags)
{
	scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL, SCX_SLICE_DFL, enq_flags);
}

s32 BPF_STRUCT_OPS_SLEEPABLE(simple_init)
{
	return 0;
}

void BPF_STRUCT_OPS(simple_exit, struct scx_exit_info *ei)
{
	exit_type = ei->type;
}

SEC(".struct_ops")
struct sched_ext_ops simple_ops = {
	.select_cpu = (void *)simple_select_cpu,
	.enqueue    = (void *)simple_enqueue,
	.init       = (void *)simple_init,
	.exit       = (void *)simple_exit,
	.name       = "simple",
};

simple_init()이 0을 반환하고 partial switch flag를 지정하지 않으므로 SCHED_EXT뿐 아니라 SCHED_OTHER, SCHED_IDLE, SCHED_BATCH task도 sched_ext를 사용한다. simple_exit()은 scx_exit_info의 종료 종류를 userspace reporting용 변수에 남긴다.

Dispatch Queue

sched_ext는 scheduler core와 BPF scheduler 사이의 실행 task 전달을 DSQ(dispatch queue)로 연결한다. DSQ는 FIFO와 priority queue로 동작할 수 있다. 기본으로 system 전체 SCX_DSQ_GLOBAL FIFO 하나와 CPU마다 SCX_DSQ_LOCAL이 하나씩 있다.

BPF scheduler는 scx_bpf_create_dsq()/scx_bpf_destroy_dsq()로 custom DSQ를 원하는 수만큼 관리할 수 있다. CPU는 항상 자신의 local DSQ에서 task를 실행한다. task를 queue에 넣는 operation은 insert이고, non-local DSQ의 task를 특정 CPU local DSQ로 옮기는 것은 move다.

CPU가 다음 task를 찾을 때 local DSQ가 비어 있지 않으면 첫 task를 고른다. 비어 있으면 global DSQ에서 local로 move를 시도하고, 거기에도 runnable task가 없을 때 ops.dispatch()를 호출한다.

wakeup부터 실행까지 scheduling cycle

task wakeup에서 첫 callback은 ops.select_cpu()다. CPU 선택 optimization hint와 idle CPU wakeup이라는 두 역할을 한다. 반환 CPU는 강제 binding이 아니며 최종 실행 CPU는 scheduling 마지막 단계에서 결정된다. 다만 hint와 최종 CPU가 같으면 migration 비용을 줄일 수 있다.

BPF scheduler는 scx_bpf_kick_cpu()로 임의 CPU를 깨울 수 있지만 select_cpu의 side effect를 적절히 쓰는 편이 단순하고 효율적이다. select_cpu 안에서 scx_bpf_dsq_insert()로 task를 즉시 넣을 수 있다. SCX_DSQ_LOCAL이면 select_cpu가 반환한 CPU의 local DSQ에 들어가며 이후 ops.enqueue()는 호출되지 않는다. task allowed cpumask 밖의 invalid CPU 반환은 core가 무시한다.

direct insert가 없으면 target CPU 선택 뒤 ops.enqueue()가 호출된다. callback은 SCX_DSQ_GLOBAL, SCX_DSQ_LOCAL, SCX_DSQ_LOCAL_ON|cpu, 2^63보다 작은 ID의 custom DSQ 중 하나에 즉시 insert하거나 BPF-side data structure에 task를 보관할 수 있다.

CPU가 schedule할 때 local, global 순서로 확인하고 둘 다 비면 ops.dispatch()를 부른다. dispatch는 scx_bpf_dsq_insert()로 어느 DSQ든 insertion을 예약할 수 있으며 pending 수는 ops.dispatch_max_batch까지다. 현재 이 helper는 BPF lock을 보유한 채 호출할 수 없지만 지원이 개발 중이다.

scx_bpf_move_to_local()은 지정 non-local DSQ에서 현재 dispatching CPU의 local DSQ로 task를 옮긴다. BPF lock을 보유한 채 호출할 수 없고, move 전에 pending insert를 flush한다.

dispatch가 반환한 뒤 local DSQ에 task가 있으면 첫 task를 실행한다. 없으면 global DSQ move를 다시 시도하고, dispatch가 task를 하나라도 예약했다면 dispatch 단계부터 재시도한다. 이전 task가 SCX task이고 여전히 runnable이면 SCX_OPS_ENQ_LAST 규칙에 따라 계속 실행할 수 있으며, 모두 실패하면 CPU가 idle로 간다.

enqueue에서 항상 built-in DSQ로 즉시 dispatch하면 BPF-side에 대기 task가 없어 ops.dispatch()를 구현할 필요가 없다. scx_bpf_dsq_insert()는 FIFO에 넣고 scx_bpf_dsq_insert_vtime()은 priority queue ordering을 사용한다. SCX_DSQ_LOCAL과 GLOBAL 같은 internal DSQ는 priority queue insertion을 지원하지 않는다.

sched_ext task lifecycle

새 task가 만들어지면 ops.init_task()로 BPF scheduler별 상태를 초기화하고 ops.enable()로 task에 BPF scheduling을 켠다. SCHED_EXT에 있는 동안 wakeup과 runnable/run/stop/quiescent cycle을 반복한다.

ops.init_task();            /* 새 task 생성 */
ops.enable();               /* task에 BPF scheduling 활성화 */

while (task in SCHED_EXT) {
	if (task can migrate)
		ops.select_cpu();   /* wakeup optimization */

	ops.runnable();       /* runnable 전환 */

	while (task is runnable) {
		if (task is not in a DSQ && task->scx.slice == 0) {
			ops.enqueue();
			/* usable CPU가 생김 */
			ops.dispatch();
		}
		ops.running();

		while (task_is_runnable(p)) {
			while (task->scx.slice > 0 && task_is_runnable(p))
				ops.tick();
			ops.dispatch(); /* slice refill 가능 */
		}
		ops.stopping();
	}
	ops.quiescent();      /* wait로 CPU release */
}

ops.disable();
ops.exit_task();

migration 가능한 wakeup에서는 select_cpu를 호출하고 runnable callback 뒤 DSQ와 slice 상태에 따라 enqueue/dispatch한다. CPU 실행 직전에 running, 1/HZ tick마다 tick, time slice 만료나 wait로 CPU를 떠날 때 stopping을 부른다. task가 wait 상태로 assigned CPU를 완전히 놓으면 quiescent가 호출된다.

task가 SCHED_EXT를 벗어나면 disable이 호출되고, task destruction 때 exit_task가 scheduler별 memory와 map state를 정리한다.

구현 위치와 ABI 안정성

가능한 범위에서 비교적 안정적인 surface를 유지하려고 하지만, out-of-tree scheduler는 대상 kernel source와 함께 build하고 API 변경을 추적해야 한다.