Какие детерминированные алгоритмы сбора мусора есть?

Ответ 1

Я знаю, что я могу получить много голосов за этот ответ, но если вы уже пытаетесь избежать динамической памяти, потому что вы сказали, что это не-нет, почему вы вообще используете GC? Я бы никогда не использовал GC в системе реального времени, где предсказуемая скорость выполнения является главной проблемой. Я бы избегал динамической памяти там, где это было возможно, поэтому есть очень, очень маленькие динамические объекты, и я бы обработал очень небольшое количество динамических распределений, которые у меня есть вручную, поэтому у меня есть 100% -ый контроль, когда что-то выпущено и где оно выпущенный. В конце концов, не только GC не детерминирован, free() так же мало детерминирован, как malloc(). Никто не говорит, что вызов free() просто должен отметить память как бесплатную. Он также может попытаться объединить меньшие свободные блоки памяти, окружающие свободный от одного, к большому, и это поведение не является детерминированным, и не является временем выполнения (иногда это не будет бесплатным, а malloc сделает это вместо следующего распределение, но нигде не написано, что бесплатный не должен этого делать).

В критической системе реального времени вы даже можете заменить системный стандарт malloc()/free() другой реализацией, возможно, даже написать свой собственный (это не так сложно, как кажется!) Я сделал это до того, как просто для удовольствия), который работает наиболее детерминированным. Для меня GC - простое удобство, это значит, что программисты не сосредоточены на сложной планировке malloc()/free(), и вместо этого система автоматически справляется с этим. Это помогает быстро разрабатывать программное обеспечение и экономит время отладки работы по поиску и исправлению утечек памяти. Но так же, как я никогда не использовал GC в ядре операционной системы, я бы никогда не использовал его в критическом приложении реального времени.

Если мне нужна более сложная обработка памяти, я бы, возможно, написал свой собственный malloc()/free(), который работает по желанию (и наиболее детерминирован) и напишет мою собственную модель подсчета ссылок поверх нее. Подсчет ссылок по-прежнему является ручным управлением памятью, но гораздо более удобным, чем просто использование malloc()/free(). Это не очень быстрый, но детерминированный (по крайней мере, увеличение/уменьшение счетчика рефлексии является детерминированным по скорости), и если вы не можете иметь круговые ссылки, он будет захватывать всю мертвую память, если вы будете следовать стратегии сохранения/выпуска в вашей заявке. Единственная не детерминированная часть состоит в том, что вы не будете знать, будет ли вызывающий релиз просто уменьшать счетчик ссылок или действительно освобождать объект (в зависимости от того, будет ли счетчик ссылок равен нулю или нет), но вы можете отложить фактическое освобождение, предложив чтобы сказать "releaseWithoutFreeing", что уменьшает счетчик ref на единицу, но даже если он достигнет нуля, он еще не освободит объект(). Реализация malloc()/free() может иметь функцию "findDeadObjects", которая ищет все объекты с сохраняющим счетчиком нуля, которые еще не были выпущены и освобождены (в более поздний момент, когда вы находитесь в менее критическом часть вашего кода, у которого больше времени для таких задач). Так как это также не детерминировано, вы можете ограничить время, которое оно может использовать для этого, например "findDeadObjectsForUpTo (ms)", а ms - это количество миллисекунд, которое оно может использовать для их поиска и освобождения, возвращаясь, как только это время квант, поэтому вы не потратите слишком много времени на выполнение этой задачи.

Ответ 2

Metronome GC и BEA JRockit - это два которые я знаю (как для Java).

Ответ 3

Случилось, что он просматривал Qaru и заметил этот довольно старый пост.

Джон Андерсон упомянул JamaicaVM. Поскольку эти должности уже более 4 лет, Я думаю, что важно ответить на часть информации, размещенной здесь.

Я работаю для aicas, разработчиков и маркетологов JamaicaVM, JamaicaCAR и Veriflux.

JamaicaVM имеет жесткий сборщик мусора в реальном времени. Он полностью превентивный. Точный такое же поведение требуется в операционной системе реального времени. Хотя латентность преемственности Зависит от скорости процессора, предположим, что на процессоре класса Ghz преимущественное использование сборщика мусора составляет менее 1 микросекунды. Существует 32-битная однопоточная версия, которая поддерживает до 3 ГБ памяти на адресное пространство процесса. Существует 32-битная многоядерная версия, которая поддерживает 3 ГБ памяти на адресное пространство процесса и несколько ядер. Существуют также 64-битные однорежимные и многоядерные версии, поддерживающие до 128 ГБ памяти на каждое адресное пространство процесса. Производительность сборщика мусора не зависит от размера памяти. В ответ на один из ответов о том, что GC полностью не хватает памяти, для жесткой системы реального времени вы никогда не планируете свою программу. Хотя в этом случае вы можете использовать жесткий GC реального времени, вам придется учитывать наихудшее время выполнения, которое, вероятно, не будет приемлемым для вашего приложения.

Вместо этого правильным будет анализ вашей программы для максимального распределения памяти, а затем настройка жесткого сборщика мусора в реальном времени для поэтапно свободных блоков во время всех предыдущих распределений, чтобы описанный конкретный сценарий никогда не возникал. Это известно как распределенная по потоку работающая сборка мусора.

р. Книга Зиберта о сборщиках мусора Hard Realtime описывает, как это сделать, и представляет собой официальное доказательство того, что сборщик мусора будет поддерживать работу с приложением, не становясь операцией O (N).

Очень важно понять, что сбор мусора в реальном времени означает несколько вещей:

• Сборщик мусора является превентивным, как и любая другая операционная система
• Можно математически доказать, что сборщик мусора будет поддерживать, так что память не будет исчерпана, потому что некоторая память еще не была восстановлена.
• Сборщик мусора не фрагментирует память, так что пока имеется доступная память, запрос на память будет успешным.
• Кроме того, вам понадобится это, чтобы быть частью системы с защитой приоритета инверсии, планировщиком потоков с фиксированным приоритетом и другими функциями. Обратитесь к RTSJ за информацией об этом.

Несмотря на то, что жесткая сборка мусора в реальном времени необходима для критически важных приложений, она может использоваться как критически важные приложения, так и приложения Java общего назначения. Нет никаких неотъемлемых ограничений при использовании жесткого сборщика мусора в реальном времени. Для общего использования вы можете ожидать более плавное выполнение программы, так как нет длинных пауз для сборщиков мусора.

Ответ 4

Для меня 100% Java в реальном времени по-прежнему очень популярна, но я не претендую на роль эксперта.

Я бы рекомендовал прочитать эти статьи - Блог клика Click. Он архитектор Azul, в значительной степени закодировал все стандартные 1.5 параллельные классы Java и т.д.... FYI, Azul предназначен для систем, требующих очень больших размеров кучи, а не только стандартных требований RT.

Ответ 5

Это не 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]);
    }
}

Если вы планируете соответственно, вы можете ограничить свой дизайн только несколькими конкретными размерами для динамического распределения и иметь свободный_list для каждого потенциального размера. Если вы используете С++, вы можете реализовать что-то простое, например scoped_ptr (для каждого размера, я бы использовал параметр шаблона) для упрощения управления памятью O (1).

Единственное реальное предостережение - это то, что у вас не будет защиты от двойных освобождений или даже случайного прохождения ptr, чтобы освободить, который не пришел от приобретения.

Ответ 6

Sun широко документировала сборщик мусора в реальном времени и предоставила тесты, которые вы можете запустить для себя здесь. Другие упоминали Metronome, который является другим основным алгоритмом RTGC производства. Многие другие производители JVM RT имеют свои собственные реализации - см. Мой список поставщиков здесь, и большинство из них предоставляют обширную документацию.

Если ваш интерес особенно касается авионики/программного обеспечения полета, я предлагаю вам взглянуть на aicas, поставщика RTSJ, который специально рынки для индустрии авионики. Dr. На главной странице Siebert (aicas CEO) перечислены некоторые академические публикации, в которых подробно рассказывается о реализации PERC GC.

Ответ 7

Возможно, вам повезло со следующей докторской диссертацией CMU-CS-01-174 - Масштабируемая сборка параллельных мусора в режиме реального времени для симметричных многопроцессоров.

Ответ 8

В реальном времени означает гарантированную верхнюю границу времени отклика. Это означает верхнюю границу инструкций, которые вы можете выполнить, пока не получите результат. Это также ограничивает количество данных, которые вы можете коснуться. Если вы не знаете, сколько памяти вам понадобится, крайне вероятно, что у вас будет вычисление, для которого вы не можете дать верхний предел времени выполнения. Отох, если вы знаете верхнюю границу своих вычислений, вы также знаете, сколько памяти коснется ее (если вы действительно не знаете, что делает ваше программное обеспечение). Таким образом, объем знаний, которые у вас есть о вашем коде, устраняет необходимость в GC.

Есть функции, такие как регионы в RT-Java, которые допускают выразительность за пределами локальных и глобальных (статических) переменных. Но они не освободят вас от обязанности управлять выделенной вами памятью, потому что в противном случае вы не можете гарантировать, что следующее предстоящее распределение не сработает из-за нехватки ресурсов памяти.

По общему признанию: я несколько подозрительно относился к вещам, которые называют себя "сборщиками мусора в реальном времени". Конечно, любой GC - это реальное время, если вы предполагаете, что в каждом распределении выполняется полная коллекция (которая по-прежнему не гарантирует, что она будет успешной после этого, поскольку все блоки памяти могут оказаться доступными). Но для любого GC, который promises имеет более низкую временную привязку при распределении, рассмотрите его производительность в следующем примере кода:

// 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, который утверждает, что имеет ограничение на распределение, должен также освоить этот пример.

Ответ 9

Я знаю, что этот пост немного устарел, но я сделал несколько интересных исследований и хочу убедиться, что это обновлено.

Детерминированный GC может предлагаться Azul Systems "Zing JVM" и JRocket. Zing поставляется с некоторыми интересными добавленными функциями и теперь "на 100% основан на программном обеспечении" (может работать на машинах x86). Это только для Linux в это время, хотя...

Цена: Если вы находитесь на Java 6 или до того, как Oracle теперь заряжает 300% и повышает поддержку этой возможности (15 000 долл. США на процессор и 3,300 долл. США). Азул, из того, что я слышал, составляет около 10 000 - 12 000 долларов, но заряжает физическую машину, а не ядро ​​/процессор. Кроме того, процесс заканчивается объемом, поэтому чем больше серверов вы используете, тем глубже дисконтируете. Мои разговоры с ними показали, что они достаточно гибкие. Oracle - это вечная лицензия, а Zing - это подписка... но если вы делаете математику и добавляете другие функции, которые имеет Zing (см. Различия ниже).

Вы можете сократить расходы, перейдя на Java 7, но затем понесите затраты на разработку. Учитывая план развития Oracle (новый выпуск каждые 18 месяцев или около того), а также тот факт, что они исторически предлагают только самые последние версии более ранних версий обновлений Java SE, "свободный" горизонт ожидается на 3 года от первоначальной GA если какая-либо основная версия. Поскольку первоначальные выпуски GA, как правило, не принимаются в производстве в течение 12-18 месяцев, и что перемещение производственных систем на новые крупные выпуски java обычно несет значительные затраты, это означает, что счета поддержки Java SE начнут ударять где-то между 6 и 24 месяцами после первоначального развертывания.

Заметные отличия: JRocket все еще имеет некоторые ограничения масштабируемости в плане ОЗУ (хотя и улучшилось с самых старых дней). Вы можете улучшить свои результаты с некоторой настройкой. Zing разработал свой алгоритм, чтобы обеспечить непрерывное, параллельное сжатие (не останавливать мир, паузы и "настройка" не требуется). Это позволяет Zing масштабироваться без теоретического потолка памяти (они делают кучи 300+ ГБ без страдания остановки мира или сбоя). Поговорите о смене парадигмы (подумайте о последствиях для больших данных). У Zing есть некоторые действительно замечательные улучшения в блокировке, дающие ему потрясающую производительность с небольшим количеством работы (если она настроена, может идти в среднем на миллисекундах). Наконец, они имеют видимость классов, методов и поведения потоков в производстве (без накладных расходов). Мы рассматриваем это как огромную экономию времени при рассмотрении обновлений, исправлений и исправлений ошибок (например, утечек и блокировок). Это может практически исключить необходимость воссоздания многих проблем в Dev/Test.

Ссылки на данные JVM Я нашел:

JRocket Детерминированный GC

Azul Presentation - Java без джиттера

Тест Azul/MyChannels

Ответ 10

Я знаю, что системы azul имеют jvm, чей GC оснащен аппаратным обеспечением. Он также может работать одновременно и собирать огромные объемы данных довольно быстро.

Не уверен, насколько детерминирован он.