Lab/SSS-PC/研究方針 の履歴(No.4)

• 履歴一覧
• ソース を表示
• Lab/SSS-PC/研究方針 は削除されています。
  • 1 (2005-07-11 (月) 06:39:09)
  • 2 (2005-11-24 (木) 17:28:11)
  • 3 (2006-01-09 (月) 02:44:05)
  • 4 (2006-01-09 (月) 10:27:17)
  • 5 (2006-01-11 (水) 08:34:55)
  • 6 (2006-01-11 (水) 09:55:07)
  • 7 (2006-01-13 (金) 02:50:27)
  • 8 (2006-01-15 (日) 16:39:16)
  • 9 (2006-01-16 (月) 15:54:56)

---

研究方針

• 研究関係Wiki・SSS-PCへ戻る

PCクラスタ向けOS「SSS-PC」のための負荷分散スケジューラの設計

卒論本体に関してはLab/卒業論文に。

設計

本スケジューラーは、各ノードの負荷情報に基づき、タスクを適当なノードにマイグレーションすることによってロードバランシングを実現する。

負荷情報の取得方法・内容

情報開示機構を用いる。

参考資料：Lab/SSS-PC/情報開示機構

検討課題

• マイグレーションのコストをどうやって設計に生かすか？
• IDMにコストはかからないのか？

アルゴリズム

ここではアルゴリズムについて検討する。スケジューラーは自ノード上のタスクを他ノードへマイグレーションするかどうか判断するが、以下の3点での判断が必要となる。

1. マイグレーションは必要かどうかの判断
2. マイグレーションさせるタスクの選択
3. マイグレーション先の選択

1.については、自ノード全体の負荷と他の各ノードそれぞれの負荷情報を比較し、他のノードより著しく高いと判断された場合にはマイグレーションすべきと判断する必要がある。

1.他ノードと自ノードの負荷状態を比較し、最も負荷の低いノードを選ぶ

• short/middle/longを逐次比較するか、足したり掛けたりするか
• longは見なくていいんじゃね？

2.については、自ノードのうち「他ノードに移動させると負荷が平均化されるタスク」を選択する必要がある。

負荷が極端に大きいタスクを他ノードへ移動させると、移動先ノードの負荷が大きくなりすぎて再びマイグレーションが発生し、これを繰り返すことでマイグレーションばかりが発生する可能性がある。

逆に負荷が極端に小さいタスクを他ノードへ移動させると、負荷の変化があまり起こらないため何度もマイグレーションが発生する可能性がある。

よって、「マイグレーションを行うと自ノード・相手先ノード共に負荷が平均化されるタスク」を選択する必要がある。

2.移転対象のタスクを決定する

• 生存時間の短いタスクを優先的に移転させる（LIFO）
  • 生存時間の取得方法は？寿命？
• タスク毎に負荷を測定できるならそのデータも使う
  • 測定できるのか？
  • どのように使う？
• shell等のシステムに関わるタスクは移転させない
  • 判断基準は？（ready状態かどうか？）
  • 自分自身を除外させる必要がある
  • readyなタスクが1つしかないなら移転させない（12/01付資料より）
  • priorityの値が高いなら移転させない（11/25付資料より）

3.については、負荷が最も小さいノードを選択すべきなのかそうでないのかを検討すべきである。

負荷が最も小さいノードを選択するようにすると、複数のノードから一斉にタスクが移動して一気に負荷がかかる可能性や、移動するタスクの負荷の大きさによってノード毎にばらつきが出る可能性がある。

マイグレーションとシグナル

ここではマイグレーション実行に必要なシグナルについて検討する。

マイグレーションの仕組みはスケジューラ側とタスク側に分けて検討する必要がある。

1. スケジューラはシグナルを発行する
2. 各タスクはシグナルをキャッチしてマイグレーションを実行する

スケジューラ

タスク

タスクへどうやってシグナルをキャッチ＆マイグレーション実行機能を組み込ませるか。

1. ソースレベルで組み込ませる
   1. 誰が使うんだろう……。
2. ライブラリを用意する
   1. ↑どうやって？ヘッダを書いてインクルードさせる？
3. ラッパーアプリケーション？？
   1. 先にマイグレ機構を搭載したプログラムを起動し、そこから該当プログラムを起動させる？

外部仕様

• スケジューラは各ノードに常駐
  • スケジューラそのものもタスクである
• タスクはライブラリ等でスケジューラからのシグナルを受け取れるようにする

キーワード

SSSPCのロードバランシング

ロードバランシング

• ロードバランシング
  • 並列に運用されている機器間での負荷がなるべく均等になるように処理を分散して割り当てること。

SSS-PC

SSS-PCの特徴より引用：

• 情報開示機構: IDM
  • この情報をメモリ参照して、今後の負荷分散戦略や実行タイミングの検討判断を ユーザアプリケーション自らが行います。
• 自由市場原理（FMM）に基づく負荷分散方式の採用
  • マシン間の負荷分散方式には自律分散方式の一つである自由市場原理に基づくスケジューリング方式を考案し実装している。開示されたシステムの資源使用状況を基に各アプリケーションは自己申告自己責任で自分の都合がよいノードで実行を進める。

この二つは何が違うの……？

その他の特徴：

• 通信機構: MBCF
• マイグレーション機能（移送機能）
• LINUX・UNIXプログラムとのソースコード互換開発環境
• 分散共有メモリ: UDSM/ADSM
• 最適化コンパイラ: RCOP
• OSカーネル: Micro Core
• その他

Lab/SSS-PC