Share
Embed
Transcript
102 slides
-
はじめに • Linuxカーネル(以下カーネル)のプロセススケジューラの歴史を振り返る • 対象バージョンは一番最初(0.01)から最新(4.18)まで全部 ◦ <= 2.6.12(*1): 切りのいいバージョンを紹介 ◦
> 2.6.12: 大きな変更が入ったバージョンを適宜紹介 • 用語 ◦ タスク: カーネルのスケジューリング単位。プロセスないしスレッド ◦ LCPU: カーネルがCPUとして認識するもの(物理CPU or コア or スレッド) ◦ Current: LCPU上で現在動作中のタスク 2 *1) git導入後最初の安定版 -
もくじ 1. ~v2.4.x: 最初のスケジューラ 2. V2.6.0~v2.6.22: O(1)スケジューラ 3. V2.6.23~: Completely
Fair Scheduler (CFS) 3 -
もくじ 1. ~v2.4.x: 最初のスケジューラ 2. V2.6.0~v2.6.22: O(1)スケジューラ 3. V2.6.23~: Completely
Fair Scheduler (CFS) 4 -
V0.01: 概要 • 超絶シンプルなラウンドロビンスケジューリング ◦ コア部分は20行弱 • タスクを管理する配列がそのままランキュー ◦ 長さは64:
つまりタスクは最大でも 64 ◦ 空要素にはnilが入る • タイムスライスは固定150[ms] ◦ インターバルタイマーの 1tickは10[ms] ◦ のちにタイムスライスはコロコロ変わるが、あまり重要じゃないので省略 • currentのタイムスライス切れ or 全タスクがsleepならスケジューラを呼ぶ 5 -
V0.01: スケジューリングアルゴリズム • ランキューを全走査して残りタイムスライスが最大のものを次に動かす • 該当者がいなければ全タスクのタイムスライスをリセット ◦ タイムスライスが切れているプロセスには 150[ms]与える ◦
スリープ中のタスクには残りタイムスライス /2をボーナスとして与える ▪ 寝起きを繰り返すbashなどを起床時に優先的に動作させる仕組み (多分) 6 -
スケジューラの挙動: 初期状態 7 runnable 10 runnable 15 nil runnable 5
ランキュー (タスク管理配列) sleep 12 タイムスライス タスク未割当 タスクの状態 t0 t1 t2 t3 t4 -
スケジューリング 8 runnable 10 runnable 15 nil runnable 5 ランキュー
(タスク管理配列) sleep 12 ランキュー全走査 runnableの中でタイムスライスが最大のものを選ぶ t0 t1 t2 t3 t4 -
t1がタイムスライス切れ 9 runnable 10 runnable 0 nil runnable 5 ランキュー
(タスク管理配列) sleep 12 t0 t1 t2 t3 t4 -
次のスケジューリング 10 runnable 10 runnable 0 nil runnable 5 ランキュー
(タスク管理配列) sleep 12 ランキュー全走査 runnableの中でタイムスライスが最大のものを選ぶ • タイムスライスが同じタスクが複数いれば最初に見つかったものを選択 t0 t1 t2 t3 t4 -
全員がタイムスライス切れ or sleep 11 runnable 0 runnable 0 nil runnable
0 ランキュー (タスク管理配列) sleep 12 t0 t1 t2 t3 t4 -
タイムスライスをリチャージ 12 runnable 15 runnable 15 nil runnable 15 ランキュー
(タスク管理配列) sleep 21 • スリープ中のタスクには残り ”タイムスライス/2”をボーナスとして与える t0 t1 t2 t3 t4 -
sleepから起床したタスクはrunnableになるだけ 13 runnable 15 runnable 15 nil runnable 15 ランキュー
(タスク管理配列) runnable 21 t0 t1 t2 t3 t4 おはよう • Preemption? そんなものは無い -
V0.01: その他 • Nice値 ◦ 変更するとタイムスライスが増減 ◦ rootでなくてもマイナス値を設定可能 ◦ 任意の値を設定可能
▪ 例: nice値-10,000 => タイムスライスは100,150[ms] ◦ 絶対値を指定できない : setpriority()システムコールは無い • タスク == プロセス。カーネル内でスレッドを扱えない 14 -
v1.0 • Preemptionの導入 ◦ 条件: sleepから起床したタスクのタイムスライス > currentのタイムスライス • Nice値の扱いがまともになる
◦ Rootでないとマイナス値を設定できなくなる ◦ nice値は-19~20の間のみ意味を持つようになる ◦ Nice値の絶対値を指定可能に : {set,get}priority()システムコールが追加 15 -
ランキューデータ構造がリストに • スケジューリングアルゴリズム ◦ ランキューからタイムスライスが最大のタスクをとってくる • タイムスライスを使い果たすとランキュー末尾に挿入 • 生成直後&sleep起床時のタスクもランキュー末尾に挿入 •
ランキューへのタスク挿入時にソートしない ◦ スケジューリング処理の計算量は O(n): nはrunnableタスクの数 17 -
sleepから起床したタスクはランキュー末尾へ 22 Runnable 10 Runnable 5 Runnable 0 Runnable 15
t0 t2 t1 t3 おはよう • Preemtion発生 ◦ T3のタイムスライス > current(t0)のタイムスライス -
V2.0: SMP対応 • ランキューはグローバルなもの1本 • sleepからの起床時には直前に動作したLCPU上で動作しやすくなっている ◦ 前回動作時の状態がキャッシュメモリに残ってる可能性が高いという推測 (多分) •
ロードバランサは無い(必要もない) 23 LCPU0 LCPU1 Runnable 10 Runnable 15 Runnable 5 共有 t0 t1 t2 -
リアルタイムポリシーの追加 • タスクをリアルタイムタスクにできる ◦ 通常のタスク(SCHED_OTHERポリシー)より常に優先的に動作可能 ◦ 用途: ハートビート処理など (1秒ごとに起動して通信してすぐ寝る、など )
• 二種類ある ◦ SCHED_FIFOポリシー: タイムスライスなし。ここではこちらのみ扱う ◦ SCHED_RRポリシー: タイムスライスあり • sched_setscheduler()システムコールやchrtコマンドによって設定 ◦ rootのみ設定可能 24 -
スケジューラの挙動: 初期状態 25 Runnable OTHER 10 Runnable FIFO -- Runnable
FIFO -- t0 t1 t2 -
スケジューリング 26 Runnable OTHER 10 Runnable FIFO -- Runnable FIFO
-- • ランキュー全走査 • リアルタイムタスクは「常に」通常のタスクより優先動作 t0 t1 t2 -
リアルタイムタスクがcurrentになると… 27 Runnable OTHER 10 Runnable FIFO -- Runnable FIFO
-- sleepするかexitするまでSCHED_OTHERがいくら待とうがずっと動作 t0 t1 t2 -
もくじ 1. ~v2.4.x: 最初のスケジューラ 2. V2.6.0~v2.6.22: O(1)スケジューラ 3. V2.6.23~: Completely
Fair Scheduler (CFS) 29 -
V2.6: O(1)スケジューラ • コア部分のアルゴリズム総とっかえ ◦ スケジュール処理の計算量が O(1) ◦ 対話型タスクの優先動作 ◦
LCPUごとのランキュー ◦ ロードバランサ ◦ Cpu affinity ◦ カーネルレベルスレッド 30 -
sleepから起床したタスクはactiveキュー末尾へ 41 Runnable 10 Runnable 10 inactive active t0 t1
Runnable 5 t2 おはよう -
優先度別ランキュー 42 nice値20のランキュー nice値-19のランキュー nice値0のランキュー … … active inactive active
inactive active inactive … … -
高優先度ランキューの先頭から順番にスケジュール 43 nice値20のランキュー nice値-19のランキュー nice値0のランキュー 1 2 … … active
inactive 3 4 active inactive 5 6 active inactive … … -
全activeキューが空になると… 44 nice値20のランキュー nice値-19のランキュー nice値0のランキュー … … active inactive active
inactive active inactive … … -
activeキューとinactiveキューをスイッチ 45 nice値20のランキュー nice値-19のランキュー nice値0のランキュー … … inactive active inactive
active inactive active … … -
対話型タスクの優先動作 • 対話型タスク: bashやXなどの人間が直接やりとりするタスク • 課題 ◦ Runnableタスク増加に伴い対話型タスク起床時のスケジュールが遅れる ◦ ユーザの体感レイテンシが長くなる
• O(1)スケジューラの対策: ヒューリスティックを入れる ◦ 単位時間あたりにsleepしている率が高いプロセスを対話型タスクとみなす ◦ 対話型タスクへの優遇 ▪ タイムスライスが切れると expiredキューではなくactiveキューに移す ▪ 優先度を上げる(最大5): タイムスライスは変化しない ◦ その一方、ずっとrunnableなタスクは優先度を下げる (最大5) 46 -
ロードバランサ • 負荷の高いLCPUから負荷の低いLCPUにタスクを移動 ◦ 負荷 == ランキュー長 ◦ のちに負荷はnice値やスケジューリングポリシーを考慮して重み付けするようになる •
動作契機 ◦ 新たにLCPUがアイドルになったとき ◦ 周期的に起動 49 -
ロードバランサの挙動: 初期状態 • 2ノード×2CPU(合計4LCPU)構成 53 t0 t1 t5 t4 t3
LCPU0 LCPU1 LCPU2 LCPU3 t2 node0 node1 -
一番busyなnodeと暇なnodeを見つける • 54 t0 t1 t5 t4 t3 LCPU0 LCPU1
LCPU2 LCPU3 t2 node0 node1 タスク数4 タスク数2 -
一番busyなnode内の一番忙しいLCPUを選ぶ • 55 t0 t1 t5 t4 t3 LCPU0 LCPU1
LCPU2 LCPU3 t2 node0 node1 タスク数3 タスク数1 -
一番暇なnode内の一番暇なLCPUを選ぶ • 56 t0 t1 t5 t4 t3 LCPU0 LCPU1
LCPU2 LCPU3 t2 node0 node1 タスク数0 タスク数2 -
一番busyなLCPUから一番暇なLCPUにタスクを移動 • 57 t0 t1 t5 t4 t3 LCPU0 LCPU1
LCPU2 LCPU3 t2 node0 node1 t2 移動 -
CPU affinity • タスクを動作させるLCPUの集合を決められる ◦ 用途: 全CPUで1つづつ動かしたいハートビート用タスクなど ◦ sched_setaffinity()システムコールやtasksetコマンドによって設定 58
T0 Affinity: 0, 1 T1 Affinity: 0 T2 Affinity: 1 LCPU0 LCPU1 × 移動可 〇 移動不可 -
カーネルレベルスレッド • メモリ空間を共有するタスクが作れるようになった • これを元にしたユーザ空間スレッドライブラリが作られた ◦ LinuxThreads -> NPTL 59
v2.4系以前のスレッド v2.6系以降のスレッド(*1) • 左記のような実装も依然できる カーネル ユーザ タスク0 プロセス0 スレッド0 スレッド1 タスク0 プロセス0 スレッド0 スレッド1 タスク1 -
魔改造カーネルの欠点 • Upstreamへの追従が大変すぎて死ぬ 1. upstreamの新バージョンが出る 2. 全パッチから必要なものを抽出 3. 必要なパッチをバックポート 4.
1に戻る • 最近はどこもupstream firstを謳っており、こういうのは減っている 62 じゃあの -
V2.6.12: cpuset • タスクのグループに割り当てられるCPUのリストやメモリ量などを制限 • アプリやユーザごとの資源管理に利用 • /dev/cgroup以下ファイルによって操作 63 Cpuset0
動作可能LCPUリスト: 0, 1 使用可能メモリ量: 100MB Cpuset1 動作可能LCPUリスト: 2, 3 使用可能メモリ量: 200MB t0 t1 t2 -
O(1)スケジューラの諸問題 • ヒューリスティック多すぎでコーナーケースが山ほどある ◦ 例: 応答性向上機能のせいでシステムが応答しなくなる 1. スリープと起床を繰り返すタスクを大量に起動 2. 一部タスクが対話的とみなされて優先度が最高になる
3. 2で述べたタスクがタイムスライスを使い切っても activeキューに再挿入 4. 他のタスクはそもそも動けないから優先度が上がらない 5. 2で述べたタスクが長時間動き続ける • runnableタスク数が多いとなかなかCPU時間が回ってこない • タイムスライスの粒度が荒くて細かい制御ができない ◦ 粒度を増やすにはタイマー割り込みの回数を増やす必要がある ◦ 粒度を1msにすると秒間1,000回の割込、1usにすると1,000,000回の割込みが必要 ◦ 細かくすると割り込み回数が上がってシステム全体の性能が下がる 64 -
V2.6.2{0,1,2}の開発中あたり: RSDL vs CFS • 次期スケジューラの座を争って2つの新実装が激突 ◦ Rotating Staircase Deadline
Scheduler by Con Kolivas ▪ 「今のスケジューラはエンプラ用途に特化しすぎ」とデスクトップ志向を目指した ◦ Completely Fair Scheduler(CFS) by Ingo Molnar ▪ RSDLに触発されて後追いで作られた ▪ 目標は全てのタスクを Completely Fair(完全に平等)に扱うこと 65 CFSがいいよ RSDLがいいよ -
もくじ 1. ~v2.4.x: 最初のスケジューラ 2. V2.6.0~v2.6.22: O(1)スケジューラ 3. V2.6.23~: Completely
Fair Scheduler (CFS) 68 -
レイテンシターゲットによるスケジューリング • ランキューはvruntimeと呼ばれる仮想的なキー(後述)とした赤黒木 ◦ スケジューリング処理の計算量は O(log(n)) ◦ active/inactiveキュー、および優先度別ランキューは廃止 • 各タスクはレイテンシターゲットと呼ばれる期間に一度CPU時間を得られる
◦ レイテンシターゲットは数 ms~数十ms。システムのLCPU数やバージョンによって変わる ◦ タイムスライス = レイテンシターゲット ()/runnableタスク数 70 -
LCPU上で動くタスク 71 タスク数2 タスク数3 タスク数4 時間 t0 t1 t0 t1
t0 t1 t2 t0 t1 t2 t0 t1 t2 t3 t0 t1 t2 t3 レイテンシターゲット レイテンシターゲット -
スケジューラの挙動: 初期状態 • 仮定 ◦ レイテンシターゲット : 10 [ms] •
タイムスライス=10/(runnableタスク数=3) [ms] 72 0 0 0 t0 t1 t2 vruntime(簡単のため簡略化している ) LCPU -
vruntimeをrunnableタスク内最小値にしてランキューに挿入 • vruntime=15のタスクの残りタイムスライス ◦ (2.0-1.5)*(10/3)=1.67 [ms] → (2.0-1.5)*(10/4) = 1.25
[ms] • vruntime=10のタスクの残りタイムスライス ◦ (2.0-1.0)*(10/3)=3.3 [ms] → (2.0-1.0)*(10/4) = 2.5 [ms] 78 1.0 1.0 t1 t2 LCPU 1.0 t3 1.5 t0 -
nice値の扱い • Niceの変化によってタイムスライスの比率が変わる ◦ nice値が低い(高優先度): 比率が上がる ◦ nice値が低い(低優先度): 比率が下がる 79
T0 0 T1 -1 T0 0 T1 0 T0 0 T1 1 時間 T0 0 T1 0 nice値 T0のnice値 > t1のnice値 T0のnice値 == t1のnice値 T0のnice値 < t1のnice値 T0 0 T1 -1 T0 0 T1 1 -
プラガブルなスケジューラ • アルゴリズム別にスケジューリングクラスという概念を導入 ◦ 効果: 後からスケジューラを追加するのが楽 & コードの見通しが良い ◦ クラスごとにコールバック関数のセットを用意
i. 次のcurrentを選ぶ関数、タスクの sleep時に呼ぶ関数、起床時に呼ぶ関数、など • 高優先度のクラスに属するrunnableタスクがあれば、それより下の優先度のタスク より常に優先動作 ◦ スケジューリングクラス (優先度順) i. rt_shed_class: リアルタイムタスク。ポリシーは SCHED_{FIFO,RR} ii. fair_sched_class: 通常のプロセス。ポリシーは SCHED_OTHER 80 -
細かいタイムスライス粒度 • O(1)まで ◦ レガシーなインターバルタイマーを使用 : 定期的に割り込みが発生し続ける ◦ ms単位が限度 •
CFS ◦ ワンショット高精度タイマー : タイムスライスが切れる時に割り込みを発生させる ◦ Ns単位の制御が可能 81 -
V2.6.24: fair group scheduling • Cpu cgroup 1. グループ間でCPUを均等配分 2.
グループ内でさらに均等配分 • Cpu cgroupのcpu.sharesパラメタによって重み付けも可能 • ネストも可能 82 -
LCPU上で動くタスク 83 時間 t0 t1 t2 t0 t1 t2 cgroupなし
Cgroupあり グループA: t0, t1 グループB: t2 t0 t1 t2 t0 t1 t2 1 1/3 1/3 1/3 1 1/4 1/4 1/2 1/2 -
LCPU上で動くタスク: share変更あり 84 時間 t0 t1 t0 t1 Cgroupあり グループA:
t0 share: 1 グループB: t1 share: 1 Cgroupあり グループA: t0 Share: 1 グループB: t1 Share: 2 1 1/2 1/2 t0 t1 1 1/3 2/3 t0 t1 -
Usecase: ユーザ間でCPU資源を均等配分 • 例: ユーザAがt0, ユーザBがt1-t3を動かしているとする 85 Fair group scheduling不使用
ユーザごとにグループ作成 時間 t0 t1 t2 t3 時間 t0 t1 t2 t3 タスク同士が公平 ユーザ同士は不公平 ユーザ同士が公平 -
リアルタイムタスクが止まらない問題 • リアルタイムタスクが暴走すると通常のタスクが一切動けない • コアが1つしかないとシステムがハング • 例: ランキュー上にいるタスク ◦ T0:
リアルタイムタスク(SCHED_FIFO)。CPUを自発的に明け渡さず動き続ける ◦ T1: 通常のタスク(SCHED_OTHER)。t0暴走中に起床 87 t0 時間 t1は一切動けない t1起床 -
V2.6.25: Realtime group scheduling • リアルタイムタスクは所定の期間内に一定の時間しか動作できない ◦ 所定の期間: sysctlのkernel.sched_rt_period_us(デフォルトは1000000[us]) ◦
一定の時間: sysctlのkernel.sched_rt_runtime_us(デフォルトは950000[us]) • 空いた時間に通常のタスクが動ける • Cpu cgroupのcpu.rt_{period,runtime}によって入れ子構造にできる 88 t0 時間 t1は1秒間に50msだけは動ける t1 t0 t1 t1起床 -
重要なカーネルスレッドが動けない問題 • 優先度最高のリアルタイムタスクがCPUを使い続けるとカーネルの重要なタスクが 動けなくなる ◦ 例: CPU hotplug時のシステムの機能をほぼ止める stop_machineという処理 •
原因: カーネルタスクの最高優先度 == ユーザタスクの最高優先度 89 -
V2.6.37: Stop scheduling class • 全てのユーザプロセスに優先して動くカーネル専用スケジューリングクラス • スケジューリングクラス(優先度順) 1. (new)
Stop_sched_class 2. Rt_sched_class 3. fair_sched_class 90 -
スケジューラの挙動: stop scheduling classなし • 例: ランキュー上のタスク • T0: ユーザのタスク。暴走していて
CPUを自発的に手放さない ◦ 優先度最大(99)のリアルタイムタスク • T1: カーネルの重要なタスク。 t0暴走中に起床 ◦ 優先度最大(99)のリアルタイムタスク 91 t0 時間 t1は一切動けない t1起床 -
スケジューラの挙動: stop scheduling classあり • 例: ランキュー上のタスク • T0: ユーザのタスク。暴走していて
CPUを自発的に手放さない ◦ 優先度最大(99)のリアルタイムタスク • T1: カーネルの重要なタスク。 t0暴走中に起床 ◦ Stop scheduling classのタスク 92 t0 時間 t1起床 t1 t0 T1 sleep or exit -
V2.6.38: autogroup • システム高負荷時におけるデスクトップ環境の応答性向上機能 ◦ 通称ミラクルパッチ • アイデア ◦ セッションごとにタスクを自動的にグループ分け
◦ グループごとに平等に CPU資源を与える • Linus氏が「小さい効果で効果が大きい」と大絶賛。パッチ投稿後速攻マージ • しかしこれも一部ケースを救うだけ ◦ 例: デスクトップアプリを動かす横でカーネルビルドをぶん回す非常に一般的なワークロード 95 -
Fair group schedulingの課題: 上限設定ができない • 例: 2ユーザA, B同居のマルチテナントシステム ◦ やりたいこと:
個々のユーザにCPU資源を”最大”1/2与えたい ▪ ユーザ間の不平等、過剰なサービスの提供を避けたい ◦ Fair group schedulingにできること: ユーザごとにグループ作成 96 時間 Aだけがタスクを動かしている状態 (あるべき姿) Aのタスク Aだけがタスクを動かしている状態 (現実) Aのタスク idle Aのタスク idle -
V3.2: CFS bandwidth controller • あるcpu cgroupが所定期間内に動ける時間を制限 ◦ cpu.Cfs_period: 期間([us]単位)
◦ Cpu.cfs_quota: 動ける時間([us]単位) • ネストも可能 • コンテナやVMのリソース制限に使われる 97 -
スケジューラの挙動 • レイテンシターゲットは10ms • グループAのcpu.cfs_period=10ms, cpu.cfs_runtime=5ms 98 時間 t0 t1
t0 t0 t1 bwc不使用 t1がsleep t1が起床 t0 t1 t0 idle t0 t1 Bwc使用 T0はグループAに所属 t1がsleep t1が起床 -
V3.14: Deadlineスケジューラ • 所定の期間中にどれだけのCPU時間を使うかを設定できる • rootのみ使える • スケジューリングクラス 1. Stop_sched_class
2. (new) Deadline_sched_class 3. Rt_sched_class 4. Fair_sched_class • sched_setscheduler() or sched_setparam()で以下3つのパラメタを与える 1. Period: タスクはperiodで示された期間中に最大 1度動作 2. Runtime: タスクが一度起床してから sleepするまでの計算所要時間 3. deadline: タスクが起床してから計算を終了しなくてはならない期間 99 -
コード量の遷移 101 O(1) CFS Fair group sched Bandwidth controller Deadline
scheduler SMP ready Realtime scheduler