Chapter 18 Paging: Introduction

第 18 章 分页：介绍

操作系统有两种方法，解决大多数空间问题

1. 将空间分隔成不同长度的分片，就像虚拟内存管理中的分段

2. 1. 但是会碎片化，时间愈长，管理俞困难

3. 空间分割成固定长度的分片

4. 1. 分页！

   2. 物理内存看成定长槽块的阵列，叫做页帧

   3. page frame

1. 一个简单的例子

1.1. 地址空间 & 物理空间

没有指定他们的对应关系...分页提供的空闲空间管理的简单性...

操作系统为每个进程保存了一个数据结构，称为页表（page table）

1.2. page table

页表主要作用是为地址空间的每个虚拟页面保存地址转换...map 可以实现...?

页表是每个进程一个的数据结构

有一个例外：倒排页表 inverted page table

translate 过程生成的虚拟地址...

有两个组件：

1. 虚拟页面号 virtual page number，VPN

2. 页内偏移量 offset

通过虚拟页表找到物理页表 找到物理页号 physical page number/physical frame number

2. 页表存在哪里

页表可以变得非常大

1. 先假设页表存在内存里

2. 稍后会了解到 实际上是存在虚拟内存里的...

3. 页表中究竟有什么

3.1. 线性页表 linear page table

就是一个数组

通过虚拟页号 VPN 检索该数组，通过索引查找页表项 PTE..以便找到期望的物理帧号

3.2. PTE 页表项

1. 有效位 valid bit 指示特定地址转换是否有效

2. 1. 一个程序运行时 中间未分配未使用的空间都会被分配为无效...

3. 保护位 protection bit 表明页是否可以读取、写入或执行

4. 存在位 present bit

5. 脏位 dirty bit

6. 参考位 reference bit / 访问位 accessed bit

4. 分页：也很慢

内存中的页表 太大了！会让速度变慢

内存虚拟化是一个大问题...

5. 内存追踪

通过一个简单的数组循环来理解操作系统内部实际的操作...

为什么循环的复杂度是 O(n) 为什么比赛尽量避免使用 循环...

我们于是知道 即使是简单的上层行为 在下层也会引起灾难性的行为

以后也只会更复杂...

6. 作业（模拟作业）

In this homework, you will use a simple program, which is known as paging-linear-translate.py, to see if you understand how simple virtual-to-physical address translation works with linear page tables. See the README for details.

• Address Space Size: Increasing the address space size while keeping the page size constant increases the number of page table entries linearly.

• Page Size: Increasing the page size while keeping the address space size constant decreases the number of page table entries.

简单的模拟 - 物理地址转换 和 线性页表的工作...