0%

提供的 Rust 代码实现了一个通用的二叉堆,支持最小堆和最大堆的功能。下面是这个实现的核心组成部分的详细解释:

  1. 结构定义 (Heap<T>)

    • T: Default:这个约束确保堆中的元素可以被初始化为默认值。这对于确保堆的向量(items)可以在索引0处有一个占位符,简化索引计算非常有用。
    • count:跟踪堆中的元素数量。
    • items:一个向量,存储堆元素。堆使用基于1的索引以简化父子计算,索引0保持为虚拟。
    • comparator:一个函数指针,用于确定元素的排序,允许灵活定义最小堆或最大堆。
  2. 构造函数 (new(comparator))

    • 使用提供的比较函数初始化一个空堆,用于元素排序。
  3. 堆操作

    • 添加元素 (add):在堆的末尾插入一个新元素,然后将其向上移动以维护堆属性。这是通过比较添加的元素与其父元素并根据比较函数进行必要的交换来完成的。
    • 移除根元素 (next in Iterator implementation):移除根元素(根据堆的类型是最小或最大),将其替换为堆中的最后一个元素,然后将此元素向下移动以维护堆属性。在此过程中,堆的大小减少一个。
  4. 辅助函数

    • parent_idx, children_present, left_child_idx, right_child_idx, smallest_child_idx:这些辅助函数用于计算父和子的索引或检查子节点的存在,这对于在添加和删除操作期间导航堆至关重要。
  5. 类型特定的堆构造器 (MinHeapMaxHeap)

    • 这些是方便的包装器,提供了使用标准比较函数(对于最小堆是 a < b,对于最大堆是 a > b)轻松实例化 Heap<T> 的方法。
  6. 测试 (tests module)

    • 包含测试来验证堆的功能,包括最小堆和最大堆行为的测试。

关键特点:

  • 通用性和可重用性:堆可以处理实现了 Default 的任何类型 T,并可以使用在实例化时传递的任何比较函数,使其可以适应不同的排序需求。
  • 效率:插入和删除操作的时间复杂度为元素数量的对数,这是二叉堆的特点。
  • 迭代器集成:通过实现带有 next 方法的 Iterator 特质,允许堆在标凈 Rust 习惯用法中使用,如循环和其他基于迭代器的操作。

增强建议:

  • 错误处理:考虑可能失败的场景,如尝试从空堆中移除元素,并优雅地处理

前言

因为之前学C++结识的好友群中发了这个训练营的报名链接,想着正好OS还没有学就想着报名参加了:)。参加本次训练营之前只有csapp的计算机体系结构这一相关经验,对于Rust和RISC-V一无所知。编程能力上,主要是C++的服务器开发,做过几个分布式微服务项目,国外的一些公开课lab(CS144/CS106B/CS50等)。

总体来说第一阶段学习过程还是有点痛苦的,毕竟Rust学习曲线比较陡峭,不过也有许多特性能与C++等语言联系起来,帮助理解。在报名之后就开始翻阅先前训练营的资料开始自学Rust了,总体还是顺利的

一些链接🔗

第一阶段总结

第一阶段主要集中于Rust基础语法的学习,并完成rustlings练习题,其次是进行RISC-V指令集的学习

  • Rust因为是第一次上手,编码熟练度还不是很高,对于一些编码更高效的方式应用不熟练,算法和数据结构的实现遇到的磕绊较多
  • RISC-V基本指令比较好理解,实际编写还是差一些,能反应指令的行为,一些寄存器记不住
  • 计组和编译原理知识比较薄弱

Rust

Rust学习过程主要参考阅读了《Rust圣经》、《Rust by Example》、和Rust之旅
之后的时间主要是对《Rust圣经》中的进阶部分和基础部分进行阅读笔记并复习,基础部分难点主要集中在所有权和特征这两个知识点上,对于生命周期以及包和模块的讨论并不是特别深入。进阶部分都难哈哈哈哈,迭代器和智能指针还算比较好理解些,对于迭代器加闭包实现的函数式编程每次都让我觉得很强大,Cell和RefCell提供的内部可变性加上智能指针也给程序提供了很大的灵活性的前提下保证了一定的安全性。生命周期的使用也是一大难点了。之后还有unsafe Rust的使用以及宏编程(对比C/C++的难的多但功能性也更强大)

rustlings的基础语法部分不算特别难,不熟练的查一查就能写得出来。难点集中在test和algorithm章节,主要是test后半部分,一些环境变量的设置,以及rust实现数据结构算法所用到的unsafe rust和智能指针的操作。

之后尝试阅读Learning Rust With Entirely Too Many Linked Lists,和用Rust实现一些算法和数据结构来巩固,多敲一些代码提高熟练度,多查文档。

RISC-V学习

这部分知识学习首先是阅读了《计算机组成于设计:RISC-V版》的前两个章节,对RISC-V的基本指令和指令格式有一个了解,以及RISC-V的设计和计算机体系结构的8个伟大思想之间的联系。之前阅读csapp并完成lab实验,有些x86_64的经验,对于一些基本指令和作用的理解还算轻松。难点集中在原子指令上。之后主要阅读了《RISC-V手册》,主要重点是第十章的特权架构,涉及之后rCore的特权级切换操作以及虚拟内存的实现(SV39多级页表)

学习后可以看出RISC-V指令集的强大和简单,和x86_64不同的理念。六种基本指令格式,等长指令就能搞定一切,精妙的设计(就是有时候脑子转不过来)

查缺补漏

阅读操作系统导论,目前还在虚拟化部分,然后观看导学阶段的OS课录播,补足操作系统的理论知识和概念

前言

经过第一阶段的Rust练习和RISC-V语法的入门阅读,进入第二阶段,完成rCore的五个实验。第二阶段主要是进行操作系统的学习,并通过实验具象操作系统概念的实现。同时也在跟着Writing an OS in Rust写blog_os作为补充。

一些链接🔗

第二阶段总结

整体rCore实验难度集中在最后三个实验中,第一二章节引入简单操作系统的架构,从裸机平台构建libOS,将整个OS作为一个库给用户使用,到加入特权级切换,让操作系统找到任务并运行实现批处理OS,第三章加入yield系统调用支持多道程序,并加入时钟中断实现抢占式多任务构成多道程序与分时多任务系统。第四章开启地址空间,进一步完善了OS的安全性,应用不再有直接访问物理内存的能力,并且只能通过虚拟地址读写自己的地址空间,无法访问破坏其它应用的地址空间,同时也给操作系统提供内存管理的灵活性,通过分页机制更好地管理物理页帧,页表管理虚拟地址到物理页帧的映射转换。第五章进一步强化任务的概念为进程,加入一个简单的shell,使得用户与操作系统之间的交互能力提高,可以动态地执行应用。第六章实现了一个easyfs文件系统,对操作系统提供持久化存储。第七章通过文件系统的支持建立进程间通信,让不同应用组合在一起运行。第八章引入线程和并发的概念,让操作系统从宏观层面实现多个应用的并发执行,实现内核态管理用户态运行的线程,并支持互斥锁、信号量和条件变量这三种资源。

由于提早完成了第一阶段任务,得以提前开始第二阶段,前面通过阅读文档并复现代码熟悉整体架构,第二阶段正式开始后完成实验。

  • lab1就是简单实现获取当前执行任务的信息,为了维护系统调用次数需要为每个任务维护一个数据结构用以记录,在每次调用之前通过syscall_id查询自增。执行时间单位是ms,初始化为任务第一次调度的时间。
  • lab2因为地址空间的引入,首先是对先前的get_time和get_taskinfo接口进行修改以支持虚拟地址,实际就将用户传递的虚拟地址转换为对应的物理地址即可访问修改,不过需要注意可能会被分成两页。之后需要实现mmap和munmap接口,对虚拟内存的申请和释放,主要需要注意判断和处理可能错误,以及释放虚拟内存的步骤实现。
  • lab3首先需要实现spawn接口,实际就是fork+exec,需要注意的是不必像fork一样复制父进程的地址空间。然后需要实现stride调度算法,需要注意调度算法所需状态的初始化和维护,可以选择通过堆或者维护单调队列来实现,不过测例简单也可以直接暴力搜索,还需注意处理溢出情况,避免调度进入死循环,同时优先级的维护还需实现set_priority系统调用。
  • lab4是实现硬链接相关接口linkat和unlinkat,需要注意unlinkat对inode以及对应数据块的回收。
  • lab5是实现死锁检测,需要注意维护检测算法所需的per-thread状态以及互斥量和信号量资源。

额外题目还没实现,后续如果有时间再研究吧:)

我先说一下感觉吧,我感觉rust好难啊,真的,^^
之前是群里面发现了rcore这个文档,跟着看到第二章,发现不懂rust,然后就找教程学rust
后来发现了这个训练营,跟着这个训练营的课程进度,做rustlings练习题
一开始确实不难,到了迭代器,traits,结构体这里,差不多就看不懂了,属于是问了gpt也还是不懂的那种
后面的算法我倒是会,就是不会rust语法,然后问群友,虽然说不是每一题都问吧,也基本上是隔一两个就问
不管怎么说,通过群友们的解答和自己的努力,rustlings是做完了
总结:rust好难,^
^

2024 开源操作系统训练营第一阶段总结-刘梓陆

本来想在这里放一个图片的,但是看群里好像图片不太好处理,那就不放了

不过在这里贴一个图片仓库链接:ServiceLogos,作者画得太好看,导致我当天看到就去印贴纸了……

写在前面

我从稍微理解了我的专业之后就一直都很崇拜 Linus,这位堪称传奇的软件工程师在 1991 年 8 月 25 日——他 21 岁时就在网络上发布了 Linux 内核的源代码。现在是 2024 年 4 月 23 日,我也是 21 岁,追逐吗,梦想吗,我也想像他一样写出这样神奇的代码,33 年后的今天,我也要开始了,Linus。

欢迎交流;-)

在写这篇博客时,本人东北大学大三在读,前两年东学西学,Rust 就是之一,说实话,在本学期开始时,我实在找不到什么东西来做,准备先买一本《趣读 Linux 源码》来看,感谢我学弟翊嘉,是他给我推荐了这个操作系统训练营,这样直接上手操作系统的效果比看书要好太多了,真的十分感谢!

我对 Rust 的理解还是比较少,future、unsafe 的内容更是知之甚少,所以大佬求带!看到我这篇总结报告之中有什么不足也请指出!

Rust,很好玩

这一阶段的练习基本上带领我加强了一遍 Rust 的语法,因为我接触 Rust 已经有小半年了,所以对我来说并不算很困难(如果要我 0 基础开始的话可能就会有点受不了了)。话虽如此, rustlings 确实给了我很多细节上的考验,我通过了它们,查缺补漏,学到了很多新东西(这里就当错题集一题一题记录了 XD):

2024_4_24, PS:因为这一个阶段基本上都是一些对 Rust 语法概念上的训练,所以我会着重讲一下对 Rust 一些重要语法概念的理解,本来写了挺多的,但是后面全部都删掉了,因为突然发现我好像也就是鹦鹉学舌,纯纯就是一些对官方文档还有论坛讨论的翻译,所以我会在讲到一个我觉得值得注意的点的时候把链接贴出来,然后提一下这个链接讲了什么,同学们自己去看会好的多

2024_4_25, PS:感觉讲的有点乱了,实际上 Rust 之中的移动、生命周期、所有权的概念真的是耦合在一起的,在讲到一个部分的时候免不了要带一点其它两个部分。

1. ♿ 移动 ♿ 和借用, options3.rs 之中犯的错误

说实话,移动和所有权这个语意在其他语言里面确实存在,但是一般作为规范存在,没有在 Rust 里面管的这么严,在 options3.rs 之中我就犯了这么一个错误:

我在 main 函数之中这样写道:

1
2
3
4
5
6
7
let y: Option<Point> = Some(Point { x: 100, y: 200 });

match y {
Some(p) => println!("Co-ordinates are {},{} ", p.x, p.y),
_ => panic!("no match!"),
}
y;

这样写会报错(value used here after partial move),因为在最后返回 y 之前 Some(p)就已经把外面 y 的所有权移动到 p 上了,此时 y 指向的是一个无效的内存空间。所以现在的解决方案就是把外面 y 借用到 Some(p)之中,一个关键字 ref 可以帮助我们做到这一点。这个关键字其实用法还是挺多的,一般用于模式匹配

下面是一段在《Rust 编程指南》之中的阐述(在第 10 章 Pattern 小节 Refrence Patterns 部分之中,如果你看的是英文版的 PDF 的话,在 P372 可以找到对这个问题的详细描述):

Rust 的模式匹配支持处理引用的两个特性:Ref 模式借用匹配值的一部分,&模式匹配引用

我个人感觉可以这样理解:Rust 之中的模式匹配就像是在匹配一个正则表达式,&被理解位一个字面值字符,如果写&的话,就会把&引用的那个值“解离”出来,因为匹配了前面的一个&,自然就是匹配后面的这个“值”了。

呃,我又要引用《Rust 编程指南》之中的原话了(毕竟真的这本书很专业)

In an expression, & creates a reference.I a pattern, & matches a refrence

在一个表达式之中,&创造一个引用,在模式之中,&匹配一个引用

当时我也是被震撼,确实有一种对称的美对吧?其实在 rustlings 对应的有关模式匹配训练之中你就可以发现这一点:你可以使用()来创建一个元组,可以使用{}来创建一个结构体,当然就可以使用对应包含(){}的模式匹配来把其中对应的字段解析出来,_这是一个互逆的过程_,我觉得这一点需要好好注意一下,基本上就是模式匹配直观意义上的精髓所在了。

但是 ref更像是一个正则表达式之中的元字符,用于描述匹配规则:我只想要借用匹配的值,而不是移动它们,如果想要借出可变引用的话就要使用ref mut。所以这里这样改改,加一个ref就成功了:

1
2
3
4
match y {
Some(ref p) => println!("Co-ordinates are {},{} ", p.x, p.y),
_ => panic!("no match!"),
}

当然,如果匹配的数据实现了Copetrait 的话,你怎么样搞都行,但是在处理有所有权的对象的时候就必须小心处理了,这 Rust 真给我好好上了一课。

1.1 讲点更复杂的怎么样?

在下一部分我想要讲讲我对生命周期和所有权的理解,所以在这里我想先就着这个例子好好借题发挥,先铺垫一下。

实际上options3.rs还能出得更加复杂一点,这种情况就要把ref&同时用上才能解决。在options3.rs之中,该结构体之中的两个成员都是实现了Copytrait 的,那么如果有具有所有权的成员的话,应该如何处理呢?

就像是下面这种情况(实际上你可以在《Rust 程序设计》的 P374 找到它):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Engine {
version: String,
}

struct Car {
engine: Engine,
}

fn main() {
let borrowed_car: Option<&Car> = Some(&Car {
engine: Engine {
version: String::from("混合动力"),
},
});

match borrowed_car {
Some(&Car { engine }) => {
println!("I got the engine!");
}
None => {
println!("noting here");
}
}
}

如果你像上面这样写的话就好像是把一辆借来的车里头的引擎偷出来了。Rust 会降下它的神罚,引导我们做出正确的选择:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
error[E0507]: cannot move out of `borrowed_car.engine` as enum variant `Some` which is behind a shared reference
--> src/main.rs:16:11
|
16 | match borrowed_car {
| ^^^^^^^^^^^^
17 | Some(&Car { engine }) => {
| ------
| |
| data moved here
| move occurs because `engine` has type `Engine`, which does not implement the `Copy` trait
|
help: consider borrowing the pattern binding
|
17 | Some(&Car { ref engine }) => {
| +++

这里忍不住想要夸一下,Rust 的错误输出真的是太好了!

所以既然车是借的,引擎也应该是借的对不对?这里使用 ref 来把引擎借出来就没事了。

1.2 Temporary lifetime,什么时候会销毁?

实际上假如你修正了上面这个ref的问题仍然会报错,😭 了:

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
error[E0716]: temporary value dropped while borrowed
--> src/main.rs:10:44
|
10 | let borrowed_car: Option<&Car> = Some(&Car {
| ____________________________________________^
11 | | engine: Engine {
12 | | version: String::from("混合动力"),
13 | | },
14 | | });
| | ^ - temporary value is freed at the end of this statement
| |_____|
| creates a temporary value which is freed while still in use
15 |
16 | match borrowed_car {
| ------------ borrow later used here
|
help: consider using a `let` binding to create a longer lived value
|
10 ~ let binding = Car {
11 + engine: Engine {
12 ~ version: String::from("混合动力"),
13 + },
14 + };
15 ~ let borrowed_car: Option<&Car> = Some(&binding);
|

这里涉及到一个比较微观的问题:Rust 在背后为我们做了的事。实际上很多时候我们创建的变量的生命周期就只是一个局限于语句(statement)的 temporary lifetime,Rust 为我们做了 lifetime extention 之后才能在 block 之中使用。

在论述这个问题之前,先列一下参考文献吧:

  • 1《Temporary lifetimes》
    • 强烈建议先看这一篇,这是 Rust 开发小组的一次会议纪要,讲了现在 Rust 之中 Temporary lifetimes 的一些情况,在 Rust2024 之中要改进哪一部分,讲的比较通俗,例子也好很多
  • 2《Place Expressions and value Expressions》
    • 这篇 RustRefrence 文档之中讲到了 Rust 之中表达式的分类(类似于 C++之中的左值和右值)
  • 3《Temporary scopes》
    • 这篇文档之中谈到了我之前没有听说过的作用域 Temporary scope,我的理解就是立即值(右值)的一个小作用域
  • 4《Temporary lifetime extension》
    • 这篇文档之中讲到了 Temporary 作用域的提升,也就是为什么说一个 Temporary scopes 在进行赋值等操作之后可以将本来很小的作用域延展到和被赋予值的变量作用域相同的情况

上面这些概念之间的关系就是: The temporary scope of an expression is the scope that is used for the temporary variable that holds the result of that expression when used in a place context。(摘自文献 3)

注意这里的三个关键词:temporary scopetemporary variableplace context

处于位置上下文(place context)的表达式就是位置表达式,它代表了一个内存位置(Paths)。这些表达式是局部变量、静态变量、解引用(*expr)表达式、数组索引表达式(expr[expr])、字段引用(expr.f)和括号内的位置表达式(parenthesized place expressions

突然感觉这里举一个例子会比较好:

1
let t = &foo();

实际上是:

1
2
let tmp;
let t = { tmp = foo(); &tmp };

也就是说,&foo()是一个表达式,现在它处于一个位置上下文之中(&需要一个位置),所以现在需要一个 temporary variable(简称 temporary)来存储这个foo()表达式的结果,也就是上面的tmp,这个tmp的生命周期就是 temporary scope。

而且在这里还做了一个 lifetime-extension:如果没有 let 的话,实际上 temporary 在语句的末尾(遇到;)就会被销毁:

1
&foo();

实际上是

1
2
3
4
{
let tmp;
tmp = &foo();
}

这个立即失效的局部变量显然不符合用户的意图。因此,我们延长 temporary 的生命周期,使其在最内层块的末尾被删除(the end of the innermost block)。

实际上就是把原来局限于语句的生命周期提升了一个一个层次,提升到块了。

怎么样,是不是原来好像很理所当然的一段代码都变得不那么简单了?更多有关这部分概念的解释请参考文献 1,我在这里就不赘述了。


回到在本小节一开始提出的问题,为啥会报错?其实看报错信息就知道了,按照我们上面的思路来思考:

首先,里面这个表达式处于一个位置上下文(place context)之中,因为&期待一个位置,所以得有一个 temporary 来保存这个位置啊:

1
2
3
4
5
6
7
8
9
{
let tmp;
tmp = Car {
engine: Engine {
version: String::from("混合动力"),
},
};
&tmp
}

但是很不幸的是,这个 temporary 首先作用于 Some,而不是 let,所以不会进行 lifetime-extension,在遇到;之后,temporary 就被 drop 掉了。

出现了,悬垂引用!Rust 就 panic 了。(本节完)

2. 🌿 生命周期和所有权 🌿 - 光的波粒二象性?

“光的波粒二象性”这个比喻是油管的一个博主 ledoo 提出来的。

我觉得讲的真的很不错,所以在这里想提一提。

大概就是说,我们讲到生命周期(lifetime)就是总是从代码层面去分析对不对?去看是不是你变量的第一次声明和最后一次使用跨越了一个 block,但是实际上 Rust 做这个生命周期是为了检查内存的有效性的,你还可以从变量指向内存的位置和保证内存的有效性这两个角度来理解生命周期。(Thinking about lifetime as regions of memory, what can they——the reference point to?)

这就好像是光的波粒二象性一样,有的时候从这个角度去看比较好理解,有的时候从另外一个角度去看则更佳。 我个人觉得用这种角度去理解生命周期标注是最好的。

就拿 lifetimes1.rs 为例吧:

实际上他视频里面就有讲这个很经典的生命周期标注问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fn longest(x: &str, y: &str) -> &str {
if x.len() > y.len() {
x
} else {
y
}
}

fn main() {
let string1 = String::from("abcd");
let string2 = "xyz";

let result = longest(string1.as_str(), string2);
println!("The longest string is '{}'", result);
}

这道题的正确答案应该是这样:

1
2
3
4
5
6
7
fn longest<'a>(x: &'a str, y: &'a str) -> &'a str {
if x.len() > y.len() {
x
} else {
y
}
}

加上生命周期标注,生命标注在我初学 Rust 的时候把我虐的死去活来的,你比如说这里的'a,为什么大家都是标'a?是不是意味着所有传入的 reference 的生命周期都要是相同的?什么?返回值的生命周期也是'a?三个都要相同?啊?这限制也太严格了把?

当然,如果你读过像是 Rust 圣经的文档话,文档里面就会告诉你:实际上呢,这里的意思是以生命周期最小的那个 Reference 为准,不过呢……总感觉怪怪的。

如果你使用指向有效内存的角度来进行分析的话,我感觉就会比较好一点:

x 指向一块内存 memory_x,y 也指向一块内存 memory_y,这两块内存当然可以是不一样的,返回值也指向一块内存,那么在这里'a的作用就是说,我要统一这两块内存,返回值指向memory_x“和”memory_y。这里“和”打双引号,因为现实不可能同时指向两部分嘛。

所以 Rust 怎么检查这个返回值是否有效?答案是在这个返回值最后一次使用之前这两块内存memory_xmemory_y都要有效

如果使用生命周期约束的话,差不多也是这个意思,比如说'a: 'b比较官方的说法就是'a的生命周期的范围必须包含或等于'b的生命周期的范围。

假如我们使用“内存说”的话,就刚刚好反过来,'b指向的内存包含了'a指向的内存,所以'b有效的时候'a也一定要有效,所以你可以这样读这个限界:'a in 'b

嗯,大概就是这样。(本节完)

写在最后

首先,感谢你看到这里!

本来还想写一些 unsafe 还有 cargo 的内容的,但是没有时间了!!!!!唉,期中了,我还有 ddl 要赶呢,在这篇博客之中写的生命周期、所有权、移动的概念(话说好像都在讲生命周期)我认为就是 Rust 的核心了,所以对于第一部分的 Rust 编程学习,内容分量应该也刚刚好吧?(小小的虚荣一下,把我在第一部分之中讲的那个车和引擎的问题出成题感觉也 ٩(•̤̀ᵕ•̤́๑)ᵒᵏᵎᵎᵎᵎ?)

所以我准备移动一下,在第二阶段的报告里面把 unsafe、cargo 连着操作系统讲一下,如果你觉得从我的这篇报告学到了什么东西的话,那就太好了!

2024 年 04 月 25 日 21:14:31

初始rcore

第一次知道rcore来源于一篇知乎的帖子,当时沉迷于操作系统的学习,希望能写出一个自己的操作系统。但当时网络上更多的是对xv6的赞赏,rcore的仅仅是一句简单的提及。受限于当时初学计算机,只知语言C,不识Rust,不希望投入太多精力到语言的学习,因此并未细探rcore究竟。(当然,三分钟热度的我最后也没写完一个操作系统,希望这次能够完善地学完!)

直到去年了解到这个开源操作系统训练营,加上自学了rust的基础语法,对其很有兴趣。可惜秋冬季已经结营,加上网站上模糊的教学视频实在难以学习,便又戛然而止。直至今年四月初至,又闻开营之事(别问,问就是大数据推送),喜从心中来,急急忙忙地就上了船。

第一阶段总结

第一阶段主要是熟悉rust语法,前三十道题进展迅速,仅涉及简单语法;中间几十道题中,所有权和生命周期单列出来较为简单,但是复杂场景中的所有权问题令人头疼;最后几道算法题,除去算法本身的难度,rust对于所有权和借用的限制才是最大的难点,以至于最后纯粹是与编译器斗智斗勇,几乎快忘了实现逻辑和复杂度。

除此之外,有多道题目在完成过程中总是不解其意,仅仅是让其通过检测。知道提交通过之后,看到群友们的讨论才恍然大悟,但又懒于修改,还是默默学习的新的内容去吧。

个人介绍

本人就读于新加坡南洋理工大学,参加这个夏令营的目的是为了弥补本科时候的遗憾。在本科期间,听说了AI多么高大上,挣钱多么多,于是把目标放在了AI方向,任何的课程和科研都是围绕着AI方向。但是后面大四发现实在是卷论文卷不动了,而且其实干的很多事情都是调参,找一组好的参数发论文,这并不是我想要的生活,也不是想干的方向。于是我开始想试试开发,因为传统开发上面我毫无经验和优势,于是便去学习小众的区块链开发,发现了Rust这门宝藏语言。顺利的学习这门语言,好好读书背八股找到了大厂的工作(今年入职),但是其实操作系统等底层的知识,在本科上课的时候都是糊弄过去的,所以一直有这个遗憾。借着这个夏令营的机会,我的目标是一阶段巩固一下Rust细节知识,为后面转向区块链开发做铺垫(参加过Solana链相关的黑客松),第二个是真正的非纸上谈兵地去用喜欢的Rust语言做一下操作系统相关的开发,希望可以坚持到最后。

一阶段学习感悟——对Rust的一些感想

Rust 是一种安全的系统编程语言,它为程序员提供了实现安全的途径,而无需担心所有的实现细节。所以这里的动机是,基本上C++是不安全的。这也是 Rust 出现的原因。
这里的安全性指的是,如果你用Rust编写了一个程序,并且它满足了某些条件,那么当你将该程序编译成汇编程序时,就可以保证汇编程序不会出错。编译器和类型系统保证了这一点。与此同时,它还实现了控制,因为它支持编程中所需的所有底层功能,例如操作系统的构建,目前Linux和Windows中的系统内核中很多部分都用Rust进行了重构。尤其是C和C++在编写并发程序的时候,无法自动检测到内存的不安全性,而Rust的所有权和生命周期抓住了并发的本质,其本质上关于安全的共享资源。
下面讨论一下系统编程里面的内存模型。我认为一个编程语言,尤其是系统编程语言,或者说比较低级别的编程语言中间最重要的实际上有两件事儿,一个就是它的内存模型,或者说你的变量在内存中是如何交互的和如何表示的。另一个就是多线程的事情,就是多个线程如何操作这些内存。
首先在系统编程领域唯三的编程语言,就是C,C++和Rust。因为Rust它实际上是有很多比较新的理念,可以视为它从C++中间去抽取了很多比较精华的部分,并且它又长出来自己独有的一些东西。
因为C++里面的特性非常多,而且有很多很复杂很融坠,很多还是由于历史原因造成的。因为 C++非常强调兼容性,所以他以前的一些设计的问题,它是没有办法在未来改变的,它只能把它保留或者是把它遮蔽起来。就像你有堆垃圾,你没有办法倒到外面,你只能拿被子先盖起来,然后在这个垃圾上面去建立一些新的东西,所以很多人都觉得C++不如C语言使用起来那样舒服。那么从Rust角度来讲的话,它就没有这个历史负担,它出现的比较晚,所以他从不管从C还是从C++,还是从 Python等等其他的语言中去抽取了很多好的东西集成起来。从整体上来看的话,共性化的部分肯定是各个语言都比较重要的部分,个性化的部分的话,Rust的部分的好处多于坏,它的坏处主要是它的带来的额外的编程和编译的复杂性。

给第一周做一个总结

  • 参加这个lab的起初目的有两个:一是有可能会有实习机会,但是现在看到这么多大佬估计也挺难了哈,二是想考研408,加深自己对于操作系统的理解。另外可以丰富自己的项目知识的积累,过去一个星期了,发现自己的这个选择真是无比的正确,在学校待的两年发现什么实操都不会,学到了很多工具的使用(非常感激群里的大佬们的帮助),并且在学习的过程中也对rust产生了浓厚的兴趣,非常想去学习。
  • 第一周在学习rust的语法,主要是跟着B站的一个up主(软件工艺师)在学习,讲解的非常的好,而且没有废话,很细节,结合rust中文圣经补充一些知识。
  • 不过没学多久就准备蓝桥杯了,刚好学到生命周期那个部分,在第一周做rustlings写到48题,刷到现在感到收获很大,深刻体会到要学会一门语言是要多加练习的。
  • 接触到rust的语言之后,我对它产生了浓厚的兴趣,虽然这门语言很难,但是也很有趣,思想也很先进,不同于初学python时不用敲代码就可以掌握,学习rust经常一个语法要写好几遍才堪堪掌握。
  • 比较开心的是,学完了trait和生命周期,这两个点大家都说难,但是我认为比较好理解,看来我果然还是很有天赋的吧哈哈哈哈哈哈哈哈!!!
  • 好吧,这也没什么要记录的了,群里很多大佬在第一二天就已经将rustlings写完,而我连github还没整明白,在第二周补补知识,把rustlings写完(话说这个博客提交又要研究一个晚上了wuwuwu)。
  • 参考的rust语言圣经:https://course.rs/basic/compound-type/string-slice.html
  • 讲解的超棒的B站视频:【Rust编程语言入门教程(Rust语言/Rust权威指南配套)【已完结】-哔哩哔哩】 https://b23.tv/AaXsgZd

第二周

  • 这一周一开始把rust剩下的智能指针,多线程,闭包等全部学完了,但是直到开始写剩下的rustlings时,才发现实际写起来困难重重,经过反复的查阅官方文档以及GPT的帮助之下,才弄懂了接下来的题。
  • 但是到了algorithm的十道题,每啃一道都会花费不少的时间,需要反复检查所有权和trait的使用,
  • 建议还是反复多练习才能更好的掌握,这次新增的这十道算法题也确实帮助我更好的打好了基础。
  • 最后,非常感谢能有机会参加这次活动,希望在第二阶段可以有更多收获,同时也为社区回馈更多。

code-debug是一个支持跨特权级调试的VSCode插件。在这篇文章中,我将介绍利用这个调试插件在VSCode上对ArceOS进行源代码级调试的过程。

首先我们需要下载 gdb-multiarch :

1
sudo apt install gdb-multiarch

接着我们运行一下 ArceOS,从而生成 bin 和 elf 文件. 这里以RISC-V上的单核arceos-helloworld为例:

1
make A=apps/helloworld/ ARCH=riscv64 LOG=info SMP=1 run

在 ArceOS 的输出中,我们发现了 QEMU的启动参数:

1
qemu-system-riscv64 -m 128M -smp 1 -machine virt -bios default -kernel apps/helloworld//helloworld_riscv64-qemu-virt.bin -nographic

我们将这些启动参数转移到配置文件 launch.json 中:

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
   //launch.json
{
"version": "0.2.0",
"configurations": [
{
"type": "gdb",
"request": "launch",
"name": "Attach to Qemu",
"executable": "${userHome}/arceos/apps/helloworld/helloworld_riscv64-qemu-virt.elf",
"target": ":1234",
"remote": true,
"cwd": "${workspaceRoot}",
"valuesFormatting": "parseText",
"gdbpath": "gdb-multiarch",
"showDevDebugOutput":true,
"internalConsoleOptions": "openOnSessionStart",
"printCalls": true,
"stopAtConnect": true,
"qemuPath": "qemu-system-riscv64",
"qemuArgs": [
"-M",
"128m",
"-smp",
"1",
"-machine",
"virt",
"-bios",
"default",
"-kernel",
"apps/helloworld/helloworld_riscv64-qemu-virt.bin",
"-nographic",
"-s",
"-S"
],

"KERNEL_IN_BREAKPOINTS_LINE":65, // src/trap/mod.rs中内核入口行号。可能要修改
"KERNEL_OUT_BREAKPOINTS_LINE":124, // src/trap/mod.rs中内核出口行号。可能要修改
"GO_TO_KERNEL_LINE":30, // src/trap/mod.rs中,用于从用户态返回内核的断点行号。在rCore-Tutorial-v3中,这是set_user_trap_entry函数中的stvec::write(TRAMPOLINE as usize, TrapMode::Direct);语句。
},
]
}

我们在qemuArgs中添加了 -s -S 参数,这样qemu在启动的时候会打开gdb调试功能并且停在第一条指令处,方便我们设置断点.

此外,应当注意executable参数指向包含符号表的elf文件,而不是去除符号表后的bin文件。

由于ArceOS是unikernel,没有用到用户态,因此以下这三个参数不需要填写:

1
2
3
"KERNEL_IN_BREAKPOINTS_LINE":65, // src/trap/mod.rs中内核入口行号。可能要修改
"KERNEL_OUT_BREAKPOINTS_LINE":124, // src/trap/mod.rs中内核出口行号。可能要修改
"GO_TO_KERNEL_LINE":30, // src/trap/mod.rs中,用于从用户态返回内核的断点行号。在rCore-Tutorial-v3中,这是set_user_trap_entry函数中的stvec::write(TRAMPOLINE as usize, TrapMode::Direct);语句。

最后我们再次按f5开始调试ArceOS. 我们发现Qemu虚拟机启动,ArceOS停在了第一条指令

1
oslab@oslab:~/arceos$  qemu-system-riscv64 -M 128m -smp 1 -machine virt -bios default -kernel apps/helloworld/helloworld_riscv64-qemu-virt.bin -nographic -s -S

接下来我们设置断点。比如我们在Hello, World输出语句打一个断点,然后按”▶️”.我们会发现断点触发了:

以上,通过一些简单的设置,我们就得以用code-debug调试器插件调试一个新OS.

Unikernel 学习心得

近期学习了一些关于Unikernel的知识,以下是一些心得体会:

  • Unikernel是基于组件化的思想设计的,由各种模块构成组件,再由各种组件构成最终的操作系统。
  • 而对于各种模块是如何被选择的,则是采用feature机制,指定最终所需要的模块

ArceOS实验

  • 这周进行了ArceOS的三个实验,在练习一中学习了用println!进行彩色打印。练习二主要学会了对ArceOS进行扩展开发,在axstd中加入了Hashmap,在axhal模块中加入rng生成器,初步了解了ArceOS的调用结构。
  • 练习三修改了axalloc模块中allocator的算法,改为early算法,同时用lock()和unimplemented!()禁用其他算法