JPH0640324B2 - マルチプロセッサ・システムおよびそのプロセス同期方法 - Google Patents

Description

【発明の詳細な説明】 Ａ．産業上の利用分野 この発明はマルチプロセッサ・システムに関し、特に、
プロセッサ間の同期に伴うオーバーヘッドと無意味なス
ケジューリングを極力抑えて、システムの性能とプロセ
ッサ資源の使用効率を向上できるようにしたものであ
る。

Ｂ．従来技術 ＶＬＳＩ技術の大きな進歩により、多数のプロセッサを
搭載したマルチプロセッサ・システムが実現されるよう
になった。そして、複数のプロセッサを用いて仕事を高
速に処理する並列処理が重要になってきている。あるプ
ロセッサが他のプロセッサの処理結果を用いる際は、そ
の処理の完了を確認する動作つまり同期が必要である。
このように、複数のプロセッサが協調して処理を行うよ
うにするにはプロセッサ間の同期が不可欠である。

従来の同期の方法について説明する。

コンピュータシステムにおいて、現実のハードウェア資
源の管理はオペレーティングシステム（以下ＯＳとい
う）によって行われている。よって、ユーザーやプログ
ラマは実プロセッサを仮想化したプロセスという概念を
用いて処理を記述する。プロセスはＯＳの管理の下で実
プロセッサの割当てを受け処理を実行する。この割当て
をプロセススケジューリング（以下単にスケジューリン
グという）と呼び、一つのプロセスに対し一つの実プロ
セッサが割当てられる。並列処理では協調して動作する
複数のプロセスを用意して、プロセス間で同期を取りな
がら処理を進める。この同期の方法には一般には次の二
つの方法が用いられている。一つはＯＳを介して同期を
行う方法で、もう一つはプロセス間の共有メモリを介し
て同期を行う方法である。同期のためには同期を取り合
うプロセス間で同期情報を交換するための共有の実体が
必要になる。前者はその実体としてＯＳを後者はメモリ
を用いている。

次に従来の同期法における問題点について述べる。

ＯＳを介して同期を実行する場合は、同期が成立しなか
ったプロセスはプロセッサの割り当てを外され休止状態
になり、空いたプロセッサには他のプロセスが割付られ
る。よって、プロセッサ資源は効率的に使われる。しか
し、ＯＳを介しての同期はオーバーヘッドが大きく、こ
のため休止状態になったり、再びプロセッサに割付られ
たりということを繰返すと著しく効率が低減する。プロ
グラムの粒度（同期から次の同期までの間隔）が十分に
大きければ、このオーバーヘッドは無視できるが、通常
は無視できない。オーバーヘッドを少なくするためのＯ
Ｓを介しての同期ではなく共有メモリを介してのビジー
・ウェイトで同期を行うときにはこのような問題はなく
なるが、他の問題が生じる場合がある。前述のようにＯ
Ｓは一つの実プロセッサに一つのプロセスを割付ける。
このスケジューリング時に、複数の特定のプロセスを同
時に複数のプロセッサに割付るといった指定が通常でき
ない。そこで、ある並列処理のために複数のプロセスを
生成し、それらがお互に同期しながら動くようなプログ
ラムを考える。スケジューリングの都合で、そのプロセ
ス群の内のいくつかはプロセッサの割当てを受け、残り
はプロセッサの割当て待ちの状態になっているとする
と、同期を取るべき時に相手のプロセスがプロセッサに
スケジューリングされておらず、同期がすぐには成立さ
せられずプロセッサが無駄なビジー・ウェイトを行うと
いった事態が起こる。つまり、第１図のようにプロセス
がプロセッサに割当てられており、Ａ１、Ａ２、Ａ３の
プロセスがＡ４のプロセスの処理結果を使うためにビジ
ー・ウェイトの同期でループしているといった事態であ
る。この場合、ＣＰＵ時間は消費するが、タイム・スラ
イスか何かで再スケジューリングが起こって、Ａ４のプ
ロセスが実プロセッサに割当てられるまで、プログラム
は何も進展しない。また、共有メモリを介してのビジー
・ウェイトで複数のプロセスが同時に一点で待ち合わせ
を行うバリア同期を行うと、スケジューリングの問題の
他にも、マルチプロセッサ上で同期のための排他的メモ
リ・アクセスが集中して、データ通信路の競合等のオー
バーヘッドを引き起こすといった問題もある。

上述からも示唆されるように、プロセスの同期とスケジ
ューリングは密接な関係を持っている。アプリケーショ
ンや特定の並列処理プログラムにおいては、スケジュー
リングを調節することによって効率を上げることができ
る。しかし、現状のＯＳでは総てのプロセスを同じアル
ゴリズムに基づいてスケジューリングを行っているので
アプリケーション毎のスケジューリングの調節といった
ことができない。

なおこの発明に関連する先行技術の文献としてはつぎの
ものがある。

（１）“Stellix：UNIX for a Graphics Supercompute
r",Proceedings of the Summer 1988 USENIX Conferenc
e,June 20-24,1988,San frascisco California USA,USE
NIX Association,pp321-330,Thomas J.Teixeira &Rober
t F.Gurwitz この文献には同期用の特別なインストラクション列によ
り同期をとるときに、すべてのプロセスが同期待ち状態
なら、フォールト信号をハードウェアが生成することを
開示している。しかしこの文献では共有メモリのプロセ
ッサ情報（後述のようにプロセッサへのプロセスの割り
当て、プロセスのグループ分けおよびプロセスの同期に
関する情報）を用いてプロセスが所定の条件をチェック
して自らが再スケジュール要求を行って効率のよいプロ
セス同期を実現できるようにすることについてはなんら
示唆していない。

（２）IBM Technical Disclosure Bulletin Vol.32 NO.
1 June 1989 pp260-262,“DEVICE THAT PROVIDES FOR C
ONTENTION-FREE BARRIER SYNCHRONIZATION IN A MULTIP
ROCESSOR" （３）IBM Technical Disclosure Bulletin Vol.31 NO.
11 Aprol 1989 pp382389,“LOW-COST DEVICE FOR CONTE
NTION-FREE BARRIER SYNCHRONIZATION" （２）、（３）の文献にはバリア同期を集中的にハード
ウェアで実行する構成が開示されているが、同期待ちに
対する工夫は示唆されていない。

（４）H.S.Stone High-Performance Computer Architec
ture,Addison-Wesley,Reading,Massachusetts,1987 この文献にはバリア同期に関する一般的解説がなされて
いる。

Ｃ．発明が解決しようとする問題点 この発明は以上の事情を考慮してなされたものであり、
プロセッサ間の同期に伴うオーバーヘッドと無意味なス
ケジューリングを極力抑えた高性能なマルチプロセッサ
・システムを提供することを目的としている。

Ｄ．問題を解決するための手段 この発明では、以上の目的を達成するために、オーバー
ヘッドを減らすため共有メモリを介しての同期を採用
し、システムのプロセッサ資源に関する情報（プロセッ
サへのプロセスの割り当て、プロセスのグループ分けお
よびプロセスの同期に関する情報）をユーザーからアク
セスできるようにしておき、ビジー・ウェイトの同期待
ちのループで同期変数のチェックだけではなく、プロセ
ッサ資源に関する情報もチェックし、そのチェックの結
果、同期が暫く成立しない状況と判断されるときはビジ
ー・ウェイト中のプロセスは自らプロセスの実行を中断
し、スケジューラに制御を移し、再スケジューリングを
行わせプロセッサへのプロセスの割当てを変更する。

またこの発明ではプロセッサ間の同期が複数のプロセッ
サが一斉に待ち合わせを行うバリア同期用に、プロセッ
サ毎に専用レジスタを設け、そのレジスタ間の情報を交
換する専用の通信路を用意して、バリア同期のオーバー
ヘッドを軽くする。

また、プロセッサ資源に関する情報をチェックするため
に生ずるオーバーヘッドを軽くするために支援ハードウ
ェアを設け、再スケジューリングの開始は割り込みで通
知されるようにしてもよい。

さらに再スケジューリングの際に最適なスケジューリン
グが行えるように、スケジューラのユーザーによるカス
タマイズを可能にしてもよい。また、これをＯＳの管理
下で可能にするためスケジューラを階層化してもよい。
すなわちアプリケーションを実行するために並列に動く
プロセス群はそのアプリケーションのためのユーザーの
スケジューラの直接の管理下に置かれる。さらに、再ス
ケジューリングを指示する割り込みのオーバーヘッドを
減らすためとユーザーのスケジューラが複数のプロセッ
サに対してなるべく小さなオーバーヘッドで非同期通信
を可能にするために、プロセッサの割り込みを階層化し
てその内の優先度の低いものはユーザーに解放された割
り込みとする。つまり、その割り込みがユーザーのプロ
グラムを実行中（ユーザー・モード中）に起こった場
合、ユーザーが予め設定した割り込みプログラムに制御
を移すだけでＯＳ（カーネル・モード）には制御を移さ
ないようにするのである。

Ｅ．実施例 以下、この発明の実施例について図面を参照して説明を
行う。

Ｅ．１．原理的な説明 Ｅ．１．１．発明の背景 同期処理を軽くすることを目的の一つとしているので、
共有メモリ等を介してのビジー・ウェイトで同期を行う
ことを前提にする（ＯＳを介してでは上述のとおりオー
バーヘッドが増大する）。この際、従来技術でも述べた
ように以下の二点が問題である。

（１）無駄に同期待ちを行うプロセスがプロセッサに割
り付けられて、プロセッサ資源を浪費する。

（２）バリア同期の際に、同期のための排他的メモリ・
アクセスが集中して、データ通信路が競合してオーバー
ヘッドを生じる。

まず、（１）の問題について述べて、解決の方針を示
す。ある処理を複数のプロセスが協調して実行している
場合（並列処理）を想定する。この処理の途中で一つの
プロセスを除いて他のプロセスは同期待ちになったとす
る。例えばその同期待ちでないプロセスが計算結果を出
すのを今後その値が必要となるので他のプロセスすべて
が待っているといった状況である。また、プロセスの数
がプロセッサ数よりも多く、すべてのプロセスをプロセ
ッサに同時に割り付けることはできないとする。この状
況で、共有メモリを介しての同期を行っているので、Ｏ
Ｓはプロセスが同期待ちであるかどうか区別できない。
そのため、スケジューリングの結果、同期待ちのプロセ
スばかりがプロセッサに割り付けられて、同期待ちでな
い本来最優先のプロセスが実行待ちになってしまう可能
性がある。この場合、一定時間毎のタイマ割り込み時の
再スケジューリングの機会に同期待ちでないプロセスが
プロセッサに割り付けられるまで、プロセッサ資源を無
駄に浪費し続けることになる。この浪費を回避するため
には、プロセッサに同期待ちのプロセスばかりが割り当
てられていることが認識できなければならない。そこ
で、ビジー・ウェイトの同期待ちのループでは同期変数
のチェックだけではなく、同期待ちの場合はシステムの
プロセッサ資源に関する情報もチェックする。そのチェ
ックの結果、状況によってはプロセスを中断し、ＯＳに
制御を移し、再スケジューリングを実行しプロセッサへ
のプロセスの割り当てを変更する。この方式により無駄
に同期待ちを行うプロセッサを減らすことができ、シス
テムのプロセッサ資源を有効に使えるようになる。状況
判断の方法と利用するデータについてはＥ．１．２．節
で述べる。再スケジューリングの方法についてはＥ．
１．３．節で述べる。

次に、（２）のバリア同期における排他的メモリ・アク
セスの集中の問題について解説し、その解決の方針を示
す。一つの同期変数を用いたＮ台のプロセッサによるバ
リア同期の場合、少なくともＮ回の同期変数への排他的
な操作が必要である。この部分のメモリ処理は直列化さ
れるのでＮが大きくなるとオーバーヘッドも増大する。
特に、バリア同期を取るプロセス間の粒度が揃ってお
り、それらのプロセスが総て同時にプロセッサに割り当
てられている（つまり、プロセッサの割当て待ちのプロ
セスがいない）状況で、このオーバーヘッドが問題とな
る。このオーバーヘッドを避けるためにバリア同期専用
の同期変数を専用レジスタ（本発明ではフラグ）として
プロセッサ毎に設け、レジスタ間の値の更新は同期情報
のための専用通信路（本発明ではブロード・キャスト型
の信号線）で行うことにする。この機構により通常のデ
ータ通信路の通信量を増やすことなしにバリア同期が行
える。当然、プロセッサへの割当てを待っているプロセ
スが存在する時には、（１）の問題の解決方針に基づい
た動作を行う。具体的な機構についてはＥ．２．節の中
で述べる。

Ｅ．１．２．プロセス切り換えの状況判断と状況の検出
法 プロセスが同期待ち時にプロセッサの割当てを自ら放棄
する条件とその状況判断に必要になるシステムのプロセ
ッサ資源に関する情報について述べる。ここで、プロセ
ッサ資源を有効に管理するためにプロセッサのグループ
という考え方を導入する。基本的にはプロセスのうち共
有メモリを介した同期を行うもの同士を一つのグループ
とする。つまり、グループが異なれば、共有メモリを介
したビジー・ウェイトの同期を行わない。プロセッサは
自分の上で現在実行されているプロセスのグループに属
する。同じグループのプロセスが同時に割り付けられて
いるプロセッサ群がプロセッサのグループを形成する。
第１図ではＡ１、Ａ２、Ａ３、Ａ４がプロセスのグルー
プを形成しており、図のようなプロセッサの割当ての場
合はCPU1、CPU2、CPU3が一つのグループであり、CPU4は別
のグループである。ＵＮＩＸ（米国ＡＴ＆Ｔ社の商標）
系のＯＳの場合、PPID（親プロセス識別子）をこのグル
ープの識別子として流用できる。なお説明を補助する目
的で図を用いるが、今後の図中での記法を説明してお
く。プロセスＡ２ｗとあれば、最初のＡはグループ名を
次の２はグループ内でのプロセス名を最後のｗはそのプ
ロセスが同期待ちであることを示す。同期待ちでないプ
ロセスではｗの代りにｒが用いられる。図の左端で長方
形の破線で囲まれたプロセスは実プロセッサの割当てを
待っているプロセスである。

同期待ち時に、実行中のプロセスが自らプロセスを中断
し、プロセスの交代を要求する条件の例として以下のよ
うなものが挙げられる。

［１］自分と同じグループに属するプロセッサが総て同
期待ちになり、実行待ちのプロセスが存在する時（第２
図(a)参照）。

［２］自分と同じグループに属するプロセスが総て同時
にプロセッサに割り付けられており、それら総てが同期
待ちになった時。但し、これはプログラミング・エラー
（デッド・ロック）と考えられる（第３図参照）。

［３］バリア同期を行うプロセス群で一つのグループを
形成しており、自分がそのグループの一員の場合、自分
のグループに属する実行待ちかつ同期待ちでないプロセ
スが存在する時（第４図(a)参照）。

［４］自分と同じグループに属する同期待ちのプロセッ
サの数がｎを越え、実行待ちのプロセスが存在する時。
但し、ｎはＯＳまたはユーザーによって設定された値で
ある。

［５］自分と同じグループに属する同期待ちのプロセッ
サの数がｎを越え、実行待ちの自分と同じグループのプ
ロセスが存在する時（第５図(a)参照）。

［１］、［２］、［３］の条件はプロセスを交代する方
が確実に効率が向上する条件で、［４］、［５］の条件
は発見法的で経験則からｎの値を決めて効率の向上を狙
うものである。処理しているアプリケーションによって
ｎの値を調節して効率を上げるべきである。［４］、
［５］の条件については、同期待ちの絶対数で判断する
のではなく、同じグループに属するプロセッサ数とその
内の同期待ちの数の比率を基準にしてもよい。

これらの条件を満たすかどうかチェックするのに必要な
システムのプロセッサ資源に関する情報は、以下のよう
なものである。

#MGC (the number of My Group Cpus)： 自分のグループに属するプロセッサの数（グループに属
するプロセスの内のプロセッサに割り付けられているも
のの数） #MWC (the number of My group Waiting Cpus)： 自分のグループに属するプロセッサの内、同期待ちのプ
ロセッサの数 #MGP (the number of My Group Processes)： 自分のグループに属するプロセスの総数 #PRQ (the number of Processes in Run Queue)： 実行待ちのプロセスの数 #MPRQ (the number of My group Processes in Run Que
ue)： 自分のグループに属する実行待ちのプロセスの数 #MNWR (the number of My group Not Waiting processe
s in Run queue)： 自分のグループに属する実行待ちだが同期待ちでないプ
ロセスの数 TVPS (Threshold Value for Process Switch)： 上述のｎ これらの値がユーザーのプロセスから低コストで参照で
きる必要があり、共有メモリ上にカーネル（ＯＳ）側か
らもユーザー側からもアクセスできる変数として置かれ
る。アクセス権の保護に関しては、#MWCのみ同期を行う
ユーザーのアプリケーションのプロセスからも書き込み
可能で、他はスケジューラ側のみから書き込める。スケ
ジューラはこれらの値をスケジューリング毎に必要に応
じて更新する。

上記で述べたプロセス切り換えのための条件判断を含む
効率のよいビジー・ウェイト同期方式についてフローチ
ャートに沿って説明する。同期変数のチェックやプロセ
ス切り換えの条件判断の具体的な方法等は、待ち合わせ
を行うプロセスの数や同期の種類によって異なる。しか
し便宜上、ここでは第６図の一つのフローチャートで待
ち合わせ処理の内容を示し、細かい差には言及しない。
第７図は従来の待ち合わせのためのループを示す。最良
の条件、つまり同期変数を初めてチェックするまえに同
期が成立し同期変数に同期成立の値がセットされている
場合において、第６図の方式のオーバーヘッドを従来の
方式と同じに抑えるために処理の頭で同期変数のチェッ
クを一度行っている（Ｓ１）。同期完了であれば当然す
ぐに待ち合わせ処理を終了する。一回目の同期変数のチ
ェックで同期未了の場合に限り、プロセッサが同期待ち
状態に入り（Ｓ２）、これにより影響を受ける変数（#M
WC等）を更新する（Ｓ３）。そして、システムのプロセ
ッサ資源に関する情報を読出して（Ｓ４）、前出の条件
によってプロセスを中断しスケジューラによるプロセス
の再スケジューリングを要求するかどうか判断する（Ｓ
５）。条件が成立すれば、影響を受ける変数（#MWC等）
を更新し（Ｓ６）、プロセッサの制御権を放棄するシス
テム呼出し等を行ってスケジューラを呼び出す（Ｓ
７）。条件が成立しなければ、新たに同期変数のチェッ
クを行なう（Ｓ１１）。同期が成立していなければ、プ
ロセッサ資源に関する情報の読出しに戻って繰返す。同
期が成立していれば、プロセッサが同期待ち状態を抜
け、これにより影響を受ける変数（#MWC等）を更新し
（Ｓ１２）、待ち合わせの処理を終了する（Ｓ９）。制
御権を放棄して、再びプロセッサに割り付けられた時
は、プロセス切り換えの条件判断が非成立の場合のフロ
ーに合流する（Ｓ８、Ｓ１０）。

第６図で点線で囲まれた処理の部分は共有メモリへのア
クセスを不可分で排他的に行うべき部分（#MWCの更新）
を示す。つまり、共有バスのシステムではロックを掛け
てアクセスする部分を示す。以下の図でも同様である。

ハードウェア構成によっては共有変数へのアクセスの集
中の問題が存在する。それは同期待ちの処理の一番内側
のループでプロセッサ間で共有されるプロセッサ資源に
関する変数をアクセスしていることに起因する。内容の
コンシステンシを保つキャッシュ（スヌープ・キャッシ
ュ）等のハードウェアを持たないシステムでは頻繁にコ
ストの掛かる共有メモリへのアクセスが発生し、データ
通信路の通信の競合をまねく可能性がある。しかし、従
来の方法でも共有変数である同期変数へのアクセスを同
期待ちの処理の一番内側のループで行っているので事情
は同じである。よって、以下はシステムが内容のコンシ
ステンシを保つキャッシュ等のハードウェアを持ってい
ることを前提とする。

スヌープ・キャッシュ等を持ったシステムでは第８図の
ようにスピン・ロックを行えばオーバーヘッドを増やさ
ずに無駄なプロセス切り換えの要求を抑えられる。つま
り、第６図の方式では複数のプロセスで同時にプロセス
切り換えの条件が成立し、プロセス切り換え要求が集中
する可能性がある。そこで、第８図のように実際にプロ
セス切り換えを要求する部分をクリティカル領域として
排他制御することにより、その要求の集中を防いでい
る。ただし、ビジー・ウェイトの最内側ループにクリテ
ィカル領域の排他制御のための共有メモリへの排他アク
セス（バス・ロック等）が入ると、共有メモリへのアク
セスが集中してオーバーヘッドが大きくなる。そこで、
最内側ループではクリティカル領域とせずにプロセス切
り換えの条件判断を行ない、条件が成立したときに限
り、クリティカル領域に入り条件判断をし直す（スピン
・ロック、Ｓ４′、Ｓ５′）。なお、第８図の方式の場
合、スケジューラがプロセスを切り換えてシステムのプ
ロセッサ資源に関する変数を更新する際も、アクセスは
排他制御される。また第８図において第６図と対応する
個所には対応する符号を付して詳細な説明は省略する。

第６図に書かれている待ち状態フラグ(PWF：Process Wa
iting state Flag)と待ち状態カウンタ(PWC：Process W
aiting states Counter)はプロセス毎に設けられ、スケ
ジューラが#MNWRを計算するデータとなり、またスケジ
ューリングにヒントを与えることができる。詳しくは次
のＥ．１．３．節で述べる。

粒度が比較的小さいプログラムでは新しい方式のオーバ
ーヘッドが従来方式に比べて目立ってくる。例えば、数
十命令毎に同期を必要とするプロセス群があり、それら
が同時に総てプロセッサに割り当てられて実行されてい
る場合、同期待ち状態に入ったとしても同期はすぐ成立
するので同期待ちのループを１〜２回程度しか回らない
と考えられる。同期待ち状態でのループの繰返し毎の処
理量は第７図と第８図から比べても判るように、新しい
方式は従来に比べてかなり重たい。そのため、ループを
１〜２回しか回らない場合は、同期が成立した（同期変
数を誰かが書き替えた）時点から実際に成立を検出して
待ち合わせ処理を終了するまでのオーバーヘッドが目立
つようになる。そこで、プロセッサ外部からハードウェ
ア的にプロセッサが同期待ち状態にいるかどうか検知で
きる機構を用意して、同期待ち状態のプロセスを切り換
えるべきかどうかのチェックを専用ハードウェアに行わ
せ、割り込みで条件成立を通知すれば、プロセッサは第
９図のような待ち合わせ処理で済む。これにより前出の
場合でも従来方式と遜色がなくなる。

Ｅ．１．３．再スケジューリングの改善 第２図に条件［１］が成立した場合、第４図に条件
［３］が成立した場合、第５図に条件［５］が成立した
場合の再スケジューリングの進行の例を図示してある。
プロセッサの割当て待ちのプロセスが複数ある場合、ど
のプロセスをプロセス切り換え時にプロセッサに割り付
けるかが効率上問題である。また、第３図ではグループ
Ａはデッド・ロックを起こしているので、再スケジュー
リングでＡのグループのプロセスの実行をすべて止める
べきである。ここではスケジューラがどのように再スケ
ジューリングを実行すべきかについて述べる。また、プ
ロセッサ台数以上のプロセスで並列処理を行う場合は必
ず再スケジューリングが起こり、プロセスの粒度が細か
いときにはその頻度が非常に大きい。そこで、そのよう
な並列処理にも対応できるように再スケジューリングの
オーバーヘッドを極力削減する必要がある。オーバーヘ
ッドの少ない階層化されたスケジューラについても述べ
る。

前出の待ち状態フラグ(PWF)と待ち状態カウンタ(PWC)は
スケジューラが#MNWRを計算するデータとなり、またス
ケジューリングにヒントを与える。共に初期値は“Ｏ”
で、PWFはプロセスが同期待ち状態にあることを“１”
で示し、PWCは同期待ち状態になった回数を示す。PWF、P
WCによりスケジューラはプロセスが同じ同期待ち状態に
いるかどうか知ることができる。これにより、条件
［２］が成立していなくても、デッド・ロックが検出で
きる場合がある。あるグループのプロセス総てが同期待
ち状態の時、さらに総てのプロセスを１回ずつプロセッ
サに割り付けた後も、総てのプロセスが前と同じ同期待
ち状態にあるとすれば、それはデッド・ロックを意味し
処理を中止すべきである。また、同期待ち状態にないプ
ロセスに優先権を与えるというスケジューリング法が採
用できる。バリア同期では、バリア同期専用のPWCB(Pro
sess Waiting Counter for Barrier)を設ける。但し、
これはPWCとは異なり待ち合わせ処理を行った回数を示
す。つまり、第６図の頭の同期変数チェックの前に更新
する。同じグループ内のプロセスが全員でバリア同期を
行う場合は、同期毎にPWCBの値が揃うので、次にスケジ
ューリングすべきプロセスが判る。ただし、第４図(c)、
(d)のようにプロセッサの割当て待ちでかつ同期待ちの
プロセスは同期の成立時に同期待ちではなくなる。そこ
で、同期成立時に#MNWRを更新する必要がある。

この他にも、アプリケーションによっては同期を取り合
う頻度の高いプロセスの組み合わせといったことに関す
る情報が事前に得られる。そういったアプリケーション
毎の情報に基づいてスケジューリングを行えば、より良
いスケジューリングが行える。

つぎにスケジューラの階層化について説明する。

通常スケジューリングはＯＳのカーネル内で行なわれ
る。よって、ユーザーのプロセスが再スケジューリング
を行ってもらうためにはカーネルへのシステム呼出しを
行う必要がある。しかし、ＯＳ側のスケジューラではユ
ーザーのアプリケーション毎の木目細かなスケジューリ
ングは不可能である。また、ＯＳのカーネルとユーザー
のプロセスが多くのデータを共有すると、それを通知し
あう手順が複雑になり、オーバーヘッドも増大する。さ
らに、システム呼出しそれ自身のオーバーヘッドがかな
り重たいので、軽くプロセスの切り換えを行うのは難し
い。そこで、スケジューラを階層化して、従来の実プロ
セッサを割り付けるためのスケジューラをカーネル・ス
ケジューラと呼び、その制御下にユーザー・スケジュー
ラを設ける（第１０図参照）。ユーザー・スケジューラ
は同一のアプリケーションを協調して処理するプロセス
・グループ毎に設けられ、スケジューリング方式はユー
ザーが処理に応じて決定できる。カーネル・スケジュー
ラは実プロセッサ全体の管理を行ない、プロセス・グル
ープ毎にまとめて実プロセッサを割り付ける。ユーザー
・スケジューラはグループに割当てられたプロセッサ内
でのスケジューリングを実行する。また、ユーザー・ス
ケジューラはカーネル側（カーネル・モード）ではなく
ユーザー側（ユーザー・モード）で走る。そこで、プロ
セス切り換えの際、システム呼出し等のオーバーヘッド
がなく、効率が向上する。

プロセス切り換えの条件が成立した場合、ユーザー・ス
ケジューラに制御を渡し、そのプロセス・グループに適
したスケジューリング・アルゴリズムで次に割当てるべ
きプロセスを選び、そのプロセスに制御を渡す。これに
より、システム呼出しのオーバーヘッドなしにプロセス
をグループ内で切り換える。第１１図はグループＡが条
件［３］でユーザー・スケジューラ使ってプロセス切り
換えを行う例を示している。

カーネル・スケジューラは各プロセス・グループからプ
ロセッサの要求台数を受け取り、なるべく要求を満たす
ようにスケジューリングを行う。カーネル・スケジュー
ラはタイム・シェアリングのためのタイマ割り込み時ま
たは周辺装置の入出力を伴うシステム呼出し時またはユ
ーザー・スケジューラからのプロセッサ資源の追加要求
・返還時に起動する。カーネル・スケジューラによるス
ケジューリングの結果、空きプロセッサが必要になった
場合は優先度の低いプロセス・グループのプロセッサを
取り上げる（プリエンプトする）。

同期におけるプロセス切り換えの条件判断をハードウェ
ア化して、割り込みで条件成立をプロセッサに通知する
場合、この割り込みでユーザー・スケジューラが起動す
るようにしておく。実行モードにカーネル側とユーザー
側の区別があるプロセッサでは割り込み後はカーネル側
に制御が切り替わる。このような従来型のプロセッサを
使う時は、この割り込み時にはなるべくオーバーヘッド
なしにユーザー側に制御を返す必要がある。この点に関
し、積極的に以下のように割り込み機能を階層化したプ
ロセッサを用意すれば、オーバーヘッドの少ないユーザ
ー・モード内の割り込みが行える。優先度の違う外部割
り込みをプロセッサに用意し、優先度の低い外部割り込
みの内のいくつかにユーザー・モードの割り込みを設け
る。つまり、割り込みが発生したらユーザーが設定した
ルーチンにユーザー・モード内で制御を移す。残りの外
部割り込みは従来通りカーネル・モードへの割り込みで
ある。また、ユーザー・モードの割り込みは割り込みの
マスクの切り換え（割り込み許可・不許可の切り換え）
でユーザー側で自由にできる。このユーザー・モードの
割り込みを同期機構からの割り込みや同じグループ内の
プロセッサへの非同期の通信に使うと、カーネルに制御
が移行しないのでオーバーヘッドを減らすことができ
る。同期機構からの割り込みでは直接ユーザー・スケジ
ューラに制御が移るようにしておく。

Ｅ．２．具体的構成例 つぎに同期機構の具体的構成例について述べる。なおビ
ジー・ウェイトの処理のオーバーヘッドを減らすため、
プロセス切り換えの条件判断はハードウェアで行う。ス
ケジューラはＥ．１．３．節に従って階層化されたもの
がソフトウェアで実現されているとする。ここでは主に
同期機構のハードウェア側とこれを用いるビジー・ウェ
イトの処理について述べる。

第１２図に全体構成を示す。この図においてデータ通信
路は共有バス１とした。プロセッサＣＰＵ１、ＣＰＵ
２、・・ＣＰＵｎ毎に同期コントローラＳＣ１、ＣＳ
２、・・ＳＣｎが設けられ、同期コントローラ間はプロ
セッサ台数分の信号線を持つ同期信号バス（ブロード・
キャスト型の信号線）２で結合されている。各プロセッ
サと同期コントローラの間はコントローラ内のレジスタ
やフラグを読み書きするためのデータ線とコントローラ
からプロセッサへの割り込み線（前出のユーザー・モー
ドの割り込み）で結合している。

第１３図に同期コントローラＳＣ１の構成を示す。なお
他の同期コントローラの構成も同様である。この図にお
いて同期コントローラＳＣ１、ＳＣ２、・・ＳＣｎ毎に
同期信号バス上の特定の一本の信号線が割り当てられて
おり、その信号線に対してのみ信号（“０”か“１”の
２値）を出力できる。この出力はコントローラ内の同期
待ち出力フラグ(SOF)またはバリア同期用同期待ち出力
フラグ(BSOF)に対応しており、SOF（またはBSOF）がセ
ットされると信号線に“１”が出力され、SOF(BSOF)が
リセットされると“０”が出力される。初期状態として
SWF、BSWFはリセットされており、プロセッサが共有メモ
リ４を介しての同期待ちのループに入るまえにSOF(BSO
F)をセットし、ループを抜けるとリセットするようにプ
ログラミングする（第９図参照）。これにより、同期待
ち状態のプロセッサに対応する同期信号バスの信号線は
総て１になる。また、同期コントローラ内には各同期信
号線に各ビットが対応するグループ・レジスタ３があ
り、自分と同じグループに属するコントローラの対応す
るビットに“１”がスケジューラによってセットされて
いる。これにより、同期コントローラは自分の属するグ
ループのプロセッサが同期待ち状態にあるかどうか区別
できる。本同期コントローラは２つの動作モードを持っ
ており、モード１は（１）の問題に対応し、モード２は
（２）の問題とバリア同期における（１）の問題（条件
[3]）に対応している。同じグループ内では一時点には
どちらか一方のモードしか選択できないが、グループが
異なればモードは異なっても構わない。モードの切り換
えはコントローラ内のレジスタ(MODE)で行なわれる。

グループで共通なレジスタやフラグは共有バスを通して
同時に書き替えることができる。つまり、スケジューラ
が共有バスにグループを特定した同期コントローラへの
命令を出力でき、それによってグループ内のコントロー
ラのレジスタが書き替わる。同様にしてスケジューラは
自分が動作しているプロセッサ以外に接続しているコン
トローラのレジスタも変更できる。このようにスケジュ
ーラによって設定されるレジスタ類は第１３図ではグル
ープ・レジスタ３、MODE、UM、KM、PRQフラグ、TVPS1、
TVPS2、MPRQフラグ、MNWRフラグ、PCOUNTである。この
内UM、KMはユーザー・スケジューラとカーネル・スケジ
ューラのための割り込みマスクで、これが一方でもセッ
トされるとプロセッサへの割り込みが禁止される。ユー
ザー・スケジューラはUMだけを変更できる。当然、カー
ネル・スケジューラは総てのレジスタとフラグを変更で
きる。PRQフラグ、TVPS1、TVPS2、MPRQフラグ、MNWRフ
ラグはプロセッサ資源に関する情報を格納するレジスタ
類である。PRQフラグ、MPRQフラグ、MNWRフラグはそれ
ぞれＥ．１．２．節の#PQR、#MPRQ、#MNWRに対応してお
り、計数が０であればフラグはリセット、計数が０以外
ではフラグがセットされる。TVPS1、（またはTVPS2）は
条件［１］、［２］、［４］、［５］で#MWCの数と比較
すべき数を設定するためのレジスタである。例えば、条
件［１］、［２］の検出にはこれを#MGCに設定する。PC
OUNTはカーネルによるグループ内のプロセスのプリエン
プトの発生回数を計数するカウンタである。カーネル・
スケジューラがプリエンプトの際に１だけカウント・ア
ップを行ない、ユーザー・スケジューラがプリエンプト
に対する処理が済むとカウント・ダウンさせる。これに
より、プリエンプトの発生をコントローラが把握し誤動
作を防ぐ。

まず、モード１の動作をのべる。同期コントローラ内に
は前述のようにプロセッサ資源に関する情報を格納する
レジスタ類があり、スケジューラにより値がセットして
ある。#MWCについては同期コントローラが同期信号バス
を監視して常時把握している。システムの状態について
前出の［１］〜［５］条件のチェックをハードウェアで
行ない、条件を満たすとプロセッサに割り込み信号を出
力し、ＯＳによるプロセスの再スケジューリングを要求
する。

次に、モード２の動作について述べる。同期コントロー
ラ内に前出のレジスタやフラグの他に読出し専用のバリ
ア同期成立フラグ(BF)が存在する。但し、スケジューラ
からは副作用なしに読み書きが可能である。このBFフラ
グはMNWRフラグがリセット（“０”）で、PCOUNTが０
で、且つ自分の属するグループの総てのプロセッサが同
期待ち状態のときに“１”にセットされる。そして、こ
のフラグが値“１”としてプロセッサから読み出される
と、コントローラは以下の動作後BFフラグを自動的にリ
セットする。まず、自分の同期信号線とBSOFを“０”に
して、MPRQフラグが“０”でない場合コントローラ内の
MNWRフラグを“１”にセットする。この後、BFフラグを
リセットする。プログラムはこのBFフラグを使って待ち
合わせを行う。また、モード１ではBSOFをセットして同
期信号線を“１”にしているが、このモードではBSOFの
自動リセット同様にBFフラグの同期成立後最初の読出し
で自動的にセットできるのでビジー・ウェイト処理内で
セットする必要はない。同様に、PWCBのカウント・アッ
プも自動化できる。結局、待ち合わせの処理は第１４図
のフローチャートのようになる。スケジューラによるプ
ロセスの生成削除の際の誤動作を防ぐため以下のように
制御する。例えば、バリア同期に参加するプロセスの生
成時はコントローラ内のMNWRフラグに“１”を設定して
おき、割り込みは禁止しておく、そしてプロセスが総て
生成された後に正しいMNWRフラグを設定し、割り込みを
許可する。また、同期コントローラは［３］の条件のチ
ェックを行う。条件が成立するとプロセスを切り換えさ
せるためプロセッサに割り込みを発生させる。但し、PC
OUNTが０以外のときも#MNWRが０でない場合と同じに扱
い、誤動作を防ぐ。

同期コントローラ内のレジスタはプロセス切り換え発生
毎に適宜更新され、プロセス入替えられるプロセッサの
同期コントローラのSOF、BSOF、BF、MNWRフラグ（BFはスケ
ジューラからは自動セット・リセット等の副作用動作を
伴わずに読み書き出来る）等は入替え前の値が退避さ
れ、再びそのプロセスが割り付けられた際に、再設定さ
れる。

Ｆ．発明の効果 以上説明したようにこの発明によれば、マルチプロセッ
サ・システム上で同期を取りながら走るプロセスが同時
に実プロセッサに割り付けられている場合は非常に軽
く、プロセッサ資源の台数の制限とスケジューリングの
都合で同時に割り付けられない場合でも効率よくプロセ
ッサ資源を使える同期が実現できる。

【図面の簡単な説明】

第１図は従来のプロセスのプロセッサへの割当てを説明
する図、第２図ないし第５図はこの発明の一実施例で採
用する再スケジュール要求の条件を説明する図、第６図
は上述一実施例を説明するフローチャート、第７図は第
６図例に対応する従来の動作を説明するフローチャー
ト、第８図、第９図および第１０図は第６図例の変形例
を示す図、第１１図は第１０図変形例を説明する図、第
１２図および第１３図は第６図例の具体的な構成例を示
すブロック図、第１４図は第１３図を説明するフローチ
ャートである。 １……共有バス、２……同期信号バス、４……共有メモ
リ、ＣＰＵ……プロセッサ、ＳＣ……同期コントロー
ラ。

Claims (9)

【特許請求の範囲】
1. 【請求項１】複数のプロセッサおよび共有メモリを具備
   するマルチプロセッサ・システムにおいて各プロセスが
   同期待ち状態に進むときに、上記共有メモリに記憶され
   た同期変数をチェックし、同期が成立しているときには
   同期待ち状態を終了し、同期が未成立のときには同期待
   ち状態を継続するマルチプロセッサ・システムのプロセ
   ス同期方法において、 上記プロセスの各々が同期待ち状態に進むときに、さら
   に、 上記共有メモリに記憶されているプロセス同期に関連す
   る所定の情報をチェックし、同期の成立の可能性に関す
   る所定の条件が成立しているかどうかを判別するステッ
   プと、 上記条件が未成立であると判別されたときに同期待ち状
   態を継続するステップと、 上記条件が成立すると判別されたときに再スケジュール
   を要求するステップを実行することを特徴とするマルチ
   プロセッサ・システムのプロセス同期方法。
2. 【請求項２】複数のプロセッサでそれぞれ実行されてい
   るプロセスの間の同期を、共有メモリに記憶されている
   同期変数を上記プロセスの各々がチェックして実行する
   マルチプロセッサ・システムにおいて、 上記プロセッサの各々に、当該プロセッサで実行されて
   いるプロセスが同期待ち状態に進むときに、上記共有メ
   モリに記憶されているプロセス同期に関連する所定の情
   報をチェックし、同期の成立の可能性に関する所定の条
   件が成立しているときに再スケジュール要求を送出する
   手段を設け、さらに、 上記再スケジュールの要求に基づいてプロセスの再スケ
   ジュールを実行するスケジュール手段を有することを特
   徴とするマルチプロセッサ・システム。
3. 【請求項３】複数のプロセッサでそれぞれ実行されてい
   るプロセスの間の同期を共有メモリに記憶されている同
   期変数を各プロセスがチェックして実行するマルチプロ
   セッサ・システムにおいて、 上記プロセッサの各々に、 上記共有メモリに記憶されているプロセス同期に関連す
   る所定の情報を受け取って記憶する記憶手段と、 当該プロセッサで実行されているプロセスが同期待ち状
   態に進むときに、上記記憶手段に記憶されている上記情
   報をチェックし、同期の成立の可能性に関する所定の条
   件が成立しているときに再スケジュール要求を送出する
   手段とを設け、さらに、 上記再スケジュールの要求に基づいてプロセスの再スケ
   ジュールを実行する手段を有することを特徴とするマル
   チプロセッサ・システム。
4. 【請求項４】上記所定の情報はプロセスのプロセッサへ
   の割り当てに関する情報、プロセスのグループ分けに関
   する情報およびプロセスの同期に関する情報とした特許
   請求の範囲第２項または第３項記載のマルチプロセッサ
   ・システム。
5. 【請求項５】上記スケジュール手段はオペレーティング
   ・システムとは別個にアプリケーションごとに設けら
   れ、再スケジュールの要求時に制御をオペレーション・
   システムに移行させないようにした特許請求の範囲第３
   項記載のマルチプロセッサ・システム。
6. 【請求項６】上記再スケジュール要求を送出する手段
   は、対応するプロセッサに対して優先度の低い外部割り
   込み信号を送出し、この優先度の低い外部割り込み信号
   に基づいて、上記オペレーティング・システムとは別個
   にアプリケーションごとに設けられた対応するスケジュ
   ール手段が再スケジュールを実行し、より高い優先度の
   外部割り込み信号で上記オペレーティング・システムへ
   制御を移管するようにした特許請求の範囲第５項記載の
   マルチプロセッサ・システム。
7. 【請求項７】上記プロセッサはそれぞれプライベート・
   キャッシュを有し、それぞれのプライベート・キャッシ
   ュを介して共有メモリの内容をアクセスする特許請求の
   範囲第２項ないし第６項記載のマルチプロセッサ・シス
   テム。
8. 【請求項８】複数のプロセッサで実行されているプロセ
   スの間のバリア同期を実行するマルチプロセッサ・シス
   テムにおいて、 上記プロセッサの各々に、 上記共有メモリに記憶されているプロセス同期に関連す
   る所定の情報を受け取って記憶する第１の記憶手段と、 当該プロセッサとバリア同期される他のプロセッサを指
   定する第２の記憶手段と、 他のプロセッサの各々から同期待ちに関する信号を受け
   取る同期待ち状態信号受信手段と、 当該プロセッサで実行されているプロセスが同期待ち状
   態に進むときに、上記第１および第２の記憶手段に記憶
   されている情報および上記同期待ち状態信号受信手段の
   出力に基づいて、当該プロセッサとバリア同期される他
   のプロセッサの中に同期待ちでなく、かつ実行待ちであ
   るものがあり、そのままではバリア同期が成立しない場
   合であるかどうかを判別し、成立しないときは再スケジ
   ュール要求を送出する手段とを設け、さらに、 上記プロセッサの各々の同期待ち状態信号受信手段を相
   互に接続する同期信号バスと、 上記再スケジュールの要求に基づいてプロセスの再スケ
   ジュールを実行する手段を有することを特徴とするマル
   チプロセッサ・システム。
9. 【請求項９】複数のプロセッサでそれぞれ実行されてい
   るプロセスの間の同期を共有メモリに記憶されている同
   期変数を各プロセスがチェックして実行するマルチプロ
   セッサ・システムにおいて、 上記プロセッサの各々に、 上記共有メモリに記憶されているプロセス同期に関連す
   る所定の情報を受け取って記憶する第１の記憶手段と、 当該プロセッサとバリア同期される他のプロセッサを指
   定する第２の記憶手段と、 他のプロセッサの各々から同期待ちに関する信号を受け
   取る同期待ち状態信号受信手段と、 当該プロセッサで実行されているプロセスが同期待ち状
   態に進むときに、上記第１および第２の記憶手段に記憶
   されている情報および上記同期待ち状態信号受信手段の
   出力に基づいて、当該プロセッサとバリア同期される他
   のプロセッサの中に同期待ちでなく、かつ実行待ちであ
   るものがあり、そのままではバリア同期が成立しないと
   いう条件および他の同期の成立の可能性に関する所定の
   条件が成立しているときに再スケジュール要求を送出す
   る手段とを設け、さらに、 上記プロセッサの各々の同期待ち状態信号受信手段を相
   互に接続する同期信号バスと、 上記再スケジュールの要求に基づいてプロセスの再スケ
   ジュールを実行する手段を有することを特徴とするマル
   チプロセッサ・システム。