Теория языков программирования методов трансляции (стр. 40 )

9.3.  Обстановка выполнения процедур

При вызове процедуры необходимо вносить поправку в стек рабочего времени, чтобы рамка, соответствующая телу процедуры, была немедленно помещена над рамкой, соответствующей блоку, в котором содержится ее описание. Иначе адреса, введенные во время прогона (номер блока, смещение), будут относиться к другой рамке. На практике, чтобы не изменять стек при исключении из него нескольких рамок, можно изменить дисплей. Тогда доступ через него даст изменение стека. Это изменение должно выполняться сразу же после вычисления параметров (рис. 8.7).

До вхождения в процедуру		После вхождения в процедуру
Дисплей Стек		Дисплей Стек

Рис. 8.7. Изменение дисплея при входе в процедуру

Конечно, после выхода из процедуры дисплей должен быть восстановлен.

Один из способов связи между фактическими и формальными параметрами заключается в введении дополнительного уровня (его называют псевдоблоком), в котором вычисляются фактические параметры. По завершению их вычисления рамку стека, соответствующую этому блоку, можно использовать в качестве рамки для тела процедуры после видоизменения дисплея. Это позволяет не прибегать к присвоению параметров.

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

Используя комбинацию рассмотренных вариантов, можно организовать работу компилятора в режиме оптимального времени либо оптимальной памяти.

9.4.  «Куча»

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

A

E

B

C

D

Рис. 8.8. Список

Каждый список состоит из головной части – литеры или указателя на другой список и хвостовой – указателя на другой список или нулевого списка. Список рис.8.8 можно записать в виде:

.

Скобки употребляются для разграничения списков и подсписков.

Память для любого элемента списка должна выделяться глобально, т. е. на время действия всей программы. Глобальная память не может ориентироваться на стек, поскольку его распределение и перераспределение не соответствует принципу «последним вошел – первым вышел». Обычно для глобальной памяти выделяется специальный участок памяти, называемый «кучей». Компилятор может выделять память и из стека, и из кучи, и в данном случае уместно сделать так, чтобы эти два участка «росли» навстречу друг другу с противоположных сторон запоминающего устройства (рис. 8.9).

СТЕК

КУЧА

Рис. 8.9. Структура распределения памяти

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

Размер стека увеличивается и уменьшается упорядоченно по мере входа в блоки и выхода из блоков. Размер же кучи может только увеличиваться, если не считать «дыр», которые могут появляться за счет освобождения отдельных участков памяти. Существует две разные концепции регулирования кучи. Одна из них основана на так называемых счетчиках ссылок, а другая – на сборке мусора.

9.5.  Счетчик ссылок

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

Для простоты допустим, что в каждой ячейке есть три поля, первое из которых отводится для счетчика ссылок. Если Х – идентификатор, указывающий на список, то его значение может быть представлено

X

1

A

1

B

1

C

Результат присвоения Y-ку второго элемента списка («хвоста» Х)

X

1

A

2

B

1

C

Y

Результат следующего присвоения

X

0

A

1

B

1

C

Y

На единицу уменьшился не только счетчик ссылок ячейки, на которую указывает Х, но и ячейка, на которую указывает данная ячейка.

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

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

Счетчики ссылок в действительности нет необходимости хранить в самих ячейках. Их можно хранить где-нибудь в другом месте, лишь бы соблюдалось полное соответствие между адресом ячейки и его счетчиком ссылок.

Основными недостатками организации такого регулирования памяти являются:

1)  Память, выделяемая для определенных структур, не восстанавливается с помощью описанного алгоритма, даже, если не будет доступа ни к одному из объемов памяти. Это четко видно на примере циклического списка (рис 8.10).

	1	A							1	B
						C	1

Рис. 8.10. Циклический список

Ни один из его счетчиков не является нулем, хотя никакие указатели на него извне не указывают. Этот объем памяти не восстановится никогда;

2)  Обновление счетчиков ссылок представляет собой значительную нагрузку для всех программ. Это противоречит принципу Бауэра – «простые программы не должны расплачиваться за дорогостоящие языковые средства, которыми не пользуются».