操作系统——内存管理（2）
虚拟内存技术
- 背景：不采用虚拟内存技术的内存管理策略的缺点：
- 一次性。必须将作业一次性装入内存中，可能会不能全部装入从而作业无法运行；或者大量作业要求运行时，内存不能容纳导致仅少量作业在运行；
- 驻留性。作业进入内存后会驻留在内存中，任何部分都不会被调出，直到作业结束。
- 局部性原理。原理不解释。采用此原理的技术有快表、页高速缓存、虚拟内存技术以及“goto语句有害”说法等。
- 时间局部性：刚执行的指令，不久之后很有可能再次执行。
- 空间局部性：一旦访问了某个存储单元，不久之后附近的存储单元很有可能被访问。
- 虚拟存储器：OS提供的，在用户看来是一个很大的存储器（比实际内存大得多的，事实上并不存在）。虚拟存储器的特征：多次性（并非一次性，多次调入内存中运行）、对换性（无需常驻，运行时可换入换出）、虚拟性（逻辑上的超大内存）。流程：
- 基于局部性原理，程序装入时，可以将程序一部分装入内存开始执行，而将其余部分留在外存。
- 在执行过程中如果所访问的信息不在内存中时，由OS将所需要的部分调入内存，然后继续执行程序。
- 另一方面，OS将内存中暂时不适用的内容换到外存上，从而腾出空间。
- 虚拟存储器必须建立在离散分配（即非连续）的内存管理方式的基础上。可以采用：请求分页式、请求分段式、请求段页式。硬件前提：一定容量的外存和内存、页表/段表机制、中断机构、地址变换机构。
请求分页
- 在基本分页技术的基础上，增加了虚拟存储器功能。只需要将一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过调页功能将其调入，同时通过置换功能将暂时不同的页面换出。
- 页表项：
| 页号 | 物理块号 | 状态位P | 访问字段A | 修改位M | 外存地址 |
|---|---|---|---|---|---|
| 标记是否已经调入内存 | 记录本页在某一个时间段内被访问的次数 | 标记调入后是否被修改 | 在外存上的地址/物理块号 |
- 缺页中断机制
- 使用请求分页技术，每次访问页面不在内存中，就会产生一个缺页中断。把缺页的进程阻塞，等待分配内存块或者置换某淘汰页。
- 与一般的中断的区别：在指令执行期间产生和处理中断信号，属于内部中断，而非一条指令执行完后产生；
- 一条指令在执行期间，可能产生多次缺页中断。
页面置换算法（挑选哪些不常用的页并换掉它）
- 最佳置换算法（OPT）
- 机制：未来不使用或很少使用的页，换掉它；
- 评价：无法预知所以无法实现。
- 先进先出（FIFO）页面置换算法
- 机制：淘汰进来最久的页；
- 评价：跟进程规律不相符，进程常常访问有些页面；而且会出现Belady异常（增加分配的物理块数，但页故障数不减反增；页故障数可以当作置换次数来理解）。
- 最近最久未使用（LRU）置换算法
- 机制：从历史数据上，发现那些很长一段时间未被访问的页，换掉它；
- 性能较好，需要寄存器和栈的支持。
- 时钟（CLOCK）置换算法
- 机制：
- 页第一次装入，使用位设1；随后被访问，使用位也设1。
- 有一个候选循环队列（挑中了会被淘汰），指针开始扫描，发现使用位为1的，跳过它的同时将其使用位设0；发现使用位是0的，选中它，置换，指针指向下一个。
- 机制：
- 时钟改良算法
- 机制跟上面的clock算法一样，都是尽可能保留曾经使用过的页面，淘汰未使用的页面。但改良算法增加一个修改位。如果全部页面都使用过，优先淘汰那些未修改过的页面。
- 机制：
- 每一个页都有两个位参选（使用位u：0/1；修改位m：0/1）；
- ① 有一个候选循环队列（挑中了会被淘汰），指针开始第一次扫描，查找u=0且m=0的，选中它，置换，指针指向下一个。如果一圈后没有找到，进入下一步；
- ② 进行第二次扫描，查找u=0且m=1的，如果不是，则跳过它的同时，将其u置为0，指针指向下一个。如果找到了，选中它，置换，指针指向下一个；
- 如果②没有找到，此时所有页的u应该都是0了，那么重复步骤 ①，如果有必要再重复步骤 ②，如此可以找到合适的页。
页面分配策略
驻留集大小
- 驻留集即给某一进程分配的主存空间。多了影响进程数 ，少了增加页错误率 。
- 三种策略:
- 固定分配局部置换：每个进程分配一定数量物理块，运行期间不改变。
- 可变分配全局置换:每个进程分配一定数量物理块，OS也预留一部分。运行时如果需要，OS再为进程动态增加一些物理块。弊端：可能会盲目增加（类似央妈无脑放水救市）
- 可变分配局部置换：每个进程分配一定数量物理块，缺页时只能换一页。如果换页频繁，OS再分配物理块；如果换页次数少，可适当减少进程的物理块。
调入页面的时机
- 预调页策略：一次调入若干个相邻的页，成功率约50%
- 请求调页策略：缺多少调多少
何处调入页面
- 页面来源有两种：文件区（存放文件）和对换区（存放对换页面）
- 对换区采用连续分配的方式，I/O速度快；文件区是离散分配的方式，I/O慢。
- 如果对换区空间够大，可以把进程相关文件放入对换区（进程执行前），在需要对换时，内存直接和对换区交互；
- 如果对换区空间不够大，读文件还是从文件区里置换。写文件比较慢，通过对换区中转。
- [扩展]对换区可以理解为文件系统的缓存。就是一个页在内存中的，那么肯定有一份拷贝在外存里，而内存中的页被改写了之后，出现了内存外存不一致的情况.
- 本来的方法是里面把改写后的内存拷贝写到外存去，但是这样浪费了时间，所以这儿的方法是先不写回去，而是写到内存的另一个区域（这儿把它叫做对换区），等到下次还需要这个页的时候就再调回来，等到这个页要被淘汰的时候才写回到外存，这样就节省下来了一些写外存的时间。
- Unix方式：进程相关文件放在文件区，曾经运行过的放在对换区。
抖动
- 频繁发生缺页中断导致页面被频繁换入换出。
- 根源；某个进程频繁访问的页面数量高于可用的物理页帧数量。因此需要合理地使用虚拟内存技术。