Исполнитель:

Студентка группы М-41 ____________ Кондратенко А.Ю.

Научный руководитель:

Канд. физ-мат. наук, доцент ____________ Гундарева Т.Е.

Гомель 2007

Содержание

Введение

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

Заключение

Литература

Введение

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

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

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

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

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

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

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

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

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

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

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--