异步操作系统设计方案

异步操作系统设计方案 #

  • v1：20201013-异步操作系统设计方案.docx，由王润基起草；
  • v2：20201213-异步操作系统设计方案.md
  • v3：20210408-异步操作系统设计方案.docx
  • v4：20210506-异步操作系统设计方案.md
  • v5：20210526-异步操作系统设计方案.md
  • v6：20210824-异步操作系统设计方案.md
  • v7：20230318-异步操作系统设计方案.md
  • [v8]

整体目标 #

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

已完成或正在进行中的工作 #

  1. 利用Rust语言和工具链的特征，在操作系统内核中实现细粒度的并发安全、模块化和可定制特征；
  2. 利用Rust语言的异步机制，改进操作系统内核的模块结构，优化操作系统内核的并发性能；
  3. 结合Rust语言编译器的异步支持技术，完善操作系统的进程、线程和协程概念，统一进程、线程和协程的调度机制；
    • 赵方亮 - async-os：支持TAIC中断控制器的异步操作系统；
    • 廖东海、李龙昊、朱懿、杨金博等 - ReL4（在线文档）：seL4微内核的Rust重写和异步优化；
      • 赵方亮、廖东海 - rCore-N：基于vDSO实现的共享协程调度器框架。它是UnifieldScheduler的后续工作。
    • 杨长轲 - embassy_preempt：uCOSII的Rust重写和异步优化；
    • 王文智 - UnifieldScheduler：支持优先级的协程调度器框架；
    • 蒋周奇、车春池 - tornado-os：基于共享调度器的异步内核
  4. 利用RISC-V平台的用户态中断和软硬协同技术，向应用程序提供的异步系统调用接口，优化操作系统的系统调用访问性能和操作系统的信号和进程通信性能；
  5. 开发原型系统，设计用户态测试用例库和操作系统动态分析跟踪工具，对异步操作系统的特征进行定量性的评估。

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

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 扩展指令集实现了用户态中断，但目前标准还在起草阶段，模拟器和物理机都没有实现。如何利用用户态中断提高用户态驱动的性能是值得探讨的话题。

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

任务：由若干相互调用的函数组成、具备一定功能的指令执行流，是CPU调度的最基本调度单位。

任务执行上下文环境 #

  • 地址空间（进程）
  • 特权级（进程或线程）
  • 任务状态：（协程）
    • 运行状态：正在占用CPU和函数调用栈上执行任务中指令序列；
    • 等待状态：正在等待某种事件对应的执行条件；
    • 就绪状态：正在等待可用CPU资源，以进入执行状态；
  • 函数调用栈（线程）：处于等待状态和就绪状态的任务是否占有函数调用栈
    • 线程：在整个生命周期占有指定的函数调用栈；
    • 协程：处于执行状态时占用函数调用栈；主动让权时释放占用的函数调用栈；

任务切换 #

根据任务可能发生切换的时机，可分为：

  • 抢占式：随时可能发生切换（时钟中断），保存状态多，切换开销大，保证实时性。
  • 协作式：调用特定操作时发生切换（yield），保存状态少，切换开销小，不保证实时性。

进程、线程和协程 #

  • 进程：每个进程有独立的地址空间，因此有页表切换开销；内核可以是一个独立的进程，有自己的独立地址空间，也可以是用户进程地址空间中的一部分；每个用户进程都有自己的独立地址空间。在异步操作系统中，内核作为独立的进程时，有自己的独立的页表，系统调用过程会变成一种特殊和优化的进程切换。
    • 类似于传统的操作系统中进程切换代码是在两个进程中共享的，把内核视为独立进程后，系统调用也成了进程切换。目前每个用户进程中还有一段内核态代码，用于完成切换过程。
  • 线程：每个线程有独立的函数调用栈，线程切换时需要保存和恢复全部寄存器。
    • 当内核与用户线程不在一个地址空间中，每个用户线程只有用户栈，不存在对应的内核栈；每个内核线程只有内核栈，不存在对应的用户栈。
  • 协程（指无栈协程）：可以理解为状态机转移函数，执行时可共用同一个函数调用栈。
    • 所有协程在执行态时一定会占用一个函数调用栈。
    • 在编译器或函数库的支持下，编译时会将async函数变换成状态机变迁和同步函数的组合；异步函数中跨越 await 的变量将存放在 Future 对象中（一般在堆上），其它变量只需放在栈上或寄存器中。这样，协程在主动让权时会出让处于空状态的函数调用栈。
    • 由于中断或异常导致的执行态协程暂停时，无法回收占用的函数调用栈，从而成为一个线程。

与原来概念的对比：

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

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

协程与线程的对比 #

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

  • 作为协程的执行流只可能在有限的await语句处主动让权进行上下文切换，因此需要保存的状态信息较少；
    • 主动让权时的协程切换无需换函数调用栈，访存局部性更好。协程切换相当于一次函数返回和调用，寄存器的使用遵守调用约定ABI，一般不会涉及全部寄存器的保存和恢复。所以协程的切换开销更小。
  • 任何执行流都可能在任意指令处被中断并进行上下文切换，因此需要保持整个函数调用栈的占用。该执行流可以视为一个线程。

理想的上下文切换过程（贾越凯细化） #

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

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

  • 协程切换（栈复用）：如果当前运行协程与选中的下一个就绪协程在同一个进程的同一个线程中，这时的协程切换就是在当前线程内的函数调用。
  • 线程切换（栈切换）：被抢占时的切换或主动让权后选择了占有函数调用栈的任务，这时的上下文切换就是在当前进程内的线程切换，需要执行函数库形式实现的线程库代码，进行用户堆栈保存和切换。
  • 进程切换（特权级切换）：如果当前运行协程与选中的下一个就绪协程在不同进程中，这时的协程切换就是在由操作系统内核支持的进程切换，需要保存当前用户堆栈，并切换到内核进程执行内核的调度器代码，以完成进程地址空间、用户堆栈和协程维护数据结构（即是由编译器生成代码维护的协程控制块）。

异步编程模式 #

进化过程：

  • 原始形态：回调函数
  • 函数式封装：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;
}
  1. 基于 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. 系统调用请求
    1. （第一次请求时）创建支持异步系统调用的请求队列和响应队列对应的共享存储区域；
    2. 填入系统调用请求信息；
    3. （填入第一次请求后）使用事件通知机制通知内核进行响应；
    4. 暂停当前任务执行流，修改任务状态为等待状态；
    5. 查询响应队列中的待处理返回结果；如果有新的返回结果，将对应请求方任务状态从等待状态改为就绪状态；
    6. 选择最高优先级的就绪请求方任务进入执行状态；
    7. 任务上下文切换：可能是进程、线程或协程切换；
  3. 系统调用响应
    1. （第一次收到请求通知时）收到系统调用请求通知后，将对应内核服务任务状态从等待状态改为就绪状态；
    2. 选择最高优先级的就绪服务任务进入执行状态；
    3. 解析请求队列中的系统调用参数；
    4. 执行系统调用服务任务；
    5. 服务任务完成后，将返回结果填入系统调用响应队列；
    6. （填入第一次响应后）使用事件通知机制通知请求方接收返回结果；
    7. 查询请求队列中的待响应系统调用请求；如果有新请求，转第3步解析系统调用参数；
    8. 选择下一个就绪任务进入执行状态；
    9. 任务上下文切换：可能是进程、线程或协程切换；
  4. 系统调用结果返回
    1. 收到系统调用返回通知后，将对应请求方任务状态从等待状态改为就绪状态；
    2. 选择最高优先级的就绪请求方任务进入执行状态；
    3. 解析响应队列中的系统调用返回结果；

下图演示了此调用流程，

异步系统调用流程图

上图中，请求队列和响应队列都可以视为无锁的双端队列，在用户与内核间共享，

  1. 用户在执行过程中发起系统调用，该协程挂起；
  2. 用户将请求填入请求队列尾端，首次填入后非阻塞地通知内核处理请求，然后向队尾填入后续请求；
  3. 内核依次从请求队列首端取出请求、解析并调用对应的服务例程；
  4. 内核将响应填入响应队列尾端，首次填入后非阻塞地通知用户处理响应，然后向队尾填入后续响应；
  5. 用户依次从响应队列首端取出响应、解析并恢复对应协程执行状态．

关键问题 #

协程的实时性问题 #

无栈协程是一种非抢占式的任务调度机制，对时间敏感的任务可能无法及时调度运行。例如 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的好处 #

vdso官方文档翻译

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

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

正在进行的相关工作： 罗熙 - [vDSO]

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

可能的一些设计目标：

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

2020-10-11 交流：

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

没想清楚

一种可能的思路 #

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

性能分析 #

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

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

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

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

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

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

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

研究和开发任务划分 #

异步系统调用 #

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

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

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

一个比较近期的目标是，在CPU上实现用户态中断，然后利用用户态中断来改进操作系统的信号机制。

用户态中断的设计文档：以按键为例（但其实讨论时更多想的是以信号为例） #

用户态中断的情况

源目的传递的内容备注
外部中断A核 x进程 U态核id使用标签传递核id以标识由哪个核处理
A核 x进程 U态A核 y进程 U态核id（同一核，一位标识此项不检查，或加特殊id标识自己）进程id（安全，用户态不能知道目的进程的页表基址等，需硬件或S态处理）中断信息（或信息的地址）
A核 x进程 U态B核 y进程 U态核id进程id中断信息
A核 x进程 S态A核 y进程 U态同一核进程id中断信息
…
核id 8bit 256个？进程id 16bit 65536个？中断信息源信息
64位仍有5字节存后面的信息

32位如何处理？（需要考虑32位机吗）

todo：

  1. 全部进程响应（温柔地劝桌面上所有应用结束）
  2. 一组进程用默认的中断处理例程

背景：

  1. 用户态中断会频繁建立和撤消；
  2. 内核控制用户态中断映射关系的建立和_撤消_（还是S态做，相当于缓存不命中（初始化）——都是先到S态，然后csrw再写要跳的或非法的地址）；
  3. 用户态中断响应过程中不需要内核参与（会有类似缓存不命中的情况需要处理）；
  4. 每个进程应该有自己的中断处理例程（所以xtvec不够用了）（用户态进程的中断处理例程由内核提供，置于跳板区域或由vDSO类似的做法实现）
  5. 某中断在三个态都要处理时，先不设置{m,s}ideleg，在M态处理。然后设置mideleg，在S态处理。再然后设置sideleg，在用户态处理——这样在处理用户态中断时，不用考虑发给其他态的处理例程了
  6. 中断的源和目的应该以线程为单位区分（多核处理同一进程的不同线程时，给哪个核？）（第四条应该是每个线程有自己的处理例程？）
  7. 存在S态向U态程序发中断的情景，这时应该跳转到U态处理中断，而不是S态

中断编号：

我们要用编号来查表，没有编号就没有表，因此编号的生成是很重要的（快速、简单、不会碰撞）（可能会碰撞，但目前没法解决）

  1. 板子上的按钮开关等可以给一个固定的编号，触发时给固定的目标进程触发固定的中断类型
  2. 进程之间的信号不能像按钮那样固定，需要用中断源（用页表基址satp、栈基址之类的算）、中断类型（外部/软件/时钟，RISC-V相同的区分）和目的线程（kill哪个，用和中断源同样的信息）（用硬件哈希算成和固定编号同样长度，或者拼起来都行，我觉得）（可能之后可以分开考虑，现在不管）

Cache：

Cache的一行如下（因为不必写回内存，所以没有dirty；因为只有一路，换出时不用选换哪个，所以没有used）：

validused（可选）编号的tag中断处理例程地址
  • 在写入时 将编号写入几个CSR寄存器（n*32位），用于控制Cache内容写在哪一行 valid和tag是一个CSR寄存器（32位） 地址是一个CSR寄存器（32位）
  • 具体CSR的地址可以在V20190608-Priv-MSU-Ratified第七页中找Custom read/write的（暂定所有行用同样的CSR地址，由硬件决定写入哪一行（可是写入例程地址时，源的编号没有给，我怎么知道写在哪？同样以新增CSR实现））（目前用户态的0x800-0x8FF）
  • 只能在S态写
  • 读取时利用编号像Cache一样寻址 写时当CSR寄存器是为了方便更新Cache内容，这样可以直接用csrw指令写入

Cache里有中断信息时，中断的处理流程：

  • 程序运行在任意态上（因为有S态给U态线程发中断的需求），mstatus.uie全局中断使能开启、uie.ueie外部中断使能开启（外部是因为按键是外部）
  • 按按键，在uip.ueip的中写入1。
  • mstatus.uie = 1, uie.ueie & uip.ueip = 1, mideleg、sideleg的对应位都是1 我们可以在用户态处理这个中断。
  • 用中断编号寻址，查用户态中断专用的Cache 假设编号有4位，用后两位作为地址，在已批准中断Cache里读取内容（应该是这个周期就能读出来，否则中断要过几个周期才能跳转到中断处理例程）
  • 判断valid是不是1，是1就可以下一步
  • 取出来的内容中有tag，用tag和编号前两位比较，如果相同则命中
  • 跳到内容中的地址处理

Cache里没有中断信息，初始化的方式；Cache里有其他中断的信息，撤销其他中断，写入当前中断的方式（其实仍然是初始化）：

  • 如果valid不是1（没有建立信道）或者tag不同（Cache冲突了），像普通的中断一样处理：跳到stvec，特权级变为S 在位于stvec的S态中断处理程序中决定要跳转到哪（根据读Cache的编号），跳转前把要跳转的地址和该中断源的编号写入Cache（方法是用csrw+标准中留白的CSR寄存器地址：csrw xxx, valid+tag; csrw yyy, handler_addr）。 这样下次同样的中断来临时，就可以在Cache中查到valid=1，tag相同的内容了 即使这个扩展尽量避免使用软件，在一开始的时候仍然要依赖软件

撤销已经批准的用户态中断的方式：

  • 陷入S态，用csrw写入CSR寄存器的方式，将valid位置0，同时清空地址位 （可以看出，建立、撤销、替换都是切换到S态处理）

使用用户态中断处理外设请求 #

使用用户态中断进行IPC时的处理时机 #

通常的中断处理过程需要保存和恢复上下文、清空流水线（硬件完成），如果发生页表切换还需要清空TLB，时间开销较大，因此应当尽量减少切换的次数。注意到进程调度时，上下文和页表切换是不可避免的，故考虑将大多数中断处理推迟到调度时处理（仅允许极少数特殊的中断打断当前进程，切换至目标进程立即处理。具体细节需进一步探讨）；而多核情况下，如果中断的目标线程恰在某个hart上运行，那么由该hart处理可以不需要切换页表。综上，用户态（软件）中断的处理流程可设计如下：

0.xxx通过一次系统调用获得yyy的pid

  1. hart A 上的进程 xxx 发起一个目标进程为 yyy 的用户态中断
    1. 发送信息：目的进程id，参数
  2. 硬件检查 yyy 是否在某个 hart 上运行，如果是，在该 hart 上置位 uip.USIP 触发用户态中断，转入 yyy 的 ISR 进行处理
  3. 若 yyy 不在任一 hart 上，则触发一个内核中断，将中断信息写入 yyy 的进程控制块中，在下一次调度到 yyy 时，首先进行处理（此时类似于信号机制）
    1. utvec的组成：内核提供基本的，用户注册一部分
  4. 同时提供一个同步式的接口，在 xxx 所在 hart 上立刻进行上下文切换，进入 yyy 的 ISR 处理

为了避免恶意程序利用用户态中断机制进行攻击，可以考虑加入令牌等权限控制机制。

具体实现上，结合前述 Cache 机制，可以每一个 hart 准备一行 Cache ，仅内核可读写；Cache 内容可以包括进程 ID 和权限控制的内容（ ISR 基址写入 utvec 即可），每次进程切换时，由内核更新其中内容。命中时，按照前述方案跳转到 utvec，不命中时，触发内核中断（可以考虑硬件置为指令异常/软件中断进行处理；也可以是跳板中进行 ecall）

快速中断 #

https://riscv.org/wp-content/uploads/2018/05/08.45-09.10-RISCV-20180509-FastInts.pdf

https://github.com/riscv/riscv-fast-interrupt

对于IPC和系统调用触发的中断，考虑将其ISR置于当前地址空间，尽可能快地完成，减小上下文切换开销，尤其是避免用户进程——内核进程——用户进程这样的双重切换（注意特权级和进程并不完全绑定在一起）

用户态中断/IPC的参数（信息）传递 #

传递的信息量有多少？

  • 对于同一核的不同进程，可以使用寄存器进行传递
  • 对于不同核的不同进程，需要通过内存进行传递
    • Binder机制？
      • 将源进程需要发送的信息物理页remap到目的进程
      • 需要内核参与，开销？
    • 可以使用专用Cache吗

IPC类用户态中断的过程 #

单核：

现假定只有一个核，有用户态进程A和B，假定进程id用16位表示。

  1. 用户态寄存器 uie.usoft、sideleg.usoft 被置位，utvec的函数由内核提供
  2. A意图发出一条请求，传信息给B，但无B的进程id，请求FFFF（表示不知道目的进程id），call 进入内核提供的用户态中断处理函数。FFFF 触发异常，陷入内核态进行查询，得到进程id（B_id）（如何查询？）。内核态将报文添加到B的消息队列中，并在转发表中存储相关信息。
    1. 请求的参数组成：| src_pid | dst_pid | priority | buffer_addr | buffer_len |。其中priority用于决定是否立即打断，还是仅添加到消息队列。通过buffer进行数据传输，长度不定，可能可以考虑类似Binder机制，即A将数据存放在一页中，这一页直接转为B的一页。下面出于简化考虑，buffer视为只有几个字节的数据 data 存在 addr 和 len占用的空间。
    2. 内核查询后，转发表中存储两条数据：| A_pid | A_satp | 和 | B_pid | B_satp |，用于之后的快速转发。
    3. B的消息队列，权限rw–rw，即内核可读可写，其他进程不可直接读写，B可读可写。队列中存储消息元数据组成的队列（可能换为优先级队列），元数据为 | req_pid | data |，长度几个字节。
  3. 异常结束，返回A，继续执行直到yield或时钟中断，经内核调度到B。
  4. B被调度，发现消息队列非空，进行相应处理。处理完成后，向A发送信息 | B_pid | A_pid | data |，call 进入用户态中断处理函数。查表，A_pid 匹配，将报文添加到A的消息队列中。
    1. 消息队列与跳板类似，可以由satp计算得到
  5. 处理完成，返回B，继续执行直到yield或时钟中断，经内核调度到其他进程。

多核：

现假定有两个核 hart 0 和 1，hart 0 上有进程 A，hart 1 上有进程 B。

中断信息的“转发表” #

交换机的工作方法： 收到来自端口 A 的数据包，源 MAC 地址与端口 A 绑定，写入表 目的端口 B 的主机应答数据包，将该数据包的源 MAC 地址写入表 端口 - MAC

收到来自进程 A 的中断请求，带有 A 的页基址和 A 的 id （是否允许用户态进程直接获取自己的基址和id？是否允许第一次经过内核处理后无区别）。内核态进程管理一个表，存储 (id, addr)，硬件表缓存以之后加速。当进程退出时需删除相应信息。（或类似交换机设置 Age）

需参考 L3 交换机的 FIB。

一个可能的硬件设计

+----------+
|   core   |   +----------+
|  +----+  |   |          |
|  |  1 |--|---|    2     |
|  +----+  |   |          |
|          |   +----------+
+----------+
1: 一个核内的“转发表”和中断模块
  - 接收外部中断信号
  - 提供“转发表”给核查询 （一个特殊的DCache？）
  - 向外发送中断请求
2: 核共享的一个中断转发模块？将来自核A的中断转给核B？
  - 一个“交换机”
  - 来自外部的中断也经过它，然后可以去掉核的标签，保留进程/线程/协程的标签？

内核的进程化改造 #

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

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

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

异步操作系统调度器 #

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

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

相关资料 #

io_uring #

async runtime #

多核支持 #

RISCV SPEC #

May 29, 2025
Edit this page