长沙雅美个人工具网站
0%

虚拟内存

发表于 更新于 分类于
本文字数： 6k 阅读时长 ≈ 22 分钟

目的

解决计算机系统时常出现内存空间不够用问题

解决办法

覆盖（overlay）

依据程序逻辑结构，将程序划分为若干功能相对独立的模块；将不会同时执行的模块共享同一块内存区域

目标：在较小的可用内存中运行较大的程序

  1. 必要部分（常用功能）的代码和数据常驻内存
  2. 可选部分（不常用功能）放在其他程序模块中,只在需要用到时装入内存
  3. 不存在调用关系的模块可相互覆盖，共用同一块内存区域
    注：不存在相互调用关系可以分成一个覆盖区
    386b045e902bfb625bf3f9548bc73a5c.png

交换（swapping）

操作系统自动把暂时不能执行的程序保存到外存中

目标：增加正在运行或需要运行的程序的内存

换入换出的基本单位（整个进程的地址空间）；

换出（swap out）：把一个进程的整个地址空间保存到外存；

换入（swap in）：将外存中某进程的地址空间读入到内存；

2cfe4c0992acd79d363d67061482bfe0.png

虚拟存储

在有限容量的内存中，以页为单位自动装入更多更大的程序

目标：

  • 只把部分程序放到内存中，从而运行比物理内存大的程序由操作系统自动完成，无需程序员的干涉
  • 实现进程在内存与外存之间的交换，从而获得更多的空闲内存空间在内存和外存之间只交换进程的部分内容
    2bd78289d2db405fa207302a90ad003e.png

思路：将不常用的部分内存块暂存到外存

原理：装载程序时，只将当前指令执行需要的部分页面或段装入内存。指令执行中需要的指令或数据不在内存（称为缺页或缺段）时，处理器通知操作系统将相应的页面或段调入内存，操作系统将内存中暂时不用的页面或段保存到外存

实现方式：虚拟页式存储；虚拟段式存储

基本特征：

  • 不连续性：
    物理内存分配非连续
    虚拟地址空间使用非连续
  • 大用户空间：
    提供给用户的虚拟内存可大于实际的物理内存
  • 部分交换
    虚拟存储只对部分虚拟地址空间进行调入和调出

支持技术：

硬件： 页式或短时存储中的地址转换机制

操作系统： 管理内存和外存间页面或段的换入和换出

内存局部性原理

程序局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域，具体来说，局部性通常有两种形式：时间局部性和空间局部性。

  • 时间局部性：被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。
  • 空间局部性：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。

缺页异常

linux内存管理–缺页异常处理

Linux Page Fault(缺页异常)

Linux的内存管理采用分页管理，使用多级页表，动态地址转换机构与主存、辅存共同实现虚拟内存。即使每个进程有相同的逻辑地址空间，通过分页机制，相应的物理地址也是不同的，因此他们在物理上不会彼此重叠。

从内核角度来看，逻辑地址和物理地址都被划分成为固定大小的页面。每个合法的逻辑页面敲好处于一个物理页面中，方便MMU的地址转换。当地址转换无法完成时(例如由于给定的逻辑地址不合法或由于逻辑页面没有对应的物理页面)，MMU将产生中断，向核心发出信号。Linux核心可以处理这种页面错误(Page Fault)问题。

MMU也负责增强内存保护，当一个应用程序试图在它的内存中队一个已标明是只读的页面进行写操作时，MMU也会产生中断错误，通知内核。在没有MMU的情况下，内核不能防止一个进程非法存取其他进程的内存空间。

每个进程都有一套自己的页目录与页表，其中页目录的基地址是关键，通过它才能查到逻辑所对应的物理地址。页目录的基地址是每个进程的私有资源，保存在该进程的task_struct对象的mm_struct结构变量mm中。

在进程切换时，CPU会把新进程的页目录基地址填入CPU的页目录寄存器，供MMU使用。当新进程有地址访问时，MMU会根据被访问地址的最高10位从页目录中找到对应的页表基地址，然后根据次高10位再从页表中找到对应的物理地址的页首，最后根据剩下的12位偏移量与页首地址找到逻辑地址对应的真正物理地址。

与直接访问物理内存不同，Page Fault过程大部分是由软件完成的，消耗时间比较久，所以是影响性能的一个关键指标。

缺页本身是一种中断，与一般的中断一样，需要经过4个处理步骤：

  1. 保护CPU现场
  2. 分析中断原因
  3. 转入缺页中断处理程序进行处理
  4. 恢复CPU现场，继续执行

但是缺页中断时由于所要访问的页面不存在与内存时，有硬件所产生的一种特殊的中断，因此，与一般的中断存在区别：

  1. 在指令执行期间产生和处理缺页中断信号
  2. 一条指令在执行期间，可能产生多次缺页中断
  3. 缺页中断返回时，执行产生中断的那一条指令，而一般的中断返回时，执行下一条指令

分类

  • 软性
    软性页缺失指页缺失发生时，相关的页已经被加载进内存，但是没有向MMU注册的情况。操作系统只需要在MMU中注册相关页对应的物理地址即可。
    发生这种情况的可能性之一，是一块物理内存被两个或多个程序共享，操作系统已经为其中的一个装载并注册了相应的页，但是没有为另一个程序注册。
    可能性之二，是该页已被从CPU的工作集中移除，但是尚未被交换到磁盘上。比如OpenVMS这样的使用次级页缓存的系统，就有可能会在工作集过大的情况下，将某页从工作集中去除，但是不写入硬盘也不擦除（比如说这一页被读出硬盘后没被修改过），只是放入空闲页表。除非有其他程序需要，导致这一页被分配出去了，不然这一页的内容不会被修改。当原程序再次需要该页内的数据时，如果这一页确实没有被分配出去，那么系统只需要重新为该页在MMU内注册映射即可。
  • 硬性
    与软性页缺失相反，硬性页缺失是指相关的页在页缺失发生时未被加载进内存的情况。
    硬性页缺失导致的性能损失是很大的。以一块7200rpm的主流机械硬盘为例，其平均寻道时间为8.5毫秒，读入内存需要0.05毫秒。相对的，DDR3内存的访问延迟通常在数十到100纳秒之间，性能差距可能会达到8万到22万倍。
    另外，有些操作系统会将程序的一部分延迟到需要使用的时候再加载入内存执行，以此来提升性能。这一特性也是通过捕获硬性页缺失达到的。
    当硬性页缺失过于频繁的发生时，称发生系统颠簸。
    这时操作系统需要：
    1. 寻找到一个空闲的页。或者把另外一个使用中的页写到磁盘上（如果其在最后一次写入后发生了变化的话），并注销在MMU内的记录
    2. 将数据读入被选定的页
    3. 向MMU注册该页
  • 无效
    当程序访问的虚拟地址是不存在于虚拟地址空间内的时候，则发生无效页缺失。一般来说这是个软件问题，但是也不排除硬件可能，比如因为内存故障而损坏了一个正确的指针。
    具体动作与所使用的操作系统有关，比如Windows会使用异常机制向程序报告，而类Unix系统则会使用信号机制。如果程序未处理相关问题，那么操作系统会执行默认处理方式，通常是转储内存、终止相关的程序，然后向用户报告。

触发时间

在linux中，用户空间的内存由VMA(virtual memory areas)结构管理：

292e31b5d809e4812f7710786131d5e1.png

当用户进程进程在一下情形时，会由MMU触发Page Fault中断：

13ba7335eef1922a2c07cab5bcaee497.jpg

  1. 新申请的堆内存（malloc等），由于lazy机制，只建立页表而没有真实物理内存的映射，因此页表里的权限是R，发生Page Fault，在Page Fault回调中，linux会去申请一页内存，此时把页表权限设置为R+W。
  2. 用户访问了非法的内存（例如引用野指针等），MMU就会触发Page Fault中断，回调中检查进程并没有对应这段内存的VMA，给用户进程发送SIGSEGV信号报段错误并终止。
  3. 代码段在VMA中权限为R+X，如果程序中有野指针飞到此区域去写，则也会由MMU触发Page Fault中断，导致用户进程收到SIGSEGV信号。（另，malloc堆区在VMA中权限为R+W，如果程序的PC指针飞到此区域去执行，同样发生段错误。）
  4. 在代码段区域运行执行操作时发生缺页，说明该段代码数据未从磁盘加载，则Linux申请一页内存，并从硬盘读取出代码段，此时产生了IO操作，为major主缺页。

如果按场景划分：

  1. 请求调页: 当进程调用malloc（）之类的函数调用时，并未实际上分配物理内存，而是仅仅分配了一段线性地址空间，在实际访问该页框时才实际去分配物理页帧，这样可以节省物理内存的开销，还有一种情况是在内存回收时，该物理页面的内容被写到了磁盘上，被系统回收了，这时候需要再分配页帧，并且读取其保存的内容。
  2. 写时复制:当fork()一个进程时，子进程并未完整的复制父进程的地址空间，而是共享相关的资源，父进程的页表被设为只读的，当子进程进行写操作时，会触发缺页异常，从而为子进程分配页帧。
  3. 地址范围外的错误:内核访问无效地址，用户态进程访问无效地址等。
  4. 内核访问非连续性地址：用于内核的高端内存映射，高端内存映射仅仅修改了主内核页表的内容，当进程访问内核态时需要将该部分的页表内容复制到自己的进程页表里面。

触发流程

从上面的讲解很容易看出，Page Fault是一个由硬件中断触发的可以由软件逻辑纠正的错误。根据《linux下的中断机制》中的叙述，一个Page Fault的触发流程为：

807dbb2ed3e6d40d4dee7a0e37652afb.png

缺页中断发生时的事件顺序如下：

  1. 硬件陷入内核，在内核堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中。
  2. 启动一个汇编代码例程保存通用寄存器和其他易失的信息，以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。
  3. 当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。
  4. 一旦知道了发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。如果不一致，向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生，系统则检查是否有空闲页框。如果没有空闲页框，执行页面置换算法寻找一个页面来淘汰。
  5. 如果选择的页框“脏”了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。无论如何，该页框被标记为忙，以免因为其他原因而被其他进程占用。
  6. 一旦页框“干净”后（无论是立刻还是在写回磁盘后），操作系统查找所需页面在磁盘上的地址，通过磁盘操作将其装入。该页面被装入后，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行。
  7. 当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态。
  8. 恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。
  9. 调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。
  10. 该例程恢复寄存器和其他状态信息

页面置换算法

最佳置换算法（OPT）（理想置换算法）

这是一种理想情况下的页面置换算法，但实际上是不可能实现的。该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。

先进先出置换算法（FIFO）

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。

这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。

FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。

最近最久未使用（LRU）算法

FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。

LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。

LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：

1.计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做，不仅要查页表，而且当页表改变时（因CPU调度）要维护这个页表中的时间，还要考虑到时钟值溢出的问题。

2.栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。

因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。

一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在最近一段时间里它未被访问过。

Clock置换算法（LRU算法的近似实现）

思路：仅对页面的访问情况进行大致统计

实现：在页表项中增加访问位，描述页面在过去一段时间的内访问情况，将各页面组织成环形链表，指针指向最先调入的页面，访问页面时，在页表项记录页面访问情况，缺页时，从指针处开始顺序查找未被访问的页面进行置换

特点：时钟算法是LRU和FIFO的折中

0965c3d90ea5203a11371ee25276eac9.png

最少使用（LFU）置换算法

在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 ms时间内可能对某页面连续访问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri最小的页。

LFU置换算法的页面访问图与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。

思路：缺页时，置换访问次数最少的页面

实现：每个页面设置一个访问计数，访问页面时，访问计数加1，缺页时，置换计数最小的页面

特点：算法开销大，开始时频繁使用，但以后不使用的页面很难置换

详细的置换过程见下图：执行在4个页帧中，假定最初的访问次数a-＞8 b-＞5 c-＞6 d-＞2

0567fb7b4d667e97236da30d43723d64.png

工作集算法

工作集时钟算法

缺页率置换算法

老化算法（非常类似LRU的有效算法）

NRU(最近未使用）算法

第二次机会算法

第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。

第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。