数据结构 基于Buddy算法的内存页面管理 基于slab算法的内存分区管理物理内存空间管理物理内存空间管理数据结构 分页管理结构 设置了一个mem_map数组管理内存页面page,其在系统初始化时由 free_area_init()函 数创建。数组元素是一个个page结构体，每个page结构体对应一个物理页面。 page结构定义为mem_map_t类型，定义在 /include/linux/mm.h中：typedef struct page struct page *next;struct page *prev;struct inode *inode;unsigned long offset;struct page *next_hash;atomic_t count;unsigned flags;unsigned dirty,age;struct wait_queue *wait;struct buffer_head * buffers;unsigned long swap_unlock_entry;unsigned long map_nr; mem_map_t; 说明： Count共享该页面的进程计数 Age标志页面的“年龄” Dirty表示该页面是否被修改过 prev和next：把page结构体链接成一个双向循环链表 prev_hash和next_hash把有关page结构体连成哈希表物理内存空间管理 inode和offset：内核以节点和其上的偏移为键值，将页面组织成哈希 表。 Wait等待该页资源的进程等待队列指针 Flag页面标志 map_nr该页面page结构体在mem_map数组中的下标值，也 就是物理页面的页号。物理内存空间管理Linux进程与物理内存的关系见P300图16-25空闲物理内存空间管理 1 空闲块的组织 图7.10 free-area数据结构 2. 空闲块的分配Linux使用buddy算法来有效地分配与释放物理页块。按照上述的数据结构，Linux可以分配的内存大小只能是1个页的块，2个页的块或4个页的块等等。在物理分配页块时，Linux首先在free-area数组中寻找一个与请求大小相同的空闲页块。如果没有所请求大小的空闲页块，则继续搜索两倍于请求大 小的内存块。 这个过程一直将持续到free-area 被搜索完或找到满足要求的最小页块为止。如果找到的空闲页块正好等于请求的块长时，将它从中删除。如果找到的页面块大于请求的页块时，将空闲块一分为二，前半部分插入 free-area中前一条list链表中，取后半部分。若还大，则继续对半分，留一半取一半，直至相等。在分配过程中要相应调整bitmap表，将相应位置“0”或置“1”。 3. 空闲块的回收页块的分配会导致内存碎片化，页面回收则可将这些页块重新组合成单一大页块。当页块被释放时，将检查是否有相同大小的相邻内存块存在。如果有，则将它们组合起来， 形成一个大小为原来两倍的新空闲块。合并时要修改bitmap表的对应位，从free-area的空闲链表中取下该相邻的块。每次组合完后，还要检查是否可以继续合并成更大的页面，直至找不到空闲邻居为止。 最佳情况是系统的空闲页块的大小和允许分配的最大内存一样。 lBuddy算法-伙伴算法 Linux对空闲内存空间管理采用Buddy算法。 Buddy算法 把内存中所有页面按照2n划分，其中n=05，每个 内存空间按1个页面、2个页面、4个页面、8个页面 、16个页面、32个页面进行六次划分。物理内存分配与回收划分后形成了大小不等的存储块，称为页面块，简称 页块。包含1个页面的页块称为1页块，包含2个页面 的称为2页块，依此类推。 每种页块按前后顺序两两结合成一对Buddy“伙伴” 系统按照Buddy关系把具有相同大小的空闲页面块组 成页块组，即1页块组、2页块组32页块组。 每个页块组用一个双向循环链表进行管理，共有个 链表，分别为1、2、4、8、16、32页块链表。分别挂到free_area 数组上。物理内存空间管理位图数组 标记内存页面使用情况，第0组每一位表示单 个页面使用情况，1表示使用，0表示空闲，第 2组每一位表示比邻的两个页面的使用情况， 依次类推。默认为10个数组。 当一对Buddy的两个页面块中有一个是空闲 的，而另一个全部或部分被占用时，该位置 1。 两个页面块都是空闲，或都被全部或部分占 用时， 对应位置0。物理内存空间管理内存分配和释放过程 内存分配时，系统按照Buddy算法，根 据请求的页面数在free_area对应的 空闲页块组中搜索。 若请求页面数不是2的整数次幂，则 按照稍大于请求数的2的整数次幂的 值搜索相应的页面块组。物理内存空间管理 当相应页块组中没有可使用的空闲页面块时就 查询更大一些的页块组， 在找到可用的空闲页面块后，分配所需页面。 当某一空闲页面块被分配后，若仍有剩余的空 闲页面，则根据剩余页面的大小把它们加入到 相应页块组中。物理内存空间管理内存页面释放时，系统将其做为空闲页面 看待。检查是否存在与这些页面相邻的其它空闲 页块，若存在，则合为一个连续的空闲区 按Buddy算法重新分组。物理内存空间管理物理内存空间管理物理内存空间管理物理内存空间管理 页面交换守护进程kswapd（） 是一个无限循环的线程，完成页面交换工作， 保证系统内有足够内存。 Linux将页面分为活跃状态、非活跃”脏“状态 、非活跃”干净“状态。需要时，将非活跃”脏“状 态页面内容写入到外存交换空间，并将该页面从 ”脏“队列移动到”干净“队列。回收页面总是从非 活跃”干净“链表队列中进行交换机制 Slab算法 采用buddy算法，解决了外碎片问题，这 种方法适合大块内存请求，不适合小内存 区请求。如：几十个或者几百个字节。 Linux2.0采用传统内存分区算法，按几何 分布提供内存区大小，内存区以2的幂次 方为单位。虽然减少了内碎片，但没有显 著提高系统效率。物理内存空间管理 Linux2.4采用了slab分配器算法该算法比传统的分配器算法有更好性能和内存 利用率，最早在solaris2.4上使用。物理内存空间管理Slab分配器思想 小对象的申请和释放通过slab分配器来管理。 slab分配器有一组高速缓存，每个高速缓存保存同一 种对象类型，如i节点缓存、PCB缓存等。 内核从它们各自的缓存种分配和释放对象。 每种对象的缓存区由一连串slab构成，每个slab由一 个或者多个连续的物理页面组成。这些页面种包含了 已分配的缓存对象，也包含了空闲对象。物理内存空间管理slab分配器Linux内核中有许多内存动态分配的需求，而其中的对象大小 也参差不齐，Linux内核提供了slab层，扮演了通用数据结构 缓存层的角色。 slab层跟据对象的类型来分组不同的cache, 每个cache存放不同类型的对象，例如一个cache被用来存储 task_struct, 而另一个存放inode等。这些cache包含几个slab, 而slab由一个或多个物理上连续的page组成。对于一般的数 据结构，每个slab只有一个页即可。 每个slab都包含一些对象成员，即被管理的数据结构。系统分 配对象时就从slab中取得。首先从这个cache中部分满的slab 中分配，如果没有这样的slab, 便从空的slab中分配，如果也 没有，就创建一个新的slab来分配即可。 因为每个slab是包含同一种对象的cache块， 它对对象的分配 和释放会变得更为容易和快速。另外，由于每个对象在释放 时几乎处于分配好并且初始化好的状态，还可以节省不少初 始化的时间。比如说分配inode变量, 首先要一块 malloc(sizeof(inode) 大小的内存, 然后初始化inode中的数据 成员, 在使用完毕后用free释放分配的内存。实际上，在free 之后内存中的内容和刚刚初始化时差不多, 比如说inode的引 用计数count一定是降为零等等。 slab分配器kernel有许多数据结构都是还原到和初始化时一样的时候才会free掉 , 例如一个mutex lock初始化时和释放时都处于unlock状态。因此， 只要在cache初始化的时候就将对象置于合法状态，以后每次分配 对象的这些field一定是确定的，从而不必重复初始化，可以节省不 少开销。为了这个目的，linux的kmem_cache_create中有一个参数 ctor初始化函数, 可以被用作这一目的，但linux似乎并没有使用slab 的这一特性(因为它没用调用ctor函数)。 每个cache都用struct kmem_cache_s表示，其中有一个重要的成员 变量struct kmem_list3 lists。这个结构体中存放了该cache中空、 部分满、满的slab的队列： slab描述符(struct slab对象)本身也要占用内存。它们可以放在slab 自身开始的地方，或者在slab之外另行分配。slab分配器创建新的 slab正是通过上面的页分配器进行的。 cacheSlab PCB缓 存Slab i节点 缓存 PCB缓存i节点缓存Slab分配器的组成数据结构 高速缓存Struct kmem_cache_s 高速缓存种的每个slab数据结构Struct kmem_slab_s物理内存空间管理C_free,c_nextp C_firstp,c_lastpC_free,c_nextp C_firstp,c_lastpC_free,c_nextp C_firstp,c_lastpS_prevp,s_nextpS_prevp,s_nextpS_prevp,s_nextpS_prevp,s_nextpS_prevp,s_nextpCache结 构Cache结 构Cache结 构Slab 结构Slab 结构Slab 结构Cache结构与slab结构之间的关系创建slab对象过程Slab分配器调用Kmem_cache_grow() 函数为缓 存分配一个新的slab对象。 调用kmem_getpages()获取一组连续内存页框 ； 调用kmem_cache_slabmgamt()分配一个新的 slab数据结构； 调用kmem_cache_init_objs（）为新slab中包 含的所有对象定义构造方法； 调用kmem_slab_link_end()将新的slab插入到 这个高速缓存的双向链表的末尾。物理内存空间管理优点： 充分利用了空间，减少了内部碎片 管理局部化，尽可能减少了与buddy分配器打 交道，提高了效率。物理内存空间管理缓冲机制 目的改善处理机和外围设备之间速度不匹配的 矛盾，提高系统性能。 Linux采用了多种与主存相关的高速缓存。 缓冲区高速缓存 页面高速缓存 交换高速缓存 硬件高速缓存 缓冲区高速缓存 大小固定，是针对块设备的I/O开辟的。 缓存区高速缓存以块设备标识符和块号作为索 引，快速查找数据块，若数据块已在缓存中，则 不必从物理设备中读取，从而加快了读取数据速 度。 缓冲区高速缓存大小可变化，当没有空闲的缓 冲区而又必须分配新缓冲区时，内核就按需分配 缓冲区，当主存空间不足时，可以释放缓冲区。缓冲机制页面高速缓存 是为了加快对磁盘文件访问而设立的。 当页面从磁盘被读入主存时，被存入页面高速缓 存。 如文件系统的一些系统调用，如read()、 write()等，都是通过页面高速缓存完成的。缓冲机制交换缓存 为了避免页面交换时，直接对磁盘交换空间操作 ，从而提高了系统性能。 linux需要将一个页面从内存中换出时