星之一角: 4/1/12

2012-04-05

thread-safe is not fiber-safe; fiber-safe could be even harder (3)

Other posts:
2148. 04-04 thread-safe is not fiber-safe; fiber-safe could be even harder
2149. 04-04 thread-safe is not fiber-safe; fiber-safe could be even harder (2)
2151. 04-05 thread-safe is not fiber-safe; fiber-safe could be even harder (3)

So I have done the Haskell equivalent for last examples.
To run these examples, you need to cabal install monad-coroutine
P.S. You can find all the codes in my sandbox/haskell/coroutine

deterministic race conditions in coroutines

import Data.IORef (IORef, newIORef, readIORef, writeIORef)
import Control.Monad.Trans (lift)
import Control.Monad.Coroutine (Coroutine, resume)
import Control.Monad.Coroutine.SuspensionFunctors (Yield(Yield), yield)

type Fiber = Coroutine (Yield ()) IO ()

fiber :: IORef Int -> Fiber
fiber i = do
            t <- lift (readIORef i)
            yield ()
            lift (writeIORef i (t + 1))
            return ()

main = do
  i <- newIORef 0
  let a = fiber i
      b = fiber i in do
      readIORef i >>= print -- 0
      Left (Yield _ a') <- resume a
      Left (Yield _ b') <- resume b
      resume a'
      resume b'
      readIORef i >>= print -- should be 2

STM cannot help here

import Control.Concurrent.STM (atomically, retry, TVar, STM,
                               newTVar, readTVar, writeTVar)
import Control.Monad.Trans (lift)
import Control.Monad.Coroutine (Coroutine, resume)
import Control.Monad.Coroutine.SuspensionFunctors (Yield(Yield), yield)

type Fiber = Coroutine (Yield ()) STM ()

fiber :: TVar Int -> Fiber
fiber i = do
            t <- lift (readTVar i)
            yield ()
            lift (writeTVar i (t + 1))
            return ()

main = do
  i <- atomically (newTVar 0)
  let a = fiber i
      b = fiber i in do
      atomically (readTVar i) >>= print -- 0
      Left (Yield _ a') <- atomically (resume a)
      Left (Yield _ b') <- atomically (resume b)
      atomically (resume a')
      atomically (resume b')
      atomically (readTVar i) >>= print -- should be 2

mutex, i.e. MVar is a better solution here, but beware of deadlock!

import Control.Concurrent.MVar (MVar, newMVar, readMVar, takeMVar, putMVar)
import Control.Monad.Trans (lift)
import Control.Monad.Coroutine (Coroutine, resume)
import Control.Monad.Coroutine.SuspensionFunctors (Yield(Yield), yield)

type Fiber = Coroutine (Yield ()) IO ()

fiber :: MVar Int -> Fiber
fiber i = do
            t <- lift (takeMVar i)
            yield ()
            lift (putMVar i (t + 1))
            return ()

main = do
  i <- newMVar 0
  let a = fiber i
      b = fiber i in do
      readMVar i >>= print -- 0
      Left (Yield _ a') <- resume a
      Left (Yield _ b') <- resume b -- deadlock
      return ()

The real solution with tryTakeMVar

import Control.Concurrent.MVar (MVar, newMVar, readMVar, tryTakeMVar, putMVar)
import Control.Monad.Trans (lift)
import Control.Monad.Coroutine (Coroutine, resume)
import Control.Monad.Coroutine.SuspensionFunctors (Yield(Yield), yield)

type Fiber = Coroutine (Yield ()) IO ()

fiber :: MVar Int -> Fiber
fiber i = lift (tryTakeMVar i) >>= \t ->
            case t of
              Nothing -> yield () >> fiber i
              Just t  -> do
                           yield ()
                           lift (putMVar i (t + 1))
                           return ()

schedule :: [Fiber] -> IO ()
schedule []     = return ()
schedule (f:fs) = resume f >>= \t -> case t of
                    Left (Yield _ f') -> schedule (fs ++ [f'])
                    Right _           -> schedule  fs

main = do
  i <- newMVar 0
  let a = fiber i
      b = fiber i in do
      readMVar i >>= print -- 0
      schedule [a, b]
      readMVar i >>= print -- 2

Conclusion

So after all this, my current conclusion is that, as every one might
already know, there's no silver bullet at all. We need threads, we
needs fibers (coroutines), we also need mutex (either with explicit
locking or not), and we also need STM in some cases. Use the right
tool for the right thing, after all... and never throw our old friends
(e.g. lock) away whether they are good or bad...

Long lived tools must have its values which cannot be easily replaced :o

反覆與步調

一下覺得很慘，一下覺得好多了，數分鐘之內不斷反覆，在想，
或許這也證明了自己的逞強，或是其實那是一種欺騙，或是本來
逞強這件事就是一種欺騙，目的只是希望能有比較好的結果，
而不是立刻放棄而求救或是徹底絕望。

我想我有我自己的步調與方式，無論那究竟是好或壞。我也決定不了。

edited 2012-04-05 01:35 不，其實只是逃避而已。

2012-04-04

thread-safe is not fiber-safe; fiber-safe could be even harder (2)

Other posts:
2148. 04-04 thread-safe is not fiber-safe; fiber-safe could be even harder
2149. 04-04 thread-safe is not fiber-safe; fiber-safe could be even harder (2)
2151. 04-05 thread-safe is not fiber-safe; fiber-safe could be even harder (3)

So I just realized that threads are not needed actually. Here's the updated solution:

detect deadlock and retry

require 'fiber'

m = Mutex.new
i = [0]
a = Fiber.new{
      begin
        m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 }
      rescue ThreadError => e
        Fiber.yield e
        retry
      end
    }
b = Fiber.new{
      begin
        m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 }
      rescue ThreadError => e
        Fiber.yield e
        retry
      end
    }
p i # => [0]
while a.alive? || b.alive?
  a.resume if a.alive?
  b.resume if b.alive?
end
p i # => [2]

retry in an eventmachine loop

require 'fiber'
require 'eventmachine'

EM.run{
  m = Mutex.new
  i = [0]
  a = Fiber.new{
        begin
          m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 }
        rescue ThreadError => e
          Fiber.yield e
          retry
        end
      }
  b = Fiber.new{
        begin
          m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 }
        rescue ThreadError => e
          Fiber.yield e
          retry
        end
      }
  p i # => [0]
  EM.add_periodic_timer(0.1){
    if !a.alive? && !b.alive?
      p i # => [2]
      EM.stop
    else
      a.resume if a.alive?
      b.resume if b.alive?
    end
  }
}

Also, I think STM won't really help here, because we need to retry anyway.
The only advantage is that we don't need to "lock" early, but only retry
upon "failures" and yet we would need to define what is a failure.

So in this extremely simple (trivial) example, locking is actually easier than
STM. The advantage of STM, I think, might be the ability to combine and
mix transactions without worrying too much, maybe, I am not sure.
Perhaps if we're using it without too much consideration, we would also
end up with deadlock or livelock, i.e. endless retry.

Next I would try either to implement STM in Ruby to try out, or just try
Haskell next time, given that I'd experience with STM in Haskell.
I need to see how to use coroutines in Haskell though.

thread-safe is not fiber-safe; fiber-safe could be even harder

deterministic race conditions in fibers

i = [0]
a = Fiber.new{ t = i[0]; Fiber.yield; i[0] = t + 1 }
b = Fiber.new{ t = i[0]; Fiber.yield; i[0] = t + 1 }
p i # => [0]
a.resume
b.resume
a.resume # 1
b.resume # 1
p i # => [1] # should be [2]

thread-safe code is not fiber-safe, here we have deadlock

m = Mutex.new
i = [0]
a = Fiber.new{ m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 } }
b = Fiber.new{ m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 } }
p i # => [0]
a.resume
b.resume # ThreadError: deadlock; recursive locking

reentrant mutex doesn't really lock for fibers. it still has race conditions

require 'monitor'
m = Monitor.new
i = [0]
a = Fiber.new{ m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 } }
b = Fiber.new{ m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 } }
p i # => [0]
a.resume
b.resume
a.resume # 1
b.resume # 1
p i # => [1] # should be [2]

detect deadlock and retry with threads to resume fibers again, finally fiber-safe now

require 'fiber'

def try_resume f
  case r = f.resume
  when ThreadError
    Thread.new{ sleep(0.1); try_resume(f) }
  else
    r
  end if f.alive?
end

m = Mutex.new
i = [0]
a = Fiber.new{
      begin
        m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 }
      rescue ThreadError => e
        Fiber.yield e
        retry
      end
    }
b = Fiber.new{
      begin
        m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 }
      rescue ThreadError => e
        Fiber.yield e
        retry
      end
    }
p i # => [0]
while a.alive? || b.alive?
  try_resume(a)
  try_resume(b)
end
p i # => [2]

retry with eventmachine instead, but do we really want to do this?

require 'fiber'
require 'eventmachine'

def try_resume f
  case r = f.resume
  when ThreadError
    EM.add_timer(0.1){ try_resume(f) }
  else
    r
  end if f.alive?
end

EM.run{
  m = Mutex.new
  i = [0]
  a = Fiber.new{
        begin
          m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 }
        rescue ThreadError => e
          Fiber.yield e
          retry
        end
      }
  b = Fiber.new{
        begin
          m.synchronize{ t = i[0]; Fiber.yield; i[0] = t + 1 }
        rescue ThreadError => e
          Fiber.yield e
          retry
        end
      }
  p i # => [0]
  try_resume(a)
  try_resume(b)
  EM.add_periodic_timer(0.1){
    try_resume(a)
    try_resume(b)
    if !a.alive? && !b.alive?
      p i # => [2]
      EM.stop
    end
  }
}

can STM (software transactional memory) help here?

STM for Ruby WANTED!!

or let's just use threads, shall we?

m = Mutex.new
i = [0]
a = Thread.new{ m.synchronize{ t = i[0]; sleep(0.1); i[0] = t + 1 } }
b = Thread.new{ m.synchronize{ t = i[0]; sleep(0.1); i[0] = t + 1 } }
p i # => [0]
a.join
b.join
p i # => [2]

--
concurrency with shared state is really hard!

2012-04-03

自由意志

想了想還是轉到 blog 上來好了。原本貼在 g+

Turing機、人工智能以及我們的世界

現在才翻完這篇，沒看得很仔細，因為類似的東西想到爛了，
沒什麼耐心細讀。不過最後一段勾起了我的注意。

不過，現代物理學的觀念，尤其是量子理論的誕生，開始質疑上帝究竟會不會擲骰子了。
然而，上帝會不會擲骰子，對於我們來說其實並不重要。 Turing 的結論告訴我們，
即使未來是注定的，我們也沒有一種算法去預測它，除非模擬它運行一遍。但是，
要想模擬這個宇宙的運行，需要的計算量必然超出了這個宇宙自身的所有資源。
運行這個宇宙的唯一方式，就是運行這個宇宙本身。 Seth Lloyd 在
《Programming the Universe》裡說到，「我們體會到的自由意志很像 Turing 的
停機問題：一旦把某個想法付諸實踐，我們完全不知道它會通向一個怎樣的結局，
除非我們親身經歷這一切，目睹結局的到來。」

未來很可能是既定的，但是誰也不知道未來究竟是什麼樣。每個人的將來依舊充滿了
未知數，依舊充滿了不確定性。所以，努力吧，未來仍然是屬於你的。

倒是沒想過把 halting problem 跟自由意志連起來過。不過以這個角度來說的話，
我們確實可以有自由意志。有種好像很簡單地解決了很困難的問題的感覺...

禁止餵食

日期分類

標籤分類

星之一角