CS61C - 总结 2
CS61C 的系统基础部分。这门课出彩的地方是硬件和计算机的伟大思想具体体现，系统部分讲的不多但有点喧宾夺主，这部分和硬件关系就不大了。不过讲的依然很好。尤其是真的能把计算机领域伟大思想传递出来。
操作系统概念
操作系统干什么：整体把控了所有的设备；启动服务；加载运行程序 (time-sharing,isolation,multiplex resource)；提供了与外界交互的窗口。
操作系统需要什么：内存地址转换：为了保持程序的抽象，为了让每个进程都认为自己拥有独占的内存空间，为了假装内存无限大且极快，操作系统分配的是虚拟地址，而硬件需要负责将虚拟地址映射到物理地址。这确保了隔离性。保护与特权级：总之就是从硬件上保证不该被访问的不被访问。RISC - V 有用户模式，监管模式和机器模式。陷阱与中断：处理程序的异常以及程序、设备和 cpu 的交互。
电脑启动时，设定 PC，从一个固定的地址（虚拟地址，通常会映射到 ROM 上，也就是 BIOS）加载一段代码，随后跳转到 Bootloader，启动操作系统。
当进程发生 Interrupt 或 Exception 时，操作系统启动 Trap 陷阱流程来修复错误尽可能让程序继续运行。但由于现代系统都是混乱并发状态运行，可能在一个时间点有大量指令同时运行，某一个中断了可能后面的指令都已经运行过了，所以需要实现 Precise Trap 假装顺序运行，保证这条指令前面的都执行过了并消除后面提早执行的指令的影响。可能需要插入空指令（bubbles），可能需要在某几个寄存器存储错误原因。
现代操作系统使用 Multiprogramming（多通道程序设计）实现单个 cpu 同时运行多个程序的假象。核心机制（context switching）上下文切换，可以理解为运行一会这个进程，然后保存现场，再为另一个进程布置现场，切换到另一个进程。由于速度极快所以看起来好像是同时运行多个程序一样。简单介绍了定时器中断，就是给一个进程定个时间，到时间了强行请出去。
虚拟内存
缓存和内存是以 block 块为交流单位，而虚拟内存是更高一级的存储结构（根据 memory hierarchy），则以 page 分页为单位，提供了可以在比主内存更大的 “内存空间” 运行程序的抽象。
如何让大量进程共享内存条：操作系统可以时间切片，上下文切换，但是我们只有一个内存，进程之间访问内存要是打架了怎么办捏。。。
建立一个内存映射表，让 A 进程访问的地址和 B 进程不是一个地址。为了保证内存的隔离，又不必改变软件层级的抽象发生的伟大谎言。顺便提一句，突然想起来了，系统内部上下文切换的时候，需要把前一个进程的寄存器进行现场保护，但这个寄存器的位置不能随便放，准确来说是一部分专属于系统的虚拟地址，而这段地址受到严密保护不会被转到硬盘去。虚拟内存使得同时执行多个任务成为可能，而且提供了隔离与保护，每个程序都以为自己访问的是一段完整连续私有的内存空间，但实际上可能分散在内存，甚至硬盘的各个角落。
虚拟地址和物理地址
在加入虚拟内存之后出现了两套地址：虚拟地址，在应用程序中直接访问的地址；物理地址，真实的内存条中对应的地址。课上讲了一个绝妙的比喻：图书馆找书，我们想的是书名，实际上书在书架的具体位置是索书号决定的。这就是虚拟地址和物理地址。但是我们不能直接把书名变成书架位置，所以需要卡片目录：页表（page table），在页表中进行查询和翻译。确定这本书实在本馆（主内存）还是分馆（硬盘）：有效位（valid bit），借阅规则：能不能借，借多长时间：访问权限位。这样一来就很清楚了。接下来就是一些常见的储存元器件，硬盘啊内存啊。作为中枢的是内存管理器 Memory Manager 负责将虚拟内存与主内存或者硬盘空间做映射。
这就得提到分页的管理模式。对于 32 位地址，一种方式是将前 20 位切分为页号 page number，类似与缓存的 index，用来表示这个地址属于哪个分页 page 管辖，后 12 位就是偏移量 offset。内存管理单元 MMU 就负责对页号做查找，找到页表 page table 中的对应物理地址，然后直接拼接 offset 就好了。注意这每个分页的 4kb 里面存的不是地址（抬杠就说指针）而是实打实数据。
缺页异常
说成是异常有点难听因为每时每刻都在发生这种异常。回顾一下是怎么加载虚拟内存的：从页表 page table 找虚拟地址，检查是不是有效，如果 valid bit 有效就美美的从内存（其实大部分是 TLB）加载过去就好了；如果不有效，那就要么在磁盘上，要么就没分配。这两种情况就是缺页异常，调用系统的例外流程进行处理。操作系统检测这块内存是不是在磁盘上。如果是的，如果有空闲内存直接从硬盘加载到内存（巨耗时），没有的话就先从主存驱逐 evict 一页，同时保存一下弃儿的数据到磁盘上（因为这部分分页还是有效信息）；如果不在硬盘，就省掉加载到内存的步骤（因为没东西可以加载），其余同上。事实上，操作系统不是根据程序声明使用多大内存就给多大内存（理论上可以申请无穷大），只有真正使用到了操作系统才会开始分页流程。
页表
储存映射关系的地方。稍加计算，每个地址 4 个字节，一共 $2^{20}$ 个分页，合计一下 4Mb 空间，放缓存里太吃力了，只能存到内存去。然而，再算算操作系统支持的最多 256 个进程，每个进程理论可以访问所有内存空间，也就是 $2^{20}$ 个分页，一共 1Gb。页表存不下捏。
可以适当增加分页大小，但这样会有潜在的内存浪费。一个程序可能只用 1kb 内存空间但却不得不分配整整一页。这就要使用分级页表 Hierarchical page tables。又是分级结构。
为了适应分级，就再拆分一遍地址。对于 32 位地址，一般分两级就足够了，把前面 20 位分成 10 + 10（巧的是 $2^{10}$ 恰好等于一个 page 的大小）这样就可以按照需求分配内存，如果没用完第一级页表分配的内存，可以只使用一部分二级页表
Exploits Sparsity of Virtual Address Space Use
这张图就很清楚。从某个寄存器中读到第一级页表的物理内存地址，用高 10 位查表，这时候查出来的是二级页表的物理地址，如果是空就说明这整块 4Mb 都没用过。随后用中间 10 位查刚刚找到的二级页表，这时候对应出来的才是 PPN（数据物理页号），拼上 offset 就是物理地址。怎么节省内存，对于没分配的空间，直接在一级页表置空就好了，省下来二级页表的空间。而且正常使用只会用到寥寥几张小表，节约大量空间。
不过话虽如此，分两次查表得慢死。但我们有缓存。太好了是缓存我们有救了。
TLB (旁路转换缓冲 / 快表)
（至于为什么是缓冲：因为先发明的 TLB 后发明的缓存）小规模的情形下是一个全映射缓存，速度极快。VPN（虚拟分页号）就是要查阅的对象，所以直接拿来当 tag，对应出来的数据就是 PPN。TLB 在电路里插到 cpu 和一级缓存之间。很容易理解，cpu 用的是虚拟地址，只有换成物理地址喂给缓存才好处理。
能大致看出对地址的处理流程。指令内存和数据内存都有一块 TLB，TLB 找不到路就交给硬件页表遍历器处理找页的流程。最后可能触发缺页异常和地址保护，也有可能最后在内存里找到了就更新一下 TLB。举例来说，从 PC 发出的虚拟地址喂给 INS TLB 查表，后从缓存中拿到相对应的指令，诸如 lw，sw 里虚拟地址经过偏移量计算后交给 DATA TLB，走一遍给出一个物理地址进行操作。
在进程切换的时候，由于映射关系要发生变化，所以在上下文切换中的一种方案是冲刷一下 TLB（当然比较慢但可以接受），同时保存一下寄存器和 PC 的值，改一下基址寄存器，就是找一级页表的寄存器。
终于写完了。感觉 cs61c 讲的比较浅，自己理解也不算透彻。还是得放张图奖励自己。
