Распределение памяти - Курсовая работа

Действительно, статические переменные (то есть те, которые описываются после ключевого слова var) создаются один раз, в момент запуска программы на выполнение и уничтожаются один раз, в момент окончания работы программы. Это означает, что проблемы перераспределения памяти просто не существует, все определяется в начале и уже никогда не изменяется. Чтобы это понять, сделаем несколько важных замечаний: Во-первых, в начале работы программы, доступная область памяти представляет собой сплошной пустой массив ячеек памяти. Его английский вариант heap), при этом программа просматривает всю свободную память до тех пор, пока не обнаружит первый достаточно большой кусок свободной памяти. Из этих трех замечаний следует, что в процессе работы программы, если динамические переменные многократно создаются и уничтожаются, то куча динамической памяти будет представлять собой беспорядочное нагромождение свободных и занятых ячеек и может даже случится так, что при наличии большого объема свободной памяти, разместить данное большого объема не получится.Мои предварительные пояснения: Основным объектом обрабатываемым алгоритмом является структура состоящая из двух ячеек (left, right) указывающих на последующие ячейки, ячеек данных и ячейки содержащей пометку занята ячейка или свободна. Таким образом, каждая ячейка, за исключением последней, содержит или в поле left, или в поле right указатель на ее предшественника - ячейку расположенную ближе к ячейке source. На ячейку на которую обычно указывает source1 теперь указывает ячейка current, а на source1 указывает previous. Чтобы отследить и сохранить путь от предыдущей ячейке, обратно к ячейке source, надо сделать так, чтобы указатель на ячейку С в поле right в предыдущей ячейке теперь указывал туда, куда указывал ранее ее левый указатель. Если мы определили, что ячейки, исходящие из текущей ячейки, уже просмотрены, но значение поля back предыдущей ячейки равно R или L, а поле right содержит атом (Атомом авторы называют содержательное данное) или нуль указатель, значит мы уже просмотрели все ячейки, исходящие из предыдущей ячейки.Понятно, что каждый из этих указателей может указывать как вперед так и назад (Помните, что каждый из указателей используется как для запоминания пути вперед так и пути назад). Во-вторых, каким-то образом для каждого узла определено сколько у него указателей, например для хранения этой информации заведена еще одна переменная. Алгоритм, как и алгоритм Дойча, должен уметь две вещи: во-первых запоминать путь назад и во вторых, определять в каждом узле указатель указывающий на узел в который необходимо перейти. Указатель ВПЕРЕД содержит адрес узла в который необходимо перейти на следующем шаге, а указатель ОБРАТНО содержит адрес узла из которого Исполнитель вышел на предыдущем шаге. Когда Исполнитель зайдет в этот узел первый раз, он должен будет перейти на узел чей адрес хранится в указателе1.Поделим всю память на блоки (назовем их элементарными) небольшого размера. Если блоки будут большими мы потерям много памяти на размещение небольших блоков, так как маленький блок будет использовать для своего хранения большой блок не нуждаясь в значительной его части.Как бы удачно мы не разбили память в начале работы компьютера, процесс появления плохих (слишком маленьких) фрагментов неизбежен, а следовательно есть потребность периодически производить перераспределение (объединять блоки, разбивать на несколько, перемещать в другое место) памяти. Простейшая стратегия: Через какой-то фиксированный интервал времени просматривать всю память и создавать новый список свободной памяти. Заметим для начала, что ни одна программа не использует всю память одновременно.Стратегия управления памятью, это способ разбиения и объединения блоков памяти позволяющий сохранять какую-то определенную структуру свободной памяти.Прежде чем начинать разговор о методах организации памяти нужно сформулировать более точно, что мы хотели бы от этого выиграть. Свободный блок памяти предназначенный для размещения в нем блока данных должен по размеру как можно точнее соответствовать этому блоку.

Содержание

Введение

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 свободных ячеек, однако нигде нет две свободных ячеек подряд, а стало быть нашу переменную, требующую две ячейки разместить некуда.

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

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

Проблема 1.

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

Проблема 2.

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

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

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

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

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

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

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

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

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

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

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

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

Все пустые блоки размера 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

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

Требовалось Использовано

4 5

1 1

6 8

7 8

Итого 18 Итого 22

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

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

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

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

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

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

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

Заключение

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

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

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

Литература

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

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

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

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

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

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

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

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

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