异步操作系统设计方案

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

整体目标

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

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

利用Rust语言和工具链的特征，在操作系统内核中实现细粒度的并发安全、模块化和可定制特征；
- 杨德睿 - rCore-Tutorial-in-single-workspace：模块化的rCore教学操作系统；
- 贾越凯 - arceos：模块化的unikernel操作系统；
利用Rust语言的异步机制，改进操作系统内核的模块结构，优化操作系统内核的并发性能；
- 吴一凡 - Exploring Asynchronous Operating System Design Using Rust
- 杨德睿 - fast-trap：裸机应用程序陷入处理流程的框架，旨在保证处理性能的同时尽量复用代码。
结合Rust语言编译器的异步支持技术，完善操作系统的进程、线程和协程概念，统一进程、线程和协程的调度机制；
- 赵方亮、廖东海 - rCore-N：基于vDSO实现的共享协程调度器框架。它是UnifieldScheduler的后续工作。
- richardanaya/executor: A minimalistic async/await executor for Rust；
- 王文智 - UnifieldScheduler：支持优先级的协程调度器框架；
- 蒋周奇、车春池 - tornado-os：基于共享调度器的异步内核
利用RISC-V平台的用户态中断技术，向应用程序提供的异步系统调用接口，优化操作系统的系统调用访问性能和操作系统的信号和进程通信性能；
- 田凯夫 - uintr：qemu模拟器上的RISC-V用户态中断设计与实现
- 项晨东 - usr-intr：qemu模拟器上的x86用户态中断支持
- 尤予阳、贺鲲鹏 - 软硬协同的用户态中断
开发原型系统，设计用户态测试用例库和操作系统动态分析跟踪工具，对异步操作系统的特征进行定量性的评估。
- 陈志扬 - code-debug：支持Rust语言的源代码级内核调试工具

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

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 函数），更接近于协程。

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

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

异步编程模式

进化过程：

原始形态：回调函数
函数式封装：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使用权，并进入运行状态。

基于 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;
}

基于 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中的异步系统调用也是用两次同步的系统调用来完成的。

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

理想的异步系统调用接口

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

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

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

同步系统调用的执行过程

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

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

异步系统调用的执行过程

第一次异步系统调用时：

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

第二次异步系统调用时：

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

关键问题

协程的实时性问题

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

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

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

协程、线程和进程的调度

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

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

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

问题讨论

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

系统调用接口设计

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

vDSO的好处

vdso官方文档翻译

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

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

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

可能的一些设计目标：

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

2020-10-11 交流：

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

没想清楚

一种可能的思路

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

性能分析

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

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

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

对于异步应用：其用户线程数很少，导致很少发生内核态 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：

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

背景：

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

中断编号：

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

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

Cache：

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

valid	used（可选）	编号的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

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

用户态寄存器 uie.usoft、sideleg.usoft 被置位，utvec的函数由内核提供
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 |，长度几个字节。
异常结束，返回A，继续执行直到yield或时钟中断，经内核调度到B。
B被调度，发现消息队列非空，进行相应处理。处理完成后，向A发送信息 | B_pid | A_pid | data |，call 进入用户态中断处理函数。查表，A_pid 匹配，将报文添加到A的消息队列中。
1. 消息队列与跳板类似，可以由satp计算得到
处理完成，返回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的内核模块

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

实现方案

目标用户程序

基于事件循环机制的异步应用，模型为每个用户线程为一个大事件循环，在循环开头通过 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。
传统面向过程的同步应用，每个线程都是从头执行到尾，它并不会关心每个调用是否被阻塞，对于它来说完全是透明的。

初步实现方案

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

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

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

TODO

日志

20210227-RISC-V进程地址空间切换交流

吴一凡介绍目前的代码状态

内核与用户进程各一个地址空间，共同有一个Trampoline（alltrap的代码）和TrapContext（alltrap的数据）；Trampoline用于在用户地址空间和内核态时访问。

讨论

trampoline区域

trampoline区域的初始化在哪？

trap_return, 链接时，把相关代码放到内核中；
map_trampoline建立映射
1. 用户态是不能访问的；
2. 中断时，中断进入时硬件保存现场并不直接访问这个区域的内存，而是放在寄存器中；
3. 这个区域只在内核态且是用户地址空间时访问；
4. 这两个页表的设置是一样的，可以保证它只在内核态可以访问；
5. 中断服务例程的地址在链接时得到；

这个思路的原始出处是哪？

XV6；MIT也没有维护X86的版本了。

内核进程中的用户进程页表

每个进程在内核中有一个页表数据结构；
用户页表项：在内核中是线性映射；
每个用户进程的页表逻辑地址是不同的；

用户进程的内核栈

目前每个用户进程在内核进程中有一个自己的内核栈；
陈老师认为，每个用户进程必须有自己的内核栈，向勇认为可以没有；有兴趣时，同学可以来讨论。

系统调用时用户进程与内核进程间的切换过程

有可能基于Trampoline完成整个切换过程吗？把内核中处理系统调用和调度的功能独立出来，形成两个或一个进程；这是有可能的；这个工作应该是hypervisor的功能；

用户进程切换

有可能进行进程间的切换吗？有可能；有时间时，再进入进一步的讨论；

内核态的中断处理

在内核态的中断的处理与用户态的有什么不同？没有地址空间切换了，服务一定是不一样的，可能还有其他区别；

建议

其他同学在看明白后，可以给出自己的理解和想法描述出来；
吴一凡：改异步方案文档；

20201111-交流

内核页表隔离

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

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

与 IPC 的统一

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

20201101-交流

目前进展：基本完成普通核部分的内核功能，有简单的 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。

20201014-讨论的实现方案

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

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

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

前期简化

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

用户程序的实现

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

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

TODO

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

是否要和 io_uring 完全一样？

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

最小原型系统

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

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

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

open
read
write
close

测试环境：

RISCV64，QEMU/K210
memory fs/SD 卡

实现步骤

方案一：从头开始造

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

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

其他问题

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

（第一版无需考虑）

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

是否可在普通核开中断？

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

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

普通核

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

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

IO 核

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

关键问题

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

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

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

Files

design.md

Latest commit

History

design.md

File metadata and controls

异步操作系统设计方案

整体目标

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

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

IO 接口类型：同步与异步

I/O接口的性能对比

事件机制：中断与轮询

中断和轮询的适用场景

中断分发和处理过程

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

协程与线程的对比

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

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

异步编程模式

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

使用 yield 实现 poll

使用 poll 实现 yield

异步系统调用

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

理想的异步系统调用接口

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

同步系统调用的执行过程

异步系统调用的执行过程

关键问题

协程的实时性问题

协程、线程和进程的调度

问题讨论

系统调用接口设计

vDSO的好处

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

一种可能的思路

性能分析

研究和开发任务划分

异步系统调用

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

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

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

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

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

快速中断

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

IPC类用户态中断的过程

中断信息的“转发表”

内核的进程化改造

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

异步操作系统调度器

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

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

Rust语言的协程支持扩展

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

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

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

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

内核中的异步支持

在内核中引入Rust异步机制

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

实现方案

目标用户程序

初步实现方案

日志

20210227-RISC-V进程地址空间切换交流

吴一凡介绍目前的代码状态

讨论

trampoline区域

内核进程中的用户进程页表

用户进程的内核栈

系统调用时用户进程与内核进程间的切换过程

用户进程切换

内核态的中断处理

建议

20201111-交流

内核页表隔离

与 IPC 的统一

20201101-交流