OS-3.1 内存扩展 -- 虚拟内存
前言
虚拟内存基本概念
传统存储方式的缺点
①一次性：作业必须一次性全部转入内存后才能运行。
- 作业很大塞不进内存
- 大作业塞进去后，小作业塞不进去，并发度下降。
② 驻留性：作业被转入内存，就会一直驻留在内存中，（无论部分数据是否用得到），直到作业运行结束。
局部性原理
时间局部性，空间局部性。
虚拟内存
基于局部性原理。
从逻辑上扩充了容量。
特征：
- 多次性：无需在作业运行时一次性装入内存。
- 对换性：作业运行时无需常驻内存，可换入换出。
- 虚拟性：逻辑上扩充了内存容量。
额外的功能：
- 请求调页/段。当访问信息不在内存块时，os负责将信息从外存调入内存。
- 页面/段置换。内存空间不够时，os将内存中暂时用不到的内存块调出到外存。
如何实现虚拟内存
虚拟内存需要建立在离散分配（而不是连续分配）的内存管理方式上。
- 请求 分页存储管理
- 请求 分段存储管理
- 请求 段页式存储管理
回顾
请求分页（VS基本分页！）
与 基本分页 相比，请求分页 需要OS额外实现的功能
- 请求调页。（优先使用空的内存块）
- 页面置换（需要调入页面，但没有空闲块时进行）。
- 修改请求页表中新增的页表项。
页表（的变化）
页表项新增的四个字段：状态位（有效位），访问字段，修改位（脏位），外存地址。
缺页中断（新增）
缺页中断属于内中断（故障类型）。在一条指令执行期间，可能有多次缺页中断。
（缺页== 页中断 == 页面失效）
==缺页过程：==
- 当访问的页面不在内存时，产生缺页中断，交给os的中断处理程序处理。
- 此时缺页的进程阻塞，进入阻塞队列，调页完成后再唤醒该进程，放回就绪队列。==（请求调页）==
- 如果内存有空闲块，为进程 分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
- 如果内存中没有空闲块，则通过 页面置换算法 选择一个页面淘汰。若该页面在内存中被修改过，则要将其写回磁盘==（页面置换==
地址变换（的变化）
回顾
页面分配与置换策略（3种）
驻留集：给进程分配的 内存块 的集合。
驻留集过小，缺页率增高，不过提升所有进程的并发程度。
固定分配：os为每个进程分配一定数目的内存块，在进程运行期间不再改变。
可变分配：先为进程分配一定数目的内存块，在进程运行期间，根据情况适当加减。
局部置换：发生缺页时只能选择自己的内存块进行置换。
全局置换：可以将os空闲的内存块分配给缺页进程。也可以将别的进程持有的内存块置换到外存，再分配给缺页进程。【这会造成别的进程内存块减少，缺页率增加】
搭配得到三种分配置换策略：
①固定分配+局部置换：不容易确定应该为每个进程分配多少个内存块。
- 页框调入算法：采用固定分配时，确定应该为每个进程分配多少个内存块。平均分配、按（地址）比例分配、按优先权分配三种。
②可变分配+全局置换： 会出现 – 只要进程发生缺页，就会获得新的内存块。（要么是拿空闲的要么是拿别的进程的哈哈哈）
③可变分配+局部置换： 综合。
when调入页面
1.预调页策略：主要用于进程的首次调入。根据局部性原理，一次性调入多个相邻的页面而不是单一个。
2.请求调页策略：运行时发现缺页，才调入。
where调入页面
1.系统有足够的对换区空间
2.系统没有足够的对换区空间：把不会被修改的数据之间从文件区调走，而不是从对换区。
（因为蓝色部分数据不会被修改，之后换出也不必写回磁盘）
3.unix方式：第一次调入从文件区。之后的调入调出从对换区。
抖动/颠簸
刚换出的页面又得换回来了，或刚换入的页面又得换出外存了。（是虚拟内存的大问题哦）
原因是：分配给进程的==内存块数不够==。（驻留集大小＜工作集大小）
工作集
工作集是：在某段时间间隔里，进程实际访问页面 的集合。
通过窗口尺寸算出工作集大小。
驻留集大小大于工作集大小。（否则进程运行时会频繁缺页）（工作集不一定是驻留集的子集）
最少页框数
不由代码段长度，虚拟地址空间大小或物理内存容量决定，
取决于单条指令在取值和执行过程中可能访问的最大页面数，
该数量由指令系统支持的寻址方式决定。
回顾
页面置换算法
Note：缺页中断并不一定发生页面置换（when还有空闲内存块的时候）
页面置换算法，决定应该换出哪一个页面。
追求更少的缺页率，减少io开销。
1.最佳置换算法OPT（optimal）
选择最长时间用不到的页面，换出。
但是实际上os并不能知道之后要访问的是哪一个页面，所以OPT是无法实现的。
2.先进先出置换算法（FIFO）
每次淘汰的是最早进入内存的页面。
（这个排序/排队的队列存在最大长度，取决于系统为该进程分配了多少个内存块。）
会产生belady异常，FIFO算法性能差。【为进程分配的物理块数增大，缺页次数不减反增。】
3.最近最久未使用置换算法（LRU）
记录自上次被访问，到现在经历的时间t。
性能好。但是需要硬件支持，实现困难，开销大。
4.时钟置换算法(CLOCK)
性能和开销平衡的算法。又叫最近未用算法（NRU）
- 简单时钟算法
- 改进时钟算法
新增一个访问位（表示最近是否被访问过）
规则：当发生缺页且需要置换时，if指针（指向上次替换位置的下一帧）所指页面访问位为0，直接淘汰该页。若为1，将其置换为0，指针指向下一页面。
简单CLOCK选择淘汰界面最多会经历两轮扫描。（when第一列访问位全1，全置0后，需进行第二轮。）
改进时钟算法
只有淘汰的页面–被修改过时，才需要io操作写回外存。
所以优先淘汰没有修改过的页面，可以减少io操作。
新增一个修改位。（访问位，修改位）
最多四轮扫描。【没访问没修改00 – 没访问有修改01 –10 –11 】
回顾
内存映射文件
传统文件访问方式
内存映射文件
把磁盘上的==文件==，直接“映射”到进程的虚拟地址空间的某个区域。
1.之后就可以以访问内存的形式访问文件数据了（通过指针读写）（无需再调用 read、write 这些系统调用）
2.且os可以通过页表将对应的虚拟地址空间映射到相同的物理内存，实现多个进程共享同一文件。
内存映射文件还可以实现文件共享
回顾
Note
虚拟内存空间由虚拟地址位数决定。
虚拟地址位数由CPU位数决定！
指令相关性是什么？
虚拟页式的链接 是运行时动态链接（因为装入是动态重定位）
页框回收
1.页面缓冲算法
前言：页面换出/换入的io开销很大的。
在页面置换算法的基础上，新增一个 修改页面链表。保存已修改且需要被换出的页面。
等到被换出的页面数量到达一定值之后，再批量写回磁盘。
新增一个 空闲页面链表。
进程需要读入一个页面时，可从中取。
另外的用途：未被修改的页面被换出时，本应直接丢弃，但是放在空闲页面链表中，万一之后被访问了，可以直接取不用从内存中找。
2.页框回收
当空闲页框数量低于特定阈值时，os会主动发起页框回收操作。（而不是等到空闲页框完全用完再回收，来不及的）
虚拟存储器性能的影响因素
core：缺页率。
缺页率的影响因素有：
- 页面大小。
- 分配给进程的内存块数。
- 页面置换算法。
- 写回磁盘的频率。
- 程序的局部化程度。