(57)【要約】      （修正有）【課題】プログラムを逐次実行とするためのオーバヘッドの削減と、オブジェクトが更新されていなければプログラムを並列実行とすることによるオーバーヘッドの削減が可能となる。【解決手段】クリティカルセクションの適用対象となるデータに対して、同期更新が行われたか否かを表す同期参照コードを付与し、同期更新を行った時点で当該コードを設定する。本発明では、クリティカルセクション内の文を実行後、データの同期更新が行われたか否かを確認する。同期参照を行うスレッドで、参照を行った後で同期更新が行われたか否かを確認し、更新の正当性を確認する。同期更新が為されていなければクリティカルセクションの実行を完了する。これによりクリティカルセクションの同時実行とオーバヘッドの削減を行い、同期更新がされている場合には、通常の排他制御を行う。【選択図】図１
2006185232.tif 000002
【特許請求の範囲】
【請求項１】
複数のプログラムを並列的に実行する機能、当該複数のプログラムが共有可能な記憶空間、及び、共有に係る記憶空間に対し１のプログラムが実行されるとき他のプログラムの実行を排除する機能を備えたコンピュータシステムにおける、複数のプログラムの実行方法において、
１のプログラムが参照する前記記憶空間におけるデータに、他のプログラムが当該データを更新したことを示す領域を設け、
１のプログラムが、前記データの第１の参照を行い、前記更新したことを示す領域の第２の参照を行い、第２の参照の結果、
当該領域が更新を意味しないとき、第１の参照を完了させ、
当該領域が更新を意味するとき、１のプログラムの実行を排除して他のプログラムが実行される、複数のプログラムの実行方法。
【請求項２】
複数のプログラムを並列的に実行する機能、当該複数のプログラムが共有可能な記憶空間、及び、共有に係る記憶空間に対し１のプログラムが実行されるとき他のプログラムの実行を排除する機能を備えたコンピュータシステムにおいて、複数のプログラムを並列的に実行する機能を備えたプログラミング言語により記述されたソースプログラム中に、当該複数のプログラムが共有するデータ構造が有るとき、当該データ構造が更新されたことを示す領域を設けた変換済プログラムへ変換することを特徴とする、プログラム変換方法。
【請求項３】
請求項２記載のプログラム変換方法において、
前記データ構造が更新されたことを示す領域が、複数のプログラムを排他的に実行する区間の開始点で設定されるよう、変換済プログラムへ変換するプログラム変換方法。
【請求項４】
請求項２記載のプログラム変換方法において、
１のプログラムが、共有するデータ構造の第１の参照を行い、前記更新されたことを示す領域の第２の参照を行い、第２の参照の結果、
当該領域が更新を意味しないとき、第１の参照を完了させ、
当該領域が更新を意味するとき、１のプログラムの実行を排して他のプログラムが実行されるよう、変換済プログラムへ変換するプログラム変換方法。
【請求項５】
請求項２記載のプログラム変換方法において、
前記データ構造が更新されたことを示す領域が、複数のプログラムを排他的に実行する区間の開始点で設定され、
１のプログラムが、共有するデータ構造の第１の参照を行い、前記更新されたことを示す領域の第２の参照を行い、第２の参照の結果、
当該領域が更新を意味しないとき、第１の参照を完了させ、
当該領域が更新を意味するとき、１のプログラムの実行を排して他のプログラムが実行されるよう、変換済プログラムへ変換するプログラム変換方法。
【請求項６】
請求項５記載のプログラム変換方法において、
１．別のプログラムから参照可能な、前記区間における、前記データ構造の更新の回数が０回又は１回であること、
２．１．の更新以外に、前記区間に、他のプログラムから参照可能なデータの更新、又は、入出力その他別のプログラムから検知可能な副作用を伴うコンピュータシステムの実行を伴わないこと、及び
３．前記区間におけるプログラムの実行が、所定のステップ数を超えずに完了すること、かつ、
ａ．前記区間に有る、他のプログラムによる前記データ構造への操作が、参照のみであること、
ｂ．ａ．のデータ構造への参照を除いて、前記区間に、別のプログラムから参照可能なデータの更新、又は、入出力その他別のプログラムから検知可能な副作用を伴うコンピュータシステムの実行を伴わないこと、
の全てが満たされる場合において、前記データ構造が更新されたことを示す領域の設定を行わない変換済プログラムへ変換するプログラム変換方法。
【請求項７】
請求項２記載のプログラム変換方法において、
前記データ構造が更新されたことを示す領域が、ビットではなくフィールドであり、前記１のプログラムの識別子を内容とする変換済プログラムへ変換するプログラム変換方法。
【請求項８】
請求項２記載のプログラム変換方法において、
全てのプログラムの実行を、前記複数のプログラムが共有するデータ構造の参照から前記データ構造が更新されたことを示す領域の参照までの間を避けて、停止させた後、
複数のプログラムを排他的に実行する区間における当該実行の対象でないデータ構造に対して、当該データ構造が更新されたことを示す領域を、更新されていないことを示す状態とする、変換済プログラムへ変換するプログラム変換方法。
【請求項９】
ソースプログラムを入力し、変換済プログラムを出力するコンパイラプログラムであって、構文解析処理機能、同期精密化処理機能及びコード生成処理機能を有するものにおいて、
前記同期精密化処理機能が、請求項２記載のプログラム変換方法を使用したことを特徴とするコンパイラプログラム。
【請求項１０】
ソースプログラムを入力し、変換済プログラムを出力するコンパイラプログラムであって、構文解析処理機能、同期精密化処理機能及びコード生成処理機能を有するものにおいて、
前記同期精密化処理機能が、請求項４記載のプログラム変換方法を使用したことを特徴とするコンパイラプログラム。
【請求項１１】
ソースプログラムを入力し、変換済プログラムを出力するコンパイラプログラムであって、構文解析処理機能、同期精密化処理機能及びコード生成処理機能を有するものにおいて、
前記同期精密化処理機能が、請求項７記載のプログラム変換方法を使用したことを特徴とするコンパイラプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のプログラムを並列的に実行する排他制御に係り、排他の精度を上げ、オーバヘッドを削減する技術に関する。
【背景技術】
【０００２】
従来から、並列実行を行うプログラムの一部の区間について、排他制御を行って逐次的に実行を行うことが知られている。
最近のＯＳやプログラミング言語は、「マルチスレッド」と呼ばれる複数の「スレッド」をマルチプロセッサ上で並列的に又は時分割によって擬似並列的に、動作させるプログラムの実行機能をサポートしている。
ここで、「スレッド」とは、コンピュータシステムの記憶空間を共有する実行主体をいう。
従来のプロセスによる処理単位の分割とは異なり、スレッドによる処理は、メモリ空間その他のコンピュータ資源を共有しているため、複数のスレッド間でのデータの共有が容易であり、実行オーバヘッドも低いという利点を持つ。
例えば、プログラミング言語の一種であるJava（登録商標）では、言語レベルでマルチスレッドをサポートしており、マルチプロセッサシステム上でのプログラム性能を向上させると共に、ネットワークサーバやGUIアプリケーションなど、複数の仕事を同時に実行する必要のある処理を簡潔に記述することを容易としている。
【０００３】
マルチスレッドの機能をサポートするプログラムでは、複数のスレッドが同時並列的に処理を行うため、複数のスレッドが同一のオブジェクト(データ)を対象として同時並列的に操作を行うと、オブジェクトの状態に不整合を生じる可能性がある。そのため、Javaでは、モニタと呼ばれる同期機能(排他制御機能)を用意し、スレッド間の排他制御を可能としている。ここで、排他制御とは、複数のスレッドが同じオブジェクトを同時期に操作することによって不都合が生じないよう、一のスレッドのみがオブジェクトを操作するよう制御することをいう。
モニタとは、排他制御対象となるデータと、それに対する排他的アクセス手続を組としたデータ構造であり、クリティカルセクションを実行する際には、高々１つのスレッドのみが実行を行えるようにしたものである。尚、クリティカルセクションとは、ユーザが指定した、排他的にプログラムの実行を行う区間をいう。
【０００４】
このために、各スレッドは、クリティカルセクションの入口で、操作対象であるオブジェクトをロックし、出口でロックを解除する。
ロック対象のオブジェクトが、他のスレッドによって既にロックされているときは、そのロックが解除されるまで実行を待たされる。このようにして、クリティカルセクションにおけるプログラムの排他的な実行が可能となる。
Javaのクラスライブラリは、マルチスレッド環境での利用を前提として設計されている。
【０００５】
一方、多くのプログラムでは、実行時に生成されるオブジェクトの殆どは、複数のスレッドから参照されることはない、ということが経験的に知られている。ここで「参照」とは、オブジェクトの性質を変えずにシステム又はプログラムがオブジェクトの内容を知得することをいう。従来のJava バーチャルマシン（以下、適宜「VM」と記す）の実装では、このような排他的制御が必要となるスレッドが局在すること（局所性）に着目して、処理の高速化を行っている。
【０００６】
例えば、非特許文献１では、Thin Lockと呼ばれる高速化方式が提案されている。
Thin Lockでは、あるオブジェクトをロックしているスレッドが、１つである間は、オブジェクトのヘッダに確保された領域へ、ロックを行っているスレッドの情報を書き込むことによって、低いオーバヘッドで、オブジェクトのロックとその解除を行う。
複数のスレッドが同時にクリティカルセクションの実行を必要とした場合は、オブジェクトのヘッダは外部に確保した、排他制御のためのデータ構造を指定するように変更する。
複数のスレッドが、クリティカルセクションの実行を必要とする場合に、外部に確保したデータ構造の操作が必要となるが、単一スレッドからのみロックが行われる場合には、ヘッダの操作だけでロックとその解除を行うことができるので、排他的処理を高速に行える。
【０００７】
このような動的な排他制御のためのオーバヘッドの削減方式以外に、プログラムを解析することによって、不要な排他制御を削除する最適化が提案されている。
例えば、非特許文献２では、エスケープ解析と呼ばれるプログラム解析を行うことで、不要な排他制御を削除する方式が提案されている。
エスケープ解析とは、プログラム中で生成されるオブジェクトについて、そのオブジェクトが複数のスレッドで共有され得るか否かを解析する技法である。オブジェクトが複数のスレッドから共有されることが有り得ないことを、同技法の解析によって保証できれば、当該オブジェクトに対する排他制御は不要であるから、この機能を削除することができる。
【０００８】
【非特許文献１】D.Bacon and R. Konuru and C. Murthy and M. Serrano, Thin Locks: Featherweight Synchronization for Java, In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, 1998.
【非特許文献２】J.D. Choi, Escape Analysis for Java, In Proceedings of the Conference on Object-Oriented Programming Systems, Languages, Applications, 1999.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従来の排他的高速化手法は、１）単一スレッドからの排他制御の要求のみである場合、又は、２）データが複数のスレッドで共有されないため排他制御が不要であることをコンパイラが保証できる場合、に限られていた。
従って、かかる場合以外では、クリティカルセクションにおける命令の実行は、現実には同時に実行可能な例えばデータの参照のみの場合であっても、排他的に行われていた。クリティカルセクションでは、データの参照のみのスレッドであっても、自己の順番が来るまで待ち、全体としては複数のスレッドに対し逐次的に排他制御が実行されていた。
【課題を解決するための手段】
【００１０】
排他制御の対象となるデータに対して、排他的に実行を行う区間内で更新が行われたか否かの情報、又は、かかる更新を行ったスレッドを識別するための情報、を付与する。ここで「更新」とは、システム又はプログラムがオブジェクトの内容を変更することをいう。「排他的に実行を行う区間内で更新」、「排他的に実行を行う区間内で参照」を以下、適宜、「同期更新」、「同期参照」と略称する。
同時期に更新を行う可能性のあるスレッドで、クリティカルセクションを開始する際には、当該情報を設定するものとする。
同時期に参照を行うスレッドでは、排他制御を行わずにデータの参照を行い、その後、前記のデータに付与した情報を検査する。
その結果、データの同時期の更新が行われていない場合、又は、同時期の更新を行ったスレッドが自スレッドのみの場合、先に参照したデータが更新されていないことを保証できるため、クリティカルセクションでの排他的な実行を行うことなく、処理を完了できる。
【発明の効果】
【００１１】
従来技術によればクリティカルセクションの排他制御が必要な場合に、本発明を適用すれば、１）プログラムを逐次実行とするためのオーバヘッドの削減と、２）オブジェクトが更新されていなければプログラムを並列実行とすることによるオーバーヘッドの削減が可能となる。
【発明を実施するための最良の形態】
【００１２】
図２に本発明を適用するシステムの例を示す。
本発明を適用した言語処理系（以下、コンパイラと称す）は、外部記憶203に格納されて配布される。実行の際には、外部記憶203からメモリ202へ読み出され、CPU201によって実行される。
【００１３】
図１に本発明の一実施例を示す。
本発明を適用したコンパイラ101は、ソースプログラム105を入力とし、変換済みプログラム107を出力する。コンパイラ101は、構文解析処理102、本発明の特徴的な処理である、同期精密化処理103、コード生成処理104から構成され、これらの処理は中間結果として、中間語106を読み書きする。
【００１４】
図３に本発明の対象とするプログラムと、その擬似コードの例を示す。
図３(a)はJavaによる同期メソッドの記述例を示している。
Javaではsynchronized指示子を付与したメソッドは、メソッド本体が所属オブジェクトを対象とするクリティカルセクションとして排他的に実行される。クラスＣに対して、フィールド_xの値を求める同期メソッドget、フィールド_xの値を設定する同期メソッドset、フィールド_xに対してパラメータで指定された値を2度加える同期メソッドtwiceが定義されている。
【００１５】
図３(b)は同期メソッドgetに対して従来の方式を適用した場合の擬似コードを示している。
同図に示すgetの擬似コードでは、対象オブジェクトをロックし(301)、フィールドの参照を行い(302)、対象オブジェクトのロックを解除(303)した後で、参照したフィールド値を返却(304)している。フィールドのロックと、ロックの解除の間は１つのスレッドしか実行できないので、排他制御が実現される。なお、ここで、thisはメソッドの所属オブジェクトを表すものとする。
【００１６】
図４に従来のオブジェクトの構造の例を示す。
オブジェクトは、固定長のヘッダ401と、可変長のオブジェクト固有データ402から構成される。ヘッダの最初のワード(マークフィールド)にはオブジェクトの状態、および、それに関連したデータを格納する。ここでは、オブジェクトのデータ構造は、非ロック状態(Unlocked)403と、ロック状態(Locked)404をとるものとする。各状態は、マークフィールドの下位2bitで識別され、下位2bitが2進数で01の場合に非ロック状態、10の場合にロック状態を表すものとする。非ロック状態のケースでは、マークフィールドはオブジェクトのハッシュ値407、オブジェクトの世代406などの情報を保持する。ロック状態のケースでは、マークフィールドには外部に確保されたロック情報を現すデータ構造409へのポインタ408が格納される。ロック情報を現すデータ構造409中には元のマークフィールドの値410が退避される。
【００１７】
図３(b)の擬似コードの例では、非ロック状態のマークフィールドを持つオブジェクトに対してlockオペレーションが適用されると、非ロック状態からロック状態へと変換される。また、ロック状態のオブジェクトに対してunlockオペレーションが適用されると、ロック状態から非ロック状態に変換される。複数のスレッドがlockオペレーションを要求した場合、外部データ構造409（図４）内に確保された待ち行列にクリティカルセクションの実施を待っているスレッドが格納され、クリティカルセクションの実行が完了するごとに、格納されたスレッドが待ち行列から取り出されて実行される。
なお、ここではオブジェクトの状態を非ロック状態とロック状態の２つとしているが、非特許文献１に示されているように、オブジェクトが単一のスレッドにのみロックされている状態が高速に処理できるよう、特別に扱われる場合は従来例である。
【００１８】
本発明の第一の形態では、同期更新されたか否かを表すフラグをオブジェクトに付加することによって、クリティカルセクションにおけるオーバヘッド削減と、同時実行とを可能とする。
図５に、改良を加えた非ロック状態のマークフィールドの構成を示す。従来の非ロック状態マークフィールド（図４）と比較すると、オブジェクトが同期更新されたか否かを表す同期更新ビット(S-MODビット)501が付加されている点が新しい。
【００１９】
次に、同期参照ビットを用いて、所定の条件下で、同期参照のシーケンスを高速に実行する、同期参照の精密化について説明する。
同期参照の精密化は、クリティカルセクションにおいて参照のみを行うメソッドに対して行われる。かかる精密化後の生成コードには、クリティカルセクション内の命令を試行的に実行し、その後、オブジェクトの同期更新ビットを参照する機能が付与されている。参照命令によっては、オブジェクトは同期更新されないので、前記試行的な実行の結果、同期更新ビットは「有効」（オブジェクトの更新なし）を意味している。
後述の条件を満たすときに、クリティカルセクション内の同期参照のシーケンスは精密化される。クリティカルセクションの試行的な実行が有効でない場合、すなわち、オブジェクトが同期更新されている場合は、従来と同じく、オブジェクトをロックしてからクリティカルセクション内の命令を実行する。
【００２０】
クリティカルセクション内の命令は試行的に実行されるため、同期参照のシーケンスの精密化は、以下の条件を満たす場合にのみ行われる。
【００２１】
Ａ．＜同期参照のシーケンスにおける精密化の実行条件＞
(1) クリティカルセクションに出現する命令のうち、他スレッドから更新可能なメモリ領域への操作が、参照のみであること。
(2) (1)のメモリ参照を除いて、クリティカルセクションに出現する命令を実行しても、メモリを介したデータのやり取り、同期化その他別のスレッドとの相互作用、又は、Ｉ／Ｏその他VMとは別のプログラムとの相互作用を伴わないこと。
【００２２】
図６に精密化を適用したgetメソッドの擬似コードの例を示す。
この擬似コードでは、まず、クリティカルセクション内のフィールド参照を実行(601)し、その後、オブジェクトのマークフィールドの下位3bitの値が１であるか否かを確認(602)する。
下位3bitの値が１であれば、非ロック状態、かつ、同期更新ビットがセットされていない(すなわち同期更新されていない)ことが確認できるので、メソッドを実行し、完了(603)する。
マークフィールドの下位3bitの値が１でない場合には、通常のケースと同様に、オブジェクトのロックを行ってクリティカルセクションを実行(604)する。
【００２３】
同期更新ビットがセットされていない場合には、複数のクリティカルセクションを同時に実行することが可能となる。また、lock、unlockオペレーションを行う必要がないため、従来と比較して同期のためのオーバヘッドが削減される。
本発明を適用したコードでは、同期更新ビットがセットされていない限り、複数のスレッドからの参照を同時に実行することができ、並列性を向上することが可能となる。従来技術（非特許文献１）では、１つのスレッドでオブジェクトに対して同期が行われる場合に着目して高速化を行っていたため、図３(a)のgetメソッドが複数のスレッドで同時実行されるようなケースでは、性能を向上することができなかった。
【００２４】
図７にtwiceメソッドの擬似コードの例を示す。
twiceメソッドは同期更新を行うメソッドであるので、オブジェクトのロック後に退避先マークフィールドの値のS-MODビット(下位3bit目)をセットする(701)。これ以降、当該オブジェクトは同期更新されたものとして扱われる。
上述のように、同期更新を行うケースでは、更新があったことを他のスレッドで識別するためにオブジェクトのロック時に同期更新ビットを１に変更する。同期更新ビットが１となったオブジェクトについては、図６に示した精密化適用版の擬似コードにおける高速パスは適用できないため、実行時オーバヘッドが若干ではあるが増加する。同期更新ビットを１に変更するケースを削減することで、このオーバヘッドを削減することができる。
【００２５】
オブジェクの同期更新ビットがセットされる頻度を削減するため、同期参照のシーケンスにおける精密化の実行条件(1)における、メモリ参照操作数を１に限定する。すると、同期更新を行う側のスレッドにおいて、クリティカルセクション内で更新があるようなケースであっても、更新側クリティカルセクションが次のような条件を満たす場合には、同期更新を行うスレッドで同期更新ビットの設定を省略することができる。
【００２６】
Ｂ．＜同期更新ビットがセットされる頻度を削減する条件＞
(1) 他スレッドから観測可能なクリティカルセクション内のメモリ更新数が高々１であること。
(2) (1)の状態の更新以外に、クリティカルセクションの実行が、他のスレッドとの相互作用、又は、同期、Ｉ／Ｏその他検知可能なVMとは別のプログラムとの相互作用を伴わないこと。
(3) クリティカルセクションの実行が、一定のステップ内で完了すること。
【００２７】
条件(1)、(2)により、参照側スレッドから検知可能な値がクリティカルセクションの実行前の値か、クリティカルセクションの実行後の値のいずれかになることが保証される。また、条件(3)により参照側スレッドが更新側クリティカルセクションの実行の完了を待つ必要がないことを保証できる。
本来のクリティカルセクションの定義より、他のクリティカルセクションを実行するスレッドは、実行中のクリティカルセクションの完了を待って実行を行わねばならない。
一方、あるスレッドにおいて、同期更新ビットの削減を適用したクリティカルセクションを実行中であった場合、精密化を適用した同期参照シーケンスは、実行中のクリティカルセクションと同時に実行を行うことが可能である。
もし、クリティカルセクションの実行が一定ステップ内で完了しない場合を適用対象として許すと、更新側スレッドにおいてクリティカルセクション内で無限ループを行うようなケースであっても、参照側スレッドが更新後の値を用いてクリティカルセクション後の実行を継続することが可能となり、プログラムの動作に不正を生じる。条件(3) はこのようなケースを排除するために設けたものである。
【００２８】
図３(a)の例において、setメソッドは上記の同期更新ビット削減の適用条件に合致する。これを適用した擬似コードの例を図８に示す。
setメソッドの擬似コードでは、従来のコードと同様に同期更新ビットのセットを行うコードは生成されない。
【００２９】
図９を用いて、提案する同期改良手法の安全性を議論する。
図９(a)は、更新スレッドのクリティカルセクション905の開始点903におけるマークフィールドの変更が、参照スレッドでのマークフィールドの参照902 よりも後であった場合を表している。
このケースでは、参照スレッドでのマークフィールドの読み出し902 よりも先にオブジェクトへの書き込み903 がなかったことを保証できるため、参照スレッドのマークフィールド参照902 よりも前におこなったフィールド参照901の値は正当であるとみなすことができる。
【００３０】
図９(b)は、同期更新スレッドのクリティカルセクション910 の開始点908におけるマークフィールドの更新が、参照スレッドによるマークフィールド参照907 よりも前のケースを示している。
このケースでは、オブジェクトがロック状態であると認識されるか、S-MOD=1、すなわち、同期更新されたものと認識されるので、参照スレッドが906で読み出したフィールド値は破棄され、通常の同期処理によるクリティカルセクションの実行が行われ、更新スレッドが909で書き込んだ値が参照される。
【００３１】
図９(c)は、同期参照および同期更新を行う点をどちらも1つのみに限定した場合を表している。このケースでは、更新側スレッドのクリティカルセクション915内の定義点が書き込み914の1つのみであることから、参照側スレッドが読み出し911で得られる値が、クリティカルセクションに入る前の値か、クリティカルセクションを抜けた後の値のいずれかとなることを保証できる。
このため、更新スレッド側のクリティカルセクションの開始点913において同期更新ビットを設定しなくとも、参照スレッドのマークフィールド参照912が不正となることは無い。
【００３２】
図１０(a)は、更新側スレッドのクリティカルセクション内で同期更新が2回(1004および1005) 以上起こりうるケースにおいて、同期更新ビットによる正当性検査を行わない場合や、同期更新後に同期更新ビットのクリアを行った場合に発生しうる状況を示したものである。
図１０(a)は不正な状況であり、本発明ではこのようなケースは、同期コード精密化の実行対象としていない。図１０(a)の例では、ロック処理1003とロック解除処理1006で構成されるクリティカルセクション内に、フィールド定義が2度出現するが、他のスレッドから検知可能となるべき値は、クリティカルセクションに入る前の更新されていない値か、クリティカルセクションを抜けた後の2度目の更新(1005)が行われた結果の値のいずれかでなければならない。
しかしながら、図の例では参照側スレッドでは最初の更新1004 による結果を1001において読み出しており、マークフィールド読み出し点1002において同期更新ビットが正しく考慮されていなければ不正な結果が得られてしまう。
本発明の精密化では、参照点と更新側クリティカルセクションで、同期更新ビットを設定するようにしているため、このような状況は生じ得ない。
【００３３】
図１０(b)は、参照側のスレッドにおいてクリティカルセクション同期更新ビットの削減処理を適用した場合に、参照側のクリティカルセクションで複数のメモリ参照を行った場合を示している。図１０(b)は不正な状況であり、本発明ではこのようなケースは、同期コード精密化の適用対象としていない。図10(b)の例では、ロック処理1010とロック解除処理1012で構成されるクリティカルセクションにおいて同期更新ビットが変更されないため、参照側スレッドと更新側スレッドが同時に実行されうる。参照側スレッドにおいてメモリ参照を複数回(1007, 1008)おこなっているため、更新側スレッドにおいてクリティカルセクション内で更新した値の更新前と更新後の値を参照し、1002の検証でクリティカルセクションの実行が正当であると判定された場合に、不整合な結果を招く可能性がある。先に述べたように、参照側クリティカルセクションでのメモリ参照の数を高々1つとすれば、このような状況は生じ得ない。
【００３４】
上記の同期更新ビットを利用した方式では、同一スレッドであっても同期更新を行い得るクリティカルセクションが一度でも実行されれば、それ以降参照クリティカルセクションに対する精密化効果は無くなる。ところが、同期更新を行うクリティカルセクションを実行するスレッドと、同期参照を行うクリティカルセクションを実行するスレッドが同一である場合、２つのクリティカルセクションが同時に実行されることはないため、同期参照精密化を適用した高速パスを実行することができる。そこで、そのようなケースに対して改良を加えた方法を示す。
【００３５】
図１１は、拡張を加えたマークフィールドの構成である。
ここでは、図５の同期更新(S-MOD) ビットの代わりに、同期更新を行ったスレッドを識別するためのスレッドID(TID)フィールドを加えている。スレッドIDフィールドの初期値は、該当スレッド無し(NoThread)とし、スレッドを同期更新した場合はそのスレッドの識別子を格納する。複数のスレッドが同期更新を行った場合は複数スレッドによる更新を表す識別子(MultipleThreads)を格納する。
【００３６】
図３(a)のgetメソッドに対して、本拡張を適用した擬似コードの例を図１２に示す。
この擬似コードでは、まずクリティカルセクション内の文を試行的に実行(1201)し、オブジェクトが同期更新されていないか、オブジェクトを同期更新したオブジェクトが自分自身である場合にはそのまま処理を終了する(1202)。他のスレッドによって同期更新がなされていた場合には、通常のクリティカルセクションの実行と同様に、オブジェクトをロック後にクリティカルセクションを実行し、そのオブジェクトのロックを解除するという手順を実行する(1203)。
【００３７】
次に、図３(a)のtwiceメソッドの擬似コードの例を図１３に示す。
図１３の擬似コードでは、オブジェクトを同期更新のためにロックした(1301)後で、対象オブジェクトが同期更新されていないか、自身によって同期更新されている場合にスレッドID(TID)フィールドを自身のスレッド識別子に設定し(1302)、それ以外の場合は複数スレッドによる更新であることを表す識別子(MultipleThreads)に設定する(1303)。
【００３８】
図１４に、同期更新(S-MOD)ビットを利用したフラグ版の動作の様子(同図(a))と、スレッド識別子(TID)を利用したスレッドID版(同図(b))の動作の様子を示す。なお、ここで、同期更新を行うスレッドと同期参照を行うスレッドは同一であるものとする。
フラグ版では、ロック1403とロックの解除1405で構成されるクリティカルセクションの実行によって同期更新(S-MOD)ビットが設定される。そのため、同一スレッドでは共有データの書き込み1404と読み出し1401が順番に行われることが保証可能であるにも関わらず、1402の検証に失敗し通常の同期処理が実行されてしまう。
スレッドID版では、ロック1408とロックの解除1410で構成されるクリティカルセクションの実行によって、スレッド識別子(TID)が同期更新を行ったスレッド(ここでは#1とする)に設定される。同期参照1406を行うスレッドが同一スレッドである場合、1407の検証に成功し、同期更新1409で書き込んだデータを同期参照1406で読み出した値を利用することができる。これにより、オブジェクトのロックおよびロック解除を必要とせず低いオーバヘッドで同期参照を行うことが可能となる。
【００３９】
図１５を用いて本発明の特徴的な処理である、同期精密化処理のフローを示す。
同期精密化処理は、処理1501から開始し、処理1502でプログラム中の文集合を変数Sに求める。次に、判定処理1503で集合Sが空集合か否かを確認する。空集合であれば処理対象の文が存在しないので、処理1511に制御を移して精密化処理を完了する。集合Sが空でなければ、処理1504において集合Sから文を１つ取り出し変数sに格納する。
次に判定処理1505において、文sがクリティカルセクションか否か(isCS(s)が真の場合、文sはクリティカルセクションであるものとする)を判定する。ある文がクリティカルセクションとなるか否かは、プログラミング言語の言語仕様等により決定される。処理1505の判定処理において、文sがクリティカルセクションでなければ、処理1503に制御を移して次の文を処理する。文sがクリティカルセクションであれば、処理1506でクリティカルセクションsが同期精密化の適用対象となるか否か(isGT(s)が真の場合、文sは同期精密化の適用対象であるものとする。)を確認する。
同期精密化の適用対象であれば、処理1507に制御を移し、精密化を適用した同期参照コードを出力した後、処理1503に制御を移して次の文の処理を行う。文sが同期精密化の適用対象でなければ、処理1508に制御を移して文sが同期更新情報(同期更新ビット、あるいは、同期更新スレッドID)の設定を必要とするクリティカルセクションであるか否か(isST(s)が真の場合、文sは同期更新情報の設定を必要であるものとする。)を確認する。
同期参照情報の設定を必要としない場合、処理1509において同期参照情報の設定を行わないクリティカルセクション実現コードを生成する。同期参照情報の設定を必要とする場合、処理1510において同期参照情報の設定を付与したクリティカルセクション実現コードを生成する。コード生成後は処理1503に制御を移して次の文の処理を行う。
【００４０】
次に、図１５の処理1506における同期精密化の適用対象であるか否かの判定処理のフローを図１６に示す。
同図の処理は、処理1601で処理を開始し、処理1602に制御を移して、判定対象のクリティカルセクション中の文集合を変数Sに求める。また、クリティカルセクション中の共有データに対するロード命令の集合を格納する変数Lを空集合に初期化する。
次に、判定処理1603において集合Sが空集合か否かを判定し、空集合であれば、処理1609に制御を移す。処理1609ではクリティカルセクションが参照のみであり、同期精密化の適用対象であるものとして、処理1610に制御を移して処理を完了する。なお、同期精密化対象のクリティカルセクション内のロード命令を高々１つに限定する場合には、集合Lの大きさが１以下であるか否かを確認すればよい。判定処理1603において集合Sが空集合でない場合には、処理1604に制御を移し集合Sから文を１つ取り出し、変数sへ格納する。
続いて、処理1605において文sが共有データに対するロード命令か否かを確認する。共有データに対するロード命令であれば、処理1606において集合Lに文sを加え、処理1603に制御を移して次の文の処理を行う。判定処理1605において文sが共有データに対するロードでない場合は、判定処理1607で文sがスレッド間で検出可能な副作用を有する命令か否かを判定する。
副作用を有する場合、クリティカルセクションは精密化の適用対象とはならないので、処理1608に制御を移し、クリティカルセクションは参照のみではないものとして、処理1610で処理を終了する。判定処理1607において文sが副作用を有しない場合は、処理1603へ戻って次の文の処理を行う。
【００４１】
図１５の判定処理1508におけるクリティカルセクションが、同期参照情報の更新を必要とするか否かの判定処理を図１７に示す。
同図の判定処理は、処理1701で処理を開始し、処理1702でクリティカルセクション中の文集合を変数Sに求め、クリティカルセクション内の共有データに対するストア命令の集合Wを空集合に初期化する。続いて、判定処理1703で文集合Sが空集合か否かを確認する。文集合Sが空集合であれば、処理すべき文が無いため、判定処理1709でクリティカルセクション内の共有データに対するストア命令の集合Wの大きさが１以下、すなわち、共有データに対するストア命令が高々１つのみであることを確認する。ストアが高々１つのみであれば、処理1710へ制御を移し、クリティカルセクションは単一定義のみであり、同期参照情報の更新を必要としないものとして、処理1711で処理を完了する。
処理1709でストアが高々１つのみでない場合は、処理1708で同期参照情報の更新が必要であるものとして処理1711で処理を完了する。判定1703に戻って、文集合Sが空集合で無い場合は、処理1704に制御を移して文集合Sから文を１つ取り出し変数sへ格納する。次に、判定処理1705で文sが共有データに対するストアであるか否かを判定する。共有データに対するストアであれば、処理1706において集合Wに文sを加え、処理1703に制御を移して次の文の処理を行う。判定処理1705において文sが共有データに対するストアでない場合、判定処理1707において、文がスレッド間で検出可能な副作用を有する命令であるか否かを確認する。
副作用を有する場合は、処理1708で同期参照情報の更新を必要であるものとして処理1711で処理を完了する。判定処理1707において、文sが副作用を有しない場合は、処理1703へ制御を移して次の文の処理を行う。
【００４２】
図１５に示す処理で生成するコードでは、同期参照情報の設定をするだけでクリア処理を行わないため、プログラムの実行が進むにつれ、同期参照精密化の適用対象となるオブジェクトの数が減少してしまう。そこで、同期参照情報を定期的にクリアする処理を導入する。
図１８及び図１９に、この処理のフローを示す。
本クリア処理は、スレッドをすべて停止させた状態で実施する。図１８は、この停止処理のフローを表したものである。スレッド停止処理は1801で処理を開始し、処理1802でプログラム中のスレッドの集合を変数Tに求める。次に、判定処理1803でスレッド集合Tが空集合か否かを確認する。空集合であれば、処理1808に制御を移して処理を完了する。Tが空集合でない場合は、処理1804で集合Tからスレッドを1つ取り出し変数tに格納する。
続いて、処理1805でスレッドtを停止させ、処理1806でtの停止点が安全な停止点か否かを確認する。なお、ここでisSafe(t)が真であれば、スレッドtが安全な停止点停止中であることを意味するものとする。安全な停止点とは、同期参照精密化の適用されたクリティカルセクションにおいて、クリティカルセクションの開始点から精密化適用の正当性の確認が完了するまでの区間以外のプログラム実行地点を意味する。
安全でない停止点で同期情報のクリアを行った場合、同期精密化の正当性の確認結果が不正となるため、クリア処理は安全な停止点で行う必要がある。判定処理1806の判定において、スレッドtの停止点が安全な停止点でない場合は、処理1807に制御を移してスレッドtの実行を暫く継続し、1805以降の処理を継続する。判定処理1806において、スレッドtの停止点が安全な停止点である場合は、処理1803に制御を移して次のスレッドを処理する。以上の処理により、すべてのスレッドが安全に同期参照情報をクリア可能な点で停止されることが保証される。
【００４３】
図１９は、オブジェクトの同期更新情報のクリア処理のフローを示したものである。
クリア処理は処理1901から処理を開始し、処理1902においてオブジェクトの集合を変数Oへ格納する。次に、判定1903において集合Oが空集合か否かを確認する。空集合であれば、処理1907に制御を移して処理を完了する。空集合でなければ、処理1904において集合Oからオブジェクトを1つ取り出し変数に格納する。次に、判定処理1905にてオブジェクトoがロック中であるか否かを確認する、ロック中であれば処理1903に制御を移して次のオブジェクトの処理を行う。ロック中でなければ処理1906に制御を移してoの同期更新情報をクリアし、処理1903に制御を移して次のオブジェクトを処理する。
【産業上の利用可能性】
【００４４】
本発明は、同期による排他制御を行うプログラムの性能向上に利用できる。
【図面の簡単な説明】
【００４５】
【図１】本発明を適用したコンパイラの構成例を示す図である。
【図２】本発明を適用するシステムの例を示す図である。
【図３】本発明の適用対象であるプログラムと、その擬似コードの例を示す図である。
【図４】従来のオブジェクトの構成例を示す図である。
【図５】改良を加えた非ロック状態のマークフィールドの構成を示す図である。
【図６】同期参照の精密化を適用したgetメソッドの擬似コードの例を示す図である。
【図７】同期更新のtwiceメソッドの擬似コードの例を示す図である。
【図８】同期参照情報の設定が不要な同期更新メソッドの擬似コードの例を示す図である。
【図９】精密化を適用した同期改良手法の安全性を議論するための図である。
【図１０】精密化を適用しない場合のプログラムの動作例を示す図である。
【図１１】拡張を加えたスレッドID版のマークフィールドの構成例を示す図である。
【図１２】拡張を加えたスレッドID版の同期参照メソッドの擬似コードの例を示す図である。
【図１３】拡張を加えたスレッドID版の同期更新メソッド（twiceメソッド）の擬似コードの例を示す図である。
【図１４】同期更新(S-MOD)ビットを利用したフラグ版プログラムの動作の様子と、スレッド識別子(TID)を利用したスレッドID版プログラムの動作の様子を示す図である。
【図１５】同期精密化処理のフローを示す図である。
【図１６】図１５の処理1506における同期精密化の適用対象であるか否かの判定処理のフローを示す図である。
【図１７】図１５の判定処理1508におけるクリティカルセクションが同期参照情報の更新を必要とするか否かの判定処理を示す図である。
【図１８】同期参照情報をクリアするためのスレッド停止処理フローを示す図である。
【図１９】オブジェクトの同期更新情報をクリアするための処理フローを示す図である。
【符号の説明】
【００４６】
101…コンパイラ
102…構文解析処理部
103…同期精密化処理部
104…コード生成処理部
105…ソースプログラム
106…中間語
107…変換済プログラム
【図１】
2006185232.tif 000003
【図２】
2006185232.tif 000004
【図３】
2006185232.tif 000005
【図４】
2006185232.tif 000006
【図５】
2006185232.tif 000007
【図６】
2006185232.tif 000008
【図７】
2006185232.tif 000009
【図８】
2006185232.tif 000010
【図９】
2006185232.tif 000011
【図１０】
2006185232.tif 000012
【図１１】
2006185232.tif 000013
【図１２】
2006185232.tif 000014
【図１３】
2006185232.tif 000015
【図１４】
2006185232.tif 000016
【図１５】
2006185232.tif 000017
【図１６】
2006185232.tif 000018
【図１７】
2006185232.tif 000019
【図１８】
2006185232.tif 000020
【図１９】
2006185232.tif 000021