虚拟存储
目的
存储器：快的贵，便宜的慢。所以不用的时候放便宜的，用的时候放快的
覆盖与交换
覆盖
把进程分为若干个子模块，进程的必要部分，常驻内存，其余的不存在调用关系的模块分成多组，每组共享一部分内存，大小由组中需求最大的决定。
开发难度增加，由程序员进行模块划分，确定模块间的覆盖关系；也增加了执行时间，从外存装入覆盖模块。
交换
内存空间不够时，将暂时不运行的进程放到外存，以进程为单位。
程序换入时采用动态地址映射的方法，重定位。
局部性原理（虚拟存储的前提）
概念：程序在执行的过程当中在一个较短的时间里，它所执行的指令和指令操作数的地址分别局限于在一定区域里
通常情况下我们指令是存在代码段里的，指令所访问的操作数呢通常是存在数据段里的
时间局部性：一条指令的连续两次执行和一个数据的连续两次访问集中在一段较短的时间
空间局部性：相邻的几条指令访问的相邻的几个数据通常情况下是局限在一个较小的区域里头；
分支局部性：一条跳转指令的两次执行很多时候是会跳转到同一个地址的
虚拟存储的基本概念
原理
装载程序时只需将当前指令所需要的页面加载到内存
指令执行中需要的指令或数据不在内存时处理器通知操作系统将相应的页面调入内存
基本特征
不连续性：物理内存分配非连续，虚拟地址空间使用非连续；
大用户空间：提供给用户的虚拟内存可以大于实际的物理内存；
部分交换：只对部分虚拟地址空间进行调入和调出
实现前提
硬件支持：页式或短时存储的地址转换机制。
操作系统：管理内存和外存页面或段的换入换出。
虚拟页式存储
在页式存储管理的基础上增加请求调页和页面置换。
满足以上添加页变项中，增加这些位
驻留位：它是表示该页面是否在内存当中
修改位：表示这一页在内存当中是否被修改
访问位：表示是否被访问过，用于页面置换算法；
保护位：可读可写可执行等。
缺页异常
异常->中断->找外存->有空位放空位，没空位置换->继续执行
外存管理：在何处保存未被映射的页？
代码段直接指向可执行文件
动态加载的共享库指向动态库文件
其他段就可以放专门的对换区
有效存储访问时间：访存时间(1-p) + 缺页异常处理时间缺页率p
页面置换算法(解决谁退出的问题)
- 不能置换的
有些页面必须常驻内存，或是操作系统的关键部分，或是要求响应速度的页面，加上一个锁定位，不进行置换。
- 局部页面置换（单进程内部）
最优算法、先进先出、最近最久未使用、时钟置换算法
- 全局置换算法（所有进程）
选择所有可换出的物理页面
最优算法
选择未来最长时间不被访问的页面。
缺页次数最少，但无法实现，作为置换算法的评测依据
先进先出算法
队列实现
性能接近随机访问，可能出现belady现象(随着分配的页面增加，缺页次数反而升高的现象)
最近最久未使用算法（LEU）
缺页时，计算每个逻辑页面的上一次访问时间，选择时间最长的
实现
页面链表：把最近访问的，放链首；缺页时，替换链尾
活动页面栈：访问时也好压入栈顶，抽出相同的页号，缺页时。替换栈底
缺点，开销太大
时钟置换算法
增加访问位，将页面设置成环形链表，指针指向的调入页面
被访问过得界面，访问位置一，拥有一圈内“免死”的权利，但被指针指过后“免死”失效。
缺页->指针单方面偏移，寻找没有“免死”的页面->找到后置换
改进：增加修改位，若未修改不写回。（我觉得都能用）
性能：是FIFO和LRU的折中
最不常用算法（LFU）
每个页面设置一个访问计数，访问页面时访问次数加一
缺页时置换计数最小的页面。定期对计数器进行衰减（避免老而不死）。
LRU关注多久未访问，LFU关注访问次数。
工作集置换算法
思路：给进程分配可变数目的物理页面
工作集：进程使用的逻辑页面的集合，表示为二元函数（t, delta）t是当前执行时刻，delta是工作集窗口，代表定长页面访问时间窗口
常驻集：进程的实际驻留内存的页面集合
常驻集如果包含了工作集，缺页率比较小；
工作集发生剧烈变动时，缺页较多；
进程常驻集达到一定大小之后，缺页率也不会明显下降。
实现
维护一个访存页面链表（工作集）
访存时换出不在工作集的页面，更新访存链表
缺页时换入页面，更新访存链表。
缺页率置换算法
缺页率
缺页次数与内存访问次数的比值，或缺页平均时间间隔的倒数
受页面置换算法、分配给进程的物理页面数目、页面大小和程序本身的影响。
缺页率随着物理页面的增加而降低。
实现
访存时设置引用位标志
出现缺页时计算从上次缺页时间到现在时间的时间间隔
根据缺页率调整物理页面的分配数量
抖动和负载控制
抖动：
概念：进程物理页面较少，造成大量缺页，频繁置换，进程运行速度变慢。
主要原因：进程数太多了
负载控制：
通过调节并发进程数来进行系统负载均衡。
平衡点：平均缺页间隔时间（MTBF）等于缺页异常处理时间（PFST）。
CPU利用率与并发进程数的关系（先增后减）
（1）进程数少时提高并发进程数，可以提高CPU利用率；
（2）并发进程导致了内存访问增加；
（3）并发进程的内存访问会降低访存的局部性特征，导致了缺页率上升。