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.
А теперь разрешите предложить небольшую задачу. Рассмотренный выше алгоритм не работает для целого класса сетей. Представитель этого класса нарисован ниже. Ошибка не в программе (конечно в программе тоже может быть есть ошибки, как сказал, кто-то из великих “Ни одна программа не работает правильно”), а в алгоритме. Я не описал некое очень важное требование к топологии сети. Сразу хочу сказать, что ограничивать топологию деревьями будет слишком жестко. Эта программа с сетями в которых есть циклы тоже вообщем-то справляется
Ещё один интересный пример ниже. Эту сеть программа проходит вполне успешно, но зависает в тот момент когда надо бы прекратить работу.
Проблема данного примера в алгоритме. Если вам удастся выяснить какие ограничения я не описал, то вы увидите, что эта сеть должна проходится алгоритмом вполне корректно.
"Как создать наиболее эффективную структуру свободной памяти. То есть такую структуру которая позволяла бы размещать блоки данных с наименьшими затратами времени и физической памяти."
Нам уже известно, что это не тривиальная проблема. Просто искать первое попавшееся свободное место хорошо только когда вся память свободна (в этом случае достаточно определить адрес первой свободной ячейки). Если же программа работает слишком долго, то память машины будет представлять собой совершено беспорядочное нагромождение свободных и занятых блоков, при этом в достаточно большом объёме свободной памяти вполне может не оказаться блока достаточного размера. Конечно, если такое случится, мы можем перераспределить память, то есть собрать все свободные блоки в одну кучу, но как мы уже видели в предыдущих лекциях это делается довольно сложными алгоритмами требующими значительного времени на свою работу и использующих значительный объём памяти. Отсюда ясно, что задача какой-то организации памяти вместо никакой может дать ощутимый выигрыш, если в результате реже будет возникать необходимость в «сборке мусора».
Для начала рассмотрим простое решение и на нём попытаемся получше понять поставленную задачу.
Поделим всю память на блоки (назовём их элементарными) небольшого размера. Тогда для размещения блока данных нужно найти столько свободных элементарных блоков, чтобы в совокупности они имели нужный объём. Почему это решение неэффективно:
-Если блоки будут маленькими, то мы ничего не выигрываем, так как такая организация памяти практически не будет отличаться от отсутствия организации. Кроме того, мы даже проиграем так как нужно ведь ещё организовать список для хранения адресов свободных блоков, каковой может занимать значительный объём памяти.
-Если блоки будут большими мы потерям много памяти на размещение небольших блоков, так как маленький блок будет использовать для своего хранения большой блок не нуждаясь в значительной его части.
Вывод: Рассмотренный пример говорит о том, что разбиение памяти на блоки одинакового размера при наличии разных блоков данных нецелесообразно. Идеальное разбиение – это такое разбиение при котором для каждого блока данных будет элементарный блок точно такого же размера. Это конечно невозможно, но мы должны хотя бы стремится к такому разбиению.
Как бы удачно мы не разбили память в начале работы компьютера, процесс появления плохих (слишком маленьких) фрагментов неизбежен, а следовательно есть потребность периодически производить перераспределение (объединять блоки, разбивать на несколько, перемещать в другое место) памяти. Какие могут быть общие методы (стратегии).
Простейшая стратегия: Через какой-то фиксированный интервал времени просматривать всю память и создавать новый список свободной памяти. Такой подход будет хорош, только если время исполнения нашей программы нас не интересует, что вряд ли.
Более эффективная стратегия. Заметим для начала, что ни одна программа не использует всю память одновременно. Из этого очевидного утверждения следует другое, менее очевидное, но очень полезное: существует интервал времени в течении которого эффективное распределение памяти нарушается лишь в небольшой области.
А следовательно все операции перераспределения выполняются только для очень небольшого количества рядом расположенных блоков памяти.
Иначе говоря
Если мы говорим, что нужно заняться перераспределением памяти, то это означает, что где-то завелось несколько подряд идущих маленьких блоков, которые есть смысл объединить в один большой или наоборот возникла потребность в разбиении одного большого блока на несколько более мелких.
Важный вывод
Стратегия управления памятью, это способ разбиения и объединения блоков памяти позволяющий сохранять какую-то определённую структуру свободной памяти.
Прежде чем начинать разговор о методах организации памяти нужно сформулировать более точно, что мы хотели бы от этого выиграть. Термин "Эффективная организация" сам по себе не несёт никакой информации. Я полагаю, что нам нужно три вещи:
1. Поиск свободного блока нужного размера должен происходить как можно быстрее.
2. Свободный блок памяти предназначенный для размещения в нём блока данных должен по размеру как можно точнее соответствовать этому блоку.
3. Перераспределение памяти не должно захватывать большое количество блоков. Оптимальный вариант - это когда в процессе перераспределения участвует не более двух блоков. То есть либо один блок разбивается на два, либо два блока объединяются в один.
Выводы:
Во-первых, программа может иметь дело с блоками данных самого разного размера, из этого следует, что в списке свободных блоков должны существовать блоки самого разного размера.
Во-вторых, для того, чтобы поиск осуществлялся как можно быстрее список блоков должен быть как то упорядочен, например по возрастанию размеров блоков.
В-третьих, размеры блоков желательно определять по какому-нибудь правилу. Это позволит получить дополнительный выигрыш в скорости при поиске, так как знание правила определения размера позволит хотя бы примерно предположить где в списке свободных блоков находится блок нужного размера.
Главная идея, лежащая в основе методов близнецов, заключается в том, что все блоки имеют лишь строго определённые размеры 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.