早期電腦僅有單一 CPU (甚至沒有 microprocessor 技術),但那時的作業系統就有多任務並行的需求:當一個任務正在執行時,另一個任務到來,於是作業系統 (早期的術語稱為 monitor) 就會判斷是否切換到新的任務,若是,作業系統會保存目前的 context,然後切換到另一個任務。
coroutine於 1958 年由 Melvin Conway 提出,引述 Wikipidia 的描述:
Coroutines are computer program components that generalize subroutines for non-preemptive multitasking, by allowing execution to be suspended and resumed. Coroutines are well-suited for implementing familiar program components such as cooperative tasks, exceptions, event loops, iterators, infinite lists and pipes.
除了上述所列的實用情境外,也有被運用於 server accept 、Virtual Machine 等。而關於 preemptive multitasking ,請不要侷限於定義上,在其他實作中,coroutine 也可以藉由 signal 等相關操作實作 preemptive 。
在分類上,coroutine 分成 stackful 和 stackless 兩種。一般來說 stackful 可自行切換 subroutine ,而 stackless 需要提供 suspend
和 resume
等功能自行手動切換。然而,stackful 需要有分配記憶體空間儲存 stack 等資訊,在 context switch 上會比 stackless 沒有效率(需要考量複製現存資訊、cache locality 等議題)。在 C++20 ,C++ 提供 coroutine 的功能,而在 2014 年時,有一份關於 coroutine 新增至 C++ Standard Library 的報告,可以參考:Stackful Coroutines and Stackless Resumable Functions; 2018 年的報告: Working Draft, C++ Extensions for Coroutines;也可看此部落格所寫的文章:Stackless vs. Stackful Coroutines。另外,其他實作案例包含,知名虛擬機器 QEMU 的 coroutine [1][2] 及 Meta 的 folly 中所使用的 coro。甚至 LLVM 或者說 Clang 編譯器也有提供 builtin coroutine support 。
以非 C/C++ 的語言來說,由 Google 開發的 Golang 也有 Goroutine 。除此之外,Google 也有對 Linux Kernel 提出 User-managed concurrency groups ,相當於使用層級執行緒,該實作方式由作業系統進行 context switch 。
coroutine 當中的 context switch 實作方式,可以藉由 setjmp / longjmp、組合語言 或 POSIX 的 ucontext 實作。各有利弊需要考量運用情境,例如最簡單的 setjmp / longjmp ,可以在 cppreference 的描述可見,對於變數的型態有相關的限制:
Upon return to the scope of setjmp, all accessible objects, floating-point status flags, and other components of the abstract machine have the same values as they had when longjmp was executed, except for the non-volatile local variables in the function containing the invocation of setjmp, whose values are indeterminate if they have been changed since the setjmp invocation.
而 volatile 會造成編譯器無法對其變數進行最佳化,而導致執行效率無法提昇。並且,若要在 signal handler 以 setjmp / longjmp 實作,則須考量 glibc 等函式庫所作的安全防範措施。可見 CS170: Project 2 - User Mode Thread Library (20% of project score)。
延伸閱讀: coroutine 的歷史、現在和未來
任務可概略分為:
早期伺服器為了解決並行需求,採用一個網路連線對應一個行程 (如 Apache HTTP Server,即 httpd
)。後來 CPU 發展到多核,該架構調整為一個網路連線對應到一個執行緒,或者是事先配置的的 thread pool。
逐漸作業系統和應用程式框架提出 event loop 的開發介面,即 EventLoop + Callback 的方式,該模式存在多個變種,如: loop per thread,但共同特點都是 callback function 中處理事件。隨著軟體規模的擴展,callback 的變得更複雜,不乏有巢狀呼叫 (nested),這對於程式開發和除錯帶來嚴重的負面影響。
goroutine 的出現帶來新的改變 —— 以同步的方式處理原本非同步執行的程式碼,於是變得更直覺、程式碼易於閱讀且除錯,適合 I/O 密集型任務,這背後的機制就是 coroutine。相較於執行緒,coroutine 佔用的記憶體空間更少,且通常不需要作業系統介入,從而在高度並行的情境可帶來優異的效能表現。
QEMU 內建 coroutine
LLVM 提供 coroutine 支援
Coroutine
FreeRTOS 的 coroutine