(57)【要約】【課題】複数のスレッドが同じカウンタの値に対して頻繁に更新操作を行う状況において、それらの更新操作を効率的に実施できるようにする。【解決手段】情報処理システムは、処理部に対応する個別カウンタと、前記個別カウンタに対応するあらかじめ定められた値に縮退された値を含むインジケータと、インクリメントに際し、先に、対応する前記個別カウンタの値を調べ、対応する前記個別カウンタの値が、前記あらかじめ定められた値以上であると、対応する前記個別カウンタの値をインクリメントし、対応する前記個別カウンタの値が、前記あらかじめ定められた値未満であると、次に、対応する前記個別カウンタに対応する前記インジケータの値をインクリメントし、かつ、対応する前記個別カウンタの値をインクリメントするスレッドを実行する前記処理部と、を含む。【選択図】      図１
2015090632.tif 000002
【特許請求の範囲】
【請求項１】
処理部に対応する個別カウンタと、
前記個別カウンタに対応するあらかじめ定められた値に縮退された値を含むインジケータと、
インクリメントに際し、先に、対応する前記個別カウンタの値を調べ、対応する前記個別カウンタの値が、前記あらかじめ定められた値以上であると、対応する前記個別カウンタの値をインクリメントし、対応する前記個別カウンタの値が、前記あらかじめ定められた値未満であると、次に、対応する前記個別カウンタに対応する前記インジケータの値をインクリメントし、かつ、対応する前記個別カウンタの値をインクリメントするスレッドを実行する前記処理部と、
を含むことを特徴とする情報処理システム。
【請求項２】
インクリメントに際し、対応する前記個別カウンタの値が前記あらかじめ定められた値未満で、かつ、対応する前記個別カウンタに対応する前記インジケータの値が、前記あらかじめ定められた値未満の場合に、対応する前記個別カウンタに対応する前記インジケータの値をインクリメントする前記スレッドを実行する前記処理部を含むことを特徴とする請求項１の情報処理システム。
【請求項３】
インクリメントに際し、先に、対応する前記個別カウンタに対応する前記インジケータの値を調べ、対応する前記個別カウンタに対応する前記インジケータの値が、前記あらかじめ定められた値未満の場合に、対応する前記個別カウンタの値を調べる前記スレッドを実行する前記処理部を含むことを特徴とする請求項２の情報処理システム。
【請求項４】
デクリメントに際し、対応する前記個別カウンタの値をデクリメントし、デクリメントした結果の値が、前記あらかじめ定められた値未満であると、対応する前記個別カウンタに対応する前記インジケータの値をデクリメントする前記スレッドを実行する前記処理部を含むことを特徴とする請求項１、２、または、３の情報処理システム。
【請求項５】
前記個別カウンタ、または、前記インジケータのインクリメント、または、デクリメントを不可分アクセス操作により処理する前記スレッドを実行する前記処理部を含むことを特徴とする請求項４の情報処理システム。
【請求項６】
ＣＡＳ操作により、前記個別カウンタの値、または、前記インジケータの値をインクリメントする前記スレッドを実行する前記処理部を含むことを特徴とする請求項５の情報処理システム。
【請求項７】
インクリメントに際し、対応する個別カウンタの値が、前記あらかじめ定められた値以上であると、対応する前記個別カウンタの値をインクリメントし、対応する前記個別カウンタの値が、前記あらかじめ定められた値未満であると、対応する前記個別カウンタに対応するあらかじめ定められた値に縮退された値を含むインジケータの値をインクリメントし、かつ、対応する前記個別カウンタの値をインクリメントすることを特徴とする情報処理方法。
【請求項８】
インクリメントに際し、対応する前記個別カウンタの値が前記あらかじめ定められた値未満で、かつ、対応する前記個別カウンタに対応する前記インジケータの値が、前記あらかじめ定められた値未満の場合に、対応する前記個別カウンタに対応する前記インジケータの値をインクリメントすることを特徴とする請求項７の情報処理方法。
【請求項９】
インクリメントに際し、対応する個別カウンタの値が、前記あらかじめ定められた値以上であると、対応する前記個別カウンタの値をインクリメントし、対応する前記個別カウンタの値が、前記あらかじめ定められた値未満であると、対応する前記個別カウンタに対応するあらかじめ定められた値に縮退された値を含むインジケータの値をインクリメントし、かつ、対応する前記個別カウンタの値をインクリメントする処理を、コンピュータに実行させることを特徴とするプログラム。
【請求項１０】
インクリメントに際し、対応する前記個別カウンタの値が前記あらかじめ定められた値未満で、かつ、対応する前記個別カウンタに対応する前記インジケータの値が、前記あらかじめ定められた値未満の場合に、対応する前記個別カウンタに対応する前記インジケータの値をインクリメントする処理を、コンピュータに実行させることを特徴とする請求項９のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システム、情報処理方法、および、プログラムに関する。
【背景技術】
【０００２】
情報処理システムでは、プロセッサなどの計算機資源を効率的に使用するため、複数のプロセスやスレッドを並行して動作させることが一般的である。
【０００３】
厳密には、プロセスとスレッドとは完全に同一ではないが、プログラムを実行する単位を意味するという点では同種の概念であり、本発明を説明する目的に関する限りでは両者の差異を区別しなくても差し支えない。したがって、以降、プログラムを実行する単位をスレッドと表記する。
【０００４】
複数のプロセッサを有することで、複数のスレッドを同時に並行して実行するように構成された情報処理システムでは、メモリ上に存在するデータに対して複数のスレッドが並行してアクセスすることがある。
【０００５】
例として、複数のスレッドがメモリ上に存在するカウンタを共有し、各スレッドがカウンタに対してインクリメント（カウンタの値に１を加える）操作やデクリメント（カウンタの値から１を減ずる）操作を行う状況がある。
【０００６】
ここで、各スレッドが行うインクリメント（デクリメント）操作とは、そのスレッドを実行しているプロセッサが、カウンタの値を読み込んで１を加え（１を減じ）、その結果を書き戻す、という処理である。
【０００７】
ここで、あるプロセッサがカウンタの値を読み込んでから演算結果を書き戻すまでの間に別のプロセッサが同じカウンタの値を読み込んで演算を行うという順で処理が進むと、正しい結果は得られなくなる。
【０００８】
そこで、このような順で処理が行われるのを防止する方法の一つとして、プロセッサには不可分（atomic）なアクセス命令（ハードウェアを利用して不可分アクセス操作を行う）が用意されることが多い。たとえば、［非特許文献２］に記載の技術では、カウンタの値に対して、LOCK prefixを付与したAdd命令などによる不可分なアクセスを行うようになっている。この不可分なアクセス命令では、プロセッサがカウンタの値を読み込んでから演算結果を書き戻すまでの間、共有バスをロックすることで、この間に他のプロセッサがカウンタの値を読み込む操作を禁止する。
【０００９】
この技術では、各プロセッサが同時に不可分なアクセスを実行すると、共有バスのロックが処理進行の妨げとなる、すなわち、ボトルネックになってしまう。
【００１０】
この問題に対処するため、キャッシュを搭載しているプロセッサの中には、共有バスをロックしない方法でLOCK prefixを付与したAdd命令を実行する技術がある。この技術では、キャッシュに読み込まれたカウンタの値に対して、不可分なアクセスを行う際、キャッシュ・プロトコルが利用される。そして、不可分なアクセスを行うプロセッサのみが、当該カウンタの値の存在するキャッシュ・ブロックのコピーを保持していることを保証するようになっている。
【００１１】
これにより、各プロセッサが同時に不可分なアクセスを実行しても、対象となる変数が別々のキャッシュ・ブロックに存在する場合は、共有バスに起因するボトルネックを避けることができる。
【００１２】
複数のプロセッサが同じカウンタの値に対して同時に不可分なアクセスを行うという事象は、複数のスレッドが同じカウンタの値に対して頻繁に不可分なアクセスを行う程高くなる。
【００１３】
したがって、複数のスレッドが独立して動作するようなプログラムでは問題になることはないが、逆に、データベース・システムのように、データの無矛盾性を保つため、複数のスレッドが頻繁に同期操作を行いながら処理を進めるようなプログラムの場合は問題となる可能性がある。
【００１４】
この問題に対処する関連技術の一つに、［非特許文献１］に記載されたscalable NonZero Indicatorsや、［非特許文献３］に記載されたsloppy counterがある。
【００１５】
これらは、プロセッサごとの個別カウンタ、および、それらを統括するインジケータを持たせる構成である。そして、（１）全カウンタ値を求めることは困難（時間のかかる処理を要する）、（２）インジケータが‘０’を示している場合は全カウンタ値も‘０’であることが保障される、という性質がある。ここで、全カウンタ値とは、個別カウンタの値の総和である。
【００１６】
すなわち、インジケータが‘０’を示していない場合でも、全カウンタ値が‘０’である状態を許容することにより、前記の問題を解決しているわけである。この性質は、オブジェクト（プログラムがアクセスするメモリ要素）に対する参照数をカウントし、そのカウント値が‘０’になったときにオブジェクトを開放（ガベージ・コレクション）するreference-counted garbage collectionの用途には適している。
【００１７】
また、［特許文献１］には、cmpxchg命令のＣＡＳ（Compare And Swap）操作の技術についての記載がある。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】ＷＯ２０１１／０９６１６３号公報
【非特許文献】
【００１９】
【非特許文献１】F. Ellen, Y. Lev, V. Luchango, and M. Moir, 「SNZI：Scalable nonzero indicators」, In PODC 2007, Portland, Oregon, USA, Aug. 2007.
【非特許文献２】「Intel64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference」, A-M, [online], 1997年, Intel, [2013年10月21日検索], インターネット＜URL: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-vol-2a-manual.pdf ＞
【非特許文献３】Boyd-Wickizer, Silas and Clements, Austin T and Mao, Yandong and Pesterev, Aleksey and Kaashoek, M Frans and Morris, Robert and Zeldovich, Nickolai, 「An analysis of Linux（登録商標） scalability to many cores」, USENIX Association, [online], 2010年10月, USENIX Association - 9th USENIX Symposium on Operating Systems Design and Implementation, Vancouver, BC, Canada, [2010年11月2日検索], インターネット＜URL: http://pdos.csail.mit.edu/papers/linux:osdi10.pdf ＞
【発明の概要】
【発明が解決しようとする課題】
【００２０】
上述の先行技術には、複数のスレッドが同じカウンタの値に対して頻繁に更新操作を行う状況において、次の問題がある。すなわち、それらの更新操作を効率的に実施でき、かつ、全カウンタ値があらかじめ定められた値以下になったことを直ちに知ることができる構成になっていないという問題がある。
【００２１】
その理由は、［非特許文献２］の単一のカウンタで全カウンタ値を保持する技術では、そのカウンタの値に対して、複数のスレッドが同時にLOCK prefixを付与したAdd命令などによる不可分アクセスを行うと、それらの操作がボトルネックになるためである。
【００２２】
なぜなら、同じカウンタの値に対して同時に不可分なアクセスが行われると、そのカウンタの値が含まれるキャッシュ・ブロックがプロセッサ間で転送されることになり、ボトルネックが発生するからである。
【００２３】
一方、［非特許文献１］、［非特許文献３］の各プロセッサに個別カウンタの値を持たせるとともに、全カウンタ値が、‘０’かどうかを示す全プロセッサに共通のインジケータを持たせる技術には、以下の理由がある。
【００２４】
その理由は、scalable NonZero Indicatorsや、sloppy counterは、全カウンタ値が、‘０’であるにも関わらずインジケータが、‘０’を示さない状態が存在するため、全カウンタ値が‘０’になってからインジケータが、‘０’を示すまでに時間がかかってしまうからである。
【００２５】
あるオブジェクトに関してアクセスが競合した場合において、競合するアクセスを行っているスレッド数が、‘０’になっても、インジケータが、‘０’を示すまでの間は、待ち状態にあるスレッドのアクセスは許可されず、有効な処理が進まなくなってしまう。
【００２６】
すなわち、全カウンタ値が、‘０’になったという事象がインジケータに反映されるまでに時間がかかるため、カウンタの値が、‘０’もしくは、「あらかじめ定められた値」になったことを効率的に検出する機能を有するという要件を満たせないからである。
【００２７】
本発明の目的は、上記問題点を解決する情報処理システム、情報処理方法、および、プログラムを提供することである。
【課題を解決するための手段】
【００２８】
本発明の情報処理システムは、処理部に対応する個別カウンタと、前記個別カウンタに対応するあらかじめ定められた値に縮退された値を含むインジケータと、インクリメントに際し、先に、対応する前記個別カウンタの値を調べ、対応する前記個別カウンタの値が、前記あらかじめ定められた値以上であると、対応する前記個別カウンタの値をインクリメントし、対応する前記個別カウンタの値が、前記あらかじめ定められた値未満であると、次に、対応する前記個別カウンタに対応する前記インジケータの値をインクリメントし、かつ、対応する前記個別カウンタの値をインクリメントするスレッドを実行する前記処理部と、を含む。
【００２９】
本発明の情報処理方法は、インクリメントに際し、対応する個別カウンタの値が、前記あらかじめ定められた値以上であると、対応する前記個別カウンタの値をインクリメントし、対応する前記個別カウンタの値が、前記あらかじめ定められた値未満であると、対応する前記個別カウンタに対応するあらかじめ定められた値に縮退された値を含むインジケータの値をインクリメントし、かつ、対応する前記個別カウンタの値をインクリメントする。
【００３０】
本発明のプログラムは、インクリメントに際し、対応する個別カウンタの値が、前記あらかじめ定められた値以上であると、対応する前記個別カウンタの値をインクリメントし、対応する前記個別カウンタの値が、前記あらかじめ定められた値未満であると、対応する前記個別カウンタに対応するあらかじめ定められた値に縮退された値を含むインジケータの値をインクリメントし、かつ、対応する前記個別カウンタの値をインクリメントする処理を、コンピュータに実行させる。
【発明の効果】
【００３１】
本発明は、複数のスレッドが、インクリメント、または、デクリメントを行う場合、個別カウンタの更新の操作を効率的に実行できるという効果を持つ。
【図面の簡単な説明】
【００３２】
【図１】本発明の第１の実施の形態の構成を示すブック図である。
【図２】本発明の第１の実施の形態の動作を示す動作説明図である。
【図３】本発明の第２の実施の形態の構成を示すブロック図である。
【図４】図３のＣＰＵの構成を示すブロック図である。
【図５】個別カウンタとインジケータの対応の一例を示す説明図である。
【図６】本発明の第２の実施の形態の動作を示す動作説明図である。
【図７】本発明の第２の実施の形態の動作を示す動作説明図である。
【図８】本発明の第２の実施の形態の動作を示す動作説明図である。
【図９】本発明の第３の実施の形態の動作を示す動作説明図である。
【発明を実施するための形態】
【００３３】
次に、本発明の第１の実施の形態について図面を参照して詳細に説明する。
【００３４】
図１は、第１の実施の形態の構成を示すブロック図である。図１を参照すると、第１の実施の形態の情報処理システム１００は、処理部１３１、処理部１３２、処理部１３３、処理部１３４、インジケータ１５０、個別カウンタ１６１、個別カウンタ１６２、個別カウンタ１６３、および、個別カウンタ１６４を含む。
【００３５】
情報処理システム１００は、たとえば、コンピュータを含み、処理部１３１〜１３４は、そのコンピュータで構成されることが可能である。
【００３６】
インジケータ１５０、および、個別カウンタ１６１〜１６４は、メモリ（図示しない）に設定されることが可能である。個別カウンタ１６１、個別カウンタ１６２、個別カウンタ１６３、個別カウンタ１６４は、それぞれ、処理部１３１、処理部１３２、処理部１３３、処理部１３４に対応している。
【００３７】
また、処理部、および、個別カウンタの個数は、４個には限定されず、ｍ（正の整数）個であってよい。
【００３８】
インジケータ１５０は、それぞれ、個別カウンタ１６１、個別カウンタ１６２、個別カウンタ１６３、個別カウンタ１６４に対応した値Ｐ１、Ｐ２、Ｐ３、Ｐ４（たとえば、ビット列）を含む。
【００３９】
Ｐ１〜Ｐ４は、それぞれ、個別カウンタ１６１〜１６４の値が、‘０’、‘１’、・・・、‘ｎ−１’、‘ｎ以上’のように、ｎ以上と、それ未満の個々の整数（０以上）を示すように縮退した値が対応する。ｎは、「あらかじめ定められた値」と定義され、任意の正の整数が可能である。このような構成を、インジケータ１５０は、個別カウンタ１６１〜１６４の「あらかじめ定められた値」に縮退された値を含む構成と称する。
【００４０】
また、処理部１３１〜１３４では、それぞれ、複数のスレッド（数は限定されない）が同時に実行可能である。
【００４１】
スレッド２１１、および、スレッド２１２は、処理部１３１で実行される。スレッド２２１、および、スレッド２２２は、処理部１３２で実行される。スレッド２３１、および、スレッド２３２は、処理部１３３で実行される。スレッド２４１、および、スレッド２４２は、処理部１３４で実行される。
【００４２】
ここで、スレッドは、プロセス等のプログラムの実行単位を代表する意味を持つ。個々のスレッド２１１〜２４２は、処理部１３１〜１３４のどれか１つでしか実行されない。すなわち、それぞれの処理部１３１〜１３４と個々のスレッド２１１〜２４２との対応関係は固定されている。
【００４３】
したがって、図１に示される範囲においては、たとえば、処理部１３１で実行されるスレッド２１１、２１２は、インジケータ１５０、および、個別カウンタ１６１にしかアクセスしない。
【００４４】
次に、第１の実施の形態の動作について図面を参照して説明する。
【００４５】
図２は、第１の実施の形態の動作を示す動作説明図である。代表して、処理部１３１で実行されるスレッド２１１に関して説明する。
【００４６】
図２を参照すると、スレッド２１１が個別カウンタ１６１の値をインクリメント（値を増加）する場合（ステップＡ１／Ｙ）、スレッド２１１は、個別カウンタ１６１の値を調べる（ステップＡ２）。
【００４７】
個別カウンタ１６１の値が、「あらかじめ定められた値」以上であると（ステップＡ２／Ｙ）、スレッド２１１は、不可分アクセス操作により、個別カウンタ１６１の値をインクリメントする（ステップＡ３）。
【００４８】
読み出した個別カウンタ１６１の値が、「あらかじめ定められた値」未満であると（ステップＡ２／Ｎ）、スレッド２１１は、不可分アクセス操作により、インジケータ１５０のＰ１をインクリメントする（ステップＡ４）。次に、スレッド２１１は、不可分アクセス操作により、個別カウンタ１６１の値をインクリメントする（ステップＡ５）。
【００４９】
スレッド２１１が個別カウンタ１６１の値をデクリメント（値を減少）する場合（ステップＡ１／Ｎ）、スレッド２１１は、不可分アクセス操作により、個別カウンタ１６１の値をデクリメントする（ステップＡ６）。
【００５０】
次に、デクリメントした結果の値が、「あらかじめ定められた値」未満であると（ステップＡ７／Ｙ）、スレッド２１１は、不可分アクセス操作により、インジケータ１５０のＰ１をデクリメントする（ステップＡ８）。
【００５１】
また、インジケータ１５０の値のみを読み出すことにより、個別カウンタ１６１〜１６４の全体の値が、「あらかじめ定められた値」以下であるかどうかを知ることができる。
【００５２】
次に、第１の実施の形態の効果について説明する。
【００５３】
第１の実施の形態は、インジケータ１５０が、スレッド２１１〜２４２が実行される処理部１３１〜１４３に対応する個別カウンタ１６１〜１６４の「あらかじめ定められた値」に縮退された値を含む構成である。
【００５４】
そして、インクリメントに際しては、対応する個別カウンタ１６１〜１６４の値が「あらかじめ定められた値」以上であると、スレッド２１１〜２４２は、自身に対応する個別カウンタ１６１〜１６４のみをインクリメントする構成である。
【００５５】
したがって、スレッド２１１〜２４２は、自身に対応しない他の処理部１３１〜１３４で実行されるスレッド２１１〜２４２と競合せずに、自身に対応する個別カウンタ１６１〜１６４のみをインクリメントできる。
【００５６】
また、対応する個別カウンタ１６１〜１６４の値が「あらかじめ定められた値」未満であると、スレッド２１１〜２４２は、インジケータ１５０の自身に対応するＰ１〜Ｐ４のみをインクリメントする構成である。すなち、インジケータ１５０には、個別カウンタ１６１〜１６４の値が縮退された形式で、即座に反映される構成である。
【００５７】
また、デクリメントに際しては、スレッド２１１〜２４２は、対応する個別カウンタ１６１〜１６４をデクリメントする。そして、デクリメントした結果の値が、「あらかじめ定められた値」未満であると、スレッド２１１〜２４２は、インジケータ１５０の自身に対応するＰ１〜Ｐ４のみをデクリメントする構成である。すなち、インジケータ１５０には、個別カウンタ１６１〜１６４の値が縮退された形式で、即座に反映される構成である。
【００５８】
以上から、第１の実施の形態は、複数のスレッド２１１〜２４２が、インクリメント、または、デクリメントを行う場合、個別カウンタ１６１〜１６４の更新の操作を効率的に実行できるという効果を持つ。
【００５９】
また、第１の実施の形態は、個別カウンタ１６１〜１６４全体の値が、「あらかじめ定められた値」以下になったことを直ちに知ることができるという効果を持つ。
【００６０】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
【００６１】
図３は、第２の実施の形態の構成を示すブロック図である。図３を参照すると、第２の実施の形態は、第１の実施の形態の一例である。
【００６２】
第２の実施の形態の情報処理システム１００は、ＣＰＵ３３１、ＣＰＵ３３２、ＣＰＵ３３３、ＣＰＵ３３４、共有バス４００、および、メモリ５００を含む。ＣＰＵ３３１〜３３４と、メモリ５００は、共有バス４００で接続される。ＣＰＵ３３１〜３３４は、Central Processing Unitであり、それぞれ、第１の実施の形態の処理部１３１〜１３４の一例である。
【００６３】
スレッド２１１、および、スレッド２１２は、ＣＰＵ３３１で実行される。スレッド２２１、および、スレッド２２２は、ＣＰＵ３３２で実行される。スレッド２３１、および、スレッド２３２は、ＣＰＵ３３３で実行される。スレッド２４１、および、スレッド２４２は、ＣＰＵ３３４で実行される。
【００６４】
個別カウンタ１６１〜１６４、および、インジケータ１５０は、メモリ５００に格納される。
【００６５】
図４は、ＣＰＵ３３１の構成を示すブロック図である。図４を参照すると、ＣＰＵ３３１は、プロセッサ・コア３４１、プロセッサ・コア３４２、プロセッサ・コア３４３、プロセッサ・コア３４４、および、キャッシュ３５０を含む。プロセッサ・コアの個数は、限定されない。
【００６６】
キャッシュ３５０は、プロセッサ・コア３４１〜３４４に共有される。ＣＰＵ３３２〜３３４も、ＣＰＵ３３１と同様な構成が可能である。
【００６７】
ＣＰＵ３３１〜３３４に割り当てられたスレッドは、それぞれのＣＰＵ３３１〜３３４に属するプロセッサ・コアであれば、どのプロセッサ・コアで実行されてもよい。
【００６８】
図５は、個別カウンタ１６１とインジケータ１５０の対応の一例を示す説明図である。図５を参照すると、インジケータ１５０のＰ１は、‘０’、‘１’、‘２’の３種類であり、それぞれ、個別カウンタ１６１の値が、‘０’、‘１’、‘２以上’であることを示す。
【００６９】
Ｐ２〜Ｐ４、および、個別カウンタ１６２〜１６４も同様である。ここで、「あらかじめ定められた値」は‘２’である。
【００７０】
次に、第２の実施の形態の動作について図面を参照して説明する。
【００７１】
図６は、第２の実施の形態の動作を示す動作説明図である。図６は、すべてのスレッド２１１〜２４１で実行可能なＣＡＳ操作の動作を示す。また、このＣＡＳ操作は、たとえば、cmpxchg命令を用いて、不可分アクセス操作として実行可能である。たとえば、不可分の実現は、バスのロック等を用いたハードウェア動作により可能である。
【００７２】
このＣＡＳ操作は、変数である対象アドレス（Ａ）、変数である旧値（Ｏ）を使用し、変数である新値（Ｎ）を格納する。説明をわかりやすくするため、代表して、ＣＰＵ３３１のプロセッサ・コア３４１で実行されるスレッド２１１が、ＣＡＳ操作を実行する場合について説明する。
【００７３】
図６を参照すると、スレッド２１１は、メモリ５００の対象アドレス（Ａ）で示される位置から変数である現在値（Ｃ）を読み出す（ステップＢ１）。次に、スレッド２１１は、読み出した現在値（Ｃ）と旧値（Ｏ）とを比較する（ステップＢ２）。
【００７４】
現在値（Ｃ）＝旧値（Ｏ）であると（ステップＢ２／Ｙ）、スレッド２１１は、対象アドレス（Ａ）で示される位置に、新値（Ｎ）を格納する（ステップＢ３）。すなわち、新値（Ｎ）が新たな現在値（Ｃ）となる。そして、スレッド２１１は、ＣＡＳ操作結果を成功として出力する（ステップＢ４）。
【００７５】
現在値（Ｃ）＝旧値（Ｏ）でないと（ステップＢ２／Ｎ）、スレッド２１１は、旧値（Ｏ）に、現在値（Ｃ）を代入する（ステップＢ５）。そして、スレッド２１１は、ＣＡＳ操作結果を失敗として出力する（ステップＢ６）。ここで、ステップＢ５の処理は、なくてもよい。
【００７６】
次に、インクリメントの動作について説明する。
【００７７】
図７は、第２の実施の形態の動作を示す動作説明図である。代表して、ＣＰＵ３３１のプロセッサ・コア３４１で実行されるスレッド２１１の動作について説明する。
【００７８】
図７を参照すると、スレッド２１１は、メモリ５００から個別カウンタ１６１の値を読み出し、読み出した個別カウンタ１６１の値を旧値（Ｏ）に代入する（ステップＳ１）。
【００７９】
読み出した個別カウンタ１６１の値≧２であると（ステップＳ２／Ｙ）、スレッド２１１は、図６に示されるＣＡＳ操作のルーチンを実行する（ステップＳ３）。ルーチンには、旧値（Ｏ）、および、対象アドレス（Ａ）が与えられる。対象アドレス（Ａ）は、個別カウンタ１６１のメモリ５００の位置を示すアドレスである。
【００８０】
また、現在値（Ｃ）は、対象アドレス（Ａ）で示される位置にある個別カウンタ１６１の値であり、新値（Ｎ）は、対象アドレス（Ａ）で示される位置から読み出された個別カウンタ１６１の値＋１である。
【００８１】
ＣＡＳ操作が失敗であると（ステップＳ４／Ｎ）、スレッド２１１は、ステップＳ１の処理に戻る。
【００８２】
このようにして、個別カウンタ１６１の値が、「あらかじめ定められた値」（＝２）以上の場合、個別カウンタ１６１の現在値（Ｃ）＝旧値（Ｏ）であると、個別カウンタ１６１がインクリメント（＋１）され、ＣＡＳ操作成功となる。また、個別カウンタ１６１の現在値（Ｃ）＝旧値（Ｏ）でないと、個別カウンタ１６１がインクリメントされず、ＣＡＳ操作失敗となる。
【００８３】
読み出した個別カウンタ１６１の値≧２でないと（ステップＳ２／Ｎ）、スレッド２１１は、メモリ５００からインジケータ１５０の値を読み出し、スレッド２１１は、読み出したインジケータ１５０の値を旧値（Ｏ）に代入する（ステップＳ５）。
【００８４】
読み出したインジケータ１５０のＰ１を判定し、Ｐ１＜２であると（ステップＳ６／Ｙ）、スレッド２１１は、図６に示されるＣＡＳ操作のルーチンを実行する（ステップＳ７）。ルーチンには、旧値（Ｏ）、および、対象アドレス（Ａ）が与えられる。対象アドレス（Ａ）は、インジケータ１５０のメモリ５００の位置を示すアドレスである。
【００８５】
ステップＳ７においては、インジケータ１５０全体に対して、不可分アクセス操作が実行される。
【００８６】
また、現在値（Ｃ）は、対象アドレス（Ａ）で示される位置にあるインジケータ１５０の値であり、新値（Ｎ）は、対象アドレス（Ａ）で示される位置から読み出されたインジケータ１５０のＰ１のみをインクリメント（＋１）とした値である。
【００８７】
ＣＡＳ操作が失敗であると（ステップＳ８／Ｎ）、スレッド２１１は、ステップＳ５の処理に戻る。ＣＡＳ操作が成功であると（ステップＳ８／Ｙ）、スレッド２１１は、不可分アクセス操作で、メモリ５００の個別カウンタ１６１をインクリメント（＋１）する（ステップＳ９）。
【００８８】
また、Ｐ１＜２でないと（ステップＳ６／Ｎ）、スレッド２１１は、ステップＳ５の処理に戻る。この場合、スレッド２１１は、プロセッサ・コア３４１の使用権を一時的に放棄してもよい。
【００８９】
このようにして、個別カウンタ１６１の値が、「あらかじめ定められた値」（＝２）未満の場合は、次のようになる。
【００９０】
インジケータ１５０のＰ１が、「あらかじめ定められた値」（＝２）未満であり、かつ、インジケータ１５０の現在値（Ｃ）＝旧値（Ｏ）であると、インジケータ１５０のＰ１がインクリメント（＋１）され、ＣＡＳ操作成功となる。そして、個別カウンタ１６１がインクリメントされる。
【００９１】
また、個別カウンタ１６１の現在値（Ｃ）＝旧値（Ｏ）でないと、個別カウンタ１６１がインクリメントされず、ＣＡＳ操作失敗となる。また、Ｐ１が、「あらかじめ定められた値」（＝２）未満でないと、ＣＡＳ操作は、実行されず、インジケータ１５０読み出し、判定の処理に戻る。
【００９２】
次に、デクリメントの動作について説明する。
【００９３】
図８は、第２の実施の形態の動作を示す動作説明図である。代表して、ＣＰＵ３３１のプロセッサ・コア３４１で実行されるスレッド２１１の動作について説明する。
【００９４】
図８を参照すると、スレッド２１１は、不可分アクセス操作で、メモリ５００から個別カウンタ１６１の値を読み出し、その値をデクリメント（−１）し、デクリメントした結果の値を、メモリ５００の個別カウンタ１６１に格納する（ステップＲ１）。
【００９５】
次に、スレッド２１１は、ステップＲ１でデクリメントした結果の値を調べる（ステップＲ２）。デクリメントした結果の値＜２であると（ステップＲ２／Ｙ）、スレッド２１１は、メモリ５００からインジケータ１５０の値を読み出し、Ｐ１のみをデクリメント（−１）したインジケータ１５０の値をメモリ５００に格納する（ステップＲ３）。
【００９６】
ステップＲ３は、不可分アクセス操作で実行される。デクリメントした結果の値≧２であると（ステップＲ２／Ｎ）、Ｐ１のデクリメントは、行われない。
【００９７】
このようにして、個別カウンタ１６１をデクリメントした結果の値が、「あらかじめ定められた値」（＝２）未満であると、インジケータ１５０のＰ１がクリメントされる。また、個別カウンタ１６１をデクリメントした結果の値が、「あらかじめ定められた値」（＝２）以上であると、インジケータ１５０のＰ１はインクリメントされない。
【００９８】
以上のようにして、すべてのスレッド２１１〜２４２は、インクリメント、デクリメントの処理を実行できる。
【００９９】
また、以上の構成から、インジケータ１５０のＰ１〜Ｐ４の値がすべて‘０’であれば、全カウンタ値（個別カウンタ１６１〜１６４の値の総和）は、‘０’と判定できる。また、Ｐ１〜Ｐ４のどれか一つの値が‘１’であり、その他の値が‘０’であれば、全カウンタ値は‘１’であると判定できる。
【０１００】
また、図８のステップＲ２において、個別カウンタ１６１をデクリメントした結果の値が‘２以上’であると、全カウンタ値も‘２以上’であると判定できる。したがって、この場合、デクリメント操作の結果の全カウンタ値は、‘０’でも‘１’でもないと判定できる。
【０１０１】
また、たとえば、デクリメント操作の後に、スレッド２１１〜２４２等が、全カウンタ値（たとえば、‘０’、‘１’、または、‘２以上’）を、アプリケーション・インタフェース（ＡＰＩ）を介して取得する構成が可能である。
【０１０２】
また、ステップＳ９、ステップＲ１、および、ステップＲ３では、ＣＡＳ操作ではない不可分アクセス操作の処理が行われているが、ＣＡＳ操作（図６）で代替する構成も可能である。
【０１０３】
また、たとえば、第２の実施の形態を、倉庫にある在庫を管理するアプリケーションプログラムで使用する場合、管理対象の物品の数を個別カウンタの値に設定する構成が可能である。アプリケーションプログラムは、管理対象の物品が倉庫に１個入庫されると、個別カウンタをインクリメントし、管理対象の物品が１個出荷されると、個別カウンタをデクリメントする。
【０１０４】
次に、第２の実施の形態の効果について説明する。
【０１０５】
第２の実施の形態は、第１の実施の形態の一例なので、第１の実施の形態と同一の効果を持つ。また、第２の実施の形態は、ＣＡＳ操作に、cmpxchg命令を用いると、実現が容易であるという効果を持つ。
【０１０６】
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。
【０１０７】
第３の実施の形態の全体の構成は、図３〜図４と同一である。図９は、第３の実施の形態の動作を示す動作説明図である。図９を参照すると、第３の実施の形態が、第２の実施の形態と異なる点は、インクリメントの動作において、スレッド２１１は、先にインジケータ１５０のＰ１に関する処理を行い、次に、個別カウンタ１６１に関する処理を行うことである。
【０１０８】
すなわち、ステップＳ５〜ステップＳ９の処理が先に実行され、Ｓ１〜ステップＳ４の処理が実行される。また、読み出したインジケータ１５０のＰ１を判定し、Ｐ１＜２でないと（ステップＳ６／Ｎ）、スレッド２１１は、Ｓ１からの処理を行う。
【０１０９】
次に、第３の実施の形態の効果について説明する。
【０１１０】
第３の実施の形態は、第２の実施の形態と同一の構成であり、処理の順序が異なるのみであるから、第２の実施の形態と同一の効果を持つ。
【０１１１】
上記の実施の形態の一部、または、全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１１２】
［付記１］
処理部に対応する個別カウンタと、
前記個別カウンタに対応するあらかじめ定められた値に縮退された値を含むインジケータと、
インクリメントに際し、先に、対応する前記個別カウンタの値を調べ、対応する前記個別カウンタの値が、前記あらかじめ定められた値以上であると、対応する前記個別カウンタの値をインクリメントし、対応する前記個別カウンタの値が、前記あらかじめ定められた値未満であると、次に、対応する前記個別カウンタに対応する前記インジケータの値をインクリメントし、かつ、対応する前記個別カウンタの値をインクリメントするスレッドを実行する前記処理部と、
を含むことを特徴とする情報処理システム。
【０１１３】
［付記２］
インクリメントに際し、対応する前記個別カウンタの値が前記あらかじめ定められた値未満で、かつ、対応する前記個別カウンタに対応する前記インジケータの値が、前記あらかじめ定められた値未満の場合に、対応する前記個別カウンタに対応する前記インジケータの値をインクリメントする前記スレッドを実行する前記処理部を含むことを特徴とする付記１の情報処理システム。
【０１１４】
［付記３］
インクリメントに際し、先に、対応する前記個別カウンタに対応する前記インジケータの値を調べ、対応する前記個別カウンタに対応する前記インジケータの値が、前記あらかじめ定められた値未満の場合に、対応する前記個別カウンタの値を調べる前記スレッドを実行する前記処理部を含むことを特徴とする付記２の情報処理システム。
【０１１５】
［付記４］
デクリメントに際し、対応する前記個別カウンタの値をデクリメントし、デクリメントした結果の値が、前記あらかじめ定められた値未満であると、対応する前記個別カウンタに対応する前記インジケータの値をデクリメントする前記スレッドを実行する前記処理部を含むことを特徴とする付記１、２、または、３の情報処理システム。
【０１１６】
［付記５］
前記個別カウンタ、または、前記インジケータのインクリメント、または、デクリメントを不可分アクセス操作により処理する前記スレッドを実行する前記処理部を含むことを特徴とする付記４の情報処理システム。
【０１１７】
［付記６］
ＣＡＳ操作により、前記個別カウンタの値、または、前記インジケータの値をインクリメントする前記スレッドを実行する前記処理部を含むことを特徴とする付記５の情報処理システム。
【０１１８】
［付記７］
インクリメントに際し、対応する個別カウンタの値が、前記あらかじめ定められた値以上であると、対応する前記個別カウンタの値をインクリメントし、対応する前記個別カウンタの値が、前記あらかじめ定められた値未満であると、対応する前記個別カウンタに対応するあらかじめ定められた値に縮退された値を含むインジケータの値をインクリメントし、かつ、対応する前記個別カウンタの値をインクリメントすることを特徴とする情報処理方法。
【０１１９】
［付記８］
インクリメントに際し、対応する前記個別カウンタの値が前記あらかじめ定められた値未満で、かつ、対応する前記個別カウンタに対応する前記インジケータの値が、前記あらかじめ定められた値未満の場合に、対応する前記個別カウンタに対応する前記インジケータの値をインクリメントすることを特徴とする付記７の情報処理方法。
【０１２０】
［付記９］
インクリメントに際し、先に、対応する前記個別カウンタに対応する前記インジケータの値を調べ、対応する前記個別カウンタに対応する前記インジケータの値が、前記あらかじめ定められた値未満の場合に、対応する前記個別カウンタの値を調べる前記スレッドを実行することを特徴とする付記８の情報処理方法。
【０１２１】
［付記１０］
デクリメントに際し、対応する前記個別カウンタの値をデクリメントし、デクリメントした結果の値が、前記あらかじめ定められた値未満であると、対応する前記個別カウンタに対応する前記インジケータの値をデクリメントする前記スレッドを実行することを特徴とする付記７、８、または、９の情報処理方法。
【０１２２】
［付記１１］
前記個別カウンタ、または、前記インジケータのインクリメント、または、デクリメントを不可分アクセス操作により処理する前記スレッドを実行することを特徴とする付記１０の情報処理方法。
【０１２３】
［付記１２］
ＣＡＳ操作により、前記個別カウンタの値、または、前記インジケータの値をインクリメントする前記スレッドを実行することを特徴とする付記１１の情報処理方法。
【０１２４】
［付記１３］
インクリメントに際し、対応する個別カウンタの値が、前記あらかじめ定められた値以上であると、対応する前記個別カウンタの値をインクリメントし、対応する前記個別カウンタの値が、前記あらかじめ定められた値未満であると、対応する前記個別カウンタに対応するあらかじめ定められた値に縮退された値を含むインジケータの値をインクリメントし、かつ、対応する前記個別カウンタの値をインクリメントする処理を、コンピュータに実行させることを特徴とするプログラム。
【０１２５】
［付記１４］
インクリメントに際し、対応する前記個別カウンタの値が前記あらかじめ定められた値未満で、かつ、対応する前記個別カウンタに対応する前記インジケータの値が、前記あらかじめ定められた値未満の場合に、対応する前記個別カウンタに対応する前記インジケータの値をインクリメントする処理を、コンピュータに実行させることを特徴とする付記１３のプログラム。
【０１２６】
［付記１５］
インクリメントに際し、先に、対応する前記個別カウンタに対応する前記インジケータの値を調べ、対応する前記個別カウンタに対応する前記インジケータの値が、前記あらかじめ定められた値未満の場合に、対応する前記個別カウンタの値を調べる処理を、コンピュータに実行させることを特徴とする付記１４のプログラム。
【０１２７】
［付記１６］
デクリメントに際し、対応する前記個別カウンタの値をデクリメントし、デクリメントした結果の値が、前記あらかじめ定められた値未満であると、対応する前記個別カウンタに対応する前記インジケータの値をデクリメントする処理を、コンピュータに実行させることを特徴とする付記１３、１４、または、１５のプログラム。
【０１２８】
［付記１７］
前記個別カウンタ、または、前記インジケータのインクリメント、または、デクリメントを不可分アクセス操作により行う処理を、コンピュータに実行させることを特徴とする付記１６のプログラム。
【０１２９】
［付記１８］
ＣＡＳ操作により、前記個別カウンタの値、または、前記インジケータの値をインクリメントする処理を、コンピュータに実行させることを特徴とする付記１７のプログラム。
【符号の説明】
【０１３０】
１００    情報処理システム
１３１    処理部
１３２    処理部
１３３    処理部
１３４    処理部
１５０    インジケータ
１６１    個別カウンタ
１６２    個別カウンタ
１６３    個別カウンタ
１６４    個別カウンタ
２１１    スレッド
２１２    スレッド
２２１    スレッド
２２２    スレッド
２３１    スレッド
２３２    スレッド
２４１    スレッド
２４２    スレッド
３３１    ＣＰＵ
３３２    ＣＰＵ
３３３    ＣＰＵ
３３４    ＣＰＵ
３４１    プロセッサ・コア
３４２    プロセッサ・コア
３４３    プロセッサ・コア
３４４    プロセッサ・コア
３５０    キャッシュ
４００    共有バス
５００    メモリ
【図１】
2015090632.tif 000003
【図２】
2015090632.tif 000004
【図３】
2015090632.tif 000005
【図４】
2015090632.tif 000006
【図５】
2015090632.tif 000007
【図６】
2015090632.tif 000008
【図７】
2015090632.tif 000009
【図８】
2015090632.tif 000010
【図９】
2015090632.tif 000011