JP2007018268A - タスクスケジューリング方法、タスクスケジューリング装置、及びタスクスケジューリングプログラム - Google Patents

Abstract

【課題】 タスク実行におけるリアルタイム性を向上させる。
【解決手段】 マルチプロセッサにより複数のタスクの割り当てを行うタスクスケジューリング方法において、前記複数のタスク毎に予め設定されたタスク実行の優先度と、前記マルチプロセッサ個々の処理能力と、前記マルチプロセッサのうち所定時間内に行ったタスク実行に対する応答時間比率と、前記応答時間比率を所定回数分計測した結果から得られる最悪応答時間比率とに基づいて、前記複数のタスクに対する前記マルチプロセッサの割り当てを行うことにより、上記課題を解決する。
【選択図】 図６

Description

本発明は、タスクスケジューリング方法、タスクスケジューリング装置、及びタスクスケジューリングプログラムに係り、特にタスク実行におけるリアルタイム性を向上させるためのタスクスケジューリング方法、タスクスケジューリング装置、及びタスクスケジューリングプログラムに関する。

一般に、マルチプロセッサを用いて複数のタスクを実行させる場合には、それぞれのタスクをどのプロセッサに割り当てるかというスケジューリングが必要となる。図１は、マルチプロセッサシステムの概要構成の一例を示す図である。図１に示すように、マルチプロセッサシステム１０においては、複数のプロセッサ１１−１〜１１−Ｎを有し、各プロセッサ１１間は共有バス等のネットワーク１２によってそれぞれが結合されている。また、ネットワーク１２には、タスクスケジューリング装置１３が接続されており、タスクスケジューリング装置１３により、各プロセッサ１１に対するタスクの割り当てを行っている。

また、図２は、従来のマルチプロセッサシステムのスケジューリング方式の一例を示す図である。例えば、図２に示すように複数のタスク（タスク０〜タスク５）がある場合のスケジューリング方式は、通常予めプロセッサ１１−１〜１１−Ｎ毎に担当させるタスクを静的に割り当て、各タスクは割り当てられた各プロセッサ上でのみ実行を許される。

なお、上述したようなスケジューリング方式では、タスク毎に実行許可時間が存在する。図３は、タスクの実行許可時間を説明するための一例の図である。図３に示すように、タスクの実行許可時間とは、タスクの実行時間ではなく、起動要求発生からタスクの実行締め切りまでの時間を示す。また、タスクの応答時間とは、タスクの起動要求発生からタスクの実行完了までの時間を示す。このように、プロセッサの処理能力等に合わせて静的に実行するタスクが割り当てられる。

なお、このようなスケジューリング方式を用いたマルチプロセッサシステムに関する技術として、プロセッサの負荷を指標とすることでプロセッサ毎のタスクの再割り当てを行うものがある（例えば、特許文献１参照。）。
特開２００４-１９２４００号公報

ところで、タスクによってはリアルタイム性が要求される場合がある。ここで、リアルタイム性とは、タスクの実行が実行許可時間以内に完了する性質を示す。このとき、プロセッサ毎に実行できるタスクが決められているため、あるプロセッサに処理時間の長いタスクが多く割り当てられる場合、リアルタイム性が確保できなくなるという問題がある。

また、特許文献１に示されているようなマルチプロセッサシステムのスケジューリング方式は、プロセッサの負荷を指標とすることでプロセッサ毎のタスクの再割り当てを行っており、プロセッサ毎に実行できるタスクの割り当てが動的に変更できる。しかしながら、特許文献１に示されているようなスケジューリング方式では、負荷の指標として計算処理速度と応答時間の短縮化については考慮されているもののリアルタイム性についての対応はされておらず、タスクの実行許可時間内にタスクの実行が完了されない状況が起こり得るという問題がある。

本発明は、上述した問題点に鑑みなされたものであり、タスク実行におけるリアルタイム性を向上させるためのタスクスケジューリング方法、タスクスケジューリング装置、及びタスクスケジューリングプログラムを提供することを特徴とする。

上述の目的を達成するために、本発明は、マルチプロセッサにより複数のタスクの割り当てを行うタスクスケジューリング方法において、前記複数のタスク毎に予め設定されたタスク実行の優先度と、前記マルチプロセッサ個々の処理能力と、前記マルチプロセッサのうち所定時間内に行ったタスク実行に対する応答時間比率と、前記応答時間比率を所定回数分計測した結果から得られる最悪応答時間比率とに基づいて、前記複数のタスクに対する前記マルチプロセッサの割り当てを行うことを特徴とする。

また、本発明は、マルチプロセッサにより複数のタスクの割り当てを行うタスクスケジューリング方法において、前記マルチプロセッサを構成する複数のプロセッサの個々の処理能力を計測する処理能力計測ステップと、前記複数のタスク毎に予め設定されたタスク優先度と、前記処理能力計測ステップにより得られる処理能力結果から各タスクに対する初期割り当て行う割り当てステップと、前記割り当てステップにより得られるタスクの割り当て結果に基づいてタスクを実行し、所定時間におけるタスクの応答時間比率を計測する応答時間比率計測ステップと、前記応答時間比率を所定回数分計測して、計測した複数の応答時間比率から最悪応答時間比率を選出する最悪応答比率選出ステップと、各タスクの前記最悪応答時間比率と設定比率とに基づいて、タスクに対するプロセッサの再割り当てを行う再割り当てステップとを有することを特徴とする。

これにより、タスクの優先度と、プロセッサ毎の処理能力と、応答時間比率と、最悪応答時間比率とに基づいて、最適なプロセッサにタスクを実行させることができる。したがって、タスク実行におけるリアルタイム性を向上させることができる。

更に、前記再割り当てステップは、前記タスクの再割り当てを行う際、各タスクにおける最悪応答時間比率の見積もりを行い、最悪応答時間比率が最も低いプロセッサに前記タスクの再割り当てを行うことが好ましい。これにより、予め各タスクの最悪応答時間比率の見積もりを行うことで、最適なプロセッサにタスクの割り当てを行うことができる。

更に、前記再割り当てステップは、前記複数のプロセッサ毎にタスクの再割り当ての許可又は禁止を設定することが好ましい。これにより、再割り当てを行う前にプロセッサに対して再割り当ての許可又は禁止を設定することができる。したがって、無駄なく迅速に再割り当てを行うことができる。

また、本発明は、マルチプロセッサにより複数のタスクの割り当てを行うタスクスケジューリング装置において、前記マルチプロセッサを構成する複数のプロセッサの個々の処理能力を計測する処理能力計測手段と、前記複数のタスク毎に予め設定されたタスク優先度と、前記処理能力計測手段により得られる処理能力結果から各タスクに対する初期割り当て行うタスク割当手段と、前記タスク割当手段により得られるタスクの割り当て結果に基づいてタスクを実行し、所定時間におけるタスクの応答時間比率を計測し、更に計測した前記応答時間比率を所定回数分計測して得られる複数の応答時間比率から最悪応答時間比率を選出する応答時間比率計測手段とを有し、前記タスク割当手段は、各タスクの前記最悪応答時間比率と設定比率とに基づいて、タスクに対するプロセッサの再割り当てを行うことを特徴とする。これにより、タスクの優先度と、プロセッサ毎の処理能力と、応答時間比率と、最悪応答時間比率とに基づいて、最適なプロセッサにタスクを実行させることができる。したがって、タスク実行におけるリアルタイム性を向上させることができる。

更に、前記タスク割当手段は、前記タスクの再割り当てを行う際、各タスクにおける最悪応答時間比率の見積もりを行い、最悪応答時間比率が最も低いプロセッサに前記タスクの再割り当てを行うことが好ましい。これにより、予め各タスクの最悪応答時間比率の見積もりを行うことで、最適なプロセッサにタスクの割り当てを行うことができる。

更に、前記タスク割当手段は、前記複数のプロセッサ毎にタスクの再割り当ての許可又は禁止を設定することが好ましい。これにより、再割り当てを行う前にプロセッサに対して再割り当ての許可又は禁止を設定することができる。したがって、無駄なく迅速に再割り当てを行うことができる。

また、本発明は、マルチプロセッサにより複数のタスクの割り当てを行うタスクスケジューリングをコンピュータに実行させるためのタスクスケジューリングプログラムにおいて、前記マルチプロセッサを構成する複数のプロセッサの個々の処理能力を計測する処理能力計測処理と、前記複数のタスク毎に予め設定されたタスク優先度と、前記処理能力計測処理により得られる処理能力結果から各タスクに対する初期割り当て行う割り当て処理と、前記割り当て処理により得られるタスクの割り当て結果に基づいてタスクを実行し、所定時間におけるタスクの応答時間比率を計測する応答時間比率計測処理と、前記応答時間比率を所定回数計測して、計測した複数の応答時間比率から最悪応答時間比率を選出する最悪応答比率選出処理と、各タスクの前記最悪応答時間比率と設定比率とに基づいて、タスクに対するプロセッサの再割り当てを行う再割り当て処理とをコンピュータに実行させる。これにより、タスクの優先度と、プロセッサ毎の処理能力と、応答時間比率と、最悪応答時間比率とに基づいて、最適なプロセッサにタスクを実行させることができる。したがって、タスク実行におけるリアルタイム性を向上させることができる。また、実行プログラムをコンピュータにインストールすることにより、容易にタスクスケジューリング処理を実現することができる。

更に、前記再割り当て処理は、前記タスクの再割り当てを行う際、各タスクにおける最悪応答時間比率の見積もりを行い、最悪応答時間比率が最も低いプロセッサに前記タスクの再割り当てを行うことが好ましい。これにより、予め各タスクの最悪応答時間比率の見積もりを行うことで、最適なプロセッサにタスクの割り当てを行うことができる。

更に、前記再割り当て処理は、前記複数のプロセッサ毎にタスクの再割り当ての許可又は禁止を設定することを特徴とする。これにより、再割り当てを行う前にプロセッサに対して再割り当ての許可又は禁止を設定することができる。したがって、無駄なく迅速に再割り当てを行うことができる。

本発明によれば、タスク実行におけるリアルタイム性を向上させることができる。

以下に、本発明におけるタスクスケジューリング方法、タスクスケジューリング装置、及びタスクスケジューリングプログラムを好適に実施した形態について、図面を用いて説明する。なお、後述する本発明の実施形態において、マルチプロセッサシステムの概要構成は、上述した図１と同様の構成を用いる。

図４は、タスクスケジューリング装置の機能構成の一例を示す図である。図４に示すタスクスケジューリング装置２０は、送受信手段２１と、処理能力計測手段２２と、タスク割当手段２３と、応答時間比率計測手段２４と、記憶手段２５と、制御手段２６とを有するよう構成されている。なお、タスクスケジューリング装置２０は、図１に示すタスクスケジューリング装置１３と同様の位置に設置される。

送受信手段２１は、タスクスケジューリング装置２０と各プロセッサ１１−１〜１１−Ｎ間との制御信号やデータ等の送受信をネットワーク１２を介して行う。また、処理能力計測手段２２は、システム起動時に各プロセッサの処理能力（パフォーマンス）を計測する。なお、処理能力を計測する際には、予め設定された処理を行って各プロセッサ１１−１〜１１−Ｎの処理能力が把握できるような計測用タスクを用いる。なお、計測用タスクは、予め記憶手段２５に記憶されている。処理能力計測手段２２は、この計測用タスクを送受信手段２１からネットワーク１２を介して各プロセッサ１１−１〜１１−Ｎに送信させる。また、各プロセッサ１１で実行されることで得られる実行結果は、ネットワーク１２を介して送受信手段２１で受け取り記憶手段２５に記憶される。なお、上述の制御は、制御手段２６により行われる。

タスク割当手段２３は、処理能力計測手段２２により計測された各プロセッサ１１−１〜１１−Ｎの処理能力結果から実際に実行させる複数のタスクに予め設定された優先度（タスク優先度）に基づいてタスクの初期割り当てを行う。なお、この優先度は、任意に設定されていてもよく、また複数のタスクにおける順序や処理の複雑さ等に基づいて設定されていてもよい。また、タスク割当手段２３は、初期割り当てが完了した後、制御手段２６にマルチプロセッサシステムを実行状態に移行させる。なお、実際に実行させる複数のタスクは、予め記憶手段２５に記憶されている。

また、タスク割当手段２３は、予め設定されたタスクの実行許可時間内における実行時間の比率（実行時間比率）を算出し、その算出結果や後述する応答時間比率計測手段２４により計測される各プロセッサに対する応答時間比率の計測結果等に基づいて、記憶手段２５に記憶されているまだ実行されていないタスクの再割り当てを行う。なお、タスクの再割り当ては、タスクの優先度、プロセッサの処理能力、応答時間比率、及び最悪応答時間比率等を用いて、例えばタスクの実行が実行許可時間以内に完了し、最悪応答時間比率が各プロセッサ１１−１〜１１−Ｎに対して予め設定されている設定比率を超えないような予め設定された条件を満たすようにタスクの再割り当てを行う。つまり、各タスクの最悪応答時間比率及び各プロセッサ処理能力に基づいてプロセッサ毎のタスクの再割り当てを行う。更に、タスク割当手段２３は、プロセッサ１１−１〜１１−Ｎ毎にタスクの再割り当ての許可又は禁止の制限を設定することもできる。なお、具体的なタスクの割り当て手法については後述する。

次に、応答時間比率計測手段２４は、予め設定されたタスクの実行許可時間内における応答時間（タスクの起動要求発生からタスクの実行完了までの時間）の比率（応答時間比率）を計測する。また、応答時間比率計測手段２４は、応答時間比率の計測を予め設定された所定の回数分繰り返し行い、計測した応答時間比率の中で最大のもの（最悪応答時間比率）を選出する。また、応答時間比率計測手段２４は、最悪応答時間比率と、設定比率とに基づいて、タスクに対するプロセッサの再割り当てを行うか否かを判断し、必要に応じてタスク割当手段２３に再割り当ての指示を出力する。また、応答時間比率計測手段２４は、計測結果等を記憶手段２５に記憶させる。

記憶手段２５は、上述した計測用タスクを記憶したり、タスク割当手段２３により割り当てられた内容を記憶したり、応答時間比率計測手段２４における計測結果等を記憶する。更に、記憶手段２５は、マルチプロセッサシステムを終了する際、現時点で各タスクに対するプロセッサの割り当て先の情報を記憶する。これにより、今回のシステムの実行により設定された各タスクに対するプロセッサの割り当て先を次回のシステム再起動後に継続させることができる。これにより、再起動後に割り当て処理をやり直す必要がなく迅速にタスクの実行を行うことができる。

また、制御手段２６は、各種演算やタスクスケジューリング装置２０における各構成部とのデータの入出力や実行指示等の処理を行い、タスクスケジューリング装置２０全体の制御を行う。具体的には、制御手段２６は、例えばマルチプロセッサシステムを実行状態へ移行したり、タスク再割り当ての指示等を行う。

上述したタスクスケジューリング装置２０を用いて、タスクの実行が実行許可時間以内に完了するように、プロセッサ毎のタスク割り当てを動的に変更するスケジューリング方式を実現することができる。これにより、マルチプロセッサシステムにおいてリアルタイム性を向上させることができる。

ここで、本発明におけるタスクスケジューリング装置２０は、上述した専用の装置構成等を用いて、マルチプロセッサシステムにおけるタスクスケジューリング処理を行うこともできるが、各構成における処理をコンピュータに実行させることができる実行プログラムを生成し、例えば、汎用のパーソナルコンピュータ、サーバ等にそのプログラムをインストールすることにより、本発明におけるタスクスケジューリング処理を実現することができる。

＜ハードウェア構成＞
ここで、本発明におけるタスクスケジューリング処理が実行可能なコンピュータのハードウェア構成例について図を用いて説明する。図５は、本発明におけるタスクスケジューリング処理が実現可能なハードウェア構成の一例を示す図である。

図５におけるコンピュータ本体には、入力装置３１と、出力装置３２と、ドライブ装置３３と、補助記憶装置３４と、メモリ装置３５と、各種制御を行うＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）３６と、ネットワーク接続装置３７とを有するよう構成されており、これらはシステムバスＢで相互に接続されている。

入力装置３１は、コンピュータを使用するユーザが操作するキーボード及びマウス等のポインティングデバイスを有しており、ユーザからのプログラムの実行等、各種操作信号を入力する。出力装置３２は、本発明における処理を行うためのコンピュータ本体を操作するのに必要な各種ウィンドウやデータ等を表示するディスプレイ（モニタ）を有し、ＣＰＵ３６が有する制御プログラムによりタスクスケジューリングプログラムの実行経過や結果等を表示することができる。

ここで、本発明において、コンピュータ本体にインストールされる実行プログラムは、例えば、ＣＤ−ＲＯＭ等の記録媒体３８等により提供することができる。プログラムを記録した記録媒体３８は、ドライブ装置３３にセット可能であり、記録媒体３８に含まれる実行プログラムが、記録媒体３８からドライブ装置３３を介して補助記憶装置３４にインストールされる。

補助記憶装置３４は、ハードディスク等のストレージ手段であり、本発明における実行プログラムや、コンピュータに設けられた制御プログラム、上述した計測用タスク等の複数のタスクや処理能力計測結果、応答時間比率計測結果等を蓄積し必要に応じて入出力を行うことができる。

ＣＰＵ３６は、ＯＳ（Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ）等の制御プログラム、及びメモリ装置３５により読み出され格納されている実行プログラムに基づいて、各種演算や各ハードウェア構成部とのデータの入出力等、コンピュータ全体の処理を制御して、タスクスケジューリングプログラムにおける各処理を実現することができる。また、プログラムの実行中に必要な各種情報等は、補助記憶装置３４から取得することができ、また格納することもできる。

ネットワーク接続装置３７は、通信ネットワーク等と接続することにより、実行プログラムを通信ネットワークに接続されている他の端末等から取得したり、プログラムを実行することで得られた実行結果又は本発明における実行プログラムを他の端末等に提供することができる。また、ネットワーク接続装置３７により各プロセッサと制御信号やデータの送受信を行うことができる。

上述したようなハードウェア構成により、特別な装置構成を必要とせず、低コストで本発明におけるタスクスケジューリング処理を実現することができる。また、プログラムをインストールすることにより、容易にタスクスケジューリング処理を実現することができる。

＜タスクスケジューリング処理手順＞
次に、本発明における実行プログラムにおけるタスクスケジューリング処理手順についてフローチャートを用いて説明する。図６は、本発明におけるタスクスケジューリング処理手順を示す一例のフローチャートである。

システムの起動時やプログラムの実行開始指示等により、タスクスケジューリング処理が実行されると、まず各タスクに対するプロセッサの割り当て先が設定（記憶）されているかを判断する（Ｓ０１）。これは、後述するＳ１２において、前回のシステムの実行により設定された各タスクに対するプロセッサの割り当て先を今回のシステム再起動後に有効にすることで、システムの起動毎に割り当て処理を行う必要がなく迅速にタスクの実行を行うための処理である。

ここで、各タスクに対するプロセッサの割り当て先が設定されていない場合（Ｓ０１において、ＮＯ）、プロセッサの処理能力を計測する（Ｓ０２）。このとき、上述したように予め計測用タスクを用意しておき、その計測用タスクを各プロセッサに用いることによりプロセッサ毎の処理能力（パフォーマンス）を計測する。次に、プロセッサ処理能力及び各タスクに与えられた優先度（タスク優先度）よりタスクの初期割り当てを行う（Ｓ０３）。

次に、Ｓ０３の処理が終了後、又はＳ０１の処理において予めプロセッサの割り当て先が設定されている場合（Ｓ０１において、ＹＥＳ）、マルチプロセッサシステムをタスク実行状態に移行させる（Ｓ０４）。

次に、実行後から所定の周期になったかを判断し（Ｓ０５）、所定周期になった場合（Ｓ０５において、ＹＥＳ）、実行許可時間に対する各タスクの応答時間の比率（応答時間比率）を算出することで計測する（Ｓ０６）。なお、Ｓ０６の処理により計測された各タスクの応答時間比率は、記憶手段等により記憶される。また、Ｓ０６の処理が終了後、応答時間比率の計測（算出）が所定回数を超えたかを判断する（Ｓ０７）。

ここで、所定回数を超えている場合（Ｓ０７において、ＹＥＳ）、つまり、応答時間比率の計測を所定回数分繰り返した後、応答時間比率の中で最大のもの（最悪応答時間比率）を選出する（Ｓ０８）。また、Ｓ０８の処理が終了後、タスクの再割り当ての必要があるかを判断し（Ｓ０９）、タスクの再割り当ての必要がある場合（Ｓ０９において、ＹＥＳ）、各タスクの最悪応答時間比率及び各プロセッサ処理能力に基づいてプロセッサ毎のタスクの再割り当てを行う（Ｓ１０）。なお、Ｓ１０の処理では、最悪応答時間比率が予め設定されている設定比率を超えているプロセッサがあれば、設定比率を超えていないプロセッサにタスクの再割り当てを行う。また、タスクの再割り当てを行う際、各タスクの最悪応答時間比率の見積もりを行い、再割り当て先のプロセッサ上でタスクが設定比率を超えないように割り当てを行う。また、Ｓ１０の処理後は、Ｓ０５に戻って上述した処理を繰り返し行う。

なお、Ｓ０５の処理において所定周期に達していない場合（Ｓ０５において、ＮＯ）、Ｓ０７の処理において所定回数を超えていない場合（Ｓ０７において、ＮＯ）、Ｓ０９の処理においてタスクの再割り当ての必要がない場合（Ｓ０９において、ＮＯ）、又はＳ１０の処理が終了後、タスクスケジューリング処理を終了するか否かの判断を行い（Ｓ１１）、処理を終了しない場合（Ｓ１１において、ＮＯ）、Ｓ０５に戻り上述した処理を繰り返し行う。

また、Ｓ１１の処理において、処理を終了させる場合（Ｓ１１において、ＹＥＳ）、現時点で各タスクに対するプロセッサの割り当て先を記憶して（Ｓ１２）タスクスケジューリング処理を終了する。

上述したタスクスケジューリング処理により、タスクの優先度と、プロセッサ毎の処理能力と、応答時間比率と、最悪応答時間比率とに基づいて、最適なプロセッサにタスクを実行させることができる。したがって、タスク実行におけるリアルタイム性を向上させることができる。また、プロセッサの負荷分散が高精度に実現できる。また、プログラムをインストールすることにより、容易にタスクスケジューリング処理を実現することができる。

＜タスクスケジューリング処理の具体例＞
次に、タスクスケジューリング処理の具体例について図を用いて説明する。まず、システム起動時に各プロセッサの処理能力（パフォーマンス）を計測し、記憶媒体等の記憶手段等に記録しておく。次に、各タスクの優先度とプロセッサの処理能力とに基づいて、プロセッサ毎のタスクの割り当てを行う。ここで、図７は、プロセッサ及び処理能力の対応表と、タスクに対する設定内容の一例を示す図である。まず、図７（ａ）に示す対応表は、各プロセッサＩＤにおける処理能力を数値で表したものである。なお、プロセッサＩＤは、各プロセッサを識別するための情報であり、数値や桁数は特に限定されるものではなく、また文字等を用いたり、数値及び文字を組み合わせてもよい。また、処理能力の数値は、計測用タスクに対応する予め設定された処理能力を「１」としておき、その処理能力に対して何倍の処理能力があるかを示している。つまり、図７に示す処理能力の数値が高いほど処理能力も高いことになる。

また、図７（ｂ）に示すタスクに対する設定内容は、タスクＩＤ毎にタスク優先度及び起動周期が予め設定されている。ここで、タスクＩＤは、タスクを識別するための情報であり、数値や桁数は特に限定されるものではなく、例えば上述したように文字等を用いてもよい。また、図７（ｂ）におけるタスク優先度は、数値が小さいほど優先度が高いものとして設定しているが、本発明においてこの限りではなく、例えば逆であってもよい。また、タスク優先度は数値に限定されず、例えば「高」、「中」、「低」等の文字やその組み合わせ等を用いてもよい。

更に、図７（ｂ）に示す起動周期には、例えば、２〔ｍｓ〕や３〔ｍｓ〕等の時間情報が蓄積される。なお、周期的な実行を行わない単発的なタスクの場合には、非周期起動情報として、例えば「０」や「非」等の数値、文字等が設定される。

図７に示すように設定された各タスクの優先度と上述した各プロセッサの処理能力に基づいて、プロセッサ毎のタスクの割り当てを行う。なお、タスクの割り当ては、処理能力の高いプロセッサから順にタスクを１つずつ割り当てる。また、割り当てる順序としては、例えばタスクの優先度順等があるが、本発明においては特に限定されるものではない。

ここで、図８は、プロセッサ毎のタスクの割り当ての一例を示す図である。図８に示す例では、割り当ての様子をより明確に説明するために図８の上から優先順位の高いタスク及び優先順位の高いプロセッサを配列している。ここで、まず各タスクのプロセッサへの割り当ては優先順位の高いタスクから処理能力の高いプロセッサに順々に割り当てを行う。また、上述そして、全てのプロセッサに１つのタスクを割り当てた後、その後のタスク（優先度：最大−Ｎ−１）は、処理能力の最も高いプロセッサ１１−１から割り当てられ、更にその後のタスクも順々に処理能力の高いプロセッサ順に割り当てられる。

ここで、優先度の同じタスクが複数存在するときは、起動周期の短いものから優先的に割り当てることとし、周期起動されないタスクは最低の優先度にする。また、全てのタスクの割り当てが完了後、タスクの割り当てを記憶媒体等の記憶手段に記録しておく。ここで、図９は、タスクＩＤとプロセッサとの割り当て対応表の一例を示す図である。図９に示すように割り当て完了後は、各タスクＩＤに対応する割り当て先のプロセッサＩＤが記憶される。なお、プロセッサＩＤ「０」はプロセッサ１１−１のプロセッサＩＤに対応し、プロセッサＩＤ「１」以降もそれぞれプロセッサ１１−２以降に対応している。

また、プロセッサＩＤは、プロセッサを識別できる情報であればよく、数値に限定されず例えば文字等であってもよい。なお、図９に示すようなプロセッサＩＤの割り当てについては、プロセッサが過負荷状態にならないように予めプロセッサの能力とタスクの負荷に応じてタスク数の上限を決めておく必要がある。

次に、上述したように設定したタスクを割り当てた後、マルチプロセッサシステムを実行状態にして各タスクを実行させる。また、所定時間における各タスクの応答時間比率を計測する。更に計測処理を所定回数分繰り返し行い、その都度記憶媒体等の記憶手段に蓄積しておく。ここで、図１０は、応答時間比率の計測結果の一例を示す図である。図１０に示すように、応答時間比率の計測により記録される内容は、タスクＩＤとそのタスクＩＤに対応する応答時間比率である。次に、上述の応答時間比率を複数回分記録し、記録された応答時間比率の中から最悪応答時間比率を選出して、予め設定されている各タスクの優先度と合わせて、記憶媒体内に蓄積しておく。

ここで、図１１は、記憶する各タスクの最悪応答時間比率の結果の一例を示す図である。図１１に示すように、記憶する内容は、各タスクＩＤに対するタスク優先度及び最悪応答時間比率である。次に、割り当てられた全てのタスクについて最悪応答時間比率が設定比率を超えるタスクの有無を確認する。ここで、設定比率を超えるタスク（オーバーランを含む）が割り当てられたプロセッサについてのみ、後述する再割り当て処理を行う。

ただし、この条件の下で割り当てられたタスクが１つしか存在しない場合はプロセッサ１１−１〜１１−Ｎ毎に予め設定されている再割り当て禁止フラグをＯＮにする。これにより、タスク割当手段におけるタスクの再割り当てにおいて、割り当て対象のプロセッサから除かれることになる。つまり、再割り当てを行う前にプロセッサに対して再割り当ての許可又は禁止を設定することができ、無駄なく迅速に再割り当てを行うことができる。また、プロセッサの負荷の集中を防止することができる。

したがって、再割り当て禁止フラグがＯＮとなっている場合と最悪応答時間比率が設定比率を超えない場合は、後述する再割り当て処理は行わずに所定時間の各タスクの応答時間比率を測定する処理へ戻り、上述した処理を繰り返し行う。なお、本発明では、禁止フラグに限定されるものではなく、例えば許可フラグを設けていれば、許可フラグをＯＦＦにする等により対応を行うことができる。

なお、タスクの終了後、又は処理終了後には、システム再起動後に割り当てた内容を有効にするため、上述した図９に示す割り当て先のプロセッサＩＤを更新しておいてもよい。これにより、タスクを最適なプロセッサに割り当てることができる。

＜タスクの再割り当て処理＞
次に、上述したタスクの再割り当て処理について説明する。まず、上述した処理において選出したタスクの最悪応答時間比率が、設定比率を超えているプロセッサにおける最低優先度のタスクの実行時間を算出する。なお、算出手順としては、まず最低優先度タスク以外の全てのタスクについて最低優先度タスクの実行許可時間内における起動回数を算出する。この起動回数に基づいて最低優先度タスク以外のタスクの実行時間を算出する。また、算出した実行時間と、最低優先度タスクの実行許可時間、最低優先度タスクの最悪応答時間比率を用いて、最低優先度タスクの実行時間を算出する。

ここで、最低優先度タスクの実行時間を算出する方法について図を用いて説明する。図１２は、最悪応答時間比率が設定比率を超えた場合のタスクの割り当ての一例を示す図である。図１２に示す例では、ある１つのプロセッサ上に優先度の異なる３つのタスクが割り当てられている。割り当てられているタスクは、タスク０（起動周期＝１ｍｓ，優先度＝高）、タスク１（起動周期＝２ｍｓ，優先度＝中）、及びタスク２（起動周期＝３ｍｓ，優先度＝低）となっている。また、タスク毎の最悪応答時間比率は、タスク０の最悪応答時間比率＝０．６、タスク１の最悪応答時間比率＝０．４５、タスク２の最悪応答時間比率＝０．６であるとする。

タスク１の最悪応答時間比率Ｒ_ｗｒ１と起動周期Ｃ_１よりタスク１の１周期当たりの最悪応答時間Ｔ_ｗｒ１は、Ｔ_ｗｒ１＝Ｒ_ｗｒ１×Ｃ_１＝０．４５×２＝０．９ｍｓとなる。また、タスク０の起動周期Ｃ_０とＴ_ｗｒ１との関係は“Ｃ_０＞Ｔ_ｗｒ１”となる。このため、タスク１の１周期当たりのタスク０の起動回数は１回となる。

次に、タスク０は最高優先度であるため、常に最悪応答時間で実行している。即ち実行時間＝最悪応答時間と見なすことができる。ここで、タスク０の最悪応答時間比率Ｒ_ｗｒ０及び起動周期Ｃ_０により、タスク１の最悪応答時間におけるタスク０の実行時間Ｔ_ｅ０は、Ｔ_ｅ０＝Ｒ_ｗｒ０×（１×Ｃ_０）＝０．６×（１×１）＝０．６ｍｓとなる。上述により、タスク１の１周期当たりの実行時間Ｔ_ｅ１は、Ｔ_ｅ１＝Ｔ_ｗｒ１−Ｔ_ｅ０＝０．９−０．６＝０．３ｍｓとなる。また、タスク１の１周期当たりの応答時間比率Ｒ_ｅ１は、Ｒ_ｅ１＝Ｔ_ｅ１÷Ｃ１＝０．３÷２＝０．１５となる。

次に、図１２のタスク２における最悪応答時間比率Ｒ_ｗｒ２と起動周期Ｃ_２により、タスク２の１周期当たりの最悪応答時間Ｔ_ｗｒ２は、Ｔ_ｗｒ２＝Ｒ_ｗｒ２×Ｃ_２＝０．６×３＝１．８ｍｓとなる。また、タスク０の起動周期Ｃ_０とＴ_ｗｒ２との関係は、“２×Ｃｏ＞Ｔ_ｗｒ２”となるため、タスク２の１周期当たりのタスク０の起動回数は２回となる。また、タスク１の起動周期Ｃ_１とＴ_ｗｒ２との関係が、“Ｃ１＞Ｔ_ｗｒ２”となるため、タスク２の１周期当たりのタスク１の起動回数は１回となる。

また、タスク２の最悪応答時間におけるタスク０の実行時間Ｔ_ｅ０’は、Ｔ_ｅ０’＝Ｒ_ｗｒ０×（２×Ｃ_０）＝０．６×（２×１）＝１．２ｍｓとなる。また、タスク２の最悪応答時間におけるタスク１の実行時間Ｔ_ｅ１’は、Ｔ_ｅ１’＝Ｒ_ｅ１×（１×Ｃ_１）＝０．１５×（１×２）＝０．３ｍｓとなる。

また、タスク２の１周期当たりの実行時間Ｔ_ｅ２’は、Ｔ_ｅ２’＝Ｔ_ｗｒ２−Ｔ_ｅ０’−Ｔ_ｅ１’＝１．８−１．２−０．３＝０．３ｍｓとなる。また、タスク２の１周期当たりの実行時間比率Ｒ_ｅ２’は、Ｒ_ｅ２’＝Ｔ_ｅ２’÷Ｃ_２＝０．３÷３＝０．１となる。

次に、上述にて割り当てられた全てのタスクについて最悪応答時間比率が、設定比率を超えていないプロセッサのうち、プロセッサの処理能力（パフォーマンス）が最も高いプロセッサを選出する。また、選出されたプロセッサにて割り当てられた全てのタスクの実行時間を算出する。手順としては、まず最低優先度タスク以外の全てのタスクについて最低優先度タスクの実行許可時間内における起動回数を算出する。また、算出した起動回数に基づいて最低優先度タスク以外のタスクの実行時間を算出する。

更に、割り当て先を変更するタスク（設定比率を超えているプロセッサに割り当てられたタスクのうち、最低優先度のタスク）について、新しい割り当て先プロセッサでの実行時間を算出する。また、上述にて得られた割り当て先を変えるタスクの１周期当たりの実行時間Ｔ_ｅＯＬＤ、現在割り当てられているプロセッサの処理能力Ａ_ＯＬＤ、新しい割り当て先プロセッサの処理能力Ａ_ＮＥＷとした場合、新しい割り当て先プロセッサでの実行時間Ｔ_ｅＮＥＷは、Ｔ_ｅＮＥＷ＝Ｔ_ｅＯＬＤ×（Ａ_ＮＥＷ÷Ａ_ＯＬＤ）となり、実行時間比率Ｒ_ＮＥＷは、起動周期ＣよりＲ_ｅＮＥＷ＝Ｔ_ｅＮＥＷ÷Ｃとなる。

これにより、算出された割り当て先を変更するタスクの新しい割り当て先プロセッサでの実行時間Ｔ_ｅＮＥＷ及び起動周期と、現在プロセッサに割り当てられたタスク全ての実行時間比率及び起動周期とにより、新しくタスク割り当てを行った状態での各タスクの最悪応答時間比率の見積もりを行う。なお、新しくタスク割り当てを行った状態での各タスクの最悪応答時間比率の見積もり方法の詳細については後述する。

ここで、図１３は、最悪応答時間比率の見積もりを行った後のタスク割り当ての様子を説明するための一例の図である。上述の見積もりを行った後、新しくタスク割り当てを行ったプロセッサのうち設定比率を超えるタスクが１つ以上存在した場合、図１３（ａ）に示すように、現状のタスクの割り当てを中止し、次に処理能力が高いプロセッサを割り当てて処理を行う。つまり、図１３（ａ）に示すタスク（優先度：最大−Ｋ（Ｋ＞Ｎ））は、一端プロセッサ１１−２に割り当てられたが、タスク（優先度：最大−Ｋ）がプロセッサ１１−２の設定比率を超えるタスクであったため、次に処理能力が高いプロセッサ（図１３（ａ）におけるプロセッサ１１−３）にタスク（優先度：最大−Ｋ）を割り当てて処理を行わせる。

また、タスク（優先度：最大−Ｋ）が次に処理能力が高いプロセッサへの割り当てもできず、以降のプロセッサ１１−Ｎまで割り当てができなかった場合は、図１３（ｂ）示すようにプロセッサ１１−１に再割り当てを行い禁止フラグをＯＮに変更して、タスク（優先度：最大−Ｋ）が終了するまで又は最悪応答時間比率（見積もり値）が設定比率内になるまで等の条件を設けて、他のタスクがプロセッサ１１−１に割り当てられないようにする。また、上述したように所定時間の各タスクの応答時間比率の計測を行う。ここで、各タスクの最悪応答時間比率（見積もり値）が設定比率内であれば、再割り当てされた各タスクに対するプロセッサの割り当て先を記憶して所定時間の各タスクの応答時間比率の計測等、それ以降の処理を行う。

＜最悪応答時間比率の見積もり方法＞
ここで、新しくタスク割り当てを行った状態での、各タスクの最悪応答時間比率の見積もり方法について図を用いて説明する。図１４は、最悪応答時間比率の見積もり例を説明するための図である。図１４の例では、まず図１４（ａ）に示す予め２つのタスク（タスクＡとタスクＢ）が割り当てられていたプロセッサに、新しくタスクＣが割り当てられた状態（図１４（ｂ））を表している。なお、図１４に示す３つのタスクは、タスクＡ（起動周期Ｃ_Ａ＝１ｍｓ，優先度＝高）、タスクＢ（起動周期Ｃ_Ｂ＝４ｍｓ，優先度＝低）、タスクＣ（起動周期Ｃｃ＝３ｍｓ，優先度＝中）となっている。また、タスク毎の実行時間比率は、タスクＡの実行時間比率Ｒ_ｅＡが０．６、タスクＢの実行時間比率Ｒ_ｅＢは０．１であるとする。更に、タスクＣの実行時間比率Ｒ_ｅＣは０．１５であるとする。

タスクＡは最高優先度であるため、タスクＡの最悪応答時間比率Ｒ_ｗｒＡは、Ｒ_ｗｒＡ’＝Ｒ_ｅＡ＝０．６となる。次に、タスクＡのみを実行させる場合のタスクＡの１周期当たりの空き時間Ｔ_ｆＡを算出する。Ｔ_ｆＡは、Ｔ_ｆＡ＝（１−Ｒ_ｗｒＡ’）×Ｃ_Ａ＝（１−０．６）×１＝０．４ｍｓとなる。

次に、タスクＡと、次に優先度の高いタスクＣのみを実行させる場合を仮定する。この仮定では、Ｔ_ｆＡにおいてタスクＣが常に実行可能であると見なせる。タスクＣの１周期当たりの実行時間Ｔ_ｅＣは、Ｔ_ｅＣ＝Ｒ_ｅＣ×Ｃｃ＝０．１５×３＝０．４５ｍｓと算出される。そのため、Ｔ_ｅＣにおけるＴ_ｆＡの割合Ｒ_ｆＡは、Ｒ_ｆＡ＝Ｔ_ｆＡ÷Ｔ_ｅＣ＝０．４÷０．４５＝０．８９となる。つまり、０．５＜Ｒ_ｆＡ＜１となるため、タスクＣが完了するにはタスクＡの２周期分の時間があれば十分であることがわかる。

上述したタスクＡとタスクＣの優先度の関係より、タスクＣの実行完了までの待ち時間はタスクＡの実行時間×２となる。これにより、タスクＣの最悪応答時間Ｔ_ｗｒＣは、Ｔ_ｗｒＣ＝｛（Ｒ_ｅＡ×Ｃ_Ａ）×２｝＋Ｔ_ｅＣ＝｛（０．６×１）×２｝＋０．４５＝１．６５となる。したがって、タスクＣの最悪応答時間比率Ｒ_ｗｒＣは、Ｒ_ｗｒＣ＝Ｔ_ｗｒＣ÷Ｃｃ＝１．６５÷３＝０．５５となる。

最後に、タスクＡとタスクＣとに加えて、残された最低優先度のタスクＢを実行させる状況を考える。上述より、タスクＡの２周期分の時間（Ｃ_Ａ×２）において、タスクＡ（起動要求回数＝２）、タスクＣ（起動要求回数＝１）は、全て完了していて、かつ空き時間も存在する。このとき、空き時間Ｔ_ｆＡＣは、Ｔ_ｆＡＣ＝２×Ｃ_Ａ−Ｔ_ｗｒＣ＝２×１−１．６５＝０．３５ｍｓとなる。また、タスクＣはタスクＡの２周期目の時間（Ｃ_Ａ×２）にて実行が完了している。そのため、タスクＡの３周期目（Ｃ_Ａ×２以降の時間）における空き時間（Ｔ_ｆＡ＝０．４ｍｓ）は、全てタスクＢの実行に割り当て可能と見なすことができる。更に、タスクＢの１周期当たりのタスクＢの実行時間Ｔ_ｅＢは、Ｔ_ｅＢ＝Ｃ_Ｂ×Ｒ_ｅＢ＝４×０．１＝０．４ｍｓとなる。

上述した内容から、Ｔ_ｆＡＣ＜Ｔ_ｅＢ＜（Ｔ_ｆＡＣ＋Ｔ_ｆＡ）の関係が成立する。したがって、タスクＢの最悪応答時間Ｔ_ｗｒＢ’は、Ｔ_ｗｒＢ’＝｛（Ｒ_ｅＡ×Ｃ_Ａ）×３｝＋Ｔ_ｅＣ＋Ｔ_ｅＢ＝｛（０．６×１）×３｝＋０．４５＋０．４＝２．６５となる。したがって、タスクＢの最悪応答時間比率Ｒ_ｗｒＢ’は、Ｒ_ｗｒＢ’＝Ｔ_ｗｒＢ’÷Ｃ_Ｂ＝２．６５÷４＝０．６６となる。

ここで、図１５は、タスクの再割り当ての一例を示す図である。図１５に示すように、プロセッサ１１−１に設定されていたタスク（優先度：最大−Ｋ）は、上述した算出等を行うことによりプロセッサ１１−２に割り当てられる。上述したように、タスクの再割り当てを行うことにより、タスク実行におけるリアルタイム性を向上させることができる。

また、上述した割り当て結果は、システム再起動後のときにもこの割り当て内容を有効にするため記憶手段等に蓄積する。これによってタスクの再割り当てがなされる。

上述したように本発明によれば、タスク実行におけるリアルタイム性を向上させることができる。具体的には、マルチプロセッサを用いたタスク実行のスケジューリングにおいて、タスクの優先度とプロセッサの処理能力、応答時間比率、最悪応答時間比率を用いることにより、タスクの実行が実行許可時間以内に完了し、かつ最悪応答時間比率が設定比率を超えないようタスクの再割り当てを行うことができる。

なお、上述した本発明に係るタスクスケジューリング装置は、一般的な機械装置の制御システムに適用可能であり、また家電に組み込まれる小規模なシステムからサーバやスーパーコンピュータに代表される大規模な並列計算機まで幅広く適用することができる。更に、１つのＣＰＵの中に演算コアが複数設けられているチップマルチプロセッサ上のリアルタイムシステム上にて運用をする場合においても本発明は有効である。

以上本発明の好ましい実施例について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形、変更が可能である。

マルチプロセッサシステムの概要構成の一例を示す図である。 従来のマルチプロセッサシステムのスケジューリング方式の一例を示す図である。 タスクの実行許可時間を説明するための一例の図である。 タスクスケジューリング装置の機能構成の一例を示す図である。 本発明におけるタスクスケジューリング処理が実現可能なハードウェア構成の一例を示す図である。 本発明におけるタスクスケジューリング処理手順を示す一例のフローチャートである。 プロセッサ及び処理能力の対応表と、タスクに対する設定内容の一例を示す図である。 プロセッサ毎のタスクの割り当ての一例を示す図である。 タスクＩＤとプロセッサとの割り当て対応表の一例を示す図である。 応答時間比率の計測結果の一例を示す図である。 記憶する各タスクの最悪応答時間比率の結果の一例を示す図である。 最悪応答時間比率が設定比率を超えた場合のタスクの割り当ての一例を示す図である。 最悪応答時間比率の見積もりを行った後の割り当ての様子を説明するための一例の図である。 最悪応答時間比率の見積もり例を説明するための図である。 タスクの再割り当ての一例を示す図である。

符号の説明

１０ マルチプロセッサシステム
１１ プロセッサ
１２ ネットワーク
１３，２１ タスクスケジューリング装置
２２ 処理能力計測手段
２３ タスク割当手段
２４ 応答時間比率計測手段
２５ 記憶手段
２６ 制御手段
３１ 入力装置
３２ 出力装置
３３ ドライブ装置
３４ 補助記憶装置
３５ メモリ装置
３６ ＣＰＵ
３７ ネットワーク接続装置
３８ 記録媒体

Claims (10)

1. マルチプロセッサにより複数のタスクの割り当てを行うタスクスケジューリング方法において、
   前記複数のタスク毎に予め設定されたタスク実行の優先度と、前記マルチプロセッサ個々の処理能力と、前記マルチプロセッサのうち所定時間内に行ったタスク実行に対する応答時間比率と、前記応答時間比率を所定回数分計測した結果から得られる最悪応答時間比率とに基づいて、前記複数のタスクに対する前記マルチプロセッサの割り当てを行うことを特徴とするタスクスケジューリング方法。
2. マルチプロセッサにより複数のタスクの割り当てを行うタスクスケジューリング方法において、
   前記マルチプロセッサを構成する複数のプロセッサの個々の処理能力を計測する処理能力計測ステップと、
   前記複数のタスク毎に予め設定されたタスク優先度と、前記処理能力計測ステップにより得られる処理能力結果から各タスクに対する初期割り当て行う割り当てステップと、
   前記割り当てステップにより得られるタスクの割り当て結果に基づいてタスクを実行し、所定時間におけるタスクの応答時間比率を計測する応答時間比率計測ステップと、
   前記応答時間比率を所定回数分計測して、計測した複数の応答時間比率から最悪応答時間比率を選出する最悪応答比率選出ステップと、
   各タスクの前記最悪応答時間比率と設定比率とに基づいて、タスクに対するプロセッサの再割り当てを行う再割り当てステップとを有することを特徴とするタスクスケジューリング方法。
3. 前記再割り当てステップは、
   前記タスクの再割り当てを行う際、各タスクにおける最悪応答時間比率の見積もりを行い、最悪応答時間比率が最も低いプロセッサに前記タスクの再割り当てを行うことを特徴とする請求項２に記載のタスクスケジューリング方法。
4. 前記再割り当てステップは、
   前記複数のプロセッサ毎にタスクの再割り当ての許可又は禁止を設定することを特徴とする請求項２又は３に記載のタスクスケジューリング方法。
5. マルチプロセッサにより複数のタスクの割り当てを行うタスクスケジューリング装置において、
   前記マルチプロセッサを構成する複数のプロセッサの個々の処理能力を計測する処理能力計測手段と、
   前記複数のタスク毎に予め設定されたタスク優先度と、前記処理能力計測手段により得られる処理能力結果から各タスクに対する初期割り当て行うタスク割当手段と、
   前記タスク割当手段により得られるタスクの割り当て結果に基づいてタスクを実行し、所定時間におけるタスクの応答時間比率を計測し、更に計測した前記応答時間比率を所定回数分計測して得られる複数の応答時間比率から最悪応答時間比率を選出する応答時間比率計測手段とを有し、
   前記タスク割当手段は、各タスクの前記最悪応答時間比率と設定比率とに基づいて、タスクに対するプロセッサの再割り当てを行うことを特徴とするタスクスケジューリング装置。
6. 前記タスク割当手段は、
   前記タスクの再割り当てを行う際、各タスクにおける最悪応答時間比率の見積もりを行い、最悪応答時間比率が最も低いプロセッサに前記タスクの再割り当てを行うことを特徴とする請求項５に記載のタスクスケジューリング装置。
7. 前記タスク割当手段は、
   前記複数のプロセッサ毎にタスクの再割り当ての許可又は禁止を設定することを特徴とする請求項５又は６に記載のタスクスケジューリング装置。
8. マルチプロセッサにより複数のタスクの割り当てを行うタスクスケジューリングをコンピュータに実行させるためのタスクスケジューリングプログラムにおいて、
   前記マルチプロセッサを構成する複数のプロセッサの個々の処理能力を計測する処理能力計測処理と、
   前記複数のタスク毎に予め設定されたタスク優先度と、前記処理能力計測処理により得られる処理能力結果から各タスクに対する初期割り当て行う割り当て処理と、
   前記割り当て処理により得られるタスクの割り当て結果に基づいてタスクを実行し、所定時間におけるタスクの応答時間比率を計測する応答時間比率計測処理と、
   前記応答時間比率を所定回数計測して、計測した複数の応答時間比率から最悪応答時間比率を選出する最悪応答比率選出処理と、
   各タスクの前記最悪応答時間比率と設定比率とに基づいて、タスクに対するプロセッサの再割り当てを行う再割り当て処理とをコンピュータに実行させるためのタスクスケジューリングプログラム。
9. 前記再割り当て処理は、
   前記タスクの再割り当てを行う際、各タスクにおける最悪応答時間比率の見積もりを行い、最悪応答時間比率が最も低いプロセッサに前記タスクの再割り当てを行うことを特徴とする請求項８に記載のタスクスケジューリングプログラム。
10. 前記再割り当て処理は、
    前記複数のプロセッサ毎にタスクの再割り当ての許可又は禁止を設定することを特徴とする請求項８又は９に記載のタスクスケジューリングプログラム。

Images