❤️操作系统的非连续内存分配
🎾1. 概述
第三章介绍的是
连续内存管理, 即 : 操作系统加载到内存以及程序加载到内存中时, 需要为其分配一块连续的空闲(内存)块. 但是容易出现碎片问题, 这一章介绍的非连续内存分配可以有效的减少碎片的出现.
为了避免产生过多碎片，而使用非连续内存分配策略
- 分段（Segmentation）
- 分页（Paging）
页表（Page Table）
- 页表概述
- 快表（TLB）
- 二级/多级页表
- 反向页表
连续内存分配的缺点
- 分配给一个程序的物理内存是连续的
- 内存利用率低
- 有外碎片 / 内碎片的问题
非连续内存分配的优点
- 一个程序的物理地址空间是非连续的
- 更好的内存利用和管理
- 允许共享代码与数据(共享库等...)
- 支持动态加载和动态链接
非连续内存分配的缺点
建立虚拟地址和物理地址的转换难度大
- 软件方案（开销太大，不选择）
- 硬件方案(采用硬件方案) :
分段 / 分页
🎾2. 分段
需要解决的问题
- 程序的分段地址空间的寻址
- 分段寻址方案
段: 在程序中会有来自不同文件的函数 ; 在程序执行时, 不同的数据也有不同的字段, 比如 : 堆 / 栈 / .bss / .data 等分段：更好的分离和共享
程序的分段地址空间如下图所示 :
🎱2.1 分段寻址方案
- 软件可以访问，但是对于每一次内存访问，软件每次都需要进行一次映射，导致内存开销很大，所以使用硬件访问
程序是一个连续的一维的逻辑地址空间，但是物理地址空间不连续，使用映射机制进行关联.
俩种实现机制
- 段寄存器+地址寄存器（段寄存器和地址寄存器是分开的）
- 单地址实现（段寄存器和地址寄存器不分开）
🎱2.3 硬件实现方案
- 根据段号找到，物理地址的起始地址
- 根据偏移找到，整个长度限制
- 操作系统建立段表，它维护这个段表（段号，物理地址的起始地址，长度限制）
- 物理地址 : 段表中的起始地址 + 二元组中的偏移地址
- 当查到相应的物理地址，CPU会将查到的段的限制和实际物理地址对比，当超出限制，CPU会产生一个中断异常，交给OS处理。如果满足限制，则段号+偏移产生物理地址，CPU根据物理地址将相应的数据取出来
🎾3. 分页
分页
- 分页地址空间
- 页寻址方案
🎱3.1 分页地址空间
段和页区别：在分段中段的尺寸是可以变化的，在页中，页或者页帧的大小是固定不变的- 完成物理页表和逻辑页表的映射
页帧（Frame）（物理地址）
分页和分段的最大区别 : 这里的 S 是一个固定的数, 而分段中的长度限制不定
例子
页（Page）（逻辑地址）
🎱3.2 页寻址机制
操作系统维护一张页表, 页表保存了逻辑地址——物理地址之间的映射关系
存储 : (页号, 帧号)
- 逻辑地址空间应当大于物理内存空间
- 页映射到帧
- 页是连续的虚拟内存
- 帧是非连续的物理内存(有助于减少碎片的产生)
- 不是所有的页都有对应的帧
分页机制和分段不一样，分页机制页内的偏移大小是一样的
逻辑地址是连续的映射到物理空间后是不连续的，这有利于减少内存碎片
🎾4. 页表
🎱4.1 页表概述
- 页表概述
- 转换后备缓冲区（TLB）
- 二级/多级页表
- 反向页表
🎱4.2 页表结构
CPU根据程序的page的页号的若干位, 计算出索引值index, 在页表中搜索这个index, 得到的是帧号, 帧号和原本的offset组成物理地址.
地址转换实例
分页机制的性能问题
访问一个内存单元需要2次内存访问
- 一次用于获取页表项
- 一次用于访问数据
页表可能非常大
- 64位机器如果每页1024字节, 那么一个页表的大小会是多少？(2^64 / 2^10 = 2^54 存放不下)
每一个运行的程序都需要有一个页表
如何处理？
缓存(Caching)：将经常用到的数据和内容缓存到离CPU很近的地方——————>速度上间接(Indirection)访问：把很大的空间，拆分成比较小的空间（多级页表）————>空间上
🎱4.3 TLB缓冲（速度上）
- MMU：CPU中的内存管理单元的TLB缓冲，缓冲页表的内容
当CPU得到逻辑地址后，根据key查找TLB表，找到f,+offset直接获得物理地址,避免了对一次页表的访问，当TLB访问不到，CPU会查找页表，如果页表的标志位为1，则存在，于是把页表中的Frame num取出来，放到TLB中
🎱4.5 二级页表、多级页表（空间上）
二级页表
- 将页号分为两个部分, 页表分为两个, 一级页号对应一级页表, 二级页号对应二级页表.
- 一级页号查表获得在二级页表的起始地址, 地址加上二级页号的值, 在二级页表中获得帧号
步骤
- page num 分成俩块P1和P2，对应一级页表页号和二级页表页号，offset没变。从而使得对大地址寻址变成对n个小地址寻址
- 首先找一级页表，一级页表起始地址CPU知道，将P1的起始地址作为index,查找一级页表的页表项，存的是二级页表的起始地址。
- 把P2作为二级页表的index+一级页表中存储的二级页表起始地址，形成针对P2的页表项，它里面存的是Frame num,在加offset获得物理地址
时间交换空间
- 节约了一定的空间, 在一级页表中如果resident bit = 0, 可以使得在二级页表中不存储相关index,而只有一张页表的话, 即使映射关系不存在，对应的一些index都需要保留
多级页表
- 通过把页号分为k个部分, 来实现多级间接页表, 建立一棵页表"树"
🎱4.6 反向页表
逻辑空间越大，寻址空间越大，对应的页表就越多，使得页表项不与逻辑空间产生直接关系，与物理地址建立映射关系
解决大地址空间问题
- 目的 : 根据物理页帧号获得逻辑页号（与之前方法相反）
- 反向页表只需要存在一张即可
⛳️4.6.1 基于页寄存器的方案
以页帧号为索引（物理地址），以页号为页表项的内容（逻辑地址），之前的页表都是以页号为索引，页帧号为内容,这种反向存储使得计算机容量只有物理地址有关系- 存储 (帧号, 页号) 使得表大小与物理内存大小相关, 而与逻辑内存关联减小.
问题
- 我们需要根据Page num查找Frame num,而这个表是以Frame num 为索引的
优势 :
- 转换表的大小相对于物理内存来说很小
- 转换表的大小跟逻辑地址空间的大小无关
劣势 :
- 需要的信息对调了, 即根据帧号可以找到页号
- 如何转换回来? (如何根据页号找到帧号)
- 在需要在反向页表中搜索想要的页号
⛳️4.6.2 基于关联内存的方案
- 并行的查找页号所对应的页帧号
- 硬件设计复杂, 容量不大, 需要放置在CPU中
- 如果帧数较少, 页寄存器可以被放置在关联内存中
在关联内存中查找逻辑页号
- 成功 : 帧号被提取
- 失败 : 页错误异常 (page fault)
限制因素:
- 大量的关联内存非常昂贵(难以在单个时钟周期内完成 ; 耗电)
⛳️4.6.3 基于哈希查找的方案
- 哈希函数 : h(PID, p) 从 PID 标号获得页号
在反向页表中通过哈希算法来搜索一个页对应的帧号
- 对页号做哈希计算, 为了在帧表中获取对应的帧号
- 页 i 被放置在表 f(i) 位置, 其中 f 是设定的哈希函数
为了查找页 i , 执行下列操作 :
- 计算哈希函数 f(i) 并且使用它作为页寄存器表的索引, 获取对应的页寄存器
- 检查寄存器标签是否包含 i, 如果包含, 则代表成功, 否则失败
