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

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

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

Метроном GC и BEA JRockit - две детерминированные реализации GC, о которых я знаю (обе для Java).

Для меня Java, работающая на 100% в реальном времени, по-прежнему остается незаменимой технологией, но я не претендую на роль эксперта.

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

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

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

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

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

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

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

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

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

// 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)

  • (а) то, что раньше было первой записью в списке, теперь недоступно, но
  • (б) он все еще выделен, что касается части управления памятью.

• В пункт (3), распределение должно добиться успеха из-за (2a) - мы можем использовать что раньше было первой ссылкой - но, из-за (2b) мы должны начать GC, который в конечном итоге пройдет n-1 объекты, следовательно, имеют время работы из O (N).

Так что да, это надуманный пример. Но сборщик мусора, который утверждает, что имеет ограничение по распределению, также должен быть в состоянии справиться с этим примером.

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

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

Пришлось искать через переполнение стека и заметил этот довольно старый пост.

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

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

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

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

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

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

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

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

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

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

Цена: Если вы используете Java 6 или более раннюю версию, Oracle теперь взимает 300% -ное повышение и принудительно поддерживает эту возможность (15 000 долларов за процессор и 3300 долларов на поддержку). Азул, насколько я слышал, стоит около 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

Представление Azul - Java без джиттера

Тест Azul / MyChannels