(57)【要約】【課題】時分割スケジューリングを前提としたアプリケーションに対して、実行アプリケーション数が頻繁に増減する環境においてもアプリケーションの応答性能を容易に、且つ自動的に最大限に引き出す。【解決手段】アプリケーション依存解析部２にて、時分割スケジューリング上で動作するプロセスにおける起床から休止までの処理をノードとして扱い、ノード間の依存関係の解析を行い、ノードの実行順序と依存関係とを示す依存解析情報を形成し、制御変更判定部３にて、依存解析情報に基づいて、アプリケーションを構成するプロセスを時分割スケジューリングからグループスケジューリングへ移行させ、グループスケジューリング実行部４にて、移行したプロセスについて、依存解析情報に基づいて、プロセス単位でグループスケジューリングを実施する。【選択図】図１
2009048358.tif 000002
【特許請求の範囲】
【請求項１】
時分割でスケジューリングを行う時分割スケジューリング上で動作するプロセスにおける起床から休止までの処理をノードとして扱い、前記ノード間の依存関係の解析を行い、前記ノードの実行順序と前記依存関係とを示す依存解析情報を形成するアプリケーション依存解析部と、
前記依存解析情報に基づいて、アプリケーションを構成するプロセスを、前記時分割スケジューリングからグループでスケジューリングを行うグループスケジューリングへ移行させる制御変更判定部と、
前記移行したプロセスについて、前記依存解析情報に基づいて、プロセス単位で前記グループスケジューリングを実施するグループスケジューリング実行部とを有する情報処理装置。
【請求項２】
請求項１に記載の情報処理装置において、
前記グループスケジューリング実行部は、前記依存解析情報に基づいて実行頻度の高い一連のプロセス実行列を１つのグループとして扱い、該グループ単位で優先度スケジューリングをすることを特徴とする情報処理装置。
【請求項３】
請求項１に記載の情報処理装置において、
前記グループスケジューリング実行部は、前記時分割スケジューリングのプロセス実行管理情報への参照を持つ仮想実行キューを用いて前記グループスケジューリングを実施することを特徴とする情報処理装置。
【請求項４】
請求項１記載の情報処理装置において、
前記制御変更判定部は、前記時分割スケジューリング上での現在のプロセス動作と過去の依存解析情報とに基づいて前記時分割スケジューリングから前記グループスケジューリングへ移行させるプロセスを決定することを特徴とする情報処理装置。
【請求項５】
請求項１記載の情報処理装置において、
前記アプリケーション依存解析部は、前記ノードの実行時間と実行開始アドレスとを含んだ依存解析情報を形成することを特徴とする情報処理装置。
【請求項６】
請求項１記載の情報処理装置において、
前記アプリケーション依存解析部は、前記プロセスのコンテキストスイッチ状況を監視して、アプリケーションの一連の動作を解析することを特徴とする情報処理装置。
【請求項７】
請求項１記載の情報処理装置において、
前記アプリケーション依存解析部は、前記依存解析情報を利用者によって予め登録された依存解析情報に置き換えることを特徴とする情報処理装置。
【請求項８】
請求項１に記載の情報処理装置において、
前記アプリケーション依存解析部は、前記プロセスのＡＰＩ呼び出し状況を監視して、アプリケーションの一連の動作を解析することを特徴とする情報処理装置。
【請求項９】
複数のプロセスの実行スケジューリングを行うスケジューリング方法であって、
時分割でスケジューリングを行う時分割スケジューリング上で動作するプロセスにおける起床から休止までの処理をノードとして扱う処理と、
前記ノード間の依存関係の解析を行う処理と、
前記ノードの実行順序と前記依存関係とを示す依存解析情報を形成する処理と、
前記依存解析情報に基づいて、アプリケーションを構成するプロセスを、前記時分割スケジューリングからグループでスケジューリングを行うグループスケジューリングへ移行させる処理と、
前記移行したプロセスについて、前記依存解析情報に基づいて、プロセス単位で前記グループスケジューリングを実施する処理とを有するスケジューリング方法。
【請求項１０】
請求項９に記載のスケジューリング方法において、
前記依存解析情報に基づいて実行頻度の高い一連のプロセス実行列を１つのグループとして扱う処理と、
該グループ単位で優先度スケジューリングをする処理とを有することを特徴とするスケジューリング方法。
【請求項１１】
請求項９に記載のスケジューリング方法において、
前記時分割スケジューリングのプロセス実行管理情報への参照を持つ仮想実行キューを用いて前記グループスケジューリングを実施する処理を有することを特徴とするスケジューリング方法。
【請求項１２】
請求項９に記載のスケジューリング方法において、
前記時分割スケジューリング上での現在のプロセス動作と過去の依存解析情報とに基づいて前記時分割スケジューリングから前記グループスケジューリングへ移行させるプロセスを決定する処理を有することを特徴とするスケジューリング方法。
【請求項１３】
請求項９に記載のスケジューリング方法において、
前記ノードの実行時間と実行開始アドレスとを含んだ依存解析情報を形成する処理を有することを特徴とするスケジューリング方法。
【請求項１４】
請求項９に記載のスケジューリング方法において、
前記プロセスのコンテキストスイッチ状況を監視して、アプリケーションの一連の動作を解析する処理を有することを特徴とするスケジューリング方法。
【請求項１５】
請求項９に記載のスケジューリング方法において、
前記依存解析情報を利用者によって予め登録された依存解析情報に置き換える処理を有することを特徴とするスケジューリング方法。
【請求項１６】
請求項９に記載のスケジューリング方法において、
前記プロセスのＡＰＩ呼び出し状況を監視して、アプリケーションの一連の動作を解析する処理を有することを特徴とするスケジューリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アプリケーションを構成するプロセスの実行をスケジューリングする情報処理装置及びスケジューリング方法に関する。
【背景技術】
【０００２】
一般的なＵｎｉｘなどの時分割スケジューリングを用いた汎用オペレーティングシステムでは、アプリケーションを構成するプロセス単位に優先度を付け、時分割にプロセスの切り替えを実行している。
【０００３】
一方、アプリケーションの性能達成に特化したリアルタイムオペレーティングシステムでは、実行するプロセスの順序やプロセス間の優先度を開発者が厳密に指定することで高い応答性能を実現している。
【０００４】
アプリケーションの応答性能の向上を検討した場合、前者ではアプリケーションを構成するプロセス間の関係が考慮されていないために、不必要なタイミングにプロセス切り替えを発生させ、アプリケーションの応答性を悪化させてしまうという問題点がある。後者では、アプリケーションをシステムに導入するたびに、開発者がプロセスの実行順序指定や全体の優先度を再設定しなければならないという問題点がある。このように現在利用できる環境では、生産性と性能達成とがトレードオフの関係にあり、状況に応じてどちらかのシステムを選択しなければならない。生産性と応答性能とを両立させるためには、アプリケーションを構成するプロセス間の関係を自動的に解析する方法が必要となる。そのような方法には、次のような技術が考えられている。
【０００５】
アプリケーションの動作性能を測定・分析し、その結果に基づき共同動作を最適化するためのシステム性能測定分析を計算機で実現する技術が考えられている（例えば、特許文献１参照。）。本技術においては、アプリケーションを構成する処理単位を抽出するためにソースコード解析を行う。
【０００６】
また、プロセスとそのプロセスがアクセスする情報（データ）との関係を実行時に解析することで、ユーザに対して、ある情報に関連深い情報を適切に提供する技術が考えられている（例えば、特許文献２参照。）。
【０００７】
また、シリアルプログラムから等価交換したマルチタスクプログラムのタスク間依存関係を解析可能な技術が考えられている（例えば、特許文献３参照。）。
【０００８】
また、実行した動作履歴を活用して、処理を効率的に行う技術が考えられている（例えば、特許文献４参照。）。
【０００９】
また、並列命令スケジューリングに必要な命令間依存抽出を、コンパイラによる高級言語からの変換時に行う並列スケジューリングが考えられている（例えば、特許文献５参照。）。
【００１０】
また、実行頻度及び実行順序を考慮したグループスケジューリングを行う技術が考えられている（例えば、特許文献６参照。）。
【００１１】
また、ユーザが持つデータ依存解析及びデータアクセスパターン頻度によってスケジューリングを行う技術が考えられている（例えば、特許文献７参照。）。
【００１２】
また、アプリケーションを構成するプロセスプロセス間の依存解析情報を利用してプロセス群単位でのスケジューリングを実施する技術が考えられている（例えば、特許文献８参照。）。
【特許文献１】特開２００４−２６４９１４号公報
【特許文献２】国際公開第２００４／０３１９５６号パンフレット
【特許文献３】特許第２６２６１３１号公報
【特許文献４】特開平１０−２５４７１９号公報
【特許文献５】特開２０００−２２２２０９号公報
【特許文献６】特開２００３−３３０７３０号公報
【特許文献７】特開２００５−１２２７２６号公報
【特許文献８】特開２００７−０４８０５２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、上述した技術においては、以下に記述する問題点がある。
【００１４】
第１の問題点は、時分割スケジューリング方式OSを用いた計算機上では複数のアプリケーションを動作させた場合に各アプリケーションの応答性能が安定しない。その理由は、アプリケーションを構成しているプロセス単位で優先度付けをする時分割方式ではプロセス数が増えるほどアプリケーションにとって最適な順番でプロセスを選択及び実行させることが困難となるためである。
【００１５】
第２の問題点は、多数の演算装置と各演算装置からアクセス速度が異なる記憶媒体とを備えた計算機上において、時分割スケジューリング方式では応答性能の安定化も高スループット性能も達成できない。その理由は、時分割スケジューリング方式はプロセス間の関係を認識していないため、処理を実行する適切な空間的な配置を決定できないからである。
【００１６】
第３の問題点は、第1及び２の問題点を解決するリアルタイムスケジューリング方式は、ソフトウェア生産性及び再利用性を大きく損なうことである。その理由は、プロセス単位で優先度付けした時分割方式は、どのような状況でもデッドロックしない動的な優先度付けと各プロセスを強制的に時分割実行する仕組みとによって、各プロセス間の厳密な実行順序や依存関係を明示しなくても全体として正常動作する環境を提供する利点を持っているからである。リアルタイムスケジューリング方式では、これらの関係を事前に厳密に指定する必要があるうえ、一般に実際に動作する環境をある程度モデル化する必要がある。これが生産性と再利用性の低下を引き起こす。
【００１７】
第４の問題点は、第３の問題点を解決するアプリケーションの依存関係をソース解析や特殊な外部ハードウェアを一時的に利用して自動的に明らかにする方法が提案されているが、実際にこの情報を利用してアプリケーションの応答性能を高めるシステムは提案されていないことである。また、この解析方法では実行するアプリケーションセット環境が頻繁に増減する利用環境には対応でき無い。
【００１８】
また、特許文献１に記載された技術においては、一般的にソースコードの入手は困難である事が多いという問題点がある。また、実際にこの情報を元に性能の最適化を行う部分は自動化されていない。
【００１９】
また、特許文献２に記載された技術においては、本技術を用いることにより、プロセスとデータの関係を自動的に抽出できるが、プロセス間依存情報は得られないという問題点がある。また、これも特許文献１と同様に情報提示から先の性能向上部分は自動化されていない。
【００２０】
また、特許文献４に記載された技術においては、この動作とはユーザ操作や機器間指示や要求が単位となっている。
【００２１】
また、特許文献５に記載された技術においては、高級言語が必要となってしまうという問題点がある。
【００２２】
また、特許文献６に記載された技術においては、グループ化にコンパイラが必要となってしまうという問題点がある。
【００２３】
また、特許文献７に記載された技術においては、時分割スケジューリングにおける実行依存関係を見出すことはできないという問題点がある。
【００２４】
また、特許文献８に記載された技術においては、コンパイラ及びコンパイラ前の高級言語で記述されたプログラムが必要になってしまうという問題点がある。
【００２５】
本発明は、上述したような従来の技術が有する問題点に鑑みてなされたものであって、時分割スケジューリングを前提としたアプリケーションに対して、実行アプリケーション数が頻繁に増減する環境においてもアプリケーションの応答性能を容易に、且つ自動的に最大限に引き出すことができる情報処理装置及びスケジューリング方法を提供することを目的とする。
【課題を解決するための手段】
【００２６】
上記目的を達成するために本発明は、
時分割でスケジューリングを行う時分割スケジューリング上で動作するプロセスにおける起床から休止までの処理をノードとして扱い、前記ノード間の依存関係の解析を行い、前記ノードの実行順序と前記依存関係とを示す依存解析情報を形成するアプリケーション依存解析部と、
前記依存解析情報に基づいて、アプリケーションを構成するプロセスを、前記時分割スケジューリングからグループでスケジューリングを行うグループスケジューリングへ移行させる制御変更判定部と、
前記移行したプロセスについて、前記依存解析情報に基づいて、プロセス単位で前記グループスケジューリングを実施するグループスケジューリング実行部とを有する。
【００２７】
また、複数のプロセスの実行スケジューリングを行うスケジューリング方法であって、
時分割でスケジューリングを行う時分割スケジューリング上で動作するプロセスにおける起床から休止までの処理をノードとして扱う処理と、
前記ノード間の依存関係の解析を行う処理と、
前記ノードの実行順序と前記依存関係とを示す依存解析情報を形成する処理と、
前記依存解析情報に基づいて、アプリケーションを構成するプロセスを、前記時分割スケジューリングからグループでスケジューリングを行うグループスケジューリングへ移行させる処理と、
前記移行したプロセスについて、前記依存解析情報に基づいて、プロセス単位で前記グループスケジューリングを実施する処理とを有する。
【発明の効果】
【００２８】
以上説明したように本発明においては、アプリケーション依存解析部にて、時分割スケジューリング上で動作するプロセスにおける起床から休止までの処理をノードとして扱い、ノード間の依存関係の解析を行い、ノードの実行順序と依存関係とを示す依存解析情報を形成し、制御変更判定部にて、依存解析情報に基づいて、アプリケーションを構成するプロセスを時分割スケジューリングからグループスケジューリングへ移行させ、グループスケジューリング実行部にて、移行したプロセスについて、依存解析情報に基づいて、プロセス単位でグループスケジューリングを実施する構成としたため、時分割スケジューリングを前提としたアプリケーションに対して、実行アプリケーション数が頻繁に増減する環境においてもアプリケーションの応答性能を容易に、且つ自動的に最大限に引き出すことができる。
【発明を実施するための最良の形態】
【００２９】
以下に、本発明の実施の形態について図面を参照して説明する。
【００３０】
図１は、本発明の情報処理装置の実施の一形態を示す図である。また、図２は、図１に示した形態において、時分割スケジューリングとグループスケジューリングとのプロセススケジューリング状態を示す図である。
【００３１】
本形態は図１に示すように、プログラムを実行する時分割スケジューリング実行部１と、アプリケーション依存解析部２と、制御変更判定部３と、グループスケジューリング実行部４とから構成されている。
【００３２】
時分割スケジューリング実行部１は、プロセスを実行単位とし、一定時間ごとに実行するプロセスを切り替えることにより、複数のプロセスを公平に実行する時分割スケジューリングシステムである。
【００３３】
アプリケーション依存解析部２は、時分割スケジューリング実行部１を監視することにより、これらプロセス間から実行依存関係パターンを検出し、収集する。この実行依存関係パターンの情報をここでは依存解析情報と呼ぶ。
【００３４】
制御変更判定部３は、収集した依存グループが時分割スケジューリング実行部１で再度現れるかどうか判断し、実行が予測可能な場合に、その依存グループに関わるプロセスの実行をグループスケジューリング実行部４で行えるよう取り計らう。
【００３５】
グループスケジューリング実行部４では、依存解析情報を利用し、依存順にプロセスをプロセス単位で実行する。同じ演算装置で実行している依存グループの実行権選択は、そのグループの実行時間などの情報を利用してグループ間の優先度付けをする。ここでのグループとは、依存解析情報に基づいて、実行頻度の高い一連のプロセスを１つのグループと扱われるものである。
【００３６】
これらの構成要素は、図２に示すように時分割スケジューリングからグループスケジューリングへの移行を実現する。その動作について詳細に説明する。
【００３７】
まず、図１の時分割スケジューリング実行部１及びアプリケーション依存解析部２の動作の概要を説明する。
【００３８】
時分割スケジューリング実行部１は、上述したようにプロセスを実行単位とし、一定時間ごとに実行するプロセスを切り替えることにより、複数のプロセスを公平に実行する時分割スケジューリングシステムである。このシステムでは、現在実行可能なプロセスが、RUNQと呼ばれるキューの１つの要素として静的もしくは動的に決められた優先度ごとに管理され、そのRUNQ内の優先度が高い順にプロセスが実行される。実行プロセスが切り替わる条件は、実装によって差異はあるものの、基本的には、現在の実行中のプロセスが終了した場合、休止した場合、決められた一定時間が経過した場合、実行プロセスより高い優先度のプロセスが実行可能となった場合である。プロセスは、休止から起床させられた場合や新たに起動させられた場合にRUNQに投入されるが、その際の優先度決定は実装方針によって様々である。例えばOSの１つであるLinuxでは、休止時間が長いほど優先度は高くなる。
【００３９】
アプリケーション依存解析部２では、このRUNQを監視することでプロセス間の実行依存パターン（依存グループ）を検出する。まず、時分割スケジューリング実行部１上の各プロセスの起床から休止までの処理を１つのノードとして認識し、実行を表す単位とする。次に、あるノードが実行されている最中のRUNQを監視し、実行中に起床させられたノードを検出する。検出されたノードは実行中のノードへ依存があると判断され、そのノード間に依存を表す枝を張っていく。これを依存が検出されなくなるまで続けると１つの依存木が形成される。これを依存グループの依存木と呼ぶ。
【００４０】
図３は、時分割スケジューリングと依存グループとの関係を示す図である。
【００４１】
図３に示すように、時分割にスケジューリングされたプロセスＡ〜Ｄにて起床したノード「１」〜「５」の依存パターンによって、依存木が形成される。アプリケーション依存解析部２では、形成された依存木の作成及びそれを構成する各ノードの実行時間の記録を行うことが主要な機能である。図３に示した関係では、プロセスＡのノード「１」によって、プロセスＢのノード「２」及びプロセスＣのノード「３」が起床する。つまり、ノード「１」とノード「２」との間に、またノード「１」とノード「３」のと間に依存関係がある。また、プロセスＣのノード「３」によって、プロセスＤのノード「４」が起床する。つまり、ノード「３」とノード「４」との間に依存関係がある。また、プロセスＤのノード「４」によって、プロセスＡのノード「５」が起床する。つまり、ノード「４」とノード「５」との間に依存関係がある。このような依存パターンによって、図３の下部に示すような依存木が形成される。この依存木が、ノードの実行順序と各ノード間の依存関係とを示す依存解析情報となる。また、依存解析情報に各ノードの実行時間が含まれるものであっても良い。
【００４２】
次に、アプリケーション依存解析部２の依存解析情報作成処理の詳細なフローを説明する。
【００４３】
図４は、図１に示したアプリケーション依存解析部２にて形成された依存木の一例を示す図である。
【００４４】
図４に示すように、上記で説明した起床から休止までの処理区画を意味する依存木の各ノードは、凡例にあるように内部的にはユニークなノード番号とプロセス番号と実行開始プログラムカウンタ、つまり実行開始アドレスとのセットで表される。プログラムカウンタは、この依存グループを実行している際に、その正しさを確認できる情報として使われるほかに、依存グループが重複している事を検出する際にも使用される。
【００４５】
また以下の説明では、依存グループの依存木について、その解析状態から便宜上、未確定依存木と確定依存木との２つの呼び方を使う。未確定依存木とは、現在解析中で、まだ完成していない依存木を指す。
【００４６】
図５は、現在解析中で、まだ完成していない依存木の一例を示す図である。
【００４７】
図５に示すように、破線で示した実行待ちの部分については未確定依存となるため、未確定依存木となる。
【００４８】
また、確定依存木とは完成しており、すぐにグループスケジューリング実行において利用可能な依存木を指す。図４に示したものが確定依存木となる。
【００４９】
次に、図１に示した形態における依存の検出方法について説明する。
【００５０】
図６は、図１に示した形態における依存の検出方法を説明するためのフローチャートである。ここで、ステップＳ１０〜Ｓ１３の処理は、図１に示した時分割スケジューリング実行部１における処理である。また、ステップＳ１００〜Ｓ１０９の処理は、図１に示したアプリケーション依存解析部２における処理である。
【００５１】
まず、監視対象の演算装置上のスケジューラで次に実行されるプロセス候補が選択されたかどうかを判断する（ステップＳ１０）。
【００５２】
次に実行されるプロセス候補が選択されたと判断した場合、次に選択されたプロセスが現在の未確定依存木の未確定依存に適合するか調べる（ステップＳ１０１）。未確定依存とは、図５にて説明したように、プロセス実行中に別のプロセスの実行可能になった事を検知したが、まだ実行されていないため現在構築中の実行依存木の依存の枝が張られていない部分のことを指す。未確定依存部分に依存先として収まるべきプロセスＩＤは判明しているため、次に実行するプロセスがそこに適合するかどうか調べる。
【００５３】
適合する場合は、その未確定依存部分に次に実行するプロセスをあらわすノードを接続し、その未確定依存は確定とする（ステップＳ１０２）。プロセスを表すノードには、このプロセスがユーザ空間で最初に実行されるプログラムカウンタを登録する。
【００５４】
また、適合しない場合は、別の機能を実現するプロセスと判断され、新たに依存木が生成され、そのプロセスは依存木の根となる（ステップＳ１０３）。
【００５５】
その後、プロセスが実行され（ステップＳ１１）、プロセスの実行が終了したかどうかが判断される（ステップＳ１２）。プロセス実行中には、別のプロセスが実行可能になるか否かを常に監視している（ステップＳ１０４）。別のプロセスが実行可能であると判断した場合、別のプロセスが実行可能状態となった原因が実行中プロセスの影響か否かを判断する（ステップＳ１０５）。
【００５６】
別のプロセスが実行可能状態となった原因が実行中プロセスの影響であると判断した場合、実行中プロセスの影響で実行可能状態となったプロセスを、現在実行中のプロセスを表すノードの未確定依存として登録する（ステップＳ１０６）。
【００５７】
また、別のプロセスが実行可能状態となった原因が実行中プロセスの影響ではない場合、ここでは特に何も行わないが、このプロセスが実際に実行される際にステップＳ１０３で新しい依存木を作成する事になる。
【００５８】
一方、プロセスの実行が終了した場合（ステップＳ１３）、実行中だったプロセスを表すノードに実行時間を登録する（ステップＳ１０７）。
【００５９】
そして、この段階で全ての依存が確定している未確定依存木が存在しているかどうかを判断する（ステップＳ１０８）。全ての依存が確定している未確定依存木が存在した場合は、その未確定依存木を確定依存木として解析対象から外し、未確定依存が無い未確定依存木を確定化する（ステップＳ１０９）。
【００６０】
そして、次の候補が無い状態で、未確定依存木がある場合、その依存木も確定したことにする（ステップＳ１００）。
【００６１】
上記のように依存木が確定した後、依存木を記録する際に依存木の整形と重複して検出された依存木の統合を行う。
【００６２】
図７は、依存木の整形と統合との実施を説明するためのフローチャートである。
【００６３】
まず依存木の整形を行うために、依存先が同じプロセスのみかどうかを判断する（ステップＳ２００）。
【００６４】
依存先が同じプロセスのみであると判断した場合、整形では、１つの枝でつながれた同じプロセスを表す２つのノードを１つのノードにする（ステップＳ２０４）。時分割スケジューリングは依存とは関係なく時間によりプロセスを切り替える場合があるため、上記依存木作成手段だけでは本質的には1つのノードとなるべきものが分割されてしまう。その２つのノードを1つに結合させる。その際、プログラムカウンタは依存元の値を使い、実行時間は加算された値を使用する。
【００６５】
また、依存先が同じプロセスのみではないと判断した場合、最後に現在管理している確定依存木群の中で同じ形状の依存木を検索する（ステップＳ２０１）。
【００６６】
同じ形状の依存木が存在する場合、各ノードのプログラムカウンタが同じで、各ノードの実行時間が近い依存木が存在するかどうかを判断する（ステップＳ２０２）。つまり、各ノードの実行時間が予め設定された設定閾値内に収まる依存木が存在するかどうかを判断する。
【００６７】
同じ木の形状を持ち、各ノードのプログラムカウンタが同じで、各ノードの実行時間が近い依存木が存在する場合、その２つの依存木を統合し、１つの依存木として登録する。（ステップＳ２０３）。このとき、実行時間の平均値を各ノードで計算して依存木を合成し、１つの依存木として登録する。
【００６８】
また、これらの依存を解決するための情報である依存解析情報は上記のような動的解析だけでなく、利用者が直接作成して登録する手段も提供する。この場合、利用者によって予め登録された依存解析情報が、アプリケーション依存解析部２からグループスケジューリング実行部４へ提供されるものであっても良い。
【００６９】
また、プロセスのAPI(Application Program Interface)呼び出し状況を監視して、アプリケーションの一連の動作を解析するものであっても良い。
【００７０】
このように形成された依存解析情報は、アプリケーション依存解析部２からグループスケジューリング実行部４へ出力される。
【００７１】
図８は、図１に示した制御変更判定部３における処理を説明するためのフローチャートである。
【００７２】
制御変更判定部３は、時分割スケジューリング実行部１を監視し、保存されている依存木に該当する機能実行が開始されたことを検知し、該当するプロセスの以後の実行をグループスケジューリング実行部４で行われるよう取り計らう。検知は、依存木の根となっているノードが表すプロセスとそのプログラムカウンタとから判断する。
【００７３】
まず、アプリケーション依存解析部２にて形成された依存解析情報から実行候補プロセスを根とする依存木を検索する（ステップＳ３００）。時分割スケジューリング実行部１で実行候補プロセスが選択されるたびにこの検索を行う。
【００７４】
複数候補がある場合、その依存木のスコアの最も高いものを選択する（ステップＳ３０１）。スコアは現段階での依存木間の優先度を示し、依存木の利用頻度やグループスケジューリング実行の成否、現在のシステム全体の実行状況が加味されて増減される。このとき、時分割スケジューリング上での現在のプロセス動作と過去の依存解析情報に基づいて増減されるものであっても良い。この段階でも複数候補がある場合は最近実行された依存木を選択する（ステップＳ３０２）。
【００７５】
以上の処理により、何らかの依存木が適合した場合には、実行候補プロセスをグループスケジューリング実行を行う演算装置で実行を開始させ、以後グループスケジューリング実行部４のスケジューリングに従い処理を進める（ステップＳ３０３）。
【００７６】
また、実行候補プロセスを根とする依存木が存在しない場合、時分割スケジューリング実行部１が実行候補プロセスを実行する（ステップＳ３０４）。
【００７７】
検知に関しては、プログラムカウンタの利用方法のほかに、依存木の根となっているノードが表すプロセスに例外などのイベントを発生させるコードを埋め込む方法もある。イベント発生時のみに依存木検索を行えばよいため、制御変更判定部３の処理を軽減できる効果がある。一方、イベントを発生させる仕組み分だけプロセスの実行速度が低減する。
【００７８】
次に、図１に示したグループスケジューリング実行部４における処理について説明する。
【００７９】
図９は、図１に示したグループスケジューリング実行部４における処理の概要を示す図である。
【００８０】
グループスケジューリング実行部４の主要な仕事は、制御変更判定部３から渡されてきた依存木に従った実行の実現、複数のグループ間の実行優先度付け、グループスケジューリング実行の実行失敗判断である。依存木の実行は、依存グラフにより依存順にほぼ一意に決定される。これを図に示すように一列の仮想キューとして管理し、キューの先頭のプロセスから順に実行していく。仮想キューとは、グループスケジューリング側と時分割スケジューリング側とでのプロセス管理の整合性を取るために導入したものであり、グループスケジューリング実行部４ではこの仮想キューの先頭プロセスが実行する。実行する際に時分割スケジューリング側のキュー（実キュー）からそのプロセス用のキューを取り除くことで、常に時分割スケジューリング側のキューをマスター情報として扱う。これにより、グループスケジューリング実行部４での実行をいつでも中断可能にしている。
【００８１】
グループスケジューリングは、実行パターンを予測してスケジューリングするという投機的実行の側面を持つため、現在採用している実行パターンが正しい保証は無い。したがって、スケジューリング内に現在の実行が正しいか否かを判断するための基準となる失敗判定基準が必要となる。最低限必要な失敗判定基準は、実行プロセスとして選択されたプロセスが実行可能となっていない場合及び依存グループ情報に記録されている実行時間を大幅に超過している場合である。
【００８２】
グループ間の実行優先度付けに関しては、グループの起動順、一定時間でのラウンドロビン、全体実行時間の短い順、グループに別途設定したデッドラインをもとにしたリアルタイムスケジューリングなど、本システムが使用される環境に応じて自由に変更可能である。
【００８３】
図１０は、図１に示したグループスケジューリング実行部４における処理を説明するためのフローチャートである。
【００８４】
実行依存木を仮想キューに変換し、実行キューに投入した時点が実行ノードである。実行キューに実行すべき仮想キューがまだ存在するか否かを判断する（ステップＳ４０１）。
【００８５】
実行キューに実行すべき仮想キューが存在しないと判断した場合、制御変更判定部３に完了通知を行う（ステップＳ４０２）。
【００８６】
また、実行キューに実行すべき仮想キューがまだ存在すると判断した場合、仮想キューより実行される実行予定プロセスが現在実行可能状態になっているか否かを判断する（ステップＳ４０３）。ここで、選択されている依存木が正しいのであれば、次のプロセスは実行可能状態になっているはずである。
【００８７】
実行可能状態になっている場合、実行プロセスを選択し（ステップＳ４０６）、選択したプロセスを実行する（ステップＳ４０８）。
【００８８】
また、実行可能状態になっていない場合、依存木の選択を誤っているため、現在実行した位置まで同型の他の依存木を選択し、実行を継続する。そして、現在の実行位置まで同型の実行依存木が存在するか否かを判断する（ステップＳ４０４）。
【００８９】
現在の実行位置まで同型の実行依存木が存在しない場合、グループスケジューリングの失敗を意味するため、制御変更判定部３に失敗通知を行い、スケジューリング実行を終了する（ステップＳ４０５）。
【００９０】
また、現在の実行位置まで同型の実行依存木が存在する場合は、実行依存木を切り替え、グループスケジューリング実行を継続する（ステップＳ４０７）。そのために、ステップＳ４０６の実行プロセスの選択を行う。
【００９１】
プロセス実行中は（ステップＳ４０９）、実行時間が予め設定された設定閾値計算値を超過しているか否かの判断を定期的に行う（ステップＳ４１０）。実行時時間が予め設定された設定閾値計算値を超過していない場合、プロセスの実行を継続する。また、実行時時間が予め設定された設定閾値計算値を超過している場合は、現在の実行位置まで同型且つ閾値計算値を満たす依存木が存在するか否かを判断する（ステップＳ４１１）。現在の実行位置まで同型且つ閾値計算値を満たす依存木が存在する場合、ステップＳ４０７の処理を行う。つまり、これらの処理を実行すべき依存木（仮想キュー）がなくなるまで繰り返す。そして、実行すべき依存木（仮想キュー）がなくなった場合、ステップＳ４０５の処理を行う。
【００９２】
また、プロセス実行が終了した場合（ステップＳ４１２）、ステップＳ４０１の処理を行う。
【００９３】
また、１つのグループスケジューリング実行を複数の演算装置上で行うことにより高速化を図ることができる。依存グラフの分岐は分岐先のノード間に並列性があることを示しているため、グループスケジューリング実行部４は分岐先のノードを別々の演算装置上で実行させることにより容易に並列処理を実現できる。
【００９４】
また、グループスケジューリング実行部４は、時分割スケジューリングにおけるプロセスを実行するための情報であるプロセス実行管理情報への参照を持つ仮想実行キューを用いてプロセススケジューリングを実施するものであっても良い。これにより、常に時分割スケジューリングに復帰可能となる。
【００９５】
以上述べたように、本発明における複数のプロセス間の依存解析は、プロセスの実行動作結果から推測するものであり、例えば、プロセスの実行順序を解析するものである。また、この依存解析には、高級言語を必要とせず、バイナリ（オブジェクト）のみで実現する。さらに、プロセスのグループ化にコンパイラを必要としない実行時解析＋スケジューリング機構を実現している。
【００９６】
次に、本実施の形態の効果について説明する。
【００９７】
本実施の形態では、時分割スケジューリング実行部１と、アプリケーション依存解析部２と、制御変更判定部３と、グループスケジューリング実行部４とが連携して動作するよう構成されている。そのため、既存のプログラムを一切修正することなくプロセス間の実行依存関係を自動的に検出できる。また、その情報をスケジューリング方針に反映させることによって、複数の演算器やローカルメモリをもつ実行環境において、複数のプロセスの実行シーケンスから構築されるアプリケーション単位でスケジューリングすることを可能とする。
（実施例）
次に、具体的な実施例を用いて本発明を実施するための最良の形態の動作を説明する。
【００９８】
ここでは、４つのCPU上で動作するSMP Linuxに本形態を適用した場合の実施例を説明する。
【００９９】
まず、アプリケーション依存解析部２の実装から説明する。アプリケーション依存解析部２で必要な情報は、プロセスの切り替え、各プロセスの実行状態の変化、その要因である。プロセスの切り替えは、Linuxのスケジューラのコンテキストスイッチ処理部（不図示）に、切り替え監視手段を設けることで実現した。各プロセスの実行状態の変化とその要因の特定は、LinuxがO(1)スケジューリングを実現するために使用しているRUNQの出入りを監視することにより実現した。これにより、コンテキストスイッチ状況を監視することで現在の実行プロセスを明らかにする。また、プロセス実行中にRUNQに入ってくるプロセスを監視することで、現在実行中のプロセスに依存しているプロセスを明らかにする。実際には、RUNQにプロセスが投入される要因として、プロセス実行以外に割り込み処理も存在する。そのため、割込みに関しても同様に監視手段を設けることによって、RUNQに投入されたプロセスの依存先をより正確に把握し、実行依存グラフの精度を向上させるよう実装した。実行依存グラフのノードには、ユーザ空間実行プログラムカウンタと実行時間とを記録した。ユーザ空間実行プログラムカウンタは各プロセスのスタックから抽出した。実行時間は、コンテキストスイッチを監視する際に時間を記録することで算出した。
【０１００】
図１１は、図１に示したグループスケジューリング実行部４内に設けられたデータベースの一構造例を示す図である。なお、このデータベースは、グループスケジューリング実行部４内に必ずしも設けられている必要は無く、グループスケジューリング実行部４に接続可能に構成されているものであれば良い。
【０１０１】
図１１に示すようにデータベースには、各依存グループを示すレベル１テーブルと、その依存木のプロセス間実行依存木を示すレベル２テーブルとを階層的にポインタでつないだ情報管理テーブルが格納されている。レベル１テーブルでは、解析された各グループを１つの行に示す。各エントリは図１１に示すように、左からグループを識別するためのID、グループ情報の有効度を示すスコア、最後に利用された時間を示すタイムスタンプ、依存木を示すレベル２テーブルへのポインタとからなる。グループ情報の有効度は利用される頻度、予測成功によって増減させる。また、レベル２テーブルでは、各ノードを１つの行に示す。各エントリは図１１に示すように、左からノードを識別するためのノードID、プロセスID、実行開始プログラムカウンタ、実行時間、実行開始依存ノードへのポインタとからなる。
【０１０２】
次に、制御変更判定部３に関して説明する。制御変更判定部３もプロセス切り替えの時点で処理するためアプリケーション依存解析部２と同様の位置に監視手段を導入した。コンテキストスイッチ時に、データベース上のプロセス及びプログラムカウンタを、実行候補プロセスと比較し、判定した。
【０１０３】
グループスケジューリング実行部４は、上述した仮想キュー管理システムだけを導入し、キュー操作に関しては、Linuxの優先度システムとプロセスのCPU割付機能を利用して実現した。
【０１０４】
図１２〜１４は、４つのCPUを用いたグループスケジューリング実行部４における処理の概要を示す図である。
【０１０５】
図１２のCPU３には、グループＡが仮想キューの形で投入されている様子を示しており、現在最初のプロセス７が実行されている。プロセス７の実行が休止されると次の候補プロセス１が実行される。その際、図１３に示すように、時分割スケジューリング実行部１のキューにプロセス１が投入されていることを確認する。この時点でキューにプロセス１が投入されていない場合、予測の失敗となり、CPU3の仮想キューは全て取り除く。投入されている場合、図１４に示すように、そのキューから引き抜くと共に、そのプロセス１をCPU3に投入する。以上によりグループスケジューリングを行う。
【０１０６】
上述したように、本発明においては、以下の効果を奏する。
【０１０７】
第１の効果は、アプリケーション実行性能の一定性を高めることにある。その理由は、自動認識した依存関係に基づく実行シーケンスを常に再現可能にしたためである。
【０１０８】
第２の効果は、複数の演算装置とそのローカルメモリとを備える環境で、データの局所性を高めることができることにある。その理由は、アプリケーション実行に関わるプロセスを同じ演算装置およびローカルメモリに集めることが可能なためである。
【０１０９】
第３の効果は、アプリケーション開発の高い生産性と再利用性とを実現できることにある。その理由は、時分割環境向けのアプリケーションを元に、それを構築するプロセス依存関係の自動認識と依存関係に基づいた効率的なスケジューリングとを可能にするためである。
【０１１０】
第４の効果は、実行環境の変化に対応できる応答性能向上スケジューリングを実現出来ることにある。その理由は、実利用環境に組み込まれ、動作しながら最適化が行われるシステムだからである。
【図面の簡単な説明】
【０１１１】
【図１】本発明の情報処理装置の実施の一形態を示す図である。
【図２】図１に示した形態において、時分割スケジューリングとグループスケジューリングとのプロセススケジューリング状態を示す図である。
【図３】時分割スケジューリングと依存グループとの関係を示す図である。
【図４】図１に示したアプリケーション依存解析部にて形成された依存木の一例を示す図である。
【図５】現在解析中で、まだ完成していない依存木の一例を示す図である。
【図６】図１に示した形態における依存の検出方法を説明するためのフローチャートである。
【図７】依存木の整形と統合との実施を説明するためのフローチャートである。
【図８】図１に示した制御変更判定部における処理を説明するためのフローチャートである。
【図９】図１に示したグループスケジューリング実行部における処理の概要を示す図である。
【図１０】図１に示したグループスケジューリング実行部における処理を説明するためのフローチャートである。
【図１１】図１に示したグループスケジューリング実行部内に設けられたデータベースの一構造例を示す図である。
【図１２】４つのＣＰＵを用いたグループスケジューリング実行部における処理の概要を示す図である。
【図１３】４つのＣＰＵを用いたグループスケジューリング実行部における処理の概要を示す図である。
【図１４】４つのＣＰＵを用いたグループスケジューリング実行部における処理の概要を示す図である。
【符号の説明】
【０１１２】
１    時分割スケジューリング実行部
２    アプリケーション依存解析部
３    制御変更判定部
４    グループスケジューリング実行部
【図１】
2009048358.tif 000003
【図２】
2009048358.tif 000004
【図３】
2009048358.tif 000005
【図４】
2009048358.tif 000006
【図５】
2009048358.tif 000007
【図６】
2009048358.tif 000008
【図７】
2009048358.tif 000009
【図８】
2009048358.tif 000010
【図９】
2009048358.tif 000011
【図１０】
2009048358.tif 000012
【図１１】
2009048358.tif 000013
【図１２】
2009048358.tif 000014
【図１３】
2009048358.tif 000015
【図１４】
2009048358.tif 000016