What have you found for these years?

2011-10-05

concurrency model 的選擇?

快速筆記思緒...

假設現在電腦都只有一核心一 cpu 以簡化問題。
如果現在有一個程式需要 concurrency 的能力,
該如何選擇呢?

我想關鍵在於 context switch 的時機。或是應該說,
我們有沒有能力自己承擔 context switch 的能力?
一個極端複雜的 concurrency 程式,就像我們不想
手動管理資源,而交給 gc 去處理,極端複雜的情形下,
我們都會希望有某種可以預先寫好的演算法去處理。

也就是說,這種時候我們會希望使用 os 提供的
process 或是 thread 來達到 concurrency, 由 os
或 system library 去處理 context switch 的時機。

但這些東西當然都是有成本的。或許我們可以再拿 gc
為例。我不是很清楚歷史,不知道早期 gc 不流行是
不是因為我們還沒有足夠好的 gc 演算法,因此 gc 的
效能不彰。現在我們有各種先進的 gc 演算法,gc
可以說是先進語言中不可或缺的一環。

我們有沒有可能說,thread 或是 process 的方式,
現在之所以會顯得太過 heavyweight, 無法承受極大量的
使用,是因為演算法還不夠好?或是說,核心數還不夠多?
也因此,在需要極大量的 concurrency 能力時,手動管理
context switch 才能夠有足夠的效能?因此我們有....

coroutine, evented driven, green thread, lightweight
process, fiber, etc etc...

或是我們可以換個角度來說。在 io intensive 的 program
裡面,由於我們不需要很複雜的 context switch 的能力,
因此應該盡量用 lightweight 的方式,也就是上面提到那一串。

而在 cpu intensive 的 program 裡,由於我們可能需要
用很複雜的方式去切割 cpu resource, 或是說要利用多核心,
因此還是只能回到 thread 或 process 上去。而要用很複雜的
方式切割 cpu 的原因,可能是因為我們很難去預測,每一個
context 需要花多少的時間或資源去運算。而在 io intensive 的
program 裡,反正 cpu resource 多得很,就算亂切一通,
就算切得很大塊,最後的結果也是一下就處理好了。

講得很亂,因為只想把思緒記錄下來。

這樣說好了,我一直不懂 concurrency, 而且覺得 multithread
很可怕,處理 mutex, lock, monitor, semaphore, race condition
live lock, dead lock, etc etc 一堆議題實在很恐怖... 就一直想走
evented 或是 coroutine, user process 等等的方式。

不過看來看去,也慢慢理解到那些是有天限的,而且也同樣可能
因為處理不好,而導致大災難...

也就是說,說來說去,就是沒有 silver bullet 就對了...

我們當然會想用盡量簡單的方式解決問題,但如果一個問題本來
就複雜無比,那一直用簡單的方式去試,恐怕也可能永遠解決不了。
而我們其實也很難去預測一個問題到底是有多複雜,直到我們真的
花了很多時間在研究之後,可能才會意會 -- 其實也可能不會。

嘛,不過如果說是寫 haskell 的話,感覺上就不太需要想這些問題。
我指 concurrency 方面。也不是說 haskell 是 silver bullet, 用了
就不用想這些,而是理論上這些東西應該是 haskell 實作者應該去
處理的。說是理論上,實際上這或許永遠也做不到也說不定。

比方說,我想 stm 和 actor model 就是比這還要高一個層級的問題。
我們可以用任何方式實作 stm 或 actor model, 然而這也不表示
不需要思考底層到底是怎麼實作的。另一方面,就算完全用底層去想,
也一樣還是得面臨高階的 race condition 等等問題!就算是 haskell,
說是沒有 state, 但在寫非純運算的 concurrency 程式時,一樣得
處理 state, 一樣會面臨到這些問題。

甚至我們可以想像成,先用 haskell 實作出一個像是 c 的 dsl !!
好吧,或許 c 太低階了,但不管怎麼樣,問題本身就是 stateful 時,
我們當然也還是得先描繪出什麼是 state, 才能描述問題是什麼。
那麼我們就等於是在 haskell 中放入 state 了...

所以其實還是逃不掉啊。

4 retries:

Poga Po said...

純粹運算的情況下,MapReduce算是解決了一些問題吧

就像是thread在運算的時候完全不溝通(沒有share data),只有各個thread得到結果之後才去整理所有thread的結果? XD

Lin Jen-Shin (godfat) said...

怎麼說呢,我覺得這可能不太算是 concurrency 的問題,
比較像是 scalability 的問題?

說到這,我還是不知道 parallelism 和 concurrency 之間的差別 :(

Lin Jen-Shin (godfat) said...

根據這句話:
"""Concurrency is concerned with nondeterministic composition of programs (or their components). Parallelism is concerned with asymptotic efficiency of programs with deterministic behavior."""
from Parallelism is not concurrency
我們可以說 MapReduce 是 parallelism 的問題嗎?

Poga Po said...

看起來應該沒錯,MapReduce主要解的還是deterministic的問題...
HTTP server這種算是concurrency problem.

兩者不相關 :P

Post a Comment

All texts are licensed under CC Attribution 3.0