LinuxのスケジューラをOptunaで最適化してみた

概要

この文書ではOSのスケジューラを扱います。
書籍『Linux Kernel Development』によれば、スケジューラとは「次にどのプロセスを実行するかを選択するプログラム」です。
LinuxはCFS(Completely Fair Scheduler)というスケジューラを使用しており、CFSは様々なチューニングパラメータを持っています。
この文書ではOptunaを用いてCFSの最適化を行います。
Linuxカーネルのビルド時間が最短になるように最適化を行います。
結論から言うと 1.8 秒だけ短縮できました。

ビルド環境

ハードウェア

項目	値
CPU	Intel Core-i7 3770 ( 3.40GHz )
CPUコア	4 個 ( HT により 8 個 )
メモリ	16 Gbytes

ソフトウェア

項目	値
ホストOS	Ubuntu 18.04 ( amd64 ) 4.15.0-45-generic

ビルド対象Linux

項目	値
kernel version	Linux 5.0-rc8
tree	wireless-testing
commit	9a656b08652c4975c17a4bec6271aebdebf3c37a
commit log	Add localversion to identify builds from this tree

ソース

import subprocess
import errno
import time
import optuna
import signal

def signal_handler(signum, frame):
	raise Exception("Timed out")

def objective(trial):
	params = {
		'GENTLE_FAIR_SLEEPERS': trial.suggest_categorical('GENTLE_FAIR_SLEEPERS', ['GENTLE_FAIR_SLEEPERS', 'NO_GENTLE_FAIR_SLEEPERS']),
		'START_DEBIT': trial.suggest_categorical('START_DEBIT', ['START_DEBIT', 'NO_START_DEBIT']),
		'NEXT_BUDDY': trial.suggest_categorical('NEXT_BUDDY', ['NEXT_BUDDY', 'NO_NEXT_BUDDY']),
		'LAST_BUDDY': trial.suggest_categorical('LAST_BUDDY', ['LAST_BUDDY', 'NO_LAST_BUDDY']),
		'CACHE_HOT_BUDDY': trial.suggest_categorical('CACHE_HOT_BUDDY', ['CACHE_HOT_BUDDY', 'NO_CACHE_HOT_BUDDY']),
		'WAKEUP_PREEMPTION': trial.suggest_categorical('WAKEUP_PREEMPTION', ['WAKEUP_PREEMPTION', 'NO_WAKEUP_PREEMPTION']),
		'HRTICK': trial.suggest_categorical('HRTICK', ['HRTICK', 'NO_HRTICK']),
		'DOUBLE_TICK': trial.suggest_categorical('DOUBLE_TICK', ['DOUBLE_TICK', 'NO_DOUBLE_TICK']),
		'LB_BIAS': trial.suggest_categorical('LB_BIAS', ['LB_BIAS', 'NO_LB_BIAS']),
		'NONTASK_CAPACITY': trial.suggest_categorical('NONTASK_CAPACITY', ['NONTASK_CAPACITY', 'NO_NONTASK_CAPACITY']),
		'TTWU_QUEUE': trial.suggest_categorical('TTWU_QUEUE', ['TTWU_QUEUE', 'NO_TTWU_QUEUE']),
		'SIS_AVG_CPU': trial.suggest_categorical('SIS_AVG_CPU', ['SIS_AVG_CPU', 'NO_SIS_AVG_CPU']),
		'SIS_PROP': trial.suggest_categorical('SIS_PROP', ['SIS_PROP', 'NO_SIS_PROP']),
		'WARN_DOUBLE_CLOCK': trial.suggest_categorical('WARN_DOUBLE_CLOCK', ['WARN_DOUBLE_CLOCK', 'NO_WARN_DOUBLE_CLOCK']),
		'RT_PUSH_IPI': trial.suggest_categorical('RT_PUSH_IPI', ['RT_PUSH_IPI', 'NO_RT_PUSH_IPI']),
		'RT_RUNTIME_SHARE': trial.suggest_categorical('RT_RUNTIME_SHARE', ['RT_RUNTIME_SHARE', 'NO_RT_RUNTIME_SHARE']),
		'LB_MIN': trial.suggest_categorical('LB_MIN', ['LB_MIN', 'NO_LB_MIN']),
		'ATTACH_AGE_LOAD': trial.suggest_categorical('ATTACH_AGE_LOAD', ['ATTACH_AGE_LOAD', 'NO_ATTACH_AGE_LOAD']),
		'WA_IDLE': trial.suggest_categorical('WA_IDLE', ['WA_IDLE', 'NO_WA_IDLE']),
		'WA_WEIGHT': trial.suggest_categorical('WA_WEIGHT', ['WA_WEIGHT', 'NO_WA_WEIGHT']),
		'WA_BIAS': trial.suggest_categorical('WA_BIAS', ['WA_BIAS', 'NO_WA_BIAS']),

		'sched_autogroup_enabled': trial.suggest_int('sched_autogroup_enabled', 0, 1),
		'sched_cfs_bandwidth_slice_us': trial.suggest_int('sched_cfs_bandwidth_slice_us', 1, 1000000000),
		'sched_child_runs_first': trial.suggest_int('sched_child_runs_first', 0, 1),
		'sched_latency_ns': trial.suggest_int('sched_latency_ns', 100000, 1000000000),
		'sched_migration_cost_ns': trial.suggest_int('sched_migration_cost_ns', 0, 1000000000),
		'sched_min_granularity_ns': trial.suggest_int('sched_min_granularity_ns', 100000, 1000000000),
		'sched_nr_migrate': trial.suggest_int('sched_nr_migrate', 1, 128),
		'sched_rr_timeslice_ms': trial.suggest_int('sched_rr_timeslice_ms', 1, 1000),
		#'sched_rt_period_us': trial.suggest_int('sched_rt_period_us', 950000, 1000000000),
		#'sched_rt_runtime_us': trial.suggest_int('sched_rt_runtime_us', 0, 1000000000),
		'sched_schedstats': trial.suggest_int('sched_schedstats', 0, 0),
		'sched_time_avg_ms': trial.suggest_int('sched_time_avg_ms', 1, 1000),
		'sched_tunable_scaling': trial.suggest_int('sched_tunable_scaling', 0, 0),
		'sched_wakeup_granularity_ns': trial.suggest_int('sched_wakeup_granularity_ns', 0, 1000000000),
	}

	for key in params:
		if key.startswith('sched_'):
			print(key, params[key])
			with open('/proc/sys/kernel/' + key, 'w') as f:
				f.write(str(params[key]))
		else:
			print(key, params[key])
			with open('/sys/kernel/debug/sched_features', 'w') as f:
				f.write(params[key])

	build_dir = '~/git/wireless-testing'

	make_result = subprocess.run(['/usr/bin/make', 'clean'], cwd=build_dir, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
	if make_result.returncode != 0:
		print('returncode', make_result.returncode)
		print('stderr', make_result.stderr.decode())
		exit(0)

	start_time = time.time()
	make_result = subprocess.run(['/usr/bin/make', '-j9'], cwd=build_dir, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
	if make_result.returncode != 0:
		print('returncode', make_result.returncode)
		print('stderr', make_result.stderr.decode())
		exit(0)

	duration = time.time() - start_time
	print(duration)

	max_time = 1000.0
	if duration > max_time:
		print('duration exceeded max time', duration)
		exit(0)

	result_array.append(duration)

	return duration / max_time

def run_optuna():
	study = optuna.create_study()
	study.optimize(objective, n_trials=256)

	print('Number of finished trials: {}'.format(len(study.trials)))

	print('Best trial:')
	trial = study.best_trial

	print('  Value: {}'.format(trial.value))

	print('  Params: ')
	for key, value in trial.params.items():
		print('    {}: {}'.format(key, value))

result_array = []
run_optuna()
print(result_array)

※ sched_rt_period_usとsched_rt_runtime_usはリアルタイムプロセスに関するパラメータなので除外しました。
※ sched_schedstats は 0 が最適なのは自明なので 0 に固定しました。
※ sched_tunable_scaling はデフォルトの 1 の場合は CPU コアの数に応じてパラメータ値が変化するので 0 に固定しました。

結果

デフォルト値での実行結果: 140.1023600101471(sec)
最適化後の実行結果: 139.7200379371643(sec)
0.4 秒しか短縮できませんでした。

※ キャッシュの効果を考慮し、一度ビルドしてから測定を開始しました。
/sys/kernel/debug/sched_features の値は以下の通りです。

項目	デフォルト	最適化後
GENTLE_FAIR_SLEEPERS	on	on
START_DEBIT	on	off
NEXT_BUDDY	off	on
LAST_BUDDY	on	on
CACHE_HOT_BUDDY	on	on
WAKEUP_PREEMPTION	on	on
HRTICK	off	off
DOUBLE_TICK	off	on
LB_BIAS	on	on
NONTASK_CAPACITY	on	on
TTWU_QUEUE	on	on
SIS_AVG_CPU	off	on
SIS_PROP	on	off
WARN_DOUBLE_CLOCK	off	on
RT_PUSH_IPI	on	off
RT_RUNTIME_SHARE	on	on
LB_MIN	off	off
ATTACH_AGE_LOAD	on	off
WA_IDLE	on	off
WA_WEIGHT	on	off
WA_BIAS	on	off

/proc/sys/kernel/sched_* の値は以下の通りです。

項目	デフォルト	最適化後
sched_autogroup_enabled	1	0
sched_cfs_bandwidth_slice_us	5000	451661808
sched_child_runs_first	0	0
sched_latency_ns	24000000	326652418
sched_migration_cost_ns	500000	1210381
sched_min_granularity_ns	3000000	210370275
sched_nr_migrate	32	80
sched_rr_timeslice_ms	100	774
sched_rt_period_us	1000000	1000000
sched_rt_runtime_us	950000	950000
sched_schedstats	0	0
sched_time_avg_ms	1000	401
sched_tunable_scaling	1	0
sched_wakeup_granularity_ns	4000000	609092

リトライ

前述の通り、あまり良い結果は出ませんでした。
やはり全パラメータ丸投げでは探索空間が広すぎると考え、効きそうなパラメータ（下記 3 項目）に絞ってリトライします。

sched_latency_ns
sched_min_granularity_ns
sched_wakeup_granularity_ns

結果、138.32158493995667(sec) になりました。デフォルトから 1.8 秒の短縮です。誤差の範囲っぽいですね...
既に先人の皆さんによって十分最適化されているということなのでしょう。「もっとこのパラメータに絞った方が良い」等ご意見お待ちしています。

項目	デフォルト	最適化後
sched_latency_ns	24000000	458865373
sched_min_granularity_ns	3000000	217321603
sched_tunable_scaling	1	0
sched_wakeup_granularity_ns	4000000	160523018

※ sched_tunable_scaling は先程同様 0 に固定しています。