-
- いいね！0
kumagi
@kumagi_bot
原始的なSTMのおはなし。STMは複数の箇所の書き換えをatomicに行えるが一体どうやってるのか、今の段階でうろ覚えしながら書きます。
2011-03-25 01:11:36
kumagi
@kumagi_bot
CASは1wordしか書き換えれないのになんでアトミックに複数箇所を書き換えれるのか、平たく言うとそれはオブジェクトそのものをCASで書き換えるのではなく、各スレッドの状態をCASで書き換えるから。
2011-03-25 01:13:33
kumagi
@kumagi_bot
どのようにしてそのような面妖な仕組みを生み出したかというとこれまたコンピュータ界の格言である「間接参照はすべての問題を解決する」そのものであり、STMにはその間接参照という魔法が2つもかけられている。
2011-03-25 01:14:41
kumagi
@kumagi_bot
一つのオブジェクトに対して「古いオブジェクト」「新しいオブジェクト」「持ち主が誰なのか」を保存しており、少なく見積もっても2倍のメモリを消費する。
2011-03-25 01:17:29
kumagi
@kumagi_bot
持ち主の状態は3通りあり「放置(commit)」「作業中だから触れるな(run?)」「不貞寝(abort)」のどれかの状態である。値を読み出すときは、commitなら「新しい値」run,abortなら「古い値」を対外的には読み出させる。
2011-03-25 01:20:32
kumagi
@kumagi_bot
commitする前には「書き換えたい全部のデータの所有者が自分」になっており、全部のデータは「新しいほうが自分の書き換えたいデータ、古いほうがもとのデータ」になっており、その状態から自スレッドの状態を run → commitにcasすることで複数箇所の見かけの情報が一息で変化。
2011-03-25 01:24:05
kumagi
@kumagi_bot
ここまでの説明で、腕っ節のある人なら実装はできるだろうけれど、このSTMがなんで原始的かというと、2回の間接参照というコストがあまりにも高いから。最近のSTMはロックベースであることは有名だけど、問題の本質はロックベースになった事ではなくて、間接参照を減らした事が一番の変化。
2011-03-25 01:29:34
kumagi
@kumagi_bot
STMの進化は僕の視点だと「間接参照という万能の錬金術をいかに薄めて目的を達成するか」に心血を注ぐ物であるので、間接参照の塊のような言語は簡潔に書けることを認めながらも、今ひとつ好きになれない。
2011-03-25 01:30:45
kumagi
@kumagi_bot
自分が特定のデータを書き換えようと思った際にそのデータを他のスレッドがrunのまま保持していた場合、トランザクションマネージャという神に信託を委ねる。トランザクションマネージャの実装は思想や研究に応じて様々なものが考えられるが、極端な話だと乱数でもトランザクションの性質は満たす。
2011-03-25 01:33:09
kumagi
@kumagi_bot
あ、read→readとwrite→readとでトランザクション中のデータの扱いは変わるんだった。今までの話は正確じゃないかも。基本的な考えはともかくとして。
2011-03-25 01:34:27
kumagi
@kumagi_bot
あ、トランザクションマネージャが走るとどちらかのスレッドの状態がabortedになるので、該当スレッドがrun→commitのCASを発行した時に失敗を検知して初めからやり直すことになる。各スレッドの状態変数はスレッド自身とトランザクションマネージャの2つが触りにくるのでCAS。
2011-03-25 01:40:07
kumagi
@kumagi_bot
STMはもう新手のデータ構造だと思ったほうがいい。しかも世代が変わるごとにbinary treeとhash mapぐらい実装の方針が大きく変わる。間接参照を削ろうとしてるんだから当たり前ではある。
2011-03-25 01:42:01
SKS rep
@repeatedly
これがよく分からない．古いオブジェクトと新しいオブジェクトはどこに保存していて，フィールドとかはどうなってるのん？ > 一つのオブジェクトに対して「古いオブジェクト」「新しいオブジェクト」「持ち主が誰なのか」を保存しており
2011-03-25 01:44:42
kumagi
@kumagi_bot
@repeatedly それぞれのオブジェクトはヒープの中に保存されてます。あるトランザクションが、他のスレッドによりcommitされた情報にアクセスする際には、「新しいオブジェクト」の所の物を「古いオブジェクト」の方から指すよう継ぎ換えた上で「新しいオブジェクト」の上で作業。
2011-03-25 01:50:06
SKS rep
@repeatedly
STMって何行くらいで書けるか．1万はいらんよなぁ．トランザクションマネージャとトランザクションコンテキストがメインか…
2011-03-25 01:48:21