第九章 虚拟存储器
主要作用：
- 将主存看作是一个存储在磁盘上的地址空间的高速缓存，在主存中只保护活动的区域，并根据需要在磁盘和主存之间来回传送数据；
- 为每个进程提供了一致的地址空间，从而简化了存储器管理；
- 保护了每个进程的地址空间不被其它进程破坏
9.1 物理和虚拟寻址
1.物理地址
计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组，每字节都有一个唯一的物理地址PA。
根据物理地址寻址的是物理寻址。
2.虚拟地址
虚拟存储器被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。
使用虚拟寻址时，CPU通过生成一个虚拟地址VA来访问主存，这个虚拟地址在被送到存储器之前先转换成适当的物理地址
9.2 地址空间
1.地址空间
地址空间是一个非负整数地址的有序集合
2.线性地址空间
地址空间中的整数是连续的。
3.虚拟地址空间
CPU从一个有 N=2^n 个地址的地址空间中生成虚拟地址，这个地址空间成为称为虚拟地址空间。
4.地址空间的大小
由表示最大地址所需要的位数来描述。
N=2^n：n位地址空间
主存中的每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。
9.3 虚拟存储器作为缓存的工具
虚拟存储器——虚拟页VP，每个虚拟页大小为P=2^平字节
物理存储器——物理页PP，也叫页帧，大小也为P字节。
任意时刻，虚拟页面的集合都被分为三个不相交的子集：
未分配的：VM系统还没分配/创建的页，不占用任何磁盘空间。
缓存的：当前缓存在物理存储器中的已分配页
未缓存的：没有缓存在物理存储器中的已分配页
9.3.1 DRAM缓存的组织结构
需要知道，这种缓存结构：
不命中处罚很大
是全相联的——任何虚拟页都可以放在任何的物理页中。
替换算法精密
总是使用写回而不是直写。
9.3.2 页表
页表是一个数据结构，存放在物理存储器中，将虚拟页映射到物理页。
页表就是一个页表条目PTE的数组
9.3.3缺页
几个定义：
缺页：就是指DRAM缓存不命中。
缺页异常：会调用内核中的缺页异常处理程序，选择一个牺牲页。
页：虚拟存储器的习惯说法，就是块
交换=页面调度：磁盘和存储器之间传送页的活动
按需页面调度：直到发生不命中时才换入页面的策略，所有现代系统都使用这个。
9.4 虚拟存储器作为存储器管理的工具
操作系统为每个进程提供了一个独立的页表，也就是一个独立的虚拟地址空间。
抖个虚拟页面可以映射到同一个共享物理页面上。
存储器映射：将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法。
9.5 虚拟存储器作为存储器保护的工具
这里需要知道PTE的三个许可位：
SUP：表示进程是否必须运行在内核模式下才能访问该页
READ：读权限
WRITE：写权限
9.6 地址翻译
地址翻译就是一个N元素的虚拟地址空间VAS中的元素和一个M元素的物理地址空间PAS中元素之间的映射。
页面基址寄存器PTBR指向当前页表。
MMU利用VPN选择适当的PTE。
PPO=VPO。
1.当页面命中时，CPU动作：
处理器生成虚拟地址，传给MMU
MMU生成PTE地址，并从高速缓存/主存请求得到他
高速缓存/主存向MMU返回PTE
MMU构造物理地址，并把它传给高速缓存/主存
高速缓存/主存返回所请求的数据给处理器。
2.处理缺页时：
处理器生成虚拟地址，传给MMU
MMU生成PTE地址，并从高速缓存/主存请求得到他
高速缓存/主存向MMU返回PTE
PTE中有效位为0，触发缺页异常
确定牺牲页
调入新页面，更新PTE
返回原来的进程，再次执行导致缺页的指令，会命中
9.6.1 结合高速缓存和虚拟存储器来看
首先，在既使用SRAM高速缓存又使用虚拟存储器的系统中，大多数系统选择物理寻址
主要思路是地址翻译发生在高速缓存之前
页表目录可以缓存，就像其他的数据字一样
9.6.2 利用TLB加速地址翻译
TLB：翻译后备缓冲器，是一个小的、虚拟存储的缓存，其中每一行都保存着一个由单个PTE组成的块
步骤：
CPU产生一个虚拟地址
MMU从TLB中取出相应的PTE
MMU将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存
高速缓存/主存将所请求的数据字返回给CPU
9.6.3 多级页表
多级页表——采用层次结构，用来压缩页表。
1.以两层页表层次结构为例，好处是：
如果一级页表中的一个PTE是空的，那么相应的二级页表就根本不会存在
只有一级页表才需要总是在主存中，虚拟存储器系统可以在需要时创建、页面调入或调出二级页表，只有最经常使用的二级页表才缓存在主存中。
9.8 存储器映射
9.8.1共享对象和私有对象
1.共享对象
共享对象对于所有把它映射到自己的虚拟存储器进程来说都是可见的
即使映射到多个共享区域，物理存储器中也只需要存放共享对象的一个拷贝。
2.私有对象
私有对象运用的技术：写时拷贝
在物理存储器中只保存有私有对象的一份拷贝
9.9 动态存储器分配
9.9.3 分配器的要求和目标：
1.要求
处理任意请求序列
立即响应请求
只使用堆
对齐块
不修改已分配的块
2.目标：
最大化吞吐率（吞吐率：每个单位时间里完成的请求数）
最大化存储器利用率——峰值利用率最大化
9.9.4 碎片
虽然有未使用的存储器，但是不能用来满足分配请求时，发生这种现象。
1.内部碎片
发生在一个已分配块比有效载荷大的时候
易于量化。
2.外部碎片
发生在当空闲存储器合计起来足够满足一个分配请求，但是没有一个单独的空间块足以处理这个请求时发生
难以量化，不可预测。
9.9.5 隐式空闲链表
堆块的格式：由一个字的头部，有效荷载，和可能的额外填充组成。
9.9.7 放置已分配的块
1.首次适配
从头开始搜索空闲链表，选择第一个合适的空闲块
2.下一次适配
从上一次搜索的结束位置开始搜索
3.最佳适配
检索每个空闲块，选择适合所需请求大小的最小空闲块
9.9.10 合并空闲块
合并是针对于假碎片问题的，任何实际的分配器都必须合并相邻的空闲块。
有两种策略：
立即合并
推迟合并。
9.9.13 显式空闲链表
1.区别
（1）分配时间
隐式的，分配时间是块总数的线性时间
但是显式的，是空闲块数量的线性时间。
（2）链表形式
隐式——隐式空闲链表
显式——双向链表，有前驱和后继，比头部脚部好使。
2.排序策略：
后进先出
按照地址顺序维护
9.9.14 分离的空闲链表
分离存储，是一种流行的减少分配时间的方法。一般思路是将所有可能的块大小分成一些等价类/大小类。
分配器维护着一个空闲链表数组，每个大小类一个空闲链表，按照大小的升序排列。
有两种基本方法：
1.简单分离存储
每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小。
2.分离适配
每个空闲链表是和一个大小类相关联的，并且被组织成某种类型的显示或隐式链表，每个链表包含潜在的大小不同的块，这些块的大小是大小类的成员。
这种方法快速并且对存储器使用很有效率。
3.伙伴系统
其中每个大小类都是2的幂
这样，给定地址和块的大小，很容易计算出它的伙伴的地址，也就是说：一个块的地址和它的伙伴的地址只有一位不同。
优点：快速检索，快速合并。
9.10 垃圾收集
垃圾收集器是一种动态存储分配器，它自动释放程序不再需要的已分配块，这些块被称为垃圾，自动回收堆存储的过程叫做垃圾收集。