Test and Set命令

メモリアクセスの排他制御

2つのプロセサが使用するメモリ領域が異なり、別々の仕事を分担する場合は問題ないのであるが、2つのプロセサで緊密に関係のあるデータを扱っている場合には問題が発生しうる。図9.19に示した預金引き出しの例では、残高と引き出し額を比較し、残高が十分にあれば残高から引き出し額を引き、引き出し額をATMから払い出す。

ここで、当初の残高が10万円の口座に対して、プロセサ1が8万円の引出し要求を受け付け、(1)で残高を読み処理を開始するが、それより一瞬遅れて、プロセサ2が同じ口座からの5万円の引出し要求を受け付けて(2)で残高を読むと、両方とも読み込んだ残高は10万円になってしまう。そしてプロセサ1が引出し処理を終わって(3)で残高に2万円と書き込むが、続いてプロセサ2が10万円-5万円＝5万円で、(4)で残高に5万円と書き込んでしまう。つまり、10万円の残高の口座から、合計13万円引き出したのに、残高が5万円も残るという問題がおきる。このようにほぼ同時に同じ口座にアクセスが来るという状況はATMの場合はありそうもないが、大規模なオンラインストアなどで、多数の問い合わせに対してそれぞれの品物の在庫を確認して納期回答し、注文を受けるような場合には発生しうる。

この問題は、残高を読み、残高から引き出し額を引き、更新した残高を書き戻すという一連の処理の間に、他のプロセサが割り込んでしまったために発生している。このような他のプロセサが割り込んでは困る部分をクリティカルセクションと呼び、正しく処理を行うためには、クリティカルセクションの実行中は他のプロセサが共通変数である残高を保持するメモリにアクセスしないようにすることが必要である。

このやり方であるが、要するに使用中という札を用いる。プロセサはクリティカルセクションの処理に入る前に、札が使用中になっているかどうかをチェックし、他のプロセサが使用中である場合は待ち、使用中が解除されると、自分が札を裏返して使用中にしてクリティカルセクションを実行する。そしてクリティカルセクションの実行を終わると、使用中の札を返して空きにする。このようにすれば同時に複数のプロセサがクリティカルセクションを実行して結果がおかしくなるという問題を避けることが出来る。

なお、この使用中の札であるが、鉄道の単線区間への列車の進入をコントロールする腕木式の信号機と同じであり、Semaphore(セマフォ)と名づけられているが、単線の腕木式信号を見たことが無い読者も多いと思うので、ここでは、使用中を示す札と呼ぶことにする。

しかし、ここで1つ問題がある。プロセサの世界では、一般には使用中の札もメモリで作ることになるが、プロセサ1が札のメモリアドレスへのロード命令を出し、続いてプロセサ2が同じメモリアドレスへのロード命令を出すと、両方のプロセサが使用中でないという状態を読んでしまい、やはり、上手く行かない。

このため、札のメモリアドレスへのアクセス用に特別なメモリアクセス命令を用意し、その命令を実行すると、メモリの内容を読み、その値がゼロであれば別の値をメモリに書き込むという一連の動作を他のプロセサのメモリアクセスを排除した状態で実行する。このように読み出し、比較、書き込みを不可分に行うということで、このようなメモリアクセスをアトミック(Atomic:原子が不可分の最小単位という意味の命名)なメモリアクセスと呼ぶ。

使用中で無い状態をゼロで表すと、あるプロセサが札メモリを読み、ゼロ(使用中でない)の場合は非ゼロの値を書き込んで使用中に札を返し、読まれた値がゼロの場合は自分がクリティカルセクションの実行権を得たことが分かる。

一方、読まれた値が非ゼロの場合は、メモリへの書き込みは行われず、読まれた値が非ゼロであることから、他のプロセサが使用中であり、クリティカルセクションの実行権を得られなかったことが分かる。

このようなメモリアクセス動作を行う命令をTest and Set命令と呼ぶ。

プロセサがキャッシュを持たず、複数のプロセサチップが共通のフロントサイドバスに接続されているコモンバス構造では、Test and Set命令の実現は容易である。最初はロード命令と同様に、普通にメモリの読み出しを行うが、メモリの読出しが終わってもコモンバスを開放せず、プロセサからの非ゼロの値の書き込みが終わるまで他のプロセサにコモンバスの使用権を与えないというようにすれば良い。