精华内容
下载资源
问答
  • 2018-07-09 15:45:04

    本节,我将介绍linux系统物理内存分配时所用到的技术——伙伴系统和slab缓存。
    伙伴系统
    使用场景:内核中很多时候要求分配连续页,为快速检测内存中的连续区域,内核采用了一种技术:伙伴系统。

    原理:系统中的空闲内存总是两两分组,每组中的两个内存块称作伙伴。伙伴的分配可以是彼此独立的。但如果两个小伙伴都是空闲的,内核将其合并为一个更大的内存块,作为下一层次上某个内存块的伙伴。如下图给出了一对伙伴,初始大小均为8页。

    内核对所有大小相同的小伙伴,都放置到统一列表中管理。如果系统现在需要8个页帧,则将16个页帧组成的块拆分为两个伙伴。其中一块用于满足应用程序的请求,而剩余的8个页帧则放置到对应8页大小内存块的列表中。

    如果下一个请求只需要2个连续页帧,则由8页组成的块分裂成2个伙伴,每个包含4个页帧。其中一块放置回伙伴列表中,而另一个再次分裂成2个伙伴,每个包含2页。其中一个回到伙伴系统,另一个则传递给应用程序。

    在应用程序释放内存时,内核可以直接检查地址,来判断是否创建一组伙伴,并合并为一个更大的内存块放回到伙伴列表中,这刚好是内存块分裂的逆过程,提高了较大内存块的可用性。

    slab缓存
    适用场景:内核本身经常需要比完整页帧小的多的内存块。

    原理:在伙伴系统基础上自行定义额外的内存管理层,将伙伴系统提供的页划分为更小的部分。

    方法1:对频繁使用的对象,内核定义了只包含了所需类型对象实例的缓存。每次需要某种对象时,可以从对应的缓存快速分配(使用后释放到缓存)。slab缓存自动维护与伙伴系统的交互,在缓存用尽时会请求新的页帧。

    方法2:对通常情况下小内存块的分配,内核针对不同大小的对象定义了一组slab缓存,可以像用户空间编程一样,用相同的函数访问这些缓存。不同之处是这些函数都增加了前缀k,表明是与内核相关联的:kmalloc和kfree。

    1.原理

    Linux的伙伴算法把所有的空闲页面分为10个块组,每组中块的大小是2的幂次方个页面,例如,第0组中块的大小都为20 (1个页面),第1组中块的大小为都为21(2个页面),第9组中块的大小都为29(512个页面)。也就是说,每一组中块的大小是相同的,且这同样大小的块形成一个链表。

    我们通过一个简单的例子来说明该算法的工作原理。

    假设要求分配的块其大小为128个页面(由多个页面组成的块我们就叫做页面块)。该算法先在块大小为128个页面的链表中查找,看是否有这样一个空闲块。如果有,就直接分配;如果没有,该算法会查找下一个更大的块,具体地说,就是在块大小为256个页面的链表中查找一个空闲块。如果存在这样的空闲块,内核就把这256个页面分为两等份,一份分配出去,另一份插入到块大小为128个页面的链表中。如果在块大小为256个页面的链表中也没有找到空闲页块,就继续找更大的块,即512个页面的块。如果存在这样的块,内核就从512个页面的块中分出128个页面满足请求,然后从384个页面中取出256个页面插入到块大小为256个页面的链表中。然后把剩余的128个页面插入到块大小为128个页面的链表中。如果512个页面的链表中还没有空闲块,该算法就放弃分配,并发出出错信号。

    以上过程的逆过程就是块的释放过程,这也是该算法名字的来由。满足以下条件的两个块称为伙伴:

    · 两个块的大小相同

    · 两个块的物理地址连续

    伙伴算法把满足以上条件的两个块合并为一个块,该算法是迭代算法,如果合并后的块还可以跟相邻的块进行合并,那么该算法就继续合并。

    6.3.3 Slab分配机制

    采用伙伴算法分配内存时,每次至少分配一个页面。但当请求分配的内存大小为几十个字节或几百个字节时应该如何处理?如何在一个页面中分配小的内存区,小内存区的分配所产生的内碎片又如何解决?

    Linux2.0采用的解决办法是建立了13个空闲区链表,它们的大小从32字节到132056字节。从Linux2.2开始,MM的开发者采用了一种叫做slab的分配模式,该模式早在1994年就被开发出来,用于Sun Microsystem Solaris 2.4操作系统中。Slab的提出主要是基于以下考虑:

    · 内核对内存区的分配取决于所存放数据的类型。例如,当给用户态进程分配页面时,内核调用get_free_page()函数,并用0填充这个页面。 而给内核的数据结构分配页面时,事情没有这么简单,例如,要对数据结构所在的内存进行初始化、在不用时要收回它们所占用的内存。因此,Slab中引入了对象这个概念,所谓对象就是存放一组数据结构的内存区,其方法就是构造或析构函数,构造函数用于初始化数据结构所在的内存区,而析构函数收回相应的内存区。但为了便于理解,你也可以把对象直接看作内核的数据结构。为了避免重复初始化对象,Slab分配模式并不丢弃已分配的对象,而是释放但把它们依然保留在内存中。当以后又要请求分配同一对象时,就可以从内存获取而不用进行初始化,这是在Solaris 中引入Slab的基本思想。

    实际上,Linux中对Slab分配模式有所改进,它对内存区的处理并不需要进行初始化或回收。出于效率的考虑,Linux并不调用对象的构造或析构函数,而是把指向这两个函数的指针都置为空。Linux中引入Slab的主要目的是为了减少对伙伴算法的调用次数。

    · 实际上,内核经常反复使用某一内存区。例如,只要内核创建一个新的进程,就要为该进程相关的数据结构(task_struct、打开文件对象等)分配内存区。当进程结束时,收回这些内存区。因为进程的创建和撤销非常频繁,因此,Linux的早期版本把大量的时间花费在反复分配或回收这些内存区上。从Linux2.2开始,把那些频繁使用的页面保存在高速缓存中并重新使用。

    · 可以根据对内存区的使用频率来对它分类。对于预期频繁使用的内存区,可以创建一组特定大小的专用缓冲区进行处理,以避免内碎片的产生。对于较少使用的内存区,可以创建一组通用缓冲区(如Linux2.0中所使用的2的幂次方)来处理,即使这种处理模式产生碎片,也对整个系统的性能影响不大。

    · 硬件高速缓存的使用,又为尽量减少对伙伴算法的调用提供了另一个理由,因为对伙伴算法的每次调用都会“弄脏”硬件高速缓存,因此,这就增加了对内存的平均访问次数。

    Slab分配模式把对象分组放进缓冲区(尽管英文中使用了Cache这个词,但实际上指的是内存中的区域,而不是指硬件高速缓存)。因为缓冲区的组织和管理与硬件高速缓存的命中率密切相关,因此,Slab缓冲区并非由各个对象直接构成,而是由一连串的“大块(Slab)”构成,而每个大块中则包含了若干个同种类型的对象,这些对象或已被分配,或空闲,如图6.12所示。一般而言,对象分两种,一种是大对象,一种是小对象。所谓小对象,是指在一个页面中可以容纳下好几个对象的那种。例如,一个inode结构大约占300多个字节,因此,一个页面中可以容纳8个以上的inode结构,因此,inode结构就为小对象。Linux内核中把小于512字节的对象叫做小对象。

    实际上,缓冲区就是主存中的一片区域,把这片区域划分为多个块,每块就是一个Slab,每个Slab由一个或多个页面组成,每个Slab中存放的就是对象。

    因为Slab分配模式的实现比较复杂,我们不准备对其进行详细的分析,只对主要内容给予描述。

    Jeff 发现对内核中普通对象进行初始化所需的时间超过了对其进行分配和释放所需的时间。因此他的结论是不应该将内存释放回一个全局的内存池,而是将内存保持为针对特定目而初始化的状态。

    更多相关内容
  • 内存分配算法代码模拟。包含 首次适应算法(First Fit) 最佳适应算法(Best Fit)最差适应算法(Worst Fit)伙伴算法(buddy) https://blog.csdn.net/GreyBtfly/article/details/84646981
  • 实现了一个小的伙伴系统内存分配算法,和linux的页框分配算法类似
  • 伙伴分配程序把内存块存放在比链接表更先进的数据结构中。这些结构常常是桶型、树型和堆型的组合或变种。一般来说,伙伴分配程序的工作方式是难以描述的,因为这种技术随所选数据结构的不同而各异。由于有各种各样的...

    伙伴(buddy)算法,它不能根据需要从被管理内存的开头部分创建新内存。它有明确的共性,就是各个内存块可分可合,但不是任意的分与合。每个块都有个朋友,或叫“伙伴”,既可与之分开,又可与之结合。伙伴分配程序把内存块存放在比链接表更先进的数据结构中。这些结构常常是桶型、树型和堆型的组合或变种。一般来说,伙伴分配程序的工作方式是难以描述的,因为这种技术随所选数据结构的不同而各异。由于有各种各样的具有已知特性的数据结构可供使用,所以伙伴分配程序得到广泛应用。有些伙伴分配程序甚至用在源码中。伙伴分配程序编写起来常常很复杂,其性能可能各不相同。伙伴分配程序通常在某种程度上限制内存碎片。

    伙伴算法管理的是物理内存。

    伙伴算法作用:  

    通常情况下,一个高级操作系统必须要给进程提供基本的、能够在任意时刻申请和释放任意大小内存的功能,就像malloc 函数那样,然而,实现malloc 函数并不简单,由于进程申请内存的大小是任意的,如果操作系统对malloc 函数的实现方法不对,将直接导致一个不可避免的问题,那就是内存碎片。

    内存碎片就是内存被分割成很小很小的一些块,这些块虽然是空闲的,但是却小到无法使用。随着申请和释放次数的增加,内存将变得越来越不连续。最后,整个内存将只剩下碎片,即使有足够的空闲页框可以满足请求,但要分配一个大块的连续页框就可能无法满足,所以减少内存浪费的核心就是尽量避免产生内存碎片。针对这样的问题,有很多行之有效的解决方法,其中伙伴算法被证明是非常行之有效的一套内存管理方法,因此也被相当多的操作系统所采用。

    伙伴算法(Buddy system)把所有的空闲页框分为11个块链表,每块链表中分布包含特定的连续页框地址空间,比如第0个块链表包含大小为2^0个连续的页框,第1个块链表中,每个链表元素包含2个页框大小的连续地址空间,….,第10个块链表中,每个链表元素代表4M的连续地址空间。每个链表中元素的个数在系统初始化时决定,在执行过程中,动态变化。

         伙伴算法每次只能分配2的幂次个页框的空间,比如一次分配1页,2页,4页,8页,…,1024页(2^10)等等,每页大小一般为4K,因此,伙伴算法最多一次能够分配4M(1024*4K)的内存空间。

    核心概念和数据结构

          两个内存块,大小相同,地址连续,同属于一个大块区域。(第0块和第1块是伙伴,第2块和第3块是伙伴,但第1块和第2块不是伙伴)

          伙伴位图:用一位描述伙伴块的状态位码,称之为伙伴位码。比如,bit0为第0块和第1块的伙伴位码,如果bit0为1,表示这两块至少有一块已经分配出去,如果bit0为0,说明两块都空闲,还没分配。

          Linux2.6为每个管理区使用不同的伙伴系统,内核空间分为三种区,DMA,NORMAL,HIGHMEM,对于每一种区,都有对应的伙伴算法,

          1. free_area数组:

            image

       

       1:  struct zone{
         
       2:     ....
       3:     struct free_area    free_area[MAX_ORDER];  
       4:     ....
       5:  }

       struct free_area  free_area[MAX_ORDER]    #MAX_ORDER 默认值为11,分别存放着11个组,free_area结构体里面又标注了该组别空闲内存块的情况。

          2.  zone_mem_map数组

          伙伴系统算法

       free_area数组中,第K个元素,它标识所有大小为2^k的空闲块,所有空闲快由free_list指向的双向循环链表组织起来。其中的nr_free,它指定了对应空间剩余块的个数。

       整个分配图示,大概如下:

    image

     


    内存分配原理

          比如,要分配4(2^2)页(16k)的内存空间,算法会先从free_area[2]中查看nr_free是否为空,如果有空闲块,就直接从中摘下并分配出去,如果没有空闲块,就顺着数组向上查找,从它的上一级free_area[3](每块32K)中分配,如果free_area[3]中有空闲块,则将其从链表中摘下,分成等大小的两部分,前四个页面作为一个块插入free_area[2],后4个页面分配出去,如果free_area[3]也没有空闲,则从更上一级申请空间,如果free_area[4]中有,就将这16(2*2*2*2)个页面等分成两份,前一半挂在free_area[3]的链表头部,后一半的8个页等分成两等分,前一半挂free_area[2]的链表中,后一半分配出去。依次递推,直到free_area[max_order],如果顶级都没有空间,那么就报告分配失败。


    内存释放原理(回收内存)

          释放是申请的逆过程,也可以看作是伙伴的合并过程。当释放一个内存块时,先在其对于的free_area链表中查找是否有伙伴存在,如果没有伙伴块,直接将释放的块插入链表头。如果有或板块的存在,则将其从链表摘下,合并成一个大块,然后继续查找合并后的块在更大一级链表中是否有伙伴的存在,直至不能合并或者已经合并至最大块2^10为止。

    内核试图将大小为b的一对空闲块(一个是现有空闲链表上的,一个是待回收的),合并为一个大小为2b的单独块,如果它成功合并所释放的块,它会试图合并2b大小的块。


    整个过程中,位图扮演了重要的角色,如图2所示,位图的某一位对应两个互为伙伴的块,为1表示其中一块已经分配出去了,为0表示两块都空闲或都已被使用。伙伴中无论是分配还是释放都只是相对的位图进行异或操作。分配内存时对位图的是为释放过程服务,释放过程根据位图判断伙伴是否存在,如果对相应位的异或操作得1,则没有伙伴可以合并,如果异或操作得0,就进行合并,并且继续按这种方式合并伙伴,直到不能合并为止。

    关于位图

    Linux内核伙伴算法中每个order 的位图都表示所有的空闲块,位图的某位对应于两个伙伴块,为1就表示其中一块忙,为0表示两块都闲或都在使用。系统每次分配和回收伙伴块时都要对它们的伙伴位跟1进行异或运算。所谓异或是指刚开始时,两个伙伴块都空闲,它们的伙伴位为0,如果其中一块被使用,异或后得1;如果另一块也被使用,异或后得0;如果前面一块回收了异或后得1;如果另一块也回收了异或后得0。
    位图的主要用途是在回收算法中指示是否可以和伙伴块合并,分配时只要搜索空闲链表就足够了。当然,分配的同时还要对相应位异或一下,这是为回收算法服务。

    关于分配算法

    假设在初始阶段,全是大小为2^9大小的块( MAX_ORDER为10),序号依次为0, 512, 1024等等,并且所有area的map位都为0(实际上操作系统代码要占一部分空间,但这里只是举例),现在要分配一个2^3大小的页面块,有以下动作:
    1. 从order为3的area的空闲链表开始搜索,没找到就向高一级area搜索,依次类推,按照假设条件,会一直搜索到order为9的area,找到了序号为0的2^9页块。
    2. 把序号为0的2^9页块从order为9的area的空闲链表中摘除并对该area的第0位( 0>>(1+9) )异或一下得1。

    对area的第(序号右移(1+order)的结果)位跟1异或一下
    3. 把序号为0的2^9页块拆分成两个序号分别为0和256的2^8页块,前者放入order为8的area的空闲链表中,并对该area的第0位( 0>>(1+8) )异或一下得1。
    4. 把序号为256的2^8页块拆分成两个序号分别为256和384的2^7页块,前者放入order为7的area的空闲链表中,并对该area的第1位( 256>>(1+7) )异或一下得1。
    5. 把序号为384的2^7页块拆分成两个序号分别为384和448的2^6页块,前者放入order为6的area的空闲链表中,并对该area的第3位( 384>>(1+6) )异或一下得1。
    6. 把序号为448的2^6页块拆分成两个序号分别为448和480的2^5页块,前者放入order为5的area的空闲链表中,并对该area的第7位( 448>>(1+5) )异或一下得1。
    7. 把序号为480的2^5页块拆分成两个序号分别为480和496的2^4页块,前者放入order为4的area的空闲链表中,并对该area的第15位( 480>>(1+4) )异或一下得1。
    8. 把序号为496的2^4页块拆分成两个序号分别为496和504的2^3页块,前者放入order为3的area的空闲链表中,并对该area的第31位( 496>>(1+3) )异或一下得1。
    9. 序号为504的2^3页块就是所求的块。

    把序号为n的页面块插入order为i的area时,需要对该area的map位(n>>(1+order))跟1异或,更新map值

    关于回收算法

    1.当回收序号为4的1页块时,先找到order为0的area,把该页面块加入到该area的空闲链表中,然后判断其伙伴块(序号为5的1页块)的状态,读该area (不是其它area !)的map的第2(下标为2 序号右移1+order的结果)位( 4>>(1+order) ),假设伙伴块被占,则该位为0(回收4块前,4、5块都忙),现跟1异或一下得1,并不再向上合并。
    2.当回收序号为5的1页块时,同理,先找到order为0的area,把该页面块加入到该area的空闲链表中,然后判断其伙伴块(序号为4的1页块)的状态,读该area的map的第2位(5>>(1+order) ),这时该位为1(先前4块已回收,5块占用),现跟1异或一下得0,并向上合并,把序号为4的1页块和序号为5的1页块从该area的空闲链表中摘除,合并成序号为4的2页块,并放到order为1的area的空闲链表中。同理,此时又要判断合并后的块的伙伴块(序号为6的2页块)的状态,读该area(order为1的area,不是其它!)的map的第1位((4>>(1+order) ),假设伙伴块在此之前已被回收,则该位为1,现异或一下得0,并向上合并,把序号为4的2页块和序号为6的2页块从order为1的area的空闲链表中摘除,合并成序号为4的4页块,并放到order为2的area的空闲链表中。然后再判断其伙伴块状态,如此反复。

    回收的页面块假设序号为n,检查order为i的该area中的map[n>>(1+order)],将该map值跟1异或,若结果为0,则序号n的页面块可跟其伙伴块合并,否则不能合并。

    回收的页块若能与伙伴块合并,插入上一级的area中,则视合并块为之前已被占用,然后根据该area中其伙伴块的状态(已被回收或者被占用)判断其map位是1(其伙伴块已被回收)还是0(其伙伴块被占用),再让map位跟1异或一下,结果为0则再合并,结果为1则不再合并。map的第几位(下标)判断依据:页块的序号>>(1+order)

    另一个例子(位图的使用):假设我们的系统内存只有16个页面RAM。因为RAM只有16个页面,我们只需用四个级别(orders)的伙伴位图(因为最大连续内存大小为16个页面),如下图所示。(2^4=16)


    初始位图:

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

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

    分配过程

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

    1、初始空闲链表为:

    order(0): 5, 10  (空闲块为什么不是5、8、9、10、12、13、14、15)

    order(1): 8 [8,9]   (空闲块为什么不是8[8,9]、12[12,13]、14[14,15])

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

    order(3): 无空闲块

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

    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 >> (1 + 0)

    = 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位)(10>>(1+1))。

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

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

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

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

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

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


    Buddy算法的优缺点:

    伙伴算法的一大优势是它能够完全避免外部碎片的产生,申请时,伙伴算法会给程序分配一个较大的内存空间,即保证所有大块内存都能得到满足。很明显分配比需求还大的内存空间,会产生内部碎片。所以伙伴算法虽然能够完全避免外部碎片的产生,但这恰恰是以产生内部碎片为代价的。

     优点:

         较好的解决外部碎片问题

         当需要分配若干个内存页面时,用于DMA的内存页面必须连续,伙伴算法很好的满足了这个要求

         只要请求的块不超过512个页面(2K),内核就尽量分配连续的页面。

         针对大内存分配设计。

    缺点:

          1. 合并的要求太过严格,只能是满足伙伴关系的块才能合并,比如第1块和第2块就不能合并。

          2. 碎片问题:一个连续的内存中仅仅一个页面被占用,导致整块内存区都不具备合并的条件

          3. 浪费问题:伙伴算法只能分配2的幂次方内存区,当需要8K(2页)时,好说,当需要9K时,那就需要分配16K(4页)的内存空间,但是实际只用到9K空间,多余的7K空间就被浪费掉。

          4. 算法的效率问题: 伙伴算法拆分和合并涉及了比较多的计算还有链表和位图的操作,开销还是比较大的,如果每次2^n大小的伙伴块就会合并到2^(n+1)的链表队列中,那么2^n大小链表中的块就会因为合并操作而减少,但系统随后立即有可能又有对该大小块的需求,为此必须再从2^(n+1)大小的链表中拆分,这样的合并又立即拆分的过程是无效率的。

     Linux针对大内存的物理地址分配,采用伙伴算法,如果是针对小于一个page的内存,频繁的分配和释放,有更加适宜的解决方案,如slab和kmem_cache等


    伙伴(buddy)算法,它不能根据需要从被管理内存的开头部分创建新内存。它有明确的共性,就是各个内存块可分可合,但不是任意的分与合。每个块都有个朋友,或叫“伙伴”,既可与之分开,又可与之结合。伙伴分配程序把内存块存放在比链接表更先进的数据结构中。这些结构常常是桶型、树型和堆型的组合或变种。一般来说,伙伴分配程序的工作方式是难以描述的,因为这种技术随所选数据结构的不同而各异。由于有各种各样的具有已知特性的数据结构可供使用,所以伙伴分配程序得到广泛应用。有些伙伴分配程序甚至用在源码中。伙伴分配程序编写起来常常很复杂,其性能可能各不相同。伙伴分配程序通常在某种程度上限制内存碎片。

    伙伴算法管理的是物理内存。

    伙伴算法作用:  

    通常情况下,一个高级操作系统必须要给进程提供基本的、能够在任意时刻申请和释放任意大小内存的功能,就像malloc 函数那样,然而,实现malloc 函数并不简单,由于进程申请内存的大小是任意的,如果操作系统对malloc 函数的实现方法不对,将直接导致一个不可避免的问题,那就是内存碎片。

    内存碎片就是内存被分割成很小很小的一些块,这些块虽然是空闲的,但是却小到无法使用。随着申请和释放次数的增加,内存将变得越来越不连续。最后,整个内存将只剩下碎片,即使有足够的空闲页框可以满足请求,但要分配一个大块的连续页框就可能无法满足,所以减少内存浪费的核心就是尽量避免产生内存碎片。针对这样的问题,有很多行之有效的解决方法,其中伙伴算法被证明是非常行之有效的一套内存管理方法,因此也被相当多的操作系统所采用。

    伙伴算法(Buddy system)把所有的空闲页框分为11个块链表,每块链表中分布包含特定的连续页框地址空间,比如第0个块链表包含大小为2^0个连续的页框,第1个块链表中,每个链表元素包含2个页框大小的连续地址空间,….,第10个块链表中,每个链表元素代表4M的连续地址空间。每个链表中元素的个数在系统初始化时决定,在执行过程中,动态变化。

         伙伴算法每次只能分配2的幂次个页框的空间,比如一次分配1页,2页,4页,8页,…,1024页(2^10)等等,每页大小一般为4K,因此,伙伴算法最多一次能够分配4M(1024*4K)的内存空间。

    核心概念和数据结构

          两个内存块,大小相同,地址连续,同属于一个大块区域。(第0块和第1块是伙伴,第2块和第3块是伙伴,但第1块和第2块不是伙伴)

          伙伴位图:用一位描述伙伴块的状态位码,称之为伙伴位码。比如,bit0为第0块和第1块的伙伴位码,如果bit0为1,表示这两块至少有一块已经分配出去,如果bit0为0,说明两块都空闲,还没分配。

          Linux2.6为每个管理区使用不同的伙伴系统,内核空间分为三种区,DMA,NORMAL,HIGHMEM,对于每一种区,都有对应的伙伴算法,

          1. free_area数组:

            image

       

       1:  struct zone{
         
       2:     ....
       3:     struct free_area    free_area[MAX_ORDER];  
       4:     ....
       5:  }

       struct free_area  free_area[MAX_ORDER]    #MAX_ORDER 默认值为11,分别存放着11个组,free_area结构体里面又标注了该组别空闲内存块的情况。

          2.  zone_mem_map数组

          伙伴系统算法

       free_area数组中,第K个元素,它标识所有大小为2^k的空闲块,所有空闲快由free_list指向的双向循环链表组织起来。其中的nr_free,它指定了对应空间剩余块的个数。

       整个分配图示,大概如下:

    image

     


    内存分配原理

          比如,要分配4(2^2)页(16k)的内存空间,算法会先从free_area[2]中查看nr_free是否为空,如果有空闲块,就直接从中摘下并分配出去,如果没有空闲块,就顺着数组向上查找,从它的上一级free_area[3](每块32K)中分配,如果free_area[3]中有空闲块,则将其从链表中摘下,分成等大小的两部分,前四个页面作为一个块插入free_area[2],后4个页面分配出去,如果free_area[3]也没有空闲,则从更上一级申请空间,如果free_area[4]中有,就将这16(2*2*2*2)个页面等分成两份,前一半挂在free_area[3]的链表头部,后一半的8个页等分成两等分,前一半挂free_area[2]的链表中,后一半分配出去。依次递推,直到free_area[max_order],如果顶级都没有空间,那么就报告分配失败。


    内存释放原理(回收内存)

          释放是申请的逆过程,也可以看作是伙伴的合并过程。当释放一个内存块时,先在其对于的free_area链表中查找是否有伙伴存在,如果没有伙伴块,直接将释放的块插入链表头。如果有或板块的存在,则将其从链表摘下,合并成一个大块,然后继续查找合并后的块在更大一级链表中是否有伙伴的存在,直至不能合并或者已经合并至最大块2^10为止。

    内核试图将大小为b的一对空闲块(一个是现有空闲链表上的,一个是待回收的),合并为一个大小为2b的单独块,如果它成功合并所释放的块,它会试图合并2b大小的块。


    整个过程中,位图扮演了重要的角色,如图2所示,位图的某一位对应两个互为伙伴的块,为1表示其中一块已经分配出去了,为0表示两块都空闲或都已被使用。伙伴中无论是分配还是释放都只是相对的位图进行异或操作。分配内存时对位图的是为释放过程服务,释放过程根据位图判断伙伴是否存在,如果对相应位的异或操作得1,则没有伙伴可以合并,如果异或操作得0,就进行合并,并且继续按这种方式合并伙伴,直到不能合并为止。

    关于位图

    Linux内核伙伴算法中每个order 的位图都表示所有的空闲块,位图的某位对应于两个伙伴块,为1就表示其中一块忙,为0表示两块都闲或都在使用。系统每次分配和回收伙伴块时都要对它们的伙伴位跟1进行异或运算。所谓异或是指刚开始时,两个伙伴块都空闲,它们的伙伴位为0,如果其中一块被使用,异或后得1;如果另一块也被使用,异或后得0;如果前面一块回收了异或后得1;如果另一块也回收了异或后得0。
    位图的主要用途是在回收算法中指示是否可以和伙伴块合并,分配时只要搜索空闲链表就足够了。当然,分配的同时还要对相应位异或一下,这是为回收算法服务。

    关于分配算法

    假设在初始阶段,全是大小为2^9大小的块( MAX_ORDER为10),序号依次为0, 512, 1024等等,并且所有area的map位都为0(实际上操作系统代码要占一部分空间,但这里只是举例),现在要分配一个2^3大小的页面块,有以下动作:
    1. 从order为3的area的空闲链表开始搜索,没找到就向高一级area搜索,依次类推,按照假设条件,会一直搜索到order为9的area,找到了序号为0的2^9页块。
    2. 把序号为0的2^9页块从order为9的area的空闲链表中摘除并对该area的第0位( 0>>(1+9) )异或一下得1。

    对area的第(序号右移(1+order)的结果)位跟1异或一下
    3. 把序号为0的2^9页块拆分成两个序号分别为0和256的2^8页块,前者放入order为8的area的空闲链表中,并对该area的第0位( 0>>(1+8) )异或一下得1。
    4. 把序号为256的2^8页块拆分成两个序号分别为256和384的2^7页块,前者放入order为7的area的空闲链表中,并对该area的第1位( 256>>(1+7) )异或一下得1。
    5. 把序号为384的2^7页块拆分成两个序号分别为384和448的2^6页块,前者放入order为6的area的空闲链表中,并对该area的第3位( 384>>(1+6) )异或一下得1。
    6. 把序号为448的2^6页块拆分成两个序号分别为448和480的2^5页块,前者放入order为5的area的空闲链表中,并对该area的第7位( 448>>(1+5) )异或一下得1。
    7. 把序号为480的2^5页块拆分成两个序号分别为480和496的2^4页块,前者放入order为4的area的空闲链表中,并对该area的第15位( 480>>(1+4) )异或一下得1。
    8. 把序号为496的2^4页块拆分成两个序号分别为496和504的2^3页块,前者放入order为3的area的空闲链表中,并对该area的第31位( 496>>(1+3) )异或一下得1。
    9. 序号为504的2^3页块就是所求的块。

    把序号为n的页面块插入order为i的area时,需要对该area的map位(n>>(1+order))跟1异或,更新map值

    关于回收算法

    1.当回收序号为4的1页块时,先找到order为0的area,把该页面块加入到该area的空闲链表中,然后判断其伙伴块(序号为5的1页块)的状态,读该area (不是其它area !)的map的第2(下标为2 序号右移1+order的结果)位( 4>>(1+order) ),假设伙伴块被占,则该位为0(回收4块前,4、5块都忙),现跟1异或一下得1,并不再向上合并。
    2.当回收序号为5的1页块时,同理,先找到order为0的area,把该页面块加入到该area的空闲链表中,然后判断其伙伴块(序号为4的1页块)的状态,读该area的map的第2位(5>>(1+order) ),这时该位为1(先前4块已回收,5块占用),现跟1异或一下得0,并向上合并,把序号为4的1页块和序号为5的1页块从该area的空闲链表中摘除,合并成序号为4的2页块,并放到order为1的area的空闲链表中。同理,此时又要判断合并后的块的伙伴块(序号为6的2页块)的状态,读该area(order为1的area,不是其它!)的map的第1位((4>>(1+order) ),假设伙伴块在此之前已被回收,则该位为1,现异或一下得0,并向上合并,把序号为4的2页块和序号为6的2页块从order为1的area的空闲链表中摘除,合并成序号为4的4页块,并放到order为2的area的空闲链表中。然后再判断其伙伴块状态,如此反复。

    回收的页面块假设序号为n,检查order为i的该area中的map[n>>(1+order)],将该map值跟1异或,若结果为0,则序号n的页面块可跟其伙伴块合并,否则不能合并。

    回收的页块若能与伙伴块合并,插入上一级的area中,则视合并块为之前已被占用,然后根据该area中其伙伴块的状态(已被回收或者被占用)判断其map位是1(其伙伴块已被回收)还是0(其伙伴块被占用),再让map位跟1异或一下,结果为0则再合并,结果为1则不再合并。map的第几位(下标)判断依据:页块的序号>>(1+order)

    另一个例子(位图的使用):假设我们的系统内存只有16个页面RAM。因为RAM只有16个页面,我们只需用四个级别(orders)的伙伴位图(因为最大连续内存大小为16个页面),如下图所示。(2^4=16)


    初始位图:

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

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

    分配过程

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

    1、初始空闲链表为:

    order(0): 5, 10  (空闲块为什么不是5、8、9、10、12、13、14、15)

    order(1): 8 [8,9]   (空闲块为什么不是8[8,9]、12[12,13]、14[14,15])

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

    order(3): 无空闲块

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

    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 >> (1 + 0)

    = 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位)(10>>(1+1))。

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

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

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

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

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

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


    Buddy算法的优缺点:

    伙伴算法的一大优势是它能够完全避免外部碎片的产生,申请时,伙伴算法会给程序分配一个较大的内存空间,即保证所有大块内存都能得到满足。很明显分配比需求还大的内存空间,会产生内部碎片。所以伙伴算法虽然能够完全避免外部碎片的产生,但这恰恰是以产生内部碎片为代价的。

     优点:

         较好的解决外部碎片问题

         当需要分配若干个内存页面时,用于DMA的内存页面必须连续,伙伴算法很好的满足了这个要求

         只要请求的块不超过512个页面(2K),内核就尽量分配连续的页面。

         针对大内存分配设计。

    缺点:

          1. 合并的要求太过严格,只能是满足伙伴关系的块才能合并,比如第1块和第2块就不能合并。

          2. 碎片问题:一个连续的内存中仅仅一个页面被占用,导致整块内存区都不具备合并的条件

          3. 浪费问题:伙伴算法只能分配2的幂次方内存区,当需要8K(2页)时,好说,当需要9K时,那就需要分配16K(4页)的内存空间,但是实际只用到9K空间,多余的7K空间就被浪费掉。

          4. 算法的效率问题: 伙伴算法拆分和合并涉及了比较多的计算还有链表和位图的操作,开销还是比较大的,如果每次2^n大小的伙伴块就会合并到2^(n+1)的链表队列中,那么2^n大小链表中的块就会因为合并操作而减少,但系统随后立即有可能又有对该大小块的需求,为此必须再从2^(n+1)大小的链表中拆分,这样的合并又立即拆分的过程是无效率的。

     Linux针对大内存的物理地址分配,采用伙伴算法,如果是针对小于一个page的内存,频繁的分配和释放,有更加适宜的解决方案,如slab和kmem_cache等


    展开全文
  • 内含伙伴系统、最坏、最佳三种分配方式的演示,有内存分配动态变化图。
  • 在动态分区管理方式下采用不同的分配算法实现主存分配和实现主存回收。 三、实验要求 (1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时,根据作业需要的主存量查看是否有足够的空闲...

    一、实验目的

    通过本实验帮助学生理解在动态分区管理方式下应怎样实现主存空间的分配和回收。

    二、实验内容

    在动态分区管理方式下采用不同的分配算法实现主存分配和实现主存回收。

    三、实验要求

    (1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时,根据作业需要的主存量查看是否有足够的空闲空间,若有,则按需要量分割一个分区分配给该作业;若无,则作业不能装入。随着作业的装入、撤离、主存空间被分成许多个分区,有的分区被作业占用,而有的分区是空闲的。例如:

    在这里插入图片描述

    为了说明哪些区是空闲的,可以用来装入新作业,必须要有一张空区说明表,格式如下:

    在这里插入图片描述

    其中
    起址——指出一个空闲区的主存起始地址
    长度——指出从起始地址开始的一个连续空闲区的长度
    状态——有两种状态,一种是“未分配”状态,指出对应的由起址指出的某个长度的区域是空闲区;另一种是“空表目”状态,表示表中对应的登记项目是空白(无效),可用来登记新的空闲区(例如,作业撤离后,它所占的区域就成了空闲区,应找一个“空表目”栏登记归还区的起址和长度且修改状态)。
    由于分区的个数不定,所以空闲区说明表中应有适量的状态为“空表目”的登记栏目,否则造成表格“溢出”无法登记。

    上述的这张说明表的登记情况是按提示(1)中的例所装入的三个作业占用的主存区域后填写的

    (2)当有一个新作业要求装入主存时,必须查空闲区说明表,从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量,这时应把原来的空闲区变成两部分:一个部分分给作业占用;另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的“碎片”,在作业请求装入时,尽可能地利用主存的低地址部分的空闲区,而尽量保存高地址部分有较大的连续空闲区域,以利于大型作业的装入。为此,在空闲区说明表中,把每个空闲区按其地址顺序登记,即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”,总是让“空表目”栏集中在表格的后部。

    (3)采用首次适应算法或循环首次算法或最佳适应算法分配主存空间。由于本实验是模拟主存的分配,所以当把主存区分配给作业后并不实际启动装入程序装入作业,而用输出“分配情况”来代替。(即输出当时的空闲区说明表及其内存分配表)

    (4)当一个作业执行结束撤离时,作业所占的区域应该归还,归还的区域如果与其它空闲区相邻,则应合成一个较大的空闲区,登记在空闲区说明表中。例如,在提示(1)中列举的情况下,如果作业2撤离,归还所占主存区域时,应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。

    (5)请分别按首次适应算法、循环首次算法和最佳适应算法设计主存分配和回收的程序。然后按(1)中假设主存中已装入三个作业,且形成两个空闲区,确定空闲说明表的初值。现有一个需要主存量为6K的作业4 申请装入主存;然后作业3 撤离;再作业2 撤离。请你为它们进行主存分配和回收,把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。

    四、代码实现

    MemoryAllocation.cpp

    #include <iostream>
    #include <Windows.h>
    #include <fstream>
    #include <string>
    #include <queue>
    using namespace std;
    int MemorySize = 0;
    int OSSize = 0;
    int Memory[1000] = { 0 };
    
    struct Struct1{
     	int begin;
    	int length;
    	string state;//值为未分配或者空条目
    }; 
    queue<Struct1> WORK;//作业集合
    queue<Struct1> EMPTY;//空区集合
    
    //更新EMPTY队列,空区集合
    void UpdateEMP(){
    	while (!EMPTY.empty()) {
    		EMPTY.pop();
    	}
    
    	for (int i = 0; i < MemorySize; i++) {
    		if (Memory[i] == 0) {
    			for (int j = i + 1; j < MemorySize; j++) {
    				if (Memory[j] == 1 || j == MemorySize - 1) {
    					Struct1 emp1;
    					emp1.begin = i;
    					if (j == MemorySize - 1) {
    						emp1.length = j - i + 1;
    					}
    					else {
    						emp1.length = j - i;
    					}
    					emp1.state = "未分配";
    					EMPTY.push(emp1);
    					i = j;
    					break;
    				}
    			}
    		}
    	}
    	cout << "现有的空区说明表为:" << endl;
    	int s = EMPTY.size();
    	cout << s << "块空区" << endl;
    	for (int i = 0; i < s; i++) {
    		Struct1 emp1;
    		emp1 = EMPTY.front();
    		EMPTY.push(emp1);
    		EMPTY.pop();
    		cout  << " 起始:" << emp1.begin << " 长度:" << emp1.length << " 状态:" << emp1.state << endl;
    	}
    }
    
    //首次适应算法(FF)
    void FF(int applyNum) {
    	if (EMPTY.empty()) {
    		cout << "没有足够的主存空间!!" << endl;
    		exit(0);
    	}
    	bool flag = false;
    	while (!EMPTY.empty()) {
    		Struct1 emp1 = EMPTY.front();
    		if (emp1.length > applyNum) {
    			for (int i = emp1.begin; i< applyNum + emp1.begin ;i++) {
    				Memory[i] = 1;
    			}
    			Struct1 work3;
    			work3.begin = emp1.begin;
    			work3.length = applyNum;
    			work3.state = "作业4";
    			WORK.push(work3);
    			UpdateEMP();
    			flag = true;
    			break;
    		}
    		EMPTY.pop();
    
    	}
    	if (!flag) {
    		cout << "没有足够的主存空间!!" << endl;
    		exit(0);
    	}
    	Sleep(2000);
    	//作业三撤离
    	for (int i = 0; i < WORK.size(); i++) {
    		Struct1 work1;
    		work1 = WORK.front();
    		if (work1.state == "作业3") {
    			for (int i = work1.begin; i < work1.begin+ work1.length;i++) {
    				Memory[i] = 0;
    			}
    			WORK.pop();
    			cout << endl << "作业三撤离!" << endl;
    			UpdateEMP();
    			break;
    		}
    		else {
    			WORK.pop();
    			WORK.push(work1);
    		}
    	}
    	Sleep(2000);
    	//作业二撤离
    	for (int i = 0; i < WORK.size(); i++) {
    		Struct1 work1;
    		work1 = WORK.front();
    		if (work1.state == "作业2") {
    			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
    				Memory[i] = 0;
    			}
    			WORK.pop();
    			cout << endl << "作业二撤离!" << endl;
    			UpdateEMP();
    			break;
    		}
    		else {
    			WORK.pop();
    			WORK.push(work1);
    		}
    	}
    
    }
    
    //循环首次适应算法(NF)
    void NF(int applyNum) {
    	if (EMPTY.empty()) {
    		cout << "没有足够的主存空间!!" << endl;
    		exit(0);
    	}
    	bool flag = false;
    	while (!EMPTY.empty()) {
    		Struct1 emp1 = EMPTY.front();
    		if (emp1.length > applyNum) {
    			for (int i = emp1.begin; i < applyNum + emp1.begin; i++) {
    				Memory[i] = 1;
    			}
    			Struct1 work3;
    			work3.begin = emp1.begin;
    			work3.length = applyNum;
    			work3.state = "作业4";
    			WORK.push(work3);
    			UpdateEMP();
    			flag = true;
    			break;
    		}
    		EMPTY.pop();
    
    	}
    	if (!flag) {
    		cout << "没有足够的主存空间!!" << endl;
    		exit(0);
    	}
    	Sleep(2000);
    	//作业三撤离
    	for (int i = 0; i < WORK.size(); i++) {
    		Struct1 work1;
    		work1 = WORK.front();
    		if (work1.state == "作业3") {
    			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
    				Memory[i] = 0;
    			}
    			WORK.pop();
    			cout << endl << "作业三撤离!" << endl;
    			UpdateEMP();
    			break;
    		}
    		else {
    			WORK.pop();
    			WORK.push(work1);
    		}
    	}
    	Sleep(2000);
    	//作业二撤离
    	for (int i = 0; i < WORK.size(); i++) {
    		Struct1 work1;
    		work1 = WORK.front();
    		if (work1.state == "作业2") {
    			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
    				Memory[i] = 0;
    			}
    			WORK.pop();
    			cout << endl << "作业二撤离!" << endl;
    			UpdateEMP();
    			break;
    		}
    		else {
    			WORK.pop();
    			WORK.push(work1);
    		}
    	}
    }
    
    //最佳适应算法(BF)
    void BF(int applyNum) {
    	if (EMPTY.empty()) {
    		cout << "没有足够的主存空间!!" << endl;
    		exit(0);
    	}
    	bool flag = false;
    	int col = 10000000;//记录每一个空区与请求大小的差值
    	string e = "";
    	int em = EMPTY.size()*2;
    	for (int i = 0; i < em; i++) {
    		Struct1 emp1 = EMPTY.front();
    		if (emp1.length > applyNum) {
    			if (col == (emp1.length - applyNum) && e==emp1.state) {
    				for (int i = emp1.begin; i < applyNum + emp1.begin; i++) {
    					Memory[i] = 1;
    				}
    				Struct1 work3;
    				work3.begin = emp1.begin;
    				work3.length = applyNum;
    				work3.state = "作业4";
    				WORK.push(work3);
    				UpdateEMP();
    				flag = true;
    				break;
    			}
    			if (col > (emp1.length - applyNum)) {
    				col = (emp1.length - applyNum);
    				e = emp1.state;
    			}
    		}
    		EMPTY.pop();
    		EMPTY.push(emp1);
    	}
    	if (!flag) {
    		cout << "没有足够的主存空间!!" << endl;
    		exit(0);
    	}
    	Sleep(2000);
    	//作业三撤离
    	for (int i = 0; i < WORK.size(); i++) {
    		Struct1 work1;
    		work1 = WORK.front();
    		if (work1.state == "作业3") {
    			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
    				Memory[i] = 0;
    			}
    			WORK.pop();
    			cout << endl << "作业三撤离!" << endl;
    			UpdateEMP();
    			break;
    		}
    		else {
    			WORK.pop();
    			WORK.push(work1);
    		}
    	}
    	Sleep(2000);
    	//作业二撤离
    	for (int i = 0; i < WORK.size(); i++) {
    		Struct1 work1;
    		work1 = WORK.front();
    		if (work1.state == "作业2") {
    			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
    				Memory[i] = 0;
    			}
    			WORK.pop();
    			cout << endl << "作业二撤离!" << endl;
    			UpdateEMP();
    			break;
    		}
    		else {
    			WORK.pop();
    			WORK.push(work1);
    		}
    	}
    }
    
    //主函数
    int main() {
    	//打印提示信息
    	cout << "************************************************\n";
    	cout << "        操作系统实验内存分配算法\n";
    	cout << "        作者:CSDN Carmelo_7 主页: https://blog.csdn.net/Carmelo_7?spm=1000.2115.3001.5343 \n";
    	cout << "************************************************\n";
    	ifstream inFile;
    	inFile.open("MemoryAllocation.dat");
    	if (!inFile.is_open())
    		cout << "文件打开时候出错!!" << endl;
    	inFile >> MemorySize >> OSSize;
    	cout << "请输入主存的现有状态" << endl;
    	cout << "正在读取数据文件..." << endl;
    	Sleep(2000);
    	//打印空闲区说明表的初始状态
    	cout << "主存总大小:" << MemorySize << endl <<"操作系统占用空间:" << OSSize <<endl;
    	for (int i = 0;i<OSSize; i++) {
    		Memory[i] = 1;
    	}
    	int n = 0;
    	while (!inFile.eof()) {
    		n++;
    		Struct1 work1;
    		inFile >> work1.begin >> work1.length;
    		work1.state = "作业"+to_string(n);
    		WORK.push(work1);
    	}
    	int s = WORK.size();
    	for (int i = 0; i < s; i++) {
    		Struct1 work2;
    		work2 = WORK.front();
    		WORK.push(work2);
    		WORK.pop();
    		cout << work2.state << " 起始:" << work2.begin << " 长度:" << work2.length << endl;
    		for (int i = work2.begin; i < work2.length + work2.begin; i++) {
    			Memory[i] = 1;
    		}
    	}
    	/*for (int i : Memory) {
    		cout << i;
    	}*/
    
    	UpdateEMP();
    
    	cout << "请输入新的作业的申请主存数量:" << endl;
    	//打印作业4的申请量
    	int applyNum = 0;
    	cin >> applyNum;
    	cout << "作业" << n << "申请了"<< applyNum <<"主存空间" << endl;
    
    	cout << "===================================================================================" << endl;
    	cout << "1.首次适应算法(FF) :将所有空闲分区按照地址递增的次序链接,在申请内存分配时,从链首开始查找,将满足需求的第一个空闲分区分配给作业。" << endl;
    	cout << "2.循环首次适应算法(NF):将所有空闲分区按照地址递增的次序链接,在申请内存分配时,总是从上次找到的空闲分区的下一个空闲分区开始查找,将满足需求的第一个空闲分区分配给作业" << endl;
    	cout << "3.最佳适应算法(BF) : 将所有空闲分区按照从小到大的顺序形成空闲分区链,在申请内存分配时,总是把满足需求的、最小的空闲分区分配给作业。" << endl;
    	cout << "===================================================================================" << endl;
    	cout << "请输入对应的序号选择算法:" << endl;
    	int choose = 0;
    	cin >> choose;
    	switch (choose)	{
    		case 1:
    			FF(applyNum);
    			break;
    		case 2:
    			NF(applyNum);
    			break;
    		case 3:
    			BF(applyNum);
    			break;
    		default:
    			cout << "你输入的序号有误!!!" << endl;
    			exit(0);
    			break;
    	}
    
    
    }
    

    MemoryAllocation.dat

    128 5
    5 5
    26 6
    10 4
    

    五、测试样例

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • linux中的伙伴算法

    2021-07-25 16:15:57
    避免外部碎片的方法有两种:一种是之前介绍过的利用非连续内存分配;另外一种则是用一种有效的方法来监视内存,保证在内核只要申请一小块内存的情况下,不会从大块的连续空闲内存中截取一段过来,从而保证了大块...

    伙伴系统

    1.前言

    Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下,避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题,采用slab解决内部碎片的问题,在这里我们先讨论外部碎片问题。避免外部碎片的方法有两种:一种是之前介绍过的利用非连续内存的分配;另外一种则是用一种有效的方法来监视内存,保证在内核只要申请一小块内存的情况下,不会从大块的连续空闲内存中截取一段过来,从而保证了大块内存的连续性和完整性。显然,前者不能成为解决问题的普遍方法,一来用来映射非连续内存线性地址空间有限,二来每次映射都要改写内核的页表,进而就要刷新TLB,这使得分配的速度大打折扣,这对于要频繁申请内存的内核显然是无法忍受的。因此Linux采用后者来解决外部碎片的问题,也就是著名的伙伴系统。

    2.伙伴系统

    伙伴算法的分配原理

    大小相同,物理地址连续的两个两个页框就被称为伙伴。Linux的伙伴算法把所有的空闲页面分成多个块链表(链表个数默认为11个),每个链表中的一个块含有2的幂次个页面,即页块或简称块。每个链表中的页块的大小是不一样的。如果分配阶为n的页框块,那么先从第n条页框块链表中查找是否存在这么大小的空闲页块。如果有则分配,否则在第n+1条链表中继续查找,直到找到为止。
    伙伴系统的宗旨就是用最小的内存块来满足内核的对于内存的请求。在最初,只有一个块,也就是整个内存,假如为1M大小,而允许的最小块为64K,那么当我们申请一块200K大小的内存时,就要先将1M的块分裂成两等分,各为512K,这两分之间的关系就称为伙伴,然后再将第一个512K的内存块分裂成两等分,各位256K,将第一个256K的内存块分配给内存,这样就是一个分配的过程。

    img

    3.数据结构

    zone

    struct zone 定义在 inlcude/linux/mmzone.h

    struct zone {
    	/* Fields commonly accessed by the page allocator */
    
    /* zone watermarks, access with *_wmark_pages(zone) macros */
    unsigned long watermark[NR_WMARK];
    
     /*
    
      * 每个 zone 在系统启动时会计算出 3 个水位值, 分别为 WMAKR_MIN, WMARK_LOW, WMARK_HIGH 水位, 这在
        * 页面分配器和 kswapd 页面回收中会用到
          */
          /*
         * When free pages are below this point, additional steps are taken
         * when reading the number of free pages to avoid per-cpu counter
         * drift allowing watermarks to be breached
           */
           unsigned long percpu_drift_mark;
    
    /*
    
     * We don't know if the memory that we're going to allocate will be freeable
     * or/and it will be released eventually, so to avoid totally wasting several
     * GB of ram we must reserve some of the lower zone memory (otherwise we risk
     * to run OOM on the lower zones despite there's tons of freeable ram
     * on the higher zones). This array is recalculated at runtime if the
     * sysctl_lowmem_reserve_ratio sysctl changes.
       */
       unsigned long		lowmem_reserve[MAX_NR_ZONES];
    
     //zone 中预留的内存, 为了防止一些代码必须运行在低地址区域,所以事先保留一些低地址区域的内存
    
    #ifdef CONFIG_NUMA
    	int node;
    	/*
    
      * zone reclaim becomes active if more unmapped pages exist.
        */
        unsigned long		min_unmapped_pages;
        unsigned long		min_slab_pages;
        #endif
        struct per_cpu_pageset __percpu *pageset;
          /*
         * page管理的数据结构对象,内部有一个page的列表(list)来管理。每个CPU维护一个page list,避免
         * 自旋锁的冲突。这个数组的大小和NR_CPUS(CPU的数量)有关,这个值是编译的时候确定的
           */
           /*
         * free areas of different sizes
           */
           spinlock_t		lock;
            //对zone并发访问的保护的自旋锁
           int                     all_unreclaimable; /* All pages pinned */
           #ifdef CONFIG_MEMORY_HOTPLUG
           /* see spanned/present_pages for more description */
           seqlock_t		span_seqlock;
           #endif
           struct free_area	free_area[MAX_ORDER];
            //页面使用状态的信息,以每个bit标识对应的page是否可以分配
    
    #ifndef CONFIG_SPARSEMEM
    	/*
    
      * Flags for a pageblock_nr_pages block. See pageblock-flags.h.
        * In SPARSEMEM, this map is stored in struct mem_section
          */
          unsigned long		*pageblock_flags;
          #endif /* CONFIG_SPARSEMEM */
    
    #ifdef CONFIG_COMPACTION
    	/*
    
      * On compaction failure, 1<<compact_defer_shift compactions
        * are skipped before trying again. The number attempted since
         * last failure is tracked with compact_considered.
           */
           unsigned int		compact_considered;
           unsigned int		compact_defer_shift;
           #endif
    
    ZONE_PADDING(_pad1_)
    
    /* Fields commonly accessed by the page reclaim scanner */
    spinlock_t		lru_lock;	
    
     //LRU(最近最少使用算法)的自旋锁
    	struct zone_lru {
    		struct list_head list;
    	} lru[NR_LRU_LISTS];
    
    struct zone_reclaim_stat reclaim_stat;
    
    unsigned long		pages_scanned;	   /* since last reclaim */
    unsigned long		flags;		   /* zone flags, see below */
    
    /* Zone statistics */
    atomic_long_t		vm_stat[NR_VM_ZONE_STAT_ITEMS];
    
    //zone 计数
    	/*
    
      * The target ratio of ACTIVE_ANON to INACTIVE_ANON pages on
        * this zone's LRU.  Maintained by the pageout code.
          */
          unsigned int inactive_ratio;
    
    ZONE_PADDING(_pad2_)
    /* Rarely used or read-mostly fields */
    
    /*
    
     * wait_table		-- the array holding the hash table
     * wait_table_hash_nr_entries	-- the size of the hash table array
     * wait_table_bits	-- wait_table_size == (1 << wait_table_bits)
       *
     * The purpose of all these is to keep track of the people
     * waiting for a page to become available and make them
     * runnable again when possible. The trouble is that this
     * consumes a lot of space, especially when so few things
     * wait on pages at a given time. So instead of using
     * per-page waitqueues, we use a waitqueue hash table.
       *
     * The bucket discipline is to sleep on the same queue when
     * colliding and wake all in that wait queue when removing.
     * When something wakes, it must check to be sure its page is
     * truly available, a la thundering herd. The cost of a
     * collision is great, but given the expected load of the
     * table, they should be so rare as to be outweighed by the
     * benefits from the saved space.
       *
     * __wait_on_page_locked() and unlock_page() in mm/filemap.c, are the
     * primary users of these fields, and in mm/page_alloc.c
     * free_area_init_core() performs the initialization of them.
       */
       wait_queue_head_t	* wait_table;
    
     //待一个page释放的等待队列哈希表。它会被wait_on_page(),unlock_page()函数使用. 用
     //哈希表,而不用一个等待队列的原因,防止进程长期等待资源
    	unsigned long		wait_table_hash_nr_entries;
     //哈希表中的等待队列的数量
    	unsigned long		wait_table_bits;
    
    /*
    
     * Discontig memory support fields.
       */
       struct pglist_data	*zone_pgdat;
    
     //指向这个zone所在的pglist_data对象
    	/* zone_start_pfn == zone_start_paddr >> PAGE_SHIFT */
    	unsigned long		zone_start_pfn;
    //和node_start_pfn的含义一样。这个成员是用于表示zone中的开始那个page在物理内存中的位置
    //的present_pages, spanned_pages: 和node中的类似的成员含义一样
    	/*
    
      * zone_start_pfn, spanned_pages and present_pages are all
        * protected by span_seqlock.  It is a seqlock because it has
         * to be read outside of zone->lock, and it is done in the main
         * allocator path.  But, it is written quite infrequently.
           *
         * The lock is declared along with zone->lock because it is
         * frequently read in proximity to zone->lock.  It's good to
         * give them a chance of being in the same cacheline.
           */
           unsigned long		spanned_pages;	/* total size, including holes */
            //zone 中包含的页面数量
           unsigned long		present_pages;	/* amount of memory (excluding holes) */
           //zone 中实际管理的页面数量. 对一些体系结构来说, 其值和 spanned_pages 相等
           /*
         * rarely used fields:
           */
           const char		*name;
            //
           }
    

    每个物理页框对应一个struct page实例(页框的描述数据结构)。每个内存区关联了一个struct zone实例,该结构中使用free_area数组对空闲页框进行管理。

    free_area

    struct free_area {
    	struct list_head	free_list[MIGRATE_TYPES];
     //free_area共有MAX_ORDER个元素,其中第order个元素记录了2^order的空闲块,这些
     //空闲块在free_list中以双向链表的形式组织起来,对于同等大小的空闲块,其类型不同,将组织在不同的free_list中
    	unsigned long		nr_free;
     //nr_free记录了该free_area中总共的空闲内存块的数量
    };
    

    free_area共有MAX_ORDER个元素,其中第order个元素记录了2order的空闲块,这些空闲块在free_list中以双向链表的形式组织起来,对于同等大小的空闲块,其类型不同,将组织在不同的free_list中,nr_free记录了该free_area中总共的空闲内存块的数量。MAX_ORDER的默认值为11,这意味着最大内存块的大小为210=1024个页框。对于同等大小的内存块,每个内存块的起始页框用于链表的节点进行相连,这些节点对应的着struct page中的lru域。

    migrate type

    内核对于迁移类型的定义如下:

    #define MIGRATE_UNMOVABLE     0//不可移动页,这类页在内存当中有固定的位置,不能移动。内核的核心分配的内存大多属于这种类型
    #define MIGRATE_RECLAIMABLE   1//可回收页,这类页不能直接移动,但可以删除,其内容页可以从其他地方重新生成,例如,映射自文件的数据属于这种类型,针对这种页,内核有专门的页面回收处理
    #define MIGRATE_MOVABLE       2//可移动页,这类页可以随意移动,用户空间应用程序所用到的页属于该类别。它们通过页表来映射,如果他们复制到新的位置,页表项也会相应的更新,应用程序不会注意到任何改变。
    #define MIGRATE_PCPTYPES      3//用来表示每CPU页框高速缓存的数据结构中的链表的迁移类型数目 
    #define MIGRATE_RESERVE       3//在前三种的列表中都没用可满足分配的内存块时,就可以从MIGRATE_RESERVE分配
    #define MIGRATE_ISOLATE       4 //用于跨越NUMA节点移动物理内存页,在大型系统上,它有益于将物理内存页移动到接近于是用该页最频繁地CPU
    #define MIGRATE_TYPES         5//表示迁移类型的数目
    

    定义migrate type,简要来说就是Linux将可移动或不可移动的内存分开分配,以便最大程度的减少碎片,提升分配大块内存的能力。基于这种思路,可见上述5种migrate type最重要的就是MIGRATE_UNMOVABLE不可移动,MIGRATE_MOVABLE可移动。另一个重要的type就是MIGRATE_RESERVE,这表示page被reserve,不接受buddy system管理。

    __rmqueue_smallest

    rmqueue_smallest()是在指定的内存区上从所请求的分配阶对应的链表开始查找所需大小的空闲块,如果不成功则从高一阶的链表上继续查找。

    static inline
    struct page *rmqueue_smallest(struct zone *zone, unsigned int order,
                            int migratetype)
    {
        unsigned int current_order;
        struct free_area * area;
        //指向空闲页框
        struct page *page;
        //指向页
    
    /* Find a page of the appropriate size in the preferred list */
    //遍历order链表,current_order 当前阶,MAX_ORDER最大阶
    for (current_order = order; current_order < MAX_ORDER; ++current_order) {
        area = &(zone->free_area[current_order]);
        if (list_empty(&area->free_list[migratetype]))
        //使用list_empty()检测,migratetype类型的链表为空时获取该页框
            continue;
    
    ​    page = list_entry(area->free_list[migratetype].next,struct page, lru);//从当前页链表项的下一项开始,获取指向的节点的struct page结构体的首地址list_del(&page->lru);//从链表上删除rmv_page_order(page);//设置页框描述符中的private为0,该字段中本来保存的是其所处页框块的分配阶
    ​    area->nr_free--;//更新当前area的nr_free数expand(zone, page, order, current_order, area, migratetype);//调用expand分裂return page;//循环条件已经不再满足,因此返回前4个页框块首页框的描述符地址page。
    }
    return NULL;
    
    }
    

    expand

    expand()为分裂函数,如果所得到的内存块大于所请求的内存块,则按照伙伴算法的分配原理,将大的页框块分裂成小的页框块。

    static inline void expand(struct zone *zone, struct page *page,
        int low, int high, struct free_area *area,
        int migratetype)
        //比如当前申请大小为4的页块。low表示当前申请页块的阶2,如果阶为2的链表没有空闲块,就一
        //直往上找,直到找到阶为4找到空闲块,则high为4。
    {
        unsigned long size = 1 << high;
        //因为只需要4个,阶为4有16个,所以多余的要往阶为2和3的链表上放
        //左移1位
        while (high > low) {
            area--;
            //通过将area指针自减即可得到下级链表
            high--;
            size >>= 1;
            //接上面的假设,刚才size=16,现在往右移一位size=8,
            VM_BUG_ON(bad_range(zone, &page[size]));
            list_add(&page[size].lru, &area->free_list[migratetype]);
            //list_add函数将这个8个页框添加到area为3的链表中
            area->nr_free++;
            //更新area为3的nr_free数
            set_page_order(&page[size], high);
            //经过第一次遍历将16一份为2,第二次遍历将8个页块一份为2,第三次时循环条件已不满足,则返回前4个页框块首页框的描述符地址page。
        }
        
    }
    
    
    

    4.总结

    伙伴算法作为一种行之有效的内存碎片解决办法,和slab一起用来解决内存浪费问题。这套内存管理方法也被很多操作系统所采用,将内存分成若干块,然后尽可能以最适合的方式满足程序内存需求就是伙伴算法的核心。

    参考资料:

    https://blog.csdn.net/vanbreaker/article/details/7605367

    展开全文
  • 分区分配算法:  首次适应算法(First Fit):从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给 作业,这种方法的目的在于减少查找时间。为适应这种算法,空闲分区表(空闲区链)中的空闲...
  • 操作系统内存分配算法

    千次阅读 2019-08-22 16:12:47
    位图算法 概念: 这种位图即二维数组,通过二维数组来保存内存的使用情况,每个位的值代表...概念: 这种分配算法通过链表来保存和维护块的使用信息,它包括多个单元,每个单元是一个连续的数组,数组的第一位用来表...
  • #include #include #include #include //双向链表 struct list_head { ...//拉链法存储空闲内存 typedef struct free_area { struct list_head free_list; //把空闲内存块链接到空闲链表 uns
  • 1.前言: PooledByteBufAllocator 实现相当复杂,其中涉及许多复杂的数据结构类: 1)PoolArena ...其核心思想是利用了为 FreeBSD 设计的 jemalloc 内存分配算法和 buddy 分配算法。为了更好地解...
  • 内存分配算法(FF、BF、MF)

    万次阅读 多人点赞 2019-05-09 17:58:48
    在实现动态分区分配时,将涉及到分区分配中所用到的数据结构、分区分配算法和分区的分配与回收操作三方面的问题。 我的理解是,动态分区分配是按照作业需要的主存空间大小来分配的,当要装入一个作业时,根据作业...
  • 算法已获得满绩 (1)空闲页面分为10个块组,块组编号为0,1,2,……,8,9; (2)内存空间及其划分(界面): 内存物理空间大小可选择:256M bytes,512M bytes; 每个页框的大小可选择:1K bytes,2K bytes,4K bytes...
  • 内存管理之伙伴算法

    2019-09-16 19:27:17
    算法作用 它要解决的问题是频繁地请求和释放不同大小的... 伙伴算法(Buddy system)把所有的空闲页框分为11个块链表,每块链表中分布包含特定的连续页框地址空间,比如第0个块链表包含大小为2^0个连续的页框,第...
  • 内存分配算法

    2019-11-26 20:09:51
    首次适配算法,存储管理器沿着段链表进行搜索,找到第一个足够大的空闲块,将一部分分配给进程使用,另一部分作为空闲块,等待下一次分配。 首次适配尽可能减少搜索链表节点。对首次适配进行很小的修改就能得到下次...
  • 内存管理伙伴算法

    2013-12-25 11:07:27
    内存管理伙伴算法
  • DMA(Direct Memory Access,直接内存存取)、常规、高端内存这3个区域都采用buddy算法进行管理,把空闲的页以2的n次方为单位进行管理,因此Linux最底层的内存申请都是以2n 为单位的。Buddy算法最主要的的特点任何...
  • 文章目录目录内存分配算法物理内存分配内存碎片伙伴(Buddy)分配算法申请和回收反碎片机制Slab 算法slab 分配器的结构slab 高速缓存分区页框分配器非连续内存内存的分配虚拟内存的分配内核空间内存分配...
  • 目录 内存管理中的分区分配方法(1) ...伙伴系统是一个内存分配与管理算法,该算法管理的内存以2的幂次增长。假设内存大小是2,假设需求S大小的内存。 If 2<S<=2: 分配全部内存 Else: 递归二等分切分块,...
  • 作业及分区已分配情况可以在程序中定义或由用户输入,用户根据打印的菜单选择采用哪种算法为队首作业分配内存空间,也可以打印当前内存分配情况,用户也可以输出要回收的作业的内存空间,其菜单如下:
  • Linux内存分配与回收——伙伴算法

    千次阅读 2020-04-15 22:11:17
    在Linux系统中,内存分配与回收速率直接影响系统的存取...在进行内存分配时,该算法通过不断平分较大的空闲内存块来获得较小的空闲内存块,直到获得所需要的内存块;在进行内存回收时,该算法尽可能地合并空闲块。
  • 操作系统实验四:内存分配算法

    千次阅读 2020-12-25 22:27:55
    实验四:内存分配算法 ——动态分区方式主存的分配和回收 本机操作系统:macOS Big Sur 一、前言 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器,而且要能合理地分配和使用这些存储...
  • 内部碎片是已经被分配出去(能明确指出属于哪个进程)的内存空间,却不能被利用的内存空间.(就是已经被分配出去的内存空间大于请求所需的内存空间,而导致有些内存自己不使用,别的也不能使用) 外部碎片是指还...
  • 1.前言本文所述关于内存管理...本文将主要以X86架构为例来介绍伙伴算法和slab分配2.伙伴算法概述块链表Linux的伙伴算法将所有的空闲页面分成MAX_ORDER+1(MAX_ORDER默认大小为11)个块链表每个链表中的一个节点指向一...
  • 本文主要介绍内存的基本概念以及操作系统的内存管理算法内存的基本概念 内存是计算机系统中除了处理器以外最重要的资源,用于存储当前正在执行的程序和数据。内存是相对于CPU来说的,CPU可以直接寻址的存储...
  • 但是slab分配器并没有脱离伙伴算法,而是基于伙伴算法分配的大内存进一步细分成小内存分配。 我们先来看一张图: kmem_cache是cache_chain上的一个元素,kmem_cache描述了一个高速缓存,每个高速缓存包含了一个slabs...
  • 精品文档 课程设计报告 设计题目 内存的连续分配算法 班级 : 学号 姓名 指导老师 设计时间 摘要 精品文档 精品文档 1主要算法包括 固定分区分配动态分区分配伙伴算法可重定位分区分配 2 内容要求 1定义与算法相关的...
  • 课程设计报告 设计题目内存的连续分配算法 班级 : 学号 姓名 指导老师 设计时间 2012年8月 1 摘要 1主要算法包括 固定分区分配动态分区分配伙伴算法可重定位分区分配 2内容要求 1定义与算法相关的数据结构如PCB空闲...
  • OS-Memory-Allocation-Algorithms-Simulation:此存储库中包含的两个程序模拟了Buddy系统,First Fit,Next Fit,Best Fit和Worst Fit内存分配算法,这些算法在许多操作系统中使用。 树数据结构用于伙伴系统的实现,...
  • 内存分配-----伙伴算法和slab算法

    万次阅读 2014-01-02 09:39:03
    内存碎片是指当回收一块内存时,一般将内存直接放入free链表中,由于内存分配越小,内存块就会特别多而且特别小,当需要一块大的内存块的时候无法找到.原因就在于回收内存的时候,不能把相邻两块可用内存合并. 解决...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,375
精华内容 6,550
关键字:

内存伙伴分配算法