(57)【特許請求の範囲】
【請求項１】
タスク分散プロセスにより新しいタスクを割り当てるためにマルチプロセッサ・アーキテクチャ内のプロセッサに関連付けられたワークキューを選択するための方法であって、当該方法を実行するシステムが、複数のプロセッサと、前記複数のプロセッサと通信可能に結合された共有ランダム・アクセス・メモリとを備えており、前記複数のプロセッサは、前記タスク分散プロセスを実行しているプロセッサであるローカル・プロセッサと、前記ローカル・プロセッサ以外のプロセッサであるリモート・プロセッサとを含み、前記共有ランダム・アクセス・メモリが複数のワークキューと、当該複数のワークキューそれぞれに関連付けられたキュー可用性フラグを格納し、前記キュー可用性フラグは前記タスク分散プロセスを実行している特定のローカル・プロセッサについてのキュー可用性フラグであるローカル・キュー可用性フラグと前記タスク分散プロセスを実行している特定のローカル・プロセッサ以外のプロセッサについてのキュー可用性フラグであるリモート・キュー可用性フラグとを含み、前記ローカル・キュー可用性フラグは当該ローカル・キュー可用性フラグに関連付けられたワークキューの新しいタスクを受け入れるための可用性を示し、前記リモート・キュー可用性フラグは当該リモート・キュー可用性フラグに関連付けられたワークキューの新しいタスクを受け入れるための可用性を示し、
前記方法は、前記システムが、
前記複数のキュー可用性フラグの少なくとも１つのフラグに基づいて、前記複数のプロセッサのうちから新しいタスクを受け入れるために選択されたプロセッサに関連付けられたワークキューの可用性を前記ローカル・プロセッサ上で判断するステップと、
前記可用性を判断することに応答して、前記新しいタスクを、前記可用性が判断されたワークキューに割り当てるステップと、
前記選択されたプロセッサが前記ローカル・プロセッサであるかを判断するステップと、
前記選択されたプロセッサが前記ローカル・プロセッサでないことに応答して、前記選択されたプロセッサに関連付けられた前記ワークキューのサイズが新しいタスクを受け入れるためのワークキューが利用不能であるかを判断するための上限比較値よりも大きいことに基づいて、前記可用性が判断されたワークキューに関連付けられたキュー可用性フラグ中のリモート・キュー可用性フラグを当該リモート・キュー可用性フラグに関連付けられたワークキューが利用不能であることを示すように更新するステップと、
前記選択されたプロセッサが前記ローカル・プロセッサであることに応答して、前記可用性が判断されたワークキューに関連付けられたキュー可用性フラグ中のローカル・キュー可用性フラグを更新しないステップと
を実行することを含む、前記方法。
【請求項２】
前記システムが、
前記複数のプロセッサそれぞれに関連付けられたワークキュー内の優先順位が異なるワークキューごとに別個の平均キュー・サイズを計算することによって、複合キュー・サイズを、一定の時間間隔又は変動する時間間隔で繰り返し求めるステップであって、前記複数のワークキューは全てが１つのタイプのものである、前記求めるステップ
を実行することをさらに含み、
前記リモート・キュー可用性フラグを更新するステップが、
前記複合キュー・サイズに基づいて、前記リモート・キュー可用性フラグが利用可能から利用不能にすべきかどうかを判断するための上限比較値を導き出すステップと、
前記選択されたプロセッサに関連付けられたワークキューのサイズを前記上限比較値と比較するステップと、
前記ワークキューのサイズが前記上限比較値よりも大きいことに応答して、前記リモート・キュー可用性フラグを、新しいタスクを受け入れるのに前記選択されたプロセッサに関連付けられた前記ワークキューが利用不能であることを示すように更新するステップと
をさらに含む、請求項１に記載の方法。
【請求項３】
前記ローカル・キュー可用性フラグ及び前記リモート・キュー可用性フラグが、前記共有ランダム・アクセス・メモリ内の別のキャッシュ・ラインに格納される、請求項１又は２に記載の方法。
【請求項４】
前記可用性を判断するステップは、
前記選択されたプロセッサが前記ローカル・プロセッサであるかを判断するステップと、
前記選択されたプロセッサが前記ローカル・プロセッサでないことに応答して、前記選択されたプロセッサに関連付けられた前記リモート・キュー可用性フラグを検査するステップと、
前記選択されたプロセッサは前記ローカル・プロセッサであることに応答して、前記選択されたプロセッサに関連付けられた前記ローカル・キュー可用性フラグを検査するステップと
を含む、請求項１に記載の方法。
【請求項５】
前記システムが、
前記ローカル・プロセッサによって、前記ローカル・プロセッサに関連付けられた前記ワークキューから実行すべきタスクを受け入れるステップと、
前記実行すべきタスクを受け入れることに応答して、前記ローカル・プロセッサに関連付けられた前記ワークキューのサイズに基づいて、前記リモート・キュー可用性フラグを更新するステップと、
前記実行すべきタスクを受け入れることに応答して、前記ローカル・キュー可用性フラグを更新しないステップと
を実行することをさらに含む、請求項４に記載の方法。
【請求項６】
前記システムが、
請求項１に記載の各ステップの繰り返し実行時、前記ローカル・プロセッサに関連付けられた前記ワークキューのサイズに基づいて、前記ローカル・キュー可用性フラグを、新しいタスクを受け入れるのに前記ローカル・プロセッサに関連付けられた前記ワークキューが利用不能であることを示すように更新するステップであって、前記ローカル・キュー可用性フラグを更新するステップは、前記タスクの受け入れとは関係のない時点で行なわれる、前記更新するステップ
を実行することを含み、請求項４に記載の方法。
【請求項７】
前記システムが、
前記ローカル・キュー可用性フラグを更新することとは関係のない時点で、前記マルチプロセッサ・アーキテクチャ内のそれぞれの複数のプロセッサそれぞれに関連付けられたワークキュー内の優先順位が異なるワークキューごとに別個の平均キュー・サイズを計算することによって、複合キュー・サイズを求めるステップであって、前記複数のワークキューは全てが１つのタイプのものである、前記複合キュー・サイズを求めるステップ
を実行することをさらに含み、
前記ローカル・キュー可用性フラグを更新するステップが、
前記複合キュー・サイズに基づいて、前記ローカル・キュー可用性フラグが利用可能から利用不能にすべきかどうかを判断するための上限比較値を導き出すステップと、
前記選択されたプロセッサに関連付けられたワークキューのサイズを前記上限比較値と比較するステップと、
前記ワークキューのサイズが前記上限比較値より大きいことに応答して、前記ローカル・キュー可用性フラグを、新しいタスクを受け入れるのに前記ローカル・プロセッサに関連付けられた前記ワークキューが利用不能であることを示すように更新するステップと
をさらに含む、請求項６に記載の方法。
【請求項８】
前記ローカル・キュー可用性フラグを更新するステップは、ランダムな時間間隔で実行される、請求項６に記載の方法。
【請求項９】
前記システムが、
前記マルチプロセッサ・アーキテクチャ内の全てのプロセッサそれぞれに関連付けられたワークキュー内の優先順位が異なるワークキューごとに別個の平均キュー・サイズを計算することによって、複合キュー・サイズを、第１の時間間隔で繰り返し求めるステップであって、前記複数のワークキューは全て１つのタイプのものである、前記繰り返し求めるステップ
を実行することをさらに含み、
前記ローカル・キュー可用性フラグを更新するステップが、前記第１の時間間隔とは無関係の第２の時間間隔で、
前記複合キュー・サイズに基づいて、前記ローカル・キュー可用性フラグが利用可能から利用不能にすべきかどうかを判断するための上限比較値を導き出すステップと、
前記選択されたプロセッサに関連付けられたワークキューのサイズを前記上限比較値と比較するステップと、
前記ワークキューのサイズが前記上限比較値より大きいことに応答して、前記ローカル・キュー可用性フラグを、新しいタスクを受け入れるのに前記ローカル・プロセッサに関連付けられた前記ワークキューが利用不能であることを示すように更新するステップと
をさらに含む、
請求項６に記載の方法。
【請求項１０】
前記第１の時間間隔及び前記第２の時間間隔の少なくとも一方は、ランダムな時間間隔を含む、請求項９に記載の方法。
【請求項１１】
タスク分散プロセスにより新しいタスクを割り当てるためにマルチプロセッサ・アーキテクチャ内のプロセッサに関連付けられたワークキューを選択するためのシステムであって、
複数のプロセッサであって、前記複数のプロセッサは、前記タスク分散プロセスを実行しているプロセッサであるローカル・プロセッサと、前記ローカル・プロセッサ以外のプロセッサであるリモート・プロセッサとを含む、前記複数のプロセッサと、
前記複数のプロセッサと通信可能に結合された共有ランダム・アクセス・メモリであって、前記共有ランダム・アクセス・メモリが複数のワークキューと、当該複数のワークキューそれぞれに関連付けられたキュー可用性フラグを格納し、前記キュー可用性フラグは前記タスク分散プロセスを実行している特定のローカル・プロセッサについてのキュー可用性フラグであるローカル・キュー可用性フラグと前記タスク分散プロセスを実行している特定のローカル・プロセッサ以外のプロセッサについてのキュー可用性フラグであるリモート・キュー可用性フラグとを含み、前記ローカル・キュー可用性フラグは当該ローカル・キュー可用性フラグに関連付けられたワークキューの新しいタスクを受け入れるための可用性を示し、前記リモート・キュー可用性フラグは当該リモート・キュー可用性フラグに関連付けられたワークキューの新しいタスクを受け入れるための可用性を示す、前記共有ランダム・アクセス・メモリと
を備えており、
前記システムが、請求項１〜１０のいずれか一項に記載の方法の各ステップを実行する、前記システム。
【請求項１２】
タスク分散プロセスにより新しいタスクを割り当てるためにマルチプロセッサ・アーキテクチャ内のプロセッサに関連付けられたワークキューを選択するためのコンピュータ・プログラムであって、複数のプロセッサであって、前記複数のプロセッサは、前記タスク分散プロセスを実行しているプロセッサであるローカル・プロセッサと、前記ローカル・プロセッサ以外のプロセッサであるリモート・プロセッサとを含む、前記複数のプロセッサと、前記複数のプロセッサと通信可能に結合された共有ランダム・アクセス・メモリであって、前記共有ランダム・アクセス・メモリが複数のワークキューと、当該複数のワークキューそれぞれに関連付けられたキュー可用性フラグを格納し、前記キュー可用性フラグは前記タスク分散プロセスを実行している特定のローカル・プロセッサについてのキュー可用性フラグであるローカル・キュー可用性フラグと前記タスク分散プロセスを実行している特定のローカル・プロセッサ以外のプロセッサについてのキュー可用性フラグであるリモート・キュー可用性フラグとを含み、前記ローカル・キュー可用性フラグは当該ローカル・キュー可用性フラグに関連付けられたワークキューの新しいタスクを受け入れるための可用性を示し、前記リモート・キュー可用性フラグは当該リモート・キュー可用性フラグに関連付けられたワークキューの新しいタスクを受け入れるための可用性を示す、前記共有ランダム・アクセス・メモリとを備えているシステムに、請求項１〜１０のいずれか一項に記載の方法の各ステップを実行させる、前記コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、マルチプロセッサ・コンピュータ・アーキテクチャにおけるタスクのディスパッチに関し、より具体的には、タスク分散処理を実行しているローカル・プロセッサ上で、コンピュータ・プロセッサの待ち状態のプロセス・キュー・サイズを正確に求めることに関する。
【背景技術】
【０００２】
中央演算処理装置（ＣＰＵ）などのコンピュータ・システムに用いられるプロセッサは、現在実行されているタスク及びそのプロセッサによる実行を待っているタスクの管理のために、幾つかのタスクキューを保持することが多い。これらの複数のタスクキューは、例えば、優先順位が異なるタスクを格納することができ、そこでは、優先順位のより低いキュー内のタスクに先立って、優先順位のより高いキュー内のタスクが、プロセッサによりサービスされる。異なる処理の優先順位レベルを表す複数のキューの一例は、処理開始の準備ができているプロセス、及び、既に処理を開始し始めたプロセスを含む、「進行中のワークキュー（in progress work queue）」と呼ばれる優先順位の高いキューを保持するプロセッサである。別のキュー、即ち「新しいメッセージ・キュー」は、例えば、実行予定のタスクを指定する、ネットワークから受け取ったメッセージを格納する。動作において、「新しいメッセージ・キュー」内のメッセージの処理に先立って、優先順位の高い「進行中のワークキュー」内のタスクが、プロセッサによりサービスされる。その結果、新しいメッセージ・キューからのメッセージが処理され、新しいタスクを生成してマルチプロセッサ・アーキテクチャ内のプロセッサに分散するとき、進行中のワークキューは空である。従って、プロセッサの負荷を判断するため、従って、どのプロセッサに新しいタスクを割り当てるかを判断するための共通のメトリックは、プロセッサに関連した進行中のキューのサイズである。
【０００３】
対称型マルチプロセッサ（Symmetric Multiple Processor、ＳＭＰ）サーバのようなマルチプロセッサ・アーキテクチャに組み込まれたプロセッサには、タスク分散プロセス又は同様のプロセスにより、タスクが割り当てられる。一例においては、タスク分散プロセスは、ネットワーク・インターフェースを通して受け取ったネットワーク・メッセージ中のタスク仕様を受け取る。マルチプロセッサ・サーバのネットワーク通信処理アーキテクチャに応じて、タスク分散プロセスは、１つの指定されたプロセッサ上で実行して全てのメッセージを処理することができ、又は、代替的なアーキテクチャが、複数のプロセッサ内のいずれかのプロセッサが、タスク分散プロセスの実行を可能にする。プロセッサが、あるプロセッサに割り当てられるタスクを指定するネットワーク・メッセージを処理するとき、そのプロセッサは、マルチプロセッサ・アーキテクチャの全てのプロセッサの処理負荷を検査し、どのプロセッサにかかる負荷が最も軽いかを判断する。次いで、最も軽負荷のプロセッサにタスクが割り当てられる。
【０００４】
幾つかの処理アーキテクチャは、新しく受け取ったネットワーク・メッセージの処理に応答してタスク分散プロセスを実行することにより動作する。新しく受け取ったネットワーク・メッセージは、進行中のワークキューより優先順位が低い新しいメッセージ・キューから処理される。進行中のワークキュー内にタスクが存在しないとき、タスク分散プロセスをトリガする新しいメッセージ・キュー内のメッセージが選択されて処理されるので、タスク分散プロセスを実行しているプロセッサに関する進行中のワークキューのサイズをタスク分散プロセスにより求めることは、概して誤解を招く恐れがあり、プロセッサの負荷を判断するのに使用する必要がある進行中のワークキューの実際の短時間平均サイズよりも低くなる。進行中のワークキュー内のタスクの数が、プロセッサの処理負荷の判断に用いられる量であるため、一般に、タスク分散プロセスが使用する、タスク分散プロセスを実行しているプロセッサの処理負荷の尺度は、不正確で誤解を招く恐れがあり、低いものとなる。その結果、タスク・プロセッサは、それを実行しているプロセッサについて不正確な低い処理負荷を検出することが多く、その結果、それぞれのプロセッサにより多くのタスクを割り当てることになる。このことにより、マルチプロセッサ・アーキテクチャの複数のプロセッサ間のタスク分散の効率が悪くなり、タスク分散プロセスを実行しているプロセッサに余計なタスクが非効率的に与えられる。マルチプロセッサ・アーキテクチャの１つのプロセッサを用いて全てのネットワーク・メッセージを処理するアーキテクチャ、従って、タスクを複数のプロセッサに分散するアーキテクチャにおいて、この不均等なタスクの分散は特によく見られる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従って、マルチプロセッサ・アーキテクチャにおいてタスク分散プロセスを実行しているプロセッサのために、より正確なプロセッサ負荷測定技術を用いることによって、マルチプロセッサ・コンピュータ・システムの効率を改善することができる。
【課題を解決するための手段】
【０００６】
一実施形態において、新しいタスクを割り当てるためにマルチプロセッサ・アーキテクチャ内のプロセッサに関連付けられたワークキューを選択するための方法が、選択されたプロセッサに関連付けられた少なくとも１つのキュー可用性フラグ（queue availability flag）に基づいて、ローカル・プロセッサ上で、新しいタスクを受け入れるために選択されたプロセッサに関連付けられたワークキューの可用性を判断することを含む。ローカル・プロセッサ及び選択されたプロセッサは、マルチプロセッサ・アーキテクチャ内にあり、かつ、共有ランダム・アクセス・データ・メモリにアクセスする。この方法は、可用性を判断することに応答して、新しいタスクを、選択されたプロセッサに関連付けられたワークキューに割り当てることをさらに含む。この方法は、選択されたプロセッサがローカル・プロセッサであることを判断することと、選択されたプロセッサがローカル・プロセッサではないと判断することに応答して、選択されたプロセッサに関連付けられたワークキューのサイズに基づいて、少なくとも１つのキュー可用性フラグを調整することと、選択されたプロセッサがローカル・プロセッサであると判断することに応答して、少なくとも１つのキュー可用性フラグを調整しないことと、をさらに含む。
【０００７】
別の実施形態において、新しいタスクを割り当てるために、マルチプロセッサ・アーキテクチャ内のプロセッサに関連付けられたワークキューを選択するためのシステムが、複数のプロセッサと、複数のプロセッサと通信可能に結合された共有ランダム・アクセス・データ・メモリを含む。このシステムはまた、選択されたプロセッサに関連付けられた少なくとも１つのキュー可用性フラグに基づいて、ローカル・プロセッサ上で、新しいタスクを受け入れるために、選択されたプロセッサに関連付けられたワークキューの可用性を判断するタスク分散プロセスも含む。ローカル・プロセッサ及び選択されたプロセッサはマルチプロセッサ・アーキテクチャ内にあり、かつ、共有ランダム・アクセス・データ・メモリにアクセスする。タスク分散プロセスはまた、可用性を判断することに応答して、新しいタスクを、選択されたプロセッサに関連付けられたワークキューに割り当てる。タスク分散プロセスは、選択されたプロセッサがローカル・プロセッサであることをさらに判断し、選択されたプロセッサがローカル・プロセッサではないとの判断に応答して、選択されたプロセッサに関連付けられた前記ワークキューのサイズに基づいて少なくとも１つのキュー可用性フラグを調整し、選択されたプロセッサがローカル・プロセッサであるとの判断に応答して、少なくとも１つのキュー可用性フラグを調整しない。
【０００８】
別の実施形態において、新しいタスクを割り当てるために、マルチプロセッサ・アーキテクチャ内のプロセッサに関連付けられたワークキューを選択するためのコンピュータ・プログラムが、コンピュータ可読プログラム・コードがこれと共に具体化されたコンピュータ可読記憶媒体を含む。コンピュータ可読プログラム・コードは、マルチプロセッサ・アーキテクチャ内の各プロセッサが共有ランダム・アクセス・データ・メモリを共有するマルチプロセッサ・アーキテクチャ内の選択されたプロセッサについての少なくとも１つのキュー可用性フラグに基づいて、ローカル・プロセッサ上で、新しいタスクを受け入れるために選択されたプロセッサに関連付けられたワークキューの可用性を判断するように構成されたコンピュータ可読プログラム・コードを含む。選択されたプロセッサは複数プロセッサ内にある。コンピュータ可読プログラム・コードはまた、可用性を判断することに応答して、新しいタスクを選択されたプロセッサに関連付けられたワークキューに割り当てるように構成されたコンピュータ可読プログラム・コードも含む。コンピュータ可読プログラム・コードは、選択されたプロセッサがローカル・プロセッサであることを判断するように構成されたコンピュータ可読プログラム・コードと、選択されたプロセッサがローカル・プロセッサではないと判断することに応答して、選択されたプロセッサに関連付けられたワークキューのサイズに基づいて、少なくとも１つのキュー可用性フラグを調整するように構成されたコンピュータ可読プログラム・コードと、選択されたプロセッサがローカル・プロセッサであると判断することに応答して、少なくとも１つのキュー可用性フラグを調整しないように構成されたコンピュータ可読プログラム・コードと、をさらに含む。
【０００９】
同様の参照番号が、個々の図面を通じて同一の又は機能的に類似した要素を指しており、以下の詳細な説明と共に明細書に組み込まれて、明細書の一部を形成する添付の図面は、種々の実施形態をさらに示し、本発明に従った種々の原理及び全ての利点を説明するように働く。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施形態による、共有メモリ型マルチプロセッサ・システムを示すブロック図である。
【図２】本発明の一実施形態による、図１に示されるようなマルチプロセッサ・システムのプロセッサについてのローカル・キュー可用性フラグ・プロセスを更新するための処理フロー図である。
【図３】本発明の一実施形態による、図１に示されるようなマルチプロセッサ・システム内の多数のプロセッサの１つにタスクをディスパッチするための処理フロー図を示す。
【図４】本発明の一実施形態による、図１に示されるようなプロセッサに関連付けられたワークキューからタスクを受け入れるための処理フロー図を示す。
【図５】本発明の一実施形態による、図１に示されるようなマルチプロセッサ・システムについての複合キュー・サイズを更新するための処理フロー図である。
【図６】本発明の一実施形態による情報処理システムを示すブロック図である。
【発明を実施するための形態】
【００１１】
必要に応じて、本発明の詳細な実施形態がここに開示されるが、開示された実施形態は、種々の形態で具体化することが可能である本発明の単なる例示であることを理解すべきである。従って、ここで開示される具体的な構造上及び機能上の詳細は、限定するものではなく、単に特許請求の範囲の基礎として、及び、事実上あらゆる適切な詳細な構造において本発明を様々に用いることを当業者に教示するための代表的な基礎として解釈されるべきである。さらに、ここで用いられる用語及び語句は、限定するのではなく、寧ろ、本発明の分かりやすい説明を提供することを意図している。
【００１２】
ここに用いられる「１つの（a）」又は「１つの（an）」という用語は、１つ又は１より多いとして定義される。ここに用いられる「複数の（plurality）」という用語は、２つ又は２つより多いとして定義される。ここに用いられる「別の（another）」という用語は、少なくとも第２の又はそれ以上のとして定義される。ここに用いられる「含む（including）」及び「有する（having）」という用語は、備える（comprising）（すなわち、包括的な言葉（open language）として定義される。ここに用いられる「結合される（coupled）」という用語は、必ずしも直接にではなく、必ずしも機械的にではなく、接続されるとして定義される。
【００１３】
タスク分散プロセスを実行するプロセッサの処理負荷を判定するためのアルゴリズムが提示される。提示されるアルゴリズムの一例を具体化する１つのシステムは、全てのプロセッサが共有ランダム・アクセス・メモリ構造体にアクセスする、対称型マルチプロセッサ（ＳＭＰ）システムである。提示されるアルゴリズムは、有利なことに、いずれの最小のキューのタスク分散アルゴリズム、及び、異なる実行優先順位レベルのキューで動作する他の共通のディスパッチャにも適用することができる。
【００１４】
提示されるのは、プロセッサの処理負荷を監視するための技術を提供するアルゴリズムである。提示されるアルゴリズムは、種々の設定時間におけるプロセッサの処理負荷を監視し、タスク分散プロセスの実行と同期化されない。提示される方法の１つの用途は、タスク分散プロセスの実行をトリガする処理タスクキューより優先順位が高い処理タスクキュー内のアイテム数に基づいて、プロセッサの負荷を判断する処理アーキテクチャにおけるものである。本アルゴリズムの一実施形態が、有利に、上述したアーキテクチャを組み入れたマルチプロセッサ・システムに用いられ、タスク分散プロセスを実行するプロセッサの負荷のより正確な判定に基づいて、タスクが、全てのプロセッサにより均等に分散される。
【００１５】
図１は、本発明の一実施形態による共有メモリ型マルチプロセッサ・システム１００を示すブロック図である。共有メモリ型マルチプロセッサ・システム１００は、共有メモリ１０２にアクセスする多数のプロセッサ、すなわちＣＰＵ  １  １１０、ＣＰＵ  ２  １１２、及びＣＰＵ  Ｎ  １１４を含む。各々のプロセッサは、関連したローカル・キャッシュを有し、ＣＰＵ  １  １１０については第１レベルＬ１キャッシュ１１６として表示される。関係技術の当業者であれば本議論に照らして理解するように、第１レベルＬ１キャッシュ１１６のようなローカル・キャッシュは、第１レベルＬ１キャッシュ１１６の例におけるＣＰＵ  １  １１０のような、その関連したプロセッサにより迅速にアクセス可能なデータを格納する。示されるような共有メモリ・システムにおいては、ローカル・キャッシュに関連付けられたプロセッサは、共有メモリ１０２内の対応するデータが変更されなかった場合、ローカル・キャッシュ内に格納されたデータに直接アクセスすることができる。一般に、アクセスの頻度が多い共有メモリにアクセスする処理のオーバーヘッドを被ることなく、関連したプロセッサにより、１つのプロセッサのみにのみ操作されるデータに迅速且つ直接にアクセスすることができる。
【００１６】
共有メモリ１０２は、ワークキュー１  １２０、ワークキュー２  １２２、及びワークキューＮ  １２４のような多数のワークキューの組を含む。共有メモリ１０２内のワークキューの組の各々は、それぞれのプロセッサに関連付けられており、特定のワークキュー内の全てのタスクは、その関連したそれぞれのプロセッサによって実行される。図示される例においては、ＣＰＵ  １  １１０はワークキューの組１  １２０に関連付けられ、ワークキューの組１  １２０内に入れられたタスクのみを実行する。同様に、ＣＰＵ  ２  １１２はワークキューの組２  １２２に関連付けられ、ＣＰＵ  Ｎ  １１４はワークキューの組Ｎ  １２４に関連付けられる。
【００１７】
図示されるワークキューの組の各々は、例えば、異なる実行優先順位のタスクを含む、多数の異なるワークキューを有する。例えば、ワークキューの組１  １２０は、「進行中のワークキュー１」１８８及び「新しいメッセージ・キュー１」１８６を含むものとして示される。他のワークキューの組の各々は、異なる優先順位のタスクを含む、類似した複数のワークキューを含む。本発明の関連部分の説明を簡略にするために、以下の議論では、特定のプロセッサに関連付けられた「ワークキューの組」を、そのプロセッサに関連付けられた「ワークキュー」と呼ぶ。以下の議論では、タスクを「ワークキュー」に入れるとは、タスクを割り当てるために従来より用いられているそのプロセッサに関するワークキューの組内のワークキューに、タスクが割り当てられることを示すように意図される。さらに、以下の説明は、キューのサイズを判断することに言及し、これは、特定のプロセッサに関するワークキューのサイズを判断するためのオペレーティング・システムの従来の技術に言及することを意図している。一実施形態において、タスク分散プロセスにより割り当てられたタスクは、優先順位がより高い進行中のワークキューに入れられ、新しいタスクをどのプロセッサに割り当てるかを決定するために用いられるプロセッサの処理負荷は、そのプロセッサに関連付けられた進行中のワークキューのサイズに基づいている。
【００１８】
各々のワークキューの組内の各々のワークキューは、その関連付けられたプロセッサによって処理されることになるタスクを受け入れることができる。本発明の一実施形態においては、いずれかのプロセッサが、あるタスクをいずれかのワークキューに入れ、それにより、そのワークキューに関連付けられたプロセッサにそのタスクを処理させることができるようになる。本発明の説明を簡略にするために、この議論は、各々のプロセッサに関連付けられた各々のワークキューの組内に含まれる２つのワークキューに言及するものとする。各々のプロセッサに関連付けられた各々のワークキューの組内に、いずれの数のワークキューも含み得ることは明らかである。
【００１９】
共有メモリ１０２は、複合キュー・サイズ１４６の値をさらに格納する。一実施形態のタスク分散プロセスは、ワークキューの組内の各々のワークキューの優先順位について、複合キュー・サイズを繰り返し求めることによって、特定の優先順位のタスクに関する処理負荷を求める。例えば、優先順位レベルのキューごとに、別個の平均キュー・サイズを計算し、複合キュー・サイズ１４６内に格納する。ワークキューの組の各々が進行中のワークキュー及び新しいメッセージ・キューを含む上記の例においては、複合キュー・サイズは、進行中のワークキューの全てについての複合キュー・サイズと、新しいメッセージ・キューの全てについての別個の複合キュー・サイズとを格納する。
【００２０】
本発明の一実施形態は、ワークキューの組１  １２０、ワークキューの組２  １２２、及びワークキューの組Ｎ  １２４内の実行優先順位が異なる別個のキューのような、ワークキューの全てにおけるワークキューの各タイプ内にあるタスクの数の平均値として、複合キュー・サイズ値を繰り返し求める。更に別の実施形態は、マルチプロセッサ・コンピュータ・システムのワークキューの組内のワークキューの各タイプに割り当てられたタスクの数を反映する、平均値、平均、又はいずれかの量を表す任意の値を用いることができる。更に別の実施形態はまた、そのタスクが必要とする推定リソース量などの適切な量に従って、ワークキュー内のタスクに重み付けすることによって、複合キュー・サイズが基にしているワークキューのサイズを求めることもできる。一実施形態においては、複合キュー・サイズは、繰り返し求められ、従って、プロセスへのタスク分散の予想時間よりもずっと長い間隔で更新される。従って、複合キュー・サイズ１４６について共有メモリ１０２内に格納される値は、各プロセッサのローカル・キャッシュ内に格納されることが多く、従って、各々のプロセッサは、多くの場合、全体の共有メモリにアクセスする処理オーバーヘッドなしに、その値にアクセスすることができる。
【００２１】
以下にさらに説明されるように、一実施形態は、キューの組内のキューのタイプの各々について、別個の上限比較値（upper compare value）１４７及び下限比較値（lower compare value）１４８を定める。プロセッサごとに進行中のワークキュー及び新しいメッセージ・キューを有する上述の例では、進行中のワークキュー及び新しいメッセージ・ワークキューの各々について、別個の上限比較値が計算される。同様に、進行中のワークキュー及び新しいメッセージ・ワークキューの各々について、別個の下限比較値が計算される。これらの値は、全て計算され、一実施形態においては、上述の複合キュー・サイズの計算と関連させて、それぞれ上限比較値１４７及び下限比較値１４８として共有メモリ内に格納される。
【００２２】
共有メモリ１０２は、多数のキュー可用性フラグ１３０をさらに格納する。一実施形態は、各プロセッサに関連付けられたキューの組に関連付けられたキュー可用性フラグの別個の対を含む。キュー可用性フラグの特定の対は、特定のキューの組に関連付けられ、その特定のキューの組は特定のプロセッサに関連付けられるので、以下の議論では、特定のキュー可用性フラグは特定のプロセッサに関連付けられるように言及される。キュー可用性フラグと特定のプロセッサとの関連性は、キュー可用性フラグがキューの組に関連付けられ、そのキューの組はその特定のプロセッサに関連付けられるものとして言及されるように理解される。
【００２３】
一実施形態において、キュー可用性フラグの対は、ローカル・キュー可用性フラグ及びリモート・キュー可用性フラグを含む。図示される例において、ワークキューの組１  １２０は、関連したリモート・キュー１可用性フラグ１４０及びローカル・キュー１可用性フラグ１８０を有する。ワークキューの組２  １２２は、関連したリモート・キュー２可用性フラグ１４２及びローカル・キュー２可用性フラグ１８２を有する。ワークキューの組Ｎ  １２４は、関連したリモート・キューＮ可用性フラグ１４４及びローカル・キューＮ可用性フラグ１８４を有する。ローカル・キュー可用性フラグ及びリモート・キュー可用性フラグの個々の用途は、以下に詳細に説明される。
【００２４】
一実施形態において、キュー１可用性フラグ１４０、キュー２可用性フラグ１４２、及びキューＮ可用性フラグ１４４のような、各々のキュー可用性フラグは、それぞれ別個のキャッシュ・ライン内に格納される。関連技術の当業者であれば本議論に照らして理解するように、各プロセッサのキュー可用性フラグをメモリの別個のセクション内に格納することにより、有効なキュー可用性フラグ・データを各プロセッサ内に格納する時間の増大が改善され、その結果、１つのＣＰＵのキュー可用性フラグを更新することで、多数のプロセッサのローカル・キャッシュ内に格納される他のＣＰＵのキュー可用性フラグの値が無効になることはない。２５６バイトのメモリ・キャッシュ・ラインを用いるプロセッサの例では、２５６バイトのグループが、メモリ・キャッシュ（例えば、ＣＰＵ１１０のＬ１キャッシュ）内に格納される。ＣＰＵ１がそのＬ１キャッシュ内に２５６バイトを有し、次いで別のＣＰＵがそれらの２５６バイトのいずれかを更新した場合、２５６バイト全てがＣＰＵ１のＬ１キャッシュから除去される。本発明の一実施形態の動作は、キュー１可用性フラグ１４０のようなキュー可用性フラグの１つが更新されたときに、キュー２可用性フラグ１４２のような他のキュー可用性フラグをフラッシュしない。従って、一実施形態は、ＣＰＵごとのキュー可用性フラグを、それぞれのメモリ・キャッシュ・ライン内に格納する、例えば、キュー可用性フラグは、それぞれの２５６バイト領域内に常駐する。
【００２５】
以下の議論において、「ローカル・プロセッサ」への言及は、対象プロセス、通常はタスク分散プロセスを実行しているプロセッサを指す。「リモート・プロセッサ」は、対象プロセスを実行しているプロセッサ以外のいずれかの他のプロセッサを指す。全てのプロセッサ、即ち、ローカル・プロセッサ及びリモート・プロセッサは、図１に示されるＣＰＵのような、ＳＭＰサーバの複数のプロセッサ内に含ませることができる。
【００２６】
一実施形態におけるキュー可用性フラグの各対は、それぞれのワークキューの組に関連付けられ、新しいタスクを受け入れるための、関連したワークキューの組の能力を示す。一実施形態において、各々のキュー可用性フラグには、２つの値のうちの一方が割り当てられる。第１の値は「グリーン」と呼ばれ、タスクを受け入れるのに、関連したワークキューが利用可能であることを示す。第２の値は「レッド」と呼ばれ、タスクを受け入れるのに、関連したワークキューが利用不能であることを示す。一実施形態において、以下にさらに詳細に説明されるように、特定のワークキューが新しいタスクを受け入れることができるという判断は、複合キュー・サイズ１４６に関連付けられた値と特定のワークキューのサイズとの比較に基づいている。本発明の種々の実施形態は、ワークキュー内のエントリの生のカウント、各エントリがエントリによって消費されると考えられる推定リソース量によって重み付けされるエントリの重み付けされたカウント、及び同様の値のような、特定のワークキューのサイズについての異なる値を用いることができる。
【００２７】
ここでは、新しいタスクを受け入れるためのワークキューの可用性（availability）又は非可用性（unavailability）を示すものとして、キュー可用性フラグを説明する。これらの用語は、以下に説明される本発明の一実施形態の処理によって判断されるようなワークキューの比較状態（comparative state）を説明するために用いられる。新しいタスクを受け入れるのに、ワークキューが「利用不能である（unavailable）」であると表示されても、新しいタスクをそのワークキュー内に入れることが可能であることは明らかである。種々の実施形態の処理は、全てのワークキューが「利用不能である」として示されるときの条件の処理など、ワークキューが「利用不能である」ことをキュー可用性フラグが示すときに、タスクをワークキュー内に入れる処理を含むことが可能である。
【００２８】
共有メモリ１０２は、例えば、ＣＰＵ  １  １１０、ＣＰＵ  ２  １１２、及びＣＰＵ  Ｎ  １１４によって実行される多数のオペレーティング・プログラムを格納する。共有メモリ１０２内に格納されたオペレーティング・プログラムは、例えば、複合サイズ・プロセッサ・プログラム１７０、タスク分散プロセッサ・プログラム１７２、タスク受け入れプロセッサ・プログラム１７４、及びローカル・フラグ保持プロセッサ・プログラム１７６を含む。これらのオペレーティング・プログラムのプロセスは、以下に詳細に説明される。
【００２９】
マルチプロセッサ・コンピュータ・システム１００は、ＣＰＵ  １  １１０、ＣＰＵ２  １１２、及びＣＰＵ  Ｎ  １１４といった複数のプロセッサに割り当てられるタスク、及び、それらにより処理されるタスクを生成する。種々のプロセッサに割り当てられるタスクの１つのソースは、ネットワーク・インターフェース１６０から受信され、ネットワーク・メッセージ・バッファ１６２内に入れられる、ネットワーク・メッセージを通じたものである。マルチプロセッサ・コンピュータ・システム１００の種々の実施形態は、ネットワーク・インターフェース１６０によって受信され、例えばラウンド・ロビン処理若しくは処理の可用性に基づいて、１つの専用プロセッサ又はプロセッサのいずれかによってネットワーク・メッセージ・バッファ内に格納される、ネットワーク・メッセージを処理する。
【００３０】
以下の説明は、どのワークキューを、従って、どのプロセッサに新しいタスクを割り当てるかを判断するために用いられる処理を説明する。本発明の一実施形態は、２つの異なる優先順位レベルを有する２つのキュー、即ち進行中のキュー及び新しいメッセージ・キューを含む、各プロセッサについてのキューの組を含む。キューの組内のこれらの２つの異なるキューは、ここでは、２つのキュー・タイプと呼ばれる。更に別の実施形態は、異なる優先順位レベルを有する任意の数のキュー、従って、任意の数のキュー・タイプを含むことができる。新しいタスクの割り当てを判断する際、最初の判断は、例えば、どの優先順位レベルのキューかといった、どのキュー・タイプかに関して行なわれることが理解される。以下に説明される処理は、キュー・タイプごとに異なるキュー特性値を使用する。例えば、複合キュー・サイズ、上限比較値、下限比較値等への言及は全て、新しいタスクが付加されることになるキュー・タイプに対応する、それらの量の値を指す。本発明の説明を簡略にするために、以下の説明は、新しいタスクが選択されたプロセッサの進行中のワークキューに付加されることになる例示的な実施形態に基づいており、関連したフラグは全て、キューの組内の進行中のキューの相対的サイズを参照する。以下の説明の原理は、キューの組内の複数のキューの相対的サイズの判断に拡張できることが理解される。
【００３１】
本発明の一実施形態は、いずれかのプロセッサが、受信したネットワーク・メッセージに応答して生成されたようなタスクを、それぞれのワークキュー、又は他のいずれかのプロセッサのワークキューに入れることを可能にする。以下にさらに詳細に説明されるように、特定のプロセッサがプロセッサに割り当てるタスクを有するとき、その特定のプロセッサは、グリーンであるキュー可用性フラグを識別する。グリーンのキュー可用性フラグが識別されると、特定のプロセッサは、タスクを、識別されたグリーンのキュー可用性フラグに関連付けられたワークキュー内に入れる。以下に説明されるように、処理は、タスク分散プロセスを実行しているローカル・プロセッサ以外のプロセッサについてのリモート・キュー可用性フラグ、又は、タスク分散プロセスを実行している特定のローカル・プロセッサについてのローカル・キュー可用性フラグのいずれかを検査する。タスクをリモート・プロセッサのワークキューに付加する場合、特定のプロセッサは、次に、タスクが付加されたばかりのワークキューのサイズを判断し、そのワークキューが利用不能であるかどうかを判断し、ワークキューの可用性が変更された場合、特定のプロセッサは、関連したキュー可用性フラグを更新する。同じく以下にさらに説明されるように、タスクをローカル・プロセッサのワークキューに付加するプロセスは、そのプロセッサに関するリモート・キュー可用性フラグを変更するだけであり、そのプロセッサのローカル・キュー可用性フラグは変更しない。
【００３２】
本発明の一実施形態の特定のプロセッサは、ラウンド・ロビン・カウンタに部分的に基づいて、新しいタスクを割り当てるプロセッサを判断する。このような実施形態においては、共有メモリ１０２は、プロセッサごとに別個のラウンド・ロビン・カウンタを格納する。図示される例においては、共有メモリ１０２は、ラウンド・ロビン・カウンタ１  １５０、ラウンド・ロビン・カウンタ２  １５２、及びラウンド・ロビン・カウンタＮ  １５４を格納する。これらのラウンド・ロビン・カウンタの各々は、それぞれのプロセッサに関連付けられるので、例えば、ＣＰＵ  １  １１０のみがラウンド・ロビン・カウンタ１  １５０を使用し、ＣＰＵ  ２  １１２のみがラウンド・ロビン・カウンタ２  １５２を使用し、以下同様である。このような構成により、ラウンド・ロビン・カウンタの値が、そのプロセッサについてのローカル・キャッシュ内に格納され、このラウンド・ロビン・カウンタの値は他のプロセッサによっては決して変更されないので、その値が、共有メモリ１０２において更新され、他のプロセッサと交換されるよう要求されることは決してない。この構成により、従来のタスク分散アーキテクチャによって実行されるように、共有メモリを通して共通のラウンド・ロビン値を複数のプロセッサと共有する、処理のオーバーヘッドがなくなる。
【００３３】
一実施形態においては、その特定のプロセッサに関連付けられたラウンド・ロビン・カウンタの現在の値に１を加算することによって、特定のプロセッサによって検査される第１のキュー可用性フラグが選択される。グリーンのキュー可用性フラグが見出されるまで、そのラウンド・ロビン・カウンタがインクリメントされ、インクリメントされた値に関連付けられたキュー可用性フラグが検査される。
【００３４】
図２は、本発明の一実施形態による、図１に示されるようなマルチプロセッサ・システム１００のプロセッサに関するローカル・キュー可用性フラグを更新するプロセス２００の処理フロー図である。ローカル・キュー可用性フラグ更新プロセス２００は、一実施形態において、ローカル・フラグ保持プロセッサ・プログラム１７６において具体化され、プロセッサごとにローカル・キュー可用性フラグの適切な値を保持する。ローカル・キュー可用性フラグ更新プロセス２００は、上述したＣＰＵ  １  １１０、ＣＰＵ  ２  １１２、又はＣＰＵ  Ｎ  １１４のいずれかのような、共有メモリを用いてマルチ処理システムの複数のプロセッサ内のプロセッサの全てによって実行される。本発明の幾つかの実施形態のローカル・キュー可用性フラグ更新プロセス２００は、一定間隔又は変動間隔で、繰り返し実行することができる。ローカル・キュー可用性フラグ更新プロセス２００の繰り返しの間に変動間隔を用いることにより、このプロセスが何らかの作業負荷バーストのタイミングに同期されることが回避され、従って、プロセッサのキュー可用性のより信頼性のある表示を提供することができる。
【００３５】
ローカル・キュー可用性フラグ更新プロセス２００は、２０２において、ローカル・ワークキュー検査イベントを待つことで始まる。本発明の種々の実施形態は、異なる技術を用いて、ローカル・キュー可用性フラグ更新プロセス２００の各々の繰り返しを開始する。例えば、一実施形態は、プロセッサのタイミング・アーキテクチャを用いて、一定の時間間隔又は変動する時間間隔で、繰り返しをトリガすることができる。一実施形態においては、以下に説明されるように、プロセッサのタイミング中断を用いて、ローカル・キュー可用性フラグ更新プロセス２００の直近の実行によって構成された間隔で、処理をトリガする。一例において、ローカル・キュー可用性フラグ更新プロセス２００は、１０ｍＳから５０ｍＳまでの間の変動間隔で実行される。
【００３６】
一実施形態の処理は、ローカル・プロセッサに関連付けられたワークキューのワークキュー・サイズに基づいて、新しいタスクを受け入れるのにローカル・プロセッサに関するワークキューが利用可能であるか又は利用不能かを示すローカル・プロセッサに関するローカル・キュー可用性フラグを変更すべきかどうかを決定する。一実施形態の処理は、異なるキュー・サイズの閾値を用いて、新しいタスクを受け入れるのにワークキューが利用可能であるかどうか、即ち、キュー可用性フラグをグリーンにすべきかどうかを判断し、かつ、新しいタスクを受け入れるのにワークキューが利用不能であるかどうか、よって、キュー可用性フラグを「レッド」にすべきかどうかを判断する。この議論において、新しいタスクを受け入れるのにワークキューが利用可能であるかどうか、即ち、キュー可用性フラグをレッドからグリーンに変更すべきかどうかを判断するための閾値は、「下限比較値１４８」と呼ばれる。新しいタスクを受け入れるのにワークキューが利用不能であるかどうか、即ち、キュー可用性フラグをグリーンからレッドに変更すべきかどうかを判断するための閾値は、「上限比較値１４７」と呼ばれる。一実施形態において、ＣＰＵの各々に関連付けられたワークキューの全てに関するワークキュー・サイズの平均が、両方の比較値の基準として用いられる。本発明の一実施形態は、同じ上限比較値１４７及び下限比較値１４８を用いて、ローカル・キュー可用性フラグ及びリモート・キュー可用性フラグの値を判断する。更に別の実施形態は、これらの異なるキュー可用性フラグに対して異なる比較値を用いることができる。
【００３７】
上限比較値１４７は、一例において、ＣＰＵの各々に関連付けられたワークキューの全てに関するワークキュー・サイズの平均よりも２５％大きい。下限比較値１４８は、ＣＰＵの各々に関連付けられたワークキューの全てに関するワークキュー・サイズの平均に設定される。一例として、全てのワークキューに関するワークキュー・サイズの平均が１２である場合を示す。上限比較値１４７は、この例では、１２より２５％大きい、即ち、１６である。この例において、上限比較値１４７は、２５％だけその値を増加させることで平均キュー・サイズを「調整する」ことによって求められる。この例は、１つの設計上の選択にすぎないことは明らかであり、更に別の実施形態は、新しいタスクを受け入れるのにワークキューが利用可能であるか又は利用不能であるかを判断するために、種々の適切な量を用いることができる。種々の実施形態は、平均キュー・サイズ又は他のいずれかの適切な量への調整を用いることによって、上限比較値及び下限比較値の一方又は両方を求めることができる。種々の実施形態は、さらに、上限比較値及び下限比較値のうちの一方として、平均キュー・サイズを用いることができる。
【００３８】
同じでない上限比較値１４７及び下限比較値１４８を用いることにより、これらのフラグの値を変更する頻度が低減される。両方の状態の変化に対して同じ閾値が用いられた場合、タスクがワークキューに付加される度又はワークキューから取り出される度、キュー可用性フラグの値が変わる可能性がある。このことにより、他のプロセッサのローカル・キャッシュ内にあるそのフラグの値が無効になり、そのフラグが更新される度に、他のプロセッサのローカル・キャッシュの更新が必要になる。上限比較値及び下限比較値に対して異なる値を用いることにより、フラグの値を変更する頻度がずっと少なくなり、従って、有効な値が、複数のプロセッサの全てのローカル・キャッシュ内に含まれ、これらのキュー可用性フラグの値の検査の間に必要とされるローカル・キャッシュ更新の量が大きく低減される。
【００３９】
ローカル・キュー可用性フラグ更新プロセス２００の処理は、２０４において、キューの組内の各キュー・タイプについての上限比較値を読み取ることで続行する。ワークキューの組が進行中のワークキュー及びネットワーク・メッセージ・ワークキューを含む例において、タスクは、進行中のワークキュー又は新しいメッセージ・ワークキューのいずれかに割り当てられるように決定される。一実施形態の処理は、各キュー・タイプに関連付けられた上限比較値１４７から上限比較値を読み取る。一実施形態において、特定のタイプのワークキューのタイプの全てに関する平均キュー・サイズを、上限比較値１４７の基準として使用し、それに一定の増加率が加えられる。更に別の実施形態は、いずれかの適切な方法によって各キュー・タイプについての複合キュー・サイズ１４６を調整し、上限比較値を導き出すことができる。処理は、２０８において、ワークキューの各タイプのローカル・ワークキュー・サイズを求める。次いで、処理は、２１０において、このプロセッサに関するローカル・キュー可用性インジケータが「レッド」であり、これにより、新しいタスクを受け入れるのにキューが利用不能であることを示すかどうか、及び、ローカル・キュー・サイズが下部比較サイズ１４８より小さいかどうかを判断する。ローカル・キュー・サイズが下部比較サイズより小さい場合、ローカル・ワークキューは、新しいタスクを受け入れることが可能であり、ローカル・キュー可用性インジケータが「レッド」である場合、その状態を変更しなければならない。これらの条件が真である場合、ステップ２１２において、処理は、ローカル・キュー可用性インジケータを「グリーン」に設定する。
【００４０】
処理は引き続き、２１４において、共有メモリ１０２から、各キュー・タイプについての下限比較値１４８を取り出す。上述されたように、一実施形態においては、下限比較値１４８は、特定のタイプの全てのワークキューについての平均キュー・サイズに設定される。更に別の実施形態は、いずれかの適切な方法によって複合キュー・サイズ１４６を調整し、下限比較値１４８を導き出すことができる。
【００４１】
次いで、処理は、２１６において、このプロセッサについてのローカル・キュー可用性インジケータが「グリーン」であり、これにより、新しいタスクを受け入れるのにキューが利用可能であることを示すかどうか、及び、ローカル・キュー・サイズが上部比較サイズより大きいかどうかを判断する。ローカル・キュー・サイズが上部比較サイズより大きい場合、新しいタスクを受け入れるのにローカル・ワークキューは利用不能であり、ローカル・キュー可用性インジケータが「グリーン」である場合、その状態を変更しなければならない。これらの条件が真である場合、処理は、ステップ２１８において、ローカル・キュー可用性インジケータを「レッド」に設定する。
【００４２】
ローカル・キュー可用性フラグの値は、必要な場合にのみ変更され、変更された値は、そのプロセッサのローカル・キャッシュがその位置を再利用するとき、共有メモリにおいて変更された値を更新する必要はないことに留意されたい。
【００４３】
処理は引き続き、２２０において、次のローカル・ワークキュー検査イベントを構成する。上述のように、このプロセスを実施しているプロセッサの実行タイミング・アーキテクチャを用いて、将来のある時期にこのイベントが発生するように構成することができる。
【００４４】
図３は、本発明の一実施形態による、図１に示されるようなマルチプロセッサ・システム内の多数のプロセッサのうちの１つにタスクをディスパッチするための処理フロー図を示す。タスク・ディスパッチ処理フロー３００は、一実施形態において、タスク分散プロセッサ・プログラム１７２において具体化され、マルチプロセッサ・システム１００内のいずれかのプロセッサによって実行されることが可能である。タスク・ディスパッチ処理は、３０２において、ディスパッチする新しいタスクを受け取ることで開始する。新しいタスクは、例えば、ネットワーク・インターフェース１６０を通して受け取ったネットワーク・メッセージから生じる場合もあり、又は、マルチプロセッサ・システム１００内のプロセッサ内で生成される場合もある。処理は引き続き、３０４において、タスク・ディスパッチ処理を実行しているプロセッサに関連付けられたローカル・プロセッサのラウンド・ロビン・カウンタを取り出す。上述のように、本発明の一実施形態は、プロセッサごとに別個のローカル・ラウンド・ロビン・カウンタを共有メモリ内に格納する。
【００４５】
本発明の一実施形態において、処理は引き続き、３２０において、カウンタ値が、ローカル・プロセッサ、即ち、タスク・ディスパッチ処理を実行しているプロセッサについてのキューを示しているか、或いは、ここではリモート・プロセッサと呼ばれる別のプロセッサについてのキューを示しているかを判断する。カウンタ値がローカル・プロセッサを示す場合、３２２において、タスク・ディスパッチ処理を実行しているプロセッサに関連付けられたローカル・キュー可用性フラグを検査する。一例において、ＣＰＵ  １  １１０がタスク・ディスパッチ処理を実行している場合、ローカル・キュー１可用性フラグが検査される。カウンタ値がローカル・プロセッサに関連付けられたキューを示さない場合、処理は、３０６において、リモート・キュー可用性フラグを検査して、タスクを分散するプロセッサに関するローカル・ラウンド・ロビン・カウンタの値で示されるワークキューを捜すことによって続行する。タスク・ディスパッチ処理を実行しているＣＰＵ  １  １１０の例においては、ラウンド・ロビン・カウンタがＣＰＵ  ２に関連付けられたキューを示す場合、ローカル・キュー２可用性フラグが検査される。
【００４６】
ローカル・プロセッサに関するローカル・キュー可用性フラグ又はリモート・プロセッサに関するリモート・キュー可用性フラグのいずれかを検査した後、処理は次に、３０８において、タスク・ディスパッチ処理を実行しているプロセッサに関するローカル・ラウンド・ロビン・カウンタをインクリメントする。一実施形態において、ラウンド・ロビン・カウンタは「Ｎを法として（Modulo-N）」インクリメントされ、ここで「Ｎ」は、マルチプロセッサ・アーキテクチャにおけるプロセッサの数である。例えば、５つのプロセッサを有するシステムにおいては、ラウンド・ロビン・カウンタが５（即ち、最大数のプロセッサを示す）に等しくなると、ラウンド・ロビン・カウンタは、その値を最小数のプロセッサに再設定することにより「インクリメントされる」。
【００４７】
処理は、３１０において、検査されたキュー可用性フラグが「グリーン」であり、これにより、タスクを受け入れるのに検査されたキュー可用性フラグに関連付けられたワークキューが利用可能であることが示されるかどうかを判断する。検査されたキュー可用性フラグがグリーンではない場合、即ち、それが「レッド」であり、新しいタスクを受け入れるのにワークキューが利用不能であることを示す場合、処理は、３３０において、新しいタスクをディスパッチするために、この処理において全てのキュー可用性フラグがチェックされたかどうかを判断する。全てのキューがチェックされ、処理により如何なる「グリーン」のフラグも見出されなかった場合、処理は、全てのフラグが「レッド」であると想定し、キュー可用性フラグをチェックした最初のキューにタスクを割り当てることを選択する。一実施形態において、３３０における判断により、全てのキュー可用性フラグがチェックされなかったと判断された場合、処理は、３０６において、次のワークキューについてのキュー可用性フラグの検査に戻り、上述のように処理が続行する。全てのキューがチェックされた場合、処理は引き続き、３３２において、タスクを、第１の通過点３０６において最初に検査されたキュー可用性フラグに対応するキュー内に入れる。
【００４８】
検査されたキュー可用性フラグが「グリーン」であると判断された場合、処理は、３１２において、タスクを、グリーンであった検査されたキュー可用性フラグに関連付けられたワークキューに入れることに進む。
【００４９】
処理は、３２４において、タスクが、ローカル・ワークキュー、即ち、タスク・ディスパッチ処理を実行しているプロセッサに関連付けられたワークキューに付加されたかどうかを判断することで進行する。タスクがローカル・ワークキューに付加された場合、処理は終了する。
【００５０】
タスクがローカル・ワークキューに付加されなかったと判断された場合、即ち、タスクが異なるリモート・プロセッサのワークキューに付加された場合、一実施形態の処理は、３１４において、上述されたように新しいタスクを受け取るためのキュー・タイプについての上限比較値１４７を取り出す。
【００５１】
上限比較値１４７はこのプロセス中に読み取られるにすぎず、書き込みはなされないので、他のプロセッサのローカル・キャッシュにおいて、この値の有効性が保存されることに留意すべきである。次いで、処理は引き続き、３１６において、グリーンであった検査されたキュー可用性フラグに関連付けられたワークキューのサイズ、即ち、３１２においてタスクが入れられたワークキューのサイズが、上限比較値より大きいかどうかを判断する。そのワークキューのサイズが上限比較値より大きい場合、３１８において、そのワークキューに関連付けられたリモート・キュー可用性フラグを「レッド」に設定し、新しいタスクを受け入れるのに該ワークキューが利用不能であることを示す。そのワークキューのサイズが上限比較値よりも大きくない場合、処理は終了する。ワークキューのサイズが上限比較値を超えない場合、即ち、新しいタスクを受け入れるのにワークキューが利用不能であることを判断するのに失敗した場合、このタスクをこのプロセッサに割り当てた結果として、関連したリモート・キュー可用性フラグの値への変更がなされないことに留意すべきである。また、３１８における「レッド」へのフラグの設定は、３１０において判断されるようにフラグの値が「グリーン」であった場合にしか達成されないので、上述の処理により、関連したキュー可用性フラグの値が変更されないということにも留意すべきである。一実施形態は、値がグリーンからレッドに変更された場合にのみ「設定」を行なうように動作し、他のプロセッサのローカル・キャッシュ・メモリ内のその値を無効にしないようにする。本発明の実施形態は、他のプロセッサのローカル・キャッシュ・メモリ内のキュー可用性フラグの値を無効にするのを防ぐために、その値が変更されるときにのみ、キュー可用性フラグの値を「設定」するように動作し、値が変更されないときには「設定」動作は行なわれないことに留意すべきである。言い換えれば、キュー可用性フラグの値が既に「レッド」である場合、処理がその値を再び「レッド」に設定することはない。この値を修正しないことを受けて、以前にこのリモート・キュー可用性フラグにアクセスしたことがあり、ローカル・キャッシュ内にその値を有する他のプロセッサは、引き続き、共有メモリ型アクセス処理を通してローカル・キャッシュの更新をトリガすることなく、そのローカルのキャッシュに入れられた値を使い続けることができる。特に共有メモリ構造を共用するプロセッサの数が大きくなるにつれて、この動作は、共有メモリの処理を通してローカル・キャッシュを更新する際に生じる輻輳を低減させ、共有メモリを用いるマルチプロセッサ・システムの処理量を増大させる。
【００５２】
図４は、本発明の一実施形態による、図１に示されるような共有メモリ１０２を用いるマルチプロセッサ・システムにおいて、プロセッサに関連付けられたワークキューからのタスクを受け入れるプロセス４００についての処理フロー図を示す。プロセッサに関連付けられたワークキューからのタスク受け入れプロセス４００は、一実施形態において、タスク受け入れプロセッサ・プログラム１７４において具体化され、かつ、上述したようなＣＰＵ  １  １１０、ＣＰＵ  ２
１１２、又はＣＰＵ  Ｎ  １１４のいずれかのような、共有メモリを用いるマルチプロセッサ・システムの複数のプロセッサ内のいずれのプロセッサによっても実行される。プロセッサに関連付けられたワークキューからのタスク受け入れ４００を実行するプロセッサは、４０２において、一実施形態においては、共有メモリ１０２内に保持されるその関連したワークキューからのタスクを受け入れる。一般に、当業者であれば本議論に照らして理解するように、特定のＣＰＵは、いつ新しいタスクをその関連したワークキューから受け入れるか、従って、この処理をいつ開始するかを判断するための、関連した処理を有する。処理は、４０４において、プロセッサに関連付けられたワークワークキューからのタスク受け入れプロセス４００を実行しているプロセッサに関連付けられたワークキューについて、リモート・キュー可用性フラグを共有メモリから取り出すことで続行する。本発明の一実施形態は、この処理を実行しているプロセッサについて、ローカル・キュー可用性フラグを検査も又は修正もしないが、タスクをこのプロセッサに割り当てるかどうかを決定するとき、他のプロセッサによって検査されるフラグであるリモート・キュー可用性フラグのみを検査し、修正することに留意すべきである。
【００５３】
処理は引き続き、キューに入れられたタスクが除去されたことに基づいて、このプロセッサに関するリモート・キュー可用性フラグが状態を変更すべきかどうかを判断する。処理は、４０６において、この処理を実行しているプロセッサに関するリモート・キュー可用性フラグが「レッド」であり、従って、新しいタスクを受け入れるのにそのワークキューが利用不能であることが示されるかどうかを判断する。リモート・キュー可用性フラグが「レッド」でない場合、リモート・キュー可用性フラグの状態の変更は必要でなく、処理は終了する。
【００５４】
リモート・キュー可用性フラグが「レッド」であった場合、処理は、４１０において、共有メモリ１０２から下限比較値１４８を取り出す。上述のように、下限比較値は、複合キュー・サイズ１４６に基づいて計算される。一実施形態における下限比較値１４８の計算が、以下に説明される。一実施形態においては、全てのワークキューに関する平均キュー・サイズが、下限比較値として用いられる。更に別の実施形態は、いずれかの適切な方法によって複合キュー・サイズ１４６を調整し、下限比較値を導き出すことができる。下限比較値１４８はこのプロセス中に読み取られるにすぎず、書き込みはされないので、他のプロセッサのローカル・キャッシュにおいてこの値の有効性が保存されることに留意すべきである。次いで、処理は、４１２において、この処理を実行しているプロセッサに関する現在のワークキュー・サイズが、求められた下限比較値より小さいかどうかを判断する。現在のワークキュー・サイズが下限比較値より小さい場合、処理は、４１４において、リモート・キュー可用性フラグを「レッド」から「グリーン」に変更し、ワークキューが新しいタスクを受け入れることができることを示す。現在のワークキュー・サイズが下限比較値より小さくはない場合、処理は終了する。本発明の実施形態は、他のプロセッサのローカル・キャッシュ・メモリ内のキュー可用性フラグの値を無効にするのを防ぐために、その値が変更されるときにのみ、キュー可用性フラグの値を「設定」するように動作し、値が変更されないときには「設定」動作は行なわれないことに留意すべきである。言い換えれば、キュー可用性フラグの値が既に「グリーン」である場合、処理がその値を再び「グリーン」に設定することはない。リモート・キュー可用性フラグの値は、必要な場合にのみ変更され、上述したように、求められたこのワークキューのタスク受け入れ能力が変わらない限り、他のプロセッサのローカル・キャッシュ内に含有されるこのフラグの値は影響を受けない。
【００５５】
図５は、本発明の一実施形態による、図１に示されるようなマルチプロセッサ・システム１００についての、複合キュー・サイズの更新５００のための処理フロー図である。本発明の種々の実施形態において、複合キュー・サイズの更新５００は、例えば、複合キュー・サイズ・プロセッサ・プログラム１７０において具体化され、かつ、上述したようなＣＰＵ  １  １１０、ＣＰＵ  ２  １１２、又はＣＰＵ  Ｎ  １１４のいずれかのような、共有メモリを用いるマルチプロセッサ・システムの複数のプロセッサ内のいずれのプロセッサによっても実行することができる。種々の実施形態は、例えば、この処理を常に実行するように、１つのプロセッサを構成することができ、或いは、種々のプロセッサによって様々な繰り返しを実行することができる。一般に、複合キュー・サイズの更新５００は、繰り返し毎に、１つのプロセッサによって繰り返し行なわれる。
【００５６】
複合キュー・サイズの更新５００は、５０２において、複合キュー・サイズ更新イベントの開始を待つことで始まる。本発明の種々の実施形態は、異なる技術を用いて、複合キュー・サイズの更新５００の各々の繰り返しを開始する。例えば、一実施形態は、プロセッサのタイミング・アーキテクチャを用いて、一定の時間間隔又は変動する時間間隔で繰り返しをトリガすることができる。一実施形態において、プロセッサのタイミング中断を用いて、５０ｍＳの間隔で処理をトリガし、結果として複合キュー・サイズ更新プロセス５００が１秒当たり２０回実行される。
【００５７】
複合キュー・サイズ更新イベントが開始されると、処理は、５０４において、進行中のワークキューのサイズ、ワークキューの組１  １２０のような、マルチプロセッサに関連付けられたワークキューの組内のワークキューの各タイプ、及び、ワークキューの組２  １２２及びワークキューの組Ｎ  １２４内のワークキューの２つのタイプに関するワークキュー・サイズを求める。マルチプロセッサ・システムは、一般に、各々のワークキュー・サイズを判断するために、確立された処理手続きを有する。上述したように、ワークキューの「サイズ」は、ワークキューにおける生のカウント又はタスク、或いは、各タスクについての予想リソース要件に基づいた重み付けカウントのような、いずれかの適切な尺度に基づくものとすることができる。
【００５８】
次いで、一実施形態の処理は、５０６において、ワークキューの組内のワークキューの各タイプについての平均ワークキュー・サイズを求め、ここで、平均ワークキュー・サイズは、５０４において求められたようなワークキューのそのタイプの全てのサイズの平均に等しい。ワークキューの組が進行中のワークキュー及びネットワーク・メッセージ・ワークキューを含む例においては、ワークキューの組の全ての中のこれらの２つのキュー・タイプの各々について、別個の平均ワークキュー値を求める。この段階において、キュー・サイズによって処理負荷を表すための他の適切な量を、代替的に求めることもできる。次いで、処理は、５０８において、直近の「Ｎ」個の平均キュー・サイズ値に対して、平均ワークキュー・サイズの各々を平滑化する。一実施形態において、複合キュー・サイズ更新プロセス５００の最後のＮ回の繰り返しの際に求められたような、直近の「Ｎ」個の求められた平均キュー・サイズの移動窓平均が用いられる。「Ｎ」の値は、２０のようないずれかの実用値となるように選択することができる。ワークキューの組内の各キュー・タイプについての平滑化された平均ワークキュー・サイズは、次いで、５１０において、共有メモリ１０２内に複合キュー・サイズ１４６として格納される。次いで、処理は、５１２において、ワークキューの組内のワークキューの各タイプについての上限比較値１４７及び下限比較値１４８を計算し、共有メモリ１０２内に格納する。ワークキューの組が進行中のワークキュー及びネットワーク・メッセージ・ワークキューを含む例において、上限比較値１４７は、進行中のワークキュー及びネットワーク・メッセージ・ワークキューの各々について別個の上限比較値を含み、下限比較値１４８は、進行中のワークキュー及びネットワーク・メッセージ・ワークキューの各々について、別個の下限比較値を含む。上限比較値１４７及び下限比較値１４８の値は、このプロセス中にのみ書き込まれ、従って、図２、図３、及び図４に示された上述の処理については読み取り専用であることに留意すべきである。次いで、５０２において、処理は戻って、複合キュー・サイズ更新イベントの開始を待ち、上述の処理の次の繰り返しを開始する。
【００５９】
上述したアルゴリズムは、共有メモリ１０２内に格納された各ワークキューに対して、１つのキュー可用性フラグを用いる。代替的な実施形態は、各ワークキューに対して２つのキュー可用性フラグ、即ち、ローカル・キュー可用性フラグ及びリモート・キュー可用性フラグを用いることができる。各ワークキューに対して２つのキュー可用性フラグを用いるアーキテクチャは、タスク分散を実行しているプロセッサ以外のプロセッサに関するワークキュー・データにアクセスするときに上述したアルゴリズムを使用し、プロセッサがそのキューから新しいタスクを受け入れるときに外部キュー可用性フラグを保持する。
【００６０】
情報処理システム
当業者によって認識されるように、本発明の態様は、システム、方法、又はコンピュータ・プログラムとして具体化することができる。従って、本発明の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、又はソフトウェアの態様とハードウェアの態様とが組み合わされた実施形態の形式を取ることができ、これらは全て、本明細書において一般的に「回路」、「モジュール」又は「システム」と呼ぶことができる。さらに、本発明の態様は、媒体上に具体化されたコンピュータ可読プログラム・コードを有する、１つ又は複数のコンピュータ可読媒体内に具体化されたコンピュータ・プログラムの形式を取ることができる。
【００６１】
１つ又は複数のコンピュータ可読媒体の任意の組み合わせを用いることができる。コンピュータ可読媒体は、コンピュータ可読信号媒体又はコンピュータ可読記憶媒体とすることができる。コンピュータ可読記憶媒体は、例えば、電子的、磁気的、光学的、電磁的、赤外線、又は半導体のシステム、装置、又はデバイス、或いは上記のいずれかの適切な組み合わせとすることができるが、これらに限定されるものではない。コンピュータ可読記憶媒体のより具体的な例（網羅的ではないリスト）は以下のもの、すなわち、１つ又は複数の配線を有する電気的接続、ポータブル・コンピュータ・ディスケット、ハードディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能なプログラム可能読み出し専用メモリ（ＥＰＲＯＭ又はフラッシュメモリ）、光ファイバ、ポータブル・コンパクト・ディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）、光記憶装置、磁気記憶装置、又は上記のいずれかの適切な組み合わせを含む。本文書の文脈において、コンピュータ可読記憶媒体は、命令実行システム、装置、又はデバイスによって使用するため、又はそれらと接続して使用するために、プログラムを収納又は格納することができる任意の有形の媒体とすることができる。
【００６２】
コンピュータ可読信号媒体は、コンピュータ可読プログラム・コードがその中で具体化された、ベースバンド内の又は搬送波の一部としての伝搬されたデータ信号を含むものとすることができる。このような伝搬信号は、これらに限定されるものではないが、電磁気、光学式、又はそれらの任意の適切な組み合わせを含む、種々の異なる形のいずれかを取ることができる。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではなく、命令実行システム、装置、又はデバイスによって使用するため、又はそれらと接続して使用するために、プログラムを通信し、伝搬し、又は輸送することができる、任意のコンピュータ可読媒体とすることができる。
【００６３】
コンピュータ可読媒体上に具体化されたプログラム・コードは、これらに限定されるものではないが、無線、有線、光ファイバ・ケーブル、ＲＦ等、又は上記のいずれかの適切な組み合わせを含む、いずれかの適切な媒体を用いて伝送することができる。
【００６４】
本発明の態様についての動作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ、ＳｍａｌｌＴａｌｋ、Ｃ＋＋などのようなオブジェクト指向プログラミング言語、及び、「Ｃ」プログラミング言語又は同様のプログラミング言語のような従来の手続き型プログラミング言語を含む、１つ又は複数のプログラミング言語のいずれかの組み合わせで記述することができる。プログラム・コードは、完全にユーザのコンピュータ上で実行される場合もあり、一部がユーザのコンピュータ上で実行される場合もあり、独立したソフトウェア・パッケージとして実行される場合もあり、一部がユーザのコンピュータ上で実行され、一部がリモート・コンピュータ上で実行される場合もあり、又は完全にリモート・コンピュータ若しくはサーバ上で実行される場合もある。一番最後のシナリオの場合、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）若しくは広域エリア・ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを通じてユーザのコンピュータに接続される場合もあり、又は、外部のコンピュータへの接続がなされる場合もある（例えば、インターネット・サービス・プロバイダを用いたインターネットを通じて）。
【００６５】
本発明の態様は、本発明の実施形態による方法、装置（システム）及びコンピュータ・プログラムのフローチャート図及び／又はブロック図を参照して以下に説明される。フローチャート図及び／又はブロック図の各ブロック、並びに、フローチャート図及び／又はブロック図内のブロックの組み合わせは、コンピュータ・プログラム命令によって実施することができることが理解されるであろう。これらのコンピュータ・プログラム命令を、機械を製造するために、汎用コンピュータ、専用コンピュータ、又は他のプログラム可能データ処理装置のプロセッサに与えて、その結果、コンピュータ又は他のプログラム可能データ処理装置のプロセッサによって実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実施するための手段を作り出すようにさせることができる。
【００６６】
これらのコンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイスを特定の方式で機能させるように指示することができるコンピュータ可読媒体内に格納し、その結果、そのコンピュータ可読媒体内に格納された命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実施する命令を含む製造物品を生成するようにさせることもできる。
【００６７】
コンピュータ・プログラム命令をコンピュータ、他のプログラム可能データ処理装置、又は他のデバイスにロードして、一連の動作ステップをコンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上で実行させ、コンピュータ又は他のプログラム可能装置上で実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実施するためのプロセスを提供するように、コンピュータにより実行されるプロセスを生成することもできる。
【００６８】
ここで、図１に関して上述された動作環境１００において用いることができる情報処理システム６００を示すブロック図である、図６を参照する。情報処理システム６００は、本発明の１つ又は複数の実施形態を実施するように適合された、適切に構成された処理システムに基づいている。同様に、本発明の実施形態により、いずれの適切に構成された処理システムを情報処理システム６００として用いることもできる。
【００６９】
情報処理システム６００は、コンピュータ６０２を含む。コンピュータ６０２は、ローカル・キャッシュ・メモリ６０６、共有メモリ６２２、大容量記憶装置インターフェース６０８、及びネットワーク・アダプタ・ハードウェア６１０に接続されたプロセッサ６０４を有する。システム・バス６１２は、これらのシステム・コンポーネントを相互接続する。共有メモリ６２２は、一実施形態においては、複合キュー・サイズ・プロセッサ１７０、タスク分散プロセッサ１７２、及びタスク受け入れプロセッサ１７４を含む。
【００７０】
大容量記憶装置インターフェース６０８は、データ記憶装置６１４のような大容量記憶装置を、情報処理システム６００に接続するのに用いられる。データ記憶装置の１つの特定のタイプは、ＣＤ／ＤＶＤドライブのような光学ドライブであり、この光学ドライブを用いて、ＣＤ／ＤＶＤ６１６のような（これに限定されるものではない）コンピュータ可読媒体又は記憶製品にデータを格納し、そこからデータを読み取ることができる。別のタイプのデータ記憶装置は、例えばＮＴＦＳ形式のファイル・システム操作をサポートするように構成されたデータ記憶装置である。
【００７１】
共有メモリ６２２内に含まれるオペレーティング・システム（図示せず）は、Ｌｉｎｕｘ、Ｗｉｎｄｏｗｓ  ＸＰ、及びＷｉｎｄｏｗｓ  Ｓｅｒｖｅｒ  ２００３オペレーティング・システムなどの適切なマルチタスク・オペレーティング・システムである。本発明の実施形態は、他のいずれかの適切なオペレーティング・システムを使用することができる。本発明の幾つかの実施形態は、オペレーティング・システム（図示せず）のコンポーネントの命令が、情報処理システム６００内に配置されたいずれか意のプロセッサ上で実行されることを可能にするオブジェクト指向フレームワーク機構などのアーキテクチャを用いる。一実施形態におけるネットワーク・アダプタ・ハードウェア６１０は、ネットワーク・インターフェース１６０の一部であり、１つ又は複数のネットワーク６２０へのネットワーク通信インターフェースを提供する。本発明の実施形態は、現在のアナログ及び／又はデジタル技術を含むいずれかのデータ通信接続と共に、又は将来のネットワーク機構を介して働くように適合させることができる。
【００７２】
図面内のフローチャート及びブロック図は、本発明の様々な実施形態によるシステム、方法、及びコンピュータ・プログラムの可能な実装のアーキテクチャ、機能、及び動作を例証する。この点で、フローチャート又はブロック図内の各ブロックは、指定された論理機能を実装するための１つ又は複数の実行可能な命令を含むコードのモジュール、セグメント、又は部分を表すことができる。また、幾つかの代替的な実装においては、ブロック内に記載された機能は、図面内に記載された順番とは異なる順番で行なわれることがあることにも留意すべきである。例えば、逐次的に図示された２つのブロックは、実際には、実質的に同時に実行されることもあり、又は、これらのブロックは、関与する機能性に応じて、ときとして逆順で実行されることもある。ブロック図及び／又はフローチャート図の各ブロック、及びブロック図及び／又はフローチャート図内のブロックの組み合わせは、指定された機能又は行動を実行する専用ハードウェア・ベースのシステム、又は専用ハードウェアとコンピュータ命令との組み合わせによって実施できることにもまた留意される。
【００７３】
限定されない例
本発明の特定の実施形態が開示されたが、当業者であれば、本発明の範囲及び精神から逸脱することなく、特定の実施形態に変更をなし得ることを理解するであろう。従って、本発明の範囲は特定の実施形態に限定されるべきではなく、添付の特許請求の範囲は、本発明の範囲内にあるありとあらゆる適用、修正、及び実施形態を網羅することが意図される。
【図１】
0005425739.tif 000002
【図２】
0005425739.tif 000003
【図３】
0005425739.tif 000004
【図４】
0005425739.tif 000005
【図５】
0005425739.tif 000006
【図６】
0005425739.tif 000007