Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Xenのスケジューラがぜんぜんわからん
Search
Keisuke Nishimura
November 20, 2021
Programming
0
1.3k
Xenのスケジューラがぜんぜんわからん
Kernel/VM探検隊online part4 発表資料
Keisuke Nishimura
November 20, 2021
Tweet
Share
More Decks by Keisuke Nishimura
See All by Keisuke Nishimura
eBPFを使ったオレオレカーネル拡張入門
mu_mu_mu
1
950
C言語プログラムの構造とほんの少し解釈
mu_mu_mu
3
1.7k
Intel MPK入門
mu_mu_mu
0
650
Other Decks in Programming
See All in Programming
プロダクトという一杯を作る - プロダクトチームが味の責任を持つまでの煮込み奮闘記
hiliteeternal
0
460
ゲームの物理
fadis
5
1.2k
TROCCO×dbtで実現する人にもAIにもやさしいデータ基盤
nealle
0
260
レガシープロジェクトで最大限AIの恩恵を受けられるようClaude Codeを利用する
tk1351
2
170
GitHub Copilotの全体像と活用のヒント AI駆動開発の最初の一歩
74th
7
2.9k
Introduction to Git & GitHub
latte72
0
110
未来を拓くAI技術〜エージェント開発とAI駆動開発〜
leveragestech
2
150
TanStack DB ~状態管理の新しい考え方~
bmthd
1
110
なぜ今、Terraformの本を書いたのか? - 著者陣に聞く!『Terraformではじめる実践IaC』登壇資料
fufuhu
4
620
The State of Fluid (2025)
s2b
0
170
UbieのAIパートナーを支えるコンテキストエンジニアリング実践
syucream
2
490
生成AI、実際どう? - ニーリーの場合
nealle
0
130
Featured
See All Featured
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
How to Ace a Technical Interview
jacobian
279
23k
Automating Front-end Workflow
addyosmani
1370
200k
Agile that works and the tools we love
rasmusluckow
329
21k
Navigating Team Friction
lara
188
15k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
49
3k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
229
22k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
8
470
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
8
890
Designing Dashboards & Data Visualisations in Web Apps
destraynor
231
53k
Rebuilding a faster, lazier Slack
samanthasiow
83
9.1k
BBQ
matthewcrist
89
9.8k
Transcript
Xenのスケジューラが ぜんぜん わからん 西村 啓佑 / mumumu (@mumumu_vm ) Kernel/VM探検隊online
part4
Xenのアーキテクチャ DomU Dom0 DomU vCPU vCPU vCPU vCPU vCPU vCPU
pCPU pCPU pCPU NIC GPU Xen (VMM) Domain (VM) スケジューラ VM間通信機構 ・・・ ・・・ vCPUをpCPUに 割り当てる 2
vCPUスケジューリング • 目的は計算資源の再配分(OSスケジューラと同じ) • OSのスケジューリングとの違い • スケジューリング単位(VM v.s. Process) •
実際に動作するApp.に関する情報の粒度 • VMM-App.間にOSが挟まるDouble-Scheduling … • OSからみると,CPUが常に使えるとは限らない. (参考) 本来のOSはCPUは常に使えることが前提 • 例:IO発生時すぐにCPUに割り込みが来る想定 • 例:IPC発生時すべてのコアが動作している想定 3
Xen のスケジューラ • Credit スケジューラ • Credit2 スケジューラ • SEDFスケジューラ
• RTDSスケジューラ • BVTスケジューラ … ←このLTの対象 (汎用,非RT系) 4
Credit スケジューラ • 元デフォルトスケジューラ: 3.0~4.11 (2005-2018) • 固定タイムスライスでProportional Share(PS) •
タイムスライスはデフォで30ms固定 (例外あり:tickle, IO) • PS: 各VM(vCPU)はWeight(優先度)に比例した時間割当て • Credit = Weightに応じ配分された実行時間 • 使い果たしたVM (credit <= 0) OVER • 残っているVM (credit > 0) UNDER • UNDERのvCPUをRRで順にスケジュール 該当コード: xen/xen/common/sched/credit.c Creditの値に非依存 (「0以上か」が重要) 5
Credit スケジューラ 基本アルゴリズム 全てのvCPUに対して Weightに応じたCreditを配布(加算) Creditが正のvCPUを選んで実行 実行時間分のCreditを消費 Creditが正の vCPUが存在 定期実行
TS(固定)時間実行 6
Credit スケジューラ IOのLatencyを削減の工夫: UNDERなVMへのevent(IO)が発生したら, 一時的に最高優先度(BOOST)でvCPUを実行 図の引用元: F. Zhou, M. Goel,
P. Desnoyers, and R. Sundaram. Scheduler vulnerabilities and attacks in cloud computing. arXiv:1103.0759v1 [cs.DC] 7
実験:レイテンシ計測 8 目的:(1)BOOSTの影響を定量化し,(2)あるVMが別 のVMのIOレイテンシに与える影響を調査. 方法:バックグラウンドで動作するVMで全体に 負荷をかけつつ,別VM間のping RTT計測 • 負荷1:iperfで別マシンと通信するNW-boundなタスク •
負荷2:yes > /dev/null を実行するCPU-boundなタスク 補足1: VM間通信はIOではないが,VMから見るとIOとほとんど同じ. 外乱が少ないメリットがある. 補足2: 誤差を減らすため,pingはRTタスクで実行,DVFSは無効化
結果:レイテンシ計測 0 5 10 15 20 25 30 35 no
BG w/ CPU BG w/ NW BG ping RTT (msec) mean max BOOSTのおかげで レイテンシ小 Tail Latencyが最悪 (×60 ~ ) Creditスケジューラ(パラメタはデフォルト) 9
Creditスケジューラ 問題点:BOOSTしたvCPU間の調停無し (同マシンに複数のIO boundなVMが存在する場合等) • Tail Latencyの大幅な悪化として観測 • BOOSTで割り込んだたくさんのvCPUが,OVERにならな い程度に長い時間の処理を続けるのが原因
• 固定のデフォルトタイムスライス(TS)が長すぎるのが元凶 • 短いタイムスライス は相対的にContext Switchコスト大 解決策(1) 短いTS (現代のCPUなら無難だが,限界あり) 解決策(2) BGのVMにCapを導入 (×Work Conservation) 10
Credit スケジューラ Capと Work Conservation • Cap: VM(vCPU)の1pCPUに対する実行可能時間 (割合)の上限(%単位表記) •
例: 4pCPU上であるVM(3vCPU)が, cap値 200[%] で動作 = 最大で全体の50%(200/(4*100))のpCPUを使用可能 (cap無しの場合,最大で全体の75% (3/4)のCPU利用可能) • Work Conservation(WC): Idleな(p)CPUがあるときほか のCPUで実行待ちのタスク(vCPU)が無い性質 Cap値を設けると メリット:CPUの”空き”が保証可能 デメリット:WCが満たされないため無駄が発生 11
結果:レイテンシ計測 0 5 10 15 20 25 30 35 30
ms no cap 5 ms no cap 30 ms cap 200(/400) ping RTT (msec) W/ NW BG mean max Creditスケジューラ(パラメタは調整) NW BG に対するcap: タイムスライス: 12
Credit2 スケジューラ • サポート開始 4.8~,デフォルト化 4.12~ • 変動タイムスライスでProportional Share(PS) •
タイムスライスは実行時に計算 • PS: 各VM(vCPU)はWeightに比例した時間割当て • Credit = Weightに応じ消費される実行時間 (UNDERとかOVERとかは存在しない) • よりレイテンシを抑えたいシステム向き※ ※Creditと比べて,スケーラブルという側面もある. 13 Wiki(更新されていない)曰く Credit2 is not in use by default.
Credit2 スケジューラ 基本アルゴリズム 全てのvCPUに 同量のCreditを配布 Credit最大vCPUを実行 実行時間分のCreditを消費して Runqをソート Credit が正の
vCPU存在? vCPUが存在 vCPUが存在しない 実行時間の決定アルゴリズム は次スライド 14
Credit2 スケジューラ タイムスライス決定アルゴリズム 1. Runqに他の実行待ちvCPUが… ある:c2t(実行予定vCPUのcredit - max(待ちvCPUのCredit)) ない:c2t(実行予定vCPUのcredit) 2.
1の値を次のパラメタで調整(上下限を設定) • ユーザ指定パラメタ: Cap, Rate Limit(=最短実行時間) • 静的なパラメタ: MIX(MIN)_TIMER ※ c2t(): credit を時間に変換する関数, Dom.のWeightに依存 最大credit 次に大きなcredit 15
Credit2 スケジューラ 基本アルゴリズム 全てのvCPUに 同量のCreditを配布 Credit最大vCPUを実行 実行時間分のCreditを消費して Runqをソート Credit が正の
vCPU存在? vCPUが存在 vCPUが存在しない 実行時間の決定アルゴリズム は次スライド 16
Credit2 スケジューラ 実行時間に応じたCredit消費 基本原理 • 大きなWeightをもつほどCreditの減りが遅い. • 最大Weightを持つvCPUは1nsで1credit消費 参考:Creditスケジューラは時間に応じた消費creditはす べてのVM共通だが,creditの分配量が異なる.
消費Credit = (実行時間(ns) * max(weights) + 補正)/ weight 17
Credit2 スケジューラ Event(IO)が発生したvCPUは… Runqに突っ込まれてCredit順にソートされ 最大CreditをもつvCPUを実行(tickle) 気持ち: • IO-boundなVMは待ち時間が多くcreditが減っていない ことが想定される. •
結果として,Event発生VMが優先されやすい. • 複数のVMが同時にIOしている状況に対応しやすい. ※厳密には,最短実行時間などパラメタで調整あり 18
結果:ping RTTの比較 0 0.5 1 1.5 2 2.5 no BG
w/ CPU BG w/ NW BG ping RTT (msec) mean max Credit2スケジューラ(パラメタはデフォルト) Tail の悪化が抑制 20
(再掲)結果:レイテンシ計測 0 5 10 15 20 25 30 35 30
ms no cap 5 ms no cap 30 ms cap 200(/400) ping RTT (msec) W/ NW BG mean max Creditスケジューラ(パラメタ調整) 21
今回話していないこと スケジューラの説明といいつつ… •ロードバランシング •スケーラビリティ •Realtime系のスケジューラ などの話題には触れていない. 22
まとめ • Xenのスケジューラの主要な2つを説明した. • Credit スケジューラ • 固定タイムスライス,Proportional Share •
IOレイテンシ削減のためにBOOST • 複数のBOOSTが同時に起こる環境ではレイテンシ大 • Credit2 スケジューラ • 変動タイムスライス,Proportional Share • レイテンシの観点で性能改善 23