miura1729の日記

module Transactionの仕様メモ

19:35 |

yarv2llvmの独自仕様でTransaction mixinを作ろうと思います。結構複雑な仕様になりそうなので、頭を整理するためにここに書いておきます。Transaction mixinはこれをincludeすることで、メソッド呼び出しをあたかも１つの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回、１円ずつ預けるのと引き出すのを別スレッドで行います。残高がマイナスになっても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