JPH036654A - 相互排除方式 - Google Patents

Abstract

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

Description

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

（従来の技術） マルチプロセッサシステムにおける共有資源に対する相
互排除の基本方式として、スピンロック方式、および、
２値セマフォ方式がある。以下に各方式の構成と欠点を
述べる。

（ａ）スピン口・ジク方式 （ａ−１）スピンロック方式の構成 第１図は、スピンロック方式を用いた相互排除を行なう
システムの構成例である。プロセッサ１゜２および、主
記憶装置３は一つのシステムバス４に接続されている。

各プロセッサは、主記憶装置３に格納された任意のデー
タの読みだし、書き込み、および、任意のプログラムの
実行が可能である。図に示すように、主記憶装置３には
、鍵、きわどい部分、１ｏｃｋ操作、ｕｎ　１　ｏｃｋ
操作のプログラム等が格納される。きわどい部分とは、
一時には一つのプロセスしか実行することのできないプ
ログラムをさし、相互排除の対象である。

鍵の値は、１または０であり、「きわどい部分」の実行
権を所有するプロセスが存在しているか否かを示す。１
ｏｃｋ操作とｕｎｌｏｃｋ操作は、「きわどい部分」に
対する相互排除を行なうプログラムである。

第２図は、１　ｏｃｋ操作とｕｎ　１ｏｃｋ操作を用い
て相互排除を行なう操作手順である。複数のプロセスが
同時に１ｏｃｋ操作を実行した場合には、以下に述べる
１ｏｃｋ操作の機能により、ただ一つのプロセスが「き
わどい部分」を実行できる。このプロセスがｕｎｌｏｃ
ｋ操作を行なうまで、他のプロセスは「きわどい部分」
に入れずに空転して待つ。

第３図は、１ｏｃｋ操作の実現例である。１Ｏｃｋ操作
は、次の手順で行なわれる。

■鍵を読み出す。読み出した値をＸとする。次に鍵を１
にする。ここで、鍵に対する読み出し・書き込みはｔｅ
ｓ　ｔ−ａｎｄ−ｓｅｔ命令など、メモリの読み出しと
書き込みが細分化されない基本演算により行なわれる。

■ＸがＯの場合には、１ｏｃｋ操作を終了する。

そうでない場合には、■に行き空転する。

第４図は、ｕｎｌｏｃｋ操作の実現例である。

ｕｎｌｏｃｋ操作は、鍵に０を書き込む。ｕｎｉｏｃｋ
操作で鍵に０を書き込むと、上記１ｏｃｋ操作で空転し
ていたプロセスが０を鍵の値として読み出し、１ｏｃｋ
操作を終了して「きわどい部分」に入ることができるよ
うになる。

（ａ−２）スピンロック方式の欠点 プロセスが空転して鍵の状態を調べ、鍵がＯになるまで
待っているので、「きわどい部分」のプログラムに対し
て次のような制約が課せられる。

・短いプログラムであること ・割り込み禁止状態にするなどして、「きわどい部分」
の実行途中でプロセッサを取り上げられないようにする
こと。

・入出力など待ち状態になる操作は行なわないこと。

・誤りを起こして例外処理プログラムにプロセッサを取
り上げられないこと。

上記の制約のため、スピンロック方式は、ＯＳカーネル
など限られたプログラムの相互排除に用いられるのが一
般的であり、通常のユーザプログラムには適していない
という欠点があった。すなわち、ユーザプログラムでス
ピンロック方式を用いた場合には、次のような問題が生
じる。

■バグのため「きわどい部分」から出ないで割り込み禁
止状態を長時間作り出す可能性がある。

■１ｏｃｋ操作は「きわどい部分」の実行権を所有する
プロセスの状態変化を検出する機能を備えていない。こ
のため、「きわどい部分」の実行権を所有するプロセス
が待ち状態に入ったりプロセッサを取り上げられた場合
に、空転を続けるプロセスを実行するプロセッサは、そ
のまま空転を続けて多大に無駄な時間を費やす。

■１ｏｃｋ操作の使い方に関する簡単な誤りをおかすだ
けで容易にデッドロックに陥ってしまう。

しかし、１ｏｃｋ操作は、「きわどい部分」の実行権を
どのプロセスが所有しているか調べる機能を備えていな
いので、簡単なプログラム誤りが原因で「きわどい部分
」の実行権を決して得ることができないのに待っている
状態を検出し適切な処理を行なわせることができない。

■ユーザプロセスはプロセッサを取り上げられてもよい
状態でできる限り実行させたいというＯ８の一般的な目
標と相反する。

（ｂ）２値セマフォ方式 （ｂ−１）２値セマフォ方式の構成 第５図は、２値セマフォ方式を用いた相互排除を行なう
システムの構成例である。プロセッサ１゜２および、主
記憶装置３は一つのシステムバス４に接続されている。

各プロセッサは、主記憶装置３に格納された任意のデー
タの読みだし、書き込み、および、任意のプログラムの
実行が可能である。図に示すように、主記憶装置３には
、前記きわどい部分の他、セマフォＳ、セマフォＳの待
ちプロセス行列、プロセッサ待ちプロセス行列、Ｐ操作
、■操作、プロセス切り替えプログラムが格納される。

きわどい部分は、前述したように一時には一つのプロセ
スしか実行することのできないプログラムであり、相互
排除の対象である。セマフォＳは、０または１をとり、
それぞれ「きわどい部分」が使用中である、あるいは、
空いていることを表わす。セマフォＳの待ちプロセス行
列は、「きわどい部分」の使用が終わるのを待っている
プロセスを整列させたＯ８の制御データである。

プロセッサ待ち行列は、プロセッサを割り付けると直ち
に実行可能なプロセスを整列させたＯ８の制御データで
ある。Ｐ操作とＶ操作は、「きわどい部分」に対する相
互排除を行なうプログラムである。

第６図は、Ｐ操作とＶ操作を用いて相互排除を行なう操
作手順である。複数のプロセスが同時にＰ操作を実行し
た場合には、以下に述べるＰ操作の機能により、ただ一
つのプロセスが「きわどい部分」を実行できる。このプ
ロセスがＶ操作を行なうまで、他のプロセスはセマフォ
Ｓの待ちプロセス行列で待たされる。

第７図は、Ｐ操作の実現例である。Ｐ操作は、次の手順
で行なわれる。

■セマフォＳを読み出す。読み出した値をｏｌｄとする
。次にｏｌｄが１の場合には、Ｓを１減じて０にする。

ここで、セマフォに対する読み出しと書き込みはプロセ
スからは細分化されない基本演算として見えるものであ
る。

■ｏｌｄが１の場合には、Ｐ操作を終了する。そうでな
い場合には、Ｐ操作を実行中のプロセスをセマフォ待ち
プロセス行列の最後尾に加え、プロセス切り替えプログ
ラムに制御を移す。

第８図は、■操作の実現例である。■操作は、セマフォ
待ちプロセス行列が空か調べ、空ならばセマフォＳに１
を書き込み、操作を終了する。空でないならば、セマフ
ォＳの待ち行列から先頭のプロセスを取り出し、プロセ
ッサ待ちプロセス行列の先頭に入れ、操作を終了する。

適当な時間経過の後、プロセス切り替えプログラムが実
行されると、プロセッサ待ちプロセス行列からプロセス
が取り出され、Ｐ操作の終了時点から処理を再開して、
「きわどい部分」を実行する。

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

・Ｐ操作の度にプロセスをセマフォＳの待ちプロセス行
列に入れ、プロセス切り替えを行なつＯ ・Ｖ操作の度にセマフォＳの待ちプロセス行列からプロ
セッサ割り付は待ちプロセス行列にプロセスを移す。■
操作の後に、プロセス切り替えが発生する。

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

（発明が解決しようとする課題） 本発明において解決しようとする課題は、スピンロック
方式における「きわどい部分」のプログラムに課せられ
た制約が大きいのでユーザプログラムの相互排除に適さ
ないという欠点、および、２値セマフォ方式における相
互排除のためにプロセスが頻繁に切り替わることによる
オーバヘッドが大きいという欠点、および、両方式にお
いて相互排除手段が「きわどい部分」の実行権を所有す
るプロセスの状態を読み出す機能を備えていないので相
互排除に係わるプログラムの誤りを検出して処理するこ
とができないという欠点であり、これら欠点を解消し、
処理量の小さなユーザプロセスが頻繁に「きわどい部分
」を実行するシステムにおいて効率的な相互排除方式を
提供することが本発明の目的である。

〔発明の構成〕

（課題を解決するための手段） 本発明は、「きわどい部分」の実行権を所有するプロセ
スの実行状態を読み出す機能、および、実行権を新たに
得ることができない状態であることを検出する機能、お
よび、実行権を得るために待っているプロセスの実行を
制御する機能を相互排除手段に備えさせることにより、
「きわどい部分」の実行権を所有するプロセスの状態に
従って、その実行権を得るために待っているプロセスに
対して、プロセッサを割り付けたまま待たせる、あるい
は、プロセッサを取り上げる、あるいは、誤り処理を行
なわせるように実行を制御して相互排除することを最も
主要な特徴とする。

（作用） 前述した本発明の相互排除方式によれば、「きわどい部
分」の実行権を所有するプロセスの状態に従ってプロセ
スを待たせる方法を選択的に定め、プロセス切り替え、
および、誤り処理を選択的に行なうことになる。

（実施例） 以下、図面を使って本発明の一実施例を詳細に説明する
。

第９図は、本発明の一実施例のシステム構成図である。

プロセッサ１．２および、主記憶装置３は一つのシステ
ムバス４に接続されている。各プロセッサは、主記憶装
置３に格納された任意のデータの読みだし、書き込み、
および、任意のプログラムの実行が可能である。図に示
すように、主記憶装置３には、プロセス制御ブロック、
プロセッサ待ちプロセス行列、鍵、きわどい部分、入口
操作、出口操作、例外処理プログラム、プロセス切り替
えプログラムが格納される。

プロセス制御ブロック（ＰＣＢ）は、Ｏ８によりプロセ
スごとに作られる制御データであり、プロセスの実行状
態やプロセスへの資源の割り付は状況などが書き込まれ
る。プロセッサ待ちプロセス行列は、プロセッサを割り
付けると直ちに実行可能なプロセスのＰＣＢを整列させ
たＯ８の制御データである。鍵は、ＰＣＢアドレスとロ
ック変数からなる。ＰＣＢアドレスには、「きわどい部
分」の実行権を所有しているプロセスのＰＣＢの先頭ア
ドレス、または、０が格納されている。ロック変数は「
きわどい部分」の実行権を所有するプロセスが存在する
か否かを示す。きわどい部分は、一時には一つのプロセ
スしか実行することのできないプログラムであり、相互
排除の対象である。入口操作と出口操作は、「きわどい
部分」に対する相互排除を行なうプログラムである。例
外処理プログラムは、相互排除に関する誤りを処理する
プログラムであり、プロセス切り替えプログラムはプロ
セッサをプロセスに割り付けるプログラムである。

第１０図は、入口操作と出口操作を用いて相互排除を行
なう操作手順である。複数のプロセスが同時に人口操作
を実行した場合には、以下に述べる人口操作の機能によ
り、ただ一つのプロセスが「きわどい部分」を実行でき
る。このプロセスが出口操作を行なうまで、他のプロセ
スは「きわどい部分」に入ることができない。

第１１図は、入口操作の一実施例である。第１１図に従
って、入口操作の実現例を以下に詳細に述べる。鍵のＰ
ＣＢアドレスとロック変数の初期値を０とし、入口操作
を実行しているプロセスをプロセスＡとする。

■鍵のＰＣＢアドレスを読み出す。読み出した値をａと
する。ａがＯの場合には、■に行く。ａがプロセスＡ（
自プロセス）のＰＣＢの先頭アドレスの場合には、プロ
セスＡのプログラムに誤りがあり、「きわどい部分」の
実行権を新たに得ることができないことを意味するので
、例外処理プログラムに制御を移す。その他の場合には
、■に行く。

■鍵のロック変数を読み出す。読み出した値をＸとする
。次に鍵のロック変数を１にする。ここで、ロック変数
に対する読み出し・書き込みはｔｅｓｔ−ａｎｄ−ｓｅ
ｔ命令などにより不可分演算によりなされるものである
。Ｘが０の場合には、入口操作を実行中のプロセスのＰ
ＣＢの先頭アドレスを鍵のＰＣＢアドレスに書き込み、
入口操作を終了する。Ｘが０でない場合には、■に行く
。

■ａを先頭アドレスとするプロセス制御ブロックからプ
ロセスの状態フィールドＳを読み出す。プロセスが実行
中であることをＳの値が示している場合には、■に行く
。Ｓの値が、プロセスが終了していることを示している
場合には、「きわどい部分」の実行権は決して返されな
いことを意味するので、例外処理プログラムに制御を移
す。その他の場合には、プロセッサ待ちプロセス行列の
最後尾にプロセスＡのＰＣＢを入れ、プロセス切り替え
プログラムに制御を移す。

第１２図は、出口操作の一実現例である。出口操作では
、まず、鍵のＰＣＢアドレスを０にし、次に鍵のロック
変数を０にする。

〔発明の効果〕

以上説明したように、本発明は、「きわどい部分」の実
行権を所有するプロセスの実行状態を読み出す機能、お
よび、実行権を新たに得ることができない状態であるこ
とを検出する機能、および、実行権を得るために待って
いるプロセスの実行を制御する機能を相互排除手段に備
えさせているので、「きわどい部分」の実行権を所有す
るプロセスの状態に従って、その実行権を得るために待
っているプロセスに対して、プロセッサを割り付けたま
ま待たせる、あるいは、プロセッサを取り上げる、ある
いは、誤りを検出して例外処理を行なわせるように実行
を制御し、処理量の小さなユザプロセスが頻繁に「きわ
どい部分」を実行するシステムにおいて効率的な相互排
除の制御を実現することができる。

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

【図面の簡単な説明】

第１図から第４図は従来の相互排除技術であるスピンロ
ック方式に関する図面であり、第１図はスピンロック方
式の実施例のシステム構成図、第２図は１ｏｃｋ操作と
ｕｎｌｏｃｋ操作を用いて相互排除する操作手順のフロ
ーチャート、第３図は１ｏｃｋ操作の詳細手順のフロー
チャート、第４図はｕｎｌｏｃｋ操作の詳細手順のフロ
ーチャートである。 第５図から第８図は従来の相互排除技術である２値セマ
フォ方式に関する図面であり、第５図は２値セマフォ方
式の実施例のシステム構成図、第６図はＰ操作とＶ操作
を用いて相互排除する操作手順のフローチャート、第７
図はＰ操作の詳細手順のフローチャート、第８図はＶ操
作の詳細手順のフローチャートである。 第９図から第１２図は本発明の実施例に関する図面であ
り、第９図は本発明の一実施例のシステム構成図、第１
０図は本発明の相互排除手段である入口操作と出口操作
を用いて相互排除する操作手順のフローチャート、第１
１図は入口操作の詳細手順のフローチャート、第１２図
は出口操作の詳細手順のフローチャートである。

Claims (1)

【特許請求の範囲】
1. 異なるプロセッサ上で動作する複数のプロセスが資源を
   共有する手段と、一時にはただ一つのプロセスでしか使
   用できない部分（きわどい部分と呼ぶ）の実行を開始す
   る権利（実行権と呼ぶ）を相互に排除する手段とを有す
   るマルチプロセッサシステムにおいて、前記相互排除手
   段は、実行権を所有するプロセスの実行状態を読み出す
   機能と、実行権を新たに得ることができない状態である
   ことを検出する機能と、実行権を得るために待っている
   プロセスの実行を制御する機能とを有し、「きわどい部
   分」の実行権を持つプロセスの状態に従って、その実行
   権を得るために待っているプロセスに対して、プロセッ
   サを割り付けたまま待たせる、あるいは、プロセッサを
   取り上げる、あるいは、誤り処理を行なわせるように実
   行を制御することを特徴とした相互排除方式。