Last active
September 29, 2020 16:23
-
-
Save tompng/fb2bf44391c48ecdea404473becb8150 to your computer and use it in GitHub Desktop.
Ractorで作ったSTMみたいなもの?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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