内存结构（精选7篇）
内存结构 篇1
摘要：“内存对齐”原则上讲是编译器的内在处理机制, 对于用户来讲是不可见的, 也应该是“透明的”, 编译器规定将程序中的每个“数据单元”只能放在合适的内存空间段中。然而, C语言的一个很强优势就是具有一定程度的开放性, 它允许程序员重置“内存对齐”规则, 也正是由于这些原因, 结构体具体所占内存的大小问题, 一直困扰着C语言的部分初学者。文章将在最常见Windows (32) /VC6.0编译环境下, 对几种不同类型的结构体所占内存大小进行详细探讨、分析, 最后归纳总结了C语言中一般结构体在该坏境下所占内存大小的几个结论及计算方法, 希望加深初学者对C语言结构体存储知识的理解。
关键词：内存对齐,开放性,内存大小,结构体
0引言
在C语言中, 求解结构体所占内存大小时, 很多人都会想到直接将结构体中声明的变量通过sizeof运算符分别求取各成员变量所占内存大小, 然后全部累加作为该结构体所占内存的大小。然而, 这种机械的累加往往是不对的, 因为这里涉及到内存字节对齐的问题。从理论上分析, 对于任何变量都可以放在大于其所需空间的任意一段连续内存中, 但是事实上并非如此, 实验表明特定类型的变量只能在特定的内存地址上访问, 这就需要各个变量在空间上按一定的规则存储, 而不是机械式地顺序存储[1]。对于C语言结构体的存储亦是如此。
从移植性方面考虑, 不同的硬件平台读写的规则不同, 也就是说并不是所有的硬件平台都能访问任意内存空间上的任意数据, 某些硬件平台只能在某些地址处读取某些特定类型的数据, 否则会抛出硬件异常。从读写性能方面考虑, 为了访问未对齐的内存, 处理器需要进行两次内存访问;而对齐的内存只要一次, 比如, 对于每次都是从偶地址处读取数据的编译平台来讲, 声明一个int型的变量, 若从偶地址单元处存放, 只需一个读取周期即可完成;若是从奇地址单元处存放, 反而需要2个读取周期读取该变量[2,3]。可见, C结构体的存储也应该是尽可能地遵循在自然边界上的内存对齐。
1常见的结构体形式
一般情况下, 结构体内会定义多种类型的变量, 如基本数据类型int、char、float、double等, 还有可能是一些复杂数据类型, 如结构体、共用体、数组、对象等。结合平时学习的实际情况, 下面定义四种常用形式的结构体, 作为具体的例子进行分析[4]。
例子一是一个含有三个基本变量的简单结构体;与例子一相比例子二中的结构体声明变量顺序与Struct1有所不同;例子三是一个包含了数组类型的结构体;例子四是一个嵌套了结构体的结构体。
2对应形式内存大小分析
这里我们以最常见的Windows (32位) /Visual C++6.0平台及编译环境为例。为了下面更好的分析, 首先给出几个名词定义及对应的变量表示:1对齐模数m, 是指基本数据类型的自身对齐值, 一般与对应数据类型占内存大小相等, 也同时应满足类型数据的存放“起始地址%m=0”。2指定对齐值n, 一般是指通过#pragma pack (n) 指定, 然后再通过与其匹配的#pragma pack () 取消的指定对齐值n, 在这里n的取值可以为1、2、4、8。3默认对齐值d, 编译器默认的对齐值, Windows (32) /VC6.0为8, 可以在VC IDE中的[Project]|[Settings], c/c++选项卡Category的Code Generation选项的Struct Member Alignment中查看, 如图1.1所示。4自身对齐值s, 是结构体中成员类型中对齐模数最大的那个值。5有效对齐值a, 就是最终确定的对齐值, 一般是指自身对齐值与指定对齐值中较小的那个值。这里需要指出的是上面给出的所有变量值的单位默认情况下均为字节。
表1是各种类型变量在该平台及编译环境下所占内存空间大小及自身对齐模数:
平台/环境tlongtle doubleows (32位) /VC6.048数48对于例子一, 结构体Struct1占内存的大小为12字节, 而并非是sizeof (char) +sizeof (int) +sizeof (short) =1+4+2=7, 其他几种例子使用这种计算思想也会存在出入。在该结构体中最大基本类型是int型, 在此坏境下其自身对齐模数m为4, 所以有效对齐值a为4, 即最后的存储结果会是4的倍数。因为char型A占一个字节, 其所在的存储单元剩余空间为3, 已小于int型B所需要的内存大小, 存储不下B, 故需要开辟第二个存储单元;第二个存储单元刚好放下B;最后再开辟第三个存储单元放short型C, 该存储单元空闲两个字节。整个结构体所占内存的大小为3*4字节=12字节, 若结构体的初始地址为0x00000000 (此假设在下文也成立) , 则该结构体在内存中对应的存放形式可如图2所示, 可以看出该结构体存储时, 最终以4字节对齐, 各个变量也满足具体的存放要求, 如对于int型变量B的起始地址为0x00000020, 满足0x00000020%4=0[5,6];当然, 这里如果我们在此结构提前加上一句#pragma pack (2) , 指定对齐值n为2, 则有效对齐值a为2, 即取Min (Max (mi) , n) , 其中mi表示各变量的对齐模数。此时Struct1的存放形式如图3所示, 其总共占内存大小为8个字节。
在该结构体中最大基本类型仍是int型, 有效对齐值a为4, 当char型A放在第一个存储单元后, 该单元还剩余3个字节内存空间, 足够放下紧接着定义的占2个字节内存大小的short型变量B, 之后, 剩余1个字节内存空间, 不能满足剩下的int型变量C的存放, 所以开辟了第二个存储单元, 此时刚好放完。所以例子二占用的内存字节为2*4=8, 具体如图1.4所示。同样若利用#pragma pack (2) , 指定对齐值n为2, 此时Struct2的存放形式如图1.5所示, 其总共占内存大小为8个字节。
对于例子三, 在该结构体中最大基本类型是char型, 有效对齐值a为1, 此时结构体大小计算过程如下, sizeof (Struct3) =sizeof (char) +sizeof (char) +4*sizeof (char) =1+1+4=6, 其大小为结构体中个字段大小之和, 这也是最节省空间的一种写法, 其对应存放形式如图6所示[7]。若提前加上一句#pragma pack (4) 来设定变量以4字节对齐方式, 对齐模数m小于指定对齐s, 故有效对齐值a与n相同为4。此时, Struct3的存放形式如图7所示, 其总共占内存大小为8个字节。
对于例子四, 这是一个结构体的嵌套, 在该结构体中最大基本类型是double型, 有效对齐值a应为8个字节, 开辟的第一个存储单元存放了Struct3后剩余两个字节大小的内存空间, 此时放不下double类型的B, 因而开辟了第二个存储单元存放。之后, 再开辟第三个存储单元可以放下分别占1个字节和2个字节空间大小的char A和char B[2];至此, sizeof (Struct4) ) =8+8+8=24字节, 具体如图1.8所示。若加上一句#pragma pack (4) 来设定变量以4字节为指定对齐n, 自身对齐s小于指定对齐n, 所以Struct4的存放形式如图1.9所示, 其总共占内存大小为20个字节。
3方法总结
从上面分析可以发现, 在Windows (32) /VC6.0下各种类型的变量的自身对齐模数就是该类型变量所占字节数的大小。经过对上面给出的几个例子计算可知[8,9], 1每个变量相对于结构体的首地址的偏移量必须是对齐模数m的整数倍;2整个结构体变量所占空间的大小是有效对齐参数a的整数倍, 很多参考文献中将这一结论在“圆整”中体现出来;3当结构体为空时, 整个结构体只占1个字节大小;4只含一种类型变量的结构体大小为变量的个数*s (有数组则看做数组长度个同类型变量) ;5当存在结构体嵌套时, 内层结构体遵循同样规则, 外层结构体只考虑内层结构体具体成员变量。
经过上面的例子分析发现, 要求的结构体所占内存的实际大小, 必先应求得有效对齐模数a, 下面给出在求取结构体有效对齐模的基础上, 进行结构体占用内存大小求取的一般算法:
(1) 结构体是否为空, 若为空则算法结束, 结果为1[10];
(2) 求取各声明变量的对齐模数mi;
(3) 判断有无指定对齐n, 若无, 则有效对齐a为已经声明变量中最大对齐模数的值Max (m1, m2, …, mi) , 转至第5步;
(4) 当有指定对齐n时, 有效对齐a与n的大小相同;
(5) 结构体实际大小为a*N, 其中N为声明变量的个数。
该计算思想, 对应流程图如10所示。
4结语
文章首先介绍了内存对齐的原因及必要性, 又列出了四种常见形式的结构体, 接着逐一分析了各自在Windows (32位) /Visual C++6.0平台及编译环境下所占内存大小的计算过程。在上面给出的四种结构体形式中, 第一种空间浪费严重, sizeof计算大小与预期不一致, 但是保持了每个字段的数据类型, 初学者极易出现此类问题;第二种形式, 介于第一种和第三种写法之间, 其空间上比较紧凑, 同时又保持了结构体中字段的数据类型;第三种形式, 最节省空间的写法, 也是使用sizeof求大小与预期一样的写法, 但是全部使用字节类型, 丢失了字段本生的数据类型, 不方便使用;第四种形式, 是结构体的嵌套, 使用时可能会同时存在前三种形式的优缺点。各成员变量存放的起始地址相对于结构的起始地址的偏移量必须为该变量的类型所占用的字节数的倍数。在结构中出现的各成员变量, 根据声明的顺序依次申请存储空间, 同时按照上面的结论适当调整位置, 空缺的字节自动填充。为了保证结构体的大小为有效对齐值 (即该结构中占用最大空间的类型所占用的字节数) 的倍数, 有时候在为最后一个成员变量申请空间时还要根据实际情况自动填充空缺字节。总之, 内存对齐问题很灵活, C语言初学者很容易受其困扰, 本文希望通过以具例子分析能够帮助初学者对C语言结构体的占用内存大小的计算有更好的理解。
参考文献
[1]Hutchinson C L, Jin I, Stover L.Memory cell with alignment structure:US, US 8097870 B2[P].2012
[2]张顺吉.C语言数据的内存存储特性的教学研究[J].计算机时代, 2011 (11) :54-56
[3]郭政慧, 王岩.内存对齐对网络通信程序的影响[J].实验室研究与探索, 2010, 29 (5)
[4]胡超.C语言从入门到精通[M].机械工业出版社, 2011:34-78
[5]Lefsky B, Rodman P K, Corbin S S.Memory alignment system and method, US4750154[P].1988
[6]Knobe B K, Lukas J D, Dally W J.Dynamic memory alignment on distributed memory systems[C]//In Proc.Workshop on Compilers for Parallel Computers.1992
[7]郝长胜, 杜鹏东.C语言程序设计[M].高等教育出版社, 2012:132-134
[9]杨军, 王华驰, 闫京生等.Xml消息与c语言程序结构体转换的方法及装置:CN, CN 101739245 A[P].2010
[10]Vetter P, Ohmura Y, Uchida T.Study of Memory Alignment of Nematic Liquid Crystals on Polyvinyl Alcohol Coatings[J].Japanese Journal of Applied Physics, 1993, 32 (9A) :L1239-L1241
[11]Krishna C M.Memory alignment issues in real-time systems[J].IEE Proceedings-Computers and Digital Techniques, 1998, 145 (5) :341-346
RFID读写器内存数据结构 篇2
在小型的RFID应用中, 进入RFID读写器读写范围内的标签被RFID读写器读取, 读写器将读取到的标签数据直接发往后台的应用程序或中间件进行处理。由于小规模应用时使用的读写器数量以及卡的数量不多, 大量的重复数据不会造成严重的问题。在大规模RFID应用中, 读写器每一次读取的标签数量可能很大, 并且一个中间件服务器可能连接有众多的读写器, 因此读写器如果直接将每次读取的标签数据发往中间件, 不但中间件服务器负担沉重, 而且网络数据的传输量将非常庞大。一般的做法是将数据处理环节推前, 即把RFID读写器读到的标签数据在读写器内进行过滤、分组等处理, 只向后台中间件发送经过处理的数据。这样可以大大减少网络数据传输流量及中间件服务器的处理数据量。为了提高读写器数据处理效率, 保证数据处理的实时性, 需要一种高效的标签数据过滤算法及相应的内存数据结构。
1 RFID读写器的读周期、事件及标签状态
在一个RFID读周期内, RFID读写器对读写范围内的所有标签进行读操作。由于RFID读写的射频物理特性, 在一个RFID读周期内, 并不能保证每一个在读写器识读范围内的标签都能被读到, 个别标签可能会在某个读周期内丢失, 当标签处于读写器识读范围边缘时这种丢失现象会更加明显。如下图所示。
由图1可见, 判断一个标签是否已进入读写器识读范围需要知道这一标签处于被读取状态的时间, 当一个标签在连续几个读周期 (超过一个阈值) 内被读写器读取, 则可以认为该标签进入读写器识读范围。同样地, 判断一个标签是否已离开读写器识读范围, 需要知道该标签处于丢失状态是否已超过某一个阈值。一般的来说, 一个标签从进入读写器识读范围到离开, 标签会在RFID读写器内经过五种状态:未知状态、第一次被发现、已进入、丢失、已离开。标签在读写器内所处的状态及转变机制如图2所示。当标签还未进入读写器识读范围时, 处于未知状态 (状态0) 。当标签进入读写器的识读范围边缘时, 第一次被读写器读取。这时的标签处于状态1, 即第一次被发现状态。由于在读写器读写范围的边缘因此读写器对该标签的读取不太稳定, 标签在下一个读周期内可能会丢失。如果在以后的时间里, 读写器在大于一个阈值 (Tenter_threshold) 的读周期内连续读到该标签, 则该标签被确认为进入读写器读写范围, 即处于状态2。处于状态2的标签如果在某个读周期内不能被读到, 则被认为是丢失了 (状态3) 。当丢失的时间超过一个阈值 (Tlost_threshold) 后, 该标签被认定为离开 (状态4) 。当处于离开状态时间大于一个阈值 (Tleave_threshold) 后, 标签回到状态0[1,2]。每个读周期结束后, 读写器向后台中间件或应用程序发送本次读周期内处于各状态的标签集合 (事件数据集) 。对于后台应用来说, 关心的事件数据集有:当前读周期新发现的标签集, 当前读周期刚离开的标签集, 当前读周期处于读写器识读范围内的标签集。
2RFID读写器生成的主要数据
由上一节读写器对标签的读取特点可以知道, 在RFID应用中读写器的数据处理是以读周期为单位进行的。在每个读周期结束后, 读写器需要将当前读周期读取的标签与当前读周期以前的各状态标签进行比对, 并将标签按照在当前读周期后处于新发现状态、已进入状态、新离开状态等几个状态进行分组, 形成各事件的标签集合。以下的公式表示了各事件标签集合的产生关系。
当前读周期的标签集合表示为
Sn={T|Tn} (1)
上式中Sn表示第n个周期读写器读到的所有标签集合, Tn表示第n周期读到的标签。当前读周期结束后, 处于发现状态的标签集合表示为
SnF={T|T∈Sn∩T∉S (n-1) E∩T∉S (n-1) F} (2)
上式中SnF表示第n个读周期后处于新发现状态的标签集合, S (n-1) E表示为上一周期结束后处于进入状态的所有标签集合, S (n-1) F表示为上一周期结束后处于发现状态的所有标签集合。当前读周期结束后, 处于进入状态的标签集合表示为
SnE={T|T∈Sn∩T∈S (n-1) F, tlast>tTenter}∪{T|T∈
S (n-1) E, tleave<tTleave} (3)
上式中SnE表示第n读周期结束后处于进入状态的标签集合, S (n-1) F表示为上一周期结束后处于发现状态的所有标签集合, tlast表示该标签处于发现状态的时间, tTenter表示标签由发现转入进入状态的时间阈值。S (n-1) E表示第n-1读周期结束后处于进入状态的标签集合, tleave 表示标签处于丢失状态的时间, tTleave表示标签由处于丢失状态转为离开状态的时间阈值。
当前读周期结束后, 处于离开状态的标签集合表示为:
SnL={T|T∈S (n-1) E, tleave>tTleave} (4)
上式中SnL表示第n个读周期后处于离开状态的标签集合, S (n-1) E表示第n-1读周期结束后处于进入状态的标签集合, tleave表示标签处于丢失状态的时间, tTleave表示标签由处于丢失状态转为离开状态的时间阈值。Sn、SnF、SnE、SnL 是读写器操作的最主要的四个集合, 其它的所有事件数据都可以从这四个集合得到。
3内存数据结构及操作
由以上的公式可以看出, RFID读写器的数据处理主要是集合数据的比较与查询, 具体的操作分为以下三步。
3.1数据的比对插入
每一个标签被读取后, 都需要与已经存在的标签进行比对, 以确定标签是否存在及处于什么状态。将新发现的标签插入新发现的标签集合, 对于已有的标签进行数据更新。
3.2状态查询
当前读周期结束后, 以标签状态为查询条件, 形成各事件报告。
3.3删除过期数据
对于过期的标签数据进行查询并删除。
由于在每一个读写周期内RFID读写器数据操作存在一个规律, 先做比较、插入操作, 所有标签比对完成后, 再对所有标签做各状态查询生成事件数据, 然后再将部分过期数据进行删除, 所以对于算法及数据结构的选择可以通过分别考察各算种算法及数据结构的比较、插入与范围查询的操作效率来实现。
对于比较与插入操作, 一些常用的对比查找算法特点及时间复杂度对比如表1所示。
顺序查找:主要应用于无序表的查找, 查找效率低。
折半查找与二叉树查找:具有相同的特征, 但是折半查找适合用于静态表的查找, 二叉树适合动态表的查找, 二叉树的查找效率很大程度上取决于建立二叉树时取得数据的顺序, 对于RFID应用来说数据是无序的, 因此二叉树难以保证具有O (lgn2) 的时间复杂度。平衡二叉树 (AVL) :是二叉树的一种改进, 它具有左右子树深度之差的绝对值不超过1的特性。能保证查找的时间复杂度为O (lnn) 。但由于在数据进行插入或删除的过程中会造成平衡被破坏, 所以需要进行平衡处理, 在插入删除操作比较多的情况下, 平衡操作会占去很多的时间。为了减少平衡操作的次数, 引入了T树的结构。在RFID读写器中, 读周期的标签数据查找插入阶段, 可以使用T树的结构, 使标签数据比较及插入过程达到O (lgn2) 的平均时间复杂度。但是在查询生成各事件标签数据集合时需要重新遍历整个T树, 因此降低了算法的效率。
哈希表:理论上利用哈希表查找法可以得到最优的查找效率, 最好的情况下只需一次查找就可以得到结果。哈希表查找法的时间复杂度主要取决于哈希函数及冲突处理算法的好坏。由于RFID标签取值范围很大, 很难做出限制, 所以找一个合适的哈希函数将标签的值均匀地映射到某一个范围内比较困难, 在RFID应用中难以得到很高的时间和空间效率。
对于范围查找操作, 需要将所有的处于某一状态的标签数据全部查找出来。对于以上的各种算法及结构, 都很难达到很高的效率。
4T链表树及数据操作
常用的数据结构及查询方法都不适合用于RFID数据处理。AVL树结构在对比插入操作中需要大量的平衡操作, 并且在状态查询时效率不高。为了减少AVL树的平衡操作, 可以使用T树结构。T树结构是AVL树的一种改进型, 它在AVL树的每个节点上增加数据量, 减少了平衡操作的次数, 提高了增加删除节点的效率, 目前T树结构在内存数据库 (MMDB) 中被大量的使用[3]。T树结构可以大大提高在对比、插入操作阶段的数据处理效率, 但是在状态查询上, 效率不高。如果能在T树的基础上将所有处于同一状态的节点用双向链表结构连接起来, 在做状态查询的时候只需要遍历某一状态的链表就可以将处于某一状态的所有标签遍历出来。因此可以考虑在T树结构上增加双向链表结构, 用于范围查询, 可以显著地提高范围查询的效率[4,5]。这种结构可以称为T链表树结构。这种结构可以综合两种数据结构的优点, 在RFID数据处理的两个阶段都达到较高的效率。一个T链表树的节点结构如图3所示。
每个T节点的各数据单元由五个域组成, 两个指针节点用于建立双向链表, 一个标签记录域用于记录标签号, 一个计数器域用于计数标签处于某一状态的时间, 一个状态域用于标记所处的状态。在T链表树结构中, 处于相同状态的标签形成一个链表, Front Ptr用于指向前一个处于同一状态节点, Successor Ptr用于指向下一个处于同一状态节点。整个T链表树的数据结构如图4所示。
T链表树有两个根指针, 一个Root指针指向T链表的树根节点, 另一个HPtr根指针指向连表的头指针链表。由RFID数据处理的特点可知, 在任何一个时刻标签只能处于四个Sn、SnF、SnE、SnL集合中的一个, 所以T链表树中共有四个链表头节点, 每个节点所链接的节点, 都是处于该集合中的标签。这四个集合分别代表了:上一次读标签后处于发现状态的标签节点链表指针、上一次读标签后处于已存在状态的标签节点链表指针、当前一次读标签后处于发现状态的标签节点链表指针及当前一次读标签后处于已存在状态的标签节点链表指针。
在每一个读周期中, 数据操作方法如下。
4.1查询、插入操作
对于每一个读周期, 新的标签进入时根据T树的查询规则从根节点开始作查询、插入操作。如果标签已存在则读取标签所处的状态值, 如果标签原先处于发现状态则判断该标签处于发现状态时间加上本次读取时间是否已经超过发现状态的门槛值, 如果已超过则更改标签的链表指针, 将节点链接入本次操作后已存在链表, 更改标签的状态, 时间设为0, 并形成本次进入标签的报告。如果未超过门槛值则链入本次操作后发现链表。
4.2删除操作
所有本次读入的标签都已查询完成后, 判断上一次处于发现状态的链表是否为空, 如不为空则根据链表指针遍历所有链表节点并执行节点删除操作。
4.3清除链表
判断上一次处于存在状态的链表是否为空, 如不为空则遍历所有节点, 如果节点的计数值加上本次计数值超出门槛值则表示该标签已经消失, 加入本次的消失标签报告, 从树中删除该节点。如果未超出门槛值则将计数加上本次值后链接入本次读后已存在标签链表。
由以上的操作可以得到, 任何一次读周期完成后, 所有的节点都处于当前周期的两个链表中, 而上一次读周期的两个链表必为空。因此四个链表指针可以循环使用。
5性能分析
本算法与采用多链表、T树结构的性能分析及对比情况如表2所示。
由上表可知, 多链表结构在读周期的新增标签部分效率比较低, 主要是因为需要通过遍历所有已知的节点进行对比。但是在对本次未读到的标签处理上, 只需遍历一次链表就能将所有标签找到, 效率比较高[6]。而对于T树结构, 在对比查找阶段, 由于AVL树的特点, 效率较高, 但是对于本次未读到的标签处理上, 需要重新遍历整个树才能得到所有的标签, 效率低[7,8]。T链表树是一个综合, 在对比查找阶段, 具有T树的特点, 在未读到标签处理上具有链表的特点。T链表树通过增加两个指针节点的空间, 和维护链表结构及T树结构的操作, 来换取查找及删除阶段的高效率。
6结论
根据RFID读写器的读写、输出及数据特点, 提出了T链表树的结构, 及与之相应的数据处理算法。利用T链表树结构及算法在每一个读周期内, 读写器只需对所有标签数据进行一次遍历就完成所有标签状态的维护、各标签报告的生成, 具有很高的效率, 可以极大的提高读写器的实时处理能力。
摘要：在大型RFID应用中, 需要将标签数据处理环节前移至读写器。由于读写器的硬件条件限制, 要提高读写器的实时数据处理能力, 就必须有适合RFID应用的高效的数据处理算法及存储结构。分析了RFID读写器数据处理的特点, 提出了一种特殊的T链表树结构。在T树的结构基础上增加了双向链表结构, 使得读写器在读周期的各个数据处理阶段都能保持很高的效率。在T链表树结构基础上, 还设计了一套数据处理算法, 结合特殊的数据结构, 可以极大地提高读写器的实时数据处理能力。
关键词：RFID,读写器,T树,T链表树,数据结构
参考文献
[1]EPC global.The EPCglobal architecture framework EPCglobal final version.July1, 2005
[2]EPC global.The application level events (ALE) specification version1.0.September15, 2005
[3]Lu Hongjun, Yeung Yuet, Tian Zengping.T-tree orB-tree:main memory database index structure revisited.Database Conference, 2000.ADC2000.Proceedings, 11th Australasian31Jan—3Feb2000
[4]Choi Kongrim, Kim Kyungchang.T*-tree:a main memory database index structure for real time applications.Real-Time Computing Sys-tems and Applications, 1996;Proceedings, Third International Work-shop30Oct—1Nov1996
[5]卢炎生, 邓立峰, 朱英武.支持实时数据库的L树.研究计算机工程与应用, 1997; (4) :5—7
[6]严蔚敏, 吴伟民.数据结构 (第二版) .北京:清华大学出版社, 1992
[7]The application level events (ALE) specification V1.1;EPCglobal Inc, www.epcglobalinc.org, 27—February, 2008
内存结构 篇3
关键词：内存块,多类型内存块,多链表结构,动态内存分配,动态内存释放
0 引 言
在一些复杂的嵌入式系统中,系统被划分成多个任务。每个任务所使用的内存分为固定内存和动态内存两大部分。固定内存是每个任务所定义的全局变量、局部变量、函数中的形式参数所占用的内存。固定内存的分配可以依赖开发工具和操作系统所提供的功能。
动态内存是每个任务在运行过程中,利用特定的函数所申请的内存,这段内存在使用结束后,又会被释放。在复杂的嵌入式系统中,由于任务个数多,任务功能差别又大,单纯依赖操作系统所提供的管理功能,会造成内存碎片多,空间浪费大的后果。嵌入式系统所能提供的内存空间往往是有限的,所以会严重影响系统的运行效率,甚至造成因内存空间不足而使系统崩溃的结果。因此,根据项目要求,建立一套自己的动态内存管理体系是非常必要的。本文提出了一种新的管理思想,就是基于不同大小内存块的嵌入式系统内存管理机制。
1 多链表内存管理思想的提出
在普通的操作系统中,一般以块为单位申请动态内存[1],使用的是单链表的管理方法。其特点是管理简单,但效率不高。在复杂的嵌入式系统中,各个任务所申请内存的长度差别可能很大,这种情况下,再使用单一长度的块方式来管理内存,无论块长度如何划分,都无法满足要求。
由于单一长度的块无法完全满足要求,有时必须使用不同长度的内存块来管理动态内存。所谓多类型内存块就是指多种长度的内存块,每一种类型对应一个块的长度值。根据动态内存申请长度的不同,可以使用不同类型的内存块用于满足要求。既提高了系统运行效率,又防止因内存浪费过多而造成内存不足的错误。下面介绍多类型内存块管理的数据结构和算法。
2 多类型内存块管理的单向链表结构
多类型内存块管理中,每种类型的内存块,对应一个单向链表,每一块内存,就对应链表中的一个节点。这个节点描述了对应内存块的信息。下面用实例说明如何组建这些单向链表。
某嵌入式系统中,总共有60M连续的内存空间,用于动态内存分配。而这段内存空间的起始地址是0x38000000。每次申请分配的动态内存不超过32K。系统设计人员根据项目的特点,设计了十种类型的内存块,具体的划分见表1所示。
每个内存块对应一个管理节点,该节点的数据结构是:
typedef struct MBNode
{
U32 baseadr; //内存块的首地址
U32 inext; //链表中下一个节点在数组中的位置
}T_ MBNode;
每一种类型的内存块,都对应一个管理节点的数组,数组的长度就是内存块的个数。再建立一个指向T_ MBNode的指针数组NodeArrayIndex,长度为10,NodeArrayIndex[i]的值就是类型标识i所对应的管理节点数组的首地址。NodeArrayIndex的值是固定的,是为了内存管理中查询所用。
系统启动后,要对这些数组初始化,给数组中的每个节点赋值。初始化后,数组中每个节点中的起始地址是按该节点在数组中下标位置而递增的,而节点中inext分量的值就是本节点的下标加一,指向数组中下一个节点。数组中最后一个节点的inext分量的值为-1,表示链表结尾。比如对0类型内存块节点数组的初始化程序如下:
T_ MBNode BolckNode0[8192]; //定义0类型内存块节点数组
T_ MBNode *p = BolckNode0; //定义一个指向节点的指针,并将
//其初始值设置成0类型内存块节点数组首地址
for (i = 0 ; i < 8192; i ++){
p-> baseadr = 0x38000000 + i * 64;
p++->inext =i+1;
}
(--p)-> inext = -1;
然后再定义一个指针数组,其数组长度就是内存块的类型数,在这个例子就是10了。系统初始化时,将数组中每个指针都指向相应类型的内存块节点数组的第一个元素。那么指针数组中的任一指针和相应类型的内存块节点数组组成了一个完整的单向链表,该指针是单向链表的头指针。
T_ MBNode *NodeChain[10];
这样,NodeChain数组和十个内存块节点数组形成了十个单向链表。NodeChain[i]就是类型标识为i的内存块节点的单向链表的头指针。
可以看出,每个链表的节点的首地址值都是按照链表从头到尾顺序,从小到大排列的。这个特性很重要,对链表的任何操作,都不能改变链表的这个特性。
对每个单向链表的操作都是排他性操作,所以,还应该给每个链表定义一个相应的互斥信号量[2]。
3 内存管理的分配和释放算法
使用多个链表对内存进行管理,其算法要比单个链表复杂。下面逐个介绍动态内存的分配和释放算法。
3.1 内存分配算法
分配内存的最基本原则是,找到一个相应的节点链表,将链表的头节点所管理的内存分配给申请者。这牵涉到两个问题,一是如何快速找到相应的链表,也就是分配哪种类型的内存块?二是如果找不到相应的链表,该如何处理?
确定内存块类型的原则是,该类型内存块的长度是大于等于所需内存长度的所有类型内存块中最小的。为了快速确定内存块类型,可以使用快速索引数组。快速索引数组内容是固定的,所以在程序编译的时候就可以将内容初始化[7]。
找到内存块类型标识Memti后,就从NodeChain数组中得到指向该类型链表的头指针。头指针所指的内存块就是要分配给用户的内存块,分配完后,将相应的内存块节点从链表中删除。如果该链表的头指针为空,表示对应类型的内存块已经分配完,需要使用其它类型的内存块。有两种方法用于选择其它类型的内存块。
一种是就大法,其算法描述如下:
FOR i = Memti+1 TO 9{
从内存块类型标识i的链表中去申请一个内存块
IF(分配成功){
将对应节点从链表中删除
返回该内存块首地址
}
}
返回0,表示分配失败。
就大法的特点是运算速度块,但是内存的浪费严重。
另一种方法是就小法,其算法描述如下:
FOR i = Memti-1 TO 0{
计算所需的类型标识i的内存块块数n
遍历类型标识i的内存块链表
搜索是否存在n个地址连续内存块
IF(搜索成功){
将这n个连续内存块节点删除
返回n个地址连续的内存块的首地址
}
}
返回0,表示分配失败。
就小法的特点是内存浪费较小,但比较费时。
嵌入式系统的运行速度比较重要,需要的话,应该先使用就大法,再用就小法。如果两者都失败,就认为分配内存失败。
在正常情况下,内存的分配是很快的。如果出现了异常情况,特别是使用了就小法后,速度就会变慢。从实际测试来看,出现异常情况的概率是较小的,平均分配速度比较快[1]。
3.2 内存释放算法
多链表结构的内存释放函数除了提供首地址外,还要提供被释放的内存段的长度。在释放函数中,根据内存首地址可以判定被释放的内存属于哪个类型的内存块,然后根据内存段的长度就可以判定到底有多少个内存块组成的。
假设要释放的内存首地址是MemAddr,长度是Len。内存释放的第一步就是计算出要释放内存所对应的内存块管理节点数(可能有多块),第二步就是将内存块管理节点重新插入链表。
根据MemAddr的值,查找动态内存的内存块划分表,得到对应的内存块类型标识Memti和该类型的内存首地址bgaddr,然后得到该类型的内存块长度size。根据Len和size的值,很容易计算出要释放的内存块数n。
根据Memti得到相应类型的链表,在链表中从头往后搜索,得到一个节点,该节点的内存块首地址的值大于要释放的内存首地址MemAddr。将n个要释放的内存块所对应的节点插入该节点的前面。这样做,保证了每个链表的节点的首地址值都是按照链表从头到尾顺序,从小到大排列这个原则。
3.3 内存分配结果的统计
多链表内存管理的效率和内存块的划分有很大关系。确定内存块划分方式的原则就是尽量保证分配内存时,一次性成功。在系统调试阶段,应尽量统计出内存分配结果,帮助开发人员和测试人员更好地确定内存块的划分方式。
4 结 论
在通信协议处理实验中,动态内存管理原先采用了单链表的方式,现在使用了基于多链表的管理方式。通过实验结果的观察,发现多链表的管理方式相对于单链表方式,对系统的运行速度几乎没有影响。而动态内存的分配效率有了显著提高。
为了定量地分析动态内存的使用分配效率,在实验中加入了计算动态内存分配效率的统计算法,其定义是:
分配效率=请求分配的内存容量 / 实际分配的内存容量
比如,请求分配20K的动态内存,但实际分配的是50K,动态内存分配效率就是0.4。显然,动态内存分配效率越高越好。
表2是两种动态内存管理方式动态内存分配效率的比较。
参考文献
[1]王田苗.嵌入式系统设计与实例开发[M].北京:清华大学出版社,2005.
[2]李忠民,等.ARM嵌入式VXWORKS实践教程[M].北京:北京航空航天大学出版社,2006.
[3]王学龙,等.嵌入式VXWORKS系统开发与应用[M].北京:人民邮电出版社,2003.
[4]史新福,等.32位微型计算机原理接口技术及其应用[M].西安:西北工业大学出版社,2004.
[5]马忠梅,等.ARM&Linux嵌入式系统教程[M].北京:北京航空航天大学出版社,2004.
[6]周立功,等.ARM嵌入式Linux系统勾践与驱动开发范例[M].北京:北京航空航天大学出版社,2006.
内存结构 篇4
GNU/Hurd操作系统是GNU设计用来替代Unix内核的新一代操作系统内核[1]。Hurd系统是基于CMU的Mach3.0微内核架构,由GNU小组对其进一步开发完成,并由Debian公司进行发布。
Hurd采用Mach微内核作为其内核,Mach微内核完成最基本的操作系统功能,例如进程通信、内存管理、硬件管理等。Hurd是架设在Mach上的一组服务,这一组服务贯彻了传统操作系统概念,实现了文件系统,网络协议,文件的访问控制,以及其它的操作系统功能。
Hurd与Mach系统在特点上各有千秋,例如Hurd的模块化以及微内核架构特点、Mach独有的IPC通信和内存管理特点等。本文将简单介绍Hurd与Mach系统特点,并分析Mach微内核的内存管理与接口实现。最后,讨论在Mach微内核下内存共享的实现。
1 Hurd操作系统与Mach微内核
1.1 Hurd操作系统及其特点
Hurd操作系统是GNU项目组设计用来取代Unix的新一代操作系统。虽然目前不是最流行的操作系统,但因其拥有很多独特的特性,从而与其它的操作系统相比,表现着更为出众的使用优势。Hurd的优点如下[2]:
(1)Hurd是开源的操作系统。任何人都可以使用并且修改,由GNU小组进行维护。
(2)兼容性。Hurd提供了一个通用的编程环境和用户环境,是一个类Unix的内核。Hurd使用GNU C库,并且兼容ANSI/ISO,POSIX,X/Open等标准。
(3)易于设计与扩展。Hurd不同于其他流行的操作系统内核,而是面向对象的结构。这种结构使得Hurd在进行扩展和修改时,无需重写内核,只需要修改相应的模块。
(4)多服务。Hurd实现了多线程,可高效地运行在单处理器和多处理机上。Hurd的运行性能非常稳定,还是一个很好的学习平台,各种想法实现起来也非常便捷。
GNU Hurd设计成多服务的面向对象的操作系统。可将其视为一组对象的集合,对象扩展了底层微内核Mach的功能,可以实现标准的操作系统功能以及实践系统设定的各项策略。系统的服务是通过专门的对象来实现的,这些对象在用户态下被称为server。一个服务也可以分解为一些对象,比如文件系统服务可以分解为后备存储、文件属性以及目录等。Hurd可以视为基于微内核Mach的服务的集合,包括文件系统、网络协议以及其他一些系统功能。GNU Hurd多服务操作系统的时新评论均详细介绍了Hurd的系统架构以及Hurd实现的详细细节,同时也给出了Hurd系统的优点和缺点[3]。
1.2 Mach微内核及其特点
Hurd作为GNU的操作系统,架设在微内核Mach之上,实现了传统意义上的操作系统功能。Mach是第一代的微内核结构,是由CMU大学设计并实现的微内核。GNU对其进行了修改和扩充,因而形成了GNU Mach微内核,GNU Mach兼容CMU的Mach 3.0系统。
GNU Mach是GNU项目的微内核。Mach并不显现操作系统的特点,而是借助一个简单的可扩展通信内核、用户模式的任务来实现传统操作系统功能。Mach所提供的基本功能包括控制流的管理(threads)、资源分配(tasks)、支持虚拟地址空间、管理硬件资源(如处理器、物理内存)等[4]。另外,Mach还具有强大的内存管理和进程间通信的功能,这是操作系统的基础功能,也为Hurd的server、GNU C库和用户程序提供了底层基础功能。微内核Mach本身虽不提供操作系统的功能,却也使得Hurd的服务和C库在Mach上实现了一个满足POSIX标准的操作系统。文献[5]给出了Mach微内核的设计创意和详细实现细节。
2 Mach微内核的虚拟内存管理
通常,操作系统的内存管理部分主要完成空间分配、虚拟地址映射和地址保护等功能,从而使得系统安全高效地使用有限的存储空间。Mach微内核的内存管理机制设计目标是:
(1)支持较大的、松散的虚拟地址空间。
(2)灵活的内存保护机制。
(3)copy-on-write操作。
(4)任务间内存共享,包括copy-on-write和read/write内存共享。
(5)内存映射文件。
(6)用户模式提供页和对象的后备存储[6,7]。
Mach的内存管理在设计上尽可能地独立于硬件,对硬件的唯一要求是提供页式管理机制支持,并且对于页的大小也不作限制,所有这些化简了在移植时的操作,使得Mach能够支持许多不同的体系结构。
2.1 Mach内核的5个基本抽象
Mach是一个支持并行分布多体系结构的操作系统微内核,有5个最基本的抽象概念,这些抽象概念对于理解Mach以及Mach的虚拟内存管理机制是必不缺少的。这五个概念分别是任务(Task)、线程(Thread)、端口(Port)、消息(Message)、内存对象(Memory object)[8],对其分析如下:
(1)任务(Task)。每个task是一个线程运行的执行环境,是最基本的资源分配单位。通常,task包括虚拟地址空间和系统资源(处理器、虚拟内存等),与UNIX进程的概念相类似。
(2)线程(Thread)。Thread是CPU使用的基本单位,是程序执行的实体。同一个任务内的所有thread共享全部资源。
(3)端口(Port)。port是一个信息通道。通过信道,Mach可以安全地进行消息传递。
(4)消息(Message)。message是线程之间通信使用的数据对象的类型集合。message大小不限,并可能包含指针和类型。
(5)内存对象(Memory Object)。Memory object是由server管理和提供的可以映射到一个任务的地址空间的数据备份。这是一种对存储的抽象,可以用来表示例如文件等存储实体。
2.2 Mach虚拟内存管理
Mach最著名的设计之一是其中的虚拟内存的设计,Mach将虚拟内存系统分为机器独立和机器依赖两部分。机器依赖提供一个简单的接口,负责管理硬件地址映射表;机器独立除了提供逻辑页表的管理,还提供映射表所组成的内存区域概念,同时也提供内存对象的支持和接口实现。Mach虚拟内存系统除支持单处理器外,还支持共享内存的多处理器系统,同时也具有很好的移植性,可以在各种不同的系统架构下加载运行。高性能也是Mach重要特点之一。Mach提供很大的、宽泛的虚拟地址空间、共享内存以及虚拟内存拷贝优化等等。Mach的每个任务(task)均拥有较大的地址空间范围,包括内存区域以及内存区域所映射的内存对象。Mach内规定任务的地址空间只由底层硬件的寻址限制所决定。
2.2.1 虚拟地址空间(Virtual Address Spaces)
虚拟地址空间定义了一组地址,这组地址指示线程thread在任务task执行的虚拟地址。虚拟地址空间由其对应的task命名。Mach的任务都拥有很大的虚拟地址空间,其线程的执行就是在此虚拟地址空间中。
虚拟地址空间由松散的已经索引的内存页面集合组成。Mach内核按照页面的属性值将这些内存页面分成不同的组,将其称为内存区域(memory regions)。页面的属性包括继承属性、保护属性、后备的抽象内存对象等等。系统的各项操作和运行机制均是基于内存区域的,但是用户对于内存区域的使用却无需限制,用户可以尽其所需地扩张内存区域。同时,Mach内核也可以按照适合的方式自由地合并和分割内存区域,从client的视角看,虚拟内存空间就是一个页面的集合。调用vm_region可以获得内存区域的属性。尽管内存区域是存在于内核的概念,调用vm_map也可以修改内存区域的继承和保护属性。
任务的虚拟地址空间是在任务创建时分配完成的,并于任务结束时一并销毁。当任务刚刚创建时,其虚拟内存空间是空的,必须通过执行一定操作申请地址内存空间。通过task_create调用,子任务可以继承其父任务的内存区域。而vm_inherit调用则可以修改内存区域的继承属性值,这些属性值包括:
(1)VM_INHERIT_NONE—该内存区域在新任务中不会被定义。
(2)VM_INHERIT_COPY—该内存区域将会以copy优化的方式在新任务中进行创建。
(3)VM_INHERIT_SHARE—新旧任务将完全共享同一内存区域。在此,可以看出Mach提供了父子任务的内存共享。
内存区域的语义识别是通过a memory manager的行为实现的。当一个内存区域在虚拟空间中创立时,一个虚拟内存对象(memory object)便和该内存区域联系在一起了。内存对象将负责内存区域的后备数据存储,其语义实现是通过一个称为memory manager的任务实现的。内核中不存在直接操作内存区域的系统调用,任务是通过memory manager的函数或者向memory manager发送消息来完成操作的。
vm_map调用是确定任务内存区域的唯一方法,借此可以设定该内存区域的基本信息(例如内存中位置、大小、保护属性、继承属性等)。需要指出的是,最重要的参数是对其抽象内存对象的指定,因其提供了内存区域的后备存储。
图1是以client的角度呈现的虚拟内存结构图。图中显示了三个内存区域,其中的两个共有一个相同的后备对象存储memory object,但是两者的继承属性或者保护属性可以不相同。
2.2.2 内存对象(Memory Objects)
内存对象代表了非常驻内存的内存区域,内存对象是内存区域的后备存储。而实现内存对象概念的任务则称为memory manager。memory manager实现了内存对象的完整语义,并且提供了若干接口,以方便用户使用。
用户态的任务操作内存的通用过程是:一个任务确定其内存区域,并指定该内存区域的内存对象;任务访问该内存区域的某部分,假如该内存区域不在内存中,则发生缺页中断,将其换入后继续访问;假如数据已修改,则将数据存入内存对象中,再将其换出内存;销毁内存区域以及内存对象。
内核使用内存可以将内存作为内存对象内容的缓存(cache)。该cache的一部分是常驻内存的,将此部分内存对象称之为memory cache object。内核维护cache,并对其适时、合理地进行管理、填充和刷新。
2.3 Mach虚拟内存管理接口的实现
GNU Mach很大程度上兼容了CMU的Mach 3.0,这一点在接口的层面上已经清晰地显现出来。文献[8,9]分别是Mach 3.0和GNU Mach的接口使用手册,经过分析,两者大部分相同,只是GNU Mach的接口实现简化了CMU Mach的接口,还对其进行了一定的封装处理。
在虚拟内存管理上,两者均提供了较为丰富的接口,同时,一个任务也可以修改其地址空间,例如:在页边界上分配虚拟内存区域、删除虚拟内存区域、设置虚拟内存区域的保护属性、指定虚拟内存区域的继承属性、创建和管理内存对象,内存对象可以映射另一个任务的虚拟地址空间。
Mach亦设有各类功能接口以实现其虚拟内存管理,可将这些接口分为两大类:虚拟内存接口和外部存储管理接口。
对于虚拟内存接口,主要有内存分配和回收、数据传输(读、写和拷贝数据)、内存区域属性设置(继承、保护属性)、映射内存对象。其中,映射内存对象可以将一个任务的地址映射到另外一个任务的地址空间中去,可以实现不同任务的内存共享。这一接口设置屏蔽了内存对象的操作,用户使用起来就像直接操作内存一样。其好处是大大降低了用户管理存储空间的难度,但是也有相应的不足,就是不可以使用高级的内存共享操作。
外部内存接口主要是针对于内存对象的接口,主要有设置内存对象服务、删除内存对象、内存对象的数据传输、内存对象锁定和设置内存对象属性等几类接口。使用外部内存管理接口可以实现较为复杂的内存管理,也包括内存共享操作。
3 Hurd的内存共享
通过对Mach微内核的内存管理的研究,本文提出在Hurd下的几种内存共享方案。
(1)考虑Hurd下POSIX标准的内存共享方案。为了便于实验和对比,同时在Linux和Hurd下进行了实验。
(2)使用Mach的内存对象的概念完成内存共享。这是重点阐述的部分,使用Mach内存对象的概念,并同时使用其IPC通信功能,实现内存共享与映射。
(3)考虑添加系统调用的方法完成内存共享。
3.1 内存共享
首先,介绍一下内存共享的概念。内存共享是指共享内存,从字面意义解释,就是多个进程可以将同一段内存映射到各自的进程空间,以此来实现数据的共享以及传输,这也是进程间最快的一种通信方式,图2是内存共享的示意图。
3.2 使用POSIX标准实现内存共享
Hurd系统支持POSIX标准,而POSIX标准对于内存共享是有规定含义的,所以可在Hurd系统下尝试使用POSIX的内存共享。POSIX标准对于内存共享的实现有两种方法。
(1)内存映射文件(memory-mapped file)。由open函数打开此类文件,并由mmap函数将得到的描述字映射到当前地址空间。
(2)共享内存区对象(shared-memory object)。由shm_open函数打开POSIX标准的一个IPC对象,并且使用mmap函数将其映射到进程地址空间中。
为了验证Hurd系统对于POSIX标准的内存共享,下面分别在Linux系统和Hurd系统下作了实验。
Linux系统下的POSIX内存共享有两种方法。一种是mmap系统调用映射普通文件完成内存共享;另一种是,shm_open函数打开对象,并且使用mmap函数完成内存共享。对于第二种方法,在Linux目录中存在共享内存区对象的目录dev/shm/,在此目录下可以发现打开的共享对象,符合POSIX标准。
Hurd系统是支持POSIX标准的,所以可假设Hurd系统也应该支持POSIX标准的内存共享。现将Linux下的程序移植到Hurd系统下进行对比。实验后发现,在Hurd目录中不存在共享内存区对象的目录/dev/shm,也不存在目标文件。同时,在程序执行的目录下发现了一个文件,该文件内容为共享内存对象的内容。这种情况说明了该文件是存储在本地磁盘上的,不是内存中的共享对象,因而不符合POSIX标准。
由此,得出结论:对于POSIX标准的支持,Hurd系统并没有完全实现,只是使用了文件进行模拟而已。所以,Hurd系统下,使用POSIX标准的内存共享是不可行的。
3.3 使用Mach自身接口实现内存共享
使用微内核Mach自身的接口和机制完成内存共享,可分为这样几种情况,即同一任务的不同线程之间、有父子关系的任务之间、无关系任务之间完成内存共享。对于前两种情况都比较简单,而对于第三种情况,稍微有些复杂。对其叙述如下:
(1)对于同一任务的不同线程之间的内存共享。这是共享任务全部资源的,所以,两个不同的线程可以直接完成最大限度的内存共享。这是内存共享中最为简单的情况。
(2)对于父子关系的任务之间的内存共享。可以通过设置内存区域(memory region)的继承属性来实现。
(3)对于无关系任务之间的内存共享。可以通过内存对象(memory object)和内存映射文件完成内存共享。本文将使用Mach微内核的内存管理以及内存对象(memory object)概念,完成内存共享。在Mach微内核中,结合Mach的IPC、Mach对于内存基本操作以及Mach对于内存对象的支持这三个方面的内容,即可完成内存共享的要求。整体思路是:首先建立共享的内存对象,设置内存对象属性,将内存对象映射到相应任务的地址空间,然后完成相应的访问,最后销毁内存对象。需要注意的是,在这一过程中,关键问题是实现任务间的交互、内存对象的保护和共享。
3.4 添加新的系统调用完成内存共享
虽然Hurd支持POSIX标准,但是对于内存共享并没有完全支持,在以后的版本中也可能会对其给予相应的支持。鉴于POSIX的内存共享标准,也可以在Hurd上实现符合POSIX标准或者其他形式的内存共享。这种实现则需要参考Linux和Mac OS的系统调用方式。
添加新的系统调用来实现内存共享的方法,需要添加至少两个系统调用,一个是内存区域的分配,另一个是内存区域的回收。详情请参考Mac OS的系统调用添加方式,这里就不再赘述了。
4 结束语
本文介绍了Hurd操作系统与Mach微内核,并解释了两者之间的关系,分别讲述了两者的特点和优点。着重阐述了微内核Mach的虚拟内存管理机制,并且分析其实现虚拟内存管理功能的接口实现。最后,给出了在GNU Hurd系统下的几种内存共享方法。经过实验分析,Hurd系统下POSIX标准的内存共享方法是不可行的,Hurd对于POSIX的标准没有达到完全兼容。而使用Mach内核自身的内存对象的概念可以实现内存共享,可以完成多种形式的内存共享,效果也十分理想,因而是一种很好的方法。另外,也可以考虑在Hurd下添加系统调用来完成内存共享。
参考文献
[1]GNU/Hurd[OL].http://www.gnu.org/software/hurd/hurd/doc-umentation.html
[2]BUSHNELL,THOMAS.The GNU Hurd Reference Manual[M].2007-11.
[3]WALFIELD N H,BRINKMANN M.A critique of the GNU H-urd multi-Server operating system[J].ACM SIGOPS Operatin-g Systems Review,2007.
[4]BRINKMANN,MARCUS.The GNU Mach reference manual[M].Free Software Foundation,2008-11.
[5]ACCETTA M,BARON R,BOLOSKY W.Mach:a new kernelfoundation for UNIX[J].Carnegie Mellon University.Citeseer,39(4864):1-16.
[6]RASHID,TEVANIAN R.Machine-independent virtual memo-ry management for paged uniprocessor and multiprocessor archi-tectures[J].IEEE Transactions on Computers,1988,37:896-908.
[7]王永杰,战超.MACH操作系统内存管理[J].计算机研究与发展,1992(10):27-30.
[8]BRINKMANN,MARCUS.Mach 3 Kernel Principles[M].Free S-oftware Foundation,2008:37-54.
购买内存谨防假冒 篇5
虚假内存危害大
内存条是电脑装机时必不可少的一项, 内存的好坏对电脑性能影响比较大。更重要的是, 内存能否正常工作直接关系到电脑能否正常运行, 所以内存的选择很关键。
业内专家表示, 假内存的危害极大, 可能导致电脑运行不稳定, 运行软件不稳定或内存读取错误, 严重的话可能导致内存或主机烧毁。如果消费者不幸买到假内存的话, 权益无法得到保障, 在售后服务方面也存在着很大问题。
三星原厂内存进入中国市场
三星内存在节能、环保、稳定方面表现出色, 采用40nm级半导体技术, 比60nm存储设备减少47%的能耗;同时, 三星内存更为绿色环保, 不含铅和卤素, 在产品上有显著的“GREEN”标示。
进入中国市场的三星内存, 包括DDR3台式机专用内存、DDR3笔记本专用内存、DDR2台式机专用内存、DDR2笔记本专用内存四款型号, 内存容量包括1G、2G、4G。三星原厂内存进入中国市场, 意味着市场上的内存种类更为丰富, 消费者在选购内存时将拥有更多的选择。
三星原厂内存防伪有高招
为了帮助消费者更好地选购正品, 三星内存在防伪方面做得比较到位。从外观上来看, 三星内存采用了十分少见的黑色窄版设计, 大小只有传统内存产品的三分之二。三星内存可识别度相当高, 提高了仿造的难度;同时, 三星正品内存的贴条号码和烫金号码一致, 消费者可以现场分辨真假。从而让消费者在购买之前就拒绝假冒品, 提高识别效率。
从细节上看, 三星正品内存做工精湛, 从内存颗粒到金手指, 质量绝非仿品可比。此外, 三星内存还提供“一年包换, 终身保修, 全国联保”服务, 让消费者可以高枕无忧。
Oracle内存组成分析 篇6
1. 系统全局区
系统全局区 (SGA, System Global Area) 。是一组包含一个Oracle实例的数据和控制信息的共享内存结构。其中具有两个很重要的特性:
(1) 系统全局区是共享的。多个用户可以同时登录这个实例, 并且能够同时访问系统全局区中的信息; (2) 一个系统全局区只为一个实例服务。即当一台机器上有多个实例运行时, 每个实例都有一个自己的系统全局区, 尽管系统全局区来自于操作系统的共享内存区, 但实例之间不能相互访问对方系统全局区区的信息。 (3) Oracle进程和一个系统全局区就构成了一个Oracle实例。当实例启动时, Oracle会自动从系统中分配内存给系统全局区, 而实例关闭时, 操作系统会回收这些内存。 (4) 系统全局区区是可读写的。所有登录到实例的用户都能读取系统全局区中的信息, 同时服务进程也会将oracle执行操作后修改的信息写入系统全局区区。
系统全局区主要包括以下的数据结构:数据缓存、重做日志缓存、共享池、Java池、大池、流池、数据字典缓存。
1.1 数据缓存
数据缓存专门用于存放从数据文件中读取的的数据块拷贝的区域。如果需要访问的数据块已经在数据缓存中, 就直接读写内存中的相应区域, 而无需读取数据文件, 从而大大提高性能。数据缓存对于所有oracle进程都是共享的, 即能被所有oracle进程访问。数据缓存被分为多个集合, 这样能够大大降低多CPU系统中的争用问题。
1.2 重做日志缓存
重做日志缓存是系统全局区中一段保存数据库修改信息的缓存。这些信息被存储在重做条目中。重做条目中包含了由于INSERT、UPDATE、DELETE、CREATE、ALTER或DROP所做的修改操作而需要对数据库重新组织或重做的必须信息。在必要时, 重做条目还可以用于数据库恢复。参数LOG_BUFFER决定了重做日志缓存的大小。它的默认值是512K, 最大可以到4G。当系统中存在很多的大事务或者事务数量非常多时, 可能会导致日志文件IO增加, 性能降低。这时可以考虑增加LOG_BUFFER值。
1.3 共享池
系统全局区中的共享池由库缓存、字典缓存、用于并行执行消息的缓冲以及控制结构组成。其大小由参数共享池大小决定。在32位系统中, 这个参数的默认值是8M, 而64位系统中的默认值位64M。最大为4G。对于共享池的内存管理, 是通过修正过的LRU算法表来实现的。
共享池包括下面几个组成部分:
(1) 库缓存
库缓存中包括共享SQL区、PL/SQL存储过程和包以及控制结构。任何用户都可以访问共享SQL区。因此库缓存存在于系统全局去的共享池中。
(2) 字典缓存
数据字典是有关于数据库的参考信息、数据库的结构信息和数据库中的用户信息的一组表和视图的集合。在SQL语句解析的过程中, Oracle可以非常迅速的访问这些数据字典。因为Oracle对数据字典访问比较频繁, 此内存中有两处地方被专门用于存放数据字典。数据字典缓存也被称为行缓存, 因为它是以记录行为单元存储数据的, 而不像数据缓存是以数据块为单元存储数据。内存中另外一个存储数据字典的地方是库缓存。所有Oracle的用户都可以访问这两个地方以获取数据字典信息。
(3) 保留共享池
为了拥有足够空间缓存大程序块, Oracle专门从共享池内置出一块区域来来分配内存保持这些大块。这个保留共享池的默认大小是共享池的5%。它的大小也可以通过参数SHARED_POOL_RESERVED_SIZE来调整。保留区是从共享池中分配, 不是直接从系统全局去中分配的, 它是共享池的保留部分, 用于存储大块段。
共享池中内存大于5000字节的大段就会被存放在共享池的保留部分。而这个大小限制是通过隐含参数_SHARED_POOL_RESERV ED_MIN_ALLOC来设定的。除了在实例启动过程中, 所有小于这个数的内存段永远都不会放到保留部分中, 而大于这个值的大内存段也永远不会存放到非保留区中, 即使共享池的空间不够用的情况下也是如此。
1.4 Java池
J ava池是系统全局区中的一块可选内存区, 属于系统全局区中的可变区。Java池的内存是用于存储所有会话中特定Java代码和JVM中数据。Java池的使用方式依赖于Oracle服务的运行模式。Java池的大小由参数JAVA_POOL_SIZE设置, 最大可到1G。在Oracle10g以后, 提供了一个新的Java池建议器, 来辅助数据库管理员调整Java池大小。
1.5 大池
大池是系统全局区中的一块可选内存池, 根据需要时配置。通过从大池中分配会话内存给共享服务或并行查询, oracle可以使用共享池主要来缓存共享SQL, 以防止由于共享SQL缓存收缩导致的性能消耗。此外, 为Oracle备份和恢复操作、IO服务进程和并行查询分配的内存一般都是几百K, 这么大的内存段从大池比从共享池更容易分配得到。
参数LARGE_POOL_SIZE设置大池的大小。大池是属于系统全局区的可变区的, 它不属于共享池。对于大池的访问, 是受到large memory latch保护的。它没有可重建内存段, 因此也不用LRU链表来管理。大池最大大小为4G。为了防止大池中产生碎片, 隐含参数_LARGE_POOL_MIN_ALLOC设置了大池中内存段的最小大小, 默认值是16K。
1.6 流池
流池是Oracle 10g中新增加的。是为了增加对流的支持。流池也是可选内存区, 属于系统全局区中的可变区。它的大小可以通过参数STREAMS_POOL_SIZE来指定。如果没有被指定, oracle会在第一次使用流时自动创建。如果设置了SGA_TARGET参数, Oracle会从系统全局区中分配内存给流池;如果没有指定SGA_TARGET, 则从数据缓存中转换一部分内存过来给流池。转换的大小是共享池大小的10%。Oracle同样为流池提供了一个流池建议器。
2. 程序全局区
程序全局区 (PGA, Program Global Area) , 是一块包含一个服务进程的数据和控制信息的内存区域。它是Oracle在一个服务进程启动时创建的, 是非共享的。一个Oracle进程拥有一个程序全局区内存区。一个程序全局区也只能被拥有它的那个服务进程所访问, 只有这个进程中的Oracle代码才能读写它。
程序全局区由两组区域组成:固定程序全局区和可变程序全局区。固定程序全局区的大小是固定的, 包含了大量原子变量、小的数据结构和指向可变程序全局区的指针。可变程序全局区是一个内存堆。程序全局区堆包含用于存放X$表的的内存。总的来说, 程序全局区的可变区中主要分为以下三部分内容:
1) 私有SQL区
2) 游标和SQL区
3) 会话内存
(1) 私有SQL区
私有SQL区包含了绑定变量值和运行时期内存结构信息等数据。每一个运行SQL语句的会话都有一个块私有SQL区。所有提交了相同SQL语句的用户都有各自的私有SQL区, 并且他们共享一个共享SQL区。因此, 一个共享SQL区可能和多个私有共享区相关联。
(2) 游标和SQL区
一个Oracle预编译程序或OCI程序的应用开发人员能够很明确的打开一个游标, 或者控制一块特定的私有SQL区, 将他们作为程序运行的命名资源。另外, oracle隐含的为一些SQL语句产生的递归调用也使用共享SQL区。私有SQL区是由用户进程管理的。如何分配和释放私有SQL区极大的依赖与你所使用的应用工具。而用户进程可以分配的私有SQL区的数量是由参数OPEN_CURSORS控制的, 它的默认值是50。
(3) 会话内存
会话内存是一段用于保存会话变量和其他预会话相关信息的内存。对于共享服务器模式下, 会话内存是共享的。对于复杂的查询, 运行区的很大一部分被那些内存需求很大的操作分配给SQL工作区。工作区的大小是可以调整的。一般来说, 大的工作区能让一些特定的操作性能更佳, 但也会消耗更多的内存。工作区的大小足够适应输入的数据和相关的SQL操作所需的辅助的内存就是最优的。如果不满足, 因为需要将一部分数据放到临时表空间磁盘上处理, 操作的响应时间会增长。
3. 用户全局区
程序全局区是一段包含一个Oracle服务或后台进程的数据和控制信息的内存。程序全局区的大小依赖与系统的配置。在专用服务模式下, 一个服务进程与一个用户进程相关, 程序全局区就包括了堆空间和用户全局区 (UGA, The User Global Area) 。而用户全局区由用户会话数据、游标状态和索引区组成。在共享服务模式下, 一个共享服务进程被多个用户进程共享, 此时用户全局区是共享池或大池的一部分。
程序全局区和用户全局区之间的区别可以理解为进程和会话之间的区别。在专用服务模式下, 进程和会话是一对一的;而在共享服务模式下, 进程和会话是一对多的关系。程序全局区是服务于进程的, 它包含的是进程的信息;而用户全局区是服务于会话的, 它包含的是会话的信息。因此, 在共享服务模式下, 程序全局区和用户全局区之间的关系也是一对多的。
4. 调用全局区
与其他的全局区不同, 调用全局区 (CGA, The Call Globa Area) 的存在是瞬间的。它只存在于一个调用过程中。对于实例的一些低层次的调用需要调用全局区, 包括:解析一条SQL语句;执行一条SQL语句;取一条SELECT语句的输出值。
如果语句产生了递归调用, 则需要为每个递归调用分配一个调用全局区。如上所述, 递归调用是在语句解析、优化器产生语句查询计划、DML操作时需要查询或修改数据字典信息的调用。因为无论那种模式, 会话在做调用时总需要一个进行进行处理。特别是在共享服务模式下时, 如果发现一次调用很久没有响应, 则可能需要增加程序全局区的大小。
5. 软件代码区
软件代码区 (SCA, Software Code Area) 是一部分用于存放那些正在运行和可以被运行的代码的内存区。Oracle代码一般存储在一个不同于用户程序存储区的软件代码区, 而用户程序存储区是排他的、受保护的区域。软件区的大小一般是固定的, 只有Oracle软件升级或重装后才会改变。在不同操作系统下, 这部分区域所要求的大小也不同。软件区是只读的, 可以被安装成共享的或非共享的。
金士顿系统指定内存 篇7
当年DIY红火的时候, 金士顿向来都是点名率很高的内存品牌, 经过这么多年的积累, 也把这种优势复制到了笔记本内存上。系统指定内存经过特殊设计, 各种延时设置针对特定品牌笔记本进行匹配。在选料上系统指定内存采用优质的组件, 并通过100%的测试与保证。同时, 系统指定内存的价格却要比原厂内存便宜得多, 尤其对于一些对兼容性和稳定性有较高要求的行业用户而言更具性价比。如今, 金士顿的系统指定内存共针对宏碁、苹果、华硕、戴尔、富士通、惠普、联想和东芝等品牌进行优化, 涵盖了目前主流的品牌。为了方便用户识别, 系统指定内存也有自己独特的命名规则——型号的前三位字母代表了具体优化的品牌。
金士顿会对每个新模组的模型执行一套严谨的测试流程, 确保模组设计的可靠性、统一性和兼容性, 以保证制造的每个模组都与使用模组的系统或系统类别100%兼容。每个新设计都要接受一系列审查和测试流程。同时, 金士顿一贯坚持对所有成品进行全面生产测试, 并采用不同类型的测试设备进行生产测试。设计和有效利用测试设备及软件方面的专业技术是使金士顿测试流程与众不同的关键因素之一。此外, 金士顿还聘请专业人员并采用必要资源以准确高效地执行测试程序, 并不断投资最新测试设备并改进个性化设计的测试硬件和软件。所有这些严格措施的执行都使得金士顿内存的质量数十年如一日, 早已成为行业不老的传奇。为了方便用户, 金士顿还强化了渠道体系, 推出了金士顿放心店, 仅有极少数有实力的代理商才能加入这一体系。同时, 各地完善的售后体系也保证了金士顿内存终生质保的实施。