Coroutine技术学习研究

举报
Jet Ding 发表于 2020/09/28 18:12:40 2020/09/28
【摘要】 oroutines是一种计算机程序组件,它通过允许暂停执行和恢复执行来实现非抢先性多任务的子程序。Coroutines非常适合实现热门的程序任务组件,如合作任务、异常、事件循环、迭代器、无限列表和管道。

Coroutines是一种计算机程序组件,它通过允许暂停执行和恢复执行来实现非抢先性多任务的子程序。Coroutines非常适合实现热门的程序任务组件,如合作任务、异常、事件循环、迭代器、无限列表和管道。

根据Donald Knuth的说法,Melvin Conway1958年创造了coroutine这个术语,当时他将其应用于汇编程序的构建。

1      与子程序的比较

子程序是coroutine的特例,当子程序被调用时,执行开始,子程序一旦退出,就结束了;一个子程序的实例只返回一次,在调用之间不保持状态。与此相反,coroutine可以通过调用其他coroutine来退出,这些coroutine以后可能会返回到原coroutine中被调用的点;从coroutine的角度来看,它不是退出,而是调用另一个coroutine,因此,一个coroutine实例保持状态,在调用之间变化;一个给定的coroutine可以同时有多个实例。通过对另一个coroutine "yielding"来调用另一个coroutine和简单地调用另一个coroutine(那么,也会回到原点)的区别在于,两个相互屈服的coroutine之间不是调用者-被调用者的关系,而是对称的关系。

任何子程序都可以翻译成一个不调用yieldcoroutine

下面是一个简单的例子,说明例程如何工作。假设你有一个消费者-生产者的关系,其中一个例程创建项目并将它们添加到队列中,另一个例程从队列中删除项目并使用它们。为了提高效率,您希望同时添加和删除多个项目。代码可能是这样的:

var q := new queue

 

coroutine produce

    loop

        while q is not full

            create some new items

            add the items to q

        yield to consume

 

coroutine consume

    loop

        while q is not empty

            remove some items from q

            use the items

        yield to produce

 

在使用yield命令将控制权交给另一个coroutine之前,队列已经被完全填满或清空。进一步的coroutine调用就在yield之后开始,在外层coroutine循环中。

虽然这个例子经常被用来介绍多线程,但并不需要为此而使用两个线程:yield语句可以通过直接从一个例程跳转到另一个例程来实现。

2      Thread的比较

Coroutine与线程非常相似。然而,coroutine是合作式多任务的,而线程通常是先发制人的多任务。这意味着,coroutine提供并发性,但不提供并行性。与线程相比,coroutine的优势在于它们可以在硬实时环境中使用(在coroutine之间的切换不需要涉及任何系统调用或任何阻塞调用),不需要同步基元(如mutexessemaphores等)来保护关键部分,也不需要操作系统的支持。

可以使用预先调度的线程来实现coroutine,这种方式对调用代码是透明的,但会失去一些优势(特别是适合硬实时操作和相对便宜的切换)。

3      与生成器的比较

生成器,又称semicoroutine,是coroutine的一个子集。具体来说,虽然两者都可以多次yield,暂停执行,并允许在多个入口点重新进入,但它们的不同之处在于coroutine可以控制在yield后立即在哪里继续执行,而生成器则不能,而是将控制权转回生成器的调用者手中。 也就是说,由于生成器主要用于简化迭代器的编写,所以生成器中的屈服语句并不指定跳转到哪个coroutine,而是将一个值传回父例程。 

然而,仍然可以在生成器设施之上实现coroutines,借助一个顶层调度例程(本质上是一个蹦床),将控制权显式地传递给由生成器传回的令牌识别的子生成器。

var q := new queue

generator produce

    loop

        while q is not full

            create some new items

            add the items to q

        yield consume

generator consume

    loop

        while q is not empty

            remove some items from q

            use the items

        yield produce

subroutine dispatcher

    var d := new dictionary(generator → iterator)

    d[produce] := start produce

    d[consume] := start consume

    var current := produce

    loop

        current := next d[current]

 

一些支持生成器但没有本地生成器的语言(例如2.5之前的Python)coroutines的实现使用了类似的模型。

4      与相互递归的比较

在状态机或并发中使用coroutine类似于使用尾部调用的相互递归,因为在这两种情况下,控制权都会改变到一组例程中的不同的一个。然而,coroutine更灵活,通常更有效率。由于coroutineyield而不是返回,然后恢复执行而不是从头开始,所以它们能够保持状态,包括变量(如closure)和执行点,而且yield不限于在尾部位置;相互递归的子例程必须使用共享变量或传递状态作为参数。此外,子程序的每一次互递归调用都需要一个新的堆栈框架(除非实现尾部调用消除),而coroutine之间传递控制权则使用现有的上下文,只需通过跳转即可实现。

5      常见用途

Coroutine可以用来实现以下功能:

1.         一个子程序内的状态机,状态由程序的当前进入/退出点决定;与使用goto相比,这可以使代码更易读,也可以通过尾部调用的相互递归实现。

2.         并发的角色模型,例如在视频游戏中。每个角色都有自己的程序(这又在逻辑上把代码分开了),但他们自愿把控制权交给中央调度器,由中央调度器依次执行(这是一种合作多任务的形式)。

3.         生成器,这些对于流--特别是输入/输出--和数据结构的通用遍历是有用的。

4.         通信顺序进程,其中每个子进程是一个coroutine。通道输入/输出和阻塞操作产生coroutine,调度器在完成事件上解除阻塞。另外,在数据管道中,每个子进程可以是它后面的子进程的父进程(或前面的子进程,在这种情况下,模式可以表示为嵌套生成器)。

5.         反向通信,通常用于数学软件中,其中一个程序如求解器、积分评估器......需要使用过程进行计算,如评估方程或积分。

6      具有本地支持的编程语言

Coroutines起源于一种汇编语言方法,但在一些高级编程语言中也得到了支持,早期的例子包括SimulaSmalltalkModula-2。早期的例子包括SimulaSmalltalkModula-2。最近的例子有RubyLuaJuliaGo

 

1.         Aikido

2.         AngelScript

3.         Ballerina

4.         BCPL

5.         Pascal (Borland Turbo Pascal 7.0 with uThreads module)

6.         BETA

7.         BLISS

8.         C++ (Since C++20)

9.         C# (Since 2.0)

10.     ChucK

11.     CLU

12.     D

13.     Dynamic C

14.     Erlang

15.     F#

16.     Factor

17.     GameMonkey Script

18.     GDScript (Godot's scripting language)

19.     Go

20.     Haskell

21.     High Level Assembly

22.     Icon

23.     Io

24.     JavaScript (since 1.7, standardized in ECMAScript 6) ECMAScript 2017 also includes await support.

25.     Julia

26.     Kotlin (since 1.1)

27.     Limbo

28.     Lua[15]

29.     Lucid

30.     µC++

31.     MiniD

32.     Modula-2

33.     Nemerle

34.     Perl 5 (using the Coro module)

35.     PHP (with HipHop, native since PHP 5.5)

36.     Picolisp

37.     Prolog

38.     Python (since 2.5, with improved support since 3.3 and with explicit syntax since 3.5)

39.     Raku

40.     Ruby

41.     Sather

42.     Scheme

43.     Self

44.     Simula 67

45.     Smalltalk

46.     Squirrel

47.     Stackless Python

48.     SuperCollider

49.     Tcl (since 8.6)

50.     urbiscript

 

由于连续性可以用来实现coroutine,所以支持连续性的编程语言也可以很容易地支持coroutine

7      实现情况

截止到2003年,许多最流行的编程语言,包括C语言及其衍生语言,在语言或其标准库中都没有对coroutine的直接支持。这在很大程度上是由于基于堆栈的子程序实现的限制)。一个例外是C++Boost.Context,它是boost库的一部分,它支持ARMMIPSPowerPCSPARCPOSIXMac OS XWindows上的x86的上下文交换。Coroutine可以建立在Boost.Context基础上。

在一些情况下,coroutine是程序机制的自然需求实现,但很多时候不好用,典型的反应是使用Closure--一个带有状态变量(静态变量,通常是布尔标志)的子程序,以在调用之间保持内部状态,并将控制转移到正确的点。代码内部的条件导致在连续调用时,根据状态变量的值执行不同的代码路径。另一种典型的应对措施是以大型复杂的switch语句的形式或通过goto语句,特别是计算的goto来实现一个显式状态机。这种实现被认为是难以理解和维护的,也是支持coroutine的一个动机。

线程,以及在较小程度上的fiber,是目前主流编程环境中coroutine的替代方案。线程提供了管理同时执行的代码片段的实时合作交互的设施。线程在支持C语言的环境中广泛存在(许多其他现代语言也原生支持),为许多程序员所熟悉,而且通常都有良好的实现、良好的文档和良好的支持。然而,由于它们解决的是一个庞大而困难的问题,它们包括许多强大而复杂的设施,并且具有相应的困难学习曲线。因此,当只需要一个coroutine时,使用线程可能是矫枉过正。

线程和coroutine之间的一个重要区别是,线程通常是预先调度的,而coroutine则不是。因为线程可以在任何时刻重新调度,并且可以并发执行,所以使用线程的程序必须小心锁定。相反,由于coroutine只能在程序中的特定点重新调度,并且不并发执行,使用coroutine的程序通常可以完全避免锁定。这个特性也被引用为事件驱动或异步编程的一个好处)。

由于fibers是合作调度的,因此它们为实现上述coroutines提供了一个理想的基础,然而,与线程的支持相比,系统对fibers的支持往往是缺乏的。

7.1    C中的实现

为了实现通用的coroutine,必须获得第二个调用栈,这是C语言不直接支持的功能。一个可靠的(尽管是特定于平台的)方法是在初始创建coroutine的过程中使用少量的内联汇编来显式操作栈指针。这是Tom Duff在讨论其与Protothreads使用的方法的相对优点时推荐的方法。在提供POSIX sigaltstack系统调用的平台上,可以通过从信号处理程序内调用一个跳板函数来获得第二个调用栈,在可移植的C语言中实现同样的目标,但代价是一些额外的复杂性。符合POSIXSingle Unix Specification (SUSv3)C库提供了getcontextsetcontextmakecontextswapcontext等例程,但这些函数在POSIX 1.2008中被宣布过时。

一旦用上述方法之一获得了第二个调用栈,就可以使用标准C库中的setjmplongjmp函数来实现coroutine之间的切换。这些函数分别保存和恢复堆栈指针、程序计数器、调用保存的寄存器以及ABI所要求的任何其他内部状态,这样,在屈服后返回到一个coroutine,就会恢复从函数调用返回时的所有状态。极简主义的实现,不依赖setjmplongjmp函数,可以通过一个小的内联程序块来实现同样的结果,这个内联程序块只交换堆栈指针和程序计数器,并(可以敞开了使用) clobbers所有其他寄存器。这可以显著地提高速度,因为setjmplongjmp必须根据ABI保守地存储所有可能正在使用的寄存器,而clobber方法只允许编译器存储(通过溢出到堆栈),它知道实际正在使用的寄存器。

 由于缺乏直接的语言支持,很多作者都为coroutine编写了自己的库,隐藏了上述细节。Russ Coxlibtask库就是这种类型的一个很好的例子。如果本机C库提供了上下文函数,它就使用这些函数;否则,它就为ARMPowerPCSparcx86提供自己的实现。其他值得注意的实现包括libpcl coro lthread libCoroutinelibconcurrency libcororibs2 libdill libaco libco 

除了上述一般方法外,还有一些人尝试用子程序和宏的组合来近似C语言中的coroutinesSimon Tatham的贡献基于Duff的装置,是该流派的一个显著的例子,也是Protothreads和类似实现的基础。除了Duff的反对意见,Tatham自己的评论也对这种方法的局限性进行了坦率的评价。"据我所知,这是在严肃的生产代码中见过的最糟糕的C语言黑客行为。这种近似方法的主要缺点是,由于没有为每个coroutine维护一个单独的堆栈框架,局部变量不能在函数的各次输出中得到保存,不可能对函数有多个入口,而且只能从顶层例程中yield

7.2    C++中的实现

 

1.         C++ coroutines TS (Technical Specification),是C++语言扩展的标准,用于类似coroutine行为的无堆栈子集,正在开发中。Visual C++Clang已经支持std::experimental命名空间中的主要部分。

2.         Boost.Coroutine--Oliver Kowalke创建,是boost1.53版本以来官方发布的可移植的coroutine库,它依赖于Boost.Context,支持ARMMIPSPowerPCSPARCX86POSIXMac OS XWindows

3.         Boost.Coroutine2--也是由Oliver Kowalke创建的,是boost 1.59版本以来的一个现代化的便携式coroutine库。它利用了C++11的特性,但删除了对对称coroutine的支持。

4.         Mordor--2010年,Mozy开源了一个实现coroutineC++库,重点是利用它们将异步I/O抽象成一个更熟悉的顺序模型。

5.         CO2 - 基于C++预处理器技巧的无堆栈的coroutine,提供了等待/收益模拟。

6.         ScummVM - ScummVM项目基于Simon Tatham的文章实现了一个轻量级的无栈coroutine版本。

7.         tonbit::coroutine - C++11.h非对称coroutine通过ucontext / fiber实现。

8.         Coroutines20175月登陆Clanglibc++的实现正在进行中 

9.         elle by Docker

 

7.3    C#的实现

 

1.         MindTouch Dream - MindTouch Dream REST框架提供了一个基于C# 2.0迭代器模式的coroutines实现。

2.         Caliburn - WPFCaliburn屏幕模式框架使用C# 2.0迭代器来简化UI编程,特别是在异步场景下。

3.         Power Threading Library - Jeffrey RichterPower Threading Library实现了AsyncEnumerator,使用基于迭代器的coroutines提供简化的异步编程模型。

4.         Unity游戏引擎实现了coroutines

5.         Servelat Pieces - Yevhen BobrovServelat Pieces项目为Silverlight WCF服务提供了透明的异步,并能够异步调用任何同步方法。该项目的实现基于CaliburnCoroutines迭代器和C#迭代器块。

6.         .NET 2.0+框架现在通过迭代器模式和yield关键字提供了半coroutine(生成器)功能。

C# 5.0 提供 await 语法支持。

 

7.4    Clojure中的实现

 

Cloroutine是一个第三方库,为Clojure中的无堆栈coroutine提供支持。它以宏的形式实现,在任意var调用时静态地拆分任意代码块,并将coroutine作为有状态函数发出。

 

7.5    D中的实现

 

D实现了coroutines作为它的标准库类Fiber A生成器使得将光纤函数作为输入范围暴露出来变得微不足道,使得任何光纤与现有的范围算法兼容。

 

7.6    Java的实现

Java中的coroutine有几种实现方式。尽管有Java的抽象所带来的限制,但JVM并不排除这种可能性,使用的一般方法有四种,但有两种方法打破了符合标准的JVM之间的字节码的可移植性。

 

1.         修改后的JVM。可以构建一个打了补丁的JVM来更原生地支持coroutines。达芬奇JVM已经创建了补丁。

2.         修改后的字节码。Coroutine功能可以通过重写常规的Java字节码实现,无论是在飞行中还是在编译时。工具包包括JavaflowJava CoroutinesCoroutines

3.         特定平台的JNI机制。这些使用在操作系统或C库中实现的JNI方法来向JVM提供功能。

4.         线程抽象。使用线程实现的Coroutine库可能是重量级的,不过性能会根据JVM的线程实现而变化。

 

7.7    Kotlin的实现

 

Kotlin实现了coroutines作为第一方库的一部分。

 

7.8    JavaScript中的实现

 

1.         node-fibers

a)        Fibjs - fibjs是一个建立在ChromeV8 JavaScript引擎上的JavaScript运行时,fibjs使用fibers-switch、同步风格和非阻塞I/O模型来构建可扩展系统。

2.         ECMAScript 2015年起,通过 "生成器"yield表达式提供了无堆栈的coroutine功能。

 

7.9    Mono中实现

 

Mono通用语言运行时支持连续性,可以从中构建coroutine

 

7.10      .NET框架中以fibers形式实现

 

.NET Framework 2.0的开发过程中,微软扩展了通用语言运行时(CLR)托管API的设计,以处理基于光纤的调度,并着眼于将其用于SQL服务器的光纤模式。在发布之前,由于时间限制,取消了对任务切换钩子ICLRTask::SwitchOut的支持。因此,在.NET框架中,使用光纤API来切换任务目前不是一个可行的选择。

 

7.11      PHP中的实现

 

1.         Amphp

 

7.12      Python中的实现

 

1.         Python 2.5 基于扩展的生成器,实现了对类似于coroutine的功能更好的支持 (PEP 342)

2.         Python 3.3 改进了这一能力,支持委托给子生成器 (PEP 380)

3.         Python 3.4引入了PEP 3156中标准化的全面异步I/O框架,其中包括利用子生成器授权的coroutines

4.         Python 3.5 引入了对使用 async/await 语法的 coroutine 的显式支持 (PEP 0492)

5.          Python 3.7 起,async/await 成为保留关键字。

6.         Eventlet

7.         Greenlet

8.         gevent

9.         stackless python

 

7.13      Ruby中的实现

 

1.         Ruby 1.9支持原生的coroutines,这些coroutines被实现为fiber,即半coroutines

2.         Marc De Scheemaecker的实现

3.         Ruby 2.5和更高版本的Ruby支持原生的coroutines,这些coroutinesfiber的形式实现。

4.         Thomas W Branson的实现

 

7.14      Perl中的实现

 

1.         Coro

 

Coroutines在所有的Raku后端都是原生实现的。

 

7.15      Rust中的实现

 

Rust有一个提供coroutines的库,生成器是一个实验性的功能,可以在夜间的rust中使用,它提供了一个带有async/awaitcoroutines的实现。

 

7.16      Scala中的实现

 

Scala Coroutines[48] Scala的一个coroutine实现。这个实现是一个库级扩展,它依靠Scala宏系统将程序的部分静态地转换为coroutine对象。因此,这个实现不需要在JVM中进行修改,所以它在不同的JVM之间是完全可移植的,并且可以与其他的Scala后端一起工作,比如编译成JavaScriptScala.js

 

Scala Coroutine依赖于coroutine宏,它将一个普通的代码块转化为coroutine定义。这样的coroutine定义可以通过调用操作来调用,从而实例化一个coroutine框架。可以用resume方法恢复coroutine框架,恢复coroutine主体的执行,直到达到yieldval关键字,暂停coroutine框架。Scala coroutine还公开了一个快照方法,它可以有效地复制coroutine.[50]ECOOP 2018上出现了带快照的Scala coroutine的详细描述,以及它们的形式模型。

 

7.17      Swift中的实现

 

SwiftCoroutine - 适用于iOSmacOSLinuxSwift coroutine库。

Smalltalk的实现

因为在大多数Smalltalk环境中,执行堆栈是一流的公民,所以无需额外的库或虚拟机支持就可以实现coroutine

 

7.18      Scheme中的实现

 

由于Scheme提供了对连续性的完全支持,实现coroutine几乎是微不足道的,只需要维护一个连续性的队列。

 

7.19      工具命令语言(Tcl)中的实现

 

8.6版本开始,工具命令语言支持核心语言中的coroutine

 

7.20      Vala中的实现

 

Vala实现了对coroutine的本地支持。它们被设计为与Gtk主循环一起使用,但如果注意确保在做至少一个yield之前不需要调用结束回调,也可以单独使用。

 

7.21      汇编语言中的实现

 

依赖于机器的汇编语言往往提供了直接执行coroutine的方法。例如,在PDP-11系列微型计算机的汇编语言MACRO-11中,"经典的 "coroutine切换是由 "JSR PC,@(SP)+"指令实现的,它跳转到从堆栈中弹出的地址,并将当前(即下一个)指令地址推到堆栈中。在VAXen上(在Macro-32中),类似的指令是 "JSB @(SP)+"。甚至在Motorola 6809上也有 "JSR [,S++]"指令;注意 "++",因为从堆栈中弹出了2个字节(地址)。这条指令在(标准) "显示器 "辅助09中用得很多。

 

8      参考

 

https://en.wikipedia.org/wiki/Async/await

https://en.wikipedia.org/wiki/Generator_(computer_programming)

https://en.wikipedia.org/wiki/Coroutine

https://en.wikipedia.org/wiki/Protothreads

 


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。