代码炼金工坊

分页的概念与 i386 的实现(未完成)
August 15, 2021

理论结合实践,学习《操作系统概念》之分页(pagging)。

概念

  • 帧(frame) - 物理内存分为固定大小的块
  • 帧表(frame table) - 记录帧的信息
  • 页(page) - 逻辑内存分为与帧同样大小的块
  • 页表(page table) - 记录页的信息
  • 页码(page number) - 页表的索引
  • 页偏移(page offset) - 页内的偏移地址

页的大小为2的幂,方便将逻辑地址转换为页码和页偏移。

逻辑地址空间为 2m ,且页的大小为 2n ,则逻辑地址的高 mn 位表示页码 ,低 n 位表示页偏移。

对于32位硬件来说,其逻辑地址空间为 232 ,页的大小(通常)为 4kb 即 212 ,因此使用高20位表示页码,低12位表示偏移,系统可访问 244 字节大小的物理内存。

分页不会产生外部碎片,但是有内部碎片。

一般意义上,逻辑地址被分解成页码和页偏移,通过页表查找到页码对应的页,然后根据页上保存的物理地址加上页偏移访问物理内存。

硬件支持

分页功能依赖于硬件的支持。

  • 页表专用寄存器: 适合小条目页表(eg: DEC PDP-11)
  • 页表基地址寄存器(PTBR): 页表放在内存中,适合大条目页表

转换表缓冲区 TLB

使用 PTBR 获取真实物理地址需要访问两次内存,内存访问速度减半,延迟提高。因此需要引入专用的小型高速硬件缓冲(Translation Look-aside Buffer)。

TLB 包含少数页表条目,逻辑地址首先从 TLB 查找页码。未找到被称为 TLB miss ,则进行两次内存访问,并把结果保存到 TLB 。

查找页表条目中在 TLB 命中次数的百分比称为命中率。可以通过加权计算获得有效内存访问时间

设 TLB 命中率为99%。当页码在 TLB 中时,访问内存需要 100ns 。如果未命中,访问页表花费 100ns , 访问内存花费 100ns ,则有效内存访问时间 =0.99×100+0.01×200=101ns

页表结构

对于32位逻辑地址空间的系统来说,当页大小为 4kb 时,页表多达 232/212=220 即1048576条,每个条目占 4byte 内存,则页表大小为 4mb 。

需要将页表划分为更小的块避免连续分配大内存。

分层分页

对页表进行两层分页,使用逻辑的地址的高10位作为外层页表的索引,中10位作为内层页表的索引,低12位作为页偏移。

对于64位则可以使用四层分页。

哈希页表

将页码哈希到哈希表,获取对应的条目。条目是一个链表,对链表进行页码匹配,获取帧。

倒置页表

对于每个真正的内存页或帧,倒置页表中才有一个条目。整个系统只有一个页表,每个页只有一条相应的条目,共享内存存在困难。

i386 的分页实现

Intel 的 i386 架构同时具有分段和分页。

它的逻辑地址并不直接分解为页码和页偏移,而是先经过分段单元生成线性地址(Linear Address) ,然后使用线性地址去查找页表访问物理内存。

i386 使用二级分页法,外层页表称为页目录(Page Directory)。

x86-64 架构采用四级分页,支持48位虚拟地址,52位的物理地址。

前文提到,分页功能依赖于硬件的支持,大条目页表使用 PTBR 。在 i386 架构中,支持此功能的硬件是 cr0, cr2 和 cr3 。

其中 cr0 用于进入保护模式和开启分页机制。二进制位0为 PE 位,用于开启保护模式;位31位 PG 位,用于开启分页机制。

cr3 用于保存页目录的基地址,因此称为页目录基地址寄存器(PDBR)。只有高20位有效。

cr2 用于保存页异常时引起异常的线性地址。

需要注意的是,分页机制必须在保护模式下才能开启。

代码实现

汇编使用 nasm 。

一共分为5个文件 mbr.asm, bootloader.asm, kernel.asm, linker.ldMakefile

其中 mbr.asm 主要负责设置加载 bootloader.asm 的代码,设置 gdt 代码段数据段和进入保护模式。

bootloader.asm 负责加载 kernel.asm 的代码,检查分页支持功能设置页表和开启分页。

kernel.asm 利用分页机制做一些简单的打印操作表明自身状态。

linker.ld 主要用来连接三个汇编文件源码,在编译时进行重定位,最终编译为平坦二进制。

Makefile 用于编排编译工作。

mbr.asm

section .mbr
global _start

[bits 16]
_start:
    mov ax, cs
    mov ss, ax
    mov sp, 0x7c00

    hlt

gdtinfo:
    dw gdt_end - gdt_start - 1
    dd gdt_start
gdt_start:
    dq 0
data_desc:
    dd 0x0000ffff
    dd 0x00cf9200
code_desc:
    dd 0x0000ffff
    dd 0x00cf9a00
gdt_end:

dap:
    db 0x10
    db 0
dap_blocks:
    dw 0
dap_buffer_addr:
    dw 0
dap_buffer_seg:
    dw 0
dap_start_lba:
    dq 0

times 510-($-$$) db 0
dw 0xaa55

未完成