А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 111
Текст из файла (страница 111)
Теперь рассмотрим, что делает Ь. Мы знаем, что в некоторой точке она использует свой параметр Г", применение которого состоит в вызове д. В стеке появляется запись активации для И, как показано на рис. 7.13, б. Корректная связь доступа для размещения в записи активации находится в значении параметра Г"; эта связь указывает на запись активации для с, поскольку с непосредственно окружает определение и'. Заметим, что Ь оказывается в состоянии установить корректное значение связи доступа, несмотря на то, что Ь находится вне области видимости определения с. 7.3.8 Дисплеи Одна из проблем обращения к нелокальным данным при помощи связей доступа заключается в том, что, когда глубина вложенности становится большой, может потребоваться пройти по длинной цепочке связей доступа для достижения необходимых данных.
Более эффективная реализация использует вспомога- 552 Глава 7. Среды времени выполнения тельный массив г1, именуемый дисцаеем~ (с11яр1ау), который содержит по одному указателю для каждой глубины вложенности. Мы договариваемся, что в любой момент времени И [з] представляет собой указатель на наивысшую запись активации в стеке для процедуры с глубиной вложенности з. Пример работы с дисплеем приведен на рис. 7.14.
Например, на рис. 7.14, г мы видим дисплей г1, элемент г! [1] которого хранит указатель на запись активации для лог!, наивысшей (и единственной) записи активации для функции с глубиной вложенности 1, Аналогично г! [2] хранит указатель на запись активации для ехспапде — наивысшую запись для глубины 2, а г! [3] — указатель на запись активации для рак!!у!оп — наивысшунз запись для глубины 3.
Преимущество использования дисплея состоит в том, что прн выполнении процедуры р, которой требуется доступ к элементу сг некоторой процедуры 9, нам достаточно провести поиск только в с! [!], где г — глубина вложенности г1; мы следуем по указателю г! [з] в запись активации для д, в которой с известным смешением находится х. Компилятору известно значение з, так что он в состоянии сгенерировать код для обращения к х с использованием д [з] и смещения т относительно вершины записи активации для 9. Таким образом, коду никогда не приходится следовать по длинной цепочке связей доступа.
Для корректной поддержки дисплея мы должны сохранять предыдущие значения записей дисплея в записях активации. Если вызывается процедура р с глубиной вложенности пр и ее запись активации не первая в стеке для процедур с глубиной вложенности пр, то запись активации для р должна хранить предыдущее значение г! [и ], которое теперь указывает на данную активацию р. При возврате из процедуры р и удалении ее записи активации из стека мы восстанавливаем значение г1 [пр] таким, каким оно было до вызова р.
Пример 7.9. На рис. 7.14 показано несколько шагов управления дисплеем. На рнс. 7.14, а функция зог! с глубиной вложенности 1 вызывает г7гг!с!тогу(1.,9) с глубиной вложенности 2. Запись активации для ди!сЬог! содержит место для хранения старого значения д [2!, которое в силу того, что к этому моменту в стеке нет записей активации для процедур с глубиной вложенности 2, представляет собой нулевой указатель. На рис. 7.14, б г7и!с!сепг! (1, 9) вызывает г!и!с!Ьог! (1, 3). Поскольку оба вызова имеют глубину 2, указатель на г7тс!гхог! (1,9), хранившийся в 4 [2], должен быть сохранен в записи активации для з7и!с!слог! (1, 3).
Указатель в !1[2] после этого делается указывающим на уи!с~Ьог! (1, 3). Далее вызывается функция риг!!г!оп. Эта функция имеет глубину вложенности 3, так что сейчас впервые используется элемент с![3], который становится 5 В русскоязычной литературе по компиляции этот термин появился в Г960-е годы в виде кальки аигз~ийского йзр!ау — "выставка", "показ". Ввиду локальности его использования мы оставляем его таким же. По сути же ои озиачаег стек ссылок иа записи активации.
— Прин, ред. 7.3. Доступ к нелокальным данным в стеке :"'ЕЛ д1)1 4121 а) д))1 4121 431 )1! 1 )121 д)з1 Рис. 7.14. Работа с дисплеем указывающим на запись активации для рагг!г!оп. Запись активации для раггй!оп содержит место для хранения предыдущего значения о [3[, но в данном случае такового нет, так что указатель остается нулевым. Состояние стека и дисплея в этот момент показано на рис.
7.14, в. После этого функция раг)!г!ол вызывает функцию ехсЬище. Эта функция имеет глубину вложенности 2, так что ее запись активации хранит старый указатель !1 [2], который вел к записи активации для !7и!с7гзогг (1, 3). Заметим, что указатели дисплея "пересекаются", т.е. 0 [3[ указывает на место в стеке, находящееся ниже места, на которое указывает 0 [2[. Однако это вполне корректная ситуация— 554 Глава 7. Среды времени выполнения функция ехсйалде может обращаться только к своим данным и данным функции хогг посредством указателя Н(1].
Б 7.3.9 Упражнения к разделу 7.3 Упражнение 7.3.1. Па рис. 7.15 приведена функция щафп на языке программирования М(., которая вычисляет число Фибоначчи нестандартным образом. Функция 11ЬО вычисляет и-е число Фибоначчи для любого и > О. В нее вложена функция 1'1Ы, которая вычисляет и-е число Фибоначчи в предположении и > 2, а в й1Ы вложена функция й1Ь2, вычисляющая и-е число Фибоначчи прн и > 4. Обратите внимание, что ни функции 1'1Ы, ни функции НЪ2 не требуется проверка базовых случаев. Покажите, как выглядит стек записей активации, получающийся при вызове ща1п, в момент непосредственно перед первым возвратом (из й1ЬО (1) ).
Укажите связи доступа для каждой из записей активации в стеке. йцп таеп () ( 1ек бцп 11ЬО(п) 1ес йцп й1Ы (п) 1еп йип 11Ь2(п) = Е1Ы(п-1) + й1Ы(п-2) 1п Н п >= 4 ЬЬеп Й.Ь2(п) е1ве Г1ЬО(п-1) + й1ЪО(п-2) епг) 1п 1й п >= 2 ЬЬеп т1Ъ1(п) е1ве 1 епс( з.п й1ЬО(4) епс1; Рис.
7.15. Вложенные функции, вычисляющие числа Фибоначчн Упражнение 7.3.2. Предположим, что функции на рис. 7.15 реализованы с использованием дисплея. Покажите состояние дисплея в момент непосредственно перед первым выходом из й1ЬО (1). Укажите также сохраненные элементы дисплея в каждой из записей активации, находящихся в этот момент в стеке. 555 7.4.
Управление кучей 7.4 Управление кучей Куча представляет собой часть памяти, использующуюся для размещения данных с неопределенным временем жизни, пока программа не удалит их. В то время как локальные переменные обычно становятся недоступными по окончании их процедур, многие языки программирования позволяют создавать объекты или иные данные, существование которых не привязано к активации создавшей их процедуры.
Например, и С++, и 1ача имеют оператор пем для создания объектов, которые (или указатели на которые) могут быть переданы от процедуры к процедуре, так что они продолжают существовать долгое время после того, как завершится создавшая их процедура. Такие объекты хранятся в куче.
В данном разделе мы рассмотрим диспетчер лалгялги (гпепюгу шапакег)— подсистему, которая выделяет и освобождает память в куче; она служит интерфейсом между прикладной программой и операционной системой. Для языков типа С или С++, которые освобождают блоки памяти вручную (т.е. путем явных инструкций программы, таких как аггее и с1е1еГе), диспетчер памяти отвечает за реализацию освобождения памяти. В разделе 7.5 мы рассмотрим сборку мусора (яагЬаке со!1есйоп) — процесс поиска в куче памяти, которая больше не нужна программе и может быть использована для хранения других данных.
В языках наподобие )ача освобождает память именно сборщик мусора. Там, где он используется, сборщик мусора представляет собой важную подсистему управления памятью. 7.4.1 Диспетчер памяти Диспетчер памяти постоянно отслеживает свободную память в куче. Он выполняет две основные функции. 1.
Выделение ламягпи. Когда программа запрашивает память для переменной или объектаь, диспетчер создает в куче непрерывный блок памяти требуемого размера. По возможности запрос на выделение памяти удовлетворяется путем использования свободной памяти в куче; если же свободного блока требуемого размера нет, предпринимаются попытки увеличения кучи за счет получения блока виртуальной памяти от операционной системы. Если память оказывается исчерпанной, диспетчер передает соответствующую информацию прикладной программе. 2.
Освобождение памяти. Диспетчер памяти возвращает освобожденную память в пул свободной памяти, так что она может затем использоваться для удовлетворения новых запросов на выделение памяти. Диспетчер памяти Мы говорим далее обо всем, что требует выделения памяти, как об "объектах", несмотря на то, что зго не обязательно объекты в смысле объектно-ориентированного программирования. 556 Глава 7. Среды времени выполнения обычно не возвращает память операционной системе даже при снижении или полном прекращении использования кучи.
Управление памятью оказывается более простым, если а) все запросы на выделение памяти оказываются запросами на выделение блоков одного и того же размера и б) память освобождается предсказуемо, скажем, раньше освобождается та память, которая была раньше выделена. Имеются языки, такие, как 1.ьр, в которых выполняется требование а. Чистый [лзр использует только один элемент данных — ячейку с двумя указателями, — из которого строятся все структуры данных.
Условие б также выполняется в некоторых ситуациях; наиболее распространенный случай — данные, память для которых может быть выделена в стеке времени выполнения. Однако в большинстве языков программирования в общем случае не выполняются ни условие а, ни условие 6. Как правило, происходит выделение памяти для объектов разных размеров, причем не существует хорошего способа предсказать времена жизни всех объектов.
Таким образом, диспетчер памяти должен быть готов обслуживать в произвольном порядке запросы на выделение и освобождение памяти любого размера, от одного байта до всего адресного пространства программы. Вот какими свойствами должен обладать хороший диспетчер памяти. ° я7лфектпвлое использование памяти. Диспетчер памяти должен минимизировать общий размер кучи, требующейся программе. Это позволяет большим программам выполняться в фиксированном виртуальном адресном пространстве. Пространственная эффективность достигается ну~ем минимизации "фрагментации", рассматривающейся в разделе 7,4.4, ° Нрограчнная эффективность. Диспетчер памяти должен так использовать подсистему памяти, чтобы программа выполнялась как можно быстрее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
