(57)【要約】システム内タイマーを管理する方法が、アレイ内にタイマーを割り当て且つこのタイマーを見出すために必要なメモリおよび時間を減少する。期限時は、時刻クロック時をタイマー時間値と組み合わせることによって、計算される。期限時は、有意な時間の単位である。多次元アレイは、複数の一次元アレイからなる。各一次元アレイは、有意な時間単位に対応し、要素にスプリットされる。一次元アレイの各要素は、一次元アレイの有意な時間の単位に対する標準の時間の単位に対応する。期限時間の有意な単位の最高位の値が、アレイ内のタイマーの位置を決めるために使用される。時間が期限値に残っている場合、それは、アレイ内のタイマーに設けられる。有意な時間の単位の期限時が切れる時、残りの値は、次の一次元アレイ内のタイマーの位置を決めるために使用される。期限時値に残りがない場合、タイマーが切れる。
2005506730.tif 000002
【特許請求の範囲】
【請求項１】
システム内のタイマーを設定する方法であり、タイマー時間値から期限時の値を決定し、期限時の値を多次元アレイの第１の一次元アレイに割り当て、多次元アレイが複数のリンクされた一次元アレイを有し、各一次元アレイが、異なる有意な時間単位に対応し、第１の一次元アレイが期限時の第１の有意な単位に対応し、そして、第１の有意な単位の期限時が切れた時に、残りの有意な単位の期限時を別の複数の一次元アレイに再割り当てし、有意な単位の期限時が切れた時にタイマーが時間切れになる、前記タイマーを設定する方法。
【請求項２】
複数の一次元アレイが、多次元アレイを形成する様に、階層順で構成されていることを特徴とする請求項１記載の方法。
【請求項３】
前記期限時の値は、タイマー値を時刻クロック値と組み合わせて決定される請求項１記載の方法。
【請求項４】
各一次元アレイが、複数の要素から成り、各要素が、対応一次元アレイに対する有意な時間単位の標準時間単位に関係している請求項１、２又は３記載の方法。
【請求項５】
前記期限時が、一次元アレイの要素に割り当てられており、前記一次元アレイの有意な単位の期限時の値に対応している請求項１乃至４の何れかに記載の方法。
【請求項６】
前記残りの有意な単位の期限時が、要素に再割り当てされる請求項５記載の方法。
【請求項７】
前記残りの有意な単位の期限時は、一次元アレイの要素に再割り当てされており、前記第１の有意な単位が期限切れになった時、残りの標準単位の値に対応する一次元アレイの要素に再割り当てされる請求項６記載の方法。
【請求項８】
前記残りの有意な単位の期限時は、複数の有意な単位からなり、前記残りの有意な単位は、階層順で次の一次元アレイの要素に再割り当てされる請求項７記載の方法。
【請求項９】
前記第１の有意な単位の期限時は、有意な単位の階層における最高位単位である請求項１乃至８の何れかに記載の方法。
【請求項１０】
各一次元アレイはリンクされたリストからなる請求項１乃至９の何れかに記載の方法。
【請求項１１】
前記有意な単位が、日、時間、分、秒およびミリ秒である請求項１記載の方法。
【請求項１２】
複数の期限時が、同じ時間に、一次元アレイの同じ要素を占有することができる、請求項１乃至１１の何れかに記載の方法。
【請求項１３】
前記タイマーが、システムプロトコル用のタイマーである請求項１乃至１２記載の方法。
【請求項１４】
前記システムが、通信システムである請求項１乃至１３の何れかに記載の方法。
【請求項１５】
複数のリンクされた一次元アレイからなる多次元アレイであり、各一次元アレイが、異なる有意な時間単位に対応し、期限時の値は、タイマー値から決定される多次元アレイ、期限時の値を、期限の値の第１の有意な単位に対応する一次元アレイに割り当てるための第１のアロケータ、第１の有意な単位の期限時が切れた時に、期限時の残りの値を再割り当てするための第２のアロケータから成り、全ての有意な単位の期限時が切れた時に、タイマーが時間切れする、タイマーを設定するシステム。
【請求項１６】
前記複数の一次元アレイが、多次元アレイを構成する様に階層順で配列されている請求項１５記載のシステム。
【請求項１７】
前記期限時の値が、タイマー値と時刻クロック値との組合せである請求項１５記載のシステム。
【請求項１８】
各一次元アレイが、複数の要素からなり、各要素が、対応一次元アレイに対する有意な時間単位の標準の時間単位に関係している請求項１５、１６又は１７記載のシステム。
【請求項１９】
アロケータが、前記期限時を、対応一次元アレイに対する期限時の有意な単位の値に対応する一次元アレイの要素に割り当てる請求項１５乃至１８何れかに記載のシステム。
【請求項２０】
有意な単位が、日、時間、分、秒およびミリ秒である請求項１５乃至１９の何れかに記載のシステム。
【請求項２１】
複数の期限時が、同じ時間に、一次元アレイの同じ要素を占有することができる請求項１５乃至２０の何れかに記載のシステム。
【請求項２２】
前記タイマーがシステムプロトコル用のタイマーである請求項１５乃至２１の何れかに記載のシステム。
【請求項２３】
前記システムが、通信システムである請求項１５乃至２２の何れかに記載のシステム。
【請求項２４】
各一次元アレイが、リンクされたリストから成る請求項１５乃至２３の何れかに記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はタイマー管理における改良に関係し、特に、多数のタイマーが管理される、例えば、通信システムにおけるアプリケーション（応用）に関係する。
【背景技術】
【０００２】
通信標準プロトコルは、多くの場合、有限状態機械（ＦＳＭ）システムに、基づいている。ＦＳＭシステムは、デバイスドライバーレベルで最も要求が厳しい時間制約を有する。このレベルで、プロトコルが、ＦＳＭの全てのインスタンシエイション（具体例）をカバーすることを要求される。プロトコルタイマーは、自身のプロトコルタイマーを作動する他の通信システムと共に多くの場合作動するので、正確である必要がある。
タイマーを管理するのに要求される時間が、タイマーが作動している環境で利用可能なタイムスライスよりも相当に短い時には、タイマーの管理は、問題とはならない。
【０００３】
しかしながら、或るアプリケーションにおいて、多数のタイマーが使用されている場合は特に、プロトコルタイマーを効率良く管理することが本質的に不可欠である。例えば、タイマーのアレイを管理するために用いられる時間が長くなりすぎる場合、タイマーが時間を費やし始め、時間誤差がシステム中に導入される。この誤差は、タイマーが時間を費やす毎に増大する。この問題は、多くの場合において、或る通信システムが他の通信システムと関連して作動する通信アプリケーションにおいて、特に、軽減されることが望ましい。
【０００４】
現在のシステムは、一次元アレイ、又は単一リンクされたリスト中に保有されるタイマーを使用する。タイマーの数がこれらのシステムで増大すると、タイマーを正しい位置に割り当てるために、リストを検索し、且つ必要であれば、タイマーを割り当ることに便宜を図るためにリスト中の他のタイマーを移動するのに莫大なオーバヘッドが必要とされる。タイマーは、数ミリ秒から何日にも変化する場合があり、比較的長期間をカバーするタイマーが、アレイ／リスト中に割り当てられる必要がある。タイマーをタイマーキューに割り当てる工程は、システムによって使用されるアレイ又はリストの形態に依存する。
【０００５】
単純なリニアーアレイにおいては、莫大な量のメモリが、使用可能性のある全てのタイマーをカバーするのに必要とされる。必要とされるメモリの量は、タイムスライスの細分性およびアレイかカバーすることを必要とする時間の範囲に比例する。
ソートされたアレイにおいては、タイマーは、単純なキュー内に整列される。この形態のアレイで必要とされるメモリはより少ない。しかしながら、タイマーマネージャは、正しい割り当てを見出すために、アレイ内でソートする必要がある。更に、新たに割り当てられたタイマーの後方に位置されるアレイ内のタイマーは、タイマーが割り当てられるアレイ内にスペースを作るために、後方に動かされる必要がある。この動きは、アレイ内に多数のタイマーが存在する場合、多くの時間を消費する場合がある。典型的に、通信システムは、４，０００個を超えるタイマーを作動する場合がある。
【０００６】
ソートされた単一リンクされたリストは、可変のサイズを有することを除いて、単純なリニアーアレイと、同等である。新たなタイマーが、ソートされリンクされたリストに割り当てられる時、リストのサイズが増大する。リスト内のポインターは、次に期限切れとなるエントリーを指し示す。
バイナリツリーアプローチを考慮に入れることができ、この場合データがランダムの場合最適に作動する。タイマーデータは、常にはランダムで無い。バイナリツリーシステムは、単一リンクされたリストよりもより効率的である、しかしながら、２つのリンクが各エントリーに対して要求されるので、バイナリーツリーはより多くのメモリを占有する。
【発明の開示】
【課題を解決するための手段】
【０００７】
本発明は、多数のタイマーを管理することに関係する問題を改善することを目的とし、最も広義の形態では、多次元アレイ内にタイマーを割り当てるタイマー管理システムを提供する。アレイ内のタイマーの位置は、タイマー内のユニットによって決定される。
特に、システム内のタイマーを設定する方法であり、タイマー時間値から期限時の値を決定し、期限時の値を多次元アレイの第１の一次元アレイに割り当て、多次元アレイが複数のリンクされた一次元アレイを有し、各一次元アレイが、時間の異なる有意な単位に対応し、第１の一次元アレイが期限時の第１の有意な単位に対応し、そして、第１の有意な単位の期限時が切れた時に、残りの有意な単位の期限時を別の複数の一次元アレイに再割り当てし、有意な単位の期限時が切れた時にタイマーがタイムアウトする（時間切れになる）、前記タイマーを設定する方法が提供される。
【０００８】
更に、複数のリンクされた一次元アレイからなる多次元アレイであり、各一次元アレイが、異なる有意な時間単位に対応し、期限時の値は、タイマー値から決定される多次元アレイ、期限時の値を、期限時の値の第１の有意な単位に対応する一次元アレイに割り当てるための第１のアロケータ、第１の有意な単位の期限時間が切れた時に、期限時の残りの値を再割り当てするための第２のアロケータから成り、全ての有意な単位の期限時が切れた時に、タイマーがタイムアウトする（時間切れになる）、タイマーを設定するシステムが提供される。
本発明の実施の形態は、システム中のタイマーを管理するのに必要とされる時間およびメモリを減少する利点を有する。タイマーを割りつけるのに消費される時間が減少すると、従来技術のシステムと関連する問題に煩わされることなしに、より多くのタイマーを扱うことのできるシステムが得られる。
本発明の実施の形態は、実施例により図面を参照して記述される。
【発明を実施するための最良の形態】
【０００９】
図１を参照する。二次元アレイ１０は、３つの列にスプリットされている。各列は有意な時間単位に関係している。列Ｐ１２は、時間に関係しており、列Ｑ１４は、分に関係しており、列Ｒ１６は、秒に関係している。列は、リンクされたリストの一次元アレイである。各列は、好ましくは階層順で次のものにリンクされている。各列の各要素は、列が表す有意な時間単位の標準時間単位に関係する。例えば、Ｐ時間列内に２４個の要素があり、分Ｑ列内に６０個の要素があり、秒Ｒ列内に６０個の要素がある。１時間が、Ｐ列内の標準時間である。
【００１０】
図２を参照する。アレイ１０内にタイマーを割り当てるためのプロセス３０が図示されている。マシン又は時刻３２は、Ａ時間、Ｂ分、およびＣ秒の別々の有意な時間単位を有している。タイマー３４は、アレイ（図示せず）内に割り当てを要求する。タイマーは、ＸＸ時間、ＹＹ分、およびＺＺ秒の後に期限が切れる様に設定される。
時刻およびタイマー値は、３６で組み合わされて、期限時３８用の値３９が計算される。従って、タイマーは、Ａ＋ＸＸ時、Ｂ＋ＹＹ分、およびＣ＋ＺＺ秒で切れる。
組み合わされたシステム時間およびタイマーの詳細３０は、次に、４０で、期限時の最上位の有意な単位の配列内の適当な要素に挿入される。この例においては、期限時は、アレイ１０内の時間列Ｐ１２内のＡ＋ＸＸ要素に入力される。それで、もし、時刻が、００：０２：１２であり、割り当てられる時間が０１：１０：０３の後に切れる場合、Ａ＋ＸＸ値は１に等しく、タイマーは、アレイ内の０１要素１８に割り当てられる。
Ｂ＋ＹＹ分およびＣ＋ＺＺ秒である残りの有意な単位の期限時は、列ＰのＡ＋ＸＸ要素内に置かれる４１。
【００１１】
システムクロックは、サイクルを継続し、４２でＡ＋ＸＸ＝０の時、残りの組み合わされたタイマー値は、アレイ内の次の列に送られる。Ｃ＋ＺＺ値４５は、列Ｑ１４のＢ＋ＹＹ要素に挿入される。例において、Ｂ＋ＹＹが１２分に等しいとすると、Ｃ＋ＺＺの残りの値は、列Ｑ２０の１２番目の要素に挿入される４５。
時刻クロックが、カウントダウンし、且つＢ＋ＹＹ＝０の場合、残りのＣ＋ＺＺは、アレイ内の列Ｒに送信される４６。タイマーが、アレイ内の列ＲのＣ＋ＺＺ要素に挿入される４８。時刻クロックがカウントダウンし、５０でＣ＋ＺＺ＝０の時、期限タイマー内にアレイの次の列に入るための値が残っていない場合、タイマーはタイムアウトする（切れる）５２。
【００１２】
多くのタイマーが列の同じ要素を占有することができる。そのタイマーに残っている値は、システムクロック構成要素が、その構成要素が対応するアレイの要素に到達する時に、アレイ内の次の列に渡される。クロック構成要素は、システムクロックの時間、分、秒等を意味する。
異なる時間値に対して異なる列が利用可能であり、例えば、アレイは、日、時間、分、秒、ミリ秒、等に対する列を有することができる。
如何なる時間においても、期限時の有意な単位に対する値がゼロに等しい場合、その値が無視され、次に有意な単位が使用されて、関連するアレイ例内のタイマーを割り当てるために使用される。
【００１３】
本発明の利点は、上述した異なる方法に対する典型的な値を計算することにより示すことができる。アレイに対して必要とされるメモリ、およびアレイ内にタイマーを割り当てるのに必要とされる最大および最小時間は、以下の例によって説明されている。
単純なアレイ方法は、最大タイマーセッティングＭで、ラップラウンド（循環）する様に、想定されており、必要なメモリは、以下の公式を使用して、計算される。
メモリ＝ｂ（Ｍ／ｒ）
ｂは、各タイマーについての情報に対して要求されるバイト数である。ｒは、タイマー解像度である。
【００１４】
タイマーを割り当てるための最大および最小時間はａに等しく、ａは割り当て時間である。
Ｔmax＝ａ
Ｔmin＝ａ
ソートされるアレイのアプローチは、タイマーが切れる順番で、タイマーを記憶するのに使用される。これは、システム内の複数のタイマーを占有するアレイを要求する。それで、システム内のタイマーの数は、
メモリ＝ｂｔ
Ｔmax＝ａ＋ｃ（ｔ−１）
Ｔmin＝ｃ＋ａ
ｔは、システム内の全タイマーの数であり、ｃは、比較時間である。
【００１５】
単一リンクリストは、タイマーエントリーが全て他のものにリンクされていることを除いて、ソートされるアレイと類似である。即ち、各タイマーは、次に切れるタイマーのアレイ内の位置についての情報を含む。
メモリ＝ｔ（ｂ＋ｓ）
Ｔmax＝ａ＋ｃ（ｔ−１）
Ｔmin＝ｃ＋ａ
ｓは単一リンクリストに必要とされる追加メモリーである。
【００１６】
タイマーを単一ストリングではなく、フラッター構造に置くことよりサーチおよびソーティングを最小にする様に、バイナリーツリー方法が設計される。この方法での各エントリーは少なくとも２つの分岐を有している。
メモリ＝ｔ（２ｓ＋ｂ）
Ｔmax＝ｃ（ｔ−１）＋ａ
Ｔmin＝ｃ＋ａ
本発明を具体化する方法は、タイマーを割り当て且つサーチするために必要な時間およびメモリを最小にする様に設計される。上述された実施の形態において、メモリおよび時間値を計算するのに使用される公式は以下の通りである。
メモリ＝ｔ（ｂ＋ｓ）＋ｓｅ
ｅは、各リンクされたリストの開始時での、アレイ内の最初の要素の数である。
Ｔmax＝ｎｃ＋ａ
Ｔmin＝ｃ＋ａ
ｎは、単一リンクリストを保有するアレイの数である。
以下の値を上述の公式に加えることにより、本発明の実施の形態の利点は従来技術に対して、はっきりと認められる。
【００１７】
メモリ
ｂ＝５      −  情報を保持するのに必要されるバイト
ｓ＝３      −  単一リンクリスト用追加メモリ
ｎ＝４          −  本発明におけるアレイの数
ｅ＝２５６      −  初期要素
時間
ｒ＝１０ｍｓ    −  タイマー解像度
ｍ＝１日        −  最大タイマー設定
ｔ＝４０００    −  全タイマー数
ｃ＝３ｏｐ      −  比較時間
ａ＝１ｏｐ      −  割り当て時間
【００１８】
【表１】
2005506730.tif 000003
【００１９】
これらの計算で使用される値は、リアルタイム通信システムの典型的なものである。
テーブル内の結果は、従来技術のシステムが、どの程度、メモリの効率は良いが時間は消費する、或いはメモリは消費するが時間効率は良いの何れかであるかを示す。本発明の実施の形態は、比較的に、メモリおよび時間の両方で効率が良い。
当業者は、本発明の範囲から離れることなしに、例示された実施の形態に対する代替例を想起する。例えば、タイマーユニットは、タイマー内の値に対応するアレイの要素に設置することができ、残りの値は、その値が期限切れになった時に、次の適当な要素に渡される。
【図面の簡単な説明】
【００２０】
【図１】本発明を実施する多次元アレイの表現。
【図２】本発明を実施するプロセスの流れ図。
【図１】
2005506730.tif 000004
【図２】
2005506730.tif 000005
【国際公開パンフレット】
2005506730.tif 000006
2005506730.tif 000007
2005506730.tif 000008
2005506730.tif 000009
2005506730.tif 000010
2005506730.tif 000011
2005506730.tif 000012
2005506730.tif 000013
2005506730.tif 000014
2005506730.tif 000015
2005506730.tif 000016
2005506730.tif 000017
2005506730.tif 000018
2005506730.tif 000019
2005506730.tif 000020
2005506730.tif 000021
2005506730.tif 000022
【国際公開パンフレット（コレクトバージョン）】
2005506730.tif 000023
2005506730.tif 000024
【国際調査報告】
2005506730.tif 000025
2005506730.tif 000026