Skip to content

Instantly share code, notes, and snippets.

@tompng
Last active September 29, 2020 16:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tompng/fb2bf44391c48ecdea404473becb8150 to your computer and use it in GitHub Desktop.
Save tompng/fb2bf44391c48ecdea404473becb8150 to your computer and use it in GitHub Desktop.
Ractorで作ったSTMみたいなもの?
module STM
class Pipe < Ractor
def self.create() = new { loop { Ractor.yield Ractor.recv } }
end
class OpRead < Pipe; end
class OpReqLock < Pipe; end
class OpReadVersion < Pipe; end
ReadPool = Pipe.create
ReqLockPool = Pipe.create
ReadVersionPool = Pipe.create
64.times do
ReadPool << OpRead.create
ReqLockPool << OpReqLock.create
ReadVersionPool << OpReadVersion.create
end
class TVar < Ractor
def self.new(initial = nil)
lock = Ractor.new { loop { Ractor.yield Ractor.recv } }
lock << :lock
super(lock, initial) do |lock, value|
version = 0
loop do
cmd = Ractor.recv
case cmd
when OpReqLock
cmd << lock
when OpReadVersion
cmd << version
when OpRead
cmd << version
cmd << value
else
value = cmd
version += 1
end
end
end
end
end
class TVarInTransaction
attr_reader :version
def initialize(version, value)
@version = version
@value = value
@read = false
@write = false
end
def read?() = @read
def written?() = @written
def value
@read = true
@value
end
def value=(value)
@written = true
@value = value
end
end
class Abort < StandardError; end
def self.abort
raise Abort
end
def self.atomically(*tvars)
read = ReadPool.take
req_lock = ReqLockPool.take
read_version = ReadVersionPool.take
loop do
ttvars = tvars.uniq.sort_by(&:__id__).map do |tvar|
tvar << read
version = read.take
value = read.take
[tvar, TVarInTransaction.new(version, value)]
end.to_h
begin
yield(*tvars.map(&ttvars))
rescue Abort
break
end
affecteds = ttvars.select { _2.read? || _2.written? }
locks = []
conflict = false
affecteds.each do |tvar, ttvar|
tvar << req_lock
lock = req_lock.take
lock.take
locks << lock
tvar << read_version
version = read_version.take
if ttvar.version != version
# p :conflict
conflict = true
break
end
end
unless conflict
affecteds.each do |tvar, ttvar|
tvar << ttvar.value if ttvar.written?
end
end
locks.each { _1 << :lock }
break unless conflict
end
ensure
ReadPool << read
ReqLockPool << req_lock
ReadVersionPool << read_version
end
end
require_relative './stm'
t1 = STM::TVar.new(0)
t2 = STM::TVar.new(0)
t3 = STM::TVar.new(0)
ractors = 10.times.map do
Ractor.new(t1, t2, t3) do |t1, t2, t3|
100.times do
STM.atomically(t1, t2) do |t1, t2|
v1 = t1.value
v2 = t2.value
t1.value = t1.value + 1
t2.value = t2.value + 1
end
STM.atomically(t2, t3) do |t2, t3|
v2 = t2.value
v3 = t3.value
t2.value = t2.value + 1
t3.value = t3.value + 1
end
STM.atomically(t3, t1) do |t3, t1|
v3 = t3.value
v1 = t1.value
t3.value = t3.value + 1
t1.value = t1.value + 1
end
end
end
end
ractors.map(&:take)
STM.atomically(t1, t2, t3) do |t1, t2, t3|
p t1.value, t2.value, t3.value
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment