А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 125
Текст из файла (страница 125)
В языках программирования, которые позволяют локальным переменным быть недоступными после завершения процедуры (или требуют этого), память для локальных переменных может быть выделена в стеке времени выполнения. В таких языках каждая активная в настоящий момент активация имеет в стеке управления запись активации (или кадр), причем корень дерева активаций находится на дне стека, а последовательность записей активации в стеке соответствует пути в дереве активаций от корня к активации, выполняющейся в настоящее время процедуры.
Запись последней активации находится на вершине стека управления. + Доступ к нелокальным данным в стеке. Для языков программирования наподобие С, в которых запрещены вложенные объявления процедур, все переменные либо являются глобальными, либо находятся в записи активации 612 Глава 7. Среды времени выполнения на вершине стека времени выполнения. В случае языков программирования с вложенными процедурами возможно обращение к нелокальным данным в стеке посредством связей доступа, которые представляют собой указатели, добавляемые к каждой записи активации. Требуемые нелокальные данные можно найти, проследовав по цепочке связей доступа к необходимой записи активации.
Вместе со связями доступа может использоваться дисплей, который представляет собой вспомогательный массив, обеспечивающий эффективную альтернативу цепочке указателей. + Управление кучей. Куча представляет собой часть памяти, использующуюся для данных с неограниченным временем жизни (или временем, ограниченным самой программой, которая явно уничтожает эти данные). Диспетчер памяти выделяет память в куче и освобождает ее. Сборка мусора находит в куче пространство, которое больше не используется и может быть выделено для размещения в нем других данных. В языках с использованием сборки мусора последняя является важной подсистемой управления памятью. + Использование локальности.
Эффективно используя иерархию памяти, диспетчеры памяти могут существенно влиять на время работы программы. Время, затрачиваемое на доступ к различным частям памяти, может варьироваться от наносекунд до миллисекунд, К счастью, большинство программ, в основном, затрачивают время на выполнение относительно малых частей кода и работают только с малыми частями данных. Программа обладает временной локальностью, если высока вероятность, что в ближайшее время она обратится к тем же данным, что и в настоящий момент; пространственная локальность означает, что, скорее всего, программа в ближайшее время обратится к данным, находящимся рядом с теми данными, с которыми она работает в настоящий момент.
+ Снижение фрагментации. В процессе выделения и освобождения памяти куча может стать фрагментированной, т.е. разбитой на большое количество несмежных блоков свободной памяти. Эмпирически доказано, что неплохо работает стратегия наилучшего подходящего, состоящая в выделении наименьшего из доступных блоков свободной памяти, удовлетворяющих запросу. Однако при том, что эта стратегия обычно эффективнее других использует свободную память, с точки зрения пространственной локальности она оказывается не самой лучшей.
Фрагментация может быть уменьшена путем слияния соседних свободных блоков памяти. + Освобождение памяти вручную. Управление памятью вручную обычно приводит к двум распространенным ошибкам: "неудаление данных", к ко- 613 7тк Резюме к главе 7 торым нельзя обратиться, приводит к утечке памяти, а обращение к уда- ленным данным — к ошибке разыменования висящего указателя.
+ Достижимость. Мусором называются недостижимые данные, к которым невозможно обратиться. Существует два основных способа поиска недостижимых объектов: перехват перехода достижимых объектов в недостижимые и периодическое выявление всех достижимых объектов (все остальные объекты — недостижимые). + Сборщики с подсчетом ссылок поддерживают счетчик количества ссылок на объект; когда количество ссылок становится равным нулю, объект становится недостижимым.
Такие сборщики характеризуются дополнительными накладными расходами на поддержание ссылок и могут некорректно обрабатывать ситуацию "циклического мусора", который состоит из недостижимых объектов, указывающих друг на друга, возможно, посредством цепочки ссылок. + Сборщики мусора на основе отслеживания итеративно исследуют, или отслеживают, все ссылки для выявления достижимых объектов, начиная с корневого множества, состоящего из объектов, обращение к которым может быть выполнено непосредственно, без разыменования каких-либо указателей. + Сборщики "пометить и подмести" на первом этапе посещают и помечают все достижимые объекты, а затем "подметают" кучу, освобождая память, занятую недостижимыми объектами.
+ Сборщики "пометить и сжать" являются усовершенствованием сборщиков "пометить и подмести"; они перемещают достижимые объекты в куче для устранения фрагментации памяти. + Копирующие сборщики отделяют отслеживание от поиска свободной памяти. Они разделяют память на полупространства А и В. Запросы на выделение памяти удовлетворяются из одного полупространства, скажем, А, пока оно не будет исчерпано. В этот момент в действие вступает сборщик мусора, который копирует достижимые объекты в полупространство В, после чего меняет роли полупространств. + Инкрементные сборщики.
Простые сборщики, основанные на отслеживании, приостанавливают выполнение программы на время сборки мусора. Инкрементные сборщики чередуют свои действия по сборке мусора с работой лчутатора, или пользовательской программы. Мутатор может влиять 614 Глава 7. Среды времени выполнения на инкрементный анализ достижимости, изменяя ссылки в уже отсканированных объектах. Таким образом, инкрементные сборщики мусора обеспечивают безопасность определенной переоценкой множества достижимых объектов; появляющийся "плавающий мусор" может быть собран в очередном цикле сборки мусора. + Частичные сборщики также уменьшают паузы в основной программе; за один цикл они собирают только часть мусора.
Среди алгоритмов частичной сборки наиболее известна сборка мусора по поколениям, подразделяющая объекты в соответствии с их "возрастом" и выполняющая сборку среди новых объектов чаще, чем среди старых, поскольку обычно время жизни объектов невелико. Другой алгоритм — алгоритм поезда — использует разделы фиксированного размера, именуемые вагонами, собранные в поезда. Каждый цикл сборки работает с первым оставшимся вагоном первого оставшегося поезда. После сборки мусора в вагоне достижимые объекты перемещаются из него в другие вагоны, так что вагон остается только с мусором и удаляется из поезда. Эти два алгоритма используются совместно для создания частичного сборщика, в котором к молодым объектам применяется сборка по поколениям, а к старым — алгоритм поезда.
7.10 Список литературы к главе 7 В математической логике правила областей видимости и передача параметров подстановкой датируются выходом работы Фрега (Ргеяе) [81. Лямбда-исчисление Черча (С!зпгс!з) [31 использует лексическую область видимости; оно используется в качестве модели для изучения языков программирования. Лексические области видимости используют А!яо1 60 и его наследники, включая С и )ача. Будучи использованной в начальной реализации !!ар, динамическая область видимости стала неотьемлемым свойством этого языка; описание этой истории можно прочесть у Мак-Карти (МсСап!зу) [14]. Многие концепции, связанные с выделением памяти в стеке, были разработаны в связи с блоками и рекурсией в языке программирования А!яо! 60.
Идея дисплея для доступа к нелокальным переменным в языке с лексическими областями видимости принадлежит Дейкстре (Гй)!гз!га) [5!. Детальное описание выделения памяти в стеке, использование дисплеев и динамическое выделение памяти для массивов можно найти в книге Ренделла (Калде!1) и Рассела (КпааеП) [161. Джонсон (Яо!зпзоп) и Риччи (Ы!сЫе) [10) рассматривают дизайн вызывающей последовательности, которая позволяет количеству аргументов процедуры изменяться от вызова к вызову. Сборка мусора была областью активных исследований; см., например, работу Вильсона (М!зоп) [17[.
Счетчики ссылок впервые описаны в работе Коллинза 615 7.10. Список литературы к главе 7 (Сей!па) !4], а сборка мусора на основе отслеживания — в работе Мак-Карти (МсСагйу) !! 3], который описал алгоритм "пометить и подмести" для ячеек фиксированного размера. Использование дескрипторов границ для управления свободной памятью было предложено Кнутом (Кпий) в 1962 году и опубликовано в 111]. Алгоритм 7.14 основан на работе Бейкера (Ва(гег) 11], а алгоритм 7.16 — на нерекурсивной версии копирующего сборщика Феничела (РешсЬе1) и Йочельсона (госЬе1аоп) !7], разработанной Чени (СЬепеу) !2].
Инкрементный анализ достижимости открыт Дейкстрой (13!1!гагга) с коллегами (6]. Либерман (Е|еЬеппап) и Хьюитт (Нечч)п) [12] представили сборщик мусора по поколениям, как расширение копирующей сборки. Алгоритм поезда разработан Хадсоном (Ниг!зоп) и Моссом (Мова) !9]. 1. Ва)гег, Н. б. 1г., "ТЬе Сгеадпнй: геа1-йпе йагЬайе сойесбоп чч!1ЬоиГ пюбоп а!с1спезз", АСМ ЯОРТА7ч' 7ч'огГсее 27:3 (Маг., 1992), рр. 66 — 70. 2. СЬепеу, С.
1., "А попгесигяче Па! сошрасбп8 а18ойгЬш", Сотт. АСМ 13:11 ()ч(оч., 1970), рр. 677 — 678. 3. С1шгсЬ, А., 7йе Са!си1с' о7' Т.атЬйа Сопчетгоп, Аппа!з оГ Май. Бшйез, Ыо. 6, Рйпсесоп 1)шчегя!у Ргезз, РПпсе!оп, 1ч!. 3., 194!. 4. Сойша, б. Е., "А шеГЬог! 1ог очег!аррш8 апг! егааиге оГ Багз", Сотт. АСМ 2:12 (Оес., 1960), рр. 655 — 657. 5. В!]!гаГга, Е. чч'., "Кесигяче ргойгагппнп8", )ч!шпейзсЬе МаГЬ.
2 (1960), рр. 312— 318. 6. Эфсагга, Е. %., 1.. ЕагпрогГ, А. 1. Маг!!п, С. Я. БсЬойеп, апг! Е. Е М. Бгейепз, "Оп-гЬе-Пу 8агЬайе соПесгюп: ап ехегсгае !п соорегаг(оп", Сотт. АСМ 21:11 (1978), рр. 966-975. 7. Реп(сЬе!, К. К. апг! 1. С. УосЬе1воп, "А 1лзр 8агЪайе-сойесгог 1ог ч!ггиа1- шепюгу согпригег зузгешз'*, Сотт. АСМ 12:11 (1969), рр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
