跳转到内容

协程

本页使用了标题或全文手工转换
维基百科，自由的百科全书

协程（英語：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]、Smalltalk和Modula-2。更新近的例子是Ruby、Lua、Julia和Go。

由于续体可被用来实现协程，支持续体的编程语言也非常容易就支持协程。

实现

直到2003年，很多最流行的编程语言，包括C语言和它的后继者，都未在语言内或其标准库中直接支持协程。这在很大程度上是受基于堆栈的子例程实现的限制。C++的Boost.Context[24]库是个例外，它是Boost C++库的一部分，它在POSIX、Mac OS X和Windows上支持多种CPU架构的上下文切换。可以在Boost.Context之上建造协程。

在协程是某种机制的最自然的实现方式，却不能获得可用协程的情况下，典型的解决方法是使用闭包，它是具有状态变量（静态变量，常为布尔标志值）的子例程，基于状态变量来在调用之间维持内部状态，并转移控制权至正确地点。基于这些状态变量的值，在代码中的条件语句导致在后续调用时有着不同代码路径的执行。另一种典型的解决方法实现一个显式状态机，采用某种形式的庞大而复杂的switch语句（英语：Switch statement）或goto语句特别是“计算goto”。这种实现被认为难于理解和维护，更是想要有协程支持的动机。

在当今的主流编程环境里，协程的合适的替代者是线程和适用范围较小的纤程。线程提供了用来管理“同时”执行的代码段实时协作交互的功能，在支持C语言的环境中，线程是广泛有效的，POSIX.1c（IEEE Std 1003.1c-1995）规定了被称为pthreads的一个标准线程API，它在类Unix系统中被普遍实现。线程被很好地实现、文档化和支持，很多程序员对其也比较熟悉。但是，线程包括了许多强大和复杂的功能用以解决大量困难的问题，这导致了困难的学习曲线，当任务仅需要协程就可完成时，使用线程似乎就是用力过猛了。GNU Pth可被视为类Unix系统上用户级线程的代表。

C

C标准库里有“非局部跳转”函数setjmp/longjmp，它们分别保存和恢复：栈指针、程序计数器、被调用者保存的寄存器和ABI要求的任何其他内部状态。在C99标准中，跳转到已经用return或longjmp终止的函数是未定义的[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）. 

参见

延伸阅读

外部链接


检索自“https://zh.wikipedia.org/w/index.php?title=协程&oldid=83302784”