所谓虚拟存储技术，就是在内存中保留一部分程序或数据，在外存中防止整个地址空间的副本。程序运行过程中可以随机访问内存中的数据或程序，但需要的程序或数据不在内存时，就将内存中部分内容根据情况写回外存，然后从外存调入所需的程序或数据，实现作业内部的局部转换，从而允许程序的地址空间大于时间分配的存储区域。它在内存和外存之间建立了层次关系，使得程序能够像访问内存一样访问外存，主要用于解决内存的容量问题。其逻辑容量由内存和外存容量之和以及CPU可寻址范围决定，其运行速度接近于内存速度，成本也不高。
1. 地址变换
由进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器，允许用户使用比内存容量大的多的地址空间来编程。用户编程所用的地址被称为逻辑地址（虚地址），实际的内存地址被称为物理地址（实地址）。每次访问内存时都要进行逻辑地址到物理地址的转换，由硬件完成这种转换，而内存和外存间的信息动态调度是硬件和操作系统两者配合完成：
- 静态重定位：静态重定位是在许空间程序执行之前有装配程序完成地址映射工作。
- 优点是不需要硬件的支持
- 缺点是无法实现虚拟存储器，必须占用连续的内存空间，且难以做到程序和数据的共享
- 动态重定位：动态重定位是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换为内存地址，依靠硬件地址变换机构完成
- 优点是可以对内存进行非连续分配，提供了虚拟存储器的基础，有利于程序段的共享
2. 存储组织
虚拟存储器有以下7种：
- 单一连续分区：把所有用户区都分配给唯一的用户作业，当作业被调度时，进程全部进入内存，一旦完成，所有内存恢复空闲，不支持多道程序设计
- 固定分区：支持多道程序设计的最简单的存储管理方法，它把内存划分为若干个固定的、大小不同的分区，每个分区能够装入一个作业，分区的大小是固定的，算法简单，但是容易生产较多的存储碎片
- 可变分区：引入可变分区后，虽然内存分配更灵活，也提高了内存利用率，但由于系统在不断地分配和回收中，必须会出现一些不连续的小的空闲区，尽管这些小的空闲区的总和超过某一个作业要求的空间，但由于不连续而无法分配，产生了碎片。解决碎片的方法是拼接（紧凑），即向一个方向（如向低地址端）移动已分配的作业，是那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面是要求能够对作业进行重新定位，另一方面系统在拼接时要多耗费较多的时间
- 可重定位分区：这是克服固定分区碎片问题的一种存储分配方法，它能够把相邻的空闲存储空间合并成一个完整的空区，还能够整理存储器内各个作业的存储位置，以达到消除存储碎片和紧缩存储空间的目的。紧缩工作需要花费大量的时间和系统资源
- 页式：页式存储组织的基本原理就是将各个进程的虚拟空间划分为若干个长度相等的页，把内存空间与页相等的大小划分为大小相等的片或页面，采用请求调页或预调页技术实现内外存的统一管理
- 优点是利用率高，产生的内存碎片小，内存空间分配及管理简单
- 缺点是要有响应的硬件支持，增加了系统开销；请求调页的算法如果选择不当，有可能产生抖动现象
- 段式：一个作业是由若干个具有逻辑意义的段（主程序、子程序、数据段等）组成。段式存储管理中，允许程序（作业）占据内存中若干分离的分区。分区系统中的虚地址是一个有序对（段号，段内位移）。系统为每一个作业建立一个段表，其内容包括段号与内存起始地址的对应关系、段长和状态等。
状态指出这个段是否已调入内存，若已调入内存，则指出这个段的起始地址位置，状态同时也支持这个段的访问权限。如果这段尚未调入内存，则产生缺段中断，以便装入所需要的段
- 优点是便于多道程序共享内存、便于对存储器的保护，各段程序修改互不影响
- 缺点是内存利用率低，内存碎片浪费大
- 段页式：结合分段式和分页式的存储管理方法，充分利用分段管理和分页管理的优点。作业按逻辑结构分段，段内分页，内存分块。作业只需要将部分页装入即可运行，所以支持虚拟存储，可实现动态连接和装配
以下是常见3中虚存组织及其优缺点：
| 项目 | 段式管理 | 页式管理 | 段页式管理 |
|---|---|---|---|
| 划分方式 | 段（不定长），每个作业一张段表 | 页（定长），每个进程一张页表 | 现将内存分为等长页，每个作业一张段表，每段对应一组页表 |
| 虚地址 | （s, d），即（段号，段内偏移） | （p, d），即（页号，页内偏移） | （s, p, d），即（段号，段内页号，段内偏移） |
| 虚实转换 | 段表内找出起始地址，然后加段内偏移 | 页表内找出起始地址，然后加页内偏移 | 先在段表中找到页表的起始地址，然后在页表中找到起始地址，最后再加页内偏移 |
| 主要优点 | 简化了任意增长和收缩的数据段管理，利于进程间共享过程和数据 | 消除了页外碎片 | 结合了段与页的优点，便于控制存取访问 |
| 主要缺点 | 段外碎片降低了利用率 | 存在页内碎片 | 提高复杂度，增加硬件，存在页内碎片 |
在现行的虚存组织方面，最常见的就是段页式管理，在进行虚实地址转换时，可以采用公式：
\[(((x)+s)+p) \times 2^n +d\]其中$x$为基号，$s$为段号，$p$为页内号，$d$为页内偏移，$n$为$d$的总位数，$(x)$表示$x$里的内容。
3. 存储管理
在虚拟存储器的管理中，涉及：
- 调入策略：即何时将一页或一段从外存调入内存，通常有两中策略：
- 请求调入法，即需要使用时才调入
- 先行调入法，即将预计要使用的页/段先行调入内存
- 放置策略：即调入后放在内存的什么位置，与内存管理基本一致
- 置换策略：由于实际内存小于虚拟内存，因此可能会发生内存已满，但需要使用的页不在内存中的情况（缺页中断）。此时需要进行置换，即将一些内存中的页淘汰到外存，腾出空间给要使用的页
3.1 置换算法
常见置换算法如下：
- 最优（Optimized，OPT）算法：选择淘汰不再使用或将来才使用的页，这是最理想的算，但最难实现，常用与淘汰算法的比较
- 随机（Rand）算法：随机地选择淘汰的页，开销小，但可能选中立即就要访问的页
- 先进先出（FIFO）算法：选择淘汰在内存中驻留时间最长的页，但可能淘汰立即要使用的页
- 最近最少使用（Least Recently Used）算法：选择淘汰离当前点时刻最近的一段内使用的最少的页
3.2 局部性原理
存储管理策略的基础是局部性原理，即进程往往会不均匀地高度局部化地访问内存。局部性分为：
- 时间局部性：指最近访问存储位置，很可能在不久的将来还有访问
- 空间局部性：指存储访问有成组的倾向：当访问了某个位置后，很可能也有访问器附近的位置
基于局部性原理，Denning阐述了程序性能的工作集理论。工作集是进程频繁访问的页面的集合。确定进程的工作集有两种等价的方法：
- 将工作集确定为在定长的页面访问序列（工作集窗口）的页面集合
- 将工作集确定为在定长时间间隔中涉及的页面集合
另一种控制颠簸的技术是控制缺页率。操作系统规定缺页率的上下限，当一个进程的缺页率高于上限，表明该进程需要更大的内存空间，则分配较多的内存页面给它；当进程的缺页率低于下限是，表明该进程占用的内存空间过大，可以适当地收回若干内存页面。
声明：本作品采用署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)进行许可，使用时请注明出处。
Author: mengbin
blog: mengbin
Github: mengbin92
cnblogs: 恋水无意