(57)【要約】      （修正有）【課題】システムおよび方法はコンカレントプライオリティキューをサポートする。【解決手段】コンカレントプライオリティキューは、複数のスレッドがプライオリティキューとインタラクトすることを可能にする。プライオリティキューは、シーケンサを用いて、プライオリティキューにおける１つ以上の要求を求めて競合する複数のスレッドを検出して順序付けることができる。さらに、プライオリティキューは複数のスレッド間における競合を減少させるよう動作する。【選択図】図１１
2019071108.tif 000002
【特許請求の範囲】
【請求項１】
コンカレントプライオリティキューをサポートするためのシステムであって、
１つ以上のマイクロプロセッサと、
プライオリティキューとを含み、前記プライオリティキューは、複数のスレッドが前記プライオリティキューとインタラクトすることを可能にし、前記システムはさらに、
前記１つ以上のマイクロプロセッサ上で実行されるシーケンサを含み、前記シーケンサは、前記プライオリティキューにおける１つ以上の要求を求めて競合する複数のスレッドを検出するよう動作し、
前記プライオリティキューは、前記複数のスレッド間における前記競合を減少させるよう動作する、システム。
【請求項２】
前記プライオリティキューはカレンダーリングを含み、前記カレンダーリングは、予め構成されたサービス品質（ＱｏＳ）よりも短い目標応答時間を有するさまざまな要求を格納するよう動作する、請求項１に記載のシステム。
【請求項３】
前記予め構成されたサービス品質（ＱｏＳ）は約２秒となるように規定される、請求項２に記載のシステム。
【請求項４】
前記カレンダーリングと同期して更新されるビットマップは、より高速にスキャンするために用いられる、請求項２または３に記載のシステム。
【請求項５】
前記プライオリティキューは、作業負荷が集中している場合、前記カレンダーリングについての競合を減少させるのに用いることができる盗まれた要求のリストを含み、前記盗まれた要求のリストは、同じカレンダーエントリ上にある１つ以上の要求を含む、請求項２から４のいずれかに記載のシステム。
【請求項６】
前記プライオリティキューは、協働的同時並行性をサポートするのに用いられる高速レーンを含む、請求項２から５のいずれかに記載のシステム。
【請求項７】
前記シーケンサは、前記複数のスレッドを順序付けることができるチケット機構を用いる、請求項１から６のいずれかに記載のシステム。
【請求項８】
前記チケット機構は、消費者が前記プライオリティキューにアクセスしようとするたびに増やされるリーダカウントを維持する、請求項７に記載のシステム。
【請求項９】
前記シーケンサは、競合スレッドにチケットを発行するよう動作し、前記チケットは、前記競合スレッドが前記プライオリティキューにアクセスすることを可能にする、請求項７または８に記載のシステム。
【請求項１０】
前記シーケンサは、前記プライオリティキューにおけるアウトライアリストの先入れ先出し（ＦＩＦＯ）順序を維持するよう動作する、請求項１から９のいずれかに記載のシステム。
【請求項１１】
コンカレントプライオリティキューをサポートするための方法であって、
複数のスレッドが前記コンカレントプライオリティキューとインタラクトすることを可能にするステップと、
前記プライオリティキューにおける１つ以上の要求を求めて競合する複数のスレッドをシーケンサを介して検出するステップと、
前記複数のスレッド間における前記競合を前記プライオリティキューを介して減少させ
るステップとを含む、方法。
【請求項１２】
前記プライオリティキューにカレンダーリングを含めるステップをさらに含み、前記カレンダーリングは、予め構成されたサービス品質（ＱｏＳ）よりも短い目標応答時間を有するさまざまな要求を格納するよう動作する、請求項１１に記載の方法。
【請求項１３】
前記予め構成されたサービス品質（ＱｏＳ）を約２秒となるように規定するステップをさらに含む、請求項１２に記載の方法。
【請求項１４】
より高速にスキャンするために前記カレンダーリングと同期して更新されるビットマップを用いるステップをさらに含む、請求項１２または１３に記載の方法。
【請求項１５】
作業負荷が集中している場合、前記カレンダーリングについての競合を減少させるのに用いることができる盗まれた要求のリストを前記プライオリティキューに関連付けるステップをさらに含み、前記盗まれた要求のリストは、同じカレンダーエントリ上にある１つ以上の要求を含む、請求項１２から１４のいずれかに記載の方法。
【請求項１６】
協働的同時並行性をサポートするのに用いられる前記プライオリティキューに高速レーンを含めるステップをさらに含む、請求項１２から１５のいずれかに記載の方法。
【請求項１７】
前記複数のスレッドを順序付けることができるチケット機構を、前記シーケンサを介して用いるステップをさらに含む、請求項１１から１６のいずれかに記載の方法。
【請求項１８】
消費者が前記プライオリティキューにアクセスしようとするたびに増やされるリーダカウントを前記チケット機構を介して維持するステップをさらに含む、請求項１７に記載の方法。
【請求項１９】
前記シーケンサを介して競合スレッドにチケットを発行するステップをさらに含み、前記チケットは、前記競合スレッドが前記プライオリティキューにアクセスすることを可能にする、請求項１７または１８に記載の方法。
【請求項２０】
機械読取可能な命令を含むコンピュータプログラムであって、前記機械読取可能な命令は、実行されると、システムに、請求項１１から１９のいずれかに記載の方法を実行させる、コンピュータプログラム。
【請求項２１】
請求項２０に記載のコンピュータプログラムを格納する機械読取可能な記憶媒体を含むコンピュータプログラムプロダクト。
【請求項２２】
命令が格納された非一時的な機械読取可能な記憶媒体であって、前記命令は、実行されると、システムに、
複数のスレッドがコンカレントプライオリティキューとインタラクトすることを可能にするステップと、
前記プライオリティキューにおける１つ以上の要求を求めて競合する複数のスレッドをシーケンサを介して検出するステップと、
前記複数のスレッド間における競合を前記プライオリティキューを介して減少させるステップとを実行させる、非一時的な機械読取可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
著作権表示：
この特許文献の開示の一部は、著作権保護の対象となる題材を含んでいる。著作権の所有者は、特許商標庁の包袋または記録に掲載されるように特許文献または特許情報開示を誰でも複製できることに対して異議はないが、その他の点ではすべての如何なる著作権をも保有する。
【０００２】
発明の分野：
本発明は、概して、ミドルウェアなどのコンピュータシステムおよびソフトウェアに関し、特に、ミドルウェアマシン環境においてキューをサポートするためのシステムおよび方法に関する。
【背景技術】
【０００３】
背景：
どのような大きな組織でも、その中では、長年を経て、さまざまな異なるコンピュータハードウェア、オペレーティングシステム、およびアプリケーションソフトウェアを含むＩＴインフラストラクチャが無秩序に拡大していることが多い。このようなインフラストラクチャの個々のコンポーネント自体は巧みに設計され適切に維持管理されているかもしれないが、このようなコンポーネントを相互に接続、または、リソースを共有しようとすると、それは困難な管理タスクであることが多い。近年、組織の関心は、仮想化およびストレージの集中化といった技術に向けられるようになっており、さらに近年では、共有インフラストラクチャの基礎を提供できるクラウドコンピューティングに向けられている。しかしながら、このような環境に特に適したオールインワンのプラットフォームはほとんどない。これらが、本発明の実施形態が取組もうとしている一般的な分野である。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
概要：
コンカレントプライオリティキューをサポートするためのシステムおよび方法を提供する。コンカレントプライオリティキューは、複数のスレッドがプライオリティキューとインタラクトすることを可能にする。プライオリティキューは、シーケンサを用いて、プライオリティキューにおける１つ以上の要求を求めて競合する複数のスレッドを検出して順序付けることができる。さらに、プライオリティキューは複数のスレッド間における競合を減少させるよう動作する。
【０００５】
本発明の他の目的および利点は、添付の図面に照らして読まれると、さまざまな実施形態の以下の詳細な説明から当業者にとって明らかになるであろう。
【図面の簡単な説明】
【０００６】
【図１】発明のある実施形態に従ったミドルウェアマシン環境１００の例を示す図である。
【図２】発明のある実施形態に従ったミドルウェアマシンプラットフォームまたは環境の別の例を示す図である。
【図３】発明のさまざまな実施形態に従った、ミドルウェアマシン環境において要求を処理するためにプライオリティキューを用いる例を示す図である。
【図４】ミドルウェアマシン環境においてノンブロッキングキューをサポートする例を示す図である。
【図５】発明のさまざまな実施形態に従った、コンカレントプライオリティキューをサポートする例を示す図である。
【図６】発明のさまざまな実施形態に従った、アウトライアリストのための先入れ先出し（ＦＩＦＯ：first-in-first-out）順序を保証する例を示す図である。
【図７】発明の実施形態に従った、コンカレントプライオリティキューにおけるアウトライアリストに複数の要求を追加するための例示的なインタラクティブチャートを示す図である。
【図８】発明のさまざまな実施形態に従った、コンカレントプライオリティキューのさまざまな消費者間における競合を検出する例を示す図である。
【図９】発明の実施形態に従った、競合が検出される場合における犠牲者と競合者との間のインタラクションを示すための例示的なインタラクティブチャートである。
【図１０】発明の実施形態に従った、競合が検出されない場合における犠牲者と競合者との間のインタラクションを示すための例示的なインタラクティブチャートである。
【図１１】発明の実施形態に従った、プライオリティキューにおける協働的同時並行性（cooperative concurrency）をサポートするための例示的なフローチャートを示す図である。
【発明を実施するための形態】
【０００７】
詳細な説明：
ここで、クラスタにおけるワークシェアリングの多重化をサポートすることができるシステムおよび方法を記載する。
【０００８】
図１は、発明のある実施形態に従ったミドルウェアマシン環境１００の例を示す。図１に示されるように、各ミドルウェアマシンシステム１０２は、数個のミドルウェアマシンラックコンポーネント１０４を含み、ミドルウェアマシンラックコンポーネント１０４は各々、高性能ミドルウェアマシンハードウェアノード１０６（たとえば６４ビットプロセッサ、高性能大型メモリ、ならびに冗長インフィニバンドおよびイーサネット（登録商標）ネットワーキング）と、ミドルウェアマシンソフトウェア環境１０８との組合せを含む。その結果は、数日または数カ月ではなく数分で提供することができ、要求に応じて拡大縮小できる、完全なアプリケーションサーバ環境である。ある実施形態に従うと、各ミドルウェアマシンシステムは、満杯の、２分の１の、もしくは４分の１のラックとしてまたはラックコンポーネントからなるその他の構成として準備することができ、数個のミドルウェアマシンシステムを、ここでもインフィニバンドを用いて連結することにより、より大きな環境を作ることができる。各ミドルウェアマシンソフトウェア環境に、数個のアプリケーションサーバインスタンスまたはその他のソフトウエアインスタンスを設けることができる。たとえば、図１に示されるように、アプリケーションサーバインスタンス１０９が、仮想マシン１１６と、オペレーティングシステム１２０と、仮想化層１２４と、アプリケーションサーバ層１２８（たとえば、サーブレット（Servlet）１３２、ＥＪＢ１
３４、およびグリッドリンク（GridLink）１３６それぞれのコンテナを含むウェブロジック（WebLogic））とを含み得る。別のアプリケーションサーバインスタンス１１０は、仮想マシン１１８と、オペレーティングシステム１２２と、仮想化層１２６と、データグリッド層１４０（たとえばアクティブキャッシュ１４２を含むコヒーレンス（Coherence）
）とを含み得る。インスタンスは各々、エクサロジック統合（integration）パックとい
ったミドルウェアマシン統合コンポーネント１５０を用いて、互いに通信でき、かつ、そのミドルウェアマシンハードウェアノードおよびその他のノード双方とも通信できる。ミドルウェアマシン統合コンポーネント１５０自体が、以下でさらに詳細に説明するように、インフィニバンドおよびその他の特徴に対するサポートといったいくつかの最適化特徴を提供する。
【０００９】
図２は、発明のある実施形態に従ったミドルウェアマシンプラットフォームまたは環境の別の例を示す。図２に示されるように、各アプリケーションサーバインスタンスは、ミドルウェアマシン環境内において送信側および／または受信側１６０、１６１として機能し得る。各アプリケーションサーバインスタンスは、アプリケーションサーバがインフィニバンドネットワーク１６４を介して互いに通信できるようにするマルチプレクサ１６２、１６３にも関連付けられている。図２に示される例では、アプリケーションサーバインスタンスは、ソケットダイレクトプロトコル（sockets direct protocol）１６８に関連
付けられ得るカーネルスペース（kernel space）１６５と、ユーザスペース１６７と、アプリケーションサーバ（たとえばウェブロジックスペース）１６６と、ＪＶＭ（たとえばジェイロキット／ホットスポット層）１７０と、ＷＬＳコア１７２と、サーブレットコンテナ１７４と、ＪＳＰコンパイラ１７６とを含み得る。他の例に従うと、ミドルウェアタイプのソフトウェアの他の組合せが含まれていてもよい。さまざまな実施形態に従い、マシン統合コンポーネントは、ゼロバッファコピー、分散／収集Ｉ／Ｏ、Ｔ３接続、遅延デシリアライゼーション、およびグリッドリンクデータソースなどの特徴１８０を提供することにより、共有されるインフラストラクチャの基礎を提供するとともにこのインフラストラクチャ内での性能を改善することができる。
【００１０】
プライオリティキュー
本発明のさまざまな実施形態に従うと、コンカレントシステムは、適切なサービスレベルアグリーメント（ＳＬＡ：service level agreement）をサービスに提供するために、
プライオリティキューを用いて、受信した要求に優先順位を付けることができる。
【００１１】
図３は、発明のさまざまな実施形態に従った、ミドルウェアマシン環境において要求を処理するためのプライオリティキューを用いる例を示す。図３に示されるように、１つ以上のスレッド、たとえばデシリアライズスレッドＡ３１１〜Ｂ３１２は、１つ以上の要求３２０を含む受信ネットワークトラフィック３１０をデシリアライズすることができる。デシリアライズスレッドＡ３１１〜Ｂ３１２は、たとえばadd()メソッドを用いて、プラ
イオリティキュー３０１に要求３２０を配置することができる。次いで、複数のワーカースレッド、たとえばワーカースレッドＡ３２１〜Ｃ３２３がプライオリティキュー３０１に同時にアクセスすることができ、たとえばdelete_min()メソッドを用いて、要求３２０を主張することができる。
【００１２】
プライオリティキュー３０１は、競合者間のインタラクションがシステム全体のスループットの低下をもたらすことのないように、要求の厳しい同時並行性基準を満たすよう設計することができる。加えて、プライオリティキュー３０１は、一定のメモリフットプリントを有するように実現することができ、このため、ＪＶＭは、一定サイズのプリミティブ配列上でその動作をより最適化することができ、実質的なキャッシュ効率を達成することができるようになる。
【００１３】
本発明のさまざまな実施形態に従うと、プライオリティキュー３０１は、カレンダーキューに基づいて、たとえばWebLogicアプリケーションサーバにおいて提供されるカレンダーキューに基づいて、実現することができる。カレンダーキューは、複数のバケットを備えたカレンダーを含み得る。複数のバケットの各々は、特定の短時間内に収まるイベントを格納することができる。たとえば、複数のバケットは、目標サービス時間を現在時間と比較することによって、ソートおよび配置することができる。時間差が第１のバイト内であれば、要求は、第１の２５６個のバケットのうち１つのバケットに格納することができる。特定のバケットは、要求を実行するための目標時間の実際値を用いて選択することができる。さらに、時間差が第２のバイト内であれば、要求は、第２の２５６個のバケットのうち１つのバケットに格納することができる。
【００１４】
コンシューマが、たとえばワーカースレッドＡ３２１〜Ｃ３２３のうちの１つを介して、最早の要求を実行するように構成された次の要求を除去しようとする場合、システムは、空ではない第１のバケットを探してカレンダーをスキャンすることができる。このバケットが第１の２５６個のバケットのうちの１つでない場合、カレンダーキューは、ループ・アンド・プロモート法（loop and promote method）を用いて、第１の２５６個のバケ
ットに向かって「１レベル低い」バケットに要求を移動させることができる。最終的に、いくつかの要求を第１の２５６個のバケットにおける１つ以上のバケットへとプロモートすることができ、コンシューマは要求を主張し、これに応じて次の段階に進むことができる。
【００１５】
上述のプロモーションプロセスは、システムの全体的な性能に影響を及ぼす可能性のある対数コストを含み得る。加えて、カレンダーキューについて他の設計があってもよく、その性能は、「0(1)add, O(logN) delete_min」をとるかまたは「O(logN)add, 0(1)delete_min」をとるかの選択に制限される可能性がある。
【００１６】
図４は、ミドルウェアマシン環境においてノンブロッキングキューをサポートする例を示す。図４に示されるように、複数のコンシューマ、たとえばコンシューマＡ４１１〜Ｂ４１２が、ミドルウェアマシン環境４００におけるプライオリティキュー４０１に同時にアクセスすることができる。プライオリティキュー４０１は、ノンブロッキングキューとして実現することができ、要求マネージャ４０２を介してアクセスすることができる。
【００１７】
スレッドプール４０３を管理する要求マネージャ４０２は、異なるスレッドを異なる要求に関連付けるための別個のロジックを有し得る。たとえば、要求マネージャ４０２は、ロック構造を用いて、すべてのスレッドプールメソッドコールを、同期されたステートメントでプライオリティキュー４０１、または同期されたブロック４１０、にラップすることによって、シリアライズすることができる。
【００１８】
このように、プライオリティキュー４０１上での動作はシングルスレッド設計によって制限される可能性がある。なぜなら、シリアライズがノンブロッキングプライオリティキュー４０１の外部でなされるからである。
【００１９】
コンカレントプライオリティキュー
図５は、発明のさまざまな実施形態に従ったコンカレントプライオリティキューをサポートする例を示す。図５に示されるように、複数のコンシューマ、たとえばコンシューマＡ５１１〜Ｃ５１３は、ミドルウェアマシン環境５００におけるコンカレントプライオリティキュー５０１に同時にアクセスすることができる。
【００２０】
コンカレントプライオリティキュー５０１は、受信した要求に優先順位を付けて格納することのできるカレンダー、たとえばカレンダーリング５０２を含み得る。サイズが制限されているカレンダーリング５０２は、予め構成された制限時間内の目標応答時間を有する要求を格納するように構成することができる。カレンダーリング５０２内において、要求は、要求のサービス品質（ＱｏＳ：Quality of Service）、たとえば目標サービス時間、と合致する位置にあるリングバッファに直接格納または配置することができる。
【００２１】
このため、システムは、カレンダーキューのメモリフットプリントを変更することなく、要求のためのルックアップをはるかに安価に行うことができる。さらに、システムは、Ｏ（１）動作としてカレンダーキューにエレメントを追加し続ける一方で、カレンダーキューのdelete_min動作についての対数の複雑さを緩和して、ほぼ線形のキャッシュ効率サーチにすることができる。
【００２２】
加えて、予め構成された制限時間よりも長い目標サービス時間を含む要求は、アウトライアのリスト、たとえばアウトライアリスト５０４、に追加することができる。これらの要求のスケジューリングがタイムクリティカルでない可能性があるので、システムは、ソート済みのアウトライアのリスト５０４に対してよりゆっくりと追加することを許可する。さらに、コンカレントプライオリティキュー５０１は、シーケンサ、たとえばoutliers_seqを用いて、アウトライアリストのための先入れ先出し（ＦＩＦＯ：first-in-first-out）順序を同じＱｏＳで実施することができる。
【００２３】
たとえば、カレンダーリング５０２は、２秒未満の目標応答時間（またはＱｏＳ）を有する要求を格納するように構成することができる。なぜなら、２秒を超えるＱｏＳを有する要求はまれにしかないと考えられ得るからである。さらに、２秒未満のＱｏＳを有する要求は、ＱｏＳと合致するカレンダーリング５０２に配置することができる一方で、２秒を超えるＱｏＳを有する要求はアウトライアのリスト５０４に配置することができる。
【００２４】
図４に示されるカレンダーキューとは異なり、要求マネージャ５１０は、同期されたステートメントで、すべてのコールをカレンダーキュー５０１に入れる必要はない。同期されたブロック５０６は、継続渡し５０７をサポートするものであり、コンカレントプライオリティキュー５０１の範囲内で実現することができる。コンシューマ、たとえばコンシューマＡ５１１〜Ｃ５１３は、コンカレントプライオリティキュー５０１の外部からスレッドプール５２０にアクセスする必要がないかもしれない。
【００２５】
継続渡しを用いると、システムは、カレンダーキュー５０１をノンブロッキングからブロッキングに変換することができる。継続渡し５０７は、コンシューマＡ５１１〜Ｃ５１３が、スレッドプール５２０における活動停止中のワーカーまたはスレッド５３０を管理することを可能にし、これにより、スレッドプール５２０において待機している可能性のあるスレッド５３０を再使用できるようにする。
【００２６】
加えて、コンカレントプライオリティキュー５０１は、コンカレントプライオリティキュー５０１が競合を検出することを可能にし、高速レーン５０５を用いて協働的同時並行性をサポートすることができるシーケンサ５０３を含み得る。このため、コンカレントプライオリティキュー５０１は、競合についての情報を公開するのにロックを必要とすることなく、競合を認識して適切に処理することができる。
【００２７】
アウトライアリストのためのＦＩＦＯの維持
図６は、発明のさまざまな実施形態に従った、アウトライアリストのための先入れ先出し（ＦＩＦＯ）順序を保証する例を示す。図６に示されるように、ミドルウェアマシン環境６００におけるプライオリティキュー６０１は、カレンダーリング６０２およびアウトライアリスト６０３を含み得る。
【００２８】
複数の発呼者、たとえば異なるスレッド上のデシリアライザＡ６１１〜Ｂ６１２は、プライオリティキュー６０１に同時にアクセスしようとしてもよい。プライオリティキュー６０１は、チケット機構に基づいたシーケンサ６０４を用いて、アウトライアリスト６０３のための先入れ先出し（ＦＩＦＯ）順序を保証することができる。
【００２９】
たとえば、発呼者、たとえばデシリアライザＡ６１１がアウトライアリスト６０３に要求Ａ６２１を追加することが可能となる前に、デシリアライザＡ６１１は、まず、チケットを要求するメッセージをシーケンサ６０４に送信することができる。競合がなければ、シーケンサ６０４は、デシリアライザＡ６１１に、チケット、たとえばチケットＡ６３１を発行することができる。
【００３０】
さらに、別の発呼者、たとえばデシリアライザＢ６１２は、アウトライアリスト６０３に別の要求、たとえば要求Ｂ６２２を追加しようとしてもよい。シーケンサ６０４は、デシリアライザＢ６１２からチケットについての別の要求を受取ってもよい。このとき、デシリアライザＡ６１１がアウトライアリスト６０３に要求Ａ６２１を追加しているので、シーケンサ６０４はデシリアライザＢ６１２をブロックすることができる。
【００３１】
デシリアライザＡ６１１がアウトライアリスト６０３に要求Ａ６２１を追加し終えた後、デシリアライザＡ６１１はシーケンサ６０４を進めさせることができる。次いで、シーケンサ６０４はデシリアライザＢ６１２にチケット、たとえばチケットＢ６３２を発行することができ、これにより、デシリアライザＢ６１２が要求Ａ６２１の後にアウトライアリスト６０３に要求Ｂ６２２を追加することが可能となる。
【００３２】
図７は、発明の実施形態に従った、コンカレントプライオリティキューにおけるアウトライアリストに複数の要求を追加するための例示的なインタラクティブチャートを示す。図７に示されるように、シーケンサ７１０は、プライオリティキューに同時にアクセスしようとし得る複数の発呼者またはスレッド、たとえばデシリアライザＡ７１１〜Ｂ７２２を調整することができる。
【００３３】
ステップ７０１において、デシリアライザＡ７１１は、シーケンサ７１０からチケットを獲得しようとすることができる。次いで、ステップ７０２において、シーケンサ７１０はチケット機構をチェックすることができる。これが成功した場合、プライオリティキューにアクセスしようとしている発呼者は他に存在しないこととなる。そうでない場合、デシリアライザＡ７１１は、誰かがそれを解放するまでブロックされてもよい。
【００３４】
次いで、ステップ７０３において、別の発呼者、すなわちデシリアライザＢ７１２は、デシリアライザＡ７１１がブロックされている間、アウトライアリストに要求を追加することができる。ステップ７０４において、デシリアライザＢは、シーケンサ７１０を進めさせようとすることができる。
【００３５】
ステップ７０５において、シーケンサ７１０が進むようにとのメッセージを受取った後、シーケンサ７１０はチケットを作成して、待機しているデシリアライザＡ７１１にこのチケットを発行することができる。結果的に、ステップ７０６において、デシリアライザＡ７１１はチケットを受取る。次いで、ステップ７０７において、デシリアライザＡ７１１は、引き続き、別の要求をアウトライアリストに追加することができる。
【００３６】
このように、シーケンサ７１０を用いると、同期機構またはロック構造を実現しなくても、アウトライアリストのＦＩＦＯ順序を保存することができる。
【００３７】
さまざまな消費者間における競合の検出および処理
図８は、発明のさまざまな実施形態に従った、コンカレントプライオリティキューの異なる消費者間における競合を検出する例を示す。図８に示されるように、さまざまな消費者、たとえば消費者Ａ８１１〜Ｂ８１２は、ミドルウェアマシン環境８００におけるプライオリティキュー８０１に同時にアクセスすることができる。プライオリティキュー８０１はカレンダーリング８０２、アウトライアリスト８０３および高速レーン８０４を含み得る。
【００３８】
各々の消費者は、盗まれた要求のリストを利用して、同時並行性をさらに低下させることができる。たとえば、消費者Ａ８１１は、消費者Ａ８１１にとってローカルなリストとして現れる可能性のある盗まれた要求のリスト８０７を用いることができる。加えて、消費者Ａ８１１〜Ｂ８１２の各々はシーケンサ８０５にメッセージを送信して、プライオリ
ティキュー８０１へのアクセスが許可される前にチケットを要求することができる。
【００３９】
シーケンサ８０５は、シーケンサ８０５に対してチケットを要求したリーダ総数の現在のカウントであるリーダカウント８０６を維持することができる。シーケンサ８０５は、チケット要求を受取るたびにリーダカウント８０６を増やすことができる。さらに、このリーダカウント８０６を用いて競合を検出することができる。
【００４０】
たとえば、消費者Ａ８１１は、プライオリティキュー８０１へのアクセスが許可される前に、シーケンサ８０５からチケット、たとえばチケットＡ８３１を得ることができる。次いで、別の消費者Ｂ８１２は、チケット、たとえばチケットＢ８３２についての要求をシーケンサ８０５に送信することができる。シーケンサ８０５は、消費者Ａ８１１がその動作を終了するまで、リーダカウント８０６を増やして、消費者Ｂ８１２をブロックすることができる。
【００４１】
他方で、消費者Ａ８１１は、シーケンサ８０５における現在のリーダカウント８０６（ｔ）が、それが有するチケット番号を上回ったこと（ｔ＞チケット番号）を検出した場合、消費者Ｂ８１２から競合を検出することができる。次いで、消費者Ａ８１１は、高速レーン８０４に要求を配置し、それが消費者Ｂ８１２によって消費されることを可能にすることによって、競合を減少させることができる。これは協働的同時並行性ストラテジーと称され得る。
【００４２】
こうして、シーケンサ８０５を用いると、プライオリティキューは、ロック機構または同期機構を必要とすることなく、カレンダーリング８０２に加えて高速レーン８０４および盗まれた要求のリスト８０７に消費者がアクセスすることを可能にすることによって、複数の消費者間における競合を処理するために最適化することができる。
【００４３】
図９は、発明の実施形態に従った、競合が検出される場合における犠牲者と競合者との間のインタラクションを示すための例示的なインタラクティブチャートである。図９に示されるように、シーケンサ９２０は、コンカレントプライオリティキューのさまざまな消費者間、たとえば犠牲者９２２と競合者９２１との間の競合を検出して処理するために用いることができる。
【００４４】
ステップ９０１において、競合者９２１は、チケットを待っていることを示すメッセージをシーケンサ９２０に送信することができる。犠牲者９２２が現在プライオリティキューにアクセスしているので、ステップ９０２において、シーケンサ９２０は競合者９２１をブロックし、リーダカウント、すなわちリーダ、を増やすことができる。
【００４５】
ステップ９０３〜９０５において、犠牲者９２２は、コンカレントプライオリティキューから要求をピックアップして、現在のリーダについてシーケンサ９２０をチェックすることができる（ステップ９０３〜９０４はまた、非時間的遷移９１３と称することもできる。これは以降の段落において説明する）。
【００４６】
次いで、ステップ９０６において、犠牲者９２２は、獲得したリーダカウント（ｔ）をチケット番号、すなわちそれが保持するチケット番号、と比較することができる。シーケンサ９２０が既にリーダカウントを増やしているので、犠牲者９２２は、ｔ＞チケット番号であることが判明すると、競合を検出することができる。
【００４７】
その後、ステップ９０７〜９０８において、犠牲者９２２は、当該犠牲者９２２がステップ９０９においてリーダシーケンサを進めさせようと試みる前に、高速レーンに要求を配置して、高速レーンにおける要求カウントfastLane_wを更新することができる（ステッ
プ９０７〜９０８はまた、非時間的遷移９１４と称することもできる。これは以降の段落で説明する）。
【００４８】
犠牲者９２２からメッセージを受取ってリーダシーケンサを進ませた後、ステップ９１０において、シーケンサ９２０は、引き続き、競合者９２１にチケットを発行して、競合者９２１を解放することができる。
【００４９】
最終的に、ステップ９１１において、競合者９２１はチケットを受取ることができ、ステップ９１２において、競合者９２１は、引き続き、高速レーンに対して要求を主張することができる。
【００５０】
図１０は、発明の実施形態に従った、競合が検出されない場合における犠牲者と競合者との間のインタラクションを示すための例示的なインタラクティブチャートである。図１０に示されるように、犠牲者１０２２は、プライオリティキューにアクセスするコンカレント特性のせいで、必ずしも競合者１０２１から競合を検出することができるとは限らないだろう。
【００５１】
ステップ１００１〜１００３において、犠牲者１０２２はコンカレントプライオリティキューから要求をピックアップすることができ、さらに、現在のリーダカウント、すなわちリーダ、についてシーケンサ１０２０をチェックすることができる（ステップ１００１〜１００２は非時間的遷移１０１１とも称され得る。これは以降の段落で説明する）。
【００５２】
さらに、ステップ１００４において、シーケンサ１０２０は、競合者１０２１からチケットについての要求を受取り、ステップ１００５において、シーケンサ１０２０は、リーダカウント、すなわちリーダ、を増やすことができる。
【００５３】
ステップ１００６において、犠牲者１０２２は、競合者１０２１から競合を検出することができないかもしれない。なぜなら、競合者１０２１が犠牲者１０２２に現在のリーダを返した後、シーケンサ１０２０がリーダカウントを増やしたからである。
【００５４】
ステップ１００７において、犠牲者１０２２は要求を主張し、リーダシーケンサを進ませることができ、さらに、ステップ１００８において、競合者１０２１にチケットを発行することができる。
【００５５】
次いで、ステップ１００９において、競合者１０２１はチケットを受取ることができ、ステップ１０１０において、競合者１０２１は、引き続き、プライオリティキュー、たとえば高速レーンに対して要求を主張することができる。
【００５６】
図１１は、発明の実施形態に従った、プライオリティキューにおける協働的同時並行性をサポートするための例示的なフローチャートを示す。図１１に示されるように、ステップ１１０１において、システムは、複数のスレッドがコンカレントプライオリティキューとインタラクトすることを可能にする。次いで、ステップ１１０２において、システムは、シーケンサを用いて、プライオリティキューにおける１つ以上の要求を求めて競合する複数のスレッドを検出することができる。さらに、ステップ１１０３において、システムは、プライオリティキューにおける複数のスレッド間における競合を減少させることができる。
【００５７】
時間的遷移および非時間的遷移
発明の実施形態に従うと、コンカレントプログラミングモデルは、時間的遷移および非時間的遷移などのさまざまな種類の遷移をサポートすることができる。
【００５８】
非時間的遷移ステップは、通常のプログラムオーダーステップを含んでおり、コンパイラおよびプロセッサによって自由に順序を並べ替えることができる。たとえば、図９は非時間的遷移ステップ９１３および９１４を含み、図１０は非時間的遷移ステップ１０１１を含む。これらの各々の非時間的遷移ステップ内においては、順序を並べ替えてもプログラムオーダーによって企図されるロジックが破壊されないことを確実にすることができる。
【００５９】
他方で、時間的遷移のために順序を並べ替えることに対しては制限があり、これはプログラムオーダーにも現われる可能性がある。時間的遷移は計画的な設計選択をコンカレントアルゴリズムに含み得る。時間的遷移は、コンパイラおよびプロセッサのバリアとして実現することができる。たとえば、delete_minにおける時間的遷移は、たとえばfastLane_wを読出すいかなるデータロードも、データロードたとえばfastLane_rのロードに先行できないことを示し得る。
【００６０】
時間的遷移および非時間的遷移を用いることにより、状態の変化を一定にするために、発呼者が、コンカレントアルゴリズムの他の部分の進捗状況についての情報を集めることが可能となる。
【００６１】
図９に示される例においては、犠牲者９２２がステップ９０６において競合者を検出した後、リーダは、さらに多くの競合者がいつ到着するかを変更することができる。犠牲者９２２がリーダの正確な値を認識していない可能性があっても、実際には、リーダカウントが単に増えるだけであるかもしれない。このため、高速レーンリングに要求を配置しても問題はない。
【００６２】
他方で、図１０に示される例においては、ステップ１００６において、競合者が存在しない（リーダ＝＝チケット番号）と犠牲者１０２２が判断した後、リーダの真値は、実際には、以前に返されたものよりも大きくなり得る。なぜなら、競合者１０２１が到着しているからである。このようなことが起こるのはまれであり、リーダの正確な値を決定するためのコストがこの値を知ることによる利益よりも高くなることが想定され得る。加えて、この場合、間違った推測をすることの損害は少ないと考えることができる。なぜなら、犠牲者１０２２が、引き続き、ステップ１００７においてほぼ速やかにリーダシーケンサを進ませて、これにより、いずれの競合者もかなり素早くブロック解除することができるからである。
【００６３】
さらに、図８に示される例においては、要求たとえば要求Ａ８２１を消費者Ａ８１１によって高速レーン８０４に追加することは非時間的遷移として実現することができ、消費者Ｂ８１２によって高速レーン８０４に対して要求Ａ８２１を主張することは時間的遷移として実現することができる。
【００６４】
この例においては、競合者、すなわち消費者Ｂ８１２は、要求が高速レーンリング８０４に実際に格納される前に、fastLane_wの値を観察し得る。ここでは、犠牲者、すなわち消費者Ａ８１１がリーダシーケンサを進ませた後、１つの競合者だけが高速レーン８０４にアクセスすることが可能となる。その後、高速レーン８０４にアクセスしている競合者は、観察することができる要求の数よりも多くは存在し得ない。
【００６５】
このため、たとえ高速レーン８０４fastLane_wについての要求カウントが高速レーン８０４の実際の充填部分よりも上まっていることを競合者８１１が観察し得たとしても、競合者は、各々の競合者によって一度だけ更新されるインデックス（fastLane_r）を用いる値にしかアクセスすることができない。言いかえれば、犠牲者、すなわち消費者Ａ８１１
は、解放され得る最大数の競合者を制御することによって、高速レーン８０４における要求のアクセス可能性を制御することができる。なぜなら、十分な競合者が犠牲者８１２によって解放される場合にだけ、fastLane_rの値がfastLane_wに達し得るからである。
【００６６】
いくつかの実施形態においては、上述の方法のうちの１つを実現するためのコンピュータプログラムが提供される。発明の実施形態に従うと、コンピュータプログラムは、システムに、複数のスレッドがコンカレントプライオリティキューとインタラクトすることを可能にするステップと、プライオリティキューにおける１つ以上の要求を求めて競合する複数のスレッドをシーケンサを介して検出するステップと、複数のスレッド間における競合をプライオリティキューを介して減少させるステップとを実行させる。
【００６７】
一実施形態においては、コンカレントプライオリティキューをサポートするためのシステムが提供される。システムは、複数のスレッドがコンカレントプライオリティキューとインタラクトすることを可能にするための手段と、プライオリティキューにおける１つ以上の要求を求めて競合する複数のスレッドをシーケンサを介して検出するための手段と、複数のスレッド間における競合をプライオリティキューを介して減少させるための手段とを含む。
【００６８】
一実施形態においては、システムはさらに、プライオリティキューにカレンダーリングを含めるための手段を含む。カレンダーリングは、予め構成されたサービス品質（ＱｏＳ）よりも短い目標応答時間を有するさまざまな要求を格納するよう動作する。
【００６９】
一実施形態においては、システムはさらに、予め構成されたサービス品質（ＱｏＳ）を約２秒となるように規定するための手段を含む。
【００７０】
一実施形態においては、システムはさらに、より高速にスキャンするためにカレンダーリングと同期して更新されたビットマップを用いるための手段を含む。
【００７１】
一実施形態においては、システムはさらに、作業負荷が集中している場合、カレンダーリングについての競合を減少させるのに用いることができる盗まれた要求のリストをプライオリティキューに関連付けるための手段を含む。盗まれた要求のリストは、同じカレンダーエントリ上にある１つ以上の要求を含む。
【００７２】
一実施形態においては、システムはさらに、協働的同時並行性をサポートするのに用いることができるプライオリティキューに高速レーンを含めるための手段を含む。
【００７３】
一実施形態においては、システムはさらに、複数のスレッドを順序付けることができるチケット機構をシーケンサを介して用いるための手段を含む。
【００７４】
一実施形態においては、システムはさらに、消費者がプライオリティキューにアクセスしようとするたびに増やされるリーダカウントを、チケット機構を介して、維持するための手段を含む。
【００７５】
一実施形態においては、システムはさらに、シーケンサを介してチケットを競合スレッドに発行するための手段を含む。チケットは、競合スレッドがプライオリティキューにアクセスすることを可能にする。
【００７６】
本発明は、本開示の教示に従いプログラムされた、１つ以上のプロセッサ、メモリ、および／またはコンピュータ読取可能な記録媒体を含む、従来の汎用もしくは専用デジタルコンピュータ、コンピューティングデバイス、マシン、またはマイクロプロセッサを１つ
以上用いて、適宜実現し得る。適切なソフトウェアコーディングは、熟練したプログラマが本開示の教示に基づいて容易に準備できる。これはソフトウェア技術における当業者には明らかであろう。
【００７７】
実施形態によっては、本発明は、本発明のプロセスのうちいずれかを実行するためにコンピュータをプログラムするのに使用できる命令が格納された記録媒体または（１つまたは複数の）コンピュータ読取可能な媒体であるコンピュータプログラムプロダクトを含む。この記録媒体は、フロッピー（登録商標）ディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ、および光磁気ディスクを含む、任意の種類のディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリデバイス、磁気もしくは光カード、ナノシステム（分子メモリＩＣを含む）、または、命令および／またはデータを格納するのに適した任意の種類の媒体もしくはデバイスを含み得るものの、これらに限定されない。
【００７８】
本発明に関するこれまでの記載は例示および説明を目的として提供されている。すべてを網羅するまたは本発明を開示された形態そのものに限定することは意図されていない。当業者には数多くの変更および変形が明らかであろう。実施形態は、本発明の原理およびその実際の応用を最もうまく説明することによって他の当業者が本発明のさまざまな実施形態および意図している特定の用途に適したさまざまな変形を理解できるようにするために、選択され説明されている。本発明の範囲は、添付の特許請求の範囲およびその均等物によって定められることが意図されている。
【図１】
2019071108.tif 000003
【図２】
2019071108.tif 000004
【図３】
2019071108.tif 000005
【図４】
2019071108.tif 000006
【図５】
2019071108.tif 000007
【図６】
2019071108.tif 000008
【図７】
2019071108.tif 000009
【図８】
2019071108.tif 000010
【図９】
2019071108.tif 000011
【図１０】
2019071108.tif 000012
【図１１】
2019071108.tif 000013
【手続補正書】
【提出日】平成31年2月5日(2019.2.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ミドルウェアマシン環境において複数のコンシューマから受取った複数の要求に優先順位を付けるための方法であって、前記方法は、
前記複数のコンシューマからの前記複数の要求の受信をノンブロッキングするための複数のスレッドを管理する継続渡し機能を有する同期ブロックを用いて、前記複数のコンシューマから前記複数の要求を受取ることと、
カレンダーリングバッファに、予め構成された時間よりも短い目標応答時間を有する前記複数の要求の第１のサブセットを格納することと、
アウトライアリストに、前記予め構成された時間よりも長い目標応答時間を有する前記複数の要求の第２のサブセットを格納することと、
シーケンサを用いて、前記アウトライアリストに格納された前記複数の要求の前記第２のサブセットのための先入れ先出し順序を実施することと、
前記複数のコンシューマと前記複数の要求との間の競合を減少させることとを含む、方法。
【請求項２】
前記複数の要求の前記第１のサブセットの各々に関連付けられたＱｏＳの値に応じた位置で前記カレンダーリングバッファに前記複数の要求の前記第１のサブセットの各々を格納することをさらに含む、請求項１に記載の方法。
【請求項３】
前記予め構成された時間は、２秒と規定される、請求項１または２に記載の方法。
【請求項４】
同期機構またはロック機構を必要とすることなく、前記アウトライアリストに格納された前記複数の要求の前記第２のサブセットのための前記先入れ先出し順序を実施するために、前記シーケンサにおいてチケット機構を実現することをさらに含む、請求項１〜３のいずれかに記載の方法。
【請求項５】
作業負荷が集中している場合、前記カレンダーリングについての競合を減少させるのに用いることができる盗まれた要求のリストを格納することをさらに含み、前記盗まれた要求のリストは、同じカレンダーエントリ上にある１つ以上の要求を含む、請求項１〜４のいずれかに記載の方法。
【請求項６】
協働的同時並行性をサポートする高速レーンを提供することをさらに含む、請求項１〜５のいずれかに記載の方法。
【請求項７】
前記アウトライアリストに格納された前記複数の要求の前記第２のサブセットのための先入れ先出し順序を実施するために前記シーケンサにおいてチケット機構を実現することと、
コンシューマが前記プライオリティキューにアクセスしようとするたびに増やされるリーダカウントを前記チケット機構で維持することとをさらに含む、請求項１〜３のいずれかに記載の方法。
【請求項８】
前記アウトライアリストに格納された前記複数の要求の前記第２のサブセットのための先入れ先出し順序を実施するために前記シーケンサにおいてチケット機構を実現することと、
前記複数のコンシューマのうち１のコンシューマにチケットを発行することとをさらに含み、前記チケットは前記コンシューマが前記アウトライアリストにアクセスすることを可能にする、請求項１〜３のいずれかに記載の方法。
【請求項９】
前記アウトライアリストに格納された前記複数の要求の前記第２のサブセットのための先入れ先出し順序を実施するために前記シーケンサにおいてチケット機構を実現することと、
コンシューマが前記プライオリティキューにアクセスしようとするたびに増やされるリーダカウントを前記チケット機構で維持することと、
前記リーダカウントを用いて、前記複数のコンシューマと前記複数の要求との間の競合を検出することとをさらに含む、請求項１〜３のいずれかに記載の方法。
【請求項１０】
請求項１〜９のいずれかに記載の方法をコンピュータに実行させるプログラム。
【外国語明細書】
2019071108000001.pdf