第一阶段总结
rustlings很有用,年轻人的第一款cpp.
第二阶段总结
老实说,文档很抽象,框架体验也比较一般……
希望越来越好
希望有更多的工具相关内容,例如gdb和cmake。os相关工作其实相对少,但是学习工具的使用对各方面都很有用。
文档要是能多一些图就更好了,理解起来实在有难处。
在Rust编程中,有许多细节和技巧可以帮助开发者更好地组织代码、优化算法性能,以及确保类型安全。本篇博客汇总了一些Rust编程的核心要点和实用代码示例,涵盖了宏的使用、排序算法、树和图的操作等内容。
Rust中的宏非常强大,用于生成重复代码和提升代码的灵活性。使用#[macro_export]
可以导出宏,使其在其他模块或包中可用;而#[macro_use]
则在现代Rust中被推荐通过use
语句显式引入。
示例宏定义:
1 | #[rustfmt::skip] |
这里的#[rustfmt::skip]
用于避免自动格式化,保持代码样式的灵活性和可读性。
在实现数据结构或算法时,我们通常需要对泛型类型T施加一些特性约束,例如:
Ord
:使得元素可以比较大小,适用于排序、合并等操作。Clone
:便于复制元素值,即使是复杂类型,也可以无所有权转移地复制。Display
:实现字符串友好的格式化输出,便于打印和日志记录。这些特性可以通过where
语句在泛型实现中指定:
1 | impl<T> LinkedList<T> |
Rust通过unsafe
块支持手动管理内存和指针操作,用于高性能或底层操作。
例如,获取节点的指针并解引用:
1 | let node_ptr = Some(unsafe { NonNull::new_unchecked(Box::into_raw(node)) }); |
指针的安全解包和操作要格外小心,可以使用Option
配合unsafe
避免空指针风险。
在链表或树结构中,我们经常用到Option
类型来表示节点的存在与否。例如,在插入和查找二叉树中,可以选择使用if let
语句来处理Some
和None
的情况:
1 | fn insert(&mut self, value: T) { |
这种写法在处理可变引用时尤其简洁。
选择排序等算法需要比较泛型元素的大小,通常需要PartialOrd
特性来支持部分排序(如非全序关系的情况),而对于要求全序的场景可以使用Ord
。
在图算法中,深度优先搜索(DFS)和广度优先搜索(BFS)是两种基础的遍历方式:
DFS示例:
1 | fn dfs_util(&self, v: usize, visited: &mut HashSet<usize>, visit_order: &mut Vec<usize>) { |
BFS示例:
1 | fn bfs_with_return(&self, start: usize) -> Vec<usize> { |
Rust标准库中Vec
的swap_remove
方法可以高效地删除指定位置的元素,适用于实现优先队列等堆结构:
1 | let result = self.items.swap_remove(1); // 移除并返回指定位置的元素 |
在删除元素后,可以通过调整堆结构(如最小/最大堆)来保持堆的性质。
使用双队列实现栈的操作逻辑:
1 | pub struct myStack<T> { |
这种方法利用队列的FIFO特性来模拟栈的LIFO特性。
Rust中的Box
和unsafe
结合用于手动管理堆内存。Box::from_raw
可以从裸指针重新创建Box
,这在需要手动内存管理的场景中非常有用。
1 | unsafe fn raw_pointer_to_box(ptr: *mut Foo) -> Box<Foo> { |
这种方法常用于FFI(外部函数接口)中将指针恢复为拥有所有权的Rust类型。
Rust语言通过丰富的内存管理工具和类型系统,确保了在安全性和性能上的平衡。无论是自定义数据结构还是排序、图遍历等基础算法,Rust的特性可以为代码提供极大的灵活性和安全保障。
作业调度、高级调度(频次最低):主要解决:接纳多少个任务+接纳那哪些任务这两个工作
进程调度、低级调度(频次最高): 必须有、核心,确定哪个进程可以占有CPU并执行
中级调度:将那些暂时不能运行的进程从内存挂起到外存,(阻塞状态下进程实体(程序 + 数据 + PCB)还在内存中,而挂起状态会把进程实体挂到外存,但是PCB会存在系统内核空间中,会记录进程在外存的状态以及位置),一般在内存紧张时使用
高级调度,用于批处理系统中,将任务从外存调度到内存中去。(在分时/实时系统中,任务是直接在内存,因此没有高级调度)
分时系统:只有进程调度
批处理系统:进程调度 + 作业调度
准则:周转时间(常用于批处理系统)、平均周转时间、带权周转时间
响应时间(交互性作业、分时系统)、截止时间的保证(实时系统)、优先权准则
周转时间 = 完成时间 - 到达时间
带权周转时间 = 周转时间 / 服务时间
调度算法
FCFS(first come first serve), SJ(P)F等等
对于抢占式调度,注意服务时间的更新,然后再比较,看谁抢
高优先权 优先调度算法
静态优先权:简单,但存在饥饿现象
动态优先权:eg Rp = (等待时间 + 服务时间)/ 服务时间 作为优先权 1 + tw / ts;
时间片轮转 ……?
多级反馈队列 S1 < S2 < S3 优先权 S1 > S2 > S3
实时调度
非抢占:轮转 || 优先权
抢占:基于中断时钟,好处是减少了上下文保存切换的次数
立即抢占
实时调度算法:EDF、LLF,还有例题
其他一些??
MPS:CPU共享内存, 共享缓存(单个儿独立的,容易出现绑定,忙闲不均)
SMP中进程分配方式:静态分配和动态分配
调度方式: 自调度和成组调度(两种方式就对应了用户级线程和系统级线程), 专用处理机分配?
一些定义:
竞争非剥夺资源,或者竞争临时资源可导致死锁
从严格依次降低,为
预防 -> 避免 -> 检测与解除
上面4个条件是死锁的必要条件 , Deadlock -> 4 其逆否命题为 !4 -> !Deadlock,所以我们从4个条件入手
这是比较中庸的做法,既不损耗很多的效率,也比较的严格
一种是,资源分配表,为
Process | Allocation | Need | Available |
---|---|---|---|
另一种是,计算表
Work | Need | Allocation | work + Allocation | Finish |
---|---|---|---|---|
对资源进行分配时,分成两步
使用方法:资源分配图
几个结论
简化方法,对一个资源分配图,首先考虑持有边,如果持有者线程能够完成(获得所有需要的资源),将持有边消去后,将资源返回,如果不能完成,边消去后,仍保持资源占有,直到完成。
然后考虑请求边,如果请求的资源有空闲的,可以把边消去,若请求线程能够完成,则可将该资源返回,否则保持占有
重复上述过程,直至卡住,或者全部成孤立。
解除
通过撤销进程或者挂起进程来释放一些资源,进而推动僵持状态。
而具体的对哪些进程,以什么样的顺序进行操作,可以参考Dijkstra
之类的算法,找到一种损耗最小、利益最大的方法。
学了一门新的语言,很是开心,对于Rust这门语言,在使用了一段时间后,虽然编译器折磨了我好久好久,但是,适应后我觉得实在是太贴心了。我不用担心内存
莫名其妙崩溃,不用担心自己的代码“不够快”。对于C++来说,Rust更像工业化的结晶,浑身上下散发着标准化的气息,我认为Rust的未来是光明的,它肯定会逐渐
顶替掉现在几大编程语言的地位。
这个阶段我获益匪浅,反复修bug也极大增强了我的编程能力,真的很喜欢,就是时间好感呀┭┮﹏┭┮,现在马上时间就截止了
实现了一个TaskInfo的提取,本身难度不大,不过刚接触系统的我写了好久,后面发现关键问题后自然就“迎刃而解”了
。
实现虚拟内存,诶,之前我暑假就学习了CSAPP,对虚拟内存的运作还是比较熟悉的,可是,我没有做实验,呀呀呀呀。做实验时那个TimeVal我一直不确定怎么
处理,还有就是我一开始思路严重有问题,舍弃了已有的封装好的系统,企图自己在写一个全局内存管理器。其实用户空间跟每个任务已经绑定在一起了,轻轻push
一下就好了。在四处求救后TimVal也是解决了
这个实验不理解具体区别,我一遍就过了,嘻嘻
文件IO重定向,这个我全程独立解决,并且我认为很好的实现了最开始的要求,unlinkat能够替换掉close,并且更改到了内存。
很难,很有跳战,银行家算法也让人眼前一亮,哈哈,写出来了
诶,最后一个实验自己sys_get_time没写,一直卡关,真的好无语
在参加训练营之前,我已经简单学习了一些 Rust 的相关知识,因此 Rustlings 我非常块的就完成了。在这个阶段的学习中,我复习了一些 Rust 的卖点,像是所有权和生命周期模型;除此之外也有一些新东西,尤其是宏和单元测试相关的内容,在之前的入门学习中我只是匆匆略过,到了现在才发现还有许多我没有关注到的重要的细节。
除了对 Rust 的学习,这个阶段对于我熟悉开发工具也提供了很大的帮助。由于学习时基本接触不到现代的项目开发,我对 git 这样的开发工具以及远程仓库、第三方库等等概念都没有了解。通过在设置 Rustling 的过程中反复使用各种命令、配置开发环境,我对接触大型项目也稍微自信起来了。
第二阶段对我就是非常大的挑战了。这次训练营可以说是我第一次接触操作系统底层,中间很多课程、作业也学的很辛苦,不过看着 ci 一片绿油油的 [PASS] 还是不由得感觉到一些成就感的。
这一阶段的学习我都是按照“看简略版教程 -> 看源代码 -> 参考完整版教程 -> 尝试实现 -> 看群友讨论难点”这样的节奏完成的。中间被别的事情占了一点时间,所以最后变得很仓促,好在是压线过关了,大概我的答案还有很多问题要我回去修改吧。
lab3 现在看来是其中最基础的一课了,不过刚拿到题目的时候还是让我面对着茫茫代码无从下手。现在想来,这一章最重要的就是推动我大胆行动,不要害怕动已经写好的部分。后面的作业很多需要跨越好几级抽象直接在系统最底层的部分做改动,如果还是按照学校里对着函数填空的思维去做是不可能有办法的。
lab4 主要关注的是“地址空间”抽象,对于写习惯了应用软件的人来说“解引用指针”突然变成了一个要跨越页面页帧、从好几层字典树中查表的行为,算是一个不小的跨度了,从群友的反馈来看这一篇作业也有一定难度。不过系统已经完成的部分中其实有许多可以类比推广的部分,比如 translated_byte_buffer
的实现稍加修改就能够变成“解引用指针”的 translated_refmut
,像是作业中的其它部分也有类似的部分可以借鉴。
lab5 的 sys_spawn
可以参考 fork 和 exec 两大函数比较轻松的写完,不过 stride 算法就有一些难度了。说实话由于测例无法涵盖算法的所有问题,我在写这一段的时候也是一头雾水,到现在也不知道自己写的有没有问题。
lab6 是我认为这次作业的另一大难点,文件系统的几个 Inode
一开始让我陷入了混乱,不知不觉就把该磁盘上修改的节点修改到抽象节点上了。最后的实现也有一些偷懒的地方,链接没有和文件分开,擦除链接也有点粗暴,不过我想几个关键的思考方向我是没有搞错的。
lab8 虽然指导我使用银行家算法,但我的实现采用的是维护资源图、尝试解锁时寻找环的思路,好在从最后的结果来看我想应该是没有太大的问题的。
最后还是很幸运能通过这一阶段的训练营,感觉这两个月因为训练营过的非常充实,也对自己以后很可能投入的领域有了真正的了解,希望能带着这些收获继续走下去吧。
21年冬季就接触过rust,但是后续没有继续学,直到今年5月份劳动节假期看到rust嵌入式群里活跃的气氛才逐渐入门,这次rustlings做第三次了,这次比之前多了算法题环节。
一直有人调侃用rust写个链表,这次真就写了一次链表,rust的裸指针乱飞。
深刻理解了操作系统的上下文切换,从最开始内核创建用户态程序,到用户态发起系统调用在返回的整个流程。
工作第二年接触过内存分配的代码一直不是很明白,尤其是在触发中断时,页表是怎么从进程空间切换到内核空间,以前只是粗略的了解Linux会将内核对应的内存映射到进程空间,在这个实验中又学到“双页表这个概念”,比较两种的优劣
以前对进程创建的了解仅限于fork这个系统调用,对其他进程相关的系统调用知之甚少,这次在参考fork、exec两个系统调用实现spwan过程中,理解了为什么
这个实验中学习了文件系统在物理存储设备的布局方式,不过,该文件系统较为简单,应该是类似ramdisk的实现,并未考虑磨损均衡,实验中的部分实现也都可以偷懒。
实验中最难的部分就是文件相关的那么多结构体,部分是方便操作系统进行管理的,部分是真实存在于块设备中的索引结构以及文件组织结构。
在实验代码中也学到了rust trait对象的使用方式,Linux里一切皆文件的概念有了真切的感受。
在过去写代码时,对进程间通信没有明确概念,尤其是敲命令行时,并没有想过管道符的实现,操作系统借助文件的概念,通过标准输入输出将管道符的多个程序连接到一起,在流水线处理某一任务时又方便又能充分发挥机器性能。
到最后六小时才开始做这个,多亏群里好心人指点,才能赶在最后时间完成,不得不承认rust的静态分析真的不错,哪里变红改哪里。
在毕业两年后有机会学习清华的操作系统课程倍感荣幸,补上了我本科操作系统选修未开课的遗憾,也补上了我工作两年中知识欠缺的地方。
阶段三我来了!!!
其实在笔者去年大二的时候,就了解了一些系统赛和rCore的相关信息,当时人比现在少很多,笔者也因为课业压力很早就放弃了。今年虽然同样有些别的事要忙,但是也各抽出一周写了前两个阶段。
在此期间,充分感受到了rust的优势,如果换成cpp的话我可能早就放弃或者早就做完了(x,rust有一种被编译器推着前行的感觉,并且rcore的代码组织相当优秀,无论是抽象层还是语法设计,都十分值得学习。
第一阶段是来自rust官方社区的rustlings语法练习,并且经过了一定的增加,加了一些用得到的数据结构算法内容。总体没有什么难度,也并不需要完全弄懂,起到了一个入门的作用。所有权,生命周期,泛型之前就在moderncpp中有所涉猎,所以理解起来没有遇到什么困难。
整个第二阶段的质量相当高,除了视频以外可以说感觉做下来不逊于6.1810,题目相当的有代表性并且需要读懂很多部分的代码才能获取正确的思路,起到了很好的引导作用。
ch3的潜在难度在于内核栈较小导致无法直接传递较大的数组,导致只能通过引用来传递,即使这里并不涉及地址变换。如果在ch3中遇到了这个坑,就更能理解后续页表的意义。
ch4中带领入门了段页式的页表和页帧。需要正确掌握好页表和物理页帧的对应关系,确保这两者是同步的而且是有效的。
ch5的编码量较少,只需要找到正确的地方插入pcb的转移和下个task的获取即可。
ch7入门了fs的抽象,从OSInode到Inode到diskInode到blockcache的抽象,层层深入,再加上用于查找的dirEnrty和fdtable,使得整个抽象层设计相当清晰。
ch8的难度在于语义含糊,我们仅有两类资源,其中mutex每种只有一个,semaphore每种可以有多个。在此基础上需要正确的理解need和alloc对应的语义,并且在阻塞线程被唤醒时及时更新。
之前自己写过rustlings的一部分,这次是完整地完成了。rust和其他语言的不同之处在于,所有权、借用和引用检查等,在内存管理、安全性、并发性方面都有其优势和特点。
这段时间的操作系统学习让我了解了计算机系统中各个模块的结构和交互过程。从搭建实验环境到实现进程管理、文件系统与并发控制,我逐步掌握了操作系统的核心概念与实现方法。
在实验环境配置上,通过熟悉 QEMU 等模拟工具的配置,我能够创建隔离的测试环境,保证了开发过程的安全性和可控性。紧接着,在应用程序与基本执行环境部分,我学习了如何在内存中定位程序的不同部分,了解了程序的加载和执行过程,打下了对操作系统基本管理能力的初步认知。
随着课程深入,我逐渐接触到批处理系统和多道程序设计,进一步理解了操作系统资源分配与调度策略。这帮助我认识到系统资源的有限性,以及多任务分配中提高资源利用率的必要性。在此基础上,我学习了进程及地址空间的相关知识,理解了分时多任务的原理,并学会了如何通过调度算法提升系统响应速度和处理效率。
在进程管理与进程间通信部分,我逐步掌握了如何创建和管理进程,以及进程如何在系统中相互通信。这些内容让我理解了操作系统在多任务处理中的关键作用,也使我了解到不同进程通信方式的特点和应用场景。
最后,通过对文件系统与 I/O 重定向的学习,我了解了数据存储、访问控制与设备交互的基本机制。此外,并发编程的知识让我对线程和同步控制有了更清晰的认识,并学会了如何在多任务环境下避免资源竞争和死锁问题。
总体而言,这次学习不仅使我对操作系统的工作原理有了系统化的理解,还培养了我的编程能力和调试技能。操作系统涉及的原理性问题较多,需要不断在实践中加深理解,也让我认识到学习操作系统的深度和广度,为未来进一步的深入学习打下了坚实的基础。
因为之前没有学习过操作系统,每个任务对我来讲都很困难,这次算是入门。
有很多代码在写lab的时候实际上还没仔细看。
有些功能可能写的不够漂亮,test偏弱,可能还有一些错误没有被发现。
首先非常感谢训练营的主办方为我们提供了交流的平台和详细的文档,也非常感谢群里的助教和各位大佬们。作为一个已经工作了几年的人,如果没有这次训练营的机会,我很难相信自己能把操作系统重新捡起来并坚持学习。
这个阶段我主要是通过rustlings来零基础学习rust语法,主要参考的的书籍有《Rust圣经》和《Rust程序设计》。感觉rustlings有些过于简单,只能用来粗略地学习一下语法,通过了也谈不上熟练,我就在后面的项目编程中因此浪费了大量的时间去调试一下基础的rust语法问题,后期准备通过斯坦福的cs110l课程来加深下对rust在内存安全方面的理解。此外,在数据结构和算法部分我也主要靠chatGPT提供思路,很受打击,未来准备在leetcode上多刷下题来长长见识。
再次感谢文档的详细和版本划分的合理,本来之前停留在课本上的内存划分、进程调度、cache、并发等概念都变得触手可用,操作系统的迷雾总算被拨开了一角。
ch1里主要是摆脱了标准库依赖构建了祼机执行环境。通过qemu模拟器加载了最初版本的内核并在屏幕上输出了文字,我第一次感觉到了操作系统其实也和普通的应用程序一样,克服了畏难情绪。在这里也对第一性原理也了进一步的了解,再复杂的程序它的最初版本也是比较精简和易于理解的,从能完成最小功能的初始版本开始,会更有利于进一步学习其它更加抽象的概念。
ch2里的难点在于汇编知识和链接器的使用。我以前对于链接器的认识仅限于使用c++第三方库,但ch2里对于link_app.S的使用让我大开眼界,原来程序链接时每个段的处理可以这么灵活。同时,我也学到了在rust里通过extern c引入外部汇编文件定义的符号,可以直接拿到内存地址。我之前没有学过riscv架构,未来准备通过《RISC-V体系结构编程与实践》系统学习。
ch3里的难点在于汇编写的_switch在任务切换里的作用,例如保存寄存器、切换栈、切换控制流等。内核通过内嵌ecall汇编指令来引发trap异常陷入S特权级。抢占式调度里让我认识了时钟中断,原来轮转调度里的时间片就是通过定时器来触发时钟中断,进行任务切换。
ch4里内存地址空间我认为是最有趣也是最难的部分。通过为用户和内核单独实现的地址空间,解释了虚地址和物理地址的由来。为了实现地址空间,rcore里设计了大量的数据结构,重点要掌握MapArea和MemorySet里接口的使用,查找页表、生成地址空间等核心功能都在里面实现。
ch5里进程的精华主要在于fork和exec等系统调用的实现,本章还实现了一个shell程序,让我理解到了进程怎么从一个程序通过fork和exec运行其它程序的。
ch6里是文件的实现,ch8里是并发,我对这两章的理解不太深,主要还是围绕测试案例来理解的,后续还要再反复多次的看看文档。
现在非常期待下一阶段ArceOS的学习,希望能成为我入门hypervisor的阶梯!!!
身为一名java开发,对rust已经是神往已久,没有垃圾回收,没有STW这种不优雅的东西,我无法给自己一个不学它的理由。
rust的生命周期和和所有权等一系列强规范,虽然如同戴着镣铐跳舞,但是只要运用得当就是优美且安全的代码,希望以后可以从事相关的开发工作。
作为本硕都是机械,之后自学跑路java开发的我来说,操作系统之流、这些基础学科,只是停留在面试的八股中。平时自己也想补齐一些短板,但都被无边的业务给推的无限延期。
曾经也尝试过自学,但是缺少志同道合的小伙伴,也缺少正确的路径和学习材料,一直不得要领。
机缘巧合我遇见了咱开源操作系统社区,很多同学都是在校的学生,让我重回18,课后作业和细致的教程又让我回到了几年前的上学时光。
虽然空的时间不是很多,基础知识也很薄弱,回头还要再补习一下计算机组成的知识,但也是很艰难的坚持下来了。
现在已经对操作系统彻底祛魅,ch3 - ch8 从畏手畏脚到后来的越来越敢写,对我来说是巨大的进步。
现在更期待后续的学习了。