理论上,是的……这是可能的。但是 GC 有一个问题:要收集垃圾,它需要知道存储在内存中的数据的布局,并且它还必须存储数据以指示内存块是否正在使用……但是布局信息与运行时共享,因为运行时需要知道对象类型(即内存布局)才能进行类型转换。
GC 是如何工作的?
GC 开始读取它知道的根对象。它获取所有引用并将它们标记为in-use。对于这些被引用的对象中的每一个,它会获取布局并从这些对象中读取更多引用,并将它们标记为正在使用……这个过程继续进行,直到没有更多的引用存在。
注:我使用了类型信息和布局信息,含义相同。
例子:
Imagine we have some object layouts:
====================================
A: { int, object, double, object }
B: { object, object }
C: { int }
Memory Data:
============
Now we need to describe what is in memory.
The following list is composed of memory positions,
and the data contained in each position.
There are 2 kinds of notation I will use:
- Address: ROOT[ list-of-root-references ]
- Address: type-identifier { object-data }
Note that each object can span multiple memory
positions from the first one.
e.g. 90: B { 0, 0 } -- this reads as
"stored at address 90: type-identifier of B followed by raw data { 0, 0 }"
- A reference is represented by a number,
that point to the memory address of the pointed object.
1: ROOT[ 90, 20, 30 ]
20: A { 1236, 30, 0.5, 60 }
30: B { 60, 70 }
40: C { 1237 }
50: A { 1238, 20, 0.8, 50 } There is a self-reference here!
60: C { 1234 }
70: A { 1234, 0, 0.7, 80 }
80: C { 1235 }
90: B { 0, 0 } Note that 0 is a null reference!
The GC need to know the layout of each object.
Otherwise it wouldn't be abled to tell
what knid of information is stored in each memory position.
Running the GC:
===============
Garbage collecting steps, to clean the memory described above:
Step 1: Get ROOT references: 2, 3, 9 and mark as 'in-use'
Step 2: Get references from 2, 3 and 9: 3, 6, 7. Note that 0 is a null reference!
Step 3: Get references from 3, 6 and 7: 6, 7, 8, and mark them.
Step 4: Get references from 6, 7, 8, and mark them: only 8!
Step 5: Get references from 8... it has none! We are finished with marking objects.
Step 6: Delete unmarked objects.
This shows what happened in each step with each object stored in the memory.
Step -> 1 2 3 4 5
Memory
20 x
30 x x
40 DELETE
50 DELETE
60 x x
70 x x
80 x x
90 x
我描述的是一个非常基本的 GC 算法。
看看三色标记……真是太棒了!这就是真正的现代 GC 的制作方式。
垃圾收集(计算机科学) - 描述了一些现代 GC 方法。
但是......关于布局的信息存储在哪里?
这个问题很重要,因为它会影响 GC 和运行时。要进行快速类型转换,类型信息必须放在引用附近或分配的内存附近。我们可以考虑将类型信息存储在分配的内存块的目录中,但是......类型转换需要访问目录,就像 new 运算符和 GC 需要删除对象时一样。
如果我们将布局信息存储在引用附近,那么对同一对象的每个引用都会重复相同的信息,以及指针本身。
例子:
To represent the memory data I will introduce the following notation:
- Address: { object-data } -- this time object type is not at the begining!
- A reference is represented by a type-identifier and an address-number,
that point to the memory address of the pointed object,
in the following format: type/number...
e.g. A/20 -- this reads as: "at address 20, there is an object of type A"
Note that: 0/0 is a null reference,
but it still requires space to store the type.
The memory would look like this:
1: ROOT[ B/90, A/20, B/30 ]
20: { 1236, B/30, 0.5, C/60 }
30: { C/60, A/70 }
40: { 1237 }
50: { 1238, A/20, 0.8, A/50 }
60: { 1234 }
70: { 1234, 0/0, 0.7, C/80 }
80: { 1235 }
90: { 0/0, 0/0 }
如果我们将布局信息存储在分配的内存块附近,那就太好了!它速度快,并且避免了重复的布局信息。
例子:
The memory looks like the first sample:
*This is the same notation used at the begining of this answer.
1: ROOT[ 90, 20, 30 ]
20: A { 1236, 30, 0.5, 60 }
30: B { 60, 70 }
40: C { 1237 }
50: A { 1238, 20, 0.8, 50 }
60: C { 1234 }
70: A { 1234, 0, 0.7, 80 }
80: C { 1235 }
90: B { 0, 0 }
到目前为止,一切都很好......但现在我想要共享内存。
我们注意到的第一件事是我们不能再将布局信息存储在分配的内存附近。
想象一个具有共享内存的数组:
例子:
I'll introduce a new notation for arrays:
type-identifier < array-length >
1: ROOT[ 20, 31 ] -- pointer 31 is invalid, destination has no type-identifier.
20: INT<5> -- info about layout of the next memory data (spans by 10 memory units)
30: 2
31: 3 -- should have type-identifier, because someone
32: 5 is pointing here!! Invalid memory!!
33: 7
34: 11
我们仍然可以尝试将布局信息放在指针旁边。现在可以使用共享内存数组:
例子:
1: ROOT[ INT<5>/30, INT<2>/31 ]
30: 2
31: 3
32: 5
33: 7
34: 11
请记住,这种方法使我们在各处重复布局信息......但这里的重点是使用更少的内存不是吗???但是为了共享内存,我们需要更多的内存来存储布局数据/指针。我们还没有甜甜圈。=(
只有一个希望:让我们降低运行时特性!
这是我的答案 - 我认为这是可能的 =>
使用内存分配目录来存储类型信息怎么样?
这可以做到,但是动态转换会受到影响,GC 也会受到影响。记得我告诉过 GC 需要访问内存目录,只是为了删除对象......好吧,现在它每次找到引用时都需要访问目录,而不仅仅是删除。我的天啊!!我们即将用这个来杀死 GC 性能,以及运行时性能。我觉得成本太高了!
<= 这是我的答案
但是......如果运行时不支持动态转换?如果编译器在编译时知道有关类型的所有信息……那么 GC 甚至不存在……它需要有关该类型的信息,因为该信息告诉它该类型使用的内存布局是什么。
看不到简单、智能的解决方案。
也许我完全错了。但我想不出比现在更好的方法了。现代 GC 比这还要复杂……我这里只介绍了基础知识,我认为,现代 GC 正在以其他方式进行优化,也就是其他更可靠的方式。
其他参考:
http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
http://www.memorymanagement.org/glossary/t.html
http://www.cs.purdue.edu/homes/sbarakat/cs456/gc-2.pdf
三色增量更新 GC:是否需要对每个堆栈进行两次扫描?