第3章

プロセッサ間の同期をソフトウェアで実現する

マルチプロセッサのためのアセンブリ命令

中森 章

マルチプロセッサ・システムを構築する際には，資源の排他制御をどのような手法で実現するのかが問題となる．近代的なプロセッサでは，排他制御を 1 命令で実現できるアセンブリ命令が用意されている．本稿では，これらのアセンブリ命令について解説する．
（編集部）

本稿では，マルチプロセッサ間で同期を取るために用意ウェア的にほかのプロセッサのアクセスを禁止します．

されたアセンブリ言語の命令について解説します．また，話が横にそれましたが，ソフトウェア的には，排他制御命令だけにとどまらず，その使い方を知ることにより，資のために，各共有資源に対して，1 対 1 に対応するロック源の排他制御を実現する方法などについても解説します．

変数を用意します．つまり，ハード・ディスクには変数A，ディスプレイには変数 B，プリンタには変数 C といっ

1．マルチプロセッサ・システムにおける排他制御た具合です．ここで，ロック変数が 0 の場合はそれに対応する資源が未使用，0 でない場合はそれに対する資源が使用中であることを示すものとします．プロセスは早い者勝

マルチプロセッサ・システムを構築する上では，いかにちで，0 以外の値をロック変数に書き込むことで，その資して排他制御を行うかが問題となります．純粋にソフト源を使用する権利を得ます．例えばプリンタを使用したいウェアだけで排他制御を行うことも可能ですが，ハード場合，変数 C が 0 なら誰も使用していないので使用可能，ウェアによる支援があると，高速な排他制御（1 クロック0 以外なら使用中なので待つ（またはあきらめる）といった〜数クロックで実行）が可能です．そして，現在のマルチ処理になります．

プロセッサ，マルチコア CPU のほとんどがハードウェア

初期の Linux では，共有資源ごとにロック変数を持つの的な排他制御機構を持ち，そのためのアセンブリ命令を備ではなく，ただ一つのロック変数で排他制御を実現していえています．

たそうです．つまり，ロック変数にアクセスできたプロセ● 同期のためのソフトウェア処理

スはすべての共有資源がアクセスできるようになるのです．

マルチプロセッサ・システムにおいては，共有バスがメ

こういう単純な制御でもシステム的には破たんしない程度イン・メモリ（共有メモリ）にアクセスする唯一のアクセスの実行性能が得られる（昔は得られていた？）のでしょうね．

手段です．メモリの排他制御は，バスの使用権を獲得した● テスト・アンド・セットによる排他制御

プロセッサがメモリ・アクセスを独占し，ほかを閉め出せ排他制御を実現する最も単純な処理が「テスト・アンばいいのです．この処理は不可分（アトミック）なスワップド・セット」です．これは，ロック変数をリードし，その命令（データ交換命令）があれば簡単に実現できます．

値が 0 ならそこに 1（または 0 以外の値）を書き込みます．

不可分とは，あるプロセスがメモリにアクセスしている間ロック変数が 0 でなければ，書き込みは行いません．通常，にほかのプロセッサからのメモリ・アクセスがないことをいロック変数の前の値がリードの結果として返されるので，います．あるいは，ほかのプロセスがアクセスしようとしてそれが 0 ならロックが成功したことを示します．0 でなけもそれが禁止されている状態をいいます．実際には，（バス）ればロックは失敗したことになります（つまり，ほかのプロックという端子を活性化して外部回路に通知し，ハードロセスが使用中であることを意味する）．図 1 にテスト・Nov. 2007

KEYWORD ―― マルチプロセッサ，排他制御，アセンブリ命令，テスト・アンド・セット，コンペア・アンド・スワップ，フェッチ・アンド・アッド，ロード・リンクト，ストア・コンディショナル

73

アンド・セットを利用した相互排除を示します．ここで，セマフォとは，鉄道で用いられる腕木式信号機のことでロック変数が 0 になるのを待つループを「スピン・ウェイ

す．信号機が「進め」であれば資源が獲得できるし，「止まト」，または「ビジー・ウェイト」と呼びます．そのため，れ」であれば資源を獲得できません．セマフォの実体は一

この排他制御方式をスピン・ロック方式と呼びます．

種の共有フラグで，同期をとるプログラム同士がこのフラ● セマフォによる排他制御

グに注目し，フラグの変化に応じて処理を行って同期を実

スピン・ロック方式は，ほかのプロセスがクリティカ現します．構造化プログラミングの提唱者である Edsger

ル・セクション（共有資源を独占できる時間的・空間的領Wybe Dijkstra 氏はセマフォに対する P 操作，V 操作とい域）を実行しているとき，同じ資源を使おうとする別のプうものを定義しました．P 操作は事象の待ち合わせ，V 操ロセスがループしながら待つ点が非効率です．スピン・作は事象の発生（およびメッセージ）の通知を行います．セウェイトを行わない同期機構としてはセマフォがあります．

マフォを実現する操作は「フェッチ・アンド・アッド」と呼ばれます．これはメモリに対する任意の数（負の数も可）の加算を不可分に行う機能です．

開始

P 操作，V 操作の P，V という名称の由来は，Dijkstra氏の母国語であるオランダ語にあります．P は「proberen

ロック変数をリード（試みる）」と「verlagen（減じる）」の合成語である「prolagen」
スピン・ウェイト No
またはビジー・ウェイトが語源です．つまり，セマフォの値を減らす働きをします．

ロック解除？
ロック変数＝0？

V は「verhogen（増やす）」または「vrygeven（解放する）」がYes語源です．つまり，セマフォの値を増やします．由来を

ロック変数をリード＆ロックを試みる（0なら1に）No

テスト・アンド・セット

知っていれば，以下に説明する，それぞれの動作も理解しやすいと思います．
セマフォ i は，共有資源 i について定義され，負の値もロックは成功？
前状態＝0？

取るカウンタ Si と待ち行列 Qi から構成されます．これにYes

対する P 操作，V 操作の流れを図 2 に示します．簡単にいクリティカル・セレクションに入る

クリティカル・セレクションを出る

えば，P 操作で資源が得られない場合は，その P 操作を行ったプロセスは待機状態となって Qi に格納され，後で起動されるのを待ちます．これをサスペンド状態といいまロックを解除，ロック変数を0に

図1
スピン・ロック方式（相互排除）

す．V 操作は，待ち行列 Qi の中にプロセスがもしあれば，それを起動します．V 操作でプロセスを起動するのは OS終了の役割です．

P（i ）

V（im）

Si ←Si −1

Si ←Si ＋1
Yes

Si ＜0Yes

Si ≦0NoNoQ i からメッセージを取り出しを発行したプロセスに渡すP（i ）P（i ）を発行したプロセスをQ i に入れて待機状態にメッセージmをQ i に入れる

Q i からプロセスを取り出し，mを渡して実行状態に実行を続行

ディスパッチャへ実行を続行

ディスパッチャへ（a）資源 i に対するP操作（b）資源 i に対するV操作

図 2 P 操作と V 操作

74

New Products ―― Agilingua，カーナビに音声対話機能を付加するキットを発売
Agilingua 社は，カーナビに音声対話機能を付加するキット「アトムカーナビ SDK」を発売する．音声認識・操作と既存システムへの統合に必要なソフトウェアやサンプル・データベースが用意されている．タッチスクリーン入力に対応する．

Nov. 2007