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

Question

Под детерминистическим пониманием я имею в виду то, что его можно использовать в критически важных программах для работы в реальном времени, таких как программы для космических полетов. Сборщики мусора (и динамическое распределение памяти в этом отношении) являются большими запретами в программном обеспечении полета, потому что они считаются недетерминированными. Тем не менее, я знаю, что в настоящее время проводятся исследования по этому вопросу, поэтому мне интересно, была ли эта проблема решена.

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

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

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

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

Answer 4

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

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

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

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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

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

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

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

Answer 9

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

Детерминированный GC может быть предложен Azul Systems "Zing JVM" и JRocket. Zing поставляется с некоторыми очень интересными дополнительными функциями и теперь "основан на 100% программного обеспечения" (может работать на машинах 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 детерминированный GC

Презентация Azul - Java без джиттера

Azul / MyChannels Test

Answer 10

Я знаю, что у Azul Systems есть JVM, чей GC с аппаратной поддержкой. Он также может работать одновременно и собирать большие объемы данных довольно быстро.

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