在JVM垃圾回收mark-sweep算法中，sweep过程的实质是什么？

Question

在mark-sweep算法中，被标记为垃圾的对象，就会被sweep清除。

那么，这个“清除”这个动作，详细的解释一下它是怎么进行的呢？也就是说，在“清除”的这个过程中，这个对象所在的内存数据，发生了哪些变化呢？

这个问题延伸一下：对于一块内存区域，JVM是怎么知道这块内存是否是可用可分配，没有被其他对象占用的呢？

我不知道问题的答案，但有两个想法：
1、在一段连续内存的起始位置做一个标记，记录它的长度和可用状态。这样做的问题是，每次需要分配内存，就要挨个遍历下去，效率很低，所以应该不太可能。
2、把内存中的所有可用内存的地址和长度存在一个集合里面，这样就可以很清晰的知道哪些地方有空余的内存了。这样做的问题在于，有可能这个集合会变得很大。通过mark-compact整理内存之后，可以减小这个集合。

Answer 1

JVM中分配内存使用了两种算法：

1. 指针碰撞：所有的存储空间分为两部分，一部分是空闲，一部分是占用，需要分配空间的时候，只需要计算指针移动的长度即可。
2. free-list:虚拟机维护了一个空闲列表，需要分配空间的时候去查该空闲列表进行分配并对空闲列表做更新

如果是使用mark-sweep算法清理，会使用第2种分配方式，把清理的内存加到空闲列表就好了，CMS就是用的mark-sweep + free-list