动态储存管理小教程 -

eXolution

浏览: 30610 次

最近访客更多访客>>

chenchangqun

shent17

木头人123

fanan_666

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

动态储存管理小教程

2012-1-9

其实这个不是真正正统的教程（甚至可以认为是不务正业），因为我使用的语言是JASS语言即魔兽争霸3地图编辑器的脚本语言。（好吧我知道石头你又该嘲笑我了。确实整这么长时间我一张成型的图也没拿出来。。。。但是，你不能否认我的技术！！）

但是其中算法和思想。其实和操作系统中储存管理是没啥区别的。在家各种冷，没事码码字活动活动僵硬的手指。

正好也尝试以浅显易懂的方式写一下自己小小的研究成果。

JASS这个语言是很简陋的(PASCAL风格)。他本身的数组全都固定是8192长度的。这样利用率非常的低。所以我就想做一套动态分配的数组。可以自定义数组长度提高利用率。所以我这个系统应运而生。

原理概要

jass中提供的数组都是8192长度。如此的规整因此我们可以把他看成一条内存。以下称作内存数组
实际上动态数组就是一个内存分配与回收的过程。就好比切一块长条的吐司面包。把最初是一块整的面包，逐渐切成根据具体需要的小块。而不是一口吞下。因此一个动态数组就是一个内存块。如何申请动态数组就是如何切面包的问题。（下文会交替使用内存块和面包块大家知道指的是一个东西就行）

首先。我要管理这个面包，我必须要了解他。这里我要给每块内存块记录一些信息。这样我才能更好的分配他们给大家吃。
控制信息如下。
  struct block
{ int state;//1 :内存块状态----1=占用、 0=空闲
      int initaddr;//2:内存块头地址也就是这块空间在内存数组中的起始索引
      int size;//3:内存块大小
      int prev;//4:前相邻内存块索引(前指针)
      int next;//5:后相邻内存块索引(后指针)
}

这里面我是用C语言的struct表示。在jass中其实就是以5个连续整数为整体放到数组中的，这个数组姑且叫做目录表。其实就是一个清单，纪录目前都有哪些面包块，都是多大。是分配给烧饼了还是分配给山炮了。或者是还没有分配。
然后这些控制信息节点在目录表中组成了一个双向链表。即知道自己的邻居在哪。能够方便的找到相邻的内存块。
1、申请

发面包了！首先我要从一大整块面包切一刀（这一大整块面包是目录表初始生成的一个节点）。然后把切出来的一块同时记录各种信息放到目录表里。然后分配给用户一个id 就像这样 integer a=allocArray(INT,200)
这样a就是一个200大小的整型数组了。这个a其实就是对应的内存块的控制信息节点的序号或者说索引。（因为我一个节点是包含5个数据的因此实际的索引是id*5再加上目录表初始位置）。这样就能通过目录表中的内存块信息。存取这段（数组）内存了。
存取就象这样 LoadInt(id,index);SaveInt(id,index,value)
2、回收

由于来面包party人比较多。你吃了面包，一定要自己再烤一块放到面包盘里供其他食用。否则后来到的人岂不是要饿死了。
做面包虽然复杂但对于咱们的内存块就简单多了。直接把内存块状态从占用改为空闲不就行了么！
真的这么简单？
确实是这么简单，但同时带来很大的问题。随着吃面包的人越来越多。原来那一整块面包被切的越来越碎。这样一来，后面如果来了饭量大的。每块面包都不够他吃但我们的规则又是只能拿一块。那么这个倒霉蛋是不是要注定饿死了。因此，当一个人吃完了之后又烤好新的放回去的时候。他要看下左右有没有别人新烤好放回去的面包，如果有，那他就应该回炉合并这两块或者三块面包组成一个更大块的面包。这样前面的杯具就不会发生了。这样就是释放做的最大的工作，合并相邻的空闲内存块。这里我的系统使用了一个策略即向右合并。即总是把左边的内存块合并到又边去，同时删掉左边的节点。如ABC三块A和C是空闲块。B是即将释放的。这是后会把A删掉各种信息合并到B里。变成B'C然后删掉B'把B'再合并到C里。
这样的好处是什么呢？因为我切面包总是从左开始切，那么那块面包剩余的部分（一般是较大的部分）总是在右边。这样的策略，总是能优先把内存释放到最大的那部分里。
不得不提的是，使用数组结构储存的另一大有点。上面所说的最大部分的面包在物理上总是存在数组的最左边的。而搜索可用内存块时又是从左边搜索。这样一来，分配总是从那块大的分配，而释放又总是释放到那块大的里面。这样就大大提高了内存的吞吐率，减少了内存碎片的产生。
3、存取

这个系统的重点就在于上述的分配与回首。当然存取也不得不提。
我这个系统内存理论上是没有长度限制的。我把多个数组拼成一个线性地址空间了。只需索引对8191取模即可当然还需要分支语句使用这几个数组
具体看实际代码吧
4、相关技术

下面我讲一下目录表表本身的存储机制
其实我是把他们存到一个特殊的栈里的。这种栈只能在栈顶添加节点。但是允许在任意位置删除节点。
原理是，栈顶指针指的是逻辑上的栈顶并不代表是物理上的顶端。举例如下【sp:stack pointer 栈顶指针】
   0 1  2  3 4 5  6                                                             0  1 2 3 4  5 6  7 8
[1][2][3][4][0][0][0]  此时sp=4 如果删除第2个元素则变成 [1][(4)][3][4][0][0][0][0][0]
               I                                                                                  I
这时sp=1即指向刚刚被删除的那个元素。但是刚才那个元素要储存上个栈顶的位置。用来指导sp的移动。
也即是说这种情况下，如果新数据到来，会存到第2个元素这里。同时sp为指向第2元素所指导的位置。即索引4.
以此类推。
当然需要说明的是。我的元素不止一个字段。必须有字段来表示这个位置是否是空的。
不然无法判断该位置是所存的4是业务数据还是栈顶指导数据。因此使用了块大小那个字段。
如果扫描节点时遇到一个节点的块大小是-1，则此节点是被删掉的节点，即【SP位移指导节点】(好吧自己胡乱起的名字)。
注：如果在需要位移指导时没有发现【SP位移指导节点】（其实就是初始的情况如图1sp指的那个位置是个空节点没有指导信息）
。那么此时sp=sp+1。和普通栈一样。

这种算法的好处就是利用本身的字段空间储存一些信息。而不用进行栈顶元素以为补空。但是对于单元素节点的表不适合此方法。
5、struct vector 与类型检查

我的代码中并未提供struct解决方案（这里是想在jass语言里实现struct封装）
但是我基于这个系统可以提供一个思路。
如struct
{
  int a;
  int b;
  real c;
unit u
}
则可以这样
integer a=allocArray(INT,2)//假设此时a=3
real b=allocArray(REAL,1)//b=11
unit u=allocArray(UNIT,1)//u=321
然后将a、b、u这3个数封装为一个数。即3210011003做为这个struct的id
然后使用这个id存取对用类型数据时再对这个数解析取出符合该类型的数就行了。
为什么要同时说下类型检查呢因为思路和这个是一样
我的动态数组分配的id号本身是无法表示类型的如果你申请了个整型的数组id用来存取unit的起步乱套了。
因此同理我把类型代号封装到这个id里存取时先检查类型。
当然这些所谓的类型检查是运行期检查而已，很没有意义。

也正如struct的意义在于一个新的语言支持（像vj）一样。
这些东西，如果我做一个新语言，实现也就显得有那么些价值了。编译器类型检查也比这方便效率多了。

globals
    //内存地址空间
    integer array IntArray1
    integer array IntArray2
    real array RealArray1
    real array RealArray2
    string array StrArray1
    string array StrArray2
    unit array UnitArray1
    unit array UnitArray2
    integer array ContentTable//目录表记录着系统中内存块的信息。
    //每块内存信息作为一个节点链式储存在这个数组中
     integer CTRLINFO_LEN=5//内存块控制字段的长度具体含义上面已经有解释了

    integer  MAXTYPE=4//这个是支持的类型的最大数目。系统会根据这个为每个类型划分目录表的存储区间
    //目前只是用了几个常用类型如下如果需要添加则增加MAXTYPE的值并添入类型代号即可注意类型代号必须是依次的。
    //例如我想加一个新类型timer 则定义integer TIMER=4
    integer INT=0//代表整形
    integer REAL=1
    integer STRING=2
    integer UNIT=3

    integer test=1
endglobals

function initArray takes nothing returns nothing
//初始化内存块。也就是分配第一个内存块。
    local integer atype=0
    local integer initaddr
    loop
        exitwhen atype>=MAXTYPE
        set initaddr=atype*R2I(8000/MAXTYPE)+atype
        set ContentTable[initaddr]=1
        set ContentTable[initaddr+2]=0
        set ContentTable[initaddr+3]=16000 //寻址两个数组长度
        set ContentTable[initaddr+4]=-1
        set ContentTable[initaddr+5]=-1
        set atype=atype+1
    endloop
endfunctionfunction dump takes string str returns nothing
    call DisplayTextToPlayer(GetLocalPlayer(),0,0,str)
endfunction

function searchBlock takes integer asklen,integer initaddr returns integer
    //寻找第一个满足分配要求的内存块大多数情况总会是第一块最大的。（因为他就在位置0）
    local integer n=0
        loop
            exitwhen ContentTable[initaddr+n*CTRLINFO_LEN+3]==0
            //因为不存在内存块大小为0的内存块（被删除的块大小为-1）因此遇到这个情况说明搜索到目录表物理末端了
            if(ContentTable[initaddr+n*CTRLINFO_LEN+1]==0 and ContentTable[initaddr+n*CTRLINFO_LEN+3]>=asklen) then
                return n
            endif
            set n=n+1
        endloop
        return -1

endfunction

function setPrevBlock takes integer initaddr,integer id,integer previd returns nothing
    //设置内存块id的前接内存块为previd
    set ContentTable[initaddr+id*CTRLINFO_LEN+4]=previd
endfunction
function getPrevBlock takes integer initaddr,integer id returns integer
    //获取内存块id的前内存接块
    return ContentTable[initaddr+id*CTRLINFO_LEN+4]
endfunction

function setNextBlock takes integer initaddr,integer id,integer nextid returns nothing
    //设置内存块id的后接内存块为nextid
    set ContentTable[initaddr+id*CTRLINFO_LEN+5]=nextid
endfunction
function getNextBlock takes integer initaddr,integer id returns integer
    //获取内存块id的后接内存块
    return ContentTable[initaddr+id*CTRLINFO_LEN+5]
endfunction

function removeBlock takes integer id,integer atype returns nothing
    //删除一个已经合并到其他空闲块的内存块。
    local integer initaddr=atype*R2I(8000/MAXTYPE)+atype
    local integer previd
    local integer nextid
    if(id==0) then
           call dump("严重警告第0块被删除了")//因为第0块其实是最右边的那块因此不可能被删除

    endif
     if(ContentTable[initaddr+id*CTRLINFO_LEN+3]==0) then
        call BJDebugMsg("无法删除一个不存在的节点")
        return
    else
        set ContentTable[initaddr+id*CTRLINFO_LEN+1]=ContentTable[initaddr]
        set ContentTable[initaddr+id*CTRLINFO_LEN+3]=-1//块大小变成-1 表示此节点变成sp位移指导节点
        set ContentTable[initaddr]=id
        //以下是标准的双向链表删除节点操作学过数据结构的都应该清楚
        //就是把前节点的后指针指向该节点的后节点
        //把后节点的前指针指向该节点的前节点
        set previd=getPrevBlock(initaddr,id)
        set nextid=getNextBlock(initaddr,id)
        if(previd>=0) then
            call setNextBlock(initaddr,previd,nextid)
        endif
        if(nextid>=0) then
            call setPrevBlock(initaddr,nextid,previd)
        endif
     endif

endfunction

function allocArray takes integer len,integer atype returns integer
    local integer initaddr=atype*R2I(8000/MAXTYPE)+atype
    local integer nid=-1
    local integer bid=searchBlock(len,initaddr)//找到待切的蛋糕

    if(bid==-1) then
        call MemDefrag(atype)
        //内存不足
        call dump("内存不足！")
    else
        set nid=ContentTable[initaddr]
        if(nid>8000/MAXTYPE/5) then
            call dump("内存块数量溢出!")
            return -1
        endif
        if(ContentTable[initaddr+nid*CTRLINFO_LEN+1]==0) then//处理无sp指导信息时的sp步进位移
            set ContentTable[initaddr]=ContentTable[initaddr]+1
        else
            set ContentTable[initaddr]=ContentTable[initaddr+nid*CTRLINFO_LEN+1]//否则sp位移到指导信息所标识位置
        endif

        set ContentTable[initaddr+nid*CTRLINFO_LEN+1]=1
        set ContentTable[initaddr+nid*CTRLINFO_LEN+2]=ContentTable[initaddr+bid*CTRLINFO_LEN+2]
        set ContentTable[initaddr+nid*CTRLINFO_LEN+3]=len
        set ContentTable[initaddr+nid*CTRLINFO_LEN+4]=ContentTable[initaddr+bid*CTRLINFO_LEN+4]
        if(ContentTable[initaddr+bid*CTRLINFO_LEN+4]!=-1) then
            set ContentTable[initaddr+ContentTable[initaddr+bid*CTRLINFO_LEN+4]*CTRLINFO_LEN+5]=nid
        endif
        set ContentTable[initaddr+nid*CTRLINFO_LEN+5]=bid
        //set test=test+1
        if(ContentTable[initaddr+bid*CTRLINFO_LEN+3]-len==0) then//如果正好分配完老内存块删掉
                call removeBlock(bid,atype)
        else
            set ContentTable[initaddr+bid*CTRLINFO_LEN+2]=ContentTable[initaddr+bid*CTRLINFO_LEN+2]+len
            set ContentTable[initaddr+bid*CTRLINFO_LEN+3]=ContentTable[initaddr+bid*CTRLINFO_LEN+3]-len
            set ContentTable[initaddr+bid*CTRLINFO_LEN+4]=nid
        endif

    endif

    return nid
endfunction
function destroyArray takes integer id,integer atype returns nothing
    local integer initaddr=atype*R2I(8000/MAXTYPE)+atype
    local integer flag=4
    local integer nid

    set ContentTable[initaddr+id*CTRLINFO_LEN+1]=0
    set nid=ContentTable[initaddr+id*CTRLINFO_LEN+4] //合并前接空闲块
     if(nid>=0 and ContentTable[initaddr+nid*CTRLINFO_LEN+1]==0) then
        set ContentTable[initaddr+id*CTRLINFO_LEN+2]=ContentTable[initaddr+nid*CTRLINFO_LEN+2]
        set ContentTable[initaddr+id*CTRLINFO_LEN+3]=ContentTable[initaddr+id*CTRLINFO_LEN+3]+ContentTable[initaddr+nid*CTRLINFO_LEN+3]
        set ContentTable[initaddr+id*CTRLINFO_LEN+4]=ContentTable[initaddr+nid*CTRLINFO_LEN+4]
        call removeBlock(nid,atype)
    endif
    set nid=ContentTable[initaddr+id*CTRLINFO_LEN+5]//合并后接空闲快
    if(nid>=0 and ContentTable[initaddr+nid*CTRLINFO_LEN+1]==0) then
         set ContentTable[initaddr+nid*CTRLINFO_LEN+2]=ContentTable[initaddr+id*CTRLINFO_LEN+2]
         set ContentTable[initaddr+nid*CTRLINFO_LEN+3]=ContentTable[initaddr+nid*CTRLINFO_LEN+3]+ContentTable[initaddr+id*CTRLINFO_LEN+3]
         set ContentTable[initaddr+nid*CTRLINFO_LEN+4]=ContentTable[initaddr+id*CTRLINFO_LEN+4]
        call removeBlock(id,atype)
    endif

endfunction
function CountRealIndex takes integer atype,integer id,integer index returns integer
//计算真实的索引
    local integer initaddr=atype*R2I(8000/MAXTYPE)+atype
    local integer loc=ContentTable[initaddr+id*CTRLINFO_LEN+2]+index
    if(index>=ContentTable[initaddr+id*CTRLINFO_LEN+3] or ContentTable[initaddr+id*CTRLINFO_LEN+1]==0) then
        call dump("非法的索引："+I2S(index))
    endif
    return loc

endfunction
function LDI takes integer id,integer index returns integer //loadinteger
    local integer loc=CountRealIndex(INT,id,index)
   if(loc>=8100) then
        return IntArray2[loc-8100]
    else
        return IntArray1[loc]
    endif

endfunction
function SVI takes integer id,integer index,integer val returns nothing //saveinteger
    local integer loc=CountRealIndex(INT,id,index)
   if(loc>=8100) then
       set IntArray2[loc-8100]=val
    else
       set IntArray1[loc]=val
    endif
endfunction

分享到：