Load LinkedとStore Conditional命令

しかし、各プロセサがキャッシュを持っている場合は、話が複雑になる。1つのやり方として、Load Linkedという命令とStore Conditionalというペアの命令を用いる方法がある。この場合は、まず、札メモリをLoad Linked命令で読む。この命令は、指定されたアドレスのデータをキャッシュに読み込み、引き続き、ハードウェアでそのキャシュラインが他のプロセサからアクセスされるかどうかを監視する。そして、プログラムは、読まれた値がゼロの場合は札メモリに対してStore Conditional命令を発行する。この間に、他のプロセサからの札メモリへのアクセスが無ければ、Store Conditional命令は成功し、オペランドで指定されたデータをキャッシュラインに書き込む。

一方、スヌープにより他のプロセサからのアクセスが検出された場合は、Store Conditional命令は失敗し、オペランドのデータは書き込まれない。また、Store Conditionalの成功、失敗は、命令の結果を示すレジスタに通知されるので、この値を見ることにより、プログラムは使用権の獲得の成功、失敗を知ることができる。

ハードウェアとしては、各キャッシュラインにLoad Linked命令で読まれたことを示す属性ビットを設ける。そして、Load Linkedで読まれたキャッシュラインのこのビットをセットし、このアドレスに他のプロセサからのスヌープが来ると、そのビットをリセットする。そして、Store Conditional命令を実行する際に、ビットがセットされたままであれば成功で、Storeを実行し、結果レジスタに成功を書き込む。一方、ビットがリセットされている場合は失敗であり、Storeを行わず、結果レジスタに失敗を書き込むというようにすれば良く、キャッシュコヒーレンス用のスヌープ機構に比較的簡単な追加を行うことで実現できる。

Test and Set命令

また、キャッシュをもつプロセサにTest and Set命令を設ける場合は、メモリを読み、その値がゼロである場合は、オペランドで指定された内容をメモリに書き込むという動作を、間に他のプロセサのメモリアクセスが入らないようにアトミックに実行する必要がある。キャッシュを持つプロセサの場合、Test and Set命令はストア命令と同様に札メモリをキャッシュに読み込み、書き込みのために、他のプロセサのキャッシュラインをスヌープして無効化する。そして、メモリから読まれた値をTest and Set命令の結果として返す。

さらに、通常のストア命令では無条件にキャッシュラインに書き込みを行うが、Test and Set命令の場合は、読まれたメモリのデータがゼロである場合はオペランド値を書き込み、非ゼロの場合は書き込みを行わないようにする。

Compare and Swap命令

図9.20のようなポインタで要素をつないだリスト構造は、プログラムで良く用いられるデータ構造である。この構造のData1とData2の要素の間にDataXを挿入する場合、まず、(1)でPtrXのリンク先をPtr2にして、(2)でPtr1のリンク先をPtrXに書き換えてやればよい。しかし、プロセサAがDataXを挿入しようとし、同時にプロセサBがDataYを同じ位置に挿入しようとしていると、一方の挿入は失敗してしまう。

図9.20 リスト構造への要素の挿入処理

セマフォ(札メモリ)を使って、このリスト構造へのアクセス権を制御しても良いが、この場合、まず、新しい要素を挿入するPtr1のリンク先アドレスを読み、挿入に必要な(1)の処理を行い、最後に再びPtr1を読んで、それが以前の値と一致している場合は他のプロセサが挿入を行っていないので、Ptr1のリンク先を挿入した要素のアドレスで置き換えるという操作をアトミックに行うことができれば、セマフォを使うより、ずっと効率よく処理を行うことができる。

このような操作を行うには、値がゼロかどうかを判定するTest and Set命令では不十分で、命令の第一オペランドの任意の値と比較を行い、一致した場合は、命令の第二オペランドの値をメモリに書き込むCompare and Swap(CAS)命令を設ける必要がある。

CAS命令を使う場合、まず、Ptr1を読み、(2)の処理を行ってから、CAS命令の第一オペランドに読んだPtr1の値、第二オペランドにPtrXのアドレスをセットして、Ptr1をアクセスする。最初の読み込みからCAS命令までの間に、別のプロセサが割り込んでPtr1を書き換えた場合は、二度目に読んだ値が一致しないので、その場合は、要素の追加は失敗である。

他のプロセサが割り込んでいない場合は、二度目に読んだポインタ値は一回目と同じであるので、挿入した要素へのポインタと置き換えられ、要素の追加が成功する。Test and Set命令は、札をひっくり返しクリティカルセクションを保護するのに用いられるが、このポインタの書き換えの例のように、処理によっては、CAS命令を使えば、特別にクリティカルセクションを作らなくても、複数のプロセサからアクセスされる構造をアトミックにアクセスすることができる。

以上述べたように、マルチプロセサで共用されるデータ構造に対しては、このような実質的にアトミックなメモリアクセスを行う命令が設けられており、これらの命令を使用することにより、安全に使用中の札をひっくり返すことができるようになっている。