【OS】操作系统笔记——虚拟内存

内存划分

在早期的操作系统中,往往是由操作系统与当前运行的程序占用了全部的物理内存。

但随着分时系统的出现,时分复用技术开始普及,此时一种比较简陋的做法是每个进程占用所有内存一小段时间,时间到达后将其状态转移到内存,之后切换到其他进程来运行。但显然上述方法太慢了,将内存信息保存到硬盘是一个比较耗时的过程。

于是,我们采用了一种仍将进程信息放在内存中的方式,这样就可以有效地实现时分复用。如下图所示:

地址空间

为了对每个进程所用的内存进行保护,互相隔离,以保证一个进程不能读取到其他进程的内存,因此操作系统提供了地址空间这一抽象,地址空间就是运行的程序所看到的系统中的内存。

地址空间包含了运行中的程序的所有内存状态,包括了:

  • 程序的代码。
  • 保存函数调用信息、局部变量、参数、返回值的栈
  • 管理动态分配,由用户管理内存的堆。

其中堆、栈是会在运行时进行增长或收缩的,为了让它们两者都能增长,将它们分别划分在了地址空间两端,以相反的方式进行增长:

这样的做法实际上就是虚拟内存,运行的程序认为它拥有着很大的地址空间。它可以让运行的进程感知不到内存被虚拟化,就像它拥有自己的私有物理内存一样,而背后的工作都通过操作系统进行管理,来营造这样的假象。

也就是说,我们平时在开发时所获取到的地址实际上只是一个假象,它并不是真正的物理内存地址,只是操作系统为我们提供的一个虚拟的地址,它与物理地址的转换由操作系统进行。

虚拟内存主要有着三个目标:

  1. 透明:让运行的程序认为自己拥有私有的物理内存。
  2. 高效:让虚拟化在时间上和空间上更高效。
  3. 保护:确保进程是受到保护的,不会被其他进程所影响。

我们可以通过地址转换技术,将指令中的虚拟地址转换为数据真正存储的物理地址。

动态重定位(基于硬件)

动态重定位是一种基于硬件的地址转换,它通过 CPU 的 MMU 提供的基址寄存器和界限寄存器,来确保进程只能访问自己的地址空间。

在编写程序的时候可以假设地址空间从 0 开始,而真正执行的时候,操作系统会决定这个程序在物理内存中的实际地址,并记录起始位置在基址寄存器中。

此时物理地址可以通过这样的方式计算:物理地址 = 虚拟地址 + 基址

而界限寄存器在这个过程中提供了访问保护,它确保了进程不会访问超过其值的虚拟地址,否则将触发异常。

操作系统为了支持动态重定位,负责了下面的工作:

  1. 内存管理:在进程创建时为进程分配一块物理内存,在进程回收时回收进程的物理内存。(如通过空闲列表的方式。
  2. 基址/界限管理:对每个进程的基址寄存器和界限寄存器进行保存和恢复(例如放在操作系统保存的进程数据结构中)。
  3. 异常处理:在启动时加载异常处理程序到陷阱表,当进程越界访问内存时触发异常并进行处理。

动态重定位并不够灵活:如果我们将整个进程的地址空间放入物理内存,则栈和堆之间的内存会因为没有使用造成浪费,并且如果剩余的物理内存不够放置完整的地址空间,则进程无法运行

分段

通过分段问题,可以解决前面提到的动态重定位不够灵活的问题。

分段的概念通过将地址空间氛围了许多连续定长的区域,成为,它在 MMU 中引入了不止一个基址寄存器和界限寄存器对,而是每个段对应了一对。

段分为了三种,分别是代码段栈段堆段。通过这种分段的机制可以将不同的段放在不同的物理内存中,而不再占据一个整块的物理内存,从而避免对物理内存的浪费。

而现在还有一个问题就是我们需要知道虚拟地址对应的是哪个段,可以通过虚拟地址的前几位来进行标示,比如有三个段的时候就可以用前两位来标示位于哪个段(如 00 位于代码,01 位于栈,10 位于堆)

同时,由于栈和堆、代码段不同,它是反向增长的。因此我们需要增加一位用于表示段的增长方向。

而后面的剩余部分就可以用来表示偏移量,通过这样的方式硬件就可以先获取前两段从而确定段的类型,根据段的类型获取到对应的基址、界限寄存器,然后进行 物理地址 = 虚拟地址 + 基址 的计算了(对于栈不同),在越界访问内存时会造成段错误

同时,为了节省内存,可以在一些地址空间之间共享同一个段(例如共享代码段),为了支持共享因此加入了一个保护位,它标志了程序是否能够对该段进行写入,从而使得共享的同时避免被被写入。

因此分段的情况下的地址空间的格式为:

操作系统在处理分段时,除了完成对异常的处理、对基址、界限寄存器进行恢复外,还需要对内存进行合理的管理。

分段会导致物理内存出现许多内存碎片,此时有两种做法:

  1. 重新对现有的段进行安排,系统先中止运行的进程,然后对内存进行整理,整理之后再继续运行
  2. 通过空闲列表管理算法,尽量保留大的内存块进行分配,但这些算法无法完全消除内存碎片,只能尽量减少。

分页

分段的方式存在着内存碎片化的问题,可以采用分页的方式。分页将内存分割为了一个个大小固定的单元,每个单元为一个,它对应了物理内存中的一个页帧

为了记录每个虚拟页在物理内存中的位置,操作系统会为每个进程维护一个页表,它为地址空间中的每个页保存了到物理地址到转换,它的表项表示了虚拟页(VP)到物理页帧(PF)的映射关系(但其实还有其他,例如保护位、存在位、参考位)。

虚拟页 VP 物理帧 PF
VP1 PF7
VP2 PF3
VP3 PF9

要通过页表进行地址转换,我们需要知道虚拟页号(VPN)以及偏移量两个值,可以将虚拟页号存储在高位,而低位则存储偏移量。

在地址转换时,我们只需要查询页表,将 VPN 转换为 PFN 即可得到物理地址,不需要对偏移量做改变。

页表需要存储每个页对物理页帧的映射,因此非常大。因此我们往往不存储在 MMU 中,而是将其存储在内存中(甚至交换到硬盘中)。

但这样简单的分页虽然解决了内存碎片化问题,但仍存在着两个问题:

  1. 运行速度慢,相比 MMU 的存储,从内存中获取实际上相对来说是比较慢的
  2. 占用内存过大,有些页并没有用到,但仍然会对内存进行占用。

快速地址转换 TLB

为了解决分页的速度慢的问题,引入了一种 TLB 的存储结构,它实际上就是对频繁发生的 VPN 到 PFN 转换的硬件缓存,对于每次内存缓存,首先都会先检查 TLB,若没有再去查找页表。

实际上 TLB 的设计就是基于时间局部性。如果访问了一个页,则接下来很有可能再次访问这个页。如一个数组中可能某几个元素处于同一页中,那么遍历时就可以通过 TLB 使得地址转换的速度更快。

对于 TLB 未命中的处理,现在往往是会抛出一个异常,之后操作系统跳转到陷阱处理程序,该处理程序会查找页表,然后更新 TLB,之后从陷阱返回,硬件会对指令进行重试,从而得到转换后的物理地址。

TLB 往往是 VPN | PFN | 其他位 这样的形式,其他位包含了保护位、有效位等。

在进程切换时,由于 TLB 清空的效率太低,因此不会清空 TLB。为了避免运行的进程读到前一个进程的地址映射,会通过有效位表明当前映射是否有效,在切换上下文时将 TLB 置为无效。

TLB 有一个较小的空间,因此它只能装下一部分的映射,如果 TLB 中有效项已经填满,就需要对缓存进行替换,此时会有不同的替换策略,往往会使用 LRU 策略。

减少页表空间

更大的页

我们可以将页的大小设置的更大,这样页表只需要存储较少的项,就可以实现对页表占用空间的减小。但同时页的增大意味着对每页内存的浪费。

段页法混合

对每个逻辑分段(代码、栈、堆)提供页表,同时在 MMU 中存储基址、界限寄存器,这些寄存器不再用于指向具体的段,而是指向页表。也就是用段的方式来对页表进行管理,用页表来实现地址转换。需要将地址的前两位用于表示属于哪种段(哪种页表)。

这种杂合首先会导致碎片再次出现,其次如果有大而稀疏的堆,仍然会导致页表的浪费。

多级页表

这种方法主要的目的是去除页表中无效的区域。它将页表分为了页大小的单元,若整页的页表项均为无效,则不分配对应的页表项。可以通过页目录追踪页表的页是否有效。

多级页表会带来成本:在 TLB 未命中时,需要从内存中加载 N 次(N 为页表级数),并且复杂性也比较高。不过它能显著地减少页表占用的空间,因此已经被广泛的应用,Linux 中就采用了多级页表机制。

超越物理内存

页的硬盘交换

实际上,页不仅仅是常驻在内存中的,为了支持更大的地址空间,操作系统还会超越物理内存,将页存储在硬盘中。在内存不够时,通过对内存页的换出,可以让进程获得更大的可用地址空间。

操作系统为了支持页的还出,会提供一个交换空间。我们可以将内存中的页交换到交换空间中,在需要的时候将其交换回去,它的大小决定了系统能使用的最大内存页数。

操作系统往往会设置高水位线低水位线,从而决定何时从内存中清除页。当操作系统发现可用的页低于低水位线时,会在后台对内存交换。直到有高水位线个可用的页出现。

当我们访问内存时,首先会尝试从 TLB 中查找对应的物理内存映射。若找不到对应的映射,说明发生了缺页,会在内存中通过基址寄存器和界限寄存器找到页表,并通过页表获取对应的 PFN。但如果这个页已经被交换到了硬盘中,则该页的存在位会被标示为无效,此时会抛出一个页错误

操作系统会通过对应的陷阱处理程序对页错误进行处理,它会将对应的页从硬盘交换到内存中,这个页在硬盘中的位置会存在于页表项中,通过它可以找到硬盘中存储的页,之后向硬盘发起请求,将页读取到内存。

将页交换回内存时,如果内存已经满了,则其次是需要将其他的页交换出去,这个页交换的策略有许多种。

交换策略

最优交换策略

最理想的情况下,我们的交换策略是将最远未来将会访问到的页进行换出,这样可以使得最远的将来才会需要进行页交换,从而提高效率。

这种策略是一个最完美的策略,但显然这种方式过于理想,我们无法确定进程在将来会访问页的时间。

FIFO

最简单的策略就是采用 FIFO,将最早进入系统的页进行换出。但这种做法没有考虑页被访问的频率,即使页 0 被频繁访问,它仍然会被换出,效率较低。

随机

通过随机的方式来挑选页并将其换出,显然不够稳定,只能取决于当时的运气。

LRU

LRU 策略是基于 LRU 算法的,它基于局部性原则,将访问时间最早的页进行换出,它在换出页的选择上表现非常不错,最接近于最优的效果。

但 LRU 意味着每次对页进行访问时,都需要对数据更新,从而将页移到列表的前面。这样的记录可能也会影响性能,因此其代价过于昂贵。

近似 LRU

近似 LRU 的做法是加入一个使用位。通过一个时钟指针在开始随机指向一个页,当要换出页的时候检查这个页的使用位,若未使用则将其换出,否则向后移动。当时钟指针移动了一个周期之后,会对所有页的使用位重置。

近似 LRU 算法虽然在换出时的表现不如 LRU,但其不需要考虑历史的访问,目前应用比较广泛。

空闲空间管理

无论是内存分配的 malloc 库还是操作系统对进程的内存分配,在内存分配时,都需要通过一定的空闲内存管理算法对内存进行合理的管理。

分割与合并

大多数分配程序采用了空闲列表的方式对内存进行管理,它是一个链表,链表中的元素记录了哪些空闲的空间还未进行分配。

分割

当进行内存分配时,会通过空闲列表找到足够分配需要的内存的一块空间,将其进行分割,第一块交给用户,第二块仍然留在空闲列表。

合并

当回收内存时,分配程序会将回收的内存重新加入空闲列表。但有时这块回收的内存实际上是可以与前后的内存区域进行合并变成一块更大的可分配区域的。

为了解决这个问题,分配程序往往会在回收内存时对连续的可用空间相合并,成为一块更大的空间。(如果两块空间相临,则合并它们)

管理策略

首次匹配

首次匹配就是在空闲列表中找到第一个足够大的块,将其返回给用户。它的效率高,但会导致空闲列表前面的部分有很多小块的碎片。

下次匹配

与首次匹配类似,但它记录了上一次结束的指针,从上一次结束的位置开始,它在效率高的同时又避免了空闲列表前面的小块碎片问题。

最优匹配

最优匹配策略会遍历整个空闲列表,找到与请求大小相同或更大的空闲块,之后返回候选中最小的一块。但这意味着遍历查找不仅仅是找到可用的块就停止了,需要选出一定的候选。

最差匹配

最差匹配尝试找到最大的块,分割后将剩余的块加入空闲列表,它的表现比较差并且易造成碎片,不常使用。、

分离空闲列表

如果某个应用程序经常申请某一种大小的内存空间,就专门为这种大小的内存空间建立一个空闲列表。例如 Linux 中的 slab 以及 ART 虚拟机中的 rosalloc 都采用了这种方式。

伙伴系统

伙伴系统中,空闲空间被看作了 2^N 的空间,当内存分配时,空闲的空间被递归地一分为二,直至刚好可以满足的大小。当回收内存时,会检查回收的块的伙伴是否可以与其合并,从而递归向上合并。

例如下图就是从 64KB 内存分配 7KB 空间的方式:

####Linux 中的内核内存分配:slab

如果在 Linux 内核中各个部分自己去实现空闲链表的话存在一个问题:无法全局控制。因此 Linux 内核提供了 slab 层(slab 分配器),来作为通用数据结构缓存层的角色。

slab 层将不同的对象划分为了高速缓存组,其中每个高速缓存组存放了不同类型的对象,每种对象类型对应一个高速缓存。(例如 task_struct 类型的高速缓存)。而内核中分配内存的 kmalloc() 建立在了 slab 层之上,使用了同一组通用高速缓存。

而这些高速缓存又被划分为 slab,slab 由一个或多个物理上连续的页组成(一般来说是一页)

每个 slab 都包含了一些对象成员,它有三种状态:满、部分满、空。当内核某部分需要一个新的对象时,先从部分满的 slab 中进行分配,若没有部分满的 slab,则从空的 slab 中进行分配。若仍没有,则会创建一个新的 slab。

高速缓存所对应的结构体为 kmem_cache,这个结构体包含三个链表:slabs_fullslabs_partialslabs_empty,均存放于 kmem_list3 结构体中,分别存放了三种不同状态的 slab。

Linux 中的虚拟内存

Linux 中的虚拟内存为每个进程维护了一个虚拟的地址空间。它将虚拟内存中的划分为了不同的虚拟内存区域,不同的区域存储了不同类型的数据,例如数据、代码、内存映射文件、进程用户空间栈等。

我们知道 Linux 中使用了 task_struct 来存储进程对应的数据结构,而 task_struct 中实际上存放了一个 mm_struct 数据结构,表示内存描述符,它包含了进程地址空间相关的信息。

mm_struct 中,分别通过 mmap 这个链表以及 mm_rb 这个红黑树对 vm_area_struct 这种用于表示前面提到的内存区域的数据进行了存放。实际上 mmapmm_rb 中存放的都是相同的数据,不过 mmap 这种链表格式更利于数据的遍历,而 mm_rb 这种结构更利于数据的查找。通过引入红黑树从而对效率进行优化。

vm_area_struct 中存放了这块虚拟内存区域的信息,包括其在虚拟地址空间中的起始位置 vm_start、在虚拟地址空间中的结束位置 vm_end、该区域的标志 vm_flags 等。

因此,Linux 中对虚拟内存的组织结构大致如图:

当出现缺页的情况时,页错误处理程序就会通过下面的步骤来处理:

  1. 检查该虚拟地址是否合法:会通过 mm_rb 这颗红黑树查找该虚拟地址所对应的 VMA,具体是通过对 vm_startvm_end 进行比较,若最后发现该虚拟地址并不合法,则会抛出一个段错误,终止该进程。
  2. 对内存访问的合法性进行判断:判断进程是否有读写这个区域对应的权限等,若不合法则会排出一个保护错误
  3. 将需要的页换入:当发现对页的访问合法时,操作系统就会通过换出一个页,之后换入对应的页并更新页表。之后硬件会重新执行访问页的指令,此时该页已经存在于内存中,就能够正常的进行地址的转换了。

对于 Linux 的页表,在 2.6 版本中采用了三级页表,在 mm_struct 中存储了全局页目录 pgd_t,全局页目录中存储了中层页目录 pmd_t,而中层页目录中则存储了对应的 pte_t,也就是对应的页表项。

而在后来的版本中,又换为了四级页表,在 pgdpmd 之间插入了上层页目录 pud

image-20191230114659747

Linux 中的内存映射

Linux 中可以通过 mmap 进行内存映射,通过 mmap 可以将磁盘中的文件其他进程的共享对象映射到内存中,对内存的访问就相当于是对映射的对象或文件的访问。它相比普通的读写来说效率更高。

mmap 的核心原理就是将虚拟内存系统应用到文件系统上,将文件当作是内存换出到硬盘的页组成的,通过换入页从而实现更高效的将文件加载到内存。

读入原理

实际上就是通过在建立映射时为它创建一个虚拟内存区域 vm_area_struct,并尝试获取文件的磁盘物理地址,为其建立对应的页表项。此时甚至不会为它分配物理内存,而是一种 copy on access 的思路。当我们访问这块区域的其中一页的时候,会发生页错误,操作系统便会像对待普通的一页一样将对应的文件的『页』换入到内存,并为它分配物理内存。之后在页表中更新后我们就可以获取到这个页的数据了。

写回原理

而关于对映射的内存写入是如何写回磁盘的,实际上是通过 Linux 中的脏页回写机制,系统自动将脏页写回磁盘中,不必再调用 readwrite 等。

为什么快

通常来说常规的文件操作为了提高读写效率,会用到页缓存机制,读文件时先将数据拷贝到页缓存中,对于内核空间中的页缓存用户无法直接访问,因此需要再将页缓存的数据拷贝到用户空间中,写入时也是需要先将 buffer 拷贝到内核空间,再由内核空间写回磁盘。也就是说常规读写都需要两次拷贝
而对于 mmap 只需要通过页换入完成由磁盘到用户空间的一次拷贝即可。也就是说mmap 减少了用户态和内核态之间的拷贝

注意事项

映射区域大小需要为页的整数倍

参考资料

《操作系统导论》(Operating System : Three Easy Pieces

《深入理解计算机系统》(Computer Systems A Programmer's Perspective

《Linux 内核设计与实现》(Linux Kernel Development

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

%d 博主赞过: