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

{Это естественное условие прекращение работы. Оно утверждает, что работа прекращена, если мы находимся в первом узле и в нем нет ненулевых ссылок}

for j:=1 to 255 do

if uzel[1].uk[j]<>0 then q:=false;

end;

until q; {Завершение процесса}

end.

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

ь этого класса нарисован ниже. Ошибка не в программе (конечно в программе тоже может быть есть ошибки, как сказал, кто-то из великих “Ни одна программа не работает правильно”), а в алгоритме. Я не описал некое очень важное требование к топологии сети. Сразу хочу сказать, что ограничивать топологию деревьями будет слишком жестко. Эта программа с сетями в которых есть циклы тоже вообщем-то справляется

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

Проблема данного примера в алгоритме. Если вам удастся выяснить какие ограничения я не описал, то вы увидите, что эта сеть должна проходится алгоритмом вполне корректно.

3 Задача 3

"Как создать наиболее эффективную структуру свободной памяти. То есть такую структуру которая позволяла бы размещать блоки данных с наименьшими затратами времени и физической памяти."

Нам уже известно, что это не тривиальная проблема. Просто искать первое попавшееся свободное место хорошо только когда вся память свободна (в этом случае достаточно определить адрес первой свободной ячейки). Если же программа работает слишком долго, то память машины будет представлять собой совершено беспорядочное нагромождение свободных и занятых блоков, при этом в достаточно большом объёме свободной памяти вполне может не оказаться блока достаточного размера. Конечно, если такое случится, мы можем перераспределить память, то есть собрать все свободные блоки в одну кучу, но как мы уже видели в предыдущих лекциях это делается довольно сложными алгоритмами требующими значительного времени на свою работу и использующих значительный объём памяти. Отсюда ясно, что задача какой-то организации памяти вместо никакой может дать ощутимый выигрыш, если в результате реже будет возникать необходимость в «сборке мусора».

Для начала рассмотрим простое решение и на нём попытаемся получше понять поставленную задачу.

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

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

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

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

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

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

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

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

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

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

Иначе говоря

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

Важный вывод

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

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

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

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

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

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

Выводы:

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

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

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

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

4.1 Главная идея

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

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