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

Question

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

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

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

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

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

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

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

Answer 1

С блоками с фиксированным размером то, что вы описали бесплатный список. Анкет Это очень распространенная техника, со следующим поворотом: список бесплатных блоков хранится в самих бесплатных блоках. В 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;
}

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

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

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

Answer 2

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

---

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

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

Answer 3

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