並列プログラミング（その３）
4.Atomicなメモリ書き換え
その１で、単純なLoad/StoreについてのAtomicについて説明しました。 こんどは、Read-Modify-Writeについてについて考えます。
Read-Modify-Writeを複数のスレッドが実行する際、マルチプロセッサ環境で 同期を取るには、そのプロセッサのメモリモデルに沿った同期機構が必要です。 そのため、大抵のCPUには、AtomicなLoad&Store命令を持っています。LoadとStoreが Atomicであるということは、LoadしてからStoreするまでの間に他のプロセッサが LoadもStoreもできない（＝バスロックしている）ということです。
x86の命令の中で、もっともシンプルなAtomic Load&Store命令は、XCHG命令です。 この命令は２つのオペランドをAtomicに交換するのですが、オペランドにレジスタとメモリの ペアを指定すれば、メモリに対してAtomicなSwapを実行できます。
例えば、ロック変数を一つ用意して、それが0だったらだれもロックしていないので 1に書き換えてロック可能、1だったら誰かがロックしているので0になるのを待つ、 ということにします。XCHGを使った擬似コードは次のようになります。
inline int xchg(int i, int *mem) {
asm(" xchg i, (mem)");
return i;
}
void lock(int *lock_val) {
while (xchg(1, lock_val)) sleep(1);
}
void unlock(int *lock_val) {
xchg(0, lock_val);
}
ちなみに、pthreadのmutexなどでは、
- とりあえずxchg
- (SMPの場合)ロックが取れなかったらしばらくnopしてからxchg (=spin lock)
- それでもロックが取れなかったら、スレッドを待ち状態に移行させる
のようにな動作をしています。 ロックの取り合いが頻発しない限りはコンテキストスイッチなどが発生しないので、 実行コストは十分に小さいです。
ちなみに、x86のXCHGは同時にメモリバリアにもなっているので、このロックで同期を 行う場合はメモリバリアが不要になります。
xchgは上手に使えばいろいろ応用できます。例えばインクリメントカウンタであれば、 別のロック変数を用意しなくても次のように実装できます。
- カウンタを読み込む
- +1した値とカウンタ変数をxchgする
- xchgで読んだ値が、1.で読んだ値と同じなら、Atomicなインクリメント成功。違ったらやり直し
ただし、x86は命令がリッチなCISC型で、(1)演算命令のオペランドにメモリを指定でき、(2)演算命令にlockというprefixを つければ演算中にバスロックしてくれる、ので、リトライ無しのインクリメントカウンタをもっと簡単に実装できます
void safe_incl(int *mem) {
// lock prefix付きのincrement.
asm(" lock linc (mem);");
}
