15

Иванова Г.С., Ничушкина Т.Н.

Конспект лекций

по курсу "Алгоритмические языки и программирование".

Тема "Программирование с использованием динамической памяти".

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

Под эту категорию подпадают все переменные и константы, объявленные в Паскале и обозначенные идентификаторами. Это определяется статической структурой Паскаль - программы, обуславливающей расположение ее объектов в непрерывной области памяти длиной не более 64к, называемой сегментом данных, к которому примыкает стек размером 16к.

Однако, помимо привычной схемы, Паскаль дает возможность образовывать новые переменные в любой момент работы программы без учета ее статической структуры, сообразуясь с потребностями решаемой задачи. Точно также допускается уничтожение созданных переменных в произвольный момент выполнения. Переменные, созданием и уничтожением которых может явно управлять программист, называются динамическими. Память для таких переменных берется из свободной, называемой «кучей», размер которой составляет ~ 200 ~300к. Эта цифра получится, если из общей памяти вычесть размер, занятый системными компонентами и самой программой на Паскале.

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

1.1 Адресация оперативной памяти. Указатели.

Наименьшей адресуемой единицей памяти ПЭВМ является байт. Для обращения к конкретному байту необходимо иметь адрес .

Здесь адрес конкретного байта определяется как А=Аб+смещение, где Аб - адрес сегмента. Физический адрес при этом определяется Аф=Аб*16+смещение.

Для формирования адреса в МП 80386 и выше используются 32 разряда, что составляет 2 слова типа word. Первое слово содержит адрес сегмента, второе - адрес смещения внутри сегмента.

Сегмент - это непрерывный участок памяти, имеющий длину 64к и начинающийся с адреса, кратного 16 ( 0,16,32,.....).

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

Параграф - фрагмент памяти длиной 16 байт.

Сегмент адресует память до параграфа, а смещение - до байта. Каждому сегменту соответствует отдельно адресуемая непрерывная область памяти. Сегменты могут следовать один за другим без промежутка, с некоторым интервалом или перекрывать друг друга.

В Паскале адрес байта памяти, состоящий из 2 - х слов типа word носит название указатель. Синтаксис определения указателя прост и описывается следующей диаграммой:

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

Примеры объявления указателей представлены ниже:

VAR p1:^integer; {типизированный указатель или указатель целого типа}

p2:^real; {типизированный указатель или указатель вещественного типа}

p3:^char; {типизированный указатель или указатель символьного типа}

p: pointer; {нетипизированный указатель или указатель неопределенного типа}

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

TYPE point1=^integer;{новый ссылочный тип - указатель на целое}

point2=^char; {новый ссылочный тип - указатель на символ}

VAR p1:point1; {переменная ссылочного типа point1}

p2:point2; { переменная ссылочного типа point2}

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

TYPE ppointer = ^percon; {тип person еще не определен}

percon = record { определение типа person}

name: string: next: ppointer;

end;

Для указателей, которые «никуда не указывают», введено понятие «нулевой адрес», имеющий обозначение nil. Указатель nil считается константой, совместимой с любым типом указателя и его можно присваивать любому указателю.

Над значениями указателей возможны следующие операции:

1.Присваивание. Указателю присваивается значение другого указателя. Допускается присваивать указателю только значение того же или неопределенного типа. Например:

VAR p1,p2:^integer;

p3:^real;

p: pointer;

.Допустимые операции Недопустимые операции

p1:=p2; p:=p3; p1:=p3;

p1:=p; p1:=p; p3:=p2;

2. Доступ к переменной по указателю (операция разыменования). Чтобы получить доступ к переменной по указателю, необходимо после переменной - указателя поставить знак «^». При этом значение имеет тип, совпадающий с базовым типом указателя. Например:

p1^ - означает « переменная, на которую указывает p1». Так как p1 указатель на целое, то p1^ - -это значение целой, расположенной по адресу p1.Если написать

p1^:=2; то содержимое ячейки памяти, адресуемой указателем станет равным 2.

Чтобы изменить содержимое ячейки, необходимо выполнить следующую операцию:

p1^:=p^+2;

При этом содержимое ячейки изменится и станет равным 4.

3. Взятие указателя. Это унарная операция, которая строится из знака операции - символа @ (амперсанд) и одного операнда - переменной любого типа. Например, если имеется описание:

TYPE p =^integer;

VAR p1:p;

i: integer;

.....то последовательность операций

p1:=@i;

p1^:=2;

приведет к присвоению переменной i значения 2.

4. Отношения. Это бинарные операции сравнения указателей на равенство и неравенство. Операции проверяют, ссылаются ли два указателя на одну и ту же область памяти, и обозначаются обычным образом - знаком «=» и «<>». Например:

sign:=p1=p2 { sign приобретает значение true или false в зависимости от значений указателей}

if p1<> nil then ...

Так как тип указателя может быть образован от любых типов, допустимо определение «указатель на указатель».

Если описать переменную pp1, используя предыдущий пример, следующим образом:

VAR pp1:^p1;

то в качестве своих возможных значений она получит множество указателей, ссылающихся на целые значения. Применив операцию

pp1:=@p1; мы получим связи, изображенные на схеме.

Для получения значения ячейки i, необходимо дважды применить операцию разыменывания. В нашем случае pp1^^ - имеет тип integer и равно 2.

2. Процедуры и функции, работающие с указателями.

Для работы с указателями в Паскале предусмотрены стандартные функции, облегчающие и упрощающие эту работу. Перечень функций представлен в таблице 1

Таблица 1.

№	Вызов функции	Тип функции	Результат
1.	ADDR(x}	pointer	Возвращает адрес аргумента. (имя пер., функции, процедуры). Аналогична операции - @.
2.	SEG(x]	word	Возвращает адрес сегмента указанного объекта.
3.	OFS(x)	word	Возвращает смещение адреса указанного объекта.
4.	CSEG	word	Возвращает текущее значение регистра адреса программного сегмента - CS.
5.	DSEG	word	Возвращает текущее значение регистра адреса сегмента данных - DS.
6.	PTR(seg,ofs)	pointer	Возвращает значение указателя по заданным seg и ofs.
7.	SIZEOF(x)	word	Возвращает длину указанного объекта в байтах.

3. Управление динамической памятью.

Определяемые в примерах предыдущих разделов указатели, для простоты объяснения, содержали адреса некоторых статических объектов. Однако, основное назначение указателей - это адресация динамических объектов. Для динамических объектов программист заказывает память требуемого размера из динамической памяти. Вся динамическая память в Паскале рассматривается как подобная стеку структура, называемая «кучей». Физически «куча» располагается в старших адресах, сразу за областью, занимаемой программой. Схема распределения оперативной памяти представлена на рис.1.

Рис. 1.

На рисунке HeapOrg - указатель на начало динамической области

HeapEnd - указатель на конец динамической области

HeapPtr - указатель на текущее значение границы свободной динамической области

Заказать память требуемого объема из динамической области в Паскале можно несколькими способами.

1. Наиболее распространенный способ - использование процедуры или функции new. Вызов осуществляется следующим образом:

процедуры - NEW (<имя переменной ссылочного типа >);

<имя переменной ссылочного типа>:=NEW(<ссылочный тип >);

Примеры использования:

TYPE p = ^integer;

pa = ^real;

VAR pp : p;

ppa :pa;

.......................

new(pp); {динамическая область вся доступна pp = HeapOrg, HeapPtr=HeapOrg+2}

pp^ := 5; {по адресу заносим число 5 }

ppa: = new(pa); {в памяти уже есть число 5 типа integer, поэтому ppa=HeapOrg+2

HeapPtr=HeapPtr+6, так как тип указателя pa - real длиной 6 байт}

ppa^ :=35.5;

Память, выделенная под динамические переменные после использования должна быть освобождена. Для этой цели используется процедура освобождения памяти DISPOSE.

Процедура DISPOSE(<имя переменной ссылочного типа >)

Для переменных из предыдущего примера процедура вызывается так:

dispose(pp);

dispose(ppa);

При попытке применить процедуру к указателю, имеющему значение nil, возникает аварийная ситуация с выдачей сообщение об ошибке.

Чередование обращений NEW и DISPOSE может привести к фрагментации памяти. Для уменьшения этого явления можно использовать процедуры MARK и RELEASE.

MARK - запоминает значение в переменной указателе, определенном в качестве параметра.

RELEASE - освобождает весь фрагмент, начиная с адреса, зафиксированного в переменной указателе из процедуры MARK.

New(p1);

new(p2);

mark(p);

new(p3);

new(p4);

release(p);

Следует заметить, что совместное использование процедур Dispose и Release недопустимо.

2. Динамическую память можно выделять фрагментом указанного размера. Для этой цели в Паскале используется процедура GetMem (p,size).

Эта процедура запрашивает у системы память требуемого размера. Указанного в параметре size (запрашиваемый объем не должен превышать 64к) и помещает адрес выделенного системой фрагмента в переменную типа указатель с имеем p. После использования память обязательно нужно освободить процедурой FreeMem (p,size), которая по адресу указателя p освобождает фрагмент размером size.

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

Избежать подобной ситуации можно несколькими способами.

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

Maxavail: longint; возвращает размер максимального непрерывного участка памяти

Memavail: longint; возвращает размер всей свободной памяти, состоящей из суммы всех свободных фрагментов.

Второй способ заключается в возможности перехватить системную ошибку. Для этого необходимо определить свою подпрограмму обработки ошибки, в которой вместо признака ошибки HeapFunc:=0 (0 означает ошибку использования динамической памяти), необходимо задать Heapfunc:=1. Пример такой подпрограммы приведен ниже:

{$F+}

FUNCTION HeapFunc (size: word) : integer: far;

begin HeapFunc: =1; end;

{$F-}

В программе необходимо определить адрес подпрограммы обработки ошибки, который задается с помощью операции взятия адреса HepError:=@HeapFunc . Использование такой подпрограммы приведет к тому, что процедуры New и GetMem вернут указатель nil и выполнение программы не будет прервано. Управление система передаст в программу в точку возврата из процедуры, в которой возникла ошибка. Именно здесь пользователь имеет возможность сам решить, как поступить при наличии такой ошибки.

Пример 1. Программа подсчитывает сумму элементов массива большой размерности. Для размещения такого массива потребуется n*m*6 байт памяти. Нетрудно подсчитать, что одного сегмента здесь явно не хватит. Использование динамического массива по схеме указатель на элемент требует n*m*4 байта памяти, что превышает, при больших n и m (например при n=200,m=200), 64к. Решение можно найти, если подойти к массиву как к массиву строк, где каждая строка адресуется отдельным указателем, как указано на схеме.

Тогда одного сегмента достаточно для адресации 64000байт/4=16000 строк. Так как указатель может адресовать целый сегмент, то в каждой строке можно разместить 64000байт/6=10677. Однако эти цифры достижимы только при наличии доступной памяти. Поэтому в программе осуществляется проверка наличия доступной памяти путем перехвата ошибки, которую выдает система при отсутствии памяти, с помощью собственной функции обработки ошибок

program ex_large_mas;

const

nn=16000; {в сегменте длиной 64к можно разместить 64к/4 = 16000 указателей длиной 4б}

var