協程(英語:coroutine)是計算機程序的一類組件,推廣了協作式多任務子例程,允許執行被掛起與被恢復。相對子例程而言,協程更為一般和靈活,但在實踐中使用沒有子例程那樣廣泛。協程更適合於用來實現彼此熟悉的程序組件,如協作式多任務異常處理事件循環迭代器無限列表管道

根據高德納的說法,馬爾文·康威於1958年發明了術語「coroutine」並用於構建匯編程序[1] ,關於協程的最初解說在1963年發表[2]

同子例程的比較

協程可以通過yield(取其「退讓」之義而非「產生」)來調用其它協程,接下來的每次協程被調用時,從協程上次yield返回的位置接着執行,通過yield方式轉移執行權的協程之間不是調用者與被調用者的關係,而是彼此對稱、平等的。由於協程不如子例程那樣被普遍所知,下面對它們作簡要比較:

  • 子例程可以調用其他子例程,調用者等待被調用者結束後繼續執行,故而子例程的生命期遵循後進先出,即最後一個被調用的子例程最先結束返回。協程的生命期完全由對它們的使用需要來決定。
  • 子例程的起始處是惟一的入口點,每當子例程被調用時,執行都從被調用子例程的起始處開始。協程可以有多個入口點,協程的起始處是第一個入口點,每個yield返回出口點都是再次被調用執行時的入口點。
  • 子例程只在結束時一次性的返回全部結果值。協程可以在yield時不調用其他協程,而是每次返回一部份的結果值,這種協程常稱為生成器迭代器
  • 現代的指令集架構通常提供對調用棧的指令支持,便於實現可遞歸調用的子例程。在以Scheme為代表的提供續體的語言環境下[3],恰好可用此控制狀態抽象表示來實現協程。

子例程可以看作是特定狀況的協程[4],任何子例程都可轉寫為不調用yield的協程[5]

偽碼示意

這裡是一個簡單的例子證明協程的實用性。假設這樣一種生產者-消費者的關係,一個協程生產產品並將它們加入隊列,另一個協程從隊列中取出產品並消費它們。偽碼表示如下:

var q := new 队列

coroutine 生产者
    loop
        while q 不满载
            建立某些新产品
            向 q 增加这些产品 
        yield 消费者

coroutine 消费者
    loop
        while q 不空载
            从 q 移除某些产品
            使用这些产品
        yield 生产者

隊列用來存放產品的空間有限,同時制約生產者和消費者:為了提高效率,生產者協程要在一次執行中儘量向隊列多增加產品,然後再放棄控制使得消費者協程開始運行;同樣消費者協程也要在一次執行中儘量從隊列多取出產品,從而倒出更多的存放產品空間,然後再放棄控制使得生產者協程開始運行。儘管這個例子常用來介紹多線程,實際上簡單明了的使用協程的yield即可實現這種協作關係。

同線程的比較

協程非常類似於線程。但是協程是協作式多任務的,而典型的線程是內核級搶占式多任務的。這意味着協程提供並發性而非並行性。協程超過線程的好處是它們可以用於硬性實時的語境(在協程之間的切換不需要涉及任何系統調用或任何阻塞調用),這裡不需要用來守衛關鍵區段的同步性原語(primitive)比如互斥鎖、信號量等,並且不需要來自操作系統的支持。有可能以一種對調用代碼透明的方式,使用搶占式調度的線程實現協程,但是會失去某些利益(特別是對硬性實時操作的適合性和相對廉價的相互之間切換)。

用戶級線程協作式多任務的輕量級線程,本質上描述了同協程一樣的概念。其區別,如果一定要說有的話,是協程是語言層級的構造,可看作一種形式的控制流程,而線程是系統層級的構造。

生成器

生成器,也叫作「半協程」[6],是協程的子集。儘管二者都可以yield多次,暫停(suspend)自身的執行,並允許在多個入口點重新進入,但它們特別差異在於,協程有能力控制在它讓位之後哪個協程立即接續它來執行,而生成器不能,它只能把控制權轉交給調用生成器的調用者[7]。在生成器中的yield語句不指定要跳轉到的協程,而是向父例程傳遞返回值。

儘管如此,仍可以在生成器設施之上實現協程,這需要通過頂層的分派器(dispatcher)例程(實質上是彈跳床英語trampoline (computing))的援助,它顯式的把控制權傳遞給由生成器傳回的記號/令牌(token)所標定的另一個生成器:

var q := new 队列

generator 生产者
    loop
        while q 不满载
            建立某些新产品
            向 q 增加这些产品
        yield 消费者

generator 消费者
    loop
        while q 不空载
            从 q 移除某些产品
            使用这些产品
        yield 生产者

subroutine 分派器
    var d :=  new 字典(生成器 → 迭代器)
    d[生产者] := start 生产者
    d[消费者] := start 消费者
    var 当前 := 生产者
    loop
        call 当前
        当前 := next d[当前]

call 分派器

在不同作者和語言之間,術語「生成器」和「迭代器」的用法有着微妙的差異[8]。有人說所有生成器都是迭代器[9],生成器看起來像函數而表現得像迭代器。在Python中,生成器是迭代器構造子:它是返回迭代器的函數。

同尾調用互遞歸的比較

使用協程用於狀態機或並發運行類似於使用經由尾調用互遞歸,在二者情況下控制權都變更給一組例程中的另一個不同例程。但是,協程更靈活並且一般而言更有效率。因為協程是yield而非return返回,接着恢復執行而非在起點重新開始,它們有能力保持狀態,包括變量(同於閉包)和執行點二者,並且yield不限於位於尾部位置;互遞歸子例程必須要麼使用共享變量,要麼把狀態作為參數傳遞。進一步的說,每一次子例程的互遞歸調用都需要一個新的棧幀(除非實現了尾調用消去),而在協程之間傳遞控制權使用現存上下文並可簡單地通過跳轉來實現。

協程之常見用例

協程有助於實現:

  • 狀態機:在單一子例程里實現狀態機,這裡狀態由該過程當前的出口/入口點確定;這可以產生可讀性更高的代碼。
  • 演員模型並發的演員模型,例如計算機遊戲。每個演員有自己的過程(這又在邏輯上分離了代碼),但他們自願地向順序執行各演員過程的中央調度器交出控制(這是合作式多任務的一種形式)。
  • 生成器:可用於串流,特別是輸入/輸出串流,和對數據結構的通用遍歷。
  • 通信順序進程:這裡每個子進程都是協程。通道輸入/輸出和阻塞操作會yield協程,並由調度器在有完成事件時對其解除阻塞(unblock)。可作為替代的方式是,每個子進程可以是在數據管道中位於其後的子進程的父進程(或是位於其前者之父,這種情況下此模式可以表達為嵌套的生成器)。

支持協程的編程語言

協程起源於一種匯編語言方法,但有一些高級編程語言支持它。早期的例子包括Simula[6]SmalltalkModula-2。更新近的例子是RubyLuaJuliaGo

由於續體可被用來實現協程,支持續體的編程語言也非常容易就支持協程。

實現

直到2003年,很多最流行的編程語言,包括C語言和它的後繼者,都未在語言內或其標準庫中直接支持協程。這在很大程度上是受基於堆棧的子例程實現的限制。C++的Boost.Context[24]庫是個例外,它是Boost C++庫的一部分,它在POSIX、Mac OS X和Windows上支持多種CPU架構的上下文切換。可以在Boost.Context之上建造協程。

在協程是某種機制的最自然的實現方式,卻不能獲得可用協程的情況下,典型的解決方法是使用閉包,它是具有狀態變量(靜態變量,常為布爾標誌值)的子例程,基於狀態變量來在調用之間維持內部狀態,並轉移控制權至正確地點。基於這些狀態變量的值,在代碼中的條件語句導致在後續調用時有着不同代碼路徑的執行。另一種典型的解決方法實現一個顯式狀態機,採用某種形式的龐大而複雜的switch語句英語Switch statementgoto語句特別是「計算goto」。這種實現被認為難於理解和維護,更是想要有協程支持的動機。

在當今的主流編程環境裡,協程的合適的替代者是線程和適用範圍較小的纖程。線程提供了用來管理「同時」執行的代碼段實時協作交互的功能,在支持C語言的環境中,線程是廣泛有效的,POSIX.1c(IEEE Std 1003.1c-1995)規定了被稱為pthreads的一個標準線程API,它在類Unix系統中被普遍實現。線程被很好地實現、文檔化和支持,很多程序員對其也比較熟悉。但是,線程包括了許多強大和複雜的功能用以解決大量困難的問題,這導致了困難的學習曲線,當任務僅需要協程就可完成時,使用線程似乎就是用力過猛了。GNU Pth可被視為類Unix系統用戶級線程的代表。

C

C標準庫里有「非局部跳轉」函數setjmp/longjmp,它們分別保存和恢復:棧指針程序計數器、被調用者保存的寄存器ABI要求的任何其他內部狀態。在C99標準中,跳轉到已經用returnlongjmp終止的函數是未定義的[25],但是大多數longjmp實現在跳轉時不專門銷毀調用棧中的局部變量,在被後續的函數調用等覆寫之前跳轉回來恢復時仍是原樣,這允許在實現協程時謹慎的用到它們。

POSIX.1-2001/SUSv3進一步提供了操縱上下文英語Context (computing)的強力設施:makecontext、setcontext英語setcontext、getcontext和swapcontext,可方便地用來實現協程,但是由於makecontext的參數定義利用了具有空圓括號的函數聲明,不符合C99標準要求,這些函數在POSIX.1-2004中被廢棄,並在POSIX.1-2008/SUSv4中被刪除[26]POSIX.1-2001/SUSv3定義了sigaltstack,可用來在不能獲得makecontext的情況下稍微迂迴的實現協程[27]極簡實現不採用有關的標準API函數進行上下文交換,而是寫一小塊內聯匯編只對換棧指針和程序計數器故而速度明顯的要更快。

由於缺乏直接的語言支持,很多作者寫了自己的含藏上述技術細節的協程庫,以Russ Cox的libtask協程庫為代表[28],其目標是讓人「寫事件驅動程序而沒有麻煩的事件」,它可用各種類Unix系統上。知名的實現還有:libpcl[29]、lthread[30]、libconcurrency[31]、libcoro[32]、libdill[33]、libaco[34]、libco[35]等等。

此外人們做了只用C語言的子例程和實現協程的大量嘗試,並取得了不同程度的成功。受到了達夫設備的啟發,Simon Tatham寫出了很好的協程示範[36],它利用了swtich語句英語Switch statement「穿透」(fallthrough)特性[37],和ANSI C提供的包含了源代碼的當前行號的特殊名字__LINE__,它也是Protothreads和類似實現的基礎[38]。在這種不為每個協程維護獨立的棧幀的實現方式下,局部變量在經過從函數yield之後是不保存的,控制權只能從頂層例程yield[39]

C++

C++20介入了作為無棧函數的標準化的協程,它可以在執行中間暫停並在後來某點上恢復。協程的暫停狀態存儲在堆之上[40]。這個標準的實現正在進行中,目前G++MSVC在新近版本中完全支持了標準協程[41]

C#

C# 2.0通過迭代器模式增加了半協程(生成器)功能並增加了yield關鍵字[42][43]C# 5.0包括了await語法支持。

Go

Go擁有內建的「goroutine」概念,它是輕量級的、無關於進程並由Go運行時系統來管理。可以使用go關鍵字來啟動一個新的goroutine。每個goroutine擁有可變大小的能在需要時擴展的棧。goroutine一般使用Go的內建通道來通信[44][45][46][47]

Python

Python 2.5基於增強的生成器實現對類似協程功能的更好支持[19]。Python 3.3通過支持委託給子生成器增進了這個能力[20]。Python 3.4介入了綜合性的異步I/O框架標準化,在其中擴展了利用子生成器委託的協程[48],這個擴展在Python 3.8中被棄用[49]。Python 3.5通過async/await語法介入了對協程的顯式支持[50]。從Python 3.7開始async/await成為保留關鍵字[51]。例如:

import asyncio
import random

async def produce(queue, n):
    for item in range(n):
        # 生产一个项目,使用sleep模拟I/O操作
        print(f'producing item {item} ->') 
        await asyncio.sleep(random.random())
        # 将项目放入队列
        await queue.put(item)
    # 指示生产完毕
    await queue.put(None)

async def consume(queue):
    while True:
        # 等待来自生产者的项目
        item = await queue.get()
        if item is None:
            break
        # 消费这个项目,使用sleep模拟I/O操作
        print(f'consuming item {item} <-')
        await asyncio.sleep(random.random()) 

async def main():
    queue = asyncio.Queue()
    task1 = asyncio.create_task(produce(queue, 10))
    task2 = asyncio.create_task(consume(queue))
    await task1
    await task2

asyncio.run(main())

實現協程的第三方庫:

Perl

Coro是Perl5中的一種協程實現[56],它使用C作為底層,所以具有良好的執行性能,而且可以配合AnyEvent共同使用,極大的彌補了Perl在線程上劣勢。

Scheme

Scheme提供了對頭等續體的完全支持,實現協程是很輕易的,在續體條目中有使用頭等續體將協程實現為線程的示例[57]

Smalltalk

在大多數Smalltalk環境中,執行堆棧是頭等公民,實現協程不需要額外的庫或VM支持。

Tcl

從 Tcl 8.6 開始,Tcl 核心內置協程支持,成為了繼事件循環、線程後的另一種內置的強大功能。

引用

  1. ^ Knuth, Donald Ervin. Fundamental Algorithms (PDF). The Art of Computer Programming 1 3rd. Addison-Wesley. 1997. Section 1.4.5: History and Bibliography, pp. 229 [2019-11-23]. ISBN 978-0-201-89683-1. (原始內容存檔 (PDF)於2019-10-21). 
  2. ^ Conway, Melvin E. Design of a Separable Transition-diagram Compiler (PDF). Communications of the ACM (ACM). July 1963, 6 (7): 396–408 [2019-11-23]. ISSN 0001-0782. doi:10.1145/366663.366704. (原始內容 (PDF)存檔於2022-04-06) –透過ACM Digital Library. 
  3. ^ call-with-current-continuation for C programmers. http://community.schemewiki.org/. [2019-11-27]. (原始內容存檔於2008-12-16). If you're a C programmer then you've probably read the various introductions and tutorials on call-with-current-continuation (call/cc) and come out not much wiser about what it all really means. Here's the secret: it's setjmp/longjmp. But on no account say that to any Scheme programmers you know, it'll send them into paroxysms of rage as they tell you you don't know what you're talking about. 
  4. ^ Knuth, Donald Ervin. Fundamental Algorithms. The Art of Computer Programming 1 3rd. Addison-Wesley. 1997. Section 1.4.2: Coroutines, pp. 193–200. ISBN 978-0-201-89683-1. 
  5. ^ Perlis, Alan J. Epigrams on programming. ACM SIGPLAN Notices. September 1982, 17 (9): 7–13 [2019-11-23]. doi:10.1145/947955.1083808. (原始內容存檔於1999-01-17). 6. Symmetry is a complexity reducing concept (co-routines include sub-routines); seek it everywhere 
  6. ^ 6.0 6.1 O. -J. Dahl; C. A. R. Hoare. Hierarchical Program Structures. C. A. R. Hoare (編). Structured Programming. London, UK: Academic Press. 1972: 175–220. ISBN 978-0122005503. In SIMULA, a coroutine is represented by an object of some class, co-operating by means of resume instructions with objects of the same or another class, which are named by means of reference variables. ……
    Thus a main program may establish a coroutine relationship with an object that it has generated, using the call/detach mechanism instead of the more symmetric resume/resume mechanism. In this case, the generated object remains subordinate to the main program, and for this reason is sometimes known as a Semicoroutine. ……
    Let X and Y be objects, generated by a "master program" M. Assume that M issues a call (X), thereby invoking an "active phase" of X, terminated by a detach operation in X; and then issues a call (Y), and so forth. In this way M may act as a "supervisor" sequencing a pattern of active phases of X, Y, and other objects. Each object is a "slave", which responds with an active phase each time it is called for, whereas M has the responsibility to define the large scale pattern of the entire computation.
    Alternatively the decision making may be "decentralised", allowing an object itself to determine its dynamic successor by a resume operation. The operation resume (Y), executed by X, combines an exit out of X (by detach) and a subsequent call (Y), thereby bypassing M. Obligation to return to M is transferred to Y.
     
  7. ^ The Python Language Reference - Yield expressions. [2019-11-22]. (原始內容存檔於2012-10-26). All of this makes generator functions quite similar to coroutines; they yield multiple times, they have more than one entry point and their execution can be suspended. The only difference is that a generator function cannot control where should the execution continue after it yields; the control is always transferred to the generator's caller. 
  8. ^ Watt, Stephen M. A Technique for Generic Iteration and Its Optimization (PDF). The University of Western Ontario, Department of Computer Science. [2012-08-08]. (原始內容存檔 (PDF)於2022-05-26). Some authors use the term iterator, and others the term generator. Some make subtle distinctions between the two. 
  9. ^ What is the difference between an Iterator and a Generator?. [2019-11-29]. (原始內容存檔於2020-06-25). 
  10. ^ Coroutine: Type-safe coroutines using lightweight session types. [2019-11-24]. (原始內容存檔於2013-01-20). 
  11. ^ Co-routines in Haskell. [2019-11-24]. (原始內容存檔於2020-01-09). 
  12. ^ The Coroutines Module (coroutines.hhf). HLA Standard Library Manual. [2019-11-24]. (原始內容存檔於2019-04-27). 
  13. ^ New in JavaScript 1.7. [2019-11-24]. (原始內容存檔於2009-03-08). 
  14. ^ Julia Manual - Control Flow - Tasks (aka Coroutines). [2019-11-24]. (原始內容存檔於2020-06-13). 
  15. ^ What's New in Kotlin 1.1. [2019-11-24]. (原始內容存檔於2019-08-11). 
  16. ^ Lua 5.2 Reference Manual. www.lua.org. [2019-11-24]. (原始內容存檔於2018-01-13). 
  17. ^ Coro. [2019-11-24]. (原始內容存檔於2019-05-29). 
  18. ^ [1]] (頁面存檔備份,存於網際網路檔案館
  19. ^ 19.0 19.1 PEP 342 -- Coroutines via Enhanced Generators. [2019-11-21]. (原始內容存檔於2020-05-29). 
  20. ^ 20.0 20.1 PEP 380 -- Syntax for Delegating to a Subgenerator. [2019-11-21]. (原始內容存檔於2020-06-04). 
  21. ^ 8. Compound statements — Python 3.8.0 documentation. docs.python.org. [2019-11-24]. (原始內容存檔於2019-11-27). 
  22. ^ Gather and/or Coroutines. 2012-12-19 [2019-11-24]. (原始內容存檔於2020-06-13). 
  23. ^ McCartney, J. "Rethinking the Computer Music Programming Language: SuperCollider". Computer Music Journal, 26(4):61-68. MIT Press, 2002.
  24. ^ Boost.Context頁面存檔備份,存於網際網路檔案館
  25. ^ ISO/IEC 9899:1999頁面存檔備份,存於網際網路檔案館), 2005, 7.13.2.1:2 and footnote 211
  26. ^ makecontext, swapcontext - manipulate user contexts. [2023-09-04]. (原始內容存檔於2023-09-04). 
  27. ^ GNU Pth - IMPLEMENTATION NOTES. [2019-11-27]. (原始內容存檔於2019-12-19). Pth is very portable because it has only one part which perhaps has to be ported to new platforms (the machine context initialization). But it is written in a way which works on mostly all Unix platforms which support makecontext(2) or at least sigstack(2) or sigaltstack(2) [see pth_mctx.c for details]. 
    Portable multithreading: the signal stack trick for user-space thread creation (PDF). ATEC '00 Proceedings of the annual conference on USENIX Annual Technical Conference. 2000-06-18: 20–20 [2023-09-04]. (原始內容存檔 (PDF)於2022-01-18). 
  28. ^ Libtask: a Coroutine Library for C and Unix. [2019-11-21]. (原始內容存檔於2019-11-15). 
  29. ^ Portable Coroutine Library頁面存檔備份,存於網際網路檔案館) - C library using POSIX/SUSv3 facilities
  30. ^ lthread: a multicore enabled coroutine library written in C 頁面存檔備份,存於網際網路檔案館) - lthread is a multicore/multithread coroutine library written in C
  31. ^ libconcurrency - A lightweight concurrency library for C. [2023-08-27]. (原始內容存檔於2023-08-27). featuring symmetric coroutines as the main control flow abstraction.
  32. ^ libcoro: C-library that implements coroutines (cooperative multitasking) in a portable fashion. [2019-11-21]. (原始內容存檔於2019-12-02). 
  33. ^ libdill: Structured Concurrency for C. [2023-08-27]. (原始內容存檔於2023-11-13). 
  34. ^ 极速的轻量级C异步协程库: hnes/libaco. October 21, 2019 [2018-10-16]. (原始內容存檔於2018-11-29) –透過GitHub. 
  35. ^ libco: cooperative multithreading library written in C89. [2023-08-27]. (原始內容存檔於2023-08-27). 
  36. ^ Simon Tatham. Coroutines in C. 2000 [2019-11-22]. (原始內容存檔於2019-11-09). 
  37. ^ Brian Kernighan, Dennis Ritchie. The C Programming Language, Second Edition (PDF). Prentice Hall. 1988 [2024-01-19]. (原始內容存檔 (PDF)於2023-03-25). The switch statement is a multi-way decision that tests whether an expression matches one of a number of constant integer values, and branches accordingly. ……
    Each case is labeled by one or more integer-valued constants or constant expressions. If a case matches the expression value, execution starts at that case. ……
    Because cases serve just as labels, after the code for one case is done, execution falls through to the next unless you take explicit action to escape. ……
    Case labels and default labels are used with the switch statement (Par.A.9.4). ……
    Labels themselves do not alter the flow of control.
     
  38. ^ Stackless coroutine implementation in C and C++: jsseldenthuis/coroutine. March 18, 2019 [2019-11-26]. (原始內容存檔於2020-06-13) –透過GitHub. 
  39. ^ Coroutines in C – brainwagon. [2019-11-22]. (原始內容存檔於2019-07-23). 
  40. ^ http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4680.pdf頁面存檔備份,存於網際網路檔案館) - Technical specification for coroutines
  41. ^ https://en.cppreference.com/w/cpp/compiler_support#cpp20頁面存檔備份,存於網際網路檔案館) - Current compiler support for standard coroutines
  42. ^ Wagner, Bill. Iterators. C# documentation. Microsoft. 11 November 2021 [2024-02-10]. (原始內容存檔於2024-04-11) –透過Microsoft Learn. 
  43. ^ Wagner, Bill. The history of C#. C# documentation. Microsoft. C# version 2.0. 13 February 2023 [2024-02-10]. (原始內容存檔於2023-04-28) –透過Microsoft Learn. 
  44. ^ Goroutines - Effective Go. go.dev. [2022-11-28]. (原始內容存檔於2024-06-27) (英語). 
  45. ^ Go statements - The Go Specification. go.dev. [2022-11-28]. (原始內容存檔於2022-11-27) (英語). 
  46. ^ Goroutines - A Tour of Go. go.dev. [2022-11-28]. (原始內容存檔於2024-06-26). 
  47. ^ Frequently Asked Questions (FAQ) - The Go Programming Language. go.dev. [2024-02-10]. (原始內容存檔於2021-11-22). 
  48. ^ PEP 3156 -- Asynchronous IO Support Rebooted: the "asyncio" Module. [2019-11-21]. (原始內容存檔於2019-11-14). 
  49. ^ Generator-based Coroutines. [2020-10-29]. (原始內容存檔於2018-12-31). Support for generator-based coroutines is deprecated and is scheduled for removal in Python 3.10. 
  50. ^ PEP 492 -- Coroutines with async and await syntax. [2019-11-21]. (原始內容存檔於2019-01-05). 
  51. ^ What’s New In Python 3.7. [2019-11-21]. (原始內容存檔於2019-11-28). 
  52. ^ Eventlet. [2019-11-21]. (原始內容存檔於2019-11-15). 
  53. ^ Greenlet. [2019-11-21]. (原始內容存檔於2019-08-25). 
  54. ^ gevent. [2020-10-02]. (原始內容存檔於2020-09-16). 
  55. ^ Stackless Python. [2019-11-21]. (原始內容存檔於2015-12-08). 
  56. ^ Coro. [2013-06-01]. (原始內容存檔於2013-06-01). 
  57. ^ Haynes, C. T., Friedman, D. P., Wand, M. Continuations and coroutines. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (Austin, Texas, United States, August 06–08, 1984). LFP '84. ACM, New York, NY, 293-298. [2024-01-14]. (原始內容存檔於2024-01-14). 

參見

延伸閱讀

外部連結