传智博客
快捷导航
蚂蚁部落
蚂蚁部落 网站首页 前端教程 JS教程 查看内容

栏目导航

≡基础知识≡

≡操作符≡

≡语句≡

≡函数≡

≡面向对象≡

≡对象≡

≡事件≡

≡事件对象≡

≡操作DOM方法≡

≡操作DOM属性≡

≡操作table表格≡

≡操作select控件≡

≡操作cookie≡

≡浏览器对象模型≡

≡进阶≡

垃圾回收的标记清除算法详解

2017-7-25 13:02| 发布者: antzone| 查看: 1075| 评论: 0|来自: 蚂蚁部落

传智播客

像javascript这样的语言有内置的垃圾回收机制,它的出现可以使我们免去了考虑内存分配和释放的操作问题。从而我们可以花费更多的精力去完成功能的实现。但是对于它的了解还是必不可少的,这样我们可以写出更为优化的代码。

当前最基本的垃圾回收算法有四种:

(1).标记-清除算法(mark-sweep)。

(2).标记-压缩算法(mark-compact)。

(3).复制算法(copying)。

(4).引用计数算法(reference counting)。

当前浏览器的垃圾回收机制通常是由上述几种算法混合而成。本章节就单独介绍比较流行的标记清除算法。

一.基本概念:

在垃圾回收的算法中,经常会出现mutator和collector两个名称,下面就对它做一下简单介绍。

(1).collector:指的就是垃圾收集器。

(2).mutator:指的是垃圾收集器之外的部分,比如当前的应用程序。它的功能是创建新对象,或者在内存读写内容。

(3).mutator roots:mutator根对象,通常是分配在堆内存之外,可以直接被mutator直接访问到的对象,一般是指静态/全局变量。

(4).可到达对象:所谓的可到达对象就是从根对象开始遍历,可以访问到的对象,也就是mutator(应用程序)正在使用的对象。

二.算法原理:

标记清除算法从名称上看,可以拆分为两部分:标记(mark)和清除(sweep)。

此算法可以分为两个阶段,一个是标记阶段,一个是清除阶段,下面就分别做一下介绍。

(1).标记阶段:

在此阶段,垃圾回收器会从mutator(应用程序)根对象开始遍历。

每一个可以从根对象访问到的对象都会被添加一个标识,于是这个对象就被标识为可到达对象。

(2).清除阶段:

在此阶段中,垃圾回收器,会对堆内存从头到尾进行线性遍历,如果发现有对象没有被标识为可到达对象,那么就将此对象占用的内存回收,并且将原来标记为可到达对象的标识清除,以便进行下一次垃圾回收操作。

图示如下:

a:3:{s:3:\"pic\";s:43:\"portal/201704/10/130136v16uyge0d6naeodd.png\";s:5:\"thumb\";s:0:\"\";s:6:\"remote\";N;}

在标记阶段,从跟对想1可以访问到B,从B又可以访问到E,那么B和E都是可到达对象,同样的道理,F、G、J和K都是可到达对象。在回收阶段,所有未标记为可到达的对象都会被垃圾回收器回收。

特别说明:在垃圾回收阶段,应用程序的执行会暂停,等待回收执行完毕后,再恢复程序的执行。

三.何时开始垃圾回收:

在使用标记清除算法时,未引用对象并不会被立即回收.取而代之的做法是,垃圾对象将一直累计到内存耗尽为止.当内存耗尽时,程序将会被挂起,垃圾回收开始执行。

四.垃圾回收伪代码表示:

[JavaScript] 纯文本查看 复制代码运行代码
New():
  //分配新的内存到ref指针
  ref <- allocate()  
  if ref == null
    //内存不足,则触发垃圾收集
    collect()  
  ref <- allocate()
  if ref == null
    //垃圾收集后仍然内存不足,则抛出Out of Memory错误
    throw "Out of Memory"   
  return ref
 
  atomic collect():
  markFromRoots()
  sweep(HeapStart,HeapEnd)

上面的代码表示了垃圾回收是如何被触发的。

[JavaScript] 纯文本查看 复制代码运行代码
markFromRoots():
  worklist <- empty
  //遍历所有mutator根对象
  for each fld in Roots
    ref <- *fld
      //如果它是可达的而且没有被标记的,直接标记该对象并将其加到worklist中
      if ref != null && isNotMarked(ref)
        setMarked(ref)
        add(worklist,ref)
        mark()
mark():
  while not isEmpty(worklist)
    //将worklist的最后一个元素弹出,赋值给ref
    ref <- remove(worklist)
    //遍历ref对象的所有指针域,如果其指针域(child)是可达的,直接标记其为可达对象并且将其加入worklist中
    for each fld in Pointers(ref)
      //通过这样的方式来实现深度遍历,直到将该对象下面所有可以访问到的对象都标记为可达对象。
      child <- *fld
        if child != null && isNotMarked(child)
          setMarked(child)
          add(worklist,child)

上面的是mark标记的算法。

[JavaScript] 纯文本查看 复制代码运行代码
sweep(start,end):
    scan <- start
   while scan < end
       if isMarked(scan)
          setUnMarked(scan)
      else
          free(scan)
      scan <- nextObject(scan)

上面的代码表示的是垃圾回收的sweep阶段。

五.标记清除算法的缺点:

垃圾收集后有可能会造成大量的内存碎片,像上面的图片所示,垃圾收集后内存中存在三个内存碎片,假设一个方格代表1个单位的内存,如果有一个对象需要占用3个内存单位的话,那么就会导致Mutator一直处于暂停状态,而Collector一直在尝试进行垃圾收集,直到Out of Memory。

1

鲜花

握手

雷人

路过

鸡蛋

刚表态过的朋友 (1 人)

最新评论

关于我们|手机版|小黑屋| ( 鲁ICP备10022556号-3 )

GMT+8, 2017-11-19 01:23 , Processed in 0.066328 second(s), 22 queries .

Powered by Discuz! X3.2 Licensed

Copyright © 2012-2017 Design: 蚂蚁部落

返回顶部