ロックのいろは

ロックと言うのはプログラミング上のコンベンション、慣用句みたいなもので、共有資源へのアクセスに対する同期のメカニズムとして利用される。

ある共有資源を複数のプロセッサ（あるいはプロセスでもいいけど）から同時に利用したいとする。変数に１を加えるという単純な動作ですら同期をとらないと正しい結果を得られない。

ロックはそのような同期を必要とする場面でよく利用される。ロックを取得したただ一つのプロセスのみその共有資源にアクセスできるようにするのである。

アトミックに値をセットしてテストする命令(test and set)を利用しロックが取得できるまでひたすらループして待つ、いわゆるスピンロックという単純素朴な方法がある。IA-32だとxchgという命令があって、あるメモリとレジスタの値をアトミックに（他のプロセッサに邪魔されることなく）行うことができて、それを利用する。例えば、0がロックされていない状態、１がロックされている状態とすると、下記のコードがそれをナイーブに実装したものである。

Spin_Lock:
Get_Lock:
    MOV EAX, 1;
    XCHG EAX, lockvar; // Try to get lock.
   CMP EAX, 0; // Test if successful.
   JNE Spin_Lock;
//
Critical_Section:
   
   MOV lockvar, 0; // Release lock.

lockvarとEAXレジスタの値を交換して、lockvarの値が0であったら誰もロックを取得していないので下に行く。誰かがロックを取得していたら1が入っているので、Spin_Lockにジャンプして繰り返す。ロックを取得できたら、共有資源にアクセスするなりなんなりをして最後にlockvarに0を代入しロックを解放する。そうすると同じロックを取得するために待っていた誰かがロックを獲得できるようになる。

上記の実装は間違いではないのだけど、実装上性能に多くの問題がある。毎回、xchg命令でメインメモリにアクセスに行くのだがアトミック性を保証するため、つまり値を交換しているとき、他の誰かが別の値に交換しないようにバスをロックし、単一のプロセッサだけが当該メモリにアクセスできるようにする。そうするとxchg命令実行中は他のプロセッサはバスがロックされているのでメインメモリにアクセスできない。プロセッサの数が増えれば増えるほどバスの競合が発生しスケールしない。またメモリアクセスは遅いでも書いたが、メモリアクセスはキャッシュアクセスに比べ100倍は遅いので毎回毎回のたのた動き回ることになる。まあ、スピンロックで持っているわけだから別に他に仕事がないので遅くてもいいっちゃいいのだが、先のバスロックはいただけない。

でもって、通常はどうするかと言うと、もう少しリラックスした方法になる。
先の実装のSpin_LockとGet_Lockの間に下記のコードを埋める。何をしているかというと、cmp命令でlockvarが0かどうか最初にチェックしている。つまり、ロックされているかチェックして、仮にロックされていなかったら、Get_Lockにジャンプしてロックの確保を試みる。

Spin_Lock:
   CMP lockvar, 0 ; // Check if lock is free.
   JE Get_lock
   PAUSE; // Short delay.
   JMP Spin_Lock;
Get_Lock:

cmp命令を実行してから、次のxchg命令まではアトミックではないので、他のプロセッサがその間にロックを取得してしまう可能性があるので、xchg命令で再度ロックが確保できるか確認している。cmp命令でlockvarを確認するのは、それがキャッシュに載っていればキャッシュアクセスなので高速に判定できる。ロックが取得できないときのループもキャッシュへのアクセスを延々と続けるので、メインメモリにアクセスしないので、他のプロセッサの邪魔をしないためスケーラビリティがある。メインメモリへのアクセスは他のプロセッサとの調停が必要なのでプロセッサの数が増えれば増えるほどコストが増大するので、できれば避けたいのある。

またスピンループ中にpause命令を入れているがこれはnopで、プロセッサに対しフルスピードでループしているけど他に有益な仕事があるんだったらそれを先にやってもいいよ、あるいは消費電力を落としてもいいよ、みたいなヒントになっている。IA-32の慣用句である。（蛇足）

スピンロックを実装するときに上記のように二重ループにするのはロックのいろはなのであるが、ユーザーランドで実装するときも注意したい。

また上記のようなアプローチはTest and Test-and-setとしても知られている。

上記の例はIntel 64 and IA-32 Architectures Optimization Reference Manualの8.4.2からの引用である。http://www.intel.com/products/processor/manuals/index.htm

メモリアクセスは遅い/ユメのチカラ
http://blog.miraclelinux.com/yume/2007/09/post_b3bc.html