What have you found for these years?

2011-12-24

concurrency and coroutine 的目前了解


講得有點亂,請見諒。東西太多,例外太多,很難一言以蔽之 :( 感覺
要講得容易懂,就勢必得簡化東西,也就等於一定會有東西講得不太
正確。而講得正確一點的話,由於太複雜太多東西,又很難表達清楚。



有點不知道從何開始說。這樣說吧,我們如何「執行」一個程式?
或是說,何謂一個「程式」?依照目前大多數的程式設計法,我們
會把一個程式切分成很多不同的 subroutine, 或是說 function,
使得我們可以重複利用同一段程式,而非不斷複製貼上同一段程式。

因此,在大多數的程式裡,我們可以理解成程式是由許多的 subroutine
組成。而為了讓 subroutine 可以再呼叫另一個,或是同一個 subroutine,
我們會用 call stack 這個概念來維護 subroutine 的 context.

這邊不細說明 subroutine 和 call stack. 總而言之,要「執行」這種
架構的程式,我們會需要 call stack. 一個 CPU 或說一個核心,可以
用 call stack 執行某個 subroutine, 而這個 subroutine 也可以呼叫
其他的 subroutine.

到這裡,「執行」這隻程式的東西就叫做 process. 如果我們要同時
執行許多的 process, 則由 OS 做 scheduling, 也就是先讓一顆 CPU
或一個核心執行一個 process, 接著 OS 可能會決定讓這隻 process
suspend 一下,透過 context switch 執行另一個 process. 可能執行
一小段時間後,OS 又決定要 suspend 這隻 process, 然後 resume
上一隻跑到一半的 process, 達成 multitasking.

當然,如果我們有多顆 CPU 或核心,OS 可以讓不同 process 跑在
不同的核心(後面省略 CPU)上。但不管怎麼樣,核心數有限,process
數無限,總還是會需要 context switch 達成 multitasking.



process 完全由 OS 處理,process 跟 process 間不共享 memory space,
要存取對方的資料,只能透過某種溝通才能達成。但有些時候,我們會需要
共享的資料,用溝通的方式會變得很不方便。這時候我們就有了 thread.

這邊不談任何實作細節,也不談一些例外,只講概念。像是 green thread,
lightweight process 這些都是實作上的例外。thread 與 process 之間,
最主要的不同點在於 thread 有共享的 memory space, 而 process 沒有。
thread 的 scheduling 我猜測是由 thread library 提供,且因為由於有共享的
資料,thread 與 thread 間往往會有 race conditions, 需要 mutex 來避免。

這並不是在說 process 與 process 間並不會有 race conditions, 任何
concurrent 的程式,無論用任何方式,都一定會有 race conditions,
重點在於會有問題的範圍在哪裡?同時,會不會有問題也取決於我們「要的」
到底是什麼。這邊也不細討論 race conditions.

複習一下:(第三個 cost 是 context switch 的 cost, 不是必然的)

scheduling on multiple cores shared state cost (usually)
process OS could be no higher
thread library could be yes lower



接著終於來到 coroutine 了。簡單地說,coroutine 就是由 application 來做
scheduling 的 thread. 而這造成了決定性的差異,process/thread 由於不是
由 application 做 scheduling, 因此執行結果對 application 而言是
non-deterministic 的。而 coroutine 由於交給 application 做 scheduling,
只要沒有用到 asynchronous I/O, 基本上應該是 deterministic 的?
也就是說,執行結果是可以預期的。

這樣能算是 concurrent 的程式嗎?為此我困惑了一段時間。我想仍然是的,
只是單純把 scheduling 的責任交給 application programmer, 同時,由於
如果我們需要不同的核心來做真正的 concurrency 的話,應該用 thread 或
process, 因此 coroutine 也不大會想放到不同核心上跑。或許可以想像成
只有一顆單核心 CPU 的時代的感覺吧。也由於用很單純的方式做 scheduling,
成本也比 process/thread 要來得低許多。

跟 process/thread 一樣的是,每個 coroutine 也都有自己的 call stack.
由 application 決定何時 suspend/resume. thread 會有 race conditions
的問題,coroutine 也同樣會有。重點則於,如果在不預期的地方 suspend
跳到別的 coroutine, 然後這個 coroutine 又去存取同樣的 state 的話,
這時候就可能會有 race conditions 了。

process 可想像成好幾個人同時在工作;thread 也可想像成好幾個人同時
在工作,只是他們往往會一起同時伸手去搶食物;coroutine 則想像成也是
好幾個人同時在工作,但一個時間點內,只有拿到信物的那個人才可以動。

process 與 thread 都是適合 CPU bound 的程式,而 coroutine 則適合
I/O bound 的程式(因為利用簡單的 context switch 來降低成本)。
event driven 也是適合 I/O bound 的程式,搭配 coroutine 正好可以解決
event callback spaghetti 的問題。

每一種技巧都有每一種技巧的好處與壞處,發明這麼多類似的東西,
當然是有原因的...。 :(

scheduling on multiple cores shared state cost (usually)
process OS could be no higher
thread library could be yes lower
coroutine application no yes lowest



p.s. 下次講 concurrency 的東西的話,我要講云風的 lua agent 的 coroutine 架構

0 retries:

Post a Comment

Note: Only a member of this blog may post a comment.



All texts are licensed under CC Attribution 3.0