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）
==每次淘汰的是相对最早进入内存的页面。==
（这个排序/排队的队列存在最大长度，取决于系统为该进程分配了多少个内存块。）
FIFO算法==性能很差==，==会产生belady异常==：为进程分配的物理块数增大，缺页次数不减反增。
3.最近最久未使用置换算法（LRU）
==记录自上次被访问，到现在经历的时间t最长的。==
性能好。但是需要硬件支持，实现困难，开销大。
4.时钟置换算法==(CLOCK)==
性能和开销平衡的算法。又叫**==最近未用算法（NRU）==**
- 简单时钟算法
- 改进时钟算法
新增一个访问位（表示最近是否被访问过）
规则：当发生缺页且需要置换时，==if指针（指向上次替换位置的下一帧）所指页面，访问位为0，直接淘汰该页。若为1，将其置换为0，指针指向下一页面。==
简单CLOCK选择淘汰界面最多会经历两轮扫描。（when第一列访问位全1，全置0后，需进行第二轮。）
改进时钟算法
只有当淘汰的页面 没有被修改过时，才==需要io操作写回外存==。
==没有访问＞没有修改过的页面＞其他==
新增一个修改位。==（访问位，修改位）==
==最多四轮扫描==。【没访问没修改00 – 没访问有修改01 –00 (将扫描过的页面都置0，本来应该为10的)–11 】
回顾
内存映射文件
传统文件访问方式
==内存映射文件==
把磁盘上的文件，直接“映射”到进程的虚拟地址空间的某个区域。
1.之后就可以**==以访问内存的形式访问文件==**⭐（通过指针读写）（无需再调用
read、write这些文件系统调用）2.且os可以通过页表将对应的虚拟地址空间映射到相同的物理内存，实现多个进程共享同一文件。
注意：不是直接实现“页到磁盘块的映射”。
内存映射文件还可以实现文件共享
回顾
Note
==最大虚拟内存空间==，由虚拟地址位数决定。
- 虚拟地址位数，由CPU位数决定。
指令相关性是什么？
虚拟页式的链接 是运行时动态链接（因为装入是动态重定位）
页框回收
1.页面缓冲算法
前言：页面换出/换入的io开销很大的。
在页面置换算法的基础上，新增一个 修改页面链表。保存已修改且需要被换出的页面。
等到被换出的页面数量到达一定值之后，再批量写回磁盘。
新增一个 空闲页面链表。
进程需要读入一个页面时，可从中取。
另外的用途：未被修改的页面被换出时，本应直接丢弃，但是放在空闲页面链表中，万一之后被访问了，可以直接取不用从内存中找。
2.页框回收
当空闲页框数量低于特定阈值时，os会主动发起页框回收操作。（而不是等到空闲页框完全用完再回收，来不及的）
虚拟存储器性能的影响因素
==core：缺页率。==
缺页率的影响因素有：
- 页面大小。
- 分配给进程的内存块数。
- 页面置换算法。
- 写回磁盘的频率。
- 程序的局部化程度。