トランザクションの検証が面倒すぎる。モデルとしては単純そうだから、作ってしまおう、と思った。

Ruby

tran_request.rb

class Request
end

class Read < Request
    attr_reader :var
    def initialize(var)
        @var = var
    end

    def to_s()
        return "Read(#{@var})"
    end
end

class Write < Request
    attr_reader :var,:val
    def initialize(var,val)
        @var = var
        @val = val
    end

    def to_s()
        return "Write(#{@var},#{@val})"
    end
end

class Insert < Request
    attr_reader :var, :val
    def initialize(var,val)
        @var = var
        @val = val
    end

    def to_s()
        return "Insert(#{@var},#{@val})"
    end
end

class Delete < Request
    attr_reader :var
    def initialize(var)
        @var = var
    end

    def to_s()
        return "Delete(#{@var})"
    end
end

class Lock < Request
    attr_reader :tr,:var,:lock_type
    def initialize(tr,var,lock_type)
        @tr = tr
        @var = var
        @lock_type = lock_type
    end

    def to_s()
        return "Lock(#{@tr},#{@var},#{@lock_type})"
    end
end

class Unlock < Request
    attr_reader :tr,:var
    def initialize(tr,var)
        @tr = tr
        @var = var
    end

    def to_s()
        return "Unlock(#{@tr},#{@var})"
    end
end

class Begin < Request
    def to_s()
        return "Begin"
    end
end

class Rollback < Request
    def to_s()
        return "Rollback"
    end
end

class Commit < Request
    def to_s()
        return "Commit"
    end
end

class Database
    attr_accessor :vars , :locks
    def initialize()
        @vars = {}
        @locks = []
    end

    def read(tr,var)
        if @locks.filter{|l| l.tr != tr && l.var == var && l.lock_type == :Exclusive}.empty? then
            return :success , @vars[var]
        else
            return :failure , nil
        end
    end

    def write(tr,var,val)
        if @locks.filter{|l| l.tr != tr && l.var == var}.empty? then
            @vars[var] = val
            return :success
        else
            return :failure
        end
    end

    def insert(tr,var,val)
        write(tr,var,val)
    end

    def delete(tr,var)
        if @locks.filter{|l| l.tr != tr && l.var == var}.empty? then
            unlock(tr,var)
            @vars.delete(var)
            return :success
        else
            return :failure
        end
    end

    def lock(tr,var,lock_type)
        if lock_type == :Exclusive then
            if @locks.filter{|l| l.tr != tr && l.var == var}.empty? then
                @locks << Lock.new(tr,var,lock_type)
                return :success
            end
            return :failure
        else
            if @locks.filter{|l| l.tr != tr && l.var == var && l.lock_type == :Exclusive}.empty? then
                @locks << Lock.new(tr,var,lock_type)
                return :success
            end
            return :failure
        end
    end

    def unlock(tr,var)
        @locks.filter!{|l| !(l.tr == tr && l.var == var)}
        return :success
    end

    def unlock_all(tr)
        @locks.filter!{|l| l.tr != tr}
        return :success
    end

    def begin(tr)
        unlock_all(tr)
        return :success
    end

    def rollback(tr)
        unlock_all(tr)
        return :success
    end

    def commit(tr)
        unlock_all(tr)
        return :success
    end
end

class Transaction
    attr_reader :db,:name,:requests,:counter,:vars,:status
    def initialize(db,name,requests)
        @db = db
        @name = name
        @requests = requests
        @counter = 0
        @vars = {}
        @status = :running # :running or :waiting
    end

    def next()
        req = @requests[@counter]
        if req.is_a?(Read) then
            status, value = @db.read(@name, req.var)
            if status == :success then
                @vars[req.var] = value
                @status = :running
                @counter += 1
                puts "#{@name} Read(#{req.var}) => #{value}"
            else
                @status = :waiting
                puts "#{@name} Read(#{req.var}) => fail"
            end
        elsif req.is_a?(Write) then
            status = @db.write(@name, req.var, req.val)
            if status == :success then
                @status = :running
                @counter += 1
                puts "#{@name} Write(#{req.var},#{req.val}) => success"
            else
                @status = :waiting
                puts "#{@name} Write(#{req.var},#{req.val}) => fail"
            end
        elsif req.is_a?(Insert) then
            status = @db.insert(@name, req.var, req.val)
            if status == :success then
                @status = :running
                @counter += 1
                puts "#{@name} Insert(#{req.var},#{req.val}) => success"
            else
                @status = :waiting
                puts "#{@name} Write(#{req.var},#{req.val}) => fail"
            end
        elsif req.is_a?(Delete) then
            status = @db.delete(@name, req.var)
            if status == :success then
                @status = :running
                @counter += 1
                puts "#{@name} Delete(#{req.var}) => success"
            else
                @status = :waiting
                puts "#{@name} Delete(#{req.var}) => fail"
            end
        elsif req.is_a?(Lock) then
            status = @db.lock(@name, req.var,req.lock_type)
            if status == :success then
                @status = :running
                @counter += 1
                puts "#{@name} Lock(#{req.var},#{req.lock_type}) => success"
            else
                @status = :waiting
                puts "#{@name} Lock(#{req.var},#{req.lock_type}) => fail"
            end
        elsif req.is_a?(Unlock) then
            status = @db.unlock(@name, req.var)
            if status == :success then
                @status = :running
                @counter += 1
                puts "#{@name} Unock(#{req.var}) => success"
            else
                @status = :waiting
                puts "#{@name} Unock(#{req.var}) => fail"
            end
        elsif req.is_a?(Begin) then
            status = @db.begin(@name)
            if status == :success then
                @status = :running
                @counter += 1
                puts "#{@name} Begin => success"
            else
                @status = :waiting
                puts "#{@name} Begin => fail"
            end
        elsif req.is_a?(Rollback) then
            status = @db.rollback(@name)
            if status == :success then
                @status = :running
                @counter += 1
                puts "#{@name} Rollback => success"
            else
                @status = :waiting
                puts "#{@name} Rollback => fail"
            end
        elsif req.is_a?(Commit) then
            status = @db.rollback(@name)
            if status == :success then
                @status = :running
                @counter += 1
                puts "#{@name} Commit => success"
            else
                @status = :waiting
                puts "#{@name} Commit => fail"
            end
        end
    end

    def current_request_info()
        return @requests[counter].to_s()
    end
end

class Scheduler
    attr_reader :trs, :schedule,  :counter
    def initialize(trs, schedule)
        @trs = trs
        @schedule = schedule
        @counter = 0
    end

    def next()
        # check for dead lock.
        if @trs.all?{|tr_name, tr| tr.status == :waiting} then
            raise("Dead lock.")
        end
        # re-run for all locked transactions.
        transaction_status()
        @trs.each {|tr_name, tr|
            if tr.status == :waiting then
                print "re-try:"
                tr.next()
            end
        }
        # execute scheduled transaction.
        printf("%6d:", @counter)
        @trs[@schedule[@counter]].next()
        @counter += 1
    end

    def transaction_status()
        @trs.each {|tr_name, tr|
            puts "status:#{tr_name}: #{tr.status} #{tr.current_request_info()}"
        }
    end
end

@tr_a_req = [
    Begin.new(),
    Write.new("X",10),
    Read.new("X"),
    Write.new("X",20),
    Commit.new()
]

@tr_b_req = [
    Begin.new(),
    Lock.new("tr_a","X",:Shared),
    Commit.new()
]

@schedule = [
    "tr_a",
    "tr_a",
    "tr_b",
    "tr_b",
    "tr_a",
    "tr_a",
    "tr_b",
]

@db = Database.new()

@tr_a = Transaction.new(@db,"tr_a",@tr_a_req)
@tr_b = Transaction.new(@db,"tr_b",@tr_b_req)
@trs = {
    "tr_a" => @tr_a,
    "tr_b" => @tr_b
}
@master = Scheduler.new(@trs, @schedule)

@schedule.size().times {
    puts
    @master.next()
}

実行例


status:tr_a: running Begin
status:tr_b: running Begin
     0:tr_a Begin => success

status:tr_a: running Write(X,10)
status:tr_b: running Begin
     1:tr_a Write(X,10) => success

status:tr_a: running Read(X)
status:tr_b: running Begin
     2:tr_b Begin => success

status:tr_a: running Read(X)
status:tr_b: running Lock(tr_a,X,Shared)
     3:tr_b Lock(X,Shared) => success

status:tr_a: running Read(X)
status:tr_b: running Commit
     4:tr_a Read(X) => 10

status:tr_a: running Write(X,20)
status:tr_b: running Commit
     5:tr_a Write(X,20) => fail

status:tr_a: waiting Write(X,20)
status:tr_b: running Commit
re-try:tr_a Write(X,20) => fail
     6:tr_b Commit => success

ステップ3でtr_bが共有ロックを取得したので、ステップ5でtr_aのWriteが失敗する。その後、tr_bがコミットをすると、tr_bが取得したロックが全て外れる。ので、このままステップ7を実行すれば、tr_aの待ちが解消されてWriteが成功する。