本页使用了标题或全文手工转换

协程

维基百科，自由的百科全书
跳到导航 跳到搜索

协程是计算机程序的一类组件，推广了协作式多任务的子程序，允许执行被挂起与被恢复。相对子例程而言，协程更为一般和灵活，但在实践中使用没有子例程那样广泛。协程更适合于用来实现彼此熟悉的程序组件，如协作式多任务、异常处理、事件循环、迭代器、无限列表和管道。

根据高德纳的说法, 马尔文·康威于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即可实现这种协作关系。

同线程的比较[编辑]

协程非常类似于线程。但是协程是协作式多任务的，而线程典型是抢占式多任务的。这意味着协程提供并发性而非并行性。协程超过线程的好处是它们可以用于硬性实时的语境（在协程之间的切换不需要涉及任何系统调用或任何阻塞（英语：Blocking (computing)）调用），这里不需要用来守卫关键区块的同步性原语（primitive）比如互斥锁、信号量等，并且不需要来自操作系统的支持。有可能以一种对调用代码透明的方式，使用抢占式调度的线程实现协程，但是会失去某些利益（特别是对硬性实时操作的适合性和相对廉价的相互之间切换）。

纤程是协作式多任务的轻量级线程，本质上描述了同协程一样的概念。其区别，如果一定要说有的话，是协程是语言层级的构造，可看作一种形式的控制流，而纤程是系统层级的构造，可看作恰巧没有并行运行的线程。这两个概念谁有优先权是争议性的：纤程可看作为协程的一种实现[6]，也可看作实现协程的基底[7]。

生成器[编辑]

生成器，也叫作“半协程”[8]，是协程的子集。尽管二者都可以yield多次，挂起（suspend）自身的执行，并允许在多个入口点重新进入，但它们特别差异在于，协程有能力控制在它让位之后哪个协程立即接续它来执行，而生成器不能，它只能把控制权转交给调用生成器的调用者[9]。在生成器中的yield语句不指定要跳转到的协程，而是向父例程传递返回值。尽管如此，仍可以在生成器设施之上实现协程，这需要通过顶层的派遣器（dispatcher）例程（实质上是trampoline（英语：trampoline (computing)））的援助，它显式的把控制权传递给由生成器传回的令牌（token）所标识出的子生成器。

在不同作者和语言之间，术语“生成器”和“迭代器”的用法有着微妙的差异[10]。有人说所有生成器都是迭代器[11]，生成器看起来像函数而表现得像迭代器。在Python中，生成器是迭代器构造子：它是返回迭代器的函数。

同尾调用互递归的比较[编辑]

参见：互递归和尾调用

使用协程用于状态机或并发运行类似于使用经由尾调用的互递归，在二者情况下控制权都变更给一组例程中的另一个不同例程。但是，协程更灵活并且一般而言更有效率。因为协程是yield而非return返回，接着恢复执行而非在起点重新开始，它们有能力保持状态，包括变量（同于闭包）和执行点二者，并且yield不限于位于尾部位置；互递归子例程必须要么使用共享变量，要么把状态作为参数传递。进一步的说，每一次子例程的互递归调用都需要一个新的栈帧（除非实现了尾调用消去），而在协程之间传递控制权使用现存上下文并可简单地通过跳转来实现。

协程之常见用例[编辑]

协程有助于实现：

  • 状态机：在一个子例程里实现状态机，这里状态由该过程当前的出口/入口点确定；这可以产生可读性更高的代码。
  • 角色模型：并发的角色模型，例如计算机游戏。每个角色有自己的过程（这又在逻辑上分离了代码），但他们自愿地向顺序执行各角色过程的中央调度器交出控制（这是合作式多任务的一种形式）。
  • 生成器：可用于流，特别是输入/输出流，和对数据结构的通用遍历。
  • 通信顺序进程：这里每个子进程都是协程。通道（channel）输入/输出和阻塞操作会yield协程，并由调度器在有完成事件时对其解除阻塞（unblock）。可作为替代的方式是，每个子进程可以是在数据管道中位于其后的子进程的父进程（或是位于其前者之父，这种情况下此模式可以表达为嵌套的生成器）。

支持协程的编程语言[编辑]

协程起源于一种汇编语言方法，但有一些高级编程语言支持它。早期的例子包括Simula[12]、Smalltalk和Modula-2。更新近的例子是Ruby、Lua、Julia和Go。

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

实现[编辑]

到2003年，很多最流行的编程语言，包括C语言和它的后继者，都未在语言内或其标准库中直接支持协程。（这在很大程度上是受基于堆栈的子例程实现的限制）。C++的Boost.Context库是个例外，它是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终止的函数是未定义的[24]，但是大多数longjmp实现在跳转时不专门销毁调用栈中的局部变量，在被后续的函数调用等覆写之前跳转回来恢复时仍是原样，这允许在实现协程时谨慎的用到它们。

POSIX.1-2001/SUSv3和此前的SUSv2进一步提供了操纵上下文（英语：Context (computing)）的强力设施：setcontext、getcontext、makecontext和swapcontext（英语：setcontext），可方便地用来实现协程，但是由于makecontext的参数定义不符合C99标准要求，这些函数在POSIX.1-2004中被废弃，并在POSIX.1-2008中被删除[25]。POSIX.1-2001/SUSv3和此前的SUSv2定义了sigaltstack，可用来在不能获得makecontext的情况下稍微迂回的实现协程[26]。极简实现不采用有关的标准API函数进行上下文交换，而是写一小块内联汇编只对换栈指针和程序计数器故而速度明显的要更快。

由于缺乏直接的语言支持，很多作者写了自己的含藏上述技术细节的协程库，以Russ Cox的libtask协程库为代表，它自称能够“写事件驱动程序而没有麻烦的事件”，并可用在FreeBSD、Linux、Mac OS X和SunOS之上。知名的实现还有：libpcl[27]、lthread[28]、libCoroutine[29]、libconcurrency[30]、libcoro[31]、ribs2[32]、libdill[33]、libaco[34]、libco[35]等等。

此外人们做了用C语言的子例程和宏实现协程的大量尝试，并获取了不同程度的成功。Simon Tatham作出的贡献是这一方法的很好示例[36]，它受到了达夫设备利用swtich语句“掉落”特性的启发，并且是Protothreads和类似实现的基础[37]。这种方法的确可以提高代码段的可写性、可读性，但可维护性是存在争议的[38]。这种不为每个协程维护独立的栈帧的实现方式主要缺点是，局部变量在经过从函数yield之后是不保存的，控制权只能从顶层例程yield[39]。

Python实现[编辑]

Python 2.5基于扩展的生成器实现对类似协程功能的更好支持[40]。Python 3.3通过支持委托给子生成器增进了这个能力[41]。Python 3.4介入了综合性的异步I/O框架准化[42]，包括了利用子生成器委托的协程。Python 3.5通过async/await语法介入了对协程的显式支持[43]。从Python 3.7开始async/await成为保留关键字[44]。

Perl实现[编辑]

  • Coro - Coro是Perl5中的一种协程实现，它使用C作为底层，所以具有良好的执行性能，而且可以配合AnyEvent共同使用，极大的弥补了Perl在线程上劣势。

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. 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. ISSN 0001-0782. doi:10.1145/366663.366704 –通过ACM Digital Library. 
  3. ^ call-with-current-continuation for C programmers. http://community.schemewiki.org/. 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. doi:10.1145/947955.1083808. （原始内容存档于January 17, 1999）. 6. Symmetry is a complexity reducing concept (co-routines include sub-routines); seek it everywhere 
  6. ^ A Fiber Class
  7. ^ 7.0 7.1 Implementing Coroutines for .NET by Wrapping the Unmanaged Fiber API. 2005-09-16. Ajai Shankar, MSDN Magazine
  8. ^ Anthony Ralston. Encyclopedia of computer science. Nature Pub. Group. 2000 [11 May 2013]. ISBN 978-1-56159-248-7. 
  9. ^ See for example The Python Language Reference "https://docs.python.org/reference/expressions.html#yieldexpr 5.2.10. Yield expressions]":
    "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]. （原始内容 (PDF)存档于2006-09-16）. 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?
  12. ^ Dahl, O.-J. and Hoare, C.A.R. (ed). Hierarchical Program Structures. Structured Programming. London, UK: Academic Press. 1972: 175–220. ISBN 978-0122005503. 
  13. ^ Coroutine: Type-safe coroutines using lightweight session types. 
  14. ^ Co-routines in Haskell. 
  15. ^ The Coroutines Module (coroutines.hhf). HLA Standard Library Manual. 
  16. ^ New in JavaScript 1.7. 
  17. ^ Julia Manual - Control Flow - Tasks (aka Coroutines). 
  18. ^ What's New in Kotlin 1.1. 
  19. ^ Lua 5.2 Reference Manual. www.lua.org. 
  20. ^ Python async/await Tutorial. Stack Abuse. December 17, 2015. 
  21. ^ 8. Compound statements — Python 3.8.0 documentation. docs.python.org. 
  22. ^ Gather and/or Coroutines. 2012-12-19. 
  23. ^ McCartney, J. "Rethinking the Computer Music Programming Language: SuperCollider". Computer Music Journal, 26(4):61-68. MIT Press, 2002.
  24. ^ ISO/IEC 9899:1999, 2005, 7.13.2.1:2 and footnote 211
  25. ^ getcontext(3) - Linux manual page. man7.org. 
  26. ^ GNU Pth - IMPLEMENTATION NOTES. 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 –通过ACM Digital Library. 
  27. ^ Portable Coroutine Library - C library using POSIX/SUSv3 facilities
  28. ^ lthread: a multicore enabled coroutine library written in C - lthread is a multicore/multithread coroutine library written in C
  29. ^ libcoroutine: A portable coroutine implementation.  for FreeBSD, Linux, OS X PPC and x86, SunOS, Symbian and others
  30. ^ libconcurrency - A scalable concurrency library for C.  a simple C library for portable stack-switching coroutines
  31. ^ libcoro: C-library that implements coroutines (cooperative multitasking) in a portable fashion.  used as the basis for the Coro perl module.
  32. ^ RIBS (Robust Infrastructure for Backend Systems) version 2. August 13, 2019 –通过GitHub. 
  33. ^ libdill: Structured Concurrency for C. libdill.org. 
  34. ^ 极速的轻量级C异步协程库: hnes/libaco. October 21, 2019 –通过GitHub. 
  35. ^ libco: cooperative multithreading library written in C89.. code.byuu.org. 
  36. ^ Simon Tatham. Coroutines in C. 2000. 
  37. ^ Stackless coroutine implementation in C and C++: jsseldenthuis/coroutine. March 18, 2019 –通过GitHub. 
  38. ^ Simon Tatham. Coroutines in C. 2000. 这一技巧破坏了书本中的每一个编码标准……［但是］任何试图牺牲算法明晰来确保语法清晰的编码标准都应该被重写。如果你的老板因为你使用了这些技巧而解雇你，在保安把你从大楼里拖出来的同时不断地告诉他们我的这句话。 
  39. ^ Coroutines in C – brainwagon. 
  40. ^ PEP 342
  41. ^ PEP 380
  42. ^ PEP 3156
  43. ^ PEP 0492
  44. ^ What’s New In Python 3.7

参见[编辑]

延伸阅读[编辑]

外部链接[编辑]

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