动态存储管理的设计

计设和现个支持多程存分配释放的动存管系统(Multi-threadedDynamicMemory之后称MTDMM)该系统为多线程应用程序的内使用和管理提供有效的解决方案对多程的线程共享和线程有数据提供不同存储策根需通动存管理统出内存分配或释放的请求存储管理系统根请求在不同的存储空间中完成具体的操作对线共的内存分或放求在线程共享的存储空间中操而对于线程私的内存分配或释放请，则在该线程对的私有存储空间中操。该系统可向用提供以下两大功多个程供个共享的储间线程间的数据共享和据通信每线建立个有存储空间足程私有数据分和释。储理对接接口动态储管系以下简称供下外接口供用户用以完对程共享线程私有的动态存储单元的分配与释放int初化系每使MTDMM的序只应当使用一次成功执行则返0，否则返回误码

int终MTDMM统对于每个用MTDMM的若成功执行则回否则回代。intmm_createspace(pthread_tpth_id)新始线创建程私空间，参为相线程线程。成返回，则回误代码int线程结束前释放线程私有空间若成功执行则返，否则回错误代码。mm_alloc(pthread_tpth_id，intsize)线程私有动态内分配函数，参数是线程，size是申请大小，以字节为位若分配成功则返回分得空间的首址，类型为void*，否回。intmm_free(pthread_tpth_id,ptr)线程私有动态内存释放函数参数tid是线程线程号ptr为待放内存址通常为指针变量。若成功执行则返回0，则回误代码MM(memorymanager)3.1MMIndex_list

地址01517

space*space*space*space*

publicspaceNULL

blobloblockckckblblobloocckckk

NULL、

、、、#+1

、、space*

NULL

图动态存储管理结构的主要数据构组织MM主数据结构如1示。在MM化将待的空将分部个长间表空初空空池初定义数目）在MM初始还为线程共享数据创建1个公存储（blic），并将这个注到间引中每个初挂载定义个。当MM第1次收到某线程（非主程）的动态内存配请求，将为该程创建一个对应私有储并默认载个block后注册到引中为线的有间当MM到pth_id)请时，会将该线程pth_id对的space放入空闲空间池中，同时释放space挂载的所到空闲储块池中MM结以上的叙述，定MM下word_mm{//索引表struct

，//b

structword_space_head*

，//有当息pthread_mutex_t////pthread_mutex_t//索引表//}word_mm,义宏定义是为了让用户实现自定大小，数量等信息，这里的数据是初始化时的默认值：30//

spaceBLCOK_NUM100//

在池的目

义的展池block目//义是组织block部的SECTOR_SIZE128//定义的sector的单位节3//

的block目MM_HASH_FUC(tid)//HASH义索引表简介索引表的容纳式是采链式hash法它的作用管理所正在使用的根据定的程编号pth_id可以快速的在索表中查找到该线程对应nit,向相应的；然在这个space上完成线程的内存分配与释放请。索引表中含有下列tid和个指针该指指某用的头部个用指下一个nit单元。索引的结构tid0*1*43*-1*2*-1*......

NULLNULL图索引的结构图示了运行过程中的索引结构中一索项是共space对的索引项，这块在MM初化的时候建立，在MM销毁时候销当毁1个space时，需删除该space在索引表中对应索引项引采Hash实处冲突的法用地法，由于三作，图没显出这关系。索引表的定义根据上面的叙述定于索引表中的素如下：index_list_unit{unsignedlong//

该space*space;的块用于多block*nextUnit//hash}index_list_unit,list_unit_t;_unit_tlist_index[LIST_LENGTH]在结构体中定义的是一个行项结构体的数组4.3

intmm_list_init()初始创索表本的是得头的list数实体化。初化时调用此数，创建成功回0。intmm_list_logon(utid)线程第一次申请内存时候或显示调用创space候注索引；参数tid是编号。该函数用get函数获头和的block块动，之册表返。intlongtid)线程结束之后，在索引表中注将tid记刷-1用space头入池调rn将block块还池longtid)据tid参定返型。函只是一个能数为其函使。5.1空闲空间池中由若干个空闲成这都有一个头信息，大小零标未用。在注索表标记已用脱池。销之后仍然回到该池，池的作相当于是空闲的管理池。5.2Space数

空总闲数数

空总闲数数斥锁

图space空闲空间的组织结构如图所示，中的space都指向任何block，有要标信。5.3Space义

Space池头结信息下：structstructword_space*firstSpace;//

个//

录space的pthread_mutex_t//Space

互斥锁

//用实现对pace空}word_space_head,space_head_t;结点结构如下：inttSize;//记录space块挂总存空大小(以数示intfSize;//录space所载的空闲内存大以块数示structword_block//指一个block块word_space*sNext;//指一块Space接

int立space链头链函得结中的实体化。创一个空载的头返回指针型。在有新线程建立且space池无闲space头时用函，回针交给引，成册()响应程新立求该数优搜空池否有有返回，如果没有调上面的函数生成一个新的；返回指向获得的的指针intmm_space_return(space*ptr)响线程结束的注函数，参数ptr指线对应的将此块space头入池中。果注销成功返回0；函数还要修改链头的信息blocks6.1该池中单元block是初始化MM时候由用户定大小单的最小储元建的个数也被用户指定。被space使管，身于己的内存有套理式head包含一基本关block信息，如锁互斥剩block数等。数blcok数blockblockblock

Spacepointer图block池的据结构组织图是运行过程中某一刻的态，色表示已占而色的表示闲space中的指指向一个同个space的block会相互连。head引的线示是将有的闲的块连，这做目的方便找空的块。对block内的构以它部管理的方式，将第七节论

block池头点如：block*//指

tSize;//记fSize;//记block

池中数块

structword_block*ffBlock;//记录第一pthread_mutex_t斥锁对pace的制

fnum:k

block内部的数据构如右图示，结结下

tsNum;//shortfsNum;//

该小小

//置structword_block*//向池链中一blockstructword_block*

//被space块中的//下一个//在被占时指下一空闲block}word_block,block;其中sector的组

intmm_block_chead()建池函数使得结构体mm的mm_block_head实体block*创建个block块返型；初化。block*mm_block_reblock()应space的加动，找中第个有占的block块，回block*并且修改池信息。该函数用来展space块大小。bool*mm_block_return(block响还块动作，参数是该的块；该函数线程注销时候由引表函调，旦行，需要改针修改block池的链头。intmm_block_realloc()在池中的有块已经被用是仍然有新的线程建立block池本身私下里用此数次拓展申请辟BLOCK_RENUM个块Space7.1-sectorSector是的分配用，用于户储使用内最小单Sector按照一定量（取决宏）被组织在个block块中。它的小也是取于宏头SECTOR_SIZE，单位字节。其中，前两个字节在初始化的时候被制定，存放个r指于组织在block中（相于静链表），而在被分配出去后被用户写覆盖在线space对于的理对的理对于线程户辟释放间的内部现在space配算法指的是对于用户的局部申请有着最为实际和有效的内分配算法，这个算可以改进；本次我们的算总体思是头block为节点创s链以为位由block用态方组空闲sector，响应户的局部申请。curcur

space

blockblocktsizefsizesnext

bnext

bnext

sb_next

block

图在线space的一时状面表一：所域称型称spacefblockblock*block

用途指第一个挂载在上的block部shortshort

短型数大短型空闲数，最大space*nextspacets_numshorttotal

注后接入space池，用于串在链上记录挂在本block上的sector总数头部

fs_numshortfreefnumshortblock*nextblocksb_nextblock*

记录挂在本block上的sector空数记第一个空闲的号当静链链头在池中续block创成bh链指下一个挂载在上的block果本block占指向链中下一个用----------------------block中的小分配单元，逻件curshort

短型表的对于载的构建以用函数（参见接口），构建完成后，可注册再挂载，是容易的对初始化block即用mm_block_init数实现制是先从存中得一大小字节的间它表示头大，加上后面所的单元大返回的指针强制block*，始入充block头，地址是BYTE*p=(BYTE*)nodeBlock；所的址第个的采用强的方式这个cur值地，写入。7.4分配算法7.4.1流图我们展示了用户的一次申请中实现的流程用Alloc(tidsize)

Locate(tid)

次？

是否logon（tid）Void*指针分法

reblock

是否

图用户内存申请流程其中使到的函数都是上面的组件中所定过的函数些函实制意事项都函数介绍中说。下面的工作就是来详细的解释下图6中分法7.4.2block分算法图说block在分前经保了本中足的间分配即block不发生溢的错误分配结后block（有大存的的返给用户分配束参看图到之后从链向后查找到第个block块的fsNum>1(表还有sector可给分配)进行块的分配到一个的sector，下地的cur值写fNum头头空数进行有，是个字，是SECTOR_SIZE-2个，有个字节是给了？不错，在空的，cur值个节了个一分配，这个cur值有意义，可（实上是为值，用户拿到这个块后写入其数了）space释算法释算法的流程图在，为看了，就以。有个参数个tid用在表中定位在有直返回；还有void*，是是的空的地。采头法行入，定到的后链地址的法找到块block指的头个字节short*型且写入fnum的值将m改当回sector块的索引号，这就是头插法还回sector。下使用况分析临界分及选定的锁系统的结以三层引(space层(对、block在线使时免不对这些线性结构进行search等以这结构就是临界资源且些界源作整存的也是说，单独的nit或或是block都不成为临界资源的，只有它们在对应的线性结构上才成为临界资源一部分另外，（即共享区）由一indexnit个及个block构，由于为所有线程共享，所其整体也为临界资源。对临界资源，为了防止多线程操作时出现问题，必须对其进行同步、互斥处理，系采用加锁方来实现互斥方考到临资源任单独的单元构成界一方面考虑小粒度会带来更大的空时间开销以及更容易带来死所以每个临资源整加锁即锁量——block池来定block池shLock——池锁（来锁定spaceindex—index锁（用来锁定索引表）；——共享区来锁定共享区种分别设定block池结构和池头结中，后两种设在结中各数定关系首，为了方便与安全，所有函数如需加锁，则该函数保持运行全程不解锁，只在数将运结束时再解锁以下述只描述单层函数若函数调用函数加锁况予描）于始化数运行在序最开始，所在同时不有线程运情发生，便不用执行任何加锁操作，只将有初化可块space块建一，所以用加锁mm_block_reblock数需从block-pool上查并取块要bhLock锁。数由于需要将插block-pool，以将bhLock锁。mm_block_realloc函于需内存间做成block插入以展，以需要锁。但是该函数只被reblock调，不上。、mm_list_logoff、数由于要上找，以需将indexlock锁上函数于需要在中检索所以需要上rn函需要将插所需将shLock锁。mm_allocmm_free在参数tid要对共享区进行操作以需将锁上。以是所有锁会在何时被锁上及解开。各函数深层对锁的操作可以由以上描述和之的函数用关系图来推。MTDMM代码结文件函分布关、MTDMM系统的结

MTDMM文件构

()图统的文结构图是系统的致可分三个层:底层操层部控制、对外接层其中层操层直接面向内的block操作，下:block池头的立block池的初化block的取块block的还块block池的展

int(intblock*mm_block_reblock()block*rn(block*