Умное управление памятью с постоянными операциями времени?

Давайте рассмотрим сегмент памяти (размер которого может увеличиваться или уменьшаться, как файл, когда это необходимо), в котором вы можете выполнить две основные операции выделения памяти, включающие блоки фиксированного размера:

• выделение одного блока
• освобождение ранее выделенного блока, который больше не используется.

Также, как требование, системе управления памятью не разрешается перемещаться по выделенным в данный момент блокам: их индекс / адрес должны оставаться неизменными.

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

Лучший подход: сохраняйте счетчик, но ведите список освобожденных блоков (что можно сделать за постоянное время) и используйте его в качестве источника для новых распределений, пока он не пуст.

Что дальше? Есть ли что-то умное, что можно сделать, но с ограничениями на постоянное выделение и освобождение времени, которые сделали бы сегмент памяти максимально коротким?

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

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

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

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

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

Есть много возможных вариантов. Хорошей вводной статьей является динамическое распределение памяти: обзор и критический обзор Wilson et al.

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

Основные стратегии, которые вы должны знать, - это «первая подгонка», «подгонка», «лучшая подгонка» и система друзей . Я написал короткое резюме для курса, который я преподавал, надеюсь, он читается. Я указываю на довольно исчерпывающий обзор .

На практике вы увидите различные модификации этих основных стратегий. Но ни один из них не является постоянным временем! Я не думаю, что это возможно в худшем случае при ограниченном объеме памяти.

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