(57)【要約】【課題】タスクを選択する時間を低減できるようにする。【解決手段】タスクの優先度別のレディキューを用いて、前記タスクの生成、削除及び優先度の変更を行うリアルタイムオペレーティングシステムであって、前記タスクの生成、削除及び優先度の変更を行う際に、前記タスクが割り当てられている優先度を示すレディキューを作成する作成手段を備えている。【選択図】図１
2009251901.tif 000002
【特許請求の範囲】
【請求項１】
タスクの優先度別のレディキューを用いて、前記タスクの生成、削除及び優先度の変更を行うリアルタイムオペレーティングシステムであって、
前記タスクの生成、削除及び優先度の変更を行う際に、前記タスクが割り当てられている優先度を示すレディキューを作成する作成手段を備えたことを特徴とするリアルタイムオペレーティングシステム。
【請求項２】
タスクの優先度別のレディキューを用いて、前記タスクの優先度が決定されているリアルタイムオペレーティングシステムであって、
システムの実行前に、前記タスクが割り当てられている優先度を示すレディキューを作成する作成手段を備えたことを特徴とするリアルタイムオペレーティングシステム。
【請求項３】
タスクの優先度別のレディキューを用いて、前記タスクの優先度が決定されているリアルタイムオペレーティングシステムであって、
あらゆるタスクが実行される前に、前記タスクが割り当てられている優先度を示すレディキューを作成する作成手段を備えたことを特徴とするリアルタイムオペレーティングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はリアルタイムオペレーティングシステムに関し、特に、実行するタスクを選択するためのスケジューリングに用いて好適な技術に関する。
【背景技術】
【０００２】
一般的なリアルタイムオペレーティングシステムでは、優先度に基づいたスケジューリング方法を用いている。すなわち、実行の優先順位を示す優先度を各タスクにあらかじめ決定して与え、実行可能である状態のタスクのうち、もっとも高い優先度を持つタスクを実行するものである。
【０００３】
このスケジューリング方法を実現するための従来の方法を図２及び図３を参照しながら説明する。システムにタスクＡからタスクＨまでの８個のタスクが存在し、タスクの優先度と状態が図２に示すようになっているとき、図３に示すようなレディキューと呼ばれる構造を用いて管理する。すなわち、実行可能である状態のタスクを優先度ごとに分類して、同じ優先度のタスクをリンクでつなぐ。この優先度ごとのリンクを優先度の順に配列に格納する。
【０００４】
図３に示す例の場合は、タスクＡを指すリンクが優先度１の領域に格納され、タスクＢとタスクＣとタスクＤとを繋げたリンクが優先度４の領域に格納され、タスクＧとタスクＨとを繋げたリンクが優先度７の領域に格納されている。なお、タスクＥ及びタスクＦは待ち状態のため、レディキューには表れない。また、実行権は常に優先度の高いタスクに割り当てられるため、優先度１のタスクＡに実行権が与えられる。
【０００５】
一方、タスクＡが待ち状態に入るか、もしくは削除された場合は、タスクＡをレディキューから削除し、次に優先度の高いタスクを選択して実行権を与える。このとき、スケジューラは優先度１のタスクがもう存在しないことを確認し、優先度２を調べて優先度２のタスクが存在しないことを確認する。そして、優先度３を調べて優先度３のタスクが存在しないことを確認し、優先度４を調べて優先度４のリンクの先頭にあるタスクＢを選択する。
【０００６】
このように、タスクが割り当てられていない優先度が多く存在すると、スケジューラがタスクを選択する場合に時間がかかってしまう。さらに、リアルタイムオペレーティングシステムが用意する優先度はあらかじめ決められており、システムが必要とする優先度の数よりは多いのが一般的である。また、システムの設計時には、各タスクの優先度を後で変更したり、任意の優先度のタスクを後で追加しやすくするように、使用するタスクの優先度を詰めて配置するのではなく、図２に示すように優先度に空きがあるように配置したりすることが多い。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
前述したように、タスクの優先度別のレディキューを持つリアルタイムオペレーティングシステムにおいて、タスクが割り当てられていない優先度が存在するとき、スケジューラがタスクを選択するのに時間がかかるという問題がある。
【０００８】
本発明は前述の問題点に鑑み、タスクを選択する時間を低減できるようにすることを目的としている。
【課題を解決するための手段】
【０００９】
本発明のリアルタイムオペレーティングシステムは、タスクの優先度別のレディキューを用いて、前記タスクの生成、削除及び優先度の変更を行うリアルタイムオペレーティングシステムであって、前記タスクの生成、削除及び優先度の変更を行う際に、前記タスクが割り当てられている優先度を示すレディキューを作成する作成手段を備えたことを特徴とする。
また、本発明のリアルタイムオペレーティングシステムの他の特徴とするところは、タスクの優先度別のレディキューを用いて、前記タスクの優先度が決定されているリアルタイムオペレーティングシステムであって、システムの実行前に、前記タスクが割り当てられている優先度を示すレディキューを作成する作成手段を備えたことを特徴とする。
また、本発明のリアルタイムオペレーティングシステムのその他の特徴とするところは、タスクの優先度別のレディキューを用いて、前記タスクの優先度が決定されているリアルタイムオペレーティングシステムであって、あらゆるタスクが実行される前に、前記タスクが割り当てられている優先度を示すレディキューを作成する作成手段を備えたことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、利用されていない優先度を検査する必要がないため、スケジューラのタスクを選択する時間を低減させることができる。
【発明を実施するための最良の形態】
【００１１】
（第１の実施形態）
以下、図面を参照しながら本発明の実施形態について詳細に説明する。
図８は、本実施形態のスケジューリング装置のハード構成例を示すブロック図である。
図８において、８００はスケジューリング装置であり、スケジューリング装置８００は、ＣＰＵ８０１を備えている。ＣＰＵ８０１は、ＲＯＭ８０２またはハードディスク（ＨＤ）８１１に記憶された、あるいはフレキシブルディスク（ＦＤ）８１２より供給されるソフトウェアを実行し、システムバス８０４に接続される外部装置にデータを送信する。
【００１２】
また、スケジューリング装置８００のＣＰＵ８０１、ＲＯＭ８０２またはハードディスク（ＨＤ）８１１に記憶されたプログラムにより、タスクの生成、削除及び優先度変更を行う各手段が構成される。
【００１３】
８０３はＲＡＭで、ＣＰＵ８０１の主メモリ、ワークエリア等として機能する。８０５はキーボードコントローラ（ＫＢＣ）で、キーボード（ＫＢ）８０９からの指示入力を制御する。
【００１４】
８０６はＣＲＴコントローラ（ＣＲＴＣ）で、ＣＲＴディスプレイ（ＣＲＴ）８１０の表示を制御する。８０７はディスクコントローラ（ＤＫＣ）であり、プログラム等を記憶するハードディスク（ＨＤ）８１１、及びフレキシブルディスク（ＦＤ）８１２とのアクセスを制御する。なお、ＨＤ８１１及びＦＤ８１２は、ブートプログラム（起動プログラム：パソコンのハードやソフトの実行（動作）を開始するプログラム）、複数のアプリケーション、編集ファイル、ユーザファイル、ネットワーク管理プログラム等を記憶している。
【００１５】
８０８はネットワークインタフェースカード（ＮＩＣ）で、ＬＡＮ８２０を介して、ネットワークプリンタ、他のネットワーク機器、あるいは他のコンピュータと双方向のデータのやり取りを行う。
【００１６】
図６は、本実施形態のスケジューリング装置におけるオペレーティングシステムの、タスクの生成と削除及び優先度変更の際のレディキューの作成に関する動作手順の一例を示すフローチャートである。これらの処理は、システムの実行前、もしくはあらゆるタスクが実行される前に行われる。まずは、タスクを新たに生成する場合について、図６（ａ）に示すフローチャートを参照しながら説明する。タスクを生成する場合は、図６のステップＳ１０から処理を開始する。
【００１７】
まず、ステップＳ１１において、実行前に生成するタスクの優先度と同じ優先度のタスクが他にあるかどうかを判定する。このとき、レディキューの優先度の欄にすでに同じ優先度が存在するかを調べればよいが、他の方法で調べてもよい。
【００１８】
この判定の結果、同じ優先度のタスクが存在した場合には、ステップＳ１３に遷移して処理を終了する。一方、ステップＳ１１の判定の結果、同じ優先度のタスクが存在しなかった場合には、ステップＳ１２に進み、レディキューに当該優先度を挿入する。そして、ステップＳ１３に遷移して処理を終了する。例えば、システム上のタスクが図２に示すような状態であったときに、優先度３のタスクＩを生成することにより図４に示すような状態になる。この結果、レディキューは図５に示すようなものになる。
【００１９】
次に、タスクを削除する場合について図６（ｂ）のフローチャートを参照しながら説明する。
タスクを削除する場合は、まず、図６（ｂ）のステップＳ２０から処理を開始する。そして、ステップＳ２１において、削除するタスクの優先度と同じ優先度のタスクが他にあるかどうかを判定する。この判定の結果、同じ優先度のタスクが存在した場合には、ステップＳ２３に遷移して処理を終了する。
【００２０】
一方、ステップＳ２１の判定の結果、同じ優先度のタスクが存在しなかった場合には、ステップＳ２２に進み、レディキューから当該優先度を削除する。このとき、それより低い優先度の欄を詰めて、レディキューの優先度の欄に空きが存在しないようにする。そして、ステップＳ２３に遷移して処理を終了する。例えば、システム上のタスクが図４に示すような状態であったときに、優先度３のタスクＩを削除することにより図２に示すような状態になる。この結果、レディキューは図１に示すようなものになる。
【００２１】
次に、タスクの優先度を変更する場合について図６（ｃ）のフローチャートを参照しながら説明する。
タスクの優先度を変更する場合は、まず、図６（ｃ）のステップＳ３０から処理を開始する。そして、ステップＳ３１において、変更前の旧優先度と同じ優先度のタスクが他にあるかどうかを判定する。この判定の結果、同じ優先度のタスクが存在した場合にはステップＳ３３に遷移する。
【００２２】
一方、ステップＳ３１の判定の結果、同じ優先度のタスクが存在しなかった場合には、ステップＳ３２に進み、レディキューから当該優先度を削除する。このとき、他の優先度の欄を詰めてレディキューに空きが存在しないようにする点では、タスクの削除と同様である。その後、ステップＳ３３に遷移する。
【００２３】
次に、ステップＳ３３において、変更後の新優先度と同じ優先度のタスクが他にあるかどうかを判定する。この判定の結果、同じ優先度のタスクが存在した場合には、ステップＳ３５に遷移して処理を終了する。一方、ステップＳ３３の判定の結果、新優先度と同じ優先度のタスクが存在しなかった場合には、ステップＳ３４に進み、レディキューに当該優先度を挿入する。その後、ステップＳ３５に遷移して処理を終了する。
【００２４】
以上のように、本実施形態のような処理を行うことにより、利用されている優先度のみからなるレディキューが作成でき、スケジューラのタスク選択にかかる時間を低減させることができる。
【００２５】
（第２の実施形態）
第１の実施形態では、レディキューの優先度の欄から利用されていない優先度を削除したため、ある優先度が与えられたとき、その優先度に該当するレディキューを直接検索することが難しい。そこで、これを解消するために、全ての優先度の欄を持つ表を用いる場合の実施形態について説明する。なお、本実施形態のスケジューリング装置のハード構成、及びタスクの生成、削除及び優先度変更手順については、第１の実施形態と同様であるため、説明は省略する。
【００２６】
図７は、本実施形態で用いるレディキューを示す図である。図７に示すように、全ての優先度が存在する優先度検索表と、タスクが割り当てられている優先度のみからなる優先度別タスクキュー表とを有している。また、優先度別タスクキュー表に存在する優先度の欄に対して、該当する優先度検索表からリンクが張られている。
【００２７】
例えば、図６において、タスクを生成する場合のステップＳ１２と、タスクの優先度を変更する場合のステップＳ３４とでは、優先度別タスクキュー表に優先度を挿入する。この場合、優先度検索表の該当優先度の欄から優先度別タスクキュー表の該当優先度の欄へリンクを張る。
【００２８】
また、図６において、タスクを削除する場合のステップＳ２２と、タスクの優先度を変更する場合のステップＳ３２とでは、優先度別タスクキュー表から優先度を削除する。この場合、優先度検索表の該当優先度の欄からリンクも削除する。
【００２９】
さらに、図６において、タスクを生成する場合のステップＳ１１と、タスクの優先度を変更する場合のステップＳ３３とでは、該当優先度と同じ優先度のタスクが他にあるかどうかを調べる。この場合には、優先度検索表から優先度別タスクキュー表へのリンクが存在するかどうかを調べればよい。
【００３０】
また、待ち状態や休止状態のタスクが実行可能な状態になってレディキューへタスクを挿入する場合には、そのタスクの優先度を元に優先度検索表から優先度別タスクキューを調べ、そのタスクキューに該当タスクを挿入すればよい。これにより、タスクを生成する処理とタスクをレディキューに追加する処理とにかかる時間も低減できる。
【００３１】
（本発明に係る他の実施形態）
前述した本発明の実施形態におけるリアルタイムオペレーティングシステム（スケジューリング装置）を構成する各手段、並びにその方法の各工程は、コンピュータのＲＡＭやＲＯＭなどに記憶されたプログラムが動作することによって実現できる。このプログラム及び前記プログラムを記録したコンピュータ読み取り可能な記録媒体は本発明に含まれる。
【００３２】
また、本発明は、例えば、システム、装置、方法、プログラムもしくは記録媒体等としての実施形態も可能であり、具体的には、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。
【００３３】
なお、本発明は、前述した実施形態の機能を実現するソフトウェアのプログラム（実施形態では図６に示すフローチャートに対応したプログラム）を、システムまたは装置に直接、または遠隔から供給する場合も含む。そして、そのシステムまたは装置のコンピュータが前記供給されたプログラムコードを読み出して実行することによっても達成される場合を含む。
【００３４】
したがって、本発明の機能処理をコンピュータで実現するために、前記コンピュータにインストールされるプログラムコード自体も本発明を実現するものである。つまり、本発明は、本発明の機能処理を実現するためのコンピュータプログラム自体も含まれる。
【００３５】
その場合、プログラムの機能を有していれば、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータ等の形態であってもよい。
【００３６】
プログラムを供給するための記録媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスクなどがある。さらに、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＤＶＤ（ＤＶＤ−ＲＯＭ、ＤＶＤ−Ｒ）などもある。
【００３７】
その他、プログラムの供給方法としては、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続する方法がある。そして、前記ホームページから本発明のコンピュータプログラムそのもの、もしくは圧縮され自動インストール機能を含むファイルをハードディスク等の記録媒体にダウンロードすることによっても供給できる。
【００３８】
また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても実現可能である。つまり、本発明の機能処理をコンピュータで実現するためのプログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバも、本発明に含まれるものである。
【００３９】
また、その他の方法として、本発明のプログラムを暗号化してＣＤ−ＲＯＭ等の記録媒体に格納してユーザに配布し、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせる。そして、その鍵情報を使用することにより暗号化されたプログラムを実行してコンピュータにインストールさせて実現することも可能である。
【００４０】
また、コンピュータが、読み出したプログラムを実行することによって、前述した実施形態の機能が実現される。さらに、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが、実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現され得る。
【００４１】
さらに、その他の方法として、まず記録媒体から読み出されたプログラムが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれる。そして、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によっても前述した実施形態の機能が実現される。
【図面の簡単な説明】
【００４２】
【図１】本発明の第１の実施形態で用いるレディキューを示す図である。
【図２】タスク状態の一例を示す図である。
【図３】従来のレディキューを示す図である。
【図４】本発明の第１の実施形態において、タスクを追加したタスク状態の一例を示す図である。
【図５】本発明の第１の実施形態において、タスクを追加したレディキューを示す図である。
【図６】本発明の第１の実施形態において、タスクの生成と削除及び優先度変更の際のレディキューの作成に関する動作手順の一例を示すフローチャートである。
【図７】本発明の第２の実施形態で用いるレディキューを示す図である。
【図８】本発明の第１の実施形態のスケジューリング装置のハード構成例を示すブロック図である。
【符号の説明】
【００４３】
８００  スケジューリング装置
８０１  ＣＰＵ
８０２  ＲＯＭ
８０３  ＲＡＭ
８０４  システムバス
８０５  キーボードコントローラ
８０６  ＣＲＴコントローラ
８０７  ディスクコントローラ
８０８  ネットワークインタフェースカード
８０９  キーボード
８１０  ＣＲＴ
８１１  ハードディスク
８１２  フレキシブルディスク
【図１】
2009251901.tif 000003
【図２】
2009251901.tif 000004
【図３】
2009251901.tif 000005
【図４】
2009251901.tif 000006
【図５】
2009251901.tif 000007
【図６】
2009251901.tif 000008
【図７】
2009251901.tif 000009
【図８】
2009251901.tif 000010