Простое и неэффективное решение проблемы

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

§Если блоки будут маленькими, то мы ничего не выигрываем, так как такая организация памяти практически не будет отличаться от отсутствия организации. Кроме того, мы даже проиграем так как нужно ведь ещё организовать список для хранения адресов свободных блоков, каковой может занимать значительный объём памяти.

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

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

 

Стратегия перераспределения памяти

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

Простейшая стратегия: Через какой-то фиксированный интервал времени просматривать всю память и создавать новый список свободной памяти. Такой подход будет хорош, только если время исполнения нашей программы нас не интересует, что вряд ли.

Более эффективная стратегия. Заметим для начала, что ни одна программа не использует всю память одновременно. Из этого очевидного утверждения следует другое, менее очевидное, но очень полезное: существует интервал времени в течении которого эффективное распределение памяти нарушается лишь в небольшой области.

А следовательно все операции перераспределения выполняются только для очень небольшого количества рядом расположенных блоков памяти.

Иначе говоря

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

Важный вывод

Стратегия управления памятью, это способ разбиения и объединения блоков памяти позволяющий сохранять какую-то определённую структуру свободной памяти.

 

О структуре памяти

Прежде чем начинать разговор о методах организации памяти нужно сформулировать более точно, что мы хотели бы от этого выиграть. Термин "Эффективная организация" сам по себе не несёт никакой информации. Я полагаю, что нам нужно три вещи:

1. Поиск свободного блока нужного размера должен происходить как можно быстрее.

2. Свободный блок памяти предназначенный для размещения в нём блока данных должен по размеру как можно точнее соответствовать этому блоку.

3.  Перераспределение памяти не должно захватывать большое количество блоков. Оптимальный вариант - это когда в процессе перераспределения участвует не более двух блоков. То есть либо один блок разбивается на два, либо два блока объединяются в один.

Выводы:

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

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

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

Метод близнецов

Главная идея

Главная идея, лежащая в основе методов близнецов, заключается в том, что все блоки имеют лишь строго определённые размеры s₁<s₂<s₂<……<s_n. (список блоков упорядочен по возрастанию) Характерными вариантами последовательности чисел s₁, s₂… являются числа 1,2, 4, 8….. (метод близнецов экспоненциального типа) и 1, 2, 3, 5, 8, 13 …. (метод близнецов с числами Фиббоначи). Возможны и другие последовательности. Единственным требованием к последовательности является простота счета. Очередное число в последовательности должно быть вычисляемо как можно меньшим количеством арифметических операций. Размер блока определяется по формуле V_i =a*s_i где а – количество байт в наименьшем блоке.