Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

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

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

То

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

Иначе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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₁22<……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

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

Рассмотрим пример. Пусть мы имеем изначально следующий ряд: 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,

Характеристики

Список файлов курсовой работы