目录：目录会放在这一楼的评论区

2.2 操作系统的中断、异常和系统调用（用于跨越操作系统、应用程序、外设三者之间的边界）
一、中断
1.硬件层面：中断控制器接收到中断源，就产生一个中断标记（可能与中断向量表有关）发给CPU判断。
CPU识别出来是什么类型的中断，然后又产生出具体的中断ID，交给操作系统处理。
2.软件层面：操作系统保存程序的当前状态，根据中断ID得到中断地址，完成中断服务程序处理，之后清除中断标记，恢复程序状态。
二、异常
其他的和中断差不多，它们都需要先保存现场，处理完后恢复现场（而且都对应用程序透明，应用程序不会知道自己发生了中断或异常）。
但处理方式不同：中断执行完一次对应服务就ok，但异常要么需要杀死产生异常的程序，要么需要重新执行异常指令（可能是资源分配不够，于是分配够了之后再来一次）
三、系统调用
应用程序不能直接调用服务，服务必须由操作系统来执行。
于是需要接口：系统调用接口（和API不一样，而且两者没有严格对应关系，最简单的记法就是：系统调用几乎必定涉及内核服务，而API可能只是一些普通的函数）
所以最终：应用程序→系统调用接口→操作系统获取接口参数（并检查参数确保安全）→完成并返回结果
四、API
API就像是更高级的封装，
只要按照同样的接口标准来写应用程序，就可以跨平台执行。
1.Win32 API用于Windows
2.POSIX API用于UNIX, LINUX, MAC OS X等等
3.Java API用于JAVA虚拟机(JVM)，比较特殊，运行在win环境就用类似win32的API，而跑在linux又会用POSIX。
五、用户态和内核态
指在应用程序运行的时候，CPU当前所处的状态，区别在于特权级别（特权指令、访问IO指令）。
而且两个状态拥有各自的堆栈（切换需要开销，开销可能大于一个函数的执行），在内核态完成后，需要把结果从内核空间copy到用户空间（又有开销）。

3.1 计算机体系结构 & 内存分层体系
一、计算机体系结构：
1.总线上有：CPU、内存、外设。
2.CPU包含：控制器、运算器、寄存器、缓存(Cache)、存储管理单元(MMU)。
3.内存：用于存放正在执行的程序的代码和正在处理的数据。
4.设备（I/O）：磁盘、鼠标、键盘等等。
二、在这里面，操作系统完成的工作：抽象、保护、共享、虚拟化（都是对应用程序透明的）
1.抽象：不用考虑物理地址和外设，只考虑逻辑地址空间。
2.保护：独立地址空间（隔离）
3.共享：访问相同内存（进程通信）
4.虚拟化：把最需要放进内存的数据放进内存，暂时不用的可以放到硬盘
三、所以操作系统有管理内存的方法：
1.首先是硬件：知道内存架构，有MMU处理CPU的内存访问请求。
2.方法：程序重定位、分段、分页、虚拟内存、按需分页虚拟内存。

3.2 地址空间 & 地址生成（都包括逻辑和物理地址）
一、地址空间：
1.物理地址空间：硬件支持管理和控制
2.逻辑地址空间：一个运行的程序所拥有的内存范围（对于程序来说是个一维线性的）
3.逻辑地址空间一定会映射在物理地址空间上（可能是内存也可能是磁盘）
二、地址生成
.c文件 → 编译 → .s文件 → 汇编（把变量和函数的符号名转换成逻辑地址） → .o文件 → 链接（需要linker完成） → 可执行文件 → 载入（需要loader完成，程序重定位） → 程序在内存中运行。

但一定要注意，到最后程序在内存中运行，也还是逻辑地址，不是物理地址。
三、映射
CPU要执行指令的时候，只知道指令的逻辑地址，需要发出请求，由MMU帮助CPU查找逻辑地址对应的物理地址
四、memory map
一个基址寄存器，一个界限寄存器，规定了这个程序的起始地址和地址长度，如果超出规定范围，就会产生内存访问异常。

3.3 & 3.4 连续内存分配：内存碎片 & 分区的动态分配 & 压缩式碎片管理 & 交换式碎片管理
一、内存碎片
1.外部碎片：分配单元之间的未使用内存。
2.内部碎片：分配单元之内的未使用内存。
二、简单的内存分配算法：
1.首次适配first fit：需求为n，直接从0开始，找到第一个不小于n的空闲内存块（回收的时候会合并，但终究还是外碎片问题严重，又多又不确定）。
2.最优识别best fit：需求为n，遍历，找到不小于n的，与n差值最小的一块（外部碎片会变小，但会产生很多微小外部碎片）
3.最差匹配：worst fit：与最优相反，偏偏找最大的一块（适用于多用需要大块内存的程序的场景，但问题也在于优先拆大块，可能导致大块程序难运行）
三、解决上面三种简单算法带来的碎片问题：
1.紧致算法（压缩式碎片整理）：把内存中的程序位置用copy挪动（问题在于安全性和开销）。
2.换入换出（交换式碎片整理）：把内存中正处于等待状态的程序暂时放到硬盘。

4.1 & 4.2 非连续内存分配
两种硬件方案：分段 & 分页
一、分段
1.分段：把连续的逻辑地址空间，分段映射到不连续的物理地址空间（库、用户代码段、程序数据、堆、运行栈）。
2.段表：段表包含段号、段基址、段长（由操作系统建立段表）。
3.于是寻址变成了：把逻辑地址分两段，一段是段号，一段是偏移地址，再配合基址寄存器和界限寄存器找到物理地址。
二、分页
1.分页：把逻辑地址空间和物理地址空间都划分成同样固定大小的页和帧，然后建立机制用MMU实现page→frame。
$$$：frame是物理页，page是逻辑页。
2.帧(Frame)：把一个内存中存储的物理地址分为高位低位两段，高F位代表帧号，低S位代表偏移量，二者恰好互补（F增加一位，页帧大小变为一一半，偏移量也就只需要原来一半）。


3.页(Page)：和帧相似，一个地址分为P和S，P和F不一定一样大，页内偏移和帧内偏移一定是一样大（意思就是页号数和帧号数总量可能不一样，但每一页和每一帧的大小肯定一样，就像下面这个图）

4.页寻址机制：程序将页号与偏移量提交给cpu，cpu通过页号找到页表项，该页表项存储了对应的帧号，cpu此时就得到了帧号、偏移量，通过2S次方*f+o，得到物理地址。
5.与分段的区别：段的长度不固定，而页的偏移量大小固定。
6.另外，逻辑地址空间要大于物理地址空间，这样的结果是：
页是连续的虚拟内存；
帧是非连续的物理内存；（比如一个逻辑地址空间里连续的两页，对应物理内存空间的两个分开的帧）
不是所有的页都有对应的帧。（页比帧多，所以需要虚拟内存）

4.3 & 4.4 & 4.5 页表 & 多级页表 & 反向页表
一、页表的结构
页表包含两部分：高位Flags，低位frame number。
1.CPU通过page number找到页表项，进一步得到frame number，然后计算得到物理地址。
2.此外还有标志位Flags，比如驻留位resident bit（该逻辑地址空间有对应的物理地址空间，则1，否则0）
举例：
(3,1023)，就会先到页表中找到第0项开始的第三项，发现第三项的Flags值为XXX，Frame num值为YYY，YYY就是页帧号，1023就是偏移量，YYY+1023结合就是物理地址。
XXX中有一位是resident bit，如果为0，会产生内存访问异常。
二、页表的性能问题
1.页表也放在内存里，导致每次访问一个内存单元都要访问两次内存（一次先找页表项，一次找数据）。
2.页表可能会很大（目前没有讲多级页表）。
3.多个应用程序，都分别占用独立的页表，空间开销大。
三、解决方法
1.用缓存cache，把常访问的部分放进缓存。
2.间接访问：多级页表
四、具体解决方法
1.时间：
MMU中有一个TLB(Translation Look-aside Buffer)，是CPU内部的一块特殊区域，是一个cache。
TLB包含两项：key和value，key是p，value是f
CPU首先拿着p到TLB中查找，如果存在，就能快速得到f，再加上offset就可以得到物理地址。
如果TLB miss，就回去查页表，如果resident bit为1，就把f取回来，放到TLB中（不常用的丢掉），这一步更新TLB的操作如果是x86的CPU，就由硬件完成，但有的CPU更新TLB需要由自己动手。
2.空间：
二级页表。
一句话：一级页表存储二级页表的起始地址。（级数越多耗时越多，但是TLB可以缓解）


五、反向页表
1.背景：
传统的多级页表受制于逻辑地址空间和物理地址空间的大小关系，而反向页表只与物理地址空间大小有关。
而且传统多级页表，n个进程就需要n个play table，大概意思是每个进程都会申请属于自己的独立页表，会造成空间浪费，而反向的映射就不会遇到这个问题，而且虚拟内存的大小可以是任意的。
2.反向页表的概念：
注意：虽然说是反向页表，但最终目的还是通过逻辑地址找物理地址！
把物理地址空间分为4000个frame，那么就得到一个4000行的反向页表，用哈希计算，将页号（VPN）和当前进程的PID作为输入，通过哈希函数计算得到一个页帧号，即反向页表的索引，也就是物理地址的索引（然后还需要处理哈希碰撞）。
3.特点：
难点在于索引的查找过程，哈希计算用纯软件实现就太慢，所以必定需要硬件加速，所以贵，采用反向页表的操作系统包括64位的UltraSPARC和PowerPC（一听就很高端）。
反向页表也会有一个类似TLB的机制来缓存。

5.1 & 5.2 & 5.3 虚拟内存 & 覆盖技术 & 交换技术
一、历史背景
直接买cache，买内存贵，而硬盘便宜。常用数据放内存，不常用放硬盘。
怎么放？虚拟内存出现之前，最初的低级方法：手动覆盖(overlay)，以及稍微发展后的，自动交换(swapping)。
1.程序太大时，手动覆盖，只把需要的指令和数据放内存中。
2.程序太多时，自动交换，把暂时不能执行的程序放外存（硬盘）中。
（交换开销较大，因为要全部复制移走。）
3.后面有了硬件分段分页支持，于是使用虚拟内存，可以以更小的粒度为单位，装入更多更大的程序。
--------------------------------------------------
二、覆盖技术（就是让不相关的模块互相覆盖，也就是分时共享）
1.原理：
让程序中不会同时执行的模块共享一块内存区域，按时间先后执行。
分为必要部分和可选部分。（占用的内存也就分为常驻区和若干个覆盖区）
必要部分是常驻内存的代码和数据，它决定在什么时候把相应的函数和数据导入和导出内存。
可选部分平时放外存，使用时放内存。
（没有互相调用关系的函数和数据就可以放进同一个覆盖区）

2.缺点：
换入换出的操作费时间，而且需要程序员手动设计，提升编程复杂度。
（当时世界最流行的微软dos系统出现了一个提供覆盖支持的软件，Turbo Pascl，帮助自动完成覆盖操作）
--------------------------------------------------
三、交换技术
1.原理：
把暂时不能运行的进程送到外存(swap out)，把外存中的某个进程的地址空间读入到内存(swap in)。
（但粒度很大，一次就必定是交换整个进程，可能包含几百页）
2.考虑的问题：
什么时候交换？→→ 只当内存空间不够或有不够的危险时换出。
交换区的大小？→→ 必须大到足够存放所有用户进程的所有内存映像的copy
换入时的重定位？ →→ 动态地址映射（交给制作页表的操作系统了）
--------------------------------------------------
四、覆盖和交换的区别
覆盖只发生在程序的模块之间，由程序员手动设计。
交换发生在内存中的程序之间，操作系统自动完成。

5.4 虚存技术
兼顾覆盖和交换的优点，只对进程的部分内容（指页，而不是指线程）进行交换。
一、基本概念
1.程序的局部性原理（时间和空间都要）
指程序在执行过程中的一个较短时期，所执行的指令地址，和指令的操作数地址，都局限于一定的区域。
局部性越好的程序，就越适合虚拟内存技术。
2.特征
大的用户空间（硬盘大，虚存就大）
部分交换（相比于交换技术，粒度小得多）
不连续性（物理内存分配不连续，虚拟地址空间使用也不连续）
--------------------------------------------------
二、具体实现
在页式内存管理的基础上，增加请求调页和页面置换功能。
1.请求调页：程序运行只需要装入部分页就可以，在需要某些外存数据时，请求调页。
2.页面置换：内存不够时，把不需要的页换出去。
--------------------------------------------------
三、页表表项
首先，浅蓝色的部分只是逻辑页号page number，应该是放在上一级页表里或者由CPU或MMU直接比对。
这个图应该分为两部分，也就是page number，和右边的页表项内容，Flag + frame number。（参考4.3节）

标志位：
驻留位：表示是否有效（有没有对应的物理地址空间）。
保护位：可以进行什么类型访问。
修改位（脏位）：如果修改过，就是脏页。如果没修改过，换出时就可以直接释放，因为硬盘中的那份还在，而且完全一样。
访问位：表示是否被经常访问，如果否，那么页面置换就换它出去。
--------------------------------------------------
四、缺页异常的处理过程
1.检查内存中是否有空闲的物理页，有则直接分配一个物理页帧f并且跳到4，没有则跳到2，多出2和3步。
4.把需要访问的页p装入到物理页面f中。
5.修改p对应的页表项内容，驻留位置为1，页帧号page num置为f。
6.重新运行被中断的指令。
--------
以下是多出的2，3步骤：
2.用页面置换算法，把其中一页q替换出去，也就是copy到硬盘并清空（如果不是脏页也就不用copy了）
（所以置换也只是置换逻辑页，而实际上的实现却是仍在在持有原本的物理页，改变的只是映射关系）
3.修改被换出去的页q对应的页表项，把驻留位设为0。
--------------------------------------------------
五、后备存储（二级存储） Backing Store（一共四类）
有些数据、指令、动态链接库都会放在硬盘，用到它们的时候才从硬盘读入。
另外，硬盘还会专门有一个分区，换入换出分区(swap)，用于存放程序运行时动态生成的一些数据（不属于前面的数据、指令、动态链接库）
--------------------------------------------------
六、有效存储器访问时间 effective memory access time(EAT)

主要取决于p，而p则取决于程序的局部性。

6.1 & 6.2 & 6.3 & 6.4 & 6.5 & 6.6 页面置换算法
一、页面置换算法
目标：尽量减少页面换入换出次数
也不是所有页面都需要换入换出，比如用lock bit标志位来记录常驻内存的进程
1.最优页面置换算法 OPT(optimal)
置换的页面是将来最长时间不需要的页面（所以无法实现，只是一种模拟预知未来情况下的概念）。
--------
2.先进先出算法 FIFO(First-In First-Out)
选择在内存中驻留时间最长的页面淘汰。
实现简单，性能差，因为驻留时间最长的很可能就是经常要访问的页面。
而且有Belady现象：分配的物理页变多，反而缺页更严重。
--------
3.最近最久未使用算法 LRU(Least Recently Used)
选择最久未使用的页面淘汰
两种实现方法：
1).OS维护一个页面链表，每次访问，就把访问的页放到链表头，每次缺页时淘汰链表尾的页。
2).维护一个页面栈，每次访问就把页号压入栈顶（如果本来栈里就有该页号，那就把这个页号移动到栈顶），每次缺页时淘汰栈底的页（其实感觉有问题，因为栈不能取中间元素，最好的方法应该时双向链表+哈希表）
--------
4.时钟页面置换算法 Clock（只有缺页才会动指针）
是LRU的近似，FIFO的改进（LRU维护容器的开销大，找一种方法近似）
把页面组织成环形链表，关键在于一个标志位access bit。
访问时：把访问到的页的access bit置为1。
缺页发生时：指针在环形链表中依次查找access为0的页面节点，如果找到为1，就把它变成0，如果找到0就换出。（这样找到的不一定最老，但一定是老了一圈的）
--------
5.二次机会法（Enhanced Clock）（考虑到优先保留脏页，让只读的页更容易换出去）
访问时：访问到的页used bit（也就是Clock算法中的access bit）置为1，如果是写访问，就把dirty bit也置1。
缺页发生时：在Clock的基础上，增加对dirty bit的判断（脏位也就是写位），如果两个位都是0就踢出了。
如果有一个位是1，另一位是0，那么两个都改为0。
如果两位都是1，那么把used bit置0，而dirty bit不变（仍为1）

--------
6.最不常用法 LFU(Least Frequently Used)
给每个页面配一个计数器，每次访问+1，发生缺页时淘汰计数最小的。
显然不够好，稍稍改进一点，可以过一段时间让所有计数器的值右移一位。

6.7 页面置换算法 小结
一、Belady现象
在用FIFO时，有时会出现分配的物理页帧数增加，缺页率反而提高的情况。
因为它的设计初衷恰好与程序的局部性有矛盾，可能程序恰好在一次错位之后陷入一个循环，恰好导致循环缺页，并一直缺页。（但也只是偶然发生，只不过相比之下，LRU等算法，物理页帧数增加，缺页率必不增加）
--------------------------------------------------
二、LRU、FIFO、Clock的比较
如果程序没有局部性这一特点，三者缺页率可能基本一样。
FIFO开销最小，LRU更契合程序的局部性，而Clock利用了硬件控制的bit，减少开销，用标志bit近似模拟LRU的最久未使用时间，算是折中的办法。

6.8 & 6.9 & 6.10 全局页面置换算法
一、局部页替换算法的问题、工作集模型
1.工作集 working set
一个进程当前正在使用的逻辑页面集合，用二元函数W(t, Δ)表示

工作集经常从一个比较稳的状态，经过波动跳变到另一个比较稳的状态（这也就是局部页替换算法的问题，因为程序所需要的页帧大小是变化的，所以要灵活给多个程序分配）。
2.常驻集
在当前时刻，进程实际驻留在内存中的页面集（可以简单理解为就是这个进程当前拿到的页帧数）
尽量让工作集都在常驻集里面，这样程序运行可以很流畅。
--------------------------------------------------
二、两个全局置换算法
1.工作集页置换算法
页帧数满了之后，应该换出哪一个，不知道（应该就是用LRU之类的局部页面替换算法）。
重点在于，即使页帧数还没占满，也会在工作集窗口之外，也就是固定访问次数后被换出。（比如设定τ = 4，那么t = -2开始的页会在t = 2时被换出）
对于单个进程来说，缺页增加，但对整个系统来说，缺页减少。
--------
2.缺页率页面置换算法
缺页率高，就多给它分配常驻集，反之减少。
缺页率的定义当然是：缺页次数 / 访问次数。
但换一种角度想，它也可以是：1 / 两次缺页的时间间隔。
所以得到了具体实现的办法
具体实现需要设定一个T，用两次缺页的时间间隔和T相比较。
如果时间差大于T，那么这两次缺页之间这段时间，所有没被访问到的页面都会从常驻集中被移除。
如果时间小于等于T，那么仅添加缺失页到常驻集。
（可能有争议，PPT和讲义写的是改变工作集，但我这里认为是改变常驻集）
--------------------------------------------------
三、抖动问题
如果常驻集不能包含工作集，那么进程就会频繁缺页，运行速度慢，称为“抖动”。
--------
解决方法：负载控制
随着进程数量增加，CPU利用率会先升后降。
根据两次缺页的平均时间间隔，和完成一次缺页异常处理的服务时间，找到它们相等的点。
（横轴是进程数量，也就是说，恰好在缺页发生和处理时间对等的情况下，维持尽量多数量的进程的点）