Динамическая память

Все глобальные переменные и типизированные константы размещаются в одной непрерывной области оперативной памяти, которая называется сегментом данных. Длина сегмента определяется архитектурой процессора 8086 и составляет 64 Килобайта (65536 байт), что может вызвать определённые трудности при описании и обработке больших массивов данных. С другой стороны объём стандартной памяти - 640 Килобайт. Выход - использовать динамическую память.
 

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

Динамическую память обычно используют при:
1. обработке больших массивов данных;
2. разработке САПР;
3. временном запоминании данных при работе с графическими и звуковыми средствами
ЭВМ.

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

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

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

Справка: процессор 8086.
8086 имеет 16 - битовые регистры, всего 14 штук, из них:

• 12 - регистры данных и адресов;
• 1 - указатель команд (регистр адреса команды);
• 1 - регистр состояния (регистр флагов).

Регистры данных и адресов делятся на три группы:
• регистр данных;
• регистр указателей и индексов;
• регистр сегментов.

Процессор 8086 всегда генерирует 20-ти бытовые адреса за счёт добавления 16-ти битового смещения к содержимому регистра, умноженному на 16:
физический адрес = смещение + 16 * регистр сегмента.
Вместо умножения на 16 содержимое регистра сегмента используется так, как если бы оно имело четыре дополнительных нулевых бита:
пусть:
   смещение = 10H
   регистр сегмента = 2000H
тогда:

физический адрес = 20010H

У 8086 адрес ячейки задаётся номером блока и смещением, что обусловлено тем, что команды 8086 и её данные должны располагаться в разных частях памяти (в разных сегментах). Если требуется адресоваться к данным, то потребуется адресация блока памяти, с которого начинается сегмент данных (из регистра сегмента данных) и позиция желаемой ячейки в этом сегменте (смещение).

В дополнение к области памяти 1 Мбайт, 8086 может адресоваться к внешним устройствам через 65536 (64 К) портов ввода-вывода. Имеются специальные команды ввода-вывода, позволяющие иметь непосредственный доступ к первым 256 (от 0 до 255) портам. Другие команды позволяют получить косвенный доступ к порту с помощью занесения идентифицирующего его номера (0 - 65535) в определенный регистр данных. Подобно ячейке памяти любой порт может быть 8 или 16- битовым.

Распределение памяти IBM PC.
• 16 - старших байт - команды начальной загрузки системы.
• Первые 1024 ячейки - вектора прерываний.

Типы прерываний.
Существуют 2 вида прерываний - одни можно игнорировать, другие обязательно обслужить как можно скорее.
8086 может распознать 256 различных прерываний, каждому из них однозначно соответствует код типа (целое число от 0 до 255). Код используется в качестве указателя ячейки в области памяти с младшими адресами (область векторов прерываний).

1. Объявление указателей

Как правило, в Турбо-Паскале указатель связывается с некоторым типом данных (типизированные указатели).

Type
  PerPnt = ^PerRec;{указатель на переменную типа PerRec}
  PerRec = Record
    Name: String;
    Job: String;
    Next: PerPnt;
  End;
Var
  P1: ^Integer;
  P2: ^Real;

Внимание! При объявлении типа PerPnt мы сослались на PerRec, который ещё не был объявлен, это связано с тем, что существует исключение из правил для указателей, которые содержат ссылку на ещё неописанный тип данных. Это исключение сделано не случайно, так как динамическая память позволяет использовать организацию данных в виде списков (каждый элемент имеет в своём составе ссылку на соседний элемент - обратите внимание на поле Next).

В Турбо-Паскале можно объявлять указатель и не связывать его с конкретным типом данных:
Var
  PP: Pointer;

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

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

Var
  P1,P2: ^Integer;
  P3: ^Real;
  PP:Pointer;
Begin
  P1:= P2; {- верно}
  P1:= P3; {- неверно}

но можно сделать так:
  PP:= P3;
  P1:= PP;
так как ограничение не распространяются на нетипизированные указатели. Но подобные операции часто путают программиста и чреваты смысловыми ошибками.

2. Выделение и освобождение динамической памяти

Вся динамическая память – пространство ячеек, называемое кучей. Физически куча располагается в старших адресах, сразу за программой. Указатель на начало кучи храниться в предопределенной переменной HeapOrg, конец - FreePtr, текущую границу незанятой динамической памяти указывает указатель HeapPtr. Для выделения памяти под любую переменную используется процедура New. Единственным параметром является типизированный указатель:

Var
  I,J: ^Integer;
  R: ^Real;
Begin
  New(I); {под I выделяется область памяти,}
  {адрес первого байта этой области помещается в I}
End.

После выполнения этого фрагмента указатель I приобретёт значение, которое перед этим имел указатель кучи HeapPtr, а HeapPtr увеличится на два (т.к. он типа Integer); New(R) - вызовет смещение указателя на 6 байт. После того как указатель приобрёл некоторое значение, то есть стал указывать на конкретный байт памяти, по этому адресу можно разместить значения соответствующего типа:

  I^:= 2;
  R^:= 2*Pi;
Допустима запись: R^:= Sqr (R^) + I^ - 17;
Но недопустима запись: R:= Sqr (R^) + I^ - 17; так как указателю R нельзя присвоить значение вещественного выражения.

Возврат динамической памяти обратно в кучу осуществляется оператором Dispose:
  Dispose(R);
  Dispose(I); - вернут в кучу, ранее забранные 8 байт.
  Dispose(Ptr) не изменяет значения указателя Ptr, а лишь возвращает в кучу память, связанную с этим указателем. Однако повторное применение процедуры к “свободному” указателю приведет к возникновению ошибки времени исполнения. Чтобы указать, что указатель свободен, нужно использовать зарезервированное слово Nil.

К указателям можно применять операции отношения, в том числе и сравнения с Nil:

Const
 P:^Real = Nil;
. . . . . . . .
Begin
 If P = Nil then
   New (P);
. . . . . . . .
 Dispose(P);
 P:= Nil;
End.

Использование указателей, которым не присвоено значение процедурой New или каким-либо другим способом, никак не контролируется системой и может привести к непредсказуемым результатам. Многократное чередование New и Dispose приводит к “ячеистой” структуре кучи. Дело в том, что все операции с кучей выполняется под управлением особой программы, которая ведёт учёт всех свободных фрагментов в куче. При выполнении оператора New( ) эта программа отыскивает минимальный свободный фрагмент, в котором может разместиться требуемая переменная. Адрес начала найденного фрагмента возвращается в указателе, а сам фрагмент или его часть нужной длины, помечаются как занятая часть кучи.

Можно освободить целый фрагмент кучи следующим образом:

1. Перед началом выделения динамической памяти значения указателя HeapPtr запоминается в переменной-указателе с помощью процедуры Mark.
2. Выполнение программы.
3. Освобождение фрагмента кучи от заполненного адреса до конца динамической памяти с использованием процедуры Release.

Var
 P, P1, P2, P3, P4, P5: ^Integer;
Begin
 New(P1);
 New(P2);
 New(P3);
 New(P4);
 New(P5);
 Mark(P);
. . . . . . . .
 Release (P);
End.

В этом примере процедурой Mark(P) в указатель P было помещено текущее значение HeapPtr, однако память под переменную не резервировалась.

Вызов Release уничтожает список свободных фрагментов в куче, созданных Dispose, поэтому совместное применение этих процедур не рекомендуется.

Для работы с нетипизированными указателями используются также процедуры GetMem(P, Size) и FreeMem(P, Size) - резервирование и освобождение памяти.
P - нетипизированный указатель, Size - размер.

За одно обращение к куче процедурой GetMem можно зарезервировать до 65521 байт. Освобождать нужно ровно столько памяти, сколько было зарезервировано, и именно с того адреса, с которого память была зарезервирована, иначе программа не будет работать и завершаться корректно!!!

Использование нетипизированных указателей даёт широкие возможности неявного преобразования типов:
Var
  i,j: ^Integer;
  r: ^Real;
Begin
  New (i); { I:= HeapOrg; HeapPtr:= HeapOrg+2 }
  j:= i; { J:= HeapOrg }
  j^:=2;
  Dispose (i); { HeapPtr:= HeapOrg }
  New (r); { R:= HeapOrg; HeapPtr:= HeapOrg+6 }
  r^:= Pi;
  WriteLn (j^);
End.
{Будет выведено: "8578"}
{здесь преобразование не имеет никакого смысла}

Примеры использования указателей.
Динамическая память - 200..300 Кбайт. Нужно разместить массив 100 * 200 типа Extended. Требуется 100 * 200 * 10 = 200000 байт. Пробуем:
Var
  i,j: Integer;
  PtrArr: Array[1..100, 1..200] of ^Extended.
Begin
. . . . . .
  For i:= 1 to 100 do
    For j:= 1 to 200 do
     New (PtrArr [i,j]);
. . . . . .
End.

Теперь к любому элементу можно обратиться: PtrArr[i,j]^:=...; Но длина внутреннего представления указателей 4 байта, поэтому потребуется ещё 100*200*4 = 80000 байт, что превышает размер сегмента (65536 байт), доступный для статического размещения данных.

Можно было бы работать с адресной арифметикой (арифметикой над указателями), то есть не создавать массив указателей, а вычислять адрес элемента непосредственно перед обращением к нему. Однако в Турбо-Паскале над указателями не определены никакие операции, кроме присваивания и отношения. Но задачу решить можно:
Seg(x) - возвращает сегментную часть адреса.
Ofs(x) - возвращает смещение.
x - любая переменная, в том числе и та, на которую указывает указатель.

Далее с помощью Ptr(Seg, Ofs: Word): Pointer можно создать значение указателя, совместимое с указателем любого типа.

Таким образом, сначала с помощью GetMem забираем из кучи несколько фрагментов подходящей длины (не более 65521). Удобно по строкам 200 * 100 = 20000 байт. Начало каждого фрагмента запоминается в массиве PtrStr из 100 указателей. Теперь для доступа к любому элементу строки нужно вычислить смещение этого элемента от начала строки и сформировать указатель.
Var
  i,j: Integer;
  PtrStr: Array [1..100] of Pointer;
  Pr: ^Extended;
Const
  SizeOfExt = 10;
Begin
  For i:= 1 to 100 do
    GetMem (PtrStr[i], SizeOfExt*200);
. . . . . . . . . . . . . . . .
    Pr:= Ptr(Seg(PtrStr[i]^), Ofs(PtrStr[i]^) + (j - 1) * SizeOfExt);
    {Обращение к элементу матрицы [i,j]}
End;

далее работаем с Pr^:=. . . и т.д.
Полезно ввести две вспомогательных функции GetExt и PutExt. Каждая из них будет обращаться к функции вычисления адреса AddrE.
Program Demo;
Const
  SizeOfExt = 10;
  N = 100;
  M = 200;
Type
  ExtPoint = ^Extended;
Var
  i,j: Integer;
  PtrStr: Array[1..N] of Pointer;
  S: Extended;

  Function AddrE(i,j: Word): ExtPoint;
  Begin
    AddrE:= Ptr(Seg(PtrStr[i]^), Ofs(PtrStr[i]^) + (j - 1) * SizeOfExt);
  End;

  Function GetExt(i,j: Integer): Extended;
  Begin
   GetExt:= AddrE(i,j)^;
  End;

  Procedure PutExt(i,j: Integer; X: Extended);
  Begin
   AddrE(i,j)^:= X;
  End;

  Begin {main}
   Randomize;
   For i:=1 to N do
   Begin
    GetMem (PtrStr[i], M*SizeOfExt);
    For i:= 1 to m do
      PutExt(i, j, Random(255));
   End;
   S:= 0;
  For i:= 1 to N do
   For j:= 1 to M do
    S:= S + GetExt(i,j);
   WriteLn(S/(N*M));
End.

Мы предполагали, что каждая строка размещается в куче с начала границы параграфа и смещение каждого указателя PtrStr ровно 0. В действительности при последовательных обращениях к GetMem начало очередного фрагмента следует за концом предыдущего и может не попасть на границу сегмента. В результате при размещении фрагментов максимальной длины (65521 байт) может возникнуть переполнение при вычислении смещения последнего байта.

3. Процедуры и функции для работы с динамической памятью

• Функция Addr - возвращает результат типа Pointer, в котором содержится адрес аргумента.
• Addr(X), x - любой объект программы. Возвращаемый адрес совместим с указателем любого типа. Аналогично операции @.
• Функция CSeg - возвращает значения хранящееся в регистре CS (в начале работы программы в CS содержится сегмент начала кода программы), результат CSeg - слово типа Word.
• Процедура Dispose(x) - возвращает в кучу фрагмент динамической памяти, зарезервированный за типизированным указателем x.
• Функция DSeg - возвращает значение хранящиеся в регистре DS (в начале работы в DS - сегмент начала данных программы), результат - типа Word.
• Процедура FreeMem - возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за нетипизированным указателем. FreeMem(P, Size), P - нетипизированный указатель. Size - длина фрагмента, подлежащего освобождению.
• Процедура GetMem(P, Size) - резервирует память (за одно обращение не более 65521 байт), если нет свободной памяти - ошибка времени исполнения.
• Процедура Mark(Ptr) запоминает текущее значение указателя кучи HeapPtr. Ptr - указатель любого типа, в нём будет возвращено HeapPtr. Используется совместно с Release для освобождения части кучи.
• Функция MaxAvail - возвращает размер (в байтах) наибольшего непрерывного свободного участка кучи. Результат типа LongInt. За один вызов New или GetMem нельзя зарезервировать значение большее, чем возвращаемое этой функцией.
• Процедура New(TP) - резервирует фрагмент кучи для размещения переменной. TP - типизированный указатель (за одно обращение не более 65521байт).
• Функция MemAvail - возвращает размер (в байтах) общего свободного пространства кучи. Результат типа Longint.
• Функция Ofs(X) - возвращает значение типа Word, содержащее смещение адреса указанного объекта. X - выражение любого типа или имя процедуры.
• Функция Ptr(Seg, Ofs) - возвращает значение типа Pointer по заданному сегменту и смещению. Значение, возвращаемое функцией, совместимо с указателем любого типа.
• Процедура Release(Ptr) - освобождает участок кучи. Рtr - указатель любого типа, в котором сохранено процедурой Mark значение указателя кучи. Освобожденный участок кучи - от адреса в Ptr до конца. Одновременно уничтожается список свободных фрагментов, созданных по Dispose и FreeMem.
• Функция Seg(X) - возвращает значение типа Word, содержащее сегмент адреса указанного объекта.
• Функция SizeOf(X) - возвращает длину (в байтах) внутреннего представления указанного объекта. X - имя переменной, функции или типа.

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

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

Program LostReference;
Type
  PPerson = ^Person;
  Person = Record
. . . .
  End;

Procedure GetPerson;
Var
  Р: РРerson;
Begin
  P:= New(PPerson);
End;

Begin
  WriteLn(MemAvail);
  GetPerson;
  Writeln(MemAvail);
End.

Вызов New в процедуре GetPerson приводит к отведению памяти для динамической переменной типа Person. Указатель на эту переменную присваивается переменной Р. Рассмотрим ситуацию, возникающую после выхода из процедуры GetPerson. По правилам блочности все локальные переменные подпрограммы перестают существовать после ее завершения. В нашем случае исчезает локальная переменная Р. Но, с другой стороны, область памяти, отведенная в процессе работы GetPerson, продолжает существовать, так как освободить ее можно только явно, посредством процедуры Dispose. Таким образом, после выхода из GetPerson отсутствует какой бы то ни было доступ к динамической переменной, так как единственная "ниточка", связывавшая ее с программой - указатель Р - оказался потерянным при завершении GetPerson. Вывод на печать общего объема свободной памяти до и после работы GetPerson подтверждает потерю определенной области.

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

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

Var
  P: Integer;

  Procedure X1;
  Var
    i: Integer;
  Begin
    i:= 12345;
    P:= @i;
    WriteLn(P^); { напечатает 12345 }
  End;

  Procedure X2;
  Var
    j: Integer;
  Begin
    j:= 7777;
    WriteLn(P^); { напечатает 7777, а не 12345 }
  End;

Begin
  X1;
  X2;
End;

В этом примере глобальная ссылочная переменная Р первоначально (в процедуре X1) устанавливается на локальную переменную i. После завершения процедуры X2 переменная i исчезает, указатель Р “повисает”. Вызов процедуры Х2 приводит к тому, что на место, локальной переменной i, будет помещена локальная переменная j, и указатель Р теперь ссылается на нее, что подтверждает результат второго вызова WriteLn.

Таким образом, смысл указателя Р зависит в данном случае не от семантики решаемой задачи, a от системных особенностей ее функционирования, что может привести к неожиданным эффектам. Аналогичные ситуации возможны при повторном использовании областей динамической памяти: если на освобожденную область остался указатель, то он может быть (по ошибке) использован после повторного выделения этой памяти для другой переменной, что опять- таки не будет "замечено" системой, но может сделать поведение программы непредсказуемым.