Главная страница
qrcode

Менеджер памяти


Скачать 16.85 Kb.
НазваниеМенеджер памяти
Дата01.12.2019
Размер16.85 Kb.
Формат файлаdocx
Имя файлаСавицкий_homework3_ex_A.docx
ТипУказатель
#66918
Каталог

Савицкий Алексей Геннадьевич

Менеджер памяти
Алгоритм решения
Изначально определим, какие структуры данных нам необходимы для решения задачи. Разобьем ячейки памяти на свободные и занятые отрезки.

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

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

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

Для обработки запроса на выделение памяти нам необходимо найти самый длинный свободный отрезок с минимальным индексом первой ячейки. Тогда при обработке запроса на выделение памяти мы должны проверить, можем ли мы выделить необходимый объем памяти, для чего мы извлекаем из кучи максимальный элемент. Если не можем, то в соответствующую ячейку массива запросов ставим -1, указатель устанавливаем NULL. Иначе – вставляем в список занятый отрезок, а также уменьшаем длину свободного отрезка. Из кучи извлекаем максимум и в неё добавляем значение max – k, где k – количество выделенных ячеек памяти.

Обработка запроса на освобождение ячеек. При получении запроса на освобождение, обращаемся в нужный нам элемент массива запросов, по указателю переходим в список. Далее могут быть варианты: либо слева и справа от отрезка ячейки заняты, либо слева или справа ячейка свободна, либо и слева и справа от отрезка ячейки свободны
Слева и справа от отрезка ячейки заняты. Тогда в кучу добавляем этот отрезок, а в списке показываем, что ячейка теперь свободна.
  • Слева или справа есть свободный отрезок. Тогда в списке увеличиваем длину левого или правого отрезка соответственно и удаляем текущий. В куче при этом для соответствующего отрезка используем increaseKey.
  • Слева и справа – свободные отрезки. Тогда из списка удаляем правый и текущий отрезки и увеличиваем длину левого на значение (длина правого отрезка + количество освобожденных ячеек). Из кучи также удаляем правый отрезок и делаем increaseKey для левого отрезка.
    Доказательство правильности.
    Использование кучи предполагает, что выделение памяти происходит из отрезка наибольшей длины. Если при использовании операции siftup и siftdown в куче добавить условие, что если длины свободных отрезков равны, то тогда нужно сравнивать номера первой ячейки и поднимать элемент вверх по куче, если длины равны, а номер первой ячейки у нижнего в куче элемента меньше, чем соответствующий номер у верхнего элемента в куче. Таким образом, выполнены два необходимых условия – выделение памяти из самого большого отрезка и, если таких несколько, то из того, у которого индекс первого элемента меньше.
      Временная сложность – асимптотика
      Посчитаем временную сложность. Нам нужно обработать M запросов. Обработка каждого запроса подразумевает использование некоторых операций над кучей, а именно удаление из кучи, добавление, извлечение максимума, увеличение ключа. Все эти операции имеют временную сложность O(logK), где K – количество элементов в куче (показано на лекциях). Извлечение максимума из кучи – O(1), тк максимальный элемент находится в корне дерева. Изменение списка требует константного времени, так как мы храним ссылки на нужные отрезки, и нам не нужно проходить по списку для поиска нужного места для вставки, поэтому добавление и удаление элемента имеют константную временную сложность O(1). Полученная временная сложность алгоритма O(M*log(K)). Количество элементов в куче <= [N/2] (N – количество ячеек памяти), если количество запросов больше, чем количество ячеек (ситуация, где ячейки имеют длину 1 и чередуются). Если же количество запросов меньше количества ячеек, то тогда кол-во элементов в куче <= [M/2] (ситуация, где мы выделяем 2/3 M ячеек длины 1, а затем освобождаем половину из них через одну)

      Итого: O(M*log(K)), K <= [N/2], если N < M, K <= [M/2], если N > M
        Затраты памяти – асимптотика
        M. (первые M отрезков длины 1 занимаем, + 1 отрезок – оставшиеся ячейки). Получаем O(K + M + L) , где L – максимальное количество ячеек в списке.
        перейти в каталог файлов


  • связь с админом