如何为自定义标记-清除收集器安排收集周期？

Question

我为一台Postscript虚拟机编写了一个简单的垃圾回收器，但是我难以设计出一个合适的规则来判断何时进行垃圾回收（当空闲列表太短时？）和何时分配新空间（当有大量可用空间时？）。

到目前为止，我已经采用了自下而上的方式，但这个问题涉及到顶层设计。所以我感觉自己站在不稳定的地面上。所有对象都是通过操作函数进行管理和访问的，因此这是一个在C语言内部实现的垃圾回收器，而不是针对C语言的垃圾回收器。

主要的分配器函数被称为gballoc：

unsigned gballoc(mfile *mem, unsigned sz) {
    unsigned z = adrent(mem, FREE);
    unsigned e;
    memcpy(&e, mem->base+z, sizeof(e));
    while (e) {
        if (szent(mem,e) >= sz) {
            memcpy(mem->base+z, mem->base+adrent(mem,e), sizeof(unsigned));
            return e;
        }
        z = adrent(mem,e);
        memcpy(&e, mem->base+z, sizeof(e));
    }
    return mtalloc(mem, 0, sz);
}

如果不知道所有类型和函数是什么意思，我确信这个内容看起来像胡言乱语，因此在这里提供该函数的伪代码：

gballoc
    load free list head into ptr
    while ptr is not NULL
        if free element size is large enough
            return element, removed from list
        next ptr
    fallback to allocating new space

所以，这是一个简单的“首次适配”算法，没有雕刻（但分配保留其大小；因此，用于小对象的大空间可以再次用于较大的对象）。

但是我什么时候应该调用collect()？

编辑： 代码的其余部分和相关模块已发布在comp.lang.postscript中的线程中： http://groups.google.com/group/comp.lang.postscript/browse_thread/thread/56c1734709ee33f1#

- luser droog

Answer 1

有几种适用的哲学：

• 在分配时将垃圾回收作为最后一招避免扩大堆。这可能是最常见的策略。
• 定期进行垃圾回收，例如每100次分配或释放一次。在某些情况下，这可能通过不让碎片化失控来减少垃圾回收的总体工作量。
• 不进行任何垃圾回收。对于短暂或简单的程序，这始终是一种可能的策略。

作为垃圾回收的开发人员，将选择策略的权利交给应用程序可能是可取的，因为它可能知道哪种策略最有效。当然，如果它没有偏好，您应该选择默认值。

- wallyk

---

是的，有一个名为vmreclaim的用户级运算符，可以（启用/禁用）自动收集，或请求立即收集。因此，您的第三个选项已经在规范中涵盖。定期似乎是现在一个合理的选择。我担心最后一招策略会导致启动抖动，除非有一个慷慨的初始池。 - luser droog

我本来希望能够获得更多的答案供选择；但是现在这已经给了我所需要的，也为将来的思考提供了素材。因此我接受了。谢谢。 - luser droog

Answer 2

这里是原始代码中包含的定期收集策略：

enum { PERIOD = 10 };

unsigned gballoc(mfile *mem, unsigned sz) {
    unsigned z = adrent(mem, FREE);
    unsigned e;
    static period = PERIOD;
    memcpy(&e, mem->base+z, sizeof(e));
try_again:
    while (e) {
        if (szent(mem,e) >= sz) {
            memcpy(mem->base+z, mem->base+adrent(mem,e), sizeof(unsigned));
            return e;
        }
        z = adrent(mem,e);
        memcpy(&e, mem->base+z, sizeof(e));
    }
    if (--period == 0) {
        period = PERIOD;
        collect(mem, 0);
        goto try_again;
    }
    return mtalloc(mem, 0, sz);
}

- luser droog

---

不要告诉任何人，但这实际上并不起作用。collect的第二个参数应该是一个包含根集的堆栈结构的地址。但我将不得不将其变为指向多个堆栈的特殊实体范围。并为不同的内存文件使用不同的集合。但至少调用已经就位了。 - luser droog