(57)【要約】【課題】  同一キャッシュブロックへのアクセス競合によるキャッシュミスを防止することができると共に、アクセス競合による待ち時間を最小限にすることができるようにする。【解決手段】  排他制御では、図３に示すように、キャッシュブロック単位にロックアドレスを取得する（排他制御としてのロックを行う）。この排他処理で、２番目にプロセッサ“０１”により、プロセッサ“００”と同一アドレスの排他制御が行われると、エントリ００がすでにロックされた「ロック取得状態」であれば、ロックの取得を中止し、他の割り込み処理など、より優先順位の高いプロセスの実行を行う。【選択図】  図６
2006268781.tif 000002
【特許請求の範囲】
【請求項１】
複数の計算手段を備え、排他制御を行う機能を備えた計算機システムであって、
キャッシュブロック単位にロックアドレスを設定するロックアドレス設定手段と、
１つの計算手段によりロックアドレスが取得されてロック取得状態となった後で当該ロックアドレスに他の計算手段からロック取得要求が行われるアクセス競合が発生した場合に、当該他の計算手段に優先順位のより高い処理を先に実行させる優先処理実行手段とを備えたことを特徴とする計算機システム。
【請求項２】
キャッシュのエントリアドレスが存在しない場合に当該キャッシュのエントリアドレスを算出するキャッシュエントリアドレス算出手段を備え、
前記ロックアドレス設定手段は、キャッシュのエントリアドレスが存在しない場合、前記キャッシュエントリアドレス算出手段により算出されたエントリアドレスを用いてロックアドレスを設定することを特徴とする請求項１記載の計算機システム。
【請求項３】
記憶手段における排他制御に用いられる排他制御領域を備え、
前記排他制御領域は、前記複数の計算手段の数を最大エントリ数とすることを特徴とする請求項１または２記載の計算機システム。
【請求項４】
複数の計算手段を備え、排他制御を行う機能を備えたシステムにおける排他制御方法であって、
１つの計算手段によりキャッシュブロック単位のロックアドレスが取得されてロック取得状態となる排他制御工程と、
前記排他制御工程の後で当該ロックアドレスに他の計算手段からロック取得要求が行われるアクセス競合が発生した場合に、当該他の計算手段が優先順位のより高い処理を先に実行する優先処理実行工程とを備えたことを特徴とする排他制御方法。
【請求項５】
キャッシュのエントリアドレスが存在しない場合に当該キャッシュのエントリアドレスを算出するキャッシュエントリアドレス算出工程を備え、
前記排他制御工程では、キャッシュのエントリアドレスが存在しない場合、前記キャッシュエントリアドレス算出工程により算出されたエントリアドレスを用いてロックアドレスを設定することを特徴とする請求項４記載の排他制御方法。
【請求項６】
前記優先処理実行工程では、排他制御に用いられる排他制御領域に対して、前記複数の計算手段の数を最大エントリ数とすることを特徴とする請求項４または５記載の排他制御方法。
【請求項７】
複数の計算手段を備え、排他制御を行う機能を備えたシステムにおける排他制御プログラムであって、
コンピュータに、
１つの計算手段によりキャッシュブロック単位のロックアドレスが取得されてロック取得状態となる排他制御処理と、
前記排他制御処理の後で当該ロックアドレスに他の計算手段からロック取得要求が行われるアクセス競合が発生した場合に、当該他の計算手段が優先順位のより高い処理を先に実行する優先処理実行処理とを実行させることを特徴とする排他制御プログラム。
【請求項８】
キャッシュのエントリアドレスが存在しない場合に当該キャッシュのエントリアドレスを算出するキャッシュエントリアドレス算出処理をさらに実行させ、
前記排他制御処理では、キャッシュのエントリアドレスが存在しない場合、前記キャッシュエントリアドレス算出処理により算出されたエントリアドレスを用いてロックアドレスを設定することを特徴とする請求項７記載の排他制御プログラム。
【請求項９】
前記優先処理実行処理では、排他制御に用いられる排他制御領域に対して、前記複数の計算手段の数を最大エントリ数とすることを特徴とする請求項７または８記載の排他制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、排他制御を行う機能を備えた計算機システム、排他制御方法、およびプログラムに関する。
【背景技術】
【０００２】
従来より、計算機システムでは、複数のプロセッサ（計算手段）が同一データへアクセスするために生じるデータの矛盾を回避する方法として、排他制御が用いられている。
【０００３】
こうした従来の排他制御におけるロック取得イメージを図８に示す。
この図８に示すように、一般的な排他制御では、ロックアドレス１とロックアドレス２といった複数のロックが同一キャッシュブロックへアクセスする。
【０００４】
また、従来の排他制御として、処理ユニットによりロック指示情報をキャッシュブロックに対応づけて登録し、他のプロセッサが同一データへアクセスした場合に登録済みのロック指示情報によりアクセスの可否を判定し制御するものがある（例えば、特許文献１参照）。
【特許文献１】特開平６−１７５９８１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、図８により上述した従来の排他制御では、同一キャッシュブロックへのアクセスが競合した場合、排他制御構造体１と排他制御構造体２の各々のメモリストアにより異なる排他制御構造体でのメモリリード時のキャッシュミス要因となってしまう虞があった。このキャッシュミスは、メモリリード量に比例して増加する。
【０００６】
また、このように同一キャッシュブロックへのアクセス競合による待ち合わせが発生してしまうと、マルチプロセッサとしての処理効率が低下してしまうという問題があった。
【０００７】
また、上述した特許文献１のものは、上述した同一キャッシュブロックへのアクセス競合によるキャッシュミスの防止についてまで考慮されたものではなかった。
【０００８】
本発明はこのような状況に鑑みてなされたものであり、同一キャッシュブロックへのアクセス競合によるキャッシュミスを防止することができると共に、アクセス競合による待ち時間を最小限にすることができる計算機システム、排他制御方法、およびプログラムを提供することをを目的とする。
【課題を解決するための手段】
【０００９】
かかる目的を達成するために、本発明の第１の態様としての計算機システムは、複数の計算手段を備え、排他制御を行う機能を備えた計算機システムであって、キャッシュブロック単位にロックアドレスを設定するロックアドレス設定手段と、１つの計算手段によりロックアドレスが取得されてロック取得状態となった後で当該ロックアドレスに他の計算手段からロック取得要求が行われるアクセス競合が発生した場合に、当該他の計算手段に優先順位のより高い処理を先に実行させる優先処理実行手段（例えば、図６のステップＳ１４）とを備えたことを特徴とする。
【００１０】
キャッシュのエントリアドレスが存在しない場合に当該キャッシュのエントリアドレスを算出するキャッシュエントリアドレス算出手段（例えば、図２のステップＳ２）を備え、上記したロックアドレス設定手段は、キャッシュのエントリアドレスが存在しない場合、キャッシュエントリアドレス算出手段により算出されたエントリアドレスを用いてロックアドレスを設定することが好ましい。
【００１１】
記憶手段における排他制御に用いられる排他制御領域を備え、上記した排他制御領域は、上記した複数の計算手段の数を最大エントリ数とすることが好ましい。
【００１２】
また、本発明の第２の態様としての排他制御方法は、複数の計算手段を備え、排他制御を行う機能を備えたシステムにおける排他制御方法であって、１つの計算手段によりキャッシュブロック単位のロックアドレスが取得されてロック取得状態となる排他制御工程と、排他制御工程の後で当該ロックアドレスに他の計算手段からロック取得要求が行われるアクセス競合が発生した場合に、当該他の計算手段が優先順位のより高い処理を先に実行する優先処理実行工程（例えば、図６のステップＳ１４）とを備えたことを特徴とする。
【００１３】
キャッシュのエントリアドレスが存在しない場合に当該キャッシュのエントリアドレスを算出するキャッシュエントリアドレス算出工程（例えば、図２のステップＳ２）を備え、上記した排他制御工程では、キャッシュのエントリアドレスが存在しない場合、キャッシュエントリアドレス算出工程により算出されたエントリアドレスを用いてロックアドレスを設定することが好ましい。
【００１４】
上記した優先処理実行工程では、排他制御に用いられる排他制御領域に対して、上記した複数の計算手段の数を最大エントリ数とすることが好ましい。
【００１５】
また、本発明の第３の態様としての排他制御プログラムは、複数の計算手段を備え、排他制御を行う機能を備えたシステムにおける排他制御プログラムであって、コンピュータに、１つの計算手段によりキャッシュブロック単位のロックアドレスが取得されてロック取得状態となる排他制御処理と、排他制御処理の後で当該ロックアドレスに他の計算手段からロック取得要求が行われるアクセス競合が発生した場合に、当該他の計算手段が優先順位のより高い処理を先に実行する優先処理実行処理（例えば、図６のステップＳ１４）とを実行させることを特徴とする。
【００１６】
キャッシュのエントリアドレスが存在しない場合に当該キャッシュのエントリアドレスを算出するキャッシュエントリアドレス算出処理（例えば、図２のステップＳ２）をさらに実行させ、上記した排他制御処理では、キャッシュのエントリアドレスが存在しない場合、キャッシュエントリアドレス算出処理により算出されたエントリアドレスを用いてロックアドレスを設定することが好ましい。
【００１７】
上記した優先処理実行処理では、排他制御に用いられる排他制御領域に対して、上記した複数の計算手段の数を最大エントリ数とすることが好ましい。
【発明の効果】
【００１８】
以上のように、本発明によれば、同一キャッシュブロックへのアクセス競合によるキャッシュミスを防止することができると共に、アクセス競合による待ち時間を最小限にすることができる。
【発明を実施するための最良の形態】
【００１９】
次に、本発明に係る計算機システム、排他制御方法、およびプログラムを適用した一実施形態について、図面を用いて詳細に説明する。
本実施形態の計算機システムは、排他制御動作における同一キャッシュブロックへのアクセス競合を削減しキャッシュ常駐率を高めることで、マルチプロセッサの処理効率を向上させる好適なものを例示している。
【００２０】
まず、図１を参照して、本実施形態におけるキャッシュエントリアドレスを利用した排他制御方法の概要について説明する。
キャッシュエントリアドレスの生成手段１１は、プロセッサ１のキャッシュ１０の構成情報が存在するか調査し、キャッシュ１０のキャッシュエントリアドレスが存在する場合その情報をキャッシュ情報記憶部２１へ格納する。キャッシュ１０の構成情報が存在しない場合は、キャッシュ構造を調査するための測定プログラムを起動しキャッシュ１０のキャッシュエントリアドレスを算出してキャッシュ情報記憶部２１へ格納する。
【００２１】
また、本実施形態では、複数プロセッサでアクセスするデータ領域の排他制御時に、上記したキャッシュ１０の構成情報が存在しない場合であっても、キャッシュエントリアドレスの生成手段１１により算出されたキャッシュエントリアドレスに対応する排他制御領域のアドレスビットを利用してキャッシュブロック単位に排他制御を行い、同一キャッシュブロックへのアクセス競合を完全に排除しマルチプロセッサ性能を向上させる。また、排他制御領域のアクセス競合時には、他の優先度の高い割り込み処理等を優先して処理することによりマルチプロセッサの処理効率を向上させる。
【００２２】
次に、本実施形態の構成について、図面を参照して詳細に説明する。
図１を参照すると、本実施形態としての計算機システムは、プログラムを実行するプロセッサ１と、プログラムやデータを記憶する記憶装置２と、診断装置３と、キャッシュエントリアドレスの生成手段１１と、排他制御の実行手段１２とを備えて構成されている。
【００２３】
プロセッサ１は、キャッシュエントリアドレスの生成手段１１と、排他制御の実行手段１２とを含む。
記憶装置２は、プログラム記憶部２０と、キャッシュエントリアドレスの生成手段１１で生成したキャッシュエントリアドレスを格納するキャッシュ情報記憶部２１と、排他制御領域２２と、排他制御が必要なデータアクセス領域２３とを含む。プログラム記憶部２０は、キャッシュエントリアドレス生成手段１１と排他制御の実行手段１２とのプログラムを格納する。
診断装置３は、プロセッサの障害発生時に障害処理を行う。
【００２４】
上述した各部分は、それぞれ概略、次のように動作する。
キャッシュエントリアドレスの生成手段１１は、図２に示すように、プロセッサ１のキャッシュ１０の構成情報が存在するか調査し（ステップＳ１）、キャッシュ１０のキャッシュエントリアドレスが存在する場合（ステップＳ１；Ｙｅｓ）、その情報をキャッシュ情報記憶部２１へ格納する（ステップＳ３）。
【００２５】
キャッシュ１０の構成情報が存在しない場合（ステップＳ１；Ｎｏ）、キャッシュ構造を調査するための測定プログラムを起動し、キャッシュ１０のキャッシュエントリアドレスを算出して（ステップＳ２）、キャッシュ情報記憶部２１へ格納する（ステップＳ３）。
【００２６】
また、キャッシュエントリアドレスの生成手段１１は、システムの立ち上げ時等に一度だけ動作し、キャッシュ１０のキャッシュエントリアドレスとシステムに接続されるプロセッサ台数から排他制御に必要なロックエントリアドレスをキャッシュ情報記憶部２１へ格納する。
排他制御の実行時には、キャッシュ情報記憶部２１へ格納したロックエントリ有効情報を排他制御情報として使用する（ステップＳ４）。
【００２７】
本実施形態における排他制御では、図３に示すように、キャッシュブロック単位にロックアドレスを取得する（排他制御としてのロックを行う）。すなわち、本発明の実施形態では、図８により上述した従来の排他制御におけるロックアドレス２，４を使用せず、キャッシュブロックに対応するロックアドレスを生成するようにしている。
なお、図３に示す例では、ブロック容量３２ｂｙｔｅ、最大プロセッサ数４台の場合を例として示している。
【００２８】
また、本実施形態では、ロックエントリアドレスとして、キャッシュブロックに対応したロックアドレスをロックエントリアドレスとして使用している。
この本実施形態によるロックエントリアドレスの取得例を図４に示す。
【００２９】
また、排他制御の実行手段１２は、排他制御が必要なデータアクセス領域２３へアクセスする場合に、キャッシュ情報記憶部２１へ格納されているロックエントリ有効情報に該当するアドレスビットに対応するアドレスを抽出し排他制御領域２２のキャッシュブロックに対応するエントリを算出する。また、この排他制御領域２２のエントリ数は、全てのキャッシュブロック分を確保する必要はないため、同時にメモリアクセスを行うシステムのプロセッサ台数と同数のエントリを最大エントリ数として確保するだけで良い。排他制御を取得する場合には、排他制御領域２２の該当するエントリを読み出しロック取得状態“ＦＦ以外”であれば、データアクセス領域へのアクセスを中止し保留されている処理や優先度の高いプロセスを起動する。ロック未取得状態“ＦＦ”であれば、排他制御領域の該当するエントリがロック取得状態であることを示す“プロセッサ番号”を格納する。
【００３０】
次に、本実施形態による動作について、図面を参照して詳細に説明する。
図５は、本発明による排他制御領域のレイアウト例を示す図である。
【００３１】
以下の動作説明では、キャッシュブロックは３２ｂｙｔｅであることと仮定する。また、アドレスのビット幅は３２ｂｉｔ、有効なプロセッサの台数は４台とし、プロセッサの番号は、００〜０３として説明する。
【００３２】
システムの立ち上げ時に、プログラム記憶部２０からキャッシュエントリアドレスの生成手段１１が起動されると、キャッシュブロックの調査が行われる。キャッシュエントリアドレスの生成手段１１は、キャッシュ１０のキャッシュブロックが３２ｂｙｔｅであると判断すると、図４の〈例１〉に示すように、メモリへアクセスするアドレスビットのキャッシュブロック単位のアドレスの下位ｂｉｔから有効なプロセッサの台数に対応する２５〜２６ｂｉｔの２ｂｉｔ（プロセッサの台数が２の階乗でなければ、２の階乗に切り上げる）をロックエントリアドレスの有効ビットのマスク情報をロックエントリ情報としてキャッシュ情報記憶部２１へ格納する。
また、排他制御領域２２に、排他制御に必要なエントリをキャッシュブロック単位に有効なプロセッサ台数分確保する。このとき、ロック取得状態は未取得状態“ＦＦ”に初期化しておく。
【００３３】
次に、本実施形態による排他制御の動作について、図６のフローチャートを参照して説明する。
まず、プロセッサ“００”にてデータアクセス領域にアクセスするアドレス（ビット２５〜２６＝“００”）への排他制御が実行されると、排他制御の実行手段１２にてキャッシュ情報記憶部２１からロックエントリ情報（図４〈例２〉参照）を取り出し、ロックエントリアドレスを生成する（ステップＳ１１）。
該当するエントリ００の排他制御領域２２がロック未取得状態“ＦＦ”の時にロック取得状態“００”とする。この時、有効なプロセッサの台数が４台であるため、ロックエントリは、最大４エントリ確保されている。このときロックエントリアドレスは０と仮定し、図５で示すロックエントリ００以外の領域は、ロック取得状態と仮定する。
【００３４】
この状態でプロセッサ“０１”により、プロセッサ“００”と同一アドレスの排他制御が行われると、まず排他制御領域２２の該当するエントリ００を読み出す（ステップＳ１２）。このとき、エントリ００は、すでにロックされた「ロック取得状態」であるため（ステップＳ１３；Ｙｅｓ）、ロックの取得を中止し、他の割り込み処理など、より優先順位の高いプロセスの実行を行う（ステップＳ１４）。
【００３５】
こうした割り込み処理など、実行要求がなされている排他制御よりも優先順位の高い処理の実行が完了すると（ステップＳ１５；Ｙｅｓ）、再び上述したステップＳ１２の処理から繰り返し、エントリ００が「ロック取得状態」でなくなっていれば、上述したステップＳ１１と同様に、排他制御の実行手段１２がキャッシュ情報記憶部２１からロックエントリ情報を取り出し、プロセッサ“０１”についてロックエントリアドレスを生成し、キャッシュ情報記憶部２１に格納する。
【００３６】
ここで仮に、プロセッサ“００”によりエントリ００が「ロック取得状態」となっている状態で、プロセッサ“０１”がロックエントリアドレス（“０１”）に対応するアドレスへの排他制御を実行すると、ロック未取得状態であるため、ロック取得が可能となる。
【００３７】
次に、１台のプロセッサで障害が発生した時の動作について、図７のフローチャートを参照して説明する。この説明では、プロセッサ“００”で障害が発生したと仮定する。
【００３８】
プロセッサ“００”の障害が診断装置３に通知されると、排他制御領域２２の４つのロックエントリを検索する（ステップＳ２１）。ロックエントリ００には障害が発生したプロセッサの番号が格納されているため、診断装置３はそのプロセッサ番号のロックエントリ情報におけるロックを解放する（ステップＳ２２）。
【００３９】
このようにして、キャッシュブロックの登録アドレス単位に排他制御を行うことにより、排他制御が必要なデータアクセス領域２３へのアクセスを完全に抑止しキャッシュ常駐率を高めると共に、排他制御時のアクセス競合を最小化することによりマルチプロセッサの処理効率を向上させることができる。また、排他制御の高速化のために必要な専用の処理ユニットを有することなくＳＷ（ソフトウェア）のバイナリコードを維持しつつプロセッサのキャッシュ構造に応じた最適な排他制御を行うことも可能となる。
【００４０】
以上のように、上述した本発明の実施形態によれば、以下の効果を得ることができる。
第１の効果は、排他制御を行うためのアクセス競合による待ちあわせ時間を最小限に出来ることである。
その理由は、キャッシュブロックの登録アドレス単位に排他制御を行うためである。
【００４１】
第２の効果は、排他制御するためにキャッシュメモリ内などに専用の処理ユニットを設ける必要がないことである。
その理由は、プログラムとして排他制御手段の実現が可能なためである。このため、排他制御を行うためのハードウェアリソースの不要な増加を抑えることができる。
【００４２】
第３の効果は、キャッシュ構造に応じて排他制御で使用するキャッシュブロックを容易に変更でき、キャッシュ構造の変化に柔軟に対応できることである。
その理由は、算出したキャッシュ情報により排他制御しているためである。
このように、キャッシュの構造に合わせてロック指示情報をキャッシュメモリ内の処理ユニットへ登録しないため、キャッシュ容量やエントリの変更が生じた場合であっても、ハードウェアリソースの変更を生じさせないようにすることができる。
【００４３】
第４の効果は、ＳＷの実行ファイル（バイナリコード）を変更せずにプロセッサのキャッシュ構造に適した排他制御が可能なことである。
その理由は、プロセッサのキャッシュ情報を事前に調査し排他制御情報として利用しているためである。
【００４４】
第５の効果は、排他制御で使用するキャッシュブロック数を最小化できることである。
その理由は、プロセッサ台数に応じて排他制御に必要なキャッシュブロックの使用量を算出しているためである。
【００４５】
このように、本発明の実施形態によれば、排他制御によるアクセス競合が生じた場合、割り込みや他の処理を優先して処理するため、アクセス競合による待ち時間を最小限にすることができる。
【００４６】
また、図３により上述したようにキャッシュブロック単位にロックアドレスを取得するようにしているため、同一キャッシュブロックへのアクセス競合によるキャッシュミスを確実に防止することができる。
【００４７】
また、発明の他の実施形態として、上述した実施形態のロックエントリアドレスビットの空きビットをロック種別表示として利用することにより、複数のロック制御も実現することが可能となる。
【００４８】
以上のように、本発明の実施形態は、マルチプロセッサシステムの処理効率を向上するといった用途に適用できる。また、プログラムのバイナリコードを変更することなくプロセッサに適した排他制御を実現する機能といった用途にも適用可能である。
【００４９】
なお、上述した各実施形態は本発明の好適な実施形態であり、本発明はこれに限定されることなく、本発明の技術的思想に基づいて種々変形して実施することが可能である。
例えば、上述した実施形態では、プロセッサ（計算手段）を“００”〜“０３”の４台備えることとして説明したが、複数のプロセッサを備えていればこの数に限定されず、いくつであってもよい。
【００５０】
また、上述した各実施形態では、プログラムは、プログラム記憶部２０に格納されることとして説明したが、コンピュータが読み取り可能な記録媒体であればこのものに限定されず、例えば、フロッピー（登録商標）ディスク，ハードディスク，光ディスク，光磁気ディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，磁気テープ，不揮発性のメモリカード，ＥＥＰＲＯＭ等に格納されてもよい。
すなわち、本発明の各実施形態による上述した各機能が、上述した記録媒体から供給されるプログラムによって、各種計算機システムのＣＰＵなどが処理を行うことにより実現されてもよい。
そして、その場合、上述した記録媒体により、あるいはネットワークを介して外部の記録媒体から、プログラムを含む情報群を出力装置に供給される場合でも本発明は適用されるものである。
すなわち、記録媒体から読み出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記憶した記録媒体および該記録媒体から読み出された信号は本発明を構成することになる。
【００５１】
この本発明に係るプログラムによれば、当該プログラムによって制御されるコンピュータに、上述した本発明に係る各実施形態としての計算機システムにおける各機能を実現させることができる。
【図面の簡単な説明】
【００５２】
【図１】本発明の実施形態としての計算機システムの構成例を示す図である。
【図２】本実施形態でのキャッシュへのアクセス動作を示すフローチャートである。
【図３】本実施形態による排他制御でのロック取得イメージを示す図である。
【図４】本実施形態でのロックエントリアドレスの例を示す図である。
【図５】本実施形態による排他制御領域のレイアウト例を示す図である。
【図６】本実施形態による排他制御動作を示すフローチャートである。
【図７】本実施形態による障害発生時の動作を示すフローチャートである。
【図８】従来の排他制御でのロック取得イメージを示す図である。
【符号の説明】
【００５３】
１    プロセッサ
１０    キャッシュ
１１    キャッシュエントリアドレスの生成手段
１２    排他制御の実行手段
２    記憶装置
２０    プログラム記憶部
２１    キャッシュ情報記憶部
２２    排他制御領域
２３    データアクセス領域
３    診断装置
【図１】
2006268781.tif 000003
【図２】
2006268781.tif 000004
【図３】
2006268781.tif 000005
【図４】
2006268781.tif 000006
【図５】
2006268781.tif 000007
【図６】
2006268781.tif 000008
【図７】
2006268781.tif 000009
【図８】
2006268781.tif 000010