(57)【特許請求の範囲】
【請求項１】
複数のプロセッサと、
前記複数のプロセッサからアクセスされる共有リソースと、
プロセッサから発行される前記共有リソースに対するロック命令、アンロック命令の受信に応じて、前記共有リソースの同期制御を行うセマフォ制御回路と、を備え、
前記セマフォ制御回路は、あるロック命令にかかる前記共有リソースのロック時間をカウントし、前記共有リソースのロック中にロック命令を発行したプロセッサの命令送信順序を保持し、確定した前記ロック時間と、前記命令送信順序と、に基づいて前記共有リソースに対するロックに失敗した各プロセッサのロック命令再発行までの待ち時間を算出して通知し、
前記セマフォ制御回路は、
前記共有リソースのロックに成功した前記ロック命令に関する第１エントリをｎ個（ｎは１以上の整数）保持する第１バッファと、
前記共有リソースのロックに失敗した前記ロック命令に関する第２エントリをｎ個（ｎは１以上の整数）保持する第２バッファと、
前記第１及び第２エントリと、入力されたロック命令との比較に応じて、当該ロック命令に対するロックの成否を判定し、ロック失敗の場合に前記待ち時間を算出する判定回路と、を備える、ことを特徴とする、マルチプロセッサシステム。
【請求項２】
前記第１エントリは、ロックの有効性を示す第１Ｖビット値と、前記共有リソースのアドレスを示す第１アドレスと、前記ロック時間をカウントする第１ロック時間と、を有する構成であり、
前記第２エントリは、ロックが失敗したプロセッサがあるか否かを示す第２Ｖビット値と、前記共有リソースのアドレスを示す第２アドレスと、プロセッサ毎のロック命令の処理状態を示すステータスフラグと、プロセッサ毎のロック命令の入力順序を示す受付番号と、現在ロック中のロック命令のアンロック後にインクリメントされ、アンロック後にロックが許可されるロック命令の識別情報を示す優先番号と、確定した前記ロック時間を保持する第２ロック時間と、を有する構成であることを特徴とする請求項１に記載のマルチプロセッサシステム。
【請求項３】
前記判定回路は、
入力されたロック命令に含まれるアドレスに基づいて、前記第１バッファと、前記第２バッファからそれぞれ対応する前記第１、前記第２エントリを取得し、
当該第１、第２エントリにかかる前記第１及び第２Ｖビット値が共に無効値（０）である場合、または当該第１エントリにかかる前記第１Ｖビット値が無効値（０）でありであり、当該第２エントリにかかる前記第２Ｖビット値が有効値（１）であり、かつ当該第２エントリにかかる前記受付番号と前記優先番号とが同じ場合、入力されたロック命令に対してロックを許可し、それ以外の場合にはロックを許可しないことを特徴とする、請求項２に記載のマルチプロセッサシステム。
【請求項４】
前記判定回路は、
ロックに失敗した各プロセッサに対し、当該プロセッサにかかる前記受付番号から前記優先番号を減算した値に前記第２ロック時間の値を乗算した値を前記待ち時間とすることを特徴とする請求項３に記載のマルチプロセッサシステム。
【請求項５】
前記判定回路は、
前記第２ロック時間に初期値が設定されている場合、ロックに失敗した各プロセッサに対し、前記待ち時間として０（待ち合わせなし）を通知することを特徴とする請求項２乃至請求項４のいずれか１項に記載のマルチプロセッサシステム。
【請求項６】
複数のプロセッサと、前記複数のプロセッサからアクセスされる共有リソースと、を備えるマルチプロセッサにおいて、プロセッサから発行される前記共有リソースに対するロック命令及びアンロック命令の受信に応じて、前記共有リソースの同期制御を行うマルチプロセッサの制御方法であって、
あるロック命令の前記共有リソースのロック時間をカウントし、前記共有リソースのロック中にロック命令を送信したプロセッサの命令送信順序を保持し、確定した前記ロック時間と、前記命令送信順序と、に基づいて、前記共有リソースに対するロックに失敗した各プロセッサのロック命令再発行までの待ち時間を算出して通知し、
前記待ち時間の算出は、
前記共有リソースのロックに成功した前記ロック命令に関する第１エントリをｎ個（ｎは１以上の整数）保持し、
前記共有リソースのロックに失敗した前記ロック命令に関する第２エントリをｎ個（ｎは１以上の整数）保持し、
前記第１及び第２エントリと、入力されたロック命令との比較に応じて、当該ロック命令に対するロックの成否を判定して、ロック失敗の場合に前記待ち時間を算出する、マルチプロセッサの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はマルチプロセッサシステム、及びマルチプロセッサシステムの制御方法に関し、特に共有リソースを扱うマルチプロセッサシステム、及びマルチプロセッサシステムの制御方法に関する。
【背景技術】
【０００２】
近年、複数のＣＰＵ（Central Processing Unit）を有するマルチコア構成のプロセッサシステムが多く使用されている。これらのプロセッサシステムにおけるＣＰＵ数は、年々増加している。そのため、多くのＣＰＵを搭載するマルチプロセッサシステムでは、ＣＰＵ間の排他制御がシステム全体の性能に大きな影響を与えている。排他制御が適切に行われない場合、ＣＰＵ数を増加してもシステム全体の性能が十分に向上しない恐れもある。マルチコア構成のプロセッサシステムにおいて、排他制御、すなわちセマフォの使用効率を改善することによりシステム全体の性能向上を実現できる。
【０００３】
以下に、一般的なマルチコアシステムの構成、及び当該システムでのセマフォを用いた排他制御等について説明する。図１は、一般的なマルチプロセッサシステムの構成を示すブロック図である。当該マルチプロセッサシステムは、ＣＰＵ１〜ｎと、ＣＰＵ１〜ｎからアクセス可能なメモリ３０と、ＣＰＵ１〜ｎからメモリ３０へのアクセスを制御するメモリコントローラ２０と、を有する。
【０００４】
ＣＰＵ１〜ｎは、それぞれ独立してメモリ３０にアクセスすることができる。そのため、ＣＰＵ１〜ｎがメモリ３０の共有メモリ（アドレス）にアクセスする場合、複数のＣＰＵが同時に共有メモリにアクセスしないように排他制御処理を行う必要がある。このＣＰＵ間で行われる排他制御は、一般的にセマフォと呼ばれる共通フラグを用いて行われる。各ＣＰＵは、セマフォを獲得するための命令（ＬＯＣＫ命令）を実行し、共有メモリへのアクセス可否を判定する。
【０００５】
以下、図８のフローチャートを参照して具体的な排他制御の動作の流れを説明する。はじめに、あるＣＰＵは、セマフォを獲得するためにＬＯＣＫ命令を発行する（Ｓ１０００）。ＬＯＣＫ命令の処理部は、ＬＯＣＫ命令に付与されるアドレスのセマフォを索引し、セマフォの値が１の場合、ＬＯＣＫ失敗（セマフォ獲得失敗）を発行元のＣＰＵに返却する（Ｓ１００１：ＮＯ）。一方、セマフォの値が０の場合、ＬＯＣＫ命令の処理部は、セマフォの値を１に更新して、ＬＯＣＫ成功（セマフォ獲得成功）を発行元のＣＰＵに返却する（Ｓ１００１：ＹＥＳ）。
【０００６】
ＣＰＵは、ＬＯＣＫ成功の通知を受け取った場合、共有メモリにアクセスし（Ｓ１００２）、アクセス後にＵＮＬＯＣＫ命令を発行してセマフォの値を０にリセットする、すなわちセマフォを解放する（Ｓ１００３）。一方、ＬＯＣＫ失敗の通知を受け取った場合、ＣＰＵは、一定時間の待ち合わせを行い（Ｓ１００４）、待ち合わせ後にＬＯＣＫ命令を再発行する。
【０００７】
次に、ＣＰＵ１〜４を有する一般的なマルチプロセッサシステムにおけるセマフォの処理フローを図９及び図１０を参照して説明する。図９及び図１０は、セマフォにかかる各ＣＰＵの動作を示すフロー図である。図９及び図１０における縦軸は、時間軸（単位はＳｔｅｐ）を示す。ＣＰＵ１〜４の発行するＬＯＣＫ命令は、全て同一アドレスに対する命令とする。図９は、ＬＯＣＫ失敗からＬＯＣＫ命令の再発行までの時間が短い場合のフローを示す。図１０は、ＬＯＣＫ失敗からＬＯＣＫ命令の再発行までの時間が長い場合のフローを示す。
【０００８】
図９において、ＣＰＵ２〜４は、Ｓｔｅｐ４においてＬＯＣＫ失敗の通知を受信すると、Ｓｔｅｐ６にＬＯＣＫ命令を再発行する。また、ＣＰＵ２〜４は、Ｓｔｅｐ７においてＬＯＣＫ失敗の通知を受信すると、Ｓｔｅｐ９にＬＯＣＫ命令を再発行する。
【０００９】
次に、図１０を参照する。図１０において、ＣＰＵ２〜４は、Ｓｔｅｐ４においてＬＯＣＫ失敗の通知を受信すると、Ｓｔｅｐ１４にＬＯＣＫ命令を再発行する。この場合、Ｓｔｅｐ８〜Ｓｔｅｐ１４の間は、セマフォの値が０（共有メモリへのアクセスがない状態）となる。
【００１０】
続いて、セマフォ処理に関連する技術を開示した文献を以下に説明する。特許文献１は、セマフォの使用効率を改善する手法を開示している。当該手法では、ＬＯＣＫ失敗時にＬＯＣＫ命令の優先順位を登録し、ＵＮＬＯＣＫ命令実行後に優先順位の高いＣＰＵにＬＯＣＫ解除を通知している。
【００１１】
特許文献２は、メモリ共有型のマルチプロセッサにおいて各プロセッサからのメモリアクセスの沈み込みを防ぐ手法が開示されている。当該手法では、メモリアクセス要求時に実行順序を保持し、当該順序に応じてメモリにアクセスする。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平４−１２８９５７号公報
【特許文献２】特開平６−１９５３１２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
図９に記載したフローでは、図示するようにＣＰＵ２〜４は、何度もＬＯＣＫ命令を再発行する。これにより、各ＣＰＵ（ＣＰＵ２〜４）の負荷が高くなってしまう。
【００１４】
一方、図１０に記載したフローでは、図示するようにＣＰＵ２〜４は、Ｓｔｅｐ４においてＬＯＣＫ失敗を受信すると、Ｓｔｅｐ１４までＬＯＣＫ命令の再発行を行わない。しかし、ＣＰＵ１は、Ｓｔｅｐ８においてＵＮＬＯＣＫ命令を発行している。すなわち、Ｓｔｅｐ８からＳｔｅｐ１４までのセマフォの値は、０（不使用）となり、セマフォの使用効率が悪い。
【００１５】
すなわち、図９、図１０を参照して説明したマルチプロセッサシステムでは、ＬＯＣＫ命令発行のための負荷が高くなる（各ＣＰＵの処理負荷が高くなる）、または、セマフォの使用効率が悪くなるという問題があった。
【００１６】
なお、特許文献１に記載の技術は、図８に示す動作に新規の処理を追加する必要があり、一般的なシステムに適用することが困難である。さらに、特許文献１に記載の技術では、全てのＣＰＵをＬＯＣＫ解除待ち（セマフォの取得待ち）状態に遷移させると、ＬＯＣＫ解除待ちの状態にあるＣＰＵは、いつＬＯＣＫ解除（セマフォ取得）が行われるかわからない。
【００１７】
特許文献２に記載の技術によっても、各ＣＰＵがどの程度セマフォの解放を待てばよいかを把握することができなかった。
【００１８】
すなわち、上記したいずれの手法によっても、各ＣＰＵ（プロセッサ）の処理負荷を軽減し、セマフォの使用効率を向上させたマルチプロセッサシステムを実現することが困難であった。
【００１９】
本発明は上記した課題に鑑みてなされたものであり、各ＣＰＵ（プロセッサ）の処理負荷を軽減し、セマフォの使用効率を向上させたマルチプロセッサシステム、マルチプロセッサシステムの制御方法を提供することを主たる目的とする。
【課題を解決するための手段】
【００２０】
本発明にかかるマルチプロセッサシステムの一態様は、
複数のプロセッサと、
前記複数のプロセッサからアクセスされる共有リソースと、
プロセッサからの前記共有リソースに対するロック命令及びアンロック命令の受信に応じて、前記共有リソースの同期制御を行うセマフォ制御回路と、を備え、
前記セマフォ制御回路は、あるプロセッサの前記共有リソースのロック時間をカウントし、前記共有リソースのロック中にロック命令を送信したプロセッサの命令送信順序を保持し、確定した前記ロック時間と、前記命令送信順序と、を基に前記共有リソースに対するロックに失敗した各プロセッサの待ち時間を算出して通知する、ものである。
【００２１】
本発明にかかるマルチプロセッサシステムの制御方法の一態様は、
複数のプロセッサと、前記複数のプロセッサからアクセスされる共有リソースと、を備えるマルチプロセッサにおいて、プロセッサからの前記共有リソースに対するロック命令及びアンロック命令の受信に応じて、前記共有リソースの同期制御を行うマルチプロセッサの制御方法であって、
あるプロセッサの前記共有リソースのロック時間をカウントし、前記共有リソースのロック中にロック命令を送信したプロセッサの命令送信順序を保持し、確定した前記ロック時間と、前記命令送信順序と、を基に前記共有リソースに対するロックに失敗した各プロセッサの待ち時間を算出して通知する、ものである。
【発明の効果】
【００２２】
本発明では、各ＣＰＵ（プロセッサ）の処理負荷を軽減し、セマフォの使用効率を向上させたマルチプロセッサシステム、マルチプロセッサシステムの制御方法を提供することができる。
【図面の簡単な説明】
【００２３】
【図１】実施の形態１にかかるマルチプロセッサシステムの全体構成を示すブロック図である。
【図２】実施の形態１にかかるメインコントローラ２０の構成を示すブロック図である。
【図３】実施の形態１にかかるセマフォ制御回路２０４の構成を示すブロック図である。
【図４】実施の形態１にかかるＬＯＣＫ成功・失敗判定回路２０４３によるＬＯＣＫの成否の判定方法を示す図である。
【図５】実施の形態１にかかるマルチプロセッサシステム（特にメモリコントローラ２０）の動作を示すフロー図である。
【図６】実施の形態１にかかるＬＡＢ２０４１、ＬＣＴ２０４２の索引結果、及び更新結果を示す図である。
【図７】実施の形態１にかかるマルチプロセッサシステムの全体構成を示すブロック図である。
【図８】一般的なマルチプロセッサシステムのセマフォ処理を示すフローチャートである。
【図９】一般的なマルチプロセッサシステムの動作を示すフロー図である。
【図１０】一般的なマルチプロセッサシステムの動作を示すフロー図である。
【発明を実施するための形態】
【００２４】
＜実施の形態１＞
以下、図面を参照して本発明の実施の形態について説明する。図１は、本実施の形態にかかるマルチプロセッサシステムの全体構成を示すブロック図である。本実施の形態にかかるマルチプロセッサシステムは、一般的なマルチコアプロセッサの構成要素と同一の要素を有する。当該マルチプロセッサシステムは、ＣＰＵ（Central Processing Unit）１〜ｎと、ＣＰＵ１〜ｎからアクセス可能なメモリ３０と、ＣＰＵ１〜ｎからメモリ３０へのアクセスを制御するメモリコントローラ２０と、を有する。
【００２５】
ＣＰＵ１〜ｎは、それぞれ独立してメモリ３０にアクセスする。ＣＰＵ１〜ｎは、メモリ３０内の共有メモリ（メモリ３０内の共有される領域であり、共有リソースの一態様である）にアクセスする場合、セマフォを獲得するためのＬＯＣＫ命令をメモリコントローラ２０に発行する。ＣＰＵ１〜ｎは、メモリ３０内の共有メモリの使用後に、セマフォを解放するためのＵＮＬＯＣＫ命令をメモリコントローラ２０に発行する。
【００２６】
さらに、ＣＰＵ１〜ｎは、メモリコントローラ２０からＬＯＣＫ命令に対するＬＯＣＫ失敗の通知を受信した場合、ＬＯＣＫ失敗と共に通知される待ち時間だけ待ち合わせを行う。ＣＰＵ１〜ｎは、待ち合わせの後にＬＯＣＫ命令を再発行する。
【００２７】
一方、ＣＰＵ１〜ｎは、メモリコントローラ２０からＬＯＣＫ命令に対するＬＯＣＫ成功の通知を受信した場合、メモリ３０の共有メモリにアクセスする。ＣＰＵ１〜ｎは、処理終了後にメモリコントローラ２０に対してＵＮＬＯＣＫ命令を発行する。なお、セマフォは、メモリ３０の任意のアドレスに配置され、ＬＯＣＫ命令、またはＵＮＬＯＣＫ命令に付与するアドレスにより該当するセマフォを指定する。
【００２８】
メモリコントローラ２０は、ＣＰＵ１〜ｎからメモリ３０へのアクセスを制御する制御装置である。メモリコントローラ２０の詳細は、図２のブロック図を参照して説明する。図２は、メモリコントローラ２０の構成を示すブロック図である。
【００２９】
メモリコントローラ２０は、ＣＰＵ命令調停回路２０１と、ＣＰＵ命令デコーダ２０２と、メモリ制御回路２０３と、セマフォ制御回路２０４と、ＣＰＵ命令返信回路２０５と、を備える。
【００３０】
ＣＰＵ命令調停回路２０１は、ＣＰＵ１〜ｎから受信した命令を調停する回路である。ＣＰＵ命令デコーダ２０２は、ＣＰＵ命令調停回路２０１が調停した命令をデコードし、デコードした命令がメモリ３０へのアクセスである場合に、メモリ制御回路２０３に当該命令を供給する。ＣＰＵ命令デコーダ２０２は、デコードした命令がＬＯＣＫ命令またはＵＮＬＯＣＫ命令である場合、ＬＯＣＫ命令またはＵＮＬＯＣＫ命令をセマフォ制御回路２０４に供給する。
【００３１】
セマフォ制御回路２０４は、受信したＬＯＣＫ命令またはＵＮＬＯＣＫ命令に対して、ＬＯＣＫが成功したか否か（セマフォを獲得できたか否か）の判定を行うとともに、ＬＯＣＫが失敗した（セマフォを獲得できない）場合の待ち時間の算出を行う。
【００３２】
ＣＰＵ命令返信回路２０５は、ＣＰＵ１〜ｎから受信した命令に対する返信を行う回路である。
【００３３】
ここで、セマフォ制御回路２０４について、図３を参照して更に詳しく説明する。図３は、セマフォ制御回路２０４の内部構成を示すブロック図である。セマフォ制御回路２０４は、ＬＯＣＫアドレスバッファ（以降の説明では、ＬＡＢと略して記載する）２０４１と、ＬＯＣＫ競合テーブル（以降の説明では、ＬＣＴと略して記載する）２０４２と、ＬＯＣＫ成功・失敗判定回路２０４３と、を有する。
【００３４】
ＬＡＢ２０４１は、ワード０〜ｎ（ｎは１以上の任意の整数）から構成され、ＬＯＣＫが成功した（セマフォを獲得できた）ＬＯＣＫ命令の情報を複数（最大ｎ個）登録できるバッファである。なお、同一アドレスに対して、同時にＬＯＣＫが成功することはあり得ないため、同一アドレスへのＬＯＣＫ命令は１ワードしか登録されない。
【００３５】
ＬＡＢ２０４１のワードｎは、Ｖビット２０４１１と、セマフォアドレス２０４１２と、ＬＯＣＫ時間２０４１３と、から構成される。Ｖビット２０４１１は、ワードｎが有効であるか否かを示すビット値である。Ｖビット２０４１１は、１が設定された場合にＬＯＣＫ処理が実行されていること（有効であること）を示す。セマフォアドレス２０４１２は、ＬＯＣＫ命令内に含まれるアドレス（メモリ３０内において、アクセスしたい共有メモリのアドレス）である。ＬＯＣＫ時間２０４１３は、Ｖビット２０４１１に"１"が設定された時間（ステップ数）、すなわちＬＯＣＫ状態となっている積算時間を保持するカウンタである。
【００３６】
さらに、ＬＡＢ２０４１は、アドレス比較器２０４１４と、セレクタ２０４１５−１と、セレクタ２０４１５−２と、を有する。アドレス比較器２０４１４は、ＣＰＵ命令デコーダ２０２から新たに入力されたＬＯＣＫ命令内のアドレスと、各ワード内のセマフォアドレス２０４１２と、を比較する。アドレス比較器２０４１４は、ＣＰＵ命令デコーダ２０２から新たに入力されたＬＯＣＫ命令内のアドレスと一致するセマフォアドレス２０４１２のワード番号を検出する。アドレス比較器２０４１４は、検出したワード番号をＬＯＣＫ成功・失敗判定回路２０４３、セレクタ２０４１５−１、セレクタ２０４１５−２に通知する。
【００３７】
セレクタ２０４１５−１は、通知されたワード番号に対応するＶビット２０４１１の値を取得して、取得値をＬＯＣＫ成功・失敗判定回路２０４３に通知する。セレクタ２０４１５−２は、通知されたワード番号に対応するＬＯＣＫ時間２０４１３の値を取得して、取得値をＬＯＣＫ成功・失敗判定回路２０４３に通知する。
【００３８】
ＬＡＢ２０４１は、ＬＯＣＫ成功・失敗判定回路２０４３によりＬＯＣＫが成功したと判定された場合、該当するワードのＶビット２０４１１の値を０から１に更新する。ＬＡＢ２０４１は、Ｖビット２０４１１の値を１に更新するとともに、該当するワードのＬＯＣＫ時間２０４１３のカウント（Ｖビット２０４１１の有効（１）期間のカウント）を開始する。
【００３９】
アドレス比較器２０４１４は、ＣＰＵ命令デコーダ２０２からＵＮＬＯＣＫ命令を受信した場合、ＵＮＬＯＣＫ命令に含まれるアドレスと一致するセマフォアドレス２０４１２のワード番号を検出する。ＬＡＢ２０４１は、検出したワードのＶビット２０４１１を０に更新することによりＬＯＣＫを解除し（セマフォを解放し）、当該ワードのＬＯＣＫ時間２０４１３のカウントを停止する。
【００４０】
なお、ＵＮＬＯＣＫ命令と同一アドレスのＬＯＣＫ命令がＬＣＴ２０４２に存在する場合、ＬＯＣＫ時間カウンタ２０４１３の値をＬＣＴ２０４２のＬＯＣＫ時間に登録する。但し、ＬＣＴ２０４２のＬＯＣＫ時間２０４２６に０以外の値が既に登録されている場合は登録しない。
【００４１】
続いて、ＬＣＴ２０４２について説明する。ＬＣＴ２０４２は、ＬＡＢ２０４１と同様に、ワード０〜ｎ（ｎは１以上の任意の整数）から構成され、ＬＯＣＫが失敗した（セマフォを獲得できなかった）ＬＯＣＫ命令の情報を複数（最大ｎ個）登録できるバッファである。ただし、同一アドレスに対するＬＯＣＫ命令は１ワードしか登録しない。
【００４２】
ＬＣＴ２０４２のワードｎは、Ｖビット２０４２１と、セマフォアドレス２０４２２と、ステータスフラグ２０４２３と、受付番号２０４２４と、優先番号２０４２５と、ＬＯＣＫ時間２０４２６と、から構成される。
【００４３】
Ｖビット２０４２１は、ワードｎが有効であるか否かを示すビット値である。Ｖビット２０４２１に１が設定されている場合、有効（該当ワードのセマフォアドレス２０４２２にアクセスするＬＯＣＫ命令が再発行される）であることを示す。セマフォアドレス２０４２２は、ＬＯＣＫ命令内に含まれるアドレス（メモリ３０内において、アクセスしたい共有メモリのアドレス）である。ステータスフラグ２０４２３は、ＣＰＵの個数と同じだけ各ワードに設けられる。ステータスフラグ２０４２３は、ＣＰＵ毎のＬＯＣＫ成功、失敗のステータスを保持する。ステータスの詳細は後述する。
【００４４】
受付番号２０４２４は、ＣＰＵの個数と同じだけ各ワードに設けられる。受付番号２０４２４は、各ＣＰＵのＬＯＣＫ命令の受け付け順序（発行順序）を保持する。優先番号２０４２５は、ＬＯＣＫ失敗したＬＯＣＫ命令のうち、最も優先順位の高い（次に処理を行う）ＬＯＣＫ命令の受付番号を保持する。ＬＯＣＫ時間２０４２６は、セマフォアドレス２０４２２と対応するセマフォアドレス２０４１２を持つＬＡＢ２０４１内のワードのＬＯＣＫ時間２０４１３の値を保持する。ＬＯＣＫ時間２０４２６は、ＵＮＬＯＣＫ命令の処理時に、ＬＯＣＫ処理を終了したＬＯＣＫ命令の処理時間が設定される。具体例は、図５及び図６を参照して再度説明する。
【００４５】
さらに、ＬＣＴ２０４２は、アドレス比較器２０４２７と、セレクタ２０４２８−１〜２０４２８−５と、を有する。アドレス比較器２０４２７は、ＣＰＵ命令デコーダ２０２から新たに入力されたＬＯＣＫ命令、ＵＮＬＯＣＫ命令内のアドレスと、各ワード内のセマフォアドレス２０４２２と、を比較する。アドレス比較器２０４２７は、ＣＰＵ命令デコーダ２０２から新たに入力されたＬＯＣＫ命令内、ＵＮＬＯＣＫ命令内のアドレスと一致するセマフォアドレス２０４２２のワード番号を検出する。アドレス比較器２０４２７は、検出したワード番号をＬＯＣＫ成功・失敗判定回路２０４３、及びセレクタ２０４２８−１〜２０４２８−５に通知する。
【００４６】
セレクタ２０４２８−１〜２０４２８−５は、通知されたワード番号に対応する値を接続先から取得して、取得値をＬＯＣＫ成功・失敗判定回路２０４３に通知する。
【００４７】
ＬＣＴ２０４２は、入力されたＬＯＣＫ命令のＬＯＣＫが失敗したとＬＯＣＫ成功・失敗判定回路２０４３に判定され、当該ＬＯＣＫ命令と同一のＬＯＣＫ命令がＬＣＴ２０４２内に登録されていない場合（アドレス比較器２０４２７の比較において入力されたＬＯＣＫ命令と同一のセマフォアドレス２０４２２を持つワードがない、またはワードがあるがＶビット２０４２１に０が設定されている場合）、当該ＬＯＣＫ命令の情報をＬＣＴ２０４２に追加する。一方、同一のＬＯＣＫ命令がＬＣＴ２０４２内に登録されている場合、ＬＯＣＫ成功・失敗判定回路２０４３は、対応するワードのステータスフラグ２０４２３と、受付番号２０４２４と、の値を更新する。ただし、発行元ＣＰＵに対応するステータスフラグ２０４２３に既に"００"以外の値が設定されている場合は処理を行わない。
【００４８】
ここで、ＣＰＵ毎に設定されるステータスフラグ２０４２３は、ＬＯＣＫ命令の処理状態が２ビットで設定される。"００"は、初期状態を示す。"１０"は、ＬＯＣＫ失敗により、ＬＯＣＫ命令を再発行している状態を示す。"１１"は、ＬＯＣＫが失敗していたＬＯＣＫ命令が再発行によりＬＯＣＫ成功した状態を示す。
【００４９】
ＣＰＵ毎に設定される受付番号２０４２４は、ＬＯＣＫ処理が失敗したＬＯＣＫ命令の受け付け順序を示す。受付番号２０４２４は、ステータスフラグ２０４２３の更新の際に、ステータスフラグ２０４２３に"１０"が設定されている個数をカウントした値となる。つまり、受付番号２０４２４には、ＬＯＣＫ失敗によりＬＯＣＫ命令の再発行処理を行っているＣＰＵの数が登録される。例えば、ＣＰＵ１、ＣＰＵ２、ＣＰＵ３の順序でＬＯＣＫ命令が失敗した場合、ＣＰＵ１の受付番号２０４２４は"０"、ＣＰＵ２の受付番号２０４２４は"１"、ＣＰＵ３の受付番号２０４２４は"２"となる。
【００５０】
優先番号２０４２５は、ＬＣＴ２０４２に登録されているＬＯＣＫ命令がＬＯＣＫ成功する毎にインクリメント（１だけ増加）する。なお、詳細な動作例は、図５及び図６を参照して後述する。
【００５１】
ＬＯＣＫ成功・失敗判定回路２０４３の動作について説明する。ＬＯＣＫ成功・失敗判定回路２０４３は、ＬＡＢ２０４１及びＬＣＴ２０４２から索引結果（アドレス比較器、またはセレクタが出力した値）を受信し、受信した情報からＬＯＣＫの成否を判定する。ＬＯＣＫ成功・失敗判定回路２０４３によるＬＯＣＫの成否の判定方法を図４に示す。図４は、ＬＡＢ２０４１及びＬＣＴ２０４２からの入力と、ＬＯＣＫの成否判定との関係を示す図である。
【００５２】
図４において、Ｖビットは、ＬＡＢ２０４１またはＬＣＴ２０４２から取得したＶビットの値を示す。なお、アドレス比較器２０４１４、アドレス比較器２０４２７は、一致するセマフォアドレスを検出できなかった場合、Ｖビットを０とする。
【００５３】
ＬＯＣＫ成功・失敗判定回路２０４３は、項番１（ＬＡＢ２０４１及びＬＣＴ２０４２に該当するワードがあり、共にＶビットが０に設定されている）と項番３（ＬＡＢ２０４１に設定されたＶビットが０であり、ＬＣＴ２０４２に設定されたＶビットが１であり、かつ優先順位が最も高い）のケースにはＬＯＣＫが成功したと判定する。ＬＯＣＫ成功・失敗判定回路２０５は、項番１、項番３に該当しない場合にはＬＯＣＫが失敗したと判定する。詳細な例は、図５、図６を参照して再度説明する。
【００５４】
ＬＯＣＫ成功・失敗判定回路２０４３は、ＬＯＣＫが失敗したと判定した場合、ＬＯＣＫ命令の発行元のＣＰＵに対して通知する待ち時間を算出する。ＬＯＣＫ成功・失敗判定回路２０４３は、ＬＯＣＫ命令の発行元の各ＣＰＵに対応する受付番号２０４２４と、優先番号２０４２５と、ＬＯＣＫ時間２０４２６と、から以下の計算式を用いて各ＣＰＵの待ち時間を算出する。ＬＯＣＫ成功・失敗判定回路２０４３は、ＬＯＣＫ失敗の情報に算出した待ち時間を付与して、ＣＰＵ命令返信回路２０５に送信する。
待ち時間  ＝（受付番号２０２４３−優先番号２０４２５）×ＬＯＣＫ時間２０４２６
【００５５】
次に、図５及び図６を参照して、本実施の形態にかかるマルチプロセッサシステム（特にメモリコントローラ２０、セマフォ制御回路２０４）の動作について説明する。図５は、ＣＰＵ１〜４を有する本実施の形態にかかるマルチプロセッサシステムの動作フローを示す図である。図中において、縦軸は時間軸（単位はＳｔｅｐ）を示し、それぞれの時刻をＳｔｅｐ１〜２６とする。なお、ＣＰＵ１〜４が発行するＬＯＣＫ命令のアドレスは、全て同じアドレスとする。
【００５６】
図６は、図５の各ステップにおいて、ＣＰＵ１〜４が発行したＬＯＣＫ命令、ＵＮＬＯＣＫ命令に対するＬＡＢ２０４１、ＬＣＴ２０４２の索引結果、及び更新結果を示す図である。Ｓｔｅｐ０では、ＬＡＢ２０４１、ＬＣＴ２０４２は初期状態に設定され、Ｖビットは"０"にリセットされている。また、優先番号２０４２５等も全て"０"にリセットされている。
【００５７】
はじめにＣＰＵ１は、Ｓｔｅｐ１において、メモリコントローラ２０にＬＯＣＫ命令を発行する。メモリコントローラ２０は、ＣＰＵ１からＬＯＣＫ命令を受信する。メモリコントローラ２０内のＣＰＵ命令調停回路２０１は、ＣＰＵ間の調停を行い、ＣＰＵ１のＬＯＣＫ命令を選択する。選択されたＣＰＵ１のＬＯＣＫ命令は、ＣＰＵ命令デコーダ２０２によりデコードされる。ＣＰＵ命令デコーダ２０２は、デコードの結果、ＬＯＣＫ命令であることを認識する。ＣＰＵ命令デコーダ２０２は、ＬＯＣＫ命令をセマフォ制御回路２０４に供給する。
【００５８】
セマフォ制御回路２０４（詳細にはアドレス比較器）は、受信したＬＯＣＫ命令のアドレスを用いて、ＬＡＢ２０４１とＬＣＴ２０４２を索引する。セマフォ制御回路２０４（ＬＯＣＫ成功・失敗判定回路２０４３）は、ＬＡＢ２０４１とＬＣＴ２０４２のＶビットが０であることを認識し、ＬＯＣＫ成功と判定する。そして、セマフォ制御回路２０４は、更新処理においてＬＡＢ２０４１に当該ＬＯＣＫ命令を登録し、ＬＯＣＫ時間の計測を開始する（なお、図６においては、"ｔ１"と記載する。）。
【００５９】
メモリコントローラ２０は、Ｓｔｅｐ２において、ＬＯＣＫ成功をＣＰＵ１に通知する。
【００６０】
ＣＰＵ２〜４は、Ｓｔｅｐ３において、ほぼ同時にメモリコントローラ２０にＬＯＣＫ命令を発行する。メモリコントローラ２０内のＣＰＵ命令調停回路２０１は、ＣＰＵ間の調停を行い、ＣＰＵ２〜４のＬＯＣＫ命令を選択する。なお、本例では、Ｓｔｅｐ３において、ＣＰＵ命令調停回路２０１は、ＣＰＵ２、ＣＰＵ３、ＣＰＵ４の順番でＣＰＵ命令デコーダ２０２にＬＯＣＫ命令を送信する。
【００６１】
ＣＰＵ命令デコーダ２０２は、受信した命令をデコードし、ＬＯＣＫ命令をセマフォ制御回路２０４に供給する。セマフォ制御回路２０４には、はじめにＣＰＵ２からのＬＯＣＫ命令が入力される。セマフォ制御回路２０４は、このＬＯＣＫ命令内のアドレスを基に、ＬＡＢ２０４１と、ＬＣＴ２０４２を索引する。この索引結果は、図６のＳｔｅｐ３内の発行元ＣＰＵ＝ＣＰＵ２に示す通りである。
【００６２】
セマフォ制御回路２０４は、ＬＡＢ２０４１のＶビットが１であるため、ＬＯＣＫ処理が失敗したと判定する。さらに、セマフォ制御回路２０４は、ＬＣＴ２０４２のＶビットが０であるため、ＬＣＴ２０４２に対し、ＣＰＵ２が発行したＬＯＣＫ命令を新規登録する。この時、セマフォ制御回路２０４は、ＬＣＴ２０４２のＣＰＵ２に対応するステータスフラグ２０４２３に"１０"（ＬＯＣＫ失敗により、ＬＯＣＫ命令を再発行している状態）を設定し、受付番号２０４２４に"０"を登録する。Ｖビット２０４２１には、"１"を設定する。
【００６３】
次にセマフォ制御回路２０４は、ＣＰＵ３からのＬＯＣＫ命令が入力される。セマフォ制御回路２０４は、このＬＯＣＫ命令内のアドレスを基に、ＬＡＢ２０４１と、ＬＣＴ２０４２を索引する。セマフォ制御回路２０４は、ＬＡＢ２０４１のＶビットが１であるため、ＣＰＵ２からのＬＯＣＫ命令と同様に、ＬＯＣＫ処理が失敗したと判定する。さらに、セマフォ制御回路２０４は、ＬＣＴ２０４２のＶビットが１であるため、ＬＣＴ２０４２に対応するワードが存在すると判定する。そのため、セマフォ制御回路２０４は、当該ワードに対し、ＣＰＵ３に対応するステータスフラグ２０４２３に"１０" を設定し、受付番号２０４２４に"１"を登録する。
【００６４】
セマフォ制御回路２０４は、ＣＰＵ４からのＬＯＣＫ命令についても同様の処理を行う。セマフォ制御回路２０４は、当該ワードに対し、ＣＰＵ４に対応するステータスフラグ２０４２３に"１０" を設定し、受付番号２０４２４に"２"を登録する。なお、上述した処理結果は、図６のＳｔｅｐ３の各欄に記載されている。
【００６５】
メモリコントローラ２０は、Ｓｔｅｐ４において、ＬＯＣＫ失敗をＣＰＵ２〜４に通知する。この際、セマフォ制御回路２０４は、ＬＣＴ２０４２の索引結果からＬＯＣＫ命令の再発行までの待ち時間を計算し、算出した値をＬＯＣＫ失敗の情報と合わせて通知する。しかし、Ｓｔｅｐ４の時点では、ＣＰＵ１のＬＯＣＫ処理が完了していない。そのため、セマフォ制御回路２０４は、待ち時間を０とする。
【００６６】
ＣＰＵ２〜４は、メモリコントローラ２０からＬＯＣＫ失敗の通知を受け取ると、ＬＯＣＫ命令の待ち合わせを行う。この場合、待ち時間は０であるため、ＣＰＵ２〜４は、待ち合わせを行わない。
【００６７】
ＣＰＵ２〜４は、Ｓｔｅｐ６において、メモリコントローラ２０に対してＬＯＣＫ命令を再発行する。メモリコントローラ２０は、Ｓｔｅｐ３にて受信したＬＯＣＫ命令と同様に処理を行う。すなわち、セマフォ制御回路２０４は、ＬＡＢ２０４１とＬＣＴ２０４２を索引し、ＬＯＣＫ失敗の判定を行う。また、ＬＣＴ２０４２内にＣＰＵ２〜４に対応するステータスフラグ２０４２３が登録されているため、ＬＣＴ２０４２の更新は行われない。
【００６８】
メモリコントローラ２０は、Ｓｔｅｐ７において、ＬＯＣＫ失敗をＣＰＵ２〜４に通知する。本処理は、Ｓｔｅｐ４における処理と同一であるため、詳細な説明は省略する。また、Ｓｔｅｐ８におけるＣＰＵ２〜４のＬＯＣＫ命令の発行処理は、Ｓｔｅｐ６と同一であり、Ｓｔｅｐ９におけるメモリコントローラ２０の処理は、Ｓｔｅｐ７と同一であるため、図示及び詳細な説明は省略する。
【００６９】
ＣＰＵ１は、Ｓｔｅｐ８において、メモリコントローラ２０に対して、共有メモリへのアクセス命令を発行する。メモリコントローラ２０は、当該アクセス命令を受信し、ＣＰＵメモリ制御回路２０３を介してメモリ３０にアクセスする。
【００７０】
ＣＰＵ１は、Ｓｔｅｐ９において、メモリコントローラ２０に対してＵＮＬＯＣＫ命令を発行する。メモリコントローラ２０は、ＵＮＬＯＣＫ命令を受信する。メモリコントローラ２０内のセマフォ制御回路２０４は、ＵＮＬＯＣＫ命令に含まれるアドレスを基にＬＡＢ２０４１と、ＬＣＴ２０４２を索引する（索引結果は、図６Ｓｔｅｐ９を参照されたい。）。そして、セマフォ制御回路２０４は、ＣＰＵ１のＬＡＢ２０４１のＶビットを０に設定することによりＬＯＣＫ命令を解除する。また、セマフォ制御回路２０４は、ＬＡＢ２０４１にて計測したＬＯＣＫ時間２０４１３をＬＣＴ２０４２のＬＯＣＫ時間２０４２６に登録する。
【００７１】
ＣＰＵ２〜４は、Ｓｔｅｐ１０において、ＬＯＣＫ命令をメモリコントローラ２０に対して再発行する。本例では、メモリコントローラ２０内のＣＰＵ命令調停回路２０１は、ＣＰＵ４、ＣＰＵ３、ＣＰＵ２の順番でＬＯＣＫ命令をＣＰＵ命令デコーダ２０２に送信する。
【００７２】
セマフォ制御回路２０４は、はじめにＣＰＵ４からのＬＯＣＫ命令を受信する。セマフォ制御回路２０４は、ＣＰＵ４からのＬＯＣＫ命令に含まれるアドレスを基にＬＡＢ２０４１と、ＬＣＴ２０４２を索引する（索引結果は、図６Ｓｔｅｐ１０、ＣＰＵ＝ＣＰＵ４を参照されたい。）。ここで、ＬＡＢ２０４１のＶビットは０にリセットされているが、ＬＣＴ２０４２のＶビットは１である。さらに、ＣＰＵ４の受付番号２０４２４の値"２"は、優先番号２０４２５の値"０"と異なる（ＣＰＵ４からのＬＯＣＫ命令の優先順位が低い）。そのため、セマフォ制御回路２０４は、ＣＰＵ４からのＬＯＣＫ命令についてＬＯＣＫ失敗と判定する。
【００７３】
この際、ＬＯＣＫ時間２０４２６が登録されている、すなわちＣＰＵ１のＬＯＣＫ処理時間が確定している。そのため、セマフォ制御回路２０４は、ＣＰＵ４の待ち時間を２ｔ１（ＣＰＵ４の受付番号２０４２４の値"２"から優先順位２０４２５の値"０"を減算した値に、ｔ１を乗算した値）と算出する。
【００７４】
ＣＰＵ４からのＬＯＣＫ命令と同様の手法により、セマフォ制御回路２０４は、ＣＰＵ３からのＬＯＣＫ命令に対し、ＬＯＣＫ失敗と判定する。また、セマフォ制御回路２０４は、ＣＰＵ３の待ち時間をｔ１（ＣＰＵ３の受付番号２０４２４の値"１"から優先順位２０４２５の値"０"を減算した値に、ｔ１を乗算した値）と算出する。
【００７５】
次にセマフォ制御回路２０４は、ＣＰＵ２からのＬＯＣＫ命令を受信する。セマフォ制御回路２０４は、ＣＰＵ２からのＬＯＣＫ命令に含まれるアドレスを基にＬＡＢ２０４１と、ＬＣＴ２０４２を索引する（索引結果は、図６Ｓｔｅｐ１０、ＣＰＵ＝ＣＰＵ２を参照されたい。）。ここで、ＬＡＢ２０４１のＶビットは０にリセットされており、ＬＣＴ２０４２のＶビットは１であり、ＣＰＵ２の受付番号２０４２４の値"０"は、優先番号２０４２５の値"０"と同一である（ＣＰＵ２のＬＯＣＫ命令の優先順位が高い）。そのため、セマフォ制御回路２０４は、ＬＯＣＫ成功と判定する。セマフォ制御回路２０４は、ＣＰＵ２のＬＯＣＫ命令をＬＡＢ２０４１に登録し、同時にＬＣＴ２０４２のＣＰＵ２にかかるステータスフラグ２０４２３を更新し（"１０"から"１１"）、優先番号２０４２５の値を更新（カウントアップ、"０"から"１"）する。
【００７６】
メモリコントローラ２０は、Ｓｔｅｐ１１において、ＣＰＵ２に対してＬＯＣＫ成功を通知する。メモリコントローラ２０は、Ｓｔｅｐ１１において、ＣＰＵ３及びＣＰＵ４に対してＬＯＣＫ失敗を通知する。この通知の際に、メモリコントローラ２０は、ＣＰＵ３に対して待ち時間の値（ｔ１）をＬＯＣＫ失敗の情報に含めて通知する。同様に、メモリコントローラ２０は、ＣＰＵ４に対して待ち時間の値（２ｔ１）をＬＯＣＫ失敗の情報に含めて通知する。
【００７７】
ＣＰＵ３は、ＬＯＣＫ失敗の通知を受信すると、ＬＯＣＫ失敗の情報に付与された待ち時間（ｔ１）の情報を取得する。同様に、ＣＰＵ４は、ＬＯＣＫ失敗の通知を受信すると、ＬＯＣＫ失敗の情報に付与された待ち時間（２ｔ１）の情報を取得する。これにより、ＣＰＵ３は、Ｓｔｅｐ１５まで待ち合わせを行う。ＣＰＵ４は、Ｓｔｅｐ２０まで待ち合わせを行う。
【００７８】
ＣＰＵ２は、Ｓｔｅｐ１３において、共有メモリへのアクセスを実行し、Ｓｔｅｐ１４においてＵＮＬＯＣＫ命令を発行する。なお、当該処理は、Ｓｔｅp８、９におけるＣＰＵ１の動作と同じであるため、詳細な説明は省略する。
【００７９】
ＣＰＵ３は、Ｓｔｅｐ１５においてｔ１時間の待ち合わせ処理を終了し、ＬＯＣＫ命令を再発行する。この時、ＣＰＵ４は、待ち合わせ処理の実行が終了していないため（残待ち合わせ時間＝２ｔ１−ｔ１＝ｔ１）、ＬＯＣＫ命令の再発行は行わない。メモリコントローラ２０は、ＣＰＵ３からＬＯＣＫ命令を受信する。メモリコントローラ２０内のセマフォ制御回路２０４は、ＣＰＵ３からのＬＯＣＫ命令に含まれるアドレスを基にＬＡＢ２０４１とＬＣＴ２０４２を索引する。そして、セマフォ制御回路２０４は、上述の手法によりＬＯＣＫが成功したと判定する。
【００８０】
メモリコントローラ２０は、Ｓｔｅｐ１６において、ＣＰＵ３に対してＬＯＣＫ成功を通知する。
【００８１】
ＣＰＵ３は、Ｓｔｅｐ１８において、共有メモリへのアクセスを実行し、Ｓｔｅｐ１９においてＵＮＬＯＣＫ命令を発行する。なお、当該処理は、Ｓｔｅp８、９におけるＣＰＵ１の動作と同じであるため、詳細な説明は省略する。
【００８２】
ＣＰＵ４は、Ｓｔｅｐ２０において２ｔ１時間の待ち合わせ処理を終了し、ＬＯＣＫ命令を再発行する。メモリコントローラ２０は、ＣＰＵ４からＬＯＣＫ命令を受信する。メモリコントローラ２０内のセマフォ制御回路２０４は、ＣＰＵ４からのＬＯＣＫ命令に含まれるアドレスを基にＬＡＢ２０４１とＬＣＴ２０４２を索引する。そして、セマフォ制御回路２０４は、上述の手法によりＬＯＣＫが成功したと判定する。
【００８３】
この時、ＬＣＴ２０４２内のステータスフラグ２０４２３に"１０"の値を持つＣＰＵが存在しなくなる。そのため、セマフォ制御回路２０４は、ＬＣＴ２０４２のＶビット２０４２１を"０"にリセットする。
【００８４】
メモリコントローラ２０は、Ｓｔｅｐ２１において、ＣＰＵ４に対してＬＯＣＫ成功を通知する。
【００８５】
ＣＰＵ４は、Ｓｔｅｐ２３において、共有メモリへのアクセスを実行し、Ｓｔｅｐ２４においてＵＮＬＯＣＫ命令を発行する。なお、当該処理は、Ｓｔｅp８、９におけるＣＰＵ１の動作と同じであるため、詳細な説明は省略する。
【００８６】
続いて、本発明にかかるマルチプロセッサシステムの効果を、図５の動作フロー図を参照して説明する。図５に示すように、ＣＰＵ２〜４は、ＣＰＵ１がＵＮＬＯＣＫ命令によりＬＯＣＫを解除（セマフォを解放）するＳｔｅｐ９まで、ＬＯＣＫ命令の再発行を繰り返している。しかし、ＣＰＵ１のＬＯＣＫ命令の処理時間が確定する（ＣＰＵ２のＬＯＣＫ命令がＬＯＣＫ成功となる）と、ＣＰＵ３、４は、メモリコントローラ２０からＬＯＣＫ命令の再発行までの待ち時間を受信する。ＣＰＵ３、４は、この待ち時間の間、ＬＯＣＫ命令の発行を待ち合わせる。
【００８７】
ＣＰＵ３及びＣＰＵ４に通知される待ち時間は、メモリコントローラ２０が処理するＬＯＣＫ命令の順序（優先順位）と、ＣＰＵ１のＬＯＣＫ命令の処理時間と、から算出された値である。そのため、ＣＰＵ３に通知される待ち時間と、ＣＰＵ４に通知される待ち時間には、異なる時間が指定される。これにより、ＣＰＵ３及びＣＰＵ４がＳｔｅp１１にてＬＯＣＫ失敗の通知を受信すると、ＣＰＵ３は、Ｓｔｅｐ１５にてＬＯＣＫ命令を再発行する。一方、ＣＰＵ４は、Ｓｔｅｐ２０にてＬＯＣＫ命令を再発行する。
【００８８】
この待ち時間の設定により、ＣＰＵ３及びＣＰＵ４は、Ｓｔｅｐ１１以降に無駄なＬＯＣＫ命令を発行しない。すなわち、ＣＰＵ３及びＣＰＵ４の処理負荷が、ＬＯＣＫ命令の発行を削減することによって軽減される。
【００８９】
さらに、図５に示すように、ＣＰＵ３及びＣＰＵ４は、他のＣＰＵがＵＮＬＯＣＫ処理をした直後にＬＯＣＫ命令を発行している。これにより、セマフォの使用効率を改善することができる（ＬＯＣＫを効率的に行うことができる）。
【００９０】
なお、上述した特許文献１の手法では、図８に示す動作フローに対して、新たな処理（ＬＯＣＫ失敗と判定した場合にＬＯＣＫ命令の優先順位を登録し、ＵＮＬＯＣＫ命令の処理後に優先順位の高いＣＰＵにＬＯＣＫ解除を通知する処理）を追加する必要がある。一方、本実施の形態にかかるマルチプロセッサシステムでは、図８に示す動作フローにおいて、待ち時間の最適化処理のみを行うだけで、上述の効果（ＣＰＵ処理負荷の軽減、セマフォの使用効率改善）を奏することができる。
【００９１】
さらにまた、特許文献１の手法では、前述のようにＬＯＣＫ解除待ちの状態にあるＣＰＵは、いつＬＯＣＫ解除（セマフォ取得）が行われるかわからない。そのため、ＬＯＣＫ解除待ちの状態にあるＣＰＵは、他の処理を行うことなく、ＬＯＣＫ解除の命令を待ち続ける必要がある。
【００９２】
一方、本実施の形態にかかるマルチプロセッサシステム内の各ＣＰＵは、ＬＯＣＫ命令の再発行までの待ち時間を正確に把握することができる。そのため、各ＣＰＵは、待ち時間の間に別の処理を実行することができ、ＣＰＵリソースを有効に利用することができる。例えば、図５において、ＣＰＵ３は、Ｓｔｅｐ１２〜Ｓｔｅｐ１４の間に他の処理を実行できる。また、ＣＰＵ４は、Ｓｔｅｐ１２〜〜Ｓｔｅｐ１９の間に他の処理を実行できる。
【００９３】
ここで、図７を参照して、本発明の概要を改めて説明する。図７は、本発明にかかるマルチプロセッサシステムの本質的部分のみを抽出して記載したブロック図である。マルチプロセッサシステムは、ＣＰＵ１と、ＣＰＵ２と、メモリコントローラ２０と、メモリ３０と、を有する。メモリコントローラ２０は、セマフォ制御回路２０４を有する。
【００９４】
メモリ３０は、ＣＰＵ１及びＣＰＵ２からアクセスされる。すなわち、メモリ３０は、共有されるリソースである。セマフォ制御回路２０４は、ＣＰＵ１、ＣＰＵ２からメモリ３０へのロック命令、アンロック命令を受信して、メモリ３０の同期制御を行う。
【００９５】
詳細には、セマフォ制御回路２０４は、ロックを行ったプロセッサがロック処理を行っている時間（ロック処理時間）をカウントする。また、セマフォ制御回路２０４は、ロック中にロック命令を送信したプロセッサの命令送信順序を保持し、算出済みのロック処理時間と、命令送信順序を基に、ロックに失敗した各プロセッサの待ち時間を算出して通知する。なお、セマフォ制御回路２０４は、ロック成功時にも、ロック成功をロック命令発行元に対して通知する。
【００９６】
上述のように、セマフォ制御回路２０４は、算出済みのロック処理時間と、命令送信順序を基に、各プロセッサの待ち時間を通知する。ロックに失敗した各プロセッサは、ロック命令の発行順に応じた正確な待ち時間を把握することができるため、適切なタイミングでロック命令を再発行できる。これにより、不要なロック命令の発行を回避することができ、ＣＰＵの処理負荷を軽減することができる。さらに、正確な待ち時間に基づいてロック命令を再発行するため、セマフォの使用効率を向上することができる（アンロック後に即座にロック処理ができる）。
【００９７】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【符号の説明】
【００９８】
１０−１〜１０−ｎ  ＣＰＵ（Central Processing Unit）
２０  メモリコントローラ
２０１  ＣＰＵ命令調停回路
２０２  ＣＰＵ命令デコーダ
２０３  メモリ制御回路
２０４  セマフォ制御回路
２０４１  ＬＯＣＫアドレスバッファ（ＬＡＢ）
２０４１１  Ｖビット
２０４１２  セマフォアドレス
２０４１３  ＬＯＣＫ時間
２０４１４  アドレス比較器
２０４１５  セレクタ
２０４２  ＬＯＣＫ競合テーブル（ＬＣＴ）
２０４２１  Ｖビット
２０４２２  セマフォアドレス
２０４２３  ステータスフラグ
２０４２４  受付番号
２０４２５  優先番号
２０４２６  ＬＯＣＫ時間
２０４２７  アドレス比較器
２０４２８  セレクタ
２０４３  ＬＯＣＫ成功・失敗判定回路
２０５  ＣＰＵ命令返信回路
３０  メモリ
【図１】
0005863021.tif 000002
【図２】
0005863021.tif 000003
【図３】
0005863021.tif 000004
【図４】
0005863021.tif 000005
【図５】
0005863021.tif 000006
【図６】
0005863021.tif 000007
【図７】
0005863021.tif 000008
【図８】
0005863021.tif 000009
【図９】
0005863021.tif 000010
【図１０】
0005863021.tif 000011