Этот подраздел посвящен детальному разбору механизма ведения учета свободных блоков в куче, и может быть опущен при ознакомительном чтении без потерь для целостности изложения. {205}
При использовании процедур Dispose и FreeMem куча становится фрагментированной, т. е. в ней появляются свободные блоки. Эти блоки могут возникать в любом порядке и со временем куча может превратиться в подобие решета. Но работоспособность кучи не исчезнет.
Адреса и размеры свободных блоков сохраняются в так называемом списке свободных блоков, который имеет стековую структуру и растет сверху вниз от верхней границы области кучи навстречу указателю заполнения кучи HeapPtr. При попытке размещения динамической переменной осуществляется просмотр списка свободных блоков. Если найден свободный блок подходящего размера, то именно он и используется.
Указатель на список свободных блоков хранится в предопределенной системной переменной FreePtr типа Pointer. Эта переменная фактически указывает на массив записей типа FreeList, т.е. соответствует типу FreeListP:
TYPE
FreeRec = RECORD { Указатели на }
OrgPtr, EndPtr: Pointer; { начало и конец }
END; { блока в куче }
FreeList = Array [0..8190] of FreeRec;
FreeListP = ^FreeList; { ссылка на массив записей }
Поля OrgPtr и EndPtr каждой записи определяют начало и конец каждого свободного блока (EndPtr, точнее говоря, указывает на первый байт после блока) и являются нормализованными указателями.
Фактическое значение самой FreePtr не является постоянным, а как бы перемещается в диапазоне от верхней границы кучи до максимальной длины списка свободных блоков.
Число освобожденных пустых блоков (элементов в массиве FreeList) на текущий момент можно вычислить по формуле
FreeCount:= (8192 - Ofs(FreePtr^) div 8) mod 8192;
Максимальное число свободных блоков, которые могут существовать одновременно, равно емкости массива FreeList (8191 блок). Число это достаточно велико, чтобы достичь его на практике. Если же это удастся, то возникнет фатальная ошибка и останов программы.
Ошибка может возникнуть также, когда куча заполнена и список свободных блоков почти смыкается с верхней границей заполнения кучи. При этом попытка освобождения блока, не лежащего на вершине кучи, будет приводить к расширению списка и возникновению ошибочной ситуации. Для решения этой проблемы монитор кучи использует системную переменную FreeMin типа Word, которую можно применять для управления минимальным размером {206} участка памяти между HeapPtr и списком свободных блоков (FreePtr). Для этого необходимо в FreeMin записать гарантированный размер этого участка в байтах. Чтобы при этом не происходило потерь памяти, значение размера должно быть вычислено как
ЧИСЛО_ЭЛЕМЕНТОВ_СПИСКА_В_ЗАЗОРЕ*8,
где 8 — размер записи FreeRec. Когда значение FreeMin не равно нулю, вызовы процедур New и GetMem будут неэффективными, если они пытаются сделать расстояние между HeapPtr и FreePtr меньше FreeMin. Кроме того, MaxAvail и MemAvail будут вычитать FreeMin из возвращаемых значений.
Иногда необходимо знать величину еще ни разу не использованного пространства кучи (между значениями указателей FreePtr сверху и HeapPtr снизу). Функция HeapAvail, анализирующая размер именно этого пространства (без учета освобожденных блоков в куче), приводится на рис. 11.7.
| {$М 1024, 4000, 4000} (*заданные параметры кучи для теста*) FUNCTION HeapAvail: LongInt; VAR LongSeg, LongFreePtr, LongHeapPtr: LongInt; BEGIN LongSeg:= Seg(FreePtr^)+$1000*Byte(Ofs(FreePtr^)=0); LongFreePtr:=(LongSeg * 16) + Ofs(FreePtr^); LongSeg:= Seg(HeapPtr^); LongHeapPtr:= (LongSeg*16) + Ofs(HeapPtr^); HeapAvail:= LongFreePtr – LongHeapPtr END; procedure WriteAvail; { вспомогательная процедура } begin WriteLn(' MemAvail=', MemAvail:6, ' MaxAvail=', MaxAvail:6, ' HeapAvail=’, HeapAvail:6) end; {WriteAvail} VAR { ПРИМЕР АНАЛИЗА ПАМЯТИ КУЧИ } P1, P2: Pointer; BEGIN WriteLn('Начало работы:'); WriteAvail; GetMem (P1, 1000); { отводится 1000 байт в куче } GetMem (Р2, 10); { отводится 10 байт в куче } WriteLn('Размещены в куче 2 переменные(1000 и 10 б)'); WriteAvail; FreeMem(P1, 1000); { освобождается первый блок } {207} {Сейчас в куче появилась "дыра", а в списке свободных блоков появились ее координаты, уменьшив кучу на 8 байт.} WrfteLn('Освобождена ссылка на 1000 байт:'); WriteAvail; FreeMem(P2, 10); { освобожден второй блок } { Теперь вся куча пуста, и нет нужды в списке блоков. } WriteLn('Освобождена ссылка на 10 байт:'); WriteAvail; ReadLn { пауза до нажатия клавиши ввода } END. |
Рис. 11.7 (окончание)
Заметьте, что все локальные параметры в функции HeapAvail имеют тип LongInt, чтобы хранить десятичные значения ненормализованных (абсолютных) адресов. Чтобы избежать потери порядка из-за превышения диапазона типа Word, значения функций Seg(...) перед умножением переписываются в переменную более «длинного» типа LongInt.
Следующий вопрос, связанный со списком свободных блоков, — это потенциальная проблема дробности. Она связана с тем, что дробность в мониторе кучи равна одному байту. Это означает, что при размещении одного байта переменная будет занимать один байт. При размещении и удалении в произвольном порядке большого числа переменных или блоков различной длины могут появляться свободные блоки небольшого размера, причем число таких блоков может быть большим. Так, например, при освобождении блока размером 20 байт и размещении вслед за этим блока размером 19 байт, появится свободный блок длиной 1 байт, который может находиться в списке свободных блоков довольно долго. Для решения этой проблемы справочное руководство по Турбо Паскалю советует воспользоваться следующим приемом. Каждый раз выделять и впоследствии освобождать блок с размером, кратным какому-либо целому числу байтов. Для этого необходимо переопределить процедуры GetMem и FreeMem. Например, если мы хотим выделять память блоками с размером, кратным 16 байт, то переопределения GetMem и FreeMem будут выглядеть следующим образом:
PROCEDURE GetMem(VAR P: Pointer; Size: Word);
BEGIN
System.GetMem(P, (Size+15) and $FFF0);
END; { GetMem } {208}
PROCEDURE FreeMem(VAR P: Pointer; Size: Word);
BEGIN
System.FreeMem(P, (Size+15) and $FFF0);
END; { FreeMem }
В этом случае минимальный размер свободного блока будет не меньше 16 байт. Однако это будет справедливо до тех пор, пока не будут применены процедуры New и Dispose. Процедура New, например, может для переменной, имеющей размер, не кратный 16 байт, использовать такой свободный блок, что останется пустой излишек с размером менее 16 байт. И уж он-то будет находиться в памяти очень долго. Ситуация осложняется еще тем, что мы теперь уже не можем так просто управлять размером выделяемого блока. Возможным средством улучшить ситуацию является приведение размера динамической переменой к величине, кратной 16 байт. Так, например, если необходимо размещать в куче переменные типа:
TYPE
Dot = RECORD x,y: Real END;
размером 12 байт (6+6), то его размер необходимо увеличить еще на 4 байта. Для этого вместо приведенного выше описания необходимо дать следующее:
TYPE
Dot = RECORD
х, у: Real;
foo: Array [1..4] of Byte
END;
Теперь при размещении переменной типа Dot память будет выделяться и, что самое главное, освобождаться блоками по 16 байт. Заметим, что в принципе можно было бы отказаться от использования процедур New и Dispose и управлять памятью с помощью одних лишь процедур GetMem и FreeMem, хотя это вызвало бы определенные трудности при работе с объектами.