(57)【特許請求の範囲】
【請求項１】
メモリーと少なくとも１つのプロセッサーとを有し、前記少なくとも１つのプロセッサー上においてオペレーティング・システムを実行するコンピューターであって、前記オペレーティング・システムが、
ワーカー・スレッドのプールと、
複数のキューであって、各々、異なる優先度を有し、前記ワーカー・スレッドに割り当てられる項目を格納するための、キューと、
前記複数のキューからの項目を、制限された数のワーカー・スレッドに割り当てる同時実行コントローラーと、
を設け、
アプリケーションから要求を受け取ることに応答して、前記同時実行コントローラーは、
前記要求に対応する項目を、前記項目の優先度が指定されたキューへ追加し、
前記項目の優先度に対し、同時実行カウントを判定し、ここで、前記同時実行カウントは、前記項目が追加されたキューの優先度、およびそれよりも高い優先度を有するキューに対するワーカー・スレッドの数であり、
前記同時実行カウントが、同時実行限度を超えない場合に、前記要求に対応する項目を、前記ワーカー・スレッドへの即座割り当てのために選択し、かつ前記同時実行カウントを増やす
よう構成されている、コンピューター。
【請求項２】
請求項１に記載のコンピューターにおいて、前記オペレーティング・システムが、指定された優先度で項目を前記キューに追加することをアプリケーションに可能にするアプリケーション・プログラミング・インターフェースを有する、コンピューター。
【請求項３】
請求項２に記載のコンピューターにおいて、各ワーカー・スレッドが、当該ワーカー・
スレッドが前記同時実行限度と対比してカウントされたか否かを示す同時実行フラグを有する、コンピューター。
【請求項４】
請求項３に記載のコンピューターにおいて、各ワーカー・スレッドが、元の優先度の指示と、任意の変更された優先度の指示とを有する、コンピューター。
【請求項５】
請求項４に記載のコンピューターにおいて、前記要求に対応する項目の優先度が低く変更されたことに応答して、優先度が変更された項目に割り当てられたワーカー・スレッドは無効とされる、コンピューター。
【請求項６】
請求項１に記載のコンピューターにおいて、前記同時実行コントローラーは、項目にサービスするためにワーカー・スレッドが利用可能であるという保証を有するという印を、前記項目に付け、前記印を付けた項目が、前記キューへ追加されると、前記同時実行カウントを増やす、コンピューター。
【請求項７】
請求項１に記載のコンピューターにおいて、現在アクティブなワーカー・スレッドの全てよりも高い優先度のキューへの項目追加に応答して、前記同時実行コントローラーが、前記現在アクティブなワーカー・スレッドのうち、より低い優先度が割り当てられたワーカー・スレッドを無効にし、前記優先度が高い方の項目をワーカー・スレッドに割り当てる、コンピューター。
【請求項８】
コンピューターにより実行される方法であって、該方法は、
コンピューター上でオペレーティング・システムを実行するステップであって、前記オペレーティング・システムは、ワーカー・スレッドのプールと、前記ワーカー・スレッドのプールに関連付けられた複数のキューとを設け、各キューが異なる優先度の項目毎にある、ステップと、
項目を前記キューに追加する要求を受け取るステップであって、各項目が、優先度を有し、前記項目は、前記項目の優先度に対応する前記キューの１つに追加される、ステップと、
同時実行コントローラーにより、項目の到達時点における最も高い優先度の項目にしたがって、前記項目をワーカー・スレッドに割り当てるステップであって、項目の割り当てを同時実行限度に限定する、ステップと、を備え、
アプリケーションから要求を受け取ることに応答して、前記同時実行コントローラーは、
前記要求に対応する項目を、前記項目の優先度が指定されたキューへ追加し、
前記項目の優先度に対し、同時実行カウントを判定し、ここで、前記同時実行カウントは、前記項目が追加されたキューの優先度、およびそれよりも高い優先度を有するキューに対するワーカー・スレッドの数であり、
前記同時実行カウントが、同時実行限度を超えない場合に、前記要求に対応する項目を、ワーカー・スレッドへの即座割り当てのために選択し、かつ前記同時実行カウントを増やす
よう構成されている、
方法。
【請求項９】
請求項８に記載の方法において、各ワーカー・スレッドが、当該ワーカー・スレッドが、前記同時実行限度と対比して、カウントするか否かを示す同時実行フラグを有する、方法。
【請求項１０】
コンピューター・プログラム命令を格納するコンピューター記憶媒体であって、前記コンピューター・プログラム命令が前記コンピューター記憶媒体から読み出され、処理デバイスにより実行されると、前記処理デバイスに請求項８又は９に記載の方法を実行させる、コンピューター記憶媒体。
【発明の詳細な説明】
【背景技術】
【０００１】
[0001]  最近の計算システムでは、コンピューター・プログラムを、オペレーティング・システムによって管理された計算リソースへのアクセスを共有する多数のスレッドとして実行させるオペレーティング・システムを有することは普通である。また、オペレーティング・システム自体も、アプリケーションからオペレーティング・システムのリソースへの要求をサービスするために利用可能な多数のスレッドを有することができる。ここでは、これらのスレッドを「ワーカー・スレッド」(worker thread)と呼ぶ。
【０００２】
[0002]  リソースを求めて競合する多数のアプリケーションの複雑さを管理するには様々な方法がある。一般に、リソースにアクセスするためにスレッドを使用する要求というような、アプリケーションからのワーカー・スレッドを使用する要求を管理するためには、キューが設けられる。全ての要求が等しく扱われる場合、最初に到達した要求に最初にワーカー・スレッドを割り当てる。場合によっては、ある要求が他の要求よりも高い優先度(priority)を有することもある。このような場合、優先順位(priority level)毎に別個の要求のキューを使用し、各優先順位は、それ自体のワーカー・スレッドのプールを有する。到達時刻に基づいて、スケジューラーがスレッドをキュー内の要求に割り当て、優先度に基づいてスレッドをアクティブにし、スレッドをブロックするまたは無効にする(preempt)ことによって、多数のスレッドによるリソースへの共有アクセスを管理する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
[0003]  このようなシステムでは、各ワーカー・スレッドは固定の優先度を有し、実行中に優先度を変更することができない。そうしないと、優先度が逆転するおそれがある。また、優先順位毎にワーカー・スレッドのプールを有すると、優先順位の数がシステム・リソースによって限定される。最後に、このようなシステムは、依存性のデッドロック(dependency deadlock)が生ずる可能性がある。
【課題を解決するための手段】
【０００４】
[0004]  この摘要は、詳細な説明において以下で更に説明する概念から選択したものを、簡略化した形態で紹介するために設けられている。この摘要は、特許請求する主題の主要な特徴や必須の特徴を特定することを意図するのではなく、特許請求する主題の範囲を限定することを意図するのでもない。
【０００５】
[0005]  オペレーティング・システムは、異なる優先順位における要求の多数のキューにサービスするワーカー・スレッドのプールを設ける。同時実行コントローラー(concurrency controller)が、同時に実行する、即ち、アクティブなワーカー・スレッドの数を制限する。オペレーティング・システムは、各優先順位よりも上で同時に実行するスレッドの数を追跡し、優先度が高い方のワーカー・スレッドを優先して、優先度が低い方のワーカー・スレッドの動作を無効にする(preempt)。システムは、ワーカー・スレッドの多数のプールを有することができ、各プールはそれ自体の優先度キューと同時実行コントローラーとを有する。
【０００６】
[0006]  同時実行コントローラーは、スケジューラーを組み込む。つまり、スレッドは、直接スケジューラーに伝えることによって、その優先度を動作中に変更することができる。スレッドの優先度が低くなり現在アクティブである場合、優先度逆転が発生しないことを確保するために策が講じられる。具体的には、スケジューラーは、優先度が高い方のワーカー・スレッドを優先して、現時点で低い方の優先度であるアクティブなワーカー・スレッドを無効にすることができる。
【０００７】
[0007]  以下の説明では、その一部を形成する添付図面を参照する。図面では、実例として、本技法の具体的な実施態様例を示す。尚、本開示の範囲から逸脱することなく他の実施形態も利用でき、構造的変更が行われてもよいことは理解されよう。
【図面の簡単な説明】
【０００８】
【図１】図１は、このようなシステムのコンポーネントを実装することができるコンピューター例のブロック図である。
【図２】図２は、コンピューター・システムのためにオペレーティング・システムによって管理されるワーカー・スレッドのプールに対する異なる優先度の多数のキューの実施態様例を示す図である。
【図３】図３は、項目をキューに追加する実施態様例を示すフロー・チャートである。
【図４】図４は、ワーカー・スレッドが完了した後に項目を選択する実施態様例のフロー・チャートである。
【図５】図５は、スレッドの優先度を変更する実施態様例のフロー・チャートである。
【図６】図６は、キューから選択した項目にワーカー・スレッドを割り当てる実施態様例のフロー・チャートである。
【図７】図７は、動作中の同時実行制御の代表例(illustrative example)の図である。
【発明を実施するための形態】
【０００９】
[0015]  以下の章では、多数の優先順キュー(prioritized cue)からの項目にワーカー・スレッドを割り当ててスケジューリングするオペレーティング・システムを実現できるコンピューター・システム例について説明する。
【００１０】
[0016]  以下の説明は、このようなシステムを実現できる、適したコンピューターの端的で総合的な説明に供することを意図している。コンピューターは、種々の汎用または特殊目的計算ハードウェア構成の内任意のものにすることができる。適しているとしてよい周知のコンピューターの例には、限定ではなく、パーソナル・コンピューター、サーバー・コンピューター、ハンドヘルドまたはラップトップ・デバイス（例えば、メディア・プレーヤー、ノートブック・コンピューター、タブレット・コンピューター、セルラ・フォン、パーソナル・データー・アシスタント、音声レコーダー）、マルチプロセッサー・システム、マイクロプロセッサー・ベースのシステム、セット・トップ・ボックス、ゲーム・コンソール、プログラマブル消費者用電子機器、ネットワークＰＣ、ミニコンピューター、メインフレーム・コンピューター、以上のシステムまたはデバイスの内任意のものを含む分散型計算環境等が含まれる。
【００１１】
[0017]  図１は、適したコンピューターの一例を示す。これは、適したコンピューターの一例に過ぎず、このようなコンピューターの使用範囲や機能に何の限定も示唆することは意図していない。
【００１２】
[0018]  図１を参照すると、コンピューター例１００は、基本構成では、少なくとも１つの処理ユニット１０２とメモリー１０４とを含む。このコンピューターは、多数の処理ユニット、および／またはグラフィクス処理ユニット１２０のような、追加の共処理ユニットを含むこともできる。コンピューターの正確な構成およびタイプに応じて、メモリー１０４は、揮発性（ＲＡＭのようなメモリー）、不揮発性（ＲＯＭ、フラッシュ・メモリー等のようなメモリー）、またはこれら２つの何らかの組み合わせとすることができる。この構成は、図１において破線１０６によって例示されている。
【００１３】
[0019]  加えて、コンピューター１００は、追加の特徴／機能を有することもできる。例えば、コンピューター１００は、磁気または光ディスクあるいはテープを含むがこれらに限定されない追加のストレージ（リムーバブルおよび／または非リムーバブル）を含むこともできる。このような追加のストレージは、図１では、リムーバブル・ストレージ１０８および非リムーバブル・ストレージ１１０によって例示されている。コンピューター記憶媒体は、揮発性および不揮発性、リムーバブルおよび非リムーバブル媒体を含み、コンピューター・プログラム命令、データー構造、プログラム・モジュール、またはその他のデーターというような情報の記憶のための任意の方法または技術で実現される。メモリー１０４、リムーバブル・ストレージ１０８、および非リムーバブル・ストレージ１１０は、全てコンピューター記憶媒体の例である。コンピューター記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリーまたは他のメモリー技術、ＣＤ−ＲＯＭ、ディジタル・バーサタイル・ディスク（ＤＶＤ）または他の光ストレージ、磁気カセット、磁気テープ、磁気ディスク記憶デバイスまたは他の磁気記憶デバイス、あるいは所望の情報を格納するために使用することができ、コンピューター１００によってアクセスすることができる任意の他の媒体を含むが、これらに限定されるのではない。このようなコンピューター記憶媒体はいずれも、コンピューター１００の一部であることもできる。
【００１４】
[0020]  また、コンピューター１００は、通信接続（１つまたは複数）１１２も内蔵することができ、通信媒体を通じてデバイスが他のデバイスと通信することを可能にする。通信媒体は、通例、コンピューター・プログラム命令、データー構造、プログラム・モジュール、または他のデーターを、搬送波のような変調データー信号、または他の移送メカニズムにおいて搬送し、任意の情報配信媒体を含む。「変調データー信号」という用語は、この信号に情報をエンコードするようなやり方でその特性の１つ以上が設定または変化させられた信号を意味し、これによって信号の受信デバイスの構成または状態を変化させる。一例として、そして限定ではなく、通信媒体は、有線ネットワークまたは直接有線接続というような有線媒体と、音響、ＲＦ、赤外線、および他のワイヤレス媒体というようなワイヤレス媒体とを含む。通信接続１１２は、通信媒体とインターフェースして、ネットワーク・インターフェースのような通信媒体を介してデーターを送信し、通信媒体からデーターを受信するデバイスである。
【００１５】
[0021]  コンピューター１００は、キーボード、マウス、ペン、カメラ、タッチ入力デバイス等のような、種々の入力デバイス（１つまたは複数）１１４を有することができる。ディスプレイ、スピーカー、プリンター等のような出力デバイス（１つまたは複数）１１６も含むことができる。これらのデバイスの全ては当技術分野では周知であり、ここで長々と論ずる必要はない。種々の入力および出力デバイスは、自然ユーザ・インターフェース（ＮＵＩ）を実現することができる。ＮＵＩとは、マウス、キーボード、リモコン等のような入力デバイスによって強制される人工的な制約を受けずに、「自然な」やり方でユーザがデバイスと対話処理することを可能にする任意のインターフェース技術である。
【００１６】
[0022]  ＮＵＩ方法の例には、音声認識、タッチおよびスタイラス認識、画面上および画面近傍の双方におけるジェスチャー認識、エアー・エスチャー、頭部および眼球追跡、音声および会話(voice and speech)、視覚、タッチ、ジェスチャー、および機械インテリジェンスに頼るものを含み、タッチ感応ディスプレイ、音声および会話認識、意図および目標理解、深度カメラ（立体視カメラ・システム、赤外線カメラ・システム、および他のカメラ・システム、ならびにこれらの組み合わせのようなカメラ）を使用する動きジェスチャー検出、加速度計／ジャイロスコープを使用する動きジェスチャー検出、顔認識、３Ｄディスプレイ、頭部、眼球、ならびに凝視追跡、没入拡張現実、および仮想現実システムといった、全て更に自然なインターフェースを設けるものの使用、ならびに電界検知電極を使用して脳の活動を検知する技術（ＥＥＧおよび関連方法）を含むことができる。
【００１７】
[0023]  コンピューター上で動作するこのシステムの各コンポーネントは、一般に、１つ以上のコンピューター・プログラムのような、ソフトウェアによって実現され、コンピューターによって処理される、プログラム・モジュールのような、コンピューター実行可能命令および／またはコンピューター解釈命令を含む。一般に、プログラム・モジュールは、ルーチン、プログラム、オブジェクト、コンポーネント、データー構造等を含み、処理ユニットによって処理されると、この処理ユニットに、特定のタスクを実行するように、または特定の抽象データー型を実装するように命令する。このコンピューター・システムは、分散型計算環境においても実現することができ、この場合、タスクは、通信ネットワークを通じてリンクされたリモート処理デバイスによって実行される。分散型計算環境では、プログラム・モジュールは、メモリー記憶デバイスを含むローカルおよびリモート双方のコンピューター記憶媒体に配置することもできる。
【００１８】
[0024]  あるいはまたは加えて、ここで説明する機能は、少なくとも部分的に、１つ以上のハードウェア論理コンポーネントによって実行することもできる。例えば、そして限定ではなく、使用することができるハードウェア論理コンポーネントの実例的タイプには、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、プログラム特定集積回路（ＡＳＩＣ）、プログラム特定標準製品（ＡＳＳＰ）、システム・オン・チップ・システム（ＳＯＣ）、複合プログラマブル論理デバイス（ＣＰＬＤ）等が含まれる。
【００１９】
[0025]  以上、コンピューターについて説明したが、オペレーティング・システムとは、他のアプリケーションによるコンピューターのリソースへのアクセスを管理するコンピューター上で実行されるコンピューター・プログラムである。オペレーティング・システムがこのようなリソースにアクセスを与える１つの方法は、図２に示すような、ワーカー・スレッド２０２のプール２００によるものである。ワーカー・スレッド２０２は、オペレーティング・システムのリソースにアクセスするために呼び出すことができるコンピューター・プログラムのインスタンスである。このようなリソースは、入力デバイス、出力デバイス、記憶デバイス、プロセッサー時間等を含むことができるが、これらに限定されるのではない。
【００２０】
[0026]  アプリケーションは、オペレーティング・システムのアプリケーション・プログラミング・インターフェースを使用して、このようなプールを要求する、プールによって処理される作業項目を指定する、およびプールによって処理される作業項目の優先度を変更するというような、しかしこれらには限定されない、このようなプールに関係する種々のタスクを実行する。
【００２１】
[0027]  一実施態様では、利用可能なワーカー・スレッドのプールは、後入れ先出し（ＬＩＦＯ）キュー、またはスタックを使用して管理される。このような実施態様を使用することによって、既に最少時間量だけ待ったスレッドに最初に作業を割り当て、このスレッドに関係するデーター構造に対するキャッシュ・ヒットの可能性(likelihood)を最適化する。
【００２２】
[0028]  このようなワーカー・スレッドのプールの使用を管理するために、プールには、１組の項目のキュー２０６が関連付けられている。キューにおける各項目は、ワーカー・スレッドによって作業を実行することを求めるアプリケーションからの要求を表す。各キューには優先順位が関連付けられており、各優先順位にはキューが関連付けられている。異なるキューは、異なる優先順位を有する。一実施態様例では、キュー２０６毎に、または優先順位毎に、本システムは、キューと同じ優先順位にある項目に割り当てられたワーカー・スレッドの数を示すスレッド・カウント２０８を維持する。キューは、種々の方法で実施することができるが、到達時刻が早い要求程先に処理させるために、各キューは先入れ先出し（ＦＩＦＯ）キューの形態として実施される。
【００２３】
[0029]  以下で更に詳しく説明するが、プールのための同時実行コントローラー２２０が、同時にアクティブなワーカー・スレッドの数を制限しつつ、キューにおける項目をワーカー・スレッドに割り当てる。この機能を実行するために、同時実行コントローラーは、同時にアクティブになることができる、即ち、オペレーティング・システムのリソースにアクセスすることができるワーカー・スレッドの数の限度２２２を維持する。同時実行コントローラーは、アクティブなワーカー・スレッドの数が同時実行限度を超過しないことを確保する。一例として、オペレーティング・システムは、限度を超えた数の作業中スレッドが中央処理ユニットに申し込まないように、プロセッサーの数に基づいて同時実行限度を設定することができる。この例では、処理の「バッチ」モードを実施し、ワーカー・スレッドは、システムにおける他のスレッドと時間多重化されるのではなく、完了まで実行する。
【００２４】
[0030]  各ワーカー・スレッドは、それが項目に割り当てられた時点におけるその優先度２１０を示すデーター、スレッドの優先度を変更できる場合における任意の変更優先度２１２、およびスレッド優先度を変更できる場合に使用するために、同時実行限度と比較して、このスレッドを宛てるか(charge)否かを示す同時実行フラグ２１４を含む。ブロックされたスレッドはいずれも、その優先順位に対しては、同時実行カウンターに入れられない(charge)。無効にされたスレッドは、その優先順位に対して、スレッド・カウンターまたは同時実行カウンターに入れられたまま残る。
【００２５】
[0031]  以上で説明した構造を想定すると、同時実行コントローラーは、同時実行限度を維持しつつ、ワーカー・スレッドに対する新しい要求各々の割り当てを管理することができる。また、同時実行カウンターは、アクティブなワーカー・スレッドによるシステム・リソースへの同時アクセスを管理するスケジューラーも統合する。変更優先度２１２および同時実行フラグ２１４を示すスレッド毎に追加のデーターを使用して、同時実行コントローラーは、スレッドの優先度が変化するに連れて、アクティブなワーカー・スレッドのスケジューリングを管理することができる。
【００２６】
[0032]  新たな要求をキューに追加し、項目およびスレッドの優先度を変更し、優先順キューにおける項目にワーカー・スレッドを割り当てることを管理する同時実行コントローラーの実施態様例について、これより図３〜図６と関連付けて説明する。
【００２７】
[0033]  図３において、これより、同時実行コントローラーの実施態様例について、ワーカー・スレッドのプールに対する優先順キュー(prioritized queue)に項目を追加する動作と関連付けて説明する。この説明では、ワーカー・スレッドのプールが既に作られており、このプールについての情報はアプリケーションに供給されているので、アプリケーションはアプリケーション・プログラミング・インターフェースを使用してこのプールにアクセスできることを想定する。アプリケーションがプールにアクセスできるようになった後、それが要求することができるコマンドの内の１つは、プールにおけるワーカー・スレッドが、ある指定された作業を指定された優先順位で実行することを求める要求を提出するためのコマンドである。優先順位の指定は、コンテキストから、例えば、アプリケーションの優先順位、またはリソース要求の性質から推論することができ、あるいはアプリケーションによって指定することができる。
【００２８】
[0034]  アプリケーションがこのような要求を提出した後、オペレーティング・システムはこの要求およびその優先順位を受ける（３００）。要求は、指定された優先順位のキューに入れられる（３０２）。
【００２９】
[0035]  次に、この要求にサービスできるか否か判定する。新たな要求が、そのキューにおいて次に未割り当ての項目でない場合、同時実行限度内でキューにおける直前の項目（１つまたは複数）が完了するまで、これはサービスされない。同時実行コントローラーは、新たな要求の優先順位に対して、同時実行カウントを判定する（３０６）。この同時実行カウントは、要求が追加されたキューの優先順位、およびそれより高い優先順位におけるアクティブなワーカー・スレッドの数である。
【００３０】
[0036]  例えば、優先順位５に２つのワーカー・スレッドがあり、優先順位４に１つのワーカー・スレッドがある場合、優先順位４に対する同時カウントは３であり、優先順位５に対する同時実行カウントは２となる。
【００３１】
[0037]  新たな項目の優先度に対する同時実行カウントが同時実行限度を超えたと３０８において判定された場合、新たな項目は単にキューに追加される（３１０）だけであり、そうでない場合、ワーカー・スレッドへの即座割り当てのために選択される（３１２）。項目のワーカー・スレッドへの割り当てについては、図６と関連付けて更に詳しく説明する。その優先順位におけるワーカー・スレッドのカウント（例えば、図２における２０８）は、項目がワーカー・スレッドに割り当てられるとき、ワーカー・スレッドが完了したとき、ワーカー・スレッドがブロックされたとき、ワーカー・スレッドの優先順位が変更したときに更新される。
【００３２】
[0038]  図４を参照すると、同時実行コントローラーが、優先順キューからの項目にワーカー・スレッドを割り当てることができる別の時点は、他のワーカー・スレッドが完了したときである。同時実行コントローラーは、ワーカー・スレッドが完了したという指示を受ける（４００）。このワーカー・スレッドの優先順位に対するスレッド・カウントを判定することができる（４０２）。優先順位に対する同時実行カウントが同時実行限度未満である限り、同時実行コントローラーは、最高の優先度から最初に、あらゆるインアクティブなスレッドおよび項目のキューにわたって繰り返し（４０４）、インアクティブなスレッドまたはそのキューにおける少なくとも１つの項目によって、最高の優先順位を識別する。同時実行コントローラーは、２番目に高い優先度の項目を選択する（４０６）。この項目がキュー内にある場合、これにワーカー・スレッドが割り当てられ、このワーカー・スレッドをアクティブにする。この項目には既にワーカー・スレッドが割り当てられている場合、このワーカー・スレッドをアクティブにする。同じ優先順位でキューに入れられた項目全体に、インアクティブなスレッドが選択される。つまり、無効にされたスレッドがスケジューリングされるのは、同時実行限度に未だ達しておらず、それよりも高い優先度のスレッドを実行することができず、更に等しい優先度のスレッドがそのスレッドの前に存在しないときである。つまり、スレッドが無効にされている間、キューは、無効にされたスレッドと同じ優先順位以下のワーカー・スレッドに対する割り当てのためには、いずれの項目も放出することはできない。項目のワーカー・スレッドへの割り当てについては、図６と関連付けて更に詳しく説明する。
【００３３】
[0039]  これより図５を参照すると、キューに入れられた項目およびワーカー・スレッドに影響を及ぼす他のイベントは、項目またはワーカー・スレッドの優先度が変化するときである。例えば、アプリケーションが要求の優先度を変更しようとする可能性があり、これは、キューにおける項目を変更すること、または項目が割り当てられるワーカー・スレッドの優先度を変更することを伴うことができる。このような変更は、同時実行コントローラーを介して実行される。同時実行コントローラーはスケジューラーを統合するので、ワーカー・スレッドの優先度はこのスケジューラーによって直接変更される。キューにおける項目の優先度が変化するとき、これは、その元の優先順位のキューから除去され、その新しい優先順位のキューに追加される。項目またはワーカー・スレッドの優先度が高くなる場合、システムに対するその影響は最少である。キューにおける項目またはワーカー・スレッドの優先度を単に変更するだけで済ますことができる。項目を低い方の優先度のキューから除去し、他の高い方の優先度のキューに入れることができ、ワーカー・スレッドの優先度は、スケジューラーにおいて更に高く変更することができる。
【００３４】
[0040]  しかしながら、ある項目が既にワーカー・スレッドに割り当てられており、その優先度が低くなる場合、優先度の逆転が起こるおそれがあり、優先度が低い方のスレッドが、優先度が高い方のキューから作業項目に割り当てられた優先度が高い方のスレッドがしかるべく実行するのを妨げる。具体的には、優先度の逆転が起こるのは、優先度が低い方のスレッドが、例えば、中間の優先度の更に他のスレッドによって、実行するのを妨げられ、そして優先度が高い方のスレッドが、優先度が低い方のスレッドのために、実行するのを妨げられる場合である。
【００３５】
[0041]  優先度変更を管理する実施態様例について、これより図５において説明する。優先度の逆転が生ずる結果となる可能性がある条件を想定して、同時実行コントローラーは、ある項目の優先順位が変化したことの指示を受ける（５００）。例えば、アプリケーション・プログラミング・インターフェースを介して、アプリケーションが同時実行コントローラーに優先度の変更を伝えることができる。項目が既にワーカー・スレッドに割り当てられている場合、即ち、項目が未だキュー内にあると５０２において判定された場合、この項目を新たな優先順位のキューに整列させ（５０６）、新たな要求として扱うことができる（図３参照）。この項目が既にワーカー・スレッドに割り当てられており、しかも新たな優先度の方が高いと５０４において判定された場合、ワーカー・スレッドの優先度をスケジューラーにおいて単に変更することができる。優先順位毎のスレッド・カウントおよび同時実行カウントを更新することができる。それ以外の場合、優先度が低下しており、この項目が既にワーカー・スレッドに割り当てられている場合、この時点で優先度が低い方の要求を無効にし、優先度が高い方のスレッドをアクティブにさせるために追加の処置を講ずる。これは、優先度が高い方のキューからの要求をワーカー・スレッドに割り当てることを含むことができる。
【００３６】
[0042]  優先度が高い方の要求をワーカー・スレッドに割り当てる、または優先度が高い方のスレッドをアクティブにさせるために、同時実行コントローラーは最初にキューをロックして（５０８）、干渉なく変更を行うことを可能にする。優先度が変更された項目に割り当てられたワーカー・スレッドを無効にする（５１０）。直前の優先順位に対するスレッド・カウント、および対応する同時実行カウントを減らす。新たな優先順位に対するスレッド・カウントおよび同時実行カウントを増やす。スレッドの優先度を新たな優先順位に設定する（５１２）。次いで、同時実行コントローラーは、優先度が高い方のスレッドをアクティブにするか、または未だワーカー・スレッドが割り当てられていない項目を選択することによって、優先度が次に高い項目を選択する（５１４）。このような割り当てについては、図６と関連付けて以下で更に詳しく説明する。次に高い優先度の項目に対するワーカー・スレッドがアクティブになった後、キュー・データーを更新し、キューに対するロックを解除することができる（５１６）。
【００３７】
[0043]  先に注記したように、項目をワーカー・スレッドに割り当てることができるのは、それがキューにおいて２番目に優先度が高い項目であり、その優先順位に対する同時実行カウントが現在の同時実行限度を超えていない場合である。この割り当ては、例えば、項目がキューに追加されるとき、ワーカー・スレッドが項目を完了したとき、そしてワーカー・スレッドの優先度が変更するときに行うことができる。
【００３８】
[0044]  項目をワーカー・スレッドに割り当てる実施態様例について、図６と関連付けてこれより説明する。
[0045]  同時実行コントローラーは、ワーカー・スレッドに割り当てられるべき、次の選択項目の指示を受ける（６００）。このステップは、同時実行コントローラーが次の項目を選択する場合、前述と同じステップとすることができる。次いで、６０２において、ワーカー・スレッドがプールから入手可能であるか否か判定を行う。ある場合には、他のワーカー・スレッドが完了した後にコントローラーが項目を選択するときのように、ワーカー・スレッドが入手可能であることが予測される。他の場合には、現在の項目よりも優先度が低い１つ以上のワーカー・スレッドがある場合もあり、リソースが利用可能でない場合、その内の１つが無効にされる。ワーカー・スレッドが利用可能である場合、それを現在の項目に割り当てる（６０４）。ワーカー・スレッドが利用可能でない場合、優先度が低い方のワーカー・スレッドを選択し、無効にする（６０６）。次いで、現在の項目を、今利用可能なワーカー・スレッドに割り当てる（６０４）。ある項目があるワーカー・スレッドに割り当てられるとき、このスレッドに、同時実行限度に寄与するという印を付けることができ（６０８）、その優先順位に対するスレッド・カウントを増やすことができる。
【００３９】
[0046]  ワーカー・スレッドが割り当てられるとき、それが割り当てられる項目の優先度が与えられる。先に注記したように、この優先度を変更するとき、同時実行コントローラーは、スケジューラーが同時実行コントローラーと統合されているというために、優先度がスケジューリング動作の一部として設定されるように、この変更を管理することができ、このため、スケジューラーにはいずれの優先度の変更も直接伝えられる。
【００４０】
[0047]  優先順キューからの項目にワーカー・スレッドを割り当てることにより、同時実行コントローラー内に存在するスケジューラーは、アクティブなワーカー・スレッドの同時動作をスケジューリングすることができる。
【００４１】
[0048]  このような実施態様では、ワーカー・スレッドの１つのプールを、多数の異なる優先度の作業項目を処理するために割り当てることができる。同時実行コントローラーは、最後に受けた、優先度が最も高い項目を最初にワーカー・スレッドに割り当てることを確保することができる。更に、スレッドおよび／またはキューにおける項目の優先度は、動作の間に変更することができ、同時実行コントローラー内に統合されたスケジューラーは、優先度の逆転の可能性を減らすために、ワーカー・スレッドの割り当てを管理することができる。
【００４２】
[0049]  動作中におけるこのようなシステムの実証例を図７に示す。図７において、ワーカー・スレッドのプール７００、スレッド・カウント７０４を有する優先度キュー７０２、および同時実行限度（「２」）が示されている。優先度キューの各々は、優先度、この例では、それぞれ、０、４、１０、１５、および３１を有する。キューに入れられようとしている作業項目のシーケンスが、７０４において示されている。「Ａ」において示すように、全てのキューは空である。次に、「Ｂ」において示すように、優先度１０のワーク項目が、優先度１０のキューに追加される。この作業項目は、優先度１０のワーカー・スレッドに割り当てられ、優先度１０のキューに対するスレッド・カウントが増やされる。「Ｃ」において示すように、優先度１０の第２作業項目が、優先度１０のキューに追加される。この作業項目は、優先度１０のワーカー・スレッドに割り当てられ、優先度１０のキューに対するスレッド・カウントが「２」に増やされる。「Ｄ」において示すように、次の項目は優先度４を有し、優先度４のキューに追加される。同時実行限度は「２」であり、４よりも高い優先度を有する全てのキューに対するスレッド・カウンターは既に「２」であるので（優先度１０の項目が２つあるため）、この項目にはワーカー・スレッドが割り当てられない。次に、「Ｅ」に示すように、優先度１５の作業項目がその対応するキューに追加される。優先順位１５以上のスレッド・カウント全ての総和は、同時実行限度未満である。つまり、この項目には直ちにワーカー・スレッドが割り当てられ、そのスレッドは優先度１５を有するように設定される。機械が利用可能な計算資源を２つしか有していない場合、グローバル・スケジューラーは、優先度１５のスレッドを実行させるために、優先度１０で実行するスレッドの内１つを無効にする。
【００４３】
[0050]  また、ワーカー・スレッドが保証される整列(queuing)の実施態様を設けることもできる。これは、作業項目がキューに入れられる時点において、作業項目にサービスするためにワーカー・スレッドが利用可能であることを確保する。保証を行うことを可能にする１つの条件は、現在優先順キューにおいて新たな項目の前にある作業項目の数よりも、待機中の作業スレッドの数が多いことである。ある項目がキューに入れられた後に、優先度がもっと高い項目が到達する可能性があるので、このような状況を考慮するためのメカニズムが設けられる。一実施態様では、保証を有する各作業項目に印を付ける。保証付きで項目がキューに追加されるとき、カウンターが増やされ、その項目にワーカー・スレッドが割り当てられるとき、カウンターは減らされる。優先度が高い新たな項目がキューに追加されるとき、それよりも優先度が低いが保証を有する項目がある場合、ワーカー・スレッドは割り当てられない。このような実施態様は、大きな負荷を受ける可能性があるシステムでは有用であり、こうしなければ実行を保証するために専用スレッドを供給する際に使用されるワーカー・スレッド・ロジックを複製するのを排除することができる。
【００４４】
[0051]  以上、実施態様例および異形について説明したが、本明細書において説明した代替実施態様の内任意のものまたは全てが、追加の混合実施態様を形成するために望まれる任意の組み合わせにおいて使用されてもよいことは明らかなはずである。尚、添付した特許請求の範囲において定められる主題は、以上で説明した具体的な実施態様に必ずしも限定される訳ではないことは理解されてしかるべきである。以上で説明した具体的な実施態様は、例として開示されたに過ぎない。
【図１】
0006320520.tif 000002
【図２】
0006320520.tif 000003
【図３】
0006320520.tif 000004
【図４】
0006320520.tif 000005
【図５】
0006320520.tif 000006
【図６】
0006320520.tif 000007
【図７Ａ】
0006320520.tif 000008
【図７Ｂ】
0006320520.tif 000009
【図７Ｃ】
0006320520.tif 000010
【図７Ｄ】
0006320520.tif 000011
【図７Ｅ】
0006320520.tif 000012