Coroutine: 入門篇

,

Coroutine 一般翻譯作「協程」，對一般 programmer 來說可能有些陌生，但其實這個想法早在 1963 年就被提出來了。近年來因為 multi-threading 的普及，主流語言鮮少提供 coroutine 的功能，但即使 coroutine 與 thread 的概念相似，卻有許多截然不同的特性，不少場合使用 coroutine 既能優雅地解決問題，又能避免 multi-threading 的 race condition。本系列文章將會介紹 coroutine 的基本概念及應用場合，讓原本複雜的流程變得簡潔易懂。

Lua 是支援 coroutine 的語言之一，同時也具備簡單易學的特性，以下將會使用 Lua 程式碼作為 coroutine 的示範。對 Lua 不熟悉的讀者可以參考 Lua Tutorial Dictionary 上的教學，實際學起來是很快的。

Coroutine 基本概念

Coroutine 可以視為「可以中斷及繼續執行的函式呼叫」。在一般的程式語言中，呼叫某個函式時，該函式一定是從頭開始執行：

1
2
3
4
5
6
7
function foo(n)
    print("hello")
    print("world")
    print("n^2 = "..(n*n))
end
foo(10) -- 不間斷地印出三行字

然而 coroutine 允許函式執行到一半就中斷（yield），中斷時內部狀態會被保留下來，呼叫端可以隨時在之後恢復（resume）這個 coroutine。

1
2
3
4
5
6
7
8
9
10
11
12
function bar(n)
    print("hello")
    print("world")
    coroutine.yield()            -- 在這裡中斷 coroutine
    print("n^2 = "..(n*n))
end
local co = coroutine.create(bar) -- co 是保留 coroutine 內部狀態的變數
coroutine.resume(co, 10)         -- 只印出前兩行 hello world
print("this is the third line.") -- 中斷後主程式可以做其它事
coroutine.resume(co)             -- 印出最後一行 n^2 = 100

上述的範例即為 coroutine 的呼叫方法：

  1. 呼叫端並非直接呼叫函式，而是使用 coroutine.create 來產生一個 coroutine object。這個 object 將會儲存 coroutine 的執行狀態，包括區域變數的內容及中斷點的位置。
  2. 產生 coroutine object 的時候並不會呼叫函式，而是在第一次使用 coroutine.resume 的時候，才會從函式的開頭開始執行。
  3. 在函式中使用 coroutine.yield 時，將會中斷函式執行並保留中斷時的狀態，控制權隨即轉移到呼叫端。
  4. 呼叫端再次執行 coroutine.resume 的時候，流程將會回到 coroutine 上次中斷之處，繼續往下執行到 yield 或函式結束。

任意中斷的特性

Coroutine 中的兩項操作：yield 及 resume，在 Lua 中只是基本的函式呼叫。你可以使用任意數量的 yield 來中斷 coroutine，當然也可以放在迴圈之類的控制結構當中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function fibb()
    local a = 1
    local b = 0
    while true do
        print(a)
        coroutine.yield()
        local tmp = a
        a = a + b
        b = tmp
    end
end
local co = coroutine.create(fibb)
for i=1,20 do                     -- 印出費氏數列前20項
    coroutine.resume(co)
end

當然，在 coroutine 中可以呼叫其它函式，而 yield 也能出現在更深層的函式當中。我們會在下一篇文章中介紹這個應用。

Coroutine 的資料傳遞

在上面費氏數列的例子中，我們都是把數字印出來後才呼叫 coroutine.yield，這顯然彈性不夠－－呼叫端可能想把數字寫到檔案、或是塞進陣列中。我們能直接把數值在 yield 的同時直接傳回到主程式嗎？答案是肯定的，而且方法非常簡單：直接當作參數丟給 coroutine.yield。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function fibb()
    local a = 1
    local b = 0
    while true do
        coroutine.yield(a)
        local tmp = a
        a = a + b
        b = tmp
    end
end
local co = coroutine.create(fibb)
local array = {}                  -- 建立空陣列
local state                       -- 表示 coroutine 的狀態
for i=1,20 do                     -- 把費氏數列前20項填進陣列中
    state, array[i] = coroutine.resume(co)
end

coroutine.resume 的第一個回傳值皆為 true 或 false，表示該 coroutine 是否正確執行。而第二個以後的回傳值則是 coroutine 在中斷時傳進 coroutine.yield 的參數，因此在第 15 行我們需要用兩個變數來接 coroutine 的回傳值。

反過來說，主程式也可以在呼叫 coroutine.resume 的時候添加參數，這些參數會被傳遞到 coroutine 當中，作為 coroutine.yield 的回傳值。

1
2
3
4
5
6
7
8
9
10
11
12
function foo(n)
    print("n = " .. n)
    while true do
        print("received " .. coroutine.yield())
    end
end
local co = coroutine.create(foo)
coroutine.resume(co, 10)         -- 印出 n = 10
coroutine.resume(co, 20)         -- 印出 received 20
coroutine.resume(co, 30)         -- 印出 received 30
coroutine.resume(co, 40)         -- 印出 received 40

第一次呼叫 coroutine.resume 時，添加的參數會被當作是函式的參數，也就是 n。第二次以後的 resume 其參數則會被當作 yield 的回傳值送進 coroutine 之中。

籍由資料傳遞的功能，我們可以利用 coroutine 輕鬆實作出 iterator pattern。我會在下一篇文章介紹這項應用。

Coroutine 與 Generator

嚴格說來，Lua 所提供的 coroutine 應該要稱之為 generator。根據 wikipedia 的說法，coroutine 在進行 yield 操作時需指定另一個 coroutine 作為參數，因此多個 coroutine 之間可以隨意跳來跳去。而在 Lua 的 coroutine 中，yield 必然回到上次呼叫 resume 的地方。

Wikipedia 上的 coroutine 範例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var q := new queue
coroutine produce
    loop
        while q is not full
            create some new items
            add the items to q
        yield to consume
coroutine consume
    loop
        while q is not empty
            remove some items from q
            use the items
        yield to produce

嚴格定義下的 coroutine 實際上可以用 generator 來達成，而許多語言似乎也沒有很精確地區分這兩者。在接下來的文章中，我會繼續用 coroutine 來稱呼。

Coroutine 與 Thread

在系統層面上，coroutine 通常和 fiber 是一樣的意思。Fiber 是一種特別的 user thread，如同一般的 thread 那樣具有自己的 call stack 與 program counter，但具備了以下的特性：

  • Thread 不需自己定義中斷點（也就是呼叫 yield 的地方），而是讓 OS 或 thread library 來決定是否進行 context switch，通常由執行時間來判斷。然而 fiber 需要自行定義中斷點，context switch 只會發生在明確呼叫 yield 的地方。
  • 因為 context switch 是由使用者自行控制，因此 fiber 通常 不需要 mutex 之類的東西來避免 race condition。
  • Kernel thread 會進入 OS 的排程中，在多核心的 CPU 上可能會使用不同的核心同時執行許多 kernel thread。但 fiber 屬於特別種類的 user thread，它無法利用多核心進行平行處理。

下一篇文章中，我將以 iterator 作為例子，介紹簡單的 coroutine 應用方式。

分享到 評論