1、其他方法：覆盖、交换

覆盖（Overlay）：按照执行顺序，将程序分为几部分，执行完一部分，加载下一部分并覆盖前一部分，重用物理内存。需程序员参与

交换（Swapping）：将暂不运行的进程写到磁盘上（换出），进程需要运行时，将其映像整个装入内存（换入）。实践换空间

2、虚拟内存 —— 时间换空间

只将部分程序装入内存，延迟加载，以页为单位还如换出保证进程当前使用的代码和数据都在物理内存中。。

用到时发现此页不在，产生异常，告知操作系统，进行换入操作。

虚拟内存 --> Lazy（延迟复制、延迟加载、延迟分配） + 页式管理 + 换入/换出（页面淘汰）

需硬件支持，eg：MMU、异常处理

进程对内存的访问存在局部化规律：时间局部性、空间局部性

3、页表、页目录

页目录 --> 页目录项是页表在内存的位置 --> 一个进程一个页表 --> 页表项是逻辑页与物理帧的对应关系以及一些控制关系

页表：操作系统维护，进程看不到。

页表动态建立，P为0的页表项表示虚拟页不在内存，P为0的页目录项表示整个页表都未建立。

页表的内容可以重叠，将多个虚拟页映射到同一个物理帧，实现内存共享。

虚拟内存区域：描述进程虚拟地址空间中的连续区间及其属性

有效虚拟地址空间：记录进程页目录的位置，组所有的虚拟内存区域

4、隔离、借用、延迟、换入、换出、存取时间

（1）隔离：段式管理中的段表隔离开了逻辑段和物理段；页式管理中的页表隔开了逻辑页和物理帧。通常在页式管理上实现虚拟内存。

请求调页：页式管理中，取消全部装入的限制，只将进程真正访问到的页装入内存在内外存间以页为单位换入/换出。（按需调页）

请求调页 --> 一页一页；交换技术 --> 整个

（2）借用

文件页：进程的数据和程序本来就在文件中，驻留在外存，称为文件页。

匿名页：进程临时申请的内存页（如堆栈），没有对应的文件。借用交换设备或文件页来暂存匿名页。

借用外存：文件页的延迟装入。

建立一个域表，记录虚拟内存页与文件页的映射关系（即虚拟内存页的内容来源）。域表中没有对应关系的页就是匿名页。

（3）延迟 Lazy

进程访问到不在物理内存的虚拟页，MMU内存管理单元无法将虚拟地址转化成物理地址，，产生一个页故障 Page fault 异常，在其处理程序中完成物理页的分配、换入。

（4）换入 Swapin

进程访问不在内存的页，产生异常，操作系统获得控制权：

① 进程对内存的访问是否合理：堆栈不断下压越界 --> 将区域往下扩一下。

②合法后进行：

（5）换出 Swapout

将某些进程页换回到外存（文件或交换设备），回收他们占用的物理帧。

有些页可以直接废弃，不用换出。最好换出暂时不会被访问到的页。

（6）有效存取时间 = （1-p）*ma+p*换入时间

p为出现缺页异常的概率；ma为内存存取时间（存或取一次物理内存的时间）

换入时间包括：异常处理时间、I/O操作时间、I/O完成后的善后处理时间

进程的总执行时间 = 加载时间 + 运行时间

5、虚拟内存实现ucore&Linux（略写）

1、操作集 vm_ops：open 打开、close 关闭、fault 页故障

2、32位机器上，进程的虚拟地址空间有4GB，内核使用高端1GB，进程使用低端3GB。

低端虚拟地址空间按动态分区法管理。（事先不知多大，静态不合适；摆一次就不动了，灰板算法没必要）

3、（1）Linux的布局方案

（2）ucore 的布局方案

程序和数据区域加载是建立，位于低端；堆区域进接数据区域，向上增长；堆栈区域位于最高端，向下增长；动态链接库、函数库、数据文件等东泰监理，位于堆和堆栈之间。

虚拟内存区域组成成红黑树或者链表。

4、进程刚创建时虚拟地址空间是从父进程复制clone的 --> 通常采用 Copy on Write 的方式。

先不复制，父进程和子进程对于页均为只读，若去写会异常，然后再复制再写。

新进程若想改变自己的行为 --> 通过exec类的系统调用加载新的可执行程序，重建虚拟地址空间（进程自己完成）

ELF是Linux的标准可执行文件格式。目标文件、可执行文件、共享库文件、内核模块文件、内核均采用ELF格式。

只建立域表和页目录，将页表的建立工作推迟到真正使用时。

5、程序加载、虚拟地址空间建立 -->  exec类系统调用（exec的工作见ppt）

CR3为正在执行的函数程序的页表。

6、修改进程系统堆栈的栈顶

7、页故障异常：①处理成功 --> 引起异常的指令重新执行 ；②不能成功处理 --> 系统严重错误，向当前进程发送SIGNAL信号，将其杀死。

页故障处理：①文件映射页的故障处理；②匿名页的故障处理；③写实复制页的故障处理；④换出页的故障处理（见ppt）

8、进程终止时，虚拟内存要全部释放。

6、页面淘汰（页面置换）Page Repalcement

1、换出位置和换出方法

回收内存的方法：废弃、写出后回收

换出的位置：映射文件、交换设备（页写回映射文件 --> 用域确定页在文件中的信息）

①共享域：页来源于映射文件，内存中只有一份拷贝，允许多个进程同时访问修改，一个进程的修改结果会立刻被其他进程看到。

②私有域：页式进程专有，内存中会有多个副本，可被多个进程同时读，不允许同时写，进程要修改/写死有余中的共享页时，为其创建一个副本Copy on Write。修改其他进程无法看到。

2、页面淘汰算法

内核页不能淘汰。

评价淘汰算法 --> 缺页率 = 缺页次数 / 总的内存访问次数

（1）最优淘汰算法（OPT）

淘汰将来不在使用的页，或在最远的将来才会使用的页。

缺页率最低，无法实现。

（2）先入先出法（FIFO）

淘汰驻留内存时间最长的页。

不太好。还可能引起反常现象：

（3）二次机会算法（Second Chance）

页面的最近使用情况记录在页表项中，访问位 A 和修改位 D。

淘汰时按 FIFO 选择最老的页面，若 A=0，则淘汰，若 A=1.则将 A 清0，再给一次机会并调到队尾。

（4）时钟算法（Clock）

对二次机会算法的一种改进，将页面队列做成环形链表，定义指针指向下次检查的开始位置，每次移动指针即可，减少开销。

（5）最近未使用算法（NRU）Not Recently Used

改进时钟算法。D=1为脏页；D-0位干净页。干净页淘汰代价小于脏页（脏页淘汰还要写出去）

（6）最久未使用算法（LRU）Least Recently Used

淘汰最长时间未访问的页面。

不会出现反常现象，需记录页面访问顺序：

①计数器：访问一次内存，计数器加1，在页表项中增加使用时间域。选择逻辑时钟或计数器最小的页面。

②堆栈：用一个栈保留被访问的页号，正在被访问的页面页号在栈顶。LRU 就是从栈底选

（7）附加访问位算法（近似 LRU）

（8）其他改进算法

①空闲帧池

系统维护一个空闲帧池，保存立刻可用的空闲帧。淘汰的页面换出后，其占用的帧加入空闲帧池。换出之前，先从空闲帧池中分配一个空闲帧，减少申请者的等待时间。

②脏页队列

系统维护一个脏页队列，保存被修改过的页。启动守护进程，外存设备空闲时，守护进程选择脏页写出，变成干净页。内存紧张时直接将干净的映射文件页废弃。将写出淘汰页 ed 工作分散开。

③页缓存

从外存读入的所有野放入页缓存。需从外存读入时先查页缓存，若有，直接使用。已写出的空闲页仍保留在页缓存，知道被再次分配。（延迟回收♻️）

页缓存和交换缓存均可防止淘汰算法的失误。

④交换缓存

交换缓存记录既在交换设备又在物理内存中的页。减少重复的换入/换出。页被写到交换设备后，回收物理帧，交换设备上的页被换入后，释放交换设备上的额页，但当这页真的被分走了，才从交换缓存去掉。

3、页面淘汰策略

①局部淘汰

一个进程页不够用时只能淘汰自己进程的页 -->  进程占用总也属于不变。

②全局淘汰

一个进程页不够用时，还可以淘汰其他进程的页 --> 进程占用的总页数在变化

7、颠簸、工作集

（1）颠簸 / 抖动

发生颠簸时，系统大部分时间在忙于换入 / 换出。

（2）工作集 Working set

工作集是一个进程在某一小段时间内访问到的页面集合。 -->  过去 t 秒实际运行时间内进程访问到的页面集合。

工作集内的页不应淘汰，工作集外的页可以淘汰。

（3）工作集淘汰算法 （WSClock 算法）

8、Ucore 的页面淘汰（见 ppt）

老版本 Ucore 采用的近似 LUR（附加访问位算法）。（应该是有修改改进什么的……）

新版 Ucore 实现了一个 FIFO 算法。

PRA 队列 Page Replacement Algorithm