页式内存管理 - 简介

这是 《Operating System: Three Easy Pieces》 的第 7 篇读书笔记。

有关 页式内存管理 介绍 。

主要介绍的是一种常见的内存管理方式。

操作系统几乎会采取两种方式来应对空间管理的问题。第一种是把空间切成大小完全相等的碎片,第二种就是把空间切分成大小相等的碎片。

第一种方式如前面两篇笔记提到的,所带来的外部碎片管理问题让人头疼,且会随着系统的运行,内存的分配也相当麻烦。
本文讨论第二种方式。

在第二种方式的概念下,被切分了的相同大小的“片”,术语叫做 ( Page )。

从简单的例子开始

我们抽象的地址空间只有 64 字节,切分成相等大小的 4 份,每份 16 字节,从上之下分别标号为 页 0/1/2/3 。

实际使用的物理地址也很小,如 Figure-18.2 所示,但同样也可以被 16 字节所切分。另外,图中的物理地址已被不同地址虚拟空间的内存所占据,而且,操作系统还保留了一部分自用。

分页之后,我们可以直观地看出些优点。

  • 分配和回收的灵活性——直接分配/回收一个 Page ,不用管其他
  • 简单——举例来说,操作系统想要放置我们的 64 字节的一个进程,它只需要找到足够多的 Page 就好(或许得通过一个记录空闲内存的链表,但是不重要),不用再管其他细节。

在这例子中,操作系统已经把 一个进程的虚拟页 0 放置在物理页 3 中,虚拟页 1 在物理页 7,虚拟页 2 在物理页 5,虚拟页 3 在物理页 2。

另外一个问题又来了,操作系统分配给一个进程的页,记录在哪里呢?通常,操作系统会为*每个进程*创建一个叫做 页表 的数据结构(page table)。

页表 主要的作用就是记录 虚拟页到物理页 的地址翻译,让操作系统知道去哪里访问虚拟地址对应的物理地址。

Figure-18.2 的例子中,一个页表可能存在这这样的元组:

  • (Virtual Page 0 -> Physical Frame 3)
  • (VP 1 -> PF 7)
  • (VP 2 -> PF 5)
  • (VP 3 -> PF 2)

看起来是不是很像一个 map ?

现在,我们来看一下如何进行地址翻译:movl <virtual address>, %eax

为了访问那个 virtual address,我们得知道虚拟页的页号,和它在该页中的偏移。然后通过页表知道物理页地址,再加上偏移,即可得到要访问的物理地址了。

拿我们的例子来说,因为我们的虚拟地址大小是 64 字节,所以我们需要 6 字节来存储一个地址(2 ^ 6 = 64)。我们把高 2 位看作页号,低 4 位看作偏移,所以正好,每个页 16 (2 ^ 4)字节,4 (2^2)个页加起来等于 64 字节。

具体给上面的指令一个地址,movl 21, %eax

21 这个地址表示如下:

非常直观地看出,虚拟地址21在虚拟页 1(01)的 5(0101) 字节偏移处。我们查一下上面的页表元组,得知对应的是物理页 7 (二进制 111),所以最终的物理地址二进制格式是 1110101 (十进制的 117)

页表存在哪里?

页表所占的内存可能非常大。

想象一下 32 位地址空间的虚拟内存,20 位的页号,12 位偏移,4 KB 页大小。

20 位大小的页号可以表示 2^20 个 虚拟页->物理页的翻译。假设需要 4 字节表示一个 页表元组(Page Table Entry) 外加其他必要信息,那么一个进程最多需要 4MB 大小的内存来保存页表。
想象下,如果一个操作系统中要同时运行 100 多个进程,那么总共需要的空间将达到 400 多 MB!

这个数字在 64 位系统中将会更加大。

但是,操作系统不会笨到全部把它们放进 MMU 里,通常是放在内存里(操作系统所在的内存/操作系统管理的内存),甚至可以是放在磁盘。

页表里有什么?

最普通的,就是用一个数组来表示页表了。虚拟页的页号作为索引,通过虚拟页页号来索引对应的页表元组(Page Table Entry),从而找到对应的物理页。

在每个 Page Table Entry 里,有一个 valid bit 来表示此元素是否有效。如果访问到了一个 invalid 的页表元组,操作系统可能就会进行必要的错误处理(trap)或者回调。

还有 protection bit,表示此页允许可读、可写、可执行。

另外还有 present bit,表示此页在内存里还是被换出了。

通常还有 dirty bit,表示此页是否被修改过了,常配合一些策略来使用。

reference bit (a.k.a accessed bit) 通常是用来表示此页是否被访问过,搭配一些换页策略而存在。

分页管理模式下的内存访问逻辑

// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT

// Form the address of the page-table entry (PTE)
PTEAddr = PTBR + (VPN * sizeof(PTE))

// Fetch the PTE
PTE = AccessMemory(PTEAddr)

// Check if process can access the page
if (PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
    RaiseException(PROTECTION_FAULT)
else
    // Access is OK: form physical address and fetch it
    offset   = VirtualAddress & OFFSET_MASK
    PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
    Register = AccessMemory(PhysAddr)

总结下,问了访问一次内存,上面的代码必须进行额外的一次 AccessMemory,以便获取到 Page Table Entry。
内存访问是相当耗时的,这额外的一次操作可能会使进程运行速度减慢 1 倍以上。

这就是我们要面临的问题。

总结

这篇简单介绍了分页式内存管理。分页的确有很多优点,优于我们之前介绍过的内存管理方法。但同时也有他自身的问题。

另外,原文还有一节是介绍分页式内存管理方式下,使用内存需要注意的点,我没有翻译,读者感兴趣自己去参考原文的 “A Memory Trace” 一节吧。

参考
《 Introduction to Paging 》

Comments
Write a Comment