调度

三级调度：

作业调度、高级调度(频次最低)：主要解决：接纳多少个任务+接纳那哪些任务这两个工作

进程调度、低级调度(频次最高): 必须有、核心，确定哪个进程可以占有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中进程分配方式：静态分配和动态分配

  ​ 调度方式： 自调度和成组调度(两种方式就对应了用户级线程和系统级线程)， 专用处理机分配？

死锁

一些定义：

• 可剥夺资源：如主存，CPU，可以在使用时被强占的资源
• 不可剥夺资源：不可被打断抢占的资源，如驱动器，打印机
• 永久资源(外存)，临时资源(进程运行过程中临时产生的数据资源等等)

竞争非剥夺资源，或者竞争临时资源可导致死锁

死锁的必要条件

• 互斥条件：进程互斥的使用临界资源
• 不剥夺条件(不可抢占)
• 请求-保持条件：进程在申请新的资源的同时，保持对某些资源的占有
• 环路等待：循环等待链

解决死锁的方法

从严格依次降低，为

预防 -> 避免 -> 检测与解除

预防

上面4个条件是死锁的必要条件 ， Deadlock -> 4 其逆否命题为 !4 -> !Deadlock,所以我们从4个条件入手

1. 互斥，并没有好的办法
2. 不抢占：不抢占变成”抢占”，如果进程申请不到全部资源时，主动释放
3. 请求保持条件：使用AND机制，但是有点浪费资源
4. 环路等待：破除环路，资源排序，参考哲学家进餐

避免死锁

这是比较中庸的做法，既不损耗很多的效率，也比较的严格

银行家算法

一种是，资源分配表，为

另一种是，计算表

对资源进行分配时，分成两步

1. 判断分配请求 R是否满足 R < Available && R < Need
2. 如果满足1，使用表1表示分配后的资源表T1，再次计算是否存在安全序列，如果不安全，退回至T0，否则保存T1，下次分配将从T1开始。

检测和解除

使用方法：资源分配图

几个结论

• 不可完全简化 => 存在死锁
• 分配图中无环 => 不会存在死锁
• 分配图中有环 => 不一定死锁

简化方法，对一个资源分配图，首先考虑持有边，如果持有者线程能够完成(获得所有需要的资源)，将持有边消去后，将资源返回，如果不能完成，边消去后，仍保持资源占有，直到完成。

然后考虑请求边，如果请求的资源有空闲的，可以把边消去，若请求线程能够完成，则可将该资源返回，否则保持占有

重复上述过程，直至卡住，或者全部成孤立。

解除

通过撤销进程或者挂起进程来释放一些资源，进而推动僵持状态。

而具体的对哪些进程，以什么样的顺序进行操作，可以参考Dijkstra之类的算法，找到一种损耗最小、利益最大的方法。

阶段一：rust语言学习阶段

学了一门新的语言，很是开心，对于Rust这门语言，在使用了一段时间后，虽然编译器折磨了我好久好久，但是，适应后我觉得实在是太贴心了。我不用担心内存
莫名其妙崩溃，不用担心自己的代码“不够快”。对于C++来说，Rust更像工业化的结晶，浑身上下散发着标准化的气息，我认为Rust的未来是光明的，它肯定会逐渐
顶替掉现在几大编程语言的地位。

阶段二：rCore OS设计实现阶段

这个阶段我获益匪浅，反复修bug也极大增强了我的编程能力，真的很喜欢，就是时间好感呀┭┮﹏┭┮，现在马上时间就截止了

lab1

实现了一个TaskInfo的提取，本身难度不大，不过刚接触系统的我写了好久，后面发现关键问题后自然就“迎刃而解”了
。

lab2

实现虚拟内存，诶，之前我暑假就学习了CSAPP，对虚拟内存的运作还是比较熟悉的，可是，我没有做实验，呀呀呀呀。做实验时那个TimeVal我一直不确定怎么
处理，还有就是我一开始思路严重有问题，舍弃了已有的封装好的系统，企图自己在写一个全局内存管理器。其实用户空间跟每个任务已经绑定在一起了，轻轻push
一下就好了。在四处求救后TimVal也是解决了

lab3

这个实验不理解具体区别，我一遍就过了，嘻嘻

lab4

文件IO重定向，这个我全程独立解决，并且我认为很好的实现了最开始的要求，unlinkat能够替换掉close,并且更改到了内存。

lab5

很难，很有跳战，银行家算法也让人眼前一亮，哈哈，写出来了

其他：

诶，最后一个实验自己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 虽然指导我使用银行家算法，但我的实现采用的是维护资源图、尝试解锁时寻找环的思路，好在从最后的结果来看我想应该是没有太大的问题的。

最后还是很幸运能通过这一阶段的训练营，感觉这两个月因为训练营过的非常充实，也对自己以后很可能投入的领域有了真正的了解，希望能带着这些收获继续走下去吧。

阶段1

21年冬季就接触过rust，但是后续没有继续学，直到今年5月份劳动节假期看到rust嵌入式群里活跃的气氛才逐渐入门，这次rustlings做第三次了，这次比之前多了算法题环节。
一直有人调侃用rust写个链表，这次真就写了一次链表，rust的裸指针乱飞。

阶段2

ch1-3

深刻理解了操作系统的上下文切换，从最开始内核创建用户态程序，到用户态发起系统调用在返回的整个流程。

ch4

工作第二年接触过内存分配的代码一直不是很明白，尤其是在触发中断时，页表是怎么从进程空间切换到内核空间，以前只是粗略的了解Linux会将内核对应的内存映射到进程空间，在这个实验中又学到“双页表这个概念”，比较两种的优劣

ch5

以前对进程创建的了解仅限于fork这个系统调用，对其他进程相关的系统调用知之甚少，这次在参考fork、exec两个系统调用实现spwan过程中，理解了为什么

ch6

这个实验中学习了文件系统在物理存储设备的布局方式，不过，该文件系统较为简单，应该是类似ramdisk的实现，并未考虑磨损均衡，实验中的部分实现也都可以偷懒。
实验中最难的部分就是文件相关的那么多结构体，部分是方便操作系统进行管理的，部分是真实存在于块设备中的索引结构以及文件组织结构。
在实验代码中也学到了rust trait对象的使用方式，Linux里一切皆文件的概念有了真切的感受。

ch7

在过去写代码时，对进程间通信没有明确概念，尤其是敲命令行时，并没有想过管道符的实现，操作系统借助文件的概念，通过标准输入输出将管道符的多个程序连接到一起，在流水线处理某一任务时又方便又能充分发挥机器性能。

ch8

到最后六小时才开始做这个，多亏群里好心人指点，才能赶在最后时间完成，不得不承认rust的静态分析真的不错，哪里变红改哪里。

感想

在毕业两年后有机会学习清华的操作系统课程倍感荣幸，补上了我本科操作系统选修未开课的遗憾，也补上了我工作两年中知识欠缺的地方。

阶段三我来了！！！

前言

其实在笔者去年大二的时候，就了解了一些系统赛和rCore的相关信息，当时人比现在少很多，笔者也因为课业压力很早就放弃了。今年虽然同样有些别的事要忙，但是也各抽出一周写了前两个阶段。

在此期间，充分感受到了rust的优势，如果换成cpp的话我可能早就放弃或者早就做完了（x，rust有一种被编译器推着前行的感觉，并且rcore的代码组织相当优秀，无论是抽象层还是语法设计，都十分值得学习。

rustlings

第一阶段是来自rust官方社区的rustlings语法练习，并且经过了一定的增加，加了一些用得到的数据结构算法内容。总体没有什么难度，也并不需要完全弄懂，起到了一个入门的作用。所有权，生命周期，泛型之前就在moderncpp中有所涉猎，所以理解起来没有遇到什么困难。

rCore

整个第二阶段的质量相当高，除了视频以外可以说感觉做下来不逊于6.1810，题目相当的有代表性并且需要读懂很多部分的代码才能获取正确的思路，起到了很好的引导作用。

ch3

ch3的潜在难度在于内核栈较小导致无法直接传递较大的数组，导致只能通过引用来传递，即使这里并不涉及地址变换。如果在ch3中遇到了这个坑，就更能理解后续页表的意义。

ch4

ch4中带领入门了段页式的页表和页帧。需要正确掌握好页表和物理页帧的对应关系，确保这两者是同步的而且是有效的。

ch5

ch5的编码量较少，只需要找到正确的地方插入pcb的转移和下个task的获取即可。

ch7

ch7入门了fs的抽象，从OSInode到Inode到diskInode到blockcache的抽象，层层深入，再加上用于查找的dirEnrty和fdtable，使得整个抽象层设计相当清晰。

ch8

ch8的难度在于语义含糊，我们仅有两类资源，其中mutex每种只有一个，semaphore每种可以有多个。在此基础上需要正确的理解need和alloc对应的语义，并且在阻塞线程被唤醒时及时更新。

第一阶段

之前自己写过rustlings的一部分，这次是完整地完成了。rust和其他语言的不同之处在于，所有权、借用和引用检查等，在内存管理、安全性、并发性方面都有其优势和特点。

第二阶段

这段时间的操作系统学习让我了解了计算机系统中各个模块的结构和交互过程。从搭建实验环境到实现进程管理、文件系统与并发控制，我逐步掌握了操作系统的核心概念与实现方法。

在实验环境配置上，通过熟悉 QEMU 等模拟工具的配置，我能够创建隔离的测试环境，保证了开发过程的安全性和可控性。紧接着，在应用程序与基本执行环境部分，我学习了如何在内存中定位程序的不同部分，了解了程序的加载和执行过程，打下了对操作系统基本管理能力的初步认知。

随着课程深入，我逐渐接触到批处理系统和多道程序设计，进一步理解了操作系统资源分配与调度策略。这帮助我认识到系统资源的有限性，以及多任务分配中提高资源利用率的必要性。在此基础上，我学习了进程及地址空间的相关知识，理解了分时多任务的原理，并学会了如何通过调度算法提升系统响应速度和处理效率。

在进程管理与进程间通信部分，我逐步掌握了如何创建和管理进程，以及进程如何在系统中相互通信。这些内容让我理解了操作系统在多任务处理中的关键作用，也使我了解到不同进程通信方式的特点和应用场景。

最后，通过对文件系统与 I/O 重定向的学习，我了解了数据存储、访问控制与设备交互的基本机制。此外，并发编程的知识让我对线程和同步控制有了更清晰的认识，并学会了如何在多任务环境下避免资源竞争和死锁问题。

总体而言，这次学习不仅使我对操作系统的工作原理有了系统化的理解，还培养了我的编程能力和调试技能。操作系统涉及的原理性问题较多，需要不断在实践中加深理解，也让我认识到学习操作系统的深度和广度，为未来进一步的深入学习打下了坚实的基础。

收获

因为之前没有学习过操作系统，每个任务对我来讲都很困难，这次算是入门。

TODO

有很多代码在写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的阶梯！！！

阶段一： rust语言基础

身为一名java开发，对rust已经是神往已久，没有垃圾回收，没有STW这种不优雅的东西，我无法给自己一个不学它的理由。

rust的生命周期和和所有权等一系列强规范，虽然如同戴着镣铐跳舞，但是只要运用得当就是优美且安全的代码，希望以后可以从事相关的开发工作。

阶段二：rCore OS设计实现阶段

作为本硕都是机械，之后自学跑路java开发的我来说，操作系统之流、这些基础学科，只是停留在面试的八股中。平时自己也想补齐一些短板，但都被无边的业务给推的无限延期。

曾经也尝试过自学，但是缺少志同道合的小伙伴，也缺少正确的路径和学习材料，一直不得要领。

机缘巧合我遇见了咱开源操作系统社区，很多同学都是在校的学生，让我重回18，课后作业和细致的教程又让我回到了几年前的上学时光。

虽然空的时间不是很多，基础知识也很薄弱，回头还要再补习一下计算机组成的知识，但也是很艰难的坚持下来了。

现在已经对操作系统彻底祛魅，ch3 - ch8 从畏手畏脚到后来的越来越敢写，对我来说是巨大的进步。

现在更期待后续的学习了。

专业阶段总结

四个抽象

• 执行环境
• 进程
• 地址空间
• 文件

  五个特征

• 虚拟化
  • 内存地址虚拟化
  • 内存大小虚拟化：通过引入硬盘空间、
  • CPU虚拟化：通过分时以及快速切换
• 并发
• 异步
• 共享
• 持久

程序编译流程

• 预处理：宏展开
• 编译器： ——> 汇编语言
• 汇编器：——> 目标代码
• 链接器：——> 可执行文件

不使用标准库

#![no_std]添加在文件开头

禁用默认的main

#![no_main]

qemu启动流程

1
2
3
4
5

qemu-system-riscv64 \
    -machine virt \
    -nographic \
    -bios ../bootloader/rustsbi-qemu.bin \
    -device loader,file=target/riscv64gc-unknown-none-elf/release/os.bin,addr=0x80200000

• virt 硬件平台上，物理内存的起始物理地址为 0x80000000 ，物理内存的默认大小为 128MiB，所以物理地址空间为[0x80000000,0x88000000)
• 启动时先将sbi文件加载到0x8000 0000, 将os.bin 加载到0x8020 0000

计算机启动的三个阶段：

1. CPU固有的一些程序，对应于QEMU就是其自带的一段程序，该程序第一条指令在0x1000处，最后一条指令就是跳转到0x8000 0000 执行bootloader
2. bootloader 负责一些计算初始化工作后，再跳转到第三程序，对于RUSTSBI第三阶段程序的入口地址固定为0x8020 0000，实际的应用中bootloader会负责将操作系统程序从硬盘加载到该地址
3. 执行os的代码

GDB调试

查看内存

x/nfu addr

• n：表示要显示的内存单元的数量。
• f：格式，可以是 b（byte）、h（halfword，2字节）、w（word，4字节）、g（giant，8字节）等。
• u：显示的格式，可以是 x（十六进制）、d（十进制）、o（八进制）、t（二进制）等。
• addr：内存地址。

  打印寄存器

  p/x $xx

特权级切换

S模式下的控制状态寄存器（CSR）

• sstatus:SPP 等字段给出 Trap 发生之前 CPU 处在哪个特权级（S/U）等信息
• sepc：当 Trap 是一个异常的时候，记录 Trap 发生之前执行的最后一条指令的地址
• scause: Trap的原因
• stval: Trap的附加信息 (例如缺页异常时的虚拟地址)
• stvec: Trap处理程序的入口地址

硬件

当执行ecall时，硬件的工作：

• sstatus 的 SPP 字段会被修改为 CPU 当前的特权级（U/S）。
• sepc ecall的地址记录在sepc寄存器中
• scause/stval 分别会被修改成这次 Trap 的原因以及相关的附加信息。
• CPU 会跳转到 stvec 所设置的 Trap 处理入口地址，并将当前特权级设置为 S ，然后从Trap 处理入口地址处开始执行。

sret

• CPU 会将当前的特权级按照 sstatus 的 SPP 字段设置为 U 或者 S ；
• CPU 会跳转到 sepc 寄存器指向的那条指令，然后继续执行。

  软件（操作系统）

  在内存中存在两个全局变量，分别表示用户栈和内核栈，位于操作系统程序的.bss段
  从用户栈切换到内核栈，只需要将寄存器sp值进行更改即可

虚拟内存

当程序所需空间大于物理内存时怎么办。在没有虚拟内存前一种方法是，程序员对程序手工分段，依次将每段程序装入内存中运行。
虚拟存储器与此类似，只是由操作系统每次将正在使用的一部分放入内存，其余存在硬盘上。

• 虚拟存储器大小由处理器位数决定，对32位处理器来说地址范围为$0 \sim FFFF\quad FFFF$，其中某一地址就叫做虚拟地址（VA）
• 没有使用虚拟地址的系统，其处理器输出的地址直接就是物理地址（PA），而如果使用了虚拟地址，则处理器输出的就是虚拟地址了，其需要通过内存管理单元（MMU）转换成物理地址
• 优点：使用虚拟地址的一大优点，对于需要同时运行多个程序的系统来说，每个系统都可以随意使用地址空间，不需要考虑地址的限制。以及保护（同一虚拟地址可以转换为不同物理地址）和共享（不同虚拟地址可以转换为统一物理地址）

  地址转换

  目前虚拟存储器通常使用请求分页（demand page）的方式实现，将虚拟内存按页划分，典型的是4KB，物理地址空间按同样大小划分，称为frame。
  对4KB大小的页，页内索引需要12位，即VA[11:0]，称为page offset，剩余部分可以看做是页编号VPN（virtual page number）。相应的PA[11:0]是frame offset，剩余部分PA[:11]是PFN(physical frame number)。从虚拟地址到物理地址的转换时间上就是VPN到PFN的转换。

  单级页表

  当要访问的page，没有与物理内存中的某个frame形成映射关系时，即需要的内容不在物理内存中，此时发生缺页异常（page fault），需要将内容从硬盘加载到内存中。
  操作系统如何知道page和frame的对应关系？目前普遍使用表格存储VPN到PFN的映射，称为页表（page table，PT），一般存放在物理内存中。
• 每个程序都有一个张页表，页表在物理内存中的首地址存放在页表寄存器中
• 页表与cache不同，其包含了所有VPN的映射关系
• 操作系统会在不同进程之间进行切换，在当前进程被替换掉之前，需要保存其状态，对于页表来说只需要保存页表寄存器就好
• 页表存在于物理内存中，因此一次取数据需要访问两次内存，第一次是访问页表完成VPN到PFN的转换，第二次是用物理地址来访问内存

一张页表存储了所有VPN的映射因此，对32位处理器，其虚拟空间为4GB，假设页大小为4KB，则VPN编号为VA[31:12]共20位，则一个页表有$2^{20}$项，假设每项占32位，则页表大小为4MB。而对64位处理器，一张页表达到了PB大小，这已经超出了物理内存的大小。而且大多数程序也不会用光虚拟空间，只会使用一小部分，页表项大多都是空的。解决方法就是多级页表

多级页表

通过引入多级页表，页表也无需占用一块连续空间。页表中的一项称为PTE（page table entry）
多级页表的引入，使得访问数据需要的访存次数增加

缺页异常

缺页异常通过是由软件来处理

• 这是因为发生缺页是需要将数据从磁盘搬运到内存，读磁盘所需时间对异常处理程序来说绰绰有余。
• 处理过程中可能需要进行页替换，使用软件来处理更加灵活，可以按需选择合适的替换策略

发生缺页异常时，如何知道虚拟地址中的一个页在硬盘哪个位置？

• 操作系统会为每个进程的所有页在硬盘中开辟一块空间（swap空间），同时建立一张表保存每个页在硬盘中的位置
  缺页处理可能会发生页替换，为了保证一致性，对页表项添加一个脏位，此外为了实现LRU替换策略，添加一个使用位，当使用位为1说明该页最近访问过，操作系统会周期性将使用位置0.
  缺页异常的硬件支持：
• 缺页发生时，硬件会产生相应的异常，并跳转值异常处理程序
• 脏位
• 使用位

除此之外还可以通过在PTE中添加AP来实现访问控制，添加cacheable来表示是否允许被缓存

引入TLB和cache

TLB

多级页表节省了页表的存储空间，但是也增加了防存次数。因此引入缓存思想，对最近访问过的PTE（页表项）进行缓存，这个缓存被称为TLB，其本质就是页表的cache。不过其只有时间相关性。
现代处理器通常采用二级TLB，第一级是哈佛结构即分为指令TLB和数据TLB，一般全相连，容量不大，第二级则是组相连模式。

TLB缺失

TLB是页表的一个子集

1. 虚拟地址对应的页不在物理内存中，此时页表中对应的PTE是空的，所以TLB中也一定不会有相关信息
2. 虚拟地址对应的页已经在物理内存中，则页表中对应PTE是有效的，但可能该PTE不在TLB中。

要解决TLB缺失，本质是从页表中找到相应PTE，将其写入TLB中，这个过程叫Page Table Walk。该过程可以用硬件实现，也可以用软件实现。

1. 软件实现：发生缺失时，硬件将产生缺失的虚拟地址保存到一个特定寄存器中，同时产生一个TLB miss 异常，然后执行异常处理程序，这个过程中可能还会出现缺页异常。软件的优点就是灵活，可以调整TLB写入换出的算法。软件实现中，当发生TLB miss时，流水线中的指令需要清空用于执行异常处理程序，有一个流水线清空和恢复的操作，流水线越深，清空的指令越多。
2. 硬件实现：一般由内存管理单元MMU实现。好处就是不需要清空恢复流水线

一种LRU近似算法：假设TLB使用全相连，使用一个计数器每周期加一，计数器宽度为TLB表项数目，当TLB表中的项目需要被替换时，就以此时计数器中的数作为要被换出的表项编号。

TLB的写入

TLB与页表的一致性。
在对物理内存进行页替换时，需要检查被替换页PTE的脏位，如果是1，需要将被替换页内存写回硬盘，如果是0可以直接替换。
而引入了TLB后，就产生了TLB中表项与PTE的一致性问题。load和store命令都会先去查看TLB，如果存在对应的项，则会将use bit置1，此外store指令会将脏位变为1，这时TLB与页表就产生了不一致。如果使用写回策略，那么知道该TLB表项被替换才会更新页表，在此之间如果系统发生了页替换，系统可能以为该内存页没有更新而直接覆盖。

解决方法：页替换发生在page fault时，在进行页替换前，先将TLB写回页表，然后再执行替换

进程调度

批处理系统的调度

特点：计算为主，少量I/O

约束条件

1. 每个进程同时到达。
2. 进程的执行时间是已知的。
3. 进程在整个执行过程期间很少执行I/O操作。
4. 进程在执行过程中不会被抢占。

性能指标

周转时间（turn around），即进程完成时间（completion）与进程到达时间（arrival）的差值：
$T_{turn} = T_{complete} - T_{arrive}$
平均周转：
$T_{avg} = \frac{1}{n}\sum T_{turn}$

先来先服务FIFO

通常使用队列来实现：

• 就绪队列
• 阻塞队列

优点：

• 实现简单
• 公平

缺点：

• 如果长任务先到，那么短任务会被迫等待很长时间，使得平均周转时间变长

最短作业优先SJF

在约束条件下，如果把平均周转时间作为唯一的性能指标，那么SJF是一个最优调度算法。

交互式系统的调度

约束条件

1. 每个进程可不同时间到达。
2. 每个进程的执行时间不同。
3. 进程的执行时间是已知的。
4. 进程在整个执行过程期间会执行I/O操作。
5. 进程在执行过程中会被抢占。

性能指标

目标是提高用户的交互性体验和减少I/O响应时间
响应时间（response time），即从程序到达到第一次被执行的时间

最短完成时间优先（STCF）

• 在支持抢占式的系统上，可以改善周转时间
• 但对于响应时间，FIFO/SJF/STCF都没用特别好的效果

  基于时间片的轮转

• 每个任务轮流占用CPU一段时间
• 时间片越短，任务得到响应越快，但存在进行切换开销
• 任务越多，轮到下一次执行的时间越长，系统平均周转时间也会变长

通用计算机系统的调度

约束条件

1. 每个进程可不同时间到达。
2. 每个进程的执行时间不同。
3. 进程的启动时间和执行时间是未知的。
4. 进程在整个执行过程期间会执行I/O操作。
5. 进程在执行过程中会被抢占。

   固定优先级的多级无反馈队列Multi-level Feedback Queue

   一般CPU密集型优先级低，I/O密集型优先级高
6. 如果进程PA的优先级 > PB的优先级，抢占并运行PA。
7. 如果进程PA的优先级 = PB的优先级，轮转运行PA和PB。

难点：

• 无法预估程序的类型
• I/O密集程度多样

  可降低优先级的多级反馈队列

• 动态调整进程的优先级
• 操作系统首先需要以优先级的数量来建立多个队列。当然这个数量是一个经验值，比如Linux操作系统设置了140个优先级。
• 优先级的变化是单向的，一个进程的优先级只会持平/降低
• 低优先级可能会一直无法拿到CPU，产生饥饿现象

如何提升优先级

• 定期统计进程在就绪态/阻塞态的等待时间，等待时间越长，其优先级的提升度就越高

语言基础

编译

rustc **.rs

项目构建cargo

cargo build默认根据代码创建一个可执行文件
cargo run 运行程序
cargo check检查语法和类型错误

模块

crate
一个crate相当于C++中的翻译单元

• binary crate 可以被编译成可执行程序，其必须有一个main函数作为程序入口
• library crate 常说的库文件，用于供其他程序调用

package

包是crate的集合，由一个Cargo.toml文件定义，可以有多个binary crate 但最多有一个库
在使用cargo new创建一个包后，默认包含一个以src/main.rs为入口的同名binary crate；
如果还有一个src/lib.rs文件，则包还包含了一个同名的library crate

modules

module 是关于在一个crate内如何组织代码
编译期在编译时，首先从src/main.rs开始查找要编译的代码

模块声明

可以通过mod xxx {} 来直接在文件内定义一个模块。

• 一个module内的成员默认是模块私有的，如果想要在模块外使用，必须声明为pub

子模块

模块允许嵌套，子模块的成员要想被最外层的访问，其每一层都需要pub关键字

字符串

字面量的类型是&str

1

let s = "hello, world";

带所有权的String，分配在堆上，底层是一个Vec，注意结尾没有null

1
2

let s = String::with_capacity(32);
s.push_str("Hello world");

这里会在堆上申请32字节的内存，在栈上创建指针s(p, 11, 32)

String 和 &str

&str to String

• to_owned：从借用类型创建拥有所有权的副本，适用于任何实现了 ToOwned 特性的类型。
• to_string：将实现了 Display 特性的类型转换为 String。
• String::from 和 .into()：将 &str 转换为 String，分别适用于显式和隐式转换。

字符串拼接

使用+号进行拼接时，左侧必须是一个String类型，而右操作数则必须是&str，其中&String可以自动转成&str

Unwrap 和 ？

1. unwrap 是一个方法，通常用于在你确定一个 Result 或 Option 包含值时获取该值。如果 Result 或 Option 包含 Err 或 None，调用 unwrap 会导致程序崩溃，并显示一个错误信息。因此，使用 unwrap 时，你应该确保被操作的 Result 或 Option 不会为 Err 或 None。
2. ? 是一个在函数中处理错误的语法糖，它可以帮助你编写更简洁的代码。当你在一个返回 Result 或 Option 的函数中使用 ? 时，如果结果为 Err 或 None，? 会立即返回该错误，否则它会解包 Ok 或 Some 中的值。这种方式允许你在遇到错误时将错误传播给调用者，而不需要显式地处理每一个可能的错误情况。

traits

在 Rust 中，实现 trait 时，不能直接在 trait 的函数签名中给参数添加 mut、&mut、& 等符号。这些符号只能出现在具体实现（impl）中，
而不是在 trait 定义本身。

lifetime

生命周期与引用是紧密相关的。

• 为编译期在编译期提供一种验证指针有效性的的方式
• 生命周期是指定的代码区域，引用必须在这些区域内有效

  ‘xxx

• 生命周期的标记只是描述多个引用之间的生命周期关系，不影响实际对象的真实生命周期

  标记消除

  为了减少编码量，当引用满足如下规则时，不需要标记引用的生命周期
• 针对输入参数，编译器会给每个参数不同的生命周期标记
• 对于返回值，如果函数只有一个输入参数，那么引用类型的返回值的生命周期标记与输入相同
• 如果第一个参数是&self或者&mut self那么输出的生命周期与其一致

迭代器

map的闭包参数时迭代器元素本身，而filter的闭包参数则是迭代器元素的引用，所以filter的引用符号比map多一个