CSCI3150 L10 分页

课程：CSCI3150 Introduction to Operating Systems · 2022未核 本讲：L10 分页，第 2 部分 / 共 2 部分 · 原件 L10-分段与分页-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.18–33 定位：用固定大小的页与页框转换地址，并看清页表的空间和访问成本。 前后：前接 分段；后接 L11 TLB。

逐页伴读

p.18 是 Part II 标题。

p.19–21：页连续，页框可以散开

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

Segmentation: variable size of logical segments(code, stack, heap, etc.)

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.

虚拟空间按固定页长切为 page，物理内存按同样大小切为 frame。每个进程的页表记录“我的第几页放在哪个物理框”，所以不同进程的同一 VPN 可以有不同映射。

图 p.20–21 用三种颜色代表 P1、P2、P3，箭头把各进程的虚拟页连到物理框；要看虚拟顺序与物理顺序无须一致。p.21 的页表逐列读取：P1 的 VPN 0–3 分别映射 3、1、7、10；P2 映射 0、4、2、6；P3 映射 8、5、9、11。三者恰好各占四框，合计十二框，没有重复占用。不能把横向相邻的表格项当成同一进程。

p.22–24：页号和页内偏移各管什么

p.22 Flexibility: Supporting the abstraction of address space effectively

Don’t need assumption how heap and stack grow and are used.

Simplicity: ease of free-space management

The page in address space and the page frame are the same size.

Easy to allocate and keep a free list

p.23 128-byte physical memory with 16 bytes page frames

64-byte address space with 16 bytes pages

p.23 (page 0 of the address space)

p.23 64-Byte Address Space Placed In Physical Memory

p.23 page frame 0 of physical memory

p.24 Two components in the virtual address

VPN: virtual page number

Offset: offset within the page

Example: virtual address 21 in 64-byte address space

原例：虚拟空间 64 B，页长 16 B，物理内存 128 B；映射为 VPN 0→PFN 3、1→7、2→5、3→2。共有 4 个虚拟页、8 个物理框。虚拟地址 6 位，其中页内偏移 4 位，VPN 2 位；物理地址 7 位，其中 PFN 3 位。

图 p.23 物理框 0 留给 OS，未用框与已映射框交错。分页的简单之处是任何空闲框都能接纳一个页，不必寻找能容纳整个进程的连续区域。它仍可能有页内部没用完的空间，不能说完全没有碎片。

p.25–27：把 21 转成 117，再问页表放哪里

p.25 The virtual address 21 in 64-byte address space

p.27 Example: Page Table in Kernel Physical Memory

题面沿用上节映射，求虚拟地址 21 对应物理地址。先做除法：$21=1\times16+5$，故 VPN=1、offset=5；页表得到 PFN=7，最终 $7\times16+5=117$。二进制就是 01 0101 换成 111 0101，低四位原样保留。

图 p.27 在物理框 0 内写入页表 3 7 5 2。页表本身也占真实存储，通常不能全塞进少量寄存器。p.26旧PDF兼容图片误显调度例子；PPTX正文层实际说明32位地址、4KiB页、20位VPN、每项4B，页表共4MiB，并存放在内存中。以下根据原件正文层完整展开，通用公式是：

原件 p.26 算例：32 位虚拟地址、4 KiB 页、每项 4 B，页数为 $2^{32}/2^{12}=2^{20}$，线性页表占 $2^{22}$ B=4 MiB。进程即使只用了几页，平铺整张表仍付出这份空间。

补充：页内偏移为什么原样保留。 转换只替换“这一页存放在哪一框”，不改变页内部字节的相对顺序。p.25 的 VA21 是 VPN1 的第5号字节；无论这一页放到哪个框，仍须访问那个框的第5号字节，所以把PFN7乘16得到框起点112，再加5到117。若把offset也查表或重新缩放，就不再访问原来的那个字节。

最后一个页内字节是offset15。VA31=1×16+15，映射为127；下一个VA32=2×16+0，却映射到PFN5的起点80。虚拟地址只加1，物理地址却可以跳到较小位置，因为跨越了页边界。这个例子沿用原映射，说明不能用第一字节物理地址加长度替代跨页访问的逐页转换。

补充：一次跨页访问要分别转换两边。 单个地址的 offset 在页内保持不变，不表示一段虚拟连续数据在物理上也连续。沿本讲固定页的思路，若一项操作覆盖下一页，必须继续查下一页的映射，不能直接把第一段物理地址向后加到底。

算一遍（数字是我为演示取的，讲义没给）：页长 16B，虚拟页 0 映到物理框 7，虚拟页 1 映到框 2。从虚拟地址 14 读四字节，14、15 位于 VPN0，物理地址为 126、127；16、17 位于 VPN1，物理地址为 32、33。结果顺序仍是四个逻辑相邻字节，但物理地址序列不是 126、127、128、129。若第二页不存在或不允许读取，第一字节合法也不能保证整个操作成功；具体异常完成语义由机器和接口决定，本例只演示逐地址映射。

p.28–30：PTE 除了框号还需要状态

p.28 The page table is just a data structure that is used to map the virtual address to physical address.

Simplest form: a linear page table, an array

The OS indexes the array by VPN, and looks up the page-table entry.

p.29 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

最简单的线性页表是数组，VPN 就是数组下标。Valid 表示映射是否合法；Present 表示合法页当前是否驻留物理内存，二者不能互换。合法但不驻留的页可能需要换入，不是非法地址。

Protection 控制读写执行；Dirty 表示换入后被改写，决定淘汰时是否需要写回；Accessed/Reference 记录近期访问，供置换参考。图 p.30 的 x86 PTE 高位存 PFN，低位存标记，具体硬件位义应按该图解释，不能把所有体系结构都当成这张格式。

把 p.30 的 32 位 PTE 位图写成表。 位号从右端 0 数到左端 31；连续的 PFN 占 20 位，组合 12 位页内偏移即可形成该例的 32 位物理地址。

课件这里只展开 P、R/W、U/S、A、D 和 PFN；G/PAT/PCD/PWT 的具体硬件组合规则没有在本讲给出，不把标签扩写成另一个体系结构的完整手册。用该图做地址题时先去掉低 12 位标记，不能把整个 PTE 整数直接当页框号。

p.31–33：一次访存为什么可能变成两次

p.31 To find a location of the desired PTE, the starting location of the page table is needed.

For every memory reference, paging requires the OS to perform one extra memory reference.

课件程序与接口（p.32，原页片段）

1   // Extract the VPN from the virtual address
2   VPN = (VirtualAddress & VPN_MASK) >> SHIFT
3
4   // Form the address of the page-table entry (PTE)
5   PTEAddr = PTBR + (VPN * sizeof(PTE))
6
7   // Fetch the PTE
8   PTE = AccessMemory(PTEAddr)
9
10  // Check if process can access the page
11  if (PTE.Valid == False)
12      RaiseException(SEGMENTATION_FAULT)
13  else if (CanAccess(PTE.ProtectBits) == False)
14      RaiseException(PROTECTION_FAULT)
15  else
16      // Access is OK: form physical address and fetch it
17      offset = VirtualAddress & OFFSET_MASK
18      PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
19      Register = AccessMemory(PhysAddr)

p.33 Segmentation

A program contains logically-different segments: code, stack, heap

Each segment can be placed in different part of physical memory.

Base and bounds exist per each segment.

Paging

physical memory is split into some number of pages called a page frame.

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

Next: Free Space Management, Translation Lookaside Buffers, Advanced Page Tables, and Swapping (Chapters 17, 19, 20, 21, 22, 23)

页表起始物理地址 PTBR 加上 VPN*sizeof(PTE) 得到的是 PTE 的地址，读取 PTE 才得到 PFN。检查合法性和权限后，再将 PFN 与偏移组成最终物理地址，读取目标。

无 TLB、无缓存命中的简化模型中，一次数据访问变成“读 PTE＋读数据”两次物理访问。课件 p.31 用 OS 概述管理责任；p.32 的正常硬件转换不意味着每次访问都陷入内核执行软件。下一讲的 TLB 正是缓存转换结果，省掉反复读页表的代价。

p.33 回看两个设计：分段贴近逻辑区域但可变长；分页固定长度，便于分配，但页表可能又大又慢。不要只记分页优点而漏掉新成本。

补充：把 p.30 的位字段与 p.32 的访存流程接起来算。 以下数值是自设例子，沿用 32 位地址、4 KiB 页、4 B PTE 的教学模型，假设使用线性页表、没有 TLB 命中，页有效且访问权限允许。令虚拟地址 VA=0x00001234，页表物理起点 PTBR=0x00100000，第 1 项存着 0x00007067。

按 p.30 所画位布局，低位 0x067 表示 bit 0、1、2、5、6 为 1，即 P、R/W、U/S、A、D 置位；这些状态不能混进 PFN。D 已为 1 说明该页曾被修改，不表示当前这一条必然是写操作。上表只为解释该布局和查表过程，不把一个线性页表教学算例称为完整真实 x86 地址转换配置。

第一次内存读取发生在 0x00100004，取回来的是映射；第二次才到 0x00007234 读数据。把这两处地址写成两行，就能看懂为什么没有 TLB 时查表增加开销，也不会把 PTBR 加到最后的数据地址上。若检查发现不在内存或无访问权限，应进入相应异常处理，不能跳过检查硬拼地址。

本讲核心考点

• [C] 用除法或位拆分计算 VPN、offset、PFN、物理地址。
• [C] 计算线性页表大小，写清 B 与 KiB 的换算。
• [C] 区分 valid、present、protection、dirty 和 accessed。
• [C] 区分 PTE 地址与目标数据地址，解释双重访存。

附录

本份没有需要移至附录的长推导；计算过程已在对应页正文写全。

来源与证据

• 原件：L10-分段与分页-2022未核.pptx（本地课件）；PDF副本（本地课件） p.18–33。本文页码均为 PDF 页号。

• 教材：OSTEP 第 18 章（Paging: Introduction）。

• 考试证据：读了 课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无

• 2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。