Динамическое распределение памяти для данных в ходе
компиляции и выполнения программ
При динамическом распределении памяти на этапе трансляции память распределяется для данных только внутри блоков, относительно начала области данных каждого блока. Это производится в ходе просмотра таблицы идентификаторов также, как и при статическом распределении, только начальные адреса областей данных для всех блоков принимаются равными T[i] = LS, где LS – длина служебной информации, размещаемой в начале области данных каждого блока. В процессе выполнения программы при входе в блок (в том числе и в процедуру) выделяется память для области данных блока.
Динамическое распределение памяти будет рассматриваться на примере программы:
program PR; Дерево блоков для данной программы
var a: real; определяет статические цепочки вло-
procedure P1; женности блоков:
var x,y,z: real; ╔════╗ уровень 1
begin ... end; ╔═════╗ ║ PR ║ ╔════╗ уровень 2
procedure P2; ║ P1 ╟──╢ a ╟──╢ P2 ║
var g: real; ║x,y,z║ ╚════╝ ║ g ║
procedure P3; ╚═════╝ ╚═╤══╝
var b,a: real; ╔═╧══╗ уровень 3
begin ... P1; ... end; ║ P3 ║
begin ... P3; ... end; ║ d,a║
begin ... P2 ... end. ╚════╝
Последовательность работы блоков определяет динамическую цепочку вызова блоков, представленную на рисунке 10.2.
При динамическом распределении памяти адрес любой переменной определяется как сумма базового адреса области данных блока и смещения переменной от начала этой области. Для хранения адресов областей данных используется массив указателей начала областей данных блоков (обычно базовых регистров) – УНБ[1], УНБ[2], ... . В соответствии с правилами определения областей действия имен переменных при работе блока уровня i должны быть загружены указатели УНБ[1]...УНБ[i] в соответствии со статической цепочкой вложенности блоков.
Так, если обозначить [V] – адрес начала области данных блока V, то после входа в блок PR должно быть: УНБ[1]=[PR], после входа в блок P2: УНБ[1]=[PR], УНБ[2]=[P2], после входа в блок P3: УНБ[1]=[PR], УНБ[2]=[P2], УНБ[3]=[P3]; после входа в блок P1: УНБ[1]=[PR], УНБ[2]=[P1].
Средством реализации динамического распределения памяти является стек. Обозначим:
УС – указатель стека;
k – номер блока;
УБ[k] – уровень блока k;
УБТ – уровень текущего блока;
n[k] – размер области данных блока k;
УНБО[k] – значение указателя начала области данных блока,
в котором описана процедура или содержится блок k;
УНБВ[k] – значение указателя начала области данных блока, из
которого произошел вызов процедуры или вход в блок k;
УБВ[k] – уровень блока, из которого произошел вызов процедуры
или вход в блок k.
Связующей информацией блока k называется тройка значений (УНБО[k], УНБВ[k], УБВ[k]). Эта информация помещается в начало области данных каждого блока. Для самого внешнего блока связующей информацией считается (0,0,0).
При входе в самый внешний блок значения УС и УНБ[1] устанавливаются на начало стека, для уровня текущего блока принимается начальное значение – УБТ = 1. Далее, при входе в любой блок k выполняется подпрограмма:
ВХОД: СТЕК(УС) = (УНБ[УБ[k]-1], УНБ[УБТ], УБТ);
УБТ = УБ[k];
УНБ[УБ[k]] = УС;
УС = УС + n[k]+ LS; // LS - длина связующей
// информации
Для приведенного примера после входов в процедуры P2, P3, P1 имеем состояние стека:
CТЕК Вход в PR Вход в P2 Вход в P3 Вход в P1
┌───────────┐
PR:│(0,0,0) │ УНБ[1]=[PR] УНБ[1]=[PR] УНБ[1]=[PR] УНБ[1]=[PR]
│ a │ УБТ=1 УНБ[2]=[P2] УНБ[2]=[P2] УНБ[2]=[P1]
P2:│[PR],[PR],1│<─ УС УБТ=2 УНБ[3]=[P3] УБТ=2
│ g │ ┌─ УС УБТ=3 ┌─ УС
P3:│[P2],[P2],2│<───────────┘ ┌── УС │
│ b │ │ │
│ a │ │ │
P1:│[PR],[P3],3│<───────────────────────┘ │
│ x │ │
│ y │ │
│ z │ │
└───────────┘<────────────────────────────────────┘
Первые элементы связующей информации определяют цепочку адресов областей данных блоков в соответствии со статической цепочкой вложенности блоков (P1→PR, P3→P2→PR). Вторые элементы определяют цепочку адресов в соответствии с динамической цепочкой вызова блоков (P1→P3→P2→PR).
При выходе из процедуры нужно восстановить УС, УБТ и цепочку УНБ. Алгоритм подпрограммы ВЫХОДПР:
восстанавливается УС = УНБ[УБТ] и из стека извлекаются УНБО[k], УНБВ[k], УБВ[k];
восстанавливается УБТ = УБВ[k];
если УБТ = 1, то конец, т.к. УНБ[1] никогда не модифицируется;
по динамической цепочке восстанавливается последний указатель УНБ[УБТ] = УНБВ[k];
для блоков на уровнях j = УБТ-1,УБТ-2,...,2 по статической цепочке восстанавливается УНБ:
Таким образом, для примера восстанавливается:
УНБ[1]=[PR] УБТ = 3
УНБ[2]=[P2]
УНБ[3]=[P3]
Для приведенного примера после выхода из процедур P1, P3, P2 имеем состояние стека:
CТЕК Выход из P1 Выход из P3 Выход из P2
┌───────────┐ УНБ[1]=[PR] УНБ[1]=[PR] УНБ[1]=[PR]
PR:│(0,0,0) │ УНБ[2]=[P2] УНБ[1]=[P2] УБТ=1
│ a │ УНБ[3]=[P3] УБТ=2
P2:│[PR],[PR],1│<─┬───────────┐ УБТ=3 ┌── УС
│ g │──┘освобождено└────────────────────┘
P3:│[P2],[P2],2│<─┬────────────────────── УС
│ b │ │освобождено
│ a │──┘
P1:│[PR],[P3],3│<─┬───────── УС
│ x │ │
│ y │ │освобождено
│ z │──┘
└───────────┘
Выход из любого блока, не являющегося вызванной процедурой, по концу работы блока реализуется подпрограммой:
ВЫХОДБЛК:
УС = УНБ[УБТ];
УБТ = УБТ-1;
В частности, для приведенного примера с помощью подпрограммы ВЫХОДБЛК реализуется выход из блока PR по концу работы всей программы. |
Скачать 0.64 Mb.