Operating System: Paging

内存管理机制: 分页

怎样虚拟化内存来避免分段(segmentation)问题？

怎样虚拟内存来避免分段问题（内部分段问题Interal segmentation fault 和外部分段问题 external segmentation fault）？
需要哪些基础技术呢 ?
这些技术又是如何工作的呢 ?

分页 (Paging)

通过分页技术，我们不在将地址空间分割为三个大小可变的逻辑分段; 而是将地址空间分割为固定大小的单元, 每个单元我们称之为页
操作系统通过分页表来保存虚拟页与物理地址之间的对应关系，分页表负责地址转换: 它将每个地址空间的虚拟页转化为对应的物理内存地址。
操作系统会为每个进程单独创建其分页表。不同进程的页面表会映射到物理内存的不同部分（共享模块除外）

分页的工作方式

假设我们有一块64 bytes 的地址空间。当我们执对地址空间中某个地址执行以下命令时时:
- movl <virtual address> , %eax
该命令会将<virtual address>里的内容加载到寄存器eax中。
为了实现该命令，我们需要将<virtual address> 翻译为物理地址。
我们将<virtual address>分为两部分：
- VPN(virtial page number 虚拟页码)
- offset(偏移量)
在这个例子中，由于虚拟地址空间大小为64 bytes且每个分页大小为16 bytes, 所以我们需要6 bits 来代表我们的虚拟地址(2^6 = 64)。
由于每个分页大小为16bytes，我们共计需要4个分页,所以我们需要2 bits (2^2 = 4)来代表VPN，其余4 bits (2^4 = 16) 则用来确定我们需要的地址在分页内的位置。
最后我们通过分页表来查询VPN 对应的物理分页地址（physical page number, PPN a.k.a physical frame number of PFN), 然后将offset部分添加到PPN尾端。最终获得了我们需要的物理地址。
一个简单的例子
movl 21, %eax
将21转化为二进制形式为010101。
分解为VPN和offset:
页面表将VPN转化为PFN
获得物理地址1110101
分页表内存储的内容
分页表仅仅是一种用来虚拟内存地址映射到物理内存地址 的数据结构，或者更直白地讲，分页表是一种将VPN映射到PFN的数据结构。
分页表的每个数据单元为PTE(page-table entry 分页表单元)
最简单的分页表结构为线性分页表(linear page table):
- 采用数组来存储数据形式。
- 数组的索引为VPN。
- PFN及相关信息即为索引VPN对应的信息。
分页表单元(PTE)不仅存储PF还存储一些与该物理地址相关的信息：
- Valid bit: 表示该物理内存地址目前是否可用。
  - 当一个程序运行起来后，分配在物理内存中堆和栈之间的物理内存是不可用的。其 valid bit 为false，如果强行读取，则会生成一个系统调度。系统调度会终结该进程。
- Protection bit: 表示该物理分页的内容是否可以读取，写入，和执行。
  - 如果强行读取（写入或执行) 一个禁止读取（写入或执行）的分页，则会生成一个系统调用，
- Present bit: 表示该分页是映射到物理内存上，还是映射到磁盘上。
- Dirty bit: 表示该分页自加载进内存时起，是否被修改过。
  分页机制的两个问题
  太慢
每次内存读取都需要执行两次内存读取:
- 第一次读取分页表获得PFN，合成实际物理内存地址。
- 第二次读取实际内存地址获得其内容。

通过上个实例具体分析

执行命令: movl 21, %eax

为了读取虚拟内存地址21的内容，我们需要将虚拟内存地址转化为物理内存地址。

首先我们需要知道当前进程的分页表的地址。（假设该地址存储在 Page-table base寄存器中)
访问 VPN 对应的 PTE（分页表单元地址)。
然后获得PTN。
PTN与offset 结合获得最终物理内存地址。

访问物理内存地址内容

// 从VPN中获得VPN
VPN = (VIrtualAddress & VPN_MASK) >> SHIFT;

// 生成PTE对应的地址
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE));

// 读取PTE内容
PTE = AccessMemory(PTEAddr);

// 检测该物理分页是否可用

if (PTE.Valid == False){
  RaiseExpection(SEGMENTATION_FAULT);
} else if (CanAccess(PTE.ProtectBits) == False) {
  RaiseException(PROTECTION_FAULT);
} else {
  
  // 可以读取，则生成物理内存地址，读取之。
  offset = VirtualAddress & OFFSET_MASK;
  PhysAddr = (PTE.PFN << PFN_SHIFT) | offset;
  Register = AccessMemory(PhysAddr);
}

// VPN_MASK 设置为 0x30 （二进制110000)，与 VirtualAddress进行按位与(&)运算。SHIFT设置为4。
// PageTableRegister 表示分页表的其实虚拟内存地址。
// OFFSET_MASK 二进制值为001111.
// PFN_SHIFT值也为4.
// PTE.PFN << PFN_SHIFT:将PFN左shift了4位。
// PTE.PRN << PFE_SHIFT 之后的结果与offset进行按位或运算获得物理内存地址

分页表太大

对于一个32-bits 的地址空间，如果一个分页大小为4Kb，那么虚拟内存地址需要12 bit(2^12约等于4000)作为offset，其余20 bits 作为VPN。
20 bits 作为VPN则意味着一个Page Table 要保存2^20（大约一百万条）条分页表单元。
假如一条分页表单元大小为4 bytes，那么整个分页表大小约为4MB !
如果共计有100个进程在运行，那么所有分页表占据的内存为400MB!!!

实例

通过一个简单的程序来了解采用分页机制下程序进行内存读取的过程。

int array[1000];

void main(){
  array[i] = 0;
}

该程序对应汇编代码如下:

0x1024 movl $0x0, (%edi, %eax, 4)
0x1028 incl %eax
0x102c cmpl $0x03e8, %eax
0x1030 jne 0x1024

我们假设：
- 虚拟内存空间大小为64KB, 分页大小为1KB。
- 分页表为线性分页表, 类似数组. 分页表的物理内存地址为1KB(1024)。
- 虚拟内存地址0x1024到0x1034对应的物理内存空间存储代码，由于分页大小为1KB, 所以0x1024属于虚拟内存空间的第二个分页VPN1(第一个分页为VPN0)，我们假设VPN1映射到PFN4。
- 数组则存储在虚拟内存地址40000到44000（由于数组大小为40000)，即有VPN39到VPN42。我们假设如下对应关系:
  - VPN39 -> PFN 7
  - VPN40 -> PFN 8
  - VPN41 -> PFN 9
  - VPN42 -> PFN 10
第一行:
- %edi 中存储了这个数组的base address， %eax中则存储了数组的索引(i)
- (%edi, %eax, 4) 计算出数组中当前单元的虚拟地址。
- movl $0x0, (%edi, %eax, 4) 将数值0移动到数组相应单元对应的虚拟内存地址中。
第二行：将数组索引加1.
第三行：将数组索引值与 0x03e8(十进制10000)比较。如果不相等，则执行第四行。
第四行：跳回虚拟内存地址0x1024即第一行。
运行过程：
- 每条命令会产生两个内存访问：
  - 根据VPN访问分页表对应的分页表单元(PTE),获得PTN。
  - 根据PTN和offset生成对应的物理内存地址。访问对应的物理内存地址，获得命令，交给CPU处理
- 在movl命令中，每次数组单元的访问也会产生产生两个内存访问：
  - 根据VPN访问分页表对应的分页表单元(PTE),获得PTN。
  - 根据PTN和offset生成对应的物理内存地址, 获得数组单元内容。
前五个循环中内存访问情况:

Operating System: Paging

内存管理机制: 分页

怎样虚拟化内存来避免分段(segmentation)问题？

分页 (Paging)

分页的工作方式

一个简单的例子

分页表内存储的内容

分页机制的两个问题

太慢

分页表太大

实例

分页的工作方式

分页表太大

实例