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

协程

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

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

根据高德纳的说法, 马尔文·康威于1958年发明了术语“coroutine”并用于构建汇编程序[1],关于协程最初的出版解说在1963年发表[2]

同子例程的比较[编辑]

协程可以通过yield(取其“让步”之义而非“出产”)来调用其它协程,接下来的每次协程被调用时,从协程上次yield返回的位置接着执行,通过yield方式转移执行权的协程之间不是调用者与被调用者的关系,而是彼此对称、平等的。由于协程不如子例程那样被普遍所知,下面对它们作简要比较:

  • 子例程可以调用其他子例程,调用者等待被调用者结束后继续执行。子例程的生命期遵循后进先出,即最后一个被调用的子例程最先结束返回。协程的生命期完全由他们的使用的需要决定。
  • 子例程的起始处是惟一的入口点,每当子例程被调用时,执行从被调用子例程的起始处开始;一旦退出即完成了子例程的执行,子例程的一个实例只会返回一次。相对于子例程,协程可以有多个入口和出口点,协程的起始处是第一个入口点,在协程里,每个返回出口点都是接下来执行时的入口点。
  • 因为子例程只返回一次,要返回多个值就要通过集合的形式。这在有些语言,如Forth里很方便;而其他语言,如C语言,只允许单一的返回值,所以就需要引用一个集合。协程可以返回多次,返回多个值只需要在后继的协程调用中返回添加的值即可。在后继调用中返回添加的值的协程常被称为生成器
  • 子例程容易实现于堆栈之上,因为子例程将调用的其他子例程作为下级。协程对等地调用其他协程,最好的实现是用续体(由有垃圾回收的堆实现)以跟踪控制流程。可以用协程来实现任何的子例程[註 1]

示例[编辑]

这里是一个简单的例子证明协程的实用性。假设你有一个生产者-消费者的关系,这里一个协程生产产品并将它们加入队列,另一个协程从队列中取出产品并使用它。为了提高效率,你想一次增加或删除多个产品。伪码表示如下:

var q := 新建队列

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

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

每个协程在用yield命令向另一个协程交出控制时都尽可能做了更多的工作。放弃控制使得另一个例程从这个例程停止的地方开始,但因为现在队列被修改了所以他可以做更多事情。尽管这个例子常用来介绍多线程,实际没有必要用多线程实现这种动态:yield语句可以通过由一个协程向另一个协程直接分支的方式实现。

生成器[编辑]

生成器,也叫作“半协程”[3],是协程的子集。尽管二者都可以yield多次,挂起(suspend)自身的执行,并允许在多个入口点重新进入,但它们特别差异在于,协程有能力控制在它让位之后哪个协程立即接续它来执行,而生成器不能,它只能把控制权转交给调用生成器的调用者[4]。就是说,由于生成器主要用于简化写迭代器的工作,在生成器中的yield语句不指定要跳转到的协程,而是向父例程传递返回值。

尽管如此,仍可以在生成器设施之上实现协程,这需要通过顶层的派遣器(dispatcher)例程(实质上是trampoline英语trampoline (computing))的援助,它显式的把控制权传递给由生成器传回的令牌(token)所标识出的子生成器。

协程之常见用例[编辑]

协程有助于实现:

  • 状态机:在一个子例程里实现状态机,这里状态由该过程当前的出口/入口点确定;这可以产生可读性更高的代码。
  • 角色模型:并行的角色模型,例如计算机游戏。每个角色有自己的过程(这又在逻辑上分离了代码),但他们自愿地向顺序执行各角色过程的中央调度器交出控制(这是合作式多任务的一种形式)。
  • 生成器:它有助于输入/输出和对数据结构的通用遍历。

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

协程最早见于SimulaModula-2语言,但也有其他语言支持。

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

实现[编辑]

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

有些情况下,使用协程的实现策略显得很自然,但是此环境下却不能使用协程。典型的解决方法是创建一个子例程,它用布尔标志的集合以及其他状态变量在调用之间维护内部状态。代码中基于这些状态变量的值的条件语句产生出不同的执行路径及后继的函数调用。另一种典型的解决方案是用一个庞大而复杂的switch语句实现一个显式状态机。这种实现理解和维护起来都很困难。

在当今的主流编程环境里,协程的合适的替代者是线程和适用范围较小的纤程。线程提供了用来管理“同时”执行的代码段实时交互的功能,在支持C语言的环境中,线程是广泛有效的,POSIX.1c规定了一个标准线程APIpthreads普遍实现于类Unix系统中。线程对很多程序员也比较熟悉,并被很好地实现、文档化和支持。因为要解决大量困难的问题,线程包括了许多强大和复杂的功能并导致了困难的学习曲线。当任务仅需要协程就可完成时,使用线程似乎就是过度杀伤了。GNU可移植线程库可被视为类Unix系统纤程的代表,有人尝试过用Windows的纤程机制实现协程[5]

C语言实现[编辑]

C标准库里的“非局部跳转”函数setjmp和longjmp可以用来实现一种协程,但有一定的难度[註 2]POSIX.1-2001/SUSv3和此前的SUSv2提供了可用来实现协程的设施如:getcontext、setcontext、makecontext和swapcontext英语setcontext,但是这些函数在POSIX.1-2004被废弃,并在POSIX.1-2008中被删除[6]。人们实现了很多C协程库,以Russ Cox的libtask协程库为代表,它自称能够“写事件驱动程序而没有麻烦的事件”,并可用在FreeBSD、Linux、Mac OS X和SunOS之上。知名的实现还有:libpcl[7]、lthread[8]、libCoroutine[9]、libconcurrency[10]、libcoro[11]、ribs2[12]、libdill[13]libaco[14]、libco[15]等等。

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

Python实现[编辑]

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

Perl实现[编辑]

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

Tcl实现[编辑]

从 Tcl 8.6 开始,Tcl 核心内置协程支持,成为了继事件循环、线程后的另一种内置的强大功能。

引用[编辑]

  1. ^ Knuth, Donald Ervin. Fundamental Algorithms. 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. 
  2. ^ Melvin E. Conway. Design of a separable transition-diagram compiler. Communications of the ACM. 1963-07-01, 6 (7): 396–408 [2018-04-02]. ISSN 0001-0782. doi:10.1145/366663.366704. 
  3. ^ Anthony Ralston. Encyclopedia of computer science. Nature Pub. Group. 2000 [11 May 2013]. ISBN 978-1-56159-248-7. 
  4. ^ 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."
  5. ^ Implementing Coroutines for .NET by Wrapping the Unmanaged Fiber API 互联网档案馆存檔,存档日期2008-09-07., Ajai Shankar, MSDN Magazine
  6. ^ getcontext(3) - Linux manual page. man7.org. 
  7. ^ Portable Coroutine Library - C library using POSIX/SUSv3 facilities
  8. ^ lthread: a multicore enabled coroutine library written in C - lthread is a multicore/multithread coroutine library written in C
  9. ^ libcoroutine: A portable coroutine implementation.  for FreeBSD, Linux, OS X PPC and x86, SunOS, Symbian and others
  10. ^ libconcurrency - A scalable concurrency library for C.  a simple C library for portable stack-switching coroutines
  11. ^ libcoro: C-library that implements coroutines (cooperative multitasking) in a portable fashion.  used as the basis for the Coro perl module.
  12. ^ RIBS (Robust Infrastructure for Backend Systems) version 2. August 13, 2019 –通过GitHub. 
  13. ^ libdill: Structured Concurrency for C. libdill.org. 
  14. ^ 极速的轻量级C异步协程库: hnes/libaco. October 21, 2019 –通过GitHub. 
  15. ^ libco: cooperative multithreading library written in C89.. code.byuu.org. 
  16. ^ Simon Tatham. Coroutines in C. 2000. 
  17. ^ Coroutines in C – brainwagon. 
  18. ^ PEP 342
  19. ^ PEP 380
  20. ^ PEP 3156
  21. ^ PEP 0492
  22. ^ What’s New In Python 3.7

注释[编辑]

  1. ^ Knuth所说:“子例程是协程的特例。”
  2. ^ 正如HarbisonSteele所述,“setjmp和longjmp的相当地难以实现,程序员要对使用它作最少的假设。”这意味着如果没有留意Harbison和Steele的警告而在某个环境下使用了setjmp和longjmp,在其他环境下可能不能正常工作。更糟糕的是,错误的实现并非个例。
  3. ^ Simon Tatham自己的注解是对这一方法的限制做了很好的评价。用他的话说:“这一技巧破坏了这本书的每一个编码标准……[但是]任何试图牺牲算法明晰来确保语法清晰的编码标准都应该被重写。如果你的老板因为因为你使用了这些技巧而解雇你,在保安把你从大楼里拖出来的同时不断地告诉他们上面那句话。”

参考[编辑]

  • 高德纳. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 1.4.2: Coroutines, pp.193–200.
  • C: A Reference Manual. Samuel P. Harbison and Guy L. Steele, Jr. Third edition; Prentice-Hall, 1991, ISBN 0-13-110933-2.

另见[编辑]