(57)【特許請求の範囲】
【請求項１】
読取プロセス−書込プロセス・ロック式のマルチプロセッサ・システムであって、
１つまたは複数のプロセッサからなる第１プロセッサ・グループと、
１つまたは複数のプロセッサからなる第２プロセッサ・グループと、
前記第１プロセッサ・グループによって共用され、前記第１プロセッサ・グループ内のプロセッサによるプロセスの実行においてロックを読取獲得したかどうかを示す、第１プライマリ・インジケータと、前記第１プライマリ・インジケータに関連し、前記マルチプロセッサ・システム内のプロセッサによるプロセスの実行において前記ロックを書込獲得したまたは書込獲得中であるかどうかを示す、第１セカンダリ・インジケータと、前記第２プロセッサ・グループによって共用され、前記第２プロセッサ・グループ内のプロセッサによるプロセスの実行において前記ロックを読取獲得したかどうかを示す、第２プライマリ・インジケータと、前記第２プライマリ・インジケータに関連し、前記マルチプロセッサ・システム内のプロセッサによるプロセスの実行において前記ロックを書込獲得したまたは書込獲得中であるかどうかを示す、第２セカンダリ・インジケータと、前記第１プロセッサ・グループ内のプロセッサおよび前記第２プロセッサ・グループ内のプロセッサによってアクセス可能で、前記第１プロセッサ・グループ内のプロセッサによるプロセスの実行において前記ロックを読取解放し、前記第１プライマリ・インジケータ内でそのような読取解放を示していないかどうかを示す、第３インジケータとを有するメモリと、
を含み、
前記第１プロセッサ・グループ内のプロセッサは前記第１プライマリ・インジケータを変更することによって前記ロックを読取獲得し、書込獲得中を示す前記第１セカンダリ・インジケータに変更し、
前記第２プロセッサ・グループ内のプロセッサは前記第２プライマリ・インジケータを変更することによって前記ロックを読取獲得し、書込獲得中を示す前記第２セカンダリ・インジケータに変更し、
前記第１プロセッサ・グループ内のプロセッサが、読取獲得しないことを示す前記第１プライマリ・インジケータに変更することまたは前記第３インジケータを変更することのいずれかによって前記ロックを読取解放し、書込獲得したことを示す前記第１セカンダリ・インジケータに変更して前記ロックを書込獲得し、前記第１プロセッサ・グループ内のプロセッサによるプロセスの実行終了に応答して、前記第２プロセッサ・グループ内のプロセッサが、書込獲得したことを示す前記第２セカンダリ・インジケータに変更して前記ロックを書込獲得する、
マルチプロセッサ・システム。
【請求項２】
前記第１プライマリ・インジケータが、第１カウンタである、請求項１に記載のマルチプロセッサ・システム。
【請求項３】
前記第１プロセッサ・グループ内のプロセッサが、前記第１カウンタを増分することによって前記ロックを読取獲得する、請求項２に記載のマルチプロセッサ・システム。
【請求項４】
前記第３インジケータが、第３カウンタであり、前記第１プロセッサ・グループ内のプロセッサが、前記第１プライマリ・インジケータを減分することまたは前記第３カウンタを減分することのいずれかによって前記ロックを読取解放する、請求項２または３に記載のマルチプロセッサ・システム。
【請求項５】
前記第３インジケータが、さらに、前記第２グループ内のプロセッサによってアクセス可能であり、さらに、前記第２プロセッサ・グループ内のプロセッサが前記ロックを読取解放し、前記第２プライマリ・インジケータでそのような読取解放を示していないかどうかを示すように適合される、請求項１に記載のマルチプロセッサ・システム。
【請求項６】
前記第２プロセッサ・グループ内のプロセッサは、前記第２プライマリ・インジケータを変更することによって前記ロックを読取獲得し、読取獲得しないことを示す前記第２プライマリ・インジケータに変更することまたは前記第３インジケータを変更することのいずれかによって前記ロックを読取解放する、請求項５に記載のマルチプロセッサ・システム。
【請求項７】
前記第２プライマリ・インジケータが、第２カウンタであり、前記第２プロセッサ・グループ内のプロセッサが、前記第２カウンタを増分することによって前記ロックを読取獲得する、請求項６に記載のマルチプロセッサ・システム。
【請求項８】
前記第３インジケータが、第３カウンタであり、前記第２プロセッサ・グループ内のプロセッサが、前記第２プライマリ・インジケータを減分することまたは前記第３カウンタを減分することのいずれかによって前記ロックを読取解放する、請求項７に記載のマルチプロセッサ・システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、全般的にはマルチプロセッサ・システムでのプロセス同期化に関する。具体的には、本発明は、システム内の他のプロセッサより少ない通信待ち時間を有するプロセッサ（ＣＰＵ）のグループを有するマルチプロセッサ・システムの読取プロセス−書込プロセス・ロックおよび関連する方法に関する。そのようなシステムには、non-uniform memory access（ＮＵＭＡ）アーキテクチャを有するマルチプロセッサ・システムが含まれるが、これに制限はされない。
【０００２】
【従来の技術】
マルチプロセッサ・システムには、定義によって、並列コンピューティングとして既知の形で、複数のプロセス（または単一プロセッサ内の複数のスレッド）を同時に実行できる複数のプロセッサ（本明細書ではＣＰＵとも称する）が含まれる。一般に、マルチプロセッサ・システムは、パーソナル・コンピュータ（ＰＣ）などのプログラムを順次実行する従来の単一プロセッサ・システムより高速に複数のプロセスまたはスレッドを実行する。実際の性能の利点は、マルチスレッド化されたプロセスおよび複数の別個のプロセスの諸部分またはその両方を並列に実行できる度合と、手近にある特定のマルチプロセッサ・システムのアーキテクチャとを含む複数の要因の関数である。プロセスを並列に実行できる度合は、部分的に、プロセスが共用メモリ・リソースへの排他アクセスについて競合する範囲に依存する。
【０００３】
共用メモリ・マルチプロセッサ・システムでは、すべてのプロセッサがアクセスできる共通の物理メモリ・アドレス・スペースが提供される。その中の複数のプロセス（または１プロセス内の複数のスレッド）が、メモリ内の共用変数を介して通信することができ、これによって、プロセスが、コンピュータ・システム内の同一のメモリ・ロケーションを読み書きすることができる。メッセージ・パッシング・マルチプロセッサ・システムは、共用メモリ・システムと異なって、プロセッサごとに分離可能なメモリ・スペースを有する。このシステムでは、プロセスが明示的なメッセージを介して互いに通信することが必要である。
【０００４】
共用メモリ・マルチプロセッサ・システムのアーキテクチャは、そのメモリが物理的にどのように編成されるかによって分類することができる。分散共用メモリ（ＤＳＭ）計算機では、メモリが、通常はプロセッサ・ノード上で、物理的に１つまたは複数のプロセッサの近くに配置されるモジュールに分割される。メモリ・モジュールのすべてが、グローバルにアクセス可能ではあるが、プロセッサは、他のノードのリモート・メモリよりも高速に、そのノード上のローカル・メモリにアクセスすることができる。メモリ・アクセス時間がメモリ・ロケーションに基づいて異なるので、そのようなシステムを、non-uniform memory access（ＮＵＭＡ）計算機とも呼ぶ。その一方で、集中共用メモリ計算機では、メモリが、物理的に１つのロケーションにある。集中共用メモリ・コンピュータは、メモリがプロセッサのそれぞれから時間的に等距離なので、uniform memory access（ＵＭＡ）計算機と呼ばれる。メモリ編成の両方の形態で、通常は、実行時間を減らすために、メイン・メモリと共に高速キャッシュが使用される。
【０００５】
性能を高めるためのＮＵＭＡアーキテクチャの使用は、ＮＵＭＡ計算機に制限されない。ＵＭＡ計算機のプロセッサのサブセットが、キャッシュを共用することができる。そのような配置では、メモリがすべてのプロセッサから等距離であるが、データが、計算機内の他のプロセッサ間より高速に（すなわち少ない待ち時間で）キャッシュを共用するプロセッサ間で循環することができる。したがって、ＮＵＭＡ計算機の性能を強化するアルゴリズムを、より低い待ち時間を有するプロセッサのサブセットを有するすべてのマルチプロセッサ・システムに適用することができる。これには、注記したＮＵＭＡ計算機および共用キャッシュ計算機だけではなく、複数のプロセッサがバス・インターフェース・ロジックの組を共用する計算機ならびにプロセッサに「ファン・アウト」する（通常は階層的な形での）相互接続を有する計算機も含まれる。
【０００６】
マルチプロセッサ・システムの設計の重要な問題が、プロセス同期化である。前に注記したように、プロセスを並列に実行できる度合は、部分的に、プロセスが共用メモリ・リソースへの排他アクセスについて競合する範囲に依存する。たとえば、２つのプロセスＡおよびＢが、並列に実行されつつある場合に、プロセスＢは、バッファにアクセスできるようになる前に、プロセスＡがそのバッファに値を書き込むのを待たなければならない場合がある。そうしなければ、競争状態が発生する可能性があり、その場合には、プロセスＢは、プロセスＡがバッファに値を書き込む機会を得る前にバッファにアクセスする可能性がある。
【０００７】
さらに説明するために、２つのプロセッサが、あるカウンタに１を加算する命令を有するプロセスを実行すると仮定する。具体的に言うと、この命令には、下記が含まれる。
カウンタをレジスタに読み込む。
レジスタに１を加算する。
レジスタをカウンタに書き込む。
２つのプロセッサが、これらの命令を並列に実行する場合には、第１プロセッサが、カウンタ（たとえば「５」）を読み取り、それに１を加算する（「６」がもたらされる）。第２プロセッサは、第１プロセッサと並列に実行中なので、第２プロセッサも、カウンタを読み取り（まだ「５」である）、それに１を加算する（「６」がもたらされる）。プロセッサの一方が、そのレジスタ（「６」が含まれる）をカウンタに書き込み、他方のプロセッサが同じことを行う。２つのプロセッサは、カウンタに１を加算する命令を実行したが、カウンタは、元の値より１つ大きいだけである。
【０００８】
この不正な結果を回避するために、プロセス同期化機構を設けて、プロセス実行の順序を制御する。これらの機構には、相互排他ロック（mutexロック）、条件変数、条件セマフォ、および読取プロセス−書込プロセス・ロックが含まれる。相互排他ロックを用いると、ロックを保持するプロセッサだけが、関連するアクションを実行できるようになる。プロセッサが、相互排他ロックを要求する時に、相互排他ロックが、そのプロセッサに排他的に与えられる。ロックを所望する他のプロセッサは、ロックを有するプロセッサがロックを解放するまで待たなければならない。上で説明したカウンタに１を加算するシナリオを解決するためには、たとえば、第１プロセッサと第２プロセッサの両方が、さらに実行する前に相互排他ロックを要求する。どれであれ、最初にロックを獲得したプロセッサが、カウンタを読み取り、レジスタを増分し、カウンタに書き込んだ後にロックを解放する。他方のプロセッサは、第１のプロセッサが終了し、ロックを解放するまで待たなければならず、その後、ロックを獲得し、カウンタに対する動作を実行し、ロックを解放する。この形で、ロックによって、命令が２回実行される場合に、並列に動作するプロセッサがそれを実行する場合であっても、カウンタが２回増分されることが保証される。
【０００９】
プロセスを同期化するために、排他アクセスを必要とする命令を、クリティカル・セクションにグループ化し、ロックに関連付けることができる。プロセスが、そのクリティカル・セクション内の命令を実行している時に、相互排他ロックによって、他のプロセスが同一の命令を実行していないことが保証される。これは、プロセスが、データの変更を試みる場合に重要である（上の例で説明したように）。しかし、そのようなロックは、複数のプロセスが、プロセスがデータを読み取ることだけを許可する命令を同時に実行することを禁止するという点で、短所を有する。対照的に、読取プロセス−書込プロセス・ロックでは、複数の読み取るプロセス（「読取プロセス」）が、データベースなどの共用リソースに同時にアクセスすることが許可されるが、整合性のために、書き込むプロセス（「書込プロセス」）は、更新を実行する前にデータベースに対する排他アクセスを有しなければならない。読取プロセス−書込プロセス・ロックに適当な情況の実用的な例が、多数の読取プロセスと情報のたまの更新を有するＴＣＰ／ＩＰルーティング構造である。読取プロセス−書込プロセス・ロックの初期の実施形態が、クルトア（Courtois）他著、「Concurrent Control with 'Readers' and 'Writers'」、Communications of the ACM, 14(10):667-668（１９７１年）に記載されている。より最近の実施形態が、メロウ−クラミイ（Mellor-Crummey）およびスコット（Scott（ＭＣＳ））共著、「Scalable Reader-Writer Synchronization for Shared-Memory Multiprocessors」、Proceedings of the Third ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming, pages 106-113（１９９１年）と、セイ（Hseih）およびウェイル（Weihl）共著、「Scalable Reader-Writer Locks for Parallel Systems」、Technical Report MIT/LCS/TR- 521（１９９１年１１月）に記載されている。
【００１０】
読取プロセス−書込プロセス・ロックの基本的な機構および構造は、周知である。通常のロックでは、複数の読取プロセスが、ロックを獲得することができるが、これは、アクティブな書込プロセスがない場合に限られる。逆に、書込プロセスは、アクティブな読取プロセスおよび他の書込プロセスがない場合に限って、ロックを獲得することができる。読取プロセスがロックを解放する時に、その読取プロセスは、最後のアクティブな読取プロセスでない場合には、何も行わないが、最後のアクティブな読取プロセスである場合には、次の待機中の書込プロセスをウェイク・アップする。書込プロセスは、ロックを解放する時に、別の書込プロセスまたは待機中のすべての読取プロセスをウェイク・アップする。読取プロセス−書込プロセス・ロックは、通常は、共用リソースにアクセスできるかどうかを示すセマフォの使用を介して実施される。セマフォは、２つのアトミック動作、Ｐ（）およびＶ（）をサポートする整数値オブジェクトである。Ｐ（）動作は、セマフォの値を減分し、ロックを獲得する。Ｖ（）動作は、値を増分し、ロックを解放する。セマフォの値を読み取ることによって、プロセッサは、関連する共用リソースが使用可能または使用中のどちらであるかを知ることができる。
【００１１】
従来の読取プロセス−書込プロセス・ロックの短所は、共用リソースの使用を望む各プロセッサが、そのリソースが使用可能であるかどうかを判定するために継続的にロックをポーリングする、望ましくない「スピン・オン・ザ・ロック（spinning on the lock）」である。複数のプロセッサが、１つのロックについてスピンする時に、これらのプロセッサは、ロックについて争い、バスおよびシステム相互接続上で過剰なトラフィックを生成することによって、システム性能を低下させる。これを、オーバーヘッドと称する。この短所は、セイおよびウェイルに記載されたものなどのより最近のロッキング方式で部分的に対処されている。セイおよびウェイルの静的ロッキング・アルゴリズムでは、プロセッサのローカル・メモリに保管される、プロセッサごとに１つのセマフォが割り振られる。追加のセマフォが、書込プロセスに対するゲートとして働く。静的ロックを獲得するために、読取プロセスは、そのローカル・セマフォを獲得するだけでよく、ローカル・スピンの量が大幅に減らされる。しかし、書込プロセスは、やはりすべてのセマフォを獲得しなければならず、このセマフォは、プロセッサごとに１つと、追加のセマフォがある。静的ロックを解放する時には、読取プロセスは、単にそのローカル・セマフォを解放するが、書込プロセスは、すべてのセマフォを解放する。したがって、このロックは、読取プロセスがお互いに干渉せず、読取プロセスが、ロックを獲得するためにシステム相互接続を介する必要がないという点で、従来のロックに対する改善を提供する。しかし、読取プロセスが、絶対に干渉しないという事実は、書込プロセスが、多数のプロセッサを有するシステム内でかなりの量の作業を行わなければならないことを意味する。要求の数％だけが書込である時であっても、書込プロセスが、成功裡にロックを獲得するために、すべてのノード上のすべてのプロセッサのセマフォを獲得しなければならないので、スループットが劇的に低下する。この問題を克服するために、セイおよびウェイルの動的ロック方式では、アクティブ読取プロセスを単一のメモリ・ロケーションで記録し、これらの読取プロセスに関連するセマフォだけを獲得することによって、書込プロセスが獲得しなければならないセマフォの数を減らすことが試みられた。この方式は、さまざまなmutexロックおよびキューを使用してこれを達成する。しかし、その代価は、読取プロセスによる競合およびシステム・トラフィックの増加である。
【００１２】
【発明が解決しようとする課題】
したがって、本発明の目的は、読取プロセス・オーバーヘッドを過度に増やさずに、書込プロセス・オーバーヘッドを減らす、マルチプロセッサ・システム用の読取プロセス−書込プロセス・ロックおよび方法を提供することである
【００１３】
【課題を解決するための手段】
本発明によるマルチプロセッサ・システム用のネスト可能読取プロセス−書込プロセス・ロックには、複数のプロセッサの第１グループによって共用される第１プライマリ・インジケータが含まれ、第１プライマリ・インジケータは、第１プロセッサ・グループ内のプロセッサで稼動するプロセスが、ロックを読取獲得したかどうかを示すように適合される。第１セカンダリ・インジケータが、第１プライマリ・インジケータに関連し、セカンダリ・インジケータは、プロセスがロックを書込獲得したか、ロックの書込獲得中であるかどうかを示すように適合される。第２プライマリ・インジケータが、１つまたは複数のプロセッサの第２グループによってアクセス可能であり、第２プライマリ・インジケータは、第２プロセッサ・グループ内のプロセッサで稼動するプロセスが、ロックを読取獲得したかどうかを示すように適合される。第２セカンダリ・インジケータが、第２プライマリ・インジケータに関連し、第２セカンダリ・インジケータは、プロセスがロックを書込獲得したか、ロックの書込獲得中であるかどうかを示すように適合される。第３インジケータが、少なくともプロセッサの第１グループによってアクセス可能であり、第１グループ内のプロセッサで稼動するプロセスが、ロックを読取解放し、第１プライマリ・インジケータでその読取解放を示していないかどうかを示すように適合される。
【００１４】
本発明の上記および他の態様を、例示的実施形態の以下の説明で説明し、添付図面に示す。
【００１５】
【発明の実施の形態】
本発明は、本明細書で示され、説明されるものなどのマルチプロセッサ・システムで実施された。しかし、この開示から、本発明が、この実施形態に制限されるのではなく、複数のノードを有し、ノード内のプロセッサ間の通信待ち時間が異なるノード内のプロセッサ間の通信待ち時間より短い、すべての適当なコンピュータ・システムで適用可能であることが、容易に諒解される。示される実施形態は、各ノードがローカル・メモリを有するＮＵＭＡ計算機で実施された本発明を示すが、本発明を、他のマルチプロセッサ・システムに適用することができる。プロセッサがグループ化され、その結果、あるプロセッサが他のプロセッサよりかなり短い通信待ち時間を有するシステム設計（たとえば、プロセッサがグループ化されてキャッシュを共用するＵＭＡ計算機）で、開示されるロッキング方式から利益を得ることができる。用語「ノード」には、本明細書では、プロセッサのそのようなグループ化が含まれる。用語「プロセス」は、本明細書では、スレッド、タスク、軽量プロセス、ジョブ、および同等の代用品にも適用されることが意図されている。
【００１６】
システムの概要
図１は、分散共用メモリ（ＤＳＭ）に基づくコンピュータ・アーキテクチャを使用するマルチプロセッサ・システム１０のブロック図である。このタイプのコンピュータ・システムを、ＮＵＭＡ計算機とも称する。４つのノード１から４が、どのノードでも他の任意のノードと通信できるようにするシステム相互接続２０（すなわちネットワーク）によって接続されて示されている。システム相互接続２０の目的は、どのノードのプロセッサでも、他のノードに常駐する物理メモリに直接に透過的にアクセスできるようにすることである。システム相互接続２０は、例示的実施形態ではScalable Coherent Interface（ＳＣＩ）相互接続機構を使用する、スイッチベースのネットワークである。ＳＣＩは、ＩＥＥＥによって認可された標準規格であり、ＩＥＥＥ  Ｓｔｄ  １５９６−１９９２（１９９３年）、およびイワン・ツビング（Ivan Tving）による修士論文、「Multiprocessor Interconnection Using SCI」、ＤＴＨ  ＩＤ−Ｅ  ５７９（１９９４年）を含む複数の刊行物で明確に文書化されている。ＳＣＩ機構を使用するマルチプロセッサ・システムが、米国特許第５８０２５７８号に図示され、説明されている。
【００１７】
相互接続２０の物理リンクは、高帯域幅および短い待ち時間を提供し、より多くのノードの追加を可能にするためにスケーラブルである。これらの要件を満たすリンクには、現在、１ギガバイト毎秒以上のデータ・スループットを有するポイントツーポイント相互接続が含まれる。リンクは、リング・トポロジ、スイッチを介する任意のトポロジ、またはこの両方の組み合わせなど、ノード１から４を接続する複数の方法で構成することができる。リンクは、システムの性能の必要に応じて、有線または無線（光、ＲＦなど）とすることができる。追加のトポロジが、ジョンソン（Ross E. Johnson）およびグッドマン（James E. Goodman）共著、「Interconnect Topologies with Point-To-Point Rings」、１９９１年１２月、Computer Sciences Technical Report #1058, University of Wisconsin - Madisonに記載されている。
【００１８】
システム１０のノードのブロック図を、図２に示す。ノードには、複数のプロセッサ２４をローカル・メモリ２６（コンピュータ可読媒体）に接続する対称型マルチプロセッサ（ＳＭＰ）ノード・バス２２が含まれる。わかりやすくするために、ノード１から４を、ホーム・ノードまたはリモート・ノードと称する場合がある。ホーム・ノードとは、そのローカル・メモリに当のメモリ・ブロックが保管される（すなわち、メモリ・ブロックの物理アドレスが、ローカル・メモリまたはキャッシュによってサポートされるアドレス範囲に含まれる）ノードであり、他のノードのすべてが、そのメモリ・ブロックに関してリモート・ノードである。さらに、ノードが、要求ノードまたは応答ノードになる場合がある。要求ノードは、データを要求するノードであり、応答ノードは、要求されたデータを供給するノードである。
【００１９】
やはりバス２２に接続される入出力装置２８が、コンピュータ・システムと外部の世界との間で情報を通信するために、ノードをコンピュータ・システム１０の外の装置に接続する。入出力装置２８は、従来の設計とすることができ、入出力装置２８には、コンピュータ・システム１０との通信を望むパーソナル・コンピュータ、ローカル・エリア・ネットワークなどにノード（およびシステム１０）を接続する手段が含まれる。入出力装置２８は、フロッピ・ディスク、ハード・ディスク、ＣＤ−ＲＯＭ、および他のコンピュータ可読媒体などの周辺装置への接続も可能にすることができる。
【００２０】
ノードをシステム内の他のノードに接続するために、ノードには、システム相互接続インターフェース３０が含まれる。システム相互接続インターフェースは、ノードとコンピュータ・システム１０の他のノード上のインターフェース・デバイスとの間の物理リンクと共に、相互接続２０の一部を形成する。図示の実施形態では、インターフェース３０が、ノード間のデータ通信に関してＳＣＩ標準規格を実施するように構成され、あるノードのプロセッサが物理的に別のノードに配置されたメモリに透過的にアクセスできるようになる。インターフェース３０には、他のノードから受け取ったデータをキャッシングするリモート・キャッシュも含まれる。
【００２１】
システム１０のノードのそれぞれに、複数のプロセッサまたはＣＰＵ２４が含まれ、そのＣＰＵ２４のそれぞれが、複数の割込みレベルをサポートする。各プロセッサは、プロセッサのキャッシング方式に従ってプロセッサ用のデータをキャッシュに入れる、少なくとも１つのプロセッサ・キャッシュ２５を有する。ノード内のＣＰＵを、さらに、下で説明するＣＰＵループに編成することができる。
【００２２】
ＣＰＵグループ
図３は、ノード１から４のプロセッサがＣＰＵグループに編成されて示された、システム１０のブロック図である。たとえば、ノード１のプロセッサ０および１が、ＣＰＵグループ０に編成される。この例示的実施形態では、ノードごとに２つのＣＰＵグループがあり、グループごとに２つのＣＰＵがある。図９を参照すると、各ＣＰＵグループ番号が、システム・メモリに保管されるデータ構造３２に含まれる。このデータ構造には、上位ビットにノード番号、下位ビットにノード内ＣＰＵグループ番号が含まれる。ＣＰＵグループ番号は、プロセスがロックを獲得する時にそのプロセスが稼動していたプロセッサを含むプロセッサ・グループを示すように適合された識別子として働く。
【００２３】
図示の実施形態では、グループごとのＣＰＵの数が、システム１０内のＣＰＵの数およびノードごとのＣＰＵの数に応答して、システム・コマンドによってセットされる。ＣＰＵの総数が１６個以下であり、ノードごとに４つのプロセッサがある場合には、グループのそれぞれに、１つのＣＰＵが含まれることが好ましい。しかし、これは、望みに応じて変更することができる（この実施形態では）。ＣＰＵの数が３２個以下であるが１６個を超える場合には、グループのそれぞれに２つのＣＰＵが含まれる。ＣＰＵの数が３２個より多い場合には、グループのそれぞれに４つのＣＰＵが含まれる。代替案では、デフォルト挙動が事前に決定されず、グループのＣＰＵの数を、システム・オペレータが指定する必要があるものとすることができる。
【００２４】
グループごとのＣＰＵの数が重要なのは、図５から８に示されているように、各ＣＰＵグループが、ロックのそれぞれについて、カウンタおよび関連するフラグからなるロック構造を共用するからである。複数のＣＰＵグループのロック構造が、本発明による単一の読取プロセス−書込プロセス・ロックの一部を形成する。プロセスの読取対書込比が大きいほど、より小さいＣＰＵグループの利益が大きくなる。プロセスが読取を実行している時に、他のＣＰＵに通知する必要がなく、グループごとのＣＰＵの数を１つまで減らすことによって、共用カウンタの更新を減らすかなくすことができる。システム内のＣＰＵの数が多いほど、より大きいＣＰＵグループの利益が大きくなる。グループごとのＣＰＵの数を増やすと、セットしなければならない関連するフラグの数を減らすことによって、書き込むプロセスがロックを獲得するために行わなければならない作業の量が減る。
【００２５】
オペレーティング・システムとロックの相互作用
図４に、カーネル５４、システム呼出しインターフェース５６、および入出力装置７６への入出力インターフェース５８を含む、コンピュータ・システム１０のオペレーティング・システム５２を示す。図示のオペレーティング・システムは、ＵＮＩＸ（Ｒ）ベースのオペレーティング・システムであるが、他のオペレーティング・システムを使用することができる。カーネル５４は、１つまたは複数のノードのローカル・メモリ２６に保管されるプログラムである。メモリ２６、プロセッサ２４、およびコンピュータ・システム１０の他のハードウェアが、カーネル５４の実行に使用され、全般的にコンピュータ・ハードウェア６０として示されている。カーネル５４は、コンピュータ・システムのリソースを制御し、各ユーザ要求がシステム・リソースの公平な共用を受け取るようにユーザ要求をスケジューリングする責任を負う。システム・リソースは、たとえば、ロック、入出力装置、共用メモリ・セグメント、ファイル、プロセス、プロセッサなどとすることができる。
【００２６】
システム１０でのアプリケーションの実行中に、要求が、アドレス・スペース６２内で動作するシステム・プロセス６４とプロセス６６および６７などの１つまたは複数のプロセスによって生成される。プロセス６６などのプロセスには、プログラム６８の一部（すなわち命令）と、プログラムを実行する実行環境が含まれる。たとえば、実行環境には、スタック７０、ローカル変数を保管する専用データ７２、および、プロセスに関連する物理メモリを定義するのに使用されるページ・テーブル７４が含まれる。システム・プロセス６４と２つのプロセス６６および６７だけが図示されているが、任意の数のプロセスおよびプロセスが、ある時点でノードで稼動することができる。
【００２７】
プロセスは、システム呼出しを介してカーネル５４に要求を行い、このシステム呼出しは、システム呼出しインターフェース５６によってカーネルに渡される。これらの要求は、プロセスが異なるプロセッサ上で稼動している場合には並列に発生する可能性があるが、これらの要求には、データベース内の共用オブジェクトに対する読取または書込が含まれる。この要求を満たすために、カーネルには、本発明に従って構成される読取プロセス−書込プロセス・ロックを処理する複数の機能またはプリミティブが含まれる。具体的に言うと、プリミティブは、ロック要求、ロック解放、および割込みに効率的な形で応答しながら共用リソースへのプロセス・アクセスを同期化する、下で説明するあるデータ構造を処理する。図示の実施形態では、プリミティブは、プロセスが、ロックの書込獲得および書込解放と、ロックの排他読取獲得および排他読取解放と、排他読取獲得されたロックの書込獲得されたロックへのアップグレードと、ロックの読取獲得および読取解放を行うことを許可する。
【００２８】
第１実施形態の読取プロセス−書込プロセス・ロック構造
図５に、本発明による複数の読取プロセス−書込プロセス・ロック８０ａからｐを示す。図示の実施形態の各ロック８０には、２つの部分すなわち、グローバル構造８１と、ＣＰＵグループごとのロック構造８３（図６）の組８２が含まれる。各ロック８０のグローバル構造８１には、セマフォ、カウンタ、および関連するカウンタの組８２へのポインタが含まれる。その関係するフィールドを、表１に示す。
【００２９】
【表１】
0003880398.tif 000002
【００３０】
図６を参照すると、ＣＰＵグループごとのロック構造８３が示されている。これには、カウンタ８４およびフラグ８５が含まれる。カウンタ８４は、ロックを保持している読み取るプロセスの数を示す。フラグ８５には、WRITER_LOCKINGビット８５ａおよびWRITER_LOCKEDビット８５ｂが含まれる。ビット８５ａがセットされている場合には、これは、プロセスが、ロックを書込獲得しようとしているが、現在そのロックを読取獲得している、読取保持しているプロセスがあることを示す。ビット８５ｂがセットされている場合には、これは、プロセスが読取プロセス−書込プロセス・ロックを書込保持していることを示す。本発明の図示の実施形態では、ロック構造（カウンタおよび関連するフラグ）が、１ワードにエンコードされ、これは、プロセッサが、１動作でロック構造を操作できることを意味する。
【００３１】
図５に戻って、ロック８０ａの構造の組８２には、ノード１から４にまたがって０ａから７ａの符号を付された構造８３が含まれる。ロック８０ｉの構造の組８２ｉに、これらのノードにまたがって０ｉから７ｉの符号を付された構造８３が含まれる。特定のＣＰＵグループのロック構造８３は、そのＣＰＵグループによって占められるノードのローカル・メモリの１ページに保管される。図５では、たとえば、システム１０が、ノードごとに２つのＣＰＵグループを用いて構成される。各グループに、２つのＣＰＵ（ノードごとに合計４つのＣＰＵ）が含まれる。ノード１のローカル・メモリ・ページに、ＣＰＵグループ０および１に関する、ロック８０ａの構造０ａおよび１ａが含まれる。同様に、ノード２のローカル・メモリ・ページに、ＣＰＵグループ２および３に関する、ロック８０ａの構造２ａおよび３ａが含まれる。ノード３のローカル・メモリ・ページには、ＣＰＵグループ４および５に関する、ロック８０ａの構造４ａおよび５ａが含まれる。ノード４のローカル・メモリ・ページには、ＣＰＵグループ６および７に関する、ロック８０ａの構造６ａおよび７ａが含まれる。
【００３２】
図５の、メモリ・ページ内でのロック構造８３の配置に留意されたい。同一の読取プロセス−書込プロセス・ロックの一部であるが異なるＣＰＵグループの一部であるロック構造、たとえば構造０ａおよび構造１ａが、ローカル・メモリ２６の異なる行（すなわち、システムを単一の単位として移動するメモリのブロック）に保管される。これは、異なるグループのプロセッサが、同一のメモリ行について競争しないようにするために行われる。また、異なる読取プロセス−書込プロセス・ロックの一部であるが同一のＣＰＵグループの一部であるロック構造８３（すなわち、０ａ、０ｂなど）が、メモリの同一の行に保管される（インターリーブされて）ことに留意されたい。同一のＣＰＵがキャッシングされた行を共用するので、これによって、大きな性能コストなしにメモリ・リソースが節約される。
【００３３】
図５に示され、表１に記されているように、特定のロック８０のグローバル構造８１は、ＣＰＵグループ０のロック構造８３をポイントする。特定のロック８０の他の構造８３には、アドレス演算を介して最初のロック構造から達することができる。
【００３４】
グループごとのＣＰＵの数（したがってロック構造ごとのＣＰＵの数）を変更することができる。上で注記したように、グループ・サイズは、当初は、システム１０内のＣＰＵの数から決定することができ、その後、その決定に従ってノードに割り振ることができる。しかし、この割振りは、動的とすることができ、混合されたものとすることができる、すなわち、一部のノードがグループごとにある個数のＣＰＵを有し、他のノードがグループごとに異なる個数のＣＰＵを有することができる。あるいは、グループごとのＣＰＵの数を均一とし、システム１０が変更された時またはグループごとの所望の数が変化した時に変更することができる。これを可能にするために、その要素が異なるロック構造の組８２をポイントする、もう１つのデータ構造（図５に示された配列８６など）を設けることができる。適当な要素ポインタが、所望のカウンタの組の配列から選択される。図５の例では、組８２が、グループごとに２つのＣＰＵまたは、ノードごとに４つのＣＰＵを有する４ノード・システムの８個のカウンタを有する。他のカウンタの組によって、グループごとに４つのＣＰＵ（合計４個のカウンタ）、グループごとに１つのＣＰＵ（合計１６個のカウンタ）などを提供することができる。
【００３５】
読取プロセス−書込プロセス・ロックの動作
各ロック８０に、特定の共用オブジェクトが関連する。共用オブジェクトへのアクセスを獲得する最初の試みの際に、グループ内のＣＰＵが、構造８３をローカル・メモリ２６からローカル・キャッシュ２５に読み込む。その後、カウンタ８４およびフラグ８５が、ＣＰＵのキャッシング方式に従って、グループ内のＣＰＵの間で更新される。図５の例では、ＣＰＵ０および１が、ＣＰＵグループ０に含まれ、ロック８０ａに関して構造０ａを共用する。ＣＰＵ０で稼動するプロセスが、ロック８０ａによって保護される共用オブジェクトの読取を求める場合に、そのプロセスは、メモリ２６から構造０ａを獲得し、構造０ａ内のカウンタ８４の値を増分する。ＣＰＵ１で稼動するプロセスが、そのオブジェクトの読取を望む場合に、このプロセスは、ＣＰＵ０のキャッシュから構造０ａのコピーを獲得し、カウンタをもう一度増分する。システム１０内のいずれかのＣＰＵで稼動するプロセスが、ロック８０ａによって保護される共用オブジェクトへの書込を望む場合に、そのプロセスは、ロック構造０ａから７ａのフラグ８５をセットする。しかし、複数のＣＰＵがフラグを共用するので、グループごとに複数のＣＰＵがある時には、セットしなければならないフラグの数が減る。競争状態を防ぐために、各ロック８０が、複数のＣＰＵが書込関連動作を実行しないようにするmutex（表１を参照されたい）を有する。
【００３６】
詳細に言うと、オペレーティング・システム・カーネル５４が、１つまたは複数の適当なプリミティブ（下で詳細に説明する）を呼び出すことによって、共用オブジェクトへのアクセスのプロセス要求に応答する。それを行う際に、カーネルは、呼び出されるプリミティブにロックへのポインタを渡す。プロセスは、他の２つの引数も渡すことができる。一方の引数は、ロックが即座に使用可能でない場合にプロセスがブロックされる優先順位を表す整数である。他方は、セットされた場合に、プロセス・ウェイクアップ時にプリミティブがプロセス終了についてテストしなければならないことを示す、終了フラグである。セットされない場合には、プロセスがその間に強制終了された場合であっても、読取プロセス−書込プロセス・ロックが、書込獲得される。
【００３７】
その後、選択されたプリミティブが実行される。ロックが使用不能である場合には、要求するプロセスが、所望の優先順位でブロックされる。ロックが使用可能である場合には、終了フラグを検査して、プロセス状況を検査しなければならないかどうかを調べる。そうである場合には、カウンタを検査し、ロックを獲得する前に、要求するプロセスを、アクティブ状況について検査する。プロセスがアクティブでない場合には、ロック要求を打ち切る。
【００３８】
以下の表に、さまざまなプリミティブがロック８０の構造とどのように相互作用するかを擬似コードで示す。
【００３９】
p_commonプリミティブ
p_commonプリミティブは、ロック８０を書込獲得し、これによって、プロセスが、そのロックによって保護される共用オブジェクトに書き込めるようにするために、プリミティブp_writerおよびu_exreader2writerによって呼び出される。このプリミティブは、ロック８０の各構造８３のフラグ８５をセットして、書き込むプロセスがロックを獲得したことを示す。しかし、ＣＰＵグループ・サイズが大きいほど、セットしなければならないフラグの数が減る。p_commonが書込プロセスのためにロックの獲得を試みる時に、読取プロセスが存在する場合には、書込プロセスが、スリープ状態にされ、その後、すべての読取プロセスが終了した後に覚醒される。
【００４０】
【表２】
0003880398.tif 000003
【００４１】
p_writerプリミティブ
p_writerプリミティブは、まず、書込獲得を１つの書込プロセスに制限するグローバル相互排他ロック（readers_writers_mutex）を獲得することによって、書込プロセスのために、指定された読取プロセス−書込プロセス・ロックを獲得する。このプリミティブは、必要な場合に、p_commonを呼び出して、関連する構造８３のフラグ８５を変更する。これは、必ず必要とは限らない。ある書込プロセスが、別の書込プロセスに続く場合には、第１の書込プロセスがフラグをクリアせずに、第２の書込プロセスがロックを獲得することができる。これによって、第１の書き込むプロセスがロックを解放したことを示すためにフラグをクリアする必要がなくなり、その後に、第２の書き込むプロセスがロックを書込獲得したことを示すためにフラグをセットする必要がなくなる。第１の書込プロセスは、v_writerプリミティブ（下で説明する）を介して、第２の書込プロセスが待っていることを知り、構造８３のフラグをセットされたままにする。第２の書込プロセスは、書き込むプロセスが稼動するプロセッサのノードの構造８３のフラグ８５などのインジケータを検査することによって、フラグがセットされたままであることを知る。
【００４２】
【表３】
0003880398.tif 000004
【００４３】
v_writerプリミティブ
v_writerプリミティブは、ロック８０内の各構造８３のフラグをクリアすることによって、ロックを書込解放するために呼び出される。しかし、このフラグのクリアは、必ず必要とは限らない。readers_writers_mutexを獲得する、キュー内の次のプロセスが書込プロセスであると判定される場合には、フラグはクリアされない。この判定は、readers_queuedフィールド（排他読取プロセスがキューに入れられていることを示す）とreaders_writers_mutex（書込プロセスまたは排他読取プロセスがキューに入れられていることを示す）の組み合わせなどのインジケータを検査することによって行われる。もちろん、単一のフィールドなどの他のインジケータを使用することができる。フラグをクリアするか、次の書込プロセスのためにセットされたままにするかにかかわらず、このプリミティブは、readers_writer_activeカウンタを減分して、書込解放を注記する。
【００４４】
【表４】
0003880398.tif 000005
【００４５】
p_exreaderプリミティブ
p_exreaderプリミティブは、指定されたロックを排他的に読取獲得する。排他読取は、共用オブジェクトの現在の内容を変更せずに、プロセスが共用オブジェクトに何かを追加できるようにするのに使用することができる。
【００４６】
【表５】
0003880398.tif 000006
【００４７】
v_exreaderプリミティブ
v_exreaderプリミティブは、指定されたロックを排他的に読取解放する。
【００４８】
【表６】
0003880398.tif 000007
【００４９】
u_exreader2writerプリミティブ
u_exreader2writerプリミティブは、排他読取獲得されたロックを書込獲得されたロックにアップグレードする。
【００５０】
【表７】
0003880398.tif 000008
【００５１】
p_readerプリミティブ
p_readerプリミティブは、指定されたロックを読取獲得する。
【００５２】
【表８】
0003880398.tif 000009
【００５３】
v_readerプリミティブ
v_readerプリミティブは、指定されたロックを読取解放する。
【００５４】
【表９】
0003880398.tif 000010
【００５５】
第１の実施形態の産業上の利用可能性
上で説明した読取プロセス−書込プロセス・ロックの第１の実施形態は、読取プロセス−書込プロセス・ロックのネストが禁止され、その結果、任意の所与のスレッドが、多くとも１つの読取プロセス−書込プロセス・ロックを保持できる場合に、非常に良好に動作する。この第１の実施形態は、任意の所与のスレッドによって同時に読取保持することができる読取プロセス−書込プロセス・ロックの最大個数が、小さく、前もって既知である場合に、ネスティングを可能にするように簡単に拡張することができる。この場合に、各スレッドに、現在読取保持されている読取プロセス−書込プロセス・ロックのそれぞれを追跡する小さい配列を含めることができる。しかし、所与のアプリケーションが同時に読取保持する必要がある読取プロセス−書込プロセス・ロックの数が限られていない場合には、読取保持されるロックのリストを維持するオーバーヘッドが、簡単に第１の実施形態の性能の利益を圧倒する可能性がある。
【００５６】
第２の実施形態のネスト可能な読取プロセス−書込プロセス・ロック構造
第２の好ましい実施形態では、読取プロセス−書込プロセス・ロックを任意の深さにネストすることができ、その結果、所与のスレッドが、無制限の数の読取プロセス−書込プロセス・ロックを保持することができる場合が、効率的に処理される。この追加の柔軟性には、読取解放コードに追加の検査が含まれるというわずかな代償がある。読取プロセス−書込プロセス・ロックの複数の異なるＣＰＵおよびＯＳ環境で動作する能力を実証するために、この第２の実施形態は、６４ビットＣＰＵ、ＲＩＳＣスタイル・アトミック動作（したがって、ＲＩＳＣ  ＣＰＵによって提供されるメモリ同期化動作を必要とする）、およびＩＢＭ／ＤＥＣ／ＯＳＦ−１スタイルのアサート−待機／ブロック／覚醒プリミティブ用に構成された。この第２の実施形態は、書込獲得を打ち切る能力も、排他読取プロセスの概念も提供しない。しかし、これらの２つの特徴は、簡単に追加することができる。
【００５７】
図７に、本発明による複数の読取プロセス−書込プロセス・ロック９０ａからｐを示す。図示の実施形態の各ロック９０には、２つの部分すなわち、グローバル構造９１および、ＣＰＵグループごとのロック構造９３（図８）の組９２が含まれる。各ロック９０のグローバル構造９１には、セマフォ、カウンタ、および関連するカウンタの組９２へのポインタが含まれる。関係するフィールドを、表１０に示す。
【００５８】
【表１０】
0003880398.tif 000011
【００５９】
図８を参照すると、ＣＰＵグループごとのロック構造９３が示されている。これには、カウンタ９４およびフラグ９５が含まれる。カウンタ９４は、ロックを保持している読み取るプロセスの数を示す。フラグ９５には、WRITER_LOCKINGビット９５ａが含まれる。ビット９５ａがセットされている場合には、これは、プロセスが、ロックを書込獲得しようとしているが、現在そのロックを読取獲得している、読取保持しているプロセスがあること、または、プロセスが読取プロセス−書込プロセス・ロックを書込保持していることを示す。本発明の図示の実施形態では、ロック構造（カウンタおよび関連するフラグ）が、１ワードにエンコードされ、これは、プロセッサが、１動作でロック構造を操作できることを意味する。
【００６０】
図７に戻って、ロック９０ａの構造の組９２には、ノード１から４にまたがって０ａから７ａの符号を付された構造９３が含まれる。ロック９０ｉの構造の組９２ｉに、これらのノードにまたがって０ｉから７ｉの符号を付された構造９３が含まれる。特定のＣＰＵグループのロック構造９３は、そのＣＰＵグループによって占められるノードのローカル・メモリの１ページに保管される。図７では、たとえば、システム１０が、ノードごとに２つのＣＰＵグループを用いて構成される。各グループに、２つのＣＰＵ（ノードごとに合計４つのＣＰＵ）が含まれる。ノード１のローカル・メモリ・ページに、ＣＰＵグループ０および１に関する、ロック９０ａの構造０ａおよび１ａが含まれる。同様に、ノード２のローカル・メモリ・ページに、ＣＰＵグループ２および３に関する、ロック９０ａの構造２ａおよび３ａが含まれる。ノード３のローカル・メモリ・ページには、ＣＰＵグループ４および５に関する、ロック９０ａの構造４ａおよび５ａが含まれる。ノード４のローカル・メモリ・ページには、ＣＰＵグループ６および７に関する、ロック９０ａの構造６ａおよび７ａが含まれる。
【００６１】
図７の、メモリ・ページ内でのロック構造９３の配置に留意されたい。同一の読取プロセス−書込プロセス・ロックの一部であるが異なるＣＰＵグループの一部であるロック構造、たとえば構造０ａおよび構造１ａが、ローカル・メモリ２６の異なる行（すなわち、システムを単一の単位として移動するメモリのブロック）に保管される。これは、異なるグループのプロセッサが、同一のメモリ行について競争しないようにするために行われる。また、異なる読取プロセス−書込プロセス・ロックの一部であるが同一のＣＰＵグループの一部であるロック構造９３（すなわち、０ａ、０ｂなど）が、メモリの同一の行に保管される（インターリーブされて）ことに留意されたい。同一のＣＰＵがキャッシングされた行を共用するので、これによって、大きな性能コストなしにメモリ・リソースが節約される。
【００６２】
図７に示され、表１０に記されているように、特定のロック９０のグローバル構造９１は、ＣＰＵグループ０のロック構造９３をポイントする。特定のロック９０の他の構造９３には、アドレス演算を介して最初のロック構造から達することができる。
【００６３】
グループごとのＣＰＵの数（したがってロック構造ごとのＣＰＵの数）を変更することができる。上で注記したように、グループ・サイズは、当初は、システム１０内のＣＰＵの数から決定することができ、その後、その決定に従ってノードに割り振ることができる。しかし、この割振りは、動的とすることができ、混合されたものとすることができる、すなわち、一部のノードがグループごとにある個数のＣＰＵを有し、他のノードがグループごとに異なる個数のＣＰＵを有することができる。あるいは、グループごとのＣＰＵの数を均一とし、システム１０が変更された時またはグループごとの所望の数が変化した時に変更することができる。これを可能にするために、その要素が異なるロック構造の組９２をポイントする、もう１つのデータ構造（図７に示された配列９６など）を設けることができる。適当な要素ポインタが、所望のカウンタの組の配列から選択される。図７の例では、組９２が、グループごとに２つのＣＰＵまたは、ノードごとに４つのＣＰＵを有する４ノード・システムの８個のカウンタを有することができる。他のカウンタの組によって、グループごとに４つのＣＰＵ（合計４個のカウンタ）、グループごとに１つのＣＰＵ（合計１６個のカウンタ）などを提供することができる。
【００６４】
第２の実施形態のネスト可能な読取プロセス−書込プロセス・ロックの動作
各ロック９０に、特定の共用オブジェクトが関連する。共用オブジェクトへのアクセスを獲得する最初の試みの際に、グループ内のＣＰＵが、構造９３をローカル・メモリ２６からローカル・キャッシュ２５に読み込む。その後、カウンタ９４およびフラグ９５が、ＣＰＵのキャッシング方式に従って、グループ内のＣＰＵの間で更新される。図７の例では、ＣＰＵ０および１が、ＣＰＵグループ０に含まれ、ロック９０ａに関して構造０ａを共用する。ＣＰＵ０で稼動するプロセスが、ロック９０ａによって保護される共用オブジェクトの読取を求める場合に、そのプロセスは、メモリ２６から構造０ａを獲得し、構造０ａ内のカウンタ９４の値を増分する。ＣＰＵ１で稼動するプロセスが、そのオブジェクトの読取を望む場合に、このプロセスは、ＣＰＵ０のキャッシュから構造０ａのコピーを獲得し、カウンタをもう一度増分する。システム１０内のいずれかのＣＰＵで稼動するプロセスが、ロック９０ａによって保護される共用オブジェクトへの書込を望む場合に、そのプロセスは、ロック構造０ａから７ａのフラグ９５をセットする。しかし、複数のＣＰＵがフラグを共用するので、グループごとに複数のＣＰＵがある時には、セットしなければならないフラグの数が減る。競争状態を防ぐために、各ロック９０が、複数のＣＰＵが書込関連動作を実行しないようにするmutex（表１０を参照されたい）を有する。
【００６５】
詳細に言うと、オペレーティング・システム・カーネル５４が、１つまたは複数の適当なプリミティブ（下で詳細に説明する）を呼び出すことによって、共用オブジェクトへのアクセスのプロセス要求に応答する。それを行う際に、カーネルは、呼び出されるプリミティブにロックへのポインタを渡す。その後、選択されたプリミティブが、実行される。ロックが使用不能である場合には、要求するプロセスがブロックされる。
【００６６】
以下の表に、さまざまなプリミティブがロック９０の構造とどのように相互作用するかを擬似コードで示す。
【００６７】
p_commonプリミティブ
p_commonプリミティブは、ロック９０を書込獲得し、これによって、プロセスが、そのロックによって保護される共用オブジェクトに書き込めるようにするために、プリミティブp_writerによって呼び出される。このプリミティブは、ロック９０の各構造９３のフラグ９５をセットして、書き込むプロセスがロックを獲得したことを示す。しかし、ＣＰＵグループ・サイズが大きいほど、セットしなければならないフラグの数が減る。p_commonが書込プロセスのためにロックの獲得を試みる時に、読取プロセスが存在する場合には、書込プロセスが、スリープ状態にされ、その後、すべての読取プロセスが終了した後に覚醒される。
【００６８】
【表１１】
0003880398.tif 000012
【００６９】
p_writerプリミティブ
p_writerプリミティブは、まず、書込獲得を１つの書込プロセスに制限するグローバル相互排他ロック（mutex）を獲得することによって、書込プロセスのために、指定された読取プロセス−書込プロセス・ロックを獲得する。このプリミティブは、必要な場合に、p_commonを呼び出して、関連する構造９３のフラグ９５を変更する。これは、必ず必要とは限らない。ある書込プロセスが、別の書込プロセスに続く場合には、第１の書込プロセスがフラグをクリアせずに、第２の書込プロセスがロックを獲得することができる。これによって、第１の書き込むプロセスがロックを解放したことを示すためにフラグをクリアする必要がなくなり、その後に、第２の書き込むプロセスがロックを書込獲得したことを示すためにフラグをセットする必要がなくなる。第１の書込プロセスは、v_writerプリミティブ（下で説明する）を介して、第２の書込プロセスが待っていることを知り、構造９３のフラグをセットされたままにする。第２の書込プロセスは、書き込むプロセスが稼動するプロセッサのノードの構造９３のフラグ９５などのインジケータを検査することによって、フラグがセットされたままであることを知る。
【００７０】
【表１２】
0003880398.tif 000013
【００７１】
v_writerプリミティブ
v_writerプリミティブは、ロック９０内の各構造９３のフラグをクリアすることによって、ロックを書込解放するために呼び出される。しかし、このフラグのクリアは、必ず必要とは限らない。readers_writers_mutexを獲得する、キュー内の次のプロセスが書込プロセスであると判定される場合には、フラグはクリアされない。この判定は、writer_await_count（書込プロセスがキューに入れられているかどうかを示す）などのインジケータを検査することによって行われる。もちろん、単一のフィールドなどの他のインジケータを使用することができる。
【００７２】
【表１３】
0003880398.tif 000014
【００７３】
p_readerプリミティブ
p_readerプリミティブは、指定されたロックを読取獲得する。
【００７４】
【表１４】
0003880398.tif 000015
【００７５】
v_lwrwプリミティブ
v_lwrwプリミティブは、指定されたロックが読取獲得された場合にはそれを読取解放し、書込獲得された場合には書込解放する。
【００７６】
【表１５】
0003880398.tif 000016
【００７７】
第２の実施形態の産業上の利用可能性
上で説明した、読取プロセス−書込プロセス・ロックの第２のネスト可能な実施形態では、任意の所与のスレッドによって保持される複数の読取プロセス−書込プロセス・ロックが効率的に可能にされ、所与のスレッドが、無制限の数の読取プロセス−書込プロセス・ロックを保持することができる。
【００７８】
代替実施形態
例示的実施形態で本発明の原理を図示し、説明したが、例示的実施形態を、本発明の原理から逸脱せずに、配置および詳細において修正できることが、当業者には明白である。たとえば、本発明を、他のロッキング・システムで使用することができ、関連する同期化サービスの提供など、ロッキング以外の目的に使用することができる。注記したように、スレッド、タスク、軽量プロセス、およびジョブなど、多数の他の周知の機構を、通常のプロセスと置換することができ、用語「プロセス」が、そのような機構およびそれらの同等物を含むものとして解釈されなければならない。データ構造は、さまざまな形で実施することができる。たとえば、主インジケータとして働く他のロック構造、変数、またはレジスタを、カウンタが所望される場所で使用することができ、フラグを、副インジケータとして働く他の構造と置換するか、カウンタと共に複合構造に組み合わせることができる。説明したプリミティブの機能を、組み合わせるか再分配することができる。実施形態のソフトウェア態様の多くを、ハードウェアで実施することができ、ハードウェア態様の多くを、ソフトウェアで実施することができる。さまざまなプリミティブのステップを、同一の形で同一の結果を達成する、異なる順序で実行することができる。上で指摘したように、本発明は、ＮＵＭＡアーキテクチャを有するマルチプロセッサ・システムに制限されない。
【００７９】
本発明の原理を適用できる多数の可能な実施形態に鑑みて、この例示的実施形態が、これらの原理を教えることを意図されたものであり、本発明の範囲を制限することを意図されたものではないことを理解されたい。したがって、請求項およびその同党物の範囲および趣旨に含まれるすべてのものが、本発明として請求される。
【図面の簡単な説明】
【図１】  複数の相互接続されたプロセッサ・ノードを有するマルチプロセッサ・システムを示す図である。
【図２】  図１のマルチプロセッサ・システムのノードの１つを示す図である。
【図３】  ＣＰＵグループに編成された、図１のシステムのプロセッサを示す図である。
【図４】  図１のシステムのオペレーティング・システムの、複数のプロセッサとの相互作用を示す図である。
【図５】  本発明による第１実施形態の読取プロセス−書込プロセス・ロックの構造を示す図である。
【図６】  カウンタおよび関連するフラグを有する、第１実施形態のロック・データ構造を示す図である。
【図７】  本発明による第２実施形態の読取プロセス−書込プロセス・ロックの構造を示す図である。
【図８】  カウンタおよび関連するフラグを有する、第２実施形態のロック・データ構造を示す図である。
【図９】  ＣＰＵグループ番号が保管されるデータ構造を示す図である。
【図１】
0003880398.tif 000017
【図２】
0003880398.tif 000018
【図３】
0003880398.tif 000019
【図４】
0003880398.tif 000020
【図５】
0003880398.tif 000021
【図６】
0003880398.tif 000022
【図７】
0003880398.tif 000023
【図８】
0003880398.tif 000024
【図９】
0003880398.tif 000025