2024 秋冬季开源操作系统训练营

导学阶段

这个阶段主要是介绍 linux 和 github的基本操作。

基础阶段-Rust 编程

在这个阶段，学员将深入学习 Rust 编程语言的基础知识和高级特性。主要内容包括 Rust 的语法结构、内存管理机制、并发编程和错误处理等。

笔记：

Rust编程 基础知识

梳理后

变量与可变性:

使用 let 声明变量

let x = 5;

默认不可变（一旦赋值，不可修改）

意义：防止意外的数据修改和并发问题

如何可变？使用 mut 关键字

let mut x = 5;

常量声明

使用 const 而不是 let

声明值只能为 常量表达式

（即，不可以是只能在程序运行时才能计算出的值）

const THREE_HOURS_IN_SECONDS: u32 = 60 * 60 * 3;

基本数据类型-原生类型（primitives）

标量类型

有符号整数 (signed integers) : i8, i16, i32, i64, i128 和 isize （指针宽度）

无符号整数 (unsigned integers) : u8

浮点数 (floating point): f32, f64

char (字符) : 单个 Unicode 字符，如 ‘a’

bool (布尔型) : 只能是 true 或 false

单元类型 (unit type) : ()。

复合类型

数组 (array) : 如 [1, 2, 3]

元组 (tuple) : 如 (1, true)

元组 (tuple)

把一个或多个其他类型的值组合进一个复合类型

长度固定（声明后长度不变）

let tup: (i32, f64, u8) = (500, 6.4, 1);

如何获取单个值？

1. 使用点号 (.) 加值的索引

2. 使用模式匹配 (pattern matching) 来解构 (destruction) 元组值

   1 2 3

   let tup = (500, 6.4, 1); let (x, y, z) = tup; println!("The value of y is: {y}");

数组 (array)

在栈上分配，单个内存块

声明

1. 直接声明

   1	let a = [1, 2, 3, 4, 5];

2. 指定元素类型和元素数量

   1	let a: [i32; 5] = [1, 2, 3, 4, 5];

3. 指定初始值和元素个数

   1	let a = [3; 5];

使用

使用索引来访问

函数

声明

使用 fn 关键字来声明

1
2
3
4
5
6
7

fn main() {
    println!("Hello, world!");
    another_function();
}
fn another_function() {
    println!("Another function.");
}

if 表达式

loop 循环

循环标签

改变 break 或 continue 的作用对象

while 循环

for 循环

所有权概念

变量作用域与变量隐藏

函数参数的所有权

函数返回值

引用与借用

可变引用

String

String slice

结构体

元组结构体

Vector

定义

可变长数组，只能存储相同类型的值

使用

Vec::new() 可以新建空 vector

1
2

let v: Vec<i32> = Vec::new();
//这个 Vec<i32> 可以不加

vec! 宏，会根据我们提供的值来创建一个新的 vector

1

let v = vec![1, 2, 3];

使用 push 可以向 vector 中增加元素

hashmap

定义

HashMap<K, V> 类型储存了一个键类型为 K 对应一个值类型为 V 的映射

其通过一个 哈希函数（hashing function）来实现映射，决定如何将键和值放入内存中

使用

可以使用 new 来创建

使用 insert 增加元素

使用 get 方法来从 hashmap 中获取值

1
2
3
4

use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50)

第二节

枚举 enum

枚举 Option

定义

1
2
3
4

enum Option<T>{
    None,
    Some(T),
}

使用

用 unwrap() 获取内部值

作用域 scope

就是作用范围吧

同一个作用域不能有两个相同名称的项 → C++ 中的变量名冲突

（可以使用一下工具来解决名称冲突？？？）

模块系统 the module system

模块系统可以将 crate 中的代码分组和封装，提高可读性和重用性

包 Packages

Cargo 的一个功能，允许构建、测试和分享 crate

包是提供一系列功能的一个或者多个 crate , 包含一个 Cargo.toml 文件

Crates

一个模块的树形结构，它形成了库或二进制项目

crate 是 Rust 在编译时最小的代码单位，有两种形式：二进制项和库

crate root 是一个源文件，是 crate 的根模块

crate 的约定

src/main.rs 是一个与包同名的二进制 crate 的 crate 根

src/lib.rs 是一个与包同名的库 crate 的 crate 根

src/bin 目录下的每个文件都会被编译成一个独立的二进制 crate

模块 Modules 和 use

允许你控制作用域和路径的私有性

use 关键字

可以在一个作用域内创建一个项的快捷方式，减少长路径的重复

类似于 Java 的导包？

as 关键字

配合 use 使用，就是给快捷方式重命名

一些调用项的方式

1
2
3
4
5
6

//例如 xxx 模块的 yyy 子模块下定义了一个 zzz
crate::xxx::yyy::zzz;

use crate::xxx::yyy::zzz;//之后就可以直接使用 zzz 了

use crate::xxx::yyy::zzz as z;

私有和公有

默认所有内容私有

pub 关键字

可以将模块或模块内的项标记为公开的

模块树

crate 根文件 (src/lib.rs 或 src/main.rs) 是 crate 模块结构的根，也是名为 crate 的隐式模块的根

在 crate 根文件中，可以声明新的模块

使用 mod 关键字和花括号或分号

1
2
3

mod a_module {
    //something...
}

如何寻找

内联（以大括号结尾时）

在文件 src/xxx.rs

在文件 src/xxx/mod.rs

在其它文件中，可以定义子模块

使用 mod 关键字和花括号或分号，并在以父模块命名的目录中寻找子模块代码

模块树可以用来展示 crate 中的模块层次结构，以及模块之间的父子和兄弟关系

路径 path

一个命名项（结构体、函数或模块等）的方式

绝对路径 absolute path

以 crate 根 (root) 开头的全路径

对于外部 crate 的代码，是以 crate 名开头的绝对路径

对于当前 crate 的代码，则以字面值 crate 开头

相对路径 relative path

从当前模块开始，以 self, super 或当前模块的标识符开头

绝对路径和相对路径都后跟一个或多个由双冒号分割的标识符

专业阶段- OS设计实现

第三章：多道程序与分时多任务系统

ch3 要求我们完成的任务具体要求如下：

• 实现系统调用 sys_task_info，系统调用号为 410
• 该系统调用需要返回当前任务的以下信息：
  • 任务状态（必定为 Running）
  • 任务使用的系统调用及其调用次数
  • 系统调用时刻距离任务第一次被调度时刻的时长（单位ms）
• 使用 TaskInfo 结构体来存储这些信息
• 系统调用成功时返回 0，失败时返回 -1
• 注意：调用 sys_task_info 本身也会被计入系统调用次数

思路：

sys_task_info 需要三个信息，我们一个一个来，

任务状态：第一个是任务状态，这个实现起来比较简单，甚至因为在这个系统里，查询的是当前任务的状态，因此 TaskStatus 一定是 Running。

系统调用时刻距离任务第一次被调度时刻的时长：我们需要的这个时长等于 当前时刻减去第一次被调度的时刻，当前时刻很好获取，利用get_time_ms()函数就可以直接获取，而另外一个 则需要为任务控制块添加新的字段 ，用于记录第一次被调度的时长，这样我们就可以通过任务管理器直接地获取某任务初次调用时刻了。

任务使用的系统调用及其调用次数:我的方法和提示里给出地方法相同 因为系统调用号一定小于 500，所以直接使用一个长为 MAX_SYSCALL_NUM=500 的数组做桶计数。同样也直接在 任务控制块中添加 数组，实现把各个任务的系统调用次数数组与该任务绑定。在此之后，我们直接到系统调用前syscall/mod.rs:syscall 增加相应任务的相应系统调用类型的调用次数即可。

最后我们直接创建一个TaskInfo类型保存如上三种数据，并利用sys_task_info中的*mut类型参数，把Taskinfo的内容传回用户态即可完成该功能。

总的来说作为第一个任务，用来熟悉内核编程，还算比较简单。

问答题-lab1

第四章：地址空间

ch4要求我们完成的具体内容如下：

重写 sys_get_time 和 sys_task_info
引入虚存机制后，原来内核的 sys_get_time 和 sys_task_info 函数实现就无效了。请你重写这个函数，恢复其正常功能。
mmap 和 munmap 匿名映射 mmap 在 Linux 中主要用于在内存中映射文件， 本次实验简化它的功能，仅用于申请内存。
请实现 mmap 和 munmap 系统调用，mmap 定义如下： fn** sys_mmap(start: usize, len: usize, port: usize) -> isize - syscall ID：222 - 申请长度为 len 字节的物理内存（不要求实际物理内存位置，可以随便找一块），将其映射到 start 开始的虚存，内存页属性为 port
参数：
start 需要映射的虚存起始地址，要求按页对齐
len 映射字节长度，可以为 0
port：第 0 位表示是否可读，第 1 位表示是否可写，第 2 位表示是否可执行。其他位无效且必须为 0
返回值：执行成功则返回 0，错误返回 1
说明： 为了简单，目标虚存区间要求按页对齐，len 可直接按页向上取整，不考虑分配失败时的页回收。
可能的错误： start 没有按页大小对齐 - port & !0x7 != 0 (port 其余位必须为0) - port & 0x7 = 0 (这样的内存无意义) - [start, start + len) 中存在已经被映射的页 - 物理内存不足

思路：

我们先说sys_get_time和sys task_info 这两个函数的重写：

首先我们来说说为什么这两个函数会失效，在ch3中我们的系统调用 利用*mut类型指针来将数据直接地写入用户态中的地址，但是在ch4中，我们将用户态和内核态都分别做了不同的地址映射，这导致我们没办法像ch3那样直接利用_ts来写入数据，因为ch4中传入的是用户态中的虚拟地址，必须借助页表机制，将虚拟地址转换为物理地址，来修改。获取 time 和 TaskInfo的步骤和之前ch3中提到的方式类似。

需要注意的是，我们写入的数据结构可能存在如下所示的跨页的问题，

/// YOUR JOB: get time with second and microsecond /// HINT: You might reimplement it with virtual memory management. /// HINT: What if [TimeVal] is splitted by two pages ?

所以我们不能把数据一次性全部写入，这里我选择的办法是将数据转换为字节数组 并依次写入。

mmap和unmmap:

首先来说mmap：

mmap需要实现的是将一段虚拟地址进行页面映射，想要实现这个功能，我们需要在进程的地址空间中加入添加新的页面映射，而该系统正好提供了为地址空间提供了insert_framed_area方法，用于插入新的逻辑段，这样的话情况就会变得很简单。

首先我们根据可能的错误对函数给出的参数进行对应的判断，并且通过port得到MapPermission。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

if _start % PAGE_SIZE != 0 || _port & !0x7 != 0 || _port & 0x7 == 0 {
return -1;

}
let portpomis = Portpomiss::from_bits_truncate(_port as u8);
let mut flag:MapPermission=MapPermission::empty();
flag|=MapPermission::U;
if portpomis.contains(Portpomiss::R){
     flag|=MapPermission::R;
}
if portpomis.contains(Portpomiss::W){
     flag|=MapPermission::W;
}
if portpomis.contains(Portpomiss::X){
    flag|=MapPermission::X;
}

之后我们检查虚拟页面是否已经被映射过

1
2
3
4
5
6
7

for vpn in vpn_range {
    if let Some(pte) = inner.tasks[cur].memory_set.translate(vpn) {
        if pte.is_valid() {
            return -1;
        }
    }
}

最后我们直接添加页面映射

inner.tasks[id].memory_set.insert_framed_area(_start, _end, port);

问答题-lab2

第五章：进程及进程管理

ch5要求我们具体完成的内容如下:

spawn 系统调用定义( 标准spawn看这里 )：

`fn sys_spawn(path: *const u8) -> isize`

• syscall ID: 400
• 功能：新建子进程，使其执行目标程序。
• 说明：成功返回子进程id，否则返回 -1。
• 可能的错误：
  • 无效的文件名。
  • 进程池满/内存不足等资源错误。

TIPS：虽然测例很简单，但提醒读者 spawn 不必 像 fork 一样复制父进程的地址空间。

stride 调度算法

算法描述如下:

(1) 为每个进程设置一个当前 stride，表示该进程当前已经运行的“长度”。另外设置其对应的 pass 值（只与进程的优先权有关系），表示对应进程在调度后，stride 需要进行的累加值。

1. 每次需要调度时，从当前 runnable 态的进程中选择 stride 最小的进程调度。对于获得调度的进程 P，将对应的 stride 加上其对应的步长 pass。
2. 一个时间片后，回到上一步骤，重新调度当前 stride 最小的进程。

可以证明，如果令 P.pass = BigStride / P.priority 其中 P.priority 表示进程的优先权（大于 1），而 BigStride 表示一个预先定义的大常数，则该调度方案为每个进程分配的时间将与其优先级成正比。证明过程我们在这里略去，有兴趣的同学可以在网上查找相关资料。

其他实验细节：

• stride 调度要求进程优先级 ≥2，所以设定进程优先级 ≤1 会导致错误。
• 进程初始 stride 设置为 0 即可。
• 进程初始优先级设置为 16。

为了实现该调度算法，内核还要增加 set_prio 系统调用

思路：

我们先说spawn系统调用:

就如同TIPS一样，我们不需要复制父进程的地址空间，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

pub fn sys_spawn(_path: *const u8) -> isize {
    trace!(
        "kernel:pid[{}] sys_spawn NOT IMPLEMENTED",
        current_task().unwrap().pid.0
    );
    let current_task = current_task().unwrap();
    let token =current_user_token();
    let path = translated_str(token, _path);
    let tcb=Arc::new(TaskControlBlock::new(get_app_data_by_name(path.as_str()).unwrap()));
    let mut inner=tcb.inner_exclusive_access();
    let mut pin=current_task.inner_exclusive_access();
    inner.parent=Some(Arc::downgrade(&current_task));
    pin.children.push(tcb.clone());
    drop(inner);
    let pid = tcb.pid.0 as isize;
    add_task(tcb);
    pid
}

我们直接用 app_data来创建TaskControlBlock而跳过了复制父进程的地址空间，并将他连接到父进程的子进程上，这样才能在sys_waitpid中被遍历到。然后把他加入任务管理器。就可以通过测试。

stride 调度算法：

时间原因暂未实现..

问答题-lab3

第六章：文件系统与I/O重定向

ch6要求我们具体完成的内容如下:

硬链接

硬链接要求两个不同的目录项指向同一个文件，在我们的文件系统中也就是两个不同名称目录项指向同一个磁盘块。

本节要求实现三个系统调用 sys_linkat、sys_unlinkat、sys_stat 。

linkat：

syscall ID: 37功能：创建一个文件的一个硬链接， linkat标准接口 。Ｃ接口： int linkat(int olddirfd, char* oldpath, int newdirfd, char* newpath, unsigned int flags)Rust 接口： fn linkat(olddirfd: i32, oldpath: *const u8, newdirfd: i32, newpath: *const u8, flags: u32) -> i32参数：olddirfd，newdirfd: 仅为了兼容性考虑，本次实验中始终为 AT_FDCWD (-100)，可以忽略。flags: 仅为了兼容性考虑，本次实验中始终为 0，可以忽略。oldpath：原有文件路径newpath: 新的链接文件路径。说明：为了方便，不考虑新文件路径已经存在的情况（属于未定义行为），除非链接同名文件。返回值：如果出现了错误则返回 -1，否则返回 0。可能的错误链接同名文件。

unlinkat:

syscall ID: 35功能：取消一个文件路径到文件的链接, unlinkat标准接口 。Ｃ接口： int unlinkat(int dirfd, char* path, unsigned int flags)Rust 接口： fn unlinkat(dirfd: i32, path: *const u8, flags: u32) -> i32参数：dirfd: 仅为了兼容性考虑，本次实验中始终为 AT_FDCWD (-100)，可以忽略。flags: 仅为了兼容性考虑，本次实验中始终为 0，可以忽略。path：文件路径。说明：注意考虑使用 unlink 彻底删除文件的情况，此时需要回收inode以及它对应的数据块。返回值：如果出现了错误则返回 -1，否则返回 0。可能的错误文件不存在。

fstat:

syscall ID: 80功能：获取文件状态。Ｃ接口： int fstat(int fd, struct Stat* st)Rust 接口： fn fstat(fd: i32, st: *mut Stat) -> i32参数：fd: 文件描述符st: 文件状态结构体#[repr(C)]
#[derive(Debug)]
pub struct Stat {
/// 文件所在磁盘驱动器号，该实验中写死为 0 即可 pub dev: u64,
/// inode 文件所在 inode 编号 pub ino: u64,
/// 文件类型 pub mode: StatMode,
/// 硬链接数量，初始为1 pub nlink: u32,
/// 无需考虑，为了兼容性设计 pad: [u64; 7],
}

/// StatMode 定义：bitflags! {
pub struct StatMode: u32 {
const NULL = 0;
/// directory const DIR = 0o040000;
/// ordinary regular file const FILE = 0o100000;
}
}

我们先来实现fstat:

fstat需要我们先得到三个位置信息分别是

/// inode 文件所在 inode 编号 pub ino: u64,
/// 文件类型 pub mode: StatMode,
/// 硬链接数量，初始为1 pub nlink: u32,

inode 文件所在 inode 编号：

在rcore系统的内核中，似乎没有提供能直接从OSinode得到inode id的接口，所以有两种办法，一种是去修改Easy-fs，另有一种方法是在OSinode被创建的时候给他们分配id。在这里我使用的是后者。

在OSinode结构体中添加如下结构体

pub struct Ino{ link:u32, ino:u64, }

然后再每次打开文件之后对OSinode 使用一个bitmap来分配 id，在文件关闭时用bitmap来回收id；

bitmap在 easyfs中的bitmap.rs有相应实现。我们只需要利用bitmap的alloc和dealloc来实现id的分配和回收。

其中文件类型，可以通过使用 read_disk_inode 获取 inode 对应的 DiskInode 的只读引用，并从中读取相关信息即可。

最后是硬链接数量，该信息显然需要结合link 与 unlink来维护，我们在link时通过刚刚所分配的id，来进行映射即可

ITOS.get_mut(&op).unwrap().link+=1;

ps:ITOS是一个BTreeMap 可以通过文件名来获取或者修改对应的 Ino结构体。

我们再来实现link与unlink:

首先我们刚刚已经为文件进行了id的分配，我们继续利用先前所分配的id，进行管理。

首先我储存了新的名字和磁盘块原名之间的映射，在文件open与close前，将输入的名字（如果已经被映射）替换为原名来实现两个不同名称目录项指向同一个磁盘块。

如下：

1
2
3
4
5
6
7
8
9
10
11

if unsafe {
UMAP2.contains_key(&path1)
}{
{
        path = unsafe { UMAP2 [&path1].clone()};

    }
}
else {
    path =path1;
}

unlink的逻辑也与link类似，通过用BTreeMap的remove方法将映射删除。
但是要特别注意的是，当link为0时，我们需要回收inode id

1
2
3
4
5
6
7
8
9
10
11

let  c= unsafe { ITOS .get_mut(&name).unwrap()};
if c.link>0{ 
        c.link-=1;
       }
       else{
         let fd=unsafe { UMAP1.get(&name).unwrap() };
         let bind=current_task().unwrap();
         let inner=bind.inner_exclusive_access().fd_table[*fd].clone().unwrap();
         inner.clear();

       }

向前兼容：

唯一要注意的点就是在spawn 中，我们需要用ch6新建立的文件系统来获取应用数据，而不是像ch4一样用translated_str方法直接获取应用数据。

let Some(app_inode) = open_file(path.as_str(), OpenFlags::RDONLY)

向前兼容的其他方面都与先前类似。

问答题-lab4

第八章：并发

ch8要求我们具体完成的内容如下:

死锁检测

目前的 mutex 和 semaphore 相关的系统调用不会分析资源的依赖情况，用户程序可能出现死锁。 我们希望在系统中加入死锁检测机制，当发现可能发生死锁时拒绝对应的资源获取请求。 一种检测死锁的算法如下：

定义如下三个数据结构：

• 可利用资源向量 Available ：含有 m 个元素的一维数组，每个元素代表可利用的某一类资源的数目， 其初值是该类资源的全部可用数目，其值随该类资源的分配和回收而动态地改变。 Available[j] = k，表示第 j 类资源的可用数量为 k。
• 分配矩阵 Allocation：n * m 矩阵，表示每类资源已分配给每个线程的资源数。 Allocation[i,j] = g，则表示线程 i 当前己分得第 j 类资源的数量为 g。
• 需求矩阵 Need：n * m 的矩阵，表示每个线程还需要的各类资源数量。 Need[i,j] = d，则表示线程 i 还需要第 j 类资源的数量为 d 。

算法运行过程如下：

1. 设置两个向量: 工作向量 Work，表示操作系统可提供给线程继续运行所需的各类资源数目，它含有 m 个元素。初始时，Work = Available ；结束向量 Finish，表示系统是否有足够的资源分配给线程， 使之运行完成。初始时 Finish[0..n-1] = false，表示所有线程都没结束；当有足够资源分配给线程时， 设置 Finish[i] = true。
2. 从线程集合中找到一个能满足下述条件的线程

1Finish[i] == false; 2Need[i,j] ≤ Work[j];

若找到，执行步骤 3，否则执行步骤 4。

1. 当线程 thr[i] 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:

1Work[j] = Work[j] + Allocation[i, j]; 2Finish[i] = **true**;

跳转回步骤2

1. 如果 Finish[0..n-1] 都为 true，则表示系统处于安全状态；否则表示系统处于不安全状态，即出现死锁。

出于兼容性和灵活性考虑，我们允许进程按需开启或关闭死锁检测功能。为此我们将实现一个新的系统调用： sys_enable_deadlock_detect 。

enable_deadlock_detect：

• syscall ID: 469
• 功能：为当前进程启用或禁用死锁检测功能。
• C 接口： int enable_deadlock_detect(int is_enable)
• Rust 接口： fn enable_deadlock_detect(is_enable: i32) -> i32
• 参数：
  • is_enable: 为 1 表示启用死锁检测， 0 表示禁用死锁检测。
• 说明：
  • 开启死锁检测功能后， mutex_lock 和 semaphore_down 如果检测到死锁， 应拒绝相应操作并返回 -0xDEAD (十六进制值)。
  • 简便起见可对 mutex 和 semaphore 分别进行检测，无需考虑二者 (以及 waittid 等) 混合使用导致的死锁。
• 返回值：如果出现了错误则返回 -1，否则返回 0。
• 可能的错误
  • 参数不合法
  • 死锁检测开启失败

思路：

要为锁机制实现死锁检测，关键在于如何维护相关状态，并在检测前构造出合适的资源分配结构。我们可以从mutex开始：每个线程最多只需要一把锁，因为线程只有在获取所需的锁资源后才能继续执行，若没有锁资源可用，线程将会被阻塞。因此，为每个线程分配一个 mutex_need 变量，用来记录当前线程所需的锁的 id。

除此之外，我们还需要维护一个 mutex_allocation 向量，记录线程当前已获得但未释放的锁资源的 id。当线程调用 sys_mutex_lock(mutex_id) 请求锁时，在实际获取锁前，我们将当前线程的 mutex_need 设置为 mutex_id。当线程成功获得锁时，将 mutex_id 加入 mutex_allocation 向量，并将 mutex_need 置为空。这里可以使用 usize::MAX 来表示空值，也可以使用 Option 类型，后者更为优雅。

当线程调用 sys_mutex_unlock(mutex_id) 释放锁时，在实际释放锁前，首先查找并移除 mutex_allocation 向量中对应的 mutex_id 元素。

通过这种方式，我们能够在死锁检测之前，根据维护的信息构建出 Available、Allocation 和 Need 数据结构，进而使用银行家算法判断当前系统是否处于不安全状态。信号量的实现方式大致相同，但由于信号量的数量不再是二值的，因此线程的资源分配向量需要记录每个信号量的数量。我们可以用 <sem_id, cnt> 这样的二元组来表示，或者也可以使用 cnt 个 sem_id 元素。在这里，我采用前者。

此外，信号量还可以为负数，负值的绝对值表示资源的提前“透支”数量。在银行家算法中，Available[i][j] 不应为负值，若出现负数，应视为 0 处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

fn deadlock_check(available: Vec<usize>, allocation: Vec<Vec<usize>>, need: Vec<Vec<usize>>) -> bool {
        // n: thread count  m: resources count
        let (n, m) = (allocation.len(), allocation[0].len());
        let mut work = available;
        let mut finish = vec![false; n];
        loop {
            let mut idx = usize::MAX;
            for i in 0..n {
                let mut flag = true;
                if finish[i] {
                    continue;
                }
                for j in 0..m {
                    if need[i][j] > work[j] {
                        flag = false;
                        break;
                    }
                }
                if flag {
                    idx = i;
                    break;
                }
            }
            // has found a thread meet the requirement
            if idx != usize::MAX {
                for j in 0..m {
                    work[j] += allocation[idx][j];
                }
                finish[idx] = true;
            } else {
                break;
            }
        }
        finish.iter().all(|&x| x)
    }

问答题-lab5

在训练营中做了什么

rust的异步机制学习

在 Rust 的异步编程中，async 和 await 是不可忽略的核心概念。

当一个函数被标记为 async 时，它会被转换为一个返回 Future 的函数。实际上，async 函数并不是立即执行的，而是生成了一个 Future，表示一个可能尚未完成的异步计算。类似地，async 代码块的行为与 async 函数本质相同，都可以生成一个 Future。

调用 async 函数后，你需要使用 await 来获取其结果：

1

some_func().await;

await的作用

await 的核心任务是对 Future 进行轮询（poll）。当调用 await 时，程序会检查 Future 是否已完成。如果尚未完成，当前任务会被暂停，并将控制权交还给执行器（executor）。此时，CPU 资源可以被其他任务使用。随后，执行器会在适当的时机再次轮询该 Future，直到其完成。

异步任务的顺序

考虑以下代码：

1
2

func1().await;
func2().await;

如果 func1 中存在一个耗时的操作（例如 2 秒的延迟），在 await 首次轮询时，由于任务未完成，执行器会暂停该任务并继续寻找其他可以执行的任务，例如 func2。这样就实现了异步调度。

然而，如果你在异步代码中混合了同步操作，比如：

1
2

func1().await;
println!("1");

这种情况下，func1 的任务未完成时，程序会暂停整个任务链，而不会直接跳到同步代码。也就是说，println!("1") 的执行必须等到 func1 完成后才能继续。这表明异步任务的执行顺序可以调整，但同步代码的执行仍然是严格按顺序进行的。

async/await的底层原理

async 和 await 的实现涉及编译器的转换。在编译时，所有 async 函数会被转换为状态机。这种状态机的实现方式类似于无栈协程。每个 Future 都维护着一个状态，记录其当前的执行进度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

enum PollResult {
    Ready,
    Pending,
}
enum State {
    StateA,
    StateB,
    StateC,
}
struct Coroutine {
    state: State,
}
impl Coroutine {
    pub fn poll(&mut self) -> PollResult {
        match self.state {
            State::StateA => {
                /* Do something */
                self.state = State::StateB;
                return PollResult::Pending;
            }
            State::StateB => {
                /* Do something */
                self.state = State::StateC;
                return PollResult::Pending;
            }
            State::StateC => {
                /* Do something */
                return PollResult::Ready;
            }
        }
    }
}

上述代码中的 poll 函数即为协程的具体运行函数，不难看出其是一个状态机模型，上层每次调用 poll 时都可能改变其状态，从而推进其运行；总的来说，无栈协程的调度是通过函数返回然后调用另一个函数实现的，而不是像有栈协程那样直接原地更改栈指针。

此外，编译器会为异步函数生成一个表，类似于 C++ 的虚函数表（vtable）。每当一个任务暂停时，执行器会通过这个表找到下一个可以执行的任务，并对其进行轮询。这种机制确保了异步任务之间的高效调度和协作。

通过这些特性，Rust 实现了高性能的异步编程，同时避免了传统回调方式的复杂性，保证了代码的可读性和可靠性。

Phoenix 异步内核学习

在这个内核中，异步任务的执行流是通过 Rust 的 async 和 await 特性来实现的。以下是执行流的一个简要过程。

任务的核心调度

首先，从内核的主循环开始：

1
2
3

loop {
    executor::run_until_idle();
}

这里的 run_until_idle 是任务调度的入口，其核心逻辑如下：

1
2
3
4
5
6
7
8
9
10
11
12

pub fn run_until_idle() -> usize {
    let mut n = 0;
    loop {
        if let Some(task) = TASK_QUEUE.fetch() {
            task.run();
            n += 1;
        } else {
            break;
        }
    }
    n
}

它从任务队列中提取任务并运行，直到队列为空。这里的任务可以是一个用户线程，也可以是其他异步任务。

线程的定义

内核将线程与进程分开设计。线程的定义如下：

1
2
3
4
5
6
7
8

pub struct Thread {
    tid: Arc<TidHandle>,
    mailbox: Mailbox,
    pub sig_trampoline: SignalTrampoline,
    pub process: Arc<Process>,
    pub sig_queue: SpinNoIrqLock<SigQueue>,
    pub inner: UnsafeCell<ThreadInner>,
}

虽然内部资源管理方式与传统内核略有不同，但核心思想是一致的：通过 Thread 表示一个具体的任务实体。

在内核中，当加载一个 ELF 文件并创建线程时，会生成一个 Thread 实例。随后，这些线程会被包装为异步任务进行管理。

线程生命周期的实现

线程的执行过程通常包括以下几步：

1. 加载用户态寄存器（ld regs）。
2. 返回用户态执行（sret）。
3. 用户态发生中断时，陷入内核处理（trap）。
4. 继续返回用户态，循环往复，直到线程终止。

在一些传统内核中，这个循环过程可能直接用汇编实现（通常写在 .S 文件中）。但在该内核中，将线程生命周期抽象为 Rust 异步函数来实现：

1
2
3
4
5
6
7
8
9
10
11
12

pub async fn threadloop(thread: Arc<Thread>) {
    thread.set_waker(async_utils::take_waker().await);
    loop {
        trap::user_trap::trap_return();
        trap::user_trap::trap_handler().await;

        if thread.is_zombie() {
            break;
        }
    }
    handle_exit(&thread);
}

这个设计的关键在于使用 async 将线程的整个生命周期建模为一个 Future，使得线程的运行和中断处理都可以以异步方式进行，而无需依赖汇编实现。这种方式可以充分利用 Rust 异步编程的特性。

任务的 Future 封装

内核将每个线程包装为一个 Future，具体定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

pub struct UserTaskFuture<F: Future + Send + 'static> {
    task_ctx: Box<LocalContext>,
    task_future: F,
}

impl<F: Future + Send + 'static> Future for UserTaskFuture<F> {
    type Output = F::Output;

    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
        let this = unsafe { self.get_unchecked_mut() };
        let hart = processor::local_hart();
        hart.push_task(&mut this.task_ctx);

        let ret = unsafe { Pin::new_unchecked(&mut this.task_future).poll(cx) };
        hart.pop_task(&mut this.task_ctx);

        ret
    }
}

其中，task_ctx 包含 CPU 上下文和线程指针，负责管理任务的运行状态。

在初始化时，线程会被封装成 Future，并推入调度队列：

1
2
3
4
5
6

pub fn spawn_thread(thread: Arc<Thread>) {
    let future = UserTaskFuture::new(thread.clone(), threadloop(thread));
    let (runnable, task) = executor::spawn(future);
    runnable.schedule();
    task.detach();
}

此处的 threadloop 被作为一个 Future 传递给 UserTaskFuture::new，从而将线程的整个生命周期管理交由异步调度器。

异步的实现

我尝试对 rCore 内核进行异步化改造，利用 Rust 提供的 async 和 await 实现异步编程。参考了 Phoenix 的实现思路，将进出用户态等流程封装为一个协程。由于这是我第一次接触操作系统相关知识，在重构内核时，需要通过大量的调试来有机地理解和掌握内核的整体工作流程。然而，受限于期末周和其他大作业的时间压力，目前仅完成了将进出用户态等过程迁移到协程中的初步工作，仍有许多细节尚未完善。

第四阶段总结报告

一些碎语

我查看了三篇文档 ， 其中https://os.phil-opp.com/async-await/#pinning

新使用的crate：crossbeam ,conquer_once

为啥使用conquer_once的OnceCell而不是lazy_static!因为这个类型实现
了避免中断程序进行堆空间开辟（从而避免产生一个死锁）

future 中还有一个Stream的trait
tokio文档看了一下（trait回忆一下，它像个接口，implement后应用到具体的一个类型）

Tokio 文档阅读

chat

首先阅读的是一堆example，这里先看chat。
chat是一个聊天室，设立服务端然后异步读取其他客户端的消息，并且广播到是所有的客户端，
是一种中心式结构

io_uring

与linux

linux有一个自己的原生异步IO接口，叫aio,他有一些问题：

1. 因为0_DIRECT，所以很多的IO用例不适用。普通的IO会退化为同步IO。
2. 就算异步，IO也可能会阻塞，比如硬件部分，这使得软件必须获取加载这些部分的锡信息
3. API不够完美，每次提交需要64+8字节的内存，每次完成徐娅萍
   他常用的方法是：io_submit() , io_setup() , io_getevents().

io-uring 和 epoll。

epoll 只是通知机制，本质上事情还是通过用户代码直接 syscall 来做的，如 read。这样在高频
syscall 的场景下，频繁的用户态内核态切换会消耗较多资源。io-uring 可以做异步 syscall，
即便是不开 SQ_POLL 也可以大大减少 syscall 次数。

io-uring 的问题在于下面几点：

兼容问题。平台兼容就不说了，linux only（epoll 在其他平台上有类似的存在，可以基于已
经十分完善的 mio 做无缝兼容）。linux 上也会对 kernel 版本有一定要求，且不同版本的实现性
能还有一定差距。大型公司一般还会有自己修改的内核版本，所以想持续跟进 backport 也是一件头疼
事。同时对于 Mac/Windows 用户，在开发体验上也会带来一定困难。

Buffer 生命周期问题。io-uring 是全异步的，Op push 到 SQ 后就不能移动 buffer，一定
要保证其有效，直到 syscall 完成或 Cancel Op 执行完毕。无论是在 C/C++ 还是 Rust 中，都
会面临 buffer 生命周期管理问题。epoll 没有这个问题，因为 syscall 就是用户做的，陷入 sy
scall 期间本来就无法操作 buffer，所以可以保证其持续有效直到 syscall 返回。

smol

在几个库的基础上封装成最后几个接口

在 Linux 上，mio 使用 epoll 来实现高效的 I/O 多路复用。smol 使用 mio 来实现
这一点。具体来说，smol 会将 I/O 操作抽象为异步任务，然后将这些任务交给 mio 处理。
mio 通过 epoll 监听文件描述符，当某个文件描述符变得可读或可写时，它会通知 smol 来
执行相应的任务。

在 smol 的源码中，底层通过调用 mio 提供的异步 I/O API 来实现任务的异步调度。例如
，读取数据时，它会发出 epoll 查询，直到某个文件描述符准备好读取数据，才会从事件队列中获
取该事件并执行对应的异步任务。

关于我的运行时

用proactor包装io_uring实现基本的异步读写，然后再包装proactor实现io和file，然后没有什么了，
一开始低估了整个运行时的大小

然后看了很多的文档：

https://github.com/rust-lang/futures-rs/blob/master/futures-core/src/stream.rs
https://rustmagazine.github.io/rust_magazine_2021/chapter_12/monoio.html
https://github.com/bytedance/monoio/blob/master/docs/zh/io-cancel.md
https://github.com/ihciah/mini-rust-runtime/blob/master/src/tcp.rs
https://github.com/rust-lang/futures-rs/blob/master/futures-core/src/lib.rs

这里我认为monoio算是一个正确的，完善的运行时，不过这个大小太夸张了，可以下期一开始就把它粘出来，让大家
直观感受一下成果的规模。

与同学们互相讨论

在本次学习过程中，我对Rust异步编程中的一些核心挑战进行了深入思考：

1. 函数着色和异步Drop的挑战

目前Rust异步编程中最棘手的问题是函数着色和async drop机制。特别是在资源管理方面，由于future是基于poll的机制，在处理background task和事务时面临两个主要场景的挑战：

• 结构体持有background task（如连接或stream）时的资源释放
• 需要uncancelable语义的事务处理场景

2. 资源安全释放的困境

在系统信号处理方面存在显著挑战。特别是在进程接收信号时的安全资源释放问题仍然没有完善的解决方案。虽然对于使用事务的SQL系统影响相对较小，但在文件系统或WAL文件等场景中，这个问题尤为突出。

3. 互斥锁的使用策略

在异步编程中，关于互斥锁的选择需要特别注意。Tokio提供了一个重要的见解：在异步代码中使用标准库的普通Mutex通常是可行且推荐的。异步互斥锁的主要优势在于能够在.await点保持锁定状态，但这也使其比阻塞式互斥锁更昂贵。因此，对于单纯的数据访问，使用标准库的阻塞式互斥锁是更合适的选择。

4. 操作系统层面的应用

在操作系统内核中，协程的应用主要可以考虑用于替代传统的自旋锁场景，而io_uring的引入则可能带来更广泛的应用空间。

5. 异步编程模型的适用场景

从资源管理的角度来看，异步编程模型在不同场景下有其独特的优势和局限。特别是在处理IO密集型任务时，异步模型能够提供更好的性能和资源利用率。

第一周：

• 复习并重新学习WASM上的async runtime相关知识
• 计划完善OS仓库，准备移植文件系统和SMP多核启动

第二周：

• 阅读Rust语言相关RFC文档：
  • async_trait与async fn in trait
  • Object Safety
  • pin_project_lite
• 为内核态编写async runtime
• 开始实现文件系统与block device
• 计划将async runtime合并到OS仓库中

第三周：

• 因家人住院需要陪护，本周暂无工作产出

概要设计

众所周知，操作系统内核对性能和时延的需求都是非常高的。当应用程序通过传统系统调用使用操作系统能力时，CPU需要经过两次特权模式转换、用户栈的保存与恢复等操作，这会消耗数十甚至数百CPU时钟周期。因此，在操作系统内核中引入异步协程机制时，不应增加这些基础开销。

在应用程序通过操作系统与外部设备交互时，由于大多数外部设备的性能都慢于CPU执行速度，且受限于信号传输延迟，响应延迟是不可避免的。操作系统在等待外部响应时采用自旋等待是非常低效的。因此，我的设想是在IO部分引入协程机制，通过用户进程的IO操作与内核线程通信的方式，为内核代码赋予异步能力。

在二阶段学习rCoreOS时，我发现其中与virtIO block-device的交互部分非常适合进行异步协程改造。

然而，我不赞成将所有内核代码和锁都替换为异步协程版本。如前所述，操作系统内核代码对性能非常敏感。虽然无栈协程的切换开销较小，但在内核开发中这种开销仍然不容忽视。此外，由于CPU大部分时间都会交由用户线程执行以最大化资源利用率，载体线程（CPU核心）会尽可能运行用户代码，这在某种程度上违反了协程使用原则，可能导致其他任务出现饥饿现象。

总结

四阶段开始前, 我曾立下这个目标: 希望能开发出我自己的操作系统内核, 并在 Lichee Pi 4A 真机设备上成功启动.

无奈上周夫人孕期遭遇大出血, 紧急住院保胎一周. 我作为陪护家属, 暂停了一周的学习与工作照顾夫人. 故未能完成四阶段开始前立下的目标😔.

从小白到操作系统开发者：我的训练营历程与成长

参加训练营已经快一年了，回顾这段时间的学习与实践，感觉收获满满，成长也非常明显。虽然过程中经历了不少挑战，但我从中学到了很多，也更加明白了自己未来的目标和方向。

从初识RTOS和操作系统

从今年刚刚开始接触开源操作系统训练营，感觉开辟了一片新的天地在训练营的第一阶段，我还是一个对RTOS（实时操作系统）了解甚少的“小白”。当时，我的理解仅限于知道 FreeRTOS 是什么，而对于操作系统的具体结构和工作原理几乎没有任何概念。然而，通过这段时间的学习，我开始接触并逐步理解操作系统的基本组成部分，像是内核、调度、进程管理等。这个阶段的学习让我明白了操作系统不仅仅是运行应用程序的基础，更是硬件和软件之间的重要桥梁。

网络问题与任务挑战

不过，学习的过程并不是一帆风顺的。由于网络不稳定，很多简单的任务总是上传不了，这让我有时感到非常沮丧。更有一次，我因为任务时间限制和一些技术难题，没能在结课期间按时完成所有的任务。这些问题让我认识到，技术的实现不仅仅依赖于个人的能力，还需要更好的时间管理和稳定的技术环境支持。

深入探索异步编程与Python适配

进入训练营的第二阶段后，任务的难度逐步增加。我选择了一个相对较简单的方向，与其他小伙伴们一起研究 异步编程。虽然这与我之前的经验较为接近，但在实际实现过程中，我还是遇到了不少挑战，尤其是在理解异步编程模型时。

然而，通过逐步的实现，我不仅加深了对异步编程的理解，还接触了Python适配的相关知识。实际上，这个阶段让我学到了很多之前没有涉及的技术，这些新知识极大地丰富了我的技术栈，也让我对未来的技术方向更加清晰。

Python与OpenCV的结合

尽管我没有完全按预期完成所有任务，但这个阶段让我深入思考了自己的学习方法。我曾经盲目追求高难度的任务，而忽略了任务的实际意义和自己的能力匹配。因此，在这个阶段，我主动选择了一个相对简单的任务——OpenCV 的相关实践。尽管我最终未能在 Starry 上完成OpenCV的测例，但这个过程让我更加明白了如何进行项目规划和任务分配。

在这阶段，我还负责了Python与OpenCV的结合，进行了一些与图像处理相关的实验和项目。通过这些实践，我深入了解了Python的图像处理能力，尤其是OpenCV库在计算机视觉中的应用。例如，如何使用OpenCV进行图像读取、处理和展示，这些操作帮助我了解了计算机如何通过视觉来感知和分析信息。

实现Python3.11的syscall系统调用

作为实习任务的一部分，我参与了分析和实现支持 Python3.11 程序的 syscall 系统调用，尤其是在 ArceOS/Starry 系统中，逐步完善Python程序所依赖的系统调用。具体来说，这个过程涉及了用户态程序的交叉编译、依赖库的交叉编译、以及系统模拟器 Qemu 中的实验。

1. 交叉编译Python程序：首先，我需要交叉编译 Python3.11，以支持 aarch64 架构。这包括了编译所需的依赖库（如 libffi、zlib、libuuid 和 xz 等），并且每个依赖库都必须交叉编译，以保证在目标架构上能够正常运行。

2. Qemu模拟环境：为了测试在交叉编译后的Python程序，我在 Qemu 模拟环境中运行了一个 aarch64 架构的 Alpine Linux，并在其中加载了交叉编译生成的Python库。通过这种方式，我能够测试并调试系统调用，确保它们能够在模拟器中正常执行。

3. 系统调用分析：我使用 strace 工具来统计Python程序所使用的所有系统调用，并分析它们在不同架构下的表现。通过这个过程，我深入了解了 syscall 的工作机制，并能够在实际操作系统中正确实现这些调用。

通过这个任务，我不仅加深了对操作系统内核和系统调用机制的理解，还在实践中学会了如何处理复杂的交叉编译任务。

未来的目标–操作系统与编译器

回顾这一年的学习，我不仅了解了操作系统的基本原理，还在逐步实现的过程中积累了不少经验。尤其是从一个仅仅知道FreeRTOS的小白，到如今能够理解操作系统结构的程度，我感到自己有了明显的进步。

最令我兴奋的是，未来我希望能够在自己写的操作系统上运行自己开发的编译器。这是我一直以来的梦想，虽然这需要我不断努力和学习，但我相信，通过这段时间的积累，我已经打下了坚实的基础。

总结

参加训练营的这一年里，我收获了很多，不仅有热心的助教和同学的帮助，还有机会接触到多种新技术和工具。虽然遇到了一些困难，但这些都成为了我成长的动力。我相信，未来我会继续沿着这个方向前行，实现自己在操作系统和编译器领域的梦想。

stage4总结

stage 4 算是很扎实的一个阶段。这个阶段从头开始学习了我原来不怎么熟悉的异步运行时。整体上来说算是比较系统的学习了如何构建一个异步运行时，同时也阅读了不少tokio这种生产环境级别的异步运行时代码，受益良多。
本阶段还学习了一些关于 uring io 的知识，同时也顺便比较系统的梳理了 linux io 这块的知识点。通过每周一次的交流活动中能比较有效的调整自己的学习方向，同时也能补充很多有用的信息。很多同学水平很高，在交流过程中深感差距，还需要不断学习。

stage4 工作进度

本周工作（第一周）：

阅读以下两个链接中文档，比较系统的了解了 rust 的异步原理

• Writing an OS in Rust async/await
• https://rust-lang.github.io/async-book/

####下周安排（第二周）：

• 阅读 tokio 源码，学习生产环境中的异步运行时实现

本周工作（第二周）：

由于本项目最终要实现一个基于 uring io 的异步运行时，于是决定从 io 的角度切入 tokio 的源码阅读。在阅读过程中发现 tokio 的文件 io 部分都是转发给某个独立线程，是基于阻塞式的操作。为了对比文件 io ，还阅读了部分 tcp 相关的源码，证实了的确网络 io 是使用了基于 epoll 的 mio 来做管理。而且本周对 uring io 有一个粗略地了解，目前看来 uring io 在文件 io 方面可能优势会更明显。 网络 io 这块相较于 epoll 优势没那么大，那么接下来第三周可能要优先实现基于 uring io 的文件 io 异步运行时的相关工作。

此外本周还阅读了以下资料

• 群友关于 smol 的博客
  https://systemxlabs.github.io/blog/smol-async-runtime/
• uring_io 在 smol 中实现相关的 issue
  https://github.com/smol-rs/async-fs/issues/24
  https://github.com/smol-rs/async-io/issues/39
• tokio uring io
  https://github.com/tokio-rs/tokio-uring
  这么看下来 smol 更为精简，而且文件 io 也是基于阻塞式操作。而且社区中也有想要让 smol 支持 uring io 的讨论，也许尝试移植一下 smol 会更有意思？

下周安排（第三周）：

编写一个简易的基于 uring io 的文件 io 的异步运行时。

本周工作（第三周）：

本周首先调研了一下在 smol 中实现基于 uring io 的可能性。首先 smol 社区中已经有一个 PR
async-io PR:Integrate io_uring in the Reactor
● 简要介绍了实现思路，
● 作者说要等等 polling Expose raw handles for the Poller 这个 issuing合并.
大概粗略浏览了一下，但是由于对 uring io 不太熟悉用法，还没有看懂，暂时搁置。

然后继续阅读了 uring io 的相关资料，包括

• https://kernel.dk/io_uring.pdf通过这个文档比较系统的了解了io uring 的背景和、原理和用法。
• https://github.com/tokio-rs/tokio-uring tokio 官方实现的基于 uring io 的异步运行时，在实现我自己的异步运行时的时候接口和一些比较棘手的问题有大量参考里面的实现方式。
• https://github.com/tokio-rs/io-uringtokio 官方封装的 io uring 库。我的异步运行时也基于这个库。
• https://rustmagazine.github.io/rust_magazine_2021/chapter_12/monoio.html参考这个文档，对基于 uring io 的异步运行时实现上可能遇到的问题和解决方案有了一个大概了解。

最后是实现我自己的uring io异步运行时
我的async-fs-uring，这里实现了一个建议的基于 reactor 模式异步运行时，并实现了基于uring io的文件读。主要思想就是把 io 委托给 reactor 去提交，然后 reactor 不断轮询，如果有 io 完成了，就返回给对应的异步任务。实现过程中比较困难的点就是buf 管理，需要保证 buf 在异步读过程中一直有效。我这里做法是直接把 buf 的所有权移交给 UringReadFuture.这只是一个权宜之计，因为我这里实现的比较简单，在异步读进行过程中 UringReadFuture不会被 drop 掉。实际上后来也阅读了 tokio-uring 的相关设计文档，也了解到了一些更合理的设计方案，但是还没有时间来实现。

未来计划：通过实现一个建议的基于 uring io 的异步运行时让我对 uring io 有了基本的了解。后续可能会进一步了解生产环境级的基于 uring io 的异步运行时的实现以及与传统阻塞式和epoll结合的异步运行时的实现差异

前言

在阶段4我进入了项目四：基于协程异步机制的操作系统，由于之前缺乏对相关知识的了解，前期花了大量时间来阅读源码和理解，最后才实现了在OS中boot了一个简单的的异步executor。

async keyword

在 Rust 中,使用 async 关键字修饰的函数会返回一个实现了 Future trait 的匿名类型

1
2
3
4

pub trait Future {
    type Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output>;
}

例如

1
2
3

async fn my_async_function() -> u32 {
    42
}

编译器会将其转换为类似以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

fn my_async_function() -> impl Future<Output = u32> {
    struct MyAsyncFunction {
        // 异步函数的状态
    }

    impl Future for MyAsyncFunction {
        type Output = u32;

        fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
            // 异步函数的执行逻辑
            Poll::Ready(42)
        }
    }

    MyAsyncFunction {
        // 初始化异步函数的状态
    }
}

这种设计允许编译器生成最优化的异步执行代码,同时提供了灵活性和类型安全性。

当然，对于rust的异步编程还有许多深入的概念，例如关于自引用的 Pin<> , 关于优化轮询的 Waker 等。

why async-OS

所以为什么要实现一个基于协程异步机制的操作系统呢？答案当然是为了并发的性能。内核可以通过轻量的内核线程和优化的异步调度执行来提升对系统调用的批处理速度。

参考async-module关于系统调用的优化，存在两种方向：

1. 减少由于系统调用导致的特权级以及上下文切换开销
2. 异步批处理

在高并发场景下，使用类似dpdk/spdk等通过用户态轮询完全绕过内核是可行的，但是如果仍然使用系统调用，那么当应用通过系统调用同步地进入内核态时，内核就可以对这些系统调用进行异步批处理，从而提升性能。
并且异步调度的 poll / wake 机制更适合设备驱动的工作状态。

design

考虑一种简单的情形，在OS初始化阶段，把栈初始化之后，直接开始运行全局的executor，负责对内核中的异步协程进行调度。这样，我们所有的系统调用都可以写成async的形式。

那么，当用户程序需要调用系统调用时，会先同步的进入内核态并设置scause寄存器的值来指定系统调用号，然后调用syscall之后await，在系统调用执行完之后再切换回用户态。所以这里的syscall api实现了一个异步和同步切换的过程。
当然另一种思路是，通过内核向用户态发送通知或者共享内存等方式，实现完全的异步系统调用，这里不再讨论。

implement

所以，我们在内核态需要建立自己的异步运行时，在抽象上的第一个问题是，Rust 欠缺对 async-trait 的支持。

例如

1
2
3

pub trait Mutex {
    async fn wait(&mut self) -> FutexWait;
}

Rust 编译器默认不支持 async trait function。编译器提示说使用 async-trait 这个 crate。可惜的是，这个 crate 不是零开销的, 会将返回值改写成 Box 的形式。

还是继续考虑对futex的实现。我们既然想让对互斥锁的wait支持异步，那么就先实现一个 Future。

1
2
3
4
5
6
7
8
9
10
11
12
13

impl Future for FutexWait {
    type Output = ();

    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
        let this = &mut *self;
        loop {
            match this.queue.poll(&mut this.id, cx.waker()) {
                Ok(poll) => break poll,
                Err(queue) => this.queue = queue,
            }
        }
    }
}

如果可以从互斥锁队列queue中拿到结果，那么就返回poll， 否则就对等待队列进行更新并继续循环。

接下来考虑进程的执行单元task，Task 结构体包含了任务的各种属性,如可执行文件、父任务、子任务、任务 ID、时间信息、信号相关的字段等。如果我们想要把task交给executor执行，就需要为task的返回值实现 Future 。

也就是说，我们把task的返回值当成 Output 以实现一个 TaskFut:Future 的结构体 ， 接着将这个 task 封装成一个异步的 loop 传入 executor 中。 在 loop 中 ，我们通过 trap 切换回用户空间 ， 并且捕获用户空间的中断和异常 ， 在切换回内核空间之后继续处理。

try

接着，在老师的指导下，我进行了将二阶段 rCore-tutorial 操作系统实现异步的尝试。

在 rust 的入口处，我们使用mm::init()来使用HEAP_ALLOCATOR来初始化堆内存，接下来我们就可以直接在堆内存上建立executor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#[no_mangle]
/// the rust entry-point of os
pub fn rust_main() -> ! {
    clear_bss();
    println!("[kernel] Hello, world!");
    logging::init();
    mm::init();
    mm::remap_test();
    
    let mut rt = RUNTIME.execlusive_access();
    rt.spawn(task1)
    rt.run()
}

async fn task1() {
    println!("[kernel] task1: hello async world!");
}

这样就是最简单的内核态的async执行测试。

第一阶段总结

第一阶段主要考察 Rust 基础编程和数据结构与算法，由于我有一定 Rust 基础，所以前 100 道题比较轻松，但从未使用 Rust 刷过算法题，因此后 10 道题让我学习了如何使用 Rust 编写常见数据结构如链表、栈、堆、图等，以及常见的排序、搜索算法等，有所收获！

第二阶段总结

第二阶段我的学习方法是先看完 v3 book 对应章节，然后再做实验题。v3 book 写得循序渐进，质量上乘，读懂后做实验题都比较轻松。第二阶段的精华都在 v3 book 中，十分建议精读一遍，我自己精读一遍后发现了若干内容和文字错误，还提交了 19 个 pr 修复。这期间我还写了篇博客分析有栈协程示例代码。

五个实验题中最后的死锁检测算法花费的时间要久一点，因为前面章节没有铺垫，直接就是抛出一个算法让实现，且算法只有过程描述，没有原理分析。这个算法似乎很少在生产上见到被实际使用（可能是我孤陋寡闻），我建议换成其他更有意义的实验，比如实现某一种同步互斥原语。

第三阶段总结

第三阶段主要是理解 ArceOS 组件化概念，如何划分组件以及如何将这些组件组装成不同的系统，如 Unikernel/宏内核/hypervisor 等。

在这个阶段，我完成了四个练习（print_with_color/support_hashmap/alt_alloc/simple_hv）和一个挑战任务：针对特定应用实现一个专门优化过的内存分配器。挑战任务并没有花太多时间，只是在 slab 分配器上做了些修改，所以得分不高，刚过及格线，排名第 14。

在这个阶段，我花费了许多时间来学习 RISC-V 的虚拟化扩展，本来是准备在第四阶段选择虚拟化项目的，但最后发现项目并没有采用 RISC-V 指令集（不想再花时间学习另一个指令集的特权架构，最终选择了基于协程异步机制的操作系统/驱动项目）。我研究了 arceos-hypervisor org 下的一些虚拟化项目和 KuangjuX/hypocaust-2 项目，arceos-hypervisor 项目因为需要做到组件复用，包括统一不同指令集架构，所以有很多抽象，学习成本有些高，而 KuangjuX/hypocaust-2 项目目前跑不起来，项目并没有指定 rust-toolchain，而且代码质量感觉不够高。最终我还是决定自己从零开始写一个纯 RISC-V 的一型 hypervisor，因为毕竟花了几个月时间参加训练营，还是想在最后自己能独立编写一个完整的实际项目。项目地址是 https://github.com/systemxlabs/riscv-hypervisor , 目前刚能将 rCore-Tutorial-v3 的第 5 章的内核作为 guest 跑起来，最终目标是能跑起 Linux。RISC-V 虚拟化扩展因为稳定不久，资料很少，所以写的过程中遇到许多困难，而且不好 debug，希望能坚持下去不弃坑~

第四阶段总结

第一周，阅读 200 行 rust 代码实现绿色线程、 200 行 rust 代码实现 futures 以及 blog_os 的 async/await 文章，输出了一篇博客，同时提了 pr 修复 rCore-Tutorial-v3 中 stackful_coroutine 示例代码，自己还将 stackful_coroutine 示例移植到 Linux for RISC-V 上（项目地址：https://github.com/systemxlabs/green-threads-in-200-lines-of-rust ），对原示例代码做了很多重构以便具有更好的可读性。调试自己的riscv hypervisor项目（第三周使用），目前可以运行 rCore-Tutorial-v3 第六章带文件系统的内核。

第二周，主要阅读 smol 生态 crates 源码，着重阅读了 polling / async-io / async-task / async-executor 库源码，理解最重要的 IO 多路复用 / reactor / driver / task / executor 等概念，输出了一篇博客。

第三周，编写异步 os（项目地址：https://github.com/systemxlabs/async-os ），本来是想把之前写的 riscv-hypervisor 改成异步，但感觉没有意义，因为 os 上面可能有成千上万的线程，所以将 os 改成异步减少上下文切换是有意义的，但 hypervisor 跟 os 不同，hypervisor 上面没有那么多的 guests，且 hypervisor 为了高性能，通常都尽可能去避免 vm exit，所以我放弃将之前写的 riscv-hypervisor 改成异步，改为实现一个异步 os，参考 phoenix 和 rCore-Tutorial-v3，特点是全隔离内核、内核栈复用、trap return回用户态时无需保存内核执行流。目前已实现多核启动、device tree解析、物理页帧和堆分配器、页表和地址空间、内核和用户态trap handling、异步runtime。

总说

在训练营的第四阶段，几乎一直在读东西，一边看一边学asynchronous和Rust，之前几乎没有了解和使用过异步方面的东西。
学习效果不是很好，结营后还得多读多写这一块的代码，继续学习。

细说

第一周：

• 了解了一些RUST的异步和协程机制
• 读了绿色线程的代码
• 读了philopp那篇用异步实现协作式任务调度

第二周:

• 跟着这篇博客了解了实现异步运行时的思路
• 看PPT给上的tokio相关

第三周:

• 读了io_uring的手册，顺带了解了一下使用环形队列和内存映射，无锁环提高性能的原理
• 读了一下smol源码，主要是futures-lite和async-executor部分
• 尝试使用iou封装的接口实现简单的异步文件读写，但是实现的waker有问题，没有成功

总结

最后这一阶段，鄙人主要围绕rust的异步编程async/await及经典运行时库tokio展开阅读研究。但并没有深入理解其中原理及实现，更多的是比较浅显地了解，像tokio的有些模块并没有看，还又比较多的疑问在里面。如果后续有时间的话，希望能继续阅读并深入。代码实现上，仅在rcore上实现了一个极为简单的用户态运行时，跑了几个异步任务，有点协程的意思了（。但是并没有实现waker机制，后续考虑进一步实现完善

协程

有栈协程

函数运行在调用栈上，把函数作为一个协程，那么协程的上下文就是这个函数及其嵌套函数的栈帧存储的值，以及此时寄存器存储的值。如果我们调度协程，也就是保存当前正在运行的协程上下文，然后恢复下个将要运行的协程的上下文。这样我们就轻松的完成了协程调度。并且因为保存的上下文和普通函数执行的上下文是一样的，所以有栈协程可以在任意嵌套函数中挂起（无栈协程不行）。

有栈协程的优点在易用性上，通常只需要调用对应的方法，就可以切换上下文挂起协程。在有栈协程调度时，需要频繁的切换上下文，开销较大。单从实现上看，有栈协程更接近于内核级线程，都需要为每个线程保存单独的上下文（寄存器、栈等），区别在于有栈协程的调度由应用程序自行实现，对内核是透明的，而内核级线程的调度由系统内核完成，是抢占式的。

无栈协程

相比于有栈协程直接切换栈帧的思路，无栈协程在不改变函数调用栈的情况下，采用类似生成器的思路实现了上下文切换。通过编译器将生成器改写为对应的迭代器类型（内部实现是一个状态机）。

而无栈协程需要在编译器将代码编译为对应的状态机代码，挂起的位置在编译器确定。无栈协程的优点在性能上，不需要保存单独的上下文，内存占用低，切换成本低，性能高。缺点是需要编译器提供语义支持，无栈协程的实现是通过编译器对语法糖做支持，rust的aysnc\await就是语法糖，编译器将带有这些关键字的方法编译为生成器，以及对应的类型作为状态机。

只有状态机的支持才能进行协程调度，例如Rust中的tokio，基于Future的用户态线程，根据poll方法获取Future状态，它不可以在任意嵌套函数中挂起（同步代码未实现状态机）。

tokio

我主要从tokio::main宏出发，一步步分析其中调用关系。主要围绕runtime库的build及Runtime结构体的方法及函数

使用#[tokio::main]宏生成的代码

1
2
3
4
5
6
7
8
9

fn main() {
    tokio::runtime::Builder::new_multi_thread()
        .enable_all()
        .build()
        .unwrap()
        .block_on(async {
            // ...
        })
}

结构体Builder用作运行时runtime配置，通过new_current_thread()使用单线程运行时，new_multi_thread()使用多线程运行时，并会返回Builder实例

new_multi_thread

1
2
3
4
5
6
7
8
9

/// Returns a new builder with the multi thread scheduler selected.
   ///
   /// Configuration methods can be chained on the return value.
#[cfg(feature = "rt-multi-thread")]
   #[cfg_attr(docsrs, doc(cfg(feature = "rt-multi-thread")))]
   pub fn new_multi_thread() -> Builder {
       // The number `61` is fairly arbitrary. I believe this value was copied from golang.
       Builder::new(Kind::MultiThread, 61)
   }

调用new方法返回一个Kind为MultiThread的Builder，对于定时器和I/O事件释放CPU之前需要61ticks

enable_all

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/// Enables both I/O and time drivers.
   ///
   /// Doing this is a shorthand for calling `enable_io` and `enable_time`
   /// individually. If additional components are added to Tokio in the future,
   /// `enable_all` will include these future components.
   pub fn enable_all(&mut self) -> &mut Self {
           #[cfg(any(
               feature = "net",
               all(unix, feature = "process"),
               all(unix, feature = "signal")
           ))]
           self.enable_io();
           #[cfg(feature = "time")]
           self.enable_time();

           self
       }

操作成员变量，使能运行时I/O和定时器

build

1
2
3
4
5
6
7
8
9
10
11
12

/// Creates the configured `Runtime`.
   ///
   /// The returned `Runtime` instance is ready to spawn tasks.
   pub fn build(&mut self) -> io::Result<Runtime> {
       match &self.kind {
           Kind::CurrentThread => self.build_current_thread_runtime(),
           #[cfg(feature = "rt-multi-thread")]
           Kind::MultiThread => self.build_threaded_runtime(),
           #[cfg(all(tokio_unstable, feature = "rt-multi-thread"))]
           Kind::MultiThreadAlt => self.build_alt_threaded_runtime(),
       }
   }

运行时创建的核心步骤，创建已经做配置的runtime，并返回Runtime实例准备创建异步任务

1
2
3
4
5
6
7
8
9
10

pub struct Runtime {
    /// Task scheduler
    scheduler: Scheduler,

    /// Handle to runtime, also contains driver handles
    handle: Handle,

    /// Blocking pool handle, used to signal shutdown
    blocking_pool: BlockingPool,
}

scheduler：异步任务调度器

handle：运行时句柄

blocking_pool：阻塞池句柄，用于发出关闭信号

build -> build_threaded_runtime

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

fn build_threaded_runtime(&mut self) -> io::Result<Runtime> {
            use crate::loom::sys::num_cpus;
            use crate::runtime::{Config, runtime::Scheduler};
            use crate::runtime::scheduler::{self, MultiThread};

            let core_threads = self.worker_threads.unwrap_or_else(num_cpus);

            let (driver, driver_handle) = driver::Driver::new(self.get_cfg(core_threads))?;

            // Create the blocking pool
            let blocking_pool =
                blocking::create_blocking_pool(self, self.max_blocking_threads + core_threads);
            let blocking_spawner = blocking_pool.spawner().clone();

            // Generate a rng seed for this runtime.
            let seed_generator_1 = self.seed_generator.next_generator();
            let seed_generator_2 = self.seed_generator.next_generator();

            let (scheduler, handle, launch) = MultiThread::new(
                core_threads,
                driver,
                driver_handle,
                blocking_spawner,
                seed_generator_2,
                Config {
                    before_park: self.before_park.clone(),
                    after_unpark: self.after_unpark.clone(),
                    before_spawn: self.before_spawn.clone(),
                    after_termination: self.after_termination.clone(),
                    global_queue_interval: self.global_queue_interval,
                    event_interval: self.event_interval,
                    local_queue_capacity: self.local_queue_capacity,
                    #[cfg(tokio_unstable)]
                    unhandled_panic: self.unhandled_panic.clone(),
                    disable_lifo_slot: self.disable_lifo_slot,
                    seed_generator: seed_generator_1,
                    metrics_poll_count_histogram: self.metrics_poll_count_histogram_builder(),
                },
            );

            let handle = Handle { inner: scheduler::Handle::MultiThread(handle) };

            // Spawn the thread pool workers
            let _enter = handle.enter();
            launch.launch();

            Ok(Runtime::from_parts(Scheduler::MultiThread(scheduler), handle, blocking_pool))
        }

1. 引入

num_cpus：用于获取系统的 CPU 核心数量。

Config：运行时的配置项。

MultiThread：多线程调度器，负责在多个线程间调度异步任务。

2. 确定核心线程数

1

let core_threads = self.worker_threads.unwrap_or_else(num_cpus);

• self.worker_threads：用户在Builder配置的核心线程数。如果未指定，使用系统的 CPU 核心数作为默认值（num_cpus()）。
• core_threads 是最终确定的核心线程数，表示运行时的调度线程数量。

3. 初始化驱动

1

let (driver, driver_handle) = driver::Driver::new(self.get_cfg(core_threads))?;

• driver：负责管理底层 IO 和定时器的核心组件。
• driver_handle：运行时与驱动交互的句柄，用于调度异步任务和管理定时器。
• get_cfg(core_threads)：返回结构体driver::Cfg，包含驱动的配置项，包含workers等配置。

4. 创建阻塞任务池

1
2

let blocking_pool = blocking::create_blocking_pool(self, self.max_blocking_threads + core_threads);
let blocking_spawner = blocking_pool.spawner().clone();

• 阻塞任务池：用于执行需要阻塞运行的任务（例如文件 IO 或计算密集型任务），避免阻塞异步任务调度线程。

  • 线程数 = 用户指定的 max_blocking_threads + 核心线程数。

• blocking_spawner：用于将任务提交到阻塞任务池的对象。

5. 生成随机数种子

1
2

let seed_generator_1 = self.seed_generator.next_generator();
let seed_generator_2 = self.seed_generator.next_generator();

• Tokio 的调度器可能需要随机化任务的分配，例如在多线程调度器中均衡负载。
• seed_generator_1 和 seed_generator_2 是生成的两个独立随机数种子，分别用于不同的组件。

6. 初始化调度器

1
2
3
4
5
6
7
8

let (scheduler, handle, launch) = MultiThread::new(
    core_threads,
    driver,
    driver_handle,
    blocking_spawner,
    seed_generator_2,
    Config { ... },
);

• 调用 MultiThread::new 创建一个多线程调度器，返回：

  • scheduler：核心调度器，管理线程间任务的分配和调度。
  • handle：调度器的句柄，用于外部与调度器交互。
  • launch：启动调度器工作线程的接口。

• 传递的参数：

  • core_threads：核心线程数。

  • driver 和 driver_handle：用于与 IO 和定时器交互的驱动组件。

  • blocking_spawner：用于执行阻塞任务的接口。

  • seed_generator_2：随机数种子，用于内部调度逻辑。

  • Config：调度器的配置，包括以下内容：

    • before_park 和 after_unpark：线程挂起与唤醒时的回调函数。
    • before_spawn 和 after_termination：任务生成和结束时的回调函数。

  • global_queue_interval 和 event_interval：全局队列检查和事件处理的时间间隔。

    • local_queue_capacity：本地任务队列容量。

  • 其他运行时的定制项。

7. 创建运行时句柄

1

let handle = Handle { inner: scheduler::Handle::MultiThread(handle) };

• Handle 是对调度器的抽象封装，用于外部访问运行时和调度器的功能。

8. 启动工作线程

1
2

let _enter = handle.enter();
launch.launch();

• handle.enter()：将当前线程设置为调度器的上下文，用于初始化调度环境。
• launch.launch()：启动调度器的所有工作线程，使其开始运行。

9. 返回运行时

1

Ok(Runtime::from_parts(Scheduler::MultiThread(scheduler), handle, blocking_pool))

• 创建并返回完整的Runtime实例，包括：
  • Scheduler::MultiThread(scheduler)：多线程调度器。
  • handle：运行时句柄。
  • blocking_pool：阻塞任务池。

driver::Driver::new方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

pub(crate) fn new(cfg: Cfg) -> io::Result<(Self, Handle)> {
        let (io_stack, io_handle, signal_handle) = create_io_stack(cfg.enable_io, cfg.nevents)?;

        let clock = create_clock(cfg.enable_pause_time, cfg.start_paused);

        let (time_driver, time_handle) =
            create_time_driver(cfg.enable_time, io_stack, &clock, cfg.workers);

        Ok((
            Self { inner: time_driver },
            Handle {
                io: io_handle,
                signal: signal_handle,
                time: time_handle,
                clock,
            },
        ))
    }

1. 创建 IO 栈

1

let (io_stack, io_handle, signal_handle) = create_io_stack(cfg.enable_io, cfg.nevents)?;

• 调用 create_io_stack 创建 IO 栈（底层 IO 相关的资源），返回：

  • io_stack：IO 栈的核心组件，用于管理底层 IO 操作。
  • io_handle：用于和 IO 栈交互的句柄。
  • signal_handle：用于处理信号的句柄（如处理 Ctrl+C）。

• 参数解释：

  • cfg.enable_io：如果为 true，启用 IO 支持；否则，不创建 IO 栈。
  • cfg.nevents：指定事件队列的大小，用于多路复用器。

2. 创建时钟

1

let clock = create_clock(cfg.enable_pause_time, cfg.start_paused);

• 调用 create_clock 创建时钟组件，用于时间相关功能的管理，返回一个 Clock 对象。
• 参数解释：
  • cfg.enable_pause_time：是否支持暂停时间。
  • cfg.start_paused：是否让时钟在启动时进入暂停状态。

时钟的主要用途：

• 为定时器、延迟任务提供精确的时间点。
• 支持测试或调试时暂停时间的功能。

3. 创建时间驱动器

1
2

let (time_driver, time_handle) =
    create_time_driver(cfg.enable_time, io_stack, &clock, cfg.workers);

• 调用 create_time_driver

  创建时间驱动器，返回：

  • time_driver：管理时间相关任务的核心组件（例如定时器、延迟任务）。
  • time_handle：与时间驱动器交互的句柄。

• 参数解释：

  • cfg.enable_time：是否启用时间功能。
  • io_stack：IO 栈，与时间驱动器共享底层的事件循环。
  • &clock：前面创建的时钟，提供时间相关支持。
  • cfg.workers：用于分配时间任务的工作线程数。

时间驱动器的主要功能：

• 实现异步延迟（如 tokio::time::sleep）。
• 管理基于时间的任务调度。

4. 返回结果

1
2
3
4
5
6
7
8
9

Ok((
    Self { inner: time_driver },
    Handle {
        io: io_handle,
        signal: signal_handle,
        time: time_handle,
        clock,
    },
))

• 返回一个包含驱动器和其句柄的元组：
  • Self { inner: time_driver }
    • 驱动器的核心部分是时间驱动器，封装到 Self 结构体中。
  • Handle：
    • 包含多个句柄，用于驱动器与外部的交互：
      • io_handle：处理 IO 事件的句柄。
      • signal_handle：处理信号的句柄。
      • time_handle：管理时间任务的句柄。
      • clock：提供时间支持的时钟实例。

tokio启动

通过launch.launch();启动所有的 worker 线程：

1
2
3
4
5

pub(crate) fn launch(mut self) {
    for worker in self.0.drain(..) {
        runtime::spawn_blocking(move || run(worker));
    }
}

runtime::spawn_blocking 调用时， || run(worker) 匿名函数会被传进去，这其实就是 worker 线程要执行的逻辑。

如下，匿名函数会被包装为 BlockingTask，并被放在 blocking thread 的 run queue 中，这样当它运行时就会执行这个匿名函数。因为这时没有足够的线程，就会初始化一个新的 OS 线程（如果有 idle 的线程，就会通过 condvar 通知），并开始执行 blocking 线程的逻辑。每个 worker 都占用一个 blocking 线程，并在 blocking 线程中运行直到最后。

1
2
3
4
5
6
7
8
9
10
11

// runtime::spawn_blocking:
let (task, _handle) = task::joinable(BlockingTask::new(func));

let mut shared = self.inner.shared.lock();
shared.queue.push_back(task);

let mut builder = thread::Builder::new(); // Create OS thread
// run worker thread
builder.spawn(move || {
    rt.blocking_spawner.inner.run(id);
})