虚拟内存管理

目标	实现思路
使得大的程序能在较小的内存中运行、使得多个程序能再较小的内存中运行、使得多个程序并发运行时地址不冲突、使得内存利用率高：无碎片，共享方便	程序运行时，只把当前必要的很小一部分代码和数据装入内存，其余代码和数据需要时再装入。不再运行的代码和数据及时从内存删除。实际内存很容易满足上述的内存需求。

• 程序运行的局部性，程序在一个有限的时间段内访问的代码和数据往往集中在有限的地址范围内（排除多跳转和循环），把程序一部分装入内存在较大概率上也足够让其运行一小段时间。

• 页式虚拟内存管理
  把进程空间（虚拟）和内存空间划成等大小的小片。
  小片的典型大小为1K，2K或4K（windows）
  进程的小片称为页，虚拟页或页面。
  内存的小页称为页框，物理页。

• 进程装入和使用内存的原则
  内存以页框为单位分配使用，进程以页为单位装入内存。
  值把程序部分页装入内存便可运行
  页在内存中占用的页框不必相邻
  需要新页时，按需从硬盘调入内存
  不再运行的页及时删除，腾出空间

  
  页面错误中的页就是此处的页

• 页式系统中的地址
  虚拟地址（VA）可以分成页号P和页内偏移W
  页号P=VA/页的大小
  页内偏移W=VA%页的大小
  CPU的计算方法，页的大小2ⁿ，则页号P=VA>>n，页内偏移W=低n位=VA&&（2ⁿ-1）

• 页面映射表
  记录页与页框之间的对应关系，也称页表，包括页表，页框号和页面其他特性（存取权限等）

• 页式地址映射
  从虚拟地址（页式地址）映射道物理地址，其过程为：从VA分离页号P和页内偏移W->查页表，以P为索引查页框号P^'->计算物理地址MA，MA=P^'*页（框）的大小+W

• 快表机制（Cache）
  慢表指放在内存中的页表，快表指放在Cache中的页表。
  快表容量小，访问快，成本高。快表是慢表部分内容的复制，地址映射时优先访问快表。若在快表中找到所需数据，则称为“命中”，没有命中时，需要访问慢表，同时更新快表。合理的页面调度策略能使快表具有较高命中率，CPU调度时间可以通过期望计算。

• 页面的共享
  在不同进程的页表中填上相同的页框号，多个进程能访问相同的内存空间，从而实现页面共享。
  共享页面在内存只有一份真实存储，节省内存。

• 页表扩充
  扩充有中断位和辅存地址的页表，中断位用于判断该页是否存在内存，1为不存在，0为存在。
  扩充有访问位和修改位的页表，访问位用于判断该页最近是否被访问，1为被访问，0为没访问。修改位用于判断该页最近是否被修改过，1为被修改，0为未修改。

• 缺页中断
  在地址映射过程中，当所要访问的目标页不在内存时，系统产生的异常中断。
  缺页中断处理程序将缺页在页表中的辅存地址调入内存的某个页框中，并更新页表中该页对应的页框号及修改中断位为0。
  缺页率，缺页次数（页面错误）/访问页面总次数，其补集为命中率。

  
  访存指令的执行过程（含缺页中断）

• 页面淘汰
  页面抖动，页面在内存和辅存间频繁交换的线性，抖动会导致系统效率下降。
  淘汰策略需要，较低的缺页率，较少的页面抖动

算法	特点
最佳算法（OPT算法）	淘汰以后不再需要或最远的将来才会用到的页面。理论上最佳，由于无法预知未来，在实践中无法实现
先进先出（FIFO算法）	淘汰在内存中停留时间最长的页面。算法实现简单，但除非进程按顺序访问地址空间，否则缺页率高。特定访问序列会出现页框增多，缺页率也增加的异常现象
最久未使用淘汰算法（LRU算法）	淘汰最长时间未被使用的页面。算法易于实现，存在硬件和软件方法。
最不经常使用算法（LFUS算法）	淘汰到当前时间为止被访问次数最少的页面。每页设置访问计数器，访问则加1，淘汰计数值最小的页面，并将所有计数清零

硬件方法：在页面设置移位寄存器R，当页面被访问时置1，周期性地将所有页面R左移，淘汰R值最大地页面，R的位数越多且周期越小就越精确，但硬件成本高，R的位数越少，可能同时出现多个0，难以比较。
软件方法：利用页表访问位，页被访问时置1，软件周期T将所有访问位置0，淘汰访问位为0的页面。周期T太小，多个访问位为0，找不到合适淘汰页，周期T太大，多个访问位为1，找不到合适淘汰页。

• 缺页因素
  1.淘汰算法
  2.分配给进程的页框数，页框数越少，越容易缺页
  3.页本身的大小，页面太大浪费内存（极限变为是分区存储)，页面太小造成页面增多，页表长度增加而浪费内存，换页频率高，系统效率低。页面越小，越容易缺页
  4.程序的编制方法，局部性越好，越不容易缺页，跳转或分支越多，越容易缺页。由于系统按行存储，数组按行访问，局部性会更好。

• 页面系统的不足
  页面划分无逻辑含义
  页的共享不灵活
  页内碎片

• 段式虚拟内存管理

• 进程分段，是把进程按逻辑意义划分为多个段，每段有段名，长度不定，进程由多段组成，如一个进程可以具有代码段、数据段和堆栈段。

• 段式内存管理系统的内存分配，以段位单位装入，每段分配连续的内存，但段与段不要求相邻

• 段式系统的虚拟地址
  短时虚拟地址VA包含段号S和段内偏移W
  *段表（SMT）
  记录每段在内存中映射的位置，包含段号S，段长L和基地址B

• 段式地址映射过程，由VA分离段号S和段内偏移W->查段表，查出该段的基地址B和长度L->物理地址MA=B+W

• 段表的扩充
  扩充如中断位、访问位、修改位，R/W/X

• 段的共享
  共享段在内存中只有一份存储
  共享段被多个进程映射到各自的段表
  需要共享的模块都可以设置位单独的段

• 段式系统的缺点
  段需要连续的存储空间
  段的最大尺寸受限于内存大小
  在辅存中管理可变尺寸的段比较困难

	页式系统	段式系统
地址空间	一维地址空间	二维地址空间
空间	页面大小固定	段长可变
划分	页面无意义	段有意义
共享	页面不方便共享	段方便共享
可见	页面用户不可见	段用户可见
溢出	页面偏移无溢出	段偏移有溢出

• 段页式虚拟内存管理
  在段式存储管理中结合页式存储管理技术，在段中划分页面。

• 段页式系统的地址构成：
  逻辑地址由段号S，页号P，页内偏移W组成，内存按页划分，按页装入

  
  段页式系统的地址

• 段页式中的段表和页表
  系统为每个进程建立一个段表，系统为每个段建立一个页表，段表给出每段的页表基地址及页表长度（段长），页表给出每页对应的页框。

• x86的实模式
  20位地址空间：1M内存空间，CPU寄存器16位
  地址表示方式：段地址（16位）和偏移地址（16位）
  段地址向左偏移4位对齐再与偏移地址相加

• 保护模式
  32位地址空间：4G内存空间
  支持多任务，任务切换，上下文保护
  进程隔离，代码和数据安全
  支持分段和分页机制
  新的寄存器，EAX_{EDX：扩充到32位，CR0}CR4, GDTR，LDTR，IDTR等

保护模式的寄存器模型

• CR0
  CR0的低5位组成机器状态字（MSW）
  PE：0——实模式；1——保护模式
  MP：1，系统有数字协处理器时
  EM：0，仿真协处理器
  TS：任务切换，切换任务时自动设置
  PG：允许分页

  
  CR0

• CR2
  如果发生缺页，引发缺页的线性地址保存在CR2中

  
  CR2

• CR3
  包含页目录基址：高20位
  由于目录是页对齐的,所以仅高20位有效,低12 位保留供更加高级的处理器使用
  

  CR3

• x86 CPU架构下的三种地址
  逻辑地址：汇编语言（段：偏移）
  线性地址：由逻辑地址转换得到
  物理地址：未分页时的线性地址同物理地址，分页则采用页式地址映射
  第一级：段机制（逻辑地址到线性地址）
  第二级：分页机制（线性地址到物理地址）
  MMU内存管理单元执行地址映射过程

  
  x86 CPU架构下的三种地址

• 段与段描述符
  段指一段连续内存
  段描述符，用于描述段的属性8字节，包括段基址，段界限，段属性和段类型，访问该段所需最小特权级，是否在内存。

  
  段描述符
  

  G表示段的粒度：G=0段长以字节计量；G=1以页面4KB计量
  P表示该段是否存在内存中
  DPL描述特权级别
  S描述段的类型，数据段，代码段，系统段等
  TYPE类型是读、写、扩展、访问标志等及组合

• 描述符表（Descriptor Table）
  存放描述符的数组，长度为8字节的整数倍，其类型包括全局描述符表GDT（所有进程可用，系统仅有1个），局部描述符表LDT（特定进程相关，每个进程都有），中断描述符表IDT（中断服务程序段，类似中断向量表）

• 选择子（Selector）
  用于选择GDT/LDT中的某个描述符
  存放在段寄存器中：高13位是整数索引
  其构成包括索引域（13位，给出描述符位置），TI域（Table Indicator，1位，GDT(0)或LDT(1)），特权级别域（2位）

  
  选择子

• 逻辑地址转换到线性地址（32位，4G）
  逻辑地址 DS： EAX
  保护模式下，CS是选择子

  
  转换过程

• Linux页面基址
  硬件分页，Intel CPU的页是4KB，通过设置CR0的PG位开启分页功能，分页从线性地址到物理地址，在MMU中进行分页

• 普通页表实现时的问题
  32位操作系统（4G空间），每页4K，页表每个记录占4字节，进程页数4G/4K=1M个页，页表所占内存1M*4字节=4M，页表占页框数4M/4K=1K页框（连续）
  困难
  1.难以找到连续1K个页框存放页表
  2.页表全部装入过度消耗内存（4M）
  方法
  1.将4M的超大页表存放到离散的1K个页框中
  2.将页表部分内容调入内存

• 二级页表
  把超大的页表（4M）以页为单位分成若干个小页表，存入离散的若干个页框中。1M的大页表/1K分解成1K个小页表，每个小页表有1K个记录，小页表大小为4K（1K*4）,刚好占用1个页框。
  为了对1K个小页表进行管理和查找，另设置一个叫页目录的表，记录每个小页表的存放位置（页框号）
  页目录实际是一个特殊页表，存放的是小页表的编号和其所在的页框号之间的对应关系。
  页目录为1级页表或外部页表；小页表为2级页表

  
  WINDOWS NT二级页表结构
  

  页目录号：小页表编号，页目录的索引，10位，1K个页表
  页号：页面编号，页表的索引，10位，1K个页面
  页偏移：页偏移，12位，4K

• 二级页表映射特点
  访问数据需要三次访问内存
  页目录调入内存
  页表按需调入内存
  页面、页表、页目录的大小都刚好4K（占1个页框）
  

  Linux三级页表结构
  实际上MIDDLE DIR并不实际存在（0位）

• Linux段基址
  Linux将4G虚拟内存划分位用户空间和内核空间
  用户空间3G，从0到0xBFFFFFFF
  内核空间1G，从0xC0000000到0xFFFFFFF

• 进程建立时，段机制对寄存器初始化，使用start_thread
  _KERNEL_CS 0x10, _KERNEL_DS 0x18, _USER_CS 0x23, _USER_DS 0x2B
  在保护模式下，按照选择子的方式展开

宏	值	INDEX	TI	DPL
_KERNEL_CS	0x10	0000 0000 0001 0	0	00
_KERNEL_DS	0x18	0000 0000 0001 1	0	00
_USER_CS	0x23	0000 0000 0010 0	0	11
_USER_DS	0x2B	0000 0000 0010 1	0	11

表示2，3，4，5全局描述符，按描述符说明可得

全局描述符

XXXX:基地址，hhhh：段界限，等于段长度-1
G位为1，表示段长单位4KB，
P为1，表示段在内存
DP表示段的描述符级别
都占4GB内存，具有相同的范围，code/data在0x00，不同的是段的描述符级别，权限级别。内核段级别为0，用户段级别为3。
利用段机制隔离用户数据和系统数据，保留段的等级保护机制
简化避免逻辑地址到线性地址的转换，可以直接将虚拟地址当做线性地址，两者完全一致。