Рис. 9.15

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

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

Метод регулирования памяти в виде кучи с использованием счетчика ссылок имеет два основных недостатка:

1. Память, выделенная для определенных структур, не восстанавливается с помощью вышеописанного алгоритма, даже если не будет доступа ни к одному из объемов памяти. Рассмотрим, например, циклический список, показанный на рис. 9.16- Ни один из его счетчиков ссылок не является нулем, хотя никакие указатели извне на него не указывают. Так что этот объем памяти не восстановится.

Рис. 9.16

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

Сборка мусора

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

требовать недоступный объем памяти, а затем уже продолжать свою работу. Конечно, может случиться так, что выполнение программы приостановится для высвобождения памяти, а высвобождать окажется нечего. В этом случае из-за отсутствия памяти программа будет вынуждена завершить свое действие.

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

1. Фаза маркировки. Все адреса (или ячейки), к которым могут (прямо или косвенно) обращаться идентификаторы, имеющиеся в про грамме, маркируются либо путем изменения бита в самой ячейке, либо в отображении памяти в другом месте.

2, Фаза уплотнения. Все маркированные ячейки передвигаются ь один конец кучи (в дальний конец от стека, если эти две области памн-ти увеличиваются навстречу друг другу).

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

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

Нахождение ячеек, доступных для программы, связано с прохождением по древовидным структурам, так как в ячейках могут содержаться указатели на другие структуры. Необходимо пройти по всем путям, представленным этими указателями, возможно,по очереди, а «очевидное> место хранения указателей, по которым еще придется пройти, будет находиться в стеке. Именно это и входит в функции переого алгоритма, который мы далее опишем. Будем считать для простоты. что каждая ячейка имеет максимум два указателя и поле маркировки, невидимое программисту. Поэтому память представляется массивом структур вида

5(гис1 (ш! 1ф, п/гЫ, Ьоо! шаг/1}

Поля 1 еЦ и пцМ - это целочисленные указатели на другие ячейки; для представления нулевого указателя используется нуль. В данном алгоритме нас интересуют только поля указателей и таг1г, остальные (возможные) поля здесь не показаны.

Алгоритм представлен в виде процедуры МАК К 1, где 5ТАС К - стек, используемый сборщиком мусора для хранения указателей, Т - указатель стека, указывающий на его верхний элемент, А - массив структур с индексами, начиная с ], представляющий кучу. После того как все отметки покажут значение «ложь», ячейки, на которые непосредствен-

но ссылаются идентификаторы в программе, или другие значения в стеке времени прогона, маркируются, и их адреса помещаются в STAC К-Далее берется верхний элемент из STAC К. маркируются непомеченные ячейки, на которые указывает ячейка, находящаяся .по этому адресу, и их адреса помещаются в STAC А. Выполнение алгоритма завершается, когда STAC К становится пустым.

ргос MARK I --laid befjn inl Л;

Т minusab 1:

if tufi of no<

rlotA[k}}-

Iben mark of Л [right of A [*]] : = trac; Tplusab I;

SrACK[T]. = ngl,iatA[k]

До вызова этой процедуры куча могла иметь вид табл. 9.1, где маркировано только Л[31, потому что на него есть прямая ссылка идентификатора в программе. Результатом выполнения алгоритма будет маркировка Л [5], А [\ \ и А\2] в указанном порядке.

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

Как и в предыдущем алгоритме, здесь считается, что ячейки, на которые есть прямые ссылки идентификаторов в программе или значений, находящихся в стеке времени прогона, уже маркированы. Ячейки в куче представлены массивом А с границами /, М:

ргос

begin int k, kl. ь2: kl: = I.

while A-2 : = :=.» + /,

for k from k2 m M do it murk of A[k]

then if/i/r of -I[A]-(land

not mark of A\left of /f [tj]: Oienmark of A\lefl of A[iJJ :- (rue,

il: - mm (Icfl of -t[*-], t/) fi. if right ttf A[k] r 0 md

nol mark of A[riglti of A[k]] Ihen mark of A[riglii of A{k]] :- true

fi fi

kl < .1/ do skip od

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

В другом крайнем ел>чае, когда нужен алгоритм, которому требуется небольшой фиксированный объем памяти, м не так важна эффективность по времени, наилучшим решением [фсдстаиляетея процедура MAR К 2, нуждающаяся в рабочей памяти только для трех. целых чисел: k, kl н kl. Эта процедура просматривает всю кучу в поисках указателей от маркированных ячеек к немаркированным, маркирует последние и запоминает наименьший адрес ячейки, маркированной таким образом. Затем она повторяет этот процесс, но начинает с наименьшего адреса, маркированного в прошлый раз, и так до тех

min представляет собой процедуру, значением которой является минимум ее двух параметров.

Если этот алгоритм применяется в примере, который рассматривался в связи с предыдущим алгоритмом (MAR К /), то ячейки маркируются в том же порядке (5, /, 2).

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

Вместо стека произвольного размера, как в MAR К 1, применяется стек фиксированного размера. Чем он больше, тем меньше времени может занять выполнение алгоритма. При достаточно большом стеке алгоритм действует точно так же, как MaR К 1. Однако поскольку стек нельзя расширять, алгоритм должен уметь обращаться с переполнением, если оно произойдет. Когда стек заполняется, из него удаляется одно значение, чтобы освободить место для другого, добавляемого значения. Для запоминания удаленного таким образом из стека самого нижнего адреса используется целочисленная переменная (это аналогично тому, что происходит в MAR К 2). Стек работает циклично с двумя указателями: один указывает наверх, другой вниз; это позволяет не перемещать все элементы стека при удалении из него одного элемента (рис. 9.17). Большей частью алгоритм выполняется как MAR К 1, и когда стек становится пустым, завершает свою работу, если только

1.1-.. 13

Г л а в а 10. ГЕНЕРАЦИЯ КОДА

Как уже отмечалось, процесс компиляции можно разбить на две стадии - анализ синтез. Главы 10 и 11(и в большой степени гл. 9) посвящены стадии синтеза. Проанализировав программу и поместив в таблицу информацию, требуемую для генерации кода, компилятор должен переходить к построению соответствующей программы а машинном коде.

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

В этой и в следующей главах мы будем считать, что фактически для получения машинного кода требуется два отдельнтх прохода:

1) генерация независящего от машины промежуточного кода (или объектного языка);

2) генерация машинного кода (или кода сборки) для конкретной машины. Во многих компиляторах оба эти процесса выполняются за один проход.

10.1. ПРОМЕЖУТОЧНЫЙ КОД

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

Одним из видов промежуточного кода являются четверки (см. гл.6).

Например, выражение

(- a + b) X (c + d) можно представить как четверки следующим образом:

- a = 1

1 + b = 2 c + d = 3

2 X 3 = 4

Здесь целые числа соответствуют идентификаторам, присваиваемым компилятором. Четверки можно считать промежуточным кодом высокого уровня. Такой код часто называют трехадресным - два адреса для операндов (кроме тех случаев, когда имеют место унарные операции) и один для результата. Другой вариант кода - тройки (двухадресный код). Каждая тройка состоит из двух адресов операндов и знака операции. Если сам операнд является тройкой, то используется ее позиция, что исключает необходимость иметь в каждой тройке адрес результата.