《操作系统导论》阅读笔记(十七)完整虚拟内存系统

 2年前     3,300  

文章目录

阅读笔记主要来自 原书 第 23 章。该章以 VMS 和 Linux 为例,对完整的虚拟内存系统进行了详细的介绍。

注:中文翻译的版本只有 VMS 的例子,没有 Linux 的例子(可能是后期更新的)。本文针对相关部分进行了补充(下划线部分还没有完全理解,请见谅...)。

0、前言

在结束虚拟化内存的学习之前,让我们仔细看看整个虚拟内存系统是如何组装在一起的。我们已经看到了这种系统的关键元素,包括大量的页表设计与 TLB 的交互(有时甚至由操作系统自己处理),以及决定哪些页面保留在内存中、哪些页面被踢出的策略。然而,还有许多其他特性组成了一个完整的虚拟内存系统,包括许多针对性能、功能和安全性的特性。因此,关键问题是:

如何构建一个完整的虚拟内存系统?实现一个完整的虚拟内存系统需要哪些特性?他们如何提高性能、增加安全性,或者改善系统?

我们将通过介绍两个系统来做到这一点。第一个是最早的“现代”虚拟内存管理器的例子之一,它出现在 VAX/VMS 操作系统中,开发于 20 世纪 70 年代和 80 年代初;这个系统中惊人数量的技术和方法流传至今,因此非常值得研究。一些想法,即使是 50 年前的想法,仍然值得了解,这是大多数其他领域(例如,物理学)的人都知道的想法,但必须在技术驱动的学科(例如,计算机科学)中陈述。

第二个是 Linux,原因显而易见。Linux 是一个广泛使用的系统,可以有效地运行在从手机到现代数据中心中最具可扩展性的多核系统这样的小而低效的系统上。因此,它的 VM 系统必须足够灵活,以便在所有这些场景中成功运行。我们将讨论每个系统,以说明在前面主题中提出的概念是如何在一个完整的内存管理器中结合在一起的。

1、VAX/VMS 虚拟内存系统

1.1 背景

数字设备公司(DEC)在 20 世纪 70 年代末推出了 VAX-11 小型机体系结构。该架构有许多实现,包括 VAX-11/780 和功能较弱的 VAX-11/750。

相应的操作系统被称为 VAX/VMS(VMS),其主要架构师之一是 Dave Cutler,他后来领导开发了微软 Windows NT。VMS 面临通用性的问题,即它将运行在各种机器上,包括非常便宜的 VAXen,以及同一架构系列中极高端和强大的机器。因此,操作系统必须具有一些机制和策略,适用于这一系列广泛的系统。

附带说一句,VMS 是软件创新的很好例子,用于隐藏架构的一些固有缺陷。尽管操作系统通常依靠硬件来构建高效的抽象和假象,但有时硬件设计人员并没有把所有事情都做好。在 VAX 硬件中,可以看到一些这样的例子,也会看到尽管存在这些硬件缺陷,VMS 操作系统如何构建一个有效的工作系统。

1.2、内存管理硬件

VAX-11 为每个进程提供了一个 32 位的虚拟地址空间,分为 512 字节的页。因此,虚拟地址由 23 位VPN 和 9 位偏移组成。此外,VPN 的高两位用于区分页所在的段。因此,如前所述,该系统是分页和分段的混合体。

地址空间的下半部分称为“进程空间”,对于每个进程都是唯一的。在进程空间的前半部分(P0)中,有用户程序和一个向下增长的堆。在进程空间的后半部分(P1),有向上增长的栈。地址空间的上半部分称为系统空间(S),尽管只有一半被使用。受保护的操作系统代码和数据驻留在此处,操作系统以这种方式跨进程共享。

VMS 设计人员的一个主要关注点是 VAX 硬件中的页大小非常小(512字节)。由于历史原因选择的这种尺寸,存在一个根本性问题,即简单的线性页表过大。因此,VMS设计人员的首要目标之一是确保 VMS 不会用页表占满内存。

系统通过两种方式,减少了页表对内存的压力。首先,通过将用户地址空间分成两部分,VAX-11 为每个进程的每个区域(P0 和 P1)提供了一个页表。因此,栈和堆之间未使用的地址空间部分不需要页表空间。基址和界限寄存器的使用与你期望的一样。一个基址寄存器保存该段的页表的地址,界限寄存器保存其大小(即页表项的数量)。

其次,通过在内核虚拟内存中放置用户页表(对于 P0 和 P1,因此每个进程两个),操作系统进一步降低了内存压力。因此,在分配或增长页表时,内核在段 S 中分配自己的虚拟内存空间。如果内存受到严重压力,内核可以将这些页表的页面交换到磁盘,从而使物理内存可以用于其他用途。

将页表放入内核虚拟内存意味着地址转换更加复杂。例如,要转换 P0 或 P1 中的虚拟地址,硬件必须首先尝试在其页表中查找该页的页表项(该进程的 P0 或 P1 页表)。但是,在这样做时,硬件可能首先需要查阅系统页表(它存在于物理内存中)。随着地址转换完成,硬件可以知道页表页的地址,然后最终知道所需内存访问的地址。幸运的是,VAX 的硬件管理的 TLB 让所有这些工作更快,TLB 通常(很有可能)会绕过这种费力的查找。

1.3、一个真实的地址空间

研究 VMS 有一个很好的方面,我们可以看到如何构建一个真正的地址空间,如下图所示。到目前为止,我们一直假设了一个简单的地址空间,只有用户代码、用户数据和用户堆,但正如我们上面所看到的,真正的地址空间显然更复杂。

《操作系统导论》阅读笔记(十七)完整虚拟内存系统

例如,代码段永远不会从第 0 页开始。相反,该页被标记为不可访问,以便为检测空指针(null-pointer)访问提供一些支持。因此,设计地址空间时需要考虑的一个问题是对调试的支持,这正是无法访问的零页所提供的

补充:为什么空指针访问会导致段错误

你现在应该很好地理解一个空指针引用会发生什么。通过这样做,进程生成了一个虚拟地址 0:

int *p = NULL; // set p = 0
*p = 10;      // try to store value 10 to virtual address 0

硬件试图在 TLB 中查找 VPN(这里也是0),遇到 TLB 未命中。查询页表,并且发现 VPN 0 的条目被标记为无效。因此,我们遇到无效的访问,将控制权交给操作系统,这可能会终止进程(在 UNIX 系统上,会向进程发出一个信号,让它们对这样的错误做出反应。但是如果信号未被捕获,则会终止进程)。

也许更重要的是,内核虚拟地址空间(即其数据结构和代码)是每个用户地址空间的一部分。在上下文切换时,操作系统改变 P0 和 P1 寄存器以指向即将运行的进程的适当页表。但是,它不会更改 S 基址和界限寄存器,并因此将“相同的”内核结构映射到每个用户的地址空间。

内核映射到每个地址空间,这有一些原因。这种结构使得内核的运转更轻松。例如,如果操作系统收到用户程序(例如,在 write() 系统调用中)递交的指针,很容易将数据从该指针处复制到它自己的结构。操作系统自然是写好和编译好的,无须担心它访问的数据来自哪里。相反,如果内核完全位于物理内存中,则很难将页表的页交换到磁盘。如果内核被赋予了自己的地址空间,那么在用户应用程序和内核之间移动数据将再次变得复杂和痛苦。通过这种构造(现在广泛使用),内核几乎就像应用程序库一样,尽管是受保护的。

关于这个地址空间的最后一点与保护有关。显然,操作系统不希望用户应用程序读取或写入操作系统数据或代码。因此,硬件必须支持页面的不同保护级别才能启用该功能。VAX 通过在页表中的保护位中指定 CPU 访问特定页面所需的特权级别来实现此目的。因此,系统数据和代码被设置为比用户数据和代码更高的保护级别。试图从用户代码访问这些信息,将会在操作系统中产生一个 trap,并且可能会终止违规进程。

1.4、页替换

VAX 中的页表项 PTE 包含以下位:一个有效位,一个保护字段(4位),一个修改(或脏位)位,为OS使用保留的字段(5位),最后是一个物理帧号码(PFN)将页面的位置存储在物理内存中。敏锐的读者可能会注意到:没有引用位!因此,VMS 替换算法必须在没有硬件支持的情况下,确定哪些页是活跃的。

开发人员也担心会有“自私贪婪的内存”—— 一些程序占用大量内存,使其他程序难以运行。到目前为止,所看到的大部分策略都容易受到这种内存的影响。例如,LRU 是一种全局策略,不会在进程之间公平分享内存

1.4.1、分段的 FIFO

为了解决这两个问题,开发人员提出了分段的 FIFO(segmented FIFO)替换策略。想法很简单:每个进程都有一个可以保存在内存中的最大页数,称为驻留集大小(RSS)。每个页都保存在 FIFO 列表中。当一个进程超过其 RSS 时,“先入”的页被驱逐。FIFO 显然不需要硬件的任何支持,因此很容易实现。

正如我们前面看到的,纯粹的 FIFO 并不是特别好。为了提高 FIFO 的性能,VMS 引入了两个二次机会链表(second-chance list),页在从内存中被踢出之前被放在其中。具体来说,是全局的干净页空闲链表和脏页链表。当进程 P 超过其 RSS 时,将从其 FIFO 中移除一个页。如果干净(未修改),则将其放在干净页链表的末尾。如果脏(已修改),则将其放在脏页链表的末尾。

如果另一个进程 Q 需要一个空闲页,它会从全局干净链表中取出第一个空闲页。但是,如果原来的进程 P 在该页被回收之前出错,则 P 会从空闲(或脏)链表中回收,从而避免昂贵的磁盘访问。这些全局二次机会链表越大,分段的 FIFO 算法越接近 LRU。

1.4.2、页聚集

VMS 采用的另一个优化也有助于克服 VMS 中的小页面问题。具体来说,对于这样的小页面,交换过程中的硬盘 I/O 可能效率非常低,因为硬盘在大型传输中效果更好。为了让交换 I/O 更有效,VMS 增加了一些优化,但最重要的是聚集。通过聚集,VMS 将大批量的页从全局脏列表中分组到一起,并将它们一举写入磁盘(从而使它们变干净)。聚集用于大多数现代系统,因为可以在交换空间的任意位置放置页,所以操作系统对页分组,执行更少和更大的写入,从而提高性能

补充:模拟引用位

事实证明,你不需要硬件引用位,就可以了解系统中哪些页在用。事实上,在 20 世纪 80 年代早期,Babaoglu 和 Joy 表明,VAX 上的保护位可以用来模拟引用位。其基本思路是:如果你想了解哪些页在系统中被活跃使用,请将页表中的所有页标记为不可访问(但请注意关于哪些页可以被进程真正访问的信息,也许在页表项的“保留的操作系统字段”部分)。当一个进程访问一页时,它会在操作系统中产生一个 trap。操作系统将检查页是否真的可以访问,如果是,则将该页恢复为正常保护(例如,只读或读写)。在替换时,操作系统可以检查哪些页仍然标记为不可用,从而了解哪些页最近没有被使用过。这种引用位“模拟”的关键是减少开销,同时仍能很好地了解页的使用。标记页不可访问时,操作系统不应太激进,否则开销会过高。同时,操作系统也不能太被动,否则所有页面都会被引用,操作系统又无法知道踢出哪一页。

1.5、其他漂亮的虚拟内存技巧

VMS 有另外两个现在成为标准的技巧:按需置零和写时复制。现在描述这些惰性优化。

VMS(以及大多数现代系统)中的一种懒惰形式是页的按需置零。为了更好地理解这一点,我们来考虑一下在你的地址空间中添加一个页的例子。在一个初级实现中,操作系统响应一个请求,在物理内存中找到页,将该页添加到你的堆中,并将其置零(安全起见,这是必需的。否则,你可以看到其他进程使用该页时的内容),然后将其映射到你的地址空间(设置页表以根据需要引用该物理页)。但是这种简单的实现可能是昂贵的,特别是如果页没有被进程使用。

利用按需置零,当页添加到你的地址空间时,操作系统的工作很少。它会在页表中放入一个标记页不可访问的条目。如果进程读取或写入页,则会向操作系统发送 trap。在处理 trap 时,操作系统注意到(通常通过页表项中“保留的操作系统字段”部分标记的一些位),这实际上是一个按需置零页。此时,操作系统会完成寻找物理页的必要工作,将它置零,并映射到进程的地址空间。如果该进程从不访问该页,则所有这些工作都可以避免,从而体现按需置零的好处。

提示:惰性

惰性可以使得工作推迟,但出于多种原因,这在操作系统中是有益的。首先,推迟工作可能会减少当前操作的延迟,从而提高响应能力。例如,操作系统通常会报告立即写入文件成功,只是稍后在后台将其写入硬盘。其次,更重要的是,惰性有时会完全避免完成这项工作。例如,延迟写入直到文件被删除,根本不需要写入。

VMS 有另一个很酷的优化(几乎每个现代操作系统都是这样),写时复制(copy-on-write,COW)。这个想法至少可以回溯到 TENEX 操作系统,它很简单:如果操作系统需要将一个页面从一个地址空间复制到另一个地址空间,不是实际复制它,而是将其映射到目标地址空间,并在两个地址空间中将其标记为只读。如果两个地址空间都只读取页面,则不会采取进一步的操作,因此操作系统已经实现了快速复制而不实际移动任何数据。

但是,如果其中一个地址空间确实尝试写入页面,就会陷入操作系统。操作系统会注意到该页面是一个 COW 页面,因此(惰性地)分配一个新页,填充数据,并将这个新页映射到出错进程的地址空间。该进程然后继续,现在有了该页的私人副本。

COW 之所以有用,有很多原因。当然,任何类型的共享库都可以通过写时复制,映射到许多进程的地址空间中,从而节省宝贵的内存空间。在 UNIX 系统中,由于 fork() 和 exec() 的语义,COW 更加关键。你可能还记得,fork() 会创建调用者地址空间的精确副本。对于大的地址空间,这样的复制过程很慢,并且是数据密集的。更糟糕的是,大部分地址空间会被随后的 exec() 调用立即覆盖,它用即将执行的程序覆盖调用进程的地址空间通过改为执行写时复制的 fork(),操作系统避免了大量不必要的复制,从而保留了正确的语义,同时提高了性能。

2、Linux 虚拟内存系统

2.1、背景

我们现在将讨论 Linux VM 系统的一些更有趣的方面。Linux 开发是由解决生产中遇到的实际问题的工程师推动的,因此大量功能慢慢地被整合到现在功能齐全、功能丰富的虚拟内存系统中。

虽然我们无法讨论 Linux VM 的每个方面,但我们将讨论最重要的方面,特别是它超出了传统虚拟机系统(如VAX/VMS)的范畴。我们还将努力强调 Linux 和旧系统之间的共性。

在本次讨论中,我们将重点讨论针对 Intel x86 的 Linux。虽然 Linux 可以而且确实在许多不同的处理器架构上运行,但 x86 上的 Linux 是最主要和最重要的部署,因此是我们关注的焦点。

2.2、Linux 地址空间

与其他现代操作系统以及 VAX/VMS 非常相似,Linux 虚拟地址空间由用户部分(用户程序代码、堆栈、堆和其他部分所在位置)和内核部分(内核代码、堆栈和堆以及其他部分所在位置)组成。与其他系统一样,在上下文切换时,当前运行的地址空间的用户部分改变;内核部分在进程之间是相同的;以用户模式运行的程序无法访问内核虚拟页面;只有进入内核并转换到特权模式,才能访问这样的内存。

在经典的 32 位 Linux(即具有 32 位虚拟地址空间的 Linux)中,地址空间的用户和内核部分之间的分离发生在地址 0xC0000000 处,即地址空间的四分之三。因此,虚拟地址 0 到 0xBFFFFFFF 是用户虚拟地址;剩余的虚拟地址(0xC0000000 到 0xFFFFFFFF)位于内核的虚拟地址空间中。6 4位Linux有一个类似的分割,但有些许不同。下图显示了典型(简化)地址空间的描述。

《操作系统导论》阅读笔记(十七)完整虚拟内存系统

Linux 的一个稍微有趣的方面是它包含两种类型的内核虚拟地址。第一种称为内核逻辑地址。这就是内核的正常虚拟地址空间;为了获得这种类型的更多内存,内核代码只需要调用 kmalloc。大多数内核数据结构都存在于此,如页表、每个进程的内核栈等。与系统中的大多数其他内存不同,内核逻辑内存不能交换到磁盘

内核逻辑地址最有趣的方面是它们与物理内存的连接。具体而言,内核逻辑地址和物理内存的第一部分之间存在直接映射。因此,内核逻辑地址 0xC0000000 转换为物理地址 0x00000000,0xC0000FFF转换为 0x00000FFF,依此类推。这种直接映射有两个含义。第一,在内核逻辑地址和物理地址之间来回转换很简单;因此,这些地址通常被视为实际上是物理地址第二,如果一块内存在内核逻辑地址空间中是连续的,那么它在物理内存中也是连续的。这使得在内核地址空间的这一部分中分配的内存适合于需要连续物理内存才能正常工作的操作,例如 I/O 通过直接内存访问(DMA)转移到设备。

另一种类型的内核地址是内核虚拟地址。 为了获得这种类型的内存,内核代码称为不同的分配器 vmalloc,该分配器将指针返回到所需大小的几乎连续区域。 与内核逻辑内存不同,内核虚拟内存通常不连续。 每个内核虚拟页面都可以映射到非连续的物理页面(因此不适合 DMA)。 但是这种内存更容易分配,因此用于大型缓冲区,在大型缓冲区中,找到大部分物理记忆将具有挑战性。

在 32 位 Linux 中,存在内核虚拟地址的另一个原因是,它们使内核能够寻址超过(大致)1GB 的内存。几年前,机器的内存比这少得多,允许访问超过 1GB 的内存也不是问题。然而,随着技术的进步,很快就需要使内核能够使用更多的内存。内核虚拟地址及其与物理内存的严格一对一映射的断开使得这成为可能。然而,随着迁移到 64 位 Linux,这种需求就不那么迫切了,因为内核并不局限于最后 1GB 的虚拟地址空间。

2.3、页表结构

因为我们关注的是 x86 平台的 Linux,所以我们的讨论将集中在 x86 提供的页表结构的类型上,因为它决定了 Linux 可以做什么和不能做什么。如前所述,x86 提供了硬件管理的多级页表结构,每个进程有一个页表;操作系统只需在其内存中设置映射,在页面目录的开始处指向一个特权寄存器,其余部分由硬件处理。正如预期的那样,操作系统参与进程创建、删除和上下文切换,确保硬件 MMU 在每种情况下都使用正确的页面表来执行翻译。

最近几年最大的变化可能是从 32 位 x86 迁移到 64 位 x86,正如上面提到的。就像在 VAX/VMS 系统中看到的,32 位地址空间已经存在了很长时间,随着技术的变化,它们最终成为了程序的限制。虚拟内存使系统编程变得很容易,但对于包含许多 GB 内存的现代系统来说,32 位已不足以表示每个系统。因此,下一个飞跃成为必要。

移动到 64 位地址会以预期的方式影响 x86 中的页表结构。因为 x86 使用多级页表,所以当前的 64 位系统使用四级页表。然而,虚拟地址空间的完整 64 位特性尚未使用,而仅使用底部 48 位。因此,虚拟地址可以如下所示:

《操作系统导论》阅读笔记(十七)完整虚拟内存系统

如图中所示,虚拟地址的前 16 位未使用(因此在转换中不起作用),后 12 位(由于页面大小为 4KB)用作偏移量(因此仅直接使用,未转换),留下虚拟地址的中间36位参与转换。地址的 P1 部分用于索引到最上面的页面目录,并且转换从那里开始,一次一级,直到页面表的实际页面被 P4 索引,产生所需的页表条目 PTE。

随着系统内存越来越大,这一庞大地址空间的更多部分将被启用,从而导致五级以及最终六级的页表树结构。想象一下:一个简单的页表查找需要六个级别的转换,仅仅是为了找出某个数据在内存中的位置。

2.4、大页支持

Intel x86 允许使用多种页面大小,而不仅仅是标准的 4KB 页面。具体而言,最近的设计在硬件上支持2MB 甚至 1GB 页面。因此,随着时间的推移,Linux 已经发展到允许应用程序使用这些巨大的页面(huge pages,巨页)。

如前所述,使用巨页可以带来许多好处。比如减少了页表中所需的映射数量:页面越大,映射越少。然而,页表条目 PET 较少并不是巨页背后的驱动力;相反,它具有更好的 TLB 行为和相关性能增益。

当进程积极使用大量内存时,它会很快用转换填满 TLB。如果这些转换是针对 4KB 页面的,那么只有少量的内存可以被访问而不会导致 TLB 未命中。对于在具有许多 GB 内存的机器上运行的现代“大内存”工作负载,其结果是显著的性能代价,最近的研究表明,一些应用程序花费 10% 的周期来处理TLB 未命中。

通过使用较少的 TLB 槽(slots),大页面允许进程访问大量内存,而不会出现 TLB 未命中,因此这是主要优势。然而,大页面还有其他好处:TLB 未命中的路径更短,这意味着当发生 TLB 未命中时,它可以更快地得到服务。此外,分配可以非常快(在某些情况下),这是一个很小但有时很重要的好处。

提示:考虑渐进主义

生活中很多时候,你被鼓励去做一个革命者。“胸怀大志!”,他们说。“改变世界!”,他们尖叫。你可以看到为什么它有吸引力;在某些情况下,需要进行大的变革,因此大力推动变革是非常有意义的。如果你试着这样做,至少他们不会再对你大喊大叫了。

然而,在许多情况下,更慢、更渐进的方法可能是正确的做法。本章中的 Linux 巨型页面示例是工程渐进主义的一个示例;开发人员没有采取原教旨主义者的立场,坚持巨页是未来的发展方向,而是采取了一种审慎的方法,首先引入对它的专门支持,更多地了解它的优点和缺点,只有在真正有理由的情况下,才为所有应用程序添加更通用的支持。

渐进主义虽然有时遭到蔑视,但往往导致缓慢、深思熟虑和明智的进步。在构建系统时,这种方法可能正是您需要的。事实上,在生活中也可能如此。

Linux 支持巨大页面的一个有趣方面是它是如何增量完成的。起初,Linux 开发人员知道这种支持只对少数应用程序很重要,例如具有严格性能要求的大型数据库。因此,决定允许应用程序显式请求大页面的内存分配(通过 mmap() 或 shmget() 调用)。这样,大多数应用程序将不受影响(并继续只使用 4KB 页面;一些要求苛刻的应用程序将不得不更改以使用这些接口,但对他们来说,这是值得的。

# 查看系统中 huge pages 相关信息
# 页的大小为 2MB(Hugepagesize),系统中目前有 0 个巨页(HugePages_Total)

ubuntu@EXP:~$ grep Huge /proc/meminfo 
AnonHugePages:         0 kB
ShmemHugePages:        0 kB
FileHugePages:         0 kB
HugePages_Total:       0
HugePages_Free:        0
HugePages_Rsvd:        0
HugePages_Surp:        0
Hugepagesize:       2048 kB
Hugetlb:               0 kB

最近,由于许多应用程序对更好的 TLB 行为的需求越来越普遍,Linux 开发人员增加了透明的巨大页面支持。启用此功能后,操作系统会自动寻找分配巨大页面的机会(通常为 2 MB,但在某些系统上为 1GB),而无需修改应用程序。

巨页并非没有成本。最大的潜在成本是内部碎片,也就是说,页面很大但很少被使用。这种形式的浪费可能会导致大而很少使用的页面填满内存。如果启用了交换,它也不能很好地处理大页面,有时会大大增加系统的I/O量。分配的开销也可能很糟糕(在某些情况下)。总的来说,有一点是明确的:多年来为系统提供良好服务的 4KB 页面大小不再是通用的解决方案不断增长的内存大小要求我们将大页面和其他解决方案视为 VM 系统必要发展的一部分。Linux 对这种基于硬件的技术的缓慢采用证明了即将发生的变化。

2.5、页面缓存

为了降低访问持久存储(磁盘)的成本,大多数操作系统都使用主动缓存子系统来将流行的数据项保存在内存中。在这方面,Linux 与传统操作系统没有什么不同。

Linux 页面缓存是统一的,将主要来自三个来源的页面保存在内存中:内存映射文件文件数据和来自设备的元数据(通常通过将 read() 和 write() 调用定向到文件系统进行访问),以及组成每个进程的堆和栈页面(有时称为匿名内存,因为它下面没有命名文件,而是交换空间)。这些实体保存在页面缓存哈希表中,允许在需要这些数据时进行快速查找

页面缓存 跟踪 条目是否干净(读取但未更新)或脏(即修改)。后台线程(称为 pdflush)定期将脏数据写入备份存储(即将文件数据写入特定文件,或为匿名区域交换空间),从而确保修改后的数据最终写入持久存储。此后台活动发生在特定时间段之后,或者如果太多页面被认为是脏的(两个都是可配置参数)。

在某些情况下,系统内存不足,Linux 必须决定从内存中清除哪些页面以释放空间。为此,Linux 使用了一种修改形式的 2Q 替换,我们在这里描述。

基本思想很简单:标准 LRU 替换是有效的,但可以被某些常见的访问模式破坏。例如,如果一个进程重复访问一个大文件(尤其是接近内存大小或更大的文件),LRU 会将所有其他文件踢出内存。更糟糕的是:在内存中保留这个文件的部分是没有用处的,因为它们在被从内存中删除之前从未被重新引用过

Linux 版本的 2Q 替换算法通过保留两个链表并在它们之间划分内存来解决这个问题。当第一次访问时,一个页面被放置在一个队列中(在原始文件中称为 A1,但在 Linux 中为非活动链表);当它被重新引用时,页面被提升到另一个队列(在原来的队列中称为 Aq,但在 Linux 中称为活动链表)。当需要更换时,将从非活动链表中选择更换的候选页面。Linux 还定期将页面从活动链表底部移动到非活动链表,使活动链表保持在页面缓存总大小的大约三分之二

理想情况下,Linux 将以完美的 LRU 顺序管理这些链表,但如前所述,这样做成本高昂。因此,与许多操作系统一样,使用 LRU 的近似值(类似于时钟替换)。

这种 2Q 方法通常表现得有点像 LRU,但主要是通过将循环访问的页面限制到非活动链表来处理发生循环大文件访问的情况。因为所述页面在被踢出内存之前从未被重新引用,所以它们不会清除活动链表中找到的其他有用页面。

补充:无处不在的内存映射

内存映射比 Linux 早几年出现,在 Linux 和其他现代系统的许多地方都使用内存映射。其思想很简单:通过在已经打开的文件描述符上调用 mmap(),进程将返回一个指向虚拟内存区域开头的指针,文件的内容似乎就位于该区域。然后使用该指针,进程就可以通过简单的指针解引用访问文件的任何部分。

对内存映射文件中尚未被放入内存的部分的访问会触发页面错误,这时操作系统将对相关数据分配物理页面,并通过更新进程的页面表使其可访问(即按需分页)。

每个常规的 Linux 进程都使用内存映射文件,即使 main() 中的代码不会直接调用 mmap(),考虑 Linux 是如何将代码从可执行文件和共享库代码加载到内存中的。下面是 pmap 命令行工具的输出(非常简短),它显示了运行程序(在本例中是shell, tcsh)的虚拟地址空间由哪些不同的映射组成。输出显示了四列:映射的虚拟地址,它的大小,区域的保护位和映射的源:

0000000000400000 372K r-x-- tcsh
00000000019d5000 1780K rw--- [anon ]
00007f4e7cf06000 1792K r-x-- libc-2.23.so
00007f4e7d2d0000 36K r-x-- libcrypt-2.23.so
00007f4e7d508000 148K r-x-- libtinfo.so.5.9
00007f4e7d731000 152K r-x-- ld-2.23.so
00007f4e7d932000 16K rw--- [stack ]

从这个输出中可以看到,tcsh 二进制文件中的代码,以及 libc、libcrypt、libtinfo 中的代码和动态链接器本身(ld.so)中的代码都映射到地址空间中。还有两个匿名区域,堆(第二个条目,标记为 anon)和栈(标记为 stack)。内存映射文件为操作系统构建现代地址空间提供了一种直接有效的方法。

2.6、安全和缓冲区溢出

现代虚拟机系统(Linux、Solaris 或其中一种 BSD 变体)与传统 VM 系统之间最大的区别可能在于现代对安全性的强调。保护一直是操作系统的一个严重问题,但随着机器之间的互联程度比以往任何时候都高,开发人员采用各种防御措施来阻止那些狡猾的黑客获得对系统的控制也就不足为奇了。

缓冲区溢出攻击是一个主要的威胁,它可以用于普通的用户程序,甚至是内核本身。这些攻击的思想是在目标系统中找到一个漏洞,让攻击者将任意数据注入目标的地址空间。这样的漏洞有时会出现,因为开发人员(错误地)假设输入不会太长,因此(可信地)将输入复制到缓冲区。因为输入实际上太长了,它会溢出缓冲区,从而覆盖目标的内存。以下代码可能是问题的根源:

int some_function(char *input) {
    char dest_buffer[100];
    strcpy(dest_buffer, input); // oops, unbounded copy!
}

在许多情况下,这种溢出不是灾难性的,例如,无意中给用户程序甚至操作系统的错误输入可能会导致其崩溃,但不会更糟。然而,恶意程序员可以精心设计溢出缓冲区的输入,以便将自己的代码注入目标系统,基本上允许他们接管并执行自己的指令。如果在网络连接的用户程序上成功,攻击者可以在受损系统上运行任意计算,甚至出租周期(rent out cycles)【放弃时间片?】;成功攻击操作系统本身,攻击可以访问更多的资源,这是一种所谓的特权升级(即用户代码获得内核访问权限)。如果你猜不到,这些都是坏事。

防止缓冲区溢出的第一个也是最简单的防御措施是防止在地址空间的某些区域(例如,在栈内)内找到的任何代码的执行。NX位(用于No-eXecute),AMD 在其 x86 版本中引入的 NX 位(用于无执行)就是这样一种防御措施(类似的 XD 位现在在 Intel 上可用);它只是阻止在相应的页表项中设置了此位的任何页执行。该方法阻止了攻击者注入到目标堆栈中的代码被执行,从而缓解了问题。

然而,聪明的攻击者非常聪明,即使攻击者无法显式添加注入的代码,恶意代码也可以执行任意代码序列。这个想法以其最普遍的形式被称为面向返回编程(ROP),它确实非常出色。ROP 背后的观察是,在任何程序的地址空间中都有大量的代码位(在 ROP 术语中称为小工具),尤其是与大量 C 库链接的 C 程序。因此,攻击者可以覆盖堆栈,使得当前执行的函数中的返回地址指向所需的恶意指令(或一系列指令),然后是返回指令。通过将大量小工具串在一起(即确保每个返回跳转到
下一个小工具),攻击者可以执行任意代码。太神了。

为了防御 ROP(包括其早期形式,返回到 libc 攻击),Linux 以及其他系统添加了另一种防御,称为地址空间布局随机化ASLR)。操作系统不是将代码、堆栈和堆放置在虚拟地址空间内的固定位置,而是将它们的放置随机化,因此,设计实现此类攻击所需的复杂代码序列非常具有挑战性。因此,对易受攻击的用户程序的大多数攻击都会导致崩溃,但无法控制正在运行的程序。

有趣的是,你可以很容易地在实践中观察到这种随机性。下面是一段在现代 Linux 系统上演示它的代码:

int main(int argc, char *argv[]) {
    int stack = 0;
    printf("%p\n", &stack);
    return 0;
}

这段代码只是打印出堆栈上变量的(虚拟)地址。在较旧的非 ASLR 系统中,该值每次都相同。但是,正如您在下面看到的,该值随每次运行而变化:

ubuntu@EXP:~gcc main.c -o main
ubuntu@EXP:~ ./main 
0x7ffff723b824
ubuntu@EXP:~./main 
0x7ffce59ab0c4
ubuntu@EXP:~ ./main 
0x7fff4f7c3cb4

ASLR对于用户级程序来说是一种非常有用的防御机制,它也被纳入了内核中,这一特性被称为内核地址空间布局随机化(KASLR)。然而,正如我们接下来讨论的,内核可能有更大的问题要处理。

2.7、其他安全问题:熔毁和幽灵(Meltdown And Spectre)

就在我们写这些话的时候(2018 年 8月),系统安全的世界已经被两种新的相关攻击彻底颠覆了。第一个叫熔毁,第二个叫幽灵。它们几乎同时被四组不同的研究人员 / 工程师发现,并引发了对计算机硬件和操作系统提供的基本保护的深刻质疑。幽灵被认为是两者中问题较多的一个。

这些攻击的普遍弱点是,现代系统中的 CPU 执行各种疯狂的幕后技巧来提高性能。这一问题的核心是一种称为推测执行的技术,在这种技术中,CPU 猜测哪些指令将在未来很快被执行,并提前开始执行它们。如果猜测正确,程序运行得更快;如果不是,CPU 会撤销它们对体系结构状态的影响(例如,寄存器),再次尝试,这一次将沿着正确的路径进行。

推测的问题是,它往往会在系统的各个部分留下执行的痕迹,例如处理器缓存、分支预测器等。这就是问题所在:正如攻击的作者所展示的,这样的状态会使内存的内容变得脆弱,甚至是我们认为受到 MMU 保护的内存。

因此,增加内核保护的一种方法是从每个用户进程中删除尽可能多的内核地址空间,取而代之的是为大多数内核数据使用一个单独的内核页表(称为内核页表隔离,或 KPTI)。因此,不是将内核的代码和数据结构映射到每个进程中,而是在其中只保留了最基本的最小值;因此,在切换到内核时,现在需要切换到内核页表。这样做可以提高安全性并避免一些攻击载体,但代价是:性能。切换页表的成本很高。啊,安全的代价:便利性和性能

不幸的是,KPTI不能解决上面列出的所有安全问题,只能解决其中的一部分。而简单的解决方案,如关闭推测,将没有什么意义,因为系统将运行慢数千倍。因此,如果您关心系统安全,那么这是一个有趣的时代。

3、小结

现在我们已经从头到尾地复习整个虚拟存储系统。希望大多数细节都很容易明白,因为你应该已经对大部分基本机制和策略有了很好的理解。

您还了解了一些关于 Linux 的知识。虽然这是一个庞大而复杂的系统,但它继承了过去的许多好想法,其中许多我们没有详细讨论的空间。例如,Linux在 fork() 上对页面执行写时延迟复制,从而通过避免不必要的复制来降低开销。Linux 也按需分配零页面(使用 /dev/zero 设备的内存映射),并有一个后台交换守护程序(swapd),用于将页面交换到磁盘以减少内存压力。事实上,VM 充满了从过去汲取的好想法,也包含了许多自己的创新。

版权声明:小傅 发表于 2年前,共 13658 字。
转载请注明:《操作系统导论》阅读笔记(十七)完整虚拟内存系统 | 太傅博客

2 条评论