(57)【特許請求の範囲】
【請求項１】
ラッチを求めて潜在的に競合する複数のタスクを含むコンピュータ・システムであって、各タスクは前記タスクが前記ラッチを正常に獲得する確率を動的に推定するための確率決定コンポーネントを含み、前記タスクは推定確率が所定のしきい値未満である場合に定義済みスリープ時間の間、前記タスクをサスペンド状態にするためのサスペンド・コンポーネントを含む、コンピュータ・システム。
【請求項２】
連続的に前記タスクをサスペンド状態に入れる場合にヒューリスティックに決定した一定係数だけ前記サスペンド・コンポーネントが前記定義済みスリープ時間を増分する、請求項１に記載のコンピュータ・システム。
【請求項３】
前記タスクが前記ラッチを正常に獲得する推定確率の変化に応じて前記サスペンド・コンポーネントが前記定義済みスリープ時間を調整する、請求項１に記載のコンピュータ・システム。
【請求項４】
サンプル・ワークロード測定によって計算されたラッチ下で実行される予測数の命令に基づいて前記サスペンド・コンポーネントが前記定義済みスリープ時間を決定する、請求項１に記載のコンピュータ・システム。
【請求項５】
前記スリープ時間の上限が所定の最大値に設けられている、請求項２、３、または４に記載のコンピュータ・システム。
【請求項６】
前記ラッチを求めて競合するタスク数の逆数を取ることにより、前記タスクが前記ラッチを正常に獲得する確率を前記確率決定コンポーネントが推定する、請求項１に記載のコンピュータ・システム。
【請求項７】
マルチタスク・コンピュータ・システム内のタスクによるラッチを求める競合を管理するための方法であって、
ａ．前記タスクが前記ラッチを正常に獲得する確率を動的に推定するタスクのステップと、
ｂ．推定確率が所定のしきい値未満である場合に定義済みスリープ時間の間、それ自体をサスペンド状態にするタスクのステップと、
ｃ．前記ラッチを獲得する前記タスクの動的推定確率が所定のしきい値以上になるまで上記のステップを繰り返し、その後、前記タスクが前記ラッチを求めて競合するタスクのステップとを含む方法。
【請求項８】
連続的に前記タスクをサスペンド状態に入れる場合にヒューリスティックに決定した一定係数だけ前記定義済みスリープ時間を増分する追加ステップを含む、請求項７に記載の方法。
【請求項９】
前記タスクが前記ラッチを正常に獲得する推定確率の変化に応じて前記定義済みスリープ時間が調整される追加ステップを含む、請求項７に記載の方法。
【請求項１０】
サンプル・ワークロード測定によって計算されたラッチ下で実行される予測数の命令により前記定義済みスリープ時間を決定する追加ステップを含む、請求項７に記載の方法。
【請求項１１】
前記スリープ時間の上限を所定の最大値に設ける追加ステップを含む、請求項８に記載の方法。
【請求項１２】
前記スリープ時間の上限を所定の最大値に設ける追加ステップを含む、請求項９に記載の方法。
【請求項１３】
前記スリープ時間の上限を所定の最大値に設ける追加ステップを含む、請求項１０に記載の方法。
【請求項１４】
前記タスクが前記ラッチを正常に獲得する確率を推定する前記ステップが、前記ラッチを求めて競合するタスク数の逆数を取って前記確率を定義するステップを含む、請求項７に記載の方法。
【請求項１５】
請求項７、８、９、１０、１１、１２、１３、または１４に記載のステップを含むプロクラムを格納した、マルチタスク・マシンによって読み取り実行可能なプログラム記憶装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピューティング・システムの改良を対象とし、特に、コンピュータ・システム・リソースに関するラッチ要求を動的にスケール・バックするための改良されたシステムを対象とする。
【０００２】
【従来の技術】
マルチタスク・コンピュータ・システムでは、システム・リソースまたは重要なコード・セクションへの排他アクセスをシリアル化するためのラッチを入手するためには、通常、このようなアクセスを必要とするタスクが必要である。任意の特定の時期にラッチを保持できるのは１つのタスク（またはスレッド／プロセス）だけである。そのシステム・リソースへのアクセスをシークするその他のタスクは、そのラッチに応対することになり、そのラッチの現行ホルダによってそのラッチが解放されるまでサスペンドされる。
【０００３】
アプリケーション・ソフトウェアでラッチを実施する一般的な方法は、すべてのウェイタが、オペレーティング・システムによって提供される低レベル・プリミティブに応対するというものである。一般的なプリミティブは、（ラッチの実施例に応じて）セマフォおよびメッセージ待ち行列を含む。ラッチを要求するタスク（「リクエスタ」）は、ラッチの獲得を正常に試みた後、適切なオペレーティング・システム・リソースに応対することになる。リクエスタはオペレーティング・システム・プリミティブに応対しているので、１つのタスクがそのラッチを保持し続ける間、オペレーティング・システムはそのラッチ（実際は低レベル・プリミティブ）に応対しているリクエスタをサスペンドする。ラッチが解放されると、オペレーティング・システムにより、要求側のサスペンドされたタスクはレジューム可能になる。その結果、それぞれの要求側タスクはそのラッチを入手するために互いに競合する。明らかなように、タスクの数が増加するにつれて、ラッチが解放されたときに各リクエスタ・タスクがレジュームすることにより、オペレーティング・システム・プリミティブを獲得するために各タスクがシークするシステム・リソース（ＣＰＵ時間を含む）の利用が拡大することになる。
【０００４】
従来技術のシステムは、優先順位とディスパッチ・クラスをプログラム・スレッドに割り当てて、アプリケーション・プログラムがプログラム・スレッドの実行スケジュールを左右できるようにするものである（たとえば、米国特許第５６３０１２８号を参照）。しかし、このようなシステムでは、複数のスレッドが同じディスパッチ・クラスの同じ優先順位を有する場合に上記のオペレーティング・システム・プリミティブを求める競合が防止されない。
【０００５】
【発明が解決しようとする課題】
したがって、ラッチがリリースされ、リクエスタ・スレッドがそのラッチを入手しようとするときに、システム・リソースに対して過度の要求を行わずにタスクがラッチを要求できるようにするシステムを有することが望ましい。
【０００６】
【課題を解決するための手段】
本発明の一態様によれば、コンピュータ・システム・リソースに関するラッチ要求を動的にスケール・バックするための改良されたシステムが提供される。
【０００７】
本発明の他の態様によれば、ラッチを求めて潜在的に競合する複数のタスクを含み、各タスクはそのタスクがラッチを正常に獲得する確率を動的に推定するための確率決定コンポーネントを含み、そのタスクは推定確率が所定のしきい値未満である場合に定義済みスリープ時間の間、そのタスクをサスペンド状態にするためのサスペンド・コンポーネントを含む、コンピュータ・システムが提供される。
【０００８】
本発明の他の態様によれば、連続的にタスクをサスペンド状態に入れる場合にヒューリスティックに決定した一定係数だけサスペンド・コンポーネントが定義済みスリープ時間を増分する、上記のコンピュータ・システムが提供される。
【０００９】
本発明の他の態様によれば、そのタスクがラッチを正常に獲得する推定確率の変化に応じてサスペンド・コンポーネントが定義済みスリープ時間を調整する、上記のコンピュータ・システムが提供される。
【００１０】
本発明の他の態様によれば、サンプル・ワークロード測定によって計算されたラッチ下で実行される予測数の命令に基づいてサスペンド・コンポーネントが定義済みスリープ時間を決定する、上記のコンピュータ・システムが提供される。
【００１１】
本発明の他の態様によれば、スリープ時間の上限が所定の最大値に設けられている、上記のコンピュータ・システムが提供される。
【００１２】
本発明の他の態様によれば、ラッチを求めて競合するタスク数の逆数を取ることにより、そのタスクがラッチを正常に獲得する確率を確率決定コンポーネントが推定する、上記のコンピュータ・システムが提供される。
【００１３】
本発明の他の態様によれば、マルチタスク・コンピュータ・システム内のタスクによるラッチを求める競合を管理するための方法が提供され、その方法は、
そのタスクがラッチを正常に獲得する確率を動的に推定するタスクのステップと、
推定確率が所定のしきい値未満である場合に定義済みスリープ時間の間、それ自体をサスペンド状態にするタスクのステップと、
ラッチを獲得するタスクの動的推定確率が所定のしきい値以上になるまで上記のステップを繰り返し、その後、タスクがラッチを求めて競合するタスクのステップとを含む。
【００１４】
本発明の他の態様によれば、タスクによるラッチを求める競合を管理するための上記の方法ステップを実行するためにマシンによって実行可能な複数命令からなるプログラムを具体的に実施する、マルチタスク・マシンによって読取り可能なプログラム記憶装置が提供される。
【００１５】
本発明の利点としては、タスクの随意サスペンドによるラッチの競合の低減と、それ自体をサスペンドしなければならないかどうかならびにその長さをタスクが動的に決定することを含む。
【００１６】
【発明の実施の形態】
図１は、コンピュータ・システム・リソースに関するラッチを実施するために使用するオペレーティング・システム・プリミティブ１０を示すブロック図である。オペレーティング・システムのサスペンド機能は、オペレーティング・システム・サスペンド１２によって図示されている。図１は、タスク例１４、１６、１８、２０、２２、２４を示している。図１のタスク１４は、ラッチを実施するオペレーティング・システム・プリミティブ（通常はセマフォまたはメッセージ待ち行列）へのアクセスが許可されることによりラッチを保持しているものとして示されている。タスク１６、１８は、オペレーティング・システム・プリミティブ１０へのアクセスをシークしたがオペレーティング・システムによってサスペンドされているリクエスタ・タスクとして示され、オペレーティング・システム・サスペンド１２にあるものとして示されている。オペレーティング・システム・プリミティブ１０をリリースすることによりタスク１４がラッチをリリースすると、オペレーティング・システムは、オペレーティング・システム・プリミティブ１０を求めてともに競合している両方のタスク１６、１８をレジュームする。
【００１７】
複数のプロセッサを有するコンピュータ・システム（対称複数プロセッサまたはＳＭＰシステム）の場合、これらの新たにサスペンド解除したタスクは通常、ラッチ上で「スピン」する。したがって、タスク１６、１８のそれぞれは、そのタスクがラッチを獲得する（オペレーティング・システム・プリミティブ１０へのアクセスが許可される）かまたはそのタスクが所定のスピンしきい値に達するまで、連続的にラッチを獲得しようと試みる。このスピンしきい値は、それを過ぎるとタスクがラッチ上でのスピンを続行しなくなる時間である。その場合、タスクはオペレーティング・システム・プリミティブ１０への応対に戻り、オペレーティング・システム・サスペンド１２に入る。
【００１８】
アプリケーション内の一部のラッチは、人気のあるシステム・リソースまたはアプリケーション内の重要なコード・セクションへのアクセスをシリアル化するので、競合度が高くなる（ラッチへのアクセスをシークするタスクが多数存在する）（この説明では、コードは概念上、リソースと同様に扱われるので、重要なコード・セクションはシステム・リソースとみなすことができる）。上記の一般的なラッチ技法を使用すると、下にあるオペレーティング・システム・ラッチ・プリミティブ（セマフォまたはメッセージ待ち行列など）が大いに使用され、これは潜在的にシステム・リソースへのアクセスをシリアル化する際に重大な障害になる。
【００１９】
たとえば、システムが、平均して「ｎ」個のウェイタを有する１つのラッチを有するものと想定する。ラッチを保持するタスクがそれを解放すると、オペレーティング・システムは、ｎ個の待機タスクの動作をレジュームする作業を行い、それぞれのタスクはもう一度、ラッチへのアクセスを求めて競合する。ｎが大きくなるにつれ、ラッチが獲得または解放されるたびにラッチへのアクセスを求めて競合するために各タスクが必要とする時間は増加し、任意の１つのタスクがラッチを獲得する確率は低下する。このような悪い確率に直面しても、各タスクは、ＣＰＵタイム・スライスを実行し、使用することができる。コンピュータ・システム上には有限数のプロセッサが存在するので、ラッチを獲得しないｎ−１個のタスクに対処するためにプロセッサが実行するコンテキスト・スイッチング時に潜在的に相当なコストが発生することになる。ｎ−１個のタスクのそれぞれは、ラッチを求めて競合する（ラッチ上でスピンする）ためのＣＰＵタイム・スライスを獲得する。これらのタスクは、ラッチを獲得しない場合、それぞれオペレーティング・システム・サスペンド１２に入ることになる。というのは、これらｎ個のタスクのうち、ラッチを獲得できるのは１つのみだからである。このように共通リソースを求めて過度に競合すると、システム・パフォーマンスが劣化する。
【００２０】
好ましい実施形態によれば、複数タスクがコンピュータ・システム・リソースを求めて競合するときに行われるラッチ要求を低減するためのシステムが提供される。この好ましい実施形態では、タスクがラッチを入手する動的確率に基づいてリソースに関するラッチ要求を決定する。タスクがラッチを入手するチャンスが乏しいことがラッチ獲得確率によって示される場合、ラッチ要求はスケール・バックされる。
【００２１】
好ましい実施形態では、タスクは、ラッチを入手する確率が定義済みの値未満になると推定された場合にそのタスクがラッチを求めて競合しないことを動的に決定する。むしろ、タスクはそれ自体をサスペンドすることになる。ラッチを獲得する確率が適度に良好ではない場合にタスクが随意に実行をサスペンドすることにより、ラッチのリクエスタの一部のみが下にあるオペレーティング・システム・プリミティブに実際に応対し、ラッチが解放されるたびにこの一部のみがラッチを求めて競合することになる。
【００２２】
このような随意の競合低減は、ラッチに使用する下にあるオペレーティング・システム・プリミティブに関する競合を低減し、平均的なコンテキスト・スイッチング時間を減少し、それにより、全体的なシステム・パフォーマンスを高める働きをする。
【００２３】
ラッチのリクエスタは、スピンによりそれがラッチを求めて競合する前にその確率判断に基づいてその実行を随意にサスペンドし、その結果、ラッチを正常に獲得する適度な確率を備えていないタスクによっていかなるＣＰＵ時間も浪費されないことを保証する。
【００２４】
この手法は図１に示すことができるが、同図ではタスク１４がラッチを有し、タスク１６、１８がラッチに応対している。タスク２０、２２はラッチを入手するチャンスが十分な高さではないと決定することができ、各タスクはそれ自体をサスペンドすることになる。その結果、オペレーティング・システム・プリミティブ１０がタスク１４によってリリースされると、タスク１６、１８のみがオペレーティング・システムによってレジュームされ、タスク２０、２２はラッチを求めて競合しなくなる。その結果、４つのタスクがラッチ上でスピンする代わりに、２つのタスク１６、１８のみがＣＰＵ時間を使用してラッチ上でスピンすることになる。
【００２５】
後で分かるように、好ましい実施形態のパフォーマンスは、所与のタスクが随意にそれ自体をサスペンドするかどうかを判定するために使用する確率しきい値と、各タスクがそれ自体をサスペンドする時間の長さによって決まることになる。
【００２６】
好ましい実施形態は、タスクが随意にそれ自体をサスペンドするための長さを動的に計算することができる。好ましい実施形態が使用する方法の１つは、サスペンドの長さに関する一定係数の増加を含めることである。好ましい実施形態では、タスクがサスペンドされる長さを定義するsleep_timeパラメータを取るスリープ・メカニズムを使用する。この値は所定の予備値に設定される。その実行を随意にサスペンドするとリクエスタが連続的に決定するたびに、スリープ時間は一定係数だけ増加する。
【００２７】
好ましい実施形態では、競合中のラッチを正常に獲得する推定確率の変化に基づいてスリープ時間も調整される。連続サスペンド間でラッチを獲得する確率が低下する場合、sleep_timeの長さはより大きなものになる。好ましい実施形態では、所定の最大スリープ時間にsleep_timeの値の上限を設けることができる。予備sleep_time変数の値と、sleep_time変数を増加するために使用する一定係数は、コンピュータ・システムおよびシステムの使用法によって決まり、好ましい実施形態の様々な実施のためにヒューリスティックに決定することができる。
【００２８】
あるタスクに関するsleep_timeの長さを決定するためのもう１つの方法は、サンプル・ワークロードに基づく予測によるものである。ラッチを保持しながらアプリケーションによって実行される命令の数は、コンピュータ・システム上でサンプル・ワークロードを実行することによって決定される。この情報により、競合中のラッチを正常に獲得する確率が好都合なものになるまでにおそらく経過する必要がある時間の量になるように、sleep_timeを動的に調整することができる。この技法の有効性は、ラッチ下で計算された命令の実数がサンプル・ワークロードから外挿法によって予測された推定値とどれだけ密接に一致するかに依存する。好ましい実施形態では使用していないが、状況によっては、ランタイム時にラッチ下で実際に実行される命令の数を追跡し、この情報を使用して、サンプル・ワークロードに基づくものより良好な推定スリープ時間を生成することも可能である。しかし、通常、ラッチ・コードがパフォーマンス限界になるので、このような手法では、一般に実際の使用には高すぎる相当なオーバヘッドを必要とする。
【００２９】
このため、所与のタスクに関して正常にラッチを獲得する確率の動的計算も、可能な限り有効なものに保持しなければならない。好ましい実施形態では、単にラッチ上のウェイタの数に基づいてその値を決定することにより、確率が計算される。この値は通常、ラッチを実施するシステムで使用可能なものである。その場合、ラッチにアクセスする確率は待機タスクの数の逆数になる。しきい値として使用する確率の値は、問題のシステムおよびシステムの使用法に関してヒューリスティックに決定される。
【００３０】
ラッチを獲得する確率を動的に計算するためのこの効率的な手法の一例では、Ｐ＝１０％（ただし、Ｐは競合中のラッチを獲得する確率である）を超える確率はすべて「競合可能」状況であることがヒューリスティックに決定される。この場合、タスクが随意にそれ自体をサスペンドするかどうかを判定するための疑似コードは「if (num_waiters < 10)」として表される（ただし、num_waitersは待機タスクの数を表す変数である）。
【００３１】
好ましい実施形態を実施するための疑似コードの一部の例を以下に示す。この例では、sleep_time値決定の一定係数手法を使用している。タスクが繰り返しそれ自体をサスペンドする場合の一定係数の増加は、この例では２として定義されている。ラッチにアクセスする確率がそのタスクの連続サスペンド間で悪化するように決定される場合、その一定係数の増加は４になるように定義される。
【００３２】
0003722422.tif 000002
0003722422.tif 000003
0003722422.tif 000004
【００３３】
好ましい実施形態の代替実施例は、サンプル・ワークロードに基づく予測を使用したsleep_time変数の計算を含む。この例では、確率しきい値ｘ＝１０％であると想定している。以下の疑似コードでは、確率（Ｐ１）が受け入れられるレベルまで低下するための予測時間に基づいてsleep_timeを計算する。
【００３４】
0003722422.tif 000005
【００３５】
上記の疑似コード例から分かるように、好ましい実施形態は、タスクがラッチを獲得できる確率の効率的な決定と、ラッチを獲得する確率が低すぎる場合にタスクがそれ自体をサスペンドする時間の決定を可能にする。その結果、ラッチ要求の動的スケール・バックを可能にするシステムが得られ、それに対応してラッチの競合が低減される。
【００３６】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００３７】
（１）ラッチを求めて潜在的に競合する複数のタスクを含むコンピュータ・システムであって、各タスクは前記タスクが前記ラッチを正常に獲得する確率を動的に推定するための確率決定コンポーネントを含み、前記タスクは推定確率が所定のしきい値未満である場合に定義済みスリープ時間の間、前記タスクをサスペンド状態にするためのサスペンド・コンポーネントを含む、コンピュータ・システム。
（２）連続的に前記タスクをサスペンド状態に入れる場合にヒューリスティックに決定した一定係数だけ前記サスペンド・コンポーネントが前記定義済みスリープ時間を増分する、上記（１）に記載のコンピュータ・システム。
（３）前記タスクが前記ラッチを正常に獲得する推定確率の変化に応じて前記サスペンド・コンポーネントが前記定義済みスリープ時間を調整する、上記（１）に記載のコンピュータ・システム。
（４）サンプル・ワークロード測定によって計算されたラッチ下で実行される予測数の命令に基づいて前記サスペンド・コンポーネントが前記定義済みスリープ時間を決定する、上記（１）に記載のコンピュータ・システム。
（５）前記スリープ時間の上限が所定の最大値に設けられている、上記（２）、（３）、または（４）に記載のコンピュータ・システム。
（６）前記ラッチを求めて競合するタスク数の逆数を取ることにより、前記タスクが前記ラッチを正常に獲得する確率を前記確率決定コンポーネントが推定する、上記（１）に記載のコンピュータ・システム。
（７）マルチタスク・コンピュータ・システム内のタスクによるラッチを求める競合を管理するための方法であって、
ａ．前記タスクが前記ラッチを正常に獲得する確率を動的に推定するタスクのステップと、
ｂ．推定確率が所定のしきい値未満である場合に定義済みスリープ時間の間、それ自体をサスペンド状態にするタスクのステップと、
ｃ．前記ラッチを獲得する前記タスクの動的推定確率が所定のしきい値以上になるまで上記のステップを繰り返し、その後、前記タスクが前記ラッチを求めて競合するタスクのステップとを含む方法。
（８）連続的に前記タスクをサスペンド状態に入れる場合にヒューリスティックに決定した一定係数だけ前記定義済みスリープ時間を増分する追加ステップを含む、上記（７）に記載の方法。
（９）前記タスクが前記ラッチを正常に獲得する推定確率の変化に応じて前記定義済みスリープ時間が調整される追加ステップを含む、上記（７）に記載の方法。
（１０）サンプル・ワークロード測定によって計算されたラッチ下で実行される予測数の命令により前記定義済みスリープ時間を決定する追加ステップを含む、上記（７）に記載の方法。
（１１）前記スリープ時間の上限を所定の最大値に設ける追加ステップを含む、上記（８）に記載の方法。
（１２）前記スリープ時間の上限を所定の最大値に設ける追加ステップを含む、上記（９）に記載の方法。
（１３）前記スリープ時間の上限を所定の最大値に設ける追加ステップを含む、上記（１０）に記載の方法。
（１４）前記タスクが前記ラッチを正常に獲得する確率を推定する前記ステップが、前記ラッチを求めて競合するタスク数の逆数を取って前記確率を定義するステップを含む、上記（７）に記載の方法。
（１５）タスクによるラッチを求める競合を管理するための方法ステップを実行するためにマシンによって実行可能な複数命令からなるプログラムを具体的に実施する、マルチタスク・マシンによって読取り可能なプログラム記憶装置であって、前記方法ステップが上記（７）、（８）、（９）、（１０）、（１１）、（１２）、（１３）、または（１４）に記載の前記方法ステップを含む、プログラム記憶装置。
【図面の簡単な説明】
【図１】オペレーティング・システム・プリミティブをシークするタスク例を示すブロック図であり、本発明の好ましい実施形態の使用を示す図である。
【符号の説明】
１０  オペレーティング・システム・プリミティブ
１２  オペレーティング・システム・サスペンド
１４  タスク
１６  タスク
１８  タスク
２０  タスク
２２  タスク
２４  タスク
【図１】
0003722422.tif 000006