这是一个创建于 1488 天前的主题，其中的信息可能已经有所发展或是发生改变。
我觉得啥关系也没有。
通过 cps 实现 call/cc->通过 call/cc 实现协程。以我的理解，cps 就是编译器层面的自动 callback，纯粹是语言层面的东西，只要能够做 callback->也就是能够 JMP->也就是移动程序指针->也就是图灵机的最基本要求，就可以实现协程，整个实现过程跟 cpu 没什么关系。
在 C/C++语言中有什么区别吗？我是按照 JS 的知识分析的。
 |
1
Mohanson 2020-12-03 21:06:59 +08:00
就拿 riscv 来说, CPU 在操作 RAS(return address stack)的时候需要做特别的处理以支持协程.
> When two different link registers (x1 and x5) are given as rs1 and rd, then the RAS is both popped and pushed to support coroutines. 另外, 协程底层是线程, 线程的实现是需要 CPU 提供底层能力支持的(需要能实现自旋锁) "我觉得啥关系也没有。" 我不要你觉得, 我要我觉得~ |
 |
2
DoctorCat 2020-12-03 21:14:45 +08:00
cps 是啥？
|
 |
3
2kCS5c0b0ITXE5k2 2020-12-03 21:41:43 +08:00
确实没啥关系。
|
 |
4
lewis89 2020-12-03 22:06:17 +08:00  2
协程是协作式的，例如我一个协程要调用 IO 了，我就通知 golang 的 IO 管控线程，我把 IO 调用 写进缓冲区 交给管控线程，然后你这个协程就放弃线程的 CPU 时间片，让其它的协程去跑起来，然后管控的线程就帮你把 IO 的请求 写进 fd-set 然后交给 epoll 调用 ，epoll 返回回来 发现你上次写的 IO 返回了，管控的线程就让你这个协程加进调度队列，等下次别的线程空出来的时候，你这个协程就可以继续跑起来干活。
传统的 Java 线程池就是 线程我要写 IO 了，然后调 IO pending 住，这个线程就去内核睡大觉了，如果线程 IO 多了，大家都得去内核睡大觉，内核睡大觉 有好几个调度队列 ，前面的人醒来干完自己的时间片才能轮到你，在内核睡大觉 还有一个麻烦就是 ring3 切换到 ring0 使用 int3 特权指令耗时 而且频繁切换 内核到应用态的上下文 很耗时，协程的话 在应用态只要把 几个寄存器跟 PC 寄存器 换到内存 然后把栈空间维持住，下次就可以实现协作式的调度，缺点是没有时间片（时间片只有内核中断向量注册后 才能响应硬件时间中断 类似的嵌入式芯片还有 watchdog 以免代码跑飞 ），有的协程跑了老半天 可能没跑到 协程退出占用的地方就把别的协程给饿死了。 |
 |
5
linux40 2020-12-03 22:11:21 +08:00
我觉得楼主的理解没啥大问题，归结到实现上就是利用了 continuation 的概念。
|
 |
6
misaka19000 2020-12-03 22:14:00 +08:00
|
 |
8
no1xsyzy 2020-12-03 22:30:58 +08:00
@lewis89 @misaka19000 为什么在解释协程是什么？喊得出 call/cc 的人需要你们教基础概念？
|
 |
9
codehz 2020-12-03 22:31:34 +08:00 via Android
你这种论证方法似乎可以套在任何一个实体上啊。。。
因为你这定义就不清晰，别放一堆高级词汇，就解释下什么叫和 cpu 有关，什么叫和 cpu 无关。。。 |
|
10
lewis89 2020-12-03 22:31:50 +08:00
@no1xsyzy #7 怎么会有分支预测，协程 协程 就是协作式的调度方式，也就是说 一个协程 霸占着线程 完全可以不退出，因为没有时钟中断，完全可能协程占着那个线程不放，协程要退出来只能主动退出调度，例如你写了个协程
for i=0; i++ ;i <1000 { 干活； 看一看是不是干了好久要不要先退出去让别的协程跑一跑？ function(); 调了个函数 被 golang hook 住了 要不要先退出去 让别的协程跑一跑？ } 线程 for i=0; i++ ;i <1000 { 干活； <-- 去你娘的 时间片到了 回内核睡大觉吧。 function(); } |
|
11
no1xsyzy 2020-12-03 22:33:00 +08:00
kotlin 的协程的底层 API 的命名甚至都明示了其实就是一个一次性的 continuation
|
|
12
lewis89 2020-12-03 22:33:35 +08:00
|
|
13
no1xsyzy 2020-12-03 22:35:17 +08:00
|
|
14
lewis89 2020-12-03 22:35:55 +08:00
@no1xsyzy #11 回去读 CSAPP 吧， 或者看看 X86 汇编手册，RSP RBP 加 PC 指针 然后使用 mprotect 注册内存访问保护 实现中断信号量访问，唯一的确定就是没有时间相应， 用这个几个东西 完全就可以实现简易版的协程
|
|
15
Mohanson 2020-12-03 22:36:28 +08:00
@no1xsyzy 支持对协程进行返回地址预测(Return-address prediction), 理解为分支预测也没有问题.
|
|
17
lewis89 2020-12-03 22:39:38 +08:00
@no1xsyzy #16 还要依赖特定指令集？ 传统的协程 确实就是 保存一下 stack 栈帧 切换一下 PC 寄存器就完事了，我确实不了解除此之外的协程方式
|
|
18
misaka19000 2020-12-03 22:46:00 +08:00 1
@no1xsyzy #8 抱歉没仔细看题主的问题
协程当然和 CPU 没有关系，只是一个逻辑上的概念，代表了对当前的状态以及对状态处理的一种逻辑的抽象。所以你说的对，一个 jmp 也就是图灵机移动指针即可实现协程。 但是，一个 jmp 也可以实现线程啊，所以如果你在讨论协程的话，一般都会与线程放在一起讨论对比的。 按照图灵机的逻辑，线程和协程其实都只是一种逻辑流以及运行状态的抽象。 |
|
19
misaka19000 2020-12-03 22:48:01 +08:00 1
协程和线程的根本区别在于一个是抢占式的，一个不是抢占式的
至于一个工作在内核态一个工作在用户态则是由于操作系统的特性决定的，因为用户态程序无法实现进程 schedule |
 |
20
Wincer 2020-12-03 23:03:13 +08:00 via Android
楼上说的栈切换和 call/cc 其实并不是两样东西。在 Scheme 中，continuation 本身就可以通过操作栈空间的方法来实现，但这仅仅是一种实现方式。如果你要问不同语言之间是否有区别，那当然也是有的。那是不是所有语言都能用 call/cc 来实现协程呢，理论上可行——只需要用他们写一个 lisp 的解释器就行了。
|
 |
21
icexin 2020-12-03 23:11:13 +08:00 1
callback 函数不是一个 jmp 指令那么简单，调用者需要传参，保存返回的 PC 指针，有时甚至要保存[caller-saved-registers]( https://stackoverflow.com/questions/9268586/what-are-callee-and-caller-saved-registers)；被调用者需要保存调用者的栈帧以方便在函数返回的时候恢复之前的栈帧。这些都是跟具体 CPU 指令相关的，我们没感觉是因为编译器帮按照语言的语义帮抹平了不同 CPU 的差异。
对于 go 这样的每个 goroutine 有自己独立栈的，在切换 goroutine 的时候还需要切换对应的栈寄存器。 |
|
22
no1xsyzy 2020-12-03 23:44:38 +08:00
@lewis89 不是，连指令集都不用，你这个还依赖三个寄存器呢，实际上还依赖硬件底层提供了访问栈帧的方式。
CPS （ Continuation-passing style ）就是回调地狱的那个形式，不是特定指令集的名字。不过这个复杂的回调是从任意代码生成的。 （论传统，X86 比不过 call/cc 的吧…… 那个是在 lisp machine 上就实现了的…… 想了想，应该这么说，你这个是在 CPU 上直接套一层实现协作式调度。而楼主的想法是在编译器层面实现的协作式调度。 我完全可以不运行用户篡改栈帧，同时写出一个 Python 解释器并使用 Python 那套协程。我所知，stackless 的协程更多是倾向楼主的想法的，依赖 call/cc 的一个下位替换叫 generator 。 |
 |
23
katsusan 2020-12-03 23:47:49 +08:00
可以参考 下 golang 的协程上下文：
struct runtime.gobuf { uintptr sp; uintptr pc; runtime.guintptr g; void *ctxt; // 闭包函数首地址,x86_64 下存在 DX 寄存器 runtime/internal/sys.Uintreg ret; // 系统调用返回值 uintptr lr; // ARM 下的 link register uintptr bp; } 以 X64 为例，切换上下文的时候大概这样执行： MOV gobuf_sp RSP; MOV gobuf_bp RBP; MOV gobuf_ctxt RDX; MOV gobuf_ret RAX; MOV gobuf_pc RBX; JMP *RBX; |
 |
25
laminux29 2020-12-04 00:15:43 +08:00
进程太重了出线程，线程太重了出协程，仅此而已。
题主可以去翻翻操作系统演变史，当年在有了进程的情况下，为什么要创造出线程，以及进程与线程的差异。 |
 |
26
CismonX 2020-12-04 00:25:13 +08:00 1
call/cc 中的 continuation 并不是协程，前者可以用来实现后者，但后者不能用来实现前者
有关 continuation 的多种不同实现，这篇简单的文章有介绍： https://wiki.c2.com/?ContinuationImplementation 至于 C++ 中的实现，举几个例子：boost::context 用了 segmented stack 实现 continuation，而以 boost::asio::yield 为典型的 stackless coroutine 是将状态存储到一个变量中，然后在语言层面利用类似 duff's device 的特性做了 hack，实现了 yield 语法。 如果说和 CPU 的关系，无非是可以利用某些特定指令来对 continuation 的实现做优化，我觉得并没有必然关系。在任何图灵完备的系统上理论上都可以实现 continuation 支持 call/cc 的编程语言中，语法最简单的是 Unlambda 语言。它也是一个非常有趣的语言。我写过它的两个实现：一个是正统的 C 实现（ https://github.com/esolangs/u6a ），用 segmented stack 实现 continuation ；另一个是基于 TypeScript 的类型系统实现的（ https://github.com/esolangs/type-unlambda ），使用 CPS 实现 continuation 。 |
|
27
no1xsyzy 2020-12-04 00:27:21 +08:00
@lewis89 …… 淦咧你到底看了什么…… CPS 分明是函数式一系的……
想了想我怎么解释都不如 wiki 清楚，而且 v2 还没格式…… https://en.wikipedia.org/wiki/Continuation-passing_style 命令式编程的控制流：一句运行完运行下一句。 而 CPS，把运算结果的去向传递给函数，让函数自己去 call 这个去向。 |
 |
28
vevlins OP 收获很多，学习学习
|
 |
29
xhystc 2020-12-04 10:26:29 +08:00 via iPhone
协程其实就是操作系统这门课所说的用户级线程换了个名词而已，我记得哈工大操作系统公开课有一节讲的是用户级线程的实现，那个就是协程的基本原理，本质就是用户空间的堆栈和 cpu 上下文的切换，没必要引入那么多名词和概念
|
|
30
no1xsyzy 2020-12-04 12:30:37 +08:00
@lewis89 刚在提醒系统里看到你这句我发现我眼花看错了……
“我只能理解命令式的编程方式吧” 我给看成了 “我只能理解**为**命令式的编程方式吧” （手动笑哭 …… 那撇开我上面说的那些，考虑下 go channel 和 pony / erlang 的消息。 更现实地，可以考虑 “流程图”，为每根线标上一个名字，这样的话一个执行节点上运行完，直接告诉调度器 “我的下游是 XX 这根线”。 其实这每根线就是命名续延。 |
 |
31
secondwtq 2020-12-04 13:27:47 +08:00 via iPhone 1
这评论都什么乱七八糟的 ...
C++ 最新的协程标准应该是 stackless 的，根据一个微软的家伙吹的，是所有协程中最 flexible，最 powerful blabla 的（原话忘了） C 的协程一般都是 stacked 的 楼主的理解大致没啥问题，你把这东西放编译器上就是 stackless coroutine，放汇编里就是 stacked coroutine，放内核里就是线程 至于什么是“CPU”的“关系”，我认为楼主的意思是一个 CPU 必须要提供一套能做到图灵完全的基本操作，超过这一范围的就属于“guanxi”。从这个角度来说，函数调用，补码，浮点运算，向量运算，虚拟内存等，甚至是基本的整数运算，都是现代 CPU 的“关系”。John Gustafson 没有关系，所以 posit 没戏。 另外反正评论区已经足够群魔乱舞了： 这东西其实就是先让一部分计算执行完后，再执行什么计算的问题，所以我认为协程是一个中国特色社会主义理论问题 |
Select Language