精华内容
下载资源
问答
  • 为了便于内存的分配和释放,AWorks提供了两种内存管理工具:堆和内存池。 本文为《面向AWorks框架和接口的编程(上)》第三部分软件篇——第9章内存管理——第1~2小节:堆管理器和内存池。 本章导...

    在程序运行过程中,可能产生一些数据,例如,串口接收的数据,ADC采集的数据。若需将数据存储在内存中,以便进一步运算、处理,则应为其分配合适的内存空间,数据处理完毕后,再释放相应的内存空间。为了便于内存的分配和释放,AWorks提供了两种内存管理工具:堆和内存池。

    本文为《面向AWorks框架和接口的编程(上)》第三部分软件篇——第9章内存管理——第1~2小节:堆管理器和内存池。

    本章导读

    在计算机系统中,数据一般存放在内存中,只有当数据需要参与运算时,才从内存中取出,交由CPU运算,运算结束再将结果存回内存中。这就需要系统为各类数据分配合适的内存空间。

    一些数据需要的内存大小在编译前可以确定。主要有两类:一类是全局变量或静态变量,这部分数据在程序的整个生命周期均有效,在编译时就为这些数据分配了固定的内存空间,后续直接使用即可,无需额外的管理;一类是局部变量,这部分数据仅在当前作用域中有效(如函数中),它们需要的内存自动从栈中分配,也无需额外的管理,但需要注意的是,由于这一部分数据的内存从栈中分配,因此,需要确保应用程序有足够的栈空间,尽量避免定义内存占用较大的局部变量(比如:一个占用数K内存的数组),以避免栈溢出,栈溢出可能破坏系统关键数据,极有可能造成系统崩溃。

    一些数据需要的内存大小需要在程序运行过程中根据实际情况确定,并不能在编译前确定。例如,可能临时需要1K内存空间用于存储远端通过串口发过来的数据。这就要求系统具有对内存空间进行动态管理的能力,在用户需要一段内存空间时,向系统申请,系统选择一段合适的内存空间分配给用户,用户使用完毕后,再释放回系统,以便系统将该段内存空间回收再利用。在AWorks中,提供了两种常见的内存管理方法:堆和内存池。

    9.1  堆管理器

    堆管理器用于管理一段连续的内存空间,可以在满足系统资源的情况下,根据用户的需求分配任意大小的内存块,完全“按需分配”,当用户不再使用分配的内存块时,又可以将内存块释放回堆中供其它应用分配使用。类似于C标准库中的malloc()/free()函数实现的功能。

    9.1.1  堆管理器的原理概述

    在使用堆管理器前,首先通过一个示例对其原理作简要的介绍,以便用户更加有效的使用堆管理器。例如,使用堆管理器对1024字节的内存空间进行管理。初始时,所有内存均处于空闲状态,可以将整个内存空间看作一个大的空闲内存块。示意图详见图9.1。

    图9.1 初始状态——单个空闲内存块

    内存分配的策略是:当用户申请一定大小的内存空间时,堆管理器会从第一个空闲内存块开始查找,直到找到一个满足用户需求的空闲内存块(即容量不小于用户请求的内存空间大小),然后从该空闲内存块中分配出用户指定大小的内存空间。

    例如,用户向该堆管理器申请100字节的内存空间,由于第一个空闲内存块的容量为1024,满足需求,因此,可以从中分配100字节的内存空间给该用户,分配后的内存示意图详见图9.2。

    图9.2 分配100字节——分割为两个内存块

    注:填充为阴影表示该块已被分配,否则,表示该块未被分配,处于空闲状态,数字表示该块的容量。

    同理,若用户再向该堆管理器连续请求三次内存空间,每次请求的内存空间容量分别为:150、250、200字节,则分配后的内存示意图详见图9.3。

    图9.3 再分配100、300、200字节内存空间——分割为五个内存块

    随着分配的继续,内存块可能越来越多。若用户的请求无法满足,则会分配失败,如果在图9.3的基础上,用户再请求400字节内存空间,由于仅有的一个空闲块,且容量为324字节,无法满足需求,此时,分配会失败,用户无法得到一段有效的内存空间。

    当用户申请的某一段内存不再使用时,应该将该内存块释放回堆中,以便回收再利用。

    回收的策略是:当用户将某一内存块释放回堆中时,首先,将该内存块变为空闲块,若该内存块相邻的内存块也为空闲块,则将它们合并为一个大的空闲内存块。

    例如,在图9.3的基础上,释放之前分配的250字节内存空间,则首先将该内存块变为空闲块,示意图详见图9.4。

    图9.4 释放一个内存块——相邻块不为空闲块

    由于该内存块前后均不为空闲块,因此,无需作合并操作。此时,释放了250字节的空闲空间,堆中共存在574字节的内存空间。但是,若用户此时向该堆管理器申请400字节的内存空间,由于第一个空闲块和第二个空闲块均不满足需求,因此,内存分配还是会失败。

    这里暴露出了一个堆管理器的缺点。频繁的分配和释放大小不一的内存块,将产生诸多内存碎片,即图9.4中被已分配内存块打断的空闲内存块,图中容量为250字节和容量为324字节的空闲内存块被一个已分配的容量为200字节的内存块打断,使得各个空闲块在物理上不连续,无法形成一个大的空闲块。这种情况下,即使请求的内存空间大小小于当前堆的空闲空间总大小,也可能会由于没有一个大的空闲块而分配失败。

    在图9.4的基础上,即使再释放掉第一次分配的100字节内存空间,使总空闲空间达到674字节,详见图9.5,同样无法满足一个400字节内存空间的分配请求。

    图9.5 释放容量为100字节内存块

    随着系统中大量内存块的分配和回收,内存碎片将越来越多,一些长时间不被释放的内存块,将始终分割着一些空闲内存块,造成内存碎片。这也告知用户,当不再使用某一内存块时,应尽快释放掉该内存块,以避免造成过多的内存碎片。

    在图9.5中,有3个空闲块,若用户在此基础上再请求一个280字节的内存空间,根据分配策略,堆管理器首先查看第一个空闲块,其容量为100字节,无法满足需求,接着查看第二个空闲块,其容量为250字节,同样无法满足需求,接着查看第三个空闲块,其容量为324字节,最终从该块中分配一段空间给用户,分配后的内存示意图详见图9.6。

    图9.6 再分配280字节内存空间

    在图9.6的基础上,若用户再释放200字节的内存块,首先,将其变为空闲块,示意图详见图9.7。

    图9.7 释放200字节的内存空间(1)——标记为空闲

    由于其左侧大小为250的内存块同样为空闲块,因此,需要将它们合并为一个大的内存块,即合并为一个大小为450的内存块,示意图详见图9.8。

    图9.8 释放200字节的内存空间(2)——与相邻空闲块合并

    此时,由于存在一个大小为450的空闲块,因此,若此时用户申请400字节的内存空间,则可以申请成功。与图9.5对比可知,虽然图9.5共计有674字节的空闲空间,而图9.8只有594字节的空闲空间,但图9.8却可以满足一个大小为400字节的内存空间请求。由此可见,受内存碎片的影响,总的空闲空间大小并不能决定一个内存请求的成功与否。

    申请400字节成功后的示意图详见图9.9。

    图9.9 再分配400字节内存空间

    在图9.9的基础上,若用户再释放280字节的内存块,同样,首先将其变为空闲块,示意图详见图9.10。

    图9.10 释放280字节的内存空间(1)——标记为空闲

    由于其左右两侧均为空闲块,因此,需要将它们合并为一个大的内存块,即合并为一个大小为374的内存块,示意图详见图9.11。

    图9.11 释放280字节的内存空间(2)——与相邻空闲块合并

    之所以要将相邻的空闲内存块合并,主要是为了避免内存块越来越多,越来越零散,如此下去,将很难再有一个大的空闲块,用户后续再申请大的内存空闲时,将无法满足需求。

    通过上面一系列内存分配和释放的示例,展示了堆管理器分配和释放内存的策略,使得用户对相关的原理有了一定的了解。

    实际上,在堆管理器的软件实现中,为了便于管理,各个内存块是以链表的形式组织起来的,每个内存块的首部会固定存放一些用于内存块管理的相关信息,示意图详见图9.12。

    图9.12 内存块(含空闲内存块和已分配内存块)链表

    图中展示了4个非常重要的信息:magic、used、p_next、p_prev。

    magic被称为魔数,会被赋值为一个特殊的固定值,它表示了该内存块是堆管理器管理的内存块,可以在一定程度上检查错误的内存操作。例如,若这个区域被改写,magic的值被修改为了其它值,表明存在非法的内存操作,可能是用户内存操作越界等,应及时处理;在释放一个内存块时,堆管理器会检查magic的值,若其值不为特殊的固定值,表明这并不是堆管理器分配的内存块,该释放操作是非法的。

    used用于表示该内存块是否已经被使用。若其值为0,则表示该内存块是空闲块;若其值为1,则表示该内存块已经被分配,不是空闲块。

    p_next和p_prev用于将各个内存块使用双向链表的形式组织起来,以便可以方便的找到当前内存块的下一个或上一个内存块,例如,在释放一个内存块时,需要查看相邻的内存块(上一个内存块和下一个内存块)是否为空闲块,以决定是否将它们合并为一个空闲块。

    此外,为了在分配内存块时,加快搜索空闲块的效率,信息中还会额外另外两个指针,用于将所有空闲块单独组织为一个双向链表。这样,在分配一个内存块时,只需要在空闲链表中查找满足需求的空闲块即可,无需依次遍历所有的内存块。示意图详见图9.13。

    图9.13 空间块链表

    对于用户来讲,其获得的内存空间为用户数据空间(获得的是直接指向用户数据空间的指针),存放在内存块首部的信息对用户是不可见的,用户不应该尝试访问、修改这些信息。

    需要用户注意的是,由于内存块的相关信息需要占用一定的内存空间(在32位系统中,通常为24字节),因此,每个内存块占用的实际大小会大于用户请求的内存空间大小,例如,用户请求一个100字节的内存空间,实际中,为了存储内存块的相关信息,会分配一个大小为124字节的内存块。基于此,用户实际可以使用的内存空间要略小于堆的总空间。

    9.1.2  堆管理器接口

    AWorks提供了堆管理器,用户通过相关接口使用即可。相关函数的原型详见表9.1。

    表9.1 堆管理器接口(aw_memheap.h)

    1.  定义堆管理器实例

    在使用堆管理器前,必须先使用aw_memheap_t类型定义堆管理器实例,该类型在aw_memheap.h中定义,具体类型的定义用户无需关心,仅需使用该类型定义堆管理器实例即可,即:

    其地址即可作为初始化接口中memheap参数的实参传递。

    在AWorks中,一个堆管理器用于管理一段连续的内存空间,一个系统中,可以使用多个堆管理器分别管理多段连续的内存空间。这就需要定义多个堆管理器实例,例如:

    如此一来,各个应用可以定义自己的堆管理器,以管理该应用中的内存分配与释放,使得各个应用之间的内存使用互不影响。

    如果所有应用使用一个堆,那么各个应用之间的内存分配将相互影响,某一应用出现内存泄漏,随着时间的推移,极有可能造成一个堆的空间被完全泄漏,这将影响所有应用程序。同时,所有应用共用一个堆,也造成在一个堆中的分配与释放更加频繁,分配的内存块大小更加不一致,更容易产生内存碎片。

    2.  初始化堆管理器

    定义堆管理器实例后,必须使用该接口初始化后才能使用,以指定其管理的内存空间,其函数原型为:

    其中,memheap为指向堆管理器实例的指针;name为堆管理器的名字,名字为一个字符串,仅用作标识;start_addr指定了其管理的内存空间首地址;size指定了其管理的内存空间大小(字节数)。

    函数的返回值为标准的错误号,返回AW_OK时,表示初始化成功;否则,表示初始化失败。

    初始化函数的核心在于指定其管理的内存空间,通常情况下,这段连续的内存空间可以通过定义一个全局的数组变量获得,其大小与实际应用相关,应根据实际情况决定。例如,使用堆管理器管理1KB的内存空间,则初始化堆管理器的范例程序详见程序清单9.1。

    程序清单9.1 初始化堆管理器范例程序

    程序中,定义了一个大小为1024字节的数组,用于分配一个1KB的内存空间,以便使用堆管理器进行管理。

    3.  分配内存

    堆管理器初始化完毕后,可以使用该接口为用户分配指定大小的内存块,内存块的大小可以是满足资源需求的任意大小。分配内存块的函数原型为:

    其中,heap为指向堆管理器的指针;size为内存块大小。返回值为分配内存块的首地址,特别地,若返回值为NULL,则表明分配失败。

    在分配内存块时,由于堆管理器并不知道分配的内存块用来存储何种类型的数据,因此,返回值为通用的无类型指针,即void *类型,代表其指向了某一类型不确定的地址。显然,分配的内存块用以存储何种类型的数据是由用户决定的,因此,用户在使用这段内存空间时,必须将其转换为实际数据类型的指针。

    例如,分配用以存储100个无符号8位数据的内存块,其范例程序详见程序清单9.2。

    程序清单9.2 分配内存块的范例程序

    程序中,将aw_memheap_alloc()的返回值强制转换为了指向uint8_t数据类型的指针。注意,使用aw_memheap_alloc()分配的内存中,数据的初始值是随机的,不一定为0。因此,若不对ptr指向的内存赋值,则其值可能是任意的。

    4.  重新调整内存大小

    有时候,需要动态调整之前分配的内存块大小,如果一开始分配了一个较小的内存块,但随着数据的增加,内存不够,此时,就可以使用该函数重新调整之前分配的内存块大小。其函数原型为:

    其中,heap为指向堆管理器的指针;ptr为使用aw_memheap_alloc()函数分配的内存块首地址,即调用aw_memheap_alloc()函数的返回值;new_size为调整后的内存块大小。返回值为调整大小后的内存空间首地址,特别地,若返回值为NULL,则表明调整大小失败。

    newsize指定的新的大小可以比原内存块大(扩大),也可以比原内存块小(缩小)。如果是扩大内存块,则新扩展部分的内存不会被初始化,值是随机的,但原内存块中的数据仍然保持不变。如果是缩小内存块,则超出new_size部分的内存会被释放,其中的数据被丢弃,其余数据保持不变。特别地,若newsize的值为0,则相当于不再使用ptr指向的内存块,此时,将会直接释放整个内存块,这种情况下,返回值同样为NULL。

    函数返回值与ptr的值可能不同,即系统可能重新选择一块合适的内存块来满足调整大小的需求,此时,内存首地址将发生变化。例如,当新的大小比原空间大时,系统先判断原内存块后是否还有足够的连续空间满足本次扩大内存的要求,如果有,则直接扩大内存空间,内存首地址不变,同样返回原内存块的首地址,即ptr的值;如果没有,则重新按照newsize分配一个内存块,并将原有数据原封不动的拷贝到新分配的内存块中,而后自动释放原有的内存块,原内存块将不再可用,此时,返回值将是重新分配的内存块首地址,与ptr将无直接关系。

    例如,首先使用aw_memheap_alloc()分配了一个100字节大小的内存块,然后重新将其调整为200字节大小的内存块。范例程序详见程序清单9.3。

    程序清单9.3 重新调整内存大小

    值得注意的是,重新调整内存空间的大小失败后,原内存空间还是有效的。因此,若采用程序清单9.3第9行的调用形式,若内存扩大失败,则返回值为NULL,这将会导致ptr的值被设置为NULL。此时,虽然原内存空间仍然有效,但由于指向该内存空间的指针信息丢失了,用户无法再访问到对应的内存空间,也无法释放对应的内存空间,造成内存泄漏。

    在实际使用时,为了避免调整内存大小失败时将原ptr的值覆盖为NULL,应该使用一个新的指针保存函数的返回值,详见程序清单9.4。

    程序清单9.4 重新调整内存大小(使用新的指针保存函数返回值)

    此时,即使扩大内存空间失败,指向原内存空间的指针ptr依然有效,依旧可以使用原先分配的内存空间,避免了内存泄漏。扩大内存空间成功时,则直接将ptr的值重新赋值为new_ptr,使其指向扩展完成后的内存空间。

    5.  释放内存

    当用户不再使用申请的内存块时,必须释放,否则将造成内存泄漏。释放内存的函数原型为:

    其中,ptr为使用aw_memheap_alloc()或aw_memheap_realloc()函数分配的内存块首地址,即调用这些函数的返回值。注意,ptr只能是上述几个函数的返回值,不能是其它地址值,例如,不能将数组首地址作为函数参数,以释放静态数组占用的内存空间。传入错误的地址值,极有可能导致系统崩溃。

    当使用aw_memheap_free()将内存块释放后,相应的内存块将变为无效,用户不能再继续使用。释放内存块的范例程序详见程序清单9.5。

    程序清单9.5 释放内存块的范例程序

    为了避免释放内存块后再继续使用,可以养成一个良好的习惯,每当内存释放后,都将相应的ptr指针赋值为NULL。

    9.1.3  系统堆管理

    在AWorks中,整个内存空间首先用于满足存放一些已知占用内存空间大小的数据,比如:全局变量、静态变量、栈空间、程序代码或常量等。

    全局变量和静态变量都比较好理解,其占用的内存大小通过数据的类型即可确定。需要注意的是,在介绍堆管理器时,定义一块待管理的内存空间同样使用了静态数组的方式,详见程序清单9.1的第6行:

    这也属于一种静态变量,其占用的内存大小是已知的。

    对于栈空间,在AWorks中,栈空间是静态分配的,类似于一个静态数组,其占用的内存空间大小由用户决定,同样是已知的。

    通常情况下,程序代码和常量都存储在ROM或FLASH等只读存储器中,不会放在内存中。但在部分平台中,出于效率或芯片架构的考虑,也可能将程序代码和常量存储在内存中。例如,在i.MX28x平台中,程序代码和常量也存储在DDR内存中。程序代码和常量占用的内存空间大小在编译后即可确定,占用的内存空间大小也是已知的。

    在满足这些数据的存储后,剩下的所有内存空间即作为系统堆空间,便于用户在程序运行过程中动态使用。

    为了便于用户使用,需要使用某种合适的方法管理系统堆空间。在AWorks中,默认使用前文介绍的堆管理器对其进行管理。出于系统的可扩展性考虑,AWorks并没有限制必须基于AWorks提供的堆管理器管理系统堆空间,如果用户有更加适合特殊应用场合的管理方法,也可以在特定环境下使用自有方法管理系统堆空间。为了保持应用程序的统一,AWorks定义了一套动态内存管理通用接口,便于用户使用系统堆空间,而无需关心具体的管理方法。相关函数原型详见表9.2。

    表9.2 动态内存管理接口(aw_mem.h)

    通过前文的介绍可知,在使用堆管理器前,需要定义堆管理器实例,然后初始化该实例,以指定其管理的内存空间,初始化完成后,用户才可向其请求内存。若是使用堆管理器管理系统堆空间(默认),那么,表9.2中的接口均可基于堆管理器接口实现。此时,系统中将定义一个默认的堆管理器实例,并在系统启动时自动完成其初始化操作,指定其管理的内存空间为系统堆空间。如此一来,系统启动后,用户可以直接向系统中默认的堆管理器申请内存块。例如,aw_mem_alloc()用于分配一个内存块,其直接基于堆管理器实现,范例程序详见程序清单9.6。

    程序清单9.6 aw_mem_alloc()函数实现范例

    其中,__g_system_heap为系统定义的堆管理器实例,已在系统启动时完成了初始化。程序清单9.6只是aw_mem_alloc()函数实现的一个简单范例,实际中,用户可以根据具体情况,使用最为合适的方法管理系统堆空间,实现AWorks定义的动态内存管理通用接口。

    下面,详细介绍各个接口的含义及使用方法。

    1.  分配内存

    aw_mem_alloc()用于从系统堆中分配指定大小的内存块,用法和C标准库中的malloc()相同,其函数原型为:

    参数size指定内存空间的大小,单位为字节。返回值为void *类型的指针,其指向分配内存块的首地址,特别地,若返回值为NULL,则表示分配失败。

    例如,申请用以存储一个int类型数据的存储空间,范例程序详见程序清单9.7。

    程序清单9.7 申请内存范例程序

    程序中,将aw_mem_alloc()的返回值强制转换为了指向int数据类型的指针。注意,使用aw_mem_alloc()分配的内存中,数据的初始值是随机的,不一定为0。因此,若不对ptr指向的内存赋值,则其值将是任意的。

    2.  分配多个指定大小的内存块

    除使用aw_mem_alloc()直接分配一个指定大小的内存块外,还可以使用aw_mem_calloc()分配多个连续的内存块,用法与C标准库中的calloc()相同,其函数原型为:

    该函数用于分配nelem个大小为size的内存块,分配的内存空间总大小为:nelem×size,实际上相当于分配一个容量为nelem×size的大内存块,返回值同样为分配内存块的首地址。与aw_mem_alloc()不同的是,该函数分配的内存块会被初始化为0。例如,分配用以存储10个int类型数据的内存,则范例程序详见程序清单9.8。

    程序清单9.8 分配10个用于存储int类型数据的内存块

    由于分配的内存空间会被初始化为0,因此,即使不对ptr指向的内存赋值,其值也是确定的0。

    3.  分配具有一定对齐要求的内存块

    有时候,用户申请的内存块可能用来存储具有特殊对齐要求的数据,要求分配内存块的首地址必须按照指定的字节数对齐。此时,可以使用aw_mem_align()分配一个满足指定对齐要求的内存块。其函数原型为:

    其中,size为分配的内存块大小,align表示对齐要求,其值是2的整数次幂,比如:2、4、8、16、32、64等。返回值同样为分配内存块的首地址,其值满足对齐要求,是align的整数倍。如align的值为16,则按照16字节对齐,分配内存块的首地址将是16的整数倍,地址的低4位全为0。程序范例详见程序清单9.9。

    程序清单9.9 分配具有一定对齐要求的内存块范例程序

    程序中,将分配的地址通过aw_kprintf()打印输出,以查看地址的具体值,实际运行可以发现,地址值是满足16字节对齐的。注意,该函数与aw_mem_alloc()分配的内存块一样,其中的数据初始值是随机的,不一定为0。

    在堆管理器中,并没有类似的分配满足一定对齐要求的内存块接口,只有普通的分配内存块接口:aw_memheap_alloc()。其分配的内存块,可能是对齐的,也可能是未对齐的。为了使返回给用户的内存块能够满足对齐要求,在使用aw_memheap_alloc()分配内存块时,可以多分配align - 1字节的空间,此时,即使获得的内存块首地址不满足对齐要求,也可以返回从内存块首地址开始,顺序第一个对齐的地址给用户,以满足用户的对齐需求。

    例如,要分配200字节的内存块,并要求满足8字节对齐,则首先使用aw_memheap_alloc()分配207字节(200 + 8 - 1)的内存块,假定得到的内存块地址范围为:3 ~ 209,示意图详见图9.14(a)。由于首地址3不是8的整数倍,因此其不是按8字节对齐的,此时,直接返回顺序第一个对齐的地址给用户,即:8。由于用户需要的是200字节的内存块,因此,对于用户来讲,其使用的内存块地址范围为 :8 ~ 207,显然,其在实际使用aw_memheap_alloc()获得的内存块地址范围内,用户获得的内存块是完全有效的,示意图详见图9.14(b)。

    图9.14 内存对齐的处理——多分配align-1字节的空间

    为什么要多分配align - 1字节的空间呢?在获得的实际内存块不满足对齐需求时,表明内存块首地址不是align的整数倍,即其对align取余数的结果(C语言的%运算符)不为0,假定其对align取余数的结果为N(N ≥1),则只要将首地址加上align-N,得到的地址值就是align的整数倍。该值也为从首地址开始,顺序第一个对齐的地址。由于在首地址不对齐时,必然有:N ≥1,因此:align - N ≤ align – 1,即顺序第一个对齐的地址相对于起始地址的偏移不会超过align - 1。基于此,只要在分配内存块时多分配align-1字节的空间,那么就可以在向用户返回一个对齐地址的同时,依旧满足用户请求的内存块容量需求。

    若不多分配align-1字节的内存空间,例如,只使用aw_memheap_alloc()分配200字节的内存块,得到的内存块地址范围为:3 ~ 203,示意图详见图9.15(a)。此时,若同样返回顺序第一个对齐的地址给用户,即:8。由于用户需要的是200字节的内存块,因此,对于用户来讲,其使用的内存块地址范围为 :8 ~ 208,显然,204 ~ 208 这段空间并不是通过分配得到的有效内存,使得用户得到了一段非法的内存空间,一旦访问,极有可能导致应用出错。示意图详见图9.15 (b)。

    图9.15 内存对齐的处理——未多分配align-1字节的空间

    实际中,由于align - 1的值往往是一些比较特殊的奇数值,例如:3、7、15、31等,经常如此分配容易把内存块的首地址打乱,出现很多非对齐的地址。因此,往往会直接多分配align字节的内存空间。

    同时,出于效率考虑,在AWorks中,每次分配的内存往往都按照默认的CPU自然对齐字节数对齐,例如,在32位系统中,默认分配的所有内存都按照4字节对齐,基于此,aw_mem_alloc()函数的实现可以更新为如程序清单9.10所示的程序。 

    程序清单9.10 aw_mem_alloc()函数分配的内存按照4字节对齐

    4.  重新调整内存大小

    有时候,需要动态调整分配内存块的大小,如果一开始分配了一个较小的内存块,但随着数据的增加,内存不够,此时,则可以使用该函数重新调整之前分配的内存块大小。其函数原型为:

    其中,ptr为使用aw_mem_alloc()、aw_mem_calloc()或aw_mem_align()函数分配的内存块首地址,即调用这些函数的返回值。new_size为调整后的大小。返回值为调整大小后的内存块首地址,特别地,若调整大小失败,则返回值为NULL。

    例如,首先使用aw_mem_alloc()分配了存储1个int类型数据的内存块,然后重新调整内存块的大小,使其可以存储2个int类型的数据。范例程序详见程序清单9.11。

    程序清单9.11 内存分配范例程序(重新调整内存大小)

    5.  释放内存

    前面讲解了4种分配内存块的方法,无论使用何种方式动态分配的内存块,在使用结束后,都必须释放,否则将造成内存泄漏。释放内存块的函数原型为:

    其中,ptr为使用aw_mem_alloc()、aw_mem_calloc()、aw_mem_align()或aw_mem_realloc()函数分配的内存块首地址,即调用这些函数的返回值。

    当使用aw_mem_free()将内存块释放后,相应的地址空间将变为无效,用户不能再继续使用。释放内存块的范例程序详见程序清单9.12。

    程序清单9.12 释放内存块的范例程序

    9.2  内存池

    堆管理器极为灵活,可以分配任意大小的内存块,非常方便。但其也存在明显的缺点:一是分配效率不高,在每次分配时,都要依次查找所有空闲内存块,直到找到一个满足需求的空闲内存块;二是容易产生大小各异的内存碎片。

    为了提高内存分配的效率,以及避免内存碎片,AWorks提供了另外一种内存管理方法:内存池(Memory Pool)。其舍弃了堆管理器中可以分配任意大小的内存块这一优点,将每次分配的内存块大小设定为固定值。

    由于每次分配的内存块大小为固定值,没有空间大小的限制,因此,在用户每次申请内存块时,分配其第一个空闲内存块即可,无需任何查找过程,同理,在释放一个内存块时,也仅需将其标志为空闲即可,无需任何额外的合并操作,这极大的提高了内存分配和释放的效率。

    同时,由于每次申请和释放的内存块都是同样的大小,只要存在空闲块,就可以分配成功,某几个空闲内存块不可能由于被某一已分配的内存块分割而导致无法使用。这种情况下,任一空闲块都可以被没有限制的分配使用,不再存在任何内存碎片,彻底避免了内存碎片。 

    但是,将内存块大小固定,会限制其使用的灵活性,并可能造成不必要的内存空间浪费,例如,用户只需要很小的一块内存空间,但若内存池中每一块内存都很大,这就会使内存分配时不得不分配出一块很大的内存,造成了内存浪费。这就要求在定义内存池时,应尽可能将内存池中内存块的大小定义为一个合理的值,避免过多的内存浪费。

    系统中可以存在多个内存池,每个内存池包含固定个数和大小的内存块。基于此,在实际应用中,为了满足不同大小的内存块需求,可以定义多种尺寸(内存池中内存块的大小)的内存池(比如:小、中、大三种),然后在实际应用中根据实际用量选择从合适的内存池中分配内存块,这样可以在一定程度上减少内存的浪费。

    9.2.1  内存池原理概述

    内存池用于管理一段连续的内存空间,由于各个内存块的大小固定,因此,首先将内存空间分为若干个大小相同的内存块,例如,管理1024字节的内存空间,每块大小为128字节。则共计可以分为8个内存块。初始时,所有内存块均为空闲块,示意图详见图9.16。

    图9.16 初始状态——8个空闲块

    在AWorks中,为便于管理,将各个空闲内存块使用单向链表的形式组织起来,示意图详见图9.17。

    图9.17 以单向链表的形式组织各个空闲块

    这就要求一个空闲块能够存放一个p_next指针,以便组织链表。在32位系统中,指针的大小为4个字节,因此,要求各个空闲块的大小不能低于4个字节。此外,出于对齐考虑,各个空闲块的大小必须为自然对齐字节数的正整数倍。例如,在32位系统中,块大小应该为4字节的整数倍,比如:4、8、12、6……而不能为5、7、9、13等。

    基于此,当需要分配一个内存块时,只需从链表中的取出第一个空闲块即可。例如,需要在图9.17的基础上分配一个内存块,可以直接从链表中取出第一个空闲块,示意图详见图9.18。

    图9.18 从链表中取出一个内存块

    此时,空闲块链表中,将只剩下7个空闲块,示意图详见图9.19。

    图9.19 剩余7个空闲块

    值得注意的是,虽然在空闲块链表中,各个内存块中存放了一个p_next指针,占用了一定的内存空间,但是,当该内存块从空闲链表中取出,分配给用户使用时,已分配的内存块并不需要组织为一个链表,p_next的值也就没有任何意义了,因此,用户可以使用内存块中所有的内存,不存在用户不可访问的区域,不会造成额外的空间浪费。

    而在堆管理器中,无论是空闲块还是已分配的内存块,头部存储的相关信息都必须保持有效,其占用的内存空间用户是不能使用的,对于用户来讲,这相当于造成了一定的内存空间浪费。

    当用户不再使用一个内存块时,需要释放相应的内存块,释放时,直接将内存块重新加入空闲块链表即可。示意图详见图9.20。

    图9.20 释放一个内存块

    释放后,空闲链表中将新增一个内存块,示意图详见图9.21。

    图9.21 释放后,新增一个内存块

    由此可见,整个内存池的分配和释放操作都非常简单。分配时,从空闲链表中取出一个内存块,释放时,将内存块重新加入空闲链表中。

    9.2.2  内存池接口

    AWorks提供了内存池软件库,用户通过相关接口使用即可。相关函数的原型详见表9.3。

    表9.3 内存池接口(aw_pool.h)

    1.  定义内存池实例

    在使用内存池前,必须先使用aw_pool_t类型定义内存池实例,该类型在aw_pool.h中定义,具体类型的定义用户无需关心,仅需使用该类型定义内存池实例即可,即:

    其地址即可作为初始化接口中p_pool参数的实参传递。

    一个内存池可以管理一段连续的内存空间,在AWorks中,可以使用多个内存池,以分别管理多段连续的内存空间。此时,就需要定义多个内存池实例,例如:

    为了满足各种大小的内存块需求,可以定义多个具有不同内存块大小的内存池。例如:定义小、中、大三种尺寸的内存池,它们对应的内存块大小分别为8、64、128。用户根据实际用量选择从合适的内存池中分配内存块,以在一定程度上减少内存的浪费。

    2.  初始化内存池

    定义内存池实例后,必须使用该接口初始化后才能使用,以指定内存池管理的内存空间,以及内存池中各个内存块的大小。其函数原型为:

    其中,p_pool指向待初始化的内存池,即使用aw_pool_t类型定义的内存池实例;p_pool_mem为该内存池管理的实际内存空间首地址;pool_size指定整个内存空间的大小;item_size指定内存池中每个内存块的大小。

    函数的返回值为内存池ID,其类型aw_pool_id_t,该类型的具体定义用户无需关心,该ID可作为其它功能接口的参数,用以表示需要操作的内存池。特别地,若返回ID的值为NULL,表明初始化失败。

    初始化时,系统会将pool_size大小的内存空间,分为多个大小为item_size的内存块进行管理。例如,使用内存池管理1KB的内存空间,每个内存块的大小为16字节,初始化范例程序详见程序清单9.13。

    程序清单9.13 初始化内存池

    程序中,将1024字节的空间分成了大小为16字节的内存块进行管理。注意,出于效率考虑,块大小并不能是任意值,只能为自然对齐字节数的正整数倍。例如,在32位系统中,块大小应该为4字节的整数倍,若不满足该条件,初始化时,将会自动向上修正为4字节的整数倍,例如,块大小的值设置为5,将被自动修正为8。用户可以通过aw_pool_item_size ()函数获得实际的内存块大小。

    3.  获取内存池中实际的块大小

    前面提到,初始化时,为了保证内存池的管理效率,可能会对用户传入的块大小进行适当的修正,用户可以通过该函数获取当前内存池中实际的块大小。其函数原型为:

    其中,pool_id为初始化函数返回的内存池ID,其用于指定要获取信息的内存池。返回值即为内存池中实际的块大小。

    例如,初始化时,将内存池的块大小设定为5,然后通过该函数获取内存池中实际的块大小。范例程序详见程序清单9.14。

    程序清单9.14 获取内存池中实际的块大小

    运行程序可以发现,实际内存块的大小为8。

    实际应用中,为了满足不同容量内存申请的需求,可以定义多个内存池,每个内存池定义不同的块大小。如定义3种块大小尺寸的内存池,分别为8字节(小)、64字节(中)、128字节(大)。范例程序详见程序清单9.15。

    程序清单9.15 定义多种不同块大小的内存池

    程序中,将三种类型内存池的总容量分别定义为了512、1024、2048。实际中,应根据情况定义,例如,小型内存块需求量很大,则应该增大对应内存池的总容量。

    4.  获取内存块

    内存池初始化完毕后,用户可以从内存池中获取固定大小内存块,其函数原型为:

    其中,pool_id为初始化函数返回的内存池ID,其用于指定内存池,表示从该内存池中获取内存块。返回值为void *类型的指针,其指向获取内存块的首地址,特别地,若返回值为NULL,则表明获取失败。从内存池中获取一个内存块的范例程序详见程序清单9.16。

    程序清单9.16 获取内存块范例程序

    5.  释放内存块

    当获取的内存块使用完毕后,应该释放该内存块,将其返还到内存池中。其函数原型为:

    其中,pool_id为初始化函数返回的内存池ID,其用于指定内存池,表示将内存块释放到该内存池中。p_item为使用aw_pool_item_get()函数获取内存块的首地址,即调用aw_pool_item_get()函数的返回值,表示要释放的内存块。

    返回值为aw_err_t类型的标准错误号,若值为AW_OK,表示释放成功,否则,表示释放失败,释放失败往往是由于参数错误造成的,例如,释放一个不是由aw_pool_item_get()函数获取的内存块。注意,内存块从哪个内存池中获取,释放时,就必须释放到相应的内存池中,不可将内存块释放到其它不对应的内存池中。

    当使用aw_pool_item_return()将内存块释放后,相应的内存空间将变为无效,用户不能再继续使用。释放内存块的范例程序详见程序清单9.17。

    程序清单9.17 释放内存块范例程序

                   </div>
                <!--<div class="side-box author-article">
                    <a href="/d/user/2671042/" target="_blank">
                            <h2 class="title">
                                周立功单片机
                                技术专区</h2>
                        </a>
                        
                    <ul class="txt-list">
                        <li><a href="/d/922003.html">E523.52—高集成度电机控制芯片</a></li><li><a href="/d/906380.html">智能门锁生命线!一“芯”当关,安全守护</a></li><li><a href="/d/905625.html">新一代车载T-Box集成以太网网关的控制方案解析</a></li><li><a href="/d/904695.html">电源模块的可靠性设计有何秘籍?</a></li><li><a href="/d/904646.html">ZLG72128数码管显示驱动及键盘扫描管理芯片</a></li>                    </ul>
                </div>-->
    
                <!-- 文章增加的调整 -->
                    <iframe id="iframe_tags" data-elecfans_trackid="article_detail" data-tag="内存,数据存储,管理器" src="/static/iframe/course.html" width="100%" height="170" style="border: none; margin: 20px 0px; display: none;"></iframe>
                    <div class="hudong clearfix">
                    </div>
                     <div class="wx_detail">
                                        <p>原文标题:AWorks软件篇 — 内存管理</p>
                                        <p>文章出处:【微信号:Zlgmcu7890,微信公众号:周立功单片机】欢迎添加关注!文章转载请注明出处。</p>
                                </div>
            </div>
    
    展开全文
  • Linux的内存管理主要分为两部分:物理地址到虚拟地址的映射,内核内存分配管理(主要基于slab)。 物理地址到虚拟地址之间的映射 1、概念  物理地址(physical address)  用于内存芯片级的单元寻址,...
    Linux的内存管理主要分为两部分:物理地址到虚拟地址的映射,内核内存分配管理(主要基于slab)。

    物理地址到虚拟地址之间的映射

    1、概念

      物理地址(physical address)

      用于内存芯片级的单元寻址,与处理器和CPU连接的地址总线相对应。——这个概念应该是这几个概念中最好理解的一个,但是值得一提的是,虽然可以直接把物理地址理解成插在机器上那根内存本身,把内存看成一个从0字节一直到最大空量逐字节的编号的大数组,然后把这个数组叫做物理地址,但是事实上,这只是一个硬件提供给软件的抽像,内存的寻址方式并不是这样。所以,说它是“与地址总线相对应”,是更贴切一些,不过抛开对物理内存寻址方式的考虑,直接 把物理地址与物理的内存一一对应,也是可以接受的。也许错误的理解更利于形而上的抽像。

      虚拟内存(virtual memory)

      这是对整个内存(不要与机器上插那条对上号)的抽像描述。它是相对于物理内存来讲的,可以直接理解成“不直实的”,“假的”内存,例如,一个0x08000000内存地址,它并不对就物理地址上那个大数组中0x08000000 - 1那个地址元素;

      之所以是这样,是因为现代操作系统都提供了一种内存管理的抽像,即虚拟内存(virtual memory)。进程使用虚拟内存中的地址,由操作系统协助相关硬件,把它“转换”成真正的物理地址。这个“转换”,是所有问题讨论的关键。有了这样的抽像,一个程序,就可以使用比真实物理地址大得多的地址空间。(拆东墙,补西墙,银行也是这样子做的),甚至多个进程可以使用相同的地址。不奇怪,因为转换 后的物理地址并非相同的。可以把连接后的程序反编译看一下,发现连接器已经为程序分配了一个地址,例如,要调用某个函数A,代码不是call A,而是call0x0811111111 ,也就是说,函数A的地址已经被定下来了。没有这样的“转换”,没有虚拟地址的概念,这样做是根本行不通的。

      打住了,这个问题再说下去,就收不住了。

      逻辑地址(logical address)

      Intel为了兼容,将远古时代的段式内存管理方式保留了下来。逻辑地址指的是机器语言指令中,用来指定一个操作数或者是一条指令的地址。以上例,我们说的连接器为A分配的0x08111111这个地址就是逻辑地址。——不过不好意思,这样说,好像又违背了Intel中段式管理中,对逻辑地址要求,“一个逻辑地址,是由一个段标识符加上一个指定段内相对地址的偏移量,表示为[段标识符:段内偏移量],也就是说,上例中那个0x08111111,应该表示为[A的代码段标识符: 0x08111111],这样,才完整一些”

      线性地址(linear address)或也叫虚拟地址(virtual address)

      跟逻辑地址类似,它也是一个不真实的地址,如果逻辑地址是对应的硬件平台段式管理转换前地址的话,那么线性地址则对应了硬件页式内存的转换前地址。

      CPU将一个虚拟内存空间中的地址转换为物理地址,需要进行两步:首先将给定一个逻辑地址(其实是段内偏移量,这个一定要理解!!!),CPU 要利用其段式内存管理单元,先将为个逻辑地址转换成一个线程地址,再利用其页式内存管理单元,转换为最终物理地址。这样做两次转换,的确是非常麻烦而且没有必要的,因为直接可以把线性地址抽像给进程。之所以这样冗余,Intel完全是为了兼容而已。

      2、CPU段式内存管理,逻辑地址如何转换为线性地址

      一个逻辑地址由两部份组成,段标识符: 段内偏移量。段标识符是由一个16位长的字段组成,称为段选择符。其中前13位是一个索引号。后面3位包含一些硬件细节,如图:
     
      最后两位涉及权限检查,本贴中不包含。

      索引号,或者直接理解成数组下标——那它总要对应一个数组吧,它又是什么东东的索引呢?这个东东就是“段描述符(segment descriptor)”,呵呵,段描述符具体地址描述了一个段(对于“段”这个字眼的理解,我是把它想像成,拿了一把刀,把虚拟内存,砍成若干的截—— 段)。这样,很多个段描述符,就组了一个数组,叫“段描述符表”,这样,可以通过段标识符的前13位,直接在段描述符表中找到一个具体的段描述符,这个描 述符就描述了一个段,我刚才对段的抽像不太准确,因为看看描述符里面究竟有什么东东——也就是它究竟是如何描述的,就理解段究竟有什么东东了,每一个段描 述符由8个字节组成,如下图:
     
      这些东东很复杂,虽然可以利用一个数据结构来定义它,不过,我这里只关心一样,就是Base字段,它描述了一个段的开始位置的线性地址。

      Intel设计的本意是,一些全局的段描述符,就放在“全局段描述符表(GDT)”中,一些局部的,例如每个进程自己的,就放在所谓的“局部段 描述符表(LDT)”中。那究竟什么时候该用GDT,什么时候该用LDT呢?这是由段选择符中的T1字段表示的,=0,表示用GDT,=1表示用LDT。

      GDT在内存中的地址和大小存放在CPU的gdtr控制寄存器中,而LDT则在ldtr寄存器中。好多概念,像绕口令一样。这张图看起来要直观些:
     
      首先,给定一个完整的逻辑地址[段选择符:段内偏移地址],

      1、看段选择符的T1=0还是1,知道当前要转换是GDT中的段,还是LDT中的段,再根据相应寄存器,得到其地址和大小。我们就有了一个数组了。

      2、拿出段选择符中前13位,可以在这个数组中,查找到对应的段描述符,这样,它了Base,即基地址就知道了。

      3、把Base + offset,就是要转换的线性地址了。

      还是挺简单的,对于软件来讲,原则上就需要把硬件转换所需的信息准备好,就可以让硬件来完成这个转换了。OK,来看看Linux怎么做的。

      3、Linux的段式管理

      Intel要求两次转换,这样虽说是兼容了,但是却是很冗余,呵呵,没办法,硬件要求这样做了,软件就只能照办,怎么着也得形式主义一样。

      另一方面,其它某些硬件平台,没有二次转换的概念,Linux也需要提供一个高层抽像,来提供一个统一的界面。所以,Linux的段式管理,事实上只是“哄骗”了一下硬件而已。按照Intel的本意,全局的用GDT,每个进程自己的用LDT——不过Linux则对所有的进程都使用了相同的段来对 指令和数据寻址。即用户数据段,用户代码段,对应的,内核中的是内核数据段和内核代码段。这样做没有什么奇怪的,本来就是走形式嘛,像我们写年终总结一样。
    include/asm-i386/segment.h

     

    #define GDT_ENTRY_DEFAULT_USER_CS        14
    #define __USER_CS (GDT_ENTRY_DEFAULT_USER_CS * 8 + 3)
    #define GDT_ENTRY_DEFAULT_USER_DS        15
    #define __USER_DS (GDT_ENTRY_DEFAULT_USER_DS * 8 + 3)
    #define GDT_ENTRY_KERNEL_BASE        12
    #define GDT_ENTRY_KERNEL_CS                (GDT_ENTRY_KERNEL_BASE + 0)
    #define __KERNEL_CS (GDT_ENTRY_KERNEL_CS * 8)
    #define GDT_ENTRY_KERNEL_DS                (GDT_ENTRY_KERNEL_BASE + 1)
    #define __KERNEL_DS (GDT_ENTRY_KERNEL_DS * 8)

     

    把其中的宏替换成数值,则为:

     

     

    #define __USER_CS 115       [00000000 1110  0  11]
    #define __USER_DS 123       [00000000 1111  0  11]
    #define __KERNEL_CS 96     [00000000 1100  0  00]
    #define __KERNEL_DS 104   [00000000 1101  0  00]

     

    方括号后是这四个段选择符的16位二制表示,它们的索引号和T1字段值也可以算出来了

     

     

    __USER_CS              index= 14   T1=0
    __USER_DS               index= 15   T1=0
    __KERNEL_CS           index=  12  T1=0
    __KERNEL_DS           index= 13   T1=0

     

    T1均为0,则表示都使用了GDT,再来看初始化GDT的内容中相应的12-15项(arch/i386/head.S):

     

            .quad0x00cf9a000000ffff        /* 0x60 kernel 4GBcode at 0x00000000 */
            .quad0x00cf92000000ffff        /* 0x68 kernel 4GBdata at 0x00000000 */
            .quad0x00cffa000000ffff        /* 0x73 user 4GBcode at 0x00000000 */
            .quad0x00cff2000000ffff        /* 0x7b user 4GBdata at 0x00000000 */

      按照前面段描述符表中的描述,可以把它们展开,发现其16-31位全为0,即四个段的基地址全为0。

      这样,给定一个段内偏移地址,按照前面转换公式,0 +段内偏移,转换为线性地址,可以得出重要的结论,“在Linux下,逻辑地址与线性地址总是一致(是一致,不是有些人说的相同)的,即逻辑地址的偏移量字段的值与线性地址的值总是相同的。!!!”

      忽略了太多的细节,例如段的权限检查。呵呵。Linux中,绝大部份进程并不例用LDT,除非使用Wine ,仿真Windows程序的时候。

      4.CPU的页式内存管理

      CPU的页式内存管理单元,负责把一个线性地址,最终翻译为一个物理地址。从管理和效率的角度出发,线性地址被分为以固定长度为单位的组,称为页(page),例如一个32位的机器,线性地址最大可为4G,可以用4KB为一个页来划分,这页,整个线性地址就被划分为一个 tatol_page[2^20]的大数组,共有2的20个次方个页。这个大数组我们称之为页目录。目录中的每一个目录项,就是一个地址——对应的页的地址。

      另一类“页”,我们称之为物理页,或者是页框、页桢的。是分页单元把所有的物理内存也划分为固定长度的管理单位,它的长度一般与内存页是一一对应的。这里注意到,这个total_page数组有2^20个成员,每个成员是一个地址(32位机,一个地址也就是4字节),那么要单单要表示这么一个数 组,就要占去4MB的内存空间。为了节省空间,引入了一个二级管理模式的机器来组织分页单元。文字描述太累,看图直观一些:
     
      如上图,

      1、分页单元中,页目录是唯一的,它的地址放在CPU的cr3寄存器中,是进行地址转换的开始点。万里长征就从此长始了。

      2、每一个活动的进程,因为都有其独立的对应的虚似内存(页目录也是唯一的),那么它也对应了一个独立的页目录地址。——运行一个进程,需要将它的页目录地址放到cr3寄存器中,将别个的保存下来。

      3、每一个32位的线性地址被划分为三部份,面目录索引(10位):页表索引(10位):偏移(12位)

      依据以下步骤进行转换:

      1、从cr3中取出进程的页目录地址(操作系统负责在调度进程的时候,把这个地址装入对应寄存器);

      2、根据线性地址前十位,在数组中,找到对应的索引项,因为引入了二级管理模式,页目录中的项,不再是页的地址,而是一个页表的地址。(又引入了一个数组),页的地址被放到页表中去了。

      3、根据线性地址的中间十位,在页表(也是数组)中找到页的起始地址;

      4、将页的起始地址与线性地址中最后12位相加,得到最终我们想要的葫芦;

      这个转换过程,应该说还是非常简单地。全部由硬件完成,虽然多了一道手续,但是节约了大量的内存,还是值得的。那么再简单地验证一下:

      1、这样的二级模式是否仍能够表示4G的地址;页目录共有:2^10项,也就是说有这么多个页表.每个目表对应了:2^10页;
    每个页中可寻址:2^12个字节。还是2^32 = 4GB

      2、这样的二级模式是否真的节约了空间;也就是算一下页目录项和页表项共占空间(2^10 *4 + 2 ^10 *4) = 8KB。哎,……怎么说呢!!!
    红色错误,标注一下,后文贴中有此讨论。。。。。。按<深入理解计算机系统>中的解释,二级模式空间的节约是从两个方面实现的:

      A、如果一级页表中的一个页表条目为空,那么那所指的二级页表就根本不会存在。这表现出一种巨大的潜在节约,因为对于一个典型的程序,4GB虚拟地址空间的大部份都会是未分配的;

      B、只有一级页表才需要总是在主存中。虚拟存储器系统可以在需要时创建,并页面调入或调出二级页表,这就减少了主存的压力。只有最经常使用的二级页表才需要缓存在主存中。——不过Linux并没有完全享受这种福利,它的页表目录和已分配页面相关的页表都是常驻内存的。值得一提的是,虽然页目录和页表中的项,都是4个字节,32位,但是它们都只用高20位,低12位屏蔽为0——把页表的低12屏蔽为0,是很好理解的,因为这样,它刚好和一个页面大 小对应起来,大家都成整数增加。计算起来就方便多了。但是,为什么同时也要把页目录低12位屏蔽掉呢?因为按同样的道理,只要屏蔽其低10位就可以了,不 过我想,因为12>10,这样,可以让页目录和页表使用相同的数据结构,方便。

      本贴只介绍一般性转换的原理,扩展分页、页的保护机制、PAE模式的分页这些麻烦点的东东就不啰嗦了……可以参考其它专业书籍。

      5.Linux的页式内存管理

      原理上来讲,Linux只需要为每个进程分配好所需数据结构,放到内存中,然后在调度进程的时候,切换寄存器cr3,剩下的就交给硬件来完成了 (呵呵,事实上要复杂得多,不过偶只分析最基本的流程)。前面说了i386的二级页管理架构,不过有些CPU,还有三级,甚至四级架构,Linux为了在 更高层次提供抽像,为每个CPU提供统一的界面。提供了一个四层页管理架构,来兼容这些二级、三级、四级管理架构的CPU。这四级分别为:

      页全局目录PGD(对应刚才的页目录)

      页上级目录PUD(新引进的)

      页中间目录PMD(也就新引进的)

      页表PT(对应刚才的页表)。

      整个转换依据硬件转换原理,只是多了二次数组的索引罢了,如下图:
     
      那么,对于使用二级管理架构32位的硬件,现在又是四级转换了,它们怎么能够协调地工作起来呢?嗯,来看这种情况下,怎么来划分线性地址吧!从硬件的角度,32位地址被分成了三部份——也就是说,不管理软件怎么做,最终落实到硬件,也只认识这三位老大。

      从软件的角度,由于多引入了两部份,,也就是说,共有五部份。——要让二层架构的硬件认识五部份也很容易,在地址划分的时候,将页上级目录和页 中间目录的长度设置为0就可以了。这样,操作系统见到的是五部份,硬件还是按它死板的三部份划分,也不会出错,也就是说大家共建了和谐计算机系统。

      这样,虽说是多此一举,但是考虑到64位地址,使用四层转换架构的CPU,我们就不再把中间两个设为0了,这样,软件与硬件再次和谐——抽像就是强大呀!!!

      例如,一个逻辑地址已经被转换成了线性地址,0x08147258,换成二制进,也就是:

      0000100000 0101000111 001001011000

      内核对这个地址进行划分,

      PGD = 0000100000
      PUD = 0
      PMD = 0
      PT = 0101000111
      offset = 001001011000

      现在来理解Linux针对硬件的花招,因为硬件根本看不到所谓PUD,PMD,所以,本质上要求PGD索引,直接就对应了PT的地址。而不是再 到PUD和PMD中去查数组(虽然它们两个在线性地址中,长度为0,2^0 =1,也就是说,它们都是有一个数组元素的数组),那么,内核如何合理安排地址呢?

      从软件的角度上来讲,因为它的项只有一个,32位,刚好可以存放与PGD中长度一样的地址指针。那么所谓先到PUD,到到PMD中做映射转换, 就变成了保持原值不变,一一转手就可以了。这样,就实现了“逻辑上指向一个PUD,再指向一个PDM,但在物理上是直接指向相应的PT的这个抽像,因为硬 件根本不知道有PUD、PMD这个东西”。然后交给硬件,硬件对这个地址进行划分,看到的是:

      页目录 = 0000100000

      PT = 0101000111

      offset = 001001011000

      嗯,先根据0000100000(32),在页目录数组中索引,找到其元素中的地址,取其高20位,找到页表的地址,页表的地址是由内核动态分配的,接着,再加一个offset,就是最终的物理地址了。



    内核内存分配管理

    内存管理方法应该实现以下两个功能:

    • 最小化管理内存所需的时间
    • 最大化用于一般应用的可用内存(最小化管理开销)

    1.直接堆分配

    每个内存管理器都使用了一种基于堆的分配策略。在这种方法中,大块内存(称为 )用来为用户定义的目的提供内存。当用户需要一块内存时,就请求给自己分配一定大小的内存。堆管理器会查看可用内存的情况(使用特定算法)并返回一块内存。搜索过程中使用的一些算法有first-fit(在堆中搜索到的第一个满足请求的内存块)和best-fit(使用堆中满足请求的最合适的内存块)。当用户使用完内存后,就将内存返回给堆。

    这种基于堆的分配策略的根本问题是碎片(fragmentation)。当内存块被分配后,它们会以不同的顺序在不同的时间返回。这样会在堆中留下一些洞,需要花一些时间才能有效地管理空闲内存。这种算法通常具有较高的内存使用效率(分配需要的内存),但是却需要花费更多时间来对堆进行管理。

    2.伙伴分配算法

    另外一种方法称为 buddy memory allocation,是一种更快的内存分配技术,它将内 存划分为 2 的幂次方个分区,并使用 best-fit 方法来分配内存请求。当用户释放内存时,就会检查 buddy 块,查看其相邻的内存块是否也已经被释放。如果是的话,将合并内存块以最小化内存碎片。这个算法的时间效率更高,但是由于使用 best-fit 方法的缘故,会产生内存浪费。

    3.slab

    关于slab 分配器有很多文档介绍。简单的说就是内核经常申请固定大小的

    一些内存空间,这些空间一般都是结构体。而这些结构体往往都会有一个共同的初始化行为比如:初始化里面的信号量、链表指针、成员。通过Sun 的大牛JeffBonwick 的研究发现,内核对这些结构体的初始化所消耗的时间比分配它们的时间还要长。所以他设计了一种算法,当这些结构体的空间被释放的时候,只是让他回到刚刚分配好的状态而不真正释放,下次再申请的时候就可以节约初始化的时间。整个过程可以理解为借用白板的过程。申请空间就是从别人那里借多块白板。由于每块白板的用处不同,每次用的时候都要先在不同的白板上画上不同的表格,然后往里面填内容。如果一般的算法则是用完白板后,直接还给人家,下次要用的时候再借回来然后画好表格。优化一点的算法就是用完后暂时不还人家,人家要用的时候再还,第二次再要用白板的时候随便取一块白板重新画表格。而使用slab 算法就是不用白板的时候擦除表格的内容留下表格,白板也暂时不还人家。下次要用的时候根据用途取出正确的白板,由于表格是现成的直接往里面填内容就可以了。省去了借白板和画表格这两个操作。


    一、slab分配器的基本观点

    *  slab分配器把内存区看作对象(object),把包含高速缓存的主内存区划分为多个slab;

    *  slab分配器把对象按照类型分组放进高速缓存,每个高速缓存都是同种类型对象的一种“储备”;

    *  每个slab由一个或多个连续的页框组成,这些页框中包含已分配的对象,也包含空闲的对象;

    *  slab分配器通过伙伴系统分配页框。

    二、slab 缓存分配器的优点

    1)、内核通常依赖于对小对象的分配,它们会在系统生命周期内进行无数次分配。slab缓存分配器通过对类似大小的对象进行缓存而提供这种功能,从而避免了常见的碎片问题。2)、slab 分配器还支持通用对象的初始化,从而避免了为同一目的而对一个对象重复进行初始化。3)、slab 分配器还可以支持硬件缓存对齐和着色,这允许不同缓存中的对象占用相同的缓存行,从而提高缓存的利用率并获得更好的性能。



    uClibc-0.9.28中的malloc可以调用mmap,从而与物理地址联系起来,也可以通过sbrk,从而与内核之间的内存管理联系起来,猜测可能也会经过slab。

    展开全文
  • C++内存地址分配和内存区划分简介

    千次阅读 2018-02-07 11:58:49
    C++内存地址分配和内存区划分简介 原文地址:http://blog.csdn.net/liuhuiyi/article/details/7530137 内存类型简介 内核:在一些系统中,当系统调用发生时,操作系统或者操作系统内核会编程应用程序内存的一...

    C++内存地址分配和内存区划分简介

    原文地址:http://blog.csdn.net/liuhuiyi/article/details/7530137

    内存类型简介

    这里写图片描述
    内核:在一些系统中,当系统调用发生时,操作系统或者操作系统内核会编程应用程序内存的一部分。
    栈:栈中包含活动记录,其中包含当前活动函数调用的返回地址和局部变量等信息。
    共享库:为了动态链接共享库文件而创建的一个内存片段
    堆内存:被用作堆内存来使用和分配的一块内存空间。如果运行时需要一些可变大小的小内存块,那么这些内存就是从这个区域中分配的
    未初始化的数据: 没有初始化的全局变量被放在固定地址中。通常,这段区域都会被初始化为0。
    初始化的数据: 任何被赋予了初始值的数据都被组织在内存中的一段连续的区域内,因此他们就能够与程序页一同被有效地载入
    程序页:构成应用程序的机器代码指令就是程序页。当有硬件支持时,程序页通常是只读的,这样就可以防止程序意外的重写其自身指令区域。
    第0页:通常,一个以地址0为开始的内存片段会被保留下来被设置为不可读区域,他可以用来捕捉一种常见的错误,这种错误就是使用一个NULL指针访问数据。

    第一部分 C++内存地址分配简介

    1 内存地址是从高地址到低地址进行分配的:

    int i=1;  
    int j=1;  
    cout<<&i<<endl<<&j<<endl;   //输出:0012FF60(高地址处) 0012FF54(低地址处)  

    2 函数参数列表的存放方式是,先对最右边的形参分配地址,后对最左边的形参分配地址。

    3 Little-endian模式的CPU对操作数的存放方式是从低字节到高字节的

    0x1234的存放方式入下:

    0X4000 0x34

    0X4001 0x12

    4 Big-endian模式的CPU对操作数的存放方式是从高字节到低字节的

    0x1234的存放方式入下:

    0x4000 0x12

    0x4001 0x34

    (关于这两种模式的更多解释:https://www.cnblogs.com/passingcloudss/archive/2011/05/03/2035273.html

    5 联合体union的存放顺序是所有成员都从低地址开始存放。

    6 一个变量的地址是由它所占内存空间中的最低位地址表示的。

    0X4000 0x34

    0X4001 0x12

    0x1234 的地址位0x4000

    7 堆栈的分配方式是从高内存地址向低内存地址分配的。

    int ivar=0;

    int iarray[2]={11, 22};

    注意iarray[2]越界使用,比如对其赋值

    iarray[2]=0;

    那么则同时对ivar赋值为0,可能产生死循环,因为它们的地址相同,即&ivar等于&iarray[2]。

    第二部分 C/C++内存区划分

    一 在C中分为这几个存储区
    1.栈 由编译器自动分配释放;
    2.堆 一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收;
    3.全局区(静态区),全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 程序结束释放;
    4.另外还有一个专门放常量的地方。 程序结束释放。

    在函数体中定义的变量通常是在栈上,用malloc, calloc, realloc等分配内存的函数分配得到的就是在堆上。在所有函数体外定义的是全局量,加了static修饰符后不管在哪里都存放在全局区(静态区),在所有函数体外定义的static变量表示在该文件中有效,不能extern到别的文件用,在函数体内定义的static表示只在该函数体内有效。另外,函数中的”adgfdf”这样的字符串存放在常量区。比如:

    int  a = 0; //全局初始化区  
    char *p1; //全局未初始化区  
    void main()  
    {       
    int b;                   //栈       
    char s[] = "abc"; //栈       
    char *p2;         //栈       
    char *p3 = "123456";       //123456{post.content}在常量区,p3在栈上       
    static int c = 0;          //全局(静态)初始化区       
    p1 = (char *)malloc(10);   //分配得来得10字节的区域在堆区       
    p2 = (char *)malloc(20);   //分配得来得20字节的区域在堆区       
    strcpy(p1, "123456");      
    //123456{post.content}放在常量区,编译器可能会将它与p3所指向的"123456"优化成一块  
    }  

    二.在C++中,内存分成5个区

    他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区
    1.栈,就是那些由编译器在需要的时候分配,在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等。
    2.堆,就是那些由new分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制,一般一个new就要对应一个delete。如果程序员没有释放掉,那么在程序结束后,操作系统会自动回收。
    3.自由存储区,就是那些由malloc等分配的内存块,他和堆是十分相似的,不过它是用free来结束自己的生命的。
    4.全局/静态存储区,全局变量和静态变量被分配到同一块内存中,在以前的C语言中,全局变量又分为初始化的和未初始化的,在C++里面没有这个区分了,他们共同占用同一块内存区。
    5.常量存储区,这是一块比较特殊的存储区,他们里面存放的是常量,不允许修改(当然,你要通过非正当手段也可以修改)。
    在bbs上,堆与栈的区分问题,似乎是一个永恒的话题。   
    首先,我们举一个例子:

    void f() 
    {
        int* p=new int[5];
    } 

    这条短短的一句话就包含了堆与栈,看到new,我们首先就应该想到,我们分配了一块堆内存,那么指针p呢?它分配的是一块栈内存,所以这句话的意思就是:在栈内存中存放了一个指向一块堆内存的指针p。

    在程序会先确定在堆中分配内存的大小,然后调用operator new分配内存,然后返回这块内存的首地址,放入栈中,他在VC6下的汇编代码如下:

    00401028 push 14h 
    0040102A call operator new (00401060) 
    0040102F add esp,4 
    00401032 mov dword ptr [ebp-8],eax `这里写代码片`
    00401035 mov eax,dword ptr [ebp-8] 
    00401038 mov dword ptr [ebp-4],eax 

      这里,我们为了简单并没有释放内存,那么该怎么去释放呢?是delete p么?错了,应该是delete []p,这是为了告诉编译器:我删除的是一个数组,VC6就会根据相应的Cookie信息去进行释放内存的工作。

      好了,我们回到我们的主题:堆和栈究竟有什么区别?

      主要的区别由以下几点:

      1、管理方式不同;

      2、空间大小不同;

      3、能否产生碎片不同;

      4、生长方向不同;

      5、分配方式不同;

      6、分配效率不同;

      管理方式:对于栈来讲,是由编译器自动管理,无需我们手工控制;对于堆来说,释放工作由程序员控制,容易产生memory leak。

      空间大小:一般来讲在32位系统下,堆内存可以达到4G的空间,从这个角度来看堆内存几乎是没有什么限制的。但是对于栈来讲,一般都是有一定的空间大小的,例如,在VC6下面,默认的栈空间大小是1M(好像是,记不清楚了)。当然,我们可以修改:

      打开工程,依次操作菜单如下:Project->Setting->Link,在Category 中选中Output,然后在Reserve中设定堆栈的最大值和commit。

      注意:Reserve最小值为4Byte;commit是保留在虚拟内存的页文件里面,它设置的较大会使栈开辟较大的值,可能增加内存的开销和启动时间。

      碎片问题:对于堆来讲,频繁的new/delete势必会造成内存空间的不连续,从而造成大量的碎片,使程序效率降低。对于栈来讲,则不会存在这个问题,因为栈是先进后出的队列,他们是如此的一一对应,以至于永远都不可能有一个内存块从栈中间弹出,在它弹出之前,在它上面的后进的栈内容已经被弹出,详细的可以参考数据结构,这里我们就不再一一讨论了。

      生长方向:对于堆来讲,生长方向是向上的,也就是向着内存地址增加的方向;对于栈来讲,它的生长方向是向下的,是向着内存地址减小的方向增长。

      分配方式:堆都是动态分配的,没有静态分配的堆。栈有2种分配方式:静态分配和动态分配。静态分配是编译器完成的,比如局部变量的分配。动态分配由alloca函数进行分配,但是栈的动态分配和堆是不同的,它的动态分配是由编译器进行释放,不需要我们手工实现。

      分配效率:栈是机器系统提供的数据结构,计算机会在底层对栈提供支持:分配专门的寄存器存放栈的地址,压栈出栈都有专门的指令执行,这就决定了栈的效率比较高(我的注释:关于EBP寄存器请参考另一篇文章)。

        堆则是C/C++函数库提供的,它的机制是很复杂的,例如为了分配一块内存,库函数会按照一定的算法
        (具体的算法可以参考数据结构/操作系统)在堆内存中搜索可用的足够大小的空间,如果没有足够大小的空间
        (可能是由于内存碎片太多),就有可能调用系统功能去增加程序数据段的内存空间,这样就有机会分到足够大小的内存,
        然后进行返回。显然,堆的效率比栈要低得多。
    

      从这里我们可以看到,堆和栈相比,由于大量new/delete的使用,容易造成大量的内存碎片;由于没有专门的系统支持,效率很低;由于可能引发用户态和核心态的切换,内存的申请,代价变得更加昂贵。所以栈在程序中是应用最广泛的,就算是函数的调用也利用栈去完成,函数调用过程中的参数,返回地址,EBP和局部变量都采用栈的方式存放。所以,我们推荐大家尽量用栈,而不是用堆。

      虽然栈有如此众多的好处,但是由于和堆相比不是那么灵活,有时候分配大量的内存空间,还是用堆好一些。

      无论是堆还是栈,都要防止越界现象的发生(除非你是故意使其越界),因为越界的结果要么是程序崩溃,要么是摧毁程序的堆、栈结构,产生意想不到的结果,就算是在你的程序运行过程中,没有发生上面的问题,你还是要小心,说不定什么时候就崩掉,那时候debug可是相当困难的:)

    展开全文
  • 内存管理的几种方法

    千次阅读 2007-10-24 20:17:00
    因为物理内存几乎全被内存整理软件占用,因此Windows被迫把其他软件的内存数据转移到硬盘上的“虚拟内存交换文件”(PageFile)中,完成这一过程之后内存整理软件就会释放掉刚刚申请的内存,至此整理过程完成,可用...

     传统的内存整理软件工作原理大概是:先申请一块“巨大内存”。因为物理内存几乎全被内存整理软件占用,因此Windows被迫把其他软件的内存数据转移到硬盘上的“虚拟内存交换文件”(PageFile)中,完成这一过程之后内存整理软件就会释放掉刚刚申请的内存,至此整理过程完成,可用物理内存显著增加。

    大体上都是那么回事,
    就是通过辅助空间,
    重新安排内存内容 ....

    但是其中使用的算法,效率是有很大的区别的 ~~

                    <script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"> </script>


    拓荒时代
    国内的程序员大多是在 Java 语言中第一次感受到垃圾收集技术的巨大魅力的,许多人也因此把 Java 和垃圾收集看成了密不可分的整体。但事实上,垃圾收集技术早在 Java 语言问世前 30 多年就已经发展和成熟起来了, Java 语言所做的不过是把这项神奇的技术带到了广大程序员身边而已。

    如果一定要为垃圾收集技术找一个孪生兄弟,那么, Lisp 语言才是当之无愧的人选。 1960 年前后诞生于 MIT 的 Lisp 语言是第一种高度依赖于动态内存分配技术的语言: Lisp 中几乎所有数据都以“表”的形式出现,而“表”所占用的空间则是在堆中动态分配得到的。 Lisp 语言先天就具有的动态内存管理特性要求 Lisp 语言的设计者必须解决堆中每一个内存块的自动释放问题(否则, Lisp 程序员就必然被程序中不计其数的 free 或 delete 语句淹没),这直接导致了垃圾收集技术的诞生和发展——说句题外话,上大学时,一位老师曾告诉我们, Lisp 是对现代软件开发技术贡献最大的语言。我当时对这一说法不以为然:布满了圆括号,看上去像迷宫一样的 Lisp 语言怎么能比 C 语言或 Pascal 语言更伟大呢?不过现在,当我知道垃圾收集技术、数据结构技术、人工智能技术、并行处理技术、虚拟机技术、元数据技术以及程序员们耳熟能详的许多技术都起源于 Lisp 语言时,我特别想向那位老师当面道歉,并收回我当时的幼稚想法。

    知道了 Lisp 语言与垃圾收集的密切关系,我们就不难理解,为什么垃圾收集技术的两位先驱者 J. McCarthy 和 M. L. Minsky 同时也是 Lisp 语言发展史上的重要人物了。 J. McCarthy 是 Lisp 之父,他在发明 Lisp 语言的同时也第一次完整地描述了垃圾收集的算法和实现方式; M. L. Minsky 则在发展 Lisp 语言的过程中成为了今天好几种主流垃圾收集算法的奠基人——和当时不少技术大师的经历相似, J. McCarthy 和 M. L. Minsky 在许多不同的技术领域里都取得了令人艳羡的成就。也许,在 1960 年代那个软件开发史上的拓荒时代里,思维敏捷、意志坚定的研究者更容易成为无所不能的西部硬汉吧。

    在了解垃圾收集算法的起源之前,有必要先回顾一下内存分配的主要方式。我们知道,大多数主流的语言或运行环境都支持三种最基本的内存分配方式,它们分别是:

    一、静态分配( Static Allocation ):静态变量和全局变量的分配形式。我们可以把静态分配的内存看成是家里的耐用家具。通常,它们无需释放和回收,因为没人会天天把大衣柜当作垃圾扔到窗外。

    二、自动分配( Automatic Allocation ):在栈中为局部变量分配内存的方法。栈中的内存可以随着代码块退出时的出栈操作被自动释放。这类似于到家中串门的访客,天色一晚就要各回各家,除了个别不识时务者以外,我们一般没必要把客人捆在垃圾袋里扫地出门。

    三、动态分配( Dynamic Allocation ):在堆中动态分配内存空间以存储数据的方式。堆中的内存块好像我们日常使用的餐巾纸,用过了就得扔到垃圾箱里,否则屋内就会满地狼藉。像我这样的懒人做梦都想有一台家用机器人跟在身边打扫卫生。在软件开发中,如果你懒得释放内存,那么你也需要一台类似的机器人——这其实就是一个由特定算法实现的垃圾收集器。

    也就是说,下面提到的所有垃圾收集算法都是在程序运行过程中收集并清理废旧“餐巾纸”的算法,它们的操作对象既不是静态变量,也不是局部变量,而是堆中所有已分配内存块。


    引用计数( Reference Counting )算法
    1960 年以前,人们为胚胎中的 Lisp 语言设计垃圾收集机制时,第一个想到的算法是引用计数算法。拿餐巾纸的例子来说,这种算法的原理大致可以描述为:

    午餐时,为了把脑子里突然跳出来的设计灵感记下来,我从餐巾纸袋中抽出一张餐巾纸,打算在上面画出系统架构的蓝图。按照“餐巾纸使用规约之引用计数版”的要求,画图之前,我必须先在餐巾纸的一角写上计数值 1 ,以表示我在使用这张餐巾纸。这时,如果你也想看看我画的蓝图,那你就要把餐巾纸上的计数值加 1 ,将它改为 2 ,这表明目前有 2 个人在同时使用这张餐巾纸(当然,我是不会允许你用这张餐巾纸来擦鼻涕的)。你看完后,必须把计数值减 1 ,表明你对该餐巾纸的使用已经结束。同样,当我将餐巾纸上的内容全部誊写到笔记本上之后,我也会自觉地把餐巾纸上的计数值减 1 。此时,不出意外的话,这张餐巾纸上的计数值应当是 0 ,它会被垃圾收集器——假设那是一个专门负责打扫卫生的机器人——捡起来扔到垃圾箱里,因为垃圾收集器的惟一使命就是找到所有计数值为 0 的餐巾纸并清理它们。

    引用计数算法的优点和缺陷同样明显。这一算法在执行垃圾收集任务时速度较快,但算法对程序中每一次内存分配和指针操作提出了额外的要求(增加或减少内存块的引用计数)。更重要的是,引用计数算法无法正确释放循环引用的内存块,对此, D. Hillis 有一段风趣而精辟的论述:

    一天,一个学生走到 Moon 面前说:“我知道如何设计一个更好的垃圾收集器了。我们必须记录指向每个结点的指针数目。” Moon 耐心地给这位学生讲了下面这个故事:“一天,一个学生走到 Moon 面前说:‘我知道如何设计一个更好的垃圾收集器了……’”

    D. Hillis 的故事和我们小时候常说的“从前有座山,山上有个庙,庙里有个老和尚”的故事有异曲同工之妙。这说明,单是使用引用计数算法还不足以解决垃圾收集中的所有问题。正因为如此,引用计数算法也常常被研究者们排除在狭义的垃圾收集算法之外。当然,作为一种最简单、最直观的解决方案,引用计数算法本身具有其不可替代的优越性。 1980 年代前后, D. P. Friedman , D. S. Wise , H. G. Baker 等人对引用计数算法进行了数次改进,这些改进使得引用计数算法及其变种(如延迟计数算法等)在简单的环境下,或是在一些综合了多种算法的现代垃圾收集系统中仍然可以一展身手。

    标记-清除( Mark-Sweep )算法
    第一种实用和完善的垃圾收集算法是 J. McCarthy 等人在 1960 年提出并成功地应用于 Lisp 语言的标记-清除算法。仍以餐巾纸为例,标记-清除算法的执行过程是这样的:

    午餐过程中,餐厅里的所有人都根据自己的需要取用餐巾纸。当垃圾收集机器人想收集废旧餐巾纸的时候,它会让所有用餐的人先停下来,然后,依次询问餐厅里的每一个人:“你正在用餐巾纸吗?你用的是哪一张餐巾纸?”机器人根据每个人的回答将人们正在使用的餐巾纸画上记号。询问过程结束后,机器人在餐厅里寻找所有散落在餐桌上且没有记号的餐巾纸(这些显然都是用过的废旧餐巾纸),把它们统统扔到垃圾箱里。

    正如其名称所暗示的那样,标记-清除算法的执行过程分为“标记”和“清除”两大阶段。这种分步执行的思路奠定了现代垃圾收集算法的思想基础。与引用计数算法不同的是,标记-清除算法不需要运行环境监测每一次内存分配和指针操作,而只要在“标记”阶段中跟踪每一个指针变量的指向——用类似思路实现的垃圾收集器也常被后人统称为跟踪收集器( Tracing Collector )

    伴随着 Lisp 语言的成功,标记-清除算法也在大多数早期的 Lisp 运行环境中大放异彩。尽管最初版本的标记-清除算法在今天看来还存在效率不高(标记和清除是两个相当耗时的过程)等诸多缺陷,但在后面的讨论中,我们可以看到,几乎所有现代垃圾收集算法都是标记-清除思想的延续,仅此一点, J. McCarthy 等人在垃圾收集技术方面的贡献就丝毫不亚于他们在 Lisp 语言上的成就了。

    复制( Copying )算法
    为了解决标记-清除算法在垃圾收集效率方面的缺陷, M. L. Minsky 于 1963 年发表了著名的论文“一种使用双存储区的 Lisp 语言垃圾收集器( A LISP Garbage Collector Algorithm Using Serial Secondary Storage )”。 M. L. Minsky 在该论文中描述的算法被人们称为复制算法,它也被 M. L. Minsky 本人成功地引入到了 Lisp 语言的一个实现版本中。

    复制算法别出心裁地将堆空间一分为二,并使用简单的复制操作来完成垃圾收集工作,这个思路相当有趣。借用餐巾纸的比喻,我们可以这样理解 M. L. Minsky 的复制算法:

    餐厅被垃圾收集机器人分成南区和北区两个大小完全相同的部分。午餐时,所有人都先在南区用餐(因为空间有限,用餐人数自然也将减少一半),用餐时可以随意使用餐巾纸。当垃圾收集机器人认为有必要回收废旧餐巾纸时,它会要求所有用餐者以最快的速度从南区转移到北区,同时随身携带自己正在使用的餐巾纸。等所有人都转移到北区之后,垃圾收集机器人只要简单地把南区中所有散落的餐巾纸扔进垃圾箱就算完成任务了。下一次垃圾收集的工作过程也大致类似,惟一的不同只是人们的转移方向变成了从北区到南区。如此循环往复,每次垃圾收集都只需简单地转移(也就是复制)一次,垃圾收集速度无与伦比——当然,对于用餐者往返奔波于南北两区之间的辛劳,垃圾收集机器人是决不会流露出丝毫怜悯的。

    M. L. Minsky 的发明绝对算得上一种奇思妙想。分区、复制的思路不仅大幅提高了垃圾收集的效率,而且也将原本繁纷复杂的内存分配算法变得前所未有地简明和扼要(既然每次内存回收都是对整个半区的回收,内存分配时也就不用考虑内存碎片等复杂情况,只要移动堆顶指针,按顺序分配内存就可以了),这简直是个奇迹!不过,任何奇迹的出现都有一定的代价,在垃圾收集技术中,复制算法提高效率的代价是人为地将可用内存缩小了一半。实话实说,这个代价未免也太高了一些。

    无论优缺点如何,复制算法在实践中都获得了可以与标记-清除算法相比拟的成功。除了 M. L. Minsky 本人在 Lisp 语言中的工作以外,从 1960 年代末到 1970 年代初, R. R. Fenichel 和 J. C. Yochelson 等人也相继在 Lisp 语言的不同实现中对复制算法进行了改进, S. Arnborg 更是成功地将复制算法应用到了 Simula 语言中。

    至此,垃圾收集技术的三大传统算法——引用计数算法、标记-清除算法和复制算法——都已在 1960 年前后相继问世,三种算法各有所长,也都存在致命的缺陷。从 1960 年代后期开始,研究者的主要精力逐渐转向对这三种传统算法进行改进或整合,以扬长避短,适应程序设计语言和运行环境对垃圾收集的效率和实时性所提出的更高要求。

    走向成熟
    从 1970 年代开始,随着科学研究和应用实践的不断深入,人们逐渐意识到,一个理想的垃圾收集器不应在运行时导致应用程序的暂停,不应额外占用大量的内存空间和 CPU 资源,而三种传统的垃圾收集算法都无法满足这些要求。人们必须提出更新的算法或思路,以解决实践中碰到的诸多难题。当时,研究者的努力目标包括:

    第一,提高垃圾收集的效率。使用标记-清除算法的垃圾收集器在工作时要消耗相当多的 CPU 资源。早期的 Lisp 运行环境收集内存垃圾的时间竟占到了系统总运行时间的 40% !——垃圾收集效率的低下直接造就了 Lisp 语言在执行速度方面的坏名声;直到今天,许多人还条件反射似地误以为所有 Lisp 程序都奇慢无比。

    第二,减少垃圾收集时的内存占用。这一问题主要出现在复制算法中。尽管复制算法在效率上获得了质的突破,但牺牲一半内存空间的代价仍然是巨大的。在计算机发展的早期,在内存价格以 KB 计算的日子里,浪费客户的一半内存空间简直就是在变相敲诈或拦路打劫。

    第三,寻找实时的垃圾收集算法。无论执行效率如何,三种传统的垃圾收集算法在执行垃圾收集任务时都必须打断程序的当前工作。这种因垃圾收集而造成的延时是许多程序,特别是执行关键任务的程序没有办法容忍的。如何对传统算法进行改进,以便实现一种在后台悄悄执行,不影响——或至少看上去不影响——当前进程的实时垃圾收集器,这显然是一件更具挑战性的工作。

    研究者们探寻未知领域的决心和研究工作的进展速度同样令人惊奇:在 1970 年代到 1980 年代的短短十几年中,一大批在实用系统中表现优异的新算法和新思路脱颖而出。正是因为有了这些日趋成熟的垃圾收集算法,今天的我们才能在 Java 或 .NET 提供的运行环境中随心所欲地分配内存块,而不必担心空间释放时的风险。

    标记-整理( Mark-Compact )算法
    标记-整理算法是标记-清除算法和复制算法的有机结合。把标记-清除算法在内存占用上的优点和复制算法在执行效率上的特长综合起来,这是所有人都希望看到的结果。不过,两种垃圾收集算法的整合并不像 1 加 1 等于 2 那样简单,我们必须引入一些全新的思路。 1970 年前后, G. L. Steele , C. J. Cheney 和 D. S. Wise 等研究者陆续找到了正确的方向,标记-整理算法的轮廓也逐渐清晰了起来:

    在我们熟悉的餐厅里,这一次,垃圾收集机器人不再把餐厅分成两个南北区域了。需要执行垃圾收集任务时,机器人先执行标记-清除算法的第一个步骤,为所有使用中的餐巾纸画好标记,然后,机器人命令所有就餐者带上有标记的餐巾纸向餐厅的南面集中,同时把没有标记的废旧餐巾纸扔向餐厅北面。这样一来,机器人只消站在餐厅北面,怀抱垃圾箱,迎接扑面而来的废旧餐巾纸就行了。

    实验表明,标记-整理算法的总体执行效率高于标记-清除算法,又不像复制算法那样需要牺牲一半的存储空间,这显然是一种非常理想的结果。在许多现代的垃圾收集器中,人们都使用了标记-整理算法或其改进版本。

    增量收集( Incremental Collecting )算法
    对实时垃圾收集算法的研究直接导致了增量收集算法的诞生。

    最初,人们关于实时垃圾收集的想法是这样的:为了进行实时的垃圾收集,可以设计一个多进程的运行环境,比如用一个进程执行垃圾收集工作,另一个进程执行程序代码。这样一来,垃圾收集工作看上去就仿佛是在后台悄悄完成的,不会打断程序代码的运行。

    在收集餐巾纸的例子中,这一思路可以被理解为:垃圾收集机器人在人们用餐的同时寻找废弃的餐巾纸并将它们扔到垃圾箱里。这个看似简单的思路会在设计和实现时碰上进程间冲突的难题。比如说,如果垃圾收集进程包括标记和清除两个工作阶段,那么,垃圾收集器在第一阶段中辛辛苦苦标记出的结果很可能被另一个进程中的内存操作代码修改得面目全非,以至于第二阶段的工作没有办法开展。

    M. L. Minsky 和 D. E. Knuth 对实时垃圾收集过程中的技术难点进行了早期的研究, G. L. Steele 于 1975 年发表了题为“多进程整理的垃圾收集( Multiprocessing compactifying garbage collection )”的论文,描述了一种被后人称为“ Minsky-Knuth-Steele 算法”的实时垃圾收集算法。 E. W. Dijkstra , L. Lamport , R. R. Fenichel 和 J. C. Yochelson 等人也相继在此领域做出了各自的贡献。 1978 年, H. G. Baker 发表了“串行计算机上的实时表处理技术( List Processing in Real Time on a Serial Computer )”一文,系统阐述了多进程环境下用于垃圾收集的增量收集算法。

    增量收集算法的基础仍是传统的标记-清除和复制算法。增量收集算法通过对进程间冲突的妥善处理,允许垃圾收集进程以分阶段的方式完成标记、清理或复制工作。详细分析各种增量收集算法的内部机理是一件相当繁琐的事情,在这里,读者们需要了解的仅仅是: H. G. Baker 等人的努力已经将实时垃圾收集的梦想变成了现实,我们再也不用为垃圾收集打断程序的运行而烦恼了。

    分代收集( Generational Collecting )算法
    和大多数软件开发技术一样,统计学原理总能在技术发展的过程中起到强力催化剂的作用。 1980 年前后,善于在研究中使用统计分析知识的技术人员发现,大多数内存块的生存周期都比较短,垃圾收集器应当把更多的精力放在检查和清理新分配的内存块上。这个发现对于垃圾收集技术的价值可以用餐巾纸的例子概括如下:

    如果垃圾收集机器人足够聪明,事先摸清了餐厅里每个人在用餐时使用餐巾纸的习惯——比如有些人喜欢在用餐前后各用掉一张餐巾纸,有的人喜欢自始至终攥着一张餐巾纸不放,有的人则每打一个喷嚏就用去一张餐巾纸——机器人就可以制定出更完善的餐巾纸回收计划,并总是在人们刚扔掉餐巾纸没多久就把垃圾捡走。这种基于统计学原理的做法当然可以让餐厅的整洁度成倍提高。

    D. E. Knuth , T. Knight , G. Sussman 和 R. Stallman 等人对内存垃圾的分类处理做了最早的研究。 1983 年, H. Lieberman 和 C. Hewitt 发表了题为“基于对象寿命的一种实时垃圾收集器( A real-time garbage collector based on the lifetimes of objects )”的论文。这篇著名的论文标志着分代收集算法的正式诞生。此后,在 H. G. Baker , R. L. Hudson , J. E. B. Moss 等人的共同努力下,分代收集算法逐渐成为了垃圾收集领域里的主流技术。

    分代收集算法通常将堆中的内存块按寿命分为两类,年老的和年轻的。垃圾收集器使用不同的收集算法或收集策略,分别处理这两类内存块,并特别地把主要工作时间花在处理年轻的内存块上。分代收集算法使垃圾收集器在有限的资源条件下,可以更为有效地工作——这种效率上的提高在今天的 Java 虚拟机中得到了最好的证明。

    应用浪潮
    Lisp 是垃圾收集技术的第一个受益者,但显然不是最后一个。在 Lisp 语言之后,许许多多传统的、现代的、后现代的语言已经把垃圾收集技术拉入了自己的怀抱。随便举几个例子吧:诞生于 1964 年的 Simula 语言, 1969 年的 Smalltalk 语言, 1970 年的 Prolog 语言, 1973 年的 ML 语言, 1975 年的 Scheme 语言, 1983 年的 Modula-3 语言, 1986 年的 Eiffel 语言, 1987 年的 Haskell 语言……它们都先后使用了自动垃圾收集技术。当然,每一种语言使用的垃圾收集算法可能不尽相同,大多数语言和运行环境甚至同时使用了多种垃圾收集算法。但无论怎样,这些实例都说明,垃圾收集技术从诞生的那一天起就不是一种曲高和寡的“学院派”技术。

    对于我们熟悉的 C 和 C++ 语言,垃圾收集技术一样可以发挥巨大的功效。正如我们在学校中就已经知道的那样, C 和 C++ 语言本身并没有提供垃圾收集机制,但这并不妨碍我们在程序中使用具有垃圾收集功能的函数库或类库。例如,早在 1988 年, H. J. Boehm 和 A. J. Demers 就成功地实现了一种使用保守垃圾收集算法( Conservative GC Algorithmic )的函数库(参见 http://www.hpl.hp.com/personal/Hans_Boehm/gc )。我们可以在 C 语言或 C++ 语言中使用该函数库完成自动垃圾收集功能,必要时,甚至还可以让传统的 C/C++ 代码与使用自动垃圾收集功能的 C/C++ 代码在一个程序里协同工作。

    1995 年诞生的 Java 语言在一夜之间将垃圾收集技术变成了软件开发领域里最为流行的技术之一。从某种角度说,我们很难分清究竟是 Java 从垃圾收集中受益,还是垃圾收集技术本身借 Java 的普及而扬名。值得注意的是,不同版本的 Java 虚拟机使用的垃圾收集机制并不完全相同, Java 虚拟机其实也经过了一个从简单到复杂的发展过程。在 Java 虚拟机的 1.4.1 版中,人们可以体验到的垃圾收集算法就包括分代收集、复制收集、增量收集、标记-整理、并行复制( Parallel Copying )、并行清除( Parallel Scavenging )、并发( Concurrent )收集等许多种, Java 程序运行速度的不断提升在很大程度上应该归功于垃圾收集技术的发展与完善。

    尽管历史上已经有许多包含垃圾收集技术的应用平台和操作系统出现,但 Microsoft .NET 却是第一种真正实用化的、包含了垃圾收集机制的通用语言运行环境。事实上, .NET 平台上的所有语言,包括 C# 、 Visual Basic .NET 、 Visual C++ .NET 、 J# 等等,都可以通过几乎完全相同的方式使用 .NET 平台提供的垃圾收集机制。我们似乎可以断言, .NET 是垃圾收集技术在应用领域里的一次重大变革,它使垃圾收集技术从一种单纯的技术变成了应用环境乃至操作系统中的一种内在文化。这种变革对未来软件开发技术的影响力也许要远远超过 .NET 平台本身的商业价值。

    大势所趋
    今天,致力于垃圾收集技术研究的人们仍在不懈努力,他们的研究方向包括分布式系统的垃圾收集、复杂事务环境下的垃圾收集、数据库等特定系统的垃圾收集等等。

    但在程序员中间,仍有不少人对垃圾收集技术不屑一顾,他们宁愿相信自己逐行编写的 free 或 delete 命令,也不愿把垃圾收集的重任交给那些在他们看来既蠢又笨的垃圾收集器。

    我个人认为,垃圾收集技术的普及是大势所趋,这就像生活会越来越好一样毋庸置疑。今天的程序员也许会因为垃圾收集器要占用一定的 CPU 资源而对其望而却步,但二十多年前的程序员还曾因为高级语言速度太慢而坚持用机器语言写程序呢!在硬件速度日新月异的今天,我们是要吝惜那一点儿时间损耗而踟躇不前,还是该坚定不移地站在代码和运行环境的净化剂——垃圾收集的一边呢?

    展开全文
  • keras 两种训练模型方式fit和fit_generator(节省内存)

    万次阅读 多人点赞 2018-04-11 17:31:09
    第一,fitimport keras from keras.models import Sequential from keras.layers import Dense import numpy as np from sklearn.preprocessing import LabelEncoder from sklearn.preprocessing import OneHot...
  • VC 检测内存泄露的几种方法

    万次阅读 2014-07-11 11:42:12
    在Visual C++中检测和隔离内存泄漏 具有动态的分配和释放内存的能力是C/C++程序语言的重要特色之一。VisualC++ debugger和CRT库提供了一系列有效的检测和鉴定内存泄漏的工具。 设置内存泄漏检测  检测内存...
  • 物理地址:这里说的物理地址内存中的内存单元实际地址,不是外部总线连接的其他电子元件的地址!物理地址属于比较好理解的,物理地址就是内存中每个内存单元的编号,这个编号是顺序排好的,物理地址的大小决定了...
  • 在这里可分为数值信息和非数值信息个方面进行讨论。 数据信息分类示意图 1.1 数值信息在计算机系统中的表示 数值信息是有正负之分的,因此,在计算机中存储数值信息必须要有表示符号的方法。由于计算机内是...
  • Java两种处理异常方法的区别

    万次阅读 多人点赞 2017-11-26 18:02:32
    Throwable类是Java语言中所有错误或异常的超类,即祖宗类,在Java中定义了很多异常类(如OutOfMemoryError、NullPointerException、IndexOutOfBoundsException等),这些异常类分为两大类: Error 和 Exception 。...
  • 最近开始学习JVM,及时整理一下,Java虚拟机在执行Java程序的过程中会把其管理的内存分为若干个不同的数据区域。 1、程序计数器(线程私有) 程序计数器是一块较小的内存空间,他可以看作是当前线程所执行的字节码...
  • 内存管理之:页和页框&地址变换结构

    万次阅读 多人点赞 2018-03-19 15:01:13
    划重点::逻辑地址空间分为若干页;物理内存空间分为若干页框(也叫作块) 页 分页存储管理是将作业的逻辑地址划分为一系列同等大小的部分,称为页。 并为各页加以编号,每个作业的页的编号都是从0开始的。...
  • 3)应用使用过程中,越来越卡——CPU能力不足/内存泄露;4)应用页面卡顿——帧率较低、页面卡顿。因此,对开发的Android应用,必须对其进行性能测试,不然将会直接影响用户体验。Android应用性能测试通常包括:启动...
  • 相关概念:实模式、保护模式、GDT、LDT、物理地址、逻辑地址、线性地址(虚拟地址) ...访问內存是通过segment:offset找到內存的。...内存的管理模式分为两种,段模式和页模式 访问一个内存地址仍然使用Se
  • https://www.mallocfree.com/interview/c-8-memory.htm标题:内存寻址:逻辑地址到物理地址转化我们知道,在计算机里,内存分为虚拟内存和物理内存。 数据是存放在物理内存中的,而程序中使用的是虚拟内存并通过虚拟...
  • (1)内存映射模块(mmap):负责把磁盘文件的逻辑地址映射到虚拟地址,以及把虚拟地址映射到物理地址。 (2)交换模块(swap):负责控制内存内容的换入和换出,它通过交换机制,使得在物理内存的页面(RAM 页)中...
  • 进程内存地址随机化--与位置无关

    千次阅读 2017-03-09 16:28:26
    与位置无关码即每次运行地址不一样,分为两种,一种是动态连接库,一种是与位置无关的应用程序。如果程序每次运行内存地址不一样,那么就能提升一定的安全性。 1. 动态库  在编译的时候加上-PIC选项即可。 2. 应用...
  • 这几个地址之间的转换
  • 逻辑地址、虚拟地址、物理地址以及内存管理

    万次阅读 多人点赞 2016-10-11 21:47:33
    本文涉及的硬件平台是X86,如果是其它平台,...——这个概念应该是这几个概念中最好理解的一个,但是值得一提的是,虽然可以直接把物理地址理解成插在机器上那根内存本身,把内存看成一个从0字节一直到最大空量逐字节的
  • 前言 内存泄露是指一些生命周期结束的对象,由于一些原因还存在内存中,并且不能被GC回收,导致内存不断的增长,最终导致程序卡顿甚至内存溢出(俗称的OOM)...Memory Monitor 是AS中自带的一种内存监视器,提供了内存
  • Java的数据类型分为大类):基本数据类型、引用类型 一、基本数据类型:是进行内容的操作,而不是进行内存的操作; Java数据类型(八大基本数据类型):六数字类型(四个整数型,个浮点型),一 字符类型...
  • 四、地址空间与内存分配

    千次阅读 2018-04-07 16:05:44
    物理地址空间和硬件直接对应,如内存条代表的主存,硬盘代表的磁盘 ,都是物理内存,其管理由硬件完成逻辑地址空间是运行的程序看到的地址空间,是一维的线性的地址空间。逻辑地址空间依赖物理地址空间而存在。2....
  • 进程虚拟地址空间与物理内存关系

    千次阅读 2013-08-28 22:07:42
    在 早期的计算机中,要运行一个程序,会把这些程序全都装入内存,程序都是直接运行在内存上的,也就是说程序中访问的内存地址都是实际的物理内存地址。当计算 机同时运行多个程序时,必须保证这些程序用到的内存总量...
  • tomcat内存溢出原因分析与解决以及java内存溢出、栈溢出的原因与排查方法
  • page fault的两种区别(major、minor)

    千次阅读 2020-09-16 15:29:07
    page fault缺页异常分为两种类型,一种叫做major page fault,这种类型的缺页可以通过 Disk IO来满足,另一种叫做minor page fault,这种缺页可以直接利用内存中的缓存页满足。 区别 对于IO子系统来说,内核中的分层...
  • 虚拟地址 、物理地址 、线性地址 、逻辑地址
  • VxWorks内存管理方案

    千次阅读 2012-06-20 10:40:57
    摘要:探讨嵌入式开发对内存管理的基本要求、嵌入式开发内存管理的关键问题以及给出一VxWorks内存管理方案,即把除VxWorks系统保留内存以外的内存分为类型进行管理:固定大小的缓冲池、动态可变的堆以及由各种...
  • cpu和内存之间——地址映射

    千次阅读 2011-11-29 00:10:56
    cpu和内存之间有三根总线,地址,数据,和控制总线。 这是在说地址之间的问题。cpu和内存之间用地址来查找数据,但是两者的地址并不总是一样的,cpu产生的是逻辑地址,而内存的就是物理地址。通常都是不一样的,...
  • 在應用中碰到如下問題, 錄入到此,以便查閱. Tomcat本身不能直接在计算机上运行,需要依赖于硬件基础之上的操作系统和一个Java虚拟机。...JVM管理两种类型的内存,堆和非堆。按照官方的说法:“Java 虚拟机具有一个
  • linux内核--段页式管理内存方法

    千次阅读 2015-01-28 19:50:28
    ——这个概念应该是这几个概念中最好理解的一个,但是值得一提的是,虽然可以直接把物理地址理解成插在机器上那根内存本身,把内存看成一 个从0字节一直到最大空量逐字节的编号的大数组,然后把这个数组叫做物理...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 356,173
精华内容 142,469
关键字:

内存地址分为哪两种表示方法