其他 关于协程(用户态线程)

yfractal · 2022年08月05日 · 最后由 yfractal 回复于 2022年08月06日 · 166 次阅读

本文主要用于闲聊,并不严谨,也比较水。

接下来,会简单说一下,为什么需要 coroutine 或者 user level thread。以及如何简单实现 user level thread。最后会说一些相关问题。

为什么需要 user level thread

系统线程的效率并不高。原因是,系统线程切换的时候,要做用户态和内核态的切换。

并且切换的时候,要换 page table,会很耗时(之前不用,但为了解决 maltdown 给加上了,搞 io_uring 的一个原因就是因为这个 [1])。

还有一种说法是系统线程比较占内存,但系统分配内存是 lazy allocation,可能没有看起来多。不过这个要具体做实验和看实现,本文属于闲聊,就略过了。

为了解决性能问题,我们可以在用户态实现线程,即所谓的 user level thread。

我们知道,系统有各种个样的 interrupt,触发 interrupt 后会进入内核态我们就可以调度系统线程,从而达到抢占式调度。

但我们自己实现线程,由于操作系统不知道我们写的线程是什么,也就失去了这个能力。

想要完成调度,需要主动让出执行,即所谓的 coroutine。

想为 user level thread 实现抢占式调度,应该有不少办法。

我能想到的编译的时候插入代码,不行就把 loop 去掉(以太坊的虚拟机就没 loop,这样他就能算程序需要多少算力)。不知道能不能用 ebpf 搞。

或者操作系统中断的时候,执行一些 hook,没有就改操作系统代码。再比如 Erlang,实现一个虚拟机。

所以我们可以看到,实际要做的是 user level thread,coroutine 不过是一种相对简单的实现。

所以 user level thread 范围更广,也会更有趣一些。

简单实现

当我们调用方法的时候,需要把局部变量(context)存在栈里,方法执行完,再把存的东西拿回来。

user level thread 也可以用类似的方法实现。

我们把 thread 简单定义为一个执行序列。比如一次快排可以是一个执行序列。

user thread 切换要做的事情是,在一个执行序列,被执行到一部分的时候,跳到其他执行序列。

比如我有两个 user thread 分别做不同的排序算法。

当一个算法,执行了一会后,跳到另一个算法,就完成了调度(方法调用是跳回 caller,user level thread 切换不过是跳到其他 thread)。

我们可以定义一个 yield 方法,执行该方法的时候,执行 yield 的时候,做切换,即跳到其他 thread。

具体一点,就是调用 yield 的时候,把上下文存起来(包括 PC),之后挑一个 user level thread,把栈指针指到对应的上下文,指 PC,就可以完成切换 [2]。

顺便说一下,经常在 user leavel thread 里调用 sleep,会造成阻塞。

如果调系统的 sleep,这个线程被挂起了,而系统线程里有多个用户线程,所以造成了所谓的阻塞(阻塞这个词其实有点模糊,看具体做了什么才好理解)。

但我们可以自己实现 sleep,比如 Erlang 的 Time Wheel[9]。

相关问题

大的问题有两个,一个是如何描述执行单元,或者说编程模型是啥。一个是如何调度。

编程模型这个问题,跟使用场景、个人喜好有关。

比如场景复不复杂,性能要求到底有多高。

比如有人喜欢 goroute,因为用起来简单。有人喜欢 Erlang 的 Process(这个说的是 Erlang 实现 user level thread,而不是系统的 Process),因为维护简单。

因为依赖场景,有一定的主观性,就不细说了。

调度方面一个问题是如何做到更高效。

比如我有两个 CPU,然后我用两个系统线程跑 n 个 user level thread。那我这两个 thread 在两个 CPU 上窜来窜去,肯定影响性能,所以一个优化就是绑定 CPU。

再比如,系统线程 0 比较闲,系统线程 1 却很忙,那我要不要从 1 里偷点给 0?

再比如,CPU 只是偶尔闲一下,我要不要胡乱搞点什么,避免系统被切换走。如果真的很闲,要不要干脆只用一个系统线程执行算了。[11]

另外一个问题,就是如何利用多核,或者说如何做并行。比如在消息传递的时候,塞消息和取消息的时候能不能不阻塞,以及内存如何申请如何回收,Erlang 的做法就很有趣 [7]。

多核、并行,在其他领域也有非常多的研究,比如 key value storge[3],网络 [4] 操作系统 [5]、数据库 [6],再比如同步 [10],都是很有趣的问题。

引用

  1. Efficient IO with io_uring https://kernel.dk/io_uring.pdf
  2. User Level Thread Switch https://github.com/yfractal/blog/blob/master/blog/2021-07-29-user-level-thread-switch.md
  3. H. Lim. MICA: A Holistic Approach to Fast In-Memory Key-Value Storage. NSDI ’14, 2014. https://www.usenix.org/conference/nsdi14/technical-sessions/presentation/lim
  4. ] E. Jeong. mTCP: A Highly Scalable User-level TCP Stack for Multicore Systems. NSDI ’14, 2014. https://www.usenix.org/conference/nsdi14/technical-sessions/presentation/jeong
  5. P. E. McKenney. RCU Usage in the Linux Kernel: One Decade Later. Technical report, 2013.
  6. X. Yu, et al., Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores, in VLDB, 2014
  7. Konstantinos Sagonas, Efficient memory management for concurrent programs that use message passing, in Science of Computer Programming, 2006 https://github.com/yfractal/blog/blob/master/slides/erlang-message-passing.key
  8. Silas Boyd-Wickizer. Corey: an operating system for many cores. OSDI'08, 2008.
  9. Erlang Time Wheel https://github.com/erlang/otp/blob/ce6172a1badb21a97a4235db27e2f991f01d5b0a/erts/emulator/beam/time.c
  10. RCU Usage In the Linux Kernel: One Decade Later https://pdos.csail.mit.edu/6.S081/2020/readings/rcu-decade-later.pdf
  11. JIANRONG ZHANG. Characterizing the Scalability of Erlang VM on Many-core Processors. 2011

想为 user level thread 实现抢占式调度,应该有不少办法。

user-programmable schedulers

Kostis Kaffes Syrup: User-Defined Scheduling Across the Stack. SOSP ’21.

Towards User-Programmable Schedulers in the Operating System Kernel https://www.pure.ed.ac.uk/ws/files/265136338/Towards_User_MVONDO_DOA04032022_AFV.pdf

没具体看,似乎是相关的东西。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号