CSAPP:垃圾回收

(一)Mark&Sweep Garbage Collectors

一个Mark&Sweep Gabage Collector包含mark阶段和sweep阶段,首先是mark阶段

void mark(ptr p) 
{
//判断p指针是否指向一块有效的block区域,若是,该block区域head的指针
if ((b = isPtr(p)) == NULL)
return;
//判断该Header是否已经被标记
if (blockMarked(b))
return;
//若无标记,进行标记,并且把该block的每一个字节进行递归mark
markBlock(b);
len = length(b);
for (i=0; i < len; i++)
mark(b[i]);
return;
}

过程:

如图第一次传入的p指针是root point,即一个在堆区外指向堆区内的指针(就是我们通常定义的指针),这个指针指向堆区内的block1,我们通过这个指针进入到堆区内mark该block,由于block1可能指向其他的block,因此我们进行搜索1,2,3,4区域,若该区域是一个指针则进入指向区域,于是我们在区域2搜索到了block2,同理递归搜索到block3..以此类推直到搜索不到。像block4,block5一个root point连接的block就不会被mark,因此他们就是garbage.

mark操作:

如图的mark操作实际上是在Head的第二位置1,Head是存储的是该block的size,由于block的地址是对齐8,因此每一个block长度至少为8,那么size的低三位则永远为0,因此可供我们使用。一般第一位存储的是该block是否被分配。

然后是sweep阶段

void sweep(ptr b, ptr end) 
{
//b为堆区开头的block,end为堆区的结尾
while (b < end)
 {
//该block是否被标记,若是则解除标记
if (blockMarked(b))
unmarkBlock(b);
//该block是否被分配,若被分配且在没有被标记,说明为garbage,回收
else if (blockAllocated(b))
free(b);
//下一个block
b = nextBlock(b);
}
return;
}

过程:

如图从b开始搜索block1的head,判断是否被标记,是否为garbage,然后nextBlock跳到block2,继续搜索直到end


两个阶段后回收完成。

(二)Conservative Mark&Sweep for C Programs

看似没问题的流程却在c语言的实现中存在着两个问题,问题主要出现在mark阶段:

1.isPtr(p)在mark阶段判断传入的指针p是否指向一块有效的block,但是我们如何确保p是一个指针而只是一个大一点的数,像0x11000,可能只是一个普通的数也有可能是指针,但是isPtr无法区分。(在java中,指针不是由用户管理的,因此他清楚的知道自己有哪一些指针)

2.如何确保p指向的位置是block的Payload区域以及如果p指向的是payload的中间我们如何获取该block的头部

我们可以看到一个指针指向一块block,他使用的只是其中的Payload区域,其他区域并不是用户在使用,他们是为了内存管理而生的。我们可以想象如果p指向的是payload中间的某一个地方,我们如何去获取他的头部,这是一个难题,因为我们不可能知道p偏离头部偏离了多少,无法获取头部我们也无法进行标记。

Solution:

如图,我们可以通过给每一个block建立平衡二叉树来解决这问题,每个block都增加left和right指针,left指向地址比自己小的block,right指向地址比自己大的block,Head存储着size,传入p在二叉树上进行搜索:

当addr<=p<=addr+size则标记该块。

参考:

1.[CSAPP笔记][第九章虚拟存储器][吐血1500行]

2.CSAPP

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇