(57)【要約】      （修正有）【課題】マルチノード型コンピュータ・システムにおいて、オペレーティング・システムのリソースをシステムの作業負荷の所望の分配割合と同じ割合でノードごとに分配する。【解決手段】システム内における全体的な均衡の割合を表すために、各ノードのプロセッサとメモリの割合に基づいて「目標重み」を割り当てる。稼働中のシステムは「現在重み」を「目標重み」に可能な限り近付けるように動作する。稼働開始時は、オペレーティング・システムのサービスはリソースを「目標重み」と同じ割合でノードごとに分配する。プロセッサおよび／またはメモリが脱着されると、それと同時に新たな「目標重み」を算出する。変更の通知を要求したすべてのサービスは当該通知を受領することになるから、新たな「目標重み」またはそれに漸進的に到達するように改良したものに従って自身のリソースを再分配することができる。【選択図】図１
2005251184.tif 000002
【特許請求の範囲】
【請求項１】
マルチノード型コンピュータ・システムにおいてリソースを管理する装置であって、
第１のプロセッサおよび該第１のプロセッサに付随する第１のメモリと、
第２のプロセッサおよび該第２のプロセッサに付随する第２のメモリと、
前記第１のプロセッサおよび前記第２のプロセッサで実行されるエンティティに少なくとも１つのサービスを提供するサービス・プロバイダと、
個別の作業負荷が前記第１のプロセッサおよび前記第２のプロセッサによって担持されるのを確実にする作業負荷管理機構であって、前記作業負荷管理機構は前記サービス・プロバイダに前記個別の作業負荷を通知して前記サービス・プロバイダが当該サービス・プロバイダのリソースを前記個別の作業負荷に従って調整するのを可能する、作業負荷管理機構と
を備えた
装置。
【請求項２】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成している、
請求項１に記載の装置。
【請求項３】
前記個別の作業負荷が個別かつ所望の作業負荷である、
請求項１に記載の装置。
【請求項４】
前記個別の作業負荷が個別かつ現在の作業負荷である、
請求項１に記載の装置。
【請求項５】
前記個別の作業負荷が個別かつ所望の作業負荷および個別かつ現在の作業負荷である、
請求項１に記載の装置。
【請求項６】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成し、前記個別の作業負荷が前記第１のノード用の第１の目標重みおよび前記第２のノード用の第２の目標重みによって表されている、
請求項３に記載の装置。
【請求項７】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成し、前記個別の作業負荷が前記第１のノード用の第１の現在重みおよび前記第２のノード用の第２の現在重みによって表されている、
請求項４に記載の装置。
【請求項８】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成し、前記個別かつ所望の作業負荷が前記第１のノード用の第１の目標重みおよび前記第２のノード用の第２の目標重によって表されており、前記個別かつ現在の作業負荷が前記第１のノード用の第１の現在重みおよび前記第２のノード用の第２の現在重によって表されている、
請求項５に記載の装置。
【請求項９】
マルチノード型コンピュータ・システムにおいてリソースを管理する装置であって、
第１のプロセッサおよび該第１のプロセッサに付随する第１のメモリと、
第２のプロセッサおよび該第２のプロセッサに付随する第２のメモリと、
前記第１のプロセッサおよび前記第２のプロセッサで実行されるエンティティに少なくとも１つのサービスを提供するサービス・プロバイダと、
個別かつ所望の作業負荷が前記第１のプロセッサおよび前記第２のプロセッサによって担持されるのを確実にするとともに、個別かつ現在の作業負荷が前記第１のプロセッサおよび前記第２のプロセッサによって担持されるのを確実にする作業負荷管理機構であって、前記作業負荷管理機構は前記個別かつ所望の作業負荷および前記個別かつ現在の作業負荷から個別かつ中間の作業負荷を抽出し、前記作業負荷管理機構は前記サービス・プロバイダに前記個別かつ中間の作業負荷を通知して前記サービス・プロバイダが当該サービス・プロバイダのリソースを前記個別かつ中間の作業負荷に従って調整するのを可能する、作業負荷管理機構と
を備えた
装置。
【請求項１０】
前記現在の作業負荷は当該現在の作業負荷が前記所望の作業負荷により近く一致するように時間をかけて調整されており、
前記個別かつ中間の作業負荷は前記現在の作業負荷に対する調整を反映しうるように周期的に更新されている、
請求項９に記載の装置。
【請求項１１】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成しており、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成している、
請求項１０に記載の装置。
【請求項１２】
前記個別かつ所望の作業負荷が前記第１のノード用の第１の目標重みおよび前記第２のノード用の第２の目標重によって表されており、前記個別かつ現在の作業負荷が前記第１のノード用の第１の現在重みおよび前記第２のノード用の第２の現在重によって表されており、前記個別かつ中間の作業負荷が前記第１のノード用第１の遷移重みおよび前記第２のノード用第２の遷移重みによって表されている、
請求項１１に記載の装置。
【請求項１３】
マルチノード型コンピュータ・システムにおいてリソースを管理するプログラムであって、
コンピュータ装置に、
作業負荷管理機構を設けるステップと、
前記作業負荷管理機構が、個別の作業負荷が第１のプロセッサおよび第２のプロセッサによって担持されるのを確実にするステップであって、前記第１のプロセッサは当該第１のプロセッサに付随する第１のメモリを備え、前記第２のプロセッサは当該第２のプロセッサに付随する第２のメモリを備えている、ステップと、
前記作業負荷管理機構が、サービス・プロバイダに前記個別の作業負荷を通知して前記サービス・プロバイダが当該サービス・プロバイダのリソースを前記個別の作業負荷に従って調整するのを可能にするステップであって、前記サービス・プロバイダは前記第１のプロセッサおよび前記第２のプロセッサで実行するエンティティに少なくとも１つのサービスを提供している、ステップと
を実行させる
プログラム。
【請求項１４】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成する、
請求項１３に記載のプログラム。
【請求項１５】
前記個別の作業負荷が個別かつ所望の作業負荷である、
請求項１３に記載のプログラム。
【請求項１６】
前記個別の作業負荷が個別かつ現在の作業負荷である、
請求項１３に記載のプログラム。
【請求項１７】
前記個別の作業負荷が個別かつ所望の作業負荷および個別かつ現在の作業負荷である、
請求項１３に記載のプログラム。
【請求項１８】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成し、前記個別の作業負荷が前記第１のノード用の第１の目標重みおよび前記第２のノード用の第２の目標重みによって表されている、
請求項１５に記載のプログラム。
【請求項１９】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成し、前記個別の作業負荷が前記第１のノード用の第１の現在重みおよび前記第２のノード用の第２の現在重みによって表されている、
請求項１６に記載のプログラム。
【請求項２０】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成し、前記個別かつ所望の作業負荷が前記第１のノード用の第１の目標重みおよび前記第２のノード用の第２の目標重によって表されており、前記個別かつ現在の作業負荷が前記第１のノード用の第１の現在重みおよび前記第２のノード用の第２の現在重によって表されている、
請求項１７に記載のプログラム。
【請求項２１】
マルチノード型コンピュータ・システムにおいてリソースを管理するプログラムであって、
コンピュータ装置に、
作業負荷管理機構を設けるステップと、
前記作業負荷管理機構が、個別かつ所望の作業負荷が前記第１のプロセッサおよび前記第２のプロセッサによって担持されるのを確実にするとともに、個別かつ現在の作業負荷が前記第１のプロセッサおよび前記第２のプロセッサによって担持されるのを確実にするステップと、
前記作業負荷管理機構が、前記個別かつ所望の作業負荷および前記個別かつ現在の作業負荷から個別かつ中間の作業負荷を抽出し、前記作業負荷管理機構は前記サービス・プロバイダに前記個別かつ中間の作業負荷を通知して前記サービス・プロバイダが当該サービス・プロバイダのリソースを前記個別かつ中間の作業負荷に従って調整するのを可能にするステップであって、前記サービス・プロバイダは前記第１のプロセッサおよび前記第２のプロセッサで実行されるエンティティに少なくとも１つのサービスを提供する、ステップと
を実行させる
プログラム。
【請求項２２】
前記現在の作業負荷は当該現在の作業負荷が前記所望の作業負荷により近く一致するように時間をかけて調整されており、
前記個別かつ中間の作業負荷は前記現在の作業負荷に対する調整を反映しうるように周期的に更新されている、
請求項２１に記載のプログラム。
【請求項２３】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成する、
請求項２２に記載のプログラム。
【請求項２４】
前記個別かつ所望の作業負荷を前記第１のノード用の第１の目標重みおよび前記第２のノード用の第２の目標重みによって表し、前記個別かつ現在の作業負荷を前記第１のノード用の第１の現在重みおよび前記第２のノード用の第２の現在重みによって表し、前記個別かつ中間の作業負荷を前記第１のノード用の第１の遷移重みおよび前記第２のノード用の第２の遷移重みによって表す、
請求項２３に記載のプログラム。
【請求項２５】
マルチノード型コンピュータ・システムにおいてリソースを管理する方法であって、
個別の作業負荷が第１のプロセッサおよび第２のプロセッサによって担持されるのを確実にするステップであって、前記第１のプロセッサは当該第１のプロセッサに付随する第１のメモリを備え、前記第２のプロセッサは当該第２のプロセッサに付随する第２のメモリを備えている、ステップと、
サービス・プロバイダに前記個別の作業負荷を通知して前記サービス・プロバイダが当該サービス・プロバイダのリソースを前記個別の作業負荷に従って調整するのを可能にするステップであって、前記サービス・プロバイダは前記第１のプロセッサおよび前記第２のプロセッサで実行されるエンティティに少なくとも１つのサービスを提供する、ステップと
を備えた
方法。
【請求項２６】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成する、
請求項２５に記載の方法。
【請求項２７】
前記個別の作業負荷が個別かつ所望の作業負荷である、
請求項２５に記載の方法。
【請求項２８】
前記個別の作業負荷が個別かつ現在の作業負荷である、
請求項２５に記載の方法。
【請求項２９】
前記個別の作業負荷が個別かつ所望の作業負荷および個別かつ現在の作業負荷である、
請求項２５に記載の方法。
【請求項３０】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成し、前記個別の作業負荷を前記第１のノード用の第１の目標重みおよび前記第２のノード用の第２の目標重みによって表す、
請求項２７に記載の方法。
【請求項３１】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成し、前記個別の作業負荷を前記第１のノード用の第１の現在重みおよび前記第２のノード用の第２の現在重みによって表す、
請求項２７に記載の方法。
【請求項３２】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成し、前記個別かつ所望の作業負荷を前記第１のノード用の第１の目標重みおよび前記第２のノード用の第２の目標重によって表し、前記個別かつ現在の作業負荷を前記第１のノード用の第１の現在重みおよび前記第２のノード用の第２の現在重によって表す、
請求項２７に記載の方法。
【請求項３３】
マルチノード型コンピュータ・システムにおいてリソースを管理する方法であって、
個別かつ所望の作業負荷が第１のプロセッサおよび第２のプロセッサによって担持されるのを確実にするステップと、
個別かつ現在の作業負荷が前記第１のプロセッサおよび前記第２のプロセッサによって担持されるのを確実にするステップと、
前記個別かつ所望の作業負荷および前記個別かつ現在の作業負荷から個別かつ中間の作業負荷を抽出するステップと、
サービス・プロバイダに前記個別かつ中間の作業負荷を通知して前記サービス・プロバイダが当該サービス・プロバイダのリソースを前記個別かつ中間の作業負荷に従って調整するのを可能にするステップであって、前記サービス・プロバイダは前記第１のプロセッサおよび前記第２のプロセッサで実行されるエンティティに少なくとも１つのサービスを提供する、ステップと
を備えた
方法。
【請求項３４】
前記現在の作業負荷は当該現在の作業負荷が前記所望の作業負荷により近く一致するように時間をかけて調整し、
前記個別かつ中間の作業負荷は前記現在の作業負荷に対する調整を反映しうるように周期的に更新する、
請求項３３に記載の方法。
【請求項３５】
前記第１のプロセッサおよび前記第１のメモリが第１のノードを形成し、前記第２のプロセッサおよび前記第２のメモリが第２のノードを形成する、
請求項３４に記載の方法。
【請求項３６】
前記個別かつ所望の作業負荷を前記第１のノード用の第１の目標重みおよび前記第２のノード用の第２の目標重によって表し、前記個別かつ現在の作業負荷を前記第１のノード用の第１の現在重みおよび前記第２のノード用の第２の現在重によって表し、前記個別かつ中間の作業負荷を前記第１のノード用の第１の遷移重みおよび前記第２のノード用の第２の遷移重みによって表す、
請求項３５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はリソースの管理に関し、特にマルチノード型コンピュータ・システムにおけるリソースの管理に関する。
【背景技術】
【０００２】
データを格納して処理するために、コンピュータ・システムが広く使用されている。データはコンピュータ・システムのメモリに格納され、コンピュータ・システムのプロセッサで実行されている、コンピュータ・システムのプログラムが処理する。周知のように、プロセッサはコンピュータ・システムの「頭脳」であると考えられることが多いが、それはプロセッサがコンピュータ・システムのプログラムを実行し、コンピュータ・システムが実際の作業（work）を行なうのを可能にする、コンピュータ・システム内のコンポーネントだからである。実行中のコンピュータ・プログラムを保持するため、および、コンピュータ・プログラムを実行しているプロセッサがアクセスする間にデータを保持するためにメモリが使用される。
【０００３】
競争場裡で優位に立つために、コンピュータ・システムの設計者達はコンピュータ・システムのサイズを維持あるいは縮小させながら、コンピュータ・システムをより強力にするために絶えず競い合っている。使用するプロセッサ数を増やしてコンピュータ・システム全体の処理能力を増大させるのが普通の方法である。製造効率を高めるために、プロセッサとメモリを一緒にパッケージングしていわゆる「ノード」を形成することが多い。そして、コンピュータ・システムはこのようなノードを少なくとも１つ備えている。これらのマルチノード型コンピュータ・システム内では、すべてのプロセッサはすべてのノードのメモリにアクセスすることができる。しかし一般に、プロセッサは任意の他のノードにあるメモリへのアクセス（リモート・アクセス）よりも自身のノードにあるメモリへのアクセス（ローカル・アクセス）をより効率的に行なうことができる。
【０００４】
コンピュータ・プログラムにはコンピュータ・システムの少なくとも１つのプロセッサが実行する一連の命令が含まれている。プロセッサはこれらの命令を実行（carry out)することによりコンピュータ・プログラムを実行（execute)するものと考えられる。オペレーティング・システム（他のプログラムのためにコンピュータ・システムのオペレーティング（操作、運転）の任に当たるプログラム）はジョブ（タスクまたはプロセスと呼ばれることもある）を使用することよりこれらのプログラムの実行を制御する。大多数のプロセッサは一度に１つの命令の流れしか実行することができない。しかし、それらはきわめて高速に動作するから、多数のジョブを実行し、同時に多数のユーザにサービスを提供しているように見える。オペレーティング・システムは各ジョブの実行時に「ターン（turn）」を付与するが、別のジョブがターンを取得している間は当該ジョブを待機させる必要がある。ジョブが処理（たとえば２次記憶装置へのアクセス）を実行する前に何かが発生するのを待ち受けている、あるいは複数のプロセッサが利用可能である状況おいては、ジョブはスレッド（サブプロセスまたはサブタスクと呼ばれることもある）を生成して処理を非同期的に継続すなわち迅速処理することができる。スレッドを生成しなかったジョブは自身が単一のスレッドを有するものと見なすことができる。したがって、ジョブは少なくとも１つのスレッドから成るものと考えることができる。
【０００５】
ノードの観点から、オペレーティング・システムは実行すべきスレッドを多くの方法で割り当てることができる。たとえば、所定のノードにおける実行用にあるジョブのスレッドを選定し、別のノードにおける実行用に別のジョブのスレッドを選定することができる。同様に、同じジョブに由来するスレッドを異なる複数のノードで実行することができるし、所定のノードで実行すべく選定したスレッドをその終了前に他の少なくとも１つのノードで実行すべく選定することができる。この柔軟性はある面では好都合であるが、データ・アクセスの観点からは問題をはらんでいる。上述したように、ノードはプロセッサとメモリから成り、プロセッサは別のノードよりも自身のノードにあるメモリにより効率的にアクセスすることができる。したがって、効率的に実行するには、オペレーティング・システムは各スレッドが（当該スレッドが実行の基盤としているノードと）同じノードにあるメモリにある当該スレッドのデータにアクセスすることを保証する必要がある（すなわち、各スレッドは実行時にいつも同じノードにあるメモリにアクセスすることを保証される必要がある）。
【０００６】
多くのオペレーティング・システムがこの問題点を解決するために用いている方法の１つは各スレッドと当該スレッドが実行およびデータ・アクセス双方のために選定するノードとを関連付けるものである。したがって、所定のスレッドを実行する場合、オペレーティング・システムは可能な限り自身にとって好都合なノードにあるプロセッサを選択する。同様に、スレッドのためにデータをメモリに格納する必要がある場合、オペレーティング・システムは可能な限り自身にとって好都合なノードにあるメモリを選択する。この方法は一般にリモート・メモリ・アクセスを最小化できる点で有益であるが、それは実行中のスレッドが行なう作業がコンピュータ・システムのノード全体にわたって均衡している場合に限られる。
【０００７】
少なくとも１つのノードを備えたコンピュータ・システムは少なくとも２つの個別のシステムに論理的に分割（partition)することもできる。１つの論理パーティションにはプロセッサとメモリを割り当てることができるが、それは当該プロセッサとメモリが属すノードとは無関係に行なうことができる。また、構成の変更または能力のアップグレードもしくはダウングレードに起因して論理パーティションおよび／またはコンピュータ・システムに対してプロセッサおよび／またはメモリを動的に脱着することができる。（「Ａおよび／またはＢ」は「ＡおよびＢ、Ａ、またはＢ」を表わす。）コンピュータ・システム内のローカル・メモリ・アクセス対リモート・メモリ・アクセスに関する効率の問題は各論理パーティションの内部にも適用することができる。この記述を通じて、用語「システム」は非分割のコンピュータ・システム全体、またはコンピュータ・システムの１つの論理パーティションを表すのに使用する。
【０００８】
オペレーティング・システムが使用する、ノードを均衡させる１つの方法はシステムにとって利用可能なプロセッサ・リソースおよび／またはメモリ・リソースと同じ割合で、作業（スレッド）を優先ノード群にノードごとに割り当てる機構を備えることである。
【０００９】
これらの機構は作業負荷を均衡させうる点、およびリモート・アクセスをほぼ最小化しうる点で有益であるが、従来技術に係るオペレーティング・システム自体は自身が提供するサービスに付随するリモート・アクセスを最小化するように最適化されていない。たとえば、クライアント・スレッドに様々なファイル・サービスを提供する統合ファイル・システムを備えたオペレーティング・システムを考える。このファイル・システムに付随して、その機能を実行するために様々なリソースが必要になる。それらのリソースの中には（一般公開されておらず、オペレーティング・システムが管理している）一連のカーネル・スレッドがある。カーネル・スレッドはキューに留まり、要求元のクライアントのためにファイルの特定部分を非同期に処理するように当該カーネル・スレッドに命令するメッセージを待ち受けている。別のリソースはこれらのスレッドに送付される可能性のあるメッセージのプールである。このメッセージ・プールとキューがクライアント・スレッドの優先ノードのメモリに偶然に存在しない限り、そして、当該要求にサービスを提供するカーネル・スレッドが同一のノードに偶然に存在しない限り、クライアント・スレッドとそれにサービスを提供するカーネル・スレッドとの間の相互作用はリモート・メモリ・アクセスを含む可能性がきわめて高い。これと同じ概念を説明するのに役立つ例が他にも多数存在する。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
オペレーティング・システムが自身のリソースをノードごとに分配してクライアント・スレッドの優先ノードに付随する特定のリソースを使用して当該クライアント・スレッドの要求にサービスを提供しうるようにする段がないと、オペレーティング・システムのサービスを使用することはリモート・メモリ・アクセスに起因して非効率になる。また、リソースの分配がシステムの作業負荷と同じ割合でノード間で均衡していないと、リソースが均一に使用されなくなるとともに、特定のリソースによっては他の様々な非効率が生じることになる。
【課題を解決するための手段】
【００１１】
本発明にはオペレーティング・システムのリソースをシステムの作業負荷の所望の分配割合と同じ割合でノードごとに分配するのを可能にする装置、方法、およびプログラムが含まれる。リソースの初期の分配が確立するのはシステムが稼働を開始し、当該システムのプロセッサ資源とメモリ資源がノードごとに特定された時である。作業負荷が再分配され、作業負荷の新たな所望の均衡状態に適合するためにシステムにプロセッサおよび／またはメモリを脱着するときには常にリソースを再分配する。（「Ａおよび／またはＢ」は「ＡおよびＢ、Ａ、またはＢ」を表わす。）したがって、リソースの再分配は漸進的に行なわれるから、実際の作業負荷のノードごとの割合を新たなノードごとの割合に漸進的に移行させることができる。
【００１２】
本発明の好適な実例では、システム内における全体的な均衡の割合を表すために、各ノードに様々な種類の重みを割り当てる。「目標重み」(target weight)は作業負荷の所望の分配を、各ノードにあるプロセッサとメモリの既存の割合に基づいて表すものである。目標重みが確立されるのはシステムが稼働を開始したのち定常状態を維持している時である（ただし後刻、プロセッサおよび／またはメモリが脱着された場合はこの限りではない）。システムにおける作業負荷の実際の均衡は「現在重み」によって表す。稼働中のシステムは現在重みを目標重みに可能な限り近付けるように絶えず奮闘している。システムが稼働を開始すると、オペレーティング・システムのサービスはそのリソースを目標重みと同じ割合でノードごとに分配する。当該サービスは目標重みが変更された場合にはその旨通知されるように要求することができる。後刻、プロセッサおよび／またはメモリが脱着されると、それと同時に新たな目標重みを算出する。変更の通知を要求したすべてのサービスは当該通知を受領することになるから、新たな目標重みまたはそれに漸進的に到達するように改良したものに従って自身のリソースを再分配することができる。
【発明を実施するための最良の形態】
【００１３】
次に、図面を参照する。図１は本発明の好適な実施形態のコンピューティング装置で使用する動作可能なコンポーネントの一部を示す図である。コンピュータ装置１００は拡張型ＩＢＭ（Ｒ）ｉＳｅｒｉｅｓ（Ｒ）コンピュータ・システムであるが、他のコンピュータを使用してもよい。図示したコンポーネントには処理ノード１３０、ネットワーク・インタフェース１２５、ユーザ・インタフェース１５０、および大容量記憶装置１５５が含まれている。好適な実施形態のコンピュータ装置１００は４つの処理ノードを備えているが、ノード数はこれより多くても少なくてもよい。ネットワーク・インタフェース１２５は他のコンピュータ・システムと通信するために使用する。ユーザ・インタフェース１５０はコマンドと、コンピュータ・システム１００の少なくとも１人のユーザへの中継情報とを受領するために使用する。
【００１４】
図１には、ノード１３０のうちの１つの分解組立図も示されている（すなわちノード１３１）。ノード１３１はプロセッサ１３２とメモリ１３４を備えている。好適な実施形態では各ノードは最大８個のプロセッサを備えることができるが、これよりも多い（または少ない）プロセッサを備える他の構成をとってもよい。プロセッサ１３２はメモリ１３４に格納されたスレッドを実行するために使用するが、これらのスレッドは大容量記憶装置１５５に部分的あるいは完全に存在してもよいということを理解すべきである。プロセッサは任意のノードのメモリにアクセスすることができるが、自身のノードのメモリにより効率的にアクセスすることができる。
【００１５】
図２は好適な実施形態のコンピューティング環境をより詳細に示す図である。図示するように、この好適な実施形態は論理的に分割されたコンピュータ・システムで動作することができる。この状況では、カーネル・サービス１３７のインスタンスは（図２にシステム１〜３として示す）各パーティションに常駐するように構成する。この好適な実施形態の機構では、各パーティションが完全なシステムとして示されている。したがって、ここで単独で使用する場合、用語「システム」は非分割のコンピュータ装置、またはコンピュータ装置内の単一の論理パーティションを指すものと解釈する必要がある。システムは（システム１およびシステム２の場合のように）コンピュータ・システム全体の一部のノードしか利用しなくともよい。また、１つのノードが複数のシステムをサポートしていてもよい。好適な実施形態の大多数の機構はシステムを構成するノード群に作業（スレッド）を割り当て、かつ調整する方法を備えている。したがって、システムの構成が変更されると、好適な実施形態の機構は作業の分配を調整する必要があるか否かを判断し、それが必要な場合にはそれらの調整を実行する。
【００１６】
各システムはスレッド１３５とオペレーティング・システム１３６を備えているように示されている。オペレーティング・システム１３６中に統合されているのはカーネル・サービス１３７である。カーネル・サービスは他のオペレーティング・システム・エンティティおよび他のプログラムにオペレーティング・システム・レベルのサービスを提供する。しかし留意点を挙げると、好適な実施形態では再均衡させる必要がある旨の通知をカーネル・サービスとして提供しているが、本発明はカーネル・レベルすなわちオペレーティング・システム・レベルのサービスに限定されず、再均衡の通知を利用しうるすべてのサービスに適用することができる。
【００１７】
最後の主要事項として理解すべき点を挙げると、ここではコンピュータ装置の文脈で本発明の実施形態を説明しているが、ある種のプログラム構造（たとえばカーネル・サービス１３７）はプログラム製品の形態で頒布することができる。無論、プログラム製品は次に示すような様々な種類の信号担持媒体を用いて頒布することができるが、それらに限定されない。すなわち、記録型媒体（たとえばフロッピー（登録商標）ディスクやＣＤ−ＲＯＭなど）および伝送型媒体（たとえばディジタル通信リンクやアナログ通信リンクなど）である。
【００１８】
図３は好適な実施形態のカーネル・サービス１３７のいくつかの側面の分解組立図である。図示するように、カーネル・サービス１３７はスレッド・マネージャ２００、ノード・マネージャ２２０、および構成マネージャ２４０を備えている。スレッド・マネージャ２００はさらにスレッド生成機構（ＴＣＭ）２０５、スレッド・ディスパッチ機構（ＴＤＭ）２１５、およびスレッド・メモリ・マネージャ（ＴＭＭ）２１７を備えている。好適な実施形態では、ＴＣＭ２０５は実行可能なスレッドを必要なスレッド制御構造体とともに生成する。生成プロセスの一部として、ＴＣＭ２０５がこれら実行可能なスレッドをホーム・ノードにも割り当てる。ホーム・ノードへの割り当てが重要なのはＴＤＭ２１５は可能な限り自身に割り当てられたホーム・ノードにあるスレッドを実行するように偏向しているからである。この偏向の意味するところはシステム全体の使用率とリソースの割り当てとに関係している。ＴＣＭ２０５がホーム・ノードへ割り当てる側面については図３５〜図３９に付随する記述において説明する。
【００１９】
ＴＣＭ２０５がスレッドを生成しそれらをホーム・ノードに割り当てたら、ＴＤＭ２１５がそれらのスレッドをディスパッチして実行の用に供する。一般に、スレッドはシステムの様々なノードにある多数のプロセッサのうちの任意のもので実行することができる。ＴＣＭ２０５は利用可能なプロセッサ資源とメモリ資源を最も有効に使用しうるようにスレッドをグループ化する、好適な実施形態内のエンティティである。ＴＣＭ２０５の機能と内部動作に関するさらなる詳細は下で示す図４〜図９の検討において説明する。
【００２０】
図３にはノード・マネージャ２２０も示されている。ノード・マネージャ２２０はそれ自身３つの個別のエンティティから成るが、好適な実施形態ではシステム中の様々なノードの相対作業負荷を決定するのに使用する。また、ノード・マネージャ２２０は好適な実施形態ではシステム内の作業負荷の不均衡を特定してそれを修正するため、および、他のカーネル・サービスにノードの作業負荷に対する変更を通知しこれらのサービス自身がそれに合わせて調整しうるようにするためにも使用する。不均衡の通知と処理はこの明細書の「作業の再分配」の章（図１８〜図２１、図２３〜図３４）で説明する。一方、「カーネル・コンポーネントによる均衡化の通知」は図１１〜図１８、図２１、および図２２に付随する記述において説明する。
【００２１】
ノード・マネージャ２２０の中にはディスパッチ・ハンドラ２３０、ウオッチドッグ・ハンドラ（ＷＤＨ）２２５、およびノード・バランサ２３５が示されている。これら３つのエンティティは好適な実施形態のシステム内では非同期スレッドとして動作する。当業者が認識しうるように、これらのスレッドの非同期性はアトミック・データ・アクセスが必要であることを意味する。このように、ここではアトミシティ（atomicity 、原子性、不可分性）の問題を偶然に参照したが、本発明はその下に存在するアトミシティ機構についてこれ以上扱うことはしない。上述したアトミシティ機構は当業者にとって周知である。その名前が示唆しているように、ディスパッチ・ハンドラ２３０はＴＤＭ２１５が出すディスパッチ要求を処理する。スレッドは絶えずディスパッチされるから、ディスパッチ・ハンドラ２３０はきわめて頻繁に実行される。これに関連して、ディスパッチ・ハンドラ２３０の任務の１つはプロセッサの実行サイクルのカウント値をホーム・ノードごとに累算することである。（このサイクル情報を取得するためにディスパッチ・ハンドラ２３０が使用する正確な手段は好適な実施形態を理解するのに重要ではないから、ここではこれ以上説明しない。）ＷＤＨ２２５は毎秒実行するようにスケジュールされているが、これら累算されたサイクルを７秒ごとに取得する。ここではこの７秒間隔を現在重み（weight）間隔と呼ぶ。情報を取得した後、ＷＤＨ２２５はその情報を基に様々な計算を行なう。それは結局、現在重みになる。（好適な実施形態中における現在重みの使用方法は下の段落で説明する。）ＷＤＨ２２５は時には、現在重み間隔が満了するごとにノード・バランサ２３５に通知する任にも当たる。ノード・バランサ２３５はこの情報を用いて「カーネル・コンポーネントによる均衡化の通知」が必要か否かを判断する。
【００２２】
図３には構成マネージャ２４０も示されている。構成マネージャ２４０は好適な実施形態では構成の変更をノード・バランサ２３５に通知するエンティティである。ノード・バランサ２３５はこの構成の変更を検討し、「作業の分配」と「カーネル・コンポーネントによる均衡化の通知」とに対して適切な処置を講じる。構成の変更の例としてはシステムのプロセッサまたはメモリを増加または減少させることが挙げられる。
【００２３】
〔メモリの親和性に基づくスレッドのグループ化〕
本発明は共用データに対して複数のスレッドがローカルにアクセスしうるようにするために、少なくとも２つのスレッドをメモリ親和性グループ（ＭＡＧ）にグループ化することを利用している。したがって、相互に依存するデータ・アクセスを必要とするスレッド群が同じノードで実行しうるようになるから、ローカル・メモリ・アクセスのために性能が向上する。好適な実施形態では、スレッドを個別にあるいはジョブごとにＭＡＧに配置する。ジョブごとにＭＡＧに配置する場合、所定のジョブのすべてのスレッドを同じＭＡＧに配置する。しかし当業者が認識しうるように、別の方法もある。たとえば、一方の指定で他方の指定をオーバーライドすることにより、両方のレベルでＭＡＧに配置することもできる。
【００２４】
ここでは図４〜図９を用いて本発明のメモリの親和性に基づくグループ化の側面を説明する。好適な実施形態では、ＭＡＧの決定と論理ノードの割り当てとは実行中のスレッドが別のスレッドを生成するように要求した時に行なう。ここでは図４と図５を用いて要求元スレッドと直接に相互作用する任に当たる、ＴＣＭ２０５の当該部分を説明する。この相互作用の結果、結局、スレッドを生成することになる。これについては図６と図７に付随する記述中で説明する。まず、図４と図５を参照する。ブロック３００はスレッドを生成する要求の受領を示している。次いでブロック３０２において、ＴＣＭ２０５はスレッド生成要求がＭＡＧへの加入を希望しているか否かを指定しているか否かを判断する。好適な実施形態では、ＭＡＧへの加入の希望はＴＣＭ２０５がアクセス権を有する永続的なスレッド生成属性（ＴＣＡ）の範囲内で指定する。このスレッド用にＭＡＧへの加入を希望している場合、ＴＣＭ２０５は次にＴＣＡが特定のＭＡＧを指定しているか否かを判断する（ブロック３０４）。好適な実施形態では、この指定はＭＡＧ識別子（すなわちグループＩＤ）を使用することによって行なう。グループＩＤがＴＣＡ内で指定されている場合、ＴＣＭは当該要求を尊重し、指定されているグループＩＤを用いてスレッドを生成するだけである（ブロック３０８）。ＴＣＡがまだ指定されたグループＩＤを持っていない場合、次に利用可能なグループＩＤを割り当てる（以後、これがＴＣＡが使用するグループＩＤになる）。
【００２５】
ブロック３０２においてＴＣＭ２０５がＭＡＧへの加入は要求されていないと判断した場合、ＴＣＭ２０５は続いて「論理ノード」の使用がＴＣＡで指定されているか否かを判断することになる。好適な実施形態では、論理ノード（これは物理ノードとは別のものである）を用いて要求元スレッドが、生成すべきスレッドが同じホーム・ノードまたは異なるホーム・ノードに割り当てられることを指定できるようにする。物理ノード（これはスレッドの実際のホーム・ノードである）は要求元スレッドから隠されている。この方法には様々な識別子を備えた物理ノードを使用する要求群を尊重する柔軟性を保持しつつ要求者用に論理ノードを指定しうるという利点がある。したがって、論理ノードを指定すると、その結果として当該スレッド用にホーム・ノードが指定される。
【００２６】
ブロック３１０において論理ノードを使用することが指定されている場合、ＴＣＭ２０５はＴＣＡが特定の論理ノードの指定を含んでいるか否かを判断する（ブロック３１２）。ＮＯの場合、ＴＣＭ２０５は２番目に利用可能な論理ノードＩＤを割り当て、それをＴＣＡに格納する（ブロック３１４）。結局、ＴＣＭ２０５はＴＣＡで指定されている論理ノードＩＤ、または新たに指定した論理ノードＩＤを用いてスレッドを生成することになる（ブロック３１６）。次にブロック３１０に戻る。ＴＣＭ２０５がＴＣＡの検査から論理ノードを使用することは指定されていないと判断した場合、ＴＣＭ２０５はブロック３１８においてＴＣＡが参照スレッドの指定を含んでいるか否かを判断する。参照スレッドとはメモリの親和性が要求される、生成すべきスレッドに対置されるスレッドのことである。好適な実施形態では、参照スレッドの指定はＴＣＡ中にスレッドＩＤを含めることにより行なう。参照スレッドが指定されていない場合、ＴＣＭ２０５は論理ノードＩＤまたはＭＡＧ  ＩＤのないスレッドを生成する（ブロック３２０）。この結果、ＴＣＭ２０５は要求元のスレッド用にホーム・ノードを選定しうるようになる。
【００２７】
参照スレッドが指定されている場合、ＴＣＭ２０５は次に、指定されたスレッドがＭＡＧに関連付け済みであるか否かを判断することになる（ブロック３２２）。ＹＥＳなら、ＴＣＭ２０５は参照スレッドのＭＡＧ  ＩＤを抽出し（ブロック３２４）、指定されたＭＡＧ  ＩＤを用いてスレッドを生成することになる（ブロック３２６）。ブロック３２２でＴＣＭ２０５が参照スレッドはまだＭＡＧに関連付けられていないと判断した場合、ＴＣＭ２０５は参照スレッドはそれに割り当てられた論理ノードを有するか否かを判断する。ＹＥＳなら、ＴＣＭ２０５は参照スレッドの論理ノードを抽出し（ブロック３３０）、指定された論理ノードを用いてスレッドを生成する（ブロック３３２）。ブロック３２８においてＴＣＭ２０５が参照スレッドには実際には論理ノードが割り当てられていないと判断した場合、ＴＣＭ２０５は２番目に利用可能なＭＡＧ  ＩＤを割り当て、参照スレッドからホーム・ノードを抽出することになる（ブロック３３６）。これらが完了したら、新たなＭＡＧを生成してＭＡＧリストに付加し、参照スレッドもこのＭＡＧに付加する（ブロック３３８）。次いで、ＴＣＭ２０５は指定されたＭＡＧ  ＩＤを用いてスレッドを生成する。
【００２８】
図６と図７はスレッドの生成を実際に実行する、好適な実施形態のＴＣＭ２０５で使用するステップ群を示す図である。図６と図７の論理へのエントリ・ポイントは３つある。ＭＡＧ  ＩＤを入力としてスレッドを生成できるし（ブロック３５４）、論理ノードを入力としてスレッドを生成できるし（ブロック３５２）、あるいは、ＭＡＧ  ＩＤまたは論理ノードＩＤの指定がなくともスレッドを生成できる（ブロック３５０）。
【００２９】
ＴＣＭ２０５がブロック３５０を通じて図６と図７の論理に入ると、ＴＣＭ２０５はスレッド用にホーム・ノードを決定することになる（ブロック３５６）。上述したように、スレッドのホーム・ノードとは可能な限り当該スレッドをディスパッチするノードのことであり、そのメモリは可能な限り当該スレッドのために割り当てられる。ホーム・ノードの決定に当たっては、システムはいくつかの要因（たとえば現在の作業負荷および所望の作業負荷）を考慮に入れる。ホーム・ノードの決定に関する詳細は図３５〜図３９に付随する記述において説明する。次いで、ＴＣＭ２０５は当該スレッド用にカーネル・スレッド構造体を生成する（ブロック３７２）。好適な実施形態では、カーネル・スレッド構造体はスレッドを表すのに使用する。したがって、カーネル・スレッド構造体の生成はスレッドの生成と同義である。次いで、ＴＣＭ２０５は最近生成されたスレッドがＭＡＧの構成要素であるか否かを判断する。この説明のこの部分における作業仮説はスレッドを生成する要求はＭＡＧの指定も論理ノードＩＤの指定も含んでいなかったというものである（上述したブロック３５０の説明を参照）。したがって、判断ブロック３８０および３８４の処理結果はＮＯである。この結果、ＴＣＭ２０５はブロック３８８において処理を終了する。この時点で、要求されたスレッドは生成されホーム・ノードに割り当てられている。
【００３０】
ＴＣＭ２０５がブロック３５２を通じて図６と図７の論理に入ると、ＴＣＭ２０５は指定された論理ノードを物理ノードに変換するすることになる。この物理ノードが以後、当該スレッドのホーム・ノードになる。好適な実施形態では、所定の論理ノードと所定の物理ノードとの間に一貫した相互関係を維持するために決定論的なアルゴリズムを使用する。そして、そのマッピングには多対一のものを使用することができる。しかし留意点を挙げると、他のマッピングを使用することもできる。ブロック３７２および３８０の処理は上述したものと同じである。しかしこの場合、論理ノードＩＤは指定済みであるから、ＴＣＭ２０５は当該スレッドを移動不可としてマークする（ブロック３８６）。すなわち、当該スレッドのホーム・ノードは変更できない（後述する「作業の再分配」の章を参照）。こうするのは要求元のスレッドが特定の論理ノードを指定するのを尊重するためである。
【００３１】
ＴＣＭ２０５がブロック３５４を通じて図６と図７の論理に入ると、ＴＣＭ２０５はグループＩＤに関連付けられたＭＡＧを探索することになる（ブロック３６０）。好適な実施形態では、各ＭＡＧはグループ・オブジェクトによって表す。各グループ・オブジェクトはグループＩＤ、当該ＭＡＧのホーム・ノード、および当該ＭＡＧを構成するスレッドのリストを備えている。グループ・オブジェクトは互いに連結されてＭＡＧのリストを形成している。ＴＣＭ２０５はこのＭＡＧのリストを探索してグループＩＤの一致が存在するか否かを判断する（ブロック３６２）。一致が存在する場合（ブロック３６２）、ＴＣＭ２０５はグループ・オブジェクトから当該ＭＡＧ用にホーム・ノードを抽出した後（ブロック３６４）、ブロック３７２においてカーネル・スレッド構造体を生成する。
【００３２】
処理ブロック３６２に戻る。ＭＡＧのリスト中に一致が存在しない場合、ＴＣＭ２０５は生成すべきスレッドとＭＡＧ用にホーム・ノードを決定する必要がある。ＴＣＭ２０５はブロック３７０に進み、このスレッド用にホーム・ノードを決定する。（上述したように、ホーム・ノードの決定は図３５〜図３９に付随する記述においてより詳細に説明する。）ホーム・ノードを決定したら、ＴＣＭ２０５は新たなＭＡＧを生成し、当該ＭＡＧにホーム・ノードとグループＩＤを格納した後（ブロック３７８）、グループ・オブジェクトをリストに付加する（ブロック３７４）。リストに新たなＭＡＧを付加したら、スレッド（すなわちカーネル・スレッド構造体）を生成する（ブロック３７２）。
【００３３】
上述したように、カーネル・スレッド構造体を生成したら、ＴＣＭ２０５は生成したばかりのスレッドがＭＡＧの構成要素であるか否かを判断する。この説明のこの部分では、当該スレッドはＭＡＧの構成要素である。したがって、ＴＣＭ２０５はブロック３８２において当該スレッドをＭＡＧに付加する。好適な実施形態では、これは当該スレッドをＭＡＧ用のスレッド・リストに付加することにより行なう。
【００３４】
図８はスレッドの終了時にＭＡＧを処理するために、好適な実施形態で使用する強調すべきステップ群を示す図である。好適な実施形態では、スレッドは自身がＭＡＧの構成要素である場合、終了する時に当該ＭＡＧから自身を削除しなければならない。したがって、ブロック４０５において終了スレッドが自身はＭＡＧの構成要素ではないと判断した場合、スレッド終了処理は単に継続するだけである（ブロック４１７）。ブロック４０５において終了スレッドが自身はＭＡＧの構成要素であると判断した場合、終了スレッドは当該ＭＡＧのスレッド・リストから自身を削除する（ブロック４１０）。終了スレッドがＭＡＧ中の最後のスレッドではない場合（ブロック４１９）、ここでも終了処理は単に継続するだけである。しかし、終了スレッドがＭＡＧ中の最後のスレッドである場合（ブロック４１９）、ブロック４２１において当該ＭＡＧをＭＡＧリストから削除する。次いで、ブロック４２３において当該ＭＡＧ自身を破棄した後、ブロック４１７において通常の終了処理を継続する。
【００３５】
ＭＡＧ管理の別の側面はＭＡＧの存在がきわめて短時間である環境（すなわちＭＡＧが現れてはすぐに消える環境）においてＭＡＧに関する情報を明確にすることである。図９はこの仕事を行なうために好適な実施形態で使用するステップ群を示す図である。情報に対する要求を受領すると（ブロック５００）、まず、当該情報を求める根拠をなすＭＡＧを突き止めるよう試みる（ブロック５０５）。関連するＭＡＧがＭＡＧリスト中にない場合、その旨をブロック５３５において要求者に通知する。次いで、ブロック５３０において通常の処理を継続する。ＭＡＧが存在する場合、要求された情報をブロック５２０において提供する。次いで、処理を継続する（ブロック５３０）。
【００３６】
〔カーネル・コンポーネントによる均衡化の通知〕
この章は「カーネル・コンポーネントによる均衡化の通知」に関する。上述したように、好適な実施形態の機構はシステム上の作業負荷全体を最も良好に均衡化させるように機能する。この均衡化に関連して必要なことは、他のカーネル・コンポーネントに作業の分配が変更されたことを通知し、これらのコンポーネントが適切な手段を講じられるようにすることである。通知を受領するには、コンポーネントはノード・バランサ２３５を用いて登録する必要がある。ノード・バランサ２３５は（図４４に示す）コンポーネント・レジストリに対してアクセス権を有している。好適な実施形態で使用するレジストリは論理的には各要素がコンポーネント名、コンポーネント・メソッド、およびレジストリ中の次の要素へのポインタを備えた連結リストのように見える。このコンポーネント・メソッドは通知の時にノード・バランサ２３５が呼び出すためにセットアップされる。また、留意点を挙げると、好適な実施形態はオペレーティング・システム・サービスに含まれるカーネル・サービスの面で機能するが、本発明の用途はカーネル・サービスすなわちおオペレーティング・システム・サービスに限定されず、システム内の仕事の分配の変更を通知されることにより利益を得る可能性のあるあらゆる種類のコンポーネントまたはサービスに適用することができる。
【００３７】
（システムのＩＰＬ）
はじめに留意点を挙げると、この「システムのＩＰＬ」の章では好適な実施形態の概念をいくつか導入するが、これらの概念（すなわち現在重み、遷移重み、重み差分（differential）閾値（いきち、しきいち）、および開始重み）の多くは文脈全体を議論するときまで完全には説明しない。現在重み、遷移重み、および重み差分なる概念は図１１〜図１３に付随する記述において説明するが、開始重みなる概念は図３５〜図３９に付随する記述とともに説明する。この方法をとるのは、これらの記述は後述する段落において提示するとより良好に理解できるからである。
【００３８】
次に、図１０を参照する。システムをブートするときは常にノード・バランサ２３５を呼び出す。したがって、これはいつでも起こりうる。ノード・バランサ２３５はノード・マネージャの状態（図４０の符号２９０２を参照）を「現在重み」にセットした後（ブロック６０５）、すべての記憶領域を零に初期化する（図４０〜図４４の符号２９０４〜３１００を参照）（ブロック６０８）。（「ＡをＢにセットする（set A to B）」とは変数Ａに値Ｂを代入することである。）次いで、ノード・バランサ２３５は重みの組を生成する。これらの重みはホーム・ノードごとに生成するが、好適な実施形態ではシステムにおける作業の分配を管理するために使用する。最初に生成する重みはいわゆる目標重みである。各ノード用の目標重みは当該所定のノード用の作業の所望の割合を表している。好適な実施形態の機構の目的は作業を様々な目標重みに比例してシステム全体に分配することである。図１０のブロック６１０は図１４を指している。図１４はこの明細書の「構成の変更」の章において詳細に説明する。
【００３９】
図１４から戻ったら、開始重み２９３０と現在重み２９０６を目標重みにセットする（ブロック６２５）。ノードごとに、その現在重みと遷移重みを現在のＫＣＢＮセット（図４３の符号３０１５を参照）中の目標重みに等しい値にセットする（ブロック６３５）。遷移重み、現在重み、および目標重みの間の相互作用は図１１〜図１３に付随する記述において詳細に説明する。開始重みはホーム・ノードの割り当てに関係するが、これについては図３５〜図３９に付随する記述において説明する。上述した処理はすべてＩＰＬ処理の残り（ブロック６４０、これにはスレッドをディスパッチすること、オペレーティング・システム１３６がホーム・ノードを移動させるのを可能にすることなどが含まれるであろう）を実行する前に行なう必要がある。また、それには目標重みに基づいてオペレーティング・システムのリソース／カーネルのリソースをノードに分配することを含めてもよい。ＩＰＬ処理はブロック６４５において終了する。
【００４０】
（構成の変更）
後続する段落において詳細に説明するように、目標重みはシステムにとって利用可能なプロセッサとメモリがノードごとに維持・管理する。目標重みは特定のシステムを立ち上げる間に当該システムごとに設定する。目標重みは当該システム内おいて構成の変更が生じない限り、あるいは当該システム内において構成の変更が生じるまで変化しない。ここでは、構成の変更はすでに行なわれたものと仮定する。この構成の変更を図１１のブロック７００によって表す。構成の変更の詳細は好適な実施形態の説明にとって重要ではないが、そのような変更の例としてノードが使用するプロセッサを３個から２個にするシステムの再構成が挙げられる。ノード・バランサ２３５は構成の変更の通知を受領すると（ブロック７００）、現在重みのコピーを取得する（ブロック７１０）。
【００４１】
現在重みはシステム内における作業の実際の分配を表している。現在重みを取得するために、好適な実施形態で使用する機構を図１６と図１７に示す。図１６で始めにとるステップは現在重みＩＤ（ＣＷＩＤ）の抽出（ブロック１０４８）であり、現在重み間隔数（ＣＷＩＮ）の抽出（ブロック１０４９）がそれに続く。現在重みは１つの間隔の間だけ有効であり、それを過ぎると満了するから、直近の間隔を基に再計算する必要がある。ＣＷＩＤ２９１１は現在重みが有効である間隔の個数を含んでいる。ＣＷＩＤ２９１１がＣＷＩＮ２９０８と等しければ現在重みは有効である。そうでなければ現在重みは満了しているから、再計算する必要がある。図４０を暫時参照する。図４０には現在重みに関する情報が示されている。ＣＷＩＤ２９１１およびＣＷＩＮ２９０８とともに、現在重み呼び出しカウント値（ＣＷＩＣ）、ＳＥＴ０、およびＳＥＴ１が示されている。各組はディスパッチャ・コミットメント割合アキュムレータ（ＤＣＰＡ）と最近実行サイクル・カウント値（ＲＥＣＣ）を備えている。ＣＷＩＣ２９１０はＣＷＩが満了した時を決定するために使用する。ＤＣＰＡ情報は好適な実施形態の「作業の再分配」の側面および「ホーム・ノードの割り当て」の側面に関するものであるから、それらの記述とともに説明する。図４０には現在重み２９０６とＤＣＰ２９０７も示されている。好適な実施形態のこの（ＫＣＢＮの論理を説明している）側面では現在重みを使用するが、好適な実施形態の「作業の再分配」の側面および「ホーム・ノードの割り当て」の側面ではＤＣＰ２９０７を使用する。
【００４２】
次に、図１６に戻る。ブロック１０４９においてＣＷＩＮを抽出したら、ノード・バランサ２３５はまずＣＷＩＤ２９１１とＣＷＩＮ２９０８とが等しいか否かを判断する。それらが等しいなら、ノード・バランサ２３５は図１７のブロック１０６１へ進む（この処理は引き続く段落において後述する）。それらが等しくないなら、ノード・バランサ２３５はＣＷＩＮ２９０８を検査してそれが奇数であるか偶数であるかを判定する（ブロック１０５０）。ＣＷＩＮ２９０８が奇数なら、ＳＥＴ１（図４０参照）からＲＥＣＣ（ブロック１０５１）とＤＣＰＡ（ブロック１０５４）を抽出する。ＣＷＩＮ２９０８が偶数なら、ＳＥＴ０からＲＥＣＣ（ブロック１０５２）とＤＣＰＡ（ブロック１０５６）を抽出する。上述したように、ディスパッチ・ハンドラ２３０はきわめて頻繁に実行されており、その機能の一部としてプロセッサの実行サイクル数をホーム・ノードごとに累算している。次いで、ウオッチ・ハンドラ２２５がこれらのサイクル・カウント値とＤＣＰを取得し、すべてのＣＷＩの終わりにＲＥＣＣとＤＣＰＡにそれぞれノードごとに格納する。また、ウオッチ・ハンドラ２２５はＣＷＩＮをインクリメントする。これにより、当該組はアクティブと非アクティブの間を行き来することなる（これは図１８と図２１において詳述する）。次いで、ノード・バランサ２３５はＣＷＩＮ２９０８を再度抽出し（ブロック１０５８）、それが前回の抽出時から変更されているか否かを判断する（ブロック１０６２）。アトミシティが問題になるのは現在のＲＥＣＣとＤＣＰＡの抽出中にＣＰＩが満了することがありうるからである。したがって、ＲＥＣＣ情報とＤＣＰＡ情報がアクティブの組から抽出したものであることを保証するためにはこれらのステップ群が必要になる。ＣＷＩＮ２９０８が変更されていたら、ＣＷＩＮ２９０８は不変であるということをノード・バランサ２３５が確認するまで上述したプロセスを繰り返す（図１７のブロック１０６２とブロック１０６３を参照）。
【００４３】
次に、図１７を参照する。ノード・バランサ２３５はＣＷＩＮ２９０８が前回の抽出以後不変であると判断したら（ブロック１０６２）、各ノードのＲＥＣＣを合計ＲＥＣＣで除算してノードごとに現在重みを算出する（ブロック１０６４）。これにより、各ノードが実際に実行している現在の作業の割合が得られる。したがって、それらは各ホーム・ノードが担持する、全作業負荷に対する実際の負担部分を表している。次いで、現在重みを図４０〜図４２の現在重み組２９０６に格納し、ＤＣＰを同図のＤＣＰ組２９０７に格納する。現在重みを算出して格納したら、ＣＷＩＤ２９１１を、抽出したＣＷＩＮと等しい値にセットする。次いで、現在重み組２９０６から現在重みを抽出し、それを図１６と図１７の論理の呼び出し側に戻す（ブロック１０６６）。ＤＣＰはブロック１０７０においてＤＣＰ２９０７からも抽出する。その目的はこの場合にも抽出したＤＣＰを図１６と図１７の論理の呼び出し側に戻すためである。最後に、ブロック１０７２においてＣＷＩＮ２９０８を再度抽出し、それをブロック１０７４において前回抽出したものと比較する。２つの値が異なれば、図１６のブロック１０５７において継続することにより実施形態を繰り返す。
【００４４】
図１１に戻る。ノード・バランサ２３５は次に新たな目標重みを決定することになる（ブロック７１５）。無論ここでは、目標重みは構成の変更に起因して変更されているものと仮定している。図１４の第１のステップ（ブロック１００２）において、システム内のプロセッサの個数とメモリの量をノードごとに決める。好適な実施形態では、この情報はシステムの立ち上げの間にノードごとのデータ構造体に格納する（図４３の符号３０１５および３０２０を参照）。好適な実施形態のノードは任意個数のプロセッサを備えることができるし、プロセッサを備えないこともできるということを想起されたい。次いでブロック１００４において、システム全体のプロセッサの総個数とメモリの総量を決定する。ノードの総個数と総量を決定したら、目標重みの非アクティブの組を特定する（すなわちＴＷＭＮが奇数の場合にはＳＥＴ０、ＴＷＭＮが偶数の場合にはＳＥＴ１）。次いで（目標重みが変更されている場合には）この非アクティブの組を用いて目標重みの新たな組を算出する。次いでＴＷＭＮ２９２０をインクリメントする。この結果、アクティブである組が変更される。
【００４５】
目標重みの非アクティブの組を特定したら、ノード・バランサ２３５は次にシステムが専用プロセッサおよび共用プロセッサのどちらで構成されているのかを判断する。システムが非分割のコンピュータ装置であるなら、定義によりそのプロセッサは専用である。なぜなら、（図１の場合のように）プロセッサを共用する可能性のあるシステムが他に存在しないからである。しかし、論理パーティションから成るシステムは共用プロセッサを使用する場合もあるし、専用プロセッサを使用する場合もある。図２を暫時参照すると、ノードが複数のパーティションにまたがっているということは当該パーティション群が当該ノードにあるプロセッサ群を共用しているということを必ずしも意味しないということが分かる。所定のノードにあるプロセッサ群を複数のパーティションの間で共用することができる。あるいは、複数のパーティション群を少なくとも１つの専用プロセッサによってサポートすることができる。専用プロセッサを有するパーティションは構成の変更を通知されるような時まで、当該専用プロセッサを排他的に使用することができる。共用プロセッサを有するパーティションはそのように通知されることはなく、コンピュータ装置上で利用可能な任意のプロセッサを使用することができる。システムのプロセッサの性質は構成マネージャ２４０がノード・バランサ２３５に提供する。システムが共用プロセッサを使用する場合、非アクティブの組中のノードごとの目標重みを、システムが利用可能な当該ノードにあるメモリと全ノードにわたってシステムが利用可能なメモリの総量との比に等しくする（ブロック１００６）。次いで、ブロック１０２０においてＴＷＭＮ２９２０をインクリメントする。その結果、非アクティブの目標重みの組がアクティブな目標重みの組に変化する。
【００４６】
システムが共用プロセッサを使用していない場合（ブロック１００８）、ノード・バランサ２３５は当該システムにプロセッサおよびメモリの双方を備えたノードが存在するか否かを判断する（ブロック１０１２）。ＮＯ（すなわちプロセッサおよびメモリの双方を備えたノードは存在しない）という判断は普通ではないが、ありうる。たとえば、プロセッサをいくつか備えるがメモリを備えないノードとメモリは備えるがプロセッサを備えない他のノードを有するように、好適な実施形態のコンピュータ・システム１００のパーティションを構成することは可能である。このような場合、ノード・バランサ２３５は非アクティブの目標重みの組中のノードごとの目標重みを、当該ノードのプロセッサの個数とノード全体にわたってシステムが利用しうるプロセッサの個数との比に等しくセットする（ブロック１０１６）。この結果、プロセッサを備えないノードの目標重みは「０」にセットされる。次いで、ブロック１０２０においてＴＷＭＮ２９２０をインクリメントする。この結果（ここでも）、非アクティブの目標重みの組はアクティブな目標重みの組に変化する（ブロック１０２０）。
【００４７】
ブロック１０１２においてノード・バランサ２３５がいくらかのメモリと組み合わさったプロセッサを少なくとも１つを備えたノードが少なくとも１つ存在すると判断した場合、ノード・バランサ２３５は次に少なくとも１つのプロセッサといくらかのメモリを備えたノードにあるプロセッサの総数を確認することになる（ブロック１０１４）。次いで、目標重重みの非アクティブの組を更新し、少なくとも１つのプロセッサといくからのメモリを備えたノード用の目標重みを、当該ノードのプロセッサの個数と上述したプロセッサの総数との比にセットする（ブロック１０１８）。プロセッサおよびメモリの双方を備えないノード用の非アクティブの組中の目標重みは「０」にセットする（ブロック１０２２）。次いで、ブロック１０２０においてＴＷＭＮ２９２０をインクリメントする。この結果（ここでも）、非アクティブの目標重みの組がアクティブな目標重みの組に変化する（ブロック１０２０）。
【００４８】
図１４のフローチャートを通じてとる経路とは無関係に、ノード・バランサ２３５は結局、目標重み、プロセッサの個数、およびメモリの量をノードごとにノード・アンカ構造体にコピーすることになる（ブロック１０２４）。こうするのは後続する段落で説明するように、「カーネル・コンポーネントによる均衡化の通知」を有意義なものにするためである。図４３は好適な実施形態で使用するノード・アンカ構造体を示す図である。各ノード・アンカ構造体はＩＤ（３００５）、現在重み、プロセッサ、およびメモリ（３０１５）、ならびに、前回の重み、プロセッサ、およびメモリ（３０２０）を備えている。ノード・アンカ構造体３０００には一連のリソース・アンカも示されている。これらアンカの使用は、登録済みコンポーネントがシステム全体の作業の分配状況に基づいてノードごとに割り当てたリソースまたはリソースへのポインタを当該登録済みコンポーネントが収納することにより行なう。この後者の概念は後続する段落においてより詳細に説明する。
【００４９】
図１１に戻る。ノード・バランサ２３５は次に現在重みと目標重みとの間の差分（differential) を算出する（ブロック７３０）。差分とはノードごとの現在重みと目標重みとの差（difference）の絶対値の合計のことである。次いで、ノード・バランサ２３５の処理は図１２のブロック８００において継続する。次いで、重み差分閾値（ＷＤＴ）を、算出したばかりの差分の３／４にセットする。図４１はＷＤＴ２９２４を示す図である。ＷＤＴは実際の作業分配が所望の新たな作業分配とはかなり相違するという事実を理解するのに適している。システムは（現在重みで表される）現在の作業分配が目標重みに近づくように調整するように動作するが、そうするには長い時間を要する。したがって、登録済みカーネル・コンポーネントが新たな目標重みに従ってそのリソースを再調整するだけでは適切でない。それゆえ、登録済みコンポーネントにそのリソースをより漸進的に調整する機会を与えるために、いわゆる遷移重みとともにＷＤＴを使用する。後述するように、遷移重みは登録済みコンポーネント用に中間均衡化点を提供しうるように、現在重みと目標重みとの間の値に設定する。好適な実施形態では、現在重みと目標重みとの差が遷移重みを使用しても差し支えないほど十分に大きくなる時を判断するためにＷＤＴを使用する。後続する記述において見るように、好適な実施形態のＷＤＴは重み差分の３／４〜１／６４（０．０１５６２５）の値をとる。
【００５０】
ＷＤＴを差分の３／４にセットしたら、ノード・バランサ２３５は差分が１／３２未満であるか否かを判断する（ブロック８０５）。ＮＯなら、ノード・バランサ２３５は差分から１／３２を減算した後、その結果がＷＤＴ２９２４より小さいか否かを判断する。その結果がＷＤＴ２９２４より小さい場合、ＷＤＴ２９２４を差分の１／３２未満にリセットする。ブロック８０５における検査の結果とは無関係に、ノード・バランサ２３５は結局、ＷＤＴ２９２４が１／６４以下であるか否かを判断する（ブロック８２０）。ＷＤＴ２９２４が１／６４以下であるなら遷移重みの使用は保証されないから、ＷＤＴ２９２４を「０」にセットした後、現在の組（３０１５）中のＫＣＢＮ遷移重みを目標重みと等しくする。ノード・バランサ２３５がブロック８２０においてＷＤＴ２９２４は１／６４以上であると判断した場合、ノード・バランサ２３５はＫＣＢＮ遷移重み（３０１５）の現在の組を現在重みと（新たな）目標重みとの間の値にセットする。好適な実施形態では、これは次に示す式に従って行なう。
遷移＝目標＋（現在−目標）×ＷＤＴ／重み差分
【００５１】
続いて、ノード・バランサ２３５は図１３のブロック９００に進む。そこで、ＫＣＢＮ現在重み（３０１５）の現在の組を現在重みにセットする。次いで、登録済みコンポーネント（３１０５）ごとに指定されたカーネル・コンポーネント・メソッド（図４４参照）を呼び出す（ブロック９０５）。
【００５２】
呼び出されると（図１３のブロック９０５参照）、カーネル・コンポーネント・メソッドは各ノードに格納されているＫＣＢＮ情報へのアクセス権を有するようになる。現在重み、遷移重み、および目標重み、ならびにそれら重みの前回の値のコピーが、呼び出されたメソッドにとって利用可能になる。プロセッサの個数およびメモリの量の現在値および前回値も呼び出されたメソッドにとって利用可能になる。これらの情報はすべて、呼び出されたメソッドがそのリソースを最も効率的に使用する方法を決めるうるという点で好適である。上述した通知サービスを使用しうるカーネル・コンポーネントの例として統合ファイル・システム（ＩＦＳ）を挙げることができる。ファイル・システムは通常、事前に生成したスレッドの組を用いて様々な機能を果たしている。たとえば、ＩＦＳはハード・ディスク駆動装置（ＨＤＤ）の読み取りを実行するスレッドの組とＨＤＤの書き込みを実行するスレッドの別の組とを備えている。これらのスレッドを最も効率的に利用するには、ＩＦＳは好適な実施形態を使用して作業の分配と整合した態様でスレッドを分配するのが最良である。ＩＦＳに付随するカーネル・コンポーネント・メソッドがＫＣＢＮ重みを考慮して作業を第１のノードから第２のノードへ移動させることに決めたと仮定すると、当該メソッドは第１のノードにあるその事前に生成したスレッドの一部または全部を破棄し、第２のノードにスレッドを生成することになるであろう。次いで、ＫＣＢＮ情報の現在の組をＫＣＢＮ情報の前回の組にコピーした後、「カーネル・コンポーネントによる均衡化の通知」の「構成の変更」の側面用の処理は終了する。
【００５３】
（遷移重みの再計算）
この明細書の前章は構成の変更が生じたときに遷移重みを計算して好適な実施形態にセットする方法に関するものであった。したがって、この明細書のこの章は遷移重みを周期的に再計算し周期的に通知することによって漸進的に再均衡化しうるようにする方法に関するものである。図１８〜図２１は好適な実施形態のウオッチドッグ・ハンドラ２２５で使用するステップ群を示す図である。上述したように、好適な実施形態のウオッチドッグ・ハンドラ２２５は毎秒実行され、好適な実施形態の様々な側面に関係する機能を備えている。しかし、この特定の記述（すなわち遷移重みの再計算）のために重要なのは、これらの側面の一部分のみである。したがって、ここでは図面および処理ブロックの一部分を示すのみにして他の部分は後続する段落のために省略する。図１８において、処理ブロック１１０５〜１１１４は好適な実施形態の他の側面に関するものである。図１８のブロック１１１６において、ウオッチドッグ・ハンドラ２２５は現在重み呼び出しカウント値（ＣＷＩＣ）をインクリメントする。ウオッチドッグ・ハンドラ２２５は毎秒実行されるから、ＣＷＩＣは毎秒インクリメントされることになる。（図４０にＣＷＩＣ２９１０を示す。）次いで、ウオッチドッグ・ハンドラ２２５は当該間隔の間に最大呼び出しカウント値に到達したか否かを判断する（ブロック１１２０）。好適な実施形態では、最大呼び出しカウント値は「７」である。カウント値が７になると、現在重みの間隔が終了した旨が通知される。
【００５４】
完了した現在重み間隔をウオッチドッグ・ハンドラ２２５が処理する様子を図２１に示す。まずブロック１４０５において、非アクティブの組中にあるＤＣＰの累算値（図４０のＤＣＰＡ２９１２および２９１６を参照）を規格化する。（どのＤＣＰＡの組が非アクティブであるかの判断は上述したＣＷＩＮ２９０８の検査（ＣＷＩＮ２９０８が奇数ならＳＥＴ０であり、ＣＷＩＮ２９０８が偶数ならＳＥＴ１である）によって行なう。）好適な実施形態では、この規格化は累算値を当該間隔中における呼び出し回数（すなわち７）で除算することにより行なう。ここで留意点を挙げると、図２１に示すステップ群のうちのいくつか（すなわちブロック１４０５〜１４３５）は「カーネル・コンポーネントによる均衡化の通知」とは関係ない。それにもかかわらずこれらの事項を説明したのは、こらのステップが現在重み間隔の終わりに実行されるからである。
【００５５】
次いで、ウオッチドッグ・ハンドラ２２５はディスパッチ・ハンドラ２３０が収集した現在重みのサイクル・カウント値を抽出する（ブロック１４１０）。好適な実施形態では、これらのカウント値はプロセッサごとに設けられたデータ構造体（図示せず）にホーム・ノードごとに格納されている。次いで、ウオッチドッグ・ハンドラ２２５は取得したばかりのサイクル・カウント値から非アクティブの組に前回格納したサイクル・カウント値（図４０のＲＥＣＣを参照）を減算して、ＣＷＩが満了している間に実行したサイクル数をホーム・ノードごとに得る。次いで、この結果を、前回の値を置換することより非アクティブの組に書き戻す（ブロック１４１５）。次いで、ブロック１４２０において、アクティブな組からＲＥＣＣを抽出し、それを２で除算した後、非アクティブの組の値に（ノードごとに）加算する。この結果、好適な実施形態において、最近実行されたサイクル・カウント値として考慮する値が得られる。
【００５６】
次いで、ブロック１４２５においてＣＷＩＮ２９０８をインクリメントして非アクティブの組（すなわち最新のカウント値を有する組）をアクティブな組に切り換える。次いで、ブロック１４３０においてＣＷＩＣを「０」にセットして新たなＣＷＩへの開始とする。次いで、ウオッチドッグ・ハンドラ２２５が、ブロック１４１０において収集したカウント値を新たに切り換えた非アクティブの組に格納し、（次のＣＷＩの終わりにおける）これらと同じ計算のための基盤を形成する（ブロック１４４０）。次いで、ブロック１４５０においてＷＤＴ２９９４を「０」と比較する。ＷＤＴが非「０」であることと現在重みの終了とが重なったら、遷移重みを再計算する必要があるか否かを判断する必要があることを通知する。図２２と図１２は好適な実施形態で使用する遷移重みを再計算するステップ群の概要を示す図である。はじめに図２２を参照する。まずブロック１５００において目標重みを取得する。
【００５７】
好適な実施形態において目標重みを取得するのに使用する機構を図１５に示す。図１５のブロック１０３０において、目標重み変更数（ＴＷＭＮ）を抽出する。次に図４０を参照する。そこには「目標重みの組」２９２２と目標重み変更数（ＴＷＭＮ）２０２０とが示されている。図示するように、好適な実施形態で使用する目標重みの組には２つある（ＳＥＴ０とＳＥＴ１）。ＴＷＭＮ２９２０が奇数の場合、ＳＥＴ１はアクティブな組であり、ＳＥＴ０は非アクティブの組である。ＴＷＭＮ２９２０が偶数の場合、ＳＥＴ０はアクティブな組であり、ＳＥＴ１は非アクティブの組である。次いで、ノード・バランサ２３５が、ＴＷＭＮ２９２０が奇数であるか偶数であるかを判断するためにそれを検査する（ブロック１０３２）。ＴＷＭＮ２９２０が偶数の場合、各ノード用の目標重みはＳＥＴ０から抽出する（ブロック１０３４）。ＴＷＭＮ２９２０が奇数の場合、各ノード用の目標重みはＳＥＴ１から抽出する（ブロック１０３６）。次いで、ブロック１０３８において再度、ＴＷＭＮ２９２０を抽出し、ブロック１０４０において変化がないか検査する。ＴＷＭＮ２９２０が不変である場合、ブロック１０４２において目標重みの前回抽出した組を書き戻す。ＴＷＭＮ２９２０が変化している場合、奇数／偶数を検査するステップ群、組の抽出、および変化の検査をＴＷＭＮ２９２０が不変になるまで繰り返す。ＴＷＭＮ２９２０を不変の状態にするという要件はアトミシティのために必要とされる。この明細書の「作業の再均衡化」の章および「ホーム・ノードの割り当て」の章において、ノード・バランサ２３５が、ＴＷＭＮ２９２０をインクリメントしながら目標重みの値を検索・取得する例の概要を示す。
【００５８】
図２２に戻る。ブロック１５０５において現在重みを取得する。現在重みを取得するために好適な実施形態で使用するステップ群の詳細については上述した図１６の説明を参照されたい。次いで、現在重みと目標重みとの間の重み差分を計算する。上述したように、差分とはノードごとの重みの差の絶対値の合計のことである。次いで、この差分とＷＤＴ２９９４とを比較する。差分がＷＤＴ２９９４よりも大きい場合、遷移重みは再計算する必要がない。しかし、差分がＷＤＴ２９９４以下の場合には、図１２と図１３に付随して上述した処理を用いて再計算する。詳細については、それらの図の説明を参照されたい。
【００５９】
［ホーム・ノードの割り当て］
図３に暫時戻る。好適な実施形態では実行可能なスレッドを必要なスレッド制御構造体とともに生成するのにＴＣＭ２０５を使用する。実行可能なスレッドにホーム・ノードを割り当てることはこの生成プロセスの一部である。ホーム・ノードの割り当てが重要なのはＴＤＭ２１５はスレッドを当該スレッドに割り当てられたホーム・ノードで可能な限り実行するように偏向しており、ＴＤＭ２１７はスレッド用のメモリを当該スレッドに割り当てられたホーム・ノードに可能な限り割り付けるように偏向しているからである。この偏向の含意はシステム全体の使用率とリソースの割り付けとに関係している。好適な実施形態では、ホーム・ノードをスレッドに割り当てることはシステムはスレッドを当該スレッドのホーム・ノードで優先的に実行し、メモリを当該スレッドのホーム・ノードに優先的に割り付ることを意味する。ここでは、これを「ノードの親和性」と呼ぶ。無論、特定のノードがただ１つのプロセッサで構成されている場合には、この親和性はプロセッサの親和性になる。また、当業者が認識しうるよにう、本発明は好適な実施形態によって実現される特定の種類の親和性に限定されない。たとえば、スレッドを常に当該スレッドのホーム・ノードで実行するという要件に等しい厳格な親和性も本発明の本旨と範囲の内である。
【００６０】
上述したように、好適な実施形態ではシステム中の作業の所望の分配を特徴付けるために目標重みを使用する。システム中の作業の現在の分配を特徴付けるために現在重みを使用する。すべてのスレッドが同量の作業を行なうのだとしたら、新たなスレッド用にホーム・ノードを決定することは単純になるであろう。すなわち、ホーム・ノードは各ノードに割り当てるられている既存のスレッドの個数を維持することを基に、目標重みと同じ割合で割り当てるだけでよくなるであろう。しかし、スレッドはそれぞれ異なる量の作業を行なっているのが現実であるから、あるスレッドが行なうことになる作業の量を事前に知ることは不可能である。したがって、好適な実施形態では、目標重みおよび現在重みの双方に基づいて開始重みを生成し、各ホーム・ノードに割り当てるスレッドの個数をこの開始重みと同じ割合に維持しうるようにホーム・ノードを割り当てている。目標重みよりも大きな現在重みを有するノードはその開始重みの組がその目標重みよりもいくぶん小さい（すなわち、このようなノードは本来のものよりも大きな作業負荷の割り当てをすでに有している）。一方、目標重みよりも小さな現在重みを有するノードはその開始重みの組がその目標重みよりもいくぶん大きい（すなわち、このようなノードは本来のものよりも小さい作業負荷の割り当てを現在有している）。ノードごとに開始重みを算出するときに、現在重みはシステムがビジーであるほどより大きな影響を受ける。
【００６１】
図３５はホーム・ノードの割り当ての高次のステップ群を示す図である。ＴＣＭ２０５はブロック２６０５を処理する際にノードごとに開始重みを取得する。図３６〜図３９はこのプロセスが好適な実施形態において機能する様子の概略を示す図である。次に、図３６を参照する。ＴＣＭ２０５はまずブロック２７０５において開始重みＩＤ（ＩＷＩＤ）を抽出する。図４１はＩＷＩＤ２９２８と開始重み２９３０を示す図である。次いで、ブロック２７１０においてＣＷＩＮ２９０８を抽出した後、ＴＣＭ２０５はブロック２７１５においてＩＷＩＤとＣＷＩＮとが一致するか否かを判断する。ＩＷＩＤとＣＷＩＮとが一致しない場合、既存の開始重みは期限切れであるから、ＴＣＭ２０５は図３７のブロック２８００に進み新たな開始重みを算出する。
【００６２】
ブロック２８０５において現在重みをＣＷＩＤおよびＤＣＰとともに取得する。これらのステップ群の説明については上述した図１６の記述を参照されたい。次いで、ブロック２７１０において抽出したＣＷＩＮの値をブロック２８１０においてＣＷＩＤにセットし、それが現在重みに付随する間隔数を表すようにする。次いで、ブロック２８１５において目標重みを取得する。これらのステップ群の説明については上述した図１５の記述を参照されたい。
【００６３】
ＴＣＭ２０５はブロック２８２０において第１のノードについて開始した後、目標重みと現在重みとを組み合わせてノードごとに開始重みを生成する。目標重みと現在重みとを組み合わせる際、所定のノードについて、そのＤＣＰが大きいほど、結果として得られる当該ノード用の現在重みが大きな影響を受けるようにする。
【００６４】
これらの重みを組み合わせる手順の第１の部分は現在重みの影響を支配することになる乗数を算出することである。ＤＣＰが７５％以下である場合（ブロック２８２５）、現在重みの影響はブロック２８５０において「（ＤＣＰの３乗）／（７５％の２乗）」と等しくなるように乗数を設定することにより抑制する。他方、ＤＣＰが１００％未満である場合（ブロック２８３５）、現在重みの影響はブロック２８５５において「１００％−（（（１００％の２乗）−ＤＣＰ）／（２５％の２乗））」と等しくなるように乗数を設定することにより誇張する。また、ＤＣＰが１００％以上である場合（ブロック２８３５）、現在重みの影響はブロック２８４０において乗数を１００％に設定することにより最大化させる。上記３つの経路のどれをとるかと無関係に、乗数は０％〜１００％になる。
この値は第２の部分で使用する。
【００６５】
これらの重みを組み合わせる手順の第２の部分は現在重みが受けうる影響の量に応じて、現在重みが目標重みよりも小さい場合に開始重みが目標重みよりも大きくなるのを可能にし、現在重みが目標重みよりも大きい場合に開始重みが目標重みよりも小さくなるのを可能にする除数を算出することである。ＴＣＭ２０５はブロック２８６０において「目標重み＋（（現在重み）−（目標重み））×乗数」に等しい除数を算出する。したがって、結果として得られる除数は乗数の値に応じて「（目標重み）〜（現在重み）」の範囲の値になる。この除数は下で説明する手順の第３の部分で使用する。
【００６６】
手順の第３の部分は「（目標重みの２乗）／除数」を実行して非規格化開始重みを算出することである（ブロック２８７５）。この結果、現在重みが小さい場合は開始重みが大きくなり、現在重みが大きい場合は開始重みが小さくなる。「０」で除算する可能性を避けるために、ＴＣＭ２０５は除数が「０」でないか検査する（ブロック２８７０）。ＹＥＳの場合でも、ＴＣＭ２０５はブロック２８６５において開始重みを目標重みに設定するだけである。次いで、ＴＣＭ２０５は処理すべきノードがほかにもないか検査する（ブロック２８９０）。ＹＥＳの場合、ＴＣＭ２０５は残りのノードの各々について上述した処理を繰り返す。ＴＣＭ２０５はすべてのノードを検討したと判断したら、図３６のブロック２７５０に進む。接続ブロック２７５０を経由して図３６の論理に戻ったら、ＴＣＭ２０５は非規格化開始重みを規格化した後、それらを開始重み２９３０に格納する（ブロック２７４５）。好適な実施形態では、開始重みの規格化は各非規格化開始重みをすべてのノードのすべての開始重みの合計で除算することにより行なう。次いで、開始重みが有効である現在重み間隔を指定するために、ブロック２７３５においてＩＷＩＤをＣＷＩＤにセットする。
【００６７】
現在説明中の実行経路とブロック２７１５からのＹＥＳ分岐とはブロック２７２５において収束する。そこでＴＣＭは開始重みを抽出した後、ＣＷＩＮを再度抽出する。新たに抽出したＣＷＩＮと前回抽出したＣＷＩＮとが異なる場合、開始重みは期限切れであるから、上述した開始重みを算出するステップ群を図３７のブロック２８０５から新たに開始する。新たに抽出したＣＷＩＮと前回抽出したＣＷＩＮとが同一である場合、抽出した開始重みは最新であるから、図３５の論理に戻る。
【００６８】
図３５のブロック２６１０に戻る。ＴＣＭ２０５は現存しているスレッドの個数をノードごとに算出する。好適な実施形態では、カーネル・サービス１３７はスレッドが生成されるとカウンタをインクリメントし、スレッドが破棄されるとカウンタをデクリメントすることによりノードに存在するスレッドを追跡している。したがって、スレッドの合計個数はカウンタを合計することにより算出する（ブロック２６１５）。次いでブロック２６２０において、スレッドの目標個数をノードごとに算出する。好適な実施形態では、これはスレッドの合計個数に各ノードの開始重みを乗算することにより行なう。実際のスレッドの個数と目標のスレッドの個数との間の相違が最も大きいノードが生成したばかりのスレッド用のホームとして選定するノードになる（ブロック２６２２）。
【００６９】
（作業の再分配）
［概要］
上では本発明の好適な実施形態がシステム内における作業の不均衡を検出し、適切な調整を行う手順について説明した。これは好適な実施形態ではウオッチドッグ・ハンドラ２２５、ディスパッチ・ハンドラ２３０、およびノード・バランサ２３５の間における一連の状態駆動型の相互作用によって行なう。作業の再分配のために好適な実施形態で使用する状態を「均衡の観察」、「サイクルの記録」、および「スレッドの移動」と名付ける。「均衡の観察」なる状態は開始点になるものであるが、システム管理者が設定する。したがって、システム管理者はシステムに作業の均衡の問題が存在するか否かを判断させることができる。状態を「均衡の観察」にセットすると、ウオッチドッグ・ハンドラ２２５はここで均衡観察間隔（ＯＢＩ）と呼ぶ５３秒間を追跡する。数間隔（好適な実施形態では６間隔）が経過すると、ウオッチドッグ・ハンドラ２２５はノード・バランサ２３５に通知する。
【００７０】
ノード・バランサ２３５は稼働状態になると、状態が「均衡の観察」にセットされていることに気付く。これに応答して、ノード・バランサ２３５はシステムが期限切れになっているか否かについて高次の解析を行なう。この判断については後続する段落において詳細に説明するが、ここで留意すべき点を挙げると、きわめて頻繁に実行されるノード・バランサ２３５は実行されたサイクル数をホーム・ノードごとに追跡している。この未加工のサイクル・カウント値を用いて、ノード・バランサ２３５はその高次の均衡判断を行なう。ノード・バランサ２３５はシステムの作業負荷が不均衡になっている可能性があると判断すると、状態を「サイクルの記録」にセットした後、その旨をウオッチドッグ・ハンドラ２２５に通知する。
【００７１】
次いで、ウオッチドッグ・ハンドラ２２５は状態が「サイクルの記録」に変化していることに気付き、１サイクル記録間隔だけ追跡した後、状態を「スレッドの移動」にセットし、その旨をノード・バランサ２３５に通知する。そのうちにディスパッチ・ハンドラ２３０はノード・バランサ２３５によって、状態が「サイクルの記録」にセットされていることに気付く。これに応答して、ディスパッチ・ハンドラ２３０はサイクル・データをスレッドごとに、かつホーム・ノードごとに収集する。ディスパッチ・ハンドラ２３０は後刻、状態が「サイクルの記録」以外のものに変化したと判断すると、スレッドごとのサイクル・データの収集を停止する。
【００７２】
ノード・バランサ２３５はウオッチドッグ・ハンドラ２２５から上述した通知を受領すると、ディスパッチ・ハンドラ２３０が収集したスレッドごとのデータの低次の解析を行なう。次いで、ノード・バランサ２３５はシステムの均衡状態／不均衡状態を二重に検査した後、スレッドごとのデータを用いてシステムの作業負荷が適切に均衡していない場合に移動させるべきスレッドを決める。ノード・バランサ２３５はシステムの作業負荷が均衡していないと判断したら、スレッドをノード群間に移動させてシステムの作業負荷をより適切に均衡させる。最後に、ノード・バランサ２３５は状態を「均衡の観察」に戻し、処理を始めからやり直す。
【００７３】
［均衡観察状態におけるディスパッチ・ハンドラ２３０］
ちょうど説明し終えたのはディスパッチ・ハンドラ２３０は均衡観察状態にあるときに、実行されたサイクル数の未加工のカウント値をホーム・ノードごとに保持するという事実であった。この論理を図２３に示す。図２３に示されているのは本発明の好適な実施形態に関する、ディスパッチ・ハンドラ２３０内のステップ群である。当業者が認識しうるように、これとは無関係の他のスレッド・ディスパッチ処理が存在する。ブロック１６００において、ディスパッチ・ハンドラ２３０はディスパッチすべきスレッド用にホーム・ノードＩＤを取得する。次いでブロック１６０５において、この特定のスレッドが最後に実行したときに使用したサイクルを取得する。次いで、使用済みサイクルのカウント値を現在重みサイクル・カウント・アキュムレータにホーム・ノードごとに付加する。このカウント値はディスパッチ・ハンドラ２３０が保持しているが、それをプロセッサごとのデータ構造体（図示せず）に格納する。次いで、ディスパッチ・ハンドラ２３０は自身が均衡観察状態にいるのか否かを判断する。ＹＥＳなら、上述した使用済みサイクルを均衡観察サイクル・カウント・アキュムレータ（図示せず）に付加する。均衡観察サイクル・カウント・アキュムレータはディスパッチ・ハンドラ２３０が保持するプロセッサごとの別のデータ記憶装置である。次いで、ディスパッチ・ハンドラ２３０は自身がサイクル記録状態にいるのか否かを判断する（ブロック１６４５）。ここでは現在、我々は均衡観察状態にいるから、ディスパッチ・ハンドラ２３０はブロック１６４０に戻るだけであり、そこで残りのスレッドのディスパッチ処理を行なう。図２４の論理については下でサイクル記録状態とともにに説明する。
【００７４】
［均衡観察状態におけるウオッチドッグ・ハンドラ２２５］
図１８は「カーネル・コンポーネントによる均衡化の通知」に関して上述した。その記述の中で、これらの処理ブロックの一部（すなわちウオッチドッグ・ハンドラ２２５のもの）は作業の再分配に関係していると述べた。次に、これらのブロックを説明する。ブロック１１０５において、現在のディスパッチャ・コミットメント割合を取得する。好適な実施形態では、これらはシステム・インタフェースを通じて取得する。システム・インタフェースは本発明の利益と利点にとって重要ではないから、ここではこれ以上説明しない。ディスパッチャ・コミットメント割合はシステムのアクティビティの程度をノードごとに示すものである。ＲＥＣＣと同様に、ＣＷＩＮ２９０８を検査して非アクティブの組を特定する（図４０のＤＣＰＡ組２９１２、２９１６を参照）（ブロック１１１０）。ＣＷＩＮ２９０８が奇数ならＤＣＰをＳＥＴ０中のＤＣＰＡに付加し、ＣＷＩＮ２９０８が偶数ならＤＣＰをＳＥＴ１中のＤＣＰＡに付加する。次いで、ウオッチドッグ・ハンドラ２２５はＣＷＩＣ２９１０がその最大値に到達しているか否かを判断する（ブロック１１２０）。最大値に到達している場合、ウオッチドッグ・ハンドラ２２５は完了済みの現在重み間隔を処理する。この処理は図２１を参照して上述した（上述した点を参照）。ここでは完了済みの現在重み間隔の処理は解決済みであると仮定する。したがって、ウオッチドッグ・ハンドラ２２５は現在の状態が「均衡の観察」であるのか否かを判断する。
【００７５】
この説明の現時点の状態は「均衡の観察」であるから、ウオッチドッグ・ハンドラ２２５は図１９のブロック１２０５に進む。そこで、ウオッチドッグ・ハンドラ２２５は最古の保存領域（図４１の保存領域ＳＡ０（２９３２）〜ＳＡＮ（２９３６）を参照）へのインデックスを計算する。好適な実施形態では、この計算には図４１の観察期間数（ＯＩＮ）２９５０を抽出すること、ＯＩＮ２９５０を保存領域の個数（すなわち（Ｎ＋１））で除算すること、および結果として得られる剰余をインデックスとして使用することが含まれる。次いで、ウオッチドッグ・ハンドラ２２５はＤＣＰを最古の保存領域のＤＣＰＡにノードごとに付加する（ブロック１２１０）。次いで、最古の保存領域の呼び出しカウント値（ＩＣ）をインクリメントする（ブロック１２１５）。次いで、ウオッチドッグ・ハンドラ２２５は最大呼び出しカウント値に到達しているか否かを判断する（ブロック１２２０）。ＹＥＳなら、処理に必要な観察間隔は完了している。この処理を図２５に示す。観察間隔が完了していない場合、処理は図２０において継続する。
【００７６】
はじめに図２５を参照する。ウオッチドッグ・ハンドラ２２５はまずディスパッチ・ハンドラ２３０から均衡観察サイクル・カウント値を取得し、それらを２番目に最古の保存領域にノードごとに格納する（ブロック１７００）。（ここでも、図４１の保存領域ＳＡ０（２９３２）〜ＳＡＮ（２９３６）を参照されたい。）これらの値は結局、次の観察間隔において実行されるサイクル数の基礎になる。次いでブロック１７０５において、ウオッチドッグ・ハンドラ２２５は完了したばかりの観察間隔において実行されたサイクル数を計算する。好適な実施形態では、これはブロック１７００において取得したカウント値から最古の保存領域中のサイクル・カウント値（これは完了したばかりの観察間隔の基礎であった）を減算することにより行なう。次いで、この計算の結果を最古の保存領域に書き戻す。ブロック１７１０において、ウオッチドッグ・ハンドラ２２５は２番目に最古の保存領域のＤＣＰＡを「０」にセットする。これは次の観察間隔の間における累算に備えて行なう。次いで、ウオッチドッグ・ハンドラ２２５は２番目に最古の保存領域に対する呼び出しカウント値を「０」にセットするが、それはここでも次の観察間隔の間における累算に備えて行なう（ブロック１７１５）。次いで、ＯＩＮ２９５０をインクリメントする。この結果、自動的に最古の保存領域は最新の保存領域になり、２番目に最古の保存領域が最古の保存領域になる（ブロック１７２０）。
【００７７】
ブロック１７２５において、ウオッチドッグ・ハンドラ２２５はＯＩＮ２９５０が均衡観察閾値に到達したか否かを判断する。この値は好適な実施形態ではシステムのノード群が作業負荷の観点から均衡しているか否かを検査すべき時をノード・バランサ２３５が判断するのに使用する。好適な実施形態では、この値は「６」である。均衡観察閾値に到達していない場合、ウオッチドッグ・ハンドラ２２５はブロック１７４０において図１９の論理に戻る。均衡観察閾値に到達している場合、ウオッチドッグ・ハンドラ２２５は現在の状態が「均衡の観察」（図４０の「ノード・マネージャの状態」２９０２を参照）であるか否かを判断する。現在の状態が「均衡の観察」ではない場合、ウオッチドッグ・ハンドラ２２５はブロック１７４０において図１９の論理に戻る。この説明の現時点の状態は「均衡の観察」であるから、ウオッチドッグ・ハンドラ２２５はノード・バランサ２３５にシステムが実行中の作業はシステムのノード群間で適切に均衡しているか否かの高次の判断を実行すべきことを通知した後、図１９の論理に戻る（ブロック１７４０）。この論理は図２６とともに説明する。
【００７８】
［均衡観察状態におけるノード・バランサ２３５］
次に、図２６を参照する。ノード・バランサ２３５は直近６個の保存領域の呼び出しカウント値を合計する（ブロック１８００）。次いで、ノード・バランサ２３５はノードごとに平均ＤＣＰを算出する（ブロック１８０５）。好適な実施形態では、これは次のようにして行なう。まず、直近６個の保存領域に由来するＤＣＰをノードごとに合計する。次いで、ノードごとの合計を呼び出しカウント値の合計値（すなわちブロック１８００で求めた値）で除算する。次いで、ノード・バランサ２３５は直近６個の保存領域用の均衡観察サイクル・カウント値をノードごとに合計する（ブロック１８１０）。（図４１のサイクル・カウント値および保存領域ＳＡ０（２９３２）〜ＳＡＮ（２９３６）を参照。）次いで、ブロック１８１５においてシステムの合計を求める。均衡／不均衡の判断を行なうステップは図２７において継続する。図２７の論理はノード・バランサ２３５が各ノードにつき１回使用する。図２７の論理を使用するごとに、次に示す入力を考慮する。すなわち、（１）システムの合計サイクル・カウント値、（２）考察中のノードのＤＣＰ、（３）当該ノードの目標重み（目標重みの算出方法を説明する図１５および付随する記述を参照）、および（４）当該特定のノードのサイクル・カウント値である。
【００７９】
次に、図２７を参照する。ノード・バランサ２３５はブロック１９００において目標サイクル・カウント値を算出する。好適な実施形態では、これはすべてのノードで実行された合計サイクル数と特定のノードの目標重みとを乗算することにより行なう。その結果は考察中のノード用の目標サイクル・カウント値である。次いで、この目標サイクル・カウント値をノードのサイクル・カウント値から減算する（ブロック１９１０）。
【００８０】
好適な実施形態では目標サイクル・カウント値の１／３２を許容差として使用しているから、実際のサイクル・カウント値が目標サイクル・カウント値の１／３２以内であれば、わずかに均衡を失していても当該ノードは均衡していると言える。この許容差の適用は処理ブロックの対１９０５／１９２０と１９１５／１９２５の論理において見ることができる。実際のサイクル・カウント値が目標サイクル・カウント値よりもわずかに小さいだけの場合（ブロック１９０５、１９２０）、「０」なる結果を返す（ブロック１９３５）。「０」なる結果は特定のノードについて不均衡は見られないということを表している。同様に、実際のサイクル・カウント値が目標サイクル・カウント値よりもわずかに大きいだけの場合（ブロック１９１５、１９２５）、「０」なる結果を返す（ブロック１９３５）。無論、ブロック１９１０における計算の結果が「０」の場合、ブロック１９３５において「０」を返す。実際のサイクル・カウント値と目標サイクル・カウント値との差が「わずかに小さい」値よりも大きい場合、図２７の論理は実際のサイクル・カウント値と目標サイクル・カウント値との差を負の値として返すことになる（ブロック１９３０）。これは特定のノードが自身に割り付けられた適正な割合を超えることなく取りうる余分の作業量を表している。実際のサイクル・カウント値と目標サイクル・カウント値との差が「わずかに大きい」値よりも大きい場合、図２７の論理は特定のノード用のＤＣＰが７５％よりも大きいか否かを検査する。サイクル・カウント値の過剰と７５％超のＤＣＰとは当該ノードが有する作業の割合が当該ノードに割り付けられた適正な割合を超えており、実際にサイクル・カウント値の過剰が存在するということを表している。このことが判明したら、図２７の論理は実際のサイクル・カウント値と目標サイクル・カウント値との差を正の値として返すことになる（ブロック１９４５）。これは問題のノードから該当する量の作業を除去すべきことを表している。ブロック１９４０において図２７の論理がサイクル・カウント値の過剰があるにもかかわらず特定のノードのＤＣＰは７５％を超えていないと判断した場合、当該ノードを過負荷であるとしては処理はしない（ブロック１９３５）。
【００８１】
図２７の論理はノードごとに使用するものであるということ想起し、すべてのノードを考察したものとみなして、図２６に戻る。図２７の論理の結果が作業の不均衡はない（すなわち作業はシステム中において適切に分配されている）ということを示している場合、ノード・バランサ２３５はブロック１８４０において実行を終了するだけである。しかし、図２７の論理の結果が作業の不均衡（すなわち少なくとも１つのノードの作業が過剰であり、少なくとも１つのノードの作業が過少である）ということを示している場合には、ノード・バランサ２３５はブロック１８３０に進み、そこで「状態の記録」の値を初期化する。この初期化の手順を次に示す。すなわち、（１）図４２の記録期間ＩＤ２９４０をインクリメントし、（２）サイクル・カウント値をホーム・ノードごとに「０」にセットし、（３）記録期間呼び出しカウント値を「０」にセットし、（４）ＤＣＰＡ２９４８をノードごとに「０」にセットする。次いで、「ノード・マネージャの状態」２９０２を「サイクルの記録」にセットした後（ブロック１８２５）、ノード・バランサ２３５はブロック１８４０において実行を終了する。
【００８２】
［サイクル記録状態におけるディスパッチ・ハンドラ］
この説明の現時点では、現在の状態はノード・バランサ２３５によって「サイクルの記録」にセット済みであるから、処理ブロック１６４５においてディスパッチ・ハンドラ２３０はこの次にスレッドをディスパッチするときにＹＥＳと評価することになる。したがって、ディスパッチ・ハンドラ２３０は次にスレッドのホーム・ノードが移動可能であるか否かを判断する（図２４のブロック１６０９）。ＮＯなら、ディスパッチ・ハンドラ２３０はブロック１６６０において「サイクルの記録」のサイクル・アキュムレータをインクリメントした後、図２３の論理に戻るだけである。ＹＥＳなら、ディスパッチ・ハンドラ２３０は記録期間ＩＤが一致するか否かを判断する（ブロック１６１０）。この判断はスレッド制御構造体中に保持されている記録期間ＩＤと図４２の記録期間ＩＤ２９４０とを比較することにより行なう。こらのＩＤが一致する場合、ディスパッチ・ハンドラ２３０はカウントした未加工のサイクル値を、スレッド構造体（図示せず）に格納済みの既存の合計値に加算する（ブロック１６５５）。これらのＩＤが一致しない場合、現在の期間用の未加工のサイクル・カウント値はこの特定のスレッドの制御構造体にまだ格納されていないから、スレッド制御構造体中の記録期間ＩＤを記録期間ＩＤ２９４０に格納されている値にセットする（ブロック１６５０）。そして、サイクル・カウント値を最近実行されたサイクル値と等しい値にセットする（ブロック１６６５）。これはブロック１６０５において確認する値である。処理ブロック１６１０における評価方法とは無関係に、ホーム・ノードの記録済みサイクル値の合計値もブロック１６６０においてインクリメントする。
【００８３】
［サイクル記録状態におけるウオッチドッグ・ハンドラ２２５］
図２０に戻って処理を継続する。ウオッチドッグ・ハンドラ２２５がこの次に実行される時、「ノード・マネージャの状態」はノード・バランサ２３５によって「サイクルの記録」にセットされているから、処理ブロック１３０５における評価はＹＥＳになる。ウオッチドッグ・ハンドラ２２５はＤＣＰを記録状態のＤＣＰＡに加算する（図４２の符号２９４８のＤＣＰＡを参照）（ブロック１３１０）。次いでブロック１３１５において、記録期間ＩＤ２９４２をインクリメントする。次いで、ウオッチドッグ・ハンドラ２２５は記録期間ＩＤ２９４２を検査して最大値に到達しているか否かを判断する。好適な実施形態では、この最大値は「５３」である。最大値に到達していない場合、ウオッチドッグ・ハンドラ２２５はブロック１３４０において終了するだけである。ウオッチドッグ・ハンドラ２２５はブロック１３２０において最大値に到達していると判断した場合、ディスパッチ・ハンドラ２３０から記録済みのサイクル・カウント値を取得し、それらをサイクル・カウント値記憶領域２９４８に格納する。次いで、ウオッチドッグ・ハンドラ２２５はブロック１３３５において状態を「スレッドの移動」にセットし、ブロック１３３０においてノード・バランサ２３５にスレッドを移動するように通知した後、ブロック１３４０において終了する。
【００８４】
［スレッド移動状態におけるノード・バランサ２３５］
好適な実施形態内にけるスレッドの移動を説明するために、ここでは図２８を使用する。ノード・バランサ２３５はまずノード当たりの平均ＤＣＰを算出する（ブロック２０００）。好適な実施形態では、これはＤＣＰＡ２９４８に保持されている値を当該期間における間隔の合計数（すなわち記録期間ＩＣ２９４２）で除算することにより行なう。次いで、ノード・バランサ２３５はＤＣＰＡ２９４８の累算サイクル・カウント値を合計する（ブロック２００５）。この値は記録期間中におけるシステム用の合計値になる。
【００８５】
次いで、ノード・バランサ２３５は記録期間を通じて作業はシステム中で適正に分配されているか否かを判断する。好適な実施形態では、これは図２７に示す論理によって行なう。想起しうるように図２７は上述したから、ここではその詳細を再言しない。しかしながら、図２７の論理はノードごとに使用することを想起し、すべてのノードを考察したものとみなして、図２８に戻る。図２７の論理の結果が作業の不均衡はないということを示している（すなわち作業がシステム中に適正に分配されている）場合、ノード・バランサ２３５はブロック２０３５において状態を「均衡の観察」にセットした後、ブロック２０４０において実行を終了するだけである。しかし、図２７の論理の結果が不均衡を示している（すなわち少なくとも１つのノードは作業が過剰であり、少なくとも１つのノードは作業が過少である。そして、同じノード群は均衡観察状態においてそれぞれ作業過剰および作業過少であることが観察れる）場合、ノード・バランサ２３５はブロック２０２０に進み、そこで移動させるべきサイクル数を決める。ブロック２０１０においてサイクル不足のノードとサイクル過剰のノードを特定したことを想起されたい。次いで、ノード・バランサ２３５は移動させるべきサイクル数を最大過剰および最大不足のうちの小さい方の値の１／２にセットする。次いで、ノード・バランサ２３５はこれに基づいてスレッドを移動させる。
【００８６】
図２９〜図３２はこの仕事を実行するために好適な実施形態で使用するノード・バランサ２３５の論理を示す図である。始めにブロック２１００において、空のリストを作成する。このリストは結局、移動させる候補のスレッドを保持することなる。次いでブロック２１０５において、ノード・バランサ２３５はシステムが保持しているスレッドのリストから最初のスレッド（または２番目のスレッド）を選定する。次いで、ノード・バランサ２３５は当該スレッドがそれに関連付けられた現在の記録期間ＩＤを有するか否かを判断する（ブロック２１１０）。ＮＯの場合、ノード・バランサ２３５は考察すべきスレッドがほかにあるか否かを判断する。ＹＥＳの場合、ノード・バランサ２３５は次のスレッドを選定し（ブロック２１０５）、この場合にも当該スレッドに現在の記録期間ＩＤが関連付けられているか否かを判断する。図３０は現在の記録期間ＩＤを有するスレッドを処理するために使用する論理を示す図である。ノード・バランサ２３５はまずブロック２１２０において問題のスレッド用のホーム・ノードが過剰のサイクルを有するものであると以前に判断したノードであるか否かを判断する。ＮＯの場合、上述したように、図２９のブロック２１１１において処理を継続する。問題のスレッドのホーム・ノードがまさに過剰のサイクルを有するノードである場合、ノード・バランサ２３５はその特定のスレッドがＭＡＧの構成要素であるか否かを判断する。この場合、そのグループのすべてのスレッドのホーム・ノードが同じである必要がある（ブロック２１２５）。ＮＯの場合、ノード・バランサ２３５はこのスレッドが記録したサイクルを抽出する（ブロック２１３０）。次いで、ノード・バランサ２３５はこのスレッドを候補リストに付加し、その記録されたサイクル数に基づいて当該スレッドをランク付けする（最大のものを最上位にする）。次いで、ノード・バランサ２３５は図２９のブロック２１１１において処理を継続する。
【００８７】
図３０のブロック２１２５においてノード・バランサ２３５が問題のスレッドは確かにグループの構成要素であると判断した場合、ノード・バランサ２３５は当該グループはこの記録期間中に以前に遭遇したものであるか否かを判断する（ブロック２１４０）。ＹＥＳの場合、図２９のブロック２１１１において処理を継続する。ＮＯの場合、ノード・バランサ２３５は当該グループ用に合計サイクル・カウント値（すなわち当該グループのスレッド群の記録されたサイクル数の合計値）を算出した後（ブロック２１４５）、当該グループ用の当該合計サイクル・カウント値に基づいて当該グループを移動候補リストに付加する（ブロック２１５０）。これを行なったら、図２９のブロック２１１１において処理を継続する。
【００８８】
すべてのスレッドを考察したら、処理ブロック２１１１における評価はＮＯになる。そして、ノード・バランサ２３５はスレッドを実際に移動させてシステムを再均衡化させる。この仕事を行なうために、好適な実施形態で使用する論理を図３１に示す。ブロック２２００において、ノード・バランサ２３５は候補リストの中から最初のスレッド（２番目のスレッド）を選定する。リストの最後に到達していないものとすると（ブロック２２０５）、ノード・バランサ２３５は問題のスレッドまたはＭＡＧのサイクル数が移動させるのに必要なサイクル数（処理ブロック２０２０と付随する記述を参照）よりも大きいか小さいかを判断する（ブロック２２１５）。当該スレッドまたはＭＡＧが使用したサイクル数が移動させるのに必要なサイクル数よりも大きい場合、ノード・バランサ２３５はブロック２２００において処理を継続するだけである。ＮＯの場合、ノード・バランサ２３５は考察しているものがスレッドなのかグループなのかを判断する（ブロック２２２５）。スレッドである場合、ノード・バランサ２３５は図３２の論理に進む。グループである場合、ブロック２２３０において当該グループ用のホーム・ノードを変更した後、当該グループ中の各スレッドに対して図３２の論理を使用する。
【００８９】
次に、図３２を参照する。ノード・バランサ２３５は問題のスレッド用のホーム・ノードを変更する（ブロック２３００）。この特定のスレッドがこの特定のホーム・ノードに留まる限り、ＴＤＭ２１５は当該特定のスレッドをディスパッチしてその新たなホーム・ノードで実行させようとする。そして、ＴＤＭ２１７は当該特定のスレッドの新たなホーム・ノードにおいてそれ用の記憶を取得しようとする。最後にブロック２３０５において、ノード・バランサ２３５は当該スレッドに関連付けられた重要なメモリ・ページを再構築する。好適な実施形態では、これは一時的に利用不可の旧ホーム・ノードにページを割り当て、それらのページを新たなホーム・ノードにコピーし、新たなホーム・ノードでそれらのページを利用可能にすることにより行なう。次に、図３１に戻る。スレッドまたはスレッドのグループを新たなホーム・ノードに移動させるごとに、移動させるべきサイクル数を移動済みのサイクル数だけ減少させる（ブロック２２４０）。次いでブロック２２００において、すべてのスレッドを考察するまで処理を継続する。すべてのスレッドの考察が完了すると、処理ブロック２２０５における評価はＹＥＳになる。この結果、ノード・バランサ２３５はＯＩＮを再構築する。また、ノード・バランサ２３５はノードのサイクル・カウント値を抽出し、それらを最古の保存領域に格納することにより、新たな観察間隔用の基礎も構築する（ブロック２２１０）。これらの初期化は、次の観察間隔をまったく新たに開始して、さらなる均衡化を考察する前に少なくとも６つの間隔を観察しうるにするという効果を有する。
【００９０】
初期化を実行したら、ノード・バランサ２３５は図２８のブロック２０３５に戻り、そこで状態を「均衡の観察」にセットした後、ブロック２０４０において処理を終了する。
【００９１】
本明細書の「作業の再分配」の章の始めにおいて、状態はシステムの管理者が始めに「均衡の観察」にセットすると指摘した。これが必要な理由はユーザが呼び戻すと、「ノード・マネージャの状態」２９０２はＩＰＬの間に現在重みにセットされる（図１０のブロック６０５を参照）からである。図３３と図３４はそれぞれホーム・ノードの移動を有効にする（すなわち再均衡化する）ための、およびホーム・ノードの移動を無効にするためのシステムとシステム管理者との間の対話を示す図である。好適な実施形態では、システムの管理者はユーザ・インタフェース１５０によってコンピュータ・システム１００と対話する。その場合、システムの管理者はコマンドを入力してノード・マネージャ２２０に自身を「均衡の観察」状態にセットするように命じる。これにより、ホーム・ノードは移動しうるようになる。図３３のブロック２４００において、ノード・マネージャ２２０は自分はすでに「均衡の観察」状態にいるのか否かを判断する。ＹＥＳの場合、ノード・マネージャ２２０はシステムの管理者に（ユーザ・インタフェース１５０を通じて）ホーム・ノードの移動はすでに有効になっていると通知するだげでよい（ブロック２４０５）。ノード・マネージャ２２０が「均衡の観察」状態にいない場合、ノード・マネージャ２２０はＯＩＮを初期化するが、このことは図３１のブロック２２１０に付随する記述において説明した。次いで、ノード・マネージャ２２０はブロック２４１５においてその状態を「均衡の観察」にセットした後、復帰する。
【００９２】
システムの管理者はコマンドを入力してノード・マネージャ２２０に自身を現在重み状態にセットするように命ずることもできる。これにより、ホーム・ノードは移動てきなくなる。図３４のブロック２５００において、ノード・マネージャ２２０は自分はすでに現在重み状態にいるのか否かを判断する。ＹＥＳの場合、ノード・マネージャ２２０はシステムの管理者に（ユーザ・インタフェース１５０を通じて）ホーム・ノードの移動はすでに無効になっていると通知するだげでよい（ブロック２５０５）。ノード・マネージャ２２０が現在重み状態にいない場合、ノード・マネージャ２２０はブロック２５１０において自身の状態を現在重みにセットした後、復帰する。
【００９３】
ここに提示した実施形態と実例は本発明とその実際の応用を最もよく説明し、それにより当業者が本発明を作るとともに使うのを可能にするために提示した。しかしながら、当業者が認識しうるように、上述した記述と実例は説明と例示を目的としてのみ提示したものである。提示した記述にはそれで尽きているという意図はないし、開示したものとまったく同じ形態に本発明を限定するという意図もない。上述した教示に鑑み、特許請求の範囲の本旨と範囲の内で多くの変更と変形をなすことができる。
【図面の簡単な説明】
【００９４】
【図１】本発明の好適な実施形態を支持しうるコンピューティング環境を示すブロック図である。
【図２】本発明の好適な実施形態を支持しうる別のコンピューティング環境を示すブロック図である。
【図３】本発明の好適な実施形態のカーネル・サービスを展開した様子を示す図である。
【図４】好適な実施形態のスレッド生成機構の特徴的な処理を実行するのに使用するステップ群を示すフローチャートを示す図である。
【図５】好適な実施形態のスレッド生成機構の特徴的な処理を実行するのに使用するステップ群を示すフローチャートを示す図である。
【図６】好適な実施形態のスレッド生成機構の特徴的な処理を実行するのに使用するステップ群を示すフローチャートを示す図である。
【図７】好適な実施形態のスレッド生成機構の特徴的な処理を実行するのに使用するステップ群を示すフローチャートを示す図である。
【図８】スレッドを親和性グループから分離するための、好適な実施形態のスレッド生成機構内の特徴的なステップ群を示すフローチャートを示す図である。
【図９】親和性グループの情報を他のシステム・コンポーネントに利用可能にするための、好適な実施形態のスレッド生成機構内の特徴的なステップ群を示すフローチャートを示す図である。
【図１０】「カーネル・コンポーネントによる均衡化の通知（ＫＣＢＮ）」を行なうために、好適な実施形態で使用する様々な重みを初期化するための、ＩＰＬ（Initial Program Load) 手順内の特徴的なステップ群を示すフローチャートを示す図である。
【図１１】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図１２】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図１３】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図１４】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図１５】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図１６】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図１７】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図１８】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図１９】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図２０】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図２１】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図２２】システム内の構成の変更に応答して様々なＫＣＢＮ重みを調整するために、好適な実施形態内で使用する特徴的なステップ群を示すフローチャートを示す図である。
【図２３】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図２４】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図２５】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図２６】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図２７】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図２８】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図２９】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図３０】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図３１】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図３２】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図３３】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図３４】作業の再分配を行なうためにウオッチドッグ・ハンドラおよびノード・バランサで使用する特徴的なステップ群を示すフローチャートを示す図である。
【図３５】好適な実施形態のスレッド生成機構がホーム・ノードの割り当てを行なう方法に関する特徴的なステップ群を示すフローチャートを示す図である。
【図３６】好適な実施形態のスレッド生成機構がホーム・ノードの割り当てを行なう方法に関する特徴的なステップ群を示すフローチャートを示す図である。
【図３７】好適な実施形態のスレッド生成機構がホーム・ノードの割り当てを行なう方法に関する特徴的なステップ群を示すフローチャートを示す図である。
【図３８】好適な実施形態のスレッド生成機構がホーム・ノードの割り当てを行なう方法に関する特徴的なステップ群を示すフローチャートを示す図である。
【図３９】好適な実施形態のスレッド生成機構がホーム・ノードの割り当てを行なう方法に関する特徴的なステップ群を示すフローチャートを示す図である。
【図４０】本発明の好適な実施形態で使用するデータ構造を示す図である。
【図４１】本発明の好適な実施形態で使用するデータ構造を示す図である。
【図４２】本発明の好適な実施形態で使用するデータ構造を示す図である。
【図４３】本発明の好適な実施形態で使用するデータ構造を示す図である。
【図４４】本発明の好適な実施形態で使用するデータ構造を示す図である。
【符号の説明】
【００９５】
１００  コンピュータ装置
１２５  ネットワーク・インタフェース
１３０  処理ノード
１３１  ノード
１３２  プロセッサ
１３４  メモリ
１３５  スレッド
１３６  オペレーティング・システム
１３７  カーネル・サービス
１５０  ユーザ・インタフェース
１５５  大容量記憶装置
２００  スレッド・マネージャ
２０５  ＴＣＭ
２１５  ＴＤＭ
２１７  ＴＭＭ
２２０  ノード・マネージャ
２２５  ウオッチドッグ・ハンドラ
２３０  ディスパッチ・ハンドラ
２３５  ノード・バランサ
２４０  構成マネージャ
２９０２  「ノード・マネージャの状態」
２９０４  コンピュータ・レジストリ・ポインタ
２９０６  現在重み
２９０７  ＤＣＰ
２９０８  ＣＷＩＮ
２９１０  ＣＷＩＣ
２９１１  ＣＥＩＤ
２９１２  ＤＣＰＡ
２９１４  ＲＥＣＣ
２９１６  ＤＣＰＡ
２９１８  ＲＥＣＣ
２９２０  ＴＷＭＮ
２９２２  目標重み
２９２４  ＷＤＴ
２９２８  ＩＷＩＤ
２９３０  開始重み
２９３２  ＤＣＰＡ
２９３４  ＤＣＰＡ
２９３６  ＤＣＰＡ
２９５０  ＯＩＮ
２９４０  記録期間ＩＤ
２９４２  記録期間ＩＣ
２９４８  ＤＣＰＡ
３０００  ノード・アンカ
３００５  ノードＩＤ
３０１０  ノード状態
３０１５  「現在の状態」
３０２０  「以前の状態」
３１００  コンポーネント・レジストリ
３１０５  カーネル・コンポーネント
【図１】
2005251184.tif 000003
【図２】
2005251184.tif 000004
【図３】
2005251184.tif 000005
【図４】
2005251184.tif 000006
【図５】
2005251184.tif 000007
【図６】
2005251184.tif 000008
【図７】
2005251184.tif 000009
【図８】
2005251184.tif 000010
【図９】
2005251184.tif 000011
【図１０】
2005251184.tif 000012
【図１１】
2005251184.tif 000013
【図１２】
2005251184.tif 000014
【図１３】
2005251184.tif 000015
【図１４】
2005251184.tif 000016
【図１５】
2005251184.tif 000017
【図１６】
2005251184.tif 000018
【図１７】
2005251184.tif 000019
【図１８】
2005251184.tif 000020
【図１９】
2005251184.tif 000021
【図２０】
2005251184.tif 000022
【図２１】
2005251184.tif 000023
【図２２】
2005251184.tif 000024
【図２３】
2005251184.tif 000025
【図２４】
2005251184.tif 000026
【図２５】
2005251184.tif 000027
【図２６】
2005251184.tif 000028
【図２７】
2005251184.tif 000029
【図２８】
2005251184.tif 000030
【図２９】
2005251184.tif 000031
【図３０】
2005251184.tif 000032
【図３１】
2005251184.tif 000033
【図３２】
2005251184.tif 000034
【図３３】
2005251184.tif 000035
【図３４】
2005251184.tif 000036
【図３５】
2005251184.tif 000037
【図３６】
2005251184.tif 000038
【図３７】
2005251184.tif 000039
【図３８】
2005251184.tif 000040
【図３９】
2005251184.tif 000041
【図４０】
2005251184.tif 000042
【図４１】
2005251184.tif 000043
【図４２】
2005251184.tif 000044
【図４３】
2005251184.tif 000045
【図４４】
2005251184.tif 000046