(57)【要約】  ２つのオペレーティングユニット及び前記オペレーティングユニットのそれぞれを使用する為に待機している仮想オブジェクトの為の複数の待ち行列を保持するように構成された仮想管理エンティティを有するプロセッサシステム内に記憶された２つのスレッド内に組み込まれた命令を実行し、前記仮想オブジェクトを１つの待ち行列から他の待ち行列に転送する方法を提供する。前記仮想オブジェクトのそれぞれは２つの仮想タイマーに関連付けられ、前記２つの仮想タイマーの１つは、前記仮想オブジェクトが前記待ち行列（ＴＩＱ）内に保持されている期間を測定するように構成され、前記２つの仮想タイマーの他の１つは、前記仮想オブジェクトが活動状態（ＴＴＬ）を維持する期間を提供するように構成されている。前記方法が、前記２つのスレッドに関連する前記仮想オブジェクトに関する情報を受信するステップと、各々の活動状態（ＴＴＬ）が終了した前記仮想オブジェクトに作用するステップと、前記仮想オブジェクトのそれぞれが、各々の待ち行列から出ると、前記仮想管理エンティティにより前記複数の待ち行列の他の１つに転送されるべきか決定するステップと、前記仮想オブジェクトを転送すると、前記待ち行列（ＴＩＱ）内に保持されている期間を測定するように構成された前記仮想タイマーをリセットするステップと、前記仮想オブジェクトのそれぞれに関連する前記待ち行列（ＴＩＱ）及び前記仮想オブジェクトが要求されるスレッドの数に基づいて前記仮想オブジェクトのそれぞれにアクセス時間を割り当てるステップと、を有する。【選択図】図１
2021531553.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つのオペレーティングユニット及び前記オペレーティングユニットのそれぞれを使用する為に待機している仮想オブジェクトの為の複数の待ち行列を保持するように構成された仮想管理エンティティを有するプロセッサシステム内に記憶された少なくとも２つのスレッド内に組み込まれた命令を実行する方法であって、前記仮想管理エンティティはさらに、前記仮想オブジェクトを前記複数の待ち行列の１つから前記複数の待ち行列の他の１つに転送するように構成され、
前記仮想オブジェクトのそれぞれは、前記複数の待ち行列の１つに保持されると、前記仮想オブジェクトとリンクする期間を動的にトラッキングする為に、２つの仮想タイマーに関連付けられ、前記２つの仮想タイマーの１つは、前記仮想オブジェクトが前記待ち行列（ＴＩＱ）内に保持されている期間を測定するように構成され、前記２つの仮想タイマーの他の１つは、前記仮想オブジェクトが活動状態（ＴＴＬ）を維持する期間を提供するように構成されている方法において、
前記方法が、
前記仮想管理エンティティにより、前記少なくとも２つのスレッドに関連する前記仮想オブジェクトに関する情報を受信するステップと、
各々の活動状態（ＴＴＬ）が終了した前記仮想オブジェクトに作用するステップと、
前記仮想オブジェクトのそれぞれが、各々の待ち行列から出ると、前記仮想管理エンティティにより前記複数の待ち行列の他の１つに転送されるべきか決定し、転送する場合、前記仮想オブジェクトは前記仮想管理エンティティにより、前記仮想オブジェクトのそれぞれに関連する活動状態（ＴＴＬ）の値よりも小さいが、最大のタイムアウト値を有する待ち行列に転送されるステップと、
前記仮想オブジェクトが前記待ち行列（ＴＩＱ）内に保持されている期間を測定するように構成された前記仮想タイマーをリセットするステップと、
各々の待ち行列から出る時に前記仮想オブジェクトのそれぞれにアクセス時間を割り当て、前記アクセス時間は、前記仮想オブジェクトのそれぞれに関連する前記待ち行列（ＴＩＱ）及び前記仮想オブジェクトが要求されるスレッドの数に基づいて決定されるステップと、
を有することを特徴とする方法。
【請求項２】
前記少なくとも２つのスレッドのそれぞれから受信した更新情報に基づいて、前記仮想オブジェクトのそれぞれの前記アクセス時間を更新するステップをさらに有し、前記更新情報は、前記仮想オブジェクトが各々の更新スレッドにより最後にアクセスされた時間に関する情報を提供することを特徴とする請求項１に記載の方法。
【請求項３】
前記仮想オブジェクトのそれぞれに関連する活動状態（ＴＴＬ）が、各々の待ち行列から前記仮想オブジェクトが出た時に計算されることを特徴とする請求項１に記載の方法。
【請求項４】
各々の活動状態（ＴＴＬ）が終了した前記仮想オブジェクトに作用する前記ステップは、各々の待ち行列からこれらの仮想オブジェクトを破棄することを含むことを特徴とする請求項１に記載の方法。
【請求項５】
各々の待ち行列において、各々の活動状態（ＴＴＬ）が終了した前記仮想オブジェクトに作用する前記ステップは、前記仮想オブジェクトが各々の待ち行列に入った時間に応じて、前記仮想管理エンティティにより実行されることを特徴とする請求項１に記載の方法。
【請求項６】
前記仮想管理エンティティはさらに、最小限の数の待ち行列を維持しながら、前記少なくとも２つのオペレーティングユニットを管理するように構成されていることを特徴とする請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、包括的には、コンピュータシステムの分野に関する。特に、本開示は、マルチスレッドアプリケーションを実装するシステムに関する。
【背景技術】
【０００２】
実行スレッドは、スケジューラにより独立して管理することができるプログラムされた命令の最も小さなシーケンスであり、一般的にオペレーティングシステムの一部である。スレッドの実装及びプロセスはオペレーティングシステム間で相違するが、ほとんどの場合、スレッドはプロセスの一部である。マルチスレッドは単一のプロセス内に存在することができるが、同時に実行され、メモリのようなリソースを共有し、他のプロセスはこれらのリソースを共有しない。特に、プロセスのスレッドは、その実行可能なコード及びその変数の値を常時共有するように構成される。
【０００３】
単一のプロセッサを有するシステムは、一般的にタイムスライシングによるマルチスレッドを実装し、中央処理装置（ＣＰＵ）が異なるソフトウェアスレッド間をスイッチングする。一般的に、ユーザがスレッド又はタスクが並列的に実行されていると認識するほど、頻繁にそして迅速にスイッチングが発生する。マルチプロセッサ又はマルチコアシステムにおいて、マルチスレッドは並列的に実行することができ、各プロセッサ又は各コアが同時に別のスレッドを実行する。
【０００４】
マルチスレッドは、主にマルチタスク・オペレーティングシステムにおいて使用されている。マルチスレッドが単一のプロセスのコンテキスト内に共存することをプログラミング及び実行モデルが可能にする。これらのスレッドはプロセスのリソースを共有するが、独立して実行することができる。スレッドプログラミングモデルは、並行実行の有効な抽象化をデベロッパに提供する。
【０００５】
オペレーティングシステムはスレッドを先制的に又は協調的にスケジューリングする。マルチユーザ・オペレーティングシステムでは、先制マルチスレッドがより広く使用されているアプローチである。なぜなら、コンテキストスイッチングを介する実行時間にわたってよりきめ細かい制御を有するからである。しかしながら、プログラマーにより予期されていない時点で先制スケジューリングがスレッドをスイッチングすることもあるので、それにより、ロックコンボイ(lock convoy)、優先度の逆転(priority inversion)、又は他の不要な効果の原因となる。対照的に、協調的なマルチスレッドは、スレッドが実行の制御を放棄することに依拠し、したがって、スレッドが完了するまで実行されることが保証される。このことは、協調的マルチタスク・スレッドブロックが利用可能なリソースを待つ必要がある、又は集中的な計算の間に他のスレッドが実行を制御することを防止することにより他のスレッドを資源飢餓にさせるような問題を生じさせる。
【０００６】
組込システム内のプロセッサは、リアルタイム動作により高い要求を有し、共通レジスタファイルを使用する代わりに、各スレッドに専用レジスタファイルを割り当てることによって、スレッドスイッチング時間を減少することによりマルチスレッドをサポートすることができる。
【０００７】
マルチスレッドアプリケーションは、一般的に以下の利点を有する。
・反応性：マルチスレッドは、アプリケーションが入力に応答し続けることを可能にする。１つのスレッドのプログラムにおいて、主実行スレッドブロックが時間のかかるタスクに従事している場合、アプリケーション全体がフリーズしたように見える。そのような時間のかかるタスクを主実行スレッドと同時に実行されている動作中のスレッドに移動することにより、バックグラウンドでタスクを実行しながらアプリケーションがユーザの入力に応答し続けることが可能になる。
・より速い実行：マルチスレッドプログラムのこの利点は、複数のＣＰＵを有するコンピュータシステム上で、１つ以上のマルチコアプロセッサを有するシステム上で、又はマシンのクラスタにわたって、より速く動作することを可能にする。なぜなら、プログラムのスレッドは互いに待機する必要は無いと仮定すると、プログラムのスレッドは本来、並列実行に適しているものだからである。
・より低いリソース消費：スレッドを使用することで、複数のプロセスのコピーを使用する場合に必要なリソースに比べてより少ないリソースを使用して、アプリケーションは複数の顧客に同時に供給することができる。
・より良いシステム利用：スレッドはどちらも他のスレッドがタスクを完了するまで待機することなく、１つのスレッドがより遅い媒体（例えば、外部ストレージ）からデータを取り出している間に、より速い媒体（例えば、キャッシュメモリ）内のデータをもう１つのスレッドにより取り出すことができるので、マルチスレッドを使用するファイルシステムは、例えばより高い処理能力及びより短い待ち時間を達成することができる。
・単純化された共有及び通信：プロセス間通信（ＩＰＣ）を実行する為に共有メモリメカニズム又はメッセージ転送を必要とするプロセスとは異なり、スレッドは、既に共有しているデータ、コード及びファイルを通して通信することができる。
・並列化：マルチコア又はマルチＣＰＵシステムに使用されるアプリケーションは、データ及びタスクを並列サブタスクに分割する為にマルチスレッドを使用することができ、１つのコアで同時に又はマルチコアで並列的に、スレッドの動作方法は基礎的構造に管理させる。
それでも、マルチスレッドは以下の欠点を有している。
・プロセスのスレッドクラッシュ：スレッドにより実行された不当な動作は、プロセス全体をクラッシュさせる。その結果、１つの誤ったスレッドは、アプリケーションに関連する他の全てのスレッドの処理を中断させる。
・同期：複数のスレッドは同じアドレス空間を共有するので、競争状態及び他の非直感的行動を避ける為に注意する必要がある。データが正しく操作される為に、正しい順序でデータを処理する為に複数のスレッドは調子を合わせてしばしば同期される必要がある。共有データが同時に修正される、又は修正中に読み込まれることを防止する為に、複数のスレッドには動作における相互排他性も必要である。不注意な使用は、デッドロック、ライブロック又はリソース競争の原因となる。
【０００８】
また、マルチスレッドアプリケーションの性能を妨げる障害の１つは、複数のスレッド間でデータブロック／構造を共有する必要があることである。安全な方法でデータブロック／構造を共有するには、通常、動作態様に関連する問題を解決するロックの使用が必要であるが、システム性能を実質的に劣化させてしまう。伝統的に、２つの動作、即ち、タイマーをリセットしてアイテムを待ち行列の背後に移動することから成るタイマー機構を使用することによりロックは実行される。
【０００９】
マルチスレッドを使用するシステムの性能を改善する為に、本技術分野において様々な試みが実施されてきた。
【００１０】
米国特許第６１１２２２２号には、スレッドコンピューティング環境の為にハイブリッドロック及びアンロック機能を使用することが教示されている。ハイブリッドアプローチは、１つのスレッド又はマルチスレッドが同時にリソースロックを要求するかを評価することにより、どのロック方式を採用するか決定する。１つのスレッドのみがロックを要求する場合、オペレーティングシステムのプリミティブロックプロセス又はハードウェアロックプロセスの１つを採用するリソースの所有権が直接スレッドに割り当てられる。オルタネートロックプロセスは、マルチスレッドが同時にロックを要求する場合に、リソースの所有権を得る為に使用される。
【００１１】
米国特許第７２０９９１８号には、マルチスレッド環境においてオブジェクトをロックする装置及び方法の使用が教示されている。例示されている方法は、オブジェクトに関連するルーティンの少なくとも一部を独占的に実行する為に、第１のスレッドがオブジェクトをロックすることを許可する。この方法は、オブジェクトが第２のスレッドにより所有されている場合、アトミック実行によりオブジェクトをロックして第１のスレッドにオブジェクトの所有権を割り当てることを含む。また、この方法は、オブジェクトが第１のスレッドにより所有されている場合、アトミック実行することなくオブジェクトをロックすることを含む。
【００１２】
米国特許第７７４８００１号には、スレッドが命令除去を進めることができない場合、スレッドに優先権を割り当てる為に使用される方法、装置及びシステムが開示されている。例えば、スレッドは、メモリライブロック遮断ロジック及び/又はスタベーション回避ロジックを含むマルチプロセッサシステム内の複数のアクティブなスレッドの１つである。
【００１３】
しかしながら、マルチアップデータによる待ち行列の背後へのアイテムの移動は、全ての待ち行列をロックすることを要求し、次に全てのスレッドがタイマーを更新しようと待ち行列内に待機するという結果をもたらすので、事実、システム性能に悪影響をもたらす。
【００１４】
本発明は、この問題の解決策を提供することを目的としている。
【発明の概要】
【発明が解決しようとする課題】
【００１５】
本開示は、特許請求の範囲を参照することによって要約できる。
【００１６】
本開示の目的は、ロックを使用することなくマルチスレッドに関連するタイマーを更新することを可能にするロックレスタイマーのシステム及び方法を提供することである。
【００１７】
本開示の他の目的は、アプリケーションの使用事例により、待ち行列管理戦略を調整し、それにより、最小限の数の待ち行列でタイマーの効果的な管理を可能にするシステム及び方法を提供することである。
【００１８】
本開示の他の目的は、以下の説明から明らかになる。
【課題を解決するための手段】
【００１９】
本開示の第１の実施形態によれば、少なくとも２つのオペレーティングユニット及び前記オペレーティングユニットのそれぞれを使用する為に待機している仮想オブジェクトの為の複数の待ち行列を保持するように構成された仮想管理エンティティを有するプロセッサシステム内に記憶された少なくとも２つのスレッド内に組み込まれた命令を実行する方法であって、前記仮想管理エンティティはさらに、前記仮想オブジェクトを前記複数の待ち行列の１つから前記複数の待ち行列の他の１つに転送するように構成され、前記仮想オブジェクトのそれぞれは、前記待ち行列の１つに保持されると、その仮想オブジェクトとリンクする期間を動的にトラッキングする為に、２つの仮想タイマーに関連付けられ、前記２つの仮想タイマーの１つは、前記仮想オブジェクトが前記待ち行列（ＴＩＱ）内に保持されている期間を測定するように構成され、前記２つの仮想タイマーの他の１つは、前記仮想オブジェクトが活動状態（ＴＴＬ）を維持する期間を提供するように構成されている方法において、前記方法が、前記仮想管理エンティティにより、前記少なくとも２つのスレッドに関連する前記仮想オブジェクトに関する情報を受信するステップと、各々の活動状態（ＴＴＬ）が終了した前記仮想オブジェクトに作用するステップと、前記仮想オブジェクトのそれぞれが、各々の待ち行列から出ると、前記仮想管理エンティティにより前記複数の待ち行列の他の１つに転送されるべきか決定し、転送する場合、前記仮想オブジェクトは前記仮想管理エンティティにより、前記仮想オブジェクトのそれぞれに関連する活動状態（ＴＴＬ）の値よりも小さいが、最大のタイムアウト値を有する待ち行列に転送されるステップと、前記仮想オブジェクトが前記待ち行列（ＴＩＱ）内に保持されている期間を測定するように構成された前記仮想タイマーをリセットするステップと、各々の待ち行列から出る時に前記仮想オブジェクトのそれぞれにアクセス時間を割り当て、前記アクセス時間は、前記仮想オブジェクトのそれぞれに関連する前記待ち行列（ＴＩＱ）及び前記仮想オブジェクトが要求されるスレッドの数に基づいて決定されるステップと、を有することを特徴とする方法を提供する。
【００２０】
他の実施形態によれば、各々の活動状態（ＴＴＬ）が終了した前記仮想オブジェクトに作用する前記ステップは、各々の待ち行列からこれらの仮想オブジェクトを破棄することを含む。
【００２１】
また、他の実施形態によれば、前記方法はさらに、前記少なくとも２つのスレッドのそれぞれから受信した更新情報に基づいて、前記仮想オブジェクトのそれぞれの前記アクセス時間を更新するステップを有し、これらの更新情報は、前記仮想オブジェクトが各々の更新スレッドにより最後にアクセスされた時間に関する情報を提供する。
【００２２】
さらに他の実施形態によれば、前記仮想オブジェクトのそれぞれに関連する活動状態（ＴＴＬ）が、各々の待ち行列から前記仮想オブジェクトが出た時に計算される。
【００２３】
また、他の実施形態によれば、各々の待ち行列から、各々の活動状態（ＴＴＬ）が終了した仮想オブジェクトを破棄する前記ステップは、前記仮想オブジェクトが各々の待ち行列に入った時間に応じて、前記仮想管理エンティティにより実行される。
【００２４】
さらに他の実施形態によれば、前記仮想管理エンティティはさらに、最小限の数の待ち行列を維持しながら、前記少なくとも２つのオペレーティングユニットを管理するように構成されている。
【００２５】
添付の図面は、本明細書に組み込まれ、本明細書の一部を構成するものであり、本開示の幾つかの実施形態を図示し、本明細書の記述とともに、本開示の実施形態の原理を説明するものである。
【図面の簡単な説明】
【００２６】
【図１】本発明による実施形態を例示する方法のフローチャートを示す図である。
【図２】仮想オブジェクトの待ち行列を実装する為に２の累乗戦略(a power of 2 strategy)を使用する前記仮想オブジェクトの待ち行列のスナップショットを示す実施例を示す図である。
【図３】１秒経過後の前記仮想オブジェクトの待ち行列に発生する変化を例示する図である。
【図４Ａ】図３の構成を達成する為に前記待ち行列内で前記仮想オブジェクトを移動することにより、中央仮想管理エンティティにより実施される動作を例示する図である。
【図４Ｂ】図３の構成を達成する為に、中央仮想管理エンティティにより実施される破棄動作を示す図である。
【発明を実施するための形態】
【００２７】
以下の詳細な説明における特定の詳細及び値のいくつかは、本開示の特定の例を示すものである。但し、この説明は、単なる例であり、本発明の範囲を限定することを意図するものではない。特許請求の範囲に記載された方法及びデバイスは、当技術分野において公知の他の方法を用いても実施できることは、当業者にとって明らかである。更に、ここに記載する実施形態は、異なるステップを含むが、その全てが本発明の全ての実施形態において必要とされるわけではない。本発明の範囲は、特許請求の範囲を参照することによって把握できる。
【００２８】
図１は、本発明の実施形態による方法を例示する図である。この実施例によると、システムは、プロセッサシステムに関連するマルチスレッドに組み込まれた命令を実行する為に提供され、前記システムは、少なくとも２つのオペレーティングユニットと、前記オペレーティングユニットのそれぞれのリソースを使用する為に待機している仮想オブジェクトの複数の待ち行列を保持している中央仮想管理エンティティと、を有する。前記中央仮想管理エンティティは、前記複数の待ち行列の１つから前記複数の待ち行列の他の１つに前記仮想オブジェクトを転送することを可能にするように構成されている。
【００２９】
これらの待ち行列内に含まれる前記仮想オブジェクトのそれぞれは、前記仮想オブジェクトにリンクする期間を動的にトラッキングする為の２つの仮想タイマーに関連付けられる。前記２つの仮想タイマーの１つは、前記仮想オブジェクトが前記待ち行列（ＴＩＱ）内に保持されている期間を測定するように構成され、前記２つの仮想タイマーの他の１つは、前記仮想オブジェクトが活動状態（ＴＴＬ）を維持する期間を提供するように構成されている。
【００３０】
ここに例示されている方法は、前記中央仮想管理エンティティにより、前記少なくとも２つのスレッドに関連する仮想オブジェクトに関する情報を受信することを含む（ステップ１００）。
【００３１】
次に、前記仮想管理エンティティは、各々の活動状態（ＴＴＬ）が既に終了した前記仮想オブジェクトに作用する（例えば、破棄する）ように構成されている（ステップ１１０）。
【００３２】
各々の待ち行列から出ると、前記仮想オブジェクトのそれぞれについて、前記仮想管理エンティティが前記待ち行列の他の1つに転送するべきかを決定し、前記仮想オブジェクトは前記仮想管理エンティティにより、前記仮想オブジェクトのそれぞれに関連する活動状態（ＴＴＬ）の値よりは小さいが、最大のタイムアウト値を有する待ち行列に移動される（ステップ１２０）。
【００３３】
好ましくは、待ち行列（ＴＩＱ）の値が待ち行列タイムアウトの値より小さい場合、現在の待ち行列は次のタイムスライスに達するまで分析する必要がない。
【００３４】
前記仮想オブジェクトが転送されると、前記仮想オブジェクトが前記待ち行列内に保持されている期間を測定するように構成されている前記仮想タイマーがリセットされる（ステップ１３０）。
【００３５】
その後、前記中央仮想管理エンティティ（又は他の適用エンティティ）は、前記仮想オブジェクトのそれぞれが各々の待ち行列から出ると、前記仮想オブジェクトのそれぞれにアクセス時間を割り当て、前記アクセス時間は、前記仮想オブジェクトに関連する前記待ち行列（ＴＩＱ）及び前記仮想オブジェクトが要求されるスレッドの数に基づいて決定される（ステップ１４０）。
【００３６】
活動中の前記仮想オブジェクトのそれぞれの前記アクセス時間は、（その仮想オブジェクトに適用する）前記マルチスレッドのそれぞれから受信した更新情報に基づいて、前記仮想管理エンティティにより更新され、これらの更新情報は、前記仮想オブジェクトが前記マルチスレッドの中の各々の更新スレッドにより最後にアクセスされた時間に関する情報を提供する（ステップ１５０）。
【００３７】
前記方法を示すために、前記複数の待ち行列の為に２の累乗戦略を使用すると仮定した場合（例えば、１−２−４−８−１６−３２−６４−１２８−２５６−５１２−１０２４−２０４８−４０９６−８１９２−１６３８４−３２７６８秒）、本発明により提供される解決策による１６の待ち行列を適用することにより、それぞれ１秒解消の待ち行列を実装することができ、９時間まで持続する。
【００３８】
図２は、待ち行列を実装する為に２の累乗戦略を使用するこれらの待ち行列のある時点のスナップショットを示す実施例を示す図であり、待ち行列（ＴＩＱ）は簡潔化の為に正規化されている。図２に図示されているように、２の累乗戦略を使用する待ち行列が、例えば１−２−４−８秒で、実装され、これらの待ち行列のそれぞれに備えられた前記仮想オブジェクトのそれぞれに関連する待ち行列（ＴＩＱ）及び活動状態（ＴＴＬ）が図２に示されている。
【００３９】
図２には、様々な仮想ブロックがＩＤ−１からＩＤ−１１により指定されている。同様に簡潔化の為に、前記仮想オブジェクトが前記待ち行列内に保持されている期間を測定するように構成されている前記仮想タイマーは正規化されている。
【００４０】
図３は、１秒経過後の図２に図示される前記仮想オブジェクトのそれぞれに発生する変化を例示する図である。
【００４１】
図４Ａ及び図４Ｂは、図３に示されている状態に達する為に、図２に例示される前記待ち行列に関連する前記仮想管理エンティティにより実施される動作を示している。
【００４２】
図４Ａは、特定の仮想オブジェクトの１つの待ち行列から他の待ち行列への移動を示し、実行された仮想オブジェクトの転送は、前記仮想オブジェクトのＩＤを追跡することにより観察することができ、図４Ｂは、前記中央仮想管理エンティティにより破棄された前記仮想ブロック（ＩＤ−１０、ＩＤ−１１及びＩＤ−７）を示している。
【００４３】
本発明の他の実施形態は、ここに開示した発明の明細書及び実施を考慮することによって、当業者に明らかとなる。本明細書及び実施例は、単に例示的なものであり、本発明の真の範囲及び思想は、特許請求の範囲によって示される。
【図１】
2021531553.tif 000003
【図２】
2021531553.tif 000004
【図３】
2021531553.tif 000005
【図４Ａ】
2021531553.tif 000006
【図４Ｂ】
2021531553.tif 000007
【国際調査報告】
2021531553.tif 000008
2021531553.tif 000009
2021531553.tif 000010