(57)【特許請求の範囲】
【請求項１】
マルチプロセッサ・コンピュータ・システム内で効率よく高コンテンションのソフトウェア・ロックを処理するための方法において、
全プロセッサの少なくとも一部を階層に編成するステップであって、前記階層が、複数プロセッサからなるどのグループがロックを待っているプロセッサを有するかを示す第１のビット・マスクと、１つのグループのうちのどのプロセッサがロックを待っているかを示す第２のビット・マスクとを有するデータ構造を含む、前記階層に編成するステップと、
ロックが使用不能である場合にロック認可の失敗を返すことを要求する第１のプロセッサに対し、
前記第１のビット・マスクが、ロックを待っているプロセッサを有するグループがいないことを示すことを条件に、前記第１のプロセッサが属するグループがロックを待っていることを示すように前記第１のビット・マスクを設定するステップと、
前記第１のプロセッサが属する前記グループの前記第２のビット・マスクが、ロックを待っているプロセッサがあることを示すことを条件に、ハンドオフ・フラグを設定して、ロック認可の失敗を返すステップとを含み、
ロックが使用可能になるまでロック上でスピンすることを要求する第２のプロセッサに対し、
前記第２のプロセッサがロックを待っていることを示すように、前記第２のプロセッサが属するグループの前記第２のビット・マスクを設定するステップと、
前記第２のビット・マスクが、前記第２のプロセッサが属する前記グループの他のプロセッサによるロック待ちがないことを示し、かつ、前記第１のビット・マスクが、前記第２のプロセッサが属する前記グループが、ロックを待っているプロセッサを有することを示す場合に、前記ハンドオフ・フラグが設定されていることを条件に、該フラグをクリアしてロックを認可するステップとを含む、
方法。
【請求項２】
前記第１のプロセッサに対し、前記第１のプロセッサが属する前記グループの前記第２のビット・マスクが、ロックを待っているプロセッサがないことを示すことを条件に、ロックを認可するステップを含む、請求項１に記載の方法。
【請求項３】
前記第２のプロセッサは、前記第２のプロセッサが属するグループの他のプロセッサによるロック待ちがあることを前記第２のビット・マスクが示す場合に、ロックが使用可能になるまでロック上でスピンする、請求項１に記載の方法。
【請求項４】
ロック上でスピンしながらシステム割込みを許可するステップをさらに具備する、請求項３に記載の方法。
【請求項５】
ロックの取得と解除との間の競争を防止するために、複数プロセッサからなるグループについて解除フラグを維持するステップをさらに具備する、請求項１ないし４のいずれかに記載の方法。
【請求項６】
コンピュータに請求項１ないし４のいずれかに記載のすべてのステップを実行させるためのコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチプロセッサにおいて高コンテンション・ロックを効率よく処理するための方法およびシステムに関する。より具体的には、システムの全プロセッサは階層状に編成され、１つのプロセッサへの割込み可能ロックの認可はその階層に基づいて行われる。
【背景技術】
【０００２】
マルチプロセッサ・システムは、定義上、複数のプロセスまたは単一プロセス内の複数のスレッドを並列計算として知られる方式で同時に実行可能な複数のプロセッサを含み、これらは本明細書ではＣＰＵとも呼ぶ。一般に、マルチプロセッサ・システムは、複数プログラムを順次実行可能な従来のユニプロセッサ・システムより高速で複数のプロセスまたはスレッドを実行する。パフォーマンス上の実際の利点は、１つのマルチスレッド・プロセスの各部分または複数の個別プロセスあるいはその両方を並列式に実行できる程度と、手元の特定のマルチプロセッサ・システムのアーキテクチャを含む、いくつかの要因の相関関係である。複数のプロセスを並列式に実行できる程度は、一つには、それらが共用メモリ・リソースへの排他アクセスについて競合する程度によって決まる。
【０００３】
共用メモリ・マルチプロセッサ・システムのアーキテクチャは、そのメモリが物理的にどのように編成されているかによって分類することができる。分散共用メモリ（ＤＳＭ）マシンでは、メモリは、通常は１つのプロセッサ・ノード上の１つまたは複数のプロセッサ付近に物理的に配置される複数のモジュールに分割される。すべてのメモリ・モジュールはグローバルにアクセス可能であるが、１つのプロセッサは、他のノード上のリモート・メモリよりそのノード上のローカル・メモリの方がより高速にアクセスすることができる。そのメモリ・アクセス時間は記憶場所に基づいて異なってくるので、このようなシステムは不均一メモリ・アクセス（ＮＵＭＡ）マシンとも呼ばれる。これに対して、集中共用メモリ・マシン内のメモリは物理的に１つの場所にある。そのメモリはそれぞれのプロセッサにとって時間的に等距離にあるので、集中共用メモリ・コンピュータは均一メモリ・アクセス（ＵＭＡ）マシンと呼ばれる。どちらの形態のメモリ編成も、通常、メイン・メモリとともに高速キャッシュを使用して実行時間を短縮する。
【０００４】
パフォーマンスを増進するためのＮＵＭＡアーキテクチャの使用は、ＮＵＭＡマシンに制限されるわけではない。１つのＵＭＡマシン内の複数プロセッサのサブセットは１つのキャッシュを共用することができる。このような配置では、そのメモリがすべてのプロセッサから等距離にある場合でも、データは、マシン内の他のプロセッサ間よりキャッシュ共用プロセッサ間の方がより高速に（すなわち、低待ち時間で）循環することができる。したがって、ＮＵＭＡマシンのパフォーマンスを強化するアルゴリズムは、低待ち時間の複数プロセッサのサブセットを有するマルチプロセッサ・システムに適用することができる。このようなものとしては、上記のＮＵＭＡおよび共用キャッシュ・マシンのみならず、複数のプロセッサが１組のバスインタフェース・ロジックを共用するマシンならびに全プロセッサに対して（通常は階層的に）「ファンアウト」する相互接続部を備えたマシンも含む。
【０００５】
マルチプロセッサ・システムを設計する際に重要な問題はプロセス同期である。複数のプロセスを並列式に実行できる程度は、一つには、それらが共用メモリ・リソースへの排他アクセスについて競合する程度によって決まる。たとえば、２つのプロセスＡおよびＢが並列式に実行されている場合、プロセスＢはプロセスＡがカウントを増分するまで待たなければ、プロセスＢがそれにアクセスすることはできない。そうではない場合、それを増分する可能性がプロセスＡに与えられる前にプロセスＢがそのカウンタにアクセスする可能性があるという競争状態が発生するだろう。衝突を回避するため、プロセス実行の順序を制御するためのプロセス同期メカニズムが設けられる。このようなメカニズムとしては、相互排除ロック、条件変数、カウント・セマフォ、リーダ／ライタ・ロックを含む。相互排除ロックでは、ロックを保持するプロセッサのみが関連アクションを実行することができる。あるプロセッサが相互排除ロックを要求すると、そのプロセッサに対して排他的に相互排除ロックが認可される。そのロックを希望する他のプロセッサは、ロックを備えたプロセッサがそれを解除するまで待たなければならない。
【０００６】
オペレーティング・システム・カーネルでは、直列化を実現するために効率のよいロック・プリミティブを必要とする。スピン・ロックと待ち行列ロックは２つの一般的な直列化メカニズムである。スケーラビリティと効率に加え、割込み可能性と公正性が所望の特性である。原子性要件のために、スレッドは、メモリを操作するクリティカル・セクションに入る前にその優先レベルを引き上げなければならない可能性がある。さらに、スレッドがロックを待っている間にそのスレッドへの割込みを可能にすると、割込みに対するシステムの応答性が増進する。
【０００７】
スピン・ロックは、クリティカル・セクションへのアクセスを制御するためにマルチプロセッサ・システム内のキャッシュ・コヒーレンス・メカニズムを使用する、単純な構成である。典型的なスピン・ロック・インプリメンテーションには２つのフェーズがある。スピン・フェーズでは、待機計算エージェント、たとえば、スレッドが単一グローバル・ロック変数のキャッシュ・コピー上でスピンする。競合フェーズでは、すべての待機計算エージェントは、ロック変数を使用可能状態から保持状態にアトミック的に変更しようと試みる。このフェーズに成功した１つの計算エージェントはそのロックの制御権を有し、他の計算エージェントはスピン・フェーズに戻る。スピン・フェーズから競合フェーズへの遷移は、ロック変数に使用可能のマークを付けることによりロック保持者がそのロックを解除したときに開始される。
【０００８】
スピン・ロックには、実現するために少数の命令のみを必要とすることと、割込み可能になるように容易に設計されるという２つの主な利点がある。スピン・ロックの主な欠点は、十分にスケーリングできないことである。競合フェーズでは、多数の計算エージェントが同時にロックを取得しようと試みたときに、システム・バス上で重大なコンテンションを引き起こす可能性がある。したがって、スピン・ロックは、軽度に競合するロックにのみ適当なものである。さらに、ロックは必ずしも先入れ先出し法（ＦＩＦＯ）の順序で認可されるわけではないので、スピン・ロックは通常、公正ではない。
【０００９】
したがって、クリティカル・セクション内で操作されるデータおよびロック・プリミティブについて高度のメモリ局所性を維持するために、複数のプロセッサを含むコンピュータ・システムと、ハイパフォーマンス並列プログラムを作成する方法が求められている。区分化により局所性が増進するが、再設計なしにクリティカル・セクションのデータ局所性を促進するロック・プリミティブが求められている。本明細書で提示する新規のロック・アルゴリズムは、重大なシステムレベル・パフォーマンス上の利点をもたらしながら、クリティカル・セクションのデータ局所性を促進する。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
したがって、本発明の一目的は、マルチプロセッサ・コンピュータ・システム内の１つのプロセッサにロックを認可する方法と割込み可能ロックを提供することにある。本発明の他の目的は、全プロセッサを階層状に編成し、階層内のその位置に基づいて後続プロセッサにロックを認可することにある。
【課題を解決するための手段】
【００１１】
本発明の第１の態様は、マルチプロセッサ・コンピュータ・システム内で効率よく高コンテンション・ロックを処理する方法である。ロックを取得または解除するために、条件付きでロックを取得するためのプリミティブと、無条件でロックを取得するためのプリミティブと、無条件でロックを解除するためのプリミティブが選択される。さらに、１グループのプロセッサについてロック取得とロックの解除との間の競争を防止するために解除フラグが実現され、条件付きロックを要求するプロセッサから無条件ロックを要求するプロセッサにロックを認可するためにハンドオフ・フラグが実現される。
【００１２】
本発明の第２の態様は、高コンテンション・ロック状況でのロック取得に対処するように設計されたマルチプロセッサ・コンピュータ・システムである。このシステムは、条件付きロック取得プリミティブと無条件ロック取得プリミティブとを含む、ロックを取得するためのプリミティブを含む。さらに、このシステムは、無条件ロック解除のためのプリミティブを含む。このシステムは好ましくは、ロック取得とロック解除との間の競争を防止するための解除フラグと、条件付きロックを要求するプロセッサから無条件ロックを要求するプロセッサにロックを認可するためのハンドオフ・フラグを含む。
【００１３】
本発明の第３の態様は、コンピュータ可読信号運搬媒体を含み、複数のプロセッサがその媒体内で動作する製品である。この製品は、ロックを処理するためのプリミティブを含み、そのプリミティブは、全プロセッサの少なくとも一部からなる階層編成に応答する。このプリミティブは、条件付きロック取得と、無条件ロック取得と、無条件ロック解除とを含む。さらに、ロック取得とロック解除との間の競争を防止するための解除フラグと、条件付きロックを要求するプロセッサから無条件ロックを要求するプロセッサにロックを認可するためのハンドオフ・フラグとを提供する。
【００１４】
本発明のその他の特徴および利点は、添付図面に関連して考慮すると、本発明の現在好ましい実施形態に関する以下の詳細な説明から明らかになるだろう。
【発明を実施するための最良の形態】
【００１５】
概要
本発明のカーネル・ラウンドロビン・ロック・プリミティブ（ｋｒｌｏｃｋ）は、ノード単位にグループ化された多数のＣＰＵを処理するように設計された直線的なスピンロックであり、そのノードは好ましくは最高４つのプロセッサを有するクワッドである。ｋｒｌｏｃｋは、ローカル・メモリとリモート・メモリとの間に様々な比率の待ち時間を備えたアーキテクチャ上の高コンテンション・ロック状況を効率よく処理するためのものである。低待ち時間比率で効率よく動作するには、ロック・プリミティブによってローカル・バスならびにリモート・メモリの動作を最小限にする必要がある。
【００１６】
メモリ待ち時間は、適切に構築された並列プログラムにおいて重要な要因になりうる。パフォーマンスは、ＣＰＵ、キャッシュ、メモリ間のデータ・フローを追跡することによって推定することができる。ＳＭＰ（対称マルチプロセッサ）およびＣＣ−ＮＵＭＡ（キャッシュ・コヒーレント不均一メモリ・アクセス）アーキテクチャの場合、このデータ・フローはキャッシュ・コヒーレント・プロトコルによって制御され、このプロトコルは複数キャッシュ・ライン単位でデータを移動する。
【００１７】
図１２に示すように、ｃｃ−ＮＵＭＡシステム９００は、ＣＰＵ９１２、９２２とメモリ９１４、９２４の両方を含む、クワッド・モジュール９１０、９２０から構成される。所与のＣＰＵにより近い位置に存在するデータは、アクセス待ち時間がより短くなる。すでに所与のＣＰＵのキャッシュ内にあるデータは、待ち時間ｔf９１６でアクセスすることができる。同じクワッド上の他の場所に位置するデータは待ち時間ｔm９１８でアクセスすることができ、他のクワッド上に位置するデータは待ち時間ｔs９２６でアクセスすることができる。所与のデータ項目がＣＰＵによってアクセスされると、そのデータ項目はそのＣＰＵのキャッシュ内にキャッシュされる。データのホームが他のクワッドのメモリ内である場合、そのデータはアクセス中のＣＰＵのクワッドのキャッシュ内にもキャッシュされることになる。このキャッシングにより、同じＣＰＵからの後続アクセスはより低い待ち時間で続行することができる。所与のＣＰＵによって以前アクセスされたことがあるデータは、そのＣＰＵのキャッシュ内に存在するものと想定され、アクセス待ち時間はｔf９１６になる。したがって、アクセス中のデータおよびリソースの待ち時間は、アクセス中のＣＰＵに対するリソースの位置に依存する。
【００１８】
カーネル・ラウンドロビン・ロック・プリミティブは、重度のコンテンション下で、すなわち、他のＣＰＵがロックを解除したときに必ず少なくとも１つのＣＰＵがそのロックを待っている場合に、ＣＣ−ＮＵＭＡマシン上で公正かつ効率よく動作するように設計されている。このプリミティブは、いずれかのクワッドが長期間の間、ロックを独占するのを防止しながら、適切な時期にイントラクワッド・ベースでロックを渡すように設計されている。特定のクワッドによるロックの独占は、システム上の他のクワッドに対する「枯渇」を引き起こす可能性があり、すなわち、他のクワッドがそのロックにアクセスするのを妨げる可能性がある。このため、カーネル・ラウンドロビン・ロック・プリミティブは、公正かつ公平にインタークワッド・ベースでロックを渡すように設計されている。１つのクワッドが１つのロック上でスピンする複数のＣＰＵを有する場合、そのクワッドは、待機クワッドにロック取得が認可される前に３つ以上の連続ロック取得エピソードを取得することができない。これは、クワッド間のロック取得に対するある程度の公正性を考慮したものである。そのうえ、１つのロックのインタークワッド・ハンドオフは、重負荷時に動作するときに最小数のリモートメモリ・トランザクションで実施しなければならない。効率を引き上げるためには、複数のＣＰＵがロックを待っていて、そのクワッドに関する連続ロックの最大数を超えていない場合に、現行ロック保持者と同じクワッド上のＣＰＵに対してロックをハンドオフしなければならない。同じクワッド上の他のＣＰＵにロックをハンドオフすると、このようなハンドオフに関する物理的な時間差は他のクワッド内のＣＰＵに対するものより小さくなるので、効率が維持される。また、イントラクワッド・ハンドオフは、クリティカル・セクションのデータ局所性も増進する。最後に、効率を維持するためには、低ローカル・バス・コンテンションと少数の命令によってロック・ハンドオフを実施しなければならない。これにより、低メモリ待ち時間比率で効率のよい動作が可能になる。したがって、上記で概略を述べたルールは、オペレーティング・システムのカーネル内でのロックの効率的使用法に備えるものである。
【００１９】
ｋｒｌｏｃｋの主な特徴の１つは、システム割込みに対処していることである。ＣＰＵがシステム割込みを経験した場合、そのＣＰＵはロックを取得することができない。ロックを取得するためのメソッドが２通りある。第１のメソッドは、割込みを排除するために同時にシステム優先レベル（「ＳＰＬ」）を引き上げながら、条件付きでロックを取得すること（ｃｐ＿ｋｒｌｏｃｋ）である。このメソッドでは、ロックが直ちに使用可能ではない場合に、ロック取得の失敗を返す。第２のメソッドは、同時にＳＰＬを引き上げながら、無条件でロックを取得すること（ｐ＿ｋｒｌｏｃｋ）である。無条件ロック取得では、ロックが使用可能になるまで、ＣＰＵがロック上でスピンすることができる。別法として、ＳＰＬを個別に管理するかまたはＳＰＬをまったく引き上げないことも可能である。割込みは、ロック上でスピンしている間に許可しなければならない。さらに、これらのロック取得メソッドは、その割込みにおいてスピンが行われている同じロックに至るまで割込みハンドラからのロック取得を適切に処理しなければならない。あるロックについてスピンし、それを待っている複数のＣＰＵは、そのロックがそのＣＰＵにとって使用可能になるまで、リモート・アクセスなしにそれぞれのキャッシュ内で完全にスピンできなければならない。ＣＰＵのスピンによってローカル・バス上にトラフィックが発生することはない。これらのロック取得メソッドに加え、このプリミティブは、同時にＳＰＬを引き下げながら、あるＣＰＵでのロックを無条件で解除するメソッド（ｖ＿ｋｒｌｏｃｋ）も含む。
【００２０】
データ構造
カーネル・ラウンドロビン・ロック・プリミティブは、４タイプのデータ構造を含む。図１は、これらのデータ構造のうちの第１のデータ構造であって、クワッドあたり１ビットずつを有する単一ビットマスク（ｋｒ＿ｓｐｉｎ）１０２を含むグローバル・ビットマスク（ｋｒｌｏｃｋ＿ｔ）１００を示しており、各クワッド単位ビットは、そのクワッド上の少なくとも１つのＣＰＵがロックを要求しているかまたはロックを保持しているかを示す。グローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）１０２内に第１のビットを設定するＣＰＵは、そのロックを所有しており、そのロックを要求するＣＰＵが存在する場合に、解除時にそのＣＰＵに対してロックを処理する責任がある。
【００２１】
第２のデータ構造は、スピン状態（ｋｒｑ＿ｓｐｉｎ）２０２と、オンクワッド認可の最大連続数（ｋｒｑ＿ｇｒａｎｔ＿ｍａｘ）２０４と、ロック・プロファイルに使用する統計データ構造を指す任意選択のポインタ（ｋｒｑ＿ｓｔａｔｓ）２０６とを含む、クワッド単位ビットマスク（ｋｒｌｏｃｋ＿ｐｑ＿ｔ）２００である。連続オンクワッド認可の最大数のビットフィールドが許可された連続ロックの最大数を超え、しかも他のクワッド上の他のＣＰＵがそのロックを要求している場合、そのロックは他のクワッドにハンドオフされる。他のいずれかのクワッド上のＣＰＵに対してそのロックをハンドオフしようという試みが行われると、このカウンタはリセットされる。したがって、グローバル・ビットマスク（ｋｒｌｏｃｋ＿ｔ）１００は、ロックを待っているかまたはロックを保持しているプロセッサをどのクワッドが持っているかを示すように機能し、クワッド・ビットマスク（ｋｒｌｏｃｋ＿ｐｑ＿ｔ）２００は、あるクワッド内のどのプロセッサがそのロックを待っているかを示すように機能する。
【００２２】
図３は、要求フィールド３０２と、保持フィールド３０４と、認可フィールド３０６と、解除フィールド３０８と、ハンドオフ・フィールド３１０とを含む複数のフィールドに分割されたクワッド単位状態のマスクとしてクワッド単位データ構造のスピン状態フィールド（ｋｒｑ＿ｓｐｉｎ）２０２を示している。要求フィールド（ｋｒｑ＿ｃｐｕ＿ｒｑｓｔ）３０２は、そのクワッド上の各ＣＰＵごとに１つのビットを含み、そのＣＰＵがロックを要求しているかどうかを示す。保持フィールド（ｋｒｑ＿ｃｐｕ＿ｈｏｌｄ）３０４は、どのＣＰＵが現在そのロックを保持しているかを示すインデックスを含む。認可フィールド（ｋｒｑ＿ｇｒａｎｔ）３０６は、同じクワッド内のＣＰＵに対して提供されたロックの連続認可の数を示すカウントを含む。これらのフィールドはいずれもアトミック的に操作しなければならない。グローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）１０２およびクワッド単位データ構造（ｋｒｌｏｃｋ＿ｐｑ＿ｔ）２００に加え、カーネル・ラウンドロビン・ロック・プリミティブは任意選択で、対応するＣＰＵがスピンしているグローバル・ビットマスク・データ構造を記録するためのＣＰＵ単位テーブルと、クワッド単位統計データ構造とを含むことができる。ＣＰＵ単位テーブルは、可能な割込みネスティング・レベルあたり１つの項目を収容するように設計され、そのロックを使用可能な他のＣＰＵが存在するときに割込みスピンへのロックのハンドオフを回避するために使用する。したがって、クワッド単位データ構造は、クワッド・ベースでロックの使用法を制御し、長期間の間、１つのロックがいずれか１つのクワッドによって独占されないことを保証するように設計されている。
【００２３】
クワッド単位データ構造のスピン状態フィールド（ｋｒｑ＿ｓｐｉｎ）２０２は、プロセッサ間で効果的にロックを転送するための解除フィールド３０８とハンドオフ・フィールド３１０とを含む。解除フィールド３０８は、ロック取得とロック解除の間で発生する可能性のあるロック取得の競争を防止するためのフラグである。このフラグは、完全ロック解除が進行中であることを識別する。ハンドオフ・フィールド３１０は、無条件ロック取得メソッドによりロックを要求するプロセッサへのロックの認可を示し、最終的な解除によって後続の取得との競争が発生するときにロックの認可を示すためのフラグである。このフラグは、条件付きロックを要求したプロセッサが失敗し、無条件ロックを要求しているプロセッサにそのロックが転送されたことを示す。したがって、解除フラグ３０８とハンドオフ・フラグ３１０はどちらも、ロック取得に関して発生しうるプロセッサ間の連絡不良を防止するように機能する。
【００２４】
インターレースにより、キャッシュ・アライメント要件を満たしながら、ｋｒｌｏｃｋ＿ｐｑ＿ｔタイプのクワッド単位ビットマスクの小型セットへの高速アクセスが可能になる。図４に示すように、これらの構造は、クワッドあたり１ページずつから構成され、ｋｒｌｏｃｋ＿ｔ構造用の追加ページが先行する「クラスタ・セット」４００単位にグループ化される。各クラスタ・セット４００は、以下のようにメモリ内にレイアウトされる。
【００２５】
ｋｒｌｏｃｋ＿ｃｌｕｓｔｅｒｓ構造４０１は、インターレース・ビットマスクのフリーリストを処理する。全ページのビットマスクは、連続仮想メモリ内にレイアウトされる。ｋｒｌｏｃｋ＿ｔページ４０２の第１のリモート（６４バイトまたはＲＭＴ＿ＣＡＣＨＥＳＩＺＥ）キャッシュ・ラインはｋｒｌｏｃｋ＿ｃｈｄｒ＿ｔ４０４によって占有される。各クワッド単位ページの最初の６４バイトは未使用である。各クワッド単位ページのその次のいくつかのローカル（３２バイト）キャッシュ・ライン４０６は、ＣＰＵによるローカル・スピンに使用され、そのクワッド上の各ＣＰＵごとに１つのキャッシュ・ラインが予約されている。これに対応するｋｒｌｏｃｋ＿ｔページのセクションは未使用である。
【００２６】
残りのキャッシュ・ラインのそれぞれは、８組のインターレース・カウンタ・セットからなる所与のＣＰＵグループの一部用のビットマスクに分割される。したがって、「Ｘａ」はロック「ａ」のｋｒｌｏｃｋ＿ｔであり、「０ａ」、「１ａ」、「２ａ」はロック「ａ」のｋｒｌｏｃｋ＿ｑｐ＿ｔビットマスクである。同様に、「Ｘｂ」、「０ｂ」、「１ｂ」、「２ｂ」はロック「ｂ」を構成するビットマスクである。
【００２７】
インターレース・カウンタのクラスタ・セットのｋｒｌｏｃｋ＿ｔビットマスクを貫くフリーリスト５００が存在する。少なくとも１組のインターレース・ビットマスクのフリーセットを有するクラスタ・セット４００は、ｋｒｌｏｃｋ＿ｃｌｕｓｔｅｒｓ構造４０１のｋｒｃ＿ｆｒｅｅフィールド５０２が先頭に付く二重リンクの循環リスト上にある。インターレース・カウンタのフリーセットを有するかどうかにかかわらず、すべてのクラスタ・セット４００は、ｋｒｌｏｃｋ＿ｃｌｕｓｔｅｒｓアレイの対応要素のｋｒｃ＿ａｌｌフィールド５０４が先頭に付く二重リンクの循環リスト上にある。
【００２８】
このフリーリストの構造により、コードはｋｒｌｏｃｋ＿ｔ１００を指すポインタから始まり、リモートである可能性のあるメモリに触れる必要なしに、現行クワッドのｋｒｌｏｃｋ＿ｐｑ＿ｔ２００にインデックスを付けることができる。これにより、リモート・キャッシュがスラッシングされる場合にも妥当なパフォーマンスが保持される。
【００２９】
ｋｒｌｏｃｋ＿ｃｈｄｒ＿ｔの各フィールドは以下の通りである。ｋｒｃ＿ｆｒｅｅ５０２は、インターレース・カウンタの少なくとも１つのフリーセットを有する所与のシフト値のｋｒｌｏｃｋクラスタ・ヘッダのリストである。ｋｒｃ＿ａｌｌ５０４は、所与のシフト値のすべてのｋｒｌｏｃｋクラスタ・ヘッダのリストである。ｋｒｃ＿ｆｒｅｅ＿ｌｉｓｔ５０６は、所与のクラスタ内のインターレース・ビットマスクのフリーセットのリストであり、ｋｒｌｏｃｋ＿ｔ１００を指すポインタである。フリーリスト５００上のインターレース・カウンタ・セットの各ｋｒｌｏｃｋ＿ｔ１００は、フリーリスト上の次のインターレース・ビットマスク・セットのｋｒｌｏｃｋ＿ｔ１００を指すポインタを含む。フリーリスト上の最後のインターレース・ビットマスク・セットのｋｒｌｏｃｋ＿ｔ１００はＮＵＬＬポインタを含む。このフィールドは、ｋｒｌｏｃｋ＿ｃｌｕｓｔｅｒｓ構造４０１にとって何も意味がないものである。ｋｒｃ＿ｎｔｏｔａｌ５０８は、フリーであるかそうではないかにかかわらず、所与のクラスタ内のインターレース・ビットマスクのセットの総数である。このフィールドもｋｒｌｏｃｋ＿ｃｌｕｓｔｅｒｓ構造４０１にとって何も意味がないものである。ｋｒｃ＿ｎｆｒｅｅ５１０は、所与のクラスタ内のインターレース・ビットマスクのフリーセットの数である。この場合も、このフィールドはｋｒｌｏｃｋ＿ｃｌｕｓｔｅｒｓ構造４０１にとって何も意味がないものである。
【００３０】
ロック機能
カーネル・ラウンドロビン・ロック・プリミティブ内でロックを取得するためのモードが２通りあり、それらは、無条件でロックを取得するためのメソッド（ｐ＿ｋｒｌｏｃｋ）と、条件付きでロックを取得するためのメソッド（ｃｐ＿ｋｒｌｏｃｋ）とを含む。さらに、ロックを解除するためのモード（ｖ＿ｋｒｌｏｃｋ）が１つある。無条件ロック取得モード（ｐ＿ｋｒｌｏｃｋ）はこのプリミティブ内の正常動作モードであり、その際、ＣＰＵはロックを取得することになるかまたはロックを取得するまで必要な限りロック上でスピンすることになる。条件付きロック取得モード（ｃｐ＿ｋｒｌｏｃｋ）は、指定の条件下でロックを取得するモードである。これらの動作モードのそれぞれについては、以下に説明し、添付図面に例示する。
【００３１】
図７および図８は、カーネル・ラウンドロビン・ロック・プリミティブの無条件ロック取得モード（ｐ＿ｋｒｌｏｃｋ）のフロー図６００を示している。このモードは、ＣＰＵが無条件でロックを取得するかまたはロック上でスピンするかあるいはその両方の場合に備えるものである。フロー図６００は、動作全体の一般的な制御の流れを示している。初期状態６１４に続いて、呼出し側ＣＰＵがロックを要求し、システム優先レベルを引き上げ、すなわち、所与の割込みが受諾されるのを防止するために１つのビットを設定する。この優先レベルでは、所与のレベル以下のシステム割込みを許可する。次に、６２２でこのロックに関するＣＰＵ要求ビットをスピン状態（ｋｒｑ＿ｓｐｉｎ）に設定し、このクワッド内のこのＣＰＵがロックを要求していることを示す。ステップ６２２に続いて、６２６でスピン状態フィールド内の解除フラグをクリアしなければならない。この解除フラグは、ロック解除とロック取得との間の競争を防止するように機能する。次に、６３０でスピン状態フィールドの値とｃｐｕｓｐｉｎフィールドの値をアトミック的に交換する。各ＣＰＵは、そのＣＰＵがスピンしているＣＰＵのクワッド上の専用位置を指すｃｐｕｓｐｉｎフィールド４０６を有する。このため、ＣＰＵは、そのロックについてスピンしている時期を示さなければならない。ロックを指すように、このＣＰＵの現行割込みネスティング・レベルに対応するＣＰＵ単位テーブル内の項目である１．ｐｌ＿ｋｒｌｏｃｋを６３４で設定する。このステップはそのＣＰＵに関する割込みネスティング・レベルを示す。ＣＰＵはそのロック上でスピンしている、すなわち、そのロックを待っているので、そのＣＰＵへのシステム割込みを許可しても安全である。このため、６３８でＳＰＬと割込みを復元する。したがって、ロックは直ちに使用可能になっておらず、ＣＰＵは、過剰割込み待ち時間を防止するために所与のレベルのシステム割込みを許可しながら、６４２でそのロック上でスピンするように配置されている。
【００３２】
６４２のスピン期間中に、ＣＰＵは、そのロック上でスピンし続ける場合もあれば、スピンが中断される場合もあれば、ロックを受け取る場合もある。ＣＰＵがロックを受け取った場合、そのロックに関するＣＰＵ要求ビットをクリアし、すなわち、ｃｐｕｓｐｉｎフィールドがＮＵＬＬになり、６４６でＳＰＬを引き上げ、システム割込みを抑制する。ＳＰＬの引上げとシステム割込みの抑制により、ＣＰＵはロックを保持することができる。次に、６５０でスピン状態のＣＰＵテーブルである１．ｐｌ＿ｋｒｌｏｃｋをＮＵＬＬに設定し、そのＣＰＵがロック上でスピンしていないことを示す。スピン状態マスク内のＣＰＵテーブルの変更に続いて、６５４でｃｐｕｓｐｉｎフィールドがＮＵＬＬであるかどうかを判定しなければならない。ｃｐｕｓｐｉｎフィールドがＮＵＬＬではない場合、６５８でシステム割込みを復元し、６６２でロック取得プロセスが完了する。しかし、６５４でｃｐｕｓｐｉｎフィールドがＮＵＬＬである場合、これは、そのＣＰＵがシステム割込みの影響を受け、ロックをあきらめなければならなかったことを示している。アルゴリズムは６３４に戻り、ロック取得を復元するためにスピン状態マスク内のＣＰＵテーブルをリセットする。
【００３３】
６４２のスピン中に、ＣＰＵが６９８でシステム割込みを受ける場合、アトミック動作は値ＮＵＬＬを取り、６１０２でそれをｃｐｕｓｐｉｎフィールド内の値と交換する。しかし、ｃｐｕｓｐｉｎフィールドがＮＵＬＬである（ＣＰＵにロックを手渡したが、システム割込みのためにＣＰＵがそれを使用することができないことを示している）場合、６１０６で無条件ロック解除手順（ｖ＿ｋｒｌｏｃｋ）を使用してロックを解除する。次に、ＣＰＵは６１１０で割込みハンドラを呼び出すことができる。６６６でシステム割込みハンドラから出ると、ＣＰＵは６２２に戻り、ロック要求ビットを設定することができる。しかし、６１０２でｃｐｕｓｐｉｎフィールドが非ＮＵＬＬであると判定した場合、６１１４でＣＰＵロック要求ビットをクリアし、ＣＰＵによるロック上でのスピンを停止する。さらに、６１１８でクワッド要求ビットもクリアしなければならない場合もある。次に、６１１０でＣＰＵに対して割込みハンドラによる割込みを行う。６６６でシステム割込みハンドラから出ると、ＣＰＵは６２２に戻り、ロック要求ビットを設定することができる。
【００３４】
６２６では、６２２に入るときにｋｒ＿ｓｐｉｎフィールドがゼロであった場合、グローバル・ビットマスク内のＣＰＵによるクワッド・ロック要求ビットが設定されているかどうかを６７０で判定しなければならない。クワッド・ビットが設定されていない場合、ＣＰＵは６８２でグローバル・ビットマスクにクワッド・ビットを設定し、６３０に戻らなければならない。しかし、グローバル・ビットマスク内のクワッド・ビットが設定されている場合、クワッド単位データ構造（ｋｒｑ＿ｓｐｉｎ）内のスピン状態ビットのハンドオフ・フラグが設定されているかどうかを６７４で判定しなければならない。６７４でハンドオフ・フラグが設定されている場合、６７８でハンドオフ・フラグをクリアしなければならず、６８６でクワッド単位データ構造（ｋｒｑ＿ｓｐｉｎ）内のスピン状態からロック要求をクリアする。ハンドオフ・フラグが設定されていないと６７４で判定した場合、手順は６７０に戻り、クワッド・ビットがグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）に設定されているかどうかを確認する。
【００３５】
無条件でロックを取得するメソッド（ｐ＿ｋｒｌｏｃｋ）の擬似コードは以下の通りである。
１．ＳＰＬを「ｓ」まで引き上げ、古いＳＰＬをローカル変数「ｏｌｄｓｐｌ」に保管する。
２．割込みを抑制する。
３．ｐ＿ｋｒｌｏｃｋ＿ｎｏｃｏｎｔｅｎｄを呼び出す。（この関数は、コンテンションがまったくない場合に指定のロックを取得する。コンテンションがまったくない場合、ＴＲＵＥを返す。コンテンションがある場合、ＣＰＵとクワッドの要求ビットのうち該当する方を設定し、ＦＡＬＳＥを返す。）これがＴＲＵＥを返す場合、ロックを持っており、以下のステップを実行する。
ａ）割込みを復元する。
ｂ）「ｏｌｄｓｐｌ」を返す。以下のステップを実行しない。
４．そうではない場合、ロックを待ってスピンし、このＣＰＵのスピン・エリアを指すようにｃｐｕｓｐｉｎを設定しなければならない。
５．以下のステップを無期限に繰り返す。
ａ）クワッド単位構造（「ｋｑｐ」）を指すポインタの値を「ｃｐｕｓｐｉｎ」が指す値とアトミック的に交換し、その結果を廃棄する。
ｂ）割込み入口および出口関数に対して、ロック上でスピンしていることを示すために、ＣＰＵ単位テーブルの１．ｐｌ＿ｋｒｌｏｃｋオーダを設定する。
ｃ）割込みを復元する。
ｄ）ＳＰＬを「ｏｌｄｓｐｌ」に復元する。
ｅ）「ｃｐｕｓｐｉｎ」がＮＵＬＬを指すまでスピンする。
ｆ）ＳＰＬを「ｓ」まで引き上げる。
ｇ）割込みを抑制する。
ｈ）ＣＰＵ単位テーブルの１．ｐｌ＿ｋｒｌｏｃｋｐをＮＵＬＬに設定する。
ｉ）「ｃｐｕｓｐｉｎ」が依然としてＮＵＬＬ値を指している場合、割込みが行われていない。以下を実行する。
ｉ）割込みを復元する。
ｉｉ）「ｏｌｄｓｐｌ」を返す。繰返しを停止する。
【００３６】
コンテンションがまったくない場合、ｐ＿ｋｒｌｏｃｋ関数はロックを取得するための関数（ｐ＿ｋｒｌｏｃｋ＿ｎｏｃｏｎｔｅｎｄ）を呼び出す。「ｋｐ」は
ｋｒｌｏｃｋ＿ｔ１００を指すポインタである。ｐ＿ｋｒｌｏｃｋ＿ｎｏｃｏｎｔｅｎｄの擬似コードは以下の通りである。
１）このＣＰＵのビットが設定され、他のすべてがクリアであるマスクのｋｑｐ−＞ｋｑｐ＿ｓｐｉｎへのアトミック加算により「ｏｌｄｓｐｉｎ」を古い値に設定する。
２）ＫＲＱ＿ＲＥＬＥＡＳＥビットがｋｑｐ−＞ｋｑｐ＿ｓｐｉｎからクリアされるまでループする。（通常、このビットはすでにクリアされているので、このループは実行されない。）
３）「ｏｌｄｓｐｉｎ」のＣＰＵ要求ビットまたは保持ビットのいずれかが設定されている場合、コンテンションが存在する。ＦＡＬＳＥを返し、以下のステップを実行しない。
４）そうではない場合、「ｏｌｄｓｐｉｎ」をｋｐ−＞ｋｒ＿ｓｐｉｎの現行値に設定する。他のＣＰＵによるこのキャッシュ・ラインのコピーを無効にすることが望ましい可能性がある。
５）以下のステップを無期限に繰り返す。通常、このループを１回だけ通過することになる。しかし、他のＣＰＵとの競争が比較交換失敗を引き起こす可能性があり、それがループを通る追加トリップを強要する可能性がある。
ａ）このクワッドのビットが「ｏｌｄｓｐｉｎ」に設定されていない場合、以下のステップを実行して、このクワッドのビットの設定を試みる。
ｉ）ｋｐ−＞ｋｒ＿ｓｐｉｎと「ｏｌｄｓｐｉｎ」とをアトミック的に比較交換し、成功時にｏｌｄｓｐｉｎ｜ｑｕａｄｍａｓｋを代入するが、その場合、「ｑｕａｄｍａｓｋ」はこのクワッドのビットが設定され、他のすべてがクリアであるマスクである。これが成功した場合、以下を実行する。
（１）「ｏｌｄｓｐｉｎ」がゼロに等しくない場合、コンテンションが存在する。ＦＡＬＳＥを返し、以下のステップを実行しない。
（２）ＫＲＱ＿ＧＲＡＮＴ＿ＩＮＣ＋ＫＲＱ＿ＭＥ２ＨＯＬＤＭＡＳＫ（）−ｃｐｕｍａｓｋをｋｑｐ−＞ｋｒｑ＿ｓｐｉｎにアトミック的に加算する。この演算は、現行ＣＰＵにロック保持のマークを付け、ロックの認可をカウントするものである。ＫＲＱ＿ＧＲＡＮＴ＿ＩＮＣは、ｋｒｑ＿ｓｐｉｎ２０２のＫＲＱ＿ＧＲＡＮＴ＿ＭＡＳＫフィールドに１を加える値である。ＫＲＱ＿ＭＥ２ＨＯＬＤＭＡＳＫは、ＣＰＵがロックを保持していることを示す値を生成するマクロである。
（３）ＴＲＵＥを返し、以下のステップを実行しない。
ｂ）そうではない場合、このクワッドのビットはすでに「ｏｌｄｓｐｉｎ」に設定されている。これは、ｃｐ＿ｋｒｌｏｃｋ（）の失敗またはｖ＿ｋｒｌｏｃｋ（）の競争または割込みエントリによる可能性がある。いずれの場合も、以下のステップを実行する。
ｉ）「ｏｌｄｓｐｉｎｑ」をｋｑｐ−＞ｋｒｑ＿ｓｐｉｎに設定する。この場合も、他のＣＰＵのキャッシュを無効にすることが望ましい可能性がある。
ｉｉ）「ｏｌｄｓｐｉｎｑ」にＫＲＱ＿ＣＰ＿ＨＡＮＤＯＦＦビットが設定されている場合、失敗したｃｐ＿ｋｒｌｏｃｋ（）との競争が発生し、それによりロックが与えられている。以下のようにロックを請求する。
（１）数量（ＫＲＱ＿ＧＲＡＮＴ＿ＩＮＣ＋ＫＲＱ＿ＭＥ２ＨＯＬＤＭＡＳＫ（）−ｃｐｕｍａｓｋ−ＫＲＱ＿ＣＰ＿ＨＡＮＤＯＦＦ）をｋｑｐ−＞ｋｒｑ＿ｓｐｉｎにアトミック的に加算する。これは、このＣＰＵの保持値をアトミック的に設定し、その要求ビットをクリアし、ＫＲＱ＿ＣＰ＿ＨＡＮＤＯＦＦビットをクリアし、ロックの認可をカウントするものである。
（２）ＴＲＵＥを返し、ロックを保持していることを示す。以下のステップを実行しない。
ｉｉｉ）そうではない場合、スピンして、このクワッドのビットがｋｐ−＞ｋｒ＿ｓｐｉｎからクリアされるのを待つかまたはＫＲＱ＿ＣＰ＿ＨＡＮＤＯＦＦビットがｋｑｐ−＞ｋｒｑ＿ｓｐｉｎからクリアされるのを待つ。ｋｐ−＞ｋｒ＿ｓｐｉｎの値をサンプリングするときは、その値を「ｏｌｄｓｐｉｎ」に保管する。
６）前のステップは無限ループなので、このステップには達しない。
【００３７】
前述の通り、ロックを取得するための無条件ロック取得（ｐ＿ｋｒｌｏｃｋ）手順に加え、条件付きでロックを取得するための手順（ｃｐ＿ｋｒｌｏｃｋ）もある。図１１は、条件付き取得を通る一般的な制御の流れを示すフロー図８００である。初期状態８０４に続いて、呼出し側ＣＰＵがロックを要求し、８０８でシステム優先レベルを引き上げ、システム割込みを抑制する。次に、ロックに関するクワッド要求ビットのいずれかがグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）フィールドに設定されているかどうかを８１２で判定しなければならない。クワッド要求ビットがすでに設定されている場合、要求側ＣＰＵはロックを取得しないことになる。８１６でＳＰＬとシステム割込みの両方を復元し、８２０でＣＰＬＯＣＫＦＡＩＬを返し、要求側ＣＰＵが条件付きでロックを取得できないことを示す。しかし、いずれのクワッド要求ビットもグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）フィールドに設定されていないと８１２で判定した場合、８２４でそのクワッドの要求ビットをアトミック的に設定する。次にＣＰＵがスピンし、８２８でロックを保持しているＣＰＵ内のクワッド単位データ構造（ｋｒｑ＿ｓｐｉｎ）の解除フラグがクリア状態になるのを待つ。８３２でスピン状態（ｋｒｑ＿ｓｐｉｎ）に設定されたＣＰＵ要求ビットをチェックして、他のＣＰＵがそのロックを要求しているかどうかを判定しなければならない。他のどのＣＰＵもロックを要求していない場合、８３６で保持フィールドをアトミック的に設定し、８４４でシステム割込みを復元し、８４８でＣＰＵはロックの取得に成功したという表示を返す。しかし、他のＣＰＵがすでにロックを要求していると８３２で判定した場合、８４０でクワッド単位データ構造（ｋｒｑ＿ｓｐｉｎ）のスピン状態内のハンドオフ・フラグを設定し、８１６でＳＰＬとシステム割込みレベルを復元し、８２０でＣＰＵはロックの条件付き取得が失敗したことを示す。
【００３８】
条件付きロック取得メソッドｃｐ＿ｋｒｌｏｃｋ８００は、指定のロックを直ちに取得できる場合にそのロックを取得する。そうではない場合、そのメソッドはロックの取得もＳＰＬの引き上げも行わないが、むしろ、ＣＰＬＯＣＫＦＡＩＬを返して、呼出し側ＣＰＵに失敗を示す。カーネル・ラウンドロビン・ロック・プリミティブは高コンテンション用に設計されているので、条件付きロック取得プリミティブｃｐ＿ｋｒｌｏｃｋ８００はほとんどいつも失敗することになる。
【００３９】
擬似コードは以下の通りである。
１）ＳＰＬを「ｓ」まで引き上げ、古いＳＰＬをローカル変数「ｏｌｄｓｐｌ」に保管する。
２）割込みを抑制する。
３）ｋｐ−＞ｋｒ＿ｓｐｉｎと０とをアトミック的に比較交換し、成功時に「ｑｕａｄｍａｓｋ」を代入する。比較交換が失敗した場合、以下のステップを実行する。
ａ）割込みを復元する。
ｂ）ＳＰＬを「ｏｌｄｓｐｌ」に復元する。
ｃ）ＣＰＬＯＣＫＦＡＩＬを返して失敗を示す。以下のステップを実行しない。
４）そうではない場合、ｋｑｐ−＞ｋｒｑ＿ｓｐｉｎからＫＲＱ＿ＲＥＬＥＡＳＥビットをクリアするまでループする。（通常、このビットはすでにクリアされているので、このループは実行されない。）
５）ＫＲＱ＿ＭＥ２ＨＯＬＤＭＡＳＫを使用して、ｋｑｐ−＞ｋｒｑ＿ｓｐｉｎと０とをアトミック的に比較交換する。比較交換が成功した場合、以下のステップを実行する。
ａ）割込みを復元する。
ｂ）「ｏｌｄｓｐｌ」を返して成功を示す。以下のステップを実行しない。
６）そうではない場合、すでに無条件ロック取得（ｐ＿ｋｒｌｏｃｋ）との競争が発生している。ハンドオフ・フラグ（ＫＲＱ＿ＣＰ＿ＨＡＮＤＯＦＦ）をｋｑｐ−＞ｋｒｑ＿ｓｐｉｎにアトミック的に加算して、無条件ロック（ｐ＿ｋｒｌｏｃｋ）を要求する競争中のＣＰＵにロックをハンドオフする。
７）割込みを復元する。
８）ＳＰＬを「ｏｌｄｓｐｌ」に復元する。
９）ＣＰＬＯＣＫＦＡＩＬを返して失敗を示す。
【００４０】
図９および図１０は、ロックを保持するＣＰＵからロックを解除するためのメソッドｖ＿ｋｒｌｏｃｋ７００のフロー図を示している。このフロー図は、動作全体の一般的な制御の流れを示している。割込みによってロックの解除に関する問題が発生する恐れがあるので、初期状態７０４に続いて、７０８に示すように、割込みを抑制し、ＳＰＬを引き上げる。さらに、７０８でロックが位置する現行クワッドを選択する。次に、そのクワッド上のどのＣＰＵがロック時に保持に関して選択したビットを有しているかを７１２で判定する。そのビットを選択すると、そのＣＰＵがどのクワッドに位置するかにかかわらず、選択したクワッド上の次のＣＰＵを７１６で選択する。次に、ＣＰＵは、次のＣＰＵに対するロックの解除が適当かどうかを判定しなければならない。以下の基準は、ロック解除が適当であることを示している。
１）他のＣＰＵがロックを要求している場合。
２）解除フラグ（ＫＲＱ＿ＲＥＬＥＡＳＥ）が設定されていない。これは、以前のロック解除動作のうち、まだ解除を完了していないものがまったくないことを示している。
３）このクワッドがその連続認可の割当て分を使い尽くしていないかまたは他のいかなるクワッドもロックを要求するＣＰＵを含んでいない。
４）このクワッド単位データ構造（ｋｒｑ＿ｓｐｉｎ）が同じクワッド用であるかまたは保持フィールドがクリアである。
異なるクワッド用の保持フィールドが設定されている場合、これは、以前の解除手順（ｖ＿ｋｒｌｏｃｋ）が完全に完了していないことを示している。したがって、ロックを受け取るために後続ＣＰＵを選択する場合、そのＣＰＵがロックを受け取るのに適しているかどうかをまず判定しなければならない。
【００４１】
選択したＣＰＵがロックを受け取るのに適していると判定され、ロックを受け取るために準備が整っている後続ＣＰＵがｃｐｕｓｐｉｎフィールドをＮＵＬＬに設定してなければならない場合、これは、７４０でロックを受け取るように設定された後続ＣＰＵがシステム割込みの影響を受けたことを示している。このため、７５２でロックを受け取るためにクワッド上の次のＣＰＵを選択する。ロック保持者としてのマークを付けた新しいＣＰＵが前のＣＰＵロック保持者と同じクワッド上にある場合、７６８でシステム割込みを復元し、指定のＳＰＬを設定する。しかし、ロックのハンドオフが他のクワッド上のＣＰＵに対するものである場合、前のクワッドに連続ロックが認可された回数を示す認可保持フィールドを７５６でクリアする。７６０で元のＣＰＵのクワッドからのＣＰＵがそれ以上存在する場合、７６８でシステム割込みを復元し、指定のＳＰＬを設定する。しかし、ロックを要求する前のＣＰＵロック保持者のクワッド上にそれ以上のＣＰＵが存在しない場合、７６４でグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）内のクワッド・ビットをクリアし、７６８でシステム割込みを復元し、指定のＳＰＬを設定する。したがって、ロックを要求するＣＰＵが、ロックを受け取るためにそのＣＰＵを選択した後でシステム割込みを受ける場合、解除手順は、次にロックを要求するＣＰＵを選択する。
【００４２】
同じクワッド上の選択ＣＰＵがロックを受け取るのに適していないと７１６で判定した場合、７２０でＣＰＵロック要求を保持する次のクワッドを選択する。ロックを要求する現行ロック保持者とは異なるクワッド上に他のＣＰＵがまったくない場合、現行クワッド上に要求側ＣＰＵがまったくない場合のみ、７４４で現行ＣＰＵロック保持者のクワッドを選択する。ロックを保持するＣＰＵについて７４８で解除フラグ（ＫＲＱ＿ＲＥＬＥＡＳＥ）を設定する。７２４でグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）からクワッド・ビットをクリアし、解除フラグ（ＫＲＱ＿ＲＥＬＥＡＳＥ）をクリアする。そうではない場合、７３２でこの同じクワッド上にロックを求める新しいＣＰＵ要求がある場合、７３６でハンドオフ・フラグ（ＫＲＱ＿ＣＰ＿ＨＡＮＤＯＦＦ）を設定し、７６８でロックを解除するＣＰＵへのシステム割込みを復元し、ＳＰＬを設定する。さらに、７３２でロックを要求する同じクワッド上に新しいＣＰＵがまったくない場合、７６８でロックを解除するＣＰＵへのシステム割込みを復元し、ＳＰＬを設定する。したがって、ロックを解除するための手順では、枯渇を防止するようにロックを要求するＣＰＵの位置を考慮し、すなわち、そのロックを単一クワッド内に保持する。
【００４３】
無条件ロック解除プリミティブの擬似コードは以下の通りである。
１）割込みを抑制する。
２）ｖ＿ｋｒｌｏｃｋ＿ｃｏｍｍｏｎ（ｋｐ）を呼び出して、ロックを解除する。（この関数は、指定のロックを解除し、１つ存在する場合にそれを次の要求側に渡すかまたは存在しない場合にロックを完全に解除する。）
３）割込みを復元する。
４）ＳＰＬを「ｓ」に設定する。
【００４４】
他のＣＰＵに対してロックを解除するためにｖ＿ｋｒｌｏｃｋが使用する関数（ｖ＿ｋｒｌｏｃｋ＿ｃｏｍｍｏｎ）の擬似コードは以下の通りである。
１）「ｏｌｄｓｐｉｎ」をｋｑｐ−＞ｋｒｑ＿ｓｐｉｎに設定する。この場合も、他のＣＰＵのキャッシュを無効にすることが望ましい可能性がある。
２）「ｏｌｄｓｐｉｎ」内の保持フィールドがこのＣＰＵを示していない場合、先行するｖ＿ｋｒｌｏｃｋ（）演算はまだ完全に完了していない。保持フィールドがこのＣＰＵを示すまでループし、各ループ反復時にｋｑｐ−＞ｋｒｑ＿ｓｐｉｎから「ｏｌｄｓｐｉｎ」を再ロードする。
３）以下のステップを無期限に繰り返す（各パスは、異なるクワッドにロックを渡そうと試みる）。
ａ）ｋｒｌｏｃｋ＿ｆｉｎｄ＿ｎｅｘｔ（ｏｌｄｓｐｉｎ＆ＫＲＱ＿ＣＰＵ＿ＲＱＳＴ＿ＭＡＳＫ，ｌａｓｔｃｐｕ）を呼び出し、その結果を「ｎｅｘｔｃｐｕ」に入れる。この関数は、「ｌａｓｔｃｐｕ」が示すＣＰＵから始めて、ハンドオフ先にするための次のＣＰＵ要求ビットをサーチする。
ｂ）以下の各条件が当てはまる場合
ｉ）ｋｒｌｏｃｋ＿ｆｉｎｄ＿ｎｅｘｔ（）がハンドオフ先にするためにこのクワッド上のＣＰＵを見つけた。
ｉｉ）ＫＲＱ＿ＲＥＬＥＡＳＥフラグが「ｏｌｄｓｐｉｎ」に設定されていない（言い換えれば、このクワッドにハンドオフしようと試みる先行するｖ＿ｋｒｌｏｃｋ（）演算が完了した）。
ｉｉｉ）このクワッド上のＣＰＵに対する連続認可の数が依然として範囲内であるかまたは「ｆｉｒｓｔｔｉｍｅ」フラグが設定されていない。
ｉｖ）このＣＰＵのクワッドにハンドオフしているかまたは「ｏｌｄｓｐｉｎ」内の保持フィールドがクリアである（先行するｖ＿ｋｒｌｏｃｋ（）が完全に完了していない場合、保持フィールドを設定することができる）。
以下のステップを使用して、このクワッド上の「ｎｅｘｔｃｐｕ」が示すＣＰＵに対してハンドオフしようと試みる。
ｉ）受取り側ＣＰＵのスピン位置を突き止め、それを指すポインタを「ｃｐｕｓｐｉｎ」に入れる。
ｉｉ）＊ｃｐｕｓｐｉｎと「ｋｑｐ」とをアトミック的に比較交換し、成功時にＮＵＬＬを代入する。この演算が失敗した場合、受取り側ＣＰＵがロックを受諾する準備ができていないことを意味する（おそらく受取り側ＣＰＵがまだスピンを開始していないかまたは割込みを受けたばかりである）。失敗時には以下を実行する。
（１）ｌａｓｔｃｐｕをｎｅｘｔｃｐｕに設定する。
（２）ｋｑｐ−＞ｋｒｑ＿ｓｐｉｎの新しいコピーを「ｏｌｄｓｐｉｎ」に入れる。この場合も、他のＣＰＵのキャッシュを無効にすることが望ましい可能性がある。
（３）このループの先頭に戻る（Ｃの「ｃｏｎｔｉｎｕｅ」文）。
ｉｉｉ）そうではない場合、比較交換演算が成功し、すでに受取り側ＣＰＵにロックをハンドオフしている。次に、クリーンアップを行わなければならない。このクリーンアップ作業は、まだ完了していない先行ｖ＿ｋｒｌｏｃｋ（）演算をすべての演算が検出する可能性がある理由の１つである。
ｉｖ）「ｎｅｗｓｐｉｎ」を（ＫＲＱ＿ＧＲＡＮＴ＿ＩＮＣ＋ＫＲＱ＿ＣＰＵ２ＲＱＳＴＨＯＬＤ（ｎｅｘｔｃｐｕ）−（ｏｌｄｓｐｉｎ＆ＫＲＱ＿ＣＰＵ＿ＨＯＬＤ＿ＭＡＳＫ）に設定する。これをアトミック的に減算すると、ロックのこの認可がカウントされ、受取り側ＣＰＵの要求フラグがクリアされ、受取り側フィールドがロックを保持していることを示すように保持フィールドが設定される。
ｖ）このクワッドがその連続認可の割当て分以上に受け取った場合、「ｎｅｗｓｐｉｎ」から（ｏｌｄｓｐｉｎ＆ＫＲＱ＿ＧＲＡＮＴ＿ＭＡＳＫ）を減算し、それにより、認可フィールドをクリアする。このステップに到達できるのは、他のどのクワッドにもロックを要求するＣＰＵがない場合だけなので、このステップは枯渇を引き起こす可能性がない（上記を参照）。
ｖｉ）「ｎｅｗｓｐｉｎ」をｋｑｐ−＞ｋｒｑ＿ｓｐｉｎにアトミック的に加算して、必要な状態更新を実行する。
ｖｉｉ）受取り側ＣＰＵが自分のクワッド上にない場合、以下のように自分のクワッド上の状態もクリーンアップしなければならない。
（１）ＫＲＬＯＣＫ２ＫＲＬＯＣＫＰＱ（ｋｐ，ＱＵＡＤ＿ＮＵＭ（））を使用して、動作中のＣＰＵのクワッドのロック構造を指すようにｋｑｐを設定する。
（２）「ｏｌｄｓｐｉｎ」をｋｑｐ−＞ｋｒｑ＿ｓｐｉｎの値に設定する。この場合も、他のＣＰＵのキャッシュを無効にすることが望ましい可能性がある。
（３）「ｎｅｗｓｐｉｎ」をｏｌｄｓｐｉｎ＆（ＫＲＱ＿ＧＲＡＮＴ＿ＭＡＳＫ｜ＫＲＱ＿ＣＰＵ＿ＨＯＬＤ＿ＭＡＳＫ）に設定する。
（４）「ｎｅｗｓｐｉｎ」をｋｑｐ−＞ｋｒｑ＿ｓｐｉｎからアトミック的に減算し、ｋｑｐ−＞ｋｒｑ＿ｓｐｉｎの古い値を「ｏｌｄｓｐｉｎ」に入れる。このアトミック減算には、認可フィールドと保持フィールドをクリアする効果がある。
（５）このクワッドからのいかなるＣＰＵもロックを要求していないことを「ｏｌｄｓｐｉｎ」が示している場合、このクワッドのビットをｋｐ−＞ｋｒ＿ｓｐｉｎからアトミック的に減算する。
（６）呼出し側に戻り、以下のステップを実行しない。
ｂ）現在選択されているクワッド上のＣＰＵにハンドオフすることが不可能である場合、ここに到達する。以下のステップはロックを完全に解除するかまたはハンドオフ先にするための他のクワッドを見つけるものである。
ｃ）ｋｐ−＞ｋｒ＿ｓｐｉｎのコピーを「ｏｌｄｓｐｉｎ」に入れる。この場合も、他のＣＰＵのキャッシュを無効にすることが望ましい可能性がある。
ｄ）「ｏｌｄｓｐｉｎ」に設定された唯一のビットが自分のクワッドに関するものである場合、以下のようにロックを完全に解除することができる。
ｉ）ｖ＿ｋｒｌｏｃｋ＿ｒｅｌｅａｓｅ（ｋｐ，ＫＲＬＯＣＫ２ＫＲＬＯＣＫＰＱ（ｋｐ，ＱＵＡＤ＿ＮＵＭ（）），ｑｕａｄｍａｓｋ）を呼び出す。これがＴＲＵＥを返す場合、ロックは完全に解除されているので、戻るだけであり、以下のステップを実行しない。
ｉｉ）ｋｐ−＞ｋｒ＿ｓｐｉｎのコピーを「ｏｌｄｓｐｉｎ」に入れる。この場合も、他のＣＰＵのキャッシュを無効にすることが望ましい可能性がある。
ｅ）「ｃｕｒｑｕａｄ」をｋｒｌｏｃｋ＿ｆｉｎｄ＿ｎｅｘｔ（ｏｌｄｓｐｉｎ，ｃｕｒｑｕａｄ）の戻り値に設定する。
ｆ）「ｋｑｐ」を「ｃｕｒｑｕａｄ」に対応するｋｒｌｏｃｋ＿ｐｑ＿ｔ構造に設定する。
ｇ）「ｆｉｒｓｔｔｉｍｅ」をＦＡＬＳＥに設定する。
ｈ）「ｏｌｄｓｐｉｎ」をｋｑｐ−＞ｋｒｑ＿ｓｐｉｎに設定する。この場合も、他のＣＰＵのキャッシュを無効にすることが望ましい可能性がある。
ｉ）「ｌａｓｔｃｐｕ」を「ｎｅｘｔｃｐｕ」に設定する。
４）このループは無期限に繰り返すので、このステップには到達しない。
【００４５】
他のＣＰＵにロックを解除するためにｖ＿ｋｒｌｏｃｋ＿ｃｏｍｍｏｎが使用する関数（ｖ＿ｋｒｌｏｃｋ＿ｒｅｌｅａｓｅ）の擬似コードは以下の通りである。
１）無期限に（または、より正確には、明示的にループを抜け出すまで）以下のステップを繰り返す。
ａ）「ｏｌｄｓｐｉｎ」内のｋｑｐ−＞ｋｒｑ＿ｓｐｉｎのコピーを獲得する。この場合も、他のＣＰＵのキャッシュを無効にすることが望ましい可能性がある。
ｂ）要求しているＣＰＵがある場合、ｐ＿ｋｒｌｏｃｋ（）との競争が発生している。ＦＡＬＳＥを返し、呼出し側にそれを分類させる。
ｃ）ｋｑｐ−＞ｋｒｑ＿ｓｐｉｎと「ｏｌｄｓｐｉｎ」とをアトミック的に比較し、成功時にＫＲＱ＿ＲＥＬＥＡＳＥを代入する。この演算が成功した場合、ループを抜け出す。
２）ｋｐ−＞ｋｒ＿ｓｐｉｎと「ｑｕａｄｍａｓｋ」とをアトミック的に比較交換し、成功時にゼロを代入する。この演算が失敗した場合、他のクワッド上のｐ＿ｋｒｌｏｃｋ（）またはｃｐ＿ｋｒｌｏｃｋ（）との競争が発生しており、以下のようにローカルｋｒｑ＿ｓｐｉｎ状態をリセットしなければならない。
ａ）数量（ｏｌｄｓｐｉｎ−ＫＲＱ＿ＲＥＬＥＡＳＥ）をｋｑｐ−＞ｋｒｑ＿ｓｐｉｎにアトミック的に加算し、ｋｑｐ−＞ｋｒｑ＿ｓｐｉｎの古い値を「ｎｅｗｓｐｉｎ」に入れる。これには、ＫＲＱ＿ＲＥＬＥＡＳＥの設定を取り消す効果がある。
ｂ）「ｎｅｗｓｐｉｎ」がいくつかの要求側ＣＰＵを有する場合、取消とこのクワッド上のｐ＿ｋｒｌｏｃｋ（）との競争が発生している。以下のように、そのうちの１つにロックをハンドオフしなければならない。
ｉ）数量（ＫＲＱ＿ＣＰ＿ＨＡＮＤＯＦＦ−（ｏｌｄｓｐｉｎ＆（ＫＲＱ＿ＣＰＵ＿ＨＯＬＤ＿ＭＡＳＫ｜ＫＲＱ＿ＣＰＵ＿ＧＲＡＮＴ＿ＭＡＳＫ）をアトミック的に加算する。これはハンドオフ・ビットを設定し、これにより、同時に保持マスクと連続認可のカウントをクリアしながら、（おそらく多数の）競争中のｐ＿ｋｒｌｏｃｋ（）演算のうちの最初の演算を続行することができる。厳密に言えば、後者は不要であるが、短時間の間、誰もロックを必要としていなければ妥当なものである。
ｉｉ）ＴＲＵＥを返し、もはやロックを保持していないことを示す。（それを解除するのではなく、それをハンドオフしたが、誰がカウントしているのか。いずれにしても、呼出し側はそれ以上ロックに介入する必要はない。）
ｃ）ＦＡＬＳＥを返し、呼出し側が競争中の演算の１つにロックをハンドオフしなければならないことを示す。
３）クワッド単位ビットを正常にクリアした場合、ここに到達する。ｋｑｐ−＞ｋｒｑ＿ｓｐｉｎからＫＲＱ＿ＲＥＬＥＡＳＥをアトミック的に減算して、解除演算を完了する。
４）ＴＲＵＥを返し、完全にロックを解除したことを示す。
【００４６】
ロックのハンドオフを受け取るための次のＣＰＵを見つけるために上記で使用する関数（ｋｒｌｏｃｋ＿ｆｉｎｄ＿ｎｅｘｔ）の擬似コードは以下の通りである。
１）「ｃｕｒｑｕａｄ」より大きい番号を有するクワッドに対応してすべてのビットが設定されるように、たとえば−（１＜＜（ｃｕｒｑｕａｄ＋１））に「ｍａｓｋ」を設定する。
２）ロックを要求するＣＰＵも含み、「ｃｕｒｑｕａｄ」より大きい番号を有するすべてのクワッド用に設定されたビットを含むように、たとえばｒｑｓｔｍａｓｋ＆ｍａｓｋに「ｍａｓｋｒｅｓｕｌｔ」を設定する。
３）「ｍａｓｋｒｅｓｕｌｔ」がゼロに等しくない場合、「ｍａｓｋｒｅｓｕｌｔ」内の最下位ビットの数字を返す。これは、ロックを渡そうと試みる次のクワッドの番号になる。以下のステップを実行しない。
４）「ｍａｓｋ」を補完する。これは、「ｍａｓｋ」により「ｃｕｒｑｕａｄ」より小さいかまたは等しい番号を有するクワッドに対応してすべてのビットを設定させる。
５）ロックを要求するＣＰＵも含み、「ｃｕｒｑｕａｄ」より小さい番号を有するすべてのクワッド用に設定されたビットを含むように、たとえばｒｑｓｔｍａｓｋ＆ｍａｓｋに「ｍａｓｋｒｅｓｕｌｔ」を設定する。
６）「ｍａｓｋｒｅｓｕｌｔ」がゼロに等しくない場合、「ｍａｓｋｒｅｓｕｌｔ」内の最下位ビットの数字を返す。これは、ロックを渡そうと試みる次のクワッドの番号になる。以下のステップを実行しない。
７）ＫＲＱ＿ＣＰＵ＿ＮＯＮＥを返し、ハンドオフ先になるためのクワッドがそれ以上存在しないことを示す。アルゴリズムのこの構造により、この文は決して実行されない。設定された現行クワッドのビットを常に残しておくので、必ずロックを渡そうと試みるクワッドが少なくとも１つ存在する。
【００４７】
スピンを取り消すための関数（ｋｒｌｏｃｋ＿ｒｒｕｐｔ＿ｅｎｔｅｒ＿ｃｈｋ＿ｃｏｍｍｏｎ）の擬似コードは以下の通りである。
１）「ｃｐｕｓｐｉｎ」が指す値をアトミック的にＮＵＬＬと交換し、古い値を「ｏｌｄｓｐｉｎ」に入れる。
２）「ｏｌｄｓｐｉｎ」がＮＵＬＬである場合、すでにロックが認可されている。
ａ）ｖ＿ｋｒｌｏｃｋ＿ｃｏｍｍｏｎ（ｋｐ）を呼び出して、ロックを解除する。
ｂ）ロックを保持せずに割込みハンドラ内を前進するために割込み入口コードに戻る。割込み出口コードは、ロック上でのスピンを取り消させることになる。
３）以下のステップを無期限に繰り返す（各パスは、ｋｒｑ＿ｓｐｉｎマスクから要求ビットを除去しようと試みる）。
ａ）「ｏｌｄｓｐｉｎ」をｋｑｐ−＞ｋｒｑ＿ｓｐｉｎに設定する。この場合も、他のＣＰＵによるそのキャッシュ・ラインのコピーを無効にすることが有利である可能性がある。
ｂ）「ｏｌｄｓｐｉｎ」にＫＲＱ＿ＲＥＬＥＡＳＥビットが設定されている場合、そのビットがクリアされるまでループし、ｋｑｐ−＞ｋｒｑ＿ｓｐｉｎの最新のコピーを拾い上げる。通常、ＫＲＱ＿ＲＥＬＥＡＳＥは設定されない。
ｃ）「ｎｅｗｓｐｉｎ」をｏｌｄｓｐｉｎ−ｃｐｕｍａｓｋに設定する。これには、このＣＰＵの要求ビットをクリアする効果がある。
ｄ）ｋｑｐ−＞ｋｒｑ＿ｓｐｉｎと「ｏｌｄｓｐｉｎ」とをアトミック的に比較交換し、成功時に「ｎｅｗｓｐｉｎ」を代入する。この比較交換が成功した場合、以下のステップを実行する。
ｉ）このクワッド上に要求しているＣＰＵがそれ以上存在しない場合、このクワッドのビットをｋｐ−＞ｋｒ＿ｓｐｉｎからアトミック的にクリアする。
ｉｉ）割込み入口コードに戻る。
【００４８】
スピンを再始動するための関数（ｋｒｌｏｃｋ＿ｒｒｕｐｔ＿ｅｘｉｔ＿ｃｈｋ＿ｃｏｍｍｏｎ）の擬似コードは以下の通りである。
１）ｐ＿ｋｒｌｏｃｋ＿ｎｏｃｏｎｔｅｎｄ（ｋｐ，ｋｑｐ，ｃｐｕｍａｓｋ）を呼び出して、ロックを求める要求を再発行する。このプリミティブがＦＡＬＳＥ（直ちにロックを獲得しなかったことを示す）を返す場合
ａ）「ｋｑｐ」をｃｐｕｓｐｉｎが指す値とアトミック的に交換し、ｃｐｕｓｐｉｎが指す古い値を処分する。
【００４９】
前述のように、無条件でロックを解除する場合、ロックを解除するかまたはロックをハンドオフするときに発生しうる競争が、競合ＣＰＵ間に存在する。このような競争状態はいずれも、スピン状態（ｋｒｑ＿ｓｐｉｎ）データ構造内のハンドオフ・フラグ（ＫＲＱ＿ＣＰ＿ＨＡＮＤＯＦＦ）および解除フラグ（ＫＲＱ＿ＲＥＬＥＡＳＥ）ビットによって解決される。ハンドオフ・フラグは、条件付きロック取得によりロックを要求するプロセッサと無条件ロック取得によりロックを要求するプロセッサとの間で発生しうる、プロセッサ間の連絡不良を制御するように設定される。解除フラグは、ロックの取得と解除との間に発生しうる競争を防止するように設定される。以下の例は、プロセッサまたはＣＰＵあるいはその両者間で発生しうるロックの競争と、ハンドオフ・フラグによってその競争を解決する方法の例証となるものである。
【００５０】
例
例Ｉ：
クワッドあたり４つのＣＰＵがあり、ＣＰＵ０、１、２、３がクワッド０にあり、ＣＰＵ４、５、６、７がクワッド１にあり、以下同様であると想定すると、以下の競争は、以下の仮説事象に沿ってハンドオフ・フラグによって解消することができる。
１）ＣＰＵ０は条件付きロック取得プリミティブを実行し、これがクワッド０のビットをグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）に設定する。グローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）には他のいかなるビットも設定されないので、ＣＰＵ０はそのクワッド・レベルに移行することができる。
２）ＣＰＵ１は無条件ロック取得プリミティブを実行し、これがＣＰＵ１の要求ビットをクワッド０のスピン状態データ構造（ｋｒｑ＿ｓｐｉｎ）に設定する。
３）ＣＰＵ１は、それがクワッド０のスピン状態データ構造（ｋｒｑ＿ｓｐｉｎ）に要求ビットを設定するための最初のＣＰＵであると検出するので、グローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）にクワッド０のビットを設定しようと試みる。ＣＰＵ０がすでにそれを設定しているので、ＣＰＵ１はそのように実行することができない。
４）ＣＰＵ２も無条件ロック取得プリミティブを実行し、これがＣＰＵ２の要求ビットをクワッド０のスピン状態データ構造（ｋｒｑ＿ｓｐｉｎ）に設定する。
５）ＣＰＵ０は、ＣＰＵ０の要求ビットをクワッド０のスピン状態データ構造（ｋｒｑ＿ｓｐｉｎ）に設定しようと試みるが、ＣＰＵ１および２がすでにそのように実行しているので、そのように実行することができない。本明細書で提示する実現例ではＣＰＵ０にハンドオフ・フラグを設定させ、これにより、それがその時点でロックを保持していることをＣＰＵ１に信号で知らせることになる。
ハンドオフ・フラグがまったくない場合、他の設計上の選択肢に応じて、以下の問題の１つが発生する恐れがある。
１）ＣＰＵ０以外のいかなるＣＰＵも、ＣＰＵ０がそのクワッド・ビットをグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）に設定したロックを取得できないので、単にＣＰＵ０によってクワッド０上でスピンする他のＣＰＵのうちの１つにハンドオフすることになるだろう。問題は、どのＣＰＵを選択するかを決定することである。ＣＰＵ０がＣＰＵ２を選択する場合、ＣＰＵ１は高いＳＰＬでスピンすることになるが、割込みが禁止された状態で長期間の間、スピンすることになる。
２）条件付きロック取得プリミティブによりグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）内のビットをクリアさせる。この結果、ハングが発生する。他のクワッド上のＣＰＵがそのビットをグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）に設定したばかりである場合、そのＣＰＵと、このクワッド上にあって条件付きロック取得プリミティブを打ち出すＣＰＵの両方は、他のＣＰＵがロックを保持していると結論を下すことになり、どちらも永遠にこの架空のＣＰＵがそれらにハンドオフするのを待つことになるだろう。
３）条件付きロック取得プリミティブにより、他のビットが設定されていない場合のみグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットをクリアさせ、他のビットが設定されている場合は他のクワッド上のＣＰＵにハンドオフさせる。この場合の問題は、ハンドオフ先にすべき他のクワッド上のＣＰＵがそのクリティカル・セクションを終了し、グローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットのクリアに取りかかる前に、そのクワッドにロックをハンドオフしようと試みる可能性があることである。この場合も、結果的に、高いＳＰＬでスピンする第１のＣＰＵはそのクワッドのグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットを設定するのを待つことになるだろう。
【００５１】
ハンドオフ・フラグに加え、解除フラグも存在する。解除フラグは、ロック解除とロック取得の動作中にプロセッサまたはＣＰＵあるいはその両者間で発生する競争を解決するように設定される。根底にある問題は、無条件ロック解除プリミティブがそのクワッド単位データ構造（ｋｒｑ＿ｓｐｉｎ）ビットをクリアする前にそのグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットをクリアすることである。この結果、他のＣＰＵがそれらにロックをハンドオフするだろうと他のクワッド上のＣＰＵが結論を下しうる遷移状況に至り、その結果、ハングが発生するかまたはクリティカル・セクションに同時に複数のＣＰＵが存在することになる可能性がある。以下の例は、解除フラグの必要性の例証となるものである。
【００５２】
例ＩＩ：
１）無条件ロック解除を実行しているＣＰＵ０は、ロックを求めるそれ以上の要求を認識せず、したがって、クワッド０のスピン状態データ構造（ｋｒｑ＿ｓｐｉｎ）ビットのすべてをクリアする。
２）ＣＰＵ４はクワッド１で無条件ロック取得プリミティブを実行し、クワッド単位データ構造（ｋｒｑ＿ｓｐｉｎ）要求ビット内のそのスピン状態をクワッド単位データ構造（ｋｒｑ＿ｓｐｉｎ）内のクワッド１のスピン状態に設定する。ＣＰＵ４は、それがクワッド１上の最初の要求であることを認識し、したがって、そのスピン状態データ構造（ｋｒ＿ｓｐｉｎ）ビットを設定する。そのＣＰＵは、クワッド０のビットが依然として設定されているのでそのＣＰＵが最初ではないことを認識し、スピンに取りかかる。
３）ＣＰＵ１はクワッド０で無条件ロック取得を実行し、クワッド単位データ構造（ｋｒｑ＿ｓｐｉｎ）要求ビット内のそのスピン状態をクワッド単位データ構造（ｋｒｑ＿ｓｐｉｎ）ビットマスク内のクワッド０のスピン状態に設定する。ＣＰＵ０も、それがクワッド０上の最初の要求であることを認識し、したがって、グローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）内のクワッド０のビットがクリアされるのを待って、スピンを開始する。
４）ＣＰＵ０は、クワッド１がそれが設定したグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）であることを認識するので、完全にロックを解除することはできないが、むしろ、それをハンドオフしなければならない。この時点では、（ａ）クワッド０のグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットをクリアできるが、クワッド１上のＣＰＵにハンドオフしようと試みるか、または（ｂ）設定されたクワッド０のグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットを残しておき、それでもクワッド１上のＣＰＵにハンドオフすることができるという、いくつかの選択肢がある。
ａ）ＣＰＵ４にハンドオフする前にＣＰＵ０がクワッド０のグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットをクリアすると想定する。この結果、ＣＰＵ１とＣＰＵ４がともにそれらがロックを保持していると確信するという競争が発生する可能性がある。
ｉ）ＣＰＵはそのグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）内のクワッド０のビットをクリアする。
ｉｉ）ＣＰＵ０はクワッド１のスピン状態データ構造（ｋｒｑ＿ｓｐｉｎ）フィールドのコピーを拾い上げる。
ｉｉｉ）ＣＰＵ４は割込みを受け取り、したがって、クワッド１のスピン状態データ構造（ｋｒｑ＿ｓｐｉｎ）フィールドからその要求をクリアし、グローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）からクワッド１のビットをクリアする。
ｉｖ）ＣＰＵ１はクワッド０のグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットを設定し、他のグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットがまったく設定されていないことを認識する。したがって、ＣＰＵ１は、それがロックを保持し、そのクリティカル・セクションに入るという結論を下す。
ｖ）ＣＰＵ４はその割込みから戻り、クワッド１のスピン状態データ構造（ｋｒｑ＿ｓｐｉｎ）フィールドにそのビットを設定し、グローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）にクワッド１のビットを設定することにより、その要求を復旧させる。クワッド０のビットはすでにグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）に設定されているので、ＣＰＵ４は、それがロックを保持していないことを把握し、したがってスピンに取りかかる。
ｖｉ）ＣＰＵ０は、ＣＰＵ１がロックを保持していることに気づかずに、この時点で回復する。したがって、ＣＰＵ０はＣＰＵ４にロックをハンドオフするので、ＣＰＵ１とＣＰＵ４の両方が同時にクリティカル・セクションに入っている。
ｂ）ＣＰＵ０は、ＣＰＵ４にハンドオフしながら、設定されたクワッド０のグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットを残しておくものと想定する。この場合、以下の一連の事象が発生しうる。
ｉ）ＣＰＵ０はＣＰＵ４にロックをハンドオフする。
ｉｉ）ＣＰＵ４はそのクリティカル・セクションに入る。
ｉｉｉ）ＣＰＵ２は無条件ロック取得を実行し、その要求ビットをクワッド０のスピン状態データ構造（ｋｒｑ＿ｓｐｉｎ）フィールドに設定する。ＣＰＵ２は、ＣＰＵ１がすでにそのスピン状態データ構造（ｋｒｑ＿ｓｐｉｎ）ビットを設定したことを認識しているので、ＣＰＵ２は通常通りスピンに取りかかる。
ｉｖ）ＣＰＵ４はそのクリティカル・セクションを終了し、クワッド０のグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットが設定されていることを認識し、ＣＰＵ２にロックをハンドオフする。次にＣＰＵ２はそのクリティカル・セクションに入る。
ｖ）次に、２つのうちの１つが発生する可能性がある。ＣＰＵ０がクワッド０のグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットをクリアした場合、ＣＰＵ５は条件付きロック取得メソッドを実行する可能性があり、グローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）にはもはやいずれのビットも設定されていないので、ＣＰＵ２が依然としてそのクリティカル・セクションに入っていても、ＣＰＵ５はそれがロックを所有していると考えることになるだろう。これに対して、ＣＰＵ０が単に設定されたクワッド０のグローバル・ビットマスク（ｋｒ＿ｓｐｉｎ）ビットを残しておく場合、ＣＰＵ１は割込みが禁止された状態で長期間の間、スピンすることになり、これは割込み待ち時間にとって不適当なことである。
したがって、解除フラグとハンドオフ・フラグの両方に関する競争を示す上記の例示は、本発明の好ましい実施形態においてこれらのフラグ両方が必要であることと、ロックの適切な使用法を保証し、ロック取得とロック解除との間でＣＰＵ間の連絡不良を防止するためにそれらがどのように機能するかを例示するものである。
【００５３】
従来技術を超える利点
このカーネル・ラウンドロビン・ロック・プリミティブでは、システム上の全プロセッサの階層を考慮する。このため、このプリミティブは、小規模システムと同様に大規模なＣＣ−ＮＵＭＡシステム上で機能することができる。このプリミティブは、条件付きロック取得と無条件ロック取得の両方を可能にし、ロックを解除するプロセッサがロックを認可すべき次のプロセッサを選択できるようにする。あるプロセッサから後続プロセッサへロックを認可することにより、インタークワッド参照の数を最小限にする。さらに、プロセッサは専用メモリ上でのロック・スピンを要求し、それにより、ローカル・バス上の負荷が低減され、長引くロックに比べ、低レベルおよび高レベル両方のコンテンション時にパフォーマンスが増進する。
【００５４】
代替実施形態
例示のために本発明の具体的な実施形態について本明細書に記載してきたが、本発明の精神および範囲を逸脱せずに様々な変更が可能であることが分かるだろう。特に、当業者であれば、好ましい実施形態で使用するスピンロックの代わりにブロッキング・ロックを使用できることが分かるだろう。さらに、好ましい実施形態では、ローカル（非リモート）メモリ上のみでスピンする割込み可能ロックの使用を企図しているが、本発明は、ロックがローカル（非リモート）メモリ上のみでスピンするが割込み不能にすることができることまたはロックが割込み可能であるがリモート・メモリ上でスピンすることができることという条件のうちの一方または他方のみを必要とする。したがって、本発明の保護範囲は、特許請求の範囲およびそれと同等のもののみによって限定される。
【図面の簡単な説明】
【００５５】
【図１】本発明の好ましい実施形態のｋｒｌｏｃｋ＿ｔデータ構造を示す図である。
【図２】本発明の好ましい実施形態のｋｒｌｏｃｋ＿ｐｑ＿ｔデータ構造を示す図である。
【図３】本発明の好ましい実施形態のｋｒｑ＿ｓｐｉｎデータ構造を示す図である。
【図４】本発明の好ましい実施形態のｋｒｌｏｃｋ＿ｃｈｄｒ＿ｔデータ構造を示す図である。
【図５】本発明の好ましい実施形態のｋｒｌｏｃｋ＿ｃｌｕｓｔｅｒｓデータ構造を示す図である。
【図６】本発明の好ましい実施形態のｋｒｌｏｃｋ＿ｃｌｕｓｔｅｒｓデータ構造を示す図である。
【図７】本発明の好ましい実施形態による無条件ロック取得モードのフロー図である。
【図８】本発明の好ましい実施形態による無条件ロック取得モードのフロー図である。
【図９】ロック解除モードのフロー図である。
【図１０】ロック解除モードのフロー図である。
【図１１】条件付きロック取得モードのフロー図である。
【図１２】メモリ待ち時間を示すマルチプロセッサ・コンピュータ・システムのブロック図である。
【図１】
0004750074.tif 000002
【図２】
0004750074.tif 000003
【図３】
0004750074.tif 000004
【図４】
0004750074.tif 000005
【図５】
0004750074.tif 000006
【図６】
0004750074.tif 000007
【図７】
0004750074.tif 000008
【図８】
0004750074.tif 000009
【図９】
0004750074.tif 000010
【図１０】
0004750074.tif 000011
【図１１】
0004750074.tif 000012
【図１２】
0004750074.tif 000013