8.6实例--存储分配程序
malloc并不是从一个在编译时就能确定的固定大小的数组中分配存储空间,而是在需要时向操作系统申请空间.因为程序中的某些地方可能不通过malloc调用申请空间,所以,malloc管理的空间不一定是连续的.这样,空闲存储空间以空闲块链表的方式组织,每个块包含一个长度,一个指向下一个空闲块的指针以及一个指向自身存储空间的指针,这些块按照存储地址的升序组织,最后一块(最高地址)指向第一块.
当有申请请求时,malloc将扫描空闲块链表,直到找到一个足够大的块为止.该算法称为"首次适应"(first fit);与之相对的算法是"最佳适应"(best fit),它寻找满足条件的最小块.如果该块恰好与请求的大小相符合,则将它从链表中移走并返回给用户.如果该块太大,则将它分成两部分,大小合适的块返回给用户,剩下的部分留在空闲块链表中.如果找不到一个足够大的块,则向操作系统申请一个大块并加入到空闲块链表中.
释放过程也是首先搜索空闲块链表,以找到可以插入被释放块的合适位置.如果与被释放块相邻的任一边是一个空闲块,则将这两个块合成一个更大的块,这样存储空间不会有太多的碎片.
机器类型各异,但是,每个特定的机器都有一个最受限(这里我要改一下,不是最受限,而是需要最大存储空间)的类型,如果这个类型可以存储在某个特定的地址中,则其他所有的类型也可以存放在此地址中(因为空间足够大).
空闲块包含一个指向链表中下一个块的指针,一个块的大小的记录和一个指向空闲空间本身的指针.位于块开始处的控制信息称为"头部",为了简化块的对齐,所有块的大小都必须是头部大小的整数倍,且头部已正确对齐.这是通过一个联合实现的,该联合包含所需的头部结构以及一个对齐要求最大空间的类型的实例.
下面那个align就是通过typedef设置的long的新名字,其实就是long.
这个用意就是,假定这个机器最大需求空间的就是long类型(书上假定的),那么只要分配给它的内存能存储long类型,那么其他的都可以在其中存储.因为联合中的元素内存是用的同一个地址,联合需要能保证存储其中每一个元素类型.所以这样的联合会按照long类型进行分配大小.这样的话就都是long类型,自然能对齐.
在malloc函数中,请求的长度(以字符为单位)将被舍入,以保证它是头部大小的整数倍.实际分配的块将多包含一个单元,用于头部本身.实际分配的块大小将被记录在头部的size字段中(包含头部),malloc函数返回的指针将指向空闲空间,而不是块的头部.用户可对获得的存储空间进行任何操作,但是,如果在分配的存储空间之外写入数据,则可能破坏块链表.
然后看具体代码.
最难受的就是开头的这一行(不算声明.)这是一个涉及到数学的问题.
最纠结的就是那个-1.这是一个不等式
nunits(一下简称num)乘以sizeof(Header)(以下简称h)肯定是小于等于nbytes+sizeof(Header)(以下简称n)的
即nunh≤n,因为n/h的结果会舍弃小数可能导致n/h == nun+1,nunh和n的差距不会大于1,就是说num*(h+1)≥n.这种情况是不应该发生的,结果不应该大于请求的数量.而(n-1)/h会解决这种情况,这就是-1的目的.
写了这么多,我也是有点懵的状态写的.知道什么意思,但是确实写不出来.凑合看吧.
反正作用就是反正超出需求.
链表需要从最后指到最前,而目前没有链表所以这个是直接指向了自己本身.并把大小设为0(因为没分配)
然后是遍历链表的循环.方式以前写过,就是往前移一个,把p的下一个块的地址转移到p身上,然后再指向转移后的p的下一块.没有终止条件.
当前的p是prevp的下一个空间块.
判断当前这个循环周期的这个空间块p是不是大于要求(条件符合.)
如果正好等于需求的大小.
将当前p的下一个空间块连接到p的上一个空间块prevp的尾部,略过正好的这个空间块,将其取出.因为其已被使用,不能在空闲链表中呆着.
如果大于需求的空间块.
将当前空间减去需求的空间得到剩余的空间数量.
然后用当前块的地址加上这个剩余的空间数量得到需要的空间块的起始地址(只要后半截.)
然后将这个得到的空间块的大小设置为需求的数量.
然后将freep设置为上一次找到空闲块的地方也就是prevp,因为刚刚prevp的下一级已经被取走使用,所以下次依然从这里找起.
然后是闭环的情况,(就是自己指向自己.里面啥都没有.)
调用morecore函数.
UNIX系统调用sbrk(n)返回一个指针,该指针指向n个字节的存储空间.如果没有空间空间,sbrk返回-1.必须将-1强制转换成char *类型,以便于返回值进行比较.而且,强制类型转换使得函数不会受不同机器中指针表示的不同的影响.
反正这章我建议看看就好,太多时间费在这不合适.
首先判断需求的空间是否小于最小申请单元.如果小于就将其设置为最小存储单元.
然后调用sbrk请求空间,大小就是单元数量乘以每个单元的长度.指针给cp.
如果出现错误,没有空间返回NULL.
否则将cp强制转换为Header的结构指针,并且地址给up.
然后把up的大小设置为刚刚申请的单元数.
然后释放申请的内存,因为现在这段空间没有用,只需要保存一个空白的区域就好.
,再然后返回freep?这里有问题吧???
刚刚up+1,现在再-1,就是将整个区域包括控制头都释放
这个比较是指针之间的比较啊.
free()首先定位要释放的ap对应的bp与空闲链表的相对位置，找到它的的最近的上一个和下一个空闲空间
将p设置为freep指向的块.
然后看bp的地址大于p并bp小于p的下一块不执行循环体,就是两个块中间有位置,下面操作会处理它.这里不管它.
只要不符合这两个其中一个条件都会执行循环体.并将p的下一块地址交给p.
循环体是如果这个地址大于p或者小于p的下一块的同时,p大于或者等于p的下一块,就是证明已经走了一圈了.p到了末尾.而p的下一块到了开头.
走了一圈都没地方肯定在开头或者末尾.
下面那两个if说简单也简单.但是不知道是我理解不对还是怎么回事.书上的就是看不明白.
如果bp的的长度末尾正好到了p的下一块的开头(bp在p和p的下一块之间.)
将bp改变为bp的大小机上p的下一块的大小(吞并p的下一块.)
然后把bp的下一块指向p的下一块的下一块.
就是将原先的p的下一块抹去,变为bp
如果不是正好连接到p的下一块.
则在p和p的下一块之间添加bp.
将bp的下一块指向p的下一块.bp都是在外面被上一级连接的.
下面也一样.
后面几个练习书上写的也足够了,而且比较简单,没什么需要写的地方.暂时告一段落.
