18

通过确定性，我含糊其词的意思是可以用于关键的实时软件，如航空航天飞行软件。垃圾收集器（以及与此相关的动态内存分配）是飞行软件中的大禁忌，因为它们被认为是非确定性的。但是，我知道对此正在进行研究，所以我想知道这个问题是否已经解决。

我还在问题中包括了任何对它们的使用方式施加限制的垃圾收集算法。

4

10 回答 10

17

我知道我可能会对此回复投下很多反对票，但是如果您一开始就已经在尝试避免动态内存，因为您说这是不行的，那您为什么还要使用 GC？我永远不会在可预测的运行时速度是主要关注点的实时系统中使用 GC。我会尽可能避免使用动态内存，因此开始时动态对象非常非常少，然后我会手动处理非常少的动态分配，因此我可以 100% 控制何时释放某些内容以及它在哪里释放。毕竟不仅 GC 不是确定性的，free() 和 malloc() 一样没有确定性。没有人说 free() 调用只需将内存标记为空闲。它不妨尝试将围绕已释放的较小的空闲内存块组合成一个大的空闲内存块，这种行为不是确定性的，

在一个关键的实时系统中，您甚至可以用不同的实现替换系统标准 malloc()/free()，甚至可能编写自己的实现（这并不像听起来那么难！我以前这样做只是为了好玩其中）最具有确定性。对我来说，GC 是一件很方便的事情，它让程序员不再专注于复杂的 malloc()/free() 规划，而是让系统自动处理这个问题。它有助于进行快速软件开发，并节省数小时的调试工作查找和修复内存泄漏。但就像我永远不会在操作系统内核中使用 GC 一样，我也永远不会在关键的实时应用程序中使用它。

如果我需要更复杂的内存处理，我可能会编写我自己的 malloc()/free() 来按需要（并且最具确定性）工作，并在其上编写我自己的引用计数模型。引用计数仍然是手动内存管理，但比仅使用 malloc()/free() 要舒服得多。它不是超快的，但具有确定性（至少增加/减少引用计数器的速度是确定性的），除非您可能有循环引用，否则如果您在整个应用程序中遵循保留/释放策略，它将捕获所有死内存。唯一不确定的部分是您不知道调用 release 是否只会减少引用计数器或真正释放对象（取决于引用计数是否为零），但您可以通过提供延迟实际释放说“releaseWithoutFreeing”的功能 ，它将引用计数器减一，但即使它达到零，它也不会释放（）对象。你的 malloc()/free() 实现可以有一个函数“findDeadObjects”，它搜索所有保留计数器为零的对象，这些对象还没有被释放并释放它们（稍后，当你不那么关键时有更多时间处理此类任务的代码的一部分）。由于这也不是确定性的，您可以像“findDeadObjectsForUpTo(ms)”一样限制它可能使用的时间量，ms 是它可能用于查找和释放它们的毫秒量，这个时间会尽快返回量子已被使用，因此您不会在此任务上花费太多时间。你的 malloc()/free() 实现可以有一个函数“findDeadObjects”，它搜索所有保留计数器为零的对象，这些对象还没有被释放并释放它们（稍后，当你不那么关键时有更多时间处理此类任务的代码的一部分）。由于这也不是确定性的，您可以像“findDeadObjectsForUpTo(ms)”一样限制它可能使用的时间量，ms 是它可能用于查找和释放它们的毫秒量，这个时间会尽快返回量子已被使用，因此您不会在此任务上花费太多时间。你的 malloc()/free() 实现可以有一个函数“findDeadObjects”，它搜索所有保留计数器为零的对象，这些对象还没有被释放并释放它们（稍后，当你不那么关键时有更多时间处理此类任务的代码的一部分）。由于这也不是确定性的，您可以像“findDeadObjectsForUpTo(ms)”一样限制它可能使用的时间量，ms 是它可能用于查找和释放它们的毫秒量，这个时间会尽快返回量子已被使用，因此您不会在此任务上花费太多时间。当您处于代码中不太重要的部分，有更多时间处理此类任务时）。由于这也不是确定性的，您可以像“findDeadObjectsForUpTo(ms)”一样限制它可能使用的时间量，ms 是它可能用于查找和释放它们的毫秒量，这个时间会尽快返回量子已被使用，因此您不会在此任务上花费太多时间。当您处于代码中不太重要的部分，有更多时间处理此类任务时）。由于这也不是确定性的，您可以像“findDeadObjectsForUpTo(ms)”一样限制它可能使用的时间量，ms 是它可能用于查找和释放它们的毫秒量，这个时间会尽快返回量子已被使用，因此您不会在此任务上花费太多时间。

于 2008-10-21T12:17:58.550 回答
10

Metronome GC和BEA JRockit是我所知道的两个确定性 GC 实现（都用于 Java）。

于 2008-10-20T05:34:10.143 回答
6

碰巧正在通过 Stack Overflow 搜索并注意到这个相当老的帖子。

Jon Anderson 提到了 JamaicaVM。由于这些帖子已经发布了 4 年多，我认为回复此处发布的一些信息很重要。

我为 aicas 工作，它是 JamaicaVM、JamaicaCAR 和 Veriflux 的开发人员和营销人员。

JamaicaVM 确实有一个硬实时垃圾收集器。它是完全抢先的。实时操作系统所需的完全相同的行为。尽管抢占延迟取决于 CPU 速度，但假设在 Ghz 级处理器上，垃圾收集器的抢占时间小于 1 微秒。有一个 32 位单核版本，每个进程地址空间支持高达 3 GB 的内存。有一个 32 位多核版本，支持每个进程地址空间和多核 3 GB 内存。还有 64 位单核和多核版本，每个进程地址空间支持高达 128 GB 的内存。垃圾收集器的性能与内存大小无关。针对有关运行 GC 完全耗尽内存的响应之一，对于硬实时系统，您不会设计您的程序来做到这一点。尽管实际上您可以在这种情况下使用硬实时 GC，但您必须考虑到您的应用程序可能无法接受的最坏情况执行时间。

相反，正确的方法是分析您的程序以获得最大内存分配，然后将硬实时垃圾收集器配置为在所有先前分配期间增量释放块，以便描述的特定场景永远不会发生。这称为线程分布式、工作节奏的垃圾收集。

Siebert 博士关于硬实时垃圾收集器的书描述了如何实现这一点，并提供了一个正式的证据，证明垃圾收集器将跟上应用程序，而不是成为 O(N) 操作。

了解实时垃圾收集意味着几件事非常重要：

  1. 垃圾收集器是可抢占式的，就像任何其他操作系统服务一样
  2. 从数学上可以证明，垃圾收集器会跟上，这样内存就不会因为一些内存还没有被回收而耗尽。
  3. 垃圾收集器不会对内存进行碎片化，只要有可用内存，内存请求就会成功。
  4. 此外，您将需要它成为具有优先级反转保护、固定优先级线程调度程序和其他功能的系统的一部分。有关这方面的一些信息，请参阅 RTSJ。

尽管安全关键应用程序需要硬实时垃圾收集，但它也可以用于任务关键型应用程序和通用 Java 应用程序。使用硬实时垃圾收集器没有固有的限制。对于一般用途，您可以期待更顺畅的程序执行，因为没有长时间的垃圾收集器暂停。

于 2012-06-23T23:36:47.670 回答
3

对我来说，100% 实时的 Java 在很大程度上仍然是一项屡试不爽的技术，但我并不声称自己是专家。

我建议阅读这些文章 - Cliff Click 博客。他是 Azul 的架构师，几乎编写了所有标准 1.5 Java 并发类等...仅供参考，Azul 专为需要非常大堆大小的系统而设计，而不仅仅是标准 RT 要求。

于 2008-10-20T08:08:56.807 回答
2

它不是 GC，但有简单的 O(1) 固定大小的块分配/释放方案，您可以使用它来进行简单的使用。例如，您可以使用固定大小块的空闲列表。

struct Block {
   Block *next;
}

Block *free_list = NULL; /* you will need to populate this at start, an 
                          * easy way is to just call free on each block you 
                          * want to add */

void release(void *p) {
    if(p != NULL) {
        struct Block *b_ptr = (struct Block *)p;
        b_ptr->next = free_list;
        free_list = b_ptr;
    }
}

void *acquire() {
    void *ret = (void *)free_list;
    if(free_list != NULL) {
        free_list = free_list->next;
    }
    return ret;
}

/* call this before you use acquire/free */
void init() {
    /* example of an allocator supporting 100 blocks each 32-bytes big */
    static const int blocks = 100;
    static const int size = 32;
    static unsigned char mem[blocks * size];
    int i;
    for(i = 0; i < blocks; ++i) {
        free(&mem[i * size]);
    }
}

如果您有相应的计划，您可以将您的设计限制为只有几个特定大小以进行动态分配，并为每个潜在大小设置一个 free_list。如果您使用的是 c++，您可以实现一些简单的东西，例如 scoped_ptr（对于每个大小，我会使用模板参数）来获得更简单但仍然 O(1) 的内存管理。

唯一真正需要注意的是，您将无法避免双重释放，甚至不小心将 ptr 传递给不是来自获取的释放。

于 2008-11-16T07:59:18.980 回答
2

Sun 已经广泛记录了他们的实时垃圾收集器，并提供了您可以在此处自己运行的基准测试。其他人提到了 Metronome，这是另一个主要的生产级 RTGC 算法。许多其他 RT JVM 供应商都有自己的实现——请参阅我的供应商列表，其中大多数都提供了大量文档。

如果您对航空电子/飞行软件特别感兴趣，我建议您看看aicas，这是一家专门针对航空电子行业进行营销的 RTSJ 供应商。 Siebert 博士（aicas CEO）的主页列出了一些学术出版物，其中详细介绍了 PERC 的 GC 实施。

于 2009-04-10T02:42:25.500 回答
1

您可能会对以下博士论文 CMU-CS-01-174 - Scalable Real-time Parallel Garbage Collection for Symmetric Multiprocessors有一些运气。

于 2008-10-20T08:35:50.887 回答
1

实时意味着响应时间有保证的上限。这意味着在您交付结果之前您可以执行的指令的上限。这也对您可以触摸的数据量设置了上限。如果您不知道您将需要多少内存，则极有可能您将有一个无法给出其执行时间上限的计算。Otoh，如果您知道计算的上限，您也知道它触及了多少内存（除非您真的不知道您的软件做了什么）。因此，您对代码的了解程度足以消除对 GC 的需求。

有一些特性，比如 RT-Java 中的区域，允许超越局部和全局（静态）变量的表达。但是它们不会免除您管理分配的内存的义务，因为否则您无法保证下一次分配不会因为内存资源不足而失败。

诚然：我对自称为“实时垃圾收集器”的东西有些怀疑。当然，如果您假设每个分配都运行一个完整的集合，那么任何 GC 都是实时的（这仍然不能保证它之后会成功，因为可能会发现所有内存块都是可访问的）。但是对于任何承诺较低分配时间限制的 GC，请考虑其在以下示例代码中的性能：

// assume that on `Link` object needs k bytes:
class Link {
    Link next = null;
    /* further fields */
    static Link head = null;
}

public static void main (String args) {
    // assume we have N bytes free now
    // set n := floor (N/k), assume that n > 1

    for (int i = 0; i < n; i ++) {
        Link tmp = new Link ();
        tmp.next = Link.head;
        Link.head = tmp;
    } 
    // (1)
    Link.head = Link.head.next; // (2)
    Link tmp = new Link ();  // (3)
}
  • 在第 (1) 点，我们只有不到 k 字节的空闲空间（分配另一个 Link对象会失败），并且 Link到目前为止分配的所有对象都可以从该 Link.static Link head字段开始访问。

  • 在点 (2)，

    • (a) 以前列表中的第一个条目现在无法访问，但是
    • (b) 就内存管理部分而言，它仍然被分配。

  • 在第 (3) 点，分配应该成功，因为 (2a) - 我们可以使用以前的第一个链接 - 但是，由于 (2b)，我们必须启动 GC，最终将遍历 n-1 个对象，因此运行时间为 O(N)。

所以，是的，这是一个人为的例子。但是声称对分配有限制的 GC 也应该能够掌握这个例子。

于 2009-03-07T11:08:37.703 回答
1

我知道这篇文章有点过时了，但我做了一些有趣的研究，并希望确保它得到更新。

Azul Systems "Zing JVM" 和 JRocket 可以提供确定性 GC。Zing 带有一些非常有趣的附加功能，现在“100% 基于软件”（可以在 x86 机器上运行）。不过，它目前仅适用于 Linux ...

价格：如果您使用的是 Java 6 或之前的版本，Oracle 现在收取 300% 的升级费用并强制支持此功能（每个处理器 15,000 美元和 3,300 美元的支持）。Azul，据我所知，大约是 10,000 - 12,000 美元，但按物理机收费，而不是核心/处理器。此外，该过程按数量分级，因此您利用的服务器越多，折扣越深。我与他们的谈话表明他们非常灵活。Oracle 是永久许可，而 Zing 是基于订阅的……但如果您算一算并添加 Zing 具有的其他功能（请参阅下面的差异）。

您可以通过迁移到 Java 7 来降低成本，但会产生开发成本。鉴于 Oracle 的路线图（每 18 个月左右发布一个新版本），以及他们历来只免费提供最新版本和一个较旧版本的 Java SE 更新的事实，“免费”期限预计从最初的 GA 开始为 3 年如果有任何主要版本，请发布。由于最初的 GA 版本通常在 12 到 18 个月内不会在生产中采用，并且将生产系统迁移到新的主要 Java 版本通常会带来巨大的成本，这意味着 Java SE 支持费用将在初始部署后 6 到 24 个月之间开始达到.

显着差异：JRocket 在 RAM 方面仍然存在一些可扩展性限制（尽管比以前有所改进）。您可以通过一些调整来改善您的结果。Zing 设计了他们的算法以允许连续、并发、压缩（不停止世界暂停，也不需要“调整”）。这使得 Zing 可以在没有理论上的内存上限的情况下进行扩展（他们正在做 300+ GB 堆而不会遭受停止世界或崩溃的痛苦）。谈论范式改变者（想想对大数据的影响）。Zing 对锁定进行了一些非常酷的改进，通过一些工作使其具有惊人的性能（如果调整，平均可以达到亚毫秒级）。最后，它们可以查看生产中的类、方法和线程行为（无开销）。在考虑更新时，我们认为这可以节省大量时间，补丁和错误修复（例如泄漏和锁定）。这实际上可以消除在开发/测试中重新创建许多问题的需要。

我发现的 JVM 数据的链接：

JRocket确定性GC

Azul 演示 - 没有抖动的 Java

Azul / MyChannels 测试

于 2012-12-12T17:26:51.110 回答
0

我知道 azul 系统有一个 jvm，其 GC 是硬件辅助的。它还可以同时运行并非常快速地收集大量数据。

不确定它的确定性如何。

于 2008-10-20T05:18:59.647 回答