(57)【特許請求の範囲】
【請求項１】
マルチプロセッサ・システムの複数のプロセッサ用にマルチプロセッサ・データをプライベート化する方法であって、
マルチプロセッサ・データを格納するためのマルチプロセッサ・システムのグローバル・アドレス・スペースにあるメモリ・ブロックを割り振るステップと、
メモリ・ブロックをメモリ・ブロックの有効ベース・アドレスとブロック内のマルチプロセッサ・データのチャンクの割り振り状態を記録する補助データ構造によって維持されるリンク・リストに追加するステップと、
メモリ・ブロックを複数のセクションに分割し、各セクションをマルチプロセッサ・システムの単一プロセッサ用とするステップと、
１つまたは複数のカーネル・サービスによってマルチプロセッサ・データを複数のセクションに格納するステップと、
１つまたは複数のカーネル・サービスによって格納されたマルチプロセッサ・データにアクセスするステップとを含み、
前記マルチプロセッサ・データを複数のセクションに格納するステップは、
マルチプロセッサ・データの領域のサイズを入力として受け取るステップと、
マルチプロセッサ・データを格納する十分なフリー・スペースを有するブロックを求めて前記リンク・リストを探索するステップと、
マルチプロセッサ・データの領域を格納するセクションのハンドルを戻すステップとを含み、
前記格納されたマルチプロセッサ・データにアクセスするステップは、
プロセッサのマルチプロセッサ・データの領域のハンドルおよび論理プロセッサ識別子を入力として受け入れ、プロセッサ・データの領域の有効アドレスを戻すステップ
を含む方法。
【請求項２】
複数のセクションのそれぞれが、前記セクションに関連するプロセッサにとってローカルなメモリにある、請求項１に記載の方法。
【請求項３】
マルチプロセッサ・データのチャンクの割り振り状態が、ブロック割り振りビットマップを使用して記録され、ブロック割り振りビットマップの各ビットが、マルチプロセッサ・データのＮ個のチャンクを示す、請求項１に記載の方法。
【請求項４】
ブロック割り振りビットマップのビットに対応するマルチプロセッサ・データの各チャンクが、メモリ・ブロックの対応するセクション内の同じ相対開始バイト・オフセットにある、請求項３に記載の方法。
【請求項５】
リンク・リストを探索するステップが、ツリー構造を使用してリンク・リストを探索するステップを含む、請求項１に記載の方法。
【請求項６】
ツリー構造の各ノードが固定数の子ノードを持ち、ツリー構造が、マルチプロセッサ・データのチャンクの固定サイズの領域を示すツリー構造の下端に割り振りビットマスクを有する、請求項５に記載の方法。
【請求項７】
マルチプロセッサ・システムの複数のプロセッサ用にマルチプロセッサ・データをプライベート化するための、コンピュータ読み取り可能な媒体内のコンピュータ・プログラムであって、
マルチプロセッサ・データを格納するマルチプロセッサ・システムのグローバル・アドレス・スペースにあるメモリ・ブロックを割り振る第１の命令と、
メモリ・ブロックをメモリ・ブロックの有効ベース・アドレスとブロック内のマルチプロセッサ・データのチャンクの割り振り状態を記録する補助データ構造によって維持されるメモリ・ブロックのリンク・リストに追加する第２の命令と、
メモリ・ブロックを複数のセクションに分割し、各セクションをマルチプロセッサ・システムの単一プロセッサ用とする第３の命令と、
１つまたは複数のカーネル・サービスによってマルチプロセッサ・データを複数のセクションに格納する第４の命令と、
１つまたは複数のカーネル・サービスを使用して、格納されたマルチプロセッサ・データにアクセスする第５の命令とを備え、
前記第４の命令は、
マルチプロセッサ・データの領域のサイズを入力として受け取り、マルチプロセッサ・データを格納する十分なフリー・スペースを有するブロックを求めてリンク・リストを探索し、マルチプロセッサ・データの領域を格納するセクションのハンドルを戻す命令を備え、
前記第５の命令は、
プロセッサのマルチプロセッサ・データの領域のハンドルおよび論理プロセッサ識別子を入力として受け入れ、プロセッサ・データの領域の有効アドレスを戻す命令
を備えるコンピュータ・プログラム。
【請求項８】
複数のセクションの各セクションが、前記セクションに関連するプロセッサにとってローカルなメモリにある、請求項７に記載のコンピュータ・プログラム。
【請求項９】
マルチプロセッサ・データのチャンクの割り振り状態が、ブロック割り振りビットマップを使用して記録され、ブロック割り振りビットマップの各ビットが、マルチプロセッサ・データのＮ個のチャンクを示す、請求項７に記載のコンピュータ・プログラム。
【請求項１０】
ブロック割り振りビットマップのビットに対応するマルチプロセッサ・データの各チャンクが、メモリ・ブロックの対応するセクション内の同じ相対開始バイト・オフセットにある、請求項９に記載のコンピュータ・プログラム。
【請求項１１】
リンク・リストを探索する命令が、ツリー構造を使用してリンク・リストを探索する命令を含む、請求項７に記載のコンピュータ・プログラム。
【請求項１２】
ツリー構造の各ノードが固定数の子ノードを持ち、ツリー構造が、マルチプロセッサ・データのチャンクの固定サイズの領域を示すツリー構造の下端に割り振り・ビットマスクを有する、請求項１１に記載のコンピュータ・プログラム。
【請求項１３】
マルチプロセッサ・システムの複数のプロセッサ用にマルチプロセッサ・データをプライベート化する装置であって、
マルチプロセッサ・データを格納するためのマルチプロセッサ・システムのグローバル・アドレス・スペースにあるメモリ・ブロックを割り振る手段と、
メモリ・ブロックをメモリ・ブロックの有効ベース・アドレスとブロック内のマルチプロセッサ・データのチャンクの割り振り状態を記録する補助データ構造によって維持されるリンク・リストに追加する手段と、
メモリ・ブロックを複数のセクションに分割し、各セクションをマルチプロセッサ・システムの単一プロセッサ用とする手段と、
１つまたは複数のカーネル・サービスによってマルチプロセッサ・データを複数のセクションに格納する手段と、
１つまたは複数のカーネル・サービスによって格納されたマルチプロセッサ・データにアクセスする手段とを備え、
前記マルチプロセッサ・データを複数のセクションに格納する手段は、
マルチプロセッサ・データの領域のサイズを入力として受け取る手段と、
マルチプロセッサ・データを格納する十分なフリー・スペースを有するブロックを求めて前記リンク・リストを探索する手段と、
マルチプロセッサ・データの領域を格納するセクションのハンドルを戻す手段とを備え、
前記格納されたマルチプロセッサ・データにアクセスする手段は、
プロセッサのマルチプロセッサ・データの領域のハンドルおよび論理プロセッサ識別子を入力として受け入れ、プロセッサ・データの領域の有効アドレスを戻す手段
を備える装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、オペレーティング・システム・データをプライベート化する装置、方法、およびコンピュータ・プログラムに関する。
【０００２】
【従来の技術】
データのプライベート化は、共用メモリ・マルチプロセッサ（ＳＭＭＰ）ハードウェア・システムで使用される既知のソフトウェア技法である。データのプライベート化は、共用キャッシュ・メモリの特定のプロセッサの特定のキャッシュ・ラインにそのプロセッサのみが必要とするデータを格納する。キャッシュ・ラインはプロセッサのキャッシュの一部であり、同じサイズの物理メモリのセクションを表す。他のプロセッサが、共用キャッシュ・メモリのプライベート化されたデータにアクセスするには、プライベート化されたデータが格納されているメモリを明示的に参照しなければならない。
【０００３】
データのプライベート化によって、ＳＭＭＰハードウェア・システムは、ハードウェア・キャッシュのコヒーレンシー・ミスを回避することができる。キャッシュ・ラインが書き込まれると、それがそのメモリの唯一の有効なコピーになる。その結果、そのキャッシュ・ラインの他のすべてのコピーが無効にならなければならない。キャッシュ・ラインが他のデータを含むために、キャッシュ・ミスが生じると、低速のシステム・メモリ（ＲＡＭ）から高速アクセス・キャッシュへのメモリ読み取りを実行しなければならない。そのようなキャッシュ・ミスは、あるプロセッサがあるキャッシュ・アドレス場所から読み取りを行っている間に、別のプロセッサが同じキャッシュ・アドレス場所に書き込みを行う、プロセッサ間の読み取り／書き込みによるデータの共用によって発生する。このようなキャッシュ・ミスは、オペレーティング・システム・ソフトウェアのパフォーマンスに悪影響を与える。
【０００４】
データのプライベート化には主に２つの用途がある。第１に、データのプライベート化は、各プロセッサの状態を示す、頻繁に修正されるオペレーティング・システム・データに使用される。このデータは他のプロセッサからアクセスされることが少ないので、プライベート化に適切である。この第１の用途の例は、プロセッサごとに実行されるキュー・データに使用されるデータのプライベート化である。
【０００５】
第２のデータのプライベート化は、プロセッサごとに維持することができるグローバル状態データに使用される。このデータはシステム全体で必要とされることはまれで、プロセッサごとに維持されるので、あるプロセッサのデータが別のプロセッサによって書き込まれることがない。このようなグローバル状態データの例は、グローバル統計である。
【０００６】
既知のデータのプライベート化技法の下では、読み取り／書き込みデータのプライベート・コピーは、各プロセッサの個々のキャッシュ・ラインに維持される。各プロセッサは自身が持つデータのコピーのみを修正し、したがって、共用キャッシュ・ラインの修正およびキャッシュ・コヒーレンシー・オーバーヘッドが回避される。
【０００７】
ＮＵＭＡ（Non-Uniform Memory Access）方式のＳＭＭＰハードウェア・システムでは、データをプライベート化する際に物理メモリ・ページの配置についても考慮しなければならない。物理メモリのローカル性は、データを物理メモリからハードウェア・キャッシュにフェッチしなければならない場合に、キャッシュ・ミスのパフォーマンス・コストに影響を与える。このようなキャッシュ・ミスのパフォーマンス・コストは、プライベート・データが、プロセッサにとってローカルな物理メモリ・ページに置かれているときに最も低い。
【０００８】
データのプライベート化では、ＳＭＭＰハードウェア・システムの物理構成のダイナミックな性質についても考慮しなければならない。このことを考慮しなければならないのは、データはハードウェア・システムのプロセッサのローカル・メモリにプロセッサごとに維持されねばならないが、プロセッサやメモリが、物理再構成操作の一部としてハードウェア・システムに追加またはハードウェア・システムから削除されるときに、システムの物理構成がダイナミックに変化する可能性があるからである。
【０００９】
データのプライベート化は、例えば、仮想メモリ・マネージャ、ファイルシステム、セキュリティなど、オペレーティング・システム・ソフトウェアの多くのサブシステムに広く適用することができる。しかし、データのプライベート化には、それを使用するハードウェア・システムの物理特性（キャッシュおよびページのサイズ、現在のプロセッサ数など）、物理トポロジー（メモリの物理的配置など）、およびダイナミックな性質の複雑さを各区域が理解することが必要である。さらに、体系的な機能が存在しないので、データをプライベート化する独自の方法を各区域が定義しなければならない。
【００１０】
【発明が解決しようとする課題】
したがって、複数のプライベート化方式の必要性をなくす統一したプライベート化方式を提供するための装置、方法、およびコンピュータ・プログラムがあれば有益である。さらに、ハードウェア・システムの物理特性、物理トポロジー、およびダイナミックな性質を考慮に入れた統一したプライベート化方式があれば有益である。
【課題を解決するための手段】
【００１１】
本発明は、オペレーティング・システム・データをプライベート化する装置、方法、およびコンピュータ・プログラムを提供する。本発明の装置、方法、コンピュータ・プログラムにより、メモリ・ブロックが割り振られ、適正に整合された同じ大きさのより小さい記憶域に分割され、各記憶域がマルチプロセッサ・システムの単一のプロセッサに割り振られる。記憶域は、最初にシステムが初期化されるときに、または必要に応じて割り振られる。
【００１２】
各２次割り振り要求は、そのプロセッサのストレージ・スペースの起点に対して同じ場所にあるストレージを使用するために行われる。これによって高速の検索が可能になる。各２次割り振りをオフセットｎのところにし、各プロセッサの記憶域の開始アドレスを維持することによって、所与のプロセッサのプライベート・データのアドレスは、単に＜ローカル・アドレス始点＞＋ｎになる。各プロセッサのストレージは、他のすべてのプロセッサと同型（isomorphic）であるので、すべてのプロセッサに対して１つの割り振りレコードだけが必要であり、したがって、データのプライベート化方式のオーバーヘッドが減少する。このようにして、メモリを割り振ることによって、キャッシュ・ラインの競合が最小限に抑えられる。
【発明の実施の形態】
【００１３】
図を参照すると、図１は、本発明が使用されるマルチプロセッサ・データ処理システムの構成図である。図１に示すように、データ処理システム１００は、共用メモリ・マルチプロセッサ（ＳＭＭＰ）システム、ＮＵＭＡ（Non-Uniform Memory Access）システム、その他の、システム・バス１０７に接続された複数のプロセッサ１０２〜１０６を含みシステム・メモリを共用するマルチプロセッサ・システムとすることができる。また、メモリ・コントローラ／キャッシュ１０８もシステム・バス１０７に接続され、ローカル・メモリ１０９へのインターフェースを提供する。入出力バス・ブリッジ１１０は、システム・バス１０７に接続され、入出力バス１１２へのインターフェースを提供する。図に示すように、メモリ・コントローラ／キャッシュ１０８および入出力バス・ブリッジ１１０は統合することもできる。
【００１４】
入出力バス１１２に接続された周辺コンポーネント相互接続（ＰＣＩ）バス・ブリッジ１１４は、ＰＣＩローカル・バス１１６へのインターフェースを提供する。何台かのモデムをＰＣＩバス１１６に接続することができる。典型的なＰＣＩバス実装は、４つのＰＣＩ拡張スロットまたはアドイン・コネクタをサポートする。他の装置やネットワークなどへの通信リンクは、アドイン・ボードを介してＰＣＩローカル・バス１１６に接続されたモデム１１８およびネットワーク・アダプタ１２０によって提供することができる。
【００１５】
追加のＰＣＩバス・ブリッジ１２２および１２４は、追加のＰＣＩバス１２６および１２８のインターフェースを提供し、そこから追加のモデムまたはネットワーク・アダプタがサポートされる。このようにして、データ処理システム１００により複数のネットワーク・コンピュータへの接続が可能になる。図に示すように、メモリ・マップ式グラフィックス・アダプタ１３０およびハード・ディスク１３２も、入出力バス１１２に直接または間接的に接続することができる。
【００１６】
図１に示すハードウェアが変更可能であることを当業者なら理解されよう。図に示すハードウェアに加えて、またはその代わりに、例えば、光ディスク・ドライブなど他の周辺装置を使用することも可能である。さらに、図１に示すエレメントの多くは、本発明が使用されるデータ処理システムに存在しなくてもよい。図に示した例は、本発明に対するアーキテクチャー上の制限を意味するものではない。
【００１７】
図１に示すデータ処理システムは、例えば、ＡＩＸ（Advanced Interactive Executive）オペレーテング・システムを実行する、ニューヨーク州アーモンクのインターナショナル・ビジネス・マシーンズ・コーポレーションの製品であるＩＢＭ  ＲＳ／６０００システムとすることができる。
【００１８】
本発明によれは、マルチプロセッサ・システムのプロセッサ用にプライベート化されたデータを維持するために、ストレージ・ブロックが割り振られる。例えば、マルチプロセッサ・システムのプロセッサ用のプライベート化されたデータ（以下では、マルチプロセッサ・データ（ｍｐｄａｔａ）と呼ぶ）を維持する際に使用するために、ローカル・メモリ１０９のストレージ・ブロックが割り振られる。このストレージ・ブロックはさらにセクションに分割され、各セクションは単一プロセッサ用のストレージを含む。ストレージ・ブロックのセクションは、マルチプロセッサ・システムの各プロセッサで同じサイズであることが好ましい。各セクション内に、ｍｐｄａｔａのチャンク、つまり１６バイトのｍｐｄａｔａを格納することができる。単一のｍｐｄａｔａ割り振りとして使用されるｍｐｄａｔａの連続チャンクの範囲を本明細書において領域と呼ぶ。
【００１９】
図２は、本発明によるｍｐｄａｔａのブロックを示す図である。図２に示すように、ｍｐｄａｔａのブロック２００には、複数のセクション２１０〜２３０が含まれ、各セクションはマルチプロセッサ・システムの１つのプロセッサに対応している。これらのセクション２１０〜２３０はそれぞれ、ｍｐｄａｔａのチャンク２１１〜２１５、２２１〜２２５、２３１〜２３５からなる。セクション内の連続チャンクの範囲が、セクション２１０〜２３０のすべてで同型である、ｍｐｄａｔａブロック２００の領域２５０を構成する。
【００２０】
本発明は、ｍｐｄａｔａを維持するこのストレージ・ブロックを確立し使用するための装置、方法、およびコンピュータ・プログラムを提供する。ストレージ・ブロックは、システムのグローバル・アドレス・スペースに存在する。各セクションは、プロセッサにとってローカルなメモリに存在し、ｍｐｄａｔａチャンクは用途に応じてメモリまたはキャッシュに存在する。
【００２１】
本発明は、ｍｐｄａｔａストレージの割り振りおよび解放を行う新しいオペレーティング・システム（ＯＳ）カーネル・サービス、ｍｐｄａｔａストレージ領域にアクセスする新しいカーネル・サービス、およびｍｐｄａｔａストレージ・ブロックで同型のｍｐｄａｔａ領域を見つける新しいカーネル・サービスを提供する。これらのカーネル・サービスを実現可能にするために、領域にアクセスするために使用されるカーネル・サービス：例えばmpdata_get()、mpdata_getcpu()、およびmpdata_find()はいつでも呼び出すことができる。具体的にはこれらのカーネル・サービスは、割込みハンドラから呼び出すことができるが、割込み自体を使用することはない。
【００２２】
本発明によれば、mpdata_alloc()カーネル・サービスは、新しいｍｐｄａｔａ領域に必要なサイズ（バイト単位）を取得し、ｍｐｄａｔａストレージ・セクションのハンドル、つまり一時ポインタを戻す。mpdata_free()カーネル・サービスは、以前に割り振られたｍｐｄａｔａストレージ領域のハンドルおよびサイズを取得し、そのｍｐｄａｔａストレージ領域を解放する。
【００２３】
ｍｐｄａｔａストレージ領域は、いったん割り振られると、いくつかのカーネル・サービスを使ってその領域のハンドルを介してアクセスすることができる。第１に、mpdata_get()カーネル・サービスを使用して、現行プロセッサ、つまり、カーネル・サービスを実行中のカーネルが置かれているプロセッサの領域にアクセスすることができる。具体的には、このカーネル・サービスは、パラメータとしてこの領域のハンドルを取得し、現行プロセッサの領域の有効アドレスを戻す。ある領域の有効アドレスが獲得されると、その領域は通常のロードおよびストア操作によってアクセスすることができる。
【００２４】
ｍｐｄａｔａストレージ領域のハンドルおよび論理プロセッサ識別子が与えられると、mpdata_getcpu()カーネル・サービスを使用して、指定されたプロセッサの領域の有効アドレスを得ることができる。mpdata_find()カーネル・サービスを使用して、所与のｍｐｄａｔａストレージ・ハンドルの第１のまたは次の領域の有効アドレスを見つけることができる。このカーネル・サービスは、ｍｐｄａｔａストレージが統計データのプライベート化に使用されるときに値を集計するのに有用である。
【００２５】
本発明を、まず、限られたアドレス・スペースを有する３２ビット・カーネルの実施形態に関して説明する。アドレス・スペースが限られているために、本発明のｍｐｄａｔａ実装では、限られた大きさの仮想スペースが割り振られるだけである。このストレージ・スペースは、必要に応じて、ピン固定カーネル・ヒープから固定サイズのブロックで割り振られる。ピン固定メモリは、物理メモリに残り、ディスクのページング空間に格納されてはならないメモリである。ピン固定カーネル・ヒープとは、ピン固定メモリを割り振るカーネルのメモリ割り振りに使用されるヒープである。本発明の好ましい実施形態では、例えば、プロセッサ当たり１キロバイトのブロック・サイズが使用される。
【００２６】
最初は、使用されるｍｐｄａｔａストレージにスペースが割り振られていない。例えばmpdata_alloc()カーネル・サービスを使用してｍｐｄａｔａストレージが割り振られるとき、複数のストレージ・ブロックが割り振られ、ブロックのリンク・リストに追加される。ｍｐｄａｔａの新しい割り振りが必要なときは、本発明のｍｐｄａｔａストレージ割り振りアプリケーション・プログラム・インターフェース（ＡＰＩ）が、ファーストフィット・アルゴリズムを使用して、十分なフリー・スペースを有するブロックを求めてリンク・リストを探索する。必要なフリー・スペースを有する既存のブロックが見つからない場合、新しいブロックがリンク・リストに追加される。
【００２７】
ブロックのリンク・リストは、補助データ構造mpdata_map_tによって維持される。mpdata_map_tデータ構造は、プログラム・セグメントを格納するためにカーネルが利用できるフリー・スペースの共通プールの一部であるカーネル・ヒープからブロックごとに割り振られる。ブロックおよびその補助データ構造がカーネル・ヒープに解放されるのは、対応するすべてのｍｐｄａｔａストレージが解放されたときである。
【００２８】
mpdata_map_tデータ構造は、ブロックの有効ベース・アドレスおよびブロック内のチャンクの割り振り状態を記録する。割り振り状態は、利用可能な最大未割振り領域を追跡するビット・マップおよび整数によって記録される。
【００２９】
図３は、mpdata_map_t構造とｍｐｄａｔａストレージ・メモリ・ブロックとの関係を示す例示の図である。図３に示すように、mpdata_next３１０は、リンク・リストの次のメンバ３１２を示すポインタである。mpdata_base３２０は、対応するブロック３１６の始点３１４を示すポインタである。mpdata_maxfree３３０は、未割振りチャンクの最長領域の長さを識別する。mpdata_avail_mask３４０は、現在の割り振り状態を示すビットマスクである。
【００３０】
例えば、３２バイトの内部チャンク・サイズで管理される１ＫＢのｍｐｄａｔａストレージ・ブロックについて考える。このブロックは３２個のチャンクからなる。第１、第５、第１２のチャンクが割り振られている場合、ビットマスクは１０００１００００００００００００００１００００００００００００になり、したがって、現在の割り振り状態は、第１、第５、第１２のチャンクが割り振り済みの状態であることを示す。これを使用して、割り振りに十分な連続チャンクを見つける。上述したように、各ブロックは、各プロセッサごとに１つずつ同じサイズのセクションに分割される。これらのプロセッサごとのセクションは、好ましい実施形態ではやはり１キロバイトである。これらのセクションは、プロセッサごとのセクション内のｍｐｄａｔａの連続チャンクからなるｍｐｄａｔａストレージ領域に再分割される。
【００３１】
ブロック割り振りマップの単一ビットはＮ個のチャンクに対応し、Ｎは、ハードウェア構成によってサポートされるプロセッサの最大数である。単一ビットで表されるＮ個のチャンクは、各プロセッサの領域における同型チャンクである。したがって、例えば図３で、割り振りマスク中の単一ビット、例えば第５のビットは、プロセッサ０の領域、プロセッサ１の領域、以下同様にしてプロセッサＮの領域における第５のｍｐｄａｔａチャンクの割り振り状態を表す。チャンクは同型なので、オフセット方程式は次のようになる。
mpdata_base＋＜ビット＃＞＊＜チャンク・サイズ＞＋＜ＣＰＵ＃＞＊＜ＣＰＵオフセット・サイズ；例えば１Ｋ＞    （１）
【００３２】
マップ・ビットに対応する各チャンクは、そのプロセッサごとのセクション内で同じ相対開始バイト・オフセットにある。このオフセットは次のように計算することができる。
オフセット＝ビット数＊エリア・サイズ（例えば、１６）  （２）
【００３３】
ｍｐｄａｔａストレージ割り振りによって戻されるハンドルはエンコード値であり（好ましい実施形態では３２ビット値）、プロセッサの領域へのアクセスを可能にする。ｍｐｄａｔａストレージ・ブロックは、開始アドレスの最後の１２ビットがすべて０になるように割り振られる。したがって、先頭の２０ビットのみが重要である。最後の１２ビットはバイト・オフセットを格納するために使用される。本質的に、ハンドルは、ｍｐｄａｔａストレージ領域のプロセッサ０のコピーの有効アドレスであると考えることができる。
【００３４】
この割り振りフォーマットによれば、mpdata_get()カーネル・サービスおよびmpdata_getcpu()カーネル・サービスは、問題のプロセッサ（例えば、現行または指定されたプロセッサ）の論理プロセッサ識別子にプロセッサごとのセクション・サイズ（例えば１キロバイト）を乗算し、その積をハンドル値に加算し、その結果を戻すことによって、ｍｐｄａｔａストレージ・ブロックの領域の有効アドレスを簡単かつ効率よく戻して、その所期の機能を実施することができる。
有効アドレス＝（ＣＰＵ  ｉｄ＊セクション・サイズ）＋ハンドル値  （３）
【００３５】
本発明の別の実施形態では、６４ビット・カーネルを使用する。６４ビット・カーネルははるかに大きなアドレス・スペースを有するので、仮想スペースを事前に割り振り、より効率的なハンドル変換が使用できる。これは、マルチプロセッサ・システム全体に大きな固定サイズのメモリ・ブロックを割り振ることによって達成することができる。このブロックはプロセッサごとのセクションに分割される。ＮＵＭＡシステムでこの実装を効率的に行うために、プロセッサごとのセクションは、プロセッサにとってローカルなメモリに置かれる。３２ビット・カーネルの場合と同様に、割り振り状態を追跡するビットマスクがある。オフセットも、同じ関係式、つまり３２ビット・カーネルの実施形態と同様に式（２）を使用して計算される。
【００３６】
６４ビット・カーネルのアドレス・スペースは大きいため、本発明のｍｐｄａｔａストレージ技法は、固定アドレスで開始される。その結果、ハンドルは、単なるプロセッサ・セクションの始点からのオフセットになる。データへの参照を最適化するためには、固定された場所に各プロセッサのセクションの始点のアドレスを維持するのが最適である。この値は一定であるので、それに関連するキャッシュ・コヒーレンシーの問題がない。これによって、単にハンドル値をこの固定されたプロセッサごとの値に加算して、プロセッサのｍｐｄａｔａ領域の有効アドレスを見つけることができる。
【００３７】
３２ビット・カーネルの実施形態の場合と同様に、割り振りマスクの１ビットはＮ個のチャンクを参照する。しかし、ｍｐｄａｔａ割り振りが行われるときは、ストレージはオンラインのプロセッサ用にのみピン固定される。新しいプロセッサがオンラインまたはオフラインになるとき、ストレージは、状況に応じてピン固定またはピン解除される。
【００３８】
６４ビット・カーネルで使用されるｍｐｄａｔａストレージの量は大きくなる可能性があるので、ビットマスクを直接探索するのは非常に非効率となる可能性がある。したがって、ツリー構造を使用して割り振りリンク・リストを探索することができる。そのようなツリー構造では、ツリーの各ノードは、固定数の子、例えば４つの子を備え、各子のサブツリーに最長連続未使用セクションの長さのカウントを保持する。チャンクの固定サイズの領域を表す割り振りビットマスクが、ツリーの下端にあり、これをすばやく探索して、適切なサイズのフリー領域を見つけることができる。本発明のツリー構造は、各レベルに２つではなく４つの子を有する、標準的なバイナリー・ツリーの変形である。これは、ツリーのｌｏｇb（ｎ）個のレベルでｎ個のビットマスクを参照できることを意味し、ｂはツリーの各レベルにおける子の数である。
【００３９】
このようなツリーを作成し探索するために、mpdata_map_tree_tデータ構造を使用する。図４は、mpdata_map_tree_tデータ構造の一部を示す例示の図である。図４に示すように、このデータ構造はparent_count４１０を含んでいる。parent_count４１０は、その親ノードのカウント・アレイ４３０内で、当該parent_count４１０を含む子を参照する値を示すポインタである。さらに、このデータ構造は、親ノードに戻るポインタである親ポインタ４２０、子の索引付きサブツリーの最長未割振り領域の長さを記録するカウント・アレイ４３０、最後のツリー・レベルか否かを示すlast_levelビット４４０、ビットマスクの最初のビットによって参照されるチャンクのバイト・オフセットを示すオフセット４５０、およびツリーの下流にある４つのサブツリー構造を示す子アレイ４６０を含んでいる。
【００４０】
したがって、本発明によれば、大きなメモリ・ブロックを割り振るカーネル・サービスを使用することにより、システムの初期化時にまたは必要に応じてメモリ内でストレージ・ブロックが割り振られる。ストレージ・ブロックはさらに、適正に整合された同じ大きさのより小さい記憶域に分割され、その各記憶域がマルチプロセッサ・システムの単一プロセッサの専用となる。
【００４１】
さらに、割り振り済みのストレージ・ブロックを表すツリー構造が、ｍｐｄａｔａ割り振りが行われるたびに探索される。例えば、１２８バイトのｍｐｄａｔａ領域が割り振られる場合、利用可能な１２８の連続バイトを有するサブツリーを見つけるためにツリー構造が探索される。サブツリーが選択されると、その子のサブツリーのみを考慮して同じプロセスが繰り返される。このプロセスは、last_levelビットがセットされるまで繰り返され、その時点で、関連する割り振りマスクが探索されて、連続バイトの領域、つまり１２８バイトの連続領域が見つけられる。
【００４２】
図５は、例示的な一実施形態による本発明の例示的な動作の概要を示す流れ図である。図５に示すように、ｍｐｄａｔａに必要なサイズのメモリを決定するためにalloc()カーネル・サービスが呼び出されることから、動作が開始する（ステップ５１０）。次に、割り振り領域のサイズが有効なサイズであるかどうか判定が行われる（ステップ５２０）。そのサイズが有効である場合、mpdata_map_tree_t内でｔの値をmpdata_map_tree_tのルートに設定することにより、ｍｐｄａｔａを格納するのに十分なメモリ・スペースを有するノードの探索が開始される（ステップ５３０）。次にツリーが、割り振り領域のサイズをブロックサイズで割った値より大きいカウントをもつノードを有するかどうか判定が行われる（ステップ５４０）。そうでない場合または割り振り領域のサイズが無効である場合は、エラー・コードが戻される（ステップ５４５）。
【００４３】
割り振り領域のサイズをブロックサイズで割った値より大きいカウントをもつノードがある場合は、ｔがツリーの最終レベルを示すかどうか判定が行われる（ステップ５５０）。ｔがツリーの最終レベルを示す場合、割り振り領域を格納するのに十分なサイズを有する未割振りストリングを求めて、ｔの子の探索が行われる（ステップ５６０）。次に、その領域のオフセットが戻され（ステップ５７０）、動作が終了する。
【００４４】
ｔがｍｐｄａｔａマップ・ツリーの最終レベルを示していない場合、ｔのカウントが、割り振り領域のサイズをブロックサイズで割った値以上になるような、最小可能値にｉの値が設定される（ステップ５５５）。次にｔの値が、ｉに対応するｔの子にリセットされる（ステップ５５８）。次に動作は、ステップ５４０に戻り、ｔがｍｐｄａｔａマップ・ツリーの最終レベルを示すまで繰り返す。
【００４５】
本発明を、完全な機能をもつデータ処理システムの状況で説明したが、本発明のプロセスは、コンピュータ読み取り可能な命令の媒体の形および様々な形で配布することが可能であり、本発明が、配布を実施するために実際に使用される信号担持媒体の種類に関係なく等しく適用されることに留意されたい。コンピュータ読み取り可能な媒体の例には、フロッピ（Ｒ）・ディスク、ハード・ディスク・ドライブ、ＲＡＭ、ＣＤ−ＲＯＭなどの記録型媒体、およびディジタル通信リンクやアナログ通信リンクなどの伝送型媒体が含まれる。
【００４６】
本発明の説明は例示および説明の目的で提示したものであり、網羅的なものでも、開示された形式の発明に限定されるものでもない。当業者には多くの変更形態や変形形態が明らかであろう。本発明の原理および実際の応用例を最もよく説明し、他の当業者が、特定の用途に適した様々な変更を加えた様々な実施形態に関して本発明を理解できるように、実施形態を選択し説明した。
【図面の簡単な説明】
【図１】本発明による、データ処理システムの例示的な構成図である。
【図２】本発明による、ｍｐｄａｔａブロックを示す図である。
【図３】本発明の一実施形態による、リンク・リスト・データ構造を示す図である。
【図４】本発明の例示的な実施形態による、ｍｐｄａｔａマップ・ツリー・データ構造の一部を示す図である。
【図５】本発明の例示的動作の概要を示す流れ図である。
【図１】
0003836740.tif 000002
【図２】
0003836740.tif 000003
【図３】
0003836740.tif 000004
【図４】
0003836740.tif 000005
【図５】
0003836740.tif 000006