Document

クラスタ資源を柔軟に利用する
スケジューリングシステムの構築
2005.10.6
近山・田浦研究室
40391 斎藤 大
1
発表の流れ




背景と目的
関連研究
提案手法
現状と今後の予定
2
背景

高性能コンピュータやネットワーク環境の普及

リソースの占有が難しい(計算時間の測定等)
現状:メール送信等で対処
並列計算は他の干渉に弱い
一つのノードの処理速度が全体へ影響

• 多数のコンピュータを用いて並列計算
• 空きリソースを利用(ex. SETI@home)
3
背景


解決法の一つ:”Batch Queueing System”
→1ノードで1ジョブを実行
問題点
• 空きリソース利用ジョブや管理ツールの扱い困難
• 並列計算で多数のノードを獲得するのは大変
• ジョブ投入から実行までに待ちが存在
•
→対話型プログラムが実行不可
複数のシステムを介するとデッドロックの可能性
4
目的

ジョブの実行方式が調整出来る

空きリソースの有効活用が出来る
並列計算に対応する

• ノードを占有したい
• 邪魔が入ってもいいから早く実行したい
柔軟なリソース利用が可能な
スケジューリングシステムの構築
5
関連研究:Batch Queueing System


ユーザのジョブ投入とマシンのジョブ実行の
仲立
マシン状況の監視
Job
Queue
Job
Job
Job
Job
6
主なBatch Queueing System

Sun Grid Engine

Condor [Miron 1986]

Portable Batch System
• ユーザ、プロジェクト毎にリソース使用量指定可
• Match-Makingによるスケジュール
• FIFO+リソースが空いていれば小規模ジョブ実行
• Starving Jobメカニズム
7
提案手法



全ジョブが100%のリソースを求めはしな
いはず
ある程度長い間隔で実行ジョブを選択して、
リソース(=CPU使用率)を振り分ける
実際の実行はOSのTime Sharingに任せる
CPU1
80
CPU2
80
60
100
40
100
60
60
60
Time
8
提案手法

ジョブ毎にCPU使用率を定め、規定値を超
えないようにジョブを選択
• CPU使用率が高い場合ほぼ単独で実行
• CPU使用率が低い場合複数実行可能



リソースの振り分けにniceを用いる
並列処理の同期(CoScheduling)にも対応
まずは、一つのLinuxマシン上で動作する、
リソース振り分けシステムの実装を目指す
9
システムの流れ
1.
プロセス実行状況の取得


2.
3.
4.
プロセスの実行時間を確認
新しいジョブが実行されていないか監視
実行プロセスの選択
nice値を計算してプロセス実行
一定時間休止、1へ戻る
10
各プロセスのパラメーター



CPU_util:CPU使用率
max_run_time:連続実行時間
unstoppable_flag:停止不可プロセス
max_run_time
CPU_util
40
Time
11
スケジューリング

定期的にジョブ選択を実行
CPU使用率が低い、連続実行時間が短い
ジョブを優先する
weight × max_run_time × (実行回数+1)

実行回数は一定期間後初期化する


• weight :CPU_utilにより定められる重み
• 今回実行した場合の合計実行時間に重み付け
12
リソース振り分け



実行ジョブ内でリソース振り分け
niceを用いて実現
Linux2.4のスケジューリング
• クォンタムの長さでCPU使用量管理
CPU
Job1:
Job2:
13
リソース振り分け – nice値の決定

niceはクォンタムの長さを変えるコマンド
• 20 - nice値 = クォンタムの長さ(tick)
-19≦nice値≦20

CPU使用率の比→nice値の比
• CPU使用率が最大のプロセスのnice値=0にする
• 他のプロセスのnice値は相対的に決定
CPUi
nicei  20  20
max(CPU )
14
リソース振り分け – niceの性能
•
•
for文を回すプログラム
ほぼ予想通り
予想CPU使用率[%]
nice値
実際のCPU使用率[%]
60
20
20
40
30
20
0
14
14
0
5
10
58.8
20.6
20.2
43.1
33.4
22.2
様々な種類のプロセスでnice –n 19の性能測定
•
•
nice –n 19プロセスを
通常プロセスと同時に実行
実行時間比を計測
Normal
Normal+nice19
Normal+nice19x2
1.6
1.4
1.2
実行時間比
1
0.8
0.6
0.4
LU
.A
.
4
4
B.
IS
.
4
.A
.
.B
CG
EP
.4
0
E
極端なCPU使用率は困難
0.2
ER
AG

CPU使用率操作
合計90%
AV

合計100%
15
本システムの利点
1.
2.
3.
4.
空きリソースの有効活用
プロセスの実行状況を見て管理下に置く
→どのようなジョブ実行方式にも対応
Batch Queueing System風の利用
CPU_utilを大きくすることで実現
max_run_time次第でFIFOやRR
unstoppable_flagにより対話型ジョブも対応
16
現状と今後の計画

現状

今後の計画
• 実装方針が定まったのでこれから実装に入る
• シングルプロセッサで動作するシステムの実装
• 並列処理(CoScheduling)への対応
• 空きノード管理&ジョブ割り当てシステム
17