Какие детерминированные алгоритмы сборки мусора существуют? - PullRequest
16 голосов
/ 20 октября 2008

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

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

Ответы [ 10 ]

17 голосов
/ 21 октября 2008

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

10 голосов
/ 20 октября 2008

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

5 голосов
/ 24 июня 2012

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

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

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

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

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

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

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

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

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

3 голосов
/ 20 октября 2008

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

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

2 голосов
/ 10 апреля 2009

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

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

2 голосов
/ 16 ноября 2008

Это не 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 для освобождения, которое не пришло от приобретения.

1 голос
/ 12 декабря 2012

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

Детерминированный 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 Deterministic GC

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

Тест Azul / MyChannels

1 голос
/ 07 марта 2009

В режиме реального времени означает гарантированный верхний предел времени отклика. Это означает верхнюю границу инструкций, которые вы можете выполнять, пока не получите результат. Это также устанавливает верхний предел количества данных, к которым вы можете прикоснуться. Если вы не знаете, сколько памяти вам понадобится, очень вероятно, что у вас будет вычисление, для которого вы не можете дать верхний предел времени его выполнения. 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), распределение должно преуспеть из-за (2а) - мы можем использовать что раньше было первой ссылкой - но, из-за (2b), мы должны начать GC, который в конечном итоге пересекает n-1 объекты, следовательно, имеют время работы O (N).

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

1 голос
/ 20 октября 2008
0 голосов
/ 20 октября 2008

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

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

...