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

第05回 ロードバランス(1)

 

前回まで,一般的なマルチプロセッサ用リアルタイムOSの概要について解説をしてきました. TOPPERS/FMPカーネルを具体的に見ていく前に,マルチプロセッサ用OSで行われているロードバランスについて,Linuxの例をご紹介したいと思います.Linuxで行っているロードバランス方針のご紹介が目的ですので,具体的なソースコードの解説はしません.ご了承ください.
※ロードバランス:複数のCPUで負荷分散を行うこと
※Linux 2.6.10を参考に書いています.(2009年4月時点での最新バージョン:2.6.29.1)
※参考文献,参考にしたWebページ等は,最後に記載しています.


ITORN系のOSでタスクと呼んでいるものを,Linuxではプロセスと呼びます.Linuxにおけるスケジュール方針の特徴は以下の2つです.

TTS方式による実行保証
応答性能向上と高いスループットという矛盾する要求に対応

TTS方式による実行保証
LinuxではTTS(Time Sharing System)方式でスケジュールを行っています.実行可能状態となったプロセスに,実行割り当て時間を与えます.そして実行状態となったプロセスは,実行割り当て時間を使い切ったら,他のプロセスに時間を明け渡します.そして,実行割り当て時間を使い果たすと,スケジューリングの対象外となります.実行割り当て時間が残っている実行待ちプロセスが1つもいなくなると,すべてのプロセスに新たに実行割り当て時間を割り当てます.必ずすべてのプロセスに実行権が割り当てられる保証をしています.ITRONでは,プリエンプティブな優先度ベーススケジューリングですので,とても大きな違いがあります.

応答性向上と高いスループットという矛盾する要求に対応
対話型プロセスは,システム利用者の体感速度を上げるため,応答性を良くし,数値演算プロセスにはスループットを上げる努力をする.という方針をとっています.対話型プロセスというのは,例えばシステム利用者の入力を待って,それに対して処理を行うといったプロセスです.では,対話型プロセス,数値演算プロセスの区別はどのように行っているのでしょうか?Linuxは,単位時間当たりの実行時間が少ないと対話型プロセスと判断します.つまりシステム利用者とのやりとりに時間がかかるため,単位時間当たりの実行時間が少なくなるという考え方に基づいています.

では,どのように対話型プロセスの応答性を保証しているのでしょうか?それは,対話型プロセスには高い変動優先度を割り当てることで実現しています.
Linuxのプロセスに与えられる優先度には,固定優先度と変動優先度があります.時間経過とともに変動優先度は変更されます.固定優先度は実行中に変化することはありません.この固定優先度と変動優先度の合計が実行優先度です.この実行優先度が最も大きなプロセスに実行件を与える仕組みになっています.対話型プロセスと判断すると,そのプロセスには高い変動優先度を与えることで,応答性を確保しようとします.また,実行割り当て時間の長さは固定優先度を基に計算します。高い固定優先度を持つプロセスほど長めの実行割り当て時間が与えられ、ほかのプロセスに比べて実行権を握ることのできる機会が増します。(図 1)

null

【図 1 Linuxの優先度】

ITORN系OSのレディキューに相当するものを,LinuxではRUNキューと呼んでいます.
LinuxのRUNキューは2種類のキューで構成されています.
・activeキュー:実行可能で,実行割り当て時間を待っているプロセスのキュー
・expiredキュー実行可能状態だが,実行割り当て時間を使い果たしてしまったプロセスのキュー

この2種類で対となりRUNキューを形成しています.LinuxのRUNキューは2種類のキューで構成されているところが,ITRON系OSとの大きな違いです.

実行可能なプロセスはRUNキューに登録されます。RUNキューには実行優先度ごとにヘッダが用意されており,実行可能なプロセスは該当する実行優先度にリンクされます.次に実行するプロセスは,プロセスが存在する最も高い実行優先度のヘッダから、先頭に登録されているプロセスとなります。この仕組みは,ITRON系OSと似ています.
実行割り当て時間を使い切ってしまったプロセスは,activeキューからexpireキューへ移動します.activeキュー上にプロセスがいなくなると,expireキューをactiveキューとして処理を続けます.
activeキュー,expireキュー両方にプロセスがいなくなると,idleキューに登録された処理(idleプロセス)が実行されます.idleプロセスはキューにつながれない,カーネルプロセスとなります.

null

図 2 LinuxのRUNキュー

マルチプロセッサシステムに対応したLinuxでは,CPUごとにこのRUNキューを持ちます.そして, RUNキュー間で負荷状態に偏りが出たときは、RUNキュー間で実行待ちプロセスのマイグレートを行い,バランスを取ります.→ロードバランス
マルチプロセッサ用のLinuxは,SMP型を対象としています.しかし,実際のマルチプロセッサはさまざまなハードウェアアーキテクチャを持っているため,ハードウェアの性質に合わせて処理方式を変更します.処理方式は,SMP型,NUMA型,ハイパースレッディング型の3つのパターンを選択できます.今回は,SMP型を選択した場合について解説します.

Linuxには,スケジュールドメインとグループという概念があります.スケジュールドメインとは,カーネルが負荷の均衡を保つべきCPUの集合体です.今回はロードバランスのみに着目しますので,ロードバランス方針を共有する集合体とも言えます.後述しますが,ロードバランスを行うかどうかは,このスケジュールドメインに対して設定します.そして,グループとは,スケジュールドメイン内のCPUの部分集合です.ロードバランス時の比較の単位となり,グループ間の負荷が均一化するように負荷分散されます.ここでは,SMP型について見ていきます.1グループに1つのCPUが所属すると考えてください.(図 3)


null



図 3 SMP型におけるスケジュールドメイン

ITRON系OSには,グループという概念はありませんので,今回は,図 4のようにグループという概念をはずして考えます.CPU間の負荷が均一化するようにロードバランスが行われると考えてください.


null

図 4 グループ概念を外したSMP型スケジュールドメイン

プロセススケジューラは各CPUで独立して動作します.つまり4コアのマルチプロセッサであれば,それぞれ4つのCPUにスケジューラが存在し,ロードバランスを行います.CPU間で負荷に大きな隔たりが出たときにロードバランスが行われますが,キャッシュやTLBの有効利用のため,プロセスは可能な限り特定のCPUに割り付けられて動作します.

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


Linuxでは,何を負荷とみてロードバランスを行っているのでしょうか?Linuxでは負荷(負荷因子)を,RUNキューに上にある実行可能なプロセスの数(nr_running)を元に算出しています.

負荷因子(cpu_load)の算出方法
cpu_load = (cpu_load + nr_running * 128) / 2

この値は,定期的(1ミリ秒ごと)に更新されます.実行可能なプロセス数の積分と考えてください.積分とするのは,一時的に増減するプロセス数の影響を受けないようにするためです.不定期にプロセス数が急増,急減するようなシステムの場合,プロセス数をそのまま負荷因子としてしまうと,プロセスのマイグレートが頻発する可能性があります.よって,負荷をプロセス数の積分とすることで,プロセス数の変化を長期的にとらえようとしています.前述したように,キャッシュやTLBの有効利用を考えると,プロセスは一度起動したら,できるだけ同じCPU上で動作する方が有利ですので,プロセスのマイグレートはできるだけしない方針です.そこで,Linuxではプロセス数の積分を負荷因子にしています.128倍しているのは,桁落ちを防ぐためです.

Linuxは以下の4つのタイミングでロードバランスを試みます.

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


これらのタイミングでロードバランスを行うかどうかは,スケジュールドメインに対して以下のフラグで設定します.


タイミング フラグ
定期的 SD_LOAD_BALANCE
CPUidle状態になるとき SD_BALANCE_NEWIDLE
プロセスの起動時 SD_BALANCE_EXEC
プロセスの起床時

SD_WAKE_AFFINE

SD_WAKE_BALANCE




まず,1.定期的に行うロードバランスについて見ていきます.
idleプロセスが実行している時,つまり実行可能状態のプロセスがいない場合は,1ミリ秒ごとに,他のプロセスが実行している場合は,64ミリ秒ごとにロードバランスを試みます.スケジュールドメインに対して設定するフラグのうち,定期的に行うロードバランスに関係するものに,「SD_LOAD_BALANCE」フラグがあります.これが立っていると,「定期的にロードバランスを行う.」という定義になります.ここでは,このフラグが立っているという前提で解説します.

◎方針
CPU間の負荷が均一になるようにロードバランスを行う
◎マイグレート元
最高負荷CPU
◎マイグレート先
ロードバランスを行おうとしている自CPU(負荷の小さいCPU)

定期的に行うロードバランスで,実際にプロセスのマイグレートが行われるのは,自CPUよりかなり負荷の大きいCPUが見つかった場合です.つまり,自CPUの負荷がある程度大きければ,負荷分散されていると判断し,プロセスのマイグレートは行われません.負荷の小さいCPUがトリガーとなって,プロセスのマイグレートが行われます.

null

図 5 ロードバランスを行うパターン

このように,ロードバランスを行うためにプロセスをマイグレートするのは,負荷の小さいCPUが行っています.負荷の高いCPUが自分のプロセスを追い出す.という方法も考えられるのですが,ロードバランスのためのプロセスのマイグレートという作業を,負荷の大きいCPUが行うと,さらに忙しくなってしまうので,負荷の小さいCPUが行う仕組みになっています.

できるだけ,プロセスのマイグレートを発生させないために,また,もし発生させるとしても,キャッシュやTLBの影響を少なくするための以下の工夫が見られます.

ポイント”蕾戮慮積もり方法
ポイント▲泪ぅ哀譟璽箸垢襯廛蹈札洪瑤了蚕佇法
ポイントマイグレートするプロセス数の選び方

処理の流れを図 6に沿って解説します.


null

図 6 Linuxの定期的に行うロードバランス

<STEP1>スケジュールドメイン内の負荷を計算
自CPUの負荷(this_load),一番負荷の高いCPUの負荷(max_load)を求めます.そして,スケジュールドメイン内のCPUの負荷平均(ave_load)を算出します.


ポイント 負荷の見積もり方法
定期的なロードバランスでは,自CPUの負荷が大きければプロセスのマイグレートが行われません.そして,できるだけプロセスのマイグレートをしたくないという方針ですので,負荷の見積もり方にも工夫が見られます.

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

自CPUの負荷を高めに見積もり,他CPUの負荷を低めに見積もることによって,プロセスのマイグレートがなるべく発生しないようにしています.このように見積もってもなお,CPU間に負荷の隔たりがある場合にはプロセスのマイグレートを行います.

<STEP2>マイグレート実行判断
自CPUの負荷が,平均以上であればプロセスのマイグレートを行いません.また,最高負荷CPUの負荷が,自CPUの負荷の1.25倍より大きくなければ,プロセスのマイグレートを行いません.つまり,自CPUの負荷が平均より小さく,かつ,最高負荷CPUの負荷が,自CPUの負荷の1.25倍以上大きい場合に,プロセスのマイグレートが行われます(図 7).できるだけプロセスをマイグレートしたくないので,最高負荷との差がある程度大きくないとロードバランスをしない.という考え方です.ある程度の差というのが,定期的なロードバランスの場合,1.25倍だということです.この数字は,プロセスが新たに起動する場合や,起床する場合には,また違っています.(次回ご紹介します.)いろいろな所に,Linux設計者の方々の工夫を垣間見ることができます.

null

図 7 定期的ロードバランスが行われる条件


<STEP3>マイグレートするプロセス数の算出
ここでは,マイグレートするプロセス数を算出します.

ポイント▲泪ぅ哀譟璽箸垢襯廛蹈札洪瑤了蚕佇法
ここでも,プロセスのマイグレートを頻発させないための工夫が見られます.プロセスをマイグレートしすぎることにより,再度マイグレートが発生するピンポンタスク現象が起きないような工夫がされています.

最高負荷と平均負荷の差と,平均負荷と自負荷の差の小さい方をマイグレートするプロセス数とします.
最高負荷と平均負荷の差の方が小さい場合は,この差をマイグレート数とします(図 8).つまり,最高負荷CPUの負荷を,平均負荷より下げないという工夫です.最高負荷CPUの負荷がロードバランスの結果,平均負荷より小さくなってしまうと, 次のロードバランス時に,プロセスを取り戻す必要があります.このようなプロセスのマイグレートの頻発を防いでいます.

null

図 8 マイグレートするプロセス数(a)

平均負荷と自負荷の差の方が小さい場合は,この差をマイグレート数とします.つまり,自負荷CPUの負荷を,平均負荷より上げないという工夫です(図 9).


null

図 9 マイグレートするプロセス数(b)

このように,プロセス数を決定することで,すべてのCPUの負荷を,平均負荷に近づけようとしています.

<STEP4>マイグレートするプロセス数の調整
ここでは,プロセスをマイグレートすることにより,全体として効率が良くなるかどうかをチェックします.詳細は省略します.


<STEP5>マイグレートするプロセスの決定
もっとも負荷の高いCPUから選択します.

ポイントマイグレートするプロセスの選び方
まず,expiredキューの優先度の高い順に選ばれます.expiredキューにあるプロセスは,activeキューにあるプロセスと比較して,近い将来実行されることがありません.また,キャッシュにデータが残っていない可能性が高いといえます.よって,CPUを変えることによる影響は少ないと考えられます.
expiredキューにプロセスがない場合は,activeキューからプロセスをマイグレートします.
activeキューにあるプロセスのうち,以下の3つの条件をすべて満たすプロセスが,マイグレート対象となります.

1,実行中でないプロセスである
2.マイグレート先CPUで実行することができるプロセスである
3.次の3つの条件のうち,少なくとも1つを満たすこと
   (a).マイグレート先CPUが待機状態である
   (b).そのスケジュールドメインが何度もロードバランスによるプロセスのマイグレートに失敗している.
   (c).対象プロセスのキャッシュがホットでない.

1と2の条件はすぐにご理解いただけると思います.
1.実行中のプロセスをマイグレートするには,そのプロセスのコンテキストを保存する必要があります.よって,CPUを変える影響は大きいので,マイグレートの対象とはなりません.
2.Linuxでは,プロセスごとに,実行できるCPUを表すビットマップを持っています.プロセスが,マイグレート先のCPUで実行できないのであれば,マイグレート対象にはなりません.
3の条件が少し複雑です.ここで詳細の解説はしませんが,条件c.に着目してください.プロセスのデータがキャッシュに残っているかどうかを判断基準にしています.キャッシュにデータが残っている可能性があれば,そのプロセスをマイグレートすることは不利であると判断し,マイグレート対象としません.
キャッシュにデータが残っている.という判断は,下記で行っています.

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

以上が1.定期的に行うロードバランスのポイントになります.Linux設計者のいろいろな知恵や経験がちりばめられていて勉強になります.


activeキューにも,expiredキューにもプロセスがいなくなった場合には,idleプロセスが起動し,idle状態となります.Linuxではidle状態になる前にも,ロードバランスを行います.その際に行われるロードバランスのポイントも,1.定期的に行われる場合と同じです.

次回は,3.プロセスの起動時,4.プロセスの起床時に行われるロードバランスのポイントについて解説します.
Linuxカーネル2.6解読室
出版:ソフトバンククリエイティブ 
著者:高橋浩和/小田逸郎/山幡為佐久

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

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

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