虚拟内存¶
虚拟记忆讲座。
什么是虚拟内存？¶
虚拟内存负责操作系统中的许多功能。其中包括：
允许一个或多个程序需要比可用内存更多的字节来继续运行。
通过支持缓冲操作来提高I/O操作的性能。
通过允许进程共享内存页来减少总体内存使用量
管理进程内存保护和沙箱(为进程提供虚拟子机)。
以将虚拟存储器地址转换为物理存储器地址并维护虚拟存储器地址的域。
内存管理单元¶
内存管理单元(以下简称MMU)是一个硬件组件，它负责：
将虚拟地址转换为物理地址
内存保护
转换后备缓冲区
页表条目
在一些现代CPU中，MMU是CPU的一部分。
当处理器有高速缓存未命中并且需要访问一页内存时，它向MMU发出请求
页面和页表¶
每个进程都会获得计算机的一个视图，从而使该进程看起来拥有该计算机的所有可用地址空间。
事实上，这一过程只使用了其中的一部分。操作系统必须在列表中维护正在使用的部件(页)。
页面和页表¶
那么，操作系统中的内存是如何分配的呢？
如果我们分配了128个字节的页面，并且必须维护4 GB的128个字节的页面，我们将需要维护一个列表：
128字节-7位用于寻址，25位用于页面偏移，4 GB/128B=33,554,432个条目*25位=页表条目中的每个进程100MB。
4K字节-12位用于寻址，20位用于页面偏移，4 GB/4K=1,048,576个条目*20位=2.5MB/进程
在32位x86中，条目为32位，因为除了地址之外还需要其他信息。1,048,576*32位=每个进程4MB。
页面和页表¶
即使在4000页的情况下，每个进程的2.5MB也是相当极端的。想象一下，启动一个需要100K内存但有2.5MB开销的进程！想象一下，如果您必须映射超过4 GB的内存！
我们有什么方法可以解决这个问题？
页表条目中有什么？¶
如果我们使用4k页，那么我们需要20位来在4 GB地址空间中寻址这些页(如果我们使用64位地址空间，则需要更多位)
我们还需要知道页面是否具有以下属性：
是可执行的
是可写的
已修改
都在现场
此外，我们可能希望存储有关进程ID、统计数据等的信息……
在32位x86中，我们需要使用32位。20位分配给页面地址，12位分配给我们需要的任何其他地址。
页表条目¶
那么，如果我们需要32位x86上的32位页表条目，我们如何避免拥有如此多的页表条目并产生如此多的开销呢？
关键部分是如何管理32位条目的前20位。我们如何使用这20位？
X86中的解决方案是使用2级或3级页表。
页表条目¶
在2级页表中，前10位用于第一级，第二20位用于第二级。
这不会减少条目的大小，但会减少每个进程需要存储的条目数量。
基本上，这是通过让页表的一个级别管理更大的范围来实现的。如果我们使用10位，则第一级页表映射4MB页，第二级将其划分为4K页。我们只在第二级创建条目，如果存在的话。
两级页表(感谢维基百科)¶
图像¶
MMU-地址转换算法¶
{LANGUAGE=C，BASIC STYLE=，INDENT=xleftMarch}
physical_address translate(virtual_address v_addr) {
physical_address addr;
if(tlb.contains(v_addr)) {
addr = tlb[v_addr];
} else {
first10 = (v_addr >> 0x16) & 0xa;
second10 = (v_addr >> 0xc) & 0xa;
level_1 = page_table_1[first10];
entry = level_1[second10];
physical_page = (v_addr >> 0xc) & 0x14;
if(physical_page >> RESIDENT_OFFSET & 0x01 -- 0)) {
generate page fault
}
addr = (physical_page << 0xc) & (v_addr & 0xc);
tlb[v_addr] = addr;
}
return addr;
}
页面错误¶
在以下情况下，由MMU或由CPU生成页面错误：
指令引用未驻留在物理内存中的虚拟地址。
指令写入不可写的虚拟地址
指令分支/跳转到不可执行的地址
每个操作系统对每种类型的页面错误有不同的实现/反应。
页面错误-Unix¶
非常驻-调用交换程序，如果成功则重试指令，如果失败则由于内存不足而崩溃。
不可写/不可读-向进程发送信号：SIGSEGV。默认情况下崩溃，如果处理，进程不会崩溃
页面错误-Windows¶
非常驻-调用交换程序，如果成功则重试指令。如果失败，则引发异常。
不可写/不可读-引发进程异常。
页面替换/交换¶
为了支持更优化地使用物理内存，操作系统实现了交换器。
交换器是一种将页面从物理内存交换到永久性和较慢存储空间的程序。
交换器是处理堆栈和堆段的页面调入/调出操作的程序。
许多实现还将要求在程序的文本段中分页，以允许在程序完全加载之前开始执行。
页面替换/交换¶
交换程序在以下情况下被调用：
操作系统尝试将虚拟地址转换为物理地址，但物理页面不驻留
操作系统已经耗尽或几乎耗尽了物理内存，需要将物理页面移动到较慢的存储空间。
操作系统已确定将某个内存区域更好地用于其他目的：
对于另一个更活跃的计划
对于文件系统缓存
页面替换/交换¶
谁是纸质页面的竞争者？
数据块/文件系统缓存
操作系统将最近读取/写入的文件保存在内存中
通过允许后写和预读，促进更好的I/O调度决策
提高文件操作性能
共享内存区域/内存映射文件
程序库和可执行文件
程序堆栈和堆段
设备驱动程序DMA(直接内存访问)区域
有些存在于虚拟/物理转换之外
这些区域通常是交换者的禁区。
一些设备实施IO-MMU
交换算法¶
在交换算法中要考虑的关键措施：
页面错误总数-在一段时间内，发生了多少页面错误？
最优页面错误-给定一个最优算法(可以预测未来)，页面错误的最小数量是多少？
B.T.W.对于存在暂停问题的程序，不存在这样的算法。
工作集-程序中最常用和最近使用的一组页面。
交换算法-页面分类¶
大多数计算机记录每个页面是如何被访问的。
通常，大多数硬件在两个位字段中记录页面是否已被读取或修改，并能够重置这些位。这会产生四类页面：
1-未引用、未修改
2-未引用、修改
3-引用，未修改
4-引用、修改
一些硬件实现将周期性地清除读取位，以帮助确定哪些页面最近已被读取。这就是你可以得到上面的2级的方法。
交换器算法-NRU¶
NRU-最近未使用
NRU算法基本上是从具有可用页面的编号最低的类中调出页面。
这是最简单的算法。
交换算法-FIFO¶
FIFO-先进先出
加载页面时，会将其添加到列表的末尾
当发生页面错误并且需要加载新页面时，将移除列表前面的页面并将其换出
FIFO的工作前提是最老的页面在未来最不可能被使用。
这种算法很少使用，因为这种假设经常是错误的
交换算法-第二次机会FIFO¶
第二次机会FIFO通过考虑读取和写入位来改善FIFO调出频繁使用的页面的缺陷
第二次机会FIFO将扫描列表，以查找读/写位均设置为零的页面。如果它在这个类中找到一个页面，它会将该页面换出。如果它找不到这样的页面，它将换出列表中的第一页。
交换器算法-时钟¶
时钟算法在第二次机会FIFO的基础上改进
第二次机会FIFO对其内部名单进行了许多修改。
时钟算法使用循环列表并存储指向最旧页面的指针。当发生页面错误时，将检查所指向的页面。如果其读取位为0，则将其逐出。如果读取位为1，则设置为0，指针前进。
在现实中，时钟算法只比第二次机会先进先出稍好一点。
交换器算法-LRU¶
LRU-最近最少使用
LRU在实践中往往接近最优
LRU假设：
最近被大量使用的页面在不久的将来将被大量使用
近期未使用的页面将不会在近期使用
为了维护实现LRU所需的数据，操作系统必须维护物理内存中所有页面的链接列表。该列表的头部是最近使用的页面，尾部是最近最少使用的页面。这可不便宜。每次访问都需要搜索列表。此外，这份清单可能会很大。
交换器算法-LRU/NFU¶
NFU：不常用-LRU的软件实现
每一页在页表中都有一个计数器。
在每个时钟中断时，OS扫描页表，并且对于读取位=1的每一页，递增计数器
当发生页错误时，计数器最低的页将被逐出
NFU的问题
NFU还不够健忘
如果单个页面访问非常频繁，然后再也不会访问，那么它将需要很长时间才能被驱逐(如果有的话)。
交换算法-LRU/NFU-老化¶
NFU可以通过一种称为老化的方法来改善
NFU+Aging是一种常用算法
老化会略微改变NFU：
当时钟中断发生时，会发生两种情况：
对于读取位设置为1的每一页，设置该页的计数器中的最高有效位。
每页都将其计数器值右移，从而减小计数器值。
交换算法-LRU/NFU-老化¶
当发生页错误时，计数器最低的页被逐出。
该策略更接近于LRU，因为它偏爱最近访问的页面，并通过减少其值来惩罚最近没有访问过的页面。
该算法在两个方面与LRU不同：
计数器中的位数是有限的。这允许两个页面的值为零，但其中一个页面是最近使用的。
该算法被限制为时钟中断的粒度。在两个连续中断之间访问的所有页面都被认为是最近访问的。
贝拉迪畸形¶
一个看似显而易见的假设是，拥有更多的物理页面将减少页面错误的总数。
这一假设并不适用于所有页面替换算法和所有访问模式。
示例-假设有5个虚拟页面，编号从0到4，并使用FIFO通过以下模式访问这些页面：
3 2 1 0 3 2 4 3 2 1 0 4
在这种情况下，拥有3个物理页面将导致9个页面错误，而拥有4个物理页面将导致10个页面错误！
贝拉迪的反常(感谢维基百科)¶
图像¶
贝拉迪畸形¶
对于两种物理内存大小，可以找到比2：1更差的访问顺序
福奈和伊万尼的一篇论文表明，在正确的访问模式下，可以获得任何比率
为页面替换建模¶
在检查特定的页面替换算法时，需要考虑以下几点：
执行进程的引用字符串
内存中可用的页数
引用字符串是来自一个或多个进程的页面访问的时间排序列表。为简单起见，通常只考虑一个流程。
为页面替换建模¶
对页面替换算法进行建模的符号：
M-跟踪内存状态的数组。M有n个元素
N-虚拟页数。
M-分为两部分：前m个条目在物理内存中，最后n-m个条目已被引用但被调出。
当逐个条目地读取引用字符串时，算法检查页面是否在内存中(M的顶部)。
如果不是，则会发生页面错误。如果有空槽(M的顶部)，页面将从底部移到该槽中。
如果M的顶部已满，则调用页面替换算法以从内存中删除页面。
LRU建模¶
这是使用参考字符串0 2 1 3 5 4 6 3 7 7 7 3 3 3 5 5 3 1 1 1 7 7 2 3 4 1建模的LRU算法
图像¶
LRU建模¶
当以这种方式建模时，LRU有一个有趣的属性。
对于LRU，M(m，r)总是M(m+1，r)的子集或等价子集。
这意味着在存储器访问‘r’时，如果存在额外的物理存储器m+1页，则m中的所有页都将存在
这意味着，LRU总是做得很好，或者随着更多的物理页面而改进，并且不会受到Belady异常的影响
建模-距离字符串¶
在这种类型的建模中，另一个有趣的度量是距离字符串。
距离字符串是指从‘堆栈’顶部到页面在堆栈中的位置的距离。
尚未引用的页面将获得无穷大的距离。
距离值取决于参考字符串和算法。
最优算法将最小化距离字符串的值。
建模-距离字符串¶
距离字符串可用于估计不同物理内存大小的页面错误数，公式如下
\($Fm = Sum(k = m+1, n, Ck) + Cinf$\)
\($Ck$\) =k在距离字符串中的出现次数
\($Cinf$\) =距离字符串中出现的无穷大
\($m$\) =物理页数
\($n$\) =虚拟页数
\($Fm$\) =m个物理页面的预测页面故障率
建模-距离字符串¶
图像¶
\($C1 = 4$\), \($C2 = 2$\), \($C3 = 1$\), \($C4 = 3$\), \($C5 = 2$\), \($C6 = 2$\), \($C7 = 1$\), \($Cinf = 8$\)
因此，对于不同的内存大小：
\($F1 = 2+1+3+2+2+1+8 = 19$\)
\($F2 = 1+3+2+2+1+8 = 17$\)
\($F5 = 2+1+8 = 11$\)
\($F6 = 1+8 = 9$\)
寻呼系统的设计考虑因素¶
一个简单的分页实现将启动一个进程，而它的任何页面都不在内存中(库、程序、数据、BSS等)。
当该进程尝试执行其第一条指令时，它会立即生成页面错误。
在程序执行的最初几分钟，它会生成许多页面错误，直到它大部分加载完毕，然后运行时才会生成许多页面错误。
生成许多不必要的错误会导致应用程序性能低下。
工作集¶
虽然不是普遍正确，但许多应用程序表现出引用的局部性。
这意味着，如果一个进程在某个时间点使用给定的页面，那么就在该时间之前和不久的将来，它可能会继续使用该页面和最近的页面(就虚拟地址距离而言)。
许多程序将有一个或多个区域，它们显示了引用的局部性。最常见的情况是，它们将是堆栈或堆中的一个或多个区域。
进程当前使用的页集称为工作集
利用地方性¶
如果我们考虑到位置，我们如何才能使寻呼系统更快？
一些方法：
从库或程序文件加载页面时，会同时加载相邻页面。
通常，在修复一个页面错误后，操作系统可以继续以异步方式加载程序页面。
在选择要逐出的页面时，如果需要逐出一个以上的页面，则OS可以选择逐出与工作集中的任何页面距离最远的页面。
寻呼不同页面类的开销¶
回想一下，前面我们定义了以下几类页面：
1-未引用、未修改
2-未引用、修改
3-引用，未修改
4-引用、修改
这些阶层在驱逐成本方面有所不同。
寻呼不同页面类的开销¶
文本和其他只读页面将始终位于类1或类3中(未修改)
堆栈和堆页面可以是1-4中的任何一个。
当类1或类3中的页(未修改)被逐出时，交换器只需将该页标记为非驻留页，然后将物理页重新用于新条目。
当2类或4类中的页面被逐出时，交换器还必须将该页面的内容复制到不同的存储系统(通常是磁盘)。这增加了驱逐这些页面的成本。
寻呼不同页面类的开销¶
我们如何降低成本？
在后台，当光盘空闲时，我们可以将修改后的页面提交到光盘，以降低未来的成本。
通常，此行为是为可能被逐出的页保留的，而不是工作集中的页。
选择未修改的页面而不是已修改的页面进行逐出。
本地寻呼与全局寻呼¶
在进程调度中，我们尽量做到公平，给每个可运行的进程平均分配CPU(S)。
在我们的页面替换实现中，我们可以做些什么来“公平”呢？
需要考虑的一种可能性是局部页面替换与全局页面替换。
在全局页面替换中，如果进程页面出现故障，我们会考虑将所有内存用于页面驱逐。
在本地页面替换中，我们只考虑导致页面错误的页面的进程来进行页面替换或以其他方式支持它们。
本地页面替换策略可以帮助确保一个导致多个页面错误的进程不会对其他进程造成太多干扰。
本地策略的不利之处在于它可能会损害整体系统性能
页面锁定¶
对于某些操作，我们需要保证页面将保留在物理内存中
最常见的情况是专用于缓冲设备的内存区域或使用DMA的内存区域。
DMA基本上是一种系统，通过该系统，操作系统内核可以告诉设备将操作结果直接写入特定的内存区域，而不直接与CPU交互。
在发生DMA操作期间，操作系统必须保证内存区域不会被交换器逐出。
最好但不太理想的替代方案是只对操作系统缓冲区执行DMA操作，然后将它们复制到程序缓冲区。
COW：写入时复制¶
在Unix中，我们通过调用fork()或clone()来创建进程。
在这两种情况下，都会复制内存区域(从程序的角度来看)。
为避免不必要的复制，操作系统将只复制页表项。
复制页表条目时，它们对于父进程和子进程都被标记为只读。
在复制操作之后，父进程和子进程将共享彼此的物理页面。
COW：写入时复制¶
当对共享页面进行写入操作时，CoW生效。
导致页错误的进程会将物理页的副本复制到新的物理页中，并更新其页表条目以指向该页。
然后，新页面将被标记为可写。
这样，新进程只使用与父进程不同的内存。
后备商店¶
对于堆、堆栈和数据页，大多数操作系统中的后备存储是以下之一：
交换文件
交换分区
在较简单的操作系统中，交换分区更可取，因为操作系统可以直接与磁盘交互，而不是与FS代码交互。
在更高级的操作系统(更高版本的Linux或Windows)中，FS实现足够先进，以至于操作系统可以保证交换文件的扇区位置，从而不会产生使用交换文件的开销。
交换文件具有能够按需调整大小的优势。在Linux中，可以创建其他交换文件，然后与swapon命令一起使用。
Windows自动管理一个或多个交换文件。
冬眠¶
休眠是交换文件的特定实现。
为了休眠，操作系统会将所有使用过的物理页面页调出到光盘上。将使用特殊休眠文件或交换文件。
然后，操作系统将关闭计算机或将计算机置于特殊的低功率状态。
当计算机重新启动时，操作系统将注意到它之前因休眠而关闭。
加载核心操作系统组件后，操作系统将从休眠文件恢复页表，然后开始从休眠文件调入页面。
虚拟机性能-热内存¶
从理论上讲，物理内存的最佳使用方式是尽可能使用所有物理内存。
为了提高需要新内存的操作(读取新文件、写入新数据、向堆或堆栈分配新页面)的性能和响应速度，许多现代的VM实现将始终保留几个空闲页面。
Windows和Linux通常都会保留大约12-16MB的空闲空间作为“热内存”区域。
该热存储器区域具有防止由于存储器使用的“抖动”而导致的页面错误的效果。因此，如果进程正在快速增加和减少其内存使用量，则不太可能生成页面错误。
建模-距离字符串¶
图像¶
在这里，我们可以看到一个长期运行的Linux操作系统。
文件系统缓存使用453388K
软件使用178580K
52704K用作缓冲区
18272K被换出
7972K被保留为“热内存”(或者最近被释放)
摘要：页面错误处理¶
1-硬件中断内核。保存程序计数器和寄存器。重新启动当前指令所需的信息也会被保存。然后调用操作系统。
2-操作系统发现发生页面错误。操作系统检查特殊寄存器或检查从1开始保存的指令，以确定需要哪一页。
3-一旦发现页面，它就会确定页面错误的原因。如果该地址与该进程可访问的访问权限或内存不一致，则向该进程发送信号或终止该进程。
4-如果一致，操作系统会尝试获取空闲的物理页面，以便将必要的页面加载到内存中。如果没有空闲的物理页面，则调用页面替换算法。
摘要：页面错误处理¶
5-如果被逐出的页面是脏的，则计划将其写入光盘。在这种情况下，出错过程进入休眠状态，并发生上下文切换。
6-一旦清除了被收回的页面，操作系统就会安排一个磁盘操作来加载该页面。在等待加载的过程中，出错进程被挂起，调度程序将选择另一个进程运行。
7-页面一从光盘加载，页面表项就会更新以反映其位置，并将页面状态更新为驻留
8-操作系统恢复程序的寄存器，并根据硬件细节重试出错指令，相应地更新程序计数器。
9-然后将出错进程标记为可为调度程序运行。