(57)【要約】  静的タスクスケジューリングに基づく実行順序を維持した上で、実行順序の維持に必要な優先度の個数を削減する。  生成した静的タスクスケジューリング結果と、静的タスクスケジューリング結果の前のタスクから見ていく場合は最良実行順序と、後ろから見ていく場合は最悪実行順序と比較し、実行順序が変化しない場合、タスクの優先度を最良実行順序で実行された場合の実行開始時刻以降で先行するタスクの最低優先度と同等若しくは高くし、又は、最悪実行順序で実行された場合の実行終了時刻以前の後続するタスクの最高優先度と同等若しくは低くする。
2014027444.tif 000002
【特許請求の範囲】
【請求項１】
タスクを複数のコアのいずれのコアに配置するかを示すコア配置と、前記タスクの前記コア上での実行順序とを含むタスクスケジューリングを静的に決定した静的タスクスケジューリング結果を生成する静的タスクスケジューリング生成手段と、
前記静的タスクスケジューリング結果の実行順序をタスクが実行される順に見ていき、優先度を付与するタスクである優先度付与対象タスクが他のタスクより優先して実行されると仮定した場合の最も早く実行の開始が可能となる順序である最良実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最良実行順序で実行された場合の実行開始時刻以降で前記優先度付与対象タスクの静的タスクスケジューリング結果の実行順序での実行開始時刻までに先行して実行する全てのタスクよりも低い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最良実行順序で実行された場合の実行開始時刻以降の前記優先度付与対象タスクに先行する全てのタスクの最も低い優先度と同等若しくは高い優先度を前記優先度付与対象タスクに付与する、
又は、
前記静的タスクスケジューリング結果の実行順序をタスクが実行される順序の後ろから見ていき、優先度を付与するタスクである優先度付与対象タスクより他のタスクが優先して実行されると仮定した場合の最も遅く実行の開始が可能となる順序である最悪実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最悪実行順序で実行された場合の実行終了時刻以前で前記優先度付与対象タスクの静的タスクスケジュール結果の実行順序での実行終了時刻に後続して実行する全てのタスクよりも高い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最悪実行順序で実行された場合の実行終了時刻以前の前記優先度付与対象タスクに後続する全てのタスクの最も高い優先度と同等若しくは低い優先度を前記優先度付与対象タスクに付与する、
優先度生成手段とを含む
タスクスケジューリング装置。
【請求項２】
前記優先度生成手段が、
実行順序が変化しない場合に、最も低い優先度と同等以上の優先度として設定可能な最高優先度を付与する、
又は、
実行順序が変化しない場合に、最も高い優先度と同等以下の優先度として設定可能な最低優先度を付与する
請求項１に記載のタスクスケジューリング装置。
【請求項３】
前記優先度生成手段が、
前記最悪実行順序を求める際に、前記優先度付与対象タスクに後続するタスクに従属するタスクを検討対象から除外する
請求項１又は２記載に記載のタスクスケジューリング装置。
【請求項４】
前記優先度生成手段が、
優先度を設定する処理の制御する優先度制御手段と、
前記優先度付与対象タスクがいずれのタスクであるかを示す情報を保持する優先度付与対象タスク保持手段と、
各タスクに設定された優先度を保持する優先度保持手段部と
をさらに含む
請求項１乃至３のいずれか１項に記載のタスクスケジューリング装置。
【請求項５】
前記優先度生成手段が、
実行順序の変動が外部へ影響するタスクである順序変動禁止タスクの実行順序が変動しない範囲で、実行順序の変動が外部に影響しない前記優先度付与対象タスクに、同一の優先度を用いる請求項１乃至４のいずれか１項に記載のタスクスケジューリング装置。
【請求項６】
前記静的タスクスケジューリング生成手段に１つタスクの静的タスクスケジューリングを行わせ、
前記優先度生成手段に、前記静的タスクスケジューリングが行われたタスクを前記優先度付与対象タスクとして、優先度を付与させ、
前記静的タスクスケジューリング生成手段及び前記優先度生成手段の動作を優先度付与対象の全てのタスクについて繰り返すように制御する
装置制御手段を
さらに含む請求項１乃至５のいずれか１項に記載のタスクスケジューリング装置。
【請求項７】
複数のコアを含むマルチコアの装置において、
タスクを複数のコアのいずれのコアに配置するかを示すコア配置と、前記タスクの前記コア上での実行順序とを含むタスクスケジューリングを静的に決定した静的タスクスケジューリング結果を生成し、
前記静的タスクスケジューリング結果の実行順序をタスクが実行される順に見ていき、優先度を付与するタスクである優先度付与対象タスクが他のタスクより優先して実行されると仮定した場合の最も早く実行の開始が可能となる順序である最良実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最良実行順序で実行された場合の実行開始時刻以降で前記優先度付与対象タスクの静的タスクスケジューリング結果の実行順序での実行開始時刻までに先行して実行する全てのタスクよりも低い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最良実行順序で実行された場合の実行開始時刻以降の前記優先度付与対象タスクに先行する全てのタスクの最も低い優先度と同等若しくは高い優先度を前記優先度付与対象タスクに付与する、
又は、
前記静的タスクスケジューリング結果の実行順序をタスクが実行される順序の後ろから見ていき、優先度を付与するタスクである優先度付与対象タスクより他のタスクが優先して実行されると仮定した場合の最も遅く実行の開始が可能となる順序である最悪実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最悪実行順序で実行された場合の実行終了時刻以前で前記優先度付与対象タスクの静的タスクスケジュール結果の実行順序での実行終了時刻に後続して実行する全てのタスクよりも高い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最悪実行順序で実行された場合の実行終了時刻以前の前記優先度付与対象タスクに後続する全てのタスクの最も高い優先度と同等若しくは低い優先度を前記優先度付与対象タスクに付与する、
タスクスケジューリング方法。
【請求項８】
複数のコアを含むマルチコアの装置において、
タスクを複数のコアのいずれのコアに配置するかを示すコア配置と、前記タスクの前記コア上での実行順序とを含むタスクスケジューリングを静的に決定した静的タスクスケジューリング結果を生成する処理と、
前記静的タスクスケジューリング結果の実行順序をタスクが実行される順に見ていき、優先度を付与するタスクである優先度付与対象タスクが他のタスクより優先して実行されると仮定した場合の最も早く実行の開始が可能となる順序である最良実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最良実行順序で実行された場合の実行開始時刻以降で前記優先度付与対象タスクの静的タスクスケジューリング結果の実行順序での実行開始時刻までに先行して実行する全てのタスクよりも低い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最良実行順序で実行された場合の実行開始時刻以降の前記優先度付与対象タスクに先行する全てのタスクの最も低い優先度と同等若しくは高い優先度を前記優先度付与対象タスクに付与する処理、
又は、
前記静的タスクスケジューリング結果の実行順序をタスクが実行される順序の後ろから見ていき、優先度を付与するタスクである優先度付与対象タスクより他のタスクが優先して実行されると仮定した場合の最も遅く実行の開始が可能となる順序である最悪実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最悪実行順序で実行された場合の実行終了時刻以前で前記優先度付与対象タスクの静的タスクスケジュール結果の実行順序での実行終了時刻に後続して実行する全てのタスクよりも高い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最悪実行順序で実行された場合の実行終了時刻以前の前記優先度付与対象タスクに後続する全てのタスクの最も高い優先度と同等若しくは低い優先度を前記優先度付与対象タスクに付与する処理とを、
コンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のコアをスケジューリングする装置及び方法に関し、特に、コアの処理のスケジューリングに関する。
【背景技術】
【０００２】
デジタル機器に対する高性能化又は低消費電量化は、常に、要求されてきた。近年、これらの要求を受け、組み込み等に用いられるＬＳＩ（Large Scale Integration）に複数の「プロセッサ・コア（以下、単に「コア」と言う）」を搭載するマルチコア構成が、注目を集めている。ＬＳＩのマルチコア化は、例えば、システム制御を目的とするリアルタイムシステムにおいて、重要な技術と、なっている。【０００３】
マルチコアを搭載したシステム又は装置は、対照型マルチプロセッシング（ＳＭＰ：Symmetric Multi Processing）方式と、非対称型マルチプロセッシング（ＡＭＰ：Asymmetric Multiple Processing）方式とに、大別される。【０００４】
ＳＭＰ方式は、コアの空き状況及び実行中のタスクの優先度等に応じて、タスクを実行するコアを切り替える。この切り替えに基づき、ＳＭＰ方式は、各タスクを、いずれのコア上でも実行できる。つまり、ＳＭＰ方式は、コアの動的な負荷分散が可能である。動的な負荷分散が可能なため、ＳＭＰ方式は、システム全体の性能を、向上できる。しかし、動的な負荷分散は、リアルタイム性能の予測を、困難とする。従って、ＳＭＰ方式は、リアルタイムシステムへの適用には適していない。【０００５】
一方、ＡＭＰ方式は、各タスクが、特定のコア上で実行される機能分散型である。そのため、ＡＭＰ方式は、システムの挙動が予測できることが重要なリアルタイムシステム、及び、特定のハードウェアが接続されているコアが限定されるシステム等に、好適である。【０００６】
このようなＡＭＰ方式のマルチコアシステムにおいて、システムの性能は、タスクのコアへの配置に応じて変化する。このため、ＡＭＰ方式のマルチコアシステムでは、最適な実行状態となるタスク配置を探索し、タスクの最適な配置を決定することが、必要である。【０００７】
ＡＭＰ方式のマルチコアシステムを活用する手法の一例として、自動並列化コンパイラを用いる方法がある。【０００８】
自動並列化コンパイラとして、静的タスクスケジューリング手法が、研究されている。静的タスクスケジューリング手法として、例えば、次のような処理を用いた手法がある。まず、この手法は、プログラムをタスクに分割する。そして、この手法は、タスクと、タスク間の依存関係とを、グラフ表現したタスクグラフを、作成する。そして、この手法は、作成したタスクグラフを用いて、マルチコアに対して、静的に、タスクを配置する。そして、この手法は、各コア上でのタスクの実行順序を、静的に、スケジューリングする。【０００９】
また、静的タスクスケジューリング手法として、例えば、リストスケジューリングを用いた手法が、ある。（例えば、特許文献１及び非特許文献１を参照）。【００１０】
リストスケジューリングの手法は、特に、各コア上でのタスクのスケジューリングを動的に変更しないシステムにおいて、良好な性能を、得ることができる。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００３−０２９９８８
【非特許文献】
【００１２】
【非特許文献１】Y. K. Kwok and I. Ahmad, "Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors," ACM Computing Surveys, vol. 31, no. 4, pp. 406 -471, December 1999
【発明の概要】
【発明が解決しようとする課題】
【００１３】
特許文献１及び非特許文献１に記載の静的タスクスケジューリング手法は、各コア上でのタスクの実行順序が確定できることを、前提とする。【００１４】
一方、ＡＭＰ方式のマルチコアの利用として、ＲＴＯＳ（Real-Time Operating System）を搭載し、ＲＴＯＳ上でタスクを実行するモデルが、ある。このモデルは、実装の容易さのため、広く用いられている。【００１５】
このモデルでは、ＲＴＯＳが、タスクの実行時に、マルチコアの各コア上でのスケジューリングを、動的に決定する。そのため、このようなシステムにおいて、同一優先度の複数タスクが同時に実行可能となった場合、実際に実行されるタスクは、ＲＴＯＳのスケジューリングの状態に基づき、決定される。つまり、タスクの実行順序は、不確定である。【００１６】
特許文献１及び非特許文献１に記載の自動並列化コンパイラの手法は、ＲＴＯＳ上でタスクを実行するモデルにおいて、実行順序が不確定のため、マルチコアに基づく効果が得られないという問題点があった。【００１７】
この対策として、例えば、実行順序を守るようタスク間での通信を追加するようにプログラムを修正する方法がある。しかし、プログラムを修正する場合、プログラムの再検証が、必要である。そのため、プログラムを修正する方法は、一般的に、好まれない。【００１８】
そこで、プログラムを修正しない方法として、各タスクへの優先度付けを用いる方法が、用いられている。コアで実行するｎ個のタスクがある場合、優先度付けを用いる方法は、ｎ個の優先度、つまり、実行するタスクの数の優先度を用いて、優先度が高い順に、タスクに優先度を付ける。このように、優先度付けを用いる方法は、プログラムを変更せずに、タスクの実行順序を守ることができる。【００１９】
しかし、タスク数が非常に多い場合、全てのタスクに優先度を割り付けることは、現実的でない。タスクが多いシステムは、多数存在する。そのため、タスクが多いシステムへの対策が、問題点となっていた。【００２０】
本発明の目的は、上述の問題点を解決し、静的タスクスケジューリングに基づく実行順序を守った上で、必要な優先度の個数を削減するスケジューリング装置、及び、スケジューリング方法を提供することにある。
【課題を解決するための手段】
【００２１】
本発明のタスクスケジューリング装置は、タスクを複数のコアのいずれのコアに配置するかを示すコア配置と、前記タスクの前記コア上での実行順序とを含むタスクスケジューリングを静的に決定した静的タスクスケジューリング結果を生成する静的タスクスケジューリング生成手段と、前記静的タスクスケジューリング結果の実行順序をタスクが実行される順に見ていき、優先度を付与するタスクである優先度付与対象タスクが他のタスクより優先して実行されると仮定した場合の最も早く実行の開始が可能となる順序である最良実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最良実行順序で実行された場合の実行開始時刻以降で前記優先度付与対象タスクの静的タスクスケジューリング結果の実行順序での実行開始時刻までに先行して実行する全てのタスクよりも低い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最良実行順序で実行された場合の実行開始時刻以降の前記優先度付与対象タスクに先行する全てのタスクの最も低い優先度と同等若しくは高い優先度を前記優先度付与対象タスクに付与する、又は、前記静的タスクスケジューリング結果の実行順序をタスクが実行される順序の後ろから見ていき、優先度を付与するタスクである優先度付与対象タスクより他のタスクが優先して実行されると仮定した場合の最も遅く実行の開始が可能となる順序である最悪実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最悪実行順序で実行された場合の実行終了時刻以前で前記優先度付与対象タスクの静的タスクスケジューリング結果の実行順序での実行終了時刻に後続して実行する全てのタスクよりも高い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最悪実行順序で実行された場合の実行終了時刻以前の前記優先度付与対象タスクに後続する全てのタスクの最も高い優先度と同等若しくは低い優先度を前記優先度付与対象タスクに付与する、優先度生成手段とを含む。【００２２】
本発明のタスクスケジューリング方法は、複数のコアを含むマルチコアの装置において、タスクを複数のコアのいずれのコアに配置するかを示すコア配置と、前記タスクの前記コア上での実行順序とを含むタスクスケジューリングを静的に決定した静的タスクスケジューリング結果を生成し、前記静的タスクスケジューリング結果の実行順序をタスクが実行される順に見ていき、優先度を付与するタスクである優先度付与対象タスクが他のタスクより優先して実行されると仮定した場合の最も早く実行の開始が可能となる順序である最良実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最良実行順序で実行された場合の実行開始時刻以降で前記優先度付与対象タスクの静的タスクスケジューリング結果の実行順序での実行開始時刻までに先行して実行する全てのタスクよりも低い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最良実行順序で実行された場合の実行開始時刻以降の前記優先度付与対象タスクに先行する全てのタスクの最も低い優先度と同等若しくは高い優先度を前記優先度付与対象タスクに付与する、又は、前記静的タスクスケジューリング結果の実行順序をタスクが実行される順序の後ろから見ていき、優先度を付与するタスクである優先度付与対象タスクより他のタスクが優先して実行されると仮定した場合の最も遅く実行の開始が可能となる順序である最悪実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最悪実行順序で実行された場合の実行終了時刻以前で前記優先度付与対象タスクの静的タスクスケジュール結果の実行順序での実行終了時刻に後続して実行する全てのタスクよりも高い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最悪実行順序で実行された場合の実行終了時刻以前の前記優先度付与対象タスクに後続する全てのタスクの最も高い優先度と同等若しくは低い優先度を前記優先度付与対象タスクに付与する。【００２３】
本発明のプログラムは、複数のコアを含むマルチコアの装置において、タスクを複数のコアのいずれのコアに配置するかを示すコア配置と、前記タスクの前記コア上での実行順序とを含むタスクスケジューリングを静的に決定した静的タスクスケジューリング結果を生成する処理と、前記静的タスクスケジューリング結果の実行順序をタスクが実行される順に見ていき、優先度を付与するタスクである優先度付与対象タスクが他のタスクより優先して実行されると仮定した場合の最も早く実行の開始が可能となる順序である最良実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最良実行順序で実行された場合の実行開始時刻以降で前記優先度付与対象タスクの静的タスクスケジューリング結果の実行順序での実行開始時刻までに先行して実行する全てのタスクよりも低い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最良実行順序で実行された場合の実行開始時刻以降の前記優先度付与対象タスクに先行する全てのタスクの最も低い優先度と同等若しくは高い優先度を前記優先度付与対象タスクに付与する処理、又は、前記静的タスクスケジューリング結果の実行順序をタスクが実行される順序の後ろから見ていき、優先度を付与するタスクである優先度付与対象タスクより他のタスクが優先して実行されると仮定した場合の最も遅く実行の開始が可能となる順序である最悪実行順序と、前記静的タスクスケジューリング結果の実行順序とを比較し、実行順序が異なる場合は前記最悪実行順序で実行された場合の実行終了時刻以前で前記優先度付与対象タスクの静的タスクスケジュール結果の実行順序での実行終了時刻に後続して実行する全てのタスクよりも高い優先度を前記優先度付与対象タスクに付与し、実行順序が変化しない場合は前記最悪実行順序で実行された場合の実行終了時刻以前の前記優先度付与対象タスクに後続する全てのタスクの最も高い優先度と同等若しくは低い優先度を前記優先度付与対象タスクに付与する処理とを、コンピュータに実行させる。
【発明の効果】
【００２４】
本発明によれば、静的タスクスケジューリングに基づく実行順序を維持した上で、実行順序の維持に必要な優先度の個数を削減することが可能となる。
【図面の簡単な説明】
【００２５】
【図１】図１は、本発明における第１の実施形態に係るマルチコアシステムの構成の一例を示すブロック図である。
【図２】図２は、第１の実施形態に係るタスクスケジューリング装置の構成の一例を示すブロック図である。
【図３】図３は、第１の実施形態のタスクスケジューリング装置の動作の一例を示すフローチャートである。
【図４】図４は、第１の実施形態のタスクスケジューリング装置の構成の一例を示すブロック図である。
【図５】図５は、第２の実施形態に係る優先度生成部の構成の一例を示すブロック図である。
【図６】図６は、第２の実施形態の優先度生成部の動作の一例を示すフローチャートである。
【図７】図７は、説明に用いる静的タスクスケジューリング結果の一例を示す図である。
【図８】図８は、第２の実施形態に係る動作を説明するための図である。
【図９】図９は、第２の実施形態に係る動作を説明するための図である。
【図１０】図１０は、第２の実施形態に係る動作を説明するための図である。
【図１１】図１１は、第２の実施形態に係る動作を説明するための図である。
【図１２】図１２は、第２の実施形態に係る動作を説明するための図である。
【図１３】図１３は、第２の実施形態に係る動作を説明するための図である。
【図１４】図１４は、第３の実施形態の優先度生成部の動作の一例を示すフローチャートである。
【図１５】図１５は、第３の実施形態に係る動作を説明するための図である。
【図１６】図１６は、第３の実施形態に係る動作を説明するための図である。
【図１７】図１７は、第３の実施形態に係る動作を説明するための図である。
【図１８】図１８は、第３の実施形態に係る動作を説明するための図である。
【図１９】図１９は、第３の実施形態に係る動作を説明するための図である。
【図２０】図２０は、第３の実施形態に係る動作を説明するための図である。
【図２１】図２１は、第４の実施形態の優先度生成部の動作の一例を示すフローチャートである。
【図２２】図２２は、説明に用いる静的タスクスケジューリング結果の一例を示す図である。
【図２３】図２３は、説明で参照する第２の実施形態の結果を示す図である。
【図２４】図２４は、第４の実施形態に係る動作を説明するための図である。
【図２５】図２５は、第４の実施形態に係る動作を説明するための図である。
【図２６】図２６は、第４の実施形態に係る動作を説明するための図である。
【図２７】図２７は、第４の実施形態に係る動作を説明するための図である。
【図２８】図２８は、第４の実施形態に係る動作を説明するための図である。
【図２９】図２９は、第４の実施形態に係る動作を説明するための図である。
【図３０】図３０は、第４の実施形態に係る動作を説明するための図である。
【図３１】図３１は、第５の実施形態に係るタスクスケジューリング装置の構成の一例を示すブロック図である。
【図３２】図３２は、第５の実施形態に係るタスクスケジューリング装置の動作の一例を示すフローチャートである。
【図３３】図３３は、第５の実施形態に係る動作を説明するための図である。
【図３４】図３４は、第５の実施形態に係る動作を説明するための図である。
【図３５】図３５は、第５の実施形態に係る動作を説明するための図である。
【図３６】図３６は、第５の実施形態に係る動作を説明するための図である。
【図３７】図３７は、第５の実施形態に係る動作を説明するための図である。
【図３８】図３８は、第５の実施形態に係る動作を説明するための図である。
【発明を実施するための形態】
【００２６】
次に、本発明の実施形態について、図面を参照して、説明する。
【００２７】
なお、各図面は、本発明の実施形態を説明するためのものである。そのため、本発明は、各図面の記載に限られるわけではない。また、各図面の同様の構成には、同じ番号を付し、その繰り返しの説明を、省略する場合がある。
【００２８】
また、本発明において、コアで実行する処理単位は、特に制限はない。例えば、処理単位は、タスク、又は、スレッドでも良い。また、処理単位は、タスク又はスレッドをまとめたアプリケーションプログラムでも良い。以下では、これら処理単位をまとめ、「タスク」として、説明する。そのため、以下の実施形態の説明では、本発明のスケジューリング装置を、タスクスケジューリング装置として説明する。
【００２９】
（第１の実施形態）
まず、本発明における第１の実施形態について説明する。
【００３０】
図１は、本発明のおける第１の実施形態に係るマルチコアシステム１の構成の一例を示すブロック図である。
【００３１】
マルチコアシステム１は、タスクスケジューリング装置１０と、コア部２０と、タスクメモリ３０とを含む。
【００３２】
コア部２０は、複数のコアを含む。コアは、タスクスケジューリング装置１０が生成するスケジューリングに基づいて、タスクが割り当てられ、割り当てられたタスクを実行する。
【００３３】
タスクスケジューリング装置１０は、後ほど詳細に説明するように、タスクをスケジューリングし、所定のコアでタスクを実行させる。
【００３４】
タスクメモリ３０は、コアで実行されるタスクを、記憶する。
【００３５】
ここで、マルチコアシステム１は、全ての構成を組み込んだ組み込みＬＳＩでも良い。あるいは、マルチコアシステム１は、１つ又は複数の機能を含む複数のＬＳＩを信号線で接続したＬＳＩシステムでも良い。あるいは、マルチコアシステム１は、１つ又は複数の機能を含む複数の装置を、バス又は通信線で接続したシステムでも良い。
【００３６】
なお、図１に示すタスクスケジューリング装置１０は、マルチコアシステム１に含まれるとした。しかし、本実施形態のタスクスケジューリング装置１０は、これに限らない。例えば、タスクスケジューリング装置１０は、マルチコアシステム１に含まれなくても良い。つまり、マルチコアシステム１は、タスクスケジューリング装置１０を含まない構成でも良い。その構成の場合、例えば、本実施形態のタスクスケジューリング装置１０は、予め、タスクスケジューリングを作成する。そして、タスクスケジューリング装置１０は、作成したタスクスケジューリングを図示しない記憶装置に保存する。マルチコアシステム１は、タスクの実行時に、図示しない記憶装置から作成済みのタスクスケジューリングを取り出し、用いればよい。
【００３７】
次に、タスクスケジューリング装置１０について、図面を参照して、より詳細に説明する。
【００３８】
図２は、タスクスケジューリング装置１０の構成の一例を示すブロック図である。
【００３９】
タスクスケジューリング装置１０は、静的タスクスケジューリング生成部１１と、優先度生成部１２とを含む。なお、図２は、本発明に関連する機能を示し、タスクに関するマルチコアの選択機能など他の機能については、省略した。
【００４０】
静的タスクスケジューリング生成部１１は、タスクをどのコアに配置するかを表すコア配置と、タスクの各コア上での実行順序とを静的に決定（生成）する。つまり、静的タスクスケジューリング生成部１１は、静的なタスクのスケジューリングを生成する。
【００４１】
優先度生成部１２は、静的タスクスケジューリング生成部１１で決定された各コア上での実行順序に従って、各タスクが実行されるように、タスクに優先度を付ける（付与する／生成する）。ただし、本実施形態の優先度生成部１２は、全てのタスクに異なる優先度を付けるのではなく、使用する優先度の個数を削減するように、タスクに優先度を付ける。この優先付けについては、後ほど説明する。
【００４２】
次に、タスクスケジューリング装置１０の動作について説明する。
【００４３】
図３は、タスクスケジューリング装置１０の動作の一例を示すフローチャートである。
【００４４】
まず、タスクスケジューリング装置１０の静的タスクスケジューリング生成部１１は、静的タスクスケジューリングを生成（決定）する（ステップＳ１００）。
【００４５】
より具体的には、静的タスクスケジューリング生成部１１は、静的タスクスケジューリングとして、次に示す項目を静的に決定（生成）する。（以下、静的タスクスケジューリングの結果を「静的タスクスケジューリング結果」と言うこともある。）
（１）タスクを、どのコアに、配置するかを、表すコア配置
（２）各コア上での、タスクの実行順序
なお、本実施形態の静的タスクスケジューリング生成部１１は、静的タスクスケジューリングに用いる手法に、特に制限はない。例えば、静的タスクスケジューリング生成部１１は、既に説明した特許文献１又は非特許文献１に記載した技術を、用いても良い。
【００４６】
次に、タスクスケジューリング装置１０の優先度生成部１２は、静的タスクスケジューリング生成部１１が決定した実行順序（上記（２）項）でタスクが実行されるように、タスクに優先度を付ける（優先度を生成する）（ステップＳ１０１）。ただし、本実施形態の優先度生成部１２は、タスクに設定する優先度の個数を削減するように、優先度を付ける。
【００４７】
本実施形態の優先度生成部１２の優先度付けについて、さらに説明する。
【００４８】
＜第１の手法＞
まず、優先度生成部１２が、静的タスクスケジューリング生成部１１が決定した静的タスクスケジューリング結果を、タスクが実行される順に、見ていく（優先度を付ける）場合の手法について、説明する。
【００４９】
この手法では、優先度生成部１２は、最初に実行されるタスク（以下、「先頭タスク」と言う）に、最も高い優先度（最高優先度）を、付与する。そして、優先度生成部１２は、静的タスクスケジューリング結果の後ろのタスクに行く（進む）に従って、タスクに付与する優先度を下げる。このような優先度の付与を用いて、優先度生成部１２は、タスクの実行順序を維持する。
【００５０】
ただし、優先度生成部１２は、付与する優先度に関わらず実行の順序の変動が起こらない箇所については、後ろのタスクに付与する優先度を、下げない。より具体的に説明すると、優先度生成部１２は、付与する優先度に関わらず実行の順序の変動が起こらない箇所については、後ろのタスクに付与する優先度を、前のタスクの優先度と同等又は高くする。
【００５１】
ここで、優先度生成部１２は、可能な限り高い優先度（最も望ましくは、先頭タスクの優先度と同等の最高優先度）を付与することが望ましい。これは、次の示す理由に基づく。高い優先度をタスクに設定すると、優先度生成部１２は、そのタスクに続くタスクに設定する優先度を、高い優先度に続く優先度から付与できる。そのため、優先度生成部１２は、タスクの付与するために必要となる優先度の個数を、削減できる。
【００５２】
この優先度生成部１２の動作をより詳細に説明する。
【００５３】
優先度生成部１２は、優先度付与対象のタスクが他のタスクより優先して実行されると仮定した場合に、最も早く実行の開始が可能となる順序である「最良実行順序」を求める。
【００５４】
そして、優先度生成部１２は、先頭タスクから各タスクの最良実行順序と、静的タスクスケジューリング結果の実行順序とを比較する。比較の結果として実行順序が異なる場合、そのタスクは、実行順序の変動が起こりえるタスクである。一方、比較の結果として実行順序が同じ場合、そのタスクは、実行順序の変動が起こりえないタスクである。
【００５５】
そこで、タスクの最良実行順序と静的タスクスケジューリング結果の実行順序とが異なる場合、優先度生成部１２は、次のように動作する。まず、優先度生成部１２は、そのタスクが最良実行順序で実行された場合の実行開始時刻以降で、そのタスクの静的タスクスケジューリング結果の実行順序での実行開始時刻までに先行して実行するタスク（以下、「先行実行タスク」と言う）の全ての優先度を調べる。そして、優先度生成部１２は、全ての先行実行タスクの優先度より低い優先度を、そのタスクに、付与する。まとめると、優先度生成部１２は、そのタスクの全ての先行実行タスクの優先度より低い優先度を、そのタスクに付与する。
【００５６】
つまり、優先度生成部１２は、先行するタスクの優先度を、後続するタスクの優先度と比較して、相対的に、高くする。この優先度の付与に基づき、優先度生成部１２は、タスクの実行順序を、維持する。
【００５７】
一方、タスクの最良実行順序と静的タスクスケジューリング結果の実行順序とが変化しない場合、優先度生成部１２は、そのタスクに先行する全てのタスクの最低の優先度と同等又は高い優先度（既に説明のとおり最高優先度が望ましい）を、そのタスクに付与する。つまり、優先度生成部１２は、先行するタスクの優先度を、後続するタスクの優先度と比較して、相対的に、同等又は低くする。この優先度の付与に基づき、優先度生成部１２は、必要な優先度の個数を、削減する。
【００５８】
＜第２の手法＞
次に、優先度生成部１２が、静的タスクスケジューリング生成部１１が決定した静的タスクスケジューリング結果を、タスクが実行される順序の後ろから、見ていく（優先度を付ける）場合の手法について、説明する。
【００５９】
この手法では、優先度生成部１２は、最後に実行されるタスク（以下、「最終タスク」と言う）に、最も低い優先度（最低優先度）を、付与する。そして、優先度生成部１２は、静的タスクスケジューリング結果の前のタスクに行く（戻る）に従って、タスクに付与する優先度を上げる。このような優先度の付与を用いて、優先度生成部１２は、タスクの実行順序を維持する。
【００６０】
ただし、優先度生成部１２は、付与する優先度に関わらず実行の順序の変動が起こらない箇所については、前のタスクに付与する優先度を、上げない。より具体的に説明すると、優先度生成部１２は、付与する優先度に関わらず実行の順序の変動が起こらない箇所については、前のタスクに付与する優先度を後ろのタスクの優先度と同等又は低くする。
【００６１】
ここで、優先度生成部１２は、可能な限り低い優先度（最も望ましくは、最終タスクの優先度と同等の最低優先度）を付与することが望ましい。これは、次に示す理由に基づく。低い優先度をタスクに設定すると、優先度生成部１２は、そのタスクの前のタスクに設定する優先度を、低い優先度に続く優先度から付与できる。そのため、優先度生成部１２は、タスクに付与するために必要となる優先度の個数を、削減できる。
【００６２】
この優先度生成部１２の動作をより詳細に説明する。
【００６３】
優先度生成部１２は、優先度付与対象のタスクより他のタスクが優先して実行されると仮定した場合に、最も遅く実行の開始が可能となる順序である「最悪実行順序」を求める。
【００６４】
そして、優先度生成部１２は、最終タスクから各タスクの最悪実行順序と静的タスクスケジューリング結果の実行順序とを比較する。比較の結果として順序が異なる場合、そのタスクは、実行順序の変動が起こりえるタスクである。一方、比較の結果として順序が同じ場合、そのタスクは、実行順序の変動が起こりえないタスクである。
【００６５】
そこで、タスクの最悪実行順序と静的タスクスケジューリング結果の実行順序とが異なる場合、優先度生成部１２は、次のように動作する。まず、優先度生成部１２は、そのタスクが最悪実行順序で実行された場合の実行終了時刻以前で、そのタスクの静的タスクスケジューリング結果の実行順序での実行終了時刻に後続して実行するタスク（以下、「後続実行タスク」と言う）の全ての優先度を調べる。そして、優先度生成部１２は、全ての後続実行タスクの優先度よりも高い優先度を、そのタスクに、付与する。まとめると、優先度生成部１２は、そのタスクの全ての後続実行タスクの優先度より高い優先度を、そのタスクに、付与する。
【００６６】
つまり、優先度生成部１２は、先行するタスクの優先度を、後続するタスクの優先度と比較して、相対的に、高くする。この優先度の付与に基づき、優先度生成部１２は、タスクに実行順序を、維持する。
【００６７】
一方、タスクの最悪実行順序と静的タスクスケジューリング結果の実行順序とが変化しない場合、優先度生成部１２は、そのタスクに後続する全てのタスクの優先度と同等又は低い優先度（既に説明のとおり最低優先度が望ましい）を、そのタスクに付与する。つまり、優先度生成部１２は、先行するタスクの優先度を、後続するタスクの優先度と比較して、相対的に、同等又は低くする。この優先度の付与に基づき、優先度生成部１２は、必要な優先度の個数を、削減する。
【００６８】
なお、最悪実行順序を求める際、優先度生成部１２は、望ましくは、後続するタスクに更に従属するタスクを、検討対象から除外した上で、最悪実行順序を求める。
【００６９】
また、優先度生成部１２は、最良実行順序又は最悪実行順序として、例えば、タスクの実行順序の数値を用いても良い。ただし、本実施形態の優先度生成部１２が用いる実行順序は、タスクの実行順序に限らない。優先度生成部１２が用いる実行順序は、タスクの実行開始時刻又は実行終了時刻など、優先度生成部１２においてタスクの順序関係が判断できれば、表現形式を限定されない。例えば、あるタスクの実行中に別の高い優先度が付与されてタスクが起動した場合、起動したタスクに実行が遷移する。このような場合、優先度生成部１２１は、単純にタスクの並びとして順序を表現できない。このような場合、優先度生成部１２は、実行順序として、時刻を用いた表現を用いても良い。
【００７０】
なお、本実施形態のタスクスケジューリング装置１０の構成は、図２に示す構成に限らない。各構成は、さらに複数の構成に分けられても良い。あるいは、タスクスケジューリング装置１０は、図２に示す構成を、１つの構成に含めても良い。
【００７１】
また、本実施形態のタスクスケジューリング装置１０は、ハードウェア構成も特に制限はない。例えば、タスクスケジューリング装置１０は、ＣＰＵ（Central Processing Unit）と、ＲＯＭ（Read Only Memory）と、ＲＡＭ（Random Access Memory）とを含むコンピュータとして実現しても良い。
【００７２】
図４は、本実施形態のタスクスケジューリング装置１０と同様に動作するタスクスケジューリング装置６０のハードウェアの構成の一例を示す図である。
【００７３】
タスクスケジューリング装置６０は、ＣＰＵ６１０と、ＲＯＭ６２０と、ＲＡＭ６３０と、記憶装置６４０と、ＩＯ（Input/Output）６５０と、入力機器６６０と、表示機器６７０とを含み、コンピュータを構成している。
【００７４】
ＣＰＵ６１０は、ＲＯＭ６２０又は記憶装置６４０からプログラムを読み込む。そして、ＣＰＵ６１０は、読み込んだプログラムに基づいて、図２に示すタスクスケジューリング装置１０の静的タスクスケジューリング生成部１１と、優先度生成部１２としての、各機能を実現する。ＣＰＵ６１０は、各機能を実現する際に、ＲＡＭ６３０及び記憶装置６４０を一時記憶として使用する。また、ＣＰＵ６１０は、ＩＯ６５０を介して、入力機器６６０から入力データを受信し、表示機器６７０にデータを表示する。
【００７５】
なお、ＣＰＵ６１０は、コンピュータで読み取り可能なプログラムを記憶した記憶媒体７００が含むプログラムを、図示しない記憶媒体読み取り装置を用いて、読み込んでも良い。あるいは、ＣＰＵ６１０は、図示しないネットワークを介して、外部の装置から、プログラムを受け取っても良い。
【００７６】
ＲＯＭ６２０は、ＣＰＵ６１０が実行するプログラム、及び、固定的なデータを記憶する。ＲＯＭ６２０は、例えば、Ｐ−ＲＯＭ(Programmable-ROM）又はフラッシュＲＯＭである。
【００７７】
ＲＡＭ６３０は、ＣＰＵ６１０が実行するプログラム及びデータを一時的に記憶する。ＲＡＭ６３０は、例えば、Ｄ−ＲＡＭ（Dynamic-RAM）である。
【００７８】
記憶装置６４０は、タスクスケジューリング装置６０で長期的に保存するデータ及びプログラムを保存する。また、記憶装置６４０は、ＣＰＵ６１０の一時記憶装置として動作しても良い。記憶装置６４０は、例えば、ハードディスク装置、光磁気ディスク装置、ＳＳＤ（Solid State Drive）、又は、ディスクアレイ装置である。
【００７９】
ＩＯ６５０は、ＣＰＵ６１０と、入力機器６６０及び表示機器６７０とのデータを仲介する。ＩＯ６５０は、例えば、ＩＯインターフェースカードである。
【００８０】
入力機器６６０は、タスクスケジューリング装置６０の操作者からの入力指示を受信する入力部である。入力機器６６０は、例えば、キーボード、マウス又はタッチパネルである。
【００８１】
表示機器６７０は、タスクスケジューリング装置６０の表示部である。表示機器６７０は、例えば、液晶ディスプレイである。
【００８２】
なお、図４に示すタスクスケジューリング装置６０は、タスクスケジューリング装置１０としての機能に加え、図１に示すコア部２０及びタスクメモリ３０の機能を含み、マルチコアシステム１として動作しても良い。
【００８３】
この場合、ＣＰＵ６１０は、図１に示すコア部２０、つまり、複数のコアを含む。
【００８４】
また、ＣＰＵ６１０が図示しない内蔵メモリを含む場合、タスクスケジューリング装置６０は、内蔵メモリを、タスクメモリ３０として用いても良い。あるいは、タスクスケジューリング装置６０は、ＲＡＭ６３０又は記憶装置６４０を、タスクメモリ３０として用いても良い。
【００８５】
本実施形態のタスクスケジューリング装置１０の効果について説明する。
【００８６】
このように構成された本実施形態のタスクスケジューリング装置１０は、静的タスクスケジューリング結果に基づく実行順序を維持した上で、実行順序の維持に必要な優先度の個数を削減する効果を得ることができる。
【００８７】
その理由は、次のとおりである。
【００８８】
本実施形態のタスクスケジューリング装置１０は、静的タスクスケジューリング結果を決定する。そして、タスクスケジューリング装置１０は、各タスクについて、タスクの優先度に基づいて実行順序が変わりえる箇所（タスク）と、優先度に関わらず実行順序が変わりえない箇所（タスク）とに分類する。
【００８９】
順序が変わりえる箇所の場合、タスクスケジューリング装置１０は、先行するタスクの優先度を、後続するタスクの優先度と比較して相対的に高くするように、優先度と付与する。そのため、タスクスケジューリング装置１０は、タスクの実行順序を、維持できる。
【００９０】
一方、順序が変わりえない箇所の場合、タスクスケジューリング装置１０は、先行するタスクの優先度を、後続するタスクの優先度と比較して相対的に同等又は低くする。
【００９１】
より具体的に説明すると、次のとおりになる。静的タスクスケジューリング結果の先頭から優先度を設定する場合、タスクスケジューリング装置１０は、先行する全てのタスクの最低の優先度と同等又は高い優先度を付与する。静的タスクスケジューリング結果の実行される順序の後ろから優先度を設定する場合、タスクスケジューリング装置１０は、後続する全てのタスクの最高の優先度と同等又は低い優先度を付与する。そのため、タスクスケジューリング装置１０は、必要な優先度の個数を、削減できる。
【００９２】
（第２の実施形態）
静的タスクスケジューリング結果の先頭タスクから優先度を定義（付与）していく手法（第１の手法）を用いるタスクスケジューリング装置１０の、より詳細な実施形態について、第２の実施形態として、説明する。
【００９３】
繰り返しの説明となるが、本実施形態のタスクスケジューリング装置１０が用いる手法は、静的タスクスケジューリング結果に基づく実行順序の、先頭タスクから優先度を定義する方法であり、次のような動作を含む。
【００９４】
まず、タスクスケジューリング装置１０は、各タスクの優先度に基づいて実行順序が変わりえる箇所と、優先度に基づいて実行順序が変わらない箇所とを、分類する。タスクスケジューリング装置１０は、実行順序が変わりえる箇所について、先行するタスクの優先度に対し、後続のタスクの優先度を、低く定義する。この動作に基づき、タスクスケジューリング装置１０は、タスクの実行順序を、維持する。
【００９５】
一方、タスクスケジューリング装置１０は、実行順序が変わらない箇所について、先行するタスクの優先度に対して、後続のタスクの優先度を、下げない。この動作に基づき、タスクスケジューリング装置１０は、必要な優先度の個数を、抑制する。
【００９６】
上記の動作を実現するため、本実施形態のタスクスケジューリング装置１０の優先度生成部１２は、図５に示す構成を含む。なお、本実施形態のタスクスケジューリング装置１０の構成は、図５に示す優先度生成部１２の構成を除き、第１の実施形態の同じ構成のため、同じ構成の説明を省略する。
【００９７】
図５は、本実施形態の優先度生成部１２の構成の一例を示すブロック図である。
【００９８】
優先度生成部１２は、優先度制御部１２１と、優先度付与対象タスク保持部１２２と、優先度保持部１２３とを含む。
【００９９】
優先度制御部１２１は、タスクの優先度の設定（付与）の処理を、制御する。
【０１００】
優先度付与対象タスク保持部１２２は、優先度付与対象タスクが、いずれのタスクであるかを示す情報を、保持する。
【０１０１】
優先度保持部１２３は、タスクに設定された優先度の値を、保持する。本実施形態の優先度保持部１２３は、少なくとも、優先度を設定するタスクの数の優先度の値を保持する領域を、備える。
【０１０２】
なお、本実施形態のタスクスケジューリング装置１０は、図４に示すタスクスケジューリング装置６０と同様に、ＣＰＵ６１０と、ＲＯＭ６２０と、ＲＡＭ６３０とを含むコンピュータで実現されても良い。
【０１０３】
次に、本実施形態の優先度生成部１２の動作について、図面を参照して、説明する。
【０１０４】
図６は、本実施形態の優先度生成部１２の動作の一例を示すフローチャートである。
【０１０５】
優先度生成部１２は、図６に示す処理を、スケジューリングの対象となる各コアに対し、実施する。なお、タスクスケジューリングに用いる最高優先度は、予め、タスクスケジューリング装置１０に、設定されていてもよい。
【０１０６】
まず、優先度制御部１２１は、タスクスケジューリングに用いる最高優先度を設定する（ステップＳ２０１）。優先度制御部１２１は、最高優先度として、任意の値を用いても良い。また、優先度制御部１２１は、既に説明したように、最高優先度が予め設定されていても良い。あるいは、優先度制御部１２１は、タスクスケジューリングで設定するタスクより重要な処理で必要とする優先度を取り除き、残った利用可能な優先度の中で最も高い優先度を、最高優先度としても良い。
【０１０７】
次に、優先度制御部１２１は、静的タスクスケジューリング結果の中の先頭から、順に、タスクを選択する。以下、選択されたタスクは、「優先度付与対象タスク」と言う。優先度制御部１２１は、優先度付与対象タスクを、優先度付与対象タスク保持部１２２に、設定する（ステップＳ２０２）。
【０１０８】
続いて、優先度制御部１２１は、優先度付与対象タスクの実行順序の変動の可能性を、調べる（ステップＳ２０３）。
【０１０９】
より具体的に説明すると、次のようになる。
【０１１０】
優先度制御部１２１は、優先度付与対象タスクが他のタスクより優先して実行されると仮定した場合に、最も早く実行の開始が可能となる順序である最良実行順序を求める。そして、優先度制御部１２１は、最良実行順序と、静的タスクスケジューリング結果の実行順序とを比較する。
【０１１１】
実行順序が異なる場合、優先度制御部１２１は、実行順序の変動が起こり得ると判断する。一方、実行順序が等しい場合、優先度制御部１２１は、実行順序の変動が起こり得ないと判断する。
【０１１２】
実行順序の変動が起こり得る場合（ステップＳ２０３でＹｅｓ）、優先度制御部１２１は、優先度付与対象タスクの全ての先行実行タスクの優先度より低い優先度を、優先度付与対象タスクに、付与する（ステップＳ２０４）。
【０１１３】
例えば、優先度が高いタスクに付与する優先度の値が小さく、優先度が低いタスクに付与する優先度の値が大きいとすると、優先度制御部１２１は、優先度の数値が大きい値を、優先度付与対象タスクに設定する。これは、優先度付与対象タスクの優先度を下げることになる。
【０１１４】
なお、優先度制御部１２１は、低い優先度として、優先度が一つ下がる（低くなる）値にすることが望ましい。このように設定すると、使用されない優先度が発生せず、使用する優先度の個数が少なくなるためである。
【０１１５】
優先度制御部１２１は、付与した優先度を優先度保持部１２３の優先度付与対象タスクの領域に保存する。
【０１１６】
この動作に基づき、優先度制御部１２１は、タスクの実行順序を維持する。
【０１１７】
一方、実行順序の変動が起こり得ない場合（ステップＳ２０３  Ｎｏ）、優先度制御部１２１は、優先度付与対象タスクに付与する優先度を下げない（ステップＳ２０５）。
【０１１８】
例えば、優先度が高いタスクに付与する優先度の値が小さく、優先度が低いタスクに付与する優先度の値が大きいとすると、優先度制御部１２１は、優先度付与対象タスクに、先行するタスクの優先度の数値として同等又は低い値を付ける。
【０１１９】
なお、優先度制御部１２１は、優先度として、最高優先度の値を設定することが望ましい。ただし、優先度制御部１２１は、必要に応じて最高優先度以外で現在の優先度より高い優先度を付与しても良く、優先度を同等としても良い。
【０１２０】
優先度制御部１２１は、付与した優先度を優先度保持部１２３のうち優先度付与対象タスクの領域に保存する。
【０１２１】
この動作に基づき、優先度制御部１２１は、必要な優先度の個数を、削減する。
【０１２２】
優先度付与対象タスクに優先度を設定すると、優先度制御部１２１は、スケジューリングの対象のコアの全てのタスクについて、優先度付けが終了したか否かを判定する（ステップＳ２０６）。
【０１２３】
終了した場合（ステップＳ２０６でＹｅｓ）、優先度制御部１２１は、優先度の付与の処理を終了する。
【０１２４】
終了していない場合（ステップＳ２０６でＮｏ）、優先度制御部１２１は、ステップＳ２０２に戻り、静的タスクスケジューリング結果の次のタスク（１つ後のタスク）を優先度付与対象タスクに設定して、上記の処理を繰り返す。
【０１２５】
次に、図面を用いて、図６を参照して説明した処理について、さらに説明する。
【０１２６】
図７は、説明に用いる静的タスクスケジューリング結果の一例を示す図である。
【０１２７】
図７は、コア０とコア１との２つのコアを示している。優先度制御部１２１は、コア０のタスクに優先度を付与するとする。コア０上には、図７に示すようにタスクＡからタスクＦまでの６つのタスクが配置されている。コア１のタスクは、表示を省略した。また、各タスク間の依存関係が、破線の矢印で示されている。この依存関係は、矢印の根元のタスクが完了後、矢印の先のタスクの実行が可能となる関係である。
【０１２８】
タスクＡは、先頭タスクである。タスクＢは、図示を省略したコア１のタスクの完了後、実行可能となるタスクである。タスクＣは、タスクＡの完了後、実行可能なタスクである。タスクＤは、タスクＡの完了後、実行可能なタスクである。タスクＥは、タスクＤの完了後、実行可能なタスクである。タスクＦは、最終タスクであり、タスクＤの完了後、実行可能なタスクである。
【０１２９】
また、優先度は、数値が小さいタスクの優先度が高いとする。つまり、同時に複数のタスクが実行可能な場合、優先度の数値が小さいタスクが、実行される。なお、数値が小さいタスクの優先度が低いとする場合、数値の大小を入れ替えればよい。また、最高優先度は、「３」とする。（つまり、優先度の最小値は、「３」とする。）
続いて、図７に示す静的タスクスケジューリング結果を用いて、優先度制御部１２１の動作について図面を参照して説明する。
【０１３０】
図８乃至図１３は、優先度制御部１２１が、設定する優先度を説明するための図である。図中の数値は、タスクに設定された優先度である。
【０１３１】
まず、優先度制御部１２１は、静的タスクスケジューリング結果の先頭タスクであるタスクＡの優先度を定義（付与）する。（これは、優先度制御部１２１が、タスクＡを優先度付与対象タスクに設定することである。）タスクＡは、先頭タスクである。そこで、優先度制御部１２１は、タスクＡに最高優先度である「３」を定義する（図８）。
【０１３２】
次に、優先度制御部１２１は、優先度付与対象タスクとして、タスクＡの次に実行されるタスクＢを設定する。そして、優先度制御部１２１は、タスクＢの実行順序変動可能性について判断する。より具体的に説明すると、優先度制御部１２１は、タスクＢがスケジューリングされている時刻より前に実行される可能性があるか否かを判断する。
【０１３３】
ここで、タスクＢは、コア１との依存関係に基づき、スケジューリングされている実行位置より前に実行されることはない。つまり、タスクＢの最良実行順序は、図に示された静的タスクスケジューリング結果の実行順序と同じである。そのため、優先度制御部１２１は、タスクＢの実行順序変動可能性がないと判断する。
【０１３４】
優先度に関わらずタスクＢは、実行順序変動可能性がない。そのため、優先度制御部１２１は、タスクＢの優先度を先行するタスクＡより下げる処理を行わず、タスクＢの優先度を「３」とする（図９）。
【０１３５】
次に、優先度制御部１２１は、タスクＢの次に実行されるタスクＣを優先度付与対象タスクとする。そして、優先度制御部１２１は、タスクＣの実行順序変動可能性を判断する。
【０１３６】
タスクＣは、タスクＡとの依存関係があるが、タスクＢとは依存関係がない。そのため、優先度に基づき、タスクＣは、タスクＢと入れ替わり、前に実行される可能性がある。つまり、タスクＣの最良実行順序は、タスクＡの直後である。この順序は、静的タスクスケジューリング結果の実行順序と異なる。そのため、優先度制御部１２１は、タスクＣを実行順序変動可能性があると判断する。
【０１３７】
そこで、優先度制御部１２１は、タスクＣの全ての先行実行タスクより低い優先度を、タスクＣに付与する。今の場合、タスクＣの先行実行タスクは、タスクＢである。そこで、優先度制御部１２１は、タスクＣの優先度を、タスクＢの優先度「３」より下げた「４」とする（図１０）。
【０１３８】
次に、優先度制御部１２１は、タスクＣの次に実行されるタスクＤを優先度付与対象タスクとする。そして、優先度制御部１２１は、タスクＤの実行順序変動可能性を判断する。
【０１３９】
タスクＤは、タスクＡとの依存関係があるが、タスクＢ及びタスクＣとは依存関係がない。そのため、優先度に基づき、タスクＤは、タスクＢ及びタスクＣと入れ替わり、前に実行される可能性がある。つまり、タスクＤの最良実行順序は、タスクＡの直後である。この順序は、静的タスクスケジューリング結果の実行順序と異なる。そのため、優先度制御部１２１は、タスクＤを実行順序変動可能性があると判断する。
【０１４０】
そこで、優先度制御部１２１は、タスクＤの全ての先行実行タスクより低い優先度を、タスクＤに付与する。今の場合、タスクＤの先行実行タスクは、タスクＢ及びタスクＣである。そこで、優先度制御部１２１は、タスクＤの優先度を、タスクＣの優先度「４」より下げた「５」とする（図１１）。
【０１４１】
次に、優先度制御部１２１は、タスクＤの次に実行されるタスクＥを優先度付与対象タスクとする。そして、優先度制御部１２１は、タスクＥの実行順序変動可能性を判断する。
【０１４２】
タスクＥは、タスクＡ及びタスクＤとの依存関係がある。そのため、タスクＥの最良実行順序は、タスクＤの直後となる。また、タスクＥは、静的タスクスケジューリング結果においても、同じタスクＤの直後である。その結果、優先度制御部１２１は、タスクＥの実行順序変動可能性がないと判断する。
【０１４３】
そこで、優先度制御部１２１は、タスクＥの優先度を先行するタスクＤの優先度より下げず、設定可能な最も高い優先度「３」を付与する（図１２）。
【０１４４】
次に、優先度制御部１２１は、タスクＥの次に実行されるタスクＦを優先度付与対象タスクとする。そして、優先度制御部１２１は、タスクＦの実行順序変動可能性を判断する。
【０１４５】
タスクＦは、タスクＤとの依存関係があるが、タスクＥとは依存関係がない。そのため、優先度に基づき、タスクＦは、タスクＥと入れ替わり、前に実行される可能性がある。つまり、タスクＦの最良実行順序は、タスクＤの直後である。この順序は、静的タスクスケジューリング結果の実行順序と異なる。そのため、優先度制御部１２１は、タスクＦを実行順序変動可能性があると判断する。
【０１４６】
そこで、優先度制御部１２１は、タスクＦの全ての先行実行タスクより低い優先度を、タスクＦに付与する。今の場合、タスクＦの先行実行タスクは、タスクＥである。そこで、優先度制御部１２１は、タスクＦの優先度を、タスクＥの優先度「３」より下げた「４」とする（図１３）。
【０１４７】
このように構成された第２の実施形態のタスクスケジューリング装置１０は、第１の実施形態の効果に加え、優先度が高いタスクを多く生成する効果を得ることができる。
【０１４８】
その理由は、第２の実施形態のタスクスケジューリング装置１０は、優先度を高く設定する静的タスクスケジューリング結果の最初に実行される先頭タスクから、優先度を定義（付与）していくためである。
【０１４９】
そのため、本実施形態のタスクスケジューリング装置１０は、優先度が低い領域での優先度の値をできるだけ確保したい場合に、特に、有効である。
【０１５０】
（第３の実施形態）
静的タスクスケジューリング結果の最終タスクから優先度を定義（付与）していく手法（第２の手法）を用いるタスクスケジューリング装置１０の、より詳細な実施形態について、第３の実施形態として、説明する。
【０１５１】
繰り返しの説明となるが、本実施形態のタスクスケジューリング装置１０が用いる手法は、静的タスクスケジューリング結果に基づく実行順序の最終タスクから優先度を定義する方法であり、次のような動作を含む。
【０１５２】
まず、タスクスケジューリング装置１０は、各タスクの優先度に基づいて実行順序が変わりえる箇所と、優先度に基づいて実行順序が変わらない箇所とを、分類する。タスクスケジューリング装置１０は、実行順序が変わりえる箇所について、後続するタスクの優先度に対し、先行のタスクの優先度を高く定義する。この動作に基づき、タスクスケジューリング装置１０は、実行順序を、維持する。
【０１５３】
一方、タスクスケジューリング装置１０は、実行順序が変わらない箇所について、先行のタスクの優先度を上げない。この動作に基づき、タスクスケジューリング装置１０は、必要な優先度の個数を、抑制する。
【０１５４】
なお、本実施形態のタスクスケジューリング装置１０の構成は、第２の実施形態と同じため、構成の説明を省略する。
【０１５５】
また、本実施形態のタスクスケジューリング装置１０は、図４に示すタスクスケジューリング装置６０と同様に、ＣＰＵ６１０と、ＲＯＭ６２０と、ＲＡＭ６３０とを含むコンピュータで実現されても良い。
【０１５６】
次に本実施形態の優先度生成部１２の動作について図面を参照して説明する。
【０１５７】
図１４は、本実施形態の優先度生成部１２の動作の一例を示すフローチャートである。
【０１５８】
優先度生成部１２は、図１４に示す処理を、スケジューリングの対象となる各コアに対し、実施する。なお、タスクスケジューリングで用いる最低優先度は、予め、タスクスケジューリング装置１０に、設定されていてもよい。
【０１５９】
まず、優先度制御部１２１は、タスクスケジューリングに用いる最低優先度を設定する（ステップＳ３０１）。優先度制御部１２１は、最低優先度として、任意の値を用いても良い。また、優先度制御部１２１は、既に説明したように、最低優先度が予め設定されていても良い。あるいは、優先度制御部１２１は、タスクスケジューリングで設定するタスクより重要な処理で必要とする優先度を取り除き、残った利用可能な優先度の中で最も低い優先度を、最低優先度としても良い。
【０１６０】
次に、優先度制御部１２１は、静的タスクスケジューリング結果の実行される順序の後ろから順にタスクを選択する。選択されたタスクは、「優先度付与対象タスク」である。優先度制御部１２１は、優先度付与対象タスクを、優先度付与対象タスク保持部１２２に、設定する（ステップＳ３０２）。
【０１６１】
続いて、優先度制御部１２１は、優先度付与対象タスクの実行順序の変動の可能性を、調べる（ステップＳ３０３）。
【０１６２】
より具体的に説明すると、次のようになる。
【０１６３】
優先度制御部１２１は、まず、後続タスクに更に従属するタスクを、検討対象から除外する。そして、優先度制御部１２１は、優先度付与対象タスクより他のタスクが優先して実行されると仮定した場合に、最も遅く実行の開始が可能となる順序である最悪実行順序を求める。そして、優先度制御部１２１は、最悪実行順序と、静的タスクスケジューリング結果の実行順序とを比較する。
【０１６４】
順序が異なる場合、優先度制御部１２１は、実行順序の変動が起こり得ると判断する。一方、実行順序が等しい場合、優先度制御部１２１は、実行順序の変動が起こり得ないと判断する。
【０１６５】
実行順序の変動が起こり得る場合（ステップＳ３０３でＹｅｓ）、優先度制御部１２１は、優先度付与対象タスクの全ての後続実行タスクより高い優先度を、優先度付与対象タスクに、付与する（ステップＳ３０４）。例えば、優先度が高いタスクに付与する優先度の値が小さく、優先度が低いタスクに付与する優先度の値が大きいとすると、優先度制御部１２１は、優先度の数値が小さい値を、優先度付与対象タスクに設定する。これは、優先度付与対象タスクの優先度を上げることになる。なお、優先度制御部１２１は、高い優先度として、優先度が一つ上がる（高くなる）値にすることが望ましい。このように設定すると、使用されない優先度が発生せず、使用する優先度の個数が少なくなるためである。優先度制御部１２１は、付与した優先度を優先度保持部１２３の優先度付与対象タスクの領域に保存する。この動作に基づき、優先度制御部１２１は、タスクの実行順序を、維持する。
【０１６６】
一方、実行順序の変動が起こり得ない場合（ステップＳ３０３  Ｎｏ）、優先度制御部１２１は、優先度付与対象タスクに付与する優先度を上げない（ステップＳ３０５）。例えば、優先度が高いタスクに付与する優先度の値が小さく、優先度が低いタスクに付与する優先度の値が大きいとすると、優先度制御部１２１は、優先度付与対象タスクに、先行するタスクの優先度の数値として同等又は高い値を付ける。なお、優先度制御部１２１は、優先度として、最低優先度の値を設定することが望ましい。ただし、優先度制御部１２１は、必要に応じて最低優先度以外で現在の優先度より低い優先度を付与しても良く、優先度を同等としても良い。優先度制御部１２１は、付与した優先度を優先度保持部１２３のうち優先度付与対象タスクの領域に保存する。この動作に基づき、優先度制御部１２１は、必要な優先度の個数を、削減する。
【０１６７】
優先度付与対象タスクに優先度を設定すると、優先度制御部１２１は、スケジューリングの対象のコアの全てのタスクについて、優先度付けが終了したか否かを判定する（ステップＳ３０６）。
【０１６８】
終了した場合（ステップＳ３０６でＹｅｓ）、優先度制御部１２１は、優先度の付与の処理を終了する。
【０１６９】
終了していない場合（ステップＳ３０６でＮｏ）、優先度制御部１２１は、ステップＳ３０２に戻り、静的タスクスケジューリング結果の次のタスク（１つ前のタスク）を優先度付与対象タスクに設定して、上記の処理を繰り返す。
【０１７０】
続いて、図７に示す静的タスクスケジューリング結果を用いて、優先度制御部１２１の動作についてさらに説明する。
【０１７１】
また、優先度は、数値が小さいタスクの優先度が高いとする。つまり、同時の複数のタスクが実行可能な場合、数値が小さいタスクが、実行される。なお、数値が小さいタスクの優先度が低いとする場合、数値の大小を入れ替えればよい。最低優先度は、「５」とする。（つまり、優先度の最大値は、「５」とする。）
図１５乃至図２０は、優先度制御部１２１が、設定する優先度を説明するための図である。図中の数値は、タスクに設定された優先度である。
【０１７２】
まず、優先度制御部１２１は、静的タスクスケジューリング結果の最終タスクであるタスクＦの優先度を定義（付与）する。（これは、優先度制御部１２１が、タスクＦを優先度付与対象タスクに設定することである。）タスクＦは、最終タスクである。そこで、優先度制御部１２１は、タスクＦに最低優先度（数値としては最大値）である「５」を定義する（図１５）。
【０１７３】
次に、優先度制御部１２１は、優先度付与対象タスクとして、タスクＦの前に実行されるタスクＥを設定する。そして、優先度制御部１２１は、タスクＥの実行順序変動可能性について判断する。より具体的に説明すると、優先度制御部１２１は、タスクＥがスケジューリングされている時刻より後に実行される可能性があるか否かを判断する。
【０１７４】
ここで、タスクＥとタスクＦは、タスクＤに依存している。そのため、タスクＦは、優先度に基づき、タスクＥと入れ替わり、前の実行位置で実行される可能性がある。つまり、タスクＥの最悪実行順序は、タスクＦの後である。これは、静的タスクスケジューリング結果の実行順序と異なる。そのため、優先度制御部１２１は、タスクＥの実行順序変動可能性があると判断する。なお、タスクＦは、タスクＥの後続実行タスクである。
【０１７５】
そこで、優先度制御部１２１は、タスクＥの優先度を、後続のタスクＦ（後続実行タスク）より上げる。今の場合、タスクＦの優先度は「５」である。そこで、優先度制御部１２１は、タスクＥの優先度を「４」とする（図１６）。
【０１７６】
次に、優先度制御部１２１は、タスクＥの前に実行されるタスクＤを優先度付与対象タスクとする。そして、優先度制御部１２１は、タスクＤの実行順序変動可能性を判断する。
【０１７７】
タスクＤは、後続するタスクＥ及びタスクＦと依存関係がある。そのため、優先度に関わらず、タスクＥ及びタスクＦは、タスクＤの前に実行されることはない。つまり、タスクＤの最悪実行順序は、静的タスクスケジューリング結果の実行順序と同じである。従って、優先度制御部１２１は、タスクＤの実行順序変動可能性がないと判断する。
【０１７８】
実行順序変動可能性がないため、優先度制御部１２１は、タスクＤの優先度を上げる処理を行わず、タスクＤに最も低い優先度（最低優先度「５」）を付与する（図１７）。
【０１７９】
次に、優先度制御部１２１は、タスクＤの前に実行されるタスクＣを優先度付与対象タスクとする。そして、優先度制御部１２１は、タスクＣの実行順序変動可能性を判断する。
【０１８０】
なお、優先度制御部１２１は、タスクＤに従属するタスクＥ及びタスクＦを検討対象から除外する。除外する理由は、次のとおりである。優先度制御部１２１が、タスクＣをタスクＤより前に実行されるように優先度を設定すれば、タスクＥ及びタスクＦは、タスクＣより前に実行されることがないためである。
【０１８１】
タスクＣ及びタスクＤの依存関係は、同様で、タスクＡとの依存関係である。そのため、タスクＤは、優先度に基づいて、タスクＣより前に実行される可能性がある。つまり、タスクＣの最悪実行順序は、タスクＤの後（タスクＥの直前）となる。最悪実行順序は、静的タスクスケジューリング結果の実行順序と異なる。そのため、優先度制御部１２１は、タスクＣの実行順序変動可能性があると判断する。
【０１８２】
そこで、優先度制御部１２１は、タスクＣの優先度を後続実行タスクより上げる処理を行う。より具体的には、優先度制御部１２１は、タスクＣの全ての後続実行タスクの優先度より上げる。今の場合、対象となる後続実行タスクは、タスクＤである。そのため、優先度制御部１２１は、タスクＣの優先度を、タスクＤの優先度「５」より高い優先度「４」とする（図１８）。
【０１８３】
次に、優先度制御部１２１は、タスクＣの前に実行されるタスクＢを優先度付与対象タスクとする。そして、優先度制御部１２１は、タスクＢの実行順序変動可能性を判断する。
【０１８４】
ただし、タスクＤに従属するタスクＥ、タスクＦは、タスクＢがタスクＤより前に実行されるよう優先度付けされればタスクＢより前に実行されることはない。そのため、優先度制御部１２１は、タスクＥ及びタスクＦを、順序変動の検討対象から除外する。
【０１８５】
タスクＣ及びタスクＤは、共に、タスクＡからの依存が存在し、他の依存関係がない。つまり、タスクＣ及びタスクＤは、タスクＢとの依存関係がない。そのため、タスクＣ及びタスクＤは、優先度に基づき、タスクＢと入れ替わり、前に実行される可能性がある。つまり、タスクＢの最悪実行順序は、タスクＤの後（検討対象から削除したタスクＥの直前）である。最悪実行順序は、静的タスクスケジューリング結果の実行順序と異なる。そのため、優先度制御部１２１は、タスクＢの実行順序変動可能性があると判断する。
【０１８６】
そこで、優先度制御部１２１は、タスクＢの優先度を、タスクＢの全ての後続実行タスクの優先度より上げる。今の場合、対象となる後続実行タスクは、タスクＣ及びタスクＤである。そのため、優先度制御部１２１は、タスクＢの優先度を、タスクＣの優先度「４」より高い優先度「３」とする（図１９）。
【０１８７】
次に、優先度制御部１２１は、タスクＢの前に実行されるタスクＡを優先度付与対象タスクとする。そして、優先度制御部１２１は、タスクＡの実行順序変動可能性を判断する。まず、優先度制御部１２１は、タスクＥ及びタスクＦを検討対象から除外する。また、タスクＣ及びタスクＤは、タスクＡと依存関係があるため、タスクＡより前に実行されることはない。さらに、タスクＢは、コア１との依存関係に基づき、タスクＡより前に実行されることはない。つまり、タスクＡより前に実行されるタスクはない。つまり、タスクＡの最悪実行順序は、静的タスクスケジューリング結果の実行順序と同じである。
【０１８８】
そこで、優先度制御部１２１は、タスクＡの実行変動可能性がないと判断する。その結果、優先度制御部１２１は、タスクＡに最低優先度「５」を付与する（図２０）。
【０１８９】
このように構成された第３の実施形態のタスクスケジューリング装置１０は、第１の実施形態の効果に加え、優先度が低いタスクを多く生成する効果を得ることができる。
【０１９０】
その理由は、第３の実施形態のタスクスケジューリング装置１０は、優先度を低く設定する静的タスクスケジューリング結果の最後に実行される最終タスクから、優先度を定義（付与）していくためである。
【０１９１】
そのため、本実施形態のタスクスケジューリング装置１０は、優先度が高い領域での優先度の値をできるだけ確保したい場合に、特に、有効である。
【０１９２】
（第４の実施形態）
次に、第４の実施形態について図面を参照して説明する。
【０１９３】
まず、以下の説明において、実行順序の変動が外部へ影響するタスクを、「順序変動禁止タスク」と呼ぶ。順序変動禁止タスクとして、例えば、Ｉ／Ｏアクセスを行うタスク、又は、他のコア上のタスクとの通信の依存関係があるタスクが、考えられる。一方、実行順序の変動が外部に影響しないタスクとして、例えば、コアでの演算処理に限られたタスク、又は、依存関係が同一コア内のタスクに限れられたタスクが、考えられる。
【０１９４】
第４の実施形態のタスクスケジューリング装置１０は、順序変動禁止タスクの実行順序が変動しない範囲で、実行順序の変動が外部に影響しないタスク群について、同じ優先度を用いる。このような優先度の付与に基づき、本実施形態のタスクスケジューリング装置１０は、必要な優先度の個数を、第１乃至第３の実施形態より、さらに、削減する。
【０１９５】
本実施形態のタスクスケジューリング装置１０は、静的タスクスケジューリング結果の先頭タスクから優先度を定義（付与）する手法（第１の手法）と、最終タスクから定義（付与）する手法（第２の手法）との、どちらも、用いることができる。以下の説明では、一例として、先頭タスクから優先度を定義する手法を用いて、説明する。
【０１９６】
本実施形態の構成は、第１の実施形態乃至第３の実施形態と同様のため、構成の説明を省略する。
【０１９７】
なお、本実施形態のタスクスケジューリング装置１０は、図４に示すタスクスケジューリング装置６０と同様に、ＣＰＵ６１０と、ＲＯＭ６２０と、ＲＡＭ６３０とを含むコンピュータで、実現されても良い。
【０１９８】
図２１は、本実施形態の優先度生成部１２の動作の一例を示すフローチャートである。なお、優先度生成部１２は、各コアについて、以下で説明する処理を、実施する。また、最高優先度についても、第２の実施形態と同様に、予め、最高優先度が設定されていても良い。
【０１９９】
まず、優先度制御部１２１は、タスクスケジューリングで用いる最高優先度を、設定する（ステップＳ４０１）。ここで、優先度制御部１２１は、最高優先度として、任意の値を用いても良い。また、優先度制御部１２１は、既に説明したように、最高優先度が、予め、設定されても良い。あるいは、優先度制御部１２１は、タスクスケジューリングで設定するタスクより重要な処理で必要とする優先度を取り除き、残った利用可能な優先度の中で最も高い優先度を、最高優先度としても良い。なお、静的タスクスケジューリング結果の最終タスクから優先度を設定する場合、優先度制御部１２１は、最低優先度を設定する。
【０２００】
次に、優先度制御部１２１は、優先度付与対象タスクを、選択する。そして、優先度制御部１２１は、選択した優先度付与対象タスクを、優先度付与対象タスク保持部１２２に、設定（保持）する（ステップＳ４０２）。
【０２０１】
次に、優先度制御部１２１は、優先度付与対象タスクの実行順序変動可能性を、調べる（ステップＳ４０３）。より具体的には、優先度制御部１２１は、次のように動作する。
【０２０２】
優先度制御部１２１は、優先度付与対象タスクの最良実行順序を求める。そして、優先度制御部１２１は、求めた最良実行順序と、静的タスクスケジューリング結果の実行順序とを比較する。順序が異なる場合、優先度制御部１２１は、実行順序の変動が起こり得ると判断する。実行順序が等しい場合、優先度制御部１２１は、実行順序の変動が起こり得ないと判断する。
【０２０３】
実行順序の変動が起こり得ない場合（ステップＳ４０３でＮｏ）、優先度制御部１２１は、優先度を下げない処理を用いて、必要な優先度の個数を、削減する（ステップＳ４０７）。具体的には、優先度制御部１２１は、次のような動作を実行する。
【０２０４】
優先度制御部１２１は、優先度の数値として先行するタスクの優先度と同等又は高い優先度を選択し、優先度保持部１２３の優先度付与対象タスクの領域に保存する。
【０２０５】
なお、優先度制御部１２１は、最高優先度の値を設定することが望ましい。ただし、優先度制御部１２１は、必要に応じて、最高優先度以外で先行するタスクの優先度より高い優先度に上げる、又は、優先度を先行するタスクの優先度と同等としてもよい。優先度を設定後、優先度制御部１２１は、ステップＳ４０８へと進む。
【０２０６】
一方、実行順序の変動が起こり得る場合（ステップＳ４０３  Ｙｅｓ）、優先度制御部１２１は、優先度付与対象タスクの実行順序の変動に基づき、外部への影響があるか否か判定する（ステップＳ４０４）。
【０２０７】
ここで、優先度付与対象タスクが順序変動禁止タスクならば、当然、実行順序の変更は、外部へ影響する。しかし、ステップＳ４０４で優先度制御部１２１が判断する外部への影響の有無は、優先度付与対象タスクが順序変動禁止タスクの場合に限られない。そのため、優先度付与対象タスクが順序変動禁止タスクの場合に限らず、優先度制御部１２１は、実行順序の変更に基づく外部への影響を判定する。
【０２０８】
例えば、優先度付与対象タスクが順序変動禁止タスク以外であっても、順序変動禁止タスクが、優先度付与対象タスクの先行実行タスクに、含まれる場合がある。その場合、順序変動禁止タスクの実行順序は、優先度付与対象タスクの実行順序に基づき、変更となる可能性がある。つまり、外部への影響が、順序変動禁止タスクでない優先度付与対象タスクの実行順序に基づいて、発生する場合がある。そこで、先行実行タスクの一部が、順序変動禁止タスクの場合、優先度制御部１２１は、順序変動禁止タスクに影響を与えない範囲で、外部への影響がない場合の処理を、優先度付与対象タスクに、適用する。
【０２０９】
外部への影響がある場合（ステップＳ４０４でＹｅｓ）、優先度制御部１２１は、優先度付与対象タスクの全ての先行実行タスクより低い優先度を、優先度付与対象タスクに、付与する（ステップＳ４０５）。
【０２１０】
例えば、優先度が低いと大きな数値を付与する場合、優先度制御部１２１は、優先度付与対象タスクの優先度の数値に大きな値を付与する。そして、優先度制御部１２１は、選択した優先度を、優先度保持部１２３の優先度付与対象タスクの領域に保存する。なお、優先度制御部１２１は、優先度が一つ下がる値を選択することが望ましい。その後、優先度制御部１２１は、ステップＳ４０８に進む。
【０２１１】
外部への影響がない場合（ステップＳ４０４でＮｏ）、優先度制御部１２１は、優先度付与対象タスクに、次の条件を満足する優先度を付与する。
【０２１２】
条件１：優先度付与対象タスクが最良実行順序で実行された場合の実行開始時刻以降で、全ての、優先度付与対象タスクの静的タスクスケジューリング結果の実行順序での実行開始時刻までに先行して実行する全ての順序変動禁止タスク（以下、「先行実行の順序変動禁止タスク」と言う）の優先度より低い優先度。
【０２１３】
条件２：優先度付与対象タスクの最良実行順序で実行された場合の実行開始時刻以降で、優先度付与対象タスクの静的タスクスケジューリング結果の実行順序での実行開始時刻までに先行して実行する順序変動禁止タスクでないタスク（以下、「先行実行の順序変動可能タスク」と言う）と同等の優先度。
【０２１４】
例えば、優先度が低い場合に大きな数値を付与とする。そして、先行実行の順序変動禁止タスクの優先度が「３」の場合、優先度制御部１２１は、優先度として、例えば、「４」を付与する。そして、優先度制御部１２１は、選択した優先度を、優先度保持部１２３の優先度付与対象タスクの領域に保存する。なお、優先度制御部１２１は、条件２の先行実行の順序変動可能タスクと同じ優先度として、最も高い優先度を選択することが望ましい。その後、優先度制御部１２１は、ステップＳ４０８に進む。
【０２１５】
ステップＳ４０５乃至Ｓ４０７の後、優先度制御部１２１は、対象となっているコアの全てのタスクについて優先度付けが終了したか否かを判定する（ステップＳ４０８）。
【０２１６】
全てのタスクについて優先度付けが終了した場合（ステップＳ４０８  Ｙｅｓ）、優先度制御部１２１は、処理を終了する。
【０２１７】
優先度付けしてないタスクがある場合（ステップＳ４０８  Ｎｏ）、優先度制御部１２１は、ステップＳ４０２へと戻り、次のタスクを優先度付与対象タスクに設定し、これまで説明した処理を繰り返す。
【０２１８】
次に、静的タスクスケジューリング結果の一例を参照して、本実施形態の動作について説明する。
【０２１９】
図２２は、説明に用いる静的タスクスケジューリング結果の一例を示す図である。
【０２２０】
図２２は、コア０とコア１との２つのコアを示している。優先度制御部１２１は、コア０のタスクに優先度を付与するとする。コア０上には、図２２に示すようにタスクＧからタスクＮまでの８つのタスクが配置されている。図２２において、コア１のタスクの表示を、省略した。また、図２２において、各タスク間の依存関係が、破線の矢印で示されている。この依存関係は、矢印の根元のタスクが完了後、矢印の先のタスクの実行が可能となる関係である。
【０２２１】
タスクＧは、先頭タスクである。タスクＨは、タスクＧの終了後、実行可能なタスクである。タスクＩは、タスクＧの終了後、実行可能なタスクである。タスクＪは、タスクＧの終了後、実行可能なタスクである。タスクＫは、タスクＨの終了後、実行可能なタスクである。タスクＬは、タスクＩの終了後、実行可能なタスクである。タスクＭは、タスクＪの終了後、実行可能なタスクである。タスクＮは、最終タスクであり、タスクＬ及びタスクＭの終了後、実行可能なタスクである。また、タスクＪ、タスクＫ及びタスクＮは、順序変動禁止タスクとする。そのため、タスクＪ、タスクＫ、タスクＮは、依存関係の先がコア１となっている矢印を付した。タスクＪ、タスクＫ及びタスクＮ以外のタスクは、順序変動禁止タスクではなく、順序変動禁止タスクへの影響がない範囲で実行順序の変動が許可される。
【０２２２】
また、優先度は、数値が小さいタスクの優先度が高いとする。つまり、同時の複数のタスクが実行可能な場合、優先度の数値が小さいタスクが、実行される。なお、数値が小さいタスクの優先度が低いとする場合、数値の大小を入れ替えればよい。また、最高優先度は、「１」とする。（つまり、優先度の最小値は、「１」とする。）
本実施形態の説明の参考として、第２の実施形態のタスクスケジューリング装置１０が図２２に示す静的タスクスケジューリング結果を付与する優先度を示しておく。
【０２２３】
図２３は、第２の実施形態のタスクスケジューリング装置１０が付与する優先度を示す図である。第２の実施形態のタスクスケジューリング装置１０は、優先度として、「１」から「６」と、タスクの数の８より少ない６個の優先度を使用する。
【０２２４】
続いて、図２２に示す静的タスクスケジューリング結果を用いて、本実施形態のタスクスケジューリング装置１０の動作について図面を参照して説明する。
【０２２５】
図２４乃至図３０は、本実施形態の優先度制御部１２１が、設定する優先度を説明するための図である。図中の数値は、タスクに定義（設定、又は、付与）された優先度である。
【０２２６】
まず、優先度制御部１２１は、コア０で最初に実行されるタスクＧを優先度付与対象タスクと設定する。そして、優先度制御部１２１は、タスクＧの優先度を定義する。優先度制御部１２１は、タスクＧの優先度として最高優先度（優先度の最小値）の「１」を設定する。
【０２２７】
次に、優先度制御部１２１は、優先度付与対象タスクを、タスクＧの次に実行されるタスクＨとする。そして、優先度制御部１２１は、優先度付与対象タスク（タスクＨ）の実行順序変動可能性について判断する。具体的には、優先度制御部１２１は、タスクＨが静的タスクスケジューリング結果の実行順序の時刻より前に実行される可能性があるか否かを判断する。
【０２２８】
タスクＨは、タスクＧとの依存関係に基づき、静的タスクスケジューリング結果の実行位置（実行順序）より前に実行されることはない。つまり、タスクＨの最良実行順序は、図２２に示された静的タスクスケジューリング結果の実行順序と同じタスクＧの直後である。このため、優先度制御部１２１は、タスクＨを実行順序変動可能性なしと判断する。
【０２２９】
判断後、優先度制御部１２１は、タスクＨに優先度を付与する。既に説明したとおり、タスクＨは、優先度に関わらず、静的タスクスケジューリング結果の実行順序の時刻より前に実行される可能性がない。そのため、優先度制御部１２１は、タスクＨの優先度を、先行するタスク（タスクＧ）より下げる処置は行わず、タスクＧと同じ優先度（今の場合「１」）とする（図２４）。
【０２３０】
次に、優先度制御部１２１は、優先度付与対象タスクを、タスクＨの次に実行されるタスクＩとする。そして、優先度制御部１２１は、優先度付与対象タスク（タスクＩ）の実行順序変動可能性について判断する。具体的には、優先度制御部１２１は、タスクＩが静的タスクスケジューリング結果の実行順序の時刻より前に実行される可能性があるか否かを判断する。
【０２３１】
タスクＩは、タスクＧとの依存関係が存在するが、先行するタスクＨとの依存関係はない。そのため、タスクＩは、優先度に基づき、タスクＨと入れ替わり、静的タスクスケジューリング結果の実行順序より前に実行される可能性がある。つまり、タスクＩの最良実行順序は、静的タスクスケジューリング結果の実行順序と異なり、タスクＧの直後である。このため、優先度制御部１２１は、タスクＩを実行順序変動可能性ありと判断する。
【０２３２】
判断後、優先度制御部１２１は、タスクＩに優先度を付与する。優先度制御部１２１は、タスクＩを、実行順序変動可能性ありの判断している。しかし、タスクＩは、順序変動禁止タスクではない。すなわち、優先度制御部１２１は、外部への影響を与えない範囲で、タスクＩの実行順序の変動が許可される。
【０２３３】
今回の例において、タスクＩに対応する先行実行の順序変動禁止タスクは、ない。
【０２３４】
タスクＩの実行順序の変動可能範囲は、最良実行順序以降である。また、繰り返しになるが、タスクＩの最良実行順序は、タスクＧの直後である。そのため、タスクＩに対応する先行実行の順序変動可能タスクは、タスクＨである。そのため、優先度制御部１２１は、タスクＩの優先度をタスクＨより下げる処置を行わない。つまり、優先度制御部１２１は、タスクＩの優先度として、タスクＩの先行実行の順序変動可能タスク（今の場合、タスクＨ）の優先度と同じ優先度（今の場合「１」）と定義する（図２５）。
【０２３５】
次に、優先度制御部１２１は、優先度付与対象タスクを、タスクＩの次に実行されるタスクＪとする。そして、優先度制御部１２１は、優先度付与対象タスク（タスクＪ）の実行順序変動可能性について判断する。具体的には、優先度制御部１２１は、タスクＪが静的タスクスケジューリング結果の実行順序の時刻より前に実行される可能性があるか否かを判断する。
【０２３６】
タスクＪは、タスクＧからの依存関係が存在するが、その他の先行するタスクとの依存関係はない。そのため、タスクＪは、優先度に基づき、タスクＨ及びタスクＩと入れ替わり、静的タスクスケジューリング結果の実行順序より前に実行される可能性がある。つまり、タスクＪの最良実行順序は、静的タスクスケジューリング結果の実行順序と異なり、タスクＧの直後である。このため、優先度制御部１２１は、タスクＪを実行順序変動可能性ありと判断する。
【０２３７】
判断後、優先度制御部１２１は、タスクＪに優先度を付与する。優先度制御部１２１は、タスクＪを、実行順序変動可能性ありと判断している。また、タスクＪは、順序変動禁止タスクである。従って、優先度制御部１２１は、タスクＪの優先度を下げる処置を行う。タスクＪの最良実行順序は、タスクＧの直後である。従って、優先度制御部１２１は、タスクＪの優先度として、全ての先行実行タスク（タスクＨ、タスクＩ）の優先度の中で最も低い優先度（今の場合「１」）より低い優先度（例えば「２」）を定義する（図２６）。
【０２３８】
次に、優先度制御部１２１は、優先度付与対象タスクを、タスクＪの次に実行されるタスクＫとする。そして、優先度制御部１２１は、優先度付与対象タスク（タスクＫ）の実行順序変動可能性について判断する。具体的には、優先度制御部１２１は、タスクＫが静的タスクスケジューリング結果の実行順序の時刻より前に実行される可能性があるか否かを判断する。
【０２３９】
タスクＫは、タスクＨとの依存関係が存在するが、タスクＩ及びタスクＪとの依存関係がない。そのため、タスクＫは、優先度に基づき、タスクＩ及びタスクＪと入れ替わり、静的タスクスケジューリング結果の実行順序より前に実行される可能性がある。つまり、タスクＫの最良実行順序は、静的タスクスケジューリング結果の実行順序と異なり、タスクＨの直後である。このため、優先度制御部１２１は、タスクＫを実行順序変動可能性ありと判断する。
【０２４０】
判定後、優先度制御部１２１は、タスクＫに優先度を付与する。優先度制御部１２１は、タスクＫを、実行順序変動可能性ありと判断している。また、タスクＫは、順序変動禁止タスクである。従って、優先度制御部１２１は、タスクＫの優先度を下げる処置を行う。タスクＫの最良実行順序は、タスクＨの直後である。従って、優先度制御部１２１は、タスクＫの優先度として、全ての先行実行タスク（タスクＩ、タスクＪ）の優先度の中で最も低い優先度（今の場合「２」）より低い優先度（例えば、「３」）を定義する（図２７）。
【０２４１】
次に、優先度制御部１２１は、優先度付与対象タスクを、タスクＫの次に実行されるタスクＬとする。そして、優先度制御部１２１は、優先度付与対象タスク（タスクＬ）の実行順序変動可能性について判断する。具体的には、優先度制御部１２１は、タスクＬが静的タスクスケジューリング結果の実行順序の時刻より前に実行される可能性があるか否かを判断する。
【０２４２】
タスクＬは、タスクＩとの依存関係が存在するが、タスクＪ及びタスクＫとの依存関係がない。そのため、タスクＬは、優先度に基づき、タスクＪ及びタスクＫと入れ替わり、静的タスクスケジューリング結果の実行順序より前に実行される可能性がある。つまり、タスクＬの最良実行順序は、静的タスクスケジューリング結果の実行順序と異なり、タスクＩの直後である。このため、優先度制御部１２１は、タスクＬを実行順序変動可能性ありと判断する。
【０２４３】
判断後、優先度制御部１２１は、タスクＬに優先度を付与する。優先度制御部１２１は、タスクＬを実行順序変動可能性ありの判断している。また、タスクＬは、順序変動禁止タスクではない。すなわち、優先度制御部１２１は、外部への影響を与えない範囲で、タスクＬの実行順序の変動が許可されている。
【０２４４】
ただし、今回の場合、タスクＬの先行実行タスク（タスクＪ及びタスクＫ）は、全て順序変動禁止タスクである。従って、タスクＬは、先行実行タスク（タスクＪ及びタスクＫ）と入れ替わることができない。そのため、優先度制御部１２１は、タスクＬの優先度として、全ての先行実行タスク（タスクＪ、タスクＫ）の優先度の中で最も低い優先度（今の場合「３」）より低い優先度（例えば、「４」）を定義する（図２８）。
【０２４５】
次に、優先度制御部１２１は、優先度付与対象タスクを、タスクＬの次に実行されるタスクＭとする。そして、優先度制御部１２１は、優先度付与対象タスク（タスクＭ）の実行順序変動可能性について判断する。具体的には、優先度制御部１２１は、タスクＭの静的タスクスケジューリング結果の実行順序の時刻より前に実行される可能性があるか否かを判断する。
【０２４６】
タスクＭは、タスクＪとの依存関係が存在するが、タスクＫ及びタスクＬとの依存関係がない。そのため、タスクＭは、優先度に基づき、タスクＫ及びタスクＬと入れ替わり、静的タスクスケジューリング結果の実行順序より前に実行される可能性がある。つまり、タスクＭの最良実行順序は、静的タスクスケジューリング結果の実行順序と異なり、タスクＪの直後である。このため、優先度制御部１２１は、タスクＭを実行順序変動可能性ありと判断する。
【０２４７】
判断後、優先度制御部１２１は、タスクＭに優先度を付与する。優先度制御部１２１は、タスクＭを実行順序変動可能性ありの判断している。また、タスクＭは、順序変動禁止タスクではない。すなわち、優先度制御部１２１は、外部への影響を与えない範囲で、タスクＭの実行順序の変動が許可される。
【０２４８】
ただし、タスクＭの先行実行タスク（タスクＫ、タスクＬ）の中で、タスクＫは、順序変動禁止タスクである。つまり、タスクＭは、タスクＫと入れ替わることができない。そのため、優先度制御部１２１は、タスクＭの優先度として、先行実行の順序変動禁止タスク（タスクＫ）の優先度より下げた優先度で、先行実行の順序変動可能タスク（タスクＬ）の優先度（今の場合「４」）と同等の優先度（「４」）を定義する（図２９）。
【０２４９】
次に、優先度制御部１２１は、優先度付与対象タスクを、タスクＭの次に実行されるタスクＮとする。そして、優先度制御部１２１は、優先度付与対象タスク（タスクＮ）の実行順序変動可能性について判断する。具体的には、優先度制御部１２１は、タスクＮの静的タスクスケジューリング結果の実行順序の時刻より前に実行される可能性があるか否かを判断する。
【０２５０】
タスクＮは、タスクＬ及びタスクＭとの依存関係が存在する。また、タスクＬ及びタスクＭは、順序変動禁止タスクではない。つまり、タスクＬ及びタスクＭは、実行順序が入れ替わる可能性がある。しかし、タスクＮは、タスクＬ及びタスクＭのどちらとも依存関係が存在する。従って、タスクＬ及びタスクＭの実行順序に関わらず、タスクＮは、２つのタスクの実行後に実行される。つまり、タスクＮの最良実行順序は、静的タスクスケジューリング結果の実行順序と同じ（タスクＭの直後）である。そのため、優先度制御部１２１は、タスクＮを実行順序変動可能性なしと判断する。
【０２５１】
判断後、優先度制御部１２１は、タスクＮに優先度を付与する。優先度制御部１２１は、タスクＮを、実行順序変動可能性なしと判断している。そのため、優先度制御部１２１は、タスクＮの優先度として、先行するタスクより下げる処置は行わず、設定可能な優先度の中で最も高い優先度（今の場合「１」）を定義する（図３０）。
【０２５２】
本実施形態の優先度付与結果である図３０と、第２の実施形態の優先度付与結果である図２３を比較すると、本実施形態のタスクスケジューリング装置１０は、優先度として、第２の実施形態の６個より少ない４個を使用している。
【０２５３】
このように、本実施形態の係るタスクスケジューリング装置１０は、使用する優先度の数を、第１乃至第３の実施形態のタスクスケジューリング装置１０より削減する効果を得ることができる。
【０２５４】
その理由は、本実施形態のタスクスケジューリング装置１０は、タスクの実行順序の変動が外部に影響しないタスクについて、同じ優先度を用いるためである。
【０２５５】
（第５の実施形態）
第５の実施形態について図面を参照して説明する。
【０２５６】
図３１は、本実施形態に係るタスクスケジューリング装置１０Ａの構成の一例を示すブロック図である。図３１において、図２と同様の構成には同様の番号を付し、その詳細な説明を省略する。
【０２５７】
タスクスケジューリング装置１０Ａは、図２に示すタスクスケジューリング装置１０が含む静的タスクスケジューリング生成部１１と、優先度生成部１２とに加え、装置制御部１３を含む。
【０２５８】
装置制御部１３は、静的タスクスケジューリング生成部１１と優先度生成部１２との動作を制御する。より具体的には、装置制御部１３は、静的タスクスケジューリング生成部１１に、タスクの静的タスクスケジューリングを実行させる。そして、装置制御部１３は、優先度生成部１２に、静的タスクスケジューリングしたタスクに優先度を付与させる。装置制御部１３は、この動作を全てにタスクが終了するまで繰り返す。
【０２５９】
このような制御に基づき、装置制御部１３は、静的タスクスケジューリング生成部１１と優先度生成部１２とを密に連携させ、最良実行順序の検出を容易にする。
【０２６０】
なお、本実施形態のタスクスケジューリング装置１０Ａは、図４に示すタスクスケジューリング装置６０と同様に、ＣＰＵ６１０と、ＲＯＭ６２０と、ＲＡＭ６３０とを含むコンピュータで実現されても良い。
【０２６１】
本実施形態のタスクスケジューリング装置１０Ａの動作について図面を参照して説明する。
【０２６２】
図３２は、本実施形態のタスクスケジューリング装置１０Ａの動作の一例を示すフローチャートである。
【０２６３】
まず、装置制御部１３は、静的タスクスケジューリング生成部１１に、処理対象のタスクについての静的タスクスケジューリングを指示する。静的タスクスケジューリング生成部１１は、指定されたタスクのコア配置と、タスクのコア上での実行順序とを決定する静的タスクスケジューリングを実行する（ステップＳ５０１）。なお、静的タスクスケジューリングに用いる手法は、既に説明した実施形態の手法を用いれば良い。また、静的タスクスケジューリングを行ったタスクは、次に優先度生成部１２で処理されるため、優先度付与対象タスクとなる。
【０２６４】
静的タスクスケジューリング生成部１１の処理が終了すると、装置制御部１３は、静的タスクスケジューリングが終了したタスクの優先度付与を、優先度生成部１２に指示する。指示を受けた優先度生成部１２は、静的タスクスケジューリングが終了した優先度付与対象タスクに優先度を付与する（ステップＳ５０２）。優先度生成部１２が優先度付与に用いる手法は、既に説明した実施形態の手法を用いれば良い。なお、後ほど説明するが、優先度生成部１２が優先度を付与する際、タスクスケジューリング装置１０Ａは、優先度付与対象タスクが最良実行順序（又は最悪実行順序）で静的タスクスケジューリングされているか否かを容易に判定できる。
【０２６５】
優先度付与後、装置制御部１３は、全てのタスクの処理が終了したか否かを判定する（ステップＳ５０３）。
【０２６６】
処理してないタスクがある場合（ステップＳ５０３  Ｎｏ）、装置制御部１３は、ステップＳ５０１に戻り、次のタスクについて処理を繰り返す。
【０２６７】
終了した場合（ステップＳ５０３  Ｙｅｓ）、装置制御部１３は、処理を終了する。
【０２６８】
次に、図７に示した静的タスクスケジューリング結果と同様のタスクＡ乃至タスクＦを用いて、本実施形態のタスクスケジューリング装置１０Ａの動作について、さらに説明する。
【０２６９】
なお、静的タスクスケジューリングは、複数コアを統合して処理できる。本実施形態のタスクスケジューリング装置１０Ａは、静的タスクスケジューリングと優先度生成とを、複数コアを統合して処理しても良い。ただし、複数コアを統合した処理の場合、説明が煩雑となる。そのため、以下では、説明の明確にするため、コア０の動作として説明する。
【０２７０】
また、優先度は、数値が小さいタスクの優先度が高いとする。つまり、同時に複数のタスクが実行可能であった場合、優先度として付与された数値が小さいタスクが、優先して実行されるとする。なお、数値が小さいタスクの優先度が低いとする場合、数字の大小の判定を入れ替えれば良い。
【０２７１】
また、以下の説明では、タスクが実行される順に優先度を設定するとし、最高優先度（優先度の数値の最小値）を「３」とする。
【０２７２】
図３３乃至図３８は、本実施形態のタスクスケジューリング装置１０Ａが、設定する優先度を説明するための図である。図中の数値は、タスクに定義（設定、付与）された優先度である。
【０２７３】
まず、装置制御部１３は、静的タスクスケジューリング生成部１１に最初のタスクの静的タスクスケジューリングを指示する。今の場合、静的タスクスケジューリング生成部１１は、コア０上で最初にタスクＡを実行することが、性能向上に良いと判断したとする。そのため、静的タスクスケジューリング生成部１１は、タスクＡの静的タスクスケジューリングを行う。なお、優先度付与対象タスクは、タスクＡとなる。
【０２７４】
また、静的タスクスケジューリングのときに、タスクＡの後に実行可能であるタスクが、明らかになる。今の場合、実行可能となるタスクは、コア１からの依存が解消するタスクＢ、並びに、タスクＡとの依存が解消するタスクＣ及びタスクＤである。つまり、タスクスケジューリング装置１０Ａは、タスクＢ、タスクＣ及びタスクＤの最良実行順序がタスクＡの直後であることを知ることができる。以下、依存が解消され、配置が可能となったタスクを「配置可能タスク」と言う。
【０２７５】
その後、装置制御部１３は、優先度生成部１２に、タスクＡの優先度の定義を指示する。タスクＡは、先頭タスクである。そのため、優先度生成部１２は、タスクＡの優先度として、最高優先度（優先度の最小値）である「３」を設定（付与）する（図３３）。
【０２７６】
装置制御部１３は、まだタスクが残っているため、次のタスクを処理する。
【０２７７】
装置制御部１３は、静的タスクスケジューリング生成部１１に、次のタスクの静的タスクスケジューリングを指示する。ここで、静的タスクスケジューリング生成部１１は、コア０上で次にタスクＢを実行することが、性能向上に良いと判断したとする。そのため、静的タスクスケジューリング生成部１１は、タスクＢの静的タスクスケジューリングを行う。なお、優先度付与対象タスクは、タスクＢとなる。
【０２７８】
静的タスクスケジューリングの後、装置制御部１３は、優先度生成部１２に優先度付与対象タスク（タスクＢ）の優先度の定義（付与）を指示する。
【０２７９】
タスクＡの静的タスクスケジューリング時に明らかなように、タスクＢの最良実行順序は、タスクＡの直後である。この実行順序は、上記の静的タスクスケジューリング結果の実行順序と同じである。このため、優先度生成部１２は、タスクＢを実行順序変動可能性なしと判断する。そして、優先度生成部１２は、タスクＢの優先度を、先行するタスクＡより下げる処置は行わず、最高優先度（今の場合「３」）とする（図３４）。なお、今回の場合、先行するタスクＡの優先度が最高優先度のため、タスクＢの優先度は、タスクＡの優先度と同じである。
【０２８０】
装置制御部１３は、まだタスクが残っているため、次のタスクを処理する。
【０２８１】
装置制御部１３は、静的タスクスケジューリング生成部１１に、次のタスクの静的タスクスケジューリングを指示する。ここで、静的タスクスケジューリング生成部１１は、コア０上で次にタスクＣを実行することが、性能向上に良いと判断したとする。そのため、静的タスクスケジューリング生成部１１は、タスクＣの静的タスクスケジューリングを行う。なお、優先度付与対象タスクは、タスクＣとなる。
【０２８２】
静的タスクスケジューリングの後、装置制御部１３は、優先度生成部１２に優先度付与対象タスク（タスクＣ）の優先度の定義（付与）を指示する。
【０２８３】
タスクＡの静的タスクスケジューリング時に明らかなように、タスクＣの最良実行順序は、タスクＡの直後である。タスクＣは、優先度に基づき、タスクＢと入れ替わる可能性がある。つまり、タスクＣの最良実行順序は、静的タスクスケジューリング結果の実行順序と異なる。このため、優先度生成部１２は、タスクＣを実行順序変動可能性ありと判断する。そして、優先度生成部１２は、タスクＣの優先度を、先行実行タスク（タスクＢ）の優先度（「３」）より低い優先度（例えば「４」）とする（図３５）。
【０２８４】
装置制御部１３は、まだタスクが残っているため、次のタスクを処理する。
【０２８５】
装置制御部１３は、静的タスクスケジューリング生成部１１に、次のタスクの静的タスクスケジューリングを指示する。ここで、静的タスクスケジューリング生成部１１は、コア０上で次にタスクＤを実行することが、性能向上に良いと判断したとする。（なお、この時点での配置可能タスクに残っているタスクは、タスクＤである（図３５を参照）。）そのため、静的タスクスケジューリング生成部１１は、タスクＤの静的タスクスケジューリングを行う。なお、優先度付与対象タスクは、タスクＤとなる。
【０２８６】
また、静的タスクスケジューリングのときに、タスクＤの後に実行可能であるタスク（配置可能タスク）が、明らかになる。今の場合、配置可能タスクは、タスクＤとの依存が解消するタスクＥ及びタスクＦである。つまり、タスクスケジューリング装置１０Ａは、タスクＥ及びタスクＦの最良実行順序がタスクＤの直後であることを知ることができる。
【０２８７】
静的タスクスケジューリングの後、装置制御部１３は、優先度生成部１２に優先度付与対象タスク（タスクＤ）の優先度の定義（付与）を指示する。
【０２８８】
タスクＡの静的タスクスケジューリング時に明らかなように、タスクＤの最良実行順序は、タスクＡの直後である。タスクＤは、優先度に基づき、タスクＢ及びタスクＣと入れ替わる可能性がある。つまり、タスクＤの最良実行順序は、静的タスクスケジューリング結果の実行順序と異なる。このため、優先度生成部１２は、タスクＤを実行順序変動可能性ありと判断する。そして、優先度生成部１２は、タスクＤの優先度を、先行実行タスク（タスクＢ及びタスクＣ）の中の最も低い優先度（「４」）より低い優先度（例えば「５」）とする（図３６）。
【０２８９】
装置制御部１３は、まだタスクが残っているため、次のタスクを処理する。
【０２９０】
装置制御部１３は、静的タスクスケジューリング生成部１１に、次のタスクの静的タスクスケジューリングを指示する。ここで、静的タスクスケジューリング生成部１１は、コア０上で次にタスクＥを実行することが、性能向上に良いと判断したとする。そのため、静的タスクスケジューリング生成部１１は、タスクＥの静的タスクスケジューリングを行う。なお、優先度付与対象タスクは、タスクＥとなる。
【０２９１】
静的タスクスケジューリングの後、装置制御部１３は、優先度生成部１２に優先度付与対象タスク（タスクＥ）の優先度の定義（付与）を指示する。
【０２９２】
タスクＤの静的タスクスケジューリング時に明らかなように、タスクＥの最良実行順序は、タスクＤの直後である。この実行順序は、上記の静的タスクスケジューリング結果の実行順序と同じである。このため、優先度生成部１２は、タスクＥを実行順序変動可能性なしと判断する。そして、優先度生成部１２は、タスクＥの優先度を、先行するタスクＤより下げる処置は行わず、設定可能な最高の優先度（今の場合「３」）とする（図３７）。
【０２９３】
装置制御部１３は、まだタスクが残っているため、次のタスクを処理する。
【０２９４】
装置制御部１３は、静的タスクスケジューリング生成部１１に、次のタスクの静的タスクスケジューリングを指示する。ここで、静的タスクスケジューリング生成部１１は、コア０上で次にタスクＦを実行することが、性能向上に良いと判断したとする。（なお、配置可能タスクの残りは、タスクＦである（図３７を参照）。）そのため、静的タスクスケジューリング生成部１１は、タスクＦの静的タスクスケジューリングを行う。なお、優先度付与対象タスクは、タスクＦとなる。
【０２９５】
タスクＤの静的タスクスケジューリング時に明らかなように、タスクＦの最良実行順序は、タスクＤの直後である。タスクＦは、優先度に基づき、タスクＥと入れ替わる可能性がある。つまり、タスクＦの最良実行順序は、静的タスクスケジューリング結果の実行順序と異なる。このため、優先度生成部１２は、タスクＦを実行順序変動可能性ありと判断する。そして、優先度生成部１２は、タスクＦの優先度として、先行実行タスク（タスクＥ）の中の最も低い優先度（「３」）より低い優先度（例えば「４」）とする（図３８）。  
【０２９６】
なお、ここまでの説明において、装置制御部１３が、静的タスクスケジューリング生成部１１と優先度生成部１２を、密に連携させることに基づき、タスクスケジューリング装置１０Ａは、最良実行順序の検出を容易とした。しかし、本実施形態のタスクスケジューリング装置１０Ａが最良実行順序を検出する手法は、これに限らない。
【０２９７】
例えば、予め、実行順序が変わり得る箇所について符号を設定することが想定できる。この設定として、静的タスクスケジューリング生成部１１が、最良実行順序で静的タスクスケジューリングされたか否かを示す符号を付与しても良い。このような構成を用いると、本実施形態のタスクスケジューリング装置１０Ａは、静的タスクスケジューリング生成部１１と優先度生成部１２との動作を分離して、図３１を用いて説明した構成と同様の効果を得ることができる。
【０２９８】
このように、第５の実施形態のタスクスケジューリング装置１０Ａは、既に説明した構成に限らず様々な変形が可能である。
【０２９９】
このように、本実施形態のタスクスケジューリング装置１０Ａは、第１乃至第４の実施形態の効果に加え、最良実行順序の検出を容易にする効果を得ることができる。
【０３００】
その理由は、本実施形態のタスクスケジューリング装置１０Ａは、装置制御部１３を含み、静的タスクスケジューリング生成部１１と優先度生成部１２との連携を実現しているためである。
【０３０１】
あるいは、本実施形態にタスクスケジューリング装置１０Ａは、実行順序が変わり得る箇所に符号を設定するためである。
【０３０２】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０３０３】
この出願は、２０１２年  ８月１３日に出願された日本出願特願２０１２−１７９４９５を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０３０４】
本発明は、静的タスクスケジューリングに基づく実行順序を維持した上で、実行順序の維持に必要な優先度の個数を削減するソフトウェア開発ツールに利用可能である。
【符号の説明】
【０３０５】
１  マルチコアシステム
１０  タスクスケジューリング装置
１０Ａ  タスクスケジューリング装置
１１  静的タスクスケジューリング生成部
１２  優先度生成部
１３  装置制御部
２０  コア部
３０  タスクメモリ
６０  タスクスケジューリング装置
１２１  優先度制御部
１２２  優先度付与対象タスク保持部
１２３  優先度保持部
６１０  ＣＰＵ
６２０  ＲＯＭ
６３０  ＲＡＭ
６４０  記憶装置
６５０  ＩＯ
６６０  入力機器
６７０  表示機器
７００  記憶媒体
【図１】
2014027444.tif 000003
【図２】
2014027444.tif 000004
【図３】
2014027444.tif 000005
【図４】
2014027444.tif 000006
【図５】
2014027444.tif 000007
【図６】
2014027444.tif 000008
【図７】
2014027444.tif 000009
【図８】
2014027444.tif 000010
【図９】
2014027444.tif 000011
【図１０】
2014027444.tif 000012
【図１１】
2014027444.tif 000013
【図１２】
2014027444.tif 000014
【図１３】
2014027444.tif 000015
【図１４】
2014027444.tif 000016
【図１５】
2014027444.tif 000017
【図１６】
2014027444.tif 000018
【図１７】
2014027444.tif 000019
【図１８】
2014027444.tif 000020
【図１９】
2014027444.tif 000021
【図２０】
2014027444.tif 000022
【図２１】
2014027444.tif 000023
【図２２】
2014027444.tif 000024
【図２３】
2014027444.tif 000025
【図２４】
2014027444.tif 000026
【図２５】
2014027444.tif 000027
【図２６】
2014027444.tif 000028
【図２７】
2014027444.tif 000029
【図２８】
2014027444.tif 000030
【図２９】
2014027444.tif 000031
【図３０】
2014027444.tif 000032
【図３１】
2014027444.tif 000033
【図３２】
2014027444.tif 000034
【図３３】
2014027444.tif 000035
【図３４】
2014027444.tif 000036
【図３５】
2014027444.tif 000037
【図３６】
2014027444.tif 000038
【図３７】
2014027444.tif 000039
【図３８】
2014027444.tif 000040
【国際調査報告】
2014027444.tif 000041
2014027444.tif 000042