继续来学习内存管理之虚拟内存管理
- 传统存储管理方式
同时将多个进程保存在内存中以便允许多道程序设计。
- 一次性
作业必须一次性全部装入内存，才能开始运行 - 驻留性
作业装入内存后，一直驻留在内存中，其任何部分都不会被换出，直到作业运行结束。
- 局部性原理
快表，页高速缓存以及虚拟内存技术，都属于高速缓存技术，依赖的原理就是局部性原理，既适用于程序结构，也适用于数据结构。
- 时间局部性
程序中某一条指令被执行，不久之后该指令可能再次执行。因为程序中存在大量的循环操作。 - 空间局部性
程序一段时间访问的地址，可能集中在一定的范围之内，因为指令通常是顺序存放，顺序执行的，数据也一般是以向量，数组，表等形式存储的。
时间局部性是将最近使用的指令和数据保存到高速缓存存储器中，并且使用高速缓存的层次结构实现。
空间局部性是使用较大的高速缓存，将预取机制集成到高速缓存控制逻辑中实现。
虚拟内存技术是建立了内存－外存的两级存储器的结构，利用局部性原理实现高速缓存。
- 虚拟存储器
程序装入的时候，可以将程序的一部分装入内存，将其余部分留在外存，需要的时候再调用，暂时不需要用的内容可以换出到外存。
虚拟存储器的大小由计算机的地址结构决定。
- 多次性
无需作业运行的时候一次性全部装入内存，而是允许被分成多次调入内存。 - 对换性
无需作业运行时候一直常驻内存，允许作业运行过程中，换入和换出。 - 虚拟性
从逻辑上扩充内存的容量。
- 虚拟内存技术的实现
需要建立在离散分配的内存管理方式的基础上。
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
需要的硬件支持
- 一定容量的内存与外存
- 页表机制，作为主要的数据结构
- 中断机构，如果缺页，则产生中断
- 地址变换结构，逻辑地址到物理地址的变换
请求分页管理方式
在基本的分页系统基础上，增加了请求调页功能和页面置换功能，是最常用的实现虚拟存储器的方法。
- 页表机制
请求分页系统在作业运行之前不需要全部一次性调入内存，因此会出现访问的页面不在内存中，所以需要发现和处理这种情况，在请求页表项中增加了四个字段。页面是将程序分成的块。
- 状态位P
指示该页是否已经调入内存 - 访问字段A
用于记录本页在一段时间内被访问的次数，或者本页多久未被访问 - 修改位M
指示该页在调入内存后是否被修改过 - 外存地址
- 缺页中断机制
如果要访问的页面不存在，那么产生一个缺页中断，请求操作系统将所缺的页面调入内存，此时将缺页的进程阻塞，调页完成唤醒，如果内存中有空闲块，则分配一个块(分配页框，分配内存)，将调入的页装入该块，页面和主存中的块是一一对应的，然后修改页表中的页表项，如果此时内存中没有空闲块，则淘汰某页(如果淘汰的页在内存期间被修改过，则要将其写回外存)
- 缺页中断
在指令执行期间产生和处理中断信号，属于内部中断。
可能产生多次缺页中断。
- 地址变换机构
- 首先检索快表
- 找到要访问的页，便修改页表项中的访问位，写指令要重置修改位，利用页表项给出的物理块号和页内地址形成物理地址。
- 如果没有找到页表项，那么去内存中查找，对比页表项中的状态位P，看该页是否调入内存，否在产生缺页中断，请求从外存把该页调入内存。
页面置换算法
选择调出页面的算法称为页面置换算法，好的页面置换算法应该有较低的页面更换频率。
- 最佳置换算法(OPT)
不可能实现的算法。它选择的被淘汰的页面是以后永远不使用的，或者是在最长时间内不再访问的页面，来保证最低的缺页率。 - 先进先出FIFO页面置换算法
优先淘汰最早进入内存的页面，也是内存中驻留时间最长的页面。
FIFO算法会产生当所分配的物理块数增大而页面故障数不减反增的异常，Belady异常。 - 最近最久未使用(LRU)置换算法
选择最近最长时间未访问过的页面进行淘汰，在过去一段时间未访问的页面，最近的将来也可能不会访问。需要对页面的最近访问时间进行排序，因此耗费系统资源比较大。
LRU性能比较好，但是需要寄存器和栈的硬件支持。是堆栈类算法，不可能出现Belady异常。 - 时钟(CLOCK)算法
算法要循环扫描缓冲区，给每一帧关联一个附加位，使用位。某一页首次装入内存的时候，使用位置为1，该页随后再被访问到，使用位也置为1。某一页被替换的时候，指针指向缓冲区的下一帧，需要被替换的时候，扫描缓冲区使用位为0的帧，每当遇到一个使用位为1的帧，将位重新置为0。如果开始时候都为0，就用第一个帧替换。如果都为1，则将所有置为0后，停留在最初的位置上，替换该帧的页。
页面置换算法都有一个原则就是尽可能的保留曾经使用过的页面，淘汰没有使用的页面，这样可以在总体上减少换页次数。
页面分配策略
- 驻留集大小
操作系统需要决定在准备执行的时候读取多少页，给特定的进程分配多大的主存空间
- 固定分配局部置换
为每一个进程分配一定数目的物理块，整个运行期间都不改变，缺页的话，从该进程在内存中选出一页换出，然后再调入需要的页面。缺点是难以为每个进程分配的物理块数目。 - 可变分配全局置换
为系统的每个进程分配一定数目的物理块，操作系统自身保持一个空闲物理块队列。缺页的时候，从队列中取出一个物理块分配给该进程，将要调入的页面装入其中。缺点是盲目给进程增加物理块，使得系统的多道程序并发能力下降。 - 可变分配局部置换
为每个进程分配一定数目的物理块，缺页的时候，只允许进程在内存的页面选出一页换出，这样不会影响其他进程的运行。如果频繁缺页，则分配物理块，如果缺页率比较低，则减少进程的物理块。
- 调入页面的时机
- 预调页策略
采用以预测为基础的预调页策略，将预计在不久之后便会访问的页面预先调入内存，这种方法主要用于进程的首次调入时，由程序猿来指出应该先调入哪些页。 - 请求调页策略
预调入时运行前的调入，请求调页时运行期间的调入。
- 从何处调入页面
请求分页系统的外存分为两部分，用于存放文件的文件区和用于存放对换页面的对换区。
对换区通常采用连续分配方式，文件区采用离散分配方式，所以对换区磁盘I/O速度比文件区更快。
- 系统拥有足够的对换区空间
- 缺少足够的对换区空间，不会修改的文件直接从文件区调入。
- Unix方式，未运行过的页面都在文件区，运行过的都在对换区
抖动
频繁的页面调度行为。如果一个进程在换页上的时间多于执行时间，那么这个进程就在颠簸。
频繁的发生缺页中断，抖动，主要原因是某个进程频繁访问的页面数目高于可用的物理块数目。工作集
指某段时间间隔内，进程要访问的页面集合，经常被使用的页面需要在工作集中，长期不被使用的页面要从工作集中丢弃，防止系统出现抖动，需要选择合适的工作集大小。
重点概念
- 虚拟存储器的容量不受外存容量限制，也不受内存容量限制，而是由CPU寻址范围决定的，最大容量由计算机的地址结构决定的。
- 缺页中断是由访存指令引起的，调入要访问的页后，访存指令应该重新执行。
- 缺页中断调入新的页面，要修改页表项和分配页框(分配内存，对应主存的物理块)，若内存中没有页面需要从外存读入。
- 程序局部性越好，虚拟存储系统越能更好的发挥其作用。
- LRU算法需要最近一次访问时间进行记录，查找时间最久的进行替换，所以需要进行按时间排序。
- 页表项中合法位信息显示本页面是否在内存中，从而决定了是否会发生页面故障。
- 抖动是频繁的页面调度行为。
- 将一些页面或者段从内存中调入调出，而调入调出的基本手段是覆盖与交换。
- 请求分页存储管理主要是为了解决内存容量不足，基于局部性原理以时间换取空间。
- 只有FIFO算法会导致Belady异常。
