前提
最近复习了Linux内存管理以及C++的内存管理,这里做一个详细的梳理。
章节
- 内存的分页和分段
- 逻辑地址,线性地址以及虚拟地址之间的关系
- linux内存分配算法:伙伴系统和slab
- linux 进程通信中共享内存技术(mmap和shm)
- C++程序进程地址空间,程序中各个变量与常量分别位于哪一个段
- C++内存池技术
内存的分页和分段
虚拟内存地址空间
由来
当直接让进程使用直接的物理内存时,会对物理内存操作时会出现混乱。
比如进程 A 装在 0-30 的物理内层,在 29 处是一条 ADD 指令。而进程 B 装在 30-40 处第一条指令为 JMP 29. 没有使用虚拟内存的话,进程 B 将直接跳到进程 A 从而使两者程序都破坏掉。
有两种解决这个问题:一种通过基址寄存器和界线寄存器形成地址空间,通过交换技术解决内存超载。另外一种就是基于分页的虚拟地址技术。
- 交换技术:把一个进程完整调入内存运行一段时间,然后把他存回磁盘,空闲进程主要存储在磁盘上。缺点:当进程空间大于内存时,不能使用。
- 虚拟内存:把一个进程的一部分调入内存中运行,当内存没有空闲空间时,将新的覆盖旧的页,同时将旧 是写入磁盘。虚拟内存主要使用分页存储管理模式。
介绍
- 在多任务操作系统中,每个进程都运行在属于自己的内存沙盘中。这个沙盘就是虚拟地址空间 (Virtual Address Space),在 32 位模式下它是一个 4GB 的内存地址块。在 Linux 系统中, 内核进程和用户进程所占的虚拟内存比例是 1:3,而 Windows 系统为 2:2(通过设置 Large-Address-Aware Executables 标志也可为 1:3)。这并不意味着内核使用那么多物理内存,仅表示它可支配这部分地址空间,根据需要将其映射到物理内存。
- CPU 通过一个虚拟地址(virtual address,VA)来访问主存,这个虚拟地址在被送到主存之前会先转换成一个物理地址。将虚拟地址转换成物理地址的任务叫做地址翻译(translation)。地址翻译需要 CPU 硬件和操作系统之间的配合。CPU 芯片上叫做内存管理单元(Menory Management Unit, MMU)的专用硬件,利用存放在主存中的(段表)页表来动态翻译虚拟地址,该表的内容由操作系统管理。
- 虚拟地址通过页表 (Page Table) 映射到物理内存,页表由操作系统维护并被处理器引用。内核空间在页表中拥有较高特权级,因此用户态程序试图访问这些页时会导致一个页错误 (page fault)。在 Linux 中,内核空间是持续存在的,并且在所有进程中都映射到同样的物理内存。内核代码和数据总是可寻址,随时准备处理中断和系统调用。与此相反,用户模式地址空间的映射随进程切换的发生而不断变化。
在C++程序进程地址空间,程序中各个变量与常量分别位于哪一个段会详细的介绍虚拟地址空间(进程地址空间)的各个段信息
分页存储管理
- 基本思想
用户程序的地址空间被划分成若干固定大小的区域,称为 “页”,相应地,内存空间分成若干个物理块(页框),页和块的大小相等。可将用户程序的任一页放在内存的任一块中,实现了离散分配。- 等分内存
页式存储管理将内存空间划分成等长的若干物理块,成为物理页面也成为物理块,每个物理块的大小一般取 2 的整数幂。内存的所有物理块从 0 开始编号,称作物理页号 - 逻辑地址
系统将程序的逻辑空间按照同样大小也划分成若干页面,称为逻辑页面也称为页。程序的各个逻辑页面从 0 开始依次编号,称作逻辑页号或相对页号。每个页面内从 0 开始编址,称为页内地址。程序中的逻辑地址由两部分组成:页号P和页内位移量W。
- 等分内存
- 分页存储管理的地址机构
页号的位数x,表示最多2的x次方个页,页内位移量的位数表示页的大小,若页内位移量的位数为y,即页的大小为2的y次方,页内地址从000000000000开始到2的y次方 内存分配
相邻的页面在内存中不一定相邻,即分配给程序的内存块之间不一定连续。对程序地址空间的分页是系统自动进行的,即对用户是透明的。由于页面尺寸为 2 的整数次幂,故相对地址中的高位部分即为页号,低位部分为页内地址。页表
分页系统中,允许将进程的每一页离散地存储在内存的任一物理块中,为了能在内存中找到每个页面对应的物理块,系统为每个进程建立一张页表,用于记录进程逻辑页面与内存物理页面之间的对应关系。页表的作用是实现从页号到物理块号的地址映射,地址空间有多少页,该页表里就登记多少行,且按逻辑页的顺序排列,形如:
地址转换(MMU)
若给定一个逻辑地址为A,页面大小为 L,则页号 P=INT[A/L],页内地址 W=A MOD L
根据上面的三个步骤可以很容易得到结果:物理地址 = 3 8 1024 + 9612 % 8192 = 25996具有快表的地址变换机构
分页系统中,CPU 每次要存取一个数据,都要两次访问内存(访问页表、访问实际物理地址)。为提高地址变换速度,增设一个具有并行查询能力的特殊高速缓冲存储器,称为 “联想存储器” 或 “快表”,存放当前访问的页表项。页面的共享与保护
当多个不同进程中需要有相同页面信息时,可以在主存中只保留一个副本,只要让这些进程各自的有关项中指向内存同一块号即可。同时在页表中设置相应的 “存取权限”,对不同进程的访问权限进行各种必要的限制。页面置换:
当进程在物理内存中运行时,调用到不在物理内存中的虚拟页面时,MMU 注意到该页面没有被映射到物理内存,于是 cpu 陷入到操作系统,这个陷阱称为缺页中断,操作系统找到一个很少使用的页框且把他的内容写入磁盘备份。随后把需要访问的虚拟页面读到刚才回收的页框中,修改映射关系,然后重新启动引起陷阱的指令。
主要的页面置换算法有:页面置换算法
分段存储管理
基本思想
页面是主存物理空间中划分出来的等长的固定区域。分页方式的优点是页长固定,因而便于构造页表、易于管理,且不存在外碎片。但分页方式的缺点是页长与程序的逻辑大小不相关。例如,某个时刻一个子程序可能有一部分在主存中,另一部分则在辅存中。这不利于编程时的独立性,并给换入换出处理、存储保护和存储共享等操作造成麻烦。
另一种划分可寻址的存储空间的方法称为分段。段是按照程序的自然分界划分的长度可以动态改变的区域。通常,程序员把子程序、操作数和常数等不同类型的数据划分到不同的段中(写 c 程序时会用到),并且每个程序可以有多个相同类型的段。
段表本身也是一个段,可以存在辅存中,但一般是驻留在主存中。将用户程序地址空间分成若干个大小不等的段,每段可以定义一组相对完整的逻辑信息。存储分配时,以段为单位,段与段在内存中可以不相邻接,也实现了离散分配。分段地址结构
作业的地址空间被划分为若干个段,每个段定义了一组逻辑信息。例程序段、数据段等。每个段都从 0 开始编址,并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定,因而各段长度不等。整个作业的地址空间是二维的。
在段式虚拟存储系统中,虚拟地址由段号和段内地址组成,虚拟地址到实存地址的变换通过段表来实现。每个程序设置一个段表,段表的每一个表项对应一个段,每个表项至少包括三个字段:有效位(指明该段是否已经调入主存)、段起址 (该段在实存中的首地址) 和段长(记录该段的实际长度)。地址变换
针对每一个虚拟地址,存储管理部件首先以段号 S 为索引访问段表的第 S 个表项。若该表项的有效位为 1,则将虚拟地址的段内地址 D 与该表项的段长字段比较;若段内地址较大则说明地址越界,将产生地址越界中断;否则,将该表项的段起址与段内地址相加,求得主存实地址并访存。如果该表项的有效位为 0,则产生缺页中断,从辅存中调入该页,并修改段表。段式虚拟存储器虚实地址变换过程如图所示。
段页式存储
段页式存储管理的基本思想
段页式存储组织是分段式和分页式结合的存储组织方法,这样可充分利用分段管理和分页管理的优点。- 用分段方法来分配和管理虚拟存储器。程序的地址空间按逻辑单位分成基本独立的段,而每一段有自己的段名,再把每段分成固定大小的若干页。
- 用分页方法来分配和管理实存。即把整个主存分成与上述页大小相等的存储块,可装入作业的任何一页。程序对内存的调入或调出是按页进行的。但它又可按段实现共享和保护。
- 逻辑地址结构。一个逻辑地址用三个参数表示:段号 S;页号 P;页内地址 d。
- 段表、页表、段表地址寄存器。为了进行地址转换,系统为每个作业建立一个段表,并且要为该作业段表中的每一个段建立一个页表。系统中有一个段表地址寄存器来指出作业的段表起始地址和段表长度。
一个逻辑地址为:基地址 x、段号 s、页号 p 和页内地址 d,求物理地址的过程
在段页式系统中,为了便于实现地址变换,须配置一个段表寄存器,其中存放段表始址和段表长 TL。
- 进行地址变换时,首先利用段号 S,将它与段表长 TL 进行比较。若 S小于TL,表示未越界
- 于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置,从中得到该段的页表始址
- 利用逻辑地址中的段内页号 P 来获得对应页的页表项位置,从中读出该页所在的物理块号 b
- 再利用块号 b 和页内地址来构成物理地址。
上图示出了段页式系统中的地址变换机构。在段页式系统中,为了获得一条指令或数据,须三次访问内存。第一次访问是访问内存中的段表,从中取得页表始址;第二次访问是访问内存中的页表,从中取出该页所在的物理块号,并将该块号与页内地址一起形成指令或数据的物理地址;第三次访问才是真正从第二次访问所得的地址中,取出指令或数据。显然,这使访问内存的次数增加了近两倍。为了提高执行速度,在地址变换机构中增设一个高速缓冲寄存器。每次访问它时,都须同时利用段号和页号去检索高速缓存,若找到匹配的表项,便可从中得到相应页的物理块号,用来与页内地址一起形成物理地址;若未找到匹配表项,则仍须再三次访问内存。
逻辑地址,线性地址以及虚拟地址之间的关系
在 Intel 32 位下,并且以代码段为例 (之所以不讲 64 位是因为在 64-bit long mode 下分段直接被禁用了,内存完全平坦,没什么可以讲的…)
- 在 Intel 平台下,逻辑地址 (logical address) 是 selector:offset 这种形式,selector 是 CS 寄存器的值,offset 是 EIP 寄存器的值。
如果用 selector 去 GDT(全局描述符表) 里拿到 segment base address(段基址) 然后加上 offset(段内偏移),这就得到了linear address。
这个过程称作段式内存管理。如果再把 linear address 切成四段,用前三段分别作为索引去 PGD、PMD、Page Table 里查表,最终就会得到一个页表项 (Page Table Entry),那里面的值就是一页物理内存的起始地址,把它加上 linear address 切分之后第四段的内容 (又叫页内偏移) 就得到了最终的 physical address。这个过程称作页式内存管理。 - virtual address,这是个什么东西?
其实在 Intel IA-32 手册里并没有提到这个术语,但是在内核的确是用到了这个概念,比如__va 和__pa 这两个宏定义。
看似神秘的 virtual address 究其本质就是程序里面使用的地址比如一个指针值,指针的本质就是 EIP 寄存器里的值,说直白点,virtual address 就是 EIP 寄存器的值。上面说过,logical address 由 selector 和 offset 两部分组成,offset 也是 EIP 寄存器的值,所以结论为:logical address 的 offset 正是 virtual address,它俩是一个东西。既然搞明白了 logical address 和 virtual address 的关系。
那么再来看下,linear address 和 virtual address 是什么关系。在上面讲到的段式内存管理中,Linux 内核会将 segment base address(段基址) 设成 0,于是就有 linear address = 0+offset,又因为 virtual address 就是 offset,所以算出的 linear address 在数值上等于 virtual address,注意,是数值上等于,它们之间是差了段基址的,只不过段基址为 0 罢了。网上很多资料认为逻辑地址是虚拟地址的别名,其实它们不是一个东西。还有很多资料把线性地址当作虚拟地址的别名,其实它们也不是一个东西,只是 Linux 在 x86 下将它们搞得数值相等而已,虽然值相等但是本质不同。
linux内存分配算法:伙伴系统和slab
外部内存锁片
外部内存碎片就是内存被分割成很小很小的一些块,这些块虽然是空闲的,但是因为是不连续的,小到无法使用。
伙伴系统
Linux 便是采用这著名的伙伴系统算法来解决外部碎片的问题。把所有的空闲页框分组为 11 块链表,每一块链表分别包含大小为1,2,4,8,16,32,64,128,256,512 和 1024 个连续的页框。对1024 个页框的最大请求对应着 4MB 大小的连续RAM 块。每一块的第一个页框的物理地址是该块大小的整数倍。例如,大小为 16个页框的块,其起始地址是 16 * 2^12 (2^12 = 4096,这是一个常规页的大小)的倍数。
假设要请求一个256(129~256)个页框的块。算法先在256个页框的链表中检查是否有一个空闲块。如果没有这样的块,算法会查找下一个更大的页块,也就是,在512个页框的链表中找一个空闲块。如果存在这样的块,内核就把512的页框分成两等分,一般用作满足需求,另一半则插入到256个页框的链表中。如果在512个页框的块链表中也没找到空闲块,就继续找更大的块——1024个页框的块。如果这样的块存在,内核就把1024个页框块的256个页框用作请求,然后剩余的768个页框中拿512个插入到512个页框的链表中,再把最后的256个插入到256个页框的链表中。如果1024个页框的链表还是空的,算法就放弃并发出错误信号。
简而言之,就是在分配内存时,首先从空闲的内存中搜索比申请的内存大的最小的内存块。如果这样的内存块存在,则将这块内存标记为“已用”,同时将该内存分配给应用程序。如果这样的内存不存在,则操作系统将寻找更大块的空闲内存,然后将这块内存平分成两部分,一部分返回给程序使用,另一部分作为空闲的内存块等待下一次被分配。
以上过程的逆过程就是页框块的释放过程,也是该算法名字的由来。
假设要释放一个256个页框的块,算法就把其插入到256个页框的链表中,然后检查与该内存相邻的内存,如果存在同样大小为256个页框的并且空闲的内存,就将这两块内存合并成512个页框,然后插入到512个页框的链表中,如果不存在,就没有后面的合并操作。然后再进一步检查,如果合并后的512个页框的内存存在大小为512个页框的相邻且空闲的内存,则将两者合并,然后插入到1024个页框的链表中。
简而言之,就是当程序释放内存时,操作系统首先将该内存回收,然后检查与该内存相邻的内存是否是同样大小并且同样处于空闲的状态,如果是,则将这两块内存合并,然后程序递归进行同样的检查。
内部内存碎片
内部碎片是已经被分配出去(能明确指出属于哪个进程)的内存空间大于请求所需的内存空间,不能被利用的内存空间就是内部碎片。
为了有效的利用内存,使内存产生更少的外部碎片,要对内存分页,内存以页为单位来使用,最后一页往往装不满,于是形成了内部碎片
slab高速缓存
通俗的讲,slab 就是专门为某一模块预先一次性申请一定数量的内存备用,当这个模块想要使用内存的时候,就不再需要从系统中分配内存了(因为从系统中申请内存的时间开销相对来说比较大),而是直接从预申请的内存中拿出一部分来使用,这样就提高了这个模块的内存申请速度。
条件:
- 当某一子系统需要频繁地申请和释放内存时,使用 slab 才会合理一些。
- 利用 slab 申请的内存必须是大小固定的。
Linux 内核提供了 slab 层(slab 分配器),其扮演了通用数据结构缓存层的角色。slab 层把不同的对象划分为所谓高速缓存组,其中每个高速缓存组都存放不同类型的对象,每种对象类型对应一个高速缓存。例如,一个高速缓存用于存放进程描述符,而另一个高速缓存存放索引节点对象,然后这些高速缓存又被划分为 slab。slab 由一个或多个物理上连续的页组成。一般情况下,slab 也就是仅仅由一页组成,每个高速缓存可以由多个 slab 组成。
slab 分配器把每一个请求的内存称之为对象。每个 slab 都包含一些对象成员,这里的对象指的是被缓存的数据结构。每个 slab 处于三种状态之一:满、部分满或空。一个满的 slab 没有空闲的对象(slab 中的对象都已被分配)。一个空的 slab 没有分配出任何对象(slab 中所有对象都是空闲的)。一个部分满的 slab 有一些对象已分配出去,有些对象还空闲着。当内核的某一部分需要一个新的对象时,先从部分满的 slab 中进行分配,如果没有部分满的 slab,就从空的 slab 中进行分配。如果没有空的 slab,就要创建一个 slab 了。
高速缓存、slab、对象之间的关系: