传统存储管理方式的特征
- 一次性：作业必须一次性全部装入内存后才能开始运行
- 驻留性：作业被装入内存后会一直驻留在内存中
前者导致：
1、作业很大时不能全部装入内存
2、大量作业运行无法全部装入，并发度下降
后者导致运行时只需访问作业一小部分，所以大部分被浪费了
局部性原理
- 时间局部性：由于循环等程序特征，导致指令短时间内多次循环
- 空间局部性：由于很多数据在内存中是连续存放的，指令也是连续存放，所以程序访问存储单元后，很可能附近储存单元也会被访问
虚拟内存的定义和特征
在程序装入时，程序将很快会用到的部分装入内存，暂时用不到的部分留在外存
在程序执行时，所访问信息不在内存时，由操作系统负责将所需信息从外存调入内存
在内存不够时，操作系统负责将用不到的信息调出外存
这样一个看起来很大的内存，就是虚拟内存
特征：
1、多次性：被允许分成多次调入
2、对换性：被允许在作业允许过程中将作业换入换出
3、虚拟性：内存容量看起来比原来的大很大
实现虚拟内存技术
建立在离散分配的内存管理方式基础上
实现：
1、请求分页存储管理
2、请求分段存储管理
3、请求段页式存储管理
与传统非连续分配存储管理的主要区别：
1、所访问信息不存在时，操作系统负责将信息从外存调入（请求调页/调段）
2、内存空间不够时操作系统负责将不用的信息调出（页面置换/段置换）
请求分页管理方式
缺页中断
缺页中断（属于内中断）：当前执行的指令未调入内存时发生。
一条指令可能发生多次中断 e.g:copy A to B
//和普通内存调用的区别以后再补//
页面置换算法
越好的算法应该追求更少的缺页率
最佳置换算法（OPT）
每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面
缺页时未必发生页面置换，若还有可用的空闲内存块，则不需进行页面置换是一个无法实现的理想算法
先进先出置换算法（FIFO）
每次选择淘汰的页面是最早进入内存的页面
Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象
只有FIFO会发生这个异常，算法性能最差，因为有可能先进的页面很受欢迎
最近最久未使用置换算法（LRU）
每次淘汰的页面是最近最久未使用的页面
实现方法：对应页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t
特点：算法性能好，实现困难，开销大
时钟置换算法（CLOCK）/最近未用算法（NRU）
折中算法
简单CLOCK算法实现方法
为每个页面设置一个访问位，将内存中的页面用指针连接成循环队列。设置两个指针，一个是扫描指针，用来在循环的队列中循环扫描；一个是访问指针，用来指向待访问的页面串。每次访问指针变动时，检测队列中页面，相应页面访问位置1，若访问指针指向队列中不存在的页面，也就是当到需要选择页面替换的时候，移动扫描指针知道遇到访问位为0的块对应页，将其替换，若扫描指针指到访问位为1，则置0（复活甲）
最多进行两轮扫描
改进CLOCK算法
相对前者多考虑了一个未被修改页面不需要写回外存的设定，即只有被淘汰的页面被修改过的，才需要写回外存。
具体规则简单来说分四大优先级：
* 第一优先——最近没访问，且没修改的页面（0，0）
* 第二优先——最近没访问，但修改过的页面（0，1）且改访问位为0
* 第三优先——最近访问过，但没修改的页面（0，0）
* 第四优先——最近访问过，且修改过的页面（0，1）
助记：00，01，10（改访问位之前），11
页面分配策略
驻留集
指请求分页存储管理中给进程分配的物理块的集合
我更喜欢另一种解释：进程已装入内存的页面的集合
其实就是作业里操作系统给进程分配的固定块数量
从操作系统角度，可以分为固定分配与可变分配两种 从进程本身角度，可以分为局部置换与全局置换两种 顾名思义，固定分配肯定和全局置换（可以置换其他空闲物理块或别的进程的物理块）相矛盾
| 固定分配 | 可变分配 | |
|---|---|---|
| 局部置换 | √ | √ |
| 全局置换 | × | √ |
所以页面分配策略能分为以下三种
页面分配/置换策略
固定分配局部置换
物理块在分配期间不变，且发生缺页时切换都发生在给自己分配的页面中进行
缺点：物理块的分配难以测定，不知道分多少合适
可变分配全局置换
物理块分配可以改变，发生缺页时，操作系统从空闲物理块队列中取出一块分配给该进程，当没有空闲物理块时，选择一个未锁定的页面换出外存，再分配给进程
未锁定:不能置换出外存的页面,如一些内核数据等
优点:发生缺页时必定获得新物理块
缺点:被分出物理块的进程缺页率增加
可变分配局部置换
根据缺页率来分配,刚开始物理块不变,若缺页率较高则分配物理块,若较低则分出物理块
调入页面的时机
预调页策略:根据局部性原理提前调入多个相邻页面,主要用于进程的首次调入,成功率低(50%)
运行前
请求调页策略:运行期间发生缺页时才将所缺页面调入内存,需要频繁使用I/O操作
运行时
抖动/颠簸
症状:频繁的页面调入调出
发生原因:进程频繁访问的页面数量高于物理块数(其实就是物理块分配不够)
物理块分配少,抖动发生频繁,物理块分配多,造成系统整体并发度降低
所以"工作集"概念被提出
工作集
指在某段时间间隔内,进程实际访问页面的集合
例如(某窗口尺寸下):
1 3 5 6 3 5 3 5
工作集为1 3 5 6
驻留集回顾:给进程分配的物理块的集合
驻留集大小不能小于工作集大小,否则容易频繁缺页
所以说在实际应用中,根据工作集给出页面置换算法是是比较科学的选择,如上例子给出4个以上内存块就能满足运行需要