企业官网建设流程全解析

企业营销策划 网站建设,wordpress公司网页主题,个人网站找谁建设好,seo单页面wordpressLinux内核伙伴系统#xff08;Buddy System#xff09;原理详解 目录 概述基本概念数据结构伙伴关系分配算法释放与合并算法完整示例性能分析优缺点总结实际应用 概述 伙伴系统#xff08;Buddy System#xff09;是Linux内核中用于管理物理页框的核心算法#xff0c;它…Linux内核伙伴系统Buddy System原理详解目录概述基本概念数据结构伙伴关系分配算法释放与合并算法完整示例性能分析优缺点总结实际应用概述伙伴系统Buddy System是Linux内核中用于管理物理页框的核心算法它通过将内存按2的幂次组织实现了高效的大块连续内存分配和回收机制。核心思想伙伴系统的核心思想是按2的幂次组织内存将内存划分为20、21、22…2n大小的块伙伴关系相邻的两个相同大小的空闲块互为伙伴自动合并释放内存时如果伙伴块也是空闲的自动合并成更大的块按需分割分配时如果没有合适大小的块从更大的块中分割基本概念Order阶order是伙伴系统中的核心概念表示2的幂次order页框数量内存大小4KB页二进制表示014KB2^0 1128KB2^1 22416KB2^2 43832KB2^3 841664KB2^4 16532128KB2^5 32664256KB2^6 647128512KB2^7 12882561MB2^8 25695122MB2^9 5121010244MB2^10 1024MAX_ORDER通常为11意味着最大可以分配2^10 1024个页框4MB页框Page FrameLinux内核将物理内存划分为固定大小的页框ARM64架构通常使用4KB页大小。每个页框都有一个对应的struct page描述符。数据结构Zone结构每个内存区域zone都维护一个伙伴系统的空闲链表数组structzone{// ... 其他字段// 伙伴系统的核心MAX_ORDER个空闲区域链表structfree_areafree_area[MAX_ORDER];// ... 其他字段};free_area结构每个order对应一个free_area结构structfree_area{// 按迁移类型分类的空闲链表// MIGRATE_TYPES包括MIGRATE_UNMOVABLE、MIGRATE_RECLAIMABLE等structlist_headfree_list[MIGRATE_TYPES];// 该order的空闲块数量unsignedlongnr_free;};重要说明order值作为数组索引是唯一的free_area[0]对应 order01个页框free_area[1]对应 order12个页框free_area[2]对应 order24个页框…以此类推到free_area[MAX_ORDER-1]每个 order 值0 到 MAX_ORDER-1都是唯一的因为数组索引是唯一的同一个order下可以有多个空闲块虽然每个 order 值唯一但同一个 order 下可以有多个空闲块这些空闲块通过free_list链表连接起来例如free_area[1].free_list[0]可能链接着多个 order1 的空闲块每个都是2个页框数据结构层次关系zone-free_area[MAX_ORDER] (数组索引就是order值) ├── free_area[0] (order0唯一) │ └── free_list[0] → [块1] → [块2] → [块3] → ... (链表可以有多个块) ├── free_area[1] (order1唯一) │ └── free_list[0] → [块1] → [块2] → ... (链表可以有多个块) └── ...free_area中存储的是合并后的块✅自动合并机制释放内存时如果伙伴块也是空闲的会自动合并成更大的块✅存储的是最大可合并块free_area 中存储的是当前可以合并的最大块⚠️合并是有条件的只有当两个块满足伙伴关系大小相同、物理相邻、对齐且都是空闲时才会合并⚠️为什么同一order下还有多个块如果某个 order 下有多个空闲块说明这些块之间不是伙伴关系或者它们的伙伴块已经被分配了所以无法合并例如页框0-1和页框10-11都是order1的空闲块但它们不是伙伴不相邻所以不会合并页描述符每个物理页框都有一个struct page描述符structpage{// 页标志位unsignedlongflags;// 引用计数atomic_t_count;// 如果页在伙伴系统中order值存储在这里unsignedintorder;// LRU链表节点Least Recently Used// 在伙伴系统中用于将空闲页框连接成链表// 当页框在空闲链表中时通过lru字段连接structlist_headlru;// ... 其他字段};lru字段的作用链表连接lru是struct list_head类型用于实现侵入式链表重要free_area 链的是块block不是单个页框每个块用一个struct page表示指向块的第一个页框当块在伙伴系统的空闲链表中时通过块的第一个页框的lru字段连接成双向链表每个free_area[order].free_list[MIGRATE_TYPE]链表中空闲块通过lru字段连接块与页框的关系块block由多个连续的页框组成大小取决于 orderorder0 的块1个页框order1 的块2个页框order2 的块4个页框…struct page链表中存储的是块的第一个页框的struct page例如order2 的块包含页框0-3但链表中只存储页框0的struct page从链表节点获取块链表操作时我们只有lru字段的地址链表节点通过list_entry(ptr, struct page, lru)宏可以从lru的地址计算出struct page的起始地址这个struct page代表块的第一个页框通过它可以访问整个块这是Linux内核中典型的侵入式链表用法数据结构关系图示free_area[order2].free_list[MIGRATE_TYPE] (链表头) ↓ ┌─────────────────────────────────┐ struct page (块1的第一个页框) 代表块1: 页框0-3 (4个页框) ... struct list_head lru; ←────────── 链表节点1 ... └─────────────────────────────────┘ ↓ (lru.next) ┌─────────────────────────────────┐ struct page (块2的第一个页框) 代表块2: 页框8-11 (4个页框) ... struct list_head lru; ←────────── 链表节点2 ... └─────────────────────────────────┘ ↓ (lru.next) ...使用示例// 从链表中取出第一个空闲块通过块的第一个页框的struct pagestructlist_head*nodearea-free_list[MIGRATE_TYPE].next;// 获取lru节点地址structpage*pagelist_entry(node,structpage,lru);// 计算出page地址// page 指向块的第一个页框通过 page-order 可以知道块的大小// 从链表中删除块list_del(page-lru);// 通过page-lru的地址删除节点伙伴关系伙伴的定义两个内存块互为伙伴需要满足以下条件大小相同两个块必须是相同的order物理相邻两个块在物理内存中必须相邻对齐要求起始地址必须对齐到块大小的边界伙伴判断算法给定一个order为k的块其起始页框号为page_num其伙伴块的页框号计算如下// 伙伴块的页框号计算staticinlineunsignedlong__find_buddy_index(unsignedlongpage_idx,unsignedintorder){returnpage_idx^(1order);}原理说明对于orderk的块大小为2^k个页框伙伴块的位置如果块起始于page_idx其伙伴块起始于page_idx ^ (1 k)^是异或运算1 k是2^k示例// 假设order24个页框起始页框号为4page_idx4order2buddy_idx4^(12)4^40// 如果起始页框号为0page_idx0buddy_idx0^44伙伴关系图示内存布局示例order2每个块4个页框 页框号: 0 1 2 3 | 4 5 6 7 | 8 9 10 11 | 12 13 14 15 ┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐ 块A: 块A (4页) 块B (4页) 块C (4页) 块D (4页) └───────────┘ └───────────┘ └───────────┘ └───────────┘ 起始:0 起始:4 起始:8 起始:12 伙伴关系 - 块A(0-3) 和 块B(4-7) 是伙伴相邻且大小相同可合并成order3的块包含页框0-7 - 块C(8-11) 和 块D(12-15) 是伙伴相邻且大小相同可合并成order3的块包含页框8-15 - 块B(4-7) 和 块C(8-11) 不是伙伴虽然相邻但合并后起始地址4不对齐到8的倍数分配算法算法流程伙伴系统的分配算法遵循以下步骤graph TD A[请求分配orderk的块] -- B{检查orderk的空闲链表} B --|有空闲块| C[从链表取出一个块] C -- D[标记为已分配] D -- E[返回块地址] B --|无空闲块| F[检查orderk1] F -- G{有空闲块?} G --|是| H[分割块] H -- I[将块分成两个orderk的块] I -- J[一个分配一个加入orderk链表] J -- E G --|否| K[继续向上查找orderk2...] K -- L{找到空闲块?} L --|是| M[递归分割直到orderk] M -- E L --|否| N[分配失败]分配算法伪代码structpage*alloc_pages(gfp_tgfp_mask,unsignedintorder){structzone*zone;structfree_area*area;structpage*page;unsignedintcurrent_order;// 1. 选择合适的zonezoneget_zone(gfp_mask);// 2. 从请求的order开始查找for(current_orderorder;current_orderMAX_ORDER;current_order){areazone-free_area[current_order];// 3. 检查是否有空闲块if(!list_empty(area-free_list[MIGRATE_TYPE])){// 4. 从链表中取出一个块// list_entry宏从链表节点(lru字段)的地址计算出struct page的起始地址// area-free_list[MIGRATE_TYPE].next 指向第一个空闲块的第一个页框的lru字段// 通过list_entry可以获取包含该lru字段的struct page指针代表块的第一个页框pagelist_entry(area-free_list[MIGRATE_TYPE].next,structpage,lru);// 从空闲链表中删除该块通过块的第一个页框的lru字段删除链表节点list_del(page-lru);// 更新该order的空闲块计数area-nr_free--;// 5. 如果取出的块比需要的大需要分割if(current_orderorder){// 分割块expand(zone,page,order,current_order,area);}// 6. 设置页标志set_page_private(page,order);returnpage;}}// 7. 所有order都没有空闲块分配失败returnNULL;}分割算法expand当从更大的块中分配时需要将块分割staticinlinevoidexpand(structzone*zone,structpage*page,intlow,inthigh,structfree_area*area){unsignedlongsize1high;// 原始块大小// 循环分割直到达到需要的orderwhile(highlow){area--;// 移到下一个更小的orderhigh--;// order减1size1;// 大小减半// 创建伙伴块高地址的一半structpage*buddypagesize;// 将伙伴块加入空闲链表通过buddy-lru字段添加到链表list_add(buddy-lru,area-free_list[MIGRATE_TYPE]);area-nr_free;// 设置伙伴块的orderset_page_private(buddy,high);}}分配示例场景请求分配order1的块2个页框但order1没有空闲块初始状态 order0: 无空闲块 order1: 无空闲块 order2: [块A: 页框0-3] ← 有空闲块 步骤1从order2取出块A4个页框 步骤2分割块A - 低地址一半页框0-1→ 分配出去order1 - 高地址一半页框2-3→ 加入order1的空闲链表 结果 order0: 无空闲块 order1: [块B: 页框2-3] ← 新加入的空闲块 order2: 无空闲块 分配页框0-1已分配释放与合并算法算法流程释放内存时伙伴系统会尝试合并伙伴块是是否否释放orderk的块将块加入orderk的空闲链表检查伙伴块是否空闲?合并两个块形成orderk1的块从orderk链表移除两个块将合并后的块加入orderk1链表可以继续合并?检查orderk1的伙伴完成释放算法伪代码void__free_pages(structpage*page,unsignedintorder){structzone*zonepage_zone(page);unsignedlongpage_idxpage_to_pfn(page);structfree_area*area;unsignedintcurrent_orderorder;// 1. 循环尝试合并直到无法合并为止while(current_orderMAX_ORDER-1){// 2. 计算伙伴块的页框号unsignedlongbuddy_idx__find_buddy_index(page_idx,current_order);structpage*buddypage(buddy_idx-page_idx);// 3. 检查伙伴块是否存在、是否空闲、是否在同一zoneif(!page_is_buddy(page,buddy,current_order))break;// 无法合并退出循环// 4. 伙伴块可以合并// 从空闲链表中移除伙伴块通过lru字段删除链表节点list_del(buddy-lru);areazone-free_area[current_order];area-nr_free--;// 5. 清除伙伴块的order标记clear_page_private(buddy);// 6. 确定合并后块的起始地址取较小的页框号if(buddy_idxpage_idx)page_idxbuddy_idx;// 7. 准备合并到下一个更大的ordercurrent_order;pagepage(page_idx-page_to_pfn(page));}// 8. 将最终合并后的块加入空闲链表// 通过page-lru字段将块添加到对应order的空闲链表中// page指向块的第一个页框通过lru字段连接成链表areazone-free_area[current_order];list_add(page-lru,area-free_list[MIGRATE_TYPE]);area-nr_free;set_page_private(page,current_order);}伙伴块检查函数staticinlineintpage_is_buddy(structpage*page,structpage*buddy,unsignedintorder){// 1. 检查伙伴块是否在同一zoneif(page_zone(page)!page_zone(buddy))return0;// 2. 检查伙伴块是否在伙伴系统中通过检查PG_buddy标志if(!PageBuddy(buddy))return0;// 3. 检查伙伴块的order是否匹配if(page_order(buddy)!order)return0;return1;// 是有效的伙伴块}释放示例场景释放页框2-3order1其伙伴块页框0-1也是空闲的order1释放前状态 order0: 无空闲块 order1: [块A: 页框0-1] ← 空闲 order2: 无空闲块 步骤1释放页框2-3order1 步骤2检查伙伴块页框0-1 - 页框0-1是空闲的order1 - 可以合并 步骤3合并两个order1的块 - 移除块A页框0-1和块B页框2-3 - 合并成order2的块页框0-3 - 加入order2的空闲链表 结果 order0: 无空闲块 order1: 无空闲块 order2: [块C: 页框0-3] ← 合并后的块完整示例示例内存分配和释放的完整过程假设系统有16个页框页框号0-15初始状态所有页框都在order3的空闲链表中8个页框的块。初始状态 order3: [块: 页框0-7] [块: 页框8-15] 内存布局 页框: 0 1 2 3 4 5 6 7 | 8 9 10 11 12 13 14 15 ┌─────────────────────┐ ┌─────────────────────┐ 块A (order3) 块B (order3) └─────────────────────┘ └─────────────────────┘操作1分配order12个页框步骤1order1无空闲块向上查找 步骤2order2无空闲块继续向上 步骤3order3有空闲块取出块A 步骤4分割块A - order2: 页框0-3继续分割 - order2: 页框4-7加入空闲链表 步骤5继续分割页框0-3 - order1: 页框0-1分配出去 - order1: 页框2-3加入空闲链表 结果 order1: [页框2-3] order2: [页框4-7] order3: [页框8-15] 已分配: 页框0-1操作2分配order24个页框步骤1order2有空闲块页框4-7直接分配 结果 order1: [页框2-3] order2: 无空闲块 order3: [页框8-15] 已分配: 页框0-1, 页框4-7操作3释放页框0-1order1步骤1检查伙伴块页框2-3 - 页框2-3是空闲的order1 - 可以合并 步骤2合并成order2的块页框0-3 结果 order1: 无空闲块 order2: [页框0-3] order3: [页框8-15] 已分配: 页框4-7操作4释放页框4-7order2步骤1检查伙伴块页框0-3 - 页框0-3是空闲的order2 - 可以合并 步骤2合并成order3的块页框0-7 结果 order1: 无空闲块 order2: 无空闲块 order3: [页框0-7] [页框8-15] 已分配: 无为什么同一个order下会有多个块关键理解free_area中存储的是已经合并过的块但合并是有条件的示例为什么order1下会有多个块假设内存状态如下内存布局16个页框 页框: 0 1 | 2 3 | 4 5 | 6 7 | 8 9 | 10 11 | 12 13 | 14 15 ┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────────────┐ ┌────┐ ┌────┐ 已分 空闲 已分 空闲 空闲 空闲 已分 空闲 └────┘ └────┘ └────┘ └────┘ └────────────┘ └────┘ └────┘ 块A 块B 块C 块D 块E 块F 块G 块H分析块B页框2-3和块D页框6-7都是order1的空闲块但它们不是伙伴块B的伙伴是页框0-1已分配无法合并块D的伙伴是页框4-5已分配无法合并块B和块D虽然都是order1但不相邻中间隔着页框4-5不满足伙伴关系所以块E和块F会合并成order2的块页框8-11正确的状态应该是order1: [块B: 页框2-3] [块D: 页框6-7] [块H: 页框14-15] order2: [块EF: 页框8-11] ← 块E和块F已合并总结✅free_area中存储的是合并后的块能合并的都已经合并了✅同一order下多个块的原因这些块之间不是伙伴关系不相邻或不对齐它们的伙伴块已经被分配所以无法合并例如页框2-3和页框6-7都是order1但它们的伙伴页框0-1和页框4-5都被分配了所以无法合并性能分析时间复杂度分配操作O(log n)其中n是最大order值最坏情况需要从MAX_ORDER向下分割到请求的order平均情况如果对应order有空闲块O(1)释放操作O(log n)最坏情况需要合并到MAX_ORDER平均情况通常只需要合并几次空间复杂度元数据开销每个空闲块只需要链表节点开销很小内存利用率由于只能分配2的幂次大小存在内部碎片性能优化迁移类型分类按MIGRATE_TYPES分类减少碎片水线标记通过pages_min/pages_low/pages_high控制内存回收每CPU缓存使用per-CPU页框缓存减少锁竞争优缺点总结优点✅分配速度快O(1)到O(log n)的时间复杂度✅保证物理连续性分配的页框物理地址连续满足DMA需求✅自动合并机制减少外部碎片✅实现简单算法清晰易于理解和维护✅可预测性分配时间可预测适合实时系统缺点❌内部碎片严重只能分配2的幂次大小浪费内存❌不适合小对象最小分配单位是4KB一页❌内存浪费实际需求与分配大小不匹配时造成浪费❌最大分配限制通常最大4MBMAX_ORDER11❌合并开销释放时需要检查并合并伙伴块内部碎片示例请求分配5个页框20KB 实际分配8个页框32KBorder3 浪费3个页框12KB37.5%的浪费率实际应用内核中的使用DMA缓冲区分配// DMA需要物理连续的内存dma_addr_tdma_addrdma_map_single(dev,buf,size,DMA_TO_DEVICE);大页内存Huge Page// 分配大页内存提高TLB效率alloc_huge_page(vma,addr,0);SLAB分配器的底层支持// SLAB从伙伴系统获取页框然后细分为小对象structpage*pagealloc_pages(GFP_KERNEL,0);分配器选择建议// 根据需求选择合适的分配方式if(size4KB){// 使用SLAB/SLUB或kmallockmalloc(size,GFP_KERNEL);}elseif(size128KBneed_physically_contiguous){// 使用kmalloc底层使用伙伴系统kmalloc(size,GFP_KERNEL);}elseif(size4KBneed_physically_contiguous){// 直接使用伙伴系统unsignedintorderget_order(size);alloc_pages(GFP_KERNEL,order);}else{// 不需要物理连续使用vmallocvmalloc(size);}调试工具查看伙伴系统状态# 查看/proc/buddyinfocat/proc/buddyinfo# 输出示例Node0, zone Normal11112222220# 表示order0有1个空闲块order1有1个空闲块等等查看页框信息# 查看/proc/pagetypeinfocat/proc/pagetypeinfo总结伙伴系统是Linux内核内存管理的基石它通过巧妙的2的幂次组织和伙伴关系实现了高效的大块连续内存管理。虽然存在内部碎片的问题但通过与其他分配器如SLAB/SLUB的配合形成了完整的内存管理体系。理解伙伴系统的原理对于深入理解Linux内核内存管理至关重要也是进行内核内存优化和调试的基础。