(57)【要約】【課題】処理量を抑えることができるタスクスケジューリング装置等を提供する。【解決手段】タスク起動要求時に、その時点のタイマ機構９０のカウントするシステム時間と、制限時間初期値テーブル６０に記憶された余裕時間の初期値とを加算して、制限時間テーブル２０へ記憶する。デッドライン違反検知機構２００は、デッドラインまでの余裕時間を「制限時間テーブル２０に記憶された各タスクの制限時間−システム時間」として求め、それぞれのタスクについてこの余裕時間が０以上か否かに基づきデッドライン違反を判定する。そして時限優先スケジューリング機構１００は、制限時間テーブル２０に登録されている各タスクの制限時間を比較し、最も制限時間の小さいタスクを最優先の実行優先度として、そのタスクを次の実行タスクとする。【選択図】図１
2004070579.tif 000002
【特許請求の範囲】
【請求項１】
タスク毎の制限時間を保持する制限時間保持手段と、
前記制限時間保持手段に保持されたタスク毎の制限時間に基づいてスケジューリングを行うスケジューリング手段と
を備えるタスクスケジューリング装置において、
時間の経過に伴いシステム時間のカウントを行うタイマ手段と、
タスクの起動要求があった場合、前記タイマ手段によってカウントされたシステム時間と予め設定された当該タスクのデッドラインまでの余裕時間の初期値とを加算して求めた当該タスクの制限時間を前記制限時間保持手段へ登録する時間加算手段を備えること
を特徴とするタスクスケジューリング装置。
【請求項２】
請求項１に記載のタスクスケジューリング装置において、
前記スケジューリング手段は、前記タスク毎の制限時間のうち、最も制限時間が小さいタスクから順に実行優先度の高いタスクとするスケジューリングを行うこと
を特徴とするタスクスケジューリング装置。
【請求項３】
請求項１または２に記載のタスクスケジューリング装置において、
前記スケジューリング手段は、前記タスク毎の制限時間のうち、制限時間の最も少ないタスクを次の実行タスクとするスケジューリングを行うこと
を特徴とするタスクスケジューリング装置。
【請求項４】
請求項１または２に記載のタスクスケジューリング装置において、
前記スケジューリング手段は、前記タスク毎の制限時間のうち、前記システム時間に最も近い前記制限時間を持つタスクを次の実行タスクとするスケジューリングを行うこと
を特徴とするタスクスケジューリング装置。
【請求項５】
請求項１〜４のいずれかに記載のタスクスケジューリング装置において、
タスク毎にタスクの状態を保持するタスク状態保持手段を備え、
前記スケジューリング手段は、前記スケジューリングを、前記タスク状態保持手段に保持されたタスクの状態が、起動状態のタスクについてのみ行うこと
を特徴とするタスクスケジューリング装置。
【請求項６】
請求項１〜５のいずれかに記載のタスクスケジューリング装置において、
前記制限時間保持手段に保持されたタスク毎の制限時間と前記タイマ手段によってカウントされるシステム時間に対し、所定の時間を減算することで、時間の更正をおこなう時間更正手段を備えること
を特徴とするタスクスケジューリング装置。
【請求項７】
請求項６に記載のタスクスケジューリング装置において、
前記時間更正手段は、前記時間の更正を、前記タスク毎の制限時間と前記システム時間に対して同時に行うこと
を特徴とするタスクスケジューリング装置。
【請求項８】
請求項６または７に記載のタスクスケジューリング装置において、
前記時間更正手段は、前記時間の更正を、前記所定の時間として予め定めた時間を減算することにより行うこと
を特徴とするタスクスケジューリング装置。
【請求項９】
請求項６〜８のいずれかに記載のタスクスケジューリング装置において、
前記時間更正手段における、前記システム時間に対する前記所定の時間と、前記タスクの制限時間に対する前記所定の時間とを同じ値とすること
を特徴とするタスクスケジューリング装置。
【請求項１０】
請求項６〜９のいずれかに記載のタスクスケジューリング装置において、
前記時間更正手段は、前記所定の時間を、前記システム時間と前記各タスクの制限時間との中で最小の値とすること
を特徴とするタスクスケジューリング装置。
【請求項１１】
請求項１〜１０のいずれかに記載のタスクスケジューリング装置において、
前記制限時間保持手段に保持されたタスク毎の制限時間と前記システム時間とに基づいてデッドライン違反を検知するデッドライン違反検知手段を備えること
を特徴とするタスクスケジューリング装置。
【請求項１２】
請求項１１に記載のタスクスケジューリング装置において、
前記デッドライン違反検知手段は、前記制限時間保持手段に保持されたタスクの制限時間がシステム時間より小さくなった場合にデッドライン違反であると判定すること
を特徴とするタスクスケジューリング装置。
【請求項１３】
タスク毎の制限時間に基づいてスケジューリングを行うスケジューリング方法において、
タスクの起動要求があった場合、当該タスクの制限時間を、時間の経過に伴ってカウントされるシステム時間と予め設定された当該タスクのデッドラインまでの余裕時間の初期値とを加算した値とすること
を特徴とするタスクスケジューリング方法。
【請求項１４】
請求項１〜１２のいずれかに記載のタスクスケジューリング装置の機能をコンピュータに実現させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
マルチタスク処理等を実現するためのタスクスケジューリング装置およびタスクスケジューリング方法等に関する。
【０００２】
【従来の技術】
マルチタスク処理を実現するためのプログラムのスケジューリング方法として、時限優先スケジューリング（ＥＤＦ（Ｅａｒｌｉｅｓｔ　Ｄｅａｄｌｉｎｅ　Ｆｉｒｓｔ）スケジューリング）が知られている。このスケジューリング方法は、実行可能なタスクのうちデッドラインまでの余裕時間が最も少ないタスクを実行タスクとして決定する方法である。
【０００３】
こうしたデッドラインまでの余裕時間は、例えば特開平９−３１９５９６号公報および特開２００１−２３６２３６号公報に記載のように、初期値をテーブル等に静的に記憶しておき、この記憶された初期値を時間の経過に伴って減算していくことで求めている。
【０００４】
こうした従来のタスクスケジューリング装置の例を図７に示して説明する。
図７に示すタスクスケジューリング装置は、タスク毎のデッドラインまでの余裕時間の初期値を制限時間初期値テーブル５６０に記憶している。そして、新たなタスクの起動要求が発生した場合、タスク登録機構５５０が、ＣＰＵからの起動要求があったタスクに対応する制限時間・状態記憶機構５２１，５２２，…に対して、そのタスクの状態を起動状態とし、制限時間初期値テーブル５６０から読み出したデッドラインまでの余裕時間の初期値をそのタスクの制限時間として設定した上で、時限優先スケジューリング機構６００を起動する。
【０００５】
そして、時間減算機構５１１，５１２，…は、制限時間・状態記憶機構５２１，５２２，…に設定された余裕時間を、例えばタスクの起動時や削除時のような所定の事象発生時に、タイマ機構９０のカウント値に基づいて所定の間隔分ずつ、デクリメントする。例えば、時間減算機構５１１，５１２，…は、それぞれ図８に示すように、タスクの起動要求やタスクの削除要求など、制限時間の更新の要求があった場合（Ｓ１１：ＹＥＳ）、制限時間テーブル５２０の制限時間・状態記憶機構５２１，５２２，…に登録されている各タスクの制限時間から、前回の制限時間の更新時のシステム時間から現在までのシステム時間の変化量（すなわち、前回の更新からの時間間隔）を差し引いて、新たな制限時間をそれぞれ求める（Ｓ１２）。そして、この新たな制限時間をそれぞれ制限時間・状態記憶機構５２１，５２２，…へ登録する（Ｓ１３）。なお、制限時間の値を無効に設定することが可能であり、制限時間が無効に設定されているタスクに関しては、この処理を行わない。
【０００６】
また、時限優先スケジューリング機構６００は、スケジューリング要求があった場合に、制限時間・状態記憶機構５２１、５２２、…の値をチェックして、起動状態にあるすべてのタスクの中でデッドラインまでの余裕時間（制限時間）が最も少ないタスクを次の実行タスクとするスケジューリング処理を行う。（この様子を図７では、タスクＡ６１０〜タスクＤ６４０，…で模式的に示している。例えばタスクＡ用制限時間・状態記憶機構５２１に記憶された余裕時間が制限時間テーブル５２０の制限時間・状態記憶機構５２１、５２２、…の中で最も小さい場合には、時限優先スケジューリング機構６００は、タスクＡ６１０を、ＣＰＵが実行すべきタスクとして決定する。そして、ＣＰＵは、時限優先スケジューリング機構６００によって決定されたタスクをディスパッチする。）
一方、ＣＰＵからタスクの終了要求が発生した場合、タスク削除機構５７０が、終了要求のあるタスクの制限時間・状態記憶機構５２１，５２２，…のデッドラインまでの余裕時間（制限時間）のデータを無効にし、タスクの状態を「終了」に更新した後、時限優先スケジューリング機構６００を起動する。そして、時限優先スケジューリング機構６００は、前述したスケジューリング処理を行う。
【０００７】
こうした従来のタスクスケジューリング装置の動作の具体例を図９に示して説明する。図９は、タイマ機構９０のカウントするシステム時間ｔの経過に伴って、各システム時間で発生したイベント（事象）の内容と、そのときの制限時間テーブル５２０の各タスクの制限時間のデータ（値）と、時限優先スケジューリング機構６００が決定した実行優先度との関係を示す図である。この例は、タスクＡ〜Ｄの４つのタスクについてスケジューリングを行う例である。なお、実行優先度の値は、「１」が最も優先度が高く、「２」「３」と続く。そして、時限優先スケジューリング機構６００は、実行優先度が最も高いタスク（すなわち実行優先度が「１」のタスク）をＣＰＵが次に実行すべきタスクとして決定する。また、制限時間初期値テーブル５６０に記憶された各タスクの制限時間の初期値は、図４に示すように、タスクＡについては３０、タスクＢは５０、タスクＣは２５、タスクＤは１５とする。
【０００８】
（１）図９のｔ＝０の行に示すように、タスクスケジューリング装置の初期状態として、タイマ機構９０のカウントするシステム時間ｔが０（ｔ＝０）の時、制限時間が存在し起動されているタスクは無いものとする。すなわち、制限時間・状態記憶機構５２１，５２２，５２３，５２４の制限時間の値は無効とする。図９では無効であることを斜線で示している。
【０００９】
（２）図９のｔ＝１０の行に示すように、システム時間ｔ＝１０で、タスクＡの起動要求が発生すると、タスク登録機構５５０は、タスクＡ用制限時間・状態記憶機構５２１へ、制限時間初期値テーブル５６０に記憶されたタスクＡの制限時間の初期値「３０」を記憶し、タスクＡの状態を起動状態として記憶する。なお、ここでは、前回更新時（ｔ＝０）からシステム時間が「１０」経過しているものの、タスクＢ〜Ｄの制限時間の値は「無効」であるので、図８に示した制限時間の減算は行わず、値は「無効」のままとなる。そしてこの時点で制限時間の更新があったものとする。
【００１０】
（３）図９のｔ＝２０の行に示すように、システム時間ｔ＝２０で、タスクＢの起動要求が発生すると、タスク登録機構５５０は、制限時間初期値テーブル５６０に記憶されたタスクＢの制限時間の初期値「５０」をタスクＢ用制限時間・状態記憶機構５２２の制限時間とし、タスクＢの状態を起動状態として記憶する。また、時間減算機構５１１は、図８に示した処理によって、新たな制限時間を制限時間テーブル５２０へ登録（記憶）する。すなわち、タスクＡの時間減算機構５１１は、前回更新時のシステム時間（ｔ＝１０）と現在のシステム時間（ｔ＝２０）との変化量（２０−１０＝１０）を、タスクＡ用制限時間・状態記憶機構５２１に記憶された値「３０」から差し引いて、新たな制限時間「２０」を求め、タスクＡ用制限時間・状態記憶機構５２１へ登録する。その結果、タスクＡの制限時間が２０，タスクＢの制限時間が５０となり、実行優先度が最も高いタスクは制限時間が最も小さいタスクＡと決定される。
【００１１】
（４）図９のｔ＝３０の行に示すように、システム時間ｔ＝３０で、タスクＣの起動要求が発生すると、タスク登録機構５５０は、制限時間初期値テーブル５６０に記憶されたタスクＣの制限時間の初期値「２５」をタスクＣ用制限時間・状態記憶機構５２３へ記憶し、時間減算機構５１１，５１２は、それぞれ、タスクＡ用制限時間・状態記憶機構５２１，タスクＢ用制限時間・状態記憶機構５２２に記憶された制限時間から、前回更新時からのシステム時間の変化量（３０ー２０＝１０）を差し引いて、新たな制限時間を求めて更新する。その結果、タスクＡの制限時間が１０，タスクＢの制限時間が４０，タスクＣの制限時間が２５となり、実行優先度が最も高いタスクはタスクＡと決定される。
【００１２】
（５）図９のｔ＝３５の行に示すように、システム時間ｔ＝３５で、タスクＡの終了要求が発生すると、タスク削除機構５７０は、タスクＡ用制限時間・状態記憶機構５２１の制限時間のデータを無効にし、タスクの状態を終了状態へ更新する。また、時間減算機構５１２，５１３は、それぞれ、タスクＢ用制限時間・状態記憶機構５２２，タスクＣ用制限時間・状態記憶機構５２３に記憶された制限時間から、前回更新時からのシステム時間の変化量（３５ー３０＝５）を差し引いて、新たな制限時間を求めて更新する。その結果、タスクＡの制限時間が無効，タスクＢの制限時間が３５，タスクＣの制限時間が２０となり、実行優先度が最も高いタスクはタスクＣと決定される。
【００１３】
（６）図９のｔ＝５０の行に示すように、システム時間ｔ＝５０で、タスクＤの起動要求が発生すると、タスク登録機構５５０は、制限時間初期値テーブル５６０に記憶されたタスクＤの制限時間の初期値「１５」をタスクＤ用制限時間・状態記憶機構５２４へ記憶し、時間減算機構５１２，５１３は、それぞれ、タスクＢ用制限時間・状態記憶機構５２２，タスクＣ用制限時間・状態記憶機構５２３に記憶された制限時間から、前回更新時からのシステム時間の変化量（５０ー３５＝１５）を差し引いて、新たな制限時間を求めて更新する。その結果、タスクＢの制限時間が２０，タスクＣの制限時間が５となり、実行優先度が最も高いタスクはタスクＣと決定される。
【００１４】
（７）システム時間ｔ＝５５では、図９のｔ＝５５の行に示すように、タスクＣ用制限時間・状態記憶機構５２３に記憶された制限時間が、０となりデッドラインに到達する。
（８）システム時間ｔ＝６０で、タスクＣの終了要求が発生すると、タスク削除機構５７０は、タスクＣ用制限時間・状態記憶機構５２３の制限時間のデータを無効にし、タスクの状態を「終了」に更新する。また、時間減算機構５１２，５１４は、それぞれ、タスクＢ用制限時間・状態記憶機構５２２，タスクＤ用制限時間・状態記憶機構５２４に記憶された制限時間から、前回更新時からのシステム時間の変化量（５５−６０＝５）を差し引いて、新たな制限時間を求めて更新する。その結果、タスクＡの制限時間が無効，タスクＢの制限時間が１０，タスクＤの制限時間が５となり、実行優先度が最も高いタスクはタスクＤと決定される。
【００１５】
【発明が解決しようとする課題】
このように従来のスケジューリング装置では、各タスク毎にそれぞれデッドラインまでの余裕時間を管理している。そのため、前述したタスクの起動要求時・タスクの終了要求時・デッドライン到達時などのスケジューリングの必要な事象発生毎に、時間減算機構５１１，５１２，…が、前回の制限時間の更新時からの時間間隔分の値を、制限時間・状態記憶機構５２１，５２２，…に保持された値から減算して更新する必要がある。
【００１６】
この更新の処理には「１タスクの制限時間・状態記憶機構の更新（設定されているデッドラインまでの余裕時間−所定の時間）×起動状態にあるタスク数」分の時間が必要であり、起動状態のタスクの数が増えるほどその処理時間が増加するという問題がある。
【００１７】
また、タスク毎にデッドラインまでの余裕時間を管理しているため、少なくとも同時に起動状態になり得るタスク数分だけ時間減算機構５１１，５１２，…が必要であり、タスクの数が増えるほど処理量（例えば回路規模、プログラムによる処理量など）が増加してしまうという問題がある。
【００１８】
そこで、本発明は、処理量を抑えることができるタスクスケジューリング装置等を提供することを目的とする。
【００１９】
【課題を解決するための手段及び発明の効果】
上述した問題点を解決するためになされた請求項１に記載のタスクスケジューリング装置は、タスクの起動要求時に、予め設定されたそのタスクのデッドラインまでの余裕時間の初期値と時間の経過に伴いカウントされるシステム時間とを加算して制限時間として保持しておく。そして、このように保持されたタスク毎の制限時間に基づいてスケジューリングを行う。
【００２０】
こうして、制限時間は、タスクの起動要求時のシステム時間を加算したものとして保持されるため、従来のように事象発生毎に制限時間保持手段に保持された制限時間を更新する必要がなくなる。そのため、従来のように制限時間を各タスク毎に減算するための時間減算機構を設ける必要がなくなる。よって、処理量の増加を抑えることができる。特にタスク数が増えるほど事象発生毎の処理量が増えるという問題を解決することが可能であり、事象発生毎の処理時間を一定にする事も容易にできる。
【００２１】
したがって、例えばタスクスケジューリング装置をハードウェアで構成する場合には、回路規模の増加を防ぐことができ、必要な回路面積を低減できる。またタスクスケジューリング装置をソフトウェア（プログラム）とコンピュータ（処理装置）で構成する場合にも処理量を削減することができ、処理時間を短縮できる。
【００２２】
こうしたスケジューリング手段によるスケジューリングの方法としては、例えば、請求項２に示すように、タスク毎の制限時間のうち、最も制限時間が小さいタスク（制限時間の厳しいタスク）から順に実行優先度の高いタスクとしたり、請求項３に示すように、タスク毎の制限時間のうち、制限時間の最も少ないタスクを次の実行タスクとしたり、請求項４に示すように、システム時間に最も近い制限時間を持つタスクを次の実行タスクとたりする方法をとることができる。また、請求項５に示すように、タスク毎にタスクの状態を保持しておき、このタスクの状態が、起動状態のタスクについてのみスケジューリングを行うようにしてもよい。例えば、いわゆる実行状態または実行可能状態のタスクを起動状態のタスクとすることができる。
【００２３】
ところで、システム時間や制限時間の最大値は有限であり、これらの時間は、例えば所定のサイズの記憶領域に保持することとなる。そのためこのサイズを超えると値がオーバーフローしてしまう。そこで、請求項６に示すように、保持されたタスク毎の制限時間と、システム時間に対し、所定の時間を減算することで、時間の更正をおこなうとよい。このようにすれば、これらの時間の最大値を超える前に、所定の時間を減算することによって、オーバーフローを防ぐことができる。
【００２４】
タスク毎の制限時間とシステム時間とは、異なる時点で更正するようにしてもよいが、請求項７に示すように、保持されたタスク毎の制限時間と、システム時間に対し、同時に時間の更正を行うとよい。このようにすれば、制限時間とシステム時間のずれを加味した処理等を行う必要がなくなって、処理が容易になり、例えば必要な回路規模や処理量などを減らすことが可能となる。
【００２５】
また、減算する所定の時間は例えば適応的に変化させるなどしてもよいが、請求項８に示すように、予め定めた時間を減算するとよい。また、請求項９に示すように、システム時間に対する更正時間と、前記タスクの制限時間に対する更正時間とを同じ値とするとよい。このようにすれば、更正を容易に行うことができ、例えば必要な回路規模や処理量などを減らすことが可能となる。
【００２６】
このような「減算する所定の時間」は、その値が大きければ大きいほど、次に更正するまでの時間間隔が長くなって更正の必要頻度を低くすることができ、更正のために費やす処理時間を減らすことができる。そこで、減算する所定の時間は、請求項１０に示すように、システム時間と各タスクの制限時間との中で最小の値とするとよい。
【００２７】
また、請求項１１に示すように、保持されたタスク毎の制限時間とシステム時間とに基づいてデッドライン違反を検知する手段を備えるとよい。例えば請求項１２に示すように、タスクの制限時間がシステム時間より小さくなった場合にデッドライン違反であると判定する。
【００２８】
なお、請求項１３は、請求項１のスケジューリング装置にて実現されるスケジューリング方法の請求項であり、このスケジューリング方法によれば、上述した請求項１の効果と同様の効果を奏する。同様にして、請求項２〜１２の構成に記載のスケジューリング方法を含む請求項を挙げることも可能である。
【００２９】
そして、請求項１〜１２に記載のタスクスケジューリング装置は、回路として実現してもよいし、コンピュータによって実行される処理として実現してもよい。
請求項１〜１２のいずれかに記載のタスクスケジューリング装置としての機能をコンピュータで実現する場合、請求項１４に示すように、例えば、コンピュータで起動するプログラムとして備えることができる。このようなプログラムの場合、例えば、フレキシブルディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ハードディスク、ＲＯＭ、ＲＡＭ等のコンピュータ読み取り可能な記録媒体に記録し、必要に応じてコンピュータシステムにロードして起動することにより用いることができ、また、ネットワークを介してロードして起動することにより用いることもできる。
【００３０】
【発明の実施の形態】
以下、本発明が適用された実施例について図面を用いて説明する。なお、本発明の実施の形態は、下記の実施例に何ら限定されることなく、本発明の技術的範囲に属する限り種々の形態を採りうることは言うまでもない。
【００３１】
図１は本実施例のタスクスケジューリング装置の構成を示すブロック図である。このタスクスケジューリング装置は、タスク毎の制限時間とタスクの状態を記憶する各タスク用制限時間・状態記憶機構（図１には、タスクＡ用制限時間・状態記憶機構２１〜タスクＤ用制限時間・状態記憶機構２４を図示している）を備える制限時間テーブル２０と、時間の経過とともに値をインクリメントすることでシステム時間を出力するタイマ機構９０と、各タスクの制限時間の初期値を記憶する制限時間初期値テーブル６０と、ＣＰＵからのタスク登録要求（例えばタスクの起動などの事象発生）に応じて、要求されたタスクの制限時間をタスクの状態とともに制限時間テーブル２０へ記憶させるタスク登録機構５０と、ＣＰＵからのタスク削除要求に応じて要求されたタスクの制限時間・状態記憶機構の制限時間を削除するタスク削除機構７０と、制限時間テーブル２０の中で最も制限時間が少ないタスクの制限時間とそのタスクの状態をＣＰＵに対して出力する時限優先スケジューリング機構１００とを備える。また、システム時間と制限時間テーブル２０の各タスク用制限時間・状態記憶機構に記憶された制限時間を更正する時間更正機構８０と、制限時間テーブル２０に記憶された制限時間とタイマ機構９０の値に基づいてデッドライン違反を検知するデッドライン違反検知機構２００を備える。
【００３２】
ＣＰＵから新たなタスクの起動要求が発生した場合、タスク登録機構５０によって、起動要求のあるタスクの制限時間の初期値を制限時間初期値テーブル６０から読み出し、時間加算機構１０はこの制限時間初期値とタイマ機構９０のシステム時間とを加算して、制限時間テーブル２０のそのタスク用の制限時間・状態記憶機構に登録する。そして、時限優先スケジューリング機構１００を起動し、時限優先スケジューリング機構１００は、制限時間テーブル２０の中の制限時間・状態記憶機構２１、２２、…の値をチェックし、起動状態にあるすべてのタスクの中で制限時間が最も少ないタスクを次の実行タスクとして出力する処理（スケジューリング処理）を行う。（図１には、この様子をタスクＡ１１０〜タスクＤ１４０，…で模式的に示している。例えばタスクＡの状態が起動状態であり、タスクＡ用制限時間・状態記憶機構２１に記憶された制限時間が制限時間テーブル２０の制限時間・状態記憶機構２１、２２、…の中で最も小さい場合には、時限優先スケジューリング機構１００は、タスクＡ１１０を、ＣＰＵが実行するタスクとして出力する。）
また、ＣＰＵからのタスクの終了要求が発生した場合、タスク削除機構７０は、終了要求のあるタスクの制限時間・状態記憶機構２１、２２、…の制限時間のデータを無効にし、タスクの状態を「終了」に更新した後、時限優先スケジューリング機構１００を起動して、前記同様にスケジューリング処理をする。この時、従来のように制限時間テーブル２０に登録されている起動状態のタスクに対して、制限時間のデータを更新する必要は無い。
【００３３】
ここで、システム時間がある一定以上の値になると、加算した値がオーバーフローしてしまい制限時間・状態記憶機構２１、２２、…に制限時間を登録できない状態が発生してしまう。そのため、時間更正機構８０は、オーバーフローしない範囲の所定のシステム時間において、タイマ機構９０のシステム時間と各タスクの制限時間・状態記憶機構２１、２２、…に格納されている制限時間とを、同じ値だけデクリメントする事により、時間の更正を行う。こうすることで、システム時間や制限時間のオーバーフローを防止することができる。
【００３４】
またデッドライン違反検知機構２００は、制限時間・状態記憶機構２１、２２、…に記憶された制限時間のデータからシステム時間を差し引くことでデッドラインまでの余裕時間を求める。そして、求めた値が０より大きい場合にはデッドラインに至っていないと判定し、０の場合にはデッドラインであると判定し、０より小さい場合にはデッドライン違反であると判定する。
【００３５】
ここで、さらに具体例を示して、このタスクスケジューリング装置の動作を説明する。
図４は、制限時間初期値テーブル６０に記憶された各タスクの制限時間の初期値を示す図である。図４に示すように、タスクＡについては制限時間の初期値として３０、タスクＢは５０、タスクＣは２５、タスクＤは１５がそれぞれ記憶されている。
【００３６】
図５は、システム時間ｔの経過に伴って、各システム時間で発生したイベントの内容と、そのときの制限時間テーブル２０の各タスクの制限時間のデータ（値）と、時限優先スケジューリング機構１００が決定した実行優先度との関係を示す図である。なお、実行優先度は値「１」が最も優先度が高く、「２」「３」と続く。そして、時限優先スケジューリング機構１００は、実行優先度が最も高い（すなわち実行優先度が「１」）のタスクをＣＰＵへ出力する。この図５に示した具体例は、従来の技術の欄で図９を参照して説明した従来例に対応する実施例である。
【００３７】
図６は、図５に示したイベント内容によるタスクの状態を時間軸（横軸）に沿って示した図であり、各システム時間におけるタスクの起動、タスクの終了、タスクのデッドライン、ＣＰＵによるタスクの実行状態、時間の構成要求の発生の様子を示している。こうしたタスクの起動の要求や終了の要求等のタスクの実行に伴う処理は、ＣＰＵにより行われる。
【００３８】
（１）システム時間ｔ＝０
タスクスケジューリング装置の初期状態として、図５のｔ＝０の行に示すように、タイマ機構９０のカウントするシステム時間ｔが０（ｔ＝０）で、制限時間が存在する起動されているタスクは無いものとする。そして時間更正機構８０によるタイマ機構及び制限時間の更正は、ｔ＝４０で行うものとする。
【００３９】
（２）システム時間ｔ＝１０
図５及び図６に示すように、ｔ＝１０でタスクＡの起動要求が発生した場合、時間加算機構１０は、図４に示した制限時間初期値テーブル６０に記憶されたタスクＡの制限時間初期値（静的に与えられるデッドラインまでの余裕時間）「３０」を、タスク登録機構５０を経由して取得する。同じく、システム時間「１０」をタイマ機構９０から取得する。そして、これら取得したタスクＡの制限時間初期値とシステム時間とを加算し（３０＋１０＝４０）、その加算結果の値「４０」を制限時間としてタスクＡ用制限時間・状態記憶機構２１へ記憶し、タスクＡの状態を起動状態として記憶する。
【００４０】
その結果、図５のｔ＝１０の行に示すように、制限時間テーブル２０は、タスクＡ用制限時間・状態記憶機構２１の制限時間のデータ＝４０，タスクＢ用制限時間・状態記憶機構２２の制限時間のデータ＝無し，タスクＣ用制限時間・状態記憶機構２３の制限時間のデータ＝無し，タスクＤ用制限時間・状態記憶機構（２４）の制限時間のデータ＝無しとなる。また、時間更正機構８０はｔ＝１０であるので、ここでは動作しない。
【００４１】
デッドライン違反検知機構２００は、システム時間ｔが「１０」、タスクＡの制限時間であるタスクＡ用制限時間・状態記憶機構２１の値が「４０」であることから、デッドラインまでの時間を「タスクＡ用制限時間・状態記憶機構の制限時間のデータ−システム時間」である「４０−１０＝３０」として求める。このようにデッドラインまでの余裕時間が「３０」であるのでデッドライン違反は発生していないと判定する。
【００４２】
時限優先スケジューリング機構１００は、各タスクの制限時間記憶機構の値をもとに、登録されているタスクのうち最も制限時間が少ない（すなわち、制限時間テーブル２０へ登録されている値が小さい）ものから順に実行優先度を高く設定し、最も実行優先度の高いタスクを、次の実行タスクとしてスケジューリングする。ｔ＝１０の時間においては、タスクＡのみが制限時間テーブル２０に記憶されているので、タスクＡの実行優先度を最も高い「１」とし、次の実行タスクは「タスクＡ」となる。
【００４３】
（３）システム時間ｔ＝２０
ｔ＝２０でタスクＢの起動要求が発生した場合、時間加算機構１０は、図４に示した制限時間初期値テーブル６０に記憶されたタスクＢの制限時間初期値「５０」をタスク登録機構５０を経由して取得する。同じく、システム時間「２０」をタイマ機構９０から取得し、タスクＢの制限時間初期値とシステム時間とを加算し（５０＋２０＝７０）、その結果である「７０」をタスクＢ用制限時間・状態記憶機構２２へ登録する。
【００４４】
その結果、図５のｔ＝２０の行に示すように、制限時間テーブル２０は、タスクＡ用制限時間・状態記憶機構２１の制限時間のデータ＝４０，タスクＢ用制限時間・状態記憶機構２２の制限時間のデータ＝７０，タスクＣ用制限時間・状態記憶機構２３の制限時間のデータ＝無し，タスクＤ用制限時間・状態記憶機構２４の制限時間のデータ＝無しとなる。また、時間更正機構８０はｔ＝２０であるので、ここでは動作しない。
【００４５】
デッドライン違反検知機構２００は、システム時間ｔが「２０」、タスクＡの制限時間はタスクＡ用制限時間・状態記憶機構２１より「４０」であることから、デッドラインまでの時間を「タスクＡ用制限時間・状態記憶機構の制限時間のデータ−システム時間」である「４０−２０＝２０」として求める。また同様に、タスクＢのデッドラインまでの時間は「７０−２０＝５０」と求める。したがって、タスクＡ，タスクＢの双方のデッドラインまでの余裕時間が０より大きいのでデッドライン違反はいずれのタスクでも発生していないと判定する。
【００４６】
時限優先スケジューリング機構１００は、制限時間テーブル２０に登録されているタスクＡの制限時間「４０」とタスクＢの制限時間「７０」を比較し、値の小さいタスクＡの実行優先度を「１」とし、タスクＢの実行優先度を「２」とする。そして、最も実行優先度の高いタスクＡを次の実行タスクとする。このように、タスクＢ起動後も引き続き実行タスクは「タスクＡ」であるためＣＰＵによるディスパッチは発生しない（図６参照）。
【００４７】
（４）システム時間ｔ＝３０
ｔ＝３０でタスクＣの起動要求が発生した場合、時間加算機構１０は、図４に示した制限時間初期値テーブル６０に記憶されたタスクＣの制限時間初期値「２５」をタスク登録機構５０を経由して取得する。同じく、システム時間「３０」をタイマ機構９０から取得し、タスクＣの制限時間初期値とシステム時間とを加算し（２５＋３０＝５５）、その結果である「５５」をタスクＣ用制限時間・状態記憶機構２３へ登録する。
【００４８】
その結果、図５のｔ＝３０の行に示すように、制限時間テーブル２０は、タスクＡ用制限時間・状態記憶機構２１の制限時間のデータ＝４０，タスクＢ用制限時間・状態記憶機構２２の制限時間のデータ＝７０，タスクＣ用制限時間・状態記憶機構２３の制限時間のデータ＝５５，タスクＤ用制限時間・状態記憶機構２４の制限時間のデータ＝無しとなる。また、時間更正機構８０はｔ＝３０であるので、ここでは動作しない。
【００４９】
デッドライン違反検知機構２００は、システム時間ｔが「３０」、タスクＡの制限時間はタスクＡ用制限時間・状態記憶機構２１より「４０」であることから、デッドラインまでの時間を「タスクＡ用制限時間・状態記憶機構の制限時間のデータ−システム時間」である「４０−３０＝１０」として求める。また同様にタスクＢのデッドラインまでの時間は「７０−３０＝４０」と求め、タスクＣのデッドライまでの時間は、「５５ー３０＝２５」と求める。したがって、タスクＡ〜Ｃのすべてについてデッドラインまでの余裕時間が０より大きいので、デッドライン違反はいずれのタスクでも発生していないと判定する。
【００５０】
時限優先スケジューリング機構１００は、制限時間テーブル２０に登録されているタスクＡの制限時間「４０」とタスクＢの制限時間「７０」、タスクＣの制限時間「５５」を比較し、最も制限時間の小さいタスクＡを最優先の実行優先度である「１」とし、続いてタスクＣの実行優先度を「２」として、タスクＤの実行優先度を「１」とする。そして、実行優先度が最も高いタスクＡを次の実行タスクとする。このように、これまでの実行タスクは「タスクＡ」であり、タスクＣ起動後も引き続き実行タスクは「タスクＡ」となったためＣＰＵによるディスパッチは発生しないが（図６参照）、実行の優先順位は「ｔ＝２０」の時と異なり、前述のように、優先度が高い方から「タスクＡ」「タスクＣ」「タスクＢ」となる。
【００５１】
（５）システム時間ｔ＝３５
そして、ｔ＝３５でタスクＡの終了要求が発生した場合、タスク削除機構７０は、終了要求のあるタスクＡ用制限時間・状態記憶機構２１の制限時間のデータを無効にし、タスクの状態を「終了」に更新する。このとき、時間更正機構８０はｔ＝３５であるので動作しない。
【００５２】
その結果、制限時間テーブル２０は、タスクＡ用制限時間・状態記憶機構２１の制限時間のデータ＝無し（データ削除後），タスクＢ用制限時間・状態記憶機構２２の制限時間のデータ＝７０，タスクＣ用制限時間・状態記憶機構２３の制限時間のデータ＝５５，タスクＤ用制限時間・状態記憶機構２４の制限時間のデータ＝無しとなる。
【００５３】
デッドライン違反検知機構２００は、システム時間ｔが「３５」、タスクＡの制限時間はタスクＡ用制限時間・状態記憶機構２１より「４０」（データ削除前）であることから、デッドラインまでの時間を「タスクＡ用制限時間・状態記憶機構の制限時間のデータ−システム時間」である「４０−３５＝５」として求める。こうして求めたデッドラインまでの余裕時間は０より大きいので、タスクＡはデッドライン違反を犯さず終了したと判定する。また、タスクＢのデッドラインまでの時間は「７０−３５＝３５」、タスクＣのデッドラインまでの時間は「５５−３５＝２０」と求められる。
【００５４】
時限優先スケジューリング機構１００は制限時間テーブル２０に登録されているタスクＢの制限時間「７０」、タスクＣの制限時間「５５」を比較し、値の小さいタスクＣから順に高い実行優先度を設定する。そして、最も実行優先度の高い（すなわち制限時間が最も小さい）タスクＣを次の実行タスクとする。このように、これまでの実行タスクは「タスクＡ」であり、タスクＡ終了後の実行タスクは「タスクＣ」と判定されたためＣＰＵはタスクＣのディスパッチを行う。そして実行の優先順位は、優先度が高い方から「タスクＣ」「タスクＢ」となる。
【００５５】
（６）システム時間ｔ＝４０（図５のｔ＝０※０）
ｔ＝４０（図５のｔ＝０※０）では時間の更正を行う。すなわち、時間更正機構８０が、制限時間テーブル２０の起動状態にあるタスクの制限時間のデータとシステム時間に対して、時間の更正を行う。つまり、各タスクの制限時間とシステム時間から所定の時間（ここでは「４０」）を減算する。
【００５６】
なお、このとき、更正できる時間の最大値は、システム時間と制限時間テーブル２０に登録されている各タスクの制限時間の中の最小値である。システム時間ｔ＝４０において、制限時間テーブル２０に登録されているデータはタスクＢが「７０」、タスクＣが「５５」であり、更正できる時間の最大値はシステム時間の「４０」となるのである。
【００５７】
更正をするには、システム時間、タスクＢ用制限時間・状態記憶機構２２の制限時間のデータ、タスクＣ用制限時間・状態記憶機構２３の制限時間のデータに対して更正する時間分「４０」だけ減算する。このように減算して更正すると、更正後はシステム時間「ｔ＝０」、タスクＢ用制限時間・状態記憶機構２２の制限時間のデータ「３０」、タスクＣ用制限時間・状態記憶機構２３の制限時間のデータ「１５」となる。
【００５８】
時間の更正においては、タスク間で制限時間のデータの値は変化するが、実行の優先順位（データの大小関係）は不変であるため時限優先スケジューリング機構１００を起動させる必要は無い。すなわち、ｔ＝４０において時間加算機構１０やデッドライン違反検知機構２００は、動作しない。
【００５９】
結果、図５のｔ＝０※０の行に示すように、制限時間テーブル２０は、タスクＡ用制限時間・状態記憶機構２１の制限時間のデータ＝無し，タスクＢ用制限時間・状態記憶機構２２の制限時間のデータ＝３０（更正後），タスクＣ用制限時間・状態記憶機構２３の制限時間のデータ＝１５（更正後），タスクＤ用制限時間・状態記憶機構２４の制限時間のデータ＝無しとなる。
【００６０】
このようにしてタイマ機構９０の時間ｔ＝４０において、時間の更正を行うことで、システム時間や制限時間のオーバーフローを防ぐことができる。
（７）システム時間ｔ＝１０※１（時間更正前の時間ではｔ＝５０）
そして、図５に示すように、ｔ＝１０※１（時間更正前の時間ではｔ＝５０）で、タスクＤの起動要求が発生した場合、時間加算機構１０は、図４に示した制限時間初期値テーブル６０に記憶されたタスクＤの制限時間初期値「１５」をタスク登録機構５０を経由して取得する。同じく、システム時間「１０」をタイマ機構９０から取得し、タスクＤの制限時間初期値とシステム時間を加算し（１５＋１０＝２５）、その結果である「２５」をタスクＤ用制限時間・状態記憶機構２４へ登録する。
【００６１】
その結果、図５のｔ＝１０※１の行に示すように、制限時間テーブル２０は、タスクＡ用制限時間・状態記憶機構２１の制限時間のデータ＝無し，タスクＢ用制限時間・状態記憶機構２２の制限時間のデータ＝３０，タスクＣ用制限時間・状態記憶機構２３の制限時間のデータ＝１５，タスクＤ用制限時間・状態記憶機構２４の制限時間のデータ＝２５となる。また、時間更正機構８０はｔ＝１０であるので、ここでは動作しない。
【００６２】
デッドライン違反検知機構２００は、システム時間ｔが「１０」、タスクＢの制限時間はタスクＢ用制限時間・状態記憶機構２２より「３０」であることから、デッドラインまでの時間は「タスクＢ用制限時間・状態記憶機構の制限時間のデータ−システム時間」である「３０−１０＝２０」と求める。また同様に、タスクＣのデッドラインまでの時間は「１５−１０＝５」、タスクＤのデッドラインまでの時間は「２５−１０＝１５」と求める。したがって、タスクＢ〜Ｃのすべてについてデッドラインまでの余裕時間が０より大きいので、デッドライン違反はいずれのタスクでも発生していないと判定する。
【００６３】
時限優先スケジューリング機構１００は、制限時間テーブル２０に登録されているタスクＢの制限時間「３０」（時間更正前のデータ「７０」に相当）とタスクＣの制限時間「１５」（時間更正前のデータ「５５」に相当）とを比較し、値の小さいタスクＣの方が制限時間が小さいと判断して、タスクＣを次の実行タスクとする。これまでの実行タスクは「タスクＣ」であり、タスクＤ起動後も実行タスクは「タスクＣ」であるためＣＰＵによるディスパッチは発生しない。しかし、実行の優先順位はｔ＝０（時間更正前の時間ではｔ＝４０）の時と異なり、優先度が高い方から「タスクＣ」「タスクＤ」「タスクＢ」となる。
【００６４】
（８）システム時間ｔ＝１５※１（時間更正前の時間ではｔ＝５５）
ｔ＝１５※２（時間更正前の時間ではｔ＝５５）では、デッドライン違反検知機構２００は、システム時間がｔ＝１５、タスクＣの制限時間は「１５」であり、「タスクＣ用制限時間・状態記憶機構の制限時間のデータ−システム時間」は「１５−１５＝０」であることから、デッドラインに達したことを検知する。なお、タスクＢのデッドラインまでの時間は「３０−１５＝１５」、タスクＤのデッドラインまでの時間は「２５−１５＝１０」である。ここでは、時間加算機構１０，時間更正機構８０は、動作せず、制限時間テーブル２０は、タスクＡ用制限時間・状態記憶機構２１の制限時間のデータ＝無し，タスクＢ用制限時間・状態記憶機構２２の制限時間のデータ＝３０，タスクＣ用制限時間・状態記憶機構２３の制限時間のデータ＝１５，タスクＤ用制限時間・状態記憶機構２４の制限時間のデータ＝２５のままとなる。
【００６５】
このようにして、デッドライン違反検知機構２００により、タスクＣがデッドラインに到達したことが検知される。このように検知された情報をもとに、ＣＰＵは、タスクＣを終了する等の処理をするなど、デッドライン違反時の処理を行うことができる。
【００６６】
（９）システム時間ｔ＝２０※２（時間更正前の時間ではｔ＝６０）
そして、図５に示すように、タイマ機構９０の時間ｔ＝２０※２（時間更正前の時間ではｔ＝６０）において、タスクＣの終了要求があった場合、タスク削除機構７０がタスクＣ用制限時間・状態記憶機構２３のデータ（この場合はタスクＣの制限時間「１５」）を削除して、状態を「終了」にする。そして、時限優先スケジューリング機構１００を起動する。ここで、時限優先スケジューリング機構１００は制限時間テーブル２０に登録されているタスクＢの制限時間「３０」、タスクＤの制限時間「２５」を比較し、値の小さいタスクＤを次の実行タスクとする。これまでの実行タスクは「タスクＣ」であり、タスクＣ終了後の実行タスクは「タスクＤ」となったためＣＰＵによるディスパッチが発生する（図６参照）。そして実行の優先順位は、優先度が高い方から「タスクＤ」「タスクＢ」となる。
【００６７】
なお、ここでは時間加算機構１０，時間更正機構８０は、動作せず、制限時間テーブル２０は、タスクＡ用制限時間・状態記憶機構２１の制限時間のデータ＝無し，タスクＢ用制限時間・状態記憶機構２２の制限時間のデータ＝３０，タスクＣ用制限時間・状態記憶機構２３の制限時間のデータ＝無し（データ削除後），タスクＤ用制限時間・状態記憶機構２４の制限時間のデータ＝２５となる。
【００６８】
そして、デッドライン違反検知機構２００は、システム時間「ｔ＝２０」、タスクＣの制限時間は「１５」（データ削除前）であり、デッドラインまでの時間は「タスクＣ用制限時間・状態記憶機構の制限時間のデータ−システム時間」である「１５−２０＝−５」であり、タスクＣについてデッドライン違反が発生したことを検知する。
【００６９】
以上が、具体例の説明である。
このように本実施例のスケジューリング装置は、タスク起動要求時（例えば図５のｔ＝１０，２０，３０など）に、その時点のタイマ機構９０のカウントするシステム時間と、制限時間初期値テーブル６０に記憶された余裕時間の初期値とを加算して、制限時間テーブル２０へ記憶（登録）する。そして、この記憶された値は、時間の更正時（例えば図５のｔ＝４０）以外には、そのまま保持され、従来の図９に示した減算は行わない。
【００７０】
すなわち、従来は、図９に示したように、タスク毎にデッドラインまでの余裕時間を制限時間テーブルで管理していたのに対し、本実施例では、図５に示したように、全てのタスクで共通のシステム時間を加算した値として制限時間を管理する。これにより、全てのタスクで１つの時間管理で済むこととなり、制限時間の更新をスケジューリング要求毎に行う必要も無くなる。そのため、従来のように制限時間を各タスク毎に減算するための時間減算機構を設ける必要がなくなる。よって、処理量の増加を抑えることができる。特に従来の構成におけるタスク数が増えるほど処理量が増えるという問題を解決することが可能となり、処理時間を一定にする事も容易にできる。
【００７１】
なお、図１のタスクスケジューリング装置は、ハードウェア（電子回路）として構成することも、ソフトウェア（プログラム）とコンピュータで構成することもできる。ハードウェアで構成する場合には、回路規模の増加を防ぐことができ、必要な回路面積を低減できる。ソフトウェア（プログラム）で構成する場合には、コンピュータでの処理量を削減することができ、処理時間を短縮できる。
【００７２】
例えば、回路規模に関しては、従来技術では、減算機構である時間減算機構５１１、５１２、…がタスク数分必要であるのに対し、本実施例では、加算機構である時間加算機構１０が全てのタスクに対して１つと、システム時間の更正をする時間更正機構８０が１つ必要なだけである。例えば時間更正機構８０は、制限時間テーブル２０に記憶された制限時間とタイマ機構９０のカウントするシステム時間の中のすべてのものについて、予め定められたビットがセットされたことを検知した場合に、これらすべての時間についてそのビットをリセットすることにより、時間を更正するように構成するとよい。このようにすれば、従来のような減算機構による任意の時間の減算を行うための回路に比べ、大幅に回路規模を削減することができる。また、処理時間に関しては、従来技術ではスケジューリングのためのデッドラインまでの余裕時間の計算量は「起動しているタスク数×減算時間×スケジューリング要求数」であり、本実施例では、タスク起動時のみその起動したタスクに対してだけ処理をすればよいため「起動しているタスク数×加算時間＋更新時間」だけでよい。以上のように、タスクスケジューリング装置の処理量を低減でき、高速化を実現できる。
【００７３】
なお、時限優先スケジューリング機構１００で判定される実行優先度はＣＰＵから参照可能とするとよい。また、時限優先スケジューリング機構１００では、実行優先度は求めずに単に最も制限時間の短いタスクを次に実行するタスクとして決定してもよい。
【００７４】
また、本実施例では、制限時間テーブル２０に各タスクの制限時間と、状態とを記憶することとしたが、その他のタスク関連情報を記憶するようにしてもよい。例えば、タスクコントロールブロック（ＴＣＢ）を記憶するようにしてもよい。
【図面の簡単な説明】
【図１】実施例のタスクスケジューリング装置の構成を示すブロック図である。
【図２】時間加算機構の処理の流れを示すフローチャートである。
【図３】時間更正機構の処理の流れを示すフローチャートである。
【図４】制限時間初期値テーブルに記憶されたタスクの制限時間初期値を示す説明図である。
【図５】実施例における、各システム時間で発生したイベントの内容と各タスクの制限時間のデータと実行優先度との関係を示す説明図である。
【図６】図５に示したイベント内容によるタスクの状態を時間軸に沿って示した説明図である。
【図７】従来技術におけるタスクスケジューリング装置の構成を示すブロック図である。
【図８】従来技術におけるタスクスケジューリング装置の時間減算機構の処理の流れを示すフローチャートである。
【図９】従来の技術における、各システム時間で発生したイベントの内容と各タスクの制限時間のデータと実行優先度との関係を示す説明図である。
【符号の説明】
１０…時間加算機構
２０…制限時間テーブル
２１…タスクＡ用制限時間・状態記憶機構
２２…タスクＢ用制限時間・状態記憶機構
２３…タスクＣ用制限時間・状態記憶機構
２４…タスクＤ用制限時間・状態記憶機構
５０…タスク登録機構
６０…制限時間初期値テーブル
７０…タスク削除機構
８０…時間更正機構
９０…タイマ機構
１００…時限優先スケジューリング機構
２００…デッドライン違反検知機構
５１１，５１２，５１３，５１４…時間減算機構
５２０…制限時間テーブル
５２１…タスクＡ用制限時間・状態記憶機構
５２２…タスクＢ用制限時間・状態記憶機構
５２３…タスクＣ用制限時間・状態記憶機構
５２４…タスクＤ用制限時間・状態記憶機構
５５０…タスク登録機構
５６０…制限時間初期値テーブル
５７０…タスク削除機構
６００…時限優先スケジューリング機構
【図１】
2004070579.tif 000003
【図２】
2004070579.tif 000004
【図３】
2004070579.tif 000005
【図４】
2004070579.tif 000006
【図５】
2004070579.tif 000007
【図６】
2004070579.tif 000008
【図７】
2004070579.tif 000009
【図８】
2004070579.tif 000010
【図９】
2004070579.tif 000011