JPH04343143A - マルチプロセッサシステムにおける共有資源相互排除方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、マルチプロセッサシス
テムにおける共有資源に対する効率的な相互排除方式に
関する。

【０００２】

【従来の技術】一般にマルチプロセッサシステムにおけ
る共有資源の相互排除方式はスピンロック方式と２値セ
マフォ方式に分類され、従来、ューザはいずれかを選択
して使用している。以下にスピンロック方式、２値セマ
フォ方式について説明する。

【０００３】スピンロック方式 　　図９はスピンロック方式を用いて相互排除を行うシ
ステムの構成例である。図において、プロセッサ１，２
および主記憶装置３は一つのシステムバス４に接続され
ている。各プロセッサ１，２は、主記憶装置３に格納さ
れた任意のデータの読み出し、書き込み、および、任意
のプログラムの実行が可能である。主記憶装置３には、
鍵９０１、きわどい部分９０２、ｌｏｃｋ操作９０３、
ｕｎｌｏｃｋ操作９０４の各情報が格納される。ここで
、きわどい部分９０２は、一時には一つのプロセスしか
実行することのできないプログラムであり、相互排除の
対象である。 鍵９０１の値は１または０であり、きわどい部分９０２
の実行権を所有するプロセスが存在しているか否かを示
す（ここでは、１は存在、０は空とする）。ｌｏｃｋ操
作９０３とｕｎｌｏｃｋ操作９０４は、きわどい部分９
０２に対する相互排除を行うプログラムである。

【０００４】図１０は、ｌｏｃｋ操作９０３とｕｎｌｏ
ｃｋ操作９０４を用いて相互排除を行う操作手順であり
、あるプロセスがきわどい部分９０２へアクセスする場
合、まずｌｏｃｋ操作９０３によりきわどい部分９０２
の実行権を得て、きわどい部分９０２の使用を開始し、
それが終了すると、ｕｎｌｏｃｋ操作９０４により実行
権を解除することを示している。これにより、複数のプ
ロセスが同時にｌｏｃｋ操作９０３を実行した場合には
、ただ一つのプロセスがきわどい部分９０２を実行でき
る。このプロセスがｕｎｌｏｃｋ９０４操作を行うまで
、他のプロセスはきわどい部分９０２に入れずに空転し
て待つことになる。

【０００５】図１１はｌｏｃｋ操作の機能ブロック図で
ある。ｌｏｃｋ操作機能はロック手段１１００で構成さ
れる。 ロック手段１１００を実行した結果、「きわどい部分」
の実行権を得たプロセスはｌｏｃｋ操作を終了し（ロッ
ク成功）、「きわどい部分」の実行権が得られなかった
プロセスは繰り返しロック手段１１００の処理を実行す
る（ロック失敗）。

【０００６】図１２はｌｏｃｋ操作の処理フロー例で、
破線で囲んだ部分がロック手段１１００である。ｌｏｃ
ｋ操作は次の手順で行われる。まず、鍵（図９の９０１
）を読み出し、この読み出した鍵の値をｘとする（ステ
ップ１２０１）。次に、鍵を１、即ち、他のプロセスが
使用できないように「きわどい部分」をロックする（ス
テップ１２０２）。ここで、鍵に対する読み出し・書き
込みはｔｅｓｔ−ａｎｄ−ｓｅｔ命令など、メモリの読
み出しと書き込みが細分化されない基本演算により行わ
れる。つまり、ステップ１２０１と１２０２は実際には
１命令で実現される。 次に、ステップ１２０１で読み出した鍵値ｘを判定する
（ステップ１２０３）。そして、ｘ＝０（きわどい部分
が未使用）であったからば、該ｌｏｃｋ操作を終了とし
（ロック成功）、ｘ＝１であったならば（きわどい部分
が使用中）、ステップ１２０１に戻ってｌｏｃｋ操作を
繰り返す（ロック失敗）。このロック失敗では、鍵に１
が上書きされるだけである。

【０００７】図１３はｕｎｌｏｃｋ操作の処理を示した
ものである。あるプロセスが「きわどい部分」の実行を
終了すると、ｕｎｌｏｃｋ操作は鍵に０を書き込む。こ
のｕｎｌｏｃｋ操作で鍵に０を書き込むと、ｌｏｃｋ操
作で空転していたプロセスが０を鍵の値として読み出し
、ｌｏｃｋ操作を終了して「きわどい部分」に入ること
ができるようになる。

【０００８】２値セマフォ方式 　　図１４は２値セマフォ方式を用いて相互排除を行う
システムの構成例である。プロセッサ１，２および主記
憶装置３は一つのシステムバス４に接続されている。各
プロセッサ１，２は主記憶装置３に格納された任意のデ
ータの読み出し、書き込み、および、任意のプログラム
の実行が可能である。主記憶装置３には、きわどい部分
１４０１、セマフォｓ１４０２、セマフォｓの待ちプロ
セス行列１４０３、プロセッサ待ちプロセス行列１４０
４、Ｐ操作１４０５、Ｖ操作１４０６、プロセス切り替
えプログラム１４０７が格納される。きわどい部分１４
０１は、一時には一つのプロセスしか実行することので
きないプログラムであり、相互排除の対象である。セマ
フォｓ１４０４は０または１をとり、それぞれきわどい
部分１４０１の使用中である、あるいは、空いているこ
とを表わす。セマフォｓの待ちプロセス行列１４０３は
、きわどい部分１４０１の使用が終わるのを待っている
プロセスを整列させたＯＳの制御データである。プロセ
ッサ待ち行列１４０４は、プロセッサを割り付けると直
ちに実行可能なプロセスを整列させたＯＳの制御データ
である。Ｐ操作１４０５とＶ操作１４０６はきわどい部
分１４０１に対する相互排除を行うプログラムである。

【０００９】図１５はＰ操作１４０５とＶ操作１４０６
を用いて相互排除を行う操作手順であり、あるプロセス
がきわどい１４０１へアクセスする場合、まず、Ｐ操作
１４０５を実行し、きわどい部分１４０１が空いていれ
ば、きわどい部分１４０１へアクセスし、それが終了す
るとＶ操作１４０６を実行することを示している。これ
により、複数のプロセスが同時にＰ操作１４０５を実行
した場合には、ただ一つのプロセスがきわどい部分１４
０１を実行できる。そして、このプロセスがＶ操作１４
０６を行うまで、他のプロセスはセマフォｓの待ちプロ
セス行列１４０５で待たされることになる。

【００１０】図１６は、Ｐ操作の機能ブロック図である
。Ｐ操作機能は、ロック手段１６０１とプロセス実行制
御手段１６０３で構成される。ロック手段１６０１を実
行した結果、「きわどい部分」の実行権を得たプロセス
はＰ操作を終了する。「きわどい部分」の実行権を得ら
れなかったプロセスはプロセス実行制御手段１６０２の
処理に移り、セマフォ待ち状態（ブロック状態）で待機
し、「きわどい部分」の実行権を所有するプロセスのＶ
操作によってセマフォ待ち状態から解除された場合、「
きわどい部分」の実行権を得てＰ操作を終了する。

【００１１】図１７はＰ操作の処理フロー例で、破線で
囲まれた部分が、ロック手段１６０１およびプロセス実
行制御手段１６０２の処理である。Ｐ操作は、次の手順
で行われる。まず、セマフォｓ（図１４の１４０２）を
読み出す（ステップ１７０１）。次に、この読み出した
セマフォｓの値を判定し（ステップ１７０２）、ｓ＝１
（きわどい部分が未使用）の場合には、ｓの値を１減じ
て０（使用中）にして（ステップ１７０３）、Ｐ操作を
終了とする（ロック成功）。ここで、セマフォｓに対す
る読み出しと書き込みはプロセスからは細線化されない
基本演算として見えるものである。一方、ｓ＝０（きわ
どい部分が使用中）の場合には（ロック失敗）、このＰ
操作を実行中のプロセスをセマフォ待ちプロセス行列（
図１４の１４０３）の最後尾に加えた後（ステップ１７
０４）、プロセス切り替えプログラム（図１４の１４０
７）に制御を移し（ステップ１７０５）、Ｐ操作を終了
とする。

【００１２】図１８はＶ操作の処理フロー例である。あ
るプロセスが「きわどい部分」の使用を終了すると、Ｖ
操作では、セマフォ待ちプロセス行列１４０３が空か調
べ（ステップ１８０１）、空ならば、セマフォｓ１４０
２に１を書き込み（ステップ１８０２）、Ｖ操作を終了
とする。また、セマフォ待ちプロセス行列１４０３が空
でない場合には、このセマフォ待ち行列から先頭のプロ
セスを取り出し、プロセッサ待ちプロセス行列１４０４
の先頭に入れ（ステップ１８０３）、Ｖ操作を終了する
。適当な時間経過の後、プロセス切り替えプログラム１
４０７が実行されると、プロセッサ待ちプロセス行列１
４０４からプロセスが取り出され、Ｐ操作のプロセス実
行制御手段１６０２の終了時点から処理を再開して、「
きわどい部分」を実行する。

【００１３】

【発明が解決しようとする課題】スピンロック方式では
、「きわどい部分」が使用中の場合、プロセスが空転し
て鍵の状態を調べ、鍵が０になるまで待っているので、
「きわどい部分」のプログラムに対して、イ．短いプロ
グラムであること、 ロ．入出力など待ち状態になる操作は行わないこと、ハ
．誤りを起こして例外処理プログラムにプロセッサを取
り上げられないこと、 のような制約が課せられる。これらの制約がのため、ス
ピンロック方式は、ＯＳのカーネルなど限られたプログ
ラムの相互排除に用いられるのが一般的であり、通常の
ユーザプログラムには適しいないという欠点があった。

【００１４】ユーザプログラムでスピンロック方式を用
いた場合には、次のような問題が生じる。 （１）バグのため、「きわどい部分」の実行権を長時間
保持する状態を作り出す可能性がある。 （２）ｌｏｃｋ操作は「きわどい部分」の実行権を所有
するプロセスの状態変化を検出する機能を備えていない
。このため、「きわどい部分」の実行権を所有するプロ
セスが待ち状態に入った場合、あるいは、プロセッサを
取り上げられた場合に、空転を続けるプロセスを実行す
るプロセッサは、そのまま空転を続けて多大に無駄な時
間を費やす。 （３）ｌｏｃｋ操作の使い方に関する簡単な誤りをおか
すだけで容易にデッドロックに陥ってしまう。しかし、
ｌｏｃｋ操作は、「きわどい部分」の実行権をどのプロ
セスが所有しているか調べる機能を備えていないので、
簡単なプログラム誤りが原因となる「きわどい部分」の
実行権を決して得ることができないのに待っている状態
を検出し適切や処理を行わせることができない。

【００１５】２値セマフォ方式では、複数のプロセスが
同一の「きわどい部分」を実行しようとした場合に、Ｐ
操作で１を減じられなかったすべてのプロセスについて
次のような操作が行われるため、相互排除においてプロ
セス切り替えが頻繁に生じるという欠点がある。

【００１６】（１）Ｐ操作の度にプロセスをセマフォｓ
の待ちプロセス行列に入れ、プロセス切り替えを行う。 （２）Ｖ操作の度にセマフォｓの待ちプロセス行列から
プロセッサ割り付け待ちプロセス行列にプロセスを移す
。Ｖ操作の後に、プロセス切り替えが発生する。

【００１７】上記操作に要する処理量は、スピンロック
方式での相互排除に要する処理量に比べ極めて大きく、
かつ、上記操作は「きわどい部分」の実行権を所有する
プロセスが既に存在する場合には必須であるので、プロ
セスの処理で大きなオーバヘッドとして現われるという
欠点がある。特に、２値セマフォ方式は、処理量の小さ
なプロセスが頻繁に「きわどい部分」を実行するシステ
ムでは、プロセス全体の処理において相互排除のための
オーバーヘッドが占める割合が著しく大きくなるという
欠点がある。また、Ｐ操作は、「きわどい部分」の実行
権を所有するプロセスの状態を読み出す機能を備えてい
ないので、該実行権の所有関係により生じるデッドロッ
クなどの誤りを検出し適切な処理が行われないという欠
点がある。

【００１８】相互排除を行うユーザプログラムを実行す
る場合、スピンロック方式と２値セマフォ方式のいずれ
かをユーザは選択して使用する。この時、ユーザはそれ
ぞれの方式の欠点を理解し、かつ、「きわどい部分」を
実行するプロセスの動作を考察した上で決定する必要が
ある。また、ユーザが十分考察して相互排除の方式を選
択した場合でも、スピンロック方式では「きわどい部分
」を実行するプロセスがＯＳによってプロセッサを取り
上げられるのを防ぐことはできない。そのため「きわど
い部分」の実行権を得るために空転して待つプロセスが
空転しプロセッサを消費し続ける欠点を回避することは
できない。また、２値セマフォ方式では相互排除を頻繁
に行うユーザプログラムの実行において、プロセス切り
替えのオーバーヘッドが大きくなる欠点を回避すること
はできない。

【００１９】本発明の目的は、ユーザプログラムでの相
互排除にスピンロック方式を用いた場合、「きわどい部
分」を実行するプロセスがプロセッサを取り上げられる
ために、空転して「きわどい部分」の実行権を得るのを
待つプロセスを実行するプロセッサが無駄な空転を費や
す点、および、２値セマフォ方式を用いた場合、頻繁に
相互排除が発生するとプロセス全体の処理においてプロ
セス切り替えに要するオーバーヘッドが占める割合が大
きくなる点、および、両方式の使い分けをユーザが考慮
しなくてはならない点、あるいは、相互排除における誤
り発生を検出して例外処理することができない点を解決
し、ユーザプロセスが頻繁に「きわどい部分」を実行す
るシステムにおいて効率的な共有資源相互排除方式を提
供することにある。

【００２０】

【課題を解決するための手段】本発明は、異なるプロセ
ッサ上で同時に動作可能な複数プロセスからなる並列プ
ログラムを実行させる機能と、各プロセスが主記憶に置
かれた共有資源へアクセスする機能と、一時にただ一つ
のプロセスしか使用できない部分（きわどい部分と呼ぶ
）の実行を開始する権利（実行権と呼ぶ）を相互に排除
する機能を有するマルチプロセッサシステムにおいて、
以下の機能を有するロック手段、ロック切り替え手段、
プロセス実行状態監視手段及びプロセス実行制御手段を
設ける。

【００２１】ロック手段は、「きわどい部分」の実行権
を持つプロセスが存在しているか否かを示すロック変数
に対して不可分な読み出し・書き込みを行う機能と、「
きわどい部分」の実行権を有するプロセス識別子を記録
する機能を有し、同時に１つ以上のプロセスが「きわど
い部分」の実行権を得ようとした場合に、ただ１つのプ
ロセスだけが「きわどい部分」の実行権を得ることを保
証し、「きわどい部分」の実行権を得たプロセスの識別
子を記録する。

【００２２】ロック切り替え手段は、現在の相互排除の
方式がスピンロック方式が２値セマフォ方式かを調べる
機能と、相互排除を行うプロセスのプログラムの誤りを
検出する機能を有し、現在の相互排除の方式によって「
きわどい部分」の実行権を得るために待つプロセスの待
機方法を変化させ、あるいは、誤りを起こしたプロセス
に例外処理を行わせる。

【００２３】プロセス実行状態監視手段は、ＯＳの制御
データであるプロセス制御ブロック（ＰＣＢと呼ぶ）を
プロセスのアドレス空間内にマッピングする機能と、マ
ッピングしたＰＣＢのプロセス状態フィールドを読み出
す機能と、現在の相互排除の方式をスピンロック方式か
２値セマフォ方式かに変化させる機能を有し、「きわど
い部分」の実行権を得るために待つプロセスに「きわど
い部分」の実行権を有するプロセスの実行状態を監視さ
せ、その結果に従って待機方法を変化させる。

【００２４】プロセス実行制御手段は、「きわどい部分
」の実行権を得るために待つプロセスをプロセッサ待ち
状態にすると、セマフォ待ち状態にする機能と、プロセ
ス切り替えプログラムを実行する機能を有し、プロセス
状態監視手段の結果により、「きわどい部分」の実行権
を得るために待つプロセスの実行状態をプロセッサ待ち
状態、あるいは、セマフォ待ち状態に変化させる。

【００２５】

【作用】本発明では、「きわどい部分」の実行権を有す
るプロセスの実行状態に従って、相互排除の方式をスピ
ンロック方式あるいは２値セマフォ方式に選択的に変化
して、「きわどい部分」の実行権を得るのを待つプロセ
スの実行を制御する。また、相互排除を行うプロセスの
プログラムの誤りを検出して例外処理を行わせる。これ
により、ユーザプロセスなどが頻繁に「きわどい部分」
をアクセスするような場合、相互排除を効率的に行うこ
とができるようになる。

【００２６】

【実施例】図１は本発明の一実施例のシステム構成図で
ある。図において、プロセッサ１，２および主記憶装置
３は一つのシステムバス４に接続されている。各プロセ
ッサ１，２は、主記憶装置３に格納された任意のデータ
の読み出し、書き込み、および任意のプログラムの実行
が可能である。主記憶装置３には、プロセス制御ブロッ
ク１０１、プロセッサ待ちプロセス行列１０２、セマフ
ォ待ちプロセス行列１０３、鍵１０４、きわどい部分１
０５、入口操作１０６、出口操作１０７、例外処理プロ
グラム１０８、プロセス切り替えプログラム１０９が格
納されている。

【００２７】プロセス制御ブロック（以下、ＰＣＢと呼
ぶ）１０１は、ＯＳによりプロセスごとに作られる制御
データであり、プロセスの実行状態やプロセスへの資源
の割り付け状況などが書き込まれ、ユーザプロセスから
は直接書き込み・読み出しができないよう保護されてい
る。ＰＣＢ内にはプロセスの状態フィールドがあり、プ
ロセスが実行である、あるいは、プロセッサ待ち状態で
ある、あるいは、イベント待ちなどのブロック状態であ
ることを示す。図１では、一例としてプロセスＡ、Ｂの
ＰＣＢを示し、プロセスＡ、Ｂはそれぞれプロセッサ１
，２に割り付けられて実行中であることを示している。

【００２８】プロセッサ待ちプロセス行列１０２は、プ
ロセッサを割り付けると直ちに実行可能なプロセスのＰ
ＣＢを整列させたＯＳの制御データである。セマフォ待
ちプロセス行列１０３は、きわどい部分１０５の使用が
終わるのを待っているプロセスを整列させたＯＳの制御
データである。

【００２９】鍵１０４は、ＰＣＢアドレスとロック変数
とロック型変数からなる。ＰＣＢアドレスには、きわど
い部分１０５の実行権を所有しているプロセスのＰＣＢ
の先頭アドレス、または、０が格納されている。ロック
変数は、きわどい部分１０５の実行権を所有するプロセ
スが存在するか否かを示す（１は存在、０は存在しない
とする）。ロック型変数は現在の相互排除方式がスピン
ロック方式かセマフォ方式かを示す。

【００３０】きわどい部分１０５は、一時には一つのプ
ロセスしか実行することのできないプログラムであり、
相互排除の対象である。入口操作１０６と出口操作１０
７は、きわどい部分１０５に対する相互排除を行なうプ
ログラムである。例外処理プログラム１０８は、相互排
除に関する誤りを処理するプログラムであり、プロセス
切り替えプログラム１０９はプロセッサ１，２をプロセ
スに割り付けるプログラムである。

【００３１】図２は入口操作１０６と出口操作１０７を
用いて、プロセスがきわどい部分１０５の相互排除を行
う操作手順を示したものである。即ち、あるプロセスが
「きわどい部分」をアクセスする場合、まず、入口操作
を実行し、「きわどい部分」が他のプロセスで使用中で
なければ、「きわどい部分」の実行権を得て「きわどい
部分」へアクセスし、それが終了すると、出口操作を実
行する。これにより、複数のプロセスが同時に入口操作
を実行した場合には、ただ一つのプロセスが「きわどい
部分」を実行できる。そして、このプロセスが出口操作
を行なうまで他のプロセスは「きわどい部分」に入るこ
とができない。

【００３２】図３は、入口操作の機能ブロック図である
。入口操作機能はロック手段３０１、ロック切り替え手
段３０２、プロセス実行状態監視手段３０３およびプロ
セス実行制御手段３０４で構成される。図３に示すよう
に、入口操作では、図１１のスピンロック方式、図１５
の２値セマフォ方式と比べ、ロック切り替え手段３０２
およびプロセス実行状態監視手段３０３が付加される。 また、後述するように、ロック手段３０１およびプロセ
ス実行制御手段３０４も機能拡張されている。

【００３３】次に、図４から図７を用いて入口操作の各
手段での処理を詳述するが、図１に示すように、鍵１０
５のＰＣＢアドレスとロック変数の初期値を０とし、ロ
ック型変数の初期値をスピンロック方式とし、入口操作
を実行するプロセスはプロセスＡとする。

【００３４】図４は、ロック手段３０１の処理フロー例
である。太線で囲った部分が、従来のスピンロック方式
および２値セマフォ方式に対して、本発明で新たに付加
した操作手順である。 （１）プロセスＡは鍵のＰＣＢアドレスを読み出す（ス
テップ４０１）。読み出した値をａとする。次に、この
ａの値を判定する（ステップ４０２）。ａが０（初期値
）の場合には、「きわどい部分」の実行権を所有するプ
ロセスが存在しない可能性があるため、（２）に行く。 その他の場合には、「きわどい部分」の実行権を所有す
るプロセスが存在することを意味するので、処理はロッ
ク切り替え手段３０２へ移る。 （２）ａが０の場合、鍵のロック変数を読み出す（ステ
ップ４０３）。読み出した値をｘとする。次に鍵のロッ
ク変数を１にする（ステップ４０４）。ここで、ロック
変数に対する読み出し・書き込みはｔｅｓｔ−ａｎｄ−
ｓｅｔ命令などによって不可分演算によりなされるもの
である。次に、読み出したロック変数の値ｘを判定する
（ステップ４０５）。ｘが０の場合には、プロセスＡが
「きわどい部分」の実行権を得たことを意味するので、
（３）へ行く。ｘが０でない場合には、（１）に行く。 これらの操作はスピンロック方式および２値セマフォ方
式での手順と同一である。 （３）読み出した鍵のロック変数の値ｘが０の場合、プ
ロセスＡ（自プロセス）のＰＣＢの先頭アドレスを鍵の
ＰＣＢアドレスに書き込み、入口操作を終了する（ステ
ップ４０６）。

【００３５】図５は、ロック切り替え手段３０２の処理
フロー例である。ロック切り替え手段３０２は、従来の
スピンロック方式および２値セマフォ方式にはない手段
であり、本発明により付加されたものである。ロック切
り替え手段３０２の入口は、図４のステップ４０２（ｎ
０側）から制御が移された場合、すなわち、プロセスＡ
がロック手段３０１において「きわどい部分」の実行権
を得られなかった場合である。 （１）ロック手段３０１において読み出した鍵のＰＣＢ
アドレスの値ａがプロセスＡ（自プロセス）のＰＣＢの
先頭アドレスか否か判定する（ステップ５０１）。先頭
アドレスの場合、プロセスＡのプログラムに誤りがあり
、「きわどい部分」の実行権を新たに得ることができな
いことを意味するので、例外処理を行うために、後述の
プロセス実行制御手段３０４の処理へ移る。その他の場
合には、次の（２）へ行く。 （２）鍵のロック型変数の値を読み出す（ステップ５０
２）。読み出した値をｃとする。次にこのロック型変数
の値ｃを判定する（ステップ５０３）。そして、現在の
相互排除の方式が２値セマフォ方式であることをｃが示
している場合、プロセスＡは、セマフォ待ちプロセスの
状態で、「きわどい部分」の実行権が解放されるのを待
つことを意味するので、プロセス実行制御手段３０４へ
行く。それ以外の場合には、プロセス実行状態監視手段
３０３へ行く。

【００３６】図６は、プロセス実行状態監視手段３０３
の処理フロー例である。プロセス実行状態監視手段３０
３も従来のスピンロック方式および２値セマフォ方式に
はない手段であり、本発明により付加されるものである
。プロセス実行状態監視手段３０３の入口は、図５のス
テップ５０３（ｎｏ側）から制御が移された場合、すな
わち、プロセスＡが「きわどい部分」の実行権を得られ
ず、かつ、相互排除の方式がスピンロック方式の場合で
ある。 （１）ロック手段３０１で読み出した鍵のＰＣＢアドレ
スの値ａを先頭アドレスとするＰＣＢがプロセスＡ（自
プロセス）のアドレス空間内にマッピングされているか
判定し（ステップ６０１）、既に、マッピングしてある
場合には（２）へ行く。マッピングしていない場合には
、ａを先頭アドレスとするＰＣＢを、プロセスＡのアド
レス空間内にマッピングした後（ステップ６０２）、（
２）へ行く。ここでマッピングとは、アクセス可能なフ
ァイルをプロセスのアドレス空間の一部として使用する
ことであり、ＵＮＩＸのｍｍａｐなど汎用ＯＳのマッピ
ング機能を用いることにより実現される。ＵＮＩＸの場
合、ＰＣＢを含むカーネルのデータ領域がファイルの形
で提供されているため、これをマッピングすることによ
り、ＰＣＢへのアクセスが可能となる。 （２）プロセスＡのアドレス空間内にマッピングされた
値ａを先頭アドレスとするＰＣＢからプロセスの状態フ
ィールドを読み出す（ステップ６０３）。読み出した値
をｓとする。次に、このｓの状態を判定する（ステップ
６０４、６０５）。「きわどい部分」の実行権を有する
プロセスが実行中であることをｓの値が示している場合
には（ステップ６０４のｙｅｓ側）、プロセス実行制御
手段３０４の処理へ行く。「きわどい部分」の実行権を
有するプロセスが実行中でなく、プロセッサ待ちプロセ
ス行列に入っていることをｓの値が示している場合には
（ステップ６０５のｙｅｓ側）、やはりプロセス実行制
御手段３０４の処理へ行く。それ以外の場合、即ち、「
きわどい部分」の実行権を有するプロセスがイベント待
ちなど、ブロック状態であることをｓの値が示している
場合には（ステップ６０５のｎｏ側）、鍵のロック型変
数をセマフォ方式にした後（ステップ６０６）、プロセ
ス実行制御手段３０４の処理へ行く。

【００３７】図７はプロセス実行制御手段３０４の処理
フロー例である。プロセス実行制御手段３０４の入口は
、ロック切り替え手段３０２において、相互排除におけ
る誤りを検出した場合（図５のステップ５０１のｙｅｓ
側）、相互排除の方式が２値セマフォ方式を検出した場
合（図５のステップ５０３のｙｅｓ側）、及び、プロセ
ス実行状態監視手段３０３において、「きわどい部分」
の実行権を有するプロセスがブロック状態であることを
検出してロック変数をスピンロック方式から２値セマフ
ォ方式に変更した場合（図６のステップ６０６）、「き
わどい部分」の実行権を有するプロセスがプロセッサ待
ち状態であることを検出した場合（図６のステップ６０
５のｙｅｓ側）、「きわどい部分」の実行権を有するプ
ロセスが実行中であることを検出した場合（図６のステ
ップ６０４のｙｅｓ側）の計５つである。図７において
、太線で囲った部分が、従来の２値セマフォ方式に対し
て、本発明で新たに付加した操作である。 （１）図５のステップ５０１（ｙｅｓ側）から制御が移
された場合、すなわち、ロック切り替え手段３０２にお
いて、相互排除における誤りを検出した場合には、例外
処理プログラムに制御を移し（ステップ７０１）、入口
操作を終了する。 （２）図５のステップ５０３（ｙｅｓ側）から制御が移
された場合、すなわち、ロック切り替え手段３０２にお
いて、相互排除の方式が２値セマフォ方式であった場合
、および、図６のステップ６０６から制御を移された場
合、すなわち、プロセス実行状態監視手段３０３におい
て、「きわどい部分」の実行権を有するプロセスがブロ
ック状態であることを検出してセマフォ方式に変更した
場合には、従来の２値セマフォ方式と同様の待機方法で
、「きわどい部分」の実行権が解放されるのを待つため
に、汎用ＯＳが持つ２値セマフォの機能を用いて、プロ
セスＡ（自プロセス）のＰＣＢをセマフォ待ちプロセス
行列の最後尾に加える（ステップ７０２）。そして、（
４）へ行く。 （３）図６のステップ６０５（ｙｅｓ側）から制御が移
された場合、すなわち、プロセス実行状態監視手段３０
３において、「きわどい部分」の実行権を有するプロセ
スがプロセッサ待ち状態であることを検出した場合には
、「きわどい部分」の実行権を有するプロセスがプロセ
ッサを取り上げられて、停止しており、「きわどい部分
」の実行権を得るために待つプロセスに割り付けられた
プロセッサは無駄な時間を費やすことを意味するので、
自プロセスに割り付けられたプロセッサを解放するため
に、汎用ＯＳのプロセス制御機能を使用して、プロセッ
サ待ちプロセス行列の最後尾にプロセスＡのＰＣＢを入
れ（ステップ７０３）、（４）へ行く。 （４）プロセス切り替えプログラムを実行し、自プロセ
スに割り付けられたプロセッサを他のプロセスに渡す（
ステップ７０４）。しばらく後に、再び、このプロセス
（プロセスＡ）にプロセッサが割り付けられた時には、
入口操作を行うために、再びロック手段３０１へ行く（
図４のステップ４０１へ制御を移す）。この操作は、従
来の２値セマフォ方式と同一の操作である。 （５）図６のステップ６０４（ｙｅｓ側）から制御を移
された場合、すなわち、プロセス実行状態監視手段３０
３において、「きわどい部分」の実行権を有するプロセ
スが実行中であることを検出した場合には、「きわどい
部分」の実行権が比較的短時間のうちに解放される可能
性があるため、「きわどい部分」の実行権を獲得するた
めに、再びロック手段３０１へ行く（図４のステップ４
０１へ制御を移す）。

【００３８】図８は出口操作の処理フロー例である。太
線が囲った部分が従来のスピンロック方および２値セマ
フォ方式に対して本発明で新たに付加した操作である。 （１）鍵のロック型変数を読み出す（ステップ８０１）
。読み出した値をｃとする。鍵のロック型変数をビジー
ウエイト方式にし（ステップ８０２）、鍵のＰＣＢアド
レスを０にする（ステップ８０３）。次に、読み出した
鍵のロック型変数の値ｃを判定し（ステップ８０４）、
ｃの値がビジーウエイ方式の場合には（２）へ行く。ｃ
の値がセマフォ方式を示している場合には、汎用ＯＳが
持つ２値セマフォの機能を用いて以下の動作を行う。セ
マフォ待ちプロセス行列が空であるか調べ（ステップ８
０５）、空ならば（２）へ行く。空でないならばセマフ
ォ方式待ち行列内の全プロセスを取り出し、プロセッサ
待ちプロセス行列に入れ（ステップ８０６）、（２）へ
行く。 （２）鍵のロック変数を０にし、出口操作を終了する。

【００３９】

【発明の効果】本発明では、「きわどい部分」の実行権
を所有するプロセスがプロセッサを取り上げられたこと
を検出し、「きわどい部分」の実行権を得るために空転
して待つプロセスからもプロセッサを取り上げることに
より、無駄な空転によるプロセッサの浪費を抑えること
が可能となり、あるいは、「きわどい部分」の実行権を
有するプロセス実行状態に従って、相互排除の方式をス
ピンロック方式か２値セマフォ方式かを切り替えること
により、「きわどい部分」の実行権を得るために待つプ
ロセスがセマフォ待ちプロセスの状態になる回数を減少
させ、プロセス切り替えの発生回数を減少させ、プロセ
ス切り換えのオーバーヘッドを小さく抑えることが可能
となり、または、ユーザが相互排除の方式を選択する必
要がなくなり、あるいは、相互排除における誤り発生を
検出することにより例外処理を行うことが可能となり、
ユーザプロセスが頻繁に「きわどい部分」を実行するシ
ステムにおいて効率的な相互排除方式を提供することが
できるという利点がある。

【００４０】さらに、「きわどい部分」の実行権を得る
ために待つプロセスが、「きわどい部分」の実行権を所
有するプロセスのプロセス制御ブロック（ＰＣＢ）を、
自アドレス空間内にマッピングしてから、その実行状態
を調べることにより、高速に値を読み出すことができる
という利点がある。

【００４１】さらに、「きわどい部分」の実行権を所有
するプロセスが実行状態にあるとき、他のプロセスが空
転して待つ操作手順の中にメモリへの書き込み命令が存
在しないという利点がある。キヤッシュを備えたメモリ
共有型マルチプロセッサの場合には、このことは、キヤ
ッシュメモリ内のデータを参照するだけであり、主記憶
装置へのアクセスあるいは他のプロセッサのキヤッシュ
へのデータ転送が生じないことを意味し、空転のために
他のプロセッサの性能を劣化させないという利点がある
。

【図面の簡単な説明】

【図１】本発明の一実施例のシステム構成図である。

【図２】本発明方式で入口操作と出口操作を用いて相互
排除去する操作手順を示した図である。

【図３】入口操作の機能ブロック図である。

【図４】図３のロック手段の処理フロー図である。

【図５】図３のロック切り替え手段の処理フロー図であ
る。

【図６】図３のプロセス実行状態監視手段の処理フロー
図である。

【図７】図３のプロセス実行制御手段の処理フロー図で
ある。

【図８】出口操作の処理フロー図である。

【図９】従来のスピンロック方式を説明するためのシス
テム構成図である。

【図１０】スピンロック方式でｌｏｃｋ操作とｕｎｌｏ
ｃｋ操作を用いて相互排除する操作手順を示した図であ
る。

【図１１】ｌｏｃｋ操作の機能ブロック図である。

【図１２】図１１のロック手段の処理フロー図である。

【図１３】ｕｎｌｏｃｋ操作の処理フロー図である。

【図１４】従来の２値セマフォ方式を説明するためのシ
ステム構成図である。

【図１５】２値セマフォ方式でＰ操作とＶ操作を用いて
相互排除する操作手順を示した図である。

【図１６】Ｐ操作の機能ブロック図である。

【図１７】図１６のロック手段、プロセス実行制御手段
の処理フロー図である。

【図１８】Ｖ操作の処理フロー図である。

【符号の説明】

１，２　　プロセッサ ３　　主記憶装置 １０１　　プロセス制御ブロック（ＰＣＢ）１０２　　
プロセス待ちプロセス行列 １０３　　セマフォ待ちプロセス行列 １０４　　鍵 １０５　　きわどい部分 １０６　　入口操作 １０７　　出口操作 １０８　　例外処理プログラム １０９　　プロセス切り替えプログラム３０１　　ロッ
ク手段 ３０２　　ロック切り替え手段 ３０３　　プロセス実行状態監視手段 ３０４　　プロセス実行制御手段

Claims (3)

【特許請求の範囲】
1. 【請求項１】　　複数のプロセッサと主記憶装置がシス
   テムバスで接続され、異なるプロセッサ上で同時に動作
   可能な複数プロセスからなる並列プログラムが走行する
   マルチプロセッサシステムにおいて、各プロセスが主記
   憶装置の共有資源へアクセスする際、一時にただ一つの
   プロセスしか使用できない部分（以下、きわどい部分と
   呼ぶ）の実行を開始する権利（以下、実行権と呼ぶ）を
   相互に排除する方式として、「きわどい部分」の実行権
   を得ることに失敗したプロセスがプロセッサの使用権を
   放棄して待機するスピンロック型とプロセッサの使用権
   を確保したまま繰り返して実行権の獲得を試みるセマフ
   ォ型とを併用し、「きわどい部分」の実行権を得るため
   に待機するプロセスを、「きわどい部分」の実行権を有
   するプロセスの実行状態に応じてスピンロック型あるい
   はセマフォ型に切り替えることを特徴とする共有資源相
   互排除方式。
2. 【請求項２】　　「きわどい部分」の実行権を得るため
   に待機するプロセスが、「きわどい部分」の実行権を有
   するプロセスのプロセス制御ブロックを自アドレス空間
   内にマッピングして、その実行状態を調べることを特徴
   とする請求項１記載の共有資源相互排除方式。
3. 【請求項３】　　相互排除を行うプロセスのプログラム
   の誤りを検出し、誤りを起こしたプロセスに例外処理を
   実行せしめることを特徴とする請求項１もしくは２記載
   の共有資源相互排除方式。