协程(三)协程与Continuation

标签: 协程 协程 continuation | 发表时间:2011-09-06 15:00 | 作者:(author unknown) Eric
出处:http://ravenw.com/

Continuation表示一个运算在其指定位置的剩余部分。当Continuation作为语言的第一类(First-class)对象时,可用于实现多种控制结构。同样作为控制结构,First-class continuation的表达力比协程更加强大,而且有着明确定义的语义,以至于在它出现之后对协程的研究就几乎完全停止了。但后来Revisiting Coroutines中证明了完全协程与One-shot continuation的表达力是完全相同的,而且协程更容易理解和使用,在某些情况下也更加高效。

理解Continuation

Continuation是一种描述程序的控制状态的抽象,它用一个数据结构来表示一个执行到指定位置的计算过程;这个数据结构可以由程序语言访问而不是隐藏在运行时环境中。Continuation在生成之后可作为控制结构使用,在调用时会从它所表示的控制点处恢复执行。

注意Continuation所保存的控制状态中并不包括数据。关于这一点有个很有趣的“Continuation三明治”的描述:

假设你在厨房里的冰箱前面,正打算做一个三明治。这时你获取一个Continuation放进兜里。然后从冰箱拿了些火鸡和面包做了个三明治,放在了桌子上。现在调用兜里的那个Continuation,你会发现你又站在了冰箱前,正打算做个三明治。但这时桌子上已经有个三明治了,而且火鸡和面包也不见了。于是你吃掉了三明治。

Continuation以及与相关的call/cc(Call-with-current-continuation)、CPS(Continuation-passing style)这几个概念比较难理解也容易混淆,要彻底把它们搞明白还真得花一番功夫。Continuation的资料也不多,这里列出几篇中文资料供参考:

First-class continuation

Continuation这个术语很多时候也用于表示First-class continuation。这时它表示一种语言构造,使语言可以在任意点保存执行状态并且在之后的某个点返回。这里与协程做比较的正是First-class continuation(或者说是call/cc机制),而不是Continuation结构或CPS编程风格。

调用call/cc时,会把当前Continuation打包成一个第一类对象。然后这个捕获的Continuation被传给call/cc的参数——此参数必须是带一个参数的过程。如果在这个过程中没有调用Continuation就返回了,则返回值作为call/cc的值。如果在其中调用了Continuation并传给它一个值,则这个值立即返回到call/cc处。

基于First-class continuation很容易实现完全协程,主要思路是在切换协程时保存当前Continuation并调用目标协程的Continuation。以下是由Marc De Scheemaecker基于Ruby call/cc实现的完全对称协程:

 1 class Coroutine
 2     def initialize(&block)
 3         # Creates a coroutine. The associated block does not run yet.
 4         @started = false
 5         @finished = false
 6         @block = Proc::new {
 7             callcc{|@cc|}
 8             block.call
 9             @finished = true
10             @started = false
11         }
12     end
13 
14     def start
15         # Starts the block. It's an error to call this method on a coroutine
16         # that has already been started.
17         raise "Block already started" if @started
18 
19         @started = true
20         @block.call
21     end
22 
23     def switch(coroutine)
24         # Switches context to another coroutine. You need to call this method
25         # on the current coroutine.
26         switch = true
27 
28         if not coroutine.finished? then
29             callcc{|@cc|}
30 
31             if switch then
32                 switch = false
33 
34                 if coroutine.running? then
35                     coroutine.continuation.call
36                 else
37                     coroutine.start
38                 end
39             end
40         end
41     end
42 
43     def running?
44         # Returns true if the associated block is started and has not yet
45         # finished
46         @started and not @finished
47     end
48 
49     def finished?
50         # Returns true if the associated block is finished
51         @finished
52     end
53 
54     def continuation
55         # Returns the associated continuation object
56         @cc
57     end
58 end

One-shot continuation

所谓One-shot continuation,即只允许调用一次的Continuation。标准的Continuation是允许多次调用(Multi-shot)的,但是很难高效地实现这样的Continuation,因为每次调用之前都必然要生成一个副本,而且在绝大多数情况下Continuation都只会被调用一次,受此启发Bruggeman et al.提出了One-shot continuation的概念和控制符call/1cc。One-shot continuation几乎可以所有应用中替换标准Continuation(包括上面协程的实现)。多次调用One-shot continuation会引发错误,无论是隐式调用(从传给call/1cc的过程中返回)还是显式调用(直接调用由call/1cc创建的Continuation)。

前面提到过完全协程与One-shot continuation的表达力是相同的,证明方式便是它们可以相互实现。从对称协程的视角来看,捕获一个One-shot continuation相当于新建一个协程并把控制传递给它。调用时相当于把控制返回给创建者。这种相似性使得基于对称协程可以很简洁地实现call/1cc。

下面是Revisiting Coroutines中使用Lua实现One-shot continuation的代码,首先实现一个完全对称协程:

 1 coro = {}
 2 coro.main = function() end
 3 coro.current = coro.main
 4 
 5 -- function to create a new coroutine
 6 function coro.create(f)
 7     local co = function(val)
 8         f(val)
 9         error("coroutine ended")
10     end
11     return coroutine.wrap(co)
12 end
13 
14 -- function to transfer control to a coroutine
15 function coro.transfer(co, val)
16     if coro.current == coro.main then
17         return coroutine.yield(co, val)
18     end
19 
20     -- dispatching loop
21     while true do
22         coro.current = co
23         if co == coro.main then
24             return val
25         end
26         co, val = co(val)
27     end
28 end

然后是call/1cc:

 1 function call1cc(f)
 2     -- save the continuation "creator"
 3     local ccoro = coro.current
 4     -- invoking the continuation transfers control
 5     -- back to its creator
 6     local cont = function(val)
 7         if ccoro == nil then
 8             error("one shot continuation called twice")
 9         end
10         coro.transfer(ccoro, val)
11     end
12     -- when a continuation is captured,
13     -- a new coroutine is created and dispatched
14     local val
15     val = coro.transfer(coro.create(function()
16         local v = f(cont)
17         cont(v)
18     end))
19     -- when control is transfered back, the continuation
20     -- was "shot" and must be invalidated
21     ccoro = nil
22     -- the value passed to the continuation
23     -- is the return value of call1/cc
24     return val
25 end

效率问题

可以看到,Continuation可以实现协程,同时协程也可以实现One-shot continuation,但这两种相反实现的效率并不相同。

在Bruggeman et al.描述的One-shot continuation实现中,控制栈由栈段(Stack segment)组成的链表表示,整个控制栈被构造成栈帧(Stack of frame)或活动记录(Activation record)。捕获Continuation时,当前栈段被保存到Continuation中,然后分配一个新的栈段。调用Continuation时,丢弃当前栈段,控制返回到之前保存的栈段。

创建一个协程同样包括分配一个单独的栈,但挂起和恢复协程的代价只比标准的函数调用略高。

使用协程实现One-shot continuation时,创建一个单独的协程——即栈“段”——就足以表示一个Continuation。因此,通过协程实现的One-shot continuation与直接实现效率几乎相同。而以Continuation实现协程时,通常每次协程挂起时都需要捕获一个新的Continuation。这导致每次控制转换都需要重新分配一个栈段,相比直接实现的协程效率要大大降低并且需要更多内存。

这里有一篇Lua、LuaJIT Coroutine和Ruby Fiber的切换效率对比,我猜测大概就是因为Ruby是在call/cc之上实现的Fiber。

相关 [协程 协程 continuation] 推荐:

协程(三)协程与Continuation

- Eric - Indie 之路
Continuation表示一个运算在其指定位置的剩余部分. 当Continuation作为语言的第一类(First-class)对象时,可用于实现多种控制结构. 同样作为控制结构,First-class continuation的表达力比协程更加强大,而且有着明确定义的语义,以至于在它出现之后对协程的研究就几乎完全停止了.

协程(二):协程的应用

- vento - python.cn(jobs, news)
# 感谢“书香”推荐: @shuxiang29. 上一篇中对协程的概念做出了解释和澄清. 总的来说,完全协程才算得上是真正意义上的协程,其它如生成器等只是部分实现了协程概念的非完全协程,我们之后主要讨论完全协程. 协程本质是一种控制抽象,它的价值在于可以简洁优雅地实现一些控制行为. 在协程中,控制可以从当前执行上下文跳转到程序的其它位置,并且可以在之后的任意时刻恢复当前执行上下文,控制从跳出点处继续执行.

java 协程 实现 Akka

- - zzm
Akka是开源的,可以通过Apache 2许可获得. 可以从 http://akka.io/downloads/ 下载.         对并发/并行程序的简单的、高级别的抽象.         异步、非阻塞、高性能的事件驱动编程模型.         非常轻量的事件驱动处理(1G内存可容纳约270万个actors).

关于线程Thread、协程Coroutine、生成器Generator、yield资料

- tangsty - 我的宝贝孙秀楠 ﹣C++, Lua, 大连,程序员
关于Green Thread(绿色环保线程)、Native Thread,以及线程的一些普及问题,下面这个presentation最为翔实. 另外毫无疑问要看看维基百科上的这一条 http://en.wikipedia.org/wiki/Thread_%28computer_science%29. 这一篇教程可以帮助你了解Lua协程的基本用法http://lua-users.org/wiki/CoroutinesTutorial .

协程与Swoole的原理,相关应用以及适用场景等

- - 编程学习网
协程(Coroutine)也叫用户态线程,其通过协作而不是抢占来进行切换. 相对于进程或者线程,协程所有的操作都可以在用户态完成,创建和切换的消耗更低. 协程是进程的补充,或者是互补关系.  要理解是什么是“用户态的线程”,必然就要先理解什么是“内核态的线程”. 内核态的线程是由操作系统来进行调度的,在切换线程上下文时,要先保存上一个线程的上下文,然后执行下一个线程,当条件满足时,切换回上一个线程,并恢复上下文.

Openresty流量复制/AB测试/协程_jinnianshilongnian的专栏-CSDN博客

- -
在实际开发中经常涉及到项目的升级,而该升级不能简单的上线就完事了,需要验证该升级是否兼容老的上线,因此可能需要并行运行两个项目一段时间进行数据比对和校验,待没问题后再进行上线. 这其实就需要进行流量复制,把流量复制到其他服务器上,一种方式是使用如. tcpcopy引流;另外我们还可以使用nginx的HttpLuaModule模块中的ngx.location.capture_multi进行并发执行来模拟复制.