Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет

им. Ф. Скорины»

Математический факультет

Кафедра МПУ

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

Курсовая работа

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

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

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

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

Проблема 1.

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

Проблема 2.

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

Группа С

Группа В

Группа А

Указатель

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

Д

С

В

А

Е

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

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

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

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

В чём будет заключаться решение:

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

Общая идея

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

1. Перейти в очередной узел списка.

2. Записать информацию о узле в список занятой памяти.

3. Пока список узлов связанных с данным не исчерпан выполнять п.1

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

Проблема

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

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

Хорошая идея

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

Примечание: Этот материал представляет собой конспект главы из книги "Структуры данных и алгоритмы" авторов: Альфред В. Ахо; Джон Э. Хопкрофт; Джеффри Д. Ульман

Я только позволил себе в некоторых местах вставить дополнительные пояснения, так как посчитал их изложение слишком сложным. Надеюсь, мои пояснения не сделали изложение ещё менее понятным.

Мои предварительные пояснения:

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

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

Таким образом, вместо стека активационных записей можно использовать поля указателей ячейки, анализируемой в настоящий момент, можно использовать поля указателей вдоль этого пути, которые и будут формировать путь. Таким образом, каждая ячейка, за исключением последней, содержит или в поле left, или в поле right указатель на её предшественника - ячейку расположенную ближе к ячейке source. Мы опишем алгоритм, использующий ещё одно битовое поле, которое называется back. Поле это имеет перечислимый тип (L, R) и говорит о том, какое из полей, left или right, указывает на предшественника.

Эта процедура, исполняющая нерекурсивный поиск в глубину использует указатель current для указания на текущую ячейку, а указатель previous - для указания на предшественника текущей ячейки. Переменная source указывает на ячейку source1, которая содержит только указатель в своем правом поле. До выполнения маркировки в ячейке source1 значение поля back устанавливаем равным R, а её правое поле указывает на самого себя. На ячейку на которую обычно указывает source1 теперь указывает ячейка current, а на source1 указывает previous. Операция маркировки прекращается в том случае, когда current=previous, это может произойти лишь при условии, если обе ячейки current и previous указывают на source1 то есть уже просмотрена вся структура.

1. Движение вглубь. Если текущая ячейка имеет один или несколько не пустых указателей, то нужно перейти на первый из них, то есть следовать указателю в поле left или, если его нет, то указателю в поле right. Теперь надо преобразовать ячейку на которую указывает текущая ячейка, в новую текущую ячейку, а старую текущую в предыдущую. Чтобы облегчить поиск пути обратно, нужно сделать так, чтобы указатель, которому мы только что следовали, теперь указывал на прежнюю предыдущую ячейку. Эти изменения показаны на рисунке А.

2. Переключение. Если мы определили, что ячейки, исходящие из текущей ячейки, уже все просмотрены, то обращаемся к полю back предыдущей ячейки. Если его значение равно L, а поле right этой ячейки содержит ненулевой указатель на какую-то ячейку C, то делаем С текущей ячейкой, в то время как статус предыдущей ячейки остаётся неизменным. Но значение поля back предыдущей устанавливаем равным R, а левый указатель в этой ячейке устанавливаем так, чтобы он указывал на прежнюю текущую ячейку. Чтобы отследить и сохранить путь от предыдущей ячейке, обратно к ячейке source, надо сделать так, чтобы указатель на ячейку С в поле right в предыдущей ячейке теперь указывал туда, куда указывал ранее её левый указатель. Эти изменения показаны на рис Б.

3. Отход. Если мы определили, что ячейки, исходящие из текущей ячейки, уже просмотрены, но значение поля back предыдущей ячейки равно R или L, а поле right содержит атом (Атомом авторы называют содержательное данное) или нуль указатель, значит мы уже просмотрели все ячейки, исходящие из предыдущей ячейки. Тогда осуществляется отход, при котором предыдущая ячейка становится текущей, а следующая ячейка вдоль пути от предыдущей к ячейке source - новой предыдущей ячейкой. Эти изменения показаны на рисунке В

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

Procedure rotate(var p1, p2, p3: ^celltype);

Var

Temp: celltype;

Begin

Temp:=p1;

P1:=p2;

P2:=p3;

P3:=temp;

End;

Теперь вернёмся к описанию нерекурсивной процедуры маркировки. Для неё возможны два состояния: продвижение вперёд, представленное меткой state1 и отход представленный меткой state2 и отход представленный меткой state2. Поначалу, а также в тех случаях, когда мы перешли на новую ячейку (либо в результате шага продвижения вперёд, либо в результате шага переключения), мы переходим в первое состояние. В этом состоянии мы пытаемся выполнить ещё один шаг продвижения вперёд и "отходим" или "переключаемся" лишь в том случае, если оказываемся заблокированными. Можно оказаться заблокированными по двум причинам: (1) ячейка к которой только, что обратились , уже помечена; (2)в данной ячейке отсутствуют ненулевые указатели. Оказавшись заблокированными, переходим во второе состояние - состояние отхода. Переход во второе состояние возможен в тех случаях, когда мы отходим или когда не можем оставаться продвижения вперёд, так как оказались заблокированными. В состоянии отхода проверяем, отошли ли обратно на ячейку source1. Как уже было сказано выше, мы распознаём эту ситуацию по выполнению условия previous=current; в этом случае переходим в состояние 3 (метка state3), то есть практически закончили маркировку ячеек. В противном случае принимается решение либо отступить и остаться в состоянии отхода, либо переключится и перейти в состояние продвижения вперёд.

А) движение вперёд

L

current

Previous

На рисунках старые указатели показаны сплошными линиями, а новые пунктирными.

Б) Переключение

R

previous

current

В) Отход

current

previous

Авторы используют следующие обозначения: PP - указатель/указатель; PA - указатель/атом и т.д. Кроме того можно заметить, что текст записанный ниже, это не вполне Паскаль-программа. Там не всё в порядке с оператором возврата из процедуры. Например return(false); это авторы делают для упрощения записи. Понимать этот оператор надо так:

Имя функции:=false;

Goto метка конца тела функции.

function blockleft (cell:celltype):boolean;

{Проверяет, является ли левое поле атомом или нуль указателем}

begin

with cell do

if (pattern=pp) or (pattern=pa) then

if left<>nil then return(false);

return true;

end; {blockleft}

function blockright (cell:celltype): boolean;

{ Проверяет, является ли левое поле атомом или нуль указателем }

begin

with cell do

if (pattern=pp) or (pattern=ap) then

if right<>nil then return(false);

end;{blockright}

function block (cell:celltype):boolean;

{проверяет, помечена ли ячейка и не содержит ли ненулевые указатели}

begin

if (cell.mark=true) or blockleft(cell) and blockright(cell) then

return true

else return false

end; {block}

procedure nrdfs; {помечает ячейки, доступные из ячейки source}

var

current, previous:^celltype;

begin {инициализация}

current:=source1^.right; {ячейка на которую указывает source1}

previous:=source1;

source1^.back:=r;

source1^.;

source1^.mark:=true;

state1: {Движение вперёд}

if block (current^) then

begin {Подготовка к отходу}

current^.mark:=true;

goto state2;

end;

else

begin

{пометить и продвинуться вперёд}

current^.mark:=true;

if blockleft (current^) then

begin

{следование правому указателю}

current^.back:=r;

rotate (previous, current, current^.right);

{реализация изменения согласно схеме а}

goto state1

end

else

begin

{следование левому указателю}

current^.back:=L;

rotate(previous, current, current^.left);

{реализация изменения согласно схеме а}

goto state1;

end;

end;

state2: {Завершение отход или переключение}

if previous = current then goto state3 {завершение}

else if (previouse^.back=L) and (not blockright(previous^)) then

begin {переключение}

previous^.back:=R;

rotate(previouse^.left,current, previouse^.right);

{реализация изменений как на схеме б}

goto state1;

end

else if previous^.back=R then {Отход}

rotate(previous, previous^.right,current)

{реализация изменений как на схеме в}

else rotate(previous, previous^.left,current);

{реализация изменений вариант в, но поле left предыдущей ячейки включено в путь}

goto state2

end;

state 3: {Здесь необходимо вставить код для связывания непомеченных ячеек в список свободной памяти}

end; {nrdfs}

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

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

В чём проблема.

Задача пометки упирается в задачу обхода списка. Если мы научимся обходить связный список, то проблема пометки решится сама собой. Задача же обхода произвольного списка имеет тривиальное решение. А именно, мы можем в каждом узле имеющем некоторое количество указателей ВПЕРЁД завести такое количество указателей НАЗАД и счётчик вхождений в данный узел. Следующий алгоритм будет решением задачи:

При вхождении в узел

Если есть неиспользованные указатели ВПЕРЁД

ТО перейти на узел по очередному указателю ВПЕРЁД

ИНАЧЕ

Если есть неиспользованные указатели НАЗАД

ТО перейти на узел по очередному указателю НАЗАД

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

Небольшой предварительный анализ

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

Идея.

Я думаю, что намек уже понятен. Если мы заведем дополнительное поле размером в один байт, то это даст нам возможность пронумеровать 256 указателей.

Но это конечно ещё не всё. Понятно, что каждый из этих указателей может указывать как вперёд так и назад (Помните, что каждый из указателей используется как для запоминания пути вперёд так и пути назад). Возникает важный вопрос: как запомнить какой куда? Для ответа договоримся о следующем:

Во-первых, пусть множество указателей в каждом узле упорядочено линейно (сейчас не важно как именно это осуществляется, важно, что порядок есть и он линейный)

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

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

Общее описание алгоритма.

Для того, чтобы иметь возможность двигаться по сети узлов в двух направлениях нужно иметь два рабочих указателя. Назовём их ВПЕРЁД и ОБРАТНО. Указатель ВПЕРЁД содержит адрес узла в который необходимо перейти на следующем шаге, а указатель ОБРАТНО содержит адрес узла из которого Исполнитель вышел на предыдущем шаге. Сие означает, что на каждом шаге (в каждом узле) нужно выполнить операции определения этих адресов.

Рассмотрим некий узел, назовём его Текущий. Когда Исполнитель зайдет в этот узел первый раз, он должен будет перейти на узел чей адрес хранится в указателе1. То есть ВПЕРЕД=Указатель1. Понятно, что это первое и последнее использование указателя Указатель1. Он больше для запоминания пути вперёд не нужен, а стало быть его теперь можно использовать для запоминания пути назад, для чего можно выполнить операцию Указатель1=ОБРАТНО.

Когда исполнитель зайдёт в текущий узел второй раз он тоже самое проделает с указателем2. Это исполнитель будет проделывать до тех пор пока есть указатели ВПЕРЁД которыми он ещё не пользовался. А вот дополнительное однобайтовое поле (назовём его счетчик) как раз и пригодится для запоминание номера указателя которым ещё не пользовались.

Перед началом работы проинициализируем поле Счетчик всех узлов сети нулями. Затем каждый раз при входе в очередной узел будем увеличивать значение счётчика на 1. Тогда его значение будет определять номер неиспользованного указателя.

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

Иначе говоря

Идя вперёд исполнитель использует все указатели узла последовательно начиная с первого, занося в них адреса из указателя ОБРАТНО. Когда исполнитель идёт назад он использует указатели в обратном порядке. Относительно динамики изменения счётчика можно сказать, что пока в узле есть неиспользованные указатели вперёд, счётчик растёт (+1 на каждом шаге). Когда начинается движение назад, счётчик убывает (-1 на каждом шаге).

Аналогия с лабиринтом

Представьте себя в лабиринте в котором узлу соответствуют комнаты, а указатели это коридоры. Счетчик это некоторая доска на которой мы можем записывать число и кроме того у нас есть возможность соединять коридоры линиями. Чтобы корректно проверить весь лабиринт мы должны обойти все коридоры по порядку и на каждом шаге коридор из которого вошли в комнату соединять направленным отрезком с тем коридором в который собираемся уйти. А номер коридора в который идти мы будем определять по числу написанному на доске. Когда не останется ни одного не пройденного коридора, мы начиная с последнего и до первого будем выполнять следующее:

1. Выбираем очередной коридор.

2. Определяем, с каким коридором он связан (указатель ОБРАТНО) и уходим по нему.

Алгоритм

Тек_узел=Первый узел

Пока процес не завершён делать

Найти последний значимый указатель

Если номер указателя меньшего счётчика вхождений

То

Движение вперёд

Иначе

Движение назад

Движение вперёд

Вычислить номер неиспользованного указателя ВПЕРЁД

Увеличить значение счётчика вхождений

Запомнить текущий указатель ОБРАТНО в найденном неиспользованном указателе ВПЕРЁД

Указатель ОБРАТНО=адресу текущего узла.

Указатель на текущий узел=указателю с вычисленным номером

Движение назад

Определить значение указателя ОБРАТНО (хранится в последнем ненулевом указателе)

Указатель на текущий узел=указателю ОБРАТНО

Обнулить последний ненулевой указатель (определить его как указывающий в никуда)

Описание программы

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

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

program example;

uses crt;

type

rec=record

count:byte; {счётчик вхождений}

num:integer; {просто числовое поле}

{Массив указателей}

uk:array[1..255] of integer;

end;

var

uzel:array[1..100] of rec;

pred_index,tek_index,i,j,n,m,c:integer;

q:boolean;

procedure print;

{Распечатка значения узла}

begin

if uzel[tek_index].num>0 then

begin

write(uzel[tek_index].num,'');

uzel[tek_index].num:=0;

{Это для того, чтобы не печатать несколько раз одно и то же значение}

readkey;

end;

end;

begin

{создание сети}

clrscr;

write('Введите количество узлов сети -');read(n);

for i:=1 to n do

begin

write('Узел номер -',i);

write(' Введите значение узла -');read(uzel[i].num);

{Инициализация массива ссылок}

for j:=1 to 255 do uzel[i].uk[j]:=0;

uzel[i].count:=0;

write('Введите количество ссылок -');read(m);

for j:=1 to m do

begin

write('ссылка номер ',j,'=');

read(uzel[i].uk[j]);

end;

end;

{прохождение сети. Начинаем работу с первого узла}

tek_index:=1;

repeat

{Поиск последней ссылки содержащей указатель}

m:=1;

while (uzel[tek_index].uk[m]<>0)and(m<255) do m:=m+1;

if m=255 then m:=0 else m:=m-1;

if uzel[tek_index].countДвижение вперёд}

begin

print;

{Мы начинаем обход указателей начиная с последнего. Формула приведённая ниже вычисляет очередной используемый указатель }

m:=m-uzel[tek_index].count;

uzel[tek_index].count:=uzel[tek_index].count+1;

{циклическая перестановка указателей}

c:=tek_index;

tek_index:=uzel[tek_index].uk[m];

if c>1 then uzel[c].uk[m]:=pred_index

else uzel[c].uk[m]:=0;

pred_index:=c;

end

else {отход назад}

begin

print;

if uzel[tek_index].count>0

{Если счетчик = 0 и тем не менее есть потребность уйти из текущего узла назад, то это означает, что в текущем узле нет ссылок вперёд, а стало быть не было запомненно много ссылок ОБРАТНО и есть только одна ссылка ОБРАТНО хранящаяся непосредственно в указателе pred_index. Если же счетчик > 0 то это означает, что есть запомненные указатели ОБРАТНО (кстати тоже может быть один) и надо найти первый из неиспользованнных}

then

begin

{счётчик как раз и показывает на первый из неиспользованных указателей ОБРАТНО}

m:=uzel[tek_index].count;

uzel[tek_index].count:=uzel[tek_index].count-1;

{если мы использовали очередной указатель ОБРАТНО, и не изменим значение счётчика, то при последующей попытке отхода назад нам будет предложен опять тот же указатель} c:=uzel[tek_index].uk[m];

uzel[tek_index].uk[m]:=0;

{ В начале цикла обработки мы ищем первый ненулевой указатель. Поэтому указатели которые были использованы и как указатели вперёд и как указатели назад нужно забыть иначе они опять будут использованы}

tek_index:=c;

end

else tek_index:=pred_index;

{write('индекс отхода - ',tek_index);

delay(1000);}

end;

if tek_index=1 then

begin

q:=true;

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

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 Главная идея

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

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

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

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

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

Блок s_i это блок нужного размера. После создания нужного блока у нас появляется новый блок, размер которого должен быть членом ряда, то есть величина s_i+1-s_i должна равняться некоторому числу s_j из используемой последовательности, 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 Это своего рода КПД (коэффициент полезного действия)

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

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

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

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

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

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

Заключение

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

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.