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

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

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