[What]Introduction to Paging

前面我们将空闲内存最开始分为一个整体,然后用户申请多少就给多少,这最终会导致很多大小各异的内存碎片。

  • 频繁的申请和释放,会生成很多很小的空闲内存碎片,比如就几个字节。这在很多时候无法满足用户申请的内存大小。

另一个方法是将内存空间划分为以页为单位(比如 4KB),虚拟地址空间和物理地址空间都以固定大小的页划分,这样分配的内存最小单位就是页。

  • 相对来讲,这种方式减缓了内存碎片的严重程度。因为空闲内存至少是一个页,在很多时候用户还是可以申请到内存的。

简单的示例

假设一个进程的 address space 是 64 字节,物理内存有 128 字节,并且目前规定的页大小是 16 字节,那么内存映射关系可能如下:

mempic/page/ex_v_1.jpg mempic/page/ex_p_1.jpg

这种分页的方式有如下两点好处:

  1. 按照上一章描述的可变大小空闲内存管理,还得需要使用 best fit、worst fit、first fit等策略以尽量避免内存的浪费。

但现在的都是以固定大小的空闲页面来管理的,那么申请内存的时候我们就可以直接从空闲列表的头取 N 个空闲页面即可。也就是说, 这样简化了空闲内存的申请和管理。

  1. 系统不用关心一个进程是如何使用它的 address space,因为这完全由页映射到对应的物理地址去了。

每个进程都有自己的 address space,那么每个进程都有属于自己的页表(page table),用于存储虚拟地址与物理地址的对应关系。

当 CPU 切换到不同进程时,同时也会切换它的对应的页表。

假设还是上面的 64 字节 address space ,那么需要 6 位来表示其整个地址空间。 并且由于有 4 个页表,那么需要两位来选择页表,剩余的 4 位在页表内部做偏移:

mempic/page/ex_v_2.jpg- VPN:virtual page number

比如在虚拟地址 0x21 处进行读写数据,那么就会取对应1号块页表(从 0 开始)的 5 号偏移处(从 0 开始)的字节:

mempic/page/ex_v_3.jpg

然后这块页表的就会被硬件查找到物理内存的对应地址:

mempic/page/ex_v_4.jpg- PFN: physical frame number,也可以叫做 PPN(physical page number)

可以发现 offset 在虚拟地址和物理地址上是一样的,因为虚拟地址和物理地址页大小是一样的, offset 的主要目的是在页内偏移,所以它们是一样的。

页表放在哪里?

我们先来做个计算,假设 32 位处理器架构上设置的页大小为 4KB,也就是说一个页表项的 offset 可以索引 4096 字节。 那就是说,一个页表项的低 12 位用于页内的 offset,剩余的 20 位用于选择哪一个页表。

那么,最多可以有 2^20 个页表,每个页表 4 字节,那就是说 一个进程的页表会占用 4MB 的空间。

由于一个页表很大,我们也不可能让 MMU 这个硬件来存储一个进程的页表,所以页表是放在内核空间对应的内存上的,而 MMU 上只存储当前页表的基地址。

mempic/page/ex_p_2.jpg

如果操作系统启动 1000 个进程,那么所有进程的页表就要占用大约 4GB 的内存空间,而 32 位系统的最大寻址空间也才 4 GB,这显然是不现实的。

  • 这就是为什么页表需要做多级,多级可以使得页表占用内存大大降低

实际的页表的内容是什么

mempic/page/pgt_1.jpg

上面这个是 X86 构架下的页表格式,页块大小为 4K,之所以用低 12 位存储设置项,就是因为虚拟地址 offset 和物理地址是一样的,所以不需要单独存储。

  • valid bit:用于说明当前页表对应的物理内存是否被映射,当一个进程启动后,很多位置的物理内存都是没有被映射的。没被映射就代表目前该进程没有对此块物理内存的使用权,很好的节省了内存。
    • 如果代码虚拟地址访问到了这块,linux 会根据这块的权限和 VMA 来决定如何操作
    • 当 P 位被设置为 1 时,代表是 valid,当 P 为 0,则还需要操作系统进一步判断。
  • protection bits(R/W):指定这块内存的访问权限,是否可读、可写、可执行
  • present bit(P):指定该块内存是否有对应的硬盘做存储
  • dirty bit(D):这块内存在被映射后,是否已经被修改过
  • reference bit(accessed bit)(A):反应这块内存是否已经被访问过了
    • 如果一个内存块经常被访问,那么系统会将它尽量留在内存中
  • user/supervisor bit(U/S):指定这块内存块是被用户空间使用还是内核空间使用
  • PWT,PCD,PAT,G:设置硬件 cache 对这块内存页的工作方式

MMU 操作也是需要时间的

在执行指令前或操作数据前,CPU 必须要等待 MMU 将其转换为物理地址后,才能从对应的物理地址获取数据或指令,这些都是需要时间的。

MMU 在转换之前,首先需要得到该进程对应页表的基地址,然后才是基于此地址做偏移到对应的内存块:

// 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)
  • VPN_MASK : 页表偏移的掩码
  • SHIFT:是块大小的位数,比如 4KB 块的 SHIFT 为 12
  • OFFSET_MASK : 块内位数的掩码

一个 MMU 的使用实例

假设 32位机上,目前仅有一级页表,并且块大小为 1 KB,接下来执行下面的代码片段:

int array[1000];
for (i = 0; i < 1000; i++)
array[i] = 0;

对应的汇编代码假设如下:

1024 movl $0x0,(%edi,%eax,4) ;将数据 0,写入 edi 存储基地址的 eax 4 倍偏移处
1028 incl %eax ;将索引增加
1032 cmpl $0x03e8,%eax ;索引值与 1000 比较
1036 jne 0x1024 ;如果索引值不等于1000,则跳转到 1024 处继续执行

目前不考虑快表和 cache 等因素,继续做如下假设:

  • 虚拟地址空间 address apace 是 64KB,内存块大小为 1KB
  • 页表的基地址位于物理内存 1KB(1024)处
  • 代码在虚拟地址空间 1024 处,那么除以其块大小,便可知其对应的页表是 1 号(从 0 开始),假设 1号页表对应于物理内存 4 号内存块,也就是说其对应的物理地址是 4096
  • 内存的虚拟地址在 40000 处,那么其地址范围是 40000 ~ 44000(十进制),除以块大小可知其对应页表是 39 ~ 42 号,依次对应物理内存块的 7 ~ 10 号,也就是物理地址起始是 7168
    • 40000 在块内偏移是 64,所以其物理地址是 7 * 1024 + 64 = 7232

最终整个内存的访问情况如下图:

mempic/page/mem_chart.jpg

取 mov 指令

最开始 CPU 要从虚拟地址 1024 处访问代码 mov,MMU 根据此值得到其页表偏移是 1,而页表的基地址是 1024。 然后 MMU 从物理地址 1028 处得到页表 1里存储的物理地址是4096,那么这样就从物理地址 4096 处取得了指令 mov。

此时发生了两次物理内存的访问:

  • 第一次是从物理地址 1028 处页表取得指令存放的物理地址
  • 第二次是从物理地址 4096 处取得指令的内容为 mov

MOV 赋值

MOV 指令从 edi 寄存器 偏移 4 * eax 处得到虚拟地址是 40000,MMU 根据此值得到页表偏移是 39,而页表基地址是 1024. 然后 MMU 从物理地址 1180 处取得页表 39 对应的物理地址是 7168,而且在此基础上偏移 64 字节,最终的数据存放物理地址是 7232

此时发生了两次物理内存访问:

  • 第一次是从物理地址 1180 处页表取得数据存放的物理基地址
  • 第二次是从物理地址偏移 64 字节处取得真正的数据位置,然后写入

接下来的 3 条指令

接下来的 3 条指令访问和取 mov 指令的流程是一样的,页表偏移一样,对应的物理内存块也是一样的,只是在块内有偏移而已。

也就是说这 3 个指令完成了 6 次内存访问操作,最终的 5 条指令一共完成了 10 次内存访问操作。

Last Updated 2020-03-29 日 23:05.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.1.14)