(57)【特許請求の範囲】
【請求項１】
マルチコアプロセッサのオペレーティングシステム環境内でアクセス可能であるメモリに関するメモリ割当ての方法であって、当該方法は、前記マルチコアプロセッサのメモリ要求部分への前記メモリの割当てを、
複数の区分化されたロックレスリスト構造を取得するステップであり、前記複数の区分化されたロックレスリスト構造の各々が、それぞれの複数のリスト要素を含み、前記それぞれのリスト要素の各々が、割当てに現在適した前記メモリのそれぞれの部分に対応し、前記複数の区分化されたロックレスリスト構造は、前記マルチコアプロセッサのアーキテクチャのトポロジーの要素に対応する複数のキー値の各々への適応ハッシュの適用によって区分化される、ステップと、
前記メモリの前記それぞれの部分のうちの１つ以上を、割当てメモリとしての使用のためにコアプロセッサに割り当てることの要求を受けて、割当てメモリとしての使用のための割当てに現在適した、前記メモリの利用可能なそれぞれの部分に対応する利用可能なリスト要素に関して、前記複数の区分化されたロックレスリスト構造を探索するステップであり、該探索は、前記複数の区分化されたロックレスリスト構造の各々に、それぞれのハッシュにキーイングされる適応ハッシュを用いて実行される、ステップと、
前記利用可能なリスト要素を発見したことを受けて、前記メモリの前記利用可能なそれぞれの部分を、割当てメモリとしての使用のために前記コアプロセッサに割り当てるステップと、
前記メモリの前記割当てを最適化するよう設定された均等化メトリックに従って、前記複数のロックレスリスト構造の間で前記利用可能なリスト要素を動的に均等化するステップと
によって制御することを含む、
方法。
【請求項２】
前記複数の区分化されたロックレスリスト構造を取得するステップは、
イニシャルの複数のリスト要素を含むイニシャルのロックレスリスト構造を取得することであり、前記イニシャルのリスト要素の各々が、割当てに現在適した前記メモリのイニシャルのそれぞれの部分に対応する、取得することと、
前記マルチコアプロセッサの前記アーキテクチャの前記トポロジーの要素に対応する前記複数のキー値の前記各々に前記適応ハッシュを適用することによって、前記イニシャルのロックレスリスト構造を前記区分化されたロックレスリスト構造へと区分化することと
を含む、請求項１に記載の方法。
【請求項３】
前記適応ハッシュは、前記マルチコアプロセッサの前記アーキテクチャの前記トポロジーの要素に従ってキーイングされる、請求項１に記載の方法。
【請求項４】
前記適応ハッシュは、プロセッサインデックスに従ってキーイングされる、請求項１に記載の方法。
【請求項５】
前記適応ハッシュは、ＮＵＭＡノード番号に従ってキーイングされる、請求項１に記載の方法。
【請求項６】
前記均等化メトリックは、前記ロックレスリスト構造の間でメモリ要素の数的均等性を実質的に維持するよう設定されている、請求項１に記載の方法。
【請求項７】
前記均等化メトリックは、メモリ資源の過大な割当てを回避するよう設定されている、請求項１に記載の方法。
【請求項８】
マルチコアプロセッサのオペレーティングシステム環境内でアクセス可能であるメモリのメモリ割当てを、前記マルチコアプロセッサのメモリ要求部分への前記メモリの割当てを制御することによって制御するシステムであって、
前記マルチコアプロセッサのアーキテクチャに従ってキーイングされる適応ハッシュを用いて、イニシャルのロックレスリスト構造を複数の区分化されたロックレスリスト構造へと初期区分化する第１のプロセッサと、
前記複数の区分化されたロックレスリスト構造の間で複数のリスト要素を初期区分化する第２のプロセッサであり、それぞれのリスト要素の各々が、割当てに現在適した前記メモリのそれぞれの部分に対応する、第２のプロセッサと、
メモリ要求コアプロセッサにメモリを割当てることの要求を受けて、前記それぞれのリスト要素のうちの利用可能なものについて前記複数の区分化されたロックレスリスト構造を探索し、前記それぞれのリスト要素のうちの前記利用可能なものを発見したことを受けて、前記それぞれのリスト要素のうちの発見された前記利用可能なものに対応した、割当てに現在適した前記メモリの前記それぞれの部分を、前記メモリ要求コアプロセッサに割り当てる第３のプロセッサと、
均等化メトリックに従って、前記複数の区分化されたロックレスリスト構造の間で前記リスト要素を動的に均等化させる第４のプロセッサであり、前記均等化メトリックは、前記複数の区分化されたロックレスリスト構造の間で前記リスト要素を分散させるように適用される、第４のプロセッサと、
を有するシステム。
【請求項９】
前記イニシャルのロックレスリスト構造を区分化することは、
プロセッサインデックスに従ってキーイングされる前記適応ハッシュを用いて、前記イニシャルのロックレスリスト構造を前記複数の区分化されたロックレスリスト構造へと区分化すること
を含む、請求項８に記載のシステム。
【請求項１０】
前記イニシャルのロックレスリスト構造を区分化することは、
ＮＵＭＡノード番号に従ってキーイングされる前記適応ハッシュを用いて、前記イニシャルのロックレスリスト構造を前記複数の区分化されたロックレスリスト構造へと区分化すること
を含む、請求項８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、複数のロックレスリスト構造内で保管される複数のメモリ要素の割当てを管理するシステム及び方法に関する。
【背景技術】
【０００２】
Ｓｌｉｓｔ（Ｓリスト）は、オペレーティングシステム内で利用可能にされる後入れ先出し（ラストイン・ファーストアウト；ＬＩＦＯ）リストのロックレス（ロックを使用しない）実装であるデータ構造である。Ｓｌｉｓｔは典型的に、スピンロック又はその他の同期プリミティブを保持することなく割当て及び解放を行われることが可能な、固定サイズのバッファを保持するデータ構造の望ましい選択肢である。Ｓｌｉｓｔはまた、ロックを使用しない一方向にリンク付されたリスト（シングリー・リンクト・リスト）の形態で様々なサイズのコンテンツに使用され得る。例えばＳｌｉｓｔ上に構築されるルックアサイドリストなど、その他の能力もオペレーティングシステム環境で提供される。
【０００３】
しかしながら、一部の状況において、Ｓｌｉｓｔの使用は望ましくないことがある。一例において、多数のプロセッサが同じＳｌｉｓｔにアクセスするサーバでは、単一のＳｌｉｓｔヘッダがキャッシュライン競合ホットスポットになり得る。これは、ネイティブ及びハイパーＶ（ｈｙｐｅｒ−Ｖ）のどちらの仮想化シナリオでもスケーラビリティボトルネックとなり得る。
【０００４】
他の状況において、Ｓｌｉｓｔは、主として、パケットキャッシュ又は固定サイズのバッファリポジトリとして使用される。しかしながら、より複雑なデータ構造又は場合により可変サイズのリソースがそのようなロックレスリスト内で維持管理されなければならない状況が存在する。例えば負荷均等化（ロードバランシング）、パケットスチーリング、ＮＵＭＡアウェアネス及びその他のそのようなアルゴリズム要求などの目的のため、単に‘プッシュ’及び‘ポップ’より多くの処理を有することが望まれることがある。これらは、しばしば、複数のＳｌｉｓｔを管理するための別のデータ構造抽象化によって満たされている。
【０００５】
ルックアサイドリストは、迅速なメモリ割当て及び解放のために固定サイズバッファのキャッシュを維持管理する。プロセッサアフィニティの利益のため、一部のオペレーティングシステムはまた、プロセッサごとのルックアサイドリストを提供している。これらのプロセッサごとのルックアサイドリストは、（必ずしもそうではないが）一般的に、プロセッサごとのリストがエンプティの場合にバックアップパケットを収容するように、グローバルリストによって支援される。単一のリソースプールの抽象化を提供する相当に大きいグローバルバックアップリストを有するために、追加のリソース割当てを有することが望まれ得る。需要が減少するとき、これらの追加のメモリ割当ては、メモリの需要が存在する場合に解放され得る。しかしながら、特定の状況において、リソースは余分に割り当てられることができない。これは特に、ＲＡＩＤコントローラが処理することが可能なＩ／Ｏ要求の最大数のような能力の限界を規定するハードウェアドライバに当てはまる。先進アルゴリズムは、それらの限界をＳｌｉｓｔの深さに結び付けて、スピンロックの使用を避けている。また、割当て及び解放の追加オーバーヘッドが、メモリ断片化を生じさせるとともに、ＣＰＵサイクルを費やしてしまう。必要量より多くを割り当てるルックアサイドリストは、これらの理由により使用されることができないことがある。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
以下は、ここに記載される一部の態様の基本的な理解を提供するために、本発明を単純化した概要を提示するものである。この概要は、特許請求に係る事項の広範囲に及び概説ではない。これは、特許請求に係る事項の主要あるいは重大な要素を特定することを意図したものでもなければ、対象とする発明の範囲を定めることを意図したものでもない。その唯一の目的は、後に提示される更なる詳細な説明への前置きとして、特許請求に係る事項のうちの一部概念を単純化した形態で提示することである。
【０００７】
一実施形態において、複数のロックレスリスト構造内で保管される複数のメモリ要素の割当てを管理するシステム及び方法を提供する。
【課題を解決するための手段】
【０００８】
これらロックレスリスト構造（例えばＳｌｉｓｔ等）は、マルチコアプロセッサのオペレーティングシステム環境内でアクセス可能にされ得る。一部の実施形態において、ロックレスリスト構造であるＳｌｉｓｔ又はこれに類するものは、様々なリソース割当て・管理要求を満足するよう、ハッシュやツリーなどのようなその他の一般的データ構造に組み込まれ得る。
【０００９】
一部の実施形態は、この複数のロックレスリスト構造を区分化（パーティション分け）することができ、先ず、これらのロックレスリスト構造の間でメモリ要素を区分化し得る。コアプロセッサ（又は、その他のプロセッシング素子）がメモリ要素を自身に割り当てることの要求を作成するとき、このシステム及び／又は方法は、これらのロックレスリスト構造の中で利用可能なメモリ要素を探索し得る。好適且つ／或いは利用可能なメモリ要素が発見されると、このシステムはその利用可能なメモリ要素を要求元のコアプロセッサに割り当て得る。
【００１０】
そして、一部の実施形態において、このシステム及び／又は方法は、好適な均等化メトリックに従って、様々なロックレスリスト構造の間でメモリ要素の組を動的に均等化させ得る。可能なそのようなメトリックは、単純に複数のロックレスリスト構造の間でメモリ要素の実質的な数的均等性を維持することとし得る。その他のメトリックは、例えばＣＰＵ競合を抑制すること又はメモリ資源の過大な割当て（オーバーアロケーション）を回避することに関して上述したものなどのような、その他の負荷均等化の考察を含むことができ、それらは場合により、実行中のプロセスの種類、考え得る競合状況、又はこれらに類するものに基づく。
【００１１】
本システムのその他の特徴及び態様が、本出願にて提供される図面とともに読まれる以下の詳細な説明にて提示される。
【図面の簡単な説明】
【００１２】
典型的な実施形態が図面の参照図に示される。ここに開示される実施形態及び図面は限定的なものではなく例示的なものと見なされることが意図される。
【図１】本出願に係るシステム及び技術が提供されて動作し得る例示的なコンピュータシステムを示す図である。
【図２Ａ】Ｓｌｉｓｔの管理のための適応ハッシュ構造システム及び方法の一実施形態を示す図である。
【図２Ｂ】Ｓｌｉｓｔの管理のための動的リストスワッピングシステム及び方法の一実施形態を示す図である。
【図３】図２Ａにて実装され得るような適応ハッシュシステムにおけるフロー図を示す図である。
【発明を実施するための形態】
【００１３】
ここでは、用語“コンポーネント”、“システム”、“インタフェース”、及びこれらに類するものは、ハードウェア、ソフトウェア（例えば、実行中のもの）、及び／又はファームウェアの何れであろうと、コンピュータ関連エンティティを表すことが意図される。例えば、コンポーネントは、プロセッサ上で実行されているプロセス、プロセッサ、オブジェクト、実行ファイル、プログラム、及び／又はコンピュータであり得る。例示として、サーバ上で実行されているアプリケーションとサーバとの何れもがコンポーネントであり得る。１つ以上のコンポーネントが１つのプロセス内にあってもよく、コンポーネントは、１つのコンピュータ上に局在化されてもよく、且つ／或いは２つ以上のコンピュータ間で分散されてもよい。
【００１４】
特許請求に係る事項を、図面を参照して説明する。図面においては、全体を通して、同様の要素は似通った参照符号を用いて参照されている。以下の説明においては、説明の目的で、対象とする発明の十分な理解をもたらすよう、数多くの具体的詳細事項が説明される。しかしながら、明らかなように、特許請求に係る事項は、これらの具体的詳細事項を用いずに実施されてもよい。また、対象とする発明を記述することを促進するため、周知の構造及び装置はブロック図の形態で示されている。
【００１５】
リソースの潜在的なボトルネックに対処するため、本出願は、効果的で効率的なＳｌｉｓｔの使用を可能にする多数の実施形態を開示する。一実施形態において、リソースＳｌｉｓｔのロックレス性を維持しながら、キャッシュライン競合の抑制、固定量割当て、及びリスト間のリソース共有／スチーリングの数多くの上述の限界を解消する効果的な手法で、Ｓｌｉｓｔが区分化（パーティション分け）され得る。他の実施形態において、これらの技術は、最適性能のためにプロセッサアフィニティ及びＮＵＭＡアウェアネスを利用し得る。
【００１６】
図１は、マルチプルグループ・ＮＵＭＡノード（すなわち、プロセッサソケット）・マルチコアシステム１００を示すコンピュータシステム図を描写している。図示のシステム１００は、例えばグループ０（１０２ａ）とグループ１（１０２ｂ）である２つのグループを有している。一実施形態において、各グループは、最大６４個（例えば、０から６３までのラベルを付される）の論理プロセッサ（ＬＰ）を有し得る。
【００１７】
認識されるように、好適な一システムは、存在する論理プロセッサが６４個より少ない場合に、１つのグループのみを有していてもよい。同様に、システムは２つより多いグループを有していてもよい。グループに十分にＮＵＭＡノードが含められ、グループが６４個より少ない論理プロセッサを有することが可能にされ得る。システムは、そのシステムに含まれる論理プロセッサの数に応じて複数のグループ（２グループより多い）を有し得る。
【００１８】
図示されるように、各グループは更に、複数のノード１０４（すなわち、プロセッサソケット）を有し得る。図中のノードはまた、ＮＵＭＡ（不均等メモリアクセス）ノードを表し得る。多くの現行システムにおいて、ＮＵＭＡノードは、全てのグループにまたがるシステム全体の中で０から６３まで番号を付されている。しかしながら、将来のシステムは異なる個数のノードを有することができ、本出願はこのような現行仕様に限定されるものではない。さらに、これらのノードは各々、複数のコア１０６を有し得る。この実施形態において、各ＬＰはコア又はハードウェアスレッドとし得る。論理プロセッサは、各グループ内で０から６３まで一意に番号付けられる。
【００１９】
一部のコンピューティング環境において、２つ以上の物理プロセッサを有するシステム、又は複数のコアを有する物理プロセッサを有するシステムは、複数の論理プロセッサを用いてオペレーティングシステムを提供することができる。論理プロセッサは、オペレーティングシステム、アプリケーション、又はドライバの視点から見て、１つの論理コンピューティングエンジンである。“コア”（又は“コアプロセッサ”）は１つのプロセッサユニットであり、これは１つ以上の論理プロセッサで構成されることができる。物理プロセッサは、１つ以上のコアで構成され得る。物理プロセッサは、プロセッサパッケージ、ソケット、又はＣＰＵと同じと解釈されてもよい。
【００２０】
また、コア０乃至Ｃ−１はメモリ資源１０８を共有し得る。所与のノード上のコアとメモリとの間でのローカルメモリアクセス時間は、その他のノードへのメモリアクセス時間より速くなり得る。ノード間の接続１１０は、全てのノードがその他全てのノード内のメモリにアクセスし得るが、そのメモリアクセス時間はローカルメモリにアクセスするより遅くなり得る、というものになり得る。
【００２１】
認識されるべきことには、必ずしも全てのノードが完全に接続される必要はなく、また、１つのノードから別のノードへのメモリアクセスは、更なるノードを横断して第３者ノード上のメモリにアクセスすることが必要なことがある。
【００２２】
Ｓｌｉｓｔ管理
本出願は、ロックレスリスト構造Ｓｌｉｓｔ又はこれに類するものの効果的な管理のための数多くの実施形態を開示する。図２Ａ及び２Ｂは、２つのそのような実施形態であるＳｌｉｓｔ管理のための適応ハッシュ関数（図２Ａ）及び動的ポップ・アンド・プッシュ構造（図２Ｂ）を示している。これらの実施形態においては、
ｉ）  ＣＰＵキャッシュライン競合を抑制すること；
ｉｉ）  リソースの過大割当てを回避すること；
ｉｉｉ）  最大限リソース需要に適応するよう、リスト間でのリソースの共有及びスチーリングを提供すること；
ｉｖ）  ＮＵＭＡトポロジーアウェアネスやプロセッサアフィニティのために更なるロジックを提供すること；及び／又は
ｖ）  例えば４ＧＢ限度及びそのようなその他の制約の中で、アロケータのように具体的なメモリ割当て要求を提供すること。メモリの追加の割り当て及び解放は、例えば特に４ＧＢ限度の場合などで問題となり得る断片化（フラグメンテーション）をもたらし得るものであり、望ましくないことがある；
のために、（Ｓｌｉｓｔのような）ロックレスリストにおけるリソース又はパケット管理を提供することが望ましいことがある。
【００２３】
概して、本出願に係る技術及び実施形態は、ロックレスリスト構造Ｓｌｉｓｔ又はこれに類するものを、様々なリソース割当て・管理要求を満足するよう、ハッシュやツリーなどのようなその他の一般的データ構造に組み込むようなものである。
【００２４】
これらの実施形態の多くにおいて、複数のロックレスリスト構造内で保管される複数のメモリ要素の割当てを管理するシステム及び方法が提示される。これらのロックレスリスト構造（例えばＳｌｉｓｔなど）は、マルチコアプロセッサのオペレーティングシステム環境内でアクセス可能にされ得る。
【００２５】
これらの実施形態は、この複数のロックレスリスト構造を区分化することができ、先ず、これらのロックレスリスト構造の間でメモリ要素を区分化し得る。コアプロセッサ（又は、その他のプロセッシング素子）がメモリ要素を自身に割り当てることの要求を作成するとき、このシステム及び／又は方法は、これらのロックレスリスト構造の中で利用可能なメモリ要素を探索し得る。好適且つ／或いは利用可能なメモリ要素が発見されると、このシステムはその利用可能なメモリ要素を要求元のコアプロセッサに割り当て得る。ロックレスリスト構造のこのようなパーティション分けは、ＣＰＵ競合を抑制する傾向を有し得る。
【００２６】
そして、このシステム及び／又は方法は、好適な均等化メトリックに従って、様々なロックレスリスト構造の間でメモリ要素の組（セット）を動的にバランスさせ得る。可能な１つのそのようなメトリックは、単純に複数のロックレスリスト構造の間でメモリ要素の実質的な数的均等性を維持することとし得る。その他のメトリックは、例えばメモリ資源の過大割当てを回避するものとして上述したものなどの、その他の負荷均等化の考察を含むことができ、それらは場合により、実行中のプロセスの種類、考え得る競合状況、又はこれらに類するものに基づく。
【００２７】
他の一実施形態において、コンピュータシステム（例えば、図１に示したもの、又はその他の好適なマルチコアプロセッシングシステムなど）の中に、好適な割当てモジュールが実装され得る。単なる一例において、割当てモジュールは、複数のコアプロセッサのうちの１つ上で実行されて、そこから動的メモリ割当てを行い得る。更に詳細に後述するように、割当てモジュールは、例えばダイナミックハッシュ構造又はダイナミックリストスワッピング構造などといった、多様なデータ構造内のメモリ要素の動的パーティション分けを管理し得る。
【００２８】
Ｓｌｉｓｔ管理のための適応ハッシュ法
図２Ａは、Ｓｌｉｓｔを管理するための適応型の動的ハッシュシステム及び技術（２００）を示している。図示のように、ハッシュモジュール２０２が１つ以上のＳｌｉｓｔ（２０４）（例えば、Ｓｌｉｓｔ０乃至Ｓｌｉｓｔ３）に接続される。各Ｓｌｉｓｔは更に、ゼロ又は１以上のメモリ要素２０６を有し得る。これらのメモリ要素２０６の各々は、固定サイズバッファ若しくは可変サイズバッファの何れか、及び／又はデータ構造を有し得る。
【００２９】
この実施形態において、異なるＳｌｉｓｔのこのハッシュは、システムに関連付けられた手法で、一般に、コンピューティングシステムトポロジー及び／又はマルチコアプロセッサアーキテクチャに関する手法で、キーイングすることによって維持管理され得る。例えば、図２Ａは、２つのそのようなトポロジー：（１）プロセッサインデックスによるキーイング（２０８ａなるラベルを付されたグループ０に関する実線の矢印によって示される）；（２）ＮＵＭＡノード番号によるキーイング（２０８ｂなるラベルを付された更にノード２１０及びＬＰ２１２を有するグループ０に関する破線の矢印によって示される）を示している。これらの実施形態において、インデックスをシステムトポロジーに関連付けるポイントは、レイテンシとシステム内のその他のプロセッサとの競合を最小化するようにアクセス時間を最適化することであり得る。見て取れるように、メモリ要素は、負荷均等化及び／又はメモリ資源の割当てに関する好適なメトリックに従って、複数のＳｌｉｓｔ間（例えば、２１４）で調整且つ／或いは均等化され得る。
【００３０】
一実施形態において、単一の論理Ｓｌｉｓｔを複数のものへと抽象化することが可能である。そのような一例において、１つの特定のＳｌｉｓｔがエンプティである場合に割当てが失敗しないよう、異なるリスト間でリストエンティティを移動することが可能であり得る。割当てが失敗する前に、そのハッシュの全てのＳｌｉｓｔが探索され得る。認識されるべきことには、異なるハッシュアルゴリズムもまた、システムトポロジー、及びこれらのリストのＮＵＭＡ拡張若しくはプロセッサアフィニティ拡張などの最適化目的に応え得る。
【００３１】
図３は、ハッシュ構造内でのＳｌｉｓｔの処理に関する１つの可能なフローチャートを示している。ステップ３００にて、システムはメモリ資源を割り当てることを開始し、ステップ３０２にて、システムは所望の鍵（例えば、図２Ａにて指し示されるようにＣＰＵ番号又はＮＵＭＡ  ＩＤ）に基づいてハッシュインデックスを計算し得る。そして、計算されたハッシュ（インデックス）にＳｌｉｓｔが割り当てられ得る。
【００３２】
システムは、ステップ３０６にて、そのＳｌｉｓｔがエンプティかについて、すなわち、メモリ要素を持っていないかについて問合せを行い、エンプティである場合、システムは、好適なリソースを発見するために、その他のＳｌｉｓｔに関して繰り返し得る。発見されると、リソースが、言わば次の非エンプティＳｌｉｓｔから割り当てられ得る。
【００３３】
上記Ｓｌｉｓｔがエンプティでなかった場合、ステップ３１０にて、そこからリソースが割り当てられ得る。割当てがステップ３１０又はステップ３１２の何れで行われようが、システムは、ステップ３１４にて、割当てが成功したかを問い合わせ得る。成功しなかった場合、システムは、ステップ３２０にてエラーメッセージを返し、ステップ３２２にて処理を終了し得る。
【００３４】
一方、割当てが成功した場合、ステップ３１６にて、割り当てられたメモリ資源が利用され得る。そのメモリ資源がもはや必要でなくなると、システムは、必要に応じてそのリソースを解放して元々のＳｌｉｓｔ又は提供元のＳｌｉｓｔへと戻し、ステップ３２２にて処理を終了し得る。
【００３５】
動的リストスワッピング
図２Ｂは、Ｓｌｉｓｔの効果的な管理のために動的リストスワッピングデータ構造（２５０）を使用する更なる他の一実施形態を示している。見て取れるように、例えばプッシュ（解放）処理用のＳｌｉｓｔ２５２ａとポップ（取得／割当て）処理用のＳｌｉｓｔ２５２ｂである２つの別々のＳｌｉｓｔが維持管理されることができ、これらは各々、割り当てるためのメモリ要素２５４を有し得る。２つの異なるポインタ（２５６ａ及び２５６ｂ）を用いてこれらのＳｌｉｓｔにアクセスし得る。処理の過程で、割当ての試み中にポップＳｌｉｓｔがエンプティ（又は、メモリ資源を均等化するためのその他好適なメトリック）である場合、以前のプッシュＳｌｉｓｔが今度はポップＳｌｉｓｔとなり、その逆もまた然りであるように、上記ポインタを交換することが可能である。そのポイントから、その時から、今度は、この新たなポップＳｌｉｓｔから割当てることを試みることができる。この技術は、異なる‘割当て’リスト及び‘解放’リストを維持管理して、‘割当て’リストがエンプティであるときにこれらを交代させることと類似である。
【００３６】
上述したものは、対象とする発明の例を含むものである。当然ながら、特許請求に係る事項を記述する目的でコンポーネント又は手順の取り得る全ての組み合わせを記載することは不可能であるが、当業者によって認識され得るように、対象とする発明の数多くの更なる組み合わせ及び置換が可能である。従って、特許請求に係る事項は、添付の請求項の精神及び範囲に入る全ての改変、変更及び変形を包含するものである。
【００３７】
特に、上述のコンポーネント、装置、回路、及びシステムなどによって実行される様々な機能に関し、そのようなコンポーネントを記述するために使用された用語（“手段”を参照するものを含む）は、別のことが指し示されていない限り、その記載されたコンポーネントについて規定された機能を果たす如何なるコンポーネント（例えば、機能的に均等なもの）にも相当するものであり、このことは、たとえ、特許請求に係る事項についてここに例示された代表的な態様でその機能を実行する開示構造とは構造的には等価でないとしても、云えることである。これに関連し、やはり認識されるように、本発明は、システムだけでなく、特許請求に係る事項の様々な方法の活動及び／又はイベントを実行するためのコンピュータ実行可能命令を有するコンピュータ読み取り可能媒体を含む。
【００３８】
さらに、対象とする発明の特定の特徴を、幾つかある実装のうちの１つのみに関して開示していることがあるが、そのような特徴は、所与あるいは特定の用途で所望され且つ有利であり得るように、その他の実装の１つ以上のその他の特徴と組み合わされてもよい。また、用語“含む”、“含んでいる”及びこれらの変化形がこの詳細な説明又は請求項の何れかで使用される限りにおいて、これらの用語は、用語“有している”と同様に包含的であることを意図したものである。
【図１】
0006275119.tif 000002
【図２Ａ】
0006275119.tif 000003
【図２Ｂ】
0006275119.tif 000004
【図３】
0006275119.tif 000005