【OSTEP】分页(Paging) | 页表中究竟有什么 | 页表存在哪 | 内存追踪

💭 写在前面

本系列博客为复习操作系统导论的笔记，内容主要参考自：

• Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy PiecesA. Silberschatz, P. Galvin, and G. Gagne,
• Operating System Concepts, 9th Edition, John Wiley & Sons, Inc., 2014, ISBN 978-1-118-09375-7.Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

0x00 分页介绍（Concept of Paging）

分页并不是将一个进程空间的地址空间分割成几个长度不同的逻辑段（代码，堆，段），而是 分割成固定大小的单元，每个单元称为一 页。

Paging splits up address space into fixed-sized unit called a page.

• Segmentation：逻辑段（代码、堆栈、堆等）的大小可变。

相应的，我们把物理内存看成是定长槽块的阵列，称为 页帧（page frame）。

With paging, physical memory is also split into some number of pages called a page frame.

每个进程都需要一个页表，用于将虚拟地址转换为物理地址。

Page table per process is needed to translate the virtual address to physical address.

关键问题：如何通过页来实现虚拟内存？

如何通过页来实现虚拟内存，从而避免分段的问题？基本技术是什么？如何让这些技术很好地运行？并尽可能地减少时间和空间的开销？

灵活性（Flexibility）：有效支持地址空间的抽象性。

• 不需要假设堆和栈是如何增长和使用的。

简单性（Simplicity）：易于自由空间的管理，

• 地址空间中的页和页框的大小是一样的。
• 易于分配和保持空闲列表

0x01 一个简单的例子

64 字节的地址空间，有 16 字节的页（4页）。

128 字节的物理内存，有 16 字节的页帧（8个页帧）。

这里只是为了方便讲解举得例子而已，然而真实的地址空间肯定比这个大得多，通常 32 位有 4GB 的地址空间，甚至有 64 位！（这里插一嘴，64位的地址空间是真他马的大，如果说 32 位地址空间有网球场那么大，那么 64 位地址空间就是整个欧洲的面积那么大）

为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常位每个进程保存一个数据结构，称为 页表（address table），又称页面映像表。页表是一种数据结构，用于将虚拟地址映射到物理地址。 从而让我们知道每个页在物理内存中的位置，起到映射作用。

为了转换该过程生成的虚拟地址，我们将虚拟地址它分为两个部分：

• 虚拟页面号 (VPN)：virtual page number
• 偏移量 (Offset)： offset within the page

例如：64 位地址空间中的虚拟地址 21（0x15）

0x02 页表中究竟有什么？

页表可以变得非常大，一个典型的32位地址空间，带有 4KB 的页。这个虚拟地址分成 20 位的 VPN 和 12 位的偏移量。

一个 20 位的 VPN 意味着操作系统必须为每个进程管理 个地址转换（大约一百万）。

❓ 页表存在哪里？

Page tables for each process are stored in memory.   （每个进程的页表都存储在内存中）

• 要找到所需PTE的位置，需要页表的起始位置（例如 PTBR - 页表基数寄存器）
• 对于每一个内存引用，分页需要操作系统执行一次额外的内存引用 → 这太慢了！

我们知道了 —— 页表就是一种数据结构，用于将虚拟地址映射到物理地址。

• 因此，任何数据结构都可以采用，最简单的形式就是线性页表（一个数组）。

操作系统通过 VPN 对数组进行索引，并查找页表条目（entry），常见的条目有：

• Valid Bit: Indicating whether the particular translation is valid.
• Protection Bit: Indicating whether the page could be read from, written to, or executed from.
• Present Bit: Indicating whether this page is in physical memory or on disk (swapped out).
• Dirty Bit: Indicating whether the page has been modified since it was brought into memory.
• Reference Bit (Accessed Bit): Indicating that a page has been accessed.

有效位：用于指示特定的地址转换是否有效。

保护位：表明页是否可以读取、写入或执行。

存在位： 表示该页实在物理存储器上还是在磁盘上。

脏位：表明页面被带入内存后是否被修改过。

参考位(访问位) ：用于追踪页是否被访问。

利用分页访问内存：

// 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)

0x03 内存追踪（A Memory Trace）

在结束之前，我们现在通过一个简单的内存访问示例，来演示使用分页时产生的所有内存访问。

需要我们感兴趣的代码片段如下：

💬 代码：array.c

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

我们用下列指令编译它：

prompt> gcc –o array array.c –Wall –o
prompt>./array

生成的汇编代码如下：

虚拟（和物理）内存追踪：

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2022.
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！