Linux内核的内存管理

用户空间分配内存可以使用C语言中的malloc和C++的new,当然了new的底层其实也是malloc,这个malloc就去分配内存给我们。但是这个不一定,你用了malloc他就会去立即给你分配,也可能是你实际去访问内存的时候,他没分配好,然后产生缺页中断才去分配。

在内核空间分配内存,首先先说物理内存,先不考虑虚拟地址,分配物理内存涉及到伙伴系统和slab机制。这是分配物理内存的方法,然后他的上一层就是虚拟内存。虚拟内存和物理内存就是靠页表关联起来的,然后MMU和TLB通过页表能够查询到具体的对应的地址。

1、物理内存

伙伴系统

在实际应用中,经常需要分配一组连续的页框,而频繁地申请和释放不同大小的连续页框,必然导致在已分配页框的内存块中分散了许多小块的空闲页框。这样,即使这些页框是空闲的,其他需要分配连续页框的应用也很难得到满足。
为了避免出现这种情况,Linux内核中引入了伙伴系统算法(buddy system)。把所有的空闲页框分组为11个块链表,每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续页框的页框块。最大可以申请1024个连续页框,对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。
假设要申请一个256个页框的块,先从256个页框的链表中查找空闲块,如果没有,就去512个页框的链表中找,找到了则将页框块分为2个256个页框的块,一个分配给应用,另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块,继续向1024个页框的链表查找,如果仍然没有,则返回错误。

页框块在释放时,会主动将两个连续的页框块合并为一个较大的页框块。

Buddy算法的优缺点:

1)尽管伙伴内存算法在内存碎片问题上已经做的相当出色,但是该算法中,一个很小的块往往会阻碍一个大块的合并,一个系统中,对内存块的分配,大小是随机的,一片内存中仅一个小的内存块没有释放,旁边两个大的就不能合并。

2)算法中有一定的浪费现象,伙伴算法是按2的幂次方大小进行分配内存块,当然这样做是有原因的,即为了避免把大的内存块拆的太碎,更重要的是使分配和释放过程迅速。但是他也带来了不利的一面,如果所需内存大小不是2的幂次方,就会有部分页面浪费。有时还很严重。比如原来是1024个块,申请了16个块,再申请600个块就申请不到了,因为已经被分割了。

3)另外拆分和合并涉及到 较多的链表和位图操作,开销还是比较大的。

Buddy(伙伴的定义):

这里给出伙伴的概念,满足以下三个条件的称为伙伴:
1)两个块大小相同;
2)两个块地址连续;
3)两个块必须是同一个大块中分离出来的;

Buddy算法的分配原理:

假如系统需要4(2x2)个页面大小的内存块,该算法就到free_area[2]中查找,如果链表中有空闲块,就直接从中摘下并分配出去。如果没有,算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块,则将其从链表中摘下,分成等大小的两部分,前四个页面作为一个块插入free_area[2],后4个页面分配出去,free_area[3]中也没有,就再向上查找,如果free_area[4]中有,就将这16(2x2x2x2)个页面等分成两份,前一半挂如free_area[3]的链表头部,后一半的8个页等分成两等分,前一半挂free_area[2]
的链表中,后一半分配出去。假如free_area[4]也没有,则重复上面的过程,知道到达free_area数组的最后,如果还没有则放弃分配。

Buddy算法的释放原理:

内存的释放是分配的逆过程,也可以看作是伙伴的合并过程。当释放一个块时,先在其对应的链表中考查是否有伙伴存在,如果没有伙伴块,就直接把要释放的块挂入链表头;如果有,则从链表中摘下伙伴,合并成一个大块,然后继续考察合并后的块在更大一级链表中是否有伙伴存在,直到不能合并或者已经合并到了最大的块(222222222个页面)。

slab机制

slab是Linux操作系统的一种内存分配机制。其工作是针对一些经常分配并释放的对象,如进程描述符等,这些对象的大小一般比较小,如果直接采用伙伴系统来进行分配和释放,不仅会造成大量的内碎片,而且处理速度也太慢。而slab分配器是基于对象进行管理的,相同类型的对象归为一类(如进程描述符就是一类),每当要申请这样一个对象,slab分配器就从一个slab列表中分配一个这样大小的单元出去,而当要释放时,将其重新保存在该列表中,而不是直接返回给伙伴系统,从而避免这些内碎片。slab分配器并不丢弃已分配的对象,而是释放并把它们保存在内存中。当以后又要请求新的对象时,就可以从内存直接获取而不用重复初始化。

Linux 的slab 可有三种状态:
满的:slab 中的所有对象被标记为使用。
空的:slab 中的所有对象被标记为空闲。
部分:slab 中的对象有的被标记为使用,有的被标记为空闲。
slab 分配器首先从部分空闲的slab 进行分配。如没有,则从空的slab 进行分配。如没有,则从物理连续页上分配新的slab,并把它赋给一个cache ,然后再从新slab 分配空间。

与传统的内存管理模式相比, slab 缓存分配器提供了很多优点。
1、内核通常依赖于对小对象的分配,它们会在系统生命周期内进行无数次分配。
2、slab 缓存分配器通过对类似大小的对象进行缓存而提供这种功能,从而避免了常见的碎片问题。
3、slab 分配器还支持通用对象的初始化,从而避免了为同一目的而对一个对象重复进行初始化。
4、slab 分配器还可以支持硬件缓存对齐和着色,这允许不同缓存中的对象占用相同的缓存行,从而提高缓存的利用率并获得更好的性能。

2、虚拟内存

进程的虚拟内存空间会被分成不同的若干区域,每个区域都有其相关的属性和用途,一个合法的地址总是落在某个区域当中的,这些区域也不会重叠。在linux内核中,这样的区域被称之为虚拟内存区域(virtual memory areas),简称 VMA。一个vma就是一块连续的线性地址空间的抽象,它拥有自身的权限(可读,可写,可执行等等) ,每一个虚拟内存区域都由一个相关的 struct vm_area_struct 结构来描述。

从进程的角度来讲,VMA 其实是虚拟空间的内存块,一个进程的所有资源由多个内存块组成,所以,一个进程的描述结构 task_struct 中首先包含Linux的内存描述符 mm_struct 结构。

struct task_struct {
.......
    struct mm_struct *mm;
.......
}

mm_struct 中进而包含了 vm_area_struct :

struct mm_struct {
          struct vm_area_struct * mmap;       /* list of VMAs */
          struct rb_root mm_rb;
          struct vm_area_struct * mmap_cache;      /* last find_vma result */
.......
}

一个进程的每个 VMA 块都会链接到中的链表和红黑树:

  1. mmap 形成一个单链表,一个进程的所有 VMA 都链接到这个链表,链表头是 mm->mmap
  2. mm_rb 是红黑树节点,每个进程都一个 VMA 红黑树

VMA 按照起始地址递增的方式,插入到 mm_struct->mmap 链表。当进程拥有大量的 VMA 的时候,搜索效率比较低,所以哟娜那个到红黑树来加快查找。

接下来看看这次的主角 vm_area_struct

struct vm_area_struct {
    struct mm_struct * vm_mm;    /* 所属的内存描述符 */
    unsigned long vm_start;    /* vma的起始地址 */
    unsigned long vm_end;        /* vma的结束地址 */
    /* 该vma的在一个进程的vma链表中的前驱vma和后驱vma指针,链表中的vma都是按地址来排序的*/
    struct vm_area_struct *vm_next, *vm_prev;
    pgprot_t vm_page_prot;        /* vma的访问权限 */
    unsigned long vm_flags;    /* 标识集 */
    struct rb_node vm_rb;      /* 红黑树中对应的节点 */
    /*
     * For areas with an address space and backing store,
     * linkage into the address_space->i_mmap prio tree, or
     * linkage to the list of like vmas hanging off its node, or
     * linkage of vma in the address_space->i_mmap_nonlinear list.
     */
    /* shared联合体用于和address space关联 */
    union {
        struct {
            struct list_head list;/* 用于链入非线性映射的链表 */
            void *parent;    /* aligns with prio_tree_node parent */
            struct vm_area_struct *head;
        } vm_set;
        struct raw_prio_tree_node prio_tree_node;/*线性映射则链入i_mmap优先树*/
    } shared;
    /*
     * A file's MAP_PRIVATE vma can be in both i_mmap tree and anon_vma
     * list, after a COW of one of the file pages.    A MAP_SHARED vma
     * can only be in the i_mmap tree.  An anonymous MAP_PRIVATE, stack
     * or brk vma (with NULL file) can only be in an anon_vma list.
     */

    /*anno_vma_node和annon_vma用于管理源自匿名映射的共享页*/
    struct list_head anon_vma_node;    /* Serialized by anon_vma->lock */
    struct anon_vma *anon_vma;    /* Serialized by page_table_lock */
    /* Function pointers to deal with this struct. */
    /*该vma上的各种标准操作函数指针集*/
    const struct vm_operations_struct *vm_ops;
    /* Information about our backing store: */
    unsigned long vm_pgoff;        /* 映射文件的偏移量,以PAGE_SIZE为单位 */
    struct file * vm_file;            /* 映射的文件,没有则为NULL */
    void * vm_private_data;        /* was vm_pte (shared mem) */
    unsigned long vm_truncate_count;/* truncate_count or restart_addr */
#ifndef CONFIG_MMU
    struct vm_region *vm_region;    /* NOMMU mapping region */
#endif
#ifdef CONFIG_NUMA
    struct mempolicy *vm_policy;    /* NUMA policy for the VMA */
#endif
};

3、页表、MMU、TLB

Linux内核中采用了一种同时适用于32位和64位系统的内存分页模型,对于32位系统来说,两级页表足够用了,而在x86_64系统中,用到了四级页表。四级页表分别为:

页全局目录PGD(Page Global Directory)

页上级目录PUD(Page Upper Directory)

页中间目录PMD(Page Middle Directory)

页表 PTE (Page Table)

页全局目录包含若干页上级目录的地址,页上级目录又依次包含若干页中间目录的地址,而页中间目录又包含若干页表的地址,每一个页表项指向一个页框。Linux中采用4KB大小的页框作为标准的内存分配单元。

MMU

MMU是一个硬件、又叫内存管理单元。他的作用就是查找页表从虚拟地址映射到物理地址

TLB

TLB是一个物理器件,用于缓存页表。根据局部性原理,能够快速提高系统的速度。
我的博客即将同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=2f9vey9fh7vok

Last modification:May 28th, 2020 at 04:15 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment