Курсовая работа: Распределение памяти

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

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 Задача 3

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

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

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

3.1 Простое и неэффективное решение проблемы

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

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

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

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

3.2 Стратегия перераспределения памяти

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

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

Более эффективная стратегия. Заметим для начала, что ни одна программа не использует всю память одновременно. Из этого очевидного утверждения следует другое, менее очевидное, но очень полезное: существует интервал времени в течении которого эффективное распределение памяти нарушается лишь в небольшой области.

А следовательно все операции перераспределения выполняются только для очень небольшого количества рядом расположенных блоков памяти.

Иначе говоря

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

Важный вывод

Стратегия управления памятью, это способ разбиения и объединения блоков памяти позволяющий сохранять какую-то определённую структуру свободной памяти.

3.3 О структуре памяти

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

1.         Поиск свободного блока нужного размера должен происходить как можно быстрее.

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

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

Выводы:

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

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

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

4 Метод близнецов

4.1 Главная идея

Главная идея, лежащая в основе методов близнецов, заключается в том, что все блоки имеют лишь строго определённые размеры 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.

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

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