CPU資源管理;cgroupとCFS(スケジューラ)

序文

linux(ver6.3)において、cgroupを通じてCFSからタスクグループに割り当てられるcpu資源を調節する仕組みをまとめました。
間違いがあれば指摘して頂けると助かります。

cgroup

cgroupとは、cpuやメモリ、ネットワーク帯域幅といったリソースを階層的なプロセスのグループに割り当てる機構のこと。namespaceと共にコンテナ技術の核をなしています。
管理するリソースはサブシステムとしてそれぞれ独立して管理されます。
/sys/fs/cgroup/<subsystem>がサブシステムのルートディレクトリであり、以下にその資源を割り当てられるグループ(cgroup)がツリー上に作成されます。

kernel/cgroup/cgroup.c

int __init cgroup_init_early(void)
{
	static struct cgroup_fs_context __initdata ctx;
	struct cgroup_subsys *ss;
	int i;
	
	ctx.root = &cgrp_dfl_root;
	init_cgroup_root(&ctx);
	...
	
	for_each_subsys(ss, i) {
		...
		if(ss->early_init)
			cgroup_init_subsys(ss, true);
	}
	return 0;
}

上記のようにカーネル起動中にcgroupのルートディレクトリ、サブシステムのディレクトリが設定され、initプロセスの中で/sys/fs/cgroupにマウントされます。

/sys/fs/cgroup$ ls
blkio  cpu  cpuacct  cpuset  devices  freezer  hugetlb  memory  misc  net_cls  net_prio  perf_event  pids  rdma  unified
/sys/fs/cgroup$ cd cpu;ls
cgroup.clone_children  cpu.cfs_burst_us   cpu.idle           cpu.shares         release_agent
cgroup.procs           cpu.cfs_period_us  cpu.rt_period_us   cpu.stat           tasks
cgroup.sane_behavior   cpu.cfs_quota_us   cpu.rt_runtime_us  notify_on_release

/sys/fs/cgroup/cpuにはcpuサブシステムのルートタスクグループの設定が置かれ、以下にディレクトリを作成することで子のタスクグループを作成します。

プロセススケジューラ

カーネルはプロセススケジューリングを行うためにランキュー(run queue)というデータ構造を使用しています。

rq構造体が各cpu(コア)に一つづつ確保されます。

kernel/sched/core.c

struct rq {
	...
	struct cfs_rq rq;
	struct rt_rq rt;
	struct dl_rq dl;
	...
}

プロセススケジューリングには様々なアルゴリズムがあり、rq内のcfs_rq,rt_rq,dl_rqといったランキューはそれぞれ
Complete Fair Scheduling
RealTime スケジューリング
DeadLine スケジューリング　
用のランキューです。
今回は特別な設定をしていない場合に用いられるCFS(complete fair scheduling)について解説します。

CFS

CFSではcfs_rqという構造体にsched_entity(タスクの情報を含む構造体)を格納し、優先度順に整理することでスケジューリングを行います。

kernel/sched/sched.h

struct cfs_rq {
	struct load_weight load;
	...
	u64 min_runtime_fi;
	...
	struct sched_avg avg;
	...
	struct rb_root_cached tasks_timeline;
	
	struct sched_entity *curr;
	struct sched_entity *next;
	struct sched_entity *last;
	struct sched_entity *skip;
	...
	int on_list;
	struct list_head leaf_cfs_rq_list;
	struct task_group *tg;
	...
}

cfs_rqはsched_entityをそのメンバのvruntime(仮想実行時間)が小さい順に並べます。アルゴリズムには赤黒木を用いています。
またleaf_cfs_rq_listに子のcfs_rqを持つこともできます。leaf_cfs_rq_listはcfs_rqのメンバであるsched_group又はh_weightが小さい順に並べられます。
以上のことを整理するとこうなります。

sched_entity->vruntimeはプロセスが実行されるとその実行時間やタスクグループに応じて増加する値で、最も小さいプロセスが実行されます。この増加幅を調整すること、そしてcpu時間が制限されている場合はその時間を超過した時にプロセスをスリープさせることでプロセスグループにcpu資源を割り当てます。
因みに、vruntimeは増加し続ける変数ですが、スケールファクタを調整することでオーバーフローが起こらないよう調整されます。また、新しくキューに入ったプロセスのvruntimeはcfs_rq->min_vruntimeから始まるランダムな値に設定されます。

cgroupによるcpu資源管理

上ではcfs_rqがツリー構造になっていることを説明しましたが、このツリー構造はcpu cgroupのツリー構造と対応しています。

vruntimeの計算はupdate_curr(),dequeue_task_fair()などで行われます。

kernel/sched/fair.c

static void update_curr(struct cfs_rq *cfs_rq)
{
	...
	curr->vruntime += calc_delta_fair(delta_exec, curr);
	...
}

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
	if(unlikely(se->load.weight != NICE_0_LOAD))
		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
	
	return delta;
}

static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
	u64 fact = scale_load_down(weight);
	u32 fact_hi = (u32)(fact >> 32);
	int shift = WMULT_SHIFT;
	int fs;
	
	__update_inv_weight(lw);
	
	if(unlikely(fact_hi)) {
		fs = fls(fact_hi);
		shift -= fs;
		fact >>= fs;
	}
	
	fact = mul_u32_u32(fact, lw->inv_weight);
	fact_hi = (u32)(fact >> 32);
	if(fact_hi) {
		fs = fls(fact_hi);
		shift -= fs;
		fact >>= fs;
	}
	
	return mul_u64_u32_shr(delta_exec, fact, shift);
}

mul_u32_u32やmul_u64_u32_shrはチューニングされた乗算・シフト命令です。
lw->inv_weightは属するcgroupに応じて設定され、小さくなるほど優先度が大きくなることが分かります。
このようにしてcpu cgroupはvruntimeの計算に影響するほか、cpu時間の制限、cpu帯域幅の制限、cpu affinityの制限、cpu使用率や消費電力の制限をすることができます。