11 Динамические структуры данных.
Указатели
Статические и динамические структуры данных.
Динамическая память
Типы данных, рассмотренные до сих пор, являются статическими. Данные этих типов имеютодини тот жеразмер и форматна протяжении выполнения всего блока, в котором были объявлены.
Во время компиляциидля каждой статической переменной (и типизованной константы) в соответствии с ее типом выделяется определенный объем памяти, который нельзя использовать для других целей до завершения работы программы. Количество переменных является постоянным на протяжении всей работы программы.
Динамическиетипы данныхпозволяют изменять количество данныхв программево время выполненияпрограммы, образовывать, выделять для них память и уничтожать, когда в них отпадет необходимость.
Необходимость в них возникает при обработке больших объемов данных (поскольку память, выделяемая под статические данные, не может превышать 64К), а также в случае использования данных, объем и содержание которых существенно меняется по ходу выполнения программы (т.е. для организации структур данных, которые по своей природе динамичны).
Во время работы программы динамические переменные располагаются в специальной динамически распределяемой области памятиили куче (Heap).
Во время выполнения программы система выделяет три сегмента:сегмент кода, сегмент данных, сегмент стека.Префиксный сегментпрограммы (PSP) — область длиной 256Б — строитсяDOSпри загрузке файлаимя.exe. Адрес сегментаPSPсохраняется в предопределенной переменнойPrefixSegдлиной в слово.
Сегмент кодаадресуется через регистрCS(содержимое не изменяется во время выполнения программы). Основная программа занимает первый сегмент кода. Следующие сегменты занимают коды модулей (если они есть) в порядке, обратном описанному в предложенииUses. Последний сегмент кода занят кодом модуляSystem. Размер каждого отдельного сегмента кода не может превышать 64К, а общий размер сегмента кода ограничен только объемом имеющейся памяти.
Сегмент данныхадресуется через регистрDS(содержимое не изменяется во время выполнения программы). Он содержит все типизованные константы, за которыми следуют все глобальные переменные. Размер сегмента данных не может превышать 64К.
В сегменте стекарасполагаются локальные переменные процедур и функций. При входе в программу регистр сегмента стекаSSи указатель стекаSPзагружаются так, что адресSS:SPуказывает на первый байт, следующий за сегментом стека. Содержимое регистраSSв процессе выполнения программы не изменяется, аSPперемещается вниз, пока не достигнет нижней границы стека. Размер стека не может превышать 64К. По умолчанию ему назначается размер 16К (можно изменить с помощью директивы компилятора {$M}, а с помощью директивы {$S} проверить на переполнение).
Оверлейный буфериспользуется для программ с перекрытиями.
Схема распределения памяти программы на Паскале:
|
Увеличение адресов → |
|
|
Верхняя граница памяти операционной системы |
| |
|
|
Куча ┌───^───┐ |
Свободная Память |
FreePtr HeapPtr | ||
|
Динамически распределяемая область памяти |
↑ ( расширение ) |
HeapOrg | |||
|
|
|
Оверлейный Буфер |
OvrHeapEnd OvrHeapOrg | ||
|
|
Область стека ( ≤ 64 К , по умолч. 16 К ) ┌───^───┐ |
Сегмент Стека |
( расширение ) ↓ |
| |
|
|
Свободная область стека |
SSeg : SPtr
SSeg : 0000 | |||
|
Образ файла имя.exe ┌──────────────^───────────────┐ |
Сегмент данных ( ≤ 64 К ) ┌─^─┐ |
Глобальные переменные |
| ||
|
Типизованные константы |
DSeg : 0000 | ||||
|
Сегмент кода ┌────────^────────┐ |
Сегмент кода модуля System ( ≤ 64 К ) |
| |||
|
Сегмент кода первого модуля ( ≤ 64 К ) |
| ||||
|
. . . |
| ||||
|
Сегмент кода последнего модуля ( ≤ 64 К ) |
| ||||
|
Основная программа ( ≤ 64 К ) |
CSeg : 0000 | ||||
|
256 Б |
Префиксный сегмент программы (PSP) |
PrefixSeg | |||
В динамически распределяемой области памяти(Heap) сохраняются динамические переменные. Она занимает всю свободную память или часть свободной памяти, оставшуюся при выполнении программы. Действительный размер области зависит от максимального и минимального значений, которые можно установить с помощью директивы компилятора {$M}. Гарантированный минимальный размер области не может быть меньше минимального значения, установленного для данной области. Максимальный размер никогда не может превышать заданного для нее максимального значения. Если указанный минимальный объем недоступен — программа не выполняется. По умолчанию минимальный размер равен 0К, максимальный — 1МБ (т.е. вся свободная адресуемая память).
Управляет (непосредственно при работе программы) динамически распределяемой областью памятипрограмма динамического распределения памяти (администратор кучи)— часть библиотеки модуляSystem. Динамически распределяемая область памяти — структура, похожая на стек, но расширяющаяся от младших адресов к старшим. Нижняя граница записывается в переменнойHeapOrg, верхняя — вHeapPtr. При каждом выделении памяти для динамической переменнойHeapPtrперемещается вверх.