地址空间与内存分配详解！
时间：2023-05-07 06:21:01 | 来源：网站运营
时间：2023-05-07 06:21:01 来源：网站运营
地址空间与内存分配详解！：
【文章推荐】：极致Linux内核：代码大佬的【Linux内核开发笔记】分享，前人栽树后人乘凉！
极致Linux内核：Linux文件系统详解
极致Linux内核：linux进程管理---实时调度
极致Linux内核：linux内核内存管理-brk系统调用
极致Linux内核：linux内核内存管理-缺页异常
地址空间
1.地址空间分为物理地址空间和逻辑地址空间。
物理地址空间和硬件直接对应，如内存条代表的主存，硬盘代表的磁盘 ，都是物理内存，其管理由硬件完成
逻辑地址空间是运行的程序看到的地址空间，是一维的线性的地址空间。
逻辑地址空间依赖物理地址空间而存在。
2.逻辑地址生成
程序中函数的位置（入口），变量的名字就是逻辑地址。C程序通过编译，汇编，链接link，载入（程序重定位）生成EXE，存放在硬盘中。汇编后（.o文件）起始地址为0，把变量名和函数名转为相应的从0开始的连续逻辑地址，link把多个.o合成一个，放在硬盘中，通过loader应用程序再把exe放在内存中执行，这里有分配地址空间和映射（偏移）的过程。上述过程与OS无关，编译器和loader来完成。此时得到的仍然是逻辑地址。
3、地址映射
物理地址生成的四个步骤
- CPU要在内存中执行指令，ALU需要知道这条指令的内容，发送请求，传参数，参数就是逻辑地址
- 查表。CPU中的MMU查找逻辑地址的映射表（有块区域表示映射关系，如果在MMU没查到会去内存中的MAP找）
- 找到后CPU给主存（就是内存）发请求，请求一个物理地址的内容（就是指令的内容）
- 主存会通过总线把内容传给CPU，CPU执行指令。
- 操作系统的作用是在这些步骤之前建立好映射表，以及地址安全检查 ，OS要检查逻辑地址起始地址和长度 ，设置逻辑地址的界限和基址，如果逻辑地址满足区域限制，则正常访问，如果不满足，就抛出内存访问异常。
连续内存分配和内存碎片
连续内存分配：给应用程序分配一块不小于指定大小的连续的物理内存区域。
碎片：连续分配会造成内存碎片问题，空闲内存不能被利用，外部碎片，在分配单元间的未使用内存，内部碎片，在分配单元中的未使用内存。
操作系统需要维护的数据结构包括所有进程的已分配分区和空闲分区(Empty-blocks）。
下面是三种简单动态分区分配策略
- First Fit 首次适配，
从0地址往后查找和使用第一个可用空闲快（要比需要的空间大）。基本实现机制要求把空闲的内存块按地址排序。回收要考虑能否合并内存块，能够形成更大的内存块
优点：简单，易于产生更大的空闲快，向着地址空间的结尾
劣势：易产生外部碎片（随着动态分配加剧），不确定性
- Best Fit 最优适配：
找比需求大但最接近需求的空闲内存块，产生尽可能小的内存碎片。原理是为了避免分割大空闲块，最小化外部碎片产生的尺寸，需要对空闲地址快按尺寸size排序，分配需要寻找一个合适的分区，重分配需要搜索及合并与相邻的空闲分区，若有。
优点：当大部分分配需要小空间时非常有效，比较简单。
缺点：外部碎片太小太细，不利于后续重分配。
- Worst Fit最差匹配
使用最大的空闲快，大块拆分变小块，可以避免产生太多微小的碎片，也要排序，分配很快，重分配需要搜索及合并与相邻的空闲分区，若有，然后调整空闲块列表
优势：分配中等尺寸最好
缺点：重分配慢，外部碎片，易于破碎大的空闲块以致大分区无法被分配。
碎片整理：通过调整进程占用的分区位置来减少或避免分区碎片
1、压缩式碎片整理 ：调整内存中程序运行的位置，通过拷贝尽量把程序紧凑放到一起，空出较多的空闲位置。拷贝要考虑何时去挪，不能在程序运行的时候挪，要在waiting时，还有考虑开销。
2、交换式碎片整理 ：硬盘当做内存的备份，把waiting的程序包括数据放在磁盘上，腾出空间给其余运行的程序。（抢占waiting程序回收其内存），也要考虑开销和换哪个程序
非连续内存分配
连续内存分配的缺点：分配给一个程序的物理内存是连续的，内存利用率较低，有外碎片和内碎片的问题。
非连续内存分配的优点：一个程序的物理地址空间是非连续的，更好的内存利用和管理，允许共享代码和数据（共享库等），支持动态加载和动态链接。
非连续内存分配最大的问题在于管理的开销。在虚拟地址和物理地址之间的转换，如果用软件来实现，开销巨大。因此要考虑用硬件来协同解决。
非连续分配的硬件辅助机制：分段和分页
分段考虑程序的分段地址空间和分段寻址方案。
将应用程序地址空间看作多个段组成
段访问机制：将一维的逻辑地址分成两块 。程序访问内存地址分为两部分，段的寻址（段号segment number）+ 段内偏移的寻址（addr）
段访问的硬件实现
将逻辑地址看成两部分段号+偏移。段表里面存放了逻辑地址段号与物理地址段号的对应关系，段表里面还包含段的起始地址和段的长度限制，段表在寻址之前由OS建立。CPU会检测访问的段的长度限制。段的起始地址+偏移量形成了物理地址。
分页：
现在绝大多数CPU采取分页机制
分页：分页地址空间和页寻址方案。
分页机制需要页号和页内偏移。
页帧（帧、物理页面,Frame, Page Frame）
- 把物理地址空间划分为大小相同的基本分配单位
- 2的n次方，如512,4096, 8192
页面（页、逻辑页面,Page）
- 把逻辑地址空间也划分为相同大小的基本分配单位
- 帧和页的大小必须是相同的
页面到页帧是逻辑地址到物理地址的转换，需要用到页表,MMU/TLB（快表）。
帧（Frame）:物理内存被划分成大小相等的帧，由帧号和帧内偏移构成。
例子：
页（page）:进程逻辑地址空间被划分为大小相等的页,由页号和页内偏移构成
映射：页表将页号映射为帧号。
页表由OS建立在初始化时建立。在分段里面段的尺寸可变，分页里面页和页帧大小不变，内偏移大小固定。逻辑地址空间会大于物理地址空间（后续会将到虚拟内存），不是所有的页都有对应的帧，逻辑地址中的页号是连续的，物理地址中的帧号是不连续的。
每个进程都有一个页表，每个页面对应一个页表项，随进程运行状态而动态变化，页表基址在页表基址寄存器(PTBR: Page Table Base Register)中。
页表结构：由页表项标志（Flags)和帧号构成，Flags由修改位(dirty bit)、存在位(resident bit)、引用位(clock/reference bit）构成，存在为0表示逻辑地址不存在对应的物理地址，内存访问异常，为1表示存在。
由于逻辑地址很大，为满足映射关系，再者应用程序很多，可能有多个页表，这都可能导致页表很大，不可能都存在CPU中，那么就需要放在内存中，这会导致一次内存寻址要访问两次内存，开销很大。
从时间上解决：快表(TranslationLook-aside Buffer, TLB)，缓存近期访问的页表项。TLB 使用关联存储(associative memory)实现，具备快速访问性能，容量有限。如果TLB命中，物理页号可以很快被获取。如果TLB未命中，对应的表项被更新到TLB中。
TLB的缺失不会很大，32位一个页4K，访问4K次miss一次，可以接受。写程序时注意具有局部性，把频繁的访问集中在一个区域。以避免对内存的访问。另外，还需要注意，miss后，更新是硬件完成（x86），还是OS完成（MIPS）。
从空间上解决：多级页表，以时间开销换取空间开销
二级页表为例，一级页表存放的是二级页表的起始地址
若P1对应得映射关系不存在，则二级页表没有必要存在，节省空间。
反向页表：由于2个问题：大地址空间（64-bits）使前向映射页表繁琐（5级），空间任然很大；虚拟地址空间增长速度快鱼物理地址空间 。因此，前向页表与逻辑空间地址的大小相关→反向页表则是与物理地址空间的大小相对应。优点：空间开销少。映射表的大小相对于物理内存很小，且与逻辑地址空间的大小无关。
方案1：基于页寄存器
优点:页表大小相对于物理内存而言很小，页表大小与逻辑地址空间大小无关
缺点:页表信息对调后，需要依据帧号可找页号，在页寄存器中搜索逻辑地址中的页号
方案2：关联存储器：类似TLB，并行查找，KEY是页号，value是帧号 。但关联存储器用到的硬件逻辑很复杂，开销很大，本身size做不了多大，还需要放到CPU否则要二次访问内存。大的关联存储器也会造成时间开销大。
方案3：哈希表：建立哈希表来实现反向页表。 对页号i做哈希计算，页i放在表中f(i)的位置，求得f(i)作为页寄存器表的索引获取对应的页寄存器,再检查标签是否有i。
问题：
- 会有碰撞，多个逻辑地址对应一个值，加入参数PID==ID of running program来缓解冲突；
- 哈希表在内存中，要访问内存，内存的时间开销还是很大
优点：本身物理存址小省空间，不再是每个应用程序都要page table了，整个系统只用一个。
缺点：需求高，有高效哈希函数和解决冲突的机制，要硬件软件配合，任然需要TLB机制。
冲突解决：
若pid和vpn不一样，则寻找到next项。
原文作者：- - 内核技术中文网 - 构建全国最权威的内核技术交流分享论坛
原文地址：地址空间与内存分配详解！ - 圈点 - 内核技术中文网 - 构建全国最权威的内核技术交流分享论坛（版权归原文作者所有，侵权联系删除）
在线咨询
