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

Содержание

Введение

1 Задача1.Алгоритм Дойча-Шорра-Уэйта

2 Задача 2. Пометка занятых ячеек памяти

3 Задача 3

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

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

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

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

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

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

Заключение

Литература align="center" >Введение

Подавляющее большинство программистов - это прикладные программисты, то есть люди полагающие, что исполнение написанной программы компьютером - это проблема компьютера. Встретив команду типа a:integer; компьютер должен её обработать, но в чём заключается эта обработка большинство из нас не слишком интересуется. Ещё меньше нас интересует и процесс выполнения таких команд как a:integer и new(a). Однако интуитивно мы все понимаем, (даже если не знаем точно), что за этими командами скрываются достаточно сложные процессы распределения и перераспределения оперативной памяти.

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

Однако статическая память это не вся память. Ещё существуют динамические переменные, которые можно, как создавать, так и уничтожить в процессе работы программы.

Итак, какие проблемы возникают при работе с динамическими переменными, как их решать и зачем их решать? Чтобы это понять, сделаем несколько важных замечаний:

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

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

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

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

	Это вся пам'ять
	А это переменная которую нужно разместить

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

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

Идея на первый взгляд очень проста, но при её реализации встречается ряд проблем, борьба с которыми может оказаться не вполне тривиальной.

Проблема 1.

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

Проблема 2.

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

Группа ячеек памяти А непосредственно связана с указателем, то есть её местоположение известно конкретной переменной, чего нельзя сказать о группе В и группе С. И чтобы их обнаружить необходимо пройти по всей цепочке связного списка. А ведь связный список может быть произвольно сложный. Например, такой:

			Е

Попытка поиска занятых ячеек памяти в таком связном списке обязательно приведёт к зацикливанию (В, С, Е) если не позаботится специальным образом о обработке таких ситуаций.

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

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