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

Как ищется пустой блок памяти для блока данных

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

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

Что делать когда нужного блока нет

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

Блок si это блок нужного размера. После создания нужного блока у нас появляется новый блок, размер которого должен быть членом ряда, то есть величина si+1-si должна равняться некоторому числу sj из используемой последовательности, j<i.

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

Рассмотрим пример. Пусть мы имеем изначально следующий ряд: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, то есть ряд построенный на числах Фиббоначи. И есть следующие блоки данных: 1, 2, 1, 4, 4, 1. Посмотрим как будут распределяться наши блоки и что будет происходить с памятью. Занятые блоки будем помечать красным, а новые блоки синим.

Шаг 1: Блок данных объёмом 1 : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Шаг 2: Блок данных объёмом 2: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Шаг 3: Блок данных объёмом 1: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Шаг 4: Блок данных объёмом 4: 1, 1, 2, 3, 1, 4, 8, 13, 21, 34, 55

4.2 Шаг 5: Блок данных объёмом 4: 1, 1, 2, 3, 1, 4, 3, 5, 13, 21, 34, 55

На этом шаге мы имеем небольшие потери. А именно пришлось использовать блок длины 5 для хранения блока данных длины 4

Шаг 6: Блок данных объёмом 1: 1, 1, 2, 3, 1, 4, 3, 5, 13, 21, 34, 55

Не сложно заметить, что количество блоков небольшого размера увеличилось. А теперь попробуем оценить потери. Рассмотрим ещё один пример и на нём рассчитаем отношение занятой памяти реальными данными к памяти которую пришлось вычеркнуть и списка свободной памяти. Пусть необходимо разместить следующие блоки: 4,1, 6,7. Общая память 1, 1, 2, 3, 5, 8, 13,

Блок 4: 1, 1, 2, 3, 5 , 8, 13

Блок 1: 1, 1, 2, 3, 5 , 8, 13

Блок 6: 1, 1, 2, 3, 5 , 8, 13

Блок 7: 1, 1, 2, 3, 5 , 8, 5, 8

Итак получаем

Отношение = 18/22=0,82 Это своего рода КПД (коэффициент полезного действия)

Конечно смотря с чем сравнивать. Если сравнить с двигателями внутреннего сгорания, то это очень высокий КПД.

Почему размер блока остатка должен быть членом ряда

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

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

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

Во-вторых, первый же найденный блок и будет оптимальным решением (потому как следующий будет уже больше и может быть даже существенно больше).

Заключение

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

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

2. Как упорядочить блоки свободной памяти, так чтобы поиск нужного блока велся максимально быстро.

3. Как организовать быстрое перераспределение памяти так, чтобы не было потребности перерабатывать всю память и составлять новый список свободных блоков.

Литература

1. Вострикова З.П. и др. "Программирование на языке "БЕЙСИК" для персональных ЭВМ". Машиностроение, 1993г.

2. Гохман А.В. и др. "Сборник задач по математической логике и алгебры множеств", издательство Саратовского Университета, 1969г.

3. Гусев В.В. Основы импульсной техники. М. Советское радио, 1975

4. Касаткин В.Н. "Информация, алгоритмы, ЭВМ", М. Просвещение, 1991г.

5. Машовцев В.А. Вступительные экзамены по информатике//Информатика. 1997, №13

6. Орлов В.А. О вступительных экзаменах по информатике//Информатика, 1997, №15

7. Яснева Г.Г. Логические основы ЭВМ//Информатика и образование, 1998, №2

8. Лыскова В.Ю., Ракитина Е.А. Логика в информатике, М. Информатика и образование 1999

9. Шауцкова Л.З. “Решение логических задач средствами алгебры логики”, газета Информатика 1999, №5.

 Скачать реферат