Для программирования в реальном времени подсчет ссылок имеет преимущество перед сборкой мусора с точки зрения детерминизма?

Question

Если бы вы разрабатывали язык программирования с автоматическим управлением памятью, можно ли с помощью подсчета ссылок обеспечить гарантии детерминизма, которые невозможны для сборщика мусора?

Будет ли другой ответ на этот вопрос для функциональных и императивных языков?

Answer 1

Позволит ли использование подсчета ссылок обеспечить гарантии детерминизма, которые невозможны для сборщика мусора?

Слово гарантия является сильным. Вот гарантии, которые вы можете предоставить при подсчете ссылок:

• Постоянные накладные расходы времени при назначении для настройки счетчиков ссылок.

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

• Постоянное время для выделения нового объекта , когда соответствующий свободный список не пуст . Эта гарантия условна и не стоит много.

Вот некоторые вещи, которые вы не можете гарантировать при подсчете ссылок:

• Постоянное время для выделения нового объекта. (В худшем случае, куча может расти, и в зависимости от системы задержка для организации новой памяти может быть значительной. Или даже хуже, вы можете заполнить кучу и быть не в состоянии выделить.)

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

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

Одной из лучших последних работ по подсчету ссылок являются Дэвид Бэкон из IBM и Эрез Петранк из Technion. Если вы хотите узнать, на что способна современная сложная система подсчета ссылок, посмотрите их документы. Помимо всего прочего, они удивительным образом используют несколько процессоров.

Более подробную информацию об управлении памятью и гарантиях в реальном времени можно получить на Международном симпозиуме по управлению памятью .

Будет ли другой ответ на этот вопрос для функциональных и императивных языков?

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

Answer 2

будет ли использование подсчета ссылок обеспечивать гарантии детерминизма, которые невозможны для сборщика мусора?

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

Единственный способ решения проблемыGC для систем реального времени - с использованием либо параллельного коллектора, либо инкрементного - и не важно, использует ли система подсчет ссылок или нет;на мой взгляд, ваше различие между подсчетом ссылок и «сбором» в любом случае не является точным, например, системы, использующие подсчет ссылок, могут все еще время от времени выполнять некоторую очистку памяти (например, для обработки циклов).

Вас могут заинтересовать Метроном IBM , и я также знаю, что Microsoft провела некоторые исследования в направлении хорошего управления памятью в реальном времени.

Answer 3

Если вы посмотрите на спецификацию RTSJ (JSR-1), вы увидите, что они обошли проблему, предоставив потоки реального времени без кучи. Имея отдельную категорию потока, которой не разрешается касаться каких-либо объектов, для которых может потребоваться остановка потока для сбора мусора, сторона JSR-1 пошла на решение проблемы. В настоящее время существует не так много реализаций RTSJ, но область сбора мусора в реальном времени является горячей темой в этом сообществе.

Answer 4

Для программирования в реальном времени подсчет ссылок имеет преимущество перед сборкой мусора с точки зрения детерминизма?

Да.Основным преимуществом подсчета ссылок является простота.

Если бы вы разрабатывали язык программирования с автоматическим управлением памятью, допускало бы использование подсчета ссылок гарантии детерминизма, которые невозможны для сборщика мусора?

ГК, подобный беговой дорожке Baker's, должен достичь того же уровня гарантий относительно детерминизма, который предлагает подсчет ссылок.

Будет ли другой ответ на этот вопрос для функциональных и императивных языков?

Да.Подсчет ссылок сам по себе не обрабатывает циклы.Некоторые функциональные языки делают невозможным создание циклов по замыслу (например, Erlang и Mathematica), поэтому они тривиально допускают только подсчет ссылок в качестве точного подхода к GC.

Answer 5

В реальном времени программирование сборки мусора может быть вредным, потому что вы не знаете, когда будет собирать сборщик мусора ... так что да, подсчет ссылок определенно лучше в этом контексте.

Как примечание: обычно в режиме реального времени система требует обработки только некоторых частей в реальном времени, поэтому вы можете избежать сбора мусора только в чувствительных компонентах. Примером из реальной жизни является программа на C #, работающая на цели Windows CE.

Answer 6

Из некоторого участия в различных проектах по переносу значительных кусков кода из C ++ (с различными классами интеллектуальных указателей, включая подсчет ссылок) в сборку мусора Java / C #, я замечаю, что самые большие болевые точки, похоже, связаны с классаминепустые деструкторы (особенно при использовании для RAII).Это довольно большой признак того, что ожидается детерминированная очистка.

Проблема, безусловно, практически одинакова для любого языка с объектами;Я не думаю, что гибридные ОО-функциональные языки, такие как Scala или Ocaml, имеют какие-то особые преимущества в этой области.Ситуация может быть иной для более «чистых» функциональных языков.