Linux 操作系统原理 — 内存 — 内存分配

06/21 12:23
阅读数 1.1K

目录

内存分配算法

Linux 系统把物理内存划分 4K 大小的内存页(Page),也称作页框(Page Frame),物理内存的分配和回收都是基于内存页进行,把物理内存分页管理有很多好处。假如系统请求小块内存,可以预先分配一页给它,避免了反复的申请和释放小块内存带来频繁的系统开销。假如系统需要大块内存,则可以用多页内存拼凑,而不必要求大块连续内存。

注意,如果就直接这样把内存分页使用,不再加额外的管理还是存在一些问题,下面我们来看下,系统在多次分配和释放物理页的时候会遇到哪些问题。

在内核态申请内存比在用户态申请内存要更为直接,它没有采用用户态那种延迟分配内存技术。内核认为一旦有内核函数申请内存,那么就必须立刻满足该申请内存的请求,并且这个请求一定是正确合理的。相反,对于用户态申请内存的请求,内核总是尽量延后分配物理内存,用户进程总是先获得一个虚拟内存区的使用权,最终通过缺页异常获得一块真正的物理内存。

IA32(Intel x86 32 位)架构支持 4GB 内存的寻址,其中的内核虚拟地址空间只有 1GB 大小(从 3GB 到 4GB),因此可以直接将 1GB 大小的物理内存(即常规内存)映射到内核地址空间,但超出 1GB 大小的物理内存(即高端内存)就不能映射到内核空间。为此,内核采取了下面的方法使得内核可以使用所有的物理内存。

  1. 高端内存不能全部映射到内核空间,也就是说这些物理内存没有对应的线性地址。不过,内核为每个物理页框都分配了对应的页框描述符,所有的页框描述符都保存在 mem_map 数组中,因此每个页框描述符的线性地址都是固定存在的。内核此时可以使用 alloc_pages() 和 alloc_page() 来分配高端内存,因为这些函数返回页框描述符的线性地址。

  2. 内核地址空间的后 128MB 专门用于映射高端内存,否则,没有线性地址的高端内存不能被内核所访问。这些高端内存的内核映射显然是暂时映射的,否则也只能映射 128MB 的高端内存。当内核需要访问高端内存时就临时在这个区域进行地址映射,使用完毕之后再用来进行其他高端内存的映射。

由于要进行高端内存的内核映射,因此直接能够映射的物理内存大小只有 896MB,该值保存在 high_memory 中。内核地址空间的线性地址区间如下图所示:

在这里插入图片描述

从图中可以看出,内核采用了三种机制将高端内存映射到内核空间:永久内核映射、固定映射和 vmalloc 机制。

物理内存分配

内存碎片

基于物理内存在内核空间中的映射原理,物理内存的管理方式也有所不同。

物理页管理面临问题:物理内存页分配会出现外部碎片和内部碎片问题,所谓的内部和外部是针对 “页框内外” 而言的,一个页框内的内存碎片是内部碎片,多个页框间的碎片是外部碎片。

  • 外部碎片:当需要分配大块内存的时候,要用好几页组合起来才够,而系统分配物理内存页的时候会尽量分配连续的内存页面,频繁的分配与回收物理页导致大量的小块内存夹杂在已分配页面中间,形成外部碎片。
    在这里插入图片描述
  • 内部碎片:物理内存是按页来分配的,这样当实际只需要很小内存的时候,也会分配至少是 4K 大小的页面,而内核中有很多需要以字节为单位分配内存的场景,这样本来只想要几个字节而已却不得不分配一页内存,除去用掉的字节剩下的就形成了内部碎片。
    在这里插入图片描述

内核中物理内存的管理机制主要有伙伴算法,Slab 高速缓存和 vmalloc 机制。其中伙伴算法和 Slab 高速缓存都在物理内存映射区分配物理内存,而 vmalloc 机制则在高端内存映射区分配物理内存。

基本原理:内存分配较小,并且分配的这些小的内存生存周期又较长,反复申请后将产生内存碎片的出现。

  • 优点:提高分配速度,便于内存管理,防止内存泄露。
  • 缺点:大量的内存碎片会使系统缓慢,内存使用率低,浪费大。

如何避免内存碎片

  • 少用动态内存分配的函数(尽量使用栈空间)。
  • 分配内存和释放的内存尽量在同一个函数中。
  • 尽量一次性申请较大的内存,而不要反复申请小内存。
  • 尽可能申请大块的 2 的指数幂大小的内存空间。
  • 外部碎片避免 — 伙伴系统算法。
  • 内部碎片避免 — slab 算法。
  • 自己进行内存管理工作,设计内存池。

伙伴(Buddy)分配算法

外部碎片:的是还没有被分配出去(不属于任何进程),但由于太小了无法分配给申请内存空间的新进程的内存空闲区域3) 组织结构。

伙伴系统算法(Buddy system),顾名思义,就是把相同大小的页框块用链表串起来,页框块就像手拉手的好伙伴,也是这个算法名字的由来。伙伴算法负责大块连续物理内存的分配和释放,以页框为基本单位。该机制可以避免外部碎片。

具体的,所有的空闲页框分组为 11 个块链表,每个块链表分别包含大小为 1,2,4,8,16,32,64,128,256,512 和 1024 个连续页框的页框块。最大可以申请 1024 个连续页框,对应 4MB 大小的连续内存。

在这里插入图片描述

在这里插入图片描述
因为任何正整数都可以由 2^n 的和组成,所以总能找到合适大小的内存块分配出去,减少了外部碎片产生 。

如此的,假设需要申请 4 个页框,但是长度为 4 个连续页框块链表没有空闲的页框块,伙伴系统会从连续 8 个页框块的链表获取一个,并将其拆分为两个连续 4 个页框块,取其中一个,另外一个放入连续 4 个页框块的空闲链表中。释放的时候会检查,释放的这几个页框前后的页框是否空闲,能否组成下一级长度的块。

命令查看:

[root@c-dev ~]# cat /proc/buddyinfo
Node 0, zone      DMA      1      0      0      0      2      1      1      0      1      1      3
Node 0, zone    DMA32    189    209    119     80     38     17     11      1      1      2    627
Node 0, zone   Normal   1298   1768   1859    661    743    461    275    133     68     61   2752

申请和回收

申请算法

  • 申请 2i 个页块存储空间,如果 2i 对应的块链表有空闲页块,则分配给应用。
  • 如果没有空闲页块,则查找 2**(i 1) 对应的块链表是否有空闲页块,如果有,则分配 2i 块链表节点给应用,另外 2i 块链表节点插入到 2**i 对应的块链表中。
  • 如果 2**(i 1) 块链表中没有空闲页块,则重复步骤 2,直到找到有空闲页块的块链表。
  • 果仍然没有,则返回内存分配失败。

回收算法

  • 释放 2i 个页块存储空间,查找 2i 个页块对应的块链表,是否有与其物理地址是连续的页块,如果没有,则无需合并。
    在这里插入图片描述
  • 如果有,则合并成 2**(i1) 的页块,以此类推,继续查找下一级块链接,直到不能合并为止。
    在这里插入图片描述

条件

  • 两个块具有相同的大小。
  • 它们的物理地址是连续的.
  • 页块大小相同。

如何分配 4M 以上内存?

  • 为何限制大块内存分配?

    • 分配的内存越大, 失败的可能性越大。
    • 大块内存使用场景少。
  • 内核中获取 4M 以上大内存的方法

    • 修改 MAX_ORDER,重新编译内核。
    • 内核启动选型传递 “mem=” 参数, 如:“mem=80M”,预留部分内存;
    • 然后通过 request_mem_region 和 ioremap_nocache 将预留的内存映射到模块中。需要修改内核启动参数,无需重新编译内核。但这种方法不支持 x86 架构, 只支持 ARM、PowerPC 等非 x86 架构。
    • 在 start_kernel 中 mem_init 函数之前调用 alloc_boot_mem 函数预分配大块内存,需要重新编译内核。
    • vmalloc 函数,内核代码使用它来分配在虚拟内存中连续但在物理内存中不一定连续的内存。

反碎片机制

不可移动页:

  • 这些页在内存中有固定的位置,不能够移动,也不可回收。
  • 内核代码段,数据段,内核 kmalloc() 出来的内存,内核线程占用的内存等。

可回收页:

  • 这些页不能移动,但可以删除。内核在回收页占据了太多的内存时或者内存短缺时进行页面回收

可移动页:

  • 这些页可以任意移动,用户空间应用程序使用的页都属于该类别。它们是通过页表映射的。
  • 当它们移动到新的位置,页表项也会相应的更新。

Slab 算法

Linux 所使用的 slab 分配器的基础是 Jeff Bonwick 为 SunOS 操作系统首次引入的一种算法。它的基本思想是:将内核中经常使用的对象放到高速缓存中,并且由系统保持为初始的可利用状态。比如进程描述符,内核中会频繁对此数据进行申请和释放。

一般来说,内核对象的生命周期是:分配内存 -> 初始化 -> 释放内存,内核中有大量的小对象,比如:文件描述结构对象、任务描述结构对象,如果按照伙伴系统按页分配和释放内存,就会对小对象频繁的执行分配内存 -> 初始化 -> 释放内存的过程,会非常消耗性能。

伙伴系统分配出去的内存还是以页框为单位,而对于内核的很多场景都是分配小片内存,远用不到一页内存大小的空间。Slab 分配器最初是为了解决物理内存的内部碎片而提出的,它将内核中常用的数据结构看做对象。Slab 分配器为每一种对象建立高速缓存,通过将内存按使用对象不同再划分成不同大小的空间,应用于内核对象的缓存,内核对该对象的分配和释放均是在这块高速缓存中操作。

可见,Slab 内存分配器是对伙伴分配算法的补充。Slab 缓存负责小块物理内存的分配,并且它也作为高速缓存,主要针对内核中经常分配并释放的对象。

  • 减少伙伴算法在分配小块连续内存时所产生的内部碎片。
  • 将频繁使用的对象缓存起来,减少分配、初始化和释放对象的时间开销。
  • 通过着色技术调整对象以更好的使用硬件高速缓存。

在这里插入图片描述

对于每个内核中的相同类型的对象,如:task_struct、file_struct 等需要重复使用的小型内核数据对象,都会有个 Slab 缓存池,缓存住大量常用的「已经初始化」的对象,每当要申请这种类型的对象时,就从缓存池的 Slab 列表中分配一个出去;而当要释放时,将其重新保存在该列表中,而不是直接返回给伙伴系统,从而避免内部碎片,同时也大大提高了内存分配性能。

主要优点:

  • Slab 内存管理基于内核小对象,不用每次都分配一页内存,充分利用内存空间,避免内部碎片。
  • Slab 对内核中频繁创建和释放的小对象做缓存,重复利用一些相同的对象,减少内存分配次数。

slab 分配器的结构

  • 由于对象是从 slab 中分配和释放的,因此单个 slab 可以在 slab 列表之间进行移动。
  • slabs_empty 列表中的 slab 是进行回收(reaping)的主要备选对象。
  • slab 还支持通用对象的初始化,从而避免了为同一目而对一个对象重复进行初始化。

在这里插入图片描述

在这里插入图片描述
kmem_cache 是一个cache_chain 的链表组成节点,代表的是一个内核中的相同类型的「对象高速缓存」,每个kmem_cache 通常是一段连续的内存块,包含了三种类型的 slabs 链表:

  • slabs_full:完全分配的 slab 链表
  • slabs_partial:部分分配的 slab 链表
  • slabs_empty:没有被分配对象的 slab 链表

kmem_cache 中有个重要的结构体 kmem_list3 包含了以上三个数据结构的声明。

在这里插入图片描述

slab 是 Slab 分配器的最小单位,在实现上一个 slab 由一个或多个连续的物理页组成(通常只有一页)。单个 slab 可以在 slab 链表之间移动,例如:如果一个半满 slabs_partial 链表被分配了对象后变满了,就要从 slabs_partial 中删除,同时插入到全满 slabs_full 链表中去。内核 slab 对象的分配过程是这样的:

在这里插入图片描述

  1. 如果 slabs_partial 链表还有未分配的空间,分配对象,若分配之后变满,移动 slab 到 slabs_full 链表。
  2. 如果 slabs_partial 链表没有未分配的空间,进入下一步。
  3. 如果 slabs_empty 链表还有未分配的空间,分配对象,同时移动 slab 进入 slabs_partial 链表。
  4. 如果 slabs_empty 为空,请求伙伴系统分页,创建一个新的空闲 slab, 按步骤 3 分配对象。

查看 Slab 内存信息:

[root@c-dev ~]# cat /proc/slabinfo
slabinfo - version: 2.1
# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <limit> <batchcount> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>
isofs_inode_cache     50     50    640   25    4 : tunables    0    0    0 : slabdata      2      2      0
kvm_async_pf           0      0    136   30    1 : tunables    0    0    0 : slabdata      0      0      0
kvm_vcpu               0      0  14976    2    8 : tunables    0    0    0 : slabdata      0      0      0
xfs_dqtrx              0      0    528   31    4 : tunables    0    0    0 : slabdata      0      0      0
xfs_dquot              0      0    488   33    4 : tunables    0    0    0 : slabdata      0      0      0
xfs_ili            40296  40296    168   24    1 : tunables    0    0    0 : slabdata   1679   1679      0
xfs_inode          41591  41616    960   34    8 : tunables    0    0    0 : slabdata   1224   1224      0
xfs_efd_item        1053   1053    416   39    4 : tunables    0    0    0 : slabdata     27     27      0

实时显示内核中的 Slab 内存缓存信息:

$ slabtop

slab 高速缓存

Slab 高速缓存分为以下两类:

  1. 通用高速缓存:slab 分配器中用 kmem_cache 来描述高速缓存的结构,它本身也需要 slab 分配器对其进行高速缓存。cache_cache 保存着对高速缓存描述符的高速缓存,是一种通用高速缓存,保存在 cache_chain 链表中的第一个元素。另外,slab 分配器所提供的小块连续内存的分配,也是通用高速缓存实现的。通用高速缓存所提供的对象具有几何分布的大小,范围为 32 到 131072 字节。内核中提供了 kmalloc() 和 kfree() 两个接口分别进行内存的申请和释放。slab 分配器所提供的小块连续内存的分配是通过通用高速缓存实现的。通用高速缓存所提供的对象具有几何分布的大小,范围为 32 到 131072 字节。内核中提供了 kmalloc() 和 kfree() 两个接口分别进行内存的申请和释放。

  2. 专用高速缓存:内核为专用高速缓存的申请和释放提供了一套完整的接口,根据所传入的参数为指定的对象分配 Slab 缓存。内核为专用高速缓存的申请和释放提供了一套完整的接口,根据所传入的参数为具体的对象分配 slab 缓存。kmem_cache_create() 用于对一个指定的对象创建高速缓存。它从 cache_cache 普通高速缓存中为新的专有缓存分配一个高速缓存描述符,并把这个描述符插入到高速缓存描述符形成的 cache_chain 链表中。kmem_cache_alloc() 在其参数所指定的高速缓存中分配一个 slab。相反, kmem_cache_free() 在其参数所指定的高速缓存中释放一个 slab。

分区页框分配器

分区页框分配器(Zoned Page Frame Allocator),处理对连续页框的内存分配请求。分区页框管理器分为两大部分:前端的管理区分配器和伙伴系统,如下图:

在这里插入图片描述
管理区分配器负责搜索一个能满足请求页框块大小的管理区。在每个管理区中,具体的页框分配工作由伙伴系统负责。为了达到更好的系统性能,单个页框的申请工作直接通过 per-CPU 页框高速缓存完成。

per-CPU 页框高速缓存:内核经常请求和释放单个页框,该缓存包含预先分配的页框,用于满足本地 CPU 发出的单一页框请求。

该分配器通过几个函数和宏来请求页框,它们之间的封装关系如下图所示。

在这里插入图片描述
这些函数和宏将核心的分配函数 __alloc_pages_nodemask() 封装,形成满足不同分配需求的分配函数。其中,alloc_pages() 系列函数返回物理内存首页框描述符,__get_free_pages() 系列函数返回内存的线性地址。

非连续内存区内存的分配

内核通过 vmalloc() 来申请非连续的物理内存,若申请成功,该函数返回连续内存区的起始地址,否则,返回 NULL。vmalloc() 和 kmalloc() 申请的内存有所不同,kmalloc() 所申请内存的线性地址与物理地址都是连续的,而 vmalloc() 所申请的内存线性地址连续而物理地址则是离散的,两个地址之间通过内核页表进行映射。

vmalloc 机制使得内核通过连续的线性地址来访问非连续的物理页框,这样可以最大限度的使用高端物理内存。

vmalloc() 的工作方式理解起来很简单:

  1. 寻找一个新的连续线性地址空间;
  2. 依次分配一组非连续的页框;
  3. 为线性地址空间和非连续页框建立映射关系,即修改内核页表;

vmalloc() 的内存分配原理与用户态的内存分配相似,都是通过连续的虚拟内存来访问离散的物理内存,并且虚拟地址和物理地址之间是通过页表进行连接的,通过这种方式可以有效的使用物理内存。但是应该注意的是,vmalloc() 申请物理内存时是立即分配的,因为内核认为这种内存分配请求是正当而且紧急的;相反,用户态有内存请求时,内核总是尽可能的延后,毕竟用户态跟内核态不在一个特权级。

虚拟内存的分配

虚拟内存的分配,包括用户空间虚拟内存和内核空间虚拟内存。

注意,分配的虚拟内存还没有映射到物理内存,只有当访问申请的虚拟内存时,才会发生缺页异常,再通过上面介绍的伙伴系统和 slab 分配器申请物理内存。

内核空间内存分配

先来回顾一下内核地址空间。

在这里插入图片描述
kmalloc 和 vmalloc 分别用于分配不同映射区的虚拟内存。
在这里插入图片描述

基本原理:

  1. 先申请分配一定数量的、大小相等(一般情况下)的内存块留作备用。
  2. 当有新的内存需求时,就从内存池中分出一部分内存块,若内存块不够再继续申请新的内存。
  3. 这样做的一个显著优点是尽量避免了内存碎片,使得内存分配效率得到提升。

内核 API:

  • mempool_create 创建内存池对象
  • mempool_alloc 分配函数获得该对象
  • mempool_free 释放一个对象
  • mempool_destroy 销毁内存池

在这里插入图片描述

kmalloc

kmalloc() 分配的虚拟地址范围在内核空间的直接内存映射区。

按字节为单位虚拟内存,一般用于分配小块内存,释放内存对应于 kfree ,可以分配连续的物理内存。函数原型在 <linux/kmalloc.h> 中声明,一般情况下在驱动程序中都是调用 kmalloc() 来给数据结构分配内存。

kmalloc 是基于 Slab 分配器的,同样可以用 cat /proc/slabinfo 命令,查看 kmalloc 相关 slab 对象信息,下面的 kmalloc-8、kmalloc-16 等等就是基于 Slab 分配的 kmalloc 高速缓存。

在这里插入图片描述

vmalloc

vmalloc 分配的虚拟地址区间,位于 vmalloc_start 与 vmalloc_end 之间的动态内存映射区。

一般用分配大块内存,释放内存对应于 vfree,分配的虚拟内存地址连续,物理地址上不一定连续。函数原型在 <linux/vmalloc.h> 中声明。一般用在为活动的交换区分配数据结构,为某些 I/O 驱动程序分配缓冲区,或为内核模块分配空间。

用户空间内存分配(malloc)

用户态内存分配函数:

  • alloca 是向栈申请内存,因此无需释放。
  • malloc 所分配的内存空间未被初始化,使用 malloc() 函数的程序开始时(内存空间还没有被重新分配)能正常运行,但经过一段时间后(内存空间已被重新分配)可能会出现问题。
  • calloc 会将所分配的内存空间中的每一位都初始化为零。
  • realloc 扩展现有内存空间大小。
    • 如果当前连续内存块足够 realloc 的话,只是将 p 所指向的空间扩大,并返回 p 的指针地址。这个时候 q 和 p 指向的地址是一样的。
    • 如果当前连续内存块不够长度,再找一个足够长的地方,分配一块新的内存,q,并将 p 指向的内容 copy 到 q,返回 q。并将 p 所指向的内存空间删除。

malloc 申请内存

malloc 用于申请用户空间的虚拟内存,当申请小于 128KB 小内存的时,malloc 使用 sbrk 或 brk 分配内存;当申请大于 128KB 的内存时,使用 mmap 函数申请内存;

存在的问题:由于 brk/sbrk/mmap 属于系统调用,如果每次申请内存都要产生系统调用开销,CPU 在用户态和内核态之间频繁切换,非常影响性能。而且,堆是从低地址往高地址增长,如果低地址的内存没有被释放,高地址的内存就不能被回收,容易产生内存碎片。

解决:因此,malloc 采用的是内存池的实现方式,先申请一大块内存,然后将内存分成不同大小的内存块,然后用户申请内存时,直接从内存池中选择一块相近的内存块分配出去。

在这里插入图片描述

  • 调用 malloc 函数时,它沿 free_chuck_list 连接表寻找一个大到足以满足用户请求所需要的内存块。
    在这里插入图片描述

  • free_chuck_list 连接表的主要工作是维护一个空闲的堆空间缓冲区链表。

  • 如果空间缓冲区链表没有找到对应的节点,需要通过系统调用 sys_brk 延伸进程的栈空间。

在这里插入图片描述

DMA 内存

直接内存访问是一种硬件机制,它允许外围设备和主内存之间直接传输它们的 I/O 数据,而不需要系统处理器的参与

DMA 控制器的功能:

  • 能向 CPU 发出系统保持(HOLD)信号,提出总线接管请求。
  • 当 CPU 发出允许接管信号后,负责对总线的控制,进入 DMA 方式。
  • 能对存储器寻址及能修改地址指针,实现对内存的读写操作。
  • 能决定本次 DMA 传送的字节数,判断 DMA 传送是否结束。
  • 发出 DMA 结束信号,使 CPU 恢复正常工作状态。

DMA 信号:

  • DREQ:DMA 请求信号。是外设向 DMA 控制器提出要求,DMA 操作的申请信号。
  • DACK:DMA 响应信号。是 DMA 控制器向提出 DMA 请求的外设表示已收到请求和正进行处理的信号。
  • HRQ:DMA 控制器向 CPU 发出的信号,要求接管总线的请求信号。
  • HLDA:CPU 向 DMA 控制器发出的信号,允许接管总线的应答信号。
    在这里插入图片描述

缺页异常

  • 通过 get_free_pages 申请一个或多个物理页面。
  • 换算 addr 在进程 pdg 映射中所在的 pte 地址。
  • 将 addr 对应的 pte 设置为物理页面的首地址。
  • 系统调用:Brk—申请内存小于等于 128kb,do_map—申请内存大于 128kb。

在这里插入图片描述

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部