Async in zCore

整体目标

在RISC-V平台上设计并实现一个基于Rust语言的异步操作系统。最终目标是，利用Rust语言和开源工具链的特征，在操作系统内核中实现细粒度的并发安全、模块化和可定制特征；利用Rust语言的异步机制，优化操作系统内核的并发性能；向应用程序提供的异步系统调用接口，优化操作系统的系统调用访问性能；结合LLVM中Rust语言编译器的异步支持技术，完善操作系统的进程、线程和协程概念，统一进程、线程和协程的调度机制；利用RISC-V平台的用户态中断技术，优化操作系统的信号和进程通信性能；开发原型系统，设计用户态测试用例库和操作系统动态分析跟踪工具，对异步操作系统的特征进行定量性的评估。

1. 利用Rust语言和开源工具链的特征，在操作系统内核中实现细粒度的并发安全、构件化和可定制特征；（基于rCore和zCore来判断，这一条应该是可行的，还需要改进；）
2. 利用Rust语言的异步无栈协程机制，优化操作系统内核的并发性能；（rCore和zCore的实现，在内核中支持异步是现成的；需要做的事，针对异步机制对现有的内核模块进行优化(贾：文件系统中的read和write的系统调用接口已完成改造，还需要对内核中的文件系统模块进行改造；网络模块：在qemu中用virtio；需要询问K210上的无线模块状态；串口模块)；陈渝老师可以支持SiFive的有网络的板子）
3. 向应用程序提供的异步系统调用接口，优化操作系统的系统调用访问性能；（贾：aCore中已经实现了read和write的异步系统调用（fork用时长，但也不需要改成异步，原因是，不会多次用它）；张译仁：系统调用的自动化异步改造：对语言有依赖，对rust实现自动化异步改造是可行，加上一个trait或宏就行；可以先改造几个，然后自动搞；异步系统调用接口可以有多种不同的实现；）
4. 结合LLVM中Rust语言编译器的异步支持技术，完善操作系统的进程、线程和协程概念，统一进程、线程和协程的调度机制；
   1. 刘丰源对Rust编译器有过分析：目前还没有分析清楚；
   2. 进程由OS内核管理；用户线程由函数库管理；协程目前是由编译器生成代码或用户函数库管理；（线程和协程都可以用语言或函数库实现，类似GO语言的支持；）
   3. 需要做的事是，分析进程、线程、协程中的数据结构和状态维护；然后尝试访问和控制这些信息；（进程、线程和协程的控制块可以分成用户态控制块和内核态控制块两部分）
   4. 最终实现：协程是基本的调度单位，只对协程进行调度。在不同情况下体现为进程切换、线程切换和协程切换；（单队列的同步开销和多队列的负载均衡开销需要折中；统一的原则是，只有一家可写，多家可读；统一的方法是，代码由内核提供，状态数据只有所有者可写，其他进程可读；）
5. 利用RISC-V平台的用户态中断技术，优化操作系统的信号和进程间通信性能；
   1. 在FPGA上实现RV的用户态中断；
   2. 优化信号的实现；
   3. 进程间通信：第一次通过内核建立通道；中间的信息交互只是请求和响应队列的访问，没有进程切换；结束时通过内核删除通道；
   4. 在单核下利用用户态中断，也可以提高IPC性能；
6. 开发原型系统，设计用户态测试用例库和操作系统动态分析跟踪工具，对异步操作系统的特征进行定量性的评估。
   1. IO 密集型程序（以 Web 服务器为例）能够达到接近专用系统的高性能（高并发，低延时）。

异步操作系统中的基本概念

IO 接口类型：同步与异步

• 同步阻塞：例如 read，阻塞当前线程直到读取完成。
• 同步非阻塞：例如 read(NONBLOCK) ，如果当前读尚未就绪则立即返回。
• 多路复用：例如 select,poll,epoll，阻塞当前线程直到给定事件中的任何一个发生。常配合同步非阻塞接口使用。
• 异步：例如 MPI_iread，发出读请求，返回一个 token。之后可以查询请求状态（轮询）或者用 wait 接口阻塞等待操作完成。
• 循环队列：例如 io_uring 及硬件设备，背后有一个内核线程（或硬件上的处理器）同时处理 IO 操作，二者通过共享内存中的两个循环队列（请求队列和完成队列）传递请求状态。

I/O接口的性能对比

上述接口的性能依次提升，易用性依次下降：

• 同步阻塞：由于每次操作都可能阻塞当前线程，因此对于每个链接都需要创建新线程，大量线程会占用系统资源并增加线程切换开销。
• 同步非阻塞+多路复用：只需要一个线程就可以处理全部 IO 操作。当未就绪时不会阻塞当前线程，但执行 IO 操作本身依然会占用当前线程。由于是同步的，因此每次操作请求方和执行方都不需要保存状态。
• 异步：将 IO 操作分为提交和完成两步，可以一次进行多次提交，然后在等待完成期间执行其它计算任务。一般由后台线程完成执行，并且可以对多个请求进行调度以提高整体性能。但是由于被拆成了两步，因此双方都需要维护每个请求的状态。
• 循环队列：异步的终极形态，具有最高的并行性和性能。生产者和消费者同时执行，不需要上下文切换。但是需要建立共享内存并防止数据竞争。

这几种方案本质上是请求状态和执行状态的不同组合方式：二者越松耦合，并行性越高，性能越高，但是易用性越差。

事件机制：中断与轮询

• 中断：当事件发生时，当前执行流被中断，产生一个新的临时执行流，运行中断处理函数，完成后返回原执行流继续执行。例如 CPU 中断，Unix 信号。
• 轮询：当前执行流永远不会被打断，需要主动去询问目标事件是否发生。

中断和轮询的适用场景

• 中断适用于事件发生不频繁，但实时性要求高的场景。中断处理过程中一般不允许嵌套中断，因此处理过程应尽量短。
• 轮询适用于事件发生频繁，要求高并发的场景。此时若开启中断会造成大量切换开销。

中断分发和处理过程

• 一切软件中断的根源都是 CPU 中断，它本质上是 CPU 在指令粒度上进行轮询。
• CPU 可以根据配置将中断分发到不同的特权级上处理，但主流实现是先分发到 OS，OS 再根据情况通过信号等机制转发到用户程序。
• RISCV 中的 N 扩展指令集实现了用户态中断，但目前标准还在起草阶段，模拟器和物理机都没有实现。如何利用用户态中断提高用户态驱动的性能是值得探讨的话题。

任务管理：进程、线程与协程

• 进程：每个进程有独立的地址空间，因此有页表切换开销；目前的设计是，内核是一个独立的进程，还存在多个用户进程。在异步操作系统中，操作系统内核被视为一个独立的进程，有自己的独立的页表；系统调用过程会变成一种特殊和优化的进程切换。
  • 类似于传统的操作系统中进程切换代码是在两个进程中共享的，把内核视为独立进程后，系统调用也成了进程切换。好像每个用户进程中还需要有一段内核态代码，以完成切换过程。
• 线程：每个线程有独立的用户栈，切换时需要保存和恢复全部寄存器。由于内核与用户线程不在一个地址空间中，每个用户线程只有用户栈，不存在对应的内核栈；每个内核线程只有内核栈，不存在对应的用户栈。
• 协程：可以理解为状态机转移函数，执行时共用同一个栈。每个线程内可以有多个协程。编译器将 async 函数变换成状态机时，函数中需要跨越 await 的变量将存放在 Future 对象中（一般在堆上），其它变量只需放在栈上或寄存器中。

协程与线程的对比

无栈协程与线程（or 有栈协程）之间的对比

• 由于协程只可能在有限的 await 语句处切换，因此需要保存的状态信息较少；而线程可能在任意指令处被中断并切换，因此需要保持整个栈空间。所以协程空间占用更少。
• 协程切换时无需换栈，访存局部性更好。协程切换相当于一次函数返回和调用，寄存器的使用遵守调用约定 ABI，一般不会涉及全部寄存器（？）。所以协程的切换开销更小。

进程、线程与协程概念 V2.0

• 协程/任务：一段正在执行的函数代码，最基本的调度单位。根据任务可能发生切换的时机，可分为：
  • 抢占式：随时可能发生切换（时钟中断），保存状态多，切换开销大，保证实时性。
  • 协作式：调用特定操作时发生切换（yield），保存状态少，切换开销小，不保证实时性。

还有一种分类方法是根据是否有栈，但无栈只是对有栈的优化，无本质区别：

* 有栈：局部变量保存在栈上，切换时切换栈指针 SP 和部分寄存器（遵循函数调用约定）；
* 无栈：局部变量不保存在栈上（堆），切换时切换状态指针和部分寄存器（遵循函数调用约定），可以手写或编译器自动生成。

• 线程：运行于同一虚拟 CPU 内，同一地址空间的任务集合。虚拟 CPU 是指程序认为计算机拥有无限的 CPU，每个线程运行于不同的虚拟 CPU 中，但不会有两个 CPU 同时运行同一线程中的任务。因为实际上物理 CPU 有限，由调度器协调让一个物理 CPU 只能同时运行一个线程。可以先简化为虚拟 CPU 等于物理 CPU，但这样同一进程内的线程数不能多于 CPU 个数。
• 进程：同一地址空间内的任务集合。其中的任务可能位于不同 CPU，即有多个线程。

与原来概念的对比：

原来	现在
1 个进程，多个线程，分别运行在不同 CPU 上	1 个进程，多个协程，每个协程属于不同线程（不同虚拟 CPU 不同物理 CPU）
1 个进程，多个线程，运行在同一 CPU 上	1 个进程，多个抢占式协程，所有协程同属一个线程（相同虚拟 CPU 相同物理 CPU）
或	1 个进程，多个抢占式协程，协程可属于不同线程（不同虚拟 CPU 相同物理 CPU）

由于实时性问题，应该要同时保留抢占式和协作式协程/任务，关键问题是这两种协程调度的统一，比如说切换时根据中断方式（被动中断还是主动中断）自动判断保存/恢复哪些状态。

理想的协程切换过程（贾越凯细化）

对于调度器而言，协程和线程没有区别，可以统一对待。事实上，在调度线程看来，执行一个线程也是一次函数调用（两次上下文切换的汇编被包装成了 switch 函数），更接近于协程。

极致的状态是，应用程序的主动切换一定是协程切换；在统一了进程、线程和协程的管理数据结构后，在协程切换中可以选择不同进程和不同线程中的下一个就绪协程。

1. 如果当前运行协程与选中的下一个就绪协程在同一个进程的同一个线程中，这时的协程切换就是在当前线程内的函数调用。
2. 如果当前运行协程与选中的下一个就绪协程在同一个进程的不同线程中，这时的协程切换就是在当前进程内的线程切换，需要执行函数库形式实现的线程库代码，进行用户堆栈保存和切换。
3. 如果当前运行协程与选中的下一个就绪协程在不同进程中，这时的协程切换就是在由操作系统内核支持的进程切换，需要保存当前用户堆栈，并切换到内核进程执行内核的调度器代码，以完成进程地址空间、用户堆栈和协程维护数据结构（即是由编译器生成代码维护的协程控制块）。

异步编程模式

进化过程：

• 原始形态：回调函数
• 函数式封装：Promise 和 Future
• 编译器变换：generator 和 async-await

async 语法的出现使得编写异步程序看起来就像以前的同步风格，不过它还是有一些限制：

• async 函数具有传染性，传统函数不能调用 async 函数
• Rust 中的 async 函数不能递归或循环调用，因为状态机不能无限嵌套下去，但是可以用 Box 绕过

Rust 的 async 机制需要运行时的配合，其中重要组件如下：

• future：协程状态机本体
• executor：协程的调度与执行器，相当于线程调度器
• reactor：负责注册和触发事件回调函数，相当于中断处理函数
• waker：唤醒协程的 token，由 future 注册给 reactor

两种主要异步编程模式的统一

应用程序在使用异步编程模式时，有yield和poll两种方式。

• yield模式是指，由应用程序通过调用yield函数（由编译器生成调用或由开发人员手工调用）放弃当前协程（任务）的CPU使用权；然后由用户库或操作系统选择下一个协程。
• poll模式是指，在编程语言的帮助下，把协程的执行封装在调度事件循环内部。应用程序中的各协程在执行过程中，遇到需要等待事件触发条件时，放弃CPU使用权，并进入等待状态；然后执行事件循环，查找下一个满足触发条件的协程，得到CPU使用权，并进入运行状态。

1. 基于 yield 函数

在一个任务内调用 yield 函数切换到另一任务。yield 会保存当前任务的状态，从任务队列中取出下一个任务，并将当前任务重新加入队列，然后恢复下一任务的状态。实现简单，与语言关系不大。代表：sys_yield 和原来进程/线程的概念。

fn task1() {
    // do work 1
    yield();
    // do work 2
    yield();
    // do work 3
}
fn task2() {
    // do work 1
    yield();
    // do work 2
    yield();
    // do work 3
    yield();
    // do work 4
}
fn yield(rip, state) {
    let current = Task {
        rip,
        state,
    };
    let next = QUEUE.pop();
    QUEUE.push(current);
    rip = next.rip;
    state = next.state;
}

2. 基于 poll 机制

有一个大的事件循环，每次循环会从事件队列中取出一个事件，调用其 poll 方法，修改状态，返回 ready/pending，如果是 ready，从队列中删去，是 pending 重新加入队列。一般与语言相关。代表：Rust，Node.js。

loop {
    let task = QUEUE.pop();
    match task.poll() {
        Ready => {},
        Pending => QUEUE.push(task),
    }
}
fn task.poll() {
    // do work 1
    loop { // sub_task1().await
        match sub_task1.poll() {
            Ready => break,
            Pending => {
                // return Pending, 但下次调用 task2.poll() 时
                // 直接从这里开始
                yield Pending;
            }
        }
    }
    // do work 2
    loop { // sub_task2().await
        match sub_task2.poll() {
            Ready => break,
            Pending => {
                // return Pending, 但下次调用 task2.poll() 时
                // 直接从这里开始
                yield Pending;
            }
        }
    }
    // do work 3
    Ready
}

使用 yield 实现 poll

将yield关键字替换为 yield() 函数即可

使用 poll 实现 yield

将yield() 函数替换为yield关键字：下次再调用该函数时直接从下一条语句开始。

需要确定统一的调度机制使用哪一种模型，然后将不同语言的协程库用该模型重新实现。感觉让yield函数作为最底层的模型比较好。

异步系统调用

基于同步系统调用实现的异步机制

目前的系统调用实现都是同步的，即使是uring中的异步系统调用也是用两次同步的系统调用来完成的。

1. 第一次执行系统调用的目的是，建立用户进程与内核进程的信息交互通道和第一个系统调用请求。第一次执行系统调用时，需要用户代码和内核的配合，并会真正切换到内核。由内核代码创建相关系统调用在内核进程与用户进程地址空间的共享内存；由用户进程在共享内存中维护系统调用的请求队列，用内核进程在共享内存中维护响应队列。
2. 第二次系统调用的目的是，查询前一次的结果和提交可能的第二个系统调用请求。查询由用户态代码完成。查询没有结果或有第二个请求时，就只在请求队列中加入第二个请求，不进内核了。查询有结果且没有第二次请求时，需要进入内核删除共享内存，并返回第一个请求的结果。

理想的异步系统调用接口

编译器与操作系统进行密切配合，用户态的异步系统调用会编译器自动生成相应的系统调用请求代码和协程控制块数据结构，只在第一次系统调用和最后一次系统调用时进入内核，中间的各次系统调用只进行系统调用的结果查询和进程、线程或协程切换。在当前协程的系统调用还没有结果返回且没有新的可执行用户任务时，才会进行协程切换。（？更细的描述需要先分析编译器的异步支持实现后，才能给出。）

同步系统调用与异步系统调用的关系

同步或异步系统调用都是用于访问操作系统内核的服务。

同步系统调用的执行过程

1. 用户进程准备好系统调用参数后，发起系统调用请求，并进入阻塞状态；
2. 内核进程收到请求后，内核进程恢复执行。首先，保存用户进程上下文，将用户进程置为阻塞状态；然后，获取系统调用参数，执行相应服务，并得到返回值；最后，将用户进程置为就绪状态，等待调度执行；
3. 用户进程得到CPU资源后，在内核态恢复上下文现场；读出系统调用返回值，完成系统调用过程。

注：用户进程与内核进程间的切换代码是，由内核进程提供，用户进程只能执行。

异步系统调用的执行过程

第一次异步系统调用时：

1. 用户进程要做的工作包括准备系统调用参数、发出系统调用请求；
2. 内核进程要做的工作包括映射共享内存、获取系统调用参数、发起相应服务协程的异步执行、返回共享内存中的服务响应队列信息给用户进程；
3. 内核进程执行完服务协程后，在响应队列保存返回值；

第二次异步系统调用时：

1. 用户进程在请求队列准备系统调用参数；在共享内存的响应队列中查看第一次系统调用的结果；
2. 内核进程在完成第一个服务协程后，在共享内存的响应队列中保存返回值，主动查询新的系统调用请求，并执行；如果没有新的请求，则让出CPU；

关键问题

协程的实时性问题

无栈协程是一种非抢占式的任务调度机制，对时间敏感的任务可能无法及时调度运行。例如 GUI 任务，它大部分时间是空闲的，但当鼠标键盘事件出现时必须及时响应，否则用户会感受到卡顿。

因此，需要实时执行的操作只能通过中断方式处理。但是无栈协程只能在特定位置主动让出，不能由中断处理函数代为让出，因此就无法让紧急任务抢占运行。

解决方案是保留线程机制。将协程封装在线程的内部。当不需要实时执行的操作请求出现时，可以在当前协程主动让出CPU时，切换到执行相关操作的协程进行处理。当需要实时执行的操作请求出现且当前协程并没有主动让出CPU时，暂停当前协程所在线程的执行，响应中断并判断是否需要抢占当前协程所在线程的执行。不需要抢占时，处理完中断后恢复当前协程执行；需要抢占时，处理完中断后，创建新线程执行实时操作。即平时在 1 个线程上调度运行所有协程，当关键事件发生需要抢占时，在中断处理函数中创建一个新线程，专门执行紧急的协程，完毕后销毁新线程，回到主线程继续执行。

协程、线程和进程的调度

进程用于管理CPU以外的资源分配和回收；线程和协程用于CPU资源的管理（调度）；目前能实现出来的状态是，线程调度可能跨进程或在相同进程内进行，协程调度不跨线程。直观感觉，协程调度应该可以跨线程，甚至是可以跨进程。

假定协程调度可以跨线程和进程，这时切换过程。

1. 同一线程内的协程切换：在rust语言中，编译器已完善搞定。协程在执行异步函数调用时，会调用编译器自动生成的有限状态机切换代码，完成如下工作。
   1. 保存当前协程的状态；（编译生成的相关代码分析结果：每一个协程会在堆上有一块数据结构保存自身状态，固定大小，大小由编译器计算得出，每次执行该协程，直接操作堆内存，所以协程状态的保存只需要把在寄存器中暂存的结果刷新到这块内存上）
   2. 查询就绪协程列表，按一定策略选择下一个就绪协程；
   3. 恢复下一个协程的状态，然后继续执行。
2. 同一进程内不同线程中的协程切换：在当前协程让出CPU时，如果同一线程内的协程都处于异步函数调用的等待状态中，从逻辑上应该整个线程让出CPU，选择其他线程中的就绪就绪协程来执行。这时的麻烦是，编译器生成的协程调度和OS内核实现的线程调度如何整合成一个有机整体（感觉这两个是相互独立的，只要调度器直接调用 sleep() 就是被切出去，唤醒：在某一个等待的系统调用返回后，将进程重新置于 ready 态）。想像的工作过程如下。
   1. 协程调度器保存当前协程的状态；（似乎不需要？进程切换代码代为保存）
   2. 协程调度器的代码代表当前线程，主动让出CPU；这时需要保存当前线程的状态（包括所有通用寄存器状态）；
   3. 执行线程调度器代码，查询就绪线程列表，按一定策略选择下一个就绪线程；
   4. 恢复下一个就绪线程的状态，然后继续执行协程调度器代码，按一定策略选择当前线程中的下一个就绪协程；
3. 不同进程内的协程切换：需要进行地址空间的切换；基于RISC-V的用户态中断就可以不通过内核直接切换到另一个进程。一种可能的做法是，用户态的调度代码通过系统调用请求内核来完成这个切换。

问题讨论

1. 如果就绪协程的队列和就绪线程的队列是一个，这个选择的过程就可以统一了。
2. 如果协程切换和线程切换的可以统一，在切换时只需要依据是否在一个线程内，就可以分情况实现协程切换、协程加堆栈切换、协程加堆栈和地址空间的切换这三种切换。
3. 这几种切换的统一需要事件注册和事件处理分发机制的统一。（不太懂，求说明）操作系统中的事件有多种，各自有自己的请求队列和响应处理。事件处理分发机制的统一，可以对这些事件的处理定义一个优先级，为调度选择提供依据。

系统调用接口设计

系统调用接口可采用vDSO来支持异步系统调用；

vDSO的好处

1. 安全性（函数调用到vDSO的代码来访问内核服务，vDSO的代码对用户只读）；
2. 兼容性（函数调用接口保持稳定）；
3. 高效性（不用进内核的服务访问，内核与用户态的内存共享（例子：获取系统时间））

可能的做法：用rust重写vDSO的实现，然后改造rCore的系统调用接口和RustSBI的SBI接口；

如何跨越系统调用打通用户态、内核态的异步运行时？

可能的一些设计目标：

1. 统一的协和调度是指由内核提供调度器代码，并使用一致的维护数据结构；调度器代码的执行仍然会分布在用户态和内核 态。在用户态执行协程调度器代码来完成进程内的协程切换开销更小。换言之：内核进程与用户进程共享协程调度数据结构，进程内的线程和协程切换在用户态执行；进程切换需要在内核态执行切换所必须的特权指令。
2. 用户态和内核态分别负责状态保存（比如在 poll 的时候会进行的状态保存）

2020-10-11 交流：

1. 内核和用户态分别调度和状态保存，中间层通过 RingBuffer 进行通信
2. 低功耗：内核作为事件触发机制，尽量减少用户/内核切换，若用户没有用到内核功能则内核不占用任何 CPU 资源，与之前的 idle process 不同（低频 spin -> nothing）

没想清楚

一种可能的思路

1. 通过共享内存来查询事件触发状态、协程就绪状态；
2. 用户态和内核态同时支持协程调度和线程调度，内核通过vDSO提供一致的协程和线程调度器代码；
3. 跨地址空间的切换只能通过内核协调。

性能分析

如果采用每个用户线程对应到一个内核协程的方式，性能提升可能并不明显。目前的设计是，内核是一个独立的进程，还存在多个用户进程；每个进程内可以有多个线程，每个线程内可以有多个协程。

1. 对于传统的同步应用：我们还是需要给每个用户线程开一个用户栈，即使现在每个核仅需要一个中断栈（但其实 Linux 似乎已经做到了这一点？）性能提升大概体现在缓存友好、内核态两个 Future 之间切换的开销较小。对于多线程的 I/O 密集型应用似乎会有一定效果；

// 对于同步调用，感觉不太可能有比较大的提升

2. 对于异步应用：其用户线程数很少，导致很少发生内核态 Future 切换，我们的异步内核相比传统内核应该没有明显提升。

// 需要重写用户异步底层接口

需要注意的是，通过 epoll 降低系统调用开销，和通过 io_uring 大幅减少系统调用次数，以及类似 Rust 这样的 async 降低用户态协程切换开销，这些优化和我们的内核是同步还是异步都是没有关系的。目前看来，如果沿用以往的 Linux 系列接口，异步 OS 的性能提升就会仅仅体现在内核栈数目的（可能）减少以及内核态两个 Future 切换开销（可能）比传统意义上两个内核线程切换开销要小。

如果想实现更大的性能提升，我们确实需要设计新的一套 syscall 打通用户、内核态的运行时，这意味着完全不同的用户程序开发方式。但为了兼容性，我们希望它能够用来实现 Nginx/Redis 的统一事件机制接口。

研究和开发任务划分

异步系统调用

基于uring的异步系统调用实现

基于RISC-V用户态中断的操作系统信号机制优化

用户态中断的注册通过系统调用在内核进程进行处理。理想的结果是，有了用户态中断后，由用户态信号服务例程处理的信号可以完全在用户进程内完成，不需要内核的参与。

内核的进程化改造

将操作系统内核改成一个进程，从而把内核地址空间和用户进程地址空间视为两个独立的地址空间，把系统调用视进程间通信的特例。

基于异步系统调用的进程间通信优化

用户进程间的通信信道的建立和删除都需要有内核进程的参与；通信的中间过程基于轮询，没有内核进程的参与；信号机制可以用于通信暂停后的恢复。

异步操作系统调度器

进程、线程和协程调度代码分析

Rust的协程调度实现分析，了解协程控制块和就绪协程队列的工作机理，尝试提供相关信息的查询接口和控制实现。

C++语言的协程支持扩展

扩展C++语法，以支持异步机制所需要的async和await；

写一个编译器，可以把扩展语法转换成标准的C++语言，并支持线程内的协程调度；

改进编译器实现，以支持多CPU时的协程调度负载均衡；

Rust语言的协程支持扩展

Rust语法已有异步机制所需要的async和await；

改进Rust语言异步机制中的executor，以支持多CPU时的协程调度负载均衡；

用户态线程和协程调度的统一

针对Rust和C++的协程支持实现，统一协程维护的数据结构，使混合编程的应用可以正常工作；

查找Rust和C++下可用的开源用户态线程库，使协程和线程可以协调工作，以支持操作系统在任何时刻的进程切换对协程的工作没有负面影响；

引入线程和协程优先级支持，支持线程内的按优先级调度协程；

统一线程和协程的调度机制，支持按优先级统一调度线程和协程；

内核进程与用户进程的线程和协程状态信息共享

通过共享存储区，利用内核进程在各用户进程间共享调度状态信息；

统一的进程、线程和协程的调度器实现

基于vDSO在应用进程执行由内核共享的调度代码，实现进程、线程和协程的调度。

多CPU上的进程、线程和协程的统一调度器测试和特征分析

设计调度器的测试用例集，对调度器的特征进行测试；

基于测试结果，对调度器的特征进行分析；

尝试对调度器进行可能的优化；

内核中的异步支持

参考链接：

no-std-async-experiments-2

no_std async/await - soon on stable

在内核中引入Rust异步机制

在内核线程中引入Rust异步机制，把I/O操作封装成协程；

基于异步机制改造zCore的内核模块

目的是充分利用异步机制来提高并发性能。

实现方案

目标用户程序

1. 基于事件循环机制的异步应用，模型为每个用户线程为一个大事件循环，在循环开头通过 syscall 检查哪些请求已经完成，随即对它们进行处理，处理过程中可能提交新的请求，然后进入下一个循环。目前已有的例子是，Nginx 和 Redis 都将事件机制封装成统一的接口，并提供基于 select/poll/epoll/kqueue/iocp/io_uring 其中的某几种系统调用的实现。如 Redis 的ae_<event_syscall>.c以及 Nginx 的ngx_<event_syscall>_module.c。tokio 的底层 mio 应该也是基于 epoll 实现的，但目前并没有深入调研。也就是说，无论应用的代码看起来是什么样子，这种应用的核心要素在于事件循环、addEvent 和 poll。
2. 传统面向过程的同步应用，每个线程都是从头执行到尾，它并不会关心每个调用是否被阻塞，对于它来说完全是透明的。

初步实现方案

每个用户线程映射到内核中的一个无栈协程，也就是一个 Rust Future。随后内核跑一个优先级线程调度器调度多个内核线程，每个内核线程是一个 Executor 调度多个内核协程。目前的 zCore 是单核的，为了支持多核需要新增优先级线程调度器。

优先级体现在：当遇到了响应优先级或实时性要求较高的中断时（如键盘等），可以将对应的 Future 从低优先级线程取出放到高优先级线程，由此可以降低延迟，但是站在高性能的角度这是可以舍弃的。

我们可以先基于 zcore-linux-bare-metal 进行改进，支持 poll/epoll/io_uring 系统调用，确定一个测试平台并实现对应的块设备和网卡驱动以及 TCP/IP 协议栈，为了提高性能均支持 DMA，以中断方式访问（根据 Biscuit 论文可以用 interrupt coalescing 技术将网卡中断间隔调整到 128 微秒）。由此，可以基于 Nginx/Redis 进行简单的 benchmark。

TODO

---

10.14 讨论的实现方案

利用 io_uring/virtio 的思想，基于共享内存实现的高效异步系统调用接口。

假设系统有两个核，分别为：

1. 普通核：类似传统的 OS，有用户态和内核态，负责运行用户进程、调度用户进程、处理普通系统调用。
2. IO 核：只有内核态，负责运行内核协程、调度内核协程、处理异步调用。实现了一套类似 io_uring 的机制，内核协程会不断 poll 共享内存中的请求队列，处理完毕后放入完成队列。使用 Rust async 实现。

前期简化

有且仅有两个核；没有用户线程；单用户进程；没有抢占；

用户程序的实现

1. 通过系统调用，创建用户进程
2. 通过系统调用，在 IO 核同时创建 io_uring 共享内存，和对应的内核协程（需要 IPI）。
3. 异步 read：向请求队列写入 read 操作和所需的参数，立即返回。直到完成队列显示已完成，并得到返回结果。（可能需要通知机制？）
4. 同步写法的异步 read（这部分是用户库的内容吗？是）：
   1. 使用 Rust async 创建用户协程，poll 函数里检查对应的 IO 操作是否在完成队列中
   2. read 后轮询是否完成，用 yield 去别的进程执行一会儿
   3. read 后 wait 进入睡眠，直到完成时才被唤醒（通知机制？）

请求队列与完成队列的设计

TODO

使用共享内存在用户进程与内核协程间共享。

是否要和 io_uring 完全一样？

是否还是两队列形式？更好的设计？

最小原型系统

预计实现的普通系统调用：（有用户/内核切换）

1. spawn：创建用户进程
2. setup_io：创建共享内存和内核协程，返回共享内存地址
3. yield：主动放弃当前进程的执行，进行进程调度
4. wait：主动放弃当前进程的执行，进行进程调度，直到 IO 操作完成时返回

预计实现的异步调用：（只需写共享内存，无用户/内核切换）

1. open
2. read
3. write
4. close

测试环境：

• RISCV64，QEMU/K210
• memory fs/SD 卡

实现步骤

方案一：从头开始造

1. RISCV64 QEMU 多核启动
2. 普通核实现内核的基本功能（内存管理、进程管理、memory FS）
3. 支持运行一个 hello_world 用户进程
4. IO 核实现共享内存创建
5. 内核协程创建与调度
6. 实现 open/close/read/write
7. 完善系统调用
8. 编写性能测试程序，真机测试

方案二：将 rCore_Tutorial 改造成这种架构

其他问题

IO 核如何访问不同用户进程的IO数据？好像还是要切页表？

（第一版无需考虑）

完成时如何通知用户程序？

是否可在普通核开中断？

是否可以支持乱序完成？（似乎 io_uring 就是乱序的，可以通过参数强制顺序执行）

---

11.1 交流

目前进展：基本完成普通核部分的内核功能，有简单的 C 用户程序和库。(step 3)

分工

jyk：完成 IO 核部分的内核功能：创建共享内存、调度 IO 协程、执行 IO。

zyr：制定系统调用接口和共享内存数据格式，用 C 编写用户态 IO 测试程序。对应上文提到的三种实现方式：3异步 read、4b同步写法的异步 read、4c同步写法的异步 read。

lfy：编写 rust 用户库，支持运行 rust 用户程序，编写利用 rust async 创建多个协程的用户程序。然后利用 rust async 将 C 的 IO 测试程序改成 rust。对应上文提到的实现方式：4a同步写法的异步 read。

用户线程与地址空间相关的问题

普通核

内核态有一个全局调度器，负责调度和执行用户线程(Thread)。每个线程都有独立的地址空间（可以多个线程共享同一地址空间），通过系统调用进入内核态时不发生地址空间切换，只有调度器进行线程切换时才进行地址空间切换。因此线程地址空间需要同时映射内核与用户的代码与数据。

注：目前的实现线程==进程，是最基本的调度单位。以后可通过将共享地址空间的线程组成一个“线程组”，来表示进程的概念。在具体实现中，用户线程也被封装为了一个 rust future，通过 executor 进行调度。

IO 核

只有一个地址空间，即内核地址空间，只映射内核的代码和数据，且不会在之后进行切换。也运行一个全局调度器，复制调度和执行用于 IO 的协程。当用户程序创建 IO 共享内存时，会同时在 IO 核的内核地址空间，和普通核对应的用户线程地址空间的用户数据段增加映射。

关键问题

IO 核如何访问不同用户进程的IO buffer而不用频繁切页表？

目前想到的解决方法：（这几种方法可以一起用：共享内存放在特定区域，以优化地址转换；加一个描述缓冲区的数据结构，提高灵活性）

1. 创建专门的共享内存，存放 IO buffer。缺点：IO buffer 需要放在特定的地方，降低了灵活性，增加编程复杂性。
2. 内核要访问用户数据时，手动进行用户虚拟地址到物理地址的转换，然后直接访问物理地址获取数据。缺点：降低安全性？对于不连续的页面每隔 4K 需要一次地址转换，开销大。适合 IO buffer 小到几个页面范围内的情况。
3. 对方案 2 的优化：将 IO buffer 映射连续的物理地址，只需进行一次地址转换；使用大页，每隔 2M 进行一次地址转换；将用户虚拟地址到物理地址的映射结果缓存到专门的区域，以减少每次地址转换的开销（相当于4级页表的4次访存变为1次）。

---

11.11 交流

内核页表隔离

每个进程两个地址空间：用户和内核。用户地址空间只保留少部分内核空间数据，每次系统调用都从用户地址空间切到内核地址空间。防止熔断漏洞。

结论：目前暂时不这样实现

与 IPC 的统一

IO 核的运行可看做另一个进程，IO 核处理用户进程的 IO 请求相当于 IPC。这种设计可与传统的 IPC 统一，即使用 ring buffer，在两个用户进程之间进行 IPC。

---

相关资料

• Asynchronous Programming in Rust，Rust 异步编程
• Async/Await ， 中文
• Tokio Tutorial，中文
• Async programming in Rust with async-std，async-std 中文文档
• Actix Tutorial， 中文
• The Node Experiment - Exploring Async Basics with Rust
• Futures Explained in 200 Lines of Rust，200行代码讲透RUST FUTURES
• A primer to Rust Async，Rust 异步入门
• The Future With Futures
• Rust's Journey to Async/await
• Asynchronous Programming in Rust(Zack Jorquera)
• rust异步编程
• Rust之异步入门
• Epoll, Kqueue and IOCP Explained with Rust
• Green Threads Explained in 200 Lines of Rust

io_uring

• io_uring 文档：https://kernel.dk/io_uring.pdf
• io_uring 相关 syscall 与用户库：https://openanolis.org/en/sig/high-perf-storage/basic/
• io_uring 测试框架：https://github.com/OpenAnolis/perf-test-for-io_uringhttps://github.com/OpenAnolis/io_uring-echo-server
• Redis 的 io_uring 实现：https://github.com/openanolis/redis/tree/feat/io_uring
• Nginx 的 io_uring 实现：https://github.com/openanolis/nginx/tree/feat/io_uring
• AIO 的新归宿：io_uring：https://zhuanlan.zhihu.com/p/62682475
• 基于 io_uring 和绑核的 Rust 异步运行时：https://github.com/DataDog/scipio
• RSoC: improving drivers and kernel (largely io_uring)https://www.redox-os.org/news/io_uring-0/把0换为 1，2，3，4 可以看到进一步的系列文章

async runtime

• 金枪鱼之夜：Build an Async Runtime for Rust from Scratchhttps://tuna.moe/event/2020/rust-async-runtime/
• async collections in githubhttps://github.com/stjepang

多核支持

• [第三版 tutorial 多核支持文档],[代码仓库]