(57)【特許請求の範囲】
【請求項１】
複数の実行体が並列に実行される計算機システムの共有資源排他制御方式であって、
共有資源の使用権を獲得している実行体を特定する実行体識別情報を格納するロックワード、及び他の実行体が使用権を獲得している間にその使用権の獲得要求を行った実行体のうち、最後に獲得要求を行った実行体の実行体識別情報を格納するロックキューヘッダからなる排他制御管理テーブルと、
個々の実行体毎に割り当てられ、割り当てられた実行体の実行体識別情報を格納する管理領域と、
実行体から前記共有資源の使用権の獲得要求を受け付けたとき、あるいは使用権の解放要求を受け付けたときに、要求元の実行体に割り当てられている管理領域の内容と、前記排他制御管理テーブルのロックキューヘッダの内容とを入れ替えることにより、他の実行体が使用権を獲得している間にその使用権の獲得要求を行った実行体を連鎖する擬似的な待ち行列を生成する資源管理手段と、
前記共有資源の使用権を獲得するために待ち状態となる実行体の処理を中断させるとともに、待ち状態にあった実行体が使用権を獲得したときに、この実行体の処理を再開させる実行体制御手段とを備える共有資源の排他制御方式。
【請求項２】
前記資源管理手段は、
前記実行体から前記共有資源の使用権の獲得要求を受け付けると、
前記実行体に割り当てられている管理領域に格納されている実行体識別情報と、前記排他制御管理テーブルのロックキューヘッダに格納されている値とを入れ替え、
入れ替え後の管理領域の値が、ロックキューヘッダの初期値であるか否かを判別し、
前記管理領域の値がロックキューヘッダの初期値である場合には、前記排他制御管理テーブルのロックワードに、他の実行体の実行体識別情報が格納されているか否かを判別し、
前記ロックワードに、他の実行体の実行体識別情報が格納されていなければ、前記ロックワードに前記獲得要求の要求元の実行体の実行体識別情報を書き込み、
前記管理領域の値がロックキューヘッダの初期値でない場合には、前記実行体制御手段に対して、前記実行体の処理を中断させる命令を通知する、
請求項１記載の共有資源の排他制御方式。
【請求項３】
前記資源管理手段は、
共有資源の使用権を獲得している実行体から、前記使用権の解放要求を受け付けると、
前記実行体に割り当てられている管理領域に格納されている値と、前記ロックキューヘッダに格納されている値とを入れ替え、
入れ替え後の管理領域の値が、前記実行体の実行体識別情報を示しているか否かを判別し、
前記入れ替え後の管理領域の値が、前記実行体の実行体識別情報を示している場合には、前記ロックワードをリセットし、
前記入れ替え後の管理領域の値が、他の実行体の実行体識別情報を示している場合には、待ち状態の実行体が存在することを判定し、前記ロックワードに前記他の実行体の実行体識別情報を設定し、
前記実行体制御手段に対して、前記他の実行体の処理再開を依頼し、
前記処理再開された実行体に割り当てられている管理領域の値が、前記解放要求の要求元の実行体の実行体識別情報を示しているか否かを判別し、
前記処理再開された実行体に割り当てられている管理領域の値が、前記解放要求の要求元の実行体の実行体識別情報を示している場合には、前記処理再開された実行体が、待ち状態にある実行体のうち、最初に使用権の獲得要求を行った実行体であることを判定し、
前記処理再開された実行体に割り当てられている管理領域の値が、前記解放要求の要求元の実行体とは異なる実行体の実行体識別情報を示している場合には、前記処理再開された実行体より先に、使用権の獲得要求を行った実行体が存在することを判定する、
請求項１記載の共有資源の排他制御方式。
【請求項４】
使用権の解放処理中に、使用権の獲得要求を行った実行体の実行体識別情報を登録するロック委譲領域を、前記排他制御管理テーブルに更に備え、
前記資源管理手段は、
前記使用権の解放処理が終了すると、前記ロック委譲領域を参照して、解放処理の途中で使用権の獲得要求を行った実行体が存在するか否かを判別し、
使用権の獲得要求を行った実行体が存在すれば、前記実行体制御手段に対して、前記実行体の処理を再開させることを依頼する、
請求項３記載の共有資源の排他制御方式。
【請求項５】
前記資源管理手段は、
前記使用権の解放処理が終了すると、再度、排他制御テーブルのロックキューヘッダを参照して、初期値が設定されているか、あるいは実行体識別情報が設定されているかを判別し、
前記ロックキューヘッダに実行体識別情報が設定されていれば、前記解放処理の途中で使用権の獲得要求を行った実行体が存在することを判定し、前記実行体制御手段に対して、前記実行体識別情報によって特定される実行体の処理を再開させることを依頼する、
請求項３記載の共有資源の排他制御方式。
【請求項６】
前記資源管理手段は、
前記使用権の解放処理を割り込み禁止処理によって実行する請求項３記載の共有資源の排他制御方式。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、スワップ処理が可能な計算機システムにおいて高速なサスペンドロックを実現する技術に関する。
【０００２】
【従来の技術】
複数の実行体を並列に起動する計算機においては、各実行体が共通に使用できる共有資源が用意されている。そして、各実行体は、共有資源を使用する際に、共有資源を排他的に使用する権利（以下、「使用権」と記す）を獲得した上で、共有資源を使用する。尚、ここでいう実行体とは、タスクやスレッド等を示すものとする。
【０００３】
従来、共有資源の排他制御の方法としては、スピンロック等のビジーウェイト方式が使用されているが、この方式では、使用権の待ち合わせ処理に、ループ処理が必要となるため、ＣＰＵを無駄に使用するという問題がある。
【０００４】
また、実行優先度が異なる実行体同士で、使用権獲得のための競合が発生すると、二次的デッドロックが発生する虞がある。すなわち、例えば、実行優先度の低い実行体が使用権を獲得している際に、実行優先度の高い実行体からの使用権の獲得要求が発生すると、実行優先度の高い実行体の使用権獲得処理において、スピンループ処理が永遠に実行され続け、二次デッドロックが発生する虞がある。
【０００５】
上記の問題を解決するために、サスペンドロックと呼ばれる処理がある。このサスペンドロックでは、使用権の待ち合わせを行う実行体の処理を中断して、その処理からＣＰＵを解放する。そして、使用権を解放する実行体が、待ち実行体の処理を再開させることにより、待ち状態の実行体にＣＰＵ資源が再度割り当てられて、その実行体の処理が再開される。
【０００６】
このサスペンドロック方式によれば、実行体の待ち合わせを行う際に、その実行体の処理からＣＰＵを解放することにより、ＣＰＵ資源を無駄に消費することがなくなるという利点がある。
【０００７】
【発明が解決しようとする課題】
ところで、上記のサスペンドロック方式では、使用権を解放する実行体が、待ち実行体へ使用権を委譲する際に、委譲すべき実行体を判別するための使用権待ち行列を必要とする。この待ち行列の作成は、コンペアスワップ命令等の特殊なシリアライズ命令を使用したり、割り込み禁止処理等を使用して行われている。このため、コンペアスワップ命令等の特殊なシリアライズ命令が用意されていないと、サスペンドロックを実現できないという問題がある。
【０００８】
そこで、本発明は、特殊なシリアライズ命令を備えていない計算機でも、アトミックにスワップ処理を行える計算機であれば、サスペンドロックを実現できる技術を提供することを課題とする。
【０００９】
【課題を解決するための手段】
本発明は、前記課題を解決するために以下のようにした。
すなわち、共有資源の排他制御方式は、排他制御管理テーブル、個々の実行体に割り当てられる管理領域、資源管理手段、及び実行体制御手段を備えている。
【００１０】
排他制御テーブルは、共有資源の使用権を獲得している実行体を特定する実行体識別情報を格納するロックワード、及び他の実行体が使用権を獲得している間にその使用権の獲得要求を行った実行体のうち、最後に獲得要求を行った実行体の実行体識別情報を格納するロックキューヘッダを備えている。
【００１１】
管理領域は、各実行体毎に割り当てられる記憶領域であり、各記憶領域には、割り当てられた実行体の実行体識別情報が格納される。
ここで、ロックワードには、共有資源の使用権が空き状態にある場合には、初期値が設定されている。そして、ある実行体が共有資源の使用権を獲得したときに、その実行体の実行体識別情報が設定される。さらに、ロックワードは、使用権を獲得している実行体が使用権を解放したときにリセットされるが、このとき、使用権が空くのを待っていた実行体が存在すると、その実行体の実行体識別情報が書き込まれることになる。
【００１２】
ロックキューヘッダには、共有資源の使用権が空き状態にある場合には、初期値が設定されている。そして、ある実行体からの使用権の獲得要求が発生すると、その実行体に割り当てられている管理領域の値と入れ替えられる（スワップ処理）。例えば、使用権が空き状態にあり、ロックキューヘッダに初期値が設定されているときに、ある実行体Ａからの使用権の獲得要求が発生すると、実行体Ａに割り当てられている管理領域に設定されている実行体識別情報“Ａ”と、ロックキューヘッダの初期値とが入れ替えられる。そして、実行体Ａが使用権を獲得している間に、実行体Ｂからの使用権の獲得要求が発生すると、実行体Ｂに割り当てられている管理領域に設定されている実行体識別情報“Ｂ”と、ロックキューヘッダの値“Ａ”とが入れ替えられる。このとき、ロックキューヘッダには、実行体識別情報“Ｂ”が設定され、実行体Ｂの管理領域には、実行体識別情報“Ａ”が設定されることになる。さらに、実行体Ｃからの使用権の獲得要求が発生すると、ロックキューヘッダの値”Ｂ”と、実行体Ｃに割り当てられている管理領域に設定されている実行体識別情報“Ｃ”とがスワップされる。このとき、ロックキューヘッダには、実行体識別情報“Ｃ”が設定され、実行体Ｃの管理領域には実行体識別情報“Ｂ”が設定され、さらに実行体Ｂの管理領域には実行体識別情報“Ａ”が設定されることになる。このように、ロックキューヘッダと管理領域とのスワップ処理を実行することにより、ロックキューヘッダ→実行体Ｃ→実行体Ｂの連鎖が発生し、これを擬似的な一方向性待ち行列として使用することができる。
【００１３】
そして、資源管理手段は、使用権の獲得要求を受け付けたときに、前述したような入れ替え処理（スワップ処理）を実行して、擬似的な待ち行列を生成する。また、使用権の解放要求を受け付けたときには、待ち行列を利用して、使用権の移転を行う。
【００１４】
実行体制御手段は、待ち状態になった実行体の処理を中断する。そして、待ち状態の実行体に使用権が移転されると、その実行体の処理を再開させる。この実行体制御手段は、例えば、各実行体毎に、各実行体の状態管理テーブルを有し、状態管理テーブルの状態識別情報を書き換えることにより、処理の中断あるいは処理の再開を実現することができる。
【００１５】
また、前記資源管理手段は、実行体から使用権の獲得要求を受け付けると、その実行体に割り当てられている管理領域に設定されている実行体識別情報と、前記排他制御管理テーブルのロックキューヘッダに格納されている値とを入れ替える。そして、入れ替え後の管理領域の値が、ロックキューヘッダの初期値であるか否かを判別することにより、待ち状態の実行体が存在しているか否かを判別する。すなわち、入れ替え後の管理領域に、ロックキューヘッダの初期値が設定されている場合には、待ち状態の実行体が存在しないことを判定する。一方、入れ替え後の管理領域に、他の実行体の実行体識別情報が設定されている場合には、待ち状態の実行体が存在していることを判定する。この場合には、資源管理手段は、実行体制御手段に対して、要求元の実行体の処理の中断を依頼し、要求元の実行体を待ち状態にする。
【００１６】
待ち状態の実行体が存在しない場合には、ロックワードの値を参照して、使用権が空き状態にあるか否かを判別する。ここで、ロックワードに初期値が設定されていれば、使用権が空き状態にあることが判定される。そして、ロックワードには、要求元の実行体の実行体識別情報が格納される。これにより、要求元の実行体は、共有資源の使用権を獲得したことになる。
【００１７】
ロックワードに他の実行体の実行体識別情報が格納されていれば、他の実行体が使用権を獲得している状態にあることが判定される。そして、要求元の実行体は、処理を中断されて待ち状態になる。具体的には、ロックキューヘッダに初期値が設定され、且つロックワードに他の実行体の実行体識別情報が格納されているケースとしては、他の実行体の使用権を解放処理している最中（ロックキューヘッダをリセットした後であり、ロックワードをリセットする前）に、割り込んだケースが考えられる。
【００１８】
ここで、本発明における使用権の解放手順について述べる。資源管理手段は、共有資源の使用権を獲得している実行体から、前記使用権の解放要求を受け付けると、その実行体に割り当てられている管理領域に設定されている値と、前記ロックキューヘッダに設定されている値とを入れ替える。そして、入れ替え後の管理領域の値が、前記実行体の実行体識別情報を示しているか否かを判別し、前記入れ替え後の管理領域の値が、前記実行体の実行体識別情報を示している場合には、前記ロックワードをリセットする。一方、入れ替え後の管理領域の値が、他の実行体の実行体識別情報を示している場合には、待ち状態の実行体が存在することを判定し、前記ロックワードに前記他の実行体の実行体識別情報を設定すると共に、実行体制御手段に対して、前記他の実行体の処理再開を依頼する。さらに、処理再開された実行体に割り当てられている管理領域の値が、前記解放要求の要求元の実行体の実行体識別情報を示しているか否かを判別し、処理再開された実行体に割り当てられている管理領域の値が、前記解放要求の要求元の実行体の実行体識別情報を示している場合には、前記処理再開された実行体が、待ち状態にある実行体のうち、最初に使用権の獲得要求を行った実行体であることを判定する。また、前記処理再開された実行体に割り当てられている管理領域の値が、前記解放要求の要求元の実行体とは異なる実行体の実行体識別情報を示している場合には、前記処理再開された実行体より先に、使用権の獲得要求を行った実行体が存在することが判定される。
【００１９】
このような流れにおいて、他の実行体の使用権を解放処理している最中（ロックキューヘッダをリセットした後であり、ロックワードをリセットする前）に、使用権の獲得要求が割り込んだ場合には、要求元の実行体は、永遠に待ち状態（デッドロック）に陥る虞がある。このため、本発明では、以下のような手段を講じている。
（１）、使用権の解放処理中に、使用権の獲得要求を行った実行体の実行体識別情報を登録するロック委譲領域を、排他制御管理テーブルに設ける。そして、資源管理手段は、使用権の解放処理が終了すると、前記ロック委譲領域を参照して、解放処理の途中で使用権の獲得要求を行った実行体が存在するか否かを判別し、使用権の獲得要求を行った実行体が存在すれば、前記実行体制御手段に対して、前記実行体の処理を再開させることを依頼する。
（２）、資源管理手段は、使用権の解放処理が終了すると、再度、排他制御テーブルのロックキューヘッダを参照して、初期値が設定されているか、あるいは実行体識別情報が設定されているかを判別する。そして、ロックキューヘッダに、実行体識別情報が設定されている場合には、前記解放処理の途中で使用権の獲得要求を行った実行体が存在することを判定し、実行体制御手段に対して、実行体識別情報によって特定される実行体の処理を再開させることを依頼する。
（３）、資源管理手段は、使用権の解放処理を割り込み禁止処理によって実行する。
【００２０】
【発明の実施の形態】
以下、本発明の実施形態について図面に沿って説明する。
《実施形態１》
共有資源の排他制御方式を実現する計算機システムの機能別構成を図１に沿って説明する。
【００２１】
同図に示す計算機システムは、複数の実行体を並列に実行することができるシステムであり、且つ、スワップ処理機能を有する計算機システムとする。  ここで、スワップ処理機能は、計算機システムの機械語の一つのスワップ命令として実現される。スワップ命令が実行されると、オペランドによる指定に応じて、メモリとレジスタの間、レジスタとレジスタの間、あるいは、メモリとメモリの間で、相互に記憶されている値が交換される。一つの機械語命令を実行中に計算機システムに対して、割り込みが発生すると、割り込みに対する処理は実行中の機械語命令の処理が完了した後に行われる。従って、スワップ命令実行中に割り込みが発生しても、スワップ処理、即ち値の交換は完全な形で行われる。また、当然のこととして、スワップ命令の実行前に割り込みが発生した場合には、値の交換は行われない。
【００２２】
そして、計算機システムは、計算機のメモリ１内に設定された排他制御管理テーブル１ａと、レジスタ２内に設定された管理領域２ａと、計算機のＣＰＵがプログラムを実行することにより実現される資源管理部３と、同様にＣＰＵがプログラムを実行することにより実現される実行体制御部４とを備えている。
【００２３】
排他制御管理テーブル１ａには、ロックワード領域、ロックキューヘッダ領域、２次キュー領域、キュー終了値領域、及びロック委譲領域が設定されている。ロックワード領域には、共有資源の使用権を獲得した実行体の実行体ＩＤが格納される。また、共有資源の使用権が空き状態にある場合には、初期値“０”が設定される。
【００２４】
ロックキューヘッダ領域は、初期状態において初期値“NULL”を登録するが、ある実行体からの共有資源の使用権の獲得要求が発生すると、その実行体に割り当てられている管理領域２ａの値（要求元実行体の実行体ＩＤ）と、このロックキューヘッダ領域の値（初期値“NULL”）とがスワップされて、要求元の実行体の実行体ＩＤが格納される。さらに、ある実行体が共有資源の使用権を獲得している間に、他の実行体からの使用権の獲得要求が発生すると、他の実行体に割り当てられている管理領域２ａの値（他の実行体の実行体ＩＤ）と、このロックキューヘッダ領域の値（使用権を獲得している実行体の実行体ＩＤ）とがスワップされて、前記他の実行体の実行体ＩＤが格納される。このように、ある一つの実行体が使用権を獲得している間に、他の実行体からの獲得要求が発生すると、ロックキューヘッダ領域の値は、次々に更新されていく。これにより、ロックキューヘッダ領域には、最後に使用権の獲得要求を行った実行体の実行体ＩＤが格納されることになり、その実行体に割り当てられている管理領域２ａには、その実行体の直前に使用権の獲得要求を行った実行体の実行体ＩＤが格納され、さらに、直前の実行体に割り当てられている管理領域２ａには、さらに直前に使用権の獲得要求を行った実行体の実行体ＩＤが格納されることになる。従って、ロックキューヘッダ領域の値を参照することにより、最後に使用権の獲得要求を行った実行体から、最初に使用権の獲得要求を行った実行体までを擬似的な一方向性キューとして取り扱うことができる（以下、擬似的な一方向性キューを「１次キュー」と記す）。
【００２５】
尚、１次キューは、一つの実行体が使用権を獲得している間に、使用権の獲得要求を行った実行体を対象としており、使用権が他の実行体へ移転する時点で、一括デキューされる。すなわち、ロックキューヘッダ領域の値は、使用権が他の実行体へ移転する際に、初期値“NULL”にリセットされるようになっているため、ロックキューヘッダ領域と１次キューとのつながりが断たれてしまう（以下、一括デキューされたキューを「２次キュー」と記す）。
【００２６】
２次キュー領域には、２次キューのうち、最後に使用権の獲得要求を行った実行体の実行体ＩＤが格納される。
キュー終了値には、ある実行体が使用権を獲得した時に、その実行体の実行体ＩＤが設定される。
【００２７】
また、レジスタ２には、複数の管理領域２ａが設定されている。そして、各管理領域２ａは、個々の実行体毎に割り当てられ、割り当てられた実行体のみがアクセスすることができる領域となっている。そして、各領域には、割り当てられた実行体を特定する実行体ＩＤが格納されている。
【００２８】
資源管理部３は、ロック処理部３ａとアンロック処理部３ｂとから構成されている。
ロック処理部３ａは、実行体から共有資源の使用権の獲得要求を受けると、メモリ１の内容とレジスタ２の内容とをスワップして、要求元の実行体に使用権を付与するか、あるいは要求元の実行体を１次キューに連結するかを制御する。
【００２９】
アンロック処理部３ｂは、使用権を獲得している実行体から、使用権の解放要求を受けると、メモリ１の内容とレジスタの内容とをスワップして、使用権の解放を行う。このとき、１次キューが存在すれば、この１次キューを２次キューへ切り換える。
【００３０】
ここで、ロック処理部３ａの処理について、図２に沿って説明する。
ロック処理部３ａは、ある実行体から共有資源の使用権の獲得要求とともに、その実行体の実行体ＩＤを受け取ると、メモリ１の排他制御管理テーブル１ａからロックワード領域の値を読み出す。そして、読み出されたロックワード値と、受け取った実行体ＩＤとを比較して、一つの実行体が使用権を二重に獲得することを防止する（Ｓ２０１）。
【００３１】
ここで、ロックワード値と実行体ＩＤとが不一致の場合に限り、処理を続行する。すなわち、管理領域２ａの値（実行体ＩＤ）と、排他制御管理テーブル１ａのロックキューヘッダ領域の値とをスワップする（Ｓ２０２）。
【００３２】
続いて、ロック処理部３ａは、スワップ後の管理領域２ａの値が、ロックキューヘッダ領域の初期値“NULL”であるか否かを判別する（Ｓ２０３）。
ここで、ロックキューヘッダ領域の初期値が“NULL”であるならば、１次キューが存在しないことが判定される。そして、ロック処理部３ａは、排他制御管理テーブル１ａのロックワード領域の値が初期値“０”であるか否かを判別する（Ｓ２０４）。
【００３３】
ロックワード領域の値が初期値“０”ならば、使用権が空き状態にあることが判定される。そして、ロック処理部３ａは、ロックワード領域に要求元実行体の実行体ＩＤを設定する（Ｓ２０５）。
【００３４】
この時点では、１次キューも２次キューも存在しないため、キュー終了値領域には、要求元の実行体の実行体ＩＤが書き込まれる（Ｓ２０６）。
これにより、要求元の実行体は、共有資源の使用権を獲得したことになる。
【００３５】
上述のＳ２０４において、ロックワード領域の値が初期値“０”でない場合には、すなわち、実行体からの使用権の獲得要求が、他の実行体の使用権の解放処理中に発生した割り込み処理である場合には、要求元の実行体の実行体ＩＤを排他制御管理テーブル１ａのロック委譲領域に設定し（Ｓ２０７）、要求元の実行体の処理を中断させる。
【００３６】
そして、他の実行体の使用権の解放処理においては、ロックワード領域の値が初期値“０”に書き換えられた後に、ロック委譲領域が参照されるので、このロック委譲領域に要求元実行体の実行体ＩＤが格納されていれば、要求元実行体の処理を再開することができる。
【００３７】
そこで、要求元の実行体の処理が再開されると、ロックワード領域の値を参照して、初期値"０"が設定されているか否かを判別する（Ｓ２０８）。ここで、ロックワード領域の値に、"０"が設定されていれば、ロック委譲領域を"０"にリセットし（Ｓ２０９）、ロックワード領域に要求元の実行体の実行体ＩＤを設定する（Ｓ２１０）。さらに、キュー終了値にも、要求元の実行体の実行体ＩＤが設定される（Ｓ２１１）。これにより、要求元の実行体は、供給資源の使用権を獲得したことになる。
【００３８】
また、上述のＳ２０８において、ロックワード領域の値に、"０"が未だ設定されていない場合には、実行体制御部４に対して、要求元の実行体の処理を中断させることを依頼する（Ｓ２１２）。その後に、要求元の実行体の処理が再開されると、ロックワード領域の値が、処理を再開された実行体の実行体ＩＤであるか否かを判別し（Ｓ２１３）、ロックワード領域の値が処理を再開された実行体の実行体ＩＤと一致するならば、ロック委譲領域を"０"にリセットし（Ｓ２１４）、キュー終了値を"NULL"にリセットし（Ｓ２１５）、さらに２次キュー領域を"NULL"にリセットする（Ｓ２１６）。
【００３９】
また、Ｓ２１３において、ロックワード領域の値と、処理を再開された実行体の実行体ＩＤとが不一致ならば、前述のＳ２０８以降の処理を繰り返し行う。
次に、前述のＳ２０３において、スワップ後の管理領域の値が初期値“NULL”でない場合の処理について図３に沿って説明する。
【００４０】
先ず、スワップ後の管理領域の値が初期値“NULL”でない場合には、待ち状態の実行体が存在していることを示しており、要求元の実行体も待ち状態にする必要がある。従って、ロック処理部３ａは、実行体制御部４に対して、要求元の実行体の処理の中断を依頼する（Ｓ２１７）。
【００４１】
このとき、ロックキューヘッダ領域には、要求元の実行体の実行体ＩＤが格納されており、要求元の実行体に割り当てられている管理領域２ａには、直前に使用権の獲得要求を行った実行体の実行体ＩＤが格納されていることになる。これにより、ロックキューヘッダ領域の値を参照すれば、最後に使用権の獲得要求を行った実行体を判別することができ、さらにその実行体に割り当てられている管理領域を参照すれば、その実行体の直前に使用権の獲得要求を行った実行体を判別することができる。そして、待ち状態にある実行体のうち、最初に使用権の獲得要求を行った実行体に割り当てられている管理領域２ａには、使用権を獲得している実行体の実行体ＩＤが格納されていることになる（図５参照）。本実施形態では、このようなつながりを擬似的な一方向性キューとして使用する。
【００４２】
そして、使用権を獲得している実行体が使用権の解放要求を行うと、ロックキューヘッダ領域に示されている実行体から順に、処理が再開される。このとき、処理を再開された実行体の実行体ＩＤと、ロックワード領域の値とを照合し（Ｓ２１８）、双方が一致すれば、処理が再開された実行体に割り当てられている管理領域２ａの値と、排他制御管理テーブル１ａのキュー終了値とが一致するか否か、すなわち、処理を再開された実行体の他に待ち状態の実行体が存在するか否かを判別する（Ｓ２１９）。
【００４３】
ここで、管理領域２ａの値とキュー終了値とが一致すれば、処理を再開された実行体が最後の待ちキューであることが判定され、キュー終了値を初期値“NULL”にリセットすると共に（Ｓ２２０）、２次キュー領域を初期値“NULL”にリセットする（Ｓ２２１）。
【００４４】
また、上述のＳ２１９において、処理が再開された実行体の他に、待ち状態の実行体が存在することが判定された場合には、処理が再開された実行体に割り当てられている管理領域２ａの値を２次キュー領域に設定する（Ｓ２２２）。
【００４５】
次に、図４に沿ってアンロック処理部３ｂの処理について説明する。
アンロック処理部３ｂは、使用権を獲得している実行体から使用権の解放要求を受けると、先ず、その実行体の実行体ＩＤとロックワード領域の実行体ＩＤとを照合し、使用権を獲得していない実行体からの使用権解放要求を排除する（Ｓ４０１）。
【００４６】
ここで、要求元の実行体の実行体ＩＤとロックワード領域の値とが一致すれば、排他制御管理テーブル１ａの２次キュー領域を参照し、待ち状態の２次キューが存在するか否かを判別する（Ｓ４０２）。
【００４７】
２次キューが存在しなければ、要求元の実行体に割り当てられている管理領域２ａの値（初期値“NULL”）と、ロックキューヘッダ領域の値とをスワップする（Ｓ４０３）。
【００４８】
そして、スワップ後の管理領域の値と、排他制御管理テーブル１ａのキュー終了値とを比較する。ここで、双方の値が一致すれば、待ち状態の実行体が存在しないことが判定され、排他制御管理テーブル１ａのロックワード領域に初期値“０”がリセットされる（Ｓ４０５）。
【００４９】
さらに、上述のＳ４０３〜Ｓ４０５の間に、割り込み処理による使用権の獲得要求が行われていないか否かを判別するために、排他制御管理テーブル１ａのロックキューヘッダ領域の値が初期値“NULL”のままであるか否かを判別する（Ｓ４０６）。
【００５０】
ここで、ロックキューヘッダ領域の値が初期値“NULL”ならば、使用権の解放処理を終了する。
また、上述のＳ４０２において、２次キュー領域の値が初期値“NULL”ではない場合、すなわち、２次キューが存在する場合には、２次キュー領域に格納されている実行体ＩＤを、ロックワード領域に設定し（Ｓ４０８）、実行体制御部４に対して、その実行体の処理を再開させることを依頼する（Ｓ４０９）。
【００５１】
さらに、上述のＳ４０４において、スワップ後の管理領域２ａの値とキュー終了値とが不一致の場合、すなわち、待ち状態の実行体が存在する場合には、これらの実行体を２次キューとして取り扱い、スワップ後の管理領域２ａの値を、２次キュー領域に設定し（Ｓ４０７）、前述のＳ４０８及びＳ４０９と同様の処理を行う。
【００５２】
また、上述のＳ４０６において、ロックキューヘッダ領域に初期値“NULL”以外の値が格納されている場合には、排他制御管理テーブル１ａのロック委譲領域の値を参照し、割り込み処理による使用権の獲得要求が発生したか否かを判別する（Ｓ４１０）。ここで、ロック委譲領域に初期値“NULL”が設定されていれば、割り込み処理が発生しなかったことが判定され、使用権の解放処理を終了する。また、ロック委譲領域に、実行体ＩＤが設定されていれば、割り込み処理による使用権の獲得要求が発生したことを判定し、実行体制御部４に対して、その実行体の処理を再開させることを依頼する（Ｓ４１１）。
【００５３】
以上、本実施形態によれば、スワップ処理のみを用いて、擬似的な一方向性キューを作成することができる。そして、一方向性キューを利用することにより、サスペンドロック方式の排他制御を実現することができる。
【００５４】
《実施形態２》
本実施形態２における排他制御管理テーブル１ａの構成を図６に示す。
同図に示すように、排他制御管理テーブル１ａは、ロックワード領域、ロックキューヘッダ領域、２次キュー領域、及びキュー終了値領域を備えている。
【００５５】
ロックワード領域には、共有資源の使用権を獲得している実行体の実行体ＩＤが格納される。また、共有資源の使用権が空き状態にある場合には、初期値“０”が設定される。
【００５６】
ロックキューヘッダ領域には、使用権の獲得に待機している実行体のうち、最後に使用権の獲得要求を行った実行体の実行体ＩＤが格納される。尚、共有資源の使用権が空き状態にあり、且つ、待ち状態の実行体が存在しない場合には、このロックキューヘッダ領域には、初期値“NULL”が格納される。
【００５７】
２次キュー領域は、２次キューのうち、最後に使用権の獲得要求を行った実行体の実行体ＩＤが格納される。
キュー終了値領域は、ある実行体が使用権を獲得した時に、その実行体の実行体ＩＤが格納される。
【００５８】
その他の構成は、前述の実施形態１と同様であり、説明は省略する。
以下、ロック処理部３ａの処理について図７に沿って説明する。
ロック処理部３ａは、ある実行体から共有資源の使用権の獲得要求とともに、その実行体の実行体ＩＤを受け取ると、メモリ１の排他制御管理テーブル１ａからロックワード領域の値を読み出す。そして、読み出されたロックワード値と、受け取った実行体ＩＤとを比較して、一つの実行体が使用権を二重に獲得することを防止する（Ｓ７０１）。
【００５９】
ここで、ロックワード値と実行体ＩＤとが不一致の場合に限り、処理を続行する。すなわち、管理領域２ａの値（実行体ＩＤ）と、排他制御管理テーブル１ａのロックキューヘッダ領域の値とをスワップする（Ｓ７０２）。
【００６０】
続いて、ロック処理部３ａは、スワップ後の管理領域２ａの値が、ロックキューヘッダ領域の初期値“NULL”であるか否かを判別する（Ｓ７０３）。
ここで、ロックキューヘッダ領域の初期値が“NULL”であるならば、１次キューが存在しないことが判定される。そして、ロック処理部３ａは、排他制御管理テーブル１ａのロックワード領域の値が初期値“０”であるか否かを判別する（Ｓ７０４）。
【００６１】
ロックワード領域の値が初期値“０”ならば、使用権が空き状態にあることが判定される。そして、ロック処理部３ａは、ロックワード領域に要求元実行体の実行体ＩＤを設定する（Ｓ７０５）。
【００６２】
この時点で、キュー終了値領域には、要求元の実行体の実行体ＩＤが書き込まれる（Ｓ７０６）。
これにより、要求元の実行体は、共有資源の使用権を獲得したことになる。
【００６３】
上述のＳ７０４において、ロックワード領域の値が初期値“０”でない場合には、実行体からの使用権の獲得要求が、他の実行体の使用権の解放処理中に発生した割り込み処理であることが判定され、実行体制御部４に対して、要求元の実行体の処理を中断させることを依頼する（Ｓ７０７）。
【００６４】
そして、他の実行体の使用権の解放処理が終了すると、実行体制御部４に対して、要求元の実行体の処理の再開を依頼する。ここで、排他制御管理テーブル１ａのロックワード領域の値を参照し、この値が初期値“０”であるか否かを判別する（Ｓ７０８）。
【００６５】
ロックワード領域の値が初期値“０”ならば、共有資源の使用権が空き状態にあることが判定され、ロックワード領域に、要求元の実行体の実行体ＩＤを設定する（Ｓ７０９）。
【００６６】
そして、排他制御管理テーブル１ａのキュー終了値領域に、要求元の実行体の実行体ＩＤを登録する（Ｓ７１０）。
これにより、要求元の実行体は、共有資源の使用権を獲得したことになる。
【００６７】
また、上述のＳ７０８において、ロックワード領域の値が初期値以外の値の場合には、ロックワード領域の値と、要求元の実行体の実行体ＩＤとを照合する（Ｓ７１１）。ここで、双方の値が一致すれば、キュー終了値に初期値“NULL”をリセットし（Ｓ７１２）、２次キュー領域に初期値“NULL”をリセットする（Ｓ７１３）。
【００６８】
上述のＳ７１１において、ロックワード領域の値と、要求元の実行体の実行体ＩＤとが不一致の場合には、上述のＳ７０７以降の処理を繰り返し行う。
ここで、上述のＳ７０３において、スワップ後の管理領域２ａの値が初期値“NULL”ではない場合の処理について説明する。
【００６９】
すなわち、スワップ後の管理領域２ａの値が初期値“NULL”ではない場合には、１次キューが存在することが判定される。そして、ロック処理部３ａは、実行体制御部４に対して、要求元の実行体の処理を中断させることを依頼する（Ｓ７１４）。このとき、要求元の実行体は、１次キューの先頭に連結される。
【００７０】
そして、使用権を獲得している実行体が、使用権の解放要求を行うと、１次キューは、一括デキューされて、２次キューになる。そして、２次キューの先頭の実行体から順次処理が再開される。このとき、要求元の実行体の処理も、再開される。
【００７１】
要求元の実行体の処理が再開されると、排他制御管理テーブル１ａのロックワード領域の値と、要求元の実行体の実行体ＩＤとが照合される（Ｓ７１５）。
ここで、ロックワード領域に、要求元の実行体の実行体ＩＤが格納されていれば、要求元の実行体に割り当てられている管理領域２ａと、排他制御管理テーブル１ａのキュー終了値領域とが照合される（Ｓ７１６）。
【００７２】
管理領域２ａの値とキュー終了値とが一致すれば、要求元の実行体が、２次キューの最後の実行体であることが判定される。そして、排他制御管理テーブル１ａのキュー終了値領域に初期値“NULL”がリセットされ（Ｓ７１７）、２次キュー領域に初期値“NULL”がリセットされる（Ｓ７１８）。このとき、要求元の実行体は、共有資源の使用権を獲得したことになる。
【００７３】
また、上述のＳ７１６において、管理領域２ａとキュー終了値とが不一致ならば、２次キューに、要求元の実行体より先に使用権の獲得要求を行った実行体が存在することが判定される。そして、要求元の実行体に割り当てられている管理領域２ａに格納されている実行体ＩＤが、２次キュー領域に設定される（Ｓ７２１）。
【００７４】
上述のＳ７１５において、ロックワード領域に、要求元の実行体の実行体ＩＤが格納されていない場合には、ロックワード領域の値が初期値“０”であるか否かが判別される（Ｓ７１９）。
【００７５】
ここで、ロックワード領域の値が初期値以外の値ならば、上述のＳ７１４以降の処理を繰り返し行う。また、ロックワード領域の値が初期値“０”ならば、要求元の実行体に割り当てられている管理領域２ａに設定されている実行体ＩＤが示す実行体の処理を再開した後に（Ｓ７２０）、上述のＳ７１４以降の処理を繰り返し行う。
【００７６】
次に、アンロック処理部３ｂの処理について図９に沿って説明する。
アンロック処理部３ｂは、使用権を獲得している実行体から、使用権の解放要求と共に、その実行体の実行体ＩＤを受けると、受けた実行体ＩＤとロックワード領域の実行体ＩＤとを照合し、使用権を獲得していない実行体からの使用権解放要求を排除する（Ｓ９０１）。
【００７７】
要求元の実行体の実行体ＩＤとロックワード領域の値とが一致する場合に限り、処理が続行される。すなわち、排他制御管理テーブル１ａの２次キュー領域を参照し、待ち状態の２次キューが存在するか否かを判別する（Ｓ９０２）。
【００７８】
２次キューが存在しなければ（２次キュー領域に初期値“NULL”が設定されていれば）、要求元の実行体に割り当てられている管理領域２ａの値（“NULL”）と、ロックキューヘッダ領域の値とをスワップする（Ｓ９０３）。
【００７９】
そして、スワップ後の管理領域の値と、排他制御管理テーブル１ａのキュー終了値とを比較する（Ｓ９０４）。ここで、双方の値が一致すれば、１次キューが存在しないことが判定され、排他制御管理テーブル１ａのロックワード領域に初期値“０”がリセットされる（Ｓ９０５）。この時点で、共有資源の使用権は、解放されたことになる。
【００８０】
また、上述のＳ４０３〜Ｓ４０５の間に、割り込み処理による使用権の獲得要求が行われていないか否かを判別するために、排他制御管理テーブル１ａのロックキューヘッダ領域の値が初期値“NULL”のままであるか否かを判別する（Ｓ９０６）。
ここで、ロックキューヘッダ領域の値が初期値“NULL”ならば、処理を終了する。一方、ロックキューヘッダ領域に、他の実行体の実行体ＩＤが格納されている場合には、割り込み処理によって１次キューが作成されたことが判定される。そして、１次キューの先頭の実行体（最後に使用権の獲得要求を行った実行体）の処理を再開させる（Ｓ９１０）。
【００８１】
上述のＳ９０２において、２次キュー領域の値が初期値“NULL”ではない場合には、ロックワード領域に、２次キュー領域に設定されている実行体ＩＤを設定し（Ｓ９０８）、２次キュー実行体の処理を再開させる（Ｓ９１０）。
【００８２】
また、上述のＳ９０４において、要求元の実行体に割り当てられている管理領域２ａの値がキュー終了値と不一致の場合には、管理領域２ａに格納されている実行体ＩＤを、２次キュー領域に設定した後（Ｓ９０７）、上述のＳ９０８及びＳ９０９と同様の処理を行う。
【００８３】
以上、本実施形態によれば、ロック委譲領域を設けなくても、前述の実施形態１と同等の効果を得ることができる。
《実施形態３》
本実施形態では、使用権の解放処理を割り込み禁止処理で行う場合について説明する。この場合の計算機システムの構成は、前述の実施形態２と同様であり、説明は省略する。
【００８４】
ここで、ロック処理部３ａの処理について図１０に沿って説明する。
ロック処理部３ａは、ある実行体から共有資源の使用権の獲得要求とともに、その実行体の実行体ＩＤを受け取ると、メモリ１の排他制御管理テーブル１ａからロックワード領域の値を読み出す。そして、読み出されたロックワード値と、受け取った実行体ＩＤとを比較して、一つの実行体が使用権を二重に獲得することを防止する（Ｓ１００１）。
【００８５】
ここで、ロックワード値と実行体ＩＤとが不一致の場合に限り、処理を続行する。すなわち、管理領域２ａの値（実行体ＩＤ）と、排他制御管理テーブル１ａのロックキューヘッダ領域の値とをスワップする（Ｓ１００２）。
【００８６】
続いて、ロック処理部３ａは、スワップ後の管理領域２ａの値が、ロックキューヘッダ領域の初期値“NULL”であるか否かを判別する（Ｓ１００３）。
ここで、ロックキューヘッダ領域の初期値が“NULL”であるならば、１次キューが存在しないことが判定される。そして、ロック処理部３ａは、排他制御管理テーブル１ａのロックワード領域の値が初期値“０”であるか否かを判別する（Ｓ１００４）。
【００８７】
ロックワード領域の値が初期値“０”ならば、使用権が空き状態にあることが判定される。そして、ロック処理部３ａは、ロックワード領域に要求元実行体の実行体ＩＤを設定する（Ｓ１００５）。
【００８８】
この時点で、キュー終了値領域には、要求元の実行体の実行体ＩＤが書き込まれる（Ｓ１００６）。
これにより、要求元の実行体は、共有資源の使用権を獲得したことになる。
【００８９】
上述のＳ１００４において、ロックワード領域の値が初期値“０”でない場合には、実行体からの使用権の獲得要求が、他の実行体の使用権の解放処理中に発生した割り込み処理であることが判定され、実行体制御部４に対して、要求元の実行体の処理を中断させることを依頼する（Ｓ１００７）。
【００９０】
そして、他の実行体の使用権の解放処理が終了すると、実行体制御部４に対して、要求元の実行体の処理の再開を依頼する。ここで、排他制御管理テーブル１ａのロックワード領域の値を参照し、この値が初期値“０”であるか否かを判別する（Ｓ１００８）。
【００９１】
ロックワード領域の値が初期値“０”ならば、共有資源の使用権が空き状態にあることが判定され、ロックワード領域に、要求元の実行体の実行体ＩＤを設定する（Ｓ１００９）。
【００９２】
そして、排他制御管理テーブル１ａのキュー終了値領域に、要求元の実行体の実行体ＩＤを登録する（Ｓ１０１０）。
これにより、要求元の実行体は、共有資源の使用権を獲得したことになる。
【００９３】
また、上述のＳ１００８において、ロックワード領域の値が初期値以外の値の場合には、ロックワード領域の値と、要求元の実行体の実行体ＩＤとを照合する（Ｓ１０１１）。ここで、双方の値が一致すれば、キュー終了値に初期値“NULL”をリセットし（Ｓ１０１２）、２次キュー領域に初期値“NULL”をリセットする（Ｓ１０１３）。
【００９４】
ここで、上述のＳ１００３において、要求元の実行体に割り当てられている管理領域２ａの値が、初期値“NULL”ではない場合の処理について図１１に沿って説明する。
【００９５】
先ず、スワップ後の管理領域の値が初期値“NULL”でない場合には、待ち状態の実行体が存在していることを示しており、要求元の実行体も待ち状態にする必要がある。従って、ロック処理部３ａは、実行体制御部４に対して、要求元の実行体の処理の中断を依頼する（Ｓ１０１４）。
【００９６】
このとき、ロックキューヘッダ領域には、要求元の実行体の実行体ＩＤが格納されており、要求元の実行体に割り当てられている管理領域２ａには、直前に使用権の獲得要求を行った実行体の実行体ＩＤが格納されていることになる。
【００９７】
そして、使用権を獲得している実行体が使用権の解放要求を行うと、ロックキューヘッダ領域に示されている実行体から順に、処理が再開される。このとき、処理が再開された実行体の実行体ＩＤと、ロックワード領域の値とが照合され（Ｓ１０１５）、双方が一致すれば、処理が再開された実行体に割り当てられている管理領域２ａの値と、排他制御管理テーブル１ａのキュー終了値とが一致するか否か、すなわち、処理を再開された実行体の他に待ち状態の実行体が存在するか否かが判別される（Ｓ１０１６）。
【００９８】
ここで、管理領域２ａの値とキュー終了値とが一致すれば、処理の再開された実行体が最後の待ちキューであることが判定され、キュー終了値を初期値“NULL”にリセットすると共に（Ｓ１０１７）、２次キュー領域を初期値“NULL”にリセットする（Ｓ１０１８）。
【００９９】
また、上述のＳ１０１６において、処理を再開された実行体の他に、待ち状態の実行体が存在することが判定された場合には、処理を再開された実行体に割り当てられている管理領域２ａの値を２次キュー領域に設定する（Ｓ１０１９）。
次に、アンロック処理部３ｂの処理について図１２に沿って説明する。
【０１００】
アンロック処理部３ｂは、使用権を獲得している実行体から、使用権の解放要求と共に、その実行体の実行体ＩＤを受けると、受けた実行体ＩＤとロックワード領域の実行体ＩＤとを照合し、使用権を獲得していない実行体からの使用権解放要求を排除する（Ｓ１２０１）。
【０１０１】
そして、要求元の実行体の実行体ＩＤとロックワード領域の値とが一致する場合に限り、処理が続行される。すなわち、排他制御管理テーブル１ａの２次キュー領域を参照し、待ち状態の２次キューが存在するか否かを判別する（Ｓ１２０２）。
【０１０２】
２次キューが存在しなければ（２次キュー領域に初期値“NULL”が設定されていれば）、要求元の実行体に割り当てられている管理領域２ａの値（“NULL”）と、ロックキューヘッダ領域の値とをスワップする（Ｓ１２０３）。
【０１０３】
そして、スワップ後の管理領域の値と、排他制御管理テーブル１ａのキュー終了値とを比較する（Ｓ１２０４）。ここで、双方の値が一致すれば、１次キューが存在しないことが判定され、排他制御管理テーブル１ａのロックワード領域に初期値“０”がリセットされる（Ｓ１２０５）。この時点で、共有資源の使用権は、解放されたことになる。
【０１０４】
上述のＳ１２０２において、２次キュー領域の値が初期値“NULL”ではない場合には、２次キューが存在することが判定される。このとき、ロックワード領域には、２次キュー領域に設定されている実行体ＩＤが設定される（Ｓ１２０７）。さらに、実行体制御部４に対して、２次キューの実行体の処理を再開することを依頼する（Ｓ１２０８）。
【０１０５】
また、上述のＳ１２０４において、要求元の実行体に割り当てられている管理領域２ａの値が、キュー終了値と不一致の場合には、管理領域２ａに格納されている実行体ＩＤを、２次キュー領域に設定した後（Ｓ１２０６）、上述のＳ１２０７及びＳ１２０８と同様の処理を行う。
【０１０６】
以上、本実施形態３によれば、前述の図１２のＳ１２０３〜Ｓ１２０５までを割り込み禁止処理として実行することにより、前述の実施形態１あるいは実施形態２と同等の効果を得ることができる。
【０１０７】
【発明の効果】
本発明によれば、ＣＳＩ等の特殊な命令を用意されていない計算機システムでも、スワップ処理を利用することにより、サスペンドロック方式の排他制御を行うことができる。
【図面の簡単な説明】
【図１】本実施形態における計算機システムの機能別構成を示す図
【図２】使用権獲得処理を示すフローチャート図（１）
【図３】使用権獲得処理を示すフローチャート図（２）
【図４】使用権解放処理を示すフローチャート図
【図５】キュー作成処理のイメージ
【図６】実施形態２における排他制御管理テーブルの構成を示す図
【図７】使用権獲得処理を示すフローチャート図（１）
【図８】  使用権獲得処理を示すフローチャート図（２）
【図９】使用権解放処理を示すフローチャート図
【図１０】使用権獲得処理を示すフローチャート図（１）
【図１１】使用権獲得処理を示すフローチャート図（２）
【図１２】使用権解放処理を示すフローチャート図
【符号の説明】
１・・メモリ
１ａ・・排他制御管理テーブル
２・・レジスタ
２ａ・・管理領域
３・・資源管理部
３ａ・・ロック処理部
３ｂ・・アンロック処理部
４・・実行体制御部
４ａ・・処理中断部
４ｂ・・処理再開部
【図１】
0003745800.tif 000002
【図２】
0003745800.tif 000003
【図３】
0003745800.tif 000004
【図４】
0003745800.tif 000005
【図５】
0003745800.tif 000006
【図６】
0003745800.tif 000007
【図７】
0003745800.tif 000008
【図８】
0003745800.tif 000009
【図９】
0003745800.tif 000010
【図１０】
0003745800.tif 000011
【図１１】
0003745800.tif 000012
【図１２】
0003745800.tif 000013