在前一篇文章中,我们只是瞎扯一下垃圾回收。对垃圾回收的中的三大算法,标记-清除,引用计数,GC复制算法,并没有进行详细地描述。在论述这三大算法之前,我们先扯一扯GC中的基本概念,搞清楚基本概念,对理解垃圾回收算法就会容易一些。当然GC本来就是一个比较复杂的东西。

我们先看下面的一张图

在GC中,对应上图的,分别是 Heap(堆),Object(对象)Mutator(突变体),Stack(栈),Pointer(指针),Root(根)

对象

对象在面向对象编程中,意味着“具有属性和行为的食物”,但是在GC的世界中,对象说的是“通过应用程序利用的数据的集合”。 对象配置在内存空间里。GC根据情况将配置好的对象进行移动或销毁操作。对象是GC的基本单位。对象一般由头(header)和域(field)构成。

我们将对象中保存对象本身信息的部分称为“头”,头主要含有下面的信息

  • 对象的大小
  • 对象的种类

如果不清楚对象的大小和种类,那么就会发生问题,例如无法知道内存中存储对象的边界。头中存有运行GC的需要的信息,根据算法不同,信息也不同。对于标记-清除算法,是在对象的头部中设置1个flag来记录对象是否已标记,从而管理各个对象。

把对象使用者在对象中可访问的部分称为“域”。我们把域想象成C语言中的结构体的成员。对象使用者会引用或替换对象的阈值。此外,对象使用者基本上无法直接更改头的信息。

域中的数据类型大致分为2种。

  • 指针
  • 非指针

指针是指向内存空间中某块区域的值。即使像java,javascript这样的没有使用指针的编程语言,语言处理程序内部也用到指针。非指针指的是在编程中直接使用值本身。数值,字符以及真假值都是非指针。

对象的结构是

对象 = 对象头+域1+域2

指针

通过GC,对象会被保留或销毁,在这过程中起关键作用的是指针。GC是根据对象的指针指向去搜寻其他对象的。在大部分语言处理程序中,指针都默认指向对象的首地址(指针如果不指向对象首地址,GC会变得很复杂)我们在实现算法的时候,对象和指针的关系如下

我们把b,c称为对象A的子对象。对对象的子对象进行处理是GC的基本操作。

Mutator(突变体)

对象是由谁生成呢,我们一般会说是由程序生成的。mutator这个词是由Edsger Dijkstra 提出来的,意思就是改变某个东西。mutator改变的是GC对象的引用关系。我们一般说来把Mutator说成应用程序。

mutator实际上进行的操作有两种

  • 生成对象
  • 更新指针

mutator在上述的操作的时候,同时为应用程序的用户进行一些处理(数值计算,浏览网页,编辑文章等)。随着这些处理的推进,对象间的引用关系也会“改变”。在这个过程中就会产生垃圾,而负责回收这些垃圾的机制就是GC

堆指的是用于动态存放对象的空间。当mutator申请存放对象时,所需的内存空间就会从堆中分配给mutator.GC是管理堆中已分配对象的机制。一旦开始执行mutator,程序就会按照mutaor的要求在堆中存放对象。等到堆被对象占满后,GC就会启动,从而分配可用空间。如果不能分配可用空间,这个时候,我们就要扩大堆的空间。

活动对象/非活动对象

分配到内存空间中的对象中那些能通过mutator引用的对象称为“活动对象”。反过来,把分配到堆中那些不能通过程序引用的对象称为“非活动对象”。 这些非活用对象,我们称为垃圾,就是需要清除掉。当销毁非活动对象时,这些非活动对象占用的空间会得到解放,供下一个要分配的新对象使用。

当mutator需要新对象时,就会向分配器申请一个大小合适的空间。分配器则在堆空间中寻找满足要求的空间,返回给mutator. 有GC机制的语言,在生成实例的时,会内部自动分配空间。对于没有GC机制的语言如C/C++ ,这个时候程序员需要使用malloc() 和new 运算符进行手动分配。

当堆被所有活动对象占满时,这个时候运行GC也无法分配可用空间。这个时候,一般采用如下两种选择

  • 销毁至今为止的所有计算结果,输出错误信息
  • 扩大堆,分配可以空间。

一般在堆情况没有特殊限制的情况下,我们是扩大堆。

根(root)

在GC的世界里,根是指向对象的指针的“起点”部分。这些都是能通过mutator直接引用的空间。我们看下面的伪代码

$obj = Object.new //对象A
$obj.field1 = Object.new //对象B

$obj是全局变量。我们在第一行分配一个对象A,然后把$obj指向这个对象的指针。在第2行我们分配一个对象B,把$obj.field1指向对象B的指针。 在执行完之后,全局变量空间和堆如下图所示

我们可以使用$obj直接从伪代码中引用对象A,这样A是活动对象。可以通过$obj >对象A>对象B. 那么对象B也是活动对象。GC就需要保护这些对象不被销毁掉。

GC把上述这样直接或间接从全局变量空间中引用的对象视为活动对象。与全局变量空间相同,我们也可以通过mutator直接引用调用栈(call stack)和寄存器。那么,调用栈,寄存器以及全局变量空间都是根。

GC算法的评价标准

  • 吞吐量
  • 最大暂停时间
  • 堆使用效率
  • 访问的局部性

吞吐量

吞吐量(throughout)指的是“在单位时间内的处理能力”。我们看下面的图

在mutator执行的过程中,GC一共启动了3次,我们把花费的时间分别设为A,B,C.也就是说GC总共花费的时间为(A+B+C)。另一方面,我们假设在这个过程中,以GC为对象的堆的大小为HEAP_SIZE. 也就是说在大小为HEAP——SIZE的堆进行内存管理,要花费的时长为(A+B+C).这种情况下,GC的吞吐量为HEAP_SIZE/(A+B+C).

我们都喜欢吞吐量高的GC算法。但是判断各个吞吐量的好坏时不能一概而论。我们比较GC算法和GC标记-清除算法。一般来说,活动对象越少吞吐量越高。而GC算法只检查活动对象,GC标记-清除算法则会检查所有的活动和非活动对象,这个时候GC算法的吞吐量比GC标记-清除算法要高,但是如果活动对象增多,极端情况下,GC标记-清除算法比GC复制算法的吞吐量更高情况。

最大暂停时间

在GC执行的过程中,mutator会暂停执行,如上图所示,最大暂停时间指的是“因执行GC而暂停执行mutator的最长时间”。上图中B的执行时间长,这个时候最大暂停时间是B.

我们在什么情况下要重视最大暂停时间呢? 典型的例子是两足步行机器人,如果在步行过程中启动GC,这个时候对机器的控制就会暂时中断,直到GC执行完毕才能重启,在这个时候,机器人完全不能运作。这个时候,机器人会摔倒。这个时候,我们要使用最大暂停时间短的算法。

堆使用效率

GC算法的不同,堆使用效率也不同。左右堆使用效率的因素有两个。

一个是头的大小,另一个是堆的用法。

在堆中堆放的信息越多,GC的效率也就越高,吞吐量也就改善。这样看来对象的头部越小越好,这样能够存下更多的对象,堆的利用率也高。此外根据堆的用法,堆的使用效率也会出现巨大差异。GC复制算法中将堆二等分,每次只使用一半。相对而言,GC标记-清除算法和引用计数法就能利用整个堆。由于GC是自动内存管理功能,所以过量占用堆就本末倒置了。所以堆使用率也是GC算法的重要评价指标之一。但是很多时候,鱼与熊掌不可兼得,一般来说可用的堆越大,GC运行越快,相反有效地利用有限的堆,GC花费的时间就越长。这看我们的舍取了。

下一篇文章,从标记-清除算法,引用计数算法,GC复制算法一遍遍过这些算法。

发表评论

电子邮件地址不会被公开。 必填项已用*标注