本頁使用了標題或全文手工轉換

協程

維基百科，自由的百科全書
跳至導覽 跳至搜尋
編程范型

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

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

同子例程的比較[編輯]

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

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

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

示例[編輯]

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

var q := 新建队列

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

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

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

同線程的比較[編輯]

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

線程是協作式多任務的輕量級線程，本質上描述了同協程一樣的概念。其區別，如果一定要說有的話，是協程是語言層級的構造，可看作一種形式的控制流，而線程是系統層級的構造，可看作恰巧沒有並行運行的線程。這兩個概念誰有優先權是爭議性的：線程可看作為協程的一種實現[6]，也可看作實現協程的基底[7]。

生成器[編輯]

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

儘管如此，仍可以在生成器設施之上實現協程，這需要通過頂層的分派器（dispatcher）例程（實質上是彈跳床（英語：trampoline (computing)））的援助，它顯式的把控制權傳遞給由生成器傳回的令牌（token）所標識出的後代生成器： 

var q := 建立新队列

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

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

subroutine 分派器
    var d := 创建新字典(generator → iterator)
    d[生产者] := start 生产者
    d[消费者] := start 消费者
    var 当前 := 生产者
    loop
        call 当前
        当前 := next d[当前]

call 分派器

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

同尾調用互遞歸的比較[編輯]

參見：互遞歸和尾調用

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

協程之常見用例[編輯]

協程有助於實現：

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

支持協程的編程語言[編輯]

協程起源於一種匯編語言方法，但有一些高級編程語言支持它。早期的例子包括Simula[8]、Smalltalk和Modula-2。更新近的例子是Ruby、Lua、Julia和Go。

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

實現[編輯]

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

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

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

C語言實現[編輯]

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

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

由於缺乏直接的語言支持，很多作者寫了自己的含藏上述技術細節的協程庫，以Russ Cox的libtask協程庫為代表[30]，它自稱能夠「寫事件驅動程序而沒有麻煩的事件」，並可用在FreeBSD、Linux、Mac OS X和SunOS之上。知名的實現還有：libpcl[31]、lthread[32]、libCoroutine[33]、libconcurrency[34]、libcoro[35]、ribs2[36]、libdill[37]、libaco[38]、libco[39]等等。

此外人們做了用C語言的子例程和宏實現協程的大量嘗試，並取得了不同程度的成功。Simon Tatham作出的貢獻是這一方法的很好示例[40]，它受到了達夫設備利用swtich語句「掉落」特性的啟發，並且是Protothreads和類似實現的基礎[41]。這種方法的確可以提高代碼段的可寫性、可讀性，但可維護性是存在爭議的[42]。這種不為每個協程維護獨立的棧幀的實現方式主要缺點是，局部變量在經過從函數yield之後是不保存的，控制權只能從頂層例程yield[43]。

Python實現[編輯]

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

import asyncio
import random

async def produce(queue, n):
    for item in range(n):
        # 生产一个项目，使用sleep模拟I/O操作
        print('producing item {} ->'.format(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('consuming item {} <-'.format(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[52]，它是Perl5中的一種協程實現，使用C作為底層，所以具有良好的執行性能，而且可以配合AnyEvent共同使用，極大的彌補了Perl在線程上劣勢。

Scheme實現[編輯]

Scheme提供了對續體的完全支持，實現協程是很輕易的，只需維護一個續體的隊列。在續體條目中有使用續體將協程實現為獨立線程的一個用例[53]。

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. ^ A Fiber Class. [2019-11-22]. （原始內容存檔於2017-10-23）. 
  7. ^ 7.0 7.1 Implementing Coroutines for .NET by Wrapping the Unmanaged Fiber API. 2005-09-16 [2019-11-26]. （原始內容存檔於2020-06-13）. Ajai Shankar, MSDN Magazine
  8. ^ 8.0 8.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.     
  9. ^ 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. 
  10. ^ Watt, Stephen M. A Technique for Generic Iteration and Its Optimization (PDF). The University of Western Ontario, Department of Computer Science. [2012-08-08]. Some authors use the term iterator, and others the term generator. Some make subtle distinctions between the two. 
  11. ^ What is the difference between an Iterator and a Generator?. [2019-11-29]. （原始內容存檔於2020-06-25）. 
  12. ^ Coroutine: Type-safe coroutines using lightweight session types. [2019-11-24]. （原始內容存檔於2013-01-20）. 
  13. ^ Co-routines in Haskell. [2019-11-24]. （原始內容存檔於2020-01-09）. 
  14. ^ The Coroutines Module (coroutines.hhf). HLA Standard Library Manual. [2019-11-24]. （原始內容存檔於2019-04-27）. 
  15. ^ New in JavaScript 1.7. [2019-11-24]. （原始內容存檔於2009-03-08）. 
  16. ^ Julia Manual - Control Flow - Tasks (aka Coroutines). [2019-11-24]. （原始內容存檔於2020-06-13）. 
  17. ^ What's New in Kotlin 1.1. [2019-11-24]. （原始內容存檔於2019-08-11）. 
  18. ^ Lua 5.2 Reference Manual. www.lua.org. [2019-11-24]. （原始內容存檔於2018-01-13）. 
  19. ^ Coro. [2019-11-24]. （原始內容存檔於2019-05-29）. 
  20. ^ [1]] （頁面存檔備份，存於網際網路檔案館）
  21. ^ 21.0 21.1 PEP 342 -- Coroutines via Enhanced Generators. [2019-11-21]. （原始內容存檔於2020-05-29）. 
  22. ^ 22.0 22.1 PEP 380 -- Syntax for Delegating to a Subgenerator. [2019-11-21]. （原始內容存檔於2020-06-04）. 
  23. ^ 8. Compound statements — Python 3.8.0 documentation. docs.python.org. [2019-11-24]. （原始內容存檔於2019-11-27）. 
  24. ^ Gather and/or Coroutines. 2012-12-19 [2019-11-24]. （原始內容存檔於2020-06-13）. 
  25. ^ McCartney, J. "Rethinking the Computer Music Programming Language: SuperCollider". Computer Music Journal, 26(4):61-68. MIT Press, 2002.
  26. ^ Boost.Context（頁面存檔備份，存於網際網路檔案館）
  27. ^ ISO/IEC 9899:1999 （頁面存檔備份，存於網際網路檔案館）, 2005, 7.13.2.1:2 and footnote 211
  28. ^ getcontext(3) - Linux manual page. man7.org. [2019-11-21]. （原始內容存檔於2019-11-27）. 
  29. ^ 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) [seepth_mctx.c for details]. 
    Portable multithreading: the signal stack trick for user-space thread creation. ATEC '00 Proceedings of the annual conference on USENIX Annual Technical Conference. 2000-06-18: 20–20 [2019-11-27]. （原始內容存檔於2019-10-31） –透過ACM Digital Library. 
  30. ^ libtask. [2019-11-21]. （原始內容存檔於2019-11-15）. 
  31. ^ Portable Coroutine Library （頁面存檔備份，存於網際網路檔案館） - C library using POSIX/SUSv3 facilities
  32. ^ lthread: a multicore enabled coroutine library written in C （頁面存檔備份，存於網際網路檔案館） - lthread is a multicore/multithread coroutine library written in C
  33. ^ libcoroutine: A portable coroutine implementation. [2019-11-21]. （原始內容存檔於2019-11-12）.  for FreeBSD, Linux, OS X PPC and x86, SunOS, Symbian and others
  34. ^ libconcurrency - A scalable concurrency library for C.  a simple C library for portable stack-switching coroutines
  35. ^ libcoro: C-library that implements coroutines (cooperative multitasking) in a portable fashion. [2019-11-21]. （原始內容存檔於2019-12-02）.  used as the basis for the Coro perl module.
  36. ^ RIBS (Robust Infrastructure for Backend Systems) version 2. August 13, 2019 [2019-11-21]. （原始內容存檔於2020-04-22） –透過GitHub. 
  37. ^ libdill: Structured Concurrency for C. libdill.org. [2019-11-21]. （原始內容存檔於2019-12-02）. 
  38. ^ 极速的轻量级C异步协程库: hnes/libaco. October 21, 2019 [2018-10-16]. （原始內容存檔於2018-11-29） –透過GitHub. 
  39. ^ libco: cooperative multithreading library written in C89.. code.byuu.org. [失效連結]
  40. ^ Simon Tatham. Coroutines in C. 2000 [2019-11-22]. （原始內容存檔於2019-11-09）. 
  41. ^ Stackless coroutine implementation in C and C++: jsseldenthuis/coroutine. March 18, 2019 [2019-11-26]. （原始內容存檔於2020-06-13） –透過GitHub. 
  42. ^ Simon Tatham. Coroutines in C. 2000 [2019-11-22]. （原始內容存檔於2019-11-09）. 這一技巧破壞了書本中的每一個編碼標準……［但是］任何試圖犧牲算法明晰來確保語法清晰的編碼標準都應該被重寫。如果你的老闆因為你使用了這些技巧而解僱你，在保安把你從大樓里拖出來的同時不斷地告訴他們我的這句話。 
  43. ^ Coroutines in C – brainwagon. [2019-11-22]. （原始內容存檔於2019-07-23）. 
  44. ^ PEP 3156 -- Asynchronous IO Support Rebooted: the "asyncio" Module. [2019-11-21]. （原始內容存檔於2019-11-14）. 
  45. ^ Generator-based Coroutines. [2020-10-29]. （原始內容存檔於2018-12-31）. 
  46. ^ PEP 492 -- Coroutines with async and await syntax. [2019-11-21]. （原始內容存檔於2019-01-05）. 
  47. ^ What’s New In Python 3.7. [2019-11-21]. （原始內容存檔於2019-11-28）. 
  48. ^ Eventlet. [2019-11-21]. （原始內容存檔於2019-11-15）. 
  49. ^ Greenlet. [2019-11-21]. （原始內容存檔於2019-08-25）. 
  50. ^ gevent. [2020-10-02]. （原始內容存檔於2020-09-16）. 
  51. ^ Stackless Python. [2019-11-21]. （原始內容存檔於2015-12-08）. 
  52. ^ Coro. [2013-06-01]. （原始內容存檔於2013-06-01）. 
  53. ^ Haynes, C. T., Friedman, D. P., and Wand, M. 1984. 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.

參見[編輯]

延伸閱讀[編輯]

外部連結[編輯]

取自「https://zh.wikipedia.org/w/index.php?title=协程&oldid=76034886」