注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mr. almost

Never mind,live goes on.On my way again.

 
 
 

日志

 
 

Linux大块内存管理之伙伴系统[为了适应潮流,叫基友系统吧(-_-)|| ]  

2011-12-11 12:11:48|  分类: linux |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 转自Linux Kernel Exploration   Link:http://ilinuxkernel.com/?p=1029

伙伴算法

Linux内核内存管理的任务包括:

  • 遵从CPU的MMU(Memory Management Unit)机制
  • 合理、有效、快速地管理内存
  • 实现内存保护机制
  • 实现虚拟内存
  • 共享
  • 重定位

Linux内核通过伙伴算法来管理物理内存。伙伴系统(Buddy System)在理论上是非常简单的内存分配算法。它的用途主要是尽可能减少外部碎片,同时允许快速分配与回收物理页面。为了减少外部碎片,连续的空闲页面,根据空闲块(由连续的空闲页面组成)大小,组织成不同的链表(或者orders)。这样所有的2个页面大小的空闲块在一个链表中,4个页面大小的空闲块在另外一个链表中,以此类推。


注意,不同大小的块在空间上,不会有重叠。当一个需求为4个连续页面时,检查是否有4个页面的空闲块而快速满足请求。若该链表上(每个结点都是大小为4页面的块)有空闲的块,则分配给用户,否则向下一个级别(order)的链表中查找。若存在(8页面的)空闲块(现处于另外一个级别的链表上),则将该页面块分裂为两个4页面的块,一块分配给请求者,另外一块加入到4页面的块链表中。这样可以避免分裂大的空闲块,而此时有可以满足需求的小页面块,从而减少外面碎片。


伙伴算法举例
假设我们的系统内存只有16个页面RAM。因为RAM只有16个页面,我们只需用四个级别(orders)的伙伴位图(因为最大连续内存大小为16个页面),如下图所示。



在order(0),第一个bit表示开始的2个页面,第二个bit表示接下来的2个页面,以此类推。因为页面4已分配,而页面5空闲,故第三个bit为1。

同样在order(1)中,bit3是1的原因是一个伙伴完全空闲(页面8和9),和它对应的伙伴(页面10和11)却并非如此,故以后回收页面时,可以合并。

分配过程

当我们需要order(1)的空闲页面块时,则执行以下步骤:

1、初始空闲链表为:

order(0): 5, 10

order(1): 8 [8,9]

order(2): 12 [12,13,14,15]

order(3):

2、从上面空闲链表中,我们可以看出,order(1)链表上,有一个空闲的页面块,把它分配给用户,并从该链表中删除。

3、当我们再需要一个order(1)的块时,同样我们从order(1)空闲链表上开始扫描。

4、若在order(1)上没有空闲页面块,那么我们就到更高的级别(order)上找,order(2)。

5、此时有一个空闲页面块,该块是从页面12开始。该页面块被分割成两个稍微小一些order(1)的页面块,[12,13]和[14,15]。[14,15]页面块加到order(1)空闲链表中,同时[12,13]页面块返回给用户。

6、最终空闲链表为:

order(0): 5, 10

order(1): 14 [14,15]

order(2):

order(3):

回收过程

当我们回收页面11(order 0)时,则执行以下步骤:

1、找到在order(0)伙伴位图中代表页面11的位,计算使用下面公示:

index = page_idx >> (order + 1)

= 11 >> (0 + 1)

= 5

2、检查上面一步计算位图中相应bit的值。若该bit值为1,则和我们临近的,有一个空闲伙伴。Bit5的值为1(注意是从bit0开始的,Bit5即为第6bit),因为它的伙伴页面10是空闲的。

3、现在我们重新设置该bit的值为0,因为此时两个伙伴(页面10和页面11)完全空闲。

4、我们将页面10,从order(0)空闲链表中摘除。

5、此时,我们对2个空闲页面(页面10和11,order(1))进行进一步操作。

6、新的空闲页面是从页面10开始的,于是我们在order(1)的伙伴位图中找到它的索引,看是否有空闲的伙伴,以进一步进行合并操作。使用第一步中的计算公司,我们得到bit 2(第3位)。

7、Bit 2(order(1)位图)同样也是1,因为它的伙伴页面块(页面8和9)是空闲的。

8、重新设置bit2(order(1)位图)的值,然后在order(1)链表中删除该空闲页面块。

9、现在我们合并成了4页面大小(从页面8开始)的空闲块,从而进入另外的级别。在order(2)中找到伙伴位图对应的bit值,是bit1,且值为1,需进一步合并(原因同上)。

10、从oder(2)链表中摘除空闲页面块(从页面12开始),进而将该页面块和前面合并得到的页面块进一步合并。现在我们得到从页面8开始,大小为8个页面的空闲页面块。

11、我们进入另外一个级别,order(3)。它的位索引为0,它的值同样为0。这意味着对应的伙伴不是全部空闲的,所以没有再进一步合并的可能。我们仅设置该bit为1,然后将合并得到的空闲页面块放入order(3)空闲链表中。

12、最终我们得到大小为8个页面的空闲块:


系统运行实例

我们可以通过echo m > /proc/sysrq-trigger来查看当前系统内存各个Order空闲情况。

root@chen-ThinkPad-X200:/home/ chen # echo m > /proc/sysrq-trigger

root@ chen -ThinkPad-X200:/home/ chen # dmesg -c

SysRq : Show Memory

Mem-Info:

Node 0 DMA per-cpu:

CPU 0: hi: 0, btch: 1 usd: 0

CPU 1: hi: 0, btch: 1 usd: 0

Node 0 DMA32 per-cpu:

CPU 0: hi: 186, btch: 31 usd: 161

CPU 1: hi: 186, btch: 31 usd: 126

Node 0 Normal per-cpu:

CPU 0: hi: 186, btch: 31 usd: 156

CPU 1: hi: 186, btch: 31 usd: 87

active_anon:99525 inactive_anon:20358 isolated_anon:0

active_file:17376 inactive_file:85309 isolated_file:0

unevictable:4 dirty:119 writeback:0 unstable:0

free:714169 slab_reclaimable:7311 slab_unreclaimable:26660

mapped:33029 shmem:20884 pagetables:6715 bounce:0

Node 0 DMA free:15744kB min:256kB low:320kB high:384kB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:0kB isolated(anon):0kB isolated(file):0kB present:15352kB mlocked:0kB dirty:0kB writeback:0kB mapped:0kB shmem:0kB slab_reclaimable:0kB slab_unreclaimable:0kB kernel_stack:0kB pagetables:0kB unstable:0kB bounce:0kB writeback_tmp:0kB pages_scanned:0 all_unreclaimable? no

lowmem_reserve[]: 0 2960 3907 3907

Node 0 DMA32 free:2820564kB min:51008kB low:63760kB high:76512kB active_anon:77944kB inactive_anon:11228kB active_file:1792kB inactive_file:35936kB unevictable:0kB isolated(anon):0kB isolated(file):0kB present:3031688kB mlocked:0kB dirty:52kB writeback:0kB mapped:20340kB shmem:11376kB slab_reclaimable:1808kB slab_unreclaimable:960kB kernel_stack:40kB pagetables:1140kB unstable:0kB bounce:0kB writeback_tmp:0kB pages_scanned:0 all_unreclaimable? no

lowmem_reserve[]: 0 0 946 946

Node 0 Normal free:20368kB min:16312kB low:20388kB high:24468kB active_anon:320156kB inactive_anon:70204kB active_file:67712kB inactive_file:305300kB unevictable:16kB isolated(anon):0kB isolated(file):0kB present:969600kB mlocked:16kB dirty:424kB writeback:0kB mapped:111776kB shmem:72160kB slab_reclaimable:27436kB slab_unreclaimable:105680kB kernel_stack:2880kB pagetables:25720kB unstable:0kB bounce:0kB writeback_tmp:0kB pages_scanned:0 all_unreclaimable? no

lowmem_reserve[]: 0 0 0 0

Node 0 DMA: 2*4kB 1*8kB 1*16kB 1*32kB 1*64kB 0*128kB 1*256kB 0*512kB 1*1024kB 1*2048kB 3*4096kB = 15744kB

Node 0 DMA32: 81*4kB 28*8kB 63*16kB 32*32kB 31*64kB 26*128kB 11*256kB 6*512kB 1*1024kB 2*2048kB 684*4096kB = 2820564kB

Node 0 Normal: 176*4kB 80*8kB 29*16kB 10*32kB 3*64kB 5*128kB 22*256kB 9*512kB 3*1024kB 2*2048kB 0*4096kB = 20368kB

123579 total pagecache pages

0 pages in swap cache

Swap cache stats: add 0, delete 0, find 0/0

Free swap = 999416kB

Total swap = 999416kB

1032191 pages RAM

44206 pages reserved

183171 pages shared

180808 pages non-shared

root@chen-ThinkPad-X200:/home/chen#

  评论这张
 
阅读(496)| 评论(0)
推荐

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018