内存管理与虚拟内存
内存管理基础
存储管理的目的：
- 主存的分配金额管理
- 提高主存储器的利用率
- 扩充主存容量
- 存储保护
- 方便用户
程序的装入和链接
在多道程序环境下，要使程序运行，必须先将它装入内存，然后再将其变为一个可以执行的程序，通常都要经过以下几个步骤：
逻辑地址与物理地址
- 逻辑地址：在每个目标都从0开始编址。不同的进程可以拥有相同的逻辑地址
- 物理地址：地址转换的最终地址，进程执行指令和访问数据最后都要通过物理地址从主存中存取
重定位
重定位的时机
- 程序编译连接时
- 程序装入内存时
- 程序执行时
重定位的分类
- 静态重定位：装入时把作业中的指令地址和数据地址全部一次性地转换成绝对地址，所以无需再进行地址转换，且不能移动位置。
- 动态重定位：执行时每当执行一条指令时由硬件的地址转换机构将指令中的逻辑地址转换成绝对（物理）地址。地址转换公式为：绝对地址=基地址寄存器的值+逻辑地址。
内存保护
内存保护是操作系统对电脑上的内存进行访问权限管理的一种机制。内存保护的主要目的是防止某个进程去访问不是操作系统配置给它的寻址空间。这个机制可以防止某个进程，因为某个写程序错误或问题，而有意或无意地影响到其他进程或是操作系统本身的运行状态和数据
内存保护的两种方法（判断有无越界）
- 上、下限寄存器：存放用户作业在主存中的下限和上限地址
- 重定位寄存器和界地址寄存器：重定位寄存器最小的物理地址值，界地址寄存器含逻辑地址的最大值。
对换和覆盖
对换和覆盖式逻辑上内存扩充的两种方式，其目的是节省主存空间
- 覆盖：覆盖技术是一个程序通常由若干功能上独立的程序段组成，在运行时，并不是所有的程序段都同事调入内存执行。因而可以按照程序自身的逻辑结构，让不同时执行的程序段先后共享同一块内存区域。
- 对换
- 换入：把准备好竞争CPU运行的程序从辅存移到内存的过程。
- 换出：把处于阻塞状态的程序从内存移到辅存的过程称。
- 对换与覆盖的区别
- 覆盖用于同一个作业或进程中，交换用于不同的作业或进程中。
- 交换技术提高作业道数，覆盖技术针对空间不足的问题。
连续分配管理方式
内存分配与回收
内部碎片：就是已经被分配出去，却不能被利用的内存空间
内部碎片程序小于固定大小时，也会占用一个完整的分区空间，此时分区内部就存在空间浪费
外部碎片：指的是还没有被分配出去，但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。
- 回收区与F1合并，空闲区首地址为F1的首地址
- 回收区与F2合并，空闲区首地址为回收区首地址
- 需要删除F1表项，并把F2表项的大小改成F1、回收区、F2之和
- 需要增加一个空闲区表项，表项的首地址为回收区的首地址，表项的大小为回收区的大小。
分页存储管理方式
分页地址中的地址结构
图中的地址长度为32位
0~11位页内地址，即每页的大小为4KB；
$2^{12}=2^2\cdot2^{10}=4\cdot1024(b)=4(k)$
12~31位为页号，地址空间最多允许有1M页。
$2^{20}=2^{10}\cdot2^{10}=1\cdot1024\cdot1024(b)=1(M)$
两级页表和多级页表
两级页表的逻辑地址结构
地址变换机构
地址变换机构的基本任务借助页表，将逻辑地址中页号转换为内存中的物理块号（可以由一组专门寄存器来实现）
基本思想：为了尽可能减少内存浪费，将内存化为表较小的的大小相等的块作为内存分配单位
快表
TLB是一个具有并行查寻能力的特殊高速缓存寄存器，又称为"联想寄存器"。增加快表的原因:页表是存放在内存中的，则CPU每存取一个数据时，都要两次访问内存，为了提高地址变换速度，增设快表。
两此访存指：第一次访问内存得到物理地址，第二次根据物理地址访问对应的内存单元
分段存储管理方式
在分段存储管理方式中，以段为单元分配，每段是一个连续存储区。
段的长度不固定，而段与段之间不一定连续
分段系统中逻辑结构
页式和段式的区别：
- 页式的地址是一维的，段式的地址二维的。
- 分页由操作系统决定，而分段式由用户决定的。
- 页式和段式都可以采用动态重定位方式。
段页式存储管理方式
段页式系统中的逻辑地址结构：
虚拟内存管理
虚拟存储器概述
虚拟存储器是指具有请求调入功能和置换功能，从逻辑上对内存容量加一扩充的一种存储器系统。虚拟存储器的容量由计算机的地址结构决定。
虚拟存储器的特征：
- 多次性：允许被分成多次调用内存运行，即只需将当前要运行的那部分程序和数据装入内存即可开始运行。
- 对换性：允许在作业的运行过程中进行换进、换出。
- 虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量
常规存储管理方式的特征：
- 一次性：指作业必须一次性地全部装入内存后方能开始运行。
- 驻留性：作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。
常规存储管理方式的局部性原理：
- 时间局部性：如果某数据被访问过，则不久以后该数据可能再次被访问。
- 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也被访问。
页框分配
页式地址=页面起始地址+页内偏移地址
对应于虚拟地址：page（页面）
对应于物理地址：frame（页框）
- 何时调入页面
- 预调页策略
- 请求调页策略
- 页面调入过程
- 发出缺页中断
- 将所缺页调入内存
- 修改页表
页框分配必须满足：
每个进程所需要少的页数
物理块分配策略：
- 平均分配算法
- 按比例分配算法
- 考虑优先权的分配算法
请求分页管理方式
- 请求页表机制
请求分页系统的页面结构如下：
状态位（存在位）：用于判断页面是否在主存中
访问字段：用于记录页面在一段时间内被访问的次数，或最近已有多久未被访问
修改位：用于表示页面调入内存后是否被修改过
外存地址：用于指出页面在外存上的存放地址
- 缺页中断机构
缺页中断机构缺页与一般中断的区别：
- 在指令执行期间产生和处理中断信号。
- 一条指令在执行期间可能产生多次缺页中断
- 地址变换机构
- 操作系统对缺页的处理方法
- 磁盘I/O
- 分配页框
- 修改页表
页面置换
最佳置换算法（OPT）
淘汰以后不再使用或最迟使用的页面。
此时OS根据最佳置换算法将选择页面7淘汰。因为：
- 页面0是第5个被访问的页面
- 页面1是第14个被访问的页面
- 页面7是第18个被访问的页面
先进先出算法（FIFO）
最早出现的置换算法，淘汰最新进入内存的页面
最近最久未使用算法（LRU）
淘汰最近最久未使用的页面
时钟置换算法（CLOCK）
内存映射文件（Memory-Mapped Files）
内存映射文件（Memory-Mapped Files）是一种文件且文件内容被映射到内存了，使用者可以通过内存读写来读读写该文件。其效果是使得使用者可以像读写内存数据一样的方式读写磁盘文件。
- 自动文件内容映射到内存，且可以做到“按需”隐射——只将文件的部分内容映射到内存。
- 同一个文件可被多个进程映射到各自内存，各进程看到的内容一致，即自身做到了“同步”。
- 效率高——直接使用OS内存而不是语言自身的内存，因此少了一些数据复制操作。
内存映射文件从功能上看与传统做法的无异，但效果上却大不相同，体现在：文件内容加载、按需加载、同步等全由内存映射文件自身支持而不需要开发者介入，效率更高。因此，内存映射文件的主要使用场景是需要频繁读取的文件数据、进程通信等。
内存映射文件是一种高效的文件IO技术，由OS提供支持。各种语言对内存映射文件的支持实际上就是进行了一层封装，最终仍是利用OS提供的能力。
虚拟存储器性能的影响因素及改进方法
Cache的性能指标是其命中率；
主存的性能指标是其存储容量，存取时间、存储周期和存储器带宽；
虚拟存储器的性能指标是主存的命中率（缺页次数）
在进程的运行过程中，缺页率f定义为： $$ f=\frac{F}{F+s} $$
s：访问页面的成功次数
F：访问页面失败的次数
影响缺页次数的因素：
- 分配给进程的物理块数
- 页面大小
- 程序固有特性
- 页面淘汰算法