(57)【特許請求の範囲】
【請求項１】
タスク情報としてタスクＩＤを用いてタスクの状態を管理するタスク管理装置において、
前記タスク情報は、前記タスクＩＤにさらにタグ情報を付加し、
前記タグ情報は、当該タスクＩＤのタスクが現在属する待ち行列の種別を示す待ち行列種別情報を付加した情報であり、
前記タスク情報を記憶する複数のタスク情報記憶領域を備えるタスク情報記憶手段と、
前記タスク情報記憶手段に外部から指定されたタスク情報を挿入するタスク情報挿入手段と、
前記タスク情報記憶手段に記憶されたタスク情報群から、外部から指定されたタスクＩＤを持つタスク情報を削除するタスク情報削除手段と、
前記タスク情報記憶手段に記憶されたタスク情報群のうち、外部から指定されたタグ情報を持つタスク情報群の中から先頭タスクに該当するタスクＩＤを読み出すための先頭タスク情報読み出し手段とを備え、
前記タスク情報挿入手段は、外部から指定されたタスク情報のタグ情報と前記タスク情報記憶手段に記憶されたタグ情報とを比較することによって前記指定されたタスク情報を挿入すべき前記タスク情報記憶領域を決定し、
前記タスク情報削除手段は、外部から指定されたタスクＩＤと前記タスク情報記憶手段に記憶されたタスクＩＤの一致を判定することで、削除すべきタスクＩＤが記憶されたタスク情報記憶領域を決定し、
前記先頭タスク情報読み出し手段は、前記指定されたタグ情報と、前記タスク情報記憶手段に記憶されたタグ情報とを比較判定することで、読み出すべきタスクＩＤが記憶されたタスク情報記憶領域を決定すること
を特徴とするタスク管理装置。
【請求項２】
請求項１に記載のタスク管理装置において、
前記タスク情報記憶手段は、タスク情報をタスク情報列として記憶し、記憶された各タスク情報は、隣接するタスク情報記憶領域に移動可能であること
を特徴とするタスク管理装置。
【請求項３】
請求項２に記載のタスク管理装置において、
前記タスク情報削除手段は、削除すべきタスクＩＤが記憶されたタスク情報記憶領域である削除領域に隣接するいずれか一方の側のタスク情報列を、前記削除領域が位置する方向に前記削除領域分移動して、前記削除領域に記憶されたタスク情報を削除すること
を特徴とするタスク管理装置。
【請求項４】
請求項２または３に記載のタスク管理装置において、
前記タスク情報挿入手段は、前記指定されたタスク情報を挿入すべきタスク情報記憶領域である挿入領域に記憶されたタスク情報を先頭とするタスク情報列を、該タスク情報列の末尾方向に前記挿入領域分移動して、前記指定されたタスク情報を前記挿入領域に挿入すること
を特徴とするタスク管理装置。
【請求項５】
請求項２〜４のいずれかに記載のタスク管理装置において、
前記タスク情報記憶手段における前記タスク情報列は、列内でタグ情報が昇べきあるいは降べきの順になるようにタスク情報の順序を整列していること
を特徴とするタスク管理装置。
【請求項６】
請求項２〜５に記載のタスク管理装置において、
前記タスク情報記憶手段における前記タスク情報列は、同一の待ち行列種別情報を持つタスク情報を先頭側あるいは後尾側から挿入順に整列していること
を特徴とするタスク管理装置。
【請求項７】
請求項２〜６に記載のタスク管理装置において、
前記タスク情報挿入手段は、前記タスク情報列として記憶されたタスク情報のタグ情報と、前記指定されたタスク情報のタグ情報とを、前記タスク情報列の前方あるいは後方のいずれか一方から比較した場合に、記憶されたタスク情報のタグ情報の値の方が大きくなった位置のタスク情報記憶領域に挿入すること
を特徴とするタスク管理装置。
【請求項８】
請求項１〜７のいずれかに記載のタスク管理装置において、
前記タグ情報として、さらに、タスクの優先順位情報を含み、
前記先頭タスク読み出し手段は、前記優先順位情報を加味して読み出すこと
を特徴とするタスク管理装置。
【請求項９】
請求項１〜８のいずれかに記載のタスク管理装置において、
前記タグ情報は、タスクが現在属する待ち行列種別情報をビット表現したものを上位側に、タスクの優先順位情報をビット表現したものを下位側に配置し連接した情報とすること
を特徴とするタスク管理装置。
【請求項１０】
請求項９に記載のタスク管理装置において、
前記タスクの優先順位情報として、優先順位が高いもの程、値が大きく割り当てられる場合には、前記タスク情報記憶手段におけるタスク情報を前記タグ値の降べきの順に整列すること
を特徴とするタスク管理装置。
【請求項１１】
請求項９に記載のタスク管理装置において、
前記タスクの優先順位情報として、優先順位が高いもの程、値が小さく割り当てられる場合には、前記タスク情報記憶手段におけるタスク情報を前記タグ値の昇べきの順に整列すること
を特徴とするタスク管理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はタスク管理装置に関する。
【０００２】
【従来の技術】
従来から、家電製品、産業機器等の制御用として組込みＣＰＵが利用されている。近年、そのような製品の機能の多様化に伴い１つのＣＰＵで複数のプログラムを並列動作させることが必要とされている。また製品の機能の多様化、大規模化に伴いＣＰＵに搭載するプログラムの規模が大きくなり、ソフトウェアの生産性、保守性の向上も必要とされている。
【０００３】
一般に、リアルタイムＯＳは、プログラムをいくつかの小さい仕事の単位であるタスクとして細分化するとともに、タスク間の関係、タスクと入出力（外部システム）との関係を明確にし、その関係に基づいて各タスクの動作を管理することにより複数のプログラムの並列動作（マルチタスキング）を可能としている。また、こうすることで、タスク単位でプログラム開発が可能となる為、生産性と保守性の向上が可能となる。
【０００４】
こうしたリアルタイムＯＳは、１つしかないＣＰＵに対して、実行が要求される複数のタスクの中から、個々のタスクが持つ優先順位、もしくは待ち時間等を評価することによりどれか１つのタスクを選択し、ＣＰＵに割り当てる。また時間および外部システムからの入力等をタスク切換えの要因（事象）とし、新たに事象が発生する毎に優先順位や待ち時間等の再評価を行って、次に実行するタスクを決定する。このような処理を行うことにより各々のタスクに対してＣＰＵ割当て時間を分配し、マルチタスキングを実現している。
【０００５】
図１７（ａ）は一般的なリアルタイムＯＳにおけるタスクの状態遷移図を示したものである。リアルタイムＯＳにより管理されるすべてのタスクは、この状態遷移図上をすごろくのコマのように遷移する。初期状態としてすべてのタスクは休止状態に位置し、プログラムより実行が要求されたタスクは実行可能状態へと遷移する。複数のタスクが実行可能状態に位置する場合は、各タスクに割り当てられた優先順位及び各タスクの実行可能状態における待ち時間等を基にして、実行待ち行列を生成し、実行待ち行列の先頭に位置するタスクのみが実行状態へと遷移し、ＣＰＵで実行される。実行されているタスクは、現在実行しているプログラムを継続するために必要な資源、条件が不足している等の理由により事象待ち状態へと遷移する場合がある。事象待ち状態においては、待ちの対象となるセマフォ、イベントフラグ等の事象毎に、該当タスクに割り当てられた優先順位や、対象となる事象における待ち時間等を基にして、待ち行列を生成する。実行タスク及び外部との入出力によって、ある事象に変化が生じた場合は、その事象に対する待ち行列の先頭から、各タスクの待ち行列抜けを評価し、待ち行列抜けと判定されたタスクに関しては実行可能状態へと遷移する。
【０００６】
なお、前記待ち行列をソフトウェアで構成した場合は図１７（ｂ）に示すようなリスト構造となり、各ノードは次のノードのアドレスとタスクＩＤの情報を持ち、先頭のアドレスから次ノードアドレスをトレースすることにより、タスクＩＤの待ち行列を探索することが可能となる。また、ハードウェアで構成した場合は、図１７（ｃ）に示すように記憶素子を連続して配置し、書き込みポインタに従って先頭からタスクＩＤを格納することによりタスクＩＤの待ち行列を形成することが可能となる。上記のようにリアルタイムＯＳはすべてのタスクの状態を図１７（ａ）に示す状態遷移図に従って、また実行可能状態、待ち状態に関しては図１７（ｂ）、図１７（ｃ）に示すような待ち行列を生成することによりマルチタスキングを実現している。
【０００７】
【発明が解決しようとする課題】
しかしながら、自動車制御、ロボット制御といった高速性が要求される分野に関してはリアルタイムＯＳでタスク制御を行うことによりシステム応答が低下し、仕様を満たすことが困難になる場合がある為、そのような分野に関してはリアルタイムＯＳの導入が遅れている。また、多機能、大規模なシステムにおいては、リアルタイムＯＳで管理しなければならないタスク数、入出力数が増えることにより、リアルタイムＯＳの処理に費やす時間が増大し、リアルタイムＯＳ処理実行のためのＣＰＵ占有時間が問題となりつつある。そのような問題を解決するために、リアルタイムＯＳをハードウェア化し、処理速度の高速化を図る取り組みが成されている。
【０００８】
しかしながら、リアルタイムＯＳをハードウェア化した場合にゲート等で費やされる面積は、従来のソフトウェアでのリアルタイムＯＳにおけるＲＯＭ、ＲＡＭの占める面積に対して数倍以上費やされる為、高速応答に加えて、低コストも重要視される組込みＣＰＵへハードウェア化したリアルタイムＯＳを適用することは難しいとされていた。
【０００９】
リアルタイムＯＳのハードウェア規模を増大させる原因の１つとして、待ち行列をＦ／Ｆ等の順序回路で構成することがあげられる。このような待ち行列は従来のソフトウェアではＲＡＭを用いて、前記図１７（ｂ）のようなリスト構造で構成されていた。しかし、このようなリスト構造を基に待ち行列の探索を行うと、先頭のノードからシーケンシャルに次のノードをたどる為、所望のタスクが格納されたノードに到達するまでに時間を費やし、このような待ち行列探索手法がソフトウェアによるリアルタイムＯＳの応答速度を遅くする原因の１つであった。
【００１０】
ハードウエアにおいては、図１７（ｃ）のように待ち行列をＦ／Ｆ等の順序回路を用いて構成し、すべての順序回路の内容に対して同時にアクセスできる為、待ち行列の探索をすべての順序回路に対してパラレルに実行することが可能となり、これにより待ち行列探索の高速化を図ることができる。一方、ＲＡＭと同等の情報量を持つ待ち行列をＦ／Ｆ等の順序回路を用いて構成する為に、ソフトウェアに対してハードウェアの規模は増大する。また、待ち行列の大きさとしては、すべてのタスクが１つの待ち行列上に配置される場合も起こりうる為、実行待ち行列、セマフォ待ち行列等のすべての待ち行列がタスク数分の格納領域を用意しなければならない。待ち行列の格納領域サイズ、待ち行列数を決定するタスク数、セマフォ、イベントフラグ等の事象数は適用するシステムが大規模化、多機能化すればするほど増える傾向にあり、それに応じてハードウェア規模はますます増大することとなる。
【００１１】
本発明は、上述の問題点を解決するべく成されたもので、リアルタイムＯＳのハードウェア化の際に、タスク管理装置のハードウェア規模を削減することを目的とする。
【００１２】
【課題を解決するための手段及び発明の効果】
上述した問題点を解決するためになされた請求項１に記載のタスク管理装置によれば、タスクＩＤと共にタグ情報として待ち行列種別情報をタスク情報記憶領域に記憶する。そして、タスク情報記憶手段は、このタスク情報記憶領域を複数備える。
【００１３】
ここでタスクＩＤは、それぞれのタスクを識別することが可能な情報であり、例えば、タスク番号やタスク名などである。また、待ち行列種別情報は、例えば、実行待ち行列、セマフォ待ち行列、イベントフラグ待ち行列、タイマ待ち行列等の各待ち行列の種別を区別可能な情報であり、例えば、各待ち行列種別毎に異なる待ち行列種別番号を用いる。
【００１４】
このようなタスク情報記憶手段に対しては、タスク情報の挿入、削除、各待ち行列種別毎の先頭タスクＩＤの読み出しを行うことができる。タスク情報の挿入は、外部から指定されたタスク情報のタグ情報とタスク情報記憶手段に記憶されたタグ情報とを比較することによってタスク情報を挿入すべきタスク情報記憶領域を決定して行う。また、タスク情報の削除は、外部から指定されたタスクＩＤとタスク情報記憶手段に記憶されたタスクＩＤの一致を判定することで削除すべき位置のタスク情報記憶領域を決定して行う。なお、「外部から指定された」とは、例えば、オペレーティングシステムによって指定されることをいう。したがって、例えば、オペレーティングシステムは、挿入するタスク情報を指定するだけで、タスク情報記憶手段にタスク情報を挿入することができ、削除したいタスクＩＤを指定するだけでそのタスクＩＤのタスク情報をタスク記憶手段から削除することができる。
【００１５】
先頭タスク情報読み出し手段は、タスク情報記憶手段に記憶されたタスク情報群のうち、指定されたタグ情報を持つタスク情報群の中から先頭タスクに該当するタスクＩＤを読み出す。具体的には、指定されたタグ情報と、タスク情報記憶手段に記憶されたタグ情報とを比較判定することで、先頭タスク情報が記憶された位置のタスク情報記憶領域を決定して読み出す。このようにすれば、オペレーティングシステムは、読み出したいタスクのタグ情報を指定するだけで、タスク情報記憶手段から先頭タスクに該当するタスクＩＤを読み出すことができる。例えば、オペレーティングシステムが実行待ち行列の先頭タスク情報を読み出す場合には、実行待ち行列の待ち行列種別番号を指定することで、実行待ち行列の先頭のタスクに該当するタスクＩＤを読み出すことができる。つまり、待ち行列種別毎に別々にタスク情報を記憶するための待ち行列を用意する従来の場合と同様に、各待ち行列種別情報毎にそれぞれの先頭タスク情報を読み出すことができる。
【００１６】
このように、タスク情報記憶手段にタスクＩＤとタグ情報としての待ち行列種別情報とを共に記憶することで、待ち行列種別毎にタスクＩＤを記憶する記憶手段を備える必要がなくなる。例えば、実行待ち行列と、セマフォ待ち行列と、イベントフラグ待ち行列の３つの待ち行列を使用する場合には、従来は、これら３つの待ち行列分の記憶領域を用意する必要があったが、このようにすれば、１つの分の記憶領域を用意するだけでよい。また、１つの状態にすべてのタスクが存在する場合がありうるため、１つの待ち行列に、すべてのタスクのタスクＩＤが入る可能性がある。つまり、ｎ個のタスクが実行される可能性があれば、これら３つの待ち行列のそれぞれがｎ個のタスクＩＤを記憶するための記憶領域を持つ必要があった。しかし、このようにすればｎ個のタスク情報記憶領域をもつタスク情報記憶手段を１つ用意するだけでよい。
【００１７】
つまり、各待ち行列種別毎にタスク数分の記憶領域を持つ必要がなくなり、Ｆ／Ｆ（フリップフロップ）等の順序回路のハードウェア規模を削減することができる。特に待ち行列（状態・事象）の数が多い場合にはこの効果が増大する。
なお、このようにすることで、タスク情報挿入手段、タスク情報削除手段、先頭タスク読み出し手段のハードウェアは、従来と比べて複雑になる可能性もあるが、このような制御手段の規模の増加量よりも、記憶領域を構成するハードウェア規模の削減量の方が大きくなるため、全体の回路規模は従来より小さくすることができる。
【００１８】
しかし、タスク情報挿入手段、タスク情報削除手段、先頭タスク読み出し手段のハードウェアもできるだけ小さな規模で構成することが望ましい。そこで、請求項２に示すように、タスク情報記憶手段はタスク情報をタスク情報列として記憶するとよい。タスク情報列として記憶するとは、タスク情報をリスト状（待ち行列状）に記憶することをいう。そして、このリスト状に記憶されたタスク情報をタスク情報列とよぶ。
【００１９】
このようにすれば、タスク情報記憶手段に記憶されるタスク情報群は、タスクＩＤとタグ情報からなるタスク情報の列として扱うことができる。そのため、管理が単純になりハードウェア規模を相対的に小さくできる。
また、タスク情報列に記憶された各タスク情報は、それぞれのそのタスク情報が記憶されたタスク情報記憶領域に隣接するタスク情報記憶領域に移動することができる。よって、請求項３のようにすれば、削除すべきタスク情報が記憶されたタスク情報記憶領域（以下、削除領域とも称す）が位置する方向（つまり、削除すべきタスク情報記憶領域を埋める方向）に、削除領域に隣接するいずれか一方の側のタスク情報列を、削除領域分移動するだけで、指定されたタスクＩＤのタスク情報（即ち、削除すべきタスク情報）を削除することができる。この削除の様子を、例えば、タスク情報記憶領域に先頭から、１，２，３，４，５，６と番号を付けて説明すると、１〜４のタスク情報記憶領域にタスク情報が記憶されており、２に記憶されたタスク情報を削除する場合には、３に記憶されたタスク情報を２に移動し、４に記憶されたタスク情報を３に移動することで２のタスク情報を削除することができる。つまり、３，４に記憶されたタスク情報列を、削除すべきタスク情報記憶領域である２を埋める方向に移動して削除する。なお、この場合、３，４，５，６に記憶されたタスク情報列を移動してもよい。この場合、６にはタスク情報は無効である旨のタスク情報を入れるようにしておけばよい。
【００２０】
また、請求項４のようにすれば、指定されたタスク情報を挿入すべきタスク情報記憶領域（以下、挿入領域とも称す）に記憶されたタスク情報を先頭とするタスク情報列を、そのタスク情報列の末尾方向（つまり、挿入すべき位置を空ける方向）に、挿入領域分移動して、指定されたタスク情報を挿入領域に挿入することができる。例えば、指定されたタスク情報を前述の３に挿入する場合には、４に記憶されたタスク情報を５に移動し、３に記憶されたタスク情報を４に移動して３を空けることでこの３に挿入する。つまり、３，４に記憶されたタスク情報列を挿入すべきタスク情報記憶領域である３を空ける方向に移動して削除する。このように、タスク情報の列として管理することで、挿入が容易にできる。
【００２１】
このようにすれば、単に隣接するタスク情報記憶領域間でタスク情報を移動するだけで挿入、削除を行うことができるため、相対的にハードウェア規模を小さくすることができる。
なお、このようにタスク情報列としてタスク情報記憶手段に記憶する場合には、そのタスク情報列は、請求項５に示すようにタグ情報が昇べきあるいは降べきの順になるように整列しているとよい。このようにすれば、同一のタグ情報を持つタスク情報がタスク情報記憶手段内でまとまって記憶されることとなり管理がしやすい。また、隣接するタスク情報記憶領域でタグ情報が異なる位置を見つけることで、タスク情報記憶手段内での待ち行列種別の変化点が分かる。この変化点間は同一のタグ情報であることがわかり管理がしやすい。
【００２２】
また、請求項６に示すように、同一の待ち行列種別情報を持つタスク情報を先頭側あるいは後尾側から挿入順に整列しているとよい。このようにすれば、先頭側から挿入順に整列されている場合には、先頭タスク情報読み出し手段は、同一の待ち行列種別情報を持つタスク情報群の中から先頭のものを読み出すだけでよい。後尾側から順に整列されている場合であれば、先頭タスク情報読み出し手段は、同一の待ち行列種別情報を持つタスク情報群の中から後尾のものを読み出すだけでよい。このように、先頭タスクの位置が容易に決定できるためハードウェア規模を削減することができる。
【００２３】
なお、請求項５及び請求項６のように整列させるためには、タスク情報記憶手段の内容をソートして整列してもよいが、請求項７のように、タスク情報挿入手段を構成するとタスク情報列内でこのように整列させることができる。すなわち、タスク情報挿入手段は、タスク情報列として記憶されたタスク情報のタグ情報と、指定されたタスク情報のタグ情報とを、タスク情報列の前方あるいは後方のいずれか一方から比較した場合に、記憶されたタスク情報のタグ情報の値の方が大きくなった位置のタスク情報記憶領域に挿入する。
【００２４】
このようにすれば、前方から比較した場合には、タグ情報の昇べきの順にタスク情報が記憶され、後方から比較した場合には、タグ情報の降べきの順にタスク情報が記憶される。例えば、前方から比較した場合の例として、タスク情報記憶手段に１，２，２，３，４，４というタグ情報を持つタスク情報列が記憶されている場合に、タグ情報が２のタスク情報を挿入すると、３の位置に挿入される。すなわち、１，２，２，３，３，４，４となり後側の３が挿入されたタスク情報の位置となる。この例からも分かるように、タスク情報記憶手段には、タグ情報の昇べきの順にタスク情報が順に記憶され、さらに、同一のタグ情報を持つタスク情報は、到着順（挿入順）に先頭方向から記憶されることになる。なお、上述の例で例えばタグ情報が５以上のタスク情報を挿入する場合には最後尾に挿入すればよい。そのため、最後尾にはタグ情報の最大値を入れておくとよい。
【００２５】
同様に、後方から比較した場合には、タスク情報記憶手段には、タスク情報がタグ情報の降べきの順に記憶され、さらに、同一のタグ情報を持つタスク情報間では、後尾方向から到着順（挿入順）に記憶されることになる。
また、このようにタスク情報を挿入すれば、同一のタグ情報を持つタスク情報は挿入順に整列されることとなるため、タグ情報を比較して先頭タスク情報を読み出す際に、待ち行列種別情報が一致するタスク情報列のうち先頭のタスク記憶領域を読み出せばよいことになり、タスク情報の管理が容易になる。そのため、さらに相対的に少ないハードウェア規模でタスクの挿入を容易に行うことができる。
【００２６】
以上のように、タスクＩＤと共にタグ情報として待ち行列種別情報をタスク情報記憶手段に記憶することでFCFS(First Come First Service)による待ち行列群を従来と比べて少ないハードウェア規模で実現することができる。
そしてさらに、請求項８に示すように、タグ情報として待ち行列種別情報に加え、タスクの優先順位情報を含み、先頭タスク読み出し手段はその優先順位情報を加味して先頭タスク情報を読み出すとよい。このようにすれば、各待ち行列種別毎に、優先順位順にタスクＩＤを読み出すことができる。
【００２７】
また、このようにタスクの優先順位を利用してタスクを管理する場合には、請求項９に示すように、タグ情報として、タスクが現在属する待ち行列種別情報をビット表現したものを上位側に、タスクの優先順位情報をビット表現したものを下位側に配置し連接した情報をタグ情報とするとよい。このようにすれば、待ち行列種別情報と優先順位情報で一つの値として一度に比較判定が可能となる。そのため、待ち行列種別情報の比較判定と優先順位情報の比較判定を別々にする必要がなくなり、ハードウェア規模を削減することができる。
【００２８】
なお、タスクの優先順位情報は、優先順位が高いもの程値を大きく割り当てる場合と、優先順位の高いもの程値を小さく割り当てる場合があるが、このようにすれば、いずれかの方向で待ち行列種別情報順に並び、同じ待ち行列種別情報の中ではいずれかの方向で優先順位順にタスク情報が並ぶことになる。
【００２９】
そこで、タスクの優先順位情報として、優先順位が高いもの程、値が大きく割り当てられる場合には、請求項１０に示すように、タスク情報記憶手段におけるタスク情報をタグ値の降べきの順に整列するとよい。このようにすれば、先頭タスク情報を読み出す際に、待ち行列種別情報が一致するタスク情報群のうち先頭のタスク情報記憶領域を読み出せば、優先度の最も高いタスクＩＤを得ることができる。なお、請求項７の構成で後方から比較して挿入することで、あらためて整列操作をしなくてもこのように整列させることができる。
【００３０】
同様に、タスクの優先順位情報として、優先順位が高いもの程、値が小さく割り当てられる場合には、請求項１１に示すように、タスク情報記憶手段におけるタスク情報をタグ値の昇べきの順に整列するとよい。このようにすれば、先頭タスク情報を読み出す際に、待ち行列種別情報が一致するタスク情報群のうち先頭のタスク情報記憶領域を読み出せば、優先度の最も高いタスクＩＤを得ることができる。なお、請求項７の構成で前方から比較して挿入することで、あらためて整列操作をしなくてもこのように整列させることができる。
【００３１】
このようにすれば、優先順位情報をタグ情報に含む場合と、優先順位情報を含まない場合とで、同様の装置構成を採ることが可能となる。そのため、優先順位情報を必要とする場合と必要としない場合が混在する環境においても、タスク情報の管理が容易となり、ハードウェア規模を削減することができる。
【００３２】
以上説明したように、待ち行列内に、待ち行列種別を示す情報を付加することにより、タスク数分の容量を持った実行待ち行列、セマフォ・イベントフラグ等の事象待ち行列等を複数用意することなしに、１つのタスク数分の容量を持つ待ち行列（タスク情報記憶手段）ですべての待ち行列の管理をすることが可能となる。これにより、リアルタイムＯＳをハードウェア化する際の、タスク管理装置のハードウェア規模を削減できる。
【００３３】
【発明の実施の形態】
以下、本発明が適用された実施例について図面を用いて説明する。
［第一実施例］
図１は第一実施例を示す構成図である。
【００３４】
図１に示すように、本実施例のタスク管理装置は、検索部１と、待ち行列２と、先頭タスク読み出し部３とを備える。さらに、待ち行列２は待ち行列種別４と、タスクＩＤ５を記憶する。動作概要としては、検索部１に、外部よりタスクを挿入するのか削除するのかを示す挿入／削除信号G、検索タスクＩＤ TS、検索待ち行列種別KSが与えられると、その情報に従って検索部１は、待ち行列２の内容を検索し、検索結果に従って待ち行列２を更新する為の制御信号S0〜SX-1、もしくは先頭タスク読み出し部３において先頭タスクを読み出す為の検出信号E0〜EX-1を出力する。待ち行列２は検索部１からの制御信号S0〜SX-1によって内部情報を更新し、先頭タスク読み出し部３は検索部１からの検出信号E0〜EX-1によって所望のタスク情報TOUTを出力する。
【００３５】
図２は待ち行列２の内部構成を示したもので、基本ユニット３０が直列に並んだ構成となっている。この基本ユニット３０は、４入力１出力のセレクタ３３と、順序回路等からなる記憶装置３４とを備える。セレクタ３３は外部からの制御信号により、制御信号値が０の場合は同ユニット内の記憶装置出力を入力とし、制御信号値が１の場合は外部からのタスクＩＤ TSと待ち行列種別KSを入力とする。また、制御信号値が２の場合は自ユニット３０の前方に位置するユニット内の記憶装置３２の出力を入力とし、制御信号値が３の場合は自ユニット３０の後方に位置するユニット内の記憶装置３６の出力を選択して自ユニット３０の記憶装置３４の入力とする。
【００３６】
図３は検索部１の内部構成を示したもので、基本ユニット４００が並列に並んだ構成となっている。この基本ユニット４００は、第１比較器４０４と、第２比較器４０５と、エッジ検出器４０６とを備える。第１比較器４０４は待ち行列２に記憶される待ち行列種別Ｋnと外部から入力される検索待ち行列種別KSを比較し、KS ＜Kn の場合に１を、そうでない場合に０を出力する。第２比較器４０５は待ち行列２に記憶されるタスクＩＤ Ｔｎと外部から入力される検索タスクＩＤ TSを比較し、一致する場合は１を、そうでない場合は０を出力する。エッジ検出器４０６は同ユニット４００内の第１比較器４０４からの入力が１で、かつユニット４００の前に位置するユニットにおける第１比較器４０１からの入力が０の場合に１を出力し、そうでない場合は０を出力する。エッジ検出器４０６の検出結果は検出信号Enとして外部に出力されるとともに、制御信号生成器４１０に入力される。
【００３７】
制御信号生成器４１０はすべてのユニット内のエッジ検出器からの入力及び第２比較器からの入力を受けると、その結果を基に制御信号S0〜SX-1を生成する。
図４（ａ）は先頭タスク読み出し部３の内部構成を示したもので、複数のトライステートバッファを並列に並べ、出力をワイアードORで接続した構成となる。待ち行列２の出力データY0〜YX-1から、検索部１による検出信号E0〜EX-1に従って１つの出力データを選択して出力する。また先頭タスク読み出し部は、図４（ｂ）に示すような構成でも実現可能である。図４（ｂ）はX入力１出力のセレクタ５４と、制御信号E0〜EX-1から、前記セレクタへの選択信号を生成するエンコーダ５３により構成され、制御信号E0〜EX-1中の１である制御信号に対応した出力データをToutとして出力する。
【００３８】
本実施例のタスク管理装置の動作は、（１）待ち行列へのタスクの挿入、（２）待ち行列からのタスクの削除、（３）指定待ち行列種別に該当する待ち行列における先頭タスクの読み出しの３つに分かれる。次に、それぞれの動作を説明する。
（１）待ち行列へのタスクの挿入
待ち行列へタスクを挿入する手順を図５に示す。待ち行列６０２に対して、待ち行列種別KS＝１で、タスクＩＤ＝TSの挿入するタスク情報６０１を挿入する。ただし、待ち行列６０２は、待ち行列の未使用部分にダミー情報として待ち行列種別として取りうる最大値に１を足した数（待ち行列６０２においては３）が挿入されている。
【００３９】
まず、検索部１の第１比較器によりKSと待ち行列６０２内の各待ち行列種別の比較が行われ、第一比較器の比較結果６０３を得る。次にこの比較結果６０３をエッジ検出器に入力することにより、エッジ検出器の検出結果６０４に示すように、比較結果６０３の０から１への変化位置のみ１となるようなビット情報へと変換される。検出結果６０４が制御信号生成器６０５に入力されると、制御信号生成器６０５は、検出結果６０４において１よりも右に位置する０をすべて２に置きかえ、制御信号６０６を出力する。制御信号６０６が待ち行列２のセレクタにそれぞれ入力されることによって、タスク挿入後の待ち行列６０７に示すように待ち行列が更新される。このように、待ち行列６０７において待ち行列種別１を持つタスクの最後尾に挿入タスクTSが挿入され、FCFSで並べられる。
（２）待ち行列からのタスクの削除
待ち行列からタスクを削除する手順を図６に示す。待ち行列７０２に対して待ち行列種別KS＝未指定で、タスクＩＤ＝TSのタスク情報７０１のタスクを削除する。まず、検索部１の第２の比較器によりTSと待ち行列７０２内のタスクＩＤの比較が行われ、第２比較器の比較結果７０３を得る。比較結果７０３が制御信号生成器７０４に入力されると、制御信号生成器７０４は比較結果７０３において、１と、１よりも右に位置するすべての０を３に置きかえ、制御信号７０５を出力する。制御信号７０５に従って、タスクTSが待ち行列７０２から削除され、待ち行列７０６が更新される。
（３）先頭タスクの読み出し
待ち行列から所望の待ち行列種別の先頭タスクを読み出す手順を図７に示す。ここで所望の待ち行列種別として先頭タスク読み出し行列情報８０１に示すようにKS=１とする。まず、このKSから１を引いた値０と、待ち行列８０２における各待ち行列種別情報が検索部１における第１比較器により比較され、
第一比較器の比較結果８０３を得る。次にこの結果をエッジ検出器に入力することにより、エッジ検出器の検出結果８０４に示すように比較結果８０３の０から１への変化位置のみ１となるような検出結果８０４へと変換される。検出結果８０４において１がたつ位置が待ち行列８０５における読み出し位置であり、先頭タスク読み出し部によって、タスクＩＤ＝T2に関するタスク情報TOUTが出力される。
【００４０】
以上が第一実施例の動作説明である。
［第二実施例］
図８は第二実施例を示す図であり、特に各タスクの優先順位情報において、優先順位が高いもの程、値が小さく割り当てられた場合の構成を示すものである。図８に示すように、本実施例のタスク管理装置は、検索部９０１と、待ち行列９０２と、先頭タスク読み出し部９０３とを備え。この内、待ち行列９０２はタグ９０４と、タスクＩＤ９０５とを備え、さらにタグ９０４は待ち行列種別９０６と、優先順位９０７とを備える。
【００４１】
動作概要としては、検索部９０１に、外部より挿入／削除信号G、検索タスクＩＤ TS、検索待ち行列種別KS、検索タスク優先順位PSが与えられると、その情報に従って、検索部９０１は待ち行列９０２の内容を検索し、検索結果に従って待ち行列９０２を更新する為の制御信号S0〜SX-1、もしくは先頭タスク読み出し部９０３において先頭タスクを読み出す為の検出信号E0〜EX-1が出力される。待ち行列９０２は検索部９０１からの制御信号S0〜SX-1によって内部情報を更新し、先頭タスク読み出し部９０３は検索部９０１からの検出信号E0〜EX-1によって所望のタスク情報TOUTを出力する。
【００４２】
待ち行列９０２の内部構成は第一実施例と同様に図９に示す構成となる。ただし外部から入力される情報はタスクＩＤと待ち行列種別に、タスク優先度が加わる。
図１０は検索部９０１の内部構成を示したもので、基本ユニット１０００が並列に並んだ構成となっている。基本ユニット１０００は第１比較器１００４と、第２比較器１００５と、エッジ検出器１００６とを備える。また各ユニットに入力される検索待ち行列種別KS、検索タスク優先順位PSはタグ１０１１に示すように、KSをMSB側に、PSをLSB側に配置し連接させたものを検索タグISとしている。第１比較器１００４は待ち行列９０２に記憶されるタグInと外部から入力される検索タグISを比較し、IS ＜ In の場合に１を、そうでない場合に０を出力する。第２比較器１００５は待ち行列９０２に記憶されるタスクＩＤ Ｔｎと外部から入力される検索タスクＩＤ TSを比較し、一致する場合は１を、そうでない場合は０を出力する。エッジ検出器１００６は同ユニット１０００内の第１比較器１００４からの入力が１で、かつユニット１０００の前に位置するユニットにおける第１比較器１００１からの入力が０の場合に１を出力し、そうでない場合は０を出力する。エッジ検出器１００６の検出結果は検出信号Enとして外部に出力されるとともに、制御信号生成器１０１０に入力される。
【００４３】
制御信号生成器１０１０はすべてのユニット内のエッジ検出器からの入力と、第２比較器からの入力を受けると、その結果を基に制御信号S0〜SX-1を生成する。
先頭タスク読み出し部９０３の内部構成は実施例１と同様に図４（ａ）、もしくは図４（ｂ）に示す構成となる。
【００４４】
本実施例の動作は、（１）待ち行列へのタスクの挿入、（２）待ち行列からのタスクの削除、（３）指定待ち行列種別に該当する待ち行列における先頭タスクの読み出しの３つに分かれる為、順にその動作を示す。
（１）待ち行列へのタスクの挿入
待ち行列へタスクを挿入する手順を図１１に示す。待ち行列１１０２に対して待ち行列種別KS＝１で、検索タスク優先順位PS＝１、合わせた検索タグIS＝（KS,PS）＝（１，１）で、タスクＩＤ＝TSの挿入するタスク情報１１０１を挿入する。（検索タグは、実際はKS,PSをビット単位で結合する為に（１，１）のような形式にはならないが説明を簡単にする為にこのような表現形式を取る）ただし、待ち行列１１０２は、待ち行列の未使用部分にダミー情報として待ち行列種別として取りうる最大値に１をたした数（待ち行列１１０２においては３）が、優先順位として取りうる最大値（待ち行列１１０２においては３）が挿入されている。
【００４５】
まず、検索部９０１の第１比較器によりISと待ち行列９０２内のタグとの比較が行われ、第一比較器の比較結果１１０３を得る。次にこの結果をエッジ検出器に入力することにより、エッジ検出器の検出結果１１０４に示すに、比較結果１１０３の０から１への変化位置のみ１となるようなビット情報へと変換される。検出結果１１０４が制御信号生成器１１０５に入力されると、制御信号生成器は検出結果１１０４において１よりも右に位置する０をすべて２に置きかえ、制御信号１１０６を出力する。制御信号１１０６が待ち行列９０２のセレクタにそれぞれ入力されることによって、タスク挿入後の待ち行列１１０７に示すように待ち行列が更新される。このように、待ち行列１１０７において待ち行列種別１を持ち、かつ優先順位１を持つタスクの最後尾に挿入タスクTSが挿入されている。これは、この待ち行列が優先順位で並べられ、かつ同優先順位においてはFCFSで並べられるからである。
（２）待ち行列からのタスクの削除
待ち行列からタスクを削除する手順を図１２に示す。待ち行列１２０２に対して１２０１に示すような待ち行列種別KS＝未指定、検索タスク優先順位＝未指定、タスクＩＤ＝TSのタスクを削除する。まず、検索部９０１の第２の比較器によりTSと待ち行列１２０２内のタスクＩＤの比較が行われ、第２比較器の比較結果１２０３を得る。比較結果１２０３が制御信号生成器１２０４に入力されると、制御信号生成器は比較結果１２０３において、１と、１よりも右に位置するすべての０を３に置きかえ、制御信号１２０５を出力する。制御信号１２０５に従って、タスクTSが待ち行列１２０２から削除され、待ち行列１２０６が更新される。
（３）先頭タスクの読み出し
待ち行列から所望の待ち行列種別が割り当てられた待ち行列の先頭タスクを読み出す手順を図１３に示す。ここで所望の待ち行列種別として先頭タスク読み出し行列情報１３０１に示すようにKS=１とする。また、先頭タスク読み出しの場合は検索タスクの優先順位として優先順位の最大値（図１３では３）を割り当てる。まず、このKSより１を引いた値０と、PS＝３を合わせて生成したタグと、待ち行列１３０２における各待ち行列種別情報が検索部９０１における第１比較器により比較され、第一比較器の比較結果１３０３を得る。次にこの結果をエッジ検出器に入力することにより、エッジ検出器の検出結果１３０４に示すように比較結果１３０３の０から１への変化位置のみ１となるような検出結果１３０４へと変換される。検出結果１３０４において１がたつ位置が待ち行列１３０５における読み出し位置となり、タスクＩＤ＝T2に関するタスク情報TOUTが出力される。
【００４６】
以上が第二実施例の動作説明である。
［第三実施例］
第二実施例に対して、各タスクの優先順位情報において、優先順位が高いもの程、値が大きく割り当てられた場合を第三実施例として示す。第三実施例の全体構成は、第二実施例と同じく、図８に示すような構成となり、検索部９０１と、待ち行列９０２と、先頭タスク読み出し部９０３と備える。ただし、検索部９０１における第１比較器の比較方法が異なり、In ＜ ISの時に１を出力するような比較器となる。以下、各ブロックの説明については第二実施例と同様であるため、省略する。本実施例の動作は、（１）待ち行列へのタスクの挿入、（２）待ち行列からのタスクの削除、（３）指定待ち行列種別に該当する待ち行列における先頭タスクの読み出しの３つに分かれる為、順にその動作を示す。
（１）待ち行列へのタスクの挿入
待ち行列へのタスク挿入手順は、待ち行列の内容が変わる以外は第二実施例と同様の手順である。
【００４７】
待ち行列へタスクを挿入する手順を図１４に示す。待ち行列１４０２に対して１４０１に示すような待ち行列種別KS＝２で、検索タスク優先順位PS＝１、合わせた検索タグIS＝（KS,PS）＝（２，１）で、タスクＩＤ＝TSの挿入するタスク情報１４０１を挿入する。（検索タグは、実際はKS,PSをビット単位で結合する為に（２，１）のような形式にはならないが説明を簡単にする為にこのような表現形式を取る）ただし、待ち行列１４０２は、待ち行列種別として０の割当てを禁止し、待ち行列の未使用部分の待ち行列種別部分にダミー情報として０を、優先順位部分に取りうる最小値（待ち行列１４０２においては０）が挿入されている。
【００４８】
まず、検索部９０１の第１比較器によりISと待ち行列９０２内の各待ち行列種別の比較が行われ、第一検出器の比較結果１４０３を得る。次にこの結果をエッジ検出器に入力することにより、エッジ検出器の検出結果１４０４に示すような比較結果１４０３の０から１への変化位置のみ１となるようなビット情報へと変換される。検出結果１４０４が制御信号生成器１４０５に入力されると、制御信号生成器は検出結果１４０４において１よりも右に位置する０をすべて２に置きかえ、制御信号１４０６を出力する。制御信号１４０６が待ち行列９０２のセレクタにそれぞれ入力されることによって、タスク挿入後の待ち行列１４０７に示すように待ち行列が更新される。
【００４９】
このように、待ち行列１４０７において待ち行列種別１を持ち、かつ優先順位１を持つタスクの最後尾に挿入タスクTSが挿入することができる。これは、この待ち行列が優先順位で並べられ、かつ同優先順位においてはFCFSで並べられるからである。
（２）  待ち行列からのタスクの削除
待ち行列からのタスクの削除手順は、待ち行列の内容が変わる以外は第二実施例と同様の手順である。
【００５０】
待ち行列からタスクを削除する手順を図１５に示す。待ち行列１５０２に対して１５０１に示すような待ち行列種別KS＝未指定、検索タスク優先順位＝未指定、タスクＩＤ＝TSのタスクを削除する。まず、検索部９０１の第２の比較器によりTSと待ち行列１５０２内のタスクＩＤの比較が行われ、１５０３に示すような比較結果を得る。比較結果１５０３が制御信号生成器１５０４に入力されると、制御信号生成器は比較結果１５０３において、１と、１よりも右に位置するすべての０を３に置きかえ、制御信号１５０５を出力する。制御信号１５０５に従って、タスクTSが待ち行列１５０２から削除され、待ち行列１５０６が更新される。
（３）先頭タスクの読み出し
待ち行列から所望の待ち行列種別が割り当てられた待ち行列の先頭タスクを読み出す手順を図１６に示す。ここで所望の待ち行列種別は先頭タスク読み出し行列情報１６０１に示すようにKS=２とする。また、先頭タスク読み出しの場合は検索タスクの優先順位として優先順位の最小値（図１３では０）を割り当てる。まず、このKSに１をたした３と、PS＝０を合わせて生成したタグと、待ち行列１６０２における各待ち行列種別情報が検索部９０１における第１比較器により比較され、第一比較器の比較結果１６０３を得る。次にこの結果をエッジ検出器に入力することにより、エッジ検出器の検出結果１６０４に示すように、比較結果１６０３の０から１への変化位置のみ１となるような検出結果１６０４へと変換される。検出結果１６０４において１がたつ位置が、待ち行列１６０５における読み出し位置となり、タスクＩＤ＝T2に関するタスク情報TOUTが出力される。
【００５１】
以上が第三実施例の動作説明である。
以上の各実施例において説明したように、待ち行列内に、待ち行列種別を示す情報を付加することにより、タスク数分の容量を持った実行待ち行列、セマフォ、イベントフラグ等の事象待ち行列を複数用意することなしに、１つのタスク数分の容量を持つ待ち行列ですべての待ち行列の管理をすることが可能となる。これにより、リアルタイムＯＳをハードウェア化する際のタスク管理装置のハードウェア規模を削減することができる。
【００５２】
なお、本発明の実施の形態は、上記の実施例に何ら限定されることなく、本発明の技術的範囲に属する限り種々の形態を採りうることは言うまでもない。
上述の各実施例において、記憶装置がタスク情報記憶領域に相当し、セレクタがタスク情報挿入手段・タスク情報削除手段に相当し、したがって、待ち行列がタスク情報記憶手段・タスク情報挿入手段・タスク情報削除手段に相当する。また、検索部がタスク情報挿入手段・タスク情報削除手段・先頭タスク情報読み出し手段の比較機能に相当し、先頭タスク読み出し部が先頭タスク情報読み出し手段に相当する。
【図面の簡単な説明】
【図１】第一実施例の全体構成を示すブロック図である。
【図２】第一実施例から第三の実施例における待ち行列の内部構成を示すブロック図である。
【図３】第一実施例における検索部の内部構成を示すブロック図である。
【図４】第一実施例から第三の実施例における先頭タスク読み出し部の内部構成を示すブロック図である。
【図５】第一実施例における待ち行列へのタスク挿入手順を示す図である。
【図６】第一実施例における待ち行列からのタスク削除手順を示す図である。
【図７】第一実施例における待ち行列から先頭タスクを読み出す手順を示す図である。
【図８】第二実施例および第三実施例の全体構成を示すブロック図である。
【図９】第二実施例および第三実施例における待ち行列の内部構成を示すブロック図である。
【図１０】第二実施例および第三実施例における検索部の内部構成を示すブロック図である。
【図１１】第二実施例における待ち行列へのタスク挿入手順を示す図である。
【図１２】第二実施例における待ち行列からのタスク削除手順を示す図である。
【図１３】第二実施例における待ち行列から先頭タスクを読み出す手順を示す図である。
【図１４】第三実施例における待ち行列へのタスク挿入手順を示す図である。
【図１５】第三実施例における待ち行列からのタスク削除手順を示す図である。
【図１６】第三実施例における待ち行列から先頭タスクを読み出す手順を示す図である。
【図１７】従来の例を示した図である。
【符号の説明】
１，９０１…検索部
２，９０２…待ち行列
３，９０３…先頭タスク読み出し部
４，９０６…待ち行列種別
５，９０５…タスクＩＤ
３０…待ち行列を構成する基本ユニット
３１，３３，３５…セレクタ
３２，３４，３６…記憶装置
５０，５１，５２…スリーステートバッファ
５３…エンコーダ
５４…X入力１出力セレクタ
４００，１０００…検索部を構成する基本ユニット
４０１，４０４，４０７，１００１，１００４，１００７…第１の比較器
４０２，４０５，４０８，１００２，１００５，１００８…第２の比較器
４０３，４０６，４０９，１００３，１００６，１００９…エッジ検出器
４１０，６０５，７０４，１０１０，１１０５，１２０４，１４０５，１５０４…制御信号生成器
６０１，１１０１，１４０１…挿入するタスク情報
６０２，１１０２，１４０２…タスク挿入前の待ち行列
６０３，８０３，１１０３，１３０３，１４０３，１６０３…第１の比較器による比較結果
６０４，８０４，１１０４，１３０４，１４０４，１６０４…エッジ検出器の検出結果
６０６，７０５，１１０６，１２０５，１４０６ ，１５０５…制御信号生成器の出力結果
６０７，１１０７，１４０７…タスク挿入後の待ち行列
７０１，１２０１，１５０１…削除するタスク情報
７０２，１２０２，１５０２…タスク削除前の待ち行列
７０３，１２０３，１５０３…第２の比較器による比較結果
７０６，１２０６，１５０６…タスク削除後の待ち行列
８０１，１３０１，１６０１…先頭タスク読み出し行列情報
８０２，１３０２，１６０２…先頭タスク読み出し前の待ち行列
８０５，１３０５，１６０５…先頭タスク読み出し後の待ち行列
９０４，１０１１…タグ
９０７…優先順位
【図１】
0004182615.tif 000002
【図２】
0004182615.tif 000003
【図３】
0004182615.tif 000004
【図４】
0004182615.tif 000005
【図５】
0004182615.tif 000006
【図６】
0004182615.tif 000007
【図７】
0004182615.tif 000008
【図８】
0004182615.tif 000009
【図９】
0004182615.tif 000010
【図１０】
0004182615.tif 000011
【図１１】
0004182615.tif 000012
【図１２】
0004182615.tif 000013
【図１３】
0004182615.tif 000014
【図１４】
0004182615.tif 000015
【図１５】
0004182615.tif 000016
【図１６】
0004182615.tif 000017
【図１７】
0004182615.tif 000018