(57)【要約】【課題】イベントの実行時間の比較回数を低減して、装置全体の処理負荷を軽減すること。【解決手段】イベント用メモリ１２内に、実行順に並び替えられて記憶されたイベントの位置情報を、イベント管理部１１によって、キャッシュメモリ１３に記憶させ、イベント管理部１１がキャッシュメモリ１３内のイベントの位置情報と、イベント用メモリ１２内のイベントの実行順とによって、新たに追加されるイベントをリスト構造のイベントと関連付けて並び替えることで、イベントの実行時間の比較回数を減らす。【選択図】      図１
2005018622.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも、実行すべき時間情報が含まれる複数のイベントを、実行順に関連付けて管理するイベント管理方法において、
予め関連付けられたイベントの位置情報および前記実行順に基づき、入力する前記イベントを関連付けて、前記イベントの並び替えを行う並び替え工程
を含むことを特徴とするイベント管理方法。
【請求項２】
前記イベント管理方法では、前記並び替えられたイベントの位置情報を保持する保持工程
をさらに含むことを特徴とする請求項１に記載のイベント管理方法。
【請求項３】
前記保持工程では、少なくとも前回入力したイベントの位置情報を保持し、
前記並び替え工程では、前記保持された前回入力したイベントの位置情報および前記実行順に基づき、入力する前記イベントを関連付けることを特徴とする請求項２に記載のイベント管理方法。
【請求項４】
前記保持工程では、前記関連付けられたイベントのうちの所定イベントの位置情報を保持し、
前記並び替え工程では、前記保持された所定イベントの位置情報および前記実行順に基づき、入力する前記イベントを関連付けることを特徴とする請求項２に記載のイベント管理方法。
【請求項５】
少なくとも、実行すべき時間情報が含まれる複数のイベントを管理する管理手段を有し、入力する前記イベントを実行順に並び替えて管理するイベント管理装置において、
前記並び替えられたイベントの位置情報を保持する保持手段と、
前記保持された位置情報および前記イベントの実行順に基づき、入力する前記イベントを関連付けて、前記イベントの並び替えを行う並び替え手段と、
を備えたことを特徴とするイベント管理装置。
【請求項６】
前記保持手段は、前記イベントの位置情報として、前回入力したイベントの位置情報を保持することを特徴とする請求項５に記載のイベント管理装置。
【請求項７】
前記保持手段は、前記イベントの位置情報として、前記関連付けられたイベントのうちの所定イベントの位置情報を保持することを特徴とする請求項５に記載のイベント管理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、実行前の複数のイベントを、実行順に関連付けて管理するイベント管理方法およびイベント管理装置に関するものである。
【０００２】
【従来の技術】
従来のイベント管理では、イベントを管理するためのヘッダを先頭として、このヘッダにタイマによって起動されるイベントが、それぞれ前後のイベントと互いに連結しており、このヘッダおよびイベントは、全体で１つのリストとして構成されて管理されている。
【０００３】
ヘッダは、たとえば一番始めに実行されるイベントと連結されている他、現在連結されているイベントの総数などの情報を含んでいる。また、それぞれのイベントは、実行すべきイベントの内容およびそのイベントを実行すべき時間情報（実際の運用では、絶対時間で表される）で構成され、実行すべき時間の順に整列された状態で連結されており、タイマの満了時にリストの先頭付近を検索して、実行するイベントを抽出していた。このイベント管理としては、たとえば特許文献１に示すようなものがあった。
【０００４】
このようなイベント管理では、たとえば現在イベントリストに１０００個のイベントが連結されているとして、ここに新たにイベント（以下、「追加イベント」という）１００１を追加する場合には、イベントの実行時間でリストを検索する必要がある。そのために、イベント管理装置では、ヘッダから順番に１つずつ他のイベントと実行時間の比較を行い、他のイベントの実行時間が追加イベント１００１の値より大きくなったら、その直前に追加イベント１００１を挿入していた。
【０００５】
【特許文献１】
特開平１０−１７７５０７号公報（第１−３頁）
【０００６】
【発明が解決しようとする課題】
しかしながら、上記従来例では、実行時間までの長さを比較することで、追加イベントのリスト挿入位置を特定しており、このためにヘッダから実行時間の短い方から順に、リストのイベントと追加イベントを１つずつ比較しなければならない。このため、追加イベントの実行時間が、リストのいずれかのイベントの実行時間よりも長い場合には、比較回数が１０００回となり、この部分の処理負荷が高くなるという問題点があった。
【０００７】
たとえば、実際の運用においては、同一時刻に実行時間に到るイベントが連続（たとえば、１０００イベント）して発生する場合があり、この場合に、これら追加イベントが、リストの最後尾に追加されることが判明するには、１０００＋１００１＋…＋１９９９＝約１５０万回、比較を続けなければならず、このようなオーダーの比較処理を実行すると、さらに処理負荷が膨大となり、装置全体の処理能力が低下するという問題点があった。特に、このイベント管理方法をネットワーク内のルータに用いた場合には、データ中継や経路情報交換の機能などが低下する可能性が高いという問題点があった。
【０００８】
この発明は、上記問題点に鑑みなされたもので、イベントの実行時間の比較回数を減して、装置全体の処理負荷を軽減することができるイベント管理方法およびイベント管理装置を提供することを目的とする。
【０００９】
【課題を解決するための手段】
上記目的を達成するため、請求項１にかかるイベント管理方法では、少なくとも、実行すべき時間情報が含まれる複数のイベントを、実行順に関連付けて管理するイベント管理方法において、予め関連付けられたイベントの位置情報および前記実行順に基づき、入力する前記イベントを関連付けて、前記イベントの並び替えを行う並び替え工程を含むことを特徴とするイベント管理方法が提供される。
【００１０】
この発明によれば、たとえばリスト構造に予め関連付けられたイベントの位置情報と、このリスト内のイベントの実行順とによって、追加イベントをリスト構造のイベントと関連付けて、該イベントの並び替えを行うことで、追加イベントの挿入位置をヘッダから実行順に検索する手間を省き、イベントの実行時間の比較回数を低減する。
【００１１】
また、請求項２にかかるイベント管理方法では、前記並び替えられたイベントの位置情報を保持する保持工程をさらに含むことを特徴とする。
【００１２】
この発明によれば、たとえば並び替えられた追加イベントの位置情報を、キャッシュなどに保持し、このイベントの位置情報と、このリスト内のイベントの実行順とによって、新たに発生した追加イベントをリスト構造のイベントと関連付けることで、イベントの実行時間の比較回数を低減する。
【００１３】
また、請求項３にかかるイベント管理方法では、前記保持工程では、少なくとも前回入力したイベントの位置情報を保持し、前記並び替え工程では、前記保持された前回入力したイベントの位置情報および前記実行順に基づき、入力する前記イベントを関連付けることを特徴とする。
【００１４】
この発明によれば、前回の並び替え工程で並び替えられた、たとえば追加イベントの位置情報を、キャッシュなどに保持し、このイベントの位置情報と前記実行順とによって、新たに発生した追加イベントをリスト構造のイベントと関連付けることで、イベントの実行時間の比較回数を低減する。
【００１５】
また、請求項４にかかるイベント管理方法では、前記保持工程では、前記関連付けられたイベントのうちの所定イベントの位置情報を保持し、前記並び替え工程では、前記保持された所定イベントの位置情報および前記実行順に基づき、入力する前記イベントを関連付けることを特徴とする。
【００１６】
この発明によれば、リスト構造のイベントのうち、任意の所定イベント、たとえば定期的に発生するイベントの定期送信時間に近似した実行時間を持つイベントの位置情報を、キャッシュなどに保持し、このイベントの位置情報と前記実行順とによって、新たに発生した追加イベントをリスト構造のイベントと関連付けることで、イベントの実行時間の比較回数を低減する。
【００１７】
また、請求項５にかかるイベント管理装置では、少なくとも、実行すべき時間情報が含まれる複数のイベントを管理する管理手段を有し、入力する前記イベントを実行順に並び替えて管理するイベント管理装置において、前記並び替えられたイベントの位置情報を保持する保持手段と、前記保持された位置情報および前記イベントの実行順に基づき、入力する前記イベントを関連付けて、前記イベントの並び替えを行う並び替え手段とを備えたことを特徴とするイベント管理装置が提供される。
【００１８】
この発明によれば、実行順に並び替えられたイベントの位置情報をキャッシュなどに記憶させて保持し、このイベントの位置情報とリスト内のイベントの実行順とによって、追加イベントをリスト構造のイベントと関連付けることで、イベントの実行時間の比較回数を低減する。
【００１９】
また、請求項６にかかるイベント管理装置では、前記保持手段は、前記イベントの位置情報として、前回入力したイベントの位置情報を保持することを特徴とする。
【００２０】
この発明によれば、前回のイベント追加動作で並び替えられた、たとえば追加イベントの位置情報を、キャッシュなどに記憶させて保持し、並び替え手段において、このイベントの位置情報と前記実行順とによって、新たに発生した追加イベントをリスト構造のイベントと関連付けることで、イベントの実行時間の比較回数を低減する。
【００２１】
また、請求項７にかかるイベント管理装置では、前記保持手段は、前記イベントの位置情報として、前記関連付けられたイベントのうちの所定イベントの位置情報を保持することを特徴とする。
【００２２】
この発明によれば、リスト構造のイベントのうち、任意の所定イベントの位置情報を、キャッシュなどに記憶させて保持し、並び替え手段において、このイベントの位置情報と前記実行順とによって、新たに発生した追加イベントをリスト構造のイベントと関連付けることで、イベントの実行時間の比較回数を低減する。
【００２３】
【発明の実施の形態】
以下に図１〜図５の添付図面を参照して、この発明にかかるイベント管理方法およびイベント管理装置の好適な実施の形態を説明する。
【００２４】
（実施の形態１）
図１は、この発明にかかるイベント管理装置のブロック構成を示す構成図である。図１において、イベント管理装置は、実行前の複数のイベントを実行順に並べて管理するイベント管理部１１と、各イベントの内容を記憶するイベント用メモリ１２と、並び替えられたイベントの位置情報を記憶するキャッシュメモリ１３とから構成されている。
【００２５】
イベント管理部１１は、ヘッダの情報、たとえば実行時間が一番短いイベント１が格納されているイベント用メモリ１２の記憶領域を示す番地情報や現在連結されているイベントの総数などの情報を記憶する記憶部を有し、イベント用メモリ１２およびキャッシュメモリ１３の情報に基づいて、複数のイベントを連結させて管理している。
【００２６】
イベント用メモリ１２は、図２に示すように、記憶領域を示す番地と、各イベントの情報、すなわちイベントの内容およびこのイベントを実行すべき時間などを記憶する記憶領域と、次のイベントが記憶されている記憶領域の番地情報を記憶する次の番地とから構成されており、記憶されている各イベントは、実行すべき時間順に次の番地で関連付けられるポインタ機能によって、実行時間の短いイベント１から順に連結されている。図２では、“００５”番地にイベント１の情報と次の番地“１００”が、“１００”番地にイベント２の情報と次の番地“１４０”が、“１４０”番地にイベント３の情報と次の番地“０００”が、また“０００”番地にイベント４の情報と次の番地“２００”が記憶されており、これらイベントが次の番地によって指定されることで、互いに連結されて１つのリストを構成している。なお、連結の最後尾に接続されたイベントには、次に接続されるイベントがないので、次の番地は、たとえば空欄に設定するか、このメモリでは使用されない任意の番地を設定することも可能である。
【００２７】
キャッシュメモリ１３は、連結の最後尾のイベントが記憶されているイベント用メモリの記憶領域の番地を記憶しており、たとえば最後尾のイベントの記憶領域が決定したら、その記憶領域の番地情報を、イベント管理部１１がキャッシュメモリ１３に記憶させておく。なお、この最後尾のイベントの記憶領域を示す番地情報は、たとえばイベント管理部１１内のヘッダ情報を記憶する記憶部に記憶させてもよい。この場合には、最後尾のイベントの挿入箇所（記憶領域）が決定したら、その挿入箇所をこの記憶部にキャッシュしておく。
【００２８】
イベント管理部１１は、イベント用メモリ１２およびキャッシュメモリ１３を制御しており、追加イベントが入力すると、実行時間の比較をヘッダから行うのではなく、キャッシュメモリ１３に記憶されている前回の最後尾の位置から比較を行い、該当するリストの位置にこの追加イベントを挿入して、番地の関連付けを行って、イベントを連結する。また、イベント管理部１１は、削除すべきイベントの入力に対しては、該当するイベントの削除を行い、かつそのイベントがキャッシュメモリ１３に記憶された番地のイベントの場合には、キャッシュメモリ１３の記憶内容の削除も合わせて行う。
【００２９】
次に、図３のイベントのリスト構造および図４のフローチャートに基づいて、イベントの追加または削除の動作を説明する。図３において、ここでは、現在イベントリストに１０００個のイベントが実行順に連結されていて、ヘッダには、イベント１０００の記憶領域の番地が、最後尾の記憶領域の情報としてキャッシュされているものとする。この状態で、イベント１００１〜イベント２０００の同一実行時間のイベントを追加する場合を説明する。
【００３０】
図４において、まずイベント１００１が入力すると、イベント管理部１１は、この入力したイベントが追加イベントかどうか判断し（ステップ１０１）、この入力したイベントが追加イベントの場合には、キャッシュの検索を行い（ステップ１０２）、キャッシュされている値からイベント用メモリ１２の挿入場所（記憶領域の番地）の決定を行う（ステップ１０３）。このイベント１００１の挿入場所が決定したら、その前後のイベントとの関連付けを行って、イベント用メモリ１２にイベント１００１を追加するとともに（ステップ１０４）、このイベント１００１の挿入場所をヘッダの記憶領域にキャッシュして、キャッシュの更新を行う（ステップ１０５）。
【００３１】
次に、イベント１００２〜２０００が入力した場合も、同様にステップ１０１〜１０５の動作を行い、キャッシュの検索、挿入場所の決定、イベントの追加およびキャッシュの更新を、イベント１００２〜２０００に対して順次行って、リスト内のイベントの追加を行う。
【００３２】
また、ステップ１０１において、入力したイベントが追加イベントではなく、削除の場合には、イベント用メモリ１２から該当するイベントの削除を行って、その前後のイベントの関連付けを行う（ステップ１０６）。そして、このイベントがキャッシュに記憶されているイベントの場合には（ステップ１０７）、キャッシュの削除を行うことによって（ステップ１０８）、リスト内のイベントの並び替えを行う。
【００３３】
このように、イベントが連続的に追加されるのは、ほぼ同じ位置（たとえば、最後尾）への挿入であることが多いので、この実施の形態では、リストの最後尾におけるイベントの挿入場所をキャッシュに記憶させておくことで、追加イベントの挿入場所はキャッシュの場所から数回の比較で決定でき、これによりイベントの実行時間の比較回数を減して、装置全体の処理負荷を軽減することができる。
【００３４】
また、このイベント管理装置を、ネットワーク内のルータに用いた場合には、比較回数をすくなくすることにより、ルータの処理負荷が軽減され、これに伴って、データ中継や経路情報交換の機能などの低下を回避することができる。
【００３５】
なお、この実施の形態では、イベント削除後の最初のイベント追加では、実行時間の短い方から順、すなわちイベント１から順に、追加イベントとの比較を行わなければならないが、２つ目の追加イベントに対しては、上述した最後尾からの検索が可能となるので、イベントの実行時間の比較回数を減して、装置全体の処理負荷を軽減することができる。
【００３６】
また、この実施の形態では、キャッシュされているイベントの削除に対しては、キャッシュの削除を行ったが、この発明はこれに限らず、たとえばキャッシュが削除されることによって最後尾となったイベント（削除された１つ前のイベント）の記憶領域の番地をキャッシュに記憶させておくことも可能である。この場合には、キャッシュ削除後の追加イベントに対しても、最後尾からの検索が可能となるので、さらにイベントの実行時間の比較回数を減らすことができ、これによって装置全体の処理負荷を軽減することができる。
【００３７】
（実施の形態２）
ところで、リストへの新しいイベントの追加は、常に最後尾に行われるわけではない。そこで、この実施の形態２では、リスト内のイベントのうち、所定のイベント、たとえば図５のイベントのリスト構造に示すように、イベント２の記憶領域の番地をキャッシュに記憶しておく。そして、イベント管理部１１は、このキャッシュの位置から次のイベントの挿入場所を決定する場合には、まず新しい追加イベントの実行時間と、キャッシュの記憶対象となるイベント２の実行時間を比較し、イベント２の実行時間よりも新しい追加イベントの実行時間が長い場合には、リストの後方（実行時間が長くなるイベントの方向）へ検索を開始し、またイベント２の実行時間よりも新しい追加イベントの実行時間が長くない場合には、このリストの前方（実行時間が短くなるイベントの方向）へ検索を開始する。
【００３８】
また、連結されたイベントは、実行された結果によって削除される場合もあるし、実行時間に到っていなくても、実行される前にキャンセルされる可能性もある。したがって、キャッシュに記憶されたイベント２がなくなることも、現実の問題として想定される。この場合には、キャッシュをクリアして、次の追加イベントに対する検索をヘッダから行うか、または削除されたイベント２の前後に連結されていたイベントを、新たにキャッシュに登録し直すという処理を行う必要がある。
【００３９】
この実施の形態では、これらのうちのいずれかに設定して、キャッシュに記憶されたイベントの実行時間と新しい追加イベントの実行時間を比較して挿入位置を検索することができるので、実施の形態１と同様、イベントの実行時間の比較回数を減して、装置全体の処理負荷を軽減することができる。
【００４０】
また、このイベント管理装置を、ネットワーク内のルータに用いた場合には、たとえばキープアライブ（ｋｅｅｐ  ａｌｉｖｅ）メッセージのように、定期的に送信される信号があるので、リストの最後尾のイベントではなく、定期送信時間に近似した実行時間を持つ、リスト内のイベントをキャッシュに記憶させておけば、比較回数を減らすことになり、これによってルータの処理負荷が軽減され、さらにはデータ中継や経路情報交換の機能などの低下を回避することができる。
【００４１】
この発明は、これら実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲で種々の変形実施が可能である。たとえば、実施の形態では、キャッシュに登録するイベントの位置情報は１つとしたが、この発明はこれに限らず、複数のイベントの位置情報をキャッシュに登録することも可能である。この場合には、状況に応じてキャッシュ内のイベントを使い分けることが可能となる。
【００４２】
【発明の効果】
以上説明したように、この発明では、予め関連付けられたイベントの位置情報およびイベントの実行順に基づき、追加イベントをリスト内のイベントに関連付けて並び替えるので、追加イベントの挿入位置をヘッダから実行順に検索する手間を省き、イベントの実行時間の比較回数を減して、装置全体の処理負荷を軽減することができる。
【００４３】
また、この発明では、前回入力したイベントの位置情報、または所定イベントの位置情報を保持し、この保持されたイベントの位置情報およびイベントの実行順に基づき、入力する追加イベントを関連付けるので、追加イベントの挿入位置をヘッダから実行順に検索する手間を省き、イベントの実行時間の比較回数を減して、装置全体の処理負荷を軽減することができる。
【図面の簡単な説明】
【図１】この発明にかかるイベント管理装置のブロック構成を示す構成図である。
【図２】図１に示したイベント用メモリの構成を示す構成図である。
【図３】イベントのリスト構造の一例を示す図である。
【図４】図１に示したイベント管理部のイベントの追加または削除の動作を説明するためのフローチャートである。
【図５】イベントのリスト構造の他例を示す図である。
【符号の説明】
１１  イベント管理部
１２  イベント用メモリ
１３  キャッシュメモリ
【図１】
2005018622.tif 000003
【図２】
2005018622.tif 000004
【図３】
2005018622.tif 000005
【図４】
2005018622.tif 000006
【図５】
2005018622.tif 000007