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

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

Краткие теоретические сведения

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

• сама программа пользователя;

• системные программы времени выполнения, которые осуществляют вспомогательные действия при работе программы пользователя;

• определяемые пользователем структуры данных и константы;

• точки возврата для подпрограмм;

• временная память для хранения промежуточных результатов при вычислении выражений;

• временная память при передаче параметров и т.п.

Из этого перечня видно, что управление памятью касается широкого класса объектов. Ранее в программах использовался простейший способ распределения памяти — статическое распределение, т. е. распределение памяти при трансляции программы. Статическое распределение памяти эффективно, поскольку на управление памятью не тратится ни время, ни память. В данной лабораторной работе рассматривается динамическое (во время выполнения программы) управление памятью.

Статические и динамические переменные

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

Рассмотрим пример. Пусть в программе обрабатывается матрица 300*300 целых чисел, тогда ее нужно описать следующим образом:

var M1: array[1..300,1..300] of Integer;

Такие переменные, описанные в разделе Var, Н.Вирт назвал статическими. Название "статические" они получили за то, что компилятор Паскаля может обработать их без выполнения программы, т. е. на основании лишь статического текста программы. Статические переменные можно использовать в случаях, когда память, необходимая для работы программы, предсказуема в момент написания программы.

В данном случае мы имеем наглядный пример нерационального использования памяти компьютера с применением статических переменных. Так как один элемент матрицы — целое число — занимает в памяти два байта, а общее количество элементов равно 300*300= 90000, то для размещения всей матрицы вышеописанным способом в памяти компьютера нужно 90000*2 байт = 180000 байт. Вместе с тем маловероятно, чтобы при всяком выполнении программы ей действительно были нужны одновременно все элементы такого огромного массива. К тому же все переменные, объявленные в программе, размещаются в одной непрерывной области оперативной памяти, которая называется сегментом данных. Длина сегмента данных определяется архитектурой микропроцессора 8086 и составляет 65536 байт (64 Кбайта), что также вызывает затруднения при обработке больших массивов данных.

Выходом из этого положения может быть использование динамической памяти. Динамическая память - это оперативная память компьютера, предоставляемая программе при ее работе, за вычетом сегмента данных (64 Кбайта), стека (обычно 16 Кбайт) и собственно тела программы. Размер динамической памяти определяется всей доступной памятью компьютера и составляет 200...400 Кбайт.

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

Указатели

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

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

Типизированные указатели

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

Для объявления типа указателя Р на целочисленный тип данных следует записать:

Type Р = ^Integer;

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

Var

Р1, Р2: Р; {Тип Р введен выше}

R: ^Byte;

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

Например:

RecPtr = ^RecordType;

RecordType=record

Name: string[20];

Number: integer;

end;

В данном примере RecPtr описывается как указатель на переменную RecordType. Базовый тип RecordType описывается в той же самой последовательности определений типов, что и тип RecPtr.

Реально значения ссылочных типов (указателей) содержат адреса расположения в памяти конкретных значений базового типа. В персональном компьютере адреса задаются совокупностью двух шестнадцатиразрядных слов, которые называются сегментом и смещением. Сегмент - это участок памяти, имеющий длину 65536 байт (64 Кбайт) и начинающийся с физического адреса, кратного 16 (0, 16, 32, 48 и т.д.). Смещение указывает, сколько байт от начала сегмента необходимо пропустить, чтобы обратиться к нужному адресу. Таким образом, по своей внутренней структуре любой указатель представляет собой совокупность двух слов (данных типа Word), трактуемых как сегмент и смещение.

Абсолютный адрес образуется следующим образом: сегмент* 16+смещение.

Для того чтобы присвоить переменной ссылочного типа некоторое значение, можно воспользоваться унарной операцией взятия указателя, которая строится из знака этой операции-символа @ (амперсант) и одного операнда-переменной. Например, если имеется описание переменной I целого типа:

Vаr I: integer;

то применение этой операции к переменной I: @I дает в качестве результата значение типа указатель на целое. Аналогичный результат получится и в результате операции Р = ^Integer;

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

Например, если есть описание:

Var А: array[1..10] of integer;

то конструкция @А[I] имеет смысл указателя на I-е целое в массиве А и также может участвовать в присваивании: Р:= @А[I].

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

Среди всех возможных указателей в Турбо Паскале выделяется один специальный указатель, который "никуда не указывает". Можно представить такую ситуацию: в адресном пространстве оперативной памяти компьютера выделяется один адрес, в котором заведомо не может быть размещена никакая переменная. На это место в памяти и ссылается такой нулевой (или пустой) указатель, который обозначается словом Nil. Указатель Nil считается константой, совместимой с любым ссылочным типом, поэтому его значение можно присваивать любому указателю. Обычно значение Nil присваивают указателю, когда его указание надо отменить или в начале инициализации программы. Это позволяет проверять значение указателя, прежде чем присваивать ему какое-либо значение.

Нетипизированный указатель (pointer)

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

Переменные типа Pointer не могут быть разименованы: указание символа ^ после такой переменной вызывает появление ошибки. Как и значение, обозначаемое словом Nil, значения типа Pointer совместимы со всеми другими типами указателей.

Над значениями ссылочных типов допускаются две операции сравнения на равенство и неравенство, например @Х <> @Y или Р1 = Р2.

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