垃圾回收算法手册——内存分配

1. 顺序分配(Sequential allocation)

2. 概述

   a又称为指针碰撞(bump pointer allocation)，或称为线性分配(linear allocation)

   b不适用于非移动式回收器

3. 代码示例

   1. sequentialAllocate(n):???
   2. ????//开始分配，result和free在统一起点，如果需要字节对齐，可能需要增加几个字节对齐??
   3. ????result?<—?free??
   4. ????//result增加指定空间，作为作为新起始地址??
   5. ????newFree?<—?result?+?n???
   6. ????//判断newFree是否超过了界限指针??
   7. ????if?newFree?>?limit??
   8. ????????//如果超过了，则返回空，分配失败??
   9. ????????return?null??
   10. ????//则更新free指针
   11. ????free?<—?newFree??
   12. ????return?result??

4. 空闲链表

5. 概述

6. 使用某种数据结构记录空闲内存单元的位置和大小
7. 实际数据结构并非一定是链表结构
8. 与顺序分配的代价差异十分小，主要差异在于两个分配策略对局部性改进程度的二阶效应决定的，

   ?

9. 首次适应分配(first-fit allocation)

10. 遍历链表，将发现的第一个满足分配要求的内存单元中进行分配，如果内存单元的空间大于分配空间，在符合一定条件下会执行分裂(split)单元空间操作
11. 如果内存单元的空间大于分配空间，但满足以下条件，则不进行分裂操作：
12. 分裂以后剩余空间小于算法及数据结构规定的最小可分配内存单元的大小
13. 分裂后剩余空间小于指定阈值或百分比
14. 首次分配基本代码示例
    1. //首次适应分配??
    2. //假设每个单元本身都记录了自身大小和下一个空闲内存单元的地址??
    3. firstFitAllocate(n):??
    4. ????//获取头对象??
    5. ????prev?<-?addressOf(head)??
    6. ????//死循环??
    7. ????loop??
    8. ???? //获取下个单元地址??
    9. ????????curr?<—?next(prev)??
    10. ????????if?curr?=?null??
    11. ????????????//如果当前单元为空，则分配失败??
    12. ????????????return?null???
    13. ????????else?if?size(curr)?<?n??
    14. ????????????//如果当前单元小于所需空间，则继续遍历下个单元??
    15. ????????????prev?<-?curr??
    16. ????????else??
    17. ????????????//如果当前单元符合所需空间，则开始分配内存??
    18. ????????????return?listAllocate(prev,?curr,?n)??
    19. ?? ?
    20. //策略1??
    21. //prev：上个单元地址，curr：当前单元空间地址，n：所需空间大小??
    22. listAllocate(prev,?curr,?n):??
    23. ????//获取当前单元起始地址??
    24. ????result?<—?curr??
    25. ????//判断是否需要判断??
    26. ????if?shouldSplit(size(curr),?n)???
    27. ????????//如果需要分裂单元??
    28. ????????//获取剩余部分起始地址??
    29. ????????remainder?<-?result?+?n??
    30. ????????//更新remainder下个对象起始地址??
    31. ????????next(remainder)?<—?next(curr)??
    32. ????????//更新remainder大小??
    33. ????????size(remainder)?<-?size(curr)?—?n??
    34. ????????//将prev单元的下个对象地址指向remainder??
    35. ????????next(prev)?<-?remainder???
    36. ????else??
    37. ????????//如果不需要分裂单元，则更新链表中单元指向，将已分配的空间抛离链表??
    38. ????????next(prev)?<-?next(curr)??
    39. ????return?result??
    40. ?? ?
    41. //策略2??
    42. //将单元的尾部分割出来??
    43. //return?the?portion?at?the?end?of?the?cell?being?split??
    44. //该方案不足之处在于对象对齐方式有所不同??
    45. //A?possible?disadvantage?of?this?approach?is?the?different?alignment?of?objects??
    46. listAllocateAlt(prev,?curr,?n):??
    47. ????//判断是否需要分裂??
    48. ????if?shouldSplit(size(curr),?n)??
    49. ??????? //当前单元减去所需大小，重新设定当前单元大小??
    50. ????????size(curr)?<—?size(curr)?—?n;??
    51. ????????//将当前单元加上新的单元大小，获取分配空间的起始地址??
    52. ????????result?<—?curr?+?size(curr)???
    53. ????else??
    54. ????????//如果不需要分裂则当前单元即分配单元??
    55. ????????next(prev)?<-?next(curr)??
    56. ????????result?<—?curr??
    57. ????//返回分配单元??
    58. ????return?result??

15. 循环首次适应分配(Next-fit allocation)

16. 每次查找都从上次分配的位置开始查找
17. 如果到达表尾，则从头开始找
18. 此分配策略存在如下不足：
19. 在空间上相邻的存活对象很可能不是同一时段分配的，因此回收的时间也不同，加剧了碎片化
20. 因为单元不断向前迭代，新分配的空间很可能不是刚释放的空间，因此空间局部性比较差(Accesses through the roving pointer have poor locality because the pointer cycles through all the free cells.)
21. 分配器的局部性也会因为同一时间分配的对象不在连续的位置上而受影响(The allocated objects may also exhibit poor locality, being spread out through memory and interspersed with objects allocated by previous mutator phases.)
22. 代码实例
    1. //循环首次适应分配??
    2. nextFitAllocate(n):??
    3. ????//获取上次单元地址??
    4. ????start?<—?prev??
    5. ????//死循环??
    6. ????loop??
    7. ????????//获取下个单元地址??
    8. ????????curr?<—?next(prev)??
    9. ????????//判断下个单元是否为空??
    10. ????????if?curr?=?null??
    11. ????????????//如果下个单元为空，则获取重新定位到头地址??
    12. ????????????prev?<—?addressOf?(head)??
    13. ????????????//再次获取下个单元地址??
    14. ????????????curr?<-?next(prev)??
    15. ????????//判断上次单元和开始单元是哦符相同??
    16. ????????if?prev?=?start??
    17. ????????????//如果相同，则说明已经轮训一遍都未找到合适的单元，返回空??
    18. ????????????return?null??
    19. ????????//判断当前单元是否符合容量需求??
    20. ????????else?if?size(curr)?<?n??
    21. ????????????//如果不符合容量要求，则进入下个单元??
    22. ????????????prev?<—?curr??
    23. ????????else??
    24. ????????????//如果符合分配需求，则??
    25. ????????????return?listAllocate(prev,?curr,?n)??

23. 最佳适应分配(best-fit allocation)

24. 查找最接近分配需求大小的单元(Best-fit allocation finds the cell whose size most closely matches the request)
25. 目标是减少空间浪费和单元分裂
26. 代码示例
    1. //最佳适应分配??
    2. bestFitAllocate(n):??
    3. ????//初始化单元最佳位置??
    4. ????best?<-?null??
    5. ????//初始化最佳单元的大小为无限大
    6. ????bestSize?<—?oo??
    7. ????//获取头地址??
    8. ????prev?<—?addressOf?(head)??
    9. ????loop??
    10. ????????//获取下个单元地址??
    11. ????????curr?<—?next(prev)??
    12. ????????//判断当前是否为空，单元大小是否符合需求?
    13. ????????if?curr?=?null?||?size(curr)?=?n
    14. //如果当前单元为空或大小正好是需求大小，则进入分配阶段
    15. ????????????//判断当前单元是否为空??
    16. ????????????if?curr?!=?null??
    17. ????????????????//如果当前单元非空，则获取最佳单元上个单元地址??
    18. ????????????????bestPrev?<—?prev??
    19. ????????????????//当前单元即为最佳单元??
    20. ????????????????best?<—?curr??
    21. ????????????else?if?best?=?null??
    22. ????????????????//如果最佳单元为空，则返回null，分配失败??
    23. ????????????????return?null??
    24. ????????????//分配内存??
    25. ????????????return?listAllocate(bestPrev,?best,?n)??
    26. ????????//判断当前单元是否小于需求或大于最佳大小??
    27. ????????else?if?size(curr)?<?n?||?bestSize?<?size(curr)??
    28. ????????????//如果当前单元小于需求或大于最佳大小，则进入下个循环??
    29. ????????????prev?<—?curr??
    30. ????????else??
    31. ????????????//如果如果当前单元大于需求且小于等于最佳大小??
    32. ????????????//设置当前单元为最佳单元??
    33. ????????????best?<—?curr??
    34. ????????????bestPrev?<—?prev??
    35. ????????????//当前单元大小为最佳大小单元??
    36. ????????????bestSize?<—?size(curr)??

27. 链表加速方案

28. 采用平衡二叉树组织内存单元，从而可以按空间大小或地址顺序进行排序。如果按节点大小排序，可将相同大小的空闲节点组织成链表来管理
29. 对于首次适应分配和循环首次适用分配，有笛卡尔树(Cartesian tree)和位图适应分配(bitmapped- fits allocation)等
30. 位图适应分配，适用额外位图记录每个可分配内存颗粒状态，有以下优点：
31. 通过映射表，分配时仅需根据位图中一个字节计算既可得知对应的8个内存颗粒所能构成的最长可连续空间。
32. 位图本身和对象隔离，因此不容被破坏(They are ‘on the side‘ and thus less vulnerable to corruption)
33. 不用记录回收信息，从而降低对内存大小的要求(They do not require information to be recorded in the free and allocated cells, and thus minimise constraints on cell size)
34. 相对于内存单元，位图更紧凑，因此可提高缓存命中率和局部性

    ?

35. 笛卡尔树(Cartesian tree)

36. 适用于优化首次适应分配和循环首次适用分配方案的平衡树
37. 依照节点地址排序，同时也将节点按大小组织成堆，从而满足快速查找
38. 树节点内容包括：单元地址和大小，左右节点指针，节点自身以及子树的最大空闲单元大小
39. 代码示例
    1. //笛卡尔树--基于首次适应分配??
    2. firstFitAllocateCartesian(n):??
    3. ????parent?<—?null??
    4. ????//从根开始遍历??
    5. ????curr?<—?root??
    6. ????loop??
    7. ???? //判断左节点非空且左节点最大单元大小是否满足需求??
    8. ????? if?left(curr)?!=?null?&&?max(left(curr))?>=?n??
    9. ????????//如果左节点非空且最大单元大小满足需求，则从左节点遍历??
    10. ????????parent?<—?curr??
    11. ????????curr?<—?left(curr)??????
    12. ??????else?if?prev?<?curr?&&?size(curr)?>=?n??
    13. ????????//如果当前节点是在上个扫描到节点之后且符合需求大小??
    14. ????????prev?<—?curr??
    15. ????????//分配资源，并增删树??
    16. ????????return?treeAllocate(curr,?parent,?n)??
    17. ??????else?if?right(curr)?!=?null?&&?max(right(curr))?>?n??
    18. ??????????//如果右节点非空且最大单元大小满足需求，则从右节点遍历??
    19. ??????????parent?<—?curr??
    20. ?????? ???curr?<—?right(curr)??
    21. ??????else??
    22. ??????????//否则OOM??
    23. ??????????return?null??

垃圾回收算法手册——内存分配

原文：https://www.cnblogs.com/adeveloper/p/13022065.html