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

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

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

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

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

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

я рекомендовал бы читать на этих статьях - блог Щелчка Утеса. Он - архитектор Azul, в значительной степени кодировал весь стандартные 1,5 Java параллельные классы и т.д. к вашему сведению, Azul разработан для систем, которые требуют очень больших размеров "кучи", а не просто стандартных требований RT.

Это не 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 для выпуска, который не прибыл из, получают.

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

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

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

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

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

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

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

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