---
tags: concurrency
---

# [並行程式設計](https://hackmd.io/@sysprog/concurrency): Coroutine

## [coroutine](https://en.wikipedia.org/wiki/Coroutine) 並非新概念

早期電腦僅有單一 CPU (甚至沒有 microprocessor 技術)，但那時的作業系統就有多任務並行的需求：當一個任務正在執行時，另一個任務到來，於是作業系統 (早期的術語稱為 monitor) 就會判斷是否切換到新的任務，若是，作業系統會保存目前的 context，然後切換到另一個任務。

[coroutine](https://en.wikipedia.org/wiki/Coroutine)於 1958 年由 Melvin Conway 提出，引述 [Wikipidia](https://en.wikipedia.org/wiki/Coroutine) 的描述：
> 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](https://man7.org/linux/man-pages/man7/signal.7.html) 等相關操作實作 [preemptive](https://www.ptt.cc/bbs/C_and_CPP/M.1584751926.A.0D6.html) 。

在分類上，coroutine 分成 stackful 和 stackless 兩種。一般來說 stackful 可自行切換 subroutine ，而 stackless 需要提供 `suspend` 和 `resume` 等功能自行手動切換。然而，stackful 需要有分配記憶體空間儲存 stack 等資訊，在 context switch 上會比 stackless 沒有效率（需要考量複製現存資訊、cache locality 等議題）。在 [C++20](https://en.cppreference.com/w/cpp/language/coroutines) ，C++ 提供 coroutine 的功能，而在 2014 年時，有一份關於 coroutine 新增至 C++ Standard Library 的報告，可以參考：[Stackful Coroutines and Stackless Resumable Functions](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4232.pdf)； 2018 年的報告： [Working Draft, C++ Extensions for Coroutines](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/n4775.pdf)；也可看此部落格所寫的文章：[Stackless vs. Stackful Coroutines](https://blog.varunramesh.net/posts/stackless-vs-stackful-coroutines/)。另外，其他實作案例包含，知名虛擬機器 QEMU 的 [coroutine](https://www.youtube.com/watch?v=2gNszk7OjIY) [[1]](https://www.qemu.org/docs/master/devel/block-coroutine-wrapper.html)[[2]](http://blog.vmsplice.net/2014/01/coroutines-in-qemu-basics.html) 及 Meta 的 folly 中所使用的 [coro](https://github.com/facebook/folly/tree/c2c5b28d3273a24bd4fe5393b3fb728cfe541284/folly/experimental/coro)。甚至 LLVM 或者說 Clang 編譯器也有提供 [builtin coroutine support](https://clang.llvm.org/docs/LanguageExtensions.html#c-coroutines-support-builtins) 。

以非 C/C++ 的語言來說，由 Google 開發的 [Golang](https://en.wikipedia.org/wiki/Go_(programming_language)) 也有 [Goroutine](https://go.dev/tour/concurrency/1) 。除此之外，Google 也有對 [Linux Kernel](https://lwn.net/Articles/863386/) 提出 [User-managed concurrency groups](https://lwn.net/Articles/879398/) ，相當於使用層級執行緒，該實作方式由作業系統進行 context switch 。

coroutine 當中的 context switch 實作方式，可以藉由 [setjmp](https://en.cppreference.com/w/c/program/setjmp) / [longjmp](https://man7.org/linux/man-pages/man3/longjmp.3p.html)、[組合語言](https://github.com/hnes/libaco/blob/master/acosw.S) 或 POSIX 的 [ucontext](https://pubs.opengroup.org/onlinepubs/7908799/xsh/ucontext.h.html) 實作。各有利弊需要考量運用情境，例如最簡單的 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](https://en.cppreference.com/w/c/language/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](https://lwn.net/Articles/233479/) 會造成編譯器無法對其變數進行最佳化，而導致執行效率無法提昇。並且，若要在 signal handler 以 setjmp / longjmp 實作，則須考量 glibc 等函式庫所作的安全防範措施。可見 [CS170: Project 2 - User Mode Thread Library (20% of project score)](https://sites.cs.ucsb.edu/~chris/teaching/cs170/projects/proj2.html)。

延伸閱讀: [coroutine 的歷史、現在和未來](https://blog.youxu.info/2014/12/04/coroutine/)

### 為何現在仍有 coroutine 的需求？

任務可概略分為:
* CPU 密集型
* I/O 密集型

早期伺服器為了解決並行需求，採用一個網路連線對應一個行程 (如 Apache HTTP Server，即 `httpd`)。後來 CPU 發展到多核，該架構調整為一個網路連線對應到一個執行緒，或者是事先配置的的 thread pool。

逐漸作業系統和應用程式框架提出 event loop 的開發介面，即 EventLoop + Callback 的方式，該模式存在多個變種，如: loop per thread，但共同特點都是 callback function 中處理事件。隨著軟體規模的擴展，callback 的變得更複雜，不乏有巢狀呼叫 (nested)，這對於程式開發和除錯帶來嚴重的負面影響。

[goroutine](https://tour.golang.org/concurrency/1) 的出現帶來新的改變 —— 以同步的方式處理原本非同步執行的程式碼，於是變得更直覺、程式碼易於閱讀且除錯，適合 I/O 密集型任務，這背後的機制就是 coroutine。相較於執行緒，coroutine 佔用的記憶體空間更少，且通常不需要作業系統介入，從而在高度並行的情境可帶來優異的效能表現。

## 案例探討

QEMU 內建 coroutine
* [QEMU 中的協程: qemu-coroutine](https://royhunter.github.io/2016/06/24/qemu-coroutine/)
* [include/qemu/coroutine.h](https://github.com/qemu/qemu/blob/master/include/qemu/coroutine.h)
* [include/qemu/coroutine_int.h](https://github.com/qemu/qemu/blob/master/include/qemu/coroutine_int.h)
* [util/qemu-coroutine.c](https://github.com/qemu/qemu/blob/master/util/qemu-coroutine.c)
* [util/coroutine-sigaltstack.c](https://github.com/qemu/qemu/blob/master/util/coroutine-sigaltstack.c)
* [util/coroutine-ucontext.c](https://github.com/qemu/qemu/blob/master/util/coroutine-ucontext.c)
* [tests/unit/test-coroutine.c](https://github.com/qemu/qemu/blob/master/tests/unit/test-coroutine.c)

LLVM 提供 coroutine 支援
[Coroutine](https://hackmd.io/@YLowy/HkT8-S20D)
FreeRTOS 的 [coroutine](https://www.freertos.org/kernel/coroutines.html)

- [Coroutine in Depth - Context Switch](http://jinke.me/2018-09-14-coroutine-context-switch/)
- [Fibers, Oh My!](https://graphitemaster.github.io/fibers/)
- [Doing multitasking the hard way](https://notnik.cc/posts/async/)

## 實作分析
* [coro](https://github.com/sysprog21/concurrent-programs/tree/master/coro)
* [tinync](https://github.com/sysprog21/concurrent-programs/tree/master/tinync)
* [fiber](https://github.com/sysprog21/concurrent-programs/tree/master/fiber)
* [cserv](https://github.com/sysprog21/cserv)
* [minicoro](https://github.com/edubart/minicoro)

延伸閱讀: [Evolution of the x86 context switch in Linux](https://www.maizure.org/projects/evolution_x86_context_switch_linux/)