(57)【要約】【課題】  情報処理システムにおいてリソースに対するアクセスについてのユーザ間のコンテンションを管理するための方法および装置を提供すること。  【解決手段】  マルチシステム・クラスタにおいてリソースに対するアクセスについてユーザ間のコンテンションを管理するための方法および装置。コンテンション・チェーンを識別し、各ユーザは、チェーン内の前のユーザ（複数のユーザ）によって保持されるリソースを待機している。チェーンの頭部におけるユーザ（複数のユーザ）に、それらの必要値が少なくともチェーン内の最高必要度の待機者のものであるかのように、システム・リソースを割り当てる。システム間のデータフローが最小であり、どのシステムもシステム間コンテンションの完全なビューを有しないとしても、最適なリソース割り当てのために必要なコンテンション・データは、システム・クラスタ間で効果的に分配される。
2006512688.tif 000002
【特許請求の範囲】
【請求項１】
複数のシステムを含むシステム・クラスタにおいて１つ以上のリソースに対するアクセスについてのユーザ間のコンテンションを管理するための方法であって、前記ユーザの各々が割り当てられた必要値を有し、アクセスを求めているリソースの保持者または待機者のいずれかとなることができ、前記方法が、ローカル・システムとしての前記システムの少なくとも１つにおいて実行され、
前記ローカル・システム上のコンテンションに基づいて、前記リソースを１つ以上のローカル・クラスタにグループ化することを示し、前記ローカル・クラスタの各々ごとに、前記ローカル・クラスタにおける１つ以上のリソースの必要値を示す、ローカル・クラスタ・データを保存するステップと、
前記システム・クラスタにおける遠隔システムとしての別のシステムから、前記遠隔システム上のコンテンションに基づいて前記リソースを１つ以上の遠隔クラスタにグループ化することを示し、前記遠隔クラスタの各々ごとに前記遠隔クラスタにおける１つ以上のリソースの必要値を示す、遠隔クラスタ・データを受信するステップと、
前記ローカル・クラスタ・データおよび前記遠隔クラスタ・データを組み合わせて、前記システム間のコンテンションに基づいて前記リソースを１つ以上の複合クラスタにグループ化することを示し、前記複合クラスタの各々ごとに前記複合クラスタにおける１つ以上のリソースの必要値を示す、複合クラスタ・データを生成するステップと、
前記クラスタのための前記複合クラスタ・データに従って前記複合クラスタの１つにおいて前記ローカル・システム上のリソースの保持者を管理するステップと、
を有する、方法。
【請求項２】
前記クラスタのいずれかにおける１つ以上のリソースの前記必要値が、前記クラスタにおけるいずれかのリソースについての最高必要度の待機者の必要値である、請求項１に記載の方法。
【請求項３】
前記管理するステップが、
他のいずれかのリソースを待機していない前記複合クラスタの１つにおいて前記ローカル・システム上のリソースの保持者を識別するステップと、
前記ローカル・システム上の前記リソースの前記保持者に、その必要値が少なくとも前記複合クラスタにおけるいずれかのリソースの最高必要度の待機者のものであるかのようにシステム・リソースを割り当てるステップと、
を有する、請求項１に記載の方法。
【請求項４】
前記受信するステップが、遠隔システムとしての前記システム・クラスタにおける複数の他のシステムの各々ごとに実行される、請求項１に記載の方法。
【請求項５】
前記ローカル・システム上のユーザが前記リソースの１つを保持していると共に前記リソースの他のものを待機している場合、前記ローカル・システムが１対のリソースを共通ローカル・クラスタに割り当てる、請求項１に記載の方法。
【請求項６】
前記ローカル・システム上のユーザに関してリソースのコンテンション・ステータスの変化の通知の受信に応答して、前記ローカル・システムが前記ローカル・クラスタ・データを更新する、請求項１に記載の方法。
【請求項７】
前記ローカル・システムが前記更新したローカル・クラスタ・データを前記遠隔システムに送信する、請求項６に記載の方法。
【請求項８】
前記遠隔システムから遠隔クラスタ・データを受信すると、前記ローカル・システムが前記複合クラスタ・データを更新する、請求項１に記載の方法。
【請求項９】
前記ローカル・システムがローカル・クラスタ・データを前記遠隔システムに送信する、請求項１に記載の方法。
【請求項１０】
前記送信されたローカル・クラスタ・データが、リソースと、前記ローカル・システム上のコンテンションに基づいて前記リソースを割り当てるクラスタと、前記リソースのための前記ローカル・システム上の必要値とを示す、請求項９に記載の方法。
【請求項１１】
複数のシステムを含むシステム・クラスタにおいて１つ以上のリソースに対するアクセスについてのユーザ間のコンテンションを管理するための装置であって、前記ユーザの各々が割り当てられた必要値を有し、アクセスを求めているリソースの保持者または待機者のいずれかとなることができ、前記装置が、ローカル・システムとしての前記システムの少なくとも１つに関連付けられ、
前記ローカル・システム上のコンテンションに基づいて、前記リソースを１つ以上のローカル・クラスタにグループ化することを示し、前記ローカル・クラスタの各々ごとに、前記ローカル・クラスタにおける１つ以上のリソースの必要値を示す、ローカル・クラスタ・データを保存するための論理と、
前記システム・クラスタにおける遠隔システムとしての別のシステムから、前記遠隔システム上のコンテンションに基づいて前記リソースを１つ以上の遠隔クラスタにグループ化することを示し、前記遠隔クラスタの各々ごとに前記遠隔クラスタにおける１つ以上のリソースの必要値を示す、遠隔クラスタ・データを受信するための論理と、
前記ローカル・クラスタ・データおよび前記遠隔クラスタ・データを組み合わせて、前記システム間のコンテンションに基づいて前記リソースを１つ以上の複合クラスタにグループ化することを示し、前記複合クラスタの各々ごとに前記複合クラスタにおける１つ以上のリソースの必要値を示す、複合クラスタ・データを生成するための論理と、
前記クラスタのための前記複合クラスタ・データに従って前記複合クラスタの１つにおいて前記ローカル・システム上のリソースの保持者を管理するための論理と、
を有する、装置。
【請求項１２】
前記管理する論理が、
他のいずれかのリソースを待機していない前記複合クラスタの１つにおいて前記ローカル・システム上のリソースの保持者を識別するための論理と、
前記ローカル・システム上の前記リソースの前記保持者に、その必要値が少なくとも前記複合クラスタにおけるいずれかのリソースの最高必要度の待機者のものであるかのようにシステム・リソースを割り当てるための論理と、
を有する、請求項１１に記載の装置。
【請求項１３】
前記ローカル・システム上のユーザが前記リソースの１つを保持していると共に前記リソースの他のものを待機している場合、前記ローカル・システムが１対のリソースを共通ローカル・クラスタに割り当てる、請求項１１に記載の装置。
【請求項１４】
前記ローカル・システム上のユーザに関してリソースのコンテンション・ステータスの変化の通知の受信に応答して、前記ローカル・システムが前記ローカル・クラスタ・データを更新し、前記更新したローカル・クラスタ・データを前記遠隔システムに送信する、請求項１１に記載の装置。
【請求項１５】
前記ローカル・システムがローカル・クラスタ・データを前記遠隔システムに送信し、前記送信されたローカル・クラスタ・データが、リソースと、前記ローカル・システム上のコンテンションに基づいて前記リソースを割り当てるクラスタと、前記リソースのための前記ローカル・システム上の必要値とを示す、請求項１１に記載の装置。
【請求項１６】
機械によって読み取り可能なプログラム・ストレージ・デバイスであって、前記機械によって実行可能な命令のプログラムを実際に具現化して、複数のシステムを含むシステム・クラスタにおいて１つ以上のリソースに対するアクセスについてのユーザ間のコンテンションを管理するための方法ステップを実行し、前記ユーザの各々が割り当てられた必要値を有し、アクセスを求めているリソースの保持者または待機者のいずれかとなることができ、前記方法ステップが、ローカル・システムとしての前記システムの１つにおいて実行され、
前記ローカル・システム上のコンテンションに基づいて、前記リソースを１つ以上のローカル・クラスタにグループ化することを示し、前記ローカル・クラスタの各々ごとに、前記ローカル・クラスタにおける１つ以上のリソースの必要値を示す、ローカル・クラスタ・データを保存するステップと、
前記システム・クラスタにおける遠隔システムとしての別のシステムから、前記遠隔システム上のコンテンションに基づいて前記リソースを１つ以上の遠隔クラスタにグループ化することを示し、前記遠隔クラスタの各々ごとに前記遠隔クラスタにおける１つ以上のリソースの必要値を示す、遠隔クラスタ・データを受信するステップと、
前記ローカル・クラスタ・データおよび前記遠隔クラスタ・データを組み合わせて、前記システム間のコンテンションに基づいて前記リソースを１つ以上の複合クラスタにグループ化することを示し、前記複合クラスタの各々ごとに前記複合クラスタにおける１つ以上のリソースの必要値を示す、複合クラスタ・データを生成するステップと、
前記クラスタのための前記複合クラスタ・データに従って前記複合クラスタの１つにおいて前記ローカル・システム上のリソースの保持者を管理するステップと、
を有する、プログラム・ストレージ・デバイス。
【請求項１７】
前記管理するステップが、
他のいずれかのリソースを待機していない前記複合クラスタの１つにおいて前記ローカル・システム上のリソースの保持者を識別するステップと、
前記ローカル・システム上の前記リソースの前記保持者に、その必要値が少なくとも前記複合クラスタにおけるいずれかのリソースの最高必要度の待機者のものであるかのようにシステム・リソースを割り当てるステップと、
を有する、請求項１６に記載のプログラム・ストレージ・デバイス。
【請求項１８】
前記ローカル・システム上のユーザが前記リソースの１つを保持していると共に前記リソースの他のものを待機している場合、前記ローカル・システムが１対のリソースを共通ローカル・クラスタに割り当てる、請求項１６に記載のプログラム・ストレージ・デバイス。
【請求項１９】
前記ローカル・システム上のユーザに関してリソースのコンテンション・ステータスの変化の通知の受信に応答して、前記ローカル・システムが前記ローカル・クラスタ・データを更新し、前記更新したローカル・クラスタ・データを前記遠隔システムに送信する、請求項１６に記載のプログラム・ストレージ・デバイス。
【請求項２０】
前記ローカル・システムがローカル・クラスタ・データを前記遠隔システムに送信し、前記送信されたローカル・クラスタ・データが、リソースと、前記ローカル・システム上のコンテンションに基づいて前記リソースを割り当てるクラスタと、前記リソースのための前記ローカル・システム上の必要値とを示す、請求項１６に記載のプログラム・ストレージ・デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システムにおいて逐次化リソースにアクセスするユーザ間のコンテンションを管理するための方法および装置に関する。更に具体的には、これは、複数のかかるシステムを含むシステム・クラスタにおいて、かかるコンテンションを管理するための方法および装置に関する。
【背景技術】
【０００２】
リソース・コンテンションは、情報処理システムにおいて周知の現象である。これが発生するのは、ユーザ（例えばプロセスまたは他の作業単位）が、すでに別のユーザが保持するリソースにアクセスを試みる場合であり、第２のユーザが要求するアクセスは第１のユーザのものと相反する。これは、例えば、どちらかのユーザが対象のリソースに対して排他的なアクセスを要求している場合に発生する。リソース・マネジャは、それらが制御するリソースに対する競合した要求間のコンテンションを管理するソフトウエア・コンポーネントであり、保持者として１人以上のかかるユーザにそのリソースに対するアクセスを与え、そのリソースが利用可能となるまで残りのユーザを待機者のプールに配置する。
【０００３】
ＩＢＭ  ｚ／ＯＳ（商標）オペレーティング・システム等のコンピュータ・オペレーティング・システムでは、多数のリソース・マネジャおよび多数の作業単位があるので、リソース・コンテンション管理は複雑な問題である。コンテンション・チェーンが生じる場合がある。換言すると、コンテンションはリソース間にまたがる可能性がある。例えば、ジョブＡはリソースＲ１を待つがＲ２を保持し、ジョブＢはＲ１を保持するがＲ３を待っており、Ｒ３はジョブＣによって保持される。コンテンションは、システム間にまたがって生じる可能性がある。上述の例で、各ジョブは別個のシステム上にある場合がある。コンテンションは、リソース・マネジャをまたがって生じる可能性がある。例えば、Ｒ１はＧＲＳエンキューであり、Ｒ２はＤＢ２（商標）ラッチとすることができる。ｚ／ＯＳの大域資源逐次化（ＧＲＳ：global resource serialization）コンポーネントはエンキューを管理し、ＩＭＳ（商標）リソース・ロック・マネージャ（ＩＲＬＭ：IMS Resource Lock Manager）はＤＢ２リソースを別個に管理する。
【０００４】
リソース間コンテンションは、通常、各リソースの保持者および待機者のトポロジを追跡し、いずれかの交点を見つけることによって、単一のリソース・マネジャ（例えばＧＲＳ）内で解決する。システム間コンテンションは、通常、リソース・マネジャに全クラスタのデータを認識させることによって解決する（クラスタを独立した複数のシステムとしてでなく１つのユニットとして管理する）。リソース・マネジャ間コンテンションは、通常、報告プロダクトに、バーチャル・リソース・マネジャであるかのように全インタフェースに問合せを行わせ、データを相関させることによって「解決」する。この問題は、コンテンションの状態にあるリソース数においてオーダーＯ（２n）であるので、計算上、複雑である。
【０００５】
ｚ／ＯＳの基本ＭＶＳ（商標）コンポーネントは、単純で効率的な解決策を有する（一般に、「エンキュー促進」として既知である）。すなわち、コンテンションの状態にあると報告されるリソースを保持するいずれかの作業のＣＰＵおよびＭＰＬアクセスを自動的に（かつ一時的に）増大させ、作業の必要度には注目しない。これは、実際のトポロジには無関係に、リソースのための「重要な」待機者（複数の待機者）があるかのように保持者を管理することと同等である。この動作を理解するため、以下の例を考える。以下のことを仮定する。
１．ジョブＡがリソースＲ１を保持する。
２．ジョブＢがリソースＲ２を保持しＲ１を待つ。
３．ジョブＣがＲ２を待つ。
【０００６】
表記上、これは、チェーンＣ→Ｂ→Ａと表すことができる。大文字はジョブを表し、符号「→」（チェーンにおける「リンク」）は、この符号の左側のジョブがこの符号の右側のジョブによって保持されるリソースを待っていることを示す。このため、上述のチェーンは、ジョブＣが、ジョブＢによって保持されるリソースを待っており、ジョブＢが、ジョブＡが保持するリソースを待っていることを意味する。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
これらがＧＲＳリソースであると仮定すると、従来のＭＶＳ実施では、ジョブＡおよびＢがコンテンションの状態にあるリソースを保持するので、それらのために役立ち、各々を等しく、限られた時間だけ促進する。しかしながら、Ｂに役立つのは無益である。なぜなら、Ｂは実際Ａを待っているからである。Ｂがそれ自身マルチタスキングである場合、この支援は実際、リソース・コンテンションに関して何もせずに、競合する作業に有害となる恐れがある。
【課題を解決するための手段】
【０００８】
本発明の１つの態様は、先に確認した同時出願の主題であり、情報処理システムにおいてリソースに対するアクセスについてのユーザ間のコンテンションを管理するための方法および装置を含む。各ユーザは、割り当てられた必要値を有し、アクセスを求めているリソースの保持者または待機者のいずれかとなることができる。本発明のこの態様によれば、ユーザのチェーンの頭部において待機者でないユーザを識別する。チェーン内では、チェーン内に次のユーザを有する各ユーザが、次のユーザが待っているリソースを保持している。チェーンの頭部におけるユーザは、その必要値が少なくともチェーンにおける最高必要度の待機者のものであるかのように管理され、好ましくは、ユーザに、その必要値が少なくともかかる最高必要度の待機者のものであるかのようにシステム・リソースを割り当てる。
【０００９】
好ましくは、本発明のこの態様の独立した発明の特徴として、かかるコンテンション・チェーンは、リソースのクラスタを識別することによって識別される。クラスタ内の各リソースは、クラスタ内の別のリソースを待っているユーザによって保持されるか、クラスタ内の別のリソースを保持しているユーザによって待機されているかのいずれかである。更に、クラスタ内のいずれかのリソースの最高必要度の待機者の必要値を決定する。ユーザは、クラスタ内のリソースの保持者であるが他のいずれかのリソースを待っていないものとして識別され、リソースのその保持者は、その必要値が少なくともクラスタ内の他のいずれかの最高必要度の待機者のものであるかのように管理される。この場合も、好ましくは、ユーザに、その必要値が少なくともかかる最高必要度の待機者のものであるかのようにシステム・リソースを割り当てる。
【００１０】
クラスタを識別するステップは、好ましくは、リソースのコンテンション・ステータスの変更の通知の受信に応答して行われる。このため、リソースは、クラスタ内の別のリソースを待機しているユーザによって保持されているか、またはクラスタ内の別のリソースを保持しているユーザによって待機されている場合、新たにクラスタに割り当てられる。一方、リソースは、クラスタ内の別のリソースを待機しているユーザによってもはや保持されていないか、またはクラスタ内の別のリソースを保持しているユーザによって待機されていない場合、クラスタから除去される。
【００１１】
このため、本発明のこの態様は、「必要度」のファクタを、基本システム・リソース割り当て機構に統合することを考え、そのため、チェーンの頭部におけるジョブ（例えば上述のジョブＡであり、必要度ファクタ４）が、リソースを解放するまで、チェーン上のどこか別の場所のもっと必要度が高いジョブ（例えば上述のジョブＣであり、必要値１）の必要度ファクタを有するかのように実行することができる。必要度の概念を先の例に統合すると、これがどのように異なる方法で実行するかをより良く理解することができる。以下を想定する。
１．ジョブＡは、「必要値」４を有し、リソースＲ１を保持する。（この明細書では、小さい数が大きい必要度を表すので、「支援の優先度」として考えることができる。）
２．ジョブＢは、必要値５を有し、リソースＲ２を保持しＲ１を待つ。
３．ジョブＣは、必要値１を有し、Ｒ２を待つ。
【００１２】
表記上、これは、チェーンＣ（１）→Ｂ（５）→Ａ（４）と表すことができる。ここで、大文字はジョブを表し、カッコ内の数はそれらのジョブの「必要値」を表し、符号「→」（チェーンにおける「リンク」）は、この符号の左側のジョブがこの符号の右側のジョブによって保持されるリソースを待っていることを示す。このため、上述のチェーンは、必要値１のジョブＣが、必要値５のジョブＢによって保持されるリソースを待っており、ジョブＢが、必要値４のジョブＡが保持するリソースを待っていることを意味する。
【００１３】
このように「必要度」ファクタを用いると、明らかでない場合があるいくつかの利点が与えられる。第１に、これは、上述のＢのような作業の支援を回避する。なぜなら、我々は、Ｂが別のリソースを待っていることを理解し、このため、よくても無益であり、最悪の場合には無関係の競合する作業に有害であるアクションを回避する。第２に、これによって、システム・リソース割り当て装置に、それ以外の場合よりも、不明確ではあるが限定された時間のみでなく、Ａを支援することができる知識を与える。従来の実施は、チェーンを無視し、ある限られた時間期間、ＡおよびＢの双方を「重要」として扱うが、本発明では、Ａが実際に必要値１を有すること、すなわち、Ｃが待機している限り「最も重要である」ことが理解される。第３に、これによって、システム・リソース割り当て装置に、それが望む場合、チェーンの頭部における保持者（複数の保持者）を支援しないようにすることができる知識を与える。これは、例えば、ネットワーク内の最高必要度の作業が現在の保持者である場合である。
【００１４】
この本発明の第１の態様は、単一のシステム上で、または複数のかかるシステムを含むシステム・クラスタにおいて実施することができる。リソース・クラスタを識別する本発明の変形は、特に、マルチシステム実施における使用に適しており、これは、以下で述べるように、ローカル・コンテンション・データのサブセットのみの交換を必要とする。
【００１５】
本発明の別の態様は、本出願の主題であり、多数システム間のリソース割り当てを管理し、同時に、コンテンション状態にあるマルチシステム・リソースの数のオーダーＯ（ｎ）で極めて少量のデータを通過させるためのプロトコルが意図される。
【００１６】
本発明の他の態様は、上述の単一システムの本発明の態様を組み込んでおり、複数のシステムを含むシステム・クラスタにおいてリソースに対するアクセスについてのユーザ間のコンテンションを管理するための方法および装置が意図される。ユーザの各々が割り当てられた必要値を有し、アクセスを求めているリソースの保持者または待機者のいずれかとなることができる。本発明のこの態様によれば、かかる各システムは、ローカル・システムとして動作し、ローカル・システム上のコンテンションに基づいて、リソースをローカル・クラスタにグループ化することを示し、各ローカル・クラスタごとに、ローカル・クラスタにおける１つ以上のリソースの必要値を示す、ローカル・クラスタ・データを保存する。また、各システムは、システム・クラスタにおける遠隔システムとして動作する別のシステムから、遠隔システム上のコンテンションに基づいてリソースを遠隔クラスタにグループ化することを示し、各遠隔クラスタごとに遠隔クラスタにおける１つ以上のリソースの必要値を示す、遠隔クラスタ・データを受信する。各ローカル・システムは、ローカル・クラスタ・データおよび遠隔クラスタ・データを組み合わせて、システム間のコンテンションに基づいてリソースを複合クラスタにグループ化することを示し、各複合クラスタごとに複合クラスタにおける１つ以上のリソースの必要値を示す、複合クラスタ・データを生成する。そして、各ローカル・システムは、この複合クラスタ・データを用いて、複合クラスタにおいてローカル・システム上のリソースの保持者を管理する。
【００１７】
好ましくは、ローカル、遠隔、および複合クラスタ・データは、対象のクラスタ内のいずれかのリソースの最高必要度の待機者の必要値を示す。複合クラスタ内におけるローカル・システム上のリソースの保持者を管理するには、他のいずれかのリソースを待機していないかかる保持者を識別し、かかる保持者に、その必要値が少なくとも対応する複合クラスタにおけるいずれかのリソースの最高必要度の待機者のものであるかのように、システム・リソースを割り当てる。
【００１８】
好ましくは、ローカル・システム上のユーザがリソースの１つを保持すると共にリソースの他のものを待機している場合に、各ローカル・システムは、１対のリソースを共通ローカル・クラスタに割り当て、ローカル・システム上のユーザに関してリソースのコンテンション・ステータスの変化の通知の受信に応答して、ローカル・クラスタ・データを更新する。また、各ローカル・システムは、いずれかの更新を含むそのローカル・クラスタ・データを遠隔システムに更新し、これは、送信されたクラスタ・データを受信側システムに対する遠隔クラスタ・データとして扱い、次いで、これに応じてそれらの複合クラスタ・データを更新する。送信されたローカル・クラスタ・データは、リソースと、ローカル・システム上のコンテンションに基づいてリソースを割り当てるクラスタと、リソースのためのローカル・システム上の必要値とを示す。
【００１９】
クラスタ内の関与する各リソース・マネジャ・インスランスからの部分データ（全リソース・トポロジではない）および「必要度」の尺度を用いて、各システムは、個別に、リソースについての最高必要度の待機者（「上述の全て」間のリソースの推移的終了におけるいずれかの待機者を含む）が、チェーンの頭部におけるリソースのいずれかの保持者よりも必要度が高いか否かを理解することができる。そして、システムは、かかる保持者（複数の保持者）が、それらの必要度の尺度が最高必要度のブロック化作業部分よりも必要度が高いかのようにリソースを割り当てることができる。
【００２０】
プロトコルは、各システムから保持者および待機者の全リストの代わりに、リソースごとの１組の情報のみを回すので、どのシステムも、クラスタ間のコンテンションの完全なビューを有しない。データ自体は、クラスタに固有のリソース名と、送信側システム上の最高必要度の待機者の必要値と、送信側システムに固有のトークンとのみから成る。後者のトークンが２つのリソースについて一致した場合、それらの管理は統合しなければならない（トークンは、送信側システムのローカル・データのみに基づいて割り当てられる）。また、トポロジにおける作業部分がコンテンション状態にない他のリソースを保持するとしても、プロトコルは、コンテンション状態にあるリソースに関するデータのみを送信する。送信側システム・クラスタ情報は、様々な方法で符号化することができる。このため、送信側システムのローカル・コンテンションのみに基づいてトークンを送信するのではなく、ローカル・システムは、好適な実施形態では、非トリビアルなクラスタ割り当て（すなわち２つ以上のリソースを含むクラスタに対する割り当て）がローカルまたは遠隔のどちらの情報に基づくかの指示と共に、遠隔コンテンションに基づいてクラスタ名を送信することができる。
【００２１】
本発明は、好ましくは、コンピュータ・オペレーティング・システムの一部として、またはかかるオペレーティング・システムと共に動作する「ミドルウエア」ソフトウエアとして、実施される。かかるソフトウエア実施は、本発明の方法ステップを実行するためにハードウエア機械によって実行可能な命令のプログラムの形態の論理を含む。命令のプログラムは、半導体、磁気、光学、または他のストレージ技術を用いた１つ以上のボリュームを含むプログラム・ストレージ・デバイス上に具現化することができる。
【発明を実施するための最良の形態】
【００２２】
図１は、本発明を組み込んだコンピュータ・システム・クラスタ１００を示す。クラスタ１００は、いずれかの適切なタイプの相互接続１０４によって結合された個々のシステム１０２（Ｓｙ１、Ｓｙ２、Ｓｙ３）を含む。例示的な３つのシステムを示すが、本発明は、システムのいずれかの特定の数には限定されない。クラスタ１００は、１つ以上のグローバルまたはマルチシステム・リソース１０６を有し、これらは様々なシステムからの要求によって争われる。
【００２３】
クラスタの各システム１０２は、別個の物理的な機械または１つ以上の物理的な機械の別個の論理区分のいずれかを含むことができる。各システムは、オペレーティング・システム（ＯＳ）１０８を含み、これが、本発明の機能を実行することに加えて、システム・サービスを提供しシステム・リソースの使用を管理するという通常の機能を実行する。本発明は、いずれかの特定のハードウエアまたはソフトウエア・プラットフォームに限定されないが、好ましくは、各システム１０２は、ＩＢＭのｚＳｅｒｉｅｓ（商標）サーバまたはかかるサーバの論理区分上で実行するＩＢ  ｚ／ＯＳオペレーティング・システムのインスタンスを含む。
【００２４】
各システム１０２は、マルチシステム・リソース１０６に対するアクセスについて互いに争う１つ以上のリクエスタ１１０、および、任意選択的に、同一システム上のリクエスタにのみ利用可能なローカル・リソース１１２を含む。リクエスタ１１０は、リソース１０６または１１２に対するアクセスを争ういずれかのエンティティを含むことができ、システム・リソースを割り当てる目的で単一のエンティティとして扱われる。
【００２５】
（リクエスタ１１０に割り当てられるシステム・リソースは、リクエスタ間のコンテンションの対象であるリソース１０６および１１２とは区別しなければならない。システム・リソースは、通常リクエスタ自体に透明な方法でリクエスタ１１０に割り当てられて、スループットまたは応答時間等の何らかの性能尺度を改善する。一方、リソース１０６および１１０は、それらの実行の一部としてリクエスタによって明白に要求される。それらを区別することが必要である場合、後者のリソース・クラスは、時に、「逐次化リソース」等の言葉を用いて称する。）
【００２６】
各オペレーティング・システム１０８は、１つ以上のリソース・マネジャ１１４および作業負荷マネジャ（ＷＬＭ：workload manager）１１６を含めて、本発明の対象のいくつかのコンポーネントを含む。各リソース・マネジャ１１４は、それが制御するリソース１０６または１１２について、競合するリクエスタ１１０間のコンテンションを管理するため、保持者として１つ以上のかかるリクエスタによるそのリソースへのアクセスを与え、リソースが利用可能になるまで残りのリクエスタを待機者のプールに配置する。本発明は、いずれかの特定のリソース・マネジャに限定されないが、１つのかかるリソース・マネジャ（マルチシステム・リソース１０６のために用いられる）は、ｚ／ＯＳオペレーティング・システムの大域資源逐次化（ＧＲＳ）コンポーネントとすることができる。これは、ＩＢＭ刊行物z/OS MVS Planning: Global Resource Serialization、ＳＡ２２−７６００−０２（２００２年３月）のような参考文献に記載されている。これは、引用により本願にも含まれるものとする。更に、リソース・マネジャ１１４は、（ＧＲＳがｚ／ＯＳの一部であるので）オペレーティング・システム１０８の一部として示すが、オペレーティング・システムから独立して他のリソース・マネジャ（ＩＲＬＭ等）が存在する場合もある。
【００２７】
作業負荷マネジャ（ＷＬＭ）１１６は、「必要」値に基づいて、システム・リソースを、作業単位（アドレス空間、エンクレーブ（enclaves）等とすることができる）に割り当てる。この必要値は、その作業単位（またはそれが属するサービス・クラス）に割り当てられており、ある意味で、処理している他の作業単位に対するその作業単位の相対的な優先度を反映する。本発明は、いずれかの特定の作業負荷マネジャに限定されないが、１つのかかる作業マネジャは、ＩＢＭ  ｚ／ＯＳオペレーティング・システムの作業負荷管理コンポーネントであり、これは、ＩＢＭ刊行物z/OS MVS Planning: Workload Management、ＳＡ２２−７６０２−０４（２００２年１０月）、およびz/OS MVSProgramming: Workload Management Services、ＳＡ２２−７６１９−０３（２００２年１０月）のような参考文献に記載されている。これらは、引用により本願にも含まれるものとする。かかる作業負荷管理コンポーネントは、ＩＢＭ  ｚ／ＯＳオペレーティング・システムのシステム・リソース・マネジャ（ＳＲＭ：system resources manager）コンポーネントと共に機能する。これは、ＩＢＭ刊行物z/OS MVS Initialization and Tuning Guide、ＳＡ２２−７５９１−０１（２００２年３月）の、特に第３章（３−１から３−８４ページ）に記載されている。これは、引用により本願にも含まれるものとする。これらのコンポーネントがインタラクトする具体的なの方法は本発明の部分ではないので、双方のコンポーネントは、図１において「ＷＬＭ」と標示したボックス１１６によって示されると想定する。
【００２８】
必要値をユーザに割り当てる具体的な方法も、割り当てた必要値に基づいてシステム・リソースをユーザに割り当てる方法も、本発明の部分ではない。双方のために、当技術分野において周知の多数の技法のいずれも用いることができる。好ましくは、必要値は、システム・クラスタ全体を通して同様の意味を有するものとする。図示する実施形態では、これはアクティブＷＬＭポリシに基づいて計算された動的な値であり、リソース・グループの限界および重要性を単一の量へと統合し、これはシステム全体において安全に比較することができる。順序付けは任意であるが、この記載では、数が小さい方が必要または優先度が高いことを表すので、の必要値１を有するユーザは、必要値５を有するユーザよりも「必要度が高い」。
【００２９】
図２から５は、システム・クラスタ１００においてリソース１０６および１１２間で生じ得る様々なコンテンション・チェーンを示す。これらのチェーンは、より正式には有向グラフとして知られるが、本明細書中ではチェーンの用語を用いる。これらのチェーンにおいて、矢印で示す各リンクは、ユーザ（矢印の尾部のノードによって表される）は、別のユーザ（矢印の頭部のノードによって表される）が保持するリソースを待っているという関係を表す。かかる関係の「推移的終了」は、チェーンのいずれかのノードを伴う全てのかかる関係を含むことによって形成されるチェーンである。このため、矢印を追っていくと、全てのノードが最終的に示す保持者は、コンテンションの状態にあるリソースを待っておらず、従ってチェーンの頭部にある。（チェーンが２つ以上の頭部を有することができるか否かは、以下で図４の説明において論じる。）
【００３０】
図２は、背景技術および課題を解決するための手段において記載したコンテンションの状況を示す。ユーザＣは、ユーザＢが保持するリソースＲ２を待っており、ユーザＢは、ユーザＡが保持するリソースＲ１を待っている。本明細書中で開示するように、ユーザＡは、保持者であるが待機者でなく、従ってチェーンの頭部にあり、その必要値が少なくとも待機者ＢおよびＣのうち必要度が高い方のものであるように、システム・リソースを割り当てられる。なぜなら、その待機者は双方とも、ＡがリソースＲ１で終わることで利益を得るからである。また、ユーザＢは保持者でもあるが、この優先的な割り当てを受けない。なぜならこれはリソースを待っており、従って実行していないからである。このため、この時点で、もっと多くのリソースをＢに割り当てることには意味がない（しかし、後にＢが保持者としてリソースＲ１を取得すると、その可能性がある）。
【００３１】
図２に示すコンテンション状況は直線チェーンであり、各ユーザは単一のユーザが保持するリソースを保持するかもしくは待機するかまたはその双方である。しかしながら、一般に、コンテンション・チェーンは分岐する可能性があるので、単一のユーザが、多数ユーザが待機するリソースを保持しているか、または、多数ユーザが保持するリソースを待っている場合がある。また、一部のリソースは、共有アクセスを要求され、多数の同時保持者が存在し得ることがある。
【００３２】
図３は、第１のタイプの分岐を有するコンテンション状況を示し、図２に示す状況と異なるのは、ここでは追加のユーザＤがユーザＢによって保持されるリソースＲ３を待っている点である。ここで、ユーザＡには、その必要値が少なくとも待機者Ｂ、Ｃ、およびＤのうち最高の必要度のものであるように、システム・リソースが割り当てられる。なぜなら、これらの待機者は全て、ＡがリソースＲ１で終わることで利益を得るからである。
【００３３】
図４は、双方のタイプの分岐を有するコンテンション状況を示し、図２に示す状況と異なるのは、ここではユーザＣがユーザＤによって制御される追加のリソースＲ３を待っており、ユーザＤがユーザＡによって制御されるリソースＲ４を待っている点である。この場合も、ユーザＡには、その必要値が少なくとも待機者Ｂ、Ｃ、およびＤのうち最高の必要度のものであるように、システム・リソースが割り当てられる。なぜなら、これらの待機者は全て、ＡがリソースＲ１で終わることで利益を得るからである。
【００３４】
最後に、図５は、第２のタイプの分岐を有するコンテンション状況を示し、図２に示すチェーンと異なるのは、ここではユーザＣがユーザＤによって保持されるリソースＲ３も待っており、ユーザＤはユーザＥによって保持されるリソースＲ４を待っている点である。理論的には、これは、各々が１つの頭部を有する２つの部分的に重複するチェーンとして分析することができる。一方のチェーンがＣ→Ｂ→Ａであり、他方がＣ→Ｄ→Ｅである。第１のチェーンでは、ユーザＡに、その必要値が少なくとも待機者ＢおよびＣのうち必要度が高い方のものであるようにシステム・リソースが割り当てられ、第２のチェーンでは、ユーザＥに、その必要値が少なくとも待機者ＣおよびＤのうち必要度が高い方のものであるようにシステム・リソースが割り当てられる。
【００３５】
これを要約すると、図６を参照して、理想的な実施において、最初に、ユーザのチェーンの頭部において、待機者でないユーザを識別する。チェーンにおいて次のユーザを有する各ユーザは、次のユーザが待っているリソースを保持している（ステップ３０２）。図５において、これは、ユーザＡ〜Ｃから成るチェーンではユーザＡであり、ユーザＣ〜Ｅから成るチェーンではユーザＥである。次いで、チェーンの頭部のユーザに、その必要値が当該チェーンにおいて少なくとも最高の必要度の待機者のものであるように、システム・リソースを割り当てる（ステップ３０４）。すなわち、チェーンの頭部におけるユーザのものより大きい必要値を有する最高の必要度の待機者があったら、そのユーザには、その必要値がそのユーザのものより大きい場合に、かかる待機者の必要値に基づいて、システム・リソースが割り当てられる。
【００３６】
２つのチェーンとしてのこの処理では、ユーザＡのリソース割り当ては、ユーザＤの必要値に依存しない。なぜなら、ユーザＤの分岐（矢印の方向に進む）は、ユーザＡに戻らず、ユーザＤはこのため、ユーザＡを有利にすることから利益を得る立場でないからである。同様の理由で、ユーザＥのリソース割り当ては、ユーザＢの必要値に依存しない。従って、好適な実施形態では、これらのチェーン（またはこれらのチェーンにおけるリンクを構成するリソース）は、２つの別個のリソース・クラスタとして分析される。すなわち、第１はリソースＲ１〜Ｒ２を含み、第２はリソースＲ３〜Ｒ４を含む。第１のクラスタでは、その第１のクラスタにおけるリソース（Ｒ１およびＲ２）のいずれかについて、ユーザＡに、その必要値が少なくとも待機者（ＢおよびＣ）のうち必要度が高い方のものであるように、システム・リソースを割り当てる。同様に、第２のクラスタでは、その第２のクラスタにおけるリソース（Ｒ３およびＲ４）のいずれかについて、ユーザＥに、その必要値が少なくとも待機者（ＣおよびＤ）のうち必要度が高い方のものであるように、システム・リソースを割り当てる。
【００３７】
上述の例の全てにおいて、コンテンション・チェーンは非周期性である。これは、それらの矢印の方向に沿ってリンクを追うことによって閉鎖経路を形成することができないことを意味する。もしもかかる閉鎖経路があれば、リソース・デッドロックが生じる。これを遮断するには、このデッドロックに伴うユーザの１つ以上を終了させるしかない。
【００３８】
ここで、マルチシステム実施の詳細に移る。図７は、いくつかのシステム上でのトランザクションおよびリソース間の典型的なコンテンション状況を示す。図において、システムＳｙ１上のトランザクションＴｘＡ（必要値１）が、システムＳｙ２上のトランザクションＴｘＢ（必要値２）およびＴｘＤ（必要値４）によって保持されているリソースＲａを待っている。そして、システムＳｙ２上のトランザクションＴｘＢは、システムＳｙ３上のトランザクションＴｘＣ（必要値３）によって保持されるリソースＲｂを待っている。システムＳｙ３上のトランザクションＴｘＥ（必要値５）も同様である。
【００３９】
この例では、システムＳｙ１〜Ｓｙ３がコンテンションをどのように管理するかを例示するものとしてシステムＳｙ２を見る。本発明の１つの態様によれば、システムＳｙ２はクラスタにおけるコンテンションの完全な全体的ピクチャを保存も維持もしないが、以下のテーブルに示すように、かかるコンテンション情報のサブセットを保存および維持する。
【表１】
2006512688.tif 000003
【００４０】
上のテーブルに示すように、システムＳｙ２は、保持者または待機者のいずれかとしてリソースを争っているそのローカル・トランザクションＴｘＢおよびＴｘＤについての完全な１組のコンテンション・データ（「ローカル・システム情報」）を保存する。ローカル・トランザクションがコンテンション状態にあるかかるリソースごとに、Ｓｙ２は、それらの固有の「必要」値を含めて、ローカル保持者および待機者を追跡する。また、システムＳｙ２は、リソースＲａおよびＲｂを共通クラスタＣａｂに割り当てている。なぜなら、少なくとも１つのローカル・トランザクション（ＴｘＢ）が、ある要求されたリソース（Ｒａ）の保持者であると共に別の要求されたリソース（ＴｘＢ）の待機者であるからである。
【００４１】
上のテーブルに示した、または他の方法でＷＬＭのローカル・インスタンスによって追跡された（そのようにそれを保存することによって、または必要に応じて他のデータからそれを導出することによってのいずれかで）データは、ローカル・クラスタ・データ、遠隔クラスタ・データ、および複合クラスタ・データを含む。ローカル・クラスタ・データは、ローカル・システム上のコンテンションに基づいてリソースをローカル・クラスタにグループ化することを示し、かかるローカル・クラスタごとに、ローカル・クラスタにおけるいずれかのリソースの最高必要度の待機者の必要値を示す。同様に、遠隔クラスタ・データは、特定の遠隔システムについて、遠隔システム上のコンテンションに基づいてリソースを遠隔クラスタにグループ化することを示し、かかる遠隔クラスタごとに、遠隔クラスタにおけるいずれかのリソースの最高必要度の待機者の必要値を示す。最後に、複合クラスタ・データは、対応するローカルおよび遠隔データを組み合わせることによって生成され、システム間のコンテンションに基づいてリソースを複合クラスタにグループ化することを示し、かかる複合クラスタごとに、複合クラスタにおけるいずれかのリソースの最高必要度の待機者の必要値を示す。
【００４２】
上のテーブルでは、「ローカル・システム情報」の見出しの下にある項目は、ローカル・クラスタ・データを表す。なぜなら、それらは、コンテンション下のリソースを待っているかまたはリソースを保持しているローカル・ユーザの意味でローカルなコンテンションのみに基づいているからである。あるリソースについて最高必要度のローカル待機者の必要値は、「ローカル・システム情報」の下の「待機者」欄を見ることによって確認することができる。このため、リソースＲａについて、ローカル待機者は存在しない（従って、「最高必要度」のローカル待機者は存在しない）が、リソースＲｂでは、最高必要度の待機者（ＴｘＢ）は必要値２を有する。ローカル・コンテンションに基づいてリソースをクラスタにグループ化することは、テーブルには明白に示さないが、ローカル・ユーザがあるリソースを保持するが他のものを待っているリソース・エントリ対を探すことによって得られる。このため、上のテーブルでは、リソースＲａの保持者およびリソースＲｂの待機者としてのユーザＴｘＢのリスト化が意味するのは、リソースＲａおよびＲｂをローカル・コンテンション・データに基づいて共通クラスタに割り当てるということである。
【００４３】
同様に、「遠隔待機者情報」の見出しの下の項目は、遠隔クラスタ・データを示す。なぜなら、それらは特定の遠隔システム上のコンテンションにのみ基づくからである。「システム名」欄において、リソースについてリスト化された各遠隔システムごとに、最高必要度の待機者の必要値を、隣接する「ＮＱＯ」欄に示す。特定の遠隔システムからのコンテンション・データに基づいてリソースをクラスタにグループ化することは、上のテーブルには示さないが、ローカルＷＬＭインスタンスによって追跡されるので、これを、ローカル・クラスタ割り当て情報と組み合わせて、複合クラスタ割り当てを得ることができる。クラスタの組み合わせは、直接的に行われる。このため、第１のシステムがリソースＡおよびＢを（そのローカル・コンテンション・データに基づいて）共通クラスタに割り当てる場合、第２のシステムは同様にリソースＢおよびＣを共通クラスタに割り当て、第３のシステムはリソースＣおよびＤを共通クラスタに割り当て、この結果、複合クラスタはリソースＡ、Ｂ、Ｃ、およびＤを含む。
【００４４】
一方、最初の欄（「リソース・クラスタ」）は、複合クラスタ・データを表す。なぜなら、そのリソースのクラスタへの割り当ては、ローカル・クラスタ・データおよび遠隔クラスタ・データの双方に基づくからである。最後の欄（「ＮＱＯ」）は、同様に複合クラスタ・データを表す。なぜなら、リスト化された必要値は、全システム中でリソースについての最高必要度の待機者のものだからである（ローカル・システムに報告されたように）。
【００４５】
システムＳｙ２は、上に示した表の形態でコンテンション・データを保存することができるが、より典型的には、かかるデータを多数のデータ構造に分散させて、操作の容易さを最適化する。これについては、以下で更に述べる。
【００４６】
図８は、ローカル・リソース・マネジャからのコンテンション通知に応答して、ＷＬＭのローカル・インスタンスが実行する全体的な手順５００を示す。特定のステップ・シーケンスを説明するが、各ステップを実行する場合に必要な入力データが利用可能である限り、シーケンスは変更することができる。
【００４７】
手順５００が開始するのは、ＷＬＭインスタンスがリソースのコンテンション状態の変化の通知をローカル・リソース・マネジャから受信し、それがローカル・ユーザに関連する場合である。かかる変更は、以下のいずれかを表すことができる。
【００４８】
１．ローカル・ユーザが別のユーザによって保持されるリソースの待機者になった。
２．ローカル・ユーザがもはやリソースの待機者ではない。この理由は、それが保持者としてリソースを取得したからか、または、それがもはや保持者または待機者のいずれかとしてリソースに関心がなくなったからである（おそらく、これが終了し、従ってもはや存在しないからである。これについては以下の例で説明する）。
３．ローカル・ユーザによって保持されるリソースが現在コンテンションの状態にある。
４．ローカル・ユーザによって保持されるリソースがもはやコンテンションの状態にない。
【００４９】
ローカル・リソース・マネジャからの通知は、リソースと同様に、ローカル保持者および待機者を識別する。好適な実施形態では、ＷＬＭは、別個には示さないＳＲＭコンポーネントから、これらの保持者および待機者の各「必要値」を取得する（それらの固有の必要値であり、本発明に従って変更した必要値ではない）。しかしながら、このデータの特定のソースは、本発明の部分を形成しない。
【００５０】
リソース・マネジャ・インスタンスからのかかる通知の受信に応答して、ＷＬＭのローカル・インスタンスは、まず、対象のリソースについてのローカル・コンテンション・データを更新する（ステップ５０４）。かかる更新は、ローカル・システム上で新たにコンテンション状態になったリソースのための新しいエントリの生成、ローカル・システム上ですでにコンテンション状態にあるリソースのための既存のエントリの変更、またはローカル・システム上でもはやコンテンション状態にないリソースのための既存のエンティティの消去を含むことができる。このローカル・コンテンション・データは、リソースを保持または待機しているいずれかのローカル・ユーザの識別と共に、かかるユーザの「必要値」も含む。
【００５１】
ローカル・コンテンション・データを更新した後、ＷＬＭのローカル・インスタンスは、必要な場合、リソースのクラスタ割り当てを更新する（ステップ５０６）。デフォルトでは、リソースは、メンバとしてそれ自身のみを含むトリビアルなクラスタに割り当てられる。かかる割り当てが、ローカル・コンテンション・データまたは遠隔コンテンション・データのいずれかによって指示される場合、リソースは、少なくとも１つの他のリソースを含む非トリビアルなクラスタに割り当てられる。ローカル・コンテンション・データによって、同じローカル・ユーザがリソースのうちあるものを保持するが他のものを待っていることが示される場合、すなわち、そのリソースが他のリソースを待っているユーザによって保持されるか、または他のリソースを保持しているユーザによって待たれていることが示される場合、リソースは、そのデータに基づいて、別のリソースを含むクラスタに割り当てられる。遠隔コンテンション・データデータによって、少なくとも１つの遠隔システムが、その遠隔システムにローカルなコンテンション・データに基づいて２つのリソースを共通クラスタに割り当てたことが示される場合、リソースは、そのデータに基づいて、別のリソースを含むクラスタに割り当てられる。このクラスタ割り当てステップは、従って、以下を含む場合がある。（１）リソースのためのクラスタ割り当てを不変のままとする、（２）変更したローカル・コンテンション・データおよびいずれかの既存の遠隔コンテンション・データがかかる割り当てを指示する場合、リソースを非トリビアルなクラスタに新たに割り当てる、または（３）変更したローカル・コンテンション・データおよびいずれかの既存の遠隔コンテンション・データがもはやかかる割り当てを指示しない場合、既存のクラスタを分解する。リソースのクラスタ割り当てが変更されると、この変更によって影響を受ける他のリソースのためのクラスタ情報は、この時点で同様に変更される。
【００５２】
同時に、ＷＬＭのローカル・インスタンスは、リソースのローカル・コンテンション・データのみに基づいているリソースの帰属「必要」値を更新する（ステップ５０８）。この帰属必要値は、リソースのローカル・コンテンション・データが示すように、リソースのいずれかのローカル待機者の必要値のうち最大のものである。このステップは、クラスタ割り当てステップの後に続くものとして示すが、ステップの順序は重要でない。なぜなら、どのステップも他のステップの結果を用いないからである。
【００５３】
クラスタ割り当ておよびリソースの帰属必要値を更新した後のある時点で、ＷＬＭのローカル・インスタンスは、その複合クラスタ・データを更新する。これは、以下を含む。（１）ローカルおよび遠隔コンテンション・データの双方に基づいた、リソースの帰属必要値（上のテーブルにおける「ＮＱＯ」）、（２）ローカルおよび遠隔コンテンション・データの双方に基づいた、リソースの複合クラスタへのグループ化、（３）全体としてのリソース・クラスタの帰属「必要」値（ステップ５１０）。最後に挙げたものは、単に、複合クラスタを形成するリソースのいずれかの必要値のうち最大のものであり、ここで、必要値は、クラスタを形成するリソースのための遠隔およびローカル・コンテンション・データに基づいている。
【００５４】
次いで、ＷＬＭのローカル・インスタンスは、その更新したローカル・コンテンション・データの要約を、クラスタにおける他のシステムに同報通信する（ステップ５１２）。このデータ要約は以下を含む。
１．ローカル・システム名。
２．リソース名。リソースがマルチシステム・リソースである場合、リソース名は、クラスタ中で認識されるようなリソースの実際の名前である。リソースがローカル・リソースである場合、リソース名は、実際のローカル・リソース名のための「プロキシ」として機能する総称のローカル・リソース名である。これについては、以下の例２において説明する。
３．リソースを割り当てるクラスタを識別するクラスタＩＤ。この値は、厳密にはローカルである。受信側システムは、この値を比較して、２つのリソースが送信側システム上の同一クラスタに属するか否かを調べるが、この値の構造または内容に関していかなる想定も行わない。以下の例では、クラスタ名を、クラスタにおけるマルチシステム・リソースの連結として与え、純粋に簡略記憶デバイスとして、読み取り側の理解を容易にする。しかしながら、好適な実施形態では、「クラスタ名」は、実際には不明瞭な「クラスタＩＤ」であり、受信側システムは、単に、同一の送信側システム上で生じる他のクラスタＩＤとの同等性について試験を行うことができるのみである。
４．送信側システムの「ローカル・システム情報」のみに基づいたリソースのための「必要値」、すなわち、リソースのための最高必要度のローカル待機者。これは、そのデータのみを考慮していた場合にその必要値がどうあるべきかこのシステムが考える表明方法と見なすことができる。リソースのためのローカル待機者が存在しない場合、ローカル必要値が存在しないことを示すダミー値を送信する。これについては、以下の例１において説明する。
５．送信側システムのいずれかのトランザクションがリソースをクラスタ内に含ませるか否か、すなわち、ローカル・コンテンション・データに基づいてリソースを非トリビアルなクラスタに割り当てているか否かの指示。これはブール値であるが、イエス／ノーではなく、この記載においてローカル／遠隔の値を与えられる。ローカルが意味するのは、（１）送信側システムが、あるリソースの待機者および別のリソースの保持者の双方である少なくとも１つのトランザクションを有すること、および（２）同じトランザクションがこのリソースの待機者または保持者のいずれかであること（このため、送信側システムは、トランザクション（複数のトランザクション）に接続したリソース・グループが１グループとして管理されることを必要とする）である。遠隔が意味するのは、送信側システムのローカル・データにおいて、リソースが非トリビアルなクラスタの一部であることを要求するものがないことを意味する。トリビアルなクラスタは、正確に１つのリソースを有し、常に「遠隔」の値を有してクラスタリング・コードを少し容易にする。
【００５５】
クラスタ再割り当てがあった場合、ＷＬＭは、その再割り当てによって影響を受ける他の各リソースごとに同様の情報を同報通信する。
【００５６】
最後に、ローカルＷＬＭインスタンスは、ローカル・ユーザの「必要」値に対していずれかの必要な調整を行う（ステップ５１４）。より具体的には、ＷＬＭは、あるリソースのローカル保持者であると共に別のリソースの待機者ではないもの（このため、コンテンション・チェーンの頭部にある）の「必要値」を調整し、これが、リソースを含むクラスタにおける最高必要度の待機者の固有の必要値に少なくとも一致するようにする。調整した値は、システム・リソースを保持者に割り当てるために実際に用いられる帰属「必要」値であり、そのユーザに割り当てられる（更に他のユーザに値を帰属するために用いられる）固有の必要値ではない。このため、特定の必要値を帰属させる理由がなくなると、ユーザに帰属した必要値は固有の必要値またはもっと小さい帰属必要値のいずれかに戻る。
【００５７】
図９は、全体的な手順６００を示し、遠隔システム上のＷＬＭインスタンスからの遠隔コンテンション・データの同報通信の受信（６０２）に応答して、ＷＬＭのローカル・インスタンスが実行する。この同報通信は、影響を受けた各リソースごとに、ステップ５１２の説明においてリスト化した情報を含む。
【００５８】
かかる通知の受信に応答して、ＷＬＭのローカル・インスタンスは、まず、対象のリソースの遠隔コンテンション・データを更新する（ステップ６０４）。ステップ５０４で説明したローカル・コンテンション・データの更新の場合と同様、かかる更新は、ローカル・システム上で新たにコンテンション状態になったリソースのための新しいエントリの生成、ローカル・システム上ですでにコンテンション状態にあるリソースのための既存のエントリの変更、またはローカル・システム上でもはやコンテンション状態にないリソースの既存のエンティティの消去を含むことができる。この遠隔コンテンション・データは、リソースの待機者を有するいずれかの遠隔システムの識別と共に、リソースについての遠隔システム上の最高必要度のかかる待機者の必要値を含む。
【００５９】
リソースのその遠隔コンテンション・データを更新した後、ステップ５１０において行ったのと同様に、ＷＬＭのローカル・インスタンスは、リソースのその複合クラスタ・データを更新する。ステップ５１０においてと同様、更新された複合クラスタは以下を含む。（１）ローカルおよび遠隔コンテンション・データの双方に基づいた、リソースのための帰属必要値、（２）ローカルおよび遠隔コンテンション・データの双方に基づいた、リソースの複合クラスタへのグループ化、および（３）ローカルおよび遠隔コンテンション・データに基づいた、全体としてのリソース・クラスタのための帰属「必要」値（ステップ６０６）。
【００６０】
最後に、ステップ５１４におけるように、ローカルＷＬＭインスタンスは、ローカル・ユーザの「必要」値に対していずれかの必要な調整を行うため、あるリソースのローカル保持者であると共に別のリソースの待機者ではないもの（このため、コンテンション・チェーンの頭部にある）の「必要値」を調整し、これが、リソースを含むクラスタにおける最高必要度の待機者の固有の必要値に少なくとも一致するようにする（ステップ６０８）。
【００６１】
詳細な例および状況は、以下の通りである。
【００６２】
例１（「単純な」推移的終了の場合）
この例は、システム間の推移的終了の場合である。２つ以上のリソースが関与する。あるリソースを保持する必要度の低いユーザを支援して、異なるリソースを待っている別の（必要度の高い）ユーザを動かす。トポロジはマルチシステムであり、同一リソースの保持者および待機者が異なるシステム上にある。
【００６３】
これは、同一リソース・クラスタにマルチシステム・リソースのみが含まれる場合に何が起こるかを示すので、「単純な」推移的終了の場合である。
【００６４】
この例では、表記は以下の通りである。各保持者および待機者はトランザクションであり（Ｔｘｎ、例えばＴｘＡ、ＴｘＢ）、ＮＱＯ（eNQueue Order）値を有する。ＮＱＯ値は、値が小さくなるほど必要度が高い（多くの支援を受けることに値する）ようになっている。各システムに付番し（Ｓｙ１、Ｓｙ２）、これらのシステムは全て同一の「システム・クラスタ」内にある。各リソースは小文字を有し（Ｒａ、Ｒｂ）、対象範囲においてマルチシステムである。各リソース・クラスタは、１つ以上の小文字を有し（Ｃａ、Ｃａｂ）、クラスタ内のリソースのリストを示す。リソースを得るための要求は、特に注記しない限り、排他的制御のためである。
【００６５】
イベントのシーケンスは、時間順に、以下の通りである。
【表２】
2006512688.tif 000004
【００６６】
ｔ＜６では、コンテンションが存在しないので、いずれのシステム上でもＷＬＭコンテンション・データは存在しない。
【００６７】
ｔ＝６では、コンテンションが生じる（Ｓｙ１：ＴｘＢはＲｂを要求し、ＴｘＣがそれを保持するので保留される）。この結果、Ｓｙ１は、
１．リソースＲｂのためのコンテンション追跡を開始する。
２．Ｒｂのみから成るリソース・クラスタを生成する。
３．Ｒｂのローカル待機者リストにＴｘＢを加える。
【００６８】
この時点で、Ｓｙ１の状態は以下の通りである。
【表３】
2006512688.tif 000005
【００６９】
Ｓｙ１が次にそのリソース・トポロジを再評価する場合、ＣｂのＮＱＯを計算する。
１．Ｓｙ１が知っているＲｂのトポロジに含まれる最高必要度のエンティティ（実際、この時点で１つのみ）はＴｘＢであるので、これは、ＲｂのＮＱＯとして、ＴｘＢのＮＱＯ（４）を用いる。
２．Ｃｂにおける全リソースについてＮＱＯを計算したので、これは、Ｃｂにおける全リソースＮＱＯの最高必要度のものとしてＣｂのＮＱＯを計算する。これによって、ＲｂからＣｂまでＮＱＯ４を伝搬させる。  
３．Ｒｂはマルチシステム・リソースであるので、Ｓｙ１はＲｂの情報をシステム・クラスタにおける他の全システムに同報通信する。上述のように、Ｒｂについて送信された情報は、システム名、リソース名、クラスタＩＤ、送信側システムの「ローカル・システム情報」のみに基づいたリソースのＮＱＯ、および、「ローカル」に送信された場合は送信側システムのトランザクションがリソースをクラスタ内に含ませることを示すブール値（ローカル／遠隔）を含む。
４．上述の説明に基づいて、送信されるデータは、Ｓｙ１、Ｒｂ、Ｃｂ、４、遠隔である。
【００７０】
この時点で、Ｓｙ１の状態は以下の通りである。
【表４】
2006512688.tif 000006
【００７１】
Ｓｙ２はこの情報を受信する。同時に、Ｓｙ２上で実行しているリソース・マネジャ・インスタンスは、ＲｂのコンテンションをＳｙ２に通知する。動作の順序は関係ないが、それらは先に記載した順序でリスト化される。コードにおける唯一の「秘訣」は、Ｓｙ２上のリソース・マネジャが競争に勝った場合、遠隔データが到着した際に、コードは、それがすでに等価のクラスタを構築したことを認識し、その既存データに遠隔情報を追加しなければならないことである。
【００７２】
Ｓｙ１から遠隔情報を受信した後、Ｓｙ２の状態は以下の通りである。
【表５】
2006512688.tif 000007
【００７３】
いったんＳｙ２のローカル・リソース・マネジャがＳｙ２にＲｂのコンテンションを通知すると、Ｓｙ１およびＳｙ２の状態は以下の通りである。    
【表６】
2006512688.tif 000008
【表７】
2006512688.tif 000009
【００７４】
ＲｂについてのＳｙ２のローカルＮＱＯが４であり、ＴｘＣのＮＱＯである５ではないことに留意すべきである。第１に、リソース保持者のＮＱＯ（複数のＮＱＯ）は、リソースのＮＱＯに影響を与えない。なぜなら、保持者が実行しているからである。ＷＬＭのポリシ調整コードは、すでにＮＱＯを自動的に用いている。第２に、Ｓｙ２はこの時点で、システム・クラスタ内のどこか他の所で、ＮＱＯ４のトランザクションが待機しているのを知っている。４は５よりも必要度が高いと規定されているので、ＲｂのＮＱＯは４以上の必要度を有しなければならない。
【００７５】
ｔ＝７では、別のリソース上でコンテンションが生じる（Ｓｙ２：ＴｘＡはＲａを要求し、ＴｘＢがそれを保持するので保留される）。図１０は、ｔ＝７の後のトポロジを示す。
【００７６】
また、リソースＲａはマルチシステム対象範囲を有するので、この結果、Ｒｂについて起こったのと同様のハンドシェーキングが生じる。この結果、以下の通りとなる。
【表８】
2006512688.tif 000010
【表９】
2006512688.tif 000011
【００７７】
いったんＳｙ１上のリソース・マネジャ・インスタンスがＳｙ１にＲａのコンテンションを通知すると、Ｓｙ１はＣａおよびＣｂをリンクして（新しい）クラスタＣａｂにする重要なステップを行う。Ｒａのコンテンションについて単に通知した後、有効な（しかしこれまでのところ不完全な）状態は、以下の通りである（これらが２つの別個のステップであるか１つの統合されたステップであるか、コード実施によって異なる。それらは別個に示す）。
【表１０】
2006512688.tif 000012
【００７８】
Ｓｙ１が次にそのトポロジを再評価する場合、これは、ローカル情報に基づいて、単一のトランザクション（ＴｘＢ）に２つの異なるリソース（ＲａおよびＲｂ）が関与することを知っており、従ってそれらのリソースの管理を統合しなければならない（換言すると、ＲａおよびＲｂは同一のリソース・クラスタＣａｂ内になければならない）。クラスタのＮＱＯは、そのメンバ・リソースのうち最高必要度のＮＱＯである（この場合は１）。
【表１１】
2006512688.tif 000013
【００７９】
ＲａおよびＲｂが共に管理されなければならないという「信号」は、コンテンション状態の１つ以上のリソースを保持していると共にコンテンション状態の１つ以上の他のリソースを待機している少なくとも１つのトランザクションの存在である。
【００８０】
そのトポロジのビューを再評価した後、Ｓｙ１（以前と同じ）は、そのビューをクラスタ内の他のシステムに同報通信する。
１．Ｓｙ１、Ｒａ、Ｃａｂ、ダミーＮＱＯ値、ローカル。
２．Ｓｙ１、Ｒｂ、Ｃａｂ、４、ローカル。
【００８１】
ダミーＮＱＯ値は、単に、ＷＬＭが生成可能であるものよりも必要度が低いものである。Ｓｙ１は、純粋にローカルなＮＱＯ値を有しない。なぜならこれはローカル待機者を有しないからであるが、これはそのローカル・データに基づいてＲａおよびＲｂを１つの単位として管理しなければならないという「バーチャル・メッセージ」を送信する必要がある。
【００８２】
Ｓｙ２は、データ（ＲａおよびＲｂを１つの単位として管理しなければならず、ＣａおよびＣｂをマージしなければならないことを意味する事実を含む）を統合し、以下を生成する。
【表１２】
2006512688.tif 000014
【００８３】
ここで、双方のシステムは、どちらも完全なトポロジのコピーを有しないとしても、問題の重要性について了解している（すなわち、最高必要度の待機者のＮＱＯ値）。
【００８４】
ｔ＝１０では、コンテンションはほぐれ始める（Ｓｙ２：ＴｘＣはＲｂを解放する）。Ｓｙ２のＲｂのビューは、ここで、遠隔データのみを含む。
【表１３】
2006512688.tif 000015
【表１４】
2006512688.tif 000016
【００８５】
ｔ＝１１では、Ｓｙ１上のリソース・マネジャ・インスタンスは、Ｒｂが利用可能であることを見出し、そのキュー上の第１の待機者にこれを与える（Ｓｙ１：ＴｘＢを再開しＲｂを取得する）。リソース・マネジャの待機キューはこの時点で空であるので、これはＷＬＭに通知して、Ｒｂのコンテンションが終わったことを示す。Ｓｙ１は、そのリソース・クラスタからＲｂを除去する。なぜなら、各システム内で、どの単一リソースも単一クラスタにのみ属することができるからである（しかし、タイミング・ウインドウのため、２つのシステムが異なるクラスタ内に同一リソースを有する場合がある）。
【表１５】
2006512688.tif 000017
【００８６】
平行して、Ｓｙ２上のリソース・マネジャ・インスタンスは、Ｒｂがもはやコンテンション状態にないことを知らされ（リソース・マネジャ実施に応じて、これはｔ＝１０の時に行われた可能性もある）、これは、また、そのリソース・トポロジからＲｂを除去する。
【表１６】
2006512688.tif 000018
【００８７】
ｔ＝１２では、解放されたリソースはもはやコンテンションの状態でないので、変化はない（Ｓｙ１：ＴｘＢはＲｂを解放する）。
【００８８】
ｔ＝１３では、コンテンションは完全にほぐれる（Ｓｙ１：ＴｘＢはＲａを解放する）。Ｓｙ１上のリソース・マネジャは、ＷＬＭに通知して、Ｒａのコンテンションの終了を伝える。
【表１７】
2006512688.tif 000019
【００８９】
ｔ＝１４では、Ｓｙ２はコンテンションの終了も見る（Ｓｙ２：ＴｘＡが再開され、Ｒａを取得する（コンテンションなし））。Ｓｙ２上のリソース・マネジャ・インスタンスは、ＷＬＭに通知して、Ｒａのコンテンションの終了を伝える。
【表１８】
2006512688.tif 000020
【００９０】
例２（ローカル・リソースによる推移的終了の場合）
この例は、別のシステム間推移的終了の場合である。２つ以上のリソースが関与する。異なるリソースを待っている（必要度の高い）ユーザを動かすため、あるリソースを保持する必要度の低いユーザを支援しなければならない。トポロジは、この場合もマルチシステムであり、同じリソースの保持者および待機者が異なるシステム上にある。更に、例１とは異なり、各システムは、純粋にローカルな（非マルチシステムの）リソース上で同一のトランザクションを伴うコンテンションを有する。これによって、マルチシステムおよび単一システム・リソースの双方が同一のリソース・クラスタに関与する場合に何が起こるかを示す。  
【００９１】
表記は例１と同じであるが、マルチシステム・リソースは大文字のＲ（Ｒａ、Ｒｂ）を用い、ローカル・リソースは小文字のｒ（ｒｃ、ｒｄ）を用いる。Ｒｌｏｃａｌ（＝ＲＬ）は、「遠隔システムに対して対象範囲においてローカルな何らかの未知の組のリソース」のためのプロキシ名である。実際の値は無関係であり、唯一の要件は、全ての参加者が値を了解し、いずれかの有効リソース名と衝突することが可能でないことである。
【００９２】
イベントのシーケンスは、時間順に、以下の通りである。
【表１９】
2006512688.tif 000021
【００９３】
ｔ＜８では、各システム上のコンテンション状態は例１と全く同じであり、従ってここでは説明しない。
【００９４】
ｔ＝８では、ローカル（非マルチシステム）リソースｒｌ（Ｓｙ１：ＴｘＳはｒｌを要求し、ＴｘＢがこれを保持するので保留される）でコンテンションが生じる。リソースｒｌは、Ｓｙ１のみの上でリソース・クラスタに統合される。ｒｌのＮＱＯは、ＴｘＳから、３であるが、クラスタＣａｂｌはＲａのためにいまだＮＱＯが１である。
【表２０】
2006512688.tif 000022
【００９５】
Ｓｙ１がそのクラスタのビューを同報通信する場合、これは直接ｒｌを同報通信しない。なぜなら、ＲａおよびＲｂは他のシステムに可視的であり得るクラスタ内の唯一のリソースであるからである。その代わり、これは、Ｓｙ１のローカル・リソースの全て（我々はｒｌのみと知っている）についてのプロキシ（Ｒｌｏｃａｌ）を同報通信する。
１．Ｓｙ１、Ｒａ、Ｃａｂｌ、ダミーＮＱＯ値、ローカル。
２．Ｓｙ１、Ｒｂ、Ｃａｂｌ、４、ローカル。
３．Ｓｙ１、Ｒｌｏｃａｌ、Ｃａｂｌ、３、ローカル。
【００９６】
このデータを受信し、そのトポロジを更新した後、Ｓｙ２はこれがその状態であると考える。
【表２１】
2006512688.tif 000023
【００９７】
ｔ＝９では、別のローカル・リソースが、他のシステム上のコンテンションを示す（Ｓｙ２：ＴｘＴはｒｊを要求し、ＴｘＡがそれを保持するので保留される）。図１１は、ｔ＝９の後のトポロジを示す。
【００９８】
Ｓｙ１に行ったのと同様の処理がＳｙ２について生じ、次いでＳｙ２はそのデータをＳｙ１に同報通信する。Ｓｙ２は以下を同報通信する。    
１．Ｓｙ２、Ｒａ、ＣａｂＬ、１、ローカル。
２．Ｓｙ２、Ｒｂ、ＣａｂＬ、ダミーＮＱＯ値、遠隔。
３．Ｓｙ２、Ｒｌｏｃａｌ、ＣａｂＬ、２、ローカル。
【００９９】
上述の同報通信では、Ｓｙ２上のローカル・リソースのためのプロキシの名前はクラスタ名によって自動的に認定される。なぜなら、下に示すように、プロキシは、全体としてのシステム・クラスタでなく各リソース・クラスタごとに規定されるからである。また、ＲａおよびＲｌｏｃａｌのための同報通信のみがブール値「ローカル」を含む。なぜなら、これら２つのリソースのみが、ローカル・データに基づいて共通のクラスタに割り当て可能だからである。
【表２２】
2006512688.tif 000024
【表２３】
2006512688.tif 000025
【０１００】
Ｓｙ２上のＲｌｏｃａｌの「遠隔待機者情報」に「Ｓｙ２、２」エントリを追加すること、またはＳｙ２上の「ローカル・システム情報．待機者」にダミー・トランザクションを追加することによって、全てのローカル・リソース・コンテンションを要約できない理由はない。上のテーブルは、この最適化なしに示す。上述の方法の１つによってＲｌｏｃａｌにローカル状態データを要約させることは、おそらく同報通信コードをもっと簡単にするであろう。そして、Ｒｌｏｃａｌは、マルチシステム対象範囲で生成することができ、同報通信における特別な場合は必要ない。明らかに特別な場合とする必要がある他の場合がある。実際、単にシステム当たり１つではなく、リソース・クラスタ当たり１つのＲｌｏｃａｌを可能としなければならない。
【０１０１】
ｔ＝１０では、コンテンションはほぐれ始める（Ｓｙ２：ＴｘＣはＲｂを解放する）。Ｓｙ２のＲｂのビューは、ここで、遠隔データのみを含む。
【表２４】
2006512688.tif 000026
【表２５】
2006512688.tif 000027
【０１０２】
ｔ＝１１では、Ｓｙ１上のリソース・マネジャ・インスタンスは、Ｒｂが利用可能であることを見出し、そのキュー上の第１の待機者にそれを与える（Ｓｙ１：ＴｘＢを再開しＲｂを取得する）。リソース・マネジャの待機キューはこの時点で空であるので、これはＷＬＭに通知して、Ｒｂのコンテンションが終わったことを示す。平行して、Ｓｙ２上のリソース・マネジャ・インスタンスは、Ｒｂがもはやコンテンションの状態にないことを知らされる（リソース・マネジャ実施に応じて、これはｔ＝１０の時に行われた可能性もある）。双方のシステムは、そのリソース・クラスタからＲｂを除去しなければならない。なぜなら、各システム内で、どの単一リソースも単一クラスタにのみ属することができるからである。２つのシステムは、タイミング・ウインドウのため一時的に、またはリソース・トポロジのため永久的に、同一の瞬間に異なるクラスタ内に同一のリソースを有する場合がある。３つ以上のシステムが関与する場合に、非対称トポロジの例が現れる。
【表２６】
2006512688.tif 000028
【表２７】
2006512688.tif 000029
【０１０３】
ｔ＝１２では、解放されたリソースはもはやコンテンション状態にないので、変化はない（Ｓｙ１：ＴｘＢはＲｂを解放する）。
【０１０４】
ｔ＝１３では、マルチシステム・コンテンションは完全にほぐれる（Ｓｙ１：ＴｘＢはＲａを解放する）。Ｓｙ１上のリソース・マネジャ・インスタンスは、ＷＬＭに通知して、Ｒａのコンテンションの終了を伝える。
【０１０５】
Ｓｙ１上のリソース・クラスタは、この時点で、ローカル・リソースおよびマルチシステム・コンテンションに関与する遠隔ローカル・リソースのためのプロキシのみから成るので、プロキシもクラスタから除去することができる。Ｓｙ２にＲａのコンテンションの終了が通知されたので、これはそのプロキシ・リソースをクラスタの一部として維持する。
【表２８】
2006512688.tif 000030
【表２９】
2006512688.tif 000031
【０１０６】
ｔ＝１４では、Ｓｙ２もコンテンションの終了を見る（Ｓｙ２：ＴｘＡは再開されＲａを取得する）。Ｓｙ２上のリソース・マネジャ・インスタンスはＷＬＭに通知して、Ｒａのコンテションの終了を伝える。
【表３０】
2006512688.tif 000032
【０１０７】
ｔ＝１５では、ＴｘＳでのローカル・リソース終了の１つでのコンテンション（Ｓｙ１：ＴｘＢはｒｌを解放する）が再開する。いったんリソース・マネジャがＳｙ１にｒｌのコンテンションが終わったことを通知すると、Ｓｙ１のトポロジは再び空になる。
【０１０８】
ｔ＝１７では、コンテンションの最後が終了し（Ｓｙ２：ＴｘＡはｒｊを解放する）ＴｘＴが再開する。いったんリソース・マネジャがＳｙ２にｒｌのコンテンションが終わったことを通知すると、Ｓｙ２のトポロジは再び空になる。
【０１０９】
例３：クラスタの分解（ＢｒｅａｋＣｌｕ１）
この例は、関与するリソースのいずれかについてのコンテンションの終了なしで、リソース・クラスタをより小さいクラスタに分解することを含む。ＲａおよびＲｂをリンクするトランザクションは取り消されるが、各リソースは他の待機者を有するので、双方のリソースはその後まだコンテンション状態にある。表記は例１と同様である。
【０１１０】
イベントのシーケンスは、時間順に、以下の通りである。
【表３１】
2006512688.tif 000033
【０１１１】
ｔ＜４では、コンテンションが存在しないので、いずれのシステム上でもＷＬＭコンテンション・データは存在しない。
【０１１２】
ｔ＝４およびｔ＝７間で生じるイベントは、先の例においてカバーされている。図１２は、ｔ＝７後のトポロジを示す。この時点での状態データは以下のように見える。
【表３２】
2006512688.tif 000034
【表３３】
2006512688.tif 000035
【０１１３】
トランザクションＴｘＤがｔ＝８で終了すると（どんな理由であっても）、各システム上のリソース・マネジャ・インスタンスは、ＴｘＤが有する残っている全ての待機要求を除去し（Ｒａ）、それが保持する全てのリソースを解放する（Ｒｂ）。いったんＷＬＭにこれらのトポロジ変更が通知されると、Ｓｙ１は、リソース・クラスタＣａｂが２つの断片（ＣａおよびＣｂ）に分解されることを知っている。これを知っている理由は、その２つがリンクすることをＳｙ１がローカルに決定したからであり（更に、これがもはやローカルに真でないことを理解することができる）、遠隔システムのどのデータも、それらをリンクしなければならないことを示さない。しかしながら、双方のリソースはいまだコンテンション状態にある。次にＳｙ１がそのトポロジ・データを同報通信する時、Ｓｙ２上の「Ｓｙ１：Ｒａ、Ｒｂリンク」データを除去し、Ｓｙ２もそのトポロジを更新する。リソース・マネジャ・インスタンスが所有権を再割り当てする前にＷＬＭがこの全てを達成すると仮定すると、結果として状態は以下の通りである。
【表３４】
2006512688.tif 000036
【表３５】
2006512688.tif 000037
【０１１４】
そして、これが示すのは、関与するリソースの１つについてコンテンションの終了に依存するのではなく、ＲａおよびＲｂを共に管理しなければならない「メモリ」を除去するための何らかの機構を有することである。いくつかの代替を示す。
【０１１５】
１．Ｓｙ１は、明示的にデータを送信し、これがもはや所与のリソース・クラスタが必要であると考えないことを示す。例えば、Ｒａ、Ｃａ、４、遠隔を送信する。Ｓｙ２がＲａのためのＳｙ１の早期データに取って代わると、これはもはやＳｙ１から来るＲａおよびＲｂを共に管理する要求を見ない。Ｓｙ２がクラスタを継続するための他の「表明方法」を有しない場合、Ｓｙ２はローカルにクラスタを分解することができる。
２．Ｓｙ１のデータは古くなる（このため、「すぐに」置換されない場合これは消去される）。これは、おそらく、「有効期間（ＴＴＬ：time to live）」値を送信することによって実施され、その後にデータは受信者によって消去される。この機構は、故障したシステム、失われた信号、バグ、回復問題等についての安全策も提供することができる。また、ＴＴＬは、通信レイテンシを透明にするという利点を有し、送信者および受信者が共通の間隔を了解する必要がない。
【０１１６】
最もロバストな解決策は、おそらく、全て３であろう。コンテンションの終了を伝えるリソース・マネジャに、我々が「Ｒａ」ブロックをローカルに消去するケースをグローバルに処理させるので、「クラスタを分解」メッセージを送信するため充分に長く保持する必要はない。リソースのコンテンションがローカルには終了するが遠隔では終了しない場合、および、ローカル・システムが、表明方法が非トリビアルなクラスタを構築することを強制したものであった場合、ＴＴＬ値に、遠隔システム上でクラスタの分散を生じさせる。クラスタを分解させる必要があるがコンテンションが終了しない場合、我々は「Ｒａ」ブロックをいまだ有し、「クラスタを分解する」メッセージは我々が送信するものの当然の結果である。
【０１１７】
例４：クラスタの分解（ＢｒｅａｋＣｌｕ２）
この例では、共通の保持者（複数の保持者）によって結合したリソース・クラスタを、「ｎ」個のリソースから成る１つのリソース・クラスタとして、または各々１リソースから成る「ｎ」個のクラスタとして処理することができる。この結果は、記すに値する驚くべきものである。
【０１１８】
表記は例１と同様である。
【０１１９】
イベントのシーケンスは、時間順に、以下の通りである。
【表３６】
2006512688.tif 000038
【０１２０】
図１３は、ｔ＝６の後のトポロジを示す。
【０１２１】
ｔ＝６まで生じるイベントは、先の例でカバーされている。ここで興味深いのは、どのように事柄を規定したかに応じて、この状況を、１つのリソース・クラスタまたは２つのいずれかとして処理することができることである。１つのリソースの保持者としておよび異なるリソースの待機者として同じトランザクションを有するシステムによってリソース・クラスタを識別可能であるという先の例からの規定を用いる（そして、システム・クラスタ内の全システムを通してこの知識を集約する）場合、上の図は、明らかに、予想可能なものでなく、２つのリソース・クラスタを図示する。
【０１２２】
リソース・クラスタＣａｂを形成する際に値は存在せず、そうする際に伴うオーバーヘッドが存在するので（更に正確には、クラスタを分解するか否かを決定する場合に伴うオーバーヘッドがある）、この規定を使用し続ける。従って、上の図に対応する状態データは、以下の通りである。    
【表３７】
2006512688.tif 000039
【表３８】
2006512688.tif 000040
【０１２３】
この規定に固有の想定は、ＷＬＭが作業を支援しようとする場合、各リソースを調べ、ＮＱＯ値に基づいて必要な場合に保持者（複数の保持者）を支援する。このトポロジが単一リソース・クラスタとして扱われた場合、ＴｘＡはクラスタＣａｂからＮＱＯ１を引き継ぐ。これを２つのクラスタとして処理して、ＷＬＭは以下の結論を出さなければならない。
１．Ｃａは支援を必要としない。なぜなら、保持者のＮＱＯ３はリソース・クラスタのＮＱＯ４より必要度が高いからである。
２．Ｃｂは支援を必要とする。なぜなら、クラスタのＮＱＯ１はＴｘＡのＮＱＯ３より必要度が高いからである。
【０１２４】
この状況が１または２のリソース・クラスタとして扱われるか否かには関係なく、ＴｘＡはＮＱＯ１の引き継ぎで終わるので、いずれかを選択することができる。２つの「トリビアルな」（単一リソース）クラスタの管理は、複合を分解する必要がある場合のテストのため、単一の複合クラスタよりも効率的であるので、この場合は２つのトリビアルなリソース・クラスタとして扱われる。
【０１２５】
例５：単純な３ウエイ状況（３ｗａｙＥａｓｙ）
この例は、単純な３システムの状況である。また、これは、推移的終了の場合であるが、その非対称トポロジによって、システムは、リソース・マネジャから来るローカル待機者／保持者情報を有しないリソースを追跡させられる。表記は例１と同様である。
【０１２６】
イベントのシーケンスは、時間順に、以下の通りである。
【表３９】
2006512688.tif 000041
【０１２７】
ｔ＝５まで生じるイベントは、先の例でカバーされている。図１４は、ｔ＝５の後のトポロジを示す。この時点での状態データは以下の通りである。
【表４０】
2006512688.tif 000042
【表４１】
2006512688.tif 000043
【表４２】
2006512688.tif 000044
【０１２８】
ここで興味深いのは、Ｓｙ３がＲａと関与しないが、ＴｘＣのＮＱＯが１であることを判定するために（Ｓｙ２上のＴｘＡから引き継いだ）、Ｒａに関する少なくとも何らかのデータを追跡することである。しかしながら、これは、大きな困難を引き起こしてはならない。Ｓｙ１およびＳｙ２は、他のどのシステムがＲａに関与するかを知らず、これは、全てのシステムがそれらの最新のトポロジ・データ（これはむろん移動する標的である）を同報通信した後に「発見可能」であるに過ぎない。このため、Ｓｙ１およびＳｙ２はそれらのデータを何としても同報通信しなければならない。追加の負担は、Ｓｙ３がそのピアから受信する要約データを記録しなければならないことであるが、これがＲａに関与しないままである限り、複雑なトランザクションに基づいた論理は呼び出されない。これは、おそらく、クラスタのＮＱＯおよびＮＱＯにつながるシステムのアイデンティティを同報通信することによって排除することができるが、クラスタをもっと小さい断片に再び分解する時になったら表面化するいくつかの問題がある。各リソースを追跡することは、正しいＮＱＯにつながると考えることができるものについて支払う小さい代価であろう。
【０１２９】
この状態からの解放は、先の例と同様に続行する。
【０１３０】
例６：クラスタの分解を伴う３ウエイ状況（３ｗａｙＢｒｅａｋＣｌｕ）
この例は、３システム推移的終了の場合であり、「コンテンションの終了」イベントによって駆動されることなく、大きいクラスタをもっと小さいものに分解する。また、この例は、リソースの多数の共有保持者を有するトポロジを示す。表記は例１と同様である。
【０１３１】
イベントのシーケンスは、時間順に、以下の通りである。
【表４３】
2006512688.tif 000045
【０１３２】
ｔ＝７までに生じるイベントは、先の例においてカバーされている。先の例と同様、Ｓｙ３はＲａに関与しないが、Ｒａに関する少なくとも何らかのデータを追跡する。
【０１３３】
図１５は、ｔ＝７の後のトポロジを示す。この時点の状態データは以下の通りである。
【表４４】
2006512688.tif 000046
【表４５】
2006512688.tif 000047
【表４６】
2006512688.tif 000048
【０１３４】
この状態からの解放は、先の例と同様に続行する。今回は、ｔ＝８およびｔ＝９におけるイベントが意味するのは、リソース・クラスタＣａｂがもはや必要でないということであり、先の例に示された通り、この場合クラスタは分解される。このため、ｔ＝９の後、我々は図１６に示す状態および以下のテーブルに示す状態を有する。
【表４７】
2006512688.tif 000049
【表４８】
2006512688.tif 000050
【表４９】
2006512688.tif 000051
【０１３５】
関与するリソースのいずれについてもコンテンションをクリアすることなくリソース・クラスタを分解した先の例と同様、コンテンション状態のリソースを保持しているまたは待っているだけのいずれかである限り、単一のトランザクション（ここではＴｘＢ）に２つの別個のリソース・クラスタが同時に関与することがわかる。コンテンション状態のリソースを待っているとすぐに、保持しているかまたは待機しているのいずれかであるコンテンション状態のリソースは全て、単一ノリソース・クラスタとして管理しなければならない。
【０１３６】
データ構造
図１７〜２４は、本発明に従ってコンテンション・データを保存するための１つの可能なデータ構造のセットを示す。
【０１３７】
図１７を参照すると、リソース・コンテンション制御テーブル（ＲＣＣＴ：resourcecontention control table）８０２を用いて、様々な対象アイテムを単一のＷＬＭサブコンポーネントにのみ（または主に）固定する。これは、以下を含む。
１．リソース・クラスタ要素（ＲＣＬＵ）８０６（図１８）のためのアンカ８０４。
２．リソース要素（ＲＳＲＣ）８１０（図１９）のためのアンカ８０８。
３．トランザクション・テーブル（ＴＲＸＮＴ）８１４（図２２）のためのアンカ８１２。
【０１３８】
図１８を参照すると、各リソース・クラスタ要素（ＲＣＬＵ）８０６は、単一リソース・クラスタに関連したデータを含む。これは、以下を含む。
１．クラスタＩＤ８１６。  
２．クラスタＮＱＯ８１８（クラスタ内の全リソースの最小値）。
３．クラスタ内のリソースのリソース要素（ＲＳＲＣ）８１０（図１９）のためのアンカ８２０。
【０１３９】
図１９を参照すると、各リソース要素（ＲＳＲＣ）８１０は、コンテンション状態のリソースを記述する。これは、以下を含む。
１．リソースの指紋／名前８２２。
２．リソースＮＱＯ８２４。（同報通信経路上の効率のためにローカル／システム・クラスタ値を別個に維持したい場合がある。その他の場合、これはシステム・クラスタＮＱＯである。）
３．クラスタ要素（ＲＣＬＵ）８０６（図１８）に対するポインタ８２６。
４．ローカル保持者のためのリソース・コンテンション・キュー要素（ＲＣＱＥ）８３０（図２４）のためのアンカ８２８。
５．ローカル待機者のためのリソース・コンテンション・キュー要素（ＲＣＱＥ）８３０のためのアンカ８３２。
６．このリソースに関する遠隔データのためのシステム・データ・アンカ（ＳＤＡ）８３６（図２０）のためのアンカ８３４。
【０１４０】
図２０を参照すると、各システム・データ・アンカ（ＳＤＡ）８３６は、単一システムのための遠隔システム情報のアンカとして機能する。これは以下を含む。
１．遠隔システムＩＤ８３８。
２．このシステムからの遠隔システム・データ要素（ＲＳＤＥ）８４２（図２１）のためのアンカ８４０。
３．遠隔システムの最高の既知の送信シーケンス数を表す値８４４。換言すると、下りの経路上で、送信側システムは、トポロジ・データの各「バッチ」ごとに同じである（タイムスタンプのような）値を含む。各受信側システムは、入来メッセージ内の値をこの値と比較する。メッセージの値が小さい場合（これが古いことを意味する。なぜなら受信側システムはすでに同じ送信者からより最近のデータを受信したからである）、メッセージは無視される。
４．トポロジ・メッセージが遠隔システムから受信されると、ローカル・クロックを用いて更新されるタイムスタンプ８４６。図２１を参照すると、各リソース・システム・データ要素（ＲＳＤＥ）８４２は、リソースのための遠隔システム情報を含む。これは以下を含む。
【０１４１】
１．システムのためのシステム・データ・アンカ（ＳＤＡ）（図２０）に対するポインタ８４８。
２．リソースのためのリソース要素（ＲＳＲＣ）８１０（図１９）に対するポインタ８５０。
３．同じリソースのための他のＲＳＤＥ８４２のためのキュー・リンク８５２。
４．遠隔システム上の待機者のみを考慮する遠隔システムのＮＱＯ８５４。
５．デバッグのみのための送信側タイムスタンプ８５６（送信された場合の遠隔システム上のクロック値）。
６．デバッグおよびＴＴＬ処理のための、受信された場合にローカル・クロック値を表すタイムスタンプ８５８。
７．このリソースのための遠隔クラスタＩＤ８６０。遠隔システムが保持者および待機者の双方であるトランザクションを有した場合、関与する全てのリソースは同じクラスタＩＤをそこに有し、ここで同じクラスタ内にある必要がある。異なるシステムからの遠隔データが、どのリソースがクラスタに属するかに関して一致しない場合、クラスタはローカルに結合される。
８．遠隔システムがデータおよび余分を送信する計画を立てる頻度に対応して、遠隔システムによって供給される有効期間（ＴＴＬ）持続時間８６２。ローカル時間が受信タイムスタンプおよびこの値よりも大きい場合、この要素は消去にふさわしい。
【０１４２】
図２２を参照すると、トランザクション・テーブル（ＴＲＸＮＴ）８１４を用いて、対象の様々なアイテムを、単一ＷＬＭサブコンポーネントにのみ（または主に）固定する。これは以下を含む。  
１．トランザクション・テーブル８１４が構築された場合のアドレス空間の数８６４。
２．トランザクション・テーブル８１４が構築された場合のエンクレーブの数８６６。
３．第１のテーブル・エントリ８６８に対するトランザクション・テーブルの開始からのオフセット８６８。
４．アドレス空間であるトランザクションのためのエントリ（ＴＲＸＮＥ）（数８６４まで）の領域８７０。
５．エンクレーブであるトランザクションのためのエントリ（ＴＲＸＮＥ）（数８６６まで）の領域８７２。
【０１４３】
図２３を参照すると、トランザクション・テーブル（ＴＲＸＮＴ）８１４の領域８７１または８７２における各エントリ（ＴＲＸＮＥ）８７４は、ＷＬＭによってコンテンションが管理されている少なくとも１つのリソースに関与する単一トランザクションに関する情報を含む。
【０１４４】
１．タイプ８７６：アドレス空間またはエンクレーブ。
２．このトランザクションのためのアドレス空間ＩＤ（ＡＳＩＤ）またはエンクレーブＩＤ８７８。
３．このトランザクションのためのアドレス空間またはエンクレーブ・トークン８８０。ＡＳＤＩおよびエンクレーブＩＤは再使用可能である。ＩＤが再使用される場合であっても、トークンは、単一イメージ内で固有性を提供する。
４．このトランザクションによって保持されるリソースのためのコンテンション要素（ＲＣＱＥ）８３０（図２４）のキュー８８４のアンカ８８２。
５．このトランザクションによって待機されるリソースのためのコンテンション要素（ＲＣＱＥ）８３０のキュー８８８のアンカ８８６。
６．このトランザクションのＮＱＯ８８８。
【０１４５】
図２４を参照すると、各リソース・コンテンション・キュー要素（ＲＣＱＥ）８３０は、トランザクション（保持者または待機者）をリソースに関連付ける。これは、以下を含む。
１．ＴＲＸＮＴ８１０においてトランザクションのためのＴＲＸＮＥ８７４のオフセット８９２。
２．このトランザクションのための次／前のＲＣＱＥ８３０のキュー・リンク８９４。
３．リソースのためのリソース要素（ＲＳＲＣ）８１０に対するポインタ８９６。
４．このリソースのための次／前のＲＣＱＥ８３０のキュー・リンク８９８。
５．保持／待機ビット８９９（おそらくキューの妥当性確認のためのみ）。
【０１４６】
図２５は、図７に示し、図７の説明に付随するテーブルにおいてＳｙ２について要約したコンテンション状況を、どのように、図１７〜２４に示す様々なデータ構造によって捕捉するかを示す。
【０１４７】
特定の実施形態について図示し記載したが、当業者には、様々な変更が明らかであろう。このため、（ローカルまたは遠隔のいずれかのコンテンション・データに基づいて）共通クラスタの一部と考えられる全てのリソースのための共通クラスタＩＤを送信するのではなく、ローカル・システムは、ローカル・コンテンション・データに基づいて、共通クラスタに属することがわかっているリソースのためのみの共通クラスタＩＤを用いることができる。他の変形も当業者には明らかであろう。
【図面の簡単な説明】
【０１４８】
【図１】本発明を組み込んだコンピュータ・システム・クラスタを示す。
【図２】様々なタイプのコンテンション・チェーンを示す。
【図３】様々なタイプのコンテンション・チェーンを示す。
【図４】様々なタイプのコンテンション・チェーンを示す。
【図５】様々なタイプのコンテンション・チェーンを示す。
【図６】コンテンション・チェーンの頭部におけるユーザにリソースを割り当てる手順を示す。
【図７】いくつかのシステム上でのトランザクションおよびリソース間の典型的なコンテンション状況を示す。
【図８】ローカル・リソース・マネジャからの通知に応答して行われる全体的な手順を示す。
【図９】遠隔システムからのコンテンション・データの同報通信の受信に応答して行われる全体的な手順を示す。
【図１０】様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１１】様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１２】様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１３】様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１４】様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１５】様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１６】様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１７】本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図１８】本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図１９】本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２０】本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２１】本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２２】本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２３】本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２４】本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２５】図７に示すコンテンション状況が、どのようにして、クラスタ内のシステムの１つによって捕捉されるかを示す。
【図１】
2006512688.tif 000052
【図２】
2006512688.tif 000053
【図３】
2006512688.tif 000054
【図４】
2006512688.tif 000055
【図５】
2006512688.tif 000056
【図６】
2006512688.tif 000057
【図７】
2006512688.tif 000058
【図８】
2006512688.tif 000059
【図９】
2006512688.tif 000060
【図１０】
2006512688.tif 000061
【図１１】
2006512688.tif 000062
【図１２】
2006512688.tif 000063
【図１３】
2006512688.tif 000064
【図１４】
2006512688.tif 000065
【図１５】
2006512688.tif 000066
【図１６】
2006512688.tif 000067
【図１７】
2006512688.tif 000068
【図１８】
2006512688.tif 000069
【図１９】
2006512688.tif 000070
【図２０】
2006512688.tif 000071
【図２１】
2006512688.tif 000072
【図２２】
2006512688.tif 000073
【図２３】
2006512688.tif 000074
【図２４】
2006512688.tif 000075
【図２５】
2006512688.tif 000076
【手続補正書】
【提出日】平成16年10月19日(2004.10.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のシステム（１０２）を含むシステム・クラスタ（１００）において１つ以上のリソースに対するアクセスについてのユーザ間のコンテンションを管理するための方法であって、前記ユーザの各々が割り当てられた必要値を有し、アクセスを求めているリソース（１０６、１１２）の保持者または待機者のいずれかとなることができ、前記方法が、ローカル・システムとしての前記システム（１０２）の少なくとも１つにおいて実行され、
前記ローカル・システム上のコンテンションに基づいて、前記リソースを１つ以上のローカル・リソース・クラスタにグループ化することを示し、前記ローカル・リソース・クラスタの各々ごとに、前記ローカル・リソース・クラスタにおける１つ以上のリソースの必要値を示す、ローカル・リソース・クラスタ・データを保存するステップ（５０４）と、
前記システム・クラスタにおける遠隔システムとしての別のシステムから、前記遠隔システム上のコンテンションに基づいて前記リソースを１つ以上の遠隔リソース・クラスタにグループ化することを示し、前記遠隔リソース・クラスタの各々ごとに前記遠隔リソース・クラスタにおける１つ以上のリソースの必要値を示す、遠隔リソース・クラスタ・データを受信するステップ（５０８）と、
前記ローカル・リソース・クラスタ・データおよび前記遠隔リソース・クラスタ・データを組み合わせて、前記システム間のコンテンションに基づいて前記リソースを１つ以上の複合リソース・クラスタにグループ化することを示し、前記複合リソース・クラスタの各々ごとに前記複合リソース・クラスタにおける１つ以上のリソースの必要値を示す、複合リソース・クラスタ・データを生成するステップ（５１０）と、
前記リソース・クラスタのための前記複合リソース・クラスタ・データに従って前記複合リソース・クラスタの１つにおいて前記ローカル・システム上のリソースの保持者（３０２、３０３）を管理するステップと、を有し、前記管理するステップが、
他のいずれかのリソースを待機していない前記複合リソース・クラスタの１つにおいて前記ローカル・システム上のリソースの保持者（３０２）を識別するステップと、
前記ローカル・システム上の前記リソースの前記保持者に、その必要値が少なくとも前記複合リソース・クラスタにおけるいずれかのリソースの最高必要度の待機者のものであるようにシステム・リソース（３０４）を割り当てるステップと、
を有する、方法。
【請求項２】
前記リソース・クラスタのいずれかにおける１つ以上のリソースの前記必要値が、前記リソース・クラスタにおけるいずれかのリソースについての最高必要度の待機者の必要値である、請求項１に記載の方法。
【請求項３】
前記受信するステップが、遠隔システムとしての前記システム・クラスタにおける複数の他のシステムの各々ごとに実行される、請求項１に記載の方法。
【請求項４】
前記ローカル・システム上のユーザが前記リソースの１つを保持していると共に前記リソースの他のものを待機している場合、前記ローカル・システムが１対のリソースを共通ローカル・リソース・クラスタに割り当てる（５０６）、請求項１に記載の方法。
【請求項５】
前記ローカル・システム上のユーザに関してリソースのコンテンション・ステータスの変化の通知の受信（５０２）に応答して、前記ローカル・システムが前記ローカル・リソース・クラスタ・データを更新する、請求項１に記載の方法。
【請求項６】
前記ローカル・システムが前記更新したローカル・リソース・クラスタ・データを前記遠隔システムに送信する、請求項５に記載の方法。
【請求項７】
前記遠隔システムから遠隔リソース・クラスタ・データを受信すると、前記ローカル・システムが前記複合リソース・クラスタ・データを更新する、請求項１に記載の方法。
【請求項８】
前記ローカル・システムがローカル・リソース・クラスタ・データを前記遠隔システムに送信する、請求項１に記載の方法。
【請求項９】
前記送信されたローカル・リソース・クラスタ・データが、リソースと、前記ローカル・システム上のコンテンションに基づいて前記リソースを割り当てるリソース・クラスタと、前記リソースのための前記ローカル・システム上の必要値とを示す、請求項８に記載の方法。
【請求項１０】
複数のシステム（１０２）を含むシステム・クラスタ（１００）において１つ以上のリソース（１０６、１１２）に対するアクセスについてのユーザ間のコンテンションを管理するための装置であって、前記ユーザの各々が割り当てられた必要値を有し、アクセスを求めているリソースの保持者または待機者のいずれかとなることができ、前記装置が、ローカル・システムとしての前記システム（１０２）の少なくとも１つに関連付けられ、
前記ローカル・システム上のコンテンションに基づいて、前記リソースを１つ以上のローカル・リソース・クラスタにグループ化することを示し、前記ローカル・リソース・クラスタの各々ごとに、前記ローカル・リソース・クラスタにおける１つ以上のリソースの必要値を示す、ローカル・リソース・クラスタ・データを保存するための論理と、
前記システム・クラスタにおける遠隔システムとしての別のシステムから、前記遠隔システム上のコンテンションに基づいて前記リソースを１つ以上の遠隔リソース・クラスタにグループ化することを示し、前記遠隔リソース・クラスタの各々ごとに前記遠隔リソース・クラスタにおける１つ以上のリソースの必要値を示す、遠隔リソース・クラスタ・データを受信するための論理と、
前記ローカル・リソース・クラスタ・データおよび前記遠隔リソース・クラスタ・データを組み合わせて、前記システム間のコンテンションに基づいて前記リソースを１つ以上の複合リソース・クラスタにグループ化することを示し、前記複合リソース・クラスタの各々ごとに前記複合リソース・クラスタにおける１つ以上のリソースの必要値を示す、複合リソース・クラスタ・データを生成するための論理と、
前記リソース・クラスタのための前記複合リソース・クラスタ・データに従って前記複合リソース・クラスタの１つにおいて前記ローカル・システム上のリソースの保持者を管理するための論理と、を有し、前記管理する論理が、
他のいずれかのリソースを待機していない前記複合リソース・クラスタの１つにおいて前記ローカル・システム上のリソースの保持者を識別する論理と、
前記ローカル・システム上の前記リソースの前記保持者に、その必要値が少なくとも前記複合リソース・クラスタにおけるいずれかのリソースの最高必要度の待機者のものであるようにシステム・リソースを割り当てる論理と、
を有する、装置。
【請求項１１】
前記ローカル・システム上のユーザが前記リソースの１つを保持していると共に前記リソースの他のものを待機している場合、前記ローカル・システムが１対のリソースを共通ローカル・リソース・クラスタに割り当てる、請求項１０に記載の装置。
【請求項１２】
前記ローカル・システム上のユーザに関してリソースのコンテンション・ステータスの変化の通知の受信に応答して、前記ローカル・システムが前記ローカル・リソース・クラスタ・データを更新し、前記更新したローカル・リソース・クラスタ・データを前記遠隔システムに送信する、請求項１０に記載の装置。
【請求項１３】
前記ローカル・システムがローカル・リソース・クラスタ・データを前記遠隔システムに送信し、前記送信されたローカル・リソース・クラスタ・データが、リソースと、前記ローカル・システム上のコンテンションに基づいて前記リソースを割り当てるリソース・クラスタと、前記リソースのための前記ローカル・システム上の必要値とを示す、請求項１０に記載の装置。
【請求項１４】
機械によって読み取り可能なプログラム・ストレージ・デバイスであって、前記機械によって実行可能な命令のプログラムを実際に具現化して、複数のシステム（１０２）を含むシステム・クラスタ（１００）において１つ以上のリソース（１０６、１１２）に対するアクセスについてのユーザ間のコンテンションを管理するための方法ステップを実行し、前記ユーザの各々が割り当てられた必要値を有し、アクセスを求めているリソースの保持者または待機者のいずれかとなることができ、前記方法ステップが、ローカル・システムとしての前記システムの１つにおいて実行され、
前記ローカル・システム上のコンテンションに基づいて、前記リソースを１つ以上のローカル・リソース・クラスタにグループ化することを示し、前記ローカル・リソース・クラスタの各々ごとに、前記ローカル・リソース・クラスタにおける１つ以上のリソースの必要値を示す、ローカル・クラスタ・データを保存するステップ（５０４）と、
前記システム・クラスタにおける遠隔システムとしての別のシステムから、前記遠隔システム上のコンテンションに基づいて前記リソースを１つ以上の遠隔リソース・クラスタにグループ化することを示し、前記遠隔リソース・クラスタの各々ごとに前記遠隔リソース・クラスタにおける１つ以上のリソースの必要値を示す、遠隔リソース・クラスタ・データを受信するステップ（５０８）と、
前記ローカル・リソース・クラスタ・データおよび前記遠隔リソース・クラスタ・データを組み合わせて、前記システム間のコンテンションに基づいて前記リソースを１つ以上の複合リソース・クラスタにグループ化することを示し、前記複合リソース・クラスタの各々ごとに前記複合リソース・クラスタにおける１つ以上のリソースの必要値を示す、複合リソース・クラスタ・データを生成するステップ（５１０）と、
前記リソース・クラスタのための前記複合リソース・クラスタ・データに従って前記複合リソース・クラスタの１つにおいて前記ローカル・システム上のリソースの保持者を管理するステップ（３０２、３０４）と、を有し、前記管理するステップが、
他のいずれかのリソースを待機していない前記複合リソース・クラスタの１つにおいて前記ローカル・システム上のリソースの保持者を識別するステップ（３０２）と、
前記ローカル・システム上の前記リソースの前記保持者に、その必要値が少なくとも前記複合リソース・クラスタにおけるいずれかのリソースの最高必要度の待機者のものであるようにシステム・リソースを割り当てるステップ（３０４）と、
を有する、プログラム・ストレージ・デバイス。
【請求項１５】
前記ローカル・システム上のユーザが前記リソースの１つを保持していると共に前記リソースの他のものを待機している場合、前記ローカル・システムが１対のリソースを共通ローカル・リソース・クラスタに割り当てる、請求項１６に記載のプログラム・ストレージ・デバイス。
【請求項１６】
前記ローカル・システム上のユーザに関してリソースのコンテンション・ステータスの変化の通知の受信に応答して、前記ローカル・システムが前記ローカル・リソース・クラスタ・データを更新し、前記更新したローカル・リソース・クラスタ・データを前記遠隔システムに送信する、請求項１４に記載のプログラム・ストレージ・デバイス。
【請求項１７】
前記ローカル・システムがローカル・リソース・クラスタ・データを前記遠隔システムに送信し、前記送信されたローカル・リソース・クラスタ・データが、リソースと、前記ローカル・システム上のコンテンションに基づいて前記リソースを割り当てるリソース・クラスタと、前記リソースのための前記ローカル・システム上の必要値とを示す、請求項１４に記載のプログラム・ストレージ・デバイス。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】  明細書    
【技術分野】
【０００１】
本発明は、情報処理システムにおいて逐次化リソースにアクセスするユーザ間のコンテンションを管理するための方法および装置に関する。更に具体的には、これは、複数のかかるシステムを含むシステム・クラスタにおいて、かかるコンテンションを管理するための方法および装置に関する。
【背景技術】
【０００２】
リソース・コンテンションは、情報処理システムにおいて周知の現象である。これが発生するのは、ユーザ（例えばプロセスまたは他の作業単位）が、すでに別のユーザが保持するリソースにアクセスを試みる場合であり、第２のユーザが要求するアクセスは第１のユーザのものと相反する。これは、例えば、どちらかのユーザが対象のリソースに対して排他的なアクセスを要求している場合に発生する。リソース・マネジャは、それらが制御するリソースに対する競合した要求間のコンテンションを管理するソフトウエア・コンポーネントであり、保持者として１人以上のかかるユーザにそのリソースに対するアクセスを与え、そのリソースが利用可能となるまで残りのユーザを待機者のプールに配置する。
【０００３】
ＩＢＭ  ｚ／ＯＳ（商標）オペレーティング・システム等のコンピュータ・オペレーティング・システムでは、多数のリソース・マネジャおよび多数の作業単位があるので、リソース・コンテンション管理は複雑な問題である。コンテンション・チェーンが生じる場合がある。換言すると、コンテンションはリソース間にまたがる可能性がある。例えば、ジョブＡはリソースＲ１を待つがＲ２を保持し、ジョブＢはＲ１を保持するがＲ３を待っており、Ｒ３はジョブＣによって保持される。コンテンションは、システム間にまたがって生じる可能性がある。上述の例で、各ジョブは別個のシステム上にある場合がある。コンテンションは、リソース・マネジャをまたがって生じる可能性がある。例えば、Ｒ１はＧＲＳエンキューであり、Ｒ２はＤＢ２（商標）ラッチとすることができる。ｚ／ＯＳの大域資源逐次化（ＧＲＳ：global resource serialization）コンポーネントはエンキューを管理し、ＩＭＳ（商標）リソース・ロック・マネージャ（ＩＲＬＭ：IMS
Resource Lock Manager）はＤＢ２リソースを別個に管理する。
【０００４】
リソース間コンテンションは、通常、各リソースの保持者および待機者のトポロジを追跡し、いずれかの交点を見つけることによって、単一のリソース・マネジャ（例えばＧＲＳ）内で解決する。システム間コンテンションは、通常、リソース・マネジャに全クラスタのデータを認識させることによって解決する（クラスタを独立した複数のシステムとしてでなく１つのユニットとして管理する）。リソース・マネジャ間コンテンションは、通常、報告プロダクトに、バーチャル・リソース・マネジャであるかのように全インタフェースに問合せを行わせ、データを相関させることによって「解決」する。この問題は、コンテンションの状態にあるリソース数においてオーダーＯ（２n）であるので、計算上、複雑である。
【０００５】
ｚ／ＯＳの基本ＭＶＳ（商標）コンポーネントは、単純で効率的な解決策を有する（一般に、「エンキュー促進」として既知である）。すなわち、コンテンションの状態にあると報告されるリソースを保持するいずれかの作業のＣＰＵおよびＭＰＬアクセスを自動的に（かつ一時的に）増大させ、作業の必要度には注目しない。これは、実際のトポロジには無関係に、リソースのための「重要な」待機者（複数の待機者）があるかのように保持者を管理することと同等である。この動作を理解するため、以下の例を考える。以下のことを仮定する。
１．ジョブＡがリソースＲ１を保持する。
２．ジョブＢがリソースＲ２を保持しＲ１を待つ。
３．ジョブＣがＲ２を待つ。
【０００６】
表記上、これは、チェーンＣ→Ｂ→Ａと表すことができる。大文字はジョブを表し、符号「→」（チェーンにおける「リンク」）は、この符号の左側のジョブがこの符号の右側のジョブによって保持されるリソースを待っていることを示す。このため、上述のチェーンは、ジョブＣが、ジョブＢによって保持されるリソースを待っており、ジョブＢが、ジョブＡが保持するリソースを待っていることを意味する。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
これらがＧＲＳリソースであると仮定すると、従来のＭＶＳ実施では、ジョブＡおよびＢがコンテンションの状態にあるリソースを保持するので、それらのために役立ち、各々を等しく、限られた時間だけ促進する。しかしながら、Ｂに役立つのは無益である。なぜなら、Ｂは実際Ａを待っているからである。Ｂがそれ自身マルチタスキングである場合、この支援は実際、リソース・コンテンションに関して何もせずに、競合する作業に有害となる恐れがある。
【０００８】
Fagen等の、「Method and apparatus for
serializing resources access requests in a multisystem complex」と題する米国特許第５，８０５，９００号は、マルチシステム複合体の１つのシステムにおいて元来はリクエスタからのリソースに対するアクセスの要求を逐次化するための方法および装置を開示する。複合体の各システムは、リソースに対するアクセスについてそのシステム上のリクエスタ間のコンテンションを示すローカル・コンテンション・データ、および、ローカル・コンテンション・データを要約するコンテンション要約を維持する。システム間のコンテンションを管理するグローバル・マネジャは、ローカル・コンテンション要約を用いて、リソースについてのグローバル・コンテションの存在を判定する。元来はシステム上のリクエスタからのリソースに対するアクセスの要求に応答して、システムは、その要求がシステムのためにローカル・コンテンション要約の更新を必要とするか否かを判定する。要求がローカル・コンテンション要約の更新を必要としない場合、システムは、システムのためのローカル・コンテンション・データに従って要求を処理する。要求がローカル・コンテンション要約の更新を必要とする場合、システムは、グローバル・マネジャに更新を通知し、グローバル・マネジャから受信した応答に従って要求を処理する。
【０００９】
セマフォ（semaphores）、モニタ、または集合等の一般的に用いられる同期プリミティブの直接適用によって、制御されない優先度反転に至ることができる。すなわち、無限の時間期間、優先度の高いジョブが優先度の低いジョブによって阻止される状況である。「Priority
Inheritance Protocols: An approach to real-time synchronization」（Lui SHA等、IEEE
Transactions on computers, IEEE INC. New York, US. Vol.39, no.9,1 １９９０年９月（１９９０−０９−０１）、１１７５〜１１８５ページ、XP000149625
ISSN: 0018-9340）と題する発表は、「基本優先度インヘリタンス・プロトコル」および「優先度上限プロトコル」と呼ばれる「優先度インヘリタンス・プロトコル」のクラスに属する２つのプロトコルを記述する。双方のプロトコルは、この非制御優先度反転問題を解決する。特に、優先度上限プロトコルは、最悪の場合のタスク阻止時間を、多くても、優先度の低いタスクの単一の重要セクションの実行の持続時間まで縮小する。更に、このプロトコルは、デッドロックの形成を防ぐ。１組の充分な条件が得られ、この条件のもとで、このプロトコルを用いた１組の周期的タスクをスケジュールすることができる。
【００１０】
「Priority inheritance and ceilings for
distributed manual exclusion」と題する発表（Mueller F ED 20th IEEEリアルタイム・システム・シンポジウムの議事録、RTSS’99, Phoenix,
AZ, 1-3, 1999,IEEEリアルタイム・システム・シンポジウム、Los Alamitos, CA: IEEE COMP. SOC. US., 1  １９９９年１２月（１９９９−１２−０１）３４０〜３４９ページ、XP000895591
ISBN: 0-7803-5986-0）は、以下の寄与を開示する。第１に、分散型システムにおける優先相互排除の問題に対する解決策が正しいと証明される。このプロトコルは、他のプロトコルの優先拡張よりも少ない要求に基づいており、ｎノードについて、平均の複雑さθ（ｎ）および最悪の場合の複雑さＯ（ｎ）のメッセージで他のプロトコルを実行する。第２に、相対的公正の概念が導入される。これは、同期化クロックが存在しない場合に順序付けに関して平行イベント間の関係を定量化する。この概念をプロトコルに適用して、メッセージ遅延が有限である場合にイベント間のある順序を保証するための要件を決定する。第３に、プロトコルを拡張して、優先度インヘリテンスおよび優先度上限プロトコルを組み込むことによって優先度反転を防ぐ。拡張は、元のプロトコルと充分に統合するものと示される。それらによって、リソース・コンテンションのため動的に高くした優先度ごとに、前述のものと同じメッセージ・オーバーヘッドが課される一方で、優先度上限エミュレーション・プロトコルのため等の早期優先度上昇は、追加のオーバーヘッドを全く要しない。
【課題を解決するための手段】
【００１１】
本発明の１つの態様は、先に確認した同時出願の主題であり、情報処理システムにおいてリソースに対するアクセスについてのユーザ間のコンテンションを管理するための方法および装置を含む。各ユーザは、割り当てられた必要値を有し、アクセスを求めているリソースの保持者または待機者のいずれかとなることができる。本発明のこの態様によれば、ユーザのチェーンの頭部において待機者でないユーザを識別する。チェーン内では、チェーン内に次のユーザを有する各ユーザが、次のユーザが待っているリソースを保持している。チェーンの頭部におけるユーザは、その必要値が少なくともチェーンにおける最高必要度の待機者のものであるかのように管理され、好ましくは、ユーザに、その必要値が少なくともかかる最高必要度の待機者のものであるかのようにシステム・リソースを割り当てる。
【００１２】
好ましくは、本発明のこの態様の独立した発明の特徴として、かかるコンテンション・チェーンは、リソースのリソース・クラスタを識別することによって識別される。リソース・クラスタ内の各リソースは、リソース・クラスタ内の別のリソースを待っているユーザによって保持されるか、リソース・クラスタ内の別のリソースを保持しているユーザによって待機されているかのいずれかである。更に、リソース・クラスタ内のいずれかのリソースの最高必要度の待機者の必要値を決定する。ユーザは、リソース・クラスタ内のリソースの保持者であるが他のいずれかのリソースを待っていないものとして識別され、リソースのその保持者は、その必要値が少なくともリソース・クラスタ内の他のいずれかの最高必要度の待機者のものであるかのように管理される。この場合も、好ましくは、ユーザに、その必要値が少なくともかかる最高必要度の待機者のものであるかのようにシステム・リソースを割り当てる。
【００１３】
リソース・クラスタを識別するステップは、好ましくは、リソースのコンテンション・ステータスの変更の通知の受信に応答して行われる。このため、リソースは、リソース・クラスタ内の別のリソースを待機しているユーザによって保持されているか、またはリソース・クラスタ内の別のリソースを保持しているユーザによって待機されている場合、新たにリソース・クラスタに割り当てられる。一方、リソースは、リソース・クラスタ内の別のリソースを待機しているユーザによってもはや保持されていないか、またはリソース・クラスタ内の別のリソースを保持しているユーザによって待機されていない場合、リソース・クラスタから除去される。
【００１４】
このため、本発明のこの態様は、「必要度」のファクタを、基本システム・リソース割り当て機構に統合することを考え、そのため、チェーンの頭部におけるジョブ（例えば上述のジョブＡであり、必要度ファクタ４）が、リソースを解放するまで、チェーン上のどこか別の場所のもっと必要度が高いジョブ（例えば上述のジョブＣであり、必要値１）の必要度ファクタを有するかのように実行することができる。必要度の概念を先の例に統合すると、これがどのように異なる方法で実行するかをより良く理解することができる。以下を想定する。
１．ジョブＡは、「必要値」４を有し、リソースＲ１を保持する。（この明細書では、小さい数が大きい必要度を表すので、「支援の優先度」として考えることができる。）
２．ジョブＢは、必要値５を有し、リソースＲ２を保持しＲ１を待つ。
３．ジョブＣは、必要値１を有し、Ｒ２を待つ。
【００１５】
表記上、これは、チェーンＣ（１）→Ｂ（５）→Ａ（４）と表すことができる。ここで、大文字はジョブを表し、カッコ内の数はそれらのジョブの「必要値」を表し、符号「→」（チェーンにおける「リンク」）は、この符号の左側のジョブがこの符号の右側のジョブによって保持されるリソースを待っていることを示す。このため、上述のチェーンは、必要値１のジョブＣが、必要値５のジョブＢによって保持されるリソースを待っており、ジョブＢが、必要値４のジョブＡが保持するリソースを待っていることを意味する。
【００１６】
このように「必要度」ファクタを用いると、明らかでない場合があるいくつかの利点が与えられる。第１に、これは、上述のＢのような作業の支援を回避する。なぜなら、我々は、Ｂが別のリソースを待っていることを理解し、このため、よくても無益であり、最悪の場合には無関係の競合する作業に有害であるアクションを回避する。第２に、これによって、システム・リソース割り当て装置に、それ以外の場合よりも、不明確ではあるが限定された時間のみでなく、Ａを支援することができる知識を与える。従来の実施は、チェーンを無視し、ある限られた時間期間、ＡおよびＢの双方を「重要」として扱うが、本発明では、Ａが実際に必要値１を有すること、すなわち、Ｃが待機している限り「最も重要である」ことが理解される。第３に、これによって、システム・リソース割り当て装置に、それが望む場合、チェーンの頭部における保持者（複数の保持者）を支援しないようにすることができる知識を与える。これは、例えば、ネットワーク内の最高必要度の作業が現在の保持者である場合である。
【００１７】
この本発明の第１の態様は、単一のシステム上で、または複数のかかるシステムを含むシステム・クラスタにおいて実施することができる。リソース・クラスタを識別する本発明の変形は、特に、マルチシステム実施における使用に適しており、これは、以下で述べるように、ローカル・コンテンション・データのサブセットのみの交換を必要とする。
【００１８】
本発明の別の態様は、本出願の主題であり、多数システム間のリソース割り当てを管理し、同時に、コンテンション状態にあるマルチシステム・リソースの数のオーダーＯ（ｎ）で極めて少量のデータを通過させるためのプロトコルが意図される。
【００１９】
本発明の他の態様は、上述の単一システムの本発明の態様を組み込んでおり、複数のシステムを含むシステム・クラスタにおいてリソースに対するアクセスについてのユーザ間のコンテンションを管理するための方法および装置が意図される。ユーザの各々が割り当てられた必要値を有し、アクセスを求めているリソースの保持者または待機者のいずれかとなることができる。本発明のこの態様によれば、かかる各システムは、ローカル・システムとして動作し、ローカル・システム上のコンテンションに基づいて、リソースをローカル・リソース・クラスタにグループ化することを示し、各ローカル・リソース・クラスタごとに、ローカル・リソース・クラスタにおける１つ以上のリソースの必要値を示す、ローカル・リソース・クラスタ・データを保存する。また、各システムは、システム・クラスタにおける遠隔システムとして動作する別のシステムから、遠隔システム上のコンテンションに基づいてリソースを遠隔リソース・クラスタにグループ化することを示し、各遠隔リソース・クラスタごとに遠隔リソース・クラスタにおける１つ以上のリソースの必要値を示す、遠隔リソース・クラスタ・データを受信する。各ローカル・システムは、ローカル・リソース・クラスタ・データおよび遠隔リソース・クラスタ・データを組み合わせて、システム間のコンテンションに基づいてリソースを複合リソース・クラスタにグループ化することを示し、各複合リソース・クラスタごとに複合リソース・クラスタにおける１つ以上のリソースの必要値を示す、複合リソース・クラスタ・データを生成する。そして、各ローカル・システムは、この複合リソース・クラスタ・データを用いて、複合リソース・クラスタにおいてローカル・システム上のリソースの保持者を管理する。
【００２０】
好ましくは、ローカル、遠隔、および複合リソース・クラスタ・データは、対象のリソース・クラスタ内のいずれかのリソースの最高必要度の待機者の必要値を示す。複合リソース・クラスタ内におけるローカル・システム上のリソースの保持者を管理するには、他のいずれかのリソースを待機していないかかる保持者を識別し、かかる保持者に、その必要値が少なくとも対応する複合リソース・クラスタにおけるいずれかのリソースの最高必要度の待機者のものであるかのように、システム・リソースを割り当てる。
【００２１】
好ましくは、ローカル・システム上のユーザがリソースの１つを保持すると共にリソースの他のものを待機している場合に、各ローカル・システムは、１対のリソースを共通ローカル・リソース・クラスタに割り当て、ローカル・システム上のユーザに関してリソースのコンテンション・ステータスの変化の通知の受信に応答して、ローカル・リソース・クラスタ・データを更新する。また、各ローカル・システムは、いずれかの更新を含むそのローカル・リソース・クラスタ・データを遠隔システムに更新し、これは、送信されたリソース・クラスタ・データを受信側システムに対する遠隔リソース・クラスタ・データとして扱い、次いで、これに応じてそれらの複合リソース・クラスタ・データを更新する。送信されたローカル・リソース・クラスタ・データは、リソースと、ローカル・システム上のコンテンションに基づいてリソースを割り当てるリソース・クラスタと、リソースのためのローカル・システム上の必要値とを示す。
【００２２】
リソース・クラスタ内の関与する各リソース・マネジャ・インスランスからの部分データ（全リソース・トポロジではない）および「必要度」の尺度を用いて、各システムは、個別に、リソースについての最高必要度の待機者（「上述の全て」間のリソースの推移的終了におけるいずれかの待機者を含む）が、チェーンの頭部におけるリソースのいずれかの保持者よりも必要度が高いか否かを理解することができる。そして、システムは、かかる保持者（複数の保持者）が、それらの必要度の尺度が最高必要度のブロック化作業部分よりも必要度が高いかのようにリソースを割り当てることができる。
【００２３】
プロトコルは、各システムから保持者および待機者の全リストの代わりに、リソースごとの１組の情報のみを回すので、どのシステムも、システム・クラスタまたはリソース・クラスタ間のコンテンションの完全なビューを有しない。データ自体は、クラスタに固有のリソース名と、送信側システム上の最高必要度の待機者の必要値と、送信側システムに固有のトークンとのみから成る。後者のトークンが２つのリソースについて一致した場合、それらの管理は統合しなければならない（トークンは、送信側システムのローカル・データのみに基づいて割り当てられる）。また、トポロジにおける作業部分がコンテンション状態にない他のリソースを保持するとしても、プロトコルは、コンテンション状態にあるリソースに関するデータのみを送信する。送信側システム・クラスタ情報は、様々な方法で符号化することができる。このため、送信側システムのローカル・コンテンションのみに基づいてトークンを送信するのではなく、ローカル・システムは、好適な実施形態では、非トリビアルなリソース・クラスタ割り当て（すなわち２つ以上のリソースを含むリソース・クラスタに対する割り当て）がローカルまたは遠隔のどちらの情報に基づくかの指示と共に、遠隔コンテンションに基づいてリソース・クラスタ名を送信することができる。
【００２４】
本発明は、好ましくは、コンピュータ・オペレーティング・システムの一部として、またはかかるオペレーティング・システムと共に動作する「ミドルウエア」ソフトウエアとして、実施される。かかるソフトウエア実施は、本発明の方法ステップを実行するためにハードウエア機械によって実行可能な命令のプログラムの形態の論理を含む。命令のプログラムは、半導体、磁気、光学、または他のストレージ技術を用いた１つ以上のボリュームを含むプログラム・ストレージ・デバイス上に具現化することができる。
【発明を実施するための最良の形態】
【００２５】
図１は、本発明を組み込んだコンピュータ・システム・クラスタ１００を示す。コンピュータ・システム・クラスタ１００は、いずれかの適切なタイプの相互接続１０４によって結合された個々のシステム１０２（Ｓｙ１、Ｓｙ２、Ｓｙ３）を含む。例示的な３つのシステムを示すが、本発明は、システムのいずれかの特定の数には限定されない。コンピュータ・システム・クラスタ１００は、１つ以上のグローバルまたはマルチシステム・リソース１０６を有し、これらは様々なシステムからの要求によって争われる。
【００２６】
システム・クラスタの各システム１０２は、別個の物理的な機械または１つ以上の物理的な機械の別個の論理区分のいずれかを含むことができる。各システムは、オペレーティング・システム（ＯＳ）１０８を含み、これが、本発明の機能を実行することに加えて、システム・サービスを提供しシステム・リソースの使用を管理するという通常の機能を実行する。本発明は、いずれかの特定のハードウエアまたはソフトウエア・プラットフォームに限定されないが、好ましくは、各システム１０２は、ＩＢＭのｚＳｅｒｉｅｓ（商標）サーバまたはかかるサーバの論理区分上で実行するＩＢ  ｚ／ＯＳオペレーティング・システムのインスタンスを含む。
【００２７】
各システム１０２は、マルチシステム・リソース１０６に対するアクセスについて互いに争う１つ以上のリクエスタ１１０、および、任意選択的に、同一システム上のリクエスタにのみ利用可能なローカル・リソース１１２を含む。リクエスタ１１０は、リソース１０６または１１２に対するアクセスを争ういずれかのエンティティを含むことができ、システム・リソースを割り当てる目的で単一のエンティティとして扱われる。
【００２８】
（リクエスタ１１０に割り当てられるシステム・リソースは、リクエスタ間のコンテンションの対象であるリソース１０６および１１２とは区別しなければならない。システム・リソースは、通常リクエスタ自体に透明な方法でリクエスタ１１０に割り当てられて、スループットまたは応答時間等の何らかの性能尺度を改善する。一方、リソース１０６および１１０は、それらの実行の一部としてリクエスタによって明白に要求される。それらを区別することが必要である場合、後者のリソース・クラスは、時に、「逐次化リソース」等の言葉を用いて称する。）
【００２９】
各オペレーティング・システム１０８は、１つ以上のリソース・マネジャ１１４および作業負荷マネジャ（ＷＬＭ：workload manager）１１６を含めて、本発明の対象のいくつかのコンポーネントを含む。各リソース・マネジャ１１４は、それが制御するリソース１０６または１１２について、競合するリクエスタ１１０間のコンテンションを管理するため、保持者として１つ以上のかかるリクエスタによるそのリソースへのアクセスを与え、リソースが利用可能になるまで残りのリクエスタを待機者のプールに配置する。本発明は、いずれかの特定のリソース・マネジャに限定されないが、１つのかかるリソース・マネジャ（マルチシステム・リソース１０６のために用いられる）は、ｚ／ＯＳオペレーティング・システムの大域資源逐次化（ＧＲＳ）コンポーネントとすることができる。これは、ＩＢＭ刊行物z/OS
MVS Planning: Global Resource Serialization、ＳＡ２２−７６００−０２（２００２年３月）のような参考文献に記載されている。これは、引用により本願にも含まれるものとする。更に、リソース・マネジャ１１４は、（ＧＲＳがｚ／ＯＳの一部であるので）オペレーティング・システム１０８の一部として示すが、オペレーティング・システムから独立して他のリソース・マネジャ（ＩＲＬＭ等）が存在する場合もある。
【００３０】
作業負荷マネジャ（ＷＬＭ）１１６は、「必要」値に基づいて、システム・リソースを、作業単位（アドレス空間、エンクレーブ（enclaves）等とすることができる）に割り当てる。この必要値は、その作業単位（またはそれが属するサービス・クラス）に割り当てられており、ある意味で、処理している他の作業単位に対するその作業単位の相対的な優先度を反映する。本発明は、いずれかの特定の作業負荷マネジャに限定されないが、１つのかかる作業マネジャは、ＩＢＭ  ｚ／ＯＳオペレーティング・システムの作業負荷管理コンポーネントであり、これは、ＩＢＭ刊行物z/OS
MVS Planning: Workload Management、ＳＡ２２−７６０２−０４（２００２年１０月）、およびz/OS MVS
Programming: Workload Management Services、ＳＡ２２−７６１９−０３（２００２年１０月）のような参考文献に記載されている。これらは、引用により本願にも含まれるものとする。かかる作業負荷管理コンポーネントは、ＩＢＭ  ｚ／ＯＳオペレーティング・システムのシステム・リソース・マネジャ（ＳＲＭ：system
resources manager）コンポーネントと共に機能する。これは、ＩＢＭ刊行物z/OS MVS Initialization and Tuning
Guide、ＳＡ２２−７５９１−０１（２００２年３月）の、特に第３章（３−１から３−８４ページ）に記載されている。これは、引用により本願にも含まれるものとする。これらのコンポーネントがインタラクトする具体的なの方法は本発明の部分ではないので、双方のコンポーネントは、図１において「ＷＬＭ」と標示したボックス１１６によって示されると想定する。
【００３１】
必要値をユーザに割り当てる具体的な方法も、割り当てた必要値に基づいてシステム・リソースをユーザに割り当てる方法も、本発明の部分ではない。双方のために、当技術分野において周知の多数の技法のいずれも用いることができる。好ましくは、必要値は、システム・クラスタ全体を通して同様の意味を有するものとする。図示する実施形態では、これはアクティブＷＬＭポリシに基づいて計算された動的な値であり、リソース・グループの限界および重要性を単一の量へと統合し、これはシステム全体において安全に比較することができる。順序付けは任意であるが、この記載では、数が小さい方が必要または優先度が高いことを表すので、の必要値１を有するユーザは、必要値５を有するユーザよりも「必要度が高い」。
【００３２】
図２から５は、システム・クラスタ１００においてリソース１０６および１１２間で生じ得る様々なコンテンション・チェーンを示す。これらのチェーンは、より正式には有向グラフとして知られるが、本明細書中ではチェーンの用語を用いる。これらのチェーンにおいて、矢印で示す各リンクは、ユーザ（矢印の尾部のノードによって表される）は、別のユーザ（矢印の頭部のノードによって表される）が保持するリソースを待っているという関係を表す。かかる関係の「推移的終了」は、チェーンのいずれかのノードを伴う全てのかかる関係を含むことによって形成されるチェーンである。このため、矢印を追っていくと、全てのノードが最終的に示す保持者は、コンテンションの状態にあるリソースを待っておらず、従ってチェーンの頭部にある。（チェーンが２つ以上の頭部を有することができるか否かは、以下で図４の説明において論じる。）
【００３３】
図２は、背景技術および課題を解決するための手段において記載したコンテンションの状況を示す。ユーザＣは、ユーザＢが保持するリソースＲ２を待っており、ユーザＢは、ユーザＡが保持するリソースＲ１を待っている。本明細書中で開示するように、ユーザＡは、保持者であるが待機者でなく、従ってチェーンの頭部にあり、その必要値が少なくとも待機者ＢおよびＣのうち必要度が高い方のものであるように、システム・リソースを割り当てられる。なぜなら、その待機者は双方とも、ＡがリソースＲ１で終わることで利益を得るからである。また、ユーザＢは保持者でもあるが、この優先的な割り当てを受けない。なぜならこれはリソースを待っており、従って実行していないからである。このため、この時点で、もっと多くのリソースをＢに割り当てることには意味がない（しかし、後にＢが保持者としてリソースＲ１を取得すると、その可能性がある）。
【００３４】
図２に示すコンテンション状況は直線チェーンであり、各ユーザは単一のユーザが保持するリソースを保持するかもしくは待機するかまたはその双方である。しかしながら、一般に、コンテンション・チェーンは分岐する可能性があるので、単一のユーザが、多数ユーザが待機するリソースを保持しているか、または、多数ユーザが保持するリソースを待っている場合がある。また、一部のリソースは、共有アクセスを要求され、多数の同時保持者が存在し得ることがある。
【００３５】
図３は、第１のタイプの分岐を有するコンテンション状況を示し、図２に示す状況と異なるのは、ここでは追加のユーザＤがユーザＢによって保持されるリソースＲ３を待っている点である。ここで、ユーザＡには、その必要値が少なくとも待機者Ｂ、Ｃ、およびＤのうち最高の必要度のものであるように、システム・リソースが割り当てられる。なぜなら、これらの待機者は全て、ＡがリソースＲ１で終わることで利益を得るからである。
【００３６】
図４は、双方のタイプの分岐を有するコンテンション状況を示し、図２に示す状況と異なるのは、ここではユーザＣがユーザＤによって制御される追加のリソースＲ３を待っており、ユーザＤがユーザＡによって制御されるリソースＲ４を待っている点である。この場合も、ユーザＡには、その必要値が少なくとも待機者Ｂ、Ｃ、およびＤのうち最高の必要度のものであるように、システム・リソースが割り当てられる。なぜなら、これらの待機者は全て、ＡがリソースＲ１で終わることで利益を得るからである。
【００３７】
最後に、図５は、第２のタイプの分岐を有するコンテンション状況を示し、図２に示すチェーンと異なるのは、ここではユーザＣがユーザＤによって保持されるリソースＲ３も待っており、ユーザＤはユーザＥによって保持されるリソースＲ４を待っている点である。理論的には、これは、各々が１つの頭部を有する２つの部分的に重複するチェーンとして分析することができる。一方のチェーンがＣ→Ｂ→Ａであり、他方がＣ→Ｄ→Ｅである。第１のチェーンでは、ユーザＡに、その必要値が少なくとも待機者ＢおよびＣのうち必要度が高い方のものであるようにシステム・リソースが割り当てられ、第２のチェーンでは、ユーザＥに、その必要値が少なくとも待機者ＣおよびＤのうち必要度が高い方のものであるようにシステム・リソースが割り当てられる。
【００３８】
これを要約すると、図６を参照して、理想的な実施において、最初に、ユーザのチェーンの頭部において、待機者でないユーザを識別する。チェーンにおいて次のユーザを有する各ユーザは、次のユーザが待っているリソースを保持している（ステップ３０２）。図５において、これは、ユーザＡ〜Ｃから成るチェーンではユーザＡであり、ユーザＣ〜Ｅから成るチェーンではユーザＥである。次いで、チェーンの頭部のユーザに、その必要値が当該チェーンにおいて少なくとも最高の必要度の待機者のものであるように、システム・リソースを割り当てる（ステップ３０４）。すなわち、チェーンの頭部におけるユーザのものより大きい必要値を有する最高の必要度の待機者があったら、そのユーザには、その必要値がそのユーザのものより大きい場合に、かかる待機者の必要値に基づいて、システム・リソースが割り当てられる。
【００３９】
２つのチェーンとしてのこの処理では、ユーザＡのリソース割り当ては、ユーザＤの必要値に依存しない。なぜなら、ユーザＤの分岐（矢印の方向に進む）は、ユーザＡに戻らず、ユーザＤはこのため、ユーザＡを有利にすることから利益を得る立場でないからである。同様の理由で、ユーザＥのリソース割り当ては、ユーザＢの必要値に依存しない。従って、好適な実施形態では、これらのチェーン（またはこれらのチェーンにおけるリンクを構成するリソース）は、２つの別個のリソース・クラスタとして分析される。すなわち、第１はリソースＲ１〜Ｒ２を含み、第２はリソースＲ３〜Ｒ４を含む。第１のリソース・クラスタでは、その第１のリソース・クラスタにおけるリソース（Ｒ１およびＲ２）のいずれかについて、ユーザＡに、その必要値が少なくとも待機者（ＢおよびＣ）のうち必要度が高い方のものであるように、システム・リソースを割り当てる。同様に、第２のリソース・クラスタでは、その第２のリソース・クラスタにおけるリソース（Ｒ３およびＲ４）のいずれかについて、ユーザＥに、その必要値が少なくとも待機者（ＣおよびＤ）のうち必要度が高い方のものであるように、システム・リソースを割り当てる。
【００４０】
上述の例の全てにおいて、コンテンション・チェーンは非周期性である。これは、それらの矢印の方向に沿ってリンクを追うことによって閉鎖経路を形成することができないことを意味する。もしもかかる閉鎖経路があれば、リソース・デッドロックが生じる。これを遮断するには、このデッドロックに伴うユーザの１つ以上を終了させるしかない。
【００４１】
ここで、マルチシステム実施の詳細に移る。図７は、いくつかのシステム上でのトランザクションおよびリソース間の典型的なコンテンション状況を示す。図において、システムＳｙ１上のトランザクションＴｘＡ（必要値１）が、システムＳｙ２上のトランザクションＴｘＢ（必要値２）およびＴｘＤ（必要値４）によって保持されているリソースＲａを待っている。そして、システムＳｙ２上のトランザクションＴｘＢは、システムＳｙ３上のトランザクションＴｘＣ（必要値３）によって保持されるリソースＲｂを待っている。システムＳｙ３上のトランザクションＴｘＥ（必要値５）も同様である。
【００４２】
この例では、システムＳｙ１〜Ｓｙ３がコンテンションをどのように管理するかを例示するものとしてシステムＳｙ２を見る。本発明の１つの態様によれば、システムＳｙ２はシステムまたはリソース・クラスタにおけるコンテンションの完全な全体的ピクチャを保存も維持もしないが、以下のテーブルに示すように、かかるコンテンション情報のサブセットを保存および維持する。
【表１】
【００４３】
上のテーブルに示すように、システムＳｙ２は、保持者または待機者のいずれかとしてリソースを争っているそのローカル・トランザクションＴｘＢおよびＴｘＤについての完全な１組のコンテンション・データ（「ローカル・システム情報」）を保存する。ローカル・トランザクションがコンテンション状態にあるかかるリソースごとに、Ｓｙ２は、それらの固有の「必要」値を含めて、ローカル保持者および待機者を追跡する。また、システムＳｙ２は、リソースＲａおよびＲｂを共通リソース・クラスタＣａｂに割り当てている。なぜなら、少なくとも１つのローカル・トランザクション（ＴｘＢ）が、ある要求されたリソース（Ｒａ）の保持者であると共に別の要求されたリソース（ＴｘＢ）の待機者であるからである。
【００４４】
上のテーブルに示した、または他の方法でＷＬＭのローカル・インスタンスによって追跡された（そのようにそれを保存することによって、または必要に応じて他のデータからそれを導出することによってのいずれかで）データは、ローカル・リソース・クラスタ・データ、遠隔リソース・クラスタ・データ、および複合リソース・クラスタ・データを含む。ローカル・リソース・クラスタ・データは、ローカル・システム上のコンテンションに基づいてリソースをローカル・リソース・クラスタにグループ化することを示し、かかるローカル・リソース・クラスタごとに、ローカル・リソース・クラスタにおけるいずれかのリソースの最高必要度の待機者の必要値を示す。同様に、遠隔リソース・クラスタ・データは、特定の遠隔システムについて、遠隔システム上のコンテンションに基づいてリソースを遠隔リソース・クラスタにグループ化することを示し、かかる遠隔リソース・クラスタごとに、遠隔リソース・クラスタにおけるいずれかのリソースの最高必要度の待機者の必要値を示す。最後に、複合リソース・クラスタ・データは、対応するローカルおよび遠隔データを組み合わせることによって生成され、システム間のコンテンションに基づいてリソースを複合リソース・クラスタにグループ化することを示し、かかる複合リソース・クラスタごとに、複合リソース・クラスタにおけるいずれかのリソースの最高必要度の待機者の必要値を示す。
【００４５】
上のテーブルでは、「ローカル・システム情報」の見出しの下にある項目は、ローカル・リソース・クラスタ・データを表す。なぜなら、それらは、コンテンション下のリソースを待っているかまたはリソースを保持しているローカル・ユーザの意味でローカルなコンテンションのみに基づいているからである。あるリソースについて最高必要度のローカル待機者の必要値は、「ローカル・システム情報」の下の「待機者」欄を見ることによって確認することができる。このため、リソースＲａについて、ローカル待機者は存在しない（従って、「最高必要度」のローカル待機者は存在しない）が、リソースＲｂでは、最高必要度の待機者（ＴｘＢ）は必要値２を有する。ローカル・コンテンションに基づいてリソースをリソース・クラスタにグループ化することは、テーブルには明白に示さないが、ローカル・ユーザがあるリソースを保持するが他のものを待っているリソース・エントリ対を探すことによって得られる。このため、上のテーブルでは、リソースＲａの保持者およびリソースＲｂの待機者としてのユーザＴｘＢのリスト化が意味するのは、リソースＲａおよびＲｂをローカル・コンテンション・データに基づいて共通リソース・クラスタに割り当てるということである。
【００４６】
同様に、「遠隔待機者情報」の見出しの下の項目は、遠隔リソース・クラスタ・データを示す。なぜなら、それらは特定の遠隔システム上のコンテンションにのみ基づくからである。「システム名」欄において、リソースについてリスト化された各遠隔システムごとに、最高必要度の待機者の必要値を、隣接する「ＮＱＯ」欄に示す。特定の遠隔システムからのコンテンション・データに基づいてリソースをリソース・クラスタにグループ化することは、上のテーブルには示さないが、ローカルＷＬＭインスタンスによって追跡されるので、これを、ローカル・リソース・クラスタ割り当て情報と組み合わせて、複合リソース・クラスタ割り当てを得ることができる。リソース・クラスタの組み合わせは、直接的に行われる。このため、第１のシステムがリソースＡおよびＢを（そのローカル・コンテンション・データに基づいて）共通リソース・クラスタに割り当てる場合、第２のシステムは同様にリソースＢおよびＣを共通リソース・クラスタに割り当て、第３のシステムはリソースＣおよびＤを共通リソース・クラスタに割り当て、この結果、複合リソース・クラスタはリソースＡ、Ｂ、Ｃ、およびＤを含む。
【００４７】
一方、最初の欄（「リソース・クラスタ」）は、複合リソース・クラスタ・データを表す。なぜなら、そのリソースのリソース・クラスタへの割り当ては、ローカル・リソース・クラスタ・データおよび遠隔リソース・クラスタ・データの双方に基づくからである。最後の欄（「ＮＱＯ」）は、同様に複合リソース・クラスタ・データを表す。なぜなら、リスト化された必要値は、全システム中でリソースについての最高必要度の待機者のものだからである（ローカル・システムに報告されたように）。
【００４８】
システムＳｙ２は、上に示した表の形態でコンテンション・データを保存することができるが、より典型的には、かかるデータを多数のデータ構造に分散させて、操作の容易さを最適化する。これについては、以下で更に述べる。
【００４９】
図８は、ローカル・リソース・マネジャからのコンテンション通知に応答して、ＷＬＭのローカル・インスタンスが実行する全体的な手順５００を示す。特定のステップ・シーケンスを説明するが、各ステップを実行する場合に必要な入力データが利用可能である限り、シーケンスは変更することができる。
【００５０】
手順５００が開始するのは、ＷＬＭインスタンスがリソースのコンテンション状態の変化の通知をローカル・リソース・マネジャから受信し、それがローカル・ユーザに関連する場合である。かかる変更は、以下のいずれかを表すことができる。
【００５１】
１．ローカル・ユーザが別のユーザによって保持されるリソースの待機者になった。
２．ローカル・ユーザがもはやリソースの待機者ではない。この理由は、それが保持者としてリソースを取得したからか、または、それがもはや保持者または待機者のいずれかとしてリソースに関心がなくなったからである（おそらく、これが終了し、従ってもはや存在しないからである。これについては以下の例で説明する）。
３．ローカル・ユーザによって保持されるリソースが現在コンテンションの状態にある。
４．ローカル・ユーザによって保持されるリソースがもはやコンテンションの状態にない。
【００５２】
ローカル・リソース・マネジャからの通知は、リソースと同様に、ローカル保持者および待機者を識別する。好適な実施形態では、ＷＬＭは、別個には示さないＳＲＭコンポーネントから、これらの保持者および待機者の各「必要値」を取得する（それらの固有の必要値であり、本発明に従って変更した必要値ではない）。しかしながら、このデータの特定のソースは、本発明の部分を形成しない。
【００５３】
リソース・マネジャ・インスタンスからのかかる通知の受信に応答して、ＷＬＭのローカル・インスタンスは、まず、対象のリソースについてのローカル・コンテンション・データを更新する（ステップ５０４）。かかる更新は、ローカル・システム上で新たにコンテンション状態になったリソースのための新しいエントリの生成、ローカル・システム上ですでにコンテンション状態にあるリソースのための既存のエントリの変更、またはローカル・システム上でもはやコンテンション状態にないリソースのための既存のエンティティの消去を含むことができる。このローカル・コンテンション・データは、リソースを保持または待機しているいずれかのローカル・ユーザの識別と共に、かかるユーザの「必要値」も含む。
【００５４】
ローカル・コンテンション・データを更新した後、ＷＬＭのローカル・インスタンスは、必要な場合、リソースのリソース・クラスタ割り当てを更新する（ステップ５０６）。デフォルトでは、リソースは、メンバとしてそれ自身のみを含むトリビアルなリソース・クラスタに割り当てられる。かかる割り当てが、ローカル・コンテンション・データまたは遠隔コンテンション・データのいずれかによって指示される場合、リソースは、少なくとも１つの他のリソースを含む非トリビアルなリソース・クラスタに割り当てられる。ローカル・コンテンション・データによって、同じローカル・ユーザがリソースのうちあるものを保持するが他のものを待っていることが示される場合、すなわち、そのリソースが他のリソースを待っているユーザによって保持されるか、または他のリソースを保持しているユーザによって待たれていることが示される場合、リソースは、そのデータに基づいて、別のリソースを含むリソース・クラスタに割り当てられる。遠隔コンテンション・データデータによって、少なくとも１つの遠隔システムが、その遠隔システムにローカルなコンテンション・データに基づいて２つのリソースを共通リソース・クラスタに割り当てたことが示される場合、リソースは、そのデータに基づいて、別のリソースを含むリソース・クラスタに割り当てられる。このリソース・クラスタ割り当てステップは、従って、以下を含む場合がある。（１）リソースのためのリソース・クラスタ割り当てを不変のままとする、（２）変更したローカル・コンテンション・データおよびいずれかの既存の遠隔コンテンション・データがかかる割り当てを指示する場合、リソースを非トリビアルなリソース・クラスタに新たに割り当てる、または（３）変更したローカル・コンテンション・データおよびいずれかの既存の遠隔コンテンション・データがもはやかかる割り当てを指示しない場合、既存のリソース・クラスタを分解する。リソースのリソース・クラスタ割り当てが変更されると、この変更によって影響を受ける他のリソースのためのリソース・クラスタ情報は、この時点で同様に変更される。
【００５５】  
同時に、ＷＬＭのローカル・インスタンスは、リソースのローカル・コンテンション・データのみに基づいているリソースの帰属「必要」値を更新する（ステップ５０８）。この帰属必要値は、リソースのローカル・コンテンション・データが示すように、リソースのいずれかのローカル待機者の必要値のうち最大のものである。このステップは、リソース・クラスタ割り当てステップの後に続くものとして示すが、ステップの順序は重要でない。なぜなら、どのステップも他のステップの結果を用いないからである。
【００５６】
リソース・クラスタ割り当ておよびリソースの帰属必要値を更新した後のある時点で、ＷＬＭのローカル・インスタンスは、その複合リソース・クラスタ・データを更新する。これは、以下を含む。（１）ローカルおよび遠隔コンテンション・データの双方に基づいた、リソースの帰属必要値（上のテーブルにおける「ＮＱＯ」）、（２）ローカルおよび遠隔コンテンション・データの双方に基づいた、リソースの複合クラスタへのグループ化、（３）全体としてのリソース・リソース・クラスタの帰属「必要」値（ステップ５１０）。最後に挙げたものは、単に、複合リソース・クラスタを形成するリソースのいずれかの必要値のうち最大のものであり、ここで、必要値は、リソース・クラスタを形成するリソースのための遠隔およびローカル・コンテンション・データに基づいている。
【００５７】
次いで、ＷＬＭのローカル・インスタンスは、その更新したローカル・コンテンション・データの要約を、システム・クラスタにおける他のシステムに同報通信する（ステップ５１２）。このデータ要約は以下を含む。
１．ローカル・システム名。
２．リソース名。リソースがマルチシステム・リソースである場合、リソース名は、システム・クラスタ中で認識されるようなリソースの実際の名前である。リソースがローカル・リソースである場合、リソース名は、実際のローカル・リソース名のための「プロキシ」として機能する総称のローカル・リソース名である。これについては、以下の例２において説明する。
３．リソースを割り当てるリソース・クラスタを識別するリソース・クラスタＩＤ。この値は、厳密にはローカルである。受信側システムは、この値を比較して、２つのリソースが送信側システム上の同一リソース・クラスタに属するか否かを調べるが、この値の構造または内容に関していかなる想定も行わない。以下の例では、リソース・クラスタ名を、リソース・クラスタにおけるマルチシステム・リソースの連結として与え、純粋に簡略記憶デバイスとして、読み取り側の理解を容易にする。しかしながら、好適な実施形態では、「リソース・クラスタ名」は、実際には不明瞭な「リソース・クラスタＩＤ」であり、受信側システムは、単に、同一の送信側システム上で生じる他のリソース・クラスタＩＤとの同等性について試験を行うことができるのみである。
４．送信側システムの「ローカル・システム情報」のみに基づいたリソースのための「必要値」、すなわち、リソースのための最高必要度のローカル待機者。これは、そのデータのみを考慮していた場合にその必要値がどうあるべきかこのシステムが考える表明方法と見なすことができる。リソースのためのローカル待機者が存在しない場合、ローカル必要値が存在しないことを示すダミー値を送信する。これについては、以下の例１において説明する。
５．送信側システムのいずれかのトランザクションがリソースをリソース・クラスタ内に含ませるか否か、すなわち、ローカル・コンテンション・データに基づいてリソースを非トリビアルなリソース・クラスタに割り当てているか否かの指示。これはブール値であるが、イエス／ノーではなく、この記載においてローカル／遠隔の値を与えられる。ローカルが意味するのは、（１）送信側システムが、あるリソースの待機者および別のリソースの保持者の双方である少なくとも１つのトランザクションを有すること、および（２）同じトランザクションがこのリソースの待機者または保持者のいずれかであること（このため、送信側システムは、トランザクション（複数のトランザクション）に接続したリソース・グループが１グループとして管理されることを必要とする）である。遠隔が意味するのは、送信側システムのローカル・データにおいて、リソースが非トリビアルなリソース・クラスタの一部であることを要求するものがないことを意味する。トリビアルなリソース・クラスタは、正確に１つのリソースを有し、常に「遠隔」の値を有してリソース・クラスタリング・コードを少し容易にする。
【００５８】
リソース・クラスタ再割り当てがあった場合、ＷＬＭは、その再割り当てによって影響を受ける他の各リソースごとに同様の情報を同報通信する。
【００５９】
最後に、ローカルＷＬＭインスタンスは、ローカル・ユーザの「必要」値に対していずれかの必要な調整を行う（ステップ５１４）。より具体的には、ＷＬＭは、あるリソースのローカル保持者であると共に別のリソースの待機者ではないもの（このため、コンテンション・チェーンの頭部にある）の「必要値」を調整し、これが、リソースを含むリソース・クラスタにおける最高必要度の待機者の固有の必要値に少なくとも一致するようにする。調整した値は、システム・リソースを保持者に割り当てるために実際に用いられる帰属「必要」値であり、そのユーザに割り当てられる（更に他のユーザに値を帰属するために用いられる）固有の必要値ではない。このため、特定の必要値を帰属させる理由がなくなると、ユーザに帰属した必要値は固有の必要値またはもっと小さい帰属必要値のいずれかに戻る。
【００６０】
図９は、全体的な手順６００を示し、遠隔システム上のＷＬＭインスタンスからの遠隔コンテンション・データの同報通信の受信（６０２）に応答して、ＷＬＭのローカル・インスタンスが実行する。この同報通信は、影響を受けた各リソースごとに、ステップ５１２の説明においてリスト化した情報を含む。
【００６１】
かかる通知の受信に応答して、ＷＬＭのローカル・インスタンスは、まず、対象のリソースの遠隔コンテンション・データを更新する（ステップ６０４）。ステップ５０４で説明したローカル・コンテンション・データの更新の場合と同様、かかる更新は、ローカル・システム上で新たにコンテンション状態になったリソースのための新しいエントリの生成、ローカル・システム上ですでにコンテンション状態にあるリソースのための既存のエントリの変更、またはローカル・システム上でもはやコンテンション状態にないリソースの既存のエンティティの消去を含むことができる。この遠隔コンテンション・データは、リソースの待機者を有するいずれかの遠隔システムの識別と共に、リソースについての遠隔システム上の最高必要度のかかる待機者の必要値を含む。
【００６２】  
リソースのその遠隔コンテンション・データを更新した後、ステップ５１０において行ったのと同様に、ＷＬＭのローカル・インスタンスは、リソースのその複合リソース・クラスタ・データを更新する。ステップ５１０においてと同様、更新された複合リソース・クラスタは以下を含む。（１）ローカルおよび遠隔コンテンション・データの双方に基づいた、リソースのための帰属必要値、（２）ローカルおよび遠隔コンテンション・データの双方に基づいた、リソースの複合リソース・クラスタへのグループ化、および（３）ローカルおよび遠隔コンテンション・データに基づいた、全体としてのリソース・クラスタのための帰属「必要」値（ステップ６０６）。
【００６３】
最後に、ステップ５１４におけるように、ローカルＷＬＭインスタンスは、ローカル・ユーザの「必要」値に対していずれかの必要な調整を行うため、あるリソースのローカル保持者であると共に別のリソースの待機者ではないもの（このため、コンテンション・チェーンの頭部にある）の「必要値」を調整し、これが、リソースを含むリソース・クラスタにおける最高必要度の待機者の固有の必要値に少なくとも一致するようにする（ステップ６０８）。
【００６４】
詳細な例および状況は、以下の通りである。
【００６５】
例１（「単純な」推移的終了の場合）
この例は、システム間の推移的終了の場合である。２つ以上のリソースが関与する。あるリソースを保持する必要度の低いユーザを支援して、異なるリソースを待っている別の（必要度の高い）ユーザを動かす。トポロジはマルチシステムであり、同一リソースの保持者および待機者が異なるシステム上にある。
【００６６】
これは、同一リソース・リソース・クラスタにマルチシステム・リソースのみが含まれる場合に何が起こるかを示すので、「単純な」推移的終了の場合である。
【００６７】
この例では、表記は以下の通りである。各保持者および待機者はトランザクションであり（Ｔｘｎ、例えばＴｘＡ、ＴｘＢ）、ＮＱＯ（eNQueue Order）値を有する。ＮＱＯ値は、値が小さくなるほど必要度が高い（多くの支援を受けることに値する）ようになっている。各システムに付番し（Ｓｙ１、Ｓｙ２）、これらのシステムは全て同一の「システム・クラスタ」内にある。各リソースは小文字を有し（Ｒａ、Ｒｂ）、対象範囲においてマルチシステムである。各リソース・クラスタは、１つ以上の小文字を有し（Ｃａ、Ｃａｂ）、リソース・クラスタ内のリソースのリストを示す。リソースを得るための要求は、特に注記しない限り、排他的制御のためである。
【００６８】
イベントのシーケンスは、時間順に、以下の通りである。
【表２】
【００６９】
ｔ＜６では、コンテンションが存在しないので、いずれのシステム上でもＷＬＭコンテンション・データは存在しない。
【００７０】  
ｔ＝６では、コンテンションが生じる（Ｓｙ１：ＴｘＢはＲｂを要求し、ＴｘＣがそれを保持するので保留される）。この結果、Ｓｙ１は、
１．リソースＲｂのためのコンテンション追跡を開始する。
２．Ｒｂのみから成るリソース・リソース・クラスタを生成する。
３．Ｒｂのローカル待機者リストにＴｘＢを加える。
【００７１】
この時点で、Ｓｙ１の状態は以下の通りである。
【表３】
【００７２】
Ｓｙ１が次にそのリソース・トポロジを再評価する場合、ＣｂのＮＱＯを計算する。
１．Ｓｙ１が知っているＲｂのトポロジに含まれる最高必要度のエンティティ（実際、この時点で１つのみ）はＴｘＢであるので、これは、ＲｂのＮＱＯとして、ＴｘＢのＮＱＯ（４）を用いる。
２．Ｃｂにおける全リソースについてＮＱＯを計算したので、これは、Ｃｂにおける全リソースＮＱＯの最高必要度のものとしてＣｂのＮＱＯを計算する。これによって、ＲｂからＣｂまでＮＱＯ４を伝搬させる。  
３．Ｒｂはマルチシステム・リソースであるので、Ｓｙ１はＲｂの情報をシステム・リソース・クラスタにおける他の全システムに同報通信する。上述のように、Ｒｂについて送信された情報は、システム名、リソース名、リソース・クラスタＩＤ、送信側システムの「ローカル・システム情報」のみに基づいたリソースのＮＱＯ、および、「ローカル」に送信された場合は送信側システムのトランザクションがリソースをリソース・クラスタ内に含ませることを示すブール値（ローカル／遠隔）を含む。
４．上述の説明に基づいて、送信されるデータは、Ｓｙ１、Ｒｂ、Ｃｂ、４、遠隔である。
【００７３】
この時点で、Ｓｙ１の状態は以下の通りである。
【表４】
【００７４】
Ｓｙ２はこの情報を受信する。同時に、Ｓｙ２上で実行しているリソース・マネジャ・インスタンスは、ＲｂのコンテンションをＳｙ２に通知する。動作の順序は関係ないが、それらは先に記載した順序でリスト化される。コードにおける唯一の「秘訣」は、Ｓｙ２上のリソース・マネジャが競争に勝った場合、遠隔データが到着した際に、コードは、それがすでに等価のリソース・クラスタを構築したことを認識し、その既存データに遠隔情報を追加しなければならないことである。
【００７５】
Ｓｙ１から遠隔情報を受信した後、Ｓｙ２の状態は以下の通りである。
【表５】
【００７６】
いったんＳｙ２のローカル・リソース・マネジャがＳｙ２にＲｂのコンテンションを通知すると、Ｓｙ１およびＳｙ２の状態は以下の通りである。    
【表６】
【表７】
【００７７】
ＲｂについてのＳｙ２のローカルＮＱＯが４であり、ＴｘＣのＮＱＯである５ではないことに留意すべきである。第１に、リソース保持者のＮＱＯ（複数のＮＱＯ）は、リソースのＮＱＯに影響を与えない。なぜなら、保持者が実行しているからである。ＷＬＭのポリシ調整コードは、すでにＮＱＯを自動的に用いている。第２に、Ｓｙ２はこの時点で、システム・クラスタ内のどこか他の所で、ＮＱＯ４のトランザクションが待機しているのを知っている。４は５よりも必要度が高いと規定されているので、ＲｂのＮＱＯは４以上の必要度を有しなければならない。
【００７８】
ｔ＝７では、別のリソース上でコンテンションが生じる（Ｓｙ２：ＴｘＡはＲａを要求し、ＴｘＢがそれを保持するので保留される）。図１０は、ｔ＝７の後のトポロジを示す。
【００７９】
また、リソースＲａはマルチシステム対象範囲を有するので、この結果、Ｒｂについて起こったのと同様のハンドシェーキングが生じる。この結果、以下の通りとなる。
【表８】
【表９】
【００８０】
いったんＳｙ１上のリソース・マネジャ・インスタンスがＳｙ１にＲａのコンテンションを通知すると、Ｓｙ１はＣａおよびＣｂをリンクして（新しい）クラスタＣａｂにする重要なステップを行う。Ｒａのコンテンションについて単に通知した後、有効な（しかしこれまでのところ不完全な）状態は、以下の通りである（これらが２つの別個のステップであるか１つの統合されたステップであるか、コード実施によって異なる。それらは別個に示す）。
【表１０】
【００８１】
Ｓｙ１が次にそのトポロジを再評価する場合、これは、ローカル情報に基づいて、単一のトランザクション（ＴｘＢ）に２つの異なるリソース（ＲａおよびＲｂ）が関与することを知っており、従ってそれらのリソースの管理を統合しなければならない（換言すると、ＲａおよびＲｂは同一のリソース・クラスタＣａｂ内になければならない）。リソース・クラスタのＮＱＯは、そのメンバ・リソースのうち最高必要度のＮＱＯである（この場合は１）。
【表１１】
【００８２】
ＲａおよびＲｂが共に管理されなければならないという「信号」は、コンテンション状態の１つ以上のリソースを保持していると共にコンテンション状態の１つ以上の他のリソースを待機している少なくとも１つのトランザクションの存在である。
【００８３】
そのトポロジのビューを再評価した後、Ｓｙ１（以前と同じ）は、そのビューをシステム・クラスタ内の他のシステムに同報通信する。
１．Ｓｙ１、Ｒａ、Ｃａｂ、ダミーＮＱＯ値、ローカル。
２．Ｓｙ１、Ｒｂ、Ｃａｂ、４、ローカル。
【００８４】
ダミーＮＱＯ値は、単に、ＷＬＭが生成可能であるものよりも必要度が低いものである。Ｓｙ１は、純粋にローカルなＮＱＯ値を有しない。なぜならこれはローカル待機者を有しないからであるが、これはそのローカル・データに基づいてＲａおよびＲｂを１つの単位として管理しなければならないという「バーチャル・メッセージ」を送信する必要がある。
【００８５】
Ｓｙ２は、データ（ＲａおよびＲｂを１つの単位として管理しなければならず、ＣａおよびＣｂをマージしなければならないことを意味する事実を含む）を統合し、以下を生成する。
【表１２】
【００８６】
ここで、双方のシステムは、どちらも完全なトポロジのコピーを有しないとしても、問題の重要性について了解している（すなわち、最高必要度の待機者のＮＱＯ値）。
【００８７】
ｔ＝１０では、コンテンションはほぐれ始める（Ｓｙ２：ＴｘＣはＲｂを解放する）。Ｓｙ２のＲｂのビューは、ここで、遠隔データのみを含む。
【表１３】
【表１４】
【００８８】
ｔ＝１１では、Ｓｙ１上のリソース・マネジャ・インスタンスは、Ｒｂが利用可能であることを見出し、そのキュー上の第１の待機者にこれを与える（Ｓｙ１：ＴｘＢを再開しＲｂを取得する）。リソース・マネジャの待機キューはこの時点で空であるので、これはＷＬＭに通知して、Ｒｂのコンテンションが終わったことを示す。Ｓｙ１は、そのリソース・クラスタからＲｂを除去する。なぜなら、各システム内で、どの単一リソースも単一リソース・クラスタにのみ属することができるからである（しかし、タイミング・ウインドウのため、２つのシステムが異なるリソース・クラスタ内に同一リソースを有する場合がある）。
【表１５】
【００８９】
平行して、Ｓｙ２上のリソース・マネジャ・インスタンスは、Ｒｂがもはやコンテンション状態にないことを知らされ（リソース・マネジャ実施に応じて、これはｔ＝１０の時に行われた可能性もある）、これは、また、そのリソース・トポロジからＲｂを除去する。
【表１６】
【００９０】
ｔ＝１２では、解放されたリソースはもはやコンテンションの状態でないので、変化はない（Ｓｙ１：ＴｘＢはＲｂを解放する）。
【００９１】
ｔ＝１３では、コンテンションは完全にほぐれる（Ｓｙ１：ＴｘＢはＲａを解放する）。Ｓｙ１上のリソース・マネジャは、ＷＬＭに通知して、Ｒａのコンテンションの終了を伝える。
【表１７】
【００９２】
ｔ＝１４では、Ｓｙ２はコンテンションの終了も見る（Ｓｙ２：ＴｘＡが再開され、Ｒａを取得する（コンテンションなし））。Ｓｙ２上のリソース・マネジャ・インスタンスは、ＷＬＭに通知して、Ｒａのコンテンションの終了を伝える。
【表１８】
【００９３】
例２（ローカル・リソースによる推移的終了の場合）
この例は、別のシステム間推移的終了の場合である。２つ以上のリソースが関与する。異なるリソースを待っている（必要度の高い）ユーザを動かすため、あるリソースを保持する必要度の低いユーザを支援しなければならない。トポロジは、この場合もマルチシステムであり、同じリソースの保持者および待機者が異なるシステム上にある。更に、例１とは異なり、各システムは、純粋にローカルな（非マルチシステムの）リソース上で同一のトランザクションを伴うコンテンションを有する。これによって、マルチシステムおよび単一システム・リソースの双方が同一のリソース・クラスタに関与する場合に何が起こるかを示す。  
【００９４】
表記は例１と同じであるが、マルチシステム・リソースは大文字のＲ（Ｒａ、Ｒｂ）を用い、ローカル・リソースは小文字のｒ（ｒｃ、ｒｄ）を用いる。Ｒｌｏｃａｌ（＝ＲＬ）は、「遠隔システムに対して対象範囲においてローカルな何らかの未知の組のリソース」のためのプロキシ名である。実際の値は無関係であり、唯一の要件は、全ての参加者が値を了解し、いずれかの有効リソース名と衝突することが可能でないことである。
【００９５】
イベントのシーケンスは、時間順に、以下の通りである。
【表１９】
【００９６】
ｔ＜８では、各システム上のコンテンション状態は例１と全く同じであり、従ってここでは説明しない。
【００９７】
ｔ＝８では、ローカル（非マルチシステム）リソースｒｌ（Ｓｙ１：ＴｘＳはｒｌを要求し、ＴｘＢがこれを保持するので保留される）でコンテンションが生じる。リソースｒｌは、Ｓｙ１のみの上でリソース・クラスタに統合される。ｒｌのＮＱＯは、ＴｘＳから、３であるが、リソース・クラスタＣａｂｌはＲａのためにいまだＮＱＯが１である。
【表２０】
【００９８】
Ｓｙ１がそのリソース・クラスタのビューを同報通信する場合、これは直接ｒｌを同報通信しない。なぜなら、ＲａおよびＲｂは他のシステムに可視的であり得るリソース・クラスタ内の唯一のリソースであるからである。その代わり、これは、Ｓｙ１のローカル・リソースの全て（我々はｒｌのみと知っている）についてのプロキシ（Ｒｌｏｃａｌ）を同報通信する。
１．Ｓｙ１、Ｒａ、Ｃａｂｌ、ダミーＮＱＯ値、ローカル。
２．Ｓｙ１、Ｒｂ、Ｃａｂｌ、４、ローカル。
３．Ｓｙ１、Ｒｌｏｃａｌ、Ｃａｂｌ、３、ローカル。
【００９９】
このデータを受信し、そのトポロジを更新した後、Ｓｙ２はこれがその状態であると考える。
【表２１】
【０１００】
ｔ＝９では、別のローカル・リソースが、他のシステム上のコンテンションを示す（Ｓｙ２：ＴｘＴはｒｊを要求し、ＴｘＡがそれを保持するので保留される）。図１１は、ｔ＝９の後のトポロジを示す。
【０１０１】
Ｓｙ１に行ったのと同様の処理がＳｙ２について生じ、次いでＳｙ２はそのデータをＳｙ１に同報通信する。Ｓｙ２は以下を同報通信する。    
１．Ｓｙ２、Ｒａ、ＣａｂＬ、１、ローカル。
２．Ｓｙ２、Ｒｂ、ＣａｂＬ、ダミーＮＱＯ値、遠隔。
３．Ｓｙ２、Ｒｌｏｃａｌ、ＣａｂＬ、２、ローカル。
【０１０２】
上述の同報通信では、Ｓｙ２上のローカル・リソースのためのプロキシの名前はリソース・クラスタ名によって自動的に認定される。なぜなら、下に示すように、プロキシは、全体としてのシステム・クラスタでなく各リソース・クラスタごとに規定されるからである。また、ＲａおよびＲｌｏｃａｌのための同報通信のみがブール値「ローカル」を含む。なぜなら、これら２つのリソースのみが、ローカル・データに基づいて共通のリソース・クラスタに割り当て可能だからである。
【表２２】
【表２３】
【０１０３】
Ｓｙ２上のＲｌｏｃａｌの「遠隔待機者情報」に「Ｓｙ２、２」エントリを追加すること、またはＳｙ２上の「ローカル・システム情報．待機者」にダミー・トランザクションを追加することによって、全てのローカル・リソース・コンテンションを要約できない理由はない。上のテーブルは、この最適化なしに示す。上述の方法の１つによってＲｌｏｃａｌにローカル状態データを要約させることは、おそらく同報通信コードをもっと簡単にするであろう。そして、Ｒｌｏｃａｌは、マルチシステム対象範囲で生成することができ、同報通信における特別な場合は必要ない。明らかに特別な場合とする必要がある他の場合がある。実際、単にシステム当たり１つではなく、リソース・クラスタ当たり１つのＲｌｏｃａｌを可能としなければならない。
【０１０４】
ｔ＝１０では、コンテンションはほぐれ始める（Ｓｙ２：ＴｘＣはＲｂを解放する）。Ｓｙ２のＲｂのビューは、ここで、遠隔データのみを含む。
【表２４】
【表２５】
【０１０５】
ｔ＝１１では、Ｓｙ１上のリソース・マネジャ・インスタンスは、Ｒｂが利用可能であることを見出し、そのキュー上の第１の待機者にそれを与える（Ｓｙ１：ＴｘＢを再開しＲｂを取得する）。リソース・マネジャの待機キューはこの時点で空であるので、これはＷＬＭに通知して、Ｒｂのコンテンションが終わったことを示す。平行して、Ｓｙ２上のリソース・マネジャ・インスタンスは、Ｒｂがもはやコンテンションの状態にないことを知らされる（リソース・マネジャ実施に応じて、これはｔ＝１０の時に行われた可能性もある）。双方のシステムは、そのリソース・クラスタからＲｂを除去しなければならない。なぜなら、各システム内で、どの単一リソースも単一リソース・クラスタにのみ属することができるからである。２つのシステムは、タイミング・ウインドウのため一時的に、またはリソース・トポロジのため永久的に、同一の瞬間に異なるリソース・クラスタ内に同一のリソースを有する場合がある。３つ以上のシステムが関与する場合に、非対称トポロジの例が現れる。
【表２６】
【表２７】
【０１０６】
ｔ＝１２では、解放されたリソースはもはやコンテンション状態にないので、変化はない（Ｓｙ１：ＴｘＢはＲｂを解放する）。
【０１０７】
ｔ＝１３では、マルチシステム・コンテンションは完全にほぐれる（Ｓｙ１：ＴｘＢはＲａを解放する）。Ｓｙ１上のリソース・マネジャ・インスタンスは、ＷＬＭに通知して、Ｒａのコンテンションの終了を伝える。
【０１０８】
Ｓｙ１上のリソース・クラスタは、この時点で、ローカル・リソースおよびマルチシステム・コンテンションに関与する遠隔ローカル・リソースのためのプロキシのみから成るので、プロキシもリソース・クラスタから除去することができる。Ｓｙ２にＲａのコンテンションの終了が通知されたので、これはそのプロキシ・リソースをリソース・クラスタの一部として維持する。
【表２８】
【表２９】
【０１０９】
ｔ＝１４では、Ｓｙ２もコンテンションの終了を見る（Ｓｙ２：ＴｘＡは再開されＲａを取得する）。Ｓｙ２上のリソース・マネジャ・インスタンスはＷＬＭに通知して、Ｒａのコンテションの終了を伝える。
【表３０】
【０１１０】
ｔ＝１５では、ＴｘＳでのローカル・リソース終了の１つでのコンテンション（Ｓｙ１：ＴｘＢはｒｌを解放する）が再開する。いったんリソース・マネジャがＳｙ１にｒｌのコンテンションが終わったことを通知すると、Ｓｙ１のトポロジは再び空になる。
【０１１１】
ｔ＝１７では、コンテンションの最後が終了し（Ｓｙ２：ＴｘＡはｒｊを解放する）ＴｘＴが再開する。いったんリソース・マネジャがＳｙ２にｒｌのコンテンションが終わったことを通知すると、Ｓｙ２のトポロジは再び空になる。
【０１１２】
例３：リソース・クラスタの分解（ＢｒｅａｋＣｌｕ１）
この例は、関与するリソースのいずれかについてのコンテンションの終了なしで、リソース・クラスタをより小さいリソース・クラスタに分解することを含む。ＲａおよびＲｂをリンクするトランザクションは取り消されるが、各リソースは他の待機者を有するので、双方のリソースはその後まだコンテンション状態にある。表記は例１と同様である。
【０１１３】
イベントのシーケンスは、時間順に、以下の通りである。
【表３１】
【０１１４】
ｔ＜４では、コンテンションが存在しないので、いずれのシステム上でもＷＬＭコンテンション・データは存在しない。
【０１１５】  
ｔ＝４およびｔ＝７間で生じるイベントは、先の例においてカバーされている。図１２は、ｔ＝７後のトポロジを示す。この時点での状態データは以下のように見える。
【表３２】
【表３３】
【０１１６】
トランザクションＴｘＤがｔ＝８で終了すると（どんな理由であっても）、各システム上のリソース・マネジャ・インスタンスは、ＴｘＤが有する残っている全ての待機要求を除去し（Ｒａ）、それが保持する全てのリソースを解放する（Ｒｂ）。いったんＷＬＭにこれらのトポロジ変更が通知されると、Ｓｙ１は、リソース・クラスタＣａｂが２つの断片（ＣａおよびＣｂ）に分解されることを知っている。これを知っている理由は、その２つがリンクすることをＳｙ１がローカルに決定したからであり（更に、これがもはやローカルに真でないことを理解することができる）、遠隔システムのどのデータも、それらをリンクしなければならないことを示さない。しかしながら、双方のリソースはいまだコンテンション状態にある。次にＳｙ１がそのトポロジ・データを同報通信する時、Ｓｙ２上の「Ｓｙ１：Ｒａ、Ｒｂリンク」データを除去し、Ｓｙ２もそのトポロジを更新する。リソース・マネジャ・インスタンスが所有権を再割り当てする前にＷＬＭがこの全てを達成すると仮定すると、結果として状態は以下の通りである。
【表３４】
【表３５】
【０１１７】
そして、これが示すのは、関与するリソースの１つについてコンテンションの終了に依存するのではなく、ＲａおよびＲｂを共に管理しなければならない「メモリ」を除去するための何らかの機構を有することである。いくつかの代替を示す。
【０１１８】  
１．Ｓｙ１は、明示的にデータを送信し、これがもはや所与のリソース・クラスタが必要であると考えないことを示す。例えば、Ｒａ、Ｃａ、４、遠隔を送信する。Ｓｙ２がＲａのためのＳｙ１の早期データに取って代わると、これはもはやＳｙ１から来るＲａおよびＲｂを共に管理する要求を見ない。Ｓｙ２がリソース・クラスタを継続するための他の「表明方法」を有しない場合、Ｓｙ２はローカルにリソース・クラスタを分解することができる。
２．Ｓｙ１のデータは古くなる（このため、「すぐに」置換されない場合これは消去される）。これは、おそらく、「有効期間（ＴＴＬ：time to live）」値を送信することによって実施され、その後にデータは受信者によって消去される。この機構は、故障したシステム、失われた信号、バグ、回復問題等についての安全策も提供することができる。また、ＴＴＬは、通信レイテンシを透明にするという利点を有し、送信者および受信者が共通の間隔を了解する必要がない。
【０１１９】
最もロバストな解決策は、おそらく、全て３であろう。コンテンションの終了を伝えるリソース・マネジャに、我々が「Ｒａ」ブロックをローカルに消去するケースをグローバルに処理させるので、「リソース・クラスタを分解」メッセージを送信するため充分に長く保持する必要はない。リソースのコンテンションがローカルには終了するが遠隔では終了しない場合、および、ローカル・システムが、表明方法が非トリビアルなリソース・クラスタを構築することを強制したものであった場合、ＴＴＬ値に、遠隔システム上でリソース・クラスタの分散を生じさせる。リソース・クラスタを分解させる必要があるがコンテンションが終了しない場合、我々は「Ｒａ」ブロックをいまだ有し、「リソース・クラスタを分解する」メッセージは我々が送信するものの当然の結果である。
【０１２０】
例４：リソース・クラスタの分解（ＢｒｅａｋＣｌｕ２）
この例では、共通の保持者（複数の保持者）によって結合したリソース・クラスタを、「ｎ」個のリソースから成る１つのリソース・クラスタとして、または各々１リソースから成る「ｎ」個のリソース・クラスタとして処理することができる。この結果は、記すに値する驚くべきものである。
【０１２１】
表記は例１と同様である。
【０１２２】
イベントのシーケンスは、時間順に、以下の通りである。
【表３６】
【０１２３】
図１３は、ｔ＝６の後のトポロジを示す。
【０１２４】
ｔ＝６まで生じるイベントは、先の例でカバーされている。ここで興味深いのは、どのように事柄を規定したかに応じて、この状況を、１つのリソース・クラスタまたは２つのいずれかとして処理することができることである。１つのリソースの保持者としておよび異なるリソースの待機者として同じトランザクションを有するシステムによってリソース・クラスタを識別可能であるという先の例からの規定を用いる（そして、システム・クラスタ内の全システムを通してこの知識を集約する）場合、上の図は、明らかに、予想可能なものでなく、２つのリソース・クラスタを図示する。
【０１２５】
リソース・クラスタＣａｂを形成する際に値は存在せず、そうする際に伴うオーバーヘッドが存在するので（更に正確には、リソース・クラスタを分解するか否かを決定する場合に伴うオーバーヘッドがある）、この規定を使用し続ける。従って、上の図に対応する状態データは、以下の通りである。    
【表３７】
【表３８】
【０１２６】
この規定に固有の想定は、ＷＬＭが作業を支援しようとする場合、各リソースを調べ、ＮＱＯ値に基づいて必要な場合に保持者（複数の保持者）を支援する。このトポロジが単一リソース・クラスタとして扱われた場合、ＴｘＡはリソース・クラスタＣａｂからＮＱＯ１を引き継ぐ。これを２つのリソース・クラスタとして処理して、ＷＬＭは以下の結論を出さなければならない。
１．Ｃａは支援を必要としない。なぜなら、保持者のＮＱＯ３はリソース・クラスタのＮＱＯ４より必要度が高いからである。
２．Ｃｂは支援を必要とする。なぜなら、リソース・クラスタのＮＱＯ１はＴｘＡのＮＱＯ３より必要度が高いからである。
【０１２７】
この状況が１または２のリソース・クラスタとして扱われるか否かには関係なく、ＴｘＡはＮＱＯ１の引き継ぎで終わるので、いずれかを選択することができる。２つの「トリビアルな」（単一リソース）リソース・クラスタの管理は、複合を分解する必要がある場合のテストのため、単一の複合リソース・クラスタよりも効率的であるので、この場合は２つのトリビアルなリソース・クラスタとして扱われる。
【０１２８】
例５：単純な３ウエイ状況（３ｗａｙＥａｓｙ）
この例は、単純な３システムの状況である。また、これは、推移的終了の場合であるが、その非対称トポロジによって、システムは、リソース・マネジャから来るローカル待機者／保持者情報を有しないリソースを追跡させられる。表記は例１と同様である。
【０１２９】
イベントのシーケンスは、時間順に、以下の通りである。
【表３９】
【０１３０】  
ｔ＝５まで生じるイベントは、先の例でカバーされている。図１４は、ｔ＝５の後のトポロジを示す。この時点での状態データは以下の通りである。
【表４０】
【表４１】
【表４２】
【０１３１】
ここで興味深いのは、Ｓｙ３がＲａと関与しないが、ＴｘＣのＮＱＯが１であることを判定するために（Ｓｙ２上のＴｘＡから引き継いだ）、Ｒａに関する少なくとも何らかのデータを追跡することである。しかしながら、これは、大きな困難を引き起こしてはならない。Ｓｙ１およびＳｙ２は、他のどのシステムがＲａに関与するかを知らず、これは、全てのシステムがそれらの最新のトポロジ・データ（これはむろん移動する標的である）を同報通信した後に「発見可能」であるに過ぎない。このため、Ｓｙ１およびＳｙ２はそれらのデータを何としても同報通信しなければならない。追加の負担は、Ｓｙ３がそのピアから受信する要約データを記録しなければならないことであるが、これがＲａに関与しないままである限り、複雑なトランザクションに基づいた論理は呼び出されない。これは、おそらく、リソース・クラスタのＮＱＯおよびＮＱＯにつながるシステムのアイデンティティを同報通信することによって排除することができるが、リソース・クラスタをもっと小さい断片に再び分解する時になったら表面化するいくつかの問題がある。各リソースを追跡することは、正しいＮＱＯにつながると考えることができるものについて支払う小さい代価であろう。
【０１３２】
この状態からの解放は、先の例と同様に続行する。
【０１３３】
例６：リソース・クラスタの分解を伴う３ウエイ状況（３ｗａｙＢｒｅａｋＣｌｕ）
この例は、３システム推移的終了の場合であり、「コンテンションの終了」イベントによって駆動されることなく、大きいリソース・クラスタをもっと小さいものに分解する。また、この例は、リソースの多数の共有保持者を有するトポロジを示す。表記は例１と同様である。
【０１３４】
イベントのシーケンスは、時間順に、以下の通りである。
【表４３】
【０１３５】
ｔ＝７までに生じるイベントは、先の例においてカバーされている。先の例と同様、Ｓｙ３はＲａに関与しないが、Ｒａに関する少なくとも何らかのデータを追跡する。
【０１３６】
図１５は、ｔ＝７の後のトポロジを示す。この時点の状態データは以下の通りである。
【表４４】
【表４５】
【表４６】
【０１３７】
この状態からの解放は、先の例と同様に続行する。今回は、ｔ＝８およびｔ＝９におけるイベントが意味するのは、リソース・クラスタＣａｂがもはや必要でないということであり、先の例に示された通り、この場合リソース・クラスタは分解される。このため、ｔ＝９の後、我々は図１６に示す状態および以下のテーブルに示す状態を有する。
【表４７】
【表４８】
【表４９】
【０１３８】
関与するリソースのいずれについてもコンテンションをクリアすることなくリソース・クラスタを分解した先の例と同様、コンテンション状態のリソースを保持しているまたは待っているだけのいずれかである限り、単一のトランザクション（ここではＴｘＢ）に２つの別個のリソース・クラスタが同時に関与することがわかる。コンテンション状態のリソースを待っているとすぐに、保持しているかまたは待機しているのいずれかであるコンテンション状態のリソースは全て、単一ノリソース・クラスタとして管理しなければならない。
【０１３９】
データ構造
図１７〜２４は、本発明に従ってコンテンション・データを保存するための１つの可能なデータ構造のセットを示す。
【０１４０】
図１７を参照すると、リソース・コンテンション制御テーブル（ＲＣＣＴ：resource
contention control table）８０２を用いて、様々な対象アイテムを単一のＷＬＭサブコンポーネントにのみ（または主に）固定する。これは、以下を含む。
１．リソース・クラスタ要素（ＲＣＬＵ）８０６（図１８）のためのアンカ８０４。
２．リソース要素（ＲＳＲＣ）８１０（図１９）のためのアンカ８０８。
３．トランザクション・テーブル（ＴＲＸＮＴ）８１４（図２２）のためのアンカ８１２。
【０１４１】
図１８を参照すると、各リソース・クラスタ要素（ＲＣＬＵ）８０６は、単一リソース・クラスタに関連したデータを含む。これは、以下を含む。
１．リソース・クラスタＩＤ８１６。  
２．リソース・クラスタＮＱＯ８１８（リソース・クラスタ内の全リソースの最小値）。
３．リソース・クラスタ内のリソースのリソース要素（ＲＳＲＣ）８１０（図１９）のためのアンカ８２０。
【０１４２】
図１９を参照すると、各リソース要素（ＲＳＲＣ）８１０は、コンテンション状態のリソースを記述する。これは、以下を含む。
１．リソースの指紋／名前８２２。
２．リソースＮＱＯ８２４。（同報通信経路上の効率のために、システム・クラスタにおいて遠隔システムが提供するＮＱＯ寄与とは別個のローカル／システム値を維持したい場合がある。その他の場合、これはリソース・クラスタＮＱＯである。）
３．リソース・クラスタ要素（ＲＣＬＵ）８０６（図１８）に対するポインタ８２６。
４．ローカル保持者のためのリソース・コンテンション・キュー要素（ＲＣＱＥ）８３０（図２４）のためのアンカ８２８。
５．ローカル待機者のためのリソース・コンテンション・キュー要素（ＲＣＱＥ）８３０のためのアンカ８３２。
６．このリソースに関する遠隔データのためのシステム・データ・アンカ（ＳＤＡ）８３６（図２０）のためのアンカ８３４。
【０１４３】
図２０を参照すると、各システム・データ・アンカ（ＳＤＡ）８３６は、単一システムのための遠隔システム情報のアンカとして機能する。これは以下を含む。
１．遠隔システムＩＤ８３８。
２．このシステムからの遠隔システム・データ要素（ＲＳＤＥ）８４２（図２１）のためのアンカ８４０。
３．遠隔システムの最高の既知の送信シーケンス数を表す値８４４。換言すると、下りの経路上で、送信側システムは、トポロジ・データの各「バッチ」ごとに同じである（タイムスタンプのような）値を含む。各受信側システムは、入来メッセージ内の値をこの値と比較する。メッセージの値が小さい場合（これが古いことを意味する。なぜなら受信側システムはすでに同じ送信者からより最近のデータを受信したからである）、メッセージは無視される。
４．トポロジ・メッセージが遠隔システムから受信されると、ローカル・クロックを用いて更新されるタイムスタンプ８４６。図２１を参照すると、各リソース・システム・データ要素（ＲＳＤＥ）８４２は、リソースのための遠隔システム情報を含む。これは以下を含む。
【０１４４】
１．システムのためのシステム・データ・アンカ（ＳＤＡ）（図２０）に対するポインタ８４８。
２．リソースのためのリソース要素（ＲＳＲＣ）８１０（図１９）に対するポインタ８５０。
３．同じリソースのための他のＲＳＤＥ８４２のためのキュー・リンク８５２。
４．遠隔システム上の待機者のみを考慮する遠隔システムのＮＱＯ８５４。
５．デバッグのみのための送信側タイムスタンプ８５６（送信された場合の遠隔システム上のクロック値）。
６．デバッグおよびＴＴＬ処理のための、受信された場合にローカル・クロック値を表すタイムスタンプ８５８。
７．このリソースのための遠隔リソース・クラスタＩＤ８６０。遠隔システムが保持者および待機者の双方であるトランザクションを有した場合、関与する全てのリソースは同じリソース・クラスタＩＤをそこに有し、ここで同じリソース・クラスタ内にある必要がある。異なるシステムからの遠隔データが、どのリソースがリソース・クラスタに属するかに関して一致しない場合、リソース・クラスタはローカルに結合される。
８．遠隔システムがデータおよび余分を送信する計画を立てる頻度に対応して、遠隔システムによって供給される有効期間（ＴＴＬ）持続時間８６２。ローカル時間が受信タイムスタンプおよびこの値よりも大きい場合、この要素は消去にふさわしい。
【０１４５】
図２２を参照すると、トランザクション・テーブル（ＴＲＸＮＴ）８１４を用いて、対象の様々なアイテムを、単一ＷＬＭサブコンポーネントにのみ（または主に）固定する。これは以下を含む。  
１．トランザクション・テーブル８１４が構築された場合のアドレス空間の数８６４。
２．トランザクション・テーブル８１４が構築された場合のエンクレーブの数８６６。
３．第１のテーブル・エントリ８６８に対するトランザクション・テーブルの開始からのオフセット８６８。
４．アドレス空間であるトランザクションのためのエントリ（ＴＲＸＮＥ）（数８６４まで）の領域８７０。
５．エンクレーブであるトランザクションのためのエントリ（ＴＲＸＮＥ）（数８６６まで）の領域８７２。
【０１４６】
図２３を参照すると、トランザクション・テーブル（ＴＲＸＮＴ）８１４の領域８７１または８７２における各エントリ（ＴＲＸＮＥ）８７４は、ＷＬＭによってコンテンションが管理されている少なくとも１つのリソースに関与する単一トランザクションに関する情報を含む。
【０１４７】
１．タイプ８７６：アドレス空間またはエンクレーブ。
２．このトランザクションのためのアドレス空間ＩＤ（ＡＳＩＤ）またはエンクレーブＩＤ８７８。
３．このトランザクションのためのアドレス空間またはエンクレーブ・トークン８８０。ＡＳＤＩおよびエンクレーブＩＤは再使用可能である。ＩＤが再使用される場合であっても、トークンは、単一イメージ内で固有性を提供する。
４．このトランザクションによって保持されるリソースのためのコンテンション要素（ＲＣＱＥ）８３０（図２４）のキュー８８４のアンカ８８２。
５．このトランザクションによって待機されるリソースのためのコンテンション要素（ＲＣＱＥ）８３０のキュー８８８のアンカ８８６。
６．このトランザクションのＮＱＯ８８８。
【０１４８】
図２４を参照すると、各リソース・コンテンション・キュー要素（ＲＣＱＥ）８３０は、トランザクション（保持者または待機者）をリソースに関連付ける。これは、以下を含む。
１．ＴＲＸＮＴ８１０においてトランザクションのためのＴＲＸＮＥ８７４のオフセット８９２。
２．このトランザクションのための次／前のＲＣＱＥ８３０のキュー・リンク８９４。
３．リソースのためのリソース要素（ＲＳＲＣ）８１０に対するポインタ８９６。
４．このリソースのための次／前のＲＣＱＥ８３０のキュー・リンク８９８。
５．保持／待機ビット８９９（おそらくキューの妥当性確認のためのみ）。
【０１４９】
図２５は、図７に示し、図７の説明に付随するテーブルにおいてＳｙ２について要約したコンテンション状況を、どのように、図１７〜２４に示す様々なデータ構造によって捕捉するかを示す。
【０１５０】
特定の実施形態について図示し記載したが、当業者には、様々な変更が明らかであろう。このため、（ローカルまたは遠隔のいずれかのコンテンション・データに基づいて）共通リソース・クラスタの一部と考えられる全てのリソースのための共通リソース・クラスタＩＤを送信するのではなく、ローカル・システムは、ローカル・コンテンション・データに基づいて、共通リソース・クラスタに属することがわかっているリソースのためのみの共通リソース・クラスタＩＤを用いることができる。他の変形も当業者には明らかであろう。
【図面の簡単な説明】  
【０１５１】
【図１】  本発明を組み込んだコンピュータ・システム・クラスタを示す。
【図２】  様々なタイプのコンテンション・チェーンを示す。
【図３】  様々なタイプのコンテンション・チェーンを示す。
【図４】  様々なタイプのコンテンション・チェーンを示す。
【図５】  様々なタイプのコンテンション・チェーンを示す。
【図６】  コンテンション・チェーンの頭部におけるユーザにリソースを割り当てる手順を示す。
【図７】  いくつかのシステム上でのトランザクションおよびリソース間の典型的なコンテンション状況を示す。
【図８】  ローカル・リソース・マネジャからの通知に応答して行われる全体的な手順を示す。
【図９】  遠隔システムからのコンテンション・データの同報通信の受信に応答して行われる全体的な手順を示す。
【図１０】  様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１１】  様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１２】  様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１３】  様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１４】  様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１５】  様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１６】  様々な動作例におけるマルチシステム・コンテンション状態を示す。
【図１７】  本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図１８】  本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図１９】  本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２０】  本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２１】  本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２２】  本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２３】  本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２４】  本発明の１実施形態においてコンテンション・データを保存するための様々なデータ構造を示す。
【図２５】  図７に示すコンテンション状況が、どのようにして、クラスタ内のシステムの１つによって捕捉されるかを示す。
【国際調査報告】
2006512688.tif 000077
2006512688.tif 000078
2006512688.tif 000079