虚拟内存：只需要将正在运行的程序的一部分加载到内存中进行执行

虚拟内存将用户的逻辑内存与物理内存分开

逻辑（或虚拟）地址空间可以大于物理地址空间

允许由多个进程共享物理地址空间

实现更快的进程创建

fork（）怎么样？

虚拟内存可以通过以下方式实现：

 Demand paging （请求调页，按需调页，请求页式管理）

 Demand segmentation（请求段式管理）

 局部性原理(principle of locality)：指程序在执行过程中的一个较短时

期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。

表现为：

 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；

 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻

近的数据都集中在一个较小区域内。

 虚拟存储器是具有请求调入功能和置换功能，能仅把进程的一部分装入内存便可运行进程的存储管理系统，它能从逻辑上对内存容量进行扩充的一种虚拟的存储器系统

只有在需要页面时，才能将页带入内存

需要更少的I/O需要

更少的内存需要

更快的响应

更多的用户

页面需要–>引用它

无效引用–>中止

不在内存中–>带到内存中

延迟交换-永远不要将页面交换到内存，除非页面是需要的

处理页面的交换器是一个寻呼机

每个页表条目都关联一个有效无效位（v–>在内存中，i–>不再内存中）

最初的有效-无效位在所有条目上被设置为i

页面表快照的示例：

在地址转换过程中，如果页面表项中的有效-无效位是i–>页面错误

 在请求分页系统中的每个页表项如图所示：

 状态位P（存在位）：用于指示该页是否已调入内存，供程序访问时参考。

 访问字段A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页时参考。

 修改位R/W：表示该页在调入内存后是否被修改过。

 外存地址：用于指出该页在外存上的地址，供调入该页时使用

如果有对一个页面的引用，第一个对该页面的引用将陷入到操作系统：

页错误

1.操作系统查看另一个表来决定：

无效引用–>中止（非法地址访问）

只是不在内存中

2.获取空帧

3.将页面交换为帧

4.重置表

5.设置有效位=v

6.重新启动导致页面故障的指令

页面故障率p在[0.0,1.0]的范围内：

如果p为0.0，则根本没有页面错误

如果p为1.0，则每一页都是一个页错误

通常p很低。。

有效的内存访问时间为

要计算EAT，我们必须知道服务一个页面故障需要多少时间。页面故障会导致发生以下顺序：

1.陷入到操作系统。

2.保存用户寄存器和进程状态。

3.确定该中断是一个页面故障。

4.检查该页面引用是否合法，并确定该页面在磁盘上的位置。

5.发出从磁盘读取到空闲帧的读取操作：

在此设备的队列中等待，直到读取请求得到服务

等待设备查找时间和延迟时间

开始将页面转移到一个空闲帧中。

6.在等待时，将CPU分配给其他用户（CPU调度，可选）。

7.从磁盘中断(I/O已完成）

8.为另一个用户保存寄存器和进程状态（如果执行步骤6）。

9.确定该中断是否来自该磁盘

10.更正页面表和其他表，以显示所需的页面现在在内存中

11.等待CPU再次分配给此进程

12.恢复用户注册器、进程状态和新页表，然后恢复中断指令。

页面故障服务时间的三个主要组成部分

 Service the page-fault interrupt(缺页中断服务时间)

 Read in the page(将缺页读入时间)

 Restart the process(重新启动进程时间)

虚拟内存允许在创建过程中的其他好处：

Copy-on-Write（写时拷贝）

写时拷贝（COW，Copy-on-Write）允许父进程和子进程最初在内存中共享相同的页面。如果其中任何一个进程修改了共享页面，则只复制该页面

COW允许更有效的过程创建，因为只复制修改后的页面

空闲页面是从一个零化页面池中分配的

Windows、Linux、Solaris

如果没有自由的帧怎么办？

页面替换-在内存中找到一些页面，但没有真正使用，交换它

算法

性能-需要一个算法，将导致最小数量的页面错误

同一页可能会被多次带入内存

通过修改缺页服务例程以包括页面替换，防止内存过度分配

使用修改（脏）位减少页面传输开销-仅将修改的页面写入磁盘

页面替换完成了逻辑内存和物理内存之间的分离——可以在较小的物理内存上提供较大的虚拟内存

页面置换过程

1.在磁盘上找到所需页面的位置

2.找到一个自由帧

如果有一个自由的帧，使用它

如果没有空闲的框架，请使用页面置换

选择victim（淘汰）帧的算法

将淘汰页面写入磁盘，并相应地更改页面和帧表。

3.将所需的页面引入（新的）自由帧中；更新页面和帧表

4.重新启动进程

想要最低的页面故障率

通过在特定的内存引用字符串（引用字符串，引用串）上运行算法，并计算该字符串上的页面错误数来评估算法

引用字符串：（每页100个字节）

0100, 0432,0101,0612, 0102,0103,0104,0611,0120 --> 1,4,1,6,1,6,1

在我们所有的示例中，引用字符串都是

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1.、

 First-In-First-Out Algorithm (FIFO，先进先出算法)

 Optimal Algorithm （OPT 最佳页面置换算法）

 Least Recently Used (LRU) Algorithm (最近最久使用算法)

 LRU Approximation Algorithms （近似LRU算法） ：

附加参考位算法

第二次机会（时钟）算法

增强的二次机会算法

计算基数页面替换：

 Least Frequently Used Algorithm (LFU最不经常使用算法）

 Most Frequently Used Algorithm (MFU引用最多算法)

Page Buffering Algorithm（页面缓冲算法）

发生了多少次页面错误？

–15次页面错误

OPT(最佳页面置换算法)：Replace page that will not be used for longest period of time。选择“未来不再使用的”或“在离当前最远位置上出现的”页被置换。

你是怎么知道的？

用于衡量算法的执行效果

9个页面错误

LRU(最近最少使用算法)：选择内存中最久没有引用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间，

硬件开销太大。

12个页面错误

计数器实现

每个页面条目都有一个计数器；每次通过此条目引用页面时，都将时钟复制到计数器中

当需要更改页面时，请查看计数器，以确定要更改哪个

堆栈实现-以双链接的形式保存一堆页码：

引用的页面：

将它移到顶部

需要更改6个指针

没有搜索置换

使用一个堆栈来记录最新的页面引用

引用位

与每个页面都有一点关联，最初是=0

当页面被引用时，位设置为1

替换0（如果存在）

然而，我们并不知道这个顺序

1.附加引用位算法

在内存中的一个表中为每个页面保留一个8位的字节

每隔一段时间（每100 ms），一个计时器中断将控制转移到操作系统。操作系统将每个页面的参考位转移到其8位字节的高阶位，将其他位右移1位，丢弃低阶位。这些8位字节包含了过去8个时间段的页面使用的历史记录。

如果我们将这些8位字节解释为无符号整数，数字最少的页面是LRU页面，可以替换。

被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。

2.第二次机会（时钟）算法

需要引用位

时钟置换

如果要替换的页面（按时钟顺序）具有参考位=1，则：

设置引用位为0

将页面留在内存中

更换下一页（按时钟顺序）

3.增强第二次机会算法（改进型的clock算法）

使用引用位和修改位：引用过或修改过置成1

（引用位，修改位）：

 (0,0): best page to replace

 (0,1): not quite good for replacement

 (1,0): will be used soon

 (1,1): worst page to replace.

淘汰次序：(0,0) -->(0,1)–>(1,0)–>(1,1)

Macintosh系统中使用

记录每个页面的引用数量

LFU算法：用最小的计数替换页面

MFU算法：基于计数最小的页面可能刚刚被引入，尚未被使用的论点

 页面缓冲算法: 通过被置换页面的缓冲，有机会找回刚被置换的页面

 被置换页面的选择和处理：用FIFO算法选择被置换页，把被置换的页面放入两个链表之一。即：如果页面未被修改，就将其归入到空闲页面链表的末尾，否则将其归入到已修改页面链表。

 需要调入新的页面时，将新页面内容读入到空闲页面链表的第一

项所指的页面，然后将第一项删除。

 空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页

面被再次访问，这些页面还在内存中。

 当已修改页面达到一定数目后，再将它们一起调出到外存，然后

将它们归入空闲页面链表。

 VAX/VMS系统使用

 Windows、Linux页面置换算法是基于页面缓冲算法。

每个进程需要最少的页数

示例：IBM370-6页来处理SS MOVE

指令：

指令是6个字节，可能跨越2页

2 pages to handle from

2 pages to handle to

两大配置方案

固定分配

优先级分配

Equal allocation（平均分配算法）——例如，如果有100帧和5个进程，则给出每个进程20帧。

Proportional allocation （按比例分配算法）——根据进程的大小进行分配

使用使用优先级而不是大小级的比例分配方案

如果进程Pi产生了一个页面故障，

选择替换它的一个帧

从一个优先级号较低的进程中选择替换一个帧

置换策略：

Global replacement（全局置换）——进程从所有帧的集合中选择一个替换帧；一个进程可以从另一个进程中获取一个帧

Local replacement （局部置换）——每个进程只从它自己的已分配的帧集中进行选择

分配策略：

固定分配

可变分配

 组合成三种策略：

 固定分配局部置换策略

 可变分配全局置换策略

 可变分配局部置换

如果一个进程没有“足够”页面，缺页率率非常高。这将导致：

低CPU利用率

操作系统认为它需要提高多重编程的程度

添加到系统中的另一个进程

颠簸=进程正在忙于交换页面

为什么需求分页会工作？

Locality（局部性） model

进程从一个位置迁移到另一个位置

地点可能重叠

颠簸为什么会发生？

近似于间隔计时器+一个引用位

示例：

定时器在每5000个时间单位后中断一次

每个页面在内存中保留2位

每当计时器中断复制并将所有引用位的值设置为0时

如果内存中的一个位=1–>页面在工作集

为什么这并不完全准确呢？

改进= 10位，每1000个时间单位中断一次

建立“可接受的”页面故障率

如果实际速率过低，则流程将丢失帧

如果实际速率过高，则进程获得帧

内存映射的文件I/O允许通过将磁盘块映射到内存中的页面，将文件I/O视为常规内存访问

最初使用需求分页来读取文件。文件的页面大小的部分从文件系统读取到物理页面中。对该文件的后续读写被视为普通内存访问。

通过内存处理文件I/O而不是read（）write（）系统调用来简化文件访问

还允许多个进程映射相同的文件，从而允许在内存中共享相同的页面

处理方式与用户内存不同

通常是从空闲内存池中分配的

内核为不同大小的结构请求内存

某些内核内存需要是连续的

从由物理连续页面组成的固定大小段分配内存

使用2次功率分配器分配的内存

以2为幂的单位满足请求

请求被舍入到下一个最高功率为2

当需要的分配小于可用时，当前块分成两个伙伴，下次功率为2

继续操作，直到适当大小的块可用

替代策略

Slab是一个或多个物理上连续的页面

高速缓存由一个或多个Slab组成

针对每个唯一的内核数据结构的单个缓存

每个高速缓存中都填充了对象——数据结构的实例化

当创建高速缓存时，填充标记为空闲的对象

当存储结构时，被标记为已使用的对象

如果Slab充满已使用的对象，则从空的Slab分配下一个对象

如果没有空的Slab，则分配新的Slab

好处包括没有碎片化，快速的记忆请求满意度

以减少在进程启动时出现的大量页面故障

在引用之前，准备进程需要的全部或部分页面

但是如果准备的页面没有使用，I/O和内存就被浪费了

假设页面有好，并使用页面的α

s * α保存页面的成本是否有错误的>或<，而比预调页s *（1- α）不必要的页面的成本还要高？

α接近零–>预调页损失

页面大小的选择必须考虑到：

碎片

表大小

I/O开销

位置

TLB Reach -可从TLB中访问的内存量

TLB Reach = (TLB Size) X (Page Size)

理想情况下，每个进程的工作集都存储在TLB中

否则就会出现严重的页面错误

增加页面大小

这可能导致碎片的增加，因为并非所有应用程序都需要大的页面大小

提供多个页面大小

这使得需要更大页面大小的应用程序有机会在不增加碎片化的情况下使用它们

I/O锁定-页面有时必须被锁定在内存中西汉姆联今晚比赛预测

考虑I/O-用于从设备复制文件的页面必须被锁定为不能通过页面替换算法选择进行驱逐

使用集群使用需求分页。集群化引入了围绕故障页面的页面

过程被分配给工作集最小和工作集最大

工作集最小值是进程保证在内存中拥有的最小页数

一个流程可以分配多个页面，最多工作集

当系统中的空闲内存量低于阈值时，将执行自动工作集修剪以恢复空闲内存量

工作集修剪将从页面超过其工作集最小值的进程中删除页面

维护要分配故障进程的空闲页面的列表

无限制-开始分页的阈值参数（可用内存量）

增加分页的解除阈值参数

正在交换的中间值阈值参数

分页通过分页输出执行过程进行

页面输出使用修改后的时钟算法扫描页面

扫描率是扫描页面的速率。这一范围从慢扫描到快速扫描

Pageout的调用频率取决于可用的空闲内存的数量

Solaris 2页面扫描仪