Задача 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<m then {Движение вперёд}

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

"Как создать наиболее эффективную структуру свободной памяти. То есть такую структуру которая позволяла бы размещать блоки данных с наименьшими затратами времени и физической памяти."

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

Для начала рассмотрим простое решение и на нём попытаемся получше понять поставленную задачу.