А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 106
Текст из файла (страница 106)
Многие языки программирования позволяют программисту выделять память для данных и освобождать ее под управлением программы. Например, С имеет функции ва11ос и йгее, которые могут использоваться для получения и освобождения блоков памяти требуемого размера. Для управления данными такого вида используется куча. В разделе 7.4 будут рассматриваться различные алгоритмы управления памятью, которые могут использоваться для работы с кучей. 7.1.1 Статическое и динамическое распределение памяти Выделение памяти для данных и схема их размещения в памяти в среде времени выполнения являются ключевыми вопросами управления памятью. Это достаточно сложные вопросы, поскольку одно и то же имя в исходном тексте программы может обозначать несколько разных мест в памяти во время работы про- 528 Глава 7. Среды времени выполнения граммьь Два прилагательных — статическое и динимическое — предназначены для того, чтобы различать действия во время компиляции и во время выполнения программы.
Мы говорим, что решение о выделении памяти статическое, если оно принимается во время компиляции, когда известен только исходный текст программы, но не то, что именно программа делала в процессе работы. И наоборот, решение является динамическим, если оно может быть принято исключительно при выполнении программы. Многие компиляторы используют для динамического выделения памяти некоторую комбинацию двух следующих стратегий. 1. Хранение в стеке.
Память для локальных имен процедуры выделяется в стеке. Стек времени выполнения мы будем рассматривать начиная с раздела 7.2. Стек поддерживает обычную политику вызова процедур и возврата из них. 2. Хранение в куче. Память для данных, которые должны "пережить" вызов создающей их процедуры, обычно выделяется в куче, которая представляет собой многократно используемую память. Работу с кучей мы будем рассматривать начиная с раздела 7.4. Куча представляет собой область виртуальной памяти, которая позволяет объектам или другим элементам данных получать место для хранения при создании и освобождать его, когда эти объекты становятся недействительными.
Одно из средств поддержки управления кучей — "сборка мусора" (йагЬайе со1- 1ес11оп) — позволяет системе времени выполнения находить ненужные элементы данных и повторно использовать занимаемую ими память, даже если программист явно не освободил ее. Автоматическая сборка мусора представляет собой сушественный элемент многих современных языков программирования, несмотря на трудность эффективного выполнения данной операции; в ряде языков применение такой технологии попросту невозможно. 7.2 Выделение памяти в стеке Почти все компиляторы языков программирования, в которых применяются пользовательские функции, процедуры или методы, как минимум часть своей памяти времени выполнения используют в качестве стека. Всякий раз при вызове процедурыз в стеке выделяется пространство для ее локальных переменных, а по завершении процедуры это пространство снимается со стека.
Как мы увидим, такой метод не только позволяет совместно использовать память не перекрывающимся по времени процедурам, но и обеспечивает возможность компиляции кода Напомним, ито "процедура" представляет собой обобщенный термин дяя процедур, функций, методов ияи подпрограмм. 529 7.2. Выделение памяти в стеке процедуры таким образом, что относительные адреса ее нелокальных переменных всегда остаются одними и теми же, независимо от последовательности вызовов процедур. 7.2.1 Деревья активации Выделение памяти в стеке не имело бы столько преимуществ, если бы вызовы, или активации (ас((иа((оп), не могли бы быть вложенными во времени.
Приведенный далее пример иллюстрирует вложенность вызовов процедур. Пример 7.1. На рис. 7.2 приведен набросок программы, которая считывает девять целых чисел в массив а и сортирует их с помощью рекурсивного алгоритма быстрой сортировки. 1пг а[11); зго1с( геас(йггау( ) ( /* Считываем 9 целых чисел в о[Ц, ..., а[9). */ 1пг зз ) 1пс рагс1с1оп(1пг в, 1пТ п) ( /* Выбор разделителя о и разделение а[т ..и) так, что а[т .. р — 1) меньше и, а[р) = и, а а[р + 1..п) не меньше и.
Возврат р. */ ) чоЫ с(ц1с)сзогс(1пс в, 1пс и) ( 1пс з.; 1й (и>в) ( = рагс1г1оп(в, п)з с(п1с)сзогс(в, з.-1); с(п1с)сзогт(1+1, п); ) ваз.п( ) ( геаг)йггау()з а[0] = -9999' а[10) = 9999' с(ц1с)сзогг(1,9)з Рис. 7.2. Набросок программы быстрой сортировки 530 Глава 7. Среды времени выполнения Функция гла(л решает три задачи, Она вызывает функцию геапАпау, устанавливает ограничители, а потом вызывает функцию ~ушсЬогг для всего массива данных.
На рис. 7.3 показана последовательность вызовов, которая может получиться в результате работы программы. При этом вызов раггШол (1, 9) возвращает 4, так что элементы массива с а [1[ по а [3[ хранят значения, меньшие выбранного разделителя и, в то время как значения, ббльшие о, размещаются в элементах от а [5[ до а [9]. и Вход в тайп() Вход в геадЛггау() Выход из геадЛггау() Вход в с)пйс)сзогг(1, 9) Вход в рагГ1Г1оп(1,9) Выход из рагс1сйоп(1,9) Вход в с(пйс)слоге(1,3) Выход из с(ц1с)сзогг(1,3) Вход в с(ц1с)слоге(5, 9) Выход из с(пйс)слоге(5,9) Выход из с(пйс)сзогс(1,9) Выход из влайп() Рис. 7.3. Возможная последовательность активаций программы, представленной на рис. 7.2 В данном примере, как и в общем случае, активации процедур оказываются вложенными во времени.
Если активация процедуры р вызывает процедуру д, то активация д должна завершиться раньше, чем завершится активация р. Обычно складывается одна из трех ситуаций. 1. Активация д завершается нормально. Тогда, по сути, в любом языке программирования управление возвращается в точку р, следующую непосредственно за точкой, в которой был сделан вызов о. 2. Активация д или некоторой процедуры, вызванной д прямо или косвенно, завершается аварийно, т.е. продолжение выполнения программы невозможно. В этом случае р завершается одновременно с д. 3.
Активация д завершается из-за сгенерированного исключения, которое 9 обработать не в состоянии. Процедура р может обработать исключение; в этом случае активация д завершается, в то время как активация р продолжается, хотя и не обязательно с точки, в которой была вызвана 9. Если р 531 7.2. Выделение памяти в стеке Версия быстрой сортировки Набросок программы быстрой сортировки на рис.
7.2 использует две вспомогательные функции: «еайА««ау и ра«йюп. Функция «еайА««ау используется только для загрузки данных в массив а. Первый и последний элементы а не используются для хранения данных, представляя собой ограничители", устанавливаемые функцией гаазп. Считаем, что а [О] имеет значение, меньшее любого возможного значения данных, а а [10] — большее. Функция ра«Шюп разбивает часть массива, определяемую аргументами т и п, таким образом, что меньшие элементы подмножества от а [т] до а [п] находятся в начале, а ббльшие — в конце, хотя эти подгруппы элементов не обязаны находиться в отсортированном порядке. Мы не вдаемся в подробности того, как работает функция ра«гйюп, за исключением того, что она может воспользоваться существованием ограничителей.
Код одного из возможных алгоритмов ра«гйюп представлен на рис. 9.1. Рекурсивная процедура дшс~Ьо«г сначала выясняет, требуется ли сортировать более одного массива. Поскольку один элемент всегда "отсортирован", 9шс1Ьо«г в этом случае не делает ничего. Если же сортировать надо несколько элементов, ди1сЬо«г сначала вызывает ра«йюп, которая возвращает индекс 1 элемента, разделяющего меньшие и ббльшие элементы.
Эти две группы элементов сортируются двумя рекурсивными вызовами дшсЬо«с не может обработать исключение, то данная активация р завершается одновременно с активацией д и, скорее всего, исключение будет обработано некоторой другой открытой активацией процедуры. Следовательно, активации процедур в процессе выполнения всей программы можно представить в виде дерева, называемого деревом акпшвапий (асбчабоп псе).
Каждый узел соответствует одной активации, а корень представляет собой активацию "главной" процедуры, которая инициирует выполнение программы. В узле акгивации процедуры р дочерние узлы соответствуют активациям процедур, вызываемых данной активацией р. Эти активации указываются слева направо в порядке их вызовов. Заметим, что активация, соответствующая дочернему узлу, должна быть завершена до того, как начнется активация его соседа справа. Пример 7.2. Одно из возможных деревьев активации, содержащее полную последовательность вызовов процедур и возвратов из них, показано на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
