マルチプロセッサ用リアルタイムOSの解説

第06回 ロードバランス(2)

今回は引き続き,マルチプロセッサ用OSで行われているロードバランスについて,Linuxの例をご紹介します.
SMP型のLinuxでは,以下の4つのタイミングでロードバランスを行っていました.

1.定期的
2.自CPUがidle状態になるとき
3.プロセスの起動時
4.プロセスの起床時

前回は,1と2のタイミングで行われるロードバランスについてご紹介しました.

ロードバランスの方針は以下の2つでした.
(1)CPU間の負荷が均一になるように,ロードバランスを行う
(2)キャッシュやTLBの有効活用のため,できるだけプロセスをマイグレートしない

今回は,3と4のタイミングで行われるロードバランスについてご紹介します.
前回ご紹介した,定期的に行われるロードバランスでマイグレート対象となるのは,すでにRUNキューにつながれているプロセスでした.プロセスの起動時に行われるロードバランスは,まだ実行状態でないプロセスをどこで起動するかということを考えます. この場合も,「(1) CPU間の負荷が均一になるように,ロードバランスを行う」という方針のもと,ロードバランスが行われます.そこで,プロセスを起動するサービスコールを発行したCPU(自CPU)の負荷が他のCPUと比較してある程度大きい場合は,他のCPUで起動した方が負荷が均一化されると判断して,他のCPUで起動します.しかし,できるだけ自CPUで起動するような工夫がされています.
スケジュールドメインに対して設定するフラグのうち,プロセス起動時のロードバランスに関係するものに,「SD_BALANCE_EXEC」フラグがあります.これが立っていると,「プロセスの起動時にロードバランスを行う.」という定義になります.ここでは,このフラグが立っているという前提で解説します.

<方針>
できるだけ,サービスコールを発行したCPUで起動する.
<マイグレート元>
自CPU(起動サービスコールを発行したCPU)
<マイグレート先>
最低負荷CPU(スケジュールドメイン内の一番負荷の低いCPU)




図 1 起動時に行われるロードバランス


では,どんな時にプロセスを移動するか細かく見てみましょう.





図 2 起動時に行われるロードバランスフロー

<STEP1>
自CPUの,実行可能なプロセスが1以下の場合は,自CPUで起動します.つまり,自CPUに,起動サービスコールを発行したプロセスしか存在しないのであれば,自CPUで起動します.

<STEP2>
自CPUの実行可能なプロセスが1以下でない場合,スケジュールドメイン内で一番負荷の小さいCPUを見つけます.その際に,自CPUの負荷が低く,他のCPUの負荷が高ければマイグレートはおきません.よって,次のような工夫をしています.

自CPUの負荷を見積もる場合→低めに見積もる
他CPUの負荷を見積もる場合→高めに見積もる

このように見積もってもなお,負荷に隔たりがある場合は,マイグレートが発生します.プロセスの起動時には,どれだけの負荷の隔たりがあれば,マイグレートが発生するのでしょうか?最低負荷を1.12倍しても,なお自CPUの負荷の方が大きければ,プロセスを最低負荷のCPUで起動します.すなわち,プロセスのマイグレートが発生します.
前回解説した,定期的に行われるロードバランスでは,最高負荷が自CPU負荷の1.25倍以上でないとマイグレートが行われませんでした.プロセスの起動時は,RUNキューにつながれているプロセスをマイグレートする定期的なロードバランスと比較して,キャッシュやTLBの影響が小さいため,比較的簡単にマイグレートが発生するようになっています.
ここでのロードバランスの対象は,プロセスが起床する場合です.つまり,これまでにどこかのCPUで実行していたということです.(例外もあります.)よって,キャッシュやTLBの影響は大きいといえます.ですから,できるだけ以前に実行していたCPU(元CPU)で起床するようにしています.以前実行していたCPUより,起床サービスコールを発行したCPU(自CPU)の負荷がかなり小さければ,自CPUで起床します.
スケジュールドメインに対して,設定するフラグのうちプロセス起床時のロードバランスに関係するものは,以下の2つのフラグです.
・SD_WAKE_AFFINE
キャッシュが有効でなければ,自CPUで起床
・SD_WAKE_BALANCE
プロセスの起床時にロードバランスを行う

<方針>
できるだけ,以前に実行していたCPUで起動する.
<マイグレート元>
元CPU(以前に実行していたCPU)
<マイグレート先>
自CPU(起床サービスコールを発行したCPU)





図 3 起床時に行われるロードバランス


では,次にロードバランスの処理について細かく見ていきましょう.




図 4 起床時に行われるロードバランスフロー

実際には,プロセスの状態によって場合分けされ,さまざまな処理が存在しますが,ここでは,ロードバランスに焦点をあてて解説します.ご了承ください.

<STEP1>
対象プロセスに対して,元CPUで起床サービスコールが発行された場合は,そのまま元CPUで起床します.

以降,負荷を見積もる場合に,できるだけ元CPUで起床する工夫がされています.
自CPUの負荷を見積もる場合→高めに見積もる
元CPUの負荷を見積もる場合→低めに見積もる

<STEP2>
上記方法で見積もった元CPUの負荷が0.5プロセス以下で,自CPUの同負荷が0.5プロセス以上であれば,元CPUで起床します.元CPUが忙しくなければ,元CPUで起床します.

<STEP3>
SD_WAKE_AFFINEフラグが立っている場合は,キャッシュが有効かどうかだけを確認し,自CPUで起床します.キャッシュが有効でない場合は,自CPUで起床します.
キャッシュが有効かどうか.という判断は,下記で行っています.

最後の実行状態中断時からの経過時間 < キャッシュが有効とみなせる時間(2,500ms)
この式を満たすときには,プロセスのデータがキャッシュに残っている可能性が大きいと判断しています.

<STEP4>
SD_WAKE_BALANCEフラグが立っている場合は,負荷のバランスによって,どちらのCPUで起床するかが決まります.元CPUの負荷が,自CPUの負荷より1.37倍以上高い場合に,マイグレートして自CPUで起床します.
定期的なロードバランスでは,1.25倍以上,起動の場合は1.12倍以上,そして,起床の場合は1.37倍以上の差がないとマイグレートが発生しません.プロセスの起床の場合は,よりキャッシュやTLBの影響を受けると考えられるからです.


前回と今回にわたって,Linuxにおけるロードバランスについて見てきました.4つのタイミングで行われるロードバランスには,下記の一貫した方針が見られました.

(1)CPU間の負荷が均一になるように,ロードバランスを行う
(2)キャッシュやTLBの有効活用のため,できるだけプロセスをマイグレートしない

この方針を実現するため,それぞれのタイミングによって,行われる処理にさまざまな工夫が施されていました.(表1)

表 1 各タイミングで行われるロードバランスの比較

  マイグレート元 マイグレート先 マイグレートが
行われる負荷の差
定期的 最高負荷CPU 自CPU 1.25倍以上
自CPUが
idle状態になるとき
最高負荷CPU 自CPU 1.25倍以上
プロセスの起動 自CPU 最低負荷CPU 1.12倍以上
プロセスの起床 元CPU 自CPU 1.37倍以上

Linuxカーネル2.6解読室
出版:ソフトバンククリエイティブ 
著者:高橋浩和/小田逸郎/山幡為佐久

詳解 Linuxカーネル 第3版
出版:オライリー・ジャパン
著者:Daniel P. Bovet, Marco Cesati
監訳:高橋 浩和
訳:杉田 由美子/清水 正明/高杉 昌督/平松 雅巳/安井 隆宏

Linuxソースコードは,下記を参考にさせていただきました.
http://hira-consulting.com/wiki/index.php

ありがとうございました.