(57)【特許請求の範囲】
【請求項１】
プロセッサ（１０２）、メモリ（１１２）および複数のリソースを有するコンピュータシステムにおいてリソースを効率的に管理するための、一連の動作の１動作当たり平均コストを制限する方法において、前記プロセッサは、
第１の条件（８０２）によって実行が必要となる第１のオペレーション（４０４）と第２の条件（９２０）によって実行が可能となる第２のオペレーション（４３４）を実行し、第１および第２のオペレーションは相互に逆であり、各オペレーションの実行はシステムパラメータ（５５０）に関して一定でないコストを有し、
第１のオペレーションが実行された時に計算デット（ｃｏｍｐｕｔａｔｉｏｎａｌ  ｄｅｂｔ）の初期値を増やし（１１１８）、また第２のオペレーションが実行された時に計算デットの初期値を増やし（１２２８）、
ある動作が実行されたされた時に計算デットの値を減らし（８１８，９１８）、
計算デットが予め定めたデットのしきい値（９２０）を下回る場合のみ、第２  のオペレーションを実行し、
前記コンピュータシステムは割り当てられた領域を前記メモリ中に含み、
前記領域より大きな、乗法定数のサイズを持つ拡張領域であって、拡張されたハンドルデータベースのための拡張領域を割り当て（１１０２）、
前記領域にあるデータを拡張されたハンドルデータベースにコピーし（１１０８−１１１６）、
拡張されたハンドルデータベースにコピーされたデータを、該データを前記サイズで割った余りの値を有する、データベースのインデックスに格納することにより後にハンドル値の衝突が生じないように再編成し（１１０８−１１１６）、
前記領域を割当解除する（１１２２）ことによって、
第１のオペレーションがデータベースサイズを拡張する（４０４）
ことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記ハンドルデータベースは前記データを格納する前記領域の第１のハンドルフィールドと該データのレコードから発行される次のデータを記憶するための第２のハンドルフィールドを有しており、前記プロセッサにより、
レコードが未使用であることを示すために第１のハンドルフィールドのデータと同じデータを第２のデータフィールドに格納し、
レコードが使用中であることを示すために第２のハンドルフィールドには第１のハンドルフィールドのデータに前記サイズを加えた値のデータを格納し、
前記拡張された領域を縮小する場合には前記領域より小さなサイズの縮小されたハンドルデータベースのための縮小領域を前記メモリ中に割り当て（１２０２）、
前記領域にあるデータを縮小されたハンドルデータベースにコピーし（１２０８−１２２６）、
縮小されたハンドルデータベースの中にコピーされたデータを、後にハンドル値の衝突が生じないように再編成し（１２０８−１２２６）、
前記領域を割当解除する（１２３２）ことによって、
第２のオペレーションがデータベースのサイズを縮小し（４０４）、
前記再編成するステップでは、移動前の現在のインデックスのレコード使用中の第１のハンドルフィールドのデータを、移動前のインデックス値から縮小の領域のサイズを引いた値のインデックス（移動後のインデックスと称す）の未使用のレコードに移動し、移動前および移動後のインデックスの第２のハンドルフィールドのデータのうちの大きい方のデータから縮小の領域のサイズを引いた値のデータを新たに移動後のインデックスの第２のハンドルフィールドに格納し、未使用のレコードのインデックスの値から縮小の領域のサイズを引いた値のインデックスのレコードが使用中の場合には、該使用中のレコードの第１のハンドルフィールドの値はそのまま残し、当該未使用のレコードの第２のハンドルフィールドのデータの値から縮小の領域のサイズを引いた値のデータを当該使用中のレコードの第２のハンドルフィールドに新たに格納することにより、後にハンドル値の衝突が生じないようにすることを特徴とする方法。
【請求項３】
請求項１に記載の方法において、さらに、前記プロセッサは、計算デットが限定値以下に低減することがないようにすることを特徴とする方法。
【請求項４】
請求項３に記載の方法において、初期値がゼロであり、限定値がゼロであり、デットのしきい値が１である（８１８，９１８，９２０）ことを特徴とする方法。
【請求項５】
請求項１に記載の方法において、一連の動作が、第１の動作によってデータをデータベースに加え（３１０）、データを第２の動作によってデータベースから削除する（３１４）ことを含み、前記プロセッサは、
データベースに不使用のレコードが含まれず、データをそのデータベースに加えることになっている場合は第１の条件を取得し（８０２）、
データベース内の不使用のレコード数が不使用のしきい値を超える場合は第２の条件を取得する（９２０）ことを含むことを特徴とする方法。
【請求項６】
請求項５に記載の方法において、データベースが拡張される時に計算デットを増やすことが、そのデータベースに加えられるレコード数だけ計算デットを増やす（１１１８）ことを含むことを特徴とする方法。
【請求項７】
請求項５に記載の方法において、データベースが縮小される時に計算デットを増やすことが、データベースから削除されるレコード数だけ計算デットを増やす（１２２８）ことを含むことを特徴とする方法。
【発明の詳細な説明】
【０００１】
技術分野
本発明は、リソース（資源）へのアクセスを要求するコンシューマーのために参照ハンドルを生成、管理、および検証するためのコンピュータ・システムに関する。
【０００２】
背景技術
コンピュータ・システムで作動するソフトウエア・モジュールが共有リソースへのアクセスを要求することは珍しいことではない。例えば、ある与えられたコンピュータ・プログラムがあるファイルシステムが管理しているファイルにアクセスを求めたり、あるネットワーク・ドライバーが管理しているネットワークコネクションへのアクセスを求めることがある。ネットワーク・ドライバーは、ネットワーク・パケット・クラシファイヤが管理する情報構造へのアクセスを求めることがある。これは、多くの共有リソースへのアクセスを求めるソフトウエア・ドライバーなどの多数のソフトウエア・モジュール、およびそのリソースを管理する、あるいは少なくともそのリソースへのソフトウエア・モジュールのアクセスを仲介するアクセス・スーパーバイザーを含む複雑な作業である。
【０００３】
このような仲介が存在するのにはいくつかの理由があり、特に重要な理由は、あるソフトウエア・モジュールがあるリソースを何時削除するかということである。第１のソフトウエア・モジュールが第１のリソースを削除しようとしたとき、他のソフトウエア・モジュールがその第１のリソースに直接ポインターを維持しているとすると、その他のソフトウエア・モジュールのポインターはそのリソースの削除を知らないので、もはや正しいリソースを指さなくなる。リソースの削除が何時起こるかをソフトウエア・モジュールに通知することによってこの問題を解決しようという試みが成されている。しかし、このためにはソフトウエア・モジュールとリソースへのそれぞれのポインターを詳しくアカウントし追跡することが必要である。その結果、このプロセスはきわめて金がかかり、非常に複雑になる。
【０００４】
この問題を解決する別の試みは、あるソフトウエア・モジュールがある特定のリソースへのアクセスを求めたときに、アクセス・スーパーバイザーに仲介させるということに関わっている。仲介するということは、そのソフトウエア・モジュールにその特定のリソースへのアクセスを認める前に、その特定のリソースがまだ存在しているということを保証することになる。これは普通、各ソフトウエア・モジュールに対して特定リソースへの直接ポインターを許可する形ではなく、アクセス・スーパーバイザーに各ソフトウエア・モジュールに対して特定のリソースへのハンドルを発行させるという形で行われる。ソフトウエア・モジュールは、リソースに直接アクセスするためにハンドルを使用しない。代わりに、ソフトウエア・モジュールは、ハンドルをアクセス・スーパーバイザーに提示し、するとアクセス・スーパーバイザーはそのハンドルをデリファレンスして（ｄｅｒｅｆｅｒｅｎｃｅ，参照値を読み出すこと）そのソフトウエア・モジュールのためにそのリソースへのポインターを取得してやることができる。このアプローチは、共有リソースの管理に関してアクセス・スーパーバイザーがコントロールすることを可能にするものであるが、このアプローチに従った従来の方法はほんの初歩的なコントロールしか行えず、いくつかの制限があった。
【０００５】
第１に、従来の方法は、非効率的、高価であり、一定時間（ｃｏｎｓｔａｎｔ−ｔｉｍｅ）でのオペレーションができないために利用が制限されており、このことは同時に活動しているハンドルの数が大きい場合に問題になる。また、従来の方法のハンドル・データベースは、限られた柔軟性しかなく、効率的な仕方で任意に成長したり縮小したりすることができない。さらに、従来の方法は、速やかで効率的なデリファレンス（ｄｅｒｅｆｅｒｅｎｃｉｎｇ）ができず、マルチスレッド環境で非効率的である。さらに、ハンドルをリサイクルしてハンドルスペースを増やし、ハンドル・データベースを最適化する効率的プロセスを欠いている。したがって、必要とされるものは、これらの制限を克服する、参照ハンドルを効果的かつ効率的に生成し、検証するコンピュータで実施するシステムである。
【０００６】
従来のシステム及び方法の利点が何であれ、それらは本発明によって得られる利点を実現できるものではない。
【０００７】
発明の開示
上述した従来技術の制限を克服し、本明細書を読んで理解するときに明らかとなる他の制限を克服するために、本発明は、コンピュータ・システムにおいてリソースへのアクセスを求めるコンシューマーに対して参照ハンドルを生成し検証するシステムおよび方法の中で具体化される。本発明による参照ハンドルの生成と検証は、ネットワーク・コンピュータおよび非ネットワークのパーソナルコンピュータなど、多くのコンピュータ環境におけるリソースへのコンシューマーのアクセスの効率的な管理および運営を可能にする。
【０００８】
本発明は、ハンドル・アドミニストレータを有するリソースマネージャーと、複数のコンシューマーと、複数のリソースを含む。以下の記述において、「コンシューマー」とは、特に、リソースへのアクセスを求めるソフトウエア・モジュール（例えば、ダイナミック・リンク・ライブラリー・ファイルへのアクセスを求めるプリンター・ドライバー）を指す。「リソースマネージャー」という用語は、リソースを管理する、又は少なくともリソースへのコンシューマーのアクセスを仲介する、ソフトウエア・モジュールを指す。リソースマネージャーは、それがコンシューマーに発行するハンドルを管理する。
【０００９】
ハンドル・アドミニストレータは、割り当てルーチン、解除ルーチン、およびデリファレンス・ルーチンを含む。割り当てルーチンは、新しいハンドルを発行し、解除ルーチンは、もはや必要のないハンドルを解除し（こうしてハンドルを無効にする）、デリファレンス・ルーチンは、ハンドルをデリファレンスしてリソースへのポインターにし、そのときハンドルが有効であることを検証する。さらに、本発明は、使用されるおよび使用されないレコード（記録）を管理する補助サブルーチン、ハンドル・データベースを効率的に拡張する拡張サブルーチン、ハンドルをリサイクリングするハンドル・リサイクリング・サブルーチン、ハンドル・データベースを効率的に縮小する縮小サブルーチン、ハンドル・データベースを確率論的に縮小するヒステリシス・サブルーチン、およびメモリ割り当て失敗サブルーチンを含む。
【００１０】
本発明の一つの特徴は、ハンドル割り当ておよび解除が一定時間（ｃｏｎｓｔａｎｔ−ｔｉｍｅ）オペレーションであるということであり、これは特に同時に活動するハンドルの数が大きい場合に重要である。もう一つの特徴は、本発明のハンドル・アドミニストレータは、マルチスレッド環境で効果的に働く効率的な割り当て、解除、デリファレンス・ルーチンを有しているということである。本発明のもう一つの特徴は、データベースのサイズは任意に増大させることができるということであり、これはハンドルの数があらかじめ知られていない場合に重要である；また、データベースのサイズは可能な場合には縮小させることができるということであり、これは特に、ハンドルの数が劇的に変化する場合に重要である。本発明のさらにもう一つの特徴は、生涯にわたって発行されるハンドルの数がハンドル・スペースのサイズを超える場合、ハンドルはリサイクルできるということである。
【００１１】
したがって、本発明のハンドル・アドミニストレータは、同時に活動するハンドルの数が大きいときにも、同時に活動するハンドルの数があらかじめ知られていないときにも、同時に活動するハンドルの数が時間と共に劇的に変化するときにも、ハンドルのデリファレンスを非常に高速で行う必要があるときにも、マルチスレッド環境で動作するときにも、そして生涯にわたって発行するハンドルの数がハンドル・スペースに比べて大きいときにも、効率的および効果的に働くように設計されている。
【００１２】
本発明の上記の、およびその他の、特徴および利点ならびにさらに完全な理解は、本発明についての以下の詳しい記述を添付の図面および付けられている特許請求の範囲と関連させて読めば明らかになるであろう。
【００１３】
発明を実施する最良の態様
本発明についての以下の記述において、その一部をなす添付図面が参照されるが、図面には本発明を実施する具体的な例が図示によって示される。本発明の範囲から逸脱することなく他の実施の形態も利用することができ、構造的な変更を加えることもできることは理解されるであろう。
【００１４】
概観
動作環境の例
図１およびそれに続く議論は、本発明を実施できる適当なコンピューティング環境を簡単に、一般的に記述することを意図している。必要ではないが、本発明は、パーソナル・コンピュータによって実行されるコンテキスト、すなわち、プログラム・モジュールなどの、コンピュータで実行できる指示の一般的コンテキストで記述される。一般に、プログラム・モジュールは、特定のタスクを行ったり、特定の抽象的データ型を有するような、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含む。さらに、本発明は、他のコンピュータ・システム形態、例えば、ハンドヘルドデバイス、マルチプロセッサ・システム、マイクロプロセッサ・ベースの又はプログラム可能なコンシューマー用エレクトロニクス、ネットワークＰＣ、ミニコンピュータ、メインフレーム・コンピュータ、等、によっても実施できるということは当業者には理解されるであろう。本発明はまた、通信ネットワークによってリンクされた遠隔処理デバイスによってタスクが実行される分散型コンピューティング環境でも実施できる。分散型コンピューティング環境ではプログラム・モジュールはローカルおよびリモート記憶保存デバイスの両方に置くことができる。
【００１５】
図１を参照して説明すると、本発明を実施する例示システムは、通常のパーソナルコンピュータ１００の形態の汎用コンピュータデバイスを含み、これはさらに、処理装置１０２，システムメモリ１０４、およびシステムメモリ１０４を含めいろいろなシステム・コンポーネントを処理装置１０２に結合するシステムバス１０６、を含んでいる。システムバス１０６は、メモリバス又はメモリコントローラ、周辺バス、およびいろいろなバスアーキテクチャーのどれかを用いたローカルバス、等いくつかのタイプのバス構造のどれであっても良い。システムメモリは、リードオンリーメモリ（ＲＯＭ）１１０、ランダムアクセスメモリ（ＲＡＭ）１１２を含む。パーソナルコンピュータ１００のエレメントの間で、例えば起動時などに、情報を転送するのに役立つ基本的ルーチンを含む基本入／出力システム１１４（ＢＩＯＳ）はＲＯＭ１１０に収められている。パーソナルコンピュータ１００は、さらに、ハードディスクから読み取ったりハードディスクに書き込んだりするための、図示されない、ハードディスク・ドライブ１１６，脱着可能な磁気ディスク１２０から読み取ったり磁気ディスク１２０に書き込んだりするための磁気ディスクドライブ１１８，ＣＤ  ＲＯＭ又は他の光学媒体などの脱着可能な光ディスク１２４から読み取ったり光ディスク１２４に書き込んだりするための光ディスク・ドライブ１２２，を含む。ハードディスク・ドライブ１１６、磁気ディスクドライブ１１８，および光ディスク・ドライブ１２２は，それぞれ、ハードディスク・ドライブ・インターフェース１２６、磁気ディスクドライブ・インターフェース１２８，および光ディスク・ドライブ・インターフェース１３０によってシステムバス１０６に結合される。ドライブおよびそれに関連したコンピュータ読み取り可能な媒体は、コンピュータ読み取り可能な指示、データ構造、プログラム・モジュール、およびその他のパーソナルコンピュータ１００のためのデータの不揮発性記憶を提供する。ここに記述した例示したコンピュータ環境は、ハードディスク、脱着可能な磁気ディスク１２０、脱着可能な光ディスク１３０、を用いているが、コンピュータがアクセスできるデータを保存できる他のタイプのコンピュータ読み取り可能な媒体、例えば、磁気カセット、フラッシュメモリカード、ディジタルビデオディスク、ベルヌーイ・カートリッジ、ランダムアクセスメモリ（ＲＡＭｓ）、リードオンリーメモリ（ＲＯＭ）、なども例示的な動作環境に使用できるということは、当業者には理解できるであろう。
【００１６】
ハードディスク、磁気ディスク１２０、光ディスク１２４、ＲＯＭ１１０、ＲＡＭ１１２，にはいくつかのプログラム・モジュール、例えばオペレーティング・システム１３２，一つ以上のアプリケーションプログラム１３４，その他のプログラム・モジュール１３６，およびプログラム・データ１３８、などが格納される。ユーザーは、キーボード１４０やポインティング・デバイス１４２などの入力装置によってコンピュータ１００に命令や情報を入力できる。その他の入力装置（図示せず）としては、マイクロホン、ジョイスティック、ゲームパッド、サテライト受信アンテナ、スキャナー、などがある。これら及びその他の入力デバイスは、しばしば、システムバス１０６に結合されたシリアルポート・インターフェース１４４によって処理装置１０２に接続されるが、他のインターフェース、例えばパラレルポート、ゲームポート、あるいはユニバーサルシリアルバス（ＵＳＢ）、などによって接続することもできる。モニター１４６又は他のタイプのディスプレー装置も、インターフェース、例えばビデオアダプター１４８など、によってシステムバス１０６に接続される。モニター１４６の他に、パーソナルコンピュータは、普通、スピーカーやプリンターなど、他の周辺出力装置も含む。
【００１７】
パーソナルコンピュータ１００は、リモート（遠隔）・コンピュータ１５０など、一つ以上のリモート・コンピュータとのロジカル結合を用いて、ネットワーク環境で作動する。リモート・コンピュータ１５０は、別のパーソナルコンピュータ、サーバー、ルーター、ネットワークＰＣ、ピアーデバイス、又はその他の普通のネットワークノードであって良く、図１には記憶保存装置１５２しか示されていないが、パーソナルコンピュータ１００に対して上述の多く又は全てを含んでいる。図１に示されているロジカル結合は、地域ネットワーク（ＬＡＮ）１５４や広域ネットワーク（ＷＡＮ）１５６などである。このようなネットワーキング環境は、オフィス、企業規模のコンピュータ・ネットワーク、イントラネットおよびインターネットでは普通のことである。
【００１８】
ＬＡＮネットワーキング環境で用いられる場合、パーソナルコンピュータ１００は、ネットワーク・インターフェース又はアダプター１５８によってローカルネットワーク１５４に接続される。ＷＡＮネットワーキング環境で用いられる場合、パーソナルコンピュータ１００は、普通、インターネットなどの広域ネットワーク１５６での通信を確立するためのモデム１６０又はその他の手段を含む。モデム１６０は、内部型も外部型もあるが、シリアルポートイース１４４によってシステム・バス１０６に接続される。ネットワーキング環境においては、パーソナルコンピュータ１００に、又はその一部に、関して述べられたプログラム・モジュールは、遠隔記憶保存デバイスに格納することもできる。図に示されたネットワーク接続は例示的なものであり、コンピュータ間に通信リンクを確立するための他の手段も用いることができるということは了解されるであろう。
【００１９】
基本システム
図２は、本発明の主なコンポーネントの間の相互作用を示す一般的なブロック図である。本発明は、リソースマネージャー２００と、複数のコンシューマー２１２，２１４，２１６、と、複数のリソース２１８、２２０、２２２とを含む。リソースマネージャー２００はまた、２００ハンドル・アドミニストレータ２３０を有する。コンシューマー２１２，２１４，２１６は、ソフトウエア・モジュールである。リソース２１８、２２０、２２２は、コンピュータ・ソフトウエア・リソース、例えばダイナミックリンク・ライブラリー・ファイル、である。ソフトウエア・モジュール２１２，２１４，２１６は、時には、リソース２１８、２２０、２２２の一つ又は全部に対するアクセス（単独又は分割の）を要求することがある。例えば、プリンタードライバー・ソフトウエア・モジュールは、通常、ダイナミックリンク・ライブラリー・ファイル・リソースへのアクセスを求める。
【００２０】
ハンドル・アドミニストレータ２３０は、コンシューマーおよびリソースアドミニストレーション設備のために、リソースマネージャー２００への参照マーカー又はハンドルを生成し、検証する。ハンドル・アドミニストレータ２３０は、参照ハンドルを用いて、リソース２１８、２２０、２２２へのアクセスを効率的に管理する。ハンドル・アドミニストレータ２３０は、あるコンシューマーがある特定のリソースへのアクセスを求めたとき、参照ハンドルによって仲介する。仲介は、コンシューマーにある特定のリソースへの直接ポインターを許可することではなく、その特定のリソースへのハンドルをそのコンシューマーに発行するということである。コンシューマーは、そのハンドルを用いてそのリソースに直接アクセスすることはできない。そうではなく、コンシューマーは、そのハンドルをハンドル・アドミニストレータ２３０に提示し、ハンドル・アドミニストレータはまず最初にそのハンドルが有効であることを検証し、次にハンドルをデリファレンスしてそのコンシューマーのためにそのリソースへのポインターを取得する。すなわち、仲介によって、特定リソースがまだ存在することが確認されてから、その特定リソースへのアクセスがコンシューマーに認められる。
【００２１】
一般に、ハンドル・アドミニストレータは、リソース２１８、２２０、２２２をポイントするコンシューマー２１２、２１４，２１６にハンドルを割り当て、解除し、デリファレンスする。リソースマネージャー２００は、リソース２１８、２２０、２２２を管理する、又は少なくともリソース２１８、２２０、２２２へのコンシューマー２１２，２１４，２１６によるアクセスに仲介するソフトウエア・モジュールである。リソースマネージャー２００は、自分がコンシューマー２１２，２１４，２１６に発行するハンドルを管理する。
【００２２】
図３は、本発明のハンドル・アドミニストレータの一般的動作を説明するフローチャートである。図３と合わせて図２を参照して説明すると、ハンドル・アドミニストレータ２３０は、新しいハンドルを発行するための割り当てルーチン３１０，もはや必要でないハンドルを解除するための解除ルーチン３１２，そして、ハンドルが有効であることを検証することも含め、ハンドルをリソースへのポインターに変換するデリファレンス・ルーチン３１４、によって上述の動作を実行する。本発明は、これらの動作の各々を、リソースマネージャー２００においてコードで呼び出される関数という形で設けている。すなわち、これらの関数は、それぞれ、ａｓｓｉｇｎ＿ｈａｎｄｌｅ（）関数、ｒｅｌｅａｓｅ＿ｈａｎｄｌｅ（）関数、ｄｅｒｅｆｅｒｅｎｃｅ＿ｈａｎｄｌｅ（）関数として定義できる。
【００２３】
ａｓｓｉｇｎ＿ｈａｎｄｌｅ（）関数は、あるリソースへのポインターを受け取り、それ以後そのポインターを参照するハンドルを返す。ｒｅｌｅａｓｅ＿ｈａｎｄｌｅ（）関数は、あるハンドルを受け付け、それを無効であるとしてマークする。その結果、それはもはやあるリソースポインターを参照するものではなく、渡されたハンドルが有効なハンドルであるかどうかを表す状態コードを返す。ｄｅｒｅｆｅｒｅｎｃｅ＿ｈａｎｄｌｅ（）関数は、あるハンドルを受け付け、それが有効かどうかをチェックし、もしそのハンドルが有効であれば、該当するリソースへのポインターを返すが、もしそのハンドルが無効であれば、ヌル（ｎｕｌｌ）ポインターを返す。これらの関数の実行はかなり複雑であり、したがって次の節ではハンドル・アドミニストレータについて、最も基本的なシステムから始めて少しずつ説明し、漸次価値ある特徴を追加して最終システムに到達するようにする。
【００２４】
理論的にはハンドルはどんなタイプの値であっても良い。何故なら、それは、リソースマネージャー２００にも、コンシューマー２１２，２１４，２１６にも不透明であるからである。本発明では、ハンドルは、無署名の整数である。その最も基本では、本発明のデータ構造はレコード（記録）のアレーからなり、その各々が表１に記述されているフィールドを含んでいる。
【００２５】
【表１】
0004290336.tif 000002
【００２６】
表１の用語“リソース*”は、“リソースへのポインター”と定義される。この命名法は、Ｃプログラミング言語では標準的であり、全体にわたって用いられる。
【００２７】
最初は、各レコードのハンドル値は、表２の例に示されているように、そのレコードのインデックスに等しく設定される。現在、有効な各ハンドルはそのアレーのレコードに対応する。
【００２８】
【表２】
0004290336.tif 000003
【００２９】
ハンドル・アドミニストレータ２３０が、ａｓｓｉｇｎ＿ｈａｎｄｌｅ（）コールによって、新しいハンドルを発行するよう要求されると、それは使用されていない（未使用）レコードを選択し（ボックス３２０）、レコードのリソースフィールドを、引数として渡されるリソースポインターに設定し（ボックス３２２）、レコードのハンドルフィールドにおけるハンドル値を返す（ボックス３２４）。
【００３０】
例えば、リソースマネージャー２００がリソースＡへのポインターで  ａｓｓｉｇｎ＿ｈａｎｄｌｅ（）をコールすると、ハンドル・アドミニストレータはインデックス０でレコードを選択することができ、その場合、それはリソースフィールドがリソースＡを指すように設定し、ハンドル値０をリソースマネージャーに返す。レコードのアレーは、こうして表３に示されるように変更される。
【００３１】
【表３】
0004290336.tif 000004
【００３２】
ｄｅｒｅｆｅｒｅｎｃｅ＿ｈａｎｄｌｅ（）コールによって、ハンドル・アドミニストレータに対して、ある与えられたハンドルに対応するポインターについての問い合わせがあった場合、それはハンドルの値をアレーのサイズで割った値の余り（ｔｈｅ  ｖａｌｕｅ  ｏｆ  ｔｈｅ  ｈａｎｄｌｅ  ｍｏｄｕｌｏ  ｔｈｅ  ｓｉｚｅ  ｏｆ  ｔｈｅ  ａｒｒａｙ）をとってインデックスを計算し（ボックス３２６）、インデックスされたレコードのハンドルフィールドにおける値と、引数として渡されたハンドル値を比較し（ボックス３２８）、値がマッチするかどうか判定する（ボックス３３０）。二つの値がマッチする場合、渡されたハンドルは有効であると判断され（ボックス３３２）、インデックスレコードのリソースフィールドのポインターが返される（ボックス３３４）。二つの値がマッチしない場合、渡されたハンドルは無効であると判断され（ボックス３３６）、ヌルポインターが返される（ボックス３３８）。
【００３３】
例えば、もしもリソースマネージャー２００が、ハンドル値０でｄｅｒｅｆｅｒｅｎｃｅ＿ｈａｎｄｌｅ（）をコールすると、ハンドル・アドミニストレータ２３０は、この値を４で割った余りをとってインデックスを計算してインデックス０を得る。ハンドル・アドミニストレータ２３０は、次に、このハンドルをレコード０のハンドルフィールドにおける値と比較する。二つの値がマッチしたので、リソースＡへのポインターが返される。
【００３４】
ｒｅｌｅａｓｅ＿ｈａｎｄｌｅ（）コールによって、ハンドル・アドミニストレータ２３０がハンドル解除を要求された場合、ハンドル・アドミニストレータ２３０は、ハンドル値をアレーのサイズで割った余りをとることによってインデックスを計算し（ボックス３４０）、インデックスレコードのハンドルフィールドにおける値と引数として渡されたハンドル値とを比較し（ボックス３４２）、値がマッチするかどうかを判定する（ボックス３４４）。この比較は、厳密には必要でないが、間違った引数の簡単なチェックになる。二つの値がマッチしない場合、渡されたハンドルは無効であると判断され（ボックス３４６）、失敗状態コードが返される（ボックス３４８）。そうでない場合、ハンドルフィールドの値をアレーのサイズだけインクリメントして（ボックス３５０）、リソースフィールドをゼロ・ポインター値に設定し（ボックス３５２）、サクセス状態コードを返す（ボックス３５４）。ハンドル値をアレーのサイズだけインクリメントする理由は、ハンドルフィールドの新しい値が、アレーのサイズで割った余りをとったときに同じインデックス値を与えるようにするためである。リソースフィールド値をヌルに設定する理由は、ハンドル・アドミニストレータが、レコードは使用されておらず、したがって、再割り当てしても良いことを判定できるようにするためである。
【００３５】
例えば、もしもリソースマネージャーが値が０のハンドルでｒｅｌｅａｓｅ＿ｈａｎｄｌｅ（）をコールした場合、ハンドル・アドミニストレータはこの値を４で割った余りをとってインデックスを計算して、０というインデックスを得る。次にハンドル・アドミニストレータは、このハンドルをレコード０のハンドルフィールドの値と比較する。二つの値はマッチするので、ハンドルフィールドの値は４にセットされ、リソースフィールドの値はヌルにセットされる。こうしてレコードのアレーは表４に示されるように変更される。
【００３６】
【表４】
0004290336.tif 000005
【００３７】
さて、リソースマネージャーが、値が０のハンドルで、ｄｅｒｅｆｅｒｅｎｃｅ＿ｈａｎｄｌｅ（）をコールした場合、ハンドル・アドミニストレータは、この値を４で割った余りとってインデックスを計算し、インデックス０を得る。ハンドル・アドミニストレータは次に、このハンドルを、レコード０のハンドルフィールドにおける値と比較する。二つの値はマッチしないので、ヌルポインターが返される。
【００３８】
次に、リソースマネージャーが、今度はリソースＢへのポインターで、ａｓｓｉｇｎ＿ｈａｎｄｌｅ（）を再度コールしたと使用。さらに、ハンドル・アドミニストレータはレコード０を選択し、リソースフィールドをリソースＢをポイントするようにセットし、リソースマネージャーにハンドル値４を返したと使用。レコードのアレーは表５に示されるように変更されるであろう。
【００３９】
【表５】
0004290336.tif 000006
【００４０】
リソースマネージャーが、値が４のハンドルで、ｄｅｒｅｆｅｒｅｎｃｅ＿ｈａｎｄｌｅ（）をコールした場合、ハンドル・アドミニストレータは、この値を４で割った余りをとってインデックスを計算し、インデックス０を得る。ハンドル・アドミニストレータは次に、このハンドルを、レコード０のハンドルフィールドにおける値と比較する。二つの値はマッチするので、リソースＢへのポインターが返される。これと対照的に、リソースマネージャーが、値が０のハンドルで、ｄｅｒｅｆｅｒｅｎｃｅ＿ｈａｎｄｌｅ（）をコールした場合、ハンドル・アドミニストレータは、この値を４で割った余り４をとってインデックスを計算し、インデックス０を得る。これは、ハンドル値４で計算したインデックスと同じである。しかし、このハンドルをレコード０のハンドルフィールドにおける値と比較すると、二つの値はマッチしないので、ヌルポインターが返される。
【００４１】
実施例
図４は、本発明の一実施例のメイン・コンポーネントおよびサブ・コンポーネントを示す構造ブロック・ダイアグラムである。基本的なシステムについては、上で述べたので以下のセクションでは本発明のハンドル・アドミニストレータの実施例について、補助的な構造から始めて、順次有益な特徴を付加してゆき、最終的な実施例が記述できるように、少しずつ順次に説明する。
【００４２】
図４を参照して説明すると、ハンドル・アドミニストレータ２３０の割り当てルーチン３１０は、使用しているレコードや使用していないレコードを管理するための補助サブルーチン４０２と、ハンドル・データベースを効率的に拡張するための拡張サブルーチン４０４と、ハンドルをリサイクリングするためのハンドル・リサイクリング・サブルーチン４０６と、メモリ割り当て失敗サブルーチン４１２と、古いハンドルを自動的に廃止するための廃止サブルーチン４１４を含む。
【００４３】
補助サブルーチンは、リンクされたリスト４２０，バイナリー・ツリー４２２，又はその他４２４の、本発明を実行するのに適したサーチツリー・サブルーチンを含む。拡張サブルーチン４０４はマルチスレッディング・サブルーチン４２６を有する。廃止サブルーチンは、高および低レコードを処理するためのレコード処理４３２のサブルーチンを有する。
【００４４】
解除ルーチンは、縮小サブルーチン４３４と、ヒステリシス・サブルーチン４３６を有する。縮小サブルーチン４３４はマルチスレッディング・サブルーチン４３７を有する。デリファレンス・ルーチン３１２はマルチスレッディング・サブルーチン４３８を有する。
【００４５】
補助構造
以下のセクションでは、本発明の補助サブルーチン４０２について記述する。上で述べたように、ハンドル・アドミニストレータ２３０は、ａｓｓｉｇｎ＿ｈａｎｄｌｅ（）コールに応答して、使用されていないレコードを見つけるためにアレーをサーチする。アレー・サイズが、上記の例におけるように、非常に小さければ、これはあまり費用がかからないオペレーションである。しかし、費用はアレー・サイズと共に直線的に変化するので、アレー・サイズが大きい場合には非常に費用が大きくなる可能性がある。使用されていないレコードのリンクのリストを保持するなどのような、簡単な最適化によってこのコストを一定に抑えることができる。新しいハンドルを発行しようとするとき、このリストからレコードが選ばれる。ハンドルを解除するときには、関連したレコードがこのリストに加えられる。これは、表６に示されているように、各レコードに新しいフィールドを加えることが必要である。
【００４６】
【表６】
0004290336.tif 000007
【００４７】
新しいフィールド、ｎｅｘｔ＿ｒｅｃｏｒｄはあるレコードへのポインターである。リストの先頭へのポインターは保持され、使用されていない各レコードはリストの別のレコードへのポインターを含んでいる。ただし最後のものだけは別で、これはヌルポインターを含んでいる。（リストのレコードをリンクするにはポインターでなく、インデックスを使用しても良かったということに注意されたい。）
【００４８】
システムの望ましい効率によっては、リンクされたリスト４２０およびサーチツリー４２２，４２４についてさらに最適化することもできる。例えば、新しいハンドルを発行するときに、最適化方法を実行して、アレーの使用されていないレコードから効率を考慮して適切なレコードを選ぶようにすることができる。例えば、最も低いインデックスのレコードを選ぶならば、低いレコードのハンドル値は上の方のレコードのものよりも速く（ハンドルを割り当て解除するにつれて）増加する傾向を示すであろう。ハンドルスペースはハンドルのビット数によって制限されているので、やがて低い方のレコードは、高い方のレコードが可能なハンドル値の相当な部分を消費するよりもずっと前に、可能なハンドル値を全て使い尽くし、これによりハンドルスペースを非効率的に利用することになる。この問題は、すべてのレコードから比較的均一な頻度でハンドルを発行することによって防ぐことができ、それは使用されていないすべてのレコードのうちから最も低いハンドル値を発行することによって実行できる。この手順を容易にするためには、使用されていないレコードを、最も低いハンドル値のレコードが速やかに選択できるような、例えばサーチツリー４２２のような構造で格納すべきである。しかし、１つのセットの中の最低値をサーチするということは（あるいは、同様に、ソートされた位置のある新しい値を１つのセットに挿入することは）、本質的に一定時間のオペレーションではなく、対数時間のオペレーションである。アクティブ・ハンドルの数に関わりなく、ａｓｓｉｇｎ＿ｈａｎｄｌｅ（）およびｒｅｌｅａｓｅ＿ｈａｎｄｌｅ（）の関数が一定時間であることがどちらかというと望ましい。
【００４９】
好ましいアプローチは、割り当ておよび解除の関数の一定時間オペレーションを維持し（そして以後のセクションで述べる強化を妨げず）、ほぼ均一な頻度でレコードからハンドルを発行することである。そのアプローチは、上で述べたようなリンクされたリスト４２０を用いて、割り当てのためのレコードはリストの先頭から取り出し、解除されたときにはレコードをリストの最後尾に入れるというものである。このためには、先頭へのポインターの他に、リストの最後尾へのポインターを保持することが必要である。解除のパターンが比較的ランダムであることを考えると、このアプローチは、ハンドルの割り当てがレコードの間で比較的均一に分布する傾向がある。どんな補助構造であっても、ハンドル・アドミニストレータ２３０が、ハンドルが解除されたときに、リソースフィールド値をヌルにセットすることはもはや必要でないということに注意しておかなければならない。それは、構造の中にレコードが存在するということが、それが使用されていないことを示しているからである。
【００５０】
データベース拡張
以下のセクションでは、ａｓｓｉｇｎ＿ｈａｎｄｌｅ（）関数がコールされたが、すべてのレコードが使用されているときに用いられる拡張サブルーチン４０４について説明する。ハンドル・データベースのサイズを増大させるメカニズムなしでは、データベースがいっぱいのときにハンドル割り当ての要求に応える望ましいやり方は何もない。その要請を拒否するか、又はすでに使用されているものからハンドル・エントリーを取ることぐらいである。広く言うと、拡張サブルーチン４０４は、アレーのサイズを増やして割り当てのためにもっと多くのレコードを利用できるようにするために実行される。しかし、ある与えられた領域の使用メモリのすぐ後に追加のメモリを割り当てることは一般には不可能である。何故なら、そのすぐ後のメモリ領域は他のデータを格納するのに使用されている可能性があるからである。したがって、アレーのサイズを増やすためには、別の大きなメモリ領域を割り当てて、小さなアレーからの情報をその大きなアレーにコピーし、小さなアレーのためのメモリ割り当てを取り消すこと必要になる。増やされる新しいサイズは、異なるハンドルから異なるエントリーへのマッピングを保存するような方法で選択される。
【００５１】
例えば、表７に示されているようなサイズ４のフル・アレーを考える。
【００５２】
【表７】
0004290336.tif 000008
【００５３】
アレー・サイズを６に増やすとすると、ハンドル７をデリファレンスする試みは１（＝７ｍｏｄ６）というインデックスを生ずる。しかし、ハンドル１をデリファレンスする試みもインデックス１を生じ、衝突になる。一般に、拡張は、大きなアレーで二つのハンドルが同じインデックスを生ずる場合、それらは小さなアレーでも同じインデックスを生じていたものでなければならない（ただし、逆は必要でもないし、望ましくもない）、という形で行われなければならない。これは、アレー・サイズをある整数の乗数定数だけ増やすということで達成される。この定数と最初のアレー・サイズを２のべき乗になるように選ぶと、複雑な数学的オペレーションの代わりに単純なビット操作オペレーションを採用することが可能になり、多少仕事が単純化される。以下の記述では、この乗数定数は２であり、アレーのサイズは拡張毎に２倍になると仮定する。したがって、表８に示されるようにアレー・サイズは８に増やされる。
【００５４】
【表８】
0004290336.tif 000009
【００５５】
割り当てられたハンドルの間に何も衝突はないということに注意されたい。ハンドル１および１０は、前にはインデックスがそれぞれ１および２であったが（１ｍｏｄ４＝１；１０ｍｏｄ４＝２）、拡張後もそうである（１ｍｏｄ８＝１；１０ｍｏｄ８＝２）。しかし、ハンドル４および７は、前にはインデックスがそれぞれ０および３であったが（４  ｍｏｄ  ４＝０；７  ｍｏｄ  ４＝３）、拡張後はインデックスがそれぞれ４および７となる（４  ｍｏｄ  ８＝４；７  ｍｏｄ  ８＝７）。大きなアレーのメモリを割り当てた後、小さなアレーから大きなアレーへ、大きなアレーに関して計算されたインデックスに従って、レコードがコピーされる。大きなアレーの他の全てのレコードのリソース・ポインターはゼロ値にセットされる（上で述べたように、どのレコードが使用されないでいるかを追跡する補助構造がある場合にはこれは厳密には必要ないが）。これら他のレコードのハンドルフィールドの値は以下で述べるように計算される。
【００５６】
まず最初に、大きなアレーでは、小さなアレーでの各インデックスに対応して二つのインデックスがあるということに注意しておかなければならない。例えば、上の例の大きなアレーにおけるインデックス０と４は、小さなアレーのインデックス０に対応し、大きなアレーでインデックス０又は４を与えるハンドル値はいずれも小さなアレーでインデックス０を与えるということを意味する。すなわち、小さなアレーを大きなアレーに拡張したとき、小さなアレーでインデックスが０のレコードは、大きなアレーではインデックス０又はインデックス４に属する。これら二つのインデックスは互いの“デュアル”と呼ばれる。小さなアレーから大きなアレーへレコードをコピーするときに、ハンドル値を新しいアレー・サイズで割った余りがこのデュアルの一方であるインデックスを与え、そこにレコードがコピーされる。他のデュアルのハンドルフィールドの値は、コピーされたレコードのハンドル値プラス、小さなアレーのサイズに等しいと置かれる。
【００５７】
例えば、表７に示された小さなアレーのインデックス０におけるレコードは、ハンドル値４を持つ。この値を大きなアレーのサイズ（８）で割った余りをとると４になるので、このレコードは、表８に示されているように、大きなアレーのインデックス４のレコードにコピーされる。このレコードのデュアルは０であるので、そのリソース・ポインターはヌルにセットされ、そのハンドル値は８にセットされる。
【００５８】
二番目の例として、表７に示されたインデックス１のレコードはハンドル値が１である。この値を大きなアレー・サイズ（８）で割った余りをとると１になるので、表８に示されるように、このレコードは、大きなアレーでインデックスが１のレコードにコピーされる。このレコードのデュアルはレコード５であるから、そのリソースポインターをゼロにセットし、そのハンドル値を５（１＋４）にセットする。
【００５９】
前節で述べたように、使用されないレコードが補助構造の中で保持される場合、新しい使用されないレコードはその構造に挿入される。
【００６０】
もしも、上で述べたように、アレーのサイズがある乗数定数だけ増やされるとすると、アレーは幾何的に増大するが、これはハンドルを発行する平均時間がある定数に漸近的に跳ね上がるという非常に望ましい性質を持つ。具体的には、上の例で、あるハンドルを発行するという一つの要求に応答してアレー・サイズが４から８に増えたことを考えよう。このためには４レコードをコピーし、新しい４レコードを初期化する必要がある。次の３ハンドル割り当てはアレーの拡張を必要としないので、これらの４ハンドルの各々を発行する平均コストは、１コピーと１初期化である。同様にハンドルが何も解除されなければ、次の割り当てはアレー・サイズを８から１６に増やすことになり、８コピーと８初期化が必要になる。次の７ハンドルの割り当てはアレーの拡張を必要としないので、これらの８ハンドルの各々を発行する平均コストは１コピーと１初期化である。この一連のオペレーションの間にハンドルが解除されれば、割り当て当たりの平均コストはもっと低くなるだろう。このように、アレーは幾何的に増大し一つのハンドルを発行する平均時間は漸近的にある定数に跳ね上がる。
【００６１】
表８は、また、上述の補助サブルーチン４０２のｎｅｘｔ＿ｒｅｃｏｒｄフィールドを示している。表６では、ｎｅｘｔ＿ｒｅｃｏｒｄフィールドは、あるレコードへのポインターとして定義されているが、表８では分かり易くするためにそれがレコードのインデックスとして示されている。補助サブルーチン４０２の目的は、使用されていないレコードを、ほぼハンドル値で分類されるリストに保管することである。表８では、使用されていないレコードのリストは完全にソートされて示されているが、これは理想的であるけれども保証される挙動ではない。リストの先頭はインデックス５のレコードであり、その情報はサブルーチン４０２によって表自体とは別の場所に格納されている。表８に見られるように、インデックス５のレコードはハンドル値が５であり、これはデータベースの使用されていない最小のハンドル値である。このレコードは、０のｎｅｘｔ＿ｒｅｃｏｒｄ値を有し、使用されていないレコードのリストの中で次のレコードはインデックスが０のレコードであることを示し。それはハンドル値８を有する。このレコードは、値が３のｎｅｘｔ＿ｒｅｃｏｒｄを有し、これは使用されていないレコードのリストの中の次のレコードが、インデックスが３のレコードであることを示す。それはハンドル値が１１である。このレコードは、値が６のｎｅｘｔ＿ｒｅｃｏｒｄを有する。これは使用されていないレコードのリストの中の次のレコードが、インデックスが６のレコードであることを示し、それはハンドル値が１４である。このレコードは、値がヌルのｎｅｘｔ＿ｒｅｃｏｒｄを有し、これはリストの中で使用されていないレコードの中の最後のものであることを示している。このように、割り当てられていないハンドル値のリストは｛５，８，１１，１４｝の順序であり、それは正しく格納されていることが分かる。割り当てられたハンドル値を持つ全てのレコードは、ｎｅｘｔ＿ｒｅｃｏｒｄ値がヌルである。
【００６２】
データベース縮小
以下のセクションで、縮小サブルーチン４３４を説明する。ハンドル・データベースの縮小は必要ないが、ハンドル・アドミニストレータのメモリフットプリンタ（ｆｏｏｔｐｒｉｎｔ）が不足している場合に特に望ましいことがある。縮小サブルーチン４３４はシステムメモリを解放する。保存に利用できるレコードより多くのハンドルが必要な場合、データベースを拡張サブルーチン４０４で拡張しなければならない。しかしながら、ハンドルを解除すると、レコードよりはるかに少ないハンドルしか必要ない状況が生じることがある。これによって直接的な機能的問題は生じないが、間接的な問題、すなわち必要以上のシステムリソース（特にメモリ）の消費が生じる。
【００６３】
例として、通常はある時点で約１０個のアクティブなハンドルがあり、上述のバイナリ拡張でアレイサイズが１６になるシナリオを考える。短期間でアクティブなハンドルの数が１０００に増えると、アレイサイズは１０２４に増える。この短いバーストが終わると、アクティブなハンドルの数は１０に減少するが、アレイサイズは１０２４のままであるため、ハンドル・アドミニストレータが消費するメモリの９９％は無駄になる。
【００６４】
本発明はそのため、ハンドル・データベースを縮小するための縮小サブルーチン４３４を含む。拡張サブルーチンの逆に似ているが、縮小サブルーチンには複雑な追加がある。まず、通常はデータベースの拡張が可能な場合（より多くのメモリを割り当てられると想定）、場合によっては、アクティブなハンドルの数がアレイサイズの半分以下でもデータベースの縮小が不可能である。表９に示すハンドルレコードのアレイを考える。
【００６５】
【表９】
0004290336.tif 000010
【００６６】
このサイズ８のアレイにはアクティブなハンドルは４個だけである。アレイのサイズを４に縮小すると衝突が生じる。特に、ハンドル１およびハンドル５はいずれもそれらのレコードについて同じアレイインデックスを生じる（１  ｍｏｄ  ４＝  ５ｍｏｄ  ４＝１）。言いかえると、これらは互いのデュアルで、共に割り当てられているので、もしアレイサイズが４に減少されると衝突する。互いのデュアルであり、いずれも割り当てられる２個のレコードを、これより「割り当て済みペア」と称する。一般に、ハンドル・アレイは表８に示すアレイのように割り当て済みペアがない場合のみ縮小可能である。
【００６７】
データベース中の割り当て済みペアの数は次のプロセスで追跡可能である。データベースを初期化するか、拡張した時、割り当て済みペアの数をゼロにセットする。デュアルが割り当て済みハンドルを持つレコードからハンドルが発行されると常に割り当て済みペアの数は１つだけデクリメントされる。縮小後の割り当て済みペア個数の再計算については以下で詳細に説明する。
【００６８】
さらに、縮小サブルーチンについては最小アレイサイズの制約がある。明らかに、サイズが１ではアレイは縮小できないが、最小アレイサイズにはより大きい値を設定するのが望ましい。すなわち、本発明の望ましい方法には、２の最小アレイサイズが必要で、そのためにアレイは少なくとも縮小サブルーチを利用する前にサイズが４でなければならない。縮小サブルーチンのほかの制約も望ましく、以下のセクションで詳細に説明する。
【００６９】
縮小サブルーチンには、表１０に示すように各レコードに新しいフィールドを追加することが必要である点に留意されたい。
【００７０】
【表１０】
0004290336.tif 000011
【００７１】
新しいフィールド、ｎｅｘｔ＿ｈａｎｄｌｅは、レコードから発行される次のハンドル値を保持する。レコードが未使用の場合、この値はハンドル値と等しい。レコードが使用されていると、この値はアレイサイズの倍数でハンドル値より大きくなる。ｎｅｘｔ＿ｈａｎｄｌｅフィールドの入ったレコードのアレイを表１１に示す。この例のアレイを縮小の説明に用いる。
【００７２】
【表１１】
0004290336.tif 000012
【００７３】
割り当て済みハンドルを含まない５個のレコードがハンドルおよび等しいｎｅｘｔ＿ｈａｎｄｌｅフィールドを有し、割り当て済みハンドルを有する３つのレコードがハンドルおよび異なるｎｅｘｔ＿ｈａｎｄｌｅ値があることに注意する。デフォルトで、レコードのハンドル値とそのｎｅｘｔ＿ｈａｎｄｌｅ値との差は現在のアレイサイズに等しい。
【００７４】
この新しいフィールドに関与するハンドル割り当てと解除についてこれから説明する。例えば、レコード０をハンドル発行に選択すると、発行されたハンドルの値は８に、ｎｅｘｔ＿ｈａｎｄｌｅフィールドはアレイサイズだけインクリメントされて値は１６になる。さらに、ハンドル値８が解除されると、レコード０のハンドルフィールドがレコード０のｎｅｘｔ＿ｈａｎｄｌｅフィールドで更新され、値は１６になる。故に、ｎｅｘｔ＿ｈａｎｄｌｅフィールドの使用はハンドル値のインクリメントを前のセクションで説明したアレイサイズで２つのステップに分割することになる。
【００７５】
ｎｅｘｔ＿ｈａｎｄｌｅフィールドとそれを縮小に利用する必要性を以下に説明する。まず、表１２に縮小完了後のアレイの状態を示す。
【００７６】
【表１２】
0004290336.tif 000013
【００７７】
縮小サブルーチンは各レコードの３つのフィールドすべてを設定する。特に、リソースフィールドについては、対応するデュアルがいずれも使用されていない場合、リソースポインタをヌルに設定する。そうでない場合、リソースポインタを使用中のレコードのリソースポインタに設定する。例えば、小さい方のアレイでレコード０のリソースポインタを設定するには、大きい方のアレイで２個の対応するデュアルレコード（０および４）を調べる。どちらも使用していないため、該当する値はヌルポインタである。別の例では、小さい方のアレイでレコード１のリソースポインタを設定するには、大きい方のアレイで２個の対応するデュアルレコード（１および５）を調べる。レコード５が使用されているため、該当する値は大きい方のアレイのレコード５からコピー、すなわち、リソースＥへのポインタとなる。
【００７８】
ｎｅｘｔ＿ｈａｎｄｌｅフィールドについては、次のハンドルフィールドの大きい方を各対応するデュアルから選択し、小さい方のアレイのサイズをこの値から減算する。例えば、小さい方のアレイのレコード０のｎｅｘｔ＿ｈａｎｄｌｅフィールドを設定するには、大きい方のアレイの２個の対応するデュアルレコード（０および４）を調べる。ｎｅｘｔ＿ｈａｎｄｌｅフィールドはそれぞれ８と４であり、このうちの大きい方は８なので、８の値を選択してから、小さい方のアレイのサイズを８から減算して４の値を得る。
【００７９】
この手順によって新しいレコードから発行された次のハンドルの値が既に発行・解除されているハンドル値と同一にならないようにする。例えば、大きい方のアレイのインデックス１のレコードのハンドル値は１７で、このレコードが以前にハンドル値９（＝１７−８）を発行していることを意味する。故に、このアレイを縮小して新しいレコードのｎｅｘｔ＿ｈａｎｄｌｅフィールドを１３に設定すると、ハンドル値９は再発行されない。反対に、ｎｅｘｔ＿ｈａｎｄｌｅフィールドをレコードに追加していないと、ハンドル５を解除した後、このレコードから発行される次のハンドル値は９（＝５＋４）と計算されることになる。
【００８０】
発行されたことのないハンドル値は除去できることに注意されたい。例えば、大きい方のアレイのインデックス６のレコードのハンドル値は３０で、このレコードが以前にハンドル値２２（＝３０−８）を発行していることを意味する。そのため、アレイを縮小すると、小さい方のアレイのレコード２のｎｅｘｔ＿ｈａｎｄｌｅフィールドは２６に設定され、ハンドル値２２が再び発行されるのを防ぐ。しかしながら、このｎｅｘｔ＿ｈａｎｄｌｅ値もまた、以前に発行されていないのにハンドル値１８が発行されるのを防ぐ。しかし、アレイの縮小はデータベースの空間要件を減らすために実行するので、このような情報を保存できる空間も減る。実験から、高度に変動するアレイサイズでも、ハンドルをランダムに解除すれば、ハンドル値は縮小のない場合より約１２％から１６％速く消費されることがわかっている。
【００８１】
各レコードのハンドルフィールドを次の手順で設定する。対応するデュアルのいずれも使用されていない場合、ハンドル値をレコードのｎｅｘｔ＿ｈａｎｄｌｅフィールドに等しく設定する。そうでない場合、ハンドル値は使用中のレコードのハンドルフィールドに設定する。例えば、小さい方のアレイのレコード０のハンドル値を設定するには、大きい方のアレイの２個の対応するデュアルレコード（０および４）を調べる。いずれも使用されていないため、ハンドル値は次のハンドル値、すなわち４に設定する。別の例として、小さい方のアレイのレコード１のハンドル値を設定するには、大きい方のアレイの２個の対応するデュアルレコード（１および５）を調べる。レコード５が使用中なので、ハンドル値を大きいほうのアレイのレコード５からコピーし、特に値を５とする。
【００８２】
縮小プロセスの完了には追加ステップ、すなわち割り当て済みペア個数の再計算が必要である。このプロセスは簡単で次の通りである。サブルーチンがアレイの半分まで繰り返され、各ステップにおいて、レコードとそのデュアルがいずれも割り当て済みだと、サブルーチンは割り当て済みペア個数をインクリメントする。この手順の前に割り当て済みペア個数をゼロにする必要はないことに注意されたい。縮小を生じさせるために既にゼロにする必要があるからである。この手順は、アレイが２個のレコードより小さくなることがなく、アレイ中の各レコードにデュアルがある場合はやや簡単になる。
【００８３】
このセクションで説明する手順には、任意のレコードを割り当てるか否かの判断が必要なことに注意されたい。レコードの割り当て状態を示すものがレコードの入ったリストのみであれば、この状態は判断には比較的高価となる可能性がある。それは、リスト全体を検索する必要があるからである。しかし、前のセクションに示すように、そのリソースポインタをヌルに設定することでレコードを未割り当てとみなすことができ、それによりレコードの割り当て状態を速くコンスタントに判断できるようになる。この技術の潜在的な問題は、コンシューマーがヌルポインタにハンドルを割り当てたいと望む場合、そうすることでハンドル・アドミニストレータがレコードが割り当て済みか否かの判断を誤ってしまう点である。上述のように、レコードが未割り当てだと、ｎｅｘｔ＿ｈａｎｄｌｅ値はそのハンドル値と等しい。反対に、レコードが割り当て済みだと、ｎｅｘｔ＿ｈａｎｄｌｅ値はそのハンドル値と等しくない。この条件は、本発明によってレコードが割り当て済みか否か判断することでチェックする。
【００８４】
縮小機会の改善
前のセクションで述べたように、ハンドルアレイを縮小するためには縮小したアレイに適合するハンドル以上のアクティブなハンドルがないことだけでなく、さらにアレイが割り当て済みペアを含まないことが必要である。アレイサイズが大きくなるにつれて、これは漸進的にあり得なくなる。ｎ個のハンドルのランダム構成がｍサイズのアレイに割り当て済みペアを生じない確率は次の公式で与えられる。
Ｐ（ｍ，ｎ）＝１−Ｕ（ｍ，ｎ）／Ｃ（ｍ，ｎ）
【００８５】
Ｃはｍおよびｎの２項係数、Ｕは次の漸化で与えられる。
Ｕ（ｍ,ｎ）＝Ｃ（ｍ−２,ｎ−２）＋２Ｕ（ｍ−２,ｎ−２）＋Ｕ（ｍ−２,ｎ）
Ｕ（２，０）＝０；Ｕ（２，１）＝０；Ｕ（２，２）＝１；
この式は、ｍおよびｎの値が大きくなるにつれ、評価が計算的に高価になる。しかしながら、十分小さい値については、表１３が各種アレイサイズと各種割り当て済みハンドル数に割り当て済みペアが存在しない確率を示す。
【００８６】
【表１３】
0004290336.tif 000014
【００８７】
表１３からわかるように、アレイサイズが３２だと、ランダムな１６個の割り当て済みハンドルのセットに割り当て済みペアがない確率は千分の１しかない。故に、このようなアレイは３２個のレコードから１６個のレコードに縮小するのが望ましいが、これを達成できる可能性は低い。割り当て済みハンドルの数が８に下がると、アレイをサイズ１６に縮小できる確率は３１％に上がるが、さらにサイズ８まで縮小できる確率はわずか２％である。
【００８８】
縮小を可能にする条件が自ら発生する可能性は比較的低いため、この条件を積極的に追求するのが望ましい。ハンドル・アドミニストレータはハンドルの解除は管理できないが、どのレコードからハンドルを割り当てるかは管理できるため、これが割り当て済みペアの予想数を減らす方法となる。
【００８９】
例えば、表９に示すハンドルアレイを考える。１組の割り当て済みレコードペア、すなわちインデックス１および５のものしかない。これらハンドルのいずれかの解除の前に、リソース・マネージャが新しいハンドルの発行を要求したとする。上述の補助サブルーチンに従って、選択したレコードは最低ハンドル値、すなわちレコード３のものでなければならない。しかしながら、レコード３を選択し、ハンドル１を解除すると、アレイを縮小できない。これは、まだ割り当て済みレコードペア、すなわちインデックス３および７のものがあるからである。そのため、割り当て済みペアを生成することはデータベース縮小能力の妨げとなる。そうでない場合、ハンドルをインデックス０のレコードまたはインデックス４のレコードから発行すると、割り当て済みペアは生成されず、ハンドル１が解除されたとき、アレイを縮小できる。低ハンドル値なので、インデックス０ではなくインデックス４を選択しなければならない。
【００９０】
結果として、可能であれば、ハンドルは割り当てペアを生成しないレコードから発行しなければならない。この要件を実現する唯一の方法は、未使用レコードの２つのリスト、１つは割り当て済みペアを生成しなくともハンドルを発行できるレコードの入ったものと、ハンドルの発行で割り当て済みペアを生成するレコードの入ったものを保持することである。そして、最初のリストが空の場合のみ第２のリストからハンドルを発行する。
【００９１】
例として、表９に示すハンドルアレイでは、第１のリストにはレコード４しか入っていないが、第２のリストにはレコード０、３および６が入っている。レコード０が第１リストではなく第２リストにある理由は、レコード４から一度ハンドルが発行されると、低レコード０からハンドルを発行することで割り当て済みペアが生成されるためである。低ハンドル値なので、レコード０ではなくレコード４が第１リストにある。
【００９２】
ハンドル１を解除すると、レコード１’のデュアル（レコード５）に割り当て済みハンドルがあるので、レコード１が第２リストに入れられる。ハンドル１０を解除すると、レコード２のハンドル値はアレイサイズだけインクリメントされて１８になり、これはそのデュアル（レコード６）のハンドル値（２２）より小さいので、レコード２は第１リストに入れられる。ハンドル７を解除すると、レコード７のハンドル値はアレイサイズだけインクリメントされて１５になり、これはそのデュアル（レコード３）のハンドル値（１１）より大きいので、、レコード７は第２リストに入れなければならず、レコード３は第２リストから第１リストに入れ替えなければならない。レコード３は第２リストの任意の位置に入れられるため、リストが二重にリンクされている場合のみ効率的に取り除かれる。このようにして、新しいフィールドを表１４に示すように各レコードに追加する。
【００９３】
【表１４】
0004290336.tif 000015
【００９４】
新しいフィールド、ｐｒｅｖ＿ｒｅｃｏｒｄはレコードへのポインタで、未使用のレコードがそれぞれこのフィールドを使用してリスト上の前のレコードを指定する。
【００９５】
縮小を実行した後、各レコードには以前と異なるデュアルがある。例えば、表１２では、レコード０のデュアルはレコード２であるが、縮小前はそのデュアルはレコード４であった。同様に、レコード１のデュアルはレコード３であるが、縮小前はそのデュアルはレコード５であった。このように、各未使用レコードがどのリストに属するかは新しいペア配置に従って決定する。
【００９６】
表１１に示すアレイを表１２に示すアレイに縮小する例に戻ると、縮小前、第１リストにはレコード４が入っている。また、第２リストにはレコード０、１および６がこの順で入っている（これらは正しく並べられていると想定し、可能性は高いが保証はしない）。縮小後、未使用のレコードのみが縮小前の第１リストのレコードに対応するものである。例では、縮小前レコード４は第２リストにのみあり、対応する縮小後レコードはレコード０で、表１２からわかるように、縮小後の未使用レコードのみである。
【００９７】
リストの順を保持することが望ましいため、本発明のこのサブルーチンで新しい第１および第２リストを２つのステップで生成する。まず、新しい割り当て済みペア個数の計算と合わせて、各レコードとそのデュアルにそれらが属するリストを示すタグをつける。第２に、古い第１リストに対して繰り返すことにより、各レコードを表示リストに入れる。
【００９８】
縮小ヒステリシス
前のセクションでは、アレイを縮小できる頻度を上げるメカニズムを提示した。以下のセクションでは、可能になるポイントを超えるとアレイの縮小を遅延させる縮小ヒステリシスサブルーチン４３６を説明する。
【００９９】
上述のように、アレイを幾何学的に拡張すると、ハンドル発行の平均時間は漸近的に定数になる。しかしながら、アレイを拡張する場合、同様には縮小は保証されない。例えば、アクティブなハンドルの数が４でアレイサイズも４である例を考える。別のハンドルを発行すると、アレイはサイズ８に拡張され、４個のレコードをコピーし、４個のレコードを初期化する必要が生まれる。そしてこの新しいハンドルを解除すると、アレイはサイズ４に再び縮小されて、４ペアのレコードをマージする必要が生じる。このシーケンスは、際限なく繰り返され、アクティブなハンドルの数が４と５の間で振動するため、各割当が４個のコピーと４個の初期化を必要とする。あるいは、アレイサイズが８と９の間で振動する場合、各割当には８個のコピーと８個の初期化が必要となる。一般に、縮小をできるだけ速く実行すると、割り当ての平均計算コストは定数ではなくアクティブなハンドル数の線形関数によって定まる。
【０１００】
割り当てと解除の平均計算コストは、該当するヒステリシスを縮小オペレーションに追加することで定数値に返すことができる。ヒステリシスを実現する方法は次の通りである。計算デット（ｄｅｂｔ）値を保持する。まず、この値をゼロに設定し、拡張オペレーションを実行するたびに値をエントリー分割オペレーションの数だけ増加する。ここで、エントリー分割は１つのエントリーコピーと１つのエントリー初期化を有する。同様に、縮小オペレーションを実行するたびに、マージしたレコードペア数だけ値を増加する。割り当てまたは解除オペレーションを実行するたびに、計算デットが１だけデクリメントし、デットの値をゼロの下限とする。アレイは、計算デットがゼロに等しい場合のみ縮小される。
【０１０１】
再び上記の例を考えると、アレイサイズは第５ハンドルを割り当てた時に４から８へ増加する。計算デットが以前ゼロだったと想定すると、この拡張によってデットが４に設定され、付随する割り当てが直ちにこれを３にデクリメントする。そしてハンドルが解除されると、このオペレーションはデットを２にデクリメントし、これがゼロより大きいため、アレイは縮小されない。次のハンドルを割り当てる時、アクティブなハンドルの数を５に戻し、これが既にサイズ８であるため、アレイは拡張の必要がなく、この割り当ては計算デットを１にデクリメントする。次の解除で計算デットをゼロにデクリメントするため、アレイは可能なら縮小されるが、この時点で、以前の拡張のコストは前の２つの拡張と２つの縮小に対して償還されている。同様に、この縮小で計算デットが４に増え、マージのコストが将来の割り当ておよび解除オペレーションに対して償還される。
【０１０２】
大きいアレイサイズについては、今説明した計算デットの追跡が非常に効果的である。しかしながら、小さいアレイサイズには、レコードのコピー、初期化およびマージのコストは拡張および縮小のためのメモリ割り当てと割り当て解除のコストに対して小さい。故に、オペレーションあたりの平均計算コストはこのシステムによって一定に保たれるが、この一定値は割り当て／割り当て解除によって許容不可能なほど高くなることがある。この問題に対する単純な解決法は、割り当ておよび割り当て解除オペレーションのコストを、拡張および縮小による計算デットに加えることである。メモリ割り当ておよび割り当て解除のコストは、作業例の特定の実施について１つのレコード修正オペレーションコストの１２倍であると経験的に決定された。故に、この実施については、拡張または縮小オペレーションを実行するたびに計算デットを１２プラス修正したレコードの数の値だけ増加する。
【０１０３】
メモリ割り当ての失敗
メモリ割り当ての試みが失敗することがあり得るため、メモリを割り当てるどのシステム（本発明のような）も割り当ての失敗に対する取り扱いを用意していなければなない。本発明ではメモリを３回、すなわち、初期化、各拡張、各縮小の３回で割り当てる。メモリを初期化で割り当てできない場合、ハンドル・アドミニストレータの作成が失敗する。
【０１０４】
メモリを拡張で割り当てできないと、アレイに余裕のない新しいハンドルの割り当ての試みを失敗させるアプローチとなることは明らかである。代わりのアプローチがあるけれども、これはハンドル・アドミニストレータのセマンティックス（ｓｅｍａｎｔｉｃｓ）の修正に依存する。この時点まで、システムはハンドルが割り当てられたら有効となり、解除されるまで有効であり続けるよう機能している。しかしながら、デリファレンス・ルーチンへのコールがヌル・ポインタを返すことがあるため、各コンシューマーは他のコンシューマーがハンドルを解除してしまったからというだけでもハンドルが無効になる用意をしておかなければならない。故に、新しいセマンティックスはハンドル・アドミニストレータにハンドル取消しの権限を与え、これによってハンドルはコンシューマーが解除したかのように無効となる。
【０１０５】
この権限を与えられると、ハンドル・アドミニストレータは現在、割り当てられているハンドルの１つを取消してから、このレコードから新しいハンドルを割り当てることで失敗したメモリ割り当てに対処することができる。このアプローチは、新しいハンドルがだいぶ前に割り当てられたハンドルよりも使用される可能性が高いので、望ましい。この考えから、このような状況で取り消すハンドルは最も古い割り当て済みハンドルでなければならないことを示すが、これにはハンドルを割り当てた順番を記録しておかなければならない。各レコードは他のレコードに対するペアのポインタを含み、各未割り当てのレコードは２つのリストの１つに存在する。この時点まで、割り当て済みレコードはどのリストにも存在しないが、これらを割り当て順になるよう１つに入れるのは瑣末なことである。レコードを割り当てるたび、これがリストの末尾に入れられる。レコードを解除すると、これがリストから除去され、レコードをメモリ割り当て失敗のために取り消す時は、リストの先頭から取り除く。メモリを縮小のため割り当てられない場合、縮小は単に実行されない。アレイの縮小はまったく必要なく、前のセクションで説明した他の理由で遅延可能であるため、割り当て失敗に対するこの応答は許容可能である。
【０１０６】
ハンドル・リサイクリング
概要セクションで述べたように、ハンドルは未署名の整数である。整数のサイズが、例えば３２ビットであるなら、発行できるユニークなハンドルは４０億ほどしかない。あるシナリオでは、これは十分である。しかし他のシナリオではそうではないことがある。例えば、ハンドルの割り当てと解除を非常に頻繁に行う長寿命のシステムではハンドルスペースを消耗する可能性がある。この問題に対する１つの代替はハンドルを大きくすることであるが、これが実用的でなかったり十分でない場合がある。もう１つの代替は、エージェントには、ハンドルが無効になったためこれらを再びデリファレンスしないことに気づく機会が十分あったとの理論により、長期間無効だったハンドルのリサイクルにリサイクルハンドルサブルーチン４０６を利用することである。ハンドルリサイクルサブルーチン４０６はオプション機能である。
【０１０７】
ハンドルリサイクルサブルーチン４０６は、効率的なハンドルリサイクルを行う。レコードのハンドル値が表現可能範囲を超える値に増加すると、その大きい値を表現可能範囲の値の数で割った余りに等しい値に「ラップアラウンド」する。例えば、ハンドル値（１６進）がＦＦＦＦＦＦＦＡで、これが８だけ増える（これがアレイサイズと想定）とすると、結果は２で、これがおそらく４０億のハンドル発行前に発行されたハンドル値になる。しかしながら、このハンドル値がずっと前に発行されたとしても、解除はほんの最近だった危険性もある。故に、このハンドルを持つコンシューマーはハンドルが無効になったことに気づく機会を持たなかったかもしれない。この潜在的な問題に対する解決法は、設定したカットオフより古くなったあらゆるハンドルを取り消して、ハンドルが無効になったことにコンシューマーが気づく十分な機会を持てるようにすることである。
【０１０８】
このように、図４のハンドルリサイクルサブルーチン４０６は定期的に非常に古いハンドルを取り消す。図５〜図７は本発明のハンドルリサイクルサブルーチン４０６を視覚的に表した図である。ハンドル・データベース５００は最大ハンドル範囲５１０、ハンドルベース５２０、ベース値５２０プラス最大ハンドル範囲に設定した閾値ハンドル５２５およびハンドル範囲ステップ５２８を含む。以下の例では、ハンドルは１６ビット整数、最大ハンドル範囲５１０は（１６進）９０００、ハンドル範囲ステップ５２８は（１６進）２０００と想定する。最初、ハンドルベース値５２０を０に設定し、閾値５２５をベース値５２０プラス最大ハンドル範囲５１０に設定するが、この場合は９０００である。図５〜図７の陰部分５３０は、割り当て済みハンドルの有効範囲を示し、これは図５で０から約２４００と示されており、発行された最大ハンドル値が約２４００であることを意味する。
【０１０９】
さらにハンドルを発行すると、割り当て済みハンドル５３０の範囲が図６および７の割り当て済みハンドル６３０および７３０のように増える。すなわち、図５と図６および図７を参照すると、閾値５２５より大きいハンドル値を発行した場合、システムはアレイのレコードをすべてスキャンして、あらゆるハンドル（この場合０）からハンドルベース５２０プラスハンドル範囲ステップ５２８（この場合２０００）までの範囲のあらゆるハンドルを取り消す。そしてハンドルベース５２０と閾値５２５とをハンドル範囲ステップ５２８だけ増やして、図６に示すような新しいハンドルベース６２０および閾値ハンドル６２５とする。
【０１１０】
あらゆる可能性の中で、この範囲にはほとんど（おそらく１つも）ハンドルがないため、この手順の実際の効果は、ハンドル・アドミニストレータ外からは見えないことが多い。この手順を完了したら、次の閾値６２５に達するまでハンドルの発行が続行されて別の取り消すパスを実行する。結果的に、ハンドルベース７２０の増加によって、閾値７２５が図７に示すように最大値５５０をラップアラウンドする。
【０１１１】
さらに、比較修正を使用することにより、値をラップアラウンドした後でもハンドル値の比較を正しく実行する。上述の方法の数カ所で、２つのハンドル値を比較し、どちらか大きい方を決定する。ハンドル値をラップアラウンドできる場合、この比較を絶対比較としてではなくハンドルベース値に関連させる。例えば、図７に示すシナリオの２個のハンドルＥ３２０と１１６２を考える。標準比較では、Ｅ３２０が大きい方の値と結論する。しかしながら、図７からわかるように、この値は実際にはハンドルベース値に対して他のものより小さい。いいかえると、ハンドルベースがゼロになるまで範囲をシフトすると、このハンドルが小さくなる。
【０１１２】
この比較は、まず各ハンドル値からハンドルベース値を減算してから結果を比較することで正しく実行できる。Ｅ３２０−Ｃ０００＝２３２０および１１６２−Ｃ０００＝５１６２で、２３２０は５１６２より小さい。減算は、加算が実質的にラップアラウンドするのと同じ理由で実質的にラップアラウンドすることに注意されたい。すなわち、それはデジタルコンピュータでの整数マス（ｍａｔｈ）の副産物である。
【０１１３】
マルチスレッド
ハンドル・アドミニストレータは、割り当て、解除、デリファレンスルーチン３１０、３１４、３１２それぞれについてマルチスレッドサブルーチン４２６、４３７、４３８のあるマルチスレッド環境で展開される。マルチスレッド環境での衝突の可能性があるため、異なるスレッドが共通のデータ構造を利用する場合に互いに干渉することを防ぐロックを採用するのが一般的である。一般的でシングルアクセスおよびシングルライター／マルチリーダーである２つのロック方法がある。シングルアクセスロックでは、スレッドとデータベースの関係に無関係に、１つのスレッドのみいつでもデータベースにアクセスできる。シングルライター／マルチリーダーでは、１つのスレッドが読み書き特権を持ってデータベースにアクセスできるか、あらゆる数のスレッドがリードオンリー特権でデータベースにアクセスできる。第２のタイプのロックは明らかに制約が少ないため、サポートできれば望ましい。本発明には、さらに制約の少ない形のロックが可能なメカニズムが含まれる。この場合、１つのスレッドのみ読み書き特権でデータベースにアクセスできるが、あらゆる数の他のスレッドは、書きこみアクセスの途中でも読み取りアクセスでデータベースにアクセスできる。
【０１１４】
特に、システムにはロックが含まれる。ａｓｓｉｇｎ  ｈａｎｄｌｅ（）ルーチンを呼び出すため、まずこのロックを取る。ｒｅｌｅａｓｅ  ｈａｎｄｌｅ（）ルーチンを呼び出すため、まずこのロックを取る。しかし、ロックはｄｅｒｅｆｅｒｅｎｃｅ  ｈａｎｄｌｅ（）を呼び出すため取る必要はない。これはこのセクションで説明するように２つの異なるテクニックによって実現される。
【０１１５】
まず、マルチスレッドによって問題が生じるかもしれない状況を考える。ある状況下ではｄｅｒｅｆｅｒｅｎｃｅ  ｈａｎｄｌｅ（）ルーチンが、他のスレッドで発生しているｒｅｌｅａｓｅ  ｈａｎｄｌｅ（）の呼出によって無効にされるプロセス内にあるハンドルを有効にしようとすることが発生する。正しい挙動では、システムは２つのオペレーションが実際には部分的に重なっていても順次発生するよう動作する。解除前にデリファレンスが発生すると、有効なポインタが返される。解除後にデリファレンスが発生すると、ヌルポインタが返され、ハンドルが有効でないことを示す。マルチスレッドの危険性は、無効なポインタが返されることである。これはロックを使わず、読み書きオペレーションを注意して順序付けることで回避できる。ｄｅｒｅｆｅｒｅｎｃｅ  ｈａｎｄｌｅ（）ルーチンは次の順でステップを実行する。
・レコードからポインタの値を読み取り、ローカルに保存する。
・レコードからハンドルの値を読み取り、パスしたハンドルに対して検証する。
・ハンドルが有効な場合、保存したポインタをローカルに返し、そうでない場合、ヌルポインタを返す。
【０１１６】
代替のさらに自然な順序は、ルーチンでまずハンドルを検証してから、レコードからポインタを読み取る順序である。しかしながら、これら２つのオペレーションの間に、レコードが無効となり、他のポインタに再割当され、デリファレンスルーチンによって誤ったポインタが返される可能性がある。
【０１１７】
上記の状況はハンドルを安全に無効にする問題に関わる。アレイのサイズ変更で別の潜在的問題が発生する。アレイのサイズを変更すると、新しいアレイが割り当てられ、古いアレイからの情報が修正付きで新しいアレイにコピーされる。このコピーの間、古いコピーは無修正のため、ハンドルは引き続き古いアレイを使ってデリファレンスできる。コピーが完了すると、ハンドルはいずれかのアレイを使ってデリファレンスできるため、この時点でシステムは安全にアレイポインタを古いアレイから新しいアレイに切り替えることができ、その後、安全に古いアレイを割り当て解除できる。アレイへのポインタとアレイのサイズを同時に切り替えることが重要である。デリファレンスルーチンでハンドルのレコードをロックするときにこれら値の一致しないセットを用いるものだった場合、ハンドル値から誤ったアレイインデックスを計算してしまう。
【０１１８】
システムは、ベリファイヤ（ｖｅｒｉｆｉｅｒ）と呼ばれる２個の補助変数を利用して２つの値が一致して見えるようにする。通常は、２個のベリファイヤの値は同じだが、アレイポインタとアレイサイズが一致していない時は（拡張および縮小ルーチンによって）異なる値に設定する。ベリファイヤはデリファレンスルーチンによってアレイポインタおよびアレイサイズ変数の一致を判定する。新しいアレイへのレコードのコピーと古いアレイの割り当て解除の間で、拡張および縮小手順が次のステップを順次実行する。
・ベリファイヤ０をインクリメントする。
・アレイポインタとアレイサイズをアップデートする。
・ベリファイヤ１をベリファイヤ０に等しく設定する。
【０１１９】
デリファレンスルーチンは次のステップを順次実行する。
・ベリファイヤ１の値を読み取りローカルに保存する。
・アレイポインタとアレイサイズを読み取る。
・レコードインデックスを計算する。
・インデックス付きレコードからポインタとハンドルの値を読み取る。
・ベリファイヤ０の値を読み取り、ローカルに保存したベリファイヤ１の値と比較する。
・ベリファイヤが一致しない場合、上記ステップをすべて繰り返す。
【０１２０】
上記手順の繰り返しクローズとは、デリファレンスルーチンが他方のスレッドのアレイサイズ変更を待つ間にしばらくスピンしてしまうことを意味する。しかしながら、ベリファイヤが一致しない時間は非常に短いため、これは非常に可能性が低い。
【０１２１】
一体式コンポーネント
以下のセクションに、一体式システム中に上述のコンポーネントを持つ本発明の例を詳述する。図８〜図１５は、上記作業例に説明した通りの、割り当てルーチン、解除ルーチン、デリファレンスルーチン、拡張サブルーチン、縮小サブルーチン、レコード更新サブルーチン、取消しサブルーチン、レコード処理サブルーチンを含む一体式システムである。すべての加算および減算オペレーションは、ハンドルスペースのサイズのモジュロ演算により実質的に実行され、すべての比較オペレーションは、上記セクションでハンドルリサイクルについて説明した通り、ハンドルベース値に対し実行される。
【０１２２】
図８は、本発明の割り当てルーチンを示すフローチャートである。このルーチンを開始し（ボックス８００）、母集団がアレイサイズより小さいか否かを判断する（アレイのエントリーは現在未割り当てか？）（ボックス８０２）。母集団がアレイサイズより小さい場合、拡張サブルーチンでアレイを拡張する試み（図１１Ａおよび１１Ｂ参照）を実行する（ボックス８０４）。そして拡張が成功したか否か判断する（ボックス８０６）。拡張が成功しないと、ルーチンのオペレーションはシステムがどう構成されたかで決まる。すなわち、ハンドル・アドミニストレータが発行済みハンドルを取り消すことができないようシステムが構成されている場合、ルーチンは失敗コードと共に（ボックス８１０への点線）リターンする。しかし、ハンドル・アドミニストレータに発行済みハンドルを取り消す権限が与えられて構成されている場合、メモリ割り当て失敗サブルーチンを実行する（ボックス８０８）。メモリ割り当て失敗サブルーチンは最も古く割り当てられたハンドルを取消し、新しいハンドル割り当てのためにハンドル・データベースのエントリーを解放する。この取消しは最も古く割り当てられたレコードを割り当て済みリストから第２リストに移動し、レコードのハンドルを次のハンドルに等しく設定し、割り当て済みペア個数をデクリメントし、母集団をデクリメントすることによって実行する（ボックス８０８）。
【０１２３】
母集団のデクリメントの後か、または（ボックス８０８）、データベース拡張に成功するか（ボックス８０６）あるいは母集団がアレイサイズより小さい場合（ボックス８０２）、縮小機会を改善するステップが実行される。これにはまず、第１リストが空であるか否かを判断する（ボックス８１２）。第１リストが空でない場合、第１リストを指定する（ボックス８１４）。第１リストが空の場合、第２リストを指定し、割り当て済みペア個数をインクリメントする（ボックス８１６）。いずれの場合も、次に、レコードは指定リストの先頭から割り当て済みリストの末尾に移動される。レコードのリソースポインタを設定し、レコードの次のハンドルをアレイサイズだけインクリメントし、母集団をインクリメントし、計算デットを縮小ヒステリシスについてゼロに定め、デクリメントする（ボックス８１８）。そして、ハンドル値は閾値より大きいか否かを判断する（ボックス８２０）。ハンドル値が閾値より大きい場合、古いハンドルの取り消しサブルーチンを実行し（図１４参照）（ボックス８２２）、レコードのハンドルを返す（ボックス８２４）。しかし、ハンドル値が閾値より大きくない場合、レコードのハンドルは古いハンドル取消しサブルーチンを実行せずに返す（ボックス８２４）。
【０１２４】
図９は、本発明の解除ルーチンを示すフロー図である。機能が開始し（ボックス９００）、レコードインデックス（ボックス９０２）を計算する。次に、レコードがハンドルと一致するか否か判断する（ボックス９０４）。レコードがハンドルと一致しないと、失敗コードが返され（ボックス９０６）、ハンドルが無効であることを示す。レコードがハンドルと一致すると、レコードのデュアルが割り当てられたと判断される（ボックス９０８）。
【０１２５】
レコードのデュアルが割り当てられていないと、デュアルの次のハンドルがレコードの次のハンドルより小さいか否か判断する（ボックス９１０）。デュアルの次のハンドルがレコードの次のハンドルより小さくない場合、第１リストを指定する（ボックス９１２）。デュアルの次のハンドルがレコードの次のハンドルより小さい場合、デュアルは第２リストから第１リストの末尾に移動し、第２リストを示す（ボックス９１４）。しかし、レコードのデュアルが割り当てられていると（ボックス９０８で判断）、第２リストを示し、割り当て済みペア個数をデクリメントする（ボックス９１６）。
【０１２６】
第１リストが指定されるか（ボックス９１２）、第２リストが指定されるか（ボックス９１４）、さもなくば割り当て済みペア個数をデクリメントした後（ボックス９１６）、割り当て済みリストからレコードを指定リストの末尾に移動し、レコードのハンドルを次のハンドルに等しく設定し、母集団をデクリメントし、計算デットをゼロに定め、デクリメントする（ボックス９１８）。次に、アレイサイズが２より大きいか否か、割り当て済みペア個数がゼロに等しいか否か、デットがゼロに等しいか否か判断する（ボックス９２０）。上記全てが真なら、縮小サブルーチンを呼び出す（図１２Ａおよび１２Ｂ参照）（ボックス９２２）。縮小が成功すると、有効な成功コードを返す（ボックス９２４）。ボックス９１８のステップが偽なら、サブルーチンは成功コードを返す（ボックス９２４）。
【０１２７】
図１０は、本発明のデリファレンスルーチンを示すフローチャートである。機能は、開始してから（ボックス１０００）ベリファイヤ１のローカルコピーを作ることで（ボックス１００２）マルチスレッド環境で動く。次に、レコードインデックスをあるアレイサイズについて計算する（ボックス１００４）。そしてレコードのリソースポインタのローカルコピーを作る（ボックス１００６）。次に、レコードのハンドル値のローカルコピーを作る（ボックス１００８）。そして、ローカル検証コピーがベリファイヤ０に一致するか否か判断する（ボックス１０１０）。ローカルベリファイヤがベリファイヤ０に一致しない場合、上記ステップを繰り返す（ボックス１００２−１００８）。ローカルベリファイヤがベリファイヤ０に一致する場合、レコードのハンドルのローカルコピーがハンドルに一致するか否か判断する（ボックス１０１２）。レコードのハンドルのローカルコピーがハンドルに一致する場合、レコードのポインタのローカルコピーを返す（ボックス１０１４）。しかし、レコードのハンドルのローカルコピーがハンドルと一致しない場合、ヌルポインタを返す（ボックス１０１６）。
【０１２８】
図１１Ａおよび１１Ｂは本発明の割り当てルーチンの拡張サブルーチンを示すフローチャートである。機能が開始し（ボックス１１１０）、ダブルサイズの新しいアレイが割り当てられる（ボックス１１０２）。次に、割り当てが成功したか否か判断する（ボックス１１０４）。割り当てが成功していないと、拡張失敗コードが返される（ボックス１１０６）。割り当てが成功すると、古いレコード変数は古いアレイの第１レコードに設定される（ボックス１１０８）。次に、古いレコードの次のハンドルについて新しいレコードインデックスを計算し、新しいレコードの次のハンドルを古いレコードの次のハンドルに設定し、新しいレコードのデュアルの次のハンドルを古いレコードの次のハンドルプラス古いアレイサイズに設定する（ボックス１１１０）。古いレコードのハンドルについて新しいレコードのインデックスを計算し、新しいレコードのハンドルを古いレコードのハンドルに設定し、新しいレコードのリソースポインタを古いレコードのリソースポインタに設定し、割り当て済みリストの古いレコードを新しいレコードと置き換え、新しいレコードのデュアルのハンドルを新しいレコードのデュアルの次のハンドルに設定する（ボックス１１１２）。次に、古いレコード変数をアレイの次のレコードに設定する（ボックス１１１４）。そして、レコードが枯渇したか否か判断する（ボックス１１１６）。レコードが枯渇していない場合、ボックス１１１０−１１１４ステップを繰り返す。これらステップは、すべてのレコードがなくなるまで繰り返される（ボックス１１１６）。
【０１２９】
レコードがなくなったら、未割り当てのレコードを、割り当て済みリストのデュアルの順で第２リストに入れて、デットをメモリ割り当てプラス古いアレイサイズだけ増やす（ボックス１１１８）。ベリファイヤ０をインクリメントし、アレイサイズおよびアレイポインタを更新し、ベリファイヤ１をベリファイヤ０に等しく設定する（ボックス１１２０）。古いアレイの割り当てを解除し、割り当て済みペア個数をゼロに設定する（ボックス１１２２）。そして拡張成功コードを返す（ボックス１１２４）。
【０１３０】
図１２Ａおよび１２Ｂは、本発明の割り当ておよび解除ルーチンの縮小サブルーチンを示すフローチャートである。機能が開始し（ボックス１２００）、前のアレイの半分のサイズの新しいアレイを割り当て、この同じサイズのタグアレイを割り当てる（ボックス１２０２）。そして、割り当てが成功したかどうか判断する（ボックス１２０４）。いずれの割り当ても成功しなかったら、縮小サブルーチンは終了し、縮小は実行されない（ボックス１２０６）。割り当てが成功したら、低いレコード０変数を古いアレイの第１レコードに設定し、低いレコード１変数を第１レコードから１／４上がった古いアレイのレコードに設定し、高いレコード０変数を第１レコードから１／２上がった古いアレイのレコードに設定し、高いレコード１変数を第１レコードから３／４上がった古いアレイのレコードに設定し、新しいレコード１変数を第１レコードから１／２上がった新しいアレイのレコードに設定する（ボックス１２０８）。ハンドル、次のハンドルおよびリソースポインタを新しいレコード０について設定し、リストの該当するレコードを図１３に詳細に示すように新しいレコード０と置き換える（ボックス１２１０）。次に、ハンドル、次のハンドルおよびリソースポインタを新しいレコード１に設定し、リストの該当するレコードを図１３に詳細に示すように新しいレコード１と置き換える（ボックス１２１２）。そして新しいレコード両方が未割り当てであるかいなか判断する（ボックス１２１４）。新しいレコードが両方とも未割り当てである場合、ハンドル値が小さい方のレコードに第１リストのタグを付け、ハンドル値の大きい方のレコードに第２リストのタグを付ける（ボックス１２１６）。少なくとも１個の新しいレコードが割り当てられたら、両レコードを第２リストについてタグを付けるが（ボックス１２１８）、ルーチンのその後のステップによって実際には未割り当てのレコードのみ第２リストに入れる。そして、新しいレコードが両方とも割り当て済みであるか否か判断する（ボックス１２２０）。新しいレコードのいずれかが割り当て済みでないか（ボックス１２２０）、ハンドル値の大きい方ほレコードに第２リストのタグをつけた後（ボックス１２１６）、または割り当て済みペア個数をインクリメントした後（ボックス１２２２）、各レコードポインタをアレイの次のレコードに設定する（ボックス１２２４）。次に、全てのレコードがなくなったか否か判断する（ボックス１２２６）。レコードがなくなっていなければ、ルーチンはボックス１２１０−１２２４のステップを循環する。しかし、レコードがなくなった場合、未割り当ての現在の未割り当てのリストと同じ順序で各レコードをタグを付けたリストに入れる。デットはメモリ割り当てコストプラス古いアレイサイズだけ増やす（ボックス１２２８）。次に、ベリファイヤ０をインクリメントし、アレイサイズとアレイポインタを更新し、ベリファイヤ１をベリファイヤ０に等しく設定する（ボックス１２３０）。そして古いアレイとタグアレイを割り当て解除し、割り当て済みペア個数をゼロに設定する（ボックス１２３２）。するとサブルーチンがリターンする（ボックス１２３４）。
【０１３１】
図１３は、図１２Ａおよび１２Ｂの縮小サブルーチンのレコード更新サブルーチンを示すフローチャートである。機能が開始し（ボックス１３００）、新しいレコードの次のハンドルが高から低レコードの次のハンドルの大きい方マイナス新しいアレイサイズに設定される（ボックス１３０２）。次に、高または低レコードが割り当て済みか否か判断する（ボックス１３０４）。高または低レコードが割り当て済みだと、割り当て済みレコードのハンドルとリソースポインタを新しいレコードにコピーし、割り当て済みリストの割り当て済みレコードを新しいレコードと置き換える（ボックス１３０６）。しかし、高または低レコードが割り当てられていないと、新しいレコードのハンドルを新しいレコードの次のハンドルに等しく設定し、第１リストで小さい方のハンドル値を持つ古いレコードを新しいレコードと置き換える（ボックス１３０８）。割り当て済みリストの割り当て済みレコードを新しいレコードに置き換えた後（ボックス１３０６）または第１リストの小さい方のハンドル値を持つ古いレコードを新しいレコードに置き換えた後（ボックス１３０８）、サブルーチンがリターンする（ボックス１３１０）。
【０１３２】
図１４は、本発明の割り当てサブルーチンの古いハンドル取消しサブルーチンを示すフロー図である。機能が開始し（ボックス１４００）、低レコード変数をアレイの第１レコードに設定し、高レコード変数を第１レコードから１／２上がったアレイのレコードに設定する（ボックス１４０２）。次に、取消し範囲に少なくとも１個のハンドルがあるか否か判断する（ボックス１４０４）。取消し範囲はハンドルベースから始まり、取消し範囲のサイズはハンドル範囲ステップに等しい。少なくとも１個のハンドルが取消し範囲にある場合、両レコードが割り当てられているか判断する（ボックス１４０６）。両レコードが割り当て済みの場合、割り当て済みペア個数をデクリメントする（ボックス１４０８）。両レコードが割り当てられていないか、割り当て済みペア個数をデクリメントした後（ボックス１４０８）、低レコード（ボックス１４１０）と高レコード（ボックス１４１２）をそれぞれ図１５のステップに従って処理する。次に、レコードが割り当てられているか判断する（ボックス１４１４）。いずれかのレコードが割り当てられてる場合（ボックス１４１４）、他方のレコードを第２リストに入れる（ボックス１４１６）。いずれかのレコードが割り当てられていない場合、ハンドル値の小さい方のレコードを第１リストに入れ、値の大きい方のレコードを第２リストに入れる（ボックス１４１８）。他方のレコードを第２リストに入れるか（ボックス１４１６）、ハンドルの大きい方のレコードを第２リストに入れるか（ボックス１４１８）、少なくとも１個のハンドルが取消し範囲にない場合（ボックス１４０４）、各レコードポインタはアレイの次のレコードに設定する。つぎに、全てのレコードがなくなったか否か判断する（ボックス１４２２）。レコードがなくなっていなければ、上記ルーチンを再び処理する（ボックス１４０４−１４２０）。レコードがなくなっていれば、ハンドル・データベースと閾値をハンドル範囲ステップだけ増やし（ボックス１４２４）、サブルーチンがリターンする（ボックス１４２６）。
【０１３３】
図１５は、図１４の古いハンドル取り消しサブルーチンのレコード処理サブルーチンを示すフローチャートである。機能が開始し（ボックス１５００）、レコードが未割り当てか、取消し範囲内かを判断する（ボックス１５０２）。レコードが未割り当てか取消し範囲内だと、レコードをリストから取り除く（ボックス１５０４）。レコードが割り当て済みか取消し範囲にないか（ボックス１５０２）、レコードをリストから取り除いた後（ボックス１５０４）、レコードハンドルが取消し範囲にあるか判断する（ボックス１５０６）。レコードが取消し範囲にないと、ルーチンは終了する（ボックス１５０８）。レコードが取消し範囲にあると、レコードが割り当て済みか否か判断する（ボックス１５１０）。レコードが割り当て済みだと、母集団をデクリメントする（ボックス１５１２）。レコードが割り当てられていないか（ボックス１５１０）、母集団をデクリメントした後、既に大きくない限りレコードの次のハンドル値をベース値プラスハンドル範囲ステッププラスレコードのインデックスに増やし、ハンドル値を次のハンドル値に等しく設定する（ボックス１５１４）。そしてサブルーチンがリターンする（ボックス１５１６）。
【０１３４】
発明の前述の説明は図解および説明のために提示した。完全あるいは本発明を開示の精密な形式に限定するものではない。上記説明の観点から多くの修正およびバリエーションが可能である。本発明の範囲はこの詳細な説明ではなく添付の特許請求の範囲によって限定される。
【図面の簡単な説明】
次に図面を参照するが、その中で全体にわたって同じ参照数字は対応するパーツを表している：
【図１】  本発明を実行するための装置を示すブロック図である。
【図２】  本発明の主なコンポーネントの相互作用を説明する一般的なブロック図である。
【図３】  本発明のハンドル・アドミニストレータの基本的な動作を説明するフローチャートである。
【図４】  本発明の実施例の主なコンポーネントとサブコンポーネントを階層的に示すブロック図である；
【図５】  本発明のハンドル・リサイクリング・サブルーチンを視覚的に説明する図である。
【図６】  本発明のハンドル・リサイクリング・サブルーチンを視覚的に説明する図である。
【図７】  本発明のハンドル・リサイクリング・サブルーチンを視覚的に説明する図である。
【図８】  本発明の割り当てルーチンを説明するフローチャートである。
【図９】  本発明の解除ルーチンを説明するフローチャートである。
【図１０】  本発明のデリファレンス・ルーチンを説明するフローチャートである。
【図１１Ａ】  本発明の割り当てルーチンの拡張サブルーチンを説明するフローチャートである。
【図１１Ｂ】  本発明の割り当てルーチンの拡張サブルーチンを説明するフローチャートである。
【図１２Ａ】  本発明の解除ルーチンの縮小サブルーチンを説明するフローチャートである。
【図１２Ｂ】  本発明の解除ルーチンの縮小サブルーチンを説明するフローチャートである。
【図１３】  本発明の縮小サブルーチンのレコード更新サブルーチンを説明するフローチャートである。
【図１４】  本発明の拡張サブルーチンの過去ハンドル廃止サブルーチンを説明するフローチャートである。
【図１５】  本発明の過去ハンドル廃止サブルーチンのレコード処理サブルーチンを説明するフローチャートである。
【図１】
0004290336.tif 000016
【図２】
0004290336.tif 000017
【図３】
0004290336.tif 000018
【図４】
0004290336.tif 000019
【図５】
0004290336.tif 000020
【図６】
0004290336.tif 000021
【図７】
0004290336.tif 000022
【図８】
0004290336.tif 000023
【図９】
0004290336.tif 000024
【図１０】
0004290336.tif 000025
【図１１Ａ】
0004290336.tif 000026
【図１１Ｂ】
0004290336.tif 000027
【図１２Ａ】
0004290336.tif 000028
【図１２Ｂ】
0004290336.tif 000029
【図１３】
0004290336.tif 000030
【図１４】
0004290336.tif 000031
【図１５】
0004290336.tif 000032