А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 123
Текст из файла (страница 123)
Но не может ли возникнуть ситуация, когда на каждом шаге сборки мусора будет создаваться новый ваюн, 603 7.7. Распределенная сборка мусора и в результате первый вагон никогда не будет полностью обработан, и сборка мусора так и не сможет перейти ко второму вагону? К сожалению, такая ситуация возможна. Проблема возникает при наличии большой циклической структуры, ие являющейся мусором, причем мутатор изменяет ссылки таким образом, что во время сборки мусора в вагоне в запомненном множестве никогда не встречаются ссылки из поездов с ббльшими номерами. Если в процессе каждого цикла сборки мусора в вагоне из поезда будет удаляться хотя бы один объект, то все в порядке, поскольку в конечном итоге первый поезд останется совсем без объектов.
Но если окажется, что мусора, который можно собрать, нет, мы рискуем заниматься бесконечной чисткой первого вагона. Чтобы избежать такой ситуации, следует изменить поведение в случае безрезулынитной (Гн!)!е) сборки мусора, т.е. вагона, из которого ии один объект ие удаляется как мусор и не переносится в другой поезд. В этом случае режима паники мы вносим два изменения. !. Когда переписывается ссылка на объект в первом вагоне, она становится новым членом корневого множества.
2. Если при сборке мусора объект в первом вагоне имеет ссылку из корневого множества, включая фиктивные ссылки, созданные первым правилом, то объект перемещается в другой поезд, даже если ссылок иа него из других поездов иет. Не важно, в какой именно поезд будет перемещен объект, лишь бы это не был первый поезд. Таким образом, при наличии ссылок иа объекты в первом поезде извне первого поезда как минимум некоторый обьект будет из этого поезда удален. После этого осуществляется выход из режима паники и возврат к обычному алгоритму.
7.7.6 Упражнения к разделу 7.7 Упражнение 7.7Д. Предположим, что сеть объектов иа рис. 7.20 управляется инкрементным алгоритмом, который использует списки Блгеаслег1, Иисаппес(, осаппей и Раек, как в алгоритме Бсйксра. Пусть для конкретности список !Унксилиег! представляет собой очередь, а при помещении в него в результате сканирования некоторого объекта сразу нескольких объектов, последние вносятся в список в алфавитном порядке. Предположим также, что, чтобы гарантировать, что ни один достижимый объект ие станет мусором, используется барьер записи. Изначально список Иисалпег! состоит из А и В. Пусть далее происходят следующие события. !. Сканируется А.
2. Указатель А — Р переписывается и становится указателем А — Н. 604 Глава 7. Среды времени выполнения 3. Сканируется В. 4. Сканируется Р. 5. Указатель  — С переписывается и становится указателем  — 1. Смоделируйте инкрементную сборку мусора, полагая, что больше никакие указатели не переписываются. Какие объекты являются мусором? Какие объекты помещаются в список В«ее? Упражнение 7.7.2.
Повторите упражнение 7.7.1 в предположении, что а) события 2 и 5 поменялись местами; б) события 2 и 5 происходят до событий 1, 3 и 4. Упражнение 7.7.3. Предположим, что куча состоит из девяти вагонов в трех поездах, как показано на рис. 7.30 (троеточия игнорируются).
На объект о в вагоне 11 имеются ссылки из вагонов 12, 23 и 32. Где может оказаться объект о после сборки мусора в вагоне 11? Упражнение 7.7.4. Повторите упражнение 7.7.3 для случаев, когда ссылки на объект о имеются а) только из вагонов 22 и 31; б) только из вагона !1. Упражнение 7.7.5. Предположим, что куча состоит из девяти вагонов в трех поездах, как показано на рис. 7.30 (троеточия игнорируются).
В настоящий момент мы находимся в режиме паники. На объект сч в вагоне 11 имеется единственная ссылка из объекта оз в вагоне 12. Эта ссылка переписывается. Что произойдет с объектом о1 при сборке мусора в вагоне 11? 7.8 Дополнительные вопросы сборки мусора Завершим наше исследование сборки мусора кратким рассмотрением четырех дополнительных тем. 1. Сборка мусора в параллельных средах. 2, Частичные перемещения объектов. 3.
Сборка мусора в языках программирования, небезопасных с точки зрения типов. 4. Взаимодействие между автоматической и программно-управляемой сборкой мусора. 605 7.8. Дополнительные вопросы сборки мусора 7.8.1 Параллельная сборка мусора Сборка мусора становится особенно сложной при использовании в многопоточных приложениях на мультипроцессорных машинах. Вполне реальна ситуация, когда у серверного приложения параллельно работают тысячи потоков, каждый из которых является мутатором. Куча может состоять из гигабайтов памяти. Масштабируемые алгоритмы сборки мусора должны использовать преимущества многопроцессорности. Будем называть сборщик мусора параллельным, если он использует несколько потоков, а работающий одновременно с мутатором сборщик будем называть конкурентным. Мы опишем параллельный и частично конкурентный сборщик мусора, который использует конкурентную и параллельную фазы для выполнения основной части работы по отслеживанию, а затем переходит на стадию исключительного выполнения, чтобы гарантировать, что найдены все достижимые объекты и утилизирована вся память.
В этом алгоритме нет никаких новых концепций; он просто демонстрирует, как можно скомбинировать рассмотренные ранее идеи для получения полного решения задачи параллельной и конкурентной сборки мусора. Однако перед нами возникают несколько новых вопросов реализации, связанных с параллельностью.
Мы рассмотрим, как алгоритм координирует множественные параллельные потоки с применением весьма распространенной модели очереди. Для понимания алгоритма следует помнить о масштабе задачи. Корневое множество многопоточного приложения существенно больше, чем однопоточного, так как, кроме регистров и глобальных переменных, в него входят стеки всех потоков. Размер кучи также может быть очень большим, как и количество достижимых данных.
Существенно возрастает и скорость изменения данных. Чтобы сократить продолжительность паузы, можно адаптировать уже рассматривавшиеся базовые идеи инкрементного анализа для многопоточного приложения, в котором сборшик мусора и мутатор работают одновременно. Вспомним, что инкрементный анализ состоит из следующих трех шагов (см, раздел 7.7).
1. Поиск корневого множества. Этот шаг обычно выполняется автоматически с остановленным мутатором (или мутаторами). 2. Чередование отслеживания достижимых объектов с выполнением мутатора (или мутаторов). На этом шаге всякий раз, когда мутатор переписывает ссылку из обьекта в состоянии Сканирован на объект в состоянии Недостижим, эта ссылка запоминается.
Как указано в разделе 7.7.2, есть разные варианты детализации запоминания таких ссылок. В этом разделе предполагается использование запоминания на основе карт, когда куча разделяется на части (" карты" ), для которых в сопутствующем битовом массиве отмечается наличие в карте одной или нескольких переписанных ссылок. 606 Глава 7.
Среды времени выполнения 3. Мутатор (или мутаторы) вновь блокируется для повторного сканирования всех карт, которые могут хранить ссылки на недостижимые объекты. В случае больших многопоточных приложений множество объектов, достижимых нз корневого множества, может быть очень большим.
Затрачивать на посещение всех этих объектов время, когда все мутаторы приостановлены, — плохое решение. Кроме того, большой размер кучи и большое количество потоков мутатора приводят к тому, что после того, как все объекты просканнрованы, требуется повторное сканирование большого количества карт. Поэтому было бы разумно выполнять сканирование некоторых из этих карт параллельно, позволяя при этом мутаторам продолжать свою работу. Для реализации параллельного выполнения шага 2 из описанных выше шагов будем одновременно с потоками мутатора использовать несколько потоков сборки мусора для отслеживания большинства достижимых объектов.
Затем, при реализации шага 3, все потоки мутаторов блокируются, а потоки сборщиков работают параллельно, обеспечивая поиск всех достижимых объектов. Отслеживание на шаге 2 выполняется за счет того, что каждый поток мутатора выполняет наряду со своей основной работой часть работы по сборке мусора. Кроме того, используются потоки, вся деятельность которых сосредоточена исключительно на сборке мусора. После начала цикла сборки мусора любое выделение памяти потоком мутатора сопровождается определенными действиями по отслеживанию. Потоки, занимающиеся исключительно сборкой мусора, активизируются только тогда, когда в работе основной программы возникает пауза.
Как и в инкрементном анализе, когда мутатор записывает ссылку, которая указывает из объекта в состоянии Сканировал на объект в состоянии Недостижим, карта, хранящая эту ссылку, помечается как требующая повторного сканирования. Вот как выглядит набросок параллельного конкурентного алгоритма сборки мусора.
Е Сканирование корневого множества для каждого потока мутатора и помещение всех объектов, достижимых непосредственно из корневого множества, в состояние Несканирован. Простейший инкрементный подход состоит в том, чтобы подождать, пока поток мутатора не вызовет диспетчер памяти, н сканировать его корневое множество, если это еще не было сделано. Если некоторый поток мутатора не вызывает функцию выделения памяти, а вся остальная работа по отслеживанию уже выполнена, для сканирования корневого множества этого потока его выполнение следует прервать. 2.
Сканирование объектов, находящихся в состоянии Нескалирован. Для поддержки параллельных вычислений используется очередь рабочих пакетов (юогк расйе1я) фиксированной длины, каждый из которых хранит некоторое количество таких объектов. Несканированные объекты помещаются в ра- 607 7.8. Дополнительные вопросы сборки мусора бочие пакеты в момент обнаружения первых. Потоки извлекают пакеты из очереди и сканируют объекты, находящиеся в них. Такая стратегия позволяет равномерно распределить работу среди участников процесса отслеживания. Если в системе не хватает памяти для создания рабочих пакетов, можно просто маркировать карты с объектами, чтобы обеспечить их сканирование. Это всегда возможно, поскольку память под битовый массив для маркировки карт уже выделена.
3. Сканирование объектов в отмеченных картах. Когда в рабочей очереди не остается несканнрованных объектов и сканированы все корневые множества потоков, выполняется повторное сканирование карт в поиске достижимых объектов. Заметим, что, пока мутаторы работают, будут образовываться новые карты, которые надо сканировать заново. Таким образом, необходимо остановить процесс отслеживания при помощи некоторого критерия, такого как разрешение повторного сканирования карты только один раз (нлн некоторое фиксированное количество раз), или когда количество ожидающих сканирования карт снизится до некоторого порогового значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
