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

I've written a simple garbage collector for a Postscript virtual machine, and I'm having difficulty designing a decent set of rules for when to do a collection (when the free list is too short?) and when to allocate new space (when there's a lot of space to use?).

我为Postscript虚拟机编写了一个简单的垃圾收集器，而且我在为何时进行收集(当空闲列表太短?)以及何时分配新空间(当有大量空间可使用时?)

I've written bottom-up so far, but this question involves top-level design. So I feel I'm on shaky ground. All objects are managed and access is only through operator functions, so this is a collector in C, not for C.

到目前为止，我已经从下往上写了，但是这个问题涉及到顶层设计。所以我觉得我的立足点不稳固了。所有对象都是通过操作符来管理和访问的，所以这是C中的收集器，而不是C。

The primary allocator function is called gballoc:

主要的分配器函数称为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);
}

I'm sure it's gibberish without knowing what all the types and functions mean, so here's pseudocode of the same function:

我肯定它是胡言乱语，不知道所有类型和函数的含义，所以这里是同一个函数的伪代码:

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

So it's a simple "first-fit" algorithm with no carving (but allocations retain their size; so a large space reused for a small object can be reused for a large object again, later).

这是一种简单的“首次匹配”算法，没有切割(但分配保留了它们的大小;因此，为小对象重用的大空间可以稍后再为大对象重用)。

But when should I call collect()?

但是我什么时候打电话给collect()?

Edit: The rest of the code and related modules have been posted in comp.lang.postscript, in the thread: http://groups.google.com/group/comp.lang.postscript/browse_thread/thread/56c1734709ee33f1#

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

2 个解决方案

#1

There are several applicable philosophies:

有几种适用的哲学:

Do garbage collection as last-ditch avoidance of expanding the heap during an allocation. This is probably the most common strategy.
将垃圾收集作为在分配期间避免扩展堆的最后手段。这可能是最常见的策略。
Do garbage collection periodically, like every hundredth allocation or deallocation. In some situations, this might decrease the overall effort of garbage collection by not letting fragmentation get out of hand.
定期进行垃圾收集，就像每100次分配或释放一样。在某些情况下，由于不让碎片失控，这可能会减少垃圾收集的总体工作量。
Don't do any garbage collection. Always a possible strategy, especially for short-lived or simple programs.
不要做任何垃圾收集。总是可能的策略，特别是对于短期或简单的程序。

As a developer of garbage collection, it might be desirable to give the choice of strategy to the application since it might know which will be most effective. Of course, if it doesn't have a preference, you should choose a default.

作为垃圾收集的开发人员，最好给应用程序选择策略，因为它可能知道哪种策略最有效。当然，如果它没有首选项，您应该选择默认。

#2

Here is the periodic collection strategy incorporated into the original code:

以下是纳入原始守则的定期收集策略:

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);
}

#1