JPH05165397A - スケジューリング装置 - Google Patents

Abstract

(57)【要約】 【目的】 先行制約関係を持った複数の処理タスクに資
源割当を決定する時の処理時間を短縮できるスケジュー
リング装置を得る。 【構成】 冗長制約除去部４３によって、複数の処理タ
スク相互の先行制約関係の中から、他の複数のタスク間
制約関係の組み合わせで代替表現可能なタスク間制約関
係を冗長なタスク間制約関係として検出し除去する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、スケジューリング装
置に関し、特に並列処理及び分散処理における処理要求
に対して、先行制約関係を持つ複数の処理タスクを有限
資源に割り当てるものに関する。

【０００２】

【従来の技術】この種のスケジューリング装置は、相互
に例えば順序関係などの先行制約関係を持つ複数の処理
単位タスクの処理において、タスクの先行制約関係を満
足し、かつ高い処理効率が得られるように、タスクが要
求するプロセッサ，メモリや周辺装置などの有限資源の
割当を決定する。全てのタスク間の先行制約関係と資源
要求がタスク実行以前に明確である時、この問題は静的
スケジューリング問題となる。

【０００３】この静的スケジューリング問題を解決する
従来装置の代表的なものとして、特開平３ー５６９８３
号公報に掲載されたものがある。このプラントシミュレ
ーション装置用のシミュレーションコード生成装置にお
けるコード生成処理を示すフローチャートを図４に示
す。図において、問題プログラムをＳＴ１でタスクに分
割し、ＳＴ２でタスク相互の先行制約関係、即ちタスク
因果関係を解析する。次に、ＳＴ３においてＳＴ２の解
析結果からスケジューリング方式が静的スケジューリン
グか動的スケジューリングかを判断する。この結果、静
的スケジューリングと判断した時はタスク負荷測定（Ｓ
Ｔ４），スケジュール決定（ＳＴ５），実行制御ルーチ
ン追加（ＳＴ６）を行う。一方、ＳＴ３で動的スケジュ
ーリングと判断した時はスケジューリングルーチン追加
（ＳＴ７）を行う。次にタスクに対するプロセッサ割当
を決定し、ＳＴ８にて並列シミュレーションコードを出
力する。

【０００４】

【発明が解決しようとする課題】スケジューリング問題
の本質は組合せ問題であるから、考慮すべき資源の種類
や先行制約関係の数が増えると問題の複雑性は級数的に
増大する。従って、上記のような従来のスケジューリン
グ装置では、スケジューリング処理に多大の時間が必要
になるという問題点があった。

【０００５】この発明は、かかる問題点を解決するため
になされたもので、スケジューリング処理において考慮
すべき処理タスク間の先行制約関係を整理して必要十分
な先行制約関係を生成することにより、スケジューリン
グ処理に要する時間を短縮できるスケジューリング装置
を得ることを目的としている。

【０００６】

【課題を解決するための手段】この発明の請求項１の発
明に係るスケジューリング装置は、複数の処理タスク相
互の先行制約関係の中から、他の複数のタスク間制約関
係の組み合わせで代替表現可能なタスク間制約関係を冗
長なタスク間制約関係として検出し除去する冗長制約除
去手段を備えたことを特徴とするものである。

【０００７】また、請求項２の発明は、処理タスクそれ
ぞれの資源アクセス手順に基づいて処理タスク全体の先
行制約関係を行列表現式Ｇとして第１依存グラフに表わ
す依存グラフ処理手段、及び他の複数の処理タスク相互
の先行制約関係の中から、他の複数のタスク間制約関係
の組み合わせで代替表現可能なタスク間制約関係を冗長
なタスク間制約関係として、第１依存グラフから検出し
除去して第２依存グラフに表わす冗長制約除去手段を備
えたことを特徴とするものである。

【０００８】また、請求項３の発明では、冗長制約除去
手段は、行列表現式で表わされているタスクの先行制約
関係Ｇよりｍが２以上の時のｍ−可到達行列Ｈを導く計
算手段と、行列表現式Ｇとｍ−可到達行列Ｈのどちらに
も表われるタスク間制約関係を冗長なタスク間制約関係
として検出し除去する処理手段を備えたことを特徴とす
るものである。

【０００９】

【作用】上記のように構成されたスケジューリング装置
では、冗長制約除去手段によって、複数の処理タスク相
互の先行制約関係の中から、他の複数のタスク間制約関
係の組み合わせで代替表現可能なタスク間制約関係を冗
長なタスク間制約関係として検出し除去するので、実際
のスケジューリング処理時に処理対象となるタスク間制
約関係を少なくすることかでき、高速化が図れる。

【００１０】また、冗長制約除去手段を実行する際、依
存グラフ処理手段によって、処理タスクそれぞれの資源
アクセス手順に基づいて処理タスク全体の先行制約関係
の行列表現式Ｇとして表わすので、行列演算で処理で
き、更に高速化される。

【００１１】

【実施例】

実施例１．この発明の一実施例によるスケジューリング
装置の構成を図１に示す。図において、４１は先行制約
関係を入力する先行制約入力部、４２は依存グラフを作
成する依存グラフ合成部、４３は冗長なタスク間制約関
係を検出して除去する冗長制約除去部、４４はスケジュ
ーリング前処理部、４５はスケジューリング部である。
先行制約入力部４１で個々の先行制約関係を与え、依存
グラフ合成部４２，冗長制約除去部４３では必要十分な
タスク依存グラフを合成し、スケジューリング部４５で
実際にスケジューリングしてタスクに対する資源割当を
決定する。

【００１２】次に依存グラフ合成部４２における処理に
ついて、更に詳しく説明する。処理タスクの先行制約関
係とは、処理タスクの実行手順と、メモリ，入出力装置
などの有限資源のアクセス順序によって規定される。従
って、タスク先行制約関係を解析して、それぞれの資源
に対する処理タスクのアクセス手順を調べ、資源アクセ
ス手順テーブルに記述する。このテーブルに基づいて、
第１依存グラフを生成する。この第１依存グラフはタス
ク数ｎを寸法とする（ｎ×ｎ）の行列表現式で表現す
る。行列要素（ｉ，ｊ）が１の時はタスクｉがｊに先行
する制約関係を持つことを意味し、行列要素（ｉ，ｊ）
が０の時は制約関係が無いことを意味する。この第１依
存グラフの行列に対して、資源アクセス手順テーブルを
参照して各資源に関するタスク先行制約関係を順に書き
込んでいく。ただし、既にタスク間先行制約関係が記入
されて値が１となっている行列要素は、１のままとす
る。全ての資源アクセス手順に基づくタスク先行制約関
係を行列に移した時、図２に示すような第１依存グラフ
が生成される。図２において、第１依存グラフのノード
が処理タスク、ノードを繋ぐパスがタスク間先行制約関
係となる。即ち、Ｎ１〜Ｎ５は処理タスクを示す第１依
存グラフのノード、Ｐ１〜Ｐ７はタスク間制約関係を示
す第１依存グラフのパスである。図２と式１は同じ意味
を表わしている。

【００１３】

【数１】

【００１４】次に冗長制約除去部４３における処理につ
いて、更に詳しく説明する。ここで冗長なタスク間制約
関係とは、その制約関係が無くともタスク全体の順序関
係が同一であり、スケジューリング結果が等価であるも
のをいう。第１依存グラフにおいて、あるノードから別
のノードにｍ本のパスを通って到達することをｍステッ
プで到達するという。例えば、Ｎ１からＮ４に到達する
には、Ｐ２の１ステップで到達するか、Ｐ１とＰ４の２
ステップで到達できる。ｍ−ステップで到達するノード
集合をｍ−到達集合といい、ｍステップ以内で到達でき
るノード集合をｍ−可到達集合という。ここで、第１依
存グラフの各ノードのｍ−到達集合を表わした行列をｍ
−到達行列と定義する。

【００１５】ｍ−到達行列の各要素はタスクｉ，ｊ間の
ｍ−到達経路の数を表わしている。第１依存グラフの接
続関係を変更してもｍ−可到達集合が等価である時、ｍ
−可到達性は保存されるという。第１依存グラフにおけ
る冗長パスとは、そのパスがなくてもタスク間前後関係
が変わらないパスのことであり、そのパスが接続する２
つの処理タスクを別の経路を通ってで到達できることで
ある。即ち、図２におけるＰ２，Ｐ５，Ｐ７は冗長パス
である。冗長制約除去部４３ではこのような冗長パスを
検出し除去して、依存グラフの可到達性を保存するよう
なパス数最少のグラフを導くことである。

【００１６】まず、第１依存グラフの行列表現式Ｇに対
して、現在のタスク状態を表わす長さがタスク数ｎのタ
スク状態ベクトルＸを定義する。Ｘの要素ｘ（ｋ）は、
タスクｋに資源が割り当てられている時に１であり、資
源待ち状態の時に０である。さて、タスク初期状態Ｘ0
からのステップ数ｍ＝１の到達集合は、資源割当ノード
からの直接パスの行き先の全てのノードであるから、第
１依存グラフの行列表現式Ｇとｍ−到達行列は同一であ
り、式２で得られる。 Ｘ1 ＝ＧＸ0 ・・・（２） 同様に繰り返して，Ｘ0 からのｍ−到達集合Ｘm は式３
で得られる。 Ｘm ＝ＧＸm-1 ＝Ｇ2 Ｘm-2 ＝・・・＝Ｇm Ｘ0 ＝Ｇm Ｘ0 ・・・（３） ただし、Ｇ1 ＝Ｇである。

【００１７】従って、ｍ−可到達集合Ｙm は式４で表さ
れる。 Ｙm ＝ Ｘ1 ＋Ｘ2 ＋・・・＋Ｘm ＝ （Ｇ1 ＋Ｇ2 ＋・・・＋Ｇm ）Ｘm ＝ Ｆm Ｘm ・・・（４） ここで、（ｍ＞１）ー可到達行列を式５で定義する。 Ｈ（ｍ＞１） ＝ Ｇ2 ＋Ｇ3 ＋・・・＋Ｇm ・・・（５）

【００１８】ｍ−可到達行列Ｈ（ｍ＞１）は、その要素
ｈ（ｍ＞１）（ｉ，ｊ）が０でなければ、ノードｉ，ｊ
間が複数ステップで到達できることを意味する。グラフ
の冗長パスとは、複数ステップで到達できるノード間の
直接パスであるから、式６の条件に当てはまる依存グラ
フＧのパスである。 ｈ（ｍ＞１）（ｉ，ｊ）＞０かつｇ（ｉ，ｊ）＝１ならば ｇ（ｉ，ｊ）＝０ ・・・（６） 式６により、もとの第１依存グラフＧから冗長制約を除
去した可到達性が保存されたパス数最小の第２依存グラ
フＧ’が得られたことになる。

【００１９】ただし、第１依存グラフにおいて、いくつ
かのパスを通って自分に戻ってくるループ経路が存在す
る時、上の手法ではループを構成するパスは冗長パスと
判断されるが、除去するとループが壊れるため可到達性
が破壊される。従って、この装置は第１依存グラフにル
ープが存在すると適用できない。

【００２０】以上が実施例１における冗長制約関係の検
出，除去の原理である。この計算はＧm を逐次的に計算
することにより、計算に必要な記憶領域を小さくでき
る。このアルゴリズムを以下に示す。 １．Ｇn ＝Ｇn-1 ×Ｇ （Ｇ：第１依存グラフ） ２．Ｇn ＝０ ならば終了 ３．Ｈ（ｍ＞１）＝Ｇ2 ＋Ｇ3 ＋…＋Ｇn-1 ４．もし（ｈ（ｍ＞１）（ｉ，ｊ）＞０かつｇ（ｉ，
ｊ）＞０）ならば、ｇ（ｉ，ｊ）＝０ ５．全てのｉ，ｊ について上記４を行って、必要十分
な第２依存グラフＧ’を得る。

【００２１】図２に示す第１依存グラフから上記のアル
ゴリズムに従い冗長制約を検出し除去する。まず、Ｇ2
〜Ｇ4 のそれぞれを計算すると、式７のようになる。

【００２２】

【数２】

【００２３】これから、Ｈ（ｍ＞１）を求めると、式８
となり、上記アルゴリズム４から冗長なパスは、Ｐ２
（１、４），Ｐ５（２，４），Ｐ７（２，５）となる。

【００２４】

【数３】

【００２５】必要十分な第２依存グラフＧ’は式９で表
される。

【００２６】

【数４】

【００２７】これを樹木型に表現すると、図３に示すよ
うになる。この実施例は第１依存グラフとしてループの
無い依存グラフを前提としているので、最大の可到達経
路長はたかだか全タスク数ｎである。従って、必ずｋ＋
１＝ｎまでにＧk ＝０となって終了するので、処理の停
止性が明確である。

【００２８】上記の動作から明らかなように、実施例１
によるスケジューリング装置では、分散処理あるいは並
列処理における資源スケジューリング処理にかかる時間
が短縮される。また、後戻り探索法による冗長パス検出
装置に比べ、時間とメモリが小さくできる。

【００２９】なお、上記計算の要素の値が０叉は１以上
としか判断していない点に注目し、行列要素をビット列
として表わし、積を論理積、和を論理和として計算すれ
ば、さらに高速計算を可能にでき、処理時間の短縮でき
るスケジューリング装置が得られる。

【００３０】叉、上記実施例１では冗長制約関係を削除
する処理がスケジューリング前処理部４４として独立し
た構成となっているが、前処理部４４の冗長制約除去部
４３だけをとりだして、依存関係解析装置の一部あるい
はスケジューリング装置の一部として実現しても上記実
施例１と同様の効果を奏する。

【００３１】

【発明の効果】以上のように、請求項１の発明によれ
ば、先行制約関係を持つ複数の処理タスクに有限資源を
割り当てるスケジューリング装置において、複数の処理
タスク相互の先行制約関係の中から、他の複数のタスク
間制約関係の組み合わせで代替表現可能なタスク間制約
関係を冗長なタスク間制約関係として検出し除去する冗
長制約除去手段を備えたことにより、処理時間が短縮で
きるスケジューリング装置が得られる効果がある。

【００３２】また、請求項２の発明によれば、先行制約
関係を持つ複数の処理タスクに有限資源を割り当てるス
ケジューリング装置において、処理タスクそれぞれの資
源アクセス手順に基づいてタスク全体の先行制約関係を
行列表現式Ｇとして第１依存グラフに表わす依存グラフ
処理手段、及び他の複数の処理タスク相互の先行制約関
係の中から、他の複数のタスク間制約関係の組み合わせ
で代替表現可能なタスク間制約関係を冗長なタスク間制
約関係として、第１依存グラフから検出し除去して第２
依存グラフに表わす冗長制約除去手段を備えたことによ
り、さらに処理時間が短縮できるスケジューリング装置
が得られる効果がある。

【００３３】また、請求項３の発明によれば、請求項２
における冗長制約除去手段を、行列表現式で表わされて
いるタスクの先行制約関係Ｇよりｍが２以上の時のｍ−
可到達行列Ｈを導く計算手段と、行列表現式Ｇとｍ−可
到達行列Ｈのどちらにも表われるタスク間制約関係を冗
長なタスク間制約関係として検出し除去する処理手段を
備えたことにより、さらに処理時間が短縮できるスケジ
ューリング装置が得られる効果がある。

【図面の簡単な説明】

【図１】この発明の実施例１によるスケジューリング装
置を示すブロック図である。

【図２】この発明の実施例１に係る第１依存グラフを示
す説明図である。

【図３】この発明の実施例１に係る第２依存グラフを示
す説明図である。

【図４】従来のスケジューリング装置による処理手順を
示すフローチャートである。

【符号の説明】

４２ 依存グラフ合成部 ４３ 冗長制約除去部 ４５ スケジューリング部

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成４年２月２６日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】請求項２

【補正方法】変更

【補正内容】

【手続補正２】

【補正対象書類名】明細書

【補正対象項目名】０００１

【補正方法】変更

【補正内容】

【０００１】

【産業上の利用分野】この発明は、スケジューリング装
置に関し、特に並列処理及び分散処理における処理要求
に対して、先行制約関係を持つ複数の処理タスクに有限
資源を割り当てるものに関する。

【手続補正３】

【補正対象書類名】明細書

【補正対象項目名】０００７

【補正方法】変更

【補正内容】

【０００７】また、請求項２の発明は、処理タスクそれ
ぞれの資源アクセス手順に基づいて処理タスク全体の先
行制約関係を行列表現式Ｇとして第１依存グラフに表わ
す依存グラフ合成手段、及び他の複数の処理タスク相互
の先行制約関係の中から、他の複数のタスク間制約関係
の組み合わせで代替表現可能なタスク間制約関係を冗長
なタスク間制約関係として、第１依存グラフから検出し
除去して第２依存グラフに表わす冗長制約除去手段を備
えたことを特徴とするものである。

【手続補正４】

【補正対象書類名】明細書

【補正対象項目名】００１０

【補正方法】変更

【補正内容】

【００１０】また、冗長制約除去手段を実行する際、依
存グラフ処理手段によって、処理タスクそれぞれの資源
アクセス手順に基づいて処理タスク全体の先行制約関係
の行列表現式Ｇとして表わすので、行列演算で処理で
き、高速に冗長制約除去を行える。

【手続補正５】

【補正対象書類名】明細書

【補正対象項目名】００１１

【補正方法】変更

【補正内容】

【００１１】

【実施例】 実施例１．この発明の一実施例によるスケジューリング
装置の構成を図１に示す。図において、４１は複数の処
理タスクの先行制約関係を入力する先行制約入力部、４
２は依存グラフを作成する依存グラフ合成手段、例えば
ここでは依存グラフ合成部で、先行制約入力部４１で入
力された処理タスクそれぞれの有限資源のアクセス手順
に基づいて、処理タスク全体の先行制約関係を行列表現
式Ｇとして第１依存グラフに表わす。４３は冗長なタス
ク間制約関係を検出して除去する冗長制約除去手段で、
例えばここでは冗長制約除去部であり、他の複数の処理
タスク相互の先行制約関係の中から、他の複数のタスク
間制約関係の組み合わせで代替表現可能なタスク間制約
関係を冗長なタスク間制約関係として、第１依存グラフ
から検出し除去して第２依存グラフに表わす。４４は実
際のスケジューリングの前に必要な処理を行うスケジュ
ーリング前処理部、４５は実際のスケジューリングを行
うスケジューリング部である。このスケジューリング前
処理部４４は先行制約入力部４１、依存グラフ合成部４
２，冗長制約除去部４３で構成されている。概略的な処
理は、先行制約入力部４１で個々の先行制約関係を与
え、依存グラフ合成部４２，冗長制約除去部４３では必
要十分なタスク依存グラフを合成し、スケジューリング
部４５で実際にスケジューリングして処理タスクに対す
る資源割当を決定する。

【手続補正６】

【補正対象書類名】明細書

【補正対象項目名】００１２

【補正方法】変更

【補正内容】

【００１２】次に依存グラフ合成部４２における処理に
ついて、更に詳しく説明する。処理タスク相互の先行制
約関係とは、処理タスクの実行手順と、メモリ，入出力
装置などの有限資源のアクセス順序によって規定され
る。従って、処理タスク相互の先行制約関係を解析し
て、それぞれの有限資源に対する処理タスクのアクセス
手順を調べ、資源アクセス手順テーブルに記述する。こ
のテーブルに基づいて、第１依存グラフを生成する。こ
の第１依存グラフはタスク数ｎを寸法とする（ｎ×ｎ）
の行列表現式Ｇで表現される。行列要素（ｉ，ｊ）が１
の時はタスクｉがｊに先行する制約関係を持つことを意
味し、行列要素（ｉ，ｊ）が０の時は制約関係が無いこ
とを意味する。この第１依存グラフの行列Ｇに対して、
資源アクセス手順テーブルを参照して各資源に関するタ
スク先行制約関係を順に書き込んでいく。ただし、既に
タスク間先行制約関係が記入されて値が１となっている
行列要素は、１のままとする。全ての資源アクセス手順
に基づくタスク先行制約関係を行列に移した時、図２に
示すような第１依存グラフが生成される。図２におい
て、第１依存グラフのノードが処理タスク、ノードを繋
ぐパスがタスク間先行制約関係となる。即ち、Ｎ１〜Ｎ
５は処理タスクを示す第１依存グラフのノード、Ｐ１〜
Ｐ７はタスク間制約関係を示す第１依存グラフのパスで
ある。図２と式１は同じ意味を表わしている。

【手続補正７】

【補正対象書類名】明細書

【補正対象項目名】００１４

【補正方法】変更

【補正内容】

【００１４】次に冗長制約除去部４３における処理につ
いて、更に詳しく説明する。ここで冗長なタスク間制約
関係とは、複数の処理タスク相互の先行制約関係の中か
ら、他の複数のタスク間制約関係の組み合わせで代替表
現可能なタスク間制約関係をいうもので、その制約関係
が無くともタスク全体の順序関係が同一であり、スケジ
ューリング結果が等価であるものをいう。第１依存グラ
フにおいて、あるノードから別のノードにｍ本のパスを
通って到達することをｍステップで到達するという。例
えば、Ｎ１からＮ４に到達するには、Ｐ２の１ステップ
で到達するか、Ｐ１とＰ４の２ステップで到達できる。
ｍ−ステップで到達するノード集合をｍ−到達集合とい
い、ｍステップ以内で到達できるノード集合をｍ−可到
達集合という。ここで、第１依存グラフの各ノードのｍ
−到達集合を表わした行列をｍ−到達行列と定義する。

【手続補正８】

【補正対象書類名】明細書

【補正対象項目名】００２８

【補正方法】変更

【補正内容】

【００２８】上記の動作から明らかなように、実施例１
によるスケジューリング装置では、冗長制約除去部４３
を備え、複数の処理タスク相互の先行制約関係の中か
ら、他の複数のタスク間制約関係の組み合わせで代替表
現可能なタスク間制約関係を冗長なタスク間制約関係と
して検出し除去するので、分散処理あるいは並列処理に
おける資源スケジューリング処理にかかる時間が短縮さ
れる。また、依存グラフ合成部４２で処理タスクそれぞ
れの資源アクセス手順に基づいてタスク全体の先行制約
関係を行列表現式Ｇとして第１依存グラフに表わし、冗
長制約除去部４３で他の複数の処理タスク相互の先行制
約関係の中から、他の複数のタスク間制約関係の組み合
わせで代替表現可能なタスク間制約関係を冗長なタスク
間制約関係として、第１依存グラフから検出し除去して
第２依存グラフに表わすので、後戻り探索法による冗長
パス検出装置に比べ、時間とメモリが小さくできる。ま
た、特に実施例１では、冗長制約除去部４３は、行列表
現式で表わされているタスクの先行制約関係Ｇよりｍが
２以上の時のｍ−可到達行列Ｈを導き、行列表現式Ｇと
ｍ−可到達行列Ｈのどちらにも表われるタスク間制約関
係を冗長なタスク間制約関係として検出し除去すること
で実現している。

【手続補正９】

【補正対象書類名】明細書

【補正対象項目名】００３２

【補正方法】変更

【補正内容】

【００３２】また、請求項２の発明によれば、先行制約
関係を持つ複数の処理タスクに有限資源を割り当てるス
ケジューリング装置において、処理タスクそれぞれの資
源アクセス手順に基づいてタスク全体の先行制約関係を
行列表現式Ｇとして第１依存グラフに表わす依存グラフ
合成手段、及び他の複数の処理タスク相互の先行制約関
係の中から、他の複数のタスク間制約関係の組み合わせ
で代替表現可能なタスク間制約関係を冗長なタスク間制
約関係として、第１依存グラフから検出し除去して第２
依存グラフに表わす冗長制約除去手段を備えたことによ
り、処理時間が短縮できるスケジューリング装置が得ら
れる効果がある。

【手続補正１０】

【補正対象書類名】明細書

【補正対象項目名】００３３

【補正方法】変更

【補正内容】

【００３３】また、請求項３の発明によれば、請求項２
における冗長制約除去手段を、行列表現式で表わされて
いるタスクの先行制約関係Ｇよりｍが２以上の時のｍ−
可到達行列Ｈを導く計算手段と、行列表現式Ｇとｍ−可
到達行列Ｈのどちらにも表われるタスク間制約関係を冗
長なタスク間制約関係として検出し除去する処理手段を
備えたことにより、処理時間が短縮できるスケジューリ
ング装置が得られる効果がある。

Claims (3)

【特許請求の範囲】
1. 【請求項１】 先行制約関係を持つ複数の処理タスクに
   有限資源を割り当てるスケジューリング装置において、
   上記複数の処理タスク相互の先行制約関係の中から、他
   の複数のタスク間制約関係の組み合わせで代替表現可能
   なタスク間制約関係を冗長なタスク間制約関係として検
   出し除去する冗長制約除去手段を備えたことを特徴とす
   るスケジューリング装置。
2. 【請求項２】 先行制約関係を持つ複数の処理タスクに
   有限資源を割り当てるスケジューリング装置において、
   上記処理タスクそれぞれの資源アクセス手順に基づいて
   タスク全体の先行制約関係を行列表現式Ｇとして第１依
   存グラフに表わす依存グラフ処理手段、及び他の複数の
   処理タスク相互の先行制約関係の中から、他の複数のタ
   スク間制約関係の組み合わせで代替表現可能なタスク間
   制約関係を冗長なタスク間制約関係として、第１依存グ
   ラフから検出し除去して第２依存グラフに表わす冗長制
   約除去手段を備えたことを特徴とするスケジューリング
   装置。
3. 【請求項３】 冗長制約除去手段は、行列表現式で表わ
   されているタスクの先行制約関係Ｇよりｍが２以上の時
   のｍ−可到達行列Ｈを導く計算手段と、上記行列表現式
   Ｇとｍ−可到達行列Ｈのどちらにも表われるタスク間制
   約関係を冗長なタスク間制約関係として検出し除去する
   処理手段を備えたことを特徴とする請求項第２項記載の
   スケジューリング装置。