А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 119
Текст из файла (страница 119)
Таблица )т'ен Еосшгоп. Эта структура может представлять собой хеш-таблицу, дерево поиска или иную структуру, реализующую две операции: а) установку значения ХежЬосаНоп(о) равным новому адресу объекта о; б) получение для данного объекта о значения )Уеи Ьосабол (о). Мы не будем останавливаться на конкретной структуре, хотя вы можете считать, что )УеиЬосаг!ол — хеш-таблица, операции установки и получения значения в которой требуют в среднем постоянного времени, независимого от количества объектов в куче.
Первая фаза — маркировки — состоит из строк 1-7 и, по сути, представляет собой то же, что и первая фаза алгоритма 7.12. На второй фазе (строки 8 — 12) происходит обход всех блоков в выделенной части кучи начиная с нижнего конца, с меньших адресов. В результате блоки получают новые адреса, увеличивающиеся в том же порядке, что и старые адреса. Этот порядок важен, поскольку объекты можно перемещать только "влево", в место, ранее занятое объектами, которые к этому моменту уже перемещены. Строка 8 присваивает указателю )гее адрес начала кучи.
На этой фазе указатель /атее используется для указания первого доступного нового адреса. Новые адреса создаются только для тех объектов о, которые помечены как достижимые. В строке 10 такой объект получает новый адрес, а в строке 11 указатель /гее увеличивается на количество памяти, требующееся объекту о, так что после этого аггее вновь указывает на начало свободной памяти. Последняя фаза (строки 13-17) вновь обходит достижимые объекты в том же порядке слева направо, что и вторая фаза. В строках !5 и 16 все внутренние 586 Глава 7. Среды времени выполнения /* Вычисление новых позиций *! 8) )гее = Начальный адрес памяти кучи; 9) (ог (Каждый блок памяти о в куче, начиная с нижнего конца) ( 1О) 1( (о достижим) ( 1!) )УеюЕосайол (о) =Яее; 12) /атее =аггее + з(гено); /* Изменение ссылок и перенос достижимых объектов *! 13) (ог (Каждый блок памяти о в куче, начиная с нижнего конца) ( 14) Ы (о достижим) ( 15) 1ог (Каждая ссылка ох в о) 16) ох = №и Ьосайол (ох); 17) Копирование о в 79етАосайол (о); 18) 1ог (Каждая ссылка т в корневом множестве) 19) г = №иЕосаг1оп (г); указатели достижимого объекта заменяются корректными новыми значениями с использованием таблицы Меи7осагюп.
После этого в строке 17 выполняется перемещение объекта о с исправленными внутренними ссылками в новое положение. Наконец, в строках 18 и 19 выполняется исправление указателей в тех элементах корневого множества, которые не являются обьектами кучи, т.е. память для них выделена либо статически, либо в стеке. На рис. 7.27 показаны как перемещение достижимых объектов (они не заштрихованы) вниз по куче, так и обновление их внутренних указателей, которые после этого указывают на новые положения перемещенных объектов. и 1) 2) 3) 4) 5) 6) 7) !* Маркировка *! (улесаплей = множество объектов, достижимых из корневого множества; зтй(!е (Блзсаппей ~ И) ( Удалить объект о из Иисаллеа'; 1ог (Каждый объект о', на который имеется ссылка в о) ( 1Г (о' недостижим) ( Пометить о' как достижимый; Поместить о' в список (улясалпед„ Рис.
7.26. Сборщик мусора "пометить и сжать" ".6 Ввснсннс в соорк на основс о~слсжнаания 588 Глава 7. Среды времени выполнения Сору1пдСоПес1ог () ( 1ог (Все объекты о из полупространства агат) Мен2,осаждал (о) = )хПЛЛ,; пвсаппет) = )гее = Начальный адрес полупространства То; ог (Каждая ссылка т в корневом множестве) Заменяем г значением т.оокир№ткГ.оса1зол (г); Ы!е (ипвсаппеИ 4 угее) ( о = объект в позиции ипвсаппет); Гог (Каждая ссылка о.г в о) о.г = ГооГтир1ЧезуТ.осаиоп (о г). ипвсаппес1 = ипвсаппетГ+ в1гео) (о); 1) 2) 3) и 4) 5) 6) и 7) 8) 9) 10) /е Поиск новой позиции перемещенного объекта. */ /* В противном случае помещение объекта в состояние Несканировал.
*! 11) Аоо)сир№нАосайоп (о) ( 12) 1Г (№тсГ.оса11оп (о) = )хПЛЛ.) ( 13) №зсТ.осайол (о) = Ггее; 14) Ггее = Ггее + ягела); 15) Копирование о в позицию ФенАосайоп (о); 16) ге1нгп ЮетуТ.оса11оп (о); Рнс. 7.28. Копирующий сборщик мусора 'Если о не назначена никакая позиция, то н типичной структуре данных, такой как хеш-таблица, просто не будет упоминания об о. лучает объект о и находит его новое положение в полупространстве То„если объект еще не был перемещен. Все новые положения объектов записываются в структуре МвткЬосайол, а значение МЛЛ, указывает, что о пока не имеет назначенной позиции в целевом полупространствеа. Как и в алгоритме 7.15, вид структуры ХеуеТ.оса11оп может варьироваться, но вполне можно считать, что это хеш-таблица.
Если в строке 12 выясняется, что у о пока нет новой позиции, то она назначается в начале свободной памяти в полупространстве 7о (строка 13). В строке 14 указатель аггее увеличивается на количество памяти, выделенной для объекта о, а в строке 15 объект о копируется из полупространства г"гот в полупространство То. Таким образом, перемещение объекта из одного полупространства в другое оказывается побочным действием при первом поиске нового положения объекта. 589 7.6.
Введение в сборку на основе отслеживания Независимо от того, был ли уже перенесен объект, в строке 16 всегда возвращается его новое положение в полупространстве То. Теперь можно приступить к рассмотрению самого алгоритма. Строка 2 устанавливает, что ни один из объектов полупространства Лот не имеет нового адреса. В строке 3 два указателя, ипвсаппей и.1гее, инициализируются начальным адресом полупространства То. Указатель аггее всегда указывает на начало свободной памяти в полупространстве То.
При добавлении объектов в полупространство То те из ннх, адреса которых располагаются ниже ипвсаппег7, находятся в состоянии Сканирован, а объекты с адресами между указателями ипвсапнег1 и /~ее — в состоянии Несканирован. Таким образом, указатель |гее всегда опережает указатель ипвсаппеН, и, когда последний догоняет первый, объектов в состоянии Несканирован не остается и сборка мусора оказывается завершенной. Заметим, что мы работаем с полупространством То, хотя все ссылки в объектах, рассматриваемых в строке 8, ведут в полупространство агат. Строки 4 и 5 обрабатывают объекты, достижимые из корневого множества.
Заметим, что в качестве побочного действия некоторые вызовы Т,оо7гиргУенЕосабоп в строке 5 увеличивают указатель |гее — при выделении блоков памяти для объектов в полупространстве То. Таким образом, вход в цикл в строках б — 10 может не состояться только в одном случае — если корневое множество не содержит ссылки ни на один объект (в этом случае вся куча представляет собой мусор). Этот цикл сканирует все объекты в полупространстве То, находящиеся в состоянии Несканирован. Строка 7 получает очередной несканированный объект о.
Затем в строках 8 и 9 каждая ссылка в о заменяется новым значением, указывающим положение объекта в полупространстве То. В качестве побочного действия, если ссылка в о указывает ранее недостижимый объект, вызов ).оо7гир- ФеггТ.осаггоп в строке 9 выделяет память для этого объекта в полупространстве То н переносит его туда. Наконец, строка 10 увеличивает указатель ипвсаппеЫ так, чтобы он указывал на следующий за о объект в полупространстве То. о 7.6.6 Сравнение стоимости Алгоритм Ченн обладает тем преимуществом, что он никак не затрагивает недостижимые объекты.
С другой стороны, копирующий сборщик мусора вынужден перемещать содержимое всех достижимых объектов. Этот процесс оказывается особенно дорогостоящим в случае больших и долгоживущих объектов, время жизни которых превышает много циклов сборки мусора. Можно резюмировать информацию о времени работы каждого из четырех рассмотренных алгоритмов следующим образом, игнорируя стоимость обработки корневого множества.
° Сборигггк мусора "пометить и подмести" (алгоритм 7.12). Время пропорционально количеству блоков в куче. 590 Глава 7. Среды времени выполнения ° Сборщик мусора "пометить и подмести " Бейкера (алгоритм 7.14). Время пропорционально количеству достижимых объектов. ° Сборщик мусора "пометить и сжать" (алгоритм 7.15). Время пропорционально количеству блоков в куче плюс общий размер достижимых обьектов. ° Копирующий сборщик Чеки (алгоритм 7.16). Время пропорционально общему размеру достижимых объектов.
7.6.7 Упражнения к разделу 7.6 Упражнение 7.6.1. Укажите шаги сборщика мусора "пометить и подмести*' для а) рис. 7.19 с удаленным указателем А — В; б) рис. 7.!9 с удаленным указателем А — С; в) рис. 7.20 с удаленным указателем А — В; г) рис. 7.20 с удаленным объектом В. Упражнение 7.6.2. Алгоритм "пометить и подмести" Бейкера перемещает объекты между четырьмя списками: аггее, !7пгеаслеа, 17пзсаппеа и Бсаппеа. Для каждой сети объектов из упражнения 7.6.! укажите для каждого объекта последовательность списков, в которых он находится с момента до начала сборки мусора и до момента после ее завершения. Упражнение 7.6.3.
Предположим, что мы выполнили сборку мусора "пометить и сжать" для каждой из сетей упражнения 7.6.1. Кроме того, будем считать, что 1. каждый объект имеет размер 100 байт; 2. изначально девять объектов в куче размещены в алфавитном порядке, начиная с нулевого байта кучи. Каким будет адрес каждого объекта по завершении сборки мусора? Упражнение 7.6.4. Предположим, что для каждой из сетей упражнения 7.6.1 выполняется алгоритм копирующей сборки мусора Чени. Предположим также, что !. каждый объект имеет размер 100 байт; 2. список несканированных объектов представляет собой очередь, а когда объект имеет более одного указателя, достижимые объекты помещаются в очередь в алфавитном порядке; 591 7.7.
Распределенная сборка мусора 3. полупространство Рвот начинается с адреса О, полупространство То — с адреса 10 000. Каким будет значение ХеиЕосаГГоп (о) для каждого объекта о, оставшегося после сборки мусора? 7.7 Распределенная сборка мусора Простые сборщики мусора на основе отслеживания работают по принципу "остановись, мгновение" и могут вносить большие паузы в работу пользовательской программы. Сократить паузы можно, выполняя сборку мусора по частям. Можно разнести работу во времени, чередуя сборку мусора и работу программы, а можно разбить ее по пространственному принципу, выполняя при каждом запуске сборку мусора только в определенном подмножестве.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
