処理状態を考慮した並列処理システムのための最適スケジューリング・アルゴリズム

概要

論文の詳細を見る
複数の処理装置からなる計算機システムにおいて, 個々の処理装置に対して処理状態を定義する. このモデルにおいて, ジョブの平均待ち時間の短縮だけでなく, 処理装置の状態切換え回数を抑える比較的簡単なスケジューリング・アルゴリズムを提案し, 理論とシミュレーションの両方でその有効性を示している. 待つことによって生じる損失と状態切換えによって生じる損失を考え, 両方の和の期待値を最小にする. しかし, 単なる時間平均でなく, 未来の損失ほど影響が小さくなるように指数関数の重みを付ける. タスクを割り当てるには各処理装置の状態を決定する必要があるので, 未来への影響も考えて先読みする. しかし, 確率の導入により, 動的計画法のように複数のパスをすべて調べるのでなく, 平均的な到着を仮定して, 状態を切り換えた場合に減少する損失と, 増加する損失を計算し, その差が一定値を越えると状態を切り換える. このような簡単化により, アルゴリズムの実行に必要な時間は, 最も単純な先着順の場合に比べても, 2〜3倍程度である. 同じカテゴリに属するタスクはまとめて処理するので, 平均待ち時間は少し大きくなるが, 状態切換え回数は小さくなる. このアルゴリズムを用いた時の状態切換え間隔の性質や, 到着率の小さいタスクについての性質を理論的に調べ, 望ましい性質を持つことを示し, さらに, シミュレーションによって処理装置の台数についての結果も示した.
一般社団法人情報処理学会の論文
1981-05-15

処理状態を考慮した並列処理システムのための最適スケジューリング・アルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク