linux使用伙伴系统来管理物理内存页。

一、伙伴系统原理

1. 伙伴关系

定义：由一个母实体分成的两个各方面属性一致的两个子实体，这两个子实体就处于伙伴关系。在操作系统分配内存的过程中，一个内存块常常被分成两个大小相等的内存块，这两个大小相等的内存块就处于伙伴关系。它满足 3 个条件 ：

•  两个块具有相同大小记为 2^K
•  它们的物理地址是连续的
•  从同一个大块中拆分出来

2. 伙伴算法的实现原理

为了便于页面的维护，将多个页面组成内存块，每个内存块都有 2 的方幂个页，方幂的指数被称为阶 order。order相同的内存块被组织到一个空闲链表中。伙伴系统基于2的方幂来申请释放内存页。
当申请内存页时，伙伴系统首先检查与申请大小相同的内存块链表中，检看是否有空闲页，如果有就将其分配出去，并将其从链表中删除，否则就检查上一级，即大小为申请大小的2倍的内存块空闲链表，如果该链表有空闲内存，就将其分配出去，同时将剩余的一部分（即未分配出去的一半）加入到下一级空闲链表中；如果这一级仍没有空闲内存；就检查它的上一级，依次类推，直到分配成功或者彻底失败，在成功时还要按照伙伴系统的要求，将未分配的内存块进行划分并加入到相应的空闲内存块链表
在释放内存页时，会检查其伙伴是否也是空闲的，如果是就将它和它的伙伴合并为更大的空闲内存块，该检查会递归进行，直到发现伙伴正在被使用或者已经合并成了最大的内存块。

二、linux中的伙伴系统相关的结构

系统中的每个物理内存页（页帧）都对应一个struct page数据结构，每个节点都包含了多个zone，每个zone都有struct zone表示，其中保存了用于伙伴系统的数据结构。zone中的

用于管理该zone的伙伴系统信息。伙伴系统将基于这些信息管理该zone的物理内存。该数组中每个数组项用于管理一个空闲内存页块链表，同一个链表中的内存页块的大小相同，并且大小为2的数组下标次方页。MAX_ORDER定义了支持的最大的内存页块大小。
struct free_area的定义如下

• nr_free:其中nr_free表示内存页块的数目，对于0阶的表示以1页为单位计算，对于1阶的以2页为单位计算，n阶的以2的n次方为单位计算。
• free_list:用于将具有该大小的内存页块连接起来。由于内存页块表示的是连续的物理页，因而对于加入到链表中的每个内存页块来说，只需要将内存页块中的第一个页加入该链表即可。因此这些链表连接的是每个内存页块中第一个内存页，使用了struct page中的struct list_head成员lru。free_list数组元素的每一个对应一种属性的类型，可用于不同的目地，但是它们的大小和组织方式相同。

因此在伙伴系统看来，一个zone中的内存组织方式如下图所示：

基于伙伴系统的内存管理方式专注于内存节点的某个内存域的管理，但是系统中的所有zone都会通过备用列表连接起来。伙伴系统和内存域/节点的关系如下图所示：

系统中伙伴系统的当前信息可以通过/proc/buddyinfo查看：

这是我的PC上的信息，这些信息描述了每个zone中对应于每个阶的空闲内存页块的数目，从左到右阶数依次升高。

三、避免碎片

1.碎片概念

伙伴系统也存在一些问题，在系统长时间运行后，物理内存会出现很多碎片，如图所示：
 
这是虽然可用内存页还有很多，但是最大的连续物理内存也只有一页，这对于用户程序不成问题，因为用户程序通过页表映射，应用程序看到的总是连续的虚拟内存。但是对于内核来说就不行了，因为内核有时候需要使用连续的物理内存。

2.linux解决方案

碎片问题也存在于文件系统，文件系统中的碎片可以通过工具来解决，即分析文件系统，然后重新组织文件的位置，但是这种方不适用于内核，因为有些物理页时不能随意移动。内核采用的方法是反碎片（anti-fragmentation）。为此内核根据页的可移动性将其划分为3种不同的类型：

• 不可移动的页：在内存中有固定位置，不能移动。分配给核心内核的页大多是此种类型
• 可回收的页：不能移动，但是可以删除，其内容可以从某些源重新生成。
• 可移动的页：可以随意移动。属于用户进程的页属于这种类型，因为它们是通过页表映射的，因而在移动后只需要更新用户进程页表即可。

页的可移动性取决于它属于上述三类中的哪一类，内核将页面按照不同的可移动性进行分组，通过这种技术，虽然在不可移动页中仍可能出现碎片，但是由于具有不同可移动性的页不会进入同一个组，因而其它两个类型的内存块就可以获得较好的“对抗碎片”的特性。
需要注意的是按照可移动性对内存页进行分组时在运行中进行的，而不是在一开始就设置好的。

1.数据结构

内核定义了MIGRATE_TYPES中迁移类型，其定义如下： 
其中前三种分别对应于三种可移动性，其它几种的含义：

• MIGRATE_PCPTYPES：是per_cpu_pageset，即用来表示每CPU页框高速缓存的数据结构中的链表的迁移类型数目
• MIGRATE_RESERVE：是在前三种的列表中都没用可满足分配的内存块时，就可以从MIGRATE_RESERVE分配
• MIGRATE_ISOLATE：用于跨越NUMA节点移动物理内存页，在大型系统上，它有益于将物理内存页移动到接近于是用该页最频繁地CPU

每种类型都对应free_list中的一个数组项。
类似于从zone中的分配，如果无法从指定的迁移类型分配到页，则会按照fallbacks指定的次序从备用迁移类型中尝试分配，它定义在page_alloc.c中。
虽然该特性总是编译进去的，但是该特性只有在系统中有足够的内存可以分配到每种迁移类型对应的链表时才有意义，也就是说每个可以迁移性链表都要有“适量”的内存，内核需要对“适量”的判断是基于两个宏的：

• pageblock_order：内核认为够大的一个分配的阶。
• pageblock_nr_pages：内核认为启用该特性时每个迁移链表需要具有的最少的内存页数。它的定义是基于pageblock_order的。

基于这个“适量”的概念内核会在build_all_zonelists中判断是否要启用该特性。page_group_by_mobility_disabled表示是否启用了该特性。
内核定义了两个标志：__GFP_MOVABLE和 __GFP_RECLAIMABLE分别用来表示可移动迁移类型和可回收迁移类型，如果没有设置这两个标志，则表示是不可移动的。如果页面迁移特性被禁止了，则所有的页都是不可移动页。
struct zone中包含了一个字段pageblock_flags，它用于跟踪包含pageblock_nr_pages个页的内存区的属性。在初始化期间，内核自动保证对每个迁移类型，在pageblock_flags中都分配了足够存储NR_PAGEBLOCK_BITS个比特的空间。
set_pageblock_migratetype用于设置一个以指定的页为起始地址的内存区的迁移类型。
页的迁移类型是预先分配好的，对应的比特位总是可用，在页释放时，必须将其返还给正确的链表。get_pageblock_migratetype可用于从struct page中获取页的迁移类型。
通过/proc/pagetypeinfo可以获取系统当前的信息。
在内存初始化期间memmap_init_zone会将所有的内存页都初始化为可移动的。该函数在paging_init中会最终被调到（会经过一些中间函数，其中就有free_area_init_node）。

3．虚拟可移动内存

内核还提供了一种机制来解决碎片问题，即使用虚拟内存域ZONE_MOVABLE。其思想是：可用内存划分为两个部分，一部分用于可移动分配，一部分用于不可移动分配。这样就防止了不可移动页向可移动内存区域引入碎片。
该机制需要管理员来配置两部分内存的大小。
kernel参数kernelcore用于指定用于不可移动分配的内存数量，如果指定了该参数，其值会保存在required_kernelcore会基于它来计算。
kernel参数movablecore用于指定用于可移动分配的内存数量，如果指定了该参数，则其值会被保存在required_movablecore中，同时会基于它来计算required_kernelcore，代码如下（函数find_zone_movable_pfns_for_nodes）：
如果计算出来的required_kernelcore为0，则该机制将无效。
该zone是一个虚拟zone，它不和任何物理内存相关联，该域中的内存可能来自高端内存或者普通内存。用于不可移动分配的内存会被均匀的分布到系统的各个内存节点中；同时用于可移动分配的内存只会取自最高内存域的内存，zone_movable_pfn记录了取自各个节点的用于可移动分配的内存的起始地址。

四、初始化内存域和节点数据结构

在内存管理的初始化中，架构相关的代码要完成系统中可用内存的检测，并要将相关信息提交给架构无关的代码。架构无关的代码free_area_init_nodes负责完成管理数据结构的创建。该函数需要一个参数max_zone_pfn，它由架构相关的代码提供，其中保存了每个内存域的最大可用页帧号。内核定义了两个数组：

这两个数组在free_area_init_nodes用于保存来自max_zone_pfn的信息，并将它转变成[low，high]的形式。
然后内核开始调用find_zone_movable_pfns_for_nodes对ZONE_MOVABLE域进行初始化。

然后内核开始为每一个节点调用free_area_init_node，这个函数将完成：

1. 调用calculate_node_totalpages计算节点中页的总数
2. 调用alloc_node_mem_map负责初始化struct pglist_data中的node_mem_map，为它分配的内存将用于存储本节点的所有物理内存的struct page结构。这片内存将对其到伙伴系统的最大分配阶上。而且如果当前节点是第0个节点，则该指针信息还将保存在全局变量mem_map中。
3. 调用free_area_init_core完成初始化进一步的初始化

free_area_init_core将完成内存域数据结构的初始化，在这个函数中

1. nr_kernel_pages记录直接映射的页面数目，而nr_all_pages则记录了包括高端内存中页数在内的页数
2. 会调用zone_pcp_init初始化该内存域的每CPU缓存
3. 会调用init_currently_empty_zone初始化该zone的wait_table，free_area列表
4. 调用memmap_init初始化zone的页，所有页都被初始化为可移动的

五、分配器API

伙伴系统只能分配2的整数幂个页。因此申请时，需要指定请求分配的阶。
有很多分配和释放页的API，都定义在gfp.h中。最简单的是alloc_page(gfp_mask)用来申请一个页， free_page(addr)用来释放一个页。
这里更值得关注的获取页面时的参数gfp_mask，所有获取页面的API都需要指定该参数。它用来影响分配器的行为，其中有是分配器提供的标志，标志有两种：
zone修饰符：用于告诉分配器从哪个zone分配内存
行为修饰符：告诉分配器应该如何进行分配
其中zone修饰符定义为

这些定义都一目了然，需要指出的是如果同时指定了__GFP_MOVABLE和__GFP_HIGHMEM，则会从虚拟的ZONE_MOVABLE分配。
更详细的可以参考gfp.h，其中包含了所有的标志及其含义。

1.分配页

__alloc_pages会完成最终的内存分配，它是伙伴系统的核心代码（但是在内核代码中，这种命名方式的函数都是需要小心调用的，一般都是给实现该功能的代码自己调用，不作为API提供出去的，因而它的包装器才是对外提供的API，也就是alloc_pages_node）。

1.选择页

选择页中最重要的函数是get_page_from_freelist，它负责通过标志和分配阶来判断分配是否可以进行，如果可以就进行实际的分配。该函数还会调用zone_watermark_ok根据指定的标识判断是否可以从给定的zone中进行分配。该函数需要struct zonelist的指针指向备用zone，当当前zone不能满足分配需求时就依次遍历该列表尝试进行分配。整体的分配流程是：

1. 调用get_page_from_freelist尝试进行分配，如果成功就返回分配到的页，否则
2. 唤醒kswapd，然后再次调用get_page_from_freelist尝试进行分配，如果成功就返回分配的页，否则
3. 如果分配的标志允许不检查阈值进行分配，则以ALLOC_NO_WATERMARKS为标志再次调用get_page_from_freelist尝试分配，如果成功则返回分配的页；如果不允许不检查阈值或者仍然失败，则
4. 如果不允许等待，就分配失败，否则
5. 如果支持压缩，则尝试先对内存进行一次压缩，然后再调用get_page_from_freelist，如果成功就返回，否则
6. 进行内存回收，然后再调用get_page_from_freelist，如果成功就返回，否则
7. 根据回收内存并尝试分配的结果以及分配标志，可能会调用OOM杀死一个进程然后再尝试分配，也可能不执行OOM这一步的操作，如果执行了，则在失败后可能就彻底失败，也可能重新回到第2步，也可能继续下一步
8. 回到第2步中调用get_page_from_freelist的地方或者再尝试一次先压缩后分配，如果走了先压缩再分配这一步，这就是最后一次尝试了，要么成功要么失败，不会再继续尝试了

2.移出所选择的页

在函数get_page_from_freelist中，会首先在zonelist中找到一个具有足够的空闲页的zone，然后会调用buffered_rmqueue进行处理，在分配成功时，该函数会把所分配的内存页从zone的free_list中移出，并且保证剩余的空闲内存页满足伙伴系统的要求，该函数还会把内存页的迁移类型存放在page的private域中。
该函数的步骤如图所示：

可以看出buffered_rmqueue的工作过程为：

1. 如果申请的是单页，会做特殊处理，内核会利用每CPU的缓存加速这个过程。并且在必要的时候会首先填充每CPU的缓存。函数rmqueue_bulk用于从伙伴系统获取内存页，并添加到指定的链表，它会调用函数__rmqueue。
2. 如果是分配多个页，则会首先调用__rmqueue从内存域的伙伴系统中选择合适的内存块，这一步可能失败，因为虽然内存域中有足够数目的空闲页，但是页不一定是连续的，如果是这样这一步就会返回NULL。在这一步中如果需要还会将大的内存块分解成小的内存块来进行分配，即按照伙伴系统的要求进行分配。
3. 无论是分配单页还是多个页，如果分配成功，在返回分配的页之前都要调用prep_new_page，如果这一步的处理不成功就会重新进行分配（跳转到函数buffered_rmqueue的开始），否则返回分配的页。

函数__rmqueue的执行过程：

1. 首先调用__rmqueue_smallest尝试根据指定的zone，分配的阶，迁移类型进行分配，该函数根据指定的信息进行查找，在找到一个可用的空闲内存页块后会将该内存页块从空闲内存页块链表中删除，并且会调用expand使得剩余的内存页块满足伙伴系统的要求。如果在这一步成功就返回，否则执行下一步
2. 调用__rmqueue_fallback尝试从备用zone分配。该函数用于根据前一类型的备用列表尝试从其它备用列表分配，但是需要注意的是这里会首先尝试最大的分配阶，依次降低分配的阶，直到指定的分配的阶，采用这个策略是为了避免碎片—如果要用其它迁移类型的内存，就拿一块大的过来，而不是在其它迁移类型的小区域中到处引入碎片。同时如果从其它迁移类型的空闲内存页块分配到的是一个较大的阶，则整块内存页块的迁移类型可能会发生改变，从原来的类型改变为申请分配时所请求的类型（即迁移类型发生了改变）。分配成功时的动作和__rmqueue_smallest类似，移出内存页，调用expand。

函数prep_new_page的操作

1. 对页进行检查，以确保页确实是可用的，否则就返回一个非0值导致分配失败
2. 设置页的标记以及引用计数等等。
3. 如果设置而来__GFP_COMP标志，则调用prep_compound_page将页组织成复合页（hugetlb会用到这个）。

复合页的结构如图所示：

复合页具有如下特性：

• 复合页中第一个页称为首页，其它所拥有页都称为尾页
• 组成复合页的所有的private域都指向首页
• 第一个尾页的lru的next域指向释放复合页的函数指针
• 第一个尾页的lru的prev域用于指向复合页所对应的分配的阶，即多少个页

2.释放页

__free_pages是释放页的核心函数，伙伴系统提供出去的API都是它的包装器。其流程：

1. 减小页的引用计数，如果计数不为0则直接返回，否则
2.  如果释放的是单页，则调用free_hot_cold_page，否则
3.  调用__free_pages_ok

free_hot_cold_page会把页返还给每-CPU缓存而不是直接返回给伙伴系统，因为如果每次都返还给伙伴系统，那么将会出现每次的分配和释放都需要伙伴系统进行分割和合并的情况，这将极大的降低分配的效率。因而这里采用的是一种“惰性合并”，单页会首先返还给每-CPU缓存，当每-CPU缓存的页面数大于一个阈值时（pcp->high），则一次将pcp->patch个页返还给伙伴系统。free_pcppages_bulk在free_hot_cold_page中用于将内存页返还给伙伴系统，它会调用函数__free_one_page。
函数__free_pages_ok最终页会调到__free_one_page来释放页，__free_one_page会将页面释放返还给伙伴系统，同时在必要时进行递归合并。
在__free_one_page进行合并时，需要找到释放的page的伙伴的页帧号，这是通过__find_buddy_index来完成的，其代码非常简单：
根据异或的规则，这个结果刚好可以得到邻居的页帧号。因为根据linux的管理策略以及伙伴系统的定义，伙伴系统中每个内存页块的第一个页帧号用来标志该页，因此对于order阶的两个伙伴，它们只有1<<order这个比特位是不同的，这样，只需要将该比特与取反即可，而根据异或的定义，一个比特和0异或还是本身，一个比特和1异或刚好可以取反。因此就得到了这个算式。
如果可以合并还需要取得合并后的页帧号，这个更简单，只需要让两个伙伴的页帧号相与即可。
__free_one_page调用page_is_buddy来对伙伴进行判断，以决定是否可以合并。

六、不连续内存页的分配

内核总是尝试使用物理上连续的内存区域，但是在分配内存时，可能无法找到大片的物理上连续的内存区域，这时候就需要使用不连续的内存，内核分配了其虚拟地址空间的一部分（vmalloc区）用于管理不连续内存页的分配。
每个vmalloc分配的子区域都自包含的，在内核的虚拟地址空间中vmalloc子区域之间都通过一个内存页隔离开来，这个间隔用来防止不正确的访问。

1. 用vmalloc分配内存

vmalloc用来分配在虚拟地址空间连续，但是在物理地址空间不一定连续的内存区域。它只需要一个以字节为单位的长度参数。为了节省宝贵的较低端的内存区域，vmalloc会使用高端内存进行分配。
内核使用struct vm_struct来管理vmalloc分配的每个子区域，其定义如下：
每个vmalloc子区域都对应一个该结构的实例。

• next：指向下一个vmalloc子区域
• addr：vmalloc子区域在内核虚拟地址空间的起始地址
• size：vmalloc子区域的长度
• flags：与该区域相关标志
• pages：指针，指向映射到虚拟地址空间的物理内存页的struct page实例
• nr_pages：映射的物理页面数目
• phys_addr：仅当用ioremap映射了由物理地址描述的内存页时才需要改域，它保存物理地址
• caller：申请者

2. 创建vmalloc子区域

所有的vmalloc子区域都被连接保存在vmlist中，该链表按照addr排序，顺序是从小到大。当创建一个新的子区域时需要，需要找到一个合适的位置。查找合适的位置采用的是首次适用算法，即从vmalloc区域找到第一个可以满足需求的区域，查找这样的区域是通过函数__get_vm_area_node完成的。其分配过程以下几步：

1. 调用__get_vm_area_node找到合适的区域
2. 调用__vmalloc_area_node分配物理内存页
3. 调用map_vm_area将物理内存页映射到内核的读你地址空间
4. 将新的子区域插入vmlist链表

在从伙伴系统分配物理内存页时使用了标志：GFP_KERNEL | __GFP_HIGHMEM
还有其它的方式来建立虚拟地址空间的连续映射：

1. vmalloc_32：与vmallo工作方式相同，但是确保所使用的物理地址总可以用32位指针寻址
2. vmap：将一组物理页面映射到连续的虚拟地址空间
3. ioremap：特定于处理器的分配函数，用于将取自物理地址空间而、由系统总线用于I/O操作的一个内存块，映射到内核的虚拟地址空间

3. 释放内存

vfree用于释放vmalloc和vmalloc_32分配的内存空间，vunmap用于释放由vmap和ioremap分配的空间（iounmap会调到vunmap）。最终都会归结到函数__vunmap。
__vunmap的执行过程：

1. 调用remove_vm_area从vmlist中找到一个子区域，然后将其从子区域删除，再解除物理页面的映射
2. 如果设置了deallocate_pages，则将物理页面归还给伙伴系统
3. 释放管理虚拟内存的数据结构struct vm_struct

七、内核映射

高端内存可通过vmalloc机制映射到内核的虚拟地址空间，但是高端内存往内核虚拟地址空间的映射并不依赖于vmalloc，而vmalloc是用于管理不连续内存的，它也并不依赖于高端内存。

1.持久内核映射

如果想要将高端内存长期映射到内核中，则必须使用kmap函数。该函数需要一个page指针用于指向需要映射的页面。如果没有启用高端内存，则该函数直接返回页的地址，因为所有页面都可以直接映射。如果启用了高端内存，则：

• 如果不是高端内存的页面，则直接返回页面地址，否则
• 调用kmap_high进行处理

1.使用的数据结构

vmalloc区域后的持久映射区域用于建立持久映射。pkmap_count是一个有LAST_PKMAP个元素的数组，每个元素对应一个持久映射。每个元素的值是被映射页的一个使用计数器：

1. 0：相关的页么有被使用
2. 1：该位置关联的页已经映射，但是由于CPU的TLB没有刷新而不能使用
3. 大于1的其它值：表示该页的引用计数，n表示有n-1处在使用该页

数据结构
用于建立物理页和其在虚拟地址空间位置之间的关系。

• page：指向全局数据结构mem_map数组中的page实例的指针
• virtual：该页在虚拟地址空间中分配的位置

所有的持久映射保存在一个散列表page_address_htable中，并用链表处理冲突，page_slot是散列函数。
函数page_address用于根据page实例获取器对应的虚拟地址。其处理过程：

1. 如果不是高端内存直接根据page获得虚拟地址（利用__va(paddr)），否则
2. 在散列表中查找该page对应的struct page_address_map实例，获取其虚拟地址

2.创建映射

函数kmap_high完成映射的实际创建，其工作过程：

1. 调用page_address获取对应的虚拟地址
2. 如果没有获取到，则调用map_new_virtual获取虚拟地址
3. pkmap_count数组中对应于该虚拟地址的元素的引用计数加1

新映射的创建在map_new_virtual中完成，其工作过程：
 

1. 执行一个无限循环：
   1. 更新last_pkmap_nr为last_pkmap_nr+1
   2. 同时如果last_pkmap_nr为0，调用flush_all_zero_pkmaps，flush CPU高速缓存
   3. 检查pkmap_count数组中索引last_pkmap_nr对应的元素的引用计数是否为0，如果是0就退出循环，否则
   4. 将自己加入到一个等待队列
   5. 调度其它任务
   6. 被唤醒时会首先检查是否有其它任务已经完成了新映射的创建，如果是就直接返回
   7. 回到循环头部重新执行
2. 获取与该索引对应的虚拟地址
3. 修改内核页表，将该页映射到获取到的虚拟地址
4. 更新该索引对应的pkmap_count元素的引用计数为1
5. 调用set_page_address将新的映射加入到page_address_htable中

flush_all_zero_pkmaps的工作过程：

1. 调用flush_cache_kmaps执行高速缓存flush动作
2. 遍历pkmap_count中的元素，如果某个元素的值为1就将其减小为0，并删除相关映射同时设置需要刷新标记
3. 如果需要刷新，则调用flush_tlb_kernel_range刷新指定的区域对应的tlb。

3.解除映射

kunmap用于解除kmap创建的映射，如果不是高端内存，什么都不做，否则kunmap_high将完成实际的工作。kunmap_high的工作很简单，将对应的pkmap_count中的元素的引用计数的值减1，如果新值为1，则看是否有任务在pkmap_map_wait上等待，如果有就唤醒它。根据该机制的涉及原理，该函数不能将引用计数减小到小于1，否则就是一个BUG。

2.临时内核映射

kmap不能用于无法休眠的上线文，如果要在不可休眠的上下文调用，则需要调用kmap_atomic。它是原子的，特定于架构的。同样的只有是高端内存时才会做实际的映射。
kmap_atomic使用了固定映射机制。在固定映射区域，系统中每个CPU都有一个对应的“窗口”，每个窗口对应于KM_TYPE_NR中不同的类型都有一项。这个映射的核心代码如下（取自powerpc）：
固定映射区域为用于kmap_atomic预留内存区的代码如下：

转：https://blog.csdn.net/goodluckwhh/article/details/9989695

内存管理笔记十、buddy伙伴系统

引言：上一篇笔记中，我们介绍了段页式的内存管理方式其不仅获得分段和分页的好处，又规避了单纯分段和分页的缺陷。这看似是一个完美的解决方案。但每次申请内存，均要完成虚拟地址至物理地址的映射、要改写内核的页表项、刷新TLB，以页为单位降低了内存分配速度。因此linux在段页式内存管理基础上，增加伙伴系统分配机制，可以理解为以空间换取时间和性能的机制。

---

一、linux物理内存划分管理

  为了有效的管理物理内存（分配、回收），Linux将整个物理内存划分为若干页，对每一个页，都有相关的数据结构来记录该页的状态和使用信息。在Linux中，每个页的大小是4KB。对于一个512MB的物理内存一共有（512 * 1024）/ 4 = 131072个页。对于每一个页，Linux都有一个struct page数据结构来记录该物理页的使用情况。所有页的struct page结构组成一个连续的数组存放在物理内存的某个地方。某页在物理内存中的物理地址除以4KB，就得到该页是第几个物理页索引，然后索引就可以查询struct page数组，得到该页的具体信息。

  除了使用struct page来记录某个4KB物理页的状态和使用信息外，Linux还将整个物理内存根据物理地址划分为不同的区。区的划分是与体系结构相关的（由于硬件的限制，内核不能对所有的页一视同仁）。对于X86，ZONE可以划分为DMA区[0，16MB]、NORMAL区[16MB， 896MB]和HIGHMEM区[896MB，memory length]。对于ARM，ZONE划分为NORMAL区和HIGHMEM区。其中NORMAL区对应线性映射的物理内存，HIGHMEM区对应非线性映射的物理内存。

---

二、Buddy伙伴系统

  我们介绍分页系统时已经讲过，分页系统不会产生外部碎片，一个进程占用的内存空间可以是不连续的，并且一个进程的虚拟页面在不需要的时候可以存放在磁盘上。当进程需要较大运行内存，以页为单位分配物理内存，每页均要完成虚拟地址至物理地址的映射、改写内核页表项、刷新TLB，效率较低。因此linux在段页式内存管理基础上，增加伙伴系统分配机制，我理解其为以空间换取性能的一种方式。

2.1、伙伴系统的作用：

  它要解决的问题是频繁地请求和释放不同大小的一组连续页框，必然导致在已分配的块内分散了许多小块的空闲页面，由此带来的问题是，即使有足够的空闲页面可以满足请求，但要分配一个大块的连续页框可能无法满足请求。其要完成的作用，即高效的分配和回收资源，降低外部碎片。

2.2、伙伴系统的介绍：

  Buddy System是Linux Kernel 进行物理内存页管理的一个子系统。在Buddy System中，管理的一个基本单位是block，每一个block有若干个连续的物理页组成，物理页的个数为2ⁿ，这个n在buddy system中被称为order。相同order的block，挂载一条双向链表上。

  当某个block空闲时，只要发现对应的伙伴也是空闲的，就和伙伴组成一个页数为2ⁿ⁺¹的block，挂载在order为(n+1)的双向链表上，换句话说一个页数为2ⁿ的block，是由两个页数为2^n-1的伙伴block组成的。因此，一个block的伙伴肯定是和这个block在物理地址上是连续的。在Linux中，order的默认的取值范围是[0,10]，其单次分配的最大内存为4M，即2¹⁰ 个4K页面。

2.3、申请和释放过程：

  申请物理内存过程：假设请求一个页框的块（即4KB），算法先在1个页框的链表中检查是否有空闲块。若没有，则查找下一个更大的块，即在2个页框的链表中找一个空闲块。如果存在这样的块，内核就把2的页框分成两等份，一半用作满足请求，另一半插入到1 个页框的链表中。
  如果在2个页框的块链表中也没找到空闲块，就继续找更大的块 —— 4个页框的块。如果这样的块存在，内核把4个页框块的1 个页框用作请求，然后从剩余的3个页框中拿2个插入到2个页框的链表中，再把最后的1个插入到1个页框的链表中。如果最终至1024个页框的链表还是空的，算法就放弃并发出错信号。

  释放物理内存过程：以上过程的逆过程就是页框块的释放过程，也是该算法名字的由来。内核试图把大小为b的一对空闲伙伴（两个块具有相同大小，且它们物理地址连续）合并为一个大小为2b的单独块。这个算法是迭代的，如果它成功合并所释放的块，它会试图合并2b 的块，以再次试图形成更大的块。

2.4、伙伴系统实现 ——相关数据结构：

  我们介绍了区的概念，每个管理区都有自己的struct zone， 而struct zone中的struct free_area则是用来描述该管理区伙伴系统的空闲内存块的。其部分代码如下：

struct zone {  
    ...  
         ...      
    struct free_area    free_area[MAX_ORDER];  
    ...  
    ...  
}  

struct free_area {  
    struct list_head    free_list[MIGRATE_TYPES];  
    unsigned long       nr_free;  
};  

  free_area共有MAX_ORDER个元素，，这些空闲块在free_list中以双向链表的形式组织起来，对于同等大小的空闲块，其类型不同，将组织在不同的free_list中，nr_free记录了该free_area中总共的空闲内存块的数量。MAX_ORDER的默认值为11，这意味着最大内存块的大小为2^10=1024个页框。

  关于伙伴系统的内核实现及相关细节，可以参考伙伴系统概述、伙伴系统初始化、伙伴系统分配页、伙伴系统释放页、通过迁移类型实现反碎片等。

2.5、伙伴算法的优缺点分析：

优点：
1)、较好的解决外部碎片问题
2)、当需要分配若干个内存页面时，用于DMA的内存页面必须连续，伙伴算法很好的满足了这个要求
3)、只要请求的块不超过1024个页面(4M)，内核就尽量分配连续的页面。
4)、针对大内存分配设计

缺点：
1)、合并的要求太过严格，只能是满足伙伴关系的块才能合并
2)、 碎片问题：一个连续的内存中仅仅一个页面被占用，导致整块内存区都不具备合并的条件
3)、浪费问题：伙伴算法只能分配2的幂次方内存区，当需要8K（2页）时，好说，当需要9K时，那就需要分配16K（4页）的内存空间，但是实际只用到9K空间，多余的7K空间就被浪费掉。
4）、算法的效率问题： 伙伴算法涉及了比较多的计算还有链表和位图的操作，开销还是比较大的，如果每次2^n大小的伙伴块就会合并到2^(n+1)的链表队列中，那么2^n大小链表中的块就会因为合并操作而减少，但系统随后立即有可能又有对该大小块的需求，为此必须再从2^(n+1)大小的链表中拆分，这样的合并又立即拆分的过程是无效率的。

总结： Linux针对大内存的物理地址分配，采用伙伴算法，如果是针对小于一个page的内存，频繁的分配和释放，有更加适宜的解决方案，如slab，那是后面笔记的内容

参考内容：
认识Linux物理内存管理系统 - Buddy System
Linux伙伴算法介绍
linux伙伴系统概述

纠错与建议
邮箱：db_hebut@163.com

---

内存保护

需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。两种方法

1. CPU中设置上、下限寄存器。
   存放用户作业在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器的值对比，判断有无越界
2. 采用 重定位寄存器（或基址寄存器） 和 界地址寄存器（限长寄存器） 来实现保护。
   重定位寄存器中含最小的物理地址值，界地址寄存器含逻辑地址的最大值。
   每个逻辑地址值必须小于界地址寄存器；若比较后未越界则加上重定位寄存器的值后映射成物理地址，再送内存单元。
   

---

 

覆盖（Overlay）

早期用的。

基本思想：由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序），因此可把用户空间分成一个固定区和若干覆盖区。将经常活跃的部分放在固定区，其他部分按调用关系分段。首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。

实现：

• 将程序的必要部分代码和数据常驻内存；
• 可选部分在其他程序模块中实现，平时存放在外存中（覆盖文件），需
  要用到时才装入到内存；
• 不存在调用关系的模块不必同时装入到内存，可相互覆盖。

特点：打破了必须将一个进程全部信息装入主存后才能运行的限制；但当同时运行代码大于主存时仍不能运行；内存中能更新的地方只有覆盖区的段，不在覆盖区的段会常驻内存。

---

 

碎片整理：分区对换（Swapping）

早期使用，基本思想：

• 把内存中处于等待状态（或在CPU调度原则下被剥夺运行权力的）程序换出到外存上【换出】，以腾出足够的内存空间；
• 把准备好竞争CPU运行的程序从辅存移到内存【换入】。

优点：不要求用户给出程序段之间的逻辑覆盖结构。

注意：

• 交换需要备份存储，通常是快速磁盘；
• 进程执行时间要比交换时间长；
• 若换出经常，必须确保该进程完全处于空闲状态；
• 交换空间常作为磁盘的一整块，且独立于文件系统，因此使用很快；
• 交换在内存吃紧时启动，系统负荷降低就暂停。

 

固定分区分配

把内存分为大小相等或不等的固定分区，在每个分区中只装入一道程序。

分区分配算法：为进程分配某个空闲分区。

• 分区相等时，任选一个空闲分区；
• 分区不等时，根据空闲分区选择最佳任务或根据任务选择最佳空闲分区。

存储保护：界限寄存器

优点： 比单一连续分配方法，内存利用率提高了；可以支持多道程序，无外部碎片；实现简单。

缺点：

• 分区数目确定，限制了系统中活跃进程的数目
• 小作业的内部碎片可能比较大；
• 作业必须预先能估计要占用多大的内存空间。

 

动态分区分配

优点：

• 支持多道程序
• 管理方案相对简单，不需要更多的软、硬件开销
• 实现存储保护的手段比较简单

缺点：

• 主存利用不够充分，存在外部碎片； ➡ 通过紧凑技术解决
• 无法实现多进程共享存储器的信息；
• 无法实现主存的逻辑扩充，进程的地址空间受实际物理内存的限制。

 

伙伴系统（Buddy system）

综合静态划分技术和动态划分技术的优点。

分配： 进程申请大小为k的空间，系统分配一 2^u 的空闲分区，其中，2^u-1＜k ≤ 2^u

1. 查找大小为 2ⁱ 的空闲分区，若找到则分配；
2. 若未找到大小为 2ⁱ 的空闲分区，则查找大小为 2ⁱ⁺¹ 的空闲分区；若找到，则将该空闲分区划分为相等的两个分区（一对伙伴），其中的一个用于分配，另一个分区加入大小为 2ⁱ 的空闲分区链中；
3. 若未找到 2ⁱ⁺¹ 的空闲分区，则需要查找大小为 2ⁱ⁺² 的空闲分区，若找到则需要进行两次划分。第一次将其分割为大小为 2ⁱ⁺¹ 的两个分区，一个用于分配，另一个加入到大小为 2ⁱ⁺¹ 的空闲分区链中；第二次将第一次用于分配的空闲分区分割为 2ⁱ 的两个分区，一个用于分配，另一个加入到大小为 2ⁱ 的空闲分区链中。
4. 若仍未找到 2ⁱ⁺² 的空闲分区，则继续查找 2ⁱ⁺³ 的空闲分区，以此类推。

回收： 释放一个大小为 2ⁱ 的分区时，算法：

1. 若事先不存在 2ⁱ 的空闲分区，则保留该分区为一个独立的空闲分区；
2. 若事先已存在 2ⁱ 的空闲分区时，则将其与伙伴分区合并为大小为为 2ⁱ⁺¹ 的空闲分区；
3. 若事先已存在 2ⁱ⁺¹ 的空闲分区时，继续合并为 2ⁱ⁺² 的空闲分区，以此类推。

缺点：速度快，但内存利用率不高。