module Transactionの仕様メモ
yarv2llvmの独自仕様でTransaction mixinを作ろうと思います。結構複雑な仕様になりそうなので、頭を整理するためにここに書いておきます。Transaction mixinはこれをincludeすることで、メソッド呼び出しをあたかも1つのTransactionのように扱えるようになります。これを使うことで、STMやTime warpアルゴリズムが実現できるんじゃないかなと思います。
例えば、こんな感じで使うことを考えています。
class Bank include Tansaction def initilaize @balance = 0 end def deposit(how) begin_transaction @balance += how commit end def draw(how) begin_transaction @balance -= how if @balance < 0 then abort else commit end end
begin_transactionメソッドを実行すると、selfが持つインスタンス変数を別領域にコピーします。今後、commitまでインスタンス変数のアクセスはその別領域に対して行います。commitを実行するとオリジナルのインスタンス変数に別領域の結果を「アトミック」に戻します。戻した後、通常のインスタンス変数アクセスに戻ります。abortを実行すると、オリジナルのインスタンス変数に戻さずに通常のインスタンス変数アクセスに戻ります。
追記(2009/1/10)
commit時にオリジナルのインスタンス変数が書き換わっていた場合はbegin_transactionから再実行します。
インスタンス変数のアクセスを別領域に対するものにすりかえることは目処が立っています。今はcommitをアトミックに行う方法(lock-freeにできればしたい)を考えています。さらに、メソッドがcommitもabortしない場合どうするのか、トランザクションモード中で別のメソッドを呼んだ場合どうするのかとかもまだ決まっていません。
IOクラスなど副作用が本質的なクラスについては、メソッド呼び出しの履歴だけを記録しておいて、commit時にまとめて実行するTransaction対応版を用意するといいなと思います。
追記2(2009/1/11)
とりあえずbegin_transaction/commitを作ってみました。結局、アトミックなcommitはインスタンス変数が1つの時限定で、CAS命令を使いlock-freeで行っています。インスタンス変数が複数のときはまだ対応できませんが、lockを使うことを考えています。
サンプルプログラムbank.rbを示します。
# # bank simulator for test Transaction mixin # # class Bank include Transaction def initialize @balance = 0 end def deposit(how) begin_transaction @balance += how commit end def draw(how) begin_transaction @balance -= how commit end def balance @balance end end b = Bank.new a = 0 t = Thread.new do 100.times do puts sprintf "DEPOSIT START: %d", b.balance b.deposit(1) puts sprintf "DEPOSIT END: %d", b.balance end a = 1 end 100.times do puts sprintf "DRAW START: %d", b.balance b.draw(1) puts sprintf "DRAW END: %d", b.balance end while a == 0 Thread.pass end puts sprintf "END: %d", b.balance
100回、1円ずつ預けるのと引き出すのを別スレッドで行います。残高がマイナスになってもOKとしています。最終的な結果は0になるはずですが、0にならないこともあります。出力を見るとうまく動いていそうなので、途中でThreadがKillされているんじゃないかなと思います。joinをサポートしたいのですが、rb_thread_join_mがstaticなのでlinkできず困っています。ソースを書き換えれば楽勝ですが...。
追記3(2009/1/12)
ちゃんと残高が0になりました。やっぱり親スレッドが終了して子スレッドが道連れに強制終了してしまったことが原因です。joinはサポートできなかったですが、Thread.passをサポートしました。これを使って親スレッドが子スレッドをbusy waitするようにしたらうまく行きました。CPU無駄遣いしまくりですが。サンプルプログラムも正しく動く版に直してあります。
yarv2llvmの最新版
http://github.com/miura1729/yarv2llvm/tree/master
Transaction mixinの変更点
http://github.com/miura1729/yarv2llvm/commit/34dad3096799f2961b238a378f53e91dfdb513d5