协程 [wiki]

  1. 云栖社区>
  2. 博客>
  3. 正文

协程 [wiki]

lin.tao 2016-04-10 00:42:00 浏览1255
展开阅读全文

协程

维基百科,自由的百科全书

子例程一样,协程也是一种程序组件。相对子例程而言,协程更为一般和灵活,但在实践中使用没有子例程那样广泛。协程源自SimulaModula-2语言,但也有其他语言支持。协程更适合于用来实现彼此熟悉的程序组件,如合作式多任务迭代器无限列表管道

协程最初在1963年被提出。[1]

简单的对比和示例

由于协程不如子例程那样被普遍所知,最好对它们作个比较。

子例程的起始处是惟一的入口点,一旦退出即完成了子例程的执行,子例程的一个实例只会返回一次。

协程可以通过yield来调用其它协程。通过yield方式转移执行权的协程之间不是调用者与被调用者的关系,而是彼此对称、平等的。

协程的起始处是第一个入口点,在协程里,返回点之后是接下来的入口点。子例程的生命期遵循后进先出(最后一个被调用的子例程最先返回);相反,协程的生命期完全由他们的使用的需要决定。

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

var q := new queue

生产者协程

   loop
       while q is not full
           create some new items
           add the items to q
       yield to consume

消费者协程

   loop
       while q is not empty
           remove some items from q
           use the items
       yield to produce

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

详细比较

因为相对于子例程,协程可以有多个入口和出口点,可以用协程来实现任何的子例程。事实上,正如Knuth所说:“子例程是协程的特例。”

每当子例程被调用时,执行从被调用子例程的起始处开始;然而,接下来的每次协程被调用时,从协程返回(或yield)的位置接着执行。

因为子例程只返回一次,要返回多个值就要通过集合的形式。这在有些语言,如Forth里很方便;而其他语言,如C,只允许单一的返回值,所以就需要引用一个集合。相反地,因为协程可以返回多次,返回多个值只需要在后继的协程调用中返回附加的值即可。在后继调用中返回附加值的协程常被称为产生器。

子例程容易实现于堆栈之上,因为子例程将调用的其他子例程作为下级。相反地,协程对等地调用其他协程,最好的实现是用continuations(由有垃圾回收的堆实现)以跟踪控制流程。

协程之常见用例[编辑]

协程有助于实现:

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

支持协程的编程语言

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

协程的替代者和实现

到2003年,很多最流行的编程语言,包括C和他的后继,都未在语言内或其标准库中直接支持协程。(这在很大程度上是受基于堆栈的子例程实现的限制)。

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

在当今的主流编程环境里,线程是协程的合适的替代者,线程提供了用来管理“同时”执行的代码段实时交互的功能。因为要解决大量困难的问题,线程包括了许多强大和复杂的功能并导致了困难的学习曲线。当需要的只是一个协程时,使用线程就过于技巧了。然而——不像其他的替代者——在支持C的环境中,线程也是广泛有效的,对很多程序员也比较熟悉,并被很好地实现,文档化和支持。在POSIX里有一个标准的良定义的线程实现pthread.

用C的实现

C标准库里的函数setjmp和longjmp可以用来实现一种协程。不幸的是,正如harbison and Steele所述,“setjmp和longjmp的相当地难以实现,程序员要对使用它作最少的假设。”这意味着如果没有留意Harbison和Steele的警告而在某个环境下使用了setjmp和longjmp,在其他环境下可能不能正常工作。更糟糕的是,错误的实现并非个例。

人们作了大量的尝试,在C里用子例程和实现协程,这些尝试有不同程度的成功之处。Simon Tatham的贡献(见下文)是这一方法的很好示例。他自己注解是对这一方法的限制做了很好的评价。这种方法的确可以提高代码段的可写性,可读性,可维护性还是存在争议的。用Titham的话说:“当然,这一技巧破坏了这本书的每一个编码标准……[但是]任何试图牺牲算法明晰来确保语法清晰的编码标准都应该被重写。如果你的老板因为因为你使用了这些技巧而解雇你,在保安把你从大楼里拖出来的同时不断地告诉他们上面那句话。

著名的实现:

Python 实现

Perl 实现

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

Tcl 实现

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

参考

  • 高德纳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.
  1. ^ Conway, Melvin E. Design of a Separable Transition-Diagram Compiler. Communications of the ACM (New York, NY, USA: Association for Computing Machinery). July 1963, 6 (7): 396–408.doi:10.1145/366663.366704. 编辑

另见



其他参考:

作者:阿猫
链接:https://www.zhihu.com/question/20511233/answer/24260355
来源:知乎
著作权归作者所有,转载请联系作者获得授权。

没有啥复杂的东西,考虑清楚需求,就可以很自然的衍生出这些解决方案。
  • 一开始大家想要同一时间执行那么三五个程序,大家能一块跑一跑。特别是UI什么的,别一上计算量比较大的玩意就跟死机一样。于是就有了并发,从程序员的角度可以看成是多个独立的逻辑流。内部可以是多cpu并行,也可以是单cpu时间分片,能快速的切换逻辑流,看起来像是大家一块跑的就行。
  • 但是一块跑就有问题了。我计算到一半,刚把多次方程解到最后一步,你突然插进来,我的中间状态咋办,我用来储存的内存被你覆盖了咋办?所以跑在一个cpu里面的并发都需要处理上下文切换的问题。进程就是这样抽象出来个一个概念,搭配虚拟内存、进程表之类的东西,用来管理独立的程序运行、切换。
  • 后来一电脑上有了好几个cpu,好咧,大家都别闲着,一人跑一进程。就是所谓的并行
  • 因为程序的使用涉及大量的计算机资源配置,把这活随意的交给用户程序,非常容易让整个系统分分钟被搞跪,资源分配也很难做到相对的公平。所以核心的操作需要陷入内核(kernel),切换到操作系统,让老大帮你来做。
  • 有的时候碰着I/O访问,阻塞了后面所有的计算。空着也是空着,老大就直接把CPU切换到其他进程,让人家先用着。当然除了I\O阻塞,还有时钟阻塞等等。一开始大家都这样弄,后来发现不成,太慢了。为啥呀,一切换进程得反复进入内核,置换掉一大堆状态。进程数一高,大部分系统资源就被进程切换给吃掉了。后来搞出线程的概念,大致意思就是,这个地方阻塞了,但我还有其他地方的逻辑流可以计算,这些逻辑流是共享一个地址空间的,不用特别麻烦的切换页表、刷新TLB,只要把寄存器刷新一遍就行,能比切换进程开销少点。
  • 如果连时钟阻塞、 线程切换这些功能我们都不需要了,自己在进程里面写一个逻辑流调度的东西。那么我们即可以利用到并发优势,又可以避免反复系统调用,还有进程切换造成的开销,分分钟给你上几千个逻辑流不费力。这就是用户态线程
  • 从上面可以看到,实现一个用户态线程有两个必须要处理的问题:一是碰着阻塞式I\O会导致整个进程被挂起;二是由于缺乏时钟阻塞,进程需要自己拥有调度线程的能力。如果一种实现使得每个线程需要自己通过调用某个方法,主动交出控制权。那么我们就称这种用户态线程是协作式的,即是协程

本质上协程就是用户空间下的线程。

网友评论

登录后评论
0/500
评论
lin.tao
+ 关注