Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@kencoba

トランザクションシミュレータ(ロック待ちバージョン)

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

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が成功する。

0
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
kencoba
A newbie Rustacean.

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?