本篇博客一部分内容复制于我的个人博客，略有修改。

一阶段

因为以前没怎么写过Rust，而且算法是我的薄弱项，所以多花了点时间。关于题目没什么好说的，下面说说我对Rust的整体理解。

类型系统

Rust的类型系统大致可以分成几个方面：

System F，也就是parametric polymorphism
trait，一种ad-hoc polymorphism，另外Rust没有函数重载
Associated Type，类比Haskell的functional dependecies
Const Generics，仅限于基础类型的type to kind promotion
Ownership，类似于Linear Types，但是有很多例外
Lifetime Parameter和相关的variance，例如'static <: 'a可以让全局的引用被更小的生命周期使用

Rust的trait可以看作具有强制类型参数Self的typeclass，例如：

1
2
3

trait A {
    ...
}

本质上和下面Haskell的写法差不太多。

1 2	class A Self where ...

Rust的Associated Type和Haskell的Associated Type虽然同名，但Rust的并不是Type Family，作用上来说只是一类特殊的类型参数(见functional dependencies)，防止一个trait因为类型参数不同被多次实现。

Const Generics允许将编译期常量当作类型参数，不过只有少数几个类型(primitive types)可以，如果非要在类型论中找个解释，大概是把这些类型promote到trait，然后把它们的编译期确定的值promote到type，类似Haskell的DataKinds。

Rust没有kind，没有高阶类型，因此没有Monad。可预见的未来大概也不会有高阶类型了，因为就算有也很难和现在默认具有Self类型参数的trait兼容。

但是令人惊讶的是Rust的问号?有专属语法和还有Try和Error的trait支持，还不算太难用。

ADT

Rust的Algebraic Data Types：

Empty，即感叹号!
Unit，即()
积类型，即tuple和struct
和类型，即discriminated union，也就是Rust的enum

Rust的Emtpy是编译器开的后门，程序员不能自己定义。这样的写法：

1	struct Unit;

居然是Rust的Unit，而大部分函数式编程语言或者proof assistant中这种没有constructor的定义都是Empty，就Rust搞特殊。

至于GADT，因为Rust完全没有高阶类型和阶(kind)的概念，所以GADT也基本不用想了。

所有权

Rust最有趣的部分莫过于Ownership和Borrow，目前我的实践还不够，只能大概谈一下。

首先是所有权，即

每个值都有所有权
一个值的所有权最多被一个变量持有
所有权可以在变量之间移动，或通过函数的参数和返回值移动
如果所有权没有被移动，那么当前的scope必须把它drop掉

类比到Linear Types，那么scope所有值都被使用刚好一次，即

要不然被转移
要不然被销毁

一个特殊情况是实现Copy trait的类型，这种类型的值(即stack-only的值)的所有权不会被转移而是被复制，它们不需要drop。

所有权可以被暂时借走(borrow)，这种机制叫做引用，引用是类型，分为不可变和可变两种。

不可变引用可以有多个，且可以不限次数地复制，例如：

let a = 2;
let b: &i32 = &a;
let c: &i32 = b;
test(b);
test(c);

其中test函数定义为fn test(v: &i32) {}。第三行只是把变量b复制给c，因此b并不会失去所有权，第四行就能把b传递给函数。

但是可变引用最多只有一个，下面这段代码会报错：

let mut a = 2;
let b: &mut i32 = &mut a;
let c: &mut i32 = b;
test2(b);
test2(c);

其中test2函数定义为fn test2(v: &mut i32) {}。第四行会报错，因为变量b持有的所有权已经被转移给c。

下面这段代码能通过编译：

1
2
3

let mut a = 2;
test2(&mut a);
test2(&mut a);

因为第一个可变引用已经使用完并被销毁，第二个可变引用才得以创建。

下面这段代码又会报错：

fn test2(v: &mut i32) {}

fn wrap<'a>(v: &'a mut i32) -> &'a mut i32 {
    v
}

fn main() {
    let mut a = 2;
    let b = wrap(&mut a);
    let c = wrap(&mut a);
    test2(b);
    test2(c);
}

因为main第二行b延续了a的可变引用的生命周期，导致第三行无法再借出可变引用。

智能指针和Interior Mutability

大部分智能指针，如Box、Arc等不可变，可理解成一个指向Heap上的不可变引用，连元数据也在堆上，所以长度仅有指针大小。

可变性需要内层的容器支持，叫做内部可变性，这种容器的长度等于容器的元数据长度加上内容长度，可以在堆上也可以在栈上。

包括：

RefCell：运行时检查引用规则的容器
UnsafeCell：同RefCell但是无检查
Cell：非引用访问，只能”整存整取”
Mutex：纯互斥锁，所有形式的访问都只能存在最多一个
RwLock：类似Mutex，但是允许一个写或多个读

一般Heap上的可读可写数据由智能指针和内层的容器构成，例如Arc<Mutex<Foo>>。

二阶段

首先二阶段以第一名拿下了，很开心o(￣▽￣)ブ

刚开始那几天由于不了解，不小心看到V3去了，不过收获颇丰，之前没怎么用过gdb这次算是彻底学会了。

第二阶段还学会了很多指令比如readelf、hexdump等等的用法，还有命令行tmux的使用方式。

现在回想起来似乎一路都没有遇到什么特别大的困难，必做题都是比较简单的，除了ch8以外差不多是一天一章的工作量。

ch8确实也有点麻烦，我花了两天才把死锁检测做出来。因为刚开始一直和银行家算法分不清楚，仔细看了书之后3个小时左右就解决了。

最有趣的我觉得是ch4的内存管理和ch5的进程管理。

我在ch5上实现了多核支持，并且在四个hart并行的情况下通过了所有测例，多核支持涉及dtb、thread local storage等等多个方面的知识，还要十分小心各种同步问题。

比如__switch中间必须加锁，否则其他hart可能加载还没有保存完毕的TaskContext，这个问题我调试了几个小时才找到原因，为了解决专门读了RISC-V的atomic extension，最后用LR/SC解决了问题。

我在ch6上实现了：

lazy allocation
demand paging
fork COW
mmap文件映射，包括Shared和Private两种模式

算是对内存管理有了一个比较广泛的了解吧，比较可惜的是忙别的去了，没有把页面置换做出来。

rcore-os Blog

2024春季开源操作系统训练营第一阶段总结报告-赵剑秋

一阶段

类型系统

ADT

所有权

智能指针和Interior Mutability

二阶段