JP2004030663A - ワークロード・マネージャをシステム・タスク・スケジューラと統合する装置および方法 - Google Patents

Abstract

【課題】システム・タスク・スケジューラをワークロード・マネージャと統合するための方法、システム、および装置を提供する。
【解決手段】
スケジューラはスレッドに初期優先順位を割り当て、実行キューに配置する。ワークロード・マネージャはシステム管理者が設定するポリシー（例えば、異なるクラスのスレッドには異る割合のＣＰＵ時間を割当てる）を実施する。もし複数クラスのスレッドが各実行キュー間に可能な限り均等に収まるならこのポリシーは達成可である。そのためスレッドはクラス毎に整理される。各クラスは使用ポリシー通りに優先順位が割振られ、これはスレッドがどの優先順位のバンドに収まるかの判断と同時に、クラス内の各スレッドに割当てるスケジューリング優先順位の修正に使われる。あるキューのあるバンドのスレッド数が別のキューの同バンドのスレッド数より規定数以上多いかが定期的に判断される。多い時はシステムは負荷不均衡とみなされ、多くない時はそのバンドの１スレッドをスレッド数が多い方のキューから少ない方のキューへと移動させ、システムを負荷均衡にする。
【選択図】　図９

Description

【０００１】
【発明の属する技術分野】
本発明はコンピュータ・システムにおけるリソース（資源）割当てに関するものである。　　より詳細には、本発明は、システム管理者によって設定されたある制約や使用ポリシー（方策）に基いてコンピュータ・システムのリソースの負荷均衡をとるための方法および装置に関するものである。
【０００２】
【従来の技術】
いかなる処理時においても、コンピュータ・システムのプロセッサあるいはＣＰＵにおいて実行されることを待つユーザー・プロセスやスレッドが重複しているという可能性はある。　その際、システムのＣＰＵを最もよく利用するためには、プロセスやスレッドを実行のために適切にキュー（待ち行列）に入れる働きをする効果的な機構を用いることが必要となる。　このタスクを完遂するためにほとんどのコンピュータ・システムで使われている機構がスケジューラである。
【０００３】
ここでプロセスはプログラムであることに注意すべきである。　プログラムが実行しているとき、それは概ねタスクとも呼ばれる。　ほとんどのオペレーティング・システムにおいては、一つのタスクと一つのプログラムとの間には一対一の関係がある。　しかしながら、いくつかのオペレーティング・システムでは一つのプログラムを複数のタスクやスレッドに分割することを認めている。　このようなシステムはマルチ・スレッド化オペレーティング・システムと呼ばれている。　話を簡単にするために、以後スレッドとプロセスは置き換えて使える言葉として取り扱うものとする。
【０００４】
スケジューラとは、コンピュータ・システムの共有リソース（例えば、ＣＰＵ）の使用の調整をつかさどるソフトウェア・プログラムである。　　スケジューラはそれ（スケジューリング）を行う際に普通、ファーストイン・ファーストアウト（即ち、ＦＩＦＯ）、ラウンド・ロビン乃至はラストイン・ファーストアウト（ＬＩＦＯ）、プライオリティ（優先順位）・キュー、ツリー（木探索）などのアルゴリズム、あるいは複数のアルゴリズムの組み合わせ、といったアルゴリズムを用いている。　　基本的に、もし、あるコンピュータ・システムが３つのＣＰＵ（ＣＰＵ１、ＣＰＵ２、およびＣＰＵ３）を持っているなら、各々のＣＰＵは適宜、処理待ちキューあるいは実行キューを持つことになる。　もし、プロセスを実行キューに割当てるのに使われるアルゴリズムがラウンド・ロビン・アルゴリズムであり、かつ最後に作成されたプロセスがＣＰＵ２用のキューに割当てられたのだとしたら、次に作成されたプロセスはＣＰＵ３のキューに割当てられることになる。　その次に作成されたプロセスは、今度はＣＰＵ１用のキューに割当てられることになり、以下同様である。　　従って、スケジューラは各々のプロセスにコンピュータ・システムのリソースを公平に分配するように設計されている。
【０００５】
時として、システム管理者は、異なったプロセスは異なったリソースの配分を受け取ることを望む場合がある。　その場合、ワークロード・マネージャ（ＷＬＭ）がスケジューラと併せて使われる。　ＷＬＭは、プロセスがコンピュータ・システムのリソースを使うかもしれない時間の割合を表す数字を、各々のプロセスに対して割当てる。　あるプロセスがそのリソースを使う度に、その割当てられた数は減らされる。　このしくみにより、より低い数を割当てられたプロセスが、それにもかかわらずそのリソースを使うことを可能にしている。
【０００６】
ある場合には、この考え方はプロセスのクラスにも応用される。　１クラスのプロセスとは、この場合、ユーザーのある特定の集まりに属するプロセスの集まりといえる。　　従って、ちょうどプロセスに数字が割当てられるのと同じようにして、あるクラスのプロセスがリソースを使っている時、そのクラスに割振られる数字は減らされる。　この場合もやはり、このしくみは、より低い数字を割振られたクラスのプロセスがリソースを使用する機会を持つことを確実にするために利用される。
【０００７】
【発明が解決しようとする課題】
しかしながら、問題点は何かというと、時として、例えばそれぞれ異なった数字を割当てられた２つのクラスのプロセスを持った２頭プロセッサ・システムが、最終的には、一方のプロセッサが一方のクラスのプロセスをそのキューに持ち、その一方で他方のプロセッサは他方のクラスのプロセスをそのキューに持ってしまう可能性があることである。　　これが起るとき、そのコンピュータ・システムの２つのプロセッサは、それらが本当ならでき得る程度には、あるいはシステム管理者が意図しているほどは、効率的に利用されない可能性がある。　　特に、一方の実行キューにあるプロセスは、許容量以上の処理時間を割り与えられることになる。
【０００８】
従って、システム管理者が制定したプロセッサ使用ポリシーに従っていることを保証するために、システムの各々のキューが、それぞれに異なった数字を割当てられた数クラスのプロセスを常に混在して含むことを確実にできるシステム、装置、そして方法が必要となる。
【０００９】
【課題を解決するための手段】
本発明はシステム・タスク・スケジューラをワークロード・マネージャと統合させるための方法、システム、そして装置を提供するものである。　スケジューラはスレッドに初期値の優先順位を割当てそのスレッドを実行キューに配置するために用いられ、またワークロード・マネージャはシステム管理者が設定したポリシーを実行するために用いられる。　それらのポリシーの一つは、異なったクラスのスレッドにはシステムのＣＰＵタイムを異なった配分比率で与えることであることもある。　このポリシーは、もし複数のクラスからのスレッドができる限り均等に実行キューの中に広がれば、確実に達成することができる。
【００１０】
ある特定の実施例においては、スレッドはクラスごとに整理されており、各々のクラスは関連する一群のスレッドから構成されている。　各々のクラスには使用ポリシーに従って優先順位が付けられている。（クラス優先順位）　この優先順位は、クラス内の各スレッドに割当てられたスケジューリングの優先順位を修正するのに使われる。　クラス優先順位の値に従って、クラス、またそれ故そのクラス内の各スレッドは、複数ある優先順位のバンド（幅）あるいはレンジ（範囲）の一つに収まることもある。　本発明では、ある実行キューのあるバンドに属するスレッドの数が、別の実行キューのその（同じ）バンドに属するスレッドの数を規定の数以上上回っているかどうかを、定期的に判断している。　もしそう（上回っている）ならば、そのシステムは負荷不均衡であるとみなされる。　本発明では更に、そのバンドに属するひとつのスレッドをより多数のスレッドを持った実行キューから、より少数のスレッドを持った実行キューへ移動させることにより、負荷均衡化を図っている。　もし最も優先順位の高いバンドにおいてシステムが負荷均衡している場合は、本発明はそのシステムがその次に優先順位の高いバンドにおいて負荷均衡になっているかを調べようとし、以下同様に繰り返す。
【００１１】
【発明の実施の形態】
以下、図を参照して説明を行う。　　図１は本発明を実施することができるデータ処理システムのネットワークを図式で表したものである。　ネットワーク・データ処理システム１００は本発明を実施することができるコンピュータのネットワークである。　ネットワーク・データ処理システム１００はネットワーク１０２を含んでおり、これはネットワーク・データ処理システム１００内で相互に接続された各種デバイスと各種コンピュータとの間の通信リンクを提供するために使われる媒体である。　ネットワーク１０２には、ワイヤー、ワイヤレス通信リンク、あるいは光ファイバー・ケーブルといった接続（部分）が含まれることもある。
【００１２】
図示された例において、サーバー１０４はストレージ（記憶）・ユニット１０６とともにネットワーク１０２に繋がっている。　これに加え、クライアント１０８、１１０、および１１２がネットワーク１０２に繋がっている。　これらのクライアント１０８、１１０、および１１２は、例えばパーソナル・コンピュータでもよく、ネットワーク・コンピュータでもよい。　図示された例においては、サーバー１０４は、ブート・ファイル、オペレーティング・システム・イメージ、アプリケーションといったデータをクライアント１０８、１１０、および１１２に提供する。　クライアント１０８、１１０、および１１２はサーバー１０４に対するクライアントである。　　ネットワーク・データ処理システム１００は、図示されていない更なるサーバー、クライアント、およびその他のデバイスを含むこともある。　図示された例において、ネットワーク・データ処理システム１００は、お互いの通信にＴＣＰ／ＩＰプロトコル一式を使うネットワークおよびゲートウェイの世界中での集りを代表するネットワーク１０２を持ったインターネットである。　　インターネットの心臓部には、データやメッセージの経路を決める無数の商用、官庁、教育用、その他のコンピュータ・システムからなる主だったノードやホスト・コンピュータの間にまたがる高速データ通信線のバック・ボーン（基幹）が走っている。　　勿論、ネットワーク・データ処理システム１００は、例えばイントラネット、ローカル・エリア・ネットワーク（ＬＡＮ）、あるいはワイド・エリア・ネットワーク（ＷＡＮ）といった、いくつかの異なったタイプのネットワークとして実現することもある。　　図１は一例を表したもので、本発明をアーキテクチャー的に限定するものではない。
【００１３】
図２は、図１のサーバー１０４のようなサーバーとして実現可能なデータ処理システムのブロック図を、本発明の実施の形態に基いて表したものである。　　データ処理システム２００は、システム・バス２０６に繋がった複数のプロセッサ２０２および２０４を備えた対称型マルチプロセッサ（ＳＭＰ）であることもある。　反対にシングル・プロセッサ・システムが採用されることもある。　　また、システム・バス２０６にはメモリ・コントローラ／キャッシュ２０８も繋がっており、これはローカル・メモリ２０９に対するインターフェースを提供する。　　Ｉ／Ｏバス・ブリッジ２１０はシステム・バス２０６に繋がっており、Ｉ／Ｏバス２１２に対するインターフェースを提供する。　　メモリ・コントローラ／キャッシュ２０６と　Ｉ／Ｏバス・ブリッジ２１０は、図示されているように１つにすることもある。
【００１４】
Ｉ／Ｏバス２１２に繋がったペリフェラル・コンポーネント・インターコネクト（ＰＣＩ）バス・ブリッジ２１４は、ＰＣＩローカル・バス２１６に対するインターフェースを提供する。　いくつかのモデムをＰＣＩローカル・バス２１６に接続することもある。　典型的なＰＣＩバスの実装では、４つのＰＣＩ拡張用スロットないしは拡張用コネクタを備えている。　　図１のネットワーク・コンピュータ１０８、１１０、および１１２に対する通信リンクは、拡張ボードを介してＰＣＩローカル・バス２１６に接続されたモデム２１８およびネットワーク・アダプタ２２０を通して提供されることもある。
【００１５】
追加のＰＣＩバス・ブリッジ２２２および２２４は、追加のＰＣＩローカル・バス２２６および２２８のためのインターフェースを提供し、それにより追加のモデムやネットワーク・アダプタを扱うことが可能となる。　このように、データ処理システム２００は複数のネットワーク・コンピュータの接続を許可している。　メモリ・マップト（メモリ空間に配置された）・グラフィクス・アダプタ２３０およびハード・ディスク２３２もまた、図示したようにＩ／Ｏローカル・バス２１２に直接または間接に接続されることがある。
【００１６】
当該技術分野における通常の技術があれば、図２に示したハードウェアが異なっていても良いと十分理解できるであろう。　　例えば、光ディスク・デバイスなどといった他の周辺デバイスもまた、図示されたハードウェアに加えてあるいはそれに代えて使われる可能性がある。　図示された例は本発明に関するアーキテクチャ上の制限を暗示するものではない。
【００１７】
図２に示したデータ処理システムは、例えば、ニューヨーク州アーモンクにあるインターナショナル・ビジネス・マシーンズ（ＩＢＭ）コーポレーションの製品で、アドバンスト・インタラクティブ・エグゼクティブ（ＡＩＸ）オペレーティング・システムやＬＩＮＵＸオペレーティング・システムで動く、ＩＢＭ　ｅ−サーバー　ｐシリーズ・システムであったりする。
【００１８】
次に図３は、本発明が実施可能なデータ処理システムを表したブロック図を示している。　　データ処理システム３００はクライアント・コンピュータの一例である。　　データ処理システム３００はペリフェラル・コンポーネント・インターコネクト（ＰＣＩ）ローカル・バス・アーキテクチャを採用している。　　図示された例ではＰＣＩバスを採用しているが、アクセラレーテッド・グラフィクス・ポート（ＡＧＰ）やインダストリ・スタンダード・アーキテクチャ（ＩＳＡ）といった他のバス・アーキテクチャを採用してもよい。　　プロセッサ３０２およびメイン・メモリ３０４はＰＣＩブリッジ３０８を介してＰＣＩローカル・バス３０６に接続されている。　　ＰＣＩブリッジ３０８はまた、プロセッサ３０２用の統合メモリ・コントローラおよびキャッシュ・メモリをも含むことがある。　　ＰＣＩローカル・バス３０６への追加の接続は直接の部品の相互接続によってや拡張ボードを通して行われることもある。　図示の例では、ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ３１０、ＳＣＳＩホスト・バス・アダプタ３１２、および拡張バス・インターフェース３１４が、直接の部品接続でＰＣＩローカル・バスに接続されている。　　これと対照的に、オーディオ・アダプタ３１６、グラフィクス・アダプタ３１８、およびオーディオ／ビデオ・アダプタ３１９は、拡張用スロットに挿入された拡張ボードによってＰＣＩローカル・バス３０６に接続されている。　　拡張バス・インターフェース３１４はキーボード兼マウス・アダプタ３２０、モデム３２２、および追加のメモリ３２４のための接続を提供する。　　スモール・コンピュータ・システム・インターフェース（ＳＣＳＩ）ホスト・バス・アダプタ３１２はハード・ディスク・ドライブ３２６、テープ・ドライブ３２８、およびＣＤ−ＲＯＭドライブ３３０のための接続を提供する。　　典型的なＰＣＩローカル・バスの実装では３つないしは４つのＰＣＩ拡張用スロットあるいは拡張用コネクタを備えることになる。
【００１９】
オペレーティング・システムはプロセッサ３０２の上で動作し、図３中のデータ処理システム３００にある各種部品の制御を調整したり提供したりするのに用いられる。　そのオペレーティング・システムは、マイクロソフト・コーポレーションから入手可能なウインドウズ２０００といった市販のオペレーティング・システムであってもよい。　　Ｊａｖａなどのオブジェクト指向プログラミング・システムもオペレーティング・システムとともに動き、データ処理システム３００上で実行しているＪａｖａプログラムあるいはＪａｖａアプリケーションからオペレーティング・システムへのコールを提供している。
「Ｊａｖａ」はサン・マイクロシステムズＩｎｃ．の商標である。　　オペレーティング・システム、オブジェクト指向オペレーティング・システム、およびアプリケーションやプログラムのための命令は、ハード・ディスク・ドライブ３２６などの記憶デバイス上に位置しており、プロセッサ３０２によって実行するためにメイン・メモリ３０４にロードされることもある。
【００２０】
当該技術分野における通常の技術があれば、図３のハードウェアが具現化次第で変わる可能性があることを十分理解できる。　　フラッシュＲＯＭ（あるいは同等の不揮発性メモリ）や光ディスク・ドライブなどといった、その他の内部ハードウェアや周辺のデバイスが、図３に示したハードウェアに加えて、あるいはこれらに代えて、使われることがある。　　また、本発明の処理過程は、マルチプロセッサ・データ処理システムにも適用されることがある。
【００２１】
今一つの例として、データ処理システム３００は、データ処理システム３００が何らかのタイプのネットワーク通信インターフェースを構成しているにしろいないにしろ、何らかのタイプのネットワーク通信インターフェースに依存しないでもブートできるように構成されたスタンドアロン（単独稼動）・システムであることもある。　　更なる例として、データ処理システム３００はパーソナル・デジタル・アシスタント（ＰＤＡ）デバイスであり、オペレーティング・システムのファイルまたはユーザー作成データの保持のための不揮発性メモリを提供するためのＲＯＭまたはフラッシュＲＯＭで構成されるもの、であることもある。
【００２２】
図３に示す例および上記の例は、アーキテクチャ上の制限を暗示するものではない。　　例えば、データ処理システム３００は、ＰＤＡの形態をとることに加えて、ノートブック・コンピュータあるいはハンドヘルド・コンピュータであることもある。　　データ処理システム３００はまた、キオスクあるいはＷｅｂ端末であることもある。
【００２３】
本発明は、マルチプロセッサ・システムの各々の実行キューが異なったクラスのスレッドに属するプロセスを含むことを確認し、各々のクラスは異なった優先順位の数字を持っており、これにより制定された使用ポリシーに準拠することを確認する装置、システム、そして方法を提供するものである。　本発明は図１のクライアント・システム１０８、１１０、および１１２に、あるいはサーバー１０４に、あるいはサーバー１０４とクライアント１０８、１１０、および１１２の両方に、限定したのであってもよい。　　それ故、本発明はコンピュータ・システムで使われるいかなる記憶デバイス（即ち、フロッピ・ディスク、コンパクト・ディスク、ハード・ディスク、ＲＯＭ、ＲＡＭ、など）上にでも存在する可能性がある。
【００２４】
図４および図５はは、システム管理者が考案することがあるリソース使用ポリシーを説明したものである。　　図４に示したように、そのリソース使用ポリシーはある大学の３つの学科（即ち、物理学、化学、および数学）で共有されるべきコンピュータ・システム（例えば、サーバー）のために開発されている。　　そのポリシーによれば、物理学科４００のユーザー４０２はそのコンピュータ・システムのＣＰＵ時間の６０％を与えられるべきで、化学科４１０のユーザー４１２はそのコンピュータ・システムのＣＰＵ時間の３０％を与えられるべきで、そして数学科のユーザー４２２は１０％を与えられるべきである。　　各々のグループのスレッドを他から区別するために、それらはクラスとして識別子を付されている。　　具体的には、　物理学科のユーザーに属するスレッドはクラスＡにあるとして識別子を付され、化学科のユーザーに属するものはクラスＢ、そして数学科のユーザーに属するもの（スレッド）はクラスＣとなっている。
【００２５】
リソース使用ポリシーの一つの付属物としてバンド分散ポリシーがある。　この分散ポリシーは図５に示されている。　この図にはバンド１とバンド２の２つのバンドが表示されている。　　この分散ポリシーでは０から１４の優先順位を持つすべてのクラスをバンド１に属するものとして、そして優先順位が１５から３０の範囲に収まるすべてのクラスをバンド２に属するものとして、分類している。従って、新たに作られたスレッドで、物理学科か化学科のいずれかからのユーザーに属するものはバンド２に収まることになるのに反して、数学科からのユーザーに属するものはバンド１に収まることになる。
【００２６】
従来技術にあるように、作成された各々のスレッドは初期値の優先順位を持っている。　この初期値の優先順位はすべてのスレッドに対して同じである。　　しかしながら、スレッドが実行キューに置かれるとき、その優先順位はそのクラスに応じて調整される。　例えば、クラスＡスレッドの初期値の優先順位に対して３０が加えられることになる。　　同様に、クラスＢスレッドの初期値の優先順位に対しては２０が加えられ、クラスＣスレッドの初期値の優先順位に対しては１０が加えられることになる。　従って、ある実行キューのあるスレッドに対する総合優先順位は　Ｐ_{Ｔｏｔａｌ}　＝　Ｐ_{Ｄｅｆａｕｌｔ}　＋　Ｐ_{Ｃｌａｓｓ}　となる。
【００２７】
図６はクラス優先順位が実行キュー内のスレッドにどのように影響を与えるかを表している。　図６では、プロセッサの優先順位空間５００が優先順位の数字、０、１０、２０、および３０で分割されている。　　あるクラスＡスレッド５２０、クラスＢスレッド５４０、およびクラスＣスレッド５６０もまた表示されている。　　スレッドのＰ_{Ｄｅｆａｕｌｔ}に値ゼロ（０）が与えられている。　　従って、すべてのスレッドはゼロ（０）という同じ優先順位レベルからスタートすることになる。　　値３０の優先順位差分ΔＡ　５３０がクラスＡスレッドに加えられ、値２０の優先順位差分ΔＢ　５５０がクラスＢスレッドに加えられ、そして値１０の優先順位差分ΔＡ　５３０がクラスＣスレッドに加えられる。　　従って、プロセッサはクラスＢスレッドよりもクラスＡスレッドを好むことになる。　　同様に、プロセッサはクラスＣスレッドよりもクラスＢスレッドを好むことになる。
【００２８】
従来の技術においては、あるスレッドが処理されるに従い、その優先順位もまた下げられる。　　この仕組みは実行キューにあるすべてのスレッドが、プロセッサの注意をひくために公平に競争するのを可能にするものである。　　これと同じ仕組みが本発明においても使用されている。　　即ち、あるスレッドが処理されるに従い、そのＰ_{Ｄｅｆａｕｌｔ}値が減らされる。　　このことは１つのクラスの範囲内のスレッドがお互いに公平に競争するのを可能にするものである。　加えて、あるクラスのスレッドが処理されていくに従い、クラス優先度も同様に下げられる。　　例えば、クラスＡスレッドはクラスＢスレッドやクラスＣスレッドよりも高いクラス優先順位を持っているので、クラスＡスレッドが他の２つより先に処理されることになる。　しかし、そのクラスＡスレッドが処理されていくにつれ、値３０のクラスＡ優先順位は、その値が２０以下に達するまで下げられることになる。　　その時点で、クラスＡとクラスＢの両スレッドが処理されることになる。　　両クラスの優先順位はその値が１０以下になるまで下げられることになり、その時点ですべての３つのクラスのスレッドが処理されることになる。
【００２９】
クラス優先順位が下げられるに従い、そのクラスがあるバンドから他へ移行することもある。　　従って、クラス優先順位は非常に変化しやすいものとみなすことができる。　　優先順位はそのクラスのスレッドが処理されていくと減少し、使用ポリシーに規定されているほど長く処理されないでいると増加する。
【００３０】
図７および図８は、ある共有型コンピュータ・システムの実行キューを示している。　　そのコンピュータ・システムは２つのＣＰＵと２つの実行キューを持ち、各実行キューはいずれかのＣＰＵ（即ち、ＣＰＵ０　６００およびＣＰＵ１　６５０）専用に用いられるものと仮定する。　　また、各々のクラスの優先順位の差分が既にスレッドに加えられているものとも仮定する。　　本システムには３つのクラスのスレッドが表されている。　　具体的には、ＣＰＵ０　６００用の実行キューはクラスＡ　６１０とクラスＢ　６２０の両方からのスレッドを含んでいる。　ＣＰＵ１用の実行キューは　クラスＣ　６３０からのスレッドを含んでいる。
【００３１】
動作中、あるスレッドが作成されたとき、ワークロード・マネージャはその（スレッドが）属するユーザーに基づいてそのスレッドのクラスを決定し、スケジューラはある配置アルゴリズム（例えば、ラウンド・ロビン）を用いてそのスレッドをある実行キューに配置する。　　スレッドが実行キューから取り出されて処理され、そして新しいスレッドがその実行キューに配置されていくに従い、図７および図８に示すようにスレッドがシステム内に分散される場合があることもある。
【００３２】
図７および図８のスレッドの分散は、システム管理者によって設定された使用ポリシー（図４参照）を遵守しないことになるので、理想的なものとは言えない。例えば、クラスＣスレッドがＣＰＵ１　６５０用の実行キューにある唯一のスレッドであるので、それらはシステムの処理時間の５０％を割り与えられることになる。　　明らかに、これはそれら（のスレッド）が割り与えられることを許された１０％よりはるかに上である。　　それら（のスレッド）が許されている以上のいかなる処理時間をも割り与えられないように保証する１つの方法は、その実行キューに別のクラスのスレッドを持つことである。　そしてこのことは、２つのクラスのスレッドの間での競争を促すことになる。　　真に理想的なスレッドの分散は各々の実行キューがすべての３つの異なったクラスからのスレッドを含んでいることである。
【００３３】
制定された使用ポリシーに従うことを保証する１つの方法は、少なくとも２つの異なったクラス（即ち、高位および低位の優先順位クラス）のスレッドがその（実行キューの）なかにあるかを判断するために定期的に各キューを調べることである。　　もしそうで無い（２つのクラスが無い）ならば、現在あるものより高位の優先順位クラスを持った別のクラスのスレッドがその実行キューの中に配置されるべきである。　　更に、もしも、その実行キューの中に２つの異なったクラスのスレッドを持っているにもかかわらず、そのいずれかあるいは両方のクラスのスレッドが依然として許容される以上の処理時間を割り与えられ続けている場合は、更に高いクラスの優先順位を持った別のクラスからのスレッドがその実行キューに配置される必要がある。
【００３４】
実行キューのそれぞれが少なくとも２つの異なったクラスのスレッドを含んでいるかどうかを判断するために実行キューにあるすべてのスレッドを調べることは、時間がかかりＣＰＵの集中を必要とするものである。　　それ故、本発明は、スレッドが実行キューに渡ってうまく分散されているかどうかを見るために、スレッドのある部分を０．１秒毎に調べている。　　本発明は、スレッドのどの部分を詳しく調べるべきかを判断するために、先に紹介したバンドの概念（図５参照）を利用している。　　具体的には、本発明では、各々の実行キューのある特定のバンドにそれぞれ等しい数のスレッドを含んでいるシステムのことをよく均衡したシステムと定義している。　もしも、２つのプロセッサ（図８参照）の各々がその実行キューに２つのクラスＡスレッド、２つのクラスＢスレッド、および２つのクラスＣスレッドを持っている場合は、そのシステムは均衡することになる。　　両方の実行キューにおいて、４つのスレッドがバンド２に、そして２つのスレッドがバンド１にあることになるので、そのシステムは均衡することになるのである。
【００３５】
もし、システムが均衡していない場合は（即ち、もし一方の実行キューが他方の実行キューよりある特定のバンドにスレッドを多く持っている場合は）、そのバンド内でより多数のスレッドを持った実効キューからより少数のスレッドを持った実効キューへスレッドが移動することになる。　　ここで、システムは非常にダイナミック（活動的）であることに注意すべきである。　　即ち、いかなる時間にあっても、１つあるいはいくつかのクラスがあるバンドから他のバンドへ移っているかもしれない間に、１つあるいはそれ以上のスレッドが実行キューから取り出されて処理されているかもしれないし、その間にもあるスレッドがある実行キューに配置されているところかもしれない。　　従って、このダイナミズム（活動性）のおかげで、本発明は一時に１つのバンドしか取り扱わないし、システムが均衡していない時はただ１つのスレッドのみがある実行キューから他へ移動される。
【００３６】
図７に戻ると、本発明がバンド２を調べる時、８つのスレッドをそのバンドに見つけることになるが、それらのすべてはＣＰＵ０　６００用の実行キューの中にある。　　それ故、システムは不均衡であると判断されることになる。　　その結果、１つのスレッドがＣＰＵ０用の実行キューからＣＰＵ１用の実行キューに移動されることになり、その処理は終わる。
【００３７】
この場合、移動されたスレッドがクラスＡスレッドかクラスＢスレッドであるかは、両クラスともバンド２にあるので、大した問題ではない。　　もしもシステムが均衡していて、その処理の中ですべてのクラスＢスレッドがＣＰＵ０用の実行キューからＣＰＵ１用のものへと移動されているのであれば、クラスＢスレッドはより多くの処理時間を割り与えられ始めていることであろう。　（なぜなら、それらの（スレッドの）クラス優先順位はクラスＣスレッドより高いので。）　　それが起こるとき、それらのクラス優先順位は下げられることになる。　　もし今、それらのクラス優先順位がバンド１に収まるところまで十分に下げられる場合は、システムは再び不均衡になることになる。　　その時、クラスＡスレッドが、システムを再度均衡させるために、ある実行キューから別のものへと移動されることになる。
【００３８】
バンド２を均衡させた後、バンド１が綿密に調べられることになる。　　この場合、すべてのクラスＣスレッド（クラスＣはバンド１の唯一のクラスであることに注意）はＣＰＵ１用の実行キューにあるので、システムは不均衡であるとわかることになる。　　その結果、両方の実行キューが同数のクラスＣスレッドを含むまで、クラスＣスレッドは１つずつ移動されることになる。
【００３９】
我々の例では、理想的なスレッドの分散とは図８に示されたものである。　　図８において、各々の実行キューは各クラスで同数のスレッドを含んでいる。　　従って、スレッドが実行キューに配置されもせず、また実行キューから取り出して処理されもしないと仮定するならば、システムは常に均衡したままとなる。　　もし、あるクラスがあるバンドから他へ移動するなら、そのクラスに属するすべてのスレッドがそれに伴う移動をすることになる。　　それ故そのシステムは均衡されたままを維持することになる。
【００４０】
図９は本発明を実施するのに使われる可能性があるソフトウェア・プログラムのフロー・チャートである。　　そのソフトウェア・プログラムはコンピュータ・システムの電源が入れられた時あるいはリセットされた時にスタートする。　　（ステップ７００）　　プログラムは各々の実行キュー内の各々のクラスのスレッドの数を監視している。　　プログラムは各々の実行キュー内の各々のクラスのスレッドの平均数をつかむために、１秒間に何回か実行キュー１００を無作為選択することで、それ（監視）を行う。　　そしてその処理過程で、一方の実行キューの最高位バンド（例えば、バンド２）に属するスレッドの数が平均としてもう一方の実行キューの同じバンド（例えば、バンド２）に属するスレッドの数より平均として１．５スレッド以上上回っているかどうかを判断するために、０．１秒毎にスレッドのクラスが利用される。　もしそう（上回っている）なら、システムは不均衡であるとみなされる。　　プロセスは、そのバンドで最大のスレッド数を持った実行キューから最小のスレッド数を持った実行キューへ１つのスレッドを移動させることによって、システムが均衡するよう試みようとする。
【００４１】
先に延べたように、システムが非常にダイナミックであるので、プロセスはシステムが本当に均衡しているか保証しようとはしない。（即ち、プロセスは、各々の実行キューのそのバンドに同数のスレッドが本当に存在しているかを確認しようとはしない。）　　更に、全バンドの観点からシステムが均衡しているということを保証することは時間がかかりＣＰＵの集中を必要とするので、本処理はそこで終了することになる。
【００４２】
従って、プロセスは常に最高位のバンドから始まる。　　もしも最高位のバンドが均衡していない場合は、本処理はバンドを均衡させようと試みようとし、そこで終了する。　　もし最高位のバンドが均衡している場合は、次に本処理はその次に高位のバンドを調べようとする。　　ある実行キューにあるスレッドの数が、別の実行キューのスレッドの数よりも１．５スレッド以上多い場合に行き当たるまで、最高位から始まって最低位に向って各々のバンドが調査されることになる。　　それに行き当たった時、最大数のスレッドを持った実行キューから最小数のスレッドを持った実行キューに、１つのスレッドが移動され、本処理は終了することになる。　もし、すべての実行キューのすべてのバンドにおけるスレッドの数が同数である場合には、いかなるスレッドをもあるキューから他へ移動させること無く本処理は終了することになる。（ステップ７００〜７１４）
【図面の簡単な説明】
【図１】本発明に基づく分散データ処理システムを表す模範的なブロック図である。
【図２】本発明に基づくサーバー装置の模範的なブロック図である。
【図３】本発明に基づくクライアント装置の模範的なブロック図である。
【図４】システム管理者によって考案されることがあるリソース使用ポリシーを表したものである。
【図５】システム管理者によって考案されることがあるリソース使用ポリシーを表したものである。
【図６】いかにしてクラス優先順位が実行キューのスレッドに影響を与えるかを表したものである。
【図７】３つの異なったグループのユーザーによって共有されたコンピュータ・システムの実行キューを表したものである。
【図８】３つの異なったグループのユーザーによって共有されたコンピュータ・システムの実行キューを表したものである。
【図９】本発明を実施するために使われる可能性があるソフトウェア・プログラムのフロー・チャートである。
【符号の説明】
１００　…　　ネットワーク・データ処理システム、
１０２　…　ネットワーク、
１０４　…　サーバー、
１０６　…　ストレージ・ユニット、
１０８　…　クライアント、
１１０　…　クライアント、
１１２　…　クライアント、
２００　…　データ処理システム、
２０２　…　プロセッサ、
２０４　…　プロセッサ、
２０６　…　システム・バス、
２０８　…　メモリ・コントローラ／キャッシュ、
２０９　…　ローカル・メモリ、
２１０　…　Ｉ／Ｏバス・ブリッジ、
２１２　…　Ｉ／Ｏバス、
２１４　…　ペリフェラル・コンポーネント・インターコネクト（ＰＣＩ）バス・ブリッジ、
２１６　…　ＰＣＩローカル・バス、
２１８　…　モデム、
２２０　…　ネットワーク・アダプタ、
２２２　…　ＰＣＩバス・ブリッジ、
２２４　…　ＰＣＩバス・ブリッジ、
２２６　…　ＰＣＩローカル・バス、
２２８　…　ＰＣＩローカル・バス、
２３０　…　グラフィクス・アダプタ、
２３２　…　ハード・ディスク、
３００　…　データ処理システム、
３０２　…　プロセッサ、
３０４　…　メイン・メモリ、
３０６　…　ＰＣＩローカル・バス、
３０８　…　ＰＣＩブリッジ、
３１０　…　ローカル・エリア・ネットワーク（ＬＡＮ）アダプタ、
３１２　…　ＳＣＳＩホスト・バス・アダプタ、
３１４　…　拡張バス・インターフェース、
３１６　…　オーディオ・アダプタ、
３１８　…　グラフィクス・アダプタ、
３１９　…　オーディオ／ビデオ・アダプタ、
３２０　…　キーボード兼マウス・アダプター、
３２２　…　モデム、
３２４　…　メモリ、
３２６　…　ハード・ディスク・ドライブ、
３２８　…　テープ・ドライブ、
３３０　…　ＣＤ−ＲＯＭドライブ、
４００　…　物理学科、
４０２　…　ユーザー、
４１０　…　化学科、
４１２　…　ユーザー、
４２０　…　数学科、
４２２　…　ユーザー、
５００　…　優先順位空間、
５２０　…　クラスＡスレッド、
５３０　…　優先順位差分ΔＡ　、
５４０　…　クラスＢスレッド、
５５０　…　優先順位差分ΔＢ、
５６０　…　クラスＣスレッド、
５７０　…　優先順位差分ΔＣ、
６００　…　ＣＰＵ０、
６１０　…　クラスＡ、
６２０　…　クラスＢ、
６３０　…　クラスＣ、
６５０　…　ＣＰＵ１、
７００　…　ステップ（スタート）、
７０２　…　ステップ（処理）、
７０４　…　ステップ（処理）、
７０６　…　ステップ（条件分岐）、
７０８　…　ステップ（処理）、
７１０　…　ステップ（条件分岐）、
７１２　…　ステップ（終了）、
７１４　…　ステップ（処理）

Claims (28)

1. マルチ・プロセッサ・システムの負荷均衡をとる方法であって、前記システムは複数のプロセッサ実行キューを備えており、各々の実行キューは処理すべきスレッドを保持するためのものであって、
   作成された各々のスレッドに優先順位を割当てて当該作成されたスレッドをある実行キューに配置するステップであって、当該割当てられた優先順位が当該スレッドをあるバンド（群）に分類するステップと、
   当該システムが負荷不均衡かどうかを判断するステップであって、もしある実行キューのあるバンドへ別の実行キューのそれと同じバンドにあるのよりも多くのスレッドが分類されているなら当該システムは負荷不均衡とするステップと、もし当該システムが負荷不均衡である場合には、当該バンドに属する、数の多いスレッドを持った方の実行キューから、当該バンドに属する、数の少ないスレッドを持った方の実行キューへとスレッドを移動することにより、当該システムの負荷均衡をとるステップと、
   を有する、マルチ・プロセッサ・システムの負荷均衡をとる方法。
2. 各々の実行キューのスレッドがクラス毎に整理されている、請求項１記載の方法。
3. あるスレッドが、それが帰属するマルチ・プロセッサ・システムのユーザーに基づいたあるクラスに属している、請求項２記載の方法。
4. 当該割当てられた優先順位が、当該スレッドが属するクラスの優先順位である、請求項３記載の方法。
5. あるクラスのスレッドが処理されるに従いそのクラス優先順位が下がり、クラスのスレッドが許され得る限り処理されないでいるとそのクラス優先順位が上がる、請求項４記載の方法。
6. クラス優先順位が下がったり上がったりするのに従い、あるスレッドが別のバンドに再分類され得る、請求項５記載の方法。
7. もしもある実行キューのあるバンドに属するスレッドの数が、別のキューの同じバンドに属するスレッドの数を規定の数以上上回っているならば、そのシステムは負荷不均衡とする、請求項６記載の方法。
8. マルチ・プロセッサ・システムの負荷均衡をとるための、コンピュータ可読媒体上のコンピュータ・プログラム記録媒体であって、前記システムは複数のプロセッサ実行キューを備え、各々の実行キューは処理すべきスレッドを保持しており、
   作成された各々のスレッドに優先順位を割当てて当該作成されたスレッドを実行キューに配置するためのコード手段であって、当該割当てられた優先順位が当該スレッドをあるバンドに分類するコード手段と、
   当該システムが負荷不均衡かどうかを判断するためのコード手段であって、もしある実行キューのあるバンドへ別の実行キューのそれと同じバンドにあるのよりも多くのスレッドが分類されているなら当該システムは負荷不均衡とするコード手段と、
   もしそのシステムが負荷不均衡ならば、当該バンドに属する、数の多いスレッドを持った方の実行キューから、当該バンドに属する、数の少ないスレッドを持った方の実行キューへとスレッドを移動することにより、当該システムの負荷均衡をとるためのコード手段と、
   を有するコンピュータ・プログラム記録媒体。
9. 各々のキューにおけるスレッドがクラス毎に整理されている、請求項８記載のコンピュータ・プログラム記録媒体。
10. あるスレッドが、それが帰属するマルチ・プロセッサ・システムのユーザーに基づいたあるクラスに属している、請求項９記載のコンピュータ・プログラム記録媒体。
11. 当該割当てられた優先順位が、当該スレッドが属するクラスの優先順位である、請求項１０記載のコンピュータ・プログラム記録媒体。
12. あるクラスのスレッドが処理されるに従いそのクラス優先順位が下がり、クラスのスレッドが許され得る限り処理されないでいるとそのクラス優先順位が上がる、請求項１１記載のコンピュータ・プログラム記録媒体。
13. クラス優先順位が下がったり上がったりするのに従い、あるスレッドが別のバンドに再分類され得る、請求項１２記載のコンピュータ・プログラム記録媒体。
14. もしもある実行キューのあるバンドにおけるスレッドの数が、別のキューの同じバンドにおけるスレッドの数を規定の数以上上回っているならば、そのシステムは負荷不均衡とする、請求項１３記載のコンピュータ・プログラム記録媒体。
15. マルチ・プロセッサ・システムの負荷均衡をとるための装置であって、前記システムは複数のプロセッサ実行キューを備えており、各々の実行キューは処理すべきスレッドを保持するためのものであって、
    作成された各々のスレッドに優先順位を割当てて当該作成されたスレッドを実行キューに配置するための手段であって、当該割当てられた優先順位が当該スレッドをあるバンド（群）に分類する手段と、
    当該システムが負荷不均衡かどうかを判断する手段であって、もしある実行キューのあるバンドへ別の実行キューのそれと同じバンドにあるのよりも多くのスレッドが分類されているならば当該システムは負荷不均衡とする手段と、
    もし当該システムが負荷不均衡である場合には、当該バンドに属する、数の多いスレッドを持った方の実行キューから、当該バンドに属する、数の少ないスレッドを持った方の実行キューへとスレッドを移動することにより、当該システムの負荷均衡をとる手段と、
    を有する、マルチ・プロセッサ・システムの負荷均衡をとるための装置。
16. 各々の実行キューのスレッドがクラス毎に整理されており、かつスレッドに割当てられた優先順位はクラス優先順位である、請求項１５記載の装置。
17. あるスレッドが、それが帰属するマルチ・プロセッサ・システムのユーザーに基づいたあるクラスに属している、請求項１６記載の装置。
18. 当該割当てられた優先順位が、当該スレッドが属するクラスの優先順位である、請求項１７記載の装置。
19. あるクラスのスレッドが処理されるに従いそのクラス優先順位が下がり、クラスのスレッドが許され得る限り処理されないでいるとそのクラス優先順位が上がる、請求項１８記載の装置。
20. クラス優先順位が下がったり上がったりするのに従い、あるスレッドが別のバンドに再分類され得る、請求項１９記載の装置。
21. もしもある実行キューのあるバンドに属するスレッドの数が、別のキューの同じバンドにおけるスレッドの数を規定の数以上上回っているならば、そのシステムは負荷不均衡とする、請求項２０記載の装置。
22. 自己負荷均衡をとり得るマルチ・プロセッサ・システムであって、前記システムは複数のプロセッサ実行キューを備えており、各々の実行キューは処理すべきスレッドを保持するためのものであって、
    コード・データを記憶するための少なくとも１つのストレージ（記憶）・システムと、
    作成された各々のスレッドに優先順位を割当てて当該作成されたスレッドを実行キューに配置するようにコード・データを処理する少なくとも一つのプロセッサとを有し、
    当該割当てられた優先順位は当該スレッドをあるバンド（群）に分類し、
    当該システムが負荷不均衡かどうかを判断し、もしある実行キューのあるバンドへ別の実行キューのそれと同じバンドにあるのよりも多くのスレッドが分類されているのであれば当該システムは負荷不均衡とし、
    もし当該システムが負荷不均衡であるならば、当該バンドに属する数の多いスレッドを持った方の実行キューから当該バンドに属する数の少ないスレッドを持った方の実行キューへとスレッドを移動することにより、当該システムの負荷均衡をとる、
    マルチ・プロセッサ・システム。
23. 各々の実行キューのスレッドがクラス毎に整理されている、請求項２２記載のマルチ・プロセッサ・システム。
24. あるスレッドが、それが帰属するマルチ・プロセッサ・システムのユーザーに基づくあるクラスに属している、請求項２３記載のマルチ・プロセッサ・システム。
25. 当該割当てられた優先順位が、当該スレッドが属するクラスの優先順位である、請求項２４記載のマルチ・プロセッサ・システム。
26. あるクラスのスレッドが処理されるに従いそのクラス優先順位が下がり、クラスのスレッドが許され得る限り処理されないでいるとそのクラス優先順位が上がる、請求項２５記載のマルチ・プロセッサ・システム。
27. クラス優先順位が下がったり上がったりするのに従い、あるスレッドが別のバンドに再分類され得る、請求項２６記載のマルチ・プロセッサ・システム。
28. もしもある実行キューのあるバンドにおけるスレッドの数が、別のキューの同じバンドにおけるスレッドの数を規定の数以上上回っているならば、当該システムは負荷不均衡とする、請求項２７記載のマルチ・プロセッサ・システム。

Images