ユーザレベルでのディスク帯域制御機構

1
ユーザレベルでのディスク帯域制御機構
山 田 浩 史†
河
野
健
二††
アプリケーションの多様化に伴い，OS に要求される資源管理ポリシーも多様化してきている．し
かし，資源管理ポリシーはカーネル内にハードコードされているため，そのポリシーの変更は容易で
はない．また，カーネルの変更を要する資源管理ポリシーは転用が難しく，広く展開しにくい．そこ
で，ユーザレベルでの資源管理機構の実現を目指し，本論文では，ディスク帯域の制御機構を提案す
る．本機構は，OS の動作を推測しながらファイル I/O を制限することで，ディスク帯域の制御を
実現している．また本機構は，ユーザレベルで実現されているので，ポリシー変更や転用が容易であ
る．本機構のプロトタイプを Linux2.4.27 上に実装し，実験を行ったところ，±2.0%以下の精度で
ディスク帯域を制御できることがわかった．また，実際のアプリケーションのディスク帯域も閾値以
下に制限することができた．
1. は じ め に
の技術を他の OS に転用することは容易ではない．
ユーザレベルでの柔軟な資源管理機構の実現を目指
アプリケーションの多様化に伴い，オペレーティン
し，本論文ではユーザレベルでのディスク帯域制御機
グシステム (OS) に要求される資源割当てポリシー
構を提案する．本機構は，ユーザレベルで OS の動作
も多様化している．SETI@home1) などに代表される
を推測しながら，プロセスのファイル読み書き (ファ
PC グリッド環境では，個人の所有する計算機資源を
イル I/O) サイズを制限することで，ディスク読み書
貸し出すため，貸し出す資源の配分をユーザが適切に
き (ディスク I/O) の帯域幅制御を実現している．ファ
制御できることが望ましい．たとえば，CPU 時間 10
イル I/O の制限は，Rate-Windows8) という機構を用
%，ディスク帯域 3 MB/s まで，ネットワーク帯域 5
いて実現する．本機構は，カーネルやアプリケーショ
MB/s までといった制限が可能であることが望まれる．
ンの変更を必要とせず，広く展開できることが期待さ
また，ウィルススキャンやバックアップなど重要度
れる．
の低いアプリケーションも，ユーザが適切に資源配分
本機構のプロトタイプを Linux2.4.27 上 に実装し
を調整できることが要求される．なぜなら，これらの
た．また，プロセスの発行したファイル I/O サイズと
アプリケーションは，ユーザの作業を妨げる可能性が
ディスク I/O サイズを測定できるように Linux2.4.27
あるからである．
を拡張し，実験を行った．実験より，ディスク帯域を
1 台の計算機を仮想的に複数のホストとして利用す
閾値の ±2 %の範囲内に制限できることがわかった．
る仮想ホスティング環境でも，資源配分を柔軟に制御
さらに，実際のアプリケーションのディスク帯域制御
できることが望ましい．なぜなら，ホスティング・サー
も行えることを確認した．
ビスの契約内容に応じ，各仮想ホストが利用できる資
以下，2 章ではディスク帯域を制御する困難さにつ
源配分は異なることが多く，仮想ホストごとに利用で
いて述べ，3 章で本機構の設計，4 章では実装を示す．
きる資源量を適切に制御できることが望まれているか
5 章で実験結果を示し，6 章では関連研究について述
らである．
べ，7 章で本論文をまとめる．
従来の OS の多くは，公平性を重視した資源割当て
ポリシーを採用しており，そのポリシーもカーネル内
2. ディスク帯域制御の困難さ
にハードコードされているため，資源割当てポリシー
2.1 ファイル I/O とディスク I/O の違い
を変更することは容易ではない．Solaris9 などの商用
ディスク帯域制御は，プロセスの発行するファイル
OS では仮想ホスティングのための資源管理機構2) を
I/O を制御するだけでは行えない．なぜなら，ファイ
備えているが，カーネル内で実現されているため，そ
ル I/O とディスク I/O では，発行量やタイミングが
異なるからである．たとえば，ファイルを読み込んで
† 電気通信大学大学院 電気通信学研究科 情報工学専攻
†† 電気通信大学 電気通信学部 情報工学科
も，ディスク読み込みが起きない，またはファイル読
み込みサイズと同サイズのディスク読み込みが必ずし
2
も起きるわけではない．また，ファイルにデータを書
する．
き込んでも，すぐにそのデータはディスクに書き込ま
プロセスのディスク帯域を制御するには，2.1 節で
れるわけではない．これは以下に列挙する OS の動作
述べたファイル I/O とディスク I/O との違いを考慮
に起因する．
する必要がある．そこで，RW ではファイル I/O に
• ディスクキャッシュ： ディスクキャッシュに存在
するファイルを読み込むときには，ディスク I/O
は発行されない．
• ブロック単位のディスクアクセス： ファイルを
読み込むときには，ファイル読み込みサイズをブ
ロックサイズに丸め上げたサイズのディスク読み
対するディスク I/O の比率を設定し，この比率を用
いて発行されるディスク I/O を推測する．たとえば，
この比率が 0.5 であれば，RW は，100KB のファイ
ル I/O を 50 KB のディスク I/O とみなす．比率の更
新は，プロセスがファイル I/O を発行する度に行う．
2.2.2 Rate-Windows の問題点
込みが起こる．そのため，ファイル読み込みサイ
RW のディスク帯域の制御法には問題点がある．RW
ズと実際に起こるディスク読み込みサイズとの間
では，ファイル I/O に対するディスク I/O の比率を
にズレが生じる．
• ファイル先読み ： ファイルを読み込むときには，
算出するために，プロセスの発行したディスク I/O サ
イズを取得する必要がある．しかし，ユーザレベルで
ファイルの先読みが行われる．そのため，この場
はシステム全体で発行されたディスク I/O サイズし
合にも，ファイル読み込みサイズと実際に起こる
か取得できない．そのため，複数のプロセスを同時に
ディスク読み込みサイズとの間にズレが生じる．
制御すると正しく比率が定まらず，ディスク帯域を適
• 非同期書き込み ： OS は汚れバッファが一定数を
切に制御できなくなる．
越えたときに，まとめてディスクに書き込む．そ
これを具体的に示すために，RW をユーザレベルに
のため，ファイル書き込みを発行しても連動して
実装して実験を行った．5 章に示す実験と同じ環境を用
ディスク書き込みが起きない．
意し，同時に 2 つのアプリケーションを起動して，そ
2.2 既存の手法の問題
れぞれディスク帯域を制限した．用意したアプリケー
ディスク帯域を制御する手法として，Rate-Windows8)
ションは以下のとおりで，図 1 に示すようなファイル
(RW) が提案されている．RW は，プロセス単位でファ
I/O，ディスク I/O を発行する．
イル I/O を制限できる．さらに，ディスク帯域の制
• tar : 200MB の tar ファイルを展開する．ファイ
御も行う．RW は，カーネルモジュールとして実装す
ル I/O に対するディスク I/O の比率は約 1.0 で
る手法だが，容易にユーザレベルへと移植できる．以
下，RW の仕組みとその問題点を述べる．
2.2.1 Rate-Windows
RW では，ファイル I/O スループットがあらかじ
め定めた閾値を越えないようにプロセスを制御する．
RW は，プロセスがファイル I/O を発行する度に 2
ある．
• make : apache をコンパイルする．ファイル I/O
に対するディスク I/O の比率は約 0.4 である．
それぞれディスク帯域を 10MB/s，400MB/s で制
限した．また，過去 1 秒間のデータを元にスループッ
トを計算した．
種類の値を記録する．1 つは，ファイル I/O サイズで
結果を図 2 に示す．縦軸にスループット，横軸に
ある．もう 1 つは，前回プロセスがファイル I/O を
経過時間をとっている．元々，make の使用するディ
発行してから経過した時間である．これらの記録を用
スク帯域幅はほぼ閾値以下であるにもかかわらず (図
いて，スループットを計算する．この値は，あらかじ
1(b))，RW でディスク帯域を制御すると，make の
め決められた期間，たとえば 1 秒間，5 秒間という期
ファイル I/O に無駄な制限がかかっていることがわ
間のデータを元に算出される．
かる (図 2(b))．これは，tar の I/O サイズが make
たとえば，閾値を R KB/s とし，T 秒間のデータ
のそれに比べて極めて大きく，ファイル I/O に対す
を元にスループットを計算しているとする．今，過去
るディスク I/O の 比率がほぼ tar の動作によって決
T 秒間内のファイル I/O サイズは B KB であった．
まるからである．これにより，make の ファイル I/O
≤ R であれば，何もしない．そうでなけ
ここで， B
T
に対するディスク I/O の比率が正しく定まらず，正
れば，つまり，スループットが閾値を越えていたなら
しくディスク I/O を推測できない．
− T 時間だけ，プロセスの実行を停止する．停
ば， B
R
止を行うことで，過去 T 秒間の平均スループットが
R KB/s となる．このように，RW はプロセスを制御
3. ディスク帯域制御機構
2.1 節で述べたように，ディスク帯域を制御するに
3
35000
2500
File I/O
Disk I/O
30000
File I/O
Disk I/O
Bandwidth [KB/s]
Bandwidth [KB/s]
2000
25000
20000
15000
10000
1500
1000
500
5000
0
0
0
10
20
30
40
Elapsed Time [sec]
50
0
20
40
(a) tar
160
制限なし
2500
File I/O
Disk I/O
File I/O
Disk I/O
2000
Throughput [KB/s]
10000
Throughput [KB/s]
140
(b) make
図1
12000
60
80 100 120
Elapsed Time [sec]
8000
6000
4000
1500
1000
500
2000
0
0
0
10
20
30
40
50
60
Elapsed Time [sec]
70
80
90
0
(a) tar(10MB/s で制限)
50
100
150 200 250 300
Elapsed Time[sec]
350
400
450
(b) make(400KB/s で制限)
図2
RateWindows で制限
は，ファイル I/O とディスク I/O の違いを考慮する
必要がある．
RW では，システム全体のディスク I/O を見て，
サイズ間にズレが生じるので，それを補整する．
• 非同期書き込み : OS は汚れバッファが一定数を
越えると，1 度にデータをディスクに書き込む．
個々のファイル I/O からどれだけのディスク I/O が
そのため，指定した間隔での平均ディスク I/O ス
発行されるかを推測する．これに対して，本機構では，
ループットが閾値を越えてしまう可能性がある．
個々のファイル I/O が ディスク I/O を伴うかどう
そこで，ディスク書き込みが起こる間隔での平均
かを判定する．これにより，複数プロセスの制御が可
ディスク I/O スループットが閾値を越えないよ
能になる．
うにファイル I/O を制限する．
本機構では，次のように OS の動作にあわせてファ
本機構では，プロセスがファイルを読み込むときに
イル I/O を制御することで，ディスク帯域の制御を
キャッシュ判定という判定を行う．キャッシュ判定は，
達成する．ファイル I/O の制御には，RW を用いる．
ファイルがディスクキャッシュ内に存在するか否かを
• ディスクキャッシュ : ディスクキャッシュ内に存
判定する．この判定でファイルがディスクキャッシュに
在するファイルの読み込みは，ディスク読み込み
存在しないと判定したときにだけ，RW を用いてファ
が起きないので制御を行わない．逆に，ディスク
イル読み込みを制御する．
キャッシュに存在しないファイルの読み込みを制
御するようにする．
ファイル読み込みの制御を行うときには，丸め上げ
とチェックウィンドウというファイル読み込みサイズ
• ブロック単位のディスクアクセス，ファイル先読
とディスク読み込みサイズ間のズレを補整する手法を
み : ファイル読み込みサイズとディスク読み込み
用いる．丸め上げはブロック単位のディスクアクセス
4
いる．
5MB
1.25
2.5
3.75
FILE
4.1 ラッパー
ラッパーは，動的リンクライブラリとして実装し，
read
read
read
環境変数 LD PRELOAD を用いてフックを実現して
read
図3
キャッシュ判定
いる．これにより，既存のアプリケーションを変更す
ることなく，ディスク帯域を制御できる．
によるズレを，チェックウィンドウはファイル先読み
4.2 Rate-Windows
によるズレを補正する．この 2 つの手法を用いて，実
ラッパーは，プロセスが発行したと推測されるディ
際に起こるディスク読み込みサイズを算出する．ファ
スク I/O サイズをモニタプロセスに TCP 通信で通
イル書き込みは，そのままディスク書き込みとして制
知する．モニタプロセスは通知を受けると，2.2.1 節
御を行う．
で示した計算を行い，適切な停止時間を算出する．そ
3.1 キャッシュ判定
して，その停止時間をラッパーに通知する．ラッパー
ユーザレベルでキャッシュ判定を行う手法として，
は通知された時間だけ sleep する．
OS の内部状態を推測する gray-box3) という手法を
4.3 チェックウィンドウ
用いる．この手法は，ファイルの読み込みにかかる時
Linux2.4 系はファイル先読みを行う．Linux2.4 系
間をもとにキャッシュ判定を行う．ファイルを 1 バイト
のファイル先読み機構は，同期的な先読みと非同期的
読み込む時間を計測し，短時間で読み込めれば，ファ
な先読みとに分かれている．プロトタイプでは，同期
イルはディスクキャッシュに存在すると判定する．そ
的な先読み部分のみを実装した．
うでなければ，存在しないと判定する．
本機構ではこの手法を利用する．まず，ファイル読
同期的な先読みでは，ファイル読み込みが起こると
1 ページ分の先読みを行う．なので，チェックウィンド
み込みが起こると，読み込む地点から 5MB のファイ
ウは読み取りサイズを 4KB(ページサイズ) で丸め上
ルデータ領域を図 3 のように 4 等分する．そして，分
げ，さらに +4KB のディスク読み込みが発行される
割してできた領域についてキャッシュ判定を行う．こ
とみなす．そして，このように算出したディスク I/O
れは，部分的にディスクキャッシュに存在する可能性
サイズをモニタプロセスに通知する．
があるので，それを検出するために行う．
本機構の判定手法を用いると，たとえば，短時間で
5. 実
験
読み込めた地点が 1.25MB，3.75MB 目であれば，0∼
本機構を用いて，ディスク帯域の制御を確認するた
1.25MB 目，2.5∼3.75MB 目の領域はディスクキャッ
めに実験を行った．実験は，表 1 の性能を持つ PC/AT
シュ内に存在すると判定する．
互換機上で行った．互換機上では，プロセスごとにファ
3.2 ズレの補整
イル I/O サイズ，ディスク I/O サイズを測定できる
丸め上げは，OS のブロック単位のディスクアクセ
よう改良した Linux2.4.27 が稼働している．また，過
スによるズレを補正する手法である．丸め上げは，プ
去 1 秒間のデータを元にスループットを計算している．
ロセスがファイルを全て読み込むと，ファイルサイズ
5.1 Micro-Benchmark
をブロックサイズで丸め上げた値を計算し，その値を
以下のようなファイル I/O を発行するジョブを用
実際のディスク読み込みサイズとする．
チェックウィンドウは，OS のファイル先読みによ
るズレを補正する手法である．チェックウィンドウは，
ファイル先読みをエミュレートし，実際のディスク読
み込みサイズを計算する．
4. 実
装
意し，ディスク帯域を 5MB/s に制限した．
• sequential read : 200MB のファイルをシーケン
シャルに読む．
• stride read : 5 個の 200MB のファイルを 12KB
おきに 1 バイト読む．
• random read : 10 個の 200MB のファイルをラ
表1
本機構のプロトタイプを Linux2.4.27 上に実装し
実験環境
た．本機構は RW を改良した機構であり，モニタプロ
構成要素
構成
セスと，read() と write() のラッパーから構成される．
CPU
メモリ
HDD
AthlonXP 1.4GHz
512MB
60GB，7200rpm，UltraATA100
Linux2.4 系では，ページサイズ単位でディスクから
ファイルデータを読み込むので，4KB で丸め上げて
5
7000
7000
File I/O
Disk I/O
Throughput [KB/s]
Throughput [KB/s]
6000
File I/O
Disk I/O
6000
5000
4000
3000
2000
5000
4000
3000
2000
1000
1000
0
0
0
10
図4
20
30
Elapsed Time[sec]
40
0
50
20
図7
sequential read の制御
7000
File I/O
Disk I/O
6000
40
60
80
100
Elapsed Time[sec]
ファイル生成の制御
File I/O
Disk I/O
12000
Throughput [KB/s]
Throughput [KB/s]
10000
5000
4000
3000
2000
8000
6000
4000
2000
1000
0
0
0
20
40
60
80
100
120
140
0
10
20
Elapsed Time[sec]
図5
図8
stride read の制御
120000
40
50
60
70
80
tar の制御 (10MB/s)
2500
File I/O
Disk I/O
100000
File I/O
Disk I/O
2000
Bandwidth [KB/s]
Throughput [KB/s]
30
Elapsed Time[sec]
80000
60000
40000
1500
1000
500
20000
0
0
0
50
図6
100
150
Elapsed Time[sec]
200
250
random read の制御
ンダムに読む．
0
50
図9
100
150
Elapsed Time[sec]
200
tar の制御 (10MB/s)
で実現していることによる精度上の誤差であると考え
• ファイル生成 : 400MB のファイルを生成する．
られる．実験より，本機構は +1.5%，−1.4%の精度
結果を図 4∼7 に示す．縦軸にスループット，横軸
でディスク帯域を制御することがわかった．
に経過時間をとり，閾値をプロットしている．図より，
本機構が，設定した閾値以下にディスク帯域を制限し
ているのがわかる．
また，ディスク帯域は，閾値の +1.5%，−1.4%の
間で制御されている．これは，本機構をユーザレベル
5.2 Macro-Benchmark
実際のアプリケーションのディスク帯域を，本機構
を用いて制御した．制御したアプリケーションは次の
とおりである．
• tar : 200MB の tar ファイルを展開する．
6
5000
File I/O
Disk I/O
Throughput [KB/s]
4000
3000
2000
1000
0
0
20
40
60
80
Elapsed Time[sec]
100
120
図 10 grep の制御 (3MB/s)
2500
File I/O
Disk I/O
12000
2000
Throughput [KB/s]
10000
Throughput [KB/s]
File I/O
Disk I/O
8000
6000
4000
1500
1000
500
2000
0
0
0
10
20
30
40
50
60
Elapsed Time [sec]
70
80
90
0
(a) tar(10MB/s で制限)
50
100
150
Elapsed Time[sec]
200
250
(b) make(400KB/s で制限)
図 11 本機構で制限
• make : apache をコンパイルする．
• grep : Linux 2.4.27 のカーネルソースツリーか
ら hoge という文字列を探す．
6. 関 連 研 究
近年のアプリケーションの多様化に伴い，さまざまな
tar，make，grep のディスク帯域を 10MB/s，400KB/s， 資源管理方式が提案されている．Proportional-Share
3MB/s で制限した．結果を，図 9∼10 に示す．図 9
資源管理方式として，lottery scheduling11) を拡張し，
∼10 より，実際のアプリケーションのディスク帯域も
チケットのやりとりで資源を柔軟に管理する手法が提
閾値以下に制限されているのがわかる．実験より，本
案されている9) ．他にも，lottery scheduling の資源
機構を用いれば，実際のアプリケーションのディスク
分配の精度を上げる stride scheduling10) や素早くス
帯域を制御できることがわかった．
ケジューリングを行う VRTT7) などがある．以上の
5.3 同 時 制 御
手法は，カーネルの変更を要するので，本手法とは異
tar と make の同時制御を本機構でも行った．結果
なる．
を図 11 に示す．図 11(b) より，RW に比べて，無駄
文献 4) では，資源を制限するサンドボックスをユー
な制限をせずにディスク帯域を制御していることがわ
ザレベルで実装する手法が提案されている．提案サン
かる．実験より，本機構は同時に複数プロセスのディ
ドボックスでは，CPU 時間，メモリ，ネットワーク
スク帯域を制御できることがわかった．
帯域を制限できるが，ディスク帯域は制限できない．
MS Manners5) では，プロセスの進捗度を元に，プ
ロセスをスケジューリングする手法が提案されている．
7
MS Manners では，制限する資源を指定できないた
め，本手法のようにディスク帯域のみを制限すること
は難しい．
文献 6) では，ユーザレベルで CPU スケジューラ
を実現する手法が提案されている．本手法と組み合わ
せることで，CPU 時間とディスク帯域をユーザレベ
ルで制御することが可能になる．
7. お わ り に
ユーザレベルでの資源管理機構を目指し，本論文で
はディスク帯域の制御機構を提案し，その実現方法を
示した．提案機構は，OS の動作を推測しながらファ
イル I/O を制限する．また提案機構は，カーネルや
アプリケーションを変更せず，ポリシー変更や転用も
容易である．本機構のプロトタイプを Linux2.4.27 上
に実装し，実際にプロセスのディスク帯域を制限でき
ることを確認した．
今後は，提案機構のオーバーヘッドを調べ，有用性
を確かめたい．
参
考
文
献
1) The Search for Extraterrestrial Intelligence.
http://setiathome.ssl.berkeley.edu/.
2) Solaris 9 Resource Manager (White Paper).
http://jp.sun.com/products/wp/solaris9/srm.pdf,
2002.
3) Andrea C. Arpaci-Dusseau and Remzi H.
Arpaci-Dusseau. Information and Control in
Gray-Box Systems. In Proceedings of the 18th
ACM Symposium on Operating Systems Principles (SOSP ’01), pp. 43–56, October 2001.
4) Fangzhe Chang, Ayal Itzkovitz, and Vijay
Karamcheti. User-level Resource-constrained
Sandboxing. In Proceedings of 4th USENIX
Windows System Symposium (WSS 2000), pp.
25–36, August 2000.
5) John R. Douceur and William J. Bolosky.
Progress-based regulation of low-importance
processes. In Proceedings of the 17th ACM
Symposium on Operating Systems Principles
(SOSP ’99), pp. 247–260, December 1999.
6) Travis Newhouse and Joseph Pasquale. A
User-Level Framework for Scheduling within
Service Execution Environments. In IEEE International Conference on (SCC ’04), pp. 311–
318, September 2004.
7) Jason Nieh, Chris Vaill, and Hua Zhong.
Virtual-Time Round-Robin : An O(1) Proportional Share Scheduler. In Proceedings of
2001 USENIX Annual Technical Conference,
pp. 245–259, June 2001.
8) Kyung D. Ryu, Jeffery K. Hollingsworth, and
Peter J. Keleher. Efficient Network and I/O
Throttling for Fine-Grain Cycle Stealing. In
Proceedings of the ACM/IEEE SC2001 Conference (SC ’01), November 2001.
9) David G. Sullivan and Margo I. Saltzer. Isolation with Flexibility: A Resource Management
Framework for Central Servers. In Proceedings
of 2000 USENIX Annual Technical Conference,
pp. 337–350, June 2000.
10) Cart A. Waldpurger and William E. Weihl.
Stride Scheduling: Deterministic ProportionalShare Resource Managemet. Technical report,
MIT/LCS/TM-528, Massachusetts Institute of
Technology, 1995.
11) Carl A. Waldspurger and William E. Weihl.
Lottery Scheduling: Flexible ProportionalShare Resource Management. In Proceedings
of the First Symposium on Operating System
Design and Implementation, pp. 1–12, November 1994.